// AV1 encoder decisions: intra modes (SATD pre-selection, then full
// rate-distortion), transform types (av1_encode.mbt) and the partition
// tree (none / split, searched recursively with state snapshots).
///|
/// Decided partition tree of a superblock.
priv enum Av1Tree {
Empty
Leaf(Av1BlockMode)
Split(Array[Av1Tree])
}
///|
/// Luma modes kept after SATD pre-selection.
let av1_mode_candidates = 3
///|
/// Sum of 4x4 Hadamard transformed differences (source - reconstruction).
fn Av1Enc::satd(
self : Av1Enc,
plane : Int32,
x0 : Int32,
y0 : Int32,
w : Int32,
h : Int32,
) -> Int32 {
let st = self.stride[plane]
let src = self.src[plane]
let rec = self.rec[plane]
let d = FixedArray::make(16, 0)
let mut total = 0
let mut by = 0
while by < h {
let mut bx = 0
while bx < w {
for i in 0..<4 {
let o = (y0 + by + i) * st + x0 + bx
let a0 = src[o] - rec[o]
let a1 = src[o + 1] - rec[o + 1]
let a2 = src[o + 2] - rec[o + 2]
let a3 = src[o + 3] - rec[o + 3]
let s01 = a0 + a1
let d01 = a0 - a1
let s23 = a2 + a3
let d23 = a2 - a3
d[i * 4] = s01 + s23
d[i * 4 + 1] = d01 + d23
d[i * 4 + 2] = s01 - s23
d[i * 4 + 3] = d01 - d23
}
for j in 0..<4 {
let s01 = d[j] + d[4 + j]
let d01 = d[j] - d[4 + j]
let s23 = d[8 + j] + d[12 + j]
let d23 = d[8 + j] - d[12 + j]
total += (s01 + s23).abs() +
(d01 + d23).abs() +
(s01 - s23).abs() +
(d01 - d23).abs()
}
bx += 4
}
by += 4
}
total >> 1
}
///|
/// Distortion of the current block (luma + chroma, visible samples).
fn Av1Enc::block_sse(self : Av1Enc) -> Int32 {
let bw = av1_bw4(self.bsize) * 4
let bh = av1_bh4(self.bsize) * 4
let mut d = self.sse(0, self.mi_col * 4, self.mi_row * 4, bw, bh)
if self.has_chroma {
let psz = self.plane_size(1)
let cw = av1_bw4(psz) * 4
let chh = av1_bh4(psz) * 4
let cx = (self.mi_col >> self.ss) * 4
let cy = (self.mi_row >> self.ss) * 4
d += self.sse(1, cx, cy, cw, chh) + self.sse(2, cx, cy, cw, chh)
}
d
}
///|
/// Dry-run the current block with `m`; returns its rate-distortion cost.
fn Av1Enc::try_mode(
self : Av1Enc,
m : Av1BlockMode,
search_tx : Bool,
) -> Double {
self.mode = m
self.search_tx = search_tx
let c0 = self.cost
self.any_nonzero = false
self.code_block()
self.search_tx = false
self.block_sse().to_double() +
self.lambda * (self.cost - c0).to_double() / 256.0
}
///|
fn av1_copy_mode(m : Av1BlockMode) -> Av1BlockMode {
{
ymode: m.ymode,
uvmode: m.uvmode,
angle_y: m.angle_y,
angle_uv: m.angle_uv,
skip: m.skip,
tx_types: m.tx_types.copy(),
}
}
///|
/// Choose the modes of the block at (r, c); leaves the encoder state as
/// after coding the best choice (dry). Returns (cost, modes).
fn Av1Enc::block_rd(
self : Av1Enc,
r : Int32,
c : Int32,
bs : Int32,
) -> (Double, Av1BlockMode) {
self.begin_block(r, c, bs)
let snap = self.snapshot(r, c, bs)
let cols = self.mi_cols
let tx = self.tx_size
let x0 = c * 4
let y0 = r * 4
let bw = av1_bw4(bs) * 4
let bh = av1_bh4(bs) * 4
let sqrt_l = self.lambda.sqrt()
let am = av1_intra_mode_context[if self.avail_u {
self.mi_ymode[(r - 1) * cols + c]
} else {
0
}]
let lm = av1_intra_mode_context[if self.avail_l {
self.mi_ymode[r * cols + c - 1]
} else {
0
}]
let ycdf = self.cdf.kf_y + (am * 5 + lm) * 14
// Luma pre-selection by SATD + mode bits.
let cands : Array[(Double, Int32, Int32)] = []
for mode in 0..<13 {
let directional = mode >= 1 && mode <= 8
let angles = if directional && bs >= av1_block_8x8 {
av1_angle_candidates
} else {
[0]
}
for a in angles {
self.predict_tx(0, x0, y0, tx, 0, 0, mode, a)
let mut bits = av1_symbol_cost(self.cdf.data, ycdf, mode)
if directional && bs >= av1_block_8x8 {
bits += av1_symbol_cost(
self.cdf.data,
self.cdf.angle + (mode - 1) * 8,
a + 3,
)
}
let score = self.satd(0, x0, y0, bw, bh).to_double() +
sqrt_l * bits.to_double() / 256.0
cands.push((score, mode, a))
}
}
cands.sort_by(fn(p, q) { p.0.compare(q.0) })
// Chroma mode by SATD (with the best luma mode's CDF).
let mut uv_best = 0
let mut uv_angle = 0
if self.has_chroma {
let ctx_mode = cands[0].1
let psz = self.plane_size(1)
let ctx_tx = self.plane_tx_size(1)
let cw = av1_bw4(psz) * 4
let chh = av1_bh4(psz) * 4
let cx = (c >> self.ss) * 4
let cy = (r >> self.ss) * 4
let cfl_ok = (if bw > bh { bw } else { bh }) <= 32
let mut best_s = 1.0e300
// The best luma mode and the common chroma modes.
let uv_modes = [ctx_mode, 0, 9, 1, 2, 12]
for k, mode in uv_modes {
if k > 0 && mode == ctx_mode {
continue
}
let directional = mode >= 1 && mode <= 8
self.predict_tx(1, cx, cy, ctx_tx, 0, 0, mode, 0)
self.predict_tx(2, cx, cy, ctx_tx, 0, 0, mode, 0)
let mut bits = if cfl_ok {
av1_symbol_cost(self.cdf.data, self.cdf.uv_cfl + ctx_mode * 15, mode)
} else {
av1_symbol_cost(self.cdf.data, self.cdf.uv_no_cfl + ctx_mode * 14, mode)
}
if directional && bs >= av1_block_8x8 {
bits += av1_symbol_cost(
self.cdf.data,
self.cdf.angle + (mode - 1) * 8,
3,
)
}
let s = (self.satd(1, cx, cy, cw, chh) + self.satd(2, cx, cy, cw, chh)).to_double() +
sqrt_l * bits.to_double() / 256.0
if s < best_s {
best_s = s
uv_best = mode
uv_angle = 0
}
}
}
// Full rate-distortion for the best luma candidates.
let mut best_j = 1.0e300
let mut best = Av1BlockMode::new()
// State after the best trial (so it need not be coded again).
let mut best_state : Av1Snap? = None
let kmax = av1_mode_candidates
let k = if cands.length() < kmax { cands.length() } else { kmax }
for i in 0.. {
// Leave the state as after the best choice.
self.restore(st)
self.begin_block(r, c, bs)
self.mode = best
return (best_j, best)
}
None => ()
}
}
}
// Leave the state as after the best choice.
self.restore(snap)
self.begin_block(r, c, bs)
let fin = av1_copy_mode(best)
if best.skip {
// A skipped block re-derives its (DCT) transform types.
fin.tx_types.clear()
}
let j = self.try_mode(fin, false)
(j, fin)
}
///|
/// Angle deltas tried for directional modes.
let av1_angle_candidates : Array[Int32] = [0]
///|
/// Search the partition tree of a square block (dry); leaves the state as
/// after coding the best tree. Returns (cost, tree).
fn Av1Enc::search(
self : Av1Enc,
r : Int32,
c : Int32,
bs : Int32,
) -> (Double, Av1Tree) {
if r >= self.mi_rows || c >= self.mi_cols {
return (0.0, Empty)
}
let half = av1_bw4(bs) >> 1
let has_rows = r + half < self.mi_rows
let has_cols = c + half < self.mi_cols
let can_none = has_rows && has_cols
let can_split = bs > av1_block_8x8
let snap0 = self.snapshot(r, c, bs)
let mut best_j = 1.0e300
let mut best_tree = Empty
let mut snap_none : Av1Snap? = None
if can_none {
let c0 = self.cost
self.write_partition(r, c, bs, 0, has_rows, has_cols)
let pc = self.cost - c0
let (j, m) = self.block_rd(r, c, bs)
best_j = j + self.lambda * pc.to_double() / 256.0
best_tree = Leaf(m)
if can_split {
snap_none = Some(self.snapshot(r, c, bs))
self.restore(snap0)
}
}
if can_split {
let c0 = self.cost
self.write_partition(r, c, bs, 3, has_rows, has_cols)
let pc = self.cost - c0
let sub = av1_subsize(3, bs)
let kids : Array[Av1Tree] = []
let mut j = self.lambda * pc.to_double() / 256.0
for k in 0..<4 {
let rr = r + (k >> 1) * half
let cc = c + (k & 1) * half
let (jk, tk) = self.search(rr, cc, sub)
j += jk
kids.push(tk)
}
if j < best_j {
best_j = j
best_tree = Split(kids)
} else {
match snap_none {
Some(s) => self.restore(s)
None => ()
}
}
}
(best_j, best_tree)
}
///|
/// Write a decided partition tree.
fn Av1Enc::write_tree(
self : Av1Enc,
r : Int32,
c : Int32,
bs : Int32,
tree : Av1Tree,
) -> Unit {
if r >= self.mi_rows || c >= self.mi_cols {
return
}
let half = av1_bw4(bs) >> 1
let has_rows = r + half < self.mi_rows
let has_cols = c + half < self.mi_cols
match tree {
Leaf(m) => {
self.write_partition(r, c, bs, 0, has_rows, has_cols)
self.begin_block(r, c, bs)
self.mode = m
self.search_tx = false
self.code_block()
}
Split(kids) => {
self.write_partition(r, c, bs, 3, has_rows, has_cols)
let sub = av1_subsize(3, bs)
for k in 0..<4 {
self.write_tree(r + (k >> 1) * half, c + (k & 1) * half, sub, kids[k])
}
}
Empty => ()
}
}