doc
|
00001 /* 00002 * c_jhash.c Jenkins Hash 00003 * 00004 * Copyright (c) 1997 Bob Jenkins <bob_jenkins@burtleburtle.net> 00005 * 00006 * lookup8.c, by Bob Jenkins, January 4 1997, Public Domain. 00007 * hash(), hash2(), hash3, and _c_mix() are externally useful functions. 00008 * Routines to test the hash are included if SELF_TEST is defined. 00009 * You can use this free for any purpose. It has no warranty. 00010 * 00011 * See http://burtleburtle.net/bob/hash/evahash.html 00012 */ 00013 00014 /** 00015 * @file c_jhash.h 00016 * 00017 * @brief Interface of the cynapses jhash implementation 00018 * 00019 * @defgroup cynJHashInternals cynapses libc jhash function 00020 * @ingroup cynLibraryAPI 00021 * 00022 * @{ 00023 */ 00024 #ifndef _C_JHASH_H 00025 #define _C_JHASH_H 00026 00027 #include <stdint.h> 00028 00029 #define c_hashsize(n) ((uint8_t) 1 << (n)) 00030 #define c_hashmask(n) (xhashsize(n) - 1) 00031 00032 /** 00033 * _c_mix -- Mix 3 32-bit values reversibly. 00034 * 00035 * For every delta with one or two bit set, and the deltas of all three 00036 * high bits or all three low bits, whether the original value of a,b,c 00037 * is almost all zero or is uniformly distributed, 00038 * If _c_mix() is run forward or backward, at least 32 bits in a,b,c 00039 * have at least 1/4 probability of changing. 00040 * If _c_mix() is run forward, every bit of c will change between 1/3 and 00041 * 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) 00042 * _c_mix() was built out of 36 single-cycle latency instructions in a 00043 * structure that could supported 2x parallelism, like so: 00044 * a -= b; 00045 * a -= c; x = (c>>13); 00046 * b -= c; a ^= x; 00047 * b -= a; x = (a<<8); 00048 * c -= a; b ^= x; 00049 * c -= b; x = (b>>13); 00050 * ... 00051 * 00052 * Unfortunately, superscalar Pentiums and Sparcs can't take advantage 00053 * of that parallelism. They've also turned some of those single-cycle 00054 * latency instructions into multi-cycle latency instructions. Still, 00055 * this is the fastest good hash I could find. There were about 2^^68 00056 * to choose from. I only looked at a billion or so. 00057 */ 00058 #define _c_mix(a,b,c) \ 00059 { \ 00060 a -= b; a -= c; a ^= (c>>13); \ 00061 b -= c; b -= a; b ^= (a<<8); \ 00062 c -= a; c -= b; c ^= (b>>13); \ 00063 a -= b; a -= c; a ^= (c>>12); \ 00064 b -= c; b -= a; b ^= (a<<16); \ 00065 c -= a; c -= b; c ^= (b>>5); \ 00066 a -= b; a -= c; a ^= (c>>3); \ 00067 b -= c; b -= a; b ^= (a<<10); \ 00068 c -= a; c -= b; c ^= (b>>15); \ 00069 } 00070 00071 /** 00072 * _c_mix64 -- Mix 3 64-bit values reversibly. 00073 * 00074 * _c_mix64() takes 48 machine instructions, but only 24 cycles on a superscalar 00075 * machine (like Intel's new MMX architecture). It requires 4 64-bit 00076 * registers for 4::2 parallelism. 00077 * All 1-bit deltas, all 2-bit deltas, all deltas composed of top bits of 00078 * (a,b,c), and all deltas of bottom bits were tested. All deltas were 00079 * tested both on random keys and on keys that were nearly all zero. 00080 * These deltas all cause every bit of c to change between 1/3 and 2/3 00081 * of the time (well, only 113/400 to 287/400 of the time for some 00082 * 2-bit delta). These deltas all cause at least 80 bits to change 00083 * among (a,b,c) when the _c_mix is run either forward or backward (yes it 00084 * is reversible). 00085 * This implies that a hash using _c_mix64 has no funnels. There may be 00086 * characteristics with 3-bit deltas or bigger, I didn't test for 00087 * those. 00088 */ 00089 #define _c_mix64(a,b,c) \ 00090 { \ 00091 a -= b; a -= c; a ^= (c>>43); \ 00092 b -= c; b -= a; b ^= (a<<9); \ 00093 c -= a; c -= b; c ^= (b>>8); \ 00094 a -= b; a -= c; a ^= (c>>38); \ 00095 b -= c; b -= a; b ^= (a<<23); \ 00096 c -= a; c -= b; c ^= (b>>5); \ 00097 a -= b; a -= c; a ^= (c>>35); \ 00098 b -= c; b -= a; b ^= (a<<49); \ 00099 c -= a; c -= b; c ^= (b>>11); \ 00100 a -= b; a -= c; a ^= (c>>12); \ 00101 b -= c; b -= a; b ^= (a<<18); \ 00102 c -= a; c -= b; c ^= (b>>22); \ 00103 } 00104 00105 /** 00106 * @brief hash a variable-length key into a 32-bit value 00107 * 00108 * The best hash table sizes are powers of 2. There is no need to do 00109 * mod a prime (mod is sooo slow!). If you need less than 32 bits, 00110 * use a bitmask. For example, if you need only 10 bits, do 00111 * h = (h & hashmask(10)); 00112 * In which case, the hash table should have hashsize(10) elements. 00113 * 00114 * Use for hash table lookup, or anything where one collision in 2^32 is 00115 * acceptable. Do NOT use for cryptographic purposes. 00116 * 00117 * @param k The key (the unaligned variable-length array of bytes). 00118 * 00119 * @param length The length of the key, counting by bytes. 00120 * 00121 * @param initval Initial value, can be any 4-byte value. 00122 * 00123 * @return Returns a 32-bit value. Every bit of the key affects every bit 00124 * of the return value. Every 1-bit and 2-bit delta achieves 00125 * avalanche. About 36+6len instructions. 00126 */ 00127 static inline uint32_t c_jhash(const uint8_t *k, uint32_t length, uint32_t initval) { 00128 uint32_t a,b,c,len; 00129 00130 /* Set up the internal state */ 00131 len = length; 00132 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ 00133 c = initval; /* the previous hash value */ 00134 00135 while (len >= 12) { 00136 a += (k[0] +((uint32_t)k[1]<<8) +((uint32_t)k[2]<<16) +((uint32_t)k[3]<<24)); 00137 b += (k[4] +((uint32_t)k[5]<<8) +((uint32_t)k[6]<<16) +((uint32_t)k[7]<<24)); 00138 c += (k[8] +((uint32_t)k[9]<<8) +((uint32_t)k[10]<<16)+((uint32_t)k[11]<<24)); 00139 _c_mix(a,b,c); 00140 k += 12; len -= 12; 00141 } 00142 00143 /* handle the last 11 bytes */ 00144 c += length; 00145 /* all the case statements fall through */ 00146 switch(len) { 00147 case 11: c+=((uint32_t)k[10]<<24); 00148 case 10: c+=((uint32_t)k[9]<<16); 00149 case 9 : c+=((uint32_t)k[8]<<8); 00150 /* the first byte of c is reserved for the length */ 00151 case 8 : b+=((uint32_t)k[7]<<24); 00152 case 7 : b+=((uint32_t)k[6]<<16); 00153 case 6 : b+=((uint32_t)k[5]<<8); 00154 case 5 : b+=k[4]; 00155 case 4 : a+=((uint32_t)k[3]<<24); 00156 case 3 : a+=((uint32_t)k[2]<<16); 00157 case 2 : a+=((uint32_t)k[1]<<8); 00158 case 1 : a+=k[0]; 00159 /* case 0: nothing left to add */ 00160 } 00161 _c_mix(a,b,c); 00162 00163 return c; 00164 } 00165 00166 /** 00167 * @brief hash a variable-length key into a 64-bit value 00168 * 00169 * The best hash table sizes are powers of 2. There is no need to do 00170 * mod a prime (mod is sooo slow!). If you need less than 64 bits, 00171 * use a bitmask. For example, if you need only 10 bits, do 00172 * h = (h & hashmask(10)); 00173 * In which case, the hash table should have hashsize(10) elements. 00174 * 00175 * Use for hash table lookup, or anything where one collision in 2^^64 00176 * is acceptable. Do NOT use for cryptographic purposes. 00177 * 00178 * @param k The key (the unaligned variable-length array of bytes). 00179 * @param length The length of the key, counting by bytes. 00180 * @param intval Initial value, can be any 8-byte value. 00181 * 00182 * @return A 64-bit value. Every bit of the key affects every bit of 00183 * the return value. No funnels. Every 1-bit and 2-bit delta 00184 * achieves avalanche. About 41+5len instructions. 00185 */ 00186 static inline uint64_t c_jhash64(const uint8_t *k, uint64_t length, uint64_t intval) { 00187 uint64_t a,b,c,len; 00188 00189 /* Set up the internal state */ 00190 len = length; 00191 a = b = intval; /* the previous hash value */ 00192 c = 0x9e3779b97f4a7c13LL; /* the golden ratio; an arbitrary value */ 00193 00194 /* handle most of the key */ 00195 while (len >= 24) 00196 { 00197 a += (k[0] +((uint64_t)k[ 1]<< 8)+((uint64_t)k[ 2]<<16)+((uint64_t)k[ 3]<<24) 00198 +((uint64_t)k[4 ]<<32)+((uint64_t)k[ 5]<<40)+((uint64_t)k[ 6]<<48)+((uint64_t)k[ 7]<<56)); 00199 b += (k[8] +((uint64_t)k[ 9]<< 8)+((uint64_t)k[10]<<16)+((uint64_t)k[11]<<24) 00200 +((uint64_t)k[12]<<32)+((uint64_t)k[13]<<40)+((uint64_t)k[14]<<48)+((uint64_t)k[15]<<56)); 00201 c += (k[16] +((uint64_t)k[17]<< 8)+((uint64_t)k[18]<<16)+((uint64_t)k[19]<<24) 00202 +((uint64_t)k[20]<<32)+((uint64_t)k[21]<<40)+((uint64_t)k[22]<<48)+((uint64_t)k[23]<<56)); 00203 _c_mix64(a,b,c); 00204 k += 24; len -= 24; 00205 } 00206 00207 /* handle the last 23 bytes */ 00208 c += length; 00209 switch(len) { 00210 case 23: c+=((uint64_t)k[22]<<56); 00211 case 22: c+=((uint64_t)k[21]<<48); 00212 case 21: c+=((uint64_t)k[20]<<40); 00213 case 20: c+=((uint64_t)k[19]<<32); 00214 case 19: c+=((uint64_t)k[18]<<24); 00215 case 18: c+=((uint64_t)k[17]<<16); 00216 case 17: c+=((uint64_t)k[16]<<8); 00217 /* the first byte of c is reserved for the length */ 00218 case 16: b+=((uint64_t)k[15]<<56); 00219 case 15: b+=((uint64_t)k[14]<<48); 00220 case 14: b+=((uint64_t)k[13]<<40); 00221 case 13: b+=((uint64_t)k[12]<<32); 00222 case 12: b+=((uint64_t)k[11]<<24); 00223 case 11: b+=((uint64_t)k[10]<<16); 00224 case 10: b+=((uint64_t)k[ 9]<<8); 00225 case 9: b+=((uint64_t)k[ 8]); 00226 case 8: a+=((uint64_t)k[ 7]<<56); 00227 case 7: a+=((uint64_t)k[ 6]<<48); 00228 case 6: a+=((uint64_t)k[ 5]<<40); 00229 case 5: a+=((uint64_t)k[ 4]<<32); 00230 case 4: a+=((uint64_t)k[ 3]<<24); 00231 case 3: a+=((uint64_t)k[ 2]<<16); 00232 case 2: a+=((uint64_t)k[ 1]<<8); 00233 case 1: a+=((uint64_t)k[ 0]); 00234 /* case 0: nothing left to add */ 00235 } 00236 _c_mix64(a,b,c); 00237 00238 return c; 00239 } 00240 00241 /** 00242 * }@ 00243 */ 00244 #endif /* _C_JHASH_H */ 00245