binius_utils/
checked_arithmetics.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Copyright 2024-2025 Irreducible Inc.
// Copyright (c) 2024 The Plonky3 Authors

/// Division implementation that fails in case when `a`` isn't divisible by `b`
pub const fn checked_int_div(a: usize, b: usize) -> usize {
	let result = a / b;
	assert!(b * result == a);

	result
}

/// log2 implementation that fails when `val` is not a power of 2.
pub const fn checked_log_2(val: usize) -> usize {
	let result = val.ilog2();
	assert!(2usize.pow(result) == val);

	result as _
}

/// Computes `ceil(log_2(n))`.
#[must_use]
pub const fn log2_ceil_usize(n: usize) -> usize {
	(usize::BITS - n.saturating_sub(1).leading_zeros()) as usize
}

/// Computes `log_2(n)`
///
/// # Panics
/// Panics if `n` is not a power of two.
#[must_use]
#[inline]
pub fn log2_strict_usize(n: usize) -> usize {
	let res = n.trailing_zeros();
	assert_eq!(n.wrapping_shr(res), 1, "Not a power of two: {n}");
	res as usize
}

#[cfg(test)]
mod tests {
	use super::*;

	#[test]
	fn test_checked_int_div_success() {
		assert_eq!(checked_int_div(6, 1), 6);
		assert_eq!(checked_int_div(6, 2), 3);
		assert_eq!(checked_int_div(6, 6), 1);
	}

	#[test]
	#[should_panic]
	const fn test_checked_int_div_fail() {
		_ = checked_int_div(5, 2);
	}

	#[test]
	fn test_checked_log2_success() {
		assert_eq!(checked_log_2(1), 0);
		assert_eq!(checked_log_2(2), 1);
		assert_eq!(checked_log_2(4), 2);
		assert_eq!(checked_log_2(64), 6);
	}

	#[test]
	#[should_panic]
	const fn test_checked_log2_fail() {
		_ = checked_log_2(6)
	}
}