Struct BitWriter 

struct BitWriter {
    bytes: Vec<u8>,
    last: u8,
    w: u32,
}

Fields

bytes: Vec<u8>

last: u8

w: u32

Implementations

impl BitWriter

fn push_bit(&mut self, b: bool)

Examples found in repository

crates/competitive/src/tools/coding.rs (line 259)

    fn output_tree(t: &HuffmanTree, buf: &mut BitWriter) {
        match t {
            HuffmanTree::Leaf(i) => {
                buf.push_bit(false);
                buf.push_u8(*i);
            }
            HuffmanTree::Node(l, r) => {
                buf.push_bit(true);
                output_tree(l, buf);
                output_tree(r, buf);
            }
        }
    }

fn push_u8(&mut self, b: u8)

Examples found in repository

crates/competitive/src/tools/coding.rs (line 260)

    fn output_tree(t: &HuffmanTree, buf: &mut BitWriter) {
        match t {
            HuffmanTree::Leaf(i) => {
                buf.push_bit(false);
                buf.push_u8(*i);
            }
            HuffmanTree::Node(l, r) => {
                buf.push_bit(true);
                output_tree(l, buf);
                output_tree(r, buf);
            }
        }
    }

fn push_u64(&mut self, b: u64, c: u32)

Examples found in repository

crates/competitive/src/tools/coding.rs (line 309)

fn huffman_coding(bytes: &[u8]) -> Vec<u8> {
    fn make_table(t: &HuffmanTree, code: u64, len: u32, table: &mut [(u64, u32)]) {
        match t {
            HuffmanTree::Leaf(i) => {
                table[*i as usize] = (code, len.max(1));
            }
            HuffmanTree::Node(l, r) => {
                make_table(l, code << 1, len + 1, table);
                make_table(r, (code << 1) | 1, len + 1, table);
            }
        }
    }
    fn output_tree(t: &HuffmanTree, buf: &mut BitWriter) {
        match t {
            HuffmanTree::Leaf(i) => {
                buf.push_bit(false);
                buf.push_u8(*i);
            }
            HuffmanTree::Node(l, r) => {
                buf.push_bit(true);
                output_tree(l, buf);
                output_tree(r, buf);
            }
        }
    }

    let mut freq = [0usize; 256];
    for &b in &bytes.len().to_le_bytes() {
        freq[b as usize] += 1;
    }
    for &b in bytes {
        freq[b as usize] += 1;
    }
    let mut heap = BinaryHeap::new();
    for (i, &f) in freq.iter().enumerate() {
        if f > 0 {
            heap.push(Reverse((f, 0usize, HuffmanTree::Leaf(i as _))));
        }
    }
    let t = if heap.is_empty() {
        HuffmanTree::Node(
            Box::new(HuffmanTree::Leaf(0)),
            Box::new(HuffmanTree::Leaf(0)),
        )
    } else {
        loop {
            let Reverse((f, c, t)) = heap.pop().unwrap();
            if let Some(Reverse((ff, cc, tt))) = heap.pop() {
                heap.push(Reverse((
                    f + ff,
                    c.max(cc) + 1,
                    HuffmanTree::Node(Box::new(t), Box::new(tt)),
                )));
            } else {
                break t;
            }
        }
    };

    let mut table = vec![(0u64, 0u32); 256];
    make_table(&t, 0, 0, &mut table);
    let mut buf = BitWriter::default();
    output_tree(&t, &mut buf);
    for &b in &bytes.len().to_le_bytes() {
        let (x, y) = table[b as usize];
        buf.push_u64(x, y);
    }
    for &b in bytes {
        let (x, y) = table[b as usize];
        buf.push_u64(x, y);
    }
    buf.into_inner()
}

fn into_inner(self) -> Vec<u8>

Examples found in repository

crates/competitive/src/tools/coding.rs (line 315)

fn huffman_coding(bytes: &[u8]) -> Vec<u8> {
    fn make_table(t: &HuffmanTree, code: u64, len: u32, table: &mut [(u64, u32)]) {
        match t {
            HuffmanTree::Leaf(i) => {
                table[*i as usize] = (code, len.max(1));
            }
            HuffmanTree::Node(l, r) => {
                make_table(l, code << 1, len + 1, table);
                make_table(r, (code << 1) | 1, len + 1, table);
            }
        }
    }
    fn output_tree(t: &HuffmanTree, buf: &mut BitWriter) {
        match t {
            HuffmanTree::Leaf(i) => {
                buf.push_bit(false);
                buf.push_u8(*i);
            }
            HuffmanTree::Node(l, r) => {
                buf.push_bit(true);
                output_tree(l, buf);
                output_tree(r, buf);
            }
        }
    }

    let mut freq = [0usize; 256];
    for &b in &bytes.len().to_le_bytes() {
        freq[b as usize] += 1;
    }
    for &b in bytes {
        freq[b as usize] += 1;
    }
    let mut heap = BinaryHeap::new();
    for (i, &f) in freq.iter().enumerate() {
        if f > 0 {
            heap.push(Reverse((f, 0usize, HuffmanTree::Leaf(i as _))));
        }
    }
    let t = if heap.is_empty() {
        HuffmanTree::Node(
            Box::new(HuffmanTree::Leaf(0)),
            Box::new(HuffmanTree::Leaf(0)),
        )
    } else {
        loop {
            let Reverse((f, c, t)) = heap.pop().unwrap();
            if let Some(Reverse((ff, cc, tt))) = heap.pop() {
                heap.push(Reverse((
                    f + ff,
                    c.max(cc) + 1,
                    HuffmanTree::Node(Box::new(t), Box::new(tt)),
                )));
            } else {
                break t;
            }
        }
    };

    let mut table = vec![(0u64, 0u32); 256];
    make_table(&t, 0, 0, &mut table);
    let mut buf = BitWriter::default();
    output_tree(&t, &mut buf);
    for &b in &bytes.len().to_le_bytes() {
        let (x, y) = table[b as usize];
        buf.push_u64(x, y);
    }
    for &b in bytes {
        let (x, y) = table[b as usize];
        buf.push_u64(x, y);
    }
    buf.into_inner()
}

Trait Implementations

impl Debug for BitWriter

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for BitWriter

fn default() -> Self

Returns the “default value” for a type.