Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-jpeg

Source of release 0.10.0

0.10.0 / src / jpeg / progressive.lucb

#==============================================================================================
#
#   jpeg/progressive - Spectral selection and successive approximation scans
#
#   DESCRIPTION:
#       Each progressive scan adds a band of coefficients (first scans) or one more bit
#       of precision to them (refinement scans) for one component, or DC for several.
#       Scans depend on each other bit by bit, so they decode in order on the calling
#       thread; rendering afterwards is parallel.
#
#==============================================================================================

## The state a progressive scan carries from block to block.
struct Progress:
    var eob: usize

func dc_first(b: Bits*, table: const Huffman*, predictor: i32*, block: i16*, al: u32) -> !:
    let size = try b.symbol(table)
    if size > 11:
        error(corrupt, "JPEG DC difference too large")
    let diff = extend(b.take(size), size) if size > 0 else 0
    let value = *predictor + diff
    if value < -32768 or value > 32767:
        error(corrupt, "JPEG DC predictor out of range")
    *predictor = value
    block[0] = (i16)(value << al)

func dc_refine(b: Bits*, block: i16*, al: u32):
    block[0] = (i16)((i32)block[0] | ((i32)b.bit() << al))

func ac_first(b: Bits*, table: const Huffman*, block: i16*, nonzero: u64*, ss: usize, se: usize, al: u32, state: Progress*) -> !:
    if state.eob > 0:
        state.eob -= 1
        return
    let order = &zigzag[0]
    let fast = &table.fast_ac[0]
    let lookup = &table.lookup[0]
    var acc = b.acc
    var bits = b.bits
    var k = ss
    while k <= se:
        if bits < 32:
            b.acc = acc
            b.bits = bits
            b.fill()
            acc = b.acc
            bits = b.bits
        let look = (usize)(acc >> peek)
        let hit = fast[look]
        if hit != 0:
            # Run, value and length from one lookup.
            k = k +% (usize)((hit >> 8) & 15)
            let used = (u32)(hit & 255)
            acc <<= used
            bits = bits -% used
            if k > se:
                error(corrupt, "JPEG AC run exceeds spectral band")
            block[order[k]] = (i16)((hit >> 16) << al)
            *nonzero |= (u64)1 << (u64)k
            k = k +% 1
            continue
        var symbol: u32 = 0
        let found = (u32)lookup[look]
        if found != 0:
            symbol = found & 255
            acc <<= found >> 8
            bits = bits -% (found >> 8)
        else:
            let (length, value) = slow_symbol(table, acc)
            if length == 0:
                error(corrupt, "invalid JPEG Huffman code")
            symbol = value
            acc <<= length
            bits = bits -% length
        let run = (usize)(symbol >> 4)
        let size = symbol & 15
        if size == 0:
            if run == 15:
                k = k +% 16
                if k > se + 1:
                    error(corrupt, "JPEG zero run exceeds spectral band")
                continue
            # An end-of-band run: this block and 2^run - 1 + (run bits) more.
            var extra: usize = 0
            if run > 0:
                extra = (usize)(acc >> (64 - (u64)run))
                acc <<= (u64)run
                bits = bits -% (u32)run
            state.eob = ((usize)1 << run) + extra - 1
            break
        if size > 10:
            error(corrupt, "JPEG AC coefficient too large")
        k = k +% run
        if k > se:
            error(corrupt, "JPEG AC run exceeds spectral band")
        block[order[k]] = (i16)(extend((u32)(acc >> (64 - size)), size) << al)
        *nonzero |= (u64)1 << (u64)k
        acc <<= size
        bits = bits -% size
        k = k +% 1
    b.acc = acc
    b.bits = bits

