use std::collections::HashSet;

use adler32::RollingAdler32;
use cyclic_poly_23::CyclicPoly32;
use rand::Rng;

fn collisions() {
    let block_size = 128;
    // High probability of collisions with a 32bit hash. see:
    //    https://hbfs.wordpress.com/2012/03/30/finding-collisions/
    let num_hashes = 1024 * 1024;
    let data_len = block_size + num_hashes - 1;
    let data = random_vec(data_len);

    // Random number -- sanity check for the expected collisions
    count_collisions("random number generator", None, num_hashes, |_| {
        rand::thread_rng().gen()
    });

    // Cyclic Poly
    let mut cyclic_poly = CyclicPoly32::new(block_size);
    let first = cyclic_poly.calculate(&data[0..block_size]);
    count_collisions("cyclic_poly 32", Some(first), num_hashes - 1, |i| {
        cyclic_poly.rotate(data[i], data[i + block_size])
    });

    // Adler 32
    let mut adler32 = RollingAdler32::from_buffer(&data[0..block_size]);
    let first = adler32.hash();
    count_collisions("adler32", Some(first), num_hashes - 1, |i| {
        adler32.remove(block_size, data[i]);
        adler32.update(data[i + block_size]);
        adler32.hash()
    });
}

fn random_vec(size: usize) -> Vec<u8> {
    let mut data: Vec<u8> = vec![0; size];
    let mut rng = rand::thread_rng();
    rng.fill(&mut data[..]);
    data
}

fn count_collisions<F>(
    name: &str,
    initial_hash: Option<u32>,
    number_comparisons: usize,
    mut rotate: F,
) -> u32
where
    F: FnMut(usize) -> u32,
{
    let mut seen = HashSet::new();
    let mut collisions = 0;
    if let Some(h) = initial_hash {
        seen.insert(h);
    }
    for i in 0..number_comparisons {
        let hash = rotate(i);
        if seen.contains(&hash) {
            collisions += 1;
        } else {
            seen.insert(hash);
        }
    }
    println!("{} collisions = {}", name, collisions);
    collisions
}

fn main() {
    collisions();
}
