mod bits;
mod huffman;
use bits::BitReader;
use huffman::Huffman;
use crate::{GitError, Result, error::invalid};
const LENGTH_BASE: [usize; 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 LENGTH_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: [usize; 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, 12_289, 16_385, 24_577,
];
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,
];
pub(crate) fn zlib(input: &[u8], limit: usize) -> Result<(Vec<u8>, usize)> {
if input.len() < 6 {
return Err(invalid("truncated zlib stream"));
}
let cmf = input[0];
let flg = input[1];
if cmf & 0x0f != 8 || cmf >> 4 > 7 || (u16::from(cmf) * 256 + u16::from(flg)) % 31 != 0 {
return Err(invalid("invalid zlib header"));
}
if flg & 0x20 != 0 {
return Err(GitError::Unsupported("preset zlib dictionaries".to_owned()));
}
let mut reader = BitReader::new(&input[2..]);
let mut output = Vec::new();
loop {
let final_block = reader.read(1)? != 0;
match reader.read(2)? {
0 => stored(&mut reader, &mut output, limit)?,
1 => {
let (literal, distance) = fixed_tables()?;
compressed(&mut reader, &literal, &distance, &mut output, limit)?;
}
2 => {
let (literal, distance) = dynamic_tables(&mut reader)?;
compressed(&mut reader, &literal, &distance, &mut output, limit)?;
}
_ => return Err(invalid("reserved DEFLATE block type")),
}
if final_block {
break;
}
}
reader.align_byte();
let trailer = 2 + reader.byte_position();
let adler_bytes = input
.get(trailer..trailer + 4)
.ok_or_else(|| invalid("truncated zlib checksum"))?;
let expected = u32::from_be_bytes(adler_bytes.try_into().expect("four bytes"));
if adler32(&output) != expected {
return Err(invalid("zlib Adler-32 mismatch"));
}
Ok((output, trailer + 4))
}
fn stored(reader: &mut BitReader<'_>, output: &mut Vec<u8>, limit: usize) -> Result<()> {
reader.align_byte();
let length = usize::try_from(reader.read(16)?).map_err(|_| invalid("length overflow"))?;
let inverse = reader.read(16)?;
if u32::try_from(length).unwrap_or(u32::MAX) ^ inverse != 0xffff {
return Err(invalid("stored DEFLATE length mismatch"));
}
ensure_capacity(output.len(), length, limit)?;
for _ in 0..length {
output.push(u8::try_from(reader.read(8)?).expect("eight bits"));
}
Ok(())
}
fn fixed_tables() -> Result<(Huffman, Huffman)> {
let mut literal = vec![0_u8; 288];
literal[..144].fill(8);
literal[144..256].fill(9);
literal[256..280].fill(7);
literal[280..].fill(8);
Ok((Huffman::new(&literal)?, Huffman::new(&[5; 32])?))
}
fn dynamic_tables(reader: &mut BitReader<'_>) -> Result<(Huffman, Huffman)> {
let literal_count = usize::try_from(reader.read(5)? + 257).expect("bounded");
let distance_count = usize::try_from(reader.read(5)? + 1).expect("bounded");
let code_count = usize::try_from(reader.read(4)? + 4).expect("bounded");
let order = [
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
];
let mut code_lengths = [0_u8; 19];
for symbol in order.into_iter().take(code_count) {
code_lengths[symbol] = u8::try_from(reader.read(3)?).expect("three bits");
}
let code_table = Huffman::new(&code_lengths)?;
let total = literal_count + distance_count;
let mut lengths = Vec::with_capacity(total);
while lengths.len() < total {
match code_table.decode(reader)? {
value @ 0..=15 => lengths.push(u8::try_from(value).expect("bounded")),
16 => {
let previous = *lengths
.last()
.ok_or_else(|| invalid("repeat without code"))?;
repeat(&mut lengths, previous, reader.read(2)? + 3, total)?;
}
17 => repeat(&mut lengths, 0, reader.read(3)? + 3, total)?,
18 => repeat(&mut lengths, 0, reader.read(7)? + 11, total)?,
_ => return Err(invalid("invalid code-length symbol")),
}
}
if lengths[256] == 0 {
return Err(invalid("DEFLATE literal tree has no end marker"));
}
Ok((
Huffman::new(&lengths[..literal_count])?,
Huffman::new(&lengths[literal_count..])?,
))
}
fn repeat(output: &mut Vec<u8>, value: u8, count: u32, limit: usize) -> Result<()> {
let count = usize::try_from(count).map_err(|_| invalid("repeat overflow"))?;
if output.len() + count > limit {
return Err(invalid("code-length repeat exceeds table"));
}
output.resize(output.len() + count, value);
Ok(())
}
fn compressed(
reader: &mut BitReader<'_>,
literal: &Huffman,
distance: &Huffman,
output: &mut Vec<u8>,
limit: usize,
) -> Result<()> {
loop {
match literal.decode(reader)? {
value @ 0..=255 => {
ensure_capacity(output.len(), 1, limit)?;
output.push(u8::try_from(value).expect("literal"));
}
256 => return Ok(()),
value @ 257..=285 => {
let index = usize::from(value - 257);
let length = LENGTH_BASE[index]
+ usize::try_from(reader.read(LENGTH_EXTRA[index])?).expect("bounded");
let symbol = usize::from(distance.decode(reader)?);
if symbol >= DIST_BASE.len() {
return Err(invalid("reserved DEFLATE distance symbol"));
}
let distance = DIST_BASE[symbol]
+ usize::try_from(reader.read(DIST_EXTRA[symbol])?).expect("bounded");
if distance == 0 || distance > output.len() {
return Err(invalid("DEFLATE distance exceeds output"));
}
ensure_capacity(output.len(), length, limit)?;
for _ in 0..length {
output.push(output[output.len() - distance]);
}
}
_ => return Err(invalid("reserved DEFLATE literal symbol")),
}
}
}
fn ensure_capacity(current: usize, added: usize, limit: usize) -> Result<()> {
if current.checked_add(added).is_none_or(|size| size > limit) {
return Err(GitError::LimitExceeded {
resource: "inflated object bytes",
limit,
});
}
Ok(())
}
fn adler32(bytes: &[u8]) -> u32 {
let (mut a, mut b) = (1_u32, 0_u32);
for chunk in bytes.chunks(5_552) {
for byte in chunk {
a += u32::from(*byte);
b += a;
}
a %= 65_521;
b %= 65_521;
}
b << 16 | a
}
#[cfg(test)]
mod tests {
use super::zlib;
#[test]
fn inflates_fixed_zlib_stream() {
let input = [
0x78, 0x9c, 0xcb, 0x48, 0xcd, 0xc9, 0xc9, 0x07, 0, 6, 0x2c, 2, 0x15,
];
let (value, used) = zlib(&input, 100).unwrap();
assert_eq!(value, b"hello");
assert_eq!(used, input.len());
}
#[test]
fn inflates_stored_zlib_stream() {
let input = [
0x78, 0x01, 0x01, 5, 0, 0xfa, 0xff, b'h', b'e', b'l', b'l', b'o', 6, 0x2c, 2, 0x15,
];
assert_eq!(zlib(&input, 5).unwrap().0, b"hello");
}
#[test]
fn rejects_headers_checksums_dictionaries_and_limits() {
assert!(zlib(&[], 10).is_err());
assert!(zlib(&[0; 6], 10).is_err());
assert!(zlib(&[0x78, 0x20, 0, 0, 0, 0], 10).is_err());
let mut input = [
0x78, 0x9c, 0xcb, 0x48, 0xcd, 0xc9, 0xc9, 0x07, 0, 6, 0x2c, 2, 0x15,
];
assert!(zlib(&input, 4).is_err());
input[12] ^= 1;
assert!(zlib(&input, 10).is_err());
}
}