Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-image

Source of release 0.45.1

0.45.1 / src / selection_tests.lucb

## Selection tests: shapes, modes, the wand, cells that share or settle to one
## value, the GPU mirror, and the whole-document oracles that Select › Modify,
## Border, Smooth, warps, Grow and Similar, the wand and channel loads are
## checked against cell by cell. The 15000×24000 timings are
## selection_scale_tests.lucb.
from luce_gpu import gpu
from luce_std import math
from luce_color import transfer
import memory
from luce_canvas.tiles import tile_size
from selection import Selection
from selection_cells import Cells, Mode, block_bytes, each
import selection_shapes as shapes
import selection_sources as sources
from luce_canvas.half import to_half
from projective import affine_warp
from luce_raster.errors import invalid

## Coverage at a pixel, nothing past the document: Selection.at, but 0 where
## nothing is selected.
func covered(selection: const Selection*, x: i64, y: i64) -> u8:
    if x < 0 or y < 0 or x >= (i64)selection.width() or y >= (i64)selection.height():
        return 0
    return selection.coverage().at(x, y)

test "selection shapes combine, invert, grow and feather":
    var selection = try Selection.create(64, 48)
    defer selection.destroy()
    assert(selection.is_empty() and selection.at(5, 5) == 255)
    selection.rectangle(10, 10, 20, 10, Mode.replace)
    assert(not selection.is_empty() and selection.at(15, 15) == 255 and selection.at(5, 5) == 0)
    assert(selection.left == 10 and selection.top == 10 and selection.right == 30 and selection.bottom == 20)
    selection.ellipse(40, 10, 20, 20, Mode.add)
    assert(selection.at(50, 20) == 255 and selection.at(41, 11) == 0 and selection.at(15, 15) == 255)
    selection.rectangle(0, 0, 64, 15, Mode.subtract)
    assert(selection.at(15, 12) == 0 and selection.at(15, 17) == 255)
    selection.rectangle(0, 0, 25, 48, Mode.intersect)
    assert(selection.at(15, 17) == 255 and selection.at(50, 20) == 0)
    selection.invert()
    assert(selection.at(15, 17) == 0 and selection.at(50, 20) == 255)
    try selection.polygon([2.0, 2.0, 12.0, 2.0, 7.0, 12.0], Mode.replace)
    assert(selection.at(7, 5) == 255 and selection.at(2, 10) == 0 and selection.at(20, 20) == 0)
    try selection.adjust(2, 0)
    assert(selection.at(1, 1) == 255 and selection.at(0, 0) == 255)
    try selection.adjust(-2, 3)
    assert(selection.at(7, 5) > 0 and selection.at(7, 5) < 255)
    selection.select_all()
    assert(selection.at(63, 47) == 255)
    selection.clear()
    assert(selection.is_empty())

test "the wand selects like colors, contiguously or not":
    var selection = try Selection.create(8, 4)
    defer selection.destroy()
    # Two red patches split by a blue column; the rest transparent.
    var pixels: f32[8 * 4 * 4]
    for y in 0..<(usize)4:
        for x in 0..<(usize)8:
            let index = (y * 8 + x) * 4
            if x == 4:
                pixels[index + 2] = 1.0
                pixels[index + 3] = 1.0
            elif x < 4 or x > 5:
                pixels[index] = 1.0 if x != 6 else 0.9
                pixels[index + 3] = 1.0
    var buffer = Buffer(pixels = pixels, width = 8, height = 4)
    let reader = buffer.reader()
    try selection.wand(reader, 1, 1, 1, 10.0, true, Mode.replace)
    assert(selection.at(0, 0) == 255 and selection.at(3, 3) == 255 and selection.at(4, 1) == 0 and selection.at(7, 1) == 0 and selection.at(5, 1) == 0)
    try selection.wand(reader, 1, 1, 1, 10.0, false, Mode.replace)
    assert(selection.at(7, 1) == 255 and selection.at(6, 1) == 0)
    try selection.wand(reader, 1, 1, 1, 40.0, false, Mode.replace)
    assert(selection.at(6, 1) == 255 and selection.at(4, 1) == 0)
    var rejected = false
    selection.wand(reader, 9, 0, 1, 10.0, true, Mode.replace) catch failure:
        assert(failure.code == invalid)
        rejected = true
    assert(rejected)

