Skip to main content

datasus_core/
blast.rs

1//! Decompressor for PKWare Data Compression Library (DCL "implode") streams.
2//!
3//! This is a Rust port of `blast.c` 1.3 by Mark Adler (zlib `contrib/blast`),
4//! distributed under the zlib license:
5//!
6//! > Copyright (C) 2003, 2012, 2013 Mark Adler
7//! >
8//! > This software is provided 'as-is', without any express or implied
9//! > warranty.  In no event will the author be held liable for any damages
10//! > arising from the use of this software.
11//! >
12//! > Permission is granted to anyone to use this software for any purpose,
13//! > including commercial applications, and to alter it and redistribute it
14//! > freely, subject to the following restrictions:
15//! >
16//! > 1. The origin of this software must not be misrepresented; you must not
17//! >    claim that you wrote the original software. If you use this software
18//! >    in a product, an acknowledgment in the product documentation would be
19//! >    appreciated but is not required.
20//! > 2. Altered source versions must be plainly marked as such, and must not
21//! >    be misrepresented as being the original software.
22//! > 3. This notice may not be removed or altered from any source distribution.
23//!
24//! This file is an altered version: it was translated to Rust, works on
25//! in-memory slices instead of callbacks, and uses the output vector itself
26//! as the sliding window.
27
28const MAXBITS: usize = 13;
29
30/// Error codes follow `blast.c` so messages stay comparable with the C reader.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum BlastError {
33    /// Ran out of input before the end code (`blast()` code 2).
34    OutOfInput,
35    /// First byte (coded-literal flag) is not 0 or 1 (code -1).
36    BadLiteralFlag,
37    /// Dictionary size is not 4, 5 or 6 (code -2).
38    BadDictSize,
39    /// Distance points before the start of the output (code -3).
40    DistanceTooFar,
41    /// Invalid Huffman code (cannot happen with the fixed tables; code -9).
42    BadCode,
43    /// The output reached the caller's limit (`blast()` code 1, its output
44    /// error).  The output holds exactly the limit's worth of bytes.
45    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
66/// Build decoding tables from the compact (repeat, length) representation.
67fn 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
96/// Bit lengths of literal codes.
97const 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];
103/// Bit lengths of length codes 0..15.
104const LENLEN: [u8; 6] = [2, 35, 36, 53, 38, 23];
105/// Bit lengths of distance codes 0..63.
106const DISTLEN: [u8; 7] = [2, 20, 53, 230, 247, 151, 248];
107/// Base for length codes.
108const BASE: [u32; 16] = [3, 2, 4, 5, 6, 7, 8, 9, 10, 12, 16, 24, 40, 72, 136, 264];
109/// Extra bits for length codes.
110const 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    /// Return `need` (0..=8) bits from the stream, least significant first.
128    #[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    /// Decode one symbol.  Codes are stored bit-reversed and inverted; see
141    /// the format notes in `blast.c`.
142    #[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
180/// Decompress a PKWare DCL stream from `input`, appending at most `max_out`
181/// bytes to `out`.
182///
183/// The format can expand a few bytes into hundreds, so untrusted input
184/// needs a bound: when the stream would produce more than `max_out` bytes,
185/// decompression stops with [`BlastError::OutputLimit`].
186///
187/// Input after the end code is ignored.  On error, `out` holds whatever was
188/// decompressed so far.
189pub 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; // end code
212            }
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                // Overlapped copy: repeats the last `dist` bytes.
232                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        // From the header comment of blast.c.
259        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}