use crate::compression::validate_compression_frame_lengths;
use crate::constants::{
DEFAULT_DIRECTORY_PERMISSIONS, DEFAULT_FILE_PERMISSIONS, DEFAULT_SYMLINK_PERMISSIONS,
};
use crate::file_chunk::{CompressionFrameSegment, FileChunk};
use crate::node_kind::NodeKind;
use crate::security::validate_permissions;
use crate::toc_entry::TocEntry;
use crate::{Error, LockboxPath, Result};
const PATH_RESTART_INTERVAL: usize = 128;
const ENTRY_FLAG_DELETED: u8 = 0x01;
const ENTRY_FLAG_SYMLINK: u8 = 0x02;
const ENTRY_FLAG_CUSTOM_PERMISSIONS: u8 = 0x04;
const ENTRY_FLAG_DIRECTORY: u8 = 0x08;
#[cfg(test)]
pub(crate) fn encode_toc(
toc_entries: &std::collections::BTreeMap<LockboxPath, TocEntry>,
) -> Vec<u8> {
encode_toc_entries(toc_entries.values())
}
#[cfg(test)]
pub(crate) fn encode_toc_entries<'a>(entries: impl IntoIterator<Item = &'a TocEntry>) -> Vec<u8> {
TocEncoder::new(entries).encode()
}
pub(crate) struct TocEncoder<'a> {
entries: Vec<&'a TocEntry>,
descriptors: Vec<FrameDescriptor>,
}
impl<'a> TocEncoder<'a> {
pub(crate) fn version(&self) -> u8 {
if block_markers_len(&self.descriptors) != 0 {
2
} else {
1
}
}
pub(crate) fn new(entries: impl IntoIterator<Item = &'a TocEntry>) -> Self {
let entries = entries.into_iter().collect::<Vec<_>>();
let descriptors = frame_descriptors(&entries);
Self {
entries,
descriptors,
}
}
pub(crate) fn encode(&self) -> Vec<u8> {
let mut out = Vec::new();
put_varint(self.entries.len() as u64, &mut out);
put_varint(self.descriptors.len() as u64, &mut out);
let block_format = self.version() == 2;
for descriptor in &self.descriptors {
encode_frame_descriptor(descriptor, &mut out, block_format);
}
let mut previous_path = "";
for (index, entry) in self.entries.iter().enumerate() {
let default_permissions = default_permissions(entry.node_kind);
let mut flags = 0u8;
if entry.deleted {
flags |= ENTRY_FLAG_DELETED;
}
if entry.node_kind == NodeKind::Symlink {
flags |= ENTRY_FLAG_SYMLINK;
}
if entry.node_kind == NodeKind::Directory {
flags |= ENTRY_FLAG_DIRECTORY;
}
if entry.permissions != default_permissions {
flags |= ENTRY_FLAG_CUSTOM_PERMISSIONS;
}
out.push(flags);
encode_path(entry.path.as_str(), previous_path, index, &mut out);
put_varint(entry.len, &mut out);
put_varint(entry.record_offset, &mut out);
put_varint(entry.record_len, &mut out);
put_varint(entry.record_object_id, &mut out);
out.extend_from_slice(&entry.record_digest);
if flags & ENTRY_FLAG_CUSTOM_PERMISSIONS != 0 {
put_varint(entry.permissions as u64, &mut out);
}
put_varint(entry.chunks.len() as u64, &mut out);
for chunk in &entry.chunks {
let stored_path = if chunk.stored_path == entry.path.as_str() {
""
} else {
chunk.stored_path.as_str()
};
put_varint(stored_path.len() as u64, &mut out);
out.extend_from_slice(stored_path.as_bytes());
put_varint(chunk.file_offset, &mut out);
put_varint(chunk.len, &mut out);
put_varint(chunk.compression_frame_offset, &mut out);
let descriptor_index =
frame_descriptor_index(&self.descriptors, chunk).unwrap_or(0);
put_varint(descriptor_index as u64, &mut out);
}
previous_path = entry.path.as_str();
}
out
}
pub(crate) fn encoded_len(&self) -> usize {
encoded_toc_count_len(self.entries.len())
+ block_markers_len(&self.descriptors)
+ encoded_toc_count_len(self.descriptors.len())
+ self
.descriptors
.iter()
.map(encoded_descriptor_len)
.sum::<usize>()
+ encoded_entries_with_descriptors_len(&self.entries, &self.descriptors)
}
}
#[cfg(test)]
pub(crate) fn encoded_toc_entries_len(entries: &[TocEntry]) -> usize {
TocEncoder::new(entries).encoded_len()
}
pub(crate) fn encoded_toc_count_len(count: usize) -> usize {
varint_len(count as u64)
}
#[derive(Debug, Default)]
pub(crate) struct TocEntriesLenEstimator {
count: usize,
descriptors: Vec<FrameDescriptor>,
descriptor_len: usize,
entries_len: usize,
previous_path: String,
}
impl TocEntriesLenEstimator {
pub(crate) fn new() -> Self {
Self::default()
}
pub(crate) fn count(&self) -> usize {
self.count
}
pub(crate) fn clear(&mut self) {
self.count = 0;
self.descriptors.clear();
self.descriptor_len = 0;
self.entries_len = 0;
self.previous_path.clear();
}
pub(crate) fn push(&mut self, entry: &TocEntry) {
for chunk in &entry.chunks {
if frame_descriptor_index(&self.descriptors, chunk).is_none() {
let descriptor = FrameDescriptor::from_chunk(chunk);
self.descriptor_len += encoded_descriptor_len(&descriptor);
self.descriptors.push(descriptor);
}
}
self.entries_len += encoded_toc_entry_len(
entry,
Some(&self.previous_path),
self.count,
&self.descriptors,
);
self.previous_path.clear();
self.previous_path.push_str(entry.path.as_str());
self.count += 1;
}
pub(crate) fn encoded_len(&self) -> usize {
encoded_toc_count_len(self.count)
+ block_markers_len(&self.descriptors)
+ encoded_toc_count_len(self.descriptors.len())
+ self.descriptor_len
+ self.entries_len
}
}
fn encoded_entries_with_descriptors_len(
entries: &[&TocEntry],
descriptors: &[FrameDescriptor],
) -> usize {
entries
.iter()
.enumerate()
.map(|(index, entry)| {
let previous_path = index
.checked_sub(1)
.and_then(|previous| entries.get(previous))
.map(|entry| entry.path.as_str());
encoded_toc_entry_len(entry, previous_path, index, descriptors)
})
.sum::<usize>()
}
fn encoded_toc_entry_len(
entry: &TocEntry,
previous_path: Option<&str>,
index: usize,
descriptors: &[FrameDescriptor],
) -> usize {
let default_permissions = default_permissions(entry.node_kind);
1 + encoded_path_len(entry.path.as_str(), previous_path.unwrap_or(""), index)
+ varint_len(entry.len)
+ varint_len(entry.record_offset)
+ varint_len(entry.record_len)
+ varint_len(entry.record_object_id)
+ 32
+ if entry.permissions == default_permissions {
0
} else {
varint_len(entry.permissions as u64)
}
+ varint_len(entry.chunks.len() as u64)
+ entry
.chunks
.iter()
.map(|chunk| encoded_chunk_len(entry, chunk, descriptors))
.sum::<usize>()
}
#[cfg(test)]
pub(crate) fn decode_toc(
payload: &[u8],
) -> Result<std::collections::BTreeMap<LockboxPath, TocEntry>> {
Ok(decode_toc_entries(payload)?
.into_iter()
.map(|entry| (entry.path.clone(), entry))
.collect())
}
#[cfg(test)]
pub(crate) fn decode_toc_entries(payload: &[u8]) -> Result<Vec<TocEntry>> {
TocDecoder::new(payload).decode()
}
pub(crate) struct TocDecoder<'a> {
payload: &'a [u8],
block_format: bool,
}
impl<'a> TocDecoder<'a> {
pub(crate) fn new(payload: &'a [u8]) -> Self {
Self {
payload,
block_format: false,
}
}
#[cfg(any(test, feature = "native-block-layout"))]
pub(crate) fn with_block_frames(mut self) -> Self {
self.block_format = true;
self
}
pub(crate) fn decode(self) -> Result<Vec<TocEntry>> {
let payload = self.payload;
let mut offset = 0;
let count = usize::try_from(take_varint(payload, &mut offset)?)
.map_err(|_| Error::CorruptRecord)?;
if count > payload.len().saturating_sub(offset) {
return Err(Error::CorruptRecord);
}
let descriptor_count = usize::try_from(take_varint(payload, &mut offset)?)
.map_err(|_| Error::CorruptRecord)?;
if descriptor_count > payload.len().saturating_sub(offset) {
return Err(Error::CorruptRecord);
}
let mut descriptors = Vec::with_capacity(descriptor_count);
for _ in 0..descriptor_count {
descriptors.push(decode_frame_descriptor(
payload,
&mut offset,
self.block_format,
)?);
}
let mut entries = Vec::with_capacity(count);
let mut previous_path = String::new();
for index in 0..count {
if offset >= payload.len() {
return Err(Error::CorruptRecord);
}
let flags = payload[offset];
offset += 1;
if flags
& !(ENTRY_FLAG_DELETED
| ENTRY_FLAG_SYMLINK
| ENTRY_FLAG_CUSTOM_PERMISSIONS
| ENTRY_FLAG_DIRECTORY)
!= 0
{
return Err(Error::CorruptRecord);
}
if flags & ENTRY_FLAG_SYMLINK != 0 && flags & ENTRY_FLAG_DIRECTORY != 0 {
return Err(Error::CorruptRecord);
}
let path = decode_path(payload, &mut offset, &previous_path, index)?;
let path = LockboxPath::from_stored(&path, false)?;
let next_previous_path = path.as_str().to_string();
let len = take_varint(payload, &mut offset)?;
let record_offset = take_varint(payload, &mut offset)?;
let record_len = take_varint(payload, &mut offset)?;
let record_object_id = take_varint(payload, &mut offset)?;
let record_digest = payload
.get(offset..offset.checked_add(32).ok_or(Error::CorruptRecord)?)
.ok_or(Error::CorruptRecord)?
.try_into()
.map_err(|_| Error::CorruptRecord)?;
offset += 32;
let deleted = flags & ENTRY_FLAG_DELETED != 0;
let node_kind = NodeKind::from_u8(if flags & ENTRY_FLAG_DIRECTORY != 0 {
3
} else if flags & ENTRY_FLAG_SYMLINK != 0 {
2
} else {
1
})?;
let permissions = if flags & ENTRY_FLAG_CUSTOM_PERMISSIONS == 0 {
default_permissions(node_kind)
} else {
u32::try_from(take_varint(payload, &mut offset)?)
.map_err(|_| Error::CorruptRecord)?
};
let permissions = validate_permissions(permissions)?;
let chunk_count = usize::try_from(take_varint(payload, &mut offset)?)
.map_err(|_| Error::CorruptRecord)?;
if chunk_count > payload.len().saturating_sub(offset) {
return Err(Error::CorruptRecord);
}
let mut chunks = Vec::with_capacity(chunk_count);
for _ in 0..chunk_count {
let stored_path_len = usize::try_from(take_varint(payload, &mut offset)?)
.map_err(|_| Error::CorruptRecord)?;
if stored_path_len > payload.len().saturating_sub(offset) {
return Err(Error::CorruptRecord);
}
let stored_path = if stored_path_len == 0 {
path.clone()
} else {
let stored_path =
String::from_utf8(payload[offset..offset + stored_path_len].to_vec())
.map_err(|_| Error::CorruptRecord)?;
LockboxPath::from_stored(&stored_path, false)?
};
offset += stored_path_len;
let file_offset = take_varint(payload, &mut offset)?;
let chunk_len = take_varint(payload, &mut offset)?;
let compression_frame_offset = take_varint(payload, &mut offset)?;
let descriptor_index = usize::try_from(take_varint(payload, &mut offset)?)
.map_err(|_| Error::CorruptRecord)?;
let descriptor = descriptors
.get(descriptor_index)
.ok_or(Error::CorruptRecord)?;
chunks.push(FileChunk {
#[cfg(any(test, feature = "native-block-layout"))]
block_frame: descriptor.block_frame.clone(),
stored_path,
file_offset,
len: chunk_len,
compression_frame_offset,
compression_frame_len: descriptor.compression_frame_len,
compressed_len: descriptor.compressed_len,
compression: descriptor.compression,
compression_frame_id: descriptor.compression_frame_id,
compression_frame_digest: descriptor.compression_frame_digest,
segments: descriptor.segments.clone(),
});
}
match node_kind {
NodeKind::Symlink
if record_offset == 0 || record_len == 0 || record_object_id == 0 =>
{
return Err(Error::CorruptRecord);
}
NodeKind::Symlink if !chunks.is_empty() => return Err(Error::CorruptRecord),
NodeKind::Directory
if len != 0
|| record_offset != 0
|| record_len != 0
|| record_object_id != 0
|| !chunks.is_empty() =>
{
return Err(Error::CorruptRecord);
}
_ => {}
}
entries.push(TocEntry {
path,
len,
record_offset,
record_len,
record_object_id,
record_digest,
deleted,
node_kind,
permissions,
chunks,
});
previous_path = next_previous_path;
}
if offset != payload.len() {
return Err(Error::CorruptRecord);
}
Ok(entries)
}
}
fn encode_path(path: &str, previous_path: &str, index: usize, out: &mut Vec<u8>) {
if path_restart(index) {
put_varint(path.len() as u64, out);
out.extend_from_slice(path.as_bytes());
return;
}
let prefix_len = common_prefix_len(previous_path, path);
let suffix = &path.as_bytes()[prefix_len..];
put_varint(prefix_len as u64, out);
put_varint(suffix.len() as u64, out);
out.extend_from_slice(suffix);
}
fn decode_path(
payload: &[u8],
offset: &mut usize,
previous_path: &str,
index: usize,
) -> Result<String> {
if path_restart(index) {
let path_len =
usize::try_from(take_varint(payload, offset)?).map_err(|_| Error::CorruptRecord)?;
if path_len > payload.len().saturating_sub(*offset) {
return Err(Error::CorruptRecord);
}
let path = String::from_utf8(payload[*offset..*offset + path_len].to_vec())
.map_err(|_| Error::CorruptRecord)?;
*offset += path_len;
return Ok(path);
}
let prefix_len =
usize::try_from(take_varint(payload, offset)?).map_err(|_| Error::CorruptRecord)?;
let suffix_len =
usize::try_from(take_varint(payload, offset)?).map_err(|_| Error::CorruptRecord)?;
if prefix_len > previous_path.len()
|| !previous_path.is_char_boundary(prefix_len)
|| suffix_len > payload.len().saturating_sub(*offset)
{
return Err(Error::CorruptRecord);
}
let mut path = Vec::with_capacity(prefix_len + suffix_len);
path.extend_from_slice(&previous_path.as_bytes()[..prefix_len]);
path.extend_from_slice(&payload[*offset..*offset + suffix_len]);
*offset += suffix_len;
String::from_utf8(path).map_err(|_| Error::CorruptRecord)
}
fn encoded_path_len(path: &str, previous_path: &str, index: usize) -> usize {
if path_restart(index) {
return varint_len(path.len() as u64) + path.len();
}
let prefix_len = common_prefix_len(previous_path, path);
let suffix_len = path.len() - prefix_len;
varint_len(prefix_len as u64) + varint_len(suffix_len as u64) + suffix_len
}
#[derive(Debug, Clone, PartialEq, Eq)]
struct FrameDescriptor {
#[cfg(any(test, feature = "native-block-layout"))]
block_frame: Option<std::sync::Arc<crate::file_chunk::BlockFrameReference>>,
compression_frame_id: u64,
compression: u8,
compression_frame_len: u64,
compressed_len: u64,
compression_frame_digest: [u8; 32],
segments: Vec<CompressionFrameSegment>,
}
impl FrameDescriptor {
fn from_chunk(chunk: &FileChunk) -> Self {
Self {
#[cfg(any(test, feature = "native-block-layout"))]
block_frame: chunk.block_frame.clone(),
compression_frame_id: chunk.compression_frame_id,
compression: chunk.compression,
compression_frame_len: chunk.compression_frame_len,
compressed_len: chunk.compressed_len,
compression_frame_digest: chunk.compression_frame_digest,
segments: chunk.segments.clone(),
}
}
fn matches_chunk(&self, chunk: &FileChunk) -> bool {
self.same_block_layout(chunk)
&& self.compression_frame_id == chunk.compression_frame_id
&& self.compression == chunk.compression
&& self.compression_frame_len == chunk.compression_frame_len
&& self.compressed_len == chunk.compressed_len
&& self.compression_frame_digest == chunk.compression_frame_digest
&& self.segments == chunk.segments
}
fn same_block_layout(&self, chunk: &FileChunk) -> bool {
#[cfg(any(test, feature = "native-block-layout"))]
{
self.block_frame == chunk.block_frame
}
#[cfg(not(any(test, feature = "native-block-layout")))]
{
let _ = chunk;
true
}
}
fn block_extra_len(&self) -> usize {
#[cfg(any(test, feature = "native-block-layout"))]
{
self.block_frame.as_ref().map_or(0, |block| {
crate::file_format::indexed_frame::BlockFrameDescriptor::ENCODED_LEN
+ varint_len(block.sequence)
})
}
#[cfg(not(any(test, feature = "native-block-layout")))]
{
0
}
}
}
fn block_markers_len(descriptors: &[FrameDescriptor]) -> usize {
#[cfg(any(test, feature = "native-block-layout"))]
if descriptors
.iter()
.any(|descriptor| descriptor.block_frame.is_some())
{
return descriptors.len();
}
let _ = descriptors;
0
}
fn frame_descriptors(entries: &[&TocEntry]) -> Vec<FrameDescriptor> {
let mut descriptors = Vec::new();
for entry in entries {
for chunk in &entry.chunks {
if frame_descriptor_index(&descriptors, chunk).is_none() {
descriptors.push(FrameDescriptor::from_chunk(chunk));
}
}
}
descriptors
}
fn frame_descriptor_index(descriptors: &[FrameDescriptor], chunk: &FileChunk) -> Option<usize> {
descriptors
.iter()
.position(|descriptor| descriptor.matches_chunk(chunk))
}
fn encode_frame_descriptor(descriptor: &FrameDescriptor, out: &mut Vec<u8>, block_format: bool) {
put_varint(descriptor.compression_frame_id, out);
put_varint(descriptor.compression as u64, out);
put_varint(descriptor.compression_frame_len, out);
put_varint(descriptor.compressed_len, out);
out.extend_from_slice(&descriptor.compression_frame_digest);
put_varint(descriptor.segments.len() as u64, out);
for segment in &descriptor.segments {
put_varint(segment.page_offset, out);
put_varint(segment.page_len, out);
put_varint(segment.object_id, out);
put_varint(segment.segment_offset, out);
put_varint(segment.segment_len, out);
}
if block_format {
#[cfg(any(test, feature = "native-block-layout"))]
{
if let Some(block) = &descriptor.block_frame {
out.push(1);
out.extend_from_slice(
&block
.descriptor
.encode()
.expect("validated native block descriptor"),
);
put_varint(block.sequence, out);
} else {
out.push(0);
}
}
#[cfg(not(any(test, feature = "native-block-layout")))]
unreachable!("block TOC writing is staged until archive integration is complete");
}
}
fn decode_frame_descriptor(
payload: &[u8],
offset: &mut usize,
block_format: bool,
) -> Result<FrameDescriptor> {
#[cfg(not(any(test, feature = "native-block-layout")))]
if block_format {
return Err(Error::CorruptRecord);
}
let compression_frame_id = take_varint(payload, offset)?;
let compression =
u8::try_from(take_varint(payload, offset)?).map_err(|_| Error::CorruptRecord)?;
let compression_frame_len = take_varint(payload, offset)?;
let compressed_len = take_varint(payload, offset)?;
validate_compression_frame_lengths(compression_frame_len, compressed_len)?;
if *offset + 32 > payload.len() {
return Err(Error::CorruptRecord);
}
let mut compression_frame_digest = [0u8; 32];
compression_frame_digest.copy_from_slice(&payload[*offset..*offset + 32]);
*offset += 32;
let segment_count =
usize::try_from(take_varint(payload, offset)?).map_err(|_| Error::CorruptRecord)?;
if segment_count > payload.len().saturating_sub(*offset) {
return Err(Error::CorruptRecord);
}
let mut segments = Vec::with_capacity(segment_count);
for _ in 0..segment_count {
let page_offset = take_varint(payload, offset)?;
let page_len = take_varint(payload, offset)?;
let object_id = take_varint(payload, offset)?;
let segment_offset = take_varint(payload, offset)?;
let segment_len = take_varint(payload, offset)?;
if segment_offset
.checked_add(segment_len)
.is_none_or(|end| end > compressed_len)
{
return Err(Error::CorruptRecord);
}
segments.push(CompressionFrameSegment {
page_offset,
page_len,
object_id,
segment_offset,
segment_len,
});
}
#[cfg(any(test, feature = "native-block-layout"))]
let block_frame = if block_format {
decode_block_reference(payload, offset)?
} else {
None
};
let descriptor = FrameDescriptor {
#[cfg(any(test, feature = "native-block-layout"))]
block_frame,
compression_frame_id,
compression,
compression_frame_len,
compressed_len,
compression_frame_digest,
segments,
};
#[cfg(any(test, feature = "native-block-layout"))]
validate_block_reference(&descriptor)?;
Ok(descriptor)
}
#[cfg(any(test, feature = "native-block-layout"))]
fn decode_block_reference(
payload: &[u8],
offset: &mut usize,
) -> Result<Option<std::sync::Arc<crate::file_chunk::BlockFrameReference>>> {
use crate::file_format::indexed_frame::BlockFrameDescriptor;
let marker = *payload.get(*offset).ok_or(Error::CorruptRecord)?;
*offset += 1;
match marker {
0 => Ok(None),
1 => {
let bytes = payload
.get(*offset..)
.and_then(|tail| tail.get(..BlockFrameDescriptor::ENCODED_LEN))
.ok_or(Error::CorruptRecord)?;
let archive = crate::LockboxId::from_bytes(
bytes[16..32].try_into().map_err(|_| Error::CorruptRecord)?,
);
let mode = crate::creation_options::FormatMode::parse(crate::checked::read_u16_le(
&bytes[8..10],
)?)?;
let descriptor = BlockFrameDescriptor::decode(bytes, archive, mode)?;
*offset += BlockFrameDescriptor::ENCODED_LEN;
let sequence = take_varint(payload, offset)?;
Ok(Some(std::sync::Arc::new(
crate::file_chunk::BlockFrameReference {
descriptor,
sequence,
},
)))
}
_ => Err(Error::CorruptRecord),
}
}
#[cfg(any(test, feature = "native-block-layout"))]
fn validate_block_reference(frame: &FrameDescriptor) -> Result<()> {
if let Some(block) = &frame.block_frame {
let descriptor = &block.descriptor;
if descriptor.frame_id != frame.compression_frame_id
|| descriptor.compression != frame.compression
|| descriptor.logical_len != frame.compression_frame_len
|| descriptor.stored_len != frame.compressed_len
|| descriptor.index_commitment != frame.compression_frame_digest
{
return Err(Error::CorruptRecord);
}
let [segment] = frame.segments.as_slice() else {
return Err(Error::CorruptRecord);
};
if segment.segment_offset != 0
|| segment.segment_len != frame.compressed_len
|| segment.object_id == 0
|| segment.page_len < (crate::page::PAGE_HEADER_LEN + descriptor.physical_len()?) as u64
|| segment.page_len > crate::page::DEFAULT_DATA_PAGE_BYTES as u64
|| segment.page_offset.checked_add(segment.page_len).is_none()
|| (!descriptor.mode.unpadded() && segment.page_len % 1024 != 0)
{
return Err(Error::CorruptRecord);
}
}
Ok(())
}
fn encoded_descriptor_len(descriptor: &FrameDescriptor) -> usize {
varint_len(descriptor.compression_frame_id)
+ descriptor.block_extra_len()
+ varint_len(descriptor.compression as u64)
+ varint_len(descriptor.compression_frame_len)
+ varint_len(descriptor.compressed_len)
+ 32
+ varint_len(descriptor.segments.len() as u64)
+ descriptor
.segments
.iter()
.map(encoded_segment_len)
.sum::<usize>()
}
fn encoded_chunk_len(
entry: &TocEntry,
chunk: &FileChunk,
descriptors: &[FrameDescriptor],
) -> usize {
let stored_path_len = if chunk.stored_path == entry.path.as_str() {
0
} else {
chunk.stored_path.len()
};
varint_len(stored_path_len as u64)
+ stored_path_len
+ varint_len(chunk.file_offset)
+ varint_len(chunk.len)
+ varint_len(chunk.compression_frame_offset)
+ varint_len(frame_descriptor_index(descriptors, chunk).unwrap_or(0) as u64)
}
fn encoded_segment_len(segment: &CompressionFrameSegment) -> usize {
varint_len(segment.page_offset)
+ varint_len(segment.page_len)
+ varint_len(segment.object_id)
+ varint_len(segment.segment_offset)
+ varint_len(segment.segment_len)
}
fn path_restart(index: usize) -> bool {
index.is_multiple_of(PATH_RESTART_INTERVAL)
}
fn common_prefix_len(previous: &str, current: &str) -> usize {
let mut len = previous
.as_bytes()
.iter()
.zip(current.as_bytes())
.take_while(|(left, right)| left == right)
.count();
while len > 0 && !current.is_char_boundary(len) {
len -= 1;
}
len
}
fn default_permissions(node_kind: NodeKind) -> u32 {
match node_kind {
NodeKind::File => DEFAULT_FILE_PERMISSIONS,
NodeKind::Symlink => DEFAULT_SYMLINK_PERMISSIONS,
NodeKind::Directory => DEFAULT_DIRECTORY_PERMISSIONS,
}
}
fn put_varint(mut value: u64, out: &mut Vec<u8>) {
while value >= 0x80 {
out.push((value as u8) | 0x80);
value >>= 7;
}
out.push(value as u8);
}
fn take_varint(payload: &[u8], cursor: &mut usize) -> Result<u64> {
let mut value = 0u64;
let mut shift = 0u32;
for _ in 0..10 {
if *cursor >= payload.len() {
return Err(Error::CorruptRecord);
}
let byte = payload[*cursor];
*cursor += 1;
value |= u64::from(byte & 0x7f) << shift;
if byte & 0x80 == 0 {
return Ok(value);
}
shift += 7;
}
Err(Error::CorruptRecord)
}
pub(crate) fn varint_len(mut value: u64) -> usize {
let mut len = 1;
while value >= 0x80 {
len += 1;
value >>= 7;
}
len
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::BTreeMap;
fn native_fixture(mode: crate::creation_options::FormatMode) -> (Vec<TocEntry>, Vec<u8>) {
use crate::compression_frame_manifest::CompressionFrameSlice;
use crate::file_format::indexed_frame::block_page::{self, PageIdentity};
let identity = PageIdentity {
archive: crate::LockboxId::from_bytes([71; 16]),
page_id: 41,
sequence: 43,
mode,
};
let slices = (0..2)
.map(|index| CompressionFrameSlice {
path: LockboxPath::new(format!("/tree/file-{index}.bin")).unwrap(),
permissions: 0o640,
total_len: 128,
file_offset: 0,
compression_frame_offset: index * 128,
len: 128,
})
.collect::<Vec<_>>();
let input: Vec<_> = (0..256).map(|n| (n % 13) as u8).collect();
let (descriptor, page) =
block_page::encode(identity, 31, &input, slices.clone(), &[53; 32]).unwrap();
let reference = std::sync::Arc::new(crate::file_chunk::BlockFrameReference {
descriptor,
sequence: identity.sequence,
});
let entries = slices
.into_iter()
.map(|slice| {
let descriptor = &reference.descriptor;
TocEntry {
path: slice.path.clone(),
len: slice.len,
record_offset: 4096,
record_len: page.len() as u64,
record_object_id: identity.page_id,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: slice.permissions,
chunks: vec![FileChunk {
block_frame: Some(reference.clone()),
stored_path: slice.path,
file_offset: 0,
len: slice.len,
compression_frame_offset: slice.compression_frame_offset,
compression_frame_len: descriptor.logical_len,
compressed_len: descriptor.stored_len,
compression: descriptor.compression,
compression_frame_id: descriptor.frame_id,
compression_frame_digest: descriptor.index_commitment,
segments: vec![CompressionFrameSegment {
page_offset: 4096,
page_len: page.len() as u64,
object_id: identity.page_id,
segment_offset: 0,
segment_len: descriptor.stored_len,
}],
}],
}
})
.collect();
(entries, page)
}
#[test]
fn native_toc_leaves_share_block_commitments_and_read_real_pages_in_all_modes() {
use crate::creation_options::FormatMode;
use crate::file_format::indexed_frame::block_page::{PageIdentity, Reader};
use crate::{Compression, EncryptionMode, LockboxFormatOptions, SigningMode, SizePadding};
for encryption in [EncryptionMode::None, EncryptionMode::ChaCha20Poly1305] {
for signing in [SigningMode::None, SigningMode::Owner] {
for compression in [Compression::None, Compression::default()] {
for size_padding in [SizePadding::Default, SizePadding::None] {
let mode = FormatMode::new(LockboxFormatOptions {
encryption,
signing,
compression,
size_padding,
});
let (mut entries, page) = native_fixture(mode);
let mut legacy = entries[0].clone();
legacy.path = LockboxPath::new("/legacy.bin").unwrap();
legacy.chunks = vec![shared_frame_chunk(0)];
let legacy_bytes =
crate::toc_btree::encode_toc_leaf(&[legacy.clone()]).unwrap();
assert_eq!(legacy_bytes[0], 1);
let wire = entries[0].chunks[0]
.block_frame
.as_ref()
.unwrap()
.descriptor
.encode()
.unwrap();
entries.insert(0, legacy);
let encoder = TocEncoder::new(&entries);
assert_eq!(encoder.version(), 2);
let leaf = crate::toc_btree::encode_toc_leaf(&entries).unwrap();
assert_eq!(leaf[0], 2);
assert_eq!(leaf.len(), 2 + encoder.encoded_len());
assert_eq!(
leaf.windows(wire.len())
.filter(|window| *window == wire)
.count(),
1
);
let mut estimator = TocEntriesLenEstimator::new();
for (index, entry) in entries.iter().enumerate() {
estimator.push(entry);
assert_eq!(
estimator.encoded_len(),
TocEncoder::new(&entries[..=index]).encode().len()
);
}
estimator.clear();
assert_eq!(
estimator.encoded_len(),
TocEncoder::new(std::iter::empty()).encode().len()
);
let crate::toc_btree::TocNode::Leaf(decoded) =
crate::toc_btree::decode_toc_node(&leaf).unwrap()
else {
panic!("leaf");
};
assert!(decoded[0].chunks[0].block_frame.is_none());
assert!(std::sync::Arc::ptr_eq(
decoded[1].chunks[0].block_frame.as_ref().unwrap(),
decoded[2].chunks[0].block_frame.as_ref().unwrap()
));
assert!(TocDecoder::new(&leaf[2..]).decode().is_err());
let mut bytes = vec![0; 4096];
bytes.extend_from_slice(&page);
let storage = crate::storage::StorageBackend::memory(bytes);
for entry in &decoded[1..] {
let chunk = &entry.chunks[0];
let reference = chunk.block_frame.as_ref().unwrap();
let segment = &chunk.segments[0];
let identity = PageIdentity {
archive: crate::LockboxId::from_bytes([71; 16]),
mode,
page_id: segment.object_id,
sequence: reference.sequence,
};
let reader = Reader::open(
&storage,
segment.page_offset,
identity,
&reference.descriptor,
segment.page_len as usize,
&[53; 32],
)
.unwrap();
let start = chunk.compression_frame_offset;
let expected: Vec<_> =
(start..start + chunk.len).map(|n| (n % 13) as u8).collect();
assert_eq!(reader.read(start..start + chunk.len).unwrap(), expected);
let mut wrong = identity;
wrong.sequence += 1;
assert!(Reader::open(
&storage,
segment.page_offset,
wrong,
&reference.descriptor,
segment.page_len as usize,
&[53; 32]
)
.is_err());
}
assert_eq!(
crate::toc_btree::encode_toc_leaf(&decoded[..1]).unwrap(),
legacy_bytes
);
}
}
}
}
}
#[test]
fn native_toc_rejects_ambiguous_layouts_and_inconsistent_block_references() {
use crate::{Compression, EncryptionMode, LockboxFormatOptions, SigningMode, SizePadding};
let mode = crate::creation_options::FormatMode::new(LockboxFormatOptions {
encryption: EncryptionMode::None,
signing: SigningMode::None,
compression: Compression::None,
size_padding: SizePadding::Default,
});
let (entries, _) = native_fixture(mode);
let mut same_fields_legacy = entries[0].clone();
same_fields_legacy.chunks[0].block_frame = None;
let distinct = TocEncoder::new([&entries[0], &same_fields_legacy]);
assert_eq!(
distinct.descriptors.len(),
2,
"layout semantics are part of descriptor identity"
);
let leaf = crate::toc_btree::encode_toc_leaf(&entries).unwrap();
let start = leaf
.windows(8)
.position(|window| window == b"LBXBF001")
.unwrap();
for offset in [start - 1, start + 11, start + 32, start + 96] {
let mut bad = leaf.clone();
bad[offset] ^= 2;
assert!(crate::toc_btree::decode_toc_node(&bad).is_err());
}
for version in [0, 3, 255] {
let mut bad = leaf.clone();
bad[0] = version;
assert!(crate::toc_btree::decode_toc_node(&bad).is_err());
}
for length in start..start + 128 {
assert!(crate::toc_btree::decode_toc_node(&leaf[..length]).is_err());
}
for scenario in 0..5 {
let mut bad = entries.clone();
let chunk = &mut bad[0].chunks[0];
match scenario {
0 => chunk.compression_frame_id += 1,
1 => chunk.compression_frame_digest[0] ^= 1,
2 => chunk.segments[0].page_offset = u64::MAX,
3 => chunk.segments[0].page_len = 1,
4 => chunk.segments.push(chunk.segments[0].clone()),
_ => unreachable!(),
}
let bytes = crate::toc_btree::encode_toc_leaf(&bad).unwrap();
assert!(crate::toc_btree::decode_toc_node(&bytes).is_err());
}
}
#[test]
fn decoded_toc_rejects_tampered_host_paths() {
let mut toc_entries = BTreeMap::new();
let invalid_path = LockboxPath::from_unchecked_for_test("/C:/Users/target.txt");
toc_entries.insert(
invalid_path.clone(),
TocEntry {
path: invalid_path,
len: 1,
record_offset: 64,
record_len: 64,
record_object_id: 1,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: DEFAULT_FILE_PERMISSIONS,
chunks: Vec::new(),
},
);
let payload = encode_toc(&toc_entries);
assert!(matches!(decode_toc(&payload), Err(Error::InvalidPath(_))));
}
#[test]
fn decoded_toc_rejects_impossible_entry_count_before_allocating() {
let payload = u64::MAX.to_le_bytes();
assert!(matches!(
decode_toc_entries(&payload),
Err(Error::CorruptRecord)
));
}
#[test]
fn decoded_toc_rejects_symlink_without_object_reference() {
let payload = encoded_symlink_entry("/links/current", 0, 0, 0);
assert!(matches!(
decode_toc_entries(&payload),
Err(Error::CorruptRecord)
));
}
#[test]
fn toc_entries_round_trip_front_coded_paths_with_restarts() {
let entries = (0..260)
.map(|i| TocEntry {
path: LockboxPath::new(format!("/docs/chapter-{i:03}/index.txt")).unwrap(),
len: 25_600,
record_offset: 96 + i * 1024,
record_len: 1024,
record_object_id: i + 1,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: DEFAULT_FILE_PERMISSIONS,
chunks: Vec::new(),
})
.collect::<Vec<_>>();
let payload = encode_toc_entries(entries.iter());
assert_eq!(payload.len(), encoded_toc_entries_len(&entries));
let decoded = decode_toc_entries(&payload).unwrap();
assert_eq!(decoded.len(), entries.len());
for (decoded, expected) in decoded.iter().zip(entries.iter()) {
assert_eq!(decoded.path, expected.path);
assert_eq!(decoded.len, expected.len);
assert_eq!(decoded.record_offset, expected.record_offset);
assert_eq!(decoded.record_len, expected.record_len);
assert_eq!(decoded.record_object_id, expected.record_object_id);
}
}
#[test]
fn front_coding_handles_unicode_boundaries() {
let entries = [
TocEntry {
path: LockboxPath::new("/docs/cafe\u{301}/a.txt").unwrap(),
len: 1,
record_offset: 64,
record_len: 64,
record_object_id: 1,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: DEFAULT_FILE_PERMISSIONS,
chunks: Vec::new(),
},
TocEntry {
path: LockboxPath::new("/docs/cafe\u{301}/b.txt").unwrap(),
len: 1,
record_offset: 64,
record_len: 64,
record_object_id: 1,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: DEFAULT_FILE_PERMISSIONS,
chunks: Vec::new(),
},
];
let payload = encode_toc_entries(entries.iter());
let decoded = decode_toc_entries(&payload).unwrap();
assert_eq!(decoded[0].path, entries[0].path);
assert_eq!(decoded[1].path, entries[1].path);
}
#[test]
fn toc_entries_share_frame_descriptors_across_chunks() {
let entries = (0..4)
.map(|i| TocEntry {
path: LockboxPath::new(format!("/tree/file-{i}.bin")).unwrap(),
len: 128,
record_offset: 4096,
record_len: 4096,
record_object_id: 10,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: DEFAULT_FILE_PERMISSIONS,
chunks: vec![shared_frame_chunk(i)],
})
.collect::<Vec<_>>();
let payload = encode_toc_entries(entries.iter());
assert_eq!(payload.len(), encoded_toc_entries_len(&entries));
let decoded = decode_toc_entries(&payload).unwrap();
assert_eq!(decoded.len(), entries.len());
for (decoded, expected) in decoded.iter().zip(entries.iter()) {
assert_eq!(decoded.path, expected.path);
assert_eq!(decoded.len, expected.len);
assert_eq!(decoded.chunks, expected.chunks);
}
assert!(
payload.len()
< entries
.iter()
.map(|entry| 64 + entry.path.len())
.sum::<usize>()
);
}
#[test]
fn toc_decode_rejects_invalid_frame_descriptor_index() {
let entry = TocEntry {
path: LockboxPath::new("/tree/file.bin").unwrap(),
len: 128,
record_offset: 4096,
record_len: 4096,
record_object_id: 10,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: DEFAULT_FILE_PERMISSIONS,
chunks: vec![shared_frame_chunk(0)],
};
let mut payload = encode_toc_entries([&entry]);
let last = payload.last_mut().unwrap();
*last = last.saturating_add(1);
assert!(matches!(
decode_toc_entries(&payload),
Err(Error::CorruptRecord)
));
}
#[test]
fn toc_decode_rejects_compressed_len_larger_than_frame_len() {
let mut entry = TocEntry {
path: LockboxPath::new("/tree/file.bin").unwrap(),
len: 128,
record_offset: 4096,
record_len: 4096,
record_object_id: 10,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: DEFAULT_FILE_PERMISSIONS,
chunks: vec![shared_frame_chunk(0)],
};
entry.chunks[0].compression_frame_len = 4;
entry.chunks[0].compressed_len = 5;
assert!(matches!(
decode_toc_entries(&encode_toc_entries([&entry])),
Err(Error::CorruptRecord)
));
}
#[test]
fn toc_decode_rejects_segment_outside_compressed_frame() {
let mut entry = TocEntry {
path: LockboxPath::new("/tree/file.bin").unwrap(),
len: 128,
record_offset: 4096,
record_len: 4096,
record_object_id: 10,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::File,
permissions: DEFAULT_FILE_PERMISSIONS,
chunks: vec![shared_frame_chunk(0)],
};
entry.chunks[0].segments[0].segment_offset = 41;
entry.chunks[0].segments[0].segment_len = 2;
assert!(matches!(
decode_toc_entries(&encode_toc_entries([&entry])),
Err(Error::CorruptRecord)
));
}
fn encoded_symlink_entry(
path: &str,
record_offset: u64,
record_len: u64,
record_object_id: u64,
) -> Vec<u8> {
encode_toc_entries([&TocEntry {
path: LockboxPath::new(path).unwrap(),
len: 0,
record_offset,
record_len,
record_object_id,
record_digest: [0; 32],
deleted: false,
node_kind: NodeKind::Symlink,
permissions: DEFAULT_SYMLINK_PERMISSIONS,
chunks: Vec::new(),
}])
}
fn shared_frame_chunk(index: u64) -> FileChunk {
FileChunk {
#[cfg(test)]
block_frame: None,
stored_path: LockboxPath::new(format!("/tree/file-{index}.bin")).unwrap(),
file_offset: 0,
len: 128,
compression_frame_offset: index * 128,
compression_frame_len: 512,
compressed_len: 42,
compression: 1,
compression_frame_id: 7,
compression_frame_digest: [9; 32],
segments: vec![CompressionFrameSegment {
page_offset: 4096,
page_len: 4096,
object_id: 10,
segment_offset: 0,
segment_len: 42,
}],
}
}
}