net/disk_cache/hash.cc

   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