arcis-compiler 0.9.4

use crate::{
    core::{
        actually_used_field::ActuallyUsedField,
        bounds::{below_power_of_two, FieldBounds, IsBounds},
        circuits::boolean::boolean_value::{Boolean, BooleanValue},
        compile_passes::new_eda_bit,
        expressions::field_expr::{keep_ls_bounds, shr_bounds, FieldExpr},
        global_value::value::FieldValue,
    },
    traits::{FromLeBits, GetBit, Reveal, Select},
    STATISTICAL_SECURITY_FACTOR,
};
use core::panic;

#[derive(Default)]
pub enum CircuitType {
    #[default]
    DepthOpt,
    #[allow(dead_code)]
    SizeOpt,
}

/// Produces a boolean circuit for the addition of two scalars and a bit.
/// The result is a vector of bits.
pub fn addition_circuit<B: Boolean>(
    bits1: Vec<B>,
    bits2: Vec<B>,
    carry_in: B,
    circuit_type: CircuitType,
) -> Vec<B> {
    if bits1.len() != bits2.len() {
        panic!(
            "bits1 and bits2 must be of same length (found {} and {})",
            bits1.len(),
            bits2.len()
        );
    }
    match circuit_type {
        CircuitType::DepthOpt => {
            if bits1.len().ilog2() >= 10 {
                panic!(
                    "DepthOpt addition_circuit only supported for inputs of at most 1023 bits (found {})",
                    bits1.len()
                );
            }
            addition_circuit_depth_opt_rec(bits1, bits2, carry_in).0
        }
        CircuitType::SizeOpt => addition_circuit_size_opt(bits1, bits2, carry_in),
    }
}

/// Produces a depth opt boolean circuit for the addition of two scalars and a bit.
/// The result is a vector of bits.
fn addition_circuit_depth_opt_rec<B: Boolean>(
    bits1: Vec<B>,
    bits2: Vec<B>,
    carry_in: B,
) -> (Vec<B>, B) {
    if bits1.len() == 1 {
        // r = b1 XOR b2 XOR carry
        let b2_xor_carry = bits2[0] ^ carry_in;
        let r = bits1[0] ^ b2_xor_carry;
        let res = vec![r];
        // carry_out = (b1 AND b2) XOR (b1 AND carry) XOR (b2 AND carry)
        //           = (b2 XOR carry) ? b1 : b2
        let carry_out = b2_xor_carry.select(bits1[0], bits2[0]);
        (res, carry_out)
    } else {
        let half = bits1.len() / 2;
        let lsbits1 = bits1.iter().copied().take(half).collect::<Vec<B>>();
        let msbits1 = bits1.iter().copied().skip(half).collect::<Vec<B>>();
        let lsbits2 = bits2.iter().copied().take(half).collect::<Vec<B>>();
        let msbits2 = bits2.iter().copied().skip(half).collect::<Vec<B>>();
        let (mut res_ls, carry_out_ls) = addition_circuit_depth_opt_rec(lsbits1, lsbits2, carry_in);
        let (res_ms_0, carry_out_ms_0) =
            addition_circuit_depth_opt_rec(msbits1.clone(), msbits2.clone(), B::from(false));
        let (res_ms_1, carry_out_ms_1) =
            addition_circuit_depth_opt_rec(msbits1, msbits2, B::from(true));
        let mut res_ms = carry_out_ls.select(res_ms_1, res_ms_0);
        res_ls.append(&mut res_ms);
        let carry_out = carry_out_ls.select(carry_out_ms_1, carry_out_ms_0);
        (res_ls, carry_out)
    }
}

/// Produces a size opt boolean circuit for the addition of two scalars and a bit.
/// The result is a vector of bits.
fn addition_circuit_size_opt<B: Boolean>(bits1: Vec<B>, bits2: Vec<B>, carry_in: B) -> Vec<B> {
    bits1
        .iter()
        .zip(bits2)
        .scan(carry_in, |carry, (b1, b2)| {
            // r = b1 XOR b2 XOR carry
            let b2_xor_carry = b2 ^ *carry;
            let r = *b1 ^ b2_xor_carry;
            // new_carry = (b1 AND b2) XOR (b1 AND carry) XOR (b2 AND carry)
            //          = (b2 XOR carry) ? b1 : b2
            let new_carry = b2_xor_carry.select(*b1, b2);
            *carry = new_carry;
            Some(r)
        })
        .collect::<Vec<B>>()
}

