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

ruint/
lib.rs
