1 // From http://www.azillionmonkeys.com/qed/hash.html 2 3 #include "net/disk_cache/hash.h" 4 5 typedef uint32 uint32_t; 6 typedef uint16 uint16_t; 7 8 namespace disk_cache { 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 21 uint32 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: hash += get16bits(data); 43 hash ^= hash << 16; 44 hash ^= data[sizeof(uint16_t)] << 18; 45 hash += hash >> 11; 46 break; 47 case 2: hash += get16bits(data); 48 hash ^= hash << 11; 49 hash += hash >> 17; 50 break; 51 case 1: hash += *data; 52 hash ^= hash << 10; 53 hash += hash >> 1; 54 } 55 56 /* Force "avalanching" of final 127 bits */ 57 hash ^= hash << 3; 58 hash += hash >> 5; 59 hash ^= hash << 4; 60 hash += hash >> 17; 61 hash ^= hash << 25; 62 hash += hash >> 6; 63 64 return hash; 65 } 66 67 } // namespace disk_cache 68
