Bitwise Calculator — C source

/* =============================================================================
 *  bitwise.c — CosmoDev polyglot showcase port of the `bitwise` tool
 *  -----------------------------------------------------------------------------
 *  Language : C (C11, 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.
 *
 *  C note: the TS source uses arbitrary-precision `bigint`. C11 has no bignum
 *  type, so values live in int64_t/uint64_t. This stays exact for every
 *  supported width (8/16/32/64): parsed magnitudes fold through two's-
 *  complement wrapping (invisible after width-bit normalization), and shift/
 *  rotate intermediates pre-mask the operand so nothing exceeds 64 bits —
 *  arithmetically identical to the reference's masked bigint shifts. Only
 *  literals beyond 2^64-1 diverge from the TS lib (reported as a clean parse
 *  error), far outside any realistic bitwise-calculator input.
 * ========================================================================== */

#include <ctype.h>
#include <stdarg.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

/* Numeric base for parsing and formatting bit patterns. */
typedef enum {
    BITWISE_BIN = 0,
    BITWISE_OCT,
    BITWISE_DEC,
    BITWISE_HEX
} bitwise_base;

/* Supported bitwise operation. `not` is unary on `a`; the binary ops take `a`
 * and `b`; for the shift/rotate ops `b` is the count. */
typedef enum {
    BITWISE_AND = 0,
    BITWISE_OR,
    BITWISE_XOR,
    BITWISE_NOT,
    BITWISE_SHL,
    BITWISE_SHR,
    BITWISE_ROL,
    BITWISE_ROR
} bitwise_op;

/* Operating field width, in bits: one of 8, 16, 32, 64. */
typedef uint32_t bitwise_width;

/* Positional radix (2/8/10/16) consumed by the parser/formatter. */
static uint32_t bitwise_radix(bitwise_base base) {
    switch (base) {
    case BITWISE_BIN: return 2;
    case BITWISE_OCT: return 8;
    case BITWISE_DEC: return 10;
    case BITWISE_HEX: return 16;
    }
    return 10;
}

/* Lowercase digit alphabet valid for each base — drives validation and the
 * per-character digit-value lookup. */
static const char *bitwise_digits(bitwise_base base) {
    switch (base) {
    case BITWISE_BIN: return "01";
    case BITWISE_OCT: return "01234567";
    case BITWISE_DEC: return "0123456789";
    case BITWISE_HEX: return "0123456789abcdef";
    }
    return "0123456789";
}

/* Lowercase name, for error messages that match the TS lib. */
static const char *bitwise_base_lower(bitwise_base base) {
    switch (base) {
    case BITWISE_BIN: return "bin";
    case BITWISE_OCT: return "oct";
    case BITWISE_DEC: return "dec";
    case BITWISE_HEX: return "hex";
    }
    return "dec";
}

/* Store a diagnostic message into the caller's error buffer (best-effort). */
static void bitwise_set_err(char *err, size_t err_len, const char *fmt, ...) {
    if (err == NULL || err_len == 0)
        return;
    va_list ap;
    va_start(ap, fmt);
    vsnprintf(err, err_len, fmt, ap);
    va_end(ap);
}

/*
 * Parse a numeric string in `base` into a signed 64-bit integer, storing it in
 * *out. Accepts an optional leading sign and a single optional base prefix
 * (0x/0b/0o, case-insensitive). Returns 0 on success, or -1 with a message in
 * `err` (never NULL; may be NULL to skip diagnostics) on empty input, any digit
 * invalid for the requested base, or a literal whose magnitude exceeds 2^64-1.
 * The raw signed value is returned (no width normalization); callers fold it
 * into a field via bitwise_normalize() / bitwise_bitwise().
 *
 * Magnitudes are accumulated as uint64_t and negated by wrapping subtraction,
 * so the full unsigned range (e.g. hex 0xFFFFFFFFFFFFFFFF) round-trips exactly
 * — a wrap of 2^64 is invisible once the value is width-normalized.
 */
