libflate_lz77/
lib.rs

1//! The interface and implementations of LZ77 compression algorithm.
2//!
3//! LZ77 is a compression algorithm used in [DEFLATE](https://tools.ietf.org/html/rfc1951).
4#![warn(missing_docs)]
5#![cfg_attr(not(feature = "std"), no_std)]
6
7extern crate alloc;
8
9pub use self::default::{DefaultLz77Encoder, DefaultLz77EncoderBuilder};
10use alloc::vec::Vec;
11use core::cmp;
12use no_std_io2::io;
13use rle_decode_fast::rle_decode;
14
15mod default;
16
17/// Maximum length of sharable bytes in a pointer.
18pub const MAX_LENGTH: u16 = 258;
19
20/// Maximum backward distance of a pointer.
21pub const MAX_DISTANCE: u16 = 32_768;
22
23/// Maximum size of a sliding window.
24pub const MAX_WINDOW_SIZE: u16 = MAX_DISTANCE;
25
26/// A LZ77 encoded data.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
28pub enum Code {
29    /// Literal byte.
30    Literal(u8),
31
32    /// Backward pointer to shared data.
33    Pointer {
34        /// Length of the shared data.
35        /// The values must be limited to [`MAX_LENGTH`].
36        length: u16,
37
38        /// Distance between current position and start position of the shared data.
39        /// The values must be limited to [`MAX_DISTANCE`].
40        backward_distance: u16,
41    },
42}
43
44/// Compression level.
45#[derive(Debug, Clone, PartialEq, Eq, Hash)]
46pub enum CompressionLevel {
47    /// No compression.
48    None,
49
50    /// Best speed.
51    Fast,
52
53    /// Balanced between speed and size.
54    Balance,
55
56    /// Best compression.
57    Best,
58}
59
60/// The [`Sink`] trait represents a consumer of LZ77 encoded data.
61pub trait Sink {
62    /// Consumes a LZ77 encoded `Code`.
63    fn consume(&mut self, code: Code);
64}
65impl<T> Sink for &mut T
66where
67    T: Sink,
68{
69    fn consume(&mut self, code: Code) {
70        (*self).consume(code);
71    }
72}
73impl<T> Sink for Vec<T>
74where
75    T: From<Code>,
76{
77    fn consume(&mut self, code: Code) {
78        self.push(T::from(code));
79    }
80}
81
82/// The [`Lz77Encode`] trait defines the interface of LZ77 encoding algorithm.
83pub trait Lz77Encode {
84    /// Encodes a buffer and writes result LZ77 codes to `sink`.
85    fn encode<S>(&mut self, buf: &[u8], sink: S)
86    where
87        S: Sink;
88
89    /// Flushes the encoder, ensuring that all intermediately buffered codes are consumed by `sink`.
90    fn flush<S>(&mut self, sink: S)
91    where
92        S: Sink;
93
94    /// Returns the compression level of the encoder.
95    ///
96    /// If the implementation is omitted, [`CompressionLevel::Balance`] will be returned.
97    fn compression_level(&self) -> CompressionLevel {
98        CompressionLevel::Balance
99    }
100
101    /// Returns the window size of the encoder.
102    ///
103    /// If the implementation is omitted, [`MAX_WINDOW_SIZE`] will be returned.
104    fn window_size(&self) -> u16 {
105        MAX_WINDOW_SIZE
106    }
107}
108
109/// A no compression implementation of [`Lz77Encode`] trait.
110#[derive(Debug, Default)]
111pub struct NoCompressionLz77Encoder;
112impl NoCompressionLz77Encoder {
113    /// Makes a new encoder instance.
114    ///
115    /// # Examples
116    /// ```
117    /// use libflate_lz77::{CompressionLevel, Lz77Encode, NoCompressionLz77Encoder};
118    ///
119    /// let lz77 = NoCompressionLz77Encoder::new();
120    /// assert_eq!(lz77.compression_level(), CompressionLevel::None);
121    /// assert_eq!(lz77.window_size(), libflate_lz77::MAX_WINDOW_SIZE);
122    /// ```
123    pub fn new() -> Self {
124        NoCompressionLz77Encoder
125    }
126}
127impl Lz77Encode for NoCompressionLz77Encoder {
128    fn encode<S>(&mut self, buf: &[u8], mut sink: S)
129    where
130        S: Sink,
131    {
132        for c in buf.iter().cloned().map(Code::Literal) {
133            sink.consume(c);
134        }
135    }
136    #[allow(unused_variables)]
137    fn flush<S>(&mut self, sink: S)
138    where
139        S: Sink,
140    {
141    }
142    fn compression_level(&self) -> CompressionLevel {
143        CompressionLevel::None
144    }
145}
146
147/// LZ77 decoder.
148#[derive(Debug, Default)]
149pub struct Lz77Decoder {
150    buffer: Vec<u8>,
151    offset: usize,
152}
153
154impl Lz77Decoder {
155    /// Makes a new [`Lz77Decoder`] instance.
156    pub fn new() -> Self {
157        Self::default()
158    }
159
160    /// Decodes a [`Code`].
161    ///
162    /// The decoded bytes are appended to the buffer of [`Lz77Decoder`].
163    #[inline]
164    pub fn decode(&mut self, code: Code) -> io::Result<()> {
165        match code {
166            Code::Literal(b) => {
167                self.buffer.push(b);
168            }
169            Code::Pointer {
170                length,
171                backward_distance,
172            } => {
173                if self.buffer.len() < backward_distance as usize {
174                    return Err(io::Error::new(
175                        io::ErrorKind::InvalidData,
176                        #[cfg(feature = "std")]
177                        format!(
178                            "Too long backword reference: buffer.len={}, distance={}",
179                            self.buffer.len(),
180                            backward_distance
181                        ),
182                        #[cfg(not(feature = "std"))]
183                        "Too long backword reference",
184                    ));
185                }
186                rle_decode(
187                    &mut self.buffer,
188                    usize::from(backward_distance),
189                    usize::from(length),
190                );
191            }
192        }
193        Ok(())
194    }
195
196    /// Appends the bytes read from `reader` to the buffer of [`Lz77Decoder`].
197    pub fn extend_from_reader<R: io::Read>(&mut self, mut reader: R) -> io::Result<usize> {
198        reader.read_to_end(&mut self.buffer)
199    }
200
201    /// Appends the given bytes to the buffer of [`Lz77Decoder`].
202    pub fn extend_from_slice(&mut self, buf: &[u8]) {
203        self.buffer.extend_from_slice(buf);
204        self.offset += buf.len();
205    }
206
207    /// Clears the buffer of [`Lz77Decoder`].
208    pub fn clear(&mut self) {
209        self.buffer.clear();
210        self.offset = 0;
211    }
212
213    /// Returns the buffer of [`Lz77Decoder`].
214    #[inline]
215    pub fn buffer(&self) -> &[u8] {
216        &self.buffer[self.offset..]
217    }
218
219    fn truncate_old_buffer(&mut self) {
220        if self.buffer().is_empty() && self.buffer.len() > MAX_DISTANCE as usize * 4 {
221            let old_len = self.buffer.len();
222            let new_len = MAX_DISTANCE as usize;
223            {
224                // isolation to please borrow checker
225                let (dst, src) = self.buffer.split_at_mut(old_len - new_len);
226                dst[..new_len].copy_from_slice(src);
227            }
228            self.buffer.truncate(new_len);
229            self.offset = new_len;
230        }
231    }
232}
233
234impl io::Read for Lz77Decoder {
235    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
236        let copy_size = cmp::min(buf.len(), self.buffer.len() - self.offset);
237        buf[..copy_size].copy_from_slice(&self.buffer[self.offset..][..copy_size]);
238        self.offset += copy_size;
239        self.truncate_old_buffer();
240        Ok(copy_size)
241    }
242}
243
244#[cfg(test)]
245mod tests {
246    use super::*;
247    use alloc::vec::Vec;
248    use no_std_io2::io::Read as _;
249
250    #[test]
251    fn encoder_and_decoder_works() {
252        let mut codes = Vec::new();
253        let mut encoder = DefaultLz77Encoder::new();
254        encoder.encode(b"hello world!", &mut codes);
255        encoder.flush(&mut codes);
256        assert!(!codes.is_empty());
257
258        let mut decoder = Lz77Decoder::new();
259        for code in codes {
260            decoder.decode(code).unwrap();
261        }
262        assert_eq!(decoder.buffer(), b"hello world!");
263
264        let mut decoded = Vec::new();
265        decoder.read_to_end(&mut decoded).unwrap();
266        assert_eq!(decoded, b"hello world!");
267        assert!(decoder.buffer().is_empty());
268    }
269}
libflate_lz77/lib.rs

libflate_lz77/
lib.rs
