dymokomi/luce-image
Source of release 0.45.1
0.45.1 / src / selection_level.lucb
## A selection's cells taken down pyramid levels: each byte of level `level`
## the mean coverage of the 2^level by 2^level square of document pixels it
## covers (those inside the document), as the view's pyramid reduces a
## layer. Previews work here — Select and Mask's and Transform Selection's —
## so a slider or a drag costs the pixels the screen shows, not the
## document's.
##
## A level cell whose square of document cells is one value throughout takes
## that value without looking at a byte; only the squares an edge crosses are
## read, a run of document pixels at a time, so the work follows the edge.
from luce_std import math
import memory
from luce_canvas.tiles import tile_size
from selection_cells import Cells, each
## How many pixels a side of `extent` document pixels has at `level`.
pub func level_extent(extent: u32, level: u32) -> u32:
let span = (u64)1 << (u64)level
return (u32)(((u64)extent + span - 1) >> (u64)level)
## `source` taken down `level` levels (0: a copy sharing its cells).
pub func reduce(source: const Cells*, level: u32) -> Cells!:
if level == 0:
return try source.copy()
var target = try Cells.create(level_extent(source.extent_x, level), level_extent(source.extent_y, level))
errdefer target.destroy()
let count = target.count()
let values = try new i64[count] --- in memory.heap
defer free(values) in memory.heap
var pending: usize = 0
for index in 0..<count:
values[index] = settled_square(source, &target, index, level)
if values[index] >= 0:
target.fill(index, (u8)values[index])
else:
pending += 1
let items = try new usize[pending] --- in memory.heap
defer free(items) in memory.heap
var at: usize = 0
for index in 0..<count:
if values[index] < 0:
items[at] = index
at += 1
# Made here, on this thread: the workers only fill the bytes.
_ = target.fresh(index)
var job = ReduceJob(source = source, target = &target, items = items, level = level, failed = false)
each(pending, (void*)&job, reduce_item)
if job.failed:
error(memory.exhausted, "out of memory taking the selection down a level")
_ = try target.settle()
return target
## The document cells level cell `index` covers: first column and row, and
## one past the last.
struct Square:
var left: i64
var top: i64
var right: i64
var bottom: i64
func square_of(source: const Cells*, target: const Cells*, index: usize, level: u32) -> Square:
let per = (i64)1 << (i64)level
let column = (i64)(index % (usize)target.columns())
let row = (i64)(index // (usize)target.columns())
return Square(left = column * per, top = row * per, right = math.imin((i64)source.columns(), (column + 1) * per),
bottom = math.imin((i64)source.rows(), (row + 1) * per))
## The one value level cell `index` takes when every document cell it covers
## is that value; -1 when its bytes must be worked out.
func settled_square(source: const Cells*, target: const Cells*, index: usize, level: u32) -> i64:
let square = square_of(source, target, index, level)
let columns = (i64)source.columns()
var value: i64 = -2
for row in square.top..<square.bottom:
for column in square.left..<square.right:
let found = source.uniform((usize)(row * columns + column))
if found < 0 or (value != -2 and found != value):
return -1
value = found
return value
struct ReduceJob:
var source: const Cells*
var target: const Cells*
var items: const usize[]
var level: u32
var failed: bool
## One level cell: the sums of the document pixels over each of its bytes,
## a run at a time along each row of each document cell it covers, then the
## means.
func reduce_item(context: void*?, item: usize):
let job = (ReduceJob*)(context else return)
let source = job.source
let index = job.items[item]
let level = (i64)job.level
let bytes = (job.target.block(index) else return).bytes
let sums = new u32[(usize)tile_size * (usize)tile_size] --- in memory.heap catch failure:
job.failed = true
return
defer free(sums) in memory.heap
memory.set(u8[]((u8*)sums.data, sums.length * 4), 0)
let square = square_of(source, job.target, index, job.level)
let columns = (i64)source.columns()
# The level cell's first document pixel.
let base_x = square.left * (i64)tile_size
let base_y = square.top * (i64)tile_size
for row in square.top..<square.bottom:
for column in square.left..<square.right:
let cell = (usize)(row * columns + column)
let value = source.uniform(cell)
if value == 0:
continue
let origin_x = column * (i64)tile_size
let origin_y = row * (i64)tile_size
let width = source.cell_width(cell)
let block = source.block(cell)
for y in 0..<source.cell_height(cell):
let line = (usize)(((origin_y + y - base_y) >> level) * (i64)tile_size)
var x: i64 = 0
while x < width:
# The run of pixels that fall in one level byte.
let at = (origin_x + x - base_x) >> level
let end = math.imin(width, ((at + 1) << level) - (origin_x - base_x))
var total: u32 = 0
if let found = block:
let row_at = y * (i64)tile_size
for sample in x..<end:
total += (u32)found.bytes[(usize)(row_at + sample)]
else:
total = (u32)value * (u32)(end - x)
sums[line + (usize)at] += total
x = end
# Each byte's mean over the document pixels it covers.
let width = job.target.cell_width(index)
let height = job.target.cell_height(index)
let limit_x = (i64)source.extent_x - base_x
let limit_y = (i64)source.extent_y - base_y
for y in 0..<height:
let across_y = math.imin((y + 1) << level, limit_y) - (y << level)
for x in 0..<width:
let across_x = math.imin((x + 1) << level, limit_x) - (x << level)
let count = (u32)(across_x * across_y)
let at = (usize)(y * (i64)tile_size + x)
bytes[at] = (u8)((sums[at] + count // 2) // count)
# mark: Tests ===================================================================================
## Tests' oracle: the mean of the document pixels a level byte covers.
func dense_mean(cells: const Cells*, level: u32, x: i64, y: i64) -> u8:
let per = (i64)1 << (i64)level
var total: i64 = 0
var count: i64 = 0
for sy in y * per..<math.imin((y + 1) * per, (i64)cells.extent_y):
for sx in x * per..<math.imin((x + 1) * per, (i64)cells.extent_x):
total += (i64)cells.at(sx, sy)
count += 1
return (u8)((total + count // 2) // count)
## Cells `width` by `height`, a soft disc, a hard notch and a cut corner:
## edges in some cells, others one value either way.
func disc(width: u32, height: u32) -> Cells!:
var cells = try Cells.create(width, height)
for index in 0..<cells.count():
let bytes = cells.writable(index)
for y in 0..<cells.cell_height(index):
for x in 0..<cells.cell_width(index):
let px = cells.origin_x(index) + x
let py = cells.origin_y(index) + y
let dx = px - 700
let dy = py - 500
let distance = math.sqrt((f64)(dx * dx + dy * dy))
var value = math.clamp((420.0 - distance) * 8.0, 0.0, 255.0)
if px > 1100 and py < 90:
value = 255.0
bytes[(usize)(y * (i64)tile_size + x)] = (u8)value
_ = try cells.settle()
return cells
test "a selection taken down a level holds each square's mean, reading only the edge":
var cells = try disc(1500, 1100)
defer cells.destroy()
for level in [(u32)1, 2, 3, 5, 9]:
var reduced = try reduce(&cells, level)
defer reduced.destroy()
assert(reduced.extent_x == level_extent(1500, level) and reduced.extent_y == level_extent(1100, level))
for y in 0..<(i64)reduced.extent_y:
for x in 0..<(i64)reduced.extent_x:
if reduced.at(x, y) != dense_mean(&cells, level, x, y):
trap(f"level {level} differs at {x}, {y}: {reduced.at(x, y)} vs {dense_mean(&cells, level, x, y)}")
test "a 15000 by 24000 selection taken down levels keeps whole squares one value":
var cells = try Cells.create(15000, 24000)
defer cells.destroy()
for index in 0..<cells.count():
let x = cells.origin_x(index)
let y = cells.origin_y(index)
if x >= 1024 and x < 12032 and y >= 2048 and y < 20224:
cells.fill(index, 255)
# A soft edge down one column of cells.
for row in 8..<(usize)79:
let bytes = cells.writable(row * (usize)cells.columns() + 47)
for y in 0..<(usize)256:
for x in 0..<(usize)256:
bytes[y * 256 + x] = (u8)x
_ = try cells.settle()
var reduced = try reduce(&cells, 5)
defer reduced.destroy()
assert(reduced.extent_x == 469 and reduced.extent_y == 750)
assert(reduced.at(200, 300) == 255 and reduced.at(10, 10) == 0 and reduced.at(380, 300) > 100 and reduced.at(380, 300) < 200)
# At level 2 a cell covers four by four document cells: inside the
# rectangle it holds no bytes.
var quarter = try reduce(&cells, 2)
defer quarter.destroy()
assert(quarter.uniform(3 * (usize)quarter.columns() + 1) == 255 and quarter.uniform(0) == 0)