跳转到内容
标准库Zig 0.17.0官方原文
源码std/simd.zig

第 1 行

SIMD,即单指令多数据的便捷函数。

在某些目标上,通过同时对多个元素 执行相同操作,可能提高性能。

已知某些函数在 MIPS 上无法工作。

std.simd.builtin

常量

第 9 行

std.simd.countElementsWithValue

函数

第 352 行

pub fn countElementsWithValue(vec: anytype, value: std.meta.Child(@TypeOf(vec))) VectorCount(@TypeOf(vec))

参数

value: std.meta.Child(@TypeOf(vec))

std.simd.countTrues

函数

第 329 行

pub fn countTrues(vec: anytype) VectorCount(@TypeOf(vec))

std.simd.deinterlace

函数

第 191 行

将 interlaced 的内容均匀拆分到 vec_count 个向量中,并以数组返回。各向量“轮流” 每次从 interlaced 接收一个元素。

pub fn deinterlace( comptime vec_count: usize, interlaced: anytype, ) [vec_count]@Vector( vectorLength(@TypeOf(interlaced)) / vec_count, std.meta.Child(@TypeOf(interlaced)), )

参数

vec_count: usize

std.simd.extract

函数

第 212 行

pub fn extract( vec: anytype, comptime first: VectorIndex(@TypeOf(vec)), comptime count: VectorCount(@TypeOf(vec)), ) @Vector(count, std.meta.Child(@TypeOf(vec)))

参数

first: VectorIndex(@TypeOf(vec))
count: VectorCount(@TypeOf(vec))

std.simd.firstIndexOfValue

函数

第 340 行

pub fn firstIndexOfValue(vec: anytype, value: std.meta.Child(@TypeOf(vec))) ?VectorIndex(@TypeOf(vec))

参数

value: std.meta.Child(@TypeOf(vec))

std.simd.firstTrue

函数

第 304 行

pub fn firstTrue(vec: anytype) ?VectorIndex(@TypeOf(vec))

std.simd.interlace

函数

第 159 行

返回一个向量,其元素交替取自每个输入向量。 例如,interlace(.{[4]u32{11, 12, 13, 14}, [4]u32{21, 22, 23, 24}}) 返回包含 .{11, 21, 12, 22, 13, 23, 14, 24} 的向量。

pub fn interlace(vecs: anytype) @Vector(vectorLength(@TypeOf(vecs[0])) * vecs.len, std.meta.Child(@TypeOf(vecs[0])))

std.simd.iota

函数

第 125 行

返回包含前 len 个整数的向量,按 0 到 len-1 顺序排列。 例如,iota(i32, 8) 返回包含 .{0, 1, 2, 3, 4, 5, 6, 7} 的向量。

pub inline fn iota(comptime T: type, comptime len: usize) @Vector(len, T)

参数

T: type
len: usize

std.simd.join

函数

第 149 行

返回一个向量:较低索引先包含第一个向量的全部元素, 较高索引随后包含第二个向量的全部元素。

pub fn join(a: anytype, b: anytype) @Vector(vectorLength(@TypeOf(a)) + vectorLength(@TypeOf(b)), std.meta.Child(@TypeOf(a)))

std.simd.lastIndexOfValue

函数

第 346 行

pub fn lastIndexOfValue(vec: anytype, value: std.meta.Child(@TypeOf(vec))) ?VectorIndex(@TypeOf(vec))

参数

value: std.meta.Child(@TypeOf(vec))

std.simd.lastTrue

函数

第 316 行

pub fn lastTrue(vec: anytype) ?VectorIndex(@TypeOf(vec))

std.simd.mergeShift

函数

第 251 行

连接两个向量,将其左移(朝更低索引方向),并取最左侧元素组成长度与 a、b 相同的向量。

pub fn mergeShift(a: anytype, b: anytype, comptime shift: VectorCount(@TypeOf(a, b))) @TypeOf(a, b)

参数

shift: VectorCount(@TypeOf(a, b))

std.simd.prefixScan

函数

第 398 行

返回向量,其中各元素为对输入向量对应元素及其之前每隔 hop 个位置的元素执行指定操作的结果;若 hop 为负,则使用之后的元素。 支持与 @reduce() 内置函数相同的操作,计算需要 O(logN) 时间。 扫描并非线性进行,可能影响浮点误差,进而影响使用此函数的算法的确定性。

