use std::io::{Cursor, Read, Seek};
use std::ops::Range;
use std::path::Path;
use bao_tree::io::BaoContentItem;
use bao_tree::io::outboard::PreOrderOutboard;
use bao_tree::io::sync::{
CreateOutboard, DecodeResponseIter, Outboard, ReadAt, encode_ranges_validated,
};
use bao_tree::{BaoTree, BlockSize, ChunkNum, ChunkRanges};
pub(crate) const BAO_BLOCK: BlockSize = BlockSize::from_chunk_log(4);
pub(crate) const GROUP_SIZE: u64 = 16 * 1024;
pub(crate) type MemOutboard = PreOrderOutboard<Vec<u8>>;
pub(crate) fn compute_outboard(data: impl Read + Seek) -> std::io::Result<MemOutboard> {
PreOrderOutboard::create(data, BAO_BLOCK)
}
pub(crate) fn compute_outboard_sized(data: impl Read, size: u64) -> std::io::Result<MemOutboard> {
PreOrderOutboard::create_sized(data, size, BAO_BLOCK)
}
pub(crate) fn tree_for(total_len: u64) -> BaoTree {
BaoTree::new(total_len, BAO_BLOCK)
}
pub(crate) fn chunk_range(bytes: Range<u64>) -> Range<ChunkNum> {
ChunkNum(bytes.start >> 10)..ChunkNum::chunks(bytes.end)
}
pub(crate) fn encode_slice(
data: impl ReadAt,
outboard: &impl Outboard,
chunks: Range<ChunkNum>,
) -> std::io::Result<Vec<u8>> {
let ranges = ChunkRanges::from(chunks);
let mut out = Vec::new();
encode_ranges_validated(data, outboard, &ranges, &mut out).map_err(std::io::Error::other)?;
Ok(out)
}
pub(crate) fn compute_outboard_file(
data: impl Read,
size: u64,
obao: &Path,
) -> std::io::Result<PreOrderOutboard<std::fs::File>> {
let file = std::fs::OpenOptions::new()
.read(true)
.write(true)
.create(true)
.truncate(true)
.open(obao)?;
let mut ob = PreOrderOutboard {
root: blake3::hash(&[]),
tree: BaoTree::new(size, BAO_BLOCK),
data: file,
};
ob.init_from(data)?;
ob.data.sync_all()?;
Ok(ob)
}
pub(crate) enum OutboardStore {
Mem(MemOutboard),
File(PreOrderOutboard<std::fs::File>),
}
impl OutboardStore {
pub fn root(&self) -> blake3::Hash {
match self {
OutboardStore::Mem(ob) => ob.root,
OutboardStore::File(ob) => ob.root,
}
}
pub fn encode_slice(
&self,
data: impl ReadAt,
chunks: Range<ChunkNum>,
) -> std::io::Result<Vec<u8>> {
match self {
OutboardStore::Mem(ob) => encode_slice(data, ob, chunks),
OutboardStore::File(ob) => encode_slice(data, ob, chunks),
}
}
}
pub(crate) struct ReadAtCursor<R> {
inner: R,
pos: u64,
}
impl<R: ReadAt> ReadAtCursor<R> {
pub fn new(inner: R) -> Self {
ReadAtCursor { inner, pos: 0 }
}
}
impl<R: ReadAt> Read for ReadAtCursor<R> {
fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
let n = self.inner.read_at(self.pos, buf)?;
self.pos += n as u64;
Ok(n)
}
}
pub(crate) fn decode_slice(
root: &blake3::Hash,
total_len: u64,
chunks: Range<ChunkNum>,
encoded: &[u8],
mut on_leaf: impl FnMut(u64, &[u8]) -> std::io::Result<()>,
) -> std::io::Result<()> {
let ranges = ChunkRanges::from(chunks);
let iter = DecodeResponseIter::new(*root, tree_for(total_len), Cursor::new(encoded), &ranges);
for item in iter {
match item.map_err(std::io::Error::other)? {
BaoContentItem::Leaf(leaf) => on_leaf(leaf.offset, &leaf.data)?,
BaoContentItem::Parent(_) => {}
}
}
Ok(())
}
#[cfg(test)]
mod properties {
use super::*;
use proptest::prelude::*;
fn slice_for(data: &[u8], chunk_size: u64, index: u64) -> Option<(Vec<u8>, Range<u64>)> {
let total = data.len() as u64;
let start = index * chunk_size;
if start >= total && total > 0 {
return None;
}
let end = (start + chunk_size).min(total);
if start == end {
return None;
}
let ob = compute_outboard(Cursor::new(data)).ok()?;
let enc = encode_slice(data, &ob, chunk_range(start..end)).ok()?;
Some((enc, start..end))
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(64))]
#[test]
fn slice_round_trips_to_its_exact_byte_range(
data in prop::collection::vec(any::<u8>(), 0..300_000),
size_groups in 1u64..8,
index in 0u64..20,
) {
let chunk_size = size_groups * GROUP_SIZE;
let Some((enc, range)) = slice_for(&data, chunk_size, index) else {
return Ok(()); };
let root = blake3::hash(&data);
let mut got = Vec::new();
let mut first_offset = None;
decode_slice(&root, data.len() as u64, chunk_range(range.clone()), &enc, |off, d| {
first_offset.get_or_insert(off);
got.extend_from_slice(d);
Ok(())
})
.map_err(|e| TestCaseError::fail(format!("honest slice rejected: {e}")))?;
prop_assert_eq!(first_offset, Some(range.start), "slice landed at the wrong offset");
prop_assert_eq!(
got.as_slice(),
&data[range.start as usize..range.end as usize],
"decoded bytes differ from the source range"
);
}
#[test]
fn any_single_byte_mutation_is_rejected(
data in prop::collection::vec(any::<u8>(), 1..120_000),
size_groups in 1u64..4,
index in 0u64..8,
mutate_at in any::<prop::sample::Index>(),
xor in 1u8..=255,
) {
let chunk_size = size_groups * GROUP_SIZE;
let Some((enc, range)) = slice_for(&data, chunk_size, index) else {
return Ok(());
};
let root = blake3::hash(&data);
let pos = mutate_at.index(enc.len());
let mut bad = enc.clone();
bad[pos] ^= xor;
let mut leaked = Vec::new();
let verdict = decode_slice(&root, data.len() as u64, chunk_range(range.clone()), &bad, |_, d| {
leaked.extend_from_slice(d);
Ok(())
});
let honest = &data[range.start as usize..range.end as usize];
if verdict.is_ok() {
prop_assert_eq!(
leaked.as_slice(), honest,
"a mutated slice was accepted with different bytes"
);
} else {
prop_assert!(
honest.starts_with(&leaked),
"bytes emitted before rejection must be a genuine prefix"
);
}
}
#[test]
fn a_slice_cannot_be_replayed_at_another_index(
data in prop::collection::vec(any::<u8>(), 40_000..200_000),
size_groups in 1u64..3,
) {
let chunk_size = size_groups * GROUP_SIZE;
let Some((enc0, _)) = slice_for(&data, chunk_size, 0) else {
return Ok(());
};
let Some((_, range1)) = slice_for(&data, chunk_size, 1) else {
return Ok(());
};
let root = blake3::hash(&data);
let mut got = Vec::new();
let verdict = decode_slice(&root, data.len() as u64, chunk_range(range1.clone()), &enc0, |_, d| {
got.extend_from_slice(d);
Ok(())
});
if verdict.is_ok() {
prop_assert_eq!(
got.as_slice(),
&data[range1.start as usize..range1.end as usize],
"chunk 0's slice was accepted as chunk 1"
);
}
}
#[test]
fn arbitrary_slice_bytes_never_panic(
junk in prop::collection::vec(any::<u8>(), 0..4096),
total_len in 0u64..200_000,
index in 0u64..8,
) {
let root = blake3::hash(b"unrelated");
let chunk_size = GROUP_SIZE;
let start = (index * chunk_size).min(total_len);
let end = (start + chunk_size).min(total_len);
if start == end {
return Ok(());
}
let _ = decode_slice(&root, total_len, chunk_range(start..end), &junk, |_, _| Ok(()));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
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 decode_collect(
root: &blake3::Hash,
total_len: u64,
chunks: Range<ChunkNum>,
encoded: &[u8],
) -> std::io::Result<Vec<(u64, Vec<u8>)>> {
let mut leaves = Vec::new();
decode_slice(root, total_len, chunks, encoded, |off, data| {
leaves.push((off, data.to_vec()));
Ok(())
})?;
Ok(leaves)
}
#[test]
fn root_matches_plain_blake3() {
let data = pseudo_random(100_000, 1);
let ob = compute_outboard(Cursor::new(&data)).unwrap();
assert_eq!(ob.root, blake3::hash(&data));
}
#[test]
fn slice_roundtrip_interior_range() {
let data = pseudo_random(100_000, 2);
let ob = compute_outboard(Cursor::new(&data)).unwrap();
let chunks = chunk_range(16_384..49_152);
let slice = encode_slice(&data[..], &ob, chunks.clone()).unwrap();
assert!(slice.len() >= 32 * 1024);
assert!(slice.len() < 32 * 1024 + 1024);
let leaves = decode_collect(&ob.root, data.len() as u64, chunks, &slice).unwrap();
let rebuilt: Vec<u8> = leaves.iter().flat_map(|(_, d)| d.clone()).collect();
assert_eq!(leaves.first().unwrap().0, 16_384);
assert_eq!(rebuilt, data[16_384..49_152]);
}
#[test]
fn slice_roundtrip_unaligned_tail() {
let data = pseudo_random(100_000, 3);
let ob = compute_outboard(Cursor::new(&data)).unwrap();
let chunks = chunk_range(98_304..100_000);
let slice = encode_slice(&data[..], &ob, chunks.clone()).unwrap();
let leaves = decode_collect(&ob.root, data.len() as u64, chunks, &slice).unwrap();
let rebuilt: Vec<u8> = leaves.iter().flat_map(|(_, d)| d.clone()).collect();
assert_eq!(rebuilt, data[98_304..]);
}
#[test]
fn tampered_slice_rejected() {
let data = pseudo_random(100_000, 4);
let ob = compute_outboard(Cursor::new(&data)).unwrap();
let chunks = chunk_range(0..32_768);
let mut slice = encode_slice(&data[..], &ob, chunks.clone()).unwrap();
let n = slice.len();
slice[n - 10] ^= 0xff;
assert!(decode_collect(&ob.root, data.len() as u64, chunks, &slice).is_err());
}
#[test]
fn wrong_root_rejected() {
let data = pseudo_random(50_000, 5);
let ob = compute_outboard(Cursor::new(&data)).unwrap();
let chunks = chunk_range(0..50_000);
let slice = encode_slice(&data[..], &ob, chunks.clone()).unwrap();
let wrong = blake3::hash(b"not the data");
assert!(decode_collect(&wrong, data.len() as u64, chunks, &slice).is_err());
}
#[test]
fn tiny_blob_no_outboard() {
let data = pseudo_random(10_000, 6);
let ob = compute_outboard(Cursor::new(&data)).unwrap();
assert!(ob.data.is_empty());
let chunks = chunk_range(0..10_000);
let slice = encode_slice(&data[..], &ob, chunks.clone()).unwrap();
let leaves = decode_collect(&ob.root, data.len() as u64, chunks, &slice).unwrap();
assert_eq!(leaves.len(), 1);
assert_eq!(leaves[0].1, data);
}
#[test]
fn empty_blob() {
let ob = compute_outboard(Cursor::new(Vec::<u8>::new())).unwrap();
assert_eq!(ob.root, blake3::hash(b""));
let slice = encode_slice(&[][..], &ob, ChunkNum(0)..ChunkNum(0)).unwrap();
assert!(slice.is_empty());
}
}