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