pub fn prefixScan(comptime op: std.builtin.ReduceOp, comptime hop: isize, vec: anytype) @TypeOf(vec)

参数

op: std.builtin.ReduceOp
hop: isize

std.simd.prefixScan.opFn

函数

第 425 行

fn opFn(a: VecType, b: VecType) VecType

参数

a: VecType
b: VecType

std.simd.prefixScanWithFunc

函数

第 368 行

与 prefixScan 相同,但使用用户提供、数学上满足结合律的函数。

pub fn prefixScanWithFunc( comptime hop: isize, vec: anytype, comptime ErrorType: type, comptime func: fn (@TypeOf(vec), @TypeOf(vec)) if (ErrorType == void) @TypeOf(vec) else ErrorType!@TypeOf(vec), comptime identity: std.meta.Child(@TypeOf(vec)), ) if (ErrorType == void) @TypeOf(vec) else ErrorType!@TypeOf(vec)

参数

hop: isize
ErrorType: type

func 可能返回的错误类型。若 func 不返回错误联合体,则设为 void。

func: fn (@TypeOf(vec), @TypeOf(vec)) if (ErrorType == void) @TypeOf(vec) else ErrorType!@TypeOf(vec)
identity: std.meta.Child(@TypeOf(vec))

当 func 所执行操作的某一操作数为此值时,结果必须等于另一操作数。 例如,加法应使用 0,乘法应使用 1。

std.simd.repeat

函数

第 141 行

返回包含与输入相同元素的向量,重复这些元素,直到达到所需长度。 例如,repeat(8, [_]u32{1, 2, 3}) 返回包含 .{1, 2, 3, 1, 2, 3, 1, 2} 的向量。

pub fn repeat(comptime len: usize, vec: anytype) @Vector(len, std.meta.Child(@TypeOf(vec)))

参数

len: usize

std.simd.reverseOrder

函数

第 287 行

pub fn reverseOrder(vec: anytype) @TypeOf(vec)

std.simd.rotateElementsLeft

函数

第 278 行

元素向左移动,即向更低索引移动。从左侧移出的元素会按相同顺序重新出现在右侧。

pub fn rotateElementsLeft(vec: anytype, comptime amount: VectorCount(@TypeOf(vec))) @TypeOf(vec)

参数

amount: VectorCount(@TypeOf(vec))

std.simd.rotateElementsRight

函数

第 283 行

元素向右移动,即向更高索引移动。从右侧移出的元素会按相同顺序重新出现在左侧。

pub fn rotateElementsRight(vec: anytype, comptime amount: VectorCount(@TypeOf(vec))) @TypeOf(vec)

参数

amount: VectorCount(@TypeOf(vec))

std.simd.shiftElementsLeft

函数

第 271 行

将元素左移(移向更低索引)。在右侧添加新元素,并截去最左侧元素, 使索引小于 0 的元素不再保留。

pub fn shiftElementsLeft(vec: anytype, comptime amount: VectorCount(@TypeOf(vec)), shift_in: std.meta.Child(@TypeOf(vec))) @TypeOf(vec)

参数

amount: VectorCount(@TypeOf(vec))
shift_in: std.meta.Child(@TypeOf(vec))

std.simd.shiftElementsRight

函数

第 259 行

将元素右移(移向更高索引)。在左侧添加新元素,并截去最右侧元素, 从而保持向量长度不变。

pub fn shiftElementsRight(vec: anytype, comptime amount: VectorCount(@TypeOf(vec)), shift_in: std.meta.Child(@TypeOf(vec))) @TypeOf(vec)

参数

amount: VectorCount(@TypeOf(vec))
shift_in: std.meta.Child(@TypeOf(vec))

std.simd.std

别名

第 8 行

别名目标 std

std.simd.suggestVectorLength

函数

第 87 行

为给定类型建议依赖目标的向量长度;若建议使用标量,则返回 null。 尚未针对所有 CPU 架构实现。

pub fn suggestVectorLength(comptime T: type) ?comptime_int

参数

T: type

std.simd.suggestVectorLengthForCpu

函数

第 11 行

pub fn suggestVectorLengthForCpu(comptime T: type, comptime cpu: std.Target.Cpu) ?comptime_int

参数

T: type
cpu: std.Target.Cpu

std.simd.VectorCount

类型函数

第 119 行

返回能够容纳给定向量类型长度的最小无符号整数类型。

