ruint/
lib.rs

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

ruint/
lib.rs
