fixed_bigint/heapless/
shift.rs

1//! `Shl<usize>` / `Shr<usize>` for `HeaplessBigInt`.
2//!
3//! Bit-count shifts by a public `usize` amount. Output `len` is derived
4//! from operand `len` + shift amount, both public shape parameters. The
5//! shape math:
6//!
7//! - `Shl`: width-preserving — `out_len = self.len`, bits shifted past the
8//!   operand width are discarded (`x << bits mod 2^(len·word_bits)`), so a
9//!   value at `len = k` shifts exactly like `FixedUInt<T, k>`. `CAP` never
10//!   enters; the words beyond `len` do not exist. A caller wanting the
11//!   shifted value to occupy more words constructs it at the wider width
12//!   first (as `div_rem` does).
13//! - `Shr`: `out_len = self.len.saturating_sub(bits / word_bits)`. The
14//!   top limb may become zero — that's fine under the zero-tail invariant
15//!   and downstream can trim explicitly if needed (NCT-only).
16//!
17//! Iteration count is derived from `self.len` + shift amount — both
18//! public — so the Nct and Ct arms share the same body.
19
20use super::{HeaplessBigInt, zero};
21use crate::MachineWord;
22use const_num_traits::Personality;
23use core::marker::PhantomData;
24use core::ops::{Shl, ShlAssign, Shr, ShrAssign};
25
26impl<T: MachineWord, const CAP: usize, P: Personality> Shl<usize> for HeaplessBigInt<T, CAP, P> {
27    type Output = Self;
28
29    fn shl(self, bits: usize) -> Self::Output {
30        let word_bits = core::mem::size_of::<T>() * 8;
31        let word_shift = bits / word_bits;
32        let bit_shift = bits % word_bits;
33
34        // Width-preserving: out_len = self.len (see module doc).
35        let out_len = self.len as usize;
36        let mut limbs = [zero::<T>(); CAP];
37
38        let mut i = 0;
39        while i < out_len {
40            let dst_lo = i + word_shift;
41            if dst_lo < out_len {
42                let lo = self.limbs[i] << bit_shift;
43                limbs[dst_lo] |= lo;
44                if bit_shift > 0 {
45                    let dst_hi = dst_lo + 1;
46                    if dst_hi < out_len {
47                        let hi = self.limbs[i] >> (word_bits - bit_shift);
48                        limbs[dst_hi] |= hi;
49                    }
50                }
51            }
52            i += 1;
53        }
54
55        Self {
56            limbs,
57            len: out_len as u16,
58            _p: PhantomData,
59        }
60    }
61}
62
63impl<T: MachineWord, const CAP: usize, P: Personality> ShlAssign<usize>
64    for HeaplessBigInt<T, CAP, P>
65{
66    fn shl_assign(&mut self, bits: usize) {
67        *self = *self << bits;
68    }
69}
70
71impl<T: MachineWord, const CAP: usize, P: Personality> ShrAssign<usize>
72    for HeaplessBigInt<T, CAP, P>
73{
74    fn shr_assign(&mut self, bits: usize) {
75        *self = *self >> bits;
76    }
77}
78
79impl<T: MachineWord, const CAP: usize, P: Personality> Shr<usize> for HeaplessBigInt<T, CAP, P> {
80    type Output = Self;
81
82    fn shr(self, bits: usize) -> Self::Output {
83        let word_bits = core::mem::size_of::<T>() * 8;
84        let word_shift = bits / word_bits;
85        let bit_shift = bits % word_bits;
86
87        let mut limbs = [zero::<T>(); CAP];
88        if word_shift >= self.len as usize {
89            return Self {
90                limbs,
91                len: 0,
92                _p: PhantomData,
93            };
94        }
95
96        let out_len = self.len as usize - word_shift;
97
98        let mut i = 0;
99        while i < out_len {
100            let src_lo = i + word_shift;
101            let lo = self.limbs[src_lo] >> bit_shift;
102            let hi = if bit_shift > 0 && src_lo + 1 < self.len as usize {
103                self.limbs[src_lo + 1] << (word_bits - bit_shift)
104            } else {
105                zero::<T>()
106            };
107            limbs[i] = lo | hi;
108            i += 1;
109        }
110
111        Self {
112            limbs,
113            len: out_len as u16,
114            _p: PhantomData,
115        }
116    }
117}
fixed_bigint/heapless/shift.rs

fixed_bigint/heapless/
shift.rs
