libcoap  4.3.0rc3
murmur3.c
Go to the documentation of this file.
1 
31 #include <assert.h>
32 #include <string.h>
33 
34 #include "murmur3.h"
35 
36 #ifndef min
37 #define min(a,b) (((a) < (b)) ? (a) : (b))
38 #endif /* min */
39 
40 static inline uint32_t
41 rol(uint32_t val, uint8_t bits) {
42  return (val << bits) + (val >> (32 - bits));
43 }
44 
45 void
47  memset(mctx, 0, sizeof(murmur3_context_t));
48 }
49 
50 const size_t murmur3_block_length = sizeof(uint32_t);
51 const uint32_t c1 = 0xcc9e2d51;
52 const uint32_t c2 = 0x1b873593;
53 const uint8_t r1 = 15;
54 const uint8_t r2 = 13;
55 const uint8_t m = 5;
56 const uint32_t n = 0xe6546b64;
57 
58 static void
60  mctx->key *= c1;
61  mctx->key = rol(mctx->key, r1);
62  mctx->key *= c2;
63 
64  mctx->hashval ^= mctx->key;
65  mctx->hashval = rol(mctx->hashval, r2);
66  mctx->hashval = (mctx->hashval * m) + n;
67 
69  mctx->len = 0;
70  mctx->key = 0;
71 }
72 
73 static size_t
74 murmur3_32_fillblock(murmur3_context_t *mctx, const void *data, size_t len) {
75  const uint8_t *key = (const uint8_t *)data;
76  size_t removed = 0;
77 
78  assert(mctx->len < murmur3_block_length);
79  if (len) {
80  size_t l = min(len, (size_t)(murmur3_block_length - mctx->len));
81  removed = l;
82  /* little endian */
83  while (l--) {
84  mctx->key <<= 8;
85  mctx->key += key[l];
86  }
87  mctx->len += removed;
88 
89  if (mctx->len == murmur3_block_length) {
90  murmur3_32_eatblock(mctx);
91  }
92  }
93 
94  return removed;
95 }
96 
97 void
98 murmur3_32_update(murmur3_context_t *mctx, const void *data, size_t len) {
99  const uint8_t *key = (const uint8_t *)data;
100 
101  /* first, feed all remaining data from mctx to murmur3 */
102  size_t removed = murmur3_32_fillblock(mctx, data, len);
103  if (removed) {
104  len -= removed;
105  key += removed;
106  }
107 
108  while (len > (murmur3_block_length - 1)) {
109  assert(mctx->len == 0);
110  /* little endian */
111  mctx->key = (key[3] << 24) + (key[2] << 16) + (key[1] << 8) + key[0];
112  murmur3_32_eatblock(mctx);
113 
114  len -= murmur3_block_length;
115  key += murmur3_block_length;
116  }
117 
118  /* store key[0..len-1] for later use */
119  murmur3_32_fillblock(mctx, key, len);
120 }
121 
122 uint32_t
124 
125  if (mctx->len) {
126  mctx->key *= c1;
127  mctx->key = rol(mctx->key, r1);
128  mctx->key *= c2;
129 
130  mctx->hashval ^= mctx->key;
131  mctx->total_len += mctx->len;
132  }
133 
134  mctx->hashval ^= mctx->total_len;
135 
136  mctx->hashval ^= mctx->hashval >> 16;
137  mctx->hashval *= 0x85ebca6b;
138  mctx->hashval ^= mctx->hashval >> 13;
139  mctx->hashval *= 0xc2b2ae35;
140  mctx->hashval ^= mctx->hashval >> 16;
141  return mctx->hashval;
142 }
143 
144 uint32_t
145 murmur3_32(const void *data, size_t len) {
146  murmur3_context_t mctx;
147  murmur3_32_init(&mctx);
148  murmur3_32_update(&mctx, data, len);
149  return murmur3_32_finalize(&mctx);
150 }
static uint32_t rol(uint32_t val, uint8_t bits)
Definition: murmur3.c:41
static size_t murmur3_32_fillblock(murmur3_context_t *mctx, const void *data, size_t len)
Definition: murmur3.c:74
const size_t murmur3_block_length
Definition: murmur3.c:50
void murmur3_32_update(murmur3_context_t *mctx, const void *data, size_t len)
Updates the state of the murmur3 context object mctx with len bytes from data.
Definition: murmur3.c:98
const uint8_t r2
Definition: murmur3.c:54
static void murmur3_32_eatblock(murmur3_context_t *mctx)
Definition: murmur3.c:59
const uint8_t m
Definition: murmur3.c:55
const uint32_t c1
Definition: murmur3.c:51
const uint32_t c2
Definition: murmur3.c:52
const uint32_t n
Definition: murmur3.c:56
uint32_t murmur3_32_finalize(murmur3_context_t *mctx)
Finalizes the given murmur3 context mctx and calculates the resulting murmur3 hash value.
Definition: murmur3.c:123
const uint8_t r1
Definition: murmur3.c:53
#define min(a, b)
Naïve implementation of Murmur3 for 32 bit with update functionality.
Definition: murmur3.c:37
uint32_t murmur3_32(const void *data, size_t len)
Calculcates the murmur3 hash value of data.
Definition: murmur3.c:145
void murmur3_32_init(murmur3_context_t *mctx)
Initializes the provided murmur3 context object mctx.
Definition: murmur3.c:46
Naïve implementation of Murmur3 for 32 bit with update functionality.
Definition: murmur3.h:36
uint8_t len
Definition: murmur3.h:40
size_t total_len
Definition: murmur3.h:37
uint32_t hashval
Definition: murmur3.h:39
uint32_t key
Definition: murmur3.h:38