pub fn VectorCount(comptime VectorType: type) type

参数

VectorType: type

std.simd.VectorIndex

类型函数

第 114 行

返回能够索引给定向量类型中任意元素的最小无符号整数类型。

pub fn VectorIndex(comptime VectorType: type) type

参数

VectorType: type

std.simd.vectorLength

函数

第 105 行

fn vectorLength(comptime VectorType: type) comptime_int

参数

VectorType: type
源码

std/simd.zig

//! SIMD,即单指令多数据的便捷函数。
//!
//! 在某些目标上,通过同时对多个元素
//! 执行相同操作,可能提高性能。
//!
//! 已知某些函数在 MIPS 上无法工作。

const std = @import("std");
const builtin = @import("builtin");

pub fn suggestVectorLengthForCpu(comptime T: type, comptime cpu: std.Target.Cpu) ?comptime_int {
    @setEvalBranchQuota(2_000);

    // 此处只是推测;如有更好的建议,可以补充或修改当前内容
    const element_bit_size = @max(8, std.math.ceilPowerOfTwo(u16, @bitSizeOf(T)) catch unreachable);
    const vector_bit_size: u16 = blk: {
        if (cpu.arch.isX86()) {
            if (T == bool and cpu.has(.x86, .prefer_mask_registers)) return 64;
            if (builtin.zig_backend != .stage2_x86_64 and cpu.has(.x86, .avx512f) and !cpu.hasAny(.x86, &.{ .prefer_256_bit, .prefer_128_bit })) break :blk 512;
            if (cpu.hasAny(.x86, &.{ .prefer_256_bit, .avx2 }) and !cpu.has(.x86, .prefer_128_bit)) break :blk 256;
            if (cpu.has(.x86, .sse)) break :blk 128;
            if (cpu.hasAny(.x86, &.{ .mmx, .@"3dnow" })) break :blk 64;
        } else if (cpu.arch.isArm()) {
            if (cpu.has(.arm, .neon)) break :blk 128;
        } else if (cpu.arch.isAARCH64()) {
            // NVIDIA Grace 支持 128 位 SVE
            // AWS Graviton3 支持 256 位 SVE
            // Fujitsu A64FX 支持 512 位 SVE
            // -> 目前采用 256 位作为默认值似乎较合适。
            if (cpu.has(.aarch64, .sve)) break :blk 256;
            if (cpu.has(.aarch64, .neon)) break :blk 128;
        } else if (cpu.arch == .hexagon) {
            if (cpu.has(.hexagon, .hvx_length64b)) break :blk 512;
            if (cpu.has(.hexagon, .hvx)) break :blk 1024;
        } else if (cpu.arch.isLoongArch()) {
            if (cpu.has(.loongarch, .lasx)) break :blk 256;
            if (cpu.has(.loongarch, .lsx)) break :blk 128;
        } else if (cpu.arch.isMIPS()) {
            if (cpu.has(.mips, .msa)) break :blk 128;
            if (cpu.has(.mips, .mips3d)) break :blk 64;
        } else if (cpu.arch.isPowerPC()) {
            if (cpu.has(.powerpc, .vsx)) break :blk 128;
            if (cpu.has(.powerpc, .altivec)) break :blk 128;
        } else if (cpu.arch.isRISCV()) {
            // RISC-V 向量寄存器不限定长度,因此没有良好方式确定最佳大小。
            // 多数 RISC-V 处理器的常见向量长度为 256 位,但也可能达到数 KiB。
            if (cpu.has(.riscv, .v)) {
                inline for (.{
                    .{ .zvl65536b, 65536 },
                    .{ .zvl32768b, 32768 },
                    .{ .zvl16384b, 16384 },
                    .{ .zvl8192b, 8192 },
                    .{ .zvl4096b, 4096 },
                    .{ .zvl2048b, 2048 },
                    .{ .zvl1024b, 1024 },
                    .{ .zvl512b, 512 },
                    .{ .zvl256b, 256 },
                    .{ .zvl128b, 128 },
                    .{ .zvl64b, 64 },
                    .{ .zvl32b, 32 },
                }) |mapping| {
                    if (cpu.has(.riscv, mapping[0])) break :blk mapping[1];
                }

                break :blk 256;
            }
        } else if (cpu.arch == .s390x) {
            if (cpu.has(.s390x, .vector)) break :blk 128;
        } else if (cpu.arch.isSPARC()) {
            if (cpu.hasAny(.sparc, &.{ .vis, .vis2, .vis3 })) break :blk 64;
        } else if (cpu.arch == .kvx) {
            break :blk 1024;
        } else if (cpu.arch == .ve) {
            if (cpu.has(.ve, .vpu)) break :blk 2048;
        } else if (cpu.arch.isWasm()) {
            if (cpu.has(.wasm, .simd128)) break :blk 128;
        }
        return null;
    };
    if (vector_bit_size <= element_bit_size) return null;

    return @divExact(vector_bit_size, element_bit_size);
}

