diff options
| author | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | 2024-02-02 23:54:03 +0000 |
|---|---|---|
| committer | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | 2024-02-02 23:54:03 +0000 |
| commit | 88dd58570161e321ed7cffec78901cd89f946f93 (patch) | |
| tree | a73eff7996fdb1f9243df90c86974af174606154 | |
| parent | a8231a119fcf29d43efca1a6cae7af0563f69890 (diff) | |
| parent | 80ddf53de8560c1d10267806f7f85ff53c31c77f (diff) | |
| download | num-bigint-simpleperf-release.tar.gz | |
Snap for 11400057 from 80ddf53de8560c1d10267806f7f85ff53c31c77f to simpleperf-releasesimpleperf-release
Change-Id: I66db7bacb7eed19a21bdf3502a9079ecd0b824a9
37 files changed, 692 insertions, 315 deletions
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 @@ -56,7 +56,7 @@ rust_library { 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 @@ rust_test { 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 @@ rust_test { 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 @@ rust_test { 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 @@ rust_test { 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 @@ rust_test { 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 @@ rust_test { 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 @@ rust_test { 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 @@ rust_test { 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 @@ rust_test { 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", @@ -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 @@ name = "roots" [[bench]] name = "shootout-pidigits" harness = false + [dependencies.arbitrary] version = "1" optional = true @@ -53,7 +73,7 @@ features = ["i128"] default-features = false [dependencies.num-traits] -version = "0.2.11" +version = "0.2.16" features = ["i128"] default-features = false @@ -71,9 +91,13 @@ default-features = false 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", +] @@ -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" } } @@ -50,20 +50,23 @@ While `num-bigint` strives for good performance in pure Rust code, other 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] @@ -5,26 +5,32 @@ use std::io::Write; 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 @@ mod arbitrary; #[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 @@ pub enum Sign { 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 Not for BigInt { } } -impl<'a> Not for &'a BigInt { +impl Not for &BigInt { type Output = BigInt; fn not(self) -> BigInt { @@ -292,7 +292,7 @@ trait UnsignedAbs { 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 Neg for BigInt { } } -impl<'a> Neg for &'a BigInt { +impl Neg for &BigInt { type Output = BigInt; #[inline] @@ -558,16 +558,16 @@ impl IntDigits for BigInt { } } -/// 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 @@ impl BigInt { 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 @@ impl BigInt { 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 @@ impl BigInt { 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 @@ impl BigInt { } } - /// Creates and initializes a `BigInt`. + /// Creates and initializes a [`BigInt`]. /// /// The bytes are in big-endian byte order. /// @@ -633,7 +633,7 @@ impl BigInt { 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 @@ impl BigInt { 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 @@ impl BigInt { 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 @@ impl BigInt { convert::from_signed_bytes_le(digits) } - /// Creates and initializes a `BigInt`. + /// Creates and initializes a [`BigInt`]. /// /// # Examples /// @@ -675,7 +675,7 @@ impl BigInt { 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 @@ impl BigInt { 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 @@ impl BigInt { 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 @@ impl BigInt { (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 @@ impl BigInt { (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 @@ impl BigInt { (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 @@ impl BigInt { (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 @@ impl BigInt { 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 @@ impl BigInt { 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 @@ impl BigInt { 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 @@ impl BigInt { /// 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 @@ impl BigInt { /// 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 @@ impl BigInt { (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 @@ impl BigInt { 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 @@ impl BigInt { &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 @@ impl BigInt { (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 @@ impl BigInt { } /// 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 BigInt { } } +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 @@ macro_rules! bigint_add { }; } -impl<'a, 'b> Add<&'b BigInt> for &'a BigInt { +impl Add<&BigInt> for &BigInt { type Output = BigInt; #[inline] @@ -46,7 +46,7 @@ impl<'a, 'b> Add<&'b BigInt> for &'a BigInt { } } -impl<'a> Add<BigInt> for &'a BigInt { +impl Add<BigInt> for &BigInt { type Output = BigInt; #[inline] @@ -55,7 +55,7 @@ impl<'a> Add<BigInt> for &'a BigInt { } } -impl<'a> Add<&'a BigInt> for BigInt { +impl Add<&BigInt> for BigInt { type Output = BigInt; #[inline] @@ -73,7 +73,7 @@ impl Add<BigInt> for BigInt { } } -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 @@ forward_ref_val_binop!(impl BitAnd for BigInt, bitand); // 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, 'b> BitAnd<&'b BigInt> for &'a BigInt { } } -impl<'a> BitAnd<&'a BigInt> for BigInt { +impl BitAnd<&BigInt> for BigInt { type Output = BigInt; #[inline] @@ -142,7 +142,7 @@ impl<'a> BitAnd<&'a BigInt> for BigInt { 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 @@ forward_ref_val_binop!(impl BitOr for BigInt, bitor); // 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, 'b> BitOr<&'b BigInt> for &'a BigInt { } } -impl<'a> BitOr<&'a BigInt> for BigInt { +impl BitOr<&BigInt> for BigInt { type Output = BigInt; #[inline] @@ -282,7 +282,7 @@ impl<'a> BitOr<&'a BigInt> for BigInt { 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 @@ fn bitxor_neg_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) { 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 @@ impl<'a> BitXor<&'a BigInt> for BigInt { 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 @@ use core::cmp::Ordering::{Equal, Greater, Less}; #[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 FromStr for BigInt { 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!(u128, FromPrimitive::from_u128); 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 @@ pub(super) fn from_signed_bytes_be(digits: &[u8]) -> BigInt { // 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 @@ pub(super) fn from_signed_bytes_le(digits: &[u8]) -> BigInt { // 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 crate::{IsizePromotion, UsizePromotion}; 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, 'b> Div<&'b BigInt> for &'a BigInt { } } -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 @@ impl Div<BigInt> for i128 { 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, 'b> Rem<&'b BigInt> for &'a BigInt { } } -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 @@ impl CheckedDiv for BigInt { 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 @@ impl Mul<Sign> for Sign { } 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 @@ macro_rules! impl_mul { )*} } 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 @@ macro_rules! impl_mul_assign { )*} } 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 @@ macro_rules! pow_impl { } } - impl<'b> Pow<&'b $T> for BigInt { + impl Pow<&$T> for BigInt { type Output = BigInt; #[inline] @@ -40,7 +40,7 @@ macro_rules! pow_impl { } } - impl<'a> Pow<$T> for &'a BigInt { + impl Pow<$T> for &BigInt { type Output = BigInt; #[inline] @@ -49,7 +49,7 @@ macro_rules! pow_impl { } } - 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 @@ use num_traits::{PrimInt, Signed, Zero}; 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 @@ macro_rules! impl_shift { 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 @@ macro_rules! impl_shift { 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 @@ macro_rules! bigint_sub { }; } -impl<'a, 'b> Sub<&'b BigInt> for &'a BigInt { +impl Sub<&BigInt> for &BigInt { type Output = BigInt; #[inline] @@ -45,7 +45,7 @@ impl<'a, 'b> Sub<&'b BigInt> for &'a BigInt { } } -impl<'a> Sub<BigInt> for &'a BigInt { +impl Sub<BigInt> for &BigInt { type Output = BigInt; #[inline] @@ -54,7 +54,7 @@ impl<'a> Sub<BigInt> for &'a BigInt { } } -impl<'a> Sub<&'a BigInt> for BigInt { +impl Sub<&BigInt> for BigInt { type Output = BigInt; #[inline] @@ -72,7 +72,7 @@ impl Sub<BigInt> for BigInt { } } -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 @@ use num_traits::{ToPrimitive, Zero}; /// /// 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 @@ impl<R: Rng + ?Sized> RandBigInt for R { } } -/// 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 @@ impl SampleUniform for BigUint { 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 @@ impl SampleUniform for BigInt { 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 @@ impl Integer for BigUint { /// 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 @@ impl Roots for BigUint { } } -/// 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 @@ pub(crate) fn biguint_from_vec(digits: Vec<BigDigit>) -> BigUint { } 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 @@ impl BigUint { 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 @@ impl BigUint { 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 @@ impl BigUint { self.normalize(); } - /// Creates and initializes a `BigUint`. + /// Creates and initializes a [`BigUint`]. /// /// The bytes are in big-endian byte order. /// @@ -586,11 +589,11 @@ impl BigUint { } 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 @@ impl BigUint { } } - /// 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 @@ impl BigUint { 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 @@ impl BigUint { 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 @@ impl BigUint { 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 @@ impl BigUint { 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 @@ impl BigUint { } } - /// 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 @@ impl BigUint { 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 @@ impl BigUint { 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 @@ impl BigUint { 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 @@ impl BigUint { /// 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 @@ impl BigUint { 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 @@ impl BigUint { } } - /// Returns a normalized `BigUint`. + /// Returns a normalized [`BigUint`]. #[inline] fn normalized(mut self) -> BigUint { self.normalize(); @@ -956,6 +959,30 @@ impl BigUint { } } +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 @@ impl IntDigits for BigUint { } } -/// 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 @@ pub(super) fn add2(a: &mut [BigDigit], b: &[BigDigit]) { 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 @@ impl<'a> Add<&'a BigUint> for BigUint { 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 @@ forward_ref_val_binop!(impl BitAnd for BigUint, bitand); // 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 @@ impl<'a, 'b> BitAnd<&'b BigUint> for &'a BigUint { 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 @@ impl<'a> BitAnd<&'a BigUint> for BigUint { 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 @@ impl<'a> BitAndAssign<&'a BigUint> for BigUint { 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 @@ impl<'a> BitOr<&'a BigUint> for BigUint { 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 @@ impl<'a> BitOrAssign<&'a BigUint> for BigUint { 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 @@ impl<'a> BitXor<&'a BigUint> for BigUint { 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::mem; 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 @@ fn from_radix_digits_be(v: &[u8], radix: u32) -> BigUint { debug_assert!(!v.is_empty() && !radix.is_power_of_two()); debug_assert!(v.iter().all(|&c| u32::from(c) < radix)); + // Estimate how big the result will be, so we can pre-allocate it. #[cfg(feature = "std")] - let radix_log2 = f64::from(radix).log2(); + 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 radix_log2 = ilog2(radix.next_power_of_two()) as f64; + 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 + }; - // 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(); 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 @@ fn high_bits_to_u64(v: &BigUint) -> u64 { 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; - ret_bits += bits_want; - bits -= bits_want; - if ret_bits == 64 { - break; + // 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; } ret @@ -572,6 +593,16 @@ impl_to_biguint!(u128, FromPrimitive::from_u128); 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 @@ pub(super) fn to_radix_digits_le(u: &BigUint, radix: u32) -> Vec<u8> { 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::cmp::Ordering::{Equal, Greater, Less}; 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 Div<BigUint> for BigUint { } } -impl<'a, 'b> Div<&'b BigUint> for &'a BigUint { +impl Div<&BigUint> for &BigUint { type Output = BigUint; #[inline] @@ -323,9 +323,9 @@ impl<'a, 'b> Div<&'b BigUint> for &'a BigUint { 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 Rem<BigUint> for BigUint { } } -impl<'a, 'b> Rem<&'b BigUint> for &'a BigUint { +impl Rem<&BigUint> for &BigUint { type Output = BigUint; #[inline] @@ -488,7 +488,7 @@ impl<'a, 'b> Rem<&'b BigUint> for &'a BigUint { } } } -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_ref_val!(impl Rem<u32> for BigUint, rem); 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 RemAssign<u32> for BigUint { } } -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 @@ impl<'a> Rem<&'a BigUint> for u32 { 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 @@ impl CheckedDiv for BigUint { 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 @@ impl MontyReducer { /// 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 @@ fn montgomery(x: &BigUint, y: &BigUint, m: &BigUint, k: BigDigit, n: usize) -> B 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 @@ fn sub_sign(mut a: &[BigDigit], mut b: &[BigDigit]) -> (Sign, BigUint) { } 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 @@ macro_rules! impl_mul { )*} } 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 @@ macro_rules! impl_mul_assign { )*} } 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 crate::big_digit::{self, BigDigit}; 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 Pow<BigUint> for BigUint { } } -impl<'a, 'b> Pow<&'b BigUint> for &'a BigUint { +impl Pow<&BigUint> for &BigUint { type Output = BigUint; #[inline] @@ -51,7 +51,7 @@ impl<'a, 'b> Pow<&'b BigUint> for &'a BigUint { } } -impl<'a> Pow<BigUint> for &'a BigUint { +impl Pow<BigUint> for &BigUint { type Output = BigUint; #[inline] @@ -92,7 +92,7 @@ macro_rules! pow_impl { } } - impl<'b> Pow<&'b $T> for BigUint { + impl Pow<&$T> for BigUint { type Output = BigUint; #[inline] @@ -101,7 +101,7 @@ macro_rules! pow_impl { } } - impl<'a> Pow<$T> for &'a BigUint { + impl Pow<$T> for &BigUint { type Output = BigUint; #[inline] @@ -113,7 +113,7 @@ macro_rules! pow_impl { } } - impl<'a, 'b> Pow<&'b $T> for &'a BigUint { + impl Pow<&$T> for &BigUint { type Output = BigUint; #[inline] @@ -225,27 +225,27 @@ fn test_plain_modpow() { 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 super::{biguint_from_vec, BigUint}; 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 @@ impl<'de> Visitor<'de> for U32Visitor { 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 @@ impl<'de> Visitor<'de> for U32Visitor { 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 @@ fn biguint_shl2(n: Cow<'_, BigUint>, digits: usize, shift: u8) -> BigUint { 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 @@ fn biguint_shr2(n: Cow<'_, BigUint>, digits: usize, shift: u8) -> BigUint { 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 @@ fn biguint_shr2(n: Cow<'_, BigUint>, digits: usize, shift: u8) -> BigUint { 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 @@ macro_rules! impl_shift { 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 @@ macro_rules! impl_shift { 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_val_val_binop!(impl Sub for BigUint, sub); 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 @@ impl<'a> Sub<&'a BigUint> for BigUint { 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 { @@ -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 @@ extern crate std; #[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 @@ extern crate alloc; #[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 @@ impl<T> TryFromBigIntError<T> { /// 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::bigint::ToBigInt; 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 @@ mod big_digit { (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_val_val_binop_commutative { 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 { 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_ref_val_binop_commutative { 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_val_ref_binop { 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 { 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_val_val_binop_to_ref_val { 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 @@ macro_rules! forward_scalar_ref_ref_binop_to_ref_val { } } - 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_ref_ref_binop_to_ref_val { 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 @@ macro_rules! forward_scalar_val_ref_binop_to_ref_val { } } - 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_ref_val { 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 @@ macro_rules! forward_scalar_val_ref_binop_to_val_val { } } - impl<'a> $imp<$res> for &'a $scalar { + impl $imp<$res> for &$scalar { type Output = $res; #[inline] @@ -233,7 +233,7 @@ macro_rules! forward_scalar_val_ref_binop_to_val_val { 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 @@ macro_rules! forward_scalar_ref_val_binop_to_val_val { } } - 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_val_binop_to_val_val { 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 @@ macro_rules! forward_scalar_ref_ref_binop_to_val_val { } } - 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::{i16, i32, i64, i8, isize}; 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 @@ fn test_to_bytes_le() { #[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 @@ fn test_to_signed_bytes_le() { #[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 @@ fn test_from_signed_bytes_le() { #[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 @@ fn test_to_signed_bytes_be() { #[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 @@ fn test_signed_bytes_le_round_trip() { #[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 @@ fn test_convert_f32() { 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 @@ fn test_convert_f64() { 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 @@ fn test_div_ceil() { } #[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 @@ fn test_lcm() { } #[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::{i128, u128}; 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 @@ mod macros; #[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 test_to_bytes_be() { 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 @@ fn test_to_bytes_be() { #[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 test_to_bytes_le() { 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 @@ fn test_convert_f32() { 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 @@ fn test_convert_f64() { 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 @@ fn test_div_ceil() { } #[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 @@ fn test_lcm() { } #[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 @@ mod bigint { 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)); |