## Refinement: every coefficient already nonzero gains one bit, and newly nonzero
## ones (magnitude 1 << al) are placed at the zeros a run skips. `nonzero` is the
## block's bitmap of nonzero coefficients by zigzag index, so the zeros counted
## and the coefficients refined are found by bit arithmetic.
func ac_refine(b: Bits*, table: const Huffman*, block: i16*, nonzero: u64*, ss: usize, se: usize, al: u32, state: Progress*) -> !:
    let order = &zigzag[0]
    let lookup = &table.lookup[0]
    let plus = (i32)1 << al
    let band = ((u64)0xFFFFFFFFFFFFFFFF << (u64)ss) & ((u64)0xFFFFFFFFFFFFFFFF >> (u64)(63 - se))
    var acc = b.acc
    var bits = b.bits
    var k = ss
    if state.eob == 0:
        while k <= se:
            if bits < 32:
                b.acc = acc
                b.bits = bits
                b.fill()
                acc = b.acc
                bits = b.bits
            var symbol: u32 = 0
            let found = (u32)lookup[(usize)(acc >> peek)]
            if found != 0:
                symbol = found & 255
                acc <<= found >> 8
                bits = bits -% (found >> 8)
            else:
                let (length, value) = slow_symbol(table, acc)
                if length == 0:
                    error(corrupt, "invalid JPEG Huffman code")
                symbol = value
                acc <<= length
                bits = bits -% length
            let run = symbol >> 4
            let size = symbol & 15
            var new_value: i32 = 0
            if size == 0:
                if run != 15:
                    var extra: usize = 0
                    if run > 0:
                        extra = (usize)(acc >> (64 - (u64)run))
                        acc <<= (u64)run
                        bits = bits -% run
                    state.eob = ((usize)1 << (usize)run) + extra
                    break
            elif size == 1:
                new_value = plus if acc >> 63 != 0 else -plus
                acc <<= 1
                bits = bits -% 1
            else:
                error(corrupt, "invalid progressive JPEG refinement")
            # The zero the symbol lands on: after `run` zeros for a new value, the
            # sixteenth for a zero run (which then continues just past it).
            let here = band & ((u64)0xFFFFFFFFFFFFFFFF << (u64)k)
            var zeros = ~*nonzero & here
            var skip = run if new_value != 0 else 15
            while skip > 0 and zeros != 0:
                zeros &= zeros - 1
                skip -= 1
            if zeros == 0:
                if new_value != 0:
                    error(corrupt, "JPEG refinement exceeds spectral band")
                error(corrupt, "JPEG refinement zero run exceeds band")
            let at = lowest64(zeros)
            # Refine the nonzero coefficients passed over on the way.
            var passed = *nonzero & here & (((u64)1 << (u64)at) - 1)
            while passed != 0:
                let j = lowest64(passed)
                passed &= passed - 1
                if bits == 0:
                    b.acc = acc
                    b.bits = bits
                    b.fill()
                    acc = b.acc
                    bits = b.bits
                refine(block + order[j], (i32)(acc >> 63), plus)
                acc <<= 1
                bits = bits -% 1
            if new_value != 0:
                block[order[at]] = (i16)new_value
                *nonzero |= (u64)1 << (u64)at
            k = at + 1
    if state.eob > 0:
        # Inside an end-of-band run: only the nonzero coefficients gain a bit.
        var passed = *nonzero & band & ((u64)0xFFFFFFFFFFFFFFFF << (u64)k) if k < 64 else 0
        while passed != 0:
            let j = lowest64(passed)
            passed &= passed - 1
            if bits == 0:
                b.acc = acc
                b.bits = bits
                b.fill()
                acc = b.acc
                bits = b.bits
            refine(block + order[j], (i32)(acc >> 63), plus)
            acc <<= 1
            bits = bits -% 1
        state.eob -= 1
    b.acc = acc
    b.bits = bits

## One correction bit for a nonzero coefficient: where it is set and the
## coefficient's own bit at this position is not, the magnitude grows by `plus`.
## Branch-free, since the bits are noise to a predictor.
inline func refine(slot: i16*, bit: i32, plus: i32):
    let value = (i32)*slot
    let sign = value >> 31
    let magnitude = (value ^ sign) -% sign
    let grow = bit & (i32)((magnitude & plus) == 0)
    *slot = (i16)(value +% (((plus ^ sign) -% sign) & -%grow))

## The index of the lowest set bit of a nonzero word, by de Bruijn multiplication.
inline func lowest64(x: u64) -> usize:
    return (usize)debruijn[(usize)(((x & -%x) *% 0x03F79D71B4CB0A89) >> 58)]

let debruijn: u8[64] = [0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4, 62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5, 63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11, 46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6]

## Decode a progressive scan whose data starts at `reader`'s position; leave the
## reader at the marker after it.
func progressive_scan(d: Decoder*, scan: const Scan*, reader: Reader*) -> !:
    let ss = scan.ss
    let se = scan.se
    let al = scan.al
    let refining = scan.ah != 0
    for i in 0..<scan.count:
        let c = &d.components[scan.selected[i]]
        if (ss == 0 and not refining and not d.tables[c.dc].present) or (ss > 0 and not d.tables[c.ac + 4].present):
            error(corrupt, "JPEG Huffman table missing")
    var b = Bits.reading(d, reader.position)
    var state = Progress()
    var predictors: i32[4]
    var expected: u8 = 208
    let one = scan.count == 1
    let total = scan.across * scan.down
    for mcu in 0..<total:
        try b.keep_up()
        if mcu > 0 and d.restart > 0 and mcu % d.restart == 0:
            if state.eob != 0:
                error(corrupt, "JPEG restart marker mismatch")
            try b.restart(expected)
            expected = next_restart(expected)
            predictors = i32[4](0)
        let mx = mcu % scan.across
        let my = mcu // scan.across
        for i in 0..<scan.count:
            let c = &d.components[scan.selected[i]]
            let horizontal: usize = 1 if one else c.horizontal
            let vertical: usize = 1 if one else c.vertical
            for y in 0..<vertical:
                let line = block_at(c, my * vertical + y, mx * horizontal)
                for x in 0..<horizontal:
                    let index = (my * vertical + y) * c.bx + mx * horizontal + x
                    let block = line + x * 64
                    if ss == 0:
                        if refining:
                            dc_refine(&b, block, al)
                        else:
                            try dc_first(&b, &d.tables[c.dc], &predictors[i], block, al)
                    elif refining:
                        try ac_refine(&b, &d.tables[c.ac + 4], block, c.nonzero.data + index, ss, se, al, &state)
                    else:
                        try ac_first(&b, &d.tables[c.ac + 4], block, c.nonzero.data + index, ss, se, al, &state)
                    if b.overrun():
                        error(corrupt, "unexpected JPEG marker inside entropy data")
    if state.eob != 0:
        error(corrupt, "JPEG EOB run exceeds scan")
    if b.leftover():
        error(corrupt, "JPEG marker prefix missing")
    resume_after(d, reader, &b)