gzip_zero/
lib.rs

1#![doc = include_str!("../README.md")]
2#![no_std]
3#![forbid(unsafe_code)]
4
5use core::fmt;
6
7use miniz_oxide::inflate::core::{decompress, inflate_flags, DecompressorOxide};
8use miniz_oxide::inflate::TINFLStatus;
9
10/// Required size of the caller-owned DEFLATE history ring.
11pub const HISTORY_SIZE: usize = 32 * 1024;
12
13const FIXED_HEADER_SIZE: usize = 10;
14const TRAILER_SIZE: usize = 8;
15
16/// Buffers borrowed by a [`Decoder`].
17pub struct DecoderBuffers<'a> {
18    /// The DEFLATE history ring. It must contain exactly [`HISTORY_SIZE`] bytes.
19    pub history: &'a mut [u8],
20}
21
22/// Fixed fields from a gzip member header.
23#[derive(Clone, Copy, Debug, Eq, PartialEq)]
24pub struct MemberHeader {
25    pub modification_time: u32,
26    pub extra_flags: u8,
27    pub operating_system: u8,
28}
29
30/// Kind of progress made by one call to [`Decoder::decode`].
31#[derive(Debug, Eq, PartialEq)]
32pub enum DecodeStep<'a> {
33    NeedInput {
34        consumed: usize,
35    },
36    MemberStarted {
37        consumed: usize,
38        header: MemberHeader,
39    },
40    Output {
41        consumed: usize,
42        bytes: &'a [u8],
43    },
44    MemberFinished {
45        consumed: usize,
46    },
47}
48
49impl DecodeStep<'_> {
50    pub const fn consumed(&self) -> usize {
51        match self {
52            Self::NeedInput { consumed }
53            | Self::MemberStarted { consumed, .. }
54            | Self::Output { consumed, .. }
55            | Self::MemberFinished { consumed } => *consumed,
56        }
57    }
58}
59
60enum InternalStep {
61    NeedInput {
62        consumed: usize,
63    },
64    MemberStarted {
65        consumed: usize,
66        header: MemberHeader,
67    },
68    Output {
69        consumed: usize,
70        start: usize,
71        end: usize,
72    },
73    MemberFinished {
74        consumed: usize,
75    },
76}
77
78/// A malformed stream or invalid decoder configuration.
79#[derive(Clone, Copy, Debug, Eq, PartialEq)]
80pub enum DecodeError {
81    InvalidHistorySize { actual: usize },
82    InvalidHeader,
83    UnsupportedCompressionMethod { method: u8 },
84    InvalidHeaderChecksum,
85    InvalidDeflateStream,
86    InvalidDataChecksum { expected: u32, actual: u32 },
87    InvalidDataSize { expected: u32, actual: u32 },
88    UnexpectedEof,
89    DecoderPoisoned,
90}
91
92impl fmt::Display for DecodeError {
93    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
94        match self {
95            Self::InvalidHistorySize { actual } => write!(
96                formatter,
97                "gzip history must contain {HISTORY_SIZE} bytes, got {actual}"
98            ),
99            Self::InvalidHeader => formatter.write_str("invalid gzip header"),
100            Self::UnsupportedCompressionMethod { method } => {
101                write!(formatter, "unsupported gzip compression method {method}")
102            }
103            Self::InvalidHeaderChecksum => formatter.write_str("gzip header checksum mismatch"),
104            Self::InvalidDeflateStream => formatter.write_str("invalid DEFLATE stream"),
105            Self::InvalidDataChecksum { expected, actual } => write!(
106                formatter,
107                "gzip data checksum mismatch: expected {expected:08x}, got {actual:08x}"
108            ),
109            Self::InvalidDataSize { expected, actual } => write!(
110                formatter,
111                "gzip data size mismatch: expected {expected}, got {actual}"
112            ),
113            Self::UnexpectedEof => formatter.write_str("unexpected end of gzip stream"),
114            Self::DecoderPoisoned => formatter.write_str("gzip decoder is poisoned"),
115        }
116    }
117}
118
119#[derive(Clone, Copy, Debug, Eq, PartialEq)]
120enum State {
121    Header,
122    ExtraLength,
123    Extra,
124    Name,
125    Comment,
126    HeaderChecksum,
127    StartDeflate,
128    Deflate,
129    Trailer,
130}
131
132/// Allocation-free incremental gzip decoder.
133pub struct Decoder<'a> {
134    history: &'a mut [u8],
135    decompressor: DecompressorOxide,
136    state: State,
137    poisoned: bool,
138    completed_members: u64,
139    fixed: [u8; FIXED_HEADER_SIZE],
140    fixed_len: usize,
141    small: [u8; TRAILER_SIZE],
142    small_len: usize,
143    flags: u8,
144    extra_remaining: usize,
145    header_crc: u32,
146    data_crc: u32,
147    data_size: u32,
148    output_position: usize,
149    header: MemberHeader,
150}
151
152impl<'a> Decoder<'a> {
153    pub fn new(buffers: DecoderBuffers<'a>) -> Result<Self, DecodeError> {
154        if buffers.history.len() != HISTORY_SIZE {
155            return Err(DecodeError::InvalidHistorySize {
156                actual: buffers.history.len(),
157            });
158        }
159        buffers.history.fill(0);
160        Ok(Self {
161            history: buffers.history,
162            decompressor: DecompressorOxide::new(),
163            state: State::Header,
164            poisoned: false,
165            completed_members: 0,
166            fixed: [0; FIXED_HEADER_SIZE],
167            fixed_len: 0,
168            small: [0; TRAILER_SIZE],
169            small_len: 0,
170            flags: 0,
171            extra_remaining: 0,
172            header_crc: !0,
173            data_crc: !0,
174            data_size: 0,
175            output_position: 0,
176            header: MemberHeader {
177                modification_time: 0,
178                extra_flags: 0,
179                operating_system: 0,
180            },
181        })
182    }
183
184    pub fn decode<'decoder>(
185        &'decoder mut self,
186        input: &[u8],
187    ) -> Result<DecodeStep<'decoder>, DecodeError> {
188        if self.poisoned {
189            return Err(DecodeError::DecoderPoisoned);
190        }
191        let step = match self.decode_inner(input) {
192            Ok(step) => step,
193            Err(error) => {
194                self.poisoned = true;
195                return Err(error);
196            }
197        };
198        Ok(match step {
199            InternalStep::NeedInput { consumed } => DecodeStep::NeedInput { consumed },
200            InternalStep::MemberStarted { consumed, header } => {
201                DecodeStep::MemberStarted { consumed, header }
202            }
203            InternalStep::Output {
204                consumed,
205                start,
206                end,
207            } => DecodeStep::Output {
208                consumed,
209                bytes: &self.history[start..end],
210            },
211            InternalStep::MemberFinished { consumed } => DecodeStep::MemberFinished { consumed },
212        })
213    }
214
215    pub fn finish(&self) -> Result<(), DecodeError> {
216        if self.poisoned {
217            return Err(DecodeError::DecoderPoisoned);
218        }
219        if self.completed_members != 0
220            && self.state == State::Header
221            && self.fixed_len == 0
222            && self.small_len == 0
223        {
224            Ok(())
225        } else {
226            Err(DecodeError::UnexpectedEof)
227        }
228    }
229
230    pub fn reset(&mut self) {
231        self.decompressor.init();
232        self.history.fill(0);
233        self.state = State::Header;
234        self.poisoned = false;
235        self.completed_members = 0;
236        self.fixed_len = 0;
237        self.small_len = 0;
238        self.flags = 0;
239        self.extra_remaining = 0;
240        self.header_crc = !0;
241        self.data_crc = !0;
242        self.data_size = 0;
243        self.output_position = 0;
244    }
245
246    fn decode_inner(&mut self, input: &[u8]) -> Result<InternalStep, DecodeError> {
247        let mut position = 0;
248        loop {
249            match self.state {
250                State::Header => {
251                    let copied =
252                        copy_into(&mut self.fixed, &mut self.fixed_len, &input[position..]);
253                    self.header_crc =
254                        crc32_update(self.header_crc, &input[position..position + copied]);
255                    position += copied;
256                    if self.fixed_len != FIXED_HEADER_SIZE {
257                        return Ok(InternalStep::NeedInput { consumed: position });
258                    }
259                    if self.fixed[0..2] != [0x1f, 0x8b] || self.fixed[3] & 0xe0 != 0 {
260                        return Err(DecodeError::InvalidHeader);
261                    }
262                    if self.fixed[2] != 8 {
263                        return Err(DecodeError::UnsupportedCompressionMethod {
264                            method: self.fixed[2],
265                        });
266                    }
267                    self.flags = self.fixed[3];
268                    self.header = MemberHeader {
269                        modification_time: u32::from_le_bytes([
270                            self.fixed[4],
271                            self.fixed[5],
272                            self.fixed[6],
273                            self.fixed[7],
274                        ]),
275                        extra_flags: self.fixed[8],
276                        operating_system: self.fixed[9],
277                    };
278                    self.fixed_len = 0;
279                    self.small_len = 0;
280                    self.state = self.next_optional_state();
281                }
282                State::ExtraLength => {
283                    let copied = copy_into(
284                        &mut self.small[..2],
285                        &mut self.small_len,
286                        &input[position..],
287                    );
288                    self.header_crc =
289                        crc32_update(self.header_crc, &input[position..position + copied]);
290                    position += copied;
291                    if self.small_len != 2 {
292                        return Ok(InternalStep::NeedInput { consumed: position });
293                    }
294                    self.extra_remaining =
295                        u16::from_le_bytes([self.small[0], self.small[1]]) as usize;
296                    self.small_len = 0;
297                    self.state = if self.extra_remaining == 0 {
298                        self.after_extra()
299                    } else {
300                        State::Extra
301                    };
302                }
303                State::Extra => {
304                    let length = self.extra_remaining.min(input.len() - position);
305                    self.header_crc =
306                        crc32_update(self.header_crc, &input[position..position + length]);
307                    position += length;
308                    self.extra_remaining -= length;
309                    if self.extra_remaining != 0 {
310                        return Ok(InternalStep::NeedInput { consumed: position });
311                    }
312                    self.state = self.after_extra();
313                }
314                State::Name | State::Comment => {
315                    let remaining = &input[position..];
316                    let Some(end) = remaining.iter().position(|byte| *byte == 0) else {
317                        self.header_crc = crc32_update(self.header_crc, remaining);
318                        return Ok(InternalStep::NeedInput {
319                            consumed: input.len(),
320                        });
321                    };
322                    let length = end + 1;
323                    self.header_crc = crc32_update(self.header_crc, &remaining[..length]);
324                    position += length;
325                    self.state = if self.state == State::Name {
326                        self.after_name()
327                    } else {
328                        self.after_comment()
329                    };
330                }
331                State::HeaderChecksum => {
332                    let copied = copy_into(
333                        &mut self.small[..2],
334                        &mut self.small_len,
335                        &input[position..],
336                    );
337                    position += copied;
338                    if self.small_len != 2 {
339                        return Ok(InternalStep::NeedInput { consumed: position });
340                    }
341                    let expected = u16::from_le_bytes([self.small[0], self.small[1]]);
342                    let actual = (!self.header_crc) as u16;
343                    if expected != actual {
344                        return Err(DecodeError::InvalidHeaderChecksum);
345                    }
346                    self.small_len = 0;
347                    self.start_deflate();
348                    return Ok(InternalStep::MemberStarted {
349                        consumed: position,
350                        header: self.header,
351                    });
352                }
353                State::StartDeflate => {
354                    self.start_deflate();
355                    return Ok(InternalStep::MemberStarted {
356                        consumed: position,
357                        header: self.header,
358                    });
359                }
360                State::Deflate => {
361                    let start = self.output_position;
362                    let (status, consumed, written) = decompress(
363                        &mut self.decompressor,
364                        &input[position..],
365                        self.history,
366                        start,
367                        inflate_flags::TINFL_FLAG_HAS_MORE_INPUT,
368                    );
369                    position += consumed;
370                    let end = start + written;
371                    self.data_crc = crc32_update(self.data_crc, &self.history[start..end]);
372                    self.data_size = self.data_size.wrapping_add(written as u32);
373                    self.output_position = if end == self.history.len() { 0 } else { end };
374                    match status {
375                        TINFLStatus::Done => self.state = State::Trailer,
376                        TINFLStatus::HasMoreOutput | TINFLStatus::NeedsMoreInput => {}
377                        _ => return Err(DecodeError::InvalidDeflateStream),
378                    }
379                    if written != 0 {
380                        return Ok(InternalStep::Output {
381                            consumed: position,
382                            start,
383                            end,
384                        });
385                    }
386                    match status {
387                        TINFLStatus::Done => {}
388                        TINFLStatus::NeedsMoreInput => {
389                            return Ok(InternalStep::NeedInput { consumed: position });
390                        }
391                        TINFLStatus::HasMoreOutput => {
392                            return Err(DecodeError::InvalidDeflateStream);
393                        }
394                        _ => unreachable!(),
395                    }
396                }
397                State::Trailer => {
398                    let copied =
399                        copy_into(&mut self.small, &mut self.small_len, &input[position..]);
400                    position += copied;
401                    if self.small_len != TRAILER_SIZE {
402                        return Ok(InternalStep::NeedInput { consumed: position });
403                    }
404                    let expected_crc = u32::from_le_bytes([
405                        self.small[0],
406                        self.small[1],
407                        self.small[2],
408                        self.small[3],
409                    ]);
410                    let actual_crc = !self.data_crc;
411                    if expected_crc != actual_crc {
412                        return Err(DecodeError::InvalidDataChecksum {
413                            expected: expected_crc,
414                            actual: actual_crc,
415                        });
416                    }
417                    let expected_size = u32::from_le_bytes([
418                        self.small[4],
419                        self.small[5],
420                        self.small[6],
421                        self.small[7],
422                    ]);
423                    if expected_size != self.data_size {
424                        return Err(DecodeError::InvalidDataSize {
425                            expected: expected_size,
426                            actual: self.data_size,
427                        });
428                    }
429                    self.completed_members += 1;
430                    self.small_len = 0;
431                    self.state = State::Header;
432                    self.header_crc = !0;
433                    return Ok(InternalStep::MemberFinished { consumed: position });
434                }
435            }
436
437            if position == input.len() {
438                return Ok(InternalStep::NeedInput { consumed: position });
439            }
440        }
441    }
442
443    fn next_optional_state(&self) -> State {
444        if self.flags & 0x04 != 0 {
445            State::ExtraLength
446        } else {
447            self.after_extra()
448        }
449    }
450
451    fn after_extra(&self) -> State {
452        if self.flags & 0x08 != 0 {
453            State::Name
454        } else {
455            self.after_name()
456        }
457    }
458
459    fn after_name(&self) -> State {
460        if self.flags & 0x10 != 0 {
461            State::Comment
462        } else {
463            self.after_comment()
464        }
465    }
466
467    fn after_comment(&self) -> State {
468        if self.flags & 0x02 != 0 {
469            State::HeaderChecksum
470        } else {
471            State::StartDeflate
472        }
473    }
474
475    fn start_deflate(&mut self) {
476        self.decompressor.init();
477        self.history.fill(0);
478        self.data_crc = !0;
479        self.data_size = 0;
480        self.output_position = 0;
481        self.state = State::Deflate;
482    }
483}
484
485fn copy_into(destination: &mut [u8], filled: &mut usize, input: &[u8]) -> usize {
486    let length = input.len().min(destination.len() - *filled);
487    destination[*filled..*filled + length].copy_from_slice(&input[..length]);
488    *filled += length;
489    length
490}
491
492fn crc32_update(mut crc: u32, bytes: &[u8]) -> u32 {
493    for byte in bytes {
494        crc = CRC32_TABLE[((crc ^ u32::from(*byte)) & 0xff) as usize] ^ (crc >> 8);
495    }
496    crc
497}
498
499const fn crc32_table() -> [u32; 256] {
500    let mut table = [0u32; 256];
501    let mut index = 0;
502    while index < table.len() {
503        let mut value = index as u32;
504        let mut bit = 0;
505        while bit < 8 {
506            value = if value & 1 == 0 {
507                value >> 1
508            } else {
509                0xedb8_8320 ^ (value >> 1)
510            };
511            bit += 1;
512        }
513        table[index] = value;
514        index += 1;
515    }
516    table
517}
518
519const CRC32_TABLE: [u32; 256] = crc32_table();
gzip_zero/lib.rs

gzip_zero/
lib.rs