test "a copy shares its cells until one of them changes, and each keeps what it had":
    var first = try Selection.create(600, 600)
    first.rectangle(0, 0, 300, 300, Mode.replace)
    var second = try first.copy()
    # The whole cell is one value; the cut one is a block both hold.
    assert(first.coverage().uniform(0) == 255 and first.coverage().block(1) == second.coverage().block(1))
    assert((first.coverage().block(1) else trap("a block")).references == 2)
    # Changing the first leaves the copy as it was.
    first.rectangle(260, 0, 100, 100, Mode.add)
    assert(first.coverage().block(1) != second.coverage().block(1) and first.at(320, 50) == 255 and second.at(320, 50) == 0 and second.at(10, 10) == 255)
    var third = try second.copy()
    third.invert()
    assert(second.at(10, 10) == 255 and third.at(10, 10) == 0 and third.at(400, 400) == 255)
    first.destroy()
    second.destroy()
    third.destroy()

test "cells one value throughout hold no bytes, and settle back to one value":
    var selection = try Selection.create(512, 512)
    defer selection.destroy()
    selection.rectangle(0, 0, 100, 256, Mode.replace)
    assert(selection.coverage().uniform(0) == -1)
    selection.rectangle(100, 0, 156, 256, Mode.add)
    assert(selection.coverage().uniform(0) == 255 and selection.coverage().uniform(1) == 0)
    selection.rectangle(0, 0, 256, 256, Mode.subtract)
    assert(selection.is_empty() and selection.coverage().uniform(0) == 0)
    # A polygon covering a cell wholly leaves it one value too.
    try selection.polygon([-10.0, -10.0, 300.0, -10.0, 300.0, 300.0, -10.0, 300.0], Mode.replace)
    assert(selection.coverage().uniform(0) == 255 and selection.coverage().uniform(1) == -1)

test "a rectangle holds bytes only in the cells along its edge":
    var selection = try Selection.create(2000, 1000)
    defer selection.destroy()
    selection.rectangle(100, 200, 1500, 600, Mode.replace)
    var blocks = 0
    var full = 0
    for index in 0..<selection.coverage().count():
        if selection.coverage().uniform(index) == -1:
            blocks += 1
        elif selection.coverage().uniform(index) == 255:
            full += 1
    assert(blocks == 18 and full == 10)
    assert(selection.left == 100 and selection.top == 200 and selection.right == 1600 and selection.bottom == 800)
    # An ellipse's middle is one value too.
    selection.ellipse(0, 0, 2000, 1000, Mode.replace)
    assert(selection.coverage().uniform(1 * 8 + 3) == 255 and selection.at(1000, 500) == 255 and selection.at(2, 2) == 0)

test "inverting cells of one value flips the value and makes no bytes":
    var selection = try Selection.create(700, 600)
    defer selection.destroy()
    selection.select_all()
    selection.invert()
    assert(selection.is_empty())
    for index in 0..<selection.coverage().count():
        assert(selection.coverage().uniform(index) == 0)
    selection.rectangle(256, 256, 256, 256, Mode.replace)
    selection.invert()
    assert(selection.coverage().uniform(4) == 0 and selection.coverage().uniform(0) == 255 and selection.coverage().uniform(8) == 255)
    assert(selection.at(300, 300) == 0 and selection.at(10, 10) == 255 and selection.at(699, 599) == 255)
    # Moving by whole cells shares the cells; by less copies the edge.
    try selection.translate(256, 0)
    assert(selection.at(300, 300) == 255 and selection.at(600, 300) == 0 and selection.at(10, 10) == 0)
    try selection.translate(-10, 5)
    assert(selection.at(590, 305) == 0 and selection.at(500, 305) == 255 and selection.at(250, 4) == 0 and selection.at(250, 5) == 255)

