dymokomi/luce-compress
Source of release 0.9.1
0.9.1 / src / brotli / prefix.lucb
#==============================================================================================
#
# brotli/prefix - Prefix codes: reading them, and their lookup tables (RFC 7932 section 3)
#
# DESCRIPTION:
# A code decodes through a table indexed by the next 8 bits: an entry is the symbol
# and its code's length, or for longer codes a link to a second-level table of up
# to 7 more bits, stored after the root. A code's tables go into the meta-block's
# one growable array of tables (`trees`); a code is known by its offset there.
# Reading a code is resumable: a simple code is one unit, a complex code one unit
# per code length code length and one per code length (with its extra bits).
#
#==============================================================================================
## Entries one code's table may need at most: a full root of 256 and 256 second-level
## tables of 128 (a complete code never needs as many).
let tree_room: usize = 256 + 256 * 128
# mark: Lookup tables =========================================================================
## The bit-reversed canonical code after `key`, a code of `length` bits (the table index
## of the next code, read least significant bit first); 0 after the last.
func next_key(key: u32, length: u32) -> u32:
var step: u32 = (u32)1 << (length - 1)
while key & step != 0:
step >>= 1
if step == 0:
return 0
return (key & (step - 1)) + step
## Bits of the second-level table for codes starting at `length` past the root, from the
## codes of each length not yet placed (`count`).
func table_bits(length: u32, root: u32, count: const u16*) -> u32:
var bits = length - root
var left: i32 = (i32)1 << bits
while bits + root < 15:
left -= (i32)count[(usize)(bits + root)]
if left <= 0:
break
bits += 1
left <<= 1
return bits
## Fill `table` with the complete canonical code whose symbols, ordered by code length and
## then value, are `sorted`, `count[n]` of them of length n; a root of `root` bits. The
## entries used, root included. `count` is consumed.
func build_table(table: u32*, root: u32, sorted: const u16*, count: u16*) -> usize:
let size = (usize)1 << root
var key: u32 = 0
var at: usize = 0
for length in 1..<root + 1:
while count[(usize)length] > 0:
let entry = ((u32)sorted[at] << 16) | length
var slot = (usize)key
while slot < size:
table[slot] = entry
slot += (usize)1 << length
key = next_key(key, length)
at += 1
count[(usize)length] -= 1
var used = size
var prefix: u32 = 0xFFFFFFFF
var start: usize = 0
var bits: u32 = 0
for length in root + 1..<(u32)16:
while count[(usize)length] > 0:
let low = key & (u32)(size - 1)
if low != prefix:
bits = table_bits(length, root, count)
start = used
used += (usize)1 << bits
table[(usize)low] = ((u32)start << 16) | (root + bits)
prefix = low
let entry = ((u32)sorted[at] << 16) | (length - root)
var slot = (usize)(key >> root)
while slot < (usize)1 << bits:
table[start + slot] = entry
slot += (usize)1 << (length - root)
key = next_key(key, length)
at += 1
count[(usize)length] -= 1
return used
## Fill `table` from per-symbol code lengths (0 for an unused symbol) of a complete code.
func build_lengths(table: u32*, root: u32, lengths: const u8[]) -> usize:
var count: u16[16]
for length in lengths:
count[(usize)length] += 1
count[0] = 0
var offsets: u16[16]
for n in 1..<(usize)15:
offsets[n + 1] = offsets[n] + count[n]
var sorted: u16[704]
for i in 0..<lengths.length:
let length = (usize)lengths[i]
if length != 0:
sorted[(usize)offsets[length]] = (u16)i
offsets[length] += 1
return build_table(table, root, &sorted[0], &count[0])
## Fill `table` (a 256-entry root) with a code of one symbol and no bits.
func build_single(table: u32*, symbol: u32) -> usize:
for i in 0..<(usize)256:
table[i] = symbol << 16
return 256
## Bits needed to write any symbol below `alphabet` (at least 2 symbols).
func alphabet_bits(alphabet: u32) -> u32:
var bits: u32 = 0
var n = alphabet - 1
while n != 0:
bits += 1
n >>= 1
return bits
# mark: Reading codes =========================================================================
let code_kind: u32 = 0
let code_length_lengths: u32 = 1
let code_symbol_lengths: u32 = 2
extend Decoder:
## Room for one more code's table in `trees`, grown when needed; a pointer valid until
## the next call.
func tree_space() -> u32*!:
if self.trees_used + tree_room > self.trees.length:
var capacity = self.trees.length * 2
if capacity < self.trees_used + tree_room:
capacity = self.trees_used + tree_room
let grown = try new u32[capacity] --- in memory.heap
if self.trees_used > 0:
memory.copy(grown, self.trees[..<self.trees_used], self.trees_used)
if self.trees.length > 0:
free(self.trees) in memory.heap
self.trees = grown
return self.trees.data + self.trees_used
## Read a prefix code over `alphabet` symbols into `trees`; its offset, or none when
## the input ran out (call again with more).
func read_code(alphabet: u32) -> u32?!:
if self.code_stage == code_kind:
let table = try self.tree_space()
let bits = alphabet_bits(alphabet)
self.begin(5 + 4 * bits)
let kind = self.take(2)
if kind != 1:
if try self.short():
return none
self.code_stage = code_length_lengths
self.code_index = kind
self.code_space = 32
self.code_count = 0
for i in 0..<(usize)18:
self.code_lengths[i] = 0
else:
let count = self.take(2) + 1
var symbols: u16[4]
for i in 0..<(usize)count:
symbols[i] = (u16)self.take(bits)
let select = self.take(1) if count == 4 else 0
if try self.short():
return none
for i in 0..<(usize)count:
if (u32)symbols[i] >= alphabet:
error(corrupt, "brotli prefix code symbol is out of range")
for j in 0..<i:
if symbols[i] == symbols[j]:
error(corrupt, "brotli prefix code repeats a symbol")
let offset = (u32)self.trees_used
self.trees_used += build_simple(table, symbols, count, select)
return offset
if self.code_stage == code_length_lengths:
while self.code_index < 18:
self.begin(4)
let peek = (usize)(self.acc & 15)
_ = self.take((u32)length_bits[peek])
if try self.short():
return none
let value = length_value[peek]
self.code_lengths[(usize)length_order[(usize)self.code_index]] = value
self.code_index += 1
if value != 0:
self.code_space -= (i32)32 >> (i32)value
self.code_count += 1
if self.code_space <= 0:
break
if self.code_count != 1 and self.code_space != 0:
error(corrupt, "invalid brotli code length code")
if self.code_count == 1:
for i in 0..<(usize)18:
if self.code_lengths[i] != 0:
for k in 0..<(usize)32:
self.code_table[k] = (u32)i << 16
else:
_ = build_lengths(&self.code_table[0], 5, self.code_lengths)
self.code_stage = code_symbol_lengths
self.code_index = 0
self.code_space = 32768
self.previous_length = 8
self.repeat = 0
self.repeat_length = 0
for i in 0..<(usize)alphabet:
self.lengths[i] = 0
while self.code_index < alphabet and self.code_space > 0:
self.begin(8)
let entry = self.code_table[(usize)(self.acc & 31)]
_ = self.take(entry & 255)
let code = entry >> 16
let extra = self.take(2) if code == 16 else self.take(3) if code == 17 else 0
if try self.short():
return none
if code < 16:
self.repeat = 0
self.lengths[(usize)self.code_index] = (u8)code
self.code_index += 1
if code != 0:
self.previous_length = code
self.code_space -= (i32)32768 >> (i32)code
continue
# A repeat: of the last nonzero length (16) or of zero (17); a repeat right
# after one of the same kind extends it.
let length = self.previous_length if code == 16 else 0
let shift: u32 = 2 if code == 16 else 3
if self.repeat_length != length:
self.repeat = 0
self.repeat_length = length
let before = self.repeat
if self.repeat > 0:
self.repeat = (self.repeat - 2) << shift
self.repeat += extra + 3
let added = self.repeat - before
if added > alphabet - self.code_index:
error(corrupt, "brotli code length repeat overruns the alphabet")
for i in 0..<(usize)added:
self.lengths[(usize)self.code_index + i] = (u8)length
self.code_index += added
if length != 0:
self.code_space -= (i32)(added << (15 - length))
if self.code_space != 0:
error(corrupt, "invalid brotli prefix code")
self.code_stage = code_kind
let table = try self.tree_space()
let offset = (u32)self.trees_used
self.trees_used += build_lengths(table, 8, self.lengths[..<(usize)alphabet])
return offset
## Fill `table` with a simple code (section 3.4): `count` distinct symbols; with four,
## `select` picks lengths 2, 2, 2, 2 (0) or 1, 2, 3, 3 (1).
func build_simple(table: u32*, symbols: u16[4], count: u32, select: u32) -> usize:
if count == 1:
return build_single(table, (u32)symbols[0])
var sorted = symbols
var lengths: u16[16]
# Symbols of one length are sorted; the lengths follow the listed order.
var sorted_from: usize = 0
if count == 2 or (count == 4 and select == 0):
lengths[(usize)(1 if count == 2 else 2)] = (u16)count
elif count == 3:
lengths[1] = 1
lengths[2] = 2
sorted_from = 1
else:
lengths[1] = 1
lengths[2] = 1
lengths[3] = 2
sorted_from = 2
for i in sorted_from..<(usize)count:
for j in i + 1..<(usize)count:
if sorted[j] < sorted[i]:
let swap = sorted[i]
sorted[i] = sorted[j]
sorted[j] = swap
return build_table(table, 8, &sorted[0], &lengths[0])