tiny.simd.algo

1const std = @import("std");2const arithmetic = @import("arithmetic.zig");3const compact = @import("compact.zig");4const compare = @import("compare.zig");5const construct = @import("construct.zig");6const memory = @import("memory.zig");7const reduce = @import("reduce.zig");89pub 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}1718pub 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}3031pub 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}5960pub 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}7576pub 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}9091pub 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}107108pub 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}124125pub 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}143144/// Returns whether every lane of `input` equals `value`, as145/// `std.mem.allEqual` does. Whole vectors compare with the broadcast value,146/// and the last vector overlaps lanes already compared. A span shorter than147/// a vector compares lane by lane.148pub 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}167168/// 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, and170/// the last vector overlaps lanes already known equal. A byte span shorter171/// than a vector compares eight bytes at a time the same way.172pub 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}182183/// Orders two spans of integer lanes lexicographically, as `std.mem.order`184/// orders slices. The first differing lane decides, and a span that is a185/// prefix of the other orders first. Byte spans that share less than a186/// vector compare as big-endian words, which order as their bytes do. Longer187/// spans compare vectors out of line, so ordering a short key reserves no188/// registers for the vector loop.189pub 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}199200const word_bytes = 8;201202/// Orders spans that share at least one vector by their first differing203/// lane, or by length when one is a prefix of the other.204noinline 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}214215/// Returns the first differing lane of equal-length spans of at least one216/// vector, or their length when they agree.217fn 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}228229/// Returns the first differing lane of the vectors at `start`, or null when230/// they agree. An or-reduction tests each vector, and only a vector that231/// differs pays to locate its first differing lane.232inline 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}244245/// Returns the first differing byte of equal-length spans of at least one246/// word, or their length when they agree. A little-endian load puts the247/// first byte in the low bits, so the lowest set bit of a difference names248/// it.249fn 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}262263/// Orders byte spans that share at least one word. A big-endian load puts264/// the first byte in the high bits, so the first differing word orders the265/// spans as their first differing byte does.266fn 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}281282fn littleWord(bytes: []const u8, start: usize) u64 {283    return std.mem.readInt(u64, bytes[start..][0..word_bytes], .little);284}285286fn bigWord(bytes: []const u8, start: usize) u64 {287    return std.mem.readInt(u64, bytes[start..][0..word_bytes], .big);288}289290pub 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}304305pub 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}313314pub 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}328329pub 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}343344pub fn isSorted(comptime D: type, input: []const D.Lane) bool {345    return isSortedBy(D, input, Less{});346}347348pub 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}366367pub 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}380381pub 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}395396pub 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}408409pub 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}429430pub 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}454455pub 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}471472pub 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}492493const Less = struct {494    fn call(_: @This(), comptime D: type, a: D.Vector, b: D.Vector) D.Mask {495        return a < b;496    }497};498499fn 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}506507fn 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}514515fn requireInteger(comptime T: type, comptime operation: []const u8) void {516    if (@typeInfo(T) != .int) @compileError(operation ++ " requires integer lanes");517}518519fn 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}526527fn 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}577578fn 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}604605fn 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}636637/// Makes `right` differ from `left` at `position` by `flip` and order the638/// other way in every later lane that can. A comparison that lets a later639/// lane outweigh the first differing one then reports the wrong order.640fn 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}652653fn 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}660661fn 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}688689test "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, &.{}));703704    fill(D, &output, -3);705    try std.testing.expectEqualSlices(i32, &(@as([input.len]i32, @splat(-3))), &output);706}707708test "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}715716test "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}724725test "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}733734test "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}744745test "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}769770test "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]);786787    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}793794test "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{}));805806    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    }817818    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    }828829    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}858859test "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}881882test "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}

1pub const algo = @import("algo.zig");