lib.no

/// a hint function (unconstrained) to extracts the `nth` bit from a given `value`.
/// Its current implementation points to `std::bits::nth_bit`. So it has an empty body in definition.
/// 
/// # Parameters
/// - `value`: The `Field` value from which to extract the bit.
/// - `nth`: The position of the bit to extract (0-indexed).
/// 
/// # Returns
/// - `Field`: The value of the `nth` bit (0 or 1).
/// 
hint fn nth_bit(value: Field, const nth: Field) -> Field;

/// A `Field` value representing a bit.
/// Use `Bit.new` to create with a range-checked value.
struct Bit {
    inner: Field,
}

/// Creates a `Bit` without any range check on `val`.
fn Bit.new_unchecked(val: Field) -> Bit {
    return Bit {
        inner: val
    };
}

/// Creates a `Bit` with a range check on `val` so that it must be `0` or `1`.
///
/// # Panics
/// - `val` is neither `0` nor `1`.
fn Bit.new(val: Field) -> Bit {
    assert_eq(val * (val - 1), 0);

    return Bit.new_unchecked(val);
}

/// Converts to a boolean.
///
/// # Returns
/// - `Bool`: `true` if value is `1` and `false` otherwise.
fn Bit.to_bool(self) -> Bool {
    return self.inner == 1;
}

/// Converts an array of boolean values (`bits`) into a `Field` value.
///
/// # Parameters
/// - `bits`: An array of `Bool` values representing bits, where each `true` represents `1` and `false` represents `0`.
///
/// # Returns
/// - `Field`: A `Field` value that represents the integer obtained from the binary representation of `bits`.
///
/// # Example
/// ```
/// let bits = [true, false, true]; // Represents the binary value 101
/// let result = from_bits(bits);
/// `result` should be 5 as 101 in binary equals 5 in decimal.
/// ```
fn from_bits(bits: [Bool; LEN]) -> Field {
    let mut lc1 = 0;
    let mut e2 = 1;
    let zero = 0;

    for index in 0..LEN {
        lc1 = lc1 + if bits[index] { e2 } else { zero };
        e2 = e2 + e2;
    }
    return lc1;
}

/// Converts a `Field` value into an array of boolean values (`bits`) representing its binary form.
///
/// # Parameters
/// - `LEN`: The length of the resulting bit array. Determines how many bits are considered in the conversion.
/// - `value`: The `Field` value to convert into binary representation.
///
/// # Returns
/// - `[Bool; LEN]`: An array of boolean values where each `true` represents `1` and `false` represents `0`.
///
/// # Example
/// ```
/// let value = 5; // Binary representation: 101
/// let bits = to_bits(3, value);
/// `bits` should be [true, false, true] corresponding to the binary 101.
/// ```
/// 
/// # Panics
/// - The function asserts that `from_bits(bits)` equals `value`, ensuring the conversion is correct.
fn to_bits(const LEN: Field, value: Field) -> [Bool; LEN] {
    let mut bits = [false; LEN];

    for index in 0..LEN {
        let bit_num = unsafe nth_bit(value, index);
        
        // constrain the bit values to booleans
        let bit = Bit.new_unchecked(bit_num);
        bits[index] = bit.to_bool();
    }

    // constrain the accumulative contributions of bits to be equal to the value
    assert_eq(from_bits(bits), value);

    return bits;
}