Skip to main content

threers_codec/
rate.rs

1//! Average-bitrate control for the all-intra encoders.
2//!
3//! Both native encoders take a quantizer, not a bitrate: you say how hard to
4//! quantize and find out afterwards how big the file is. That is the wrong way
5//! round for the question people actually ask, which is "make this fit in ten
6//! megabytes".
7//!
8//! Intra pictures follow a rate law simple enough to steer by:
9//!
10//! ```text
11//! log2(bytes) ≈ k − slope · qp
12//! ```
13//!
14//! `k` describes the *content* — how much there is to code — and `slope` how
15//! fast the encoder gives it up. A controller that learns both from what it has
16//! already coded can invert the law to pick the next quantizer.
17//!
18//! The obvious value for `slope` is 1/6: the quantizer step doubles every six
19//! QP, so the rate should halve. It does not. Measured on this encoder the
20//! slope is about **0.116**, nearer 1/8.6 — coefficients that quantize to zero
21//! stop costing anything at all, and the residual's entropy does not fall as
22//! fast as its magnitude. Assuming 1/6 makes the controller under-correct, and
23//! it undershot a 20 Mbit/s target by half before this was measured rather than
24//! assumed. So the slope is learned too, from pairs of frames coded at
25//! different quantizers, and 1/6 appears nowhere.
26//!
27//! It is single-pass by design. A second pass would be more accurate, and for
28//! all-intra content it would be easy, but it doubles the encode time to buy an
29//! accuracy the measurements below suggest is not needed.
30
31/// What a caller wants from the encoder.
32#[derive(Clone, Copy, Debug)]
33pub enum Quality {
34    /// A fixed quantizer: predictable quality, unpredictable size.
35    Qp(i32),
36    /// A target average bitrate in bits per second: predictable size,
37    /// quality that moves with the content.
38    Bitrate(u64),
39}
40
41/// Why a bitrate target cannot be met.
42#[derive(Clone, Copy, Debug)]
43pub enum Reach {
44    /// The content is too detailed: even the coarsest quantizer overshoots.
45    TooComplex {
46        /// How many times larger than the target the coarsest encode is.
47        times: f64,
48    },
49    /// The content is too simple: even the finest quantizer undershoots.
50    TooSimple {
51        /// How many times smaller than the target the finest encode is.
52        times: f64,
53    },
54}
55
56/// Tracks the rate law and picks a quantizer per frame.
57#[derive(Debug)]
58pub struct RateControl {
59    /// Bytes per frame the clip is aiming at.
60    target: f64,
61    /// The content constant: `log2(bytes) + slope·qp`, learned as frames go by.
62    k: f64,
63    /// How much `log2(bytes)` falls per step of quantizer, also learned.
64    slope: f64,
65    /// The last observation, to estimate the slope from a pair.
66    last: Option<(f64, f64)>,
67    /// How many slope measurements have been made.
68    pairs: u32,
69    /// The quantizer last handed out, to limit how far the next one may move.
70    prev_qp: Option<i32>,
71    /// How many observations have gone into `k`.
72    seen: u32,
73    /// Bytes emitted so far.
74    spent: f64,
75    /// Frames emitted so far.
76    done: u32,
77    /// Total frames, when the caller knows. Without it the controller spreads
78    /// its correction over a fixed horizon instead of over what is left.
79    total: Option<u32>,
80    qp_min: i32,
81    qp_max: i32,
82    /// Whether the controller ever ran out of quantizer in either direction.
83    pinned_coarse: bool,
84    pinned_fine: bool,
85}
86
87/// Quantizer the probe frame is coded at, and the fallback when nothing has
88/// been observed yet. The middle of the useful range, so the first correction
89/// is a small one whichever way it goes.
90pub const PROBE_QP: i32 = 26;
91
92/// How many frames to spread a rate correction over, at most.
93const BLIND_HORIZON: f64 = 12.0;
94
95/// How far the quantizer may move between batches once under way.
96///
97/// Deriving this from the measured slope — so that one correction always
98/// changes the rate by the same ratio — is the elegant version, and it measured
99/// worse than a constant. On steep content it collapses to a single step, and
100/// the controller then cannot reach its target before the clip ends.
101const MAX_QP_STEP: i32 = 8;
102
103/// Fall in `log2(bytes)` per step of quantizer, before anything is measured.
104///
105/// The measured value for this encoder on photographic content, which is a far
106/// better starting point than the 1/6 the quantizer step size suggests.
107const DEFAULT_SLOPE: f64 = 0.116;
108
109/// The slope cannot be trusted outside this range — a pair of frames whose
110/// content changed between them can imply anything, including a negative slope.
111///
112/// Wide, because the slope is not one number. Measured on noise-like content it
113/// is 0.075 between QP 20 and 30 and **0.32** between 40 and 51: once most
114/// coefficients quantize to zero, each further step costs far more of the rate
115/// than it did while there was still detail to lose. A narrow clamp pinned the
116/// estimate below the truth and left the controller unable to reach high
117/// quantizers, which is only survivable when there are enough feedback rounds to
118/// crawl there one step at a time — so it worked single-threaded and failed with
119/// large batches.
120const SLOPE_RANGE: (f64, f64) = (0.04, 0.50);
121
122impl RateControl {
123    /// `bits_per_second` at `fps`, over `total` frames if that is known.
124    pub fn new(bits_per_second: u64, fps: u32, total: Option<u32>) -> Self {
125        let fps = fps.max(1) as f64;
126        Self {
127            target: bits_per_second as f64 / 8.0 / fps,
128            k: 0.0,
129            slope: DEFAULT_SLOPE,
130            last: None,
131            pairs: 0,
132            prev_qp: None,
133            seen: 0,
134            spent: 0.0,
135            done: 0,
136            total,
137            qp_min: 0,
138            qp_max: 51,
139            pinned_coarse: false,
140            pinned_fine: false,
141        }
142    }
143
144    /// Restrict the quantizer range, for callers who would rather miss the
145    /// target than let quality out of a band.
146    pub fn clamp_qp(mut self, min: i32, max: i32) -> Self {
147        self.qp_min = min.clamp(0, 51);
148        self.qp_max = max.clamp(self.qp_min, 51);
149        self
150    }
151
152    /// The quantizer for the next frame.
153    pub fn next_qp(&self) -> i32 {
154        if self.seen == 0 {
155            return PROBE_QP.clamp(self.qp_min, self.qp_max);
156        }
157        // Aim at the target, adjusted by a slice of whatever has been over- or
158        // underspent so far.
159        //
160        // The obvious alternative — aim at the exact average the remaining
161        // frames must hit — is far too sharp. It asks one frame to repay the
162        // whole debt, which on steep content means a large quantizer step,
163        // which overshoots the other way and repeats. Spreading the repayment
164        // over a horizon damps that, and the horizon shrinks to whatever is
165        // actually left so the clip still lands on target.
166        let debt = self.spent - self.target * f64::from(self.done);
167        let horizon = match self.total {
168            Some(n) if n > self.done => f64::from(n - self.done).min(BLIND_HORIZON),
169            _ => BLIND_HORIZON,
170        }
171        .max(1.0);
172        let want = self.target - debt / horizon;
173        // A frame that would have to be four times smaller than the average is
174        // a sign the content changed, not that the quantizer should collapse.
175        let want = want.clamp(self.target * 0.25, self.target * 4.0);
176        let qp = ((self.k - want.max(1.0).log2()) / self.slope).round() as i32;
177        // Damp the step once the controller is under way. The rate curve is far
178        // steeper at high quantizers than at low ones, so a model fitted in one
179        // region badly overshoots when aimed at another — and an overshoot in a
180        // feedback loop is an oscillation. The first move is undamped because it
181        // is the one that has to cross the distance from the probe.
182        let qp = match self.prev_qp {
183            // Wide enough to cross the useful range in two corrections. A
184            // tighter limit sounds safer and measures worse: the controller
185            // cannot reach the target inside a short clip, and spends the whole
186            // clip travelling.
187            Some(p) => qp.clamp(p - MAX_QP_STEP, p + MAX_QP_STEP),
188            None => qp,
189        };
190        qp.clamp(self.qp_min, self.qp_max)
191    }
192
193    /// Record what a frame actually cost at the quantizer it was coded with.
194    pub fn observe(&mut self, qp: i32, bytes: usize) {
195        let lg = (bytes.max(1) as f64).log2();
196        let q = f64::from(qp);
197        // Two frames at different quantizers are a measurement of the slope.
198        // Frames at the same quantizer are not, and neither is a pair a step
199        // apart, where the content's own variation swamps the signal.
200        if let Some((q0, lg0)) = self.last
201            && (q - q0).abs() >= 2.0
202        {
203            let obs = ((lg0 - lg) / (q - q0)).clamp(SLOPE_RANGE.0, SLOPE_RANGE.1);
204            // Trust the first real measurement outright. Blending it with
205            // the default drags the estimate toward a slope that describes
206            // some other content, and on steep material that error is worth
207            // ten quantizer steps — which is what set the oscillation off.
208            // Weighted hard toward the newest measurement. The slope is not
209            // one number — it is 0.12 where there is still detail to lose
210            // and 0.44 once most coefficients have gone — so an estimate
211            // that averages across regions describes neither, and an
212            // underestimate makes every correction overshoot. Swept against
213            // real encodes: 0.4 left a 30% miss where 0.7 leaves 8%.
214            let w = if self.pairs == 0 { 1.0 } else { 0.7 };
215            self.slope = self.slope * (1.0 - w) + obs * w;
216            self.pairs += 1;
217        }
218        self.last = Some((q, lg));
219        self.prev_qp = Some(qp);
220        self.pinned_coarse |= qp >= self.qp_max;
221        self.pinned_fine |= qp <= self.qp_min;
222        let k_obs = lg + q * self.slope;
223        // Trust the first observation completely and then settle down: the
224        // content constant is genuinely constant for a static scene, and moves
225        // slowly for anything else, so a long memory beats a responsive one.
226        let weight = if self.seen == 0 {
227            1.0
228        } else {
229            (1.0 / f64::from(self.seen + 1)).max(0.15)
230        };
231        self.k = self.k * (1.0 - weight) + k_obs * weight;
232        self.seen += 1;
233        self.spent += bytes as f64;
234        self.done += 1;
235    }
236
237    /// Seed the law from a probe encode without counting it against the budget.
238    pub fn seed(&mut self, qp: i32, bytes: usize) {
239        let lg = (bytes.max(1) as f64).log2();
240        self.k = lg + f64::from(qp) * self.slope;
241        self.last = Some((f64::from(qp), lg));
242        self.seen = 1;
243    }
244
245    /// A second quantizer worth probing before committing, if there is one.
246    ///
247    /// The probe and the answer can be twenty-five quantizer steps apart, and
248    /// the rate curve bends enough over that distance that the chord between
249    /// them is a poor guide — the slope is 0.075 per step at one end and 0.32 at
250    /// the other. A second probe near where the answer is thought to be turns
251    /// that chord into a local measurement.
252    ///
253    /// It costs one frame encode, against a whole clip coded at the wrong rate.
254    pub fn probe_again(&self) -> Option<i32> {
255        let (last, _) = self.last?;
256        let want = self.next_qp();
257        ((want - last as i32).abs() > 6).then_some(want)
258    }
259
260    /// Fold a second probe in: it refines the law but does not count against
261    /// the budget, because its frame will be coded again for real.
262    pub fn seed_pair(&mut self, qp: i32, bytes: usize) {
263        let lg = (bytes.max(1) as f64).log2();
264        let q = f64::from(qp);
265        if let Some((q0, lg0)) = self.last
266            && (q - q0).abs() >= 2.0
267        {
268            self.slope = ((lg0 - lg) / (q - q0)).clamp(SLOPE_RANGE.0, SLOPE_RANGE.1);
269            self.pairs += 1;
270        }
271        self.k = lg + q * self.slope;
272        self.last = Some((q, lg));
273    }
274
275    /// Bytes emitted so far.
276    pub fn spent(&self) -> f64 {
277        self.spent
278    }
279
280    /// Whether the target turned out to be out of reach, and in which direction.
281    ///
282    /// A bitrate can be unreachable both ways. Past `qp_max` the encoder has
283    /// nothing coarser to offer, so content too complex cannot be squeezed into
284    /// the target. Past `qp_min` it has nothing finer, so content too *simple*
285    /// cannot be made to fill it — a flat render at QP 0 is as large as it will
286    /// ever get, and asking for ten times that gets the same file.
287    ///
288    /// Both are properties of the request rather than faults, and both are worth
289    /// saying: a file at a fifth of the requested bitrate looks exactly like a
290    /// bug from outside.
291    ///
292    /// Judged from what was actually coded, not from the model. Extrapolating
293    /// the rate law from the quantizers in use out to 0 or 51 is exactly where
294    /// it stops holding — doing that reported a rendered clip as "2.9x too
295    /// simple" for a target it in fact came within 3% of.
296    pub fn outcome(&self) -> Option<Reach> {
297        if self.done == 0 {
298            return None;
299        }
300        let ratio = self.spent / (self.target * f64::from(self.done));
301        if self.pinned_coarse && ratio > 1.10 {
302            Some(Reach::TooComplex { times: ratio })
303        } else if self.pinned_fine && ratio < 0.90 {
304            Some(Reach::TooSimple { times: 1.0 / ratio })
305        } else {
306            None
307        }
308    }
309
310    /// How many frames to encode before consulting the controller again.
311    ///
312    /// Frames are encoded in parallel batches, and the controller only learns at
313    /// a batch boundary — so a clip that fits in one batch gets no feedback at
314    /// all, and lands wherever the first extrapolation put it. That was worth
315    /// 10-24% on a ten-frame clip.
316    ///
317    /// Eight rounds, and the group size is derived only from the clip length and
318    /// the memory budget — never from the core count.
319    ///
320    /// The controller learns once per group, so the group size *is* the
321    /// accuracy. Sizing it by how many frames happen to fit on the machine's
322    /// cores made the same clip encode to a different size on a different
323    /// machine: one thread gave ninety-six single-frame rounds and fourteen gave
324    /// twelve, and the two missed the target by 19% and 1% respectively. Which
325    /// is the wrong kind of surprise.
326    pub fn group_size(&self, memory_limit: usize) -> usize {
327        const ROUNDS: usize = 8;
328        match self.total {
329            Some(n) if n > 0 => memory_limit.min(((n as usize) / ROUNDS).max(1)).max(1),
330            _ => memory_limit.min(BLIND_HORIZON as usize).max(1),
331        }
332    }
333}
334
335#[cfg(test)]
336mod tests {
337    use super::*;
338
339    /// A synthetic encoder that obeys the rate law exactly, to check the
340    /// controller inverts it correctly rather than to check the law.
341    /// A synthetic encoder obeying the measured law, not the textbook one.
342    fn coded_size(qp: i32, k: f64) -> usize {
343        (2f64.powf(k - f64::from(qp) * DEFAULT_SLOPE)) as usize
344    }
345
346    /// A content constant whose ideal quantizer is `qp`.
347    ///
348    /// Derived rather than written down: a hard-coded constant silently becomes
349    /// unreachable — or trivially reachable — whenever the model's slope
350    /// changes, and then the test is measuring the clamp instead of the
351    /// controller. It has happened twice.
352    fn content_needing_qp(bits_per_second: u64, fps: u32, qp: f64) -> f64 {
353        let target = bits_per_second as f64 / 8.0 / f64::from(fps);
354        target.log2() + qp * DEFAULT_SLOPE
355    }
356
357    #[test]
358    fn it_converges_on_a_target() {
359        // 4 Mbit/s at 30fps is 16667 bytes a frame.
360        let mut rc = RateControl::new(4_000_000, 30, Some(60));
361        let k = content_needing_qp(4_000_000, 30, 38.0);
362        for _ in 0..60 {
363            let qp = rc.next_qp();
364            rc.observe(qp, coded_size(qp, k));
365        }
366        let mean = rc.spent() / 60.0;
367        let target = 4_000_000.0 / 8.0 / 30.0;
368        assert!(
369            (mean - target).abs() / target < 0.05,
370            "mean {mean:.0} bytes vs target {target:.0}"
371        );
372    }
373
374    /// The first frame is a probe, so it is the *rest* that has to absorb the
375    /// error — a controller that only corrected going forward would overshoot
376    /// by whatever the probe cost.
377    #[test]
378    fn it_pays_back_a_bad_first_frame() {
379        let mut rc = RateControl::new(4_000_000, 30, Some(30));
380        // Reachable, but only well below the probe quantizer, so the probe
381        // frame overspends badly and the rest has to make it up.
382        let k = content_needing_qp(4_000_000, 30, 44.0);
383        let qp0 = rc.next_qp();
384        assert_eq!(qp0, PROBE_QP);
385        rc.observe(qp0, coded_size(qp0, k));
386        for _ in 1..30 {
387            let qp = rc.next_qp();
388            rc.observe(qp, coded_size(qp, k));
389        }
390        let mean = rc.spent() / 30.0;
391        let target = 4_000_000.0 / 8.0 / 30.0;
392        assert!(
393            (mean - target).abs() / target < 0.10,
394            "mean {mean:.0} vs target {target:.0} — the overspend was not paid back"
395        );
396    }
397
398    /// Content that changes must not make the quantizer oscillate.
399    #[test]
400    fn it_does_not_oscillate_when_content_changes() {
401        let mut rc = RateControl::new(4_000_000, 30, Some(80));
402        let mut qps = Vec::new();
403        for i in 0..80 {
404            // The scene gets busier a third of the way through.
405            let k = content_needing_qp(4_000_000, 30, if i < 40 { 32.0 } else { 42.0 });
406            let qp = rc.next_qp();
407            rc.observe(qp, coded_size(qp, k));
408            qps.push(qp);
409        }
410        // After the change has been absorbed, successive quantizers should be
411        // within a step or two of each other.
412        let tail = &qps[55..];
413        let swing = tail.iter().max().unwrap() - tail.iter().min().unwrap();
414        assert!(
415            swing <= 2,
416            "quantizer swings by {swing} after settling: {tail:?}"
417        );
418    }
419
420    /// Asking for less than the content can be coded in is a request the
421    /// encoder cannot meet, and it should be detectable rather than silent.
422    #[test]
423    fn an_impossible_target_is_reported() {
424        // Content whose ideal quantizer is past 51: it cannot be made to fit.
425        let k = content_needing_qp(4_000_000, 30, 70.0);
426        let mut rc = RateControl::new(4_000_000, 30, Some(20));
427        for _ in 0..20 {
428            let qp = rc.next_qp();
429            rc.observe(qp, coded_size(qp, k));
430        }
431        match rc.outcome() {
432            Some(Reach::TooComplex { times }) => {
433                assert!(times > 1.3, "reported only {times:.2}x over")
434            }
435            other => panic!("expected TooComplex, got {other:?}"),
436        }
437
438        let k_ok = content_needing_qp(4_000_000, 30, 40.0);
439        let mut ok = RateControl::new(4_000_000, 30, Some(20));
440        for _ in 0..20 {
441            let qp = ok.next_qp();
442            ok.observe(qp, coded_size(qp, k_ok));
443        }
444        assert!(ok.outcome().is_none(), "this target is reachable");
445    }
446
447    /// Content too simple to fill the target is the other failure, and it looks
448    /// identical from outside: a file far off the requested size.
449    #[test]
450    fn a_target_the_content_cannot_fill_is_reported() {
451        // Content whose ideal quantizer is below 0: it cannot be made that big.
452        let k = content_needing_qp(20_000_000, 30, -40.0);
453        let mut rc = RateControl::new(20_000_000, 30, Some(20));
454        for _ in 0..20 {
455            let qp = rc.next_qp();
456            rc.observe(qp, coded_size(qp, k));
457        }
458        match rc.outcome() {
459            Some(Reach::TooSimple { times }) => assert!(times > 1.3, "only {times:.2}x under"),
460            other => panic!("expected TooSimple, got {other:?}"),
461        }
462    }
463
464    /// Without a frame count the controller still has to converge.
465    #[test]
466    fn it_works_without_knowing_the_clip_length() {
467        let mut rc = RateControl::new(4_000_000, 30, None);
468        let k = content_needing_qp(4_000_000, 30, 36.0);
469        for _ in 0..120 {
470            let qp = rc.next_qp();
471            rc.observe(qp, coded_size(qp, k));
472        }
473        let mean = rc.spent() / 120.0;
474        let target = 4_000_000.0 / 8.0 / 30.0;
475        assert!(
476            (mean - target).abs() / target < 0.10,
477            "mean {mean:.0} vs target {target:.0}"
478        );
479    }
480}