smudge-cpu 0.1.0

//! Drawing display items into the surface.
//!
//! Every pixel's coverage is computed from its own absolute position and the
//! shape that covers it, never from the area being drawn. Drawing any part of
//! the surface on its own therefore produces exactly the bytes a full repaint
//! would, however the damage is split. Glyphs meet the same rule through their
//! masks, which are rasterized whole and depend on nothing but the glyph, its
//! size and its subpixel phase.

use std::ops::Range;

use smudge_core::geometry::{Color, Corners, PixelRect, Point, Rect};
use smudge_core::paint::{DisplayItem, GlyphRun, PaintOp};

use crate::glyph_cache::{GlyphCache, MAX_GLYPH_SIZE, MaskKey};

/// The largest glyph position, in physical pixels from the surface origin,
/// that is placed at all.
///
/// It only keeps the integer placement of a glyph from overflowing. Ordinary
/// fonts keep their bearings within a few tens of thousands of pixels, so no
/// glyph they shape onto a surface comes near it. Culling by distance is left
/// to the clip, because a crafted font's bearing has no useful bound.
const PLACEMENT_LIMIT: f32 = 1.0e9;

/// The surface a display list walk converts logical coordinates against.
#[derive(Copy, Clone)]
pub(crate) struct Surface {
    /// Physical pixels per logical pixel.
    pub(crate) scale: f32,
    /// The surface width in physical pixels.
    pub(crate) width: u32,
    /// The surface height in physical pixels.
    pub(crate) height: u32,
}

/// Translates `rect` by `offset`, unless the offset is zero, which is what
/// operations outside every offset scope carry.
fn maybe_translated(rect: Rect, offset: Point) -> Rect {
    if offset == Point::default() {
        rect
    } else {
        rect.translated(offset)
    }
}

/// Walks `items` in paint order under `root`, calling `on_op` for every
/// drawable operation with the physical pixels it can change and the logical
/// offset the operation is drawn at.
///
/// `root` is the rectangle the walk repaints, usually a damage rectangle or
/// the whole surface: every area handed over lies inside it. Each operation's
/// area is its [`PaintOp::bounds`] in physical pixels, intersected with every
/// clip around it and clamped to the surface, so an operation outside `root`,
/// outside the surface, or under an empty clip draws nothing and is never
/// handed over. An offset scope moves the operations and the clips it wraps,
/// and the offsets it sits inside stack up. The walk visits clips, offsets and
/// operations once, in list order, so a caller pays one bounds conversion per
/// operation however many rectangles it repaints.
pub(crate) fn for_each_op(
    mut on_op: impl FnMut(usize, &PaintOp, PixelRect, Point),
    clips: &mut Vec<Option<PixelRect>>,
    offsets: &mut Vec<Point>,
    items: &[DisplayItem],
    surface: Surface,
    root: PixelRect,
) {
    clips.clear();
    clips.push(Some(root));
    offsets.clear();
    // The clip that operations see, always the top of `clips`, and the offset
    // operations and clips are translated by, the sum of the open scopes.
    let mut current = Some(root);
    let mut offset = Point::default();
    for (index, item) in items.iter().enumerate() {
        match item {
            DisplayItem::Op(op) => {
                if let Some(clip) = current
                    && let Some(area) = PixelRect::from_logical(
                        maybe_translated(op.bounds(), offset),
                        surface.scale,
                        surface.width,
                        surface.height,
                    )
                    .and_then(|area| area.intersect(clip))
                {
                    on_op(index, op, area, offset);
                }
            }
            DisplayItem::PushClip(rect) => {
                let inner = current.and_then(|outer| {
                    PixelRect::from_logical(
                        maybe_translated(*rect, offset),
                        surface.scale,
                        surface.width,
                        surface.height,
                    )
                    .and_then(|inner| inner.intersect(outer))
                });
                clips.push(inner);
                current = inner;
            }
            DisplayItem::PopClip => {
                // The root clip stays, so a list with more pops than pushes
                // keeps `root` as the clip.
                if clips.len() > 1 {
                    clips.pop();
                    current = clips.last().copied().flatten();
                }
            }
            DisplayItem::PushOffset(delta) => {
                offsets.push(offset);
                offset = Point {
                    x: offset.x + delta.x,
                    y: offset.y + delta.y,
                };
            }
            DisplayItem::PopOffset => {
                // An unbalanced list keeps the offset it has, as with clips.
                offset = offsets.pop().unwrap_or(offset);
            }
        }
    }
}

