reddb_file/
vector_value_codec.rs

1//! Large-value codec for vector/B-tree persisted payloads.
2//!
3//! This byte-slice codec knows nothing about pages, MVCC, or overflow chains.
4//! It stores either raw bytes or an LZ4 block prefixed with the original length.
5
6/// One-byte tag stored alongside the encoded payload.
7#[repr(u8)]
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum ValueFlag {
10    /// Payload bytes are the original input, byte-identical.
11    Raw = 0,
12    /// Payload bytes are an LZ4 block with a little-endian `u32` raw length.
13    Lz4 = 1,
14}
15
16impl ValueFlag {
17    /// Convert from the on-disk tag byte. Unknown tags are rejected.
18    pub fn from_byte(b: u8) -> Result<Self, ValueCodecError> {
19        match b {
20            0 => Ok(ValueFlag::Raw),
21            1 => Ok(ValueFlag::Lz4),
22            other => Err(ValueCodecError::UnknownFlag(other)),
23        }
24    }
25}
26
27#[derive(Debug, PartialEq, Eq)]
28pub enum ValueCodecError {
29    UnknownFlag(u8),
30    TruncatedHeader,
31    Lz4Decode(String),
32}
33
34impl std::fmt::Display for ValueCodecError {
35    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
36        match self {
37            ValueCodecError::UnknownFlag(b) => write!(f, "unknown value codec flag: {}", b),
38            ValueCodecError::TruncatedHeader => write!(
39                f,
40                "compressed payload truncated: need at least 4 bytes for length header"
41            ),
42            ValueCodecError::Lz4Decode(msg) => write!(f, "lz4 decode failed: {}", msg),
43        }
44    }
45}
46
47impl std::error::Error for ValueCodecError {}
48
49/// Encode `input` for storage. Returns the flag and stored bytes.
50///
51/// When LZ4 would not shrink the input including the 4-byte raw length header,
52/// the codec returns raw bytes. Equal size is treated as no win.
53pub fn encode(input: &[u8]) -> (ValueFlag, Vec<u8>) {
54    if input.is_empty() {
55        return (ValueFlag::Raw, Vec::new());
56    }
57
58    let compressed = lz4_flex::compress(input);
59    if compressed.len() + 4 < input.len() {
60        let mut out = Vec::with_capacity(compressed.len() + 4);
61        out.extend_from_slice(&(input.len() as u32).to_le_bytes());
62        out.extend_from_slice(&compressed);
63        (ValueFlag::Lz4, out)
64    } else {
65        (ValueFlag::Raw, input.to_vec())
66    }
67}
68
69/// Return the on-disk size [`encode`] would choose without returning the bytes.
70pub fn would_encode_to(input: &[u8]) -> usize {
71    if input.is_empty() {
72        return 0;
73    }
74    let compressed_len = lz4_flex::compress(input).len();
75    let lz4_total = compressed_len + 4;
76    if lz4_total < input.len() {
77        lz4_total
78    } else {
79        input.len()
80    }
81}
82
83/// Inspect the authoritative codec framing before reserving expansion space.
84pub fn decoded_length(flag: ValueFlag, bytes: &[u8]) -> Result<usize, ValueCodecError> {
85    match flag {
86        ValueFlag::Raw => Ok(bytes.len()),
87        ValueFlag::Lz4 => {
88            let header = bytes.get(..4).ok_or(ValueCodecError::TruncatedHeader)?;
89            let length =
90                u32::from_le_bytes(header.try_into().expect("invariant: four-byte header"));
91            Ok(usize::try_from(length)
92                .expect("invariant: supported address spaces are at least 32 bits"))
93        }
94    }
95}
96
97/// Decode a `(flag, bytes)` pair produced by [`encode`].
98pub fn decode(flag: ValueFlag, bytes: &[u8]) -> Result<Vec<u8>, ValueCodecError> {
99    match flag {
100        ValueFlag::Raw => Ok(bytes.to_vec()),
101        ValueFlag::Lz4 => {
102            let raw_len = decoded_length(flag, bytes)?;
103            lz4_flex::decompress(&bytes[4..], raw_len)
104                .map_err(|e| ValueCodecError::Lz4Decode(e.to_string()))
105        }
106    }
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112
113    #[test]
114    fn round_trip_compressible_text() {
115        let input = "the quick brown fox jumps over the lazy dog "
116            .repeat(64)
117            .into_bytes();
118        let (flag, bytes) = encode(&input);
119        assert_eq!(flag, ValueFlag::Lz4, "highly repetitive text must compress");
120        assert!(
121            bytes.len() < input.len(),
122            "stored size {} must be less than input {}",
123            bytes.len(),
124            input.len()
125        );
126        let decoded = decode(flag, &bytes).expect("decode");
127        assert_eq!(decoded, input);
128    }
129
130    #[test]
131    fn round_trip_incompressible_random() {
132        let mut state: u64 = 0x9E37_79B9_7F4A_7C15;
133        let input: Vec<u8> = (0..512)
134            .map(|_| {
135                state ^= state << 13;
136                state ^= state >> 7;
137                state ^= state << 17;
138                state as u8
139            })
140            .collect();
141        let (flag, bytes) = encode(&input);
142        assert_eq!(
143            flag,
144            ValueFlag::Raw,
145            "incompressible input must fall back to raw"
146        );
147        assert_eq!(bytes, input, "raw bytes must be byte-identical");
148        let decoded = decode(flag, &bytes).expect("decode");
149        assert_eq!(decoded, input);
150    }
151
152    #[test]
153    fn empty_input_round_trips_as_raw() {
154        let (flag, bytes) = encode(&[]);
155        assert_eq!(flag, ValueFlag::Raw);
156        assert!(bytes.is_empty());
157        let decoded = decode(flag, &bytes).expect("decode empty");
158        assert!(decoded.is_empty());
159    }
160
161    #[test]
162    fn exact_threshold_falls_back_to_raw() {
163        let input = vec![0x42u8];
164        let (flag, bytes) = encode(&input);
165        assert_eq!(flag, ValueFlag::Raw);
166        assert_eq!(bytes, input);
167    }
168
169    #[test]
170    fn flag_distinguishes_compressed_and_raw() {
171        let compressible = vec![b'a'; 256];
172        let (flag_c, _) = encode(&compressible);
173        let (flag_r, _) = encode(&[0xAB, 0xCD, 0xEF]);
174        assert_eq!(flag_c, ValueFlag::Lz4);
175        assert_eq!(flag_r, ValueFlag::Raw);
176        assert_ne!(flag_c, flag_r);
177    }
178
179    #[test]
180    fn flag_byte_round_trips() {
181        assert_eq!(ValueFlag::from_byte(0).unwrap(), ValueFlag::Raw);
182        assert_eq!(ValueFlag::from_byte(1).unwrap(), ValueFlag::Lz4);
183        assert_eq!(
184            ValueFlag::from_byte(255).unwrap_err(),
185            ValueCodecError::UnknownFlag(255)
186        );
187    }
188
189    #[test]
190    fn would_encode_to_matches_actual_encode() {
191        let compressible = vec![b'x'; 1024];
192        let (_, bytes) = encode(&compressible);
193        assert_eq!(would_encode_to(&compressible), bytes.len());
194
195        let mut state: u64 = 0xDEAD_BEEF_1234_5678;
196        let random: Vec<u8> = (0..256)
197            .map(|_| {
198                state ^= state << 13;
199                state ^= state >> 7;
200                state ^= state << 17;
201                state as u8
202            })
203            .collect();
204        let (_, bytes) = encode(&random);
205        assert_eq!(would_encode_to(&random), bytes.len());
206
207        assert_eq!(would_encode_to(&[]), 0);
208    }
209
210    #[test]
211    fn would_encode_to_decouples_from_spill_decision() {
212        let blob = vec![b'z'; 4096];
213        let projected = would_encode_to(&blob);
214        let fits_in_64 = projected <= 64;
215
216        let (flag, bytes) = encode(&blob);
217        assert_eq!(bytes.len(), projected);
218        assert_eq!(decode(flag, &bytes).unwrap(), blob);
219        assert!(fits_in_64);
220    }
221
222    #[test]
223    fn decode_rejects_unknown_flag_byte() {
224        assert!(matches!(
225            ValueFlag::from_byte(7),
226            Err(ValueCodecError::UnknownFlag(7))
227        ));
228    }
229
230    #[test]
231    fn decode_rejects_truncated_lz4_header() {
232        let err = decode(ValueFlag::Lz4, &[0x01, 0x02]).unwrap_err();
233        assert_eq!(err, ValueCodecError::TruncatedHeader);
234    }
235}
reddb_file/vector_value_codec.rs

reddb_file/
vector_value_codec.rs
