chapter_tgz/

encode.rs

use crate::decode;

pub(crate) const MAX_BYTES_FINAL: usize = 28;
pub(crate) const MAX_BYTES_NONFINAL: usize = 23;

pub(crate) struct Bits {
    bitpos: u8,
    packed: [u8; MAX_BYTES_FINAL],
}

impl Bits {
    pub(crate) const fn new() -> Self {
        Bits {
            bitpos: 0,
            packed: [0u8; MAX_BYTES_FINAL],
        }
    }

    pub(crate) const fn push(&mut self, val: u8, len: u8) {
        self.packed[(self.bitpos / 8) as usize] |= val << (self.bitpos % 8);
        if val.leading_zeros() < (self.bitpos % 8) as u32 {
            self.packed[(self.bitpos / 8 + 1) as usize] |= val >> (8 - self.bitpos % 8);
        }
        self.bitpos += len;
    }

    pub(crate) fn as_slice(&self) -> &[u8] {
        &self.packed[..self.bitpos.div_ceil(8) as usize]
    }
}

macro_rules! push {
    ($bits:ident, $($lit:literal)+) => {
        $(
            $bits.push(
                const {
                    match u8::from_str_radix(stringify!($lit), 2) {
                        Ok(val) => val,
                        Err(_) => panic!(),
                    }
                },
                stringify!($lit).len() as u8,
            );
        )+
    };
}

pub(crate) fn encode(bfinal: bool, payload: u64) -> Bits {
    assert_ne!(payload, 0);

    let mut bits = Bits::new();
    bits.push(u8::from(bfinal), 1); // BFINAL
    push!(bits, 10); // BTYPE (dynamic)
    push!(bits, 00000); // HLIT (257+0)
    push!(bits, 00000); // HDIST (1+0)
    push!(bits, 1110); // HCLEN (4+14);

    // Code lengths for the code length alphabet
    push!(bits, 000); // 16 -> none (copy the previous code length 3 - 6 times)
    push!(bits, 001); // 17 -> '0' (repeat a code length of 0 for 3 - 10 times)
    push!(bits, 010); // 18 -> '11' (repeat a code length of 0 for 11 - 138 times)
    push!(bits, 000); // 0 -> none
    push!(bits, 000); // 8 -> none
    push!(bits, 000); // 7 -> none
    push!(bits, 000); // 9 -> none
    push!(bits, 000); // 6 -> none
    push!(bits, 000); // 10 -> none
    push!(bits, 000); // 5 -> none
    push!(bits, 000); // 11 -> none
    push!(bits, 000); // 4 -> none
    push!(bits, 000); // 12 -> none
    push!(bits, 000); // 3 -> none
    push!(bits, 000); // 13 -> none
    push!(bits, 000); // 2 -> none
    push!(bits, 000); // 14 -> none
    push!(bits, 010); // 1 -> '01'

    /*
    push!(bits, 000); // 15 -> none
    */

    // Code lengths for the literal/length alphabet
    let mut rest = payload;
    let mut zeros = 0;
    while rest != 0 {
        push!(bits, 0);
        bits.push(rest as u8 & 0b111, 3);
        zeros += 3 + (rest & 0b111);
        rest >>= 3;
    }
    match zeros {
        4..=97 => {
            // two big repetitions, at least 21 zeros in the second; 18 bits
            push!(bits, 11 1111111);
            push!(bits, 11);
            bits.push((256 - (zeros + 138) - 11) as u8, 7);
        }
        98..=107 => {
            // one big, two little repetitions; 17 bits
            push!(bits, 11);
            bits.push((256 - (zeros + 20) - 11) as u8, 7);
            push!(bits, 0 111);
            push!(bits, 0 111);
        }
        108..=117 => {
            // one big, one little repetition; 13 bits
            push!(bits, 11);
            bits.push((256 - (zeros + 10) - 11) as u8, 7);
            push!(bits, 0 111);
        }
        118..=214 => {
            // one big repetition; 9 bits
            push!(bits, 11);
            bits.push((256 - zeros - 11) as u8, 7);
        }
        0..=3 | 215.. => {
            // payload=1 => zeros=4
            // payload=max => zeros=214
            unreachable!()
        }
    }

    push!(bits, 01); // len=8 for symbol=256

    // Code lengths for the distance alphabet
    push!(bits, 01); // len=8 for distance=1

    // End of block (symbol 256)
    push!(bits, 0);

    assert!(bits.as_slice().starts_with(&decode::prefix(bfinal)));

    // Pad to a multiple of 8 bits
    if !bfinal {
        match bits.bitpos % 8 {
            0 => {}
            n @ (1..=5 | 7) => {
                push!(bits, 0); // BFINAL
                push!(bits, 00); // BTYPE (stored)
                bits.push(0, (13 - n) % 8); // pad
                push!(bits, 00000000 00000000); // LEN
                push!(bits, 11111111 11111111); // NLEN
            }
            6 => {
                push!(bits, 0); // BFINAL
                push!(bits, 01); // BTYPE (fixed)
                push!(bits, 0000000); // end-of-block
            }
            8.. => unreachable!(),
        }
    }

    bits
}