8000 perf: improve conversion to primitive integers by DaniPopes · Pull Request #477 · recmo/uint · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

perf: improve conversion to primitive integers #477

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 2 commits into from
May 29, 2025
Merged

perf: improve conversion to primitive integers #477

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
81cebfc
perf: improve conversion to primitive integers
DaniPopes May 29, 2025
0e26736
Merge branch 'main' into special-from
prestwich May 29, 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 proptest-regressions/algorithms/gcd/mod.txt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -7,3 +7,5 @@
cc e80d6610b72805963058b52f9c024568385d5591c2c6bb8771e06807fb723078 # shrinks to a = 0x03_U2, b = 0x03_U2
cc 48ada708fbffc83f19348c31ee9388f57b3f22f1c5002f6e933c65454f8f022f # shrinks to a = 0x00_U2, b = 0x03_U2
cc 9d90b9bd7f76b2bda5e809f460c255d5f645ee8b91fb309dc603930f49ff491c # shrinks to a = 0x01275e59cb2997da6a_U65, b = 0x0191dcee62b362fb99_U65
cc dc0fbfc4cd9fe8eb6fb2e49a387d7ae1091a2a4220b7306400d81cae26a3ba26 # shrinks to a = 3, b = 3
cc 4ed79a81d375438e0e0828fae4e14455be9804edc93bb7b4652042416e3d19de # shrinks to a = 1, b = 1
33 changes: 22 additions & 11 deletions src/bits.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -135,24 +135,35 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
self.masked()
}

