kevy_compress/lib.rs
1//! `kevy-compress` — corpus-aware LZ for the tiered value log.
2//!
3//! # Why this exists
4//!
5//! PostgreSQL compresses **per datum** and skips values under ~2 KB
6//! entirely; a 400 B row's redundancy lives *across* rows (field
7//! names, enum members, shared prefixes) where a per-datum window
8//! cannot see it. kevy's vlog is a **corpus** — a contiguous sample of
9//! one keyspace — so a dictionary trained on the file reaches the
10//! redundancy PG structurally cannot (RFC
11//! the premise was measured before a line was written: on identical
12//! 400 B values a shared dictionary encodes N values as O(dictionary)
13//! + N × ~9 B while per-datum pays 89 B each, forever).
14//!
15//! # The three measured constraints this crate is shaped by
16//!
17//! - **Decode ≥ ~1 GB/s**: at 100 MiB/s a 4 KiB cold read spends
18//! 38 % of its p99 budget in decode; a token + wildcopy design
19//! measured ~8 GB/s in its naive form. Speed is a requirement of the
20//! design, not a later optimisation.
21//!
22//! **Met through [`Dict`], missed through [`decode`].** The cause was
23//! never the token grammar: the dictionary is per-file state and every
24//! entry point took it as a per-call argument. `examples/decode_budget`
25//! measures held-out values against a trained dictionary — the shape
26//! `kevy-vlog` produces — and reports, per value:
27//!
28//! | path | `decode` | [`Dict::decode`] |
29//! |---|---|---|
30//! | fast | 0.543 GB/s | **2.079 GB/s** |
31//! | compaction | 0.045 GB/s | **1.265 GB/s** |
32//!
33//! `kevy-vlog` holds one `Dict` per file, so a cold read takes the
34//! right column. `decode` stays for callers with nothing to hold it in,
35//! and is honest about what it costs.
36//!
37//! The earlier "order of magnitude above" reading came from
38//! `examples/k1_sanity`, which trains the dictionary on the same value
39//! it compresses; that decodes one long match out of the dictionary at
40//! a 41x ratio, which no stored value ever does.
41//!
42//! The write side had the same shape and is fixed the same way:
43//! seeding the match table walks every dictionary position, so encode
44//! time was flat in input size — an 8-byte value cost more than a
45//! 6 KiB one, because almost none of the work was about the value.
46//!
47//! | path | `encode` | [`Dict::encode`] |
48//! |---|---|---|
49//! | fast | 35.2 us/value | **0.47 us** |
50//! | compaction | 38.4 us/value | **2.86 us** |
51//!
52//! The frames are identical either way — `examples/decode_budget`
53//! asserts that before it reports a number, because a speedup that
54//! changed what was written would be a different change.
55//! - **Never expand**: per-datum zlib on random 400 B values
56//! *grows* them by 11 B. The raw-frame fallback is therefore part of
57//! the format, not an optimisation.
58//! - **The dictionary carries the corpus claim**: match-finding refinements move
59//! little; dictionary construction decides how much of the corpus
60//! ceiling is captured. **Measured, this is the wrong way round on the
61//! templated corpus**: a brute-force oracle over the same grammar
62//! reaches 181.8 B/value where the shipped single-probe finder reaches
63//! 220.7 — 17.6 % of frame bytes — and `HT_BITS = 12` alone leaves
64//! 43.5 % of the dictionary's distinct 4-grams unreachable, so a
65//! better `train` cannot cash in what it produces. The `train` entry point is deliberately a
66//! replaceable policy behind a stable signature.
67//!
68//! # Format
69//!
70//! A frame is `[tag: u8][orig_len: LEB128][payload]`.
71//!
72//! - `TAG_RAW`: payload is the input verbatim. Chosen whenever LZ
73//! would not save a byte — never-expanding is structural, not tuned.
74//! - `TAG_LZ` / `TAG_LZ_DICT`: LZ4-style token stream (4-bit literal
75//! and match-length nibbles with 255-continuation bytes, 16-bit
76//! little-endian offsets, minimum match 4). With `TAG_LZ_DICT`
77//! offsets may reach back past the start of output into the
78//! caller-supplied dictionary, which is virtually prepended history.
79//!
80//! The dictionary is **a parameter, never a dependency**: this crate
81//! knows only bytes. Lifecycle (one dictionary per vlog file, seeded
82//! across rotation, disposable with the file) belongs to the caller.
83//!
84//! ```
85//! use kevy_compress::{encode, encode_high, decode, train};
86//!
87//! // No dictionary: an empty one is the ordinary LZ path.
88//! let value = b"user:1 name=ada user:1 name=ada user:1 name=ada";
89//! let frame = encode(b"", value);
90//! assert_eq!(decode(b"", &frame).unwrap(), value);
91//! assert!(frame.len() < value.len(), "repetition should compress");
92//!
93//! // Corpus-aware: a dictionary trained on samples that share a shape
94//! // lets a SHORT value reference bytes it never carries itself.
95//! let samples: Vec<&[u8]> = vec![
96//! b"{\"user\":1,\"role\":\"admin\"}",
97//! b"{\"user\":2,\"role\":\"admin\"}",
98//! b"{\"user\":3,\"role\":\"guest\"}",
99//! ];
100//! let dict = train(&samples, 4096);
101//! let one = b"{\"user\":9,\"role\":\"admin\"}";
102//! assert_eq!(decode(&dict, &encode(&dict, one)).unwrap(), one);
103//!
104//! // `encode_high` spends more time for a smaller frame; both decode
105//! // with the same dictionary.
106//! assert_eq!(decode(b"", &encode_high(b"", value)).unwrap(), value);
107//!
108//! // A frame decoded against the WRONG dictionary is refused or wrong —
109//! // never a silent half-value. Truncation is refused outright.
110//! assert!(decode(b"", &frame[..frame.len() / 2]).is_err());
111//! ```
112
113#![cfg_attr(not(test), no_std)]
114#![forbid(unsafe_code)]
115#![warn(missing_docs)]
116
117extern crate alloc;
118
119use alloc::vec::Vec;
120
121mod decode;
122mod dict;
123mod encode;
124mod huff;
125mod tag;
126
127pub use dict::Dict;
128pub use tag::{MAX_OFFSET, TAG_LZ, TAG_LZ_DICT, TAG_LZH, TAG_LZH_DICT, TAG_RAW};
129
130/// Magic prefix of a structured dictionary: `[magic][128 B code
131/// lengths][content]`. The embedded table is the file-scoped entropy
132/// model (one header per FILE instead of per record — the reason the
133/// per-record Huffman header could not amortize at 400 B). A
134/// dictionary without the magic is plain content bytes; the vlog is
135/// disposable, so this format carries no compatibility burden.
136const DICT_MAGIC: &[u8; 5] = b"KVCD1";
137
138/// Split a dictionary into its optional entropy table and its content
139/// (the match-history bytes).
140fn parse_dict(dict: &[u8]) -> (Option<[u8; 256]>, &[u8]) {
141 let Some(rest) = dict.strip_prefix(DICT_MAGIC.as_slice()) else {
142 return (None, dict);
143 };
144 let Some((hdr, content)) = rest.split_at_checked(huff::HEADER_LEN) else {
145 return (None, dict);
146 };
147 let mut lens = [0u8; 256];
148 for (i, &b) in hdr.iter().enumerate() {
149 lens[i * 2] = b & 0x0f;
150 lens[i * 2 + 1] = b >> 4;
151 }
152 if huff::validate_lens(&lens, 1).is_err() {
153 return (None, dict);
154 }
155 (Some(lens), content)
156}
157
158/// Decode failure: the frame does not decode to exactly what its
159/// header promises. Corrupt and truncated frames land here — they are
160/// rejected, never mis-decoded.
161/// # Examples
162///
163/// ```
164/// use kevy_compress::decode;
165///
166/// // A frame the decoder cannot trust is refused, not half-decoded.
167/// assert!(decode(b"", b"\x01truncated").is_err());
168/// ```
169#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
170pub struct DecodeError;
171
172impl core::fmt::Display for DecodeError {
173 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
174 f.write_str("kevy-compress: corrupt or truncated frame")
175 }
176}
177
178impl core::error::Error for DecodeError {}
179
180/// Close a frame, or throw it away and store the input verbatim.
181///
182/// Never-expanding is a return value here, not a hope: an encoder that
183/// could not beat the input hands back a `TAG_RAW` frame rather than a
184/// larger one. Shared by all four entry points so the fallback cannot
185/// drift between them.
186fn finish_or_raw(frame: &mut Vec<u8>, tag: u8, ok: bool, input: &[u8]) {
187 if ok {
188 finish_header(frame, tag, input.len());
189 } else {
190 frame.clear();
191 push_header(frame, TAG_RAW, input.len());
192 frame.extend_from_slice(input);
193 }
194}
195
196/// Encode `input` into a frame, using `dict` as shared history when it
197/// pays. The result is **never longer than `input` plus the frame
198/// header**: when LZ cannot save a byte — incompressible input,
199/// adversarial input, anything — the frame stores the bytes raw.
200/// # Examples
201///
202/// Encode and decode are inverses under the same dictionary. An empty
203/// dictionary is valid and means "no shared prefix knowledge".
204///
205/// ```
206/// let input = b"the quick brown fox jumps over the quick brown dog";
207/// let frame = kevy_compress::encode(&[], input);
208/// assert_eq!(kevy_compress::decode(&[], &frame).unwrap(), input);
209/// ```
210///
211/// A frame decoded under a different dictionary than it was built with is
212/// refused rather than silently producing other bytes.
213///
214/// ```
215/// let frame = kevy_compress::encode(b"shared prefix", b"shared prefix and more");
216/// assert_eq!(kevy_compress::decode(b"shared prefix", &frame).unwrap(),
217/// b"shared prefix and more");
218/// ```
219#[must_use]
220pub fn encode(dict: &[u8], input: &[u8]) -> Vec<u8> {
221 let (_, content) = parse_dict(dict);
222 let mut frame = Vec::with_capacity(input.len() + MAX_HEADER);
223 let (tag, ok) = if input.len() >= encode::MIN_INPUT {
224 encode::try_lz(content, None, input, &mut frame)
225 } else {
226 (TAG_RAW, false)
227 };
228 finish_or_raw(&mut frame, tag, ok, input);
229 frame
230}
231
232/// Encode at the compaction level: same match finder, literals pulled
233/// into one Huffman-coded block (zstd's shape). Strictly
234/// smallest-wins: the result is the smaller of high / fast / raw, so
235/// never-expanding holds here exactly as for [`encode`]. Costs roughly a
236/// second serialization pass at encode time — which is the point: a
237/// value re-encoded by compaction has proven cold (RFC §3).
238/// # Examples
239///
240/// ```
241/// use kevy_compress::{encode, encode_high, decode};
242///
243/// let v = b"ababababababababababababababababab";
244/// // Same frame format, more search: never larger than `encode`'s.
245/// assert!(encode_high(b"", v).len() <= encode(b"", v).len());
246/// assert_eq!(decode(b"", &encode_high(b"", v)).unwrap(), v);
247/// ```
248#[must_use]
249pub fn encode_high(dict: &[u8], input: &[u8]) -> Vec<u8> {
250 let (lens, content) = parse_dict(dict);
251 let mut frame = Vec::with_capacity(input.len() + MAX_HEADER);
252 let (tag, ok) = if input.len() >= encode::MIN_INPUT {
253 encode::try_high(content, lens.as_ref(), None, input, &mut frame)
254 } else {
255 (TAG_RAW, false)
256 };
257 finish_or_raw(&mut frame, tag, ok, input);
258 frame
259}
260
261/// Decode one frame produced by [`encode`]. `dict` must be the same
262/// bytes the encoder was given — the tag records whether the frame
263/// depends on it at all.
264/// # Examples
265///
266/// ```
267/// use kevy_compress::{encode, decode};
268///
269/// let v = b"the same dictionary that encoded it";
270/// assert_eq!(decode(b"", &encode(b"", v)).unwrap(), v);
271///
272/// // Bytes that are not a frame are refused rather than guessed at.
273/// assert!(decode(b"", b"").is_err());
274/// assert!(decode(b"", b"\xff\xff\xff").is_err());
275/// ```
276pub fn decode(dict: &[u8], frame: &[u8]) -> Result<Vec<u8>, DecodeError> {
277 // The tag first. `parse_dict` used to run above this line, so a
278 // `TAG_RAW` or `TAG_LZ` frame — which never reads the dictionary —
279 // still paid 128 header bytes unpacked into a 256-entry array and a
280 // Kraft sum over all of it. Measured at +0.138 us, which is 111% of
281 // a 400 B decode and 79% of a 64 B one.
282 let (&tag, rest) = frame.split_first().ok_or(DecodeError)?;
283 let (orig_len, payload) = read_varint(rest)?;
284 if matches!(tag, TAG_RAW | TAG_LZ) {
285 return match tag {
286 TAG_RAW if payload.len() == orig_len => Ok(payload.to_vec()),
287 TAG_RAW => Err(DecodeError),
288 _ => decode::lz(&[], payload, orig_len),
289 };
290 }
291 let (lens, content) = parse_dict(dict);
292 match tag {
293 TAG_LZ_DICT => {
294 if content.is_empty() {
295 return Err(DecodeError);
296 }
297 decode::lz(content, payload, orig_len)
298 }
299 TAG_LZH => match decode::lz_high(&[], None, None, payload, orig_len) {
300 // Compat: the 5.0.0 encoder could emit a shared-table
301 // (flag 2) literal block under TAG_LZH — the tag missed
302 // the dict dependency (fuzz crash 6b733e74; fixed in
303 // try_high). Those on-disk frames need the dict's lens
304 // table: retry with it before declaring corrupt. The
305 // record's CRC already vouched for the bytes.
306 Err(DecodeError) if lens.is_some() => {
307 decode::lz_high(&[], lens.as_ref(), None, payload, orig_len)
308 }
309 r => r,
310 },
311 TAG_LZH_DICT => {
312 if content.is_empty() {
313 return Err(DecodeError);
314 }
315 decode::lz_high(content, lens.as_ref(), None, payload, orig_len)
316 }
317 _ => Err(DecodeError),
318 }
319}
320
321/// Build a dictionary from sample values under a byte budget.
322///
323/// v1 policy: evenly-strided whole samples until the budget fills —
324/// the simplest construction that makes identical and near-identical
325/// corpora hit the "O(dictionary) + N × small" shape. The premise
326/// measurement says construction (not match-finding) is where corpus
327/// capture is won, so expect this policy to be replaced behind the
328/// same signature; its output is bytes, and bytes carry no versioning
329/// burden (the dictionary dies with its vlog file).
330/// # Examples
331///
332/// ```
333/// use kevy_compress::{encode, decode, train};
334///
335/// // Samples that share a shape leave that shape in the dictionary, so
336/// // a value carrying only the varying part still round-trips.
337/// let samples: Vec<&[u8]> = vec![
338/// b"GET /api/v1/users/1 HTTP/1.1",
339/// b"GET /api/v1/users/2 HTTP/1.1",
340/// b"GET /api/v1/users/3 HTTP/1.1",
341/// ];
342/// let dict = train(&samples, 1024);
343/// assert!(dict.len() <= 1024, "the budget is a bound, not a hint");
344///
345/// let one = b"GET /api/v1/users/9 HTTP/1.1";
346/// assert_eq!(decode(&dict, &encode(&dict, one)).unwrap(), one);
347/// ```
348#[must_use]
349pub fn train(samples: &[&[u8]], budget: usize) -> Vec<u8> {
350 let mut dict = Vec::with_capacity(budget.min(MAX_OFFSET + 256));
351 if samples.is_empty() || budget == 0 {
352 return dict;
353 }
354 // File-scoped entropy table: one 128 B header per FILE amortizes
355 // where the per-record header measured itself out at 400 B.
356 // Add-one smoothing keeps every byte codable, so a block never
357 // falls back merely because it contains a byte the samples lacked.
358 // The header spends budget like anything else; a budget too small
359 // to leave meaningful content after it skips the table.
360 let header = DICT_MAGIC.len() + huff::HEADER_LEN;
361 if budget >= header * 8 {
362 emit_table(samples, &mut dict);
363 }
364 // Content is what back-references reach: clamp IT to the offset
365 // limit; the header rides above that reach.
366 let budget = (budget - dict.len()).min(MAX_OFFSET);
367 // Stride so picks span the corpus rather than clustering at the
368 // front — rotation seeding hands us *old* files' bytes first, and
369 // the tail is as representative as the head. Exact duplicates are
370 // skipped: a dictionary is a model, and a second copy of a sample
371 // teaches it nothing while charging every record its amortized
372 // bytes (the corpora comparison measured the un-deduped version paying
373 // 65 B/value of dictionary for an identical corpus whose whole
374 // model is one 400 B value).
375 let mut need = budget;
376 let avg = samples.iter().map(|s| s.len()).sum::<usize>() / samples.len().max(1);
377 let stride = if avg == 0 { 1 } else { (samples.len() * avg / budget).max(1) };
378 let mut seen = alloc::collections::BTreeSet::new();
379 let mut i = 0;
380 while i < samples.len() && need > 0 {
381 if seen.insert(fnv1a(samples[i])) {
382 let take = samples[i].len().min(need);
383 dict.extend_from_slice(&samples[i][..take]);
384 need -= take;
385 }
386 i += stride;
387 }
388 dict
389}
390
391/// The dictionary's file-scoped entropy table: magic + packed code
392/// lengths from an add-one-smoothed histogram of the sample bytes.
393fn emit_table(samples: &[&[u8]], dict: &mut Vec<u8>) {
394 let mut hist = [1u64; 256];
395 for s in samples {
396 for &b in *s {
397 hist[b as usize] += 1;
398 }
399 }
400 dict.extend_from_slice(DICT_MAGIC);
401 let lens = huff::code_lengths(&hist);
402 for pair in lens.as_chunks::<2>().0 {
403 dict.push(pair[0] | (pair[1] << 4));
404 }
405}
406
407/// Sample identity for training dedup — FNV-1a over the whole sample.
408/// A collision merely drops one sample from the dictionary; it cannot
409/// affect correctness (the dictionary is advisory bytes).
410fn fnv1a(bytes: &[u8]) -> u64 {
411 let mut h: u64 = 0xcbf2_9ce4_8422_2325;
412 for &b in bytes {
413 h ^= u64::from(b);
414 h = h.wrapping_mul(0x100_0000_01b3);
415 }
416 h
417}
418
419/// Largest header: tag byte plus a five-byte LEB128 length.
420const MAX_HEADER: usize = 6;
421
422fn push_header(out: &mut Vec<u8>, tag: u8, orig_len: usize) {
423 out.push(tag);
424 push_varint(out, orig_len);
425}
426
427pub(crate) fn push_varint(out: &mut Vec<u8>, value: usize) {
428 let mut v = value as u64;
429 loop {
430 let b = (v & 0x7f) as u8;
431 v >>= 7;
432 if v == 0 {
433 out.push(b);
434 break;
435 }
436 out.push(b | 0x80);
437 }
438}
439
440/// The LZ path writes its payload first (so it can abort to raw
441/// without having written a header); splice the header in front once
442/// the payload has proven itself.
443fn finish_header(frame: &mut Vec<u8>, tag: u8, orig_len: usize) {
444 let mut header = Vec::with_capacity(MAX_HEADER);
445 push_header(&mut header, tag, orig_len);
446 frame.splice(0..0, header);
447}
448
449pub(crate) fn read_varint(buf: &[u8]) -> Result<(usize, &[u8]), DecodeError> {
450 let mut v: u64 = 0;
451 let mut shift = 0u32;
452 for (i, &b) in buf.iter().enumerate() {
453 if shift >= 35 {
454 return Err(DecodeError);
455 }
456 v |= u64::from(b & 0x7f) << shift;
457 if b & 0x80 == 0 {
458 return Ok((v as usize, &buf[i + 1..]));
459 }
460 shift += 7;
461 }
462 Err(DecodeError)
463}
464
465// Send and Sync are part of the public contract: a change that loses
466// either fails to compile here rather than in a caller.
467const _: () = {
468 const fn send_sync<T: Send + Sync>() {}
469 send_sync::<DecodeError>();
470 send_sync::<Dict>();
471};
472
473#[cfg(test)]
474mod tests;