source/src/ring_hashlib.c

   1 /* Source : https://en.wikipedia.org/wiki/MurmurHash */
   2 /* Source : http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */
   3
   4 #include <stdlib.h>
   5
   6 unsigned ring_hash(unsigned pid)
   7 {
   8     return pid / 1000 % 100;
   9 }
  10
  11 unsigned ring_add_hash(unsigned char *key, int len)
  12 {
  13     unsigned char *p = key;
  14     unsigned h = 0;
  15     int i;
  16
  17     for (i = 0; i < len; i++)
  18     {
  19         h += p[i];
  20     }
  21
  22     return h;
  23 }
  24
  25 unsigned ring_xor_hash(unsigned char *key, int len)
  26 {
  27     unsigned char *p = key;
  28     unsigned h = 0;
  29     int i;
  30
  31     for (i = 0; i < len; i++)
  32     {
  33         h ^= p[i];
  34     }
  35
  36     return h;
  37 }
  38
  39 unsigned ring_rot_hash(unsigned char *key, int len)
  40 {
  41     unsigned char *p = key;
  42     unsigned h = 0;
  43     int i;
  44
  45     for (i = 0; i < len; i++)
  46     {
  47         h = (h << 4) ^ (h >> 28) ^ p[i];
  48     }
  49
  50     return h;
  51 }
  52
  53 unsigned ring_djb_hash(unsigned char *key, int len)
  54 {
  55     unsigned char *p = key;
  56     unsigned h = 0;
  57     int i;
  58
  59     for (i = 0; i < len; i++)
  60     {
  61         h = 33 * h ^ p[i];
  62     }
  63
  64     return h;
  65 }
  66
  67 unsigned ring_sax_hash(unsigned char *key, int len)
  68 {
  69     unsigned char *p = key;
  70     unsigned h = 0;
  71     int i;
  72
  73     for (i = 0; i < len; i++)
  74     {
  75         h ^= (h << 5) + (h >> 2) + p[i];
  76     }
  77
  78     return h;
  79 }
  80
  81 unsigned ring_oat_hash(unsigned char *key, int len)
  82 {
  83     unsigned char *p = key;
  84     unsigned h = 0;
  85     int i;
  86
  87     for (i = 0; i < len; i++)
  88     {
  89         h += p[i];
  90         h += (h << 10);
  91         h ^= (h >> 6);
  92     }
  93
  94     h += (h << 3);
  95     h ^= (h >> 11);
  96     h += (h << 15);
  97     return h;
  98 }
  99
 100 unsigned ring_elf_hash(unsigned char *key, int len)
 101 {
 102     unsigned char *p = key;
 103     unsigned h = 0, g;
 104     int i;
 105
 106     for (i = 0; i < len; i++)
 107     {
 108         h = (h << 4) + p[i];
 109         g = h & 0xf0000000L;
 110
 111         if (g != 0)
 112         {
 113             h ^= g >> 24;
 114         }
 115
 116         h &= ~g;
 117     }
 118
 119     return h;
 120 }
 121
 122 #define hashsize(n) (1U << (n))
 123 #define hashmask(n) (hashsize(n) - 1)
 124
 125 #define mix(a,b,c) \
 126 { \
 127     a -= b; a -= c; a ^= (c >> 13); \
 128     b -= c; b -= a; b ^= (a << 8); \
 129     c -= a; c -= b; c ^= (b >> 13); \
 130     a -= b; a -= c; a ^= (c >> 12); \
 131     b -= c; b -= a; b ^= (a << 16); \
 132     c -= a; c -= b; c ^= (b >> 5); \
 133     a -= b; a -= c; a ^= (c >> 3); \
 134     b -= c; b -= a; b ^= (a << 10); \
 135     c -= a; c -= b; c ^= (b >> 15); \
 136 }
 137
 138 unsigned ring_jen_hash(unsigned char *k, unsigned length, unsigned initval)
 139 {
 140     unsigned a, b;
 141     unsigned c = initval;
 142     unsigned len = length;
 143
 144     a = b = 0x9e3779b9;
 145
 146     while (len >= 12)
 147     {
 148         a += (k[0] + ((unsigned)k[1] << 8) + ((unsigned)k[2] << 16) + ((unsigned)k[3] << 24));
 149         b += (k[4] + ((unsigned)k[5] << 8) + ((unsigned)k[6] << 16) + ((unsigned)k[7] << 24));
 150         c += (k[8] + ((unsigned)k[9] << 8) + ((unsigned)k[10] << 16) + ((unsigned)k[11] << 24));
 151
 152         mix(a, b, c);
 153
 154         k += 12;
 155         len -= 12;
 156     }
 157
 158     c += length;
 159
 160     switch (len)
 161     {
 162     case 11: c += ((unsigned)k[10] << 24);
 163     case 10: c += ((unsigned)k[9] << 16);
 164     case 9: c += ((unsigned)k[8] << 8);
 165         /* First byte of c reserved for length */
 166     case 8: b += ((unsigned)k[7] << 24);
 167     case 7: b += ((unsigned)k[6] << 16);
 168     case 6: b += ((unsigned)k[5] << 8);
 169     case 5: b += k[4];
 170     case 4: a += ((unsigned)k[3] << 24);
 171     case 3: a += ((unsigned)k[2] << 16);
 172     case 2: a += ((unsigned)k[1] << 8);
 173     case 1: a += k[0];
 174     }
 175
 176     mix(a, b, c);
 177
 178     return c;
 179 }
 180
 181 unsigned int ring_murmur3_32(const char *key, unsigned int len, unsigned int seed) {
 182         static const unsigned int c1 = 0xcc9e2d51;
 183         static const unsigned int c2 = 0x1b873593;
 184         static const unsigned int r1 = 15;
 185         static const unsigned int r2 = 13;
 186         static const unsigned int m = 5;
 187         static const unsigned int n = 0xe6546b64;
 188
 189         unsigned int hash = seed;
 190
 191         const int nblocks = len / 4;
 192         const unsigned int *blocks = (const unsigned int *) key;
 193         int i;
 194
 195         const unsigned char *tail ;
 196         unsigned int k1 = 0;
 197
 198         for (i = 0; i < nblocks; i++) {
 199                 unsigned int k = blocks[i];
 200                 k *= c1;
 201                 k = (k << r1) | (k >> (32 - r1));
 202                 k *= c2;
 203
 204                 hash ^= k;
 205                 hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
 206         }
 207
 208         tail = (const unsigned char *) (key + nblocks * 4);
 209
 210         switch (len & 3) {
 211         case 3:
 212                 k1 ^= tail[2] << 16;
 213         case 2:
 214                 k1 ^= tail[1] << 8;
 215         case 1:
 216                 k1 ^= tail[0];
 217
 218                 k1 *= c1;
 219                 k1 = (k1 << r1) | (k1 >> (32 - r1));
 220                 k1 *= c2;
 221                 hash ^= k1;
 222         }
 223
 224         hash ^= len;
 225         hash ^= (hash >> 16);
 226         hash *= 0x85ebca6b;
 227         hash ^= (hash >> 13);
 228         hash *= 0xc2b2ae35;
 229         hash ^= (hash >> 16);
 230
 231         return hash;
 232 }