stak_lzss/
lib.rs

1//! LZSS compression.
2
3#![no_std]
4
5#[cfg(test)]
6extern crate alloc;
7#[cfg(test)]
8extern crate std;
9
10mod compress;
11mod decompress;
12mod ring_buffer;
13
14use self::{compress::LzssCompressionIterator, decompress::LzssDecompressionIterator};
15
16/// The maximum window size.
17pub const MAX_WINDOW_SIZE: usize = 1 << 8;
18
19/// The maximum match length.
20pub const MAX_LENGTH: usize = 1 << 7;
21
22/// LZSS compression for 7-bit bytes.
23pub trait Lzss {
24    /// Compresses bytes.
25    fn compress<const W: usize>(self) -> impl Iterator<Item = u8>;
26
27    /// Decompresses bytes.
28    fn decompress<const W: usize>(self) -> impl Iterator<Item = u8>;
29}
30
31impl<I: IntoIterator<Item = u8>> Lzss for I {
32    fn compress<const B: usize>(self) -> impl Iterator<Item = u8> {
33        LzssCompressionIterator::<B, _>::new(self.into_iter())
34    }
35
36    fn decompress<const W: usize>(self) -> impl Iterator<Item = u8> {
37        LzssDecompressionIterator::<W, _>::new(self.into_iter())
38    }
39}
40
41#[cfg(test)]
42mod tests {
43    use super::*;
44    use alloc::vec::Vec;
45    use core::iter::repeat;
46    use pretty_assertions::assert_eq;
47    use quickcheck_macros::quickcheck;
48
49    const WINDOW_SIZE: usize = 8;
50    const BUFFER_SIZE: usize = WINDOW_SIZE + MAX_LENGTH;
51
52    #[test]
53    fn empty() {
54        let data = [];
55
56        assert_eq!(
57            data.iter()
58                .copied()
59                .compress::<BUFFER_SIZE>()
60                .decompress::<WINDOW_SIZE>()
61                .collect::<Vec<u8>>(),
62            data
63        );
64    }
65
66    #[test]
67    fn byte() {
68        let data = [42];
69
70        assert_eq!(
71            data.iter()
72                .copied()
73                .compress::<BUFFER_SIZE>()
74                .decompress::<WINDOW_SIZE>()
75                .collect::<Vec<u8>>(),
76            data
77        );
78    }
79
80    #[test]
81    fn two_bytes() {
82        let data = [1, 2];
83
84        assert_eq!(
85            data.iter()
86                .copied()
87                .compress::<BUFFER_SIZE>()
88                .decompress::<WINDOW_SIZE>()
89                .collect::<Vec<u8>>(),
90            data
91        );
92    }
93
94    #[test]
95    fn three_bytes() {
96        let data = [1, 2, 3];
97
98        assert_eq!(
99            data.iter()
100                .copied()
101                .compress::<BUFFER_SIZE>()
102                .decompress::<WINDOW_SIZE>()
103                .collect::<Vec<u8>>(),
104            data
105        );
106    }
107
108    #[test]
109    fn ascii_string() {
110        let data = b"ABABABABABABABABABABA123123123123";
111
112        assert_eq!(
113            data.iter()
114                .copied()
115                .compress::<BUFFER_SIZE>()
116                .decompress::<WINDOW_SIZE>()
117                .collect::<Vec<u8>>(),
118            data
119        );
120    }
121
122    #[test]
123    fn uninitialized_zeros() {
124        let data = [0, 0, 0, 0, 0, 0];
125
126        assert_eq!(
127            data.iter()
128                .copied()
129                .compress::<BUFFER_SIZE>()
130                .decompress::<WINDOW_SIZE>()
131                .collect::<Vec<u8>>(),
132            data
133        );
134    }
135
136    #[test]
137    fn max_length() {
138        const WINDOW_SIZE: usize = 1;
139        let data = repeat(42).take(MAX_LENGTH + 1).collect::<Vec<_>>();
140
141        assert_eq!(
142            data.iter()
143                .copied()
144                .compress::<{ WINDOW_SIZE + MAX_LENGTH }>()
145                .decompress::<WINDOW_SIZE>()
146                .collect::<Vec<_>>(),
147            data
148        );
149    }
150
151    #[test]
152    fn max_offset() {
153        const WINDOW_SIZE: usize = 128;
154        let data = repeat(0..128).take(2).flatten().collect::<Vec<_>>();
155
156        assert_eq!(
157            data.iter()
158                .copied()
159                .compress::<{ WINDOW_SIZE + MAX_LENGTH }>()
160                .decompress::<WINDOW_SIZE>()
161                .collect::<Vec<_>>(),
162            data
163        );
164    }
165
166    #[quickcheck]
167    fn random(data: Vec<u8>) -> bool {
168        let data = data.into_iter().map(|x| x >> 1).collect::<Vec<_>>();
169
170        data.iter()
171            .copied()
172            .compress::<{ WINDOW_SIZE + MAX_LENGTH }>()
173            .decompress::<WINDOW_SIZE>()
174            .collect::<Vec<_>>()
175            == data
176    }
177
178    #[quickcheck]
179    fn random_max(data: Vec<u8>) -> bool {
180        let data = data.into_iter().map(|x| x >> 1).collect::<Vec<_>>();
181
182        data.iter()
183            .copied()
184            .compress::<{ MAX_WINDOW_SIZE + MAX_LENGTH }>()
185            .decompress::<MAX_WINDOW_SIZE>()
186            .collect::<Vec<_>>()
187            == data
188    }
189}
stak_lzss/lib.rs

stak_lzss/
lib.rs
