wombatkv_format/
lib.rs

1#![forbid(unsafe_code)]
2
3/// Returns crate identity for smoke tests.
4#[must_use]
5pub fn crate_id() -> &'static str {
6    "wombatkv-format"
7}
8
9const WAL_MAGIC: &[u8; 12] = b"WMBT_KV_WAL1";
10const WAL_HEADER_SIZE: usize = 24;
11const SEGMENT_FOOTER_MAGIC: &[u8; 12] = b"WMBT_KV_SEG1";
12const SEGMENT_FOOTER_SIZE: usize = 20;
13const SEGMENT_MAGIC: &[u8; 12] = b"WMBT_KV_SGV1";
14const SEGMENT_HEADER_SIZE: usize = 16;
15
16/// WAL record v1 used for append-only chunk payloads.
17#[derive(Clone, Debug, PartialEq, Eq)]
18pub struct WalRecord {
19    pub key: Vec<u8>,
20    pub meta: Vec<u8>,
21    pub payload: Vec<u8>,
22}
23
24/// Binary format parsing and encoding errors.
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub enum FormatError {
27    InvalidMagic,
28    UnexpectedEof,
29    ChecksumMismatch,
30    FieldTooLarge,
31}
32
33/// Encodes a single `WalRecord` using `WMBT_KV_WAL1` layout.
34pub fn encode_wal_record(record: &WalRecord) -> Result<Vec<u8>, FormatError> {
35    let key_len = u16::try_from(record.key.len()).map_err(|_| FormatError::FieldTooLarge)?;
36    let meta_len = u16::try_from(record.meta.len()).map_err(|_| FormatError::FieldTooLarge)?;
37    let payload_len =
38        u32::try_from(record.payload.len()).map_err(|_| FormatError::FieldTooLarge)?;
39
40    let mut body = Vec::with_capacity(
41        usize::from(key_len) + usize::from(meta_len) + usize::try_from(payload_len).unwrap_or(0),
42    );
43    body.extend_from_slice(&record.key);
44    body.extend_from_slice(&record.meta);
45    body.extend_from_slice(&record.payload);
46
47    let checksum = checksum32(&body);
48
49    let mut out = Vec::with_capacity(WAL_HEADER_SIZE + body.len());
50    out.extend_from_slice(WAL_MAGIC);
51    out.extend_from_slice(&key_len.to_le_bytes());
52    out.extend_from_slice(&meta_len.to_le_bytes());
53    out.extend_from_slice(&payload_len.to_le_bytes());
54    out.extend_from_slice(&checksum.to_le_bytes());
55    out.extend_from_slice(&body);
56    Ok(out)
57}
58
59/// Decodes a single `WalRecord` from binary bytes.
60pub fn decode_wal_record(data: &[u8]) -> Result<WalRecord, FormatError> {
61    if data.len() < WAL_HEADER_SIZE {
62        return Err(FormatError::UnexpectedEof);
63    }
64
65    if &data[..WAL_MAGIC.len()] != WAL_MAGIC {
66        return Err(FormatError::InvalidMagic);
67    }
68
69    let key_len = usize::from(u16::from_le_bytes([data[12], data[13]]));
70    let meta_len = usize::from(u16::from_le_bytes([data[14], data[15]]));
71    let payload_len_u32 = u32::from_le_bytes([data[16], data[17], data[18], data[19]]);
72    let payload_len = usize::try_from(payload_len_u32).map_err(|_| FormatError::FieldTooLarge)?;
73    let checksum = u32::from_le_bytes([data[20], data[21], data[22], data[23]]);
74
75    let body_len = key_len
76        .checked_add(meta_len)
77        .and_then(|x| x.checked_add(payload_len))
78        .ok_or(FormatError::FieldTooLarge)?;
79
80    let total_len = WAL_HEADER_SIZE.checked_add(body_len).ok_or(FormatError::FieldTooLarge)?;
81    if data.len() < total_len {
82        return Err(FormatError::UnexpectedEof);
83    }
84
85    let body = &data[WAL_HEADER_SIZE..total_len];
86    if checksum32(body) != checksum {
87        return Err(FormatError::ChecksumMismatch);
88    }
89
90    let key_end = key_len;
91    let meta_end = key_end + meta_len;
92    Ok(WalRecord {
93        key: body[..key_end].to_vec(),
94        meta: body[key_end..meta_end].to_vec(),
95        payload: body[meta_end..].to_vec(),
96    })
97}
98
99/// Lightweight deterministic checksum for v1 scaffolding tests.
100#[must_use]
101pub fn checksum32(bytes: &[u8]) -> u32 {
102    let mut state = 0x811c_9dc5_u32;
103    for byte in bytes {
104        state ^= u32::from(*byte);
105        state = state.wrapping_mul(16_777_619);
106    }
107    state
108}
109
110/// Segment footer v1 for validating index footer integrity.
111#[derive(Clone, Copy, Debug, PartialEq, Eq)]
112pub struct SegmentFooter {
113    pub index_len: u32,
114    pub index_checksum: u32,
115}
116
117/// Encodes a v1 segment footer.
118#[must_use]
119pub fn encode_segment_footer(footer: SegmentFooter) -> [u8; SEGMENT_FOOTER_SIZE] {
120    let mut out = [0_u8; SEGMENT_FOOTER_SIZE];
121    out[..12].copy_from_slice(SEGMENT_FOOTER_MAGIC);
122    out[12..16].copy_from_slice(&footer.index_len.to_le_bytes());
123    out[16..20].copy_from_slice(&footer.index_checksum.to_le_bytes());
124    out
125}
126
127/// Parses and validates a v1 segment footer and index payload.
128pub fn decode_segment_footer(
129    footer_bytes: &[u8],
130    index_bytes: &[u8],
131) -> Result<SegmentFooter, FormatError> {
132    if footer_bytes.len() < SEGMENT_FOOTER_SIZE {
133        return Err(FormatError::UnexpectedEof);
134    }
135
136    if &footer_bytes[..12] != SEGMENT_FOOTER_MAGIC {
137        return Err(FormatError::InvalidMagic);
138    }
139
140    let index_len = u32::from_le_bytes([
141        footer_bytes[12],
142        footer_bytes[13],
143        footer_bytes[14],
144        footer_bytes[15],
145    ]);
146    let index_checksum = u32::from_le_bytes([
147        footer_bytes[16],
148        footer_bytes[17],
149        footer_bytes[18],
150        footer_bytes[19],
151    ]);
152
153    if usize::try_from(index_len).map_err(|_| FormatError::FieldTooLarge)? != index_bytes.len() {
154        return Err(FormatError::UnexpectedEof);
155    }
156
157    if checksum32(index_bytes) != index_checksum {
158        return Err(FormatError::ChecksumMismatch);
159    }
160
161    Ok(SegmentFooter { index_len, index_checksum })
162}
163
164/// Segment index entry mapping key -> payload byte range.
165#[derive(Clone, Debug, PartialEq, Eq)]
166pub struct SegmentIndexEntry {
167    pub key: Vec<u8>,
168    pub payload_offset: u32,
169    pub payload_len: u32,
170}
171
172/// Encode compact segment object with sparse index + footer.
173pub fn encode_segment_v1(blocks: &[(Vec<u8>, Vec<u8>)]) -> Result<Vec<u8>, FormatError> {
174    let block_count = u32::try_from(blocks.len()).map_err(|_| FormatError::FieldTooLarge)?;
175    let mut out = Vec::new();
176    out.extend_from_slice(SEGMENT_MAGIC);
177    out.extend_from_slice(&block_count.to_le_bytes());
178
179    let mut index_entries = Vec::with_capacity(blocks.len());
180    for (key, payload) in blocks {
181        let key_len = u16::try_from(key.len()).map_err(|_| FormatError::FieldTooLarge)?;
182        let payload_len = u32::try_from(payload.len()).map_err(|_| FormatError::FieldTooLarge)?;
183        let payload_offset = u32::try_from(out.len() + 2 + 4 + usize::from(key_len))
184            .map_err(|_| FormatError::FieldTooLarge)?;
185        out.extend_from_slice(&key_len.to_le_bytes());
186        out.extend_from_slice(&payload_len.to_le_bytes());
187        out.extend_from_slice(key);
188        out.extend_from_slice(payload);
189        index_entries.push(SegmentIndexEntry { key: key.clone(), payload_offset, payload_len });
190    }
191
192    let index_bytes = encode_segment_index(&index_entries)?;
193    let footer = encode_segment_footer(SegmentFooter {
194        index_len: u32::try_from(index_bytes.len()).map_err(|_| FormatError::FieldTooLarge)?,
195        index_checksum: checksum32(&index_bytes),
196    });
197    out.extend_from_slice(&index_bytes);
198    out.extend_from_slice(&footer);
199    Ok(out)
200}
201
202/// Decode segment index from a full segment object.
203pub fn decode_segment_index(segment: &[u8]) -> Result<Vec<SegmentIndexEntry>, FormatError> {
204    if segment.len() < SEGMENT_HEADER_SIZE + SEGMENT_FOOTER_SIZE {
205        return Err(FormatError::UnexpectedEof);
206    }
207    if &segment[..SEGMENT_MAGIC.len()] != SEGMENT_MAGIC {
208        return Err(FormatError::InvalidMagic);
209    }
210
211    let footer_start =
212        segment.len().checked_sub(SEGMENT_FOOTER_SIZE).ok_or(FormatError::UnexpectedEof)?;
213    let footer_bytes = &segment[footer_start..];
214    let index_len_u32 = u32::from_le_bytes([
215        footer_bytes[12],
216        footer_bytes[13],
217        footer_bytes[14],
218        footer_bytes[15],
219    ]);
220    let index_len = usize::try_from(index_len_u32).map_err(|_| FormatError::FieldTooLarge)?;
221    let index_start = footer_start.checked_sub(index_len).ok_or(FormatError::UnexpectedEof)?;
222    let index_bytes = &segment[index_start..footer_start];
223    let _ = decode_segment_footer(footer_bytes, index_bytes)?;
224    parse_segment_index(index_bytes)
225}
226
227fn encode_segment_index(entries: &[SegmentIndexEntry]) -> Result<Vec<u8>, FormatError> {
228    let mut out = Vec::new();
229    for entry in entries {
230        let key_len = u16::try_from(entry.key.len()).map_err(|_| FormatError::FieldTooLarge)?;
231        out.extend_from_slice(&key_len.to_le_bytes());
232        out.extend_from_slice(&entry.key);
233        out.extend_from_slice(&entry.payload_offset.to_le_bytes());
234        out.extend_from_slice(&entry.payload_len.to_le_bytes());
235    }
236    Ok(out)
237}
238
239fn parse_segment_index(index_bytes: &[u8]) -> Result<Vec<SegmentIndexEntry>, FormatError> {
240    let mut cursor = 0_usize;
241    let mut entries = Vec::new();
242    while cursor < index_bytes.len() {
243        if index_bytes.len().saturating_sub(cursor) < 2 {
244            return Err(FormatError::UnexpectedEof);
245        }
246        let key_len =
247            usize::from(u16::from_le_bytes([index_bytes[cursor], index_bytes[cursor + 1]]));
248        cursor = cursor.saturating_add(2);
249        if index_bytes.len().saturating_sub(cursor) < key_len + 8 {
250            return Err(FormatError::UnexpectedEof);
251        }
252        let key = index_bytes[cursor..cursor + key_len].to_vec();
253        cursor = cursor.saturating_add(key_len);
254        let payload_offset = u32::from_le_bytes([
255            index_bytes[cursor],
256            index_bytes[cursor + 1],
257            index_bytes[cursor + 2],
258            index_bytes[cursor + 3],
259        ]);
260        cursor = cursor.saturating_add(4);
261        let payload_len = u32::from_le_bytes([
262            index_bytes[cursor],
263            index_bytes[cursor + 1],
264            index_bytes[cursor + 2],
265            index_bytes[cursor + 3],
266        ]);
267        cursor = cursor.saturating_add(4);
268        entries.push(SegmentIndexEntry { key, payload_offset, payload_len });
269    }
270    Ok(entries)
271}
272
273#[cfg(test)]
274mod tests {
275    use super::{
276        checksum32, decode_segment_footer, decode_segment_index, decode_wal_record,
277        encode_segment_footer, encode_segment_v1, encode_wal_record, FormatError, SegmentFooter,
278        WalRecord,
279    };
280
281    #[test]
282    fn crate_id_is_stable() {
283        assert_eq!(super::crate_id(), "wombatkv-format");
284    }
285
286    #[test]
287    fn wal_record_round_trip_is_lossless() {
288        let record = WalRecord {
289            key: b"k/tenant/f/hash".to_vec(),
290            meta: b"{\"epoch\":1700}".to_vec(),
291            payload: vec![1, 2, 3, 4, 5, 6],
292        };
293        let encoded = encode_wal_record(&record).expect("encode");
294        let decoded = decode_wal_record(&encoded).expect("decode");
295        assert_eq!(decoded, record);
296    }
297
298    #[test]
299    fn wal_checksum_mismatch_is_rejected() {
300        let record = WalRecord {
301            key: b"key".to_vec(),
302            meta: b"meta".to_vec(),
303            payload: b"payload".to_vec(),
304        };
305        let mut encoded = encode_wal_record(&record).expect("encode");
306        let last = encoded.len() - 1;
307        encoded[last] ^= 0xFF;
308        assert_eq!(decode_wal_record(&encoded), Err(FormatError::ChecksumMismatch));
309    }
310
311    #[test]
312    fn wal_golden_vector_v1_stable() {
313        let record = WalRecord {
314            key: vec![0x6B],                 // "k"
315            meta: vec![0x6D],                // "m"
316            payload: vec![0x70, 0x71, 0x72], // "pqr"
317        };
318        let encoded = encode_wal_record(&record).expect("encode");
319        let expected = include_bytes!("../tests/golden/wal_v1_record.bin");
320        assert_eq!(encoded, expected);
321    }
322
323    #[test]
324    fn segment_footer_round_trip_with_checksum_validation() {
325        let index_bytes = b"index-v1".to_vec();
326        let index_len = u32::try_from(index_bytes.len()).expect("small test index");
327        let footer = SegmentFooter { index_len, index_checksum: checksum32(&index_bytes) };
328        let encoded = encode_segment_footer(footer);
329        let decoded = decode_segment_footer(&encoded, &index_bytes).expect("decode footer");
330        assert_eq!(decoded, footer);
331    }
332
333    #[test]
334    fn segment_footer_rejects_corrupt_index_checksum() {
335        let index_bytes = b"index-v1".to_vec();
336        let index_len = u32::try_from(index_bytes.len()).expect("small test index");
337        let footer = SegmentFooter { index_len, index_checksum: checksum32(&index_bytes) };
338        let encoded = encode_segment_footer(footer);
339        let mut corrupted_index = index_bytes.clone();
340        corrupted_index[0] ^= 0xFF;
341        assert_eq!(
342            decode_segment_footer(&encoded, &corrupted_index),
343            Err(FormatError::ChecksumMismatch)
344        );
345    }
346
347    #[test]
348    fn segment_footer_rejects_unknown_magic_for_backward_compat() {
349        let index_bytes = b"index-v1".to_vec();
350        let index_len = u32::try_from(index_bytes.len()).expect("small test index");
351        let mut encoded = encode_segment_footer(SegmentFooter {
352            index_len,
353            index_checksum: checksum32(&index_bytes),
354        });
355        encoded[0] = b'X';
356        assert_eq!(decode_segment_footer(&encoded, &index_bytes), Err(FormatError::InvalidMagic));
357    }
358
359    #[test]
360    fn segment_v1_encode_decode_index_round_trip() {
361        let segment = encode_segment_v1(&[
362            (b"a".to_vec(), b"payload-a".to_vec()),
363            (b"b".to_vec(), b"payload-b".to_vec()),
364            (b"c".to_vec(), b"payload-c".to_vec()),
365        ])
366        .expect("encode segment");
367        let index = decode_segment_index(&segment).expect("decode index");
368        assert_eq!(index.len(), 3);
369        assert_eq!(index[0].key, b"a".to_vec());
370        assert_eq!(index[1].key, b"b".to_vec());
371        assert_eq!(index[2].key, b"c".to_vec());
372    }
373}
wombatkv_format/lib.rs

wombatkv_format/
lib.rs
