Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-webp

Source of release 0.1.0

0.1.0 / src / webp / vp8l_huffman.lucb

#==============================================================================================
#
#   webp/vp8l_huffman - Huffman tables and groups
#
#   DESCRIPTION:
#       Port of utils/huffman_utils.c (BuildHuffmanTable: two-level lookup tables, eight
#       bits at the root) and of the code reading of dec/vp8l_dec.c (ReadHuffmanCode,
#       ReadHuffmanCodeLengths, ReadHuffmanCodesHelper, BuildPackedTable, ReadSymbol).
#       A group holds five codes: green with the length prefixes and the color cache,
#       red, blue, alpha, and the distance prefixes. A group whose red, blue and alpha
#       codes have one symbol each is a trivial literal; one whose green code has a single
#       literal too is a trivial code, decoded without reading a bit; one whose literal
#       codes are short together gets a packed table that reads a whole pixel at once.
#
#       libwebp keeps its tables in chained segments; here they are one array, grown when
#       a group's tables would not fit, the groups holding offsets into it.
#
#==============================================================================================

## Root table bits for the five codes and for the code length code (HUFFMAN_TABLE_BITS,
## LENGTHS_TABLE_BITS).
let huffman_table_bits: u32 = 8
let huffman_table_mask: u32 = 0xff
let lengths_table_bits: u32 = 7
let lengths_table_mask: u32 = 0x7f
let max_allowed_code_length: usize = 15
## The packed table's bits (HUFFMAN_PACKED_BITS) and the mark of an entry that is not a
## literal (BITS_SPECIAL_MARKER).
let huffman_packed_bits: u32 = 6
let bits_special_marker: i32 = 0x100

## The alphabets: 256 literals, 24 length prefixes, 40 distance prefixes.
let num_literal_codes: u32 = 256
let num_length_codes: u32 = 24
let num_distance_codes: u32 = 40
let huffman_codes_per_meta_code: usize = 5
let max_cache_bits: u32 = 11
## The codes of a group (HuffIndex).
let huff_green: usize = 0
let huff_red: usize = 1
let huff_blue: usize = 2
let huff_alpha: usize = 3
let huff_dist: usize = 4
let alphabet_sizes: u32[5] = [280, 256, 256, 256, 40]
let literal_map: bool[5] = [false, true, true, true, false]

