nx_av1_ec.nx source

1// nx_av1_ec.nx -- the AV1/AV2 multi-symbol CDF arithmetic decoder. 2// 3// THE MOAT FOUNDATION. AV1, AVIF and AV2 all rest on this one primitive: a 4// multi-symbol (not binary) arithmetic coder whose probability tables ADAPT 5// as they decode. Nothing in this tree had it. nx_rangecoder.nx is the older 6// BINARY range coder (CABAC/VP8 class) -- it cannot decode AV1, because AV1 7// draws an N-ary symbol per call against a cumulative distribution rather 8// than a sequence of bits against a single probability. 9// 10// AV2 v1.0.0 (spec frozen 2026-05-28) inherits this coder essentially intact, 11// so this module is the shared substrate for both. Build it once, correctly. 12// 13// CDF CONVENTION -- FORWARD, PER THE SPEC. cdf[i] is the cumulative 14// probability of symbols <= i scaled to 32768, so the array INCREASES and 15// cdf[N-1] == 32768. libaom stores the INVERSE internally (32768 minus this, 16// decreasing to 0) and its update formula is written for that form. Mixing 17// the two is the classic porting error and it is nearly invisible: the 18// terminating entry agrees under BOTH conventions, so the first symbol of a 19// stream often decodes correctly and everything after it diverges. This file 20// is spec-form throughout; do not paste libaom arithmetic into it. 21// 22// THE TRAILING SLOT. cdf has N+1 entries: N probabilities plus a COUNTER at 23// cdf[N] that tracks how many times this context has been used. The counter 24// drives the adaptation rate -- a fresh context adapts fast, a mature one 25// slowly. Dropping it (sizing the array at N) both breaks adaptation and 26// writes one past the end. 27// 28// genealogy_id: av1_spec_8_3_symbol_decoder 29// lineage_id: nx_av1_ec_v1 30// license_tier: ORIGINAL 31 32import "nx_syscalls.nx" 33import "nx_bitstream.nx" 34 35const NX_AV1_CDF_TOTAL: i64 = 32768 36const NX_AV1_EC_BYTES: i64 = 40 37 38struct NxAv1Ec { 39 bs: i64, 40 value: i64, 41 range: i64, 42 max_bits: i64, 43} 44 45// ===== FloorLog2 ================================================== 46// 47// Returns -1 for 0 so a caller can distinguish "no bits" from "bit 0". 48 49func nx_av1_floor_log2(v: i64) -> i64 { 50 if v <= 0 { return 0 - 1 } 51 var x: i64 = v 52 var n: i64 = 0 53 while x > 1 { x = x >> 1; n = n + 1 } 54 return n 55} 56 57func nx_av1_min(a: i64, b: i64) -> i64 { if a < b { return a } return b } 58func nx_av1_max(a: i64, b: i64) -> i64 { if a > b { return a } return b } 59 60// ===== init ======================================================= 61// 62// sz is the size in BYTES of the tile/partition this coder will read. The 63// first 15 bits prime the value register; max_bits tracks how many real bits 64// remain so renormalization can pad with zeros past the end instead of 65// reading off the buffer. 66 67func nx_av1_ec_init(bs: *NxBitStream, sz: i64) -> *NxAv1Ec { 68 if bs == (0 as *NxBitStream) { return 0 as *NxAv1Ec } 69 if sz <= 0 { return 0 as *NxAv1Ec } 70 let num_bits: i64 = nx_av1_min(sz * 8, 15) 71 let buf: i64 = nx_bitstream_read_msb(bs, num_bits) 72 let padded: i64 = buf << (15 - num_bits) 73 let ec: *NxAv1Ec = sys_mmap(NX_AV1_EC_BYTES) as *NxAv1Ec 74 ec.bs = bs as i64 75 ec.value = (NX_AV1_CDF_TOTAL - 1) ^ padded 76 ec.range = NX_AV1_CDF_TOTAL 77 ec.max_bits = sz * 8 - 15 78 return ec 79} 80 81// ===== renormalization ============================================ 82// 83// Rescales range back up into its working window and refills value. Past the 84// end of the real data it pads with zeros rather than failing -- AV1 streams 85// legitimately run the coder past the final byte. 86 87func nx_av1_ec_renorm(ec: *NxAv1Ec) -> i64 { 88 let bits: i64 = 15 - nx_av1_floor_log2(ec.range) 89 if bits <= 0 { return 1 } 90 let bs: *NxBitStream = ec.bs as *NxBitStream 91 let num_bits: i64 = nx_av1_min(bits, nx_av1_max(0, ec.max_bits)) 92 var new_data: i64 = 0 93 if num_bits > 0 { new_data = nx_bitstream_read_msb(bs, num_bits) } 94 let padded: i64 = new_data << (bits - num_bits) 95 ec.range = ec.range << bits 96 ec.value = padded ^ (((ec.value + 1) << bits) - 1) 97 ec.max_bits = ec.max_bits - bits 98 return 1 99} 100 101// ===== decode one symbol ========================================== 102// 103// cdf holds N inverted cumulative probabilities plus the usage counter at 104// cdf[N]. Returns the symbol in [0, N-1], or -1 on a malformed call. 105// cdf[N-1] == 32768 makes f zero on the last symbol, so cur reaches 0 and the 106// walk always terminates. 107 108func nx_av1_decode_symbol(ec: *NxAv1Ec, cdf: *i64, n: i64) -> i64 { 109 if ec == (0 as *NxAv1Ec) { return 0 - 1 } 110 if n < 2 { return 0 - 1 } 111 var symbol: i64 = 0 - 1 112 var cur: i64 = ec.range 113 var prev: i64 = cur 114 var go: i64 = 1 115 while go == 1 { 116 symbol = symbol + 1 117 if symbol >= n { return 0 - 1 } 118 prev = cur 119 let f: i64 = NX_AV1_CDF_TOTAL - cdf[symbol] 120 cur = ((ec.range >> 8) * f) >> 7 121 if ec.value >= cur { go = 0 } 122 } 123 ec.range = prev - cur 124 ec.value = ec.value - cur 125 nx_av1_ec_renorm(ec) 126 return symbol 127} 128 129// ===== adaptation ================================================= 130// 131// Moves the chosen symbol's probability up and every other down, at a rate 132// that slows as the context matures. The counter at cdf[N] saturates at 32. 133// 134// `tmp` is a RUNNING THRESHOLD, not a per-entry equality test: it is 0 for 135// entries below the decoded symbol and 32768 from the symbol onward. Every 136// entry below the symbol is pulled down and every entry from the symbol up is 137// pushed toward full, which widens exactly that symbol's interval. Writing it 138// as a bare `if i == symbol` touches ONE entry and leaves the distribution 139// un-normalised -- it still decodes, it just drifts away from the encoder 140// until the stream desyncs. 141 142func nx_av1_update_cdf(cdf: *i64, symbol: i64, n: i64) -> i64 { 143 if n < 2 { return 0 } 144 if symbol < 0 { return 0 } 145 if symbol >= n { return 0 } 146 var rate: i64 = 3 147 if cdf[n] > 15 { rate = rate + 1 } 148 if cdf[n] > 31 { rate = rate + 1 } 149 let lg: i64 = nx_av1_floor_log2(n) 150 rate = rate + nx_av1_min(lg, 2) 151 152 var tmp: i64 = 0 153 var i: i64 = 0 154 while i < n - 1 { 155 if i == symbol { tmp = NX_AV1_CDF_TOTAL } 156 if tmp < cdf[i] { 157 cdf[i] = cdf[i] - ((cdf[i] - tmp) >> rate) 158 } else { 159 cdf[i] = cdf[i] + ((tmp - cdf[i]) >> rate) 160 } 161 i = i + 1 162 } 163 if cdf[n] < 32 { cdf[n] = cdf[n] + 1 } 164 return 1 165} 166 167// ===== a uniform starting CDF ===================================== 168// 169// Allocates N+1 slots and fills the first N with an equiprobable inverted 170// distribution, terminator included, and zeroes the usage counter. 171 172func nx_av1_cdf_uniform(n: i64) -> *i64 { 173 if n < 2 { return 0 as *i64 } 174 let cdf: *i64 = sys_mmap((n + 2) * 8 + 64) as *i64 175 var i: i64 = 0 176 while i < n { 177 cdf[i] = ((i + 1) * NX_AV1_CDF_TOTAL) / n 178 i = i + 1 179 } 180 cdf[n - 1] = NX_AV1_CDF_TOTAL 181 cdf[n] = 0 182 return cdf 183}