Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / raster / ft_grays.lucb

#==============================================================================================
#
#   ft_grays - FreeType's anti-aliasing rasterizer, for glyph masks
#
#   DESCRIPTION:
#       Port of FreeType 2.13.3's smooth rasterizer (src/smooth/ftgrays.c, the 64-bit build:
#       FT_INT64 is defined, so lines are walked cell by cell with `prod` and conics are drawn
#       by forward differences) and of FT_Outline_Decompose (src/base/ftoutln.c), as
#       FT_Outline_Get_Bitmap runs them for an 8-bit gray bitmap. Ladybird's Skia asks
#       FreeType for every glyph mask (SkScalerContext_FreeType::generateImage), so text drawn
#       through this rasterizer has the coverage of the reference screenshots, byte for byte:
#       the arithmetic is integer only and the same on every platform.
#
#       Cells live in one growable pool instead of ftgrays' fixed render pool, so the whole
#       bitmap is one band (FreeType bisects bands only when its pool overflows; a cell's
#       cover and area do not depend on the band it was computed in).
#
#       Copyright (c) 2000-2024 by David Turner, Robert Wilhelm, and Werner Lemberg.
#       Copyright (c) 2026 the luce-browser authors.
#       SPDX-License-Identifier: FTL (see LICENSE-freetype)
#
#==============================================================================================

# mark: Outlines ===============================================================================

## FT_CURVE_TAG's values: an on-curve point, a conic (quadratic) and a cubic control point.
pub let ft_curve_tag_on: u8 = 1
pub let ft_curve_tag_conic: u8 = 0
pub let ft_curve_tag_cubic: u8 = 2

## An FT_Outline as the rasterizer reads it: points in 26.6 fixed point with y growing
## upward, their curve tags (FT_CURVE_TAG reads the low two bits), the index of each
## contour's last point, and the fill rule (FT_OUTLINE_EVEN_ODD_FILL).
pub struct FtOutline:
    pub var xs: const i64[]
    pub var ys: const i64[]
    pub var tags: const u8[]
    pub var contour_ends: const usize[]
    pub var even_odd: bool

## FT_Outline_Get_CBox: the bounding box of every point, control points included, as
## (x_min, y_min, x_max, y_max); zeros for an outline without points.
pub func ft_outline_cbox(outline: const FtOutline*) -> (i64, i64, i64, i64):
    if outline.xs.length == 0:
        return (0, 0, 0, 0)
    var x_min = outline.xs[0]
    var x_max = x_min
    var y_min = outline.ys[0]
    var y_max = y_min
    for i in 1..<outline.xs.length:
        let x = outline.xs[i]
        if x < x_min:
            x_min = x
        if x > x_max:
            x_max = x
        let y = outline.ys[i]
        if y < y_min:
            y_min = y
        if y > y_max:
            y_max = y
    return (x_min, y_min, x_max, y_max)

# mark: The worker =============================================================================

## PIXEL_BITS: the rasterizer's subpixel precision (ONE_PIXEL is 256 units).
let gray_pixel_bits: i64 = 8
let gray_one_pixel: i64 = 256

## The null cell's index: ftgrays' dumpster cell, whose x is CELL_MAX_X_VALUE.
let gray_null_cell: i32 = -1

## TCell: one pixel's accumulated cover and area, linked to the next cell of its row.
struct GrayCell:
    var x: i32
    var cover: i32
    var area: i32
    var next: i32

## gray_TWorker: the cells of the band, the current cell and pen position, the target.
struct GrayWorker:
    var min_ex: i32
    var max_ex: i32
    var min_ey: i32
    var max_ey: i32
    var count_ey: i32
    var cells: Vec[GrayCell]
    ## The first cell of each row (`ycells`), the null cell for an empty row.
    var ycells: Vec[i32]
    ## The current cell, or the null cell.
    var cell: i32
    ## The null cell's accumulators (written to and never read, as ftgrays' dumpster).
    var dumpster: GrayCell
    ## The last pen position, in 1/256 pixels.
    var x: i64
    var y: i64

    func release():
        self.cells.release()
        self.ycells.release()

## TRUNC: the integer pixel of a 1/256 coordinate.
func gray_trunc(x: i64) -> i32:
    return (i32)(x >> gray_pixel_bits)