/// Produces a boolean circuit for the subtraction of two scalars.
/// The result is a vector of bits.
pub fn subtraction_circuit<B: Boolean>(
    bits1: Vec<B>,
    bits2: Vec<B>,
    circuit_type: CircuitType,
) -> Vec<B> {
    addition_circuit(
        bits1,
        bits2.into_iter().map(|bit| !bit).collect::<Vec<B>>(),
        B::from(true),
        circuit_type,
    )
}

/// Outputs a vector of 0's with a single 1 at the position of the first 1-bit of `bits`.
/// cpot stands for closest power of two.
pub fn cpot_circuit<B: Boolean>(bits: Vec<B>, circuit_type: CircuitType) -> (Vec<B>, B) {
    if bits.is_empty() {
        return (vec![], B::from(true));
    }
    match circuit_type {
        CircuitType::DepthOpt => {
            if bits.len() >= 1024 {
                panic!(
                    "DepthOpt cpot_circuit only supported for input of at most 1023 bits (found {})",
                    bits.len()
                );
            }
            cpot_circuit_depth_opt_rec(bits, B::from(true))
        }
        CircuitType::SizeOpt => cpot_circuit_size_opt(bits),
    }
}

/// Outputs a vector of 0's with a single 1 at the position of the first 1-bit of `bits`.
/// cpot stands for closest power of two.
fn cpot_circuit_depth_opt_rec<B: Boolean>(bits: Vec<B>, carry_in: B) -> (Vec<B>, B) {
    if bits.len() == 1 {
        let r = bits[0] & carry_in;
        let res = vec![r];
        let carry_out = r ^ carry_in;
        (res, carry_out)
    } else {
        let half = bits.len() / 2;
        let lsbits = bits.iter().copied().take(half).collect::<Vec<B>>();
        let msbits = bits.iter().copied().skip(half).collect::<Vec<B>>();
        let (mut res_ls, carry_out_ls) = cpot_circuit_depth_opt_rec(lsbits, carry_in);
        let (res_ms, carry_out_ms) = cpot_circuit_depth_opt_rec(msbits, carry_in);
        // TODO: this could be vectorized
        let mut res_ms_corrected = res_ms
            .into_iter()
            .map(|r| carry_out_ls & r)
            .collect::<Vec<B>>();
        res_ls.append(&mut res_ms_corrected);
        let carry_out = carry_out_ls & carry_out_ms;
        (res_ls, carry_out)
    }
}

/// Outputs a vector of 0's with a single 1 at the position of the first 1-bit of `bits`.
/// cpot stands for closest power of two.
fn cpot_circuit_size_opt<B: Boolean>(bits: Vec<B>) -> (Vec<B>, B) {
    let mut carry = B::from(true);
    (
        bits.into_iter()
            .map(|b| {
                let r = b & carry;
                carry = r ^ carry;
                r
            })
            .collect::<Vec<B>>(),
        carry,
    )
}

/// icpot (inverse closest power of two) corresponds to 2^{b-1-floor(log2(e))}
/// if e is positive, and to 0 otherwise, where b = e.bounds.unsigned_bin_size().
/// We also return the bits of icpot.
pub fn icpot_unsigned<F: ActuallyUsedField>(
    x: FieldValue<F>,
    max_size: usize,
    circuit_type: CircuitType,
) -> (FieldValue<F>, Vec<BooleanValue>, BooleanValue) {
    let x_bounds = x.bounds();
    let x_size = x_bounds.unsigned_bin_size();
    let circuit_size = x_size.min(max_size);
    let inter_bounds = x_bounds.inter(below_power_of_two(max_size));
    let (min, max) = if x_size > circuit_size || inter_bounds.is_empty() {
        (F::ZERO, F::power_of_two(circuit_size))
    } else {
        inter_bounds.min_and_max(false)
    };

    if x_bounds.has_negatives() {
        panic!("icpot_unsigned only supports unsigned input")
    } else {
        let bits = (0..circuit_size)
            .map(|i| x.get_bit(i, false))
            .collect::<Vec<BooleanValue>>();
        let (icpot_bits, is_zero) = cpot_circuit(
            bits.into_iter().rev().collect::<Vec<BooleanValue>>(),
            circuit_type,
        );
        let icpot = FieldValue::<F>::from_le_bits(icpot_bits.clone(), false);
        let (min_bound, max_bound) = {
            if min == F::ZERO {
                (F::ZERO, F::power_of_two(circuit_size))
            } else {
                (
                    F::power_of_two(circuit_size - max.unsigned_bits()),
                    F::power_of_two(circuit_size - min.unsigned_bits()),
                )
            }
        };
        let icpot_bounds = FieldBounds::new(min_bound, max_bound);
        (
            icpot.with_bounds(icpot_bounds),
            icpot_bits,
            if min_bound == F::ZERO {
                is_zero
            } else {
                BooleanValue::from(false)
            },
        )
    }
}

