Skip to content

FilmCraft: An open-source, nonlinear video editor written by scratch in pure Rust

6.7 KB
Raw Blame
//! Boolean entropy decoder (RFC 6386 section 7).
//!
//! The specification keeps two bytes of the input in `value` and shifts in one byte every eight
//! renormalisation steps. This implementation keeps the active bits at the top of a 64-bit window
//! whose lower bits hold the next bytes of the input, which is equivalent and refills only every
//! few bytes. Reading past the end of the data yields zero bits.

pub struct BoolDecoder<'a> {
    data: &'a [u8],
    pos: usize,
    /// The bits being decoded, most significant first: the top 8 bits correspond to the
    /// specification's `value >> 8`, followed by `count` further bits of input.
    value: u64,
    count: i32,
    range: u32,
}

impl<'a> BoolDecoder<'a> {
    pub fn new(data: &'a [u8]) -> Self {
        let mut d = BoolDecoder { data, pos: 0, value: 0, count: -8, range: 255 };
        d.fill();
        d
    }

    fn fill(&mut self) {
        let mut shift = 48 - self.count;
        while shift >= 0 {
            match self.data.get(self.pos) {
                Some(&b) => {
                    self.pos += 1;
                    self.value |= u64::from(b) << shift;
                    self.count += 8;
                    shift -= 8;
                }
                None => {
                    // past the end: zero bits for as long as anyone reads
                    self.count += 0x4000;
                    return;
                }
            }
        }
    }

    /// `read_bool` (7.3): a bool whose probability of being zero is `p / 256`.
    #[inline(always)]
    pub fn read_bool(&mut self, p: u8) -> bool {
        let split = 1 + (((self.range - 1) * u32::from(p)) >> 8);
        if self.count < 0 {
            self.fill();
        }
        let big_split = u64::from(split) << 56;
        let bit = if self.value >= big_split {
            self.range -= split;
            self.value -= big_split;
            true
        } else {
            self.range = split;
            false
        };
        // renormalise: shift until range >= 128
        let shift = self.range.leading_zeros().saturating_sub(24);
        self.range <<= shift;
        self.value <<= shift;
        self.count -= shift as i32;
        bit
    }

    /// `read_literal` (7.3): an `n`-bit unsigned value, most significant bit first, each bit at
    /// probability 1/2.
    #[inline]
    pub fn read_literal(&mut self, n: u32) -> u32 {
        let mut v = 0;
        for _ in 0..n {
            v = (v << 1) | u32::from(self.read_bool(128));
        }
        v
    }

    /// An `L(1)` flag.
    #[inline]
    pub fn read_flag(&mut self) -> bool {
        self.read_bool(128)
    }

    /// A magnitude `L(n)` followed by a sign `L(1)` (1 = negative), as the frame header codes its
    /// signed fields.
    pub fn read_signed(&mut self, n: u32) -> i32 {
        let v = self.read_literal(n) as i32;
        if self.read_flag() { -v } else { v }
    }

    /// An optional signed field: a flag, then [`Self::read_signed`] when it is set, else 0.
    pub fn read_optional_signed(&mut self, n: u32) -> i32 {
        if self.read_flag() { self.read_signed(n) } else { 0 }
    }

    /// `treed_read` (8.1): a tree-coded value. `tree` uses the specification's layout: positive
    /// entries index deeper nodes, non-positive entries `-v` are leaves of value `v`; `probs[i]`
    /// is the probability of node `2 * i`.
    #[inline]
    pub fn read_tree(&mut self, tree: &[i8], probs: &[u8]) -> u8 {
        self.read_tree_from(tree, probs, 0)
    }

    /// [`Self::read_tree`] starting at node `start` instead of the root.
    #[inline]
    pub fn read_tree_from(&mut self, tree: &[i8], probs: &[u8], start: usize) -> u8 {
        let mut i = start;
        loop {
            let p = probs.get(i >> 1).copied().unwrap_or(128);
            let next = tree.get(i + usize::from(self.read_bool(p))).copied().unwrap_or(0);
            if next <= 0 {
                return (-next) as u8;
            }
            i = next as usize;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// The encoder of section 7.3, to round-trip the decoder.
    struct BoolEncoder {
        out: Vec<u8>,
        range: u32,
        bottom: u32,
        bit_count: i32,
    }

    impl BoolEncoder {
        fn new() -> Self {
            BoolEncoder { out: Vec::new(), range: 255, bottom: 0, bit_count: 24 }
        }
        fn add_one(&mut self) {
            let mut i = self.out.len();
            while i > 0 {
                i -= 1;
                if self.out[i] == 255 {
                    self.out[i] = 0;
                } else {
                    self.out[i] += 1;
                    break;
                }
            }
        }
        fn write(&mut self, p: u8, bit: bool) {
            let split = 1 + (((self.range - 1) * u32::from(p)) >> 8);
            if bit {
                self.bottom = self.bottom.wrapping_add(split);
                self.range -= split;
            } else {
                self.range = split;
            }
            while self.range < 128 {
                self.range <<= 1;
                if self.bottom & (1 << 31) != 0 {
                    self.add_one();
                }
                self.bottom <<= 1;
                self.bit_count -= 1;
                if self.bit_count == 0 {
                    self.out.push((self.bottom >> 24) as u8);
                    self.bottom &= (1 << 24) - 1;
                    self.bit_count = 8;
                }
            }
        }
        fn finish(mut self) -> Vec<u8> {
            let mut c = self.bit_count;
            let mut v = self.bottom;
            if v & (1u32.wrapping_shl((32 - c) as u32)) != 0 {
                self.add_one();
            }
            v <<= c & 7;
            c >>= 3;
            while c > 0 {
                c -= 1;
                v <<= 8;
            }
            for _ in 0..4 {
                self.out.push((v >> 24) as u8);
                v <<= 8;
            }
            self.out
        }
    }

    #[test]
    fn round_trips_bools_at_every_probability() {
        let mut seed = 0x1234_5678u32;
        let mut rnd = || {
            seed ^= seed << 13;
            seed ^= seed >> 17;
            seed ^= seed << 5;
            seed
        };
        let bits: Vec<(u8, bool)> = (0..20_000).map(|_| (((rnd() % 255) + 1) as u8, rnd() % 3 == 0)).collect();
        let mut e = BoolEncoder::new();
        for &(p, b) in &bits {
            e.write(p, b);
        }
        let data = e.finish();
        let mut d = BoolDecoder::new(&data);
        for (i, &(p, b)) in bits.iter().enumerate() {
            assert_eq!(d.read_bool(p), b, "bool {i}");
        }
    }

    #[test]
    fn reads_zeros_past_the_end() {
        let mut d = BoolDecoder::new(&[]);
        for _ in 0..1000 {
            assert!(!d.read_bool(128));
        }
    }
}