## FRACT: the fraction of a 1/256 coordinate.
func gray_fract(x: i64) -> i32:
    return (i32)(x & (gray_one_pixel - 1))

## UPSCALE: 26.6 to 1/256 pixels.
func gray_upscale(x: i64) -> i64:
    return x * (gray_one_pixel >> 6)

## FT_UDIVPREP's reciprocal: (FT_Int64)0xFFFFFFFF / b, or 0 when `c` is false.
func gray_udiv_prep(c: bool, b: i64) -> i64:
    return 0xFFFFFFFF // b if c else 0

## FT_UDIV: `a` divided through the reciprocal `b_r`, ((FT_UInt64)a * (FT_UInt64)b_r) >> 32.
func gray_udiv(a: i64, b_r: i64) -> i32:
    return (i32)(((u64)a *% (u64)b_r) >> 32)

## The current cell's accumulators.
func gray_current(ras: GrayWorker*) -> GrayCell*:
    if ras.cell == gray_null_cell:
        return &ras.dumpster
    return &ras.cells.data[(usize)ras.cell]

## FT_INTEGRATE: adds `a` to the current cell's cover and `a * b` to its area (TArea is
## an int, and ADD_INT wraps).
func gray_integrate(ras: GrayWorker*, a: i32, b: i32):
    let cell = gray_current(ras)
    cell.cover = cell.cover +% a
    cell.area = cell.area +% a *% b

## gray_set_cell: makes the cell at (ex, ey) current, inserting it into its row's list in x
## order. Cells outside the band (or right of it) go to the null cell; cells left of it are
## gathered at min_ex - 1.
func gray_set_cell(ras: GrayWorker*, ex0: i32, ey: i32):
    let ey_index = ey - ras.min_ey
    if ey_index < 0 or ey_index >= ras.count_ey or ex0 >= ras.max_ex:
        ras.cell = gray_null_cell
        return
    let ex = ex0 if ex0 > ras.min_ex - 1 else ras.min_ex - 1
    # `link` is where the pointer to the next cell lives: the row's head, or a cell's next.
    var previous = gray_null_cell
    var cell = ras.ycells.data[(usize)ey_index]
    while cell != gray_null_cell:
        let x = ras.cells.data[(usize)cell].x
        if x > ex:
            break
        if x == ex:
            ras.cell = cell
            return
        previous = cell
        cell = ras.cells.data[(usize)cell].next
    let index = (i32)ras.cells.len
    ras.cells.push(GrayCell(x = ex, cover = 0, area = 0, next = cell))
    if previous == gray_null_cell:
        ras.ycells.data[(usize)ey_index] = index
    else:
        ras.cells.data[(usize)previous].next = index
    ras.cell = index

# mark: Lines and curves =======================================================================

