git.m6w6.name Git - m6w6/libmemcached/blob - libmemcached/hsieh_hash.c

   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 "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 uint32_t hsieh_hash(char *key, size_t key_length)
  21 {
  22   uint32_t hash = 0, tmp;
  23   int rem;
  24
  25   if (key_length <= 0 || key == NULL) return 0;
  26
  27   rem = key_length & 3;
  28   key_length >>= 2;
  29
  30   /* Main loop */
  31   for (;key_length > 0; key_length--) {
  32     hash  += get16bits (key);
  33     tmp    = (get16bits (key+2) << 11) ^ hash;
  34     hash   = (hash << 16) ^ tmp;
  35     key  += 2*sizeof (uint16_t);
  36     hash  += hash >> 11;
  37   }
  38
  39   /* Handle end cases */
  40   switch (rem) {
  41   case 3: hash += get16bits (key);
  42           hash ^= hash << 16;
  43           hash ^= key[sizeof (uint16_t)] << 18;
  44           hash += hash >> 11;
  45           break;
  46   case 2: hash += get16bits (key);
  47           hash ^= hash << 11;
  48           hash += hash >> 17;
  49           break;
  50   case 1: hash += *key;
  51           hash ^= hash << 10;
  52           hash += hash >> 1;
  53   }
  54
  55   /* Force "avalanching" of final 127 bits */
  56   hash ^= hash << 3;
  57   hash += hash >> 5;
  58   hash ^= hash << 4;
  59   hash += hash >> 17;
  60   hash ^= hash << 25;
  61   hash += hash >> 6;
  62
  63   return hash;
  64 }
  65