… | |
… | |
750 | |
750 | |
751 | 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 | |
752 | |
753 | =back |
753 | =back |
754 | |
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. |
|
|
820 | |
|
|
821 | =back |
|
|
822 | |
755 | =head2 HOST ENDIANNESS CONVERSION |
823 | =head2 HOST ENDIANNESS CONVERSION |
756 | |
824 | |
757 | =over |
825 | =over |
758 | |
826 | |
759 | =item uint_fast16_t ecb_be_u16_to_host (uint_fast16_t v) |
827 | =item uint_fast16_t ecb_be_u16_to_host (uint_fast16_t v) |