base/hash.cc

   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
  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:
  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