Skip to content

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

14.3 KB
Raw Blame
//! Quantisation, scalefactor selection, codebook/section selection, bit counting and writing of one
//! `individual_channel_stream`.
//!
//! Coefficients are kept in bitstream order ("interleaved": group → band → window → line), so every
//! (group, band) is a contiguous slice and short-window grouping needs no special casing.

use filmcraft_bitstream::BitWriter;

use crate::huffman::{self, ZERO_HCB};
use crate::ics::IcsInfo;
use crate::tables::pow43;
use crate::tns::TnsData;

/// Magic rounding offset for AAC quantisation (`0.5 - 0.0946`), minimising the error for the
/// `x^(3/4)` companding.
const ROUND: f32 = 0.4054;
const MAX_Q: i32 = 8191;

/// One (group, band) of a channel, in bitstream order.
#[derive(Clone, Copy, Debug)]
pub struct Band {
    /// Range in the interleaved coefficient array.
    pub start: usize,
    pub end: usize,
    /// Allowed noise energy at λ = 1.
    pub thr: f32,
    /// Coefficient energy.
    pub en: f32,
    /// Largest `|x|^(3/4)`.
    pub max34: f32,
}

/// Everything the rate loop needs for one channel.
pub struct ChannelInput {
    pub info: IcsInfo,
    /// Interleaved (bitstream-order) coefficients.
    pub x: Vec<f32>,
    pub xabs: Vec<f32>,
    pub x34: Vec<f32>,
    pub bands: Vec<Band>,
    pub tns: Option<TnsData>,
}

impl ChannelInput {
    /// `spec` is window-major (short windows at stride 128); `thr[g][sfb]` and the grouping come from
    /// `info`.
    pub fn new(info: IcsInfo, swb: &[u16], spec: &[f32], thr: &[Vec<f32>], tns: Option<TnsData>) -> ChannelInput {
        let mut x = Vec::with_capacity(1024);
        let mut bands = Vec::new();
        for g in 0..info.num_groups {
            let w0 = info.group_start(g);
            for sfb in 0..info.max_sfb {
                let start = x.len();
                for w in w0..w0 + info.group_len[g] as usize {
                    x.extend_from_slice(&spec[w * 128 + swb[sfb] as usize..w * 128 + swb[sfb + 1] as usize]);
                }
                bands.push(Band { start, end: x.len(), thr: thr[g][sfb], en: 0.0, max34: 0.0 });
            }
        }
        let xabs: Vec<f32> = x.iter().map(|v| v.abs()).collect();
        let x34: Vec<f32> = xabs.iter().map(|v| v.powf(0.75)).collect();
        for b in &mut bands {
            b.en = x[b.start..b.end].iter().map(|v| v * v).sum();
            b.max34 = x34[b.start..b.end].iter().cloned().fold(0.0, f32::max);
        }
        ChannelInput { info, x, xabs, x34, bands, tns }
    }
}

/// A quantised channel ready to be written.
#[derive(Clone, Default)]
pub struct QuantChannel {
    pub q: Vec<i32>,
    /// Scalefactor per band (only meaningful where `cb != 0`).
    pub sf: Vec<i32>,
    pub cb: Vec<u8>,
    /// Per group: (codebook, number of bands).
    pub sections: Vec<Vec<(u8, usize)>>,
    pub global_gain: i32,
    /// Bits of the ICS excluding `ics_info`.
    pub bits: u32,
}

#[inline]
fn gain34(sf: i32) -> f32 {
    (-0.1875 * (sf as f32 - 100.0)).exp2()
}
#[inline]
fn gain(sf: i32) -> f32 {
    (0.25 * (sf as f32 - 100.0)).exp2()
}

/// Quantise a slice at `sf`, returning the distortion; writes the (signed) values to `out` if given.
fn quantise(x: &[f32], xabs: &[f32], x34: &[f32], sf: i32, out: Option<&mut [i32]>) -> f32 {
    let g34 = gain34(sf);
    let g = gain(sf);
    let mut d = 0f32;
    match out {
        Some(out) => {
            for i in 0..x.len() {
                let q = ((x34[i] * g34 + ROUND) as i32).min(MAX_Q);
                let e = xabs[i] - pow43(q as u32) * g;
                d += e * e;
                out[i] = if x[i] < 0.0 { -q } else { q };
            }
        }
        None => {
            for i in 0..x.len() {
                let q = ((x34[i] * g34 + ROUND) as i32).min(MAX_Q);
                let e = xabs[i] - pow43(q as u32) * g;
                d += e * e;
            }
        }
    }
    d
}