test "rectangles fill whole rows in every mode, and a big selection finds its box in bands":
    # Over a million pixels, so the bounds are found on several threads.
    var selection = try Selection.create(2000, 1000)
    defer selection.destroy()
    selection.rectangle(100, 200, 500, 300, Mode.replace)
    assert(selection.at(100, 200) == 255 and selection.at(599, 499) == 255 and selection.at(600, 499) == 0 and selection.at(99, 200) == 0)
    assert(selection.left == 100 and selection.top == 200 and selection.right == 600 and selection.bottom == 500)
    selection.rectangle(1500, 900, 1000, 1000, Mode.add)
    assert(selection.at(1999, 999) == 255 and selection.right == 2000 and selection.bottom == 1000)
    selection.rectangle(0, 0, 2000, 400, Mode.subtract)
    assert(selection.at(300, 300) == 0 and selection.at(300, 450) == 255 and selection.top == 400)
    selection.rectangle(200, 400, 200, 50, Mode.intersect)
    assert(selection.at(250, 420) == 255 and selection.at(150, 420) == 0 and selection.at(1600, 950) == 0)
    assert(selection.left == 200 and selection.top == 400 and selection.right == 400 and selection.bottom == 450)
    selection.rectangle(5000, 5000, 10, 10, Mode.intersect)
    assert(selection.is_empty())

test "the GPU tiles follow the cells, uploading only the cells that changed":
    var device = gpu.Device.open() catch failure:
        assert(failure.code == gpu.unavailable)
        return
    defer device.destroy()
    var selection = try Selection.create(600, 300)
    defer selection.destroy()
    selection.rectangle(0, 0, 300, 300, Mode.replace)
    let first = (try selection.gpu_tiles(device)) else trap("something is selected")
    let whole = first.stamp(0, 0)
    let edge = first.stamp(1, 0)
    assert(whole != 0 and edge != 0 and first.stamp(2, 0) == 0 and first.stamp(0, 1) != 0)
    selection.rectangle(520, 0, 50, 50, Mode.add)
    let second = (try selection.gpu_tiles(device)) else trap("something is selected")
    assert(second == first and second.stamp(0, 0) == whole and second.stamp(1, 0) == edge and second.stamp(2, 0) != 0)
    let pixels = try new f32[600 * 300 * 4] --- in memory.heap
    defer free(pixels) in memory.heap
    try second.read(pixels)
    for probe in [(i64)(100 * 600 + 100), 10 * 600 + 310, 10 * 600 + 530, 299 * 600 + 290, 299 * 600 + 5, 60 * 600 + 530]:
        let expected: f32 = 0.0 if probe == 10 * 600 + 310 or probe == 60 * 600 + 530 else 1.0
        assert(pixels[(usize)probe * 4] == expected)
    selection.clear()
    assert((try selection.gpu_tiles(device)) == none)

# mark: Select › Modify against the whole-document passes ======================================

## Tests' oracle: one separable pass of a max (grow) or min (shrink) filter
## over a whole document's `coverage`, as Select › Modify once ran.
func morph(coverage: u8[], scratch: u8[], w: usize, h: usize, radius: usize, grow: bool, horizontal: bool):
    for y in 0..<h:
        for x in 0..<w:
            var value: u8 = 0 if grow else 255
            let span = (i64)radius
            for offset in -span..<(span + 1):
                let sx = (i64)x + (offset if horizontal else 0)
                let sy = (i64)y + (0 if horizontal else offset)
                var sample: u8 = 0
                if sx >= 0 and sy >= 0 and sx < (i64)w and sy < (i64)h:
                    sample = coverage[(usize)sy * w + (usize)sx]
                if grow:
                    if sample > value:
                        value = sample
                elif sample < value:
                    value = sample
            scratch[y * w + x] = value
    memory.copy(coverage, scratch, coverage.length)

