Skip to main content

embark_codec/
best.rs

1//! Codec selection for the `auto` family: compress with a tier of candidate
2//! codecs and keep the smallest result.
3
4extern crate alloc;
5#[cfg(feature = "enc")]
6use alloc::vec::Vec;
7#[cfg(feature = "enc")]
8use embark_format::CodecId;
9
10/// Which codecs a selection pass is allowed to try.
11///
12/// Compression runs once, in the proc macro; decompression runs in every
13/// consumer's shipped binary on every access. The two are not
14/// interchangeable costs, so the tiers cut the codec set by decode speed and
15/// each keeps the smallest output *within its own candidates*. Measured on a
16/// 125,976-byte executable, with the decoders this crate actually ships:
17///
18/// | tier | wins with | payload | decode |
19/// |---|---|---:|---:|
20/// | [`Fast`](AutoTier::Fast) | LZ4 | 81,798 B | 2,775 MB/s |
21/// | [`Balanced`](AutoTier::Balanced) | Zstd | 56,140 B | 112 MB/s |
22/// | [`Small`](AutoTier::Small) | LZMA | 52,512 B | 41 MB/s |
23///
24/// The tiers are nested, so a wider one never picks a *larger* payload than
25/// a narrower one. They are fixed membership rather than a cost function:
26/// which codec a build selects has to be predictable from the asset and the
27/// enabled features alone, never from how fast the build machine is.
28///
29/// The tier is a build-time policy. An entry header records the one
30/// [`CodecId`] that won, so nothing about it reaches the decode side.
31#[cfg(feature = "enc")]
32#[derive(Debug, Clone, Copy, PartialEq, Eq)]
33pub enum AutoTier {
34    /// `Store`, `Lz4`, `Snappy` — the codecs that decode at GB/s.
35    ///
36    /// Selected by `codec = auto_fast`. Also by far the cheapest to
37    /// *encode*: it runs neither the LZMA nor the Zstd encoder, both of
38    /// which search hard enough to cost minutes on a large, poorly
39    /// compressible asset. Measured on 32 MiB of such data: this tier took
40    /// 0.2 s where [`Balanced`](AutoTier::Balanced) took 180 s.
41    Fast,
42    /// [`Fast`](AutoTier::Fast) plus `Deflate` and `Zstd`.
43    ///
44    /// Selected by `codec = auto`, and the balance point the `auto` family
45    /// is named for: roughly a third off the payload `Fast` picks, and
46    /// still read back around three times quicker than LZMA's.
47    ///
48    /// The balance is in *decode* speed, which the consumer's binary pays on
49    /// every access. It is not cheap to encode: Zstd parses each block by
50    /// price over several passes, so a large asset costs this tier minutes
51    /// at build time. See the README's note on build times.
52    Balanced,
53    /// [`Balanced`](AutoTier::Balanced) plus `Lzma` — every compressing
54    /// codec there is.
55    ///
56    /// Selected by `codec = auto_small`. The smallest binary available, at
57    /// the slowest decode. Its build cost is close to
58    /// [`Balanced`](AutoTier::Balanced)'s rather than far above it, since
59    /// both tiers run a codec that searches hard: 226 s against 180 s on
60    /// the same 32 MiB asset.
61    Small,
62}
63
64/// Whether `id` is one of `tier`'s candidates.
65///
66/// [`CodecId::Store`] is deliberately absent: it is the baseline every tier
67/// falls back to when nothing shrinks the input, not a codec a tier chooses
68/// between.
69#[cfg(feature = "enc")]
70fn contains(tier: AutoTier, id: CodecId) -> bool {
71    match id {
72        CodecId::Lz4 | CodecId::Snappy => true,
73        CodecId::Deflate | CodecId::Zstd => matches!(tier, AutoTier::Balanced | AutoTier::Small),
74        CodecId::Lzma => matches!(tier, AutoTier::Small),
75        // `Store`, plus -- `CodecId` being `#[non_exhaustive]` -- any codec
76        // added to the format and not yet placed in a tier.
77        _ => false,
78    }
79}
80
81/// Whether this build compiled in any of `tier`'s candidates.
82#[cfg(feature = "enc")]
83fn is_populated(tier: AutoTier) -> bool {
84    crate::dispatch::ENCODERS
85        .iter()
86        .any(|&(id, _)| contains(tier, id))
87}
88
89/// The tier a request for `tier` actually runs, after widening.
90///
91/// A tier whose candidates are all switched off at feature level would
92/// otherwise emit `Store` and leave the asset uncompressed, which is the
93/// worst outcome on both axes at once. The tiers nest, so widening is
94/// well-defined: take the narrowest tier at or above the requested one that
95/// this build has a candidate for. A build with only `lzma` on therefore
96/// serves `auto_fast` with LZMA -- the fast codecs it asked for do not
97/// exist here, and LZMA is strictly better than not compressing.
98///
99/// This depends only on the enabled features, never on the asset or the
100/// build machine.
101#[cfg(feature = "enc")]
102fn effective(tier: AutoTier) -> AutoTier {
103    let wider: &[AutoTier] = match tier {
104        AutoTier::Fast => &[AutoTier::Fast, AutoTier::Balanced, AutoTier::Small],
105        AutoTier::Balanced => &[AutoTier::Balanced, AutoTier::Small],
106        AutoTier::Small => &[AutoTier::Small],
107    };
108    // With no compressing codec compiled in at all there is nothing to widen
109    // to; the caller falls through to `Store` either way.
110    wider
111        .iter()
112        .copied()
113        .find(|&t| is_populated(t))
114        .unwrap_or(tier)
115}
116
117/// Compress `input` with each of `tier`'s candidates compiled into this
118/// build and return the smallest result.
119///
120/// Only the tier's own candidates are encoded, so `AutoTier::Fast` does not
121/// pay LZMA's encode time to then discard its output.
122///
123/// [`CodecId::Store`] is the baseline: a codec wins only if it is strictly
124/// smaller than the input, and among codecs the earliest entry of the codec
125/// table wins a tie, which is what `min_by_key` yields.
126///
127/// If none of `tier`'s candidates were compiled in, the selection widens to
128/// the next tier rather than giving up and storing the input verbatim.
129#[cfg(feature = "enc")]
130#[must_use]
131pub fn compress_best_in(tier: AutoTier, input: &[u8]) -> (CodecId, Vec<u8>) {
132    let tier = effective(tier);
133    // The candidates are independent: each reads the same input and writes
134    // its own output, and none of them looks at what another produced. With
135    // `parallel-encode` on they run concurrently, which matters most for the
136    // tiers that include a codec searching as hard as Zstd or LZMA.
137    //
138    // `map` preserves the table's order, so the tie-break below is the one
139    // the table spells out rather than whichever encoder happened to finish
140    // first.
141    let candidates: Vec<(CodecId, crate::dispatch::CompressFn)> = crate::dispatch::ENCODERS
142        .iter()
143        .copied()
144        .filter(|&(id, _)| contains(tier, id))
145        .collect();
146    crate::parallel::map(&candidates, |&(id, compress)| (id, compress(input)))
147        .into_iter()
148        .min_by_key(|(_, out)| out.len())
149        .filter(|(_, out)| out.len() < input.len())
150        .unwrap_or_else(|| (CodecId::Store, crate::store::compress(input)))
151}
152
153/// Compress `input` with every codec compiled into this build and return the
154/// smallest result.
155///
156/// The smallest-output end of the family, equivalent to
157/// [`compress_best_in`] with [`AutoTier::Small`].
158#[cfg(feature = "enc")]
159#[must_use]
160pub fn compress_best(input: &[u8]) -> (CodecId, Vec<u8>) {
161    compress_best_in(AutoTier::Small, input)
162}