/// Largest scalefactor whose distortion stays within `allowed`.
fn search_sf(ch: &ChannelInput, b: &Band, allowed: f32) -> i32 {
    let r = b.start..b.end;
    let (x, xa, x34) = (&ch.x[r.clone()], &ch.xabs[r.clone()], &ch.x34[r]);
    let l2 = b.max34.log2();
    let lo = ((100.0 - ((MAX_Q as f32 + 0.5).log2() - l2) / 0.1875).ceil() as i32).clamp(0, 255);
    let zero = ((100.0 - ((1.0 - ROUND).log2() - l2) / 0.1875).floor() as i32 + 1).clamp(0, 256);
    let mut a = lo;
    let mut hi = (zero - 1).clamp(lo, 255);
    if quantise(x, xa, x34, a, None) > allowed {
        return a;
    }
    while a < hi {
        let mid = (a + hi + 1) / 2;
        if quantise(x, xa, x34, mid, None) <= allowed {
            a = mid;
        } else {
            hi = mid - 1;
        }
    }
    a
}

/// Candidate codebooks for a band whose largest magnitude is `m` (0 for all-zero bands).
fn candidates(m: i32) -> &'static [u8] {
    match m {
        0 => &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
        1 => &[1, 2, 3, 4, 5, 6],
        2 => &[3, 4, 5, 6, 7, 8],
        3..=4 => &[5, 6, 7, 8, 9, 10],
        5..=7 => &[7, 8, 9, 10, 11],
        8..=12 => &[9, 10, 11],
        _ => &[11],
    }
}

/// Bring the scalefactor differences between coded bands (`sf >= 0`) within ±60 by lowering the
/// offenders, sweeping up and down until stable.
fn limit_sf_steps(sf: &mut [i32]) {
    let coded: Vec<usize> = (0..sf.len()).filter(|&i| sf[i] >= 0).collect();
    for _ in 0..8 {
        let mut changed = false;
        for w in coded.windows(2) {
            if sf[w[1]] > sf[w[0]] + 60 {
                sf[w[1]] = sf[w[0]] + 60;
                changed = true;
            }
        }
        for w in coded.windows(2).rev() {
            if sf[w[0]] > sf[w[1]] + 60 {
                sf[w[0]] = sf[w[1]] + 60;
                changed = true;
            }
        }
        if !changed {
            break;
        }
    }
}

/// Quantise every band at its scalefactor into `q`, recording each band's largest magnitude in
/// `maxq`. A band that quantises to all zeros leaves the chain (`sf = -1`); returns whether any did.
fn quantise_bands(ch: &ChannelInput, sf: &mut [i32], q: &mut [i32], maxq: &mut [i32]) -> bool {
    let mut removed = false;
    for (i, b) in ch.bands.iter().enumerate() {
        let r = b.start..b.end;
        if sf[i] < 0 {
            q[r].fill(0);
            maxq[i] = 0;
            continue;
        }
        quantise(&ch.x[r.clone()], &ch.xabs[r.clone()], &ch.x34[r.clone()], sf[i], Some(&mut q[r.clone()]));
        maxq[i] = q[r].iter().map(|v| v.abs()).max().unwrap_or(0);
        if maxq[i] == 0 {
            sf[i] = -1;
            removed = true;
        }
    }
    removed
}

/// Cost sentinel for a codebook that cannot code a band.
const INF: u32 = u32::MAX / 4;

/// Bits to code each band of a group with each codebook (`INF` when the codebook cannot).
fn codebook_costs(ch: &ChannelInput, q: &[i32], maxq: &[i32], base: usize, n: usize) -> Vec<[u32; 12]> {
    let mut cost = vec![[INF; 12]; n];
    for i in 0..n {
        let bi = base + i;
        let b = &ch.bands[bi];
        let vals = &q[b.start..b.end];
        for &c in candidates(maxq[bi]) {
            cost[i][c as usize] = if c == 0 {
                0
            } else {
                // all-zero band inside a coded section also needs a (zero) scalefactor difference
                huffman::count_bits(c, vals) + if maxq[bi] == 0 { 1 } else { 0 }
            };
        }
    }
    cost
}