## Tests' oracle: one separable pass of a box blur of `radius`.
func soften(coverage: u8[], scratch: u8[], w: usize, h: usize, radius: usize, horizontal: bool):
    let span = (i64)radius
    for y in 0..<h:
        for x in 0..<w:
            var total: i64 = 0
            var count: i64 = 0
            for offset in -span..<(span + 1):
                let sx = (i64)x + (offset if horizontal else 0)
                let sy = (i64)y + (0 if horizontal else offset)
                if sx >= 0 and sy >= 0 and sx < (i64)w and sy < (i64)h:
                    total += (i64)coverage[(usize)sy * w + (usize)sx]
                count += 1
            scratch[y * w + x] = (u8)(total // count)
    memory.copy(coverage, scratch, coverage.length)

## Tests' oracle: Select › Modify on a whole document's bytes.
func dense_adjust(coverage: u8[], w: usize, h: usize, pixels: i64, feather: i64):
    let scratch = new u8[coverage.length] --- in memory.heap catch failure:
        trap("out of memory in a test")
    defer free(scratch) in memory.heap
    if pixels != 0:
        morph(coverage, scratch, w, h, (usize)math.iabs(pixels), pixels > 0, true)
        morph(coverage, scratch, w, h, (usize)math.iabs(pixels), pixels > 0, false)
    if feather > 0:
        soften(coverage, scratch, w, h, (usize)feather, true)
        soften(coverage, scratch, w, h, (usize)feather, false)

## A selection with edges everywhere: cells wholly selected against the
## document's edges, curves across cells, a corner, a partial last cell.
func busy_selection(width: u32, height: u32) -> Selection!:
    var selection = try Selection.create(width, height)
    selection.rectangle(0, 0, 260, (i64)height, Mode.replace)
    selection.ellipse(300, 60, 250, 330, Mode.add)
    selection.rectangle(40, 200, 90, 60, Mode.subtract)
    try selection.polygon([400.0, 380.0, 590.0, 400.0, 470.0, 515.0, 330.0, 470.0], Mode.add)
    selection.rectangle((i64)width - 20, (i64)height - 20, 20, 20, Mode.add)
    return selection

test "modify matches the whole-document passes, near edges and across cells":
    let width: u32 = 600
    let height: u32 = 520
    let pixels: i64[11] = [1, 7, 40, 270, -1, -7, -40, -270, 0, 0, 12]
    let feathers: i64[11] = [0, 0, 0, 0, 0, 0, 0, 0, 3, 90, 9]
    let dense = try new u8[(usize)width * (usize)height] --- in memory.heap
    defer free(dense) in memory.heap
    for case in 0..<(usize)13:
        var selection = try busy_selection(width, height)
        defer selection.destroy()
        var p = pixels[case] if case < 11 else -15
        var f = feathers[case] if case < 11 else 6
        if case == 12:
            # Everything selected: only the document's edge moves in.
            selection.select_all()
            p = -5
            f = 0
        for y in 0..<(i64)height:
            for x in 0..<(i64)width:
                dense[(usize)y * (usize)width + (usize)x] = covered(&selection, x, y)
        try selection.adjust(p, f)
        dense_adjust(dense, (usize)width, (usize)height, p, f)
        for y in 0..<(i64)height:
            for x in 0..<(i64)width:
                if covered(&selection, x, y) != dense[(usize)y * (usize)width + (usize)x]:
                    trap(f"modify {p}, {f} differs at {x}, {y}: {covered(&selection, x, y)} vs {dense[(usize)y * (usize)width + (usize)x]}")
    # Contracting a selection of whole cells keeps the untouched middle one value.
    var whole = try Selection.create(2048, 2048)
    defer whole.destroy()
    whole.select_all()
    try whole.adjust(-5, 0)
    assert(whole.coverage().uniform(9) == 255 and whole.coverage().uniform(0) == -1 and whole.at(4, 100) == 0 and whole.at(5, 100) == 255)

## Tests' oracle: Border on a whole document's bytes.
func dense_border(coverage: u8[], w: usize, h: usize, width: i64):
    let radius = (usize)((width + 1) // 2)
    let grown = new u8[coverage.length] --- in memory.heap catch failure:
        trap("out of memory in a test")
    defer free(grown) in memory.heap
    let scratch = new u8[coverage.length] --- in memory.heap catch failure:
        trap("out of memory in a test")
    defer free(scratch) in memory.heap
    memory.copy(grown, coverage, coverage.length)
    morph(grown, scratch, w, h, radius, true, true)
    morph(grown, scratch, w, h, radius, true, false)
    morph(coverage, scratch, w, h, radius, false, true)
    morph(coverage, scratch, w, h, radius, false, false)
    for at in 0..<coverage.length:
        coverage[at] = grown[at] - coverage[at] if grown[at] > coverage[at] else 0
    soften(coverage, scratch, w, h, 1, true)
    soften(coverage, scratch, w, h, 1, false)

## Tests' oracle: Smooth on a whole document's bytes.
func dense_smooth(coverage: u8[], w: usize, h: usize, radius: i64):
    let scratch = new u8[coverage.length] --- in memory.heap catch failure:
        trap("out of memory in a test")
    defer free(scratch) in memory.heap
    soften(coverage, scratch, w, h, (usize)radius, true)
    soften(coverage, scratch, w, h, (usize)radius, false)
    for at in 0..<coverage.length:
        coverage[at] = (u8)math.imin(255, math.imax(0, ((i64)coverage[at] - 128) * 4 + 128))

test "a warped selection samples only the cells its edge crosses, and agrees with sampling them all":
    var big = try Selection.create(15000, 24000)
    defer big.destroy()
    big.rectangle(1000, 2000, 9000, 15000, Mode.replace)
    try big.warp(try affine_warp(0.8, 1.1, 0.3, 500.0, -300.0, 5500.0, 9500.0))
    var blocks = 0
    for index in 0..<big.coverage().count():
        if big.coverage().uniform(index) == -1:
            blocks += 1
    # A rotated rectangle's edge crosses a few hundred cells of the 5,568.
    assert(blocks > 50 and blocks < 800 and big.at(5500, 9500) == 255 and big.at(100, 100) == 0)
    # On a small canvas, the settled cells agree with sampling every pixel.
    var small = try busy_selection(600, 520)
    defer small.destroy()
    var sampled = try small.copy()
    defer sampled.destroy()
    let warp = try affine_warp(1.3, 0.9, -0.4, 20.0, 10.0, 300.0, 260.0)
    try small.warp(warp)
    var every = try Cells.create(600, 520)
    defer every.destroy()
    for index in 0..<every.count():
        let shape = try new u8[block_bytes] --- in memory.heap
        defer free(shape) in memory.heap
        memory.set(shape, 0)
        for row in 0..<every.cell_height(index):
            for column in 0..<every.cell_width(index):
                var x = 0.0
                var y = 0.0
                var value = 0.0
                if warp.map((f64)(every.origin_x(index) + column) + 0.5, (f64)(every.origin_y(index) + row) + 0.5, &x, &y):
                    let sx = x - 0.5
                    let sy = y - 0.5
                    let fx0 = (i64)math.floor(sx)
                    let fy0 = (i64)math.floor(sy)
                    let fx = sx - (f64)fx0
                    let fy = sy - (f64)fy0
                    let upper = (f64)covered(&sampled, fx0, fy0) * (1.0 - fx) + (f64)covered(&sampled, fx0 + 1, fy0) * fx
                    let lower = (f64)covered(&sampled, fx0, fy0 + 1) * (1.0 - fx) + (f64)covered(&sampled, fx0 + 1, fy0 + 1) * fx
                    value = upper * (1.0 - fy) + lower * fy
                shape[(usize)row * (usize)tile_size + (usize)column] = (u8)math.clamp(math.round(value), 0.0, 255.0)
        shapes.combine_cell(&every, index, shape, Mode.add)
    for y in 0..<(i64)520:
        for x in 0..<(i64)600:
            if covered(&small, x, y) != every.at(x, y):
                trap(f"warped selection differs at {x}, {y}")

test "border and smooth match the whole-document passes across cells":
    let width: u32 = 600
    let height: u32 = 520
    let dense = try new u8[(usize)width * (usize)height] --- in memory.heap
    defer free(dense) in memory.heap
    let amounts: i64[6] = [1, 4, 25, 3, 10, 60]
    for case in 0..<(usize)7:
        var selection = try busy_selection(width, height)
        defer selection.destroy()
        if case == 6:
            selection.select_all()
        for y in 0..<(i64)height:
            for x in 0..<(i64)width:
                dense[(usize)y * (usize)width + (usize)x] = covered(&selection, x, y)
        let border = case < 3 or case == 6
        let amount = amounts[case] if case < 6 else 8
        if border:
            try selection.border(amount)
            dense_border(dense, (usize)width, (usize)height, amount)
        else:
            try selection.smooth(amount)
            dense_smooth(dense, (usize)width, (usize)height, amount)
        for y in 0..<(i64)height:
            for x in 0..<(i64)width:
                if covered(&selection, x, y) != dense[(usize)y * (usize)width + (usize)x]:
                    trap(f"case {case} differs at {x}, {y}: {covered(&selection, x, y)} vs {dense[(usize)y * (usize)width + (usize)x]}")
    # A whole-cell selection's border holds bytes only along its edge.
    var big = try Selection.create(2048, 2048)
    defer big.destroy()
    big.rectangle(300, 300, 1400, 1400, Mode.replace)
    try big.border(10)
    assert(big.at(300, 1000) > 0 and big.at(1000, 1000) == 0 and big.coverage().uniform(2 * 8 + 2) == 0)

test "grow and similar take the colors the selection covers, near and far":
    let width: usize = 600
    let height: usize = 520
    let pixels = try wand_picture(width, height)
    defer free(pixels) in memory.heap
    var buffer = Buffer(pixels = pixels, width = width, height = height)
    for contiguous in 0..<(usize)2:
        for tolerance in [0.0, 12.0]:
            var selection = try Selection.create((u32)width, (u32)height)
            defer selection.destroy()
            selection.rectangle(20, 300, 30, 20, Mode.replace)
            let before = try selection.copy()
            try selection.grow(buffer.reader(), tolerance, contiguous == 1)
            # Everything selected stays selected, and more is taken.
            for py in 300..<(i64)320:
                for px in 20..<(i64)50:
                    assert(selection.at(px, py) == 255)
            var added = 0
            var far = 0
            for py in 0..<(i64)height:
                for px in 0..<(i64)width:
                    if covered(&selection, px, py) == 255 and covered(&before, px, py) == 0:
                        added += 1
                        # Past the moat at x 300..302 only Similar reaches.
                        if px > 302 and py >= 256:
                            far += 1
            assert(added > 0)
            if contiguous == 1:
                assert(far == 0)
            var copy = before
            copy.destroy()
    # Grow on a selection over the transparent cell takes clear pixels only.
    var clear = try Selection.create((u32)width, (u32)height)
    defer clear.destroy()
    clear.rectangle(300, 10, 20, 20, Mode.replace)
    try clear.grow(buffer.reader(), 0.0, true)
    assert(clear.at(260, 100) == 255 and clear.at(100, 100) == 0 and clear.at(520, 100) == 0)

# mark: Pixels a cell at a time against the whole-document wand ================================

## Tests' pixels, straight-alpha linear RGBA, served a cell at a time as
## half floats; a cell of nothing but zeros reads as transparent, as a layer's
## unpainted cell does.
struct Buffer:
    var pixels: const f32[]
    var width: usize
    var height: usize

    func reader() -> sources.Reader:
        return sources.cpu_reader((void*)&self, read_buffer)

func read_buffer(context: void*?, column: u32, row: u32, halves: u8[]) -> bool!:
    let buffer = (Buffer*)(context else return false)
    let left = (usize)column * (usize)tile_size
    let top = (usize)row * (usize)tile_size
    let width = math.imin((i64)tile_size, (i64)(buffer.width - left))
    let height = math.imin((i64)tile_size, (i64)(buffer.height - top))
    var painted = false
    for y in 0..<(usize)height:
        for x in 0..<(usize)width:
            for channel in 0..<(usize)4:
                let value = buffer.pixels[((top + y) * buffer.width + left + x) * 4 + channel]
                if value != 0.0:
                    painted = true
                let bits = to_half(value)
                let at = (y * (usize)tile_size + x) * 8 + channel * 2
                halves[at] = (u8)(bits & 0xff)
                halves[at + 1] = (u8)(bits >> 8)
    return painted

## Tests' oracle: whether pixel `b` of `bytes` is within `limit` of pixel `a`.
func within(bytes: const u8[], a: usize, b: usize, limit: i64) -> bool:
    for channel in 0..<(usize)4:
        let difference = (i64)bytes[a * 4 + channel] - (i64)bytes[b * 4 + channel]
        if difference > limit or -difference > limit:
            return false
    return true

## Tests' oracle: the magic wand on a whole document's pixels as it once ran,
## the seed pixel first averaged over its `reach`: 255 where matched.
func dense_wand(source: const f32[], width: usize, height: usize, x: i64, y: i64, reach: i64, tolerance: f64, contiguous: bool, matched: u8[]):
    let pixels = new f32[source.length] --- in memory.heap catch failure:
        trap("out of memory in a test")
    defer free(pixels) in memory.heap
    memory.copy(pixels, source, source.length)
    var sum: f64[4] = [0.0, 0.0, 0.0, 0.0]
    var count = 0.0
    for dy in -reach..<(reach + 1):
        for dx in -reach..<(reach + 1):
            let px = x + dx
            let py = y + dy
            if px < 0 or py < 0 or px >= (i64)width or py >= (i64)height:
                continue
            for channel in 0..<(usize)4:
                sum[channel] += (f64)pixels[((usize)py * width + (usize)px) * 4 + channel]
            count += 1.0
    if reach > 0:
        for channel in 0..<(usize)4:
            pixels[((usize)y * width + (usize)x) * 4 + channel] = (f32)(sum[channel] / count)
    let bytes = new u8[width * height * 4] --- in memory.heap catch failure:
        trap("out of memory in a test")
    defer free(bytes) in memory.heap
    for index in 0..<(width * height):
        for channel in 0..<(usize)3:
            bytes[index * 4 + channel] = transfer.srgb_byte((f64)pixels[index * 4 + channel])
        bytes[index * 4 + 3] = (u8)(math.clamp((f64)pixels[index * 4 + 3], 0.0, 1.0) * 255.0 + 0.5)
    let seed = (usize)y * width + (usize)x
    let limit = (i64)math.floor(tolerance + 0.5)
    memory.set(matched, 0)
    if not contiguous:
        for index in 0..<(width * height):
            if within(bytes, seed, index, limit):
                matched[index] = 255
        return
    let queue = new u32[width * height] --- in memory.heap catch failure:
        trap("out of memory in a test")
    defer free(queue) in memory.heap
    var head: usize = 0
    var tail: usize = 1
    queue[0] = (u32)seed
    matched[seed] = 255
    while head < tail:
        let index = (usize)queue[head]
        head += 1
        let column = (i64)(index % width)
        let row = (i64)(index // width)
        for step in 0..<(usize)4:
            let nx = column + (1 if step == 0 else (-1 if step == 1 else 0))
            let ny = row + (1 if step == 2 else (-1 if step == 3 else 0))
            if nx < 0 or ny < 0 or nx >= (i64)width or ny >= (i64)height:
                continue
            let next = (usize)ny * width + (usize)nx
            if matched[next] == 0 and within(bytes, seed, next, limit):
                matched[next] = 255
                queue[tail] = (u32)next
                tail += 1

## A test picture over several cells: bands of close colors that the wand
## tells apart by tolerance, a transparent cell, a moat splitting a region,
## and halves-exact values so the half floats read back unchanged.
func wand_picture(width: usize, height: usize) -> f32[]!:
    let pixels = try new f32[width * height * 4] --- in memory.heap
    memory.set(u8[]((u8*)pixels.data, pixels.length * 4), 0)
    for y in 0..<height:
        for x in 0..<width:
            let at = (y * width + x) * 4
            # The top-right cell stays transparent.
            if x >= 256 and x < 512 and y < 256:
                continue
            let band = (x // 37 + y // 53) % 5
            pixels[at] = (f32)(band * 8 + 64) / 256.0
            pixels[at + 1] = (f32)((x * 7 + y * 3) % 16 + 100) / 256.0
            pixels[at + 2] = 0.5 if band != 3 else 0.25
            pixels[at + 3] = 1.0 if (x + y) % 97 != 0 else 0.5
            # A moat of pure blue down x = 300 below the first row of cells.
            if x >= 300 and x < 303 and y >= 256:
                pixels[at] = 0.0
                pixels[at + 1] = 0.0
                pixels[at + 2] = 1.0
    return pixels

test "the wand read a cell at a time matches the whole-document wand":
    let width: usize = 600
    let height: usize = 520
    let pixels = try wand_picture(width, height)
    defer free(pixels) in memory.heap
    let matched = try new u8[width * height] --- in memory.heap
    defer free(matched) in memory.heap
    var buffer = Buffer(pixels = pixels, width = width, height = height)
    let seeds: i64[10] = [10, 10, 255, 255, 256, 256, 599, 519, 400, 100]
    let tolerances: f64[4] = [0.0, 6.0, 20.0, 255.0]
    let samples: i64[3] = [1, 3, 5]
    for seed in 0..<(usize)5:
        for tolerance in tolerances:
            for sample in samples:
                for contiguous in 0..<(usize)2:
                    let x = seeds[seed * 2]
                    let y = seeds[seed * 2 + 1]
                    var selection = try Selection.create((u32)width, (u32)height)
                    defer selection.destroy()
                    try selection.wand(buffer.reader(), x, y, sample, tolerance, contiguous == 1, Mode.replace)
                    dense_wand(pixels, width, height, x, y, sample // 2, tolerance, contiguous == 1, matched)
                    for py in 0..<(i64)height:
                        for px in 0..<(i64)width:
                            if covered(&selection, px, py) != matched[(usize)py * width + (usize)px]:
                                trap(f"wand at {x}, {y}, tolerance {tolerance}, sample {sample}, contiguous {contiguous}: differs at {px}, {py}")

test "loading a channel a cell at a time matches the samples, transparent cells blank":
    let width: usize = 600
    let height: usize = 520
    let pixels = try wand_picture(width, height)
    defer free(pixels) in memory.heap
    var buffer = Buffer(pixels = pixels, width = width, height = height)
    for blank in 0..<(usize)2:
        var selection = try Selection.create((u32)width, (u32)height)
        defer selection.destroy()
        selection.rectangle(0, 0, 50, 50, Mode.replace)
        try selection.load(buffer.reader(), 3, 255 if blank == 1 else 0, Mode.add)
        for py in 0..<(i64)height:
            for px in 0..<(i64)width:
                let transparent = px >= 256 and px < 512 and py < 256
                var expected = (u8)(math.clamp((f64)pixels[((usize)py * width + (usize)px) * 4 + 3], 0.0, 1.0) * 255.0 + 0.5)
                if transparent:
                    expected = 255 if blank == 1 else 0
                if px < 50 and py < 50:
                    expected = 255
                if covered(&selection, px, py) != expected:
                    trap(f"load differs at {px}, {py}")