Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.1

0.6.1 / src / raster / analytic_edge.lucb

#==============================================================================================
#
#   analytic_edge - the edges of the analytic anti-aliasing scan converter
#
#   DESCRIPTION:
#       Port of Skia m144 src/core/SkAnalyticEdge.h/.cpp: SkAnalyticEdge and its quadratic
#       and cubic subclasses, which walk a path segment as a sequence of lines in SkFixed
#       with y snapped to 1/4 pixel (kDefaultAccuracy), quick_inverse/quick_div and the
#       SkFixed helpers of SkFixed.h the AAA code uses. The three classes are one struct
#       (the `Type` the edge was built as is `edge_type`); Skia's fNext/fPrev pointers are
#       indices into the edge list (edge_nil for none), see scan_aaa_path.lucb.
#
#       Copyright (c) 2006 The Android Open Source Project
#       Copyright (c) 2026 the luce-browser authors.
#       SPDX-License-Identifier: BSD-3-Clause (see LICENSE-skia)
#
#==============================================================================================

# mark: SkFixed ===============================================================================
# Skia's macros wrap on overflow (it computes them on sentinels such as SK_MaxS32), so these
# use the wrapping operators.

let fixed_one: i32 = 65536
let fixed_half: i32 = 32768
let fixed_max: i32 = 2147483647
let fixed_min: i32 = -2147483648

## SkIntToFixed.
func int_to_fixed(n: i32) -> i32:
    return (i32)((u32)n << 16)

## SkFixedFloorToInt.
func fixed_floor_to_int(x: i32) -> i32:
    return x >> 16

## SkFixedCeilToInt.
func fixed_ceil_to_int(x: i32) -> i32:
    return (x +% (fixed_one - 1)) >> 16

## SkFixedRoundToInt.
func fixed_round_to_int(x: i32) -> i32:
    return (x +% fixed_half) >> 16

## SkFixedFloorToFixed.
func fixed_floor_to_fixed(x: i32) -> i32:
    return (i32)((u32)x & 0xFFFF0000)

## SkFixedCeilToFixed.
func fixed_ceil_to_fixed(x: i32) -> i32:
    return (i32)((u32)(x +% (fixed_one - 1)) & 0xFFFF0000)

## SkFixedRoundToFixed.
func fixed_round_to_fixed(x: i32) -> i32:
    return (i32)((u32)(x +% fixed_half) & 0xFFFF0000)

## SkFixedMul.
func fixed_mul(a: i32, b: i32) -> i32:
    return (i32)(((i64)a * (i64)b) >> 16)

## SkFixedToFDot6.
func fixed_to_fdot6(x: i32) -> i32:
    return x >> 10

## Sk32_sat_add.
func sat_add32(a: i32, b: i32) -> i32:
    return (i32)bound_i64((i64)i32_min, (i64)a + (i64)b, (i64)i32_max)

## Sk32_sat_sub.
func sat_sub32(a: i32, b: i32) -> i32:
    return (i32)bound_i64((i64)i32_min, (i64)a - (i64)b, (i64)i32_max)

## SkAbs32.
func abs32(x: i32) -> i32:
    return -%x if x < 0 else x

# mark: quick_div =============================================================================

func quick_inverse(x: i32) -> i32:
    if x > 0:
        return -quick_inverse_table[(usize)(inverse_table_size - x)]
    return quick_inverse_table[(usize)(inverse_table_size + x)]

func quick_div(a: i32, b: i32) -> i32:
    let min_bits: i32 = 3  # abs(b) should be at least (1 << min_bits) for quick division
    let max_bits: i32 = 31  # Number of bits available in signed int
    # Given abs(b) <= (1 << min_bits), the inverse of abs(b) is at most 1 << (22 - min_bits)
    # in SkFixed format. Hence abs(a) should be less than max_abs_a
    let max_abs_a: i32 = 1 << (max_bits - (22 - min_bits))
    let abs_a = abs32(a)
    let abs_b = abs32(b)
    if abs_b >= (1 << min_bits) and abs_b < inverse_table_size and abs_a < max_abs_a:
        return (a * quick_inverse(b)) >> 6
    return fdot6_div(a, b)

