Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-jpeg

Source of release 0.10.1

0.10.1 / src / jpeg / render.lucb

#==============================================================================================
#
#   jpeg/render - The worker crew, render geometry, the band schedule and targets
#
#   DESCRIPTION:
#       Rendering runs in MCU-row bands on every processor, the calling thread one of
#       the workers: the IDCT of a band's blocks into component planes, and the band's
#       output rows. A band's rows interpolate one plane row into each neighbouring
#       band, so its color task waits for the IDCT of those. Tasks are handed out in
#       the order I0, I1, C0, I2, C1, ... (IDCT, color one band behind).
#
#       For a baseline picture coded in one interleaved scan, the calling thread
#       entropy-decodes MCU rows while the workers render the rows it has finished, so
#       nearly all of the rendering hides behind the entropy decoding.
#
#       Row callbacks from the frame's one interleaved baseline scan stream: the calling
#       thread entropy-decodes a group of MCU rows into a ring of coefficients, the workers
#       transform and color them, and the rows go to the callback before the next group
#       is decoded, so the first rows arrive at once and a few MCU rows are all it holds.
#       Other row callbacks render in groups of bands into one buffer after decoding and
#       hand each group on in order.
#
#==============================================================================================

## A worker's rows for one output row: component samples, an interpolated plane
## row and 8-bit pixels; and bytes for the encoder's band planes.
struct Scratch:
    var rows: f64[]
    var column: i32[]
    var pixels: u8[]
    var bytes: u8[]

struct Pool:
    var next: @usize
    var count: usize
    var task: func(void*, usize, Scratch*) -> unit
    var context: void*

struct Worker:
    var pool: Pool*
    var scratch: Scratch

## Workers draining one pool of tasks: started, then finished on the caller.
struct Crew:
    var pool: Pool
    var slots: Worker[]
    var handles: thread.Handle[64]
    var started: usize

func worker_main(context: void*?):
    drain((Worker*)(context else return))

func drain(worker: Worker*):
    let pool = worker.pool
    while true:
        let index = pool.next.add(1)
        if index >= pool.count:
            return
        pool.task(pool.context, index, &worker.scratch)

## Start up to `threads - 1` threads on `task(context, i, scratch)` for i in
## 0..<`count`; `crew_finish` makes the caller the last worker. `width`, `column`
## and `bytes` size each worker's Scratch (0 for none).
func crew_start(task: func(void*, usize, Scratch*) -> unit, context: void*, count: usize, threads: usize, width: usize, column: usize, bytes: usize = 0) -> Crew*!:
    var workers: usize = threads if threads < count else count
    workers = 64 if workers > 64 else (1 if workers == 0 else workers)
    let crew = try new Crew(pool = Pool(count = count, task = task, context = context)) in memory.heap
    crew.slots = new Worker[workers] --- in memory.heap catch failure:
        free(crew) in memory.heap
        error(failure.code, failure.message)
    for i in 0..<workers:
        crew.slots[i] = Worker(pool = &crew.pool, scratch = Scratch())
    errdefer release(crew)
    for i in 0..<workers:
        try allocate_scratch(&crew.slots[i].scratch, width, column, bytes)
    for i in 1..<workers:
        crew.handles[crew.started] = thread.spawn(worker_main, (void*)&crew.slots[i], name = "jpeg") catch:
            # Fewer threads: the others take its share from the counter.
            break
        crew.started += 1
    return crew

func allocate_scratch(scratch: Scratch*, width: usize, column: usize, bytes: usize) -> !:
    if width > 0:
        scratch.rows = try new f64[4 * width] in memory.heap
        scratch.column = try new i32[column + 1] in memory.heap
        scratch.pixels = try new u8[4 * width] in memory.heap
    if bytes > 0:
        scratch.bytes = try new u8[bytes] --- in memory.heap

## Work on the crew's tasks until none are left, join its threads and free it.
func crew_finish(crew: Crew*) -> !:
    drain(&crew.slots[0])
    var failed = false
    for i in 0..<crew.started:
        crew.handles[i].join() catch:
            failed = true
    release(crew)
    if failed:
        error(invalid, "JPEG worker thread could not be joined")

func release(crew: Crew*):
    for slot in crew.slots:
        if slot.scratch.rows.length > 0:
            free(slot.scratch.rows) in memory.heap
        if slot.scratch.column.length > 0:
            free(slot.scratch.column) in memory.heap
        if slot.scratch.pixels.length > 0:
            free(slot.scratch.pixels) in memory.heap
        if slot.scratch.bytes.length > 0:
            free(slot.scratch.bytes) in memory.heap
    free(crew.slots) in memory.heap
    free(crew) in memory.heap