/// 为给定类型建议依赖目标的向量长度;若建议使用标量,则返回 null。
/// 尚未针对所有 CPU 架构实现。
pub fn suggestVectorLength(comptime T: type) ?comptime_int {
    return suggestVectorLengthForCpu(T, builtin.cpu);
}

test "suggestVectorLengthForCpu works with signed and unsigned values" {
    comptime var cpu = std.Target.Cpu.baseline(std.Target.Cpu.Arch.x86_64, builtin.os);
    comptime cpu.features.addFeature(@backingInt(std.Target.x86.Feature.avx512f));
    comptime cpu.features.populateDependencies(&std.Target.x86.all_features);
    const expected_len: usize = switch (builtin.zig_backend) {
        .stage2_x86_64 => 8,
        else => 16,
    };
    const signed_integer_len = suggestVectorLengthForCpu(i32, cpu).?;
    const unsigned_integer_len = suggestVectorLengthForCpu(u32, cpu).?;
    try std.testing.expectEqual(expected_len, unsigned_integer_len);
    try std.testing.expectEqual(expected_len, signed_integer_len);
}

fn vectorLength(comptime VectorType: type) comptime_int {
    return switch (@typeInfo(VectorType)) {
        .vector => |info| info.len,
        .array => |info| info.len,
        else => @compileError("Invalid type " ++ @typeName(VectorType)),
    };
}

/// 返回能够索引给定向量类型中任意元素的最小无符号整数类型。
pub fn VectorIndex(comptime VectorType: type) type {
    return std.math.IntFittingRange(0, vectorLength(VectorType) - 1);
}

/// 返回能够容纳给定向量类型长度的最小无符号整数类型。
pub fn VectorCount(comptime VectorType: type) type {
    return std.math.IntFittingRange(0, vectorLength(VectorType));
}

/// 返回包含前 `len` 个整数的向量,按 0 到 `len`-1 顺序排列。
/// 例如,`iota(i32, 8)` 返回包含 `.{0, 1, 2, 3, 4, 5, 6, 7}` 的向量。
pub inline fn iota(comptime T: type, comptime len: usize) @Vector(len, T) {
    comptime {
        var out: [len]T = undefined;
        for (&out, 0..) |*element, i| {
            element.* = switch (@typeInfo(T)) {
                .int => @as(T, @intCast(i)),
                .float => @as(T, @floatFromInt(i)),
                else => @compileError("Can't use type " ++ @typeName(T) ++ " in iota."),
            };
        }
        return @as(@Vector(len, T), out);
    }
}

/// 返回包含与输入相同元素的向量,重复这些元素,直到达到所需长度。
/// 例如,`repeat(8, [_]u32{1, 2, 3})` 返回包含 `.{1, 2, 3, 1, 2, 3, 1, 2}` 的向量。
pub fn repeat(comptime len: usize, vec: anytype) @Vector(len, std.meta.Child(@TypeOf(vec))) {
    const Child = std.meta.Child(@TypeOf(vec));

    return @shuffle(Child, vec, undefined, iota(i32, len) % @as(@Vector(len, i32), @splat(@intCast(vectorLength(@TypeOf(vec))))));
}

/// 返回一个向量:较低索引先包含第一个向量的全部元素,
/// 较高索引随后包含第二个向量的全部元素。
pub fn join(a: anytype, b: anytype) @Vector(vectorLength(@TypeOf(a)) + vectorLength(@TypeOf(b)), std.meta.Child(@TypeOf(a))) {
    const Child = std.meta.Child(@TypeOf(a));
    const a_len = vectorLength(@TypeOf(a));
    const b_len = vectorLength(@TypeOf(b));

    return @shuffle(Child, a, b, @as([a_len]i32, iota(i32, a_len)) ++ @as([b_len]i32, ~iota(i32, b_len)));
}