## The code length code's order (kCodeLengthCodeOrder), and its repeat codes.
let code_length_code_order: u8[19] = [17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
let num_code_length_codes: usize = 19
let code_length_literals: u32 = 16
let code_length_repeat_code: u32 = 16
let code_length_extra_bits: u8[3] = [2, 3, 7]
let code_length_repeat_offsets: u8[3] = [3, 3, 11]
let default_code_length: i32 = 8

## The table entries a group's codes need at most, by color cache bits (kTableSize).
let table_sizes: u16[12] = [2954, 2956, 2958, 2962, 2970, 2986, 3018, 3082, 3212, 3468, 3980, 5004]

# mark: Tables ================================================================================

## A lookup table entry: the bits of the symbol, or of the second level's table; the
## symbol, or the offset of the second level's table (HuffmanCode).
struct HuffmanCode:
    var bits: u8
    var value: u16

## A packed table entry: a whole literal pixel and its bits, or a non-literal symbol with
## its bits plus the special marker (HuffmanCode32).
struct HuffmanCode32:
    var bits: i32
    var value: u32

## The tables of every group, in one array.
struct HuffmanTables:
    var codes: HuffmanCode[]
    var used: usize

    func release():
        if self.codes.length > 0:
            free(self.codes) in memory.heap
        var empty: HuffmanCode[]
        self.codes = empty
        self.used = 0

## A group's five codes (HTreeGroup).
struct TreeGroup:
    ## Each code's table, as an offset into the tables.
    var htrees: usize[5]
    var is_trivial_literal: bool
    ## The red, blue and alpha of a trivial literal, green zero.
    var literal_arb: u32
    var is_trivial_code: bool
    var use_packed_table: bool
    var packed_table: HuffmanCode32[64]

## GetNextKey: reverse(reverse(key, len) + 1, len).
inline func get_next_key(key: u32, len: usize) -> u32:
    var step = (u32)1 << (u32)(len - 1)
    while (key & step) != 0:
        step >>= 1
    return (key & (step - 1)) + step if step != 0 else key

## ReplicateValue: `code` into table[0], table[step], ..., below `end`.
inline func replicate_value(table: HuffmanCode*, step: usize, end: usize, code: HuffmanCode):
    var at = end
    while true:
        at -= step
        table[at] = code
        if at == 0:
            return

## NextTableBitSize: the width of the next second-level table.
func next_table_bit_size(count: const i32*, len: usize, root_bits: usize) -> usize:
    var length = len
    var left = (i32)1 << (u32)(length - root_bits)
    while length < max_allowed_code_length:
        left -= count[length]
        if left <= 0:
            break
        length += 1
        left <<= 1
    return length - root_bits

## BuildHuffmanTable: the table of `code_lengths` at `root_table` (or, without one, only
## its size), the symbols sorted by length into `sorted`. Returns its size, 0 when the
## lengths are not a valid code.
func build_huffman_table(root_table: HuffmanCode*?, root_bits: usize, code_lengths: const i32[], sorted: u16*?) -> usize:
    let code_lengths_size = code_lengths.length
    var total_size = (usize)1 << (u32)root_bits
    var count: i32[16]
    var offset: i32[16]
    # The histogram of code lengths.
    for symbol in 0..<code_lengths_size:
        if code_lengths[symbol] > (i32)max_allowed_code_length:
            return 0
        count[(usize)code_lengths[symbol]] += 1
    # All code lengths zero.
    if (usize)count[0] == code_lengths_size:
        return 0
    # The offsets of each length in the sorted symbols.
    offset[1] = 0
    for len in 1..<max_allowed_code_length:
        if count[len] > (i32)1 << (u32)len:
            return 0
        offset[len + 1] = offset[len] + count[len]
    # The symbols sorted by length, by symbol within a length.
    for symbol in 0..<code_lengths_size:
        let symbol_code_length = (usize)code_lengths[symbol]
        if symbol_code_length > 0:
            if let into = sorted:
                if (usize)offset[symbol_code_length] >= code_lengths_size:
                    return 0
                into[(usize)offset[symbol_code_length]] = (u16)symbol
            offset[symbol_code_length] += 1
    # A code of one symbol.
    if offset[max_allowed_code_length] == 1:
        if let table = root_table:
            let into = sorted else trap("a table is built with its sorted symbols")
            replicate_value(table, 1, total_size, HuffmanCode(bits = 0, value = into[0]))
        return total_size
    var low: u32 = 0xffffffff
    let mask = (u32)total_size - 1
    var key: u32 = 0
    var num_nodes: i32 = 1
    var num_open: i32 = 1
    var table_bits = root_bits
    var table_size = (usize)1 << (u32)table_bits
    var symbol: usize = 0
    var table_at: usize = 0
    # The root table.
    var step: usize = 2
    for len in 1..<root_bits + 1:
        num_open <<= 1
        num_nodes += num_open
        num_open -= count[len]
        if num_open < 0:
            return 0
        if let table = root_table:
            let into = sorted else trap("a table is built with its sorted symbols")
            while count[len] > 0:
                replicate_value(table + (usize)key, step, table_size, HuffmanCode(bits = (u8)len, value = into[symbol]))
                symbol += 1
                key = get_next_key(key, len)
                count[len] -= 1
        step <<= 1
    # The second level tables, and their entries in the root table.
    step = 2
    for len in root_bits + 1..<max_allowed_code_length + 1:
        num_open <<= 1
        num_nodes += num_open
        num_open -= count[len]
        if num_open < 0:
            return 0
        while count[len] > 0:
            if (key & mask) != low:
                table_at += table_size
                table_bits = next_table_bit_size(&count[0], len, root_bits)
                table_size = (usize)1 << (u32)table_bits
                total_size += table_size
                low = key & mask
                if let table = root_table:
                    table[(usize)low] = HuffmanCode(bits = (u8)(table_bits + root_bits), value = (u16)(table_at - (usize)low))
            if let table = root_table:
                let into = sorted else trap("a table is built with its sorted symbols")
                replicate_value(table + table_at + (usize)(key >> (u32)root_bits), step, table_size, HuffmanCode(bits = (u8)(len - root_bits), value = into[symbol]))
                symbol += 1
            key = get_next_key(key, len)
            count[len] -= 1
        step <<= 1
    # The tree must be full.
    if num_nodes != 2 * offset[max_allowed_code_length] - 1:
        return 0
    return total_size

## VP8LBuildHuffmanTable: the table of `code_lengths` at the end of `tables` (grown when
## it does not fit), or its size alone without `tables`. 0 when the code is invalid.
func add_huffman_table(tables: HuffmanTables*?, root_bits: usize, code_lengths: const i32[]) -> usize!:
    let total_size = build_huffman_table(none, root_bits, code_lengths, none)
    let into = tables else return total_size
    if total_size == 0:
        return 0
    if into.used + total_size > into.codes.length:
        let larger = try new HuffmanCode[into.used + total_size + into.codes.length] in memory.heap
        memory.copy(larger, into.codes, into.used)
        into.release()
        into.codes = larger
    let sorted = try new u16[code_lengths.length] --- in memory.heap
    defer free(sorted) in memory.heap
    _ = build_huffman_table(into.codes.data + into.used, root_bits, code_lengths, sorted.data)
    return total_size

# mark: Reading codes =========================================================================

## ReadSymbol: the next symbol of the code at `table`. The bit window must hold enough bits.
inline func read_symbol(table: const HuffmanCode*, br: LosslessBits*) -> u32:
    var val = br.prefetch_bits()
    var entry = table + (usize)(val & huffman_table_mask)
    let nbits = (u32)entry[0].bits
    if nbits > huffman_table_bits:
        br.bit_pos = br.bit_pos +% huffman_table_bits
        val = br.prefetch_bits()
        entry = entry + (usize)entry[0].value
        entry = entry + (usize)(val & ((((u32)1 << ((nbits -% huffman_table_bits) & 31)) -% 1)))
    br.bit_pos = br.bit_pos +% (u32)entry[0].bits
    return (u32)entry[0].value

## ReadHuffmanCodeLengths: the code lengths of `code_lengths.length` symbols, coded with
## the code length code.
func read_huffman_code_lengths(br: LosslessBits*, code_length_code_lengths: const i32[], code_lengths: i32[]) -> !:
    let num_symbols = code_lengths.length
    var table: HuffmanCode[128]
    var sorted: u16[19]
    if build_huffman_table(&table[0], (usize)lengths_table_bits, code_length_code_lengths, &sorted[0]) == 0:
        error(corrupt, "VP8L code length code is invalid")
    var max_symbol = num_symbols
    if br.read_bits(1) != 0:
        # The number of symbols coded.
        let length_nbits = 2 + 2 * br.read_bits(3)
        max_symbol = 2 + (usize)br.read_bits(length_nbits)
        if max_symbol > num_symbols:
            error(corrupt, "VP8L code lengths are too many")
    var symbol: usize = 0
    var prev_code_len = default_code_length
    while symbol < num_symbols:
        if max_symbol == 0:
            break
        max_symbol -= 1
        br.fill_bit_window()
        let p = table[(usize)(br.prefetch_bits() & lengths_table_mask)]
        br.bit_pos += (u32)p.bits
        let code_len = (u32)p.value
        if code_len < code_length_literals:
            code_lengths[symbol] = (i32)code_len
            symbol += 1
            if code_len != 0:
                prev_code_len = (i32)code_len
        else:
            let use_prev = code_len == code_length_repeat_code
            let slot = (usize)(code_len - code_length_literals)
            let extra_bits = (u32)code_length_extra_bits[slot]
            let repeat_offset = (usize)code_length_repeat_offsets[slot]
            let repeat = (usize)br.read_bits(extra_bits) + repeat_offset
            if symbol + repeat > num_symbols:
                error(corrupt, "VP8L code length repeat runs past the alphabet")
            let length = prev_code_len if use_prev else 0
            for i in 0..<repeat:
                code_lengths[symbol + i] = length
            symbol += repeat

## ReadHuffmanCode: one code of `alphabet_size` symbols into `tables` (or only checked,
## without), its lengths left in `code_lengths`. Returns the table's size.
func read_huffman_code(br: LosslessBits*, alphabet_size: usize, code_lengths: i32[], tables: HuffmanTables*?) -> usize!:
    let lengths = code_lengths[..<alphabet_size]
    memory.set(u8[]((u8*)lengths.data, alphabet_size * 4), 0)
    if br.read_bits(1) != 0:
        # A simple code: one or two symbols, given directly, of length 1. A symbol past the
        # alphabet lands in the rest of the buffer, outside the code, as in libwebp.
        let num_symbols = br.read_bits(1) + 1
        let first_symbol_len_code = br.read_bits(1)
        # The first symbol has 1 or 8 bits, the second 8.
        let first = br.read_bits(1 if first_symbol_len_code == 0 else 8)
        code_lengths[(usize)first] = 1
        if num_symbols == 2:
            code_lengths[(usize)br.read_bits(8)] = 1
    else:
        # Code lengths, Huffman-coded.
        var code_length_code_lengths: i32[19]
        let num_codes = (usize)br.read_bits(4) + 4
        for i in 0..<num_codes:
            code_length_code_lengths[(usize)code_length_code_order[i]] = (i32)br.read_bits(3)
        try read_huffman_code_lengths(br, code_length_code_lengths, lengths)
    if br.eos:
        error(corrupt, "VP8L data ends in a Huffman code")
    let size = try add_huffman_table(tables, (usize)huffman_table_bits, lengths)
    if size == 0:
        error(corrupt, "VP8L Huffman code is invalid")
    return size

## AccumulateHCode: one code's entry added to a packed entry, its bits used.
inline func accumulate_hcode(hcode: HuffmanCode, shift: u32, huff: HuffmanCode32*) -> u32:
    huff.bits += (i32)hcode.bits
    huff.value |= (u32)hcode.value << shift
    return (u32)hcode.bits

## BuildPackedTable: every six-bit prefix to a whole literal pixel, or to a non-literal
## green symbol.
func build_packed_table(group: TreeGroup*, codes: const HuffmanCode*):
    for code in 0..<(u32)64:
        var bits = code
        let huff = &group.packed_table[(usize)code]
        let hcode = codes[group.htrees[huff_green] + (usize)bits]
        if (u32)hcode.value >= num_literal_codes:
            huff.bits = (i32)hcode.bits + bits_special_marker
            huff.value = (u32)hcode.value
        else:
            huff.bits = 0
            huff.value = 0
            bits >>= accumulate_hcode(hcode, 8, huff)
            bits >>= accumulate_hcode(codes[group.htrees[huff_red] + (usize)bits], 16, huff)
            bits >>= accumulate_hcode(codes[group.htrees[huff_blue] + (usize)bits], 0, huff)
            bits >>= accumulate_hcode(codes[group.htrees[huff_alpha] + (usize)bits], 24, huff)

## ReadHuffmanCodesHelper: the groups' codes. With a `mapping`, `num_htree_groups_max`
## groups are read and those the Huffman image does not use (-1) only checked.
func read_huffman_codes_helper(br: LosslessBits*, color_cache_bits: u32, num_htree_groups: usize, num_htree_groups_max: usize, mapping: const i32[], tables: HuffmanTables*, groups: TreeGroup[]) -> !:
    let max_alphabet_size = (usize)alphabet_sizes[0] + ((usize)1 << color_cache_bits if color_cache_bits > 0 else 0)
    let table_size = (usize)table_sizes[(usize)color_cache_bits]
    if (mapping.length == 0 and num_htree_groups != num_htree_groups_max) or num_htree_groups > num_htree_groups_max:
        error(corrupt, "VP8L Huffman groups are inconsistent")
    let code_lengths = try new i32[max_alphabet_size] in memory.heap
    defer free(code_lengths) in memory.heap
    tables.codes = try new HuffmanCode[num_htree_groups * table_size] in memory.heap
    for i in 0..<num_htree_groups_max:
        if mapping.length > 0 and mapping[i] == -1:
            # Unused by the Huffman image: checked, not kept.
            for j in 0..<huffman_codes_per_meta_code:
                var alphabet_size = (usize)alphabet_sizes[j]
                if j == 0 and color_cache_bits > 0:
                    alphabet_size += (usize)1 << color_cache_bits
                _ = try read_huffman_code(br, alphabet_size, code_lengths, none)
            continue
        let group = &groups[i if mapping.length == 0 else (usize)mapping[i]]
        var total_size: u32 = 0
        var is_trivial_literal = true
        var max_bits: i32 = 0
        for j in 0..<huffman_codes_per_meta_code:
            var alphabet_size = (usize)alphabet_sizes[j]
            if j == 0 and color_cache_bits > 0:
                alphabet_size += (usize)1 << color_cache_bits
            let at = tables.used
            let size = try read_huffman_code(br, alphabet_size, code_lengths, tables)
            group.htrees[j] = at
            let first = tables.codes[at]
            if is_trivial_literal and literal_map[j]:
                is_trivial_literal = first.bits == 0
            total_size += (u32)first.bits
            tables.used += size
            if j <= huff_alpha:
                var local_max_bits = code_lengths[0]
                for k in 1..<alphabet_size:
                    if code_lengths[k] > local_max_bits:
                        local_max_bits = code_lengths[k]
                max_bits += local_max_bits
        group.is_trivial_literal = is_trivial_literal
        group.is_trivial_code = false
        if is_trivial_literal:
            let red_value = (u32)tables.codes[group.htrees[huff_red]].value
            let blue_value = (u32)tables.codes[group.htrees[huff_blue]].value
            let alpha_value = (u32)tables.codes[group.htrees[huff_alpha]].value
            group.literal_arb = (alpha_value << 24) | (red_value << 16) | blue_value
            let green_value = (u32)tables.codes[group.htrees[huff_green]].value
            if total_size == 0 and green_value < num_literal_codes:
                group.is_trivial_code = true
                group.literal_arb |= green_value << 8
        group.use_packed_table = not group.is_trivial_code and max_bits < (i32)huffman_packed_bits
        if group.use_packed_table:
            build_packed_table(group, tables.codes.data)