/// One operation of a [`RasterPlan`].
#[derive(Copy, Clone)]
pub(crate) struct PlannedOp {
    /// The index of the operation's [`DisplayItem::Op`] in the display list.
    pub(crate) index: usize,
    /// The physical pixels the operation can change, already intersected with
    /// every clip around it and clamped to the surface.
    pub(crate) area: PixelRect,
    /// The logical offset the operation's geometry is drawn at, the sum of
    /// the offset scopes around it.
    pub(crate) offset: Point,
}

/// A display list's drawable operations with the pixels each can change,
/// collected in one walk.
///
/// Replaying the list once per damage rectangle costs a walk of every item
/// and a bounds conversion of every operation per rectangle, and every clip
/// rescan costs a walk of its subtree. Collecting the operations once per
/// frame turns both into a single walk plus an integer intersection test per
/// operation and rectangle. On the scroll scene, where sixteen damage
/// rectangles cover a list of about two thousand items, that cut the raster
/// time from about 435 to 108 microseconds per frame, below the 156 of a
/// full repaint.
pub(crate) struct RasterPlan {
    /// The drawable operations, in paint order.
    ops: Vec<PlannedOp>,
    /// The clip stack scratch of the walk, reused between builds and walks.
    pub(crate) clips: Vec<Option<PixelRect>>,
    /// The offset stack scratch of the walk, reused between builds and walks.
    pub(crate) offsets: Vec<Point>,
}

impl RasterPlan {
    /// Creates an empty plan.
    pub(crate) fn new() -> RasterPlan {
        RasterPlan {
            ops: Vec::new(),
            clips: Vec::new(),
            offsets: Vec::new(),
        }
    }

    /// Collects the drawable operations of `items` for a surface of `width`
    /// by `height` physical pixels at `scale`.
    ///
    /// The caller treats a planned index as an operation item. That holds
    /// because only [`DisplayItem::Op`] entries push to [`RasterPlan::ops`].
    pub(crate) fn build(&mut self, items: &[DisplayItem], scale: f32, width: u32, height: u32) {
        self.ops.clear();
        for_each_op(
            |index, _op, area, offset| {
                self.ops.push(PlannedOp {
                    index,
                    area,
                    offset,
                })
            },
            &mut self.clips,
            &mut self.offsets,
            items,
            Surface {
                scale,
                width,
                height,
            },
            PixelRect {
                x: 0,
                y: 0,
                width,
                height,
            },
        );
    }

    /// Returns the planned operations in paint order.
    pub(crate) fn ops(&self) -> &[PlannedOp] {
        &self.ops
    }
}

/// The surface pixels and the scale that logical coordinates convert with.
pub(crate) struct Canvas<'a> {
    /// Premultiplied RGBA8 pixels, row-major with no padding.
    pub(crate) pixels: &'a mut [u8],
    /// The surface width in physical pixels.
    pub(crate) width: u32,
    /// Physical pixels per logical pixel.
    pub(crate) scale: f32,
    /// The cache of rasterized glyph masks, shared across frames.
    pub(crate) glyphs: &'a mut GlyphCache,
}

