1 // From http://www.azillionmonkeys.com/qed/hash.html 2 3 #include "base/hash.h" 4 5 typedef uint32 uint32_t; 6 typedef uint16 uint16_t; 7 8 namespace base { 9 10 #undef get16bits 11 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 12 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 13 #define get16bits(d) (*((const uint16_t *) (d))) 14 #endif 15 16 #if !defined (get16bits) 17 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ 18 +(uint32_t)(((const uint8_t *)(d))[0]) ) 19 #endif 20 SuperFastHash(const char * data,int len)21uint32 SuperFastHash(const char * data, int len) { 22 uint32_t hash = len, tmp; 23 int rem; 24 25 if (len <= 0 || data == NULL) 26 return 0; 27 28 rem = len & 3; 29 len >>= 2; 30 31 /* Main loop */ 32 for (; len > 0; len--) { 33 hash += get16bits(data); 34 tmp = (get16bits(data + 2) << 11) ^ hash; 35 hash = (hash << 16) ^ tmp; 36 data += 2 * sizeof(uint16_t); 37 hash += hash >> 11; 38 } 39 40 /* Handle end cases */ 41 switch (rem) { 42 case 3: 43 hash += get16bits(data); 44 hash ^= hash << 16; 45 46 // Treat the final character as signed. This ensures all platforms behave 47 // consistently with the original x86 code. 48 hash ^= static_cast<signed char>(data[sizeof(uint16_t)]) << 18; 49 hash += hash >> 11; 50 break; 51 case 2: 52 hash += get16bits(data); 53 hash ^= hash << 11; 54 hash += hash >> 17; 55 break; 56 case 1: 57 hash += static_cast<signed char>(*data); 58 hash ^= hash << 10; 59 hash += hash >> 1; 60 } 61 62 /* Force "avalanching" of final 127 bits */ 63 hash ^= hash << 3; 64 hash += hash >> 5; 65 hash ^= hash << 4; 66 hash += hash >> 17; 67 hash ^= hash << 25; 68 hash += hash >> 6; 69 70 return hash; 71 } 72 73 } // namespace base 74