#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum Algorithm {
#[cfg_attr(not(feature = "btrfs"), allow(dead_code))]
Zlib,
#[cfg_attr(not(feature = "btrfs"), allow(dead_code))]
Lzo,
#[cfg_attr(not(feature = "btrfs"), allow(dead_code))]
Zstd,
#[cfg_attr(not(feature = "apfs"), allow(dead_code))]
Lzvn,
#[cfg_attr(not(feature = "apfs"), allow(dead_code))]
Lzfse,
#[cfg_attr(not(feature = "apfs"), allow(dead_code))]
Lzbitmap,
}
impl Algorithm {
pub(crate) const fn name(self) -> &'static str {
match self {
Algorithm::Zlib => "zlib",
Algorithm::Lzo => "lzo",
Algorithm::Zstd => "zstd",
Algorithm::Lzvn => "lzvn",
Algorithm::Lzfse => "lzfse",
Algorithm::Lzbitmap => "lzbitmap",
}
}
pub(crate) const fn available(self) -> bool {
match self {
Algorithm::Zlib => cfg!(feature = "zlib"),
Algorithm::Lzo => cfg!(feature = "lzo"),
Algorithm::Zstd => cfg!(feature = "zstd"),
Algorithm::Lzvn => cfg!(feature = "lzvn"),
Algorithm::Lzfse => cfg!(feature = "lzfse"),
Algorithm::Lzbitmap => cfg!(feature = "lzbitmap"),
}
}
}
pub(crate) struct CompiledBy(pub(crate) Option<Algorithm>);
impl std::fmt::Display for CompiledBy {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self.0 {
Some(algorithm) => write!(
f,
"; the `{}` feature compiles its decoder",
algorithm.name()
),
None => Ok(()),
}
}
}
#[cfg_attr(
not(any(
feature = "zlib",
feature = "lzo",
feature = "zstd",
feature = "lzvn",
feature = "lzbitmap"
)),
allow(dead_code)
)]
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub(crate) enum Error {
#[error(
"{} is an algorithm this build does not decode{}",
.0.name(),
CompiledBy(Some(*.0))
)]
Unavailable(Algorithm),
#[error("the {} stream does not decode: {fault}", .algorithm.name())]
#[non_exhaustive]
Malformed {
algorithm: Algorithm,
fault: &'static str,
},
#[error(
"the {} stream expands past the {expected} bytes the record declares",
.algorithm.name()
)]
#[non_exhaustive]
Overrun {
algorithm: Algorithm,
expected: usize,
},
}
#[cfg_attr(
not(any(
feature = "zlib",
feature = "lzo",
feature = "zstd",
feature = "lzvn",
feature = "lzbitmap"
)),
allow(unused_variables)
)]
pub(crate) fn decompress(
algorithm: Algorithm,
input: &[u8],
out: &mut [u8],
) -> Result<usize, Error> {
match algorithm {
#[cfg(feature = "zlib")]
Algorithm::Zlib => zlib::decompress(input, out),
#[cfg(feature = "lzo")]
Algorithm::Lzo => lzo::decompress(input, out),
#[cfg(feature = "zstd")]
Algorithm::Zstd => zstd::decompress(input, out),
#[cfg(feature = "lzvn")]
Algorithm::Lzvn => lifted(Algorithm::Lzvn, ferrosys_lzfse::decompress_lzvn(input, out)),
#[cfg(feature = "lzfse")]
Algorithm::Lzfse => lifted(
Algorithm::Lzfse,
ferrosys_lzfse::decompress_lzfse(input, out),
),
#[cfg(feature = "lzbitmap")]
Algorithm::Lzbitmap => lzbitmap::decompress(input, out),
#[allow(unreachable_patterns)]
other => Err(Error::Unavailable(other)),
}
}
#[cfg(feature = "zlib")]
mod zlib {
use super::{Algorithm, Error};
pub(super) fn decompress(input: &[u8], out: &mut [u8]) -> Result<usize, Error> {
use miniz_oxide::inflate::TINFLStatus;
miniz_oxide::inflate::decompress_slice_iter_to_slice(
out,
core::iter::once(input),
true,
false,
)
.map_err(|status| match status {
TINFLStatus::HasMoreOutput => Error::Overrun {
algorithm: Algorithm::Zlib,
expected: out.len(),
},
TINFLStatus::NeedsMoreInput | TINFLStatus::FailedCannotMakeProgress => {
Error::Malformed {
algorithm: Algorithm::Zlib,
fault: "the stream ends mid-symbol",
}
}
TINFLStatus::BadParam => Error::Malformed {
algorithm: Algorithm::Zlib,
fault: "the stream's own parameters are not ones the format defines",
},
TINFLStatus::Adler32Mismatch => Error::Malformed {
algorithm: Algorithm::Zlib,
fault: "the stream's own checksum does not cover what it decoded to",
},
_ => Error::Malformed {
algorithm: Algorithm::Zlib,
fault: "the stream is not well-formed",
},
})
}
}
#[cfg(feature = "zstd")]
mod zstd {
use std::io::Read as _;
use super::{Algorithm, Error};
const MIN_WINDOW: u64 = 1 << 10;
pub(super) fn decompress(input: &[u8], out: &mut [u8]) -> Result<usize, Error> {
let malformed = |fault| Error::Malformed {
algorithm: Algorithm::Zstd,
fault,
};
let window_cap = (out.len() as u64).next_power_of_two().max(MIN_WINDOW);
let mut decoder =
ruzstd::decoding::StreamingDecoder::new_with_max_window_size(input, window_cap)
.map_err(|error| match error {
ruzstd::decoding::errors::FrameDecoderError::WindowSizeTooBig { .. } => {
malformed("the frame declares a window larger than what it decodes into")
}
_ => malformed("the frame header is not one the format defines"),
})?;
let mut filled = 0;
while filled < out.len() {
match decoder.read(&mut out[filled..]) {
Ok(0) => return Ok(filled),
Ok(n) => filled += n,
Err(_) => return Err(malformed("the frame does not decode")),
}
}
let mut past = [0u8; 1];
match decoder.read(&mut past) {
Ok(0) => Ok(filled),
Ok(_) => Err(Error::Overrun {
algorithm: Algorithm::Zstd,
expected: out.len(),
}),
Err(_) => Err(malformed("the frame does not decode")),
}
}
}
#[cfg(feature = "lzvn")]
fn lifted(
algorithm: Algorithm,
answer: Result<usize, ferrosys_lzfse::Error>,
) -> Result<usize, Error> {
answer.map_err(|error| match error {
ferrosys_lzfse::Error::Malformed { fault, .. } => Error::Malformed { algorithm, fault },
ferrosys_lzfse::Error::Overrun { expected, .. } => Error::Overrun {
algorithm,
expected,
},
_ => Error::Malformed {
algorithm,
fault: "the decoder refuses the stream",
},
})
}
#[cfg(feature = "lzo")]
fn copy_back(out: &mut [u8], at: usize, distance: usize, count: usize) -> bool {
if distance == 0 || distance > at {
return false;
}
for i in at..at + count {
out[i] = out[i - distance];
}
true
}
#[cfg(feature = "lzo")]
pub(crate) mod lzo;
#[cfg(feature = "lzbitmap")]
mod lzbitmap;
#[cfg(all(test, feature = "lzvn", feature = "lzfse", feature = "lzbitmap"))]
mod reference;
#[cfg(all(
test,
any(
feature = "lzo",
feature = "zlib",
feature = "zstd",
feature = "lzbitmap"
)
))]
pub(crate) fn sweep_changes_of<E>(
stream: &[u8],
room: usize,
mut decode: impl FnMut(&[u8], &mut [u8]) -> Result<usize, E>,
) {
const GUARD: u8 = 0xee;
let mut held = |bytes: &[u8], what: &dyn Fn() -> String| {
let mut out = vec![GUARD; room + 64];
if let Ok(produced) = decode(bytes, &mut out[..room]) {
assert!(produced <= room, "{} reported {produced} of {room}", what());
}
assert!(
out[room..].iter().all(|&b| b == GUARD),
"{} wrote past the buffer it was given",
what()
);
};
let mut changed = stream.to_vec();
for at in 0..stream.len() {
for value in [
stream[at] ^ 0x01,
stream[at] ^ 0x80,
!stream[at],
0x00,
0x7F,
0xFF,
] {
changed[at] = value;
held(&changed, &|| format!("byte {at} as {value:#04x}"));
}
changed[at] = stream[at];
}
for len in 0..stream.len() {
held(&stream[..len], &|| format!("the first {len} bytes"));
}
}
#[cfg(all(
test,
any(
feature = "lzo",
feature = "zlib",
feature = "zstd",
feature = "lzvn",
feature = "lzbitmap"
)
))]
pub(crate) fn sweep_arbitrary_bytes<E>(
salt: u32,
mut decode: impl FnMut(&[u8], &mut [u8]) -> Result<usize, E>,
) {
const GUARD: u8 = 0xee;
for seed in 0..2048u32 {
let mut bytes = Vec::new();
let mut x = seed.wrapping_mul(2_654_435_761).wrapping_add(salt);
for _ in 0..(seed as usize % 160) + 1 {
x = x.wrapping_mul(1_103_515_245).wrapping_add(12_345);
bytes.push((x >> 16) as u8);
}
let mut out = [GUARD; 512];
let room = out.len() - 64;
if let Ok(produced) = decode(&bytes, &mut out[..room]) {
assert!(
produced <= room,
"seed {seed} reported {produced} of {room}"
);
}
assert!(
out[room..].iter().all(|&b| b == GUARD),
"seed {seed} wrote past the buffer it was given"
);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn every_algorithm_is_named_whether_or_not_this_build_decodes_it() {
for (algorithm, name) in [
(Algorithm::Zlib, "zlib"),
(Algorithm::Lzo, "lzo"),
(Algorithm::Zstd, "zstd"),
(Algorithm::Lzvn, "lzvn"),
(Algorithm::Lzfse, "lzfse"),
(Algorithm::Lzbitmap, "lzbitmap"),
] {
assert_eq!(algorithm.name(), name);
assert_eq!(
Error::Unavailable(algorithm).to_string(),
format!(
"{name} is an algorithm this build does not decode; the `{name}` feature \
compiles its decoder"
)
);
}
}
#[test]
fn the_feature_a_refusal_names_is_one_the_manifest_declares() {
let manifest = include_str!("../Cargo.toml");
let features = manifest
.split("\n[features]\n")
.nth(1)
.and_then(|rest| rest.split("\n[").next())
.expect("the manifest has a [features] table");
let declared: Vec<&str> = features
.lines()
.filter_map(|line| line.split_once(" = ").map(|(name, _)| name.trim()))
.filter(|name| !name.starts_with('#'))
.collect();
for algorithm in [
Algorithm::Zlib,
Algorithm::Lzo,
Algorithm::Zstd,
Algorithm::Lzvn,
Algorithm::Lzfse,
Algorithm::Lzbitmap,
] {
assert!(
declared.contains(&algorithm.name()),
"`{}` is not a feature in {declared:?}",
algorithm.name()
);
}
assert_eq!(CompiledBy(None).to_string(), "");
}
#[test]
fn an_algorithm_this_build_does_not_carry_is_refused_rather_than_attempted() {
for algorithm in [
Algorithm::Zlib,
Algorithm::Lzo,
Algorithm::Zstd,
Algorithm::Lzvn,
Algorithm::Lzfse,
Algorithm::Lzbitmap,
] {
let mut out = [0u8; 8];
let refused = decompress(algorithm, b"", &mut out);
assert_eq!(
matches!(refused, Err(Error::Unavailable(_))),
!algorithm.available(),
"{algorithm:?} reported itself {} and answered {refused:?}",
if algorithm.available() {
"available"
} else {
"unavailable"
}
);
}
}
#[cfg(feature = "zlib")]
#[test]
fn a_zlib_stream_decodes_to_what_it_stands_for() {
const STREAM: &[u8] = &[
0x78, 0xda, 0x4b, 0x4b, 0x2d, 0x2a, 0xca, 0x2f, 0xae, 0x2c, 0x4e, 0x23, 0x93, 0x06,
0x00, 0x88, 0x65, 0x1b, 0xe9,
];
let want = b"ferrosys".repeat(8);
let mut out = vec![0u8; want.len()];
assert_eq!(
decompress(Algorithm::Zlib, STREAM, &mut out),
Ok(want.len())
);
assert_eq!(out, want);
let mut small = vec![0u8; want.len() - 1];
assert!(matches!(
decompress(Algorithm::Zlib, STREAM, &mut small),
Err(Error::Overrun { .. })
));
let mut out = vec![0u8; 64];
assert!(matches!(
decompress(Algorithm::Zlib, b"not a stream", &mut out),
Err(Error::Malformed { .. })
));
}
#[cfg(feature = "zstd")]
#[test]
fn a_zstd_frame_declaring_a_giant_window_is_refused_at_the_header() {
const FRAME: &[u8] = &[0x28, 0xb5, 0x2f, 0xfd, 0x00, 0x80];
let mut out = vec![0u8; 4096];
assert_eq!(
decompress(Algorithm::Zstd, FRAME, &mut out),
Err(Error::Malformed {
algorithm: Algorithm::Zstd,
fault: "the frame declares a window larger than what it decodes into",
})
);
}
#[cfg(feature = "zstd")]
#[test]
fn a_zstd_block_expanding_past_its_window_is_refused_rather_than_produced() {
const fn frame(window: u8) -> [u8; 22] {
[
0x28, 0xb5, 0x2f, 0xfd, 0x00, window, 0x08, 0x00, 0x00, b'A', 0x4d, 0x00, 0x00,
0x00, 0x01, 0x54, 0x00, 0x02, 0x34, 0x00, 0x00, 0x04,
]
}
let mut out = vec![0u8; 4096];
assert_eq!(
decompress(Algorithm::Zstd, &frame(0x10), &mut out),
Err(Error::Malformed {
algorithm: Algorithm::Zstd,
fault: "the frame does not decode",
})
);
let mut out = vec![0u8; 1 + 65_539];
assert_eq!(
decompress(Algorithm::Zstd, &frame(0x38), &mut out),
Ok(out.len())
);
assert!(out.iter().all(|&byte| byte == b'A'));
}
#[cfg(feature = "zstd")]
#[test]
fn a_zstd_frame_decodes_to_what_it_stands_for() {
const FRAME: &[u8] = &[
0x28, 0xb5, 0x2f, 0xfd, 0x24, 0x40, 0x7d, 0x00, 0x00, 0x48, 0x66, 0x65, 0x72, 0x72,
0x6f, 0x73, 0x79, 0x73, 0x66, 0x01, 0x00, 0x7c, 0xde, 0x23, 0x80, 0xc5, 0xf4, 0x04,
];
let want = b"ferrosys".repeat(8);
let mut out = vec![0u8; want.len()];
assert_eq!(decompress(Algorithm::Zstd, FRAME, &mut out), Ok(want.len()));
assert_eq!(out, want);
let mut small = vec![0u8; want.len() - 1];
assert!(matches!(
decompress(Algorithm::Zstd, FRAME, &mut small),
Err(Error::Overrun { .. })
));
let mut out = vec![0u8; 64];
assert!(matches!(
decompress(Algorithm::Zstd, b"not a frame at all", &mut out),
Err(Error::Malformed { .. })
));
}
#[cfg(feature = "zlib")]
#[test]
fn arbitrary_bytes_are_a_zlib_stream_that_refuses_or_fits() {
sweep_arbitrary_bytes(2, |bytes, out| decompress(Algorithm::Zlib, bytes, out));
}
#[cfg(feature = "zstd")]
#[test]
fn arbitrary_bytes_are_a_zstd_frame_that_refuses_or_fits() {
sweep_arbitrary_bytes(3, |bytes, out| decompress(Algorithm::Zstd, bytes, out));
}
#[cfg(feature = "lzvn")]
#[test]
fn arbitrary_bytes_are_an_lzvn_stream_that_refuses_or_fits() {
sweep_arbitrary_bytes(4, |bytes, out| decompress(Algorithm::Lzvn, bytes, out));
}
#[cfg(feature = "zlib")]
#[test]
fn a_zlib_stream_changed_a_byte_at_a_time_refuses_or_fits() {
const STREAM: &[u8] = &[
0x78, 0xda, 0x4b, 0x4b, 0x2d, 0x2a, 0xca, 0x2f, 0xae, 0x2c, 0x4e, 0x23, 0x93, 0x06,
0x00, 0x88, 0x65, 0x1b, 0xe9,
];
sweep_changes_of(STREAM, 64 + 16, |bytes, out| {
decompress(Algorithm::Zlib, bytes, out)
});
}
#[cfg(feature = "lzfse")]
#[test]
fn arbitrary_bytes_are_an_lzfse_stream_that_refuses_or_fits() {
for (i, magic) in [b"bvx-", b"bvxn", b"bvx2", b"bvx$"].into_iter().enumerate() {
sweep_arbitrary_bytes(5 + i as u32, |bytes, out| {
let stream = [&magic[..], bytes].concat();
decompress(Algorithm::Lzfse, &stream, out)
});
}
}
}