# mark: SkAnalyticEdge ========================================================================

## The index of no edge (Skia's nullptr).
let edge_nil: u32 = 0xFFFFFFFF

## The default accuracy for snapping: y is snapped to 1/4 pixel.
let analytic_default_accuracy: i32 = 2

## The type an analytic edge was built as.
enum AnalyticEdgeType as u8:
    line = 0
    quad = 1
    cubic = 2

## SkAnalyticEdge with the fields of SkAnalyticQuadraticEdge and SkAnalyticCubicEdge.
struct AnalyticEdge:
    var next: u32
    var prev: u32

    var x: i32
    var dx: i32
    ## The x value when y = upper_y.
    var upper_x: i32
    ## The current y.
    var y: i32
    ## The upper bound of y (our edge is from y = upper_y to y = lower_y).
    var upper_y: i32
    ## The lower bound of y.
    var lower_y: i32
    ## abs(1/dx); may be fixed_max when dx is close to 0. Only used for trapezoids.
    var dy: i32

    ## Remembers the *initial* edge type.
    var edge_type: AnalyticEdgeType
    ## Only used by quads (+) and cubics (-).
    var curve_count: i32
    ## Applied to all Dx/DDx/DDDx except for cubic_dshift.
    var curve_shift: i32
    ## 1 (clockwise) or -1.
    var winding: i32

    # SkAnalyticQuadraticEdge
    var qx: i32
    var qy: i32
    var qdx: i32
    var qdy: i32
    var qddx: i32
    var qddy: i32
    var qlast_x: i32
    var qlast_y: i32
    # snap y to integer points in the middle of the curve to accelerate AAA path filling
    var snapped_x: i32
    ## Also SkAnalyticCubicEdge's fSnappedY: make sure that y is increasing with smooth jump
    ## and snapping.
    var snapped_y: i32

    # SkAnalyticCubicEdge
    var cx: i32
    var cy: i32
    var cdx: i32
    var cdy: i32
    var cddx: i32
    var cddy: i32
    var cdddx: i32
    var cdddy: i32
    var clast_x: i32
    var clast_y: i32
    ## Applied to cdx and cdy.
    var cubic_dshift: i32

    static func snap_y(y: i32) -> i32:
        let accuracy = analytic_default_accuracy
        # This approach is safer than left shift, round, then right shift
        return (i32)((((u32)y +% (u32)(fixed_one >> (accuracy + 1))) >> (u32)(16 - accuracy)) << (u32)(16 - accuracy))

    ## Update x, y of this edge so y = new_y.
    func go_y(new_y: i32):
        if new_y == self.y +% fixed_one:
            self.x = self.x + self.dx
            self.y = new_y
        elif new_y != self.y:
            # Drop lower digits as our alpha only has 8 bits (dx and y - upper_y may be
            # greater than SK_Fixed1)
            self.x = self.upper_x + fixed_mul(self.dx, new_y - self.upper_y)
            self.y = new_y

    func go_y_shift(new_y: i32, y_shift: i32):
        self.y = new_y
        self.x += self.dx >> y_shift

    ## SkAnalyticEdge::setLine.
    func set_line(p0: Point, p1: Point) -> bool:
        # We must set X/Y using the same way (e.g., times 4, to FDot6, then to Fixed) as
        # Quads/Cubics. Otherwise the order of the edge might be wrong due to precision
        # limit.
        let accuracy = analytic_default_accuracy
        let multiplier = (f32)(1 << accuracy)
        var x0 = fdot6_to_fdot16(fdot6_from_f32(p0.x * multiplier)) >> accuracy
        var y0 = AnalyticEdge.snap_y(fdot6_to_fdot16(fdot6_from_f32(p0.y * multiplier)) >> accuracy)
        var x1 = fdot6_to_fdot16(fdot6_from_f32(p1.x * multiplier)) >> accuracy
        var y1 = AnalyticEdge.snap_y(fdot6_to_fdot16(fdot6_from_f32(p1.y * multiplier)) >> accuracy)

        var winding: i32 = 1

        if y0 > y1:
            let tx = x0
            x0 = x1
            x1 = tx
            let ty = y0
            y0 = y1
            y1 = ty
            winding = -1

        # are we a zero-height line?
        let dy = fixed_to_fdot6(y1 - y0)
        if dy == 0:
            return false
        let dx = fixed_to_fdot6(x1 - x0)
        let slope = quick_div(dx, dy)
        let abs_slope = abs32(slope)

        self.x = x0
        self.dx = slope
        self.upper_x = x0
        self.y = y0
        self.upper_y = y0
        self.lower_y = y1
        if dx == 0 or slope == 0:
            self.dy = fixed_max
        elif abs_slope < inverse_table_size:
            self.dy = quick_inverse(abs_slope)
        else:
            self.dy = abs32(quick_div(dy, dx))
        self.edge_type = .line
        self.curve_count = 0
        self.winding = winding
        self.curve_shift = 0

        return true

    ## SkAnalyticEdge::updateLine. The slope is computed by the caller: calling SkFixedDiv
    ## twice here would be a bottleneck for small ovals.
    func update_line(x00: i32, y00: i32, x10: i32, y10: i32, slope: i32) -> bool:
        var x0 = x00
        var y0 = y00
        var x1 = x10
        var y1 = y10
        # We don't chop at y extrema for cubics so the y is not guaranteed to be increasing
        # for them. In that case, we have to swap x/y and negate the winding.
        if y0 > y1:
            let tx = x0
            x0 = x1
            x1 = tx
            let ty = y0
            y0 = y1
            y1 = ty
            self.winding = -self.winding

        let dx = fixed_to_fdot6(x1 - x0)
        let dy = fixed_to_fdot6(y1 - y0)

        # are we a zero-height line?
        if dy == 0:
            return false

        let abs_slope = abs32(fixed_to_fdot6(slope))
        self.x = x0
        self.dx = slope
        self.upper_x = x0
        self.y = y0
        self.upper_y = y0
        self.lower_y = y1
        if dx == 0 or slope == 0:
            self.dy = fixed_max
        elif abs_slope < inverse_table_size:
            self.dy = quick_inverse(abs_slope)
        else:
            self.dy = abs32(quick_div(dy, dx))

        return true

    ## Returns true if we're NOT done with this edge.
    func update(last_y: i32) -> bool:
        if self.curve_count < 0:
            return self.update_cubic()
        elif self.curve_count > 0:
            return self.update_quadratic()
        return false

    # mark: SkAnalyticQuadraticEdge ===============================================================

    func set_quadratic_without_update(pts: const Point[], shift0: i32) -> bool:
        let scale = (f32)(1 << (shift0 + 6))
        var x0 = (i32)(pts[0].x * scale)
        var y0 = (i32)(pts[0].y * scale)
        let x1 = (i32)(pts[1].x * scale)
        let y1 = (i32)(pts[1].y * scale)
        var x2 = (i32)(pts[2].x * scale)
        var y2 = (i32)(pts[2].y * scale)

        var winding: i32 = 1
        if y0 > y2:
            let tx = x0
            x0 = x2
            x2 = tx
            let ty = y0
            y0 = y2
            y2 = ty
            winding = -1

        let top = fdot6_round(y0)
        let bot = fdot6_round(y2)

        # are we a zero-height quad (line)?
        if top == bot:
            return false

        # compute number of steps needed (1 << shift)
        let ddx = (left_shift(x1, 1) - x0 - x2) >> 2
        let ddy = (left_shift(y1, 1) - y0 - y2) >> 2
        # This is a little confusing: before this line, shift is the scale up factor for AA;
        # after this line, shift is the fCurveShift.
        var shift = diff_to_shift(ddx, ddy, shift0)
        # need at least 1 subdivision for our bias trick
        if shift == 0:
            shift = 1
        elif shift > max_coeff_shift:
            shift = max_coeff_shift

        self.winding = winding
        self.edge_type = .quad
        self.curve_count = 1 << shift

        # We want to reformulate into polynomial form, to make it clear how we should
        # forward-difference.
        #
        #   p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
        #
        #   A = p0 - 2p1 + p2
        #   B = 2(p1 - p0)
        #   C = p0
        #
        # Our caller must have constrained our inputs (p0..p2) to all fit into 16.16.
        # However, as seen above, we sometimes compute values that can be larger (e.g.
        # B = 2*(p1 - p0)). To guard against overflow, we will store A and B at 1/2 of their
        # actual value, and just apply a 2x scale during application in updateQuadratic().
        # Hence we store (shift - 1) in fCurveShift.
        self.curve_shift = shift - 1

        var a = fdot6_to_fixed_div2(x0 - x1 - x1 + x2)  # 1/2 the real value
        var b = fdot6_to_fdot16(x1 - x0)  # 1/2 the real value

        self.qx = fdot6_to_fdot16(x0)
        self.qdx = b + (a >> shift)  # biased by shift
        self.qddx = a >> (shift - 1)  # biased by shift

        a = fdot6_to_fixed_div2(y0 - y1 - y1 + y2)  # 1/2 the real value
        b = fdot6_to_fdot16(y1 - y0)  # 1/2 the real value

        self.qy = fdot6_to_fdot16(y0)
        self.qdy = b + (a >> shift)  # biased by shift
        self.qddy = a >> (shift - 1)  # biased by shift

        self.qlast_x = fdot6_to_fdot16(x2)
        self.qlast_y = fdot6_to_fdot16(y2)

        return true

    ## SkAnalyticQuadraticEdge::setQuadratic.
    func set_quadratic(pts: const Point[]) -> bool:
        if not self.set_quadratic_without_update(pts, analytic_default_accuracy):
            return false
        let acc = analytic_default_accuracy
        self.qx >>= acc
        self.qy >>= acc
        self.qdx >>= acc
        self.qdy >>= acc
        self.qddx >>= acc
        self.qddy >>= acc
        self.qlast_x >>= acc
        self.qlast_y >>= acc
        self.qy = AnalyticEdge.snap_y(self.qy)
        self.qlast_y = AnalyticEdge.snap_y(self.qlast_y)

        self.edge_type = .quad

        self.snapped_x = self.qx
        self.snapped_y = self.qy

        return self.update_quadratic()

    ## SkAnalyticQuadraticEdge::updateQuadratic.
    func update_quadratic() -> bool:
        var success = false  # initialize to fail!
        var count = self.curve_count
        var oldx = self.qx
        var oldy = self.qy
        var dx = self.qdx
        var dy = self.qdy
        var newx: i32 = 0
        var newy: i32 = 0
        var new_snapped_x: i32 = 0
        var new_snapped_y: i32 = 0
        let shift = self.curve_shift

        while true:
            var slope: i32 = 0
            count -= 1
            if count > 0:
                newx = oldx + (dx >> shift)
                newy = oldy + (dy >> shift)
                # only snap when dy is large enough and dx/dy isn't too large
                if abs32(dy >> shift) >= fixed_one * 2 and ((i64)abs32(dy) << 6) > (i64)abs32(dx):
                    let diff_y = fixed_to_fdot6(newy - self.snapped_y)
                    slope = quick_div(fixed_to_fdot6(newx - self.snapped_x), diff_y) if diff_y != 0 else fixed_max
                    let rounded = fixed_round_to_fixed(newy)
                    new_snapped_y = self.qlast_y if self.qlast_y < rounded else rounded
                    new_snapped_x = newx - fixed_mul(slope, newy - new_snapped_y)
                else:
                    let snapped = AnalyticEdge.snap_y(newy)
                    new_snapped_y = self.qlast_y if self.qlast_y < snapped else snapped
                    new_snapped_x = newx
                    let diff_y = fixed_to_fdot6(new_snapped_y - self.snapped_y)
                    slope = quick_div(fixed_to_fdot6(newx - self.snapped_x), diff_y) if diff_y != 0 else fixed_max
                dx += self.qddx
                dy += self.qddy
            # last segment
            else:
                newx = self.qlast_x
                newy = self.qlast_y
                new_snapped_y = newy
                new_snapped_x = newx
                let diff_y = fixed_to_fdot6(newy - self.snapped_y)
                slope = quick_div(fixed_to_fdot6(newx - self.snapped_x), diff_y) if diff_y != 0 else fixed_max
            if slope < fixed_max:
                success = self.update_line(self.snapped_x, self.snapped_y, new_snapped_x, new_snapped_y, slope)
            oldx = newx
            oldy = newy
            if not (count > 0 and not success):
                break

        self.qx = newx
        self.qy = newy
        self.qdx = dx
        self.qdy = dy
        self.snapped_x = new_snapped_x
        self.snapped_y = new_snapped_y
        self.curve_count = count
        return success

    ## SkAnalyticQuadraticEdge::keepContinuous: we use x as the starting x to ensure the
    ## continuity. Without it, we may break the sorted edge list.
    func keep_continuous_quad():
        self.snapped_x = self.x
        self.snapped_y = self.y

    # mark: SkAnalyticCubicEdge ===================================================================

    ## SkAnalyticCubicEdge::setCubic.
    func set_cubic(pts: const Point[]) -> bool:
        if not self.set_cubic_without_update(pts, analytic_default_accuracy):
            return false

        let acc = analytic_default_accuracy
        self.cx >>= acc
        self.cy >>= acc
        self.cdx >>= acc
        self.cdy >>= acc
        self.cddx >>= acc
        self.cddy >>= acc
        self.cdddx >>= acc
        self.cdddy >>= acc
        self.clast_x >>= acc
        self.clast_y >>= acc
        self.cy = AnalyticEdge.snap_y(self.cy)
        self.snapped_y = self.cy
        self.clast_y = AnalyticEdge.snap_y(self.clast_y)

        self.edge_type = .cubic

        return self.update_cubic()

    func set_cubic_without_update(pts: const Point[], shift0: i32) -> bool:
        let scale = (f32)(1 << (shift0 + 6))
        var x0 = (i32)(pts[0].x * scale)
        var y0 = (i32)(pts[0].y * scale)
        var x1 = (i32)(pts[1].x * scale)
        var y1 = (i32)(pts[1].y * scale)
        var x2 = (i32)(pts[2].x * scale)
        var y2 = (i32)(pts[2].y * scale)
        var x3 = (i32)(pts[3].x * scale)
        var y3 = (i32)(pts[3].y * scale)

        var winding: i32 = 1
        if y0 > y3:
            var t = x0
            x0 = x3
            x3 = t
            t = x1
            x1 = x2
            x2 = t
            t = y0
            y0 = y3
            y3 = t
            t = y1
            y1 = y2
            y2 = t
            winding = -1

        let top = fdot6_round(y0)
        let bot = fdot6_round(y3)

        # are we a zero-height cubic (line)?
        if top == bot:
            return false

        # compute number of steps needed (1 << shift)
        # Can't use (center of curve - center of baseline), since center-of-curve need not
        # be the max delta from the baseline (it could even be coincident) so we try just
        # looking at the two off-curve points
        let ddx = cubic_delta_from_line(x0, x1, x2, x3)
        let ddy = cubic_delta_from_line(y0, y1, y2, y3)
        # add 1 (by observation)
        var shift = diff_to_shift(ddx, ddy, 2) + 1
        # need at least 1 subdivision for our bias trick
        if shift > max_coeff_shift:
            shift = max_coeff_shift

        # Since our in coming data is initially shifted down by 10 (or 8 in antialias). That
        # means the most we can shift up is 8. However, we compute coefficients with a 3*,
        # so the safest upshift is really 6
        var up_shift: i32 = 6  # largest safe value
        var down_shift = shift + up_shift - 10
        if down_shift < 0:
            down_shift = 0
            up_shift = 10 - shift

        self.winding = winding
        self.edge_type = .cubic
        self.curve_count = left_shift(-1, shift)
        self.curve_shift = shift
        self.cubic_dshift = down_shift

        var b = fdot6_up_shift(3 * (x1 - x0), up_shift)
        var c = fdot6_up_shift(3 * (x0 - x1 - x1 + x2), up_shift)
        var d = fdot6_up_shift(x3 + 3 * (x1 - x2) - x0, up_shift)

        self.cx = fdot6_to_fdot16(x0)
        self.cdx = b + (c >> shift) + (d >> (2 * shift))  # biased by shift
        self.cddx = 2 * c + ((3 * d) >> (shift - 1))  # biased by 2*shift
        self.cdddx = (3 * d) >> (shift - 1)  # biased by 2*shift

        b = fdot6_up_shift(3 * (y1 - y0), up_shift)
        c = fdot6_up_shift(3 * (y0 - y1 - y1 + y2), up_shift)
        d = fdot6_up_shift(y3 + 3 * (y1 - y2) - y0, up_shift)

        self.cy = fdot6_to_fdot16(y0)
        self.cdy = b + (c >> shift) + (d >> (2 * shift))  # biased by shift
        self.cddy = 2 * c + ((3 * d) >> (shift - 1))  # biased by 2*shift
        self.cdddy = (3 * d) >> (shift - 1)  # biased by 2*shift

        self.clast_x = fdot6_to_fdot16(x3)
        self.clast_y = fdot6_to_fdot16(y3)

        return true

    ## SkAnalyticCubicEdge::updateCubic.
    func update_cubic() -> bool:
        var success = false
        var count = self.curve_count
        var oldx = self.cx
        var oldy = self.cy
        var newx: i32 = 0
        var newy: i32 = 0
        let ddshift = self.curve_shift
        let dshift = self.cubic_dshift

        while true:
            count += 1
            if count < 0:
                newx = oldx + (self.cdx >> dshift)
                self.cdx += self.cddx >> ddshift
                self.cddx += self.cdddx

                newy = oldy + (self.cdy >> dshift)
                self.cdy += self.cddy >> ddshift
                self.cddy += self.cdddy
            # last segment
            else:
                newx = self.clast_x
                newy = self.clast_y

            # we want to say SkASSERT(oldy <= newy), but our finite fixedpoint doesn't
            # always achieve that, so we have to explicitly pin it here.
            if newy < oldy:
                newy = oldy

            var new_snapped_y = AnalyticEdge.snap_y(newy)
            # we want to SkASSERT(snappedNewY <= fCLastY), but our finite fixedpoint doesn't
            # always achieve that, so we have to explicitly pin it here.
            if self.clast_y < new_snapped_y:
                new_snapped_y = self.clast_y
                count = 0

            var slope = fixed_max
            if fixed_to_fdot6(new_snapped_y - self.snapped_y) != 0:
                slope = fdot6_div(fixed_to_fdot6(newx - oldx), fixed_to_fdot6(new_snapped_y - self.snapped_y))

            success = self.update_line(oldx, self.snapped_y, newx, new_snapped_y, slope)

            oldx = newx
            oldy = newy
            self.snapped_y = new_snapped_y
            if not (count < 0 and not success):
                break

        self.cx = newx
        self.cy = newy
        self.curve_count = count
        return success

    ## SkAnalyticCubicEdge::keepContinuous.
    func keep_continuous_cubic():
        self.cx = self.x
        self.snapped_y = self.y