brotli/enc/
util.rs

Help
1#![allow(clippy::excessive_precision)]
2
3use crate::enc::log_table_16::logs_16;
4use crate::enc::log_table_8::logs_8;
5
6#[cfg(feature = "float64")]
7pub type floatX = f64;
8
9#[cfg(not(feature = "float64"))]
10pub type floatX = f32;
11
12#[inline(always)]
13pub fn FastLog2u16(v: u16) -> floatX {
14    logs_16[v as usize]
15}
16
17#[cfg(feature = "std")]
18#[inline(always)]
19pub fn FastLog2(v: u64) -> floatX {
20    if v < 256 {
21        logs_8[v as usize]
22    } else {
23        (v as f32).log2() as floatX
24    }
25}
26
27#[cfg(not(feature = "std"))]
28#[inline(always)]
29pub fn FastLog2(v: u64) -> floatX {
30    if v < 256 {
31        logs_8[v as usize]
32    } else {
33        FastLog2u64(v)
34    }
35}
36
37#[cfg(feature = "std")]
38#[inline(always)]
39pub fn FastLog2f64(v: u64) -> floatX {
40    if v < 256 {
41        logs_8[v as usize]
42    } else {
43        (v as floatX).log2()
44    }
45}
46
47#[cfg(not(feature = "std"))]
48#[inline(always)]
49pub fn FastLog2f64(v: u64) -> floatX {
50    FastLog2(v) as floatX
51}
52
53#[inline]
54pub fn FastLog2u64(v: u64) -> floatX {
55    let bsr_8 = 56i8 - v.leading_zeros() as i8;
56    let offset = bsr_8 & -((bsr_8 >= 0) as i8);
57    (offset as floatX) + logs_8[(v >> offset) as usize]
58}
59
60#[inline(always)]
61pub fn FastLog2u32(v: i32) -> floatX {
62    let bsr_8 = 24i8 - v.leading_zeros() as i8;
63    let offset = bsr_8 & -((bsr_8 >= 0) as i8);
64    (offset as floatX) + logs_8[(v >> offset) as usize]
65}
66
67#[inline(always)]
68pub fn xFastLog2u16(v: u16) -> floatX {
69    let bsr_8 = 8i8 - v.leading_zeros() as i8;
70    let offset = (bsr_8 & -((bsr_8 >= 0) as i8));
71    (offset as floatX) + logs_8[(v >> offset) as usize]
72}
73
74#[cfg(feature = "std")]
75#[inline(always)]
76pub fn FastPow2(v: floatX) -> floatX {
77    (2 as floatX).powf(v)
78}
79
80#[cfg(not(feature = "std"))]
81#[inline(always)]
82pub fn FastPow2(v: floatX) -> floatX {
83    assert!(v >= 0 as floatX);
84    let round_down = v as i32;
85    let remainder = v - round_down as floatX;
86    let mut x = 1 as floatX;
87    // (1 + (x/n) * ln2) ^ n
88    // let n = 8
89    x += remainder * (0.693147180559945309417232121458 / 256.0) as floatX;
90    x *= x;
91    x *= x;
92    x *= x;
93    x *= x;
94    x *= x;
95    x *= x;
96    x *= x;
97    x *= x;
98
99    (1 << round_down) as floatX * x
100}
101
102#[inline(always)]
103pub fn Log2FloorNonZero(v: u64) -> u32 {
104    63u32 ^ v.leading_zeros()
105}
106
107#[cfg(test)]
108mod test {
109    fn baseline_log2_floor_non_zero(mut n: u64) -> u32 {
110        let mut result: u32 = 0;
111        while {
112            n >>= 1i32;
113            n
114        } != 0
115        {
116            result = result.wrapping_add(1);
117        }
118        result
119    }
120
121    #[test]
122    fn log2floor_non_zero_works() {
123        let examples = [
124            4u64,
125            254,
126            256,
127            1428,
128            25412509,
129            21350891256,
130            65536,
131            1258912591,
132            60968101,
133            1,
134            12589125190825,
135            105912059215091,
136            0,
137        ];
138        for example in examples.iter() {
139            let fast_version = super::Log2FloorNonZero(*example);
140            let baseline_version = baseline_log2_floor_non_zero(*example);
141            if *example != 0 {
142                // make sure we don't panic when computing...but don't care about result
143                assert_eq!(fast_version, baseline_version);
144            }
145        }
146    }
147    pub fn approx_eq(a: f64, b: f64, tol: f64) {
148        let mut t0 = a - b;
149        let mut t1 = b - a;
150        if t0 < 0.0 {
151            t0 = -t0;
152        }
153        if t1 < 0.0 {
154            t1 = -t1;
155        }
156        if (!(t1 < tol)) {
157            assert_eq!(a, b);
158        }
159        if (!(t0 < tol)) {
160            assert_eq!(a, b);
161        }
162    }
163    #[test]
164    fn fast_log2_works() {
165        let examples = [
166            4u64,
167            254,
168            256,
169            1428,
170            25412509,
171            21350891256,
172            65536,
173            1258912591,
174            60968101,
175            1,
176            12589125190825,
177            105912059215091,
178            0,
179        ];
180        let tol = [
181            0.00001, 0.0001, 0.0001, 0.005, 0.007, 0.008, 0.01, 0.01, 0.01, 0.000001, 0.01, 0.01,
182            0.0001,
183        ];
184        for (index, example) in examples.iter().enumerate() {
185            let fast_version = super::FastLog2(*example);
186            if *example != 0 {
187                // make sure we don't panic when computing...but don't care about result
188                let baseline_version = (*example as f64).log2();
189                approx_eq(fast_version as f64, baseline_version, tol[index]);
190            } else {
191                //assert_eq!(fast_version as f64, 0.0 as f64);
192            }
193        }
194    }
195}
brotli/enc/util.rs

brotli/enc/
util.rs
