Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-jpeg

Source of release 0.10.0

0.10.0 / src / jpeg / huffman.lucb

#==============================================================================================
#
#   jpeg/huffman - Huffman tables with 11-bit lookahead, and the 64-bit bit reader
#
#   DESCRIPTION:
#       A code of up to eleven bits decodes with one table lookup on the next eleven bits.
#       For AC tables a second lookup also covers the coefficient's magnitude bits when
#       code and magnitude together fit in eleven bits, which is most coefficients of a
#       photograph: run, value and total length come from one load. Longer codes fall
#       back to the canonical maxcode walk.
#
#==============================================================================================

let lookahead: u32 = 11
## Lookup entries, 2^lookahead, and the shift that leaves the top lookahead bits.
let entries: usize = 2048
let peek: u64 = 53

struct Huffman:
    ## The next eleven bits: (code length << 8) | symbol, or 0 for a longer code.
    var lookup: u16[entries]
    ## AC tables, the next eleven bits: (value << 16) | (run << 8) | bits used by code
    ## and magnitude together, or 0 when they do not fit or the symbol has no value.
    var fast_ac: i32[entries]
    ## The largest code of each length, -1 for none.
    var maxcode: i32[18]
    ## Index of a length's first symbol, less its first code.
    var offset: i32[17]
    var symbols: u8[256]
    var present: bool

## Build `table` from a DHT segment's code counts and symbols; the counts are
## already checked not to oversubscribe the code space.
func build_huffman(table: Huffman*, counts: const u32[17], values: const u8[]):
    *table = Huffman()
    var code: i32 = 0
    var k: usize = 0
    for length in 1..<(usize)17:
        table.offset[length] = (i32)k - code
        for i in 0..<(usize)counts[length]:
            table.symbols[k] = values[k]
            if length <= (usize)lookahead:
                let shift = lookahead - (u32)length
                let first = (usize)code << shift
                for fill in 0..<((usize)1 << shift):
                    table.lookup[first + fill] = (u16)((length << 8) | (usize)values[k])
            code += 1
            k += 1
        table.maxcode[length] = code - 1 if counts[length] > 0 else -1
        code <<= 1
    table.maxcode[17] = 2147483647
    for prefix in 0..<entries:
        let entry = (u32)table.lookup[prefix]
        if entry == 0:
            continue
        let length = entry >> 8
        let run = (entry >> 4) & 15
        let size = entry & 15
        if size == 0 or length + size > lookahead:
            continue
        let bits = ((u32)prefix >> (lookahead - length - size)) & (((u32)1 << size) - 1)
        let value = extend(bits, size)
        table.fast_ac[prefix] = (value << 16) | (i32)(run << 8) | (i32)(length + size)
    table.present = true

## The signed value of `size` magnitude bits.
inline func extend(bits: u32, size: u32) -> i32:
    return (i32)bits if bits >= ((u32)1 << (size -% 1)) else (i32)bits +% 1 -% ((i32)1 << size)

## A code longer than eleven bits, from the top of `acc`: (length, symbol), or length 0
## when no code matches.
func slow_symbol(table: const Huffman*, acc: u64) -> (u32, u32):
    var length: u32 = lookahead + 1
    var code = (i32)(acc >> (64 - length))
    while length <= 16 and code > table.maxcode[(usize)length]:
        length += 1
        code = (i32)(acc >> (64 - length))
    if length > 16:
        return (0, 0)
    return (length, (u32)table.symbols[(usize)(table.offset[(usize)length] + code)])

