ruint/
lib.rs

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

ruint/
lib.rs
