Returns a vector whose elements are the result of performing the specified operation on the corresponding element of the input vector and every hop'th element that came before it (or after, if hop is negative). Supports the same operations as the @reduce() builtin. Takes O(logN) to compute. The scan is not linear, which may affect floating point errors. This may affect the determinism of algorithms that use this function.
pub fn prefixScan(comptime op: std.builtin.ReduceOp, comptime hop: isize, vec: anytype) @TypeOf(vec)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);
}