| 1 |
// Copyright (c) 2017-2022, The rav1e contributors. All rights reserved |
| 2 |
// |
| 3 |
// This source code is subject to the terms of the BSD 2 Clause License and |
| 4 |
// the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License |
| 5 |
// was not distributed with this source code in the LICENSE file, you can |
| 6 |
// obtain it at www.aomedia.org/license/software. If the Alliance for Open |
| 7 |
// Media Patent License 1.0 was not distributed with this source code in the |
| 8 |
// PATENTS file, you can obtain it at www.aomedia.org/license/patent. |
| 9 |
|
| 10 |
#![allow(non_upper_case_globals)] |
| 11 |
|
| 12 |
mod tables; |
| 13 |
|
| 14 |
cfg_if::cfg_if! { |
| 15 |
if #[cfg(nasm_x86_64)] { |
| 16 |
pub use crate::asm::x86::quantize::*; |
| 17 |
} else { |
| 18 |
pub use self::rust::*; |
| 19 |
} |
| 20 |
} |
| 21 |
|
| 22 |
pub use tables::*; |
| 23 |
|
| 24 |
use crate::scan_order::av1_scan_orders; |
| 25 |
use crate::transform::{TxSize, TxType}; |
| 26 |
use crate::util::*; |
| 27 |
use std::mem; |
| 28 |
use std::num::{NonZeroU16, NonZeroU32, NonZeroU64}; |
| 29 |
|
| 30 |
pub fn get_log_tx_scale(tx_size: TxSize) -> usize { |
| 31 |
let num_pixels = tx_size.area(); |
| 32 |
|
| 33 |
Into::<usize>::into(num_pixels > 256) |
| 34 |
+ Into::<usize>::into(num_pixels > 1024) |
| 35 |
} |
| 36 |
|
| 37 |
pub fn dc_q(qindex: u8, delta_q: i8, bit_depth: usize) -> NonZeroU16 { |
| 38 |
let dc_q: [&[NonZeroU16; 256]; 3] = |
| 39 |
[&dc_qlookup_Q3, &dc_qlookup_10_Q3, &dc_qlookup_12_Q3]; |
| 40 |
let bd = ((bit_depth ^ 8) >> 1).min(2); |
| 41 |
dc_q[bd][((qindex as isize + delta_q as isize).max(0) as usize).min(255)] |
| 42 |
} |
| 43 |
|
| 44 |
pub fn ac_q(qindex: u8, delta_q: i8, bit_depth: usize) -> NonZeroU16 { |
| 45 |
let ac_q: [&[NonZeroU16; 256]; 3] = |
| 46 |
[&ac_qlookup_Q3, &ac_qlookup_10_Q3, &ac_qlookup_12_Q3]; |
| 47 |
let bd = ((bit_depth ^ 8) >> 1).min(2); |
| 48 |
ac_q[bd][((qindex as isize + delta_q as isize).max(0) as usize).min(255)] |
| 49 |
} |
| 50 |
|
| 51 |
// TODO: Handle lossless properly. |
| 52 |
fn select_qi(quantizer: i64, qlookup: &[NonZeroU16; QINDEX_RANGE]) -> u8 { |
| 53 |
if quantizer < qlookup[MINQ].get() as i64 { |
| 54 |
MINQ as u8 |
| 55 |
} else if quantizer >= qlookup[MAXQ].get() as i64 { |
| 56 |
MAXQ as u8 |
| 57 |
} else { |
| 58 |
match qlookup |
| 59 |
.binary_search(&NonZeroU16::new(quantizer as u16).expect("Not zero")) |
| 60 |
{ |
| 61 |
Ok(qi) => qi as u8, |
| 62 |
Err(qi) => { |
| 63 |
debug_assert!(qi > MINQ); |
| 64 |
debug_assert!(qi <= MAXQ); |
| 65 |
// Pick the closest quantizer in the log domain. |
| 66 |
let qthresh = |
| 67 |
(qlookup[qi - 1].get() as i32) * (qlookup[qi].get() as i32); |
| 68 |
let q2_i32 = (quantizer as i32) * (quantizer as i32); |
| 69 |
if q2_i32 < qthresh { |
| 70 |
(qi - 1) as u8 |
| 71 |
} else { |
| 72 |
qi as u8 |
| 73 |
} |
| 74 |
} |
| 75 |
} |
| 76 |
} |
| 77 |
} |
| 78 |
|
| 79 |
pub fn select_dc_qi(quantizer: i64, bit_depth: usize) -> u8 { |
| 80 |
let qlookup = match bit_depth { |
| 81 |
8 => &dc_qlookup_Q3, |
| 82 |
10 => &dc_qlookup_10_Q3, |
| 83 |
12 => &dc_qlookup_12_Q3, |
| 84 |
_ => unimplemented!(), |
| 85 |
}; |
| 86 |
select_qi(quantizer, qlookup) |
| 87 |
} |
| 88 |
|
| 89 |
pub fn select_ac_qi(quantizer: i64, bit_depth: usize) -> u8 { |
| 90 |
let qlookup = match bit_depth { |
| 91 |
8 => &ac_qlookup_Q3, |
| 92 |
10 => &ac_qlookup_10_Q3, |
| 93 |
12 => &ac_qlookup_12_Q3, |
| 94 |
_ => unimplemented!(), |
| 95 |
}; |
| 96 |
select_qi(quantizer, qlookup) |
| 97 |
} |
| 98 |
|
| 99 |
#[derive(Debug, Clone, Copy)] |
| 100 |
pub struct QuantizationContext { |
| 101 |
log_tx_scale: usize, |
| 102 |
dc_quant: NonZeroU16, |
| 103 |
dc_offset: u32, |
| 104 |
dc_mul_add: (u32, u32, u32), |
| 105 |
|
| 106 |
ac_quant: NonZeroU16, |
| 107 |
ac_offset_eob: u32, |
| 108 |
ac_offset0: u32, |
| 109 |
ac_offset1: u32, |
| 110 |
ac_mul_add: (u32, u32, u32), |
| 111 |
} |
| 112 |
|
| 113 |
impl Default for QuantizationContext { |
| 114 |
fn default() -> Self { |
| 115 |
QuantizationContext { |
| 116 |
dc_quant: NonZeroU16::new(1).expect("Not zero"), |
| 117 |
ac_quant: NonZeroU16::new(1).expect("Not zero"), |
| 118 |
log_tx_scale: Default::default(), |
| 119 |
dc_offset: Default::default(), |
| 120 |
dc_mul_add: Default::default(), |
| 121 |
ac_offset_eob: Default::default(), |
| 122 |
ac_offset0: Default::default(), |
| 123 |
ac_offset1: Default::default(), |
| 124 |
ac_mul_add: Default::default(), |
| 125 |
} |
| 126 |
} |
| 127 |
} |
| 128 |
|
| 129 |
fn divu_gen(d: NonZeroU32) -> (u32, u32, u32) { |
| 130 |
let nbits = (mem::size_of_val(&d) as u64) * 8; |
| 131 |
let m = nbits - d.leading_zeros() as u64 - 1; |
| 132 |
if d.is_power_of_two() { |
| 133 |
(0xFFFF_FFFF, 0xFFFF_FFFF, m as u32) |
| 134 |
} else { |
| 135 |
let d = NonZeroU64::from(d); |
| 136 |
let t = (1u64 << (m + nbits)) / d; |
| 137 |
|
| 138 |
let d = d.get(); |
| 139 |
let r = (t * d + d) & ((1 << nbits) - 1); |
| 140 |
if r <= 1u64 << m { |
| 141 |
(t as u32 + 1, 0u32, m as u32) |
| 142 |
} else { |
| 143 |
(t as u32, t as u32, m as u32) |
| 144 |
} |
| 145 |
} |
| 146 |
} |
| 147 |
|
| 148 |
#[inline] |
| 149 |
const fn divu_pair(x: u32, d: (u32, u32, u32)) -> u32 { |
| 150 |
let x = x as u64; |
| 151 |
let (a, b, shift) = d; |
| 152 |
let shift = shift as u64; |
| 153 |
let a = a as u64; |
| 154 |
let b = b as u64; |
| 155 |
|
| 156 |
(((a * x + b) >> 32) >> shift) as u32 |
| 157 |
} |
| 158 |
|
| 159 |
#[inline] |
| 160 |
const fn copysign(value: u32, signed: i32) -> i32 { |
| 161 |
if signed < 0 { |
| 162 |
-(value as i32) |
| 163 |
} else { |
| 164 |
value as i32 |
| 165 |
} |
| 166 |
} |
| 167 |
|
| 168 |
#[cfg(test)] |
| 169 |
mod test { |
| 170 |
use super::*; |
| 171 |
use crate::transform::TxSize::*; |
| 172 |
|
| 173 |
#[test] |
| 174 |
fn test_divu_pair() { |
| 175 |
for d in 1..1024 { |
| 176 |
for x in 0..1000 { |
| 177 |
let ab = divu_gen(NonZeroU32::new(d).unwrap()); |
| 178 |
assert_eq!(x / d, divu_pair(x, ab)); |
| 179 |
} |
| 180 |
} |
| 181 |
} |
| 182 |
#[test] |
| 183 |
fn gen_divu_table() { |
| 184 |
let b: Vec<(u32, u32, u32)> = |
| 185 |
dc_qlookup_Q3.iter().map(|&v| divu_gen(v.into())).collect(); |
| 186 |
|
| 187 |
println!("{:?}", b); |
| 188 |
} |
| 189 |
#[test] |
| 190 |
fn test_tx_log_scale() { |
| 191 |
let tx_sizes = [ |
| 192 |
(TX_4X4, 0), |
| 193 |
(TX_8X8, 0), |
| 194 |
(TX_16X16, 0), |
| 195 |
(TX_32X32, 1), |
| 196 |
(TX_64X64, 2), |
| 197 |
(TX_4X8, 0), |
| 198 |
(TX_8X4, 0), |
| 199 |
(TX_8X16, 0), |
| 200 |
(TX_16X8, 0), |
| 201 |
(TX_16X32, 1), |
| 202 |
(TX_32X16, 1), |
| 203 |
(TX_32X64, 2), |
| 204 |
(TX_64X32, 2), |
| 205 |
(TX_4X16, 0), |
| 206 |
(TX_16X4, 0), |
| 207 |
(TX_8X32, 0), |
| 208 |
(TX_32X8, 0), |
| 209 |
(TX_16X64, 1), |
| 210 |
(TX_64X16, 1), |
| 211 |
]; |
| 212 |
for &tx_size in tx_sizes.iter() { |
| 213 |
assert!(tx_size.1 == get_log_tx_scale(tx_size.0)); |
| 214 |
} |
| 215 |
} |
| 216 |
} |
| 217 |
|
| 218 |
impl QuantizationContext { |
| 219 |
pub fn update( |
| 220 |
&mut self, qindex: u8, tx_size: TxSize, is_intra: bool, bit_depth: usize, |
| 221 |
dc_delta_q: i8, ac_delta_q: i8, |
| 222 |
) { |
| 223 |
self.log_tx_scale = get_log_tx_scale(tx_size); |
| 224 |
|
| 225 |
self.dc_quant = dc_q(qindex, dc_delta_q, bit_depth); |
| 226 |
self.dc_mul_add = divu_gen(self.dc_quant.into()); |
| 227 |
|
| 228 |
self.ac_quant = ac_q(qindex, ac_delta_q, bit_depth); |
| 229 |
self.ac_mul_add = divu_gen(self.ac_quant.into()); |
| 230 |
|
| 231 |
// All of these biases were derived by measuring the cost of coding |
| 232 |
// a zero vs coding a one on any given coefficient position, or, in |
| 233 |
// the case of the EOB bias, the cost of coding the block with |
| 234 |
// the chosen EOB (rounding to one) vs rounding to zero and continuing |
| 235 |
// to choose a new EOB. This was done over several clips, with the |
| 236 |
// average of the bit costs taken over all blocks in the set, and a new |
| 237 |
// bias derived via the method outlined in Jean-Marc Valin's |
| 238 |
// Journal of Dubious Theoretical Results[1], aka: |
| 239 |
// |
| 240 |
// lambda = ln(2) / 6.0 |
| 241 |
// threshold = 0.5 + (lambda * avg_rate_diff) / 2.0 |
| 242 |
// bias = 1 - threshold |
| 243 |
// |
| 244 |
// lambda is a constant since our offsets are already adjusted for the |
| 245 |
// quantizer. |
| 246 |
// |
| 247 |
// Biases were then updated, and cost collection was re-run, until |
| 248 |
// the calculated biases started to converge after 2-4 iterations. |
| 249 |
// |
| 250 |
// In theory, the rounding biases for inter should be somewhat smaller |
| 251 |
// than the biases for intra, but this turns out to only be the case |
| 252 |
// for EOB optimization, or at least, is covered by EOB optimization. |
| 253 |
// The RD-optimal rounding biases for the actual coefficients seem |
| 254 |
// to be quite close (+/- 1/256), for both inter and intra, |
| 255 |
// post-deadzoning. |
| 256 |
// |
| 257 |
// [1] https://jmvalin.ca/notes/theoretical_results.pdf |
| 258 |
self.dc_offset = |
| 259 |
self.dc_quant.get() as u32 * (if is_intra { 109 } else { 108 }) / 256; |
| 260 |
self.ac_offset0 = |
| 261 |
self.ac_quant.get() as u32 * (if is_intra { 98 } else { 97 }) / 256; |
| 262 |
self.ac_offset1 = |
| 263 |
self.ac_quant.get() as u32 * (if is_intra { 109 } else { 108 }) / 256; |
| 264 |
self.ac_offset_eob = |
| 265 |
self.ac_quant.get() as u32 * (if is_intra { 88 } else { 44 }) / 256; |
| 266 |
} |
| 267 |
|
| 268 |
#[inline] |
| 269 |
pub fn quantize<T: Coefficient>( |
| 270 |
&self, coeffs: &[T], qcoeffs: &mut [T], tx_size: TxSize, tx_type: TxType, |
| 271 |
) -> u16 { |
| 272 |
let scan = av1_scan_orders[tx_size as usize][tx_type as usize].scan; |
| 273 |
let iscan = av1_scan_orders[tx_size as usize][tx_type as usize].iscan; |
| 274 |
|
| 275 |
qcoeffs[0] = { |
| 276 |
let coeff: i32 = i32::cast_from(coeffs[0]) << self.log_tx_scale; |
| 277 |
let abs_coeff = coeff.unsigned_abs(); |
| 278 |
T::cast_from(copysign( |
| 279 |
divu_pair(abs_coeff + self.dc_offset, self.dc_mul_add), |
| 280 |
coeff, |
| 281 |
)) |
| 282 |
}; |
| 283 |
|
| 284 |
// Find the last non-zero coefficient using our smaller biases and |
| 285 |
// zero everything else. |
| 286 |
// This threshold is such that `abs(coeff) < deadzone` implies: |
| 287 |
// (abs(coeff << log_tx_scale) + ac_offset_eob) / ac_quant == 0 |
| 288 |
let deadzone = T::cast_from( |
| 289 |
(self.ac_quant.get() as usize - self.ac_offset_eob as usize) |
| 290 |
.align_power_of_two_and_shift(self.log_tx_scale), |
| 291 |
); |
| 292 |
let eob = { |
| 293 |
let eob_minus_one = iscan |
| 294 |
.iter() |
| 295 |
.zip(coeffs) |
| 296 |
.map(|(&i, &c)| if c.abs() >= deadzone { i } else { 0 }) |
| 297 |
.max() |
| 298 |
.unwrap_or(0); |
| 299 |
// We skip the DC coefficient since it has its own quantizer index. |
| 300 |
if eob_minus_one > 0 { |
| 301 |
eob_minus_one + 1 |
| 302 |
} else { |
| 303 |
u16::from(qcoeffs[0] != T::cast_from(0)) |
| 304 |
} |
| 305 |
}; |
| 306 |
|
| 307 |
// Here we use different rounding biases depending on whether we've |
| 308 |
// had recent coefficients that are larger than one, or less than |
| 309 |
// one. The reason for this is that a block usually has a chunk of |
| 310 |
// large coefficients and a tail of zeroes and ones, and the tradeoffs |
| 311 |
// for coding these two are different. In the tail of zeroes and ones, |
| 312 |
// you'll likely end up spending most bits just saying where that |
| 313 |
// coefficient is in the block, whereas in the chunk of larger |
| 314 |
// coefficients, most bits will be spent on coding its magnitude. |
| 315 |
// To that end, we want to bias more toward rounding to zero for |
| 316 |
// that tail of zeroes and ones than we do for the larger coefficients. |
| 317 |
let mut level_mode = 1; |
| 318 |
let ac_quant = self.ac_quant.get() as u32; |
| 319 |
for &pos in scan.iter().take(usize::from(eob)).skip(1) { |
| 320 |
let coeff = i32::cast_from(coeffs[pos as usize]) << self.log_tx_scale; |
| 321 |
let abs_coeff = coeff.unsigned_abs(); |
| 322 |
|
| 323 |
let level0 = divu_pair(abs_coeff, self.ac_mul_add); |
| 324 |
let offset = if level0 > 1 - level_mode { |
| 325 |
self.ac_offset1 |
| 326 |
} else { |
| 327 |
self.ac_offset0 |
| 328 |
}; |
| 329 |
|
| 330 |
let abs_qcoeff: u32 = |
| 331 |
level0 + (abs_coeff + offset >= (level0 + 1) * ac_quant) as u32; |
| 332 |
if level_mode != 0 && abs_qcoeff == 0 { |
| 333 |
level_mode = 0; |
| 334 |
} else if abs_qcoeff > 1 { |
| 335 |
level_mode = 1; |
| 336 |
} |
| 337 |
|
| 338 |
qcoeffs[pos as usize] = T::cast_from(copysign(abs_qcoeff, coeff)); |
| 339 |
} |
| 340 |
|
| 341 |
// Rather than zeroing the tail in scan order, assume that qcoeffs is |
| 342 |
// pre-filled with zeros. |
| 343 |
|
| 344 |
// Check the eob is correct |
| 345 |
debug_assert_eq!( |
| 346 |
usize::from(eob), |
| 347 |
scan |
| 348 |
.iter() |
| 349 |
.rposition(|&i| qcoeffs[i as usize] != T::cast_from(0)) |
| 350 |
.map(|n| n + 1) |
| 351 |
.unwrap_or(0) |
| 352 |
); |
| 353 |
|
| 354 |
eob |
| 355 |
} |
| 356 |
} |
| 357 |
|
| 358 |
pub mod rust { |
| 359 |
use super::*; |
| 360 |
use crate::cpu_features::CpuFeatureLevel; |
| 361 |
use std::mem::MaybeUninit; |
| 362 |
|
| 363 |
pub fn dequantize<T: Coefficient>( |
| 364 |
qindex: u8, coeffs: &[T], _eob: u16, rcoeffs: &mut [MaybeUninit<T>], |
| 365 |
tx_size: TxSize, bit_depth: usize, dc_delta_q: i8, ac_delta_q: i8, |
| 366 |
_cpu: CpuFeatureLevel, |
| 367 |
) { |
| 368 |
let log_tx_scale = get_log_tx_scale(tx_size) as i32; |
| 369 |
let offset = (1 << log_tx_scale) - 1; |
| 370 |
|
| 371 |
let dc_quant = dc_q(qindex, dc_delta_q, bit_depth).get() as i32; |
| 372 |
let ac_quant = ac_q(qindex, ac_delta_q, bit_depth).get() as i32; |
| 373 |
|
| 374 |
for (i, (r, c)) in rcoeffs |
| 375 |
.iter_mut() |
| 376 |
.zip(coeffs.iter().map(|&c| i32::cast_from(c))) |
| 377 |
.enumerate() |
| 378 |
{ |
| 379 |
let quant = if i == 0 { dc_quant } else { ac_quant }; |
| 380 |
r.write(T::cast_from( |
| 381 |
(c * quant + ((c >> 31) & offset)) >> log_tx_scale, |
| 382 |
)); |
| 383 |
} |
| 384 |
} |
| 385 |
} |