Bitwise Calculator — Zig source

// =============================================================================
//  zig.zig — CosmoDev polyglot showcase port of the `bitwise` tool
//  -----------------------------------------------------------------------------
//  Language : Zig (0.13, standard library only)
//  Source:   ported from src/lib/bitwise.ts (the canonical, live TypeScript
//             lib); mirrors src/tool-sources/bitwise/{python.py,rust.rs}
//  License  : display source — part of CosmoDev's polyglot tool pages
//             (dev.cosmolabs.org). Shown verbatim alongside the JS/TS/Go/Rust/
//             Python ports and the other language ports.
//  -----------------------------------------------------------------------------
//  Pure, deterministic bitwise calculator. Zero deps. Operands are interpreted
//  as width-bit two's-complement values: any integer is normalized to the
//  half-open range [0, 2^width) before an operation, and every result is masked
//  back into that range — so the returned integer is always the unsigned
//  bit-pattern of the width-bit result.
//
//  Zig note: the TS source uses arbitrary-precision `bigint`. Zig has built-in
//  i128/u128, so signed parsing uses i128 and masked results use u128 — the
//  same approach as the Rust port. This is exact for every supported width
//  (8/16/32/64) and for all shift intermediates. Only literals beyond ~1.7e38
//  diverge from the TS lib (a clean error.ValueOutOfRange), far outside any
//  realistic bitwise-calculator input.
//
//  Zig errors cannot carry payloads, so the Rust port's messages become the
//  tagged error names below (the base is recoverable from the argument).
//  @"and"/@"or"/@"not" are quoted because the bare spellings are (or risk
//  becoming) Zig keywords.
// =============================================================================

const std = @import("std");

/// Numeric radix used for parsing and formatting.
pub const Base = enum {
    bin,
    oct,
    dec,
    hex,

    /// Positional radix (2/8/10/16).
    pub fn radix(self: Base) u8 {
        return switch (self) {
            .bin => 2,
            .oct => 8,
            .dec => 10,
            .hex => 16,
        };
    }

    /// Lowercase digit alphabet valid for this base.
    pub fn digits(self: Base) []const u8 {
        return switch (self) {
            .bin => "01",
            .oct => "01234567",
            .dec => "0123456789",
            .hex => "0123456789abcdef",
        };
    }

    /// Lowercase name, for diagnostics that match the TS lib's messages.
    pub fn lower(self: Base) []const u8 {
        return switch (self) {
            .bin => "bin",
            .oct => "oct",
            .dec => "dec",
            .hex => "hex",
        };
    }
};

/// Bit-width of the virtual register (8/16/32/64).
pub const Width = u32;

/// Supported bitwise operation. `.not` is unary on `a`; the rest are binary,
/// with `b` as the shift/rotate count for the shift/rotate ops.
pub const Op = enum {
    @"and",
    @"or",
    xor,
    @"not",
    shl,
    shr,
    rol,
    ror,
};

/// Parse failure: empty input (`EmptyValue`, also covers a bare "-"), a digit
/// outside the requested base (`InvalidDigit`), or a literal that overflows
/// i128 (`ValueOutOfRange`).
pub const ParseError = error{
    EmptyValue,
    InvalidDigit,
    ValueOutOfRange,
};

/// Parse a numeric string in `base` into a signed integer. Strips 0x/0b/0o
/// prefixes and an optional leading sign. The raw signed value is returned
/// (no width normalization); callers fold it into a field via `normalize` /
/// `bitwise`.
pub fn parse(value: []const u8, base: Base) ParseError!i128 {
    const trimmed = std.mem.trim(u8, value, " \t\n\r");
    if (trimmed.len == 0)
        return error.EmptyValue;

    // Peel off an optional leading '-' so negative literals parse correctly.
    var negative = false;
    var body: []const u8 = trimmed;
    if (body[0] == '-') {
        negative = true;
        body = body[1..];
    }
    if (body.len == 0) // a bare "-"
        return error.EmptyValue;

    // Strip each base prefix in turn (0x, then 0b, then 0o) from a lowered
    // copy — mirrors the reference's chained leading-prefix removal.
    // Matching against the lowercased copy keeps "0xFF" valid.
    var lbuf: [128]u8 = undefined;
    if (body.len > lbuf.len)
        return error.ValueOutOfRange; // cannot fit i128 anyway
    const lowered = std.ascii.lowerString(&lbuf, body);
    var digit_str = lowered;
    const prefixes = [_][]const u8{ "0x", "0b", "0o" };
    for (prefixes) |prefix| {
        if (std.mem.startsWith(u8, digit_str, prefix))
            digit_str = digit_str[prefix.len..];
    }
    if (digit_str.len == 0)
        return error.EmptyValue;

    // Horner's method over the digit alphabet, with checked arithmetic:
    // an over-wide literal reports a clean error instead of overflowing.
    const allowed = base.digits();
    const radix: i128 = base.radix();
    var acc: i128 = 0;
    for (digit_str) |ch| {
        const idx = std.mem.indexOfScalar(u8, allowed, ch) orelse
            return error.InvalidDigit;
        const digit: i128 = idx;
        const mul = @mulWithOverflow(acc, radix);
        if (mul[1] != 0)
            return error.ValueOutOfRange;
        const add = @addWithOverflow(mul[0], digit);
        if (add[1] != 0)
            return error.ValueOutOfRange;
        acc = add[0];
    }

    return if (negative) -acc else acc;
}

