tiny.simd.ShuffledIota

1pub const ShuffledIota = struct {2    coprime: u32 = 1,34    pub fn init(coprime: u32) ShuffledIota {5        return .{ .coprime = coprime };6    }78    pub fn next(9        self: ShuffledIota,10        current: u32,11        size: u32,12    ) u32 {13        std.debug.assert(size != 0);14        std.debug.assert(current < size);15        return @intCast(16            (@as(u64, current) + self.coprime) % @as(u64, size),17        );18    }1920    pub fn coprimeNonzero(a_value: u32, b_value: u32) bool {21        std.debug.assert(a_value != 0);22        std.debug.assert(b_value != 0);23        var a = a_value;24        var b = b_value;25        const trailing_a = @ctz(a);26        const trailing_b = @ctz(b);27        if (@min(trailing_a, trailing_b) != 0) return false;28        a >>= @intCast(trailing_a);29        b >>= @intCast(trailing_b);30        while (true) {31            const previous_a = a;32            a = @max(previous_a, b);33            b = @min(previous_a, b);34            if (b == 1) return true;35            a -= b;36            if (a == 0) return false;37            a >>= @intCast(@ctz(a));38        }39    }4041    pub fn findAnotherCoprime(size: u32, start: u32) u32 {42        std.debug.assert(size != 0);43        if (size <= 2) return 1;44        const increment: u32 = if (size & 1 == 0) 2 else 1;45        var candidate = start | 1;46        var attempts: u64 = 0;47        const max_attempts = @as(u64, size) * 16;48        while (attempts < max_attempts) : (attempts += 1) {49            if (coprimeNonzero(candidate, size)) return candidate;50            candidate +%= increment;51            if (candidate == 0) candidate = 1;52        }53        unreachable;54    }55};

1pub const ShuffledIota = thread.ShuffledIota;