/src/rust-brotli/src/enc/util.rs

Source
#![allow(clippy::excessive_precision)]

use crate::enc::log_table_16::logs_16;
use crate::enc::log_table_8::logs_8;

#[cfg(feature = "float64")]
pub type floatX = f64;

#[cfg(not(feature = "float64"))]
pub type floatX = f32;

#[inline(always)]
pub fn FastLog2u16(v: u16) -> floatX {
    logs_16[v as usize]
}

#[cfg(feature = "std")]
#[inline(always)]
pub fn FastLog2(v: u64) -> floatX {
    if v < 256 {
        logs_8[v as usize]
    } else {
        (v as f32).log2() as floatX
    }
}

#[cfg(not(feature = "std"))]
#[inline(always)]
pub fn FastLog2(v: u64) -> floatX {
    if v < 256 {
        logs_8[v as usize]
    } else {
        FastLog2u64(v)
    }
}

#[cfg(feature = "std")]
#[inline(always)]
pub fn FastLog2f64(v: u64) -> floatX {
    if v < 256 {
        logs_8[v as usize]
    } else {
        (v as floatX).log2()
    }
}

#[cfg(not(feature = "std"))]
#[inline(always)]
pub fn FastLog2f64(v: u64) -> floatX {
    FastLog2(v) as floatX
}

#[inline]
pub fn FastLog2u64(v: u64) -> floatX {
    let bsr_8 = 56i8 - v.leading_zeros() as i8;
    let offset = bsr_8 & -((bsr_8 >= 0) as i8);
    (offset as floatX) + logs_8[(v >> offset) as usize]
}

#[inline(always)]
pub fn FastLog2u32(v: i32) -> floatX {
    let bsr_8 = 24i8 - v.leading_zeros() as i8;
    let offset = bsr_8 & -((bsr_8 >= 0) as i8);
    (offset as floatX) + logs_8[(v >> offset) as usize]
}

#[inline(always)]
pub fn xFastLog2u16(v: u16) -> floatX {
    let bsr_8 = 8i8 - v.leading_zeros() as i8;
    let offset = (bsr_8 & -((bsr_8 >= 0) as i8));
    (offset as floatX) + logs_8[(v >> offset) as usize]
}

#[cfg(feature = "std")]
#[inline(always)]
pub fn FastPow2(v: floatX) -> floatX {
    (2 as floatX).powf(v)
}

#[cfg(not(feature = "std"))]
#[inline(always)]
pub fn FastPow2(v: floatX) -> floatX {
    assert!(v >= 0 as floatX);
    let round_down = v as i32;
    let remainder = v - round_down as floatX;
    let mut x = 1 as floatX;
    // (1 + (x/n) * ln2) ^ n
    // let n = 8
    x += remainder * (0.693147180559945309417232121458 / 256.0) as floatX;
    x *= x;
    x *= x;
    x *= x;
    x *= x;
    x *= x;
    x *= x;
    x *= x;
    x *= x;

    (1 << round_down) as floatX * x
}

#[inline(always)]
pub fn Log2FloorNonZero(v: u64) -> u32 {
    63u32 ^ v.leading_zeros()
}

#[cfg(test)]
mod test {
    fn baseline_log2_floor_non_zero(mut n: u64) -> u32 {
        let mut result: u32 = 0;
        while {
            n >>= 1i32;
            n
        } != 0
        {
            result = result.wrapping_add(1);
        }
        result
    }

