| 1 |
// Copyright (c) 2019-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 |
use crate::ec::rust; |
| 11 |
#[cfg(target_arch = "x86_64")] |
| 12 |
use std::arch::x86_64::*; |
| 13 |
|
| 14 |
#[inline(always)] |
| 15 |
pub fn update_cdf<const N: usize>(cdf: &mut [u16; N], val: u32) { |
| 16 |
if cdf.len() == 4 { |
| 17 |
// SAFETY: Calls Assembly code, which is only valid when the length of |
| 18 |
// `cdf` is 4. |
| 19 |
return unsafe { |
| 20 |
update_cdf_4_sse2(cdf, val); |
| 21 |
}; |
| 22 |
} |
| 23 |
|
| 24 |
rust::update_cdf(cdf, val); |
| 25 |
} |
| 26 |
|
| 27 |
#[target_feature(enable = "sse2")] |
| 28 |
#[inline] |
| 29 |
unsafe fn update_cdf_4_sse2(cdf: &mut [u16], val: u32) { |
| 30 |
let nsymbs = 4; |
| 31 |
let rate = 5 + (cdf[nsymbs - 1] >> 4) as usize; |
| 32 |
let count = cdf[nsymbs - 1] + (cdf[nsymbs - 1] < 32) as u16; |
| 33 |
|
| 34 |
// A bit of explanation of what is happening down here. First of all, let's look at the simple |
| 35 |
// implementation: |
| 36 |
// |
| 37 |
// ``` |
| 38 |
// if i as u32 >= val { |
| 39 |
// *v -= *v >> rate; |
| 40 |
// } else { |
| 41 |
// *v += (32768 - *v) >> rate; |
| 42 |
// } |
| 43 |
// ``` |
| 44 |
// |
| 45 |
// We want to perform the same arithmetic operation in the two branches, therefore we can |
| 46 |
// transform in something like: |
| 47 |
// |
| 48 |
// ``` |
| 49 |
// if i as u32 >= val { |
| 50 |
// *v -= *v >> rate; |
| 51 |
// } else { |
| 52 |
// *v -= -((32768 - *v) >> rate); |
| 53 |
// } |
| 54 |
// ``` |
| 55 |
// |
| 56 |
// It is possible to bring the "minus" for the second branch logically before the right shift |
| 57 |
// using the following rule: |
| 58 |
// -(x >> y) = (-1 - x) >> y + 1 |
| 59 |
// So we obtain |
| 60 |
// |
| 61 |
// ``` |
| 62 |
// if i as u32 >= val { |
| 63 |
// *v -= *v >> rate; |
| 64 |
// } else { |
| 65 |
// *v -= (-1 - (32768 - *v)) >> rate + 1; |
| 66 |
// } |
| 67 |
// ``` |
| 68 |
// |
| 69 |
// Good. A range `0..4` can be compared against `val` in order to have a starting point to work |
| 70 |
// in different ways on the two branches. `cmplt` returns `-1` if `lhs < rhs`, 0 otherwise. |
| 71 |
// It is possible to use the `avg` SIMD operator, which performs `(lhs + rhs + 1) >> 1`. This is |
| 72 |
// useful because `avg` treats numbers as unsigned, `-1 = 0xFFFF`, therefore `(0xFFFF + 0 + 1) >> |
| 73 |
// 1 = 0x8000 = 32768`. Obviously `(0 + 0 + 1) >> 1 = 0`. |
| 74 |
// |
| 75 |
// Now the result of `cmplt` can be used along with the result from `avg` and the data in `cdf` |
| 76 |
// in order to obtain the right hand side of the subtraction from `cdf`. |
| 77 |
|
| 78 |
let val_splat = _mm_set1_epi16(val as i16); |
| 79 |
let indices = _mm_set_epi16(0, 0, 0, 0, 3, 2, 1, 0); |
| 80 |
let index_lt_val = _mm_cmplt_epi16(indices, val_splat); |
| 81 |
let k = _mm_avg_epu16(index_lt_val, _mm_setzero_si128()); |
| 82 |
let cdf_simd = _mm_loadl_epi64(cdf.as_mut_ptr() as *const __m128i); |
| 83 |
let k_minus_v = _mm_sub_epi16(k, cdf_simd); |
| 84 |
let negated_if_lt_val = _mm_sub_epi16(index_lt_val, k_minus_v); |
| 85 |
let shifted = |
| 86 |
_mm_sra_epi16(negated_if_lt_val, _mm_set_epi32(0, 0, 0, rate as i32)); |
| 87 |
let fixed_if_lt_val = _mm_sub_epi16(shifted, index_lt_val); |
| 88 |
let result = _mm_sub_epi16(cdf_simd, fixed_if_lt_val); |
| 89 |
|
| 90 |
_mm_storel_epi64(cdf.as_mut_ptr() as *mut __m128i, result); |
| 91 |
cdf[nsymbs - 1] = count; |
| 92 |
} |
| 93 |
|
| 94 |
#[cfg(test)] |
| 95 |
mod test { |
| 96 |
use crate::ec::rust; |
| 97 |
|
| 98 |
#[test] |
| 99 |
fn update_cdf_4_sse2() { |
| 100 |
let mut cdf = [7296, 3819, 1616, 0]; |
| 101 |
let mut cdf2 = [7296, 3819, 1616, 0]; |
| 102 |
for i in 0..4 { |
| 103 |
rust::update_cdf(&mut cdf, i); |
| 104 |
// SAFETY: We are only testing on cdfs of size 4 |
| 105 |
unsafe { |
| 106 |
super::update_cdf_4_sse2(&mut cdf2, i); |
| 107 |
} |
| 108 |
assert_eq!(cdf, cdf2); |
| 109 |
} |
| 110 |
|
| 111 |
let mut cdf = [7297, 3820, 1617, 0]; |
| 112 |
let mut cdf2 = cdf; |
| 113 |
for i in 0..4 { |
| 114 |
rust::update_cdf(&mut cdf, i); |
| 115 |
// SAFETY: We are only testing on cdfs of size 4 |
| 116 |
unsafe { |
| 117 |
super::update_cdf_4_sse2(&mut cdf2, i); |
| 118 |
} |
| 119 |
assert_eq!(cdf, cdf2); |
| 120 |
} |
| 121 |
} |
| 122 |
} |