1// Copyright (c) 2023 Espresso Systems (espressosys.com)
  2// This file is part of the HyperPlonk library.
  3
  4// You should have received a copy of the MIT License
  5// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
  6
  7use ark_ff::PrimeField;
  8use ark_std::log2;
  9
 10/// Decompose an integer into a binary vector in little endian.
 11pub fn bit_decompose(input: u64, num_var: usize) -> Vec<bool> {
 12    let mut res = Vec::with_capacity(num_var);
 13    let mut i = input;
 14    for _ in 0..num_var {
 15        res.push(i & 1 == 1);
 16        i >>= 1;
 17    }
 18    res
 19}
 20
 21/// given the evaluation input `point` of the `index`-th polynomial,
 22/// obtain the evaluation point in the merged polynomial
 23pub fn gen_eval_point<F: PrimeField>(index: usize, index_len: usize, point: &[F]) -> Vec<F> {
 24    let index_vec: Vec<F> = bit_decompose(index as u64, index_len)
 25        .into_iter()
 26        .map(|x| F::from(x))
 27        .collect();
 28    [point, &index_vec].concat()
 29}
 30
 31/// Return the number of variables that one need for an MLE to
 32/// batch the list of MLEs
 33#[inline]
 34pub fn get_batched_nv(num_var: usize, polynomials_len: usize) -> usize {
 35    num_var + log2(polynomials_len) as usize
 36}
 37
 38// Input index
 39// - `i := (i_0, ...i_{n-1})`,
 40// - `num_vars := n`
 41// return three elements:
 42// - `x0 := (i_1, ..., i_{n-1}, 0)`
 43// - `x1 := (i_1, ..., i_{n-1}, 1)`
 44// - `sign := i_0`
 45#[inline]
 46pub fn get_index(i: usize, num_vars: usize) -> (usize, usize, bool) {
 47    let bit_sequence = bit_decompose(i as u64, num_vars);
 48
 49    // the last bit comes first here because of LE encoding
 50    let x0 = project(&[[false].as_ref(), bit_sequence[..num_vars - 1].as_ref()].concat()) as usize;
 51    let x1 = project(&[[true].as_ref(), bit_sequence[..num_vars - 1].as_ref()].concat()) as usize;
 52
 53    (x0, x1, bit_sequence[num_vars - 1])
 54}
 55
 56/// Project a little endian binary vector into an integer.
 57#[inline]
 58pub(crate) fn project(input: &[bool]) -> u64 {
 59    let mut res = 0;
 60    for &e in input.iter().rev() {
 61        res <<= 1;
 62        res += e as u64;
 63    }
 64    res
 65}
 66
 67#[cfg(test)]
 68mod test {
 69    use super::{bit_decompose, get_index, project};
 70    use ark_std::{rand::RngCore, test_rng};
 71
 72    #[test]
 73    fn test_decomposition() {
 74        let mut rng = test_rng();
 75        for _ in 0..100 {
 76            let t = rng.next_u64();
 77            let b = bit_decompose(t, 64);
 78            let r = project(&b);
 79            assert_eq!(t, r)
 80        }
 81    }
 82
 83    #[test]
 84    fn test_get_index() {
 85        let a = 0b1010;
 86        let (x0, x1, sign) = get_index(a, 4);
 87        assert_eq!(x0, 0b0100);
 88        assert_eq!(x1, 0b0101);
 89        assert!(sign);
 90
 91        let (x0, x1, sign) = get_index(a, 5);
 92        assert_eq!(x0, 0b10100);
 93        assert_eq!(x1, 0b10101);
 94        assert!(!sign);
 95
 96        let a = 0b1111;
 97        let (x0, x1, sign) = get_index(a, 4);
 98        assert_eq!(x0, 0b1110);
 99        assert_eq!(x1, 0b1111);
100        assert!(sign);
101    }
102}