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

crypto_bigint/uint/
ref_type.rs
