1const std = @import("std");
2const builtin = @import("builtin");
3const testing = std.testing;
4const native_endian = builtin.target.cpu.arch.endian();
5
6const default_seed: u32 = 0xc70f6907;
7
8pub const Murmur2_32 = struct {
9 const Self = @This();
10
11 pub fn hash(str: []const u8) u32 {
12 return @call(.always_inline, Self.hashWithSeed, .{ str, default_seed });
13 }
14
15 pub fn hashWithSeed(str: []const u8, seed: u32) u32 {
16 const m: u32 = 0x5bd1e995;
17 const len: u32 = @truncate(str.len);
18 var h1: u32 = seed ^ len;
19 for (@as([*]align(1) const u32, @ptrCast(str.ptr))[0..(len >> 2)]) |v| {
20 var k1: u32 = v;
21 if (native_endian == .big)
22 k1 = @byteSwap(k1);
23 k1 *%= m;
24 k1 ^= k1 >> 24;
25 k1 *%= m;
26 h1 *%= m;
27 h1 ^= k1;
28 }
29 const offset = len & 0xfffffffc;
30 const rest = len & 3;
31 if (rest >= 3) {
32 h1 ^= @as(u32, @intCast(str[offset + 2])) << 16;
33 }
34 if (rest >= 2) {
35 h1 ^= @as(u32, @intCast(str[offset + 1])) << 8;
36 }
37 if (rest >= 1) {
38 h1 ^= @as(u32, @intCast(str[offset + 0]));
39 h1 *%= m;
40 }
41 h1 ^= h1 >> 13;
42 h1 *%= m;
43 h1 ^= h1 >> 15;
44 return h1;
45 }
46
47 pub fn hashUint32(v: u32) u32 {
48 return @call(.always_inline, Self.hashUint32WithSeed, .{ v, default_seed });
49 }
50
51 pub fn hashUint32WithSeed(v: u32, seed: u32) u32 {
52 const m: u32 = 0x5bd1e995;
53 const len: u32 = 4;
54 var h1: u32 = seed ^ len;
55 var k1: u32 = undefined;
56 k1 = v *% m;
57 k1 ^= k1 >> 24;
58 k1 *%= m;
59 h1 *%= m;
60 h1 ^= k1;
61 h1 ^= h1 >> 13;
62 h1 *%= m;
63 h1 ^= h1 >> 15;
64 return h1;
65 }
66
67 pub fn hashUint64(v: u64) u32 {
68 return @call(.always_inline, Self.hashUint64WithSeed, .{ v, default_seed });
69 }
70
71 pub fn hashUint64WithSeed(v: u64, seed: u32) u32 {
72 const m: u32 = 0x5bd1e995;
73 const len: u32 = 8;
74 var h1: u32 = seed ^ len;
75 var k1: u32 = undefined;
76 k1 = @as(u32, @truncate(v)) *% m;
77 k1 ^= k1 >> 24;
78 k1 *%= m;
79 h1 *%= m;
80 h1 ^= k1;
81 k1 = @as(u32, @truncate(v >> 32)) *% m;
82 k1 ^= k1 >> 24;
83 k1 *%= m;
84 h1 *%= m;
85 h1 ^= k1;
86 h1 ^= h1 >> 13;
87 h1 *%= m;
88 h1 ^= h1 >> 15;
89 return h1;
90 }
91};
92
93pub const Murmur2_64 = struct {
94 const Self = @This();
95
96 pub fn hash(str: []const u8) u64 {
97 return @call(.always_inline, Self.hashWithSeed, .{ str, default_seed });
98 }
99
100 pub fn hashWithSeed(str: []const u8, seed: u64) u64 {
101 const m: u64 = 0xc6a4a7935bd1e995;
102 var h1: u64 = seed ^ (@as(u64, str.len) *% m);
103 for (@as([*]align(1) const u64, @ptrCast(str.ptr))[0 .. str.len / 8]) |v| {
104 var k1: u64 = v;
105 if (native_endian == .big)
106 k1 = @byteSwap(k1);
107 k1 *%= m;
108 k1 ^= k1 >> 47;
109 k1 *%= m;
110 h1 ^= k1;
111 h1 *%= m;
112 }
113 const rest = str.len & 7;
114 const offset = str.len - rest;
115 if (rest > 0) {
116 var k1: u64 = 0;
117 @memcpy(@as([*]u8, @ptrCast(&k1))[0..rest], str[offset..]);
118 if (native_endian == .big)
119 k1 = @byteSwap(k1);
120 h1 ^= k1;
121 h1 *%= m;
122 }
123 h1 ^= h1 >> 47;
124 h1 *%= m;
125 h1 ^= h1 >> 47;
126 return h1;
127 }
128
129 pub fn hashUint32(v: u32) u64 {
130 return @call(.always_inline, Self.hashUint32WithSeed, .{ v, default_seed });
131 }
132
133 pub fn hashUint32WithSeed(v: u32, seed: u64) u64 {
134 const m: u64 = 0xc6a4a7935bd1e995;
135 const len: u64 = 4;
136 var h1: u64 = seed ^ (len *% m);
137 const k1: u64 = v;
138 h1 ^= k1;
139 h1 *%= m;
140 h1 ^= h1 >> 47;
141 h1 *%= m;
142 h1 ^= h1 >> 47;
143 return h1;
144 }
145
146 pub fn hashUint64(v: u64) u64 {
147 return @call(.always_inline, Self.hashUint64WithSeed, .{ v, default_seed });
148 }
149
150 pub fn hashUint64WithSeed(v: u64, seed: u64) u64 {
151 const m: u64 = 0xc6a4a7935bd1e995;
152 const len: u64 = 8;
153 var h1: u64 = seed ^ (len *% m);
154 var k1: u64 = undefined;
155 k1 = v *% m;
156 k1 ^= k1 >> 47;
157 k1 *%= m;
158 h1 ^= k1;
159 h1 *%= m;
160 h1 ^= h1 >> 47;
161 h1 *%= m;
162 h1 ^= h1 >> 47;
163 return h1;
164 }
165};
166
167pub const Murmur3_32 = struct {
168 const Self = @This();
169
170 fn rotl32(x: u32, comptime r: u32) u32 {
171 return (x << r) | (x >> (32 - r));
172 }
173
174 pub fn hash(str: []const u8) u32 {
175 return @call(.always_inline, Self.hashWithSeed, .{ str, default_seed });
176 }
177
178 pub fn hashWithSeed(str: []const u8, seed: u32) u32 {
179 const c1: u32 = 0xcc9e2d51;
180 const c2: u32 = 0x1b873593;
181 const len: u32 = @truncate(str.len);
182 var h1: u32 = seed;
183 for (@as([*]align(1) const u32, @ptrCast(str.ptr))[0..(len >> 2)]) |v| {
184 var k1: u32 = v;
185 if (native_endian == .big)
186 k1 = @byteSwap(k1);
187 k1 *%= c1;
188 k1 = rotl32(k1, 15);
189 k1 *%= c2;
190 h1 ^= k1;
191 h1 = rotl32(h1, 13);
192 h1 *%= 5;
193 h1 +%= 0xe6546b64;
194 }
195 {
196 var k1: u32 = 0;
197 const offset = len & 0xfffffffc;
198 const rest = len & 3;
199 if (rest == 3) {
200 k1 ^= @as(u32, @intCast(str[offset + 2])) << 16;
201 }
202 if (rest >= 2) {
203 k1 ^= @as(u32, @intCast(str[offset + 1])) << 8;
204 }
205 if (rest >= 1) {
206 k1 ^= @as(u32, @intCast(str[offset + 0]));
207 k1 *%= c1;
208 k1 = rotl32(k1, 15);
209 k1 *%= c2;
210 h1 ^= k1;
211 }
212 }
213 h1 ^= len;
214 h1 ^= h1 >> 16;
215 h1 *%= 0x85ebca6b;
216 h1 ^= h1 >> 13;
217 h1 *%= 0xc2b2ae35;
218 h1 ^= h1 >> 16;
219 return h1;
220 }
221
222 pub fn hashUint32(v: u32) u32 {
223 return @call(.always_inline, Self.hashUint32WithSeed, .{ v, default_seed });
224 }
225
226 pub fn hashUint32WithSeed(v: u32, seed: u32) u32 {
227 const c1: u32 = 0xcc9e2d51;
228 const c2: u32 = 0x1b873593;
229 const len: u32 = 4;
230 var h1: u32 = seed;
231 var k1: u32 = undefined;
232 k1 = v *% c1;
233 k1 = rotl32(k1, 15);
234 k1 *%= c2;
235 h1 ^= k1;
236 h1 = rotl32(h1, 13);
237 h1 *%= 5;
238 h1 +%= 0xe6546b64;
239 h1 ^= len;
240 h1 ^= h1 >> 16;
241 h1 *%= 0x85ebca6b;
242 h1 ^= h1 >> 13;
243 h1 *%= 0xc2b2ae35;
244 h1 ^= h1 >> 16;
245 return h1;
246 }
247
248 pub fn hashUint64(v: u64) u32 {
249 return @call(.always_inline, Self.hashUint64WithSeed, .{ v, default_seed });
250 }
251
252 pub fn hashUint64WithSeed(v: u64, seed: u32) u32 {
253 const c1: u32 = 0xcc9e2d51;
254 const c2: u32 = 0x1b873593;
255 const len: u32 = 8;
256 var h1: u32 = seed;
257 var k1: u32 = undefined;
258 k1 = @as(u32, @truncate(v)) *% c1;
259 k1 = rotl32(k1, 15);
260 k1 *%= c2;
261 h1 ^= k1;
262 h1 = rotl32(h1, 13);
263 h1 *%= 5;
264 h1 +%= 0xe6546b64;
265 k1 = @as(u32, @truncate(v >> 32)) *% c1;
266 k1 = rotl32(k1, 15);
267 k1 *%= c2;
268 h1 ^= k1;
269 h1 = rotl32(h1, 13);
270 h1 *%= 5;
271 h1 +%= 0xe6546b64;
272 h1 ^= len;
273 h1 ^= h1 >> 16;
274 h1 *%= 0x85ebca6b;
275 h1 ^= h1 >> 13;
276 h1 *%= 0xc2b2ae35;
277 h1 ^= h1 >> 16;
278 return h1;
279 }
280};
281
282const verify = @import("verify.zig");
283
284test "murmur2_32" {
285 const v0: u32 = 0x12345678;
286 const v1: u64 = 0x1234567812345678;
287 const v0le: u32, const v1le: u64 = switch (native_endian) {
288 .little => .{ v0, v1 },
289 .big => .{ @byteSwap(v0), @byteSwap(v1) },
290 };
291 try testing.expectEqual(Murmur2_32.hash(@as([*]const u8, @ptrCast(&v0le))[0..4]), Murmur2_32.hashUint32(v0));
292 try testing.expectEqual(Murmur2_32.hash(@as([*]const u8, @ptrCast(&v1le))[0..8]), Murmur2_32.hashUint64(v1));
293}
294
295test "murmur2_32 smhasher" {
296 const Test = struct {
297 fn do() !void {
298 try testing.expectEqual(verify.smhasher(Murmur2_32.hashWithSeed), 0x27864C1E);
299 }
300 };
301 try Test.do();
302 @setEvalBranchQuota(30000);
303 try comptime Test.do();
304}
305
306test "murmur2_64" {
307 const v0: u32 = 0x12345678;
308 const v1: u64 = 0x1234567812345678;
309 const v0le: u32, const v1le: u64 = switch (native_endian) {
310 .little => .{ v0, v1 },
311 .big => .{ @byteSwap(v0), @byteSwap(v1) },
312 };
313 try testing.expectEqual(Murmur2_64.hash(@as([*]const u8, @ptrCast(&v0le))[0..4]), Murmur2_64.hashUint32(v0));
314 try testing.expectEqual(Murmur2_64.hash(@as([*]const u8, @ptrCast(&v1le))[0..8]), Murmur2_64.hashUint64(v1));
315}
316
317test "mumur2_64 smhasher" {
318 const Test = struct {
319 fn do() !void {
320 try std.testing.expectEqual(verify.smhasher(Murmur2_64.hashWithSeed), 0x1F0D3804);
321 }
322 };
323 try Test.do();
324 @setEvalBranchQuota(30000);
325 try comptime Test.do();
326}
327
328test "murmur3_32" {
329 const v0: u32 = 0x12345678;
330 const v1: u64 = 0x1234567812345678;
331 const v0le: u32, const v1le: u64 = switch (native_endian) {
332 .little => .{ v0, v1 },
333 .big => .{ @byteSwap(v0), @byteSwap(v1) },
334 };
335 try testing.expectEqual(Murmur3_32.hash(@as([*]const u8, @ptrCast(&v0le))[0..4]), Murmur3_32.hashUint32(v0));
336 try testing.expectEqual(Murmur3_32.hash(@as([*]const u8, @ptrCast(&v1le))[0..8]), Murmur3_32.hashUint64(v1));
337}
338
339test "mumur3_32 smhasher" {
340 const Test = struct {
341 fn do() !void {
342 try std.testing.expectEqual(verify.smhasher(Murmur3_32.hashWithSeed), 0xB0F57EE3);
343 }
344 };
345 try Test.do();
346 @setEvalBranchQuota(30000);
347 try comptime Test.do();
348}