pixelflux/

ledger.rs

/*
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

//! Where a region's picture stands, block by block: the per-block counterpart of the cleanup
//! policy's per-region bookkeeping (`pipeline::cleanup_due`).
//!
//! The cleanup policy reads a region as still or moving whole, so a region that never holds
//! still (a video playing in one window) keeps everything else in it at the quality motion is
//! coded at: 1080p text beside a 640x360 video at 8 Mbit/s stayed at 32 dB, where the same
//! text alone was cleaned up to 55. The ledger keeps, for each `BLOCK` x `BLOCK` block, how
//! many frames it has held still and whether its last coding was at the paint-over quality
//! (clean). The capture's damage marks the blocks it covers changed and unclean each frame; a
//! frame that codes blocks finer through the encoder's per-block quantizer
//! (`FrameEncoder::refine_blocks`, x264's quantizer offsets) asks the ledger which
//! (`BlockLedger::plan`): blocks that held still for the cleanup's trigger and are not clean,
//! at most so many a frame, taken in turn from where the last plan stopped so a large set is
//! refined across frames rather than in one, and marks them clean once coded. A whole frame
//! coded at the paint-over quality cleans every block it did not see change; a key frame at the
//! rate control's quality leaves every block unclean. A block that held still and is clean is
//! constant (`BlockLedger::constant`): a frame of the rate control's may code it as a skip
//! without analysis (`FrameEncoder::constant_blocks`), since its reference already holds it at
//! the cleanup's quality. A block coded while a capped constant quality's peak bound it is
//! coarse (`BlockLedger::coded`), never clean; once the peak lets go, the coarse blocks that held
//! still are coded again at the session's own quality, so many a frame (`BlockLedger::refresh`,
//! `RefreshPace`), the rest of them waiting as skips. Nothing reads pixels: the damage source
//! did the detection, and a source that over-reports (a client damaging its whole surface)
//! only refines less, never wrongly.

use smithay::utils::{Physical, Rectangle};

/// The side of a block in pixels: an H.264 or VP8 macroblock. An encoder whose quantizer map is
/// coarser (a 32x32 HEVC tree block, a 64x64 AV1 superblock) reads its unit from the blocks it
/// covers (`BlockPlan::refines_area`).
pub const BLOCK: i32 = 16;

/// Quality index steps finer than the paint-over one x264 codes a refined block at, so the block
/// comes to what the region's own cleanup reaches: one predicted frame at the paint-over
/// quantizer left 1080p text at 44.6 dB, where the cleanup's key frame, at x264's intra offset,
/// reached 49.1; six steps finer reached 49.4. Each encoder that refines says its own
/// (`FrameEncoder::refines`).
pub const REFINE_FINER: u32 = 6;

/// The most blocks a region refines a frame, as a share of it: a large set is refined over
/// `REFINE_FRAMES` frames at least rather than in one frame the size of a cleanup. A constant
/// quality refines that many; a constant rate starts at a share of `REFINE_START_FRAMES` and
/// follows its rate control (`RefinePace`).
const REFINE_FRAMES: usize = 64;
const REFINE_START_FRAMES: usize = 512;

/// Quality index steps the rate control's frames may come out coarser than before the region
/// started refining before its refined blocks a frame halve (or past `REFINE_OVER`); where they
/// come out no coarser, a quarter more. Dense 1080p text refined at 128 blocks a frame beside a
/// video at 8 Mbit/s ran x264's row-level control past quantizer 51, where it scales every
/// macroblock offset toward nothing, and left the text at 42 dB; at 16 a frame it reached 48.
const REFINE_RISE: i32 = 2;

/// Frame budgets, or as much as the frames before refining came to where that is more, a
/// refining frame may come out at before its refined blocks a frame halve, as they do past
/// `REFINE_RISE`: a rate control pinned at its coarsest quantizer says nothing through it, and
/// at 2 Mbit/s at 1080p x264 sent the refinement at twice the rate.
const REFINE_OVER: f64 = 1.5;

/// How an encoder refines blocks (`FrameEncoder::refines`): the quality index steps finer than
/// the paint-over one it codes them at, so a refined block comes to what the region's own
/// cleanup reaches (`finer`); the most steps off the frame's own quality one frame may code a
/// block at (`reach`), past which its rate control loses the rate; and the most runs of blocks
/// along a row one frame may refine (`runs`), where the encoder takes regions rather than a map.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Refiner {
    pub finer: u32,
    pub reach: u32,
    pub runs: usize,
}

impl Refiner {
    /// A refiner `finer` steps past the paint-over quality, with no bound on its reach or runs.
    pub const fn finer(finer: u32) -> Self {
        Self {
            finer,
            reach: u32::MAX,
            runs: usize::MAX,
        }
    }
}

/// A frame's refinement: the blocks (`plan`), the quality index they are coded at (`target`),
/// the rate control's index the offset to it was taken from (`from`), and the most steps the
/// offset may take (`reach`, `Refiner::reach`).
#[derive(Clone, Debug, PartialEq)]
pub struct Refinement {
    pub plan: BlockPlan,
    pub target: i32,
    pub from: i32,
    pub reach: u32,
}

impl Refinement {
    /// The quality index steps the refined blocks are coded off the frame's own.
    pub fn offset(&self) -> i32 {
        (self.target - self.from).clamp(-(self.reach.min(i32::MAX as u32) as i32), 0)
    }
}

/// Frames a region refines nothing for once a frame refining one block came out past
/// `REFINE_OVER` or `REFINE_RISE`: a rate that cannot afford a block a frame is one where the
/// encoder's own refinement of the region does better than a block a frame. VP8 at 2 Mbit/s
/// beside a video came to 24.2 dB refining a block a frame, against 29.6 with none, its cyclic
/// refresh, which the region map displaces, refining the still screen itself.
const REFINE_PAUSE: u32 = 64;

/// The frame budgets the frames of a region refining nothing may average before it refines
/// nothing for `REFINE_PAUSE` frames: a rate control that already runs over its rate has none to
/// spare. Beside a video, VP8's frames averaged 1.38 budgets at 2 Mbit/s, where refining took
/// the text to 25.5 dB against 29.6 by its cyclic refresh and 12% more bytes, and 0.76 at 8
/// Mbit/s, where it took the text from 33.5 to 42.6.
const REFINE_RATE_HELD: f64 = 1.2;

/// How many blocks a region refines a frame (`REFINE_FRAMES`, `REFINE_RISE`, `REFINE_OVER`,
/// `REFINE_PAUSE`, `REFINE_RATE_HELD`).
#[derive(Clone, Debug, Default)]
pub struct RefinePace {
    count: usize,
    base: Option<i32>,
    /// The bytes of the frames that refined nothing, on average over the last eight or so.
    base_bytes: f64,
    paused: u32,
}

impl RefinePace {
    /// The most blocks of a region of `blocks` this frame refines, under a constant rate or not.
    pub fn most(&mut self, blocks: usize, constant_rate: bool) -> usize {
        let most = blocks.div_ceil(REFINE_FRAMES);
        if !constant_rate {
            return most;
        }
        if self.paused > 0 {
            self.paused -= 1;
            return 0;
        }
        if self.count == 0 {
            self.count = blocks.div_ceil(REFINE_START_FRAMES);
        }
        self.count.min(most)
    }

    /// A frame the rate control coded at quality index `coded` in `bytes` against a `budget`,
    /// which refined blocks or not, of a region of `blocks`.
    pub fn coded(&mut self, refined: bool, coded: i32, bytes: usize, budget: f64, blocks: usize) {
        if !refined {
            self.base = Some(coded);
            self.base_bytes += (bytes as f64 - self.base_bytes) / 8.0;
            if self.base_bytes > budget * REFINE_RATE_HELD {
                self.paused = REFINE_PAUSE;
            }
            return;
        }
        let base = *self.base.get_or_insert(coded);
        let budget = budget.max(self.base_bytes);
        let most = blocks.div_ceil(REFINE_FRAMES);
        let count = self.count;
        let costly = bytes as f64 > budget * REFINE_OVER || coded > base + REFINE_RISE;
        if costly && count <= 1 {
            self.paused = REFINE_PAUSE;
        }
        self.count = if costly {
            (count / 2).max(1)
        } else if coded <= base {
            (count + count / 4 + 1).min(most)
        } else {
            count
        };
    }
}

/// Quality index steps finer than the session's own a capped constant quality's refresh codes its
/// coarse blocks at (`BlockLedger::refresh`, `Codec::refresh_index`), so a predicted frame
/// refreshing them comes to what the uncapped session's picture stands at: refreshing a 720p
/// page of text a scroll left coarse, libvpx's VP8 and VP9 came to 44.8 and 41.7 dB against the
/// uncapped sessions' 44.5 and 40.5, and NVENC's H.264 to 41.1 against 38.8. x264 takes a step
/// more (`X264_REFRESH_FINER` in the software encoder).
pub const REFRESH_FINER: u32 = 3;

/// Quality index steps further finer a refresh codes a block a capped key frame left coarse at
/// (`BlockLedger::refresh`), where the uncapped session's key frame stood at its rate factor's
/// intra offset finer than its predicted frames: x264's coarse start on a 1080p desktop left
/// the screen's still parts 0.6 dB under the uncapped session's refreshed `REFRESH_FINER` steps
/// finer.
pub const REFRESH_KEY_FINER: u32 = 3;

/// Frames a capped constant quality's refresh of its coarse blocks (`BlockLedger::refresh`) would
/// take at its first share of the region's blocks a frame, which halves while a refreshing frame
/// comes out past the peak's frame budget and doubles while one comes out under half of it
/// (`RefreshPace`): on a fast path the share doubles to the whole region in eight frames, and
/// on a slow one the first frame is a small one.
const REFRESH_FRAMES: usize = 256;

/// Frames a refresh waits, refreshing nothing and holding nothing back, once a frame refreshing
/// one block comes out past the peak's frame budget: the content alone fills the peak, as where
/// NVENC runs past a peak it leaves its level for, and a refresh crawling a block a frame would
/// hold the rest of the coarse blocks back for seconds, which NVENC holds at its coarsest
/// quantizer through its QP map and deblocks frame after frame (the static parts of a 1080p
/// scene 0.4 dB under the uncapped session's after two seconds).
const REFRESH_PAUSE: u32 = 60;

/// How many coarse blocks a region refreshes a frame (`REFRESH_FRAMES`, `REFRESH_PAUSE`).
#[derive(Clone, Debug, Default)]
pub struct RefreshPace {
    count: usize,
    paused: u32,
}

impl RefreshPace {
    /// The most blocks of a region of `blocks` this frame refreshes, 0 while it waits.
    pub fn most(&mut self, blocks: usize) -> usize {
        if self.paused > 0 {
            self.paused -= 1;
            return 0;
        }
        if self.count == 0 {
            self.count = blocks.div_ceil(REFRESH_FRAMES).max(1);
        }
        self.count
    }

    /// A refreshing frame came out at `bytes` against the peak's frame `budget`.
    pub fn coded(&mut self, bytes: usize, budget: f64, blocks: usize) {
        let count = self.count.max(1);
        if bytes as f64 > budget && count == 1 {
            self.paused = REFRESH_PAUSE;
        }
        self.count = if bytes as f64 > budget {
            (count / 2).max(1)
        } else if (bytes as f64) < budget / 2.0 {
            count.saturating_mul(2).min(blocks.max(1))
        } else {
            count
        };
    }
}

/// The blocks of a picture to code at the paint-over quality this frame (`BlockLedger::plan`).
#[derive(Clone, Debug, PartialEq)]
pub struct BlockPlan {
    pub cols: usize,
    pub rows: usize,
    refine: Vec<u64>,
    /// How many blocks the plan refines.
    pub count: usize,
}

impl BlockPlan {
    /// A plan of this one's blocks that refines none of them.
    pub fn none_like(&self) -> Self {
        Self {
            cols: self.cols,
            rows: self.rows,
            refine: vec![0; self.refine.len()],
            count: 0,
        }
    }

    /// Whether block (`col`, `row`) is refined.
    pub fn refines(&self, col: usize, row: usize) -> bool {
        let i = row * self.cols + col;
        col < self.cols && row < self.rows && self.refine[i / 64] >> (i % 64) & 1 != 0
    }

    /// Whether any refined block lies in the pixel area from (`x`, `y`) of `width` x `height`:
    /// an encoder whose map unit spans several blocks refines a unit that holds one.
    pub fn refines_area(&self, x: i32, y: i32, width: i32, height: i32) -> bool {
        let c0 = (x.max(0) / BLOCK) as usize;
        let r0 = (y.max(0) / BLOCK) as usize;
        let c1 = (((x + width).max(0) + BLOCK - 1) / BLOCK) as usize;
        let r1 = (((y + height).max(0) + BLOCK - 1) / BLOCK) as usize;
        (r0..r1.min(self.rows)).any(|r| (c0..c1.min(self.cols)).any(|c| self.refines(c, r)))
    }
}

/// Per-block stillness and cleanliness of one region (module docblock).
#[derive(Clone, Debug, Default)]
pub struct BlockLedger {
    width: i32,
    height: i32,
    cols: usize,
    rows: usize,
    /// Frames each block has held still, saturating.
    still: Vec<u16>,
    /// Whether each block's last coding was at the paint-over quality or finer.
    clean: Vec<bool>,
    /// Whether each block was refined (`refined`) since it last changed: coded at the target a
    /// key-frame cleanup reaches, which a refresh at the paint-over quality does not.
    refined: Vec<bool>,
    /// Whether each block was last coded under a capped constant quality's binding peak,
    /// coarser than the rate factor would have chosen (`coded`), and not refreshed since, and
    /// whether that was in a key frame.
    coarse: Vec<bool>,
    coarse_key: Vec<bool>,
    /// How many blocks are coarse, so a session no peak ever bound reads none at no cost.
    coarse_count: usize,
    /// Whether each block is owed its paint-over: a cleanup that fell due on it was left to the
    /// refresh, or coded short of its target under a binding peak (`spent`), and the block not
    /// coded at it since. An owed block is coarse too, and the refresh codes it at the
    /// paint-over quality (`refresh_owed`).
    owed: Vec<bool>,
    owed_count: usize,
    /// Whether each block was refreshed at the session's own quality since it changed: a
    /// cleanup coded over it as over the picture an uncapped session holds leaves it coarser
    /// than that session's paint-over, the quality it starts from being finer (`fresh`).
    fresh: Vec<bool>,
    fresh_count: usize,
    /// The block the next refresh starts its turn from.
    next_refresh: usize,
    /// The block the next plan starts its turn from.
    next: usize,
    /// Whether the region's source was last seen to leave a change unreported
    /// (`frame_reported`).
    unreported: bool,
}

impl BlockLedger {
    /// A ledger of a `width` x `height` region, every block changed and unclean.
    pub fn new(width: i32, height: i32) -> Self {
        let cols = (width.max(0) + BLOCK - 1) as usize / BLOCK as usize;
        let rows = (height.max(0) + BLOCK - 1) as usize / BLOCK as usize;
        Self {
            width,
            height,
            cols,
            rows,
            still: vec![0; cols * rows],
            clean: vec![false; cols * rows],
            refined: vec![false; cols * rows],
            coarse: vec![false; cols * rows],
            coarse_key: vec![false; cols * rows],
            coarse_count: 0,
            owed: vec![false; cols * rows],
            owed_count: 0,
            fresh: vec![false; cols * rows],
            fresh_count: 0,
            next_refresh: 0,
            next: 0,
            unreported: true,
        }
    }

    /// Follow the region to `width` x `height`, starting over where that changed it: a resize,
    /// a scale change, or a rebuilt encoder leaves nothing of the old picture's quality.
    pub fn fit(&mut self, width: i32, height: i32) {
        if (width, height) != (self.width, self.height) {
            *self = Self::new(width, height);
        }
    }

    /// One frame of the region: the blocks `rects` cover changed and are unclean, and every
    /// other block held still one more frame. Damage across frames the capture skipped is the
    /// caller's to union into `rects`.
    pub fn frame<'a>(&mut self, rects: impl IntoIterator<Item = &'a Rectangle<i32, Physical>>) {
        for s in self.still.iter_mut() {
            *s = s.saturating_add(1);
        }
        for r in rects {
            let c0 = (r.loc.x.max(0) / BLOCK) as usize;
            let r0 = (r.loc.y.max(0) / BLOCK) as usize;
            let c1 = ((r.loc.x + r.size.w).clamp(0, self.width) + BLOCK - 1) / BLOCK;
            let r1 = ((r.loc.y + r.size.h).clamp(0, self.height) + BLOCK - 1) / BLOCK;
            for row in r0..(r1 as usize).min(self.rows) {
                for col in c0..(c1 as usize).min(self.cols) {
                    let i = row * self.cols + col;
                    self.still[i] = 0;
                    self.clean[i] = false;
                    self.refined[i] = false;
                }
            }
        }
    }

    /// One frame of a region whose source reports where it changed (`rects`) and whose content
    /// hash says whether it did (`dirty`): the blocks `rects` cover changed, and where none does
    /// the whole region did, while the source was last seen to leave a change unreported. A
    /// frame the hash checked and found changed (`observed`) says which: without a rectangle
    /// the source missed it, as the X server's DAMAGE misses directly rendered GL. A hash that
    /// keeps a region dirty for a run of frames after it moved checks only the run's last, so
    /// read as a change, the frames after a video stopped beside clean text dropped every block
    /// the ledger had refined.
    pub fn frame_reported(
        &mut self,
        rects: &[Rectangle<i32, Physical>],
        dirty: bool,
        observed: bool,
    ) {
        if observed {
            self.unreported = rects.is_empty();
        }
        if rects.is_empty() && dirty && self.unreported {
            self.frame_all();
        } else {
            self.frame(rects);
        }
    }

    /// The whole region changed this frame (a source that cannot say where).
    pub fn frame_all(&mut self) {
        self.still.fill(0);
        self.clean.fill(false);
        self.refined.fill(false);
    }

    /// The frame just coded the whole region at the rate control's quality where it was clean
    /// (a key frame a consumer asked for): every block is unclean again.
    pub fn coarsened(&mut self) {
        self.clean.fill(false);
        self.refined.fill(false);
    }

    /// The frame just coded the whole region at the paint-over quality or finer: every block
    /// that did not change in it is clean, and no longer coarse nor owed its paint-over.
    pub fn cleaned(&mut self) {
        for i in 0..self.still.len() {
            if self.still[i] == 0 {
                continue;
            }
            self.clean[i] = true;
            if self.coarse[i] {
                self.coarse[i] = false;
                self.coarse_count -= 1;
            }
            if self.owed[i] {
                self.owed[i] = false;
                self.owed_count -= 1;
            }
            self.unfresh(i);
        }
    }

    /// Block `i` holds no refresh at the session's own quality.
    fn unfresh(&mut self, i: usize) {
        if self.fresh[i] {
            self.fresh[i] = false;
            self.fresh_count -= 1;
        }
    }

    /// A cleanup that fell due on the region is left to the refresh, or was coded short of its
    /// target under a binding peak: every block that did not change this frame is owed its
    /// paint-over, for the refresh once the peak lets go (`refresh_owed`). Whether that owed
    /// any block it did not owe.
    pub fn spent(&mut self) -> bool {
        let before = self.owed_count;
        for i in 0..self.still.len() {
            if self.still[i] == 0 {
                continue;
            }
            self.clean[i] = false;
            self.refined[i] = false;
            if !self.coarse[i] {
                self.coarse[i] = true;
                self.coarse_count += 1;
            }
            if !self.owed[i] {
                self.owed[i] = true;
                self.owed_count += 1;
            }
            self.unfresh(i);
        }
        self.owed_count > before
    }

    /// Whether every block that held still is clean: nothing for a cleanup to do.
    pub fn settled(&self) -> bool {
        self.clean
            .iter()
            .zip(&self.still)
            .all(|(&c, &s)| c || s == 0)
    }

    /// The blocks to refine this frame: those still for `trigger` frames or more and not
    /// clean, at most `max` in at most `runs` runs along a row, in turn from where the last
    /// plan stopped; `None` where there are none.
    pub fn plan(&mut self, trigger: u32, max: usize, runs: usize) -> Option<BlockPlan> {
        let n = self.cols * self.rows;
        if n == 0 || max == 0 {
            return None;
        }
        let trigger = trigger.min(u32::from(u16::MAX)) as u16;
        let mut refine = vec![0u64; n.div_ceil(64)];
        let (mut count, mut started) = (0, 0);
        let mut last: Option<usize> = None;
        let start = self.next % n;
        for k in 0..n {
            let i = (start + k) % n;
            if self.still[i] >= trigger && !self.clean[i] {
                let continues = last.is_some_and(|l| l + 1 == i && !i.is_multiple_of(self.cols));
                if !continues {
                    if started == runs {
                        self.next = i;
                        break;
                    }
                    started += 1;
                }
                refine[i / 64] |= 1 << (i % 64);
                last = Some(i);
                count += 1;
                if count == max {
                    self.next = i + 1;
                    break;
                }
            }
        }
        (count > 0).then_some(BlockPlan {
            cols: self.cols,
            rows: self.rows,
            refine,
            count,
        })
    }

    /// A frame that carried `refinement` came out with the rate control at quality index
    /// `coded`: its blocks are clean where that put them at the target or finer. A rate control
    /// codes the rows a refinement overspends coarser, and a block it left short is refined again
    /// on its next turn, from the index it now codes at.
    pub fn refinement_coded(&mut self, refinement: &Refinement, coded: i32) {
        let at_reach = refinement.offset() <= -(refinement.reach.min(i32::MAX as u32) as i32);
        if coded + refinement.offset() <= refinement.target || at_reach {
            self.refined(&refinement.plan);
        }
    }

    /// The blocks `plan` refined were coded at the paint-over quality: they are clean.
    pub fn refined(&mut self, plan: &BlockPlan) {
        for row in 0..self.rows.min(plan.rows) {
            for col in 0..self.cols.min(plan.cols) {
                if plan.refines(col, row) {
                    self.clean[row * self.cols + col] = true;
                    self.refined[row * self.cols + col] = true;
                }
            }
        }
    }

    /// The share of the region's blocks not refined since they last changed: what a key-frame
    /// cleanup has left to do (`pipeline::cleanup_due`), the whole region on a session that does
    /// not refine.
    pub fn unrefined_share(&self) -> f32 {
        if self.refined.is_empty() {
            return 1.0;
        }
        let unrefined = self.refined.iter().filter(|&&r| !r).count();
        unrefined as f32 / self.refined.len() as f32
    }

    /// Whether each block, in raster order, held still this frame: what the source reported
    /// unchanged since the frame before.
    pub fn unchanged(&self) -> impl Iterator<Item = bool> + '_ {
        self.still.iter().map(|&s| s > 0)
    }

    /// Whether each block, in raster order, held still this frame and is clean: coded at the
    /// cleanup's quality since it last changed, so a frame of the rate control's may code it as
    /// a skip without analysis (`FrameEncoder::constant_blocks`). A still block not yet clean is
    /// left to the encoder, whose rate control refines it as it codes the frame; a skip there
    /// would hold it at the quality it was coded at while moving.
    pub fn constant(&self) -> impl Iterator<Item = bool> + '_ {
        self.still
            .iter()
            .zip(&self.clean)
            .map(|(&still, &clean)| still > 0 && clean)
    }

    /// The number of blocks in the region.
    pub fn blocks(&self) -> usize {
        self.cols * self.rows
    }

    /// The frame just coded the blocks that changed in it, or the whole region where it was a
    /// key frame (`whole`), under a capped constant quality's binding peak (`capped`): coarser
    /// than the rate factor would have chosen, so coarse and unclean, or at the session's own
    /// quality, so no longer coarse. Either way they are owed no paint-over: one falls due on
    /// them again once they hold still.
    pub fn coded(&mut self, capped: bool, whole: bool) {
        if !capped && self.coarse_count == 0 && self.fresh_count == 0 {
            return;
        }
        for i in 0..self.coarse.len() {
            if whole || self.still[i] == 0 {
                match (self.coarse[i], capped) {
                    (false, true) => self.coarse_count += 1,
                    (true, false) => self.coarse_count -= 1,
                    _ => {}
                }
                self.coarse[i] = capped;
                self.coarse_key[i] = capped && whole;
                if self.owed[i] {
                    self.owed[i] = false;
                    self.owed_count -= 1;
                }
                self.unfresh(i);
                if capped {
                    self.clean[i] = false;
                    self.refined[i] = false;
                }
            }
        }
    }

    /// The coarse blocks (`coded`) that held still this frame, split into the ones it codes
    /// again at the session's own quality, at most `max` in turn from where the last refresh
    /// stopped, and the rest, which wait as skips; `None` where none is coarse.
    pub fn refresh(&mut self, max: usize) -> Option<(BlockPlan, BlockPlan)> {
        self.refresh_keyed(max).map(|(now, _, wait)| (now, wait))
    }

    /// `refresh`, with the blocks it codes now that a capped key frame left coarse apart
    /// (`REFRESH_KEY_FINER`), among them. A block owed its paint-over waits for
    /// `refresh_owed`.
    pub fn refresh_keyed(&mut self, max: usize) -> Option<(BlockPlan, BlockPlan, BlockPlan)> {
        let n = self.cols * self.rows;
        if n == 0 || self.coarse_count == 0 {
            return None;
        }
        let mut now = vec![0u64; n.div_ceil(64)];
        let mut key = vec![0u64; n.div_ceil(64)];
        let mut wait = vec![0u64; n.div_ceil(64)];
        let (mut count, mut keyed, mut waiting) = (0, 0, 0);
        let start = self.next_refresh % n;
        for k in 0..n {
            let i = (start + k) % n;
            if !self.coarse[i] || self.still[i] == 0 {
                continue;
            }
            if count < max.max(1) && !self.owed[i] {
                now[i / 64] |= 1 << (i % 64);
                count += 1;
                if self.coarse_key[i] {
                    key[i / 64] |= 1 << (i % 64);
                    keyed += 1;
                }
                self.next_refresh = i + 1;
            } else {
                wait[i / 64] |= 1 << (i % 64);
                waiting += 1;
            }
        }
        let plan = |refine, count| BlockPlan {
            cols: self.cols,
            rows: self.rows,
            refine,
            count,
        };
        (count > 0).then(|| (plan(now, count), plan(key, keyed), plan(wait, waiting)))
    }

    /// The coarse blocks owed their paint-over (`spent`) that held still this frame, split into
    /// the ones it codes again at the paint-over quality, at most `max` in turn from where the
    /// last refresh stopped, and every other coarse block that held still, which waits as a
    /// skip; `None` where none is owed. A refresh takes these before the rest (`refresh`).
    pub fn refresh_owed(&mut self, max: usize) -> Option<(BlockPlan, BlockPlan)> {
        let n = self.cols * self.rows;
        if n == 0 || self.owed_count == 0 {
            return None;
        }
        let mut now = vec![0u64; n.div_ceil(64)];
        let mut wait = vec![0u64; n.div_ceil(64)];
        let (mut count, mut waiting) = (0, 0);
        let start = self.next_refresh % n;
        for k in 0..n {
            let i = (start + k) % n;
            if !self.coarse[i] || self.still[i] == 0 {
                continue;
            }
            if self.owed[i] && count < max.max(1) {
                now[i / 64] |= 1 << (i % 64);
                count += 1;
                self.next_refresh = i + 1;
            } else {
                wait[i / 64] |= 1 << (i % 64);
                waiting += 1;
            }
        }
        let plan = |refine, count| BlockPlan {
            cols: self.cols,
            rows: self.rows,
            refine,
            count,
        };
        (count > 0).then(|| (plan(now, count), plan(wait, waiting)))
    }

    /// The blocks `plan` refreshed were coded at the session's own quality, or at the
    /// paint-over quality where they were owed it (`refresh_owed`), which leaves them clean: no
    /// longer coarse.
    pub fn refreshed(&mut self, plan: &BlockPlan) {
        for row in 0..self.rows.min(plan.rows) {
            for col in 0..self.cols.min(plan.cols) {
                let i = row * self.cols + col;
                if !plan.refines(col, row) {
                    continue;
                }
                if self.coarse[i] {
                    self.coarse[i] = false;
                    self.coarse_count -= 1;
                }
                if self.owed[i] {
                    self.owed[i] = false;
                    self.owed_count -= 1;
                    self.clean[i] = true;
                    self.refined[i] = true;
                } else if !self.fresh[i] {
                    self.fresh[i] = true;
                    self.fresh_count += 1;
                }
            }
        }
    }

    /// Whether any block is owed its paint-over (`spent`).
    pub fn owed(&self) -> bool {
        self.owed_count > 0
    }

    /// Whether any block was refreshed at the session's own quality since it changed.
    pub fn fresh(&self) -> bool {
        self.fresh_count > 0
    }

    /// Whether any block is coarse (`coded`).
    pub fn coarse(&self) -> bool {
        self.coarse_count > 0
    }
}

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

    /// A frame the content hash keeps dirty without a rectangle drops nothing a source that
    /// reports its changes refined; a change the hash saw and the source did not report drops it
    /// all, and so does every dirty frame without a rectangle after it.
    #[test]
    fn a_dirty_frame_without_a_change_keeps_what_was_refined() {
        let mut ledger = BlockLedger::new(64, 64);
        let rect = [Rectangle::new((0, 0).into(), (16, 16).into())];
        ledger.frame_reported(&rect, true, true);
        let plan = ledger.plan(0, usize::MAX, usize::MAX).unwrap();
        ledger.refined(&plan);
        assert_eq!(ledger.unrefined_share(), 0.0);
        ledger.frame_reported(&[], true, false);
        assert_eq!(ledger.unrefined_share(), 0.0);
        ledger.frame_reported(&[], true, true);
        assert_eq!(ledger.unrefined_share(), 1.0);
        let plan = ledger.plan(0, usize::MAX, usize::MAX).unwrap();
        ledger.refined(&plan);
        ledger.frame_reported(&[], true, false);
        assert_eq!(ledger.unrefined_share(), 1.0);
    }

    /// A refresh at the paint-over quality cleans the blocks that held still without refining
    /// them: a key-frame cleanup still has them to do.
    /// A block is constant once it held still and was cleaned; a change makes it variable
    /// again, and a still block the cleanup has not reached stays variable.
    #[test]
    fn a_still_clean_block_is_constant_until_it_changes() {
        let mut ledger = BlockLedger::new(64, 32);
        ledger.frame([]);
        assert!(ledger.constant().all(|c| !c), "nothing is clean yet");
        ledger.cleaned();
        ledger.frame([]);
        assert!(ledger.constant().all(|c| c));
        ledger.frame([&Rectangle::new((0, 0).into(), (16, 16).into())]);
        let constant: Vec<bool> = ledger.constant().collect();
        assert_eq!(
            constant,
            vec![false, true, true, true, true, true, true, true]
        );
        ledger.frame([]);
        assert!(!ledger.constant().next().unwrap(), "still but unclean");
    }

    #[test]
    fn a_refresh_cleans_without_refining() {
        let mut ledger = BlockLedger::new(64, 64);
        ledger.frame([]);
        ledger.cleaned();
        assert!(ledger.settled());
        assert_eq!(ledger.unrefined_share(), 1.0);
    }

    fn rect(x: i32, y: i32, w: i32, h: i32) -> Rectangle<i32, Physical> {
        Rectangle::new((x, y).into(), (w, h).into())
    }

    #[test]
    fn blocks_that_held_still_are_refined_while_others_keep_changing() {
        let mut ledger = BlockLedger::new(64, 32);
        let video = rect(32, 0, 32, 32);
        for _ in 0..3 {
            ledger.frame([&video]);
        }
        let plan = ledger.plan(3, usize::MAX, usize::MAX).expect("a plan");
        assert_eq!(plan.count, 4, "the two still columns of two rows");
        assert!(plan.refines(0, 0) && plan.refines(1, 1) && !plan.refines(2, 0));
        ledger.refined(&plan);
        ledger.frame([&video]);
        assert_eq!(
            ledger.plan(3, usize::MAX, usize::MAX),
            None,
            "nothing left to refine"
        );
        assert!(ledger.settled());
    }

    #[test]
    fn a_large_set_is_refined_in_turn() {
        let mut ledger = BlockLedger::new(64, 64);
        ledger.frame([]);
        let first = ledger.plan(1, 6, usize::MAX).unwrap();
        ledger.refined(&first);
        let second = ledger.plan(1, 6, usize::MAX).unwrap();
        assert_eq!((first.count, second.count), (6, 6));
        assert!(
            first.refines(0, 0) && second.refines(2, 1),
            "the second takes up where the first stopped"
        );
        ledger.refined(&second);
        let rest = ledger.plan(1, 16, usize::MAX).unwrap();
        assert_eq!(rest.count, 4);
    }

    #[test]
    fn a_change_or_a_coarse_key_frame_makes_blocks_unclean_again() {
        let mut ledger = BlockLedger::new(32, 32);
        ledger.frame([]);
        ledger.cleaned();
        assert!(ledger.settled());
        ledger.frame([&rect(0, 0, 1, 1)]);
        assert!(ledger.settled(), "a block that just changed is not due");
        ledger.frame([]);
        assert!(!ledger.settled());
        assert_eq!(ledger.plan(1, 8, usize::MAX).unwrap().count, 1);
        ledger.cleaned();
        ledger.coarsened();
        assert_eq!(ledger.plan(1, 8, usize::MAX).unwrap().count, 4);
    }

    #[test]
    fn a_coarser_map_unit_refines_where_it_holds_a_refined_block() {
        let mut ledger = BlockLedger::new(64, 64);
        ledger.frame([&rect(0, 0, 64, 48)]);
        let plan = ledger.plan(1, usize::MAX, usize::MAX).unwrap();
        assert!(!plan.refines_area(0, 0, 32, 32));
        assert!(
            plan.refines_area(32, 32, 32, 32),
            "the bottom row of blocks"
        );
    }

    #[test]
    fn a_rate_that_cannot_afford_a_block_a_frame_pauses_refinement() {
        let mut pace = RefinePace::default();
        assert_eq!(pace.most(512, true), 1);
        pace.coded(true, 30, 3000, 1000.0, 512);
        assert_eq!(
            pace.most(512, true),
            0,
            "a block a frame over budget pauses"
        );
        for _ in 1..REFINE_PAUSE {
            assert_eq!(pace.most(512, true), 0);
        }
        assert_eq!(pace.most(512, true), 1, "and resumes after the pause");
        assert_eq!(
            pace.most(512, false),
            8,
            "a constant quality refines its share"
        );
    }

    #[test]
    fn a_plan_keeps_to_the_runs_an_encoder_takes() {
        let mut ledger = BlockLedger::new(64, 64);
        ledger.frame([&rect(16, 0, 16, 64)]);
        ledger.frame([&rect(16, 0, 16, 64)]);
        let plan = ledger.plan(1, usize::MAX, 3).unwrap();
        assert_eq!(
            plan.count, 4,
            "column 0 and columns 2 and 3 of row 0, then column 0 of row 1"
        );
        assert!(
            plan.refines(0, 0) && plan.refines(2, 0) && plan.refines(3, 0) && plan.refines(0, 1)
        );
        assert!(!plan.refines(2, 1));
    }

    #[test]
    fn a_block_refined_at_the_encoders_reach_counts_clean() {
        let mut ledger = BlockLedger::new(16, 16);
        ledger.frame([]);
        let plan = ledger.plan(1, 8, usize::MAX).unwrap();
        let reached = Refinement {
            plan: plan.clone(),
            target: 10,
            from: 40,
            reach: 10,
        };
        assert_eq!(reached.offset(), -10);
        ledger.refinement_coded(&reached, 40);
        assert!(ledger.settled(), "it could go no finer in one frame");
        ledger.coarsened();
        let short = Refinement {
            plan,
            target: 10,
            from: 40,
            reach: u32::MAX,
        };
        ledger.refinement_coded(&short, 45);
        assert!(!ledger.settled(), "the frame came out coarser than planned");
    }

    /// The blocks a capped frame coded are coarse and unclean; once the peak lets go, the ones
    /// that held still are refreshed so many a frame in turn, the rest waiting, each once, and
    /// a block an uncapped frame codes again is no longer coarse.
    #[test]
    fn coarse_blocks_are_refreshed_once_in_turn() {
        let mut ledger = BlockLedger::new(64, 16);
        ledger.frame([]);
        ledger.cleaned();
        ledger.frame([&Rectangle::new((0, 0).into(), (48, 16).into())]);
        ledger.coded(true, false);
        assert!(ledger.coarse());
        assert!(
            ledger.constant().take(3).all(|c| !c),
            "a capped block is unclean"
        );
        assert!(ledger.refresh(8).is_none(), "nothing coarse held still yet");
        ledger.frame([]);
        let (now, wait) = ledger.refresh(2).unwrap();
        assert_eq!((now.count, wait.count), (2, 1));
        assert!(now.refines(0, 0) && now.refines(1, 0) && wait.refines(2, 0));
        assert!(
            !now.refines(3, 0) && !wait.refines(3, 0),
            "block 3 was never coarse"
        );
        ledger.refreshed(&now);
        ledger.frame([]);
        let (now, wait) = ledger.refresh(2).unwrap();
        assert_eq!((now.count, wait.count), (1, 0));
        assert!(now.refines(2, 0));
        ledger.refreshed(&now);
        assert!(!ledger.coarse() && ledger.refresh(2).is_none());
        ledger.frame([&Rectangle::new((0, 0).into(), (16, 16).into())]);
        ledger.coded(true, false);
        ledger.frame([&Rectangle::new((0, 0).into(), (16, 16).into())]);
        ledger.coded(false, false);
        assert!(!ledger.coarse(), "coded again at the session's quality");
        ledger.frame([]);
        ledger.coded(true, true);
        ledger.frame([]);
        assert_eq!(
            ledger.refresh(usize::MAX).unwrap().0.count,
            4,
            "a capped key frame"
        );
    }

    /// A cleanup coded under a binding peak leaves the blocks that held still owed their
    /// paint-over: a refresh codes them first, so many a frame, every other coarse block waiting,
    /// and leaves them clean; a block that changed on the cleanup frame is owed nothing.
    #[test]
    fn a_spent_cleanup_is_owed_to_the_blocks_that_held_still() {
        let mut ledger = BlockLedger::new(64, 16);
        ledger.frame([&Rectangle::new((0, 0).into(), (16, 16).into())]);
        ledger.coded(true, false);
        ledger.frame([&Rectangle::new((48, 0).into(), (16, 16).into())]);
        ledger.coded(true, false);
        ledger.spent();
        assert!(ledger.owed() && ledger.coarse());
        assert!(!ledger.settled(), "an owed block is unclean");
        ledger.frame([]);
        let (now, wait) = ledger.refresh_owed(1).unwrap();
        assert_eq!((now.count, wait.count), (1, 3));
        assert!(
            !now.refines(3, 0),
            "block 3 changed on the cleanup frame: nothing owed"
        );
        let (plain, _) = ledger.refresh(usize::MAX).unwrap();
        assert!(
            plain.refines(3, 0) && (0..3).all(|c| !plain.refines(c, 0)),
            "an owed block waits for the owed refresh"
        );
        ledger.refreshed(&now);
        ledger.frame([]);
        let (now, wait) = ledger.refresh_owed(usize::MAX).unwrap();
        assert_eq!((now.count, wait.count), (2, 1));
        ledger.refreshed(&now);
        assert!(!ledger.owed() && ledger.coarse());
        assert!(
            ledger.clean[..3].iter().all(|&c| c),
            "the owed blocks are clean"
        );
        ledger.refreshed(&plain);
        assert!(!ledger.coarse() && !ledger.clean[3]);
    }

    /// The count of coarse blocks follows the blocks through every path that marks or clears
    /// them, a resize among them.
    #[test]
    fn the_coarse_count_follows_the_coarse_blocks() {
        let tally = |l: &BlockLedger| {
            assert_eq!(l.coarse_count, l.coarse.iter().filter(|&&c| c).count());
            assert_eq!(l.owed_count, l.owed.iter().filter(|&&c| c).count());
            assert!(l.owed.iter().zip(&l.coarse).all(|(&o, &c)| !o || c));
            assert_eq!(l.fresh_count, l.fresh.iter().filter(|&&c| c).count());
        };
        let mut ledger = BlockLedger::new(64, 32);
        ledger.frame([&Rectangle::new((0, 0).into(), (48, 16).into())]);
        ledger.coded(true, false);
        tally(&ledger);
        ledger.frame([&Rectangle::new((16, 0).into(), (32, 32).into())]);
        ledger.coded(true, false);
        tally(&ledger);
        ledger.frame([]);
        ledger.cleaned();
        tally(&ledger);
        ledger.frame([]);
        ledger.coded(true, true);
        tally(&ledger);
        ledger.frame([]);
        let (now, _) = ledger.refresh(3).unwrap();
        ledger.refreshed(&now);
        ledger.refreshed(&now);
        tally(&ledger);
        ledger.frame([&Rectangle::new((0, 0).into(), (16, 16).into())]);
        ledger.spent();
        tally(&ledger);
        ledger.frame([]);
        let (now, _) = ledger.refresh_owed(2).unwrap();
        ledger.refreshed(&now);
        tally(&ledger);
        ledger.frame([&Rectangle::new((0, 16).into(), (64, 16).into())]);
        ledger.coded(false, false);
        tally(&ledger);
        ledger.frame([]);
        ledger.cleaned();
        tally(&ledger);
        ledger.fit(32, 32);
        tally(&ledger);
        assert!(!ledger.coarse());
    }

    /// A refresh spreads over more frames while its frames come out past the peak's budget, and
    /// over fewer while they come out well under it; one a block a frame still past it waits.
    #[test]
    fn a_refresh_follows_the_peaks_budget() {
        let mut pace = RefreshPace::default();
        let first = pace.most(25_600);
        assert_eq!(first, 100);
        pace.coded(20_000, 10_000.0, 25_600);
        assert_eq!(pace.most(25_600), 50);
        pace.coded(7_000, 10_000.0, 25_600);
        assert_eq!(pace.most(25_600), 50);
        pace.coded(1_000, 10_000.0, 25_600);
        assert_eq!(pace.most(25_600), 100);
        for _ in 0..7 {
            pace.coded(20_000, 10_000.0, 25_600);
        }
        assert_eq!(
            pace.most(25_600),
            0,
            "a block a frame past the budget waits"
        );
        for _ in 1..REFRESH_PAUSE {
            pace.most(25_600);
        }
        assert_eq!(pace.most(25_600), 1);
    }

    #[test]
    fn a_resize_starts_the_ledger_over() {
        let mut ledger = BlockLedger::new(32, 32);
        ledger.frame([]);
        ledger.cleaned();
        ledger.fit(48, 32);
        assert_eq!(ledger.blocks(), 6);
        assert!(
            ledger.plan(0, 8, usize::MAX).is_some(),
            "every block unclean"
        );
    }
}