#[must_use]
pub fn zlib_deflate(data: &[u8]) -> Vec<u8> {
let mut out = vec![0x78, 0x01];
deflate_fixed(&mut out, data);
out.extend_from_slice(&adler32(data).to_be_bytes());
out
}
#[cfg(test)]
pub fn zlib_inflate(src: &[u8]) -> Result<Vec<u8>, &'static str> {
if src.len() < 6 {
return Err("zlib too short");
}
let cmf = src[0];
let flg = src[1];
if (u16::from(cmf) * 256 + u16::from(flg)) % 31 != 0 {
return Err("zlib FCHECK");
}
if cmf & 0x0f != 8 {
return Err("zlib CM");
}
if flg & 0x20 != 0 {
return Err("zlib dict");
}
let body = &src[2..src.len() - 4];
let got = u32::from_be_bytes(src[src.len() - 4..].try_into().map_err(|_| "zlib adler")?);
let raw = inflate_deflate(body)?;
if adler32(&raw) != got {
return Err("zlib adler mismatch");
}
Ok(raw)
}
pub(crate) fn adler32(data: &[u8]) -> u32 {
let mut a = 1u32;
let mut b = 0u32;
for &byte in data {
a += u32::from(byte);
if a >= 65521 {
a -= 65521;
}
b += a;
if b >= 65521 {
b -= 65521;
}
}
(b << 16) | a
}
fn deflate_fixed(out: &mut Vec<u8>, data: &[u8]) {
let mut bw = BitWriter::new(out);
bw.bits(0b011, 3);
let mut i = 0usize;
let mut head = [u32::MAX; HASH];
while i < data.len() {
let mut best_len = 0u32;
let mut best_dist = 0u32;
if i + MIN_MATCH <= data.len() {
let h = hash3(&data[i..]);
let prev = head[h];
if prev != u32::MAX {
let dist = i as u32 - prev;
if dist > 0 && dist <= MAX_DIST {
let p = prev as usize;
let max = (data.len() - i).min(MAX_MATCH);
let mut n = 0usize;
while n < max && data[p + n] == data[i + n] {
n += 1;
}
if n >= MIN_MATCH {
best_len = n as u32;
best_dist = dist;
}
}
}
head[h] = i as u32;
}
if best_len >= MIN_MATCH as u32 {
write_len(&mut bw, best_len);
write_dist(&mut bw, best_dist);
let end = i + best_len as usize;
i += 1;
while i < end && i + MIN_MATCH <= data.len() {
head[hash3(&data[i..])] = i as u32;
i += 1;
}
i = end;
} else {
write_lit(&mut bw, u16::from(data[i]));
i += 1;
}
}
write_lit(&mut bw, 256);
bw.flush();
}
const HASH: usize = 1 << 12;
const MIN_MATCH: usize = 3;
const MAX_MATCH: usize = 258;
const MAX_DIST: u32 = 32_768;
fn hash3(b: &[u8]) -> usize {
let x = u32::from(b[0]) | (u32::from(b[1]) << 8) | (u32::from(b[2]) << 16);
(x.wrapping_mul(0x1e35_a7bd) >> (32 - 12)) as usize
}
fn write_lit(bw: &mut BitWriter<'_>, lit: u16) {
if lit <= 143 {
bw.bits(revbits(u32::from(lit) + 0x30, 8), 8);
} else if lit <= 255 {
bw.bits(revbits(u32::from(lit) - 144 + 0x190, 9), 9);
} else if lit <= 279 {
bw.bits(revbits(u32::from(lit) - 256, 7), 7);
} else {
bw.bits(revbits(u32::from(lit) - 280 + 0xc0, 8), 8);
}
}
fn write_len(bw: &mut BitWriter<'_>, len: u32) {
let (sym, extra_n, extra) = length_sym(len);
write_lit(bw, sym);
if extra_n > 0 {
bw.bits(extra, extra_n);
}
}
fn write_dist(bw: &mut BitWriter<'_>, dist: u32) {
let (sym, extra_n, extra) = dist_sym(dist);
bw.bits(revbits(sym, 5), 5);
if extra_n > 0 {
bw.bits(extra, extra_n);
}
}
fn length_sym(len: u32) -> (u16, u32, u32) {
debug_assert!((3..=258).contains(&len));
if len == 258 {
return (285, 0, 0);
}
let l = len - 3;
if l < 8 {
return (257 + l as u16, 0, 0);
}
let mut extra = 1u32;
let mut base = 8u32;
let mut sym = 265u16;
loop {
let span = 1u32 << extra;
if l < base + span * 4 {
let slot = (l - base) >> extra;
let lo = base + (slot << extra);
return (sym + slot as u16, extra, l - lo);
}
base += span * 4;
extra += 1;
sym += 4;
if extra > 5 {
return (285, 0, 0);
}
}
}
fn dist_sym(dist: u32) -> (u32, u32, u32) {
debug_assert!((1..=MAX_DIST).contains(&dist));
let d = dist - 1;
if d < 4 {
return (d, 0, 0);
}
let mut extra = 1u32;
let mut base = 4u32;
let mut sym = 4u32;
loop {
let span = 1u32 << extra;
if d < base + span * 2 {
let slot = (d - base) >> extra;
let lo = base + (slot << extra);
return (sym + slot, extra, d - lo);
}
base += span * 2;
extra += 1;
sym += 2;
if extra > 13 {
return (29, 13, d.saturating_sub(24576));
}
}
}
fn revbits(mut v: u32, n: u32) -> u32 {
let mut r = 0u32;
for _ in 0..n {
r = (r << 1) | (v & 1);
v >>= 1;
}
r
}
struct BitWriter<'a> {
out: &'a mut Vec<u8>,
acc: u32,
n: u32,
}
impl<'a> BitWriter<'a> {
fn new(out: &'a mut Vec<u8>) -> Self {
Self { out, acc: 0, n: 0 }
}
fn bits(&mut self, val: u32, nbits: u32) {
self.acc |= val << self.n;
self.n += nbits;
while self.n >= 8 {
self.out.push(self.acc as u8);
self.acc >>= 8;
self.n -= 8;
}
}
fn flush(&mut self) {
if self.n > 0 {
self.out.push(self.acc as u8);
self.acc = 0;
self.n = 0;
}
}
}
#[cfg(test)]
fn inflate_deflate(src: &[u8]) -> Result<Vec<u8>, &'static str> {
let mut br = BitReader::new(src);
let mut out = Vec::new();
loop {
let bfinal = br.bit()?;
let btype = br.bits(2)?;
match btype {
0 => inflate_stored(&mut br, &mut out)?,
1 => inflate_fixed(&mut br, &mut out)?,
2 => return Err("dynamic huffman"),
_ => return Err("bad btype"),
}
if bfinal != 0 {
break;
}
}
Ok(out)
}
#[cfg(test)]
fn inflate_stored(br: &mut BitReader<'_>, out: &mut Vec<u8>) -> Result<(), &'static str> {
br.byte_align();
let len = br.bits(16)? as u16;
let nlen = br.bits(16)? as u16;
if len != !nlen {
return Err("stored nlen");
}
for _ in 0..len {
out.push(br.bits(8)? as u8);
}
Ok(())
}
#[cfg(test)]
fn inflate_fixed(br: &mut BitReader<'_>, out: &mut Vec<u8>) -> Result<(), &'static str> {
loop {
let sym = read_fixed_lit(br)?;
match sym {
0..=255 => out.push(sym as u8),
256 => return Ok(()),
257..=285 => {
let len = decode_length(sym, br)?;
let dsym = revbits(br.bits(5)?, 5);
let dist = decode_dist(dsym, br)?;
if dist == 0 || dist as usize > out.len() {
return Err("bad dist");
}
for _ in 0..len {
let b = out[out.len() - dist as usize];
out.push(b);
}
}
_ => return Err("bad lit"),
}
}
}
#[cfg(test)]
fn read_fixed_lit(br: &mut BitReader<'_>) -> Result<u16, &'static str> {
let mut code = 0u32;
for _ in 0..7 {
code = (code << 1) | br.bit()?;
}
if code <= 23 {
return Ok(256 + code as u16);
}
code = (code << 1) | br.bit()?;
if (48..192).contains(&code) {
return Ok((code - 48) as u16);
}
if (192..200).contains(&code) {
return Ok((code - 192 + 280) as u16);
}
code = (code << 1) | br.bit()?;
if (400..512).contains(&code) {
return Ok((code - 400 + 144) as u16);
}
Err("bad fixed lit")
}
#[cfg(test)]
fn decode_length(sym: u16, br: &mut BitReader<'_>) -> Result<u32, &'static str> {
if (257..265).contains(&sym) {
return Ok(u32::from(sym - 257) + 3);
}
if sym == 285 {
return Ok(258);
}
if !(265..=284).contains(&sym) {
return Err("len sym");
}
let extra = ((sym - 261) / 4) as u32;
let base = match extra {
1 => 11,
2 => 19,
3 => 35,
4 => 67,
5 => 131,
_ => return Err("len extra"),
};
let slot = u32::from((sym - 265) % 4);
Ok(base + (slot << extra) + br.bits(extra)?)
}
#[cfg(test)]
fn decode_dist(sym: u32, br: &mut BitReader<'_>) -> Result<u32, &'static str> {
if sym <= 3 {
return Ok(sym + 1);
}
if sym > 29 {
return Err("dist sym");
}
let extra = (sym - 2) / 2;
let base = match extra {
1 => 5,
2 => 9,
3 => 17,
4 => 33,
5 => 65,
6 => 129,
7 => 257,
8 => 513,
9 => 1025,
10 => 2049,
11 => 4097,
12 => 8193,
13 => 16385,
_ => return Err("dist extra"),
};
let slot = (sym - 4) % 2;
Ok(base + (slot << extra) + br.bits(extra)?)
}
#[cfg(test)]
struct BitReader<'a> {
src: &'a [u8],
i: usize,
acc: u32,
n: u32,
}
#[cfg(test)]
impl<'a> BitReader<'a> {
fn new(src: &'a [u8]) -> Self {
Self {
src,
i: 0,
acc: 0,
n: 0,
}
}
fn bit(&mut self) -> Result<u32, &'static str> {
self.bits(1)
}
fn bits(&mut self, nbits: u32) -> Result<u32, &'static str> {
while self.n < nbits {
if self.i >= self.src.len() {
return Err("truncated");
}
self.acc |= u32::from(self.src[self.i]) << self.n;
self.i += 1;
self.n += 8;
}
let v = self.acc & ((1u32 << nbits) - 1);
self.acc >>= nbits;
self.n -= nbits;
Ok(v)
}
fn byte_align(&mut self) {
self.acc = 0;
self.n = 0;
}
}
#[cfg(test)]
mod tests {
use super::*;
fn roundtrip(data: &[u8]) {
let z = zlib_deflate(data);
let back = zlib_inflate(&z).expect("inflate");
assert_eq!(back, data, "len {}", data.len());
}
#[test]
fn empty() {
roundtrip(b"");
}
#[test]
fn small_literals() {
roundtrip(b"hello");
roundtrip(&[0, 1, 2, 3, 255, 144, 143, 200]);
}
#[test]
fn repeats() {
roundtrip(&[0x0bu8, 0x0d, 0x10].repeat(800));
roundtrip(&vec![7u8; 4000]);
}
#[test]
fn length_table_spot() {
assert_eq!(length_sym(3), (257, 0, 0));
assert_eq!(length_sym(10), (264, 0, 0));
assert_eq!(length_sym(11), (265, 1, 0));
assert_eq!(length_sym(12), (265, 1, 1));
assert_eq!(length_sym(258), (285, 0, 0));
}
#[test]
fn dist_table_spot() {
assert_eq!(dist_sym(1), (0, 0, 0));
assert_eq!(dist_sym(4), (3, 0, 0));
assert_eq!(dist_sym(5), (4, 1, 0));
assert_eq!(dist_sym(6), (4, 1, 1));
}
#[test]
fn all_byte_values() {
let v: Vec<u8> = (0..=255).collect();
roundtrip(&v);
}
#[test]
fn length_dist_roundtrip_sizes() {
for n in [3usize, 4, 10, 11, 12, 18, 19, 50, 258, 400, 2000] {
roundtrip(&vec![0xABu8; n]);
}
let mut d = (0u8..=40).collect::<Vec<_>>();
d.extend_from_slice(&d.clone());
roundtrip(&d);
}
}