binius_utils/
checked_arithmetics.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright (c) 2024 The Plonky3 Authors
3
4/// Division implementation that fails in case when `a`` isn't divisible by `b`
5pub const fn checked_int_div(a: usize, b: usize) -> usize {
6	let result = a / b;
7	assert!(b * result == a);
8
9	result
10}
11
12/// Computes binary logarithm of `val`.
13/// If `val` is not a power of 2, returns `None`.
14#[inline]
15#[must_use]
16pub const fn strict_log_2(val: usize) -> Option<usize> {
17	if val == 0 {
18		return None;
19	}
20
21	let pow = val.trailing_zeros();
22	if val.wrapping_shr(pow) == 1 {
23		Some(pow as usize)
24	} else {
25		None
26	}
27}
28
29/// log2 implementation that fails when `val` is not a power of 2.
30#[inline]
31#[must_use]
32pub const fn checked_log_2(val: usize) -> usize {
33	strict_log_2(val).expect("Value is not a power of 2")
34}
35
36/// Computes the binary logarithm of $n$ rounded up to the nearest integer.
37///
38/// When $n$ is 0, this function returns 0. Otherwise, it returns $\lceil \log_2 n \rceil$.
39#[must_use]
40pub const fn log2_ceil_usize(n: usize) -> usize {
41	min_bits(n.saturating_sub(1))
42}
43
44/// Returns the number of bits needed to represent $n$.
45///
46/// When $n$ is 0, this function returns 0. Otherwise, it returns $\lfloor \log_2 n \rfloor + 1$.
47#[must_use]
48pub const fn min_bits(n: usize) -> usize {
49	(usize::BITS - n.leading_zeros()) as usize
50}
51
52/// Computes `log_2(n)`
53///
54/// # Panics
55/// Panics if `n` is not a power of two.
56#[must_use]
57#[inline]
58pub fn log2_strict_usize(n: usize) -> usize {
59	let res = n.trailing_zeros();
60	assert_eq!(n.wrapping_shr(res), 1, "Not a power of two: {n}");
61	res as usize
62}
63
64#[cfg(test)]
65mod tests {
66	use super::*;
67
68	#[test]
69	fn test_checked_int_div_success() {
70		assert_eq!(checked_int_div(6, 1), 6);
71		assert_eq!(checked_int_div(6, 2), 3);
72		assert_eq!(checked_int_div(6, 6), 1);
73	}
74
75	#[test]
76	#[should_panic]
77	const fn test_checked_int_div_fail() {
78		_ = checked_int_div(5, 2);
79	}
80
81	#[test]
82	fn test_checked_log2_success() {
83		assert_eq!(checked_log_2(1), 0);
84		assert_eq!(checked_log_2(2), 1);
85		assert_eq!(checked_log_2(4), 2);
86		assert_eq!(checked_log_2(64), 6);
87	}
88
89	#[test]
90	#[should_panic]
91	const fn test_checked_log2_fail() {
92		_ = checked_log_2(6)
93	}
94}
binius_utils/checked_arithmetics.rs

binius_utils/
checked_arithmetics.rs
