// AV1 entropy coding: the MSB-first bit writer used by OBU headers and the
// multi-symbol range encoder (the encoder side of the spec's symbol
// decoder, after libaom / rav1e), with the spec's CDF adaptation.
///|
/// MSB-first bit writer (the spec's f(n) descriptors).
priv struct Av1BitWriter {
buf : Array[Byte]
mut acc : Int32
mut nbits : Int32
}
///|
fn Av1BitWriter::new() -> Av1BitWriter {
{ buf: [], acc: 0, nbits: 0, }
}
///|
fn Av1BitWriter::put(self : Av1BitWriter, v : Int32, n : Int32) -> Unit {
for i = n - 1; i >= 0; i = i - 1 {
self.acc = (self.acc << 1) | ((v >> i) & 1)
self.nbits += 1
if self.nbits == 8 {
self.buf.push(self.acc.to_byte())
self.acc = 0
self.nbits = 0
}
}
}
///|
/// trailing_bits: a one bit, then zeros up to the byte boundary.
fn Av1BitWriter::trailing(self : Av1BitWriter) -> Unit {
self.put(1, 1)
while self.nbits != 0 {
self.put(0, 1)
}
}
///|
fn Av1BitWriter::byte_align(self : Av1BitWriter) -> Unit {
while self.nbits != 0 {
self.put(0, 1)
}
}
///|
fn Av1BitWriter::bytes(self : Av1BitWriter) -> Array[Byte] {
self.buf
}
///|
/// leb128 encoding of `v` (OBU sizes).
fn av1_leb128(out : Array[Byte], v : Int32) -> Unit {
let mut x = v
while true {
let b = x & 0x7f
x = x >> 7
if x != 0 {
out.push((b | 0x80).to_byte())
} else {
out.push(b.to_byte())
break
}
}
}
///|
/// Range encoder state.
priv struct Av1SymWriter {
precarry : Array[Int32]
mut low : UInt32
mut rng : Int32
mut cnt : Int32
}
///|
fn Av1SymWriter::new() -> Av1SymWriter {
{ precarry: [], low: 0U, rng: 0x8000, cnt: -9, }
}
///|
/// Leading zeros of a 16-bit value.
fn av1_clz16(v : Int32) -> Int32 {
let mut n = 0
let mut x = v
while n < 16 && (x & 0x8000) == 0 {
x = x << 1
n += 1
}
n
}
///|
/// Encode the interval [fl, fh) of an inverse CDF (32768 - cdf) with
/// `nms` symbols at or above the coded one.
fn Av1SymWriter::store(
self : Av1SymWriter,
fl : Int32,
fh : Int32,
nms : Int32,
) -> Unit {
let r = self.rng
let u = if fl >= 32768 { r } else { (((r >> 8) * (fl >> 6)) >> 1) + 4 * nms }
let v = (((r >> 8) * (fh >> 6)) >> 1) + 4 * (nms - 1)
let mut low = (r - u).reinterpret_as_uint() + self.low
let rr = u - v
let mut c = self.cnt
let d = av1_clz16(rr)
let mut s = c + d
if s >= 0 {
c += 16
let mut m = (1U << c) - 1U
if s >= 8 {
self.precarry.push((low >> c).reinterpret_as_int())
low = low & m
c -= 8
m = m >> 8
}
self.precarry.push((low >> c).reinterpret_as_int())
s = c + d - 24
low = low & m
}
self.low = low << d
self.rng = rr << d
self.cnt = s
}
///|
/// Encode symbol `s` with the CDF `cdf[off ..< off + n]` (spec layout:
/// increasing, last 32768) and adapt it (count at `cdf[off + n]`).
fn Av1SymWriter::symbol(
self : Av1SymWriter,
cdf : FixedArray[Int32],
off : Int32,
n : Int32,
s : Int32,
) -> Unit {
let fl = if s > 0 { 32768 - cdf[off + s - 1] } else { 32768 }
let fh = 32768 - cdf[off + s]
self.store(fl, fh, n - s)
av1_update_cdf(cdf, off, n, s)
}
///|
/// One equiprobable bit (read_bool).
fn Av1SymWriter::bool(self : Av1SymWriter, b : Int32) -> Unit {
// cdf = { 16384, 32768 }
if b == 0 {
self.store(32768, 16384, 2)
} else {
self.store(16384, 0, 1)
}
}
///|
/// `n` raw bits, MSB first (read_literal).
fn Av1SymWriter::literal(self : Av1SymWriter, v : Int32, n : Int32) -> Unit {
for i = n - 1; i >= 0; i = i - 1 {
self.bool((v >> i) & 1)
}
}
///|
/// Flush and return the coded bytes (the decoder's exit_symbol padding
/// rules hold: a final one bit followed by zeros).
fn Av1SymWriter::finish(self : Av1SymWriter) -> Array[Byte] {
let l = self.low
let mut c = self.cnt
let mut s = 10
let m = 0x3FFFU
let mut e = ((l + m) & m.lnot()) | (m + 1U)
s += c
if s > 0 {
let mut n = (1U << (c + 16)) - 1U
while true {
self.precarry.push((e >> (c + 16)).reinterpret_as_int())
e = e & n
s -= 8
c -= 8
n = n >> 8
if s <= 0 {
break
}
}
}
let len = self.precarry.length()
let out = Array::make(len, b'\x00')
let mut carry = 0
for i = len - 1; i >= 0; i = i - 1 {
carry += self.precarry[i]
out[i] = (carry & 0xff).to_byte()
carry = carry >> 8
}
out
}
///|
/// The spec's CDF adaptation after coding `s` (disable_cdf_update = 0).
fn av1_update_cdf(
cdf : FixedArray[Int32],
off : Int32,
n : Int32,
s : Int32,
) -> Unit {
let cnt = cdf[off + n]
let rate = 3 +
(if cnt > 15 { 1 } else { 0 }) +
(if cnt > 31 { 1 } else { 0 }) +
(if n >= 4 { 2 } else if n >= 2 { 1 } else { 0 })
for i in 0..<(n - 1) {
if i < s {
cdf[off + i] = cdf[off + i] - (cdf[off + i] >> rate)
} else {
cdf[off + i] = cdf[off + i] + ((32768 - cdf[off + i]) >> rate)
}
}
if cnt < 32 {
cdf[off + n] = cnt + 1
}
}
///|
/// Cost in 1/256 bit of coding `s` with the CDF at `off` (no update).
fn av1_symbol_cost(cdf : FixedArray[Int32], off : Int32, s : Int32) -> Int32 {
let lo = if s > 0 { cdf[off + s - 1] } else { 0 }
let p = cdf[off + s] - lo
av1_cost_q15(p)
}
///|
/// -log2(p / 32768) * 256 for p in 1..32768.
fn av1_cost_q15(p : Int32) -> Int32 {
av1_cost_table[if p < 1 { 1 } else { p }]
}
///|
/// -log2(p / 32768) * 256 for p = 0..32768 (entry 0 is unused).
let av1_cost_table : FixedArray[Int32] = FixedArray::makei(32769, fn(p) {
if p < 1 {
3840
} else {
3840 - vp8l_log2_fix(p)
}
})