// stdlib/crypto/bitops.sy — bitwise operations via arithmetic fallback
//
// TODAY: Scyla has no bitwise operators (& | ^ << >>). These functions
// simulate them using *, /, %. SLOW but correct for sketching Phase 3
// crypto code.
//
// PHASE 3 SWAP: replace every function body with a single VM builtin call
// once §1.1 of CARDEA_PHASE3_PREREQS.md lands. Call sites do not change.
//
// Aislinn McCubbins, Apr 11 2026

// ── Power-of-two helper ──────────────────────────────────
// pow2(n) = 2^n. Used anywhere we'd otherwise write `1 << n`.
fn pow2(n: Int) -> Int {
    let mut r = 1
    let mut i = 0
    while i < n {
        r = r * 2
        i = i + 1
    }
    return r
}

// ── Shifts ───────────────────────────────────────────────
// Arithmetic left shift. Overflow is user's problem (Int is i64-ish).
fn shl(a: Int, n: Int) -> Int {
    return a * pow2(n)
}

// Logical right shift for non-negative a. For negative a, this is
// floor-division, which matches arithmetic shift in two's complement
// on the Rust side — good enough for now.
fn shr(a: Int, n: Int) -> Int {
    return a / pow2(n)
}

// ── Bitwise AND / OR / XOR ───────────────────────────────
// Decompose both operands bit-by-bit via %2 and /2, combine, recompose.
// O(log max(a,b)) per call. Plenty fast for correctness testing;
// unacceptable for production Kyber (NTT calls these in hot loops).

fn bit_and(a: Int, b: Int) -> Int {
    let mut result = 0
    let mut bit = 1
    let mut a_rem = a
    let mut b_rem = b
    while a_rem > 0 || b_rem > 0 {
        let a_bit = a_rem % 2
        let b_bit = b_rem % 2
        if a_bit == 1 && b_bit == 1 {
            result = result + bit
        }
        bit = bit * 2
        a_rem = a_rem / 2
        b_rem = b_rem / 2
    }
    return result
}

fn bit_or(a: Int, b: Int) -> Int {
    let mut result = 0
    let mut bit = 1
    let mut a_rem = a
    let mut b_rem = b
    while a_rem > 0 || b_rem > 0 {
        let a_bit = a_rem % 2
        let b_bit = b_rem % 2
        if a_bit == 1 || b_bit == 1 {
            result = result + bit
        }
        bit = bit * 2
        a_rem = a_rem / 2
        b_rem = b_rem / 2
    }
    return result
}

fn bit_xor(a: Int, b: Int) -> Int {
    let mut result = 0
    let mut bit = 1
    let mut a_rem = a
    let mut b_rem = b
    while a_rem > 0 || b_rem > 0 {
        let a_bit = a_rem % 2
        let b_bit = b_rem % 2
        if a_bit != b_bit {
            result = result + bit
        }
        bit = bit * 2
        a_rem = a_rem / 2
        b_rem = b_rem / 2
    }
    return result
}

// ── Masks ────────────────────────────────────────────────
// Fast path for the common case `x & ((1<<n) - 1)`: just use modulo.
// Phase 3 call sites should prefer this over bit_and when the mask is a
// power-of-two-minus-one, because it's O(1) instead of O(log x).
fn mask_low_bits(x: Int, n: Int) -> Int {
    return x % pow2(n)
}

// Extract the nth bit of x (0 = LSB). Returns 0 or 1.
fn bit_get(x: Int, n: Int) -> Int {
    return (x / pow2(n)) % 2
}