## Run `task` for 0..<`count` on up to `threads` threads, the caller's included.
func run_tasks(task: func(void*, usize, Scratch*) -> unit, context: void*, count: usize, threads: usize, width: usize = 0, column: usize = 0, bytes: usize = 0) -> !:
    if count == 0:
        return
    try crew_finish(try crew_start(task, context, count, threads, width, column, bytes))

## The threads a decode uses: `requested`, or every processor for 0; one for a
## picture too small to be worth starting threads.
func thread_count(requested: usize, pixels: usize) -> usize:
    if pixels < 65536:
        return 1
    let wanted = (usize)os.cpus() if requested == 0 else requested
    return 1 if wanted == 0 else 64 if wanted > 64 else wanted

## Where rendered rows go: 8-bit pixels, a Raster's f64 samples, or a row sink
## fed from a buffer of whole bands.
struct Target:
    var bytes: u8[]
    var doubles: f64[]
    ## Values a pixel: 1 or 3 for a Raster, 3 or 4 for bytes.
    var pixel: usize
    var sink: RowSink?
    var context: void*?
    ## The output row stored at the start of `bytes`.
    var first_row: usize

struct RenderJob:
    var d: const Decoder*
    var target: const Target*
    var cosines: Cosines
    var quant: f64[256]
    ## The output size, output rows a band, and the band color task 0 renders.
    var width: usize
    var height: usize
    var band_rows: usize
    var first_band: usize

## Plan the planes for a decode at 1/`scale` and set up its job: each component's
## IDCT output size, its plane, and its sampling ratio against output pixels.
func plan(d: Decoder*, target: const Target*, scale: usize, ring: usize = 0) -> RenderJob*!:
    let n = 8 // scale
    let width = (d.width + scale - 1) // scale
    let height = (d.height + scale - 1) // scale
    var allocated: usize = 0
    for i in 0..<d.count:
        let c = &d.components[i]
        if not d.quant_present[c.quant]:
            error(corrupt, "JPEG component lacks quantization or DC scan")
        allocated += c.bands.length * c.vertical * c.bx * 128 + c.nonzero.length * 8
        # Scaled, a subsampled component takes a larger square IDCT where that
        # replaces upsampling by a power of two in both directions, as libjpeg does.
        var size = n
        while size < 8 and (d.max_h * n) % (c.horizontal * size * 2) == 0 and (d.max_v * n) % (c.vertical * size * 2) == 0:
            size *= 2
        c.out_w = size
        c.out_h = size
        c.stride = c.bx * c.out_w
        c.rows = c.by * c.out_h
        c.num_x = c.horizontal * c.out_w
        c.den_x = n * d.max_h
        c.num_y = c.vertical * c.out_h
        c.den_y = n * d.max_v
        c.valid_w = (width * c.num_x + c.den_x - 1) // c.den_x
        c.valid_h = (height * c.num_y + c.den_y - 1) // c.den_y
        # Scaled output upsamples as libjpeg does: triangle for 2:1 when there are
        # more than two samples and the scale is above 1/8, else replication.
        let halves = (c.num_x == c.den_x or c.num_x * 2 == c.den_x) and (c.num_y == c.den_y or c.num_y * 2 == c.den_y)
        c.replicate = scale > 1 and (c.num_x != c.den_x or c.num_y != c.den_y) and (scale == 8 or not halves or c.valid_w <= 2)
        # A streamed scan's plane is a ring of `ring` MCU rows.
        c.plane_ring = ring * c.vertical * c.out_h
        let plane_rows = c.rows if ring == 0 or c.plane_ring > c.rows else c.plane_ring
        if ring > 0:
            c.plane_ring = plane_rows
        allocated += c.stride * plane_rows
        if allocated > d.max_bytes:
            error(limit, "JPEG coefficient and sample buffers exceed byte limit")
        if c.plane.length > 0:
            free(c.plane) in memory.heap
        c.plane = try new u8[c.stride * plane_rows] --- in memory.heap
    let job = try new RenderJob(d = d, target = target, cosines = Cosines.make(), width = width, height = height, band_rows = d.max_v * n, first_band = 0) in memory.heap
    for i in 0..<(usize)256:
        job.quant[i] = (f64)d.quant[i]
    return job

## The widest plane, for Scratch.column.
func widest_plane(d: const Decoder*) -> usize:
    var column: usize = 0
    for i in 0..<d.count:
        column = d.components[i].stride if d.components[i].stride > column else column
    return column

