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_two(values: &[[u8; 32]; 2]) -> [u8; 32] {
 27    let mut hasher = Keccak::v256();
 28    hasher.update(&values[0]);
 29    hasher.update(&values[1]);
 30    let mut hash = [0u8; 32];
 31    hasher.finalize(&mut hash);
 32    hash
 33}
 34
 35pub fn hash_all(values: &[[u8; 32]]) -> [u8; 32] {
 36    let mut hasher = Keccak::v256();
 37    for value in values {
 38        hasher.update(value);
 39    }
 40    let mut hash = [0u8; 32];
 41    hasher.finalize(&mut hash);
 42    hash
 43}
 44
 45fn sample_index(random_bytes: [u8; 64], size: usize) -> usize {
 46    let mut acc: u64 = 0;
 47    for b in random_bytes {
 48        acc = acc << 8 ^ (b as u64);
 49    }
 50
 51    (acc % (size as u64)) as usize
 52}
 53
 54pub fn sample_indices<F: FieldExt>(
 55    num_indices: usize,
 56    max_index: usize,
 57    transcript: &mut Transcript<F>,
 58) -> Vec<usize> {
 59    assert!(
 60        num_indices <= max_index,
 61        "max_index {:?} num_indices {:?}",
 62        max_index,
 63        num_indices
 64    );
 65
 66    let mut indices = Vec::with_capacity(num_indices);
 67    let mut counter: u32 = 0;
 68
 69    let n = max_index / 2;
 70    while indices.len() < num_indices {
 71        let mut random_bytes = [0u8; 64];
 72
 73        transcript.append_bytes(&counter.to_le_bytes());
 74        transcript.challenge_bytes(&mut random_bytes);
 75
 76        let index = sample_index(random_bytes, max_index);
 77        let pair_index = if index > n { index - n } else { index + n };
 78        if !indices.contains(&index) && !indices.contains(&pair_index) {
 79            indices.push(index);
 80        }
 81        counter += 1;
 82    }
 83
 84    indices
 85}
 86
 87#[cfg(test)]
 88mod tests {
 89    use super::*;
 90    type F = halo2curves::secp256k1::Fp;
 91
 92    #[test]
 93    fn test_sample_indices() {
 94        let mut transcript = Transcript::<F>::new(b"test_sample_index");
 95        let num_indices = 10;
 96        let max_index = 100;
 97        let indices = sample_indices(num_indices, max_index, &mut transcript);
 98
 99        assert_eq!(indices.len(), 10);
100        let n = max_index / 2;
101        for index in &indices {
102            if *index > n {
103                assert!(!indices.contains(&(index - n)));
104            } else {
105                assert!(!indices.contains(&(index + n)));
106            }
107        }
108    }
109}