//! 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);
    }
}