lib/simd/src/algo.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const arithmetic = @import("arithmetic.zig");
3 const compact = @import("compact.zig");
4 const compare = @import("compare.zig");
5 const construct = @import("construct.zig");
6 const memory = @import("memory.zig");
7 const reduce = @import("reduce.zig");
8
9 pub fn fill(comptime D: type, output: []D.Lane, value: D.Lane) void {
10 const vector: D.Vector = @splat(value);
11 var index: usize = 0;
12 while (index + D.lane_count <= output.len) : (index += D.lane_count) {
13 memory.store(D, vector, output[index..]);
14 }
15 if (index != output.len) memory.storeN(D, vector, output[index..], output.len - index);
16 }
17
18 pub fn copy(comptime D: type, input: []const D.Lane, output: []D.Lane) void {
19 std.debug.assert(output.len >= input.len);
20 var index: usize = 0;
21 while (index + D.lane_count <= input.len) : (index += D.lane_count) {
22 memory.store(D, memory.load(D, input[index..]), output[index..]);
23 }
24 if (index != input.len) {
25 const remaining = input.len - index;
26 const value = memory.loadN(D, input[index..], remaining);
27 memory.storeN(D, value, output[index..input.len], remaining);
28 }
29 }
30
31 pub fn copyIf(
32 comptime D: type,
33 input: []const D.Lane,
34 output: []D.Lane,
35 predicate: anytype,
36 ) usize {
37 if (@sizeOf(D.Lane) == 1) @compileError("copyIf requires 16/32/64-bit lanes");
38 std.debug.assert(output.len >= input.len);
39 var input_index: usize = 0;
40 var output_index: usize = 0;
41 while (input_index + D.lane_count <= input.len) : (input_index += D.lane_count) {
42 const value = memory.load(D, input[input_index..]);
43 output_index += compact.compressBlendedStore(
44 D,
45 value,
46 predicate.call(D, value),
47 output[output_index..],
48 );
49 }
50 if (input_index != input.len) {
51 const remaining = input.len - input_index;
52 const value = memory.loadN(D, input[input_index..], remaining);
53 const mask = predicate.call(D, value) & construct.firstN(D, remaining);
54 output_index += compact.compressBlendedStore(D, value, mask, output[output_index..]);
55 }
56 std.debug.assert(output_index <= input.len);
57 return output_index;
58 }
59
60 pub fn count(comptime D: type, input: []const D.Lane, value: D.Lane) usize {
61 const broadcast: D.Vector = @splat(value);
62 var total: usize = 0;
63 var index: usize = 0;
64 while (index + D.lane_count <= input.len) : (index += D.lane_count) {
65 total += compare.countTrue(D, memory.load(D, input[index..]) == broadcast);
66 }
67 if (index != input.len) {
68 const remaining = input.len - index;
69 const matches = memory.loadN(D, input[index..], remaining) == broadcast;
70 total += compare.countTrue(D, matches & construct.firstN(D, remaining));
71 }
72 std.debug.assert(total <= input.len);
73 return total;
74 }
75
76 pub fn countIf(comptime D: type, input: []const D.Lane, predicate: anytype) usize {
77 var total: usize = 0;
78 var index: usize = 0;
79 while (index + D.lane_count <= input.len) : (index += D.lane_count) {
80 total += compare.countTrue(D, predicate.call(D, memory.load(D, input[index..])));
81 }
82 if (index != input.len) {
83 const remaining = input.len - index;
84 const matches = predicate.call(D, memory.loadN(D, input[index..], remaining));
85 total += compare.countTrue(D, matches & construct.firstN(D, remaining));
86 }
87 std.debug.assert(total <= input.len);
88 return total;
89 }
90
91 pub fn find(comptime D: type, input: []const D.Lane, value: D.Lane) usize {
92 const broadcast: D.Vector = @splat(value);
93 var index: usize = 0;
94 while (index + D.lane_count <= input.len) : (index += D.lane_count) {
95 const position = compare.findFirstTrue(D, memory.load(D, input[index..]) == broadcast);
96 if (position >= 0) return index + @as(usize, @intCast(position));
97 }
98 if (index != input.len) {
99 const remaining = input.len - index;
100 const loaded = memory.loadN(D, input[index..], remaining);
101 const matches = (loaded == broadcast) & construct.firstN(D, remaining);
102 const position = compare.findFirstTrue(D, matches);
103 if (position >= 0) return index + @as(usize, @intCast(position));
104 }
105 return input.len;
106 }
107
108 pub fn findIf(comptime D: type, input: []const D.Lane, predicate: anytype) usize {
109 var index: usize = 0;
110 while (index + D.lane_count <= input.len) : (index += D.lane_count) {
111 const value = memory.load(D, input[index..]);
112 const position = compare.findFirstTrue(D, predicate.call(D, value));
113 if (position >= 0) return index + @as(usize, @intCast(position));
114 }
115 if (index != input.len) {
116 const remaining = input.len - index;
117 const value = memory.loadN(D, input[index..], remaining);
118 const matches = predicate.call(D, value) & construct.firstN(D, remaining);
119 const position = compare.findFirstTrue(D, matches);
120 if (position >= 0) return index + @as(usize, @intCast(position));
121 }
122 return input.len;
123 }
124
125 pub fn equal(comptime D: type, left: []const D.Lane, right: []const D.Lane) bool {
126 requireInteger(D.Lane, "equal");
127 if (left.len != right.len) return false;
128 if (left.len <= D.lane_count) return std.mem.eql(D.Lane, left, right);
129 if (left.ptr == right.ptr) return true;
130 const last = left.len - D.lane_count;
131 var index: usize = 0;
132 while (index < last) : (index += D.lane_count) {
133 const first: D.Vector = left[index..][0..D.lane_count].*;
134 const second: D.Vector = right[index..][0..D.lane_count].*;
135 if (@reduce(.Or, first != second)) return false;
136 }
137 std.debug.assert(index >= last);
138 std.debug.assert(index - last < D.lane_count);
139 const first: D.Vector = left[last..][0..D.lane_count].*;
140 const second: D.Vector = right[last..][0..D.lane_count].*;
141 return !@reduce(.Or, first != second);
142 }
143
144 /// Returns whether every lane of `input` equals `value`, as
145 /// `std.mem.allEqual` does. Whole vectors compare with the broadcast value,
146 /// and the last vector overlaps lanes already compared. A span shorter than
147 /// a vector compares lane by lane.
148 pub fn allEqual(comptime D: type, input: []const D.Lane, value: D.Lane) bool {
149 if (input.len < D.lane_count) {
150 for (input) |lane| {
151 if (lane != value) return false;
152 }
153 return true;
154 }
155 const broadcast: D.Vector = @splat(value);
156 const last = input.len - D.lane_count;
157 var index: usize = 0;
158 while (index < last) : (index += D.lane_count) {
159 const lanes: D.Vector = input[index..][0..D.lane_count].*;
160 if (@reduce(.Or, lanes != broadcast)) return false;
161 }
162 std.debug.assert(index >= last);
163 std.debug.assert(index - last < D.lane_count);
164 const lanes: D.Vector = input[last..][0..D.lane_count].*;
165 return !@reduce(.Or, lanes != broadcast);
166 }
167
168 /// Returns the index of the first lane where two equal-length spans differ,
169 /// or their length when every lane agrees. Whole vectors compare first, and
170 /// the last vector overlaps lanes already known equal. A byte span shorter
171 /// than a vector compares eight bytes at a time the same way.
172 pub fn mismatch(comptime D: type, left: []const D.Lane, right: []const D.Lane) usize {
173 requireInteger(D.Lane, "mismatch");
174 std.debug.assert(left.len == right.len);
175 if (left.len >= D.lane_count) return vectorMismatch(D, left, right);
176 if (D.Lane == u8 and left.len >= word_bytes) return wordMismatch(left, right);
177 for (left, right, 0..) |first, second, index| {
178 if (first != second) return index;
179 }
180 return left.len;
181 }
182
183 /// Orders two spans of integer lanes lexicographically, as `std.mem.order`
184 /// orders slices. The first differing lane decides, and a span that is a
185 /// prefix of the other orders first. Byte spans that share less than a
186 /// vector compare as big-endian words, which order as their bytes do. Longer
187 /// spans compare vectors out of line, so ordering a short key reserves no
188 /// registers for the vector loop.
189 pub fn order(comptime D: type, left: []const D.Lane, right: []const D.Lane) std.math.Order {
190 requireInteger(D.Lane, "order");
191 const shared = @min(left.len, right.len);
192 if (shared >= D.lane_count) return vectorOrder(D, left, right);
193 if (D.Lane == u8 and shared >= word_bytes) return wordOrder(left, right);
194 for (left[0..shared], right[0..shared]) |first, second| {
195 if (first != second) return std.math.order(first, second);
196 }
197 return std.math.order(left.len, right.len);
198 }
199
200 const word_bytes = 8;
201
202 /// Orders spans that share at least one vector by their first differing
203 /// lane, or by length when one is a prefix of the other.
204 noinline fn vectorOrder(
205 comptime D: type,
206 left: []const D.Lane,
207 right: []const D.Lane,
208 ) std.math.Order {
209 const shared = @min(left.len, right.len);
210 const index = vectorMismatch(D, left[0..shared], right[0..shared]);
211 if (index != shared) return std.math.order(left[index], right[index]);
212 return std.math.order(left.len, right.len);
213 }
214
215 /// Returns the first differing lane of equal-length spans of at least one
216 /// vector, or their length when they agree.
217 fn vectorMismatch(comptime D: type, left: []const D.Lane, right: []const D.Lane) usize {
218 std.debug.assert(left.len == right.len);
219 std.debug.assert(left.len >= D.lane_count);
220 if (left.ptr == right.ptr) return left.len;
221 const last = left.len - D.lane_count;
222 var index: usize = 0;
223 while (index < last) : (index += D.lane_count) {
224 if (vectorDifference(D, left, right, index)) |position| return position;
225 }
226 return vectorDifference(D, left, right, last) orelse left.len;
227 }
228
229 /// Returns the first differing lane of the vectors at `start`, or null when
230 /// they agree. An or-reduction tests each vector, and only a vector that
231 /// differs pays to locate its first differing lane.
232 inline fn vectorDifference(
233 comptime D: type,
234 left: []const D.Lane,
235 right: []const D.Lane,
236 start: usize,
237 ) ?usize {
238 const first: D.Vector = left[start..][0..D.lane_count].*;
239 const second: D.Vector = right[start..][0..D.lane_count].*;
240 const differs = first != second;
241 if (!@reduce(.Or, differs)) return null;
242 return start + compare.findKnownFirstTrue(D, differs);
243 }
244
245 /// Returns the first differing byte of equal-length spans of at least one
246 /// word, or their length when they agree. A little-endian load puts the
247 /// first byte in the low bits, so the lowest set bit of a difference names
248 /// it.
249 fn wordMismatch(left: []const u8, right: []const u8) usize {
250 std.debug.assert(left.len == right.len);
251 std.debug.assert(left.len >= word_bytes);
252 const last = left.len - word_bytes;
253 var index: usize = 0;
254 while (index < last) : (index += word_bytes) {
255 const differs = littleWord(left, index) ^ littleWord(right, index);
256 if (differs != 0) return index + @ctz(differs) / 8;
257 }
258 const differs = littleWord(left, last) ^ littleWord(right, last);
259 if (differs != 0) return last + @ctz(differs) / 8;
260 return left.len;
261 }
262
263 /// Orders byte spans that share at least one word. A big-endian load puts
264 /// the first byte in the high bits, so the first differing word orders the
265 /// spans as their first differing byte does.
266 fn wordOrder(left: []const u8, right: []const u8) std.math.Order {
267 const shared = @min(left.len, right.len);
268 std.debug.assert(shared >= word_bytes);
269 const last = shared - word_bytes;
270 var index: usize = 0;
271 while (index < last) : (index += word_bytes) {
272 const first = bigWord(left, index);
273 const second = bigWord(right, index);
274 if (first != second) return std.math.order(first, second);
275 }
276 const first = bigWord(left, last);
277 const second = bigWord(right, last);
278 if (first != second) return std.math.order(first, second);
279 return std.math.order(left.len, right.len);
280 }
281
282 fn littleWord(bytes: []const u8, start: usize) u64 {
283 return std.mem.readInt(u64, bytes[start..][0..word_bytes], .little);
284 }
285
286 fn bigWord(bytes: []const u8, start: usize) u64 {
287 return std.mem.readInt(u64, bytes[start..][0..word_bytes], .big);
288 }
289
290 pub fn unique(comptime D: type, input: []D.Lane) usize {
291 requireInteger(D.Lane, "unique");
292 if (input.len <= 1) return input.len;
293 var written: usize = 1;
294 var index: usize = 1;
295 while (index < input.len) : (index += 1) {
296 if (input[index] != input[written - 1]) {
297 input[written] = input[index];
298 written += 1;
299 }
300 }
301 std.debug.assert(written <= input.len);
302 return written;
303 }
304
305 pub fn allUnique(comptime D: type, input: []const D.Lane) bool {
306 requireInteger(D.Lane, "allUnique");
307 if (input.len <= 1) return true;
308 for (input[1..], input[0 .. input.len - 1]) |current, previous| {
309 if (current == previous) return false;
310 }
311 return true;
312 }
313
314 pub fn minValue(comptime D: type, input: []const D.Lane) D.Lane {
315 const identity = positiveIdentity(D.Lane);
316 var accumulator: D.Vector = @splat(identity);
317 var index: usize = 0;
318 while (index + D.lane_count <= input.len) : (index += D.lane_count) {
319 accumulator = arithmetic.min(D, accumulator, memory.load(D, input[index..]));
320 }
321 if (index != input.len) {
322 const remaining = input.len - index;
323 const value = memory.loadNOr(D, @splat(identity), input[index..], remaining);
324 accumulator = arithmetic.min(D, accumulator, value);
325 }
326 return reduce.min(D, accumulator);
327 }
328
329 pub fn maxValue(comptime D: type, input: []const D.Lane) D.Lane {
330 const identity = negativeIdentity(D.Lane);
331 var accumulator: D.Vector = @splat(identity);
332 var index: usize = 0;
333 while (index + D.lane_count <= input.len) : (index += D.lane_count) {
334 accumulator = arithmetic.max(D, accumulator, memory.load(D, input[index..]));
335 }
336 if (index != input.len) {
337 const remaining = input.len - index;
338 const value = memory.loadNOr(D, @splat(identity), input[index..], remaining);
339 accumulator = arithmetic.max(D, accumulator, value);
340 }
341 return reduce.max(D, accumulator);
342 }
343
344 pub fn isSorted(comptime D: type, input: []const D.Lane) bool {
345 return isSortedBy(D, input, Less{});
346 }
347
348 pub fn isSortedBy(comptime D: type, input: []const D.Lane, comparator: anytype) bool {
349 if (input.len < 2) return true;
350 const pairs = input.len - 1;
351 var index: usize = 0;
352 while (index + D.lane_count <= pairs) : (index += D.lane_count) {
353 const current = memory.load(D, input[index..]);
354 const next = memory.load(D, input[index + 1 ..]);
355 if (!compare.allFalse(D, comparator.call(D, next, current))) return false;
356 }
357 if (index != pairs) {
358 const remaining = pairs - index;
359 const current = memory.loadN(D, input[index .. input.len - 1], remaining);
360 const next = memory.loadN(D, input[index + 1 ..], remaining);
361 const valid = construct.firstN(D, remaining);
362 if (!compare.allFalse(D, comparator.call(D, next, current) & valid)) return false;
363 }
364 return true;
365 }
366
367 pub fn generate(comptime D: type, output: []D.Lane, generator: anytype) void {
368 const U = @Int(.unsigned, @bitSizeOf(D.Lane));
369 const DU = D.rebind(U);
370 var indices = construct.iota(DU, 0);
371 var index: usize = 0;
372 while (index + D.lane_count <= output.len) : (index += D.lane_count) {
373 memory.store(D, generator.call(D, indices), output[index..]);
374 indices +%= @as(DU.Vector, @splat(@intCast(D.lane_count)));
375 }
376 if (index != output.len) {
377 memory.storeN(D, generator.call(D, indices), output[index..], output.len - index);
378 }
379 }
380
381 pub fn foreach(
382 comptime D: type,
383 input: []const D.Lane,
384 no: D.Vector,
385 function: anytype,
386 ) void {
387 var index: usize = 0;
388 while (index + D.lane_count <= input.len) : (index += D.lane_count) {
389 function.call(D, memory.load(D, input[index..]));
390 }
391 if (index != input.len) {
392 function.call(D, memory.loadNOr(D, no, input[index..], input.len - index));
393 }
394 }
395
396 pub fn transform(comptime D: type, input_output: []D.Lane, function: anytype) void {
397 var index: usize = 0;
398 while (index + D.lane_count <= input_output.len) : (index += D.lane_count) {
399 const value = memory.load(D, input_output[index..]);
400 memory.store(D, function.call(D, value), input_output[index..]);
401 }
402 if (index != input_output.len) {
403 const remaining = input_output.len - index;
404 const value = memory.loadN(D, input_output[index..], remaining);
405 memory.storeN(D, function.call(D, value), input_output[index..], remaining);
406 }
407 }
408
409 pub fn transform1(
410 comptime D: type,
411 input_output: []D.Lane,
412 input: []const D.Lane,
413 function: anytype,
414 ) void {
415 std.debug.assert(input.len >= input_output.len);
416 var index: usize = 0;
417 while (index + D.lane_count <= input_output.len) : (index += D.lane_count) {
418 const value = memory.load(D, input_output[index..]);
419 const other = memory.load(D, input[index..]);
420 memory.store(D, function.call(D, value, other), input_output[index..]);
421 }
422 if (index != input_output.len) {
423 const remaining = input_output.len - index;
424 const value = memory.loadN(D, input_output[index..], remaining);
425 const other = memory.loadN(D, input[index..input_output.len], remaining);
426 memory.storeN(D, function.call(D, value, other), input_output[index..], remaining);
427 }
428 }
429
430 pub fn transform2(
431 comptime D: type,
432 input_output: []D.Lane,
433 input1: []const D.Lane,
434 input2: []const D.Lane,
435 function: anytype,
436 ) void {
437 std.debug.assert(input1.len >= input_output.len);
438 std.debug.assert(input2.len >= input_output.len);
439 var index: usize = 0;
440 while (index + D.lane_count <= input_output.len) : (index += D.lane_count) {
441 const value = memory.load(D, input_output[index..]);
442 const first = memory.load(D, input1[index..]);
443 const second = memory.load(D, input2[index..]);
444 memory.store(D, function.call(D, value, first, second), input_output[index..]);
445 }
446 if (index != input_output.len) {
447 const remaining = input_output.len - index;
448 const value = memory.loadN(D, input_output[index..], remaining);
449 const first = memory.loadN(D, input1[index..input_output.len], remaining);
450 const second = memory.loadN(D, input2[index..input_output.len], remaining);
451 memory.storeN(D, function.call(D, value, first, second), input_output[index..], remaining);
452 }
453 }
454
455 pub fn replace(comptime D: type, input_output: []D.Lane, old: D.Lane, new: D.Lane) void {
456 const old_vector: D.Vector = @splat(old);
457 const new_vector: D.Vector = @splat(new);
458 var index: usize = 0;
459 while (index + D.lane_count <= input_output.len) : (index += D.lane_count) {
460 const value = memory.load(D, input_output[index..]);
461 const result = @select(D.Lane, value == old_vector, new_vector, value);
462 memory.store(D, result, input_output[index..]);
463 }
464 if (index != input_output.len) {
465 const remaining = input_output.len - index;
466 const value = memory.loadN(D, input_output[index..], remaining);
467 const result = @select(D.Lane, value == old_vector, new_vector, value);
468 memory.storeN(D, result, input_output[index..], remaining);
469 }
470 }
471
472 pub fn replaceIf(
473 comptime D: type,
474 input_output: []D.Lane,
475 new: D.Lane,
476 predicate: anytype,
477 ) void {
478 const new_vector: D.Vector = @splat(new);
479 var index: usize = 0;
480 while (index + D.lane_count <= input_output.len) : (index += D.lane_count) {
481 const value = memory.load(D, input_output[index..]);
482 const result = @select(D.Lane, predicate.call(D, value), new_vector, value);
483 memory.store(D, result, input_output[index..]);
484 }
485 if (index != input_output.len) {
486 const remaining = input_output.len - index;
487 const value = memory.loadN(D, input_output[index..], remaining);
488 const result = @select(D.Lane, predicate.call(D, value), new_vector, value);
489 memory.storeN(D, result, input_output[index..], remaining);
490 }
491 }
492
493 const Less = struct {
494 fn call(_: @This(), comptime D: type, a: D.Vector, b: D.Vector) D.Mask {
495 return a < b;
496 }
497 };
498
499 fn positiveIdentity(comptime T: type) T {
500 return switch (@typeInfo(T)) {
501 .float => std.math.inf(T),
502 .int => std.math.maxInt(T),
503 else => @compileError("minimum requires numeric lanes"),
504 };
505 }
506
507 fn negativeIdentity(comptime T: type) T {
508 return switch (@typeInfo(T)) {
509 .float => -std.math.inf(T),
510 .int => std.math.minInt(T),
511 else => @compileError("maximum requires numeric lanes"),
512 };
513 }
514
515 fn requireInteger(comptime T: type, comptime operation: []const u8) void {
516 if (@typeInfo(T) != .int) @compileError(operation ++ " requires integer lanes");
517 }
518
519 fn scalar(comptime T: type, value: u8) T {
520 return switch (@typeInfo(T)) {
521 .int => @intCast(value),
522 .float => @floatFromInt(value),
523 else => unreachable,
524 };
525 }
526
527 fn verifyAllTypeAlgorithms(comptime T: type) !void {
528 const simd = @import("root.zig");
529 const D = simd.FixedTag(T, 4);
530 const length: usize = D.lane_count * 2 + 1;
531 const sentinel = scalar(T, 31);
532 var input_storage = @as([(length + 2)]T, @splat(sentinel));
533 var output_storage = @as([(length + 2)]T, @splat(sentinel));
534 const input = input_storage[1 .. length + 1];
535 const output = output_storage[1 .. length + 1];
536 for (input, 0..) |*value, index| value.* = scalar(T, @intCast(index % 5));
537 copy(D, input, output);
538 try std.testing.expectEqualSlices(T, input, output);
539 try std.testing.expectEqual(sentinel, output_storage[0]);
540 try std.testing.expectEqual(sentinel, output_storage[length + 1]);
541 if (@typeInfo(T) == .int) {
542 try std.testing.expect(equal(D, input, output));
543 output[length - 1] = sentinel;
544 try std.testing.expect(!equal(D, input, output));
545 try std.testing.expect(!equal(D, input, output[0 .. length - 1]));
546 output[length - 1] = input[length - 1];
547 }
548 try std.testing.expectEqual(@as(usize, 2), count(D, input, scalar(T, 3)));
549 try std.testing.expectEqual(@as(usize, 3), find(D, input, scalar(T, 3)));
550 try std.testing.expectEqual(scalar(T, 0), minValue(D, input));
551 try std.testing.expectEqual(scalar(T, 4), maxValue(D, input));
552 const GreaterTwo = struct {
553 fn call(_: @This(), comptime Tag: type, value: Tag.Vector) Tag.Mask {
554 return value > @as(Tag.Vector, @splat(scalar(Tag.Lane, 2)));
555 }
556 };
557 try std.testing.expectEqual(@as(usize, 3), countIf(D, input, GreaterTwo{}));
558 try std.testing.expectEqual(@as(usize, 3), findIf(D, input, GreaterTwo{}));
559 if (@sizeOf(T) != 1) {
560 const written = copyIf(D, input, output, GreaterTwo{});
561 try std.testing.expectEqual(@as(usize, 3), written);
562 const expected = [_]T{ scalar(T, 3), scalar(T, 4), scalar(T, 3) };
563 try std.testing.expectEqualSlices(T, &expected, output[0..written]);
564 }
565 var sorted: [length]T = undefined;
566 for (&sorted, 0..) |*value, index| value.* = scalar(T, @intCast(index / 2));
567 try std.testing.expect(isSorted(D, &sorted));
568 sorted[length / 2] = scalar(T, 0);
569 try std.testing.expect(!isSorted(D, &sorted));
570 fill(D, output, scalar(T, 7));
571 try std.testing.expect(allEqual(D, output, scalar(T, 7)));
572 replace(D, output, scalar(T, 7), scalar(T, 9));
573 for (output) |value| try std.testing.expectEqual(scalar(T, 9), value);
574 try std.testing.expect(!allEqual(D, output, scalar(T, 7)));
575 try std.testing.expect(!allEqual(D, input, scalar(T, 0)));
576 }
577
578 fn verifyUniformSpan(comptime D: type) !void {
579 const capacity = 4 * D.lane_count + 9;
580 var storage: [capacity + 2]D.Lane = undefined;
581 var prng = std.Random.DefaultPrng.init(0x3c1e40a7);
582 const U = @Int(.unsigned, @bitSizeOf(D.Lane));
583 const flips = [_]D.Lane{ 1, @bitCast(@as(U, 1) << (@bitSizeOf(D.Lane) - 1)) };
584 for ([_]usize{ 0, 1 }) |offset| {
585 const value = prng.random().int(D.Lane);
586 const input = storage[offset..][0..capacity];
587 for (0..capacity + 1) |length| {
588 @memset(&storage, value ^ flips[0]);
589 @memset(input[0..length], value);
590 try std.testing.expect(allEqual(D, input[0..length], value));
591 if (length != 0) {
592 try std.testing.expect(!allEqual(D, input[0..length], value ^ flips[1]));
593 }
594 for (0..length) |position| {
595 for (flips) |flip| {
596 input[position] ^= flip;
597 try std.testing.expect(!allEqual(D, input[0..length], value));
598 input[position] ^= flip;
599 }
600 }
601 }
602 }
603 }
604
605 fn verifySpanOrder(comptime D: type) !void {
606 const capacity = 4 * D.lane_count + 9;
607 var left_storage: [capacity + 1]D.Lane = undefined;
608 var right_storage: [capacity + 1]D.Lane = undefined;
609 var prng = std.Random.DefaultPrng.init(0x0bd34a11);
610 prng.random().bytes(std.mem.sliceAsBytes(left_storage[0..]));
611 const U = @Int(.unsigned, @bitSizeOf(D.Lane));
612 const flips = [_]D.Lane{ 1, @bitCast(@as(U, 1) << (@bitSizeOf(D.Lane) - 1)) };
613 for ([_]usize{ 0, 1 }) |offset| {
614 const left = left_storage[offset..][0..capacity];
615 const right = right_storage[offset..][0..capacity];
616 for (0..capacity + 1) |length| {
617 @memcpy(right[0..length], left[0..length]);
618 try expectSpanOrder(D, left[0..length], right[0..length]);
619 try expectSpanOrder(D, left[0..length], left[0..length]);
620 if (length != 0) try expectSpanOrder(D, left[0..length], right[0 .. length - 1]);
621 for (0..length) |position| {
622 for (flips) |flip| {
623 right[position] ^= flip;
624 try expectSpanOrder(D, left[0..length], right[0..length]);
625 try expectSpanOrder(D, right[0..length], left[0..length]);
626 right[position] ^= flip;
627 reverseAfter(D.Lane, left[0..length], right[0..length], position, flip);
628 try expectSpanOrder(D, left[0..length], right[0..length]);
629 try expectSpanOrder(D, right[0..length], left[0..length]);
630 @memcpy(right[position..length], left[position..length]);
631 }
632 }
633 }
634 }
635 }
636
637 /// Makes `right` differ from `left` at `position` by `flip` and order the
638 /// other way in every later lane that can. A comparison that lets a later
639 /// lane outweigh the first differing one then reports the wrong order.
640 fn reverseAfter(
641 comptime Lane: type,
642 left: []const Lane,
643 right: []Lane,
644 position: usize,
645 flip: Lane,
646 ) void {
647 std.debug.assert(left.len == right.len);
648 right[position] = left[position] ^ flip;
649 const rises = right[position] > left[position];
650 @memset(right[position + 1 ..], if (rises) std.math.minInt(Lane) else std.math.maxInt(Lane));
651 }
652
653 fn expectSpanOrder(comptime D: type, left: []const D.Lane, right: []const D.Lane) !void {
654 try std.testing.expectEqual(std.mem.order(D.Lane, left, right), order(D, left, right));
655 const shared = @min(left.len, right.len);
656 var expected: usize = 0;
657 while (expected < shared and left[expected] == right[expected]) expected += 1;
658 try std.testing.expectEqual(expected, mismatch(D, left[0..shared], right[0..shared]));
659 }
660
661 fn verifySpanEquality(comptime D: type) !void {
662 const capacity = 4 * D.lane_count + 9;
663 var left_storage: [capacity + 1]D.Lane = undefined;
664 var right_storage: [capacity + 1]D.Lane = undefined;
665 var prng = std.Random.DefaultPrng.init(0x507c9c25);
666 prng.random().bytes(std.mem.sliceAsBytes(left_storage[0..]));
667 const flips = [_]D.Lane{ 1, @as(D.Lane, 1) << (@bitSizeOf(D.Lane) - 1) };
668 for ([_]usize{ 0, 1 }) |offset| {
669 const left = left_storage[offset..][0..capacity];
670 const right = right_storage[offset..][0..capacity];
671 for (0..capacity + 1) |length| {
672 @memcpy(right[0..length], left[0..length]);
673 try std.testing.expect(equal(D, left[0..length], right[0..length]));
674 try std.testing.expect(equal(D, left[0..length], left[0..length]));
675 if (length != 0) {
676 try std.testing.expect(!equal(D, left[0..length], right[0 .. length - 1]));
677 }
678 for (0..length) |position| {
679 for (flips) |flip| {
680 right[position] ^= flip;
681 try std.testing.expect(!equal(D, left[0..length], right[0..length]));
682 right[position] ^= flip;
683 }
684 }
685 }
686 }
687 }
688
689 test "Highway span copy count find and extrema preserve awkward tails" {
690 const simd = @import("root.zig");
691 const D = simd.FixedTag(i32, 8);
692 const input = [_]i32{ 4, 1, 7, 4, 9, 4, 2, 8, 4, 5, 6, 4, 3, 0, 4, 10, 11, 4, 12 };
693 var output = @as([input.len]i32, @splat(99));
694 copy(D, &input, &output);
695 try std.testing.expectEqualSlices(i32, &input, &output);
696 try std.testing.expectEqual(@as(usize, 7), count(D, &input, 4));
697 try std.testing.expectEqual(@as(usize, 0), find(D, &input, 4));
698 try std.testing.expectEqual(input.len, find(D, &input, 13));
699 try std.testing.expectEqual(@as(i32, 0), minValue(D, &input));
700 try std.testing.expectEqual(@as(i32, 12), maxValue(D, &input));
701 try std.testing.expectEqual(std.math.maxInt(i32), minValue(D, &.{}));
702 try std.testing.expectEqual(std.math.minInt(i32), maxValue(D, &.{}));
703
704 fill(D, &output, -3);
705 try std.testing.expectEqualSlices(i32, &(@as([input.len]i32, @splat(-3))), &output);
706 }
707
708 test "span equality agrees with element equality at every length and mismatch position" {
709 const simd = @import("root.zig");
710 try verifySpanEquality(simd.ScalableTag(u8));
711 try verifySpanEquality(simd.FixedTag(u8, 16));
712 try verifySpanEquality(simd.FixedTag(u32, 8));
713 try verifySpanEquality(simd.ScalableTag(u64));
714 }
715
716 test "uniform spans agree with element equality at every length and differing position" {
717 const simd = @import("root.zig");
718 try verifyUniformSpan(simd.ScalableTag(u8));
719 try verifyUniformSpan(simd.FixedTag(u8, 16));
720 try verifyUniformSpan(simd.FixedTag(i16, 8));
721 try verifyUniformSpan(simd.FixedTag(u32, 8));
722 try verifyUniformSpan(simd.ScalableTag(u64));
723 }
724
725 test "span mismatch and order agree with element order at every length and mismatch position" {
726 const simd = @import("root.zig");
727 try verifySpanOrder(simd.ScalableTag(u8));
728 try verifySpanOrder(simd.FixedTag(u8, 16));
729 try verifySpanOrder(simd.FixedTag(i16, 8));
730 try verifySpanOrder(simd.FixedTag(u32, 8));
731 try verifySpanOrder(simd.ScalableTag(u64));
732 }
733
734 test "byte order compares unsigned bytes and breaks prefix ties by length" {
735 const simd = @import("root.zig");
736 const Bytes = simd.ScalableTag(u8);
737 try std.testing.expectEqual(std.math.Order.lt, order(Bytes, "k0000001", "k0000002"));
738 try std.testing.expectEqual(std.math.Order.gt, order(Bytes, "\xff", "\x00\xff"));
739 try std.testing.expectEqual(std.math.Order.lt, order(Bytes, "k00000001\xff", "k00000002\x00"));
740 try std.testing.expectEqual(std.math.Order.lt, order(Bytes, "abcdefgh", "abcdefghi"));
741 try std.testing.expectEqual(std.math.Order.eq, order(Bytes, "abcdefghij", "abcdefghij"));
742 try std.testing.expectEqual(std.math.Order.eq, order(Bytes, "", ""));
743 }
744
745 test "span equality finds one changed byte anywhere in a large span" {
746 const simd = @import("root.zig");
747 const D = simd.ScalableTag(u8);
748 const capacity = (1 << 20) + 13;
749 const left_storage = try std.testing.allocator.alloc(u8, capacity + 1);
750 defer std.testing.allocator.free(left_storage);
751 const right_storage = try std.testing.allocator.alloc(u8, capacity + 1);
752 defer std.testing.allocator.free(right_storage);
753 var prng = std.Random.DefaultPrng.init(0x507c9c25);
754 prng.random().bytes(left_storage);
755 const positions = [_]usize{ 0, capacity / 2 + 7, capacity - D.lane_count - 1, capacity - 1 };
756 for ([_]usize{ 0, 1 }) |offset| {
757 const left = left_storage[offset..][0..capacity];
758 const right = right_storage[offset..][0..capacity];
759 @memcpy(right, left);
760 try std.testing.expect(equal(D, left, right));
761 for (positions) |position| {
762 right[position] ^= 0x40;
763 try std.testing.expect(!equal(D, left, right));
764 right[position] ^= 0x40;
765 }
766 try std.testing.expect(equal(D, left, right));
767 }
768 }
769
770 test "Highway predicate algorithms retain stable order and callback tails" {
771 const simd = @import("root.zig");
772 const D = simd.FixedTag(i32, 8);
773 const Positive = struct {
774 fn call(_: @This(), comptime Tag: type, value: Tag.Vector) Tag.Mask {
775 return value > @as(Tag.Vector, @splat(0));
776 }
777 };
778 const predicate = Positive{};
779 const input = [_]i32{ -4, 1, 7, -2, 9, 0, 2, 8, -3, 5, 6 };
780 try std.testing.expectEqual(@as(usize, 7), countIf(D, &input, predicate));
781 try std.testing.expectEqual(@as(usize, 1), findIf(D, &input, predicate));
782 var selected = @as([input.len]i32, @splat(99));
783 const written = copyIf(D, &input, &selected, predicate);
784 try std.testing.expectEqual(@as(usize, 7), written);
785 try std.testing.expectEqualSlices(i32, &.{ 1, 7, 9, 2, 8, 5, 6 }, selected[0..written]);
786
787 var grouped = [_]i32{ 1, 1, 2, 2, 2, 4, 7, 7, 9 };
788 try std.testing.expect(!allUnique(D, &grouped));
789 const unique_count = unique(D, &grouped);
790 try std.testing.expectEqualSlices(i32, &.{ 1, 2, 4, 7, 9 }, grouped[0..unique_count]);
791 try std.testing.expect(allUnique(D, grouped[0..unique_count]));
792 }
793
794 test "Highway sorted and transform algorithms honor vector callbacks" {
795 const simd = @import("root.zig");
796 const D = simd.FixedTag(i32, 8);
797 const Descending = struct {
798 fn call(_: @This(), comptime Tag: type, a: Tag.Vector, b: Tag.Vector) Tag.Mask {
799 return a > b;
800 }
801 };
802 try std.testing.expect(isSorted(D, &.{ -3, -1, -1, 0, 4, 9 }));
803 try std.testing.expect(!isSorted(D, &.{ -3, 2, 1, 4 }));
804 try std.testing.expect(isSortedBy(D, &.{ 9, 4, 4, 0, -1 }, Descending{}));
805
806 const GenerateSquare = struct {
807 fn call(_: @This(), comptime Tag: type, indices: Tag.rebind(u32).Vector) Tag.Vector {
808 const signed: Tag.Vector = @bitCast(indices);
809 return signed * signed;
810 }
811 };
812 var values: [19]i32 = undefined;
813 generate(D, &values, GenerateSquare{});
814 for (&values, 0..) |value, index| {
815 try std.testing.expectEqual(@as(i32, @intCast(index * index)), value);
816 }
817
818 const Scale = struct {
819 factor: i32,
820 fn call(self: @This(), comptime Tag: type, value: Tag.Vector) Tag.Vector {
821 return value * @as(Tag.Vector, @splat(self.factor));
822 }
823 };
824 transform(D, &values, Scale{ .factor = 2 });
825 for (&values, 0..) |value, index| {
826 try std.testing.expectEqual(@as(i32, @intCast(index * index * 2)), value);
827 }
828
829 const Add = struct {
830 fn call(_: @This(), comptime Tag: type, a: Tag.Vector, b: Tag.Vector) Tag.Vector {
831 return a + b;
832 }
833 };
834 const ones = @as([values.len]i32, @splat(1));
835 transform1(D, &values, &ones, Add{});
836 const twos = @as([values.len]i32, @splat(2));
837 transform2(D, &values, &ones, &twos, struct {
838 fn call(
839 _: @This(),
840 comptime Tag: type,
841 a: Tag.Vector,
842 b: Tag.Vector,
843 c: Tag.Vector,
844 ) Tag.Vector {
845 return a + b * c;
846 }
847 }{});
848 replace(D, &values, 3, -3);
849 replaceIf(D, &values, 0, struct {
850 fn call(_: @This(), comptime Tag: type, value: Tag.Vector) Tag.Mask {
851 return value > @as(Tag.Vector, @splat(100));
852 }
853 }{});
854 try std.testing.expectEqual(@as(i32, -3), values[0]);
855 try std.testing.expectEqual(@as(i32, 5), values[1]);
856 try std.testing.expectEqual(@as(i32, 0), values[8]);
857 }
858
859 test "Highway foreach substitutes caller lanes beyond the input" {
860 const simd = @import("root.zig");
861 const D = simd.FixedTag(i32, 4);
862 const Collector = struct {
863 output: *[8]i32,
864 index: *usize,
865 fn call(self: @This(), comptime Tag: type, value: Tag.Vector) void {
866 const lanes: [Tag.lane_count]Tag.Lane = value;
867 for (lanes) |lane_value| {
868 self.output[self.index.*] = lane_value;
869 self.index.* += 1;
870 }
871 }
872 };
873 var output: [8]i32 = undefined;
874 var index: usize = 0;
875 foreach(D, &.{ 1, 2, 3, 4, 5, 6 }, @as(D.Vector, .{ 90, 91, 92, 93 }), Collector{
876 .output = &output,
877 .index = &index,
878 });
879 try std.testing.expectEqualSlices(i32, &.{ 1, 2, 3, 4, 5, 6, 92, 93 }, &output);
880 }
881
882 test "Highway algorithms instantiate every supported lane type" {
883 inline for (.{ u8, i8, u16, i16, u32, i32, u64, i64, f16, f32, f64 }) |T| {
884 try verifyAllTypeAlgorithms(T);
885 }
886 }