impl Canvas<'_> {
    /// Fills `rect` with `color`, replacing what was there.
    pub(crate) fn clear(&mut self, rect: PixelRect, color: Color) {
        let alpha = u32::from(color.a);
        let pixel = [
            premultiply(color.r, alpha),
            premultiply(color.g, alpha),
            premultiply(color.b, alpha),
            color.a,
        ];
        for y in rect.y..rect.y + rect.height {
            let start = self.index(rect.x, y);
            let row = &mut self.pixels[start..start + rect.width as usize * 4];
            row.as_chunks_mut::<4>().0.fill(pixel);
        }
    }

    /// Draws `op` into `area`, the part of the operation's bounds inside the
    /// clip and the rectangle being repainted.
    ///
    /// `offset` is the logical translation the offset scopes around the
    /// operation apply to it: the operation's geometry is drawn moved by it,
    /// while `area` is where the moved operation can land.
    pub(crate) fn draw(&mut self, op: &PaintOp, area: PixelRect, offset: Point) {
        match *op {
            PaintOp::FillRect {
                rect,
                radius,
                color,
            } => {
                if let Some(shape) = Shape::new(maybe_translated(rect, offset), radius, self.scale)
                {
                    self.fill(
                        area,
                        color,
                        |x, y| shape.coverage(x, y),
                        |y| shape.steady(y),
                    );
                }
            }
            PaintOp::StrokeRect {
                rect,
                radius,
                width,
                color,
            } => {
                if !width.is_finite() || width <= 0.0 {
                    return;
                }
                let Some(outer) = Shape::new(maybe_translated(rect, offset), radius, self.scale)
                else {
                    return;
                };
                match outer.inset(width * self.scale) {
                    Some(inner) => self.fill(
                        area,
                        color,
                        |x, y| (outer.coverage(x, y) - inner.coverage(x, y)).max(0.0),
                        |y| inner.steady(y),
                    ),
                    None => self.fill(
                        area,
                        color,
                        |x, y| outer.coverage(x, y),
                        |y| outer.steady(y),
                    ),
                }
            }
            PaintOp::Glyphs(ref run) => self.draw_glyphs(run.as_ref(), area, offset),
        }
    }

    /// Blits every glyph of `run` that reaches into `area`, the part of the
    /// run's ink bounds inside the clip, with the run drawn moved by the
    /// logical `offset`.
    ///
    /// Each glyph is drawn from its cached alpha mask at its own physical
    /// position. A glyph's mask depends on the glyph, its quantized size and
    /// its subpixel x phase only, so the same text blits the same bytes
    /// whichever part of the surface is drawn. Glyphs whose ink bounds claim
    /// no pixels draw nothing, which keeps a run inside the damage its bounds
    /// produced even when a font's metrics disagree with its outlines.
    ///
    /// A glyph whose size or position is not finite, whose size exceeds
    /// [`MAX_GLYPH_SIZE`] physical pixels, or whose origin lies more than
    /// [`PLACEMENT_LIMIT`] physical pixels from the surface origin draws
    /// nothing.
    fn draw_glyphs(&mut self, run: &GlyphRun, area: PixelRect, offset: Point) {
        let size_px = run.size * self.scale;
        if !run.size.is_finite()
            || run.size <= 0.0
            || !size_px.is_finite()
            || size_px <= 0.0
            || size_px > MAX_GLYPH_SIZE
        {
            return;
        }
        // The size the masks are rasterized at, quantized to 1/64 of a pixel,
        // is what the cache keys a glyph by.
        let size = (size_px * 64.0).round() as i32;
        if size <= 0 {
            return;
        }
        let Canvas {
            pixels,
            width,
            scale,
            glyphs,
            ..
        } = self;
        let scale = *scale;
        let shift_x = offset.x * scale;
        let shift_y = offset.y * scale;
        for glyph in &run.glyphs {
            let x = glyph.x * scale + shift_x;
            let y = (glyph.y * scale + shift_y).round();
            // Only positions far past any surface are skipped, so the integer
            // placement below cannot overflow. A bearing is not bounded by
            // the mask size, so nothing closer may be skipped, and the clip to
            // `area` handles everything in between.
            if !(-PLACEMENT_LIMIT..=PLACEMENT_LIMIT).contains(&x)
                || !(-PLACEMENT_LIMIT..=PLACEMENT_LIMIT).contains(&y)
            {
                continue;
            }
            let origin_x = x.floor();
            let subpixel = ((x - origin_x) * 4.0) as u32 % 4;
            let key = MaskKey {
                font_id: run.font.id,
                font_index: run.font.index,
                glyph_id: glyph.id,
                size,
                subpixel,
            };
            let Some(entry) = glyphs.entry(key, &run.font) else {
                continue;
            };
            let (mask_width, mask_height) = (entry.width(), entry.height());
            if mask_width == 0 || mask_height == 0 {
                continue;
            }

            // The mask is placed at the glyph's baseline origin, offset by its
            // bearings. Intersecting with `area` keeps every write inside the
            // run's ink bounds and the clip, which is what the damage covers.
            let x0 = origin_x as i64 + i64::from(entry.left());
            let y0 = y as i64 + i64::from(entry.top());
            let x1 = x0 + i64::from(mask_width);
            let y1 = y0 + i64::from(mask_height);
            let ix0 = x0.max(i64::from(area.x));
            let iy0 = y0.max(i64::from(area.y));
            let ix1 = x1.min(i64::from(area.x) + i64::from(area.width));
            let iy1 = y1.min(i64::from(area.y) + i64::from(area.height));
            if ix0 >= ix1 || iy0 >= iy1 {
                continue;
            }

            let mut mask_offset = ((iy0 - y0) as usize) * mask_width as usize + (ix0 - x0) as usize;
            let row_bytes = (ix1 - ix0) as usize * 4;
            for y in iy0..iy1 {
                let start = (y as usize * *width as usize + ix0 as usize) * 4;
                let row = &mut pixels[start..start + row_bytes];
                let coverage = &entry.data()[mask_offset..mask_offset + (ix1 - ix0) as usize];
                for (target, &coverage) in row.as_chunks_mut::<4>().0.iter_mut().zip(coverage) {
                    if coverage == 0 {
                        continue;
                    }
                    let alpha = (u32::from(coverage) * u32::from(run.color.a) + 127) / 255;
                    blend(target, run.color, alpha);
                }
                mask_offset += mask_width as usize;
            }
        }
    }

    /// Blends `color` into every pixel of `area`, weighted by the coverage
    /// that `coverage` gives for the pixel's absolute position.
    ///
    /// `steady` returns, for a row, a run of pixels that all share one
    /// coverage, so the coverage is computed once for the whole run. Which
    /// pixels fall in the run depends only on their position, so a pixel gets
    /// the same value whichever part of the surface is drawn. Filling the run
    /// this way took a full repaint of a 1920 by 1080 scene of 200 rounded,
    /// bordered panels from 18.6 ms to 2.9 ms in a release build.
    fn fill(
        &mut self,
        area: PixelRect,
        color: Color,
        coverage: impl Fn(u32, u32) -> f32,
        steady: impl Fn(u32) -> Range<u32>,
    ) {
        if color.a == 0 {
            return;
        }
        let to_alpha = |coverage: f32| (coverage * f32::from(color.a) + 0.5) as u32;
        let right = area.x + area.width;
        for y in area.y..area.y + area.height {
            let run = steady(y);
            let start = run.start.clamp(area.x, right);
            let end = run.end.clamp(start, right);
            let row_start = self.index(area.x, y);
            let row = &mut self.pixels[row_start..row_start + area.width as usize * 4];
            let (before, rest) = row.split_at_mut((start - area.x) as usize * 4);
            let (middle, after) = rest.split_at_mut((end - start) as usize * 4);

            for (x, target) in (area.x..).zip(before.as_chunks_mut::<4>().0) {
                put(target, color, to_alpha(coverage(x, y)));
            }
            if start < end {
                let middle = middle.as_chunks_mut::<4>().0;
                match to_alpha(coverage(start, y)) {
                    0 => {}
                    255 => middle.fill([color.r, color.g, color.b, 255]),
                    alpha => middle
                        .iter_mut()
                        .for_each(|target| blend(target, color, alpha)),
                }
            }
            for (x, target) in (end..).zip(after.as_chunks_mut::<4>().0) {
                put(target, color, to_alpha(coverage(x, y)));
            }
        }
    }

    /// Returns the byte offset of pixel `(x, y)`.
    fn index(&self, x: u32, y: u32) -> usize {
        (y as usize * self.width as usize + x as usize) * 4
    }
}

