use zerocopy::FromBytes;
use super::FormatFault;
use crate::entry::{EntryHeader, SEQUENCE_MASK, TOMBSTONE_BIT, compute_crc32, entry_size};
pub(crate) const BLOCK_HEADER_LEN: usize = 16;
pub(crate) const CODEC_NONE: u8 = 0;
const ENTRY_HEADER_LEN: usize = size_of::<EntryHeader>();
const CRC_COVERED_HEADER: usize = 12;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct BlockHeader {
pub codec: u8,
pub flags: u8,
pub stored_len: u32,
pub raw_len: u32,
pub crc32: u32,
}
fn block_crc(header: &[u8; BLOCK_HEADER_LEN], payload: &[u8]) -> u32 {
let mut hasher = crc32fast::Hasher::new();
hasher.update(&header[..CRC_COVERED_HEADER]);
hasher.update(payload);
hasher.finalize()
}
impl BlockHeader {
pub(crate) fn encode(&self) -> [u8; BLOCK_HEADER_LEN] {
let mut b = [0u8; BLOCK_HEADER_LEN];
b[0] = self.codec;
b[1] = self.flags;
b[4..8].copy_from_slice(&self.stored_len.to_le_bytes());
b[8..12].copy_from_slice(&self.raw_len.to_le_bytes());
b[12..16].copy_from_slice(&self.crc32.to_le_bytes());
b
}
pub(crate) fn decode(block: &[u8]) -> Result<Self, FormatFault> {
let Some((head, payload)) = block.split_first_chunk::<BLOCK_HEADER_LEN>() else {
return Err(FormatFault::corrupt("block is shorter than its header"));
};
let u32_at =
|at: usize| u32::from_le_bytes([head[at], head[at + 1], head[at + 2], head[at + 3]]);
let crc32 = u32_at(12);
let computed = block_crc(head, payload);
if computed != crc32 {
return Err(FormatFault::corrupt(format!(
"block CRC mismatch: stored {crc32:#x}, computed {computed:#x}"
)));
}
let codec = head[0];
let flags = head[1];
let reserved = u16::from_le_bytes([head[2], head[3]]);
if codec != CODEC_NONE {
return Err(FormatFault::unsupported(format!("block codec {codec}")));
}
if flags != 0 {
return Err(FormatFault::unsupported(format!("block flags {flags:#x}")));
}
if reserved != 0 {
return Err(FormatFault::unsupported(format!(
"block reserved bytes {reserved:#x}"
)));
}
Ok(Self {
codec,
flags,
stored_len: u32_at(4),
raw_len: u32_at(8),
crc32,
})
}
}
pub(crate) struct FinishedBlock {
pub first_h: u64,
pub entries: u32,
pub header: [u8; BLOCK_HEADER_LEN],
pub payload: Vec<u8>,
}
impl FinishedBlock {
pub(crate) fn len(&self) -> usize {
BLOCK_HEADER_LEN + self.payload.len()
}
#[cfg(test)]
pub(crate) fn to_bytes(&self) -> Vec<u8> {
[&self.header[..], &self.payload].concat()
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum BlockBuildError {
PayloadTooLarge,
TooManyEntries,
}
impl std::fmt::Display for BlockBuildError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::PayloadTooLarge => f.write_str("block length exceeds u32::MAX bytes"),
Self::TooManyEntries => f.write_str("block entry count exceeds u32::MAX"),
}
}
}
impl std::error::Error for BlockBuildError {}
fn checked_growth(
payload_len: usize,
entries: u32,
entry_len: usize,
) -> Result<(u32, u32), BlockBuildError> {
let next_len = payload_len
.checked_add(entry_len)
.filter(|&len| {
len.checked_add(BLOCK_HEADER_LEN)
.is_some_and(|block| u32::try_from(block).is_ok())
})
.ok_or(BlockBuildError::PayloadTooLarge)?;
let next_entries = entries
.checked_add(1)
.ok_or(BlockBuildError::TooManyEntries)?;
Ok((next_len as u32, next_entries))
}
pub(crate) struct BlockBuilder {
target: usize,
payload: Vec<u8>,
entries: u32,
first_h: u64,
last_h: u64,
}
impl BlockBuilder {
pub(crate) fn new(target_block_size: u32) -> Self {
let target = (target_block_size as usize).max(BLOCK_HEADER_LEN + 1);
Self {
target,
payload: Vec::with_capacity(target),
entries: 0,
first_h: 0,
last_h: 0,
}
}
pub(crate) fn is_empty(&self) -> bool {
self.entries == 0
}
pub(crate) fn fits(&self, h: u64, entry_len: usize) -> bool {
if self.entries == 0 || h == self.last_h {
return true;
}
BLOCK_HEADER_LEN
.checked_add(self.payload.len())
.and_then(|len| len.checked_add(entry_len))
.is_some_and(|len| len <= self.target)
}
pub(crate) fn fits_key(&self, entry_len: usize) -> bool {
self.is_empty()
|| BLOCK_HEADER_LEN
.checked_add(self.payload.len())
.and_then(|len| len.checked_add(entry_len))
.is_some_and(|len| len <= self.target)
}
pub(crate) fn push(&mut self, h: u64, entry: &[u8]) -> Result<(), BlockBuildError> {
let (_, next_entries) = checked_growth(self.payload.len(), self.entries, entry.len())?;
if self.entries == 0 {
self.first_h = h;
}
self.last_h = h;
self.payload.extend_from_slice(entry);
self.entries = next_entries;
Ok(())
}
pub(crate) fn finish(&mut self) -> FinishedBlock {
debug_assert!(!self.is_empty(), "an empty block is never written");
let len = u32::try_from(self.payload.len()).expect("push enforces the block payload bound");
let mut header = BlockHeader {
codec: CODEC_NONE,
flags: 0,
stored_len: len,
raw_len: len,
crc32: 0,
};
header.crc32 = block_crc(&header.encode(), &self.payload);
let payload = std::mem::replace(&mut self.payload, Vec::with_capacity(self.target));
let block = FinishedBlock {
first_h: self.first_h,
entries: self.entries,
header: header.encode(),
payload,
};
self.entries = 0;
self.first_h = 0;
self.last_h = 0;
block
}
}
pub(crate) fn decode_block(bytes: &[u8]) -> Result<&[u8], FormatFault> {
let header = BlockHeader::decode(bytes)?;
let payload = &bytes[BLOCK_HEADER_LEN..];
if header.stored_len as usize != payload.len() {
return Err(FormatFault::corrupt(format!(
"block holds {} payload bytes, its header says {}",
payload.len(),
header.stored_len
)));
}
if header.raw_len != header.stored_len {
return Err(FormatFault::corrupt(
"uncompressed block with different stored and raw lengths",
));
}
Ok(payload)
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct EntryRef<'a> {
pub gsn: u64,
pub crc32: u32,
pub key: &'a [u8],
pub value: &'a [u8],
pub raw: &'a [u8],
}
impl EntryRef<'_> {
pub(crate) fn is_tombstone(&self) -> bool {
self.gsn & TOMBSTONE_BIT != 0
}
pub(crate) fn sequence(&self) -> u64 {
self.gsn & SEQUENCE_MASK
}
pub(crate) fn verify_crc(&self) -> Result<(), FormatFault> {
let computed = compute_crc32(self.gsn, self.value.len() as u32, self.key, self.value);
if computed != self.crc32 {
return Err(FormatFault::corrupt(format!(
"entry CRC mismatch: stored {:#x}, computed {computed:#x}",
self.crc32
)));
}
Ok(())
}
}
pub(crate) struct EntryIter<'a> {
payload: &'a [u8],
offset: usize,
key_len: usize,
failed: bool,
}
impl<'a> EntryIter<'a> {
pub(crate) fn new(payload: &'a [u8], key_len: usize) -> Self {
Self {
payload,
offset: 0,
key_len,
failed: false,
}
}
}
impl<'a> Iterator for EntryIter<'a> {
type Item = Result<EntryRef<'a>, FormatFault>;
fn next(&mut self) -> Option<Self::Item> {
if self.failed || self.offset == self.payload.len() {
return None;
}
let rest = &self.payload[self.offset..];
let parsed = parse_entry(rest, self.key_len);
match parsed {
Ok(entry) => {
self.offset += entry.raw.len();
Some(Ok(entry))
}
Err(fault) => {
self.failed = true;
Some(Err(fault))
}
}
}
}
pub(crate) fn parse_entry(rest: &[u8], key_len: usize) -> Result<EntryRef<'_>, FormatFault> {
if rest.len() < ENTRY_HEADER_LEN {
return Err(FormatFault::corrupt("payload ends inside an entry header"));
}
let header = EntryHeader::read_from_bytes(&rest[..ENTRY_HEADER_LEN])
.map_err(|_| FormatFault::corrupt("unreadable entry header"))?;
let raw_len = ENTRY_HEADER_LEN
.checked_add(key_len)
.and_then(|len| len.checked_add(header.value_len as usize))
.ok_or_else(|| FormatFault::corrupt("entry length overflows usize"))?;
raw_len
.checked_add(7)
.ok_or_else(|| FormatFault::corrupt("aligned entry length overflows usize"))?;
let total = entry_size(key_len, header.value_len) as usize;
if total > rest.len() {
return Err(FormatFault::corrupt(format!(
"entry of {total} bytes does not fit the {} bytes left in its block",
rest.len()
)));
}
let key_end = ENTRY_HEADER_LEN + key_len;
let value_end = key_end + header.value_len as usize;
Ok(EntryRef {
gsn: header.gsn,
crc32: header.crc32,
key: &rest[ENTRY_HEADER_LEN..key_end],
value: &rest[key_end..value_end],
raw: &rest[..total],
})
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum Found {
Live(Vec<u8>),
Tombstone,
}
pub(crate) fn find_in_block(payload: &[u8], key: &[u8]) -> Result<Option<Found>, FormatFault> {
for entry in EntryIter::new(payload, key.len()) {
let entry = entry?;
if entry.key != key {
continue;
}
entry.verify_crc()?;
return Ok(Some(if entry.is_tombstone() {
Found::Tombstone
} else {
Found::Live(entry.value.to_vec())
}));
}
Ok(None)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::entry::serialize_entry;
const KEY_LEN: usize = 32;
fn key(tag: u8) -> [u8; KEY_LEN] {
[tag; KEY_LEN]
}
fn live(gsn: u64, tag: u8, value: &[u8]) -> Vec<u8> {
serialize_entry(gsn, &key(tag), value, false)
}
fn tombstone(gsn: u64, tag: u8) -> Vec<u8> {
serialize_entry(gsn, &key(tag), &[], true)
}
fn block_of(entries: &[(u64, Vec<u8>)]) -> Vec<u8> {
let mut b = BlockBuilder::new(16 * 1024);
for (h, e) in entries {
b.push(*h, e).unwrap();
}
b.finish().to_bytes()
}
#[test]
fn header_round_trips() {
let payload = [7u8; 1234];
let mut h = BlockHeader {
codec: CODEC_NONE,
flags: 0,
stored_len: 1234,
raw_len: 1234,
crc32: 0,
};
h.crc32 = block_crc(&h.encode(), &payload);
let block = [&h.encode()[..], &payload].concat();
assert_eq!(BlockHeader::decode(&block).unwrap(), h);
}
#[test]
fn header_numbers_are_little_endian() {
let h = BlockHeader {
codec: CODEC_NONE,
flags: 0,
stored_len: 0x0102_0304,
raw_len: 0x0506_0708,
crc32: 0x090a_0b0c,
};
assert_eq!(
h.encode(),
[0, 0, 0, 0, 4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9]
);
}
fn reseal(bytes: &mut [u8]) {
let mut h = crc32fast::Hasher::new();
h.update(&bytes[..12]);
h.update(&bytes[BLOCK_HEADER_LEN..]);
let crc = h.finalize();
bytes[12..16].copy_from_slice(&crc.to_le_bytes());
}
#[test]
fn block_bytes_are_pinned() {
let bytes = block_of(&[(5, b"abcdefgh".to_vec())]);
let mut expected = vec![0, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 0x05, 0x87, 0x07, 0xb1];
expected.extend_from_slice(b"abcdefgh");
assert_eq!(bytes, expected);
assert_eq!(decode_block(&bytes).unwrap(), b"abcdefgh");
}
#[test]
fn a_damaged_header_byte_is_corruption_not_another_format() {
let good = block_of(&[(1, live(1, 1, b"payload"))]);
for at in 0..12 {
for bit in [0x01u8, 0x80] {
let mut bytes = good.clone();
bytes[at] ^= bit;
assert!(
matches!(decode_block(&bytes), Err(FormatFault::Corrupt(m)) if m.contains("CRC")),
"byte {at} bit {bit:#x}: {:?}",
decode_block(&bytes)
);
}
}
}
#[test]
fn a_block_whose_crc_holds_may_claim_an_unknown_format() {
let good = block_of(&[(1, live(1, 1, b"payload"))]);
for (at, value, what) in [(0, 9u8, "codec"), (1, 1, "flags"), (2, 1, "reserved")] {
let mut bytes = good.clone();
bytes[at] = value;
reseal(&mut bytes);
assert!(
matches!(decode_block(&bytes), Err(FormatFault::Unsupported(m)) if m.contains(what)),
"{what}: {:?}",
decode_block(&bytes)
);
}
}
#[test]
fn a_block_round_trips_and_finds_its_entries() {
let bytes = block_of(&[
(10, live(1, 1, b"one")),
(20, tombstone(2, 2)),
(30, live(3, 3, b"")),
]);
let payload = decode_block(&bytes).unwrap();
assert_eq!(
find_in_block(payload, &key(1)).unwrap(),
Some(Found::Live(b"one".to_vec()))
);
assert_eq!(
find_in_block(payload, &key(2)).unwrap(),
Some(Found::Tombstone)
);
assert_eq!(
find_in_block(payload, &key(3)).unwrap(),
Some(Found::Live(Vec::new()))
);
assert_eq!(find_in_block(payload, &key(9)).unwrap(), None);
}
#[test]
fn two_keys_with_one_hash_are_both_found() {
let bytes = block_of(&[(77, live(1, 1, b"a")), (77, live(2, 2, b"b"))]);
let payload = decode_block(&bytes).unwrap();
assert_eq!(
find_in_block(payload, &key(1)).unwrap(),
Some(Found::Live(b"a".to_vec()))
);
assert_eq!(
find_in_block(payload, &key(2)).unwrap(),
Some(Found::Live(b"b".to_vec()))
);
}
#[test]
fn the_iterator_yields_entries_with_their_raw_bytes() {
let a = live(5, 1, b"value-a");
let b = tombstone(6, 2);
let bytes = block_of(&[(1, a.clone()), (2, b.clone())]);
let payload = decode_block(&bytes).unwrap();
let entries: Vec<_> = EntryIter::new(payload, KEY_LEN)
.collect::<Result<_, _>>()
.unwrap();
assert_eq!(entries.len(), 2);
assert_eq!(entries[0].raw, &a[..]);
assert_eq!(entries[0].sequence(), 5);
assert!(!entries[0].is_tombstone());
assert_eq!(entries[1].raw, &b[..]);
assert_eq!(entries[1].sequence(), 6);
assert!(entries[1].is_tombstone());
for e in &entries {
e.verify_crc().unwrap();
}
}
#[test]
fn a_flipped_payload_byte_fails_the_block_crc() {
let mut bytes = block_of(&[(1, live(1, 1, b"payload"))]);
let last = bytes.len() - 9;
bytes[last] ^= 0x01;
assert!(matches!(
decode_block(&bytes),
Err(FormatFault::Corrupt(m)) if m.contains("CRC")
));
}
#[test]
fn a_truncated_block_is_corrupt_not_a_panic() {
let bytes = block_of(&[(1, live(1, 1, b"payload")), (2, live(2, 2, b"more"))]);
for cut in [0, 1, 15, 16, 17, bytes.len() - 1] {
assert!(
matches!(decode_block(&bytes[..cut]), Err(FormatFault::Corrupt(_))),
"cut at {cut}"
);
}
}
#[test]
fn a_payload_that_ends_inside_an_entry_is_corrupt() {
let entry = live(1, 1, b"payload");
let cut = &entry[..entry.len() - 8];
let mut iter = EntryIter::new(cut, KEY_LEN);
assert!(matches!(iter.next(), Some(Err(FormatFault::Corrupt(_)))));
assert!(iter.next().is_none(), "the iterator stops after a fault");
assert!(matches!(
find_in_block(cut, &key(1)),
Err(FormatFault::Corrupt(_))
));
}
#[test]
fn an_impossible_key_length_returns_a_fault_without_panicking() {
let entry = live(1, 1, b"payload");
let mut iter = EntryIter::new(&entry, usize::MAX);
assert!(matches!(iter.next(), Some(Err(FormatFault::Corrupt(_)))));
}
#[test]
fn an_entry_whose_own_crc_is_wrong_is_reported() {
let mut entry = live(1, 1, b"payload");
let value_at = 16 + KEY_LEN;
entry[value_at] ^= 0x01;
assert!(matches!(
find_in_block(&entry, &key(1)),
Err(FormatFault::Corrupt(m)) if m.contains("entry CRC")
));
}
#[test]
fn packing_fills_a_block_up_to_the_target() {
let entry = live(1, 1, &[0u8; 100]);
let target = 1024u32;
let mut b = BlockBuilder::new(target);
let mut h = 0u64;
while b.fits(h, entry.len()) {
b.push(h, &entry).unwrap();
h += 1;
}
let block = b.finish();
assert!(block.len() <= target as usize);
assert!(block.len() + entry.len() > target as usize);
assert_eq!(block.entries as u64, h);
assert_eq!(block.first_h, 0);
assert!(b.is_empty(), "finish resets the builder");
}
#[test]
fn an_oversized_entry_gets_a_block_of_its_own() {
let big = live(1, 1, &[0u8; 4096]);
let mut b = BlockBuilder::new(1024);
assert!(b.fits(1, big.len()), "an empty block takes anything");
b.push(1, &big).unwrap();
assert!(!b.fits(2, 8), "nothing else fits after it");
let block = b.finish();
assert_eq!(block.entries, 1);
assert!(block.len() > 1024);
}
#[test]
fn equal_hashes_never_split_across_blocks() {
let entry = live(1, 1, &[0u8; 400]);
let mut b = BlockBuilder::new(1024);
b.push(5, &entry).unwrap();
b.push(5, &entry).unwrap();
assert!(b.fits(5, entry.len()));
assert!(!b.fits(6, entry.len()));
}
#[test]
fn an_impossible_entry_length_does_not_fit() {
let mut b = BlockBuilder::new(1024);
b.push(1, &live(1, 1, b"a")).unwrap();
assert!(!b.fits(2, usize::MAX));
}
#[test]
fn payload_growth_rejects_unencodable_lengths() {
let max_payload = u32::MAX as usize - BLOCK_HEADER_LEN;
assert_eq!(
checked_growth(max_payload - 1, 0, 1),
Ok((max_payload as u32, 1))
);
assert_eq!(
checked_growth(max_payload, 1, 1),
Err(BlockBuildError::PayloadTooLarge)
);
assert_eq!(
checked_growth(u32::MAX as usize - 1, 1, 1),
Err(BlockBuildError::PayloadTooLarge)
);
assert_eq!(
checked_growth(1, 1, usize::MAX),
Err(BlockBuildError::PayloadTooLarge)
);
}
#[test]
fn push_rejects_entry_count_overflow_without_changing_builder() {
let mut b = BlockBuilder::new(1024);
b.push(5, b"a").unwrap();
b.entries = u32::MAX;
assert_eq!(b.push(6, b"b"), Err(BlockBuildError::TooManyEntries));
assert_eq!(b.payload, b"a");
assert_eq!(b.first_h, 5);
assert_eq!(b.last_h, 5);
assert_eq!(b.entries, u32::MAX);
}
}