Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-image

Source of release 0.45.0

0.45.0 / src / selection_sources.lucb

## Selections made from pixels read a cell at a time: a layer's transparency
## (or mask) loaded as the selection, and the magic wand. Nothing the size of
## the document is ever held. The pixels come through a `Reader` (a layer's
## tiles, the composited picture, or a test's buffer) as straight-alpha RGBA
## half floats. GPU sources are read 64 cells to a read batch on the calling
## thread (the GPU's), two batches in turn: while every processor turns one
## batch into coverage straight from the readback memory, the next is already
## on the GPU. Half floats have 65536 values, so
## each conversion is a table lookup.
##
## The wand's matching pixels become a selection of their own (`near`), cells
## wholly matching or wholly not costing nothing; a contiguous wand then
## floods through it from the seed, a cell that matches wholly being taken at
## once and only mixed cells being walked pixel by pixel.
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 luce_canvas.half import from_half
from selection_cells import Cells, Mode, block_bytes, each
from selection_shapes import combine_cell, combine_value
from luce_raster.errors import invalid

## Bytes of one cell's pixels as half floats, rows of 256.
let cell_halves: usize = 524288

## Cells read before they are converted together.
let batch_cells: usize = 32

## Where pixels come from, a cell at a time (`cpu_reader`, `gpu_reader`).
## A CPU source's `read(context, column, row, halves)` fills `halves` (rows of
## 256 pixels, 8 bytes each, as many rows as the cell has) and is true, or is
## false for a cell wholly transparent and leaves `halves` alone. A GPU
## source's `texture(context, column, row)` is the cell's tile (256 wide,
## rgba16f) or none where it is transparent; its cells are read in batches.
pub struct Reader:
    pub var context: void*?
    pub var read: func(void*?, u32, u32, u8[]) -> bool!
    pub var texture: func(void*?, u32, u32) -> gpu.Texture?!
    pub var device: gpu.Device
    pub var batched: bool

## A reader of pixels the CPU already has.
pub func cpu_reader(context: void*?, read: func(void*?, u32, u32, u8[]) -> bool!) -> Reader:
    return Reader(context = context, read = read, texture = no_texture, device = gpu.Device(), batched = false)

## A reader of tiles on `device`, read back in batches.
pub func gpu_reader(context: void*?, device: gpu.Device, texture: func(void*?, u32, u32) -> gpu.Texture?!) -> Reader:
    return Reader(context = context, read = no_read, texture = texture, device = device, batched = true)

func no_texture(context: void*?, column: u32, row: u32) -> gpu.Texture?!:
    _ = context
    _ = column
    _ = row
    return none

func no_read(context: void*?, column: u32, row: u32, halves: u8[]) -> bool!:
    _ = context
    _ = column
    _ = row
    _ = halves
    return false

## One cell through `reader` into `halves`: whether it is painted.
func read_one(cells: const Cells*, reader: Reader, column: u32, row: u32, halves: u8[]) -> bool!:
    if not reader.batched:
        return try reader.read(reader.context, column, row, halves)
    let texture = (try reader.texture(reader.context, column, row)) else return false
    let rows = min_u32(tile_size, cells.extent_y - row * tile_size)
    try texture.read(halves[..<(usize)rows * (usize)tile_size * 8], gpu.Region(0, 0, tile_size, rows))
    return true

func min_u32(a: u32, b: u32) -> u32:
    return a if a < b else b

# mark: Loading =================================================================================

## Channel `channel` of every pixel as coverage, combined into `cells` by
## `mode`; a transparent cell's coverage is `blank` (a mask never painted
## shows everything).
pub func load(cells: Cells*, reader: Reader, channel: usize, blank: u8, mode: Mode) -> !:
    if channel > 3:
        error(invalid, "a pixel has four channels")
    let table = try new u8[65536] --- in memory.heap
    defer free(table) in memory.heap
    for bits in 0..<(usize)65536:
        table[bits] = coverage_byte(from_half((u16)bits))
    var no_indices: usize[]
    var no_halves: u8[]
    var no_ranges: u8[]
    var no_ranged: bool[]
    var job = CellJob(cells = cells, table = table, channel = channel, mode = mode, low = [0, 0, 0, 0], high = [0, 0, 0, 0], limit = 0, only = none,
                      ranges = no_ranges, ranged = no_ranged, indices = no_indices, halves = no_halves)
    try read_batches(cells, reader, &job, load_item, blank)

