ruint/
lib.rs

1#![doc = include_str!("../README.md")]
2#![doc(issue_tracker_base_url = "https://github.com/alloy-rs/ruint/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// On riscv, `PartialEq` is implemented by hand in `cmp.rs` rather than derived: the
149// derive compares the `[u64; LIMBS]` limb array, which LLVM lowers to a `bcmp`/`memcmp`
150// libcall there (no inline-memcmp expansion), where the call dwarfs the comparison
151// itself.
152#[derive(Clone, Copy, Eq, Hash)]
153#[cfg_attr(
154    not(any(target_arch = "riscv32", target_arch = "riscv64")),
155    derive(PartialEq)
156)]
157#[repr(transparent)]
158pub struct Uint<const BITS: usize, const LIMBS: usize> {
159    limbs: [u64; LIMBS],
160}
161
162impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
163    /// The size of this integer type in 64-bit limbs.
164    pub const LIMBS: usize = {
165        let limbs = nlimbs(BITS);
166        assert!(
167            LIMBS == limbs,
168            "Can not construct Uint<BITS, LIMBS> with incorrect LIMBS"
169        );
170        limbs
171    };
172
173    /// Bit mask for the last limb.
174    pub const MASK: u64 = mask(BITS);
175
176    const SHOULD_MASK: bool = BITS > 0 && Self::MASK != u64::MAX;
177
178    /// The size of this integer type in bits.
179    pub const BITS: usize = BITS;
180
181    /// The value zero. This is the only value that exists in all [`Uint`]
182    /// types.
183    pub const ZERO: Self = Self::from_limbs([0; LIMBS]);
184
185    /// The value one. This is useful to have as a constant for use in const fn.
186    ///
187    /// Zero if `BITS` is zero.
188    pub const ONE: Self = Self::const_from_u64(1);
189
190    /// The smallest value that can be represented by this integer type.
191    /// Synonym for [`Self::ZERO`].
192    pub const MIN: Self = Self::ZERO;
193
194    /// The largest value that can be represented by this integer type,
195    /// $2^{\mathtt{BITS}} − 1$.
196    pub const MAX: Self = Self::from_limbs_unmasked([u64::MAX; LIMBS]);
197
198    /// View the array of limbs.
199    #[inline(always)]
200    #[must_use]
201    pub const fn as_limbs(&self) -> &[u64; LIMBS] {
202        &self.limbs
203    }
204
205    /// Access the array of limbs.
206    ///
207    /// # Safety
208    ///
209    /// This function is unsafe because it allows setting a bit outside the bit
210    /// size if the bit-size is not limb-aligned.
211    #[inline(always)]
212    #[must_use]
213    pub const unsafe fn as_limbs_mut(&mut self) -> &mut [u64; LIMBS] {
214        &mut self.limbs
215    }
216
217    /// Convert to a array of limbs.
218    ///
219    /// Limbs are least significant first.
220    #[inline(always)]
221    #[must_use]
222    pub const fn into_limbs(self) -> [u64; LIMBS] {
223        self.limbs
224    }
225
226    #[inline]
227    pub(crate) const fn as_double_words(&self) -> &[pu128] {
228        assert!(LIMBS >= 2);
229        let (ptr, len) = (self.limbs.as_ptr(), self.limbs.len());
230        unsafe { core::slice::from_raw_parts(ptr.cast(), len / 2) }
231    }
232
233    /// Construct a new integer from little-endian a array of limbs.
234    ///
235    /// # Panics
236    ///
237    /// Panics it `LIMBS` is not equal to `nlimbs(BITS)`.
238    ///
239    /// Panics if the value is too large for the bit-size of the Uint.
240    #[inline(always)]
241    #[must_use]
242    #[track_caller]
243    pub const fn from_limbs(limbs: [u64; LIMBS]) -> Self {
244        if Self::SHOULD_MASK {
245            // FEATURE: (BLOCKED) Add `<{BITS}>` to the type when Display works in const fn.
246            assert!(
247                limbs[LIMBS - 1] <= Self::MASK,
248                "Value too large for this Uint"
249            );
250        }
251        let _ = Self::LIMBS; // Triggers the assertion.
252        Self { limbs }
253    }
254
255    #[inline(always)]
256    #[must_use]
257    const fn from_limbs_unmasked(limbs: [u64; LIMBS]) -> Self {
258        let _ = Self::LIMBS; // Triggers the assertion.
259        Self { limbs }.masked()
260    }
261
262    /// Construct a new integer from little-endian a slice of limbs.
263    ///
264    /// # Panics
265    ///
266    /// Panics if the value is too large for the bit-size of the Uint.
267    #[inline]
268    #[must_use]
269    #[track_caller]
270    pub const fn from_limbs_slice(slice: &[u64]) -> Self {
271        match Self::overflowing_from_limbs_slice(slice) {
272            (n, false) => n,
273            (_, true) => panic!("Value too large for this Uint"),
274        }
275    }
276
277    /// Construct a new integer from little-endian a slice of limbs, or `None`
278    /// if the value is too large for the [`Uint`].
279    #[inline]
280    #[must_use]
281    pub const fn checked_from_limbs_slice(slice: &[u64]) -> Option<Self> {
282        match Self::overflowing_from_limbs_slice(slice) {
283            (n, false) => Some(n),
284            (_, true) => None,
285        }
286    }
287
288    /// Construct a new [`Uint`] from a little-endian slice of limbs. Returns
289    /// a potentially truncated value.
290    #[inline]
291    #[must_use]
292    pub const fn wrapping_from_limbs_slice(slice: &[u64]) -> Self {
293        Self::overflowing_from_limbs_slice(slice).0
294    }
295
296    /// Construct a new [`Uint`] from a little-endian slice of limbs. Returns
297    /// a potentially truncated value and a boolean indicating whether the value
298    /// was truncated.
299    #[inline]
300    #[must_use]
301    pub const fn overflowing_from_limbs_slice(slice: &[u64]) -> (Self, bool) {
302        if slice.len() < LIMBS {
303            let mut limbs = [0; LIMBS];
304            // SAFETY: `slice` and `limbs` are disjoint, and `limbs` has at
305            // least `slice.len()` elements.
306            unsafe {
307                core::ptr::copy_nonoverlapping(slice.as_ptr(), limbs.as_mut_ptr(), slice.len());
308            }
309            (Self::from_limbs(limbs), false)
310        } else {
311            let (head, tail) = slice.split_at(LIMBS);
312            let mut limbs = [0; LIMBS];
313            // SAFETY: `head` and `limbs` have the same length and are disjoint.
314            unsafe {
315                core::ptr::copy_nonoverlapping(head.as_ptr(), limbs.as_mut_ptr(), LIMBS);
316            }
317            let mut overflow = false;
318            const_range_for!(&limb in ref tail => {
319                if limb != 0 {
320                    overflow = true;
321                    break;
322                }
323            });
324            if LIMBS > 0 {
325                overflow |= limbs[LIMBS - 1] > Self::MASK;
326                limbs[LIMBS - 1] &= Self::MASK;
327            }
328            (Self::from_limbs(limbs), overflow)
329        }
330    }
331
332    /// Construct a new [`Uint`] from a little-endian slice of limbs. Returns
333    /// the maximum value if the value is too large for the [`Uint`].
334    #[inline]
335    #[must_use]
336    pub const fn saturating_from_limbs_slice(slice: &[u64]) -> Self {
337        match Self::overflowing_from_limbs_slice(slice) {
338            (n, false) => n,
339            (_, true) => Self::MAX,
340        }
341    }
342
343    #[inline(always)]
344    const fn apply_mask(&mut self) {
345        if Self::SHOULD_MASK {
346            self.limbs[LIMBS - 1] &= Self::MASK;
347        }
348    }
349
350    #[inline(always)]
351    const fn maskable_bits(&self) -> u64 {
352        if Self::SHOULD_MASK {
353            self.limbs[LIMBS - 1] & !Self::MASK
354        } else {
355            0
356        }
357    }
358
359    #[inline(always)]
360    const fn masked(mut self) -> Self {
361        self.apply_mask();
362        self
363    }
364}
365
366impl<const BITS: usize, const LIMBS: usize> Default for Uint<BITS, LIMBS> {
367    #[inline]
368    fn default() -> Self {
369        Self::ZERO
370    }
371}
372
373/// Number of `u64` limbs required to represent the given number of bits.
374/// This needs to be public because it is used in the `Uint` type.
375#[inline]
376#[must_use]
377pub const fn nlimbs(bits: usize) -> usize {
378    bits.div_ceil(64)
379}
380
381/// Mask to apply to the highest limb to get the correct number of bits.
382#[inline]
383#[must_use]
384pub const fn mask(bits: usize) -> u64 {
385    if bits == 0 {
386        return 0;
387    }
388    let bits = bits % 64;
389    if bits == 0 { u64::MAX } else { (1 << bits) - 1 }
390}
391
392// Not public API.
393#[doc(hidden)]
394pub mod __private {
395    pub use ruint_macro;
396}
397
398#[cfg(test)]
399mod test {
400    use super::*;
401
402    #[test]
403    fn test_mask() {
404        assert_eq!(mask(0), 0);
405        assert_eq!(mask(1), 1);
406        assert_eq!(mask(5), 0x1f);
407        assert_eq!(mask(63), u64::MAX >> 1);
408        assert_eq!(mask(64), u64::MAX);
409    }
410
411    #[test]
412    fn test_max() {
413        assert_eq!(Uint::<0, 0>::MAX, Uint::ZERO);
414        assert_eq!(Uint::<1, 1>::MAX, Uint::from_limbs([1]));
415        assert_eq!(Uint::<7, 1>::MAX, Uint::from_limbs([127]));
416        assert_eq!(Uint::<64, 1>::MAX, Uint::from_limbs([u64::MAX]));
417        assert_eq!(
418            Uint::<100, 2>::MAX,
419            Uint::from_limbs([u64::MAX, u64::MAX >> 28])
420        );
421    }
422
423    #[test]
424    fn test_constants() {
425        const_for!(BITS in SIZES {
426            const LIMBS: usize = nlimbs(BITS);
427            assert_eq!(Uint::<BITS, LIMBS>::MIN, Uint::<BITS, LIMBS>::ZERO);
428            let _ = Uint::<BITS, LIMBS>::MAX;
429        });
430    }
431
432    #[test]
433    fn test_const_from_limbs_slice() {
434        const_for!(BITS in SIZES {
435            const LIMBS: usize = nlimbs(BITS);
436            type U = Uint<BITS, LIMBS>;
437            const {
438                let empty = [];
439                assert!(U::from_limbs_slice(&empty).const_is_zero());
440                assert!(matches!(U::checked_from_limbs_slice(&empty), Some(value) if value.const_is_zero()));
441                assert!(U::wrapping_from_limbs_slice(&empty).const_is_zero());
442
443                let source = [u64::MAX, u64::MAX];
444                let (truncated, overflow) = U::overflowing_from_limbs_slice(&source);
445                assert!(U::wrapping_from_limbs_slice(&source).const_eq(&truncated));
446                let saturated = U::saturating_from_limbs_slice(&source);
447                if overflow {
448                    assert!(saturated.const_eq(&U::MAX));
449                } else {
450                    assert!(saturated.const_eq(&truncated));
451                }
452            }
453        });
454    }
455}
ruint/lib.rs

ruint/
lib.rs