/// icpot (inverse closest power of two) corresponds to 2^{b-1-floor(log2(e))}
/// if e is positive, and to 0 otherwise, where b = e.bounds.unsigned_bin_size().
/// We also return the bits of icpot.
pub fn icpot_signed<F: ActuallyUsedField>(
    x: FieldValue<F>,
    circuit_type: CircuitType,
) -> (FieldValue<F>, Vec<BooleanValue>, BooleanValue) {
    let x_bounds = x.bounds();
    let circuit_size = x_bounds.signed_bin_size();
    let bits = (0..circuit_size)
        .map(|i| x.get_bit(i, true))
        .collect::<Vec<BooleanValue>>();
    let sign = *bits.last().unwrap();
    let (mut icpot_bits, is_zero) = cpot_circuit(
        bits.into_iter().rev().collect::<Vec<BooleanValue>>(),
        circuit_type,
    );
    // we can simply remove the first bit of icpot_bits, because in case
    // the sign bit is 1, icpot_bits corresponds to [1, 0, .., 0]
    icpot_bits.remove(0);
    let icpot = FieldValue::<F>::from_le_bits(icpot_bits.clone(), false);
    let (min_bound, max_bound) = {
        if x_bounds.signed_min().is_le_zero() {
            (F::ZERO, F::power_of_two(circuit_size - 1))
        } else {
            (
                F::power_of_two(circuit_size - 1 - x_bounds.unsigned_max().unsigned_bits()),
                F::power_of_two(circuit_size - 1 - x_bounds.unsigned_min().unsigned_bits()),
            )
        }
    };
    (
        icpot.with_bounds(FieldBounds::new(min_bound, max_bound)),
        icpot_bits,
        if min_bound.is_le_zero() {
            sign ^ is_zero
        } else {
            BooleanValue::from(false)
        },
    )
}

/// Decoder circuit: takes as input a sequence of bits b0, b1, .., b_{n-1}
/// and outputs the binary characteristic vector of length 2^n with a single 1
/// at position b0 + b1*2 + b2*2^2 + .. + b_{n-1}*2^{n-1}
pub fn decoder_circuit<B: Boolean>(bits: Vec<B>) -> Vec<B> {
    if bits.len() == 1 {
        let b = bits[0];
        vec![!b, b]
    } else {
        let half = bits.len() / 2;
        let lsbits = bits.iter().copied().take(half).collect::<Vec<B>>();
        let msbits = bits.iter().copied().skip(half).collect::<Vec<B>>();
        let res_ls = decoder_circuit(lsbits);
        let res_ms = decoder_circuit(msbits);
        res_ms
            .into_iter()
            .flat_map(|b_ms| res_ls.iter().map(|&b_ls| b_ms & b_ls).collect::<Vec<B>>())
            .collect::<Vec<B>>()
    }
}

pub fn all_circuit<B: Boolean>(bits: Vec<B>, circuit_type: CircuitType) -> B {
    match circuit_type {
        CircuitType::DepthOpt => all_circuit_depth_opt_rec(bits),
        CircuitType::SizeOpt => bits
            .into_iter()
            .reduce(|a: B, b| a & b)
            .unwrap_or(B::from(true)),
    }
}

fn all_circuit_depth_opt_rec<B: Boolean>(bits: Vec<B>) -> B {
    if bits.is_empty() {
        B::from(true)
    } else if bits.len() == 1 {
        bits[0]
    } else {
        let half = bits.len() / 2;
        let lhs_bits = bits.iter().copied().take(half).collect::<Vec<B>>();
        let rhs_bits = bits.iter().copied().skip(half).collect::<Vec<B>>();
        let res_lhs = all_circuit_depth_opt_rec(lhs_bits);
        let res_rhs = all_circuit_depth_opt_rec(rhs_bits);
        res_lhs & res_rhs
    }
}

pub fn is_zero_circuit<B: Boolean>(bits: Vec<B>, circuit_type: CircuitType) -> B {
    all_circuit(
        bits.into_iter().map(|bit| !bit).collect::<Vec<B>>(),
        circuit_type,
    )
}

