Google Git
Sign in
android / platform / external / rust / android-crates-io / 27bf8216a / . / crates / zlib-rs / src / inflate.rs
blob: 47584572a6e4fec3485213cd55e0fed88304d033 [file] [log] [blame]
#![allow(non_snake_case)] // TODO ultimately remove this
#![allow(clippy::missing_safety_doc)] // obviously needs to be fixed long-term
use core::ffi::{c_char, c_int, c_long, c_ulong};
use core::marker::PhantomData;
use core::mem::MaybeUninit;
use core::ops::ControlFlow;
mod bitreader;
mod inffixed_tbl;
mod inftrees;
mod window;
mod writer;
use crate::allocate::Allocator;
use crate::c_api::internal_state;
use crate::cpu_features::CpuFeatures;
use crate::{
adler32::adler32,
c_api::{gz_header, z_checksum, z_size, z_stream, Z_DEFLATED},
inflate::writer::Writer,
Code, InflateFlush, ReturnCode, DEF_WBITS, MAX_WBITS, MIN_WBITS,
};
use crate::crc32::{crc32, Crc32Fold};
use self::{
bitreader::BitReader,
inftrees::{inflate_table, CodeType, InflateTable},
window::Window,
};
const INFLATE_STRICT: bool = false;
// SAFETY: This struct must have the same layout as [`z_stream`], so that casts and transmutations
// between the two can work without UB.
#[repr(C)]
pub struct InflateStream<'a> {
pub(crate) next_in: *mut crate::c_api::Bytef,
pub(crate) avail_in: crate::c_api::uInt,
pub(crate) total_in: crate::c_api::z_size,
pub(crate) next_out: *mut crate::c_api::Bytef,
pub(crate) avail_out: crate::c_api::uInt,
pub(crate) total_out: crate::c_api::z_size,
pub(crate) msg: *mut c_char,
pub(crate) state: &'a mut State<'a>,
pub(crate) alloc: Allocator<'a>,
pub(crate) data_type: c_int,
pub(crate) adler: crate::c_api::z_checksum,
pub(crate) reserved: crate::c_api::uLong,
}
#[cfg(feature = "__internal-test")]
#[doc(hidden)]
pub const INFLATE_STATE_SIZE: usize = core::mem::size_of::<crate::inflate::State>();
#[cfg(feature = "__internal-test")]
#[doc(hidden)]
pub unsafe fn set_mode_dict(strm: &mut z_stream) {
unsafe {
(*(strm.state as *mut State)).mode = Mode::Dict;
}
}
impl<'a> InflateStream<'a> {
// z_stream and DeflateStream must have the same layout. Do our best to check if this is true.
// (imperfect check, but should catch most mistakes.)
const _S: () = assert!(core::mem::size_of::<z_stream>() == core::mem::size_of::<Self>());
const _A: () = assert!(core::mem::align_of::<z_stream>() == core::mem::align_of::<Self>());
/// # Safety
///
/// Behavior is undefined if any of the following conditions are violated:
///
/// - `strm` satisfies the conditions of [`pointer::as_ref`]
/// - if not `NULL`, `strm` as initialized using [`init`] or similar
///
/// [`pointer::as_ref`]: https://doc.rust-lang.org/core/primitive.pointer.html#method.as_ref
#[inline(always)]
pub unsafe fn from_stream_ref(strm: *const z_stream) -> Option<&'a Self> {
{
// Safety: ptr points to a valid value of type z_stream (if non-null)
let stream = unsafe { strm.as_ref() }?;
if stream.zalloc.is_none() || stream.zfree.is_none() {
return None;
}
if stream.state.is_null() {
return None;
}
}
// Safety: InflateStream has an equivalent layout as z_stream
strm.cast::<InflateStream>().as_ref()
}
/// # Safety
///
/// Behavior is undefined if any of the following conditions are violated:
///
/// - `strm` satisfies the conditions of [`pointer::as_mut`]
/// - if not `NULL`, `strm` as initialized using [`init`] or similar
///
/// [`pointer::as_mut`]: https://doc.rust-lang.org/core/primitive.pointer.html#method.as_mut
#[inline(always)]
pub unsafe fn from_stream_mut(strm: *mut z_stream) -> Option<&'a mut Self> {
{
// Safety: ptr points to a valid value of type z_stream (if non-null)
let stream = unsafe { strm.as_ref() }?;
if stream.zalloc.is_none() || stream.zfree.is_none() {
return None;
}
if stream.state.is_null() {
return None;
}
}
// Safety: InflateStream has an equivalent layout as z_stream
strm.cast::<InflateStream>().as_mut()
}
fn as_z_stream_mut(&mut self) -> &mut z_stream {
// safety: a valid &mut InflateStream is also a valid &mut z_stream
unsafe { &mut *(self as *mut _ as *mut z_stream) }
}
}
const MAX_BITS: u8 = 15; // maximum number of bits in a code
const MAX_DIST_EXTRA_BITS: u8 = 13; // maximum number of extra distance bits
//
pub fn uncompress_slice<'a>(
output: &'a mut [u8],
input: &[u8],
config: InflateConfig,
) -> (&'a mut [u8], ReturnCode) {
// SAFETY: [u8] is also a valid [MaybeUninit<u8>]
let output_uninit = unsafe {
core::slice::from_raw_parts_mut(output.as_mut_ptr() as *mut MaybeUninit<u8>, output.len())
};
uncompress(output_uninit, input, config)
}
/// Inflates `source` into `dest`, and writes the final inflated size into `dest_len`.
pub fn uncompress<'a>(
output: &'a mut [MaybeUninit<u8>],
input: &[u8],
config: InflateConfig,
) -> (&'a mut [u8], ReturnCode) {
let mut dest_len_ptr = output.len() as z_checksum;
// for detection of incomplete stream when *destLen == 0
let mut buf = [0u8];
let mut left;
let mut len = input.len() as u64;
let dest = if output.is_empty() {
left = 1;
buf.as_mut_ptr()
} else {
left = output.len() as u64;
dest_len_ptr = 0;
output.as_mut_ptr() as *mut u8
};
let mut stream = z_stream {
next_in: input.as_ptr() as *mut u8,
avail_in: 0,
zalloc: None,
zfree: None,
opaque: core::ptr::null_mut(),
..z_stream::default()
};
let err = init(&mut stream, config);
if err != ReturnCode::Ok {
return (&mut [], err);
}
stream.next_out = dest;
stream.avail_out = 0;
let Some(stream) = (unsafe { InflateStream::from_stream_mut(&mut stream) }) else {
return (&mut [], ReturnCode::StreamError);
};
let err = loop {
if stream.avail_out == 0 {
stream.avail_out = Ord::min(left, u32::MAX as u64) as u32;
left -= stream.avail_out as u64;
}
if stream.avail_in == 0 {
stream.avail_in = Ord::min(len, u32::MAX as u64) as u32;
len -= stream.avail_in as u64;
}
let err = unsafe { inflate(stream, InflateFlush::NoFlush) };
if err != ReturnCode::Ok {
break err;
}
};
if !output.is_empty() {
dest_len_ptr = stream.total_out;
} else if stream.total_out != 0 && err == ReturnCode::BufError {
left = 1;
}
let avail_out = stream.avail_out;
end(stream);
let ret = match err {
ReturnCode::StreamEnd => ReturnCode::Ok,
ReturnCode::NeedDict => ReturnCode::DataError,
ReturnCode::BufError if (left + avail_out as u64) != 0 => ReturnCode::DataError,
_ => err,
};
// SAFETY: we have now initialized these bytes
let output_slice = unsafe {
core::slice::from_raw_parts_mut(output.as_mut_ptr() as *mut u8, dest_len_ptr as usize)
};
(output_slice, ret)
}
#[derive(Debug, Clone, Copy)]
#[repr(u8)]
pub enum Mode {
Head,
Flags,
Time,
Os,
ExLen,
Extra,
Name,
Comment,
HCrc,
Sync,
Mem,
Length,
Type,
TypeDo,
Stored,
CopyBlock,
Check,
Len_,
Len,
Lit,
LenExt,
Dist,
DistExt,
Match,
Table,
LenLens,
CodeLens,
DictId,
Dict,
Done,
Bad,
}
#[derive(Default, Clone, Copy)]
#[allow(clippy::enum_variant_names)]
enum Codes {
#[default]
Fixed,
Codes,
Len,
Dist,
}
#[derive(Default, Clone, Copy)]
struct Table {
codes: Codes,
bits: usize,
}
#[derive(Clone, Copy)]
struct Flags(u8);
impl Default for Flags {
fn default() -> Self {
Self::SANE
}
}
impl Flags {
/// set if currently processing the last block
const IS_LAST_BLOCK: Self = Self(0b0000_0001);
/// set if a custom dictionary was provided
const HAVE_DICT: Self = Self(0b0000_0010);
/// if false, allow invalid distance too far
const SANE: Self = Self(0b0000_0100);
pub(crate) const fn contains(self, other: Self) -> bool {
debug_assert!(other.0.count_ones() == 1);
self.0 & other.0 != 0
}
#[inline(always)]
pub(crate) fn update(&mut self, other: Self, value: bool) {
if value {
*self = Self(self.0 | other.0);
} else {
*self = Self(self.0 & !other.0);
}
}
}
#[repr(C, align(64))]
pub(crate) struct State<'a> {
/// Current inflate mode
mode: Mode,
flags: Flags,
/// log base 2 of requested window size
wbits: u8,
/// bitflag
///
/// - bit 0 true if zlib
/// - bit 1 true if gzip
/// - bit 2 true to validate check value
wrap: u8,
flush: InflateFlush,
// allocated window if needed (capacity == 0 if unused)
window: Window<'a>,
//
/// number of code length code lengths
ncode: usize,
/// number of length code lengths
nlen: usize,
/// number of distance code lengths
ndist: usize,
/// number of code lengths in lens[]
have: usize,
/// next available space in codes[]
next: usize, // represented as an index, don't want a self-referential structure here
// IO
bit_reader: BitReader<'a>,
writer: Writer<'a>,
total: usize,
/// length of a block to copy
length: usize,
/// distance back to copy the string from
offset: usize,
/// extra bits needed
extra: usize,
/// bits back of last unprocessed length/lit
back: usize,
/// initial length of match
was: usize,
/// size of memory copying chunk
chunksize: usize,
in_available: usize,
out_available: usize,
gzip_flags: i32,
checksum: u32,
crc_fold: Crc32Fold,
error_message: Option<&'static str>,
/// place to store gzip header if needed
head: Option<&'a mut gz_header>,
dmax: usize,
/// table for length/literal codes
len_table: Table,
/// table for dist codes
dist_table: Table,
codes_codes: [Code; crate::ENOUGH_LENS],
len_codes: [Code; crate::ENOUGH_LENS],
dist_codes: [Code; crate::ENOUGH_DISTS],
/// temporary storage space for code lengths
lens: [u16; 320],
/// work area for code table building
work: [u16; 288],
}
impl<'a> State<'a> {
fn new(reader: &'a [u8], writer: Writer<'a>) -> Self {
let in_available = reader.len();
let out_available = writer.capacity();
Self {
flush: InflateFlush::NoFlush,
flags: Flags::default(),
wrap: 0,
mode: Mode::Head,
length: 0,
len_table: Table::default(),
dist_table: Table::default(),
wbits: 0,
offset: 0,
extra: 0,
back: 0,
was: 0,
chunksize: 0,
in_available,
out_available,
bit_reader: BitReader::new(reader),
writer,
total: 0,
window: Window::empty(),
head: None,
lens: [0u16; 320],
work: [0u16; 288],
ncode: 0,
nlen: 0,
ndist: 0,
have: 0,
next: 0,
error_message: None,
checksum: 0,
crc_fold: Crc32Fold::new(),
dmax: 0,
gzip_flags: 0,
codes_codes: [Code::default(); crate::ENOUGH_LENS],
len_codes: [Code::default(); crate::ENOUGH_LENS],
dist_codes: [Code::default(); crate::ENOUGH_DISTS],
}
}
fn len_table_ref(&self) -> &[Code] {
match self.len_table.codes {
Codes::Fixed => &self::inffixed_tbl::LENFIX,
Codes::Codes => &self.codes_codes,
Codes::Len => &self.len_codes,
Codes::Dist => &self.dist_codes,
}
}
fn dist_table_ref(&self) -> &[Code] {
match self.dist_table.codes {
Codes::Fixed => &self::inffixed_tbl::DISTFIX,
Codes::Codes => &self.codes_codes,
Codes::Len => &self.len_codes,
Codes::Dist => &self.dist_codes,
}
}
fn len_table_get(&self, index: usize) -> Code {
self.len_table_ref()[index]
}
fn dist_table_get(&self, index: usize) -> Code {
self.dist_table_ref()[index]
}
}
// swaps endianness
const fn zswap32(q: u32) -> u32 {
u32::from_be(q.to_le())
}
const INFLATE_FAST_MIN_HAVE: usize = 15;
const INFLATE_FAST_MIN_LEFT: usize = 260;
impl State<'_> {
// This logic is split into its own function for two reasons
//
// - We get to load state to the stack; doing this in all cases is expensive, but doing it just
// for Len and related states is very helpful.
// - The `-Cllvm-args=-enable-dfa-jump-thread` llvm arg is able to optimize this function, but
// not the entirity of `dispatch`. We get a massive boost from that pass.
//
// It unfortunately does duplicate the code for some of the states; deduplicating it by having
// more of the states call this function is slower.
fn len_and_friends(&mut self) -> ControlFlow<ReturnCode, ()> {
let avail_in = self.bit_reader.bytes_remaining();
let avail_out = self.writer.remaining();
if avail_in >= INFLATE_FAST_MIN_HAVE && avail_out >= INFLATE_FAST_MIN_LEFT {
inflate_fast_help(self, 0);
match self.mode {
Mode::Len => {}
_ => return ControlFlow::Continue(()),
}
}
let mut mode;
let mut writer;
let mut bit_reader;
macro_rules! load {
() => {
mode = self.mode;
writer = core::mem::replace(&mut self.writer, Writer::new(&mut []));
bit_reader = self.bit_reader;
};
}
macro_rules! restore {
() => {
self.mode = mode;
self.writer = writer;
self.bit_reader = bit_reader;
};
}
load!();
let len_table = match self.len_table.codes {
Codes::Fixed => &self::inffixed_tbl::LENFIX[..],
Codes::Codes => &self.codes_codes,
Codes::Len => &self.len_codes,
Codes::Dist => &self.dist_codes,
};
let dist_table = match self.dist_table.codes {
Codes::Fixed => &self::inffixed_tbl::DISTFIX[..],
Codes::Codes => &self.codes_codes,
Codes::Len => &self.len_codes,
Codes::Dist => &self.dist_codes,
};
loop {
mode = 'top: {
match mode {
Mode::Len => {
let avail_in = bit_reader.bytes_remaining();
let avail_out = writer.remaining();
// INFLATE_FAST_MIN_LEFT is important. It makes sure there is at least 32 bytes of free
// space available. This means for many SIMD operations we don't need to process a
// remainder; we just copy blindly, and a later operation will overwrite the extra copied
// bytes
if avail_in >= INFLATE_FAST_MIN_HAVE && avail_out >= INFLATE_FAST_MIN_LEFT {
restore!();
inflate_fast_help(self, 0);
return ControlFlow::Continue(());
}
self.back = 0;
// get a literal, length, or end-of-block code
let mut here;
loop {
let bits = bit_reader.bits(self.len_table.bits);
here = len_table[bits as usize];
if here.bits <= bit_reader.bits_in_buffer() {
break;
}
if let Err(return_code) = bit_reader.pull_byte() {
restore!();
return ControlFlow::Break(return_code);
};
}
if here.op != 0 && here.op & 0xf0 == 0 {
let last = here;
loop {
let bits = bit_reader.bits((last.bits + last.op) as usize) as u16;
here = len_table[(last.val + (bits >> last.bits)) as usize];
if last.bits + here.bits <= bit_reader.bits_in_buffer() {
break;
}
if let Err(return_code) = bit_reader.pull_byte() {
restore!();
return ControlFlow::Break(return_code);
};
}
bit_reader.drop_bits(last.bits);
self.back += last.bits as usize;
}
bit_reader.drop_bits(here.bits);
self.back += here.bits as usize;
self.length = here.val as usize;
if here.op == 0 {
break 'top Mode::Lit;
} else if here.op & 32 != 0 {
// end of block
// eprintln!("inflate: end of block");
self.back = usize::MAX;
mode = Mode::Type;
restore!();
return ControlFlow::Continue(());
} else if here.op & 64 != 0 {
mode = Mode::Bad;
{
restore!();
let this = &mut *self;
let msg: &'static str = "invalid literal/length code\0";
#[cfg(all(feature = "std", test))]
dbg!(msg);
this.error_message = Some(msg);
return ControlFlow::Break(ReturnCode::DataError);
}
} else {
// length code
self.extra = (here.op & MAX_BITS) as usize;
break 'top Mode::LenExt;
}
}
Mode::Lit => {
// NOTE: this branch must be kept in sync with its counterpart in `dispatch`
if writer.is_full() {
restore!();
#[cfg(all(test, feature = "std"))]
eprintln!("Ok: writer is full ({} bytes)", self.writer.capacity());
return ControlFlow::Break(ReturnCode::Ok);
}
writer.push(self.length as u8);
break 'top Mode::Len;
}
Mode::LenExt => {
// NOTE: this branch must be kept in sync with its counterpart in `dispatch`
let extra = self.extra;
// get extra bits, if any
if extra != 0 {
match bit_reader.need_bits(extra) {
Err(return_code) => {
restore!();
return ControlFlow::Break(return_code);
}
Ok(v) => v,
};
self.length += bit_reader.bits(extra) as usize;
bit_reader.drop_bits(extra as u8);
self.back += extra;
}
// eprintln!("inflate: length {}", state.length);
self.was = self.length;
break 'top Mode::Dist;
}
Mode::Dist => {
// NOTE: this branch must be kept in sync with its counterpart in `dispatch`
// get distance code
let mut here;
loop {
let bits = bit_reader.bits(self.dist_table.bits) as usize;
here = dist_table[bits];
if here.bits <= bit_reader.bits_in_buffer() {
break;
}
if let Err(return_code) = bit_reader.pull_byte() {
restore!();
return ControlFlow::Break(return_code);
};
}
if here.op & 0xf0 == 0 {
let last = here;
loop {
let bits = bit_reader.bits((last.bits + last.op) as usize);
here =
dist_table[last.val as usize + ((bits as usize) >> last.bits)];
if last.bits + here.bits <= bit_reader.bits_in_buffer() {
break;
}
if let Err(return_code) = bit_reader.pull_byte() {
restore!();
return ControlFlow::Break(return_code);
};
}
bit_reader.drop_bits(last.bits);
self.back += last.bits as usize;
}
bit_reader.drop_bits(here.bits);
if here.op & 64 != 0 {
restore!();
self.mode = Mode::Bad;
return ControlFlow::Break(self.bad("invalid distance code\0"));
}
self.offset = here.val as usize;
self.extra = (here.op & MAX_BITS) as usize;
break 'top Mode::DistExt;
}
Mode::DistExt => {
// NOTE: this branch must be kept in sync with its counterpart in `dispatch`
let extra = self.extra;
if extra > 0 {
match bit_reader.need_bits(extra) {
Err(return_code) => {
restore!();
return ControlFlow::Break(return_code);
}
Ok(v) => v,
};
self.offset += bit_reader.bits(extra) as usize;
bit_reader.drop_bits(extra as u8);
self.back += extra;
}
if INFLATE_STRICT && self.offset > self.dmax {
restore!();
self.mode = Mode::Bad;
return ControlFlow::Break(
self.bad("invalid distance code too far back\0"),
);
}
// eprintln!("inflate: distance {}", state.offset);
break 'top Mode::Match;
}
Mode::Match => {
// NOTE: this branch must be kept in sync with its counterpart in `dispatch`
if writer.is_full() {
restore!();
#[cfg(all(feature = "std", test))]
eprintln!(
"BufError: writer is full ({} bytes)",
self.writer.capacity()
);
return ControlFlow::Break(ReturnCode::Ok);
}
let left = writer.remaining();
let copy = writer.len();
let copy = if self.offset > copy {
// copy from window to output
let mut copy = self.offset - copy;
if copy > self.window.have() {
if self.flags.contains(Flags::SANE) {
restore!();
self.mode = Mode::Bad;
return ControlFlow::Break(
self.bad("invalid distance too far back\0"),
);
}
// TODO INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
panic!("INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR")
}
let wnext = self.window.next();
let wsize = self.window.size();
let from = if copy > wnext {
copy -= wnext;
wsize - copy
} else {
wnext - copy
};
copy = Ord::min(copy, self.length);
copy = Ord::min(copy, left);
writer.extend_from_window(&self.window, from..from + copy);
copy
} else {
let copy = Ord::min(self.length, left);
writer.copy_match(self.offset, copy);
copy
};
self.length -= copy;
if self.length == 0 {
break 'top Mode::Len;
} else {
// otherwise it seems to recurse?
// self.match_()
break 'top Mode::Match;
}
}
_ => unsafe { core::hint::unreachable_unchecked() },
}
}
}
}
fn dispatch(&mut self) -> ReturnCode {
// Note: All early returns must save mode into self.mode again.
let mut mode = self.mode;
macro_rules! pull_byte {
($self:expr) => {
match $self.bit_reader.pull_byte() {
Err(return_code) => {
self.mode = mode;
return $self.inflate_leave(return_code);
}
Ok(_) => (),
}
};
}
macro_rules! need_bits {
($self:expr, $n:expr) => {
match $self.bit_reader.need_bits($n) {
Err(return_code) => {
self.mode = mode;
return $self.inflate_leave(return_code);
}
Ok(v) => v,
}
};
}
let ret = 'label: loop {
mode = 'blk: {
match mode {
Mode::Head => {
if self.wrap == 0 {
break 'blk Mode::TypeDo;
}
need_bits!(self, 16);
// Gzip
if (self.wrap & 2) != 0 && self.bit_reader.hold() == 0x8b1f {
if self.wbits == 0 {
self.wbits = 15;
}
let b0 = self.bit_reader.bits(8) as u8;
let b1 = (self.bit_reader.hold() >> 8) as u8;
self.checksum = crc32(crate::CRC32_INITIAL_VALUE, &[b0, b1]);
self.bit_reader.init_bits();
break 'blk Mode::Flags;
}
if let Some(header) = &mut self.head {
header.done = -1;
}
// check if zlib header is allowed
if (self.wrap & 1) == 0
|| ((self.bit_reader.bits(8) << 8) + (self.bit_reader.hold() >> 8)) % 31
!= 0
{
mode = Mode::Bad;
break 'label self.bad("incorrect header check\0");
}
if self.bit_reader.bits(4) != Z_DEFLATED as u64 {
mode = Mode::Bad;
break 'label self.bad("unknown compression method\0");
}
self.bit_reader.drop_bits(4);
let len = self.bit_reader.bits(4) as u8 + 8;
if self.wbits == 0 {
self.wbits = len;
}
if len as i32 > MAX_WBITS || len > self.wbits {
mode = Mode::Bad;
break 'label self.bad("invalid window size\0");
}
self.dmax = 1 << len;
self.gzip_flags = 0; // indicate zlib header
self.checksum = crate::ADLER32_INITIAL_VALUE as _;
if self.bit_reader.hold() & 0x200 != 0 {
self.bit_reader.init_bits();
break 'blk Mode::DictId;
} else {
self.bit_reader.init_bits();
break 'blk Mode::Type;
}
}
Mode::Flags => {
need_bits!(self, 16);
self.gzip_flags = self.bit_reader.hold() as i32;
// Z_DEFLATED = 8 is the only supported method
if self.gzip_flags & 0xff != Z_DEFLATED {
mode = Mode::Bad;
break 'label self.bad("unknown compression method\0");
}
if self.gzip_flags & 0xe000 != 0 {
mode = Mode::Bad;
break 'label self.bad("unknown header flags set\0");
}
if let Some(head) = self.head.as_mut() {
head.text = ((self.bit_reader.hold() >> 8) & 1) as i32;
}
if (self.gzip_flags & 0x0200) != 0 && (self.wrap & 4) != 0 {
let b0 = self.bit_reader.bits(8) as u8;
let b1 = (self.bit_reader.hold() >> 8) as u8;
self.checksum = crc32(self.checksum, &[b0, b1]);
}
self.bit_reader.init_bits();
break 'blk Mode::Time;
}
Mode::Time => {
need_bits!(self, 32);
if let Some(head) = self.head.as_mut() {
head.time = self.bit_reader.hold() as z_size;
}
if (self.gzip_flags & 0x0200) != 0 && (self.wrap & 4) != 0 {
let bytes = (self.bit_reader.hold() as u32).to_le_bytes();
self.checksum = crc32(self.checksum, &bytes);
}
self.bit_reader.init_bits();
break 'blk Mode::Os;
}
Mode::Os => {
need_bits!(self, 16);
if let Some(head) = self.head.as_mut() {
head.xflags = (self.bit_reader.hold() & 0xff) as i32;
head.os = (self.bit_reader.hold() >> 8) as i32;
}
if (self.gzip_flags & 0x0200) != 0 && (self.wrap & 4) != 0 {
let bytes = (self.bit_reader.hold() as u16).to_le_bytes();
self.checksum = crc32(self.checksum, &bytes);
}
self.bit_reader.init_bits();
break 'blk Mode::ExLen;
}
Mode::ExLen => {
if (self.gzip_flags & 0x0400) != 0 {
need_bits!(self, 16);
// self.length (and head.extra_len) represent the length of the extra field
self.length = self.bit_reader.hold() as usize;
if let Some(head) = self.head.as_mut() {
head.extra_len = self.length as u32;
}
if (self.gzip_flags & 0x0200) != 0 && (self.wrap & 4) != 0 {
let bytes = (self.bit_reader.hold() as u16).to_le_bytes();
self.checksum = crc32(self.checksum, &bytes);
}
self.bit_reader.init_bits();
} else if let Some(head) = self.head.as_mut() {
head.extra = core::ptr::null_mut();
}
break 'blk Mode::Extra;
}
Mode::Extra => {
if (self.gzip_flags & 0x0400) != 0 {
// self.length is the number of remaining `extra` bytes. But they may not all be available
let extra_available =
Ord::min(self.length, self.bit_reader.bytes_remaining());
if extra_available > 0 {
if let Some(head) = self.head.as_mut() {
if !head.extra.is_null() {
// at `head.extra`, the caller has reserved `head.extra_max` bytes.
// in the deflated byte stream, we've found a gzip header with
// `head.extra_len` bytes of data. We must be careful because
// `head.extra_len` may be larger than `head.extra_max`.
// how many bytes we've already written into `head.extra`
let written_so_far = head.extra_len as usize - self.length;
// min of number of bytes available at dst and at src
let count = Ord::min(
(head.extra_max as usize)
.saturating_sub(written_so_far),
extra_available,
);
// SAFETY: location where we'll write: this saturates at the
// `head.extra.add(head.extra.max)` to prevent UB
let next_write_offset =
Ord::min(written_so_far, head.extra_max as usize);
unsafe {
// SAFETY: count is effectively bounded by head.extra_max
// and bit_reader.bytes_remaining(), so the count won't
// go out of bounds.
core::ptr::copy_nonoverlapping(
self.bit_reader.as_mut_ptr(),
head.extra.add(next_write_offset),
count,
);
}
}
}
// Checksum
if (self.gzip_flags & 0x0200) != 0 && (self.wrap & 4) != 0 {
let extra_slice =
&self.bit_reader.as_slice()[..extra_available];
self.checksum = crc32(self.checksum, extra_slice)
}
self.in_available -= extra_available;
self.bit_reader.advance(extra_available);
self.length -= extra_available;
}
// Checks for errors occur after returning
if self.length != 0 {
break 'label self.inflate_leave(ReturnCode::Ok);
}
}
self.length = 0;
break 'blk Mode::Name;
}
Mode::Name => {
if (self.gzip_flags & 0x0800) != 0 {
if self.in_available == 0 {
break 'label self.inflate_leave(ReturnCode::Ok);
}
// the name string will always be null-terminated, but might be longer than we have
// space for in the header struct. Nonetheless, we read the whole thing.
let slice = self.bit_reader.as_slice();
let null_terminator_index = slice.iter().position(|c| *c == 0);
// we include the null terminator if it exists
let name_slice = match null_terminator_index {
Some(i) => &slice[..=i],
None => slice,
};
// if the header has space, store as much as possible in there
if let Some(head) = self.head.as_mut() {
if !head.name.is_null() {
let remaining_name_bytes = (head.name_max as usize)
.checked_sub(self.length)
.expect("name out of bounds");
let copy = Ord::min(name_slice.len(), remaining_name_bytes);
unsafe {
// SAFETY: copy is effectively bound by the name length and
// head.name_max, so this won't go out of bounds.
core::ptr::copy_nonoverlapping(
name_slice.as_ptr(),
head.name.add(self.length),
copy,
)
};
self.length += copy;
}
}
if (self.gzip_flags & 0x0200) != 0 && (self.wrap & 4) != 0 {
self.checksum = crc32(self.checksum, name_slice);
}
let reached_end = name_slice.last() == Some(&0);
self.bit_reader.advance(name_slice.len());
if !reached_end && self.bit_reader.bytes_remaining() == 0 {
break 'label self.inflate_leave(ReturnCode::Ok);
}
} else if let Some(head) = self.head.as_mut() {
head.name = core::ptr::null_mut();
}
self.length = 0;
break 'blk Mode::Comment;
}
Mode::Comment => {
if (self.gzip_flags & 0x01000) != 0 {
if self.in_available == 0 {
break 'label self.inflate_leave(ReturnCode::Ok);
}
// the comment string will always be null-terminated, but might be longer than we have
// space for in the header struct. Nonetheless, we read the whole thing.
let slice = self.bit_reader.as_slice();
let null_terminator_index = slice.iter().position(|c| *c == 0);
// we include the null terminator if it exists
let comment_slice = match null_terminator_index {
Some(i) => &slice[..=i],
None => slice,
};
// if the header has space, store as much as possible in there
if let Some(head) = self.head.as_mut() {
if !head.comment.is_null() {
let remaining_comm_bytes = (head.comm_max as usize)
.checked_sub(self.length)
.expect("comm out of bounds");
let copy = Ord::min(comment_slice.len(), remaining_comm_bytes);
unsafe {
// SAFETY: copy is effectively bound by the comment length and
// head.comm_max, so this won't go out of bounds.
core::ptr::copy_nonoverlapping(
comment_slice.as_ptr(),
head.comment.add(self.length),
copy,
)
};
self.length += copy;
}
}
if (self.gzip_flags & 0x0200) != 0 && (self.wrap & 4) != 0 {
self.checksum = crc32(self.checksum, comment_slice);
}
let reached_end = comment_slice.last() == Some(&0);
self.bit_reader.advance(comment_slice.len());
if !reached_end && self.bit_reader.bytes_remaining() == 0 {
break 'label self.inflate_leave(ReturnCode::Ok);
}
} else if let Some(head) = self.head.as_mut() {
head.comment = core::ptr::null_mut();
}
break 'blk Mode::HCrc;
}
Mode::HCrc => {
if (self.gzip_flags & 0x0200) != 0 {
need_bits!(self, 16);
if (self.wrap & 4) != 0
&& self.bit_reader.hold() as u32 != (self.checksum & 0xffff)
{
mode = Mode::Bad;
break 'label self.bad("header crc mismatch\0");
}
self.bit_reader.init_bits();
}
if let Some(head) = self.head.as_mut() {
head.hcrc = (self.gzip_flags >> 9) & 1;
head.done = 1;
}
// compute crc32 checksum if not in raw mode
if (self.wrap & 4 != 0) && self.gzip_flags != 0 {
self.crc_fold = Crc32Fold::new();
self.checksum = crate::CRC32_INITIAL_VALUE;
}
break 'blk Mode::Type;
}
Mode::Type => {
use InflateFlush::*;
match self.flush {
Block | Trees => break 'label ReturnCode::Ok,
NoFlush | SyncFlush | Finish => {
// NOTE: this is slightly different to what zlib-rs does!
break 'blk Mode::TypeDo;
}
}
}
Mode::TypeDo => {
if self.flags.contains(Flags::IS_LAST_BLOCK) {
self.bit_reader.next_byte_boundary();
break 'blk Mode::Check;
}
need_bits!(self, 3);
// self.last = self.bit_reader.bits(1) != 0;
self.flags
.update(Flags::IS_LAST_BLOCK, self.bit_reader.bits(1) != 0);
self.bit_reader.drop_bits(1);
match self.bit_reader.bits(2) {
0b00 => {
// eprintln!("inflate: stored block (last = {last})");
self.bit_reader.drop_bits(2);
break 'blk Mode::Stored;
}
0b01 => {
// eprintln!("inflate: fixed codes block (last = {last})");
self.len_table = Table {
codes: Codes::Fixed,
bits: 9,
};
self.dist_table = Table {
codes: Codes::Fixed,
bits: 5,
};
mode = Mode::Len_;
self.bit_reader.drop_bits(2);
if let InflateFlush::Trees = self.flush {
break 'label self.inflate_leave(ReturnCode::Ok);
} else {
break 'blk Mode::Len_;
}
}
0b10 => {
// eprintln!("inflate: dynamic codes block (last = {last})");
self.bit_reader.drop_bits(2);
break 'blk Mode::Table;
}
0b11 => {
// eprintln!("inflate: invalid block type");
self.bit_reader.drop_bits(2);
mode = Mode::Bad;
break 'label self.bad("invalid block type\0");
}
_ => {
// LLVM will optimize this branch away
unreachable!("BitReader::bits(2) only yields a value of two bits, so this match is already exhaustive")
}
}
}
Mode::Stored => {
self.bit_reader.next_byte_boundary();
need_bits!(self, 32);
let hold = self.bit_reader.bits(32) as u32;
// eprintln!("hold {hold:#x}");
if hold as u16 != !((hold >> 16) as u16) {
mode = Mode::Bad;
break 'label self.bad("invalid stored block lengths\0");
}
self.length = hold as usize & 0xFFFF;
// eprintln!("inflate: stored length {}", state.length);
self.bit_reader.init_bits();
if let InflateFlush::Trees = self.flush {
break 'label self.inflate_leave(ReturnCode::Ok);
} else {
break 'blk Mode::CopyBlock;
}
}
Mode::CopyBlock => {
loop {
let mut copy = self.length;
if copy == 0 {
break;
}
copy = Ord::min(copy, self.writer.remaining());
copy = Ord::min(copy, self.bit_reader.bytes_remaining());
if copy == 0 {
break 'label self.inflate_leave(ReturnCode::Ok);
}
self.writer.extend(&self.bit_reader.as_slice()[..copy]);
self.bit_reader.advance(copy);
self.length -= copy;
}
break 'blk Mode::Type;
}
Mode::Check => {
if !cfg!(feature = "__internal-fuzz-disable-checksum") && self.wrap != 0 {
need_bits!(self, 32);
self.total += self.writer.len();
if self.wrap & 4 != 0 {
if self.gzip_flags != 0 {
self.crc_fold.fold(self.writer.filled(), self.checksum);
self.checksum = self.crc_fold.finish();
} else {
self.checksum = adler32(self.checksum, self.writer.filled());
}
}
let given_checksum = if self.gzip_flags != 0 {
self.bit_reader.hold() as u32
} else {
zswap32(self.bit_reader.hold() as u32)
};
self.out_available = self.writer.capacity() - self.writer.len();
if self.wrap & 4 != 0 && given_checksum != self.checksum {
mode = Mode::Bad;
break 'label self.bad("incorrect data check\0");
}
self.bit_reader.init_bits();
}
break 'blk Mode::Length;
}
Mode::Len_ => {
break 'blk Mode::Len;
}
Mode::Len => {
self.mode = mode;
let val = self.len_and_friends();
mode = self.mode;
match val {
ControlFlow::Break(return_code) => break 'label return_code,
ControlFlow::Continue(()) => continue 'label,
}
}
Mode::LenExt => {
// NOTE: this branch must be kept in sync with its counterpart in `len_and_friends`
let extra = self.extra;
// get extra bits, if any
if extra != 0 {
need_bits!(self, extra);
self.length += self.bit_reader.bits(extra) as usize;
self.bit_reader.drop_bits(extra as u8);
self.back += extra;
}
// eprintln!("inflate: length {}", state.length);
self.was = self.length;
break 'blk Mode::Dist;
}
Mode::Lit => {
// NOTE: this branch must be kept in sync with its counterpart in `len_and_friends`
if self.writer.is_full() {
#[cfg(all(test, feature = "std"))]
eprintln!("Ok: writer is full ({} bytes)", self.writer.capacity());
break 'label self.inflate_leave(ReturnCode::Ok);
}
self.writer.push(self.length as u8);
break 'blk Mode::Len;
}
Mode::Dist => {
// NOTE: this branch must be kept in sync with its counterpart in `len_and_friends`
// get distance code
let mut here;
loop {
let bits = self.bit_reader.bits(self.dist_table.bits) as usize;
here = self.dist_table_get(bits);
if here.bits <= self.bit_reader.bits_in_buffer() {
break;
}
pull_byte!(self);
}
if here.op & 0xf0 == 0 {
let last = here;
loop {
let bits = self.bit_reader.bits((last.bits + last.op) as usize);
here = self.dist_table_get(
last.val as usize + ((bits as usize) >> last.bits),
);
if last.bits + here.bits <= self.bit_reader.bits_in_buffer() {
break;
}
pull_byte!(self);
}
self.bit_reader.drop_bits(last.bits);
self.back += last.bits as usize;
}
self.bit_reader.drop_bits(here.bits);
if here.op & 64 != 0 {
mode = Mode::Bad;
break 'label self.bad("invalid distance code\0");
}
self.offset = here.val as usize;
self.extra = (here.op & MAX_BITS) as usize;
break 'blk Mode::DistExt;
}
Mode::DistExt => {
// NOTE: this branch must be kept in sync with its counterpart in `len_and_friends`
let extra = self.extra;
if extra > 0 {
need_bits!(self, extra);
self.offset += self.bit_reader.bits(extra) as usize;
self.bit_reader.drop_bits(extra as u8);
self.back += extra;
}
if INFLATE_STRICT && self.offset > self.dmax {
mode = Mode::Bad;
break 'label self.bad("invalid distance code too far back\0");
}
// eprintln!("inflate: distance {}", state.offset);
break 'blk Mode::Match;
}
Mode::Match => {
// NOTE: this branch must be kept in sync with its counterpart in `len_and_friends`
'match_: loop {
if self.writer.is_full() {
#[cfg(all(feature = "std", test))]
eprintln!(
"BufError: writer is full ({} bytes)",
self.writer.capacity()
);
break 'label self.inflate_leave(ReturnCode::Ok);
}
let left = self.writer.remaining();
let copy = self.writer.len();
let copy = if self.offset > copy {
// copy from window to output
let mut copy = self.offset - copy;
if copy > self.window.have() {
if self.flags.contains(Flags::SANE) {
mode = Mode::Bad;
break 'label self.bad("invalid distance too far back\0");
}
// TODO INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
panic!("INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR")
}
let wnext = self.window.next();
let wsize = self.window.size();
let from = if copy > wnext {
copy -= wnext;
wsize - copy
} else {
wnext - copy
};
copy = Ord::min(copy, self.length);
copy = Ord::min(copy, left);
self.writer
.extend_from_window(&self.window, from..from + copy);
copy
} else {
let copy = Ord::min(self.length, left);
self.writer.copy_match(self.offset, copy);
copy
};
self.length -= copy;
if self.length == 0 {
break 'blk Mode::Len;
} else {
// otherwise it seems to recurse?
continue 'match_;
}
}
}
Mode::Done => todo!(),
Mode::Table => {
need_bits!(self, 14);
self.nlen = self.bit_reader.bits(5) as usize + 257;
self.bit_reader.drop_bits(5);
self.ndist = self.bit_reader.bits(5) as usize + 1;
self.bit_reader.drop_bits(5);
self.ncode = self.bit_reader.bits(4) as usize + 4;
self.bit_reader.drop_bits(4);
// TODO pkzit_bug_workaround
if self.nlen > 286 || self.ndist > 30 {
mode = Mode::Bad;
break 'label self.bad("too many length or distance symbols\0");
}
self.have = 0;
break 'blk Mode::LenLens;
}
Mode::LenLens => {
// permutation of code lengths ;
const ORDER: [u8; 19] = [
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
];
while self.have < self.ncode {
need_bits!(self, 3);
self.lens[usize::from(ORDER[self.have])] =
self.bit_reader.bits(3) as u16;
self.have += 1;
self.bit_reader.drop_bits(3);
}
while self.have < 19 {
self.lens[usize::from(ORDER[self.have])] = 0;
self.have += 1;
}
let InflateTable::Success { root, used } = inflate_table(
CodeType::Codes,
&self.lens,
19,
&mut self.codes_codes,
7,
&mut self.work,
) else {
mode = Mode::Bad;
break 'label self.bad("invalid code lengths set\0");
};
self.next = used;
self.len_table.codes = Codes::Codes;
self.len_table.bits = root;
self.have = 0;
break 'blk Mode::CodeLens;
}
Mode::CodeLens => {
while self.have < self.nlen + self.ndist {
let here = loop {
let bits = self.bit_reader.bits(self.len_table.bits);
let here = self.len_table_get(bits as usize);
if here.bits <= self.bit_reader.bits_in_buffer() {
break here;
}
pull_byte!(self);
};
let here_bits = here.bits;
match here.val {
0..=15 => {
self.bit_reader.drop_bits(here_bits);
self.lens[self.have] = here.val;
self.have += 1;
}
16 => {
need_bits!(self, usize::from(here_bits) + 2);
self.bit_reader.drop_bits(here_bits);
if self.have == 0 {
mode = Mode::Bad;
break 'label self.bad("invalid bit length repeat\0");
}
let len = self.lens[self.have - 1];
let copy = 3 + self.bit_reader.bits(2) as usize;
self.bit_reader.drop_bits(2);
if self.have + copy > self.nlen + self.ndist {
mode = Mode::Bad;
break 'label self.bad("invalid bit length repeat\0");
}
self.lens[self.have..][..copy].fill(len);
self.have += copy;
}
17 => {
need_bits!(self, usize::from(here_bits) + 3);
self.bit_reader.drop_bits(here_bits);
let copy = 3 + self.bit_reader.bits(3) as usize;
self.bit_reader.drop_bits(3);
if self.have + copy > self.nlen + self.ndist {
mode = Mode::Bad;
break 'label self.bad("invalid bit length repeat\0");
}
self.lens[self.have..][..copy].fill(0);
self.have += copy;
}
18.. => {
need_bits!(self, usize::from(here_bits) + 7);
self.bit_reader.drop_bits(here_bits);
let copy = 11 + self.bit_reader.bits(7) as usize;
self.bit_reader.drop_bits(7);
if self.have + copy > self.nlen + self.ndist {
mode = Mode::Bad;
break 'label self.bad("invalid bit length repeat\0");
}
self.lens[self.have..][..copy].fill(0);
self.have += copy;
}
}
}
// check for end-of-block code (better have one)
if self.lens[256] == 0 {
mode = Mode::Bad;
break 'label self.bad("invalid code -- missing end-of-block\0");
}
// build code tables
let InflateTable::Success { root, used } = inflate_table(
CodeType::Lens,
&self.lens,
self.nlen,
&mut self.len_codes,
10,
&mut self.work,
) else {
mode = Mode::Bad;
break 'label self.bad("invalid literal/lengths set\0");
};
self.len_table.codes = Codes::Len;
self.len_table.bits = root;
self.next = used;
let InflateTable::Success { root, used } = inflate_table(
CodeType::Dists,
&self.lens[self.nlen..],
self.ndist,
&mut self.dist_codes,
9,
&mut self.work,
) else {
mode = Mode::Bad;
break 'label self.bad("invalid distances set\0");
};
self.dist_table.bits = root;
self.dist_table.codes = Codes::Dist;
self.next += used;
mode = Mode::Len_;
if matches!(self.flush, InflateFlush::Trees) {
break 'label self.inflate_leave(ReturnCode::Ok);
}
break 'blk Mode::Len_;
}
Mode::Dict => {
if !self.flags.contains(Flags::HAVE_DICT) {
break 'label self.inflate_leave(ReturnCode::NeedDict);
}
self.checksum = crate::ADLER32_INITIAL_VALUE as _;
break 'blk Mode::Type;
}
Mode::DictId => {
need_bits!(self, 32);
self.checksum = zswap32(self.bit_reader.hold() as u32);
self.bit_reader.init_bits();
break 'blk Mode::Dict;
}
Mode::Bad => {
let msg = "repeated call with bad state\0";
#[cfg(all(feature = "std", test))]
dbg!(msg);
self.error_message = Some(msg);
break 'label ReturnCode::DataError;
}
Mode::Mem => {
break 'label ReturnCode::MemError;
}
Mode::Sync => {
break 'label ReturnCode::StreamError;
}
Mode::Length => {
// for gzip, last bytes contain LENGTH
if self.wrap != 0 && self.gzip_flags != 0 {
need_bits!(self, 32);
if (self.wrap & 4) != 0 && self.bit_reader.hold() != self.total as u64 {
mode = Mode::Bad;
break 'label self.bad("incorrect length check\0");
}
self.bit_reader.init_bits();
}
// inflate stream terminated properly
break 'label ReturnCode::StreamEnd;
}
};
}
};
self.mode = mode;
ret
}
fn bad(&mut self, msg: &'static str) -> ReturnCode {
#[cfg(all(feature = "std", test))]
dbg!(msg);
self.error_message = Some(msg);
self.inflate_leave(ReturnCode::DataError)
}
// NOTE: it is crucial for the internal bookkeeping that this is the only route for actually
// leaving the inflate function call chain
fn inflate_leave(&mut self, return_code: ReturnCode) -> ReturnCode {
// actual logic is in `inflate` itself
return_code
}
/// Stored in the `z_stream.data_type` field
fn decoding_state(&self) -> i32 {
let bit_reader_bits = self.bit_reader.bits_in_buffer() as i32;
debug_assert!(bit_reader_bits < 64);
let last = if self.flags.contains(Flags::IS_LAST_BLOCK) {
64
} else {
0
};
let mode = match self.mode {
Mode::Type => 128,
Mode::Len_ | Mode::CopyBlock => 256,
_ => 0,
};
bit_reader_bits | last | mode
}
}
fn inflate_fast_help(state: &mut State, start: usize) {
#[cfg(any(target_arch = "x86_64", target_arch = "x86"))]
if crate::cpu_features::is_enabled_avx2_and_bmi2() {
// SAFETY: we've verified the target features
return unsafe { inflate_fast_help_avx2(state, start) };
}
inflate_fast_help_vanilla(state, start);
}
#[cfg(any(target_arch = "x86_64", target_arch = "x86"))]
#[target_feature(enable = "avx2")]
#[target_feature(enable = "bmi2")]
#[target_feature(enable = "bmi1")]
unsafe fn inflate_fast_help_avx2(state: &mut State, start: usize) {
inflate_fast_help_impl::<{ CpuFeatures::AVX2 }>(state, start);
}
fn inflate_fast_help_vanilla(state: &mut State, start: usize) {
inflate_fast_help_impl::<{ CpuFeatures::NONE }>(state, start);
}
#[inline(always)]
fn inflate_fast_help_impl<const FEATURES: usize>(state: &mut State, _start: usize) {
let mut bit_reader = BitReader::new(&[]);
core::mem::swap(&mut bit_reader, &mut state.bit_reader);
let mut writer = Writer::new(&mut []);
core::mem::swap(&mut writer, &mut state.writer);
let lcode = state.len_table_ref();
let dcode = state.dist_table_ref();
// IDEA: use const generics for the bits here?
let lmask = (1u64 << state.len_table.bits) - 1;
let dmask = (1u64 << state.dist_table.bits) - 1;
// TODO verify if this is relevant for us
let extra_safe = false;
let window_size = state.window.size();
let mut bad = None;
if bit_reader.bits_in_buffer() < 10 {
bit_reader.refill();
}
'outer: loop {
let mut here = {
let bits = bit_reader.bits_in_buffer();
let hold = bit_reader.hold();
bit_reader.refill();
// in most cases, the read can be interleaved with the logic
// based on benchmarks this matters in practice. wild.
if bits as usize >= state.len_table.bits {
lcode[(hold & lmask) as usize]
} else {
lcode[(bit_reader.hold() & lmask) as usize]
}
};
if here.op == 0 {
writer.push(here.val as u8);
bit_reader.drop_bits(here.bits);
here = lcode[(bit_reader.hold() & lmask) as usize];
if here.op == 0 {
writer.push(here.val as u8);
bit_reader.drop_bits(here.bits);
here = lcode[(bit_reader.hold() & lmask) as usize];
}
}
'dolen: loop {
bit_reader.drop_bits(here.bits);
let op = here.op;
if op == 0 {
writer.push(here.val as u8);
} else if op & 16 != 0 {
let op = op & MAX_BITS;
let mut len = here.val + bit_reader.bits(op as usize) as u16;
bit_reader.drop_bits(op);
here = dcode[(bit_reader.hold() & dmask) as usize];
// we have two fast-path loads: 10+10 + 15+5 = 40,
// but we may need to refill here in the worst case
if bit_reader.bits_in_buffer() < MAX_BITS + MAX_DIST_EXTRA_BITS {
bit_reader.refill();
}
'dodist: loop {
bit_reader.drop_bits(here.bits);
let op = here.op;
if op & 16 != 0 {
let op = op & MAX_BITS;
let dist = here.val + bit_reader.bits(op as usize) as u16;
if INFLATE_STRICT && dist as usize > state.dmax {
bad = Some("invalid distance too far back\0");
state.mode = Mode::Bad;
break 'outer;
}
bit_reader.drop_bits(op);
// max distance in output
let written = writer.len();
if dist as usize > written {
// copy fropm the window
if (dist as usize - written) > state.window.have() {
if state.flags.contains(Flags::SANE) {
bad = Some("invalid distance too far back\0");
state.mode = Mode::Bad;
break 'outer;
}
panic!("INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR")
}
let mut op = dist as usize - written;
let mut from;
let window_next = state.window.next();
if window_next == 0 {
// This case is hit when the window has just wrapped around
// by logic in `Window::extend`. It is special-cased because
// apparently this is quite common.
//
// the match is at the end of the window, even though the next
// position has now wrapped around.
from = window_size - op;
} else if window_next >= op {
// the standard case: a contiguous copy from the window, no wrapping
from = window_next - op;
} else {
// This case is hit when the window has recently wrapped around
// by logic in `Window::extend`.
//
// The match is (partially) at the end of the window
op -= window_next;
from = window_size - op;
if op < len as usize {
// This case is hit when part of the match is at the end of the
// window, and part of it has wrapped around to the start. Copy
// the end section here, the start section will be copied below.
len -= op as u16;
writer.extend_from_window_with_features::<FEATURES>(
&state.window,
from..from + op,
);
from = 0;
op = window_next;
}
}
let copy = Ord::min(op, len as usize);
writer.extend_from_window_with_features::<FEATURES>(
&state.window,
from..from + copy,
);
if op < len as usize {
// here we need some bytes from the output itself
writer.copy_match_with_features::<FEATURES>(
dist as usize,
len as usize - op,
);
}
} else if extra_safe {
todo!()
} else {
writer.copy_match_with_features::<FEATURES>(dist as usize, len as usize)
}
} else if (op & 64) == 0 {
// 2nd level distance code
here = dcode[(here.val + bit_reader.bits(op as usize) as u16) as usize];
continue 'dodist;
} else {
bad = Some("invalid distance code\0");
state.mode = Mode::Bad;
break 'outer;
}
break 'dodist;
}
} else if (op & 64) == 0 {
// 2nd level length code
here = lcode[(here.val + bit_reader.bits(op as usize) as u16) as usize];
continue 'dolen;
} else if op & 32 != 0 {
// end of block
state.mode = Mode::Type;
break 'outer;
} else {
bad = Some("invalid literal/length code\0");
state.mode = Mode::Bad;
break 'outer;
}
break 'dolen;
}
// include the bits in the bit_reader buffer in the count of available bytes
let remaining = bit_reader.bytes_remaining_including_buffer();
if remaining >= INFLATE_FAST_MIN_HAVE && writer.remaining() >= INFLATE_FAST_MIN_LEFT {
continue;
}
break 'outer;
}
// return unused bytes (on entry, bits < 8, so in won't go too far back)
bit_reader.return_unused_bytes();
state.bit_reader = bit_reader;
state.writer = writer;
if let Some(error_message) = bad {
debug_assert!(matches!(state.mode, Mode::Bad));
state.bad(error_message);
}
}
pub fn prime(stream: &mut InflateStream, bits: i32, value: i32) -> ReturnCode {
if bits == 0 {
/* fall through */
} else if bits < 0 {
stream.state.bit_reader.init_bits();
} else if bits > 16 || stream.state.bit_reader.bits_in_buffer() + bits as u8 > 32 {
return ReturnCode::StreamError;
} else {
stream.state.bit_reader.prime(bits as u8, value as u64);
}
ReturnCode::Ok
}
#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
pub struct InflateConfig {
pub window_bits: i32,
}
impl Default for InflateConfig {
fn default() -> Self {
Self {
window_bits: DEF_WBITS,
}
}
}
/// Initialize the stream in an inflate state
pub fn init(stream: &mut z_stream, config: InflateConfig) -> ReturnCode {
stream.msg = core::ptr::null_mut();
// for safety we must really make sure that alloc and free are consistent
// this is a (slight) deviation from stock zlib. In this crate we pick the rust
// allocator as the default, but `libz-rs-sys` configures the C allocator
#[cfg(feature = "rust-allocator")]
if stream.zalloc.is_none() || stream.zfree.is_none() {
stream.configure_default_rust_allocator()
}
#[cfg(feature = "c-allocator")]
if stream.zalloc.is_none() || stream.zfree.is_none() {
stream.configure_default_c_allocator()
}
if stream.zalloc.is_none() || stream.zfree.is_none() {
return ReturnCode::StreamError;
}
let mut state = State::new(&[], Writer::new(&mut []));
// TODO this can change depending on the used/supported SIMD instructions
state.chunksize = 32;
let alloc = Allocator {
zalloc: stream.zalloc.unwrap(),
zfree: stream.zfree.unwrap(),
opaque: stream.opaque,
_marker: PhantomData,
};
// allocated here to have the same order as zlib
let Some(state_allocation) = alloc.allocate_raw::<State>() else {
return ReturnCode::MemError;
};
// FIXME: write is stable for NonNull since 1.80.0
unsafe { state_allocation.as_ptr().write(state) };
stream.state = state_allocation.as_ptr() as *mut internal_state;
// SAFETY: we've correctly initialized the stream to be an InflateStream
let ret = if let Some(stream) = unsafe { InflateStream::from_stream_mut(stream) } {
reset_with_config(stream, config)
} else {
ReturnCode::StreamError
};
if ret != ReturnCode::Ok {
let ptr = stream.state;
stream.state = core::ptr::null_mut();
// SAFETY: we assume deallocation does not cause UB
unsafe { alloc.deallocate(ptr, 1) };
}
ret
}
pub fn reset_with_config(stream: &mut InflateStream, config: InflateConfig) -> ReturnCode {
let mut window_bits = config.window_bits;
let wrap;
if window_bits < 0 {
wrap = 0;
if window_bits < -MAX_WBITS {
return ReturnCode::StreamError;
}
window_bits = -window_bits;
} else {
wrap = (window_bits >> 4) + 5; // TODO wth?
if window_bits < 48 {
window_bits &= MAX_WBITS;
}
}
if window_bits != 0 && !(MIN_WBITS..=MAX_WBITS).contains(&window_bits) {
#[cfg(feature = "std")]
eprintln!("invalid windowBits");
return ReturnCode::StreamError;
}
if stream.state.window.size() != 0 && stream.state.wbits as i32 != window_bits {
let mut window = Window::empty();
core::mem::swap(&mut window, &mut stream.state.window);
let (ptr, len) = window.into_raw_parts();
assert_ne!(len, 0);
// SAFETY: window is discarded after this deallocation.
unsafe { stream.alloc.deallocate(ptr, len) };
}
stream.state.wrap = wrap as u8;
stream.state.wbits = window_bits as _;
reset(stream)
}
pub fn reset(stream: &mut InflateStream) -> ReturnCode {
// reset the state of the window
stream.state.window.clear();
stream.state.error_message = None;
reset_keep(stream)
}
pub fn reset_keep(stream: &mut InflateStream) -> ReturnCode {
stream.total_in = 0;
stream.total_out = 0;
stream.state.total = 0;
stream.msg = core::ptr::null_mut();
let state = &mut stream.state;
if state.wrap != 0 {
// to support ill-conceived Java test suite
stream.adler = (state.wrap & 1) as _;
}
state.mode = Mode::Head;
state.checksum = crate::ADLER32_INITIAL_VALUE as u32;
state.flags.update(Flags::IS_LAST_BLOCK, false);
state.flags.update(Flags::HAVE_DICT, false);
state.flags.update(Flags::SANE, true);
state.gzip_flags = -1;
state.dmax = 32768;
state.head = None;
state.bit_reader = BitReader::new(&[]);
state.next = 0;
state.len_table = Table::default();
state.dist_table = Table::default();
state.back = usize::MAX;
ReturnCode::Ok
}
pub fn codes_used(stream: &InflateStream) -> usize {
stream.state.next
}
pub unsafe fn inflate(stream: &mut InflateStream, flush: InflateFlush) -> ReturnCode {
if stream.next_out.is_null() || (stream.next_in.is_null() && stream.avail_in != 0) {
return ReturnCode::StreamError as _;
}
let state = &mut stream.state;
// skip check
if let Mode::Type = state.mode {
state.mode = Mode::TypeDo;
}
state.flush = flush;
unsafe {
state
.bit_reader
.update_slice(stream.next_in, stream.avail_in as usize)
};
state.writer = Writer::new_uninit(stream.next_out.cast(), stream.avail_out as usize);
state.in_available = stream.avail_in as _;
state.out_available = stream.avail_out as _;
let mut err = state.dispatch();
let in_read = state.bit_reader.as_ptr() as usize - stream.next_in as usize;
let out_written = state.out_available - (state.writer.capacity() - state.writer.len());
stream.total_in += in_read as z_size;
state.total += out_written;
stream.total_out = state.total as _;
stream.avail_in = state.bit_reader.bytes_remaining() as u32;
stream.next_in = state.bit_reader.as_ptr() as *mut u8;
stream.avail_out = (state.writer.capacity() - state.writer.len()) as u32;
stream.next_out = state.writer.next_out() as *mut u8;
stream.adler = state.checksum as z_checksum;
let valid_mode = |mode| !matches!(mode, Mode::Bad | Mode::Mem | Mode::Sync);
let not_done = |mode| {
!matches!(
mode,
Mode::Check | Mode::Length | Mode::Bad | Mode::Mem | Mode::Sync
)
};
let must_update_window = state.window.size() != 0
|| (out_written != 0
&& valid_mode(state.mode)
&& (not_done(state.mode) || !matches!(state.flush, InflateFlush::Finish)));
let update_checksum = state.wrap & 4 != 0;
if must_update_window {
'blk: {
// initialize the window if needed
if state.window.size() == 0 {
match Window::new_in(&stream.alloc, state.wbits as usize) {
Some(window) => state.window = window,
None => {
state.mode = Mode::Mem;
err = ReturnCode::MemError;
break 'blk;
}
}
}
state.window.extend(
&state.writer.filled()[..out_written],
state.gzip_flags,
update_checksum,
&mut state.checksum,
&mut state.crc_fold,
);
}
}
if let Some(msg) = state.error_message {
assert!(msg.ends_with('\0'));
stream.msg = msg.as_ptr() as *mut u8 as *mut core::ffi::c_char;
}
stream.data_type = state.decoding_state();
if ((in_read == 0 && out_written == 0) || flush == InflateFlush::Finish as _)
&& err == (ReturnCode::Ok as _)
{
ReturnCode::BufError as _
} else {
err as _
}
}
fn syncsearch(mut got: usize, buf: &[u8]) -> (usize, usize) {
let len = buf.len();
let mut next = 0;
while next < len && got < 4 {
if buf[next] == if got < 2 { 0 } else { 0xff } {
got += 1;
} else if buf[next] != 0 {
got = 0;
} else {
got = 4 - got;
}
next += 1;
}
(got, next)
}
pub fn sync(stream: &mut InflateStream) -> ReturnCode {
let state = &mut stream.state;
if stream.avail_in == 0 && state.bit_reader.bits_in_buffer() < 8 {
return ReturnCode::BufError;
}
/* if first time, start search in bit buffer */
if !matches!(state.mode, Mode::Sync) {
state.mode = Mode::Sync;
let (buf, len) = state.bit_reader.start_sync_search();
(state.have, _) = syncsearch(0, &buf[..len]);
}
// search available input
// SAFETY: user guarantees that pointer and length are valid.
let slice = unsafe { core::slice::from_raw_parts(stream.next_in, stream.avail_in as usize) };
let len;
(state.have, len) = syncsearch(state.have, slice);
// SAFETY: syncsearch() returns an index that is in-bounds of the slice.
stream.next_in = unsafe { stream.next_in.add(len) };
stream.avail_in -= len as u32;
stream.total_in += len as z_size;
/* return no joy or set up to restart inflate() on a new block */
if state.have != 4 {
return ReturnCode::DataError;
}
if state.gzip_flags == -1 {
state.wrap = 0; /* if no header yet, treat as raw */
} else {
state.wrap &= !4; /* no point in computing a check value now */
}
let flags = state.gzip_flags;
let total_in = stream.total_in;
let total_out = stream.total_out;
reset(stream);
stream.total_in = total_in;
stream.total_out = total_out;
stream.state.gzip_flags = flags;
stream.state.mode = Mode::Type;
ReturnCode::Ok
}
/*
Returns true if inflate is currently at the end of a block generated by
Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
implementation to provide an additional safety check. PPP uses
Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
block. When decompressing, PPP checks that at the end of input packet,
inflate is waiting for these length bytes.
*/
pub fn sync_point(stream: &mut InflateStream) -> bool {
matches!(stream.state.mode, Mode::Stored) && stream.state.bit_reader.bits_in_buffer() == 0
}
pub unsafe fn copy<'a>(
dest: &mut MaybeUninit<InflateStream<'a>>,
source: &InflateStream<'a>,
) -> ReturnCode {
if source.next_out.is_null() || (source.next_in.is_null() && source.avail_in != 0) {
return ReturnCode::StreamError;
}
// Safety: source and dest are both mutable references, so guaranteed not to overlap.
// dest being a reference to maybe uninitialized memory makes a copy of 1 DeflateStream valid.
unsafe {
core::ptr::copy_nonoverlapping(source, dest.as_mut_ptr(), 1);
}
// allocated here to have the same order as zlib
let Some(state_allocation) = source.alloc.allocate_raw::<State>() else {
return ReturnCode::MemError;
};
let state = &source.state;
// SAFETY: an initialized Writer is a valid MaybeUninit<Writer>.
let writer: MaybeUninit<Writer> =
unsafe { core::ptr::read(&state.writer as *const _ as *const MaybeUninit<Writer>) };
let mut copy = State {
mode: state.mode,
flags: state.flags,
wrap: state.wrap,
len_table: state.len_table,
dist_table: state.dist_table,
wbits: state.wbits,
window: Window::empty(),
head: None,
ncode: state.ncode,
nlen: state.nlen,
ndist: state.ndist,
have: state.have,
next: state.next,
bit_reader: state.bit_reader,
writer: Writer::new(&mut []),
total: state.total,
length: state.length,
offset: state.offset,
extra: state.extra,
back: state.back,
was: state.was,
chunksize: state.chunksize,
in_available: state.in_available,
out_available: state.out_available,
lens: state.lens,
work: state.work,
error_message: state.error_message,
flush: state.flush,
checksum: state.checksum,
crc_fold: state.crc_fold,
dmax: state.dmax,
gzip_flags: state.gzip_flags,
codes_codes: state.codes_codes,
len_codes: state.len_codes,
dist_codes: state.dist_codes,
};
if !state.window.is_empty() {
let Some(window) = state.window.clone_in(&source.alloc) else {
// SAFETY: state_allocation is not used again.
source.alloc.deallocate(state_allocation.as_ptr(), 1);
return ReturnCode::MemError;
};
copy.window = window;
}
// write the cloned state into state_ptr
unsafe { state_allocation.as_ptr().write(copy) }; // FIXME: write is stable for NonNull since 1.80.0
// insert the state_ptr into `dest`
let field_ptr = unsafe { core::ptr::addr_of_mut!((*dest.as_mut_ptr()).state) };
unsafe { core::ptr::write(field_ptr as *mut *mut State, state_allocation.as_ptr()) };
// update the writer; it cannot be cloned so we need to use some shennanigans
let field_ptr = unsafe { core::ptr::addr_of_mut!((*dest.as_mut_ptr()).state.writer) };
unsafe { core::ptr::copy(writer.as_ptr(), field_ptr, 1) };
// update the gzhead field (it contains a mutable reference so we need to be careful
let field_ptr = unsafe { core::ptr::addr_of_mut!((*dest.as_mut_ptr()).state.head) };
unsafe { core::ptr::copy(&source.state.head, field_ptr, 1) };
ReturnCode::Ok
}
pub fn undermine(stream: &mut InflateStream, subvert: i32) -> ReturnCode {
stream.state.flags.update(Flags::SANE, (!subvert) != 0);
ReturnCode::Ok
}
pub fn mark(stream: &InflateStream) -> c_long {
if stream.next_out.is_null() || (stream.next_in.is_null() && stream.avail_in != 0) {
return c_long::MIN;
}
let state = &stream.state;
let length = match state.mode {
Mode::CopyBlock => state.length,
Mode::Match => state.was - state.length,
_ => 0,
};
(((state.back as c_long) as c_ulong) << 16) as c_long + length as c_long
}
pub fn set_dictionary(stream: &mut InflateStream, dictionary: &[u8]) -> ReturnCode {
if stream.state.wrap != 0 && !matches!(stream.state.mode, Mode::Dict) {
return ReturnCode::StreamError;
}
// check for correct dictionary identifier
if matches!(stream.state.mode, Mode::Dict) {
let dictid = adler32(1, dictionary);
if dictid != stream.state.checksum {
return ReturnCode::DataError;
}
}
let err = 'blk: {
// initialize the window if needed
if stream.state.window.size() == 0 {
match Window::new_in(&stream.alloc, stream.state.wbits as usize) {
None => break 'blk ReturnCode::MemError,
Some(window) => stream.state.window = window,
}
}
stream.state.window.extend(
dictionary,
stream.state.gzip_flags,
false,
&mut stream.state.checksum,
&mut stream.state.crc_fold,
);
ReturnCode::Ok
};
if err != ReturnCode::Ok {
stream.state.mode = Mode::Mem;
return ReturnCode::MemError;
}
stream.state.flags.update(Flags::HAVE_DICT, true);
ReturnCode::Ok
}
pub fn end<'a>(stream: &'a mut InflateStream<'a>) -> &'a mut z_stream {
let alloc = stream.alloc;
let mut window = Window::empty();
core::mem::swap(&mut window, &mut stream.state.window);
// safety: window is not used again
if !window.is_empty() {
let (ptr, len) = window.into_raw_parts();
unsafe { alloc.deallocate(ptr, len) };
}
let stream = stream.as_z_stream_mut();
let state_ptr = core::mem::replace(&mut stream.state, core::ptr::null_mut());
// safety: state_ptr is not used again
unsafe { alloc.deallocate(state_ptr as *mut State, 1) };
stream
}
/// # Safety
///
/// The caller must guarantee:
///
/// * If `head` is `Some`:
/// - If `head.extra` is not NULL, it must be writable for at least `head.extra_max` bytes
/// - if `head.name` is not NULL, it must be writable for at least `head.name_max` bytes
/// - if `head.comment` is not NULL, it must be writable for at least `head.comm_max` bytes
pub unsafe fn get_header<'a>(
stream: &mut InflateStream<'a>,
head: Option<&'a mut gz_header>,
) -> ReturnCode {
if (stream.state.wrap & 2) == 0 {
return ReturnCode::StreamError;
}
stream.state.head = head.map(|head| {
head.done = 0;
head
});
ReturnCode::Ok
}
/// # Safety
///
/// The `dictionary` must have enough space for the dictionary.
pub unsafe fn get_dictionary(stream: &InflateStream<'_>, dictionary: *mut u8) -> usize {
let whave = stream.state.window.have();
let wnext = stream.state.window.next();
if !dictionary.is_null() {
unsafe {
core::ptr::copy_nonoverlapping(
stream.state.window.as_ptr().add(wnext),
dictionary,
whave - wnext,
);
core::ptr::copy_nonoverlapping(
stream.state.window.as_ptr(),
dictionary.add(whave).sub(wnext).cast(),
wnext,
);
}
}
stream.state.window.have()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn uncompress_buffer_overflow() {
let mut output = [0; 1 << 13];
let input = [
72, 137, 58, 0, 3, 39, 255, 255, 255, 255, 255, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 184, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 184, 14, 14,
14, 14, 14, 14, 14, 63, 14, 14, 14, 14, 14, 14, 14, 14, 184, 14, 14, 255, 14, 103, 14,
14, 14, 14, 14, 14, 61, 14, 255, 255, 63, 14, 14, 14, 14, 14, 14, 14, 14, 184, 14, 14,
255, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 6, 14, 14, 14, 14, 14, 14, 14, 14, 71,
4, 137, 106,
];
let config = InflateConfig { window_bits: 15 };
let (_decompressed, err) = uncompress_slice(&mut output, &input, config);
assert_eq!(err, ReturnCode::DataError);
}
}