use std::io::Read;
use std::ops::Range;
use serde::{Deserialize, Serialize};
use crate::error::{BlobError, Result};
use crate::verify::GROUP_SIZE;
pub const MIN_CHUNK_SIZE: u32 = 64 * 1024;
pub const MAX_CHUNK_SIZE: u32 = 4 * 1024 * 1024;
pub const DEFAULT_CHUNK_SIZE: u32 = 256 * 1024;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct TransferChunks {
chunk_size: u32,
total_len: u64,
}
impl TransferChunks {
pub fn validate_chunk_size(chunk_size: u32) -> Result<()> {
if !(MIN_CHUNK_SIZE..=MAX_CHUNK_SIZE).contains(&chunk_size) {
return Err(BlobError::InvalidManifest(format!(
"chunk_size {chunk_size} outside [{MIN_CHUNK_SIZE}, {MAX_CHUNK_SIZE}]"
)));
}
if !(chunk_size as u64).is_multiple_of(GROUP_SIZE) {
return Err(BlobError::InvalidManifest(format!(
"chunk_size {chunk_size} is not a multiple of the {GROUP_SIZE}-byte bao group"
)));
}
Ok(())
}
pub fn new(chunk_size: u32, total_len: u64) -> Result<Self> {
Self::validate_chunk_size(chunk_size)?;
if total_len.div_ceil(chunk_size as u64) > u32::MAX as u64 {
return Err(BlobError::InvalidManifest(format!(
"total_len {total_len} at chunk_size {chunk_size} needs more than \
{} chunks, which cannot be indexed",
u32::MAX
)));
}
Ok(TransferChunks {
chunk_size,
total_len,
})
}
pub fn chunk_size(&self) -> u32 {
self.chunk_size
}
pub fn total_len(&self) -> u64 {
self.total_len
}
pub fn count(&self) -> u32 {
debug_assert!(self.total_len.div_ceil(self.chunk_size as u64) <= u32::MAX as u64);
self.total_len.div_ceil(self.chunk_size as u64) as u32
}
pub fn byte_range(&self, index: u32) -> Range<u64> {
let start = (index as u64 * self.chunk_size as u64).min(self.total_len);
let end = (start + self.chunk_size as u64).min(self.total_len);
start..end
}
pub fn len_of(&self, index: u32) -> u32 {
let r = self.byte_range(index);
(r.end - r.start) as u32
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub struct CdcParams {
pub min: u32,
pub avg: u32,
pub max: u32,
pub normalization: u8,
pub gear_seed: u64,
}
impl Default for CdcParams {
fn default() -> Self {
CdcParams {
min: 16 * 1024,
avg: 64 * 1024,
max: 256 * 1024,
normalization: 2,
gear_seed: 0,
}
}
}
impl CdcParams {
pub fn with_seed(gear_seed: u64) -> Self {
CdcParams {
gear_seed,
..Default::default()
}
}
pub fn validate(&self) -> Result<()> {
let ok = self.min >= 64
&& self.min <= self.avg
&& self.avg <= self.max
&& self.avg >= 256
&& self.max <= 16 * 1024 * 1024
&& self.normalization <= 3;
if ok {
Ok(())
} else {
Err(BlobError::InvalidManifest(format!(
"invalid CDC parameters {self:?}"
)))
}
}
fn level(&self) -> fastcdc::v2020::Normalization {
match self.normalization {
0 => fastcdc::v2020::Normalization::Level0,
1 => fastcdc::v2020::Normalization::Level1,
3 => fastcdc::v2020::Normalization::Level3,
_ => fastcdc::v2020::Normalization::Level2,
}
}
pub fn chunk_reader<R: Read>(
&self,
reader: R,
) -> impl Iterator<Item = std::io::Result<Vec<u8>>> {
fastcdc::v2020::StreamCDC::with_level_and_seed(
reader,
self.min as usize,
self.avg as usize,
self.max as usize,
self.level(),
self.gear_seed,
)
.map(|item| match item {
Ok(chunk) => Ok(chunk.data),
Err(fastcdc::v2020::Error::IoError(e)) => Err(e),
Err(other) => Err(std::io::Error::other(format!("fastcdc: {other:?}"))),
})
}
}
#[cfg(test)]
mod properties {
use super::*;
use proptest::prelude::*;
fn valid_chunk_size() -> impl Strategy<Value = u32> {
(MIN_CHUNK_SIZE / (16 * 1024)..=MAX_CHUNK_SIZE / (16 * 1024)).prop_map(|k| k * 16 * 1024)
}
proptest! {
#[test]
fn chunks_tile_the_blob_exactly(
chunk_size in valid_chunk_size(),
total_len in 0u64..(64 * 1024 * 1024),
) {
let c = TransferChunks::new(chunk_size, total_len).unwrap();
let count = c.count();
let mut cursor = 0u64;
let mut summed = 0u64;
for i in 0..count {
let r = c.byte_range(i);
prop_assert_eq!(r.start, cursor, "gap or overlap at chunk {}", i);
prop_assert!(r.end > r.start, "empty chunk {} within count", i);
prop_assert_eq!(c.len_of(i) as u64, r.end - r.start);
prop_assert!(c.len_of(i) <= chunk_size);
cursor = r.end;
summed += c.len_of(i) as u64;
}
prop_assert_eq!(cursor, total_len, "tiling does not reach the end");
prop_assert_eq!(summed, total_len);
prop_assert_eq!(c.len_of(count), 0);
prop_assert_eq!(c.len_of(u32::MAX), 0);
}
#[test]
fn chunk_starts_are_group_aligned(
chunk_size in valid_chunk_size(),
total_len in 0u64..(16 * 1024 * 1024),
index in 0u32..64,
) {
let c = TransferChunks::new(chunk_size, total_len).unwrap();
let start = c.byte_range(index).start;
prop_assert!(
start.is_multiple_of(crate::verify::GROUP_SIZE) || start == total_len,
"chunk {} starts at {} which is not group-aligned", index, start
);
}
#[test]
fn accepted_geometries_have_representable_counts(
chunk_size in valid_chunk_size(),
total_len in any::<u64>(),
) {
if TransferChunks::new(chunk_size, total_len).is_ok() {
prop_assert!(total_len.div_ceil(chunk_size as u64) <= u32::MAX as u64);
}
}
#[test]
fn chunk_size_validation_is_total(size in any::<u32>()) {
match TransferChunks::validate_chunk_size(size) {
Ok(()) => {
prop_assert!((MIN_CHUNK_SIZE..=MAX_CHUNK_SIZE).contains(&size));
prop_assert!((size as u64).is_multiple_of(crate::verify::GROUP_SIZE));
}
Err(_) => {
prop_assert!(
!(MIN_CHUNK_SIZE..=MAX_CHUNK_SIZE).contains(&size)
|| !(size as u64).is_multiple_of(crate::verify::GROUP_SIZE)
);
}
}
}
#[test]
fn cdc_chunking_is_lossless(
data in prop::collection::vec(any::<u8>(), 0..70_000),
seed in any::<u64>(),
) {
let params = CdcParams { min: 2048, avg: 8192, max: 32768, normalization: 2, gear_seed: seed };
let mut rebuilt = Vec::new();
for chunk in params.chunk_reader(std::io::Cursor::new(&data)) {
let bytes = chunk.map_err(|e| TestCaseError::fail(e.to_string()))?;
prop_assert!(!bytes.is_empty(), "CDC must not emit empty chunks");
prop_assert!(bytes.len() <= params.max as usize, "chunk exceeds declared max");
rebuilt.extend_from_slice(&bytes);
}
prop_assert_eq!(rebuilt, data);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::hash::Hash;
#[test]
fn transfer_chunk_size_validated_never_clamped() {
assert!(TransferChunks::new(DEFAULT_CHUNK_SIZE, 1).is_ok());
assert!(TransferChunks::new(MIN_CHUNK_SIZE, 1).is_ok());
assert!(TransferChunks::new(MAX_CHUNK_SIZE, 1).is_ok());
assert!(TransferChunks::new(MIN_CHUNK_SIZE - 1, 1).is_err());
assert!(TransferChunks::new(MAX_CHUNK_SIZE + 16 * 1024, 1).is_err());
assert!(TransferChunks::new(0, 1).is_err());
assert!(TransferChunks::new(MIN_CHUNK_SIZE + 1, 1).is_err());
}
#[test]
fn transfer_chunk_geometry() {
let size = DEFAULT_CHUNK_SIZE as u64;
let total = size * 3 + size / 2;
let c = TransferChunks::new(DEFAULT_CHUNK_SIZE, total).unwrap();
assert_eq!(c.count(), 4);
assert_eq!(c.byte_range(0), 0..size);
assert_eq!(c.byte_range(3), size * 3..total);
assert_eq!(c.len_of(3) as u64, size / 2);
assert_eq!(c.len_of(4), 0); assert_eq!(c.byte_range(9), total..total);
let empty = TransferChunks::new(DEFAULT_CHUNK_SIZE, 0).unwrap();
assert_eq!(empty.count(), 0);
let exact = TransferChunks::new(DEFAULT_CHUNK_SIZE, size * 2).unwrap();
assert_eq!(exact.count(), 2);
assert_eq!(exact.len_of(1), DEFAULT_CHUNK_SIZE);
}
#[test]
fn cdc_params_validation() {
assert!(CdcParams::default().validate().is_ok());
assert!(CdcParams::with_seed(42).validate().is_ok());
let bad = [
CdcParams {
min: 32,
..Default::default()
},
CdcParams {
min: 1 << 20,
avg: 1 << 18,
..Default::default()
},
CdcParams {
max: 32 * 1024 * 1024,
..Default::default()
},
CdcParams {
normalization: 9,
..Default::default()
},
];
for p in bad {
assert!(p.validate().is_err(), "{p:?}");
}
}
fn pseudo_random(len: usize, seed: u64) -> Vec<u8> {
let mut out = Vec::with_capacity(len);
let mut x = seed | 1;
for _ in 0..len {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
out.push((x & 0xff) as u8);
}
out
}
fn small_cdc(seed: u64) -> CdcParams {
CdcParams {
min: 2048,
avg: 8192,
max: 32768,
normalization: 2,
gear_seed: seed,
}
}
fn cdc_hashes(params: &CdcParams, data: &[u8]) -> std::collections::HashSet<Hash> {
params
.chunk_reader(std::io::Cursor::new(data))
.map(|c| Hash::of(&c.unwrap()))
.collect()
}
#[test]
fn chunks_tile_the_input() {
let data = pseudo_random(100_000, 7);
let rebuilt: Vec<u8> = small_cdc(0)
.chunk_reader(std::io::Cursor::new(&data))
.flat_map(|c| c.unwrap())
.collect();
assert_eq!(rebuilt, data);
assert_eq!(
small_cdc(0)
.chunk_reader(std::io::Cursor::new(&[] as &[u8]))
.count(),
0
);
}
#[test]
fn fastcdc_localizes_edits_far_better_than_fixed() {
let base = pseudo_random(200_000, 0xC0FFEE);
let mut edited = base.clone();
edited.splice(4096..4096, pseudo_random(50, 0xBEEF));
let cdc = small_cdc(0);
let cdc_a = cdc_hashes(&cdc, &base);
let cdc_b = cdc_hashes(&cdc, &edited);
let cdc_ratio = cdc_a.intersection(&cdc_b).count() as f64 / cdc_a.len() as f64;
let fix_a: std::collections::HashSet<Hash> = base.chunks(8192).map(Hash::of).collect();
let fix_b: std::collections::HashSet<Hash> = edited.chunks(8192).map(Hash::of).collect();
let fix_ratio = fix_a.intersection(&fix_b).count() as f64 / fix_a.len() as f64;
assert!(
cdc_ratio > 0.8,
"FastCDC should retain >80% of chunks, got {cdc_ratio:.2}"
);
assert!(
cdc_ratio > fix_ratio + 0.3,
"FastCDC ({cdc_ratio:.2}) should dedup far better than fixed ({fix_ratio:.2})"
);
}
#[test]
fn gear_seed_changes_boundaries() {
let data = pseudo_random(200_000, 0x5EED);
let a = cdc_hashes(&small_cdc(0), &data);
let b = cdc_hashes(&small_cdc(0xDEADBEEF), &data);
let a2 = cdc_hashes(&small_cdc(0), &data);
assert_eq!(a, a2, "same seed → identical chunking");
let overlap = a.intersection(&b).count() as f64 / a.len().max(1) as f64;
assert!(
overlap < 0.5,
"different seeds should share few chunks, got {overlap:.2}"
);
}
}