fixed_bigint/heapless/
bitwise.rs

1//! `BitAnd` / `BitOr` / `BitXor` for `HeaplessBigInt` (all four receiver
2//! forms each), plus the compound-assign forms.
3//!
4//! All three resolve at `len = max(a.len, b.len)` — the same operand-width
5//! rule as the arithmetic ops, so every binary op hands back one consistent
6//! width. `CAP` never enters. Above `min(len)` the shorter operand is in its
7//! zero-tail, so `AND` yields zero there while `OR` / `XOR` leave the wider
8//! operand's limbs unchanged; the result is value-correct at the wider width.
9//! (`AND` could store the value in `min(len)` — its high limbs are zero — but
10//! a narrower result than the sibling ops would desync widths for a following
11//! width-sensitive op such as `Not` / `count_zeros`.)
12//!
13//! `len` is a public shape parameter, so the body is identical for Nct and
14//! Ct. The compound-assign forms delegate to (or mirror) the binary op.
15
16use super::{HeaplessBigInt, zero};
17use crate::MachineWord;
18use const_num_traits::Personality;
19use core::marker::PhantomData;
20use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
21
22// The value/mixed receiver forms of each bitwise op are uniform pure
23// delegation to the hand-written `&Self $op &Self` core.
24macro_rules! forward_bitwise_receivers {
25    ($imp:ident, $method:ident) => {
26        impl<T: MachineWord, const CAP: usize, P: Personality> $imp for HeaplessBigInt<T, CAP, P> {
27            type Output = Self;
28            fn $method(self, other: Self) -> Self {
29                (&self).$method(&other)
30            }
31        }
32        impl<T: MachineWord, const CAP: usize, P: Personality> $imp<&HeaplessBigInt<T, CAP, P>>
33            for HeaplessBigInt<T, CAP, P>
34        {
35            type Output = Self;
36            fn $method(self, other: &Self) -> Self {
37                (&self).$method(other)
38            }
39        }
40        impl<T: MachineWord, const CAP: usize, P: Personality> $imp<HeaplessBigInt<T, CAP, P>>
41            for &HeaplessBigInt<T, CAP, P>
42        {
43            type Output = HeaplessBigInt<T, CAP, P>;
44            fn $method(self, other: HeaplessBigInt<T, CAP, P>) -> HeaplessBigInt<T, CAP, P> {
45                self.$method(&other)
46            }
47        }
48    };
49}
50
51// Core: `&Self & &Self`. The value + mixed receiver forms delegate here.
52impl<T: MachineWord, const CAP: usize, P: Personality> BitAnd<&HeaplessBigInt<T, CAP, P>>
53    for &HeaplessBigInt<T, CAP, P>
54{
55    type Output = HeaplessBigInt<T, CAP, P>;
56    fn bitand(self, other: &HeaplessBigInt<T, CAP, P>) -> Self::Output {
57        // Operand width, like every other binary op. Above `min(len)` one
58        // operand's zero-tail forces the AND to zero, so the extra high limbs
59        // stay zero — value-correct at the wider width.
60        let out_len = core::cmp::max(self.len, other.len);
61        let n = out_len as usize;
62        let mut limbs = [zero::<T>(); CAP];
63        for ((&ai, &bi), oi) in self.limbs[..n]
64            .iter()
65            .zip(&other.limbs[..n])
66            .zip(&mut limbs[..n])
67        {
68            *oi = ai & bi;
69        }
70        HeaplessBigInt {
71            limbs,
72            len: out_len,
73            _p: PhantomData,
74        }
75    }
76}
77
78forward_bitwise_receivers!(BitAnd, bitand);
79
80// Core: `&Self | &Self`. The value + mixed receiver forms delegate here.
81impl<T: MachineWord, const CAP: usize, P: Personality> BitOr<&HeaplessBigInt<T, CAP, P>>
82    for &HeaplessBigInt<T, CAP, P>
83{
84    type Output = HeaplessBigInt<T, CAP, P>;
85    fn bitor(self, other: &HeaplessBigInt<T, CAP, P>) -> Self::Output {
86        let out_len = core::cmp::max(self.len, other.len);
87        let n = out_len as usize;
88        let mut limbs = [zero::<T>(); CAP];
89        for ((&ai, &bi), oi) in self.limbs[..n]
90            .iter()
91            .zip(&other.limbs[..n])
92            .zip(&mut limbs[..n])
93        {
94            *oi = ai | bi;
95        }
96        HeaplessBigInt {
97            limbs,
98            len: out_len,
99            _p: PhantomData,
100        }
101    }
102}
103
104forward_bitwise_receivers!(BitOr, bitor);
105
106// Core: `&Self ^ &Self`. The value + mixed receiver forms delegate here.
107impl<T: MachineWord, const CAP: usize, P: Personality> BitXor<&HeaplessBigInt<T, CAP, P>>
108    for &HeaplessBigInt<T, CAP, P>
109{
110    type Output = HeaplessBigInt<T, CAP, P>;
111    fn bitxor(self, other: &HeaplessBigInt<T, CAP, P>) -> Self::Output {
112        let out_len = core::cmp::max(self.len, other.len);
113        let n = out_len as usize;
114        let mut limbs = [zero::<T>(); CAP];
115        for ((&ai, &bi), oi) in self.limbs[..n]
116            .iter()
117            .zip(&other.limbs[..n])
118            .zip(&mut limbs[..n])
119        {
120            *oi = ai ^ bi;
121        }
122        HeaplessBigInt {
123            limbs,
124            len: out_len,
125            _p: PhantomData,
126        }
127    }
128}
129
130forward_bitwise_receivers!(BitXor, bitxor);
131
132// Complement over the value width (`len` limbs); the result stays at `len`,
133// so `!x` matches the same-width `FixedUInt` bit-for-bit. `CAP` never enters
134// — the words beyond `len` do not exist. Data-independent, hence uniform
135// across personalities and inherently constant-time.
136impl<T: MachineWord, const CAP: usize, P: Personality> Not for HeaplessBigInt<T, CAP, P> {
137    type Output = Self;
138    fn not(self) -> Self {
139        let n = self.len as usize;
140        let mut limbs = [zero::<T>(); CAP];
141        for (o, &s) in limbs[..n].iter_mut().zip(&self.limbs[..n]) {
142            *o = !s;
143        }
144        HeaplessBigInt {
145            limbs,
146            len: self.len,
147            _p: PhantomData,
148        }
149    }
150}
151
152impl<T: MachineWord, const CAP: usize, P: Personality> Not for &HeaplessBigInt<T, CAP, P> {
153    type Output = HeaplessBigInt<T, CAP, P>;
154    fn not(self) -> Self::Output {
155        !*self
156    }
157}
158
159// ── Compound-assign forms (in-place on `self.limbs`) ──
160
161impl<T: MachineWord, const CAP: usize, P: Personality> BitAndAssign for HeaplessBigInt<T, CAP, P> {
162    fn bitand_assign(&mut self, other: Self) {
163        self.bitand_assign(&other);
164    }
165}
166
167impl<T: MachineWord, const CAP: usize, P: Personality> BitAndAssign<&HeaplessBigInt<T, CAP, P>>
168    for HeaplessBigInt<T, CAP, P>
169{
170    fn bitand_assign(&mut self, other: &Self) {
171        // Result width is `max(len)` (operand width). AND the overlap, then
172        // clear `self`'s own limbs above it — they AND with `other`'s zero-tail,
173        // so they go to zero. When `other` is the wider operand `[min..self.len]`
174        // is empty: `self`'s high limbs are already zero, and the wider result
175        // width is reached just by bumping `len`.
176        let min_len = core::cmp::min(self.len, other.len) as usize;
177        let self_len = self.len as usize;
178        let max_len = core::cmp::max(self.len, other.len);
179        for (si, &oi) in self.limbs[..min_len]
180            .iter_mut()
181            .zip(&other.limbs[..min_len])
182        {
183            *si &= oi;
184        }
185        for si in &mut self.limbs[min_len..self_len] {
186            *si = zero::<T>();
187        }
188        self.len = max_len;
189    }
190}
191
192impl<T: MachineWord, const CAP: usize, P: Personality> BitOrAssign for HeaplessBigInt<T, CAP, P> {
193    fn bitor_assign(&mut self, other: Self) {
194        self.bitor_assign(&other);
195    }
196}
197
198impl<T: MachineWord, const CAP: usize, P: Personality> BitOrAssign<&HeaplessBigInt<T, CAP, P>>
199    for HeaplessBigInt<T, CAP, P>
200{
201    fn bitor_assign(&mut self, other: &Self) {
202        // Result width is `max(len)`: OR the overlap, then copy `other`'s
203        // high limbs (they OR with `self`'s zero-tail = `other`). The copy
204        // range is empty when `self` is the wider operand.
205        let self_len = self.len as usize;
206        let max_len = core::cmp::max(self_len, other.len as usize);
207        for (si, &oi) in self.limbs[..self_len]
208            .iter_mut()
209            .zip(&other.limbs[..self_len])
210        {
211            *si |= oi;
212        }
213        for (si, &oi) in self.limbs[self_len..max_len]
214            .iter_mut()
215            .zip(&other.limbs[self_len..max_len])
216        {
217            *si = oi;
218        }
219        self.len = max_len as u16;
220    }
221}
222
223impl<T: MachineWord, const CAP: usize, P: Personality> BitXorAssign for HeaplessBigInt<T, CAP, P> {
224    fn bitxor_assign(&mut self, other: Self) {
225        self.bitxor_assign(&other);
226    }
227}
228
229impl<T: MachineWord, const CAP: usize, P: Personality> BitXorAssign<&HeaplessBigInt<T, CAP, P>>
230    for HeaplessBigInt<T, CAP, P>
231{
232    fn bitxor_assign(&mut self, other: &Self) {
233        // Result width is `max(len)`: XOR the overlap, then copy `other`'s
234        // high limbs (they XOR with `self`'s zero-tail = `other`). The copy
235        // range is empty when `self` is the wider operand.
236        let self_len = self.len as usize;
237        let max_len = core::cmp::max(self_len, other.len as usize);
238        for (si, &oi) in self.limbs[..self_len]
239            .iter_mut()
240            .zip(&other.limbs[..self_len])
241        {
242            *si ^= oi;
243        }
244        for (si, &oi) in self.limbs[self_len..max_len]
245            .iter_mut()
246            .zip(&other.limbs[self_len..max_len])
247        {
248            *si = oi;
249        }
250        self.len = max_len as u16;
251    }
252}
fixed_bigint/heapless/bitwise.rs

fixed_bigint/heapless/
bitwise.rs
