chunk.rs 92.3%

120 of 130 lines run, 18 of 20 functions · run #314 on main · run missed

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

1		//! FastCDC content-defined chunking (spec §13.2).
2		//!
3		//! Parameters: 32 KiB minimum, 64 KiB target, 256 KiB maximum, normalized
4		//! chunking level 2. The gear table is derived from BLAKE3 so that every
5		//! implementation produces identical chunk boundaries:
6		//! `GEAR[i] = u64::from_le_bytes(XOF("oxy1 fastcdc gear")[8i .. 8i+8])`.
7		//! The masks have `16 + 2` and `16 - 2` one-bits spread evenly over 64 bits
8		//! (see `spread_mask`). Cut-point skipping starts hashing at the minimum size,
9		//! as in the FastCDC paper (Xia et al., 2016).
10
11		use std::sync::OnceLock;
12
13		pub const MIN_SIZE: usize = 32 * 1024;
14		pub const AVG_SIZE: usize = 64 * 1024;
15		pub const MAX_SIZE: usize = 256 * 1024;
16		const AVG_BITS: u32 = 16; // log2(AVG_SIZE)
17		const NORMALIZATION: u32 = 2;
18		pub const GEAR_SEED: &[u8] = b"oxy1 fastcdc gear";
19
20	1032×	fn gear() -> &'static [u64; 256] {
21		static GEAR: OnceLock<[u64; 256]> = OnceLock::new();
22	1032×	GEAR.get_or_init(\|\| {
23	2×	let mut out = [0u8; 256 * 8];
24	2×	blake3::Hasher::new()
25	2×	.update(GEAR_SEED)
26	2×	.finalize_xof()
27	2×	.fill(&mut out);
28	2×	let mut g = [0u64; 256];
29	512×	for (i, v) in g.iter_mut().enumerate() {
30	512×	v = u64::from_le_bytes(out[i 8..i * 8 + 8].try_into().unwrap());
31	512×	}
32	2×	g
33	2×	})
34	1032×	}
35
36		/// A mask with `ones` one-bits at bit positions `63 - floor(i * 64 / ones)`.
37	0×	pub const fn spread_mask(ones: u32) -> u64 {
38	0×	let mut m = 0u64;
39	0×	let mut i = 0;
40	0×	while i < ones {
41	0×	m \|= 1u64 << (63 - (i * 64 / ones));
42	0×	i += 1;
43	0×	}
44	0×	m
45	0×	}
46
47		pub const MASK_S: u64 = spread_mask(AVG_BITS + NORMALIZATION);
48		pub const MASK_L: u64 = spread_mask(AVG_BITS - NORMALIZATION);
49
50		/// Length of the first chunk of `data`.
51	1029×	pub fn cut_point(data: &[u8]) -> usize {
52	1029×	let g = gear();
53	1029×	let mut n = data.len();
54	1029×	if n <= MIN_SIZE {
55	517×	return n;
56	512×	}
57	512×	let mut normal = AVG_SIZE;
58	512×	if n >= MAX_SIZE {
59	282×	n = MAX_SIZE;
60	282×	} else if n <= normal {
61	137×	normal = n;
62	137×	}
63	512×	let mut hash: u64 = 0;
64	512×	let mut i = MIN_SIZE;
65	13175817×	while i < normal {
66	13175321×	hash = (hash << 1).wrapping_add(g[data[i] as usize]);
67	13175321×	if hash & MASK_S == 0 {
68	16×	return i;
69	13175305×	}
70	13175305×	i += 1;
71		}
72	24477131×	while i < n {
73	24476861×	hash = (hash << 1).wrapping_add(g[data[i] as usize]);
74	24476861×	if hash & MASK_L == 0 {
75	226×	return i;
76	24476635×	}
77	24476635×	i += 1;
78		}
79	270×	n
80	1029×	}
81
82		/// Split `data` into chunks; the concatenation of the result is `data`.
83	686×	pub fn chunks(data: &[u8]) -> Vec<&[u8]> {
84	686×	let mut out = Vec::new();
85	686×	let mut rest = data;
86	1715×	while !rest.is_empty() {
87	1029×	let n = cut_point(rest);
88	1029×	out.push(&rest[..n]);
89	1029×	rest = &rest[n..];
90	1029×	}
91	686×	out
92	686×	}
93
94		#[cfg(test)]
95		mod tests {
96		use super::*;
97		use rand::{RngCore, SeedableRng};
98
99	4×	fn random(len: usize, seed: u64) -> Vec<u8> {
100	4×	let mut v = vec![0u8; len];
101	4×	rand::rngs::StdRng::seed_from_u64(seed).fill_bytes(&mut v);
102	4×	v
103	4×	}
104
105		#[test]
106	1×	fn masks_and_gear_are_pinned() {
107	1×	assert_eq!(MASK_S.count_ones(), 18);
108	1×	assert_eq!(MASK_L.count_ones(), 14);
109	1×	assert_eq!(MASK_S & (1 << 63), 1 << 63);
110		// Pin the first gear entry so the table cannot drift silently.
111	1×	let mut out = [0u8; 8];
112	1×	blake3::Hasher::new()
113	1×	.update(GEAR_SEED)
114	1×	.finalize_xof()
115	1×	.fill(&mut out);
116	1×	assert_eq!(gear()[0], u64::from_le_bytes(out));
117	1×	assert_ne!(gear()[1], gear()[2]);
118	1×	}
119
120		#[test]
121	1×	fn small_inputs_are_one_chunk() {
122	1×	assert!(chunks(b"").is_empty());
123	1×	assert_eq!(chunks(b"abc"), vec![&b"abc"[..]]);
124	1×	let d = random(MIN_SIZE, 1);
125	1×	assert_eq!(chunks(&d).len(), 1);
126	1×	}
127
128		#[test]
129	1×	fn bounds_and_reassembly() {
130	1×	let d = random(3 * 1024 * 1024, 2);
131	1×	let cs = chunks(&d);
132	1×	assert!(cs.len() > 10, "{}", cs.len());
133	42×	let total: usize = cs.iter().map(\|c\| c.len()).sum();
134	1×	assert_eq!(total, d.len());
135	1×	assert_eq!(cs.concat(), d);
136	42×	for (i, c) in cs.iter().enumerate() {
137	42×	assert!(c.len() <= MAX_SIZE);
138	42×	if i + 1 < cs.len() {
139	41×	assert!(c.len() >= MIN_SIZE, "chunk {i} is {} bytes", c.len());
140	1×	}
141		}
142	1×	let avg = total / cs.len();
143	1×	assert!(avg > MIN_SIZE && avg < MAX_SIZE, "average {avg}");
144	1×	assert_eq!(chunks(&d), cs, "deterministic");
145	1×	}
146
147		#[test]
148	1×	fn insertion_only_disturbs_local_chunks() {
149	1×	let d = random(2 * 1024 * 1024, 3);
150	1×	let mut e = d.clone();
151	1×	e.splice(1_000_000..1_000_000, random(100, 4));
152	1×	let a: std::collections::HashSet<[u8; 32]> = chunks(&d)
153	1×	.iter()
154	27×	.map(\|c\| *blake3::hash(c).as_bytes())
155	1×	.collect();
156	1×	let b: Vec<[u8; 32]> = chunks(&e)
157	1×	.iter()
158	27×	.map(\|c\| *blake3::hash(c).as_bytes())
159	1×	.collect();
160	27×	let shared = b.iter().filter(\|h\| a.contains(*h)).count();
161	1×	assert!(
162	1×	shared * 10 >= b.len() * 8,
163		"only {shared} of {} chunks shared",
164	0×	b.len()
165		);
166	1×	}
167
168		#[test]
169	1×	fn adversarial_constant_input_hits_bounds() {
170	1×	let zeros = vec![0u8; 1024 * 1024];
171	1×	let cs = chunks(&zeros);
172	3×	for c in &cs[..cs.len() - 1] {
173	3×	assert!(c.len() >= MIN_SIZE && c.len() <= MAX_SIZE);
174		}
175	1×	assert!(cs.len() >= 1024 * 1024 / MAX_SIZE);
176	1×	assert!(cs.len() <= 1024 * 1024 / MIN_SIZE + 1);
177	1×	}
178		}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

Coverage / crates/oxy-core/src/chunk.rs 92.3%

Keyboard