/// A rounded rectangle in physical pixels whose radii fit inside it.
#[derive(Copy, Clone)]
struct Shape {
    /// The left edge.
    x0: f32,
    /// The top edge.
    y0: f32,
    /// The right edge.
    x1: f32,
    /// The bottom edge.
    y1: f32,
    /// The corner radii, each at most half the shorter side.
    radius: Corners,
}

impl Shape {
    /// Converts a logical rectangle and its logical radii to physical pixels.
    ///
    /// Returns `None` when the rectangle is empty or holds a coordinate that is
    /// not finite.
    fn new(rect: Rect, radius: Corners, scale: f32) -> Option<Shape> {
        let scaled = Corners {
            top_left: radius.top_left * scale,
            top_right: radius.top_right * scale,
            bottom_right: radius.bottom_right * scale,
            bottom_left: radius.bottom_left * scale,
        };
        Shape::fitted(
            rect.x0 * scale,
            rect.y0 * scale,
            rect.x1 * scale,
            rect.y1 * scale,
            scaled,
        )
    }

    /// Returns the shape that lies `by` pixels inside this one, with each
    /// radius shrunk by the same amount so the two edges stay `by` apart.
    ///
    /// Returns `None` when nothing is left inside.
    fn inset(&self, by: f32) -> Option<Shape> {
        let radius = self.radius;
        Shape::fitted(
            self.x0 + by,
            self.y0 + by,
            self.x1 - by,
            self.y1 - by,
            Corners {
                top_left: radius.top_left - by,
                top_right: radius.top_right - by,
                bottom_right: radius.bottom_right - by,
                bottom_left: radius.bottom_left - by,
            },
        )
    }

