libs/lmo/src/lmo_hash.c

   1 /*
   2  * Hash function from http://www.azillionmonkeys.com/qed/hash.html
   3  * Copyright (C) 2004-2008 by Paul Hsieh
   4  */
   5
   6 #include "lmo.h"
   7
   8 uint32_t sfh_hash(const char * data, int len)
   9 {
  10         uint32_t hash = len, tmp;
  11         int rem;
  12
  13         if (len <= 0 || data == NULL) return 0;
  14
  15         rem = len & 3;
  16         len >>= 2;
  17
  18         /* Main loop */
  19         for (;len > 0; len--) {
  20                 hash  += sfh_get16(data);
  21                 tmp    = (sfh_get16(data+2) << 11) ^ hash;
  22                 hash   = (hash << 16) ^ tmp;
  23                 data  += 2*sizeof(uint16_t);
  24                 hash  += hash >> 11;
  25         }
  26
  27         /* Handle end cases */
  28         switch (rem) {
  29                 case 3: hash += sfh_get16(data);
  30                         hash ^= hash << 16;
  31                         hash ^= data[sizeof(uint16_t)] << 18;
  32                         hash += hash >> 11;
  33                         break;
  34                 case 2: hash += sfh_get16(data);
  35                         hash ^= hash << 11;
  36                         hash += hash >> 17;
  37                         break;
  38                 case 1: hash += *data;
  39                         hash ^= hash << 10;
  40                         hash += hash >> 1;
  41         }
  42
  43         /* Force "avalanching" of final 127 bits */
  44         hash ^= hash << 3;
  45         hash += hash >> 5;
  46         hash ^= hash << 4;
  47         hash += hash >> 17;
  48         hash ^= hash << 25;
  49         hash += hash >> 6;
  50
  51         return hash;
  52 }
  53