crypto_bigint/uint/
ref_type.rs

1//! Unsigned integer reference type.
2
3mod add;
4mod bits;
5mod cmp;
6mod ct;
7mod div;
8mod invert_mod;
9mod mul;
10mod shl;
11mod shr;
12mod slice;
13mod sub;
14
15use crate::{Choice, Limb, NonZero, Odd, Uint, Word};
16use core::{
17    fmt,
18    ops::{Index, IndexMut},
19    ptr,
20};
21
22#[cfg(feature = "alloc")]
23use {
24    crate::{BoxedUint, ToUnsigned},
25    alloc::borrow::ToOwned,
26};
27
28/// Unsigned integer reference type.
29///
30/// This type contains a limb slice which can be borrowed from either a [`Uint`] or [`BoxedUint`] and
31/// thus provides an abstraction for writing shared implementations.
32#[repr(transparent)]
33#[derive(PartialEq, Eq)]
34pub struct UintRef {
35    /// Inner limb array. Stored from least significant to most significant.
36    // TODO(tarcieri): maintain an invariant of at least one limb?
37    pub(crate) limbs: [Limb],
38}
39
40impl UintRef {
41    /// Create a [`UintRef`] reference type from a [`Limb`] slice.
42    #[inline]
43    #[must_use]
44    pub const fn new(limbs: &[Limb]) -> &Self {
45        // SAFETY: `UintRef` is a `repr(transparent)` newtype for `[Limb]`.
46        #[allow(unsafe_code)]
47        unsafe {
48            &*(ptr::from_ref(limbs) as *const UintRef)
49        }
50    }
51
52    /// Create a mutable [`UintRef`] reference type from a [`Limb`] slice.
53    #[inline]
54    pub const fn new_mut(limbs: &mut [Limb]) -> &mut Self {
55        // SAFETY: `UintRef` is a `repr(transparent)` newtype for `[Limb]`.
56        #[allow(unsafe_code)]
57        unsafe {
58            &mut *(ptr::from_mut(limbs) as *mut UintRef)
59        }
60    }
61
62    /// Create a new mutable [`UintRef`] reference type from a slice of [`Limb`] arrays.
63    pub const fn new_flattened_mut<const N: usize>(slice: &mut [[Limb; N]]) -> &mut Self {
64        // This is a temporary shim for `[[T;N]]::as_flattened_mut` which is only const-stable as of
65        // Rust 1.87.
66        let len = slice.len() * N;
67
68        // SAFETY: we are converting a slice of limb arrays to a slice of limbs, and `len` has been
69        // calculated to be the total number of limbs. The pointer has the lifetime of `slice` and
70        // is for `Word`, so we're requesting a slice of words the size of the total number of words
71        // in the original slice, and giving it a valid pointer to the first word.
72        #[allow(unsafe_code)]
73        let slice = unsafe { core::slice::from_raw_parts_mut(slice.as_mut_ptr().cast(), len) };
74        Self::new_mut(slice)
75    }
76
77    /// Borrow the inner `&[Limb]` slice.
78    #[inline]
79    #[must_use]
80    pub const fn as_limbs(&self) -> &[Limb] {
81        &self.limbs
82    }
83
84    /// Mutably borrow the inner `&mut [Limb]` slice.
85    #[inline]
86    pub const fn as_mut_limbs(&mut self) -> &mut [Limb] {
87        &mut self.limbs
88    }
89
90    /// Borrow the inner limbs as a slice of [`Word`]s.
91    #[inline]
92    #[must_use]
93    pub const fn as_words(&self) -> &[Word] {
94        Limb::slice_as_words(&self.limbs)
95    }
96
97    /// Borrow the inner limbs as a mutable slice of [`Word`]s.
98    #[inline]
99    pub const fn as_mut_words(&mut self) -> &mut [Word] {
100        Limb::slice_as_mut_words(&mut self.limbs)
101    }
102
103    /// Get an iterator over the inner limbs.
104    #[inline]
105    #[must_use]
106    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &Limb> {
107        self.limbs.iter()
108    }
109
110    /// Get a mutable iterator over the inner limbs.
111    #[inline]
112    #[allow(dead_code)] // TODO(tarcieri): use this
113    pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut Limb> {
114        self.limbs.iter_mut()
115    }
116
117    /// Access the number of limbs.
118    #[inline]
119    #[must_use]
120    pub const fn nlimbs(&self) -> usize {
121        self.limbs.len()
122    }
123
124    /// Conditionally assign all of the limbs to zero.
125    #[inline(always)]
126    pub const fn conditional_set_zero(&mut self, choice: Choice) {
127        let mut i = 0;
128        while i < self.nlimbs() {
129            self.limbs[i] = Limb::select(self.limbs[i], Limb::ZERO, choice);
130            i += 1;
131        }
132    }
133
134    /// Conditionally assign the value to one.
135    #[inline(always)]
136    pub const fn conditional_set_one(&mut self, choice: Choice) {
137        self.limbs[0] = Limb::select(self.limbs[0], Limb::ONE, choice);
138        self.trailing_mut(1).conditional_set_zero(choice);
139    }
140
141    /// Conditionally assign all of the limbs to the maximum.
142    #[inline]
143    pub const fn conditional_set_max(&mut self, choice: Choice) {
144        let mut i = 0;
145        while i < self.nlimbs() {
146            self.limbs[i] = Limb::select(self.limbs[i], Limb::MAX, choice);
147            i += 1;
148        }
149    }
150
151    /// Extract up to `LIMBS` limbs into a new `Uint`.
152    #[must_use]
153    pub const fn to_uint_resize<const LIMBS: usize>(&self) -> Uint<LIMBS> {
154        let mut out = Uint::ZERO;
155        let len = if self.nlimbs() > LIMBS {
156            LIMBS
157        } else {
158            self.nlimbs()
159        };
160        let mut i = 0;
161        while i < len {
162            out.limbs[i] = self.limbs[i];
163            i += 1;
164        }
165        out
166    }
167
168    /// Construct a [`NonZero`] reference, returning [`None`] in the event `self` is `0`.
169    #[inline]
170    #[must_use]
171    pub const fn as_nz_vartime(&self) -> Option<&NonZero<Self>> {
172        if self.is_zero_vartime() {
173            return None;
174        }
175        Some(NonZero::new_ref_unchecked(self))
176    }
177
178    /// Construct a [`Odd`] reference, returning [`None`] in the event `self` is even.
179    #[inline]
180    #[must_use]
181    pub const fn as_odd_vartime(&self) -> Option<&Odd<Self>> {
182        if !self.is_odd().to_bool_vartime() {
183            return None;
184        }
185        Some(Odd::new_ref_unchecked(self))
186    }
187
188    cpubits::cpubits! {
189        32 => {
190            /// Get the least significant 64-bits.
191            #[inline(always)]
192            pub(crate) const fn lowest_u64(&self) -> u64 {
193                debug_assert!(self.nlimbs() >= 1);
194                let mut ret = self.limbs[0].0 as u64;
195
196                if self.nlimbs() >= 2 {
197                    ret |= (self.limbs[1].0 as u64) << 32;
198                }
199
200                ret
201            }
202        }
203        64 => {
204            /// Get the least significant 64-bits.
205            #[inline(always)]
206            pub(crate) const fn lowest_u64(&self) -> u64 {
207                self.limbs[0].0
208            }
209        }
210    }
211
212    /// Perform a carry chain-like operation over the limbs of `lhs` and `rhs` inputs, virtually
213    /// padding each with `Limb::ZERO` as needed to match the width of `self` and assigning the
214    /// result to `self`.
215    #[cfg(feature = "alloc")]
216    #[inline(always)]
217    pub(crate) fn fold_limbs<F>(&mut self, lhs: &Self, rhs: &Self, mut carry: Limb, f: F) -> Limb
218    where
219        F: Fn(Limb, Limb, Limb) -> (Limb, Limb),
220    {
221        for i in 0..self.nlimbs() {
222            let &a = lhs.limbs.get(i).unwrap_or(&Limb::ZERO);
223            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
224            (self.limbs[i], carry) = f(a, b, carry);
225        }
226
227        carry
228    }
229
230    /// Perform a carry chain-like operation over the limbs of the inputs, virtually padding
231    /// `rhs` with `Limb::ZERO` as needed to match the width of `self` and assigning the result
232    /// to `self`.
233    #[cfg(feature = "alloc")]
234    #[inline(always)]
235    pub(crate) fn fold_limbs_assign<F>(&mut self, rhs: &UintRef, mut carry: Limb, f: F) -> Limb
236    where
237        F: Fn(Limb, Limb, Limb) -> (Limb, Limb),
238    {
239        for i in 0..self.nlimbs() {
240            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
241            (self.limbs[i], carry) = f(self.limbs[i], b, carry);
242        }
243
244        carry
245    }
246}
247
248impl AsRef<[Limb]> for UintRef {
249    #[inline]
250    fn as_ref(&self) -> &[Limb] {
251        self.as_limbs()
252    }
253}
254
255impl AsRef<UintRef> for UintRef {
256    #[inline]
257    fn as_ref(&self) -> &Self {
258        self
259    }
260}
261
262impl AsMut<[Limb]> for UintRef {
263    #[inline]
264    fn as_mut(&mut self) -> &mut [Limb] {
265        self.as_mut_limbs()
266    }
267}
268
269impl AsMut<UintRef> for UintRef {
270    #[inline]
271    fn as_mut(&mut self) -> &mut Self {
272        self
273    }
274}
275
276impl Index<usize> for UintRef {
277    type Output = Limb;
278
279    #[inline]
280    fn index(&self, index: usize) -> &Limb {
281        self.limbs.index(index)
282    }
283}
284
285impl IndexMut<usize> for UintRef {
286    #[inline]
287    fn index_mut(&mut self, index: usize) -> &mut Limb {
288        self.limbs.index_mut(index)
289    }
290}
291
292#[cfg(feature = "alloc")]
293impl ToOwned for UintRef {
294    type Owned = BoxedUint;
295
296    fn to_owned(&self) -> BoxedUint {
297        BoxedUint::from(self)
298    }
299}
300
301#[cfg(feature = "alloc")]
302impl ToUnsigned for UintRef {
303    type Unsigned = BoxedUint;
304
305    fn to_unsigned(&self) -> Self::Unsigned {
306        BoxedUint::from(self)
307    }
308
309    fn to_unsigned_zero(&self) -> Self::Unsigned {
310        BoxedUint::zero_with_precision(self.bits_precision())
311    }
312}
313
314impl fmt::Debug for UintRef {
315    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
316        write!(f, "UintRef(0x{self:X})")
317    }
318}
319
320impl fmt::Binary for UintRef {
321    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
322        if f.alternate() {
323            write!(f, "0b")?;
324        }
325
326        for limb in self.iter().rev() {
327            write!(f, "{:0width$b}", &limb.0, width = Limb::BITS as usize)?;
328        }
329        Ok(())
330    }
331}
332
333impl fmt::Display for UintRef {
334    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
335        fmt::UpperHex::fmt(self, f)
336    }
337}
338
339impl fmt::LowerHex for UintRef {
340    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
341        if f.alternate() {
342            write!(f, "0x")?;
343        }
344        for limb in self.iter().rev() {
345            write!(f, "{:0width$x}", &limb.0, width = Limb::BYTES * 2)?;
346        }
347        Ok(())
348    }
349}
350
351impl fmt::UpperHex for UintRef {
352    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
353        if f.alternate() {
354            write!(f, "0x")?;
355        }
356        for limb in self.iter().rev() {
357            write!(f, "{:0width$X}", &limb.0, width = Limb::BYTES * 2)?;
358        }
359        Ok(())
360    }
361}
crypto_bigint/uint/ref_type.rs

crypto_bigint/uint/
ref_type.rs
