Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-image

Source of release 0.45.1

0.45.1 / src / selection_cells.lucb

## A selection's coverage kept in cells of the canvas's 256-pixel grid. A cell
## is either one value throughout (nothing selected, or all of it), which costs
## no memory, or a block of coverage bytes. Blocks are counted and shared with
## every copy of the selection (an undo step's) until one of them writes to
## one, so a copy costs a pointer a cell and a change costs only the cells it
## touches: a marquee across a 360-megapixel canvas holds its edge cells alone.
from luce_std import math
import memory
from luce_canvas import pool
from luce_canvas.tiles import tile_size

## Bytes in one cell's block: 256 rows of 256, whatever the cell's size.
pub let block_bytes: usize = 65536

## How a new shape combines with the selection so far.
pub enum Mode as u8:
    replace = 0
    add = 1
    subtract = 2
    intersect = 3

## One cell's coverage, rows of 256 bytes. Past the document's edge (in the
## last column and row of cells) the bytes are never read.
pub struct Block:
    pub var references: usize
    ## The content's name for the GPU mirror, unique for all time; 0 while
    ## written and not yet settled.
    var version: u64
    ## Whether the fields below describe the bytes: what `settle` found.
    var scanned: bool
    ## 0 all clear, 255 all selected, 1 a mix.
    var kind: u8
    ## The box of nonzero bytes in the cell, when the kind is not 0.
    var left: i64
    var top: i64
    var right: i64
    var bottom: i64
    pub var bytes: u8[]

## The box of every selected pixel, and whether there is one.
pub struct Covered:
    pub var found: bool = false
    pub var left: i64 = 0
    pub var top: i64 = 0
    pub var right: i64 = 0
    pub var bottom: i64 = 0

    func take(left: i64, top: i64, right: i64, bottom: i64):
        if not self.found:
            self = Covered(found = true, left = left, top = top, right = right, bottom = bottom)
            return
        self.left = math.imin(self.left, left)
        self.top = math.imin(self.top, top)
        self.right = math.imax(self.right, right)
        self.bottom = math.imax(self.bottom, bottom)

## Versions for the GPU mirror; 0 is unsettled and 1 and 2 name the uniform
## selected cells (`Cells.shows`). Settled on the main thread only.
var last_version: u64 = 2