int bitwise_parse(const char *value, bitwise_base base, int64_t *out,
                  char *err, size_t err_len) {
    *out = 0;

    /* Trim ASCII whitespace from both ends. */
    while (*value == ' ' || *value == '\t' || *value == '\n' || *value == '\r')
        value++;
    size_t len = strlen(value);
    while (len > 0 && (value[len - 1] == ' ' || value[len - 1] == '\t' ||
                       value[len - 1] == '\n' || value[len - 1] == '\r'))
        len--;

    /* Peel off an optional leading '-' so negative literals parse correctly. */
    int negative = 0;
    if (len > 0 && value[0] == '-') {
        negative = 1;
        value++;
        len--;
    }
    if (len == 0) {
        bitwise_set_err(err, err_len, "Empty %s value", bitwise_base_lower(base));
        return -1;
    }

    /* Lowercase copy: keeps an uppercase mantissa like "0xFF" valid, mirroring
     * the reference's chained prefix removal over a lowered string. Any string
     * longer than this buffer cannot fit in 64 bits anyway. */
    char buf[128];
    if (len >= sizeof buf) {
        bitwise_set_err(err, err_len, "Value out of range for base %s",
                        bitwise_base_lower(base));
        return -1;
    }
    for (size_t i = 0; i < len; i++)
        buf[i] = (char)tolower((unsigned char)value[i]);
    buf[len] = '\0';

    /* Strip each base prefix in turn (0x, then 0b, then 0o) — mirrors the
     * reference's chained leading-prefix removal. */
    static const char *const prefixes[] = {"0x", "0b", "0o"};
    for (size_t i = 0; i < sizeof prefixes / sizeof prefixes[0]; i++) {
        size_t plen = strlen(prefixes[i]);
        if (strncmp(buf, prefixes[i], plen) == 0)
            memmove(buf, buf + plen, strlen(buf) + 1 - plen);
    }
    if (buf[0] == '\0') {
        bitwise_set_err(err, err_len, "Empty %s value", bitwise_base_lower(base));
        return -1;
    }

    /* Horner's method over the digit alphabet, with a checked accumulate:
     * an over-wide literal reports a clean error instead of wrapping. */
    const char *alphabet = bitwise_digits(base);
    uint32_t radix = bitwise_radix(base);
    uint64_t acc = 0;
    for (const char *p = buf; *p != '\0'; p++) {
        const char *hit = strchr(alphabet, *p);
        if (hit == NULL) {
            bitwise_set_err(err, err_len, "Invalid digit '%c' for base %s",
                            *p, bitwise_base_lower(base));
            return -1;
        }
        uint64_t digit = (uint64_t)(hit - alphabet);
        if (acc > (UINT64_MAX - digit) / radix) {
            bitwise_set_err(err, err_len, "Value out of range for base %s",
                            bitwise_base_lower(base));
            return -1;
        }
        acc = acc * radix + digit;
    }

    /* Wrapping negate is exact mod 2^64 (all target platforms are two's
     * complement); the (int64_t) cast reinterprets the pattern as signed. */
    *out = negative ? (int64_t)(UINT64_C(0) - acc) : (int64_t)acc;
    return 0;
}

/*
 * Bitmask for a `width`-bit field: 2^width - 1. Width 64 is spelled directly
 * because 1 << 64 would overflow uint64_t.
 */
