ruint/
lib.rs

1#![doc = include_str!("../README.md")]
2#![doc(issue_tracker_base_url = "https://github.com/recmo/uint/issues/")]
3#![cfg_attr(test, allow(clippy::wildcard_imports, clippy::cognitive_complexity))]
4#![cfg_attr(not(test), warn(unused_crate_dependencies))]
5#![cfg_attr(not(feature = "std"), no_std)]
6// Unstable features
7#![cfg_attr(docsrs, feature(doc_cfg))]
8#![cfg_attr(
9    feature = "nightly",
10    feature(core_intrinsics, const_unsigned_bigint_helpers)
11)]
12#![cfg_attr(
13    feature = "nightly",
14    allow(internal_features, clippy::incompatible_msrv)
15)]
16#![cfg_attr(
17    feature = "generic_const_exprs",
18    feature(generic_const_exprs),
19    allow(incomplete_features)
20)]
21
22#[cfg(feature = "alloc")]
23#[allow(unused_imports)]
24// `unused_imports` triggers on macro_use, which is required by some support
25// modules.
26#[macro_use]
27extern crate alloc;
28
29#[macro_use]
30mod macros;
31
32mod add;
33pub mod algorithms;
34pub mod aliases;
35mod base_convert;
36mod bit_arr;
37mod bits;
38mod bytes;
39mod cmp;
40mod const_for;
41mod div;
42mod fmt;
43mod from;
44mod gcd;
45mod log;
46mod modular;
47mod mul;
48mod pow;
49mod root;
50mod special;
51mod string;
52mod utils;
53
54pub mod support;
55
56#[doc(inline)]
57pub use bit_arr::Bits;
58
59#[doc(inline)]
60pub use self::{
61    base_convert::BaseConvertError,
62    bytes::nbytes,
63    from::{FromUintError, ToFieldError, ToUintError, UintTryFrom, UintTryTo},
64    string::ParseError,
65};
66
67// For documentation purposes we expose the macro directly, otherwise it is
68// wrapped in ./macros.rs.
69#[cfg(doc)]
70#[doc(inline)]
71pub use ruint_macro::uint;
72
73/// Extra features that are nightly only.
74#[cfg(feature = "generic_const_exprs")]
75pub mod nightly {
76    /// Alias for `Uint` specified only by bit size.
77    ///
78    /// Compared to [`crate::Uint`] it compile-time computes the required number
79    /// of limbs. Unfortunately this requires the nightly feature
80    /// `generic_const_exprs`.
81    ///
82    /// # References
83    /// * [Working group](https://rust-lang.github.io/project-const-generics/)
84    ///   const generics working group.
85    /// * [RFC2000](https://rust-lang.github.io/rfcs/2000-const-generics.html)
86    ///   const generics.
87    /// * [#60551](https://github.com/rust-lang/rust/issues/60551) associated
88    ///   constants in const generics.
89    /// * [#76560](https://github.com/rust-lang/rust/issues/76560) tracking
90    ///   issue for `generic_const_exprs`.
91    /// * [Rust blog](https://blog.rust-lang.org/inside-rust/2021/09/06/Splitting-const-generics.html)
92    ///   2021-09-06 Splitting const generics.
93    pub type Uint<const BITS: usize> = crate::Uint<BITS, { crate::nlimbs(BITS) }>;
94
95    /// Alias for `Bits` specified only by bit size.
96    ///
97    /// See [`Uint`] for more information.
98    pub type Bits<const BITS: usize> = crate::Bits<BITS, { crate::nlimbs(BITS) }>;
99}
100
101/// Packed u128, for [`as_double_words`](Uint::as_double_words).
102#[derive(Clone, Copy)]
103#[allow(non_camel_case_types)]
104pub(crate) struct pu128 {
105    inner: [u64; 2],
106}
107impl pu128 {
108    #[inline]
109    pub(crate) const fn get(self) -> u128 {
110        let arr = self.inner;
111        #[cfg(target_endian = "little")]
112        {
113            unsafe { core::mem::transmute(arr) }
114        }
115        #[cfg(target_endian = "big")]
116        {
117            arr[0] as u128 | (arr[1] as u128) << 64
118        }
119    }
120}
121
122/// The ring of numbers modulo $2^{\mathtt{BITS}}$.
123///
124/// [`Uint`] implements nearly all traits and methods from the `std` unsigned
125/// integer types, including most nightly only ones.
126///
127/// # Notable differences from `std` uint types.
128///
129/// * The operators `+`, `-`, `*`, etc. using wrapping math by default. The std
130///   operators panic on overflow in debug, and are undefined in release, see
131///   [reference][std-overflow].
132/// * The [`Uint::checked_shl`], [`Uint::overflowing_shl`], etc return overflow
133///   when non-zero bits are shifted out. In std they return overflow when the
134///   shift amount is greater than the bit size.
135/// * Some methods like [`u64::div_euclid`] and [`u64::rem_euclid`] are left out
136///   because they are meaningless or redundant for unsigned integers. Std has
137///   them for compatibility with their signed integers.
138/// * Many functions that are `const` in std are not in [`Uint`].
139/// * [`Uint::to_le_bytes`] and [`Uint::to_be_bytes`] require the output size to
140///   be provided as a const-generic argument. They will runtime panic if the
141///   provided size is incorrect.
142/// * [`Uint::widening_mul`] takes as argument an [`Uint`] of arbitrary size and
143///   returns a result that is sized to fit the product without overflow (i.e.
144///   the sum of the bit sizes of self and the argument). The std version
145///   requires same-sized arguments and returns a pair of lower and higher bits.
146///
147/// [std-overflow]: https://doc.rust-lang.org/reference/expressions/operator-expr.html#overflow
148#[derive(Clone, Copy, Eq, PartialEq, Hash)]
149#[repr(transparent)]
150pub struct Uint<const BITS: usize, const LIMBS: usize> {
151    limbs: [u64; LIMBS],
152}
153
154impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
155    /// The size of this integer type in 64-bit limbs.
156    pub const LIMBS: usize = {
157        let limbs = nlimbs(BITS);
158        assert!(
159            LIMBS == limbs,
160            "Can not construct Uint<BITS, LIMBS> with incorrect LIMBS"
161        );
162        limbs
163    };
164
165    /// Bit mask for the last limb.
166    pub const MASK: u64 = mask(BITS);
167
168    const SHOULD_MASK: bool = BITS > 0 && Self::MASK != u64::MAX;
169
170    /// The size of this integer type in bits.
171    pub const BITS: usize = BITS;
172
173    /// The value zero. This is the only value that exists in all [`Uint`]
174    /// types.
175    pub const ZERO: Self = Self::from_limbs([0; LIMBS]);
176
177    /// The value one. This is useful to have as a constant for use in const fn.
178    ///
179    /// Zero if `BITS` is zero.
180    pub const ONE: Self = Self::const_from_u64(1);
181
182    /// The smallest value that can be represented by this integer type.
183    /// Synonym for [`Self::ZERO`].
184    pub const MIN: Self = Self::ZERO;
185
186    /// The largest value that can be represented by this integer type,
187    /// $2^{\mathtt{BITS}} − 1$.
188    pub const MAX: Self = Self::from_limbs_unmasked([u64::MAX; LIMBS]);
189
190    /// View the array of limbs.
191    #[inline(always)]
192    #[must_use]
193    pub const fn as_limbs(&self) -> &[u64; LIMBS] {
194        &self.limbs
195    }
196
197    /// Access the array of limbs.
198    ///
199    /// # Safety
200    ///
201    /// This function is unsafe because it allows setting a bit outside the bit
202    /// size if the bit-size is not limb-aligned.
203    #[inline(always)]
204    #[must_use]
205    pub const unsafe fn as_limbs_mut(&mut self) -> &mut [u64; LIMBS] {
206        &mut self.limbs
207    }
208
209    /// Convert to a array of limbs.
210    ///
211    /// Limbs are least significant first.
212    #[inline(always)]
213    #[must_use]
214    pub const fn into_limbs(self) -> [u64; LIMBS] {
215        self.limbs
216    }
217
218    #[inline]
219    pub(crate) const fn as_double_words(&self) -> &[pu128] {
220        assert!(LIMBS >= 2);
221        let (ptr, len) = (self.limbs.as_ptr(), self.limbs.len());
222        unsafe { core::slice::from_raw_parts(ptr.cast(), len / 2) }
223    }
224
225    /// Construct a new integer from little-endian a array of limbs.
226    ///
227    /// # Panics
228    ///
229    /// Panics it `LIMBS` is not equal to `nlimbs(BITS)`.
230    ///
231    /// Panics if the value is too large for the bit-size of the Uint.
232    #[inline(always)]
233    #[must_use]
234    #[track_caller]
235    pub const fn from_limbs(limbs: [u64; LIMBS]) -> Self {
236        if Self::SHOULD_MASK {
237            // FEATURE: (BLOCKED) Add `<{BITS}>` to the type when Display works in const fn.
238            assert!(
239                limbs[LIMBS - 1] <= Self::MASK,
240                "Value too large for this Uint"
241            );
242        }
243        let _ = Self::LIMBS; // Triggers the assertion.
244        Self { limbs }
245    }
246
247    #[inline(always)]
248    #[must_use]
249    const fn from_limbs_unmasked(limbs: [u64; LIMBS]) -> Self {
250        let _ = Self::LIMBS; // Triggers the assertion.
251        Self { limbs }.masked()
252    }
253
254    /// Construct a new integer from little-endian a slice of limbs.
255    ///
256    /// # Panics
257    ///
258    /// Panics if the value is too large for the bit-size of the Uint.
259    #[inline]
260    #[must_use]
261    #[track_caller]
262    pub fn from_limbs_slice(slice: &[u64]) -> Self {
263        match Self::overflowing_from_limbs_slice(slice) {
264            (n, false) => n,
265            (_, true) => panic!("Value too large for this Uint"),
266        }
267    }
268
269    /// Construct a new integer from little-endian a slice of limbs, or `None`
270    /// if the value is too large for the [`Uint`].
271    #[inline]
272    #[must_use]
273    pub fn checked_from_limbs_slice(slice: &[u64]) -> Option<Self> {
274        match Self::overflowing_from_limbs_slice(slice) {
275            (n, false) => Some(n),
276            (_, true) => None,
277        }
278    }
279
280    /// Construct a new [`Uint`] from a little-endian slice of limbs. Returns
281    /// a potentially truncated value.
282    #[inline]
283    #[must_use]
284    pub fn wrapping_from_limbs_slice(slice: &[u64]) -> Self {
285        Self::overflowing_from_limbs_slice(slice).0
286    }
287
288    /// Construct a new [`Uint`] from a little-endian slice of limbs. Returns
289    /// a potentially truncated value and a boolean indicating whether the value
290    /// was truncated.
291    #[inline]
292    #[must_use]
293    pub fn overflowing_from_limbs_slice(slice: &[u64]) -> (Self, bool) {
294        if slice.len() < LIMBS {
295            let mut limbs = [0; LIMBS];
296            limbs[..slice.len()].copy_from_slice(slice);
297            (Self::from_limbs(limbs), false)
298        } else {
299            let (head, tail) = slice.split_at(LIMBS);
300            let mut limbs = [0; LIMBS];
301            limbs.copy_from_slice(head);
302            let mut overflow = tail.iter().any(|&limb| limb != 0);
303            if LIMBS > 0 {
304                overflow |= limbs[LIMBS - 1] > Self::MASK;
305                limbs[LIMBS - 1] &= Self::MASK;
306            }
307            (Self::from_limbs(limbs), overflow)
308        }
309    }
310
311    /// Construct a new [`Uint`] from a little-endian slice of limbs. Returns
312    /// the maximum value if the value is too large for the [`Uint`].
313    #[inline]
314    #[must_use]
315    pub fn saturating_from_limbs_slice(slice: &[u64]) -> Self {
316        match Self::overflowing_from_limbs_slice(slice) {
317            (n, false) => n,
318            (_, true) => Self::MAX,
319        }
320    }
321
322    #[inline(always)]
323    const fn apply_mask(&mut self) {
324        if Self::SHOULD_MASK {
325            self.limbs[LIMBS - 1] &= Self::MASK;
326        }
327    }
328
329    #[inline(always)]
330    const fn masked(mut self) -> Self {
331        self.apply_mask();
332        self
333    }
334}
335
336impl<const BITS: usize, const LIMBS: usize> Default for Uint<BITS, LIMBS> {
337    #[inline]
338    fn default() -> Self {
339        Self::ZERO
340    }
341}
342
343/// Number of `u64` limbs required to represent the given number of bits.
344/// This needs to be public because it is used in the `Uint` type.
345#[inline]
346#[must_use]
347pub const fn nlimbs(bits: usize) -> usize {
348    bits.div_ceil(64)
349}
350
351/// Mask to apply to the highest limb to get the correct number of bits.
352#[inline]
353#[must_use]
354pub const fn mask(bits: usize) -> u64 {
355    if bits == 0 {
356        return 0;
357    }
358    let bits = bits % 64;
359    if bits == 0 { u64::MAX } else { (1 << bits) - 1 }
360}
361
362// Not public API.
363#[doc(hidden)]
364pub mod __private {
365    pub use ruint_macro;
366}
367
368#[cfg(test)]
369mod test {
370    use super::*;
371
372    #[test]
373    fn test_mask() {
374        assert_eq!(mask(0), 0);
375        assert_eq!(mask(1), 1);
376        assert_eq!(mask(5), 0x1f);
377        assert_eq!(mask(63), u64::MAX >> 1);
378        assert_eq!(mask(64), u64::MAX);
379    }
380
381    #[test]
382    fn test_max() {
383        assert_eq!(Uint::<0, 0>::MAX, Uint::ZERO);
384        assert_eq!(Uint::<1, 1>::MAX, Uint::from_limbs([1]));
385        assert_eq!(Uint::<7, 1>::MAX, Uint::from_limbs([127]));
386        assert_eq!(Uint::<64, 1>::MAX, Uint::from_limbs([u64::MAX]));
387        assert_eq!(
388            Uint::<100, 2>::MAX,
389            Uint::from_limbs([u64::MAX, u64::MAX >> 28])
390        );
391    }
392
393    #[test]
394    fn test_constants() {
395        const_for!(BITS in SIZES {
396            const LIMBS: usize = nlimbs(BITS);
397            assert_eq!(Uint::<BITS, LIMBS>::MIN, Uint::<BITS, LIMBS>::ZERO);
398            let _ = Uint::<BITS, LIMBS>::MAX;
399        });
400    }
401}
ruint/lib.rs

ruint/
lib.rs
