Snap for 11400057 from 80ddf53de8560c1d10267806f7f85ff53c31c77f to simpleperf-release
Change-Id: I66db7bacb7eed19a21bdf3502a9079ecd0b824a9
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 326b504..b503925 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,6 @@
{
"git": {
- "sha1": "e77ffacafef7e8fa2c2b990489b7aa30dceaed64"
- }
-}
+ "sha1": "f09eee83f174619ac9c2489e3feec62544984bc5"
+ },
+ "path_in_vcs": ""
+}
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index 611412d..d484866 100644
--- a/Android.bp
+++ b/Android.bp
@@ -56,7 +56,7 @@
host_supported: true,
crate_name: "num_bigint",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"src/lib.rs",
":copy_num-bigint_build_out",
@@ -87,7 +87,7 @@
host_supported: true,
crate_name: "num_bigint",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"src/lib.rs",
":copy_num-bigint_build_out",
@@ -117,7 +117,7 @@
host_supported: true,
crate_name: "bigint",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"tests/bigint.rs",
":copy_num-bigint_build_out",
@@ -148,7 +148,7 @@
host_supported: true,
crate_name: "bigint_bitwise",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"tests/bigint_bitwise.rs",
":copy_num-bigint_build_out",
@@ -179,7 +179,7 @@
host_supported: true,
crate_name: "bigint_scalar",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"tests/bigint_scalar.rs",
":copy_num-bigint_build_out",
@@ -210,7 +210,7 @@
host_supported: true,
crate_name: "biguint",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"tests/biguint.rs",
":copy_num-bigint_build_out",
@@ -241,7 +241,7 @@
host_supported: true,
crate_name: "biguint_scalar",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"tests/biguint_scalar.rs",
":copy_num-bigint_build_out",
@@ -272,7 +272,7 @@
host_supported: true,
crate_name: "fuzzed",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"tests/fuzzed.rs",
":copy_num-bigint_build_out",
@@ -303,7 +303,7 @@
host_supported: true,
crate_name: "modpow",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"tests/modpow.rs",
":copy_num-bigint_build_out",
@@ -334,7 +334,7 @@
host_supported: true,
crate_name: "roots",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.3",
+ cargo_pkg_version: "0.4.4",
srcs: [
"tests/roots.rs",
":copy_num-bigint_build_out",
diff --git a/Cargo.toml b/Cargo.toml
index 1c15d09..2656b5f 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -12,20 +12,39 @@
[package]
edition = "2018"
name = "num-bigint"
-version = "0.4.3"
+version = "0.4.4"
authors = ["The Rust Project Developers"]
build = "build.rs"
-exclude = ["/bors.toml", "/ci/*", "/.github/*"]
+exclude = [
+ "/bors.toml",
+ "/ci/*",
+ "/.github/*",
+]
description = "Big integer implementation for Rust"
homepage = "https://github.com/rust-num/num-bigint"
documentation = "https://docs.rs/num-bigint"
readme = "README.md"
-keywords = ["mathematics", "numerics", "bignum"]
-categories = ["algorithms", "data-structures", "science"]
+keywords = [
+ "mathematics",
+ "numerics",
+ "bignum",
+]
+categories = [
+ "algorithms",
+ "data-structures",
+ "science",
+]
license = "MIT OR Apache-2.0"
repository = "https://github.com/rust-num/num-bigint"
+
[package.metadata.docs.rs]
-features = ["std", "serde", "rand", "quickcheck", "arbitrary"]
+features = [
+ "std",
+ "serde",
+ "rand",
+ "quickcheck",
+ "arbitrary",
+]
[[bench]]
name = "bigint"
@@ -42,6 +61,7 @@
[[bench]]
name = "shootout-pidigits"
harness = false
+
[dependencies.arbitrary]
version = "1"
optional = true
@@ -53,7 +73,7 @@
default-features = false
[dependencies.num-traits]
-version = "0.2.11"
+version = "0.2.16"
features = ["i128"]
default-features = false
@@ -71,9 +91,13 @@
version = "1.0"
optional = true
default-features = false
+
[build-dependencies.autocfg]
version = "1"
[features]
default = ["std"]
-std = ["num-integer/std", "num-traits/std"]
+std = [
+ "num-integer/std",
+ "num-traits/std",
+]
diff --git a/METADATA b/METADATA
index e0e6f54..0b227f8 100644
--- a/METADATA
+++ b/METADATA
@@ -1,19 +1,20 @@
+# This project was upgraded with external_updater.
+# Usage: tools/external_updater/updater.sh update external/rust/crates/num-bigint
+# For more info, check https://cs.android.com/android/platform/superproject/+/main:tools/external_updater/README.md
+
name: "num-bigint"
description: "Big integer implementation for Rust"
third_party {
- url {
- type: HOMEPAGE
- value: "https://crates.io/crates/num-bigint"
- }
- url {
- type: ARCHIVE
- value: "https://static.crates.io/crates/num-bigint/num-bigint-0.4.3.crate"
- }
- version: "0.4.3"
license_type: NOTICE
last_upgrade_date {
- year: 2022
- month: 3
- day: 1
+ year: 2024
+ month: 2
+ day: 2
+ }
+ homepage: "https://crates.io/crates/num-bigint"
+ identifier {
+ type: "Archive"
+ value: "https://static.crates.io/crates/num-bigint/num-bigint-0.4.4.crate"
+ version: "0.4.4"
}
}
diff --git a/README.md b/README.md
index d1cedad..21f7749 100644
--- a/README.md
+++ b/README.md
@@ -50,20 +50,23 @@
crates may offer better performance with different trade-offs. The following
table offers a brief comparison to a few alternatives.
-| Crate | License | Min rustc | Implementation |
-| :--------------- | :------------- | :-------- | :------------- |
-| **`num-bigint`** | MIT/Apache-2.0 | 1.31 | pure rust |
-| [`ramp`] | Apache-2.0 | nightly | rust and inline assembly |
-| [`rug`] | LGPL-3.0+ | 1.37 | bundles [GMP] via [`gmp-mpfr-sys`] |
-| [`rust-gmp`] | MIT | stable? | links to [GMP] |
-| [`apint`] | MIT/Apache-2.0 | 1.26 | pure rust (unfinished) |
+| Crate | License | Min rustc | Implementation | Features |
+| :--------------- | :------------- | :-------- | :------------- | :------- |
+| **`num-bigint`** | MIT/Apache-2.0 | 1.31 | pure rust | dynamic width, number theoretical functions |
+| [`awint`] | MIT/Apache-2.0 | 1.66 | pure rust | fixed width, heap or stack, concatenation macros |
+| [`bnum`] | MIT/Apache-2.0 | 1.61 | pure rust | fixed width, parity with Rust primitives including floats |
+| [`crypto-bigint`] | MIT/Apache-2.0 | 1.57 | pure rust | fixed width, stack only |
+| [`ibig`] | MIT/Apache-2.0 | 1.49 | pure rust | dynamic width, number theoretical functions |
+| [`rug`] | LGPL-3.0+ | 1.65 | bundles [GMP] via [`gmp-mpfr-sys`] | all the features of GMP, MPFR, and MPC |
+
+[`awint`]: https://crates.io/crates/awint
+[`bnum`]: https://crates.io/crates/bnum
+[`crypto-bigint`]: https://crates.io/crates/crypto-bigint
+[`ibig`]: https://crates.io/crates/ibig
+[`rug`]: https://crates.io/crates/rug
[GMP]: https://gmplib.org/
[`gmp-mpfr-sys`]: https://crates.io/crates/gmp-mpfr-sys
-[`rug`]: https://crates.io/crates/rug
-[`rust-gmp`]: https://crates.io/crates/rust-gmp
-[`ramp`]: https://crates.io/crates/ramp
-[`apint`]: https://crates.io/crates/apint
## License
diff --git a/RELEASES.md b/RELEASES.md
index cd1432f..ad5dd49 100644
--- a/RELEASES.md
+++ b/RELEASES.md
@@ -1,3 +1,21 @@
+# Release 0.4.4 (2023-08-22)
+
+- [Implemented `From<bool>` for `BigInt` and `BigUint`.][239]
+- [Implemented `num_traits::Euclid` and `CheckedEuclid` for `BigInt` and `BigUint`.][245]
+- [Implemented ties-to-even for `BigInt` and `BigUint::to_f32` and `to_f64`.][271]
+- [Implemented `num_traits::FromBytes` and `ToBytes` for `BigInt` and `BigUint`.][276]
+- Limited pre-allocation from serde size hints against potential OOM.
+- Miscellaneous other code cleanups and maintenance tasks.
+
+**Contributors**: @AaronKutch, @archseer, @cuviper, @dramforever, @icecream17,
+@icedrocket, @janmarthedal, @jaybosamiya, @OliveIsAWord, @PatrickNorton,
+@smoelius, @waywardmonkeys
+
+[239]: https://github.com/rust-num/num-bigint/pull/239
+[245]: https://github.com/rust-num/num-bigint/pull/245
+[271]: https://github.com/rust-num/num-bigint/pull/271
+[276]: https://github.com/rust-num/num-bigint/pull/276
+
# Release 0.4.3 (2021-11-02)
- [GHSA-v935-pqmr-g8v9]: [Fix unexpected panics in multiplication.][228]
diff --git a/build.rs b/build.rs
index 3daed5e..5d5406c 100644
--- a/build.rs
+++ b/build.rs
@@ -5,26 +5,32 @@
use std::path::Path;
fn main() {
- let pointer_width = env::var("CARGO_CFG_TARGET_POINTER_WIDTH");
- let u64_digit = pointer_width.as_ref().map(String::as_str) == Ok("64");
+ let ptr_width = env::var("CARGO_CFG_TARGET_POINTER_WIDTH");
+ let u64_digit = ptr_width
+ .as_ref()
+ .map(|x| x == "64" || x == "128")
+ .unwrap_or(false);
+
if u64_digit {
autocfg::emit("u64_digit");
}
+
let ac = autocfg::new();
let std = if ac.probe_sysroot_crate("std") {
"std"
} else {
"core"
};
+
if ac.probe_path(&format!("{}::convert::TryFrom", std)) {
autocfg::emit("has_try_from");
}
- if let Ok(target_arch) = env::var("CARGO_CFG_TARGET_ARCH") {
- if target_arch == "x86_64" || target_arch == "x86" {
+ if let Ok(arch) = env::var("CARGO_CFG_TARGET_ARCH") {
+ if arch == "x86_64" || arch == "x86" {
let digit = if u64_digit { "u64" } else { "u32" };
- let addcarry = format!("{}::arch::{}::_addcarry_{}", std, target_arch, digit);
+ let addcarry = format!("{}::arch::{}::_addcarry_{}", std, arch, digit);
if ac.probe_path(&addcarry) {
autocfg::emit("use_addcarry");
}
diff --git a/out/probe0.ll b/out/probe0.ll
index 2caa464..304b8db 100644
--- a/out/probe0.ll
+++ b/out/probe0.ll
@@ -1,9 +1,11 @@
-; ModuleID = 'probe0.cb193764fe6a59bf-cgu.0'
-source_filename = "probe0.cb193764fe6a59bf-cgu.0"
+; ModuleID = 'probe0.7ce72c5dd1a2f6c1-cgu.0'
+source_filename = "probe0.7ce72c5dd1a2f6c1-cgu.0"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
!0 = !{i32 8, !"PIC Level", i32 2}
!1 = !{i32 2, !"RtLibUseGOT", i32 1}
+!2 = !{!"rustc version 1.74.1-dev (a28077b28 2023-12-04) (Android Rust Toolchain version linux-11359135)"}
diff --git a/out/probe1.ll b/out/probe1.ll
index 0542724..0264507 100644
--- a/out/probe1.ll
+++ b/out/probe1.ll
@@ -1,9 +1,11 @@
-; ModuleID = 'probe1.2bff0dfac3348e8e-cgu.0'
-source_filename = "probe1.2bff0dfac3348e8e-cgu.0"
+; ModuleID = 'probe1.c3864d9408e8f73b-cgu.0'
+source_filename = "probe1.c3864d9408e8f73b-cgu.0"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
!0 = !{i32 8, !"PIC Level", i32 2}
!1 = !{i32 2, !"RtLibUseGOT", i32 1}
+!2 = !{!"rustc version 1.74.1-dev (a28077b28 2023-12-04) (Android Rust Toolchain version linux-11359135)"}
diff --git a/out/probe2.ll b/out/probe2.ll
index 49f9752..8614afd 100644
--- a/out/probe2.ll
+++ b/out/probe2.ll
@@ -1,9 +1,11 @@
-; ModuleID = 'probe2.4761aca40dff6533-cgu.0'
-source_filename = "probe2.4761aca40dff6533-cgu.0"
+; ModuleID = 'probe2.9623900266cad2ed-cgu.0'
+source_filename = "probe2.9623900266cad2ed-cgu.0"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
!0 = !{i32 8, !"PIC Level", i32 2}
!1 = !{i32 2, !"RtLibUseGOT", i32 1}
+!2 = !{!"rustc version 1.74.1-dev (a28077b28 2023-12-04) (Android Rust Toolchain version linux-11359135)"}
diff --git a/out/probe3.ll b/out/probe3.ll
index 3259da1..605bbe6 100644
--- a/out/probe3.ll
+++ b/out/probe3.ll
@@ -1,9 +1,11 @@
-; ModuleID = 'probe3.7ceaed51021b51ba-cgu.0'
-source_filename = "probe3.7ceaed51021b51ba-cgu.0"
+; ModuleID = 'probe3.971c5a3bb38f7b08-cgu.0'
+source_filename = "probe3.971c5a3bb38f7b08-cgu.0"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
!0 = !{i32 8, !"PIC Level", i32 2}
!1 = !{i32 2, !"RtLibUseGOT", i32 1}
+!2 = !{!"rustc version 1.74.1-dev (a28077b28 2023-12-04) (Android Rust Toolchain version linux-11359135)"}
diff --git a/src/bigint.rs b/src/bigint.rs
index 891eeb4..97faa83 100644
--- a/src/bigint.rs
+++ b/src/bigint.rs
@@ -36,7 +36,7 @@
#[cfg(feature = "serde")]
mod serde;
-/// A Sign is a `BigInt`'s composing element.
+/// A `Sign` is a [`BigInt`]'s composing element.
#[derive(PartialEq, PartialOrd, Eq, Ord, Copy, Clone, Debug, Hash)]
pub enum Sign {
Minus,
@@ -47,7 +47,7 @@
impl Neg for Sign {
type Output = Sign;
- /// Negate Sign value.
+ /// Negate `Sign` value.
#[inline]
fn neg(self) -> Sign {
match self {
@@ -196,7 +196,7 @@
}
}
-impl<'a> Not for &'a BigInt {
+impl Not for &BigInt {
type Output = BigInt;
fn not(self) -> BigInt {
@@ -292,7 +292,7 @@
type Unsigned;
/// A convenience method for getting the absolute value of a signed primitive as unsigned
- /// See also `unsigned_abs`: https://github.com/rust-lang/rust/issues/74913
+ /// See also `unsigned_abs`: <https://github.com/rust-lang/rust/issues/74913>
fn uabs(self) -> Self::Unsigned;
fn checked_uabs(self) -> CheckedUnsignedAbs<Self::Unsigned>;
@@ -342,7 +342,7 @@
}
}
-impl<'a> Neg for &'a BigInt {
+impl Neg for &BigInt {
type Output = BigInt;
#[inline]
@@ -558,16 +558,16 @@
}
}
-/// A generic trait for converting a value to a `BigInt`. This may return
+/// A generic trait for converting a value to a [`BigInt`]. This may return
/// `None` when converting from `f32` or `f64`, and will always succeed
-/// when converting from any integer or unsigned primitive, or `BigUint`.
+/// when converting from any integer or unsigned primitive, or [`BigUint`].
pub trait ToBigInt {
- /// Converts the value of `self` to a `BigInt`.
+ /// Converts the value of `self` to a [`BigInt`].
fn to_bigint(&self) -> Option<BigInt>;
}
impl BigInt {
- /// Creates and initializes a BigInt.
+ /// Creates and initializes a [`BigInt`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
@@ -575,7 +575,7 @@
BigInt::from_biguint(sign, BigUint::new(digits))
}
- /// Creates and initializes a `BigInt`.
+ /// Creates and initializes a [`BigInt`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
@@ -589,7 +589,7 @@
BigInt { sign, data }
}
- /// Creates and initializes a `BigInt`.
+ /// Creates and initializes a [`BigInt`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
@@ -597,7 +597,7 @@
BigInt::from_biguint(sign, BigUint::from_slice(slice))
}
- /// Reinitializes a `BigInt`.
+ /// Reinitializes a [`BigInt`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
@@ -610,7 +610,7 @@
}
}
- /// Creates and initializes a `BigInt`.
+ /// Creates and initializes a [`BigInt`].
///
/// The bytes are in big-endian byte order.
///
@@ -633,7 +633,7 @@
BigInt::from_biguint(sign, BigUint::from_bytes_be(bytes))
}
- /// Creates and initializes a `BigInt`.
+ /// Creates and initializes a [`BigInt`].
///
/// The bytes are in little-endian byte order.
#[inline]
@@ -641,7 +641,7 @@
BigInt::from_biguint(sign, BigUint::from_bytes_le(bytes))
}
- /// Creates and initializes a `BigInt` from an array of bytes in
+ /// Creates and initializes a [`BigInt`] from an array of bytes in
/// two's complement binary representation.
///
/// The digits are in big-endian base 2<sup>8</sup>.
@@ -650,7 +650,7 @@
convert::from_signed_bytes_be(digits)
}
- /// Creates and initializes a `BigInt` from an array of bytes in two's complement.
+ /// Creates and initializes a [`BigInt`] from an array of bytes in two's complement.
///
/// The digits are in little-endian base 2<sup>8</sup>.
#[inline]
@@ -658,7 +658,7 @@
convert::from_signed_bytes_le(digits)
}
- /// Creates and initializes a `BigInt`.
+ /// Creates and initializes a [`BigInt`].
///
/// # Examples
///
@@ -675,7 +675,7 @@
BigInt::from_str_radix(s, radix).ok()
}
- /// Creates and initializes a `BigInt`. Each u8 of the input slice is
+ /// Creates and initializes a [`BigInt`]. Each `u8` of the input slice is
/// interpreted as one digit of the number
/// and must therefore be less than `radix`.
///
@@ -696,7 +696,7 @@
Some(BigInt::from_biguint(sign, u))
}
- /// Creates and initializes a `BigInt`. Each u8 of the input slice is
+ /// Creates and initializes a [`BigInt`]. Each `u8` of the input slice is
/// interpreted as one digit of the number
/// and must therefore be less than `radix`.
///
@@ -717,7 +717,7 @@
Some(BigInt::from_biguint(sign, u))
}
- /// Returns the sign and the byte representation of the `BigInt` in big-endian byte order.
+ /// Returns the sign and the byte representation of the [`BigInt`] in big-endian byte order.
///
/// # Examples
///
@@ -732,7 +732,7 @@
(self.sign, self.data.to_bytes_be())
}
- /// Returns the sign and the byte representation of the `BigInt` in little-endian byte order.
+ /// Returns the sign and the byte representation of the [`BigInt`] in little-endian byte order.
///
/// # Examples
///
@@ -747,7 +747,7 @@
(self.sign, self.data.to_bytes_le())
}
- /// Returns the sign and the `u32` digits representation of the `BigInt` ordered least
+ /// Returns the sign and the `u32` digits representation of the [`BigInt`] ordered least
/// significant digit first.
///
/// # Examples
@@ -766,7 +766,7 @@
(self.sign, self.data.to_u32_digits())
}
- /// Returns the sign and the `u64` digits representation of the `BigInt` ordered least
+ /// Returns the sign and the `u64` digits representation of the [`BigInt`] ordered least
/// significant digit first.
///
/// # Examples
@@ -786,7 +786,7 @@
(self.sign, self.data.to_u64_digits())
}
- /// Returns an iterator of `u32` digits representation of the `BigInt` ordered least
+ /// Returns an iterator of `u32` digits representation of the [`BigInt`] ordered least
/// significant digit first.
///
/// # Examples
@@ -805,7 +805,7 @@
self.data.iter_u32_digits()
}
- /// Returns an iterator of `u64` digits representation of the `BigInt` ordered least
+ /// Returns an iterator of `u64` digits representation of the [`BigInt`] ordered least
/// significant digit first.
///
/// # Examples
@@ -825,7 +825,7 @@
self.data.iter_u64_digits()
}
- /// Returns the two's-complement byte representation of the `BigInt` in big-endian byte order.
+ /// Returns the two's-complement byte representation of the [`BigInt`] in big-endian byte order.
///
/// # Examples
///
@@ -840,7 +840,7 @@
convert::to_signed_bytes_be(self)
}
- /// Returns the two's-complement byte representation of the `BigInt` in little-endian byte order.
+ /// Returns the two's-complement byte representation of the [`BigInt`] in little-endian byte order.
///
/// # Examples
///
@@ -880,7 +880,7 @@
/// Returns the integer in the requested base in big-endian digit order.
/// The output is not given in a human readable alphabet but as a zero
- /// based u8 number.
+ /// based `u8` number.
/// `radix` must be in the range `2...256`.
///
/// # Examples
@@ -899,7 +899,7 @@
/// Returns the integer in the requested base in little-endian digit order.
/// The output is not given in a human readable alphabet but as a zero
- /// based u8 number.
+ /// based `u8` number.
/// `radix` must be in the range `2...256`.
///
/// # Examples
@@ -916,7 +916,7 @@
(self.sign, self.data.to_radix_le(radix))
}
- /// Returns the sign of the `BigInt` as a `Sign`.
+ /// Returns the sign of the [`BigInt`] as a [`Sign`].
///
/// # Examples
///
@@ -933,7 +933,7 @@
self.sign
}
- /// Returns the magnitude of the `BigInt` as a `BigUint`.
+ /// Returns the magnitude of the [`BigInt`] as a [`BigUint`].
///
/// # Examples
///
@@ -950,8 +950,8 @@
&self.data
}
- /// Convert this `BigInt` into its `Sign` and `BigUint` magnitude,
- /// the reverse of `BigInt::from_biguint`.
+ /// Convert this [`BigInt`] into its [`Sign`] and [`BigUint`] magnitude,
+ /// the reverse of [`BigInt::from_biguint()`].
///
/// # Examples
///
@@ -968,14 +968,14 @@
(self.sign, self.data)
}
- /// Determines the fewest bits necessary to express the `BigInt`,
+ /// Determines the fewest bits necessary to express the [`BigInt`],
/// not including the sign.
#[inline]
pub fn bits(&self) -> u64 {
self.data.bits()
}
- /// Converts this `BigInt` into a `BigUint`, if it's not negative.
+ /// Converts this [`BigInt`] into a [`BigUint`], if it's not negative.
#[inline]
pub fn to_biguint(&self) -> Option<BigUint> {
match self.sign {
@@ -1026,19 +1026,19 @@
}
/// Returns the truncated principal square root of `self` --
- /// see [Roots::sqrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.sqrt).
+ /// see [`num_integer::Roots::sqrt()`].
pub fn sqrt(&self) -> Self {
Roots::sqrt(self)
}
/// Returns the truncated principal cube root of `self` --
- /// see [Roots::cbrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.cbrt).
+ /// see [`num_integer::Roots::cbrt()`].
pub fn cbrt(&self) -> Self {
Roots::cbrt(self)
}
/// Returns the truncated principal `n`th root of `self` --
- /// See [Roots::nth_root](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#tymethod.nth_root).
+ /// See [`num_integer::Roots::nth_root()`].
pub fn nth_root(&self, n: u32) -> Self {
Roots::nth_root(self, n)
}
@@ -1097,6 +1097,30 @@
}
}
+impl num_traits::FromBytes for BigInt {
+ type Bytes = [u8];
+
+ fn from_be_bytes(bytes: &Self::Bytes) -> Self {
+ Self::from_signed_bytes_be(bytes)
+ }
+
+ fn from_le_bytes(bytes: &Self::Bytes) -> Self {
+ Self::from_signed_bytes_le(bytes)
+ }
+}
+
+impl num_traits::ToBytes for BigInt {
+ type Bytes = Vec<u8>;
+
+ fn to_be_bytes(&self) -> Self::Bytes {
+ self.to_signed_bytes_be()
+ }
+
+ fn to_le_bytes(&self) -> Self::Bytes {
+ self.to_signed_bytes_le()
+ }
+}
+
#[test]
fn test_from_biguint() {
fn check(inp_s: Sign, inp_n: usize, ans_s: Sign, ans_n: usize) {
diff --git a/src/bigint/addition.rs b/src/bigint/addition.rs
index b999f62..76aeb99 100644
--- a/src/bigint/addition.rs
+++ b/src/bigint/addition.rs
@@ -30,7 +30,7 @@
};
}
-impl<'a, 'b> Add<&'b BigInt> for &'a BigInt {
+impl Add<&BigInt> for &BigInt {
type Output = BigInt;
#[inline]
@@ -46,7 +46,7 @@
}
}
-impl<'a> Add<BigInt> for &'a BigInt {
+impl Add<BigInt> for &BigInt {
type Output = BigInt;
#[inline]
@@ -55,7 +55,7 @@
}
}
-impl<'a> Add<&'a BigInt> for BigInt {
+impl Add<&BigInt> for BigInt {
type Output = BigInt;
#[inline]
@@ -73,7 +73,7 @@
}
}
-impl<'a> AddAssign<&'a BigInt> for BigInt {
+impl AddAssign<&BigInt> for BigInt {
#[inline]
fn add_assign(&mut self, other: &BigInt) {
let n = mem::replace(self, BigInt::zero());
diff --git a/src/bigint/bits.rs b/src/bigint/bits.rs
index 686def4..80f4e2c 100644
--- a/src/bigint/bits.rs
+++ b/src/bigint/bits.rs
@@ -108,7 +108,7 @@
// do not use forward_ref_ref_binop_commutative! for bitand so that we can
// clone as needed, avoiding over-allocation
-impl<'a, 'b> BitAnd<&'b BigInt> for &'a BigInt {
+impl BitAnd<&BigInt> for &BigInt {
type Output = BigInt;
#[inline]
@@ -130,7 +130,7 @@
}
}
-impl<'a> BitAnd<&'a BigInt> for BigInt {
+impl BitAnd<&BigInt> for BigInt {
type Output = BigInt;
#[inline]
@@ -142,7 +142,7 @@
forward_val_assign!(impl BitAndAssign for BigInt, bitand_assign);
-impl<'a> BitAndAssign<&'a BigInt> for BigInt {
+impl BitAndAssign<&BigInt> for BigInt {
fn bitand_assign(&mut self, other: &BigInt) {
match (self.sign, other.sign) {
(NoSign, _) => {}
@@ -247,7 +247,7 @@
// do not use forward_ref_ref_binop_commutative! for bitor so that we can
// clone as needed, avoiding over-allocation
-impl<'a, 'b> BitOr<&'b BigInt> for &'a BigInt {
+impl BitOr<&BigInt> for &BigInt {
type Output = BigInt;
#[inline]
@@ -270,7 +270,7 @@
}
}
-impl<'a> BitOr<&'a BigInt> for BigInt {
+impl BitOr<&BigInt> for BigInt {
type Output = BigInt;
#[inline]
@@ -282,7 +282,7 @@
forward_val_assign!(impl BitOrAssign for BigInt, bitor_assign);
-impl<'a> BitOrAssign<&'a BigInt> for BigInt {
+impl BitOrAssign<&BigInt> for BigInt {
fn bitor_assign(&mut self, other: &BigInt) {
match (self.sign, other.sign) {
(_, NoSign) => {}
@@ -408,7 +408,7 @@
forward_all_binop_to_val_ref_commutative!(impl BitXor for BigInt, bitxor);
-impl<'a> BitXor<&'a BigInt> for BigInt {
+impl BitXor<&BigInt> for BigInt {
type Output = BigInt;
#[inline]
@@ -420,7 +420,7 @@
forward_val_assign!(impl BitXorAssign for BigInt, bitxor_assign);
-impl<'a> BitXorAssign<&'a BigInt> for BigInt {
+impl BitXorAssign<&BigInt> for BigInt {
fn bitxor_assign(&mut self, other: &BigInt) {
match (self.sign, other.sign) {
(_, NoSign) => {}
diff --git a/src/bigint/convert.rs b/src/bigint/convert.rs
index ff8e04e..c4f888b 100644
--- a/src/bigint/convert.rs
+++ b/src/bigint/convert.rs
@@ -10,7 +10,7 @@
#[cfg(has_try_from)]
use core::convert::TryFrom;
use core::str::{self, FromStr};
-use num_traits::{FromPrimitive, Num, ToPrimitive, Zero};
+use num_traits::{FromPrimitive, Num, One, ToPrimitive, Zero};
impl FromStr for BigInt {
type Err = ParseBigIntError;
@@ -24,7 +24,7 @@
impl Num for BigInt {
type FromStrRadixErr = ParseBigIntError;
- /// Creates and initializes a BigInt.
+ /// Creates and initializes a [`BigInt`].
#[inline]
fn from_str_radix(mut s: &str, radix: u32) -> Result<BigInt, ParseBigIntError> {
let sign = if s.starts_with('-') {
@@ -367,6 +367,16 @@
impl_to_bigint!(f32, FromPrimitive::from_f32);
impl_to_bigint!(f64, FromPrimitive::from_f64);
+impl From<bool> for BigInt {
+ fn from(x: bool) -> Self {
+ if x {
+ One::one()
+ } else {
+ Zero::zero()
+ }
+ }
+}
+
#[inline]
pub(super) fn from_signed_bytes_be(digits: &[u8]) -> BigInt {
let sign = match digits.first() {
@@ -379,7 +389,7 @@
// two's-complement the content to retrieve the magnitude
let mut digits = Vec::from(digits);
twos_complement_be(&mut digits);
- BigInt::from_biguint(sign, BigUint::from_bytes_be(&*digits))
+ BigInt::from_biguint(sign, BigUint::from_bytes_be(&digits))
} else {
BigInt::from_biguint(sign, BigUint::from_bytes_be(digits))
}
@@ -397,7 +407,7 @@
// two's-complement the content to retrieve the magnitude
let mut digits = Vec::from(digits);
twos_complement_le(&mut digits);
- BigInt::from_biguint(sign, BigUint::from_bytes_le(&*digits))
+ BigInt::from_biguint(sign, BigUint::from_bytes_le(&digits))
} else {
BigInt::from_biguint(sign, BigUint::from_bytes_le(digits))
}
diff --git a/src/bigint/division.rs b/src/bigint/division.rs
index a702b8f..318d1fb 100644
--- a/src/bigint/division.rs
+++ b/src/bigint/division.rs
@@ -6,11 +6,11 @@
use core::ops::{Div, DivAssign, Rem, RemAssign};
use num_integer::Integer;
-use num_traits::{CheckedDiv, ToPrimitive, Zero};
+use num_traits::{CheckedDiv, CheckedEuclid, Euclid, Signed, ToPrimitive, Zero};
forward_all_binop_to_ref_ref!(impl Div for BigInt, div);
-impl<'a, 'b> Div<&'b BigInt> for &'a BigInt {
+impl Div<&BigInt> for &BigInt {
type Output = BigInt;
#[inline]
@@ -20,7 +20,7 @@
}
}
-impl<'a> DivAssign<&'a BigInt> for BigInt {
+impl DivAssign<&BigInt> for BigInt {
#[inline]
fn div_assign(&mut self, other: &BigInt) {
*self = &*self / other;
@@ -235,7 +235,7 @@
forward_all_binop_to_ref_ref!(impl Rem for BigInt, rem);
-impl<'a, 'b> Rem<&'b BigInt> for &'a BigInt {
+impl Rem<&BigInt> for &BigInt {
type Output = BigInt;
#[inline]
@@ -251,7 +251,7 @@
}
}
-impl<'a> RemAssign<&'a BigInt> for BigInt {
+impl RemAssign<&BigInt> for BigInt {
#[inline]
fn rem_assign(&mut self, other: &BigInt) {
*self = &*self % other;
@@ -446,3 +446,51 @@
Some(self.div(v))
}
}
+
+impl CheckedEuclid for BigInt {
+ #[inline]
+ fn checked_div_euclid(&self, v: &BigInt) -> Option<BigInt> {
+ if v.is_zero() {
+ return None;
+ }
+ Some(self.div_euclid(v))
+ }
+
+ #[inline]
+ fn checked_rem_euclid(&self, v: &BigInt) -> Option<BigInt> {
+ if v.is_zero() {
+ return None;
+ }
+ Some(self.rem_euclid(v))
+ }
+}
+
+impl Euclid for BigInt {
+ #[inline]
+ fn div_euclid(&self, v: &BigInt) -> BigInt {
+ let (q, r) = self.div_rem(v);
+ if r.is_negative() {
+ if v.is_positive() {
+ q - 1
+ } else {
+ q + 1
+ }
+ } else {
+ q
+ }
+ }
+
+ #[inline]
+ fn rem_euclid(&self, v: &BigInt) -> BigInt {
+ let r = self % v;
+ if r.is_negative() {
+ if v.is_positive() {
+ r + v
+ } else {
+ r - v
+ }
+ } else {
+ r
+ }
+ }
+}
diff --git a/src/bigint/multiplication.rs b/src/bigint/multiplication.rs
index a2d9708..82e64c2 100644
--- a/src/bigint/multiplication.rs
+++ b/src/bigint/multiplication.rs
@@ -22,8 +22,8 @@
}
macro_rules! impl_mul {
- ($(impl<$($a:lifetime),*> Mul<$Other:ty> for $Self:ty;)*) => {$(
- impl<$($a),*> Mul<$Other> for $Self {
+ ($(impl Mul<$Other:ty> for $Self:ty;)*) => {$(
+ impl Mul<$Other> for $Self {
type Output = BigInt;
#[inline]
@@ -37,15 +37,15 @@
)*}
}
impl_mul! {
- impl<> Mul<BigInt> for BigInt;
- impl<'b> Mul<&'b BigInt> for BigInt;
- impl<'a> Mul<BigInt> for &'a BigInt;
- impl<'a, 'b> Mul<&'b BigInt> for &'a BigInt;
+ impl Mul<BigInt> for BigInt;
+ impl Mul<BigInt> for &BigInt;
+ impl Mul<&BigInt> for BigInt;
+ impl Mul<&BigInt> for &BigInt;
}
macro_rules! impl_mul_assign {
- ($(impl<$($a:lifetime),*> MulAssign<$Other:ty> for BigInt;)*) => {$(
- impl<$($a),*> MulAssign<$Other> for BigInt {
+ ($(impl MulAssign<$Other:ty> for BigInt;)*) => {$(
+ impl MulAssign<$Other> for BigInt {
#[inline]
fn mul_assign(&mut self, other: $Other) {
// automatically match value/ref
@@ -61,8 +61,8 @@
)*}
}
impl_mul_assign! {
- impl<> MulAssign<BigInt> for BigInt;
- impl<'a> MulAssign<&'a BigInt> for BigInt;
+ impl MulAssign<BigInt> for BigInt;
+ impl MulAssign<&BigInt> for BigInt;
}
promote_all_scalars!(impl Mul for BigInt, mul);
diff --git a/src/bigint/power.rs b/src/bigint/power.rs
index a4dd806..4b41f4f 100644
--- a/src/bigint/power.rs
+++ b/src/bigint/power.rs
@@ -31,7 +31,7 @@
}
}
- impl<'b> Pow<&'b $T> for BigInt {
+ impl Pow<&$T> for BigInt {
type Output = BigInt;
#[inline]
@@ -40,7 +40,7 @@
}
}
- impl<'a> Pow<$T> for &'a BigInt {
+ impl Pow<$T> for &BigInt {
type Output = BigInt;
#[inline]
@@ -49,7 +49,7 @@
}
}
- impl<'a, 'b> Pow<&'b $T> for &'a BigInt {
+ impl Pow<&$T> for &BigInt {
type Output = BigInt;
#[inline]
diff --git a/src/bigint/shift.rs b/src/bigint/shift.rs
index b816e12..22bb744 100644
--- a/src/bigint/shift.rs
+++ b/src/bigint/shift.rs
@@ -6,25 +6,25 @@
macro_rules! impl_shift {
(@ref $Shx:ident :: $shx:ident, $ShxAssign:ident :: $shx_assign:ident, $rhs:ty) => {
- impl<'b> $Shx<&'b $rhs> for BigInt {
+ impl $Shx<&$rhs> for BigInt {
type Output = BigInt;
#[inline]
- fn $shx(self, rhs: &'b $rhs) -> BigInt {
+ fn $shx(self, rhs: &$rhs) -> BigInt {
$Shx::$shx(self, *rhs)
}
}
- impl<'a, 'b> $Shx<&'b $rhs> for &'a BigInt {
+ impl $Shx<&$rhs> for &BigInt {
type Output = BigInt;
#[inline]
- fn $shx(self, rhs: &'b $rhs) -> BigInt {
+ fn $shx(self, rhs: &$rhs) -> BigInt {
$Shx::$shx(self, *rhs)
}
}
- impl<'b> $ShxAssign<&'b $rhs> for BigInt {
+ impl $ShxAssign<&$rhs> for BigInt {
#[inline]
- fn $shx_assign(&mut self, rhs: &'b $rhs) {
+ fn $shx_assign(&mut self, rhs: &$rhs) {
$ShxAssign::$shx_assign(self, *rhs);
}
}
@@ -38,7 +38,7 @@
BigInt::from_biguint(self.sign, self.data << rhs)
}
}
- impl<'a> Shl<$rhs> for &'a BigInt {
+ impl Shl<$rhs> for &BigInt {
type Output = BigInt;
#[inline]
@@ -65,7 +65,7 @@
BigInt::from_biguint(self.sign, data)
}
}
- impl<'a> Shr<$rhs> for &'a BigInt {
+ impl Shr<$rhs> for &BigInt {
type Output = BigInt;
#[inline]
diff --git a/src/bigint/subtraction.rs b/src/bigint/subtraction.rs
index a12a844..548f314 100644
--- a/src/bigint/subtraction.rs
+++ b/src/bigint/subtraction.rs
@@ -29,7 +29,7 @@
};
}
-impl<'a, 'b> Sub<&'b BigInt> for &'a BigInt {
+impl Sub<&BigInt> for &BigInt {
type Output = BigInt;
#[inline]
@@ -45,7 +45,7 @@
}
}
-impl<'a> Sub<BigInt> for &'a BigInt {
+impl Sub<BigInt> for &BigInt {
type Output = BigInt;
#[inline]
@@ -54,7 +54,7 @@
}
}
-impl<'a> Sub<&'a BigInt> for BigInt {
+impl Sub<&BigInt> for BigInt {
type Output = BigInt;
#[inline]
@@ -72,7 +72,7 @@
}
}
-impl<'a> SubAssign<&'a BigInt> for BigInt {
+impl SubAssign<&BigInt> for BigInt {
#[inline]
fn sub_assign(&mut self, other: &BigInt) {
let n = mem::replace(self, BigInt::zero());
diff --git a/src/bigrand.rs b/src/bigrand.rs
index 8f0ce5b..ec03224 100644
--- a/src/bigrand.rs
+++ b/src/bigrand.rs
@@ -16,22 +16,22 @@
///
/// The `rand` feature must be enabled to use this. See crate-level documentation for details.
pub trait RandBigInt {
- /// Generate a random `BigUint` of the given bit size.
+ /// Generate a random [`BigUint`] of the given bit size.
fn gen_biguint(&mut self, bit_size: u64) -> BigUint;
- /// Generate a random BigInt of the given bit size.
+ /// Generate a random [ BigInt`] of the given bit size.
fn gen_bigint(&mut self, bit_size: u64) -> BigInt;
- /// Generate a random `BigUint` less than the given bound. Fails
+ /// Generate a random [`BigUint`] less than the given bound. Fails
/// when the bound is zero.
fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
- /// Generate a random `BigUint` within the given range. The lower
+ /// Generate a random [`BigUint`] within the given range. The lower
/// bound is inclusive; the upper bound is exclusive. Fails when
/// the upper bound is not greater than the lower bound.
fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
- /// Generate a random `BigInt` within the given range. The lower
+ /// Generate a random [`BigInt`] within the given range. The lower
/// bound is inclusive; the upper bound is exclusive. Fails when
/// the upper bound is not greater than the lower bound.
fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
@@ -141,7 +141,7 @@
}
}
-/// The back-end implementing rand's `UniformSampler` for `BigUint`.
+/// The back-end implementing rand's [`UniformSampler`] for [`BigUint`].
#[derive(Clone, Debug)]
pub struct UniformBigUint {
base: BigUint,
@@ -197,7 +197,7 @@
type Sampler = UniformBigUint;
}
-/// The back-end implementing rand's `UniformSampler` for `BigInt`.
+/// The back-end implementing rand's [`UniformSampler`] for [`BigInt`].
#[derive(Clone, Debug)]
pub struct UniformBigInt {
base: BigInt,
@@ -253,7 +253,7 @@
type Sampler = UniformBigInt;
}
-/// A random distribution for `BigUint` and `BigInt` values of a particular bit size.
+/// A random distribution for [`BigUint`] and [`BigInt`] values of a particular bit size.
///
/// The `rand` feature must be enabled to use this. See crate-level documentation for details.
#[derive(Clone, Copy, Debug)]
diff --git a/src/biguint.rs b/src/biguint.rs
index 623823c..1554eb0 100644
--- a/src/biguint.rs
+++ b/src/biguint.rs
@@ -283,6 +283,9 @@
/// Returns `true` if the number is a multiple of `other`.
#[inline]
fn is_multiple_of(&self, other: &BigUint) -> bool {
+ if other.is_zero() {
+ return self.is_zero();
+ }
(self % other).is_zero()
}
@@ -501,13 +504,13 @@
}
}
-/// A generic trait for converting a value to a `BigUint`.
+/// A generic trait for converting a value to a [`BigUint`].
pub trait ToBigUint {
- /// Converts the value of `self` to a `BigUint`.
+ /// Converts the value of `self` to a [`BigUint`].
fn to_biguint(&self) -> Option<BigUint>;
}
-/// Creates and initializes a `BigUint`.
+/// Creates and initializes a [`BigUint`].
///
/// The digits are in little-endian base matching `BigDigit`.
#[inline]
@@ -516,7 +519,7 @@
}
impl BigUint {
- /// Creates and initializes a `BigUint`.
+ /// Creates and initializes a [`BigUint`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
@@ -535,7 +538,7 @@
big
}
- /// Creates and initializes a `BigUint`.
+ /// Creates and initializes a [`BigUint`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
@@ -545,7 +548,7 @@
big
}
- /// Assign a value to a `BigUint`.
+ /// Assign a value to a [`BigUint`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
@@ -561,7 +564,7 @@
self.normalize();
}
- /// Creates and initializes a `BigUint`.
+ /// Creates and initializes a [`BigUint`].
///
/// The bytes are in big-endian byte order.
///
@@ -586,11 +589,11 @@
} else {
let mut v = bytes.to_vec();
v.reverse();
- BigUint::from_bytes_le(&*v)
+ BigUint::from_bytes_le(&v)
}
}
- /// Creates and initializes a `BigUint`.
+ /// Creates and initializes a [`BigUint`].
///
/// The bytes are in little-endian byte order.
#[inline]
@@ -602,7 +605,7 @@
}
}
- /// Creates and initializes a `BigUint`. The input slice must contain
+ /// Creates and initializes a [`BigUint`]. The input slice must contain
/// ascii/utf8 characters in [0-9a-zA-Z].
/// `radix` must be in the range `2...36`.
///
@@ -624,7 +627,7 @@
BigUint::from_str_radix(s, radix).ok()
}
- /// Creates and initializes a `BigUint`. Each u8 of the input slice is
+ /// Creates and initializes a [`BigUint`]. Each `u8` of the input slice is
/// interpreted as one digit of the number
/// and must therefore be less than `radix`.
///
@@ -644,7 +647,7 @@
convert::from_radix_be(buf, radix)
}
- /// Creates and initializes a `BigUint`. Each u8 of the input slice is
+ /// Creates and initializes a [`BigUint`]. Each `u8` of the input slice is
/// interpreted as one digit of the number
/// and must therefore be less than `radix`.
///
@@ -664,7 +667,7 @@
convert::from_radix_le(buf, radix)
}
- /// Returns the byte representation of the `BigUint` in big-endian byte order.
+ /// Returns the byte representation of the [`BigUint`] in big-endian byte order.
///
/// # Examples
///
@@ -681,7 +684,7 @@
v
}
- /// Returns the byte representation of the `BigUint` in little-endian byte order.
+ /// Returns the byte representation of the [`BigUint`] in little-endian byte order.
///
/// # Examples
///
@@ -700,7 +703,7 @@
}
}
- /// Returns the `u32` digits representation of the `BigUint` ordered least significant digit
+ /// Returns the `u32` digits representation of the [`BigUint`] ordered least significant digit
/// first.
///
/// # Examples
@@ -718,7 +721,7 @@
self.iter_u32_digits().collect()
}
- /// Returns the `u64` digits representation of the `BigUint` ordered least significant digit
+ /// Returns the `u64` digits representation of the [`BigUint`] ordered least significant digit
/// first.
///
/// # Examples
@@ -737,7 +740,7 @@
self.iter_u64_digits().collect()
}
- /// Returns an iterator of `u32` digits representation of the `BigUint` ordered least
+ /// Returns an iterator of `u32` digits representation of the [`BigUint`] ordered least
/// significant digit first.
///
/// # Examples
@@ -755,7 +758,7 @@
U32Digits::new(self.data.as_slice())
}
- /// Returns an iterator of `u64` digits representation of the `BigUint` ordered least
+ /// Returns an iterator of `u64` digits representation of the [`BigUint`] ordered least
/// significant digit first.
///
/// # Examples
@@ -794,7 +797,7 @@
/// Returns the integer in the requested base in big-endian digit order.
/// The output is not given in a human readable alphabet but as a zero
- /// based u8 number.
+ /// based `u8` number.
/// `radix` must be in the range `2...256`.
///
/// # Examples
@@ -832,7 +835,7 @@
convert::to_radix_le(self, radix)
}
- /// Determines the fewest bits necessary to express the `BigUint`.
+ /// Determines the fewest bits necessary to express the [`BigUint`].
#[inline]
pub fn bits(&self) -> u64 {
if self.is_zero() {
@@ -855,7 +858,7 @@
}
}
- /// Returns a normalized `BigUint`.
+ /// Returns a normalized [`BigUint`].
#[inline]
fn normalized(mut self) -> BigUint {
self.normalize();
@@ -956,6 +959,30 @@
}
}
+impl num_traits::FromBytes for BigUint {
+ type Bytes = [u8];
+
+ fn from_be_bytes(bytes: &Self::Bytes) -> Self {
+ Self::from_bytes_be(bytes)
+ }
+
+ fn from_le_bytes(bytes: &Self::Bytes) -> Self {
+ Self::from_bytes_le(bytes)
+ }
+}
+
+impl num_traits::ToBytes for BigUint {
+ type Bytes = Vec<u8>;
+
+ fn to_be_bytes(&self) -> Self::Bytes {
+ self.to_bytes_be()
+ }
+
+ fn to_le_bytes(&self) -> Self::Bytes {
+ self.to_bytes_le()
+ }
+}
+
pub(crate) trait IntDigits {
fn digits(&self) -> &[BigDigit];
fn digits_mut(&mut self) -> &mut Vec<BigDigit>;
@@ -987,7 +1014,7 @@
}
}
-/// Convert a u32 chunk (len is either 1 or 2) to a single u64 digit
+/// Convert a `u32` chunk (len is either 1 or 2) to a single `u64` digit
#[inline]
fn u32_chunk_to_u64(chunk: &[u32]) -> u64 {
// raw could have odd length
diff --git a/src/biguint/addition.rs b/src/biguint/addition.rs
index e54f8cb..ac6c0dd 100644
--- a/src/biguint/addition.rs
+++ b/src/biguint/addition.rs
@@ -86,7 +86,7 @@
forward_all_binop_to_val_ref_commutative!(impl Add for BigUint, add);
forward_val_assign!(impl AddAssign for BigUint, add_assign);
-impl<'a> Add<&'a BigUint> for BigUint {
+impl Add<&BigUint> for BigUint {
type Output = BigUint;
fn add(mut self, other: &BigUint) -> BigUint {
@@ -94,7 +94,7 @@
self
}
}
-impl<'a> AddAssign<&'a BigUint> for BigUint {
+impl AddAssign<&BigUint> for BigUint {
#[inline]
fn add_assign(&mut self, other: &BigUint) {
let self_len = self.data.len();
diff --git a/src/biguint/bits.rs b/src/biguint/bits.rs
index 58c755a..42d7ec0 100644
--- a/src/biguint/bits.rs
+++ b/src/biguint/bits.rs
@@ -7,7 +7,7 @@
// do not use forward_ref_ref_binop_commutative! for bitand so that we can
// clone the smaller value rather than the larger, avoiding over-allocation
-impl<'a, 'b> BitAnd<&'b BigUint> for &'a BigUint {
+impl BitAnd<&BigUint> for &BigUint {
type Output = BigUint;
#[inline]
@@ -23,7 +23,7 @@
forward_val_assign!(impl BitAndAssign for BigUint, bitand_assign);
-impl<'a> BitAnd<&'a BigUint> for BigUint {
+impl BitAnd<&BigUint> for BigUint {
type Output = BigUint;
#[inline]
@@ -32,7 +32,7 @@
self
}
}
-impl<'a> BitAndAssign<&'a BigUint> for BigUint {
+impl BitAndAssign<&BigUint> for BigUint {
#[inline]
fn bitand_assign(&mut self, other: &BigUint) {
for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
@@ -46,7 +46,7 @@
forward_all_binop_to_val_ref_commutative!(impl BitOr for BigUint, bitor);
forward_val_assign!(impl BitOrAssign for BigUint, bitor_assign);
-impl<'a> BitOr<&'a BigUint> for BigUint {
+impl BitOr<&BigUint> for BigUint {
type Output = BigUint;
fn bitor(mut self, other: &BigUint) -> BigUint {
@@ -54,7 +54,7 @@
self
}
}
-impl<'a> BitOrAssign<&'a BigUint> for BigUint {
+impl BitOrAssign<&BigUint> for BigUint {
#[inline]
fn bitor_assign(&mut self, other: &BigUint) {
for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
@@ -70,7 +70,7 @@
forward_all_binop_to_val_ref_commutative!(impl BitXor for BigUint, bitxor);
forward_val_assign!(impl BitXorAssign for BigUint, bitxor_assign);
-impl<'a> BitXor<&'a BigUint> for BigUint {
+impl BitXor<&BigUint> for BigUint {
type Output = BigUint;
fn bitxor(mut self, other: &BigUint) -> BigUint {
@@ -78,7 +78,7 @@
self
}
}
-impl<'a> BitXorAssign<&'a BigUint> for BigUint {
+impl BitXorAssign<&BigUint> for BigUint {
#[inline]
fn bitxor_assign(&mut self, other: &BigUint) {
for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
diff --git a/src/biguint/convert.rs b/src/biguint/convert.rs
index 5cf05cb..f19bc75 100644
--- a/src/biguint/convert.rs
+++ b/src/biguint/convert.rs
@@ -1,3 +1,6 @@
+// This uses stdlib features higher than the MSRV
+#![allow(clippy::manual_range_contains)] // 1.35
+
use super::{biguint_from_vec, BigUint, ToBigUint};
use super::addition::add2;
@@ -17,7 +20,7 @@
use core::str::FromStr;
use num_integer::{Integer, Roots};
use num_traits::float::FloatCore;
-use num_traits::{FromPrimitive, Num, PrimInt, ToPrimitive, Zero};
+use num_traits::{FromPrimitive, Num, One, PrimInt, ToPrimitive, Zero};
/// Find last set bit
/// fls(0) == 0, fls(u32::MAX) == 32
@@ -102,14 +105,20 @@
debug_assert!(!v.is_empty() && !radix.is_power_of_two());
debug_assert!(v.iter().all(|&c| u32::from(c) < radix));
- #[cfg(feature = "std")]
- let radix_log2 = f64::from(radix).log2();
- #[cfg(not(feature = "std"))]
- let radix_log2 = ilog2(radix.next_power_of_two()) as f64;
-
// Estimate how big the result will be, so we can pre-allocate it.
- let bits = radix_log2 * v.len() as f64;
- let big_digits = (bits / big_digit::BITS as f64).ceil();
+ #[cfg(feature = "std")]
+ let big_digits = {
+ let radix_log2 = f64::from(radix).log2();
+ let bits = radix_log2 * v.len() as f64;
+ (bits / big_digit::BITS as f64).ceil()
+ };
+ #[cfg(not(feature = "std"))]
+ let big_digits = {
+ let radix_log2 = ilog2(radix.next_power_of_two()) as usize;
+ let bits = radix_log2 * v.len();
+ (bits / big_digit::BITS as usize) + 1
+ };
+
let mut data = Vec::with_capacity(big_digits.to_usize().unwrap_or(0));
let (base, power) = get_radix_base(radix, big_digit::BITS);
@@ -281,19 +290,31 @@
let digit_bits = (bits - 1) % u64::from(big_digit::BITS) + 1;
let bits_want = Ord::min(64 - ret_bits, digit_bits);
- if bits_want != 64 {
- ret <<= bits_want;
+ if bits_want != 0 {
+ if bits_want != 64 {
+ ret <<= bits_want;
+ }
+ // XXX Conversion is useless if already 64-bit.
+ #[allow(clippy::useless_conversion)]
+ let d0 = u64::from(*d) >> (digit_bits - bits_want);
+ ret |= d0;
}
- // XXX Conversion is useless if already 64-bit.
- #[allow(clippy::useless_conversion)]
- let d0 = u64::from(*d) >> (digit_bits - bits_want);
- ret |= d0;
+
+ // Implement round-to-odd: If any lower bits are 1, set LSB to 1
+ // so that rounding again to floating point value using
+ // nearest-ties-to-even is correct.
+ //
+ // See: https://en.wikipedia.org/wiki/Rounding#Rounding_to_prepare_for_shorter_precision
+
+ if digit_bits - bits_want != 0 {
+ // XXX Conversion is useless if already 64-bit.
+ #[allow(clippy::useless_conversion)]
+ let masked = u64::from(*d) << (64 - (digit_bits - bits_want) as u32);
+ ret |= (masked != 0) as u64;
+ }
+
ret_bits += bits_want;
bits -= bits_want;
-
- if ret_bits == 64 {
- break;
- }
}
ret
@@ -572,6 +593,16 @@
impl_to_biguint!(f32, FromPrimitive::from_f32);
impl_to_biguint!(f64, FromPrimitive::from_f64);
+impl From<bool> for BigUint {
+ fn from(x: bool) -> Self {
+ if x {
+ One::one()
+ } else {
+ Zero::zero()
+ }
+ }
+}
+
// Extract bitwise digits that evenly divide BigDigit
pub(super) fn to_bitwise_digits_le(u: &BigUint, bits: u8) -> Vec<u8> {
debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits == 0);
@@ -647,12 +678,17 @@
debug_assert!(!u.is_zero() && !radix.is_power_of_two());
#[cfg(feature = "std")]
- let radix_log2 = f64::from(radix).log2();
+ let radix_digits = {
+ let radix_log2 = f64::from(radix).log2();
+ ((u.bits() as f64) / radix_log2).ceil()
+ };
#[cfg(not(feature = "std"))]
- let radix_log2 = ilog2(radix) as f64;
+ let radix_digits = {
+ let radix_log2 = ilog2(radix) as usize;
+ ((u.bits() as usize) / radix_log2) + 1
+ };
// Estimate how big the result will be, so we can pre-allocate it.
- let radix_digits = ((u.bits() as f64) / radix_log2).ceil();
let mut res = Vec::with_capacity(radix_digits.to_usize().unwrap_or(0));
let mut digits = u.clone();
diff --git a/src/biguint/division.rs b/src/biguint/division.rs
index b5d4259..2999838 100644
--- a/src/biguint/division.rs
+++ b/src/biguint/division.rs
@@ -10,7 +10,7 @@
use core::mem;
use core::ops::{Div, DivAssign, Rem, RemAssign};
use num_integer::Integer;
-use num_traits::{CheckedDiv, One, ToPrimitive, Zero};
+use num_traits::{CheckedDiv, CheckedEuclid, Euclid, One, ToPrimitive, Zero};
/// Divide a two digit numerator by a one digit divisor, returns quotient and remainder:
///
@@ -314,7 +314,7 @@
}
}
-impl<'a, 'b> Div<&'b BigUint> for &'a BigUint {
+impl Div<&BigUint> for &BigUint {
type Output = BigUint;
#[inline]
@@ -323,9 +323,9 @@
q
}
}
-impl<'a> DivAssign<&'a BigUint> for BigUint {
+impl DivAssign<&BigUint> for BigUint {
#[inline]
- fn div_assign(&mut self, other: &'a BigUint) {
+ fn div_assign(&mut self, other: &BigUint) {
*self = &*self / other;
}
}
@@ -475,7 +475,7 @@
}
}
-impl<'a, 'b> Rem<&'b BigUint> for &'a BigUint {
+impl Rem<&BigUint> for &BigUint {
type Output = BigUint;
#[inline]
@@ -488,7 +488,7 @@
}
}
}
-impl<'a> RemAssign<&'a BigUint> for BigUint {
+impl RemAssign<&BigUint> for BigUint {
#[inline]
fn rem_assign(&mut self, other: &BigUint) {
*self = &*self % other;
@@ -501,7 +501,7 @@
forward_all_scalar_binop_to_val_val!(impl Rem<u64> for BigUint, rem);
forward_all_scalar_binop_to_val_val!(impl Rem<u128> for BigUint, rem);
-impl<'a> Rem<u32> for &'a BigUint {
+impl Rem<u32> for &BigUint {
type Output = BigUint;
#[inline]
@@ -516,11 +516,11 @@
}
}
-impl<'a> Rem<&'a BigUint> for u32 {
+impl Rem<&BigUint> for u32 {
type Output = BigUint;
#[inline]
- fn rem(mut self, other: &'a BigUint) -> BigUint {
+ fn rem(mut self, other: &BigUint) -> BigUint {
self %= other;
From::from(self)
}
@@ -529,7 +529,7 @@
macro_rules! impl_rem_assign_scalar {
($scalar:ty, $to_scalar:ident) => {
forward_val_assign_scalar!(impl RemAssign for BigUint, $scalar, rem_assign);
- impl<'a> RemAssign<&'a BigUint> for $scalar {
+ impl RemAssign<&BigUint> for $scalar {
#[inline]
fn rem_assign(&mut self, other: &BigUint) {
*self = match other.$to_scalar() {
@@ -618,3 +618,35 @@
Some(self.div(v))
}
}
+
+impl CheckedEuclid for BigUint {
+ #[inline]
+ fn checked_div_euclid(&self, v: &BigUint) -> Option<BigUint> {
+ if v.is_zero() {
+ return None;
+ }
+ Some(self.div_euclid(v))
+ }
+
+ #[inline]
+ fn checked_rem_euclid(&self, v: &BigUint) -> Option<BigUint> {
+ if v.is_zero() {
+ return None;
+ }
+ Some(self.rem_euclid(v))
+ }
+}
+
+impl Euclid for BigUint {
+ #[inline]
+ fn div_euclid(&self, v: &BigUint) -> BigUint {
+ // trivially same as regular division
+ self / v
+ }
+
+ #[inline]
+ fn rem_euclid(&self, v: &BigUint) -> BigUint {
+ // trivially same as regular remainder
+ self % v
+ }
+}
diff --git a/src/biguint/monty.rs b/src/biguint/monty.rs
index a5c79aa..abaca50 100644
--- a/src/biguint/monty.rs
+++ b/src/biguint/monty.rs
@@ -37,7 +37,7 @@
/// Computes z mod m = x * y * 2 ** (-n*_W) mod m
/// assuming k = -1/m mod 2**_W
/// See Gueron, "Efficient Software Implementations of Modular Exponentiation".
-/// https://eprint.iacr.org/2011/239.pdf
+/// <https://eprint.iacr.org/2011/239.pdf>
/// In the terminology of that paper, this is an "Almost Montgomery Multiplication":
/// x and y are required to satisfy 0 <= z < 2**(n*_W) and then the result
/// z is guaranteed to satisfy 0 <= z < 2**(n*_W), but it may not be < m.
@@ -78,8 +78,8 @@
z.data = z.data[n..].to_vec();
} else {
{
- let (mut first, second) = z.data.split_at_mut(n);
- sub_vv(&mut first, &second, &m.data);
+ let (first, second) = z.data.split_at_mut(n);
+ sub_vv(first, second, &m.data);
}
z.data = z.data[..n].to_vec();
}
diff --git a/src/biguint/multiplication.rs b/src/biguint/multiplication.rs
index 597a202..4d7f1f2 100644
--- a/src/biguint/multiplication.rs
+++ b/src/biguint/multiplication.rs
@@ -402,8 +402,8 @@
}
macro_rules! impl_mul {
- ($(impl<$($a:lifetime),*> Mul<$Other:ty> for $Self:ty;)*) => {$(
- impl<$($a),*> Mul<$Other> for $Self {
+ ($(impl Mul<$Other:ty> for $Self:ty;)*) => {$(
+ impl Mul<$Other> for $Self {
type Output = BigUint;
#[inline]
@@ -422,15 +422,15 @@
)*}
}
impl_mul! {
- impl<> Mul<BigUint> for BigUint;
- impl<'b> Mul<&'b BigUint> for BigUint;
- impl<'a> Mul<BigUint> for &'a BigUint;
- impl<'a, 'b> Mul<&'b BigUint> for &'a BigUint;
+ impl Mul<BigUint> for BigUint;
+ impl Mul<BigUint> for &BigUint;
+ impl Mul<&BigUint> for BigUint;
+ impl Mul<&BigUint> for &BigUint;
}
macro_rules! impl_mul_assign {
- ($(impl<$($a:lifetime),*> MulAssign<$Other:ty> for BigUint;)*) => {$(
- impl<$($a),*> MulAssign<$Other> for BigUint {
+ ($(impl MulAssign<$Other:ty> for BigUint;)*) => {$(
+ impl MulAssign<$Other> for BigUint {
#[inline]
fn mul_assign(&mut self, other: $Other) {
match (&*self.data, &*other.data) {
@@ -448,8 +448,8 @@
)*}
}
impl_mul_assign! {
- impl<> MulAssign<BigUint> for BigUint;
- impl<'a> MulAssign<&'a BigUint> for BigUint;
+ impl MulAssign<BigUint> for BigUint;
+ impl MulAssign<&BigUint> for BigUint;
}
promote_unsigned_scalars!(impl Mul for BigUint, mul);
diff --git a/src/biguint/power.rs b/src/biguint/power.rs
index d24651b..621e1b1 100644
--- a/src/biguint/power.rs
+++ b/src/biguint/power.rs
@@ -6,7 +6,7 @@
use num_integer::Integer;
use num_traits::{One, Pow, ToPrimitive, Zero};
-impl<'b> Pow<&'b BigUint> for BigUint {
+impl Pow<&BigUint> for BigUint {
type Output = BigUint;
#[inline]
@@ -36,7 +36,7 @@
}
}
-impl<'a, 'b> Pow<&'b BigUint> for &'a BigUint {
+impl Pow<&BigUint> for &BigUint {
type Output = BigUint;
#[inline]
@@ -51,7 +51,7 @@
}
}
-impl<'a> Pow<BigUint> for &'a BigUint {
+impl Pow<BigUint> for &BigUint {
type Output = BigUint;
#[inline]
@@ -92,7 +92,7 @@
}
}
- impl<'b> Pow<&'b $T> for BigUint {
+ impl Pow<&$T> for BigUint {
type Output = BigUint;
#[inline]
@@ -101,7 +101,7 @@
}
}
- impl<'a> Pow<$T> for &'a BigUint {
+ impl Pow<$T> for &BigUint {
type Output = BigUint;
#[inline]
@@ -113,7 +113,7 @@
}
}
- impl<'a, 'b> Pow<&'b $T> for &'a BigUint {
+ impl Pow<&$T> for &BigUint {
type Output = BigUint;
#[inline]
@@ -225,27 +225,27 @@
let exp = vec![0, 0b1];
assert_eq!(
two.pow(0b1_00000000_u32) % &modulus,
- plain_modpow(&two, &exp, &modulus)
+ plain_modpow(two, &exp, &modulus)
);
let exp = vec![0, 0b10];
assert_eq!(
two.pow(0b10_00000000_u32) % &modulus,
- plain_modpow(&two, &exp, &modulus)
+ plain_modpow(two, &exp, &modulus)
);
let exp = vec![0, 0b110010];
assert_eq!(
two.pow(0b110010_00000000_u32) % &modulus,
- plain_modpow(&two, &exp, &modulus)
+ plain_modpow(two, &exp, &modulus)
);
let exp = vec![0b1, 0b1];
assert_eq!(
two.pow(0b1_00000001_u32) % &modulus,
- plain_modpow(&two, &exp, &modulus)
+ plain_modpow(two, &exp, &modulus)
);
let exp = vec![0b1100, 0, 0b1];
assert_eq!(
two.pow(0b1_00000000_00001100_u32) % &modulus,
- plain_modpow(&two, &exp, &modulus)
+ plain_modpow(two, &exp, &modulus)
);
}
diff --git a/src/biguint/serde.rs b/src/biguint/serde.rs
index ed663c6..3240f09 100644
--- a/src/biguint/serde.rs
+++ b/src/biguint/serde.rs
@@ -2,10 +2,21 @@
use crate::std_alloc::Vec;
-use core::fmt;
+use core::{cmp, fmt, mem};
use serde::de::{SeqAccess, Visitor};
use serde::{Deserialize, Deserializer, Serialize, Serializer};
+// `cautious` is based on the function of the same name in `serde`, but specialized to `u32`:
+// https://github.com/dtolnay/serde/blob/399ef081ecc36d2f165ff1f6debdcbf6a1dc7efb/serde/src/private/size_hint.rs#L11-L22
+fn cautious(hint: Option<usize>) -> usize {
+ const MAX_PREALLOC_BYTES: usize = 1024 * 1024;
+
+ cmp::min(
+ hint.unwrap_or(0),
+ MAX_PREALLOC_BYTES / mem::size_of::<u32>(),
+ )
+}
+
impl Serialize for BigUint {
#[cfg(not(u64_digit))]
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
@@ -70,7 +81,7 @@
where
S: SeqAccess<'de>,
{
- let len = seq.size_hint().unwrap_or(0);
+ let len = cautious(seq.size_hint());
let mut data = Vec::with_capacity(len);
while let Some(value) = seq.next_element::<u32>()? {
@@ -88,7 +99,7 @@
use crate::big_digit::BigDigit;
use num_integer::Integer;
- let u32_len = seq.size_hint().unwrap_or(0);
+ let u32_len = cautious(seq.size_hint());
let len = Integer::div_ceil(&u32_len, &2);
let mut data = Vec::with_capacity(len);
diff --git a/src/biguint/shift.rs b/src/biguint/shift.rs
index 05964d2..00326bb 100644
--- a/src/biguint/shift.rs
+++ b/src/biguint/shift.rs
@@ -35,7 +35,7 @@
if shift > 0 {
let mut carry = 0;
- let carry_shift = big_digit::BITS as u8 - shift;
+ let carry_shift = big_digit::BITS - shift;
for elem in data[digits..].iter_mut() {
let new_carry = *elem >> carry_shift;
*elem = (*elem << shift) | carry;
@@ -79,7 +79,7 @@
if shift > 0 {
let mut borrow = 0;
- let borrow_shift = big_digit::BITS as u8 - shift;
+ let borrow_shift = big_digit::BITS - shift;
for elem in data.iter_mut().rev() {
let new_borrow = *elem << borrow_shift;
*elem = (*elem >> shift) | borrow;
@@ -92,25 +92,25 @@
macro_rules! impl_shift {
(@ref $Shx:ident :: $shx:ident, $ShxAssign:ident :: $shx_assign:ident, $rhs:ty) => {
- impl<'b> $Shx<&'b $rhs> for BigUint {
+ impl $Shx<&$rhs> for BigUint {
type Output = BigUint;
#[inline]
- fn $shx(self, rhs: &'b $rhs) -> BigUint {
+ fn $shx(self, rhs: &$rhs) -> BigUint {
$Shx::$shx(self, *rhs)
}
}
- impl<'a, 'b> $Shx<&'b $rhs> for &'a BigUint {
+ impl $Shx<&$rhs> for &BigUint {
type Output = BigUint;
#[inline]
- fn $shx(self, rhs: &'b $rhs) -> BigUint {
+ fn $shx(self, rhs: &$rhs) -> BigUint {
$Shx::$shx(self, *rhs)
}
}
- impl<'b> $ShxAssign<&'b $rhs> for BigUint {
+ impl $ShxAssign<&$rhs> for BigUint {
#[inline]
- fn $shx_assign(&mut self, rhs: &'b $rhs) {
+ fn $shx_assign(&mut self, rhs: &$rhs) {
$ShxAssign::$shx_assign(self, *rhs);
}
}
@@ -124,7 +124,7 @@
biguint_shl(Cow::Owned(self), rhs)
}
}
- impl<'a> Shl<$rhs> for &'a BigUint {
+ impl Shl<$rhs> for &BigUint {
type Output = BigUint;
#[inline]
@@ -149,7 +149,7 @@
biguint_shr(Cow::Owned(self), rhs)
}
}
- impl<'a> Shr<$rhs> for &'a BigUint {
+ impl Shr<$rhs> for &BigUint {
type Output = BigUint;
#[inline]
diff --git a/src/biguint/subtraction.rs b/src/biguint/subtraction.rs
index 6700517..b7cf59d 100644
--- a/src/biguint/subtraction.rs
+++ b/src/biguint/subtraction.rs
@@ -108,7 +108,7 @@
forward_ref_ref_binop!(impl Sub for BigUint, sub);
forward_val_assign!(impl SubAssign for BigUint, sub_assign);
-impl<'a> Sub<&'a BigUint> for BigUint {
+impl Sub<&BigUint> for BigUint {
type Output = BigUint;
fn sub(mut self, other: &BigUint) -> BigUint {
@@ -116,14 +116,14 @@
self
}
}
-impl<'a> SubAssign<&'a BigUint> for BigUint {
- fn sub_assign(&mut self, other: &'a BigUint) {
+impl SubAssign<&BigUint> for BigUint {
+ fn sub_assign(&mut self, other: &BigUint) {
sub2(&mut self.data[..], &other.data[..]);
self.normalize();
}
}
-impl<'a> Sub<BigUint> for &'a BigUint {
+impl Sub<BigUint> for &BigUint {
type Output = BigUint;
fn sub(self, mut other: BigUint) -> BigUint {
diff --git a/src/lib.rs b/src/lib.rs
index b88c5df..893b747 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -8,10 +8,10 @@
// option. This file may not be copied, modified, or distributed
// except according to those terms.
-//! A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
+//! Big Integer Types for Rust
//!
-//! A `BigUint` is represented as a vector of `BigDigit`s.
-//! A `BigInt` is a combination of `BigUint` and `Sign`.
+//! * A [`BigUint`] is unsigned and represented as a vector of digits.
+//! * A [`BigInt`] is signed and is a combination of [`BigUint`] and [`Sign`].
//!
//! Common numerical operations are overloaded, so we can treat them
//! the same way we treat other numbers.
@@ -22,7 +22,6 @@
//! # fn main() {
//! use num_bigint::BigUint;
//! use num_traits::{Zero, One};
-//! use std::mem::replace;
//!
//! // Calculate large fibonacci numbers.
//! fn fib(n: usize) -> BigUint {
@@ -30,8 +29,8 @@
//! let mut f1: BigUint = One::one();
//! for _ in 0..n {
//! let f2 = f0 + &f1;
-//! // This is a low cost way of swapping f0 with f1 and f1 with f2.
-//! f0 = replace(&mut f1, f2);
+//! f0 = f1;
+//! f1 = f2;
//! }
//! f0
//! }
@@ -95,7 +94,7 @@
#[cfg(feature = "std")]
mod std_alloc {
pub(crate) use std::borrow::Cow;
- #[cfg(any(feature = "quickcheck"))]
+ #[cfg(feature = "quickcheck")]
pub(crate) use std::boxed::Box;
pub(crate) use std::string::String;
pub(crate) use std::vec::Vec;
@@ -108,7 +107,7 @@
#[cfg(not(feature = "std"))]
mod std_alloc {
pub(crate) use alloc::borrow::Cow;
- #[cfg(any(feature = "quickcheck"))]
+ #[cfg(feature = "quickcheck")]
pub(crate) use alloc::boxed::Box;
pub(crate) use alloc::string::String;
pub(crate) use alloc::vec::Vec;
@@ -202,9 +201,6 @@
/// Extract the original value, if available. The value will be available
/// if the type before conversion was either [`BigInt`] or [`BigUint`].
- ///
- /// [`BigInt`]: struct.BigInt.html
- /// [`BigUint`]: struct.BigUint.html
pub fn into_original(self) -> T {
self.original
}
@@ -240,26 +236,26 @@
pub use crate::bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint};
mod big_digit {
- /// A `BigDigit` is a `BigUint`'s composing element.
+ /// A [`BigDigit`] is a [`BigUint`]'s composing element.
#[cfg(not(u64_digit))]
pub(crate) type BigDigit = u32;
#[cfg(u64_digit)]
pub(crate) type BigDigit = u64;
- /// A `DoubleBigDigit` is the internal type used to do the computations. Its
- /// size is the double of the size of `BigDigit`.
+ /// A [`DoubleBigDigit`] is the internal type used to do the computations. Its
+ /// size is the double of the size of [`BigDigit`].
#[cfg(not(u64_digit))]
pub(crate) type DoubleBigDigit = u64;
#[cfg(u64_digit)]
pub(crate) type DoubleBigDigit = u128;
- /// A `SignedDoubleBigDigit` is the signed version of `DoubleBigDigit`.
+ /// A [`SignedDoubleBigDigit`] is the signed version of [`DoubleBigDigit`].
#[cfg(not(u64_digit))]
pub(crate) type SignedDoubleBigDigit = i64;
#[cfg(u64_digit)]
pub(crate) type SignedDoubleBigDigit = i128;
- // `DoubleBigDigit` size dependent
+ // [`DoubleBigDigit`] size dependent
#[cfg(not(u64_digit))]
pub(crate) const BITS: u8 = 32;
#[cfg(u64_digit)]
@@ -280,13 +276,13 @@
(n & LO_MASK) as BigDigit
}
- /// Split one `DoubleBigDigit` into two `BigDigit`s.
+ /// Split one [`DoubleBigDigit`] into two [`BigDigit`]s.
#[inline]
pub(crate) fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
(get_hi(n), get_lo(n))
}
- /// Join two `BigDigit`s into one `DoubleBigDigit`
+ /// Join two [`BigDigit`]s into one [`DoubleBigDigit`].
#[inline]
pub(crate) fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
DoubleBigDigit::from(lo) | (DoubleBigDigit::from(hi) << BITS)
diff --git a/src/macros.rs b/src/macros.rs
index a03cb67..1618616 100644
--- a/src/macros.rs
+++ b/src/macros.rs
@@ -34,7 +34,7 @@
macro_rules! forward_ref_val_binop {
(impl $imp:ident for $res:ty, $method:ident) => {
- impl<'a> $imp<$res> for &'a $res {
+ impl $imp<$res> for &$res {
type Output = $res;
#[inline]
@@ -48,7 +48,7 @@
macro_rules! forward_ref_val_binop_commutative {
(impl $imp:ident for $res:ty, $method:ident) => {
- impl<'a> $imp<$res> for &'a $res {
+ impl $imp<$res> for &$res {
type Output = $res;
#[inline]
@@ -62,7 +62,7 @@
macro_rules! forward_val_ref_binop {
(impl $imp:ident for $res:ty, $method:ident) => {
- impl<'a> $imp<&'a $res> for $res {
+ impl $imp<&$res> for $res {
type Output = $res;
#[inline]
@@ -76,7 +76,7 @@
macro_rules! forward_ref_ref_binop {
(impl $imp:ident for $res:ty, $method:ident) => {
- impl<'a, 'b> $imp<&'b $res> for &'a $res {
+ impl $imp<&$res> for &$res {
type Output = $res;
#[inline]
@@ -90,7 +90,7 @@
macro_rules! forward_ref_ref_binop_commutative {
(impl $imp:ident for $res:ty, $method:ident) => {
- impl<'a, 'b> $imp<&'b $res> for &'a $res {
+ impl $imp<&$res> for &$res {
type Output = $res;
#[inline]
@@ -167,7 +167,7 @@
macro_rules! forward_scalar_ref_ref_binop_to_ref_val {
(impl $imp:ident<$scalar:ty> for $res:ty, $method:ident) => {
- impl<'a, 'b> $imp<&'b $scalar> for &'a $res {
+ impl $imp<&$scalar> for &$res {
type Output = $res;
#[inline]
@@ -176,7 +176,7 @@
}
}
- impl<'a, 'b> $imp<&'a $res> for &'b $scalar {
+ impl $imp<&$res> for &$scalar {
type Output = $res;
#[inline]
@@ -189,7 +189,7 @@
macro_rules! forward_scalar_val_ref_binop_to_ref_val {
(impl $imp:ident<$scalar:ty> for $res:ty, $method:ident) => {
- impl<'a> $imp<&'a $scalar> for $res {
+ impl $imp<&$scalar> for $res {
type Output = $res;
#[inline]
@@ -198,7 +198,7 @@
}
}
- impl<'a> $imp<$res> for &'a $scalar {
+ impl $imp<$res> for &$scalar {
type Output = $res;
#[inline]
@@ -211,7 +211,7 @@
macro_rules! forward_scalar_val_ref_binop_to_val_val {
(impl $imp:ident<$scalar:ty> for $res:ty, $method:ident) => {
- impl<'a> $imp<&'a $scalar> for $res {
+ impl $imp<&$scalar> for $res {
type Output = $res;
#[inline]
@@ -220,7 +220,7 @@
}
}
- impl<'a> $imp<$res> for &'a $scalar {
+ impl $imp<$res> for &$scalar {
type Output = $res;
#[inline]
@@ -233,7 +233,7 @@
macro_rules! forward_scalar_ref_val_binop_to_val_val {
(impl $imp:ident < $scalar:ty > for $res:ty, $method:ident) => {
- impl<'a> $imp<$scalar> for &'a $res {
+ impl $imp<$scalar> for &$res {
type Output = $res;
#[inline]
@@ -242,7 +242,7 @@
}
}
- impl<'a> $imp<&'a $res> for $scalar {
+ impl $imp<&$res> for $scalar {
type Output = $res;
#[inline]
@@ -255,7 +255,7 @@
macro_rules! forward_scalar_ref_ref_binop_to_val_val {
(impl $imp:ident<$scalar:ty> for $res:ty, $method:ident) => {
- impl<'a, 'b> $imp<&'b $scalar> for &'a $res {
+ impl $imp<&$scalar> for &$res {
type Output = $res;
#[inline]
@@ -264,7 +264,7 @@
}
}
- impl<'a, 'b> $imp<&'a $res> for &'b $scalar {
+ impl $imp<&$res> for &$scalar {
type Output = $res;
#[inline]
diff --git a/tests/bigint.rs b/tests/bigint.rs
index f244bc4..75cf81e 100644
--- a/tests/bigint.rs
+++ b/tests/bigint.rs
@@ -13,7 +13,9 @@
use std::{u16, u32, u64, u8, usize};
use num_integer::Integer;
-use num_traits::{pow, FromPrimitive, Num, One, Pow, Signed, ToPrimitive, Zero};
+use num_traits::{
+ pow, Euclid, FromBytes, FromPrimitive, Num, One, Pow, Signed, ToBytes, ToPrimitive, Zero,
+};
mod consts;
use crate::consts::*;
@@ -94,12 +96,9 @@
#[test]
fn test_to_signed_bytes_le() {
fn check(s: &str, result: Vec<u8>) {
- assert_eq!(
- BigInt::parse_bytes(s.as_bytes(), 10)
- .unwrap()
- .to_signed_bytes_le(),
- result
- );
+ let b = BigInt::parse_bytes(s.as_bytes(), 10).unwrap();
+ assert_eq!(b.to_signed_bytes_le(), result);
+ assert_eq!(<BigInt as ToBytes>::to_le_bytes(&b), result);
}
check("0", vec![0]);
@@ -115,10 +114,9 @@
#[test]
fn test_from_signed_bytes_le() {
fn check(s: &[u8], result: &str) {
- assert_eq!(
- BigInt::from_signed_bytes_le(s),
- BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
- );
+ let b = BigInt::parse_bytes(result.as_bytes(), 10).unwrap();
+ assert_eq!(BigInt::from_signed_bytes_le(s), b);
+ assert_eq!(<BigInt as FromBytes>::from_le_bytes(s), b);
}
check(&[], "0");
@@ -136,12 +134,9 @@
#[test]
fn test_to_signed_bytes_be() {
fn check(s: &str, result: Vec<u8>) {
- assert_eq!(
- BigInt::parse_bytes(s.as_bytes(), 10)
- .unwrap()
- .to_signed_bytes_be(),
- result
- );
+ let b = BigInt::parse_bytes(s.as_bytes(), 10).unwrap();
+ assert_eq!(b.to_signed_bytes_be(), result);
+ assert_eq!(<BigInt as ToBytes>::to_be_bytes(&b), result);
}
check("0", vec![0]);
@@ -157,10 +152,9 @@
#[test]
fn test_from_signed_bytes_be() {
fn check(s: &[u8], result: &str) {
- assert_eq!(
- BigInt::from_signed_bytes_be(s),
- BigInt::parse_bytes(result.as_bytes(), 10).unwrap()
- );
+ let b = BigInt::parse_bytes(result.as_bytes(), 10).unwrap();
+ assert_eq!(BigInt::from_signed_bytes_be(s), b);
+ assert_eq!(<BigInt as FromBytes>::from_be_bytes(s), b);
}
check(&[], "0");
@@ -193,7 +187,7 @@
#[test]
fn test_cmp() {
- let vs: [&[u32]; 4] = [&[2 as u32], &[1, 1], &[2, 1], &[1, 1, 1]];
+ let vs: [&[u32]; 4] = [&[2_u32], &[1, 1], &[2, 1], &[1, 1, 1]];
let mut nums = Vec::new();
for s in vs.iter().rev() {
nums.push(BigInt::from_slice(Minus, *s));
@@ -421,6 +415,13 @@
b <<= 1;
}
+ // test correct ties-to-even rounding
+ let weird: i128 = (1i128 << 100) + (1i128 << (100 - f32::MANTISSA_DIGITS));
+ assert_ne!(weird as f32, (weird + 1) as f32);
+
+ assert_eq!(BigInt::from(weird).to_f32(), Some(weird as f32));
+ assert_eq!(BigInt::from(weird + 1).to_f32(), Some((weird + 1) as f32));
+
// rounding
assert_eq!(
BigInt::from_f32(-f32::consts::PI),
@@ -511,6 +512,13 @@
b <<= 1;
}
+ // test correct ties-to-even rounding
+ let weird: i128 = (1i128 << 100) + (1i128 << (100 - f64::MANTISSA_DIGITS));
+ assert_ne!(weird as f64, (weird + 1) as f64);
+
+ assert_eq!(BigInt::from(weird).to_f64(), Some(weird as f64));
+ assert_eq!(BigInt::from(weird + 1).to_f64(), Some((weird + 1) as f64));
+
// rounding
assert_eq!(
BigInt::from_f64(-f64::consts::PI),
@@ -903,6 +911,58 @@
}
#[test]
+fn test_div_rem_euclid() {
+ fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
+ eprintln!("{} {} {} {}", a, b, ans_d, ans_m);
+ assert_eq!(a.div_euclid(b), *ans_d);
+ assert_eq!(a.rem_euclid(b), *ans_m);
+ assert!(*ans_m >= BigInt::zero());
+ assert!(*ans_m < b.abs());
+ }
+
+ fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
+ if m.is_zero() {
+ check_sub(a, b, d, m);
+ check_sub(a, &b.neg(), &d.neg(), m);
+ check_sub(&a.neg(), b, &d.neg(), m);
+ check_sub(&a.neg(), &b.neg(), d, m);
+ } else {
+ let one: BigInt = One::one();
+ check_sub(a, b, d, m);
+ check_sub(a, &b.neg(), &d.neg(), m);
+ check_sub(&a.neg(), b, &(d + &one).neg(), &(b - m));
+ check_sub(&a.neg(), &b.neg(), &(d + &one), &(b.abs() - m));
+ }
+ }
+
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+
+ if !a.is_zero() {
+ check(&c, &a, &b, &Zero::zero());
+ }
+ if !b.is_zero() {
+ check(&c, &b, &a, &Zero::zero());
+ }
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigInt::from_slice(Plus, a_vec);
+ let b = BigInt::from_slice(Plus, b_vec);
+ let c = BigInt::from_slice(Plus, c_vec);
+ let d = BigInt::from_slice(Plus, d_vec);
+
+ if !b.is_zero() {
+ check(&a, &b, &c, &d);
+ }
+ }
+}
+
+#[test]
fn test_checked_add() {
for elm in SUM_TRIPLES.iter() {
let (a_vec, b_vec, c_vec) = *elm;
@@ -1037,6 +1097,18 @@
}
#[test]
+fn test_is_multiple_of() {
+ assert!(BigInt::from(0).is_multiple_of(&BigInt::from(0)));
+ assert!(BigInt::from(6).is_multiple_of(&BigInt::from(6)));
+ assert!(BigInt::from(6).is_multiple_of(&BigInt::from(3)));
+ assert!(BigInt::from(6).is_multiple_of(&BigInt::from(1)));
+
+ assert!(!BigInt::from(42).is_multiple_of(&BigInt::from(5)));
+ assert!(!BigInt::from(5).is_multiple_of(&BigInt::from(3)));
+ assert!(!BigInt::from(42).is_multiple_of(&BigInt::from(0)));
+}
+
+#[test]
fn test_next_multiple_of() {
assert_eq!(
BigInt::from(16).next_multiple_of(&BigInt::from(8)),
diff --git a/tests/biguint.rs b/tests/biguint.rs
index 821b754..c027771 100644
--- a/tests/biguint.rs
+++ b/tests/biguint.rs
@@ -14,8 +14,8 @@
use std::{u16, u32, u64, u8, usize};
use num_traits::{
- pow, CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, FromPrimitive, Num, One, Pow, ToPrimitive,
- Zero,
+ pow, CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, Euclid, FromBytes, FromPrimitive, Num,
+ One, Pow, ToBytes, ToPrimitive, Zero,
};
mod consts;
@@ -27,10 +27,9 @@
#[test]
fn test_from_bytes_be() {
fn check(s: &str, result: &str) {
- assert_eq!(
- BigUint::from_bytes_be(s.as_bytes()),
- BigUint::parse_bytes(result.as_bytes(), 10).unwrap()
- );
+ let b = BigUint::parse_bytes(result.as_bytes(), 10).unwrap();
+ assert_eq!(BigUint::from_bytes_be(s.as_bytes()), b);
+ assert_eq!(<BigUint as FromBytes>::from_be_bytes(s.as_bytes()), b);
}
check("A", "65");
check("AA", "16705");
@@ -44,6 +43,7 @@
fn check(s: &str, result: &str) {
let b = BigUint::parse_bytes(result.as_bytes(), 10).unwrap();
assert_eq!(b.to_bytes_be(), s.as_bytes());
+ assert_eq!(<BigUint as ToBytes>::to_be_bytes(&b), s.as_bytes());
}
check("A", "65");
check("AA", "16705");
@@ -60,10 +60,9 @@
#[test]
fn test_from_bytes_le() {
fn check(s: &str, result: &str) {
- assert_eq!(
- BigUint::from_bytes_le(s.as_bytes()),
- BigUint::parse_bytes(result.as_bytes(), 10).unwrap()
- );
+ let b = BigUint::parse_bytes(result.as_bytes(), 10).unwrap();
+ assert_eq!(BigUint::from_bytes_le(s.as_bytes()), b);
+ assert_eq!(<BigUint as FromBytes>::from_le_bytes(s.as_bytes()), b);
}
check("A", "65");
check("AA", "16705");
@@ -77,6 +76,7 @@
fn check(s: &str, result: &str) {
let b = BigUint::parse_bytes(result.as_bytes(), 10).unwrap();
assert_eq!(b.to_bytes_le(), s.as_bytes());
+ assert_eq!(<BigUint as ToBytes>::to_le_bytes(&b), s.as_bytes());
}
check("A", "65");
check("AA", "16705");
@@ -646,6 +646,13 @@
b <<= 1;
}
+ // test correct ties-to-even rounding
+ let weird: i128 = (1i128 << 100) + (1i128 << (100 - f32::MANTISSA_DIGITS));
+ assert_ne!(weird as f32, (weird + 1) as f32);
+
+ assert_eq!(BigInt::from(weird).to_f32(), Some(weird as f32));
+ assert_eq!(BigInt::from(weird + 1).to_f32(), Some((weird + 1) as f32));
+
// rounding
assert_eq!(BigUint::from_f32(-1.0), None);
assert_eq!(BigUint::from_f32(-0.99999), Some(BigUint::zero()));
@@ -722,6 +729,13 @@
b <<= 1;
}
+ // test correct ties-to-even rounding
+ let weird: i128 = (1i128 << 100) + (1i128 << (100 - f64::MANTISSA_DIGITS));
+ assert_ne!(weird as f64, (weird + 1) as f64);
+
+ assert_eq!(BigInt::from(weird).to_f64(), Some(weird as f64));
+ assert_eq!(BigInt::from(weird + 1).to_f64(), Some((weird + 1) as f64));
+
// rounding
assert_eq!(BigUint::from_f64(-1.0), None);
assert_eq!(BigUint::from_f64(-0.99999), Some(BigUint::zero()));
@@ -949,6 +963,40 @@
}
#[test]
+fn test_div_rem_euclid() {
+ fn check(a: &BigUint, b: &BigUint, d: &BigUint, m: &BigUint) {
+ assert_eq!(a.div_euclid(b), *d);
+ assert_eq!(a.rem_euclid(b), *m);
+ }
+
+ for elm in MUL_TRIPLES.iter() {
+ let (a_vec, b_vec, c_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+
+ if !a.is_zero() {
+ check(&c, &a, &b, &Zero::zero());
+ }
+ if !b.is_zero() {
+ check(&c, &b, &a, &Zero::zero());
+ }
+ }
+
+ for elm in DIV_REM_QUADRUPLES.iter() {
+ let (a_vec, b_vec, c_vec, d_vec) = *elm;
+ let a = BigUint::from_slice(a_vec);
+ let b = BigUint::from_slice(b_vec);
+ let c = BigUint::from_slice(c_vec);
+ let d = BigUint::from_slice(d_vec);
+
+ if !b.is_zero() {
+ check(&a, &b, &c, &d);
+ }
+ }
+}
+
+#[test]
fn test_checked_add() {
for elm in SUM_TRIPLES.iter() {
let (a_vec, b_vec, c_vec) = *elm;
@@ -1086,6 +1134,18 @@
}
#[test]
+fn test_is_multiple_of() {
+ assert!(BigUint::from(0u32).is_multiple_of(&BigUint::from(0u32)));
+ assert!(BigUint::from(6u32).is_multiple_of(&BigUint::from(6u32)));
+ assert!(BigUint::from(6u32).is_multiple_of(&BigUint::from(3u32)));
+ assert!(BigUint::from(6u32).is_multiple_of(&BigUint::from(1u32)));
+
+ assert!(!BigUint::from(42u32).is_multiple_of(&BigUint::from(5u32)));
+ assert!(!BigUint::from(5u32).is_multiple_of(&BigUint::from(3u32)));
+ assert!(!BigUint::from(42u32).is_multiple_of(&BigUint::from(0u32)));
+}
+
+#[test]
fn test_next_multiple_of() {
assert_eq!(
BigUint::from(16u32).next_multiple_of(&BigUint::from(8u32)),
diff --git a/tests/modpow.rs b/tests/modpow.rs
index 276f066..d7a247b 100644
--- a/tests/modpow.rs
+++ b/tests/modpow.rs
@@ -120,7 +120,7 @@
let even_m = m << 1u8;
let even_modpow = b.modpow(e, m);
assert!(even_modpow.abs() < even_m.abs());
- assert_eq!(&even_modpow.mod_floor(&m), r);
+ assert_eq!(&even_modpow.mod_floor(m), r);
// the sign of the result follows the modulus like `mod_floor`, not `rem`
assert_eq!(b.modpow(&BigInt::one(), m), b.mod_floor(m));
