1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 * Copyright (C) 2018 Blender Foundation.
16 */
17
18 /** \file
19 * \ingroup bli
20 *
21 * Functions to compute Murmur3 hash key.
22 *
23 * This Code is based on alShaders/Cryptomatte/MurmurHash3.h:
24 *
25 * MurmurHash3 was written by Austin Appleby, and is placed in the public
26 * domain. The author hereby disclaims copyright to this source code.
27 */
28
29 #include "BLI_compiler_attrs.h"
30 #include "BLI_compiler_compat.h"
31 #include "BLI_hash_mm3.h" /* own include */
32
33 #if defined(_MSC_VER)
34 # include <stdlib.h>
35 # define ROTL32(x, y) _rotl(x, y)
36 # define BIG_CONSTANT(x) (x)
37
38 /* Other compilers */
39 #else /* defined(_MSC_VER) */
rotl32(uint32_t x,int8_t r)40 static inline uint32_t rotl32(uint32_t x, int8_t r)
41 {
42 return (x << r) | (x >> (32 - r));
43 }
44 # define ROTL32(x, y) rotl32(x, y)
45 # define BIG_CONSTANT(x) (x##LLU)
46 #endif /* !defined(_MSC_VER) */
47
48 /* Block read - if your platform needs to do endian-swapping or can only
49 * handle aligned reads, do the conversion here
50 */
51
getblock32(const uint32_t * p,int i)52 BLI_INLINE uint32_t getblock32(const uint32_t *p, int i)
53 {
54 return p[i];
55 }
56
getblock64(const uint64_t * p,int i)57 BLI_INLINE uint64_t getblock64(const uint64_t *p, int i)
58 {
59 return p[i];
60 }
61
62 /* Finalization mix - force all bits of a hash block to avalanche */
63
fmix32(uint32_t h)64 BLI_INLINE uint32_t fmix32(uint32_t h)
65 {
66 h ^= h >> 16;
67 h *= 0x85ebca6b;
68 h ^= h >> 13;
69 h *= 0xc2b2ae35;
70 h ^= h >> 16;
71
72 return h;
73 }
74
fmix64(uint64_t k)75 BLI_INLINE uint64_t fmix64(uint64_t k)
76 {
77 k ^= k >> 33;
78 k *= BIG_CONSTANT(0xff51afd7ed558ccd);
79 k ^= k >> 33;
80 k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
81 k ^= k >> 33;
82
83 return k;
84 }
85
BLI_hash_mm3(const unsigned char * data,size_t len,uint32_t seed)86 uint32_t BLI_hash_mm3(const unsigned char *data, size_t len, uint32_t seed)
87 {
88 const uint8_t *in_data = (const uint8_t *)data;
89 const int nblocks = len / 4;
90
91 uint32_t h1 = seed;
92
93 const uint32_t c1 = 0xcc9e2d51;
94 const uint32_t c2 = 0x1b873593;
95
96 /* body */
97
98 const uint32_t *blocks = (const uint32_t *)(in_data + nblocks * 4);
99
100 for (int i = -nblocks; i; i++) {
101 uint32_t k1 = getblock32(blocks, i);
102
103 k1 *= c1;
104 k1 = ROTL32(k1, 15);
105 k1 *= c2;
106
107 h1 ^= k1;
108 h1 = ROTL32(h1, 13);
109 h1 = h1 * 5 + 0xe6546b64;
110 }
111
112 /* tail */
113
114 const uint8_t *tail = (const uint8_t *)(in_data + nblocks * 4);
115
116 uint32_t k1 = 0;
117
118 switch (len & 3) {
119 case 3:
120 k1 ^= tail[2] << 16;
121 ATTR_FALLTHROUGH;
122 case 2:
123 k1 ^= tail[1] << 8;
124 ATTR_FALLTHROUGH;
125 case 1:
126 k1 ^= tail[0];
127 k1 *= c1;
128 k1 = ROTL32(k1, 15);
129 k1 *= c2;
130 h1 ^= k1;
131 }
132
133 /* finalization */
134
135 h1 ^= len;
136
137 h1 = fmix32(h1);
138
139 return h1;
140 }
141