tsaur_core/
chunk.rs

1//! Content-defined chunking (FastCDC 2020, normalized chunking level 2) and BLAKE3 identities.
2
3use crate::error::{Error, Result};
4use fastcdc::v2020::{FastCDC, Normalization};
5use serde::{Deserialize, Serialize};
6
7pub type Hash = [u8; 32];
8
9#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
10pub struct ChunkParams {
11    pub min: u32,
12    pub avg: u32,
13    pub max: u32,
14}
15
16impl ChunkParams {
17    /// Small text corpora: fine-grained dedup, more metadata.
18    pub const FINE: ChunkParams = ChunkParams { min: 2 * 1024, avg: 8 * 1024, max: 64 * 1024 };
19    /// Default: aligned with Hugging Face Xet / casync (~64 KiB), P2P friendly.
20    pub const P2P: ChunkParams = ChunkParams { min: 16 * 1024, avg: 64 * 1024, max: 256 * 1024 };
21    /// Large archives: fewer chunks, less metadata.
22    pub const ARCHIVE: ChunkParams = ChunkParams { min: 64 * 1024, avg: 256 * 1024, max: 1024 * 1024 };
23
24    pub fn validate(&self) -> Result<()> {
25        if self.min < 64 || self.avg < 256 || self.max < 1024 || self.min > self.avg || self.avg > self.max {
26            return Err(Error::Invalid(format!("chunk parameters out of range: {self:?}")));
27        }
28        Ok(())
29    }
30
31    pub fn by_name(name: &str) -> Option<ChunkParams> {
32        match name {
33            "fine" => Some(Self::FINE),
34            "p2p" => Some(Self::P2P),
35            "archive" => Some(Self::ARCHIVE),
36            _ => None,
37        }
38    }
39}
40
41impl Default for ChunkParams {
42    fn default() -> Self {
43        Self::P2P
44    }
45}
46
47/// Chunk boundaries as (offset, length) pairs covering `data` exactly.
48pub fn boundaries(data: &[u8], p: &ChunkParams) -> Vec<(usize, usize)> {
49    if data.is_empty() {
50        return Vec::new();
51    }
52    FastCDC::with_level(data, p.min, p.avg, p.max, Normalization::Level2).map(|c| (c.offset, c.length)).collect()
53}
54
55pub fn hash(data: &[u8]) -> Hash {
56    *blake3::hash(data).as_bytes()
57}
58
59/// Binary Merkle root with domain separation (RFC 9162 style: 0x00 for leaves, 0x01 for nodes).
60pub fn merkle_root(hashes: &[Hash]) -> Hash {
61    if hashes.is_empty() {
62        return hash(b"");
63    }
64    let mut level: Vec<Hash> = hashes
65        .iter()
66        .map(|h| {
67            let mut m = Vec::with_capacity(33);
68            m.push(0u8);
69            m.extend_from_slice(h);
70            hash(&m)
71        })
72        .collect();
73    while level.len() > 1 {
74        if level.len() % 2 == 1 {
75            let last = *level.last().unwrap();
76            level.push(last);
77        }
78        level = level
79            .chunks(2)
80            .map(|pair| {
81                let mut m = Vec::with_capacity(65);
82                m.push(1u8);
83                m.extend_from_slice(&pair[0]);
84                m.extend_from_slice(&pair[1]);
85                hash(&m)
86            })
87            .collect();
88    }
89    level[0]
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn boundaries_cover_input() {
98        let data: Vec<u8> = (0..300_000u32).map(|i| (i.wrapping_mul(2654435761) >> 13) as u8).collect();
99        let b = boundaries(&data, &ChunkParams::FINE);
100        let total: usize = b.iter().map(|x| x.1).sum();
101        assert_eq!(total, data.len());
102        assert!(b.len() > 10);
103        assert_eq!(b[0].0, 0);
104    }
105
106    #[test]
107    fn merkle_is_stable() {
108        let a = merkle_root(&[hash(b"a"), hash(b"b"), hash(b"c")]);
109        let b = merkle_root(&[hash(b"a"), hash(b"b"), hash(b"c")]);
110        assert_eq!(a, b);
111        assert_ne!(a, merkle_root(&[hash(b"a"), hash(b"b")]));
112    }
113}
tsaur_core/chunk.rs

tsaur_core/
chunk.rs
