ruby-tdb.git  about / heads / tags
Trivial Database bindings for Ruby
blob 1880cc62dea0294f5b24bc0ce80a8acdf85b5ac6 2583 bytes (raw)
$ git show HEAD:ext/tdb/murmur1.c	# shows this blob on the CLI

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
#include "rbtdb.h"
#include <assert.h>

/*
 * https://sites.google.com/site/murmurhash/
 *
 * Public Domain hash functions by Austin Appleby.
 *
 * Trivially adapted for use with Ruby TDB by Eric Wong.
 */

/*
 * 'm' and 'r' are mixing constants generated offline.
 * They're not really 'magic', they just happen to work well.
 */
static const unsigned int m = 0xc6a4a793;
static const int r = 16;
static const unsigned int seed;

unsigned int rbtdb_murmur1(TDB_DATA * key)
{
	const unsigned char *data = key->dptr;
	int len = (int)key->dsize;
	/* Initialize the hash to a 'random' value */
	unsigned int h = seed ^ (len * m);

	while (len >= 4) {
		h += *(const unsigned int *)data;
		h *= m;
		h ^= h >> r;

		data += 4;
		len -= 4;
	}

	/* Handle the last few bytes of the input array */
	switch (len) {
	case 3:
		h += data[2] << 16;
	case 2:
		h += data[1] << 8;
	case 1:
		h += data[0];
		h *= m;
		h ^= h >> r;
	};

	/*
	 * Do a few final mixes of the hash to ensure the last few
	 * bytes are well-incorporated.
	 */
	h *= m;
	h ^= h >> 10;
	h *= m;
	h ^= h >> 17;

	return h;
}

/* adapted from MurmurHashAligned */
unsigned int rbtdb_murmur1_aligned(TDB_DATA * key)
{
	const unsigned char *data = key->dptr;
	int len = (int)key->dsize;
	unsigned int h = seed ^ (len * m);
	union { const unsigned char *byte; int integer; } cast = { data };
	int align = cast.integer & 3;

	if (align & (len >= 4)) {
		/* Pre-load the temp registers */
		unsigned int t = 0, d = 0;
		int sl, sr, pack;

		switch (align) {
		case 1: t |= data[2] << 16;
		case 2: t |= data[1] << 8;
		case 3: t |= data[0];
		}

		t <<= (8 * align);

		data += 4 - align;
		len -= 4 - align;

		sl = 8 * (4 - align);
		sr = 8 * align;

		/* Mix */
		while (len >= 4) {
			assert((cast.integer & 3) == 0);

			d = *(const unsigned int *)data;
			t = (t >> sr) | (d << sl);
			h += t;
			h *= m;
			h ^= h >> r;
			t = d;

			data += 4;
			len -= 4;
		}

		/* Handle leftover data in temp registers */
		pack = len < align ? len : align;
		d = 0;

		switch (pack) {
		case 3:
			d |= data[2] << 16;
		case 2:
			d |= data[1] << 8;
		case 1:
			d |= data[0];
		case 0:
			h += (t >> sr) | (d << sl);
			h *= m;
			h ^= h >> r;
		}

		data += pack;
		len -= pack;
	} else {
		while (len >= 4) {
			h += *(const unsigned int *)data;
			h *= m;
			h ^= h >> r;

			data += 4;
			len -= 4;
		}
	}

	/* Handle tail bytes */
	switch (len) {
	case 3:
		h += data[2] << 16;
	case 2:
		h += data[1] << 8;
	case 1:
		h += data[0];
		h *= m;
		h ^= h >> r;
	};

	h *= m;
	h ^= h >> 10;
	h *= m;
	h ^= h >> 17;

	return h;
}

git clone https://yhbt.net/ruby-tdb.git