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            // Shared full-width branchless scan (see `const_leading_zeros_ct`).
50            PersonalityTag::Ct => {
51                let n = self.len as usize;
52                let s = self.limbs.get(..n).unwrap_or(&self.limbs);
53                crate::fixeduint::const_leading_zeros_ct(s) as usize
54            }
55        }
56    }
57}
58
59// ── const_num_traits::BitWidth (bit-length) / BitsPrecision (width) ──
60//
61// Two distinct quantities (bit-vocabulary canon): `bit_width` is the
62// significant-bit count (per-value magnitude); `bits_precision` is the
63// operating width, which for this variable-width carrier is the
64// constructed `len·word_bits` — NOT `CAP` (capacity stays out of any
65// trait answer). `bit_length <= bits_precision` always. Value receiver
66// per the traits; `&Self` mirrors (no reference blanket upstream).
67
68impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::BitWidth
69    for HeaplessBigInt<T, CAP, P>
70{
71    fn bit_width(self) -> u32 {
72        self.bit_length() as u32
73    }
74}
75
76impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::BitWidth
77    for &HeaplessBigInt<T, CAP, P>
78{
79    fn bit_width(self) -> u32 {
80        self.bit_length() as u32
81    }
82}
83
84impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::BitsPrecision
85    for HeaplessBigInt<T, CAP, P>
86{
87    fn bits_precision(&self) -> u32 {
88        self.len as u32 * (core::mem::size_of::<T>() as u32 * 8)
89    }
90}
91
92impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::BitsPrecision
93    for &HeaplessBigInt<T, CAP, P>
94{
95    fn bits_precision(&self) -> u32 {
96        self.len as u32 * (core::mem::size_of::<T>() as u32 * 8)
97    }
98}
99
100// Establish a width from a witness. Grow-only, value-preserving: widen `self`
101// to the whole-word length covering `bits_precision` bits, never shrinking.
102// The zero/one/witness constructors (`zero_with_precision_of(&modulus)` etc.)
103// default over this, giving generic reducers a correctly-sized seed instead of
104// the minimal-width `zero()` that silently truncates. `CAP` is the ceiling:
105// `widened` panics if the requested width exceeds it.
106impl<T: MachineWord, const CAP: usize, P: Personality> const_num_traits::WithPrecision
107    for HeaplessBigInt<T, CAP, P>
108{
109    fn widen_to_precision(self, bits_precision: u32) -> Self {
110        let word_bits = core::mem::size_of::<T>() as u32 * 8;
111        let target_len = bits_precision.div_ceil(word_bits) as u16;
112        self.widened(target_len.max(self.len()))
113    }
114}
fixed_bigint/heapless/bits.rs

fixed_bigint/heapless/
bits.rs
