1use crate::transcript::Transcript;
  2use crate::FieldExt;
  3use tiny_keccak::{Hasher, Keccak};
  4
  5pub fn rlc_rows<F: FieldExt>(x: Vec<Vec<F>>, r: &[F]) -> Vec<F> {
  6    debug_assert_eq!(x.len(), r.len());
  7    let num_cols = x[0].len();
  8    let mut result = vec![F::ZERO; num_cols];
  9    for (row, r_i) in x.iter().zip(r.iter()) {
 10        for j in 0..num_cols {
 11            result[j] += row[j] * r_i
 12        }
 13    }
 14    result
 15}
 16
 17pub fn dot_prod<F: FieldExt>(x: &[F], y: &[F]) -> F {
 18    assert_eq!(x.len(), y.len());
 19    let mut result = F::ZERO;
 20    for i in 0..x.len() {
 21        result += x[i] * y[i];
 22    }
 23    result
 24}
 25
 26pub fn hash_all(values: &[[u8; 32]]) -> [u8; 32] {
 27    let mut hasher = Keccak::v256();
 28    for value in values {
 29        hasher.update(value);
 30    }
 31    let mut hash = [0u8; 32];
 32    hasher.finalize(&mut hash);
 33    hash
 34}
 35
 36fn sample_index(random_bytes: [u8; 64], size: usize) -> usize {
 37    let mut acc: u64 = 0;
 38    for b in random_bytes {
 39        acc = acc << 8 ^ (b as u64);
 40    }
 41
 42    (acc % (size as u64)) as usize
 43}
 44
 45pub fn sample_indices<F: FieldExt>(
 46    num_indices: usize,
 47    max_index: usize,
 48    transcript: &mut Transcript<F>,
 49) -> Vec<usize> {
 50    assert!(
 51        num_indices <= max_index,
 52        "max_index {:?} num_indices {:?}",
 53        max_index,
 54        num_indices
 55    );
 56
 57    let mut indices = Vec::with_capacity(num_indices);
 58    let mut counter: u32 = 0;
 59
 60    let n = max_index / 2;
 61    while indices.len() < num_indices {
 62        let mut random_bytes = [0u8; 64];
 63
 64        transcript.append_bytes(&counter.to_le_bytes());
 65        transcript.challenge_bytes(&mut random_bytes);
 66
 67        let index = sample_index(random_bytes, max_index);
 68        let pair_index = if index > n { index - n } else { index + n };
 69        if !indices.contains(&index) && !indices.contains(&pair_index) {
 70            indices.push(index);
 71        }
 72        counter += 1;
 73    }
 74
 75    indices
 76}
 77
 78pub fn det_num_cols(num_entries: usize, l: usize) -> usize {
 79    let num_entries_sqrt = (num_entries as f64).sqrt() as usize;
 80    // The number of columns must be a power of two
 81    // to tensor-query the polynomial evaluation
 82    let num_cols = std::cmp::max(num_entries_sqrt, l).next_power_of_two();
 83    num_cols
 84}
 85
 86pub fn det_num_rows(num_entries: usize, l: usize) -> usize {
 87    // The number of rows must be a power of two
 88    // to tensor-query the polynomial evaluation
 89    let num_rows = (num_entries / det_num_cols(num_entries, l)).next_power_of_two();
 90    num_rows
 91}
 92
 93#[cfg(test)]
 94mod tests {
 95    use super::*;
 96    type F = halo2curves::secp256k1::Fp;
 97
 98    #[test]
 99    fn test_sample_indices() {
100        let mut transcript = Transcript::<F>::new(b"test_sample_index");
101        let num_indices = 10;
102        let max_index = 100;
103        let indices = sample_indices(num_indices, max_index, &mut transcript);
104
105        assert_eq!(indices.len(), 10);
106        let n = max_index / 2;
107        for index in &indices {
108            if *index > n {
109                assert!(!indices.contains(&(index - n)));
110            } else {
111                assert!(!indices.contains(&(index + n)));
112            }
113        }
114    }
115}