Skip to main content

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;