fixed_bigint/heapless/
bits.rs

1//! `bit_length` and `leading_zeros` for `HeaplessBigInt`.
2//!
3//! Both dispatch on `P` like `FixedUInt`: `Nct` scans MSB-to-LSB and
4//! stops at the highest non-zero limb; `Ct` scans the full width with an
5//! `undecided` lock so the loop is value-independent (mirroring
6//! `const_leading_zeros_ct`). The returned count is the magnitude either
7//! way — a caller that must keep the magnitude secret does not call these.
8//!
9//! `bit_length` is the position of the highest set bit plus one, so
10//! `bit_length(0) == 0` and `bit_length(1) == 1`. `leading_zeros` is
11//! taken against the value's **width** (`len * word_bits`), not capacity
12//! — so `bit_length + leading_zeros == bits_precision()` and `CAP` never
13//! enters. A caller that wants zeros relative to a wider window sizes it
14//! from that window's own `bits_precision`, not this value's capacity.
15
16use super::HeaplessBigInt;
17use crate::MachineWord;
18use const_num_traits::{Personality, PersonalityTag};
19
20impl<T: MachineWord, const CAP: usize, P: Personality> HeaplessBigInt<T, CAP, P> {
21    /// Number of bits needed to represent the value: `0` for zero,
22    /// otherwise the position of the highest set bit plus one.
23    pub fn bit_length(&self) -> usize {
24        let width = self.len as usize * core::mem::size_of::<T>() * 8;
25        width - self.leading_zeros()
26    }
27
28    /// Leading zeros against the value's width (`len * word_bits`), so
29    /// `leading_zeros + bit_length == bits_precision()`. A `len = 0`
30    /// value has width 0, hence `leading_zeros() == 0`.
31    pub fn leading_zeros(&self) -> usize {
32        let word_bits = core::mem::size_of::<T>() * 8;
33        match P::TAG {
34            // MSB-to-LSB; the first non-zero limb fixes the count and the
35            // invariant guarantees limbs above it are zero. Zero words above
36            // that limb contribute a full `word_bits` each.
37            PersonalityTag::Nct => {
38                let len = self.len as usize;
39                let mut i = len;
40                while i > 0 {
41                    i -= 1;
42                    let limb = self.limbs[i];
43                    if !super::is_zero(&limb) {
44                        return (len - 1 - i) * word_bits + limb.leading_zeros() as usize;
45                    }
46                }
47                len * word_bits
48            }
49            // Full scan: accumulate each limb's leading-zero contribution
50            // until a non-zero limb locks `decided`; later limbs add 0.
51            PersonalityTag::Ct => {
52                let mut total = 0usize;
53                let mut decided = 0usize;
54                let mut i = self.len as usize;
55                while i > 0 {
56                    i -= 1;
57                    let v = self.limbs[i];
58                    let v_lz = v.leading_zeros() as usize;
59                    let undecided = core::hint::black_box(!decided);
60                    total += undecided & v_lz;
61                    let v_nz_mask =
62                        core::hint::black_box(((!super::is_zero(&v)) as usize).wrapping_neg());
63                    decided |= v_nz_mask;
64                }
65                total
66            }
67        }
68    }
69}
70
71// ── const_num_traits::BitWidth (bit-length) / BitsPrecision (width) ──
72//
73// Two distinct quantities (bit-vocabulary canon): `bit_width` is the
74// significant-bit count (per-value magnitude); `bits_precision` is the
75// operating width, which for this variable-width carrier is the
76// constructed `len·word_bits` — NOT `CAP` (capacity stays out of any
77// trait answer). `bit_length <= bits_precision` always. Value receiver
78// per the traits; `&Self` mirrors (no reference blanket upstream).
79
80impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::BitWidth
81    for HeaplessBigInt<T, CAP, P>
82{
83    fn bit_width(self) -> u32 {
84        self.bit_length() as u32
85    }
86}
87
88impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::BitWidth
89    for &HeaplessBigInt<T, CAP, P>
90{
91    fn bit_width(self) -> u32 {
92        self.bit_length() as u32
93    }
94}
95
96impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::BitsPrecision
97    for HeaplessBigInt<T, CAP, P>
98{
99    fn bits_precision(&self) -> u32 {
100        self.len as u32 * (core::mem::size_of::<T>() as u32 * 8)
101    }
102}
103
104impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::BitsPrecision
105    for &HeaplessBigInt<T, CAP, P>
106{
107    fn bits_precision(&self) -> u32 {
108        self.len as u32 * (core::mem::size_of::<T>() as u32 * 8)
109    }
110}
111
112// Establish a width from a witness. Grow-only, value-preserving: widen `self`
113// to the whole-word length covering `bits_precision` bits, never shrinking.
114// The zero/one/witness constructors (`zero_with_precision_of(&modulus)` etc.)
115// default over this, giving generic reducers a correctly-sized seed instead of
116// the minimal-width `zero()` that silently truncates. `CAP` is the ceiling:
117// `widened` panics if the requested width exceeds it.
118impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::WithPrecision
119    for HeaplessBigInt<T, CAP, P>
120{
121    fn widen_to_precision(self, bits_precision: u32) -> Self {
122        let word_bits = core::mem::size_of::<T>() as u32 * 8;
123        let target_len = bits_precision.div_ceil(word_bits) as u16;
124        self.widened(target_len.max(self.len()))
125    }
126}
fixed_bigint/heapless/bits.rs

fixed_bigint/heapless/
bits.rs
