Skip to main content

amplify_num/
bigint.rs

1// SPDX-License-Identifier: Apache-2.0
2//
3// Written in 2014 by
4//     Andrew Poelstra <apoelstra@wpsoftware.net>
5// Refactored, fixed & improved in 2021-2026 by
6//     Dr. Maxim Orlovsky <orlovsky@ubideco.org>
7//
8// Copyright 2024-2026 Laboratories for Ubiquitous and Deterministic Computing,
9// Institute for Distributed and Cognitive Computing (InDCS), Switzerland.
10// All rights reserved.
11//
12// Copyright (C) 2021-2026 Dr Maxim Orlovsky.
13// All rights reserved.
14//
15// Licensed under the Apache License, Version 2.0 (the "License"); you may not
16// use this file except in compliance with the License. You may obtain a copy of
17// the License at <http://www.apache.org/licenses/LICENSE-2.0>
18//
19// Unless required by applicable law or agreed to in writing, software
20// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
21// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
22// License for the specific language governing permissions and limitations under
23// the License.
24
25use crate::error::{DivError, ParseLengthError};
26
27macro_rules! construct_bigint {
28    ($name:ident, $n_words:expr) => {
29        /// Large integer type
30        ///
31        /// The type is composed of little-endian ordered 64-bit words, which represents
32        /// its inner representation.
33        #[allow(non_camel_case_types)]
34        #[derive(Copy, Clone, PartialEq, Eq, Hash, Default)]
35        pub struct $name([u64; $n_words]);
36
37        impl $name {
38            #[inline]
39            /// Converts the object to a raw pointer
40            pub fn as_ptr(&self) -> *const u64 {
41                let &$name(ref dat) = self;
42                dat.as_ptr()
43            }
44
45            #[inline]
46            /// Converts the object to a mutable raw pointer
47            pub fn as_mut_ptr(&mut self) -> *mut u64 {
48                let &mut $name(ref mut dat) = self;
49                dat.as_mut_ptr()
50            }
51
52            #[inline]
53            /// Returns the underlying array of words constituting large integer
54            pub const fn as_inner(&self) -> &[u64; $n_words] { &self.0 }
55
56            #[inline]
57            /// Returns the underlying array of words constituting large integer
58            pub const fn into_inner(self) -> [u64; $n_words] { self.0 }
59
60            #[inline]
61            /// Constructs integer type from the underlying array of words.
62            pub const fn from_inner(array: [u64; $n_words]) -> Self { Self(array) }
63        }
64
65        impl $name {
66            /// Zero value
67            pub const ZERO: $name = $name([0u64; $n_words]);
68
69            /// Value for `1`
70            pub const ONE: $name = $name({
71                let mut one = [0u64; $n_words];
72                one[0] = 1u64;
73                one
74            });
75
76            /// Bit dimension
77            pub const BITS: u32 = $n_words * 64;
78
79            /// Length of the integer in bytes
80            pub const BYTES: u8 = $n_words * 8;
81
82            /// Length of the inner representation in 64-bit words
83            pub const INNER_LEN: u8 = $n_words;
84
85            /// Returns whether specific bit number is set to `1` or not
86            #[inline]
87            pub const fn bit(&self, index: usize) -> bool {
88                let &$name(ref arr) = self;
89                arr[index / 64] & (1 << (index % 64)) != 0
90            }
91
92            /// Returns lower 32 bits of the number as `u32`
93            #[inline]
94            pub const fn low_u32(&self) -> u32 {
95                let &$name(ref arr) = self;
96                (arr[0] & u32::MAX as u64) as u32
97            }
98
99            /// Returns lower 64 bits of the number as `u32`
100            #[inline]
101            pub const fn low_u64(&self) -> u64 {
102                let &$name(ref arr) = self;
103                arr[0] as u64
104            }
105
106            /// Returns the number of leading ones in the binary representation of
107            /// `self`.
108            #[inline]
109            pub fn leading_ones(&self) -> u32 {
110                for i in 0..$n_words {
111                    let leading_ones = (!self[$n_words - i - 1]).leading_zeros();
112                    if leading_ones != 64 {
113                        return 64 * i as u32 + leading_ones;
114                    }
115                }
116                64 * $n_words
117            }
118
119            /// Returns the number of leading zeros in the binary representation of
120            /// `self`.
121            #[inline]
122            pub fn leading_zeros(&self) -> u32 {
123                for i in 0..$n_words {
124                    let leading_zeros = self[$n_words - i - 1].leading_zeros();
125                    if leading_zeros != 64 {
126                        return 64 * i as u32 + leading_zeros;
127                    }
128                }
129                64 * $n_words
130            }
131
132            /// Returns the number of trailing ones in the binary representation of
133            /// `self`.
134            #[inline]
135            pub fn trailing_ones(&self) -> u32 {
136                for i in 0..$n_words {
137                    let trailing_ones = (!self[i]).trailing_zeros();
138                    if trailing_ones != 64 {
139                        return 64 * i as u32 + trailing_ones;
140                    }
141                }
142                64 * $n_words
143            }
144
145            /// Returns the number of trailing zeros in the binary representation of
146            /// `self`.
147            #[inline]
148            pub fn trailing_zeros(&self) -> u32 {
149                for i in 0..$n_words {
150                    let trailing_zeros = self[i].trailing_zeros();
151                    if trailing_zeros != 64 {
152                        return 64 * i as u32 + trailing_zeros;
153                    }
154                }
155                64 * $n_words
156            }
157
158            #[inline]
159            pub fn is_zero(&self) -> bool { self[..] == [0; $n_words] }
160
161            #[inline]
162            pub fn is_positive(&self) -> bool { !self.is_negative() && !self.is_zero() }
163
164            #[inline]
165            pub fn abs(self) -> $name {
166                if !self.is_negative() {
167                    return self;
168                }
169                (!self).wrapping_add($name::ONE)
170            }
171
172            /// Creates the integer value from a byte array using big-endian
173            /// encoding
174            pub fn from_be_bytes(bytes: [u8; $n_words * 8]) -> $name {
175                Self::_from_be_slice(&bytes)
176            }
177
178            /// Creates the integer value from a byte slice using big-endian
179            /// encoding
180            pub fn from_be_slice(bytes: &[u8]) -> Result<$name, ParseLengthError> {
181                if bytes.len() != $n_words * 8 {
182                    Err(ParseLengthError {
183                        actual: bytes.len(),
184                        expected: $n_words * 8,
185                    })
186                } else {
187                    Ok(Self::_from_be_slice(bytes))
188                }
189            }
190
191            /// Creates the integer value from a byte array using little-endian
192            /// encoding
193            pub fn from_le_bytes(bytes: [u8; $n_words * 8]) -> $name {
194                Self::_from_le_slice(&bytes)
195            }
196
197            /// Creates the integer value from a byte slice using little-endian
198            /// encoding
199            pub fn from_le_slice(bytes: &[u8]) -> Result<$name, ParseLengthError> {
200                if bytes.len() != $n_words * 8 {
201                    Err(ParseLengthError {
202                        actual: bytes.len(),
203                        expected: $n_words * 8,
204                    })
205                } else {
206                    Ok(Self::_from_le_slice(bytes))
207                }
208            }
209
210            fn _from_be_slice(bytes: &[u8]) -> $name {
211                let mut slice = [0u64; $n_words];
212                slice
213                    .iter_mut()
214                    .rev()
215                    .zip(bytes.chunks(8).into_iter().map(|s| {
216                        let mut b = [0u8; 8];
217                        b.copy_from_slice(s);
218                        b
219                    }))
220                    .for_each(|(word, bytes)| *word = u64::from_be_bytes(bytes));
221                $name(slice)
222            }
223
224            fn _from_le_slice(bytes: &[u8]) -> $name {
225                let mut slice = [0u64; $n_words];
226                slice
227                    .iter_mut()
228                    .zip(bytes.chunks(8).into_iter().map(|s| {
229                        let mut b = [0u8; 8];
230                        b.copy_from_slice(s);
231                        b
232                    }))
233                    .for_each(|(word, bytes)| *word = u64::from_le_bytes(bytes));
234                $name(slice)
235            }
236
237            /// Convert the integer into a byte array using big-endian encoding
238            pub fn to_be_bytes(self) -> [u8; $n_words * 8] {
239                let mut res = [0; $n_words * 8];
240                for i in 0..$n_words {
241                    let start = i * 8;
242                    res[start..start + 8]
243                        .copy_from_slice(&self.0[$n_words - (i + 1)].to_be_bytes());
244                }
245                res
246            }
247
248            /// Convert a integer into a byte array using little-endian encoding
249            pub fn to_le_bytes(self) -> [u8; $n_words * 8] {
250                let mut res = [0; $n_words * 8];
251                for i in 0..$n_words {
252                    let start = i * 8;
253                    res[start..start + 8].copy_from_slice(&self.0[i].to_le_bytes());
254                }
255                res
256            }
257
258            // divmod like operation, returns (quotient, remainder)
259            #[inline]
260            fn div_rem(self, other: Self) -> Result<(Self, Self), DivError> {
261                // Check for division by 0
262                if other.is_zero() {
263                    return Err(DivError::ZeroDiv);
264                }
265                if other.is_negative() && self == Self::MIN && other == Self::ONE.wrapping_neg() {
266                    return Err(DivError::Overflow);
267                }
268                let mut me = self.abs();
269                let mut you = other.abs();
270                let mut ret = [0u64; $n_words];
271                if self.is_negative() == other.is_negative() && me < you {
272                    return Ok(($name(ret), self));
273                }
274
275                let shift = me.bits_required() - you.bits_required();
276                you <<= shift;
277                for i in (0..=shift).rev() {
278                    if me >= you {
279                        ret[i / 64] |= 1 << (i % 64);
280                        me -= you;
281                    }
282                    you >>= 1;
283                }
284
285                Ok((
286                    if self.is_negative() == other.is_negative() {
287                        Self(ret)
288                    } else {
289                        -Self(ret)
290                    },
291                    if self.is_negative() { -me } else { me },
292                ))
293            }
294
295            #[inline]
296            fn div_rem_euclid(self, other: Self) -> Result<(Self, Self), DivError> {
297                self.div_rem(other).map(|(q, r)| {
298                    (
299                        match (r.is_negative(), other.is_positive()) {
300                            (true, true) => q.wrapping_sub(Self::ONE),
301                            (true, false) => q.wrapping_add(Self::ONE),
302                            _ => q,
303                        },
304                        match (r.is_negative(), other.is_positive()) {
305                            (true, true) => r.wrapping_add(other),
306                            (true, false) => r.wrapping_sub(other),
307                            _ => r,
308                        },
309                    )
310                })
311            }
312        }
313
314        impl From<bool> for $name {
315            fn from(init: bool) -> $name {
316                let mut ret = [0; $n_words];
317                if init {
318                    ret[0] = 1;
319                }
320                $name(ret)
321            }
322        }
323
324        impl From<u8> for $name {
325            fn from(init: u8) -> $name {
326                let mut ret = [0; $n_words];
327                ret[0] = init as u64;
328                $name(ret)
329            }
330        }
331
332        impl From<u16> for $name {
333            fn from(init: u16) -> $name {
334                let mut ret = [0; $n_words];
335                ret[0] = init as u64;
336                $name(ret)
337            }
338        }
339
340        impl From<u32> for $name {
341            fn from(init: u32) -> $name {
342                let mut ret = [0; $n_words];
343                ret[0] = init as u64;
344                $name(ret)
345            }
346        }
347
348        impl From<u64> for $name {
349            fn from(init: u64) -> $name {
350                let mut ret = [0; $n_words];
351                ret[0] = init;
352                $name(ret)
353            }
354        }
355
356        impl From<u128> for $name {
357            fn from(init: u128) -> $name {
358                let mut ret = [0; $n_words * 8];
359                for (pos, byte) in init.to_le_bytes().iter().enumerate() {
360                    ret[pos] = *byte;
361                }
362                $name::from_le_bytes(ret)
363            }
364        }
365
366        impl<'a> ::core::convert::TryFrom<&'a [u64]> for $name {
367            type Error = $crate::error::ParseLengthError;
368            fn try_from(data: &'a [u64]) -> Result<$name, Self::Error> {
369                if data.len() != $n_words {
370                    Err($crate::error::ParseLengthError {
371                        actual: data.len(),
372                        expected: $n_words,
373                    })
374                } else {
375                    let mut bytes = [0u64; $n_words];
376                    bytes.copy_from_slice(data);
377                    Ok(Self::from_inner(bytes))
378                }
379            }
380        }
381        impl ::core::ops::Index<usize> for $name {
382            type Output = u64;
383
384            #[inline]
385            fn index(&self, index: usize) -> &u64 { &self.0[index] }
386        }
387
388        impl ::core::ops::Index<::core::ops::Range<usize>> for $name {
389            type Output = [u64];
390
391            #[inline]
392            fn index(&self, index: ::core::ops::Range<usize>) -> &[u64] { &self.0[index] }
393        }
394
395        impl ::core::ops::Index<::core::ops::RangeTo<usize>> for $name {
396            type Output = [u64];
397
398            #[inline]
399            fn index(&self, index: ::core::ops::RangeTo<usize>) -> &[u64] { &self.0[index] }
400        }
401
402        impl ::core::ops::Index<::core::ops::RangeFrom<usize>> for $name {
403            type Output = [u64];
404
405            #[inline]
406            fn index(&self, index: ::core::ops::RangeFrom<usize>) -> &[u64] { &self.0[index] }
407        }
408
409        impl ::core::ops::Index<::core::ops::RangeFull> for $name {
410            type Output = [u64];
411
412            #[inline]
413            fn index(&self, _: ::core::ops::RangeFull) -> &[u64] { &self.0[..] }
414        }
415
416        impl PartialOrd for $name {
417            #[inline]
418            fn partial_cmp(&self, other: &$name) -> Option<::core::cmp::Ordering> {
419                Some(self.cmp(&other))
420            }
421        }
422
423        impl Ord for $name {
424            #[inline]
425            fn cmp(&self, other: &$name) -> ::core::cmp::Ordering {
426                // We need to manually implement ordering because the words in our array
427                // are in little-endian order, i.e. the most significant word is last in
428                // the array, and the auto derive for array Ord compares the elements
429                // from first to last.
430                for i in 0..$n_words {
431                    let self_word = self[$n_words - 1 - i];
432                    let other_word = other[$n_words - 1 - i];
433
434                    // If this is a signed type, start with signed comparison on the
435                    // most-significant word, then continue with unsigned comparisons on
436                    // the rest of the words.
437                    let res = if i == 0 && Self::IS_SIGNED_TYPE {
438                        (self_word as i64).cmp(&(other_word as i64))
439                    } else {
440                        self_word.cmp(&other_word)
441                    };
442
443                    if res != ::core::cmp::Ordering::Equal {
444                        return res;
445                    }
446                }
447                ::core::cmp::Ordering::Equal
448            }
449        }
450
451        impl ::core::ops::Neg for $name {
452            type Output = Self;
453            fn neg(self) -> Self::Output {
454                assert!(
455                    $name::MIN != $name([u64::MAX; $n_words]),
456                    "attempt to negate unsigned number"
457                );
458                assert!(
459                    self != $name::MIN,
460                    "attempt to negate the minimum value, which would overflow"
461                );
462                (!self).wrapping_add($name::ONE)
463            }
464        }
465
466        impl $name {
467            /// Checked integer addition. Computes `self + rhs`, returning `None` if
468            /// overflow occurred.
469            pub fn checked_add<T>(self, other: T) -> Option<$name>
470            where T: Into<$name> {
471                let (res, flag) = self.overflowing_add(other);
472                if flag { None } else { Some(res) }
473            }
474
475            /// Saturating integer addition. Computes `self + rhs`, saturating at the
476            /// numeric bounds instead of overflowing.
477            pub fn saturating_add<T>(self, other: T) -> $name
478            where T: Into<$name> {
479                let (res, flag) = self.overflowing_add(other);
480                if flag { Self::MAX } else { res }
481            }
482
483            /// Calculates `self + rhs`
484            ///
485            /// Returns a tuple of the addition along with a boolean indicating whether
486            /// an arithmetic overflow would occur. If an overflow would have occurred
487            /// then the wrapped value is returned.
488            pub fn overflowing_add<T>(self, other: T) -> ($name, bool)
489            where T: Into<$name> {
490                let $name(ref me) = self;
491                let other = other.into();
492                let $name(ref you) = other;
493                let mut ret = [0u64; $n_words];
494                let mut carry = 0u64;
495                for i in 0..$n_words {
496                    let (res, flag) = me[i].overflowing_add(carry);
497                    carry = flag as u64;
498                    let (res, flag) = res.overflowing_add(you[i]);
499                    carry += flag as u64;
500                    ret[i] = res;
501                }
502                let ret = Self(ret);
503                let overflow = if !Self::IS_SIGNED_TYPE {
504                    carry > 0
505                } else {
506                    self != Self::MIN &&
507                        other != Self::MIN &&
508                        (self.is_negative() == other.is_negative()) &&
509                        (self.is_negative() != ret.is_negative())
510                };
511                (ret, overflow)
512            }
513
514            /// Wrapping (modular) addition. Computes `self + rhs`, wrapping around at
515            /// the boundary of the type.
516            pub fn wrapping_add<T>(self, other: T) -> $name
517            where T: Into<$name> {
518                self.overflowing_add(other).0
519            }
520
521            /// Checked integer subtraction. Computes `self - rhs`, returning `None` if
522            /// overflow occurred.
523            pub fn checked_sub<T>(self, other: T) -> Option<$name>
524            where T: Into<$name> {
525                let (res, flag) = self.overflowing_sub(other);
526                if flag { None } else { Some(res) }
527            }
528
529            /// Saturating integer subtraction. Computes `self - rhs`, saturating at the
530            /// numeric bounds instead of overflowing.
531            pub fn saturating_sub<T>(self, other: T) -> $name
532            where T: Into<$name> {
533                let (res, flag) = self.overflowing_sub(other);
534                if flag { Self::MAX } else { res }
535            }
536
537            /// Calculates `self - rhs`
538            ///
539            /// Returns a tuple of the subtraction along with a boolean indicating
540            /// whether an arithmetic overflow would occur. If an overflow would
541            /// have occurred then the wrapped value is returned.
542            pub fn overflowing_sub<T>(self, other: T) -> ($name, bool)
543            where T: Into<$name> {
544                let other = other.into();
545                if !Self::IS_SIGNED_TYPE {
546                    (self.wrapping_add(!other).wrapping_add($name::ONE), self < other)
547                } else {
548                    self.overflowing_add((!other).wrapping_add($name::ONE))
549                }
550            }
551
552            /// Wrapping (modular) subtraction. Computes `self - rhs`, wrapping around
553            /// at the boundary of the type.
554            pub fn wrapping_sub<T>(self, other: T) -> $name
555            where T: Into<$name> {
556                self.overflowing_sub(other).0
557            }
558
559            /// Checked integer multiplication. Computes `self * rhs`, returning `None`
560            /// if overflow occurred.
561            pub fn checked_mul<T>(self, other: T) -> Option<$name>
562            where T: Into<$name> {
563                let (res, flag) = self.overflowing_mul(other);
564                if flag { None } else { Some(res) }
565            }
566
567            /// Saturating integer multiplication. Computes `self * rhs`, saturating at
568            /// the numeric bounds instead of overflowing.
569            pub fn saturating_mul<T>(self, other: T) -> $name
570            where T: Into<$name> {
571                let (res, flag) = self.overflowing_mul(other);
572                if flag { Self::MAX } else { res }
573            }
574
575            /// Wrapping (modular) multiplication. Computes `self * rhs`, wrapping
576            /// around at the boundary of the type.
577            pub fn wrapping_mul<T>(self, other: T) -> $name
578            where T: Into<$name> {
579                self.overflowing_mul(other).0
580            }
581
582            /// Calculates `self / rhs`
583            ///
584            /// Returns a tuple of the divisor along with a boolean indicating
585            /// whether an arithmetic overflow would occur. If an overflow would
586            /// have occurred then the wrapped value is returned.
587            pub fn overflowing_div<T>(self, other: T) -> ($name, bool)
588            where T: Into<$name> {
589                let rhs = other.into();
590                match self.div_rem(rhs) {
591                    Err(DivError::Overflow) => (Self::MIN, true),
592                    res => (res.expect("Error occurred during bigint division").0, false),
593                }
594            }
595
596            /// Wrapping (modular) division. Calculates `self / rhs`,
597            /// wrapping around at the boundary of the type.
598            ///
599            /// The only case where such wrapping can occur is when one divides
600            /// `MIN / -1` on a signed type (where MIN is the negative minimal value for
601            /// the type); this is equivalent to -MIN, a positive value that is
602            /// too large to represent in the type.
603            /// In such a case, this function returns MIN itself.
604            pub fn wrapping_div<T>(self, other: T) -> $name
605            where T: Into<$name> {
606                self.overflowing_div(other.into()).0
607            }
608
609            /// Checked integer division. Computes `self / rhs`,
610            /// returning None if `rhs == 0` or the division results in overflow.
611            pub fn checked_div<T>(self, other: T) -> Option<$name>
612            where T: Into<$name> {
613                self.div_rem(other.into()).ok().map(|(q, _)| q)
614            }
615
616            /// Saturating integer division. Computes `self / rhs`,
617            /// saturating at the numeric bounds instead of overflowing.
618            pub fn saturating_div<T>(self, other: T) -> $name
619            where T: Into<$name> {
620                let rhs = other.into();
621                match self.div_rem(rhs) {
622                    Err(DivError::Overflow) => Self::MAX,
623                    res => res.expect("Error occurred during bigint division").0,
624                }
625            }
626
627            /// Calculates the remainder when `self` is divided by `rhs`.
628            ///
629            /// Returns a tuple of the remainder after dividing along with a boolean
630            /// indicating whether an arithmetic overflow would occur.
631            /// If an overflow would occur then 0 is returned.
632            pub fn overflowing_rem<T>(self, other: T) -> ($name, bool)
633            where T: Into<$name> {
634                let rhs = other.into();
635                match self.div_rem(rhs) {
636                    Err(DivError::Overflow) => (Self::ZERO, true),
637                    res => (res.expect("Error occurred during bigint division").1, false),
638                }
639            }
640
641            /// Wrapping (modular) remainder.
642            /// Computes self % rhs, wrapping around at the boundary of the type.
643            ///
644            /// Such wrap-around never actually occurs mathematically;
645            /// implementation artifacts make x % y invalid for MIN / -1
646            /// on a signed type (where MIN is the negative minimal value).
647            /// In such a case, this function returns 0.
648            pub fn wrapping_rem<T>(self, other: T) -> $name
649            where T: Into<$name> {
650                self.overflowing_rem(other.into()).0
651            }
652
653            /// Checked integer remainder. Computes `self % rhs`,
654            /// returning None if `rhs == 0` or the division results in overflow.
655            pub fn checked_rem<T>(self, other: T) -> Option<$name>
656            where T: Into<$name> {
657                self.div_rem(other.into()).ok().map(|(_, r)| r)
658            }
659
660            /// Calculates the quotient of Euclidean division of `self` by `rhs`.
661            ///
662            /// This computes the integer `q` such that `self = q * rhs + r`,
663            /// with `r = self.rem_euclid(rhs)` and `0 <= r < abs(rhs)`.
664            ///
665            /// In other words, the result is `self / rhs` rounded to the integer `q`
666            /// such that `self >= q * rhs`. If `self > 0`,
667            /// this is equal to round towards zero (the default in Rust);
668            /// if `self < 0`, this is equal to round towards +/- infinity.
669            pub fn div_euclid<T>(self, other: T) -> $name
670            where T: Into<$name> {
671                self.div_rem_euclid(other.into())
672                    .expect("Error occurred during bigint division")
673                    .0
674            }
675
676            /// Calculates the quotient of Euclidean division `self.div_euclid(rhs)`.
677            ///
678            /// Returns a tuple of the divisor along with a boolean indicating
679            /// whether an arithmetic overflow would occur.
680            /// If an overflow would occur then `self` is returned.
681            pub fn overflowing_div_euclid<T>(self, other: T) -> ($name, bool)
682            where T: Into<$name> {
683                match self.div_rem_euclid(other.into()) {
684                    Err(DivError::Overflow) => (Self::MIN, true),
685                    res => (res.expect("Error occurred during bigint division").0, false),
686                }
687            }
688
689            /// Wrapping Euclidean division. Computes `self.div_euclid(rhs)`,
690            /// wrapping around at the boundary of the type.
691            ///
692            /// Wrapping will only occur in `MIN / -1` on a signed type
693            /// (where MIN is the negative minimal value for the type).
694            /// This is equivalent to `-MIN`, a positive value
695            /// that is too large to represent in the type.
696            /// In this case, this method returns `MIN` itself.
697            pub fn wrapping_div_euclid<T>(self, other: T) -> $name
698            where T: Into<$name> {
699                self.overflowing_div_euclid(other.into()).0
700            }
701
702            /// Checked Euclidean division. Computes `self.div_euclid(rhs)`,
703            /// returning None if `rhs == 0` or the division results in overflow.
704            pub fn checked_div_euclid<T>(self, other: T) -> Option<$name>
705            where T: Into<$name> {
706                self.div_rem_euclid(other.into()).ok().map(|(q, _)| q)
707            }
708
709            /// Calculates the least nonnegative remainder of `self (mod rhs)`.
710            ///
711            /// This is done as if by the Euclidean division algorithm –
712            /// given `r = self.rem_euclid(rhs)`, `self = rhs * self.div_euclid(rhs) +
713            /// r`, and `0 <= r < abs(rhs)`.
714            pub fn rem_euclid<T>(self, other: T) -> $name
715            where T: Into<$name> {
716                self.div_rem_euclid(other.into())
717                    .expect("Error occurred during bigint division")
718                    .1
719            }
720
721            /// Overflowing Euclidean remainder. Calculates `self.rem_euclid(rhs)`.
722            ///
723            /// Returns a tuple of the remainder after dividing along with a boolean
724            /// indicating whether an arithmetic overflow would occur.
725            /// If an overflow would occur then 0 is returned.
726            pub fn overflowing_rem_euclid<T>(self, other: T) -> ($name, bool)
727            where T: Into<$name> {
728                match self.div_rem_euclid(other.into()) {
729                    Err(DivError::Overflow) => (Self::ZERO, true),
730                    res => (res.expect("Error occurred during bigint division").1, false),
731                }
732            }
733
734            /// Wrapping Euclidean remainder. Computes `self.rem_euclid(rhs)`,
735            /// wrapping around at the boundary of the type.
736            ///
737            /// Wrapping will only occur in `MIN % -1` on a signed type
738            /// (where `MIN` is the negative minimal value for the type).
739            /// In this case, this method returns 0.
740            pub fn wrapping_rem_euclid<T>(self, other: T) -> $name
741            where T: Into<$name> {
742                self.overflowing_rem_euclid(other.into()).0
743            }
744
745            /// Checked Euclidean remainder. Computes `self.rem_euclid(rhs)`,
746            /// returning None if `rhs == 0` or the division results in overflow.
747            pub fn checked_rem_euclid<T>(self, other: T) -> Option<$name>
748            where T: Into<$name> {
749                self.div_rem_euclid(other.into()).ok().map(|(_, r)| r)
750            }
751
752            /// Checked shift left. Computes self << rhs,
753            /// returning None if rhs is larger than or equal to the number of bits in
754            /// self.
755            pub fn checked_shl(self, rhs: u32) -> Option<$name> {
756                match rhs < Self::BITS {
757                    true => Some(self << (rhs as usize)),
758                    false => None,
759                }
760            }
761
762            /// Checked shift right. Computes self >> rhs,
763            /// returning None if rhs is larger than or equal to the number of bits in
764            /// self.
765            pub fn checked_shr(self, rhs: u32) -> Option<$name> {
766                match rhs < Self::BITS {
767                    true => Some(self >> (rhs as usize)),
768                    false => None,
769                }
770            }
771
772            /// Wrapping (modular) negation. Computes -self,
773            /// wrapping around at the boundary of the type.
774            /// Since unsigned types do not have negative equivalents
775            /// all applications of this function will wrap (except for -0).
776            /// For values smaller than the corresponding signed type's maximum
777            /// the result is the same as casting the corresponding signed value.
778            /// Any larger values are equivalent to MAX + 1 - (val - MAX - 1)
779            /// where MAX is the corresponding signed type's maximum.
780            pub fn wrapping_neg(self) -> $name { (!self).wrapping_add(Self::ONE) }
781        }
782
783        impl<T> ::core::ops::Add<T> for $name
784        where T: Into<$name>
785        {
786            type Output = $name;
787
788            fn add(self, other: T) -> $name {
789                let (res, flag) = self.overflowing_add(other);
790                assert!(!flag, "attempt to add with overflow");
791                res
792            }
793        }
794        impl<T> ::core::ops::AddAssign<T> for $name
795        where T: Into<$name>
796        {
797            #[inline]
798            fn add_assign(&mut self, rhs: T) { self.0 = (*self + rhs).0 }
799        }
800
801        impl<T> ::core::ops::Sub<T> for $name
802        where T: Into<$name>
803        {
804            type Output = $name;
805
806            #[inline]
807            fn sub(self, other: T) -> $name {
808                let (res, flag) = self.overflowing_sub(other);
809                assert!(!flag, "attempt to subtract with overflow");
810                res
811            }
812        }
813        impl<T> ::core::ops::SubAssign<T> for $name
814        where T: Into<$name>
815        {
816            #[inline]
817            fn sub_assign(&mut self, rhs: T) { self.0 = (*self - rhs).0 }
818        }
819
820        impl<T> ::core::ops::Mul<T> for $name
821        where T: Into<$name>
822        {
823            type Output = $name;
824
825            fn mul(self, other: T) -> $name {
826                let (res, flag) = self.overflowing_mul(other);
827                assert!(!flag, "attempt to mul with overflow");
828                res
829            }
830        }
831        impl<T> ::core::ops::MulAssign<T> for $name
832        where T: Into<$name>
833        {
834            #[inline]
835            fn mul_assign(&mut self, rhs: T) { self.0 = (*self * rhs).0 }
836        }
837
838        impl<T> ::core::ops::Div<T> for $name
839        where T: Into<$name>
840        {
841            type Output = $name;
842
843            fn div(self, other: T) -> $name {
844                self.div_rem(other.into())
845                    .expect("Error occurred during bigint division")
846                    .0
847            }
848        }
849        impl<T> ::core::ops::DivAssign<T> for $name
850        where T: Into<$name>
851        {
852            #[inline]
853            fn div_assign(&mut self, rhs: T) { self.0 = (*self / rhs).0 }
854        }
855
856        impl<T> ::core::ops::Rem<T> for $name
857        where T: Into<$name>
858        {
859            type Output = $name;
860
861            fn rem(self, other: T) -> $name {
862                self.div_rem(other.into())
863                    .expect("Error occurred during bigint division")
864                    .1
865            }
866        }
867        impl<T> ::core::ops::RemAssign<T> for $name
868        where T: Into<$name>
869        {
870            #[inline]
871            fn rem_assign(&mut self, rhs: T) { self.0 = (*self % rhs).0 }
872        }
873
874        impl<T> ::core::ops::BitAnd<T> for $name
875        where T: Into<$name>
876        {
877            type Output = $name;
878
879            #[inline]
880            fn bitand(self, other: T) -> $name {
881                let $name(ref arr1) = self;
882                let $name(ref arr2) = other.into();
883                let mut ret = [0u64; $n_words];
884                for i in 0..$n_words {
885                    ret[i] = arr1[i] & arr2[i];
886                }
887                $name(ret)
888            }
889        }
890        impl<T> ::core::ops::BitAndAssign<T> for $name
891        where T: Into<$name>
892        {
893            #[inline]
894            fn bitand_assign(&mut self, rhs: T) { self.0 = (*self & rhs).0 }
895        }
896
897        impl<T> ::core::ops::BitXor<T> for $name
898        where T: Into<$name>
899        {
900            type Output = $name;
901
902            #[inline]
903            fn bitxor(self, other: T) -> $name {
904                let $name(ref arr1) = self;
905                let $name(ref arr2) = other.into();
906                let mut ret = [0u64; $n_words];
907                for i in 0..$n_words {
908                    ret[i] = arr1[i] ^ arr2[i];
909                }
910                $name(ret)
911            }
912        }
913        impl<T> ::core::ops::BitXorAssign<T> for $name
914        where T: Into<$name>
915        {
916            #[inline]
917            fn bitxor_assign(&mut self, rhs: T) { self.0 = (*self ^ rhs).0 }
918        }
919
920        impl<T> ::core::ops::BitOr<T> for $name
921        where T: Into<$name>
922        {
923            type Output = $name;
924
925            #[inline]
926            fn bitor(self, other: T) -> $name {
927                let $name(ref arr1) = self;
928                let $name(ref arr2) = other.into();
929                let mut ret = [0u64; $n_words];
930                for i in 0..$n_words {
931                    ret[i] = arr1[i] | arr2[i];
932                }
933                $name(ret)
934            }
935        }
936        impl<T> ::core::ops::BitOrAssign<T> for $name
937        where T: Into<$name>
938        {
939            #[inline]
940            fn bitor_assign(&mut self, rhs: T) { self.0 = (*self | rhs).0 }
941        }
942
943        impl ::core::ops::Shl<usize> for $name {
944            type Output = $name;
945
946            fn shl(self, shift: usize) -> $name {
947                let $name(ref original) = self;
948                let mut ret = [0u64; $n_words];
949                let word_shift = shift / 64;
950                let bit_shift = shift % 64;
951                for i in 0..$n_words {
952                    // Shift
953                    if bit_shift < 64 && i + word_shift < $n_words {
954                        ret[i + word_shift] += original[i] << bit_shift;
955                    }
956                    // Carry
957                    if bit_shift > 0 && i + word_shift + 1 < $n_words {
958                        ret[i + word_shift + 1] += original[i] >> (64 - bit_shift);
959                    }
960                }
961                $name(ret)
962            }
963        }
964        impl ::core::ops::ShlAssign<usize> for $name {
965            #[inline]
966            fn shl_assign(&mut self, rhs: usize) { self.0 = (*self << rhs).0 }
967        }
968
969        impl ::core::ops::Shr<usize> for $name {
970            type Output = $name;
971
972            fn shr(self, shift: usize) -> $name {
973                let $name(ref original) = self;
974                let mut ret = [0u64; $n_words];
975                let word_shift = shift / 64;
976                let bit_shift = shift % 64;
977                for i in word_shift..$n_words {
978                    // Shift
979                    ret[i - word_shift] += original[i] >> bit_shift;
980                    // Carry
981                    if bit_shift > 0 && i < $n_words - 1 {
982                        ret[i - word_shift] += original[i + 1] << (64 - bit_shift);
983                    }
984                }
985                if self.is_negative() {
986                    ret[$n_words - 1] |= 0x8000_0000_0000_0000
987                }
988                $name(ret)
989            }
990        }
991
992        impl ::core::ops::ShrAssign<usize> for $name {
993            #[inline]
994            fn shr_assign(&mut self, rhs: usize) { self.0 = (*self >> rhs).0 }
995        }
996
997        impl ::core::ops::Not for $name {
998            type Output = $name;
999
1000            #[inline]
1001            fn not(self) -> $name {
1002                let $name(ref arr) = self;
1003                let mut ret = [0u64; $n_words];
1004                for i in 0..$n_words {
1005                    ret[i] = !arr[i];
1006                }
1007                $name(ret)
1008            }
1009        }
1010
1011        impl ::core::fmt::Debug for $name {
1012            fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
1013                let &$name(ref data) = self;
1014                write!(f, "0x")?;
1015                for ch in data.iter().rev() {
1016                    write!(f, "{:016x}", ch)?;
1017                }
1018                Ok(())
1019            }
1020        }
1021
1022        impl ::core::fmt::Display for $name {
1023            fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
1024                ::core::fmt::Debug::fmt(self, f)
1025            }
1026        }
1027
1028        #[cfg(feature = "alloc")]
1029        impl ::core::fmt::UpperHex for $name {
1030            fn fmt(&self, f: &mut ::core::fmt::Formatter<'_>) -> Result<(), ::core::fmt::Error> {
1031                use alloc::format;
1032                use alloc::string::String;
1033
1034                let mut hex = String::new();
1035                for chunk in self.0.iter().rev().skip_while(|x| **x == 0) {
1036                    if hex.is_empty() {
1037                        hex.push_str(&format!("{:X}", chunk));
1038                    } else {
1039                        hex.push_str(&format!("{:0>16X}", chunk));
1040                    }
1041                }
1042                if hex.is_empty() {
1043                    hex.push_str("0");
1044                }
1045
1046                let mut prefix = if f.alternate() {
1047                    String::from("0x")
1048                } else {
1049                    String::new()
1050                };
1051                if let Some(width) = f.width() {
1052                    if f.sign_aware_zero_pad() {
1053                        let missing_width =
1054                            width.saturating_sub(prefix.len()).saturating_sub(hex.len());
1055                        prefix.push_str(&"0".repeat(missing_width));
1056                    }
1057                }
1058
1059                prefix.push_str(&hex);
1060                f.pad(&prefix)
1061            }
1062        }
1063
1064        #[cfg(feature = "alloc")]
1065        impl ::core::fmt::LowerHex for $name {
1066            fn fmt(&self, f: &mut ::core::fmt::Formatter<'_>) -> Result<(), ::core::fmt::Error> {
1067                use alloc::format;
1068                use alloc::string::String;
1069
1070                let mut hex = String::new();
1071                for chunk in self.0.iter().rev().skip_while(|x| **x == 0) {
1072                    if hex.is_empty() {
1073                        hex.push_str(&format!("{:x}", chunk));
1074                    } else {
1075                        hex.push_str(&format!("{:0>16x}", chunk));
1076                    }
1077                }
1078                if hex.is_empty() {
1079                    hex.push_str("0");
1080                }
1081
1082                let mut prefix = if f.alternate() {
1083                    String::from("0x")
1084                } else {
1085                    String::new()
1086                };
1087                if let Some(width) = f.width() {
1088                    if f.sign_aware_zero_pad() {
1089                        let missing_width =
1090                            width.saturating_sub(prefix.len()).saturating_sub(hex.len());
1091                        prefix.push_str(&"0".repeat(missing_width));
1092                    }
1093                }
1094
1095                prefix.push_str(&hex);
1096                f.pad(&prefix)
1097            }
1098        }
1099
1100        #[cfg(feature = "alloc")]
1101        impl ::core::fmt::Octal for $name {
1102            fn fmt(&self, f: &mut ::core::fmt::Formatter<'_>) -> Result<(), ::core::fmt::Error> {
1103                use alloc::format;
1104                use alloc::string::String;
1105
1106                let mut octal = String::new();
1107                for chunk in self.0.iter().rev().skip_while(|x| **x == 0) {
1108                    if octal.is_empty() {
1109                        octal.push_str(&format!("{:o}", chunk));
1110                    } else {
1111                        octal.push_str(&format!("{:0>22o}", chunk));
1112                    }
1113                }
1114                if octal.is_empty() {
1115                    octal.push_str("0");
1116                }
1117
1118                let mut prefix = if f.alternate() {
1119                    String::from("0o")
1120                } else {
1121                    String::new()
1122                };
1123                if let Some(width) = f.width() {
1124                    if f.sign_aware_zero_pad() {
1125                        let missing_width = width
1126                            .saturating_sub(prefix.len())
1127                            .saturating_sub(octal.len());
1128                        prefix.push_str(&"0".repeat(missing_width));
1129                    }
1130                }
1131
1132                prefix.push_str(&octal);
1133                f.pad(&prefix)
1134            }
1135        }
1136
1137        #[cfg(feature = "alloc")]
1138        impl ::core::fmt::Binary for $name {
1139            fn fmt(&self, f: &mut ::core::fmt::Formatter<'_>) -> Result<(), ::core::fmt::Error> {
1140                use alloc::format;
1141                use alloc::string::String;
1142
1143                let mut binary = String::new();
1144                for chunk in self.0.iter().rev().skip_while(|x| **x == 0) {
1145                    if binary.is_empty() {
1146                        binary.push_str(&format!("{:b}", chunk));
1147                    } else {
1148                        binary.push_str(&format!("{:0>64b}", chunk));
1149                    }
1150                }
1151                if binary.is_empty() {
1152                    binary.push_str("0");
1153                }
1154
1155                let mut prefix = if f.alternate() {
1156                    String::from("0b")
1157                } else {
1158                    String::new()
1159                };
1160                if let Some(width) = f.width() {
1161                    if f.sign_aware_zero_pad() {
1162                        let missing_width = width
1163                            .saturating_sub(prefix.len())
1164                            .saturating_sub(binary.len());
1165                        prefix.push_str(&"0".repeat(missing_width));
1166                    }
1167                }
1168
1169                prefix.push_str(&binary);
1170                f.pad(&prefix)
1171            }
1172        }
1173
1174        #[cfg(feature = "serde")]
1175        impl $crate::serde::Serialize for $name {
1176            fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1177            where S: $crate::serde::Serializer {
1178                use $crate::hex::ToHex;
1179                let bytes = self.to_be_bytes();
1180                if serializer.is_human_readable() {
1181                    serializer.serialize_str(&bytes.to_hex())
1182                } else {
1183                    serializer.serialize_bytes(&bytes)
1184                }
1185            }
1186        }
1187
1188        #[cfg(feature = "serde")]
1189        impl<'de> $crate::serde::Deserialize<'de> for $name {
1190            fn deserialize<D: $crate::serde::Deserializer<'de>>(
1191                deserializer: D,
1192            ) -> Result<Self, D::Error> {
1193                use ::std::fmt;
1194                use $crate::hex::FromHex;
1195                use $crate::serde::de;
1196                struct Visitor;
1197                impl<'de> de::Visitor<'de> for Visitor {
1198                    type Value = $name;
1199
1200                    fn expecting(&self, f: &mut fmt::Formatter) -> fmt::Result {
1201                        write!(
1202                            f,
1203                            "{} bytes or a hex string with {} characters",
1204                            $n_words * 8,
1205                            $n_words * 8 * 2
1206                        )
1207                    }
1208
1209                    fn visit_str<E>(self, s: &str) -> Result<Self::Value, E>
1210                    where E: de::Error {
1211                        let bytes = Vec::from_hex(s)
1212                            .map_err(|_| de::Error::invalid_value(de::Unexpected::Str(s), &self))?;
1213                        $name::from_be_slice(&bytes)
1214                            .map_err(|_| de::Error::invalid_length(bytes.len() * 2, &self))
1215                    }
1216
1217                    fn visit_bytes<E>(self, bytes: &[u8]) -> Result<Self::Value, E>
1218                    where E: de::Error {
1219                        $name::from_be_slice(bytes)
1220                            .map_err(|_| de::Error::invalid_length(bytes.len(), &self))
1221                    }
1222                }
1223
1224                if deserializer.is_human_readable() {
1225                    deserializer.deserialize_str(Visitor)
1226                } else {
1227                    deserializer.deserialize_bytes(Visitor)
1228                }
1229            }
1230        }
1231    };
1232}
1233
1234macro_rules! construct_signed_bigint_methods {
1235    ($name:ident, $n_words:expr) => {
1236        impl From<i8> for $name {
1237            fn from(init: i8) -> $name {
1238                let bytes = init.to_le_bytes();
1239                let mut ret = [if init.is_negative() { u8::MAX } else { 0 }; $n_words * 8];
1240                for i in 0..bytes.len() {
1241                    ret[i] = bytes[i]
1242                }
1243                $name::from_le_bytes(ret)
1244            }
1245        }
1246
1247        impl From<i16> for $name {
1248            fn from(init: i16) -> $name {
1249                let bytes = init.to_le_bytes();
1250                let mut ret = [if init.is_negative() { u8::MAX } else { 0 }; $n_words * 8];
1251                for i in 0..bytes.len() {
1252                    ret[i] = bytes[i]
1253                }
1254                $name::from_le_bytes(ret)
1255            }
1256        }
1257
1258        impl From<i32> for $name {
1259            fn from(init: i32) -> $name {
1260                let bytes = init.to_le_bytes();
1261                let mut ret = [if init.is_negative() { u8::MAX } else { 0 }; $n_words * 8];
1262                for i in 0..bytes.len() {
1263                    ret[i] = bytes[i]
1264                }
1265                $name::from_le_bytes(ret)
1266            }
1267        }
1268
1269        impl From<i64> for $name {
1270            fn from(init: i64) -> $name {
1271                let bytes = init.to_le_bytes();
1272                let mut ret = [if init.is_negative() { u8::MAX } else { 0 }; $n_words * 8];
1273                for i in 0..bytes.len() {
1274                    ret[i] = bytes[i]
1275                }
1276                $name::from_le_bytes(ret)
1277            }
1278        }
1279
1280        impl From<i128> for $name {
1281            fn from(init: i128) -> $name {
1282                let bytes = init.to_le_bytes();
1283                let mut ret = [if init.is_negative() { u8::MAX } else { 0 }; $n_words * 8];
1284                for i in 0..bytes.len() {
1285                    ret[i] = bytes[i]
1286                }
1287                $name::from_le_bytes(ret)
1288            }
1289        }
1290
1291        impl $name {
1292            const IS_SIGNED_TYPE: bool = true;
1293
1294            /// Minimum value
1295            pub const MIN: $name = {
1296                let mut min = [0u64; $n_words];
1297                min[$n_words - 1] = 0x8000_0000_0000_0000;
1298                $name(min)
1299            };
1300
1301            /// Maximum value
1302            pub const MAX: $name = {
1303                let mut max = [u64::MAX; $n_words];
1304                max[$n_words - 1] = u64::MAX >> 1;
1305                $name(max)
1306            };
1307
1308            #[inline]
1309            pub fn is_negative(&self) -> bool {
1310                self[($name::INNER_LEN - 1) as usize] & 0x8000_0000_0000_0000 != 0
1311            }
1312
1313            /// Return the least number of bits needed to represent the number
1314            #[inline]
1315            pub fn bits_required(&self) -> usize {
1316                let &$name(ref arr) = self;
1317                let iter = arr.iter().rev().take($n_words - 1);
1318                if self.is_negative() {
1319                    let ctr = iter.take_while(|&&b| b == u64::MAX).count();
1320                    (0x40 * ($n_words - ctr)) + 1 -
1321                        (!arr[$n_words - ctr - 1]).leading_zeros() as usize
1322                } else {
1323                    let ctr = iter.take_while(|&&b| b == u64::MIN).count();
1324                    (0x40 * ($n_words - ctr)) + 1 - arr[$n_words - ctr - 1].leading_zeros() as usize
1325                }
1326            }
1327
1328            /// Calculates `self * rhs`
1329            ///
1330            /// Returns a tuple of the multiplication along with a boolean indicating
1331            /// whether an arithmetic overflow would occur. If an overflow would
1332            /// have occurred then the wrapped value is returned.
1333            pub fn overflowing_mul<T>(self, other: T) -> ($name, bool)
1334            where T: Into<$name> {
1335                let sub = if self != $name::MIN { -self } else { self };
1336                let mut p_high = $name::ZERO;
1337                let mut p_low = other.into();
1338                let mut prev = false;
1339                for _i in 0..$name::BITS {
1340                    let p_low_trailing_bit = (p_low[0] & 1) != 0;
1341                    p_high = match (p_low_trailing_bit, prev) {
1342                        (false, true) => p_high.wrapping_add(self),
1343                        (true, false) => p_high.wrapping_add(sub),
1344                        _ => p_high,
1345                    };
1346                    prev = p_low_trailing_bit;
1347                    p_low >>= 1;
1348                    p_low = match p_high[0] & 1 {
1349                        0 => p_low & $name::MAX,
1350                        _ => p_low | $name::MIN,
1351                    };
1352                    p_high >>= 1;
1353                }
1354                let negative_overflow =
1355                    p_low.is_negative() && p_high != $name([u64::MAX; $n_words]);
1356                let positive_overflow = !p_low.is_negative() && p_high != $name::ZERO;
1357                (p_low, negative_overflow || positive_overflow)
1358            }
1359        }
1360    };
1361}
1362
1363macro_rules! construct_unsigned_bigint_methods {
1364    ($name:ident, $n_words:expr) => {
1365        impl $name {
1366            const IS_SIGNED_TYPE: bool = false;
1367
1368            /// Minimum value
1369            pub const MIN: $name = $name([0u64; $n_words]);
1370
1371            /// Maximum value
1372            pub const MAX: $name = $name([u64::MAX; $n_words]);
1373
1374            #[inline]
1375            pub const fn is_negative(&self) -> bool { false }
1376
1377            /// Return the least number of bits needed to represent the number
1378            #[inline]
1379            pub fn bits_required(&self) -> usize {
1380                let &$name(ref arr) = self;
1381                let iter = arr.iter().rev().take($n_words - 1);
1382                let ctr = iter.take_while(|&&b| b == u64::MIN).count();
1383                (0x40 * ($n_words - ctr)) - arr[$n_words - ctr - 1].leading_zeros() as usize
1384            }
1385
1386            /// Calculates `self * rhs`
1387            ///
1388            /// Returns a tuple of the multiplication along with a boolean indicating
1389            /// whether an arithmetic overflow would occur. If an overflow would
1390            /// have occurred then the wrapped value is returned.
1391            pub fn overflowing_mul<T>(self, other: T) -> ($name, bool)
1392            where T: Into<$name> {
1393                let $name(ref me) = self;
1394                let $name(ref you) = other.into();
1395                let mut ret = [0u64; $n_words];
1396                let mut overflow = false;
1397                for i in 0..$n_words {
1398                    let mut carry = 0u64;
1399                    for j in 0..$n_words {
1400                        if i + j >= $n_words {
1401                            if me[i] > 0 && you[j] > 0 {
1402                                overflow = true
1403                            }
1404                            continue;
1405                        }
1406                        let prev_carry = carry;
1407                        let res = me[i] as u128 * you[j] as u128;
1408                        carry = (res >> 64) as u64;
1409                        let mul = (res & u64::MAX as u128) as u64;
1410                        let (res, flag) = ret[i + j].overflowing_add(mul);
1411                        carry += flag as u64;
1412                        ret[i + j] = res;
1413                        let (res, flag) = ret[i + j].overflowing_add(prev_carry);
1414                        carry += flag as u64;
1415                        ret[i + j] = res;
1416                    }
1417                    if carry > 0 {
1418                        overflow = true
1419                    }
1420                }
1421                (Self(ret), overflow)
1422            }
1423        }
1424    };
1425}
1426
1427macro_rules! impl_from {
1428    ($from:ident, $n_words_from:expr, $to:ident, $n_words_to:expr) => {
1429        impl From<$from> for $to {
1430            fn from(init: $from) -> $to {
1431                let mut ret = [0u64; $n_words_to];
1432                for i in 0..$n_words_from {
1433                    ret[i] = init.0[i]
1434                }
1435                $to(ret)
1436            }
1437        }
1438    };
1439}
1440
1441construct_bigint!(i256, 4);
1442construct_bigint!(i512, 8);
1443construct_bigint!(i1024, 16);
1444construct_bigint!(u256, 4);
1445construct_bigint!(u512, 8);
1446construct_bigint!(u1024, 16);
1447
1448construct_unsigned_bigint_methods!(u256, 4);
1449construct_unsigned_bigint_methods!(u512, 8);
1450construct_unsigned_bigint_methods!(u1024, 16);
1451construct_signed_bigint_methods!(i256, 4);
1452construct_signed_bigint_methods!(i512, 8);
1453construct_signed_bigint_methods!(i1024, 16);
1454
1455impl_from!(u256, 4, u512, 8);
1456impl_from!(u256, 4, u1024, 16);
1457impl_from!(u512, 8, u1024, 16);
1458
1459#[cfg(test)]
1460mod tests {
1461    #![allow(unused)]
1462
1463    use super::*;
1464
1465    construct_bigint!(Uint128, 2);
1466    construct_unsigned_bigint_methods!(Uint128, 2);
1467
1468    #[test]
1469    fn u256_bits_test() {
1470        assert_eq!(u256::from(255u64).bits_required(), 8);
1471        assert_eq!(u256::from(256u64).bits_required(), 9);
1472        assert_eq!(u256::from(300u64).bits_required(), 9);
1473        assert_eq!(u256::from(60000u64).bits_required(), 16);
1474        assert_eq!(u256::from(70000u64).bits_required(), 17);
1475
1476        // Try to read the following lines out loud quickly
1477        let mut shl = u256::from(70000u64);
1478        shl <<= 100;
1479        assert_eq!(shl.bits_required(), 117);
1480        shl <<= 100;
1481        assert_eq!(shl.bits_required(), 217);
1482        shl <<= 100;
1483        assert_eq!(shl.bits_required(), 0);
1484
1485        // Bit set check
1486        assert!(!u256::from(10u64).bit(0));
1487        assert!(u256::from(10u64).bit(1));
1488        assert!(!u256::from(10u64).bit(2));
1489        assert!(u256::from(10u64).bit(3));
1490        assert!(!u256::from(10u64).bit(4));
1491    }
1492
1493    #[test]
1494    fn u256_display_test() {
1495        assert_eq!(
1496            format!("{}", u256::from(0xDEADBEEFu64)),
1497            "0x00000000000000000000000000000000000000000000000000000000deadbeef"
1498        );
1499        assert_eq!(
1500            format!("{}", u256::from(u64::MAX)),
1501            "0x000000000000000000000000000000000000000000000000ffffffffffffffff"
1502        );
1503
1504        let max_val =
1505            u256([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF]);
1506        assert_eq!(
1507            format!("{}", max_val),
1508            "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
1509        );
1510    }
1511
1512    #[cfg(feature = "alloc")]
1513    #[test]
1514    fn fmt_hex() {
1515        let one = u256::ONE;
1516        let u_256 =
1517            u256([0x0000000000000000, 0xAAAAAAAABBBBBBBB, 0x0000000111122222, 0x0000000000000000]);
1518
1519        // UpperHex
1520        assert_eq!(format!("{:X}", u_256), "111122222AAAAAAAABBBBBBBB0000000000000000");
1521        assert_eq!(format!("{:#X}", u_256), "0x111122222AAAAAAAABBBBBBBB0000000000000000");
1522        assert_eq!(format!("{:X}", u256::ZERO), "0");
1523        assert_eq!(format!("{:05X}", one), "00001");
1524        assert_eq!(format!("{:#05X}", one), "0x001");
1525        assert_eq!(format!("{:5X}", one), "1    ");
1526        assert_eq!(format!("{:#5X}", one), "0x1  ");
1527        assert_eq!(format!("{:w^#7X}", one), "ww0x1ww");
1528
1529        // LowerHex
1530        assert_eq!(format!("{:x}", u_256), "111122222aaaaaaaabbbbbbbb0000000000000000");
1531        assert_eq!(format!("{:#x}", u_256), "0x111122222aaaaaaaabbbbbbbb0000000000000000");
1532        assert_eq!(format!("{:x}", u256::ZERO), "0");
1533        assert_eq!(format!("{:05x}", one), "00001");
1534        assert_eq!(format!("{:#05x}", one), "0x001");
1535        assert_eq!(format!("{:5x}", one), "1    ");
1536        assert_eq!(format!("{:#5x}", one), "0x1  ");
1537        assert_eq!(format!("{:w^#7x}", one), "ww0x1ww");
1538    }
1539
1540    #[cfg(feature = "alloc")]
1541    #[test]
1542    fn fmt_octal() {
1543        let one = u256::ONE;
1544        let u_256 = u256([
1545            0o0000000000000000000000,
1546            0o0011222222222222222222,
1547            0o0000000001111111111111,
1548            0o0000000000000000000000,
1549        ]);
1550
1551        assert_eq!(
1552            format!("{:o}", u_256),
1553            "111111111111100112222222222222222220000000000000000000000"
1554        );
1555        assert_eq!(
1556            format!("{:#o}", u_256),
1557            "0o111111111111100112222222222222222220000000000000000000000"
1558        );
1559        assert_eq!(format!("{:o}", u256::ZERO), "0");
1560        assert_eq!(format!("{:05o}", one), "00001");
1561        assert_eq!(format!("{:#05o}", one), "0o001");
1562        assert_eq!(format!("{:5o}", one), "1    ");
1563        assert_eq!(format!("{:#5o}", one), "0o1  ");
1564        assert_eq!(format!("{:w^#7o}", one), "ww0o1ww");
1565    }
1566
1567    #[cfg(feature = "alloc")]
1568    #[test]
1569    fn fmt_binary() {
1570        let one = u256::ONE;
1571        let u_256 = u256([
1572            0b0000000000000000000000000000000000000000000000000000000000000000,
1573            0b0001111000011110001111000011110001111000011110001111000011110000,
1574            0b0000000000000000000000000000001111111111111111111111111111111111,
1575            0b0000000000000000000000000000000000000000000000000000000000000000,
1576        ]);
1577
1578        assert_eq!(
1579            format!("{:b}", u_256),
1580            "111111111111111111111111111111111100011110000111100011110000111100011110000111100011110000111100000000000000000000000000000000000000000000000000000000000000000000"
1581        );
1582        assert_eq!(
1583            format!("{:#b}", u_256),
1584            "0b111111111111111111111111111111111100011110000111100011110000111100011110000111100011110000111100000000000000000000000000000000000000000000000000000000000000000000"
1585        );
1586        assert_eq!(format!("{:b}", u256::ZERO), "0");
1587        assert_eq!(format!("{:05b}", one), "00001");
1588        assert_eq!(format!("{:#05b}", one), "0b001");
1589        assert_eq!(format!("{:5b}", one), "1    ");
1590        assert_eq!(format!("{:#5b}", one), "0b1  ");
1591        assert_eq!(format!("{:w^#7b}", one), "ww0b1ww");
1592    }
1593
1594    #[test]
1595    fn u256_comp_test() {
1596        let small = u256([10u64, 0, 0, 0]);
1597        let big = u256([0x8C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]);
1598        let bigger = u256([0x9C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]);
1599        let biggest = u256([0x5C8C3EE70C644118u64, 0x0209E7378231E632, 0, 1]);
1600
1601        assert!(small < big);
1602        assert!(big < bigger);
1603        assert!(bigger < biggest);
1604        assert!(bigger <= biggest);
1605        assert!(biggest <= biggest);
1606        assert!(bigger >= big);
1607        assert!(bigger >= small);
1608        assert!(small <= small);
1609    }
1610
1611    #[test]
1612    fn uint_from_be_bytes() {
1613        assert_eq!(
1614            Uint128::from_be_bytes([
1615                0x1b, 0xad, 0xca, 0xfe, 0xde, 0xad, 0xbe, 0xef, 0xde, 0xaf, 0xba, 0xbe, 0x2b, 0xed,
1616                0xfe, 0xed
1617            ]),
1618            Uint128([0xdeafbabe2bedfeed, 0x1badcafedeadbeef])
1619        );
1620
1621        assert_eq!(
1622            u256::from_be_bytes([
1623                0x1b, 0xad, 0xca, 0xfe, 0xde, 0xad, 0xbe, 0xef, 0xde, 0xaf, 0xba, 0xbe, 0x2b, 0xed,
1624                0xfe, 0xed, 0xba, 0xad, 0xf0, 0x0d, 0xde, 0xfa, 0xce, 0xda, 0x11, 0xfe, 0xd2, 0xba,
1625                0xd1, 0xc0, 0xff, 0xe0
1626            ]),
1627            u256([0x11fed2bad1c0ffe0, 0xbaadf00ddefaceda, 0xdeafbabe2bedfeed, 0x1badcafedeadbeef])
1628        );
1629    }
1630
1631    #[test]
1632    fn uint_from_le_bytes() {
1633        let mut be = [
1634            0x1b, 0xad, 0xca, 0xfe, 0xde, 0xad, 0xbe, 0xef, 0xde, 0xaf, 0xba, 0xbe, 0x2b, 0xed,
1635            0xfe, 0xed,
1636        ];
1637        be.reverse();
1638        assert_eq!(Uint128::from_le_bytes(be), Uint128([0xdeafbabe2bedfeed, 0x1badcafedeadbeef]));
1639
1640        let mut be = [
1641            0x1b, 0xad, 0xca, 0xfe, 0xde, 0xad, 0xbe, 0xef, 0xde, 0xaf, 0xba, 0xbe, 0x2b, 0xed,
1642            0xfe, 0xed, 0xba, 0xad, 0xf0, 0x0d, 0xde, 0xfa, 0xce, 0xda, 0x11, 0xfe, 0xd2, 0xba,
1643            0xd1, 0xc0, 0xff, 0xe0,
1644        ];
1645        be.reverse();
1646        assert_eq!(
1647            u256::from_le_bytes(be),
1648            u256([0x11fed2bad1c0ffe0, 0xbaadf00ddefaceda, 0xdeafbabe2bedfeed, 0x1badcafedeadbeef])
1649        );
1650    }
1651
1652    #[test]
1653    fn uint_to_be_bytes() {
1654        assert_eq!(Uint128([0xdeafbabe2bedfeed, 0x1badcafedeadbeef]).to_be_bytes(), [
1655            0x1b, 0xad, 0xca, 0xfe, 0xde, 0xad, 0xbe, 0xef, 0xde, 0xaf, 0xba, 0xbe, 0x2b, 0xed,
1656            0xfe, 0xed
1657        ]);
1658
1659        assert_eq!(
1660            u256([0x11fed2bad1c0ffe0, 0xbaadf00ddefaceda, 0xdeafbabe2bedfeed, 0x1badcafedeadbeef])
1661                .to_be_bytes(),
1662            [
1663                0x1b, 0xad, 0xca, 0xfe, 0xde, 0xad, 0xbe, 0xef, 0xde, 0xaf, 0xba, 0xbe, 0x2b, 0xed,
1664                0xfe, 0xed, 0xba, 0xad, 0xf0, 0x0d, 0xde, 0xfa, 0xce, 0xda, 0x11, 0xfe, 0xd2, 0xba,
1665                0xd1, 0xc0, 0xff, 0xe0
1666            ]
1667        );
1668    }
1669
1670    #[test]
1671    fn uint_to_le_bytes() {
1672        assert_eq!(Uint128([0xdeafbabe2bedfeed, 0x1badcafedeadbeef]).to_le_bytes(), [
1673            0xed, 0xfe, 0xed, 0x2b, 0xbe, 0xba, 0xaf, 0xde, 0xef, 0xbe, 0xad, 0xde, 0xfe, 0xca,
1674            0xad, 0x1b
1675        ]);
1676
1677        assert_eq!(
1678            u256([0x11fed2bad1c0ffe0, 0xbaadf00ddefaceda, 0xdeafbabe2bedfeed, 0x1badcafedeadbeef])
1679                .to_le_bytes(),
1680            [
1681                0xe0, 0xff, 0xc0, 0xd1, 0xba, 0xd2, 0xfe, 0x11, 0xda, 0xce, 0xfa, 0xde, 0x0d, 0xf0,
1682                0xad, 0xba, 0xed, 0xfe, 0xed, 0x2b, 0xbe, 0xba, 0xaf, 0xde, 0xef, 0xbe, 0xad, 0xde,
1683                0xfe, 0xca, 0xad, 0x1b,
1684            ]
1685        );
1686    }
1687
1688    #[test]
1689    fn u256_div_rem_0() {
1690        let zero = u256::ZERO;
1691        let number_one = u256::from(0xDEADBEEFu64);
1692        let number_two = u256::from(u64::MAX);
1693        let one_div_rem_two =
1694            (u256::from(u64::MAX / 0xDEADBEEFu64), u256::from(u64::MAX % 0xDEADBEEFu64));
1695        let max = u256::MAX;
1696
1697        // Division by zero gets not panic and gets None
1698        assert_eq!(u256::div_rem(max, zero), Err(DivError::ZeroDiv));
1699        assert_eq!(u256::div_rem(number_two, zero), Err(DivError::ZeroDiv));
1700        assert_eq!(u256::div_rem(number_one, zero), Err(DivError::ZeroDiv));
1701
1702        // Division of zero gets Zero
1703        assert_eq!(u256::div_rem(zero, max), Ok((zero, zero)));
1704        assert_eq!(u256::div_rem(zero, number_two), Ok((zero, zero)));
1705        assert_eq!(u256::div_rem(zero, number_one), Ok((zero, zero)));
1706
1707        // Division by another than zero not gets None
1708        assert!(u256::div_rem(max, number_one).is_ok());
1709        assert!(u256::div_rem(number_two, number_one).is_ok());
1710
1711        // In u256 division gets the same as in u64
1712        assert_eq!(u256::div_rem(number_two, number_one), Ok(one_div_rem_two));
1713    }
1714
1715    #[test]
1716    fn u256_div_rem_1() {
1717        let zero = u256::ZERO;
1718        let number_one = u256::from(0xDEADBEEFu64);
1719        let number_two = u256::from(u64::MAX);
1720        let max = u256::MAX;
1721
1722        assert!(u256::div_rem(max, zero).is_err());
1723        assert!(u256::div_rem(number_one, zero).is_err());
1724        assert!(u256::div_rem(number_two, zero).is_err());
1725
1726        assert_eq!(u256::MAX / u256::ONE, u256::MAX);
1727        assert_eq!(u256::from(12u8) / u256::from(4u8), u256::from(3u8));
1728        assert!(std::panic::catch_unwind(|| number_one / zero).is_err());
1729        assert!(std::panic::catch_unwind(|| i256::MIN / (-i256::ONE)).is_err());
1730    }
1731
1732    #[test]
1733    fn bigint_min_max() {
1734        assert_eq!(u256::MIN.as_inner(), &[0u64; 4]);
1735        assert_eq!(u512::MIN.as_inner(), &[0u64; 8]);
1736        assert_eq!(u1024::MIN.as_inner(), &[0u64; 16]);
1737        assert_eq!(u256::MAX.as_inner(), &[u64::MAX; 4]);
1738        assert_eq!(u512::MAX.as_inner(), &[u64::MAX; 8]);
1739        assert_eq!(u1024::MAX.as_inner(), &[u64::MAX; 16]);
1740        assert_eq!(u256::BITS, 4 * 64);
1741        assert_eq!(u512::BITS, 8 * 64);
1742        assert_eq!(u1024::BITS, 16 * 64);
1743    }
1744
1745    #[test]
1746    fn u256_arithmetic_test() {
1747        let init = u256::from(0xDEADBEEFDEADBEEFu64);
1748        let copy = init;
1749
1750        let add = init + copy;
1751        assert_eq!(add, u256([0xBD5B7DDFBD5B7DDEu64, 1, 0, 0]));
1752        // Bitshifts
1753        let shl = add << 88;
1754        assert_eq!(shl, u256([0u64, 0xDFBD5B7DDE000000, 0x1BD5B7D, 0]));
1755        let shr = shl >> 40;
1756        assert_eq!(shr, u256([0x7DDE000000000000u64, 0x0001BD5B7DDFBD5B, 0, 0]));
1757        // Increment
1758        let mut incr = shr;
1759        incr += 1u32;
1760        assert_eq!(incr, u256([0x7DDE000000000001u64, 0x0001BD5B7DDFBD5B, 0, 0]));
1761        // Subtraction
1762        let sub = incr - init;
1763        assert_eq!(sub, u256([0x9F30411021524112u64, 0x0001BD5B7DDFBD5A, 0, 0]));
1764        // Multiplication
1765        let mult = sub * 300u32;
1766        assert_eq!(mult, u256([0x8C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]));
1767        // Division
1768        assert_eq!(u256::from(105u64) / u256::from(5u64), u256::from(21u64));
1769        let div = mult / u256::from(300u64);
1770        assert_eq!(div, u256([0x9F30411021524112u64, 0x0001BD5B7DDFBD5A, 0, 0]));
1771
1772        assert_eq!(u256::from(105u64) % u256::from(5u64), u256::from(0u64));
1773        assert_eq!(u256::from(35498456u64) % u256::from(3435u64), u256::from(1166u64));
1774        let rem_src = mult * u256::from(39842u64) + u256::from(9054u64);
1775        assert_eq!(rem_src % u256::from(39842u64), u256::from(9054u64));
1776        // TODO: bit inversion
1777    }
1778
1779    #[test]
1780    fn mul_u32_test() {
1781        let u64_val = u256::from(0xDEADBEEFDEADBEEFu64);
1782
1783        let u96_res = u64_val * 0xFFFFFFFFu32;
1784        let u128_res = u96_res * 0xFFFFFFFFu32;
1785        let u160_res = u128_res * 0xFFFFFFFFu32;
1786        let u192_res = u160_res * 0xFFFFFFFFu32;
1787        let u224_res = u192_res * 0xFFFFFFFFu32;
1788        let u256_res = u224_res * 0xFFFFFFFFu32;
1789
1790        assert_eq!(u96_res, u256([0xffffffff21524111u64, 0xDEADBEEE, 0, 0]));
1791        assert_eq!(u128_res, u256([0x21524111DEADBEEFu64, 0xDEADBEEE21524110, 0, 0]));
1792        assert_eq!(u160_res, u256([0xBD5B7DDD21524111u64, 0x42A4822200000001, 0xDEADBEED, 0]));
1793        assert_eq!(
1794            u192_res,
1795            u256([0x63F6C333DEADBEEFu64, 0xBD5B7DDFBD5B7DDB, 0xDEADBEEC63F6C334, 0])
1796        );
1797        assert_eq!(
1798            u224_res,
1799            u256([0x7AB6FBBB21524111u64, 0xFFFFFFFBA69B4558, 0x854904485964BAAA, 0xDEADBEEB])
1800        );
1801        assert_eq!(
1802            u256_res,
1803            u256([
1804                0xA69B4555DEADBEEFu64,
1805                0xA69B455CD41BB662,
1806                0xD41BB662A69B4550,
1807                0xDEADBEEAA69B455C
1808            ])
1809        );
1810    }
1811
1812    #[test]
1813    fn multiplication_test() {
1814        let u64_val = u256::from(0xDEADBEEFDEADBEEFu64);
1815
1816        let u128_res = u64_val * u64_val;
1817
1818        assert_eq!(u128_res, u256([0x048D1354216DA321u64, 0xC1B1CD13A4D13D46, 0, 0]));
1819
1820        let u256_res = u128_res * u128_res;
1821
1822        assert_eq!(
1823            u256_res,
1824            u256([
1825                0xF4E166AAD40D0A41u64,
1826                0xF5CF7F3618C2C886u64,
1827                0x4AFCFF6F0375C608u64,
1828                0x928D92B4D7F5DF33u64
1829            ])
1830        );
1831    }
1832
1833    #[test]
1834    fn u256_extreme_bitshift_test() {
1835        // Shifting a u64 by 64 bits gives an undefined value, so make sure that
1836        // we're doing the Right Thing here
1837        let init = u256::from(0xDEADBEEFDEADBEEFu64);
1838
1839        assert_eq!(init << 64, u256([0, 0xDEADBEEFDEADBEEF, 0, 0]));
1840        let add = (init << 64) + init;
1841        assert_eq!(add, u256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0]));
1842        assert_eq!(add >> 0, u256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0]));
1843        assert_eq!(add << 0, u256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0]));
1844        assert_eq!(add >> 64, u256([0xDEADBEEFDEADBEEF, 0, 0, 0]));
1845        assert_eq!(add << 64, u256([0, 0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0]));
1846    }
1847
1848    #[cfg(feature = "serde")]
1849    #[test]
1850    fn u256_serde_test() {
1851        let check = |uint, hex| {
1852            let json = format!("\"{}\"", hex);
1853            assert_eq!(::serde_json::to_string(&uint).unwrap(), json);
1854            assert_eq!(::serde_json::from_str::<u256>(&json).unwrap(), uint);
1855        };
1856
1857        check(u256::from(0u64), "0000000000000000000000000000000000000000000000000000000000000000");
1858        check(
1859            u256::from(0xDEADBEEFu64),
1860            "00000000000000000000000000000000000000000000000000000000deadbeef",
1861        );
1862        check(
1863            u256([0xaa11, 0xbb22, 0xcc33, 0xdd44]),
1864            "000000000000dd44000000000000cc33000000000000bb22000000000000aa11",
1865        );
1866        check(
1867            u256([u64::MAX, u64::MAX, u64::MAX, u64::MAX]),
1868            "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
1869        );
1870        check(
1871            u256([0xA69B4555DEADBEEF, 0xA69B455CD41BB662, 0xD41BB662A69B4550, 0xDEADBEEAA69B455C]),
1872            "deadbeeaa69b455cd41bb662a69b4550a69b455cd41bb662a69b4555deadbeef",
1873        );
1874
1875        assert!(
1876            ::serde_json::from_str::<u256>(
1877                "\"fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffg\""
1878            )
1879            .is_err()
1880        ); // invalid char
1881        assert!(
1882            ::serde_json::from_str::<u256>(
1883                "\"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff\""
1884            )
1885            .is_err()
1886        ); // invalid length
1887        assert!(
1888            ::serde_json::from_str::<u256>(
1889                "\"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff\""
1890            )
1891            .is_err()
1892        ); // invalid length
1893    }
1894
1895    #[test]
1896    fn i256_test() {
1897        let x = i256::from(1);
1898        let y = i256::from(1);
1899        assert_eq!(x.checked_add(y), Some(i256::from(2)));
1900    }
1901
1902    #[test]
1903    fn i256_is_positive_test() {
1904        assert!(i256::from(1).is_positive());
1905        assert!(!i256::from(-1).is_positive());
1906        assert!(!i256::from(0).is_positive());
1907        assert!(i256::MAX.is_positive());
1908        assert!(!i256::MIN.is_positive());
1909        assert!(i256::MIN.is_negative());
1910    }
1911
1912    #[test]
1913    fn u256_add_test() {
1914        assert_eq!((u256::MAX - u256::ONE, true), u256::MAX.overflowing_add(u256::MAX));
1915    }
1916
1917    #[test]
1918    fn i256_add_test() {
1919        assert_eq!((i256::from(3), false), i256::from(1).overflowing_add(i256::from(2)));
1920        assert_eq!((i256::from(1), false), i256::from(-1).overflowing_add(i256::from(2)));
1921        assert_eq!((i256::from(-2), false), i256::from(-1).overflowing_add(i256::from(-1)));
1922        assert_eq!((i256::from(0), false), i256::from(0).overflowing_add(i256::from(0)));
1923        assert_eq!((i256::MIN, true), i256::from(1).overflowing_add(i256::MAX));
1924    }
1925
1926    #[test]
1927    fn i256_sub_test() {
1928        assert_eq!((i256::from(-1), false), i256::from(1).overflowing_sub(i256::from(2)));
1929        assert_eq!((i256::from(1), false), i256::from(3).overflowing_sub(i256::from(2)));
1930        assert_eq!((i256::from(-3), false), i256::from(-4).overflowing_sub(i256::from(-1)));
1931        assert_eq!((i256::from(0), false), i256::from(0).overflowing_add(i256::from(0)));
1932        assert_eq!((i256::MIN, false), i256::from(0).overflowing_sub(i256::MIN));
1933        assert_eq!((i256::ZERO, false), i256::MIN.overflowing_sub(i256::MIN));
1934        assert_eq!((-i256::ONE, false), i256::MAX.overflowing_sub(i256::MIN));
1935        assert_eq!((i256::MAX, true), (-i256::from(2)).overflowing_sub(i256::MAX));
1936    }
1937
1938    #[test]
1939    fn i256_neg_test() {
1940        assert_eq!(i256::from(1), -i256::from(-1));
1941        assert_eq!(i256::from(-1), -i256::from(1));
1942        assert_eq!(i256::from(0), -i256::from(0));
1943        assert_eq!(i256::MIN + 1, -i256::MAX);
1944    }
1945
1946    #[test]
1947    #[should_panic]
1948    fn i256_neg_min_test() {
1949        assert_eq!(-i256::MIN, -i256::MIN);
1950    }
1951
1952    #[test]
1953    fn i256_mul_test() {
1954        assert_eq!((i256::from(-12), false), i256::from(3).overflowing_mul(i256::from(-4)));
1955        assert_eq!((i256::from(6), false), i256::from(2).overflowing_mul(i256::from(3)));
1956        assert_eq!((i256::from(30), false), i256::from(-6).overflowing_mul(i256::from(-5)));
1957        assert_eq!((i256::from(-2), true), i256::MAX.overflowing_mul(i256::from(2)));
1958        assert_eq!((i256::ZERO, true), i256::MIN.overflowing_mul(i256::from(2)));
1959        assert_eq!((i256::ONE, true), i256::MAX.overflowing_mul(i256::MAX));
1960    }
1961
1962    #[test]
1963    fn i256_arithmetic_shr_test() {
1964        assert_eq!(i256::from(-1), i256::from(-1) >> 1);
1965        assert_eq!(i256::from(-1), i256::from(-2) >> 1);
1966        assert_eq!(i256::from(1), i256::from(2) >> 1);
1967        assert_eq!(i256::from(1), i256::from(2) >> 1);
1968        assert_eq!(i256::from(0), i256::from(1) >> 1);
1969    }
1970
1971    #[test]
1972    fn i256_bits_required_test() {
1973        assert_eq!(i256::from(255).bits_required(), 9);
1974        assert_eq!(i256::from(256).bits_required(), 10);
1975        assert_eq!(i256::from(300).bits_required(), 10);
1976        assert_eq!(i256::from(60000).bits_required(), 17);
1977        assert_eq!(i256::from(70000).bits_required(), 18);
1978        assert_eq!(i256::from(-128).bits_required(), 8);
1979        assert_eq!(i256::from(-129).bits_required(), 9);
1980        assert_eq!(i256::from(0).bits_required(), 1);
1981        assert_eq!(i256::from(-1).bits_required(), 1);
1982        assert_eq!(i256::from(-2).bits_required(), 2);
1983        assert_eq!(i256::MIN.bits_required(), 256);
1984        assert_eq!(i256::MAX.bits_required(), 256);
1985    }
1986
1987    #[test]
1988    fn i256_div_test() {
1989        assert_eq!(Ok((i256::from(3), i256::from(1))), i256::from(7).div_rem(i256::from(2i32)));
1990        assert_eq!(Ok((i256::from(-3), i256::from(1))), i256::from(7).div_rem(i256::from(-2i128)));
1991        assert_eq!(Ok((i256::from(-3), i256::from(-1))), i256::from(-7).div_rem(i256::from(2)));
1992        assert_eq!(Ok((i256::from(3), i256::from(-1))), i256::from(-7).div_rem(i256::from(-2)));
1993        assert!(i256::div_rem(i256::MAX, i256::ZERO).is_err());
1994    }
1995
1996    #[test]
1997    fn overflowing_div_est() {
1998        assert_eq!((i256::from(3), false), i256::from(7).overflowing_div(i256::from(2i32)));
1999        assert_eq!((i256::MIN, true), i256::MIN.overflowing_div(i256::from(-1)));
2000        let res = std::panic::catch_unwind(|| i256::overflowing_div(i256::MAX, i256::ZERO));
2001        assert!(res.is_err());
2002    }
2003
2004    #[test]
2005    fn wrapping_div_est() {
2006        assert_eq!(i1024::from(3), i1024::from(7).wrapping_div(2));
2007        assert_eq!(i512::MIN, i512::MIN.wrapping_div(-1));
2008        let res = std::panic::catch_unwind(|| i256::wrapping_div(i256::MAX, i256::ZERO));
2009        assert!(res.is_err());
2010    }
2011
2012    #[test]
2013    fn checked_div_est() {
2014        assert_eq!(Some(i1024::from(3)), i1024::from(7).checked_div(2));
2015        assert_eq!(Some(i512::MAX), i512::MAX.checked_div(1));
2016        assert_eq!(Some(i512::MIN + 1), i512::MAX.checked_div(-1));
2017        assert_eq!(None, i512::MIN.checked_div(-1));
2018        assert_eq!(None, i512::MAX.checked_div(0));
2019    }
2020
2021    #[test]
2022    fn saturating_div_test() {
2023        assert_eq!(i256::from(5).saturating_div(2), i256::from(2));
2024        assert_eq!(i256::MAX.saturating_div(-i256::ONE), i256::MIN + 1);
2025        assert_eq!(i256::MIN.saturating_div(-1), i256::MAX);
2026    }
2027
2028    #[test]
2029    fn overflowing_rem_est() {
2030        assert_eq!((i256::from(1), false), i256::from(7).overflowing_rem(i256::from(2i32)));
2031        assert_eq!((i256::ZERO, true), i256::MIN.overflowing_rem(i256::from(-1)));
2032        let res = std::panic::catch_unwind(|| i256::overflowing_rem(i256::MAX, i256::ZERO));
2033        assert!(res.is_err());
2034    }
2035
2036    #[test]
2037    fn wrapping_rem_test() {
2038        assert_eq!(i1024::from(1), i1024::from(7).wrapping_rem(2));
2039        assert_eq!(i512::ZERO, i512::MIN.wrapping_rem(-1));
2040        let res = std::panic::catch_unwind(|| i256::wrapping_rem(i256::MAX, i256::ZERO));
2041        assert!(res.is_err());
2042    }
2043
2044    #[test]
2045    fn checked_rem_test() {
2046        assert_eq!(Some(i1024::from(1)), i1024::from(7).checked_rem(2));
2047        assert_eq!(None, i512::MIN.checked_rem(-1));
2048        assert_eq!(None, i512::MAX.checked_rem(0));
2049    }
2050
2051    #[test]
2052    fn div_euclid_test() {
2053        assert_eq!(i1024::from(1), i1024::from(7).div_euclid(4));
2054        assert_eq!(i1024::from(-1), i1024::from(7).div_euclid(-4));
2055        assert_eq!(i1024::from(-2), i1024::from(-7).div_euclid(4));
2056        assert_eq!(i1024::from(2), i1024::from(-7).div_euclid(-4));
2057    }
2058
2059    #[test]
2060    fn overflowing_div_euclid_test() {
2061        assert_eq!((u512::from(2u8), false), u512::from(5u8).overflowing_div_euclid(2u8));
2062        assert_eq!((i1024::MIN, true), i1024::MIN.overflowing_div_euclid(-1));
2063    }
2064
2065    #[test]
2066    fn wrapping_div_euclid_test() {
2067        assert_eq!(u256::from(10u8), u256::from(100u8).wrapping_div_euclid(10u8));
2068        assert_eq!(i1024::MIN, i1024::MIN.wrapping_div_euclid(-1));
2069    }
2070
2071    #[test]
2072    fn checked_div_euclid_test() {
2073        assert_eq!(None, u256::from(100u8).checked_div_euclid(0u8));
2074        assert_eq!(None, i1024::MIN.checked_div_euclid(-1));
2075        assert_eq!(Some(i1024::from(-3)), i1024::from(6).checked_div_euclid(-2));
2076    }
2077
2078    #[test]
2079    fn rem_euclid_test() {
2080        assert_eq!(i1024::from(3), i1024::from(7).rem_euclid(4));
2081        assert_eq!(i1024::from(1), i1024::from(-7).rem_euclid(4));
2082        assert_eq!(i1024::from(3), i1024::from(7).rem_euclid(-4));
2083        assert_eq!(i1024::from(1), i1024::from(-7).rem_euclid(-4));
2084    }
2085
2086    #[test]
2087    fn overflowing_rem_euclid_test() {
2088        assert_eq!((u512::from(1u8), false), u512::from(5u8).overflowing_rem_euclid(2u8));
2089        assert_eq!((i1024::ZERO, true), i1024::MIN.overflowing_rem_euclid(-1));
2090    }
2091
2092    #[test]
2093    fn wrapping_rem_euclid_test() {
2094        assert_eq!(u256::ZERO, u256::from(100u8).wrapping_rem_euclid(10u8));
2095        assert_eq!(i1024::ZERO, i1024::MIN.wrapping_rem_euclid(-1));
2096    }
2097
2098    #[test]
2099    fn checked_rem_euclid_test() {
2100        assert_eq!(None, u256::from(100u8).checked_rem_euclid(0u8));
2101        assert_eq!(None, i1024::MIN.checked_rem_euclid(-1));
2102        assert_eq!(Some(i1024::from(1)), i1024::from(5).checked_rem_euclid(2));
2103    }
2104
2105    #[test]
2106    fn i256_cmp_test() {
2107        assert!(i256::ZERO < i256::ONE);
2108        assert!(-i256::ONE < i256::ZERO);
2109        assert!(i256::MIN < i256::MAX);
2110        assert!(i256::MIN < i256::ZERO);
2111        assert!(i256::from(200) < i256::from(10000000));
2112        assert!(i256::from(-3) < i256::from(87));
2113    }
2114
2115    #[test]
2116    fn u256_to_u512_test() {
2117        assert_eq!(u512::from(u256::from(30u8)), u512::from(30u8));
2118    }
2119
2120    #[test]
2121    fn leading_zeros_test() {
2122        assert_eq!(u512::ZERO.leading_zeros(), 512);
2123        assert_eq!(u512::ZERO.leading_ones(), 0);
2124        assert_eq!(u512::ZERO.trailing_zeros(), 512);
2125        assert_eq!(u512::ZERO.trailing_ones(), 0);
2126        assert_eq!(u512::MAX.leading_zeros(), 0);
2127        assert_eq!(u512::MAX.leading_ones(), 512);
2128        assert_eq!(u512::MAX.trailing_zeros(), 0);
2129        assert_eq!(u512::MAX.trailing_ones(), 512);
2130        assert_eq!(u256::from(32u8).leading_zeros(), 256 - 6);
2131        assert_eq!(u256::from(32u8).leading_ones(), 0);
2132        assert_eq!(u256::from(32u8).trailing_zeros(), 5);
2133        assert_eq!(u256::from(32u8).trailing_ones(), 0);
2134        assert_eq!(i256::from(-2).leading_zeros(), 0);
2135        assert_eq!(i256::from(-2).leading_ones(), 255);
2136        assert_eq!(i256::from(-2).trailing_zeros(), 1);
2137        assert_eq!(i256::from(-2).trailing_ones(), 0);
2138    }
2139
2140    #[test]
2141    fn checked_shl_test() {
2142        assert_eq!(i256::from(4).checked_shl(0), Some(i256::from(4)));
2143        assert_eq!(i256::from(4).checked_shl(1), Some(i256::from(8)));
2144        assert_eq!(i256::from(1).checked_shl(255), Some(i256::MIN));
2145        assert_eq!(i256::from(4).checked_shl(255), Some(i256::from(0)));
2146        assert_eq!(i256::from(4).checked_shl(256), None);
2147        assert_eq!(u256::from(4u8).checked_shl(0), Some(u256::from(4u8)));
2148        assert_eq!(u256::from(4u8).checked_shl(1), Some(u256::from(8u8)));
2149        assert_eq!(u256::from(4u8).checked_shl(255), Some(u256::from(0u8)));
2150        assert_eq!(u256::from(4u8).checked_shl(256), None);
2151    }
2152
2153    #[test]
2154    fn checked_shr_test() {
2155        assert_eq!(i256::from(4).checked_shr(0), Some(i256::from(4)));
2156        assert_eq!(i256::from(4).checked_shr(1), Some(i256::from(2)));
2157        assert_eq!(i256::from(4).checked_shr(255), Some(i256::from(0)));
2158        assert_eq!(i256::from(4).checked_shr(256), None);
2159        assert_eq!(u256::from(4u8).checked_shr(0), Some(u256::from(4u8)));
2160        assert_eq!(u256::from(4u8).checked_shr(1), Some(u256::from(2u8)));
2161        assert_eq!(u256::from(4u8).checked_shr(255), Some(u256::from(0u8)));
2162        assert_eq!(u256::from(4u8).checked_shr(256), None);
2163    }
2164
2165    #[test]
2166    fn wrapping_neg_test() {
2167        assert_eq!(i256::from(2).wrapping_neg(), i256::from(-2));
2168        assert_eq!(i256::MIN.wrapping_neg(), i256::MIN);
2169        assert_eq!(i256::from(0).wrapping_neg(), i256::from(0));
2170        assert_eq!(u256::from(1u8).wrapping_neg(), u256::MAX);
2171    }
2172}