/// 返回一个向量,其元素交替取自每个输入向量。
/// 例如,`interlace(.{[4]u32{11, 12, 13, 14}, [4]u32{21, 22, 23, 24}})` 返回包含 `.{11, 21, 12, 22, 13, 23, 14, 24}` 的向量。
pub fn interlace(vecs: anytype) @Vector(vectorLength(@TypeOf(vecs[0])) * vecs.len, std.meta.Child(@TypeOf(vecs[0]))) {
    const VecType = @TypeOf(vecs[0]);
    const vecs_arr = @as([vecs.len]VecType, vecs);
    const Child = std.meta.Child(@TypeOf(vecs_arr[0]));

    if (vecs_arr.len == 1) return vecs_arr[0];

    const a_vec_count = (1 + vecs_arr.len) >> 1;
    const b_vec_count = vecs_arr.len >> 1;

    const a = interlace(@as(*const [a_vec_count]VecType, @ptrCast(vecs_arr[0..a_vec_count])).*);
    const b = interlace(@as(*const [b_vec_count]VecType, @ptrCast(vecs_arr[a_vec_count..])).*);

    const a_len = vectorLength(@TypeOf(a));
    const b_len = vectorLength(@TypeOf(b));
    const len = a_len + b_len;

    const indices = comptime blk: {
        const Vi32 = @Vector(len, i32);
        const count_up = iota(i32, len);
        const cycle = @divFloor(count_up, @as(Vi32, @splat(@intCast(vecs_arr.len))));
        const select_mask = repeat(len, join(@as(@Vector(a_vec_count, bool), @splat(true)), @as(@Vector(b_vec_count, bool), @splat(false))));
        const a_indices = count_up - cycle * @as(Vi32, @splat(@intCast(b_vec_count)));
        const b_indices = shiftElementsRight(count_up - cycle * @as(Vi32, @splat(@intCast(a_vec_count))), a_vec_count, 0);
        break :blk @select(i32, select_mask, a_indices, ~b_indices);
    };

    return @shuffle(Child, a, b, indices);
}

/// 将 `interlaced` 的内容均匀拆分到 vec_count 个向量中,并以数组返回。各向量“轮流”
/// 每次从 `interlaced` 接收一个元素。
pub fn deinterlace(
    comptime vec_count: usize,
    interlaced: anytype,
) [vec_count]@Vector(
    vectorLength(@TypeOf(interlaced)) / vec_count,
    std.meta.Child(@TypeOf(interlaced)),
) {
    const vec_len = vectorLength(@TypeOf(interlaced)) / vec_count;
    const Child = std.meta.Child(@TypeOf(interlaced));

    var out: [vec_count]@Vector(vec_len, Child) = undefined;

    comptime var i: usize = 0; // 显然,for 循环不适用于此处。
    inline while (i < out.len) : (i += 1) {
        const indices = comptime iota(i32, vec_len) * @as(@Vector(vec_len, i32), @splat(@intCast(vec_count))) + @as(@Vector(vec_len, i32), @splat(@intCast(i)));
        out[i] = @shuffle(Child, interlaced, undefined, indices);
    }

    return out;
}

pub fn extract(
    vec: anytype,
    comptime first: VectorIndex(@TypeOf(vec)),
    comptime count: VectorCount(@TypeOf(vec)),
) @Vector(count, std.meta.Child(@TypeOf(vec))) {
    const Child = std.meta.Child(@TypeOf(vec));
    const len = vectorLength(@TypeOf(vec));

    std.debug.assert(@as(comptime_int, @intCast(first)) + @as(comptime_int, @intCast(count)) <= len);

    return @shuffle(Child, vec, undefined, iota(i32, count) + @as(@Vector(count, i32), @splat(@intCast(first))));
}

