lz4_flex/block/
mod.rs

1//! LZ4 Block Format
2//!
3//! As defined in <https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md>
4//!
5//! Currently for no_std support only the block format is supported.
6//! Without the `alloc` feature only the `_into` variants are available, e.g. [`compress_into`].
7//!
8//! # Example: block format roundtrip
9//! ```
10//! use lz4_flex::block::{compress_prepend_size, decompress_size_prepended};
11//! let input: &[u8] = b"Hello people, what's up?";
12//! let compressed = compress_prepend_size(input);
13//! let uncompressed = decompress_size_prepended(&compressed).unwrap();
14//! assert_eq!(input, uncompressed);
15//! ```
16//!
17
18#[cfg_attr(feature = "safe-encode", forbid(unsafe_code))]
19pub(crate) mod compress;
20pub(crate) mod hashtable;
21
22#[cfg(feature = "safe-decode")]
23#[cfg_attr(feature = "safe-decode", forbid(unsafe_code))]
24pub(crate) mod decompress_safe;
25#[cfg(feature = "safe-decode")]
26pub(crate) use decompress_safe as decompress;
27
28#[cfg(not(feature = "safe-decode"))]
29pub(crate) mod decompress;
30
31pub use compress::*;
32pub use decompress::*;
33
34use core::{error::Error, fmt};
35
36pub(crate) const WINDOW_SIZE: usize = 64 * 1024;
37
38/// https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md#end-of-block-restrictions
39/// The last match must start at least 12 bytes before the end of block. The last match is part of
40/// the penultimate sequence. It is followed by the last sequence, which contains only literals.
41///
42/// Note that, as a consequence, an independent block < 13 bytes cannot be compressed, because the
43/// match must copy "something", so it needs at least one prior byte.
44///
45/// When a block can reference data from another block, it can start immediately with a match and no
46/// literal, so a block of 12 bytes can be compressed.
47const MFLIMIT: usize = 12;
48
49/// The last 5 bytes of input are always literals. Therefore, the last sequence contains at least 5
50/// bytes.
51const LAST_LITERALS: usize = 5;
52
53/// Due the way the compression loop is arrange we may read up to (register_size - 2) bytes from the
54/// current position. So we must end the matches 6 bytes before the end, 1 more than required by the
55/// spec.
56const END_OFFSET: usize = LAST_LITERALS + 1;
57
58/// https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md#end-of-block-restrictions
59/// Minimum length of a block
60///
61/// MFLIMIT + 1 for the token.
62const LZ4_MIN_LENGTH: usize = MFLIMIT + 1;
63
64const MAXD_LOG: usize = 16;
65const MAX_DISTANCE: usize = (1 << MAXD_LOG) - 1;
66
67#[allow(dead_code)]
68const MATCH_LENGTH_MASK: u32 = (1_u32 << 4) - 1; // 0b1111 / 15
69
70/// The minimum length of a duplicate
71const MINMATCH: usize = 4;
72
73#[allow(dead_code)]
74const FASTLOOP_SAFE_DISTANCE: usize = 64;
75
76/// Switch for the hashtable size byU16
77#[allow(dead_code)]
78static LZ4_64KLIMIT: usize = (64 * 1024) + (MFLIMIT - 1);
79
80/// An error representing invalid compressed data.
81#[derive(Debug)]
82#[non_exhaustive]
83pub enum DecompressError {
84    /// The provided output is too small
85    OutputTooSmall {
86        /// Minimum expected output size
87        expected: usize,
88        /// Actual size of output
89        actual: usize,
90    },
91    /// Literal is out of bounds of the input
92    LiteralOutOfBounds,
93    /// Expected another byte, but none found.
94    ExpectedAnotherByte,
95    /// Match offset is 0
96    OffsetZero,
97    /// Deduplication offset out of bounds (not in buffer).
98    OffsetOutOfBounds,
99}
100
101#[derive(Debug)]
102#[non_exhaustive]
103/// Errors that can happen during compression.
104pub enum CompressError {
105    /// The provided output is too small.
106    OutputTooSmall,
107}
108
109impl fmt::Display for DecompressError {
110    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
111        match self {
112            DecompressError::OutputTooSmall { expected, actual } => {
113                write!(
114                    f,
115                    "provided output is too small for the decompressed data, actual {actual}, expected \
116                     {expected}"
117                )
118            }
119            DecompressError::LiteralOutOfBounds => {
120                f.write_str("literal is out of bounds of the input")
121            }
122            DecompressError::ExpectedAnotherByte => {
123                f.write_str("expected another byte, found none")
124            }
125            DecompressError::OffsetZero => f.write_str("0 is not a valid match offset"),
126            DecompressError::OffsetOutOfBounds => {
127                f.write_str("the offset to copy is not contained in the decompressed buffer")
128            }
129        }
130    }
131}
132
133impl fmt::Display for CompressError {
134    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
135        match self {
136            CompressError::OutputTooSmall => f.write_str(
137                "output is too small for the compressed data, use get_maximum_output_size to \
138                 reserve enough space",
139            ),
140        }
141    }
142}
143
144impl Error for DecompressError {}
145
146impl Error for CompressError {}
147
148/// This can be used in conjunction with `decompress_size_prepended`.
149/// It will read the first 4 bytes as little-endian encoded length, and return
150/// the rest of the bytes after the length encoding.
151#[inline]
152pub fn uncompressed_size(input: &[u8]) -> Result<(usize, &[u8]), DecompressError> {
153    let size = input.get(..4).ok_or(DecompressError::ExpectedAnotherByte)?;
154    let size: &[u8; 4] = size.try_into().unwrap();
155    let uncompressed_size = u32::from_le_bytes(*size) as usize;
156    let rest = &input[4..];
157    Ok((uncompressed_size, rest))
158}
159
160#[test]
161#[cfg(target_pointer_width = "64")] // only relevant for 64bit CPUs
162fn large_integer_roundtrip() {
163    let u32_max = usize::try_from(u32::MAX).unwrap();
164    let value = u32_max + u32_max / 2;
165
166    let mut buf = vec![0u8; value / 255 + 1];
167    let mut sink = crate::sink::SliceSink::new(&mut buf, 0);
168    self::compress::write_integer(&mut sink, value);
169
170    #[cfg(feature = "safe-decode")]
171    let value_decompressed = self::decompress_safe::read_integer(&buf, &mut 0).unwrap();
172
173    #[cfg(not(feature = "safe-decode"))]
174    let value_decompressed = {
175        let mut ptr_range = buf.as_ptr_range();
176        self::decompress::read_integer_ptr(&mut ptr_range.start, ptr_range.end).unwrap()
177    };
178
179    assert_eq!(value, value_decompressed);
180}
lz4_flex/block/mod.rs

lz4_flex/block/
mod.rs
