Merge "Update num-bigint to 0.4.6." into main
diff --git a/crates/num-bigint/.android-checksum.json b/crates/num-bigint/.android-checksum.json
index 784a38e..c8260be 100644
--- a/crates/num-bigint/.android-checksum.json
+++ b/crates/num-bigint/.android-checksum.json
@@ -1 +1 @@
-{"package":null,"files":{".cargo-checksum.json":"c474d7b1e972aaac3ba2ad751456181f9352609ba5afaa55d79c729908f429ce","Android.bp":"4cdcb535e9fe5c0e81c99ea109648b98e5e5995b887704c5b3c30e60c5419abc","Cargo.toml":"3c5e9454ee88f5777011f279313358e81298e01224f5bea7b854dc483393c526","LICENSE":"3c7cd2396b5b772507febd2615d3d5a55b80103845037df77c87ba6e64872f2c","LICENSE-APACHE":"3c7cd2396b5b772507febd2615d3d5a55b80103845037df77c87ba6e64872f2c","LICENSE-MIT":"16693a68efd65bc6a9df3448c8f7ee6745418c73faff4ec4d443648c04285fa4","METADATA":"ebb9e723d418045170c370000a45160f22aac6704ce2737c3db66e81017b4621","MODULE_LICENSE_APACHE2":"0d6f8afa3940b7f06bebee651376d43bc8b0d5b437337be2696d30377451e93a","README.md":"f940329d227cacb8c6764bdfa83a347ca4d21504b2a82d872cd0456d3a70d58c","RELEASES.md":"82711df67e4677900233d9723dc0b733f7310db714ba12c4967bed945d9b31bf","TEST_MAPPING":"c7bad5ec6f7bf48bb856a231acfacaa7f39e438507a269c058f5250421ed683e","benches/bigint.rs":"9e883892483328f2698770d0b5563de5a2034379ac399b13cb5dc372d48669da","benches/factorial.rs":"6a0d78154597de3d3a469e661a2d0d29b0c095696d5387ddd6be4f0cc3da236b","benches/gcd.rs":"e66e9488678528c5386f43bcd1498da579a18b0d7a203b90e459f3fae80ba435","benches/rng/mod.rs":"9d49b4584c9bc6b3b1cbab51b08e00334b09b26b7a758491e8208ec7f21fe0b8","benches/roots.rs":"5d83ab3461ba7ed36b1a6c1250d73519f72bfd7309f2046b5d5437c8d3e68ae5","benches/shootout-pidigits.rs":"1393ffbdc2555e34818ba81a5bf9eb28c8568b71196bad4e811b504d145bea2e","build.rs":"d4a11772dfd067dd98f9657b17a3f8d3bb5f9ae69a5737102b2236b5fd90ef92","cargo_embargo.json":"be3a30d8e5d9126130b453bb35f83bfeaf4275f85e8209865cca2a6609eb4b2d","out/radix_bases.rs":"ed7b02913dc9ea14d5ac607b4c0cb9726549c7350cd9e70aaef564ad97d08112","patches/disable_tests.patch":"8e6908c72054213761d720a7fea46347042fb14b322f1d02216d7c4739a516da","patches/pin-autocfg-version.patch":"ce923d0868aff09af2454e3d09ba8f744609d96419d0da81710e8e8d911cde97","patches/remove-probe-files.patch":"f814eb4a30ccadd11bf62f70067c4fc2b7bee3dfaf05aff2e297af2b1afabd22","src/bigint.rs":"3763bb5be008327bad22ead79e7b2ba841de5f16b6ddb2e6fdcc3fa01d70c745","src/bigint/addition.rs":"582b2e34e48f04a2f9a569b644ff27588e1aa08a1de8ea2cb26edb327514c097","src/bigint/arbitrary.rs":"7d001a5966d0d4d9c69435270b38da102ac03804dba593433653f99d30da9bb8","src/bigint/bits.rs":"3b68b5af1a019923ac110571d7274ff11396ea9a9b1c8068b76be2e0cf99a957","src/bigint/convert.rs":"57e6ad3809058e69a80682c88e58a47105ccc7be1c953cbf219f874733deba74","src/bigint/division.rs":"5f402a3b99fdd8b710ecb4b395b56dda87d0dc3f0e052d82a1d37fca55a04971","src/bigint/multiplication.rs":"10605872fae3ee6e6af13ab7588151b390a11bd0c1b8234947334ffb2d4a0bc8","src/bigint/power.rs":"1d8f4ddef1881ee12b8047c46b1c38271e117aaf64d3ca0d5b0b36c7f200cb60","src/bigint/serde.rs":"6dcef1946d8249c87f3f310e4172fe2d1c8b37fff48924ed9e596ff0eda132f3","src/bigint/shift.rs":"7090e677289786c25e0a6ec13e89b9775dda240e624e4add5ac34f8ff08d70e1","src/bigint/subtraction.rs":"90dae2623ae729cef303fc96010a801481f5a2e0d351dfe51c34467dcf7fb206","src/bigrand.rs":"eb962c11890dff31976d04b964ee6f53b9067bdeb92f72abe05cc492bd255250","src/biguint.rs":"e2d196b385477da6646f3cfeff44b7f285361b362c575625c88d9ffdc7791eee","src/biguint/addition.rs":"60d474ce33a375a733587d8a76a5913f831b81fd3f95f14c734117fe266eedca","src/biguint/arbitrary.rs":"723d7f2b9aaff1cf88b11722a9ea6fc9f1eb7c359d41151f4b7f8eb0dcadbb59","src/biguint/bits.rs":"07fef255da30a2bb10d5c34dacb3c2b2a84c872dcefcaaa5c41bcd1519fe97e8","src/biguint/convert.rs":"0f6f1c6bae3bcc30a0e8ae1f1050c37b20c494d63ec4ff676eb2e86a54ce8ed0","src/biguint/division.rs":"db5fe4e18e62c435d72ff90f4941b401caac527e701f187beb9c0aafe7647029","src/biguint/iter.rs":"40c4d38ef3a0a8d5b85094e06bf6acc82027bc606f68f0cd6b76895b370179aa","src/biguint/monty.rs":"0880fad70df7893f8b2a0f74fae9a2ef51b1f9ff1ea641128d4f64d02e11fe77","src/biguint/multiplication.rs":"71f5bec327b9f9cacdf4a611176475a09449bcc51d34aa8ff495964ccf383982","src/biguint/power.rs":"c1bc2fcd128ffbdfe108dda83e34abc17d8a8e5b3ed60e9c854514cedda7d079","src/biguint/serde.rs":"7ec071edbaadcc7daa17d86d9039e84f1e530eb38337574e935afae607c12803","src/biguint/shift.rs":"d80b5790cf6658a6346c3b225cfe8bce516409ce84c1b0c2a7581655b7c480e6","src/biguint/subtraction.rs":"c23bd19d477d36bc0e4e628291debbc62e62b6419fd0fffacf5f999c68fcd0b7","src/lib.rs":"a2a71876248018ad59fc13622886dbbb9f83e71e07da63185ca03856f36be60b","src/macros.rs":"80b081a2600e235f78a9f8bd8cecbbcee925c3624a351ed4a1301852238beac0","tests/bigint.rs":"7fa53731766e0239db3e9faf1a1ba257704ddc21a2c0dc282398123df93a224e","tests/bigint_bitwise.rs":"f99856586df07fd0126f363b1bee30924135ba14657fb296cc2e35624d2afbac","tests/bigint_scalar.rs":"0ac683c29a4b8f883eca986b3234530fc493fb3e6f0cc16858093f49846492cc","tests/biguint.rs":"aa65b2e68b2d285641c88a4eb35eb99d198bd9e6a1bc2db5e3e3f56da5429962","tests/biguint_scalar.rs":"c8d90abf23d75f603c7b2e8f475959319a2374bd285fc7fc9a9d31e7f7ee4bab","tests/consts/mod.rs":"873ed51d89e18ba0da3c11a985f6a3f0df8be189fa41c2cf8b5e4c25233a9ae5","tests/fuzzed.rs":"b01ddbada1bdee35563ccb953deee3476f1a8cd6daa7de0e1a708bd0845c56fa","tests/macros/mod.rs":"20098c9bd76d007dec91fddf9a99196f9e3455485ca1f7165528597b18b39975","tests/modpow.rs":"fa80f4701af352e301161a465a9f4d374eed799a7de7f239bb4ec0857b1b9377","tests/roots.rs":"849dbe2c32b9488e4f094c1aaaa55f059602fb166b317bccfd01998d54b46474"}}
\ No newline at end of file
+{"package":null,"files":{".cargo-checksum.json":"626b607b73b3e005fe49806848857f387f5d6222276fde1628eb5f37de94cca5","Android.bp":"862279e0c8dbab3d68e6ca66cec24f617cd8c57d4cf712489da2b9f79eef31cb","Cargo.toml":"c192cc08038c59c085bc092ae6d73182d8e16c4fc41c88477aa943c33eb7d692","LICENSE":"3c7cd2396b5b772507febd2615d3d5a55b80103845037df77c87ba6e64872f2c","LICENSE-APACHE":"3c7cd2396b5b772507febd2615d3d5a55b80103845037df77c87ba6e64872f2c","LICENSE-MIT":"16693a68efd65bc6a9df3448c8f7ee6745418c73faff4ec4d443648c04285fa4","METADATA":"7de11c53a3a58ad7394dfa79b309e07bdec5ae6322ca3972f06a5fd83607a5f8","MODULE_LICENSE_APACHE2":"0d6f8afa3940b7f06bebee651376d43bc8b0d5b437337be2696d30377451e93a","README.md":"50e069a2328fc53a4c2b4186f9cb22f80271c4eba13bb65fe30966c76657ea11","RELEASES.md":"36c08807a67002d7fa82327ca5ebcf6553dc981b3471f11ab82ee3af2be3dce1","TEST_MAPPING":"c7bad5ec6f7bf48bb856a231acfacaa7f39e438507a269c058f5250421ed683e","benches/bigint.rs":"11044fe6ee2c8c7a0f827d42187496689c78a5f168684bde57f7d7ce5ce8fd93","benches/factorial.rs":"6a0d78154597de3d3a469e661a2d0d29b0c095696d5387ddd6be4f0cc3da236b","benches/gcd.rs":"e66e9488678528c5386f43bcd1498da579a18b0d7a203b90e459f3fae80ba435","benches/rng/mod.rs":"9d49b4584c9bc6b3b1cbab51b08e00334b09b26b7a758491e8208ec7f21fe0b8","benches/roots.rs":"5d83ab3461ba7ed36b1a6c1250d73519f72bfd7309f2046b5d5437c8d3e68ae5","benches/shootout-pidigits.rs":"1393ffbdc2555e34818ba81a5bf9eb28c8568b71196bad4e811b504d145bea2e","cargo_embargo.json":"be3a30d8e5d9126130b453bb35f83bfeaf4275f85e8209865cca2a6609eb4b2d","patches/disable_tests.patch":"8e6908c72054213761d720a7fea46347042fb14b322f1d02216d7c4739a516da","src/bigint.rs":"7f392985a5791a611c4facd493788ace49e57900ef3a31264725a8ce915c2bef","src/bigint/addition.rs":"e6a2946eb8721b9c777593d72bb4057bfa5fb1ea11bf73878640352f02960dbe","src/bigint/arbitrary.rs":"51f6937e59f386953ebf2733823be04c0f1861590bfc070888c36e7c3a610d1b","src/bigint/bits.rs":"b76d7abeaf07ebd1255b297590fa9d6b05c963cbc46f9610df728f99dc0a17ae","src/bigint/convert.rs":"98a6ddb01599bee9c1cb09264650a0ae3955cd1e8b22a6ac325315937e20f2a9","src/bigint/division.rs":"b75b3244b354a9cd6df59bed20b0128dcec401ce243de58f8b2bd772fa0f5ac3","src/bigint/multiplication.rs":"10605872fae3ee6e6af13ab7588151b390a11bd0c1b8234947334ffb2d4a0bc8","src/bigint/power.rs":"119ec879b2b65de573c9eb23955fc75655c8b0b05791a808d76c66de9fe78d14","src/bigint/serde.rs":"e49e01da48214a17de01f18b9a37c4787b91858513763af4d086b17d1f2bb411","src/bigint/shift.rs":"7090e677289786c25e0a6ec13e89b9775dda240e624e4add5ac34f8ff08d70e1","src/bigint/subtraction.rs":"687febaa35535cb0f8b81115020d17c09295b474030778500f584957ba0ffc74","src/bigrand.rs":"2a2c352e57d2dd95b40e116675ce2214e9a8f1c100667dac91965942a0564e28","src/biguint.rs":"67707669c4d99453131d8641d02919a4991392bc33bd6fbd3818f006cb6e6a19","src/biguint/addition.rs":"3de84c1c94bc3ea8e427026f3ec266e651144f4cd87354c8d6f7c89abd4c231c","src/biguint/arbitrary.rs":"007e5185a2e909fb7881b7cb4718fa3de31e9f841f192887d30a4075b8d3fac2","src/biguint/bits.rs":"07fef255da30a2bb10d5c34dacb3c2b2a84c872dcefcaaa5c41bcd1519fe97e8","src/biguint/convert.rs":"540bdd333542f54bb52466dc849d7a73503512cf44bb0a10b131dc820ff2b97f","src/biguint/division.rs":"a00701225783744cbe8fb11536f4851c09a39d9c82f41f67996519de76089f17","src/biguint/iter.rs":"e5c10ed11fc11fa2bda75bb1b884b89475626e983545d99132068a2d761792b1","src/biguint/monty.rs":"19ca69a11d0c580510dd65299374cd501feecb712da4b7bdc17d7ac0bba37071","src/biguint/multiplication.rs":"eecc40e564117990e853fe4b088d2f0dd85a1611e57758210d7ab6613cf28ab3","src/biguint/power.rs":"b7bf53f58cabd6ef581c4c5caa4e38407939e438dafcda780aab0e8205151443","src/biguint/serde.rs":"47b8f666ddeda66ea7ca7ff745edbd3543a57221e14ad27e46275a02f52deff7","src/biguint/shift.rs":"a6cfcc0476fd2cff0268614718f7e135b71899f208138293fe7ca99db0199638","src/biguint/subtraction.rs":"75cbdb772971330a27aee32fecf0dcb23e93886b9c4b5cffd5906ac25010a1f3","src/lib.rs":"8d98cc2ac5c23d00d35bcc7971a5ce9bcae0c11070bf462dc8c143de8dd6796a","src/macros.rs":"e5f1c3c3b455c6178e7448cb499d5304bb8e3683f6796aee02496ff7599907a5","tests/bigint.rs":"6b4e118d09fe901ab9ffdcee9e5d40aa0b26e27954db592408bb996b7578633b","tests/bigint_bitwise.rs":"dbc1ccd93320f427ffb84af856b1ba923e911038d5e34d9482dcd9d5b95d870b","tests/bigint_scalar.rs":"0ac683c29a4b8f883eca986b3234530fc493fb3e6f0cc16858093f49846492cc","tests/biguint.rs":"0ee251ef674fa9803281e90cc5b8ab190408418d93a68c4a73d31baf9fa5304f","tests/biguint_scalar.rs":"c8d90abf23d75f603c7b2e8f475959319a2374bd285fc7fc9a9d31e7f7ee4bab","tests/consts/mod.rs":"31035c244b43702f9751c8e48f45eb2a007a40585c3c50083e4054e78c732206","tests/fuzzed.rs":"b01ddbada1bdee35563ccb953deee3476f1a8cd6daa7de0e1a708bd0845c56fa","tests/macros/mod.rs":"20098c9bd76d007dec91fddf9a99196f9e3455485ca1f7165528597b18b39975","tests/modpow.rs":"fa80f4701af352e301161a465a9f4d374eed799a7de7f239bb4ec0857b1b9377","tests/roots.rs":"c632b43665d471a12c0cbfb4eecb9fa010fe3bf4c9df182aad10d206dd324ecb"}}
\ No newline at end of file
diff --git a/crates/num-bigint/.cargo-checksum.json b/crates/num-bigint/.cargo-checksum.json
index 28c7008..5de47f9 100644
--- a/crates/num-bigint/.cargo-checksum.json
+++ b/crates/num-bigint/.cargo-checksum.json
@@ -1 +1 @@
-{"files":{"Cargo.toml":"2cfbab335a56779607ae2bd573b3144768321d4aaeb3b48a8fc5e8473bfe61ff","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"6485b8ed310d3f0340bf1ad1f47645069ce4069dcc6bb46c7d5c6faf41de1fdb","README.md":"1ee66f7d39c572dabe553b5ad698111d58a9ab1f0019ed8b6371af2b67ad0aae","RELEASES.md":"ed8cff3aa3583da2ab9cb3185e93b5644aafbef03e08647b51f57ddc99d27acd","benches/bigint.rs":"7efd4741f53c786bae63d1196492b5657fd0d928b37a59a08629f6efdc35c845","benches/factorial.rs":"ed1d276a780e7e5fe79121b941c22a00c2854dbf92fd8a5372619853ba0c13b7","benches/gcd.rs":"3cc1a3356f680a6fa625f0ece0c8dd778f4091a53a31177f2870ef9a6c858c7d","benches/rng/mod.rs":"38144fc8283955db4be72a1533328fded98986d6f9d0bc7da0b306f7d4b5ca43","benches/roots.rs":"b31846852a7215c26df228940f2e469aff32fa8805eccc2b5ee5e7280ef0eeb4","benches/shootout-pidigits.rs":"c2a48133f5b679928f7e3f4e764c78aaa8c5b811f58b86fe57fae8c63cb07136","build.rs":"9a4c2d95c240f46a54b565a6fc9d5f3b2fef2634bc829175ea7740652207bd34","src/bigint.rs":"f7aa256232ac8b4208ae6c3e026a4313afd6d0a79377d0d989ef6db8b31bb942","src/bigint/addition.rs":"57d88a77b36494441b6b6e969269c4dee237cead018512f2bcd074f28806ef00","src/bigint/arbitrary.rs":"6679833dffb38fa81f251bf9dd35b0d5b4cecb2a368e82aac92b00cef4dfc21b","src/bigint/bits.rs":"0e09e62317fa74a85c7f45c2bf441a7a40bb02b4a2ef52620871573b73ac6808","src/bigint/convert.rs":"8c3763391fc2df1e79268fcc03cae4454ace87455d1994288e55473a8993528a","src/bigint/division.rs":"1a268e7739a7f5be56ff084aa092d1c570e593690ca980ff77254faf51620202","src/bigint/multiplication.rs":"c262f732b86cc36804895df21e5ea5221944cadc1fca7903ff75a26102ba70f1","src/bigint/power.rs":"0ed57f2c9b5bc3debd6811dbb8705d07b0131f594be268321da35e70c08dbea9","src/bigint/serde.rs":"8240ed79ac11ec0ec2dfc85d4657693d5b03379bdd60a42dccee4764b000e5b6","src/bigint/shift.rs":"3f28bca2d52621133cdf567290645d30a746e663d8dacea29c172b5ed7ff3538","src/bigint/subtraction.rs":"6c3cce163293e2b95df38df4797329e2f9b43369e845697744dfbe43a67399ce","src/bigrand.rs":"2af7fde779b326006d1fd00f85f81ab6d3b2e30ec370fe4eaa41eeceeec6b7a6","src/biguint.rs":"a8c6b4d5fd6c3e07e888727385fc7148ad5e952eb940ee48c3086c864ad80941","src/biguint/addition.rs":"4f79fc1fc3157303309dcfa2166ae10ed33edbb11bf5602c43038485b5562746","src/biguint/arbitrary.rs":"895fe5a9bbcf40824d1a342e089fb2aec78cb9bad0dd489cfef489a3323f6c3b","src/biguint/bits.rs":"509036c6c6cb083d4568f92ac852cf5f12510f98c4547d47a80e3db4282a159e","src/biguint/convert.rs":"10d25021dab0bf88a58b96ca786689f72530a946d0a080e29ba40079dc1d844d","src/biguint/division.rs":"bedce3a1a7ffa271e0b74e98929f98a87343bb6a54a9de3c2effdd27041c78a5","src/biguint/iter.rs":"c21e30f573bdf1936e72dd56a89ee662329d25e8b55e37e88e9b1aea2da48abd","src/biguint/monty.rs":"08554859ed7aeaec89b311458c443d3eab375b02da7a9b20df8b42ed18b8c8c1","src/biguint/multiplication.rs":"501da2844830b1699a05e58fae3deb21b158fc0871e2cd4fc50049202faeb2c8","src/biguint/power.rs":"e428489a4aa6db640fde03eca61bce8eb56502303c48794248a6d14154ecf2ae","src/biguint/serde.rs":"23e028b21a9a836f443c8bf996c2011d2a1df87bc53fb96b83ae1545efccba81","src/biguint/shift.rs":"c67a37cf2605e06bb706d493659303992d25d623fa62dfa085e01d53acbaa08a","src/biguint/subtraction.rs":"3b18ab809da5efed5204217b46ccf4d653b3e8abb61820c1e0eebe13e400b3a9","src/lib.rs":"35f99739d938f36701d7951e40aaaf4a5b96efdce6c6d489af775913ed32eed4","src/macros.rs":"a007d89d68848f99119c524ff1d01c4acaf052f46555cb395fff066879153b77","tests/bigint.rs":"f2bfe36ebee59e083a1133838240167e902f1f2580bce68057a86de9dab5fe56","tests/bigint_bitwise.rs":"e6a2f76fa1eb919e7c513d7e30a8a2a963841a295a71103462fb8ab9792419b5","tests/bigint_scalar.rs":"a87e801e370686985d44e1f020c69fceca72b9f048e0f7301d2b8d38469e5636","tests/biguint.rs":"09dc0cc5e7c81974e2097666de3732917b21df93362b17fcab1e180d44296d0a","tests/biguint_scalar.rs":"b09cda9d4fe6ec519e93282653f69b57d70db73b9cb59c0ea5cd0861ca2de266","tests/consts/mod.rs":"e20bc49a7cc95077242cbe4016b37745ea986c779d2385cb367fbfe44f15ff94","tests/fuzzed.rs":"f60a84c446ea2f45d87eb4ee64682ea63fdef05bc74f482739d4e968960e8f4e","tests/macros/mod.rs":"1a8f9f015e5caaac60ce9ccff01a75ae489801c3ede6e7b9b3c5079b6efefc9c","tests/modpow.rs":"f4c81111308d63876ed02229cbab50bec9bac082bfa71f481120e46b5d7e5560","tests/roots.rs":"a3bc2de170a0f6297cc8d8830d608db537ca102ccf204fd4fb8e2d92675622d8"},"package":"608e7659b5c3d7cba262d894801b9ec9d00de989e8a82bd4bef91d08da45cdc0"}
\ No newline at end of file
+{"files":{"Cargo.toml":"a6042603541ecb91ec1f5c158679c0b47090462434e2a53e65f78395994f223f","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"6485b8ed310d3f0340bf1ad1f47645069ce4069dcc6bb46c7d5c6faf41de1fdb","README.md":"abf3dae8d5ccf7693234cb0101a205f844959366bc906a1a5b53973a73a3054c","RELEASES.md":"80b60df30e92e913d710e558f1a2de0baa8a3e49b242c66bc1a1a18de5ff4618","benches/bigint.rs":"0943fcfdc290db028bc37d63c118284c79681a52a62311cc036da80d3b9ac390","benches/factorial.rs":"ed1d276a780e7e5fe79121b941c22a00c2854dbf92fd8a5372619853ba0c13b7","benches/gcd.rs":"3cc1a3356f680a6fa625f0ece0c8dd778f4091a53a31177f2870ef9a6c858c7d","benches/rng/mod.rs":"38144fc8283955db4be72a1533328fded98986d6f9d0bc7da0b306f7d4b5ca43","benches/roots.rs":"b31846852a7215c26df228940f2e469aff32fa8805eccc2b5ee5e7280ef0eeb4","benches/shootout-pidigits.rs":"c2a48133f5b679928f7e3f4e764c78aaa8c5b811f58b86fe57fae8c63cb07136","src/bigint.rs":"e5735688e1345396c21a7f5e8328bcdf77f5a0c7068028caa74063c68a3e4ef7","src/bigint/addition.rs":"cdc28e59a5dc6fe7dbad2d8d9514b49fe1bea061e82ebefe89c518f448dc8ba9","src/bigint/arbitrary.rs":"9fb1f7f8bbc7a792d19d4c30ed2671ed2d73847d57e5f65380ae31e5db0146c6","src/bigint/bits.rs":"3d696d43bcd336690ce1412af75a38d490fd2af745c2efc7cb2fc51bace07de8","src/bigint/convert.rs":"1463ecd5e39c938ae5b8e2b685d69a85c2e795c1fa96531b2192abb11ccdf638","src/bigint/division.rs":"dea89b4efb06b77bbbf07036c454d52f4d026658bcbacad1d15302c93d61b3dd","src/bigint/multiplication.rs":"c262f732b86cc36804895df21e5ea5221944cadc1fca7903ff75a26102ba70f1","src/bigint/power.rs":"a3823654f022014c5ce2dc2fd97afa6696589d32a54cc4ec65e6c113e8613672","src/bigint/serde.rs":"a7275341ec518f27f4d955e95b6e302b786944e9462bf0c17c7087d073212943","src/bigint/shift.rs":"3f28bca2d52621133cdf567290645d30a746e663d8dacea29c172b5ed7ff3538","src/bigint/subtraction.rs":"c2aa7e0fbfc7747099d0eec77efdedaa8d79cff88b1587d640d6b1c3c7dc0e4a","src/bigrand.rs":"115ab17de1c909b22bf20374b31cf5b1e9b28cd4914bf8cd6852375c35d6a027","src/biguint.rs":"bf69f80a59b528e0743390663f9a6a8f6d3edc8643a65c8d0f7f01a8f434f478","src/biguint/addition.rs":"1429575654102731024259da7d5586a4db44387ae86c1b170083c5565b37b410","src/biguint/arbitrary.rs":"3492432d1b5e9f851ce120549bf82e89ba2b6c51f584f8d9ac6782fe10fb58dc","src/biguint/bits.rs":"509036c6c6cb083d4568f92ac852cf5f12510f98c4547d47a80e3db4282a159e","src/biguint/convert.rs":"85cdb3e60856d281f45dff602960666fe44af0ab54ba2ce26cfa4018a9309c60","src/biguint/division.rs":"13ed075f244510eb0354b899b8b9d99216d202bd4eae445ee18a444e06dd708b","src/biguint/iter.rs":"6f843751c93520817a182a2a335001ff221478499eb765d09a0a6f19ba0f7f97","src/biguint/monty.rs":"68851ce7542acdc180431905668684dcadf7d5b422073c6d8acc418ceb86f5d0","src/biguint/multiplication.rs":"e3908aecda0fbbf8c97c96d1d9b24ff9bbe4e09df3b15e460e00c73ecf1c0e4e","src/biguint/power.rs":"4740974546f85da802f7fee4a7c595a8d1b46611914130237cd26c20c268db84","src/biguint/serde.rs":"f4d4e6f2d56c9bab95d8b178682ebeba88965a36bcff42ccade3334712c9977a","src/biguint/shift.rs":"4962ff0d8d0371e7ab39b00a9fc29907e5cd37b9819f61d5ef82ff13b0f55071","src/biguint/subtraction.rs":"b124b9a12bdb67cadb98050feba8cd04fcd22e985c2f994b7c473d38b94f4821","src/lib.rs":"70493e8293b769076d6a16df962a4913b74aa1925fe8bd448865da097ee2dbe1","src/macros.rs":"ab2a5b6e39538f62fdf39f6f3695e9f2f532715f40109795a787aadbb2b8ea9a","tests/bigint.rs":"929422608f842cfb0bdd5117f5af74c954704d3c84df7da46b0eea1fdedd5ba8","tests/bigint_bitwise.rs":"a69d59c3eb07867f9da66ad9a8ae101a15366f88fb1f72f2015a9fe4de3518db","tests/bigint_scalar.rs":"a87e801e370686985d44e1f020c69fceca72b9f048e0f7301d2b8d38469e5636","tests/biguint.rs":"61fb3cb51ab2102330225adbfbbef9934defc23be9ab04e4c09129cd67b6f380","tests/biguint_scalar.rs":"b09cda9d4fe6ec519e93282653f69b57d70db73b9cb59c0ea5cd0861ca2de266","tests/consts/mod.rs":"f077d1aea22895a29df4e1391b40cc983cde9389f97e5b30923765f61dc3d017","tests/fuzzed.rs":"f60a84c446ea2f45d87eb4ee64682ea63fdef05bc74f482739d4e968960e8f4e","tests/macros/mod.rs":"1a8f9f015e5caaac60ce9ccff01a75ae489801c3ede6e7b9b3c5079b6efefc9c","tests/modpow.rs":"f4c81111308d63876ed02229cbab50bec9bac082bfa71f481120e46b5d7e5560","tests/roots.rs":"1c1576309eef9a6eb7ac8db4358fcf1d5b55403deaf27fd40ba2aa61b9567c87"},"package":"a5e44f723f1133c9deac646763579fdb3ac745e418f2a7af9cd0c431da1f20b9"}
\ No newline at end of file
diff --git a/crates/num-bigint/Android.bp b/crates/num-bigint/Android.bp
index 2054852..b389417 100644
--- a/crates/num-bigint/Android.bp
+++ b/crates/num-bigint/Android.bp
@@ -13,30 +13,18 @@
license_text: ["LICENSE"],
}
-genrule {
- name: "copy_num-bigint_build_out",
- srcs: ["out/*"],
- cmd: "cp $(in) $(genDir)",
- out: ["radix_bases.rs"],
-}
-
rust_library {
name: "libnum_bigint",
host_supported: true,
crate_name: "num_bigint",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "src/lib.rs",
- srcs: [":copy_num-bigint_build_out"],
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_integer",
"libnum_traits",
@@ -54,23 +42,18 @@
host_supported: true,
crate_name: "num_bigint",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "src/lib.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_integer",
"libnum_traits",
@@ -82,23 +65,18 @@
host_supported: true,
crate_name: "bigint",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "tests/bigint.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_bigint",
"libnum_integer",
@@ -111,23 +89,18 @@
host_supported: true,
crate_name: "bigint_bitwise",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "tests/bigint_bitwise.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_bigint",
"libnum_integer",
@@ -140,23 +113,18 @@
host_supported: true,
crate_name: "bigint_scalar",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "tests/bigint_scalar.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_bigint",
"libnum_integer",
@@ -169,23 +137,18 @@
host_supported: true,
crate_name: "biguint",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "tests/biguint.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_bigint",
"libnum_integer",
@@ -198,23 +161,18 @@
host_supported: true,
crate_name: "biguint_scalar",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "tests/biguint_scalar.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_bigint",
"libnum_integer",
@@ -227,23 +185,18 @@
host_supported: true,
crate_name: "fuzzed",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "tests/fuzzed.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_bigint",
"libnum_integer",
@@ -256,23 +209,18 @@
host_supported: true,
crate_name: "modpow",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "tests/modpow.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_bigint",
"libnum_integer",
@@ -285,23 +233,18 @@
host_supported: true,
crate_name: "roots",
cargo_env_compat: true,
- cargo_pkg_version: "0.4.4",
+ cargo_pkg_version: "0.4.6",
crate_root: "tests/roots.rs",
- srcs: [":copy_num-bigint_build_out"],
test_suites: ["general-tests"],
auto_gen_config: true,
test_options: {
unit_test: true,
},
- edition: "2018",
+ edition: "2021",
features: [
"default",
"std",
],
- cfgs: [
- "has_try_from",
- "u64_digit",
- ],
rustlibs: [
"libnum_bigint",
"libnum_integer",
diff --git a/crates/num-bigint/Cargo.toml b/crates/num-bigint/Cargo.toml
index 7e93523..0218bbd 100644
--- a/crates/num-bigint/Cargo.toml
+++ b/crates/num-bigint/Cargo.toml
@@ -10,13 +10,12 @@
# See Cargo.toml.orig for the original contents.
[package]
-edition = "2018"
+edition = "2021"
+rust-version = "1.60"
name = "num-bigint"
-version = "0.4.4"
+version = "0.4.6"
authors = ["The Rust Project Developers"]
-build = "build.rs"
exclude = [
- "/bors.toml",
"/ci/*",
"/.github/*",
]
@@ -45,6 +44,10 @@
"quickcheck",
"arbitrary",
]
+rustdoc-args = [
+ "--cfg",
+ "docsrs",
+]
[[bench]]
name = "bigint"
@@ -68,12 +71,12 @@
default-features = false
[dependencies.num-integer]
-version = "0.1.42"
+version = "0.1.46"
features = ["i128"]
default-features = false
[dependencies.num-traits]
-version = "0.2.16"
+version = "0.2.18"
features = ["i128"]
default-features = false
@@ -92,14 +95,12 @@
optional = true
default-features = false
-[build-dependencies.autocfg]
-# autocfg 1.4 uses different, non-deterministic filenames. We don't
-# actually depend on these files, but they are present in the out/
-# directory, and it's simpler to keep them around.
-version = "=1.1.0"
-
[features]
+arbitrary = ["dep:arbitrary"]
default = ["std"]
+quickcheck = ["dep:quickcheck"]
+rand = ["dep:rand"]
+serde = ["dep:serde"]
std = [
"num-integer/std",
"num-traits/std",
diff --git a/crates/num-bigint/METADATA b/crates/num-bigint/METADATA
index 0b227f8..6b3715c 100644
--- a/crates/num-bigint/METADATA
+++ b/crates/num-bigint/METADATA
@@ -1,20 +1,17 @@
-# 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 {
+ version: "0.4.6"
license_type: NOTICE
last_upgrade_date {
- year: 2024
- month: 2
- day: 2
+ year: 2025
+ month: 1
+ day: 22
}
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"
+ value: "https://static.crates.io/crates/num-bigint/num-bigint-0.4.6.crate"
+ version: "0.4.6"
}
}
diff --git a/crates/num-bigint/README.md b/crates/num-bigint/README.md
index 21f7749..cce185b 100644
--- a/crates/num-bigint/README.md
+++ b/crates/num-bigint/README.md
@@ -2,7 +2,7 @@
[](https://crates.io/crates/num-bigint)
[](https://docs.rs/num-bigint)
-[](https://rust-lang.github.io/rfcs/2495-min-rust-version.html)
+[](https://rust-lang.github.io/rfcs/2495-min-rust-version.html)
[](https://github.com/rust-num/num-bigint/actions)
Big integer types for Rust, `BigInt` and `BigUint`.
@@ -42,7 +42,7 @@
## Compatibility
-The `num-bigint` crate is tested for rustc 1.31 and greater.
+The `num-bigint` crate is tested for rustc 1.60 and greater.
## Alternatives
@@ -52,10 +52,10 @@
| Crate | License | Min rustc | Implementation | Features |
| :--------------- | :------------- | :-------- | :------------- | :------- |
-| **`num-bigint`** | MIT/Apache-2.0 | 1.31 | pure rust | dynamic width, number theoretical functions |
+| **`num-bigint`** | MIT/Apache-2.0 | 1.60 | 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 |
+| [`bnum`] | MIT/Apache-2.0 | 1.65 | pure rust | fixed width, parity with Rust primitives including floats |
+| [`crypto-bigint`] | MIT/Apache-2.0 | 1.73 | 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 |
diff --git a/crates/num-bigint/RELEASES.md b/crates/num-bigint/RELEASES.md
index ad5dd49..bc4c353 100644
--- a/crates/num-bigint/RELEASES.md
+++ b/crates/num-bigint/RELEASES.md
@@ -1,3 +1,27 @@
+# Release 0.4.6 (2024-06-27)
+
+- [Fixed compilation on `x86_64-unknown-linux-gnux32`.][312]
+
+**Contributors**: @cuviper, @ralphtandetzky, @yhx-12243
+
+[312]: https://github.com/rust-num/num-bigint/pull/312
+
+# Release 0.4.5 (2024-05-06)
+
+- [Upgrade to 2021 edition, **MSRV 1.60**][292]
+- [Add `const ZERO` and implement `num_traits::ConstZero`][298]
+- [Add `modinv` methods for the modular inverse][288]
+- [Optimize multiplication with imbalanced operands][295]
+- [Optimize scalar division on x86 and x86-64][236]
+
+**Contributors**: @cuviper, @joelonsql, @waywardmonkeys
+
+[236]: https://github.com/rust-num/num-bigint/pull/236
+[288]: https://github.com/rust-num/num-bigint/pull/288
+[292]: https://github.com/rust-num/num-bigint/pull/292
+[295]: https://github.com/rust-num/num-bigint/pull/295
+[298]: https://github.com/rust-num/num-bigint/pull/298
+
# Release 0.4.4 (2023-08-22)
- [Implemented `From<bool>` for `BigInt` and `BigUint`.][239]
diff --git a/crates/num-bigint/benches/bigint.rs b/crates/num-bigint/benches/bigint.rs
index 80ec191..2279527 100644
--- a/crates/num-bigint/benches/bigint.rs
+++ b/crates/num-bigint/benches/bigint.rs
@@ -88,6 +88,16 @@
}
#[bench]
+fn multiply_4(b: &mut Bencher) {
+ multiply_bench(b, 1 << 12, 1 << 13);
+}
+
+#[bench]
+fn multiply_5(b: &mut Bencher) {
+ multiply_bench(b, 1 << 12, 1 << 14);
+}
+
+#[bench]
fn divide_0(b: &mut Bencher) {
divide_bench(b, 1 << 8, 1 << 6);
}
diff --git a/crates/num-bigint/build.rs b/crates/num-bigint/build.rs
deleted file mode 100644
index 82b7a43..0000000
--- a/crates/num-bigint/build.rs
+++ /dev/null
@@ -1,103 +0,0 @@
-use std::env;
-use std::error::Error;
-use std::fs::File;
-use std::io::Write;
-use std::path::Path;
-
-fn main() {
- 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(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, arch, digit);
- if ac.probe_path(&addcarry) {
- autocfg::emit("use_addcarry");
- }
- }
- }
-
- // autocfg generates probe files in $OUT_DIR with nondeterministic contents.
- // (In autocfg 1.4, the filenames are nondeterministic as well.)
- let out_dir_env = env::var("OUT_DIR").unwrap();
- let out_dir = Path::new(&out_dir_env);
- std::fs::remove_file(out_dir.join("probe0.ll")).unwrap();
- std::fs::remove_file(out_dir.join("probe1.ll")).unwrap();
- std::fs::remove_file(out_dir.join("probe2.ll")).unwrap();
- std::fs::remove_file(out_dir.join("probe3.ll")).unwrap();
-
- autocfg::rerun_path("build.rs");
-
- write_radix_bases().unwrap();
-}
-
-/// Write tables of the greatest power of each radix for the given bit size. These are returned
-/// from `biguint::get_radix_base` to batch the multiplication/division of radix conversions on
-/// full `BigUint` values, operating on primitive integers as much as possible.
-///
-/// e.g. BASES_16[3] = (59049, 10) // 3¹⁰ fits in u16, but 3¹¹ is too big
-/// BASES_32[3] = (3486784401, 20)
-/// BASES_64[3] = (12157665459056928801, 40)
-///
-/// Powers of two are not included, just zeroed, as they're implemented with shifts.
-fn write_radix_bases() -> Result<(), Box<dyn Error>> {
- let out_dir = env::var("OUT_DIR")?;
- let dest_path = Path::new(&out_dir).join("radix_bases.rs");
- let mut f = File::create(&dest_path)?;
-
- for &bits in &[16, 32, 64] {
- let max = if bits < 64 {
- (1 << bits) - 1
- } else {
- std::u64::MAX
- };
-
- writeln!(f, "#[deny(overflowing_literals)]")?;
- writeln!(
- f,
- "pub(crate) static BASES_{bits}: [(u{bits}, usize); 257] = [",
- bits = bits
- )?;
- for radix in 0u64..257 {
- let (base, power) = if radix == 0 || radix.is_power_of_two() {
- (0, 0)
- } else {
- let mut power = 1;
- let mut base = radix;
-
- while let Some(b) = base.checked_mul(radix) {
- if b > max {
- break;
- }
- base = b;
- power += 1;
- }
- (base, power)
- };
- writeln!(f, " ({}, {}), // {}", base, power, radix)?;
- }
- writeln!(f, "];")?;
- }
-
- Ok(())
-}
diff --git a/crates/num-bigint/out/radix_bases.rs b/crates/num-bigint/out/radix_bases.rs
deleted file mode 100644
index 8702741..0000000
--- a/crates/num-bigint/out/radix_bases.rs
+++ /dev/null
@@ -1,780 +0,0 @@
-#[deny(overflowing_literals)]
-pub(crate) static BASES_16: [(u16, usize); 257] = [
- (0, 0), // 0
- (0, 0), // 1
- (0, 0), // 2
- (59049, 10), // 3
- (0, 0), // 4
- (15625, 6), // 5
- (46656, 6), // 6
- (16807, 5), // 7
- (0, 0), // 8
- (59049, 5), // 9
- (10000, 4), // 10
- (14641, 4), // 11
- (20736, 4), // 12
- (28561, 4), // 13
- (38416, 4), // 14
- (50625, 4), // 15
- (0, 0), // 16
- (4913, 3), // 17
- (5832, 3), // 18
- (6859, 3), // 19
- (8000, 3), // 20
- (9261, 3), // 21
- (10648, 3), // 22
- (12167, 3), // 23
- (13824, 3), // 24
- (15625, 3), // 25
- (17576, 3), // 26
- (19683, 3), // 27
- (21952, 3), // 28
- (24389, 3), // 29
- (27000, 3), // 30
- (29791, 3), // 31
- (0, 0), // 32
- (35937, 3), // 33
- (39304, 3), // 34
- (42875, 3), // 35
- (46656, 3), // 36
- (50653, 3), // 37
- (54872, 3), // 38
- (59319, 3), // 39
- (64000, 3), // 40
- (1681, 2), // 41
- (1764, 2), // 42
- (1849, 2), // 43
- (1936, 2), // 44
- (2025, 2), // 45
- (2116, 2), // 46
- (2209, 2), // 47
- (2304, 2), // 48
- (2401, 2), // 49
- (2500, 2), // 50
- (2601, 2), // 51
- (2704, 2), // 52
- (2809, 2), // 53
- (2916, 2), // 54
- (3025, 2), // 55
- (3136, 2), // 56
- (3249, 2), // 57
- (3364, 2), // 58
- (3481, 2), // 59
- (3600, 2), // 60
- (3721, 2), // 61
- (3844, 2), // 62
- (3969, 2), // 63
- (0, 0), // 64
- (4225, 2), // 65
- (4356, 2), // 66
- (4489, 2), // 67
- (4624, 2), // 68
- (4761, 2), // 69
- (4900, 2), // 70
- (5041, 2), // 71
- (5184, 2), // 72
- (5329, 2), // 73
- (5476, 2), // 74
- (5625, 2), // 75
- (5776, 2), // 76
- (5929, 2), // 77
- (6084, 2), // 78
- (6241, 2), // 79
- (6400, 2), // 80
- (6561, 2), // 81
- (6724, 2), // 82
- (6889, 2), // 83
- (7056, 2), // 84
- (7225, 2), // 85
- (7396, 2), // 86
- (7569, 2), // 87
- (7744, 2), // 88
- (7921, 2), // 89
- (8100, 2), // 90
- (8281, 2), // 91
- (8464, 2), // 92
- (8649, 2), // 93
- (8836, 2), // 94
- (9025, 2), // 95
- (9216, 2), // 96
- (9409, 2), // 97
- (9604, 2), // 98
- (9801, 2), // 99
- (10000, 2), // 100
- (10201, 2), // 101
- (10404, 2), // 102
- (10609, 2), // 103
- (10816, 2), // 104
- (11025, 2), // 105
- (11236, 2), // 106
- (11449, 2), // 107
- (11664, 2), // 108
- (11881, 2), // 109
- (12100, 2), // 110
- (12321, 2), // 111
- (12544, 2), // 112
- (12769, 2), // 113
- (12996, 2), // 114
- (13225, 2), // 115
- (13456, 2), // 116
- (13689, 2), // 117
- (13924, 2), // 118
- (14161, 2), // 119
- (14400, 2), // 120
- (14641, 2), // 121
- (14884, 2), // 122
- (15129, 2), // 123
- (15376, 2), // 124
- (15625, 2), // 125
- (15876, 2), // 126
- (16129, 2), // 127
- (0, 0), // 128
- (16641, 2), // 129
- (16900, 2), // 130
- (17161, 2), // 131
- (17424, 2), // 132
- (17689, 2), // 133
- (17956, 2), // 134
- (18225, 2), // 135
- (18496, 2), // 136
- (18769, 2), // 137
- (19044, 2), // 138
- (19321, 2), // 139
- (19600, 2), // 140
- (19881, 2), // 141
- (20164, 2), // 142
- (20449, 2), // 143
- (20736, 2), // 144
- (21025, 2), // 145
- (21316, 2), // 146
- (21609, 2), // 147
- (21904, 2), // 148
- (22201, 2), // 149
- (22500, 2), // 150
- (22801, 2), // 151
- (23104, 2), // 152
- (23409, 2), // 153
- (23716, 2), // 154
- (24025, 2), // 155
- (24336, 2), // 156
- (24649, 2), // 157
- (24964, 2), // 158
- (25281, 2), // 159
- (25600, 2), // 160
- (25921, 2), // 161
- (26244, 2), // 162
- (26569, 2), // 163
- (26896, 2), // 164
- (27225, 2), // 165
- (27556, 2), // 166
- (27889, 2), // 167
- (28224, 2), // 168
- (28561, 2), // 169
- (28900, 2), // 170
- (29241, 2), // 171
- (29584, 2), // 172
- (29929, 2), // 173
- (30276, 2), // 174
- (30625, 2), // 175
- (30976, 2), // 176
- (31329, 2), // 177
- (31684, 2), // 178
- (32041, 2), // 179
- (32400, 2), // 180
- (32761, 2), // 181
- (33124, 2), // 182
- (33489, 2), // 183
- (33856, 2), // 184
- (34225, 2), // 185
- (34596, 2), // 186
- (34969, 2), // 187
- (35344, 2), // 188
- (35721, 2), // 189
- (36100, 2), // 190
- (36481, 2), // 191
- (36864, 2), // 192
- (37249, 2), // 193
- (37636, 2), // 194
- (38025, 2), // 195
- (38416, 2), // 196
- (38809, 2), // 197
- (39204, 2), // 198
- (39601, 2), // 199
- (40000, 2), // 200
- (40401, 2), // 201
- (40804, 2), // 202
- (41209, 2), // 203
- (41616, 2), // 204
- (42025, 2), // 205
- (42436, 2), // 206
- (42849, 2), // 207
- (43264, 2), // 208
- (43681, 2), // 209
- (44100, 2), // 210
- (44521, 2), // 211
- (44944, 2), // 212
- (45369, 2), // 213
- (45796, 2), // 214
- (46225, 2), // 215
- (46656, 2), // 216
- (47089, 2), // 217
- (47524, 2), // 218
- (47961, 2), // 219
- (48400, 2), // 220
- (48841, 2), // 221
- (49284, 2), // 222
- (49729, 2), // 223
- (50176, 2), // 224
- (50625, 2), // 225
- (51076, 2), // 226
- (51529, 2), // 227
- (51984, 2), // 228
- (52441, 2), // 229
- (52900, 2), // 230
- (53361, 2), // 231
- (53824, 2), // 232
- (54289, 2), // 233
- (54756, 2), // 234
- (55225, 2), // 235
- (55696, 2), // 236
- (56169, 2), // 237
- (56644, 2), // 238
- (57121, 2), // 239
- (57600, 2), // 240
- (58081, 2), // 241
- (58564, 2), // 242
- (59049, 2), // 243
- (59536, 2), // 244
- (60025, 2), // 245
- (60516, 2), // 246
- (61009, 2), // 247
- (61504, 2), // 248
- (62001, 2), // 249
- (62500, 2), // 250
- (63001, 2), // 251
- (63504, 2), // 252
- (64009, 2), // 253
- (64516, 2), // 254
- (65025, 2), // 255
- (0, 0), // 256
-];
-#[deny(overflowing_literals)]
-pub(crate) static BASES_32: [(u32, usize); 257] = [
- (0, 0), // 0
- (0, 0), // 1
- (0, 0), // 2
- (3486784401, 20), // 3
- (0, 0), // 4
- (1220703125, 13), // 5
- (2176782336, 12), // 6
- (1977326743, 11), // 7
- (0, 0), // 8
- (3486784401, 10), // 9
- (1000000000, 9), // 10
- (2357947691, 9), // 11
- (429981696, 8), // 12
- (815730721, 8), // 13
- (1475789056, 8), // 14
- (2562890625, 8), // 15
- (0, 0), // 16
- (410338673, 7), // 17
- (612220032, 7), // 18
- (893871739, 7), // 19
- (1280000000, 7), // 20
- (1801088541, 7), // 21
- (2494357888, 7), // 22
- (3404825447, 7), // 23
- (191102976, 6), // 24
- (244140625, 6), // 25
- (308915776, 6), // 26
- (387420489, 6), // 27
- (481890304, 6), // 28
- (594823321, 6), // 29
- (729000000, 6), // 30
- (887503681, 6), // 31
- (0, 0), // 32
- (1291467969, 6), // 33
- (1544804416, 6), // 34
- (1838265625, 6), // 35
- (2176782336, 6), // 36
- (2565726409, 6), // 37
- (3010936384, 6), // 38
- (3518743761, 6), // 39
- (4096000000, 6), // 40
- (115856201, 5), // 41
- (130691232, 5), // 42
- (147008443, 5), // 43
- (164916224, 5), // 44
- (184528125, 5), // 45
- (205962976, 5), // 46
- (229345007, 5), // 47
- (254803968, 5), // 48
- (282475249, 5), // 49
- (312500000, 5), // 50
- (345025251, 5), // 51
- (380204032, 5), // 52
- (418195493, 5), // 53
- (459165024, 5), // 54
- (503284375, 5), // 55
- (550731776, 5), // 56
- (601692057, 5), // 57
- (656356768, 5), // 58
- (714924299, 5), // 59
- (777600000, 5), // 60
- (844596301, 5), // 61
- (916132832, 5), // 62
- (992436543, 5), // 63
- (0, 0), // 64
- (1160290625, 5), // 65
- (1252332576, 5), // 66
- (1350125107, 5), // 67
- (1453933568, 5), // 68
- (1564031349, 5), // 69
- (1680700000, 5), // 70
- (1804229351, 5), // 71
- (1934917632, 5), // 72
- (2073071593, 5), // 73
- (2219006624, 5), // 74
- (2373046875, 5), // 75
- (2535525376, 5), // 76
- (2706784157, 5), // 77
- (2887174368, 5), // 78
- (3077056399, 5), // 79
- (3276800000, 5), // 80
- (3486784401, 5), // 81
- (3707398432, 5), // 82
- (3939040643, 5), // 83
- (4182119424, 5), // 84
- (52200625, 4), // 85
- (54700816, 4), // 86
- (57289761, 4), // 87
- (59969536, 4), // 88
- (62742241, 4), // 89
- (65610000, 4), // 90
- (68574961, 4), // 91
- (71639296, 4), // 92
- (74805201, 4), // 93
- (78074896, 4), // 94
- (81450625, 4), // 95
- (84934656, 4), // 96
- (88529281, 4), // 97
- (92236816, 4), // 98
- (96059601, 4), // 99
- (100000000, 4), // 100
- (104060401, 4), // 101
- (108243216, 4), // 102
- (112550881, 4), // 103
- (116985856, 4), // 104
- (121550625, 4), // 105
- (126247696, 4), // 106
- (131079601, 4), // 107
- (136048896, 4), // 108
- (141158161, 4), // 109
- (146410000, 4), // 110
- (151807041, 4), // 111
- (157351936, 4), // 112
- (163047361, 4), // 113
- (168896016, 4), // 114
- (174900625, 4), // 115
- (181063936, 4), // 116
- (187388721, 4), // 117
- (193877776, 4), // 118
- (200533921, 4), // 119
- (207360000, 4), // 120
- (214358881, 4), // 121
- (221533456, 4), // 122
- (228886641, 4), // 123
- (236421376, 4), // 124
- (244140625, 4), // 125
- (252047376, 4), // 126
- (260144641, 4), // 127
- (0, 0), // 128
- (276922881, 4), // 129
- (285610000, 4), // 130
- (294499921, 4), // 131
- (303595776, 4), // 132
- (312900721, 4), // 133
- (322417936, 4), // 134
- (332150625, 4), // 135
- (342102016, 4), // 136
- (352275361, 4), // 137
- (362673936, 4), // 138
- (373301041, 4), // 139
- (384160000, 4), // 140
- (395254161, 4), // 141
- (406586896, 4), // 142
- (418161601, 4), // 143
- (429981696, 4), // 144
- (442050625, 4), // 145
- (454371856, 4), // 146
- (466948881, 4), // 147
- (479785216, 4), // 148
- (492884401, 4), // 149
- (506250000, 4), // 150
- (519885601, 4), // 151
- (533794816, 4), // 152
- (547981281, 4), // 153
- (562448656, 4), // 154
- (577200625, 4), // 155
- (592240896, 4), // 156
- (607573201, 4), // 157
- (623201296, 4), // 158
- (639128961, 4), // 159
- (655360000, 4), // 160
- (671898241, 4), // 161
- (688747536, 4), // 162
- (705911761, 4), // 163
- (723394816, 4), // 164
- (741200625, 4), // 165
- (759333136, 4), // 166
- (777796321, 4), // 167
- (796594176, 4), // 168
- (815730721, 4), // 169
- (835210000, 4), // 170
- (855036081, 4), // 171
- (875213056, 4), // 172
- (895745041, 4), // 173
- (916636176, 4), // 174
- (937890625, 4), // 175
- (959512576, 4), // 176
- (981506241, 4), // 177
- (1003875856, 4), // 178
- (1026625681, 4), // 179
- (1049760000, 4), // 180
- (1073283121, 4), // 181
- (1097199376, 4), // 182
- (1121513121, 4), // 183
- (1146228736, 4), // 184
- (1171350625, 4), // 185
- (1196883216, 4), // 186
- (1222830961, 4), // 187
- (1249198336, 4), // 188
- (1275989841, 4), // 189
- (1303210000, 4), // 190
- (1330863361, 4), // 191
- (1358954496, 4), // 192
- (1387488001, 4), // 193
- (1416468496, 4), // 194
- (1445900625, 4), // 195
- (1475789056, 4), // 196
- (1506138481, 4), // 197
- (1536953616, 4), // 198
- (1568239201, 4), // 199
- (1600000000, 4), // 200
- (1632240801, 4), // 201
- (1664966416, 4), // 202
- (1698181681, 4), // 203
- (1731891456, 4), // 204
- (1766100625, 4), // 205
- (1800814096, 4), // 206
- (1836036801, 4), // 207
- (1871773696, 4), // 208
- (1908029761, 4), // 209
- (1944810000, 4), // 210
- (1982119441, 4), // 211
- (2019963136, 4), // 212
- (2058346161, 4), // 213
- (2097273616, 4), // 214
- (2136750625, 4), // 215
- (2176782336, 4), // 216
- (2217373921, 4), // 217
- (2258530576, 4), // 218
- (2300257521, 4), // 219
- (2342560000, 4), // 220
- (2385443281, 4), // 221
- (2428912656, 4), // 222
- (2472973441, 4), // 223
- (2517630976, 4), // 224
- (2562890625, 4), // 225
- (2608757776, 4), // 226
- (2655237841, 4), // 227
- (2702336256, 4), // 228
- (2750058481, 4), // 229
- (2798410000, 4), // 230
- (2847396321, 4), // 231
- (2897022976, 4), // 232
- (2947295521, 4), // 233
- (2998219536, 4), // 234
- (3049800625, 4), // 235
- (3102044416, 4), // 236
- (3154956561, 4), // 237
- (3208542736, 4), // 238
- (3262808641, 4), // 239
- (3317760000, 4), // 240
- (3373402561, 4), // 241
- (3429742096, 4), // 242
- (3486784401, 4), // 243
- (3544535296, 4), // 244
- (3603000625, 4), // 245
- (3662186256, 4), // 246
- (3722098081, 4), // 247
- (3782742016, 4), // 248
- (3844124001, 4), // 249
- (3906250000, 4), // 250
- (3969126001, 4), // 251
- (4032758016, 4), // 252
- (4097152081, 4), // 253
- (4162314256, 4), // 254
- (4228250625, 4), // 255
- (0, 0), // 256
-];
-#[deny(overflowing_literals)]
-pub(crate) static BASES_64: [(u64, usize); 257] = [
- (0, 0), // 0
- (0, 0), // 1
- (0, 0), // 2
- (12157665459056928801, 40), // 3
- (0, 0), // 4
- (7450580596923828125, 27), // 5
- (4738381338321616896, 24), // 6
- (3909821048582988049, 22), // 7
- (0, 0), // 8
- (12157665459056928801, 20), // 9
- (10000000000000000000, 19), // 10
- (5559917313492231481, 18), // 11
- (2218611106740436992, 17), // 12
- (8650415919381337933, 17), // 13
- (2177953337809371136, 16), // 14
- (6568408355712890625, 16), // 15
- (0, 0), // 16
- (2862423051509815793, 15), // 17
- (6746640616477458432, 15), // 18
- (15181127029874798299, 15), // 19
- (1638400000000000000, 14), // 20
- (3243919932521508681, 14), // 21
- (6221821273427820544, 14), // 22
- (11592836324538749809, 14), // 23
- (876488338465357824, 13), // 24
- (1490116119384765625, 13), // 25
- (2481152873203736576, 13), // 26
- (4052555153018976267, 13), // 27
- (6502111422497947648, 13), // 28
- (10260628712958602189, 13), // 29
- (15943230000000000000, 13), // 30
- (787662783788549761, 12), // 31
- (0, 0), // 32
- (1667889514952984961, 12), // 33
- (2386420683693101056, 12), // 34
- (3379220508056640625, 12), // 35
- (4738381338321616896, 12), // 36
- (6582952005840035281, 12), // 37
- (9065737908494995456, 12), // 38
- (12381557655576425121, 12), // 39
- (16777216000000000000, 12), // 40
- (550329031716248441, 11), // 41
- (717368321110468608, 11), // 42
- (929293739471222707, 11), // 43
- (1196683881290399744, 11), // 44
- (1532278301220703125, 11), // 45
- (1951354384207722496, 11), // 46
- (2472159215084012303, 11), // 47
- (3116402981210161152, 11), // 48
- (3909821048582988049, 11), // 49
- (4882812500000000000, 11), // 50
- (6071163615208263051, 11), // 51
- (7516865509350965248, 11), // 52
- (9269035929372191597, 11), // 53
- (11384956040305711104, 11), // 54
- (13931233916552734375, 11), // 55
- (16985107389382393856, 11), // 56
- (362033331456891249, 10), // 57
- (430804206899405824, 10), // 58
- (511116753300641401, 10), // 59
- (604661760000000000, 10), // 60
- (713342911662882601, 10), // 61
- (839299365868340224, 10), // 62
- (984930291881790849, 10), // 63
- (0, 0), // 64
- (1346274334462890625, 10), // 65
- (1568336880910795776, 10), // 66
- (1822837804551761449, 10), // 67
- (2113922820157210624, 10), // 68
- (2446194060654759801, 10), // 69
- (2824752490000000000, 10), // 70
- (3255243551009881201, 10), // 71
- (3743906242624487424, 10), // 72
- (4297625829703557649, 10), // 73
- (4923990397355877376, 10), // 74
- (5631351470947265625, 10), // 75
- (6428888932339941376, 10), // 76
- (7326680472586200649, 10), // 77
- (8335775831236199424, 10), // 78
- (9468276082626847201, 10), // 79
- (10737418240000000000, 10), // 80
- (12157665459056928801, 10), // 81
- (13744803133596058624, 10), // 82
- (15516041187205853449, 10), // 83
- (17490122876598091776, 10), // 84
- (231616946283203125, 9), // 85
- (257327417311663616, 9), // 86
- (285544154243029527, 9), // 87
- (316478381828866048, 9), // 88
- (350356403707485209, 9), // 89
- (387420489000000000, 9), // 90
- (427929800129788411, 9), // 91
- (472161363286556672, 9), // 92
- (520411082988487293, 9), // 93
- (572994802228616704, 9), // 94
- (630249409724609375, 9), // 95
- (692533995824480256, 9), // 96
- (760231058654565217, 9), // 97
- (833747762130149888, 9), // 98
- (913517247483640899, 9), // 99
- (1000000000000000000, 9), // 100
- (1093685272684360901, 9), // 101
- (1195092568622310912, 9), // 102
- (1304773183829244583, 9), // 103
- (1423311812421484544, 9), // 104
- (1551328215978515625, 9), // 105
- (1689478959002692096, 9), // 106
- (1838459212420154507, 9), // 107
- (1999004627104432128, 9), // 108
- (2171893279442309389, 9), // 109
- (2357947691000000000, 9), // 110
- (2558036924386500591, 9), // 111
- (2773078757450186752, 9), // 112
- (3004041937984268273, 9), // 113
- (3251948521156637184, 9), // 114
- (3517876291919921875, 9), // 115
- (3802961274698203136, 9), // 116
- (4108400332687853397, 9), // 117
- (4435453859151328768, 9), // 118
- (4785448563124474679, 9), // 119
- (5159780352000000000, 9), // 120
- (5559917313492231481, 9), // 121
- (5987402799531080192, 9), // 122
- (6443858614676334363, 9), // 123
- (6930988311686938624, 9), // 124
- (7450580596923828125, 9), // 125
- (8004512848309157376, 9), // 126
- (8594754748609397887, 9), // 127
- (0, 0), // 128
- (9892530380752880769, 9), // 129
- (10604499373000000000, 9), // 130
- (11361656654439817571, 9), // 131
- (12166492167065567232, 9), // 132
- (13021612539908538853, 9), // 133
- (13929745610903012864, 9), // 134
- (14893745087865234375, 9), // 135
- (15916595351771938816, 9), // 136
- (17001416405572203977, 9), // 137
- (18151468971815029248, 9), // 138
- (139353667211683681, 8), // 139
- (147578905600000000, 8), // 140
- (156225851787813921, 8), // 141
- (165312903998914816, 8), // 142
- (174859124550883201, 8), // 143
- (184884258895036416, 8), // 144
- (195408755062890625, 8), // 145
- (206453783524884736, 8), // 146
- (218041257467152161, 8), // 147
- (230193853492166656, 8), // 148
- (242935032749128801, 8), // 149
- (256289062500000000, 8), // 150
- (270281038127131201, 8), // 151
- (284936905588473856, 8), // 152
- (300283484326400961, 8), // 153
- (316348490636206336, 8), // 154
- (333160561500390625, 8), // 155
- (350749278894882816, 8), // 156
- (369145194573386401, 8), // 157
- (388379855336079616, 8), // 158
- (408485828788939521, 8), // 159
- (429496729600000000, 8), // 160
- (451447246258894081, 8), // 161
- (474373168346071296, 8), // 162
- (498311414318121121, 8), // 163
- (523300059815673856, 8), // 164
- (549378366500390625, 8), // 165
- (576586811427594496, 8), // 166
- (604967116961135041, 8), // 167
- (634562281237118976, 8), // 168
- (665416609183179841, 8), // 169
- (697575744100000000, 8), // 170
- (731086699811838561, 8), // 171
- (765997893392859136, 8), // 172
- (802359178476091681, 8), // 173
- (840221879151902976, 8), // 174
- (879638824462890625, 8), // 175
- (920664383502155776, 8), // 176
- (963354501121950081, 8), // 177
- (1007766734259732736, 8), // 178
- (1053960288888713761, 8), // 179
- (1101996057600000000, 8), // 180
- (1151936657823500641, 8), // 181
- (1203846470694789376, 8), // 182
- (1257791680575160641, 8), // 183
- (1313840315232157696, 8), // 184
- (1372062286687890625, 8), // 185
- (1432529432742502656, 8), // 186
- (1495315559180183521, 8), // 187
- (1560496482665168896, 8), // 188
- (1628150074335205281, 8), // 189
- (1698356304100000000, 8), // 190
- (1771197285652216321, 8), // 191
- (1846757322198614016, 8), // 192
- (1925122952918976001, 8), // 193
- (2006383000160502016, 8), // 194
- (2090628617375390625, 8), // 195
- (2177953337809371136, 8), // 196
- (2268453123948987361, 8), // 197
- (2362226417735475456, 8), // 198
- (2459374191553118401, 8), // 199
- (2560000000000000000, 8), // 200
- (2664210032449121601, 8), // 201
- (2772113166407885056, 8), // 202
- (2883821021683985761, 8), // 203
- (2999448015365799936, 8), // 204
- (3119111417625390625, 8), // 205
- (3242931408352297216, 8), // 206
- (3371031134626313601, 8), // 207
- (3503536769037500416, 8), // 208
- (3640577568861717121, 8), // 209
- (3782285936100000000, 8), // 210
- (3928797478390152481, 8), // 211
- (4080251070798954496, 8), // 212
- (4236788918503437921, 8), // 213
- (4398556620369715456, 8), // 214
- (4565703233437890625, 8), // 215
- (4738381338321616896, 8), // 216
- (4916747105530914241, 8), // 217
- (5100960362726891776, 8), // 218
- (5291184662917065441, 8), // 219
- (5487587353600000000, 8), // 220
- (5690339646868044961, 8), // 221
- (5899616690476974336, 8), // 222
- (6115597639891380481, 8), // 223
- (6338465731314712576, 8), // 224
- (6568408355712890625, 8), // 225
- (6805617133840466176, 8), // 226
- (7050287992278341281, 8), // 227
- (7302621240492097536, 8), // 228
- (7562821648920027361, 8), // 229
- (7831098528100000000, 8), // 230
- (8107665808844335041, 8), // 231
- (8392742123471896576, 8), // 232
- (8686550888106661441, 8), // 233
- (8989320386052055296, 8), // 234
- (9301283852250390625, 8), // 235
- (9622679558836781056, 8), // 236
- (9953750901796946721, 8), // 237
- (10294746488738365696, 8), // 238
- (10645920227784266881, 8), // 239
- (11007531417600000000, 8), // 240
- (11379844838561358721, 8), // 241
- (11763130845074473216, 8), // 242
- (12157665459056928801, 8), // 243
- (12563730464589807616, 8), // 244
- (12981613503750390625, 8), // 245
- (13411608173635297536, 8), // 246
- (13854014124583882561, 8), // 247
- (14309137159611744256, 8), // 248
- (14777289335064248001, 8), // 249
- (15258789062500000000, 8), // 250
- (15753961211814252001, 8), // 251
- (16263137215612256256, 8), // 252
- (16786655174842630561, 8), // 253
- (17324859965700833536, 8), // 254
- (17878103347812890625, 8), // 255
- (0, 0), // 256
-];
diff --git a/crates/num-bigint/patches/pin-autocfg-version.patch b/crates/num-bigint/patches/pin-autocfg-version.patch
deleted file mode 100644
index 7930756..0000000
--- a/crates/num-bigint/patches/pin-autocfg-version.patch
+++ /dev/null
@@ -1,16 +0,0 @@
-diff --git a/Cargo.toml b/Cargo.toml
-index 2656b5f..159937f 100644
---- a/Cargo.toml
-+++ b/Cargo.toml
-@@ -93,7 +93,10 @@ optional = true
- default-features = false
-
- [build-dependencies.autocfg]
--version = "1"
-+# autocfg 1.4 uses different, non-deterministic filenames. We don't
-+# actually depend on these files, but they are present in the out/
-+# directory, and it's simpler to keep them around.
-+version = "=1.1.0"
-
- [features]
- default = ["std"]
diff --git a/crates/num-bigint/patches/remove-probe-files.patch b/crates/num-bigint/patches/remove-probe-files.patch
deleted file mode 100644
index 0292603..0000000
--- a/crates/num-bigint/patches/remove-probe-files.patch
+++ /dev/null
@@ -1,20 +0,0 @@
-diff --git a/build.rs b/build.rs
-index 5d5406c..82b7a43 100644
---- a/build.rs
-+++ b/build.rs
-@@ -37,6 +37,15 @@ fn main() {
- }
- }
-
-+ // autocfg generates probe files in $OUT_DIR with nondeterministic contents.
-+ // (In autocfg 1.4, the filenames are nondeterministic as well.)
-+ let out_dir_env = env::var("OUT_DIR").unwrap();
-+ let out_dir = Path::new(&out_dir_env);
-+ std::fs::remove_file(out_dir.join("probe0.ll")).unwrap();
-+ std::fs::remove_file(out_dir.join("probe1.ll")).unwrap();
-+ std::fs::remove_file(out_dir.join("probe2.ll")).unwrap();
-+ std::fs::remove_file(out_dir.join("probe3.ll")).unwrap();
-+
- autocfg::rerun_path("build.rs");
-
- write_radix_bases().unwrap();
diff --git a/crates/num-bigint/src/bigint.rs b/crates/num-bigint/src/bigint.rs
index 97faa83..b4f84b9 100644
--- a/crates/num-bigint/src/bigint.rs
+++ b/crates/num-bigint/src/bigint.rs
@@ -1,18 +1,17 @@
// `Add`/`Sub` ops may flip from `BigInt` to its `BigUint` magnitude
#![allow(clippy::suspicious_arithmetic_impl)]
-use crate::std_alloc::{String, Vec};
+use alloc::string::String;
+use alloc::vec::Vec;
use core::cmp::Ordering::{self, Equal};
use core::default::Default;
use core::fmt;
use core::hash;
use core::ops::{Neg, Not};
use core::str;
-use core::{i128, u128};
-use core::{i64, u64};
use num_integer::{Integer, Roots};
-use num_traits::{Num, One, Pow, Signed, Zero};
+use num_traits::{ConstZero, Num, One, Pow, Signed, Zero};
use self::Sign::{Minus, NoSign, Plus};
@@ -25,16 +24,12 @@
mod multiplication;
mod subtraction;
+mod arbitrary;
mod bits;
mod convert;
mod power;
-mod shift;
-
-#[cfg(any(feature = "quickcheck", feature = "arbitrary"))]
-mod arbitrary;
-
-#[cfg(feature = "serde")]
mod serde;
+mod shift;
/// A `Sign` is a [`BigInt`]'s composing element.
#[derive(PartialEq, PartialOrd, Eq, Ord, Copy, Clone, Debug, Hash)]
@@ -132,7 +127,7 @@
impl Default for BigInt {
#[inline]
fn default() -> BigInt {
- Zero::zero()
+ Self::ZERO
}
}
@@ -211,10 +206,7 @@
impl Zero for BigInt {
#[inline]
fn zero() -> BigInt {
- BigInt {
- sign: NoSign,
- data: BigUint::zero(),
- }
+ Self::ZERO
}
#[inline]
@@ -229,6 +221,11 @@
}
}
+impl ConstZero for BigInt {
+ // forward to the inherent const
+ const ZERO: Self = Self::ZERO;
+}
+
impl One for BigInt {
#[inline]
fn one() -> BigInt {
@@ -262,7 +259,7 @@
#[inline]
fn abs_sub(&self, other: &BigInt) -> BigInt {
if *self <= *other {
- Zero::zero()
+ Self::ZERO
} else {
self - other
}
@@ -273,7 +270,7 @@
match self.sign {
Plus => BigInt::one(),
Minus => -BigInt::one(),
- NoSign => BigInt::zero(),
+ NoSign => Self::ZERO,
}
}
@@ -291,10 +288,6 @@
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>
- fn uabs(self) -> Self::Unsigned;
-
fn checked_uabs(self) -> CheckedUnsignedAbs<Self::Unsigned>;
}
@@ -310,11 +303,6 @@
type Unsigned = $Unsigned;
#[inline]
- fn uabs(self) -> $Unsigned {
- self.wrapping_abs() as $Unsigned
- }
-
- #[inline]
fn checked_uabs(self) -> CheckedUnsignedAbs<Self::Unsigned> {
if self >= 0 {
Positive(self as $Unsigned)
@@ -462,7 +450,7 @@
fn extended_gcd_lcm(&self, other: &BigInt) -> (num_integer::ExtendedGcd<BigInt>, BigInt) {
let egcd = self.extended_gcd(other);
let lcm = if egcd.gcd.is_zero() {
- BigInt::zero()
+ Self::ZERO
} else {
BigInt::from(&self.data / &egcd.gcd.data * &other.data)
};
@@ -508,6 +496,14 @@
fn prev_multiple_of(&self, other: &Self) -> Self {
self - self.mod_floor(other)
}
+
+ fn dec(&mut self) {
+ *self -= 1u32;
+ }
+
+ fn inc(&mut self) {
+ *self += 1u32;
+ }
}
impl Roots for BigInt {
@@ -567,6 +563,12 @@
}
impl BigInt {
+ /// A constant `BigInt` with value 0, useful for static initialization.
+ pub const ZERO: Self = BigInt {
+ sign: NoSign,
+ data: BigUint::ZERO,
+ };
+
/// Creates and initializes a [`BigInt`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
@@ -922,11 +924,10 @@
///
/// ```
/// use num_bigint::{BigInt, Sign};
- /// use num_traits::Zero;
///
/// assert_eq!(BigInt::from(1234).sign(), Sign::Plus);
/// assert_eq!(BigInt::from(-4321).sign(), Sign::Minus);
- /// assert_eq!(BigInt::zero().sign(), Sign::NoSign);
+ /// assert_eq!(BigInt::ZERO.sign(), Sign::NoSign);
/// ```
#[inline]
pub fn sign(&self) -> Sign {
@@ -943,7 +944,7 @@
///
/// assert_eq!(BigInt::from(1234).magnitude(), &BigUint::from(1234u32));
/// assert_eq!(BigInt::from(-4321).magnitude(), &BigUint::from(4321u32));
- /// assert!(BigInt::zero().magnitude().is_zero());
+ /// assert!(BigInt::ZERO.magnitude().is_zero());
/// ```
#[inline]
pub fn magnitude(&self) -> &BigUint {
@@ -957,11 +958,10 @@
///
/// ```
/// use num_bigint::{BigInt, BigUint, Sign};
- /// use num_traits::Zero;
///
/// assert_eq!(BigInt::from(1234).into_parts(), (Sign::Plus, BigUint::from(1234u32)));
/// assert_eq!(BigInt::from(-4321).into_parts(), (Sign::Minus, BigUint::from(4321u32)));
- /// assert_eq!(BigInt::zero().into_parts(), (Sign::NoSign, BigUint::zero()));
+ /// assert_eq!(BigInt::ZERO.into_parts(), (Sign::NoSign, BigUint::ZERO));
/// ```
#[inline]
pub fn into_parts(self) -> (Sign, BigUint) {
@@ -980,7 +980,7 @@
pub fn to_biguint(&self) -> Option<BigUint> {
match self.sign {
Plus => Some(self.data.clone()),
- NoSign => Some(Zero::zero()),
+ NoSign => Some(BigUint::ZERO),
Minus => None,
}
}
@@ -1025,6 +1025,64 @@
power::modpow(self, exponent, modulus)
}
+ /// Returns the modular multiplicative inverse if it exists, otherwise `None`.
+ ///
+ /// This solves for `x` such that `self * x ≡ 1 (mod modulus)`.
+ /// Note that this rounds like `mod_floor`, not like the `%` operator,
+ /// which makes a difference when given a negative `self` or `modulus`.
+ /// The solution will be in the interval `[0, modulus)` for `modulus > 0`,
+ /// or in the interval `(modulus, 0]` for `modulus < 0`,
+ /// and it exists if and only if `gcd(self, modulus) == 1`.
+ ///
+ /// ```
+ /// use num_bigint::BigInt;
+ /// use num_integer::Integer;
+ /// use num_traits::{One, Zero};
+ ///
+ /// let m = BigInt::from(383);
+ ///
+ /// // Trivial cases
+ /// assert_eq!(BigInt::zero().modinv(&m), None);
+ /// assert_eq!(BigInt::one().modinv(&m), Some(BigInt::one()));
+ /// let neg1 = &m - 1u32;
+ /// assert_eq!(neg1.modinv(&m), Some(neg1));
+ ///
+ /// // Positive self and modulus
+ /// let a = BigInt::from(271);
+ /// let x = a.modinv(&m).unwrap();
+ /// assert_eq!(x, BigInt::from(106));
+ /// assert_eq!(x.modinv(&m).unwrap(), a);
+ /// assert_eq!((&a * x).mod_floor(&m), BigInt::one());
+ ///
+ /// // Negative self and positive modulus
+ /// let b = -&a;
+ /// let x = b.modinv(&m).unwrap();
+ /// assert_eq!(x, BigInt::from(277));
+ /// assert_eq!((&b * x).mod_floor(&m), BigInt::one());
+ ///
+ /// // Positive self and negative modulus
+ /// let n = -&m;
+ /// let x = a.modinv(&n).unwrap();
+ /// assert_eq!(x, BigInt::from(-277));
+ /// assert_eq!((&a * x).mod_floor(&n), &n + 1);
+ ///
+ /// // Negative self and modulus
+ /// let x = b.modinv(&n).unwrap();
+ /// assert_eq!(x, BigInt::from(-106));
+ /// assert_eq!((&b * x).mod_floor(&n), &n + 1);
+ /// ```
+ pub fn modinv(&self, modulus: &Self) -> Option<Self> {
+ let result = self.data.modinv(&modulus.data)?;
+ // The sign of the result follows the modulus, like `mod_floor`.
+ let (sign, mag) = match (self.is_negative(), modulus.is_negative()) {
+ (false, false) => (Plus, result),
+ (true, false) => (Plus, &modulus.data - result),
+ (false, true) => (Minus, &modulus.data - result),
+ (true, true) => (Minus, result),
+ };
+ Some(BigInt::from_biguint(sign, mag))
+ }
+
/// Returns the truncated principal square root of `self` --
/// see [`num_integer::Roots::sqrt()`].
pub fn sqrt(&self) -> Self {
diff --git a/crates/num-bigint/src/bigint/addition.rs b/crates/num-bigint/src/bigint/addition.rs
index 76aeb99..0d3a0e2 100644
--- a/crates/num-bigint/src/bigint/addition.rs
+++ b/crates/num-bigint/src/bigint/addition.rs
@@ -8,7 +8,7 @@
use core::iter::Sum;
use core::mem;
use core::ops::{Add, AddAssign};
-use num_traits::{CheckedAdd, Zero};
+use num_traits::CheckedAdd;
// We want to forward to BigUint::add, but it's not clear how that will go until
// we compare both sign and magnitude. So we duplicate this body for every
@@ -24,7 +24,7 @@
(Plus, Minus) | (Minus, Plus) => match $a.data.cmp(&$b.data) {
Less => BigInt::from_biguint($b.sign, $b_data - $a_data),
Greater => BigInt::from_biguint($a.sign, $a_data - $b_data),
- Equal => Zero::zero(),
+ Equal => BigInt::ZERO,
},
}
};
@@ -76,7 +76,7 @@
impl AddAssign<&BigInt> for BigInt {
#[inline]
fn add_assign(&mut self, other: &BigInt) {
- let n = mem::replace(self, BigInt::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n + other;
}
}
@@ -97,7 +97,7 @@
NoSign => From::from(other),
Plus => BigInt::from(self.data + other),
Minus => match self.data.cmp(&From::from(other)) {
- Equal => Zero::zero(),
+ Equal => Self::ZERO,
Less => BigInt::from(other - self.data),
Greater => -BigInt::from(self.data - other),
},
@@ -108,7 +108,7 @@
impl AddAssign<u32> for BigInt {
#[inline]
fn add_assign(&mut self, other: u32) {
- let n = mem::replace(self, BigInt::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n + other;
}
}
@@ -122,7 +122,7 @@
NoSign => From::from(other),
Plus => BigInt::from(self.data + other),
Minus => match self.data.cmp(&From::from(other)) {
- Equal => Zero::zero(),
+ Equal => Self::ZERO,
Less => BigInt::from(other - self.data),
Greater => -BigInt::from(self.data - other),
},
@@ -133,7 +133,7 @@
impl AddAssign<u64> for BigInt {
#[inline]
fn add_assign(&mut self, other: u64) {
- let n = mem::replace(self, BigInt::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n + other;
}
}
@@ -147,7 +147,7 @@
NoSign => BigInt::from(other),
Plus => BigInt::from(self.data + other),
Minus => match self.data.cmp(&From::from(other)) {
- Equal => BigInt::zero(),
+ Equal => Self::ZERO,
Less => BigInt::from(other - self.data),
Greater => -BigInt::from(self.data - other),
},
@@ -157,7 +157,7 @@
impl AddAssign<u128> for BigInt {
#[inline]
fn add_assign(&mut self, other: u128) {
- let n = mem::replace(self, BigInt::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n + other;
}
}
diff --git a/crates/num-bigint/src/bigint/arbitrary.rs b/crates/num-bigint/src/bigint/arbitrary.rs
index df66050..3cb90b3 100644
--- a/crates/num-bigint/src/bigint/arbitrary.rs
+++ b/crates/num-bigint/src/bigint/arbitrary.rs
@@ -1,10 +1,13 @@
-use super::{BigInt, Sign};
+#![cfg(any(feature = "quickcheck", feature = "arbitrary"))]
-#[cfg(feature = "quickcheck")]
-use crate::std_alloc::Box;
+use super::{BigInt, Sign};
use crate::BigUint;
#[cfg(feature = "quickcheck")]
+use alloc::boxed::Box;
+
+#[cfg(feature = "quickcheck")]
+#[cfg_attr(docsrs, doc(cfg(feature = "quickcheck")))]
impl quickcheck::Arbitrary for BigInt {
fn arbitrary(g: &mut quickcheck::Gen) -> Self {
let positive = bool::arbitrary(g);
@@ -20,6 +23,7 @@
}
#[cfg(feature = "arbitrary")]
+#[cfg_attr(docsrs, doc(cfg(feature = "arbitrary")))]
impl arbitrary::Arbitrary<'_> for BigInt {
fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
let positive = bool::arbitrary(u)?;
diff --git a/crates/num-bigint/src/bigint/bits.rs b/crates/num-bigint/src/bigint/bits.rs
index 80f4e2c..ac4fe1d 100644
--- a/crates/num-bigint/src/bigint/bits.rs
+++ b/crates/num-bigint/src/bigint/bits.rs
@@ -3,8 +3,8 @@
use crate::big_digit::{self, BigDigit, DoubleBigDigit};
use crate::biguint::IntDigits;
-use crate::std_alloc::Vec;
+use alloc::vec::Vec;
use core::cmp::Ordering::{Equal, Greater, Less};
use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign};
use num_traits::{ToPrimitive, Zero};
@@ -36,7 +36,7 @@
// + 1 & -ff = ...0 01 & ...f 01 = ...0 01 = + 1
// +ff & - 1 = ...0 ff & ...f ff = ...0 ff = +ff
// answer is pos, has length of a
-fn bitand_pos_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
+fn bitand_pos_neg(a: &mut [BigDigit], b: &[BigDigit]) {
let mut carry_b = 1;
for (ai, &bi) in a.iter_mut().zip(b.iter()) {
let twos_b = negate_carry(bi, &mut carry_b);
@@ -114,7 +114,7 @@
#[inline]
fn bitand(self, other: &BigInt) -> BigInt {
match (self.sign, other.sign) {
- (NoSign, _) | (_, NoSign) => BigInt::zero(),
+ (NoSign, _) | (_, NoSign) => BigInt::ZERO,
(Plus, Plus) => BigInt::from(&self.data & &other.data),
(Plus, Minus) => self.clone() & other,
(Minus, Plus) => other.clone() & self,
@@ -202,7 +202,7 @@
// - 1 | +ff = ...f ff | ...0 ff = ...f ff = - 1
// -ff | + 1 = ...f 01 | ...0 01 = ...f 01 = -ff
// answer is neg, has length of a
-fn bitor_neg_pos(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
+fn bitor_neg_pos(a: &mut [BigDigit], b: &[BigDigit]) {
let mut carry_a = 1;
let mut carry_or = 1;
for (ai, &bi) in a.iter_mut().zip(b.iter()) {
diff --git a/crates/num-bigint/src/bigint/convert.rs b/crates/num-bigint/src/bigint/convert.rs
index c4f888b..d0e28b6 100644
--- a/crates/num-bigint/src/bigint/convert.rs
+++ b/crates/num-bigint/src/bigint/convert.rs
@@ -1,13 +1,11 @@
use super::Sign::{self, Minus, NoSign, Plus};
use super::{BigInt, ToBigInt};
-use crate::std_alloc::Vec;
-#[cfg(has_try_from)]
use crate::TryFromBigIntError;
use crate::{BigUint, ParseBigIntError, ToBigUint};
+use alloc::vec::Vec;
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, One, ToPrimitive, Zero};
@@ -27,8 +25,7 @@
/// Creates and initializes a [`BigInt`].
#[inline]
fn from_str_radix(mut s: &str, radix: u32) -> Result<BigInt, ParseBigIntError> {
- let sign = if s.starts_with('-') {
- let tail = &s[1..];
+ let sign = if let Some(tail) = s.strip_prefix('-') {
if !tail.starts_with('+') {
s = tail
}
@@ -52,7 +49,7 @@
let m: u64 = 1 << 63;
match n.cmp(&m) {
Less => Some(-(n as i64)),
- Equal => Some(core::i64::MIN),
+ Equal => Some(i64::MIN),
Greater => None,
}
}
@@ -69,7 +66,7 @@
let m: u128 = 1 << 127;
match n.cmp(&m) {
Less => Some(-(n as i128)),
- Equal => Some(core::i128::MIN),
+ Equal => Some(i128::MIN),
Greater => None,
}
}
@@ -109,7 +106,6 @@
macro_rules! impl_try_from_bigint {
($T:ty, $to_ty:path) => {
- #[cfg(has_try_from)]
impl TryFrom<&BigInt> for $T {
type Error = TryFromBigIntError<()>;
@@ -119,7 +115,6 @@
}
}
- #[cfg(has_try_from)]
impl TryFrom<BigInt> for $T {
type Error = TryFromBigIntError<BigInt>;
@@ -183,7 +178,7 @@
if n >= 0 {
BigInt::from(n as u64)
} else {
- let u = core::u64::MAX - (n as u64) + 1;
+ let u = u64::MAX - (n as u64) + 1;
BigInt {
sign: Minus,
data: BigUint::from(u),
@@ -198,7 +193,7 @@
if n >= 0 {
BigInt::from(n as u128)
} else {
- let u = core::u128::MAX - (n as u128) + 1;
+ let u = u128::MAX - (n as u128) + 1;
BigInt {
sign: Minus,
data: BigUint::from(u),
@@ -232,7 +227,7 @@
data: BigUint::from(n),
}
} else {
- BigInt::zero()
+ Self::ZERO
}
}
}
@@ -246,7 +241,7 @@
data: BigUint::from(n),
}
} else {
- BigInt::zero()
+ Self::ZERO
}
}
}
@@ -271,7 +266,7 @@
#[inline]
fn from(n: BigUint) -> Self {
if n.is_zero() {
- BigInt::zero()
+ Self::ZERO
} else {
BigInt {
sign: Plus,
@@ -292,7 +287,7 @@
#[inline]
fn to_bigint(&self) -> Option<BigInt> {
if self.is_zero() {
- Some(Zero::zero())
+ Some(BigInt::ZERO)
} else {
Some(BigInt {
sign: Plus,
@@ -307,13 +302,12 @@
fn to_biguint(&self) -> Option<BigUint> {
match self.sign() {
Plus => Some(self.data.clone()),
- NoSign => Some(Zero::zero()),
+ NoSign => Some(BigUint::ZERO),
Minus => None,
}
}
}
-#[cfg(has_try_from)]
impl TryFrom<&BigInt> for BigUint {
type Error = TryFromBigIntError<()>;
@@ -325,7 +319,6 @@
}
}
-#[cfg(has_try_from)]
impl TryFrom<BigInt> for BigUint {
type Error = TryFromBigIntError<BigInt>;
@@ -372,7 +365,7 @@
if x {
One::one()
} else {
- Zero::zero()
+ Self::ZERO
}
}
}
@@ -382,7 +375,7 @@
let sign = match digits.first() {
Some(v) if *v > 0x7f => Sign::Minus,
Some(_) => Sign::Plus,
- None => return BigInt::zero(),
+ None => return BigInt::ZERO,
};
if sign == Sign::Minus {
@@ -400,7 +393,7 @@
let sign = match digits.last() {
Some(v) if *v > 0x7f => Sign::Minus,
Some(_) => Sign::Plus,
- None => return BigInt::zero(),
+ None => return BigInt::ZERO,
};
if sign == Sign::Minus {
diff --git a/crates/num-bigint/src/bigint/division.rs b/crates/num-bigint/src/bigint/division.rs
index 318d1fb..0d4d23f 100644
--- a/crates/num-bigint/src/bigint/division.rs
+++ b/crates/num-bigint/src/bigint/division.rs
@@ -358,14 +358,14 @@
#[inline]
fn rem(self, other: i32) -> BigInt {
- self % other.uabs()
+ self % other.unsigned_abs()
}
}
impl RemAssign<i32> for BigInt {
#[inline]
fn rem_assign(&mut self, other: i32) {
- *self %= other.uabs();
+ *self %= other.unsigned_abs();
}
}
@@ -386,14 +386,14 @@
#[inline]
fn rem(self, other: i64) -> BigInt {
- self % other.uabs()
+ self % other.unsigned_abs()
}
}
impl RemAssign<i64> for BigInt {
#[inline]
fn rem_assign(&mut self, other: i64) {
- *self %= other.uabs();
+ *self %= other.unsigned_abs();
}
}
@@ -414,14 +414,14 @@
#[inline]
fn rem(self, other: i128) -> BigInt {
- self % other.uabs()
+ self % other.unsigned_abs()
}
}
impl RemAssign<i128> for BigInt {
#[inline]
fn rem_assign(&mut self, other: i128) {
- *self %= other.uabs();
+ *self %= other.unsigned_abs();
}
}
@@ -463,6 +463,10 @@
}
Some(self.rem_euclid(v))
}
+
+ fn checked_div_rem_euclid(&self, v: &Self) -> Option<(Self, Self)> {
+ Some(self.div_rem_euclid(v))
+ }
}
impl Euclid for BigInt {
@@ -493,4 +497,17 @@
r
}
}
+
+ fn div_rem_euclid(&self, v: &Self) -> (Self, Self) {
+ let (q, r) = self.div_rem(v);
+ if r.is_negative() {
+ if v.is_positive() {
+ (q - 1, r + v)
+ } else {
+ (q + 1, r - v)
+ }
+ } else {
+ (q, r)
+ }
+ }
}
diff --git a/crates/num-bigint/src/bigint/power.rs b/crates/num-bigint/src/bigint/power.rs
index 4b41f4f..ef254c8 100644
--- a/crates/num-bigint/src/bigint/power.rs
+++ b/crates/num-bigint/src/bigint/power.rs
@@ -80,7 +80,7 @@
let result = x.data.modpow(&exponent.data, &modulus.data);
if result.is_zero() {
- return BigInt::zero();
+ return BigInt::ZERO;
}
// The sign of the result follows the modulus, like `mod_floor`.
diff --git a/crates/num-bigint/src/bigint/serde.rs b/crates/num-bigint/src/bigint/serde.rs
index 5c232f9..6c47692 100644
--- a/crates/num-bigint/src/bigint/serde.rs
+++ b/crates/num-bigint/src/bigint/serde.rs
@@ -1,3 +1,6 @@
+#![cfg(feature = "serde")]
+#![cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+
use super::{BigInt, Sign};
use serde::de::{Error, Unexpected};
diff --git a/crates/num-bigint/src/bigint/subtraction.rs b/crates/num-bigint/src/bigint/subtraction.rs
index 548f314..ef77854 100644
--- a/crates/num-bigint/src/bigint/subtraction.rs
+++ b/crates/num-bigint/src/bigint/subtraction.rs
@@ -7,7 +7,7 @@
use core::cmp::Ordering::{Equal, Greater, Less};
use core::mem;
use core::ops::{Sub, SubAssign};
-use num_traits::{CheckedSub, Zero};
+use num_traits::CheckedSub;
// We want to forward to BigUint::sub, but it's not clear how that will go until
// we compare both sign and magnitude. So we duplicate this body for every
@@ -23,7 +23,7 @@
(Plus, Plus) | (Minus, Minus) => match $a.data.cmp(&$b.data) {
Less => BigInt::from_biguint(-$a.sign, $b_data - $a_data),
Greater => BigInt::from_biguint($a.sign, $a_data - $b_data),
- Equal => Zero::zero(),
+ Equal => BigInt::ZERO,
},
}
};
@@ -75,7 +75,7 @@
impl SubAssign<&BigInt> for BigInt {
#[inline]
fn sub_assign(&mut self, other: &BigInt) {
- let n = mem::replace(self, BigInt::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n - other;
}
}
@@ -96,7 +96,7 @@
NoSign => -BigInt::from(other),
Minus => -BigInt::from(self.data + other),
Plus => match self.data.cmp(&From::from(other)) {
- Equal => Zero::zero(),
+ Equal => Self::ZERO,
Greater => BigInt::from(self.data - other),
Less => -BigInt::from(other - self.data),
},
@@ -106,7 +106,7 @@
impl SubAssign<u32> for BigInt {
#[inline]
fn sub_assign(&mut self, other: u32) {
- let n = mem::replace(self, BigInt::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n - other;
}
}
@@ -147,7 +147,7 @@
NoSign => -BigInt::from(other),
Minus => -BigInt::from(self.data + other),
Plus => match self.data.cmp(&From::from(other)) {
- Equal => Zero::zero(),
+ Equal => Self::ZERO,
Greater => BigInt::from(self.data - other),
Less => -BigInt::from(other - self.data),
},
@@ -158,7 +158,7 @@
impl SubAssign<u64> for BigInt {
#[inline]
fn sub_assign(&mut self, other: u64) {
- let n = mem::replace(self, BigInt::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n - other;
}
}
@@ -172,7 +172,7 @@
NoSign => -BigInt::from(other),
Minus => -BigInt::from(self.data + other),
Plus => match self.data.cmp(&From::from(other)) {
- Equal => Zero::zero(),
+ Equal => Self::ZERO,
Greater => BigInt::from(self.data - other),
Less => -BigInt::from(other - self.data),
},
@@ -183,7 +183,7 @@
impl SubAssign<u128> for BigInt {
#[inline]
fn sub_assign(&mut self, other: u128) {
- let n = mem::replace(self, BigInt::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n - other;
}
}
diff --git a/crates/num-bigint/src/bigrand.rs b/crates/num-bigint/src/bigrand.rs
index ec03224..e5cbacd 100644
--- a/crates/num-bigint/src/bigrand.rs
+++ b/crates/num-bigint/src/bigrand.rs
@@ -1,4 +1,6 @@
//! Randomization of big integers
+#![cfg(feature = "rand")]
+#![cfg_attr(docsrs, doc(cfg(feature = "rand")))]
use rand::distributions::uniform::{SampleBorrow, SampleUniform, UniformSampler};
use rand::prelude::*;
@@ -47,42 +49,42 @@
}
impl<R: Rng + ?Sized> RandBigInt for R {
- #[cfg(not(u64_digit))]
- fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
- let (digits, rem) = bit_size.div_rem(&32);
- let len = (digits + (rem > 0) as u64)
- .to_usize()
- .expect("capacity overflow");
- let mut data = vec![0u32; len];
- gen_bits(self, &mut data, rem);
- biguint_from_vec(data)
- }
-
- #[cfg(u64_digit)]
- fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
- use core::slice;
-
- let (digits, rem) = bit_size.div_rem(&32);
- let len = (digits + (rem > 0) as u64)
- .to_usize()
- .expect("capacity overflow");
- let native_digits = Integer::div_ceil(&bit_size, &64);
- let native_len = native_digits.to_usize().expect("capacity overflow");
- let mut data = vec![0u64; native_len];
- unsafe {
- // Generate bits in a `&mut [u32]` slice for value stability
- let ptr = data.as_mut_ptr() as *mut u32;
- debug_assert!(native_len * 2 >= len);
- let data = slice::from_raw_parts_mut(ptr, len);
- gen_bits(self, data, rem);
+ cfg_digit!(
+ fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
+ let (digits, rem) = bit_size.div_rem(&32);
+ let len = (digits + (rem > 0) as u64)
+ .to_usize()
+ .expect("capacity overflow");
+ let mut data = vec![0u32; len];
+ gen_bits(self, &mut data, rem);
+ biguint_from_vec(data)
}
- #[cfg(target_endian = "big")]
- for digit in &mut data {
- // swap u32 digits into u64 endianness
- *digit = (*digit << 32) | (*digit >> 32);
+
+ fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
+ use core::slice;
+
+ let (digits, rem) = bit_size.div_rem(&32);
+ let len = (digits + (rem > 0) as u64)
+ .to_usize()
+ .expect("capacity overflow");
+ let native_digits = Integer::div_ceil(&bit_size, &64);
+ let native_len = native_digits.to_usize().expect("capacity overflow");
+ let mut data = vec![0u64; native_len];
+ unsafe {
+ // Generate bits in a `&mut [u32]` slice for value stability
+ let ptr = data.as_mut_ptr() as *mut u32;
+ debug_assert!(native_len * 2 >= len);
+ let data = slice::from_raw_parts_mut(ptr, len);
+ gen_bits(self, data, rem);
+ }
+ #[cfg(target_endian = "big")]
+ for digit in &mut data {
+ // swap u32 digits into u64 endianness
+ *digit = (*digit << 32) | (*digit >> 32);
+ }
+ biguint_from_vec(data)
}
- biguint_from_vec(data)
- }
+ );
fn gen_bigint(&mut self, bit_size: u64) -> BigInt {
loop {
diff --git a/crates/num-bigint/src/biguint.rs b/crates/num-bigint/src/biguint.rs
index 1554eb0..196fa32 100644
--- a/crates/num-bigint/src/biguint.rs
+++ b/crates/num-bigint/src/biguint.rs
@@ -1,6 +1,7 @@
use crate::big_digit::{self, BigDigit};
-use crate::std_alloc::{String, Vec};
+use alloc::string::String;
+use alloc::vec::Vec;
use core::cmp;
use core::cmp::Ordering;
use core::default::Default;
@@ -8,28 +9,23 @@
use core::hash;
use core::mem;
use core::str;
-use core::{u32, u64, u8};
use num_integer::{Integer, Roots};
-use num_traits::{Num, One, Pow, ToPrimitive, Unsigned, Zero};
+use num_traits::{ConstZero, Num, One, Pow, ToPrimitive, Unsigned, Zero};
mod addition;
mod division;
mod multiplication;
mod subtraction;
+mod arbitrary;
mod bits;
mod convert;
mod iter;
mod monty;
mod power;
-mod shift;
-
-#[cfg(any(feature = "quickcheck", feature = "arbitrary"))]
-mod arbitrary;
-
-#[cfg(feature = "serde")]
mod serde;
+mod shift;
pub(crate) use self::convert::to_str_radix_reversed;
pub use self::iter::{U32Digits, U64Digits};
@@ -101,7 +97,7 @@
impl Default for BigUint {
#[inline]
fn default() -> BigUint {
- Zero::zero()
+ Self::ZERO
}
}
@@ -146,7 +142,7 @@
impl Zero for BigUint {
#[inline]
fn zero() -> BigUint {
- BigUint { data: Vec::new() }
+ Self::ZERO
}
#[inline]
@@ -160,6 +156,11 @@
}
}
+impl ConstZero for BigUint {
+ // forward to the inherent const
+ const ZERO: Self = Self::ZERO; // BigUint { data: Vec::new() };
+}
+
impl One for BigUint {
#[inline]
fn one() -> BigUint {
@@ -255,7 +256,7 @@
#[inline]
fn lcm(&self, other: &BigUint) -> BigUint {
if self.is_zero() && other.is_zero() {
- Self::zero()
+ Self::ZERO
} else {
self / self.gcd(other) * other
}
@@ -267,7 +268,7 @@
fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
let gcd = self.gcd(other);
let lcm = if gcd.is_zero() {
- Self::zero()
+ Self::ZERO
} else {
self / &gcd * other
};
@@ -320,6 +321,14 @@
fn prev_multiple_of(&self, other: &Self) -> Self {
self - self.mod_floor(other)
}
+
+ fn dec(&mut self) {
+ *self -= 1u32;
+ }
+
+ fn inc(&mut self) {
+ *self += 1u32;
+ }
}
#[inline]
@@ -397,7 +406,7 @@
_ => {
// Try to guess by scaling down such that it does fit in `f64`.
// With some (x * 2ⁿᵏ), its nth root ≈ (ⁿ√x * 2ᵏ)
- let extra_bits = bits - (core::f64::MAX_EXP as u64 - 1);
+ let extra_bits = bits - (f64::MAX_EXP as u64 - 1);
let root_scale = Integer::div_ceil(&extra_bits, &n64);
let scale = root_scale * n64;
if scale < bits && bits - scale > n64 {
@@ -445,7 +454,7 @@
_ => {
// Try to guess by scaling down such that it does fit in `f64`.
// With some (x * 2²ᵏ), its sqrt ≈ (√x * 2ᵏ)
- let extra_bits = bits - (core::f64::MAX_EXP as u64 - 1);
+ let extra_bits = bits - (f64::MAX_EXP as u64 - 1);
let root_scale = (extra_bits + 1) / 2;
let scale = root_scale * 2;
(self >> scale).sqrt() << root_scale
@@ -486,7 +495,7 @@
_ => {
// Try to guess by scaling down such that it does fit in `f64`.
// With some (x * 2³ᵏ), its cbrt ≈ (∛x * 2ᵏ)
- let extra_bits = bits - (core::f64::MAX_EXP as u64 - 1);
+ let extra_bits = bits - (f64::MAX_EXP as u64 - 1);
let root_scale = (extra_bits + 2) / 3;
let scale = root_scale * 3;
(self >> scale).cbrt() << root_scale
@@ -519,21 +528,23 @@
}
impl BigUint {
+ /// A constant `BigUint` with value 0, useful for static initialization.
+ pub const ZERO: Self = BigUint { data: Vec::new() };
+
/// Creates and initializes a [`BigUint`].
///
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
pub fn new(digits: Vec<u32>) -> BigUint {
- let mut big = BigUint::zero();
+ let mut big = Self::ZERO;
- #[cfg(not(u64_digit))]
- {
- big.data = digits;
- big.normalize();
- }
-
- #[cfg(u64_digit)]
- big.assign_from_slice(&digits);
+ cfg_digit_expr!(
+ {
+ big.data = digits;
+ big.normalize();
+ },
+ big.assign_from_slice(&digits)
+ );
big
}
@@ -543,7 +554,7 @@
/// The base 2<sup>32</sup> digits are ordered least significant digit first.
#[inline]
pub fn from_slice(slice: &[u32]) -> BigUint {
- let mut big = BigUint::zero();
+ let mut big = Self::ZERO;
big.assign_from_slice(slice);
big
}
@@ -555,11 +566,10 @@
pub fn assign_from_slice(&mut self, slice: &[u32]) {
self.data.clear();
- #[cfg(not(u64_digit))]
- self.data.extend_from_slice(slice);
-
- #[cfg(u64_digit)]
- self.data.extend(slice.chunks(2).map(u32_chunk_to_u64));
+ cfg_digit_expr!(
+ self.data.extend_from_slice(slice),
+ self.data.extend(slice.chunks(2).map(u32_chunk_to_u64))
+ );
self.normalize();
}
@@ -585,7 +595,7 @@
#[inline]
pub fn from_bytes_be(bytes: &[u8]) -> BigUint {
if bytes.is_empty() {
- Zero::zero()
+ Self::ZERO
} else {
let mut v = bytes.to_vec();
v.reverse();
@@ -599,7 +609,7 @@
#[inline]
pub fn from_bytes_le(bytes: &[u8]) -> BigUint {
if bytes.is_empty() {
- Zero::zero()
+ Self::ZERO
} else {
convert::from_bitwise_digits_le(bytes, 8)
}
@@ -877,6 +887,86 @@
power::modpow(self, exponent, modulus)
}
+ /// Returns the modular multiplicative inverse if it exists, otherwise `None`.
+ ///
+ /// This solves for `x` in the interval `[0, modulus)` such that `self * x ≡ 1 (mod modulus)`.
+ /// The solution exists if and only if `gcd(self, modulus) == 1`.
+ ///
+ /// ```
+ /// use num_bigint::BigUint;
+ /// use num_traits::{One, Zero};
+ ///
+ /// let m = BigUint::from(383_u32);
+ ///
+ /// // Trivial cases
+ /// assert_eq!(BigUint::zero().modinv(&m), None);
+ /// assert_eq!(BigUint::one().modinv(&m), Some(BigUint::one()));
+ /// let neg1 = &m - 1u32;
+ /// assert_eq!(neg1.modinv(&m), Some(neg1));
+ ///
+ /// let a = BigUint::from(271_u32);
+ /// let x = a.modinv(&m).unwrap();
+ /// assert_eq!(x, BigUint::from(106_u32));
+ /// assert_eq!(x.modinv(&m).unwrap(), a);
+ /// assert!((a * x % m).is_one());
+ /// ```
+ pub fn modinv(&self, modulus: &Self) -> Option<Self> {
+ // Based on the inverse pseudocode listed here:
+ // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers
+ // TODO: consider Binary or Lehmer's GCD algorithms for optimization.
+
+ assert!(
+ !modulus.is_zero(),
+ "attempt to calculate with zero modulus!"
+ );
+ if modulus.is_one() {
+ return Some(Self::zero());
+ }
+
+ let mut r0; // = modulus.clone();
+ let mut r1 = self % modulus;
+ let mut t0; // = Self::zero();
+ let mut t1; // = Self::one();
+
+ // Lift and simplify the first iteration to avoid some initial allocations.
+ if r1.is_zero() {
+ return None;
+ } else if r1.is_one() {
+ return Some(r1);
+ } else {
+ let (q, r2) = modulus.div_rem(&r1);
+ if r2.is_zero() {
+ return None;
+ }
+ r0 = r1;
+ r1 = r2;
+ t0 = Self::one();
+ t1 = modulus - q;
+ }
+
+ while !r1.is_zero() {
+ let (q, r2) = r0.div_rem(&r1);
+ r0 = r1;
+ r1 = r2;
+
+ // let t2 = (t0 - q * t1) % modulus;
+ let qt1 = q * &t1 % modulus;
+ let t2 = if t0 < qt1 {
+ t0 + (modulus - qt1)
+ } else {
+ t0 - qt1
+ };
+ t0 = t1;
+ t1 = t2;
+ }
+
+ if r0.is_one() {
+ Some(t0)
+ } else {
+ None
+ }
+ }
+
/// 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)
pub fn sqrt(&self) -> Self {
@@ -906,10 +996,7 @@
/// Returns the number of least-significant bits that are ones.
pub fn trailing_ones(&self) -> u64 {
if let Some(i) = self.data.iter().position(|&digit| !digit != 0) {
- // XXX u64::trailing_ones() introduced in Rust 1.46,
- // but we need to be compatible further back.
- // Thanks to cuviper for this workaround.
- let ones: u64 = (!self.data[i]).trailing_zeros().into();
+ let ones: u64 = self.data[i].trailing_ones().into();
i as u64 * u64::from(big_digit::BITS) + ones
} else {
self.data.len() as u64 * u64::from(big_digit::BITS)
@@ -941,9 +1028,7 @@
// Note: we're saturating `digit_index` and `new_len` -- any such case is guaranteed to
// fail allocation, and that's more consistent than adding our own overflow panics.
let bits_per_digit = u64::from(big_digit::BITS);
- let digit_index = (bit / bits_per_digit)
- .to_usize()
- .unwrap_or(core::usize::MAX);
+ let digit_index = (bit / bits_per_digit).to_usize().unwrap_or(usize::MAX);
let bit_mask = (1 as BigDigit) << (bit % bits_per_digit);
if value {
if digit_index >= self.data.len() {
@@ -1025,86 +1110,77 @@
digit
}
-/// Combine four `u32`s into a single `u128`.
-#[cfg(any(test, not(u64_digit)))]
-#[inline]
-fn u32_to_u128(a: u32, b: u32, c: u32, d: u32) -> u128 {
- u128::from(d) | (u128::from(c) << 32) | (u128::from(b) << 64) | (u128::from(a) << 96)
-}
-
-/// Split a single `u128` into four `u32`.
-#[cfg(any(test, not(u64_digit)))]
-#[inline]
-fn u32_from_u128(n: u128) -> (u32, u32, u32, u32) {
- (
- (n >> 96) as u32,
- (n >> 64) as u32,
- (n >> 32) as u32,
- n as u32,
- )
-}
-
-#[cfg(not(u64_digit))]
-#[test]
-fn test_from_slice() {
- fn check(slice: &[u32], data: &[BigDigit]) {
- assert_eq!(BigUint::from_slice(slice).data, data);
+cfg_32_or_test!(
+ /// Combine four `u32`s into a single `u128`.
+ #[inline]
+ fn u32_to_u128(a: u32, b: u32, c: u32, d: u32) -> u128 {
+ u128::from(d) | (u128::from(c) << 32) | (u128::from(b) << 64) | (u128::from(a) << 96)
}
- check(&[1], &[1]);
- check(&[0, 0, 0], &[]);
- check(&[1, 2, 0, 0], &[1, 2]);
- check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
- check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
- check(&[-1i32 as u32], &[-1i32 as BigDigit]);
-}
+);
-#[cfg(u64_digit)]
-#[test]
-fn test_from_slice() {
- fn check(slice: &[u32], data: &[BigDigit]) {
- assert_eq!(
- BigUint::from_slice(slice).data,
- data,
- "from {:?}, to {:?}",
- slice,
- data
- );
+cfg_32_or_test!(
+ /// Split a single `u128` into four `u32`.
+ #[inline]
+ fn u32_from_u128(n: u128) -> (u32, u32, u32, u32) {
+ (
+ (n >> 96) as u32,
+ (n >> 64) as u32,
+ (n >> 32) as u32,
+ n as u32,
+ )
}
- check(&[1], &[1]);
- check(&[0, 0, 0], &[]);
- check(&[1, 2], &[8_589_934_593]);
- check(&[1, 2, 0, 0], &[8_589_934_593]);
- check(&[0, 0, 1, 2], &[0, 8_589_934_593]);
- check(&[0, 0, 1, 2, 0, 0], &[0, 8_589_934_593]);
- check(&[-1i32 as u32], &[(-1i32 as u32) as BigDigit]);
-}
+);
+
+cfg_digit!(
+ #[test]
+ fn test_from_slice() {
+ fn check(slice: &[u32], data: &[BigDigit]) {
+ assert_eq!(BigUint::from_slice(slice).data, data);
+ }
+ check(&[1], &[1]);
+ check(&[0, 0, 0], &[]);
+ check(&[1, 2, 0, 0], &[1, 2]);
+ check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
+ check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
+ check(&[-1i32 as u32], &[-1i32 as BigDigit]);
+ }
+
+ #[test]
+ fn test_from_slice() {
+ fn check(slice: &[u32], data: &[BigDigit]) {
+ assert_eq!(
+ BigUint::from_slice(slice).data,
+ data,
+ "from {:?}, to {:?}",
+ slice,
+ data
+ );
+ }
+ check(&[1], &[1]);
+ check(&[0, 0, 0], &[]);
+ check(&[1, 2], &[8_589_934_593]);
+ check(&[1, 2, 0, 0], &[8_589_934_593]);
+ check(&[0, 0, 1, 2], &[0, 8_589_934_593]);
+ check(&[0, 0, 1, 2, 0, 0], &[0, 8_589_934_593]);
+ check(&[-1i32 as u32], &[(-1i32 as u32) as BigDigit]);
+ }
+);
#[test]
fn test_u32_u128() {
assert_eq!(u32_from_u128(0u128), (0, 0, 0, 0));
assert_eq!(
- u32_from_u128(u128::max_value()),
- (
- u32::max_value(),
- u32::max_value(),
- u32::max_value(),
- u32::max_value()
- )
+ u32_from_u128(u128::MAX),
+ (u32::MAX, u32::MAX, u32::MAX, u32::MAX)
);
- assert_eq!(
- u32_from_u128(u32::max_value() as u128),
- (0, 0, 0, u32::max_value())
- );
+ assert_eq!(u32_from_u128(u32::MAX as u128), (0, 0, 0, u32::MAX));
+
+ assert_eq!(u32_from_u128(u64::MAX as u128), (0, 0, u32::MAX, u32::MAX));
assert_eq!(
- u32_from_u128(u64::max_value() as u128),
- (0, 0, u32::max_value(), u32::max_value())
- );
-
- assert_eq!(
- u32_from_u128((u64::max_value() as u128) + u32::max_value() as u128),
- (0, 1, 0, u32::max_value() - 1)
+ u32_from_u128((u64::MAX as u128) + u32::MAX as u128),
+ (0, 1, 0, u32::MAX - 1)
);
assert_eq!(u32_from_u128(36_893_488_151_714_070_528), (0, 2, 1, 0));
@@ -1116,11 +1192,11 @@
let values = vec![
0u128,
1u128,
- u64::max_value() as u128 * 3,
- u32::max_value() as u128,
- u64::max_value() as u128,
- (u64::max_value() as u128) + u32::max_value() as u128,
- u128::max_value(),
+ u64::MAX as u128 * 3,
+ u32::MAX as u128,
+ u64::MAX as u128,
+ (u64::MAX as u128) + u32::MAX as u128,
+ u128::MAX,
];
for val in &values {
diff --git a/crates/num-bigint/src/biguint/addition.rs b/crates/num-bigint/src/biguint/addition.rs
index ac6c0dd..b671131 100644
--- a/crates/num-bigint/src/biguint/addition.rs
+++ b/crates/num-bigint/src/biguint/addition.rs
@@ -1,5 +1,3 @@
-#[cfg(not(u64_digit))]
-use super::u32_from_u128;
use super::{BigUint, IntDigits};
use crate::big_digit::{self, BigDigit};
@@ -7,40 +5,44 @@
use core::iter::Sum;
use core::ops::{Add, AddAssign};
-use num_traits::{CheckedAdd, Zero};
+use num_traits::CheckedAdd;
-#[cfg(all(use_addcarry, target_arch = "x86_64"))]
+#[cfg(target_arch = "x86_64")]
use core::arch::x86_64 as arch;
-#[cfg(all(use_addcarry, target_arch = "x86"))]
+#[cfg(target_arch = "x86")]
use core::arch::x86 as arch;
// Add with carry:
-#[cfg(all(use_addcarry, u64_digit))]
-#[inline]
-fn adc(carry: u8, a: u64, b: u64, out: &mut u64) -> u8 {
- // Safety: There are absolutely no safety concerns with calling `_addcarry_u64`.
- // It's just unsafe for API consistency with other intrinsics.
- unsafe { arch::_addcarry_u64(carry, a, b, out) }
-}
+#[cfg(target_arch = "x86_64")]
+cfg_64!(
+ #[inline]
+ fn adc(carry: u8, a: u64, b: u64, out: &mut u64) -> u8 {
+ // Safety: There are absolutely no safety concerns with calling `_addcarry_u64`.
+ // It's just unsafe for API consistency with other intrinsics.
+ unsafe { arch::_addcarry_u64(carry, a, b, out) }
+ }
+);
-#[cfg(all(use_addcarry, not(u64_digit)))]
-#[inline]
-fn adc(carry: u8, a: u32, b: u32, out: &mut u32) -> u8 {
- // Safety: There are absolutely no safety concerns with calling `_addcarry_u32`.
- // It's just unsafe for API consistency with other intrinsics.
- unsafe { arch::_addcarry_u32(carry, a, b, out) }
-}
+#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
+cfg_32!(
+ #[inline]
+ fn adc(carry: u8, a: u32, b: u32, out: &mut u32) -> u8 {
+ // Safety: There are absolutely no safety concerns with calling `_addcarry_u32`.
+ // It's just unsafe for API consistency with other intrinsics.
+ unsafe { arch::_addcarry_u32(carry, a, b, out) }
+ }
+);
// fallback for environments where we don't have an addcarry intrinsic
-#[cfg(not(use_addcarry))]
+// (copied from the standard library's `carrying_add`)
+#[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
#[inline]
-fn adc(carry: u8, a: BigDigit, b: BigDigit, out: &mut BigDigit) -> u8 {
- use crate::big_digit::DoubleBigDigit;
-
- let sum = DoubleBigDigit::from(a) + DoubleBigDigit::from(b) + DoubleBigDigit::from(carry);
- *out = sum as BigDigit;
- (sum >> big_digit::BITS) as u8
+fn adc(carry: u8, lhs: BigDigit, rhs: BigDigit, out: &mut BigDigit) -> u8 {
+ let (a, b) = lhs.overflowing_add(rhs);
+ let (c, d) = a.overflowing_add(carry as BigDigit);
+ *out = c;
+ u8::from(b || d)
}
/// Two argument addition of raw slices, `a += b`, returning the carry.
@@ -154,38 +156,38 @@
}
impl AddAssign<u64> for BigUint {
- #[cfg(not(u64_digit))]
- #[inline]
- fn add_assign(&mut self, other: u64) {
- let (hi, lo) = big_digit::from_doublebigdigit(other);
- if hi == 0 {
- *self += lo;
- } else {
- while self.data.len() < 2 {
- self.data.push(0);
- }
+ cfg_digit!(
+ #[inline]
+ fn add_assign(&mut self, other: u64) {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ if hi == 0 {
+ *self += lo;
+ } else {
+ while self.data.len() < 2 {
+ self.data.push(0);
+ }
- let carry = __add2(&mut self.data, &[lo, hi]);
- if carry != 0 {
- self.data.push(carry);
+ let carry = __add2(&mut self.data, &[lo, hi]);
+ if carry != 0 {
+ self.data.push(carry);
+ }
}
}
- }
- #[cfg(u64_digit)]
- #[inline]
- fn add_assign(&mut self, other: u64) {
- if other != 0 {
- if self.data.is_empty() {
- self.data.push(0);
- }
+ #[inline]
+ fn add_assign(&mut self, other: u64) {
+ if other != 0 {
+ if self.data.is_empty() {
+ self.data.push(0);
+ }
- let carry = __add2(&mut self.data, &[other as BigDigit]);
- if carry != 0 {
- self.data.push(carry);
+ let carry = __add2(&mut self.data, &[other as BigDigit]);
+ if carry != 0 {
+ self.data.push(carry);
+ }
}
}
- }
+ );
}
impl Add<u128> for BigUint {
@@ -199,49 +201,49 @@
}
impl AddAssign<u128> for BigUint {
- #[cfg(not(u64_digit))]
- #[inline]
- fn add_assign(&mut self, other: u128) {
- if other <= u128::from(u64::max_value()) {
- *self += other as u64
- } else {
- let (a, b, c, d) = u32_from_u128(other);
- let carry = if a > 0 {
- while self.data.len() < 4 {
- self.data.push(0);
- }
- __add2(&mut self.data, &[d, c, b, a])
+ cfg_digit!(
+ #[inline]
+ fn add_assign(&mut self, other: u128) {
+ if other <= u128::from(u64::MAX) {
+ *self += other as u64
} else {
- debug_assert!(b > 0);
- while self.data.len() < 3 {
+ let (a, b, c, d) = super::u32_from_u128(other);
+ let carry = if a > 0 {
+ while self.data.len() < 4 {
+ self.data.push(0);
+ }
+ __add2(&mut self.data, &[d, c, b, a])
+ } else {
+ debug_assert!(b > 0);
+ while self.data.len() < 3 {
+ self.data.push(0);
+ }
+ __add2(&mut self.data, &[d, c, b])
+ };
+
+ if carry != 0 {
+ self.data.push(carry);
+ }
+ }
+ }
+
+ #[inline]
+ fn add_assign(&mut self, other: u128) {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ if hi == 0 {
+ *self += lo;
+ } else {
+ while self.data.len() < 2 {
self.data.push(0);
}
- __add2(&mut self.data, &[d, c, b])
- };
- if carry != 0 {
- self.data.push(carry);
+ let carry = __add2(&mut self.data, &[lo, hi]);
+ if carry != 0 {
+ self.data.push(carry);
+ }
}
}
- }
-
- #[cfg(u64_digit)]
- #[inline]
- fn add_assign(&mut self, other: u128) {
- let (hi, lo) = big_digit::from_doublebigdigit(other);
- if hi == 0 {
- *self += lo;
- } else {
- while self.data.len() < 2 {
- self.data.push(0);
- }
-
- let carry = __add2(&mut self.data, &[lo, hi]);
- if carry != 0 {
- self.data.push(carry);
- }
- }
- }
+ );
}
impl CheckedAdd for BigUint {
diff --git a/crates/num-bigint/src/biguint/arbitrary.rs b/crates/num-bigint/src/biguint/arbitrary.rs
index 6fa91c0..9d5c5cc 100644
--- a/crates/num-bigint/src/biguint/arbitrary.rs
+++ b/crates/num-bigint/src/biguint/arbitrary.rs
@@ -1,11 +1,14 @@
+#![cfg(any(feature = "quickcheck", feature = "arbitrary"))]
+
use super::{biguint_from_vec, BigUint};
use crate::big_digit::BigDigit;
#[cfg(feature = "quickcheck")]
-use crate::std_alloc::Box;
-use crate::std_alloc::Vec;
+use alloc::boxed::Box;
+use alloc::vec::Vec;
#[cfg(feature = "quickcheck")]
+#[cfg_attr(docsrs, doc(cfg(feature = "quickcheck")))]
impl quickcheck::Arbitrary for BigUint {
fn arbitrary(g: &mut quickcheck::Gen) -> Self {
// Use arbitrary from Vec
@@ -19,6 +22,7 @@
}
#[cfg(feature = "arbitrary")]
+#[cfg_attr(docsrs, doc(cfg(feature = "arbitrary")))]
impl arbitrary::Arbitrary<'_> for BigUint {
fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
Ok(biguint_from_vec(Vec::<BigDigit>::arbitrary(u)?))
diff --git a/crates/num-bigint/src/biguint/convert.rs b/crates/num-bigint/src/biguint/convert.rs
index f19bc75..3daf3dc 100644
--- a/crates/num-bigint/src/biguint/convert.rs
+++ b/crates/num-bigint/src/biguint/convert.rs
@@ -4,17 +4,15 @@
use super::{biguint_from_vec, BigUint, ToBigUint};
use super::addition::add2;
-use super::division::div_rem_digit;
+use super::division::{div_rem_digit, FAST_DIV_WIDE};
use super::multiplication::mac_with_carry;
use crate::big_digit::{self, BigDigit};
-use crate::std_alloc::Vec;
use crate::ParseBigIntError;
-#[cfg(has_try_from)]
use crate::TryFromBigIntError;
+use alloc::vec::Vec;
use core::cmp::Ordering::{Equal, Greater, Less};
-#[cfg(has_try_from)]
use core::convert::TryFrom;
use core::mem;
use core::str::FromStr;
@@ -71,7 +69,7 @@
let total_bits = (v.len() as u64).saturating_mul(bits.into());
let big_digits = Integer::div_ceil(&total_bits, &big_digit::BITS.into())
.to_usize()
- .unwrap_or(core::usize::MAX);
+ .unwrap_or(usize::MAX);
let mut data = Vec::with_capacity(big_digits);
let mut d = 0;
@@ -121,7 +119,7 @@
let mut data = Vec::with_capacity(big_digits.to_usize().unwrap_or(0));
- let (base, power) = get_radix_base(radix, big_digit::BITS);
+ let (base, power) = get_radix_base(radix);
let radix = radix as BigDigit;
let r = v.len() % power;
@@ -161,7 +159,7 @@
);
if buf.is_empty() {
- return Some(Zero::zero());
+ return Some(BigUint::ZERO);
}
if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
@@ -192,7 +190,7 @@
);
if buf.is_empty() {
- return Some(Zero::zero());
+ return Some(BigUint::ZERO);
}
if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
@@ -223,8 +221,7 @@
fn from_str_radix(s: &str, radix: u32) -> Result<BigUint, ParseBigIntError> {
assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
let mut s = s;
- if s.starts_with('+') {
- let tail = &s[1..];
+ if let Some(tail) = s.strip_prefix('+') {
if !tail.starts_with('+') {
s = tail
}
@@ -247,7 +244,7 @@
b'a'..=b'z' => b - b'a' + 10,
b'A'..=b'Z' => b - b'A' + 10,
b'_' => continue,
- _ => core::u8::MAX,
+ _ => u8::MAX,
};
if d < radix as u8 {
v.push(d);
@@ -374,8 +371,8 @@
let mantissa = high_bits_to_u64(self);
let exponent = self.bits() - u64::from(fls(mantissa));
- if exponent > core::f32::MAX_EXP as u64 {
- Some(core::f32::INFINITY)
+ if exponent > f32::MAX_EXP as u64 {
+ Some(f32::INFINITY)
} else {
Some((mantissa as f32) * 2.0f32.powi(exponent as i32))
}
@@ -386,8 +383,8 @@
let mantissa = high_bits_to_u64(self);
let exponent = self.bits() - u64::from(fls(mantissa));
- if exponent > core::f64::MAX_EXP as u64 {
- Some(core::f64::INFINITY)
+ if exponent > f64::MAX_EXP as u64 {
+ Some(f64::INFINITY)
} else {
Some((mantissa as f64) * 2.0f64.powi(exponent as i32))
}
@@ -396,7 +393,6 @@
macro_rules! impl_try_from_biguint {
($T:ty, $to_ty:path) => {
- #[cfg(has_try_from)]
impl TryFrom<&BigUint> for $T {
type Error = TryFromBigIntError<()>;
@@ -406,7 +402,6 @@
}
}
- #[cfg(has_try_from)]
impl TryFrom<BigUint> for $T {
type Error = TryFromBigIntError<BigUint>;
@@ -473,7 +468,7 @@
// handle 0.x, -0.x
if n.is_zero() {
- return Some(BigUint::zero());
+ return Some(Self::ZERO);
}
let (mantissa, exponent, sign) = FloatCore::integer_decode(n);
@@ -495,7 +490,7 @@
impl From<u64> for BigUint {
#[inline]
fn from(mut n: u64) -> Self {
- let mut ret: BigUint = Zero::zero();
+ let mut ret: BigUint = Self::ZERO;
while n != 0 {
ret.data.push(n as BigDigit);
@@ -510,7 +505,7 @@
impl From<u128> for BigUint {
#[inline]
fn from(mut n: u128) -> Self {
- let mut ret: BigUint = Zero::zero();
+ let mut ret: BigUint = Self::ZERO;
while n != 0 {
ret.data.push(n as BigDigit);
@@ -539,7 +534,6 @@
macro_rules! impl_biguint_try_from_int {
($T:ty, $from_ty:path) => {
- #[cfg(has_try_from)]
impl TryFrom<$T> for BigUint {
type Error = TryFromBigIntError<()>;
@@ -598,7 +592,7 @@
if x {
One::one()
} else {
- Zero::zero()
+ Self::ZERO
}
}
}
@@ -612,7 +606,7 @@
let digits_per_big_digit = big_digit::BITS / bits;
let digits = Integer::div_ceil(&u.bits(), &u64::from(bits))
.to_usize()
- .unwrap_or(core::usize::MAX);
+ .unwrap_or(usize::MAX);
let mut res = Vec::with_capacity(digits);
for mut r in u.data[..last_i].iter().cloned() {
@@ -638,7 +632,7 @@
let mask: BigDigit = (1 << bits) - 1;
let digits = Integer::div_ceil(&u.bits(), &u64::from(bits))
.to_usize()
- .unwrap_or(core::usize::MAX);
+ .unwrap_or(usize::MAX);
let mut res = Vec::with_capacity(digits);
let mut r = 0;
@@ -693,7 +687,13 @@
let mut digits = u.clone();
- let (base, power) = get_radix_base(radix, big_digit::HALF_BITS);
+ // X86 DIV can quickly divide by a full digit, otherwise we choose a divisor
+ // that's suitable for `div_half` to avoid slow `DoubleBigDigit` division.
+ let (base, power) = if FAST_DIV_WIDE {
+ get_radix_base(radix)
+ } else {
+ get_half_radix_base(radix)
+ };
let radix = radix as BigDigit;
// For very large numbers, the O(n²) loop of repeated `div_rem_digit` dominates the
@@ -701,8 +701,8 @@
// The threshold for this was chosen by anecdotal performance measurements to
// approximate where this starts to make a noticeable difference.
if digits.data.len() >= 64 {
- let mut big_base = BigUint::from(base * base);
- let mut big_power = 2usize;
+ let mut big_base = BigUint::from(base);
+ let mut big_power = 1usize;
// Choose a target base length near √n.
let target_len = digits.data.len().sqrt();
@@ -788,33 +788,79 @@
res
}
-/// Returns the greatest power of the radix for the given bit size
+/// Returns the greatest power of the radix for the `BigDigit` bit size
#[inline]
-fn get_radix_base(radix: u32, bits: u8) -> (BigDigit, usize) {
- mod gen {
- include! { concat!(env!("OUT_DIR"), "/radix_bases.rs") }
+fn get_radix_base(radix: u32) -> (BigDigit, usize) {
+ static BASES: [(BigDigit, usize); 257] = generate_radix_bases(big_digit::MAX);
+ debug_assert!(!radix.is_power_of_two());
+ debug_assert!((3..256).contains(&radix));
+ BASES[radix as usize]
+}
+
+/// Returns the greatest power of the radix for half the `BigDigit` bit size
+#[inline]
+fn get_half_radix_base(radix: u32) -> (BigDigit, usize) {
+ static BASES: [(BigDigit, usize); 257] = generate_radix_bases(big_digit::HALF);
+ debug_assert!(!radix.is_power_of_two());
+ debug_assert!((3..256).contains(&radix));
+ BASES[radix as usize]
+}
+
+/// Generate tables of the greatest power of each radix that is less that the given maximum. These
+/// are returned from `get_radix_base` to batch the multiplication/division of radix conversions on
+/// full `BigUint` values, operating on primitive integers as much as possible.
+///
+/// e.g. BASES_16[3] = (59049, 10) // 3¹⁰ fits in u16, but 3¹¹ is too big
+/// BASES_32[3] = (3486784401, 20)
+/// BASES_64[3] = (12157665459056928801, 40)
+///
+/// Powers of two are not included, just zeroed, as they're implemented with shifts.
+const fn generate_radix_bases(max: BigDigit) -> [(BigDigit, usize); 257] {
+ let mut bases = [(0, 0); 257];
+
+ let mut radix: BigDigit = 3;
+ while radix < 256 {
+ if !radix.is_power_of_two() {
+ let mut power = 1;
+ let mut base = radix;
+
+ while let Some(b) = base.checked_mul(radix) {
+ if b > max {
+ break;
+ }
+ base = b;
+ power += 1;
+ }
+ bases[radix as usize] = (base, power)
+ }
+ radix += 1;
}
- debug_assert!(
- 2 <= radix && radix <= 256,
- "The radix must be within 2...256"
- );
- debug_assert!(!radix.is_power_of_two());
- debug_assert!(bits <= big_digit::BITS);
+ bases
+}
- match bits {
- 16 => {
- let (base, power) = gen::BASES_16[radix as usize];
- (base as BigDigit, power)
+#[test]
+fn test_radix_bases() {
+ for radix in 3u32..256 {
+ if !radix.is_power_of_two() {
+ let (base, power) = get_radix_base(radix);
+ let radix = BigDigit::from(radix);
+ let power = u32::try_from(power).unwrap();
+ assert_eq!(base, radix.pow(power));
+ assert!(radix.checked_pow(power + 1).is_none());
}
- 32 => {
- let (base, power) = gen::BASES_32[radix as usize];
- (base as BigDigit, power)
+ }
+}
+
+#[test]
+fn test_half_radix_bases() {
+ for radix in 3u32..256 {
+ if !radix.is_power_of_two() {
+ let (base, power) = get_half_radix_base(radix);
+ let radix = BigDigit::from(radix);
+ let power = u32::try_from(power).unwrap();
+ assert_eq!(base, radix.pow(power));
+ assert!(radix.pow(power + 1) > big_digit::HALF);
}
- 64 => {
- let (base, power) = gen::BASES_64[radix as usize];
- (base as BigDigit, power)
- }
- _ => panic!("Invalid bigdigit size"),
}
}
diff --git a/crates/num-bigint/src/biguint/division.rs b/crates/num-bigint/src/biguint/division.rs
index 2999838..3dfb0bb 100644
--- a/crates/num-bigint/src/biguint/division.rs
+++ b/crates/num-bigint/src/biguint/division.rs
@@ -1,6 +1,4 @@
use super::addition::__add2;
-#[cfg(not(u64_digit))]
-use super::u32_to_u128;
use super::{cmp_slice, BigUint};
use crate::big_digit::{self, BigDigit, DoubleBigDigit};
@@ -12,12 +10,15 @@
use num_integer::Integer;
use num_traits::{CheckedDiv, CheckedEuclid, Euclid, One, ToPrimitive, Zero};
+pub(super) const FAST_DIV_WIDE: bool = cfg!(any(target_arch = "x86", target_arch = "x86_64"));
+
/// Divide a two digit numerator by a one digit divisor, returns quotient and remainder:
///
/// Note: the caller must ensure that both the quotient and remainder will fit into a single digit.
/// This is _not_ true for an arbitrary numerator/denominator.
///
/// (This function also matches what the x86 divide instruction does).
+#[cfg(any(miri, not(any(target_arch = "x86", target_arch = "x86_64"))))]
#[inline]
fn div_wide(hi: BigDigit, lo: BigDigit, divisor: BigDigit) -> (BigDigit, BigDigit) {
debug_assert!(hi < divisor);
@@ -27,6 +28,47 @@
((lhs / rhs) as BigDigit, (lhs % rhs) as BigDigit)
}
+/// x86 and x86_64 can use a real `div` instruction.
+#[cfg(all(not(miri), any(target_arch = "x86", target_arch = "x86_64")))]
+#[inline]
+fn div_wide(hi: BigDigit, lo: BigDigit, divisor: BigDigit) -> (BigDigit, BigDigit) {
+ // This debug assertion covers the potential #DE for divisor==0 or a quotient too large for one
+ // register, otherwise in release mode it will become a target-specific fault like SIGFPE.
+ // This should never occur with the inputs from our few `div_wide` callers.
+ debug_assert!(hi < divisor);
+
+ // SAFETY: The `div` instruction only affects registers, reading the explicit operand as the
+ // divisor, and implicitly reading RDX:RAX or EDX:EAX as the dividend. The result is implicitly
+ // written back to RAX or EAX for the quotient and RDX or EDX for the remainder. No memory is
+ // used, and flags are not preserved.
+ unsafe {
+ let (div, rem);
+
+ cfg_digit!(
+ macro_rules! div {
+ () => {
+ "div {0:e}"
+ };
+ }
+ macro_rules! div {
+ () => {
+ "div {0:r}"
+ };
+ }
+ );
+
+ core::arch::asm!(
+ div!(),
+ in(reg) divisor,
+ inout("dx") hi => rem,
+ inout("ax") lo => div,
+ options(pure, nomem, nostack),
+ );
+
+ (div, rem)
+ }
+}
+
/// For small divisors, we can divide without promoting to `DoubleBigDigit` by
/// using half-size pieces of digit, like long-division.
#[inline]
@@ -47,7 +89,7 @@
let mut rem = 0;
- if b <= big_digit::HALF {
+ if !FAST_DIV_WIDE && b <= big_digit::HALF {
for d in a.data.iter_mut().rev() {
let (q, r) = div_half(rem, *d, b);
*d = q;
@@ -72,7 +114,7 @@
let mut rem = 0;
- if b <= big_digit::HALF {
+ if !FAST_DIV_WIDE && b <= big_digit::HALF {
for &digit in a.data.iter().rev() {
let (_, r) = div_half(rem, digit, b);
rem = r;
@@ -121,12 +163,12 @@
panic!("attempt to divide by zero")
}
if u.is_zero() {
- return (Zero::zero(), Zero::zero());
+ return (BigUint::ZERO, BigUint::ZERO);
}
if d.data.len() == 1 {
if d.data == [1] {
- return (u, Zero::zero());
+ return (u, BigUint::ZERO);
}
let (div, rem) = div_rem_digit(u, d.data[0]);
// reuse d
@@ -137,10 +179,10 @@
// Required or the q_len calculation below can underflow:
match u.cmp(&d) {
- Less => return (Zero::zero(), u),
+ Less => return (BigUint::ZERO, u),
Equal => {
u.set_one();
- return (u, Zero::zero());
+ return (u, BigUint::ZERO);
}
Greater => {} // Do nothing
}
@@ -168,12 +210,12 @@
panic!("attempt to divide by zero")
}
if u.is_zero() {
- return (Zero::zero(), Zero::zero());
+ return (BigUint::ZERO, BigUint::ZERO);
}
if d.data.len() == 1 {
if d.data == [1] {
- return (u.clone(), Zero::zero());
+ return (u.clone(), BigUint::ZERO);
}
let (div, rem) = div_rem_digit(u.clone(), d.data[0]);
@@ -182,8 +224,8 @@
// Required or the q_len calculation below can underflow:
match u.cmp(d) {
- Less => return (Zero::zero(), u.clone()),
- Equal => return (One::one(), Zero::zero()),
+ Less => return (BigUint::ZERO, u.clone()),
+ Equal => return (One::one(), BigUint::ZERO),
Greater => {} // Do nothing
}
@@ -232,7 +274,7 @@
let mut a0 = 0;
// [b1, b0] are the two most significant digits of the divisor. They never change.
- let b0 = *b.last().unwrap();
+ let b0 = b[b.len() - 1];
let b1 = b[b.len() - 2];
let q_len = a.data.len() - b.len() + 1;
@@ -360,7 +402,7 @@
match other.data.len() {
0 => panic!("attempt to divide by zero"),
1 => From::from(self as BigDigit / other.data[0]),
- _ => Zero::zero(),
+ _ => BigUint::ZERO,
}
}
}
@@ -378,7 +420,7 @@
#[inline]
fn div_assign(&mut self, other: u64) {
// a vec of size 0 does not allocate, so this is fairly cheap
- let temp = mem::replace(self, Zero::zero());
+ let temp = mem::replace(self, Self::ZERO);
*self = temp / other;
}
}
@@ -386,26 +428,26 @@
impl Div<BigUint> for u64 {
type Output = BigUint;
- #[cfg(not(u64_digit))]
- #[inline]
- fn div(self, other: BigUint) -> BigUint {
- match other.data.len() {
- 0 => panic!("attempt to divide by zero"),
- 1 => From::from(self / u64::from(other.data[0])),
- 2 => From::from(self / big_digit::to_doublebigdigit(other.data[1], other.data[0])),
- _ => Zero::zero(),
+ cfg_digit!(
+ #[inline]
+ fn div(self, other: BigUint) -> BigUint {
+ match other.data.len() {
+ 0 => panic!("attempt to divide by zero"),
+ 1 => From::from(self / u64::from(other.data[0])),
+ 2 => From::from(self / big_digit::to_doublebigdigit(other.data[1], other.data[0])),
+ _ => BigUint::ZERO,
+ }
}
- }
- #[cfg(u64_digit)]
- #[inline]
- fn div(self, other: BigUint) -> BigUint {
- match other.data.len() {
- 0 => panic!("attempt to divide by zero"),
- 1 => From::from(self / other.data[0]),
- _ => Zero::zero(),
+ #[inline]
+ fn div(self, other: BigUint) -> BigUint {
+ match other.data.len() {
+ 0 => panic!("attempt to divide by zero"),
+ 1 => From::from(self / other.data[0]),
+ _ => BigUint::ZERO,
+ }
}
- }
+ );
}
impl Div<u128> for BigUint {
@@ -428,33 +470,34 @@
impl Div<BigUint> for u128 {
type Output = BigUint;
- #[cfg(not(u64_digit))]
- #[inline]
- fn div(self, other: BigUint) -> BigUint {
- match other.data.len() {
- 0 => panic!("attempt to divide by zero"),
- 1 => From::from(self / u128::from(other.data[0])),
- 2 => From::from(
- self / u128::from(big_digit::to_doublebigdigit(other.data[1], other.data[0])),
- ),
- 3 => From::from(self / u32_to_u128(0, other.data[2], other.data[1], other.data[0])),
- 4 => From::from(
- self / u32_to_u128(other.data[3], other.data[2], other.data[1], other.data[0]),
- ),
- _ => Zero::zero(),
+ cfg_digit!(
+ #[inline]
+ fn div(self, other: BigUint) -> BigUint {
+ use super::u32_to_u128;
+ match other.data.len() {
+ 0 => panic!("attempt to divide by zero"),
+ 1 => From::from(self / u128::from(other.data[0])),
+ 2 => From::from(
+ self / u128::from(big_digit::to_doublebigdigit(other.data[1], other.data[0])),
+ ),
+ 3 => From::from(self / u32_to_u128(0, other.data[2], other.data[1], other.data[0])),
+ 4 => From::from(
+ self / u32_to_u128(other.data[3], other.data[2], other.data[1], other.data[0]),
+ ),
+ _ => BigUint::ZERO,
+ }
}
- }
- #[cfg(u64_digit)]
- #[inline]
- fn div(self, other: BigUint) -> BigUint {
- match other.data.len() {
- 0 => panic!("attempt to divide by zero"),
- 1 => From::from(self / other.data[0] as u128),
- 2 => From::from(self / big_digit::to_doublebigdigit(other.data[1], other.data[0])),
- _ => Zero::zero(),
+ #[inline]
+ fn div(self, other: BigUint) -> BigUint {
+ match other.data.len() {
+ 0 => panic!("attempt to divide by zero"),
+ 1 => From::from(self / other.data[0] as u128),
+ 2 => From::from(self / big_digit::to_doublebigdigit(other.data[1], other.data[0])),
+ _ => BigUint::ZERO,
+ }
}
- }
+ );
}
forward_val_ref_binop!(impl Rem for BigUint, rem);
@@ -635,6 +678,10 @@
}
Some(self.rem_euclid(v))
}
+
+ fn checked_div_rem_euclid(&self, v: &Self) -> Option<(Self, Self)> {
+ Some(self.div_rem_euclid(v))
+ }
}
impl Euclid for BigUint {
@@ -649,4 +696,9 @@
// trivially same as regular remainder
self % v
}
+
+ fn div_rem_euclid(&self, v: &Self) -> (Self, Self) {
+ // trivially same as regular division and remainder
+ self.div_rem(v)
+ }
}
diff --git a/crates/num-bigint/src/biguint/iter.rs b/crates/num-bigint/src/biguint/iter.rs
index 1e673e4..066c9c1 100644
--- a/crates/num-bigint/src/biguint/iter.rs
+++ b/crates/num-bigint/src/biguint/iter.rs
@@ -1,268 +1,271 @@
use core::iter::FusedIterator;
-#[cfg(not(u64_digit))]
-use super::u32_chunk_to_u64;
-
-/// An iterator of `u32` digits representation of a `BigUint` or `BigInt`,
-/// ordered least significant digit first.
-pub struct U32Digits<'a> {
- #[cfg(u64_digit)]
- data: &'a [u64],
- #[cfg(u64_digit)]
- next_is_lo: bool,
- #[cfg(u64_digit)]
- last_hi_is_zero: bool,
-
- #[cfg(not(u64_digit))]
- it: core::slice::Iter<'a, u32>,
-}
-
-#[cfg(u64_digit)]
-impl<'a> U32Digits<'a> {
- #[inline]
- pub(super) fn new(data: &'a [u64]) -> Self {
- let last_hi_is_zero = data
- .last()
- .map(|&last| {
- let last_hi = (last >> 32) as u32;
- last_hi == 0
- })
- .unwrap_or(false);
- U32Digits {
- data,
- next_is_lo: true,
- last_hi_is_zero,
- }
+cfg_digit!(
+ /// An iterator of `u32` digits representation of a `BigUint` or `BigInt`,
+ /// ordered least significant digit first.
+ pub struct U32Digits<'a> {
+ it: core::slice::Iter<'a, u32>,
}
-}
-#[cfg(u64_digit)]
-impl Iterator for U32Digits<'_> {
- type Item = u32;
- #[inline]
- fn next(&mut self) -> Option<u32> {
- match self.data.split_first() {
- Some((&first, data)) => {
- let next_is_lo = self.next_is_lo;
- self.next_is_lo = !next_is_lo;
- if next_is_lo {
- Some(first as u32)
- } else {
- self.data = data;
- if data.is_empty() && self.last_hi_is_zero {
- self.last_hi_is_zero = false;
- None
- } else {
- Some((first >> 32) as u32)
- }
+ /// An iterator of `u32` digits representation of a `BigUint` or `BigInt`,
+ /// ordered least significant digit first.
+ pub struct U32Digits<'a> {
+ data: &'a [u64],
+ next_is_lo: bool,
+ last_hi_is_zero: bool,
+ }
+);
+
+cfg_digit!(
+ const _: () = {
+ impl<'a> U32Digits<'a> {
+ #[inline]
+ pub(super) fn new(data: &'a [u32]) -> Self {
+ Self { it: data.iter() }
+ }
+ }
+
+ impl Iterator for U32Digits<'_> {
+ type Item = u32;
+ #[inline]
+ fn next(&mut self) -> Option<u32> {
+ self.it.next().cloned()
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.it.size_hint()
+ }
+
+ #[inline]
+ fn nth(&mut self, n: usize) -> Option<u32> {
+ self.it.nth(n).cloned()
+ }
+
+ #[inline]
+ fn last(self) -> Option<u32> {
+ self.it.last().cloned()
+ }
+
+ #[inline]
+ fn count(self) -> usize {
+ self.it.count()
+ }
+ }
+
+ impl DoubleEndedIterator for U32Digits<'_> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.it.next_back().cloned()
+ }
+ }
+
+ impl ExactSizeIterator for U32Digits<'_> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.it.len()
+ }
+ }
+ };
+
+ const _: () = {
+ impl<'a> U32Digits<'a> {
+ #[inline]
+ pub(super) fn new(data: &'a [u64]) -> Self {
+ let last_hi_is_zero = data
+ .last()
+ .map(|&last| {
+ let last_hi = (last >> 32) as u32;
+ last_hi == 0
+ })
+ .unwrap_or(false);
+ U32Digits {
+ data,
+ next_is_lo: true,
+ last_hi_is_zero,
}
}
- None => None,
}
- }
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let len = self.len();
- (len, Some(len))
- }
-
- #[inline]
- fn last(self) -> Option<u32> {
- self.data.last().map(|&last| {
- if self.last_hi_is_zero {
- last as u32
- } else {
- (last >> 32) as u32
- }
- })
- }
-
- #[inline]
- fn count(self) -> usize {
- self.len()
- }
-}
-
-#[cfg(u64_digit)]
-impl DoubleEndedIterator for U32Digits<'_> {
- fn next_back(&mut self) -> Option<Self::Item> {
- match self.data.split_last() {
- Some((&last, data)) => {
- let last_is_lo = self.last_hi_is_zero;
- self.last_hi_is_zero = !last_is_lo;
- if last_is_lo {
- self.data = data;
- if data.is_empty() && !self.next_is_lo {
- self.next_is_lo = true;
- None
- } else {
- Some(last as u32)
+ impl Iterator for U32Digits<'_> {
+ type Item = u32;
+ #[inline]
+ fn next(&mut self) -> Option<u32> {
+ match self.data.split_first() {
+ Some((&first, data)) => {
+ let next_is_lo = self.next_is_lo;
+ self.next_is_lo = !next_is_lo;
+ if next_is_lo {
+ Some(first as u32)
+ } else {
+ self.data = data;
+ if data.is_empty() && self.last_hi_is_zero {
+ self.last_hi_is_zero = false;
+ None
+ } else {
+ Some((first >> 32) as u32)
+ }
+ }
}
- } else {
- Some((last >> 32) as u32)
+ None => None,
}
}
- None => None,
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ let len = self.len();
+ (len, Some(len))
+ }
+
+ #[inline]
+ fn last(self) -> Option<u32> {
+ self.data.last().map(|&last| {
+ if self.last_hi_is_zero {
+ last as u32
+ } else {
+ (last >> 32) as u32
+ }
+ })
+ }
+
+ #[inline]
+ fn count(self) -> usize {
+ self.len()
+ }
}
- }
-}
-#[cfg(u64_digit)]
-impl ExactSizeIterator for U32Digits<'_> {
- #[inline]
- fn len(&self) -> usize {
- self.data.len() * 2 - usize::from(self.last_hi_is_zero) - usize::from(!self.next_is_lo)
- }
-}
+ impl DoubleEndedIterator for U32Digits<'_> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ match self.data.split_last() {
+ Some((&last, data)) => {
+ let last_is_lo = self.last_hi_is_zero;
+ self.last_hi_is_zero = !last_is_lo;
+ if last_is_lo {
+ self.data = data;
+ if data.is_empty() && !self.next_is_lo {
+ self.next_is_lo = true;
+ None
+ } else {
+ Some(last as u32)
+ }
+ } else {
+ Some((last >> 32) as u32)
+ }
+ }
+ None => None,
+ }
+ }
+ }
-#[cfg(not(u64_digit))]
-impl<'a> U32Digits<'a> {
- #[inline]
- pub(super) fn new(data: &'a [u32]) -> Self {
- Self { it: data.iter() }
- }
-}
-
-#[cfg(not(u64_digit))]
-impl Iterator for U32Digits<'_> {
- type Item = u32;
- #[inline]
- fn next(&mut self) -> Option<u32> {
- self.it.next().cloned()
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.it.size_hint()
- }
-
- #[inline]
- fn nth(&mut self, n: usize) -> Option<u32> {
- self.it.nth(n).cloned()
- }
-
- #[inline]
- fn last(self) -> Option<u32> {
- self.it.last().cloned()
- }
-
- #[inline]
- fn count(self) -> usize {
- self.it.count()
- }
-}
-
-#[cfg(not(u64_digit))]
-impl DoubleEndedIterator for U32Digits<'_> {
- fn next_back(&mut self) -> Option<Self::Item> {
- self.it.next_back().copied()
- }
-}
-
-#[cfg(not(u64_digit))]
-impl ExactSizeIterator for U32Digits<'_> {
- #[inline]
- fn len(&self) -> usize {
- self.it.len()
- }
-}
+ impl ExactSizeIterator for U32Digits<'_> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.data.len() * 2
+ - usize::from(self.last_hi_is_zero)
+ - usize::from(!self.next_is_lo)
+ }
+ }
+ };
+);
impl FusedIterator for U32Digits<'_> {}
-/// An iterator of `u64` digits representation of a `BigUint` or `BigInt`,
-/// ordered least significant digit first.
-pub struct U64Digits<'a> {
- #[cfg(not(u64_digit))]
- it: core::slice::Chunks<'a, u32>,
-
- #[cfg(u64_digit)]
- it: core::slice::Iter<'a, u64>,
-}
-
-#[cfg(not(u64_digit))]
-impl<'a> U64Digits<'a> {
- #[inline]
- pub(super) fn new(data: &'a [u32]) -> Self {
- U64Digits { it: data.chunks(2) }
- }
-}
-
-#[cfg(not(u64_digit))]
-impl Iterator for U64Digits<'_> {
- type Item = u64;
- #[inline]
- fn next(&mut self) -> Option<u64> {
- self.it.next().map(u32_chunk_to_u64)
+cfg_digit!(
+ /// An iterator of `u64` digits representation of a `BigUint` or `BigInt`,
+ /// ordered least significant digit first.
+ pub struct U64Digits<'a> {
+ it: core::slice::Chunks<'a, u32>,
}
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let len = self.len();
- (len, Some(len))
+ /// An iterator of `u64` digits representation of a `BigUint` or `BigInt`,
+ /// ordered least significant digit first.
+ pub struct U64Digits<'a> {
+ it: core::slice::Iter<'a, u64>,
}
+);
- #[inline]
- fn last(self) -> Option<u64> {
- self.it.last().map(u32_chunk_to_u64)
- }
+cfg_digit!(
+ const _: () = {
+ impl<'a> U64Digits<'a> {
+ #[inline]
+ pub(super) fn new(data: &'a [u32]) -> Self {
+ U64Digits { it: data.chunks(2) }
+ }
+ }
- #[inline]
- fn count(self) -> usize {
- self.len()
- }
-}
+ impl Iterator for U64Digits<'_> {
+ type Item = u64;
+ #[inline]
+ fn next(&mut self) -> Option<u64> {
+ self.it.next().map(super::u32_chunk_to_u64)
+ }
-#[cfg(not(u64_digit))]
-impl DoubleEndedIterator for U64Digits<'_> {
- fn next_back(&mut self) -> Option<Self::Item> {
- self.it.next_back().map(u32_chunk_to_u64)
- }
-}
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ let len = self.len();
+ (len, Some(len))
+ }
-#[cfg(u64_digit)]
-impl<'a> U64Digits<'a> {
- #[inline]
- pub(super) fn new(data: &'a [u64]) -> Self {
- Self { it: data.iter() }
- }
-}
+ #[inline]
+ fn last(self) -> Option<u64> {
+ self.it.last().map(super::u32_chunk_to_u64)
+ }
-#[cfg(u64_digit)]
-impl Iterator for U64Digits<'_> {
- type Item = u64;
- #[inline]
- fn next(&mut self) -> Option<u64> {
- self.it.next().cloned()
- }
+ #[inline]
+ fn count(self) -> usize {
+ self.len()
+ }
+ }
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.it.size_hint()
- }
+ impl DoubleEndedIterator for U64Digits<'_> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.it.next_back().map(super::u32_chunk_to_u64)
+ }
+ }
+ };
- #[inline]
- fn nth(&mut self, n: usize) -> Option<u64> {
- self.it.nth(n).cloned()
- }
+ const _: () = {
+ impl<'a> U64Digits<'a> {
+ #[inline]
+ pub(super) fn new(data: &'a [u64]) -> Self {
+ Self { it: data.iter() }
+ }
+ }
- #[inline]
- fn last(self) -> Option<u64> {
- self.it.last().cloned()
- }
+ impl Iterator for U64Digits<'_> {
+ type Item = u64;
+ #[inline]
+ fn next(&mut self) -> Option<u64> {
+ self.it.next().cloned()
+ }
- #[inline]
- fn count(self) -> usize {
- self.it.count()
- }
-}
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.it.size_hint()
+ }
-#[cfg(u64_digit)]
-impl DoubleEndedIterator for U64Digits<'_> {
- fn next_back(&mut self) -> Option<Self::Item> {
- self.it.next_back().cloned()
- }
-}
+ #[inline]
+ fn nth(&mut self, n: usize) -> Option<u64> {
+ self.it.nth(n).cloned()
+ }
+
+ #[inline]
+ fn last(self) -> Option<u64> {
+ self.it.last().cloned()
+ }
+
+ #[inline]
+ fn count(self) -> usize {
+ self.it.count()
+ }
+ }
+
+ impl DoubleEndedIterator for U64Digits<'_> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.it.next_back().cloned()
+ }
+ }
+ };
+);
impl ExactSizeIterator for U64Digits<'_> {
#[inline]
diff --git a/crates/num-bigint/src/biguint/monty.rs b/crates/num-bigint/src/biguint/monty.rs
index abaca50..a0b26b5 100644
--- a/crates/num-bigint/src/biguint/monty.rs
+++ b/crates/num-bigint/src/biguint/monty.rs
@@ -1,9 +1,9 @@
-use crate::std_alloc::Vec;
+use alloc::vec::Vec;
use core::mem;
use core::ops::Shl;
-use num_traits::{One, Zero};
+use num_traits::One;
-use crate::big_digit::{self, BigDigit, DoubleBigDigit, SignedDoubleBigDigit};
+use crate::big_digit::{self, BigDigit, DoubleBigDigit};
use crate::biguint::BigUint;
struct MontyReducer {
@@ -15,8 +15,8 @@
fn inv_mod_alt(b: BigDigit) -> BigDigit {
assert_ne!(b & 1, 0);
- let mut k0 = 2 - b as SignedDoubleBigDigit;
- let mut t = (b - 1) as SignedDoubleBigDigit;
+ let mut k0 = BigDigit::wrapping_sub(2, b);
+ let mut t = b - 1;
let mut i = 1;
while i < big_digit::BITS {
t = t.wrapping_mul(t);
@@ -24,7 +24,8 @@
i <<= 1;
}
- -k0 as BigDigit
+ debug_assert_eq!(k0.wrapping_mul(b), 1);
+ k0.wrapping_neg()
}
impl MontyReducer {
@@ -56,7 +57,7 @@
n
);
- let mut z = BigUint::zero();
+ let mut z = BigUint::ZERO;
z.data.resize(n * 2, 0);
let mut c: BigDigit = 0;
@@ -173,7 +174,7 @@
// initialize z = 1 (Montgomery 1)
let mut z = powers[0].clone();
z.data.resize(num_words, 0);
- let mut zz = BigUint::zero();
+ let mut zz = BigUint::ZERO;
zz.data.resize(num_words, 0);
// same windowed exponent, but with Montgomery multiplications
diff --git a/crates/num-bigint/src/biguint/multiplication.rs b/crates/num-bigint/src/biguint/multiplication.rs
index 4d7f1f2..e9d2138 100644
--- a/crates/num-bigint/src/biguint/multiplication.rs
+++ b/crates/num-bigint/src/biguint/multiplication.rs
@@ -1,7 +1,5 @@
use super::addition::{__add2, add2};
use super::subtraction::sub2;
-#[cfg(not(u64_digit))]
-use super::u32_from_u128;
use super::{biguint_from_vec, cmp_slice, BigUint, IntDigits};
use crate::big_digit::{self, BigDigit, DoubleBigDigit};
@@ -88,9 +86,10 @@
let acc = acc;
let (x, y) = if b.len() < c.len() { (b, c) } else { (c, b) };
- // We use three algorithms for different input sizes.
+ // We use four algorithms for different input sizes.
//
// - For small inputs, long multiplication is fastest.
+ // - If y is at least least twice as long as x, split using Half-Karatsuba.
// - Next we use Karatsuba multiplication (Toom-2), which we have optimized
// to avoid unnecessary allocations for intermediate values.
// - For the largest inputs we use Toom-3, which better optimizes the
@@ -104,6 +103,65 @@
for (i, xi) in x.iter().enumerate() {
mac_digit(&mut acc[i..], y, *xi);
}
+ } else if x.len() * 2 <= y.len() {
+ // Karatsuba Multiplication for factors with significant length disparity.
+ //
+ // The Half-Karatsuba Multiplication Algorithm is a specialized case of
+ // the normal Karatsuba multiplication algorithm, designed for the scenario
+ // where y has at least twice as many base digits as x.
+ //
+ // In this case y (the longer input) is split into high2 and low2,
+ // at m2 (half the length of y) and x (the shorter input),
+ // is used directly without splitting.
+ //
+ // The algorithm then proceeds as follows:
+ //
+ // 1. Compute the product z0 = x * low2.
+ // 2. Compute the product temp = x * high2.
+ // 3. Adjust the weight of temp by adding m2 (* NBASE ^ m2)
+ // 4. Add temp and z0 to obtain the final result.
+ //
+ // Proof:
+ //
+ // The algorithm can be derived from the original Karatsuba algorithm by
+ // simplifying the formula when the shorter factor x is not split into
+ // high and low parts, as shown below.
+ //
+ // Original Karatsuba formula:
+ //
+ // result = (z2 * NBASE ^ (m2 × 2)) + ((z1 - z2 - z0) * NBASE ^ m2) + z0
+ //
+ // Substitutions:
+ //
+ // low1 = x
+ // high1 = 0
+ //
+ // Applying substitutions:
+ //
+ // z0 = (low1 * low2)
+ // = (x * low2)
+ //
+ // z1 = ((low1 + high1) * (low2 + high2))
+ // = ((x + 0) * (low2 + high2))
+ // = (x * low2) + (x * high2)
+ //
+ // z2 = (high1 * high2)
+ // = (0 * high2)
+ // = 0
+ //
+ // Simplified using the above substitutions:
+ //
+ // result = (z2 * NBASE ^ (m2 × 2)) + ((z1 - z2 - z0) * NBASE ^ m2) + z0
+ // = (0 * NBASE ^ (m2 × 2)) + ((z1 - 0 - z0) * NBASE ^ m2) + z0
+ // = ((z1 - z0) * NBASE ^ m2) + z0
+ // = ((z1 - z0) * NBASE ^ m2) + z0
+ // = (x * high2) * NBASE ^ m2 + z0
+ let m2 = y.len() / 2;
+ let (low2, high2) = y.split_at(m2);
+
+ // (x * high2) * NBASE ^ m2 + z0
+ mac3(acc, x, low2);
+ mac3(&mut acc[m2..], x, high2);
} else if x.len() <= 256 {
// Karatsuba multiplication:
//
@@ -311,9 +369,9 @@
// in terms of its coefficients:
//
// w0 = w(0)
- // w1 = w(0)/2 + w(1)/3 - w(-1) + w(2)/6 - 2*w(inf)
+ // w1 = w(0)/2 + w(1)/3 - w(-1) + w(-2)/6 - 2*w(inf)
// w2 = -w(0) + w(1)/2 + w(-1)/2 - w(inf)
- // w3 = -w(0)/2 + w(1)/6 + w(-1)/2 - w(1)/6
+ // w3 = -w(0)/2 + w(1)/6 + w(-1)/2 - w(-2)/6 + 2*w(inf)
// w4 = w(inf)
//
// This particular sequence is given by Bodrato and is an interpolation
@@ -397,7 +455,7 @@
sub2(&mut b, a);
(Minus, biguint_from_vec(b))
}
- Ordering::Equal => (NoSign, Zero::zero()),
+ Ordering::Equal => (NoSign, BigUint::ZERO),
}
}
@@ -410,7 +468,7 @@
fn mul(self, other: $Other) -> BigUint {
match (&*self.data, &*other.data) {
// multiply by zero
- (&[], _) | (_, &[]) => BigUint::zero(),
+ (&[], _) | (_, &[]) => BigUint::ZERO,
// multiply by a scalar
(_, &[digit]) => self * digit,
(&[digit], _) => other * digit,
@@ -484,22 +542,22 @@
}
}
impl MulAssign<u64> for BigUint {
- #[cfg(not(u64_digit))]
- #[inline]
- fn mul_assign(&mut self, other: u64) {
- if let Some(other) = BigDigit::from_u64(other) {
- scalar_mul(self, other);
- } else {
- let (hi, lo) = big_digit::from_doublebigdigit(other);
- *self = mul3(&self.data, &[lo, hi]);
+ cfg_digit!(
+ #[inline]
+ fn mul_assign(&mut self, other: u64) {
+ if let Some(other) = BigDigit::from_u64(other) {
+ scalar_mul(self, other);
+ } else {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ *self = mul3(&self.data, &[lo, hi]);
+ }
}
- }
- #[cfg(u64_digit)]
- #[inline]
- fn mul_assign(&mut self, other: u64) {
- scalar_mul(self, other);
- }
+ #[inline]
+ fn mul_assign(&mut self, other: u64) {
+ scalar_mul(self, other);
+ }
+ );
}
impl Mul<u128> for BigUint {
@@ -513,30 +571,30 @@
}
impl MulAssign<u128> for BigUint {
- #[cfg(not(u64_digit))]
- #[inline]
- fn mul_assign(&mut self, other: u128) {
- if let Some(other) = BigDigit::from_u128(other) {
- scalar_mul(self, other);
- } else {
- *self = match u32_from_u128(other) {
- (0, 0, c, d) => mul3(&self.data, &[d, c]),
- (0, b, c, d) => mul3(&self.data, &[d, c, b]),
- (a, b, c, d) => mul3(&self.data, &[d, c, b, a]),
- };
+ cfg_digit!(
+ #[inline]
+ fn mul_assign(&mut self, other: u128) {
+ if let Some(other) = BigDigit::from_u128(other) {
+ scalar_mul(self, other);
+ } else {
+ *self = match super::u32_from_u128(other) {
+ (0, 0, c, d) => mul3(&self.data, &[d, c]),
+ (0, b, c, d) => mul3(&self.data, &[d, c, b]),
+ (a, b, c, d) => mul3(&self.data, &[d, c, b, a]),
+ };
+ }
}
- }
- #[cfg(u64_digit)]
- #[inline]
- fn mul_assign(&mut self, other: u128) {
- if let Some(other) = BigDigit::from_u128(other) {
- scalar_mul(self, other);
- } else {
- let (hi, lo) = big_digit::from_doublebigdigit(other);
- *self = mul3(&self.data, &[lo, hi]);
+ #[inline]
+ fn mul_assign(&mut self, other: u128) {
+ if let Some(other) = BigDigit::from_u128(other) {
+ scalar_mul(self, other);
+ } else {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ *self = mul3(&self.data, &[lo, hi]);
+ }
}
- }
+ );
}
impl CheckedMul for BigUint {
diff --git a/crates/num-bigint/src/biguint/power.rs b/crates/num-bigint/src/biguint/power.rs
index 621e1b1..fa1c492 100644
--- a/crates/num-bigint/src/biguint/power.rs
+++ b/crates/num-bigint/src/biguint/power.rs
@@ -14,7 +14,7 @@
if self.is_one() || exp.is_zero() {
BigUint::one()
} else if self.is_zero() {
- BigUint::zero()
+ Self::ZERO
} else if let Some(exp) = exp.to_u64() {
self.pow(exp)
} else if let Some(exp) = exp.to_u128() {
@@ -44,7 +44,7 @@
if self.is_one() || exp.is_zero() {
BigUint::one()
} else if self.is_zero() {
- BigUint::zero()
+ BigUint::ZERO
} else {
self.clone().pow(exp)
}
diff --git a/crates/num-bigint/src/biguint/serde.rs b/crates/num-bigint/src/biguint/serde.rs
index 3240f09..84bdf50 100644
--- a/crates/num-bigint/src/biguint/serde.rs
+++ b/crates/num-bigint/src/biguint/serde.rs
@@ -1,7 +1,9 @@
+#![cfg(feature = "serde")]
+#![cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+
use super::{biguint_from_vec, BigUint};
-use crate::std_alloc::Vec;
-
+use alloc::vec::Vec;
use core::{cmp, fmt, mem};
use serde::de::{SeqAccess, Visitor};
use serde::{Deserialize, Deserializer, Serialize, Serializer};
@@ -18,44 +20,44 @@
}
impl Serialize for BigUint {
- #[cfg(not(u64_digit))]
- fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
- where
- S: Serializer,
- {
- // Note: do not change the serialization format, or it may break forward
- // and backward compatibility of serialized data! If we ever change the
- // internal representation, we should still serialize in base-`u32`.
- let data: &[u32] = &self.data;
- data.serialize(serializer)
- }
-
- #[cfg(u64_digit)]
- fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
- where
- S: Serializer,
- {
- use serde::ser::SerializeSeq;
-
- if let Some((&last, data)) = self.data.split_last() {
- let last_lo = last as u32;
- let last_hi = (last >> 32) as u32;
- let u32_len = data.len() * 2 + 1 + (last_hi != 0) as usize;
- let mut seq = serializer.serialize_seq(Some(u32_len))?;
- for &x in data {
- seq.serialize_element(&(x as u32))?;
- seq.serialize_element(&((x >> 32) as u32))?;
- }
- seq.serialize_element(&last_lo)?;
- if last_hi != 0 {
- seq.serialize_element(&last_hi)?;
- }
- seq.end()
- } else {
- let data: &[u32] = &[];
+ cfg_digit!(
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ // Note: do not change the serialization format, or it may break forward
+ // and backward compatibility of serialized data! If we ever change the
+ // internal representation, we should still serialize in base-`u32`.
+ let data: &[u32] = &self.data;
data.serialize(serializer)
}
- }
+
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ use serde::ser::SerializeSeq;
+
+ if let Some((&last, data)) = self.data.split_last() {
+ let last_lo = last as u32;
+ let last_hi = (last >> 32) as u32;
+ let u32_len = data.len() * 2 + 1 + (last_hi != 0) as usize;
+ let mut seq = serializer.serialize_seq(Some(u32_len))?;
+ for &x in data {
+ seq.serialize_element(&(x as u32))?;
+ seq.serialize_element(&((x >> 32) as u32))?;
+ }
+ seq.serialize_element(&last_lo)?;
+ if last_hi != 0 {
+ seq.serialize_element(&last_hi)?;
+ }
+ seq.end()
+ } else {
+ let data: &[u32] = &[];
+ data.serialize(serializer)
+ }
+ }
+ );
}
impl<'de> Deserialize<'de> for BigUint {
@@ -76,44 +78,44 @@
formatter.write_str("a sequence of unsigned 32-bit numbers")
}
- #[cfg(not(u64_digit))]
- fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
- where
- S: SeqAccess<'de>,
- {
- let len = cautious(seq.size_hint());
- let mut data = Vec::with_capacity(len);
+ cfg_digit!(
+ fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
+ where
+ S: SeqAccess<'de>,
+ {
+ let len = cautious(seq.size_hint());
+ let mut data = Vec::with_capacity(len);
- while let Some(value) = seq.next_element::<u32>()? {
- data.push(value);
- }
-
- Ok(biguint_from_vec(data))
- }
-
- #[cfg(u64_digit)]
- fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
- where
- S: SeqAccess<'de>,
- {
- use crate::big_digit::BigDigit;
- use num_integer::Integer;
-
- let u32_len = cautious(seq.size_hint());
- let len = Integer::div_ceil(&u32_len, &2);
- let mut data = Vec::with_capacity(len);
-
- while let Some(lo) = seq.next_element::<u32>()? {
- let mut value = BigDigit::from(lo);
- if let Some(hi) = seq.next_element::<u32>()? {
- value |= BigDigit::from(hi) << 32;
+ while let Some(value) = seq.next_element::<u32>()? {
data.push(value);
- } else {
- data.push(value);
- break;
}
+
+ Ok(biguint_from_vec(data))
}
- Ok(biguint_from_vec(data))
- }
+ fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
+ where
+ S: SeqAccess<'de>,
+ {
+ use crate::big_digit::BigDigit;
+ use num_integer::Integer;
+
+ let u32_len = cautious(seq.size_hint());
+ let len = Integer::div_ceil(&u32_len, &2);
+ let mut data = Vec::with_capacity(len);
+
+ while let Some(lo) = seq.next_element::<u32>()? {
+ let mut value = BigDigit::from(lo);
+ if let Some(hi) = seq.next_element::<u32>()? {
+ value |= BigDigit::from(hi) << 32;
+ data.push(value);
+ } else {
+ data.push(value);
+ break;
+ }
+ }
+
+ Ok(biguint_from_vec(data))
+ }
+ );
}
diff --git a/crates/num-bigint/src/biguint/shift.rs b/crates/num-bigint/src/biguint/shift.rs
index 00326bb..51483cd 100644
--- a/crates/num-bigint/src/biguint/shift.rs
+++ b/crates/num-bigint/src/biguint/shift.rs
@@ -1,8 +1,9 @@
use super::{biguint_from_vec, BigUint};
use crate::big_digit;
-use crate::std_alloc::{Cow, Vec};
+use alloc::borrow::Cow;
+use alloc::vec::Vec;
use core::mem;
use core::ops::{Shl, ShlAssign, Shr, ShrAssign};
use num_traits::{PrimInt, Zero};
@@ -58,7 +59,7 @@
return n.into_owned();
}
let bits = T::from(big_digit::BITS).unwrap();
- let digits = (shift / bits).to_usize().unwrap_or(core::usize::MAX);
+ let digits = (shift / bits).to_usize().unwrap_or(usize::MAX);
let shift = (shift % bits).to_u8().unwrap();
biguint_shr2(n, digits, shift)
}
@@ -135,7 +136,7 @@
impl ShlAssign<$rhs> for BigUint {
#[inline]
fn shl_assign(&mut self, rhs: $rhs) {
- let n = mem::replace(self, BigUint::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n << rhs;
}
}
@@ -160,7 +161,7 @@
impl ShrAssign<$rhs> for BigUint {
#[inline]
fn shr_assign(&mut self, rhs: $rhs) {
- let n = mem::replace(self, BigUint::zero());
+ let n = mem::replace(self, Self::ZERO);
*self = n >> rhs;
}
}
diff --git a/crates/num-bigint/src/biguint/subtraction.rs b/crates/num-bigint/src/biguint/subtraction.rs
index b7cf59d..47a5015 100644
--- a/crates/num-bigint/src/biguint/subtraction.rs
+++ b/crates/num-bigint/src/biguint/subtraction.rs
@@ -1,5 +1,3 @@
-#[cfg(not(u64_digit))]
-use super::u32_from_u128;
use super::BigUint;
use crate::big_digit::{self, BigDigit};
@@ -7,42 +5,44 @@
use core::cmp::Ordering::{Equal, Greater, Less};
use core::ops::{Sub, SubAssign};
-use num_traits::{CheckedSub, Zero};
+use num_traits::CheckedSub;
-#[cfg(all(use_addcarry, target_arch = "x86_64"))]
+#[cfg(target_arch = "x86_64")]
use core::arch::x86_64 as arch;
-#[cfg(all(use_addcarry, target_arch = "x86"))]
+#[cfg(target_arch = "x86")]
use core::arch::x86 as arch;
// Subtract with borrow:
-#[cfg(all(use_addcarry, u64_digit))]
-#[inline]
-fn sbb(borrow: u8, a: u64, b: u64, out: &mut u64) -> u8 {
- // Safety: There are absolutely no safety concerns with calling `_subborrow_u64`.
- // It's just unsafe for API consistency with other intrinsics.
- unsafe { arch::_subborrow_u64(borrow, a, b, out) }
-}
+#[cfg(target_arch = "x86_64")]
+cfg_64!(
+ #[inline]
+ fn sbb(borrow: u8, a: u64, b: u64, out: &mut u64) -> u8 {
+ // Safety: There are absolutely no safety concerns with calling `_subborrow_u64`.
+ // It's just unsafe for API consistency with other intrinsics.
+ unsafe { arch::_subborrow_u64(borrow, a, b, out) }
+ }
+);
-#[cfg(all(use_addcarry, not(u64_digit)))]
-#[inline]
-fn sbb(borrow: u8, a: u32, b: u32, out: &mut u32) -> u8 {
- // Safety: There are absolutely no safety concerns with calling `_subborrow_u32`.
- // It's just unsafe for API consistency with other intrinsics.
- unsafe { arch::_subborrow_u32(borrow, a, b, out) }
-}
+#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
+cfg_32!(
+ #[inline]
+ fn sbb(borrow: u8, a: u32, b: u32, out: &mut u32) -> u8 {
+ // Safety: There are absolutely no safety concerns with calling `_subborrow_u32`.
+ // It's just unsafe for API consistency with other intrinsics.
+ unsafe { arch::_subborrow_u32(borrow, a, b, out) }
+ }
+);
// fallback for environments where we don't have a subborrow intrinsic
-#[cfg(not(use_addcarry))]
+// (copied from the standard library's `borrowing_sub`)
+#[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
#[inline]
-fn sbb(borrow: u8, a: BigDigit, b: BigDigit, out: &mut BigDigit) -> u8 {
- use crate::big_digit::SignedDoubleBigDigit;
-
- let difference = SignedDoubleBigDigit::from(a)
- - SignedDoubleBigDigit::from(b)
- - SignedDoubleBigDigit::from(borrow);
- *out = difference as BigDigit;
- u8::from(difference < 0)
+fn sbb(borrow: u8, lhs: BigDigit, rhs: BigDigit, out: &mut BigDigit) -> u8 {
+ let (a, b) = lhs.overflowing_sub(rhs);
+ let (c, d) = a.overflowing_sub(borrow as BigDigit);
+ *out = c;
+ u8::from(b || d)
}
pub(super) fn sub2(a: &mut [BigDigit], b: &[BigDigit]) {
@@ -167,27 +167,27 @@
impl Sub<BigUint> for u32 {
type Output = BigUint;
- #[cfg(not(u64_digit))]
- #[inline]
- fn sub(self, mut other: BigUint) -> BigUint {
- if other.data.len() == 0 {
- other.data.push(self);
- } else {
- sub2rev(&[self], &mut other.data[..]);
+ cfg_digit!(
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ if other.data.len() == 0 {
+ other.data.push(self);
+ } else {
+ sub2rev(&[self], &mut other.data[..]);
+ }
+ other.normalized()
}
- other.normalized()
- }
- #[cfg(u64_digit)]
- #[inline]
- fn sub(self, mut other: BigUint) -> BigUint {
- if other.data.is_empty() {
- other.data.push(self as BigDigit);
- } else {
- sub2rev(&[self as BigDigit], &mut other.data[..]);
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ if other.data.is_empty() {
+ other.data.push(self as BigDigit);
+ } else {
+ sub2rev(&[self as BigDigit], &mut other.data[..]);
+ }
+ other.normalized()
}
- other.normalized()
- }
+ );
}
impl Sub<u64> for BigUint {
@@ -201,47 +201,47 @@
}
impl SubAssign<u64> for BigUint {
- #[cfg(not(u64_digit))]
- #[inline]
- fn sub_assign(&mut self, other: u64) {
- let (hi, lo) = big_digit::from_doublebigdigit(other);
- sub2(&mut self.data[..], &[lo, hi]);
- self.normalize();
- }
+ cfg_digit!(
+ #[inline]
+ fn sub_assign(&mut self, other: u64) {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ sub2(&mut self.data[..], &[lo, hi]);
+ self.normalize();
+ }
- #[cfg(u64_digit)]
- #[inline]
- fn sub_assign(&mut self, other: u64) {
- sub2(&mut self.data[..], &[other as BigDigit]);
- self.normalize();
- }
+ #[inline]
+ fn sub_assign(&mut self, other: u64) {
+ sub2(&mut self.data[..], &[other as BigDigit]);
+ self.normalize();
+ }
+ );
}
impl Sub<BigUint> for u64 {
type Output = BigUint;
- #[cfg(not(u64_digit))]
- #[inline]
- fn sub(self, mut other: BigUint) -> BigUint {
- while other.data.len() < 2 {
- other.data.push(0);
+ cfg_digit!(
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ while other.data.len() < 2 {
+ other.data.push(0);
+ }
+
+ let (hi, lo) = big_digit::from_doublebigdigit(self);
+ sub2rev(&[lo, hi], &mut other.data[..]);
+ other.normalized()
}
- let (hi, lo) = big_digit::from_doublebigdigit(self);
- sub2rev(&[lo, hi], &mut other.data[..]);
- other.normalized()
- }
-
- #[cfg(u64_digit)]
- #[inline]
- fn sub(self, mut other: BigUint) -> BigUint {
- if other.data.is_empty() {
- other.data.push(self);
- } else {
- sub2rev(&[self], &mut other.data[..]);
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ if other.data.is_empty() {
+ other.data.push(self);
+ } else {
+ sub2rev(&[self], &mut other.data[..]);
+ }
+ other.normalized()
}
- other.normalized()
- }
+ );
}
impl Sub<u128> for BigUint {
@@ -255,49 +255,49 @@
}
impl SubAssign<u128> for BigUint {
- #[cfg(not(u64_digit))]
- #[inline]
- fn sub_assign(&mut self, other: u128) {
- let (a, b, c, d) = u32_from_u128(other);
- sub2(&mut self.data[..], &[d, c, b, a]);
- self.normalize();
- }
+ cfg_digit!(
+ #[inline]
+ fn sub_assign(&mut self, other: u128) {
+ let (a, b, c, d) = super::u32_from_u128(other);
+ sub2(&mut self.data[..], &[d, c, b, a]);
+ self.normalize();
+ }
- #[cfg(u64_digit)]
- #[inline]
- fn sub_assign(&mut self, other: u128) {
- let (hi, lo) = big_digit::from_doublebigdigit(other);
- sub2(&mut self.data[..], &[lo, hi]);
- self.normalize();
- }
+ #[inline]
+ fn sub_assign(&mut self, other: u128) {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ sub2(&mut self.data[..], &[lo, hi]);
+ self.normalize();
+ }
+ );
}
impl Sub<BigUint> for u128 {
type Output = BigUint;
- #[cfg(not(u64_digit))]
- #[inline]
- fn sub(self, mut other: BigUint) -> BigUint {
- while other.data.len() < 4 {
- other.data.push(0);
+ cfg_digit!(
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ while other.data.len() < 4 {
+ other.data.push(0);
+ }
+
+ let (a, b, c, d) = super::u32_from_u128(self);
+ sub2rev(&[d, c, b, a], &mut other.data[..]);
+ other.normalized()
}
- let (a, b, c, d) = u32_from_u128(self);
- sub2rev(&[d, c, b, a], &mut other.data[..]);
- other.normalized()
- }
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ while other.data.len() < 2 {
+ other.data.push(0);
+ }
- #[cfg(u64_digit)]
- #[inline]
- fn sub(self, mut other: BigUint) -> BigUint {
- while other.data.len() < 2 {
- other.data.push(0);
+ let (hi, lo) = big_digit::from_doublebigdigit(self);
+ sub2rev(&[lo, hi], &mut other.data[..]);
+ other.normalized()
}
-
- let (hi, lo) = big_digit::from_doublebigdigit(self);
- sub2rev(&[lo, hi], &mut other.data[..]);
- other.normalized()
- }
+ );
}
impl CheckedSub for BigUint {
@@ -305,7 +305,7 @@
fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
match self.cmp(v) {
Less => None,
- Equal => Some(Zero::zero()),
+ Equal => Some(Self::ZERO),
Greater => Some(self.sub(v)),
}
}
diff --git a/crates/num-bigint/src/lib.rs b/crates/num-bigint/src/lib.rs
index 893b747..6e47479 100644
--- a/crates/num-bigint/src/lib.rs
+++ b/crates/num-bigint/src/lib.rs
@@ -21,12 +21,12 @@
//! ```rust
//! # fn main() {
//! use num_bigint::BigUint;
-//! use num_traits::{Zero, One};
+//! use num_traits::One;
//!
//! // Calculate large fibonacci numbers.
//! fn fib(n: usize) -> BigUint {
-//! let mut f0: BigUint = Zero::zero();
-//! let mut f1: BigUint = One::one();
+//! let mut f0 = BigUint::ZERO;
+//! let mut f1 = BigUint::one();
//! for _ in 0..n {
//! let f2 = f0 + &f1;
//! f0 = f1;
@@ -60,10 +60,10 @@
//!
//! ## Features
//!
-//! The `std` crate feature is enabled by default, and is mandatory before Rust
-//! 1.36 and the stabilized `alloc` crate. If you depend on `num-bigint` with
-//! `default-features = false`, you must manually enable the `std` feature yourself
-//! if your compiler is not new enough.
+//! The `std` crate feature is enabled by default, which enables [`std::error::Error`]
+//! implementations and some internal use of floating point approximations. This can be disabled by
+//! depending on `num-bigint` with `default-features = false`. Either way, the `alloc` crate is
+//! always required for heap allocation of the `BigInt`/`BigUint` digits.
//!
//! ### Random Generation
//!
@@ -78,53 +78,42 @@
//! Note that you must use the version of `rand` that `num-bigint` is compatible
//! with: `0.8`.
//!
+//! ### Arbitrary Big Integers
+//!
+//! `num-bigint` supports `arbitrary` and `quickcheck` features to implement
+//! [`arbitrary::Arbitrary`] and [`quickcheck::Arbitrary`], respectively, for both `BigInt` and
+//! `BigUint`. These are useful for fuzzing and other forms of randomized testing.
+//!
+//! ### Serialization
+//!
+//! The `serde` feature adds implementations of [`Serialize`][serde::Serialize] and
+//! [`Deserialize`][serde::Deserialize] for both `BigInt` and `BigUint`. Their serialized data is
+//! generated portably, regardless of platform differences like the internal digit size.
+//!
//!
//! ## Compatibility
//!
-//! The `num-bigint` crate is tested for rustc 1.31 and greater.
+//! The `num-bigint` crate is tested for rustc 1.60 and greater.
+#![cfg_attr(docsrs, feature(doc_cfg))]
#![doc(html_root_url = "https://docs.rs/num-bigint/0.4")]
#![warn(rust_2018_idioms)]
#![no_std]
-#[cfg(feature = "std")]
-#[macro_use]
-extern crate std;
-
-#[cfg(feature = "std")]
-mod std_alloc {
- pub(crate) use std::borrow::Cow;
- #[cfg(feature = "quickcheck")]
- pub(crate) use std::boxed::Box;
- pub(crate) use std::string::String;
- pub(crate) use std::vec::Vec;
-}
-
-#[cfg(not(feature = "std"))]
#[macro_use]
extern crate alloc;
-#[cfg(not(feature = "std"))]
-mod std_alloc {
- pub(crate) use alloc::borrow::Cow;
- #[cfg(feature = "quickcheck")]
- pub(crate) use alloc::boxed::Box;
- pub(crate) use alloc::string::String;
- pub(crate) use alloc::vec::Vec;
-}
+#[cfg(feature = "std")]
+extern crate std;
use core::fmt;
-#[cfg(feature = "std")]
-use std::error::Error;
#[macro_use]
mod macros;
mod bigint;
-mod biguint;
-
-#[cfg(feature = "rand")]
mod bigrand;
+mod biguint;
#[cfg(target_pointer_width = "32")]
type UsizePromotion = u32;
@@ -176,20 +165,19 @@
}
#[cfg(feature = "std")]
-impl Error for ParseBigIntError {
+#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
+impl std::error::Error for ParseBigIntError {
fn description(&self) -> &str {
self.__description()
}
}
/// The error type returned when a checked conversion regarding big integer fails.
-#[cfg(has_try_from)]
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct TryFromBigIntError<T> {
original: T,
}
-#[cfg(has_try_from)]
impl<T> TryFromBigIntError<T> {
fn new(original: T) -> Self {
TryFromBigIntError { original }
@@ -206,7 +194,8 @@
}
}
-#[cfg(all(feature = "std", has_try_from))]
+#[cfg(feature = "std")]
+#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
impl<T> std::error::Error for TryFromBigIntError<T>
where
T: fmt::Debug,
@@ -216,7 +205,6 @@
}
}
-#[cfg(has_try_from)]
impl<T> fmt::Display for TryFromBigIntError<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
self.__description().fmt(f)
@@ -233,39 +221,29 @@
pub use crate::bigint::ToBigInt;
#[cfg(feature = "rand")]
+#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
pub use crate::bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint};
mod big_digit {
- /// 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 [`BigDigit`] is a [`BigUint`]'s composing element.
+ cfg_digit!(
+ pub(crate) type BigDigit = u32;
+ 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`].
- #[cfg(not(u64_digit))]
- pub(crate) type DoubleBigDigit = u64;
- #[cfg(u64_digit)]
- pub(crate) type DoubleBigDigit = u128;
+ // A [`DoubleBigDigit`] is the internal type used to do the computations. Its
+ // size is the double of the size of [`BigDigit`].
+ cfg_digit!(
+ pub(crate) type DoubleBigDigit = u64;
+ pub(crate) type DoubleBigDigit = u128;
+ );
- /// 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
- #[cfg(not(u64_digit))]
- pub(crate) const BITS: u8 = 32;
- #[cfg(u64_digit)]
- pub(crate) const BITS: u8 = 64;
-
+ pub(crate) const BITS: u8 = BigDigit::BITS as u8;
pub(crate) const HALF_BITS: u8 = BITS / 2;
pub(crate) const HALF: BigDigit = (1 << HALF_BITS) - 1;
- const LO_MASK: DoubleBigDigit = (1 << BITS) - 1;
- pub(crate) const MAX: BigDigit = LO_MASK as BigDigit;
+ pub(crate) const MAX: BigDigit = BigDigit::MAX;
+ const LO_MASK: DoubleBigDigit = MAX as DoubleBigDigit;
#[inline]
fn get_hi(n: DoubleBigDigit) -> BigDigit {
diff --git a/crates/num-bigint/src/macros.rs b/crates/num-bigint/src/macros.rs
index 1618616..f2e21e3 100644
--- a/crates/num-bigint/src/macros.rs
+++ b/crates/num-bigint/src/macros.rs
@@ -1,5 +1,37 @@
#![allow(unused_macros)]
+macro_rules! cfg_32 {
+ ($($any:tt)+) => {
+ #[cfg(not(target_pointer_width = "64"))] $($any)+
+ }
+}
+
+macro_rules! cfg_32_or_test {
+ ($($any:tt)+) => {
+ #[cfg(any(not(target_pointer_width = "64"), test))] $($any)+
+ }
+}
+
+macro_rules! cfg_64 {
+ ($($any:tt)+) => {
+ #[cfg(target_pointer_width = "64")] $($any)+
+ }
+}
+
+macro_rules! cfg_digit {
+ ($item32:item $item64:item) => {
+ cfg_32!($item32);
+ cfg_64!($item64);
+ };
+}
+
+macro_rules! cfg_digit_expr {
+ ($expr32:expr, $expr64:expr) => {
+ cfg_32!($expr32);
+ cfg_64!($expr64);
+ };
+}
+
macro_rules! forward_val_val_binop {
(impl $imp:ident for $res:ty, $method:ident) => {
impl $imp<$res> for $res {
@@ -418,7 +450,7 @@
where
I: Iterator<Item = T>,
{
- iter.fold(Zero::zero(), <$res>::add)
+ iter.fold(Self::ZERO, <$res>::add)
}
}
};
diff --git a/crates/num-bigint/tests/bigint.rs b/crates/num-bigint/tests/bigint.rs
index 75cf81e..fea5232 100644
--- a/crates/num-bigint/tests/bigint.rs
+++ b/crates/num-bigint/tests/bigint.rs
@@ -8,9 +8,6 @@
use std::iter::repeat;
use std::ops::Neg;
use std::{f32, f64};
-use std::{i128, u128};
-use std::{i16, i32, i64, i8, isize};
-use std::{u16, u32, u64, u8, usize};
use num_integer::Integer;
use num_traits::{
diff --git a/crates/num-bigint/tests/bigint_bitwise.rs b/crates/num-bigint/tests/bigint_bitwise.rs
index 6c1e82f..94d92e1 100644
--- a/crates/num-bigint/tests/bigint_bitwise.rs
+++ b/crates/num-bigint/tests/bigint_bitwise.rs
@@ -1,6 +1,5 @@
use num_bigint::{BigInt, Sign, ToBigInt};
use num_traits::ToPrimitive;
-use std::{i32, i64, u32};
enum ValueVec {
N,
diff --git a/crates/num-bigint/tests/biguint.rs b/crates/num-bigint/tests/biguint.rs
index c027771..4e2c625 100644
--- a/crates/num-bigint/tests/biguint.rs
+++ b/crates/num-bigint/tests/biguint.rs
@@ -6,12 +6,9 @@
use std::cmp::Ordering::{Equal, Greater, Less};
use std::collections::hash_map::RandomState;
use std::hash::{BuildHasher, Hash, Hasher};
-use std::i64;
use std::iter::repeat;
use std::str::FromStr;
use std::{f32, f64};
-use std::{i128, u128};
-use std::{u16, u32, u64, u8, usize};
use num_traits::{
pow, CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, Euclid, FromBytes, FromPrimitive, Num,
diff --git a/crates/num-bigint/tests/consts/mod.rs b/crates/num-bigint/tests/consts/mod.rs
index 5d0555d..457fbd3 100644
--- a/crates/num-bigint/tests/consts/mod.rs
+++ b/crates/num-bigint/tests/consts/mod.rs
@@ -16,7 +16,7 @@
(&[1, 2, 2, 1], &[N1, N2], &[0, 1, 3, 1]),
];
-pub const M: u32 = ::std::u32::MAX;
+pub const M: u32 = u32::MAX;
pub const MUL_TRIPLES: &[(&[u32], &[u32], &[u32])] = &[
(&[], &[], &[]),
(&[], &[1], &[]),
diff --git a/crates/num-bigint/tests/roots.rs b/crates/num-bigint/tests/roots.rs
index cfef80c..7110adf 100644
--- a/crates/num-bigint/tests/roots.rs
+++ b/crates/num-bigint/tests/roots.rs
@@ -1,7 +1,6 @@
mod biguint {
use num_bigint::BigUint;
use num_traits::{One, Zero};
- use std::{i32, u32};
fn check<T: Into<BigUint>>(x: T, n: u32) {
let x: BigUint = x.into();
diff --git a/pseudo_crate/Cargo.lock b/pseudo_crate/Cargo.lock
index 0315d99..6e7ff72 100644
--- a/pseudo_crate/Cargo.lock
+++ b/pseudo_crate/Cargo.lock
@@ -3473,11 +3473,10 @@
[[package]]
name = "num-bigint"
-version = "0.4.4"
+version = "0.4.6"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "608e7659b5c3d7cba262d894801b9ec9d00de989e8a82bd4bef91d08da45cdc0"
+checksum = "a5e44f723f1133c9deac646763579fdb3ac745e418f2a7af9cd0c431da1f20b9"
dependencies = [
- "autocfg",
"num-integer",
"num-traits",
]
diff --git a/pseudo_crate/Cargo.toml b/pseudo_crate/Cargo.toml
index 3717891..0b5ce4f 100644
--- a/pseudo_crate/Cargo.toml
+++ b/pseudo_crate/Cargo.toml
@@ -210,7 +210,7 @@
nix = "=0.28.0"
no-panic = "=0.1.33"
nom = "=7.1.3"
-num-bigint = "=0.4.4"
+num-bigint = "=0.4.6"
num-complex = "=0.4.6"
num-derive = "=0.4.2"
num-integer = "=0.1.46"