uint64_t bitwise_mask(bitwise_width width) {
    return width == 64 ? UINT64_MAX : ((UINT64_C(1) << 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 on arbitrary-
 * precision ints; casting to uint64_t already yields n mod 2^64 (two's-
 * complement truncation), and ANDing with the width-bit mask reduces that to
 * n mod 2^width — the same canonical value, without materializing 2^64 itself.
 */
uint64_t bitwise_normalize(int64_t n, bitwise_width width) {
    return (uint64_t)n & bitwise_mask(width);
}

/*
 * Render an unsigned value in `base`, zero-padded to at least `min_digits`
 * places, into `buf`. Returns 0 on success, -1 if the buffer is too small
 * (a width-64 binary value needs 65 bytes including the NUL).
 * Manual base conversion keeps the port stdlib-only and yields the lowercase
 * digits of the TS `bigint.toString(radix)` output.
 */
static int bitwise_format_u64(uint64_t v, bitwise_base base, size_t min_digits,
                              char *buf, size_t buf_size) {
    static const char alphabet[] = "0123456789abcdef";
    uint32_t radix = bitwise_radix(base);

    /* Extract digits LSB-first; the do/while renders "0" for zero naturally. */
    char tmp[64];
    size_t nd = 0;
    do {
        tmp[nd++] = alphabet[v % radix];
        v /= radix;
    } while (v != 0);

    size_t digits = nd > min_digits ? nd : min_digits;
    if (digits + 1 > buf_size)
        return -1;

    char *w = buf;
    for (size_t i = nd; i < digits; i++)
        *w++ = '0'; /* zero-pad up to the minimum width */
    while (nd > 0)
        *w++ = tmp[--nd];
    *w = '\0';
    return 0;
}

/*
 * Render `n` in `base`, zero-padded to at least `min_digits` places, into
 * `buf`. Negative values carry a leading '-' and format their magnitude
 * (computed with wrapping subtraction — exact and INT64_MIN-safe).
 * `min_digits` corresponds to the `width` parameter of the TS reference
 * (a width-bit binary value needs exactly `width` digits).
 */
int bitwise_format(int64_t n, bitwise_base base, size_t min_digits,
                   char *buf, size_t buf_size) {
    if (n < 0) {
        uint64_t mag = (uint64_t)0 - (uint64_t)n;
        char tmp[65]; /* 64 digits + NUL */
        if (bitwise_format_u64(mag, base, min_digits, tmp, sizeof tmp) != 0)
            return -1;
        size_t len = strlen(tmp);
        if (len + 2 > buf_size) /* '-' + digits + NUL */
            return -1;
        buf[0] = '-';
        memcpy(buf + 1, tmp, len + 1);
        return 0;
    }
    return bitwise_format_u64((uint64_t)n, base, min_digits, buf, buf_size);
}

/*
 * 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 `width`:
 * every significant bit is shifted out, so the masked result is zero (this
 * also keeps every shift amount below 64 — C leaves shifts >= 64 undefined).
 * For shl/rol the shifted operand is pre-masked with (mask >> count): the low
 * `width` bits of the true bigint shift are identical, but the intermediate
 * can no longer exceed 64 bits.
 */
uint64_t bitwise_bitwise(bitwise_op op, int64_t a, int64_t b, bitwise_width width) {
    uint64_t m = bitwise_mask(width);
    uint64_t x = bitwise_normalize(a, width);
    uint64_t y = bitwise_normalize(b, width);

    switch (op) {
    case BITWISE_AND:
        return x & y;
    case BITWISE_OR:
        return x | y;
    case BITWISE_XOR:
        return x ^ y;
    case BITWISE_NOT:
        return ~x & m;
    case BITWISE_SHL:
        if (y >= width)
            return 0;
        return (x & (m >> y)) << y; /* == (x << y) & m, without overflow */
    case BITWISE_SHR:
        /* x is normalized non-negative → logical (zero-filling) shift. */
        return y >= width ? 0 : x >> y;
    case BITWISE_ROL:
    case BITWISE_ROR: {
        uint64_t shift = y % width; /* rotate amount wraps within width */
        if (shift == 0)
            return x;
        /* A right-rotate by `shift` is a left-rotate by (width - shift). */
        uint64_t s = (op == BITWISE_ROL) ? shift : (uint64_t)width - shift;
        return ((x & (m >> s)) << s) | (x >> (width - s));
    }
    }
    return 0; /* unreachable with a valid op */
}

/*
 * Fixed-width binary string of `width` bits (MSB first), into `buf`.
 * Formats the unsigned normalized pattern directly: a width-64 pattern can
 * exceed INT64_MAX and must not round-trip through the signed path.
 */
int bitwise_to_bits(int64_t n, bitwise_width width, char *buf, size_t buf_size) {
    return bitwise_format_u64(bitwise_normalize(n, width), BITWISE_BIN, width,
                              buf, buf_size);
}

/*
 * Indices of set bits (LSB = index 0), normalized to `width`, written to `out`
 * in ascending order. `out` must have room for `width` entries; returns the
 * number of indices written (the loop stops at the highest set bit, so at
 * most `width` — and usually far fewer — are written).
 */
size_t bitwise_flags(int64_t n, bitwise_width width, uint32_t *out, size_t cap) {
    uint64_t v = bitwise_normalize(n, width);
    size_t count = 0;
    uint32_t i = 0;
    while (v != 0) {
        if (v & 1) {
            if (count < cap)
                out[count] = i;
            count++;
        }
        v >>= 1;
        i++;
    }
    return count;
}