## The IDCT of MCU row `band`'s blocks into the planes.
func idct_band(job: const RenderJob*, band: usize):
    let d = job.d
    for i in 0..<d.count:
        let c = &d.components[i]
        let across = &job.cosines.by_frequency[cosine_level(c.out_w) * 64]
        let down = &job.cosines.table[cosine_level(c.out_h) * 64]
        let quant = &job.quant[c.quant * 64]
        let plane = c.plane.data
        for by in band * c.vertical..<(band + 1) * c.vertical:
            let line = block_at(c, by, 0)
            for bx in 0..<c.bx:
                idct_block(line + bx * 64, quant, across, down, c.out_w, c.out_h, plane + plane_row(c, by * c.out_h) * c.stride + bx * c.out_w, c.stride)

func idct_task(context: void*, band: usize, scratch: Scratch*):
    idct_band((RenderJob*)context, band)

## Band `band`'s output rows into the target.
func color_band(job: const RenderJob*, band: usize, scratch: Scratch*):
    let d = job.d
    let target = job.target
    let width = job.width
    let first = band * job.band_rows
    let last = first + job.band_rows if first + job.band_rows < job.height else job.height
    let rows = scratch.rows.data
    let pixel = target.pixel
    for y in first..<last:
        for i in 0..<d.count:
            component_row(&d.components[i], y, width, rows + i * width, scratch.column.data)
        if target.doubles.length > 0:
            let out = scratch.pixels.data
            convert_row(d, rows, width, out, pixel)
            let base = target.doubles.data + y * width * pixel
            for v in 0..<width * pixel:
                base[v] = (f64)out[v]
        else:
            convert_row(d, rows, width, target.bytes.data + (y - target.first_row) * width * pixel, pixel)

func color_task(context: void*, index: usize, scratch: Scratch*):
    let job = (RenderJob*)context
    color_band(job, index + job.first_band, scratch)

## A one-way gate: shut until opened, then open for good. Waiters sleep in the
## kernel; passing an open gate is one load.
struct Gate:
    var opened: @u32
    var sleepers: sync.Semaphore

    func open():
        self.opened.store(1, .release)
        self.sleepers.release()

    func pass():
        if self.opened.load(.acquire) == 0:
            # Take the permit `open` leaves and hand it on to the next waiter.
            self.sleepers.acquire()
            self.sleepers.release()

## IDCT and color tasks for every band, with the waits between them. A waiter
## sleeps at the one band gate it needs, so a band finishing wakes only its own.
struct Schedule:
    var job: RenderJob*
    ## MCU rows: IDCT bands. Color bands can be fewer (padding rows).
    var bands: usize
    var color_bands: usize
    ## Per band: its coefficients are complete; its IDCT is done.
    var ready: Gate[]
    var done: Gate[]
    ## Set when the decode fails: the remaining tasks do nothing.
    var stopped: @u32

## Wait at `gate`; false when the decode stopped meanwhile.
func await(s: Schedule*, gate: Gate*) -> bool:
    gate.pass()
    return s.stopped.load(.acquire) == 0