/// Produces a boolean circuit for the equality (==) of two scalars.
/// The result is a boolean value.
pub fn equal<F: ActuallyUsedField>(
    x: FieldValue<F>,
    y: FieldValue<F>,
    signed_input: bool,
    circuit_type: CircuitType,
) -> BooleanValue {
    let union_bounds = x.bounds().union(y.bounds());
    let circuit_size = union_bounds.signed_bin_size();
    let x_bits = (0..circuit_size)
        .map(|i| x.get_bit(i, signed_input))
        .collect::<Vec<BooleanValue>>();
    let y_bits = (0..circuit_size)
        .map(|i| y.get_bit(i, signed_input))
        .collect::<Vec<BooleanValue>>();
    let xored = x_bits
        .into_iter()
        .zip(y_bits)
        .map(|(bit_x, bit_y)| bit_x ^ bit_y)
        .collect::<Vec<BooleanValue>>();
    is_zero_circuit(xored, circuit_type)
}
/// Produces a boolean circuit for the zeroness of a number.
/// The result is a boolean value.
pub fn is_number_zero<F: ActuallyUsedField>(
    x: FieldValue<F>,
    circuit_type: CircuitType,
) -> BooleanValue {
    let f_num_bits = F::NUM_BITS as usize;
    let circuit_size = x.bounds().max_abs().unsigned_bits();
    let eda_bit_size = (circuit_size + STATISTICAL_SECURITY_FACTOR).min(f_num_bits);
    let (eda_bit_scalar, eda_bit_bits, ..) = new_eda_bit::<F>(eda_bit_size, true);
    let masked = (x + eda_bit_scalar).reveal();
    let add_overflow_bit = masked.bounds() == FieldBounds::All && circuit_size < f_num_bits;
    let masked_bits =
        (0..(circuit_size + add_overflow_bit as usize)).map(|i| masked.get_bit(i, false));
    // It's ok if there are less masked_bits than eda_bit_bits.
    let xored = masked_bits
        .zip(eda_bit_bits)
        .map(|(bit_x, bit_y)| bit_x ^ bit_y)
        .collect::<Vec<BooleanValue>>();
    is_zero_circuit(xored, circuit_type)
        & BooleanValue::from(FieldValue::new(FieldExpr::Ge(
            FieldValue::from(eda_bit_scalar.bounds().unsigned_max()),
            masked,
            false,
        )))
}

/// Produces a boolean circuit for the unsigned comparison of two scalars.
/// The result is a scalar (0 (false) or 1 (true)).
pub fn greater_than<F: ActuallyUsedField>(
    x: FieldValue<F>,
    y: FieldValue<F>,
    if_equal: BooleanValue,
    signed: bool,
    mut signed_input: bool,
) -> BooleanValue {
    let union_bounds = x.bounds().union(y.bounds());
    if signed && union_bounds.has_negatives() && union_bounds.signed_max().is_ge_zero() {
        signed_input = true;
    }
    let circuit_size = union_bounds.bin_size(signed_input);
    let mut x_bits = (0..circuit_size)
        .map(|i| x.get_bit(i, signed_input))
        .collect::<Vec<BooleanValue>>();
    let mut y_bits = (0..circuit_size)
        .map(|i| y.get_bit(i, signed_input))
        .collect::<Vec<BooleanValue>>();
    if signed && signed_input {
        x_bits[circuit_size - 1] = !x_bits[circuit_size - 1];
        y_bits[circuit_size - 1] = !y_bits[circuit_size - 1];
    }
    !addition_circuit_depth_opt_rec(
        y_bits,
        x_bits.into_iter().map(|bit| !bit).collect(),
        !if_equal,
    )
    .1
}

/// Produces a boolean circuit for the right-shift of a scalar.
/// The result is a scalar.
pub fn shift_right<F: ActuallyUsedField>(
    x: FieldValue<F>,
    k: usize,
    signed: bool,
) -> FieldValue<F> {
    let bounds = x.bounds();
    let is_signed = signed && bounds.has_negatives();
    let circuit_size = bounds.bin_size(is_signed);
    let bits = (k..(circuit_size.max(k + is_signed as usize)))
        .map(|i| x.get_bit(i, is_signed))
        .collect::<Vec<BooleanValue>>();

    FieldValue::<F>::from_le_bits(bits, is_signed).with_bounds(shr_bounds(bounds, k, signed))
}