/// Dynamic programming over the codebook of each band of a group, charging `new_sec` bits for every
/// section start. Returns the chosen codebook per band.
fn best_codebooks(cost: &[[u32; 12]], new_sec: u32) -> Vec<u8> {
    let n = cost.len();
    let mut best = [INF; 12];
    let mut back = vec![[0u8; 12]; n];
    for c in 0..12 {
        if cost[0][c] < INF {
            best[c] = new_sec + cost[0][c];
        }
    }
    for i in 1..n {
        let (mut min_c, mut min_v) = (0usize, INF);
        for c in 0..12 {
            if best[c] < min_v {
                min_v = best[c];
                min_c = c;
            }
        }
        let mut nb_ = [INF; 12];
        for c in 0..12 {
            if cost[i][c] >= INF {
                continue;
            }
            let stay = best[c];
            let switch = min_v + new_sec;
            if stay <= switch {
                nb_[c] = stay + cost[i][c];
                back[i][c] = c as u8;
            } else {
                nb_[c] = switch + cost[i][c];
                back[i][c] = min_c as u8;
            }
        }
        best = nb_;
    }
    let mut cbs = vec![0u8; n];
    let mut c = (0..12).min_by_key(|&c| best[c]).unwrap_or(0);
    for i in (0..n).rev() {
        cbs[i] = c as u8;
        c = back[i][c] as usize;
    }
    cbs
}

/// Run-length encode a group's codebooks into `(codebook, length)` sections, and sum the spectral
/// bits of its non-zero sections. `base` is the index of the group's first band.
fn group_sections(ch: &ChannelInput, q: &[i32], cbs: &[u8], base: usize) -> (Vec<(u8, usize)>, u32) {
    let mut secs: Vec<(u8, usize)> = Vec::new();
    let mut spectral_bits = 0u32;
    for (i, &c) in cbs.iter().enumerate() {
        match secs.last_mut() {
            Some((lc, len)) if *lc == c => *len += 1,
            _ => secs.push((c, 1)),
        }
        if c != ZERO_HCB {
            let b = &ch.bands[base + i];
            spectral_bits += huffman::count_bits(c, &q[b.start..b.end]);
        }
    }
    (secs, spectral_bits)
}

/// Section selection: a codebook per band, the sections of each group and the bits they cost
/// `(codebooks, sections, spectral_bits, section_bits)`.
fn select_sections(ch: &ChannelInput, q: &[i32], maxq: &[i32]) -> (Vec<u8>, Vec<Vec<(u8, usize)>>, u32, u32) {
    let info = &ch.info;
    let (sect_bits, esc) = if info.is_short() { (3u32, 7usize) } else { (5u32, 31usize) };
    let mut cb = vec![ZERO_HCB; ch.bands.len()];
    let mut sections = Vec::with_capacity(info.num_groups);
    let mut spectral_bits = 0u32;
    let mut section_bits = 0u32;
    let n = info.max_sfb;
    for g in 0..info.num_groups {
        let base = g * n;
        if n == 0 {
            sections.push(Vec::new());
            continue;
        }
        let cost = codebook_costs(ch, q, maxq, base, n);
        cb[base..base + n].copy_from_slice(&best_codebooks(&cost, 4 + sect_bits));
        let (secs, bits) = group_sections(ch, q, &cb[base..base + n], base);
        spectral_bits += bits;
        for &(_, len) in &secs {
            section_bits += 4 + sect_bits * (len / esc + 1) as u32;
        }
        sections.push(secs);
    }
    (cb, sections, spectral_bits, section_bits)
}