test "vector patterns" {
    if (builtin.cpu.arch == .hexagon) return error.SkipZigTest;

    const base = @Vector(4, u32){ 10, 20, 30, 40 };
    const other_base = @Vector(4, u32){ 55, 66, 77, 88 };

    const small_bases = [5]@Vector(2, u8){
        @Vector(2, u8){ 0, 1 },
        @Vector(2, u8){ 2, 3 },
        @Vector(2, u8){ 4, 5 },
        @Vector(2, u8){ 6, 7 },
        @Vector(2, u8){ 8, 9 },
    };

    try std.testing.expectEqual([6]u32{ 10, 20, 30, 40, 10, 20 }, repeat(6, base));
    try std.testing.expectEqual([8]u32{ 10, 20, 30, 40, 55, 66, 77, 88 }, join(base, other_base));
    try std.testing.expectEqual([2]u32{ 20, 30 }, extract(base, 1, 2));

    try std.testing.expectEqual([8]u32{ 10, 55, 20, 66, 30, 77, 40, 88 }, interlace(.{ base, other_base }));

    const small_braid = interlace(small_bases);
    try std.testing.expectEqual([10]u8{ 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 }, small_braid);
    try std.testing.expectEqual(small_bases, deinterlace(small_bases.len, small_braid));
}

/// 连接两个向量,将其左移(朝更低索引方向),并取最左侧元素组成长度与 a、b 相同的向量。
pub fn mergeShift(a: anytype, b: anytype, comptime shift: VectorCount(@TypeOf(a, b))) @TypeOf(a, b) {
    const len = vectorLength(@TypeOf(a, b));

    return extract(join(a, b), shift, len);
}

/// 将元素右移(移向更高索引)。在左侧添加新元素,并截去最右侧元素,
/// 从而保持向量长度不变。
pub fn shiftElementsRight(vec: anytype, comptime amount: VectorCount(@TypeOf(vec)), shift_in: std.meta.Child(@TypeOf(vec))) @TypeOf(vec) {
    // 或许可通过两个连接后的向量的切片实现移位与旋转,该切片便于运行时操作,因为其
    // 长度在编译期已知。这将允许向量使用编译期未知的位数进行移位和旋转。
    // 不过,我不确定所有平台上的编译器优化能否足够好地处理此情况。
    const V = @TypeOf(vec);
    const len = vectorLength(V);

    return mergeShift(@as(V, @splat(shift_in)), vec, len - amount);
}

/// 将元素左移(移向更低索引)。在右侧添加新元素,并截去最左侧元素,
/// 使索引小于 0 的元素不再保留。
pub fn shiftElementsLeft(vec: anytype, comptime amount: VectorCount(@TypeOf(vec)), shift_in: std.meta.Child(@TypeOf(vec))) @TypeOf(vec) {
    const V = @TypeOf(vec);

    return mergeShift(vec, @as(V, @splat(shift_in)), amount);
}

/// 元素向左移动,即向更低索引移动。从左侧移出的元素会按相同顺序重新出现在右侧。
pub fn rotateElementsLeft(vec: anytype, comptime amount: VectorCount(@TypeOf(vec))) @TypeOf(vec) {
    return mergeShift(vec, vec, amount);
}

/// 元素向右移动,即向更高索引移动。从右侧移出的元素会按相同顺序重新出现在左侧。
pub fn rotateElementsRight(vec: anytype, comptime amount: VectorCount(@TypeOf(vec))) @TypeOf(vec) {
    return rotateElementsLeft(vec, vectorLength(@TypeOf(vec)) - amount);
}

pub fn reverseOrder(vec: anytype) @TypeOf(vec) {
    const Child = std.meta.Child(@TypeOf(vec));
    const len = vectorLength(@TypeOf(vec));

    return @shuffle(Child, vec, undefined, @as(@Vector(len, i32), @splat(@as(i32, @intCast(len)) - 1)) - iota(i32, len));
}

test "vector shifting" {
    const base = @Vector(4, u32){ 10, 20, 30, 40 };

    try std.testing.expectEqual([4]u32{ 30, 40, 999, 999 }, shiftElementsLeft(base, 2, 999));
    try std.testing.expectEqual([4]u32{ 999, 999, 10, 20 }, shiftElementsRight(base, 2, 999));
    try std.testing.expectEqual([4]u32{ 20, 30, 40, 10 }, rotateElementsLeft(base, 1));
    try std.testing.expectEqual([4]u32{ 40, 10, 20, 30 }, rotateElementsRight(base, 1));
    try std.testing.expectEqual([4]u32{ 40, 30, 20, 10 }, reverseOrder(base));
}

pub fn firstTrue(vec: anytype) ?VectorIndex(@TypeOf(vec)) {
    const len = vectorLength(@TypeOf(vec));
    const IndexInt = VectorIndex(@TypeOf(vec));

    if (!@reduce(.Or, vec)) {
        return null;
    }
    const all_max: @Vector(len, IndexInt) = @splat(~@as(IndexInt, 0));
    const indices = @select(IndexInt, vec, iota(IndexInt, len), all_max);
    return @reduce(.Min, indices);
}