pub struct Cells:
    pub var extent_x: u32
    pub var extent_y: u32
    var cell_columns: u32
    var cell_rows: u32
    ## A cell's block, or `none` where it is `values`' one value throughout.
    var blocks: Block*?[]
    var values: u8[]

    ## `width` by `height` pixels, nothing selected.
    pub static func create(width: u32, height: u32) -> Cells!:
        let columns = (width + tile_size - 1) // tile_size
        let rows = (height + tile_size - 1) // tile_size
        let count = (usize)columns * (usize)rows
        let blocks = try new Block*?[count] --- in memory.heap
        errdefer free(blocks) in memory.heap
        let values = try new u8[count] --- in memory.heap
        for index in 0..<count:
            blocks[index] = none
        memory.set(values, 0)
        return Cells(extent_x = width, extent_y = height, cell_columns = columns, cell_rows = rows, blocks = blocks, values = values)

    ## A second holder of the same cells: every block shared until written.
    pub func copy() -> Cells!:
        var copy = try Cells.create(self.extent_x, self.extent_y)
        for index in 0..<self.blocks.length:
            copy.values[index] = self.values[index]
            if let block = self.blocks[index]:
                block.references += 1
                copy.blocks[index] = block
        return copy

    pub func destroy():
        for index in 0..<self.blocks.length:
            self.release(index)
        if self.blocks.length > 0:
            free(self.blocks) in memory.heap
            free(self.values) in memory.heap
        var no_blocks: Block*?[]
        var no_values: u8[]
        self.blocks = no_blocks
        self.values = no_values

    pub func count() -> usize:
        return self.blocks.length

    pub func columns() -> u32:
        return self.cell_columns

    pub func rows() -> u32:
        return self.cell_rows

    ## The document pixels cell `index` covers: its corner and size.
    pub func origin_x(index: usize) -> i64:
        return (i64)(index % (usize)self.cell_columns) * (i64)tile_size

    pub func origin_y(index: usize) -> i64:
        return (i64)(index // (usize)self.cell_columns) * (i64)tile_size

    pub func cell_width(index: usize) -> i64:
        return math.imin((i64)tile_size, (i64)self.extent_x - self.origin_x(index))

    pub func cell_height(index: usize) -> i64:
        return math.imin((i64)tile_size, (i64)self.extent_y - self.origin_y(index))

    ## Whether the cell is a whole 256 by 256 (not cut by the document's edge).
    pub func whole(index: usize) -> bool:
        return self.cell_width(index) == (i64)tile_size and self.cell_height(index) == (i64)tile_size

    ## The coverage at a document pixel, which must be inside.
    pub func at(x: i64, y: i64) -> u8:
        let index = (usize)(y // (i64)tile_size) * (usize)self.cell_columns + (usize)(x // (i64)tile_size)
        let block = self.blocks[index] else return self.values[index]
        return block.bytes[(usize)(y % (i64)tile_size) * (usize)tile_size + (usize)(x % (i64)tile_size)]

    ## The cell's one value, or -1 when it holds a block.
    pub func uniform(index: usize) -> i64:
        if self.blocks[index] != none:
            return -1
        return (i64)self.values[index]

    ## The cell's block, borrowed, or `none` when it is one value.
    pub func block(index: usize) -> Block*?:
        return self.blocks[index]

    ## Make cell `index` `value` throughout, letting its block go.
    pub func fill(index: usize, value: u8):
        self.release(index)
        self.values[index] = value

    ## Every cell `value` throughout.
    pub func fill_all(value: u8):
        for index in 0..<self.blocks.length:
            self.fill(index, value)

    ## Put `other`'s cell `source` here at `index`, shared.
    pub func share(index: usize, other: const Cells*, source: usize):
        self.release(index)
        self.values[index] = other.values[source]
        if let block = other.blocks[source]:
            block.references += 1
            self.blocks[index] = block

    ## The bytes of cell `index`, held here alone and ready to write: a block
    ## made from the cell's one value, or copied when shared. Safe from several
    ## threads on different cells: a block shared with another selection is
    ## only ever read there while this one changes.
    pub func writable(index: usize) -> u8[]:
        if let block = self.blocks[index]:
            if block.references == 1:
                block.scanned = false
                block.version = 0
                return block.bytes
            let copied = Cells.fresh_block()
            memory.copy(copied.bytes, block.bytes, block_bytes)
            block.references -= 1
            self.blocks[index] = copied
            return copied.bytes
        let made = Cells.fresh_block()
        memory.set(made.bytes, self.values[index])
        self.blocks[index] = made
        return made.bytes

    ## A block of its own for cell `index`, its bytes unset: for a change
    ## that writes every byte.
    pub func fresh(index: usize) -> u8[]:
        self.release(index)
        let made = Cells.fresh_block()
        self.blocks[index] = made
        return made.bytes

    static func fresh_block() -> Block*:
        let bytes = new u8[block_bytes] --- in memory.heap catch failure:
            trap("out of memory for a selection cell")
        let block = new Block(references = 1, version = 0, scanned = false, kind = 1, left = 0, top = 0, right = 0, bottom = 0, bytes = bytes) in memory.heap catch failure:
            trap("out of memory for a selection cell")
        return block

    func release(index: usize):
        let block = self.blocks[index] else return
        self.blocks[index] = none
        block.references -= 1
        if block.references == 0:
            free(block.bytes) in memory.heap
            free(block) in memory.heap

    ## What the GPU mirror shows for cell `index`: 0 nothing, 1 the tile every
    ## whole selected cell shares, 2 a selected cell cut by the document's edge
    ## (its own tile, clear past the edge), else its block's version.
    pub func shows(index: usize) -> u64:
        if let block = self.blocks[index]:
            return block.version
        if self.values[index] == 0:
            return 0
        return 1 if self.whole(index) and self.values[index] == 255 else 2

    ## After a change: the blocks written since are scanned (on every
    ## processor), those one value throughout become that value again, each
    ## other gets a new version; the box of every selected pixel is returned.
    pub func settle() -> Covered!:
        var pending: usize = 0
        for block in self.blocks:
            if let written = block:
                if not written.scanned:
                    pending += 1
        if pending > 0:
            let items = try new usize[pending] --- in memory.heap
            defer free(items) in memory.heap
            var at: usize = 0
            for index in 0..<self.blocks.length:
                if let written = self.blocks[index]:
                    if not written.scanned:
                        items[at] = index
                        at += 1
            var job = ScanJob(cells = &self, items = items)
            each(pending, (void*)&job, scan_item)
            for item in items:
                let block = self.blocks[item] else continue
                if block.kind != 1:
                    self.fill(item, block.kind)
                elif block.version == 0:
                    last_version += 1
                    block.version = last_version
        var covered = Covered()
        for index in 0..<self.blocks.length:
            let x = self.origin_x(index)
            let y = self.origin_y(index)
            if let block = self.blocks[index]:
                covered.take(x + block.left, y + block.top, x + block.right, y + block.bottom)
            elif self.values[index] != 0:
                covered.take(x, y, x + self.cell_width(index), y + self.cell_height(index))
        return covered

## The blocks `settle` scans, an item each.
struct ScanJob:
    var cells: Cells*
    var items: const usize[]

## Scan one block: its kind and the box of its nonzero bytes, within the cell.
func scan_item(context: void*?, item: usize):
    let job = (ScanJob*)(context else return)
    let index = job.items[item]
    let block = job.cells.blocks[index] else return
    let width = (usize)job.cells.cell_width(index)
    let height = (usize)job.cells.cell_height(index)
    var found = false
    var full = true
    var left = width
    var right: usize = 0
    var top: usize = 0
    var bottom: usize = 0
    for y in 0..<height:
        let line = block.bytes[y * (usize)tile_size..<y * (usize)tile_size + width]
        var low: usize = 0
        while low < width and line[low] == 0:
            low += 1
        if low > 0:
            full = false
        if low == width:
            continue
        var high = width
        while line[high - 1] == 0:
            high -= 1
        if full:
            if high < width:
                full = false
            else:
                for x in low..<high:
                    if line[x] != 255:
                        full = false
                        break
        if not found:
            found = true
            top = y
        left = left if left < low else low
        right = right if right > high else high
        bottom = y + 1
    block.scanned = true
    block.kind = 255 if found and full else (1 if found else 0)
    block.left = (i64)left
    block.top = (i64)top
    block.right = (i64)right
    block.bottom = (i64)bottom

## `work(context, item)` for every item in 0..<`count`, on the worker pool (at
## most 16 threads, this one among them); the items go to whichever thread is
## free next.
pub func each(count: usize, context: void*?, work: func(void*?, usize) -> unit):
    pool.run(count, work, context, limit = 16)