// Port of jxl-coding/src/prefix.rs: prefix code based on Brotli
///|
const MAX_PREFIX_BITS : Int32 = 15
///|
const MAX_TOPLEVEL_BITS : Int32 = 10
///|
/// A prefix code of one cluster (`prefix::Histogram`).
///
/// Entries are packed into an `Int`:
/// `symbol_or_offset | bits_or_mask << 16 | nested << 24`.
priv struct PrefixHistogram {
toplevel_bits : Int32
toplevel_mask : UInt32
toplevel_entries : FixedArray[Int32]
second_level_entries : FixedArray[Int32]
}
///|
fn prefix_entry(
nested : Bool,
bits_or_mask : Int32,
symbol_or_offset : Int32,
) -> Int32 {
(symbol_or_offset & 0xffff) |
((bits_or_mask & 0xff) << 16) |
(if nested { 1 << 24 } else { 0 })
}
///|
fn PrefixHistogram::with_code_lengths(
code_lengths : FixedArray[Int32],
) -> PrefixHistogram raise @bitstream.JxlError {
let syms_for_length : Array[Array[Int32]] = []
for sym, len in code_lengths {
if len > 0 {
while syms_for_length.length() < len {
syms_for_length.push([])
}
syms_for_length[len - 1].push(sym)
}
}
let num_lengths = syms_for_length.length()
let toplevel_bits = if num_lengths < MAX_TOPLEVEL_BITS {
num_lengths
} else {
MAX_TOPLEVEL_BITS
}
let toplevel_size = 1 << toplevel_bits
let entries = FixedArray::make(toplevel_size, 0)
let mut current_bits = 0
for idx in 0.. toplevel_size {
// Rust panics on the out-of-bounds slice here.
raise coding_error("InvalidPrefixHistogram")
}
for i in current_bits..<(current_bits + n) {
entries[i] = entry
}
current_bits += n
}
}
let second_level_entries : Array[Int32] = []
if toplevel_bits < num_lengths {
let mut remaining_entries : Array[Int32] = []
let mut remaining_entry_bits = 0
for idx in toplevel_bits..= toplevel_size {
// Rust panics on the out-of-bounds index here.
raise coding_error("InvalidPrefixHistogram")
}
entries[current_bits] = prefix_entry(
true,
chunk_size - 1,
second_level_entries.length(),
)
vec_reverse_bits(chunk[:], second_level_entries)
current_bits += 1
chunk = Array(capacity=chunk_size)
}
}
remaining_entries = chunk
remaining_entry_bits = chunk_size_bits
}
if !remaining_entries.is_empty() {
raise coding_error("InvalidPrefixHistogram")
}
}
if current_bits == toplevel_size {
let toplevel_entries : Array[Int32] = Array(capacity=toplevel_size)
vec_reverse_bits(entries[:], toplevel_entries)
{
toplevel_bits,
toplevel_mask: (toplevel_size - 1).reinterpret_as_uint(),
toplevel_entries: FixedArray::from_array(toplevel_entries),
second_level_entries: FixedArray::from_array(second_level_entries),
}
} else {
raise coding_error("InvalidPrefixHistogram")
}
}
///|
fn PrefixHistogram::with_single_symbol(symbol : Int32) -> PrefixHistogram {
{
toplevel_bits: 0,
toplevel_mask: 0,
toplevel_entries: [prefix_entry(false, 0, symbol)],
second_level_entries: [],
}
}
///|
fn PrefixHistogram::parse(
bitstream : @bitstream.Bitstream,
alphabet_size : Int32,
) -> PrefixHistogram raise @bitstream.JxlError {
if alphabet_size == 1 {
return PrefixHistogram::with_single_symbol(0)
}
if alphabet_size > 1 << MAX_PREFIX_BITS {
raise coding_error("PrefixSymbolTooLarge")
}
let hskip = bitstream.read_bits_int(2)
if hskip == 1 {
PrefixHistogram::parse_simple(bitstream, alphabet_size)
} else {
PrefixHistogram::parse_complex(bitstream, alphabet_size, hskip)
}
}
///|
fn PrefixHistogram::parse_simple(
bitstream : @bitstream.Bitstream,
alphabet_size : Int32,
) -> PrefixHistogram raise @bitstream.JxlError {
// alphabet_size.next_power_of_two().trailing_zeros()
let mut alphabet_bits = 0
while 1 << alphabet_bits < alphabet_size {
alphabet_bits += 1
}
let nsym = bitstream.read_bits_int(2) + 1
let syms = FixedArray::make(4, 0)
let lens = FixedArray::make(4, 0)
match nsym {
1 => {
let sym = bitstream.read_bits_int(alphabet_bits)
if sym >= alphabet_size {
raise coding_error("InvalidPrefixHistogram")
}
return PrefixHistogram::with_single_symbol(sym)
}
2 => {
syms[2] = bitstream.read_bits_int(alphabet_bits)
syms[3] = bitstream.read_bits_int(alphabet_bits)
lens[2] = 1
lens[3] = 1
}
3 => {
syms[1] = bitstream.read_bits_int(alphabet_bits)
syms[2] = bitstream.read_bits_int(alphabet_bits)
syms[3] = bitstream.read_bits_int(alphabet_bits)
lens[1] = 1
lens[2] = 2
lens[3] = 2
}
_ => {
for i in 0..<4 {
syms[i] = bitstream.read_bits_int(alphabet_bits)
}
let tree_selector = bitstream.read_bool()
if tree_selector {
lens[0] = 1
lens[1] = 2
lens[2] = 3
lens[3] = 3
} else {
lens[0] = 2
lens[1] = 2
lens[2] = 2
lens[3] = 2
}
}
}
let code_lengths = FixedArray::make(alphabet_size, 0)
for i in 0..<4 {
let sym = syms[i]
if sym < alphabet_size {
code_lengths[sym] = lens[i]
} else {
raise coding_error("InvalidPrefixHistogram")
}
}
PrefixHistogram::with_code_lengths(code_lengths)
}
///|
let code_length_order : FixedArray[Int32] = [
1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
]
///|
fn PrefixHistogram::parse_complex(
bitstream : @bitstream.Bitstream,
alphabet_size : Int32,
hskip : Int32,
) -> PrefixHistogram raise @bitstream.JxlError {
let code_length_code_lengths = FixedArray::make(18, 0)
let mut bitacc = 0
let mut nonzero_count = 0
let mut nonzero_sym = 0
for i in hskip..<18 {
let idx = code_length_order[i]
// Read single code length code.
let base = bitstream
.read_u32(
@bitstream.c(0),
@bitstream.c(4),
@bitstream.c(3),
@bitstream.c(8),
)
.reinterpret_as_int()
let len = if base == 8 {
if bitstream.read_bool() {
if bitstream.read_bool() {
// 1111
5
} else {
// 0111
1
}
} else {
// 011
2
}
} else {
base
}
code_length_code_lengths[idx] = len
if len != 0 {
nonzero_count += 1
nonzero_sym = idx
bitacc += 32 >> len
if bitacc == 32 {
break
} else if bitacc > 32 {
raise coding_error("InvalidPrefixHistogram")
}
}
}
let code_length_histogram = if nonzero_count == 1 {
PrefixHistogram::with_single_symbol(nonzero_sym)
} else if bitacc != 32 {
raise coding_error("InvalidPrefixHistogram")
} else {
PrefixHistogram::with_code_lengths(code_length_code_lengths)
}
let code_lengths = FixedArray::make(alphabet_size, 0)
let mut bitacc = 0
let mut prev_sym = 8
let mut last_nonzero_sym = 8
let mut last_repeat_count = 0
let mut repeat_count = 0
let mut repeat_sym = 0
for i in 0.. 0 {
code_lengths[i] = repeat_sym
repeat_count -= 1
} else {
let sym = code_length_histogram.read_symbol(bitstream) & 0xff
match sym {
0 => ()
16 => {
repeat_count = bitstream.peek_bits_prefilled(2).reinterpret_as_int() +
3
bitstream.consume_bits(2)
if prev_sym == 16 {
repeat_count += last_repeat_count * 3 - 8
last_repeat_count += repeat_count
} else {
last_repeat_count = repeat_count
}
repeat_sym = last_nonzero_sym
code_lengths[i] = repeat_sym
repeat_count -= 1
}
17 => {
repeat_count = bitstream.peek_bits_prefilled(3).reinterpret_as_int() +
3
bitstream.consume_bits(3)
if prev_sym == 17 {
repeat_count += last_repeat_count * 7 - 16
last_repeat_count += repeat_count
} else {
last_repeat_count = repeat_count
}
repeat_sym = 0
code_lengths[i] = repeat_sym
repeat_count -= 1
}
_ => {
// 1..=15
code_lengths[i] = sym
last_nonzero_sym = sym
}
}
prev_sym = sym
}
let len = code_lengths[i]
if len != 0 {
bitacc += 1 <<
(if len >= MAX_PREFIX_BITS { 0 } else { MAX_PREFIX_BITS - len })
if bitacc > 1 << MAX_PREFIX_BITS {
raise coding_error("PrefixSymbolTooLarge")
} else if bitacc == 1 << MAX_PREFIX_BITS && repeat_count == 0 {
break
}
}
}
if bitacc != 1 << MAX_PREFIX_BITS || repeat_count > 0 {
raise coding_error("InvalidPrefixHistogram")
}
PrefixHistogram::with_code_lengths(code_lengths)
}
///|
#inline
fn PrefixHistogram::read_symbol(
self : PrefixHistogram,
bitstream : @bitstream.Bitstream,
) -> Int32 raise @bitstream.JxlError {
let peeked = bitstream.peek_bits(MAX_PREFIX_BITS)
let toplevel_offset = (peeked & self.toplevel_mask).reinterpret_as_int()
let toplevel_entry = self.toplevel_entries[toplevel_offset]
if toplevel_entry >= 1 << 24 {
let chunk_offset = (peeked.reinterpret_as_int() >> self.toplevel_bits) &
((toplevel_entry >> 16) & 0xff)
let second_level_offset = (toplevel_entry & 0xffff) + chunk_offset
let second_level_entry = self.second_level_entries[second_level_offset]
bitstream.consume_bits((second_level_entry >> 16) & 0xff)
second_level_entry & 0xffff
} else {
bitstream.consume_bits((toplevel_entry >> 16) & 0xff)
toplevel_entry & 0xffff
}
}
///|
/// The single symbol if this code always emits one symbol without reading
/// bits, or -1.
fn PrefixHistogram::single_symbol(self : PrefixHistogram) -> Int32 {
if self.toplevel_entries.length() == 1 {
let e = self.toplevel_entries[0]
if e >> 16 == 0 {
return e & 0xffff
}
}
-1
}
///|
fn vec_reverse_bits(v : ArrayView[Int32], out : Array[Int32]) -> Unit {
let len = v.length()
// len is a power of two
let mut bits = 0
while 1 << bits < len {
bits += 1
}
for idx in 0..> b) & 1) << (bits - 1 - b))
}
out.push(v[rev_idx])
}
}