## gray_render_line (the FT_INT64 version): a straight line from the pen to (to_x, to_y),
## across as many cells as it touches, in any direction.
func gray_render_line(ras: GrayWorker*, to_x: i64, to_y: i64):
    var ey1 = gray_trunc(ras.y)
    let ey2 = gray_trunc(to_y)

    # perform vertical clipping
    if (ey1 >= ras.max_ey and ey2 >= ras.max_ey) or (ey1 < ras.min_ey and ey2 < ras.min_ey):
        ras.x = to_x
        ras.y = to_y
        return

    var ex1 = gray_trunc(ras.x)
    let ex2 = gray_trunc(to_x)
    var fx1 = gray_fract(ras.x)
    var fy1 = gray_fract(ras.y)

    let dx = to_x - ras.x
    let dy = to_y - ras.y

    if ex1 == ex2 and ey1 == ey2:
        # inside one cell
        _ = 0
    elif dy == 0:
        # any horizontal line
        gray_set_cell(ras, ex2, ey2)
        ras.x = to_x
        ras.y = to_y
        return
    elif dx == 0:
        if dy > 0:
            # vertical line up
            while true:
                let fy2 = (i32)gray_one_pixel
                gray_integrate(ras, fy2 - fy1, fx1 * 2)
                fy1 = 0
                ey1 += 1
                gray_set_cell(ras, ex1, ey1)
                if ey1 == ey2:
                    break
        else:
            # vertical line down
            while true:
                let fy2: i32 = 0
                gray_integrate(ras, fy2 - fy1, fx1 * 2)
                fy1 = (i32)gray_one_pixel
                ey1 -= 1
                gray_set_cell(ras, ex1, ey1)
                if ey1 == ey2:
                    break
    else:
        # any other line
        var prod = dx * (i64)fy1 - dy * (i64)fx1
        let dx_r = gray_udiv_prep(ex1 != ex2, dx)
        let dy_r = gray_udiv_prep(ey1 != ey2, dy)

        # The fundamental value `prod' determines which side and the exact coordinate where
        # the line exits current cell. It is also easily updated when moving from one cell
        # to the next.
        while true:
            var fx2: i32
            var fy2: i32
            if prod - dx * gray_one_pixel > 0 and prod <= 0:
                # left
                fx2 = 0
                fy2 = gray_udiv(-prod, -dx_r)
                prod -= dy * gray_one_pixel
                gray_integrate(ras, fy2 - fy1, fx1 + fx2)
                fx1 = (i32)gray_one_pixel
                fy1 = fy2
                ex1 -= 1
            elif prod - dx * gray_one_pixel + dy * gray_one_pixel > 0 and prod - dx * gray_one_pixel <= 0:
                # up
                prod -= dx * gray_one_pixel
                fx2 = gray_udiv(-prod, dy_r)
                fy2 = (i32)gray_one_pixel
                gray_integrate(ras, fy2 - fy1, fx1 + fx2)
                fx1 = fx2
                fy1 = 0
                ey1 += 1
            elif prod + dy * gray_one_pixel >= 0 and prod - dx * gray_one_pixel + dy * gray_one_pixel <= 0:
                # right
                prod += dy * gray_one_pixel
                fx2 = (i32)gray_one_pixel
                fy2 = gray_udiv(prod, dx_r)
                gray_integrate(ras, fy2 - fy1, fx1 + fx2)
                fx1 = 0
                fy1 = fy2
                ex1 += 1
            else:
                # down
                fx2 = gray_udiv(prod, -dy_r)
                fy2 = 0
                prod += dx * gray_one_pixel
                gray_integrate(ras, fy2 - fy1, fx1 + fx2)
                fx1 = fx2
                fy1 = (i32)gray_one_pixel
                ey1 -= 1
            gray_set_cell(ras, ex1, ey1)
            if ex1 == ex2 and ey1 == ey2:
                break

    let fx2 = gray_fract(to_x)
    let fy2 = gray_fract(to_y)
    gray_integrate(ras, fy2 - fy1, fx1 + fx2)
    ras.x = to_x
    ras.y = to_y

