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

ruint/
lib.rs
