//! FastCDC content-defined chunking (spec §13.2).

//!

//! Parameters: 32 KiB minimum, 64 KiB target, 256 KiB maximum, normalized

//! chunking level 2. The gear table is derived from BLAKE3 so that every

//! implementation produces identical chunk boundaries:

//! `GEAR[i] = u64::from_le_bytes(XOF("oxy1 fastcdc gear")[8*i .. 8*i+8])`.

//! The masks have `16 + 2` and `16 - 2` one-bits spread evenly over 64 bits

//! (see `spread_mask`). Cut-point skipping starts hashing at the minimum size,

//! as in the FastCDC paper (Xia et al., 2016).

use std::sync::OnceLock;

pub const MIN_SIZE: usize = 32 * 1024;

pub const AVG_SIZE: usize = 64 * 1024;

pub const MAX_SIZE: usize = 256 * 1024;

const AVG_BITS: u32 = 16; // log2(AVG_SIZE)

const NORMALIZATION: u32 = 2;

pub const GEAR_SEED: &[u8] = b"oxy1 fastcdc gear";

fn gear() -> &'static [u64; 256] {

    static GEAR: OnceLock<[u64; 256]> = OnceLock::new();

    GEAR.get_or_init(|| {

        let mut out = [0u8; 256 * 8];

        blake3::Hasher::new().update(GEAR_SEED).finalize_xof().fill(&mut out);

        let mut g = [0u64; 256];

        for (i, v) in g.iter_mut().enumerate() {

            *v = u64::from_le_bytes(out[i * 8..i * 8 + 8].try_into().unwrap());

        }

        g

    })

}

/// A mask with `ones` one-bits at bit positions `63 - floor(i * 64 / ones)`.

pub const fn spread_mask(ones: u32) -> u64 {

    let mut m = 0u64;

    let mut i = 0;

    while i < ones {

        m |= 1u64 << (63 - (i * 64 / ones));

        i += 1;

    }

    m

}

pub const MASK_S: u64 = spread_mask(AVG_BITS + NORMALIZATION);

pub const MASK_L: u64 = spread_mask(AVG_BITS - NORMALIZATION);

/// Length of the first chunk of `data`.

pub fn cut_point(data: &[u8]) -> usize {

    let g = gear();

    let mut n = data.len();

    if n <= MIN_SIZE {

        return n;

    }

    let mut normal = AVG_SIZE;

    if n >= MAX_SIZE {

        n = MAX_SIZE;

    } else if n <= normal {

        normal = n;

    }

    let mut hash: u64 = 0;

    let mut i = MIN_SIZE;

    while i < normal {

        hash = (hash << 1).wrapping_add(g[data[i] as usize]);

        if hash & MASK_S == 0 {

            return i;

        }

        i += 1;

    }

    while i < n {

        hash = (hash << 1).wrapping_add(g[data[i] as usize]);

        if hash & MASK_L == 0 {

            return i;

        }

        i += 1;

    }

    n

}

/// Split `data` into chunks; the concatenation of the result is `data`.

pub fn chunks(data: &[u8]) -> Vec<&[u8]> {

    let mut out = Vec::new();

    let mut rest = data;

    while !rest.is_empty() {

        let n = cut_point(rest);

        out.push(&rest[..n]);

        rest = &rest[n..];

    }

    out

}

#[cfg(test)]

mod tests {

    use super::*;

    use rand::{RngCore, SeedableRng};

    fn random(len: usize, seed: u64) -> Vec<u8> {

        let mut v = vec![0u8; len];

        rand::rngs::StdRng::seed_from_u64(seed).fill_bytes(&mut v);

        v

    }

    #[test]

    fn masks_and_gear_are_pinned() {

        assert_eq!(MASK_S.count_ones(), 18);

        assert_eq!(MASK_L.count_ones(), 14);

        assert_eq!(MASK_S & (1 << 63), 1 << 63);

        // Pin the first gear entry so the table cannot drift silently.

        let mut out = [0u8; 8];

        blake3::Hasher::new().update(GEAR_SEED).finalize_xof().fill(&mut out);

        assert_eq!(gear()[0], u64::from_le_bytes(out));

        assert_ne!(gear()[1], gear()[2]);

    }

    #[test]

    fn small_inputs_are_one_chunk() {

        assert!(chunks(b"").is_empty());

        assert_eq!(chunks(b"abc"), vec![&b"abc"[..]]);

        let d = random(MIN_SIZE, 1);

        assert_eq!(chunks(&d).len(), 1);

    }

    #[test]

    fn bounds_and_reassembly() {

        let d = random(3 * 1024 * 1024, 2);

        let cs = chunks(&d);

        assert!(cs.len() > 10, "{}", cs.len());

        let total: usize = cs.iter().map(|c| c.len()).sum();

        assert_eq!(total, d.len());

        assert_eq!(cs.concat(), d);

        for (i, c) in cs.iter().enumerate() {

            assert!(c.len() <= MAX_SIZE);

            if i + 1 < cs.len() {

                assert!(c.len() >= MIN_SIZE, "chunk {i} is {} bytes", c.len());

            }

        }

        let avg = total / cs.len();

        assert!(avg > MIN_SIZE && avg < MAX_SIZE, "average {avg}");

        assert_eq!(chunks(&d), cs, "deterministic");

    }

    #[test]

    fn insertion_only_disturbs_local_chunks() {

        let d = random(2 * 1024 * 1024, 3);

        let mut e = d.clone();

        e.splice(1_000_000..1_000_000, random(100, 4));

        let a: std::collections::HashSet<[u8; 32]> = chunks(&d).iter().map(|c| *blake3::hash(c).as_bytes()).collect();

        let b: Vec<[u8; 32]> = chunks(&e).iter().map(|c| *blake3::hash(c).as_bytes()).collect();

        let shared = b.iter().filter(|h| a.contains(*h)).count();

        assert!(shared * 10 >= b.len() * 8, "only {shared} of {} chunks shared", b.len());

    }

    #[test]

    fn adversarial_constant_input_hits_bounds() {

        let zeros = vec![0u8; 1024 * 1024];

        let cs = chunks(&zeros);

        for c in &cs[..cs.len() - 1] {

            assert!(c.len() >= MIN_SIZE && c.len() <= MAX_SIZE);

        }

        assert!(cs.len() >= 1024 * 1024 / MAX_SIZE);

        assert!(cs.len() <= 1024 * 1024 / MIN_SIZE + 1);

    }

}