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 all of the limbs to the maximum.
135    #[inline]
136    pub const fn conditional_set_max(&mut self, choice: Choice) {
137        let mut i = 0;
138        while i < self.nlimbs() {
139            self.limbs[i] = Limb::select(self.limbs[i], Limb::MAX, choice);
140            i += 1;
141        }
142    }
143
144    /// Extract up to `LIMBS` limbs into a new `Uint`.
145    #[must_use]
146    pub const fn to_uint_resize<const LIMBS: usize>(&self) -> Uint<LIMBS> {
147        let mut out = Uint::ZERO;
148        let len = if self.nlimbs() > LIMBS {
149            LIMBS
150        } else {
151            self.nlimbs()
152        };
153        let mut i = 0;
154        while i < len {
155            out.limbs[i] = self.limbs[i];
156            i += 1;
157        }
158        out
159    }
160
161    /// Construct a [`NonZero`] reference, returning [`None`] in the event `self` is `0`.
162    #[inline]
163    #[must_use]
164    pub const fn as_nz_vartime(&self) -> Option<&NonZero<Self>> {
165        if self.is_zero_vartime() {
166            return None;
167        }
168        Some(self.as_nz_unchecked())
169    }
170
171    /// Cast to [`NonZero`] without first checking that the contained value is non-zero.
172    ///
173    /// Use with care! This method bypasses [`NonZero`] invariant checks.
174    ///
175    /// # Warning: Panics
176    /// We don't explicitly flag this function as `unsafe` because it doesn't have a memory safety
177    /// impact, however functions called with `NonZero` arguments assume this value is non-zero
178    /// and may panic if given a zero value.
179    #[inline]
180    #[must_use]
181    #[allow(unsafe_code)]
182    pub(crate) const fn as_nz_unchecked(&self) -> &NonZero<Self> {
183        // SAFETY: `NonZero` is a `repr(transparent)` newtype
184        unsafe { &*(ptr::from_ref(self) as *const NonZero<Self>) }
185    }
186
187    /// Construct a [`Odd`] reference, returning [`None`] in the event `self` is even.
188    #[inline]
189    #[must_use]
190    pub const fn as_odd_vartime(&self) -> Option<&Odd<Self>> {
191        if !self.is_odd().to_bool_vartime() {
192            return None;
193        }
194        Some(self.as_odd_unchecked())
195    }
196
197    /// Cast to [`Odd`] without first checking that the contained value is actually odd.
198    ///
199    /// Use with care! This method bypasses [`Odd`] invariant checks.
200    ///
201    /// # Panics
202    /// We don't explicitly flag this function as `unsafe` because it doesn't have a memory safety
203    /// impact, however functions called with `Odd` arguments assume this value is actually odd
204    /// and may panic if given an even value.
205    #[inline]
206    #[must_use]
207    #[allow(unsafe_code)]
208    pub(crate) const fn as_odd_unchecked(&self) -> &Odd<Self> {
209        // SAFETY: `Odd` is a `repr(transparent)` newtype
210        unsafe { &*(ptr::from_ref(self) as *const Odd<Self>) }
211    }
212
213    cpubits::cpubits! {
214        32 => {
215            /// Get the least significant 64-bits.
216            #[inline(always)]
217            pub(crate) const fn lowest_u64(&self) -> u64 {
218                debug_assert!(self.nlimbs() >= 1);
219                let mut ret = self.limbs[0].0 as u64;
220
221                if self.nlimbs() >= 2 {
222                    ret |= (self.limbs[1].0 as u64) << 32;
223                }
224
225                ret
226            }
227        }
228        64 => {
229            /// Get the least significant 64-bits.
230            #[inline(always)]
231            pub(crate) const fn lowest_u64(&self) -> u64 {
232                self.limbs[0].0
233            }
234        }
235    }
236
237    /// Perform a carry chain-like operation over the limbs of `lhs` and `rhs` inputs, virtually
238    /// padding each with `Limb::ZERO` as needed to match the width of `self` and assigning the
239    /// result to `self`.
240    #[cfg(feature = "alloc")]
241    #[inline(always)]
242    pub(crate) fn fold_limbs<F>(&mut self, lhs: &Self, rhs: &Self, mut carry: Limb, f: F) -> Limb
243    where
244        F: Fn(Limb, Limb, Limb) -> (Limb, Limb),
245    {
246        for i in 0..self.nlimbs() {
247            let &a = lhs.limbs.get(i).unwrap_or(&Limb::ZERO);
248            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
249            (self.limbs[i], carry) = f(a, b, carry);
250        }
251
252        carry
253    }
254
255    /// Perform a carry chain-like operation over the limbs of the inputs, virtually padding
256    /// `rhs` with `Limb::ZERO` as needed to match the width of `self` and assigning the result
257    /// to `self`.
258    #[cfg(feature = "alloc")]
259    #[inline(always)]
260    pub(crate) fn fold_limbs_assign<F>(&mut self, rhs: &UintRef, mut carry: Limb, f: F) -> Limb
261    where
262        F: Fn(Limb, Limb, Limb) -> (Limb, Limb),
263    {
264        for i in 0..self.nlimbs() {
265            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
266            (self.limbs[i], carry) = f(self.limbs[i], b, carry);
267        }
268
269        carry
270    }
271}
272
273impl AsRef<[Limb]> for UintRef {
274    #[inline]
275    fn as_ref(&self) -> &[Limb] {
276        self.as_limbs()
277    }
278}
279
280impl AsRef<UintRef> for UintRef {
281    #[inline]
282    fn as_ref(&self) -> &Self {
283        self
284    }
285}
286
287impl AsMut<[Limb]> for UintRef {
288    #[inline]
289    fn as_mut(&mut self) -> &mut [Limb] {
290        self.as_mut_limbs()
291    }
292}
293
294impl AsMut<UintRef> for UintRef {
295    #[inline]
296    fn as_mut(&mut self) -> &mut Self {
297        self
298    }
299}
300
301impl Index<usize> for UintRef {
302    type Output = Limb;
303
304    #[inline]
305    fn index(&self, index: usize) -> &Limb {
306        self.limbs.index(index)
307    }
308}
309
310impl IndexMut<usize> for UintRef {
311    #[inline]
312    fn index_mut(&mut self, index: usize) -> &mut Limb {
313        self.limbs.index_mut(index)
314    }
315}
316
317#[cfg(feature = "alloc")]
318impl ToOwned for UintRef {
319    type Owned = BoxedUint;
320
321    fn to_owned(&self) -> BoxedUint {
322        BoxedUint::from(self)
323    }
324}
325
326#[cfg(feature = "alloc")]
327impl ToUnsigned for UintRef {
328    type Unsigned = BoxedUint;
329
330    fn to_unsigned(&self) -> Self::Unsigned {
331        BoxedUint::from(self)
332    }
333
334    fn to_unsigned_zero(&self) -> Self::Unsigned {
335        BoxedUint::zero_with_precision(self.bits_precision())
336    }
337}
338
339impl fmt::Debug for UintRef {
340    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
341        write!(f, "UintRef(0x{self:X})")
342    }
343}
344
345impl fmt::Binary for UintRef {
346    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
347        if f.alternate() {
348            write!(f, "0b")?;
349        }
350
351        for limb in self.iter().rev() {
352            write!(f, "{:0width$b}", &limb.0, width = Limb::BITS as usize)?;
353        }
354        Ok(())
355    }
356}
357
358impl fmt::Display for UintRef {
359    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
360        fmt::UpperHex::fmt(self, f)
361    }
362}
363
364impl fmt::LowerHex for UintRef {
365    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
366        if f.alternate() {
367            write!(f, "0x")?;
368        }
369        for limb in self.iter().rev() {
370            write!(f, "{:0width$x}", &limb.0, width = Limb::BYTES * 2)?;
371        }
372        Ok(())
373    }
374}
375
376impl fmt::UpperHex for UintRef {
377    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
378        if f.alternate() {
379            write!(f, "0x")?;
380        }
381        for limb in self.iter().rev() {
382            write!(f, "{:0width$X}", &limb.0, width = Limb::BYTES * 2)?;
383        }
384        Ok(())
385    }
386}
crypto_bigint/uint/ref_type.rs

crypto_bigint/uint/
ref_type.rs
