Debian Codegraph @

.cargo/vendor/num-bigint/src/lib.rs

raw
1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! Big Integer Types for Rust
12 //!
13 //! * A [`BigUint`] is unsigned and represented as a vector of digits.
14 //! * A [`BigInt`] is signed and is a combination of [`BigUint`] and [`Sign`].
15 //!
16 //! Common numerical operations are overloaded, so we can treat them
17 //! the same way we treat other numbers.
18 //!
19 //! ## Example
20 //!
21 //! ```rust
22 //! # fn main() {
23 //! use num_bigint::BigUint;
24 //! use num_traits::One;
25 //!
26 //! // Calculate large fibonacci numbers.
27 //! fn fib(n: usize) -> BigUint {
28 //! let mut f0 = BigUint::ZERO;
29 //! let mut f1 = BigUint::one();
30 //! for _ in 0..n {
31 //! let f2 = f0 + &f1;
32 //! f0 = f1;
33 //! f1 = f2;
34 //! }
35 //! f0
36 //! }
37 //!
38 //! // This is a very large number.
39 //! println!("fib(1000) = {}", fib(1000));
40 //! # }
41 //! ```
42 //!
43 //! It's easy to generate large random numbers:
44 //!
45 //! ```rust,ignore
46 //! use num_bigint::{ToBigInt, RandBigInt};
47 //!
48 //! let mut rng = rand::thread_rng();
49 //! let a = rng.gen_bigint(1000);
50 //!
51 //! let low = -10000.to_bigint().unwrap();
52 //! let high = 10000.to_bigint().unwrap();
53 //! let b = rng.gen_bigint_range(&low, &high);
54 //!
55 //! // Probably an even larger number.
56 //! println!("{}", a * b);
57 //! ```
58 //!
59 //! See the "Features" section for instructions for enabling random number generation.
60 //!
61 //! ## Features
62 //!
63 //! The `std` crate feature is enabled by default, which enables [`std::error::Error`]
64 //! implementations and some internal use of floating point approximations. This can be disabled by
65 //! depending on `num-bigint` with `default-features = false`. Either way, the `alloc` crate is
66 //! always required for heap allocation of the `BigInt`/`BigUint` digits.
67 //!
68 //! ### Random Generation
69 //!
70 //! `num-bigint` supports the generation of random big integers when the `rand`
71 //! feature is enabled. To enable it include rand as
72 //!
73 //! ```toml
74 //! rand = "0.8"
75 //! num-bigint = { version = "0.4", features = ["rand"] }
76 //! ```
77 //!
78 //! Note that you must use the version of `rand` that `num-bigint` is compatible
79 //! with: `0.8`.
80 //!
81 //! ### Arbitrary Big Integers
82 //!
83 //! `num-bigint` supports `arbitrary` and `quickcheck` features to implement
84 //! [`arbitrary::Arbitrary`] and [`quickcheck::Arbitrary`], respectively, for both `BigInt` and
85 //! `BigUint`. These are useful for fuzzing and other forms of randomized testing.
86 //!
87 //! ### Serialization
88 //!
89 //! The `serde` feature adds implementations of [`Serialize`][serde::Serialize] and
90 //! [`Deserialize`][serde::Deserialize] for both `BigInt` and `BigUint`. Their serialized data is
91 //! generated portably, regardless of platform differences like the internal digit size.
92 //!
93 //!
94 //! ## Compatibility
95 //!
96 //! The `num-bigint` crate is tested for rustc 1.60 and greater.
97
98 #![cfg_attr(docsrs, feature(doc_cfg))]
99 #![doc(html_root_url = "https://docs.rs/num-bigint/0.4")]
100 #![warn(rust_2018_idioms)]
101 #![no_std]
102
103 #[macro_use]
104 extern crate alloc;
105
106 #[cfg(feature = "std")]
107 extern crate std;
108
109 use core::fmt;
110
111 #[macro_use]
112 mod macros;
113
114 mod bigint;
115 mod bigrand;
116 mod biguint;
117
118 #[cfg(target_pointer_width = "32")]
119 type UsizePromotion = u32;
120 #[cfg(target_pointer_width = "64")]
121 type UsizePromotion = u64;
122
123 #[cfg(target_pointer_width = "32")]
124 type IsizePromotion = i32;
125 #[cfg(target_pointer_width = "64")]
126 type IsizePromotion = i64;
127
128 #[derive(Debug, Clone, PartialEq, Eq)]
129 pub struct ParseBigIntError {
130 kind: BigIntErrorKind,
131 }
132
133 #[derive(Debug, Clone, PartialEq, Eq)]
134 enum BigIntErrorKind {
135 Empty,
136 InvalidDigit,
137 }
138
139 impl ParseBigIntError {
140 fn __description(&self) -> &str {
141 use crate::BigIntErrorKind::*;
142 match self.kind {
143 Empty => "cannot parse integer from empty string",
144 InvalidDigit => "invalid digit found in string",
145 }
146 }
147
148 fn empty() -> Self {
149 ParseBigIntError {
150 kind: BigIntErrorKind::Empty,
151 }
152 }
153
154 fn invalid() -> Self {
155 ParseBigIntError {
156 kind: BigIntErrorKind::InvalidDigit,
157 }
158 }
159 }
160
161 impl fmt::Display for ParseBigIntError {
162 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
163 self.__description().fmt(f)
164 }
165 }
166
167 #[cfg(feature = "std")]
168 #[cfg_attr(docsrs, doc(cfg(feature = "std")))]
169 impl std::error::Error for ParseBigIntError {
170 fn description(&self) -> &str {
171 self.__description()
172 }
173 }
174
175 /// The error type returned when a checked conversion regarding big integer fails.
176 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
177 pub struct TryFromBigIntError<T> {
178 original: T,
179 }
180
181 impl<T> TryFromBigIntError<T> {
182 fn new(original: T) -> Self {
183 TryFromBigIntError { original }
184 }
185
186 fn __description(&self) -> &str {
187 "out of range conversion regarding big integer attempted"
188 }
189
190 /// Extract the original value, if available. The value will be available
191 /// if the type before conversion was either [`BigInt`] or [`BigUint`].
192 pub fn into_original(self) -> T {
193 self.original
194 }
195 }
196
197 #[cfg(feature = "std")]
198 #[cfg_attr(docsrs, doc(cfg(feature = "std")))]
199 impl<T> std::error::Error for TryFromBigIntError<T>
200 where
201 T: fmt::Debug,
202 {
203 fn description(&self) -> &str {
204 self.__description()
205 }
206 }
207
208 impl<T> fmt::Display for TryFromBigIntError<T> {
209 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
210 self.__description().fmt(f)
211 }
212 }
213
214 pub use crate::biguint::BigUint;
215 pub use crate::biguint::ToBigUint;
216 pub use crate::biguint::U32Digits;
217 pub use crate::biguint::U64Digits;
218
219 pub use crate::bigint::BigInt;
220 pub use crate::bigint::Sign;
221 pub use crate::bigint::ToBigInt;
222
223 #[cfg(feature = "rand")]
224 #[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
225 pub use crate::bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint};
226
227 mod big_digit {
228 // A [`BigDigit`] is a [`BigUint`]'s composing element.
229 cfg_digit!(
230 pub(crate) type BigDigit = u32;
231 pub(crate) type BigDigit = u64;
232 );
233
234 // A [`DoubleBigDigit`] is the internal type used to do the computations. Its
235 // size is the double of the size of [`BigDigit`].
236 cfg_digit!(
237 pub(crate) type DoubleBigDigit = u64;
238 pub(crate) type DoubleBigDigit = u128;
239 );
240
241 pub(crate) const BITS: u8 = BigDigit::BITS as u8;
242 pub(crate) const HALF_BITS: u8 = BITS / 2;
243 pub(crate) const HALF: BigDigit = (1 << HALF_BITS) - 1;
244
245 pub(crate) const MAX: BigDigit = BigDigit::MAX;
246 const LO_MASK: DoubleBigDigit = MAX as DoubleBigDigit;
247
248 #[inline]
249 fn get_hi(n: DoubleBigDigit) -> BigDigit {
250 (n >> BITS) as BigDigit
251 }
252 #[inline]
253 fn get_lo(n: DoubleBigDigit) -> BigDigit {
254 (n & LO_MASK) as BigDigit
255 }
256
257 /// Split one [`DoubleBigDigit`] into two [`BigDigit`]s.
258 #[inline]
259 pub(crate) fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
260 (get_hi(n), get_lo(n))
261 }
262
263 /// Join two [`BigDigit`]s into one [`DoubleBigDigit`].
264 #[inline]
265 pub(crate) fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
266 DoubleBigDigit::from(lo) | (DoubleBigDigit::from(hi) << BITS)
267 }
268 }