Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-jpeg

Source of release 0.10.1

0.10.1 / src / jpeg / encode_entropy.lucb

#==============================================================================================
#
#   jpeg/encode_entropy - Huffman coding of quantized blocks
#
#   DESCRIPTION:
#       Blocks arrive quantized in zigzag order. A block's nonzero coefficients are found
#       as a 64-bit mask, four at a time, and walked by their set bits, so zero runs cost
#       nothing. Each band codes into its own unstuffed stream of 32-bit words; the
#       bands are then joined in order into the file with 0xFF stuffing, restart markers
#       and the first MCU of each band, whose DC predictions need the band before.
#
#       Tables are the standard ones of ITU T.81 Annex K, or with `optimize` ones fitted
#       to the picture's own symbol counts (libjpeg's jpeg_gen_optimal_table).
#
#==============================================================================================

let std_dc_luma_counts: u8[16] = [0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
let std_dc_luma_values: u8[12] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
let std_ac_luma_counts: u8[16] = [0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 125]
let std_ac_luma_values: u8[162] = [1, 2, 3, 0, 4, 17, 5, 18, 33, 49, 65, 6, 19, 81, 97, 7, 34, 113, 20, 50, 129, 145, 161, 8, 35, 66, 177, 193, 21, 82, 209, 240, 36, 51, 98, 114, 130, 9, 10, 22, 23, 24, 25, 26, 37, 38, 39, 40, 41, 42, 52, 53, 54, 55, 56, 57, 58, 67, 68, 69, 70, 71, 72, 73, 74, 83, 84, 85, 86, 87, 88, 89, 90, 99, 100, 101, 102, 103, 104, 105, 106, 115, 116, 117, 118, 119, 120, 121, 122, 131, 132, 133, 134, 135, 136, 137, 138, 146, 147, 148, 149, 150, 151, 152, 153, 154, 162, 163, 164, 165, 166, 167, 168, 169, 170, 178, 179, 180, 181, 182, 183, 184, 185, 186, 194, 195, 196, 197, 198, 199, 200, 201, 202, 210, 211, 212, 213, 214, 215, 216, 217, 218, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250]
let std_dc_chroma_counts: u8[16] = [0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
let std_dc_chroma_values: u8[12] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
let std_ac_chroma_counts: u8[16] = [0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 119]
let std_ac_chroma_values: u8[162] = [0, 1, 2, 3, 17, 4, 5, 33, 49, 6, 18, 65, 81, 7, 97, 113, 19, 34, 50, 129, 8, 20, 66, 145, 161, 177, 193, 9, 35, 51, 82, 240, 21, 98, 114, 209, 10, 22, 36, 52, 225, 37, 241, 23, 24, 25, 26, 38, 39, 40, 41, 42, 53, 54, 55, 56, 57, 58, 67, 68, 69, 70, 71, 72, 73, 74, 83, 84, 85, 86, 87, 88, 89, 90, 99, 100, 101, 102, 103, 104, 105, 106, 115, 116, 117, 118, 119, 120, 121, 122, 130, 131, 132, 133, 134, 135, 136, 137, 138, 146, 147, 148, 149, 150, 151, 152, 153, 154, 162, 163, 164, 165, 166, 167, 168, 169, 170, 178, 179, 180, 181, 182, 183, 184, 185, 186, 194, 195, 196, 197, 198, 199, 200, 201, 202, 210, 211, 212, 213, 214, 215, 216, 217, 218, 226, 227, 228, 229, 230, 231, 232, 233, 234, 242, 243, 244, 245, 246, 247, 248, 249, 250]

## One Huffman table for writing: counts of codes by length and symbols (for the
## DHT segment), and each symbol's code and length.
struct CodeTable:
    var counts: u8[16]
    var values: u8[256]
    var count: usize
    var code: u32[256]
    var size: u8[256]

    ## A table from code counts by length and symbols in code order.
    static func make(counts: const u8[], values: const u8[]) -> CodeTable:
        var table = CodeTable()
        var code: u32 = 0
        var k: usize = 0
        for length in 0..<(usize)16:
            table.counts[length] = counts[length]
            for i in 0..<(usize)counts[length]:
                let symbol = (usize)values[k]
                table.values[k] = values[k]
                table.code[symbol] = code
                table.size[symbol] = (u8)(length + 1)
                code += 1
                k += 1
            code <<= 1
        table.count = k
        return table

## Symbol counts for fitting tables: DC and AC, luma at 0 and chroma at 257.
struct Counts:
    var dc: u32[514]
    var ac: u32[514]

## A table fitted to `frequency` (257 entries, the last reserved): libjpeg's
## jpeg_gen_optimal_table, code lengths limited to 16 bits and the all-ones code
## left unused.
func optimal_table(frequency: const u32[]) -> CodeTable:
    var freq: i64[257]
    for i in 0..<(usize)256:
        freq[i] = (i64)frequency[i]
    freq[256] = 1
    var codesize: i32[257]
    var others: i32[257]
    for i in 0..<(usize)257:
        others[i] = -1
    while true:
        # The two least frequent trees (the larger symbol on ties) merge.
        var c1: i32 = -1
        var v: i64 = 1000000000000
        for i in 0..<(usize)257:
            if freq[i] != 0 and freq[i] <= v:
                v = freq[i]
                c1 = (i32)i
        var c2: i32 = -1
        v = 1000000000000
        for i in 0..<(usize)257:
            if freq[i] != 0 and freq[i] <= v and (i32)i != c1:
                v = freq[i]
                c2 = (i32)i
        if c2 < 0:
            break
        freq[(usize)c1] += freq[(usize)c2]
        freq[(usize)c2] = 0
        codesize[(usize)c1] += 1
        while others[(usize)c1] >= 0:
            c1 = others[(usize)c1]
            codesize[(usize)c1] += 1
        others[(usize)c1] = c2
        codesize[(usize)c2] += 1
        while others[(usize)c2] >= 0:
            c2 = others[(usize)c2]
            codesize[(usize)c2] += 1
    var bits: i32[33]
    for i in 0..<(usize)257:
        if codesize[i] != 0:
            bits[(usize)codesize[i]] += 1
    # Lengths over 16 move up the tree, as Annex K.3 describes.
    var i: usize = 32
    while i > 16:
        while bits[i] > 0:
            var j = i - 2
            while bits[j] == 0:
                j -= 1
            bits[i] -= 2
            bits[i - 1] += 1
            bits[j + 1] += 2
            bits[j] -= 1
        i -= 1
    # Drop the reserved symbol's code, the longest.
    while bits[i] == 0:
        i -= 1
    bits[i] -= 1
    var counts: u8[16]
    for length in 1..<(usize)17:
        counts[length - 1] = (u8)bits[length]
    var values: u8[256]
    var k: usize = 0
    for length in 1..<(i32)33:
        for symbol in 0..<(usize)256:
            if codesize[symbol] == length:
                values[k] = (u8)symbol
                k += 1
    return CodeTable.make(counts, values[..<k])

## The number of bits of a magnitude below 2048.
func magnitude_bits() -> u8[2048]:
    var table: u8[2048]
    for v in 1..<(usize)2048:
        var n: u8 = 0
        var x = v
        while x != 0:
            x >>= 1
            n += 1
        table[v] = n
    return table

## An unstuffed bit stream in 32-bit words, most significant first, growing as it
## fills; `failed` when growing failed.
struct BitBuffer:
    var words: u32[]
    var used: usize
    var acc: u64
    var bits: u32
    var failed: bool

    ## Room for `count` more words.
    func ensure(count: usize) -> bool:
        if self.used + count <= self.words.length:
            return true
        var capacity = self.words.length * 2
        if capacity < self.used + count:
            capacity = self.used + count + 1024
        let grown = new u32[capacity] --- in memory.heap catch:
            self.failed = true
            return false
        memory.copy(grown, self.words, self.used)
        if self.words.length > 0:
            free(self.words) in memory.heap
        self.words = grown
        return true

    func reset():
        self.used = 0
        self.acc = 0
        self.bits = 0
        self.failed = false

    func close():
        if self.words.length > 0:
            free(self.words) in memory.heap
        self = BitBuffer()

## Everything block coding reads.
struct Coding:
    ## DC and AC tables for luma (0) and chroma (1).
    var dc: CodeTable[2]
    var ac: CodeTable[2]
    var sizes: u8[2048]

## Code one zigzag-ordered block after `predictor` into `out`, which has room for
## 64 symbols (at most 54 words).
func code_block(out: BitBuffer*, block: const i16*, predictor: i32, dc: const CodeTable*, ac: const CodeTable*, sizes: const u8*):
    var acc = out.acc
    var bits = out.bits
    var used = out.used
    let words = out.words.data
    # DC: the size category, then the difference's bits.
    let diff = (i32)block[0] - predictor
    let magnitude = diff if diff >= 0 else -diff
    let dc_size = (u32)sizes[(usize)magnitude]
    let dc_bits = (u64)(diff if diff >= 0 else diff - 1) & (((u64)1 << (u64)dc_size) - 1)
    let dc_length = (u32)dc.size[(usize)dc_size]
    acc = (acc << (u64)(dc_length + dc_size)) | ((u64)dc.code[(usize)dc_size] << (u64)dc_size) | dc_bits
    bits += dc_length + dc_size
    if bits >= 32:
        bits -= 32
        words[used] = (u32)(acc >> (u64)bits)
        used += 1
    # AC: walk the nonzero coefficients; the gaps are the runs.
    let quads = (const u64*)block
    var mask: u64 = 0
    for q in 0..<(usize)16:
        mask |= (u64)nonzero4(quads[q]) << (u64)(q * 4)
    mask &= ~(u64)1
    var last: usize = 0
    while mask != 0:
        let k = lowest64(mask)
        mask &= mask - 1
        var run = k - last - 1
        last = k
        while run > 15:
            acc = (acc << (u64)ac.size[240]) | (u64)ac.code[240]
            bits += (u32)ac.size[240]
            if bits >= 32:
                bits -= 32
                words[used] = (u32)(acc >> (u64)bits)
                used += 1
            run -= 16
        let value = (i32)block[k]
        let size = (u32)sizes[(usize)(value if value >= 0 else -value)]
        let symbol = (run << 4) | (usize)size
        let length = (u32)ac.size[symbol]
        let extra = (u64)(value if value >= 0 else value - 1) & (((u64)1 << (u64)size) - 1)
        acc = (acc << (u64)(length + size)) | ((u64)ac.code[symbol] << (u64)size) | extra
        bits += length + size
        if bits >= 32:
            bits -= 32
            words[used] = (u32)(acc >> (u64)bits)
            used += 1
    if last != 63:
        acc = (acc << (u64)ac.size[0]) | (u64)ac.code[0]
        bits += (u32)ac.size[0]
        if bits >= 32:
            bits -= 32
            words[used] = (u32)(acc >> (u64)bits)
            used += 1
    out.acc = acc
    out.bits = bits
    out.used = used

## Count one block's symbols after `predictor` into `dc` and `ac`.
func count_block(block: const i16*, predictor: i32, dc: u32*, ac: u32*, sizes: const u8*):
    let diff = (i32)block[0] - predictor
    dc[(usize)sizes[(usize)(diff if diff >= 0 else -diff)]] += 1
    let quads = (const u64*)block
    var mask: u64 = 0
    for q in 0..<(usize)16:
        mask |= (u64)nonzero4(quads[q]) << (u64)(q * 4)
    mask &= ~(u64)1
    var last: usize = 0
    while mask != 0:
        let k = lowest64(mask)
        mask &= mask - 1
        var run = k - last - 1
        last = k
        while run > 15:
            ac[240] += 1
            run -= 16
        let value = (i32)block[k]
        ac[(run << 4) | (usize)sizes[(usize)(value if value >= 0 else -value)]] += 1
    if last != 63:
        ac[0] += 1

## The file writer: bits into bytes of `out`, with a 0 after every 0xFF.
struct Stuffer:
    var out: Buffer*
    var acc: u64
    var bits: u32

    ## `count` bits (at most 32) of `value`; the caller has reserved room.
    func put(value: u64, count: u32):
        var acc = (self.acc << (u64)count) | value
        var bits = self.bits + count
        let data = self.out.data.data
        var used = self.out.used
        while bits >= 8:
            bits -= 8
            let byte = (u8)(acc >> (u64)bits)
            data[used] = byte
            used += 1
            if byte == 255:
                data[used] = 0
                used += 1
        self.out.used = used
        self.acc = acc
        self.bits = bits

    ## Pad to a byte with ones.
    func align():
        if self.bits > 0:
            self.put(((u64)1 << (u64)(8 - self.bits)) - 1, 8 - self.bits)

    ## A band's stream: its words, then its unfinished last word.
    func append(band: const BitBuffer*):
        let words = band.words.data
        for i in 0..<band.used:
            self.put((u64)words[i], 32)
        if band.bits > 0:
            self.put(band.acc & (((u64)1 << (u64)band.bits) - 1), band.bits)