1/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2
3#include <sys/types.h>
4#include <stdbool.h>
5#include <stdint.h>
6
7/*
8  "Murmur" hash provided by Austin, tanjent@gmail.com
9  http://murmurhash.googlepages.com/
10
11  Note - This code makes a few assumptions about how your machine behaves -
12
13  1. We can read a 4-byte value from any address without crashing
14  2. sizeof(int) == 4
15
16  And it has a few limitations -
17  1. It will not work incrementally.
18  2. It will not produce the same results on little-endian and big-endian
19  machines.
20
21  Updated to murmur2 hash - BP
22*/
23
24uint32_t murmur_hash(const char *key, size_t length);
25
26uint32_t murmur_hash(const char *key, size_t length)
27{
28  /*
29    'm' and 'r' are mixing constants generated offline.  They're not
30    really 'magic', they just happen to work well.
31  */
32
33  const unsigned int m= 0x5bd1e995;
34  const unsigned int seed= (0xdeadbeef * length);
35  const int r= 24;
36
37
38  /* Initialize the hash to a 'random' value */
39
40  unsigned int h= seed ^ length;
41
42  /* Mix 4 bytes at a time into the hash */
43
44  const unsigned char * data= (const unsigned char *)key;
45
46  while(length >= 4)
47  {
48    unsigned int k = *(unsigned int *)data;
49
50    k *= m;
51    k ^= k >> r;
52    k *= m;
53
54    h *= m;
55    h ^= k;
56
57    data += 4;
58    length -= 4;
59  }
60
61  /* Handle the last few bytes of the input array */
62
63  switch(length)
64  {
65  case 3: h ^= data[2] << 16;
66  case 2: h ^= data[1] << 8;
67  case 1: h ^= data[0];
68          h *= m;
69  };
70
71  /*
72    Do a few final mixes of the hash to ensure the last few bytes are
73    well-incorporated.
74  */
75
76  h ^= h >> 13;
77  h *= m;
78  h ^= h >> 15;
79
80  return h;
81}
82