doc: s/bogomips.org/yhbt.net/
[ruby-tdb.git] / ext / tdb / murmur1.c
blob1880cc62dea0294f5b24bc0ce80a8acdf85b5ac6
1 #include "rbtdb.h"
2 #include <assert.h>
4 /*
5 * https://sites.google.com/site/murmurhash/
7 * Public Domain hash functions by Austin Appleby.
9 * Trivially adapted for use with Ruby TDB by Eric Wong.
13 * 'm' and 'r' are mixing constants generated offline.
14 * They're not really 'magic', they just happen to work well.
16 static const unsigned int m = 0xc6a4a793;
17 static const int r = 16;
18 static const unsigned int seed;
20 unsigned int rbtdb_murmur1(TDB_DATA * key)
22 const unsigned char *data = key->dptr;
23 int len = (int)key->dsize;
24 /* Initialize the hash to a 'random' value */
25 unsigned int h = seed ^ (len * m);
27 while (len >= 4) {
28 h += *(const unsigned int *)data;
29 h *= m;
30 h ^= h >> r;
32 data += 4;
33 len -= 4;
36 /* Handle the last few bytes of the input array */
37 switch (len) {
38 case 3:
39 h += data[2] << 16;
40 case 2:
41 h += data[1] << 8;
42 case 1:
43 h += data[0];
44 h *= m;
45 h ^= h >> r;
49 * Do a few final mixes of the hash to ensure the last few
50 * bytes are well-incorporated.
52 h *= m;
53 h ^= h >> 10;
54 h *= m;
55 h ^= h >> 17;
57 return h;
60 /* adapted from MurmurHashAligned */
61 unsigned int rbtdb_murmur1_aligned(TDB_DATA * key)
63 const unsigned char *data = key->dptr;
64 int len = (int)key->dsize;
65 unsigned int h = seed ^ (len * m);
66 union { const unsigned char *byte; int integer; } cast = { data };
67 int align = cast.integer & 3;
69 if (align & (len >= 4)) {
70 /* Pre-load the temp registers */
71 unsigned int t = 0, d = 0;
72 int sl, sr, pack;
74 switch (align) {
75 case 1: t |= data[2] << 16;
76 case 2: t |= data[1] << 8;
77 case 3: t |= data[0];
80 t <<= (8 * align);
82 data += 4 - align;
83 len -= 4 - align;
85 sl = 8 * (4 - align);
86 sr = 8 * align;
88 /* Mix */
89 while (len >= 4) {
90 assert((cast.integer & 3) == 0);
92 d = *(const unsigned int *)data;
93 t = (t >> sr) | (d << sl);
94 h += t;
95 h *= m;
96 h ^= h >> r;
97 t = d;
99 data += 4;
100 len -= 4;
103 /* Handle leftover data in temp registers */
104 pack = len < align ? len : align;
105 d = 0;
107 switch (pack) {
108 case 3:
109 d |= data[2] << 16;
110 case 2:
111 d |= data[1] << 8;
112 case 1:
113 d |= data[0];
114 case 0:
115 h += (t >> sr) | (d << sl);
116 h *= m;
117 h ^= h >> r;
120 data += pack;
121 len -= pack;
122 } else {
123 while (len >= 4) {
124 h += *(const unsigned int *)data;
125 h *= m;
126 h ^= h >> r;
128 data += 4;
129 len -= 4;
133 /* Handle tail bytes */
134 switch (len) {
135 case 3:
136 h += data[2] << 16;
137 case 2:
138 h += data[1] << 8;
139 case 1:
140 h += data[0];
141 h *= m;
142 h ^= h >> r;
145 h *= m;
146 h ^= h >> 10;
147 h *= m;
148 h ^= h >> 17;
150 return h;