master
1const std = @import("std");
2const builtin = @import("builtin");
3const mem = std.mem;
4const expectEqual = std.testing.expectEqual;
5const native_endian = builtin.cpu.arch.endian();
6
7const rotl = std.math.rotl;
8
9pub const XxHash64 = struct {
10 accumulator: Accumulator,
11 seed: u64,
12 buf: [32]u8,
13 buf_len: usize,
14 byte_count: usize,
15
16 const prime_1 = 0x9E3779B185EBCA87; // 0b1001111000110111011110011011000110000101111010111100101010000111
17 const prime_2 = 0xC2B2AE3D27D4EB4F; // 0b1100001010110010101011100011110100100111110101001110101101001111
18 const prime_3 = 0x165667B19E3779F9; // 0b0001011001010110011001111011000110011110001101110111100111111001
19 const prime_4 = 0x85EBCA77C2B2AE63; // 0b1000010111101011110010100111011111000010101100101010111001100011
20 const prime_5 = 0x27D4EB2F165667C5; // 0b0010011111010100111010110010111100010110010101100110011111000101
21
22 const Accumulator = struct {
23 acc1: u64,
24 acc2: u64,
25 acc3: u64,
26 acc4: u64,
27
28 fn init(seed: u64) Accumulator {
29 return .{
30 .acc1 = seed +% prime_1 +% prime_2,
31 .acc2 = seed +% prime_2,
32 .acc3 = seed,
33 .acc4 = seed -% prime_1,
34 };
35 }
36
37 fn updateEmpty(self: *Accumulator, input: anytype, comptime unroll_count: usize) usize {
38 var i: usize = 0;
39
40 if (unroll_count > 0) {
41 const unrolled_bytes = unroll_count * 32;
42 while (i + unrolled_bytes <= input.len) : (i += unrolled_bytes) {
43 inline for (0..unroll_count) |j| {
44 self.processStripe(input[i + j * 32 ..][0..32]);
45 }
46 }
47 }
48
49 while (i + 32 <= input.len) : (i += 32) {
50 self.processStripe(input[i..][0..32]);
51 }
52
53 return i;
54 }
55
56 fn processStripe(self: *Accumulator, buf: *const [32]u8) void {
57 self.acc1 = round(self.acc1, mem.readInt(u64, buf[0..8], .little));
58 self.acc2 = round(self.acc2, mem.readInt(u64, buf[8..16], .little));
59 self.acc3 = round(self.acc3, mem.readInt(u64, buf[16..24], .little));
60 self.acc4 = round(self.acc4, mem.readInt(u64, buf[24..32], .little));
61 }
62
63 fn merge(self: Accumulator) u64 {
64 var acc = rotl(u64, self.acc1, 1) +% rotl(u64, self.acc2, 7) +%
65 rotl(u64, self.acc3, 12) +% rotl(u64, self.acc4, 18);
66 acc = mergeAccumulator(acc, self.acc1);
67 acc = mergeAccumulator(acc, self.acc2);
68 acc = mergeAccumulator(acc, self.acc3);
69 acc = mergeAccumulator(acc, self.acc4);
70 return acc;
71 }
72
73 fn mergeAccumulator(acc: u64, other: u64) u64 {
74 const a = acc ^ round(0, other);
75 const b = a *% prime_1;
76 return b +% prime_4;
77 }
78 };
79
80 fn finalize(
81 unfinished: u64,
82 byte_count: usize,
83 partial: anytype,
84 ) u64 {
85 std.debug.assert(partial.len < 32);
86 var acc = unfinished +% @as(u64, byte_count) +% @as(u64, partial.len);
87
88 switch (partial.len) {
89 inline 0, 1, 2, 3 => |count| {
90 inline for (0..count) |i| acc = finalize1(acc, partial[i]);
91 return avalanche(acc);
92 },
93 inline 4, 5, 6, 7 => |count| {
94 acc = finalize4(acc, partial[0..4]);
95 inline for (4..count) |i| acc = finalize1(acc, partial[i]);
96 return avalanche(acc);
97 },
98 inline 8, 9, 10, 11 => |count| {
99 acc = finalize8(acc, partial[0..8]);
100 inline for (8..count) |i| acc = finalize1(acc, partial[i]);
101 return avalanche(acc);
102 },
103 inline 12, 13, 14, 15 => |count| {
104 acc = finalize8(acc, partial[0..8]);
105 acc = finalize4(acc, partial[8..12]);
106 inline for (12..count) |i| acc = finalize1(acc, partial[i]);
107 return avalanche(acc);
108 },
109 inline 16, 17, 18, 19 => |count| {
110 acc = finalize8(acc, partial[0..8]);
111 acc = finalize8(acc, partial[8..16]);
112 inline for (16..count) |i| acc = finalize1(acc, partial[i]);
113 return avalanche(acc);
114 },
115 inline 20, 21, 22, 23 => |count| {
116 acc = finalize8(acc, partial[0..8]);
117 acc = finalize8(acc, partial[8..16]);
118 acc = finalize4(acc, partial[16..20]);
119 inline for (20..count) |i| acc = finalize1(acc, partial[i]);
120 return avalanche(acc);
121 },
122 inline 24, 25, 26, 27 => |count| {
123 acc = finalize8(acc, partial[0..8]);
124 acc = finalize8(acc, partial[8..16]);
125 acc = finalize8(acc, partial[16..24]);
126 inline for (24..count) |i| acc = finalize1(acc, partial[i]);
127 return avalanche(acc);
128 },
129 inline 28, 29, 30, 31 => |count| {
130 acc = finalize8(acc, partial[0..8]);
131 acc = finalize8(acc, partial[8..16]);
132 acc = finalize8(acc, partial[16..24]);
133 acc = finalize4(acc, partial[24..28]);
134 inline for (28..count) |i| acc = finalize1(acc, partial[i]);
135 return avalanche(acc);
136 },
137 else => unreachable,
138 }
139 }
140
141 fn finalize8(v: u64, bytes: *const [8]u8) u64 {
142 var acc = v;
143 const lane = mem.readInt(u64, bytes, .little);
144 acc ^= round(0, lane);
145 acc = rotl(u64, acc, 27) *% prime_1;
146 acc +%= prime_4;
147 return acc;
148 }
149
150 fn finalize4(v: u64, bytes: *const [4]u8) u64 {
151 var acc = v;
152 const lane = @as(u64, mem.readInt(u32, bytes, .little));
153 acc ^= lane *% prime_1;
154 acc = rotl(u64, acc, 23) *% prime_2;
155 acc +%= prime_3;
156 return acc;
157 }
158
159 fn finalize1(v: u64, byte: u8) u64 {
160 var acc = v;
161 const lane = @as(u64, byte);
162 acc ^= lane *% prime_5;
163 acc = rotl(u64, acc, 11) *% prime_1;
164 return acc;
165 }
166
167 fn avalanche(value: u64) u64 {
168 var result = value ^ (value >> 33);
169 result *%= prime_2;
170 result ^= result >> 29;
171 result *%= prime_3;
172 result ^= result >> 32;
173
174 return result;
175 }
176
177 pub fn init(seed: u64) XxHash64 {
178 return XxHash64{
179 .accumulator = Accumulator.init(seed),
180 .seed = seed,
181 .buf = undefined,
182 .buf_len = 0,
183 .byte_count = 0,
184 };
185 }
186
187 pub fn update(self: *XxHash64, input: anytype) void {
188 if (input.len < 32 - self.buf_len) {
189 @memcpy(self.buf[self.buf_len..][0..input.len], input);
190 self.buf_len += input.len;
191 return;
192 }
193
194 var i: usize = 0;
195
196 if (self.buf_len > 0) {
197 i = 32 - self.buf_len;
198 @memcpy(self.buf[self.buf_len..][0..i], input[0..i]);
199 self.accumulator.processStripe(&self.buf);
200 self.byte_count += self.buf_len;
201 }
202
203 i += self.accumulator.updateEmpty(input[i..], 32);
204 self.byte_count += i;
205
206 const remaining_bytes = input[i..];
207 @memcpy(self.buf[0..remaining_bytes.len], remaining_bytes);
208 self.buf_len = remaining_bytes.len;
209 }
210
211 fn round(acc: u64, lane: u64) u64 {
212 const a = acc +% (lane *% prime_2);
213 const b = rotl(u64, a, 31);
214 return b *% prime_1;
215 }
216
217 pub fn final(self: *XxHash64) u64 {
218 const unfinished = if (self.byte_count < 32)
219 self.seed +% prime_5
220 else
221 self.accumulator.merge();
222
223 return finalize(unfinished, self.byte_count, self.buf[0..self.buf_len]);
224 }
225
226 const Size = enum {
227 small,
228 large,
229 unknown,
230 };
231
232 pub fn hash(seed: u64, input: anytype) u64 {
233 if (input.len < 32) {
234 return finalize(seed +% prime_5, 0, input);
235 } else {
236 var hasher = Accumulator.init(seed);
237 const i = hasher.updateEmpty(input, 0);
238 return finalize(hasher.merge(), i, input[i..]);
239 }
240 }
241};
242
243pub const XxHash32 = struct {
244 accumulator: Accumulator,
245 seed: u32,
246 buf: [16]u8,
247 buf_len: usize,
248 byte_count: usize,
249
250 const prime_1 = 0x9E3779B1; // 0b10011110001101110111100110110001
251 const prime_2 = 0x85EBCA77; // 0b10000101111010111100101001110111
252 const prime_3 = 0xC2B2AE3D; // 0b11000010101100101010111000111101
253 const prime_4 = 0x27D4EB2F; // 0b00100111110101001110101100101111
254 const prime_5 = 0x165667B1; // 0b00010110010101100110011110110001
255
256 const Accumulator = struct {
257 acc1: u32,
258 acc2: u32,
259 acc3: u32,
260 acc4: u32,
261
262 fn init(seed: u32) Accumulator {
263 return .{
264 .acc1 = seed +% prime_1 +% prime_2,
265 .acc2 = seed +% prime_2,
266 .acc3 = seed,
267 .acc4 = seed -% prime_1,
268 };
269 }
270
271 fn updateEmpty(self: *Accumulator, input: anytype, comptime unroll_count: usize) usize {
272 var i: usize = 0;
273
274 if (unroll_count > 0) {
275 const unrolled_bytes = unroll_count * 16;
276 while (i + unrolled_bytes <= input.len) : (i += unrolled_bytes) {
277 inline for (0..unroll_count) |j| {
278 self.processStripe(input[i + j * 16 ..][0..16]);
279 }
280 }
281 }
282
283 while (i + 16 <= input.len) : (i += 16) {
284 self.processStripe(input[i..][0..16]);
285 }
286
287 return i;
288 }
289
290 fn processStripe(self: *Accumulator, buf: *const [16]u8) void {
291 self.acc1 = round(self.acc1, mem.readInt(u32, buf[0..4], .little));
292 self.acc2 = round(self.acc2, mem.readInt(u32, buf[4..8], .little));
293 self.acc3 = round(self.acc3, mem.readInt(u32, buf[8..12], .little));
294 self.acc4 = round(self.acc4, mem.readInt(u32, buf[12..16], .little));
295 }
296
297 fn merge(self: Accumulator) u32 {
298 return rotl(u32, self.acc1, 1) +% rotl(u32, self.acc2, 7) +%
299 rotl(u32, self.acc3, 12) +% rotl(u32, self.acc4, 18);
300 }
301 };
302
303 pub fn init(seed: u32) XxHash32 {
304 return XxHash32{
305 .accumulator = Accumulator.init(seed),
306 .seed = seed,
307 .buf = undefined,
308 .buf_len = 0,
309 .byte_count = 0,
310 };
311 }
312
313 pub fn update(self: *XxHash32, input: []const u8) void {
314 if (input.len < 16 - self.buf_len) {
315 @memcpy(self.buf[self.buf_len..][0..input.len], input);
316 self.buf_len += input.len;
317 return;
318 }
319
320 var i: usize = 0;
321
322 if (self.buf_len > 0) {
323 i = 16 - self.buf_len;
324 @memcpy(self.buf[self.buf_len..][0..i], input[0..i]);
325 self.accumulator.processStripe(&self.buf);
326 self.byte_count += self.buf_len;
327 self.buf_len = 0;
328 }
329
330 i += self.accumulator.updateEmpty(input[i..], 16);
331 self.byte_count += i;
332
333 const remaining_bytes = input[i..];
334 @memcpy(self.buf[0..remaining_bytes.len], remaining_bytes);
335 self.buf_len = remaining_bytes.len;
336 }
337
338 fn round(acc: u32, lane: u32) u32 {
339 const a = acc +% (lane *% prime_2);
340 const b = rotl(u32, a, 13);
341 return b *% prime_1;
342 }
343
344 pub fn final(self: *XxHash32) u32 {
345 const unfinished = if (self.byte_count < 16)
346 self.seed +% prime_5
347 else
348 self.accumulator.merge();
349
350 return finalize(unfinished, self.byte_count, self.buf[0..self.buf_len]);
351 }
352
353 fn finalize(unfinished: u32, byte_count: usize, partial: anytype) u32 {
354 std.debug.assert(partial.len < 16);
355 var acc = unfinished +% @as(u32, @intCast(byte_count)) +% @as(u32, @intCast(partial.len));
356
357 switch (partial.len) {
358 inline 0, 1, 2, 3 => |count| {
359 inline for (0..count) |i| acc = finalize1(acc, partial[i]);
360 return avalanche(acc);
361 },
362 inline 4, 5, 6, 7 => |count| {
363 acc = finalize4(acc, partial[0..4]);
364 inline for (4..count) |i| acc = finalize1(acc, partial[i]);
365 return avalanche(acc);
366 },
367 inline 8, 9, 10, 11 => |count| {
368 acc = finalize4(acc, partial[0..4]);
369 acc = finalize4(acc, partial[4..8]);
370 inline for (8..count) |i| acc = finalize1(acc, partial[i]);
371 return avalanche(acc);
372 },
373 inline 12, 13, 14, 15 => |count| {
374 acc = finalize4(acc, partial[0..4]);
375 acc = finalize4(acc, partial[4..8]);
376 acc = finalize4(acc, partial[8..12]);
377 inline for (12..count) |i| acc = finalize1(acc, partial[i]);
378 return avalanche(acc);
379 },
380 else => unreachable,
381 }
382
383 return avalanche(acc);
384 }
385
386 fn finalize4(v: u32, bytes: *const [4]u8) u32 {
387 var acc = v;
388 const lane = mem.readInt(u32, bytes, .little);
389 acc +%= lane *% prime_3;
390 acc = rotl(u32, acc, 17) *% prime_4;
391 return acc;
392 }
393
394 fn finalize1(v: u32, byte: u8) u32 {
395 var acc = v;
396 const lane = @as(u32, byte);
397 acc +%= lane *% prime_5;
398 acc = rotl(u32, acc, 11) *% prime_1;
399 return acc;
400 }
401
402 fn avalanche(value: u32) u32 {
403 var acc = value ^ value >> 15;
404 acc *%= prime_2;
405 acc ^= acc >> 13;
406 acc *%= prime_3;
407 acc ^= acc >> 16;
408
409 return acc;
410 }
411
412 pub fn hash(seed: u32, input: anytype) u32 {
413 if (input.len < 16) {
414 return finalize(seed +% prime_5, 0, input);
415 } else {
416 var hasher = Accumulator.init(seed);
417 const i = hasher.updateEmpty(input, 0);
418 return finalize(hasher.merge(), i, input[i..]);
419 }
420 }
421};
422
423pub const XxHash3 = struct {
424 const Block = @Vector(8, u64);
425 const default_secret: [192]u8 = .{
426 0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
427 0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
428 0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
429 0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
430 0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
431 0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
432 0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
433 0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
434 0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
435 0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
436 0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
437 0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
438 };
439
440 const prime_mx1 = 0x165667919E3779F9;
441 const prime_mx2 = 0x9FB21C651E98DF25;
442
443 inline fn avalanche(mode: union(enum) { h3, h64, rrmxmx: u64 }, x0: u64) u64 {
444 switch (mode) {
445 .h3 => {
446 const x1 = (x0 ^ (x0 >> 37)) *% prime_mx1;
447 return x1 ^ (x1 >> 32);
448 },
449 .h64 => {
450 const x1 = (x0 ^ (x0 >> 33)) *% XxHash64.prime_2;
451 const x2 = (x1 ^ (x1 >> 29)) *% XxHash64.prime_3;
452 return x2 ^ (x2 >> 32);
453 },
454 .rrmxmx => |len| {
455 const x1 = (x0 ^ rotl(u64, x0, 49) ^ rotl(u64, x0, 24)) *% prime_mx2;
456 const x2 = (x1 ^ ((x1 >> 35) +% len)) *% prime_mx2;
457 return x2 ^ (x2 >> 28);
458 },
459 }
460 }
461
462 inline fn fold(a: u64, b: u64) u64 {
463 const wide: [2]u64 = @bitCast(@as(u128, a) *% b);
464 return wide[0] ^ wide[1];
465 }
466
467 inline fn swap(x: anytype) @TypeOf(x) {
468 return if (native_endian == .big) @byteSwap(x) else x;
469 }
470
471 inline fn disableAutoVectorization(x: anytype) void {
472 if (!@inComptime()) asm volatile (""
473 :
474 : [x] "r" (x),
475 );
476 }
477
478 inline fn mix16(seed: u64, input: []const u8, secret: []const u8) u64 {
479 const blk: [4]u64 = @bitCast([_][16]u8{ input[0..16].*, secret[0..16].* });
480 disableAutoVectorization(seed);
481
482 return fold(
483 swap(blk[0]) ^ (swap(blk[2]) +% seed),
484 swap(blk[1]) ^ (swap(blk[3]) -% seed),
485 );
486 }
487
488 const Accumulator = extern struct {
489 consumed: usize = 0,
490 seed: u64,
491 secret: [192]u8 = undefined,
492 state: Block = Block{
493 XxHash32.prime_3,
494 XxHash64.prime_1,
495 XxHash64.prime_2,
496 XxHash64.prime_3,
497 XxHash64.prime_4,
498 XxHash32.prime_2,
499 XxHash64.prime_5,
500 XxHash32.prime_1,
501 },
502
503 inline fn init(seed: u64) Accumulator {
504 var self = Accumulator{ .seed = seed };
505 for (
506 std.mem.bytesAsSlice(Block, &self.secret),
507 std.mem.bytesAsSlice(Block, &default_secret),
508 ) |*dst, src| {
509 dst.* = swap(swap(src) +% Block{
510 seed, @as(u64, 0) -% seed,
511 seed, @as(u64, 0) -% seed,
512 seed, @as(u64, 0) -% seed,
513 seed, @as(u64, 0) -% seed,
514 });
515 }
516 return self;
517 }
518
519 inline fn round(
520 noalias state: *Block,
521 noalias input_block: *align(1) const Block,
522 noalias secret_block: *align(1) const Block,
523 ) void {
524 const data = swap(input_block.*);
525 const mixed = data ^ swap(secret_block.*);
526 state.* +%= (mixed & @as(Block, @splat(0xffffffff))) *% (mixed >> @splat(32));
527 state.* +%= @shuffle(u64, data, undefined, [_]i32{ 1, 0, 3, 2, 5, 4, 7, 6 });
528 }
529
530 fn accumulate(noalias self: *Accumulator, blocks: []align(1) const Block) void {
531 const secret = std.mem.bytesAsSlice(u64, self.secret[self.consumed * 8 ..]);
532 for (blocks, secret[0..blocks.len]) |*input_block, *secret_block| {
533 @prefetch(@as([*]const u8, @ptrCast(input_block)) + 320, .{});
534 round(&self.state, input_block, @ptrCast(secret_block));
535 }
536 }
537
538 fn scramble(self: *Accumulator) void {
539 const secret_block: Block = @bitCast(self.secret[192 - @sizeOf(Block) .. 192].*);
540 self.state ^= self.state >> @splat(47);
541 self.state ^= swap(secret_block);
542 self.state *%= @as(Block, @splat(XxHash32.prime_1));
543 }
544
545 fn consume(noalias self: *Accumulator, input_blocks: []align(1) const Block) void {
546 const blocks_per_scramble = 1024 / @sizeOf(Block);
547 std.debug.assert(self.consumed <= blocks_per_scramble);
548
549 var blocks = input_blocks;
550 var blocks_until_scramble = blocks_per_scramble - self.consumed;
551 while (blocks.len >= blocks_until_scramble) {
552 self.accumulate(blocks[0..blocks_until_scramble]);
553 self.scramble();
554
555 self.consumed = 0;
556 blocks = blocks[blocks_until_scramble..];
557 blocks_until_scramble = blocks_per_scramble;
558 }
559
560 self.accumulate(blocks);
561 self.consumed += blocks.len;
562 }
563
564 fn digest(noalias self: *Accumulator, total_len: u64, noalias last_block: *align(1) const Block) u64 {
565 const secret_block = self.secret[192 - @sizeOf(Block) - 7 ..][0..@sizeOf(Block)];
566 round(&self.state, last_block, @ptrCast(secret_block));
567
568 const merge_block: Block = @bitCast(self.secret[11 .. 11 + @sizeOf(Block)].*);
569 self.state ^= swap(merge_block);
570
571 var result = XxHash64.prime_1 *% total_len;
572 inline for (0..4) |i| {
573 result +%= fold(self.state[i * 2], self.state[i * 2 + 1]);
574 }
575 return avalanche(.h3, result);
576 }
577 };
578
579 // Public API - Oneshot
580
581 pub fn hash(seed: u64, input: anytype) u64 {
582 const secret = &default_secret;
583 if (input.len > 240) return hashLong(seed, input);
584 if (input.len > 128) return hash240(seed, input, secret);
585 if (input.len > 16) return hash128(seed, input, secret);
586 if (input.len > 8) return hash16(seed, input, secret);
587 if (input.len > 3) return hash8(seed, input, secret);
588 if (input.len > 0) return hash3(seed, input, secret);
589
590 const flip: [2]u64 = @bitCast(secret[56..72].*);
591 const key = swap(flip[0]) ^ swap(flip[1]);
592 return avalanche(.h64, seed ^ key);
593 }
594
595 fn hash3(seed: u64, input: anytype, noalias secret: *const [192]u8) u64 {
596 @branchHint(.unlikely);
597 std.debug.assert(input.len > 0 and input.len < 4);
598
599 const flip: [2]u32 = @bitCast(secret[0..8].*);
600 const blk: u32 = @bitCast([_]u8{
601 input[input.len - 1],
602 @truncate(input.len),
603 input[0],
604 input[input.len / 2],
605 });
606
607 const key = @as(u64, swap(flip[0]) ^ swap(flip[1])) +% seed;
608 return avalanche(.h64, key ^ swap(blk));
609 }
610
611 fn hash8(seed: u64, input: anytype, noalias secret: *const [192]u8) u64 {
612 @branchHint(.cold);
613 std.debug.assert(input.len >= 4 and input.len <= 8);
614
615 const flip: [2]u64 = @bitCast(secret[8..24].*);
616 const blk: [2]u32 = @bitCast([_][4]u8{
617 input[0..4].*,
618 input[input.len - 4 ..][0..4].*,
619 });
620
621 const mixed = seed ^ (@as(u64, @byteSwap(@as(u32, @truncate(seed)))) << 32);
622 const key = (swap(flip[0]) ^ swap(flip[1])) -% mixed;
623 const combined = (@as(u64, swap(blk[0])) << 32) +% swap(blk[1]);
624 return avalanche(.{ .rrmxmx = input.len }, key ^ combined);
625 }
626
627 fn hash16(seed: u64, input: anytype, noalias secret: *const [192]u8) u64 {
628 @branchHint(.unlikely);
629 std.debug.assert(input.len > 8 and input.len <= 16);
630
631 const flip: [4]u64 = @bitCast(secret[24..56].*);
632 const blk: [2]u64 = @bitCast([_][8]u8{
633 input[0..8].*,
634 input[input.len - 8 ..][0..8].*,
635 });
636
637 const lo = swap(blk[0]) ^ ((swap(flip[0]) ^ swap(flip[1])) +% seed);
638 const hi = swap(blk[1]) ^ ((swap(flip[2]) ^ swap(flip[3])) -% seed);
639 const combined = @as(u64, input.len) +% @byteSwap(lo) +% hi +% fold(lo, hi);
640 return avalanche(.h3, combined);
641 }
642
643 fn hash128(seed: u64, input: anytype, noalias secret: *const [192]u8) u64 {
644 @branchHint(.unlikely);
645 std.debug.assert(input.len > 16 and input.len <= 128);
646
647 var acc = XxHash64.prime_1 *% @as(u64, input.len);
648 inline for (0..4) |i| {
649 const in_offset = 48 - (i * 16);
650 const scrt_offset = 96 - (i * 32);
651 if (input.len > scrt_offset) {
652 acc +%= mix16(seed, input[in_offset..], secret[scrt_offset..]);
653 acc +%= mix16(seed, input[input.len - (in_offset + 16) ..], secret[scrt_offset + 16 ..]);
654 }
655 }
656 return avalanche(.h3, acc);
657 }
658
659 fn hash240(seed: u64, input: anytype, noalias secret: *const [192]u8) u64 {
660 @branchHint(.unlikely);
661 std.debug.assert(input.len > 128 and input.len <= 240);
662
663 var acc = XxHash64.prime_1 *% @as(u64, input.len);
664 inline for (0..8) |i| {
665 acc +%= mix16(seed, input[i * 16 ..], secret[i * 16 ..]);
666 }
667
668 var acc_end = mix16(seed, input[input.len - 16 ..], secret[136 - 17 ..]);
669 for (8..(input.len / 16)) |i| {
670 acc_end +%= mix16(seed, input[i * 16 ..], secret[((i - 8) * 16) + 3 ..]);
671 disableAutoVectorization(i);
672 }
673
674 acc = avalanche(.h3, acc) +% acc_end;
675 return avalanche(.h3, acc);
676 }
677
678 noinline fn hashLong(seed: u64, input: []const u8) u64 {
679 @branchHint(.unlikely);
680 std.debug.assert(input.len >= 240);
681
682 const block_count = ((input.len - 1) / @sizeOf(Block)) * @sizeOf(Block);
683 const last_block = input[input.len - @sizeOf(Block) ..][0..@sizeOf(Block)];
684
685 var acc = Accumulator.init(seed);
686 acc.consume(std.mem.bytesAsSlice(Block, input[0..block_count]));
687 return acc.digest(input.len, @ptrCast(last_block));
688 }
689
690 // Public API - Streaming
691
692 buffered: usize = 0,
693 buffer: [256]u8 = undefined,
694 total_len: usize = 0,
695 accumulator: Accumulator,
696
697 pub fn init(seed: u64) XxHash3 {
698 return .{ .accumulator = Accumulator.init(seed) };
699 }
700
701 pub fn update(self: *XxHash3, input: anytype) void {
702 self.total_len += input.len;
703 std.debug.assert(self.buffered <= self.buffer.len);
704
705 // Copy the input into the buffer if we haven't filled it up yet.
706 const remaining = self.buffer.len - self.buffered;
707 if (input.len <= remaining) {
708 @memcpy(self.buffer[self.buffered..][0..input.len], input);
709 self.buffered += input.len;
710 return;
711 }
712
713 // Input will overflow the buffer. Fill up the buffer with some input and consume it.
714 var consumable: []const u8 = input;
715 if (self.buffered > 0) {
716 @memcpy(self.buffer[self.buffered..], consumable[0..remaining]);
717 consumable = consumable[remaining..];
718
719 self.accumulator.consume(std.mem.bytesAsSlice(Block, &self.buffer));
720 self.buffered = 0;
721 }
722
723 // The input isn't small enough to fit in the buffer. Consume it directly.
724 if (consumable.len > self.buffer.len) {
725 const block_count = ((consumable.len - 1) / @sizeOf(Block)) * @sizeOf(Block);
726 self.accumulator.consume(std.mem.bytesAsSlice(Block, consumable[0..block_count]));
727 consumable = consumable[block_count..];
728
729 // In case we consume all remaining input, write the last block to end of the buffer
730 // to populate the last_block_copy in final() similar to hashLong()'s last_block.
731 @memcpy(
732 self.buffer[self.buffer.len - @sizeOf(Block) .. self.buffer.len],
733 (consumable.ptr - @sizeOf(Block))[0..@sizeOf(Block)],
734 );
735 }
736
737 // Copy in any remaining input into the buffer.
738 std.debug.assert(consumable.len <= self.buffer.len);
739 @memcpy(self.buffer[0..consumable.len], consumable);
740 self.buffered = consumable.len;
741 }
742
743 pub fn final(self: *XxHash3) u64 {
744 std.debug.assert(self.buffered <= self.total_len);
745 std.debug.assert(self.buffered <= self.buffer.len);
746
747 // Use Oneshot hashing for smaller sizes as it doesn't use Accumulator like hashLong.
748 if (self.total_len <= 240) {
749 return hash(self.accumulator.seed, self.buffer[0..self.total_len]);
750 }
751
752 // Make a copy of the Accumulator state in case `self` needs to update() / be used later.
753 var accumulator_copy = self.accumulator;
754 var last_block_copy: [@sizeOf(Block)]u8 = undefined;
755
756 // Digest the last block onthe Accumulator copy.
757 return accumulator_copy.digest(self.total_len, last_block: {
758 if (self.buffered >= @sizeOf(Block)) {
759 const block_count = ((self.buffered - 1) / @sizeOf(Block)) * @sizeOf(Block);
760 accumulator_copy.consume(std.mem.bytesAsSlice(Block, self.buffer[0..block_count]));
761 break :last_block @ptrCast(self.buffer[self.buffered - @sizeOf(Block) ..][0..@sizeOf(Block)]);
762 } else {
763 const remaining = @sizeOf(Block) - self.buffered;
764 @memcpy(last_block_copy[0..remaining], self.buffer[self.buffer.len - remaining ..][0..remaining]);
765 @memcpy(last_block_copy[remaining..][0..self.buffered], self.buffer[0..self.buffered]);
766 break :last_block @ptrCast(&last_block_copy);
767 }
768 });
769 }
770};
771
772const verify = @import("verify.zig");
773
774fn testExpect(comptime H: type, seed: anytype, input: []const u8, expected: u64) !void {
775 try expectEqual(expected, H.hash(seed, input));
776
777 var hasher = H.init(seed);
778 hasher.update(input);
779 try expectEqual(expected, hasher.final());
780}
781
782test "xxhash3" {
783 if (builtin.cpu.arch.isMIPS64()) return error.SkipZigTest; // https://github.com/ziglang/zig/issues/23807
784
785 const H = XxHash3;
786 // Non-Seeded Tests
787 try testExpect(H, 0, "", 0x2d06800538d394c2);
788 try testExpect(H, 0, "a", 0xe6c632b61e964e1f);
789 try testExpect(H, 0, "abc", 0x78af5f94892f3950);
790 try testExpect(H, 0, "message", 0x0b1ca9b8977554fa);
791 try testExpect(H, 0, "message digest", 0x160d8e9329be94f9);
792 try testExpect(H, 0, "abcdefghijklmnopqrstuvwxyz", 0x810f9ca067fbb90c);
793 try testExpect(H, 0, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 0x643542bb51639cb2);
794 try testExpect(H, 0, "12345678901234567890123456789012345678901234567890123456789012345678901234567890", 0x7f58aa2520c681f9);
795 try testExpect(H, 0, "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678", 0xb66ea795b5edc38c);
796 try testExpect(H, 0, "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", 0x8845e0b1b57330de);
797 try testExpect(H, 0, "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123123", 0xf031f373d63c5653);
798 try testExpect(H, 0, "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", 0xf1bf601f9d868dce);
799
800 // Seeded Tests
801 try testExpect(H, 1, "", 0x4dc5b0cc826f6703);
802 try testExpect(H, 1, "a", 0xd2f6d0996f37a720);
803 try testExpect(H, 1, "abc", 0x6b4467b443c76228);
804 try testExpect(H, 1, "message", 0x73fb1cf20d561766);
805 try testExpect(H, 1, "message digest", 0xfe71a82a70381174);
806 try testExpect(H, 1, "abcdefghijklmnopqrstuvwxyz", 0x902a2c2d016a37ba);
807 try testExpect(H, 1, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 0xbf552e540c5c6882);
808 try testExpect(H, 1, "12345678901234567890123456789012345678901234567890123456789012345678901234567890", 0xf2ca33235a6b865b);
809 try testExpect(H, 1, "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678", 0x6ef5cf958ba52c4);
810 try testExpect(H, 1, "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", 0xfbc5f9c53d21cb2f);
811 try testExpect(H, 1, "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123123", 0x48682aca3b1c5c18);
812 try testExpect(H, 1, "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", 0x3903c5437fc4e726);
813}
814
815test "xxhash3 smhasher" {
816 if (builtin.cpu.arch.isMIPS64()) return error.SkipZigTest; // https://github.com/ziglang/zig/issues/23807
817
818 const Test = struct {
819 fn do() !void {
820 try expectEqual(verify.smhasher(XxHash3.hash), 0x9a636405);
821 }
822 };
823 try Test.do();
824 @setEvalBranchQuota(75000);
825 comptime try Test.do();
826}
827
828test "xxhash3 iterative api" {
829 if (builtin.cpu.arch.isMIPS64()) return error.SkipZigTest; // https://github.com/ziglang/zig/issues/23807
830
831 const Test = struct {
832 fn do() !void {
833 try verify.iterativeApi(XxHash3);
834 }
835 };
836 try Test.do();
837 @setEvalBranchQuota(30000);
838 comptime try Test.do();
839}
840
841test "xxhash64" {
842 const H = XxHash64;
843 try testExpect(H, 0, "", 0xef46db3751d8e999);
844 try testExpect(H, 0, "a", 0xd24ec4f1a98c6e5b);
845 try testExpect(H, 0, "abc", 0x44bc2cf5ad770999);
846 try testExpect(H, 0, "message digest", 0x066ed728fceeb3be);
847 try testExpect(H, 0, "abcdefghijklmnopqrstuvwxyz", 0xcfe1f278fa89835c);
848 try testExpect(H, 0, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 0xaaa46907d3047814);
849 try testExpect(H, 0, "12345678901234567890123456789012345678901234567890123456789012345678901234567890", 0xe04a477f19ee145d);
850}
851
852test "xxhash64 smhasher" {
853 const Test = struct {
854 fn do() !void {
855 try expectEqual(verify.smhasher(XxHash64.hash), 0x024B7CF4);
856 }
857 };
858 try Test.do();
859 @setEvalBranchQuota(75000);
860 comptime try Test.do();
861}
862
863test "xxhash64 iterative api" {
864 const Test = struct {
865 fn do() !void {
866 try verify.iterativeApi(XxHash64);
867 }
868 };
869 try Test.do();
870 @setEvalBranchQuota(30000);
871 comptime try Test.do();
872}
873
874test "xxhash32" {
875 const H = XxHash32;
876
877 try testExpect(H, 0, "", 0x02cc5d05);
878 try testExpect(H, 0, "a", 0x550d7456);
879 try testExpect(H, 0, "abc", 0x32d153ff);
880 try testExpect(H, 0, "message digest", 0x7c948494);
881 try testExpect(H, 0, "abcdefghijklmnopqrstuvwxyz", 0x63a14d5f);
882 try testExpect(H, 0, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 0x9c285e64);
883 try testExpect(H, 0, "12345678901234567890123456789012345678901234567890123456789012345678901234567890", 0x9c05f475);
884}
885
886test "xxhash32 smhasher" {
887 const Test = struct {
888 fn do() !void {
889 try expectEqual(verify.smhasher(XxHash32.hash), 0xBA88B743);
890 }
891 };
892 try Test.do();
893 @setEvalBranchQuota(85000);
894 comptime try Test.do();
895}
896
897test "xxhash32 iterative api" {
898 const Test = struct {
899 fn do() !void {
900 try verify.iterativeApi(XxHash32);
901 }
902 };
903 try Test.do();
904 @setEvalBranchQuota(30000);
905 comptime try Test.do();
906}