8000 feat: add `random`, `random_with`, `randomize`, `randomize_with` methods by DaniPopes · Pull Request #444 · recmo/uint · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

feat: add random, random_with, randomize, randomize_with methods #444

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Mar 13, 2025
Merged

feat: add random, random_with, randomize, randomize_with methods #444

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
d10fc71
feat: add `random`, `random_with`, `randomize`, `randomize_with` methods
DaniPopes Feb 28, 2025
611926a
Merge branch 'main' into randomize-fns
prestwich Mar 13, 2025
fd2b99f
Merge branch 'main' into randomize-fns
prestwich Mar 13, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 2 additions & 0 deletions CHANGELOG.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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])
- Add `const ONE` ([#448])

### Changed
Expand All @@ -26,6 +27,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
[#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
[#448]: https://github.com/recmo/uint/pull/448

## [1.13.1] - 2025-02-18
Expand Down
6 changes: 2 additions & 4 deletions src/add.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -69,8 +69,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
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}}$.
Expand Down Expand Up @@ -103,8 +102,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
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
Expand Down
5 changes: 2 additions & 3 deletions src/bits.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -134,8 +134,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
i += 1;
}

self.limbs[LIMBS - 1] &= Self::MASK;
self
self.masked()
}

/// Returns the number of leading zeros in the binary representation of
Expand Down Expand Up @@ -324,7 +323,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
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)
}

Expand Down
33 changes: 25 additions & 8 deletions src/lib.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -167,6 +167,8 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
/// 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;

Expand All @@ -185,13 +187,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {

/// 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)]
Expand Down Expand Up @@ -232,7 +228,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
#[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,
Expand All @@ -242,6 +238,12 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
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
Expand Down Expand Up @@ -309,6 +311,21 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
(_, 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<const BITS: usize, const LIMBS: usize> Default for Uint<BITS, LIMBS> {
Expand Down
6 changes: 3 additions & 3 deletions src/mul.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -41,7 +41,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
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)
}
Expand All @@ -64,7 +64,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
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
}
Expand Down Expand Up @@ -99,7 +99,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
result *= Self::from(2) - self * result;
correct_limbs *= 2;
}
result.limbs[LIMBS - 1] &= Self::MASK;
result.apply_mask();

Some(result)
}
Expand Down
7 changes: 1 addition & 6 deletions src/support/proptest.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,12 +18,7 @@ impl<const BITS: usize, const LIMBS: usize> Arbitrary for Uint<BITS, LIMBS> {
}

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)
}
}

Expand Down
59 changes: 50 additions & 9 deletions src/support/rand.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -7,20 +7,61 @@

use crate::Uint;
use rand::{
distributions::{Distribution, Standard, Uniform},
distributions::{Distribution, Standard},
Rng,
};

impl<const BITS: usize, const LIMBS: usize> Distribution<Uint<BITS, LIMBS>> for Standard {
#[inline]
fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Uint<BITS, LIMBS> {
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::<BITS, LIMBS>::MASK).sample(rng);
}
Uint::<BITS, LIMBS>::from_limbs(limbs)
<Uint<BITS, LIMBS>>::random_with(rng)
}
}

impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
/// 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::<Self>::uninit().assume_init() };
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

why unsafety here instead of Uint::ZERO?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

uses undefined memory instead of zeroing it

uint.randomize();
uint
}

/// Creates a new [`Uint`] with the given random number generator.
#[inline]
#[doc(alias = "random_using")]
#[must_use]
pub fn random_with<R: rand::RngCore + ?Sized>(rng: &mut R) -> Self {
// SAFETY: `uint` is only accessible after random initialization.
#[allow(clippy::uninit_assumed_init)]
let mut uint = unsafe { core::mem::MaybeUninit::<Self>::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<R: rand::RngCore + ?Sized>(&mut self, rng: &mut R) {
rng.fill(&mut self.limbs[..]);
self.apply_mask();
}
}

Expand Down
0