fixed_bigint/heapless/
bit_scan.rs

1//! Bit-scan traits for `HeaplessBigInt`: `HighestOne` / `LowestOne` (bit
2//! indices) and `IsolateHighestOne` / `IsolateLowestOne` (masks).
3//!
4//! `HighestOne` / `LowestOne` return a `u32` index (or `None` for zero), so
5//! there is no result width to preserve. The `Isolate*` masks return a value
6//! and are width-preserving: the single-bit result carries `self.len`
7//! (`one` is widened before the shift; the low-bit trick resolves at
8//! `max(len)`).
9//!
10//! `IsolateHighestOne` is P-generic in name only for parity with `FixedUInt`,
11//! but note the highest-bit path is not constant-time (the zero test and the
12//! shift amount both depend on the value). `IsolateLowestOne` uses the
13//! branchless `self & (0 - self)` trick.
14
15use super::HeaplessBigInt;
16use crate::MachineWord;
17use const_num_traits::{
18    HighestOne, IsolateHighestOne, IsolateLowestOne, LowestOne, One, Personality, PrimBits,
19    WrappingSub, Zero,
20};
21
22impl<T, const CAP: usize, P: Personality> HighestOne for HeaplessBigInt<T, CAP, P>
23where
24    T: MachineWord,
25{
26    fn highest_one(self) -> Option<u32> {
27        // Index of the highest set bit = bit_length - 1; zero has none.
28        let bl = self.bit_length();
29        if bl == 0 { None } else { Some(bl as u32 - 1) }
30    }
31}
32
33impl<T, const CAP: usize, P: Personality> LowestOne for HeaplessBigInt<T, CAP, P>
34where
35    T: MachineWord,
36{
37    fn lowest_one(self) -> Option<u32> {
38        if <Self as Zero>::is_zero(&self) {
39            None
40        } else {
41            Some(PrimBits::trailing_zeros(self))
42        }
43    }
44}
45
46impl<T, const CAP: usize, P: Personality> IsolateHighestOne for HeaplessBigInt<T, CAP, P>
47where
48    T: MachineWord,
49{
50    type Output = Self;
51    fn isolate_highest_one(self) -> Self {
52        match self.highest_one() {
53            // Zero has no set bit; return it unchanged (width-preserving).
54            None => self,
55            Some(pos) => {
56                <Self as One>::one().widened(core::cmp::max(1, self.len())) << (pos as usize)
57            }
58        }
59    }
60}
61
62impl<T, const CAP: usize, P: Personality> IsolateLowestOne for HeaplessBigInt<T, CAP, P>
63where
64    T: MachineWord,
65{
66    type Output = Self;
67    fn isolate_lowest_one(self) -> Self {
68        // `self & (-self)`: for unsigned, `-x == wrapping_sub(0, x)`. Works at
69        // `self.len` (the zero seed resolves up to it) and gives 0 for 0.
70        let neg = <Self as WrappingSub>::wrapping_sub(<Self as Zero>::zero(), self);
71        self & neg
72    }
73}
74
75// Reference-receiver mirrors (`&HeaplessBigInt`), so `(&h).highest_one()` etc.
76// resolve. `HeaplessBigInt` is `Copy`, so each delegates to the value impl on
77// `*self`.
78
79impl<T, const CAP: usize, P: Personality> HighestOne for &HeaplessBigInt<T, CAP, P>
80where
81    T: MachineWord,
82{
83    fn highest_one(self) -> Option<u32> {
84        <HeaplessBigInt<T, CAP, P> as HighestOne>::highest_one(*self)
85    }
86}
87
88impl<T, const CAP: usize, P: Personality> LowestOne for &HeaplessBigInt<T, CAP, P>
89where
90    T: MachineWord,
91{
92    fn lowest_one(self) -> Option<u32> {
93        <HeaplessBigInt<T, CAP, P> as LowestOne>::lowest_one(*self)
94    }
95}
96
97impl<T, const CAP: usize, P: Personality> IsolateHighestOne for &HeaplessBigInt<T, CAP, P>
98where
99    T: MachineWord,
100{
101    type Output = HeaplessBigInt<T, CAP, P>;
102    fn isolate_highest_one(self) -> HeaplessBigInt<T, CAP, P> {
103        <HeaplessBigInt<T, CAP, P> as IsolateHighestOne>::isolate_highest_one(*self)
104    }
105}
106
107impl<T, const CAP: usize, P: Personality> IsolateLowestOne for &HeaplessBigInt<T, CAP, P>
108where
109    T: MachineWord,
110{
111    type Output = HeaplessBigInt<T, CAP, P>;
112    fn isolate_lowest_one(self) -> HeaplessBigInt<T, CAP, P> {
113        <HeaplessBigInt<T, CAP, P> as IsolateLowestOne>::isolate_lowest_one(*self)
114    }
115}
116
117#[cfg(test)]
118mod tests {
119    use super::HeaplessBigInt;
120    use const_num_traits::{HighestOne, IsolateHighestOne, IsolateLowestOne, LowestOne};
121
122    type H = HeaplessBigInt<u8, 8>;
123
124    #[test]
125    fn indices() {
126        assert_eq!(HighestOne::highest_one(H::from(0u8)), None);
127        assert_eq!(HighestOne::highest_one(H::from(1u8)), Some(0));
128        assert_eq!(HighestOne::highest_one(H::from(0xB4u8)), Some(7));
129        assert_eq!(LowestOne::lowest_one(H::from(0u8)), None);
130        assert_eq!(LowestOne::lowest_one(H::from(0xB0u8)), Some(4));
131        assert_eq!(LowestOne::lowest_one(H::from(1u8)), Some(0));
132    }
133
134    #[test]
135    fn isolate_masks_and_width() {
136        // 0xB4 = 1011_0100: highest bit 7, lowest bit 2.
137        let v = H::from(0xB4u8).widened(8);
138        let hi = IsolateHighestOne::isolate_highest_one(v);
139        assert_eq!(hi, H::from(0x80u8));
140        assert_eq!(hi.len(), 8);
141        let lo = IsolateLowestOne::isolate_lowest_one(v);
142        assert_eq!(lo, H::from(0x04u8));
143        assert_eq!(lo.len(), 8);
144
145        // Zero isolates to zero, keeping its width.
146        let z = H::new_zero_with_len(8);
147        assert_eq!(IsolateHighestOne::isolate_highest_one(z).len(), 8);
148        assert_eq!(IsolateLowestOne::isolate_lowest_one(z).len(), 8);
149
150        // A len-0 operand stays len 0: `zero()` (the neg seed) is itself len 0,
151        // so `wrapping_sub`/`&` resolve at max(0, 0) = 0.
152        let z0 = H::new_zero_with_len(0);
153        assert_eq!(IsolateHighestOne::isolate_highest_one(z0).len(), 0);
154        assert_eq!(IsolateLowestOne::isolate_lowest_one(z0).len(), 0);
155    }
156
157    // The `&Self` mirrors agree with the value impls.
158    #[test]
159    fn by_ref_matches_value() {
160        let v = H::from(0xB4u8).widened(8);
161        let r = &v; // dispatch through the `&Self` mirror
162        assert_eq!(HighestOne::highest_one(r), HighestOne::highest_one(v));
163        assert_eq!(LowestOne::lowest_one(r), LowestOne::lowest_one(v));
164        assert_eq!(
165            IsolateHighestOne::isolate_highest_one(r),
166            IsolateHighestOne::isolate_highest_one(v)
167        );
168        assert_eq!(
169            IsolateLowestOne::isolate_lowest_one(r),
170            IsolateLowestOne::isolate_lowest_one(v)
171        );
172    }
173}
fixed_bigint/heapless/bit_scan.rs

fixed_bigint/heapless/
bit_scan.rs
