ruint/
lib.rs

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

ruint/
lib.rs