/// Quantise one channel at rate-distortion multiplier `lambda` and select sections.
pub fn quantise_channel(ch: &ChannelInput, lambda: f32) -> QuantChannel {
    let nb = ch.bands.len();
    let mut sf = vec![-1i32; nb];
    for (i, b) in ch.bands.iter().enumerate() {
        let allowed = lambda * b.thr;
        if b.max34 <= 0.0 || b.en <= allowed {
            continue;
        }
        sf[i] = search_sf(ch, b, allowed);
    }
    // Scalefactor differences between coded bands must stay within ±60: lower (refine) offenders,
    // then quantise; repeat if a band unexpectedly quantised to all zeros (it leaves the chain).
    let mut q = vec![0i32; ch.x.len()];
    let mut maxq = vec![0i32; nb];
    loop {
        limit_sf_steps(&mut sf);
        if !quantise_bands(ch, &mut sf, &mut q, &mut maxq) {
            break;
        }
    }

    let (cb, sections, spectral_bits, section_bits) = select_sections(ch, &q, &maxq);

    // Scalefactors: global gain is the first coded band's value; bands coded with a non-zero
    // codebook but all-zero values reuse the previous value (difference 0).
    let first = (0..nb).find(|&i| sf[i] >= 0).map(|i| sf[i]).unwrap_or(100);
    let mut prev = first;
    let mut sf_bits = 0u32;
    for i in 0..nb {
        if cb[i] == ZERO_HCB {
            continue;
        }
        if sf[i] < 0 {
            sf[i] = prev;
        }
        sf_bits += huffman::sf_bits(sf[i] - prev);
        prev = sf[i];
    }
    let tns_bits = 1 + ch.tns.as_ref().map(|t| t.bit_count(&ch.info)).unwrap_or(0);
    let bits = 8 + section_bits + sf_bits + 1 + tns_bits + 1 + spectral_bits;
    QuantChannel { q, sf, cb, sections, global_gain: first, bits }
}

/// Write an `individual_channel_stream`; `write_info` is false inside a common-window CPE.
pub fn write_ics(bw: &mut BitWriter, ch: &ChannelInput, qc: &QuantChannel, write_info: bool) {
    let info = &ch.info;
    bw.write_bits(qc.global_gain as u32, 8);
    if write_info {
        info.write(bw);
    }
    let (sect_bits, esc) = if info.is_short() { (3u32, 7usize) } else { (5u32, 31usize) };
    for secs in &qc.sections {
        for &(c, len) in secs {
            bw.write_bits(c as u32, 4);
            let mut l = len;
            while l >= esc {
                bw.write_bits(esc as u32, sect_bits);
                l -= esc;
            }
            bw.write_bits(l as u32, sect_bits);
        }
    }
    let mut prev = qc.global_gain;
    for i in 0..ch.bands.len() {
        if qc.cb[i] == ZERO_HCB {
            continue;
        }
        huffman::write_sf(bw, qc.sf[i] - prev);
        prev = qc.sf[i];
    }
    bw.write_bits(0, 1); // pulse_data_present
    match &ch.tns {
        Some(t) => {
            bw.write_bits(1, 1);
            t.write(bw, info);
        }
        None => bw.write_bits(0, 1),
    }
    bw.write_bits(0, 1); // gain_control_data_present
    for (i, b) in ch.bands.iter().enumerate() {
        if qc.cb[i] != ZERO_HCB {
            huffman::write_spectral(bw, qc.cb[i], &qc.q[b.start..b.end]);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::ics::WindowSequence;
    use crate::mdct::WindowShape;
    use crate::tables::swb_offsets_long;
    use filmcraft_bitstream::BitWriter;

    #[test]
    fn bit_count_matches_written_bits() {
        let swb = swb_offsets_long(4);
        let info = IcsInfo { window_sequence: WindowSequence::OnlyLong, window_shape: WindowShape::Sine, max_sfb: 40, ..Default::default() };
        let spec: Vec<f32> = (0..1024).map(|i| ((i * 7919 % 1000) as f32 - 500.0) * (1000.0 / (i as f32 + 10.0))).collect();
        let thr = vec![vec![1000.0f32; 64]];
        let ch = ChannelInput::new(info, swb, &spec, &thr, None);
        for lambda in [0.01f32, 1.0, 100.0, 1e5] {
            let qc = quantise_channel(&ch, lambda);
            let mut bw = BitWriter::new();
            write_ics(&mut bw, &ch, &qc, false);
            assert_eq!(bw.bit_len() as u32, qc.bits, "lambda {lambda}");
        }
    }
}