lib/simd/src/hash.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const arithmetic = @import("arithmetic.zig");
3 const random = @import("random.zig");
4 const shift = @import("shift.zig");
5 const tag = @import("tag.zig");
6
7 pub fn lemireMod(input: u32, range: u32) u32 {
8 std.debug.assert(range != 0);
9 const reduced: u32 = @truncate((@as(u64, input) * @as(u64, range)) >> 32);
10 std.debug.assert(reduced < range);
11 return reduced;
12 }
13
14 test "Highway Lemire reduction scales the full u32 domain into range" {
15 try std.testing.expectEqual(@as(u32, 0), lemireMod(0, 37));
16 try std.testing.expectEqual(@as(u32, 18), lemireMod(0x8000_0000, 37));
17 try std.testing.expectEqual(@as(u32, 36), lemireMod(std.math.maxInt(u32), 37));
18 try std.testing.expectEqual(@as(u32, 0), lemireMod(std.math.maxInt(u32), 1));
19 }
20
21 pub fn MaskedWeakTwoMul(comptime bits: usize) type {
22 validateBits(u32, bits);
23 return struct {
24 key_value: u32 = 0,
25
26 const Self = @This();
27 pub const Lane: type = u32;
28 pub const mask: u32 = maskValue(u32, bits);
29
30 pub fn init() Self {
31 return .{};
32 }
33
34 pub fn initKey(key_value: u32) Self {
35 assertMasked(u32, bits, key_value);
36 return .{ .key_value = key_value };
37 }
38
39 pub fn initSeed(engine: *const random.AesCtrEngine, seed: u64) Self {
40 return .{ .key_value = maybeMask(u32, bits, @truncate(engine.generate(seed, 0))) };
41 }
42
43 pub fn hash(self: Self, input: u32) u32 {
44 assertMasked(u32, bits, input);
45 var result = input ^ self.key_value;
46 result ^= result >> 16;
47 result *%= 0x21f0_aaad;
48 result = maybeMask(u32, bits, result);
49 result ^= result >> 15;
50 result *%= 0xf35a_2d97;
51 result = maybeMask(u32, bits, result);
52 result ^= result >> 15;
53 assertMasked(u32, bits, result);
54 return result;
55 }
56
57 pub fn oneVec(self: Self, comptime D: type, input: D.Vector) D.Vector {
58 requireTag(D, u32);
59 assertMaskedVector(D, bits, input);
60 var result = input ^ @as(D.Vector, @splat(self.key_value));
61 result ^= shift.shiftRight(D, 16, result);
62 result = arithmetic.mul(D, result, @splat(0x21f0_aaad));
63 result = maybeMaskVector(D, bits, result);
64 result ^= shift.shiftRight(D, 15, result);
65 result = arithmetic.mul(D, result, @splat(0xf35a_2d97));
66 result = maybeMaskVector(D, bits, result);
67 result ^= shift.shiftRight(D, 15, result);
68 assertMaskedVector(D, bits, result);
69 return result;
70 }
71
72 pub fn twoVec(self: Self, comptime D: type, first: *D.Vector, second: *D.Vector) void {
73 first.* = self.oneVec(D, first.*);
74 second.* = self.oneVec(D, second.*);
75 }
76 };
77 }
78
79 pub const WeakTwoMul = MaskedWeakTwoMul(32);
80
81 pub fn MaskedTriple32(comptime bits: usize) type {
82 validateBits(u32, bits);
83 return struct {
84 key_value: u32 = 0,
85
86 const Self = @This();
87 pub const Lane: type = u32;
88 pub const mask: u32 = maskValue(u32, bits);
89
90 pub fn init() Self {
91 return .{};
92 }
93
94 pub fn initKey(key_value: u32) Self {
95 assertMasked(u32, bits, key_value);
96 return .{ .key_value = key_value };
97 }
98
99 pub fn initSeed(engine: *const random.AesCtrEngine, seed: u64) Self {
100 return .{ .key_value = maybeMask(u32, bits, @truncate(engine.generate(seed, 0))) };
101 }
102
103 pub fn key(self: Self) u32 {
104 return self.key_value;
105 }
106
107 pub fn hash(self: Self, input: u32) u32 {
108 assertMasked(u32, bits, input);
109 var result = input ^ self.key_value;
110 result ^= result >> 17;
111 result *%= 0xed5a_d4bb;
112 result = maybeMask(u32, bits, result);
113 result ^= result >> 11;
114 result *%= 0xac4c_1b51;
115 result = maybeMask(u32, bits, result);
116 result ^= result >> 15;
117 result *%= 0x3184_8bab;
118 result = maybeMask(u32, bits, result);
119 result ^= result >> 14;
120 assertMasked(u32, bits, result);
121 return result;
122 }
123
124 pub fn oneVec(self: Self, comptime D: type, input: D.Vector) D.Vector {
125 requireTag(D, u32);
126 assertMaskedVector(D, bits, input);
127 var result = input ^ @as(D.Vector, @splat(self.key_value));
128 result ^= shift.shiftRight(D, 17, result);
129 result = arithmetic.mul(D, result, @splat(0xed5a_d4bb));
130 result = maybeMaskVector(D, bits, result);
131 result ^= shift.shiftRight(D, 11, result);
132 result = arithmetic.mul(D, result, @splat(0xac4c_1b51));
133 result = maybeMaskVector(D, bits, result);
134 result ^= shift.shiftRight(D, 15, result);
135 result = arithmetic.mul(D, result, @splat(0x3184_8bab));
136 result = maybeMaskVector(D, bits, result);
137 result ^= shift.shiftRight(D, 14, result);
138 assertMaskedVector(D, bits, result);
139 return result;
140 }
141
142 pub fn twoVec(self: Self, comptime D: type, first: *D.Vector, second: *D.Vector) void {
143 first.* = self.oneVec(D, first.*);
144 second.* = self.oneVec(D, second.*);
145 }
146 };
147 }
148
149 pub const Triple32 = MaskedTriple32(32);
150
151 pub fn MaskedMoremur(comptime bits: usize) type {
152 validateBits(u64, bits);
153 return struct {
154 key_value: u64 = 0,
155
156 const Self = @This();
157 pub const Lane: type = u64;
158 pub const mask: u64 = maskValue(u64, bits);
159
160 pub fn init() Self {
161 return .{};
162 }
163
164 pub fn initKey(key_value: u64) Self {
165 assertMasked(u64, bits, key_value);
166 return .{ .key_value = key_value };
167 }
168
169 pub fn initSeed(engine: *const random.AesCtrEngine, seed: u64) Self {
170 return .{ .key_value = maybeMask(u64, bits, engine.generate(seed, 0)) };
171 }
172
173 pub fn key(self: Self) u64 {
174 return self.key_value;
175 }
176
177 pub fn hash(self: Self, input: u64) u64 {
178 assertMasked(u64, bits, input);
179 var result = input ^ self.key_value;
180 result ^= result >> 27;
181 result *%= 0x3c79_ac49_2ba7_b653;
182 result = maybeMask(u64, bits, result);
183 result ^= result >> 33;
184 result *%= 0x1c69_b3f7_4ac4_ae35;
185 result = maybeMask(u64, bits, result);
186 result ^= result >> 27;
187 assertMasked(u64, bits, result);
188 return result;
189 }
190
191 pub fn oneVec(self: Self, comptime D: type, input: D.Vector) D.Vector {
192 requireTag(D, u64);
193 assertMaskedVector(D, bits, input);
194 var result = input ^ @as(D.Vector, @splat(self.key_value));
195 result ^= shift.shiftRight(D, 27, result);
196 result = arithmetic.mul(D, result, @splat(0x3c79_ac49_2ba7_b653));
197 result = maybeMaskVector(D, bits, result);
198 result ^= shift.shiftRight(D, 33, result);
199 result = arithmetic.mul(D, result, @splat(0x1c69_b3f7_4ac4_ae35));
200 result = maybeMaskVector(D, bits, result);
201 result ^= shift.shiftRight(D, 27, result);
202 assertMaskedVector(D, bits, result);
203 return result;
204 }
205
206 pub fn twoVec(self: Self, comptime D: type, first: *D.Vector, second: *D.Vector) void {
207 first.* = self.oneVec(D, first.*);
208 second.* = self.oneVec(D, second.*);
209 }
210 };
211 }
212
213 pub const Moremur = MaskedMoremur(64);
214
215 pub fn hashArrayInPlace(comptime D: type, hash: anytype, inout: []D.Lane) void {
216 hashArray(D, hash, inout, inout);
217 }
218
219 pub fn hashArray(
220 comptime D: type,
221 hash: anytype,
222 input: []const D.Lane,
223 output: []D.Lane,
224 ) void {
225 std.debug.assert(input.len == output.len);
226 const lanes = D.lane_count;
227 var index: usize = 0;
228 var remaining = input.len;
229 while (remaining >= 4 * lanes) : ({
230 index += 4 * lanes;
231 remaining -= 4 * lanes;
232 }) {
233 var first = loadVector(D, input[index + 0 * lanes ..]);
234 var second = loadVector(D, input[index + 1 * lanes ..]);
235 var third = loadVector(D, input[index + 2 * lanes ..]);
236 var fourth = loadVector(D, input[index + 3 * lanes ..]);
237 hash.twoVec(D, &first, &second);
238 hash.twoVec(D, &third, &fourth);
239 storeVector(D, first, output[index + 0 * lanes ..]);
240 storeVector(D, second, output[index + 1 * lanes ..]);
241 storeVector(D, third, output[index + 2 * lanes ..]);
242 storeVector(D, fourth, output[index + 3 * lanes ..]);
243 }
244 while (remaining >= lanes) : ({
245 index += lanes;
246 remaining -= lanes;
247 }) {
248 const value = hash.oneVec(D, loadVector(D, input[index..]));
249 storeVector(D, value, output[index..]);
250 }
251 if (remaining != 0) {
252 var tail: [D.lane_count]D.Lane = @splat(0);
253 @memcpy(tail[0..remaining], input[index..]);
254 const value = hash.oneVec(D, @as(D.Vector, tail));
255 const result: [D.lane_count]D.Lane = value;
256 @memcpy(output[index..], result[0..remaining]);
257 }
258 }
259
260 pub fn fillRandomDistinct(comptime T: type, key: u32, output: []T) void {
261 requireDistinctLane(T);
262 if (@bitSizeOf(usize) > 32) {
263 std.debug.assert(output.len <= @as(usize, 1) << 32);
264 }
265 const permutation = Triple32.initKey(key);
266 for (output, 0..) |*value, index| {
267 value.* = @intCast(permutation.hash(@intCast(index)));
268 }
269 }
270
271 fn loadVector(comptime D: type, input: []const D.Lane) D.Vector {
272 std.debug.assert(input.len >= D.lane_count);
273 var lanes: [D.lane_count]D.Lane = undefined;
274 @memcpy(&lanes, input[0..D.lane_count]);
275 return lanes;
276 }
277
278 fn storeVector(comptime D: type, value: D.Vector, output: []D.Lane) void {
279 std.debug.assert(output.len >= D.lane_count);
280 const lanes: [D.lane_count]D.Lane = value;
281 @memcpy(output[0..D.lane_count], &lanes);
282 }
283
284 fn maskValue(comptime T: type, comptime bits: usize) T {
285 return if (bits == 0)
286 0
287 else if (bits == @bitSizeOf(T))
288 std.math.maxInt(T)
289 else
290 (@as(T, 1) << @intCast(bits)) - 1;
291 }
292
293 fn maybeMask(comptime T: type, comptime bits: usize, value: T) T {
294 return if (bits == @bitSizeOf(T)) value else value & maskValue(T, bits);
295 }
296
297 fn maybeMaskVector(comptime D: type, comptime bits: usize, value: D.Vector) D.Vector {
298 return if (bits == @bitSizeOf(D.Lane))
299 value
300 else
301 value & @as(D.Vector, @splat(maskValue(D.Lane, bits)));
302 }
303
304 fn assertMasked(comptime T: type, comptime bits: usize, value: T) void {
305 if (bits != @bitSizeOf(T)) std.debug.assert(value <= maskValue(T, bits));
306 }
307
308 fn assertMaskedVector(comptime D: type, comptime bits: usize, value: D.Vector) void {
309 if (bits != @bitSizeOf(D.Lane)) {
310 const mask: D.Vector = @splat(maskValue(D.Lane, bits));
311 std.debug.assert(@reduce(.And, value <= mask));
312 }
313 }
314
315 fn validateBits(comptime T: type, comptime bits: usize) void {
316 if (bits > @bitSizeOf(T)) @compileError("masked hash bits exceed lane width");
317 }
318
319 fn requireTag(comptime D: type, comptime T: type) void {
320 if (comptime D.Lane != T) @compileError("hash tag lane type mismatch");
321 }
322
323 fn requireDistinctLane(comptime T: type) void {
324 switch (@typeInfo(T)) {
325 .int => |info| {
326 if (info.signedness != .unsigned or info.bits < 32) {
327 @compileError("distinct hash outputs require unsigned lanes of at least 32 bits");
328 }
329 },
330 else => @compileError("distinct hash outputs require unsigned integer lanes"),
331 }
332 }
333
334 test "Highway hash scalar and vector paths agree lane by lane" {
335 const engine = random.AesCtrEngine.initDeterministic();
336 const D32 = tag.FixedTag(u32, 8);
337 const D64 = tag.FixedTag(u64, 4);
338 const triple = Triple32.initSeed(&engine, 7);
339 const moremur = Moremur.initSeed(&engine, 9);
340 const input32: D32.Vector = .{ 0, 1, 2, 3, 0x1234_5678, 0xffff_ffff, 77, 91 };
341 const input64: D64.Vector = .{ 0, 1, 0x1234_5678_9abc_def0, 0xffff_ffff_ffff_ffff };
342 const input32_lanes: [D32.lane_count]u32 = input32;
343 const input64_lanes: [D64.lane_count]u64 = input64;
344 const output32: [D32.lane_count]u32 = triple.oneVec(D32, input32);
345 const output64: [D64.lane_count]u64 = moremur.oneVec(D64, input64);
346 for (input32_lanes, output32) |input, output| {
347 try std.testing.expectEqual(triple.hash(input), output);
348 }
349 for (input64_lanes, output64) |input, output| {
350 try std.testing.expectEqual(moremur.hash(input), output);
351 }
352 var first = input32;
353 var second = input32 +% @as(D32.Vector, @splat(11));
354 const expected_first = triple.oneVec(D32, first);
355 const expected_second = triple.oneVec(D32, second);
356 triple.twoVec(D32, &first, &second);
357 try std.testing.expect(@reduce(.And, first == expected_first));
358 try std.testing.expect(@reduce(.And, second == expected_second));
359 }
360
361 test "Highway AVX2 keyed hash oracle matches exactly" {
362 const engine = random.AesCtrEngine.initDeterministic();
363 const weak = WeakTwoMul.initKey(0x1234_5678);
364 const triple = Triple32.initKey(0x1234_5678);
365 const moremur = Moremur.initSeed(&engine, 7);
366 const input32 = [_]u32{ 0, 1, 2, 3, 0x1234_5678, 0xffff_ffff, 77, 91 };
367 const input64 = [_]u64{ 0, 1, 0x1234_5678_9abc_def0, 0xffff_ffff_ffff_ffff };
368 const weak_expected = [_]u32{
369 0x96e6_76bd,
370 0x2634_7ffd,
371 0x2135_26e1,
372 0xe0f5_ee5a,
373 0,
374 0x1f4b_2c03,
375 0xe7b2_d7ae,
376 0xf79d_2c26,
377 };
378 const triple_expected = [_]u32{
379 0xfac9_70ff,
380 0x603a_31eb,
381 0x531f_8519,
382 0xac2e_592d,
383 0,
384 0x8414_acc4,
385 0xc6e3_2b94,
386 0x00df_8b80,
387 };
388 const moremur_expected = [_]u64{
389 0xd451_6cbf_6f1f_b72a,
390 0x902e_cf3f_1199_340a,
391 0x2e51_df48_8121_df97,
392 0x5b31_dff9_dfb3_9f71,
393 };
394 try std.testing.expectEqual(@as(u64, 0xf0ea_ad2f_c4a2_c3e1), moremur.key());
395 for (input32, weak_expected) |input, expected| {
396 try std.testing.expectEqual(expected, weak.hash(input));
397 }
398 for (input32, triple_expected) |input, expected| {
399 try std.testing.expectEqual(expected, triple.hash(input));
400 }
401 for (input64, moremur_expected) |input, expected| {
402 try std.testing.expectEqual(expected, moremur.hash(input));
403 }
404 const masked_weak = MaskedWeakTwoMul(13).initSeed(&engine, 3);
405 const masked_triple = MaskedTriple32(13).initSeed(&engine, 5);
406 const masked_moremur = MaskedMoremur(47).initSeed(&engine, 9);
407 try std.testing.expectEqual(@as(u32, 0x1e42), masked_triple.key());
408 try std.testing.expectEqual(@as(u32, 0x10ed), masked_weak.hash(0x1234));
409 try std.testing.expectEqual(@as(u32, 0x0b10), masked_triple.hash(0x1234));
410 try std.testing.expectEqual(@as(u64, 0x1de5_1286_7cff), masked_moremur.hash(0x1234_5678_9ab));
411 var tail = [_]u32{ 3, 20, 37, 54, 71, 88, 105, 122, 139, 156, 173, 190, 207 };
412 hashArrayInPlace(tag.FixedTag(u32, 8), triple, &tail);
413 try std.testing.expectEqual(
414 [_]u32{
415 0xac2e_592d,
416 0xcd31_1a0a,
417 0xdaa8_653e,
418 0x7962_6834,
419 0x612e_c03a,
420 0x9412_7d8c,
421 0x2a72_c1ed,
422 0x6417_39d8,
423 0xc56a_7ac6,
424 0x4d0f_5ada,
425 0x4e17_8eab,
426 0x5473_f841,
427 0x11fb_5ecd,
428 },
429 tail,
430 );
431 }
432
433 test "Highway masked hashes remain bijections on a small complete domain" {
434 const engine = random.AesCtrEngine.initDeterministic();
435 try expectBijection13(MaskedWeakTwoMul(13).initSeed(&engine, 3));
436 try expectBijection13(MaskedTriple32(13).initSeed(&engine, 5));
437 try expectBijection13(MaskedMoremur(13).initSeed(&engine, 7));
438 }
439
440 test "Highway masked hashes retain their declared ranges" {
441 const engine = random.AesCtrEngine.initDeterministic();
442 try expectMaskedSamples(MaskedWeakTwoMul(1).initSeed(&engine, 1), &engine);
443 try expectMaskedSamples(MaskedWeakTwoMul(31).initSeed(&engine, 2), &engine);
444 try expectMaskedSamples(MaskedTriple32(7).initSeed(&engine, 3), &engine);
445 try expectMaskedSamples(MaskedTriple32(31).initSeed(&engine, 4), &engine);
446 try expectMaskedSamples(MaskedMoremur(1).initSeed(&engine, 5), &engine);
447 try expectMaskedSamples(MaskedMoremur(63).initSeed(&engine, 6), &engine);
448 }
449
450 test "Highway hash arrays preserve scalar order through full vectors and tails" {
451 const engine = random.AesCtrEngine.initDeterministic();
452 const D32 = tag.FixedTag(u32, 8);
453 const D64 = tag.FixedTag(u64, 4);
454 const triple = Triple32.initSeed(&engine, 11);
455 const moremur = Moremur.initSeed(&engine, 13);
456 var input32: [73]u32 = undefined;
457 var output32: [73]u32 = undefined;
458 for (&input32, 0..) |*value, index| value.* = @intCast(index * 17 + 3);
459 hashArray(D32, triple, &input32, &output32);
460 for (input32, output32) |input, output| try std.testing.expectEqual(triple.hash(input), output);
461 hashArrayInPlace(D32, triple, &input32);
462 try std.testing.expectEqualSlices(u32, &output32, &input32);
463 var input64: [39]u64 = undefined;
464 var output64: [39]u64 = undefined;
465 for (&input64, 0..) |*value, index| {
466 value.* = @as(u64, @intCast(index)) * 0x1_0000_0001 + 9;
467 }
468 hashArray(D64, moremur, &input64, &output64);
469 for (input64, output64) |input, output| {
470 try std.testing.expectEqual(moremur.hash(input), output);
471 }
472 }
473
474 test "Highway hash edge cases remain nontrivial and seed separated" {
475 const engine = random.AesCtrEngine.initDeterministic();
476 const triple = Triple32.initSeed(&engine, 0);
477 const other_triple = Triple32.initSeed(&engine, 1);
478 const moremur = Moremur.initSeed(&engine, 0);
479 const other_moremur = Moremur.initSeed(&engine, 1);
480 try std.testing.expect(triple.hash(0) != 0);
481 try std.testing.expect(triple.hash(0) != triple.hash(1));
482 try std.testing.expect(triple.hash(0xffff_ffff) != 0);
483 try std.testing.expect(triple.hash(42) != other_triple.hash(42));
484 try std.testing.expect(moremur.hash(0) != 0);
485 try std.testing.expect(moremur.hash(0) != moremur.hash(1));
486 try std.testing.expect(moremur.hash(0xffff_ffff_ffff_ffff) != 0);
487 try std.testing.expect(moremur.hash(42) != other_moremur.hash(42));
488 for (0..1000) |input| {
489 const value: u32 = @intCast(input);
490 try std.testing.expect(triple.hash(value) != triple.hash(value + 1));
491 const large = @as(u64, 1) << 40;
492 try std.testing.expect(moremur.hash(large + input) != moremur.hash(large + input + 1));
493 }
494 try std.testing.expectEqual(@as(u32, 0), MaskedTriple32(0).initKey(0).hash(0));
495 try std.testing.expectEqual(@as(u64, 0), MaskedMoremur(0).initKey(0).hash(0));
496 }
497
498 test "Highway Triple32 avalanche and output bits remain balanced" {
499 const engine = random.AesCtrEngine.initDeterministic();
500 const hash = Triple32.initSeed(&engine, 0);
501 var generator = random.Xoshiro.init(0x4841_5348_5445_5354);
502 const avalanche_trials: u32 = 2000;
503 var flip_counts: [32][32]u32 = @splat(@splat(0));
504 for (0..avalanche_trials) |_| {
505 const input: u32 = @truncate(generator.next());
506 const baseline = hash.hash(input);
507 for (0..32) |input_bit| {
508 const changed = hash.hash(input ^ (@as(u32, 1) << @intCast(input_bit)));
509 const difference = baseline ^ changed;
510 for (0..32) |output_bit| {
511 if (difference & (@as(u32, 1) << @intCast(output_bit)) != 0) {
512 flip_counts[input_bit][output_bit] += 1;
513 }
514 }
515 }
516 }
517 for (flip_counts) |row| {
518 for (row) |count| {
519 try std.testing.expect(count >= avalanche_trials * 35 / 100);
520 try std.testing.expect(count <= avalanche_trials * 65 / 100);
521 }
522 }
523 const bias_trials: u32 = 20_000;
524 var one_counts: [32]u32 = @splat(0);
525 for (0..bias_trials) |_| {
526 const output = hash.hash(@truncate(generator.next()));
527 for (0..32) |bit| {
528 if (output & (@as(u32, 1) << @intCast(bit)) != 0) one_counts[bit] += 1;
529 }
530 }
531 for (one_counts) |count| {
532 try std.testing.expect(count >= bias_trials * 48 / 100);
533 try std.testing.expect(count <= bias_trials * 52 / 100);
534 }
535 }
536
537 test "Highway distinct counter fill widens the same Triple32 permutation" {
538 var narrow: [257]u32 = undefined;
539 var wide: [257]u64 = undefined;
540 fillRandomDistinct(u32, 0x1234_5678, &narrow);
541 fillRandomDistinct(u64, 0x1234_5678, &wide);
542 for (narrow, wide, 0..) |value, widened, index| {
543 try std.testing.expectEqual(@as(u64, value), widened);
544 for (narrow[0..index]) |prior| try std.testing.expect(value != prior);
545 }
546 }
547
548 fn expectBijection13(hash: anytype) !void {
549 var seen: [1 << 13]bool = @splat(false);
550 for (0..seen.len) |input| {
551 const output: usize = @intCast(hash.hash(@intCast(input)));
552 try std.testing.expect(output < seen.len);
553 try std.testing.expect(!seen[output]);
554 seen[output] = true;
555 }
556 for (seen) |value| try std.testing.expect(value);
557 }
558
559 fn expectMaskedSamples(hash: anytype, engine: *const random.AesCtrEngine) !void {
560 const Hash = @TypeOf(hash);
561 var stream = random.RngStream.init(engine, 101);
562 for (0..1000) |_| {
563 const input: Hash.Lane = @truncate(stream.next() & Hash.mask);
564 try std.testing.expect(hash.hash(input) <= Hash.mask);
565 }
566 }