    /// Builds a shape from physical edges, clamping each radius to between
    /// zero and half the shorter side.
    fn fitted(x0: f32, y0: f32, x1: f32, y1: f32, radius: Corners) -> Option<Shape> {
        let finite = x0.is_finite() && y0.is_finite() && x1.is_finite() && y1.is_finite();
        if !finite || x0 >= x1 || y0 >= y1 {
            return None;
        }
        let limit = (x1 - x0).min(y1 - y0) / 2.0;
        let fit = |radius: f32| radius.max(0.0).min(limit);
        Some(Shape {
            x0,
            y0,
            x1,
            y1,
            radius: Corners {
                top_left: fit(radius.top_left),
                top_right: fit(radius.top_right),
                bottom_right: fit(radius.bottom_right),
                bottom_left: fit(radius.bottom_left),
            },
        })
    }

    /// Returns the pixels of row `y` that lie wholly inside the shape's
    /// straight edges and outside every corner square, which all share the
    /// row's vertical coverage.
    fn steady(&self, y: u32) -> Range<u32> {
        let top = y as f32;
        let down = self.y1.min(top + 1.0) - self.y0.max(top);
        if down <= 0.0 {
            return 0..0;
        }
        let cy = top + 0.5;
        let Corners {
            top_left,
            top_right,
            bottom_right,
            bottom_left,
        } = self.radius;
        let band = |upper: f32, lower: f32| {
            if cy < self.y0 + upper {
                upper
            } else if cy > self.y1 - lower {
                lower
            } else {
                0.0
            }
        };
        let start = (self.x0 + band(top_left, bottom_left)).ceil() as u32;
        let end = (self.x1 - band(top_right, bottom_right)).floor() as u32;
        start..end.max(start)
    }

    /// Returns how much of pixel `(x, y)` the shape covers, from 0 to 1.
    ///
    /// Along the straight edges this is the exact area of the pixel inside the
    /// shape. Inside a corner square it is also limited by the distance from
    /// the pixel center to the arc, which approximates the area the arc cuts
    /// off.
    fn coverage(&self, x: u32, y: u32) -> f32 {
        let (left, top) = (x as f32, y as f32);
        let across = (self.x1.min(left + 1.0) - self.x0.max(left)).clamp(0.0, 1.0);
        let down = (self.y1.min(top + 1.0) - self.y0.max(top)).clamp(0.0, 1.0);
        let area = across * down;
        if area == 0.0 {
            return 0.0;
        }

        let (cx, cy) = (left + 0.5, top + 0.5);
        let Corners {
            top_left,
            top_right,
            bottom_right,
            bottom_left,
        } = self.radius;
        let corner = if cx < self.x0 + top_left && cy < self.y0 + top_left {
            (top_left, self.x0 + top_left, self.y0 + top_left)
        } else if cx > self.x1 - top_right && cy < self.y0 + top_right {
            (top_right, self.x1 - top_right, self.y0 + top_right)
        } else if cx > self.x1 - bottom_right && cy > self.y1 - bottom_right {
            (bottom_right, self.x1 - bottom_right, self.y1 - bottom_right)
        } else if cx < self.x0 + bottom_left && cy > self.y1 - bottom_left {
            (bottom_left, self.x0 + bottom_left, self.y1 - bottom_left)
        } else {
            return area;
        };
        let (radius, ox, oy) = corner;
        let distance = (cx - ox).hypot(cy - oy);
        area.min((radius - distance + 0.5).clamp(0.0, 1.0))
    }
}

/// Draws `color` at `alpha` into a premultiplied pixel.
fn put(target: &mut [u8; 4], color: Color, alpha: u32) {
    match alpha {
        0 => {}
        255 => *target = [color.r, color.g, color.b, 255],
        _ => blend(target, color, alpha),
    }
}

/// Blends straight-alpha `color` at `alpha` over a premultiplied pixel.
fn blend(target: &mut [u8; 4], color: Color, alpha: u32) {
    let rest = 255 - alpha;
    let mix = |source: u8, target: u8| {
        ((u32::from(source) * alpha + u32::from(target) * rest + 127) / 255) as u8
    };
    target[0] = mix(color.r, target[0]);
    target[1] = mix(color.g, target[1]);
    target[2] = mix(color.b, target[2]);
    target[3] = mix(255, target[3]);
}

/// Returns `channel` multiplied by `alpha` out of 255, rounded.
fn premultiply(channel: u8, alpha: u32) -> u8 {
    ((u32::from(channel) * alpha + 127) / 255) as u8
}