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))]
18 pub(crate) mod compress;
19 pub(crate) mod hashtable;
20
21 #[cfg(feature = "safe-decode")]
22 #[cfg_attr(feature = "safe-decode", forbid(unsafe_code))]
23 pub(crate) mod decompress_safe;
24 #[cfg(feature = "safe-decode")]
25 pub(crate) use decompress_safe as decompress;
26
27 #[cfg(not(feature = "safe-decode"))]
28 pub(crate) mod decompress;
29
30 pub use compress::*;
31 pub use decompress::*;
32
33 use core::convert::TryInto;
34 use core::fmt;
35
36 pub(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.
47 const MFLIMIT: usize = 12;
48
49 /// The last 5 bytes of input are always literals. Therefore, the last sequence contains at least 5
50 /// bytes.
51 const 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.
56 const 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.
62 const LZ4_MIN_LENGTH: usize = MFLIMIT + 1;
63
64 const MAXD_LOG: usize = 16;
65 const MAX_DISTANCE: usize = (1 << MAXD_LOG) - 1;
66
67 #[allow(dead_code)]
68 const MATCH_LENGTH_MASK: u32 = (1_u32 << 4) - 1; // 0b1111 / 15
69
70 /// The minimum length of a duplicate
71 const MINMATCH: usize = 4;
72
73 #[allow(dead_code)]
74 const FASTLOOP_SAFE_DISTANCE: usize = 64;
75
76 /// Switch for the hashtable size byU16
77 #[allow(dead_code)]
78 static LZ4_64KLIMIT: usize = (64 * 1024) + (MFLIMIT - 1);
79
80 /// An error representing invalid compressed data.
81 #[derive(Debug)]
82 #[non_exhaustive]
83 pub 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 /// Deduplication offset out of bounds (not in buffer).
96 OffsetOutOfBounds,
97 }
98
99 #[derive(Debug)]
100 #[non_exhaustive]
101 /// Errors that can happen during compression.
102 pub enum CompressError {
103 /// The provided output is too small.
104 OutputTooSmall,
105 }
106
107 impl fmt::Display for DecompressError {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result108 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
109 match self {
110 DecompressError::OutputTooSmall { expected, actual } => {
111 write!(
112 f,
113 "provided output is too small for the decompressed data, actual {actual}, expected \
114 {expected}"
115 )
116 }
117 DecompressError::LiteralOutOfBounds => {
118 f.write_str("literal is out of bounds of the input")
119 }
120 DecompressError::ExpectedAnotherByte => {
121 f.write_str("expected another byte, found none")
122 }
123 DecompressError::OffsetOutOfBounds => {
124 f.write_str("the offset to copy is not contained in the decompressed buffer")
125 }
126 }
127 }
128 }
129
130 impl fmt::Display for CompressError {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result131 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
132 match self {
133 CompressError::OutputTooSmall => f.write_str(
134 "output is too small for the compressed data, use get_maximum_output_size to \
135 reserve enough space",
136 ),
137 }
138 }
139 }
140
141 #[cfg(feature = "std")]
142 impl std::error::Error for DecompressError {}
143
144 #[cfg(feature = "std")]
145 impl std::error::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]
uncompressed_size(input: &[u8]) -> Result<(usize, &[u8]), DecompressError>151 pub 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