/// Returns the number of leading zeros in the binary representation of
/// `self`.
/// Returns the number of significant words (limbs) in the integer.
///
/// If this is 0, then `limbs[1..]` are all non-zero.
#[inline]
#[must_use]
pub const fn leading_zeros(&self) -> usize {
pub(crate) const fn count_significant_words(&self) -> usize {
let mut i = LIMBS;
while i > 0 {
i -= 1;
if self.limbs[i] != 0 {
let n = LIMBS - 1 - i;
let skipped = n * 64;
let fixed = Self::MASK.leading_zeros() as usize;
let top = self.limbs[i].leading_zeros() as usize;
return skipped + top - fixed;
return i + 1;
}
}
0
}

BITS
/// Returns the number of leading zeros in the binary representation of
/// `self`.
#[inline]
#[must_use]
pub const fn leading_zeros( 10000 &self) -> usize {
let s = self.count_significant_words();
if s == 0 {
return BITS;
}
let n = LIMBS - s;
let skipped = n * 64;
let fixed = Self::MASK.leading_zeros() as usize;
let top = self.limbs[s - 1].leading_zeros() as usize;
skipped + top - fixed
}

/// Returns the number of leading ones in the binary representation of
Expand Down Expand Up @@ -315,7 +326,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
let mut r = Self::ZERO;
let mut carry = 0;
let mut i = 0;
while i < Self::LIMBS - limbs {
while i < LIMBS - limbs {
let x = self.limbs[i];
r.limbs[i + limbs] = (x << bits) | carry;
carry = (x >> (word_bits - bits - 1)) >> 1;
Expand Down
4 changes: 2 additions & 2 deletions src/bytes.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -266,7 +266,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
limbs[limb] += (bytes[c] as u64) << (byte * 8);
i += 1;
}
if Self::LIMBS > 0 && limbs[Self::LIMBS - 1] > Self::MASK {
if LIMBS > 0 && limbs[LIMBS - 1] > Self::MASK {
return None;
}
Some(Self::from_limbs(limbs))
Expand Down Expand Up @@ -342,7 +342,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
limbs[limb] += (bytes[i] as u64) << (byte * 8);
i += 1;
}
if Self::LIMBS > 0 && limbs[Self::LIMBS - 1] > Self::MASK {
if LIMBS > 0 && limbs[LIMBS - 1] > Self::MASK {
return None;
}
Some(Self::from_limbs(limbs))
Expand Down
89 changes: 69 additions & 20 deletions src/from.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -316,6 +316,21 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
) -> Option<Self> {
Self::checked_from_limbs_slice(value.as_limbs())
}

/// Returns `true` if `self` is larger than 64 bits.
#[inline]
fn gt_u64_max(&self) -> bool {
if BITS <= 512 {
// Use branchless `bitor` chain for smaller integers.
self.as_limbs()[1..]
.iter()
.copied()
.fold(0u64, core::ops::BitOr::bitor)
!= 0
} else {
self.count_significant_words() == 0
}
}
}

/// ⚠️ Workaround for [Rust issue #50133](https://github.com/rust-lang/rust/issues/50133).
Expand Down Expand Up @@ -395,18 +410,15 @@ impl<const BITS: usize, const LIMBS: usize> TryFrom<u64> for Uint<BITS, LIMBS> {

#[inline]
fn try_from(value: u64) -> Result<Self, Self::Error> {
if LIMBS <= 1 {
if value > Self::MASK {
// Construct wrapped value
let mut limbs = [0; LIMBS];
if LIMBS == 1 {
limbs[0] = value & Self::MASK;
}
return Err(ToUintError::ValueTooLarge(BITS, Self::from_limbs(limbs)));
}
if LIMBS == 0 {
return Ok(Self::ZERO);
match LIMBS {
0 | 1 if value > Self::MASK => {
return Err(ToUintError::ValueTooLarge(
BITS,
Self::from_limbs([value & Self::MASK; LIMBS]),
))
}
0 => return Ok(Self::ZERO),
_ => {}
}
let mut limbs = [0; LIMBS];
limbs[0] = value;
Expand All @@ -425,15 +437,15 @@ impl<const BITS: usize, const LIMBS: usize> TryFrom<u128> for Uint<BITS, LIMBS>
if value <= u64::MAX as u128 {
return Self::try_from(value as u64);
}
if Self::LIMBS < 2 {
if LIMBS < 2 {
return Self::try_from(value as u64)
.and_then(|n| Err(ToUintError::ValueTooLarge(BITS, n)));
}
let mut limbs = [0; LIMBS];
limbs[0] = value as u64;
limbs[1] = (value >> 64) as u64;
if Self::LIMBS == 2 && limbs[1] > Self::MASK {
limbs[1] %= Self::MASK;
if LIMBS == 2 && limbs[1] > Self::MASK {
limbs[1] &= Self::MASK;
Copy link
Contributor Author

Choose a reason for hiding this comment

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

minor drive-by fix: & instead of %

Err(ToUintError::ValueTooLarge(BITS, Self::from_limbs(limbs)))
} else {
Ok(Self::from_limbs(limbs))
Expand Down Expand Up @@ -599,10 +611,10 @@ impl<const BITS: usize, const LIMBS: usize> TryFrom<&Uint<BITS, LIMBS>> for bool
if BITS == 0 {
return Ok(false);
}
if value.bit_len() > 1 {
if value.gt_u64_max() || value.limbs[0] > 1 {
return Err(Self::Error::Overflow(BITS, value.bit(0), true));
}
Ok(value.as_limbs()[0] != 0)
Ok(value.limbs[0] != 0)
}
}

Expand All @@ -616,19 +628,17 @@ macro_rules! to_int {
#[inline]
#[allow(clippy::cast_possible_truncation, clippy::cast_possible_wrap)]
fn try_from(value: &Uint<BITS, LIMBS>) -> Result<Self, Self::Error> {
const SIGNED: bool = <$int>::MIN != 0;
const CAPACITY: usize = if SIGNED { <$int>::BITS - 1 } else { <$int>::BITS } as usize;
if BITS == 0 {
return Ok(0);
}
if value.bit_len() > CAPACITY {
if value.gt_u64_max() || value.limbs[0] > (Self::MAX as u64) {
return Err(Self::Error::Overflow(
BITS,
value.limbs[0] as Self,
Self::MAX,
));
}
Ok(value.as_limbs()[0] as Self)
Ok(value.limbs[0] as Self)
}
}
)*};
Expand Down Expand Up @@ -747,6 +757,45 @@ mod test {
});
}

#[test]
fn test_u64_max() {
assert_eq!(
Uint::<64, 1>::try_from(u64::MAX),
Ok(Uint::from_limbs([u64::MAX]))
);
assert_eq!(
Uint::<64, 1>::try_from(u64::MAX as u128),
Ok(Uint::from_limbs([u64::MAX]))
);
assert_eq!(
Uint::<64, 1>::try_from(u64::MAX as u128 + 1),
Err(ToUintError::ValueTooLarge(64, Uint::ZERO))
);

assert_eq!(
Uint::<128, 2>::try_from(u64::MAX),
Ok(Uint::from_limbs([u64::MAX, 0]))
);
assert_eq!(
Uint::<128, 2>::try_from(u64::MAX as u128),
Ok(Uint::from_limbs([u64::MAX, 0]))
);
assert_eq!(
Uint::<128, 2>::try_from(u64::MAX as u128 + 1),
Ok(Uint::from_limbs([0, 1]))
);
}

#[test]
fn test_u65() {
let x = uint!(18446744073711518810_U65);
assert_eq!(x.bit_len(), 65);
assert_eq!(
u64::try_from(x),
Err(FromUintError::Overflow(65, 1967194, u64::MAX))
);
}

#[test]
#[cfg(feature = "std")]
fn test_f64() {
Expand Down
2 changes: 1 addition & 1 deletion src/lib.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -231,7 +231,7 @@ impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
if Self::SHOULD_MASK {
// FEATURE: (BLOCKED) Add `<{BITS}>` to the type when Display works in const fn.
assert!(
limbs[Self::LIMBS - 1] <= Self::MASK,
limbs[LIMBS - 1] <= Self::MASK,
"Value too large for this Uint"
);
}
Expand Down
2 changes: 1 addition & 1 deletion src/support/pyo3.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -90,7 +90,7 @@ impl<'a, const BITS: usize, const LIMBS: usize> FromPyObject<'a> for Uint<BITS,
// On big endian we use an intermediate
#[cfg(not(target_endian = "little"))]
let py_result = {
let mut raw = vec![0_u8; Self::LIMBS * 8];
let mut raw = vec![0_u8; LIMBS * 8];
let py_result = unsafe {
ffi::_PyLong_AsByteArray(
ob.as_ptr().cast::<ffi::PyLongObject>(),
Expand Down
0