## Entropy-coded data as a stream of bits, most significant first, read 64 bits
## ahead. Stuffed zero bytes are removed. At a marker or the end of the data the
## reader supplies zero bits and counts them in `padded`; reading into them is
## corrupt data, checked after each block.
struct Bits:
    var data: const u8*
    var end: usize
    var pos: usize
    ## Unread bits at the top; `bits` of them are valid, the last `padded` are fill.
    var acc: u64
    var bits: u32
    var padded: u32
    ## The window a scan from a file reads through (jpeg/source).
    var window: Window*?

    static func over(data: const u8[], position: usize) -> Bits:
        return Bits(data = data.data, end = data.length, pos = position, acc = 0, bits = 0, padded = 0, window = none)

    ## A scan's reader from `position` in the decoder's data, through its window if any.
    static func reading(d: const Decoder*, position: usize) -> Bits:
        return Bits(data = d.data.data, end = d.data.length, pos = position, acc = 0, bits = 0, padded = 0, window = d.window)

    ## Before an MCU of a scan from a file: the window slides on once less than
    ## an MCU's worst is left, so no MCU reads past it.
    func keep_up() -> !:
        let window = self.window else return
        if self.end - self.pos >= window_margin or not window.more():
            return
        try window.slide(self.pos)
        self.data = window.buffer.data
        self.end = window.length
        self.pos = 0

    ## Top up to at least 57 bits.
    func fill():
        var acc = self.acc
        var bits = self.bits
        let data = self.data
        var pos = self.pos
        # Eight bytes at once while none of them is 0xFF (a stuffed byte or marker).
        if bits <= 56 and pos + 8 <= self.end:
            let p = data + pos
            let word = ((u64)p[0] << 56) | ((u64)p[1] << 48) | ((u64)p[2] << 40) | ((u64)p[3] << 32) | ((u64)p[4] << 24) | ((u64)p[5] << 16) | ((u64)p[6] << 8) | (u64)p[7]
            if ((~word -% 0x0101010101010101) & word & 0x8080808080808080) == 0:
                let count = (64 - bits) >> 3
                let taken = 8 * count
                acc |= (word >> (64 - taken)) << (64 - taken - bits)
                self.acc = acc
                self.bits = bits + taken
                self.pos = pos + (usize)count
                return
        while bits <= 56:
            var byte: u64 = 0
            if pos < self.end:
                let value = data[pos]
                if value != 255:
                    byte = (u64)value
                    pos += 1
                elif pos + 1 < self.end and data[pos + 1] == 0:
                    byte = 255
                    pos += 2
                else:
                    self.padded += 8
            else:
                self.padded += 8
            acc |= byte << (56 - bits)
            bits += 8
        self.acc = acc
        self.bits = bits
        self.pos = pos

    ## `count` bits (1 through 16) as an unsigned value.
    func take(count: u32) -> u32:
        if self.bits < count:
            self.fill()
        let value = (u32)(self.acc >> (64 - count))
        self.acc <<= count
        self.bits -= count
        return value

    ## One bit.
    func bit() -> u32:
        if self.bits == 0:
            self.fill()
        let value = (u32)(self.acc >> 63)
        self.acc <<= 1
        self.bits -= 1
        return value

    ## The next Huffman symbol from `table`.
    func symbol(table: const Huffman*) -> u32!:
        if self.bits < 16:
            self.fill()
        let entry = (u32)table.lookup[(usize)(self.acc >> peek)]
        if entry != 0:
            let length = entry >> 8
            self.acc <<= length
            self.bits -= length
            return entry & 255
        let (length, value) = slow_symbol(table, self.acc)
        if length == 0:
            error(corrupt, "invalid JPEG Huffman code")
        self.acc <<= length
        self.bits -= length
        return value

    ## Whether the last read went past the data into fill bits.
    func overrun() -> bool:
        return self.bits < self.padded

    ## Whether whole bytes of data were read ahead and left unconsumed: the scan or
    ## restart interval ended before its data did.
    func leftover() -> bool:
        return self.bits >= self.padded + 8

    ## Past the restart marker `expected` (208..215) at the reader's position, with
    ## the bit buffer emptied.
    func restart(expected: u8) -> !:
        if self.leftover():
            error(corrupt, "JPEG marker prefix missing")
        if self.pos >= self.end or self.data[self.pos] != 255:
            error(corrupt, "JPEG marker prefix missing")
        var at = self.pos + 1
        while at < self.end and self.data[at] == 255:
            at += 1
        if at >= self.end:
            error(corrupt, "JPEG restart marker missing")
        if self.data[at] != expected:
            error(corrupt, "JPEG restart marker mismatch")
        self.pos = at + 1
        self.acc = 0
        self.bits = 0
        self.padded = 0

## The next restart marker after `marker` (208..215).
func next_restart(code: u8) -> u8:
    return 208 if code == 215 else code + 1