1 use super::Sign::{self, Minus, NoSign, Plus};
2 use super::{BigInt, ToBigInt};
3
4 use crate::std_alloc::Vec;
5 #[cfg(has_try_from)]
6 use crate::TryFromBigIntError;
7 use crate::{BigUint, ParseBigIntError, ToBigUint};
8
9 use core::cmp::Ordering::{Equal, Greater, Less};
10 #[cfg(has_try_from)]
11 use core::convert::TryFrom;
12 use core::str::{self, FromStr};
13 use num_traits::{FromPrimitive, Num, One, ToPrimitive, Zero};
14
15 impl FromStr for BigInt {
16 type Err = ParseBigIntError;
17
18 #[inline]
from_str(s: &str) -> Result<BigInt, ParseBigIntError>19 fn from_str(s: &str) -> Result<BigInt, ParseBigIntError> {
20 BigInt::from_str_radix(s, 10)
21 }
22 }
23
24 impl Num for BigInt {
25 type FromStrRadixErr = ParseBigIntError;
26
27 /// Creates and initializes a [`BigInt`].
28 #[inline]
from_str_radix(mut s: &str, radix: u32) -> Result<BigInt, ParseBigIntError>29 fn from_str_radix(mut s: &str, radix: u32) -> Result<BigInt, ParseBigIntError> {
30 let sign = if s.starts_with('-') {
31 let tail = &s[1..];
32 if !tail.starts_with('+') {
33 s = tail
34 }
35 Minus
36 } else {
37 Plus
38 };
39 let bu = BigUint::from_str_radix(s, radix)?;
40 Ok(BigInt::from_biguint(sign, bu))
41 }
42 }
43
44 impl ToPrimitive for BigInt {
45 #[inline]
to_i64(&self) -> Option<i64>46 fn to_i64(&self) -> Option<i64> {
47 match self.sign {
48 Plus => self.data.to_i64(),
49 NoSign => Some(0),
50 Minus => {
51 let n = self.data.to_u64()?;
52 let m: u64 = 1 << 63;
53 match n.cmp(&m) {
54 Less => Some(-(n as i64)),
55 Equal => Some(core::i64::MIN),
56 Greater => None,
57 }
58 }
59 }
60 }
61
62 #[inline]
to_i128(&self) -> Option<i128>63 fn to_i128(&self) -> Option<i128> {
64 match self.sign {
65 Plus => self.data.to_i128(),
66 NoSign => Some(0),
67 Minus => {
68 let n = self.data.to_u128()?;
69 let m: u128 = 1 << 127;
70 match n.cmp(&m) {
71 Less => Some(-(n as i128)),
72 Equal => Some(core::i128::MIN),
73 Greater => None,
74 }
75 }
76 }
77 }
78
79 #[inline]
to_u64(&self) -> Option<u64>80 fn to_u64(&self) -> Option<u64> {
81 match self.sign {
82 Plus => self.data.to_u64(),
83 NoSign => Some(0),
84 Minus => None,
85 }
86 }
87
88 #[inline]
to_u128(&self) -> Option<u128>89 fn to_u128(&self) -> Option<u128> {
90 match self.sign {
91 Plus => self.data.to_u128(),
92 NoSign => Some(0),
93 Minus => None,
94 }
95 }
96
97 #[inline]
to_f32(&self) -> Option<f32>98 fn to_f32(&self) -> Option<f32> {
99 let n = self.data.to_f32()?;
100 Some(if self.sign == Minus { -n } else { n })
101 }
102
103 #[inline]
to_f64(&self) -> Option<f64>104 fn to_f64(&self) -> Option<f64> {
105 let n = self.data.to_f64()?;
106 Some(if self.sign == Minus { -n } else { n })
107 }
108 }
109
110 macro_rules! impl_try_from_bigint {
111 ($T:ty, $to_ty:path) => {
112 #[cfg(has_try_from)]
113 impl TryFrom<&BigInt> for $T {
114 type Error = TryFromBigIntError<()>;
115
116 #[inline]
117 fn try_from(value: &BigInt) -> Result<$T, TryFromBigIntError<()>> {
118 $to_ty(value).ok_or(TryFromBigIntError::new(()))
119 }
120 }
121
122 #[cfg(has_try_from)]
123 impl TryFrom<BigInt> for $T {
124 type Error = TryFromBigIntError<BigInt>;
125
126 #[inline]
127 fn try_from(value: BigInt) -> Result<$T, TryFromBigIntError<BigInt>> {
128 <$T>::try_from(&value).map_err(|_| TryFromBigIntError::new(value))
129 }
130 }
131 };
132 }
133
134 impl_try_from_bigint!(u8, ToPrimitive::to_u8);
135 impl_try_from_bigint!(u16, ToPrimitive::to_u16);
136 impl_try_from_bigint!(u32, ToPrimitive::to_u32);
137 impl_try_from_bigint!(u64, ToPrimitive::to_u64);
138 impl_try_from_bigint!(usize, ToPrimitive::to_usize);
139 impl_try_from_bigint!(u128, ToPrimitive::to_u128);
140
141 impl_try_from_bigint!(i8, ToPrimitive::to_i8);
142 impl_try_from_bigint!(i16, ToPrimitive::to_i16);
143 impl_try_from_bigint!(i32, ToPrimitive::to_i32);
144 impl_try_from_bigint!(i64, ToPrimitive::to_i64);
145 impl_try_from_bigint!(isize, ToPrimitive::to_isize);
146 impl_try_from_bigint!(i128, ToPrimitive::to_i128);
147
148 impl FromPrimitive for BigInt {
149 #[inline]
from_i64(n: i64) -> Option<BigInt>150 fn from_i64(n: i64) -> Option<BigInt> {
151 Some(BigInt::from(n))
152 }
153
154 #[inline]
from_i128(n: i128) -> Option<BigInt>155 fn from_i128(n: i128) -> Option<BigInt> {
156 Some(BigInt::from(n))
157 }
158
159 #[inline]
from_u64(n: u64) -> Option<BigInt>160 fn from_u64(n: u64) -> Option<BigInt> {
161 Some(BigInt::from(n))
162 }
163
164 #[inline]
from_u128(n: u128) -> Option<BigInt>165 fn from_u128(n: u128) -> Option<BigInt> {
166 Some(BigInt::from(n))
167 }
168
169 #[inline]
from_f64(n: f64) -> Option<BigInt>170 fn from_f64(n: f64) -> Option<BigInt> {
171 if n >= 0.0 {
172 BigUint::from_f64(n).map(BigInt::from)
173 } else {
174 let x = BigUint::from_f64(-n)?;
175 Some(-BigInt::from(x))
176 }
177 }
178 }
179
180 impl From<i64> for BigInt {
181 #[inline]
from(n: i64) -> Self182 fn from(n: i64) -> Self {
183 if n >= 0 {
184 BigInt::from(n as u64)
185 } else {
186 let u = core::u64::MAX - (n as u64) + 1;
187 BigInt {
188 sign: Minus,
189 data: BigUint::from(u),
190 }
191 }
192 }
193 }
194
195 impl From<i128> for BigInt {
196 #[inline]
from(n: i128) -> Self197 fn from(n: i128) -> Self {
198 if n >= 0 {
199 BigInt::from(n as u128)
200 } else {
201 let u = core::u128::MAX - (n as u128) + 1;
202 BigInt {
203 sign: Minus,
204 data: BigUint::from(u),
205 }
206 }
207 }
208 }
209
210 macro_rules! impl_bigint_from_int {
211 ($T:ty) => {
212 impl From<$T> for BigInt {
213 #[inline]
214 fn from(n: $T) -> Self {
215 BigInt::from(n as i64)
216 }
217 }
218 };
219 }
220
221 impl_bigint_from_int!(i8);
222 impl_bigint_from_int!(i16);
223 impl_bigint_from_int!(i32);
224 impl_bigint_from_int!(isize);
225
226 impl From<u64> for BigInt {
227 #[inline]
from(n: u64) -> Self228 fn from(n: u64) -> Self {
229 if n > 0 {
230 BigInt {
231 sign: Plus,
232 data: BigUint::from(n),
233 }
234 } else {
235 BigInt::zero()
236 }
237 }
238 }
239
240 impl From<u128> for BigInt {
241 #[inline]
from(n: u128) -> Self242 fn from(n: u128) -> Self {
243 if n > 0 {
244 BigInt {
245 sign: Plus,
246 data: BigUint::from(n),
247 }
248 } else {
249 BigInt::zero()
250 }
251 }
252 }
253
254 macro_rules! impl_bigint_from_uint {
255 ($T:ty) => {
256 impl From<$T> for BigInt {
257 #[inline]
258 fn from(n: $T) -> Self {
259 BigInt::from(n as u64)
260 }
261 }
262 };
263 }
264
265 impl_bigint_from_uint!(u8);
266 impl_bigint_from_uint!(u16);
267 impl_bigint_from_uint!(u32);
268 impl_bigint_from_uint!(usize);
269
270 impl From<BigUint> for BigInt {
271 #[inline]
from(n: BigUint) -> Self272 fn from(n: BigUint) -> Self {
273 if n.is_zero() {
274 BigInt::zero()
275 } else {
276 BigInt {
277 sign: Plus,
278 data: n,
279 }
280 }
281 }
282 }
283
284 impl ToBigInt for BigInt {
285 #[inline]
to_bigint(&self) -> Option<BigInt>286 fn to_bigint(&self) -> Option<BigInt> {
287 Some(self.clone())
288 }
289 }
290
291 impl ToBigInt for BigUint {
292 #[inline]
to_bigint(&self) -> Option<BigInt>293 fn to_bigint(&self) -> Option<BigInt> {
294 if self.is_zero() {
295 Some(Zero::zero())
296 } else {
297 Some(BigInt {
298 sign: Plus,
299 data: self.clone(),
300 })
301 }
302 }
303 }
304
305 impl ToBigUint for BigInt {
306 #[inline]
to_biguint(&self) -> Option<BigUint>307 fn to_biguint(&self) -> Option<BigUint> {
308 match self.sign() {
309 Plus => Some(self.data.clone()),
310 NoSign => Some(Zero::zero()),
311 Minus => None,
312 }
313 }
314 }
315
316 #[cfg(has_try_from)]
317 impl TryFrom<&BigInt> for BigUint {
318 type Error = TryFromBigIntError<()>;
319
320 #[inline]
try_from(value: &BigInt) -> Result<BigUint, TryFromBigIntError<()>>321 fn try_from(value: &BigInt) -> Result<BigUint, TryFromBigIntError<()>> {
322 value
323 .to_biguint()
324 .ok_or_else(|| TryFromBigIntError::new(()))
325 }
326 }
327
328 #[cfg(has_try_from)]
329 impl TryFrom<BigInt> for BigUint {
330 type Error = TryFromBigIntError<BigInt>;
331
332 #[inline]
try_from(value: BigInt) -> Result<BigUint, TryFromBigIntError<BigInt>>333 fn try_from(value: BigInt) -> Result<BigUint, TryFromBigIntError<BigInt>> {
334 if value.sign() == Sign::Minus {
335 Err(TryFromBigIntError::new(value))
336 } else {
337 Ok(value.data)
338 }
339 }
340 }
341
342 macro_rules! impl_to_bigint {
343 ($T:ty, $from_ty:path) => {
344 impl ToBigInt for $T {
345 #[inline]
346 fn to_bigint(&self) -> Option<BigInt> {
347 $from_ty(*self)
348 }
349 }
350 };
351 }
352
353 impl_to_bigint!(isize, FromPrimitive::from_isize);
354 impl_to_bigint!(i8, FromPrimitive::from_i8);
355 impl_to_bigint!(i16, FromPrimitive::from_i16);
356 impl_to_bigint!(i32, FromPrimitive::from_i32);
357 impl_to_bigint!(i64, FromPrimitive::from_i64);
358 impl_to_bigint!(i128, FromPrimitive::from_i128);
359
360 impl_to_bigint!(usize, FromPrimitive::from_usize);
361 impl_to_bigint!(u8, FromPrimitive::from_u8);
362 impl_to_bigint!(u16, FromPrimitive::from_u16);
363 impl_to_bigint!(u32, FromPrimitive::from_u32);
364 impl_to_bigint!(u64, FromPrimitive::from_u64);
365 impl_to_bigint!(u128, FromPrimitive::from_u128);
366
367 impl_to_bigint!(f32, FromPrimitive::from_f32);
368 impl_to_bigint!(f64, FromPrimitive::from_f64);
369
370 impl From<bool> for BigInt {
from(x: bool) -> Self371 fn from(x: bool) -> Self {
372 if x {
373 One::one()
374 } else {
375 Zero::zero()
376 }
377 }
378 }
379
380 #[inline]
from_signed_bytes_be(digits: &[u8]) -> BigInt381 pub(super) fn from_signed_bytes_be(digits: &[u8]) -> BigInt {
382 let sign = match digits.first() {
383 Some(v) if *v > 0x7f => Sign::Minus,
384 Some(_) => Sign::Plus,
385 None => return BigInt::zero(),
386 };
387
388 if sign == Sign::Minus {
389 // two's-complement the content to retrieve the magnitude
390 let mut digits = Vec::from(digits);
391 twos_complement_be(&mut digits);
392 BigInt::from_biguint(sign, BigUint::from_bytes_be(&digits))
393 } else {
394 BigInt::from_biguint(sign, BigUint::from_bytes_be(digits))
395 }
396 }
397
398 #[inline]
from_signed_bytes_le(digits: &[u8]) -> BigInt399 pub(super) fn from_signed_bytes_le(digits: &[u8]) -> BigInt {
400 let sign = match digits.last() {
401 Some(v) if *v > 0x7f => Sign::Minus,
402 Some(_) => Sign::Plus,
403 None => return BigInt::zero(),
404 };
405
406 if sign == Sign::Minus {
407 // two's-complement the content to retrieve the magnitude
408 let mut digits = Vec::from(digits);
409 twos_complement_le(&mut digits);
410 BigInt::from_biguint(sign, BigUint::from_bytes_le(&digits))
411 } else {
412 BigInt::from_biguint(sign, BigUint::from_bytes_le(digits))
413 }
414 }
415
416 #[inline]
to_signed_bytes_be(x: &BigInt) -> Vec<u8>417 pub(super) fn to_signed_bytes_be(x: &BigInt) -> Vec<u8> {
418 let mut bytes = x.data.to_bytes_be();
419 let first_byte = bytes.first().cloned().unwrap_or(0);
420 if first_byte > 0x7f
421 && !(first_byte == 0x80 && bytes.iter().skip(1).all(Zero::is_zero) && x.sign == Sign::Minus)
422 {
423 // msb used by magnitude, extend by 1 byte
424 bytes.insert(0, 0);
425 }
426 if x.sign == Sign::Minus {
427 twos_complement_be(&mut bytes);
428 }
429 bytes
430 }
431
432 #[inline]
to_signed_bytes_le(x: &BigInt) -> Vec<u8>433 pub(super) fn to_signed_bytes_le(x: &BigInt) -> Vec<u8> {
434 let mut bytes = x.data.to_bytes_le();
435 let last_byte = bytes.last().cloned().unwrap_or(0);
436 if last_byte > 0x7f
437 && !(last_byte == 0x80
438 && bytes.iter().rev().skip(1).all(Zero::is_zero)
439 && x.sign == Sign::Minus)
440 {
441 // msb used by magnitude, extend by 1 byte
442 bytes.push(0);
443 }
444 if x.sign == Sign::Minus {
445 twos_complement_le(&mut bytes);
446 }
447 bytes
448 }
449
450 /// Perform in-place two's complement of the given binary representation,
451 /// in little-endian byte order.
452 #[inline]
twos_complement_le(digits: &mut [u8])453 fn twos_complement_le(digits: &mut [u8]) {
454 twos_complement(digits)
455 }
456
457 /// Perform in-place two's complement of the given binary representation
458 /// in big-endian byte order.
459 #[inline]
twos_complement_be(digits: &mut [u8])460 fn twos_complement_be(digits: &mut [u8]) {
461 twos_complement(digits.iter_mut().rev())
462 }
463
464 /// Perform in-place two's complement of the given digit iterator
465 /// starting from the least significant byte.
466 #[inline]
twos_complement<'a, I>(digits: I) where I: IntoIterator<Item = &'a mut u8>,467 fn twos_complement<'a, I>(digits: I)
468 where
469 I: IntoIterator<Item = &'a mut u8>,
470 {
471 let mut carry = true;
472 for d in digits {
473 *d = !*d;
474 if carry {
475 *d = d.wrapping_add(1);
476 carry = d.is_zero();
477 }
478 }
479 }
480