| 1 |
// Copyright (c) 2017-2020, 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 num_traits::PrimInt; |
| 11 |
use std::mem::size_of; |
| 12 |
|
| 13 |
pub trait Fixed { |
| 14 |
fn floor_log2(&self, n: usize) -> usize; |
| 15 |
fn ceil_log2(&self, n: usize) -> usize; |
| 16 |
fn align_power_of_two(&self, n: usize) -> usize; |
| 17 |
fn align_power_of_two_and_shift(&self, n: usize) -> usize; |
| 18 |
} |
| 19 |
|
| 20 |
impl Fixed for usize { |
| 21 |
#[inline] |
| 22 |
fn floor_log2(&self, n: usize) -> usize { |
| 23 |
self & !((1 << n) - 1) |
| 24 |
} |
| 25 |
#[inline] |
| 26 |
fn ceil_log2(&self, n: usize) -> usize { |
| 27 |
(self + (1 << n) - 1).floor_log2(n) |
| 28 |
} |
| 29 |
#[inline] |
| 30 |
fn align_power_of_two(&self, n: usize) -> usize { |
| 31 |
self.ceil_log2(n) |
| 32 |
} |
| 33 |
#[inline] |
| 34 |
fn align_power_of_two_and_shift(&self, n: usize) -> usize { |
| 35 |
(self + (1 << n) - 1) >> n |
| 36 |
} |
| 37 |
} |
| 38 |
|
| 39 |
pub fn clamp<T: PartialOrd>(input: T, min: T, max: T) -> T { |
| 40 |
if input < min { |
| 41 |
min |
| 42 |
} else if input > max { |
| 43 |
max |
| 44 |
} else { |
| 45 |
input |
| 46 |
} |
| 47 |
} |
| 48 |
|
| 49 |
pub trait ILog: PrimInt { |
| 50 |
// Integer binary logarithm of an integer value. |
| 51 |
// Returns floor(log2(self)) + 1, or 0 if self == 0. |
| 52 |
// This is the number of bits that would be required to represent self in two's |
| 53 |
// complement notation with all of the leading zeros stripped. |
| 54 |
// TODO: Mark const once trait functions can be constant |
| 55 |
fn ilog(self) -> usize { |
| 56 |
size_of::<Self>() * 8 - self.leading_zeros() as usize |
| 57 |
} |
| 58 |
} |
| 59 |
|
| 60 |
impl<T> ILog for T where T: PrimInt {} |
| 61 |
|
| 62 |
#[inline(always)] |
| 63 |
pub fn msb(x: i32) -> i32 { |
| 64 |
debug_assert!(x > 0); |
| 65 |
31 ^ (x.leading_zeros() as i32) |
| 66 |
} |
| 67 |
|
| 68 |
#[inline(always)] |
| 69 |
pub const fn round_shift(value: i32, bit: usize) -> i32 { |
| 70 |
(value + (1 << bit >> 1)) >> bit |
| 71 |
} |
| 72 |
|
| 73 |
#[cfg(test)] |
| 74 |
mod tests { |
| 75 |
use super::*; |
| 76 |
|
| 77 |
#[test] |
| 78 |
fn test_floor_log2() { |
| 79 |
assert_eq!(123usize.floor_log2(4), 112); |
| 80 |
assert_eq!(16usize.floor_log2(4), 16); |
| 81 |
assert_eq!(0usize.floor_log2(4), 0); |
| 82 |
} |
| 83 |
|
| 84 |
#[test] |
| 85 |
fn test_ceil_log2() { |
| 86 |
assert_eq!(123usize.ceil_log2(4), 128); |
| 87 |
assert_eq!(16usize.ceil_log2(4), 16); |
| 88 |
assert_eq!(0usize.ceil_log2(4), 0); |
| 89 |
} |
| 90 |
|
| 91 |
#[test] |
| 92 |
fn test_align_power_of_two() { |
| 93 |
assert_eq!(123usize.align_power_of_two(4), 128); |
| 94 |
assert_eq!(16usize.align_power_of_two(4), 16); |
| 95 |
assert_eq!(0usize.align_power_of_two(4), 0); |
| 96 |
} |
| 97 |
|
| 98 |
#[test] |
| 99 |
fn test_align_power_of_two_and_shift() { |
| 100 |
assert_eq!(123usize.align_power_of_two_and_shift(4), 8); |
| 101 |
assert_eq!(16usize.align_power_of_two_and_shift(4), 1); |
| 102 |
assert_eq!(0usize.align_power_of_two_and_shift(4), 0); |
| 103 |
} |
| 104 |
|
| 105 |
#[test] |
| 106 |
fn test_clamp() { |
| 107 |
assert_eq!(clamp(5, 0, 10), 5); |
| 108 |
assert_eq!(clamp(-1, 0, 10), 0); |
| 109 |
assert_eq!(clamp(11, 0, 10), 10); |
| 110 |
} |
| 111 |
|
| 112 |
#[test] |
| 113 |
fn test_ilog() { |
| 114 |
assert_eq!(ILog::ilog(0i32), 0); |
| 115 |
assert_eq!(ILog::ilog(1i32), 1); |
| 116 |
assert_eq!(ILog::ilog(2i32), 2); |
| 117 |
assert_eq!(ILog::ilog(3i32), 2); |
| 118 |
assert_eq!(ILog::ilog(4i32), 3); |
| 119 |
} |
| 120 |
|
| 121 |
#[test] |
| 122 |
fn test_msb() { |
| 123 |
assert_eq!(msb(1), 0); |
| 124 |
assert_eq!(msb(2), 1); |
| 125 |
assert_eq!(msb(3), 1); |
| 126 |
assert_eq!(msb(4), 2); |
| 127 |
} |
| 128 |
|
| 129 |
#[test] |
| 130 |
fn test_round_shift() { |
| 131 |
assert_eq!(round_shift(7, 2), 2); |
| 132 |
assert_eq!(round_shift(8, 2), 2); |
| 133 |
assert_eq!(round_shift(9, 2), 2); |
| 134 |
assert_eq!(round_shift(10, 2), 3); |
| 135 |
} |
| 136 |
} |