evm_dex_pool/v3/
bit_math.rs

1//! ## Bit Math Library in Rust
2//!
3//! This module is a Rust port of the Solidity [BitMath library](https://github.com/uniswap/v3-core/blob/main/contracts/libraries/BitMath.sol).
4
5use alloy::primitives::Uint;
6
7/// Trait to associate bit math functions with [`Uint`] types.
8pub trait BitMath {
9    #[must_use]
10    fn most_significant_bit(self) -> usize;
11    #[must_use]
12    fn least_significant_bit(self) -> usize;
13}
14
15impl<const BITS: usize, const LIMBS: usize> BitMath for Uint<BITS, LIMBS> {
16    #[inline]
17    fn most_significant_bit(self) -> usize {
18        most_significant_bit(self)
19    }
20
21    #[inline]
22    fn least_significant_bit(self) -> usize {
23        least_significant_bit(self)
24    }
25}
26
27/// Returns the index of the most significant bit in a given [`Uint`].
28///
29/// ## Panics
30///
31/// Panics if the input is zero.
32#[inline]
33#[must_use]
34pub fn most_significant_bit<const BITS: usize, const LIMBS: usize>(x: Uint<BITS, LIMBS>) -> usize {
35    BITS - 1 - x.leading_zeros()
36}
37
38/// Returns the index of the least significant bit in a given [`Uint`].
39#[inline]
40#[must_use]
41pub fn least_significant_bit<const BITS: usize, const LIMBS: usize>(x: Uint<BITS, LIMBS>) -> usize {
42    x.trailing_zeros()
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48    use alloy::primitives::{uint, U256};
49
50    const ONE: U256 = uint!(1_U256);
51
52    #[test]
53    #[should_panic(expected = "overflow")]
54    fn most_significant_bit_throws_for_zero() {
55        let _ = most_significant_bit(U256::ZERO);
56    }
57
58    #[test]
59    fn test_most_significant_bit() {
60        for i in 0..=255 {
61            let x = ONE << i;
62            assert_eq!(most_significant_bit(x), i);
63        }
64        for i in 1..=255 {
65            let x = (ONE << i) - ONE;
66            assert_eq!(most_significant_bit(x), i - 1);
67        }
68        assert_eq!(most_significant_bit(U256::MAX), 255);
69    }
70
71    #[test]
72    fn test_least_significant_bit() {
73        for i in 0..=255 {
74            let x = ONE << i;
75            assert_eq!(least_significant_bit(x), i);
76        }
77        for i in 1..=255 {
78            let x = (ONE << i) - ONE;
79            assert_eq!(least_significant_bit(x), 0);
80        }
81        assert_eq!(least_significant_bit(U256::MAX), 0);
82    }
83}
evm_dex_pool/v3/bit_math.rs

evm_dex_pool/v3/
bit_math.rs
