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
 78#[cfg(test)]
 79mod tests {
 80    use super::*;
 81    type F = halo2curves::secp256k1::Fp;
 82
 83    #[test]
 84    fn test_sample_indices() {
 85        let mut transcript = Transcript::<F>::new(b"test_sample_index");
 86        let num_indices = 10;
 87        let max_index = 100;
 88        let indices = sample_indices(num_indices, max_index, &mut transcript);
 89
 90        assert_eq!(indices.len(), 10);
 91        let n = max_index / 2;
 92        for index in &indices {
 93            if *index > n {
 94                assert!(!indices.contains(&(index - n)));
 95            } else {
 96                assert!(!indices.contains(&(index + n)));
 97            }
 98        }
 99    }
100}