f67d38b35cc5
inflate.rs
//! zlib / DEFLATE decompression (RFC 1950 / RFC 1951), written from the RFCs for OpenEXR's ZIP
//! compression. Every input is hostile: truncated streams, invalid codes, distances before the start
//! and output beyond the caller's limit are errors, never panics.
/// Why a stream did not decompress.
pub type Error = &'static str;
/// Inflate a zlib stream (RFC 1950: two-byte header, DEFLATE data, Adler-32 trailer) into exactly
/// `expected` bytes. The trailer is not checked: the caller verifies the size, and EXR's own
/// structure catches corruption.
pub fn zlib(src: &[u8], expected: usize) -> Result<Vec<u8>, Error> {
let (&cmf, &flg) = match src {
[a, b, ..] => (a, b),
_ => return Err("truncated zlib header"),
};
if cmf & 0x0F != 8 || cmf >> 4 > 7 || (u16::from(cmf) << 8 | u16::from(flg)) % 31 != 0 {
return Err("not a zlib stream");
}
if flg & 0x20 != 0 {
return Err("zlib preset dictionary");
}
let out = inflate(src.get(2..).unwrap_or_default(), expected)?;
if out.len() != expected {
return Err("zlib stream ends early");
}
Ok(out)
}
/// Inflate raw DEFLATE data, producing at most `limit` bytes (more is an error).
pub fn inflate(src: &[u8], limit: usize) -> Result<Vec<u8>, Error> {
let mut bits = Bits { src, pos: 0, buf: 0, cnt: 0 };
let mut out = Vec::new();
out.try_reserve_exact(limit).map_err(|_| "output too large to allocate")?;
let mut fixed: Option<(Huffman, Huffman)> = None;
loop {
let last = bits.take(1)? == 1;
match bits.take(2)? {
0 => stored(&mut bits, &mut out, limit)?,
1 => {
let (lit, dist) = match &fixed {
Some(t) => t,
None => fixed.insert(fixed_tables()?),
};
codes(&mut bits, &mut out, limit, lit, dist)?;
}
2 => {
let (lit, dist) = dynamic_tables(&mut bits)?;
codes(&mut bits, &mut out, limit, &lit, &dist)?;
}
_ => return Err("invalid deflate block type"),
}
if last {
return Ok(out);
}
}
}
/// LSB-first bit reader.
struct Bits<'a> {
src: &'a [u8],
pos: usize,
buf: u64,
cnt: u32,
}
impl Bits<'_> {
fn refill(&mut self) {
while self.cnt <= 56 {
let Some(&b) = self.src.get(self.pos) else { return };
self.buf |= u64::from(b) << self.cnt;
self.pos += 1;
self.cnt += 8;
}
}
/// The next `n` (≤ 32) bits without consuming them; zeros past the end of the input.
fn peek(&mut self, n: u32) -> u32 {
self.refill();
(self.buf & ((1u64 << n) - 1)) as u32
}
fn consume(&mut self, n: u32) -> Result<(), Error> {
if n > self.cnt {
return Err("truncated deflate stream");
}
self.buf >>= n;
self.cnt -= n;
Ok(())
}
fn take(&mut self, n: u32) -> Result<u32, Error> {
let v = self.peek(n);
self.consume(n)?;
Ok(v)
}
}
/// A stored (uncompressed) block.
fn stored(bits: &mut Bits, out: &mut Vec<u8>, limit: usize) -> Result<(), Error> {
bits.consume(bits.cnt % 8)?;
let len = bits.take(16)?;
if len != !bits.take(16)? & 0xFFFF {
return Err("stored block length mismatch");
}
if out.len().saturating_add(len as usize) > limit {
return Err("deflate output exceeds the expected size");
}
for _ in 0..len {
out.push(bits.take(8)? as u8);
}
Ok(())
}
/// Codes of up to this many bits decode with one table lookup; longer ones walk the canonical code.
const FAST_BITS: u32 = 10;
const MAX_BITS: usize = 15;
/// A canonical Huffman code (RFC 1951 §3.2.2).
struct Huffman {
/// Indexed by the next `FAST_BITS` input bits: `symbol << 4 | length`, 0 when the code is longer
/// (or unassigned).
fast: Vec<u16>,
/// Number of codes of each length.
count: [u16; MAX_BITS + 1],
/// Symbols ordered by code (length, then symbol value).
symbols: Vec<u16>,
}
impl Huffman {
/// Build from per-symbol code lengths (0 = unused). Over-subscribed lengths are an error;
/// incomplete codes are allowed (an unassigned code is an error when it is met).
fn new(lengths: &[u8]) -> Result<Self, Error> {
let mut count = [0u16; MAX_BITS + 1];
for &l in lengths {
let c = count.get_mut(usize::from(l)).ok_or("code length over 15")?;
*c += 1;
}
count[0] = 0;
let mut left: i32 = 1;
for &c in &count[1..] {
left = (left << 1) - i32::from(c);
if left < 0 {
return Err("over-subscribed Huffman code");
}
}
// first index into `symbols` and first code of each length
let mut offs = [0usize; MAX_BITS + 2];
let mut next = [0u32; MAX_BITS + 2];
let mut code = 0u32;
for len in 1..=MAX_BITS {
offs[len + 1] = offs[len] + usize::from(count[len]);
code = (code + u32::from(count[len - 1])) << 1;
next[len] = code;
}
let mut symbols = vec![0u16; offs[MAX_BITS + 1]];
let mut fast = vec![0u16; 1 << FAST_BITS];
for (sym, &l) in lengths.iter().enumerate() {
let len = usize::from(l);
if len == 0 {
continue;
}
if let Some(s) = symbols.get_mut(offs[len]) {
*s = sym as u16;
}
offs[len] += 1;
let c = next[len];
next[len] += 1;
if len as u32 <= FAST_BITS {
// codes are sent MSB first; the reader sees them bit-reversed
let rev = c.reverse_bits() >> (32 - len as u32);
let entry = (sym as u16) << 4 | len as u16;
let mut i = rev as usize;
while let Some(e) = fast.get_mut(i) {
*e = entry;
i += 1 << len;
}
}
}
Ok(Self { fast, count, symbols })
}
fn decode(&self, bits: &mut Bits) -> Result<u16, Error> {
let peek = bits.peek(MAX_BITS as u32);
let e = self.fast.get((peek & ((1 << FAST_BITS) - 1)) as usize).copied().unwrap_or(0);
if e != 0 {
bits.consume(u32::from(e & 15))?;
return Ok(e >> 4);
}
// canonical walk: codes of each length are consecutive, starting at `first`
let (mut code, mut first, mut index) = (0i32, 0i32, 0i32);
for len in 1..=MAX_BITS {
code |= ((peek >> (len - 1)) & 1) as i32;
let count = i32::from(self.count[len]);
if code - first < count {
bits.consume(len as u32)?;
return self.symbols.get((index + code - first) as usize).copied().ok_or("invalid Huffman code");
}
index += count;
first = (first + count) << 1;
code <<= 1;
}
Err("invalid Huffman code")
}
}
fn fixed_tables() -> Result<(Huffman, Huffman), Error> {
let mut lit = [8u8; 288];
lit[144..256].fill(9);
lit[256..280].fill(7);
Ok((Huffman::new(&lit)?, Huffman::new(&[5; 30])?))
}
/// Order in which code-length code lengths are sent.
const CL_ORDER: [usize; 19] = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];
fn dynamic_tables(bits: &mut Bits) -> Result<(Huffman, Huffman), Error> {
let nlit = bits.take(5)? as usize + 257;
let ndist = bits.take(5)? as usize + 1;
let ncl = bits.take(4)? as usize + 4;
if nlit > 286 || ndist > 30 {
return Err("too many deflate codes");
}
let mut cl = [0u8; 19];
for &i in CL_ORDER.iter().take(ncl) {
cl[i] = bits.take(3)? as u8;
}
let clh = Huffman::new(&cl)?;
let mut lengths = vec![0u8; nlit + ndist];
let mut i = 0;
while i < lengths.len() {
let sym = clh.decode(bits)?;
let (value, repeat) = match sym {
0..=15 => (sym as u8, 1),
16 => {
let prev = *lengths.get(i.wrapping_sub(1)).ok_or("repeat with no previous length")?;
(prev, 3 + bits.take(2)? as usize)
}
17 => (0, 3 + bits.take(3)? as usize),
18 => (0, 11 + bits.take(7)? as usize),
_ => return Err("invalid code length symbol"),
};
let run = lengths.get_mut(i..i + repeat).ok_or("code lengths overflow")?;
run.fill(value);
i += repeat;
}
let (lit, dist) = lengths.split_at(nlit);
if lit.get(256).copied().unwrap_or(0) == 0 {
return Err("no end-of-block code");
}
Ok((Huffman::new(lit)?, Huffman::new(dist)?))
}
const LEN_BASE: [u16; 29] = [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];
const LEN_EXTRA: [u8; 29] = [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];
const DIST_BASE: [u16; 30] =
[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, 12289, 16385, 24577];
const DIST_EXTRA: [u8; 30] = [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];
/// The literal / length and distance codes of one compressed block.
fn codes(bits: &mut Bits, out: &mut Vec<u8>, limit: usize, lit: &Huffman, dist: &Huffman) -> Result<(), Error> {
loop {
let sym = lit.decode(bits)?;
if sym < 256 {
if out.len() >= limit {
return Err("deflate output exceeds the expected size");
}
out.push(sym as u8);
continue;
}
if sym == 256 {
return Ok(());
}
let k = usize::from(sym - 257);
let (&base, &extra) = LEN_BASE.get(k).zip(LEN_EXTRA.get(k)).ok_or("invalid length code")?;
let len = usize::from(base) + bits.take(u32::from(extra))? as usize;
let d = usize::from(dist.decode(bits)?);
let (&base, &extra) = DIST_BASE.get(d).zip(DIST_EXTRA.get(d)).ok_or("invalid distance code")?;
let distance = usize::from(base) + bits.take(u32::from(extra))? as usize;
if distance > out.len() {
return Err("distance before the start of the output");
}
if out.len().saturating_add(len) > limit {
return Err("deflate output exceeds the expected size");
}
let from = out.len() - distance;
if distance >= len {
out.extend_from_within(from..from + len);
} else {
// overlapping copy: repeats the last `distance` bytes
for j in 0..len {
let b = out.get(from + j).copied().unwrap_or(0);
out.push(b);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
// Vectors made with Python's zlib (an external tool; the bytes are data).
/// `zlib.compress(b"hello hello hello hello", 9)`: one fixed-Huffman block with a back reference.
const FIXED: &[u8] = &[0x78, 0xda, 0xcb, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0xc8, 0x40, 0x27, 0x01, 0x68, 0x03, 0x08, 0xb1];
#[test]
fn fixed_block() {
assert_eq!(zlib(FIXED, 23).unwrap(), b"hello hello hello hello");
}
#[test]
fn stored_block() {
// zlib header, one final stored block of 3 bytes, Adler-32
let s = [0x78, 0x01, 0x01, 0x03, 0x00, 0xfc, 0xff, b'a', b'b', b'c', 0x02, 0x4d, 0x01, 0x27];
assert_eq!(zlib(&s, 3).unwrap(), b"abc");
}
/// `zlib.compressobj(9)` of the 300 bytes `(i*i*7 + i/3) % 23 + 65`: one dynamic-Huffman block.
const DYNAMIC: &[u8] = &[
0x78, 0xda, 0xe5, 0xcc, 0x01, 0x11, 0xc0, 0x20, 0x08, 0x00, 0xc0, 0x6c, 0x6c, 0x22, 0x70, 0x0a, 0xe2, 0xa1, 0xd0, 0xbf, 0xc9, 0x82, 0xec, 0x03, 0x3c,
0x70, 0x8f, 0xf4, 0x07, 0x2c, 0xac, 0x60, 0x9d, 0xdd, 0xf0, 0x36, 0xd0, 0xc5, 0x6e, 0x2f, 0x81, 0x48, 0xbe, 0xc9, 0x5c, 0x08, 0x53, 0x71, 0xca, 0x29,
0xaf, 0x1c, 0x26, 0xdb, 0x69, 0x74, 0x77, 0x52, 0x89, 0xab, 0xb1, 0x91, 0xe0, 0x1f, 0xc9, 0x07, 0x4a, 0xb8, 0x58, 0xfe,
];
#[test]
fn dynamic_block() {
let want: Vec<u8> = (0..300usize).map(|i| ((i * i * 7 + i / 3) % 23 + 65) as u8).collect();
assert_eq!(zlib(DYNAMIC, 300).unwrap(), want);
}
#[test]
fn garbage_never_panics() {
for seed in 1u32..3000 {
let mut x = seed.wrapping_mul(2_654_435_761);
let v: Vec<u8> = (0..64)
.map(|_| {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
x as u8
})
.collect();
let _ = inflate(&v, 4096);
}
// every truncation and single-byte corruption of a real stream
for n in 0..DYNAMIC.len() {
let _ = zlib(&DYNAMIC[..n], 300);
let mut v = DYNAMIC.to_vec();
v[n] ^= 0x5A;
let _ = zlib(&v, 300);
}
}
#[test]
fn hostile_streams_are_errors() {
assert!(zlib(&[], 1).is_err());
assert!(zlib(&[0x78, 0x9c], 1).is_err()); // header only
assert!(zlib(&FIXED[..8], 23).is_err()); // truncated
assert!(zlib(FIXED, 5).is_err()); // more output than allowed
assert!(zlib(FIXED, 30).is_err()); // less output than expected
assert!(zlib(&[0x78, 0x01, 0x07], 1).is_err()); // reserved block type
// distance 1 with no output yet: fixed block, length code 257, distance code 0
assert!(inflate(&[0x03, 0x02], 16).is_err());
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.