Validark

PDEP Visualization PEXT Visualization

Here is an overview of which ISA's support these instructions:

• BESM Soviet mainframes:
  • BESM-6 (Designed in 1965. Produced 1968-1987) => AUX & APX
• x86-64:
  • BMI2 (Intel Haswell 2013+, AMD Excavator 2015+, Fast on AMD since Zen 3 2020+) => PDEP & PEXT
• arm64 / aarch64:

Validark

fn swarGe(x: anytype, y: @TypeOf(x)) @TypeOf(x) {
    const msb: @TypeOf(x) = @bitCast(@as(@Vector(@sizeOf(@TypeOf(x)), u8), @splat(0x80)));
    return (((x ^ y) & x) | (~(x ^ y) & ((x | msb) -% (y & ~msb))));
}

fn swarLe(x: anytype, y: @TypeOf(x)) @TypeOf(x) {
    return swarGe(y, x);
}

fn swarEq(x: anytype, y: @TypeOf(x)) @TypeOf(x) {

Validark

const std = @import("std");

export fn columnCountsVec(chunk: @Vector(16, u8)) @TypeOf(chunk) {
    var mask = chunk != @as(@TypeOf(chunk), @splat('\n'));
    var array_count = @select(u8, mask, @as(@TypeOf(chunk), @splat(1)), @as(@TypeOf(chunk), @splat(0)));

    inline for (0..std.math.log2(@sizeOf(@TypeOf(chunk)))) |i| {
        array_count = @select(u8, mask, array_count +% std.simd.shiftElementsRight(array_count, 1 << i, 0), array_count);
        mask = @select(bool, mask, std.simd.shiftElementsRight(mask, 1 << i, false), @as(@TypeOf(mask), @splat(false)));
    }

Validark

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

const HAS_FAST_PDEP_AND_PEXT = blk: {
    const cpu_name = builtin.cpu.model.llvm_name orelse builtin.cpu.model.name;
    break :blk builtin.cpu.arch == .x86_64 and
        std.Target.x86.featureSetHas(builtin.cpu.features, .bmi2) and
        // pdep is microcoded (slow) on AMD architectures before Zen 3.
        !std.mem.startsWith(u8, cpu_name, "bdver") and
        (!std.mem.startsWith(u8, cpu_name, "znver") or cpu_name["znver".len] >= '3');

Validark

const std = @import("std");
const builtin = @import("builtin");
const assert = std.debug.assert;

inline fn pdep(src: u64, mask: u64) u64 {
    return asm ("pdep %[mask], %[src], %[ret]"
        : [ret] "=r" (-> u64),
        : [src] "r" (src),
          [mask] "r" (mask),
    );

Validark

inline fn pext(src: anytype, mask: @TypeOf(src)) @TypeOf(src) {
    switch (@TypeOf(src)) {
        u32, u64 => {},
        else => @compileError(std.fmt.comptimePrint("pext called with a bad type: {}\n", .{@TypeOf(src)})),
    }

    if (@inComptime()) {
        @setEvalBranchQuota(std.math.maxInt(u32));
        var result: @TypeOf(src) = 0;
        var m = mask;

Validark

/// Given a bitmask, will return a mask where the bits are filled in between.
/// On modern x86 and aarch64 CPU's, it should have a latency of 3 and a throughput of 1.
pub fn prefix_xor(bitmask: u64) u64 {
    const impl: enum { x86, aarch64, agnostic } =
        // There should be no such thing with a processor supporting avx2 but not clmul.
        comptime if (builtin.cpu.arch == .x86_64 and
        std.Target.x86.featureSetHas(builtin.cpu.features, .pclmul) and
        std.Target.x86.featureSetHas(builtin.cpu.features, .avx2))
        .x86
    else if (builtin.cpu.arch == .aarch64 and std.Target.aarch64.featureSetHas(builtin.cpu.features, .aes))

Validark

fn pdep(src: u64, mask: u64) u64 {
    return asm ("pdep %[mask], %[src], %[ret]"
        : [ret] "=r" (-> u64),
        : [src] "r" (src),
          [mask] "r" (mask),
    );
}

fn select(x: u64, k: u6) u6 {
    @setRuntimeSafety(false);

Validark

-- @author Validark
-- Solves Shifted geometric recursive formulae

local function Recurse(U_0, r, d, i, seq)
	--- Finds a value in a shifted geometric recursive formula
	-- @param number U_0 The starting value
	-- @param number r The common ratio
	-- @param number d The common difference
	-- @param number i The index of the desired value in the sequence
	-- @param number seq = 1 Either 1 or 2

Validark

-- We can re-use metatables where possible
local lookupCache = {
	__index = function(self, i)
		local v = { __index = i }
		self[i] = v
		return v
	end
}

local function use_aho_corasick(automaton, str)