summaryrefslogtreecommitdiffstats
path: root/vendor/crypto-bigint
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 12:41:35 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 12:41:35 +0000
commit7e5d7eea9c580ef4b41a765bde624af431942b96 (patch)
tree2c0d9ca12878fc4525650aa4e54d77a81a07cc09 /vendor/crypto-bigint
parentAdding debian version 1.70.0+dfsg1-9. (diff)
downloadrustc-7e5d7eea9c580ef4b41a765bde624af431942b96.tar.xz
rustc-7e5d7eea9c580ef4b41a765bde624af431942b96.zip
Merging upstream version 1.70.0+dfsg2.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/crypto-bigint')
-rw-r--r--vendor/crypto-bigint/.cargo-checksum.json1
-rw-r--r--vendor/crypto-bigint/CHANGELOG.md273
-rw-r--r--vendor/crypto-bigint/Cargo.toml107
-rw-r--r--vendor/crypto-bigint/LICENSE-APACHE201
-rw-r--r--vendor/crypto-bigint/LICENSE-MIT25
-rw-r--r--vendor/crypto-bigint/README.md64
-rw-r--r--vendor/crypto-bigint/src/array.rs41
-rw-r--r--vendor/crypto-bigint/src/checked.rs131
-rw-r--r--vendor/crypto-bigint/src/lib.rs199
-rw-r--r--vendor/crypto-bigint/src/limb.rs189
-rw-r--r--vendor/crypto-bigint/src/limb/add.rs180
-rw-r--r--vendor/crypto-bigint/src/limb/bit_and.rs21
-rw-r--r--vendor/crypto-bigint/src/limb/bit_not.rs19
-rw-r--r--vendor/crypto-bigint/src/limb/bit_or.rs19
-rw-r--r--vendor/crypto-bigint/src/limb/bit_xor.rs19
-rw-r--r--vendor/crypto-bigint/src/limb/bits.rs8
-rw-r--r--vendor/crypto-bigint/src/limb/cmp.rs176
-rw-r--r--vendor/crypto-bigint/src/limb/encoding.rs67
-rw-r--r--vendor/crypto-bigint/src/limb/from.rs76
-rw-r--r--vendor/crypto-bigint/src/limb/mul.rs195
-rw-r--r--vendor/crypto-bigint/src/limb/rand.rs45
-rw-r--r--vendor/crypto-bigint/src/limb/shl.rs73
-rw-r--r--vendor/crypto-bigint/src/limb/shr.rs73
-rw-r--r--vendor/crypto-bigint/src/limb/sub.rs182
-rw-r--r--vendor/crypto-bigint/src/nlimbs.rs29
-rw-r--r--vendor/crypto-bigint/src/non_zero.rs385
-rw-r--r--vendor/crypto-bigint/src/traits.rs227
-rw-r--r--vendor/crypto-bigint/src/uint.rs484
-rw-r--r--vendor/crypto-bigint/src/uint/add.rs189
-rw-r--r--vendor/crypto-bigint/src/uint/add_mod.rs139
-rw-r--r--vendor/crypto-bigint/src/uint/array.rs189
-rw-r--r--vendor/crypto-bigint/src/uint/bit_and.rs145
-rw-r--r--vendor/crypto-bigint/src/uint/bit_not.rs48
-rw-r--r--vendor/crypto-bigint/src/uint/bit_or.rs141
-rw-r--r--vendor/crypto-bigint/src/uint/bit_xor.rs141
-rw-r--r--vendor/crypto-bigint/src/uint/bits.rs55
-rw-r--r--vendor/crypto-bigint/src/uint/cmp.rs196
-rw-r--r--vendor/crypto-bigint/src/uint/concat.rs60
-rw-r--r--vendor/crypto-bigint/src/uint/div.rs496
-rw-r--r--vendor/crypto-bigint/src/uint/encoding.rs278
-rw-r--r--vendor/crypto-bigint/src/uint/encoding/der.rs69
-rw-r--r--vendor/crypto-bigint/src/uint/encoding/rlp.rs79
-rw-r--r--vendor/crypto-bigint/src/uint/from.rs238
-rw-r--r--vendor/crypto-bigint/src/uint/inv_mod.rs62
-rw-r--r--vendor/crypto-bigint/src/uint/mul.rs246
-rw-r--r--vendor/crypto-bigint/src/uint/mul_mod.rs131
-rw-r--r--vendor/crypto-bigint/src/uint/neg_mod.rs68
-rw-r--r--vendor/crypto-bigint/src/uint/rand.rs92
-rw-r--r--vendor/crypto-bigint/src/uint/resize.rs37
-rw-r--r--vendor/crypto-bigint/src/uint/shl.rs134
-rw-r--r--vendor/crypto-bigint/src/uint/shr.rs93
-rw-r--r--vendor/crypto-bigint/src/uint/split.rs58
-rw-r--r--vendor/crypto-bigint/src/uint/sqrt.rs145
-rw-r--r--vendor/crypto-bigint/src/uint/sub.rs192
-rw-r--r--vendor/crypto-bigint/src/uint/sub_mod.rs182
-rw-r--r--vendor/crypto-bigint/src/wrapping.rs108
-rw-r--r--vendor/crypto-bigint/tests/proptests.rs209
57 files changed, 7729 insertions, 0 deletions
diff --git a/vendor/crypto-bigint/.cargo-checksum.json b/vendor/crypto-bigint/.cargo-checksum.json
new file mode 100644
index 000000000..49e1f2cba
--- /dev/null
+++ b/vendor/crypto-bigint/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"CHANGELOG.md":"51183f8239b77b2cf3214eba6cd149953e42088e38eb638a0eeb963ab2514497","Cargo.toml":"d6e917974ab2117117fac4dbb2d14d994c462e85c01f3a85e04410b89467bc60","LICENSE-APACHE":"a9040321c3712d8fd0b09cf52b17445de04a23a10165049ae187cd39e5c86be5","LICENSE-MIT":"90c503b61dee04e1449c323ec34c229dfb68d7adcb96c7e140ee55f70fce2d8e","README.md":"201b065b69baf2ee4e055b0d342864788c5d32744de2d8a8bea1b3dbfa5bfdd6","src/array.rs":"242b83d3b3a89f68e2c7b172df28a30cf6a5a1176c272b0512a6518a138ad5a3","src/checked.rs":"b2bc6e7c8886c7002ab5daa4dcc5c1c7d82a7b41f45d3112c7b623aec07941a9","src/lib.rs":"9a72c010366b0f67f3ef8636c34da5b6891e8f0d7cd8bdaf3a0ed359b3cb1cfa","src/limb.rs":"9cf16fdeef8336bd765a5bb7ff3137cf20d3c61aca049771f5113a3bcaffa1e2","src/limb/add.rs":"a6d02510472feef5d51c9dbdc59f4f9da2e442c5510a488f50b7af62f9a1eb8a","src/limb/bit_and.rs":"019f888b11e16fafbd0518eb5b583094a5e8490f59f458195db9306d86e1adaa","src/limb/bit_not.rs":"0fa7cdec58e1d3058daee88ef26f07ad0ba9e545505c97a130b47ef3fdf46c5a","src/limb/bit_or.rs":"1b5f85eac6768d460070da05b4a1257cceafff2b612b63a609aff3ff48df8480","src/limb/bit_xor.rs":"06acf291a316aa1fa2311bedd1a7aca5170564735c1f0b1103ed9e2c6f24f096","src/limb/bits.rs":"8f21514d463196fc01c9d2e5d13ea77af4ea7e6ee267c6d71f28e5d616811859","src/limb/cmp.rs":"169984e53efd043af5dd9ad0535685ed27cb60e36a80e3da992d40dcca3d255b","src/limb/encoding.rs":"a8962dd9046510f692293be7b049bbeed7ea57d26dcfcdae35dd796cf14bae96","src/limb/from.rs":"6217abd3d2380e099b332946fe87ed856b3a59c0f7885f85e4f1f0aad89fe8d4","src/limb/mul.rs":"342e20b79749683ccf9b77ee90dbbd666a24c6d50c78c187d54f90ad5b032cdd","src/limb/rand.rs":"495d5426ae12072e86435eae765ee8bc6cdee297c0552096ce28bb589600cf94","src/limb/shl.rs":"8d0cd4029375c7a66c0b72e21a8634a805cd5cc8c78320c1466f16ee0b16dbc7","src/limb/shr.rs":"c60b47739213722f7b4e7473d40be2f207484efbf8344cb7920558870aa5169c","src/limb/sub.rs":"6fe15fc5a2dcac9a23a072a4976db432c35805d2afdbfec44f18530f164f03d0","src/nlimbs.rs":"8938fb529a3f71396372df9d651f93ae6e399398e17c391c6d2a0a7352b21512","src/non_zero.rs":"cee6eec57b7489cdf4bbf088dcff554d0f5d9a4932a418ebd0c5d0e5d79503dd","src/traits.rs":"629251720bd7d54fb891c328326cd22fff37963239fb21f6d1afa677d1f9fa44","src/uint.rs":"b5494b6da6ba4f4adae6e6c2eecc0ad1d27728b6ec36e211798a48b33a3e1cf3","src/uint/add.rs":"4613f40921c6f02da14a1b066d949d8b95ea5a47c8d04a72e656c4257d481328","src/uint/add_mod.rs":"e6d938be5315a635348c274e961b07783a4d45b5f510a680b798b31044380cc2","src/uint/array.rs":"87d4daa5eb5a0601a186eb8759261f826e939317f14202564031b7a25b62e799","src/uint/bit_and.rs":"0a863260b07c900c89d3664171e415e3e7889a09c3f368fa6c3dc3ad4e3ffb7b","src/uint/bit_not.rs":"19cd1a760810651d66e488592a4c4d3451207caa269fe14b6efb69ee1acfcc44","src/uint/bit_or.rs":"a44b27ebb8821e8b029f173c4582bd4ff6e487f65c7ecba6861d43110cb1761a","src/uint/bit_xor.rs":"8c2011b1e51fbc8efbb1529d148e29b7e487da2b067f258b279eb32eee4f8504","src/uint/bits.rs":"955f63ad4dc51aabd26ef5c545bd185d99b5e7f5c4164a8da1dc28f39ebce509","src/uint/cmp.rs":"0db7e6f8bb362ae41c9a11e4ed97c79d2c206a9569542b55ccad8d2b29b406f7","src/uint/concat.rs":"b7efee5bb9e0a91cf4b3f24e16c2757de6fcfaec8ed94d7fbebb1fe66d5324e4","src/uint/div.rs":"6a16e6382a12bcce20ed7ad510f346972327fed81e29016e802801780dc0c12c","src/uint/encoding.rs":"566a4a739880c8f83dd3550cf5bbbc1fde5c7f2fb816253ebb46fe36301aa55b","src/uint/encoding/der.rs":"55b26c697d0886cd19e6b32480bbfd0c4ea600f7d89d26721c436685e7941b9b","src/uint/encoding/rlp.rs":"965f485eef2cac0b1316136119b83955d93ab6cb7f71cf93dfc94cb6a7938464","src/uint/from.rs":"25e97ecbe641560103ad611dbfbc5eb89fce08ae14a4a148e096f2b5fc882f7b","src/uint/inv_mod.rs":"e860561ab73822e01a03412589f2a064102830c3cf67b92b2e15ec14a6efebe2","src/uint/mul.rs":"1bbad1aa10897c7ebc90880009eee92896a6b6f0c490f93de7a6e3a97f3d0f18","src/uint/mul_mod.rs":"c0e6480b871606d61454f7e21459cd3264af69348909fcd9d2d761bce650083a","src/uint/neg_mod.rs":"8e37cd1d4f1d69f946be57fda2f8672731c09e334386478df0dcdab700abd0b6","src/uint/rand.rs":"a2b3f60a76e5117dee3320694e3a731fc123fd86c6685c7e63fd0f1578105131","src/uint/resize.rs":"f5c7a693492b02c4e2995f86cf814e87e47ed246bb2a8409df527318b163bec2","src/uint/shl.rs":"67850ed75e2e9acd82fb8dd88438938b7eda2093ddb18ce2ba320d94f0ae0d89","src/uint/shr.rs":"63f862573ece17b693dd20ff610557504b114512b194fed28bfab01961c87360","src/uint/split.rs":"f8038b0d00161a0ce6781b645b7de7fb7b0377dfb4e29c4faa150a685a0d8c67","src/uint/sqrt.rs":"35842add9b503a7f4694940ff5e975756c9f6c8ce0d99c8eecf8a710924c0ec0","src/uint/sub.rs":"37b87756e967b1ffdc4ba6284435940023974c49d4b3ec646d31c228da2e13e5","src/uint/sub_mod.rs":"9bf319958df7abfc8eaa2da740bde7072c41d263647b57312701fc597284f60f","src/wrapping.rs":"8d2ed844ce2978ac4f89d73eb2aca968664266ec811f53e8992717b499564a81","tests/proptests.rs":"58d142bf9666ae7b1b5eaf4a1a2e54d8d646a6a89c1aeaddeab5d22307111c22"},"package":"ef2b4b23cddf68b89b8f8069890e8c270d54e2d5fe1b143820234805e4cb17ef"} \ No newline at end of file
diff --git a/vendor/crypto-bigint/CHANGELOG.md b/vendor/crypto-bigint/CHANGELOG.md
new file mode 100644
index 000000000..58dcb4575
--- /dev/null
+++ b/vendor/crypto-bigint/CHANGELOG.md
@@ -0,0 +1,273 @@
+# Changelog
+All notable changes to this project will be documented in this file.
+
+The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),
+and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
+
+## 0.4.9 (2022-10-11)
+### Added
+- `UInt::from_word` and `::from_wide_word` ([#105])
+- `UInt` modulo operations for special moduli ([#108])
+- Non-const `UInt` decoding from an array ([#110])
+- `const fn` impls of `concat` and `split` ([#111])
+- `Limb` left/right bitshifts ([#112])
+- `UInt::LIMBS` constant ([#114])
+
+### Changed
+- Optimize `UInt::neg_mod` by simply calling `::sub_mod` ([#106])
+- Relax bounds for `UInt::add_mod` and `::sub_mod` ([#104])
+- Always inline `Limb::bitand` ([#109])
+- Faster const decoding of UInt ([#113])
+- Optimize `UInt::neg_mod` ([#127])
+- Faster comparisons ([#128])
+- `UInt::resize` ([#129])
+- `UInt::bit` accessor methods ([#122])
+
+### Fixed
+- Constant-time behaviour for `ct_reduce`/`ct_div_rem` ([#117])
+
+[#104]: https://github.com/RustCrypto/crypto-bigint/pull/104
+[#105]: https://github.com/RustCrypto/crypto-bigint/pull/105
+[#106]: https://github.com/RustCrypto/crypto-bigint/pull/106
+[#108]: https://github.com/RustCrypto/crypto-bigint/pull/108
+[#109]: https://github.com/RustCrypto/crypto-bigint/pull/109
+[#110]: https://github.com/RustCrypto/crypto-bigint/pull/110
+[#111]: https://github.com/RustCrypto/crypto-bigint/pull/111
+[#112]: https://github.com/RustCrypto/crypto-bigint/pull/112
+[#113]: https://github.com/RustCrypto/crypto-bigint/pull/113
+[#114]: https://github.com/RustCrypto/crypto-bigint/pull/114
+[#117]: https://github.com/RustCrypto/crypto-bigint/pull/117
+[#122]: https://github.com/RustCrypto/crypto-bigint/pull/122
+[#127]: https://github.com/RustCrypto/crypto-bigint/pull/127
+[#128]: https://github.com/RustCrypto/crypto-bigint/pull/128
+[#129]: https://github.com/RustCrypto/crypto-bigint/pull/129
+
+## 0.4.8 (2022-06-30)
+### Added
+- `Word` as a replacement for `LimbUInt` ([#88])
+- `WideWord` as a replacement for `WideLimbUInt` ([#88])
+- `UInt::*_words` as a replacement for `UInt::*_uint_array` ([#88])
+
+### Changed
+- Deprecated `*LimbUInt` and `UInt::*_uint_array` ([#88])
+
+[#88]: https://github.com/RustCrypto/crypto-bigint/pull/88
+
+## 0.4.7 (2022-06-12)
+### Added
+- `Encoding` tests ([#93])
+
+### Changed
+- Use const generic impls of `*Mod` traits ([#98])
+
+[#93]: https://github.com/RustCrypto/crypto-bigint/pull/93
+[#98]: https://github.com/RustCrypto/crypto-bigint/pull/98
+
+## 0.4.6 (2022-06-12)
+### Added
+- Impl `ArrayEncoding` for `U576` ([#96])
+
+[#96]: https://github.com/RustCrypto/crypto-bigint/pull/96
+
+## 0.4.5 (2022-06-12)
+### Added
+- `serde` support ([#73])
+- `U576` type alias ([#94])
+
+[#73]: https://github.com/RustCrypto/crypto-bigint/pull/73
+[#94]: https://github.com/RustCrypto/crypto-bigint/pull/94
+
+## 0.4.4 (2022-06-02)
+### Added
+- `UInt::as_uint_array` ([#91])
+
+[#91]: https://github.com/RustCrypto/crypto-bigint/pull/91
+
+## 0.4.3 (2022-05-31)
+### Added
+- Impl `AsRef`/`AsMut<[LimbUInt]>` for `UInt` ([#89])
+
+[#89]: https://github.com/RustCrypto/crypto-bigint/pull/89
+
+## 0.4.2 (2022-05-18)
+### Added
+- `UInt::inv_mod2k` ([#86])
+
+### Fixed
+- Wrong results for remainder ([#84])
+
+[#84]: https://github.com/RustCrypto/crypto-bigint/pull/84
+[#86]: https://github.com/RustCrypto/crypto-bigint/pull/86
+
+## 0.4.1 (2022-05-10)
+### Fixed
+- Bug in `from_le_slice` ([#82])
+
+[#82]: https://github.com/RustCrypto/crypto-bigint/pull/82
+
+## 0.4.0 (2022-05-08) [YANKED]
+
+NOTE: this release was yanked due to [#82].
+
+### Added
+- Const-friendly `NonZero` from `UInt` ([#56])
+- Optional `der` feature ([#61], [#80])
+
+### Changed
+- Use `const_panic`; MSRV 1.57 ([#60])
+- 2021 edition ([#60])
+
+### Fixed
+- Pad limbs with zeros when displaying hexadecimal representation ([#74])
+
+[#56]: https://github.com/RustCrypto/crypto-bigint/pull/56
+[#60]: https://github.com/RustCrypto/crypto-bigint/pull/60
+[#61]: https://github.com/RustCrypto/crypto-bigint/pull/61
+[#74]: https://github.com/RustCrypto/crypto-bigint/pull/74
+[#80]: https://github.com/RustCrypto/crypto-bigint/pull/80
+
+## 0.3.2 (2021-11-17)
+### Added
+- `Output = Self` to all bitwise ops on `Integer` trait ([#53])
+
+[#53]: https://github.com/RustCrypto/crypto-bigint/pull/53
+
+## 0.3.1 (2021-11-17)
+### Added
+- Bitwise ops to `Integer` trait ([#51])
+
+[#51]: https://github.com/RustCrypto/crypto-bigint/pull/51
+
+## 0.3.0 (2021-11-14) [YANKED]
+### Added
+- Bitwise `Xor`/`Not` operations ([#27])
+- `Zero` trait ([#35])
+- `Checked*` traits ([#41])
+- `prelude` module ([#45])
+- `saturating_*` ops ([#47])
+
+### Changed
+- Rust 2021 edition upgrade; MSRV 1.56 ([#33])
+- Reverse ordering of `UInt::mul_wide` return tuple ([#34])
+- Have `Div` and `Rem` impls always take `NonZero` args ([#39])
+- Rename `limb::Inner` to `LimbUInt` ([#40])
+- Make `limb` module private ([#40])
+- Use `Zero`/`Integer` traits for `is_zero`, `is_odd`, and `is_even` ([#46])
+
+### Fixed
+- `random_mod` performance for small moduli ([#36])
+- `NonZero` moduli ([#36])
+
+### Removed
+- Deprecated `LIMB_BYTES` constant ([#43])
+
+[#27]: https://github.com/RustCrypto/crypto-bigint/pull/27
+[#33]: https://github.com/RustCrypto/crypto-bigint/pull/33
+[#34]: https://github.com/RustCrypto/crypto-bigint/pull/34
+[#35]: https://github.com/RustCrypto/crypto-bigint/pull/35
+[#36]: https://github.com/RustCrypto/crypto-bigint/pull/36
+[#39]: https://github.com/RustCrypto/crypto-bigint/pull/39
+[#40]: https://github.com/RustCrypto/crypto-bigint/pull/40
+[#41]: https://github.com/RustCrypto/crypto-bigint/pull/41
+[#43]: https://github.com/RustCrypto/crypto-bigint/pull/43
+[#45]: https://github.com/RustCrypto/crypto-bigint/pull/45
+[#46]: https://github.com/RustCrypto/crypto-bigint/pull/46
+[#47]: https://github.com/RustCrypto/crypto-bigint/pull/47
+
+## 0.2.11 (2021-10-16)
+### Added
+- `AddMod` proptests ([#24])
+- Bitwise `And`/`Or` operations ([#25])
+
+[#24]: https://github.com/RustCrypto/crypto-bigint/pull/24
+[#25]: https://github.com/RustCrypto/crypto-bigint/pull/25
+
+## 0.2.10 (2021-09-21)
+### Added
+- `ArrayDecoding` trait ([#12])
+- `NonZero` wrapper ([#13], [#16])
+- Impl `Div`/`Rem` for `NonZero<UInt>` ([#14])
+
+[#12]: https://github.com/RustCrypto/crypto-bigint/pull/12
+[#13]: https://github.com/RustCrypto/crypto-bigint/pull/13
+[#14]: https://github.com/RustCrypto/crypto-bigint/pull/14
+[#16]: https://github.com/RustCrypto/crypto-bigint/pull/16
+
+## 0.2.9 (2021-09-16)
+### Added
+- `UInt::sqrt` ([#9])
+
+### Changed
+- Make `UInt` division similar to other interfaces ([#8])
+
+[#8]: https://github.com/RustCrypto/crypto-bigint/pull/8
+[#9]: https://github.com/RustCrypto/crypto-bigint/pull/9
+
+## 0.2.8 (2021-09-14) [YANKED]
+### Added
+- Implement constant-time division and modulo operations
+
+### Changed
+- Moved from RustCrypto/utils to RustCrypto/crypto-bigint repo ([#2])
+
+[#2]: https://github.com/RustCrypto/crypto-bigint/pull/2
+
+## 0.2.7 (2021-09-12)
+### Added
+- `UInt::shl_vartime`
+
+### Fixed
+- `add_mod` overflow handling
+
+## 0.2.6 (2021-09-08)
+### Added
+- `Integer` trait
+- `ShrAssign` impl for `UInt`
+- Recursive Length Prefix (RLP) encoding support for `UInt`
+
+## 0.2.5 (2021-09-02)
+### Fixed
+- `ConditionallySelectable` impl for `UInt`
+
+## 0.2.4 (2021-08-23) [YANKED]
+### Added
+- Expose `limb` module
+- `[limb::Inner; LIMBS]` conversions for `UInt`
+- Bitwise right shift support for `UInt` ([#586], [#590])
+
+## 0.2.3 (2021-08-16) [YANKED]
+### Fixed
+- `UInt::wrapping_mul`
+
+### Added
+- Implement the `Hash` trait for `UInt` and `Limb`
+
+## 0.2.2 (2021-06-26) [YANKED]
+### Added
+- `Limb::is_odd` and `UInt::is_odd`
+- `UInt::new`
+- `rand` feature
+
+### Changed
+- Deprecate `LIMB_BYTES` constant
+- Make `Limb`'s `Inner` value public
+
+## 0.2.1 (2021-06-21) [YANKED]
+### Added
+- `Limb` newtype
+- Target-specific rustdocs
+
+## 0.2.0 (2021-06-07) [YANKED]
+### Added
+- `ConstantTimeGreater`/`ConstantTimeLess` impls for UInt
+- `From` conversions between `UInt` and limb arrays
+- `zeroize` feature
+- Additional `ArrayEncoding::ByteSize` bounds
+- `UInt::into_limbs`
+- `Encoding` trait
+
+### Removed
+- `NumBits`/`NumBytes` traits; use `Encoding` instead
+
+## 0.1.0 (2021-05-30)
+- Initial release
diff --git a/vendor/crypto-bigint/Cargo.toml b/vendor/crypto-bigint/Cargo.toml
new file mode 100644
index 000000000..20d8afd9f
--- /dev/null
+++ b/vendor/crypto-bigint/Cargo.toml
@@ -0,0 +1,107 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies.
+#
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
+
+[package]
+edition = "2021"
+rust-version = "1.57"
+name = "crypto-bigint"
+version = "0.4.9"
+authors = ["RustCrypto Developers"]
+description = """
+Pure Rust implementation of a big integer library which has been designed from
+the ground-up for use in cryptographic applications. Provides constant-time,
+no_std-friendly implementations of modern formulas using const generics.
+"""
+readme = "README.md"
+keywords = [
+ "arbitrary",
+ "crypto",
+ "bignum",
+ "integer",
+ "precision",
+]
+categories = [
+ "algorithms",
+ "cryptography",
+ "data-structures",
+ "mathematics",
+ "no-std",
+]
+license = "Apache-2.0 OR MIT"
+repository = "https://github.com/RustCrypto/crypto-bigint"
+resolver = "2"
+
+[package.metadata.docs.rs]
+all-features = true
+rustdoc-args = [
+ "--cfg",
+ "docsrs",
+]
+
+[dependencies.der]
+version = "0.6"
+optional = true
+default-features = false
+
+[dependencies.generic-array]
+version = "0.14"
+optional = true
+
+[dependencies.rand_core]
+version = "0.6"
+optional = true
+
+[dependencies.rlp]
+version = "0.5"
+optional = true
+default-features = false
+
+[dependencies.serdect]
+version = "0.1"
+optional = true
+default-features = false
+
+[dependencies.subtle]
+version = "2.4"
+default-features = false
+
+[dependencies.zeroize]
+version = "1"
+optional = true
+default-features = false
+
+[dev-dependencies.bincode]
+version = "1"
+
+[dev-dependencies.hex-literal]
+version = "0.3"
+
+[dev-dependencies.num-bigint]
+version = "0.4"
+
+[dev-dependencies.num-traits]
+version = "0.2"
+
+[dev-dependencies.proptest]
+version = "1"
+
+[dev-dependencies.rand_chacha]
+version = "0.3"
+
+[dev-dependencies.rand_core]
+version = "0.6"
+features = ["std"]
+
+[features]
+alloc = []
+default = ["rand"]
+rand = ["rand_core/std"]
+serde = ["serdect"]
diff --git a/vendor/crypto-bigint/LICENSE-APACHE b/vendor/crypto-bigint/LICENSE-APACHE
new file mode 100644
index 000000000..78173fa2e
--- /dev/null
+++ b/vendor/crypto-bigint/LICENSE-APACHE
@@ -0,0 +1,201 @@
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+END OF TERMS AND CONDITIONS
+
+APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "[]"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+Copyright [yyyy] [name of copyright owner]
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
diff --git a/vendor/crypto-bigint/LICENSE-MIT b/vendor/crypto-bigint/LICENSE-MIT
new file mode 100644
index 000000000..c869ada57
--- /dev/null
+++ b/vendor/crypto-bigint/LICENSE-MIT
@@ -0,0 +1,25 @@
+Copyright (c) 2021 The RustCrypto Project Developers
+
+Permission is hereby granted, free of charge, to any
+person obtaining a copy of this software and associated
+documentation files (the "Software"), to deal in the
+Software without restriction, including without
+limitation the rights to use, copy, modify, merge,
+publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software
+is furnished to do so, subject to the following
+conditions:
+
+The above copyright notice and this permission notice
+shall be included in all copies or substantial portions
+of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
+ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
+PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
+SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
diff --git a/vendor/crypto-bigint/README.md b/vendor/crypto-bigint/README.md
new file mode 100644
index 000000000..f4e3daba9
--- /dev/null
+++ b/vendor/crypto-bigint/README.md
@@ -0,0 +1,64 @@
+# [RustCrypto]: Cryptographic Big Integers
+
+[![crate][crate-image]][crate-link]
+[![Docs][docs-image]][docs-link]
+[![Build Status][build-image]][build-link]
+![Apache2/MIT licensed][license-image]
+![Rust Version][rustc-image]
+[![Project Chat][chat-image]][chat-link]
+
+Pure Rust implementation of a big integer library which has been designed from
+the ground-up for use in cryptographic applications.
+
+Provides constant-time, `no_std`-friendly implementations of modern formulas
+using const generics.
+
+[Documentation][docs-link]
+
+## Goals
+
+- No heap allocations. `no_std`-friendly.
+- Constant-time by default. Variable-time functions are explicitly marked as such.
+- Leverage what is possible today with const generics on `stable` rust.
+- Support `const fn` as much as possible, including decoding big integers from
+ bytes/hex and performing arithmetic operations on them, with the goal of
+ being able to compute values at compile-time.
+
+## Minimum Supported Rust Version
+
+This crate requires **Rust 1.57** at a minimum.
+
+We may change the MSRV in the future, but it will be accompanied by a minor
+version bump.
+
+## License
+
+Licensed under either of:
+
+- [Apache License, Version 2.0](http://www.apache.org/licenses/LICENSE-2.0)
+- [MIT license](http://opensource.org/licenses/MIT)
+
+at your option.
+
+### Contribution
+
+Unless you explicitly state otherwise, any contribution intentionally submitted
+for inclusion in the work by you, as defined in the Apache-2.0 license, shall be
+dual licensed as above, without any additional terms or conditions.
+
+[//]: # (badges)
+
+[crate-image]: https://buildstats.info/crate/crypto-bigint
+[crate-link]: https://crates.io/crates/crypto-bigint
+[docs-image]: https://docs.rs/crypto-bigint/badge.svg
+[docs-link]: https://docs.rs/crypto-bigint/
+[build-image]: https://github.com/RustCrypto/crypto-bigint/actions/workflows/crypto-bigint.yml/badge.svg
+[build-link]: https://github.com/RustCrypto/crypto-bigint/actions/workflows/crypto-bigint.yml
+[license-image]: https://img.shields.io/badge/license-Apache2.0/MIT-blue.svg
+[rustc-image]: https://img.shields.io/badge/rustc-1.57+-blue.svg
+[chat-image]: https://img.shields.io/badge/zulip-join_chat-blue.svg
+[chat-link]: https://rustcrypto.zulipchat.com/#narrow/stream/300602-crypto-bigint
+
+[//]: # (links)
+
+[RustCrypto]: https://github.com/rustcrypto
diff --git a/vendor/crypto-bigint/src/array.rs b/vendor/crypto-bigint/src/array.rs
new file mode 100644
index 000000000..ea4f437ef
--- /dev/null
+++ b/vendor/crypto-bigint/src/array.rs
@@ -0,0 +1,41 @@
+//! Interop support for `generic-array`
+
+use crate::{Encoding, Integer};
+use core::ops::Add;
+use generic_array::{typenum::Unsigned, ArrayLength, GenericArray};
+
+/// Alias for a byte array whose size is defined by [`ArrayEncoding::ByteSize`].
+#[cfg_attr(docsrs, doc(cfg(feature = "generic-array")))]
+pub type ByteArray<T> = GenericArray<u8, <T as ArrayEncoding>::ByteSize>;
+
+/// Support for encoding a big integer as a `GenericArray`.
+#[cfg_attr(docsrs, doc(cfg(feature = "generic-array")))]
+pub trait ArrayEncoding: Encoding {
+ /// Size of a byte array which encodes a big integer.
+ type ByteSize: ArrayLength<u8> + Add + Eq + Ord + Unsigned;
+
+ /// Deserialize from a big-endian byte array.
+ fn from_be_byte_array(bytes: ByteArray<Self>) -> Self;
+
+ /// Deserialize from a little-endian byte array.
+ fn from_le_byte_array(bytes: ByteArray<Self>) -> Self;
+
+ /// Serialize to a big-endian byte array.
+ fn to_be_byte_array(&self) -> ByteArray<Self>;
+
+ /// Serialize to a little-endian byte array.
+ fn to_le_byte_array(&self) -> ByteArray<Self>;
+}
+
+/// Support for decoding a `GenericArray` as a big integer.
+#[cfg_attr(docsrs, doc(cfg(feature = "generic-array")))]
+pub trait ArrayDecoding {
+ /// Big integer which decodes a `GenericArray`.
+ type Output: ArrayEncoding + Integer;
+
+ /// Deserialize from a big-endian `GenericArray`.
+ fn into_uint_be(self) -> Self::Output;
+
+ /// Deserialize from a little-endian `GenericArray`.
+ fn into_uint_le(self) -> Self::Output;
+}
diff --git a/vendor/crypto-bigint/src/checked.rs b/vendor/crypto-bigint/src/checked.rs
new file mode 100644
index 000000000..e02317e32
--- /dev/null
+++ b/vendor/crypto-bigint/src/checked.rs
@@ -0,0 +1,131 @@
+//! Checked arithmetic.
+
+use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
+
+#[cfg(feature = "serde")]
+use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
+
+/// Provides intentionally-checked arithmetic on `T`.
+///
+/// Internally this leverages the [`CtOption`] type from the [`subtle`] crate
+/// in order to handle overflows in constant time.
+#[derive(Copy, Clone, Debug)]
+pub struct Checked<T>(pub CtOption<T>);
+
+impl<T> Checked<T> {
+ /// Create a new checked arithmetic wrapper for the given value.
+ pub fn new(val: T) -> Self {
+ Self(CtOption::new(val, Choice::from(1)))
+ }
+}
+
+impl<T> Default for Checked<T>
+where
+ T: Default,
+{
+ fn default() -> Self {
+ Self::new(T::default())
+ }
+}
+
+impl<T: ConditionallySelectable> ConditionallySelectable for Checked<T> {
+ #[inline]
+ fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
+ Self(CtOption::conditional_select(&a.0, &b.0, choice))
+ }
+}
+
+impl<T: ConstantTimeEq> ConstantTimeEq for Checked<T> {
+ #[inline]
+ fn ct_eq(&self, rhs: &Self) -> Choice {
+ self.0.ct_eq(&rhs.0)
+ }
+}
+
+impl<T> From<Checked<T>> for CtOption<T> {
+ fn from(checked: Checked<T>) -> CtOption<T> {
+ checked.0
+ }
+}
+
+impl<T> From<CtOption<T>> for Checked<T> {
+ fn from(ct_option: CtOption<T>) -> Checked<T> {
+ Checked(ct_option)
+ }
+}
+
+impl<T> From<Checked<T>> for Option<T> {
+ fn from(checked: Checked<T>) -> Option<T> {
+ checked.0.into()
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de, T: Default + Deserialize<'de>> Deserialize<'de> for Checked<T> {
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ let value = Option::<T>::deserialize(deserializer)?;
+ let choice = Choice::from(value.is_some() as u8);
+ Ok(Self(CtOption::new(value.unwrap_or_default(), choice)))
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de, T: Copy + Serialize> Serialize for Checked<T> {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ Option::<T>::from(self.0).serialize(serializer)
+ }
+}
+
+#[cfg(all(test, feature = "serde"))]
+mod tests {
+ use crate::{Checked, U64};
+ use subtle::{Choice, ConstantTimeEq, CtOption};
+
+ #[test]
+ fn serde() {
+ let test = Checked::new(U64::from_u64(0x0011223344556677));
+
+ let serialized = bincode::serialize(&test).unwrap();
+ let deserialized: Checked<U64> = bincode::deserialize(&serialized).unwrap();
+
+ assert!(bool::from(test.ct_eq(&deserialized)));
+
+ let test = Checked::new(U64::ZERO) - Checked::new(U64::ONE);
+ assert!(bool::from(
+ test.ct_eq(&Checked(CtOption::new(U64::ZERO, Choice::from(0))))
+ ));
+
+ let serialized = bincode::serialize(&test).unwrap();
+ let deserialized: Checked<U64> = bincode::deserialize(&serialized).unwrap();
+
+ assert!(bool::from(test.ct_eq(&deserialized)));
+ }
+
+ #[test]
+ fn serde_owned() {
+ let test = Checked::new(U64::from_u64(0x0011223344556677));
+
+ let serialized = bincode::serialize(&test).unwrap();
+ let deserialized: Checked<U64> = bincode::deserialize_from(serialized.as_slice()).unwrap();
+
+ assert!(bool::from(test.ct_eq(&deserialized)));
+
+ let test = Checked::new(U64::ZERO) - Checked::new(U64::ONE);
+ assert!(bool::from(
+ test.ct_eq(&Checked(CtOption::new(U64::ZERO, Choice::from(0))))
+ ));
+
+ let serialized = bincode::serialize(&test).unwrap();
+ let deserialized: Checked<U64> = bincode::deserialize_from(serialized.as_slice()).unwrap();
+
+ assert!(bool::from(test.ct_eq(&deserialized)));
+ }
+}
diff --git a/vendor/crypto-bigint/src/lib.rs b/vendor/crypto-bigint/src/lib.rs
new file mode 100644
index 000000000..4d376421c
--- /dev/null
+++ b/vendor/crypto-bigint/src/lib.rs
@@ -0,0 +1,199 @@
+#![no_std]
+#![cfg_attr(docsrs, feature(doc_cfg))]
+#![doc = include_str!("../README.md")]
+#![doc(
+ html_logo_url = "https://raw.githubusercontent.com/RustCrypto/meta/master/logo.svg",
+ html_favicon_url = "https://raw.githubusercontent.com/RustCrypto/meta/master/logo.svg"
+)]
+#![deny(unsafe_code)]
+#![warn(
+ clippy::unwrap_used,
+ missing_docs,
+ missing_debug_implementations,
+ missing_copy_implementations,
+ rust_2018_idioms,
+ trivial_casts,
+ trivial_numeric_casts,
+ unused_qualifications
+)]
+
+//! ## Usage
+//!
+//! This crate defines a [`UInt`] type which is const generic around an inner
+//! [`Limb`] array, where a [`Limb`] is a newtype for a word-sized integer.
+//! Thus large integers are represented as a arrays of smaller integers which
+//! are sized appropriately for the CPU, giving us some assurances of how
+//! arithmetic operations over those smaller integers will behave.
+//!
+//! To obtain appropriately sized integers regardless of what a given CPU's
+//! word size happens to be, a number of portable type aliases are provided for
+//! integer sizes commonly used in cryptography, for example:
+//! [`U128`], [`U384`], [`U256`], [`U2048`], [`U3072`], [`U4096`].
+//!
+//! ### `const fn` usage
+//!
+//! The [`UInt`] type provides a number of `const fn` inherent methods which
+//! can be used for initializing and performing arithmetic on big integers in
+//! const contexts:
+//!
+//! ```
+//! use crypto_bigint::U256;
+//!
+//! // Parse a constant from a big endian hexadecimal string.
+//! pub const MODULUS: U256 =
+//! U256::from_be_hex("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551");
+//!
+//! // Compute `MODULUS` shifted right by 1 at compile time
+//! pub const MODULUS_SHR1: U256 = MODULUS.shr_vartime(1);
+//! ```
+//!
+//! ### Trait-based usage
+//!
+//! The [`UInt`] type itself does not implement the standard arithmetic traits
+//! such as [`Add`], [`Sub`], [`Mul`], and [`Div`].
+//!
+//! To use these traits you must first pick a wrapper type which determines
+//! overflow behavior: [`Wrapping`] or [`Checked`].
+//!
+//! #### Wrapping arithmetic
+//!
+//! ```
+//! use crypto_bigint::{U256, Wrapping};
+//!
+//! let a = Wrapping(U256::MAX);
+//! let b = Wrapping(U256::ONE);
+//! let c = a + b;
+//!
+//! // `MAX` + 1 wraps back around to zero
+//! assert_eq!(c.0, U256::ZERO);
+//! ```
+//!
+//! #### Checked arithmetic
+//!
+//! ```
+//! use crypto_bigint::{U256, Checked};
+//!
+//! let a = Checked::new(U256::ONE);
+//! let b = Checked::new(U256::from(2u8));
+//! let c = a + b;
+//! assert_eq!(c.0.unwrap(), U256::from(3u8))
+//! ```
+//!
+//! ### Modular arithmetic
+//!
+//! This library has initial support for modular arithmetic in the form of the
+//! [`AddMod`], [`SubMod`], [`NegMod`], and [`MulMod`] traits, as well as the
+//! support for the [`Rem`] trait when used with a [`NonZero`] operand.
+//!
+//! ```
+//! use crypto_bigint::{AddMod, U256};
+//!
+//! // mod 3
+//! let modulus = U256::from(3u8);
+//!
+//! // 1 + 1 mod 3 = 2
+//! let a = U256::ONE.add_mod(&U256::ONE, &modulus);
+//! assert_eq!(a, U256::from(2u8));
+//!
+//! // 2 + 1 mod 3 = 0
+//! let b = a.add_mod(&U256::ONE, &modulus);
+//! assert_eq!(b, U256::ZERO);
+//! ```
+//!
+//! ### Random number generation
+//!
+//! When the `rand_core` or `rand` features of this crate are enabled, it's
+//! possible to generate random numbers using any [`CryptoRng`] by using the
+//! [`Random`] trait:
+//!
+//! ```
+//! # #[cfg(feature = "rand")]
+//! # {
+//! use crypto_bigint::{Random, U256, rand_core::OsRng};
+//!
+//! let n = U256::random(&mut OsRng);
+//! # }
+//! ```
+//!
+//! #### Modular random number generation
+//!
+//! The [`RandomMod`] trait supports generating random numbers with a uniform
+//! distribution around a given [`NonZero`] modulus.
+//!
+//! ```
+//! # #[cfg(feature = "rand")]
+//! # {
+//! use crypto_bigint::{NonZero, RandomMod, U256, rand_core::OsRng};
+//!
+//! let modulus = NonZero::new(U256::from(3u8)).unwrap();
+//! let n = U256::random_mod(&mut OsRng, &modulus);
+//! # }
+//! ```
+//!
+//! [`Add`]: core::ops::Add
+//! [`Div`]: core::ops::Div
+//! [`Mul`]: core::ops::Mul
+//! [`Rem`]: core::ops::Rem
+//! [`Sub`]: core::ops::Sub
+//! [`CryptoRng`]: rand_core::CryptoRng
+
+#[cfg(all(feature = "alloc", test))]
+extern crate alloc;
+
+#[macro_use]
+mod nlimbs;
+
+#[cfg(feature = "generic-array")]
+mod array;
+mod checked;
+mod limb;
+mod non_zero;
+mod traits;
+mod uint;
+mod wrapping;
+
+pub use crate::{
+ checked::Checked,
+ limb::{Limb, WideWord, Word},
+ non_zero::NonZero,
+ traits::*,
+ uint::*,
+ wrapping::Wrapping,
+};
+pub use subtle;
+
+// TODO(tarcieri): remove these in the next breaking release
+#[allow(deprecated)]
+pub use crate::limb::{LimbUInt, WideLimbUInt};
+
+pub(crate) use limb::{SignedWord, WideSignedWord};
+
+#[cfg(feature = "generic-array")]
+pub use {
+ crate::array::{ArrayDecoding, ArrayEncoding, ByteArray},
+ generic_array::{self, typenum::consts},
+};
+
+#[cfg(feature = "rand_core")]
+pub use rand_core;
+
+#[cfg(feature = "rlp")]
+pub use rlp;
+
+#[cfg(feature = "zeroize")]
+pub use zeroize;
+
+/// Import prelude for this crate: includes important traits.
+pub mod prelude {
+ pub use crate::traits::*;
+
+ #[cfg(feature = "generic-array")]
+ pub use crate::array::{ArrayDecoding, ArrayEncoding};
+}
+
+#[cfg(sidefuzz)]
+#[no_mangle]
+pub extern "C" fn fuzz() {
+ let input = sidefuzz::fetch_input(32); // 32 bytes of of fuzzing input as a &[u8]
+ sidefuzz::black_box(my_hopefully_constant_fn(input));
+}
diff --git a/vendor/crypto-bigint/src/limb.rs b/vendor/crypto-bigint/src/limb.rs
new file mode 100644
index 000000000..df3ae7a72
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb.rs
@@ -0,0 +1,189 @@
+//! Big integers are represented as an array of smaller CPU word-size integers
+//! called "limbs".
+
+#![allow(clippy::derive_hash_xor_eq)]
+
+mod add;
+mod bit_and;
+mod bit_not;
+mod bit_or;
+mod bit_xor;
+mod bits;
+mod cmp;
+mod encoding;
+mod from;
+mod mul;
+mod shl;
+mod shr;
+mod sub;
+
+#[cfg(feature = "rand_core")]
+mod rand;
+
+use crate::Zero;
+use core::fmt;
+use subtle::{Choice, ConditionallySelectable};
+
+#[cfg(feature = "serde")]
+use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
+
+#[cfg(not(any(target_pointer_width = "32", target_pointer_width = "64")))]
+compile_error!("this crate builds on 32-bit and 64-bit platforms only");
+
+//
+// 32-bit definitions
+//
+
+/// Inner integer type that the [`Limb`] newtype wraps.
+#[cfg(target_pointer_width = "32")]
+pub type Word = u32;
+
+/// Signed integer type that corresponds to [`Word`].
+#[cfg(target_pointer_width = "32")]
+pub(crate) type SignedWord = i32;
+
+/// Unsigned wide integer type: double the width of [`Word`].
+#[cfg(target_pointer_width = "32")]
+pub type WideWord = u64;
+
+/// Signed wide integer type: double the width of [`Limb`].
+#[cfg(target_pointer_width = "32")]
+pub(crate) type WideSignedWord = i64;
+
+//
+// 64-bit definitions
+//
+
+/// Unsigned integer type that the [`Limb`] newtype wraps.
+#[cfg(target_pointer_width = "64")]
+pub type Word = u64;
+
+/// Signed integer type that corresponds to [`Word`].
+#[cfg(target_pointer_width = "64")]
+pub(crate) type SignedWord = i64;
+
+/// Wide integer type: double the width of [`Word`].
+#[cfg(target_pointer_width = "64")]
+pub type WideWord = u128;
+
+/// Signed wide integer type: double the width of [`SignedWord`].
+#[cfg(target_pointer_width = "64")]
+pub(crate) type WideSignedWord = i128;
+
+//
+// Deprecated legacy names
+//
+
+// TODO(tarcieri): remove these in the next breaking release
+
+/// Deprecated: unsigned integer type that the [`Limb`] newtype wraps.
+#[deprecated(since = "0.4.8", note = "please use `Word` instead")]
+pub type LimbUInt = Word;
+
+/// Deprecated: wide integer type which is double the width of [`Word`].
+#[deprecated(since = "0.4.8", note = "please use `WideWord` instead")]
+pub type WideLimbUInt = WideWord;
+
+/// Highest bit in a [`Limb`].
+pub(crate) const HI_BIT: usize = Limb::BIT_SIZE - 1;
+
+/// Big integers are represented as an array of smaller CPU word-size integers
+/// called "limbs".
+#[derive(Copy, Clone, Debug, Default, Hash)]
+#[repr(transparent)]
+pub struct Limb(pub Word);
+
+impl Limb {
+ /// The value `0`.
+ pub const ZERO: Self = Limb(0);
+
+ /// The value `1`.
+ pub const ONE: Self = Limb(1);
+
+ /// Maximum value this [`Limb`] can express.
+ pub const MAX: Self = Limb(Word::MAX);
+
+ // 32-bit
+
+ /// Size of the inner integer in bits.
+ #[cfg(target_pointer_width = "32")]
+ pub const BIT_SIZE: usize = 32;
+ /// Size of the inner integer in bytes.
+ #[cfg(target_pointer_width = "32")]
+ pub const BYTE_SIZE: usize = 4;
+
+ // 64-bit
+
+ /// Size of the inner integer in bits.
+ #[cfg(target_pointer_width = "64")]
+ pub const BIT_SIZE: usize = 64;
+ /// Size of the inner integer in bytes.
+ #[cfg(target_pointer_width = "64")]
+ pub const BYTE_SIZE: usize = 8;
+
+ /// Return `a` if `c`==0 or `b` if `c`==`Word::MAX`.
+ ///
+ /// Const-friendly: we can't yet use `subtle` in `const fn` contexts.
+ #[inline]
+ pub(crate) const fn ct_select(a: Self, b: Self, c: Word) -> Self {
+ Self(a.0 ^ (c & (a.0 ^ b.0)))
+ }
+}
+
+impl ConditionallySelectable for Limb {
+ #[inline]
+ fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
+ Self(Word::conditional_select(&a.0, &b.0, choice))
+ }
+}
+
+impl Zero for Limb {
+ const ZERO: Self = Self::ZERO;
+}
+
+impl fmt::Display for Limb {
+ #[inline]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::UpperHex::fmt(self, f)
+ }
+}
+
+impl fmt::LowerHex for Limb {
+ #[inline]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "{:0width$x}", &self.0, width = Self::BYTE_SIZE * 2)
+ }
+}
+
+impl fmt::UpperHex for Limb {
+ #[inline]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "{:0width$X}", &self.0, width = Self::BYTE_SIZE * 2)
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de> Deserialize<'de> for Limb {
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ Ok(Self(Word::deserialize(deserializer)?))
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de> Serialize for Limb {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ self.0.serialize(serializer)
+ }
+}
+
+#[cfg(feature = "zeroize")]
+#[cfg_attr(docsrs, doc(cfg(feature = "zeroize")))]
+impl zeroize::DefaultIsZeroes for Limb {}
diff --git a/vendor/crypto-bigint/src/limb/add.rs b/vendor/crypto-bigint/src/limb/add.rs
new file mode 100644
index 000000000..ddeda9e67
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/add.rs
@@ -0,0 +1,180 @@
+//! Limb addition
+
+use crate::{Checked, CheckedAdd, Limb, WideWord, Word, Wrapping, Zero};
+use core::ops::{Add, AddAssign};
+use subtle::CtOption;
+
+impl Limb {
+ /// Computes `self + rhs + carry`, returning the result along with the new carry.
+ #[inline(always)]
+ pub const fn adc(self, rhs: Limb, carry: Limb) -> (Limb, Limb) {
+ let a = self.0 as WideWord;
+ let b = rhs.0 as WideWord;
+ let carry = carry.0 as WideWord;
+ let ret = a + b + carry;
+ (Limb(ret as Word), Limb((ret >> Self::BIT_SIZE) as Word))
+ }
+
+ /// Perform saturating addition.
+ #[inline]
+ pub const fn saturating_add(&self, rhs: Self) -> Self {
+ Limb(self.0.saturating_add(rhs.0))
+ }
+
+ /// Perform wrapping addition, discarding overflow.
+ #[inline(always)]
+ pub const fn wrapping_add(&self, rhs: Self) -> Self {
+ Limb(self.0.wrapping_add(rhs.0))
+ }
+}
+
+impl CheckedAdd for Limb {
+ type Output = Self;
+
+ #[inline]
+ fn checked_add(&self, rhs: Self) -> CtOption<Self> {
+ let (result, carry) = self.adc(rhs, Limb::ZERO);
+ CtOption::new(result, carry.is_zero())
+ }
+}
+
+impl Add for Wrapping<Limb> {
+ type Output = Self;
+
+ fn add(self, rhs: Self) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_add(rhs.0))
+ }
+}
+
+impl Add<&Wrapping<Limb>> for Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn add(self, rhs: &Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_add(rhs.0))
+ }
+}
+
+impl Add<Wrapping<Limb>> for &Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn add(self, rhs: Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_add(rhs.0))
+ }
+}
+
+impl Add<&Wrapping<Limb>> for &Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn add(self, rhs: &Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_add(rhs.0))
+ }
+}
+
+impl AddAssign for Wrapping<Limb> {
+ fn add_assign(&mut self, other: Self) {
+ *self = *self + other;
+ }
+}
+
+impl AddAssign<&Wrapping<Limb>> for Wrapping<Limb> {
+ fn add_assign(&mut self, other: &Self) {
+ *self = *self + other;
+ }
+}
+
+impl Add for Checked<Limb> {
+ type Output = Self;
+
+ fn add(self, rhs: Self) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_add(rhs))),
+ )
+ }
+}
+
+impl Add<&Checked<Limb>> for Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn add(self, rhs: &Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_add(rhs))),
+ )
+ }
+}
+
+impl Add<Checked<Limb>> for &Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn add(self, rhs: Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_add(rhs))),
+ )
+ }
+}
+
+impl Add<&Checked<Limb>> for &Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn add(self, rhs: &Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_add(rhs))),
+ )
+ }
+}
+
+impl AddAssign for Checked<Limb> {
+ fn add_assign(&mut self, other: Self) {
+ *self = *self + other;
+ }
+}
+
+impl AddAssign<&Checked<Limb>> for Checked<Limb> {
+ fn add_assign(&mut self, other: &Self) {
+ *self = *self + other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{CheckedAdd, Limb};
+
+ #[test]
+ fn adc_no_carry() {
+ let (res, carry) = Limb::ZERO.adc(Limb::ONE, Limb::ZERO);
+ assert_eq!(res, Limb::ONE);
+ assert_eq!(carry, Limb::ZERO);
+ }
+
+ #[test]
+ fn adc_with_carry() {
+ let (res, carry) = Limb::MAX.adc(Limb::ONE, Limb::ZERO);
+ assert_eq!(res, Limb::ZERO);
+ assert_eq!(carry, Limb::ONE);
+ }
+
+ #[test]
+ fn wrapping_add_no_carry() {
+ assert_eq!(Limb::ZERO.wrapping_add(Limb::ONE), Limb::ONE);
+ }
+
+ #[test]
+ fn wrapping_add_with_carry() {
+ assert_eq!(Limb::MAX.wrapping_add(Limb::ONE), Limb::ZERO);
+ }
+
+ #[test]
+ fn checked_add_ok() {
+ let result = Limb::ZERO.checked_add(Limb::ONE);
+ assert_eq!(result.unwrap(), Limb::ONE);
+ }
+
+ #[test]
+ fn checked_add_overflow() {
+ let result = Limb::MAX.checked_add(Limb::ONE);
+ assert!(!bool::from(result.is_some()));
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/bit_and.rs b/vendor/crypto-bigint/src/limb/bit_and.rs
new file mode 100644
index 000000000..3f0bfba0e
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/bit_and.rs
@@ -0,0 +1,21 @@
+//! Limb bit and operations.
+
+use super::Limb;
+use core::ops::BitAnd;
+
+impl Limb {
+ /// Calculates `a & b`.
+ #[inline(always)]
+ pub const fn bitand(self, rhs: Self) -> Self {
+ Limb(self.0 & rhs.0)
+ }
+}
+
+impl BitAnd for Limb {
+ type Output = Limb;
+
+ #[inline(always)]
+ fn bitand(self, rhs: Self) -> Self::Output {
+ self.bitand(rhs)
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/bit_not.rs b/vendor/crypto-bigint/src/limb/bit_not.rs
new file mode 100644
index 000000000..26676d598
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/bit_not.rs
@@ -0,0 +1,19 @@
+//! Limb bit not operations.
+
+use super::Limb;
+use core::ops::Not;
+
+impl Limb {
+ /// Calculates `!a`.
+ pub const fn not(self) -> Self {
+ Limb(!self.0)
+ }
+}
+
+impl Not for Limb {
+ type Output = Limb;
+
+ fn not(self) -> <Self as Not>::Output {
+ self.not()
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/bit_or.rs b/vendor/crypto-bigint/src/limb/bit_or.rs
new file mode 100644
index 000000000..cafac18da
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/bit_or.rs
@@ -0,0 +1,19 @@
+//! Limb bit or operations.
+
+use super::Limb;
+use core::ops::BitOr;
+
+impl Limb {
+ /// Calculates `a | b`.
+ pub const fn bitor(self, rhs: Self) -> Self {
+ Limb(self.0 | rhs.0)
+ }
+}
+
+impl BitOr for Limb {
+ type Output = Limb;
+
+ fn bitor(self, rhs: Self) -> Self::Output {
+ self.bitor(rhs)
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/bit_xor.rs b/vendor/crypto-bigint/src/limb/bit_xor.rs
new file mode 100644
index 000000000..a50782293
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/bit_xor.rs
@@ -0,0 +1,19 @@
+//! Limb bit xor operations.
+
+use super::Limb;
+use core::ops::BitXor;
+
+impl Limb {
+ /// Calculates `a ^ b`.
+ pub const fn bitxor(self, rhs: Self) -> Self {
+ Limb(self.0 ^ rhs.0)
+ }
+}
+
+impl BitXor for Limb {
+ type Output = Limb;
+
+ fn bitxor(self, rhs: Self) -> Self::Output {
+ self.bitxor(rhs)
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/bits.rs b/vendor/crypto-bigint/src/limb/bits.rs
new file mode 100644
index 000000000..c470ae9ab
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/bits.rs
@@ -0,0 +1,8 @@
+use super::Limb;
+
+impl Limb {
+ /// Calculate the number of bits needed to represent this number.
+ pub const fn bits(self) -> usize {
+ Limb::BIT_SIZE - (self.0.leading_zeros() as usize)
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/cmp.rs b/vendor/crypto-bigint/src/limb/cmp.rs
new file mode 100644
index 000000000..76cc4b07c
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/cmp.rs
@@ -0,0 +1,176 @@
+//! Limb comparisons
+
+use super::{Limb, SignedWord, WideSignedWord, Word, HI_BIT};
+use core::cmp::Ordering;
+use subtle::{Choice, ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
+
+impl Limb {
+ /// Is this limb an odd number?
+ #[inline]
+ pub fn is_odd(&self) -> Choice {
+ Choice::from(self.0 as u8 & 1)
+ }
+
+ /// Perform a comparison of the inner value in variable-time.
+ ///
+ /// Note that the [`PartialOrd`] and [`Ord`] impls wrap constant-time
+ /// comparisons using the `subtle` crate.
+ pub fn cmp_vartime(&self, other: &Self) -> Ordering {
+ self.0.cmp(&other.0)
+ }
+
+ /// Performs an equality check in variable-time.
+ pub const fn eq_vartime(&self, other: &Self) -> bool {
+ self.0 == other.0
+ }
+
+ /// Returns all 1's if `a`!=0 or 0 if `a`==0.
+ ///
+ /// Const-friendly: we can't yet use `subtle` in `const fn` contexts.
+ #[inline]
+ pub(crate) const fn is_nonzero(self) -> Word {
+ let inner = self.0 as SignedWord;
+ ((inner | inner.saturating_neg()) >> HI_BIT) as Word
+ }
+
+ #[inline]
+ pub(crate) const fn ct_cmp(lhs: Self, rhs: Self) -> SignedWord {
+ let a = lhs.0 as WideSignedWord;
+ let b = rhs.0 as WideSignedWord;
+ let gt = ((b - a) >> Limb::BIT_SIZE) & 1;
+ let lt = ((a - b) >> Limb::BIT_SIZE) & 1 & !gt;
+ (gt as SignedWord) - (lt as SignedWord)
+ }
+}
+
+impl ConstantTimeEq for Limb {
+ #[inline]
+ fn ct_eq(&self, other: &Self) -> Choice {
+ self.0.ct_eq(&other.0)
+ }
+}
+
+impl ConstantTimeGreater for Limb {
+ #[inline]
+ fn ct_gt(&self, other: &Self) -> Choice {
+ self.0.ct_gt(&other.0)
+ }
+}
+
+impl ConstantTimeLess for Limb {
+ #[inline]
+ fn ct_lt(&self, other: &Self) -> Choice {
+ self.0.ct_lt(&other.0)
+ }
+}
+
+impl Eq for Limb {}
+
+impl Ord for Limb {
+ fn cmp(&self, other: &Self) -> Ordering {
+ let mut n = 0i8;
+ n -= self.ct_lt(other).unwrap_u8() as i8;
+ n += self.ct_gt(other).unwrap_u8() as i8;
+
+ match n {
+ -1 => Ordering::Less,
+ 1 => Ordering::Greater,
+ _ => {
+ debug_assert_eq!(n, 0);
+ debug_assert!(bool::from(self.ct_eq(other)));
+ Ordering::Equal
+ }
+ }
+ }
+}
+
+impl PartialOrd for Limb {
+ #[inline]
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+impl PartialEq for Limb {
+ #[inline]
+ fn eq(&self, other: &Self) -> bool {
+ self.ct_eq(other).into()
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{Limb, Zero};
+ use core::cmp::Ordering;
+ use subtle::{ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
+
+ #[test]
+ fn is_zero() {
+ assert!(bool::from(Limb::ZERO.is_zero()));
+ assert!(!bool::from(Limb::ONE.is_zero()));
+ assert!(!bool::from(Limb::MAX.is_zero()));
+ }
+
+ #[test]
+ fn is_odd() {
+ assert!(!bool::from(Limb::ZERO.is_odd()));
+ assert!(bool::from(Limb::ONE.is_odd()));
+ assert!(bool::from(Limb::MAX.is_odd()));
+ }
+
+ #[test]
+ fn ct_eq() {
+ let a = Limb::ZERO;
+ let b = Limb::MAX;
+
+ assert!(bool::from(a.ct_eq(&a)));
+ assert!(!bool::from(a.ct_eq(&b)));
+ assert!(!bool::from(b.ct_eq(&a)));
+ assert!(bool::from(b.ct_eq(&b)));
+ }
+
+ #[test]
+ fn ct_gt() {
+ let a = Limb::ZERO;
+ let b = Limb::ONE;
+ let c = Limb::MAX;
+
+ assert!(bool::from(b.ct_gt(&a)));
+ assert!(bool::from(c.ct_gt(&a)));
+ assert!(bool::from(c.ct_gt(&b)));
+
+ assert!(!bool::from(a.ct_gt(&a)));
+ assert!(!bool::from(b.ct_gt(&b)));
+ assert!(!bool::from(c.ct_gt(&c)));
+
+ assert!(!bool::from(a.ct_gt(&b)));
+ assert!(!bool::from(a.ct_gt(&c)));
+ assert!(!bool::from(b.ct_gt(&c)));
+ }
+
+ #[test]
+ fn ct_lt() {
+ let a = Limb::ZERO;
+ let b = Limb::ONE;
+ let c = Limb::MAX;
+
+ assert!(bool::from(a.ct_lt(&b)));
+ assert!(bool::from(a.ct_lt(&c)));
+ assert!(bool::from(b.ct_lt(&c)));
+
+ assert!(!bool::from(a.ct_lt(&a)));
+ assert!(!bool::from(b.ct_lt(&b)));
+ assert!(!bool::from(c.ct_lt(&c)));
+
+ assert!(!bool::from(b.ct_lt(&a)));
+ assert!(!bool::from(c.ct_lt(&a)));
+ assert!(!bool::from(c.ct_lt(&b)));
+ }
+
+ #[test]
+ fn cmp() {
+ assert_eq!(Limb::ZERO.cmp(&Limb::ONE), Ordering::Less);
+ assert_eq!(Limb::ONE.cmp(&Limb::ONE), Ordering::Equal);
+ assert_eq!(Limb::MAX.cmp(&Limb::ONE), Ordering::Greater);
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/encoding.rs b/vendor/crypto-bigint/src/limb/encoding.rs
new file mode 100644
index 000000000..39974b061
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/encoding.rs
@@ -0,0 +1,67 @@
+//! Limb encoding
+
+use super::{Limb, Word};
+use crate::Encoding;
+
+impl Encoding for Limb {
+ const BIT_SIZE: usize = Self::BIT_SIZE;
+ const BYTE_SIZE: usize = Self::BYTE_SIZE;
+
+ #[cfg(target_pointer_width = "32")]
+ type Repr = [u8; 4];
+ #[cfg(target_pointer_width = "64")]
+ type Repr = [u8; 8];
+
+ #[inline]
+ fn from_be_bytes(bytes: Self::Repr) -> Self {
+ Limb(Word::from_be_bytes(bytes))
+ }
+
+ #[inline]
+ fn from_le_bytes(bytes: Self::Repr) -> Self {
+ Limb(Word::from_le_bytes(bytes))
+ }
+
+ #[inline]
+ fn to_be_bytes(&self) -> Self::Repr {
+ self.0.to_be_bytes()
+ }
+
+ #[inline]
+ fn to_le_bytes(&self) -> Self::Repr {
+ self.0.to_le_bytes()
+ }
+}
+
+#[cfg(test)]
+mod test {
+ use super::*;
+ use proptest::prelude::*;
+
+ prop_compose! {
+ fn limb()(inner in any::<Word>()) -> Limb {
+ Limb(inner)
+ }
+ }
+
+ proptest! {
+ #[test]
+ fn roundtrip(a in limb()) {
+ assert_eq!(a, Limb::from_be_bytes(a.to_be_bytes()));
+ assert_eq!(a, Limb::from_le_bytes(a.to_le_bytes()));
+ }
+ }
+
+ proptest! {
+ #[test]
+ fn reverse(a in limb()) {
+ let mut bytes = a.to_be_bytes();
+ bytes.reverse();
+ assert_eq!(a, Limb::from_le_bytes(bytes));
+
+ let mut bytes = a.to_le_bytes();
+ bytes.reverse();
+ assert_eq!(a, Limb::from_be_bytes(bytes));
+ }
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/from.rs b/vendor/crypto-bigint/src/limb/from.rs
new file mode 100644
index 000000000..fd2765bc9
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/from.rs
@@ -0,0 +1,76 @@
+//! `From`-like conversions for [`Limb`].
+
+use super::{Limb, WideWord, Word};
+
+impl Limb {
+ /// Create a [`Limb`] from a `u8` integer (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u8>` when stable
+ pub const fn from_u8(n: u8) -> Self {
+ Limb(n as Word)
+ }
+
+ /// Create a [`Limb`] from a `u16` integer (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u16>` when stable
+ pub const fn from_u16(n: u16) -> Self {
+ Limb(n as Word)
+ }
+
+ /// Create a [`Limb`] from a `u32` integer (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u32>` when stable
+ pub const fn from_u32(n: u32) -> Self {
+ #[allow(trivial_numeric_casts)]
+ Limb(n as Word)
+ }
+
+ /// Create a [`Limb`] from a `u64` integer (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u64>` when stable
+ #[cfg(target_pointer_width = "64")]
+ #[cfg_attr(docsrs, doc(cfg(target_pointer_width = "64")))]
+ pub const fn from_u64(n: u64) -> Self {
+ Limb(n)
+ }
+}
+
+impl From<u8> for Limb {
+ #[inline]
+ fn from(n: u8) -> Limb {
+ Limb(n.into())
+ }
+}
+
+impl From<u16> for Limb {
+ #[inline]
+ fn from(n: u16) -> Limb {
+ Limb(n.into())
+ }
+}
+
+impl From<u32> for Limb {
+ #[inline]
+ fn from(n: u32) -> Limb {
+ Limb(n.into())
+ }
+}
+
+#[cfg(target_pointer_width = "64")]
+#[cfg_attr(docsrs, doc(cfg(target_pointer_width = "64")))]
+impl From<u64> for Limb {
+ #[inline]
+ fn from(n: u64) -> Limb {
+ Limb(n)
+ }
+}
+
+impl From<Limb> for Word {
+ #[inline]
+ fn from(limb: Limb) -> Word {
+ limb.0
+ }
+}
+
+impl From<Limb> for WideWord {
+ #[inline]
+ fn from(limb: Limb) -> WideWord {
+ limb.0.into()
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/mul.rs b/vendor/crypto-bigint/src/limb/mul.rs
new file mode 100644
index 000000000..a342c6eae
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/mul.rs
@@ -0,0 +1,195 @@
+//! Limb multiplication
+
+use crate::{Checked, CheckedMul, Limb, WideWord, Word, Wrapping, Zero};
+use core::ops::{Mul, MulAssign};
+use subtle::CtOption;
+
+impl Limb {
+ /// Computes `self + (b * c) + carry`, returning the result along with the new carry.
+ #[inline(always)]
+ pub const fn mac(self, b: Limb, c: Limb, carry: Limb) -> (Limb, Limb) {
+ let a = self.0 as WideWord;
+ let b = b.0 as WideWord;
+ let c = c.0 as WideWord;
+ let carry = carry.0 as WideWord;
+ let ret = a + (b * c) + carry;
+ (Limb(ret as Word), Limb((ret >> Self::BIT_SIZE) as Word))
+ }
+
+ /// Perform saturating multiplication.
+ #[inline]
+ pub const fn saturating_mul(&self, rhs: Self) -> Self {
+ Limb(self.0.saturating_mul(rhs.0))
+ }
+
+ /// Perform wrapping multiplication, discarding overflow.
+ #[inline(always)]
+ pub const fn wrapping_mul(&self, rhs: Self) -> Self {
+ Limb(self.0.wrapping_mul(rhs.0))
+ }
+
+ /// Compute "wide" multiplication, with a product twice the size of the input.
+ pub(crate) const fn mul_wide(&self, rhs: Self) -> WideWord {
+ (self.0 as WideWord) * (rhs.0 as WideWord)
+ }
+}
+
+impl CheckedMul for Limb {
+ type Output = Self;
+
+ #[inline]
+ fn checked_mul(&self, rhs: Self) -> CtOption<Self> {
+ let result = self.mul_wide(rhs);
+ let overflow = Limb((result >> Self::BIT_SIZE) as Word);
+ CtOption::new(Limb(result as Word), overflow.is_zero())
+ }
+}
+
+impl Mul for Wrapping<Limb> {
+ type Output = Self;
+
+ fn mul(self, rhs: Self) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_mul(rhs.0))
+ }
+}
+
+impl Mul<&Wrapping<Limb>> for Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn mul(self, rhs: &Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_mul(rhs.0))
+ }
+}
+
+impl Mul<Wrapping<Limb>> for &Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn mul(self, rhs: Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_mul(rhs.0))
+ }
+}
+
+impl Mul<&Wrapping<Limb>> for &Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn mul(self, rhs: &Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_mul(rhs.0))
+ }
+}
+
+impl MulAssign for Wrapping<Limb> {
+ fn mul_assign(&mut self, other: Self) {
+ *self = *self * other;
+ }
+}
+
+impl MulAssign<&Wrapping<Limb>> for Wrapping<Limb> {
+ fn mul_assign(&mut self, other: &Self) {
+ *self = *self * other;
+ }
+}
+
+impl Mul for Checked<Limb> {
+ type Output = Self;
+
+ fn mul(self, rhs: Self) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_mul(rhs))),
+ )
+ }
+}
+
+impl Mul<&Checked<Limb>> for Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn mul(self, rhs: &Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_mul(rhs))),
+ )
+ }
+}
+
+impl Mul<Checked<Limb>> for &Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn mul(self, rhs: Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_mul(rhs))),
+ )
+ }
+}
+
+impl Mul<&Checked<Limb>> for &Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn mul(self, rhs: &Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_mul(rhs))),
+ )
+ }
+}
+
+impl MulAssign for Checked<Limb> {
+ fn mul_assign(&mut self, other: Self) {
+ *self = *self * other;
+ }
+}
+
+impl MulAssign<&Checked<Limb>> for Checked<Limb> {
+ fn mul_assign(&mut self, other: &Self) {
+ *self = *self * other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::{CheckedMul, Limb, WideWord};
+
+ #[test]
+ fn mul_wide_zero_and_one() {
+ assert_eq!(Limb::ZERO.mul_wide(Limb::ZERO), 0);
+ assert_eq!(Limb::ZERO.mul_wide(Limb::ONE), 0);
+ assert_eq!(Limb::ONE.mul_wide(Limb::ZERO), 0);
+ assert_eq!(Limb::ONE.mul_wide(Limb::ONE), 1);
+ }
+
+ #[test]
+ fn mul_wide() {
+ let primes: &[u32] = &[3, 5, 17, 256, 65537];
+
+ for &a_int in primes {
+ for &b_int in primes {
+ let actual = Limb::from_u32(a_int).mul_wide(Limb::from_u32(b_int));
+ let expected = a_int as WideWord * b_int as WideWord;
+ assert_eq!(actual, expected);
+ }
+ }
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn checked_mul_ok() {
+ let n = Limb::from_u16(0xffff);
+ assert_eq!(n.checked_mul(n).unwrap(), Limb::from_u32(0xfffe_0001));
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn checked_mul_ok() {
+ let n = Limb::from_u32(0xffff_ffff);
+ assert_eq!(
+ n.checked_mul(n).unwrap(),
+ Limb::from_u64(0xffff_fffe_0000_0001)
+ );
+ }
+
+ #[test]
+ fn checked_mul_overflow() {
+ let n = Limb::MAX;
+ assert!(bool::from(n.checked_mul(n).is_none()));
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/rand.rs b/vendor/crypto-bigint/src/limb/rand.rs
new file mode 100644
index 000000000..0bc8af31a
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/rand.rs
@@ -0,0 +1,45 @@
+//! Random number generator support
+
+use super::Limb;
+use crate::{Encoding, NonZero, Random, RandomMod};
+use rand_core::{CryptoRng, RngCore};
+use subtle::ConstantTimeLess;
+
+#[cfg_attr(docsrs, doc(cfg(feature = "rand_core")))]
+impl Random for Limb {
+ #[cfg(target_pointer_width = "32")]
+ fn random(mut rng: impl CryptoRng + RngCore) -> Self {
+ Self(rng.next_u32())
+ }
+
+ #[cfg(target_pointer_width = "64")]
+ fn random(mut rng: impl CryptoRng + RngCore) -> Self {
+ Self(rng.next_u64())
+ }
+}
+
+#[cfg_attr(docsrs, doc(cfg(feature = "rand_core")))]
+impl RandomMod for Limb {
+ fn random_mod(mut rng: impl CryptoRng + RngCore, modulus: &NonZero<Self>) -> Self {
+ let mut bytes = <Self as Encoding>::Repr::default();
+
+ // TODO(tarcieri): use `div_ceil` when available
+ // See: https://github.com/rust-lang/rust/issues/88581
+ let mut n_bytes = modulus.bits() / 8;
+
+ // Ensure the randomly generated value can always be larger than
+ // the modulus in order to ensure a uniform distribution
+ if n_bytes < Self::BYTE_SIZE {
+ n_bytes += 1;
+ }
+
+ loop {
+ rng.fill_bytes(&mut bytes[..n_bytes]);
+ let n = Limb::from_le_bytes(bytes);
+
+ if n.ct_lt(modulus).into() {
+ return n;
+ }
+ }
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/shl.rs b/vendor/crypto-bigint/src/limb/shl.rs
new file mode 100644
index 000000000..c0003ddbb
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/shl.rs
@@ -0,0 +1,73 @@
+//! Limb left bitshift
+
+use crate::{Limb, Word};
+use core::ops::{Shl, ShlAssign};
+
+impl Limb {
+ /// Computes `self << rhs`.
+ #[inline(always)]
+ pub const fn shl(self, rhs: Self) -> Self {
+ Limb(self.0 << rhs.0)
+ }
+}
+
+impl Shl for Limb {
+ type Output = Self;
+
+ #[inline(always)]
+ fn shl(self, rhs: Self) -> Self::Output {
+ self.shl(rhs)
+ }
+}
+
+impl Shl<usize> for Limb {
+ type Output = Self;
+
+ #[inline(always)]
+ fn shl(self, rhs: usize) -> Self::Output {
+ self.shl(Limb(rhs as Word))
+ }
+}
+
+impl ShlAssign for Limb {
+ #[inline(always)]
+ fn shl_assign(&mut self, other: Self) {
+ *self = self.shl(other);
+ }
+}
+
+impl ShlAssign<usize> for Limb {
+ #[inline(always)]
+ fn shl_assign(&mut self, other: usize) {
+ *self = self.shl(Limb(other as Word));
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::Limb;
+
+ #[test]
+ fn shl1() {
+ assert_eq!(Limb(1) << 1, Limb(2));
+ }
+
+ #[test]
+ fn shl2() {
+ assert_eq!(Limb(1) << 2, Limb(4));
+ }
+
+ #[test]
+ fn shl_assign1() {
+ let mut l = Limb(1);
+ l <<= 1;
+ assert_eq!(l, Limb(2));
+ }
+
+ #[test]
+ fn shl_assign2() {
+ let mut l = Limb(1);
+ l <<= 2;
+ assert_eq!(l, Limb(4));
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/shr.rs b/vendor/crypto-bigint/src/limb/shr.rs
new file mode 100644
index 000000000..29ee76353
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/shr.rs
@@ -0,0 +1,73 @@
+//! Limb right bitshift
+
+use crate::{Limb, Word};
+use core::ops::{Shr, ShrAssign};
+
+impl Limb {
+ /// Computes `self >> rhs`.
+ #[inline(always)]
+ pub const fn shr(self, rhs: Self) -> Self {
+ Limb(self.0 >> rhs.0)
+ }
+}
+
+impl Shr for Limb {
+ type Output = Self;
+
+ #[inline(always)]
+ fn shr(self, rhs: Self) -> Self::Output {
+ self.shr(rhs)
+ }
+}
+
+impl Shr<usize> for Limb {
+ type Output = Self;
+
+ #[inline(always)]
+ fn shr(self, rhs: usize) -> Self::Output {
+ self.shr(Limb(rhs as Word))
+ }
+}
+
+impl ShrAssign for Limb {
+ #[inline(always)]
+ fn shr_assign(&mut self, other: Self) {
+ *self = self.shr(other);
+ }
+}
+
+impl ShrAssign<usize> for Limb {
+ #[inline(always)]
+ fn shr_assign(&mut self, other: usize) {
+ *self = self.shr(Limb(other as Word));
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::Limb;
+
+ #[test]
+ fn shr1() {
+ assert_eq!(Limb(2) >> 1, Limb(1));
+ }
+
+ #[test]
+ fn shr2() {
+ assert_eq!(Limb(16) >> 2, Limb(4));
+ }
+
+ #[test]
+ fn shr_assign1() {
+ let mut l = Limb::ONE;
+ l >>= 1;
+ assert_eq!(l, Limb::ZERO);
+ }
+
+ #[test]
+ fn shr_assign2() {
+ let mut l = Limb(32);
+ l >>= 2;
+ assert_eq!(l, Limb(8));
+ }
+}
diff --git a/vendor/crypto-bigint/src/limb/sub.rs b/vendor/crypto-bigint/src/limb/sub.rs
new file mode 100644
index 000000000..1560a1b64
--- /dev/null
+++ b/vendor/crypto-bigint/src/limb/sub.rs
@@ -0,0 +1,182 @@
+//! Limb subtraction
+
+use crate::{Checked, CheckedSub, Limb, WideWord, Word, Wrapping, Zero};
+use core::ops::{Sub, SubAssign};
+use subtle::CtOption;
+
+impl Limb {
+ /// Computes `self - (rhs + borrow)`, returning the result along with the new borrow.
+ #[inline(always)]
+ pub const fn sbb(self, rhs: Limb, borrow: Limb) -> (Limb, Limb) {
+ let a = self.0 as WideWord;
+ let b = rhs.0 as WideWord;
+ let borrow = (borrow.0 >> (Self::BIT_SIZE - 1)) as WideWord;
+ let ret = a.wrapping_sub(b + borrow);
+ (Limb(ret as Word), Limb((ret >> Self::BIT_SIZE) as Word))
+ }
+
+ /// Perform saturating subtraction.
+ #[inline]
+ pub const fn saturating_sub(&self, rhs: Self) -> Self {
+ Limb(self.0.saturating_sub(rhs.0))
+ }
+
+ /// Perform wrapping subtraction, discarding underflow and wrapping around
+ /// the boundary of the type.
+ #[inline(always)]
+ pub const fn wrapping_sub(&self, rhs: Self) -> Self {
+ Limb(self.0.wrapping_sub(rhs.0))
+ }
+}
+
+impl CheckedSub for Limb {
+ type Output = Self;
+
+ #[inline]
+ fn checked_sub(&self, rhs: Self) -> CtOption<Self> {
+ let (result, underflow) = self.sbb(rhs, Limb::ZERO);
+ CtOption::new(result, underflow.is_zero())
+ }
+}
+
+impl Sub for Wrapping<Limb> {
+ type Output = Self;
+
+ fn sub(self, rhs: Self) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_sub(rhs.0))
+ }
+}
+
+impl Sub<&Wrapping<Limb>> for Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn sub(self, rhs: &Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_sub(rhs.0))
+ }
+}
+
+impl Sub<Wrapping<Limb>> for &Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn sub(self, rhs: Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_sub(rhs.0))
+ }
+}
+
+impl Sub<&Wrapping<Limb>> for &Wrapping<Limb> {
+ type Output = Wrapping<Limb>;
+
+ fn sub(self, rhs: &Wrapping<Limb>) -> Wrapping<Limb> {
+ Wrapping(self.0.wrapping_sub(rhs.0))
+ }
+}
+
+impl SubAssign for Wrapping<Limb> {
+ fn sub_assign(&mut self, other: Self) {
+ *self = *self - other;
+ }
+}
+
+impl SubAssign<&Wrapping<Limb>> for Wrapping<Limb> {
+ fn sub_assign(&mut self, other: &Self) {
+ *self = *self - other;
+ }
+}
+
+impl Sub for Checked<Limb> {
+ type Output = Self;
+
+ fn sub(self, rhs: Self) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_sub(rhs))),
+ )
+ }
+}
+
+impl Sub<&Checked<Limb>> for Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn sub(self, rhs: &Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_sub(rhs))),
+ )
+ }
+}
+
+impl Sub<Checked<Limb>> for &Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn sub(self, rhs: Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_sub(rhs))),
+ )
+ }
+}
+
+impl Sub<&Checked<Limb>> for &Checked<Limb> {
+ type Output = Checked<Limb>;
+
+ fn sub(self, rhs: &Checked<Limb>) -> Checked<Limb> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_sub(rhs))),
+ )
+ }
+}
+
+impl SubAssign for Checked<Limb> {
+ fn sub_assign(&mut self, other: Self) {
+ *self = *self - other;
+ }
+}
+
+impl SubAssign<&Checked<Limb>> for Checked<Limb> {
+ fn sub_assign(&mut self, other: &Self) {
+ *self = *self - other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{CheckedSub, Limb};
+
+ #[test]
+ fn sbb_no_borrow() {
+ let (res, borrow) = Limb::ONE.sbb(Limb::ONE, Limb::ZERO);
+ assert_eq!(res, Limb::ZERO);
+ assert_eq!(borrow, Limb::ZERO);
+ }
+
+ #[test]
+ fn sbb_with_borrow() {
+ let (res, borrow) = Limb::ZERO.sbb(Limb::ONE, Limb::ZERO);
+
+ assert_eq!(res, Limb::MAX);
+ assert_eq!(borrow, Limb::MAX);
+ }
+
+ #[test]
+ fn wrapping_sub_no_borrow() {
+ assert_eq!(Limb::ONE.wrapping_sub(Limb::ONE), Limb::ZERO);
+ }
+
+ #[test]
+ fn wrapping_sub_with_borrow() {
+ assert_eq!(Limb::ZERO.wrapping_sub(Limb::ONE), Limb::MAX);
+ }
+
+ #[test]
+ fn checked_sub_ok() {
+ let result = Limb::ONE.checked_sub(Limb::ONE);
+ assert_eq!(result.unwrap(), Limb::ZERO);
+ }
+
+ #[test]
+ fn checked_sub_overflow() {
+ let result = Limb::ZERO.checked_sub(Limb::ONE);
+ assert!(!bool::from(result.is_some()));
+ }
+}
diff --git a/vendor/crypto-bigint/src/nlimbs.rs b/vendor/crypto-bigint/src/nlimbs.rs
new file mode 100644
index 000000000..c3f91b9fe
--- /dev/null
+++ b/vendor/crypto-bigint/src/nlimbs.rs
@@ -0,0 +1,29 @@
+/// Calculate the number of limbs required to represent the given number of bits.
+// TODO(tarcieri): replace with `generic_const_exprs` (rust-lang/rust#76560) when stable
+#[macro_export]
+macro_rules! nlimbs {
+ ($bits:expr) => {
+ $bits / $crate::Limb::BIT_SIZE
+ };
+}
+
+#[cfg(test)]
+mod tests {
+ #[cfg(target_pointer_width = "32")]
+ #[test]
+ fn nlimbs_for_bits_macro() {
+ assert_eq!(nlimbs!(64), 2);
+ assert_eq!(nlimbs!(128), 4);
+ assert_eq!(nlimbs!(192), 6);
+ assert_eq!(nlimbs!(256), 8);
+ }
+
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn nlimbs_for_bits_macro() {
+ assert_eq!(nlimbs!(64), 1);
+ assert_eq!(nlimbs!(128), 2);
+ assert_eq!(nlimbs!(192), 3);
+ assert_eq!(nlimbs!(256), 4);
+ }
+}
diff --git a/vendor/crypto-bigint/src/non_zero.rs b/vendor/crypto-bigint/src/non_zero.rs
new file mode 100644
index 000000000..fc3c9a84d
--- /dev/null
+++ b/vendor/crypto-bigint/src/non_zero.rs
@@ -0,0 +1,385 @@
+//! Wrapper type for non-zero integers.
+
+use crate::{Encoding, Integer, Limb, UInt, Zero};
+use core::{
+ fmt,
+ num::{NonZeroU128, NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8},
+ ops::Deref,
+};
+use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
+
+#[cfg(feature = "generic-array")]
+use crate::{ArrayEncoding, ByteArray};
+
+#[cfg(feature = "rand_core")]
+use {
+ crate::Random,
+ rand_core::{CryptoRng, RngCore},
+};
+
+#[cfg(feature = "serde")]
+use serdect::serde::{
+ de::{Error, Unexpected},
+ Deserialize, Deserializer, Serialize, Serializer,
+};
+
+/// Wrapper type for non-zero integers.
+#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, PartialOrd, Ord)]
+pub struct NonZero<T: Zero>(T);
+
+impl<T> NonZero<T>
+where
+ T: Zero,
+{
+ /// Create a new non-zero integer.
+ pub fn new(n: T) -> CtOption<Self> {
+ let is_zero = n.is_zero();
+ CtOption::new(Self(n), !is_zero)
+ }
+}
+
+impl<T> NonZero<T>
+where
+ T: Integer,
+{
+ /// The value `1`.
+ pub const ONE: Self = Self(T::ONE);
+
+ /// Maximum value this integer can express.
+ pub const MAX: Self = Self(T::MAX);
+}
+
+impl<T> NonZero<T>
+where
+ T: Encoding + Zero,
+{
+ /// Decode from big endian bytes.
+ pub fn from_be_bytes(bytes: T::Repr) -> CtOption<Self> {
+ Self::new(T::from_be_bytes(bytes))
+ }
+
+ /// Decode from little endian bytes.
+ pub fn from_le_bytes(bytes: T::Repr) -> CtOption<Self> {
+ Self::new(T::from_le_bytes(bytes))
+ }
+}
+
+#[cfg(feature = "generic-array")]
+#[cfg_attr(docsrs, doc(cfg(feature = "generic-array")))]
+impl<T> NonZero<T>
+where
+ T: ArrayEncoding + Zero,
+{
+ /// Decode a non-zero integer from big endian bytes.
+ pub fn from_be_byte_array(bytes: ByteArray<T>) -> CtOption<Self> {
+ Self::new(T::from_be_byte_array(bytes))
+ }
+
+ /// Decode a non-zero integer from big endian bytes.
+ pub fn from_le_byte_array(bytes: ByteArray<T>) -> CtOption<Self> {
+ Self::new(T::from_be_byte_array(bytes))
+ }
+}
+
+impl<T> AsRef<T> for NonZero<T>
+where
+ T: Zero,
+{
+ fn as_ref(&self) -> &T {
+ &self.0
+ }
+}
+
+impl<T> ConditionallySelectable for NonZero<T>
+where
+ T: ConditionallySelectable + Zero,
+{
+ fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
+ Self(T::conditional_select(&a.0, &b.0, choice))
+ }
+}
+
+impl<T> ConstantTimeEq for NonZero<T>
+where
+ T: Zero,
+{
+ fn ct_eq(&self, other: &Self) -> Choice {
+ self.0.ct_eq(&other.0)
+ }
+}
+
+impl<T> Deref for NonZero<T>
+where
+ T: Zero,
+{
+ type Target = T;
+
+ fn deref(&self) -> &T {
+ &self.0
+ }
+}
+
+#[cfg(feature = "rand_core")]
+#[cfg_attr(docsrs, doc(cfg(feature = "rand_core")))]
+impl<T> Random for NonZero<T>
+where
+ T: Random + Zero,
+{
+ /// Generate a random `NonZero<T>`.
+ fn random(mut rng: impl CryptoRng + RngCore) -> Self {
+ // Use rejection sampling to eliminate zero values.
+ // While this method isn't constant-time, the attacker shouldn't learn
+ // anything about unrelated outputs so long as `rng` is a secure `CryptoRng`.
+ loop {
+ if let Some(result) = Self::new(T::random(&mut rng)).into() {
+ break result;
+ }
+ }
+ }
+}
+
+impl<T> fmt::Display for NonZero<T>
+where
+ T: fmt::Display + Zero,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::Display::fmt(&self.0, f)
+ }
+}
+
+impl<T> fmt::Binary for NonZero<T>
+where
+ T: fmt::Binary + Zero,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::Binary::fmt(&self.0, f)
+ }
+}
+
+impl<T> fmt::Octal for NonZero<T>
+where
+ T: fmt::Octal + Zero,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::Octal::fmt(&self.0, f)
+ }
+}
+
+impl<T> fmt::LowerHex for NonZero<T>
+where
+ T: fmt::LowerHex + Zero,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::LowerHex::fmt(&self.0, f)
+ }
+}
+
+impl<T> fmt::UpperHex for NonZero<T>
+where
+ T: fmt::UpperHex + Zero,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::UpperHex::fmt(&self.0, f)
+ }
+}
+
+impl NonZero<Limb> {
+ /// Create a [`NonZero<Limb>`] from a [`NonZeroU8`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU8>` when stable
+ pub const fn from_u8(n: NonZeroU8) -> Self {
+ Self(Limb::from_u8(n.get()))
+ }
+
+ /// Create a [`NonZero<Limb>`] from a [`NonZeroU16`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU16>` when stable
+ pub const fn from_u16(n: NonZeroU16) -> Self {
+ Self(Limb::from_u16(n.get()))
+ }
+
+ /// Create a [`NonZero<Limb>`] from a [`NonZeroU32`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU32>` when stable
+ pub const fn from_u32(n: NonZeroU32) -> Self {
+ Self(Limb::from_u32(n.get()))
+ }
+
+ /// Create a [`NonZero<Limb>`] from a [`NonZeroU64`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU64>` when stable
+ #[cfg(target_pointer_width = "64")]
+ #[cfg_attr(docsrs, doc(cfg(target_pointer_width = "64")))]
+ pub const fn from_u64(n: NonZeroU64) -> Self {
+ Self(Limb::from_u64(n.get()))
+ }
+}
+
+impl From<NonZeroU8> for NonZero<Limb> {
+ fn from(integer: NonZeroU8) -> Self {
+ Self::from_u8(integer)
+ }
+}
+
+impl From<NonZeroU16> for NonZero<Limb> {
+ fn from(integer: NonZeroU16) -> Self {
+ Self::from_u16(integer)
+ }
+}
+
+impl From<NonZeroU32> for NonZero<Limb> {
+ fn from(integer: NonZeroU32) -> Self {
+ Self::from_u32(integer)
+ }
+}
+
+#[cfg(target_pointer_width = "64")]
+#[cfg_attr(docsrs, doc(cfg(target_pointer_width = "64")))]
+impl From<NonZeroU64> for NonZero<Limb> {
+ fn from(integer: NonZeroU64) -> Self {
+ Self::from_u64(integer)
+ }
+}
+
+impl<const LIMBS: usize> NonZero<UInt<LIMBS>> {
+ /// Create a [`NonZero<UInt>`] from a [`UInt`] (const-friendly)
+ pub const fn from_uint(n: UInt<LIMBS>) -> Self {
+ let mut i = 0;
+ let mut found_non_zero = false;
+ while i < LIMBS {
+ if n.limbs()[i].0 != 0 {
+ found_non_zero = true;
+ }
+ i += 1;
+ }
+ assert!(found_non_zero, "found zero");
+ Self(n)
+ }
+
+ /// Create a [`NonZero<UInt>`] from a [`NonZeroU8`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU8>` when stable
+ pub const fn from_u8(n: NonZeroU8) -> Self {
+ Self(UInt::from_u8(n.get()))
+ }
+
+ /// Create a [`NonZero<UInt>`] from a [`NonZeroU16`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU16>` when stable
+ pub const fn from_u16(n: NonZeroU16) -> Self {
+ Self(UInt::from_u16(n.get()))
+ }
+
+ /// Create a [`NonZero<UInt>`] from a [`NonZeroU32`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU32>` when stable
+ pub const fn from_u32(n: NonZeroU32) -> Self {
+ Self(UInt::from_u32(n.get()))
+ }
+
+ /// Create a [`NonZero<UInt>`] from a [`NonZeroU64`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU64>` when stable
+ pub const fn from_u64(n: NonZeroU64) -> Self {
+ Self(UInt::from_u64(n.get()))
+ }
+
+ /// Create a [`NonZero<UInt>`] from a [`NonZeroU128`] (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<NonZeroU128>` when stable
+ pub const fn from_u128(n: NonZeroU128) -> Self {
+ Self(UInt::from_u128(n.get()))
+ }
+}
+
+impl<const LIMBS: usize> From<NonZeroU8> for NonZero<UInt<LIMBS>> {
+ fn from(integer: NonZeroU8) -> Self {
+ Self::from_u8(integer)
+ }
+}
+
+impl<const LIMBS: usize> From<NonZeroU16> for NonZero<UInt<LIMBS>> {
+ fn from(integer: NonZeroU16) -> Self {
+ Self::from_u16(integer)
+ }
+}
+
+impl<const LIMBS: usize> From<NonZeroU32> for NonZero<UInt<LIMBS>> {
+ fn from(integer: NonZeroU32) -> Self {
+ Self::from_u32(integer)
+ }
+}
+
+impl<const LIMBS: usize> From<NonZeroU64> for NonZero<UInt<LIMBS>> {
+ fn from(integer: NonZeroU64) -> Self {
+ Self::from_u64(integer)
+ }
+}
+
+impl<const LIMBS: usize> From<NonZeroU128> for NonZero<UInt<LIMBS>> {
+ fn from(integer: NonZeroU128) -> Self {
+ Self::from_u128(integer)
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de, T: Deserialize<'de> + Zero> Deserialize<'de> for NonZero<T> {
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ let value: T = T::deserialize(deserializer)?;
+
+ if bool::from(value.is_zero()) {
+ Err(D::Error::invalid_value(
+ Unexpected::Other("zero"),
+ &"a non-zero value",
+ ))
+ } else {
+ Ok(Self(value))
+ }
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de, T: Serialize + Zero> Serialize for NonZero<T> {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ self.0.serialize(serializer)
+ }
+}
+
+#[cfg(all(test, feature = "serde"))]
+mod tests {
+ use crate::{NonZero, U64};
+ use bincode::ErrorKind;
+
+ #[test]
+ fn serde() {
+ let test =
+ Option::<NonZero<U64>>::from(NonZero::new(U64::from_u64(0x0011223344556677))).unwrap();
+
+ let serialized = bincode::serialize(&test).unwrap();
+ let deserialized: NonZero<U64> = bincode::deserialize(&serialized).unwrap();
+
+ assert_eq!(test, deserialized);
+
+ let serialized = bincode::serialize(&U64::ZERO).unwrap();
+ assert!(matches!(
+ *bincode::deserialize::<NonZero<U64>>(&serialized).unwrap_err(),
+ ErrorKind::Custom(message) if message == "invalid value: zero, expected a non-zero value"
+ ));
+ }
+
+ #[test]
+ fn serde_owned() {
+ let test =
+ Option::<NonZero<U64>>::from(NonZero::new(U64::from_u64(0x0011223344556677))).unwrap();
+
+ let serialized = bincode::serialize(&test).unwrap();
+ let deserialized: NonZero<U64> = bincode::deserialize_from(serialized.as_slice()).unwrap();
+
+ assert_eq!(test, deserialized);
+
+ let serialized = bincode::serialize(&U64::ZERO).unwrap();
+ assert!(matches!(
+ *bincode::deserialize_from::<_, NonZero<U64>>(serialized.as_slice()).unwrap_err(),
+ ErrorKind::Custom(message) if message == "invalid value: zero, expected a non-zero value"
+ ));
+ }
+}
diff --git a/vendor/crypto-bigint/src/traits.rs b/vendor/crypto-bigint/src/traits.rs
new file mode 100644
index 000000000..b89c70a9b
--- /dev/null
+++ b/vendor/crypto-bigint/src/traits.rs
@@ -0,0 +1,227 @@
+//! Traits provided by this crate
+
+use crate::{Limb, NonZero};
+use core::fmt::Debug;
+use core::ops::{BitAnd, BitOr, BitXor, Div, Not, Rem, Shl, Shr};
+use subtle::{
+ Choice, ConditionallySelectable, ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess,
+ CtOption,
+};
+
+#[cfg(feature = "rand_core")]
+use rand_core::{CryptoRng, RngCore};
+
+/// Integer type.
+pub trait Integer:
+ 'static
+ + AsRef<[Limb]>
+ + BitAnd<Output = Self>
+ + BitOr<Output = Self>
+ + BitXor<Output = Self>
+ + for<'a> CheckedAdd<&'a Self, Output = Self>
+ + for<'a> CheckedSub<&'a Self, Output = Self>
+ + for<'a> CheckedMul<&'a Self, Output = Self>
+ + Copy
+ + ConditionallySelectable
+ + ConstantTimeEq
+ + ConstantTimeGreater
+ + ConstantTimeLess
+ + Debug
+ + Default
+ + Div<NonZero<Self>, Output = Self>
+ + Eq
+ + From<u64>
+ + Not
+ + Ord
+ + Rem<NonZero<Self>, Output = Self>
+ + Send
+ + Sized
+ + Shl<usize, Output = Self>
+ + Shr<usize, Output = Self>
+ + Sync
+ + Zero
+{
+ /// The value `1`.
+ const ONE: Self;
+
+ /// Maximum value this integer can express.
+ const MAX: Self;
+
+ /// Is this integer value an odd number?
+ ///
+ /// # Returns
+ ///
+ /// If odd, returns `Choice(1)`. Otherwise, returns `Choice(0)`.
+ fn is_odd(&self) -> Choice;
+
+ /// Is this integer value an even number?
+ ///
+ /// # Returns
+ ///
+ /// If even, returns `Choice(1)`. Otherwise, returns `Choice(0)`.
+ fn is_even(&self) -> Choice {
+ !self.is_odd()
+ }
+}
+
+/// Zero values.
+pub trait Zero: ConstantTimeEq + Sized {
+ /// The value `0`.
+ const ZERO: Self;
+
+ /// Determine if this value is equal to zero.
+ ///
+ /// # Returns
+ ///
+ /// If zero, returns `Choice(1)`. Otherwise, returns `Choice(0)`.
+ fn is_zero(&self) -> Choice {
+ self.ct_eq(&Self::ZERO)
+ }
+}
+
+/// Random number generation support.
+#[cfg(feature = "rand_core")]
+#[cfg_attr(docsrs, doc(cfg(feature = "rand_core")))]
+pub trait Random: Sized {
+ /// Generate a cryptographically secure random value.
+ fn random(rng: impl CryptoRng + RngCore) -> Self;
+}
+
+/// Modular random number generation support.
+#[cfg(feature = "rand_core")]
+#[cfg_attr(docsrs, doc(cfg(feature = "rand_core")))]
+pub trait RandomMod: Sized + Zero {
+ /// Generate a cryptographically secure random number which is less than
+ /// a given `modulus`.
+ ///
+ /// This function uses rejection sampling, a method which produces an
+ /// unbiased distribution of in-range values provided the underlying
+ /// [`CryptoRng`] is unbiased, but runs in variable-time.
+ ///
+ /// The variable-time nature of the algorithm should not pose a security
+ /// issue so long as the underlying random number generator is truly a
+ /// [`CryptoRng`], where previous outputs are unrelated to subsequent
+ /// outputs and do not reveal information about the RNG's internal state.
+ fn random_mod(rng: impl CryptoRng + RngCore, modulus: &NonZero<Self>) -> Self;
+}
+
+/// Compute `self + rhs mod p`.
+pub trait AddMod<Rhs = Self> {
+ /// Output type.
+ type Output;
+
+ /// Compute `self + rhs mod p`.
+ ///
+ /// Assumes `self` and `rhs` are `< p`.
+ fn add_mod(&self, rhs: &Rhs, p: &Self) -> Self::Output;
+}
+
+/// Compute `self - rhs mod p`.
+pub trait SubMod<Rhs = Self> {
+ /// Output type.
+ type Output;
+
+ /// Compute `self - rhs mod p`.
+ ///
+ /// Assumes `self` and `rhs` are `< p`.
+ fn sub_mod(&self, rhs: &Rhs, p: &Self) -> Self::Output;
+}
+
+/// Compute `-self mod p`.
+pub trait NegMod {
+ /// Output type.
+ type Output;
+
+ /// Compute `-self mod p`.
+ #[must_use]
+ fn neg_mod(&self, p: &Self) -> Self::Output;
+}
+
+/// Compute `self * rhs mod p`.
+///
+/// Requires `p_inv = -(p^{-1} mod 2^{BITS}) mod 2^{BITS}` to be provided for efficiency.
+pub trait MulMod<Rhs = Self> {
+ /// Output type.
+ type Output;
+
+ /// Compute `self * rhs mod p`.
+ ///
+ /// Requires `p_inv = -(p^{-1} mod 2^{BITS}) mod 2^{BITS}` to be provided for efficiency.
+ fn mul_mod(&self, rhs: &Rhs, p: &Self, p_inv: Limb) -> Self::Output;
+}
+
+/// Checked addition.
+pub trait CheckedAdd<Rhs = Self>: Sized {
+ /// Output type.
+ type Output;
+
+ /// Perform checked subtraction, returning a [`CtOption`] which `is_some`
+ /// only if the operation did not overflow.
+ fn checked_add(&self, rhs: Rhs) -> CtOption<Self>;
+}
+
+/// Checked multiplication.
+pub trait CheckedMul<Rhs = Self>: Sized {
+ /// Output type.
+ type Output;
+
+ /// Perform checked multiplication, returning a [`CtOption`] which `is_some`
+ /// only if the operation did not overflow.
+ fn checked_mul(&self, rhs: Rhs) -> CtOption<Self>;
+}
+
+/// Checked substraction.
+pub trait CheckedSub<Rhs = Self>: Sized {
+ /// Output type.
+ type Output;
+
+ /// Perform checked subtraction, returning a [`CtOption`] which `is_some`
+ /// only if the operation did not underflow.
+ fn checked_sub(&self, rhs: Rhs) -> CtOption<Self>;
+}
+
+/// Concatenate two numbers into a "wide" twice-width value, using the `rhs`
+/// value as the least significant value.
+pub trait Concat<Rhs = Self> {
+ /// Concatenated output: twice the width of `Self`.
+ type Output;
+
+ /// Concatenate the two values, with `self` as most significant and `rhs`
+ /// as the least significant.
+ fn concat(&self, rhs: &Self) -> Self::Output;
+}
+
+/// Split a number in half, returning the most significant half followed by
+/// the least significant.
+pub trait Split<Rhs = Self> {
+ /// Split output: high/low components of the value.
+ type Output;
+
+ /// Split this number in half, returning its high and low components
+ /// respectively.
+ fn split(&self) -> (Self::Output, Self::Output);
+}
+
+/// Encoding support.
+pub trait Encoding: Sized {
+ /// Size of this integer in bits.
+ const BIT_SIZE: usize;
+
+ /// Size of this integer in bytes.
+ const BYTE_SIZE: usize;
+
+ /// Byte array representation.
+ type Repr: AsRef<[u8]> + AsMut<[u8]> + Copy + Clone + Sized;
+
+ /// Decode from big endian bytes.
+ fn from_be_bytes(bytes: Self::Repr) -> Self;
+
+ /// Decode from little endian bytes.
+ fn from_le_bytes(bytes: Self::Repr) -> Self;
+
+ /// Encode to big endian bytes.
+ fn to_be_bytes(&self) -> Self::Repr;
+
+ /// Encode to little endian bytes.
+ fn to_le_bytes(&self) -> Self::Repr;
+}
diff --git a/vendor/crypto-bigint/src/uint.rs b/vendor/crypto-bigint/src/uint.rs
new file mode 100644
index 000000000..5aac67c5a
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint.rs
@@ -0,0 +1,484 @@
+//! Big unsigned integers.
+
+#![allow(
+ clippy::needless_range_loop,
+ clippy::many_single_char_names,
+ clippy::derive_hash_xor_eq
+)]
+
+#[macro_use]
+mod concat;
+#[macro_use]
+mod split;
+
+mod add;
+mod add_mod;
+mod bit_and;
+mod bit_not;
+mod bit_or;
+mod bit_xor;
+mod bits;
+mod cmp;
+mod div;
+mod encoding;
+mod from;
+mod inv_mod;
+mod mul;
+mod mul_mod;
+mod neg_mod;
+mod resize;
+mod shl;
+mod shr;
+mod sqrt;
+mod sub;
+mod sub_mod;
+
+#[cfg(feature = "generic-array")]
+mod array;
+
+#[cfg(feature = "rand_core")]
+mod rand;
+
+use crate::{Concat, Encoding, Integer, Limb, Split, Word, Zero};
+use core::{fmt, mem};
+use subtle::{Choice, ConditionallySelectable};
+
+#[cfg(feature = "serde")]
+use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
+
+#[cfg(feature = "zeroize")]
+use zeroize::DefaultIsZeroes;
+
+/// Big unsigned integer.
+///
+/// Generic over the given number of `LIMBS`
+///
+/// # Encoding support
+/// This type supports many different types of encodings, either via the
+/// [`Encoding`][`crate::Encoding`] trait or various `const fn` decoding and
+/// encoding functions that can be used with [`UInt`] constants.
+///
+/// Optional crate features for encoding (off-by-default):
+/// - `generic-array`: enables [`ArrayEncoding`][`crate::ArrayEncoding`] trait which can be used to
+/// [`UInt`] as `GenericArray<u8, N>` and a [`ArrayDecoding`][`crate::ArrayDecoding`] trait which
+/// can be used to `GenericArray<u8, N>` as [`UInt`].
+/// - `rlp`: support for [Recursive Length Prefix (RLP)][RLP] encoding.
+///
+/// [RLP]: https://eth.wiki/fundamentals/rlp
+// TODO(tarcieri): make generic around a specified number of bits.
+#[derive(Copy, Clone, Debug, Hash)]
+pub struct UInt<const LIMBS: usize> {
+ /// Inner limb array. Stored from least significant to most significant.
+ limbs: [Limb; LIMBS],
+}
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// The value `0`.
+ pub const ZERO: Self = Self::from_u8(0);
+
+ /// The value `1`.
+ pub const ONE: Self = Self::from_u8(1);
+
+ /// The number of limbs used on this platform.
+ pub const LIMBS: usize = LIMBS;
+
+ /// Maximum value this [`UInt`] can express.
+ pub const MAX: Self = Self {
+ limbs: [Limb::MAX; LIMBS],
+ };
+
+ /// Const-friendly [`UInt`] constructor.
+ pub const fn new(limbs: [Limb; LIMBS]) -> Self {
+ Self { limbs }
+ }
+
+ /// Create a [`UInt`] from an array of [`Word`]s (i.e. word-sized unsigned
+ /// integers).
+ #[inline]
+ pub const fn from_words(arr: [Word; LIMBS]) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+ let mut i = 0;
+
+ while i < LIMBS {
+ limbs[i] = Limb(arr[i]);
+ i += 1;
+ }
+
+ Self { limbs }
+ }
+
+ /// Create an array of [`Word`]s (i.e. word-sized unsigned integers) from
+ /// a [`UInt`].
+ #[inline]
+ pub const fn to_words(self) -> [Word; LIMBS] {
+ let mut arr = [0; LIMBS];
+ let mut i = 0;
+
+ while i < LIMBS {
+ arr[i] = self.limbs[i].0;
+ i += 1;
+ }
+
+ arr
+ }
+
+ /// Borrow the inner limbs as an array of [`Word`]s.
+ pub const fn as_words(&self) -> &[Word; LIMBS] {
+ // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
+ #[allow(unsafe_code)]
+ unsafe {
+ // TODO(tarcieri): use &*((&self.limbs as *const _) as *const [Word; LIMBS])
+ mem::transmute(&self.limbs)
+ }
+ }
+
+ /// Borrow the inner limbs as a mutable array of [`Word`]s.
+ pub fn as_words_mut(&mut self) -> &mut [Word; LIMBS] {
+ // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
+ #[allow(trivial_casts, unsafe_code)]
+ unsafe {
+ &mut *((&mut self.limbs as *mut _) as *mut [Word; LIMBS])
+ }
+ }
+
+ /// Deprecated: borrow the inner limbs as an array of [`Word`]s.
+ #[deprecated(since = "0.4.8", note = "please use `as_words` instead")]
+ pub const fn as_uint_array(&self) -> &[Word; LIMBS] {
+ self.as_words()
+ }
+
+ /// Deprecated: create a [`UInt`] from an array of [`Word`]s.
+ #[deprecated(since = "0.4.8", note = "please use `from_words` instead")]
+ pub const fn from_uint_array(words: [Word; LIMBS]) -> Self {
+ Self::from_words(words)
+ }
+
+ /// Deprecated: create an array of [`Word`]s from a [`UInt`].
+ #[deprecated(since = "0.4.8", note = "please use `to_words` instead")]
+ pub const fn to_uint_array(self) -> [Word; LIMBS] {
+ self.to_words()
+ }
+
+ /// Borrow the limbs of this [`UInt`].
+ // TODO(tarcieri): rename to `as_limbs` for consistency with `as_words`
+ pub const fn limbs(&self) -> &[Limb; LIMBS] {
+ &self.limbs
+ }
+
+ /// Borrow the limbs of this [`UInt`] mutably.
+ // TODO(tarcieri): rename to `as_limbs_mut` for consistency with `as_words_mut`
+ pub fn limbs_mut(&mut self) -> &mut [Limb; LIMBS] {
+ &mut self.limbs
+ }
+
+ /// Convert this [`UInt`] into its inner limbs.
+ // TODO(tarcieri): rename to `to_limbs` for consistency with `to_words`
+ pub const fn into_limbs(self) -> [Limb; LIMBS] {
+ self.limbs
+ }
+}
+
+impl<const LIMBS: usize> AsRef<[Word; LIMBS]> for UInt<LIMBS> {
+ fn as_ref(&self) -> &[Word; LIMBS] {
+ self.as_words()
+ }
+}
+
+impl<const LIMBS: usize> AsMut<[Word; LIMBS]> for UInt<LIMBS> {
+ fn as_mut(&mut self) -> &mut [Word; LIMBS] {
+ self.as_words_mut()
+ }
+}
+
+// TODO(tarcieri): eventually phase this out in favor of `limbs()`?
+impl<const LIMBS: usize> AsRef<[Limb]> for UInt<LIMBS> {
+ fn as_ref(&self) -> &[Limb] {
+ self.limbs()
+ }
+}
+
+// TODO(tarcieri): eventually phase this out in favor of `limbs_mut()`?
+impl<const LIMBS: usize> AsMut<[Limb]> for UInt<LIMBS> {
+ fn as_mut(&mut self) -> &mut [Limb] {
+ self.limbs_mut()
+ }
+}
+
+impl<const LIMBS: usize> ConditionallySelectable for UInt<LIMBS> {
+ fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+
+ for i in 0..LIMBS {
+ limbs[i] = Limb::conditional_select(&a.limbs[i], &b.limbs[i], choice);
+ }
+
+ Self { limbs }
+ }
+}
+
+impl<const LIMBS: usize> Default for UInt<LIMBS> {
+ fn default() -> Self {
+ Self::ZERO
+ }
+}
+
+impl<const LIMBS: usize> Integer for UInt<LIMBS> {
+ const ONE: Self = Self::ONE;
+ const MAX: Self = Self::MAX;
+
+ fn is_odd(&self) -> Choice {
+ self.limbs
+ .first()
+ .map(|limb| limb.is_odd())
+ .unwrap_or_else(|| Choice::from(0))
+ }
+}
+
+impl<const LIMBS: usize> Zero for UInt<LIMBS> {
+ const ZERO: Self = Self::ZERO;
+}
+
+impl<const LIMBS: usize> fmt::Display for UInt<LIMBS> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::UpperHex::fmt(self, f)
+ }
+}
+
+impl<const LIMBS: usize> fmt::LowerHex for UInt<LIMBS> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ for limb in self.limbs.iter().rev() {
+ fmt::LowerHex::fmt(limb, f)?;
+ }
+ Ok(())
+ }
+}
+
+impl<const LIMBS: usize> fmt::UpperHex for UInt<LIMBS> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ for limb in self.limbs.iter().rev() {
+ fmt::UpperHex::fmt(limb, f)?;
+ }
+ Ok(())
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de, const LIMBS: usize> Deserialize<'de> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Encoding,
+{
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ let mut buffer = Self::ZERO.to_le_bytes();
+ serdect::array::deserialize_hex_or_bin(buffer.as_mut(), deserializer)?;
+
+ Ok(Self::from_le_bytes(buffer))
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de, const LIMBS: usize> Serialize for UInt<LIMBS>
+where
+ UInt<LIMBS>: Encoding,
+{
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ serdect::array::serialize_hex_lower_or_bin(&Encoding::to_le_bytes(self), serializer)
+ }
+}
+
+#[cfg(feature = "zeroize")]
+#[cfg_attr(docsrs, doc(cfg(feature = "zeroize")))]
+impl<const LIMBS: usize> DefaultIsZeroes for UInt<LIMBS> {}
+
+// TODO(tarcieri): use `const_evaluatable_checked` when stable to make generic around bits.
+macro_rules! impl_uint_aliases {
+ ($(($name:ident, $bits:expr, $doc:expr)),+) => {
+ $(
+ #[doc = $doc]
+ #[doc="unsigned big integer."]
+ pub type $name = UInt<{nlimbs!($bits)}>;
+
+ impl Encoding for $name {
+ const BIT_SIZE: usize = $bits;
+ const BYTE_SIZE: usize = $bits / 8;
+
+ type Repr = [u8; $bits / 8];
+
+ #[inline]
+ fn from_be_bytes(bytes: Self::Repr) -> Self {
+ Self::from_be_slice(&bytes)
+ }
+
+ #[inline]
+ fn from_le_bytes(bytes: Self::Repr) -> Self {
+ Self::from_le_slice(&bytes)
+ }
+
+ #[inline]
+ fn to_be_bytes(&self) -> Self::Repr {
+ let mut result = [0u8; $bits / 8];
+ self.write_be_bytes(&mut result);
+ result
+ }
+
+ #[inline]
+ fn to_le_bytes(&self) -> Self::Repr {
+ let mut result = [0u8; $bits / 8];
+ self.write_le_bytes(&mut result);
+ result
+ }
+ }
+ )+
+ };
+}
+
+// TODO(tarcieri): use `const_evaluatable_checked` when stable to make generic around bits.
+impl_uint_aliases! {
+ (U64, 64, "64-bit"),
+ (U128, 128, "128-bit"),
+ (U192, 192, "192-bit"),
+ (U256, 256, "256-bit"),
+ (U384, 384, "384-bit"),
+ (U448, 448, "448-bit"),
+ (U512, 512, "512-bit"),
+ (U576, 576, "576-bit"),
+ (U768, 768, "768-bit"),
+ (U896, 896, "896-bit"),
+ (U1024, 1024, "1024-bit"),
+ (U1536, 1536, "1536-bit"),
+ (U1792, 1792, "1792-bit"),
+ (U2048, 2048, "2048-bit"),
+ (U3072, 3072, "3072-bit"),
+ (U3584, 3584, "3584-bit"),
+ (U4096, 4096, "4096-bit"),
+ (U6144, 6144, "6144-bit"),
+ (U8192, 8192, "8192-bit")
+}
+
+// TODO(tarcieri): use `const_evaluatable_checked` when stable to make generic around bits.
+impl_concat! {
+ (U64, 64),
+ (U128, 128),
+ (U192, 192),
+ (U256, 256),
+ (U384, 384),
+ (U448, 448),
+ (U512, 512),
+ (U768, 768),
+ (U896, 896),
+ (U1024, 1024),
+ (U1536, 1536),
+ (U1792, 1792),
+ (U2048, 2048),
+ (U3072, 3072),
+ (U4096, 4096)
+}
+
+// TODO(tarcieri): use `const_evaluatable_checked` when stable to make generic around bits.
+impl_split! {
+ (U128, 128),
+ (U192, 192),
+ (U256, 256),
+ (U384, 384),
+ (U448, 448),
+ (U512, 512),
+ (U768, 768),
+ (U896, 896),
+ (U1024, 1024),
+ (U1536, 1536),
+ (U1792, 1792),
+ (U2048, 2048),
+ (U3072, 3072),
+ (U3584, 3584),
+ (U4096, 4096),
+ (U6144, 6144),
+ (U8192, 8192)
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{Encoding, U128};
+ use subtle::ConditionallySelectable;
+
+ #[cfg(feature = "serde")]
+ use crate::U64;
+
+ #[test]
+ #[cfg(feature = "alloc")]
+ fn display() {
+ let hex = "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD";
+ let n = U128::from_be_hex(hex);
+
+ use alloc::string::ToString;
+ assert_eq!(hex, n.to_string());
+
+ let hex = "AAAAAAAABBBBBBBB0000000000000000";
+ let n = U128::from_be_hex(hex);
+ assert_eq!(hex, n.to_string());
+
+ let hex = "AAAAAAAABBBBBBBB00000000DDDDDDDD";
+ let n = U128::from_be_hex(hex);
+ assert_eq!(hex, n.to_string());
+
+ let hex = "AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD";
+ let n = U128::from_be_hex(hex);
+ assert_eq!(hex, n.to_string());
+ }
+
+ #[test]
+ fn from_bytes() {
+ let a = U128::from_be_hex("AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD");
+
+ let be_bytes = a.to_be_bytes();
+ let le_bytes = a.to_le_bytes();
+ for i in 0..16 {
+ assert_eq!(le_bytes[i], be_bytes[15 - i]);
+ }
+
+ let a_from_be = U128::from_be_bytes(be_bytes);
+ let a_from_le = U128::from_le_bytes(le_bytes);
+ assert_eq!(a_from_be, a_from_le);
+ assert_eq!(a_from_be, a);
+ }
+
+ #[test]
+ fn conditional_select() {
+ let a = U128::from_be_hex("00002222444466668888AAAACCCCEEEE");
+ let b = U128::from_be_hex("11113333555577779999BBBBDDDDFFFF");
+
+ let select_0 = U128::conditional_select(&a, &b, 0.into());
+ assert_eq!(a, select_0);
+
+ let select_1 = U128::conditional_select(&a, &b, 1.into());
+ assert_eq!(b, select_1);
+ }
+
+ #[test]
+ #[cfg(feature = "serde")]
+ fn serde() {
+ const TEST: U64 = U64::from_u64(0x0011223344556677);
+
+ let serialized = bincode::serialize(&TEST).unwrap();
+ let deserialized: U64 = bincode::deserialize(&serialized).unwrap();
+
+ assert_eq!(TEST, deserialized);
+ }
+
+ #[test]
+ #[cfg(feature = "serde")]
+ fn serde_owned() {
+ const TEST: U64 = U64::from_u64(0x0011223344556677);
+
+ let serialized = bincode::serialize(&TEST).unwrap();
+ let deserialized: U64 = bincode::deserialize_from(serialized.as_slice()).unwrap();
+
+ assert_eq!(TEST, deserialized);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/add.rs b/vendor/crypto-bigint/src/uint/add.rs
new file mode 100644
index 000000000..2822e9e67
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/add.rs
@@ -0,0 +1,189 @@
+//! [`UInt`] addition operations.
+
+use crate::{Checked, CheckedAdd, Limb, UInt, Wrapping, Zero};
+use core::ops::{Add, AddAssign};
+use subtle::CtOption;
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `a + b + carry`, returning the result along with the new carry.
+ #[inline(always)]
+ pub const fn adc(&self, rhs: &Self, mut carry: Limb) -> (Self, Limb) {
+ let mut limbs = [Limb::ZERO; LIMBS];
+ let mut i = 0;
+
+ while i < LIMBS {
+ let (w, c) = self.limbs[i].adc(rhs.limbs[i], carry);
+ limbs[i] = w;
+ carry = c;
+ i += 1;
+ }
+
+ (Self { limbs }, carry)
+ }
+
+ /// Perform saturating addition, returning `MAX` on overflow.
+ pub const fn saturating_add(&self, rhs: &Self) -> Self {
+ let (res, overflow) = self.adc(rhs, Limb::ZERO);
+
+ if overflow.0 == 0 {
+ res
+ } else {
+ Self::MAX
+ }
+ }
+
+ /// Perform wrapping addition, discarding overflow.
+ pub const fn wrapping_add(&self, rhs: &Self) -> Self {
+ self.adc(rhs, Limb::ZERO).0
+ }
+}
+
+impl<const LIMBS: usize> CheckedAdd<&UInt<LIMBS>> for UInt<LIMBS> {
+ type Output = Self;
+
+ fn checked_add(&self, rhs: &Self) -> CtOption<Self> {
+ let (result, carry) = self.adc(rhs, Limb::ZERO);
+ CtOption::new(result, carry.is_zero())
+ }
+}
+
+impl<const LIMBS: usize> Add for Wrapping<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn add(self, rhs: Self) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_add(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Add<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn add(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_add(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Add<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn add(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_add(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Add<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn add(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_add(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> AddAssign for Wrapping<UInt<LIMBS>> {
+ fn add_assign(&mut self, other: Self) {
+ *self = *self + other;
+ }
+}
+
+impl<const LIMBS: usize> AddAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn add_assign(&mut self, other: &Self) {
+ *self = *self + other;
+ }
+}
+
+impl<const LIMBS: usize> Add for Checked<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn add(self, rhs: Self) -> Checked<UInt<LIMBS>> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_add(&rhs))),
+ )
+ }
+}
+
+impl<const LIMBS: usize> Add<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn add(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_add(&rhs))),
+ )
+ }
+}
+
+impl<const LIMBS: usize> Add<Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn add(self, rhs: Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_add(&rhs))),
+ )
+ }
+}
+
+impl<const LIMBS: usize> Add<&Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn add(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_add(&rhs))),
+ )
+ }
+}
+
+impl<const LIMBS: usize> AddAssign for Checked<UInt<LIMBS>> {
+ fn add_assign(&mut self, other: Self) {
+ *self = *self + other;
+ }
+}
+
+impl<const LIMBS: usize> AddAssign<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
+ fn add_assign(&mut self, other: &Self) {
+ *self = *self + other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{CheckedAdd, Limb, U128};
+
+ #[test]
+ fn adc_no_carry() {
+ let (res, carry) = U128::ZERO.adc(&U128::ONE, Limb::ZERO);
+ assert_eq!(res, U128::ONE);
+ assert_eq!(carry, Limb::ZERO);
+ }
+
+ #[test]
+ fn adc_with_carry() {
+ let (res, carry) = U128::MAX.adc(&U128::ONE, Limb::ZERO);
+ assert_eq!(res, U128::ZERO);
+ assert_eq!(carry, Limb::ONE);
+ }
+
+ #[test]
+ fn wrapping_add_no_carry() {
+ assert_eq!(U128::ZERO.wrapping_add(&U128::ONE), U128::ONE);
+ }
+
+ #[test]
+ fn wrapping_add_with_carry() {
+ assert_eq!(U128::MAX.wrapping_add(&U128::ONE), U128::ZERO);
+ }
+
+ #[test]
+ fn checked_add_ok() {
+ let result = U128::ZERO.checked_add(&U128::ONE);
+ assert_eq!(result.unwrap(), U128::ONE);
+ }
+
+ #[test]
+ fn checked_add_overflow() {
+ let result = U128::MAX.checked_add(&U128::ONE);
+ assert!(!bool::from(result.is_some()));
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/add_mod.rs b/vendor/crypto-bigint/src/uint/add_mod.rs
new file mode 100644
index 000000000..3486a0a57
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/add_mod.rs
@@ -0,0 +1,139 @@
+//! [`UInt`] addition modulus operations.
+
+use crate::{AddMod, Limb, UInt};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `self + rhs mod p` in constant time.
+ ///
+ /// Assumes `self + rhs` as unbounded integer is `< 2p`.
+ pub const fn add_mod(&self, rhs: &UInt<LIMBS>, p: &UInt<LIMBS>) -> UInt<LIMBS> {
+ let (w, carry) = self.adc(rhs, Limb::ZERO);
+
+ // Attempt to subtract the modulus, to ensure the result is in the field.
+ let (w, borrow) = w.sbb(p, Limb::ZERO);
+ let (_, borrow) = carry.sbb(Limb::ZERO, borrow);
+
+ // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
+ // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the
+ // modulus.
+ let mut i = 0;
+ let mut res = Self::ZERO;
+ let mut carry = Limb::ZERO;
+
+ while i < LIMBS {
+ let rhs = p.limbs[i].bitand(borrow);
+ let (limb, c) = w.limbs[i].adc(rhs, carry);
+ res.limbs[i] = limb;
+ carry = c;
+ i += 1;
+ }
+
+ res
+ }
+
+ /// Computes `self + rhs mod p` in constant time for the special modulus
+ /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
+ ///
+ /// Assumes `self + rhs` as unbounded integer is `< 2p`.
+ pub const fn add_mod_special(&self, rhs: &Self, c: Limb) -> Self {
+ // `UInt::adc` also works with a carry greater than 1.
+ let (out, carry) = self.adc(rhs, c);
+
+ // If overflow occurred, then above addition of `c` already accounts
+ // for the overflow. Otherwise, we need to subtract `c` again, which
+ // in that case cannot underflow.
+ let l = carry.0.wrapping_sub(1) & c.0;
+ let (out, _) = out.sbb(&UInt::from_word(l), Limb::ZERO);
+ out
+ }
+}
+
+impl<const LIMBS: usize> AddMod for UInt<LIMBS> {
+ type Output = Self;
+
+ fn add_mod(&self, rhs: &Self, p: &Self) -> Self {
+ debug_assert!(self < p);
+ debug_assert!(rhs < p);
+ self.add_mod(rhs, p)
+ }
+}
+
+#[cfg(all(test, feature = "rand"))]
+mod tests {
+ use crate::{Limb, NonZero, Random, RandomMod, UInt, U256};
+ use rand_core::SeedableRng;
+
+ // TODO(tarcieri): additional tests + proptests
+
+ #[test]
+ fn add_mod_nist_p256() {
+ let a =
+ U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+ let b =
+ U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251");
+ let n =
+ U256::from_be_hex("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551");
+
+ let actual = a.add_mod(&b, &n);
+ let expected =
+ U256::from_be_hex("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956");
+
+ assert_eq!(expected, actual);
+ }
+
+ macro_rules! test_add_mod_special {
+ ($size:expr, $test_name:ident) => {
+ #[test]
+ fn $test_name() {
+ let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
+ let moduli = [
+ NonZero::<Limb>::random(&mut rng),
+ NonZero::<Limb>::random(&mut rng),
+ ];
+
+ for special in &moduli {
+ let p = &NonZero::new(UInt::ZERO.wrapping_sub(&UInt::from_word(special.0)))
+ .unwrap();
+
+ let minus_one = p.wrapping_sub(&UInt::ONE);
+
+ let base_cases = [
+ (UInt::ZERO, UInt::ZERO, UInt::ZERO),
+ (UInt::ONE, UInt::ZERO, UInt::ONE),
+ (UInt::ZERO, UInt::ONE, UInt::ONE),
+ (minus_one, UInt::ONE, UInt::ZERO),
+ (UInt::ONE, minus_one, UInt::ZERO),
+ ];
+ for (a, b, c) in &base_cases {
+ let x = a.add_mod_special(b, *special.as_ref());
+ assert_eq!(*c, x, "{} + {} mod {} = {} != {}", a, b, p, x, c);
+ }
+
+ for _i in 0..100 {
+ let a = UInt::<$size>::random_mod(&mut rng, p);
+ let b = UInt::<$size>::random_mod(&mut rng, p);
+
+ let c = a.add_mod_special(&b, *special.as_ref());
+ assert!(c < **p, "not reduced: {} >= {} ", c, p);
+
+ let expected = a.add_mod(&b, p);
+ assert_eq!(c, expected, "incorrect result");
+ }
+ }
+ }
+ };
+ }
+
+ test_add_mod_special!(1, add_mod_special_1);
+ test_add_mod_special!(2, add_mod_special_2);
+ test_add_mod_special!(3, add_mod_special_3);
+ test_add_mod_special!(4, add_mod_special_4);
+ test_add_mod_special!(5, add_mod_special_5);
+ test_add_mod_special!(6, add_mod_special_6);
+ test_add_mod_special!(7, add_mod_special_7);
+ test_add_mod_special!(8, add_mod_special_8);
+ test_add_mod_special!(9, add_mod_special_9);
+ test_add_mod_special!(10, add_mod_special_10);
+ test_add_mod_special!(11, add_mod_special_11);
+ test_add_mod_special!(12, add_mod_special_12);
+}
diff --git a/vendor/crypto-bigint/src/uint/array.rs b/vendor/crypto-bigint/src/uint/array.rs
new file mode 100644
index 000000000..cba2b3716
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/array.rs
@@ -0,0 +1,189 @@
+//! `generic-array` integration with `UInt`.
+// TODO(tarcieri): completely phase out `generic-array` when const generics are powerful enough
+
+use crate::{ArrayDecoding, ArrayEncoding, ByteArray};
+use generic_array::{typenum, GenericArray};
+
+macro_rules! impl_uint_array_encoding {
+ ($(($uint:ident, $bytes:path)),+) => {
+ $(
+ #[cfg_attr(docsrs, doc(cfg(feature = "generic-array")))]
+ impl ArrayEncoding for super::$uint {
+ type ByteSize = $bytes;
+
+ #[inline]
+ fn from_be_byte_array(bytes: ByteArray<Self>) -> Self {
+ Self::from_be_slice(&bytes)
+ }
+
+ #[inline]
+ fn from_le_byte_array(bytes: ByteArray<Self>) -> Self {
+ Self::from_le_slice(&bytes)
+ }
+
+ #[inline]
+ fn to_be_byte_array(&self) -> ByteArray<Self> {
+ let mut result = GenericArray::default();
+ self.write_be_bytes(&mut result);
+ result
+ }
+
+ #[inline]
+ fn to_le_byte_array(&self) -> ByteArray<Self> {
+ let mut result = GenericArray::default();
+ self.write_le_bytes(&mut result);
+ result
+ }
+ }
+
+ #[cfg_attr(docsrs, doc(cfg(feature = "generic-array")))]
+ impl ArrayDecoding for GenericArray<u8, $bytes> {
+ type Output = super::$uint;
+
+ fn into_uint_be(self) -> Self::Output {
+ Self::Output::from_be_byte_array(self)
+ }
+
+ fn into_uint_le(self) -> Self::Output {
+ Self::Output::from_le_byte_array(self)
+ }
+ }
+ )+
+ };
+}
+
+// TODO(tarcieri): use `const_evaluatable_checked` when stable to make generic around bits.
+impl_uint_array_encoding! {
+ (U64, typenum::U8),
+ (U128, typenum::U16),
+ (U192, typenum::U24),
+ (U256, typenum::U32),
+ (U384, typenum::U48),
+ (U448, typenum::U56),
+ (U512, typenum::U64),
+ (U576, typenum::U72),
+ (U768, typenum::U96),
+ (U896, typenum::U112),
+ (U1024, typenum::U128),
+ (U1536, typenum::U192),
+ (U1792, typenum::U224),
+ (U2048, typenum::U256),
+ (U3072, typenum::U384),
+ (U3584, typenum::U448),
+ (U4096, typenum::U512),
+ (U6144, typenum::U768),
+ (U8192, typenum::U1024)
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{ArrayDecoding, ArrayEncoding, Limb};
+ use hex_literal::hex;
+
+ #[cfg(target_pointer_width = "32")]
+ use crate::U64 as UIntEx;
+
+ #[cfg(target_pointer_width = "64")]
+ use crate::U128 as UIntEx;
+
+ /// Byte array that corresponds to `UIntEx`
+ type ByteArray = crate::ByteArray<UIntEx>;
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn from_be_byte_array() {
+ let n = UIntEx::from_be_byte_array(hex!("0011223344556677").into());
+ assert_eq!(n.limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn from_be_byte_array() {
+ let n = UIntEx::from_be_byte_array(hex!("00112233445566778899aabbccddeeff").into());
+ assert_eq!(
+ n.limbs(),
+ &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
+ );
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn from_le_byte_array() {
+ let n = UIntEx::from_le_byte_array(hex!("7766554433221100").into());
+ assert_eq!(n.limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn from_le_byte_array() {
+ let n = UIntEx::from_le_byte_array(hex!("ffeeddccbbaa99887766554433221100").into());
+ assert_eq!(
+ n.limbs(),
+ &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
+ );
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn to_be_byte_array() {
+ let expected_bytes = ByteArray::from(hex!("0011223344556677"));
+ let actual_bytes = UIntEx::from_be_byte_array(expected_bytes).to_be_byte_array();
+ assert_eq!(expected_bytes, actual_bytes);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn to_be_byte_array() {
+ let expected_bytes = ByteArray::from(hex!("00112233445566778899aabbccddeeff"));
+ let actual_bytes = UIntEx::from_be_byte_array(expected_bytes).to_be_byte_array();
+ assert_eq!(expected_bytes, actual_bytes);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn to_le_byte_array() {
+ let expected_bytes = ByteArray::from(hex!("7766554433221100"));
+ let actual_bytes = UIntEx::from_le_byte_array(expected_bytes).to_le_byte_array();
+ assert_eq!(expected_bytes, actual_bytes);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn to_le_byte_array() {
+ let expected_bytes = ByteArray::from(hex!("ffeeddccbbaa99887766554433221100"));
+ let actual_bytes = UIntEx::from_le_byte_array(expected_bytes).to_le_byte_array();
+ assert_eq!(expected_bytes, actual_bytes);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn into_uint_be() {
+ let expected_bytes = ByteArray::from(hex!("0011223344556677"));
+ let actual_bytes = expected_bytes.into_uint_be().to_be_byte_array();
+ assert_eq!(expected_bytes, actual_bytes);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn into_uint_be() {
+ let expected_bytes = ByteArray::from(hex!("00112233445566778899aabbccddeeff"));
+ let actual_bytes = expected_bytes.into_uint_be().to_be_byte_array();
+ assert_eq!(expected_bytes, actual_bytes);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn into_uint_le() {
+ let expected_bytes = ByteArray::from(hex!("7766554433221100"));
+ let actual_bytes = expected_bytes.into_uint_le().to_le_byte_array();
+ assert_eq!(expected_bytes, actual_bytes);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn into_uint_le() {
+ let expected_bytes = ByteArray::from(hex!("ffeeddccbbaa99887766554433221100"));
+ let actual_bytes = expected_bytes.into_uint_le().to_le_byte_array();
+ assert_eq!(expected_bytes, actual_bytes);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/bit_and.rs b/vendor/crypto-bigint/src/uint/bit_and.rs
new file mode 100644
index 000000000..cab89a429
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/bit_and.rs
@@ -0,0 +1,145 @@
+//! [`UInt`] bitwise and operations.
+
+use super::UInt;
+use crate::{Limb, Wrapping};
+use core::ops::{BitAnd, BitAndAssign};
+use subtle::{Choice, CtOption};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes bitwise `a & b`.
+ #[inline(always)]
+ pub const fn bitand(&self, rhs: &Self) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+ let mut i = 0;
+
+ while i < LIMBS {
+ limbs[i] = self.limbs[i].bitand(rhs.limbs[i]);
+ i += 1;
+ }
+
+ Self { limbs }
+ }
+
+ /// Perform wrapping bitwise `AND`.
+ ///
+ /// There's no way wrapping could ever happen.
+ /// This function exists so that all operations are accounted for in the wrapping operations
+ pub const fn wrapping_and(&self, rhs: &Self) -> Self {
+ self.bitand(rhs)
+ }
+
+ /// Perform checked bitwise `AND`, returning a [`CtOption`] which `is_some` always
+ pub fn checked_and(&self, rhs: &Self) -> CtOption<Self> {
+ let result = self.bitand(rhs);
+ CtOption::new(result, Choice::from(1))
+ }
+}
+
+impl<const LIMBS: usize> BitAnd for UInt<LIMBS> {
+ type Output = Self;
+
+ fn bitand(self, rhs: Self) -> UInt<LIMBS> {
+ self.bitand(&rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitAnd<&UInt<LIMBS>> for UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitand(self, rhs: &UInt<LIMBS>) -> UInt<LIMBS> {
+ (&self).bitand(rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitAnd<UInt<LIMBS>> for &UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitand(self, rhs: UInt<LIMBS>) -> UInt<LIMBS> {
+ self.bitand(&rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitAnd<&UInt<LIMBS>> for &UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitand(self, rhs: &UInt<LIMBS>) -> UInt<LIMBS> {
+ self.bitand(rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitAndAssign for UInt<LIMBS> {
+ #[allow(clippy::assign_op_pattern)]
+ fn bitand_assign(&mut self, other: Self) {
+ *self = *self & other;
+ }
+}
+
+impl<const LIMBS: usize> BitAndAssign<&UInt<LIMBS>> for UInt<LIMBS> {
+ #[allow(clippy::assign_op_pattern)]
+ fn bitand_assign(&mut self, other: &Self) {
+ *self = *self & other;
+ }
+}
+
+impl<const LIMBS: usize> BitAnd for Wrapping<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn bitand(self, rhs: Self) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitand(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitAnd<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitand(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitand(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitAnd<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitand(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitand(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitAnd<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitand(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitand(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitAndAssign for Wrapping<UInt<LIMBS>> {
+ #[allow(clippy::assign_op_pattern)]
+ fn bitand_assign(&mut self, other: Self) {
+ *self = *self & other;
+ }
+}
+
+impl<const LIMBS: usize> BitAndAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ #[allow(clippy::assign_op_pattern)]
+ fn bitand_assign(&mut self, other: &Self) {
+ *self = *self & other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U128;
+
+ #[test]
+ fn checked_and_ok() {
+ let result = U128::ZERO.checked_and(&U128::ONE);
+ assert_eq!(result.unwrap(), U128::ZERO);
+ }
+
+ #[test]
+ fn overlapping_and_ok() {
+ let result = U128::MAX.wrapping_and(&U128::ONE);
+ assert_eq!(result, U128::ONE);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/bit_not.rs b/vendor/crypto-bigint/src/uint/bit_not.rs
new file mode 100644
index 000000000..747d3b49e
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/bit_not.rs
@@ -0,0 +1,48 @@
+//! [`UInt`] bitwise not operations.
+
+use super::UInt;
+use crate::{Limb, Wrapping};
+use core::ops::Not;
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes bitwise `!a`.
+ #[inline(always)]
+ pub const fn not(&self) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+ let mut i = 0;
+
+ while i < LIMBS {
+ limbs[i] = self.limbs[i].not();
+ i += 1;
+ }
+
+ Self { limbs }
+ }
+}
+
+impl<const LIMBS: usize> Not for UInt<LIMBS> {
+ type Output = Self;
+
+ fn not(self) -> <Self as Not>::Output {
+ (&self).not()
+ }
+}
+
+impl<const LIMBS: usize> Not for Wrapping<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn not(self) -> <Self as Not>::Output {
+ Wrapping(self.0.not())
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U128;
+
+ #[test]
+ fn bitnot_ok() {
+ assert_eq!(U128::ZERO.not(), U128::MAX);
+ assert_eq!(U128::MAX.not(), U128::ZERO);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/bit_or.rs b/vendor/crypto-bigint/src/uint/bit_or.rs
new file mode 100644
index 000000000..4a01a8343
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/bit_or.rs
@@ -0,0 +1,141 @@
+//! [`UInt`] bitwise or operations.
+
+use super::UInt;
+use crate::{Limb, Wrapping};
+use core::ops::{BitOr, BitOrAssign};
+use subtle::{Choice, CtOption};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes bitwise `a & b`.
+ #[inline(always)]
+ pub const fn bitor(&self, rhs: &Self) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+ let mut i = 0;
+
+ while i < LIMBS {
+ limbs[i] = self.limbs[i].bitor(rhs.limbs[i]);
+ i += 1;
+ }
+
+ Self { limbs }
+ }
+
+ /// Perform wrapping bitwise `OR`.
+ ///
+ /// There's no way wrapping could ever happen.
+ /// This function exists so that all operations are accounted for in the wrapping operations
+ pub const fn wrapping_or(&self, rhs: &Self) -> Self {
+ self.bitor(rhs)
+ }
+
+ /// Perform checked bitwise `OR`, returning a [`CtOption`] which `is_some` always
+ pub fn checked_or(&self, rhs: &Self) -> CtOption<Self> {
+ let result = self.bitor(rhs);
+ CtOption::new(result, Choice::from(1))
+ }
+}
+
+impl<const LIMBS: usize> BitOr for UInt<LIMBS> {
+ type Output = Self;
+
+ fn bitor(self, rhs: Self) -> UInt<LIMBS> {
+ self.bitor(&rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitOr<&UInt<LIMBS>> for UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitor(self, rhs: &UInt<LIMBS>) -> UInt<LIMBS> {
+ (&self).bitor(rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitOr<UInt<LIMBS>> for &UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitor(self, rhs: UInt<LIMBS>) -> UInt<LIMBS> {
+ self.bitor(&rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitOr<&UInt<LIMBS>> for &UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitor(self, rhs: &UInt<LIMBS>) -> UInt<LIMBS> {
+ self.bitor(rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitOrAssign for UInt<LIMBS> {
+ fn bitor_assign(&mut self, other: Self) {
+ *self = *self | other;
+ }
+}
+
+impl<const LIMBS: usize> BitOrAssign<&UInt<LIMBS>> for UInt<LIMBS> {
+ fn bitor_assign(&mut self, other: &Self) {
+ *self = *self | other;
+ }
+}
+
+impl<const LIMBS: usize> BitOr for Wrapping<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn bitor(self, rhs: Self) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitor(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitOr<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitor(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitor(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitOr<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitor(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitor(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitOr<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitor(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitor(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitOrAssign for Wrapping<UInt<LIMBS>> {
+ fn bitor_assign(&mut self, other: Self) {
+ *self = *self | other;
+ }
+}
+
+impl<const LIMBS: usize> BitOrAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn bitor_assign(&mut self, other: &Self) {
+ *self = *self | other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U128;
+
+ #[test]
+ fn checked_or_ok() {
+ let result = U128::ZERO.checked_or(&U128::ONE);
+ assert_eq!(result.unwrap(), U128::ONE);
+ }
+
+ #[test]
+ fn overlapping_or_ok() {
+ let result = U128::MAX.wrapping_or(&U128::ONE);
+ assert_eq!(result, U128::MAX);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/bit_xor.rs b/vendor/crypto-bigint/src/uint/bit_xor.rs
new file mode 100644
index 000000000..16d78ad3a
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/bit_xor.rs
@@ -0,0 +1,141 @@
+//! [`UInt`] bitwise xor operations.
+
+use super::UInt;
+use crate::{Limb, Wrapping};
+use core::ops::{BitXor, BitXorAssign};
+use subtle::{Choice, CtOption};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes bitwise `a ^ b`.
+ #[inline(always)]
+ pub const fn bitxor(&self, rhs: &Self) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+ let mut i = 0;
+
+ while i < LIMBS {
+ limbs[i] = self.limbs[i].bitxor(rhs.limbs[i]);
+ i += 1;
+ }
+
+ Self { limbs }
+ }
+
+ /// Perform wrapping bitwise `XOR``.
+ ///
+ /// There's no way wrapping could ever happen.
+ /// This function exists so that all operations are accounted for in the wrapping operations
+ pub const fn wrapping_xor(&self, rhs: &Self) -> Self {
+ self.bitxor(rhs)
+ }
+
+ /// Perform checked bitwise `XOR`, returning a [`CtOption`] which `is_some` always
+ pub fn checked_xor(&self, rhs: &Self) -> CtOption<Self> {
+ let result = self.bitxor(rhs);
+ CtOption::new(result, Choice::from(1))
+ }
+}
+
+impl<const LIMBS: usize> BitXor for UInt<LIMBS> {
+ type Output = Self;
+
+ fn bitxor(self, rhs: Self) -> UInt<LIMBS> {
+ self.bitxor(&rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitXor<&UInt<LIMBS>> for UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitxor(self, rhs: &UInt<LIMBS>) -> UInt<LIMBS> {
+ (&self).bitxor(rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitXor<UInt<LIMBS>> for &UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitxor(self, rhs: UInt<LIMBS>) -> UInt<LIMBS> {
+ self.bitxor(&rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitXor<&UInt<LIMBS>> for &UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ fn bitxor(self, rhs: &UInt<LIMBS>) -> UInt<LIMBS> {
+ self.bitxor(rhs)
+ }
+}
+
+impl<const LIMBS: usize> BitXorAssign for UInt<LIMBS> {
+ fn bitxor_assign(&mut self, other: Self) {
+ *self = *self ^ other;
+ }
+}
+
+impl<const LIMBS: usize> BitXorAssign<&UInt<LIMBS>> for UInt<LIMBS> {
+ fn bitxor_assign(&mut self, other: &Self) {
+ *self = *self ^ other;
+ }
+}
+
+impl<const LIMBS: usize> BitXor for Wrapping<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn bitxor(self, rhs: Self) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitxor(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitXor<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitxor(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitxor(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitXor<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitxor(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitxor(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitXor<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn bitxor(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.bitxor(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> BitXorAssign for Wrapping<UInt<LIMBS>> {
+ fn bitxor_assign(&mut self, other: Self) {
+ *self = *self ^ other;
+ }
+}
+
+impl<const LIMBS: usize> BitXorAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn bitxor_assign(&mut self, other: &Self) {
+ *self = *self ^ other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U128;
+
+ #[test]
+ fn checked_xor_ok() {
+ let result = U128::ZERO.checked_xor(&U128::ONE);
+ assert_eq!(result.unwrap(), U128::ONE);
+ }
+
+ #[test]
+ fn overlapping_xor_ok() {
+ let result = U128::ZERO.wrapping_xor(&U128::ONE);
+ assert_eq!(result, U128::ONE);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/bits.rs b/vendor/crypto-bigint/src/uint/bits.rs
new file mode 100644
index 000000000..b76d89fa5
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/bits.rs
@@ -0,0 +1,55 @@
+use crate::{Limb, UInt, Word};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Get the value of the bit at position `index`, as a 0- or 1-valued Word.
+ /// Returns 0 for indices out of range.
+ #[inline(always)]
+ pub const fn bit_vartime(self, index: usize) -> Word {
+ if index >= LIMBS * Limb::BIT_SIZE {
+ 0
+ } else {
+ (self.limbs[index / Limb::BIT_SIZE].0 >> (index % Limb::BIT_SIZE)) & 1
+ }
+ }
+
+ /// Calculate the number of bits needed to represent this number.
+ #[deprecated(note = "please use `bits_vartime` instead")]
+ #[inline(always)]
+ pub const fn bits(self) -> usize {
+ self.bits_vartime()
+ }
+
+ /// Calculate the number of bits needed to represent this number.
+ #[allow(trivial_numeric_casts)]
+ pub const fn bits_vartime(self) -> usize {
+ let mut i = LIMBS - 1;
+ while i > 0 && self.limbs[i].0 == 0 {
+ i -= 1;
+ }
+
+ let limb = self.limbs[i].0;
+ let bits = (Limb::BIT_SIZE * (i + 1)) as Word - limb.leading_zeros() as Word;
+
+ Limb::ct_select(
+ Limb(bits),
+ Limb::ZERO,
+ !self.limbs[0].is_nonzero() & !Limb(i as Word).is_nonzero(),
+ )
+ .0 as usize
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U128;
+
+ #[test]
+ fn bit_vartime_ok() {
+ let u = U128::from_be_hex("f0010000000000000001000000010000");
+ assert_eq!(u.bit_vartime(0), 0);
+ assert_eq!(u.bit_vartime(1), 0);
+ assert_eq!(u.bit_vartime(16), 1);
+ assert_eq!(u.bit_vartime(127), 1);
+ assert_eq!(u.bit_vartime(130), 0);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/cmp.rs b/vendor/crypto-bigint/src/uint/cmp.rs
new file mode 100644
index 000000000..19046df9b
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/cmp.rs
@@ -0,0 +1,196 @@
+//! [`UInt`] comparisons.
+//!
+//! By default these are all constant-time and use the `subtle` crate.
+
+use super::UInt;
+use crate::{limb::HI_BIT, Limb, SignedWord, WideSignedWord, Word, Zero};
+use core::cmp::Ordering;
+use subtle::{Choice, ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Return `a` if `c`==0 or `b` if `c`==`Word::MAX`.
+ ///
+ /// Const-friendly: we can't yet use `subtle` in `const fn` contexts.
+ #[inline]
+ pub(crate) const fn ct_select(a: UInt<LIMBS>, b: UInt<LIMBS>, c: Word) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+
+ let mut i = 0;
+ while i < LIMBS {
+ limbs[i] = Limb::ct_select(a.limbs[i], b.limbs[i], c);
+ i += 1;
+ }
+
+ UInt { limbs }
+ }
+
+ /// Returns all 1's if `self`!=0 or 0 if `self`==0.
+ ///
+ /// Const-friendly: we can't yet use `subtle` in `const fn` contexts.
+ #[inline]
+ pub(crate) const fn ct_is_nonzero(&self) -> Word {
+ let mut b = 0;
+ let mut i = 0;
+ while i < LIMBS {
+ b |= self.limbs[i].0;
+ i += 1;
+ }
+ Limb::is_nonzero(Limb(b))
+ }
+
+ /// Returns -1 if self < rhs
+ /// 0 if self == rhs
+ /// 1 if self > rhs
+ ///
+ /// Const-friendly: we can't yet use `subtle` in `const fn` contexts.
+ #[inline]
+ pub(crate) const fn ct_cmp(&self, rhs: &Self) -> SignedWord {
+ let mut gt = 0;
+ let mut lt = 0;
+ let mut i = LIMBS;
+
+ while i > 0 {
+ let a = self.limbs[i - 1].0 as WideSignedWord;
+ let b = rhs.limbs[i - 1].0 as WideSignedWord;
+ gt |= ((b - a) >> Limb::BIT_SIZE) & 1 & !lt;
+ lt |= ((a - b) >> Limb::BIT_SIZE) & 1 & !gt;
+ i -= 1;
+ }
+ (gt as SignedWord) - (lt as SignedWord)
+ }
+
+ /// Returns 0 if self == rhs or Word::MAX if self != rhs.
+ /// Const-friendly: we can't yet use `subtle` in `const fn` contexts.
+ #[inline]
+ pub(crate) const fn ct_not_eq(&self, rhs: &Self) -> Word {
+ let mut acc = 0;
+ let mut i = 0;
+
+ while i < LIMBS {
+ acc |= self.limbs[i].0 ^ rhs.limbs[i].0;
+ i += 1;
+ }
+ let acc = acc as SignedWord;
+ ((acc | acc.wrapping_neg()) >> HI_BIT) as Word
+ }
+}
+
+impl<const LIMBS: usize> ConstantTimeEq for UInt<LIMBS> {
+ #[inline]
+ fn ct_eq(&self, other: &Self) -> Choice {
+ Choice::from((!self.ct_not_eq(other) as u8) & 1)
+ }
+}
+
+impl<const LIMBS: usize> ConstantTimeGreater for UInt<LIMBS> {
+ #[inline]
+ fn ct_gt(&self, other: &Self) -> Choice {
+ let underflow = other.sbb(self, Limb::ZERO).1;
+ !underflow.is_zero()
+ }
+}
+
+impl<const LIMBS: usize> ConstantTimeLess for UInt<LIMBS> {
+ #[inline]
+ fn ct_lt(&self, other: &Self) -> Choice {
+ let underflow = self.sbb(other, Limb::ZERO).1;
+ !underflow.is_zero()
+ }
+}
+
+impl<const LIMBS: usize> Eq for UInt<LIMBS> {}
+
+impl<const LIMBS: usize> Ord for UInt<LIMBS> {
+ fn cmp(&self, other: &Self) -> Ordering {
+ match self.ct_cmp(other) {
+ -1 => Ordering::Less,
+ 1 => Ordering::Greater,
+ n => {
+ debug_assert_eq!(n, 0);
+ debug_assert!(bool::from(self.ct_eq(other)));
+ Ordering::Equal
+ }
+ }
+ }
+}
+
+impl<const LIMBS: usize> PartialOrd for UInt<LIMBS> {
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+impl<const LIMBS: usize> PartialEq for UInt<LIMBS> {
+ fn eq(&self, other: &Self) -> bool {
+ self.ct_eq(other).into()
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{Integer, Zero, U128};
+ use subtle::{ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
+
+ #[test]
+ fn is_zero() {
+ assert!(bool::from(U128::ZERO.is_zero()));
+ assert!(!bool::from(U128::ONE.is_zero()));
+ assert!(!bool::from(U128::MAX.is_zero()));
+ }
+
+ #[test]
+ fn is_odd() {
+ assert!(!bool::from(U128::ZERO.is_odd()));
+ assert!(bool::from(U128::ONE.is_odd()));
+ assert!(bool::from(U128::MAX.is_odd()));
+ }
+
+ #[test]
+ fn ct_eq() {
+ let a = U128::ZERO;
+ let b = U128::MAX;
+
+ assert!(bool::from(a.ct_eq(&a)));
+ assert!(!bool::from(a.ct_eq(&b)));
+ assert!(!bool::from(b.ct_eq(&a)));
+ assert!(bool::from(b.ct_eq(&b)));
+ }
+
+ #[test]
+ fn ct_gt() {
+ let a = U128::ZERO;
+ let b = U128::ONE;
+ let c = U128::MAX;
+
+ assert!(bool::from(b.ct_gt(&a)));
+ assert!(bool::from(c.ct_gt(&a)));
+ assert!(bool::from(c.ct_gt(&b)));
+
+ assert!(!bool::from(a.ct_gt(&a)));
+ assert!(!bool::from(b.ct_gt(&b)));
+ assert!(!bool::from(c.ct_gt(&c)));
+
+ assert!(!bool::from(a.ct_gt(&b)));
+ assert!(!bool::from(a.ct_gt(&c)));
+ assert!(!bool::from(b.ct_gt(&c)));
+ }
+
+ #[test]
+ fn ct_lt() {
+ let a = U128::ZERO;
+ let b = U128::ONE;
+ let c = U128::MAX;
+
+ assert!(bool::from(a.ct_lt(&b)));
+ assert!(bool::from(a.ct_lt(&c)));
+ assert!(bool::from(b.ct_lt(&c)));
+
+ assert!(!bool::from(a.ct_lt(&a)));
+ assert!(!bool::from(b.ct_lt(&b)));
+ assert!(!bool::from(c.ct_lt(&c)));
+
+ assert!(!bool::from(b.ct_lt(&a)));
+ assert!(!bool::from(c.ct_lt(&a)));
+ assert!(!bool::from(c.ct_lt(&b)));
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/concat.rs b/vendor/crypto-bigint/src/uint/concat.rs
new file mode 100644
index 000000000..e92960da7
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/concat.rs
@@ -0,0 +1,60 @@
+// TODO(tarcieri): use `const_evaluatable_checked` when stable to make generic around bits.
+macro_rules! impl_concat {
+ ($(($name:ident, $bits:expr)),+) => {
+ $(
+ impl $name {
+ /// Concatenate the two values, with `self` as most significant and `rhs`
+ /// as the least significant.
+ pub const fn concat(&self, rhs: &Self) -> UInt<{nlimbs!($bits) * 2}> {
+ let mut limbs = [Limb::ZERO; nlimbs!($bits) * 2];
+ let mut i = 0;
+ let mut j = 0;
+
+ while j < nlimbs!($bits) {
+ limbs[i] = rhs.limbs[j];
+ i += 1;
+ j += 1;
+ }
+
+ j = 0;
+ while j < nlimbs!($bits) {
+ limbs[i] = self.limbs[j];
+ i += 1;
+ j += 1;
+ }
+
+ UInt { limbs }
+ }
+ }
+
+ impl Concat for $name {
+ type Output = UInt<{nlimbs!($bits) * 2}>;
+
+ fn concat(&self, rhs: &Self) -> Self::Output {
+ self.concat(rhs)
+ }
+ }
+
+ impl From<($name, $name)> for UInt<{nlimbs!($bits) * 2}> {
+ fn from(nums: ($name, $name)) -> UInt<{nlimbs!($bits) * 2}> {
+ nums.0.concat(&nums.1)
+ }
+ }
+ )+
+ };
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{U128, U64};
+
+ #[test]
+ fn concat() {
+ let hi = U64::from_u64(0x0011223344556677);
+ let lo = U64::from_u64(0x8899aabbccddeeff);
+ assert_eq!(
+ hi.concat(&lo),
+ U128::from_be_hex("00112233445566778899aabbccddeeff")
+ );
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/div.rs b/vendor/crypto-bigint/src/uint/div.rs
new file mode 100644
index 000000000..f7d9d6bf3
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/div.rs
@@ -0,0 +1,496 @@
+//! [`UInt`] division operations.
+
+use super::UInt;
+use crate::limb::Word;
+use crate::{Integer, Limb, NonZero, Wrapping};
+use core::ops::{Div, DivAssign, Rem, RemAssign};
+use subtle::{Choice, CtOption};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `self` / `rhs`, returns the quotient (q), remainder (r)
+ /// and 1 for is_some or 0 for is_none. The results can be wrapped in [`CtOption`].
+ /// NOTE: Use only if you need to access const fn. Otherwise use `div_rem` because
+ /// the value for is_some needs to be checked before using `q` and `r`.
+ ///
+ /// This is variable only with respect to `rhs`.
+ ///
+ /// When used with a fixed `rhs`, this function is constant-time with respect
+ /// to `self`.
+ pub(crate) const fn ct_div_rem(&self, rhs: &Self) -> (Self, Self, u8) {
+ let mb = rhs.bits_vartime();
+ let mut bd = (LIMBS * Limb::BIT_SIZE) - mb;
+ let mut rem = *self;
+ let mut quo = Self::ZERO;
+ let mut c = rhs.shl_vartime(bd);
+
+ loop {
+ let (mut r, borrow) = rem.sbb(&c, Limb::ZERO);
+ rem = Self::ct_select(r, rem, borrow.0);
+ r = quo.bitor(&Self::ONE);
+ quo = Self::ct_select(r, quo, borrow.0);
+ if bd == 0 {
+ break;
+ }
+ bd -= 1;
+ c = c.shr_vartime(1);
+ quo = quo.shl_vartime(1);
+ }
+
+ let is_some = Limb(mb as Word).is_nonzero();
+ quo = Self::ct_select(Self::ZERO, quo, is_some);
+ (quo, rem, (is_some & 1) as u8)
+ }
+
+ /// Computes `self` % `rhs`, returns the remainder and
+ /// and 1 for is_some or 0 for is_none. The results can be wrapped in [`CtOption`].
+ /// NOTE: Use only if you need to access const fn. Otherwise use `reduce`
+ /// This is variable only with respect to `rhs`.
+ ///
+ /// When used with a fixed `rhs`, this function is constant-time with respect
+ /// to `self`.
+ pub(crate) const fn ct_reduce(&self, rhs: &Self) -> (Self, u8) {
+ let mb = rhs.bits_vartime();
+ let mut bd = (LIMBS * Limb::BIT_SIZE) - mb;
+ let mut rem = *self;
+ let mut c = rhs.shl_vartime(bd);
+
+ loop {
+ let (r, borrow) = rem.sbb(&c, Limb::ZERO);
+ rem = Self::ct_select(r, rem, borrow.0);
+ if bd == 0 {
+ break;
+ }
+ bd -= 1;
+ c = c.shr_vartime(1);
+ }
+
+ let is_some = Limb(mb as Word).is_nonzero();
+ (rem, (is_some & 1) as u8)
+ }
+
+ /// Computes `self` % 2^k. Faster than reduce since its a power of 2.
+ /// Limited to 2^16-1 since UInt doesn't support higher.
+ pub const fn reduce2k(&self, k: usize) -> Self {
+ let highest = (LIMBS - 1) as u32;
+ let index = k as u32 / (Limb::BIT_SIZE as u32);
+ let res = Limb::ct_cmp(Limb::from_u32(index), Limb::from_u32(highest)) - 1;
+ let le = Limb::is_nonzero(Limb(res as Word));
+ let word = Limb::ct_select(Limb::from_u32(highest), Limb::from_u32(index), le).0 as usize;
+
+ let base = k % Limb::BIT_SIZE;
+ let mask = (1 << base) - 1;
+ let mut out = *self;
+
+ let outmask = Limb(out.limbs[word].0 & mask);
+
+ out.limbs[word] = Limb::ct_select(out.limbs[word], outmask, le);
+
+ let mut i = word + 1;
+ while i < LIMBS {
+ out.limbs[i] = Limb::ZERO;
+ i += 1;
+ }
+
+ out
+ }
+
+ /// Computes self / rhs, returns the quotient, remainder
+ /// if rhs != 0
+ pub fn div_rem(&self, rhs: &Self) -> CtOption<(Self, Self)> {
+ let (q, r, c) = self.ct_div_rem(rhs);
+ CtOption::new((q, r), Choice::from(c))
+ }
+
+ /// Computes self % rhs, returns the remainder
+ /// if rhs != 0
+ pub fn reduce(&self, rhs: &Self) -> CtOption<Self> {
+ let (r, c) = self.ct_reduce(rhs);
+ CtOption::new(r, Choice::from(c))
+ }
+
+ /// Wrapped division is just normal division i.e. `self` / `rhs`
+ /// There’s no way wrapping could ever happen.
+ /// This function exists, so that all operations are accounted for in the wrapping operations.
+ pub const fn wrapping_div(&self, rhs: &Self) -> Self {
+ let (q, _, c) = self.ct_div_rem(rhs);
+ assert!(c == 1, "divide by zero");
+ q
+ }
+
+ /// Perform checked division, returning a [`CtOption`] which `is_some`
+ /// only if the rhs != 0
+ pub fn checked_div(&self, rhs: &Self) -> CtOption<Self> {
+ let (q, _, c) = self.ct_div_rem(rhs);
+ CtOption::new(q, Choice::from(c))
+ }
+
+ /// Wrapped (modular) remainder calculation is just `self` % `rhs`.
+ /// There’s no way wrapping could ever happen.
+ /// This function exists, so that all operations are accounted for in the wrapping operations.
+ pub const fn wrapping_rem(&self, rhs: &Self) -> Self {
+ let (r, c) = self.ct_reduce(rhs);
+ assert!(c == 1, "modulo zero");
+ r
+ }
+
+ /// Perform checked reduction, returning a [`CtOption`] which `is_some`
+ /// only if the rhs != 0
+ pub fn checked_rem(&self, rhs: &Self) -> CtOption<Self> {
+ let (r, c) = self.ct_reduce(rhs);
+ CtOption::new(r, Choice::from(c))
+ }
+}
+
+impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ type Output = UInt<LIMBS>;
+
+ fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+ *self / *rhs
+ }
+}
+
+impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ type Output = UInt<LIMBS>;
+
+ fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+ self / *rhs
+ }
+}
+
+impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ type Output = UInt<LIMBS>;
+
+ fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+ *self / rhs
+ }
+}
+
+impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ type Output = UInt<LIMBS>;
+
+ fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+ let (q, _, _) = self.ct_div_rem(&rhs);
+ q
+ }
+}
+
+impl<const LIMBS: usize> DivAssign<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ fn div_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
+ let (q, _, _) = self.ct_div_rem(rhs);
+ *self = q
+ }
+}
+
+impl<const LIMBS: usize> DivAssign<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ fn div_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
+ *self /= &rhs;
+ }
+}
+
+impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+ Wrapping(self.0.wrapping_div(rhs.as_ref()))
+ }
+}
+
+impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+ *self / rhs
+ }
+}
+
+impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+ *self / *rhs
+ }
+}
+
+impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+ self / *rhs
+ }
+}
+
+impl<const LIMBS: usize> DivAssign<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn div_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
+ *self = Wrapping(self.0.wrapping_div(rhs.as_ref()))
+ }
+}
+
+impl<const LIMBS: usize> DivAssign<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn div_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
+ *self /= &rhs;
+ }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ type Output = UInt<LIMBS>;
+
+ fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+ *self % *rhs
+ }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ type Output = UInt<LIMBS>;
+
+ fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+ self % *rhs
+ }
+}
+
+impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ type Output = UInt<LIMBS>;
+
+ fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+ *self % rhs
+ }
+}
+
+impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ type Output = UInt<LIMBS>;
+
+ fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+ let (r, _) = self.ct_reduce(&rhs);
+ r
+ }
+}
+
+impl<const LIMBS: usize> RemAssign<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ fn rem_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
+ let (r, _) = self.ct_reduce(rhs);
+ *self = r
+ }
+}
+
+impl<const LIMBS: usize> RemAssign<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: Integer,
+{
+ fn rem_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
+ *self %= &rhs;
+ }
+}
+
+impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+ Wrapping(self.0.wrapping_rem(rhs.as_ref()))
+ }
+}
+
+impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+ *self % rhs
+ }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+ *self % *rhs
+ }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+ self % *rhs
+ }
+}
+
+impl<const LIMBS: usize> RemAssign<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn rem_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
+ *self %= &rhs;
+ }
+}
+
+impl<const LIMBS: usize> RemAssign<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn rem_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
+ *self = Wrapping(self.0.wrapping_rem(rhs.as_ref()))
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use crate::{limb::HI_BIT, Limb, U256};
+
+ #[cfg(feature = "rand")]
+ use {
+ crate::{CheckedMul, Random},
+ rand_chacha::ChaChaRng,
+ rand_core::RngCore,
+ rand_core::SeedableRng,
+ };
+
+ #[test]
+ fn div_word() {
+ for (n, d, e, ee) in &[
+ (200u64, 2u64, 100u64, 0),
+ (100u64, 25u64, 4u64, 0),
+ (100u64, 10u64, 10u64, 0),
+ (1024u64, 8u64, 128u64, 0),
+ (27u64, 13u64, 2u64, 1u64),
+ (26u64, 13u64, 2u64, 0u64),
+ (14u64, 13u64, 1u64, 1u64),
+ (13u64, 13u64, 1u64, 0u64),
+ (12u64, 13u64, 0u64, 12u64),
+ (1u64, 13u64, 0u64, 1u64),
+ ] {
+ let lhs = U256::from(*n);
+ let rhs = U256::from(*d);
+ let (q, r, is_some) = lhs.ct_div_rem(&rhs);
+ assert_eq!(is_some, 1);
+ assert_eq!(U256::from(*e), q);
+ assert_eq!(U256::from(*ee), r);
+ }
+ }
+
+ #[cfg(feature = "rand")]
+ #[test]
+ fn div() {
+ let mut rng = ChaChaRng::from_seed([7u8; 32]);
+ for _ in 0..25 {
+ let num = U256::random(&mut rng).shr_vartime(128);
+ let den = U256::random(&mut rng).shr_vartime(128);
+ let n = num.checked_mul(&den);
+ if n.is_some().unwrap_u8() == 1 {
+ let (q, _, is_some) = n.unwrap().ct_div_rem(&den);
+ assert_eq!(is_some, 1);
+ assert_eq!(q, num);
+ }
+ }
+ }
+
+ #[test]
+ fn div_max() {
+ let mut a = U256::ZERO;
+ let mut b = U256::ZERO;
+ b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
+ let q = a.wrapping_div(&b);
+ assert_eq!(q, UInt::ZERO);
+ a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
+ b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
+ let q = a.wrapping_div(&b);
+ assert_eq!(q, UInt::ZERO);
+ }
+
+ #[test]
+ fn div_zero() {
+ let (q, r, is_some) = U256::ONE.ct_div_rem(&U256::ZERO);
+ assert_eq!(is_some, 0);
+ assert_eq!(q, U256::ZERO);
+ assert_eq!(r, U256::ONE);
+ }
+
+ #[test]
+ fn div_one() {
+ let (q, r, is_some) = U256::from(10u8).ct_div_rem(&U256::ONE);
+ assert_eq!(is_some, 1);
+ assert_eq!(q, U256::from(10u8));
+ assert_eq!(r, U256::ZERO);
+ }
+
+ #[test]
+ fn reduce_one() {
+ let (r, is_some) = U256::from(10u8).ct_reduce(&U256::ONE);
+ assert_eq!(is_some, 1);
+ assert_eq!(r, U256::ZERO);
+ }
+
+ #[test]
+ fn reduce_zero() {
+ let u = U256::from(10u8);
+ let (r, is_some) = u.ct_reduce(&U256::ZERO);
+ assert_eq!(is_some, 0);
+ assert_eq!(r, u);
+ }
+
+ #[test]
+ fn reduce_tests() {
+ let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(2u8));
+ assert_eq!(is_some, 1);
+ assert_eq!(r, U256::ZERO);
+ let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(3u8));
+ assert_eq!(is_some, 1);
+ assert_eq!(r, U256::ONE);
+ let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(7u8));
+ assert_eq!(is_some, 1);
+ assert_eq!(r, U256::from(3u8));
+ }
+
+ #[test]
+ fn reduce_max() {
+ let mut a = U256::ZERO;
+ let mut b = U256::ZERO;
+ b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
+ let r = a.wrapping_rem(&b);
+ assert_eq!(r, UInt::ZERO);
+ a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
+ b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
+ let r = a.wrapping_rem(&b);
+ assert_eq!(r, a);
+ }
+
+ #[cfg(feature = "rand")]
+ #[test]
+ fn reduce2krand() {
+ let mut rng = ChaChaRng::from_seed([7u8; 32]);
+ for _ in 0..25 {
+ let num = U256::random(&mut rng);
+ let k = (rng.next_u32() % 256) as usize;
+ let den = U256::ONE.shl_vartime(k);
+
+ let a = num.reduce2k(k);
+ let e = num.wrapping_rem(&den);
+ assert_eq!(a, e);
+ }
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/encoding.rs b/vendor/crypto-bigint/src/uint/encoding.rs
new file mode 100644
index 000000000..a83976238
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/encoding.rs
@@ -0,0 +1,278 @@
+//! Const-friendly decoding operations for [`UInt`]
+
+#[cfg(all(feature = "der", feature = "generic-array"))]
+mod der;
+
+#[cfg(feature = "rlp")]
+mod rlp;
+
+use super::UInt;
+use crate::{Encoding, Limb, Word};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Create a new [`UInt`] from the provided big endian bytes.
+ pub const fn from_be_slice(bytes: &[u8]) -> Self {
+ assert!(
+ bytes.len() == Limb::BYTE_SIZE * LIMBS,
+ "bytes are not the expected size"
+ );
+
+ let mut res = [Limb::ZERO; LIMBS];
+ let mut buf = [0u8; Limb::BYTE_SIZE];
+ let mut i = 0;
+
+ while i < LIMBS {
+ let mut j = 0;
+ while j < Limb::BYTE_SIZE {
+ buf[j] = bytes[i * Limb::BYTE_SIZE + j];
+ j += 1;
+ }
+ res[LIMBS - i - 1] = Limb(Word::from_be_bytes(buf));
+ i += 1;
+ }
+
+ UInt::new(res)
+ }
+
+ /// Create a new [`UInt`] from the provided big endian hex string.
+ pub const fn from_be_hex(hex: &str) -> Self {
+ let bytes = hex.as_bytes();
+
+ assert!(
+ bytes.len() == Limb::BYTE_SIZE * LIMBS * 2,
+ "hex string is not the expected size"
+ );
+
+ let mut res = [Limb::ZERO; LIMBS];
+ let mut buf = [0u8; Limb::BYTE_SIZE];
+ let mut i = 0;
+
+ while i < LIMBS {
+ let mut j = 0;
+ while j < Limb::BYTE_SIZE {
+ let offset = (i * Limb::BYTE_SIZE + j) * 2;
+ buf[j] = decode_hex_byte([bytes[offset], bytes[offset + 1]]);
+ j += 1;
+ }
+ res[LIMBS - i - 1] = Limb(Word::from_be_bytes(buf));
+ i += 1;
+ }
+
+ UInt::new(res)
+ }
+
+ /// Create a new [`UInt`] from the provided little endian bytes.
+ pub const fn from_le_slice(bytes: &[u8]) -> Self {
+ assert!(
+ bytes.len() == Limb::BYTE_SIZE * LIMBS,
+ "bytes are not the expected size"
+ );
+
+ let mut res = [Limb::ZERO; LIMBS];
+ let mut buf = [0u8; Limb::BYTE_SIZE];
+ let mut i = 0;
+
+ while i < LIMBS {
+ let mut j = 0;
+ while j < Limb::BYTE_SIZE {
+ buf[j] = bytes[i * Limb::BYTE_SIZE + j];
+ j += 1;
+ }
+ res[i] = Limb(Word::from_le_bytes(buf));
+ i += 1;
+ }
+
+ UInt::new(res)
+ }
+
+ /// Create a new [`UInt`] from the provided little endian hex string.
+ pub const fn from_le_hex(hex: &str) -> Self {
+ let bytes = hex.as_bytes();
+
+ assert!(
+ bytes.len() == Limb::BYTE_SIZE * LIMBS * 2,
+ "bytes are not the expected size"
+ );
+
+ let mut res = [Limb::ZERO; LIMBS];
+ let mut buf = [0u8; Limb::BYTE_SIZE];
+ let mut i = 0;
+
+ while i < LIMBS {
+ let mut j = 0;
+ while j < Limb::BYTE_SIZE {
+ let offset = (i * Limb::BYTE_SIZE + j) * 2;
+ buf[j] = decode_hex_byte([bytes[offset], bytes[offset + 1]]);
+ j += 1;
+ }
+ res[i] = Limb(Word::from_le_bytes(buf));
+ i += 1;
+ }
+
+ UInt::new(res)
+ }
+
+ /// Serialize this [`UInt`] as big-endian, writing it into the provided
+ /// byte slice.
+ #[inline]
+ #[cfg_attr(docsrs, doc(cfg(feature = "generic-array")))]
+ pub(crate) fn write_be_bytes(&self, out: &mut [u8]) {
+ debug_assert_eq!(out.len(), Limb::BYTE_SIZE * LIMBS);
+
+ for (src, dst) in self
+ .limbs
+ .iter()
+ .rev()
+ .cloned()
+ .zip(out.chunks_exact_mut(Limb::BYTE_SIZE))
+ {
+ dst.copy_from_slice(&src.to_be_bytes());
+ }
+ }
+
+ /// Serialize this [`UInt`] as little-endian, writing it into the provided
+ /// byte slice.
+ #[inline]
+ #[cfg_attr(docsrs, doc(cfg(feature = "generic-array")))]
+ pub(crate) fn write_le_bytes(&self, out: &mut [u8]) {
+ debug_assert_eq!(out.len(), Limb::BYTE_SIZE * LIMBS);
+
+ for (src, dst) in self
+ .limbs
+ .iter()
+ .cloned()
+ .zip(out.chunks_exact_mut(Limb::BYTE_SIZE))
+ {
+ dst.copy_from_slice(&src.to_le_bytes());
+ }
+ }
+}
+
+/// Decode a single byte encoded as two hexadecimal characters.
+const fn decode_hex_byte(bytes: [u8; 2]) -> u8 {
+ let mut i = 0;
+ let mut result = 0u8;
+
+ while i < 2 {
+ result <<= 4;
+ result |= match bytes[i] {
+ b @ b'0'..=b'9' => b - b'0',
+ b @ b'a'..=b'f' => 10 + b - b'a',
+ b @ b'A'..=b'F' => 10 + b - b'A',
+ b => {
+ assert!(
+ matches!(b, b'0'..=b'9' | b'a' ..= b'f' | b'A'..=b'F'),
+ "invalid hex byte"
+ );
+ 0
+ }
+ };
+
+ i += 1;
+ }
+
+ result
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::Limb;
+ use hex_literal::hex;
+
+ #[cfg(feature = "alloc")]
+ use {crate::U128, alloc::format};
+
+ #[cfg(target_pointer_width = "32")]
+ use crate::U64 as UIntEx;
+
+ #[cfg(target_pointer_width = "64")]
+ use crate::U128 as UIntEx;
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn from_be_slice() {
+ let bytes = hex!("0011223344556677");
+ let n = UIntEx::from_be_slice(&bytes);
+ assert_eq!(n.limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn from_be_slice() {
+ let bytes = hex!("00112233445566778899aabbccddeeff");
+ let n = UIntEx::from_be_slice(&bytes);
+ assert_eq!(
+ n.limbs(),
+ &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
+ );
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn from_le_slice() {
+ let bytes = hex!("7766554433221100");
+ let n = UIntEx::from_le_slice(&bytes);
+ assert_eq!(n.limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn from_le_slice() {
+ let bytes = hex!("ffeeddccbbaa99887766554433221100");
+ let n = UIntEx::from_le_slice(&bytes);
+ assert_eq!(
+ n.limbs(),
+ &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
+ );
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn from_be_hex() {
+ let n = UIntEx::from_be_hex("0011223344556677");
+ assert_eq!(n.limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn from_be_hex() {
+ let n = UIntEx::from_be_hex("00112233445566778899aabbccddeeff");
+ assert_eq!(
+ n.limbs(),
+ &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
+ );
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "32")]
+ fn from_le_hex() {
+ let n = UIntEx::from_le_hex("7766554433221100");
+ assert_eq!(n.limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
+ }
+
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn from_le_hex() {
+ let n = UIntEx::from_le_hex("ffeeddccbbaa99887766554433221100");
+ assert_eq!(
+ n.limbs(),
+ &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
+ );
+ }
+
+ #[cfg(feature = "alloc")]
+ #[test]
+ fn hex_upper() {
+ let hex = "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD";
+ let n = U128::from_be_hex(hex);
+ assert_eq!(hex, format!("{:X}", n));
+ }
+
+ #[cfg(feature = "alloc")]
+ #[test]
+ fn hex_lower() {
+ let hex = "aaaaaaaabbbbbbbbccccccccdddddddd";
+ let n = U128::from_be_hex(hex);
+ assert_eq!(hex, format!("{:x}", n));
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/encoding/der.rs b/vendor/crypto-bigint/src/uint/encoding/der.rs
new file mode 100644
index 000000000..cf1b9c31e
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/encoding/der.rs
@@ -0,0 +1,69 @@
+//! Support for decoding/encoding [`UInt`] as an ASN.1 DER `INTEGER`.
+
+use crate::{generic_array::GenericArray, ArrayEncoding, UInt};
+use ::der::{
+ asn1::{AnyRef, UIntRef},
+ DecodeValue, EncodeValue, FixedTag, Length, Tag,
+};
+
+#[cfg_attr(docsrs, doc(cfg(feature = "der")))]
+impl<'a, const LIMBS: usize> TryFrom<AnyRef<'a>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: ArrayEncoding,
+{
+ type Error = der::Error;
+
+ fn try_from(any: AnyRef<'a>) -> der::Result<UInt<LIMBS>> {
+ UIntRef::try_from(any)?.try_into()
+ }
+}
+
+#[cfg_attr(docsrs, doc(cfg(feature = "der")))]
+impl<'a, const LIMBS: usize> TryFrom<UIntRef<'a>> for UInt<LIMBS>
+where
+ UInt<LIMBS>: ArrayEncoding,
+{
+ type Error = der::Error;
+
+ fn try_from(bytes: UIntRef<'a>) -> der::Result<UInt<LIMBS>> {
+ let mut array = GenericArray::default();
+ let offset = array.len().saturating_sub(bytes.len().try_into()?);
+ array[offset..].copy_from_slice(bytes.as_bytes());
+ Ok(UInt::from_be_byte_array(array))
+ }
+}
+
+#[cfg_attr(docsrs, doc(cfg(feature = "der")))]
+impl<'a, const LIMBS: usize> DecodeValue<'a> for UInt<LIMBS>
+where
+ UInt<LIMBS>: ArrayEncoding,
+{
+ fn decode_value<R: der::Reader<'a>>(reader: &mut R, header: der::Header) -> der::Result<Self> {
+ UIntRef::decode_value(reader, header)?.try_into()
+ }
+}
+
+#[cfg_attr(docsrs, doc(cfg(feature = "der")))]
+impl<const LIMBS: usize> EncodeValue for UInt<LIMBS>
+where
+ UInt<LIMBS>: ArrayEncoding,
+{
+ fn value_len(&self) -> der::Result<Length> {
+ // TODO(tarcieri): more efficient length calculation
+ let array = self.to_be_byte_array();
+ UIntRef::new(&array)?.value_len()
+ }
+
+ fn encode_value(&self, encoder: &mut dyn der::Writer) -> der::Result<()> {
+ let array = self.to_be_byte_array();
+ UIntRef::new(&array)?.encode_value(encoder)
+ }
+}
+
+#[cfg_attr(docsrs, doc(cfg(feature = "der")))]
+impl<const LIMBS: usize> FixedTag for UInt<LIMBS>
+where
+ UInt<LIMBS>: ArrayEncoding,
+{
+ const TAG: Tag = Tag::Integer;
+}
diff --git a/vendor/crypto-bigint/src/uint/encoding/rlp.rs b/vendor/crypto-bigint/src/uint/encoding/rlp.rs
new file mode 100644
index 000000000..8a10170d5
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/encoding/rlp.rs
@@ -0,0 +1,79 @@
+//! Recursive Length Prefix (RLP) encoding support.
+
+use crate::{Encoding, UInt};
+use rlp::{DecoderError, Rlp, RlpStream};
+
+#[cfg_attr(docsrs, doc(cfg(feature = "rlp")))]
+impl<const LIMBS: usize> rlp::Encodable for UInt<LIMBS>
+where
+ Self: Encoding,
+{
+ fn rlp_append(&self, stream: &mut RlpStream) {
+ let bytes = self.to_be_bytes();
+ let mut bytes_stripped = bytes.as_ref();
+
+ while bytes_stripped.first().cloned() == Some(0) {
+ bytes_stripped = &bytes_stripped[1..];
+ }
+
+ stream.encoder().encode_value(bytes_stripped);
+ }
+}
+
+#[cfg_attr(docsrs, doc(cfg(feature = "rlp")))]
+impl<const LIMBS: usize> rlp::Decodable for UInt<LIMBS>
+where
+ Self: Encoding,
+ <Self as Encoding>::Repr: Default,
+{
+ fn decode(rlp: &Rlp<'_>) -> Result<Self, DecoderError> {
+ rlp.decoder().decode_value(|bytes| {
+ if bytes.first().cloned() == Some(0) {
+ Err(rlp::DecoderError::RlpInvalidIndirection)
+ } else {
+ let mut repr = <Self as Encoding>::Repr::default();
+ let offset = repr
+ .as_ref()
+ .len()
+ .checked_sub(bytes.len())
+ .ok_or(DecoderError::RlpIsTooBig)?;
+
+ repr.as_mut()[offset..].copy_from_slice(bytes);
+ Ok(Self::from_be_bytes(repr))
+ }
+ })
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U256;
+ use hex_literal::hex;
+
+ /// U256 test vectors from the `rlp` crate.
+ ///
+ /// <https://github.com/paritytech/parity-common/blob/faad8b6/rlp/tests/tests.rs#L216-L222>
+ const U256_VECTORS: &[(U256, &[u8])] = &[
+ (U256::ZERO, &hex!("80")),
+ (
+ U256::from_be_hex("0000000000000000000000000000000000000000000000000000000001000000"),
+ &hex!("8401000000"),
+ ),
+ (
+ U256::from_be_hex("00000000000000000000000000000000000000000000000000000000ffffffff"),
+ &hex!("84ffffffff"),
+ ),
+ (
+ U256::from_be_hex("8090a0b0c0d0e0f00910203040506077000000000000000100000000000012f0"),
+ &hex!("a08090a0b0c0d0e0f00910203040506077000000000000000100000000000012f0"),
+ ),
+ ];
+
+ #[test]
+ fn round_trip() {
+ for &(uint, expected_bytes) in U256_VECTORS {
+ assert_eq!(rlp::encode(&uint), expected_bytes);
+ assert_eq!(rlp::decode::<U256>(expected_bytes).unwrap(), uint);
+ }
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/from.rs b/vendor/crypto-bigint/src/uint/from.rs
new file mode 100644
index 000000000..daa5b7092
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/from.rs
@@ -0,0 +1,238 @@
+//! `From`-like conversions for [`UInt`].
+
+use crate::{Limb, UInt, WideWord, Word, U128, U64};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Create a [`UInt`] from a `u8` (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u8>` when stable
+ pub const fn from_u8(n: u8) -> Self {
+ assert!(LIMBS >= 1, "number of limbs must be greater than zero");
+ let mut limbs = [Limb::ZERO; LIMBS];
+ limbs[0].0 = n as Word;
+ Self { limbs }
+ }
+
+ /// Create a [`UInt`] from a `u16` (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u16>` when stable
+ pub const fn from_u16(n: u16) -> Self {
+ assert!(LIMBS >= 1, "number of limbs must be greater than zero");
+ let mut limbs = [Limb::ZERO; LIMBS];
+ limbs[0].0 = n as Word;
+ Self { limbs }
+ }
+
+ /// Create a [`UInt`] from a `u32` (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u32>` when stable
+ #[allow(trivial_numeric_casts)]
+ pub const fn from_u32(n: u32) -> Self {
+ assert!(LIMBS >= 1, "number of limbs must be greater than zero");
+ let mut limbs = [Limb::ZERO; LIMBS];
+ limbs[0].0 = n as Word;
+ Self { limbs }
+ }
+
+ /// Create a [`UInt`] from a `u64` (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u64>` when stable
+ #[cfg(target_pointer_width = "32")]
+ pub const fn from_u64(n: u64) -> Self {
+ assert!(LIMBS >= 2, "number of limbs must be two or greater");
+ let mut limbs = [Limb::ZERO; LIMBS];
+ limbs[0].0 = (n & 0xFFFFFFFF) as u32;
+ limbs[1].0 = (n >> 32) as u32;
+ Self { limbs }
+ }
+
+ /// Create a [`UInt`] from a `u64` (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u64>` when stable
+ #[cfg(target_pointer_width = "64")]
+ pub const fn from_u64(n: u64) -> Self {
+ assert!(LIMBS >= 1, "number of limbs must be greater than zero");
+ let mut limbs = [Limb::ZERO; LIMBS];
+ limbs[0].0 = n;
+ Self { limbs }
+ }
+
+ /// Create a [`UInt`] from a `u128` (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<u128>` when stable
+ pub const fn from_u128(n: u128) -> Self {
+ assert!(
+ LIMBS >= (128 / Limb::BIT_SIZE),
+ "number of limbs must be greater than zero"
+ );
+
+ let lo = U64::from_u64((n & 0xffff_ffff_ffff_ffff) as u64);
+ let hi = U64::from_u64((n >> 64) as u64);
+
+ let mut limbs = [Limb::ZERO; LIMBS];
+
+ let mut i = 0;
+ while i < lo.limbs.len() {
+ limbs[i] = lo.limbs[i];
+ i += 1;
+ }
+
+ let mut j = 0;
+ while j < hi.limbs.len() {
+ limbs[i + j] = hi.limbs[j];
+ j += 1;
+ }
+
+ Self { limbs }
+ }
+
+ /// Create a [`UInt`] from a `Word` (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<Word>` when stable
+ pub const fn from_word(n: Word) -> Self {
+ assert!(LIMBS >= 1, "number of limbs must be greater than zero");
+ let mut limbs = [Limb::ZERO; LIMBS];
+ limbs[0].0 = n;
+ Self { limbs }
+ }
+
+ /// Create a [`UInt`] from a `WideWord` (const-friendly)
+ // TODO(tarcieri): replace with `const impl From<WideWord>` when stable
+ pub const fn from_wide_word(n: WideWord) -> Self {
+ assert!(LIMBS >= 2, "number of limbs must be two or greater");
+ let mut limbs = [Limb::ZERO; LIMBS];
+ limbs[0].0 = n as Word;
+ limbs[1].0 = (n >> Limb::BIT_SIZE) as Word;
+ Self { limbs }
+ }
+}
+
+impl<const LIMBS: usize> From<u8> for UInt<LIMBS> {
+ fn from(n: u8) -> Self {
+ // TODO(tarcieri): const where clause when possible
+ debug_assert!(LIMBS > 0, "limbs must be non-zero");
+ Self::from_u8(n)
+ }
+}
+
+impl<const LIMBS: usize> From<u16> for UInt<LIMBS> {
+ fn from(n: u16) -> Self {
+ // TODO(tarcieri): const where clause when possible
+ debug_assert!(LIMBS > 0, "limbs must be non-zero");
+ Self::from_u16(n)
+ }
+}
+
+impl<const LIMBS: usize> From<u32> for UInt<LIMBS> {
+ fn from(n: u32) -> Self {
+ // TODO(tarcieri): const where clause when possible
+ debug_assert!(LIMBS > 0, "limbs must be non-zero");
+ Self::from_u32(n)
+ }
+}
+
+impl<const LIMBS: usize> From<u64> for UInt<LIMBS> {
+ fn from(n: u64) -> Self {
+ // TODO(tarcieri): const where clause when possible
+ debug_assert!(LIMBS >= (64 / Limb::BIT_SIZE), "not enough limbs");
+ Self::from_u64(n)
+ }
+}
+
+impl<const LIMBS: usize> From<u128> for UInt<LIMBS> {
+ fn from(n: u128) -> Self {
+ // TODO(tarcieri): const where clause when possible
+ debug_assert!(LIMBS >= (128 / Limb::BIT_SIZE), "not enough limbs");
+ Self::from_u128(n)
+ }
+}
+
+#[cfg(target_pointer_width = "32")]
+#[cfg_attr(docsrs, doc(cfg(target_pointer_width = "32")))]
+impl From<U64> for u64 {
+ fn from(n: U64) -> u64 {
+ (n.limbs[0].0 as u64) | ((n.limbs[1].0 as u64) << 32)
+ }
+}
+
+#[cfg(target_pointer_width = "64")]
+#[cfg_attr(docsrs, doc(cfg(target_pointer_width = "64")))]
+impl From<U64> for u64 {
+ fn from(n: U64) -> u64 {
+ n.limbs[0].into()
+ }
+}
+
+impl From<U128> for u128 {
+ fn from(n: U128) -> u128 {
+ let (hi, lo) = n.split();
+ (u64::from(hi) as u128) << 64 | (u64::from(lo) as u128)
+ }
+}
+
+impl<const LIMBS: usize> From<[Word; LIMBS]> for UInt<LIMBS> {
+ fn from(arr: [Word; LIMBS]) -> Self {
+ Self::from_words(arr)
+ }
+}
+
+impl<const LIMBS: usize> From<UInt<LIMBS>> for [Word; LIMBS] {
+ fn from(n: UInt<LIMBS>) -> [Word; LIMBS] {
+ *n.as_ref()
+ }
+}
+
+impl<const LIMBS: usize> From<[Limb; LIMBS]> for UInt<LIMBS> {
+ fn from(limbs: [Limb; LIMBS]) -> Self {
+ Self { limbs }
+ }
+}
+
+impl<const LIMBS: usize> From<UInt<LIMBS>> for [Limb; LIMBS] {
+ fn from(n: UInt<LIMBS>) -> [Limb; LIMBS] {
+ n.limbs
+ }
+}
+
+impl<const LIMBS: usize> From<Limb> for UInt<LIMBS> {
+ fn from(limb: Limb) -> Self {
+ limb.0.into()
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{Limb, Word, U128};
+
+ #[cfg(target_pointer_width = "32")]
+ use crate::U64 as UIntEx;
+
+ #[cfg(target_pointer_width = "64")]
+ use crate::U128 as UIntEx;
+
+ #[test]
+ fn from_u8() {
+ let n = UIntEx::from(42u8);
+ assert_eq!(n.limbs(), &[Limb(42), Limb(0)]);
+ }
+
+ #[test]
+ fn from_u16() {
+ let n = UIntEx::from(42u16);
+ assert_eq!(n.limbs(), &[Limb(42), Limb(0)]);
+ }
+
+ #[test]
+ fn from_u64() {
+ let n = UIntEx::from(42u64);
+ assert_eq!(n.limbs(), &[Limb(42), Limb(0)]);
+ }
+
+ #[test]
+ fn from_u128() {
+ let n = U128::from(42u128);
+ assert_eq!(&n.limbs()[..2], &[Limb(42), Limb(0)]);
+ assert_eq!(u128::from(n), 42u128);
+ }
+
+ #[test]
+ fn array_round_trip() {
+ let arr1 = [1, 2];
+ let n = UIntEx::from(arr1);
+ let arr2: [Word; 2] = n.into();
+ assert_eq!(arr1, arr2);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/inv_mod.rs b/vendor/crypto-bigint/src/uint/inv_mod.rs
new file mode 100644
index 000000000..a11408564
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/inv_mod.rs
@@ -0,0 +1,62 @@
+use super::UInt;
+use crate::Limb;
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes 1/`self` mod 2^k as specified in Algorithm 4 from
+ /// A Secure Algorithm for Inversion Modulo 2k by
+ /// Sadiel de la Fe and Carles Ferrer. See
+ /// <https://www.mdpi.com/2410-387X/2/3/23>.
+ ///
+ /// Conditions: `self` < 2^k and `self` must be odd
+ pub const fn inv_mod2k(&self, k: usize) -> Self {
+ let mut x = Self::ZERO;
+ let mut b = Self::ONE;
+ let mut i = 0;
+
+ while i < k {
+ let mut x_i = Self::ZERO;
+ let j = b.limbs[0].0 & 1;
+ x_i.limbs[0] = Limb(j);
+ x = x.bitor(&x_i.shl_vartime(i));
+
+ let t = b.wrapping_sub(self);
+ b = Self::ct_select(b, t, j.wrapping_neg()).shr_vartime(1);
+ i += 1;
+ }
+ x
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U256;
+
+ #[test]
+ fn inv_mod2k() {
+ let v = U256::from_be_slice(&[
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
+ 0xff, 0xff, 0xfc, 0x2f,
+ ]);
+ let e = U256::from_be_slice(&[
+ 0x36, 0x42, 0xe6, 0xfa, 0xea, 0xac, 0x7c, 0x66, 0x63, 0xb9, 0x3d, 0x3d, 0x6a, 0x0d,
+ 0x48, 0x9e, 0x43, 0x4d, 0xdc, 0x01, 0x23, 0xdb, 0x5f, 0xa6, 0x27, 0xc7, 0xf6, 0xe2,
+ 0x2d, 0xda, 0xca, 0xcf,
+ ]);
+ let a = v.inv_mod2k(256);
+ assert_eq!(e, a);
+
+ let v = U256::from_be_slice(&[
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, 0xbf, 0xd2, 0x5e, 0x8c,
+ 0xd0, 0x36, 0x41, 0x41,
+ ]);
+ let e = U256::from_be_slice(&[
+ 0x26, 0x17, 0x76, 0xf2, 0x9b, 0x6b, 0x10, 0x6c, 0x76, 0x80, 0xcf, 0x3e, 0xd8, 0x30,
+ 0x54, 0xa1, 0xaf, 0x5a, 0xe5, 0x37, 0xcb, 0x46, 0x13, 0xdb, 0xb4, 0xf2, 0x00, 0x99,
+ 0xaa, 0x77, 0x4e, 0xc1,
+ ]);
+ let a = v.inv_mod2k(256);
+ assert_eq!(e, a);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/mul.rs b/vendor/crypto-bigint/src/uint/mul.rs
new file mode 100644
index 000000000..ecb32fd10
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/mul.rs
@@ -0,0 +1,246 @@
+//! [`UInt`] addition operations.
+
+use crate::{Checked, CheckedMul, Concat, Limb, UInt, Wrapping, Zero};
+use core::ops::{Mul, MulAssign};
+use subtle::CtOption;
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Compute "wide" multiplication, with a product twice the size of the input.
+ ///
+ /// Returns a tuple containing the `(lo, hi)` components of the product.
+ ///
+ /// # Ordering note
+ ///
+ /// Releases of `crypto-bigint` prior to v0.3 used `(hi, lo)` ordering
+ /// instead. This has been changed for better consistency with the rest of
+ /// the APIs in this crate.
+ ///
+ /// For more info see: <https://github.com/RustCrypto/crypto-bigint/issues/4>
+ // TODO(tarcieri): use `concat` to construct a wide output
+ pub const fn mul_wide(&self, rhs: &Self) -> (Self, Self) {
+ let mut i = 0;
+ let mut lo = Self::ZERO;
+ let mut hi = Self::ZERO;
+
+ // Schoolbook multiplication.
+ // TODO(tarcieri): use Karatsuba for better performance?
+ while i < LIMBS {
+ let mut j = 0;
+ let mut carry = Limb::ZERO;
+
+ while j < LIMBS {
+ let k = i + j;
+
+ if k >= LIMBS {
+ let (n, c) = hi.limbs[k - LIMBS].mac(self.limbs[i], rhs.limbs[j], carry);
+ hi.limbs[k - LIMBS] = n;
+ carry = c;
+ } else {
+ let (n, c) = lo.limbs[k].mac(self.limbs[i], rhs.limbs[j], carry);
+ lo.limbs[k] = n;
+ carry = c;
+ }
+
+ j += 1;
+ }
+
+ hi.limbs[i + j - LIMBS] = carry;
+ i += 1;
+ }
+
+ (lo, hi)
+ }
+
+ /// Perform saturating multiplication, returning `MAX` on overflow.
+ pub const fn saturating_mul(&self, rhs: &Self) -> Self {
+ let (res, overflow) = self.mul_wide(rhs);
+
+ let mut i = 0;
+ let mut accumulator = 0;
+
+ while i < LIMBS {
+ accumulator |= overflow.limbs[i].0;
+ i += 1;
+ }
+
+ if accumulator == 0 {
+ res
+ } else {
+ Self::MAX
+ }
+ }
+
+ /// Perform wrapping multiplication, discarding overflow.
+ pub const fn wrapping_mul(&self, rhs: &Self) -> Self {
+ self.mul_wide(rhs).0
+ }
+
+ /// Square self, returning a "wide" result.
+ pub fn square(&self) -> <Self as Concat>::Output
+ where
+ Self: Concat,
+ {
+ let (lo, hi) = self.mul_wide(self);
+ hi.concat(&lo)
+ }
+}
+
+impl<const LIMBS: usize> CheckedMul<&UInt<LIMBS>> for UInt<LIMBS> {
+ type Output = Self;
+
+ fn checked_mul(&self, rhs: &Self) -> CtOption<Self> {
+ let (lo, hi) = self.mul_wide(rhs);
+ CtOption::new(lo, hi.is_zero())
+ }
+}
+
+impl<const LIMBS: usize> Mul for Wrapping<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn mul(self, rhs: Self) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_mul(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Mul<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn mul(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_mul(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Mul<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn mul(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_mul(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Mul<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn mul(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_mul(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> MulAssign for Wrapping<UInt<LIMBS>> {
+ fn mul_assign(&mut self, other: Self) {
+ *self = *self * other;
+ }
+}
+
+impl<const LIMBS: usize> MulAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn mul_assign(&mut self, other: &Self) {
+ *self = *self * other;
+ }
+}
+
+impl<const LIMBS: usize> Mul for Checked<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn mul(self, rhs: Self) -> Checked<UInt<LIMBS>> {
+ Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
+ }
+}
+
+impl<const LIMBS: usize> Mul<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn mul(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
+ }
+}
+
+impl<const LIMBS: usize> Mul<Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn mul(self, rhs: Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
+ }
+}
+
+impl<const LIMBS: usize> Mul<&Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn mul(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
+ }
+}
+
+impl<const LIMBS: usize> MulAssign for Checked<UInt<LIMBS>> {
+ fn mul_assign(&mut self, other: Self) {
+ *self = *self * other;
+ }
+}
+
+impl<const LIMBS: usize> MulAssign<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
+ fn mul_assign(&mut self, other: &Self) {
+ *self = *self * other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{CheckedMul, Zero, U64};
+
+ #[test]
+ fn mul_wide_zero_and_one() {
+ assert_eq!(U64::ZERO.mul_wide(&U64::ZERO), (U64::ZERO, U64::ZERO));
+ assert_eq!(U64::ZERO.mul_wide(&U64::ONE), (U64::ZERO, U64::ZERO));
+ assert_eq!(U64::ONE.mul_wide(&U64::ZERO), (U64::ZERO, U64::ZERO));
+ assert_eq!(U64::ONE.mul_wide(&U64::ONE), (U64::ONE, U64::ZERO));
+ }
+
+ #[test]
+ fn mul_wide_lo_only() {
+ let primes: &[u32] = &[3, 5, 17, 256, 65537];
+
+ for &a_int in primes {
+ for &b_int in primes {
+ let (lo, hi) = U64::from_u32(a_int).mul_wide(&U64::from_u32(b_int));
+ let expected = U64::from_u64(a_int as u64 * b_int as u64);
+ assert_eq!(lo, expected);
+ assert!(bool::from(hi.is_zero()));
+ }
+ }
+ }
+
+ #[test]
+ fn checked_mul_ok() {
+ let n = U64::from_u32(0xffff_ffff);
+ assert_eq!(
+ n.checked_mul(&n).unwrap(),
+ U64::from_u64(0xffff_fffe_0000_0001)
+ );
+ }
+
+ #[test]
+ fn checked_mul_overflow() {
+ let n = U64::from_u64(0xffff_ffff_ffff_ffff);
+ assert!(bool::from(n.checked_mul(&n).is_none()));
+ }
+
+ #[test]
+ fn saturating_mul_no_overflow() {
+ let n = U64::from_u8(8);
+ assert_eq!(n.saturating_mul(&n), U64::from_u8(64));
+ }
+
+ #[test]
+ fn saturating_mul_overflow() {
+ let a = U64::from(0xffff_ffff_ffff_ffffu64);
+ let b = U64::from(2u8);
+ assert_eq!(a.saturating_mul(&b), U64::MAX);
+ }
+
+ #[test]
+ fn square() {
+ let n = U64::from_u64(0xffff_ffff_ffff_ffff);
+ let (hi, lo) = n.square().split();
+ assert_eq!(lo, U64::from_u64(1));
+ assert_eq!(hi, U64::from_u64(0xffff_ffff_ffff_fffe));
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/mul_mod.rs b/vendor/crypto-bigint/src/uint/mul_mod.rs
new file mode 100644
index 000000000..1e9c053ea
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/mul_mod.rs
@@ -0,0 +1,131 @@
+//! [`UInt`] multiplication modulus operations.
+
+use crate::{Limb, UInt, WideWord, Word};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `self * rhs mod p` in constant time for the special modulus
+ /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
+ /// For the modulus reduction, this function implements Algorithm 14.47 from
+ /// the "Handbook of Applied Cryptography", by A. Menezes, P. van Oorschot,
+ /// and S. Vanstone, CRC Press, 1996.
+ pub const fn mul_mod_special(&self, rhs: &Self, c: Limb) -> Self {
+ // We implicitly assume `LIMBS > 0`, because `UInt<0>` doesn't compile.
+ // Still the case `LIMBS == 1` needs special handling.
+ if LIMBS == 1 {
+ let prod = self.limbs[0].0 as WideWord * rhs.limbs[0].0 as WideWord;
+ let reduced = prod % Word::MIN.wrapping_sub(c.0) as WideWord;
+ return Self::from_word(reduced as Word);
+ }
+
+ let (lo, hi) = self.mul_wide(rhs);
+
+ // Now use Algorithm 14.47 for the reduction
+ let (lo, carry) = mac_by_limb(lo, hi, c, Limb::ZERO);
+
+ let (lo, carry) = {
+ let rhs = (carry.0 + 1) as WideWord * c.0 as WideWord;
+ lo.adc(&Self::from_wide_word(rhs), Limb::ZERO)
+ };
+
+ let (lo, _) = {
+ let rhs = carry.0.wrapping_sub(1) & c.0;
+ lo.sbb(&Self::from_word(rhs), Limb::ZERO)
+ };
+
+ lo
+ }
+}
+
+/// Computes `a + (b * c) + carry`, returning the result along with the new carry.
+const fn mac_by_limb<const LIMBS: usize>(
+ mut a: UInt<LIMBS>,
+ b: UInt<LIMBS>,
+ c: Limb,
+ mut carry: Limb,
+) -> (UInt<LIMBS>, Limb) {
+ let mut i = 0;
+
+ while i < LIMBS {
+ let (n, c) = a.limbs[i].mac(b.limbs[i], c, carry);
+ a.limbs[i] = n;
+ carry = c;
+ i += 1;
+ }
+
+ (a, carry)
+}
+
+#[cfg(all(test, feature = "rand"))]
+mod tests {
+ use crate::{Limb, NonZero, Random, RandomMod, UInt};
+ use rand_core::SeedableRng;
+
+ macro_rules! test_mul_mod_special {
+ ($size:expr, $test_name:ident) => {
+ #[test]
+ fn $test_name() {
+ let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
+ let moduli = [
+ NonZero::<Limb>::random(&mut rng),
+ NonZero::<Limb>::random(&mut rng),
+ ];
+
+ for special in &moduli {
+ let p = &NonZero::new(UInt::ZERO.wrapping_sub(&UInt::from_word(special.0)))
+ .unwrap();
+
+ let minus_one = p.wrapping_sub(&UInt::ONE);
+
+ let base_cases = [
+ (UInt::ZERO, UInt::ZERO, UInt::ZERO),
+ (UInt::ONE, UInt::ZERO, UInt::ZERO),
+ (UInt::ZERO, UInt::ONE, UInt::ZERO),
+ (UInt::ONE, UInt::ONE, UInt::ONE),
+ (minus_one, minus_one, UInt::ONE),
+ (minus_one, UInt::ONE, minus_one),
+ (UInt::ONE, minus_one, minus_one),
+ ];
+ for (a, b, c) in &base_cases {
+ let x = a.mul_mod_special(&b, *special.as_ref());
+ assert_eq!(*c, x, "{} * {} mod {} = {} != {}", a, b, p, x, c);
+ }
+
+ for _i in 0..100 {
+ let a = UInt::<$size>::random_mod(&mut rng, p);
+ let b = UInt::<$size>::random_mod(&mut rng, p);
+
+ let c = a.mul_mod_special(&b, *special.as_ref());
+ assert!(c < **p, "not reduced: {} >= {} ", c, p);
+
+ let expected = {
+ let (lo, hi) = a.mul_wide(&b);
+ let mut prod = UInt::<{ 2 * $size }>::ZERO;
+ prod.limbs[..$size].clone_from_slice(&lo.limbs);
+ prod.limbs[$size..].clone_from_slice(&hi.limbs);
+ let mut modulus = UInt::ZERO;
+ modulus.limbs[..$size].clone_from_slice(&p.as_ref().limbs);
+ let reduced = prod.reduce(&modulus).unwrap();
+ let mut expected = UInt::ZERO;
+ expected.limbs[..].clone_from_slice(&reduced.limbs[..$size]);
+ expected
+ };
+ assert_eq!(c, expected, "incorrect result");
+ }
+ }
+ }
+ };
+ }
+
+ test_mul_mod_special!(1, mul_mod_special_1);
+ test_mul_mod_special!(2, mul_mod_special_2);
+ test_mul_mod_special!(3, mul_mod_special_3);
+ test_mul_mod_special!(4, mul_mod_special_4);
+ test_mul_mod_special!(5, mul_mod_special_5);
+ test_mul_mod_special!(6, mul_mod_special_6);
+ test_mul_mod_special!(7, mul_mod_special_7);
+ test_mul_mod_special!(8, mul_mod_special_8);
+ test_mul_mod_special!(9, mul_mod_special_9);
+ test_mul_mod_special!(10, mul_mod_special_10);
+ test_mul_mod_special!(11, mul_mod_special_11);
+ test_mul_mod_special!(12, mul_mod_special_12);
+}
diff --git a/vendor/crypto-bigint/src/uint/neg_mod.rs b/vendor/crypto-bigint/src/uint/neg_mod.rs
new file mode 100644
index 000000000..0a1dc033a
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/neg_mod.rs
@@ -0,0 +1,68 @@
+//! [`UInt`] negation modulus operations.
+
+use crate::{Limb, NegMod, UInt};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `-a mod p` in constant time.
+ /// Assumes `self` is in `[0, p)`.
+ pub const fn neg_mod(&self, p: &Self) -> Self {
+ let z = self.ct_is_nonzero();
+ let mut ret = p.sbb(self, Limb::ZERO).0;
+ let mut i = 0;
+ while i < LIMBS {
+ // Set ret to 0 if the original value was 0, in which
+ // case ret would be p.
+ ret.limbs[i].0 &= z;
+ i += 1;
+ }
+ ret
+ }
+
+ /// Computes `-a mod p` in constant time for the special modulus
+ /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
+ pub const fn neg_mod_special(&self, c: Limb) -> Self {
+ Self::ZERO.sub_mod_special(self, c)
+ }
+}
+
+impl<const LIMBS: usize> NegMod for UInt<LIMBS> {
+ type Output = Self;
+
+ fn neg_mod(&self, p: &Self) -> Self {
+ debug_assert!(self < p);
+ self.neg_mod(p)
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U256;
+
+ #[test]
+ fn neg_mod_random() {
+ let x =
+ U256::from_be_hex("8d16e171674b4e6d8529edba4593802bf30b8cb161dd30aa8e550d41380007c2");
+ let p =
+ U256::from_be_hex("928334a4e4be0843ec225a4c9c61df34bdc7a81513e4b6f76f2bfa3148e2e1b5");
+
+ let actual = x.neg_mod(&p);
+ let expected =
+ U256::from_be_hex("056c53337d72b9d666f86c9256ce5f08cabc1b63b207864ce0d6ecf010e2d9f3");
+
+ assert_eq!(expected, actual);
+ }
+
+ #[test]
+ fn neg_mod_zero() {
+ let x =
+ U256::from_be_hex("0000000000000000000000000000000000000000000000000000000000000000");
+ let p =
+ U256::from_be_hex("928334a4e4be0843ec225a4c9c61df34bdc7a81513e4b6f76f2bfa3148e2e1b5");
+
+ let actual = x.neg_mod(&p);
+ let expected =
+ U256::from_be_hex("0000000000000000000000000000000000000000000000000000000000000000");
+
+ assert_eq!(expected, actual);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/rand.rs b/vendor/crypto-bigint/src/uint/rand.rs
new file mode 100644
index 000000000..df551c71b
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/rand.rs
@@ -0,0 +1,92 @@
+//! Random number generator support
+
+use super::UInt;
+use crate::{Limb, NonZero, Random, RandomMod};
+use rand_core::{CryptoRng, RngCore};
+use subtle::ConstantTimeLess;
+
+#[cfg_attr(docsrs, doc(cfg(feature = "rand_core")))]
+impl<const LIMBS: usize> Random for UInt<LIMBS> {
+ /// Generate a cryptographically secure random [`UInt`].
+ fn random(mut rng: impl CryptoRng + RngCore) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+
+ for limb in &mut limbs {
+ *limb = Limb::random(&mut rng)
+ }
+
+ limbs.into()
+ }
+}
+
+#[cfg_attr(docsrs, doc(cfg(feature = "rand_core")))]
+impl<const LIMBS: usize> RandomMod for UInt<LIMBS> {
+ /// Generate a cryptographically secure random [`UInt`] which is less than
+ /// a given `modulus`.
+ ///
+ /// This function uses rejection sampling, a method which produces an
+ /// unbiased distribution of in-range values provided the underlying
+ /// [`CryptoRng`] is unbiased, but runs in variable-time.
+ ///
+ /// The variable-time nature of the algorithm should not pose a security
+ /// issue so long as the underlying random number generator is truly a
+ /// [`CryptoRng`], where previous outputs are unrelated to subsequent
+ /// outputs and do not reveal information about the RNG's internal state.
+ fn random_mod(mut rng: impl CryptoRng + RngCore, modulus: &NonZero<Self>) -> Self {
+ let mut n = Self::ZERO;
+
+ // TODO(tarcieri): use `div_ceil` when available
+ // See: https://github.com/rust-lang/rust/issues/88581
+ let mut n_limbs = modulus.bits_vartime() / Limb::BIT_SIZE;
+ if n_limbs < LIMBS {
+ n_limbs += 1;
+ }
+
+ // Compute the highest limb of `modulus` as a `NonZero`.
+ // Add one to ensure `Limb::random_mod` returns values inclusive of this limb.
+ let modulus_hi =
+ NonZero::new(modulus.limbs[n_limbs.saturating_sub(1)].saturating_add(Limb::ONE))
+ .unwrap(); // Always at least one due to `saturating_add`
+
+ loop {
+ for i in 0..n_limbs {
+ n.limbs[i] = if (i + 1 == n_limbs) && (*modulus_hi != Limb::MAX) {
+ // Highest limb
+ Limb::random_mod(&mut rng, &modulus_hi)
+ } else {
+ Limb::random(&mut rng)
+ }
+ }
+
+ if n.ct_lt(modulus).into() {
+ return n;
+ }
+ }
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{NonZero, RandomMod, U256};
+ use rand_core::SeedableRng;
+
+ #[test]
+ fn random_mod() {
+ let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
+
+ // Ensure `random_mod` runs in a reasonable amount of time
+ let modulus = NonZero::new(U256::from(42u8)).unwrap();
+ let res = U256::random_mod(&mut rng, &modulus);
+
+ // Sanity check that the return value isn't zero
+ assert_ne!(res, U256::ZERO);
+
+ // Ensure `random_mod` runs in a reasonable amount of time
+ // when the modulus is larger than 1 limb
+ let modulus = NonZero::new(U256::from(0x10000000000000001u128)).unwrap();
+ let res = U256::random_mod(&mut rng, &modulus);
+
+ // Sanity check that the return value isn't zero
+ assert_ne!(res, U256::ZERO);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/resize.rs b/vendor/crypto-bigint/src/uint/resize.rs
new file mode 100644
index 000000000..5a5ec7eef
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/resize.rs
@@ -0,0 +1,37 @@
+use super::UInt;
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Construct a `UInt<T>` from the unsigned integer value,
+ /// truncating the upper bits if the value is too large to be
+ /// represented.
+ #[inline(always)]
+ pub const fn resize<const T: usize>(&self) -> UInt<T> {
+ let mut res = UInt::ZERO;
+ let mut i = 0;
+ let dim = if T < LIMBS { T } else { LIMBS };
+ while i < dim {
+ res.limbs[i] = self.limbs[i];
+ i += 1;
+ }
+ res
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{U128, U64};
+
+ #[test]
+ fn resize_larger() {
+ let u = U64::from_be_hex("AAAAAAAABBBBBBBB");
+ let u2: U128 = u.resize();
+ assert_eq!(u2, U128::from_be_hex("0000000000000000AAAAAAAABBBBBBBB"));
+ }
+
+ #[test]
+ fn resize_smaller() {
+ let u = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
+ let u2: U64 = u.resize();
+ assert_eq!(u2, U64::from_be_hex("CCCCCCCCDDDDDDDD"));
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/shl.rs b/vendor/crypto-bigint/src/uint/shl.rs
new file mode 100644
index 000000000..9d4669130
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/shl.rs
@@ -0,0 +1,134 @@
+//! [`UInt`] bitwise left shift operations.
+
+use crate::{Limb, UInt, Word};
+use core::ops::{Shl, ShlAssign};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `self << shift`.
+ ///
+ /// NOTE: this operation is variable time with respect to `n` *ONLY*.
+ ///
+ /// When used with a fixed `n`, this function is constant-time with respect
+ /// to `self`.
+ #[inline(always)]
+ pub const fn shl_vartime(&self, n: usize) -> Self {
+ let mut limbs = [Limb::ZERO; LIMBS];
+
+ if n >= Limb::BIT_SIZE * LIMBS {
+ return Self { limbs };
+ }
+
+ let shift_num = n / Limb::BIT_SIZE;
+ let rem = n % Limb::BIT_SIZE;
+ let nz = Limb(rem as Word).is_nonzero();
+ let lshift_rem = rem as Word;
+ let rshift_rem = Limb::ct_select(Limb::ZERO, Limb((Limb::BIT_SIZE - rem) as Word), nz).0;
+
+ let mut i = LIMBS - 1;
+ while i > shift_num {
+ let mut limb = self.limbs[i - shift_num].0 << lshift_rem;
+ let hi = self.limbs[i - shift_num - 1].0 >> rshift_rem;
+ limb |= hi & nz;
+ limbs[i] = Limb(limb);
+ i -= 1
+ }
+ limbs[shift_num] = Limb(self.limbs[0].0 << lshift_rem);
+
+ Self { limbs }
+ }
+}
+
+impl<const LIMBS: usize> Shl<usize> for UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
+ ///
+ /// When used with a fixed `rhs`, this function is constant-time with respect
+ /// to `self`.
+ fn shl(self, rhs: usize) -> UInt<LIMBS> {
+ self.shl_vartime(rhs)
+ }
+}
+
+impl<const LIMBS: usize> Shl<usize> for &UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
+ ///
+ /// When used with a fixed `rhs`, this function is constant-time with respect
+ /// to `self`.
+ fn shl(self, rhs: usize) -> UInt<LIMBS> {
+ self.shl_vartime(rhs)
+ }
+}
+
+impl<const LIMBS: usize> ShlAssign<usize> for UInt<LIMBS> {
+ /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
+ ///
+ /// When used with a fixed `rhs`, this function is constant-time with respect
+ /// to `self`.
+ fn shl_assign(&mut self, rhs: usize) {
+ *self = self.shl_vartime(rhs)
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U256;
+
+ const N: U256 =
+ U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
+
+ const TWO_N: U256 =
+ U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD755DB9CD5E9140777FA4BD19A06C8282");
+
+ const FOUR_N: U256 =
+ U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFAEABB739ABD2280EEFF497A3340D90504");
+
+ const SIXTY_FIVE: U256 =
+ U256::from_be_hex("FFFFFFFFFFFFFFFD755DB9CD5E9140777FA4BD19A06C82820000000000000000");
+
+ const EIGHTY_EIGHT: U256 =
+ U256::from_be_hex("FFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD03641410000000000000000000000");
+
+ const SIXTY_FOUR: U256 =
+ U256::from_be_hex("FFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD03641410000000000000000");
+
+ #[test]
+ fn shl_simple() {
+ let mut t = U256::from(1u8);
+ assert_eq!(t << 1, U256::from(2u8));
+ t = U256::from(3u8);
+ assert_eq!(t << 8, U256::from(0x300u16));
+ }
+
+ #[test]
+ fn shl1() {
+ assert_eq!(N << 1, TWO_N);
+ }
+
+ #[test]
+ fn shl2() {
+ assert_eq!(N << 2, FOUR_N);
+ }
+
+ #[test]
+ fn shl65() {
+ assert_eq!(N << 65, SIXTY_FIVE);
+ }
+
+ #[test]
+ fn shl88() {
+ assert_eq!(N << 88, EIGHTY_EIGHT);
+ }
+
+ #[test]
+ fn shl256() {
+ assert_eq!(N << 256, U256::default());
+ }
+
+ #[test]
+ fn shl64() {
+ assert_eq!(N << 64, SIXTY_FOUR);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/shr.rs b/vendor/crypto-bigint/src/uint/shr.rs
new file mode 100644
index 000000000..54375ae72
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/shr.rs
@@ -0,0 +1,93 @@
+//! [`UInt`] bitwise right shift operations.
+
+use super::UInt;
+use crate::Limb;
+use core::ops::{Shr, ShrAssign};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `self >> n`.
+ ///
+ /// NOTE: this operation is variable time with respect to `n` *ONLY*.
+ ///
+ /// When used with a fixed `n`, this function is constant-time with respect
+ /// to `self`.
+ #[inline(always)]
+ pub const fn shr_vartime(&self, shift: usize) -> Self {
+ let full_shifts = shift / Limb::BIT_SIZE;
+ let small_shift = shift & (Limb::BIT_SIZE - 1);
+ let mut limbs = [Limb::ZERO; LIMBS];
+
+ if shift > Limb::BIT_SIZE * LIMBS {
+ return Self { limbs };
+ }
+
+ let n = LIMBS - full_shifts;
+ let mut i = 0;
+
+ if small_shift == 0 {
+ while i < n {
+ limbs[i] = Limb(self.limbs[i + full_shifts].0);
+ i += 1;
+ }
+ } else {
+ while i < n {
+ let mut lo = self.limbs[i + full_shifts].0 >> small_shift;
+
+ if i < (LIMBS - 1) - full_shifts {
+ lo |= self.limbs[i + full_shifts + 1].0 << (Limb::BIT_SIZE - small_shift);
+ }
+
+ limbs[i] = Limb(lo);
+ i += 1;
+ }
+ }
+
+ Self { limbs }
+ }
+}
+
+impl<const LIMBS: usize> Shr<usize> for UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
+ ///
+ /// When used with a fixed `rhs`, this function is constant-time with respect
+ /// to `self`.
+ fn shr(self, rhs: usize) -> UInt<LIMBS> {
+ self.shr_vartime(rhs)
+ }
+}
+
+impl<const LIMBS: usize> Shr<usize> for &UInt<LIMBS> {
+ type Output = UInt<LIMBS>;
+
+ /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
+ ///
+ /// When used with a fixed `rhs`, this function is constant-time with respect
+ /// to `self`.
+ fn shr(self, rhs: usize) -> UInt<LIMBS> {
+ self.shr_vartime(rhs)
+ }
+}
+
+impl<const LIMBS: usize> ShrAssign<usize> for UInt<LIMBS> {
+ fn shr_assign(&mut self, rhs: usize) {
+ *self = self.shr_vartime(rhs);
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::U256;
+
+ const N: U256 =
+ U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
+
+ const N_2: U256 =
+ U256::from_be_hex("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0");
+
+ #[test]
+ fn shr1() {
+ assert_eq!(N >> 1, N_2);
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/split.rs b/vendor/crypto-bigint/src/uint/split.rs
new file mode 100644
index 000000000..ecff9d6d8
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/split.rs
@@ -0,0 +1,58 @@
+// TODO(tarcieri): use `const_evaluatable_checked` when stable to make generic around bits.
+macro_rules! impl_split {
+ ($(($name:ident, $bits:expr)),+) => {
+ $(
+ impl $name {
+ /// Split this number in half, returning its high and low components
+ /// respectively.
+ pub const fn split(&self) -> (UInt<{nlimbs!($bits) / 2}>, UInt<{nlimbs!($bits) / 2}>) {
+ let mut lo = [Limb::ZERO; nlimbs!($bits) / 2];
+ let mut hi = [Limb::ZERO; nlimbs!($bits) / 2];
+ let mut i = 0;
+ let mut j = 0;
+
+ while j < (nlimbs!($bits) / 2) {
+ lo[j] = self.limbs[i];
+ i += 1;
+ j += 1;
+ }
+
+ j = 0;
+ while j < (nlimbs!($bits) / 2) {
+ hi[j] = self.limbs[i];
+ i += 1;
+ j += 1;
+ }
+
+ (UInt { limbs: hi }, UInt { limbs: lo })
+ }
+ }
+
+ impl Split for $name {
+ type Output = UInt<{nlimbs!($bits) / 2}>;
+
+ fn split(&self) -> (Self::Output, Self::Output) {
+ self.split()
+ }
+ }
+
+ impl From<$name> for (UInt<{nlimbs!($bits) / 2}>, UInt<{nlimbs!($bits) / 2}>) {
+ fn from(num: $name) -> (UInt<{nlimbs!($bits) / 2}>, UInt<{nlimbs!($bits) / 2}>) {
+ num.split()
+ }
+ }
+ )+
+ };
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{U128, U64};
+
+ #[test]
+ fn split() {
+ let (hi, lo) = U128::from_be_hex("00112233445566778899aabbccddeeff").split();
+ assert_eq!(hi, U64::from_u64(0x0011223344556677));
+ assert_eq!(lo, U64::from_u64(0x8899aabbccddeeff));
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/sqrt.rs b/vendor/crypto-bigint/src/uint/sqrt.rs
new file mode 100644
index 000000000..4a9f26a61
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/sqrt.rs
@@ -0,0 +1,145 @@
+//! [`UInt`] square root operations.
+
+use super::UInt;
+use crate::{Limb, Word};
+use subtle::{ConstantTimeEq, CtOption};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes √(`self`)
+ /// Uses Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.13
+ ///
+ /// Callers can check if `self` is a square by squaring the result
+ pub const fn sqrt(&self) -> Self {
+ let max_bits = (self.bits_vartime() + 1) >> 1;
+ let cap = Self::ONE.shl_vartime(max_bits);
+ let mut guess = cap; // ≥ √(`self`)
+ let mut xn = {
+ let q = self.wrapping_div(&guess);
+ let t = guess.wrapping_add(&q);
+ t.shr_vartime(1)
+ };
+
+ // If guess increased, the initial guess was low.
+ // Repeat until reverse course.
+ while guess.ct_cmp(&xn) == -1 {
+ // Sometimes an increase is too far, especially with large
+ // powers, and then takes a long time to walk back. The upper
+ // bound is based on bit size, so saturate on that.
+ let res = Limb::ct_cmp(Limb(xn.bits_vartime() as Word), Limb(max_bits as Word)) - 1;
+ let le = Limb::is_nonzero(Limb(res as Word));
+ guess = Self::ct_select(cap, xn, le);
+ xn = {
+ let q = self.wrapping_div(&guess);
+ let t = guess.wrapping_add(&q);
+ t.shr_vartime(1)
+ };
+ }
+
+ // Repeat while guess decreases.
+ while guess.ct_cmp(&xn) == 1 && xn.ct_is_nonzero() == Word::MAX {
+ guess = xn;
+ xn = {
+ let q = self.wrapping_div(&guess);
+ let t = guess.wrapping_add(&q);
+ t.shr_vartime(1)
+ };
+ }
+
+ Self::ct_select(Self::ZERO, guess, self.ct_is_nonzero())
+ }
+
+ /// Wrapped sqrt is just normal √(`self`)
+ /// There’s no way wrapping could ever happen.
+ /// This function exists, so that all operations are accounted for in the wrapping operations.
+ pub const fn wrapping_sqrt(&self) -> Self {
+ self.sqrt()
+ }
+
+ /// Perform checked sqrt, returning a [`CtOption`] which `is_some`
+ /// only if the √(`self`)² == self
+ pub fn checked_sqrt(&self) -> CtOption<Self> {
+ let r = self.sqrt();
+ let s = r.wrapping_mul(&r);
+ CtOption::new(r, self.ct_eq(&s))
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{Limb, U256};
+
+ #[cfg(feature = "rand")]
+ use {
+ crate::{CheckedMul, Random, U512},
+ rand_chacha::ChaChaRng,
+ rand_core::{RngCore, SeedableRng},
+ };
+
+ #[test]
+ fn edge() {
+ assert_eq!(U256::ZERO.sqrt(), U256::ZERO);
+ assert_eq!(U256::ONE.sqrt(), U256::ONE);
+ let mut half = U256::ZERO;
+ for i in 0..half.limbs.len() / 2 {
+ half.limbs[i] = Limb::MAX;
+ }
+ assert_eq!(U256::MAX.sqrt(), half,);
+ }
+
+ #[test]
+ fn simple() {
+ let tests = [
+ (4u8, 2u8),
+ (9, 3),
+ (16, 4),
+ (25, 5),
+ (36, 6),
+ (49, 7),
+ (64, 8),
+ (81, 9),
+ (100, 10),
+ (121, 11),
+ (144, 12),
+ (169, 13),
+ ];
+ for (a, e) in &tests {
+ let l = U256::from(*a);
+ let r = U256::from(*e);
+ assert_eq!(l.sqrt(), r);
+ assert_eq!(l.checked_sqrt().is_some().unwrap_u8(), 1u8);
+ }
+ }
+
+ #[test]
+ fn nonsquares() {
+ assert_eq!(U256::from(2u8).sqrt(), U256::from(1u8));
+ assert_eq!(U256::from(2u8).checked_sqrt().is_some().unwrap_u8(), 0);
+ assert_eq!(U256::from(3u8).sqrt(), U256::from(1u8));
+ assert_eq!(U256::from(3u8).checked_sqrt().is_some().unwrap_u8(), 0);
+ assert_eq!(U256::from(5u8).sqrt(), U256::from(2u8));
+ assert_eq!(U256::from(6u8).sqrt(), U256::from(2u8));
+ assert_eq!(U256::from(7u8).sqrt(), U256::from(2u8));
+ assert_eq!(U256::from(8u8).sqrt(), U256::from(2u8));
+ assert_eq!(U256::from(10u8).sqrt(), U256::from(3u8));
+ }
+
+ #[cfg(feature = "rand")]
+ #[test]
+ fn fuzz() {
+ let mut rng = ChaChaRng::from_seed([7u8; 32]);
+ for _ in 0..50 {
+ let t = rng.next_u32() as u64;
+ let s = U256::from(t);
+ let s2 = s.checked_mul(&s).unwrap();
+ assert_eq!(s2.sqrt(), s);
+ assert_eq!(s2.checked_sqrt().is_some().unwrap_u8(), 1);
+ }
+
+ for _ in 0..50 {
+ let s = U256::random(&mut rng);
+ let mut s2 = U512::ZERO;
+ s2.limbs[..s.limbs.len()].copy_from_slice(&s.limbs);
+ assert_eq!(s.square().sqrt(), s2);
+ }
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/sub.rs b/vendor/crypto-bigint/src/uint/sub.rs
new file mode 100644
index 000000000..102f6b978
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/sub.rs
@@ -0,0 +1,192 @@
+//! [`UInt`] addition operations.
+
+use super::UInt;
+use crate::{Checked, CheckedSub, Limb, Wrapping, Zero};
+use core::ops::{Sub, SubAssign};
+use subtle::CtOption;
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `a - (b + borrow)`, returning the result along with the new borrow.
+ #[inline(always)]
+ pub const fn sbb(&self, rhs: &Self, mut borrow: Limb) -> (Self, Limb) {
+ let mut limbs = [Limb::ZERO; LIMBS];
+ let mut i = 0;
+
+ while i < LIMBS {
+ let (w, b) = self.limbs[i].sbb(rhs.limbs[i], borrow);
+ limbs[i] = w;
+ borrow = b;
+ i += 1;
+ }
+
+ (Self { limbs }, borrow)
+ }
+
+ /// Perform saturating subtraction, returning `ZERO` on underflow.
+ pub const fn saturating_sub(&self, rhs: &Self) -> Self {
+ let (res, underflow) = self.sbb(rhs, Limb::ZERO);
+
+ if underflow.0 == 0 {
+ res
+ } else {
+ Self::ZERO
+ }
+ }
+
+ /// Perform wrapping subtraction, discarding underflow and wrapping around
+ /// the boundary of the type.
+ pub const fn wrapping_sub(&self, rhs: &Self) -> Self {
+ self.sbb(rhs, Limb::ZERO).0
+ }
+}
+
+impl<const LIMBS: usize> CheckedSub<&UInt<LIMBS>> for UInt<LIMBS> {
+ type Output = Self;
+
+ fn checked_sub(&self, rhs: &Self) -> CtOption<Self> {
+ let (result, underflow) = self.sbb(rhs, Limb::ZERO);
+ CtOption::new(result, underflow.is_zero())
+ }
+}
+
+impl<const LIMBS: usize> Sub for Wrapping<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn sub(self, rhs: Self) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_sub(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Sub<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn sub(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_sub(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Sub<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn sub(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_sub(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> Sub<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
+ type Output = Wrapping<UInt<LIMBS>>;
+
+ fn sub(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
+ Wrapping(self.0.wrapping_sub(&rhs.0))
+ }
+}
+
+impl<const LIMBS: usize> SubAssign for Wrapping<UInt<LIMBS>> {
+ fn sub_assign(&mut self, other: Self) {
+ *self = *self - other;
+ }
+}
+
+impl<const LIMBS: usize> SubAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
+ fn sub_assign(&mut self, other: &Self) {
+ *self = *self - other;
+ }
+}
+
+impl<const LIMBS: usize> Sub for Checked<UInt<LIMBS>> {
+ type Output = Self;
+
+ fn sub(self, rhs: Self) -> Checked<UInt<LIMBS>> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_sub(&rhs))),
+ )
+ }
+}
+
+impl<const LIMBS: usize> Sub<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn sub(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_sub(&rhs))),
+ )
+ }
+}
+
+impl<const LIMBS: usize> Sub<Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn sub(self, rhs: Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_sub(&rhs))),
+ )
+ }
+}
+
+impl<const LIMBS: usize> Sub<&Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
+ type Output = Checked<UInt<LIMBS>>;
+
+ fn sub(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
+ Checked(
+ self.0
+ .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_sub(&rhs))),
+ )
+ }
+}
+
+impl<const LIMBS: usize> SubAssign for Checked<UInt<LIMBS>> {
+ fn sub_assign(&mut self, other: Self) {
+ *self = *self - other;
+ }
+}
+
+impl<const LIMBS: usize> SubAssign<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
+ fn sub_assign(&mut self, other: &Self) {
+ *self = *self - other;
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::{CheckedSub, Limb, U128};
+
+ #[test]
+ fn sbb_no_borrow() {
+ let (res, borrow) = U128::ONE.sbb(&U128::ONE, Limb::ZERO);
+ assert_eq!(res, U128::ZERO);
+ assert_eq!(borrow, Limb::ZERO);
+ }
+
+ #[test]
+ fn sbb_with_borrow() {
+ let (res, borrow) = U128::ZERO.sbb(&U128::ONE, Limb::ZERO);
+
+ assert_eq!(res, U128::MAX);
+ assert_eq!(borrow, Limb::MAX);
+ }
+
+ #[test]
+ fn wrapping_sub_no_borrow() {
+ assert_eq!(U128::ONE.wrapping_sub(&U128::ONE), U128::ZERO);
+ }
+
+ #[test]
+ fn wrapping_sub_with_borrow() {
+ assert_eq!(U128::ZERO.wrapping_sub(&U128::ONE), U128::MAX);
+ }
+
+ #[test]
+ fn checked_sub_ok() {
+ let result = U128::ONE.checked_sub(&U128::ONE);
+ assert_eq!(result.unwrap(), U128::ZERO);
+ }
+
+ #[test]
+ fn checked_sub_overflow() {
+ let result = U128::ZERO.checked_sub(&U128::ONE);
+ assert!(!bool::from(result.is_some()));
+ }
+}
diff --git a/vendor/crypto-bigint/src/uint/sub_mod.rs b/vendor/crypto-bigint/src/uint/sub_mod.rs
new file mode 100644
index 000000000..f699f66eb
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/sub_mod.rs
@@ -0,0 +1,182 @@
+//! [`UInt`] subtraction modulus operations.
+
+use crate::{Limb, SubMod, UInt};
+
+impl<const LIMBS: usize> UInt<LIMBS> {
+ /// Computes `self - rhs mod p` in constant time.
+ ///
+ /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
+ pub const fn sub_mod(&self, rhs: &UInt<LIMBS>, p: &UInt<LIMBS>) -> UInt<LIMBS> {
+ let (mut out, borrow) = self.sbb(rhs, Limb::ZERO);
+
+ // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
+ // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
+ let mut carry = Limb::ZERO;
+ let mut i = 0;
+
+ while i < LIMBS {
+ let (l, c) = out.limbs[i].adc(p.limbs[i].bitand(borrow), carry);
+ out.limbs[i] = l;
+ carry = c;
+ i += 1;
+ }
+
+ out
+ }
+
+ /// Computes `self - rhs mod p` in constant time for the special modulus
+ /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
+ ///
+ /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
+ pub const fn sub_mod_special(&self, rhs: &Self, c: Limb) -> Self {
+ let (out, borrow) = self.sbb(rhs, Limb::ZERO);
+
+ // If underflow occurred, then we need to subtract `c` to account for
+ // the underflow. This cannot underflow due to the assumption
+ // `self - rhs >= -p`.
+ let l = borrow.0 & c.0;
+ let (out, _) = out.sbb(&UInt::from_word(l), Limb::ZERO);
+ out
+ }
+}
+
+impl<const LIMBS: usize> SubMod for UInt<LIMBS> {
+ type Output = Self;
+
+ fn sub_mod(&self, rhs: &Self, p: &Self) -> Self {
+ debug_assert!(self < p);
+ debug_assert!(rhs < p);
+ self.sub_mod(rhs, p)
+ }
+}
+
+#[cfg(all(test, feature = "rand"))]
+mod tests {
+ use crate::{Limb, NonZero, Random, RandomMod, UInt};
+ use rand_core::SeedableRng;
+
+ macro_rules! test_sub_mod {
+ ($size:expr, $test_name:ident) => {
+ #[test]
+ fn $test_name() {
+ let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
+ let moduli = [
+ NonZero::<UInt<$size>>::random(&mut rng),
+ NonZero::<UInt<$size>>::random(&mut rng),
+ ];
+
+ for p in &moduli {
+ let base_cases = [
+ (1u64, 0u64, 1u64.into()),
+ (0, 1, p.wrapping_sub(&1u64.into())),
+ (0, 0, 0u64.into()),
+ ];
+ for (a, b, c) in &base_cases {
+ let a: UInt<$size> = (*a).into();
+ let b: UInt<$size> = (*b).into();
+
+ let x = a.sub_mod(&b, p);
+ assert_eq!(*c, x, "{} - {} mod {} = {} != {}", a, b, p, x, c);
+ }
+
+ if $size > 1 {
+ for _i in 0..100 {
+ let a: UInt<$size> = Limb::random(&mut rng).into();
+ let b: UInt<$size> = Limb::random(&mut rng).into();
+ let (a, b) = if a < b { (b, a) } else { (a, b) };
+
+ let c = a.sub_mod(&b, p);
+ assert!(c < **p, "not reduced");
+ assert_eq!(c, a.wrapping_sub(&b), "result incorrect");
+ }
+ }
+
+ for _i in 0..100 {
+ let a = UInt::<$size>::random_mod(&mut rng, p);
+ let b = UInt::<$size>::random_mod(&mut rng, p);
+
+ let c = a.sub_mod(&b, p);
+ assert!(c < **p, "not reduced: {} >= {} ", c, p);
+
+ let x = a.wrapping_sub(&b);
+ if a >= b && x < **p {
+ assert_eq!(c, x, "incorrect result");
+ }
+ }
+ }
+ }
+ };
+ }
+
+ macro_rules! test_sub_mod_special {
+ ($size:expr, $test_name:ident) => {
+ #[test]
+ fn $test_name() {
+ let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
+ let moduli = [
+ NonZero::<Limb>::random(&mut rng),
+ NonZero::<Limb>::random(&mut rng),
+ ];
+
+ for special in &moduli {
+ let p = &NonZero::new(UInt::ZERO.wrapping_sub(&UInt::from_word(special.0)))
+ .unwrap();
+
+ let minus_one = p.wrapping_sub(&UInt::ONE);
+
+ let base_cases = [
+ (UInt::ZERO, UInt::ZERO, UInt::ZERO),
+ (UInt::ONE, UInt::ZERO, UInt::ONE),
+ (UInt::ZERO, UInt::ONE, minus_one),
+ (minus_one, minus_one, UInt::ZERO),
+ (UInt::ZERO, minus_one, UInt::ONE),
+ ];
+ for (a, b, c) in &base_cases {
+ let x = a.sub_mod_special(&b, *special.as_ref());
+ assert_eq!(*c, x, "{} - {} mod {} = {} != {}", a, b, p, x, c);
+ }
+
+ for _i in 0..100 {
+ let a = UInt::<$size>::random_mod(&mut rng, p);
+ let b = UInt::<$size>::random_mod(&mut rng, p);
+
+ let c = a.sub_mod_special(&b, *special.as_ref());
+ assert!(c < **p, "not reduced: {} >= {} ", c, p);
+
+ let expected = a.sub_mod(&b, p);
+ assert_eq!(c, expected, "incorrect result");
+ }
+ }
+ }
+ };
+ }
+
+ // Test requires 1-limb is capable of representing a 64-bit integer
+ #[cfg(target_pointer_width = "64")]
+ test_sub_mod!(1, sub1);
+
+ test_sub_mod!(2, sub2);
+ test_sub_mod!(3, sub3);
+ test_sub_mod!(4, sub4);
+ test_sub_mod!(5, sub5);
+ test_sub_mod!(6, sub6);
+ test_sub_mod!(7, sub7);
+ test_sub_mod!(8, sub8);
+ test_sub_mod!(9, sub9);
+ test_sub_mod!(10, sub10);
+ test_sub_mod!(11, sub11);
+ test_sub_mod!(12, sub12);
+
+ test_sub_mod_special!(1, sub_mod_special_1);
+ test_sub_mod_special!(2, sub_mod_special_2);
+ test_sub_mod_special!(3, sub_mod_special_3);
+ test_sub_mod_special!(4, sub_mod_special_4);
+ test_sub_mod_special!(5, sub_mod_special_5);
+ test_sub_mod_special!(6, sub_mod_special_6);
+ test_sub_mod_special!(7, sub_mod_special_7);
+ test_sub_mod_special!(8, sub_mod_special_8);
+ test_sub_mod_special!(9, sub_mod_special_9);
+ test_sub_mod_special!(10, sub_mod_special_10);
+ test_sub_mod_special!(11, sub_mod_special_11);
+ test_sub_mod_special!(12, sub_mod_special_12);
+}
diff --git a/vendor/crypto-bigint/src/wrapping.rs b/vendor/crypto-bigint/src/wrapping.rs
new file mode 100644
index 000000000..c2f6c2b34
--- /dev/null
+++ b/vendor/crypto-bigint/src/wrapping.rs
@@ -0,0 +1,108 @@
+//! Wrapping arithmetic.
+
+use crate::Zero;
+use core::fmt;
+use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
+
+#[cfg(feature = "serde")]
+use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
+
+/// Provides intentionally-wrapped arithmetic on `T`.
+///
+/// This is analogous to [`core::num::Wrapping`] but allows this crate to
+/// define trait impls for this type.
+#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, PartialOrd, Ord)]
+pub struct Wrapping<T>(pub T);
+
+impl<T: Zero> Zero for Wrapping<T> {
+ const ZERO: Self = Self(T::ZERO);
+}
+
+impl<T: fmt::Display> fmt::Display for Wrapping<T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.0.fmt(f)
+ }
+}
+
+impl<T: fmt::Binary> fmt::Binary for Wrapping<T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.0.fmt(f)
+ }
+}
+
+impl<T: fmt::Octal> fmt::Octal for Wrapping<T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.0.fmt(f)
+ }
+}
+
+impl<T: fmt::LowerHex> fmt::LowerHex for Wrapping<T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.0.fmt(f)
+ }
+}
+
+impl<T: fmt::UpperHex> fmt::UpperHex for Wrapping<T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.0.fmt(f)
+ }
+}
+
+impl<T: ConditionallySelectable> ConditionallySelectable for Wrapping<T> {
+ fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
+ Wrapping(T::conditional_select(&a.0, &b.0, choice))
+ }
+}
+
+impl<T: ConstantTimeEq> ConstantTimeEq for Wrapping<T> {
+ fn ct_eq(&self, other: &Self) -> Choice {
+ self.0.ct_eq(&other.0)
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de, T: Deserialize<'de>> Deserialize<'de> for Wrapping<T> {
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ Ok(Self(T::deserialize(deserializer)?))
+ }
+}
+
+#[cfg(feature = "serde")]
+#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
+impl<'de, T: Serialize> Serialize for Wrapping<T> {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ self.0.serialize(serializer)
+ }
+}
+
+#[cfg(all(test, feature = "serde"))]
+mod tests {
+ use crate::{Wrapping, U64};
+
+ #[test]
+ fn serde() {
+ const TEST: Wrapping<U64> = Wrapping(U64::from_u64(0x0011223344556677));
+
+ let serialized = bincode::serialize(&TEST).unwrap();
+ let deserialized: Wrapping<U64> = bincode::deserialize(&serialized).unwrap();
+
+ assert_eq!(TEST, deserialized);
+ }
+
+ #[test]
+ fn serde_owned() {
+ const TEST: Wrapping<U64> = Wrapping(U64::from_u64(0x0011223344556677));
+
+ let serialized = bincode::serialize(&TEST).unwrap();
+ let deserialized: Wrapping<U64> = bincode::deserialize_from(serialized.as_slice()).unwrap();
+
+ assert_eq!(TEST, deserialized);
+ }
+}
diff --git a/vendor/crypto-bigint/tests/proptests.rs b/vendor/crypto-bigint/tests/proptests.rs
new file mode 100644
index 000000000..42a3066c6
--- /dev/null
+++ b/vendor/crypto-bigint/tests/proptests.rs
@@ -0,0 +1,209 @@
+//! Equivalence tests between `num-bigint` and `crypto-bigint`
+
+use crypto_bigint::{Encoding, U256};
+use num_bigint::BigUint;
+use num_traits::identities::Zero;
+use proptest::prelude::*;
+use std::mem;
+
+/// Example prime number (NIST P-256 curve order)
+const P: U256 =
+ U256::from_be_hex("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551");
+
+fn to_biguint(uint: &U256) -> BigUint {
+ BigUint::from_bytes_le(uint.to_le_bytes().as_ref())
+}
+
+fn to_uint(big_uint: BigUint) -> U256 {
+ let mut input = [0u8; U256::BYTE_SIZE];
+ let encoded = big_uint.to_bytes_le();
+ let l = encoded.len().min(U256::BYTE_SIZE);
+ input[..l].copy_from_slice(&encoded[..l]);
+
+ U256::from_le_slice(&input)
+}
+
+prop_compose! {
+ fn uint()(bytes in any::<[u8; 32]>()) -> U256 {
+ U256::from_le_slice(&bytes)
+ }
+}
+prop_compose! {
+ fn uint_mod_p(p: U256)(a in uint()) -> U256 {
+ a.wrapping_rem(&p)
+ }
+}
+
+proptest! {
+ #[test]
+ fn roundtrip(a in uint()) {
+ assert_eq!(a, to_uint(to_biguint(&a)));
+ }
+
+ #[test]
+ fn wrapping_add(a in uint(), b in uint()) {
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+
+ let expected = to_uint(a_bi + b_bi);
+ let actual = a.wrapping_add(&b);
+
+ assert_eq!(expected, actual);
+ }
+
+ #[test]
+ fn add_mod_nist_p256(a in uint_mod_p(P), b in uint_mod_p(P)) {
+ assert!(a < P);
+ assert!(b < P);
+
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+ let p_bi = to_biguint(&P);
+
+ let expected = to_uint((a_bi + b_bi) % p_bi);
+ let actual = a.add_mod(&b, &P);
+
+ assert!(expected < P);
+ assert!(actual < P);
+
+ assert_eq!(expected, actual);
+ }
+
+ #[test]
+ fn sub_mod_nist_p256(mut a in uint_mod_p(P), mut b in uint_mod_p(P)) {
+ if b > a {
+ mem::swap(&mut a, &mut b);
+ }
+
+ assert!(a < P);
+ assert!(b < P);
+
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+ let p_bi = to_biguint(&P);
+
+ let expected = to_uint((a_bi - b_bi) % p_bi);
+ let actual = a.sub_mod(&b, &P);
+
+ assert!(expected < P);
+ assert!(actual < P);
+
+ assert_eq!(expected, actual);
+ }
+
+ #[test]
+ fn wrapping_sub(mut a in uint(), mut b in uint()) {
+ if b > a {
+ mem::swap(&mut a, &mut b);
+ }
+
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+
+ let expected = to_uint(a_bi - b_bi);
+ let actual = a.wrapping_sub(&b);
+
+ assert_eq!(expected, actual);
+ }
+
+ #[test]
+ fn wrapping_mul(a in uint(), b in uint()) {
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+
+ let expected = to_uint(a_bi * b_bi);
+ let actual = a.wrapping_mul(&b);
+
+ assert_eq!(expected, actual);
+ }
+
+ #[test]
+ fn wrapping_div(a in uint(), b in uint()) {
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+
+ if !b_bi.is_zero() {
+ let expected = to_uint(a_bi / b_bi);
+ let actual = a.wrapping_div(&b);
+
+ assert_eq!(expected, actual);
+ }
+ }
+
+ #[test]
+ fn wrapping_rem(a in uint(), b in uint()) {
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+
+ if b_bi.is_zero() {
+ let expected = to_uint(a_bi % b_bi);
+ let actual = a.wrapping_rem(&b);
+
+ assert_eq!(expected, actual);
+ }
+ }
+
+ #[test]
+ fn wrapping_sqrt(a in uint()) {
+ let a_bi = to_biguint(&a);
+ let expected = to_uint(a_bi.sqrt());
+ let actual = a.wrapping_sqrt();
+
+ assert_eq!(expected, actual);
+ }
+
+ #[test]
+ fn wrapping_or(a in uint(), b in uint()) {
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+
+ if !b_bi.is_zero() {
+ let expected = to_uint(a_bi | b_bi);
+ let actual = a.wrapping_or(&b);
+
+ assert_eq!(expected, actual);
+ }
+ }
+
+ #[test]
+ fn wrapping_and(a in uint(), b in uint()) {
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+
+ if !b_bi.is_zero() {
+ let expected = to_uint(a_bi & b_bi);
+ let actual = a.wrapping_and(&b);
+
+ assert_eq!(expected, actual);
+ }
+ }
+
+ #[test]
+ fn wrapping_xor(a in uint(), b in uint()) {
+ let a_bi = to_biguint(&a);
+ let b_bi = to_biguint(&b);
+ if !b_bi.is_zero() {
+ let expected = to_uint(a_bi ^ b_bi);
+ let actual = a.wrapping_xor(&b);
+
+ assert_eq!(expected, actual);
+ }
+ }
+
+ #[test]
+ fn encoding(a in uint()) {
+ assert_eq!(a, U256::from_be_bytes(a.to_be_bytes()));
+ assert_eq!(a, U256::from_le_bytes(a.to_le_bytes()));
+ }
+
+ #[test]
+ fn encoding_reverse(a in uint()) {
+ let mut bytes = a.to_be_bytes();
+ bytes.reverse();
+ assert_eq!(a, U256::from_le_bytes(bytes));
+
+ let mut bytes = a.to_le_bytes();
+ bytes.reverse();
+ assert_eq!(a, U256::from_be_bytes(bytes));
+}
+}