pub fn lastTrue(vec: anytype) ?VectorIndex(@TypeOf(vec)) {
    const len = vectorLength(@TypeOf(vec));
    const IndexInt = VectorIndex(@TypeOf(vec));

    if (!@reduce(.Or, vec)) {
        return null;
    }

    const all_zeroes: @Vector(len, IndexInt) = @splat(0);
    const indices = @select(IndexInt, vec, iota(IndexInt, len), all_zeroes);
    return @reduce(.Max, indices);
}

pub fn countTrues(vec: anytype) VectorCount(@TypeOf(vec)) {
    const len = vectorLength(@TypeOf(vec));
    const CountIntType = VectorCount(@TypeOf(vec));

    const all_ones: @Vector(len, CountIntType) = @splat(1);
    const all_zeroes: @Vector(len, CountIntType) = @splat(0);

    const one_if_true = @select(CountIntType, vec, all_ones, all_zeroes);
    return @reduce(.Add, one_if_true);
}

pub fn firstIndexOfValue(vec: anytype, value: std.meta.Child(@TypeOf(vec))) ?VectorIndex(@TypeOf(vec)) {
    const V = @TypeOf(vec);

    return firstTrue(vec == @as(V, @splat(value)));
}

pub fn lastIndexOfValue(vec: anytype, value: std.meta.Child(@TypeOf(vec))) ?VectorIndex(@TypeOf(vec)) {
    const V = @TypeOf(vec);

    return lastTrue(vec == @as(V, @splat(value)));
}

pub fn countElementsWithValue(vec: anytype, value: std.meta.Child(@TypeOf(vec))) VectorCount(@TypeOf(vec)) {
    const V = @TypeOf(vec);

    return countTrues(vec == @as(V, @splat(value)));
}

test "vector searching" {
    const base = @Vector(8, u32){ 6, 4, 7, 4, 4, 2, 3, 7 };

    try std.testing.expectEqual(@as(?u3, 1), firstIndexOfValue(base, 4));
    try std.testing.expectEqual(@as(?u3, 4), lastIndexOfValue(base, 4));
    try std.testing.expectEqual(@as(?u3, null), lastIndexOfValue(base, 99));
    try std.testing.expectEqual(@as(u4, 3), countElementsWithValue(base, 4));
}

/// 与 prefixScan 相同,但使用用户提供、数学上满足结合律的函数。
pub fn prefixScanWithFunc(
    comptime hop: isize,
    vec: anytype,
    /// `func` 可能返回的错误类型。若 `func` 不返回错误联合体,则设为 `void`。
    comptime ErrorType: type,
    comptime func: fn (@TypeOf(vec), @TypeOf(vec)) if (ErrorType == void) @TypeOf(vec) else ErrorType!@TypeOf(vec),
    /// 当 `func` 所执行操作的某一操作数为此值时,结果必须等于另一操作数。
    /// 例如,加法应使用 0,乘法应使用 1。
    comptime identity: std.meta.Child(@TypeOf(vec)),
) if (ErrorType == void) @TypeOf(vec) else ErrorType!@TypeOf(vec) {
    const len = vectorLength(@TypeOf(vec));

    if (hop == 0) @compileError("hop can not be 0; you'd be going nowhere forever!");
    const abs_hop = if (hop < 0) -hop else hop;

    var acc = vec;
    comptime var i = 0;
    inline while ((abs_hop << i) < len) : (i += 1) {
        const shifted = if (hop < 0) shiftElementsLeft(acc, abs_hop << i, identity) else shiftElementsRight(acc, abs_hop << i, identity);

        acc = if (ErrorType == void) func(acc, shifted) else try func(acc, shifted);
    }
    return acc;
}