## Task `t` of 2 * bands: I0, I1, C0, I2, C1, ..., I(n-1), C(n-2), C(n-1).
func schedule_task(context: void*, t: usize, scratch: Scratch*):
    let s = (Schedule*)context
    if t == 0 or (t % 2 == 1 and (t + 1) // 2 < s.bands):
        let band = 0 if t == 0 else (t + 1) // 2
        if not await(s, &s.ready[band]):
            return
        idct_band(s.job, band)
        s.done[band].open()
        return
    let band = t // 2 - 1 if t % 2 == 0 else (t - 1) // 2
    if band >= s.color_bands:
        return
    # The IDCT of this band and its neighbours, latest first.
    let high = band + 1 if band + 1 < s.bands else band
    let low = band - 1 if band > 0 else 0
    var b = high + 1
    while b > low:
        b -= 1
        if not await(s, &s.done[b]):
            return
    color_band(s.job, band, scratch)

## A schedule over `job`'s bands, every band's coefficients complete when `decoded`.
func schedule_new(job: RenderJob*, decoded: bool) -> Schedule*!:
    let d = job.d
    let s = try new Schedule(job = job, bands = d.mcuy, color_bands = (job.height + job.band_rows - 1) // job.band_rows) in memory.heap
    errdefer free(s) in memory.heap
    s.ready = try new Gate[d.mcuy] in memory.heap
    errdefer free(s.ready) in memory.heap
    s.done = try new Gate[d.mcuy] in memory.heap
    if decoded:
        for i in 0..<d.mcuy:
            s.ready[i].open()
    return s

## Stop a schedule's remaining tasks and release everything waiting.
func schedule_stop(s: Schedule*):
    s.stopped.store(1, .release)
    for i in 0..<s.bands:
        s.ready[i].open()
        s.done[i].open()

func schedule_free(s: Schedule*):
    free(s.ready) in memory.heap
    free(s.done) in memory.heap
    free(s) in memory.heap

## Whether a scan can be decoded while its rows render: the frame's one
## interleaved baseline scan, not split at restart markers, going to pixels.
func pipelines(d: const Decoder*, scan: const Scan*) -> bool:
    if d.progressive or d.threads < 2 or scan.count != d.count or splits(d, scan):
        return false
    if let target = d.target:
        if target.sink != none:
            return false
        return d.count > 1 or (d.components[0].horizontal == 1 and d.components[0].vertical == 1)
    return false

## Decode the frame's one interleaved scan on this thread while workers render
## each MCU row once it is complete.
func pipelined_scan(d: Decoder*, scan: const Scan*, reader: Reader*) -> !:
    try check_tables(d, scan)
    let target = d.target else trap("pipelined without a target")
    let job = try plan(d, target, d.scale)
    defer free(job) in memory.heap
    let s = try schedule_new(job, false)
    defer schedule_free(s)
    let crew = try crew_start(schedule_task, (void*)s, 2 * d.mcuy, d.threads, job.width, widest_plane(d))
    var b = Bits.reading(d, reader.position)
    var cursor = Cursor.at(d, 0)
    for row in 0..<scan.down:
        sequential_range(d, scan, &b, &cursor, row * scan.across, (row + 1) * scan.across) catch failure:
            # Release the waiting workers, finish, and report.
            schedule_stop(s)
            crew_finish(crew) catch:
                recover ()
            error(failure.code, failure.message)
        s.ready[row].open()
    try crew_finish(crew)
    if b.leftover():
        error(corrupt, "JPEG marker prefix missing")
    resume_after(d, reader, &b)
    d.rendered = true

## Whether a scan streams to the row sink: the frame's one interleaved baseline
## scan, its coefficients not made whole already by an earlier scan.
func streams(d: const Decoder*, scan: const Scan*) -> bool:
    if d.progressive or not d.to_sink() or scan.count != d.count or d.components[0].bands.length > 0:
        return false
    return d.count > 1 or (d.components[0].horizontal == 1 and d.components[0].vertical == 1)

## Decode a streaming scan a group of MCU rows at a time: coefficients into a
## ring of the group's rows, transformed into a ring of planes two MCU rows
## longer (a band's color reads the rows either side), and every band whose
## next row is in colored and handed on.
func streamed_scan(d: Decoder*, scan: const Scan*, reader: Reader*) -> !:
    try check_tables(d, scan)
    let target = d.target else trap("a streamed scan has a target")
    let deliver = target.sink else trap("a streamed scan has a sink")
    let group = d.threads * 2 if d.threads > 1 else 2
    for i in 0..<d.count:
        let c = &d.components[i]
        c.ring = group
        try allocate_bands(c, group)
    let job = try plan(d, target, d.scale, group + 2)
    defer free(job) in memory.heap
    let width = job.width
    let column = widest_plane(d)
    let buffer = try new u8[(group + 1) * job.band_rows * width * target.pixel] in memory.heap
    defer free(buffer) in memory.heap
    target.bytes = buffer
    let color_bands = (job.height + job.band_rows - 1) // job.band_rows
    var b = Bits.reading(d, reader.position)
    var cursor = Cursor.at(d, 0)
    var decoded: usize = 0
    var colored: usize = 0
    while decoded < scan.down:
        let count = group if decoded + group <= scan.down else scan.down - decoded
        # Blocks decode into zeroed coefficients.
        for i in 0..<d.count:
            for slot in d.components[i].bands:
                memory.set(u8[]((u8*)slot.blocks.data, slot.blocks.length * 2), 0)
        try sequential_range(d, scan, &b, &cursor, decoded * scan.across, (decoded + count) * scan.across)
        job.first_band = decoded
        try run_tasks(idct_group_task, (void*)job, count, d.threads)
        decoded += count
        let ready = decoded - 1 if decoded < scan.down else color_bands
        let last_band = ready if ready < color_bands else color_bands
        if last_band > colored:
            job.first_band = colored
            target.first_row = colored * job.band_rows
            try run_tasks(color_task, (void*)job, last_band - colored, d.threads, width, column)
            let first = colored * job.band_rows
            let last = last_band * job.band_rows if last_band * job.band_rows < job.height else job.height
            try deliver(target.context, first, last - first, buffer[..<(last - first) * width * target.pixel])
            colored = last_band
    if b.leftover():
        error(corrupt, "JPEG marker prefix missing")
    resume_after(d, reader, &b)
    d.rendered = true

func idct_group_task(context: void*, index: usize, scratch: Scratch*):
    let job = (RenderJob*)context
    idct_band(job, job.first_band + index)

## Render a completely read decoder into its target.
func render(d: Decoder*) -> !:
    let target = d.target else trap("render without a target")
    if let deliver = target.sink:
        try render_rows(d, target, deliver)
        return
    let job = try plan(d, target, d.scale)
    defer free(job) in memory.heap
    let width = job.width
    let column = widest_plane(d)
    let s = try schedule_new(job, true)
    defer schedule_free(s)
    try run_tasks(schedule_task, (void*)s, 2 * d.mcuy, d.threads, width, column)

## Render a completely read decoder to a row sink a group of MCU rows at a
## time, as a streamed scan does: the IDCT into a ring of planes two MCU rows
## longer than the group (a band's color reads the rows either side), and
## every band whose next row is in colored and handed on. The planes stay a
## few rows, whatever the picture, and each MCU row's coefficients go once its
## planes are made, as the rows made from them go out.
func render_rows(d: Decoder*, target: Target*, deliver: RowSink) -> !:
    # The progressive scans' bitmaps are done with.
    for i in 0..<d.count:
        let c = &d.components[i]
        if c.nonzero.length > 0:
            free(c.nonzero) in memory.heap
            var none_left: u64[]
            c.nonzero = none_left
    let group = d.threads * 2 if d.threads > 1 else 2
    let job = try plan(d, target, d.scale, group + 2)
    defer free(job) in memory.heap
    let width = job.width
    let column = widest_plane(d)
    let buffer = try new u8[(group + 1) * job.band_rows * width * target.pixel] in memory.heap
    defer free(buffer) in memory.heap
    target.bytes = buffer
    let color_bands = (job.height + job.band_rows - 1) // job.band_rows
    var made: usize = 0
    var colored: usize = 0
    while made < d.mcuy:
        let count = group if made + group <= d.mcuy else d.mcuy - made
        job.first_band = made
        try run_tasks(idct_group_task, (void*)job, count, d.threads)
        for i in 0..<d.count:
            for band in made..<made + count:
                release_band(&d.components[i], band)
        made += count
        let ready = made - 1 if made < d.mcuy else color_bands
        let last_band = ready if ready < color_bands else color_bands
        if last_band > colored:
            job.first_band = colored
            target.first_row = colored * job.band_rows
            try run_tasks(color_task, (void*)job, last_band - colored, d.threads, width, column)
            let first = colored * job.band_rows
            let last = last_band * job.band_rows if last_band * job.band_rows < job.height else job.height
            try deliver(target.context, first, last - first, buffer[..<(last - first) * width * target.pixel])
            colored = last_band

## A progressive picture's first sight: once every component has its DC
## coefficients (the first scans), the picture at 1/8 size, straight from them,
## to the decoder's coarse sink as RGBA; later scans refine what the rows show.
func render_coarse(d: Decoder*) -> !:
    d.coarse_done = true
    let sink = d.coarse else return
    let width = (d.width + 7) // 8
    let height = (d.height + 7) // 8
    let pixels = try new u8[width * height * 4] in memory.heap
    defer free(pixels) in memory.heap
    var target = Target(bytes = pixels, pixel = 4)
    let job = try plan(d, &target, 8)
    defer free(job) in memory.heap
    try run_tasks(idct_task, (void*)job, d.mcuy, d.threads)
    let bands = (height + job.band_rows - 1) // job.band_rows
    try run_tasks(color_task, (void*)job, bands, d.threads, width, widest_plane(d))
    # Its planes go; the full render plans its own.
    for i in 0..<d.count:
        let c = &d.components[i]
        if c.plane.length > 0:
            free(c.plane) in memory.heap
            var empty: u8[]
            c.plane = empty
    try sink(d.coarse_context, width, height, pixels)

## Whether every component has had its first DC scan.
func dc_ready(d: const Decoder*) -> bool:
    for i in 0..<d.count:
        if d.components[i].progression[0] == -1:
            return false
    return true