fixed_bigint/heapless/
prim_bits.rs

1//! `const_num_traits::PrimBits` for `HeaplessBigInt` — the bit-operation
2//! vocabulary (count / scan / rotate / reverse / byte-swap / shift),
3//! personality-generic.
4//!
5//! Every width-sensitive member operates over the value width
6//! (`len·word_bits`), never `CAP`: a value at `len = k` returns exactly
7//! what the same-width `FixedUInt<T, k>` returns. `count_ones`/`count_zeros`
8//! are uniform across personalities (any CT weakness in `T::count_ones` is
9//! inherited by both, same as `FixedUInt`); `leading_zeros`/`trailing_zeros`
10//! branch on `P::TAG` and share `FixedUInt`'s `black_box`-guarded Ct scans.
11//! `leading_ones`/`trailing_ones` use the trait defaults (`(!self).*_zeros()`),
12//! which are correct given the value-width `Not`.
13//!
14//! `pow` and the `num_traits::PrimInt` bridge are deliberately absent:
15//! `PrimInt` supertrait-requires `CheckedDiv`/`Saturating`/`Num`, which
16//! `HeaplessBigInt` does not implement yet.
17
18use super::{HeaplessBigInt, is_zero, zero};
19use crate::MachineWord;
20use const_num_traits::{Bounded, Personality, PersonalityTag, PrimBits};
21use core::marker::PhantomData;
22
23/// Value width in bits (`len·word_bits`) — the width every PrimBits member
24/// operates over. `len <= u16::MAX` and `word_bits <= 64`, so it fits `u32`.
25#[inline]
26fn value_bits<T: MachineWord, const CAP: usize, P: Personality>(
27    v: &HeaplessBigInt<T, CAP, P>,
28) -> u32 {
29    v.len as u32 * (core::mem::size_of::<T>() as u32 * 8)
30}
31
32/// Fixed-width zero at a given `len` (all `CAP` limbs zero).
33#[inline]
34fn zero_at<T: MachineWord, const CAP: usize, P: Personality>(
35    len: u16,
36) -> HeaplessBigInt<T, CAP, P> {
37    HeaplessBigInt {
38        limbs: [zero::<T>(); CAP],
39        len,
40        _p: PhantomData,
41    }
42}
43
44impl<T: MachineWord, const CAP: usize, P: Personality> PrimBits for HeaplessBigInt<T, CAP, P> {
45    fn count_ones(self) -> u32 {
46        let n = self.len as usize;
47        let mut count = 0u32;
48        for &w in &self.limbs[..n] {
49            count += w.count_ones();
50        }
51        count
52    }
53
54    fn count_zeros(self) -> u32 {
55        let n = self.len as usize;
56        let mut count = 0u32;
57        for &w in &self.limbs[..n] {
58            count += w.count_zeros();
59        }
60        count
61    }
62
63    fn leading_zeros(self) -> u32 {
64        // Delegate to the inherent `leading_zeros` (bits.rs), which handles
65        // both personalities at value width. The `&self` borrow is required,
66        // not needless — it selects the inherent `&self` method; without it,
67        // method resolution picks this by-value trait method and recurses.
68        #[allow(clippy::needless_borrow)]
69        let lz = (&self).leading_zeros();
70        lz as u32
71    }
72
73    fn trailing_zeros(self) -> u32 {
74        let n = self.len as usize;
75        match P::TAG {
76            PersonalityTag::Nct => {
77                // LSB-to-MSB; stop at the first non-zero limb. Iterating the
78                // slice keeps the loop bounds-check-free.
79                let mut ret = 0u32;
80                for &v in &self.limbs[..n] {
81                    ret += <T as PrimBits>::trailing_zeros(v);
82                    if !is_zero(&v) {
83                        break;
84                    }
85                }
86                ret
87            }
88            // Shared full-width branchless scan (see `const_trailing_zeros_ct`).
89            PersonalityTag::Ct => {
90                let s = self.limbs.get(..n).unwrap_or(&self.limbs);
91                crate::fixeduint::const_trailing_zeros_ct(s)
92            }
93        }
94    }
95
96    fn swap_bytes(self) -> Self {
97        // Reverse limb order over the value width, each limb byte-swapped.
98        let n = self.len as usize;
99        let mut limbs = [zero::<T>(); CAP];
100        for (o, i) in limbs[..n].iter_mut().zip(self.limbs[..n].iter().rev()) {
101            *o = i.swap_bytes();
102        }
103        Self {
104            limbs,
105            len: self.len,
106            _p: PhantomData,
107        }
108    }
109
110    fn reverse_bits(self) -> Self {
111        // Reverse limb order and every limb's bits, over the value width.
112        let n = self.len as usize;
113        let mut limbs = [zero::<T>(); CAP];
114        for (o, i) in limbs[..n].iter_mut().rev().zip(self.limbs[..n].iter()) {
115            *o = i.reverse_bits();
116        }
117        Self {
118            limbs,
119            len: self.len,
120            _p: PhantomData,
121        }
122    }
123
124    fn rotate_left(self, n: u32) -> Self {
125        let bits = value_bits(&self);
126        if bits == 0 {
127            return self;
128        }
129        let shift = n % bits;
130        if shift == 0 {
131            return self;
132        }
133        // `shift` and `bits - shift` are both in `1..bits` (< u16::MAX·64),
134        // so the usize casts are lossless even where `usize` is 16-bit.
135        let a = self << shift as usize;
136        let b = self >> (bits - shift) as usize;
137        a | b
138    }
139
140    fn rotate_right(self, n: u32) -> Self {
141        let bits = value_bits(&self);
142        if bits == 0 {
143            return self;
144        }
145        let shift = n % bits;
146        if shift == 0 {
147            return self;
148        }
149        let a = self >> shift as usize;
150        let b = self << (bits - shift) as usize;
151        a | b
152    }
153
154    fn unsigned_shl(self, n: u32) -> Self {
155        // Shifting by >= the value width clears it. The guard also keeps the
156        // `as usize` cast below lossless on a 16-bit-`usize` target.
157        if n >= value_bits(&self) {
158            return zero_at(self.len);
159        }
160        self << n as usize
161    }
162
163    fn unsigned_shr(self, n: u32) -> Self {
164        if n >= value_bits(&self) {
165            return zero_at(self.len);
166        }
167        // `>>` narrows `len` on whole-word shifts, but PrimBits is fixed-width:
168        // restore the operand width so downstream width-sensitive ops
169        // (count_zeros, leading_zeros) match FixedUInt. The freed high limbs
170        // are already zero, so bumping `len` back is value-preserving.
171        let mut r = self >> n as usize;
172        r.len = self.len;
173        r
174    }
175
176    fn signed_shl(self, n: u32) -> Self {
177        // Unsigned carrier: identical to unsigned_shl (mirrors FixedUInt).
178        <Self as PrimBits>::unsigned_shl(self, n)
179    }
180
181    fn signed_shr(self, n: u32) -> Self {
182        // Arithmetic (sign-extending) right shift over the value width
183        // (`len·word_bits`), matching FixedUInt: the vacated top bits take the
184        // MSB. Branchless on the value — the sign bit is spread to a full-width
185        // mask via `bit * MAX` — and width-preserving, like `unsigned_shr`. The
186        // fill `sign_full ^ (sign_full >> n)` is the top-`n` sign bits when the
187        // MSB is set and zero otherwise, so a non-negative value shifts
188        // identically to `unsigned_shr`.
189        let logical = <Self as PrimBits>::unsigned_shr(self, n);
190        let len = self.len as usize;
191        if len == 0 {
192            return logical;
193        }
194        let word_bits = core::mem::size_of::<T>() * 8;
195        let sign_bit = self.limbs[len - 1] >> (word_bits - 1);
196        let mask_word = <T as core::ops::Mul>::mul(sign_bit, <T as Bounded>::max_value());
197        let mut sign_full = self;
198        let mut i = 0;
199        while i < len {
200            sign_full.limbs[i] = mask_word;
201            i += 1;
202        }
203        let sf_shr = <Self as PrimBits>::unsigned_shr(sign_full, n);
204        let mut result = logical;
205        let mut i = 0;
206        while i < len {
207            let fill = mask_word ^ sf_shr.limbs[i];
208            result.limbs[i] = logical.limbs[i] | fill;
209            i += 1;
210        }
211        result
212    }
213
214    // Little-endian host: in-memory order already matches, so to/from_le are
215    // no-ops and to/from_be byte-swap. Big-endian hosts unsupported, same as
216    // FixedUInt.
217    fn from_be(x: Self) -> Self {
218        x.swap_bytes()
219    }
220
221    fn from_le(x: Self) -> Self {
222        x
223    }
224
225    fn to_be(self) -> Self {
226        self.swap_bytes()
227    }
228
229    fn to_le(self) -> Self {
230        self
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237    use crate::FixedUInt;
238    use const_num_traits::{Ct, Nct};
239
240    // Differential: at width N, HeaplessBigInt<u32, CAP> carried at len = N
241    // must return exactly what FixedUInt<u32, N> returns for every PrimBits
242    // member. FixedUInt is the trusted reference.
243    fn assert_parity<const CAP: usize, const N: usize>(
244        h: HeaplessBigInt<u32, CAP, Nct>,
245        f: FixedUInt<u32, N, Nct>,
246    ) {
247        assert_eq!(h.len as usize, N, "test pattern must fill exactly N limbs");
248        assert_eq!(
249            PrimBits::count_ones(h),
250            PrimBits::count_ones(f),
251            "count_ones"
252        );
253        assert_eq!(
254            PrimBits::count_zeros(h),
255            PrimBits::count_zeros(f),
256            "count_zeros"
257        );
258        assert_eq!(PrimBits::leading_zeros(h), PrimBits::leading_zeros(f), "lz");
259        assert_eq!(
260            PrimBits::trailing_zeros(h),
261            PrimBits::trailing_zeros(f),
262            "tz"
263        );
264        assert_eq!(PrimBits::leading_ones(h), PrimBits::leading_ones(f), "lo");
265        assert_eq!(PrimBits::trailing_ones(h), PrimBits::trailing_ones(f), "to");
266        assert_eq!(
267            &PrimBits::swap_bytes(h).limbs[..N],
268            &PrimBits::swap_bytes(f).array[..]
269        );
270        assert_eq!(
271            &PrimBits::reverse_bits(h).limbs[..N],
272            &PrimBits::reverse_bits(f).array[..]
273        );
274        assert_eq!(
275            &PrimBits::to_be(h).limbs[..N],
276            &PrimBits::to_be(f).array[..]
277        );
278        assert_eq!(
279            &PrimBits::from_be(h).limbs[..N],
280            &PrimBits::from_be(f).array[..]
281        );
282        assert_eq!(&(!h).limbs[..N], &(!f).array[..], "not");
283        for k in [0u32, 1, 5, 31, 33, 100, 255] {
284            assert_eq!(
285                &PrimBits::rotate_left(h, k).limbs[..N],
286                &PrimBits::rotate_left(f, k).array[..],
287                "rotl {k}"
288            );
289            assert_eq!(
290                &PrimBits::rotate_right(h, k).limbs[..N],
291                &PrimBits::rotate_right(f, k).array[..],
292                "rotr {k}"
293            );
294            assert_eq!(
295                &PrimBits::unsigned_shl(h, k).limbs[..N],
296                &PrimBits::unsigned_shl(f, k).array[..],
297                "ushl {k}"
298            );
299            assert_eq!(
300                &PrimBits::unsigned_shr(h, k).limbs[..N],
301                &PrimBits::unsigned_shr(f, k).array[..],
302                "ushr {k}"
303            );
304            assert_eq!(
305                &PrimBits::signed_shr(h, k).limbs[..N],
306                &PrimBits::signed_shr(f, k).array[..],
307                "sshr {k}"
308            );
309        }
310    }
311
312    // Full-width parity across both carriers lives in the generic
313    // `tests/carrier_generic.rs` harness (`prim_bits_bit_vocabulary`). What
314    // stays here is heapless-only: the sub-capacity value-width guarantee and
315    // the Ct-scan behavior, neither of which the fixed-width harness can reach.
316    #[test]
317    fn parity_sub_capacity_is_value_width() {
318        // 8 bytes → len 2 inside a CAP-8 carrier. Must mirror FixedUInt<u32,2>,
319        // NOT the CAP-8 width: this is the value-width guarantee.
320        let b = [0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0x80];
321        assert_parity(
322            HeaplessBigInt::<u32, 8, Nct>::from_le_bytes(&b),
323            FixedUInt::<u32, 2, Nct>::from_le_bytes(&b),
324        );
325    }
326
327    #[test]
328    fn shr_preserves_value_width() {
329        // PrimBits shifts are fixed-width, unlike the `>>` operator which
330        // narrows `len` on whole-word shifts. Without width preservation,
331        // count_zeros/leading_zeros after the shift report the wrong width.
332        let h = HeaplessBigInt::<u32, 8, Nct>::from_le_bytes(&[0, 0, 0, 0, 0, 0, 0, 0x80]); // len 2
333        let f = FixedUInt::<u32, 2, Nct>::from_le_bytes(&[0, 0, 0, 0, 0, 0, 0, 0x80]);
334        let hs = PrimBits::unsigned_shr(h, 32);
335        assert_eq!(hs.len, 2, "shr must preserve the operand width");
336        assert_eq!(
337            PrimBits::count_zeros(hs),
338            PrimBits::count_zeros(f >> 32usize)
339        );
340        assert_eq!(
341            PrimBits::leading_zeros(hs),
342            PrimBits::leading_zeros(f >> 32usize)
343        );
344        // Over-shift clears to a fixed-width zero, not a narrowed one.
345        let hz = PrimBits::unsigned_shr(h, 999);
346        assert_eq!(hz.len, 2);
347        assert_eq!(PrimBits::count_zeros(hz), 64);
348    }
349
350    #[test]
351    fn ct_scans_match_nct() {
352        // The Ct personality's full-width scans return the same magnitude as
353        // Nct for the same value (they differ only in timing).
354        let b = [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x80];
355        let hn = HeaplessBigInt::<u32, 8, Nct>::from_le_bytes(&b);
356        let hc = HeaplessBigInt::<u32, 8, Ct>::from_le_bytes(&b);
357        assert_eq!(PrimBits::trailing_zeros(hc), PrimBits::trailing_zeros(hn));
358        assert_eq!(PrimBits::leading_zeros(hc), PrimBits::leading_zeros(hn));
359        assert_eq!(PrimBits::count_ones(hc), PrimBits::count_ones(hn));
360    }
361
362    #[test]
363    fn not_is_value_width() {
364        // !x over one limb: 0x0000_00FF → 0xFFFF_FF00, len stays 1.
365        let x = HeaplessBigInt::<u32, 8, Nct>::from_le_bytes(&[0xFF]);
366        let n = !x;
367        assert_eq!(n.len, 1);
368        assert_eq!(n.limbs[0], 0xFFFF_FF00);
369    }
370}
fixed_bigint/heapless/prim_bits.rs

fixed_bigint/heapless/
prim_bits.rs
