use super::*;
use crate::shared::{update_adler32, HUFFMAN_LENGTH_ORDER};
use ::core::convert::TryInto;
use ::core::{cmp, slice};
use self::output_buffer::OutputBuffer;
pub const TINFL_LZ_DICT_SIZE: usize = 32_768;
struct HuffmanTable {
pub code_size: [u8; MAX_HUFF_SYMBOLS_0],
pub look_up: [i16; FAST_LOOKUP_SIZE as usize],
pub tree: [i16; MAX_HUFF_TREE_SIZE],
}
impl HuffmanTable {
const fn new() -> HuffmanTable {
HuffmanTable {
code_size: [0; MAX_HUFF_SYMBOLS_0],
look_up: [0; FAST_LOOKUP_SIZE as usize],
tree: [0; MAX_HUFF_TREE_SIZE],
}
}
#[inline]
fn fast_lookup(&self, bit_buf: BitBuffer) -> i16 {
self.look_up[(bit_buf & BitBuffer::from(FAST_LOOKUP_SIZE - 1)) as usize]
}
#[inline]
fn tree_lookup(&self, fast_symbol: i32, bit_buf: BitBuffer, mut code_len: u32) -> (i32, u32) {
let mut symbol = fast_symbol;
loop {
symbol = i32::from(self.tree[(!symbol + ((bit_buf >> code_len) & 1) as i32) as usize]);
code_len += 1;
if symbol >= 0 {
break;
}
}
(symbol, code_len)
}
#[inline]
fn lookup(&self, bit_buf: BitBuffer) -> Option<(i32, u32)> {
let symbol = self.fast_lookup(bit_buf).into();
if symbol >= 0 {
if (symbol >> 9) as u32 != 0 {
Some((symbol, (symbol >> 9) as u32))
} else {
None
}
} else {
Some(self.tree_lookup(symbol, bit_buf, FAST_LOOKUP_BITS.into()))
}
}
}
const MAX_HUFF_TABLES: usize = 3;
const MAX_HUFF_SYMBOLS_0: usize = 288;
const MAX_HUFF_SYMBOLS_1: usize = 32;
const _MAX_HUFF_SYMBOLS_2: usize = 19;
const FAST_LOOKUP_BITS: u8 = 10;
const FAST_LOOKUP_SIZE: u32 = 1 << FAST_LOOKUP_BITS;
const MAX_HUFF_TREE_SIZE: usize = MAX_HUFF_SYMBOLS_0 * 2;
const LITLEN_TABLE: usize = 0;
const DIST_TABLE: usize = 1;
const HUFFLEN_TABLE: usize = 2;
pub mod inflate_flags {
pub const TINFL_FLAG_PARSE_ZLIB_HEADER: u32 = 1;
pub const TINFL_FLAG_HAS_MORE_INPUT: u32 = 2;
pub const TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF: u32 = 4;
pub const TINFL_FLAG_COMPUTE_ADLER32: u32 = 8;
}
use self::inflate_flags::*;
const MIN_TABLE_SIZES: [u16; 3] = [257, 1, 4];
#[cfg(target_pointer_width = "64")]
type BitBuffer = u64;
#[cfg(not(target_pointer_width = "64"))]
type BitBuffer = u32;
pub struct DecompressorOxide {
state: core::State,
num_bits: u32,
z_header0: u32,
z_header1: u32,
z_adler32: u32,
finish: u32,
block_type: u32,
check_adler32: u32,
dist: u32,
counter: u32,
num_extra: u32,
table_sizes: [u32; MAX_HUFF_TABLES],
bit_buf: BitBuffer,
tables: [HuffmanTable; MAX_HUFF_TABLES],
raw_header: [u8; 4],
len_codes: [u8; MAX_HUFF_SYMBOLS_0 + MAX_HUFF_SYMBOLS_1 + 137],
}
impl DecompressorOxide {
pub fn new() -> DecompressorOxide {
DecompressorOxide::default()
}
#[inline]
pub fn init(&mut self) {
self.state = core::State::Start;
}
#[inline]
pub fn adler32(&self) -> Option<u32> {
if self.state != State::Start && !self.state.is_failure() && self.z_header0 != 0 {
Some(self.check_adler32)
} else {
None
}
}
}
impl Default for DecompressorOxide {
#[inline(always)]
fn default() -> Self {
DecompressorOxide {
state: core::State::Start,
num_bits: 0,
z_header0: 0,
z_header1: 0,
z_adler32: 0,
finish: 0,
block_type: 0,
check_adler32: 0,
dist: 0,
counter: 0,
num_extra: 0,
table_sizes: [0; MAX_HUFF_TABLES],
bit_buf: 0,
tables: [
HuffmanTable::new(),
HuffmanTable::new(),
HuffmanTable::new(),
],
raw_header: [0; 4],
len_codes: [0; MAX_HUFF_SYMBOLS_0 + MAX_HUFF_SYMBOLS_1 + 137],
}
}
}
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
enum State {
Start = 0,
ReadZlibCmf,
ReadZlibFlg,
ReadBlockHeader,
BlockTypeNoCompression,
RawHeader,
RawMemcpy1,
RawMemcpy2,
ReadTableSizes,
ReadHufflenTableCodeSize,
ReadLitlenDistTablesCodeSize,
ReadExtraBitsCodeSize,
DecodeLitlen,
WriteSymbol,
ReadExtraBitsLitlen,
DecodeDistance,
ReadExtraBitsDistance,
RawReadFirstByte,
RawStoreFirstByte,
WriteLenBytesToEnd,
BlockDone,
HuffDecodeOuterLoop1,
HuffDecodeOuterLoop2,
ReadAdler32,
DoneForever,
BlockTypeUnexpected,
BadCodeSizeSum,
BadTotalSymbols,
BadZlibHeader,
DistanceOutOfBounds,
BadRawLength,
BadCodeSizeDistPrevLookup,
InvalidLitlen,
InvalidDist,
InvalidCodeLen,
}
impl State {
fn is_failure(self) -> bool {
match self {
BlockTypeUnexpected => true,
BadCodeSizeSum => true,
BadTotalSymbols => true,
BadZlibHeader => true,
DistanceOutOfBounds => true,
BadRawLength => true,
BadCodeSizeDistPrevLookup => true,
InvalidLitlen => true,
InvalidDist => true,
_ => false,
}
}
#[inline]
fn begin(&mut self, new_state: State) {
*self = new_state;
}
}
use self::State::*;
#[rustfmt::skip]
const LENGTH_BASE: [u16; 32] = [
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 512, 512, 512
];
#[rustfmt::skip]
const LENGTH_EXTRA: [u8; 32] = [
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 0, 0, 0
];
#[rustfmt::skip]
const DIST_BASE: [u16; 32] = [
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33,
49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537,
2049, 3073, 4097, 6145, 8193, 12_289, 16_385, 24_577, 32_768, 32_768
];
#[rustfmt::skip]
const DIST_EXTRA: [u8; 32] = [
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 13, 13
];
const BASE_EXTRA_MASK: usize = 32 - 1;
#[inline]
fn memset<T: Copy>(slice: &mut [T], val: T) {
for x in slice {
*x = val
}
}
#[inline]
fn read_u16_le(iter: &mut slice::Iter<u8>) -> u16 {
let ret = {
let two_bytes = iter.as_ref()[..2].try_into().unwrap();
u16::from_le_bytes(two_bytes)
};
iter.nth(1);
ret
}
#[inline(always)]
#[cfg(target_pointer_width = "64")]
fn read_u32_le(iter: &mut slice::Iter<u8>) -> u32 {
let ret = {
let four_bytes: [u8; 4] = iter.as_ref()[..4].try_into().unwrap();
u32::from_le_bytes(four_bytes)
};
iter.nth(3);
ret
}
#[inline(always)]
#[cfg(target_pointer_width = "64")]
fn fill_bit_buffer(l: &mut LocalVars, in_iter: &mut slice::Iter<u8>) {
if l.num_bits < 30 {
l.bit_buf |= BitBuffer::from(read_u32_le(in_iter)) << l.num_bits;
l.num_bits += 32;
}
}
#[inline(always)]
#[cfg(not(target_pointer_width = "64"))]
fn fill_bit_buffer(l: &mut LocalVars, in_iter: &mut slice::Iter<u8>) {
if l.num_bits < 15 {
l.bit_buf |= BitBuffer::from(read_u16_le(in_iter)) << l.num_bits;
l.num_bits += 16;
}
}
#[inline]
fn validate_zlib_header(cmf: u32, flg: u32, flags: u32, mask: usize) -> Action {
let mut failed =
(((cmf * 256) + flg) % 31 != 0) ||
((flg & 0b0010_0000) != 0) ||
((cmf & 15) != 8);
let window_size = 1 << ((cmf >> 4) + 8);
if (flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF) == 0 {
failed |= (mask + 1) < window_size;
}
failed |= window_size > 32_768;
if failed {
Action::Jump(BadZlibHeader)
} else {
Action::Jump(ReadBlockHeader)
}
}
enum Action {
None,
Jump(State),
End(TINFLStatus),
}
fn decode_huffman_code<F>(
r: &mut DecompressorOxide,
l: &mut LocalVars,
table: usize,
flags: u32,
in_iter: &mut slice::Iter<u8>,
f: F,
) -> Action
where
F: FnOnce(&mut DecompressorOxide, &mut LocalVars, i32) -> Action,
{
if l.num_bits < 15 {
if in_iter.len() < 2 {
loop {
let mut temp = i32::from(r.tables[table].fast_lookup(l.bit_buf));
if temp >= 0 {
let code_len = (temp >> 9) as u32;
if (code_len != 0) && (l.num_bits >= code_len) {
break;
}
} else if l.num_bits > FAST_LOOKUP_BITS.into() {
let mut code_len = u32::from(FAST_LOOKUP_BITS);
loop {
temp = i32::from(
r.tables[table].tree
[(!temp + ((l.bit_buf >> code_len) & 1) as i32) as usize],
);
code_len += 1;
if temp >= 0 || l.num_bits < code_len + 1 {
break;
}
}
if temp >= 0 {
break;
}
}
let mut byte = 0;
if let a @ Action::End(_) = read_byte(in_iter, flags, |b| {
byte = b;
Action::None
}) {
return a;
};
l.bit_buf |= BitBuffer::from(byte) << l.num_bits;
l.num_bits += 8;
if l.num_bits >= 15 {
break;
}
}
} else {
l.bit_buf |= BitBuffer::from(read_u16_le(in_iter)) << l.num_bits;
l.num_bits += 16;
}
}
let mut symbol = i32::from(r.tables[table].fast_lookup(l.bit_buf));
let code_len;
if symbol >= 0 {
code_len = (symbol >> 9) as u32;
symbol &= 511;
} else {
let res = r.tables[table].tree_lookup(symbol, l.bit_buf, u32::from(FAST_LOOKUP_BITS));
symbol = res.0;
code_len = res.1 as u32;
};
if code_len == 0 {
return Action::Jump(InvalidCodeLen);
}
l.bit_buf >>= code_len as u32;
l.num_bits -= code_len;
f(r, l, symbol)
}
#[inline]
fn read_byte<F>(in_iter: &mut slice::Iter<u8>, flags: u32, f: F) -> Action
where
F: FnOnce(u8) -> Action,
{
match in_iter.next() {
None => end_of_input(flags),
Some(&byte) => f(byte),
}
}
#[inline]
#[allow(clippy::while_immutable_condition)]
fn read_bits<F>(
l: &mut LocalVars,
amount: u32,
in_iter: &mut slice::Iter<u8>,
flags: u32,
f: F,
) -> Action
where
F: FnOnce(&mut LocalVars, BitBuffer) -> Action,
{
while l.num_bits < amount {
match read_byte(in_iter, flags, |byte| {
l.bit_buf |= BitBuffer::from(byte) << l.num_bits;
l.num_bits += 8;
Action::None
}) {
Action::None => (),
action => return action,
}
}
let bits = l.bit_buf & ((1 << amount) - 1);
l.bit_buf >>= amount;
l.num_bits -= amount;
f(l, bits)
}
#[inline]
fn pad_to_bytes<F>(l: &mut LocalVars, in_iter: &mut slice::Iter<u8>, flags: u32, f: F) -> Action
where
F: FnOnce(&mut LocalVars) -> Action,
{
let num_bits = l.num_bits & 7;
read_bits(l, num_bits, in_iter, flags, |l, _| f(l))
}
#[inline]
fn end_of_input(flags: u32) -> Action {
Action::End(if flags & TINFL_FLAG_HAS_MORE_INPUT != 0 {
TINFLStatus::NeedsMoreInput
} else {
TINFLStatus::FailedCannotMakeProgress
})
}
#[inline]
fn undo_bytes(l: &mut LocalVars, max: u32) -> u32 {
let res = cmp::min(l.num_bits >> 3, max);
l.num_bits -= res << 3;
res
}
fn start_static_table(r: &mut DecompressorOxide) {
r.table_sizes[LITLEN_TABLE] = 288;
r.table_sizes[DIST_TABLE] = 32;
memset(&mut r.tables[LITLEN_TABLE].code_size[0..144], 8);
memset(&mut r.tables[LITLEN_TABLE].code_size[144..256], 9);
memset(&mut r.tables[LITLEN_TABLE].code_size[256..280], 7);
memset(&mut r.tables[LITLEN_TABLE].code_size[280..288], 8);
memset(&mut r.tables[DIST_TABLE].code_size[0..32], 5);
}
fn init_tree(r: &mut DecompressorOxide, l: &mut LocalVars) -> Action {
loop {
let table = &mut r.tables[r.block_type as usize];
let table_size = r.table_sizes[r.block_type as usize] as usize;
let mut total_symbols = [0u32; 16];
let mut next_code = [0u32; 17];
memset(&mut table.look_up[..], 0);
memset(&mut table.tree[..], 0);
for &code_size in &table.code_size[..table_size] {
total_symbols[code_size as usize] += 1;
}
let mut used_symbols = 0;
let mut total = 0;
for i in 1..16 {
used_symbols += total_symbols[i];
total += total_symbols[i];
total <<= 1;
next_code[i + 1] = total;
}
if total != 65_536 && used_symbols > 1 {
return Action::Jump(BadTotalSymbols);
}
let mut tree_next = -1;
for symbol_index in 0..table_size {
let mut rev_code = 0;
let code_size = table.code_size[symbol_index];
if code_size == 0 {
continue;
}
let mut cur_code = next_code[code_size as usize];
next_code[code_size as usize] += 1;
for _ in 0..code_size {
rev_code = (rev_code << 1) | (cur_code & 1);
cur_code >>= 1;
}
if code_size <= FAST_LOOKUP_BITS {
let k = (i16::from(code_size) << 9) | symbol_index as i16;
while rev_code < FAST_LOOKUP_SIZE {
table.look_up[rev_code as usize] = k;
rev_code += 1 << code_size;
}
continue;
}
let mut tree_cur = table.look_up[(rev_code & (FAST_LOOKUP_SIZE - 1)) as usize];
if tree_cur == 0 {
table.look_up[(rev_code & (FAST_LOOKUP_SIZE - 1)) as usize] = tree_next as i16;
tree_cur = tree_next;
tree_next -= 2;
}
rev_code >>= FAST_LOOKUP_BITS - 1;
for _ in FAST_LOOKUP_BITS + 1..code_size {
rev_code >>= 1;
tree_cur -= (rev_code & 1) as i16;
if table.tree[(-tree_cur - 1) as usize] == 0 {
table.tree[(-tree_cur - 1) as usize] = tree_next as i16;
tree_cur = tree_next;
tree_next -= 2;
} else {
tree_cur = table.tree[(-tree_cur - 1) as usize];
}
}
rev_code >>= 1;
tree_cur -= (rev_code & 1) as i16;
table.tree[(-tree_cur - 1) as usize] = symbol_index as i16;
}
if r.block_type == 2 {
l.counter = 0;
return Action::Jump(ReadLitlenDistTablesCodeSize);
}
if r.block_type == 0 {
break;
}
r.block_type -= 1;
}
l.counter = 0;
Action::Jump(DecodeLitlen)
}
macro_rules! generate_state {
($state: ident, $state_machine: tt, $f: expr) => {
loop {
match $f {
Action::None => continue,
Action::Jump(new_state) => {
$state = new_state;
continue $state_machine;
},
Action::End(result) => break $state_machine result,
}
}
};
}
#[derive(Copy, Clone)]
struct LocalVars {
pub bit_buf: BitBuffer,
pub num_bits: u32,
pub dist: u32,
pub counter: u32,
pub num_extra: u32,
}
#[inline]
fn transfer(
out_slice: &mut [u8],
mut source_pos: usize,
mut out_pos: usize,
match_len: usize,
out_buf_size_mask: usize,
) {
for _ in 0..match_len >> 2 {
out_slice[out_pos] = out_slice[source_pos & out_buf_size_mask];
out_slice[out_pos + 1] = out_slice[(source_pos + 1) & out_buf_size_mask];
out_slice[out_pos + 2] = out_slice[(source_pos + 2) & out_buf_size_mask];
out_slice[out_pos + 3] = out_slice[(source_pos + 3) & out_buf_size_mask];
source_pos += 4;
out_pos += 4;
}
match match_len & 3 {
0 => (),
1 => out_slice[out_pos] = out_slice[source_pos & out_buf_size_mask],
2 => {
out_slice[out_pos] = out_slice[source_pos & out_buf_size_mask];
out_slice[out_pos + 1] = out_slice[(source_pos + 1) & out_buf_size_mask];
}
3 => {
out_slice[out_pos] = out_slice[source_pos & out_buf_size_mask];
out_slice[out_pos + 1] = out_slice[(source_pos + 1) & out_buf_size_mask];
out_slice[out_pos + 2] = out_slice[(source_pos + 2) & out_buf_size_mask];
}
_ => unreachable!(),
}
}
#[inline]
fn apply_match(
out_slice: &mut [u8],
out_pos: usize,
dist: usize,
match_len: usize,
out_buf_size_mask: usize,
) {
debug_assert!(out_pos + match_len <= out_slice.len());
let source_pos = out_pos.wrapping_sub(dist) & out_buf_size_mask;
if match_len == 3 {
out_slice[out_pos] = out_slice[source_pos];
out_slice[out_pos + 1] = out_slice[(source_pos + 1) & out_buf_size_mask];
out_slice[out_pos + 2] = out_slice[(source_pos + 2) & out_buf_size_mask];
return;
}
if cfg!(not(any(target_arch = "x86", target_arch = "x86_64"))) {
transfer(out_slice, source_pos, out_pos, match_len, out_buf_size_mask);
return;
}
if source_pos >= out_pos && (source_pos - out_pos) < match_len {
transfer(out_slice, source_pos, out_pos, match_len, out_buf_size_mask);
} else if match_len <= dist && source_pos + match_len < out_slice.len() {
if source_pos < out_pos {
let (from_slice, to_slice) = out_slice.split_at_mut(out_pos);
to_slice[..match_len].copy_from_slice(&from_slice[source_pos..source_pos + match_len]);
} else {
let (to_slice, from_slice) = out_slice.split_at_mut(source_pos);
to_slice[out_pos..out_pos + match_len].copy_from_slice(&from_slice[..match_len]);
}
} else {
transfer(out_slice, source_pos, out_pos, match_len, out_buf_size_mask);
}
}
fn decompress_fast(
r: &mut DecompressorOxide,
mut in_iter: &mut slice::Iter<u8>,
out_buf: &mut OutputBuffer,
flags: u32,
local_vars: &mut LocalVars,
out_buf_size_mask: usize,
) -> (TINFLStatus, State) {
let mut l = *local_vars;
let mut state;
let status: TINFLStatus = 'o: loop {
state = State::DecodeLitlen;
loop {
if out_buf.bytes_left() < 259 || in_iter.len() < 14 {
state = State::DecodeLitlen;
break 'o TINFLStatus::Done;
}
fill_bit_buffer(&mut l, &mut in_iter);
if let Some((symbol, code_len)) = r.tables[LITLEN_TABLE].lookup(l.bit_buf) {
l.counter = symbol as u32;
l.bit_buf >>= code_len;
l.num_bits -= code_len;
if (l.counter & 256) != 0 {
break;
} else {
if cfg!(not(target_pointer_width = "64")) {
fill_bit_buffer(&mut l, &mut in_iter);
}
if let Some((symbol, code_len)) = r.tables[LITLEN_TABLE].lookup(l.bit_buf) {
l.bit_buf >>= code_len;
l.num_bits -= code_len;
out_buf.write_byte(l.counter as u8);
if (symbol & 256) != 0 {
l.counter = symbol as u32;
break;
} else {
out_buf.write_byte(symbol as u8);
}
} else {
state.begin(InvalidCodeLen);
break 'o TINFLStatus::Failed;
}
}
} else {
state.begin(InvalidCodeLen);
break 'o TINFLStatus::Failed;
}
}
l.counter &= 511;
if l.counter == 256 {
state.begin(BlockDone);
break 'o TINFLStatus::Done;
} else if l.counter > 285 {
state.begin(InvalidLitlen);
break 'o TINFLStatus::Failed;
} else {
l.num_extra = u32::from(LENGTH_EXTRA[(l.counter - 257) as usize & BASE_EXTRA_MASK]);
l.counter = u32::from(LENGTH_BASE[(l.counter - 257) as usize & BASE_EXTRA_MASK]);
fill_bit_buffer(&mut l, &mut in_iter);
if l.num_extra != 0 {
let extra_bits = l.bit_buf & ((1 << l.num_extra) - 1);
l.bit_buf >>= l.num_extra;
l.num_bits -= l.num_extra;
l.counter += extra_bits as u32;
}
if cfg!(not(target_pointer_width = "64")) {
fill_bit_buffer(&mut l, &mut in_iter);
}
if let Some((mut symbol, code_len)) = r.tables[DIST_TABLE].lookup(l.bit_buf) {
symbol &= 511;
l.bit_buf >>= code_len;
l.num_bits -= code_len;
if symbol > 29 {
state.begin(InvalidDist);
break 'o TINFLStatus::Failed;
}
l.num_extra = u32::from(DIST_EXTRA[symbol as usize]);
l.dist = u32::from(DIST_BASE[symbol as usize]);
} else {
state.begin(InvalidCodeLen);
break 'o TINFLStatus::Failed;
}
if l.num_extra != 0 {
fill_bit_buffer(&mut l, &mut in_iter);
let extra_bits = l.bit_buf & ((1 << l.num_extra) - 1);
l.bit_buf >>= l.num_extra;
l.num_bits -= l.num_extra;
l.dist += extra_bits as u32;
}
let position = out_buf.position();
if l.dist as usize > out_buf.position()
&& (flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF != 0)
{
state.begin(DistanceOutOfBounds);
break TINFLStatus::Failed;
}
apply_match(
out_buf.get_mut(),
position,
l.dist as usize,
l.counter as usize,
out_buf_size_mask,
);
out_buf.set_position(position + l.counter as usize);
}
};
*local_vars = l;
(status, state)
}
pub fn decompress(
r: &mut DecompressorOxide,
in_buf: &[u8],
out: &mut [u8],
out_pos: usize,
flags: u32,
) -> (TINFLStatus, usize, usize) {
let out_buf_size_mask = if flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF != 0 {
usize::max_value()
} else {
out.len().saturating_sub(1)
};
if (out_buf_size_mask.wrapping_add(1) & out_buf_size_mask) != 0 || out_pos > out.len() {
return (TINFLStatus::BadParam, 0, 0);
}
let mut in_iter = in_buf.iter();
let mut state = r.state;
let mut out_buf = OutputBuffer::from_slice_and_pos(out, out_pos);
let mut l = LocalVars {
bit_buf: r.bit_buf,
num_bits: r.num_bits,
dist: r.dist,
counter: r.counter,
num_extra: r.num_extra,
};
let mut status = 'state_machine: loop {
match state {
Start => generate_state!(state, 'state_machine, {
l.bit_buf = 0;
l.num_bits = 0;
l.dist = 0;
l.counter = 0;
l.num_extra = 0;
r.z_header0 = 0;
r.z_header1 = 0;
r.z_adler32 = 1;
r.check_adler32 = 1;
if flags & TINFL_FLAG_PARSE_ZLIB_HEADER != 0 {
Action::Jump(State::ReadZlibCmf)
} else {
Action::Jump(State::ReadBlockHeader)
}
}),
ReadZlibCmf => generate_state!(state, 'state_machine, {
read_byte(&mut in_iter, flags, |cmf| {
r.z_header0 = u32::from(cmf);
Action::Jump(State::ReadZlibFlg)
})
}),
ReadZlibFlg => generate_state!(state, 'state_machine, {
read_byte(&mut in_iter, flags, |flg| {
r.z_header1 = u32::from(flg);
validate_zlib_header(r.z_header0, r.z_header1, flags, out_buf_size_mask)
})
}),
ReadBlockHeader => generate_state!(state, 'state_machine, {
read_bits(&mut l, 3, &mut in_iter, flags, |l, bits| {
r.finish = (bits & 1) as u32;
r.block_type = (bits >> 1) as u32 & 3;
match r.block_type {
0 => Action::Jump(BlockTypeNoCompression),
1 => {
start_static_table(r);
init_tree(r, l)
},
2 => {
l.counter = 0;
Action::Jump(ReadTableSizes)
},
3 => Action::Jump(BlockTypeUnexpected),
_ => unreachable!()
}
})
}),
BlockTypeNoCompression => generate_state!(state, 'state_machine, {
pad_to_bytes(&mut l, &mut in_iter, flags, |l| {
l.counter = 0;
Action::Jump(RawHeader)
})
}),
RawHeader => generate_state!(state, 'state_machine, {
if l.counter < 4 {
if l.num_bits != 0 {
read_bits(&mut l, 8, &mut in_iter, flags, |l, bits| {
r.raw_header[l.counter as usize] = bits as u8;
l.counter += 1;
Action::None
})
} else {
read_byte(&mut in_iter, flags, |byte| {
r.raw_header[l.counter as usize] = byte;
l.counter += 1;
Action::None
})
}
} else {
let length = u16::from(r.raw_header[0]) | (u16::from(r.raw_header[1]) << 8);
let check = u16::from(r.raw_header[2]) | (u16::from(r.raw_header[3]) << 8);
let valid = length == !check;
l.counter = length.into();
if !valid {
Action::Jump(BadRawLength)
} else if l.counter == 0 {
Action::Jump(BlockDone)
} else if l.num_bits != 0 {
Action::Jump(RawReadFirstByte)
} else {
Action::Jump(RawMemcpy1)
}
}
}),
RawReadFirstByte => generate_state!(state, 'state_machine, {
read_bits(&mut l, 8, &mut in_iter, flags, |l, bits| {
l.dist = bits as u32;
Action::Jump(RawStoreFirstByte)
})
}),
RawStoreFirstByte => generate_state!(state, 'state_machine, {
if out_buf.bytes_left() == 0 {
Action::End(TINFLStatus::HasMoreOutput)
} else {
out_buf.write_byte(l.dist as u8);
l.counter -= 1;
if l.counter == 0 || l.num_bits == 0 {
Action::Jump(RawMemcpy1)
} else {
Action::Jump(RawReadFirstByte)
}
}
}),
RawMemcpy1 => generate_state!(state, 'state_machine, {
if l.counter == 0 {
Action::Jump(BlockDone)
} else if out_buf.bytes_left() == 0 {
Action::End(TINFLStatus::HasMoreOutput)
} else {
Action::Jump(RawMemcpy2)
}
}),
RawMemcpy2 => generate_state!(state, 'state_machine, {
if in_iter.len() > 0 {
let space_left = out_buf.bytes_left();
let bytes_to_copy = cmp::min(cmp::min(
space_left,
in_iter.len()),
l.counter as usize
);
out_buf.write_slice(&in_iter.as_slice()[..bytes_to_copy]);
(&mut in_iter).nth(bytes_to_copy - 1);
l.counter -= bytes_to_copy as u32;
Action::Jump(RawMemcpy1)
} else {
end_of_input(flags)
}
}),
ReadTableSizes => generate_state!(state, 'state_machine, {
if l.counter < 3 {
let num_bits = [5, 5, 4][l.counter as usize];
read_bits(&mut l, num_bits, &mut in_iter, flags, |l, bits| {
r.table_sizes[l.counter as usize] =
bits as u32 + u32::from(MIN_TABLE_SIZES[l.counter as usize]);
l.counter += 1;
Action::None
})
} else {
memset(&mut r.tables[HUFFLEN_TABLE].code_size[..], 0);
l.counter = 0;
Action::Jump(ReadHufflenTableCodeSize)
}
}),
ReadHufflenTableCodeSize => generate_state!(state, 'state_machine, {
if l.counter < r.table_sizes[HUFFLEN_TABLE] {
read_bits(&mut l, 3, &mut in_iter, flags, |l, bits| {
r.tables[HUFFLEN_TABLE]
.code_size[HUFFMAN_LENGTH_ORDER[l.counter as usize] as usize] =
bits as u8;
l.counter += 1;
Action::None
})
} else {
r.table_sizes[HUFFLEN_TABLE] = 19;
init_tree(r, &mut l)
}
}),
ReadLitlenDistTablesCodeSize => generate_state!(state, 'state_machine, {
if l.counter < r.table_sizes[LITLEN_TABLE] + r.table_sizes[DIST_TABLE] {
decode_huffman_code(
r, &mut l, HUFFLEN_TABLE,
flags, &mut in_iter, |r, l, symbol| {
l.dist = symbol as u32;
if l.dist < 16 {
r.len_codes[l.counter as usize] = l.dist as u8;
l.counter += 1;
Action::None
} else if l.dist == 16 && l.counter == 0 {
Action::Jump(BadCodeSizeDistPrevLookup)
} else {
l.num_extra = [2, 3, 7][l.dist as usize - 16];
Action::Jump(ReadExtraBitsCodeSize)
}
}
)
} else if l.counter != r.table_sizes[LITLEN_TABLE] + r.table_sizes[DIST_TABLE] {
Action::Jump(BadCodeSizeSum)
} else {
r.tables[LITLEN_TABLE].code_size[..r.table_sizes[LITLEN_TABLE] as usize]
.copy_from_slice(&r.len_codes[..r.table_sizes[LITLEN_TABLE] as usize]);
let dist_table_start = r.table_sizes[LITLEN_TABLE] as usize;
let dist_table_end = (r.table_sizes[LITLEN_TABLE] +
r.table_sizes[DIST_TABLE]) as usize;
r.tables[DIST_TABLE].code_size[..r.table_sizes[DIST_TABLE] as usize]
.copy_from_slice(&r.len_codes[dist_table_start..dist_table_end]);
r.block_type -= 1;
init_tree(r, &mut l)
}
}),
ReadExtraBitsCodeSize => generate_state!(state, 'state_machine, {
let num_extra = l.num_extra;
read_bits(&mut l, num_extra, &mut in_iter, flags, |l, mut extra_bits| {
extra_bits += [3, 3, 11][(l.dist as usize - 16) & 3];
let val = if l.dist == 16 {
r.len_codes[l.counter as usize - 1]
} else {
0
};
memset(
&mut r.len_codes[
l.counter as usize..l.counter as usize + extra_bits as usize
],
val,
);
l.counter += extra_bits as u32;
Action::Jump(ReadLitlenDistTablesCodeSize)
})
}),
DecodeLitlen => generate_state!(state, 'state_machine, {
if in_iter.len() < 4 || out_buf.bytes_left() < 2 {
decode_huffman_code(
r,
&mut l,
LITLEN_TABLE,
flags,
&mut in_iter,
|_r, l, symbol| {
l.counter = symbol as u32;
Action::Jump(WriteSymbol)
},
)
} else if
out_buf.bytes_left() >= 259 &&
in_iter.len() >= 14
{
let (status, new_state) = decompress_fast(
r,
&mut in_iter,
&mut out_buf,
flags,
&mut l,
out_buf_size_mask,
);
state = new_state;
if status == TINFLStatus::Done {
Action::Jump(new_state)
} else {
Action::End(status)
}
} else {
fill_bit_buffer(&mut l, &mut in_iter);
if let Some((symbol, code_len)) = r.tables[LITLEN_TABLE].lookup(l.bit_buf) {
l.counter = symbol as u32;
l.bit_buf >>= code_len;
l.num_bits -= code_len;
if (l.counter & 256) != 0 {
Action::Jump(HuffDecodeOuterLoop1)
} else {
if cfg!(not(target_pointer_width = "64")) {
fill_bit_buffer(&mut l, &mut in_iter);
}
if let Some((symbol, code_len)) = r.tables[LITLEN_TABLE].lookup(l.bit_buf) {
l.bit_buf >>= code_len;
l.num_bits -= code_len;
out_buf.write_byte(l.counter as u8);
if (symbol & 256) != 0 {
l.counter = symbol as u32;
Action::Jump(HuffDecodeOuterLoop1)
} else {
out_buf.write_byte(symbol as u8);
Action::None
}
} else {
Action::Jump(InvalidCodeLen)
}
}
} else {
Action::Jump(InvalidCodeLen)
}
}
}),
WriteSymbol => generate_state!(state, 'state_machine, {
if l.counter >= 256 {
Action::Jump(HuffDecodeOuterLoop1)
} else if out_buf.bytes_left() > 0 {
out_buf.write_byte(l.counter as u8);
Action::Jump(DecodeLitlen)
} else {
Action::End(TINFLStatus::HasMoreOutput)
}
}),
HuffDecodeOuterLoop1 => generate_state!(state, 'state_machine, {
l.counter &= 511;
if l.counter == 256 {
Action::Jump(BlockDone)
} else if l.counter > 285 {
Action::Jump(InvalidLitlen)
} else {
l.num_extra =
u32::from(LENGTH_EXTRA[(l.counter - 257) as usize & BASE_EXTRA_MASK]);
l.counter = u32::from(LENGTH_BASE[(l.counter - 257) as usize & BASE_EXTRA_MASK]);
if l.num_extra != 0 {
Action::Jump(ReadExtraBitsLitlen)
} else {
Action::Jump(DecodeDistance)
}
}
}),
ReadExtraBitsLitlen => generate_state!(state, 'state_machine, {
let num_extra = l.num_extra;
read_bits(&mut l, num_extra, &mut in_iter, flags, |l, extra_bits| {
l.counter += extra_bits as u32;
Action::Jump(DecodeDistance)
})
}),
DecodeDistance => generate_state!(state, 'state_machine, {
decode_huffman_code(r, &mut l, DIST_TABLE, flags, &mut in_iter, |_r, l, symbol| {
if symbol > 29 {
return Action::Jump(InvalidDist)
}
l.num_extra = u32::from(DIST_EXTRA[symbol as usize & BASE_EXTRA_MASK]);
l.dist = u32::from(DIST_BASE[symbol as usize & BASE_EXTRA_MASK]);
if l.num_extra != 0 {
Action::Jump(ReadExtraBitsDistance)
} else {
Action::Jump(HuffDecodeOuterLoop2)
}
})
}),
ReadExtraBitsDistance => generate_state!(state, 'state_machine, {
let num_extra = l.num_extra;
read_bits(&mut l, num_extra, &mut in_iter, flags, |l, extra_bits| {
l.dist += extra_bits as u32;
Action::Jump(HuffDecodeOuterLoop2)
})
}),
HuffDecodeOuterLoop2 => generate_state!(state, 'state_machine, {
if l.dist as usize > out_buf.position() &&
(flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF != 0)
{
Action::Jump(DistanceOutOfBounds)
} else {
let out_pos = out_buf.position();
let source_pos = out_buf.position()
.wrapping_sub(l.dist as usize) & out_buf_size_mask;
let out_len = out_buf.get_ref().len() as usize;
let match_end_pos = out_buf.position() + l.counter as usize;
if match_end_pos > out_len ||
(source_pos >= out_pos && (source_pos - out_pos) < l.counter as usize)
{
if l.counter == 0 {
Action::Jump(DecodeLitlen)
} else {
Action::Jump(WriteLenBytesToEnd)
}
} else {
apply_match(
out_buf.get_mut(),
out_pos,
l.dist as usize,
l.counter as usize,
out_buf_size_mask
);
out_buf.set_position(out_pos + l.counter as usize);
Action::Jump(DecodeLitlen)
}
}
}),
WriteLenBytesToEnd => generate_state!(state, 'state_machine, {
if out_buf.bytes_left() > 0 {
let out_pos = out_buf.position();
let source_pos = out_buf.position()
.wrapping_sub(l.dist as usize) & out_buf_size_mask;
let len = cmp::min(out_buf.bytes_left(), l.counter as usize);
transfer(out_buf.get_mut(), source_pos, out_pos, len, out_buf_size_mask);
out_buf.set_position(out_pos + len);
l.counter -= len as u32;
if l.counter == 0 {
Action::Jump(DecodeLitlen)
} else {
Action::None
}
} else {
Action::End(TINFLStatus::HasMoreOutput)
}
}),
BlockDone => generate_state!(state, 'state_machine, {
if r.finish != 0 {
pad_to_bytes(&mut l, &mut in_iter, flags, |_| Action::None);
let in_consumed = in_buf.len() - in_iter.len();
let undo = undo_bytes(&mut l, in_consumed as u32) as usize;
in_iter = in_buf[in_consumed - undo..].iter();
l.bit_buf &= ((1 as BitBuffer) << l.num_bits) - 1;
debug_assert_eq!(l.num_bits, 0);
if flags & TINFL_FLAG_PARSE_ZLIB_HEADER != 0 {
l.counter = 0;
Action::Jump(ReadAdler32)
} else {
Action::Jump(DoneForever)
}
} else {
Action::Jump(ReadBlockHeader)
}
}),
ReadAdler32 => generate_state!(state, 'state_machine, {
if l.counter < 4 {
if l.num_bits != 0 {
read_bits(&mut l, 8, &mut in_iter, flags, |l, bits| {
r.z_adler32 <<= 8;
r.z_adler32 |= bits as u32;
l.counter += 1;
Action::None
})
} else {
read_byte(&mut in_iter, flags, |byte| {
r.z_adler32 <<= 8;
r.z_adler32 |= u32::from(byte);
l.counter += 1;
Action::None
})
}
} else {
Action::Jump(DoneForever)
}
}),
DoneForever => break TINFLStatus::Done,
_ => break TINFLStatus::Failed,
};
};
let in_undo = if status != TINFLStatus::NeedsMoreInput
&& status != TINFLStatus::FailedCannotMakeProgress
{
undo_bytes(&mut l, (in_buf.len() - in_iter.len()) as u32) as usize
} else {
0
};
if status == TINFLStatus::NeedsMoreInput && out_buf.bytes_left() == 0 {
status = TINFLStatus::HasMoreOutput
}
r.state = state;
r.bit_buf = l.bit_buf;
r.num_bits = l.num_bits;
r.dist = l.dist;
r.counter = l.counter;
r.num_extra = l.num_extra;
r.bit_buf &= ((1 as BitBuffer) << r.num_bits) - 1;
let need_adler = flags & (TINFL_FLAG_PARSE_ZLIB_HEADER | TINFL_FLAG_COMPUTE_ADLER32) != 0;
if need_adler && status as i32 >= 0 {
let out_buf_pos = out_buf.position();
r.check_adler32 = update_adler32(r.check_adler32, &out_buf.get_ref()[out_pos..out_buf_pos]);
if !cfg!(fuzzing) {
if status == TINFLStatus::Done
&& flags & TINFL_FLAG_PARSE_ZLIB_HEADER != 0
&& r.check_adler32 != r.z_adler32
{
status = TINFLStatus::Adler32Mismatch;
}
}
}
(
status,
in_buf.len() - in_iter.len() - in_undo,
out_buf.position() - out_pos,
)
}
#[cfg(test)]
mod test {
use super::*;
fn tinfl_decompress_oxide<'i>(
r: &mut DecompressorOxide,
input_buffer: &'i [u8],
output_buffer: &mut [u8],
flags: u32,
) -> (TINFLStatus, &'i [u8], usize) {
let (status, in_pos, out_pos) = decompress(r, input_buffer, output_buffer, 0, flags);
(status, &input_buffer[in_pos..], out_pos)
}
#[test]
fn decompress_zlib() {
let encoded = [
120, 156, 243, 72, 205, 201, 201, 215, 81, 168, 202, 201, 76, 82, 4, 0, 27, 101, 4, 19,
];
let flags = TINFL_FLAG_COMPUTE_ADLER32 | TINFL_FLAG_PARSE_ZLIB_HEADER;
let mut b = DecompressorOxide::new();
const LEN: usize = 32;
let mut b_buf = vec![0; LEN];
let b_status = tinfl_decompress_oxide(&mut b, &encoded[..], b_buf.as_mut_slice(), flags);
assert_eq!(b_status.0, TINFLStatus::Failed);
let flags = flags | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF;
b = DecompressorOxide::new();
let b_status = tinfl_decompress_oxide(&mut b, &encoded[..], b_buf.as_mut_slice(), flags);
assert_eq!(b_buf[..b_status.2], b"Hello, zlib!"[..]);
assert_eq!(b_status.0, TINFLStatus::Done);
}
#[test]
fn raw_block() {
const LEN: usize = 64;
let text = b"Hello, zlib!";
let encoded = {
let len = text.len();
let notlen = !len;
let mut encoded = vec![
1,
len as u8,
(len >> 8) as u8,
notlen as u8,
(notlen >> 8) as u8,
];
encoded.extend_from_slice(&text[..]);
encoded
};
let flags = TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF;
let mut b = DecompressorOxide::new();
let mut b_buf = vec![0; LEN];
let b_status = tinfl_decompress_oxide(&mut b, &encoded[..], b_buf.as_mut_slice(), flags);
assert_eq!(b_buf[..b_status.2], text[..]);
assert_eq!(b_status.0, TINFLStatus::Done);
}
fn masked_lookup(table: &HuffmanTable, bit_buf: BitBuffer) -> (i32, u32) {
let ret = table.lookup(bit_buf).unwrap();
(ret.0 & 511, ret.1)
}
#[test]
fn fixed_table_lookup() {
let mut d = DecompressorOxide::new();
d.block_type = 1;
start_static_table(&mut d);
let mut l = LocalVars {
bit_buf: d.bit_buf,
num_bits: d.num_bits,
dist: d.dist,
counter: d.counter,
num_extra: d.num_extra,
};
init_tree(&mut d, &mut l);
let llt = &d.tables[LITLEN_TABLE];
let dt = &d.tables[DIST_TABLE];
assert_eq!(masked_lookup(llt, 0b00001100), (0, 8));
assert_eq!(masked_lookup(llt, 0b00011110), (72, 8));
assert_eq!(masked_lookup(llt, 0b01011110), (74, 8));
assert_eq!(masked_lookup(llt, 0b11111101), (143, 8));
assert_eq!(masked_lookup(llt, 0b000010011), (144, 9));
assert_eq!(masked_lookup(llt, 0b111111111), (255, 9));
assert_eq!(masked_lookup(llt, 0b00000000), (256, 7));
assert_eq!(masked_lookup(llt, 0b1110100), (279, 7));
assert_eq!(masked_lookup(llt, 0b00000011), (280, 8));
assert_eq!(masked_lookup(llt, 0b11100011), (287, 8));
assert_eq!(masked_lookup(dt, 0), (0, 5));
assert_eq!(masked_lookup(dt, 20), (5, 5));
}
fn check_result(input: &[u8], expected_status: TINFLStatus, expected_state: State, zlib: bool) {
let mut r = DecompressorOxide::default();
let mut output_buf = vec![0; 1024 * 32];
let flags = if zlib {
inflate_flags::TINFL_FLAG_PARSE_ZLIB_HEADER
} else {
0
} | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF
| TINFL_FLAG_HAS_MORE_INPUT;
let (d_status, _in_bytes, _out_bytes) =
decompress(&mut r, input, &mut output_buf, 0, flags);
assert_eq!(expected_status, d_status);
assert_eq!(expected_state, r.state);
}
#[test]
fn bogus_input() {
use self::check_result as cr;
const F: TINFLStatus = TINFLStatus::Failed;
const OK: TINFLStatus = TINFLStatus::Done;
cr(&[0x77, 0x85], F, State::BadZlibHeader, true);
cr(&[0x88, 0x98], F, State::BadZlibHeader, true);
cr(&[0x78, 0x98], F, State::BadZlibHeader, true);
cr(
b"M\xff\xffM*\xad\xad\xad\xad\xad\xad\xad\xcd\xcd\xcdM",
F,
State::BadTotalSymbols,
false,
);
cr(
b"\xdd\xff\xff*M\x94ffffffffff",
F,
State::BadTotalSymbols,
false,
);
let c = |a, b, c| cr(a, b, c, false);
c(&[0, 0, 0, 0, 0], F, State::BadRawLength);
c(&[3, 0], OK, State::DoneForever);
c(&[6], F, State::BlockTypeUnexpected);
c(&[1, 1, 0, 0xfe, 0xff, 0], OK, State::DoneForever);
c(&[4, 0, 0xfe, 0xff], F, State::BadTotalSymbols);
c(&[4, 0, 0x24, 0x49, 0], F, State::BadCodeSizeDistPrevLookup);
c(
&[
4, 0x80, 0x49, 0x92, 0x24, 0x49, 0x92, 0x24, 0x71, 0xff, 0xff, 0x93, 0x11, 0,
],
F,
State::BadTotalSymbols,
);
c(&[2, 0x7e, 0xff, 0xff], F, State::InvalidDist);
c(
&[0x0c, 0xc0, 0x81, 0, 0, 0, 0, 0, 0x90, 0xff, 0x6b, 0x4, 0],
F,
State::DistanceOutOfBounds,
);
}
#[test]
fn empty_output_buffer_non_wrapping() {
let encoded = [
120, 156, 243, 72, 205, 201, 201, 215, 81, 168, 202, 201, 76, 82, 4, 0, 27, 101, 4, 19,
];
let flags = TINFL_FLAG_COMPUTE_ADLER32
| TINFL_FLAG_PARSE_ZLIB_HEADER
| TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF;
let mut r = DecompressorOxide::new();
let mut output_buf = vec![];
let res = decompress(&mut r, &encoded, &mut output_buf, 0, flags);
assert_eq!(res, (TINFLStatus::HasMoreOutput, 4, 0));
}
#[test]
fn empty_output_buffer_wrapping() {
let encoded = [
0x73, 0x49, 0x4d, 0xcb, 0x49, 0x2c, 0x49, 0x55, 0x00, 0x11, 0x00,
];
let flags = TINFL_FLAG_COMPUTE_ADLER32;
let mut r = DecompressorOxide::new();
let mut output_buf = vec![];
let res = decompress(&mut r, &encoded, &mut output_buf, 0, flags);
assert_eq!(res, (TINFLStatus::HasMoreOutput, 2, 0));
}
}