/// Mask for a `width`-bit field: 2^width - 1. (Valid for width <= 127.)
pub fn mask(width: Width) u128 {
    return (@as(u128, 1) << @intCast(width)) - 1;
}

/// Normalize any signed value to its unsigned width-bit two's-complement
/// value, i.e. into the half-open range [0, 2^width) — e.g. -1 at width 8
/// yields 255. The reference computes ((n % m) + m) % m with m = 2^width;
/// Zig's @mod is floored (result takes the divisor's sign), so a single
/// application over a positive divisor produces the same canonical value.
pub fn normalize(n: i128, width: Width) u128 {
    const m: i128 = @as(i128, 1) << @intCast(width); // 2^width (fits i128 for width <= 126)
    return @intCast(@mod(n, m));
}

/// Format `n` in `base`, zero-padded to at least `min_digits` digits, into a
/// freshly allocated string. Negatives carry a leading '-' and format their
/// magnitude. (The third arg is a minimum digit count — the binary rendering
/// of a width-bit value needs exactly `width` digits.)
///
/// Manual base conversion keeps parity with the sibling ports and yields the
/// lowercase digits of the TS `bigint.toString(radix)` output.
pub fn format(alloc: std.mem.Allocator, n: i128, base: Base, min_digits: usize) std.mem.Allocator.Error![]u8 {
    if (n < 0) {
        // Format the magnitude and prepend the sign. The (-(n+1))+1 form
        // negates safely even at i128 min.
        const mag: u128 = @intCast(-(n + 1));
        const body = try format_unsigned(alloc, mag + 1, base, min_digits);
        defer alloc.free(body);
        const out = try alloc.alloc(u8, body.len + 1);
        out[0] = '-';
        @memcpy(out[1..], body);
        return out;
    }
    return format_unsigned(alloc, @intCast(n), base, min_digits);
}

// Extract digits LSB-first; the loop renders "0" for zero naturally.
fn format_unsigned(alloc: std.mem.Allocator, v_in: u128, base: Base, min_digits: usize) std.mem.Allocator.Error![]u8 {
    const alphabet = "0123456789abcdef";
    const radix = base.radix();

    var tmp: [128]u8 = undefined; // a 128-bit max is 128 binary digits
    var nd: usize = 0;
    var v = v_in;
    while (true) {
        tmp[nd] = alphabet[@intCast(v % radix)];
        nd += 1;
        v /= radix;
        if (v == 0)
            break;
    }

    const pad = min_digits -| nd; // saturating: no padding when already long enough
    const out = try alloc.alloc(u8, pad + nd);
    var i: usize = 0;
    while (i < pad) : (i += 1)
        out[i] = '0'; // zero-pad up to the minimum
    var j: usize = 0;
    while (j < nd) : (j += 1) {
        out[pad + j] = tmp[nd - 1 - j]; // emit MSB-first
    }
    return out;
}

/// Apply a width-bit operation. `a` is the (unary) operand for `.@"not"`;
/// `b` is the second operand for binary ops and the shift/rotate count for
/// shl/shr/rol/ror. Both operands are normalized to width-bit two's
/// complement first; the result is masked to `width` bits.
///
/// For shl/shr we short-circuit when the shift count meets or exceeds the
/// width: every significant bit is shifted out, so the masked result is zero
/// (this also keeps every shift amount below 128 — Zig left-shifts by >= the
/// type's bit count are illegal behavior).
pub fn bitwise(op: Op, a: i128, b: i128, width: Width) u128 {
    const m = mask(width);
    const x = normalize(a, width);
    const y = normalize(b, width);
    const w: u128 = width;

    return switch (op) {
        .@"and" => x & y,
        .@"or" => x | y,
        .xor => x ^ y,
        .@"not" => ~x & m,
        .shl => if (y >= w) 0 else (x << @intCast(y)) & m,
        // x is normalized non-negative → logical (zero-filling) shift.
        .shr => if (y >= w) 0 else x >> @intCast(y),
        .rol, .ror => blk: {
            const shift = y % w; // rotate amount wraps within width
            if (shift == 0)
                break :blk x;
            // A right-rotate by `shift` is a left-rotate by (width - shift).
            const s = if (op == .rol) shift else w - shift;
            break :blk ((x << @intCast(s)) | (x >> @intCast(w - s))) & m;
        },
    };
}

/// Fixed-width binary string of `width` bits (MSB first), freshly allocated.
/// Formats the unsigned normalized pattern directly: a width-64 pattern can
/// exceed i64 range and must not round-trip through the signed path.
pub fn to_bits(alloc: std.mem.Allocator, n: i128, width: Width) std.mem.Allocator.Error![]u8 {
    return format(alloc, @intCast(normalize(n, width)), .bin, width);
}

/// Indices of set bits (LSB = index 0), normalized to `width`, in ascending
/// order. The caller owns the returned slice. Stops at the highest set bit.
pub fn flags(alloc: std.mem.Allocator, n: i128, width: Width) std.mem.Allocator.Error![]u32 {
    var v = normalize(n, width);
    var tmp: [64]u32 = undefined; // at most `width` (<= 64) indices
    var count: usize = 0;
    var i: u32 = 0;
    while (v != 0) {
        if (v & 1 != 0) {
            tmp[count] = i;
            count += 1;
        }
        v >>= 1;
        i += 1;
    }
    const out = try alloc.alloc(u32, count);
    @memcpy(out, tmp[0..count]);
    return out;
}