From d10fc712b14685ad1f706e3895653ab2524a6983 Mon Sep 17 00:00:00 2001 From: DaniPopes <57450786+DaniPopes@users.noreply.github.com> Date: Fri, 28 Feb 2025 19:52:49 +0100 Subject: [PATCH] feat: add `random`, `random_with`, `randomize`, `randomize_with` methods Closes https://github.com/recmo/uint/issues/440. --- CHANGELOG.md | 6 +++-- src/add.rs | 6 ++--- src/bits.rs | 5 ++-- src/lib.rs | 33 +++++++++++++++++------ src/mul.rs | 6 ++--- src/support/proptest.rs | 7 +---- src/support/rand.rs | 59 ++++++++++++++++++++++++++++++++++------- 7 files changed, 87 insertions(+), 35 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 3fb06eb8..6f12cd54 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -13,6 +13,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - Add const `not` function ([#442]) - Make `leading_zeros`, `leading_ones`, `count_ones`, `count_zeros`, `bit_len`, `byte_len`, `is_power_of_two` functions `const` ([#442]) +- `random`, `random_with`, `randomize`, `randomize_with` methods ([#444]) ### Changed @@ -22,9 +23,10 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - Fix `checked_byte` bounds check and make it const ([#438]) -[#442]: https://github.com/recmo/uint/pull/442 -[#439]: https://github.com/recmo/uint/pull/439 [#438]: https://github.com/recmo/uint/pull/438 +[#439]: https://github.com/recmo/uint/pull/439 +[#442]: https://github.com/recmo/uint/pull/442 +[#444]: https://github.com/recmo/uint/pull/444 ## [1.13.1] - 2025-02-18 diff --git a/src/add.rs b/src/add.rs index 9c508b73..506706ec 100644 --- a/src/add.rs +++ b/src/add.rs @@ -69,8 +69,7 @@ impl Uint { i += 1; } let overflow = carry | (self.limbs[LIMBS - 1] > Self::MASK); - self.limbs[LIMBS - 1] &= Self::MASK; - (self, overflow) + (self.masked(), overflow) } /// Calculates $\mod{-\mathtt{self}}_{2^{BITS}}$. @@ -103,8 +102,7 @@ impl Uint { i += 1; } let overflow = borrow | (self.limbs[LIMBS - 1] > Self::MASK); - self.limbs[LIMBS - 1] &= Self::MASK; - (self, overflow) + (self.masked(), overflow) } /// Computes `self + rhs`, saturating at the numeric bounds instead of diff --git a/src/bits.rs b/src/bits.rs index e30ee4f5..c88bf1e7 100644 --- a/src/bits.rs +++ b/src/bits.rs @@ -134,8 +134,7 @@ impl Uint { i += 1; } - self.limbs[LIMBS - 1] &= Self::MASK; - self + self.masked() } /// Returns the number of leading zeros in the binary representation of @@ -324,7 +323,7 @@ impl Uint { r.limbs[i + limbs] = (x << bits) | carry; carry = (x >> (word_bits - bits - 1)) >> 1; } - r.limbs[LIMBS - 1] &= Self::MASK; + r.apply_mask(); (r, carry != 0) } diff --git a/src/lib.rs b/src/lib.rs index a581c123..580f49e2 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -167,6 +167,8 @@ impl Uint { /// Bit mask for the last limb. pub const MASK: u64 = mask(BITS); + const SHOULD_MASK: bool = BITS > 0 && Self::MASK != u64::MAX; + /// The size of this integer type in bits. pub const BITS: usize = BITS; @@ -180,13 +182,7 @@ impl Uint { /// The largest value that can be represented by this integer type, /// $2^{\mathtt{BITS}} − 1$. - pub const MAX: Self = { - let mut limbs = [u64::MAX; LIMBS]; - if BITS > 0 { - limbs[LIMBS - 1] &= Self::MASK; - } - Self::from_limbs(limbs) - }; + pub const MAX: Self = Self::from_limbs_unmasked([u64::MAX; LIMBS]); /// View the array of limbs. #[inline(always)] @@ -227,7 +223,7 @@ impl Uint { #[must_use] #[track_caller] pub const fn from_limbs(limbs: [u64; LIMBS]) -> Self { - if BITS > 0 && Self::MASK != u64::MAX { + if Self::SHOULD_MASK { // FEATURE: (BLOCKED) Add `<{BITS}>` to the type when Display works in const fn. assert!( limbs[Self::LIMBS - 1] <= Self::MASK, @@ -237,6 +233,12 @@ impl Uint { Self { limbs } } + #[inline(always)] + #[must_use] + const fn from_limbs_unmasked(limbs: [u64; LIMBS]) -> Self { + Self { limbs }.masked() + } + /// Construct a new integer from little-endian a slice of limbs. /// /// # Panics @@ -304,6 +306,21 @@ impl Uint { (_, true) => Self::MAX, } } + + #[inline(always)] + fn apply_mask(&mut self) { + if Self::SHOULD_MASK { + self.limbs[LIMBS - 1] &= Self::MASK; + } + } + + #[inline(always)] + const fn masked(mut self) -> Self { + if Self::SHOULD_MASK { + self.limbs[LIMBS - 1] &= Self::MASK; + } + self + } } impl Default for Uint { diff --git a/src/mul.rs b/src/mul.rs index 51056038..3b627121 100644 --- a/src/mul.rs +++ b/src/mul.rs @@ -41,7 +41,7 @@ impl Uint { let mut overflow = algorithms::addmul(&mut result.limbs, self.as_limbs(), rhs.as_limbs()); if BITS > 0 { overflow |= result.limbs[LIMBS - 1] > Self::MASK; - result.limbs[LIMBS - 1] &= Self::MASK; + result.apply_mask(); } (result, overflow) } @@ -64,7 +64,7 @@ impl Uint { let mut result = Self::ZERO; algorithms::addmul_n(&mut result.limbs, self.as_limbs(), rhs.as_limbs()); if BITS > 0 { - result.limbs[LIMBS - 1] &= Self::MASK; + result.apply_mask(); } result } @@ -99,7 +99,7 @@ impl Uint { result *= Self::from(2) - self * result; correct_limbs *= 2; } - result.limbs[LIMBS - 1] &= Self::MASK; + result.apply_mask(); Some(result) } diff --git a/src/support/proptest.rs b/src/support/proptest.rs index 5f798036..cff9d5ea 100644 --- a/src/support/proptest.rs +++ b/src/support/proptest.rs @@ -18,12 +18,7 @@ impl Arbitrary for Uint { } fn arbitrary_with((): Self::Parameters) -> Self::Strategy { - any::<[u64; LIMBS]>().prop_map(|mut limbs| { - if LIMBS > 0 { - limbs[LIMBS - 1] &= Self::MASK; - } - Self::from_limbs(limbs) - }) + any::<[u64; LIMBS]>().prop_map(Self::from_limbs_unmasked) } } diff --git a/src/support/rand.rs b/src/support/rand.rs index d79af0e9..9b952a54 100644 --- a/src/support/rand.rs +++ b/src/support/rand.rs @@ -7,20 +7,61 @@ use crate::Uint; use rand::{ - distributions::{Distribution, Standard, Uniform}, + distributions::{Distribution, Standard}, Rng, }; impl Distribution> for Standard { + #[inline] fn sample(&self, rng: &mut R) -> Uint { - let mut limbs = [0; LIMBS]; - if let Some((last, rest)) = limbs.split_last_mut() { - for limb in rest { - *limb = rng.gen(); - } - *last = Uniform::new_inclusive(0, Uint::::MASK).sample(rng); - } - Uint::::from_limbs(limbs) + >::random_with(rng) + } +} + +impl Uint { + /// Creates a new [`Uint`] with the default cryptographic random number + /// generator. + /// + /// This is currently [`rand::thread_rng`]. + #[inline] + #[must_use] + #[cfg(feature = "std")] + pub fn random() -> Self { + // SAFETY: `uint` is only accessible after random initialization. + #[allow(clippy::uninit_assumed_init)] + let mut uint = unsafe { core::mem::MaybeUninit::::uninit().assume_init() }; + uint.randomize(); + uint + } + + /// Creates a new [`Uint`] with the given random number generator. + #[inline] + #[doc(alias = "random_using")] + #[must_use] + pub fn random_with(rng: &mut R) -> Self { + // SAFETY: `uint` is only accessible after random initialization. + #[allow(clippy::uninit_assumed_init)] + let mut uint = unsafe { core::mem::MaybeUninit::::uninit().assume_init() }; + uint.randomize_with(rng); + uint + } + + /// Fills this [`Uint`] with the default cryptographic random number + /// generator. + /// + /// See [`random`](Self::random) for more details. + #[inline] + #[cfg(feature = "std")] + pub fn randomize(&mut self) { + self.randomize_with(&mut rand::thread_rng()); + } + + /// Fills this [`Uint`] with the given random number generator. + #[inline] + #[doc(alias = "randomize_using")] + pub fn randomize_with(&mut self, rng: &mut R) { + rng.fill(&mut self.limbs[..]); + self.apply_mask(); } }