git.m6w6.name Git - awesomized/libmemcached/blob - libhashkit/hsieh.cc

   1 /* By Paul Hsieh (C) 2004, 2005.  Covered under the Paul Hsieh
   2  * derivative license.
   3  * See: http://www.azillionmonkeys.com/qed/weblicense.html for license
   4  * details.
   5  * http://www.azillionmonkeys.com/qed/hash.html
   6 */
   7
   8 #include <libhashkit/common.h>
   9
  10 #undef get16bits
  11 #if (defined(__GNUC__) && defined(__i386__))
  12 #define get16bits(d) (*((const uint16_t *) (d)))
  13 #endif
  14
  15 #if !defined (get16bits)
  16 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
  17                       +(uint32_t)(((const uint8_t *)(d))[0]) )
  18 #endif
  19
  20 #ifdef HAVE_HSIEH_HASH
  21 uint32_t hashkit_hsieh(const char *key, size_t key_length, void *)
  22 {
  23   uint32_t hash = 0, tmp;
  24   int rem;
  25
  26   if (key_length <= 0 || key == NULL)
  27     return 0;
  28
  29   rem = key_length & 3;
  30   key_length >>= 2;
  31
  32   /* Main loop */
  33   for (;key_length > 0; key_length--)
  34   {
  35     hash  += get16bits (key);
  36     tmp    = (get16bits (key+2) << 11) ^ hash;
  37     hash   = (hash << 16) ^ tmp;
  38     key  += 2*sizeof (uint16_t);
  39     hash  += hash >> 11;
  40   }
  41
  42   /* Handle end cases */
  43   switch (rem)
  44   {
  45   case 3: hash += get16bits (key);
  46           hash ^= hash << 16;
  47           hash ^= (uint32_t)key[sizeof (uint16_t)] << 18;
  48           hash += hash >> 11;
  49           break;
  50   case 2: hash += get16bits (key);
  51           hash ^= hash << 11;
  52           hash += hash >> 17;
  53           break;
  54   case 1: hash += (unsigned char)(*key);
  55           hash ^= hash << 10;
  56           hash += hash >> 1;
  57   default:
  58           break;
  59   }
  60
  61   /* Force "avalanching" of final 127 bits */
  62   hash ^= hash << 3;
  63   hash += hash >> 5;
  64   hash ^= hash << 4;
  65   hash += hash >> 17;
  66   hash ^= hash << 25;
  67   hash += hash >> 6;
  68
  69   return hash;
  70 }
  71 #else
  72 uint32_t hashkit_hsieh(const char *, size_t , void *)
  73 {
  74   return 0;
  75 }
  76 #endif