## Coverage for cell `job.indices[item]` from its halves.
func load_item(context: void*?, item: usize):
    let job = (CellJob*)(context else return)
    let index = job.indices[item]
    let halves = job.halves[item * cell_halves..<(item + 1) * cell_halves]
    let shape = new u8[block_bytes] --- in memory.heap catch failure:
        trap("out of memory loading a selection")
    defer free(shape) in memory.heap
    memory.set(shape, 0)
    let width = (usize)job.cells.cell_width(index)
    for y in 0..<(usize)job.cells.cell_height(index):
        for x in 0..<width:
            let at = (y * (usize)tile_size + x) * 8 + job.channel * 2
            shape[y * (usize)tile_size + x] = job.table[(usize)((u16)halves[at] | ((u16)halves[at + 1] << 8))]
    combine_cell(job.cells, index, shape, job.mode)

## Into `target` (empty to begin with): the pixels' perceptual lightness as a
## byte, 0 where transparent, for every cell `only` selects anything in, read
## a batch at a time: the guide Select and Mask's edge detection follows.
pub func luma(target: Cells*, reader: Reader, only: const Cells*) -> !:
    var no_indices: usize[]
    var no_halves: u8[]
    var no_ranges: u8[]
    var no_ranged: bool[]
    var no_table: u8[]
    var job = CellJob(cells = target, table = no_table, channel = 0, mode = Mode.replace, low = [0, 0, 0, 0], high = [0, 0, 0, 0], limit = 0, only = only,
                      ranges = no_ranges, ranged = no_ranged, indices = no_indices, halves = no_halves)
    try read_batches(target, reader, &job, luma_item, 0)

## Lightness for cell `job.indices[item]` from its halves: straight linear
## light weighted as Rec. 709, square-rooted (about gamma 2), times alpha.
func luma_item(context: void*?, item: usize):
    let job = (CellJob*)(context else return)
    let index = job.indices[item]
    let halves = job.halves[item * cell_halves..<(item + 1) * cell_halves]
    let bytes = job.cells.fresh(index)
    memory.set(bytes, 0)
    let width = (usize)job.cells.cell_width(index)
    for y in 0..<(usize)job.cells.cell_height(index):
        for x in 0..<width:
            let at = (y * (usize)tile_size + x) * 8
            let red = (f64)from_half((u16)halves[at] | ((u16)halves[at + 1] << 8))
            let green = (f64)from_half((u16)halves[at + 2] | ((u16)halves[at + 3] << 8))
            let blue = (f64)from_half((u16)halves[at + 4] | ((u16)halves[at + 5] << 8))
            let alpha = math.clamp((f64)from_half((u16)halves[at + 6] | ((u16)halves[at + 7] << 8)), 0.0, 1.0)
            let light = math.sqrt(math.clamp(0.2126 * red + 0.7152 * green + 0.0722 * blue, 0.0, 1.0)) * alpha
            bytes[y * (usize)tile_size + x] = (u8)math.imin(255, (i64)(light * 255.0 + 0.5))

# mark: The magic wand ==========================================================================