    #[test]
    fn log2floor_non_zero_works() {
        let examples = [
            4u64,
            254,
            256,
            1428,
            25412509,
            21350891256,
            65536,
            1258912591,
            60968101,
            1,
            12589125190825,
            105912059215091,
            0,
        ];
        for example in examples.iter() {
            let fast_version = super::Log2FloorNonZero(*example);
            let baseline_version = baseline_log2_floor_non_zero(*example);
            if *example != 0 {
                // make sure we don't panic when computing...but don't care about result
                assert_eq!(fast_version, baseline_version);
            }
        }
    }
    pub fn approx_eq(a: f64, b: f64, tol: f64) {
        let mut t0 = a - b;
        let mut t1 = b - a;
        if t0 < 0.0 {
            t0 = -t0;
        }
        if t1 < 0.0 {
            t1 = -t1;
        }
        if (!(t1 < tol)) {
            assert_eq!(a, b);
        }
        if (!(t0 < tol)) {
            assert_eq!(a, b);
        }
    }
    #[test]
    fn fast_log2_works() {
        let examples = [
            4u64,
            254,
            256,
            1428,
            25412509,
            21350891256,
            65536,
            1258912591,
            60968101,
            1,
            12589125190825,
            105912059215091,
            0,
        ];
        let tol = [
            0.00001, 0.0001, 0.0001, 0.005, 0.007, 0.008, 0.01, 0.01, 0.01, 0.000001, 0.01, 0.01,
            0.0001,
        ];
        for (index, example) in examples.iter().enumerate() {
            let fast_version = super::FastLog2(*example);
            if *example != 0 {
                // make sure we don't panic when computing...but don't care about result
                let baseline_version = (*example as f64).log2();
                approx_eq(fast_version as f64, baseline_version, tol[index]);
            } else {
                //assert_eq!(fast_version as f64, 0.0 as f64);
            }
        }
    }
}

Coverage Report

Created: 2026-02-26 07:28

Line	Count	Source
1		#![allow(clippy::excessive_precision)]
2
3		use crate::enc::log_table_16::logs_16;
4		use crate::enc::log_table_8::logs_8;
5
6		#[cfg(feature = "float64")]
7		pub type floatX = f64;
8
9		#[cfg(not(feature = "float64"))]
10		pub type floatX = f32;
11
12		#[inline(always)]
13	6.83G	pub fn FastLog2u16(v: u16) -> floatX {
14	6.83G	logs_16[v as usize]
15	6.83G	}
16
17		#[cfg(feature = "std")]
18		#[inline(always)]
19	557M	pub fn FastLog2(v: u64) -> floatX {
20	557M	if v < 256 {
21	515M	logs_8[v as usize]
22		} else {
23	41.7M	(v as f32).log2() as floatX
24		}
25	557M	}
26
27		#[cfg(not(feature = "std"))]
28		#[inline(always)]
29		pub 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)]
39	389M	pub fn FastLog2f64(v: u64) -> floatX {
40	389M	if v < 256 {
41	98.8M	logs_8[v as usize]
42		} else {
43	290M	(v as floatX).log2()
44		}
45	389M	}
46
47		#[cfg(not(feature = "std"))]
48		#[inline(always)]
49		pub fn FastLog2f64(v: u64) -> floatX {
50		FastLog2(v) as floatX
51		}
52
53		#[inline]
54	0	pub fn FastLog2u64(v: u64) -> floatX {
55	0	let bsr_8 = 56i8 - v.leading_zeros() as i8;
56	0	let offset = bsr_8 & -((bsr_8 >= 0) as i8);
57	0	(offset as floatX) + logs_8[(v >> offset) as usize]
58	0	}
59
60		#[inline(always)]
61	0	pub fn FastLog2u32(v: i32) -> floatX {
62	0	let bsr_8 = 24i8 - v.leading_zeros() as i8;
63	0	let offset = bsr_8 & -((bsr_8 >= 0) as i8);
64	0	(offset as floatX) + logs_8[(v >> offset) as usize]
65	0	}
66
67		#[inline(always)]
68	0	pub fn xFastLog2u16(v: u16) -> floatX {
69	0	let bsr_8 = 8i8 - v.leading_zeros() as i8;
70	0	let offset = (bsr_8 & -((bsr_8 >= 0) as i8));
71	0	(offset as floatX) + logs_8[(v >> offset) as usize]
72	0	}
73
74		#[cfg(feature = "std")]
75		#[inline(always)]
76	0	pub fn FastPow2(v: floatX) -> floatX {
77	0	(2 as floatX).powf(v)
78	0	}
79
80		#[cfg(not(feature = "std"))]
81		#[inline(always)]
82		pub 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)]
103	4.43G	pub fn Log2FloorNonZero(v: u64) -> u32 {
104	4.43G	63u32 ^ v.leading_zeros()
105	4.43G	}
106
107		#[cfg(test)]
108		mod 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		}