1const MAXBITS: usize = 13;
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum BlastError {
33 OutOfInput,
35 BadLiteralFlag,
37 BadDictSize,
39 DistanceTooFar,
41 BadCode,
43 OutputLimit,
46}
47
48impl BlastError {
49 pub fn code(self) -> i32 {
50 match self {
51 BlastError::OutOfInput => 2,
52 BlastError::BadLiteralFlag => -1,
53 BlastError::BadDictSize => -2,
54 BlastError::DistanceTooFar => -3,
55 BlastError::BadCode => -9,
56 BlastError::OutputLimit => 1,
57 }
58 }
59}
60
61struct Huffman {
62 count: [u16; MAXBITS + 1],
63 symbol: [u16; 256],
64}
65
66fn construct(rep: &[u8]) -> Huffman {
68 let mut length = [0u8; 256];
69 let mut n = 0usize;
70 for &r in rep {
71 let len = r & 15;
72 for _ in 0..(r >> 4) + 1 {
73 length[n] = len;
74 n += 1;
75 }
76 }
77
78 let mut h = Huffman { count: [0; MAXBITS + 1], symbol: [0; 256] };
79 for &len in &length[..n] {
80 h.count[len as usize] += 1;
81 }
82
83 let mut offs = [0u16; MAXBITS + 1];
84 for len in 1..MAXBITS {
85 offs[len + 1] = offs[len] + h.count[len];
86 }
87 for (symbol, &len) in length[..n].iter().enumerate() {
88 if len != 0 {
89 h.symbol[offs[len as usize] as usize] = symbol as u16;
90 offs[len as usize] += 1;
91 }
92 }
93 h
94}
95
96const LITLEN: [u8; 98] = [
98 11, 124, 8, 7, 28, 7, 188, 13, 76, 4, 10, 8, 12, 10, 12, 10, 8, 23, 8, 9, 7, 6, 7, 8, 7, 6,
99 55, 8, 23, 24, 12, 11, 7, 9, 11, 12, 6, 7, 22, 5, 7, 24, 6, 11, 9, 6, 7, 22, 7, 11, 38, 7, 9,
100 8, 25, 11, 8, 11, 9, 12, 8, 12, 5, 38, 5, 38, 5, 11, 7, 5, 6, 21, 6, 10, 53, 8, 7, 24, 10, 27,
101 44, 253, 253, 253, 252, 252, 252, 13, 12, 45, 12, 45, 12, 61, 12, 45, 44, 173,
102];
103const LENLEN: [u8; 6] = [2, 35, 36, 53, 38, 23];
105const DISTLEN: [u8; 7] = [2, 20, 53, 230, 247, 151, 248];
107const BASE: [u32; 16] = [3, 2, 4, 5, 6, 7, 8, 9, 10, 12, 16, 24, 40, 72, 136, 264];
109const EXTRA: [u32; 16] = [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8];
111
112struct State<'a> {
113 input: &'a [u8],
114 pos: usize,
115 bitbuf: u32,
116 bitcnt: u32,
117}
118
119impl State<'_> {
120 #[inline]
121 fn next_byte(&mut self) -> Result<u32, BlastError> {
122 let b = *self.input.get(self.pos).ok_or(BlastError::OutOfInput)?;
123 self.pos += 1;
124 Ok(b as u32)
125 }
126
127 #[inline]
129 fn bits(&mut self, need: u32) -> Result<u32, BlastError> {
130 let mut val = self.bitbuf;
131 while self.bitcnt < need {
132 val |= self.next_byte()? << self.bitcnt;
133 self.bitcnt += 8;
134 }
135 self.bitbuf = val >> need;
136 self.bitcnt -= need;
137 Ok(val & ((1 << need) - 1))
138 }
139
140 #[inline]
143 fn decode(&mut self, h: &Huffman) -> Result<usize, BlastError> {
144 let mut bitbuf = self.bitbuf;
145 let mut left = self.bitcnt;
146 let mut code: i32 = 0;
147 let mut first: i32 = 0;
148 let mut index: i32 = 0;
149 let mut len: u32 = 1;
150 loop {
151 while left > 0 {
152 left -= 1;
153 code |= ((bitbuf & 1) ^ 1) as i32;
154 bitbuf >>= 1;
155 let count = h.count[len as usize] as i32;
156 if code < first + count {
157 self.bitbuf = bitbuf;
158 self.bitcnt = self.bitcnt.wrapping_sub(len) & 7;
159 return Ok(h.symbol[(index + (code - first)) as usize] as usize);
160 }
161 index += count;
162 first += count;
163 first <<= 1;
164 code <<= 1;
165 len += 1;
166 }
167 left = (MAXBITS as u32 + 1) - len;
168 if left == 0 {
169 break;
170 }
171 bitbuf = self.next_byte()?;
172 if left > 8 {
173 left = 8;
174 }
175 }
176 Err(BlastError::BadCode)
177 }
178}
179
180pub fn blast(input: &[u8], out: &mut Vec<u8>, max_out: usize) -> Result<(), BlastError> {
190 let litcode = construct(&LITLEN);
191 let lencode = construct(&LENLEN);
192 let distcode = construct(&DISTLEN);
193
194 let start = out.len();
195 let mut s = State { input, pos: 0, bitbuf: 0, bitcnt: 0 };
196
197 let lit = s.bits(8)?;
198 if lit > 1 {
199 return Err(BlastError::BadLiteralFlag);
200 }
201 let dict = s.bits(8)?;
202 if !(4..=6).contains(&dict) {
203 return Err(BlastError::BadDictSize);
204 }
205
206 loop {
207 if s.bits(1)? != 0 {
208 let symbol = s.decode(&lencode)?;
209 let len = (BASE[symbol] + s.bits(EXTRA[symbol])?) as usize;
210 if len == 519 {
211 break; }
213
214 let shift = if len == 2 { 2 } else { dict };
215 let mut dist = s.decode(&distcode)? << shift;
216 dist += s.bits(shift)? as usize;
217 dist += 1;
218
219 let produced = out.len() - start;
220 if dist > produced {
221 return Err(BlastError::DistanceTooFar);
222 }
223
224 let room = max_out - produced;
225 let over = len > room;
226 let len = len.min(room);
227 let from = out.len() - dist;
228 if dist >= len {
229 out.extend_from_within(from..from + len);
230 } else {
231 out.reserve(len);
233 for i in 0..len {
234 let b = out[from + i];
235 out.push(b);
236 }
237 }
238 if over {
239 return Err(BlastError::OutputLimit);
240 }
241 } else {
242 let symbol = if lit != 0 { s.decode(&litcode)? as u32 } else { s.bits(8)? };
243 if out.len() - start >= max_out {
244 return Err(BlastError::OutputLimit);
245 }
246 out.push(symbol as u8);
247 }
248 }
249 Ok(())
250}
251
252#[cfg(test)]
253mod tests {
254 use super::*;
255
256 #[test]
257 fn adler_example() {
258 let input = [0x00, 0x04, 0x82, 0x24, 0x25, 0x8f, 0x80, 0x7f];
260 let mut out = Vec::new();
261 blast(&input, &mut out, usize::MAX).unwrap();
262 assert_eq!(out, b"AIAIAIAIAIAIA");
263 }
264
265 #[test]
266 fn output_limit() {
267 let input = [0x00, 0x04, 0x82, 0x24, 0x25, 0x8f, 0x80, 0x7f];
268 for max in [0, 1, 2, 5, 12] {
269 let mut out = Vec::new();
270 assert_eq!(blast(&input, &mut out, max), Err(BlastError::OutputLimit));
271 assert_eq!(out, &b"AIAIAIAIAIAIA"[..max]);
272 }
273 let mut out = Vec::new();
274 assert_eq!(blast(&input, &mut out, 13), Ok(()));
275 }
276
277 #[test]
278 fn errors() {
279 let mut out = Vec::new();
280 assert_eq!(blast(&[], &mut out, usize::MAX), Err(BlastError::OutOfInput));
281 assert_eq!(blast(&[2, 4], &mut out, usize::MAX), Err(BlastError::BadLiteralFlag));
282 assert_eq!(blast(&[0, 7], &mut out, usize::MAX), Err(BlastError::BadDictSize));
283 assert_eq!(blast(&[0x00, 0x04, 0x82], &mut out, usize::MAX), Err(BlastError::OutOfInput));
284 assert_eq!(BlastError::OutOfInput.code(), 2);
285 }
286}