## Into `found` (empty to begin with): the pixels within `tolerance` (0..255,
## 8-bit sRGB, alpha included) of the color at (`x`, `y`), averaged over a
## `sample` by `sample` square, only those reachable from it through such
## pixels when `contiguous`. The seed pixel is always found.
pub func wand(found: Cells*, reader: Reader, x: i64, y: i64, sample: i64, tolerance: f64, contiguous: bool) -> !:
    if x < 0 or y < 0 or x >= (i64)found.extent_x or y >= (i64)found.extent_y:
        error(invalid, "the wand point lies outside the document")
    if not math.is_finite(tolerance) or tolerance < 0.0 or tolerance > 255.0:
        error(invalid, "wand tolerance is 0..255")
    if sample != 1 and sample != 3 and sample != 5:
        error(invalid, "the wand samples 1, 3 or 5 pixels square")
    let table = try new u8[131072] --- in memory.heap
    defer free(table) in memory.heap
    for bits in 0..<(usize)65536:
        let value = from_half((u16)bits)
        table[bits] = transfer.srgb_byte((f64)value)
        table[65536 + bits] = coverage_byte(value)
    var no_indices: usize[]
    var no_halves: u8[]
    var no_ranges: u8[]
    var no_ranged: bool[]
    let seed = try seed_color(found, reader, x, y, sample // 2)
    var job = CellJob(cells = found, table = table, channel = 0, mode = Mode.add, low = seed, high = seed,
                      limit = (i64)math.floor(tolerance + 0.5), only = none, ranges = no_ranges, ranged = no_ranged, indices = no_indices, halves = no_halves)
    # A transparent cell matches wholly or not at all.
    let clear: u8[4] = [0, 0, 0, 0]
    let blank: u8 = 255 if job.matches(clear) else 0
    var near = try Cells.create(found.extent_x, found.extent_y)
    defer near.destroy()
    job.cells = &near
    try read_batches(&near, reader, &job, match_item, blank)
    # The seed itself, whatever its own color against the average.
    let seed_cell = (usize)(y // (i64)tile_size) * (usize)near.columns() + (usize)(x // (i64)tile_size)
    if near.uniform(seed_cell) != 255:
        near.writable(seed_cell)[(usize)(y % (i64)tile_size) * (usize)tile_size + (usize)(x % (i64)tile_size)] = 255
    if not contiguous:
        for index in 0..<near.count():
            found.share(index, &near, index)
        return
    try flood(&near, found, x, y)

# mark: Grow and Similar ======================================================================

## Select › Grow (`contiguous`) and Similar, into `found` (empty to begin
## with): the pixels whose color (8-bit sRGB and alpha) lies within
## `tolerance` of the range of colors `selection` covers (its pixels wholly
## selected, or any selected where none is), reachable from the
## selection through such pixels when `contiguous`. Only the cells the
## selection touches are read for the range; every cell for the matches.
pub func grow(found: Cells*, selection: const Cells*, reader: Reader, tolerance: f64, contiguous: bool) -> !:
    if not math.is_finite(tolerance) or tolerance < 0.0 or tolerance > 255.0:
        error(invalid, "tolerance is 0..255")
    let table = try new u8[131072] --- in memory.heap
    defer free(table) in memory.heap
    for bits in 0..<(usize)65536:
        let value = from_half((u16)bits)
        table[bits] = transfer.srgb_byte((f64)value)
        table[65536 + bits] = coverage_byte(value)
    let count = found.count()
    # Per cell: lows and highs at half coverage, then at any coverage.
    let ranges = try new u8[count * 16] --- in memory.heap
    defer free(ranges) in memory.heap
    let ranged = try new bool[count * 2] --- in memory.heap
    defer free(ranged) in memory.heap
    for index in 0..<ranged.length:
        ranged[index] = false
    var no_indices: usize[]
    var no_halves: u8[]
    var job = CellJob(cells = found, table = table, channel = 0, mode = Mode.add, low = [0, 0, 0, 0], high = [255, 255, 255, 255],
                      limit = (i64)math.floor(tolerance + 0.5), only = selection, ranges = ranges, ranged = ranged, indices = no_indices, halves = no_halves)
    # The selection over transparent cells: their color is clear.
    var transparent = false
    var scratch = try Cells.create(found.extent_x, found.extent_y)
    defer scratch.destroy()
    var range_job = job
    range_job.cells = &scratch
    range_job.selection = selection
    # Cells the selection touches that hold no pixels come back 255 here.
    try read_batches(&scratch, reader, &range_job, range_item, 255)
    for index in 0..<count:
        if selection.uniform(index) != 0 and scratch.uniform(index) != 0:
            transparent = true
    if not merge_ranges(&job, ranges, ranged, count, 0, transparent) and not merge_ranges(&job, ranges, ranged, count, 1, transparent):
        return
    let clear: u8[4] = [0, 0, 0, 0]
    let blank: u8 = 255 if job.matches(clear) else 0
    var near = try Cells.create(found.extent_x, found.extent_y)
    defer near.destroy()
    job.cells = &near
    job.only = none
    try read_batches(&near, reader, &job, match_item, blank)
    if not contiguous:
        for index in 0..<near.count():
            found.share(index, &near, index)
        return
    try flood_from(&near, found, selection)

## Merge the cells' ranges at `level` (0 half coverage, 1 any) into the job's
## low and high; `transparent` adds clear. Whether any color was found.
func merge_ranges(job: CellJob*, ranges: const u8[], ranged: const bool[], count: usize, level: usize, transparent: bool) -> bool:
    var found = false
    var low: u8[4] = [255, 255, 255, 255]
    var high: u8[4] = [0, 0, 0, 0]
    if transparent:
        found = true
        low = [0, 0, 0, 0]
    for index in 0..<count:
        if not ranged[index * 2 + level]:
            continue
        found = true
        let at = index * 16 + level * 8
        for channel in 0..<(usize)4:
            low[channel] = ranges[at + channel] if ranges[at + channel] < low[channel] else low[channel]
            high[channel] = ranges[at + 4 + channel] if ranges[at + 4 + channel] > high[channel] else high[channel]
    if found:
        job.low = low
        job.high = high
    return found

## Grow's first pass: the range of colors under the selection in cell
## `job.indices[item]`, at half coverage and at any.
func range_item(context: void*?, item: usize):
    let job = (CellJob*)(context else return)
    let index = job.indices[item]
    let selection = job.selection else return
    let halves = job.halves[item * cell_halves..<(item + 1) * cell_halves]
    let value = selection.uniform(index)
    let bytes = (selection.block(index) else trap("a mixed cell has a block")).bytes if value < 0 else no_bytes()
    var low: u8[8] = [255, 255, 255, 255, 255, 255, 255, 255]
    var high: u8[8] = [0, 0, 0, 0, 0, 0, 0, 0]
    var any: bool[2] = [false, false]
    var color: u8[4] = [0, 0, 0, 0]
    let width = (usize)selection.cell_width(index)
    for y in 0..<(usize)selection.cell_height(index):
        for x in 0..<width:
            let coverage = (u8)value if value >= 0 else bytes[y * (usize)tile_size + x]
            if coverage == 0:
                continue
            let at = (y * (usize)tile_size + x) * 8
            for channel in 0..<(usize)4:
                let bits = (usize)((u16)halves[at + channel * 2] | ((u16)halves[at + channel * 2 + 1] << 8))
                color[channel] = job.table[bits + (65536 if channel == 3 else 0)]
            for level in 0..<(usize)2:
                # The range is the selection's solid colors: an anti-aliased
                # edge blends in the neighbours' colors and would let Grow
                # spread into them. Partial coverage counts only when nothing
                # is wholly selected.
                if level == 0 and coverage < 255:
                    continue
                any[level] = true
                for channel in 0..<(usize)4:
                    low[level * 4 + channel] = color[channel] if color[channel] < low[level * 4 + channel] else low[level * 4 + channel]
                    high[level * 4 + channel] = color[channel] if color[channel] > high[level * 4 + channel] else high[level * 4 + channel]
    for level in 0..<(usize)2:
        job.ranged[index * 2 + level] = any[level]
        for channel in 0..<(usize)4:
            job.ranges[index * 16 + level * 8 + channel] = low[level * 4 + channel]
            job.ranges[index * 16 + level * 8 + 4 + channel] = high[level * 4 + channel]

func no_bytes() -> u8[]:
    var nothing: u8[]
    return nothing

## The color the wand matches against, as 8-bit sRGB and alpha: the mean of
## the pixels within `reach` of (`x`, `y`) inside the document.
func seed_color(cells: const Cells*, reader: Reader, x: i64, y: i64, reach: i64) -> u8[4]!:
    let halves = try new u8[cell_halves] --- in memory.heap
    defer free(halves) in memory.heap
    var sum: f64[4] = [0.0, 0.0, 0.0, 0.0]
    var count = 0.0
    # Row by row, as the pixels come, so the sum is the same whatever the cells.
    var read_column: i64 = -1
    var read_row: i64 = -1
    var painted = false
    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)cells.extent_x or py >= (i64)cells.extent_y:
                continue
            let column = px // (i64)tile_size
            let row = py // (i64)tile_size
            if column != read_column or row != read_row:
                painted = try read_one(cells, reader, (u32)column, (u32)row, halves)
                read_column = column
                read_row = row
            count += 1.0
            if not painted:
                continue
            let at = ((usize)(py % (i64)tile_size) * (usize)tile_size + (usize)(px % (i64)tile_size)) * 8
            for channel in 0..<(usize)4:
                sum[channel] += (f64)from_half((u16)halves[at + channel * 2] | ((u16)halves[at + channel * 2 + 1] << 8))
    var seed: u8[4] = [0, 0, 0, 0]
    for channel in 0..<(usize)3:
        seed[channel] = transfer.srgb_byte((f64)(f32)(sum[channel] / count))
    seed[3] = coverage_byte((f32)(sum[3] / count))
    return seed

## Which pixels of cell `job.indices[item]` match the seed.
func match_item(context: void*?, item: usize):
    let job = (CellJob*)(context else return)
    let index = job.indices[item]
    let halves = job.halves[item * cell_halves..<(item + 1) * cell_halves]
    let shape = new u8[block_bytes] --- in memory.heap catch failure:
        trap("out of memory for the magic wand")
    defer free(shape) in memory.heap
    memory.set(shape, 0)
    let width = (usize)job.cells.cell_width(index)
    var color: u8[4] = [0, 0, 0, 0]
    for y in 0..<(usize)job.cells.cell_height(index):
        for x in 0..<width:
            let at = (y * (usize)tile_size + x) * 8
            for channel in 0..<(usize)4:
                let bits = (usize)((u16)halves[at + channel * 2] | ((u16)halves[at + channel * 2 + 1] << 8))
                color[channel] = job.table[bits + (65536 if channel == 3 else 0)]
            if job.matches(color):
                shape[y * (usize)tile_size + x] = 255
    combine_cell(job.cells, index, shape, Mode.add)

# mark: Reading in batches ======================================================================

## One pass over a batch of cells: what they are turned into, and how.
struct CellJob:
    var cells: Cells*
    var table: const u8[]
    var channel: usize
    var mode: Mode
    ## The colors matched: each channel from `low` to `high` (the wand's
    ## seed for both), and how far a channel may stray past them.
    var low: u8[4]
    var high: u8[4]
    var limit: i64
    ## When set, only the cells where it selects anything are read.
    var only: const Cells*?
    ## Grow and Similar: each cell's range of selected colors, 8 bytes a cell
    ## (four lows then four highs), and whether it has any.
    var ranges: u8[]
    var ranged: bool[]
    ## Grow's selection, whose covered pixels give the range.
    var selection: const Cells*? = none
    ## The batch: the cells, and their halves one after another.
    var indices: usize[]
    var halves: const u8[]

    ## Whether `color` is within the limit of the colors matched on every channel.
    func matches(color: u8[4]) -> bool:
        for channel in 0..<(usize)4:
            let value = (i64)color[channel]
            if value < (i64)self.low[channel] - self.limit or value > (i64)self.high[channel] + self.limit:
                return false
        return true

## Every cell of `cells` read through `reader` and handed to `work` a batch
## at a time on every processor; a transparent cell is `blank` throughout,
## combined by the job's mode here.
func read_batches(cells: Cells*, reader: Reader, job: CellJob*, work: func(void*?, usize) -> unit, blank: u8) -> !:
    if reader.batched:
        try read_gpu_batches(cells, reader, job, work, blank)
        return
    let indices = try new usize[batch_cells] --- in memory.heap
    defer free(indices) in memory.heap
    let halves = try new u8[batch_cells * cell_halves] --- in memory.heap
    defer free(halves) in memory.heap
    var filled: usize = 0
    for index in 0..<cells.count():
        let column = (u32)(index % (usize)cells.columns())
        let row = (u32)(index // (usize)cells.columns())
        if skipped(job.only, index):
            if filled > 0 and index + 1 == cells.count():
                job.indices = indices[..<filled]
                job.halves = halves
                each(filled, (void*)job, work)
                filled = 0
            continue
        if try reader.read(reader.context, column, row, halves[filled * cell_halves..<(filled + 1) * cell_halves]):
            indices[filled] = index
            filled += 1
        else:
            combine_value(cells, index, blank, job.mode)
        if filled == batch_cells or (filled > 0 and index + 1 == cells.count()):
            job.indices = indices[..<filled]
            job.halves = halves
            each(filled, (void*)job, work)
            filled = 0

## One of the two read batches a GPU source's cells go through, and which
## cells it holds (its halves one after another from offset 0).
struct CellRead:
    var batch: gpu.ReadBatch
    var indices: usize[]
    var filled: usize

## `read_batches` for a GPU source: cells recorded into one read batch while
## the other's are worked on, straight from the readback memory.
func read_gpu_batches(cells: Cells*, reader: Reader, job: CellJob*, work: func(void*?, usize) -> unit, blank: u8) -> !:
    var reads: CellRead[2] = [CellRead(batch = try gpu.ReadBatch.begin(reader.device)), CellRead(batch = gpu.ReadBatch())]
    defer release_cell_read(&reads[0])
    reads[1].batch = try gpu.ReadBatch.begin(reader.device)
    defer release_cell_read(&reads[1])
    let per_batch = reads[0].batch.capacity() // cell_halves
    for index in 0..<(usize)2:
        reads[index].indices = try new usize[per_batch] --- in memory.heap
    var next: usize = 0
    next = try fill_cell_read(cells, reader, &reads[0], next, blank, job.mode, job.only)
    next = try fill_cell_read(cells, reader, &reads[1], next, blank, job.mode, job.only)
    var turn: usize = 0
    while reads[turn].filled > 0:
        let current = &reads[turn]
        try current.batch.wait()
        job.indices = current.indices[..<current.filled]
        job.halves = try current.batch.bytes(0, current.filled * cell_halves)
        each(current.filled, (void*)job, work)
        next = try fill_cell_read(cells, reader, current, next, blank, job.mode, job.only)
        turn = 1 - turn

## Record cells from `next` on into `target` until it is full and submit it;
## transparent cells are combined as `blank` on the way. Where the list continues.
func fill_cell_read(cells: Cells*, reader: Reader, target: CellRead*, next: usize, blank: u8, mode: Mode, only: const Cells*?) -> usize!:
    try target.batch.reset()
    target.filled = 0
    var index = next
    while index < cells.count() and target.filled < target.indices.length:
        if skipped(only, index):
            index += 1
            continue
        let column = (u32)(index % (usize)cells.columns())
        let row = (u32)(index // (usize)cells.columns())
        if let texture = try reader.texture(reader.context, column, row):
            # Cells of halves one after another: each offset is a whole cell on.
            let offset = (try target.batch.reserve(cell_halves)) else break
            let rows = min_u32(tile_size, cells.extent_y - row * tile_size)
            try target.batch.copy(texture, gpu.Region(0, 0, tile_size, rows), offset)
            target.indices[target.filled] = index
            target.filled += 1
        else:
            combine_value(cells, index, blank, mode)
        index += 1
    if target.filled > 0:
        try target.batch.submit()
    return index

## Whether cell `index` is left out: `only` selects nothing there.
func skipped(only: const Cells*?, index: usize) -> bool:
    let limit = only else return false
    return limit.uniform(index) == 0

func release_cell_read(target: CellRead*):
    target.batch.finish()
    if target.indices.length > 0:
        free(target.indices) in memory.heap
        var none_left: usize[]
        target.indices = none_left

# mark: The flood ===============================================================================

## A growing stack of places to reach: a cell and a pixel in it, packed.
struct Places:
    var items: u64[]
    var count: usize

    func push(index: usize, x: i64, y: i64) -> !:
        if self.count == self.items.length:
            let grown = try new u64[(usize)math.imax(4096, (i64)self.items.length * 2)] --- in memory.heap
            if self.count > 0:
                memory.copy(grown, self.items, self.count)
            if self.items.length > 0:
                free(self.items) in memory.heap
            self.items = grown
        self.items[self.count] = ((u64)index << 16) | ((u64)y << 8) | (u64)x
        self.count += 1

    func destroy():
        if self.items.length > 0:
            free(self.items) in memory.heap

## Into `found`: every pixel of `near` reachable from (`x`, `y`) through
## pixels of `near`, sideways and up and down.
func flood(near: Cells*, found: Cells*, x: i64, y: i64) -> !:
    var none_yet: u64[]
    var places = Places(items = none_yet, count = 0)
    defer places.destroy()
    let queue = try new u16[65536] --- in memory.heap
    defer free(queue) in memory.heap
    let columns = (usize)near.columns()
    try places.push((usize)(y // (i64)tile_size) * columns + (usize)(x // (i64)tile_size), x % (i64)tile_size, y % (i64)tile_size)
    try drain(near, found, &places, queue)

## Into `found`: every pixel of `near` reachable from a pixel `seeds` at
## least half selects, through pixels of `near`: Select › Grow.
func flood_from(near: Cells*, found: Cells*, seeds: const Cells*) -> !:
    var none_yet: u64[]
    var places = Places(items = none_yet, count = 0)
    defer places.destroy()
    let queue = try new u16[65536] --- in memory.heap
    defer free(queue) in memory.heap
    for index in 0..<near.count():
        let seed = seeds.uniform(index)
        let kind = near.uniform(index)
        if seed == 0 or kind == 0 or found.uniform(index) == 255:
            continue
        let seed_bytes = (seeds.block(index) else trap("a mixed cell has a block")).bytes if seed < 0 else no_bytes()
        let width = seeds.cell_width(index)
        let height = seeds.cell_height(index)
        if kind == 255:
            # Any seed in a cell matching wholly reaches all of it.
            var seeded = seed >= 128
            if seed < 0:
                for y in 0..<height:
                    for x in 0..<width:
                        if seed_bytes[(usize)y * (usize)tile_size + (usize)x] >= 128:
                            seeded = true
                            break
                    if seeded:
                        break
            if seeded:
                found.fill(index, 255)
                try spill(near, found, &places, index)
            continue
        let matching = (near.block(index) else continue).bytes
        var reached: u8[] = no_bytes()
        for y in 0..<height:
            for x in 0..<width:
                let at = (usize)y * (usize)tile_size + (usize)x
                let covered = (u8)seed if seed >= 0 else seed_bytes[at]
                if covered < 128 or matching[at] == 0:
                    continue
                if reached.length == 0:
                    reached = found.writable(index)
                if reached[at] != 255:
                    try walk(near, found, &places, index, matching, reached, queue, at)
    try drain(near, found, &places, queue)

## Reach every place on `places`, and every place reaching them leads to.
func drain(near: Cells*, found: Cells*, places: Places*, queue: u16[]) -> !:
    while places.count > 0:
        places.count -= 1
        let item = places.items[places.count]
        let index = (usize)(item >> 16)
        let px = (i64)(item & 0xff)
        let py = (i64)((item >> 8) & 0xff)
        if found.uniform(index) == 255:
            continue
        let kind = near.uniform(index)
        if kind == 0:
            continue
        if kind == 255:
            # A cell matching wholly is reached wholly; on into its neighbours.
            found.fill(index, 255)
            try spill(near, found, places, index)
            continue
        let matching = (near.block(index) else continue).bytes
        let reached = found.writable(index)
        let start = (usize)py * (usize)tile_size + (usize)px
        if reached[start] == 255 or matching[start] == 0:
            continue
        try walk(near, found, places, index, matching, reached, queue, start)

## The pixels of mixed cell `index` reachable from `start` inside it; the
## places past its sides go on `places` for the cells beside.
func walk(near: const Cells*, found: const Cells*, places: Places*, index: usize, matching: const u8[], reached: u8[], queue: u16[], start: usize) -> !:
    let width = near.cell_width(index)
    let height = near.cell_height(index)
    let column = (i64)(index % (usize)near.columns())
    let row = (i64)(index // (usize)near.columns())
    reached[start] = 255
    queue[0] = (u16)start
    var head: usize = 0
    var tail: usize = 1
    while head < tail:
        let at = (usize)queue[head]
        head += 1
        let px = (i64)(at % (usize)tile_size)
        let py = (i64)(at // (usize)tile_size)
        for step in 0..<(usize)4:
            let nx = px + (1 if step == 0 else (-1 if step == 1 else 0))
            let ny = py + (1 if step == 2 else (-1 if step == 3 else 0))
            if nx >= 0 and ny >= 0 and nx < width and ny < height:
                let next = (usize)ny * (usize)tile_size + (usize)nx
                if matching[next] != 0 and reached[next] != 255:
                    reached[next] = 255
                    queue[tail] = (u16)next
                    tail += 1
                continue
            # Past the cell's side: the cell beside, when inside the document.
            let beside_column = column + (1 if nx >= width else (-1 if nx < 0 else 0))
            let beside_row = row + (1 if ny >= height else (-1 if ny < 0 else 0))
            if beside_column < 0 or beside_row < 0 or beside_column >= (i64)near.columns() or beside_row >= (i64)near.rows():
                continue
            let beside = (usize)beside_row * (usize)near.columns() + (usize)beside_column
            try offer(near, found, places, beside, (nx + (i64)tile_size) % (i64)tile_size, (ny + (i64)tile_size) % (i64)tile_size)

## A place in cell `index` onto `places`, unless it plainly leads nowhere.
func offer(near: const Cells*, found: const Cells*, places: Places*, index: usize, x: i64, y: i64) -> !:
    if found.uniform(index) == 255:
        return
    let kind = near.uniform(index)
    if kind == 0:
        return
    if kind < 0:
        let matching = (near.block(index) else return).bytes
        if matching[(usize)y * (usize)tile_size + (usize)x] == 0:
            return
    try places.push(index, x, y)

## From cell `index`, reached wholly: every place along its sides into the
## cells beside (one place will do for a cell that matches wholly).
func spill(near: const Cells*, found: const Cells*, places: Places*, index: usize) -> !:
    let columns = (i64)near.columns()
    let column = (i64)index % columns
    let row = (i64)index // columns
    let width = near.cell_width(index)
    let height = near.cell_height(index)
    for side in 0..<(usize)4:
        let beside_column = column + (1 if side == 0 else (-1 if side == 1 else 0))
        let beside_row = row + (1 if side == 2 else (-1 if side == 3 else 0))
        if beside_column < 0 or beside_row < 0 or beside_column >= columns or beside_row >= (i64)near.rows():
            continue
        let beside = (usize)(beside_row * columns + beside_column)
        # Along the shared side: its pixels in the cell beside.
        let along = height if side < 2 else width
        for step in 0..<along:
            let x = (0 if side == 0 else (near.cell_width(beside) - 1 if side == 1 else step))
            let y = (0 if side == 2 else (near.cell_height(beside) - 1 if side == 3 else step))
            try offer(near, found, places, beside, x, y)
            if near.uniform(beside) == 255:
                break

# mark: Conversions =============================================================================

## A sample 0..1 as coverage 0..255, rounded.
pub func coverage_byte(value: f32) -> u8:
    return (u8)(math.clamp((f64)value, 0.0, 1.0) * 255.0 + 0.5)