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)]
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    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &Limb> {
106        self.limbs.iter()
107    }
108
109    /// Get a mutable iterator over the inner limbs.
110    #[inline]
111    #[allow(dead_code)] // TODO(tarcieri): use this
112    pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut Limb> {
113        self.limbs.iter_mut()
114    }
115
116    /// Access the number of limbs.
117    #[inline]
118    #[must_use]
119    pub const fn nlimbs(&self) -> usize {
120        self.limbs.len()
121    }
122
123    /// Conditionally assign all of the limbs to zero.
124    #[inline(always)]
125    pub const fn conditional_set_zero(&mut self, choice: Choice) {
126        let mut i = 0;
127        while i < self.nlimbs() {
128            self.limbs[i] = Limb::select(self.limbs[i], Limb::ZERO, choice);
129            i += 1;
130        }
131    }
132
133    /// Conditionally assign the value to one.
134    #[inline(always)]
135    pub const fn conditional_set_one(&mut self, choice: Choice) {
136        self.limbs[0] = Limb::select(self.limbs[0], Limb::ONE, choice);
137        self.trailing_mut(1).conditional_set_zero(choice);
138    }
139
140    /// Conditionally assign all of the limbs to the maximum.
141    #[inline]
142    pub const fn conditional_set_max(&mut self, choice: Choice) {
143        let mut i = 0;
144        while i < self.nlimbs() {
145            self.limbs[i] = Limb::select(self.limbs[i], Limb::MAX, choice);
146            i += 1;
147        }
148    }
149
150    /// Extract up to `LIMBS` limbs into a new `Uint`.
151    #[must_use]
152    pub const fn to_uint_resize<const LIMBS: usize>(&self) -> Uint<LIMBS> {
153        let mut out = Uint::ZERO;
154        let len = if self.nlimbs() > LIMBS {
155            LIMBS
156        } else {
157            self.nlimbs()
158        };
159        let mut i = 0;
160        while i < len {
161            out.limbs[i] = self.limbs[i];
162            i += 1;
163        }
164        out
165    }
166
167    /// Construct a [`NonZero`] reference, returning [`None`] in the event `self` is `0`.
168    #[inline]
169    #[must_use]
170    pub const fn as_nz_vartime(&self) -> Option<&NonZero<Self>> {
171        if self.is_zero_vartime() {
172            return None;
173        }
174        Some(NonZero::new_ref_unchecked(self))
175    }
176
177    /// Construct a [`Odd`] reference, returning [`None`] in the event `self` is even.
178    #[inline]
179    #[must_use]
180    pub const fn as_odd_vartime(&self) -> Option<&Odd<Self>> {
181        if !self.is_odd().to_bool() {
182            return None;
183        }
184        Some(Odd::new_ref_unchecked(self))
185    }
186
187    cpubits::cpubits! {
188        32 => {
189            /// Get the least significant 64-bits.
190            #[inline(always)]
191            pub(crate) const fn lowest_u64(&self) -> u64 {
192                debug_assert!(self.nlimbs() >= 1);
193                let mut ret = self.limbs[0].0 as u64;
194
195                if self.nlimbs() >= 2 {
196                    ret |= (self.limbs[1].0 as u64) << 32;
197                }
198
199                ret
200            }
201        }
202        64 => {
203            /// Get the least significant 64-bits.
204            #[inline(always)]
205            pub(crate) const fn lowest_u64(&self) -> u64 {
206                self.limbs[0].0
207            }
208        }
209    }
210
211    /// Perform a carry chain-like operation over the limbs of `lhs` and `rhs` inputs, virtually
212    /// padding each with `Limb::ZERO` as needed to match the width of `self` and assigning the
213    /// result to `self`.
214    #[cfg(feature = "alloc")]
215    #[inline(always)]
216    pub(crate) fn fold_limbs<F>(&mut self, lhs: &Self, rhs: &Self, mut carry: Limb, f: F) -> Limb
217    where
218        F: Fn(Limb, Limb, Limb) -> (Limb, Limb),
219    {
220        for i in 0..self.nlimbs() {
221            let &a = lhs.limbs.get(i).unwrap_or(&Limb::ZERO);
222            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
223            (self.limbs[i], carry) = f(a, b, carry);
224        }
225
226        carry
227    }
228
229    /// Perform a carry chain-like operation over the limbs of the inputs, virtually padding
230    /// `rhs` with `Limb::ZERO` as needed to match the width of `self` and assigning the result
231    /// to `self`.
232    #[cfg(feature = "alloc")]
233    #[inline(always)]
234    pub(crate) fn fold_limbs_assign<F>(&mut self, rhs: &UintRef, mut carry: Limb, f: F) -> Limb
235    where
236        F: Fn(Limb, Limb, Limb) -> (Limb, Limb),
237    {
238        for i in 0..self.nlimbs() {
239            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
240            (self.limbs[i], carry) = f(self.limbs[i], b, carry);
241        }
242
243        carry
244    }
245}
246
247impl AsRef<[Limb]> for UintRef {
248    #[inline]
249    fn as_ref(&self) -> &[Limb] {
250        self.as_limbs()
251    }
252}
253
254impl AsRef<UintRef> for UintRef {
255    #[inline]
256    fn as_ref(&self) -> &Self {
257        self
258    }
259}
260
261impl AsMut<[Limb]> for UintRef {
262    #[inline]
263    fn as_mut(&mut self) -> &mut [Limb] {
264        self.as_mut_limbs()
265    }
266}
267
268impl AsMut<UintRef> for UintRef {
269    #[inline]
270    fn as_mut(&mut self) -> &mut Self {
271        self
272    }
273}
274
275impl Index<usize> for UintRef {
276    type Output = Limb;
277
278    #[inline]
279    fn index(&self, index: usize) -> &Limb {
280        self.limbs.index(index)
281    }
282}
283
284impl IndexMut<usize> for UintRef {
285    #[inline]
286    fn index_mut(&mut self, index: usize) -> &mut Limb {
287        self.limbs.index_mut(index)
288    }
289}
290
291#[cfg(feature = "alloc")]
292impl ToOwned for UintRef {
293    type Owned = BoxedUint;
294
295    fn to_owned(&self) -> BoxedUint {
296        BoxedUint::from(self)
297    }
298}
299
300#[cfg(feature = "alloc")]
301impl ToUnsigned for UintRef {
302    type Unsigned = BoxedUint;
303
304    fn to_unsigned(&self) -> Self::Unsigned {
305        BoxedUint::from(self)
306    }
307
308    fn to_unsigned_zero(&self) -> Self::Unsigned {
309        BoxedUint::zero_with_precision(self.bits_precision())
310    }
311}
312
313impl fmt::Debug for UintRef {
314    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
315        write!(f, "UintRef(0x{self:X})")
316    }
317}
318
319impl fmt::Binary for UintRef {
320    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
321        if f.alternate() {
322            write!(f, "0b")?;
323        }
324
325        for limb in self.iter().rev() {
326            write!(f, "{:0width$b}", &limb.0, width = Limb::BITS as usize)?;
327        }
328        Ok(())
329    }
330}
331
332impl fmt::Display for UintRef {
333    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
334        fmt::UpperHex::fmt(self, f)
335    }
336}
337
338impl fmt::LowerHex for UintRef {
339    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
340        if f.alternate() {
341            write!(f, "0x")?;
342        }
343        for limb in self.iter().rev() {
344            write!(f, "{:0width$x}", &limb.0, width = Limb::BYTES * 2)?;
345        }
346        Ok(())
347    }
348}
349
350impl fmt::UpperHex for UintRef {
351    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
352        if f.alternate() {
353            write!(f, "0x")?;
354        }
355        for limb in self.iter().rev() {
356            write!(f, "{:0width$X}", &limb.0, width = Limb::BYTES * 2)?;
357        }
358        Ok(())
359    }
360}
crypto_bigint/uint/ref_type.rs

crypto_bigint/uint/
ref_type.rs
