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

lz4_flex/block/
mod.rs