/// 返回向量,其中各元素为对输入向量对应元素及其之前每隔 hop 个位置的元素执行指定操作的结果;若 hop 为负,则使用之后的元素。
/// 支持与 @reduce() 内置函数相同的操作,计算需要 O(logN) 时间。
/// 扫描并非线性进行,可能影响浮点误差,进而影响使用此函数的算法的确定性。
///
///
pub fn prefixScan(comptime op: std.builtin.ReduceOp, comptime hop: isize, vec: anytype) @TypeOf(vec) {
    const VecType = @TypeOf(vec);
    const Child = std.meta.Child(VecType);

    const identity = comptime switch (@typeInfo(Child)) {
        .bool => switch (op) {
            .Or, .Xor => false,
            .And => true,
            else => @compileError("Invalid prefixScan operation " ++ @tagName(op) ++ " for vector of booleans."),
        },
        .int => switch (op) {
            .Max => std.math.minInt(Child),
            .Add, .Or, .Xor => 0,
            .Mul => 1,
            .And, .Min => std.math.maxInt(Child),
        },
        .float => switch (op) {
            .Max => -std.math.inf(Child),
            .Add => 0,
            .Mul => 1,
            .Min => std.math.inf(Child),
            else => @compileError("Invalid prefixScan operation " ++ @tagName(op) ++ " for vector of floats."),
        },
        else => @compileError("Invalid type " ++ @typeName(VecType) ++ " for prefixScan."),
    };

    const fn_container = struct {
        fn opFn(a: VecType, b: VecType) VecType {
            return if (Child == bool) switch (op) {
                .And => @select(bool, a, b, @as(VecType, @splat(false))),
                .Or => @select(bool, a, @as(VecType, @splat(true)), b),
                .Xor => a != b,
                else => unreachable,
            } else switch (op) {
                .And => a & b,
                .Or => a | b,
                .Xor => a ^ b,
                .Add => a + b,
                .Mul => a * b,
                .Min => @min(a, b),
                .Max => @max(a, b),
            };
        }
    };

    return prefixScanWithFunc(hop, vec, void, fn_container.opFn, identity);
}

test "vector prefix scan" {
    const int_base = @Vector(4, i32){ 11, 23, 9, -21 };
    const float_base = @Vector(4, f32){ 2, 0.5, -10, 6.54321 };
    const bool_base = @Vector(4, bool){ true, false, true, false };

    const ones: @Vector(32, u8) = @splat(1);

    try std.testing.expectEqual(iota(u8, 32) + ones, prefixScan(.Add, 1, ones));
    try std.testing.expectEqual(@Vector(4, i32){ 11, 3, 1, 1 }, prefixScan(.And, 1, int_base));
    try std.testing.expectEqual(@Vector(4, i32){ 11, 31, 31, -1 }, prefixScan(.Or, 1, int_base));
    try std.testing.expectEqual(@Vector(4, i32){ 11, 28, 21, -2 }, prefixScan(.Xor, 1, int_base));
    try std.testing.expectEqual(@Vector(4, i32){ 11, 34, 43, 22 }, prefixScan(.Add, 1, int_base));
    try std.testing.expectEqual(@Vector(4, i32){ 11, 253, 2277, -47817 }, prefixScan(.Mul, 1, int_base));
    try std.testing.expectEqual(@Vector(4, i32){ 11, 11, 9, -21 }, prefixScan(.Min, 1, int_base));
    try std.testing.expectEqual(@Vector(4, i32){ 11, 23, 23, 23 }, prefixScan(.Max, 1, int_base));

    // 试图预测 prefixScans 对浮点数进行加法和乘法时的所有误差会非常复杂,因此不测试这些情况。
    try std.testing.expectEqual(@Vector(4, f32){ 2, 0.5, -10, -10 }, prefixScan(.Min, 1, float_base));
    try std.testing.expectEqual(@Vector(4, f32){ 2, 2, 2, 6.54321 }, prefixScan(.Max, 1, float_base));

    try std.testing.expectEqual(@Vector(4, bool){ true, true, false, false }, prefixScan(.Xor, 1, bool_base));
    try std.testing.expectEqual(@Vector(4, bool){ true, true, true, true }, prefixScan(.Or, 1, bool_base));
    try std.testing.expectEqual(@Vector(4, bool){ true, false, false, false }, prefixScan(.And, 1, bool_base));

    try std.testing.expectEqual(@Vector(4, i32){ 11, 23, 20, 2 }, prefixScan(.Add, 2, int_base));
    try std.testing.expectEqual(@Vector(4, i32){ 22, 11, -12, -21 }, prefixScan(.Add, -1, int_base));
    try std.testing.expectEqual(@Vector(4, i32){ 11, 23, 9, -10 }, prefixScan(.Add, 3, int_base));
}