about summary refs log tree commit homepage
path: root/ext/tdb/murmur3.c
blob: cdc7f73c9c8fa6c8a9dee1603e6b7ace845234b5 (plain)
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
#include "rbtdb.h"
/*
 * https://sites.google.com/site/murmurhash/
 *
 * MurmurHash3 was written by Austin Appleby, and is placed in the public
 * domain. The author hereby disclaims copyright to this source code.
 *
 * Eric Wong trivially ported this to C for Ruby tdb (32-bit version only)
 */

#include <stdint.h>
#define	FORCE_INLINE __attribute__((always_inline))

static inline uint32_t rotl32(uint32_t x, int8_t r)
{
	return (x << r) | (x >> (32 - r));
}

#define	ROTL32(x,y)	rotl32(x,y)

#define BIG_CONSTANT(x) (x##LLU)

/* ----------------------------------------------------------------------------
 * Block read - if your platform needs to do endian-swapping or can only
 * handle aligned reads, do the conversion here
 */

static FORCE_INLINE uint32_t getblock(const uint32_t * p, int i)
{
	return p[i];
}

/* ----------------------------------------------------------------------------
 * Finalization mix - force all bits of a hash block to avalanche
 */

static FORCE_INLINE uint32_t fmix(uint32_t h)
{
	h ^= h >> 16;
	h *= 0x85ebca6b;
	h ^= h >> 13;
	h *= 0xc2b2ae35;
	h ^= h >> 16;

	return h;
}

unsigned int rbtdb_murmur3a(TDB_DATA * key)
{
	const uint8_t *data = key->dptr;
	int len = (int)key->dsize;
	const int nblocks = len / 4;
	static const uint32_t seed;
	uint32_t h1 = seed;
	int i;

	static const uint32_t c1 = 0xcc9e2d51;
	static const uint32_t c2 = 0x1b873593;

	/* body */
	const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);

	for (i = -nblocks; i; i++) {
		uint32_t k1 = getblock(blocks, i);

		k1 *= c1;
		k1 = ROTL32(k1, 15);
		k1 *= c2;

		h1 ^= k1;
		h1 = ROTL32(h1, 13);
		h1 = h1 * 5 + 0xe6546b64;
	}

	/* tail */
	{
		const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
		uint32_t k1 = 0;

		switch (len & 3) {
		case 3:
			k1 ^= tail[2] << 16;
		case 2:
			k1 ^= tail[1] << 8;
		case 1:
			k1 ^= tail[0];
			k1 *= c1;
			k1 = ROTL32(k1, 15);
			k1 *= c2;
			h1 ^= k1;
		};
	}

	/* finalization */

	h1 ^= len;

	return fmix(h1);
}