use super::{Error, Map, Range};
use alloc::vec::Vec;
use core::{alloc::Allocator, ops::Bound};
use sha2::{Digest, Sha256};
mod reader;
pub use reader::{Page, Reader};
#[cfg(test)]
mod tests;
pub const PAGE_BYTES: usize = 32 * 1024;
pub const PAGE_RECORDS: usize = 64;
pub const MANIFEST_BYTES: usize = 128;
const HEADER: usize = 88;
const PAGE_MAGIC: &[u8; 8] = b"ORDPG001";
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Manifest {
epoch: u64,
root: u64,
count: usize,
pages: usize,
first: [u8; 32],
}
impl Manifest {
pub fn decode(bytes: &[u8], epoch: u64, root: u64, limit: usize) -> Result<Self, Error> {
if bytes.len() != MANIFEST_BYTES
|| &bytes[..8] != b"ORDPAG01"
|| word(&bytes[8..16]) != 1
|| root == 0
|| word(&bytes[24..32]) != root
|| word(&bytes[48..56]) != PAGE_BYTES as u64
|| &bytes[88..96] != b"ORDPDONE"
|| Sha256::digest(&bytes[..96]).as_slice() != &bytes[96..]
{
return Err(Error::Checkpoint);
}
if word(&bytes[16..24]) != epoch {
return Err(Error::Epoch);
}
let count = usize::try_from(word(&bytes[32..40])).map_err(|_| Error::Limit)?;
let pages = usize::try_from(word(&bytes[40..48])).map_err(|_| Error::Limit)?;
if count > limit {
return Err(Error::Limit);
}
if pages > count
|| pages < count.div_ceil(PAGE_RECORDS)
|| (count == 0 && bytes[56..88] != [0; 32])
{
return Err(Error::Checkpoint);
}
Ok(Self {
epoch,
root,
count,
pages,
first: core::array::from_fn(|index| bytes[56 + index]),
})
}
#[must_use]
pub fn encode(&self) -> [u8; MANIFEST_BYTES] {
let mut bytes = [0; MANIFEST_BYTES];
bytes[..8].copy_from_slice(b"ORDPAG01");
for (index, value) in [
1,
self.epoch,
self.root,
self.count as u64,
self.pages as u64,
PAGE_BYTES as u64,
]
.into_iter()
.enumerate()
{
bytes[8 + index * 8..16 + index * 8].copy_from_slice(&value.to_le_bytes());
}
bytes[56..88].copy_from_slice(&self.first);
bytes[88..96].copy_from_slice(b"ORDPDONE");
let seal = Sha256::digest(&bytes[..96]);
bytes[96..].copy_from_slice(&seal);
bytes
}
#[must_use]
pub const fn len(&self) -> usize {
self.count
}
#[must_use]
pub const fn is_empty(&self) -> bool {
self.count == 0
}
#[must_use]
pub const fn page_count(&self) -> usize {
self.pages
}
#[must_use]
pub fn reader<const K: usize, const V: usize>(&self) -> Reader<K, V> {
Reader::new(self.clone())
}
}
#[derive(Debug, PartialEq, Eq)]
pub enum ExportError<E> {
Map(Error),
Sink(E),
}
impl<const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> Map<K, V, A, P> {
pub fn export_pages<E>(
&self,
epoch: u64,
root: u64,
mut sink: impl FnMut(usize, &[u8]) -> Result<(), E>,
) -> Result<Manifest, ExportError<E>> {
self.healthy().map_err(ExportError::Map)?;
if root == 0 {
return Err(ExportError::Map(Error::Checkpoint));
}
let mut pages = 0;
let (mut used, mut count) = (0, 0);
for (key, value) in Range::new(self, Bound::Unbounded, Bound::Unbounded).rev() {
let size = record_size(key.as_slice(), value.as_slice()).map_err(ExportError::Map)?;
if count == 0 || count == PAGE_RECORDS || used + size > PAGE_BYTES - HEADER {
pages += 1;
(used, count) = (0, 0);
}
used += size;
count += 1;
}
let mut manifest = Manifest {
epoch,
root,
count: self.image.len,
pages,
first: [0; 32],
};
if pages == 0 {
return Ok(manifest);
}
let mut page = Vec::new();
page.try_reserve_exact(PAGE_BYTES)
.map_err(|_| ExportError::Map(Error::Allocation))?;
page.resize(PAGE_BYTES, 0);
let mut records = Range::new(self, Bound::Unbounded, Bound::Unbounded)
.rev()
.peekable();
for index in (0..pages).rev() {
page.fill(0);
let (mut start, mut count) = (PAGE_BYTES, 0);
while let Some(&(key, value)) = records.peek() {
let (key, value) = (key.as_slice(), value.as_slice());
let size = 8 + key.len() + value.len();
if count == PAGE_RECORDS || size > start - HEADER {
break;
}
start -= size;
page[start..start + 4].copy_from_slice(&(key.len() as u32).to_le_bytes());
page[start + 4..start + 8].copy_from_slice(&(value.len() as u32).to_le_bytes());
page[start + 8..start + 8 + key.len()].copy_from_slice(key);
page[start + 8 + key.len()..start + size].copy_from_slice(value);
records.next();
count += 1;
}
let used = PAGE_BYTES - start;
page.copy_within(start..PAGE_BYTES, HEADER);
page[HEADER + used..].fill(0);
page[..8].copy_from_slice(PAGE_MAGIC);
for (field, value) in [
epoch,
root,
index as u64,
count as u64,
self.image.len as u64,
]
.into_iter()
.enumerate()
{
page[8 + field * 8..16 + field * 8].copy_from_slice(&value.to_le_bytes());
}
page[48..80].copy_from_slice(&manifest.first);
page[80..88].copy_from_slice(&(used as u64).to_le_bytes());
manifest.first = page_digest(&page);
sink(index, &page).map_err(ExportError::Sink)?;
}
Ok(manifest)
}
}
fn record_size(key: &[u8], value: &[u8]) -> Result<usize, Error> {
let size = key
.len()
.checked_add(value.len())
.and_then(|n| n.checked_add(8))
.ok_or(Error::Limit)?;
if size > PAGE_BYTES - HEADER {
return Err(Error::Limit);
}
Ok(size)
}
fn page_digest(bytes: &[u8]) -> [u8; 32] {
let mut digest = Sha256::new();
digest.update(b"ORDPGH01");
digest.update(bytes);
digest.finalize().into()
}
fn word(bytes: &[u8]) -> u64 {
u64::from_le_bytes(bytes.try_into().unwrap())
}