## gray_render_conic (the FT_INT64 version): a quadratic arc from the pen, drawn as the
## lines between points computed by forward differences at a power-of-two step.
func gray_render_conic(ras: GrayWorker*, control_x: i64, control_y: i64, to_x: i64, to_y: i64):
    let p0x = ras.x
    let p0y = ras.y
    let p1x = gray_upscale(control_x)
    let p1y = gray_upscale(control_y)
    let p2x = gray_upscale(to_x)
    let p2y = gray_upscale(to_y)

    # short-cut the arc that crosses the current band
    if (gray_trunc(p0y) >= ras.max_ey and gray_trunc(p1y) >= ras.max_ey and gray_trunc(p2y) >= ras.max_ey) or (gray_trunc(p0y) < ras.min_ey and gray_trunc(p1y) < ras.min_ey and gray_trunc(p2y) < ras.min_ey):
        ras.x = p2x
        ras.y = p2y
        return

    let bx = p1x - p0x
    let by = p1y - p0y
    let ax = p2x - p1x - bx  # p0.x + p2.x - 2 * p1.x
    let ay = p2y - p1y - by  # p0.y + p2.y - 2 * p1.y

    var dx = ax if ax >= 0 else -ax
    let dy = ay if ay >= 0 else -ay
    if dx < dy:
        dx = dy

    if dx <= gray_one_pixel // 4:
        gray_render_line(ras, p2x, p2y)
        return

    # We can calculate the number of necessary segments because each bisection predictably
    # reduces deviation exactly 4-fold. Even 32-bit deviation would vanish after 16
    # bisections.
    var shift: i64 = 16
    while true:
        dx >>= 2
        shift -= 1
        if not (dx > gray_one_pixel // 4):
            break
    var count = (u32)0x10000 >> (u32)shift

    # Q << 32 = (B << (33 - N)) + (A << (32 - 2*N)), R << 32 = A << (33 - 2*N): positions are
    # computed on 64-bit values scaled by 2^32.
    var rx = (i64)((u64)ax << (u64)(shift + shift))
    var ry = (i64)((u64)ay << (u64)(shift + shift))
    var qx = (i64)((u64)bx << (u64)(shift + 17)) +% rx
    var qy = (i64)((u64)by << (u64)(shift + 17)) +% ry

    rx = rx *% 2
    ry = ry *% 2

    var px = (i64)((u64)p0x << 32)
    var py = (i64)((u64)p0y << 32)

    while true:
        px = px +% qx
        py = py +% qy
        qx = qx +% rx
        qy = qy +% ry
        gray_render_line(ras, px >> 32, py >> 32)
        count -= 1
        if count == 0:
            break

## A point of the curve stacks.
struct GrayVector:
    var x: i64
    var y: i64

## gray_split_cubic: splits the cubic at base[0..3] in two at t = 1/2, into base[0..6].
func gray_split_cubic(arc: GrayVector[], base: usize):
    var a: i64
    var b: i64
    var c: i64

    arc[base + 6].x = arc[base + 3].x
    a = arc[base + 0].x + arc[base + 1].x
    b = arc[base + 1].x + arc[base + 2].x
    c = arc[base + 2].x + arc[base + 3].x
    arc[base + 5].x = c >> 1
    c += b
    arc[base + 4].x = c >> 2
    arc[base + 1].x = a >> 1
    a += b
    arc[base + 2].x = a >> 2
    arc[base + 3].x = (a + c) >> 3

    arc[base + 6].y = arc[base + 3].y
    a = arc[base + 0].y + arc[base + 1].y
    b = arc[base + 1].y + arc[base + 2].y
    c = arc[base + 2].y + arc[base + 3].y
    arc[base + 5].y = c >> 1
    c += b
    arc[base + 4].y = c >> 2
    arc[base + 1].y = a >> 1
    a += b
    arc[base + 2].y = a >> 2
    arc[base + 3].y = (a + c) >> 3

func gray_abs(x: i64) -> i64:
    return x if x >= 0 else -x

## gray_render_cubic: a cubic arc from the pen, split in halves until each piece is flat
## enough (its control points within half a pixel of the chord's trisection points).
func gray_render_cubic(ras: GrayWorker*, control1: GrayVector, control2: GrayVector, to: GrayVector):
    var arc: GrayVector[16 * 3 + 1]  # enough to accommodate bisections
    var top: usize = 0

    arc[0] = GrayVector(x = gray_upscale(to.x), y = gray_upscale(to.y))
    arc[1] = GrayVector(x = gray_upscale(control2.x), y = gray_upscale(control2.y))
    arc[2] = GrayVector(x = gray_upscale(control1.x), y = gray_upscale(control1.y))
    arc[3] = GrayVector(x = ras.x, y = ras.y)

    # short-cut the arc that crosses the current band
    if (gray_trunc(arc[0].y) >= ras.max_ey and gray_trunc(arc[1].y) >= ras.max_ey and gray_trunc(arc[2].y) >= ras.max_ey and gray_trunc(arc[3].y) >= ras.max_ey) or (gray_trunc(arc[0].y) < ras.min_ey and gray_trunc(arc[1].y) < ras.min_ey and gray_trunc(arc[2].y) < ras.min_ey and gray_trunc(arc[3].y) < ras.min_ey):
        ras.x = arc[0].x
        ras.y = arc[0].y
        return

    while true:
        # with each split, control points quickly converge towards chord trisection points
        # and the vanishing distances below indicate when the segment is flat enough to draw
        let flat_limit = gray_one_pixel // 2
        if gray_abs(2 * arc[top].x - 3 * arc[top + 1].x + arc[top + 3].x) > flat_limit or gray_abs(2 * arc[top].y - 3 * arc[top + 1].y + arc[top + 3].y) > flat_limit or gray_abs(arc[top].x - 3 * arc[top + 2].x + 2 * arc[top + 3].x) > flat_limit or gray_abs(arc[top].y - 3 * arc[top + 2].y + 2 * arc[top + 3].y) > flat_limit:
            gray_split_cubic(arc, top)
            top += 3
            continue

        gray_render_line(ras, arc[top].x, arc[top].y)

        if top == 0:
            return
        top -= 3

## gray_move_to: starts a new contour at `to`.
func gray_move_to(ras: GrayWorker*, to: GrayVector):
    let x = gray_upscale(to.x)
    let y = gray_upscale(to.y)
    gray_set_cell(ras, gray_trunc(x), gray_trunc(y))
    ras.x = x
    ras.y = y

# mark: FT_Outline_Decompose ===================================================================

## FT_CURVE_TAG.
func ft_curve_tag(flag: u8) -> u8:
    return flag & 3

## The point `index` of `outline`.
func ft_outline_point(outline: const FtOutline*, index: usize) -> GrayVector:
    return GrayVector(x = outline.xs[index], y = outline.ys[index])

## FT_Outline_Decompose with ftgrays' emitters (shift 0, delta 0): walks every contour and
## draws its lines, conic arcs (with the implied on-curve midpoints between two conic control
## points) and cubic arcs. False for an invalid outline (FT_THROW(Invalid_Outline)).
func ft_outline_decompose(outline: const FtOutline*, ras: GrayWorker*) -> bool:
    var last: i64 = -1
    for n in 0..<outline.contour_ends.length:
        let first = (usize)(last + 1)
        last = (i64)outline.contour_ends[n]
        if last < (i64)first:
            return false
        var limit = (usize)last

        var v_start = ft_outline_point(outline, first)
        let v_last = ft_outline_point(outline, (usize)last)
        var v_control = v_start

        var tag = ft_curve_tag(outline.tags[first])

        # A contour cannot start with a cubic control point!
        if tag == ft_curve_tag_cubic:
            return false

        # check first point to determine origin
        var started_before_first = false
        if tag == ft_curve_tag_conic:
            # first point is conic control. Yes, this happens.
            if ft_curve_tag(outline.tags[(usize)last]) == ft_curve_tag_on:
                # start at last point if it is on the curve
                v_start = v_last
                limit -= 1
            else:
                # if both first and last points are conic, start at their middle and record
                # its position for closure
                v_start.x = (v_start.x + v_last.x) // 2
                v_start.y = (v_start.y + v_last.y) // 2
            started_before_first = true

        gray_move_to(ras, v_start)

        # Iterate as ftoutln.c does, with `point` pointing at the point last read; when the
        # first point is a conic control point, iteration starts one before it.
        var closed = false
        var at = first
        var before_first = started_before_first
        while true:
            # while ( point < limit ): point++
            if before_first:
                before_first = false
            else:
                if not (at < limit):
                    break
                at += 1
            tag = ft_curve_tag(outline.tags[at])
            if tag == ft_curve_tag_on:
                # emit a single line_to
                let vec = ft_outline_point(outline, at)
                gray_render_line(ras, gray_upscale(vec.x), gray_upscale(vec.y))
                continue
            if tag == ft_curve_tag_conic:
                # consume conic arcs
                v_control = ft_outline_point(outline, at)
                var done_contour = false
                while true:
                    # Do_Conic:
                    if at < limit:
                        at += 1
                        let next_tag = ft_curve_tag(outline.tags[at])
                        let vec = ft_outline_point(outline, at)
                        if next_tag == ft_curve_tag_on:
                            gray_render_conic(ras, v_control.x, v_control.y, vec.x, vec.y)
                            break
                        if next_tag != ft_curve_tag_conic:
                            return false
                        let v_middle = GrayVector(x = (v_control.x + vec.x) // 2, y = (v_control.y + vec.y) // 2)
                        gray_render_conic(ras, v_control.x, v_control.y, v_middle.x, v_middle.y)
                        v_control = vec
                        continue
                    gray_render_conic(ras, v_control.x, v_control.y, v_start.x, v_start.y)
                    done_contour = true
                    break
                if done_contour:
                    closed = true
                    break
                continue
            # FT_CURVE_TAG_CUBIC
            if at + 1 > limit or ft_curve_tag(outline.tags[at + 1]) != ft_curve_tag_cubic:
                return false
            at += 2
            let vec1 = ft_outline_point(outline, at - 2)
            let vec2 = ft_outline_point(outline, at - 1)
            if at <= limit:
                let vec = ft_outline_point(outline, at)
                gray_render_cubic(ras, vec1, vec2, vec)
                continue
            gray_render_cubic(ras, vec1, vec2, v_start)
            closed = true
            break

        if not closed:
            # close the contour with a line segment
            gray_render_line(ras, gray_upscale(v_start.x), gray_upscale(v_start.y))
    return true

# mark: Sweeping and rendering =================================================================

## FT_FILL_RULE: scales a cell's area to a coverage byte and applies the fill rule (`fill`
## is INT_MIN for non-zero, whose higher coverages are clamped, and 0x100 for even-odd,
## whose higher bits are dropped when the byte is stored).
func gray_fill_rule(area: i32, fill: i32) -> i32:
    var coverage = area >> (gray_pixel_bits * 2 + 1 - 8)
    if (coverage & fill) != 0:
        coverage = ~coverage
    if coverage > 255 and (fill & i32_min) != 0:
        coverage = 255
    return coverage

## gray_sweep: turns the cells of every row into coverage bytes in the target, whose row
## `y` (counted upward from the bottom) is `buffer[(rows - 1 - y) * pitch ..]`.
func gray_sweep(ras: GrayWorker*, even_odd: bool, buffer: u8[], rows: i32, pitch: i32):
    let fill: i32 = 0x100 if even_odd else i32_min
    for y in ras.min_ey..<ras.max_ey:
        var cell = ras.ycells.data[(usize)(y - ras.min_ey)]
        var x = ras.min_ex
        var cover: i32 = 0
        let line = (usize)((rows - 1 - y) * pitch)

        while cell != gray_null_cell:
            let c = ras.cells.data[(usize)cell]
            if cover != 0 and c.x > x:
                let coverage = (u8)gray_fill_rule(cover, fill)
                for i in x..<c.x:
                    buffer[line + (usize)i] = coverage

            cover = cover +% c.cover *% (i32)(gray_one_pixel * 2)
            let area = cover -% c.area

            if area != 0 and c.x >= ras.min_ex:
                buffer[line + (usize)c.x] = (u8)gray_fill_rule(area, fill)

            x = c.x + 1
            cell = c.next

        if cover != 0:
            # only if cropped
            let coverage = (u8)gray_fill_rule(cover, fill)
            for i in x..<ras.max_ex:
                buffer[line + (usize)i] = coverage

## FT_Outline_Get_Bitmap into an 8-bit gray bitmap (gray_raster_render with
## FT_RASTER_FLAG_AA): draws `outline` into `buffer`, `width` x `rows` bytes whose rows are
## `pitch` bytes apart, top row first. The bitmap's (0, 0) is the outline's origin, at the
## bottom-left corner. Coverage is written where the outline has some; the rest of the
## buffer is left as it is (Skia clears it first). False for an invalid outline.
pub func ft_outline_render_gray(outline: const FtOutline*, buffer: u8[], width: i32, rows: i32, pitch: i32) -> bool:
    # return immediately if the outline is empty
    if outline.xs.length == 0 or outline.contour_ends.length == 0:
        return true
    if outline.xs.length != outline.contour_ends[outline.contour_ends.length - 1] + 1:
        return false
    if width <= 0 or rows <= 0:
        return true

    var ras = GrayWorker(min_ex = 0, max_ex = width, min_ey = 0, max_ey = rows, count_ey = rows, cell = gray_null_cell)
    defer ras.release()
    ras.ycells.reserve((usize)rows)
    for _ in 0..<rows:
        ras.ycells.push(gray_null_cell)

    if not ft_outline_decompose(outline, &ras):
        return false
    gray_sweep(&ras, outline.even_odd, buffer, rows, pitch)
    return true