/// Signed right shift with a rounding towards zero.
/// Produces a scalar.
pub fn shift_right_round_towards_zero<F: ActuallyUsedField>(
    x: FieldValue<F>,
    k: usize,
) -> FieldValue<F> {
    let bounds = x.bounds();
    if bounds.has_negatives() {
        let mut lsbits = (0..bounds.signed_bin_size().max(k + 1))
            .map(|i| x.get_bit(i, true))
            .collect::<Vec<BooleanValue>>();
        let msbits = lsbits.split_off(k);
        let sign = *msbits.last().unwrap();
        let is_zero = is_zero_circuit(lsbits, CircuitType::default());
        let carry_in = sign & !is_zero;
        let zeros = vec![BooleanValue::from(false); msbits.len()];
        let res_bits = addition_circuit(msbits, zeros, carry_in, CircuitType::default());

        FieldValue::<F>::from_le_bits(res_bits, true)
    } else {
        shift_right(x, k, false)
    }
}

/// Produces a boolean circuit for the least significant bits of a scalar.
/// The result is a scalar.
pub fn keep_ls_bits<F: ActuallyUsedField>(
    x: FieldValue<F>,
    k: usize,
    signed_output: bool,
) -> FieldValue<F> {
    let bounds = x.bounds();
    if !signed_output && x.is_plaintext() && !bounds.has_negatives() {
        return FieldValue::new(FieldExpr::Rem(x, F::power_of_two(k).into()));
    }
    let bits = (0..k)
        .map(|i| x.get_bit(i, true))
        .collect::<Vec<BooleanValue>>();

    FieldValue::<F>::from_le_bits(bits, signed_output).with_bounds(keep_ls_bounds(
        bounds,
        k,
        signed_output,
    ))
}

/// Produces a boolean circuit for the sign of a scalar.
/// The result is a scalar.
///    0 if       0 <= x <= (p-1)/2,
///    1 if (p+1)/2 <= x <= p-1
pub fn sign_bit<F: ActuallyUsedField>(x: FieldValue<F>) -> BooleanValue {
    let bounds = x.bounds();
    let (min, max) = bounds.min_and_max(true);
    if min.is_ge_zero() {
        BooleanValue::from(false)
    } else if max.is_lt_zero() {
        BooleanValue::from(true)
    } else {
        let mut bits = (0..bounds.signed_bin_size())
            .map(|i| x.get_bit(i, true))
            .collect::<Vec<BooleanValue>>();
        bits.pop().unwrap()
    }
}

fn neg_if_cond_is_one<B: Boolean>(cond: B, bits: Vec<B>) -> Vec<B> {
    let xored = bits.into_iter().map(|b| b ^ cond).collect::<Vec<B>>();
    let zeros = vec![B::from(false); xored.len()];
    addition_circuit(xored, zeros, cond, CircuitType::default())
}

/// Produces a boolean circuit for the absolute value of a scalar.
/// The result is a scalar.
/// Absolute value is defined as:
///    x if       0 <= x <= (p-1)/2,
///  p-x if (p+1)/2 <= x <= p-1
pub fn abs<F: ActuallyUsedField>(x: FieldValue<F>) -> FieldValue<F> {
    let bounds = x.bounds();
    let (min, max) = bounds.min_and_max(true);
    if min.is_ge_zero() {
        x
    } else if max.is_le_zero() {
        -x
    } else {
        let circuit_size = bounds.signed_bin_size();
        let mut bits = (0..circuit_size)
            .map(|i| x.get_bit(i, true))
            .collect::<Vec<BooleanValue>>();
        let sign = bits.pop().unwrap();
        let abs_bits = neg_if_cond_is_one(sign, bits);
        let res = FieldValue::<F>::from_le_bits(abs_bits, false);

        res.with_bounds(FieldBounds::new(bounds.min_abs(), bounds.max_abs()))
    }
}

/// Produces a boolean circuit for the negative absolute value of a scalar.
/// The result is a scalar.
/// Negative absolute value is defined as:
///  p-x if       0 <= x <= (p-1)/2,
///    x if (p+1)/2 <= x <= p-1
pub fn neg_abs<F: ActuallyUsedField>(x: FieldValue<F>) -> FieldValue<F> {
    let bounds = x.bounds();
    let (min, max) = bounds.min_and_max(true);
    if max.is_le_zero() {
        x
    } else if min.is_ge_zero() {
        -x
    } else {
        let circuit_size = bounds.signed_bin_size();
        let bits = (0..circuit_size)
            .map(|i| x.get_bit(i, true))
            .collect::<Vec<BooleanValue>>();
        let sign = *bits.last().unwrap();
        let neg_abs_bits = neg_if_cond_is_one(!sign, bits);
        let res = FieldValue::<F>::from_le_bits(neg_abs_bits, true);

        res.with_bounds(FieldBounds::new(-bounds.max_abs(), -bounds.min_abs()))
    }
}

