murmur3_32.c (2a382033b5c379d4d57f4030f6045bbd5527a1e9) murmur3_32.c (99e9de871aee402a1166cdecb957fe6c8c99da13)
1/*-
2 * Copyright (c) 2014 Dag-Erling Smørgrav
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright

--- 8 unchanged lines hidden (view full) ---

17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
1/*-
2 * Copyright (c) 2014 Dag-Erling Smørgrav
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright

--- 8 unchanged lines hidden (view full) ---

17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD$
25 */
26
27#include <sys/hash.h>
28#include <sys/endian.h>
29#include <sys/stdint.h>
30#include <sys/types.h>
31
32#define rol32(i32, n) ((i32) << (n) | (i32) >> (32 - (n)))
33
34/*
27 */
28
29#include <sys/hash.h>
30#include <sys/endian.h>
31#include <sys/stdint.h>
32#include <sys/types.h>
33
34#define rol32(i32, n) ((i32) << (n) | (i32) >> (32 - (n)))
35
36/*
35 * $FreeBSD$
36 * Simple implementation of the Murmur3-32 hash function optimized for
37 * aligned sequences of 32-bit words. If len is not a multiple of 4, it
38 * will be rounded down, droping trailer bytes.
37 * Simple implementation of the Murmur3-32 hash function.
38 *
39 * This implementation is slow but safe. It can be made significantly
40 * faster if the caller guarantees that the input is correctly aligned for
41 * 32-bit reads, and slightly faster yet if the caller guarantees that the
42 * length of the input is always a multiple of 4 bytes.
39 */
40uint32_t
43 */
44uint32_t
41murmur3_aligned_32(const void *data, size_t len, uint32_t seed)
45murmur3_32_hash(const void *data, size_t len, uint32_t seed)
42{
46{
43 const uint32_t *data32;
47 const uint8_t *bytes;
44 uint32_t hash, k;
45 size_t res;
46
48 uint32_t hash, k;
49 size_t res;
50
47 /* initialize */
48 len -= len % sizeof(*data32);
51 /* initialization */
52 bytes = data;
49 res = len;
53 res = len;
50 data32 = data;
51 hash = seed;
52
54 hash = seed;
55
53 /* iterate */
54 for (res = 0; res < len; res += sizeof(*data32), data32++) {
55 k = le32toh(*data32);
56 /* main loop */
57 while (res >= 4) {
58 /* replace with le32toh() if input is aligned */
59 k = le32dec(bytes);
60 bytes += 4;
61 res -= 4;
56 k *= 0xcc9e2d51;
57 k = rol32(k, 15);
58 k *= 0x1b873593;
59 hash ^= k;
60 hash = rol32(hash, 13);
61 hash *= 5;
62 hash += 0xe6546b64;
63 }
64
62 k *= 0xcc9e2d51;
63 k = rol32(k, 15);
64 k *= 0x1b873593;
65 hash ^= k;
66 hash = rol32(hash, 13);
67 hash *= 5;
68 hash += 0xe6546b64;
69 }
70
71 /* remainder */
72 /* remove if input length is a multiple of 4 */
73 if (res > 0) {
74 k = 0;
75 switch (res) {
76 case 3:
77 k |= bytes[2] << 16;
78 case 2:
79 k |= bytes[1] << 8;
80 case 1:
81 k |= bytes[0];
82 k *= 0xcc9e2d51;
83 k = rol32(k, 15);
84 k *= 0x1b873593;
85 hash ^= k;
86 break;
87 }
88 }
89
65 /* finalize */
66 hash ^= (uint32_t)len;
67 hash ^= hash >> 16;
68 hash *= 0x85ebca6b;
69 hash ^= hash >> 13;
70 hash *= 0xc2b2ae35;
71 hash ^= hash >> 16;
72 return (hash);
73}
74
90 /* finalize */
91 hash ^= (uint32_t)len;
92 hash ^= hash >> 16;
93 hash *= 0x85ebca6b;
94 hash ^= hash >> 13;
95 hash *= 0xc2b2ae35;
96 hash ^= hash >> 16;
97 return (hash);
98}
99
100/*
101 * Simplified version of the above optimized for aligned sequences of
102 * 32-bit words. The count argument is the number of words, not the
103 * length in bytes.
104 */
105uint32_t
106murmur3_32_hash32(const uint32_t *data, size_t count, uint32_t seed)
107{
108 uint32_t hash, k;
109 size_t res;
110
111 /* iterate */
112 for (res = count, hash = seed; res > 0; res--, data++) {
113 k = le32toh(*data);
114 k *= 0xcc9e2d51;
115 k = rol32(k, 15);
116 k *= 0x1b873593;
117 hash ^= k;
118 hash = rol32(hash, 13);
119 hash *= 5;
120 hash += 0xe6546b64;
121 }
122
123 /* finalize */
124 hash ^= (uint32_t)count;
125 hash ^= hash >> 16;
126 hash *= 0x85ebca6b;
127 hash ^= hash >> 13;
128 hash *= 0xc2b2ae35;
129 hash ^= hash >> 16;
130 return (hash);
131}
132