| … | |
… | |
| 732 | =item uint64_t ecb_rotr64 (uint64_t x, unsigned int count) |
732 | =item uint64_t ecb_rotr64 (uint64_t x, unsigned int count) |
| 733 | |
733 | |
| 734 | These two families of functions return the value of C<x> after rotating |
734 | These two families of functions return the value of C<x> after rotating |
| 735 | all the bits by C<count> positions to the right (C<ecb_rotr>) or left |
735 | all the bits by C<count> positions to the right (C<ecb_rotr>) or left |
| 736 | (C<ecb_rotl>). There are no restrictions on the value C<count>, i.e. both |
736 | (C<ecb_rotl>). There are no restrictions on the value C<count>, i.e. both |
| 737 | zero and values equal or larger than the word width work correctly. |
737 | zero and values equal or larger than the word width work correctly. Also, |
|
|
738 | notwithstanding C<count> being unsigned, negative numbers work and shift |
|
|
739 | to the opposite direction. |
| 738 | |
740 | |
| 739 | Current GCC/clang versions understand these functions and usually compile |
741 | Current GCC/clang versions understand these functions and usually compile |
| 740 | them to "optimal" code (e.g. a single C<rol> or a combination of C<shld> |
742 | them to "optimal" code (e.g. a single C<rol> or a combination of C<shld> |
| 741 | on x86). |
743 | on x86). |
| 742 | |
744 | |
| … | |
… | |
| 745 | =item T ecb_rotr (T x, unsigned int count) [C++] |
747 | =item T ecb_rotr (T x, unsigned int count) [C++] |
| 746 | |
748 | |
| 747 | Overloaded C++ rotl/rotr functions. |
749 | Overloaded C++ rotl/rotr functions. |
| 748 | |
750 | |
| 749 | C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>. |
751 | C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>. |
|
|
752 | |
|
|
753 | =back |
|
|
754 | |
|
|
755 | =head2 BIT MIXING, HASHING |
|
|
756 | |
|
|
757 | Sometimes you have an integer and want to distribute its bits well, for |
|
|
758 | example, to use it as a hash in a hashtable. A common example is pointer |
|
|
759 | values, which often only have a limited range (e.g. low and high bits are |
|
|
760 | often zero). |
|
|
761 | |
|
|
762 | The following functions try to mix the bits to get a good bias-free |
|
|
763 | distribution. They were mainly made for pointers, but the underlying |
|
|
764 | integer functions are exposed as well. |
|
|
765 | |
|
|
766 | As an added benefit, the functions are reversible, so if you find it |
|
|
767 | convenient to store only the hash value, you can recover the original |
|
|
768 | pointer from the hash ("unmix"), as long as your pinters are 32 or 64 bit |
|
|
769 | (if this isn't the case on your platform, drop us a note and we will add |
|
|
770 | functions for other bit widths). |
|
|
771 | |
|
|
772 | The unmix functions are very slightly slower than the mix functions, so |
|
|
773 | it is equally very slightly preferable to store the original values wehen |
|
|
774 | convenient. |
|
|
775 | |
|
|
776 | The underlying algorithm if subject to change, so currently these |
|
|
777 | functions are not suitable for persistent hash tables, as their result |
|
|
778 | value can change between diferent versions of libecb. |
|
|
779 | |
|
|
780 | =over |
|
|
781 | |
|
|
782 | =item uintptr_t ecb_ptrmix (void *ptr) |
|
|
783 | |
|
|
784 | Mixes the bits of a pointer so the result is suitable for hash table |
|
|
785 | lookups. In other words, this hashes the pointer value. |
|
|
786 | |
|
|
787 | =item uintptr_t ecb_ptrmix (T *ptr) [C++] |
|
|
788 | |
|
|
789 | Overload the C<ecb_ptrmix> function to work for any pointer in C++. |
|
|
790 | |
|
|
791 | =item void *ecb_ptrunmix (uintptr_t v) |
|
|
792 | |
|
|
793 | Unmix the hash value into the original pointer. This only works as long |
|
|
794 | as the hash value is not truncated, i.e. you used C<uintptr_t> (or |
|
|
795 | equivalent) throughout to store it. |
|
|
796 | |
|
|
797 | =item T *ecb_ptrunmix<T> (uintptr_t v) [C++] |
|
|
798 | |
|
|
799 | The somewhat less useful template version of C<ecb_ptrunmix> for |
|
|
800 | C++. Example: |
|
|
801 | |
|
|
802 | sometype *myptr; |
|
|
803 | uintptr_t hash = ecb_ptrmix (myptr); |
|
|
804 | sometype *orig = ecb_ptrunmix<sometype> (hash); |
|
|
805 | |
|
|
806 | =item uint32_t ecb_mix32 (uint32_t v) |
|
|
807 | |
|
|
808 | =item uint64_t ecb_mix64 (uint64_t v) |
|
|
809 | |
|
|
810 | Sometimes you don't have a pointer but an integer whose values are very |
|
|
811 | badly distributed. In this case you cna sue these integer versions of the |
|
|
812 | mixing function. No C++ template is provided currently. |
|
|
813 | |
|
|
814 | =item uint32_t ecb_unmix32 (uint32_t v) |
|
|
815 | |
|
|
816 | =item uint64_t ecb_unmix64 (uint64_t v) |
|
|
817 | |
|
|
818 | The reverse of the C<ecb_mix> functions - they take a mixed/hashed value |
|
|
819 | and recover the original value. |
| 750 | |
820 | |
| 751 | =back |
821 | =back |
| 752 | |
822 | |
| 753 | =head2 HOST ENDIANNESS CONVERSION |
823 | =head2 HOST ENDIANNESS CONVERSION |
| 754 | |
824 | |
