Home | History | Annotate | Download | only in src 
      1 //-----------------------------------------------------------------------------
      2 // MurmurHash was written by Austin Appleby, and is placed in the public
      3 // domain. The author hereby disclaims copyright to this source code.
      4 
      5 // Note - This code makes a few assumptions about how your machine behaves -
      6 
      7 // 1. We can read a 4-byte value from any address without crashing
      8 // 2. sizeof(int) == 4
      9 
     10 // And it has a few limitations -
     11 
     12 // 1. It will not work incrementally.
     13 // 2. It will not produce the same results on little-endian and big-endian
     14 //    machines.
     15 
     16 #include "MurmurHash1.h"
     17 
     18 //-----------------------------------------------------------------------------
     19 
     20 uint32_t MurmurHash1 ( const void * key, int len, uint32_t seed )
     21 {
     22   const unsigned int m = 0xc6a4a793;
     23 
     24   const int r = 16;
     25 
     26   unsigned int h = seed ^ (len * m);
     27 
     28   //----------
     29 
     30   const unsigned char * data = (const unsigned char *)key;
     31 
     32   while(len >= 4)
     33   {
     34     unsigned int k = *(unsigned int *)data;
     35 
     36     h += k;
     37     h *= m;
     38     h ^= h >> 16;
     39 
     40     data += 4;
     41     len -= 4;
     42   }
     43 
     44   //----------
     45 
     46   switch(len)
     47   {
     48   case 3:
     49     h += data[2] << 16;
     50   case 2:
     51     h += data[1] << 8;
     52   case 1:
     53     h += data[0];
     54     h *= m;
     55     h ^= h >> r;
     56   };
     57 
     58   //----------
     59 
     60   h *= m;
     61   h ^= h >> 10;
     62   h *= m;
     63   h ^= h >> 17;
     64 
     65   return h;
     66 }
     67 
     68 //-----------------------------------------------------------------------------
     69 // MurmurHash1Aligned, by Austin Appleby
     70 
     71 // Same algorithm as MurmurHash1, but only does aligned reads - should be safer
     72 // on certain platforms.
     73 
     74 // Performance should be equal to or better than the simple version.
     75 
     76 unsigned int MurmurHash1Aligned ( const void * key, int len, unsigned int seed )
     77 {
     78   const unsigned int m = 0xc6a4a793;
     79   const int r = 16;
     80 
     81   const unsigned char * data = (const unsigned char *)key;
     82 
     83   unsigned int h = seed ^ (len * m);
     84 
     85   int align = (uint64_t)data & 3;
     86 
     87   if(align && (len >= 4))
     88   {
     89     // Pre-load the temp registers
     90 
     91     unsigned int t = 0, d = 0;
     92 
     93     switch(align)
     94     {
     95       case 1: t |= data[2] << 16;
     96       case 2: t |= data[1] << 8;
     97       case 3: t |= data[0];
     98     }
     99 
    100     t <<= (8 * align);
    101 
    102     data += 4-align;
    103     len -= 4-align;
    104 
    105     int sl = 8 * (4-align);
    106     int sr = 8 * align;
    107 
    108     // Mix
    109 
    110     while(len >= 4)
    111     {
    112       d = *(unsigned int *)data;
    113       t = (t >> sr) | (d << sl);
    114       h += t;
    115       h *= m;
    116       h ^= h >> r;
    117       t = d;
    118 
    119       data += 4;
    120       len -= 4;
    121     }
    122 
    123     // Handle leftover data in temp registers
    124 
    125     int pack = len < align ? len : align;
    126 
    127     d = 0;
    128 
    129     switch(pack)
    130     {
    131     case 3: d |= data[2] << 16;
    132     case 2: d |= data[1] << 8;
    133     case 1: d |= data[0];
    134     case 0: h += (t >> sr) | (d << sl);
    135         h *= m;
    136         h ^= h >> r;
    137     }
    138 
    139     data += pack;
    140     len -= pack;
    141   }
    142   else
    143   {
    144     while(len >= 4)
    145     {
    146       h += *(unsigned int *)data;
    147       h *= m;
    148       h ^= h >> r;
    149 
    150       data += 4;
    151       len -= 4;
    152     }
    153   }
    154 
    155   //----------
    156   // Handle tail bytes
    157 
    158   switch(len)
    159   {
    160   case 3: h += data[2] << 16;
    161   case 2: h += data[1] << 8;
    162   case 1: h += data[0];
    163       h *= m;
    164       h ^= h >> r;
    165   };
    166 
    167   h *= m;
    168   h ^= h >> 10;
    169   h *= m;
    170   h ^= h >> 17;
    171 
    172   return h;
    173 }
    174 
    175