use crate::hevc::tables::{RANGE_TAB_LPS, TRANS_IDX_LPS, TRANS_IDX_MPS};
struct Reader<'a> {
b: &'a [u8],
p: usize,
}
impl<'a> Reader<'a> {
fn bit(&mut self) -> u32 {
let (byte, off) = (self.p >> 3, 7 - (self.p & 7));
self.p += 1;
if byte < self.b.len() {
((self.b[byte] >> off) & 1) as u32
} else {
0
}
}
fn bits(&mut self, n: u32) -> u32 {
let mut v = 0;
for _ in 0..n {
v = (v << 1) | self.bit();
}
v
}
}
struct Dec<'a> {
range: u32,
offset: u32,
r: Reader<'a>,
}
impl<'a> Dec<'a> {
fn new(b: &'a [u8]) -> Self {
let mut r = Reader { b, p: 0 };
let offset = r.bits(9);
Self { range: 510, offset, r }
}
fn bin(&mut self, c: &mut CtxModel) -> u32 {
let q = ((self.range >> 6) & 3) as usize;
let lps = RANGE_TAB_LPS[c.state as usize][q] as u32;
self.range -= lps;
let v;
if self.offset >= self.range {
v = 1 - c.mps as u32;
self.offset -= self.range;
self.range = lps;
if c.state == 0 {
c.mps = 1 - c.mps;
}
c.state = TRANS_IDX_LPS[c.state as usize];
} else {
v = c.mps as u32;
c.state = TRANS_IDX_MPS[c.state as usize];
}
while self.range < 256 {
self.range <<= 1;
self.offset = (self.offset << 1) | self.r.bit();
}
v
}
fn bypass(&mut self) -> u32 {
self.offset = (self.offset << 1) | self.r.bit();
if self.offset >= self.range {
self.offset -= self.range;
1
} else {
0
}
}
fn bypass_bits(&mut self, n: u32) -> u32 {
let mut v = 0;
for _ in 0..n {
v = (v << 1) | self.bypass();
}
v
}
fn decode_terminate(&mut self) -> u32 {
self.range -= 2;
if self.offset >= self.range {
1
} else {
while self.range < 256 {
self.range <<= 1;
self.offset = (self.offset << 1) | self.r.bit();
}
0
}
}
}
fn decode_last_prefix(dec: &mut Dec, ctxs: &mut [CtxModel], log2n: usize, chroma: bool) -> usize {
let c_max = (log2n << 1) - 1;
let mut group = 0;
while group < c_max && dec.bin(&mut ctxs[last_ctx(group, log2n, chroma)]) == 1 {
group += 1;
}
group
}
fn decode_last_suffix(dec: &mut Dec, group: usize) -> usize {
if group > 3 {
let nbits = (group >> 1) - 1;
MIN_IN_GROUP[group] + dec.bypass_bits(nbits as u32) as usize
} else {
group
}
}
fn read_remaining(dec: &mut Dec, rice: u32) -> u32 {
let mut prefix = 0u32;
while dec.bypass() == 1 {
prefix += 1;
}
if prefix < 3 {
let suffix = if rice > 0 { dec.bypass_bits(rice) } else { 0 };
(prefix << rice) + suffix
} else {
let len = prefix - 3 + rice;
let suffix = dec.bypass_bits(len);
((3 << rice) + ((1u32 << len) - (1u32 << rice))) + suffix
}
}
fn decode(dec: &mut Dec, ctx: &mut ResidualCtx, n: usize, chroma: bool, scan_idx: u8) -> Vec<i32> {
let log2n = log2(n);
let scan = full_scan(n, scan_idx);
let inner = scan_kxk(4, scan_idx);
let side = n / 4;
let gx = decode_last_prefix(dec, &mut ctx.last_x, log2n, chroma);
let gy = decode_last_prefix(dec, &mut ctx.last_y, log2n, chroma);
let last_x = decode_last_suffix(dec, gx);
let last_y = decode_last_suffix(dec, gy);
let (last_x, last_y) = if scan_idx == 2 {
(last_y, last_x)
} else {
(last_x, last_y)
};
let last_scan = scan.iter().position(|&p| p == (last_x, last_y)).unwrap();
let last_sb = last_scan / 16;
let last_pos = last_scan % 16;
let mut coeff = vec![0i32; n * n];
let mut csbf = vec![vec![false; side]; side];
let sb_scan = scan_kxk(side, scan_idx);
let mut c1_carry = 1u32;
for si in (0..=last_sb).rev() {
let (sxs, sys) = sb_scan[si];
let (is_first, is_last) = (si == 0, si == last_sb);
let mut infer_dc = false;
if !is_first && !is_last {
let rb = csbf_right_below(&csbf, sxs, sys, side);
let ci = (rb.min(1) as usize) + if chroma { 2 } else { 0 };
let bit = dec.bin(&mut ctx.csbf[ci]) == 1;
csbf[sys][sxs] = bit;
if !bit {
continue;
}
infer_dc = true;
} else {
csbf[sys][sxs] = true;
}
let csbf_rb = csbf_right_below(&csbf, sxs, sys, side);
let start = if is_last { last_pos as i32 - 1 } else { 15 };
let mut sig = [false; 16];
if is_last {
sig[last_pos] = true;
}
let sub_nonzero = sxs + sys != 0;
let mut num_sig = if is_last { 1 } else { 0 };
for p in (0..=start).rev() {
let (px, py) = inner[p as usize];
let (xc, yc) = (sxs * 4 + px, sys * 4 + py);
if p == 0 && infer_dc && num_sig == 0 {
sig[0] = true;
num_sig += 1;
break;
}
let ci = sig_ctx(xc, yc, log2n, chroma, sub_nonzero, csbf_rb, scan_idx);
if dec.bin(&mut ctx.sig[ci]) == 1 {
sig[p as usize] = true;
num_sig += 1;
}
}
if num_sig == 0 {
continue;
}
let mut positions = Vec::with_capacity(num_sig);
for p in (0..16).rev() {
if sig[p] {
let (px, py) = inner[p];
positions.push((sxs * 4 + px, sys * 4 + py));
}
}
let ctx_set_base = if si > 0 && !chroma { 2 } else { 0 };
let ctx_set = ctx_set_base + if c1_carry == 0 { 1 } else { 0 };
let mut c1 = 1u32;
let mut first_gt1: i32 = -1;
let n_gt1 = positions.len().min(8);
let mut gt1 = vec![0u32; n_gt1];
for idx in 0..n_gt1 {
let base = if chroma { 16 } else { 0 };
let ci = base + (ctx_set << 2) + c1 as usize;
let bin = dec.bin(&mut ctx.gt1[ci]);
gt1[idx] = bin;
if bin == 1 {
c1 = 0;
if first_gt1 < 0 {
first_gt1 = idx as i32;
}
} else if c1 > 0 && c1 < 3 {
c1 += 1;
}
}
c1_carry = c1;
let mut gt2 = 0u32;
if first_gt1 >= 0 {
let base = if chroma { 4 } else { 0 };
gt2 = dec.bin(&mut ctx.gt2[base + ctx_set]);
}
let signs: Vec<u32> = (0..positions.len()).map(|_| dec.bypass()).collect();
let mut first_coeff2 = 1u32;
let mut rice = 0u32;
for idx in 0..positions.len() {
let base_level = if idx < 8 { 2 + first_coeff2 } else { 1 };
let g1 = if idx < n_gt1 { gt1[idx] } else { 0 };
let g2 = if idx as i32 == first_gt1 { gt2 } else { 0 };
let coded = 1 + g1 + g2;
let abs = if coded == base_level {
let rem = read_remaining(dec, rice);
let a = base_level + rem;
if a > 3 * (1 << rice) {
rice = (rice + 1).min(4);
}
a
} else {
coded
};
if abs >= 2 {
first_coeff2 = 0;
}
let (xc, yc) = positions[idx];
coeff[yc * n + xc] = if signs[idx] == 1 { -(abs as i32) } else { abs as i32 };
}
}
coeff
}
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
self.0
}
fn upto(&mut self, m: u32) -> u32 {
(self.next() % m as u64) as u32
}
}
fn roundtrip_block(n: usize, chroma: bool, scan_idx: u8, coeff: &[i32], qp: i32) {
let mut enc = CabacEncoder::new();
let mut ectx = ResidualCtx::new(qp);
encode(&mut enc, &mut ectx, coeff, n, chroma, scan_idx);
enc.encode_terminate(1);
let bytes = enc.finish();
let mut dec = Dec::new(&bytes);
let mut dctx = ResidualCtx::new(qp);
let got = decode(&mut dec, &mut dctx, n, chroma, scan_idx);
assert_eq!(got, coeff, "residual roundtrip n={n} chroma={chroma} scan={scan_idx}");
}
#[test]
fn residual_roundtrips_random() {
let mut rng = Rng(0x1234_5678_9abc_def1);
for trial in 0..300u32 {
let n = *[4usize, 8, 16].get((trial % 3) as usize).unwrap();
let chroma = trial % 2 == 0;
let scan_idx = (trial % 3) as u8;
let mut coeff = vec![0i32; n * n];
let density = 1 + rng.upto(6);
let mut any = false;
for c in coeff.iter_mut() {
if rng.upto(density) == 0 {
let mag = match rng.upto(10) {
0..=5 => 1,
6..=7 => 2,
8 => 3 + rng.upto(5) as i32,
_ => 1 + rng.upto(300) as i32,
};
*c = if rng.upto(2) == 0 { -mag } else { mag };
any = true;
}
}
if !any {
coeff[0] = 1; }
roundtrip_block(n, chroma, scan_idx, &coeff, 26);
}
}
#[test]
fn residual_roundtrips_edge_cases() {
roundtrip_block(4, false, 0, &{ let mut c = vec![0; 16]; c[0] = 5; c }, 26);
roundtrip_block(16, false, 0, &{ let mut c = vec![0; 256]; c[255] = -1; c }, 26);
roundtrip_block(8, true, 0, &vec![7; 64], 26);
}
#[test]
fn residual_roundtrips_chained() {
let mut rng = Rng(0xdead_beef_cafe_0001);
let blocks: Vec<(usize, bool, Vec<i32>)> = (0..40)
.map(|t| {
let n = *[4usize, 8, 16].get((t % 3) as usize).unwrap();
let mut c = vec![0i32; n * n];
for x in c.iter_mut() {
if rng.upto(4) == 0 {
let m = 1 + rng.upto(50) as i32;
*x = if rng.upto(2) == 0 { -m } else { m };
}
}
if !c.iter().any(|&v| v != 0) {
c[0] = 1;
}
(n, t % 2 == 0, c)
})
.collect();
let mut enc = CabacEncoder::new();
let mut ectx = ResidualCtx::new(26);
for (i, (n, chroma, c)) in blocks.iter().enumerate() {
encode(&mut enc, &mut ectx, c, *n, *chroma, 0);
enc.encode_terminate((i + 1 == blocks.len()) as u32);
}
let bytes = enc.finish();
let mut dec = Dec::new(&bytes);
let mut dctx = ResidualCtx::new(26);
for (i, (n, chroma, c)) in blocks.iter().enumerate() {
let got = decode(&mut dec, &mut dctx, *n, *chroma, 0);
assert_eq!(&got, c, "chained block {i}");
let term = dec.decode_terminate();
assert_eq!(term, (i + 1 == blocks.len()) as u32, "terminate {i}");
}
}