/// Produces a boolean circuit for the Euclidean division of two scalars.
/// The result is two scalars,
/// * the first one being the quotient,
/// * the second one being the remainder.
pub fn euclidean_division<F: ActuallyUsedField>(
    dividend: FieldValue<F>,
    divisor: FieldValue<F>,
) -> (FieldValue<F>, FieldValue<F>) {
    fn pop_vec(mut v: Vec<BooleanValue>) -> (BooleanValue, Vec<BooleanValue>) {
        let a = v.pop();
        (a.unwrap(), v)
    }
    let leave_room_for_sign = false;
    let bounds_dividend = dividend.bounds();
    let bounds_divisor = divisor.bounds();
    let divider_size = bounds_divisor.unsigned_bin_size() + 1 + (leave_room_for_sign as usize);
    let n_rounds = bounds_dividend.unsigned_bin_size() + (leave_room_for_sign as usize);
    let mut dividend_bits = (0..n_rounds + divider_size - 1)
        .map(|i| dividend.get_bit(i, false))
        .collect::<Vec<BooleanValue>>();
    if let Some(divisor_val) = bounds_divisor.as_constant() {
        if let Some(exponent) = divisor_val.as_power_of_two() {
            let quotient_bits = dividend_bits.split_off(exponent);
            return (
                FieldValue::<F>::from_le_bits(quotient_bits, false),
                FieldValue::<F>::from_le_bits(dividend_bits, false),
            );
        }
    }
    let divisor_bits = (0..divider_size)
        .map(|i| divisor.get_bit(i, false))
        .collect::<Vec<BooleanValue>>();
    let mut quotient_bits = Vec::new();
    for k in (0..n_rounds).rev() {
        let (not_test, c) = pop_vec(subtraction_circuit(
            dividend_bits
                .iter()
                .copied()
                .skip(k)
                .collect::<Vec<BooleanValue>>(),
            divisor_bits.clone(),
            CircuitType::default(),
        ));
        let test = !not_test;
        dividend_bits.pop();
        quotient_bits.push(test);
        let l = dividend_bits.len();
        dividend_bits[k..l]
            .iter_mut()
            .enumerate()
            .for_each(|(i, x)| *x = test.select(c[i], *x));
    }
    quotient_bits.reverse();

    (
        FieldValue::<F>::from_le_bits(quotient_bits, false),
        FieldValue::<F>::from_le_bits(dividend_bits, false),
    )
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        core::{
            circuits::boolean::utils::{abs, icpot_unsigned, neg_abs},
            expressions::{
                bit_expr::BitExpr,
                expr::Expr,
                field_expr::{FieldExpr, InputInfo},
                InputKind,
            },
            global_value::global_expr_store::with_local_expr_store_as_global,
            ir::IntermediateRepresentation,
            ir_builder::{ExprStore, IRBuilder},
        },
        utils::{
            field::{BaseField, ScalarField},
            used_field::UsedField,
        },
    };
    use ff::Field;
    use std::rc::Rc;

    #[test]
    fn icpot_unsigned_test() {
        let rng = &mut crate::utils::test_rng::get();
        let max = 100i32;
        let input_info = Rc::new(InputInfo {
            kind: InputKind::Secret,
            min: 0.into(),
            max: ScalarField::from(max),
            ..InputInfo::default()
        });
        let mut ctrl_ir_builder = IRBuilder::new(true);
        let e0 = ctrl_ir_builder.push_field(FieldExpr::Input(0, input_info));
        let max_size = (max.ilog2() + 1) as usize;
        let mut test_ir_builder_depth_opt = ctrl_ir_builder.clone();
        let e1_depth_opt = with_local_expr_store_as_global(
            || {
                icpot_unsigned(
                    FieldValue::<ScalarField>::from_id(e0),
                    max_size,
                    CircuitType::DepthOpt,
                )
                .0
                .expr()
            },
            &mut test_ir_builder_depth_opt,
        );
        let test_output_depth_opt = test_ir_builder_depth_opt.new_expr(e1_depth_opt);
        let test_ir_depth_opt = test_ir_builder_depth_opt.into_ir(vec![test_output_depth_opt]);
        let mut test_ir_builder_size_opt = ctrl_ir_builder.clone();
        let e1_size_opt = with_local_expr_store_as_global(
            || {
                icpot_unsigned(
                    FieldValue::<ScalarField>::from_id(e0),
                    max_size,
                    CircuitType::SizeOpt,
                )
                .0
                .expr()
            },
            &mut test_ir_builder_size_opt,
        );
        let test_output_size_opt = test_ir_builder_size_opt.new_expr(e1_size_opt);
        let test_ir_size_opt = test_ir_builder_size_opt.into_ir(vec![test_output_size_opt]);
        IntermediateRepresentation::test_eq(rng, &test_ir_depth_opt, &test_ir_size_opt, 4);
    }

    #[test]
    fn euclidean_division_test() {
        let rng = &mut crate::utils::test_rng::get();
        let num_info = Rc::new(InputInfo {
            kind: InputKind::Secret,
            min: (-1024).into(),
            max: ScalarField::from(1024),
            ..InputInfo::default()
        });
        let denom_info = Rc::new(InputInfo {
            kind: InputKind::Secret,
            min: 1.into(),
            max: ScalarField::from(1024),
            ..InputInfo::default()
        });
        let mut ctrl_ir_builder = IRBuilder::new(true);
        let e0 = ctrl_ir_builder.push_field(FieldExpr::Input(0, num_info));
        let e1 = ctrl_ir_builder.push_field(FieldExpr::Input(1, denom_info));
        let mut test_ir_builder = ctrl_ir_builder.clone();
        let (q, r) = with_local_expr_store_as_global(
            || {
                let (q, r) = euclidean_division(
                    FieldValue::<ScalarField>::from_id(e0),
                    FieldValue::<ScalarField>::from_id(e1),
                );
                (q.expr(), r.expr())
            },
            &mut test_ir_builder,
        );
        let test_outputs = vec![test_ir_builder.new_expr(q), test_ir_builder.new_expr(r)];
        let test_ir = test_ir_builder.into_ir(test_outputs);
        let ctrl_outputs = vec![
            ctrl_ir_builder.push_field(FieldExpr::<ScalarField, _>::Div(e0, e1)),
            ctrl_ir_builder.push_field(FieldExpr::<ScalarField, _>::Rem(e0, e1)),
        ];
        let ctrl_ir = ctrl_ir_builder.into_ir(ctrl_outputs);
        IntermediateRepresentation::test_eq(rng, &ctrl_ir, &test_ir, 16)
    }

    #[test]
    fn abs_test() {
        let rng = &mut crate::utils::test_rng::get();
        let input_info = Rc::new(InputInfo {
            kind: InputKind::Secret,
            min: (-1024).into(),
            max: ScalarField::from(1024),
            ..InputInfo::default()
        });
        let mut ctrl_ir_builder = IRBuilder::new(true);
        let e = ctrl_ir_builder.push_field(FieldExpr::Input(0, input_info));
        let mut test_ir_builder = ctrl_ir_builder.clone();
        let e_abs = with_local_expr_store_as_global(
            || abs(FieldValue::<ScalarField>::from_id(e)).expr(),
            &mut test_ir_builder,
        );
        let test_output = test_ir_builder.new_expr(e_abs);
        let test_ir = test_ir_builder.into_ir(vec![test_output]);
        let ctrl_output = ctrl_ir_builder.push_field(FieldExpr::<ScalarField, _>::Abs(e));
        let ctrl_ir = ctrl_ir_builder.into_ir(vec![ctrl_output]);
        IntermediateRepresentation::test_eq(rng, &ctrl_ir, &test_ir, 16)
    }

    #[test]
    fn neg_abs_test() {
        let rng = &mut crate::utils::test_rng::get();
        let input_info = Rc::new(InputInfo {
            kind: InputKind::Secret,
            min: (-1024).into(),
            max: ScalarField::from(1024),
            ..InputInfo::default()
        });
        let mut ctrl_ir_builder = IRBuilder::new(true);
        let e = ctrl_ir_builder.push_field(FieldExpr::Input(0, input_info));
        let mut test_ir_builder = ctrl_ir_builder.clone();
        let e_neg_abs = with_local_expr_store_as_global(
            || neg_abs(FieldValue::<ScalarField>::from_id(e)).expr(),
            &mut test_ir_builder,
        );
        let test_output = test_ir_builder.new_expr(e_neg_abs);
        let test_ir = test_ir_builder.into_ir(vec![test_output]);
        let e_abs = ctrl_ir_builder.push_field(FieldExpr::<ScalarField, _>::Abs(e));
        let ctrl_output = ctrl_ir_builder.push_field(FieldExpr::<ScalarField, _>::Neg(e_abs));
        let ctrl_ir = ctrl_ir_builder.into_ir(vec![ctrl_output]);
        IntermediateRepresentation::test_eq(rng, &ctrl_ir, &test_ir, 16)
    }
    #[test]
    fn greater_than_test() {
        let rng = &mut crate::utils::test_rng::get();
        type F = ScalarField;

        let vals = [-F::ONE, F::ZERO, F::ONE, -(F::ONE + F::ONE)];
        let bounds = [(1, 0), (3, 0), (1, 2)].map(|(a, b)| (vals[a], vals[b]));
        for (l_min, l_max) in bounds {
            let l_info = Rc::new(InputInfo {
                kind: InputKind::Secret,
                min: l_min,
                max: l_max,
                ..InputInfo::default()
            });
            for (r_min, r_max) in bounds {
                let r_info = Rc::new(InputInfo {
                    kind: InputKind::Secret,
                    min: r_min,
                    max: r_max,
                    ..InputInfo::default()
                });
                for if_equal in [false, true] {
                    for signed in [false, true] {
                        for signed_input in [false, true] {
                            let mut ctrl_expr_store = IRBuilder::new(true);
                            let l = ctrl_expr_store.push_field(FieldExpr::Input(0, l_info.clone()));
                            let r = ctrl_expr_store.push_field(FieldExpr::Input(1, r_info.clone()));
                            let mut test_expr_store = ctrl_expr_store.clone();
                            let test_output = with_local_expr_store_as_global(
                                || {
                                    FieldValue::<F>::from(greater_than(
                                        FieldValue::<ScalarField>::from_id(l),
                                        FieldValue::<ScalarField>::from_id(r),
                                        if_equal.into(),
                                        signed,
                                        signed_input,
                                    ))
                                    .get_id()
                                },
                                &mut test_expr_store,
                            );
                            let test_ir = test_expr_store.into_ir(vec![test_output]);
                            let ctrl_output = ctrl_expr_store.push_field(if if_equal {
                                FieldExpr::<F, _>::Ge(l, r, signed)
                            } else {
                                FieldExpr::Gt(l, r, signed)
                            });
                            let ctrl_ir = ctrl_expr_store.into_ir(vec![ctrl_output]);
                            IntermediateRepresentation::test_eq(rng, &ctrl_ir, &test_ir, 16)
                        }
                    }
                }
            }
        }
    }

    #[test]
    fn zero_test() {
        // We're looking for x and y such that
        // ((x + y) % (2^255-19)) % 2^k == y % 2^k
        // x < 2^k
        // y < 2^255-19
        // k <= 255
        // (x is x in zero_circuit, y is eda_bit, k is circuit_size)
        // Without unsigned overflow on x + y, this results in (x + y) % 2^k == y % 2^k.
        // So x == 0 % 2^k, which means x == 0 because x < 2^k
        // With overflow on x + y, this results in (x + y + 19 - 2^255) % 2^k = y % 2^k.
        // x + 19 = 0 % 2^k
        // So x = 2^k - 19 is important to test.
        // This explains why we need circuit_size + 1 in is_number_zero when x + y can overflow.
        let rng = &mut crate::utils::test_rng::get();

        let mut test_expr_store = IRBuilder::new(true);
        let test_output = with_local_expr_store_as_global(
            || {
                is_number_zero(
                    FieldValue::from(BaseField::power_of_two(254) - BaseField::from(19u64)),
                    CircuitType::default(),
                )
                .get_id()
            },
            &mut test_expr_store,
        );
        let test_ir = test_expr_store.into_ir(vec![test_output]);

        let mut ctrl_expr_store = IRBuilder::new(true);
        let ctrl_output = ctrl_expr_store.new_expr(Expr::Bit(BitExpr::Val(false)));
        let ctrl_ir = ctrl_expr_store.into_ir(vec![ctrl_output]);

        IntermediateRepresentation::test_eq(rng, &ctrl_ir, &test_ir, 16)
    }
}