///|
/// Meta-adaptive tree configuration.
///
/// Meta-adaptive (MA) tree is a decision tree that controls how the sample is
/// decoded in the given context. The configuration consists of two
/// components: the MA tree itself, and the distribution information of an
/// entropy decoder. These components are read from the bitstream.
pub struct MaConfig {
priv num_tree_nodes : Int32
priv tree_depth : Int32
priv tree : MaTreeNode
priv decoder : @coding.Decoder
}
///|
/// Returns the entropy decoder.
///
/// The decoder should be cloned to be used for decoding.
pub fn MaConfig::decoder(self : MaConfig) -> @coding.Decoder {
self.decoder
}
///|
/// Creates a simplified MA tree with given channel index and stream index,
/// which then can be used to decode samples.
///
/// The method will evaluate the tree with the given information and prune
/// branches which are always not taken.
pub fn MaConfig::make_flat_tree(
self : MaConfig,
channel : Int32,
stream_idx : Int32,
prev_channels : Int32,
) -> FlatMaTree {
let nodes = self.tree.flatten(channel, stream_idx, prev_channels)
FlatMaTree::new(nodes)
}
///|
/// Returns the number of MA tree nodes.
pub fn MaConfig::num_tree_nodes(self : MaConfig) -> Int32 {
self.num_tree_nodes
}
///|
/// Returns the maximum distance from root to any leaf node.
pub fn MaConfig::tree_depth(self : MaConfig) -> Int32 {
self.tree_depth
}
///|
/// Parameters for decoding `MaConfig`.
pub(all) struct MaConfigParams {
/// Allocation tracker.
tracker : @grid.AllocTracker?
/// Maximum number of meta-adaptive tree nodes.
node_limit : Int32
depth_limit : Int32
}
///|
priv enum FoldingTree {
Decision(Int32, Int32)
Leaf(Int32, Predictor, Int32, Int32)
}
///|
/// Size of a `FoldingTree` in upstream, used for allocation tracking.
const FOLDING_TREE_SIZE = 16
///|
/// Saturates a `u32` to `Int`; property ids above `i32::MAX` behave the same
/// as `i32::MAX` (a previous-channel property that is always pruned).
fn u32_to_property(v : UInt32) -> Int32 {
if v > 0x7fffffffU {
0x7fffffff
} else {
v.reinterpret_as_int()
}
}
///|
pub fn MaConfig::parse(
bs : @bitstream.Bitstream,
params : MaConfigParams,
) -> MaConfig raise @bitstream.JxlError {
let { tracker, node_limit, depth_limit, } = params
let tree_decoder = @coding.Decoder::parse(bs, 6)
if is_infinite_tree_dist(tree_decoder) {
raise modular_error("InvalidMaTree")
}
let mut ctx = 0
let mut nodes_left = 1
// Allocation tracking mirrors upstream's growing temporary buffer.
let mut tmp_alloc = 0
if tracker is Some(t) {
t.alloc(16, FOLDING_TREE_SIZE)
tmp_alloc = 16
}
let mut capacity = 16
let nodes : Array[FoldingTree] = Array(capacity=16)
let mut max_depth = 1
defer (if tracker is Some(t) { t.free(tmp_alloc, FOLDING_TREE_SIZE) })
tree_decoder.begin(bs)
while nodes_left > 0 {
if nodes.length() >= 1 << 26 {
raise modular_error("InvalidMaTree")
}
if nodes.length() > node_limit {
raise @bitstream.ProfileConformance("MA tree limit exceeded")
}
if nodes.length() == capacity && tracker is Some(t) {
let current_len = nodes.length()
t.free(tmp_alloc, FOLDING_TREE_SIZE)
tmp_alloc = 0
let new_cap = if current_len <= 16 {
256
} else if current_len <= 256 {
1024
} else {
current_len * 2
}
t.alloc(new_cap, FOLDING_TREE_SIZE)
tmp_alloc = new_cap
capacity = new_cap
}
nodes_left -= 1
let property = tree_decoder.read_varint(bs, 1)
let node = if property != 0 {
let value = @bitstream.unpack_signed(tree_decoder.read_varint(bs, 0))
nodes_left += 2
FoldingTree::Decision(u32_to_property(property - 1), value)
} else {
let predictor = Predictor::try_from(tree_decoder.read_varint(bs, 2))
let offset = @bitstream.unpack_signed(tree_decoder.read_varint(bs, 3))
let mul_log = tree_decoder.read_varint(bs, 4)
if mul_log > 30 {
raise modular_error("InvalidMaTree")
}
let mul_log = mul_log.reinterpret_as_int()
let mul_bits = tree_decoder.read_varint(bs, 5)
if mul_bits > (1U << (31 - mul_log)) - 2 {
raise modular_error("InvalidMaTree")
}
let multiplier = ((mul_bits + 1) << mul_log).reinterpret_as_int()
let node = FoldingTree::Leaf(ctx, predictor, offset, multiplier)
ctx += 1
node
}
nodes.push(node)
if nodes_left > max_depth {
max_depth = nodes_left
}
}
tree_decoder.finalize()
let num_tree_nodes = nodes.length()
let decoder = @coding.Decoder::parse(bs, ctx)
let cluster_map = decoder.cluster_map()
if tracker is Some(t) {
t.alloc(nodes.length(), FOLDING_TREE_SIZE)
}
// A queue: push to the back, pop from the front.
let tmp : Array[(MaTreeNode, Int32)] = Array(capacity=nodes.length())
let mut head = 0
for i = nodes.length() - 1; i >= 0; i = i - 1 {
match nodes[i] {
Decision(property, value) => {
let (right, dr) = tmp[head]
let (left, dl) = tmp[head + 1]
head += 2
let node = MaTreeNode::Decision(property~, value~, left~, right~)
let depth = (if dr > dl { dr } else { dl }) + 1
if depth > depth_limit {
raise @bitstream.ProfileConformance("decoded MA tree is too deep")
}
tmp.push((node, depth))
}
Leaf(ctx, predictor, offset, multiplier) => {
let cluster = cluster_map[ctx]
let leaf = { cluster, predictor, offset, multiplier, }
tmp.push((MaTreeNode::Leaf(leaf), 0))
}
}
}
guard tmp.length() - head == 1 else { abort("assertion failed") }
let (tree, tree_depth) = tmp[head]
{ num_tree_nodes, tree_depth, tree, decoder, }
}
///|
fn is_infinite_tree_dist(decoder : @coding.Decoder) -> Bool {
let cluster_map = decoder.cluster_map()
// Distribution #1 decides whether it's decision node or leaf node; if it
// reads 0 it's a leaf node. Therefore, the tree is infinitely large if the
// dist always reads token other than 0.
let cluster = cluster_map[1]
match decoder.single_token(cluster) {
None => false
Some(token) => token != 0
}
}
///|
/// A "flat" meta-adaptive tree, constructed with `MaConfig::make_flat_tree`.
pub struct FlatMaTree {
priv nodes : Array[FlatMaTreeNode]
priv need_self_correcting : Bool
priv max_prev_channel_depth : Int32
}
///|
priv enum FlatMaTreeNode {
FusedDecision(
prop_level0~ : Int32,
value_level0~ : Int32,
prop_l~ : Int32,
prop_r~ : Int32,
value_l~ : Int32,
value_r~ : Int32,
index_base~ : Int32
)
Table(prop~ : Int32, value_base~ : Int32, indices~ : FixedArray[Int32])
Leaf(MaTreeLeafClustered)
}
///|
#derive(Debug, Eq)
pub(all) struct MaTreeLeafClustered {
cluster : Int32
predictor : Predictor
offset : Int32
/// `u32` in upstream; always below `2^31`.
multiplier : Int32
}
///|
fn prev_channel_depth(p : Int32) -> Int32 {
if p >= 16 {
(p - 16) / 4 + 1
} else {
0
}
}
///|
fn FlatMaTree::new(nodes : Array[FlatMaTreeNode]) -> FlatMaTree {
let mut need_self_correcting = false
let mut max_prev_channel_depth = 0
for node in nodes {
match node {
FusedDecision(prop_level0=p, prop_l=pl, prop_r=pr, ..) => {
if p == 15 || pl == 15 || pr == 15 {
need_self_correcting = true
}
for q in [p, pl, pr] {
let d = prev_channel_depth(q)
if d > max_prev_channel_depth {
max_prev_channel_depth = d
}
}
}
Table(prop~, ..) => {
if prop == 15 {
need_self_correcting = true
}
let d = prev_channel_depth(prop)
if d > max_prev_channel_depth {
max_prev_channel_depth = d
}
}
Leaf(leaf) =>
if leaf.predictor == SelfCorrecting {
need_self_correcting = true
}
}
}
{ nodes, need_self_correcting, max_prev_channel_depth, }
}
///|
/// `v.saturating_sub(base).clamp(0, len - 1)`.
#inline
fn table_index(v : Int32, base : Int32, len : Int32) -> Int32 {
let d = v.to_int64() - base.to_int64()
if d < 0L {
0
} else if d > (len - 1).to_int64() {
len - 1
} else {
d.to_int()
}
}
///|
/// Walks the tree with the properties computed in `properties`.
pub fn FlatMaTree::get_leaf(
self : FlatMaTree,
properties : PredictorState,
) -> MaTreeLeafClustered {
let nodes = self.nodes
let mut current_node = nodes[0]
while true {
match current_node {
FusedDecision(
prop_level0=p,
value_level0=v,
prop_l=pl,
prop_r=pr,
value_l=vl,
value_r=vr,
index_base~
) => {
let next_node = if properties.get_property(p) <= v {
index_base + (if properties.get_property(pr) <= vr { 3 } else { 2 })
} else {
index_base + (if properties.get_property(pl) <= vl { 1 } else { 0 })
}
current_node = nodes[next_node]
}
Table(prop~, value_base~, indices~) => {
let v = properties.get_property(prop)
let idx = table_index(v, value_base, indices.length())
current_node = nodes[indices[idx]]
}
Leaf(leaf) => return leaf
}
}
panic()
}
///|
/// Returns whether self-correcting predictor should be initialized.
pub fn FlatMaTree::need_self_correcting(self : FlatMaTree) -> Bool {
self.need_self_correcting
}
///|
/// Returns the number of previously decoded channels needed in order to
/// traverse the MA tree.
pub fn FlatMaTree::max_prev_channel_depth(self : FlatMaTree) -> Int32 {
self.max_prev_channel_depth
}
///|
/// Decode a sample with the given state.
pub fn FlatMaTree::decode_sample(
self : FlatMaTree,
bs : @bitstream.Bitstream,
decoder : @coding.Decoder,
properties : PredictorState,
dist_multiplier : Int32,
) -> (Int32, Predictor) raise @bitstream.JxlError {
let leaf = self.get_leaf(properties)
let diff = decoder.read_varint_with_multiplier_clustered(
bs,
leaf.cluster,
dist_multiplier,
)
let diff = wrapping_muladd_i32(
unpack_signed_u32(diff),
leaf.multiplier,
leaf.offset,
)
(diff, leaf.predictor)
}
///|
fn FlatMaTree::single_node(self : FlatMaTree) -> MaTreeLeafClustered? {
match self.nodes {
[Leaf(node), ..] => Some(node)
_ => None
}
}
///|
priv struct SimpleMaTable {
decision_prop : Int32
value_base : Int32
predictor : Predictor
offset : Int32
multiplier : Int32
cluster_table : FixedArray[Int32]
}
///|
fn FlatMaTree::simple_table(self : FlatMaTree) -> SimpleMaTable? {
guard self.nodes is [Table(prop=decision_prop, value_base~, indices~), ..] else {
return None
}
let mut state : (Predictor, Int32, Int32)? = None
let cluster_table = FixedArray::make(indices.length(), 0)
for i, index in indices {
guard self.nodes[index] is Leaf(leaf) else { return None }
let leaf_props = (leaf.predictor, leaf.offset, leaf.multiplier)
match state {
None => state = Some(leaf_props)
Some(s) => if s != leaf_props { return None }
}
cluster_table[i] = leaf.cluster
}
let (predictor, offset, multiplier) = state.unwrap()
Some({
decision_prop,
value_base,
predictor,
offset,
multiplier,
cluster_table,
})
}
///|
priv enum MaTreeNode {
Decision(
property~ : Int32,
value~ : Int32,
left~ : MaTreeNode,
right~ : MaTreeNode
)
Leaf(MaTreeLeafClustered)
}
///|
fn MaTreeNode::next_decision_node(
self : MaTreeNode,
channel : Int32,
stream_idx : Int32,
prev_channels : Int32,
) -> MaTreeNode {
let mut node = self
while true {
match node {
Decision(property~, value~, left~, right~) if property == 0 ||
property == 1 => {
let target = if property == 0 { channel } else { stream_idx }
node = if target > value { left } else { right }
}
Decision(property~, value~, left~, right~) if property >= 16 => {
let prev_channel_idx = (property - 16) / 4
if prev_channel_idx >= prev_channels {
node = if value < 0 { left } else { right }
} else {
return node
}
}
_ => return node
}
}
panic()
}
///|
fn MaTreeNode::try_compile_to_table(
self : MaTreeNode,
channel : Int32,
stream_idx : Int32,
prev_channels : Int32,
next_index_base : Int32,
) -> (FlatMaTreeNode, Array[MaTreeNode])? {
guard self is Decision(property~, value~, left~, right~) else { return None }
let mut lower_bound = value
let mut upper_bound = value
// (node, range start, range end), inclusive ranges
let stack : Array[(MaTreeNode, Int32, Int32)] = [
(left, value + 1, 0x7fffffff),
(right, -0x80000000, value),
]
let range_nodes : Array[(MaTreeNode, Int32)] = []
while stack.pop() is Some((node, range_start, range_end)) {
let node = node.next_decision_node(channel, stream_idx, prev_channels)
guard node is Decision(property=target_property, value~, left~, right~) &&
target_property == property else {
range_nodes.push((node, range_end))
continue
}
let new_lower_bound = if value < lower_bound { value } else { lower_bound }
let new_upper_bound = if value > upper_bound { value } else { upper_bound }
if new_upper_bound.to_int64() - new_lower_bound.to_int64() > 1024L - 2L {
range_nodes.push((node, range_end))
continue
}
lower_bound = new_lower_bound
upper_bound = new_upper_bound
let left_start = value + 1
let left_end = range_end
let right_start = range_start
let right_end = value
if left_start <= left_end {
stack.push((left, left_start, left_end))
}
if right_start <= right_end {
stack.push((right, right_start, right_end))
}
}
if range_nodes.length() < 4 {
return None
}
range_nodes.sort_by_key(fn(x) { x.1 })
let index_count = (upper_bound.to_int64() - lower_bound.to_int64()).to_int() +
2
let indices = FixedArray::make(index_count, 0)
let nodes = []
let mut range_start = lower_bound - 1
let mut next_index = 0
for idx, item in range_nodes {
let (node, range_end) = item
if range_end == 0x7fffffff {
indices[index_count - 1] = next_index_base + idx
nodes.push(node)
break
}
let len = abs_diff_i32(range_end, range_start).to_int()
let end_index = next_index + len
guard end_index <= index_count else { abort("index out of bounds") }
for i in next_index.. Array[FlatMaTreeNode] {
let target = self.next_decision_node(channel, stream_idx, prev_channels)
let q : Array[MaTreeNode] = [target]
let mut head = 0
let out = []
let mut next_base = 1
while head < q.length() {
let target = q[head]
head += 1
let target = target.next_decision_node(channel, stream_idx, prev_channels)
if target.try_compile_to_table(
channel, stream_idx, prev_channels, next_base,
)
is Some((out_node, nodes)) {
out.push(out_node)
q.push_iter(nodes.iter())
next_base += nodes.length()
continue
}
match target {
Decision(property~, value~, left~, right~) => {
let left = left.next_decision_node(channel, stream_idx, prev_channels)
let (lp, lv, ll, lr) = match left {
Decision(property~, value~, left~, right~) =>
(property, value, left, right)
node => (0, 0, node, node)
}
let right = right.next_decision_node(channel, stream_idx, prev_channels)
let (rp, rv, rl, rr) = match right {
Decision(property~, value~, left~, right~) =>
(property, value, left, right)
node => (0, 0, node, node)
}
out.push(
FlatMaTreeNode::FusedDecision(
prop_level0=property,
value_level0=value,
prop_l=lp,
prop_r=rp,
value_l=lv,
value_r=rv,
index_base=next_base,
),
)
q.push(ll)
q.push(lr)
q.push(rl)
q.push(rr)
next_base += 4
}
Leaf(leaf) => out.push(FlatMaTreeNode::Leaf(leaf))
}
}
out
}