lib/simd/src/shardmul.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const builtin = @import("builtin");
3 const hash_mod = @import("hash.zig");
4 const multiply = @import("multiply.zig");
5 const random = @import("random.zig");
6 const shift = @import("shift.zig");
7 const table = @import("table.zig");
8
9 pub const bucket_count: usize = 16;
10 pub const feistel_candidate_count: usize = 9;
11 pub const max_attempts_per_bucket: usize = 150_000;
12
13 pub const ShardMulData = struct {
14 table: [bucket_count]u32 = @splat(0),
15 keys: [4]u32 = @splat(0),
16 attempts: [bucket_count]u32 = @splat(0),
17 };
18
19 pub const ShardMul = struct {
20 table: [bucket_count]u32,
21 rounds: [4]hash_mod.WeakTwoMul,
22
23 const Self = @This();
24
25 pub const FeistelPair = struct {
26 left: u32,
27 right: u32,
28 };
29
30 pub fn init(data: ShardMulData) Self {
31 return .{
32 .table = data.table,
33 .rounds = .{
34 hash_mod.WeakTwoMul.initKey(data.keys[0]),
35 hash_mod.WeakTwoMul.initKey(data.keys[1]),
36 hash_mod.WeakTwoMul.initKey(data.keys[2]),
37 hash_mod.WeakTwoMul.initKey(data.keys[3]),
38 },
39 };
40 }
41
42 pub fn isEmpty(self: Self) bool {
43 if (self.table[0] == 0) return true;
44 for (self.table) |entry| {
45 if (entry == 0) @panic("ShardMul table contains a zero multiplier");
46 }
47 return false;
48 }
49
50 pub fn feistel(self: Self, input: u64) FeistelPair {
51 var left: u32 = @truncate(input);
52 var right: u32 = @truncate(input >> 32);
53 left ^= self.rounds[0].hash(right);
54 right ^= self.rounds[1].hash(left);
55 left ^= self.rounds[2].hash(right);
56 right ^= self.rounds[3].hash(left);
57 return .{ .left = left, .right = right };
58 }
59
60 pub fn bucketIndex(left: u32) u32 {
61 return left >> 28;
62 }
63
64 pub fn lookupMul(self: Self, bucket: u32) u32 {
65 std.debug.assert(bucket < bucket_count);
66 return self.table[bucket];
67 }
68
69 pub fn hash(self: Self, input: u64) u32 {
70 std.debug.assert(!self.isEmpty());
71 const pair = self.feistel(input);
72 return mulAndXorScalar(pair.left, pair.right, self.lookupMul(bucketIndex(pair.left)));
73 }
74
75 pub fn oneVec(self: Self, comptime D64: type, input: D64.Vector) D64.rebind(u32).Vector {
76 requireTag(D64, u64);
77 std.debug.assert(!self.isEmpty());
78 const D32 = D64.rebind(u32);
79 var left: D32.Vector = undefined;
80 var right: D32.Vector = undefined;
81 inline for (0..D64.lane_count) |lane| {
82 left[lane] = @truncate(input[lane]);
83 right[lane] = @truncate(input[lane] >> 32);
84 }
85 return self.resultFromFeistel(D32, self.feistelVector(D32, left, right));
86 }
87
88 pub fn twoVec(
89 self: Self,
90 comptime D32: type,
91 first: D32.repartition(u64).Vector,
92 second: D32.repartition(u64).Vector,
93 ) D32.Vector {
94 requireTag(D32, u32);
95 if (D32.lane_count < 2) @compileError("ShardMul twoVec requires at least two u32 lanes");
96 std.debug.assert(!self.isEmpty());
97 const D64 = D32.repartition(u64);
98 var left: D32.Vector = undefined;
99 var right: D32.Vector = undefined;
100 inline for (0..D64.lane_count) |lane| {
101 left[lane] = @truncate(first[lane]);
102 right[lane] = @truncate(first[lane] >> 32);
103 left[D64.lane_count + lane] = @truncate(second[lane]);
104 right[D64.lane_count + lane] = @truncate(second[lane] >> 32);
105 }
106 return self.resultFromFeistel(D32, self.feistelVector(D32, left, right));
107 }
108
109 pub fn mulAndXor(
110 comptime D32: type,
111 left: D32.Vector,
112 right: D32.Vector,
113 muls: D32.Vector,
114 ) D32.Vector {
115 requireTag(D32, u32);
116 const D16 = D32.repartition(u16);
117 const products = multiply.mulHigh(
118 D16,
119 @as(D16.Vector, @bitCast(right)),
120 @as(D16.Vector, @bitCast(muls)),
121 );
122 const mixed: D32.Vector = @bitCast(products);
123 return left ^ (mixed & @as(D32.Vector, @splat(0x0fff_ffff)));
124 }
125
126 fn feistelVector(
127 self: Self,
128 comptime D32: type,
129 initial_left: D32.Vector,
130 initial_right: D32.Vector,
131 ) VectorPair(D32) {
132 var left = initial_left;
133 var right = initial_right;
134 left ^= self.rounds[0].oneVec(D32, right);
135 right ^= self.rounds[1].oneVec(D32, left);
136 left ^= self.rounds[2].oneVec(D32, right);
137 right ^= self.rounds[3].oneVec(D32, left);
138 return .{ .left = left, .right = right };
139 }
140
141 fn resultFromFeistel(self: Self, comptime D32: type, pair: VectorPair(D32)) D32.Vector {
142 const buckets = shift.shiftRight(D32, 28, pair.left);
143 const muls = table.lookup16(D32, &self.table, buckets);
144 return mulAndXor(D32, pair.left, pair.right, muls);
145 }
146 };
147
148 pub const ShardMulBuildError = error{
149 CapacityExceeded,
150 PlanMismatch,
151 ScratchTooSmall,
152 };
153
154 pub const ShardMulPlan = struct {
155 best_seed: u64,
156 key_counts: [bucket_count]usize,
157 extra_counts: [bucket_count]usize,
158 offsets: [bucket_count + 1]usize,
159 slot_count: usize,
160 scratch_len: usize,
161
162 const Self = @This();
163
164 pub fn inspect(keys: []const u64, extra_outputs: []const u32) ShardMulBuildError!Self {
165 const total = std.math.add(usize, keys.len, extra_outputs.len) catch
166 return error.CapacityExceeded;
167 if (total > std.math.maxInt(u32)) return error.CapacityExceeded;
168 const engine = random.AesCtrEngine.initDeterministic();
169 var extra_counts: [bucket_count]usize = @splat(0);
170 for (extra_outputs) |value| extra_counts[value >> 28] += 1;
171
172 var best_seed: u64 = feistel_candidate_count;
173 var best_ratio: f32 = std.math.inf(f32);
174 for (0..feistel_candidate_count) |candidate| {
175 const candidate_seed: u64 = @intCast(candidate);
176 const shard = ShardMul.init(.{ .keys = makeFeistelKeys(&engine, candidate_seed) });
177 var counts = extra_counts;
178 for (keys) |key| counts[ShardMul.bucketIndex(shard.feistel(key).left)] += 1;
179 var minimum = counts[0];
180 var maximum = counts[0];
181 for (counts[1..]) |count| {
182 minimum = @min(minimum, count);
183 maximum = @max(maximum, count);
184 }
185 if (minimum == 0) continue;
186 const ratio = @as(f32, @floatFromInt(maximum)) /
187 @as(f32, @floatFromInt(minimum));
188 if (ratio < best_ratio) {
189 best_ratio = ratio;
190 best_seed = candidate_seed;
191 }
192 }
193
194 const shard = ShardMul.init(.{ .keys = makeFeistelKeys(&engine, best_seed) });
195 var key_counts: [bucket_count]usize = @splat(0);
196 for (keys) |key| key_counts[ShardMul.bucketIndex(shard.feistel(key).left)] += 1;
197 var offsets: [bucket_count + 1]usize = @splat(0);
198 var maximum_bucket_size: usize = 0;
199 for (0..bucket_count) |bucket| {
200 const bucket_size = std.math.add(
201 usize,
202 key_counts[bucket],
203 extra_counts[bucket],
204 ) catch return error.CapacityExceeded;
205 if (bucket_size > @as(usize, 1) << 28) return error.CapacityExceeded;
206 maximum_bucket_size = @max(maximum_bucket_size, bucket_size);
207 offsets[bucket + 1] = std.math.add(usize, offsets[bucket], bucket_size) catch
208 return error.CapacityExceeded;
209 }
210 std.debug.assert(offsets[bucket_count] == total);
211 const slot_count = try slotsFor(maximum_bucket_size);
212 const slot_u64 = std.math.divCeil(usize, slot_count, 2) catch unreachable;
213 const scratch_len = std.math.add(usize, total, slot_u64) catch
214 return error.CapacityExceeded;
215 return .{
216 .best_seed = best_seed,
217 .key_counts = key_counts,
218 .extra_counts = extra_counts,
219 .offsets = offsets,
220 .slot_count = slot_count,
221 .scratch_len = scratch_len,
222 };
223 }
224
225 pub fn build(
226 self: Self,
227 scratch: []u64,
228 keys: []const u64,
229 extra_outputs: []const u32,
230 ) ShardMulBuildError!ShardMulData {
231 if (scratch.len < self.scratch_len) return error.ScratchTooSmall;
232 const total = std.math.add(usize, keys.len, extra_outputs.len) catch
233 return error.CapacityExceeded;
234 if (total != self.offsets[bucket_count]) return error.PlanMismatch;
235 const engine = random.AesCtrEngine.initDeterministic();
236 const feistel_keys = makeFeistelKeys(&engine, self.best_seed);
237 const shard = ShardMul.init(.{ .keys = feistel_keys });
238 const records = scratch[0..total];
239 const slot_bytes = std.mem.sliceAsBytes(scratch[total..self.scratch_len]);
240 const all_slots = std.mem.bytesAsSlice(u32, slot_bytes)[0..self.slot_count];
241 var key_cursor = self.offsets[0..bucket_count].*;
242 var extra_cursor: [bucket_count]usize = undefined;
243 for (0..bucket_count) |bucket| {
244 extra_cursor[bucket] = self.offsets[bucket] + self.key_counts[bucket];
245 }
246 for (keys) |key| {
247 const pair = shard.feistel(key);
248 const bucket = ShardMul.bucketIndex(pair.left);
249 if (key_cursor[bucket] >= self.offsets[bucket] + self.key_counts[bucket]) {
250 return error.PlanMismatch;
251 }
252 records[key_cursor[bucket]] = encodePair(pair);
253 key_cursor[bucket] += 1;
254 }
255 for (extra_outputs) |value| {
256 const bucket = value >> 28;
257 if (extra_cursor[bucket] >= self.offsets[bucket + 1]) return error.PlanMismatch;
258 records[extra_cursor[bucket]] = value;
259 extra_cursor[bucket] += 1;
260 }
261 for (0..bucket_count) |bucket| {
262 if (key_cursor[bucket] != self.offsets[bucket] + self.key_counts[bucket] or
263 extra_cursor[bucket] != self.offsets[bucket + 1])
264 {
265 return error.PlanMismatch;
266 }
267 }
268
269 var data = ShardMulData{ .keys = feistel_keys };
270 for (0..bucket_count) |bucket| {
271 const bucket_size = self.key_counts[bucket] + self.extra_counts[bucket];
272 const slots = all_slots[0..try slotsFor(bucket_size)];
273 const first = self.offsets[bucket];
274 const key_records = records[first .. first + self.key_counts[bucket]];
275 const extras = records[first + self.key_counts[bucket] .. self.offsets[bucket + 1]];
276 for (0..max_attempts_per_bucket) |attempt| {
277 @memset(slots, 0);
278 var stream = random.RngStream.init(
279 &engine,
280 multiplierSeed(self.best_seed, bucket, attempt),
281 );
282 const muls = makeMultiplierPair(&stream);
283 var collision = false;
284 for (key_records) |encoded| {
285 const pair = decodePair(encoded);
286 const output = mulAndXorScalar(pair.left, pair.right, muls);
287 if (!insertUnique(slots, output)) {
288 collision = true;
289 break;
290 }
291 }
292 if (!collision) {
293 for (extras) |encoded| {
294 if (!insertUnique(slots, @truncate(encoded))) {
295 collision = true;
296 break;
297 }
298 }
299 }
300 if (!collision) {
301 data.table[bucket] = muls;
302 data.attempts[bucket] = @intCast(attempt + 1);
303 break;
304 }
305 }
306 if (data.table[bucket] == 0) return .{};
307 }
308 return data;
309 }
310 };
311
312 pub fn shardMulScratchLen(
313 keys: []const u64,
314 extra_outputs: []const u32,
315 ) ShardMulBuildError!usize {
316 return (try ShardMulPlan.inspect(keys, extra_outputs)).scratch_len;
317 }
318
319 pub fn buildShardMul(
320 scratch: []u64,
321 keys: []const u64,
322 extra_outputs: []const u32,
323 ) ShardMulBuildError!ShardMulData {
324 const plan = try ShardMulPlan.inspect(keys, extra_outputs);
325 return plan.build(scratch, keys, extra_outputs);
326 }
327
328 pub fn makeShardMul(
329 scratch: []u64,
330 keys: []const u64,
331 extra_outputs: []const u32,
332 ) ShardMulBuildError!ShardMul {
333 return ShardMul.init(try buildShardMul(scratch, keys, extra_outputs));
334 }
335
336 fn VectorPair(comptime D: type) type {
337 return struct {
338 left: D.Vector,
339 right: D.Vector,
340 };
341 }
342
343 fn mulAndXorScalar(left: u32, right: u32, muls: u32) u32 {
344 const mul0 = muls & 0xffff;
345 const mul1 = muls >> 16;
346 const x0 = right & 0xffff;
347 const x1 = right >> 16;
348 const r0 = (x0 * mul0) >> 16;
349 const r1 = (x1 * mul1) >> 16;
350 return left ^ (((r1 & 0x0fff) << 16) | r0);
351 }
352
353 fn makeFeistelKeys(engine: *const random.AesCtrEngine, seed: u64) [4]u32 {
354 var keys: [4]u32 = undefined;
355 for (&keys, 0..) |*key, index| {
356 key.* = @truncate(engine.generate(4 * seed + index, 0));
357 }
358 return keys;
359 }
360
361 fn makeMultiplierPair(stream: *random.RngStream) u32 {
362 const initial: u32 = @truncate(stream.next());
363 const mul0 = (initial & 0xffff) | 0x8001;
364 var mul1 = (initial >> 16) | 0x8001;
365 while (mul1 == mul0) mul1 = @as(u32, @truncate(stream.next())) & 0xffff | 0x8001;
366 std.debug.assert(mul0 != mul1);
367 return (mul1 << 16) | mul0;
368 }
369
370 fn multiplierSeed(best_seed: u64, bucket: usize, attempt: usize) u64 {
371 return best_seed * bucket_count * max_attempts_per_bucket +
372 bucket * max_attempts_per_bucket + attempt + 0x9e37_79b9;
373 }
374
375 fn slotsFor(count: usize) ShardMulBuildError!usize {
376 if (count == 0) return 1;
377 const doubled = std.math.mul(usize, count, 2) catch return error.CapacityExceeded;
378 return std.math.ceilPowerOfTwo(usize, doubled) catch error.CapacityExceeded;
379 }
380
381 fn insertUnique(slots: []u32, value: u32) bool {
382 std.debug.assert(std.math.isPowerOfTwo(slots.len));
383 const payload = value & 0x0fff_ffff;
384 const marker = payload + 1;
385 var index: usize = @intCast((payload *% 0x9e37_79b1) & @as(u32, @intCast(slots.len - 1)));
386 for (0..slots.len) |_| {
387 if (slots[index] == 0) {
388 slots[index] = marker;
389 return true;
390 }
391 if (slots[index] == marker) return false;
392 index = (index + 1) & (slots.len - 1);
393 }
394 unreachable;
395 }
396
397 fn encodePair(pair: ShardMul.FeistelPair) u64 {
398 return @as(u64, pair.right) << 32 | pair.left;
399 }
400
401 fn decodePair(encoded: u64) ShardMul.FeistelPair {
402 return .{ .left = @truncate(encoded), .right = @truncate(encoded >> 32) };
403 }
404
405 fn requireTag(comptime D: type, comptime T: type) void {
406 if (comptime D.Lane != T) @compileError("ShardMul tag lane type mismatch");
407 }
408
409 test "Highway ShardMul scalar and vector queries agree" {
410 const tag = @import("tag.zig");
411 const D32 = tag.FixedTag(u32, 8);
412 const D64 = tag.FixedTag(u64, 4);
413 var data = ShardMulData{ .keys = .{ 0x1234_5678, 0x2345_6789, 0x3456_789a, 0x4567_89ab } };
414 for (&data.table, 0..) |*entry, index| {
415 const offset: u32 = @intCast(index * 2);
416 entry.* = ((0x9001 + offset) << 16) | (0x8001 + offset);
417 }
418 const shard = ShardMul.init(data);
419 try std.testing.expect(!shard.isEmpty());
420 const first: D64.Vector = .{ 0, 1, 0x1234_5678_9abc_def0, 0xffff_ffff_ffff_ffff };
421 const second: D64.Vector = .{ 17, 29, 0x4865_6c6c_6f20_576f, 0xc3a9_c3a0_c3bc_e282 };
422 const actual: [D32.lane_count]u32 = shard.twoVec(D32, first, second);
423 try std.testing.expectEqual(
424 [D32.lane_count]u32{
425 0x05cb_c28f,
426 0x3bb0_03f5,
427 0x5170_30fd,
428 0x2bbb_e45e,
429 0x8929_bb1a,
430 0x6146_891f,
431 0x0886_bd51,
432 0xa184_cae4,
433 },
434 actual,
435 );
436 for (@as([D64.lane_count]u64, first), 0..) |value, lane| {
437 try std.testing.expectEqual(shard.hash(value), actual[lane]);
438 }
439 for (@as([D64.lane_count]u64, second), 0..) |value, lane| {
440 try std.testing.expectEqual(shard.hash(value), actual[D64.lane_count + lane]);
441 }
442 const half: [D64.lane_count]u32 = shard.oneVec(D64, first);
443 for (@as([D64.lane_count]u64, first), half) |value, output| {
444 try std.testing.expectEqual(shard.hash(value), output);
445 }
446 }
447
448 test "Highway ShardMul single-worker builder oracle matches exactly" {
449 var keys: [1024]u64 = undefined;
450 var extras: [128]u32 = undefined;
451 for (&keys, 0..) |*key, index| {
452 key.* = @as(u64, @intCast(index)) *% 0x9e37_79b9_7f4a_7c15 +%
453 0x1234_5678_9abc_def0;
454 }
455 for (&extras, 0..) |*extra, index| {
456 extra.* = @as(u32, @intCast(index)) *% 0x9e37_79b1 +% 0x1357_9bdf;
457 }
458 const plan = try ShardMulPlan.inspect(&keys, &extras);
459 const scratch = try std.testing.allocator.alloc(u64, plan.scratch_len);
460 defer std.testing.allocator.free(scratch);
461 const data = try plan.build(scratch, &keys, &extras);
462 try std.testing.expectEqual(
463 [4]u32{ 0x3060_d0b5, 0x0b2d_cddf, 0xb5eb_7a83, 0xed2b_6bf4 },
464 data.keys,
465 );
466 try std.testing.expectEqual(
467 [bucket_count]u32{
468 0xf105_8109,
469 0xed8b_8d05,
470 0xd157_9813,
471 0xc907_ad69,
472 0xafe3_df3f,
473 0xc2a9_ff59,
474 0xb203_e48d,
475 0xee7f_bc3d,
476 0x8739_f43d,
477 0x950b_98bb,
478 0x927d_d2b7,
479 0xc031_802b,
480 0xb051_b9a9,
481 0xe2c9_8d73,
482 0xf821_8b21,
483 0xf907_baa7,
484 },
485 data.table,
486 );
487 const shard = ShardMul.init(data);
488 const expected = [8]u32{
489 0xee76_e3a9,
490 0x1a6b_3ea9,
491 0x557e_148f,
492 0x40df_2dbb,
493 0x3929_8336,
494 0x5e57_7a7a,
495 0xd60a_4f37,
496 0x8ef7_d963,
497 };
498 for (keys[0..expected.len], expected) |key, output| {
499 try std.testing.expectEqual(output, shard.hash(key));
500 }
501 }
502
503 test "Highway ShardMul builder produces collision-free outputs and excludes extras" {
504 const allocator = std.testing.allocator;
505 const key_count = if (builtin.mode == .debug) 12_000 else 300_000;
506 const extra_count = if (builtin.mode == .debug) 3000 else 80_000;
507 const keys = try allocator.alloc(u64, key_count);
508 defer allocator.free(keys);
509 const candidates = try allocator.alloc(u64, key_count * 3 / 2);
510 defer allocator.free(candidates);
511 try fillClusteredKeys(keys, candidates);
512 const extras = try allocator.alloc(u32, extra_count);
513 defer allocator.free(extras);
514 const engine = random.AesCtrEngine.initDeterministic();
515 random.fillRandom(u32, &engine, 0, extras);
516 std.mem.sort(u32, extras, {}, std.sort.asc(u32));
517 const distinct_extras = extras[0..uniquePrefixLen(u32, extras)];
518 const plan = try ShardMulPlan.inspect(keys, distinct_extras);
519 const scratch = try allocator.alloc(u64, plan.scratch_len);
520 defer allocator.free(scratch);
521 const data = try plan.build(scratch, keys, distinct_extras);
522 const shard = ShardMul.init(data);
523 try std.testing.expect(!shard.isEmpty());
524 const combined = try allocator.alloc(u32, key_count + distinct_extras.len);
525 defer allocator.free(combined);
526 for (keys, combined[0..key_count]) |key, *output| output.* = shard.hash(key);
527 @memcpy(combined[key_count..], distinct_extras);
528 std.mem.sort(u32, combined, {}, std.sort.asc(u32));
529 for (combined[1..], combined[0 .. combined.len - 1]) |current, previous| {
530 try std.testing.expect(current != previous);
531 }
532 }
533
534 test "Highway ShardMul builder remains collision-free for clustered keys" {
535 const allocator = std.testing.allocator;
536 const key_count = if (builtin.mode == .debug) 30_000 else 1_000_000;
537 const keys = try allocator.alloc(u64, key_count);
538 defer allocator.free(keys);
539 const candidates = try allocator.alloc(u64, key_count * 3 / 2);
540 defer allocator.free(candidates);
541 try fillClusteredKeys(keys, candidates);
542 const plan = try ShardMulPlan.inspect(keys, &.{});
543 const scratch = try allocator.alloc(u64, plan.scratch_len);
544 defer allocator.free(scratch);
545 const shard = ShardMul.init(try plan.build(scratch, keys, &.{}));
546 try std.testing.expect(!shard.isEmpty());
547 const outputs = try allocator.alloc(u32, key_count);
548 defer allocator.free(outputs);
549 for (keys, outputs) |key, *output| output.* = shard.hash(key);
550 std.mem.sort(u32, outputs, {}, std.sort.asc(u32));
551 try std.testing.expectEqual(key_count, uniquePrefixLen(u32, outputs));
552 }
553
554 test "Highway ShardMul plans enforce scratch and input distributions" {
555 const keys = [_]u64{ 1, 2, 3, 4, 5, 6, 7, 8 };
556 const extras = [_]u32{ 9, 10, 11 };
557 const plan = try ShardMulPlan.inspect(&keys, &extras);
558 const allocator = std.testing.allocator;
559 const scratch = try allocator.alloc(u64, plan.scratch_len);
560 defer allocator.free(scratch);
561 try std.testing.expectError(
562 error.ScratchTooSmall,
563 plan.build(scratch[0 .. scratch.len - 1], &keys, &extras),
564 );
565 try std.testing.expectError(error.PlanMismatch, plan.build(scratch, keys[0..7], &extras));
566 const empty = ShardMul.init(.{});
567 try std.testing.expect(empty.isEmpty());
568 }
569
570 fn fillClusteredKeys(output: []u64, candidates: []u64) !void {
571 std.debug.assert(candidates.len >= output.len * 3 / 2);
572 const patterns = [4]u64{
573 0x4865_6c6c_6f20_576f,
574 0x7468_655f_6b65_795f,
575 0xc3a9_c3a0_c3bc_e282,
576 0x6162_6364_6566_6747,
577 };
578 const engine = random.AesCtrEngine.initDeterministic();
579 var stream = random.RngStream.init(&engine, 0);
580 for (candidates, 0..) |*candidate, index| {
581 var bytes: [8]u8 = @bitCast(patterns[index % patterns.len]);
582 const mutation_count: usize = @intCast(1 + stream.next() % 5);
583 for (0..mutation_count) |_| {
584 const position: usize = @intCast(stream.next() % bytes.len);
585 bytes[position] = @intCast(0x20 + stream.next() % 213);
586 }
587 var key: u64 = @bitCast(bytes);
588 if (stream.next() % 4 == 0) key >>= 8;
589 candidate.* = key;
590 }
591 std.mem.sort(u64, candidates, {}, std.sort.asc(u64));
592 const distinct = uniquePrefixLen(u64, candidates);
593 try std.testing.expect(distinct >= output.len);
594 @memcpy(output, candidates[0..output.len]);
595 }
596
597 fn uniquePrefixLen(comptime T: type, values: []T) usize {
598 if (values.len == 0) return 0;
599 var count: usize = 1;
600 for (values[1..]) |value| {
601 if (value != values[count - 1]) {
602 values[count] = value;
603 count += 1;
604 }
605 }
606 return count;
607 }