lambdaworks_math/unsigned_integer/
element.rs

1use core::cmp::Ordering;
2use core::convert::From;
3use core::ops::{
4    Add, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Mul, Shl, Shr, ShrAssign,
5    Sub,
6};
7
8#[cfg(feature = "proptest")]
9use proptest::{
10    arbitrary::Arbitrary,
11    prelude::any,
12    strategy::{SBoxedStrategy, Strategy},
13};
14
15use crate::errors::ByteConversionError;
16use crate::errors::CreationError;
17#[cfg(feature = "alloc")]
18use crate::traits::AsBytes;
19use crate::traits::ByteConversion;
20use crate::unsigned_integer::traits::IsUnsignedInteger;
21
22use core::fmt::{self, Debug, Display};
23
24pub type U384 = UnsignedInteger<6>;
25pub type U256 = UnsignedInteger<4>;
26pub type U128 = UnsignedInteger<2>;
27pub type U64 = UnsignedInteger<1>;
28
29/// A big unsigned integer in base 2^{64} represented
30/// as fixed-size array `limbs` of `u64` components.
31/// The most significant bit is in the left-most position.
32/// That is, the array `[a_n, ..., a_0]` represents the
33/// integer 2^{64 * n} * a_n + ... + 2^{64} * a_1 + a_0.
34#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
35pub struct UnsignedInteger<const NUM_LIMBS: usize> {
36    pub limbs: [u64; NUM_LIMBS],
37}
38
39impl<const NUM_LIMBS: usize> Default for UnsignedInteger<NUM_LIMBS> {
40    fn default() -> Self {
41        Self {
42            limbs: [0; NUM_LIMBS],
43        }
44    }
45}
46
47// NOTE: manually implementing `PartialOrd` may seem unorthodox, but the
48// derived implementation had terrible performance.
49#[allow(clippy::non_canonical_partial_ord_impl)]
50impl<const NUM_LIMBS: usize> PartialOrd for UnsignedInteger<NUM_LIMBS> {
51    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
52        let mut i = 0;
53        while i < NUM_LIMBS {
54            if self.limbs[i] != other.limbs[i] {
55                return Some(self.limbs[i].cmp(&other.limbs[i]));
56            }
57            i += 1;
58        }
59        Some(Ordering::Equal)
60    }
61}
62
63// NOTE: because we implemented `PartialOrd`, clippy asks us to implement
64// this manually too.
65impl<const NUM_LIMBS: usize> Ord for UnsignedInteger<NUM_LIMBS> {
66    fn cmp(&self, other: &Self) -> Ordering {
67        let mut i = 0;
68        while i < NUM_LIMBS {
69            if self.limbs[i] != other.limbs[i] {
70                return self.limbs[i].cmp(&other.limbs[i]);
71            }
72            i += 1;
73        }
74        Ordering::Equal
75    }
76}
77
78impl<const NUM_LIMBS: usize> From<u128> for UnsignedInteger<NUM_LIMBS> {
79    fn from(value: u128) -> Self {
80        let mut limbs = [0u64; NUM_LIMBS];
81        limbs[NUM_LIMBS - 1] = value as u64;
82        limbs[NUM_LIMBS - 2] = (value >> 64) as u64;
83        UnsignedInteger { limbs }
84    }
85}
86
87impl<const NUM_LIMBS: usize> From<u64> for UnsignedInteger<NUM_LIMBS> {
88    fn from(value: u64) -> Self {
89        Self::from_u64(value)
90    }
91}
92
93impl<const NUM_LIMBS: usize> From<u16> for UnsignedInteger<NUM_LIMBS> {
94    fn from(value: u16) -> Self {
95        let mut limbs = [0u64; NUM_LIMBS];
96        limbs[NUM_LIMBS - 1] = value as u64;
97        UnsignedInteger { limbs }
98    }
99}
100
101impl<const NUM_LIMBS: usize> From<&str> for UnsignedInteger<NUM_LIMBS> {
102    fn from(hex_str: &str) -> Self {
103        Self::from_hex_unchecked(hex_str)
104    }
105}
106
107impl<const NUM_LIMBS: usize> Display for UnsignedInteger<NUM_LIMBS> {
108    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
109        let mut limbs_iterator = self.limbs.iter().skip_while(|limb| **limb == 0).peekable();
110
111        if limbs_iterator.peek().is_none() {
112            write!(f, "0x0")?;
113        } else {
114            write!(f, "0x")?;
115            if let Some(most_significant_limb) = limbs_iterator.next() {
116                write!(f, "{:x}", most_significant_limb)?;
117            }
118
119            for limb in limbs_iterator {
120                write!(f, "{:016x}", limb)?;
121            }
122        }
123
124        Ok(())
125    }
126}
127
128// impl Add
129
130impl<const NUM_LIMBS: usize> Add<&UnsignedInteger<NUM_LIMBS>> for &UnsignedInteger<NUM_LIMBS> {
131    type Output = UnsignedInteger<NUM_LIMBS>;
132
133    fn add(self, other: &UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
134        let (result, overflow) = UnsignedInteger::add(self, other);
135        debug_assert!(!overflow, "UnsignedInteger addition overflow.");
136        result
137    }
138}
139
140impl<const NUM_LIMBS: usize> Add<UnsignedInteger<NUM_LIMBS>> for UnsignedInteger<NUM_LIMBS> {
141    type Output = UnsignedInteger<NUM_LIMBS>;
142
143    fn add(self, other: UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
144        &self + &other
145    }
146}
147
148impl<const NUM_LIMBS: usize> Add<&UnsignedInteger<NUM_LIMBS>> for UnsignedInteger<NUM_LIMBS> {
149    type Output = UnsignedInteger<NUM_LIMBS>;
150
151    fn add(self, other: &Self) -> Self {
152        &self + other
153    }
154}
155
156impl<const NUM_LIMBS: usize> Add<UnsignedInteger<NUM_LIMBS>> for &UnsignedInteger<NUM_LIMBS> {
157    type Output = UnsignedInteger<NUM_LIMBS>;
158
159    fn add(self, other: UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
160        self + &other
161    }
162}
163
164// impl Sub
165
166impl<const NUM_LIMBS: usize> Sub<&UnsignedInteger<NUM_LIMBS>> for &UnsignedInteger<NUM_LIMBS> {
167    type Output = UnsignedInteger<NUM_LIMBS>;
168
169    fn sub(self, other: &UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
170        let (result, overflow) = UnsignedInteger::sub(self, other);
171        debug_assert!(!overflow, "UnsignedInteger subtraction overflow.");
172        result
173    }
174}
175
176impl<const NUM_LIMBS: usize> Sub<UnsignedInteger<NUM_LIMBS>> for UnsignedInteger<NUM_LIMBS> {
177    type Output = UnsignedInteger<NUM_LIMBS>;
178
179    fn sub(self, other: UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
180        &self - &other
181    }
182}
183
184impl<const NUM_LIMBS: usize> Sub<&UnsignedInteger<NUM_LIMBS>> for UnsignedInteger<NUM_LIMBS> {
185    type Output = UnsignedInteger<NUM_LIMBS>;
186
187    fn sub(self, other: &Self) -> Self {
188        &self - other
189    }
190}
191
192impl<const NUM_LIMBS: usize> Sub<UnsignedInteger<NUM_LIMBS>> for &UnsignedInteger<NUM_LIMBS> {
193    type Output = UnsignedInteger<NUM_LIMBS>;
194    #[inline(always)]
195    fn sub(self, other: UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
196        self - &other
197    }
198}
199
200/// Multi-precision multiplication.
201/// Algorithm 14.12 of "Handbook of Applied Cryptography" (https://cacr.uwaterloo.ca/hac/)
202impl<const NUM_LIMBS: usize> Mul<&UnsignedInteger<NUM_LIMBS>> for &UnsignedInteger<NUM_LIMBS> {
203    type Output = UnsignedInteger<NUM_LIMBS>;
204
205    #[inline(always)]
206    fn mul(self, other: &UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
207        let (mut n, mut t) = (0, 0);
208        for i in (0..NUM_LIMBS).rev() {
209            if self.limbs[i] != 0u64 {
210                n = NUM_LIMBS - 1 - i;
211            }
212            if other.limbs[i] != 0u64 {
213                t = NUM_LIMBS - 1 - i;
214            }
215        }
216        debug_assert!(
217            n + t < NUM_LIMBS,
218            "UnsignedInteger multiplication overflow."
219        );
220
221        // 1.
222        let mut limbs = [0u64; NUM_LIMBS];
223        // 2.
224        let mut carry = 0u128;
225        for i in 0..=t {
226            // 2.2
227            for j in 0..=n {
228                let uv = (limbs[NUM_LIMBS - 1 - (i + j)] as u128)
229                    + (self.limbs[NUM_LIMBS - 1 - j] as u128)
230                        * (other.limbs[NUM_LIMBS - 1 - i] as u128)
231                    + carry;
232                carry = uv >> 64;
233                limbs[NUM_LIMBS - 1 - (i + j)] = uv as u64;
234            }
235            if i + n + 1 < NUM_LIMBS {
236                // 2.3
237                limbs[NUM_LIMBS - 1 - (i + n + 1)] = carry as u64;
238                carry = 0;
239            }
240        }
241        assert_eq!(carry, 0, "UnsignedInteger multiplication overflow.");
242        // 3.
243        Self::Output { limbs }
244    }
245}
246
247impl<const NUM_LIMBS: usize> Mul<UnsignedInteger<NUM_LIMBS>> for UnsignedInteger<NUM_LIMBS> {
248    type Output = UnsignedInteger<NUM_LIMBS>;
249    #[inline(always)]
250    fn mul(self, other: UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
251        &self * &other
252    }
253}
254
255impl<const NUM_LIMBS: usize> Mul<&UnsignedInteger<NUM_LIMBS>> for UnsignedInteger<NUM_LIMBS> {
256    type Output = UnsignedInteger<NUM_LIMBS>;
257    #[inline(always)]
258    fn mul(self, other: &Self) -> Self {
259        &self * other
260    }
261}
262
263impl<const NUM_LIMBS: usize> Mul<UnsignedInteger<NUM_LIMBS>> for &UnsignedInteger<NUM_LIMBS> {
264    type Output = UnsignedInteger<NUM_LIMBS>;
265    #[inline(always)]
266    fn mul(self, other: UnsignedInteger<NUM_LIMBS>) -> UnsignedInteger<NUM_LIMBS> {
267        self * &other
268    }
269}
270
271impl<const NUM_LIMBS: usize> Shl<usize> for &UnsignedInteger<NUM_LIMBS> {
272    type Output = UnsignedInteger<NUM_LIMBS>;
273    #[inline(always)]
274    fn shl(self, times: usize) -> UnsignedInteger<NUM_LIMBS> {
275        self.const_shl(times)
276    }
277}
278
279impl<const NUM_LIMBS: usize> Shl<usize> for UnsignedInteger<NUM_LIMBS> {
280    type Output = UnsignedInteger<NUM_LIMBS>;
281    #[inline(always)]
282    fn shl(self, times: usize) -> UnsignedInteger<NUM_LIMBS> {
283        &self << times
284    }
285}
286
287// impl Shr
288
289impl<const NUM_LIMBS: usize> Shr<usize> for &UnsignedInteger<NUM_LIMBS> {
290    type Output = UnsignedInteger<NUM_LIMBS>;
291    #[inline(always)]
292    fn shr(self, times: usize) -> UnsignedInteger<NUM_LIMBS> {
293        self.const_shr(times)
294    }
295}
296
297impl<const NUM_LIMBS: usize> Shr<usize> for UnsignedInteger<NUM_LIMBS> {
298    type Output = UnsignedInteger<NUM_LIMBS>;
299    #[inline(always)]
300    fn shr(self, times: usize) -> UnsignedInteger<NUM_LIMBS> {
301        &self >> times
302    }
303}
304
305impl<const NUM_LIMBS: usize> ShrAssign<usize> for UnsignedInteger<NUM_LIMBS> {
306    fn shr_assign(&mut self, times: usize) {
307        debug_assert!(
308            times < 64 * NUM_LIMBS,
309            "UnsignedInteger shift left overflows."
310        );
311
312        let (a, b) = (times / 64, times % 64);
313
314        if b == 0 {
315            self.limbs.copy_within(..NUM_LIMBS - a, a);
316        } else {
317            for i in (a + 1..NUM_LIMBS).rev() {
318                self.limbs[i] = (self.limbs[i - a] >> b) | (self.limbs[i - a - 1] << (64 - b));
319            }
320            self.limbs[a] = self.limbs[0] >> b;
321        }
322
323        for limb in self.limbs.iter_mut().take(a) {
324            *limb = 0;
325        }
326    }
327}
328
329/// Impl BitAnd
330impl<const NUM_LIMBS: usize> BitAnd for UnsignedInteger<NUM_LIMBS> {
331    type Output = Self;
332
333    #[inline(always)]
334    fn bitand(self, rhs: Self) -> Self::Output {
335        let mut result = self;
336        result &= rhs;
337        result
338    }
339}
340
341impl<const NUM_LIMBS: usize> BitAndAssign for UnsignedInteger<NUM_LIMBS> {
342    fn bitand_assign(&mut self, rhs: Self) {
343        for (a_i, b_i) in self.limbs.iter_mut().zip(rhs.limbs.iter()) {
344            *a_i &= b_i;
345        }
346    }
347}
348
349/// Impl BitOr
350impl<const NUM_LIMBS: usize> BitOr for UnsignedInteger<NUM_LIMBS> {
351    type Output = Self;
352
353    #[inline(always)]
354    fn bitor(self, rhs: Self) -> Self::Output {
355        let mut result = self;
356        result |= rhs;
357        result
358    }
359}
360
361impl<const NUM_LIMBS: usize> BitOrAssign for UnsignedInteger<NUM_LIMBS> {
362    #[inline(always)]
363    fn bitor_assign(&mut self, rhs: Self) {
364        for (a_i, b_i) in self.limbs.iter_mut().zip(rhs.limbs.iter()) {
365            *a_i |= b_i;
366        }
367    }
368}
369
370/// Impl BitXor
371impl<const NUM_LIMBS: usize> BitXor for UnsignedInteger<NUM_LIMBS> {
372    type Output = Self;
373
374    #[inline(always)]
375    fn bitxor(self, rhs: Self) -> Self::Output {
376        let mut result = self;
377        result ^= rhs;
378        result
379    }
380}
381
382impl<const NUM_LIMBS: usize> BitXorAssign for UnsignedInteger<NUM_LIMBS> {
383    #[inline(always)]
384    fn bitxor_assign(&mut self, rhs: Self) {
385        for (a_i, b_i) in self.limbs.iter_mut().zip(rhs.limbs.iter()) {
386            *a_i ^= b_i;
387        }
388    }
389}
390
391impl<const NUM_LIMBS: usize> UnsignedInteger<NUM_LIMBS> {
392    pub const fn from_limbs(limbs: [u64; NUM_LIMBS]) -> Self {
393        Self { limbs }
394    }
395
396    #[inline(always)]
397    pub const fn from_u64(value: u64) -> Self {
398        let mut limbs = [0u64; NUM_LIMBS];
399        limbs[NUM_LIMBS - 1] = value;
400        UnsignedInteger { limbs }
401    }
402
403    #[inline(always)]
404    pub const fn from_u128(value: u128) -> Self {
405        let mut limbs = [0u64; NUM_LIMBS];
406        limbs[NUM_LIMBS - 1] = value as u64;
407        limbs[NUM_LIMBS - 2] = (value >> 64) as u64;
408        UnsignedInteger { limbs }
409    }
410
411    #[inline(always)]
412    const fn is_hex_string(string: &str) -> bool {
413        let len: usize = string.len();
414        let bytes = string.as_bytes();
415        let mut i = 0;
416
417        while i < len {
418            match bytes[i] {
419                b'0'..=b'9' => (),
420                b'a'..=b'f' => (),
421                b'A'..=b'F' => (),
422                _ => return false,
423            }
424            i += 1;
425        }
426
427        true
428    }
429
430    /// Creates an `UnsignedInteger` from a hexstring. It can contain `0x` or not.
431    /// Returns an `CreationError::InvalidHexString`if the value is not a hexstring.
432    /// Returns a `CreationError::EmptyString` if the input string is empty.
433    /// Returns a `CreationError::HexStringIsTooBig` if the the input hex string is bigger
434    /// than the maximum amount of characters for this element.
435    pub fn from_hex(value: &str) -> Result<Self, CreationError> {
436        let mut string = value;
437        let mut char_iterator = value.chars();
438        if string.len() > 2
439            && char_iterator.next().unwrap() == '0'
440            && char_iterator.next().unwrap() == 'x'
441        {
442            string = &string[2..];
443        }
444        if string.is_empty() {
445            return Err(CreationError::EmptyString);
446        }
447        if !Self::is_hex_string(string) {
448            return Err(CreationError::InvalidHexString);
449        }
450
451        // Limbs are of 64 bits - 8 bytes
452        // We have 16 nibbles per bytes
453        let max_amount_of_hex_chars = NUM_LIMBS * 16;
454        if string.len() > max_amount_of_hex_chars {
455            return Err(CreationError::HexStringIsTooBig);
456        }
457
458        Ok(Self::from_hex_unchecked(string))
459    }
460
461    /// Creates an `UnsignedInteger` from a hexstring
462    /// # Panics
463    /// Panics if value is not a hexstring. It can contain `0x` or not.
464    pub const fn from_hex_unchecked(value: &str) -> Self {
465        let mut result = [0u64; NUM_LIMBS];
466        let mut limb = 0;
467        let mut limb_index = NUM_LIMBS - 1;
468        let mut shift = 0;
469
470        let value_bytes = value.as_bytes();
471
472        // Remove "0x" if it's at the beginning of the string
473        let mut i = 0;
474        if value_bytes.len() > 2 && value_bytes[0] == b'0' && value_bytes[1] == b'x' {
475            i = 2;
476        }
477
478        let mut j = value_bytes.len();
479        while j > i {
480            j -= 1;
481            limb |= match value_bytes[j] {
482                c @ b'0'..=b'9' => (c as u64 - b'0' as u64) << shift,
483                c @ b'a'..=b'f' => (c as u64 - b'a' as u64 + 10) << shift,
484                c @ b'A'..=b'F' => (c as u64 - b'A' as u64 + 10) << shift,
485                _ => panic!("Malformed hex expression."),
486            };
487            shift += 4;
488            if shift == 64 && limb_index > 0 {
489                result[limb_index] = limb;
490                limb = 0;
491                limb_index -= 1;
492                shift = 0;
493            }
494        }
495
496        result[limb_index] = limb;
497        UnsignedInteger { limbs: result }
498    }
499
500    /// Creates a hexstring from a `FieldElement` without `0x`.
501    #[cfg(feature = "std")]
502    pub fn to_hex(&self) -> String {
503        let mut hex_string = String::new();
504        for &limb in self.limbs.iter() {
505            hex_string.push_str(&format!("{:016X}", limb));
506        }
507        hex_string.trim_start_matches('0').to_string()
508    }
509
510    pub const fn const_ne(a: &UnsignedInteger<NUM_LIMBS>, b: &UnsignedInteger<NUM_LIMBS>) -> bool {
511        let mut i = 0;
512        while i < NUM_LIMBS {
513            if a.limbs[i] != b.limbs[i] {
514                return true;
515            }
516            i += 1;
517        }
518        false
519    }
520
521    pub const fn const_le(a: &UnsignedInteger<NUM_LIMBS>, b: &UnsignedInteger<NUM_LIMBS>) -> bool {
522        let mut i = 0;
523        while i < NUM_LIMBS {
524            if a.limbs[i] < b.limbs[i] {
525                return true;
526            } else if a.limbs[i] > b.limbs[i] {
527                return false;
528            }
529            i += 1;
530        }
531        true
532    }
533
534    pub const fn const_shl(self, times: usize) -> Self {
535        debug_assert!(
536            times < 64 * NUM_LIMBS,
537            "UnsignedInteger shift left overflows."
538        );
539        let mut limbs = [0u64; NUM_LIMBS];
540        let (a, b) = (times / 64, times % 64);
541
542        if b == 0 {
543            let mut i = 0;
544            while i < NUM_LIMBS - a {
545                limbs[i] = self.limbs[a + i];
546                i += 1;
547            }
548            Self { limbs }
549        } else {
550            limbs[NUM_LIMBS - 1 - a] = self.limbs[NUM_LIMBS - 1] << b;
551            let mut i = a + 1;
552            while i < NUM_LIMBS {
553                limbs[NUM_LIMBS - 1 - i] = (self.limbs[NUM_LIMBS - 1 - i + a] << b)
554                    | (self.limbs[NUM_LIMBS - i + a] >> (64 - b));
555                i += 1;
556            }
557            Self { limbs }
558        }
559    }
560
561    pub const fn const_shr(self, times: usize) -> UnsignedInteger<NUM_LIMBS> {
562        debug_assert!(
563            times < 64 * NUM_LIMBS,
564            "UnsignedInteger shift right overflows."
565        );
566
567        let mut limbs = [0u64; NUM_LIMBS];
568        let (a, b) = (times / 64, times % 64);
569
570        if b == 0 {
571            let mut i = 0;
572            while i < NUM_LIMBS - a {
573                limbs[a + i] = self.limbs[i];
574                i += 1;
575            }
576            Self { limbs }
577        } else {
578            limbs[a] = self.limbs[0] >> b;
579            let mut i = a + 1;
580            while i < NUM_LIMBS {
581                limbs[i] = (self.limbs[i - a - 1] << (64 - b)) | (self.limbs[i - a] >> b);
582                i += 1;
583            }
584            Self { limbs }
585        }
586    }
587
588    pub const fn add(
589        a: &UnsignedInteger<NUM_LIMBS>,
590        b: &UnsignedInteger<NUM_LIMBS>,
591    ) -> (UnsignedInteger<NUM_LIMBS>, bool) {
592        let mut limbs = [0u64; NUM_LIMBS];
593        let mut carry = 0u64;
594        let mut i = NUM_LIMBS;
595        while i > 0 {
596            let (x, cb) = a.limbs[i - 1].overflowing_add(b.limbs[i - 1]);
597            let (x, cc) = x.overflowing_add(carry);
598            limbs[i - 1] = x;
599            carry = (cb | cc) as u64;
600            i -= 1;
601        }
602        (UnsignedInteger { limbs }, carry > 0)
603    }
604
605    pub fn double(a: &UnsignedInteger<NUM_LIMBS>) -> (UnsignedInteger<NUM_LIMBS>, bool) {
606        let mut cloned = *a;
607        let overflow = cloned.double_in_place();
608        (cloned, overflow)
609    }
610
611    pub fn double_in_place(&mut self) -> bool {
612        let mut msb_of_previous_limb = 0;
613        for i in (0..NUM_LIMBS).rev() {
614            let limb_ref = &mut self.limbs[i];
615            let msb_of_current_limb = *limb_ref >> 63;
616            *limb_ref <<= 1;
617            *limb_ref |= msb_of_previous_limb;
618            msb_of_previous_limb = msb_of_current_limb;
619        }
620        msb_of_previous_limb != 0
621    }
622
623    /// Multi-precision subtraction.
624    /// Adapted from Algorithm 14.9 of "Handbook of Applied Cryptography" (https://cacr.uwaterloo.ca/hac/)
625    /// Returns the results and a flag that is set if the substraction underflowed
626    #[inline(always)]
627    pub const fn sub(
628        a: &UnsignedInteger<NUM_LIMBS>,
629        b: &UnsignedInteger<NUM_LIMBS>,
630    ) -> (UnsignedInteger<NUM_LIMBS>, bool) {
631        let mut limbs = [0u64; NUM_LIMBS];
632        // 1.
633        let mut carry = false;
634        // 2.
635        let mut i: usize = NUM_LIMBS;
636        while i > 0 {
637            i -= 1;
638            let (x, cb) = a.limbs[i].overflowing_sub(b.limbs[i]);
639            let (x, cc) = x.overflowing_sub(carry as u64);
640            // Casting i128 to u64 drops the most significant bits of i128,
641            // which effectively computes residue modulo 2^{64}
642            // 2.1
643            limbs[i] = x;
644            // 2.2
645            carry = cb | cc;
646        }
647        // 3.
648        (Self { limbs }, carry)
649    }
650
651    /// Multi-precision multiplication.
652    /// Adapted from Algorithm 14.12 of "Handbook of Applied Cryptography" (https://cacr.uwaterloo.ca/hac/)
653    pub const fn mul(
654        a: &UnsignedInteger<NUM_LIMBS>,
655        b: &UnsignedInteger<NUM_LIMBS>,
656    ) -> (UnsignedInteger<NUM_LIMBS>, UnsignedInteger<NUM_LIMBS>) {
657        // 1.
658        let mut hi = [0u64; NUM_LIMBS];
659        let mut lo = [0u64; NUM_LIMBS];
660        // Const functions don't support for loops so we use whiles
661        // this is equivalent to:
662        // for i in (0..NUM_LIMBS).rev()
663        // 2.
664        let mut i = NUM_LIMBS;
665        while i > 0 {
666            i -= 1;
667            // 2.1
668            let mut carry = 0u128;
669            let mut j = NUM_LIMBS;
670            // 2.2
671            while j > 0 {
672                j -= 1;
673                let mut k = i + j;
674                if k >= NUM_LIMBS - 1 {
675                    k -= NUM_LIMBS - 1;
676                    let uv = (lo[k] as u128) + (a.limbs[j] as u128) * (b.limbs[i] as u128) + carry;
677                    carry = uv >> 64;
678                    // Casting u128 to u64 takes modulo 2^{64}
679                    lo[k] = uv as u64;
680                } else {
681                    let uv =
682                        (hi[k + 1] as u128) + (a.limbs[j] as u128) * (b.limbs[i] as u128) + carry;
683                    carry = uv >> 64;
684                    // Casting u128 to u64 takes modulo 2^{64}
685                    hi[k + 1] = uv as u64;
686                }
687            }
688            // 2.3
689            hi[i] = carry as u64;
690        }
691        // 3.
692        (Self { limbs: hi }, Self { limbs: lo })
693    }
694
695    #[inline(always)]
696    pub fn square(
697        a: &UnsignedInteger<NUM_LIMBS>,
698    ) -> (UnsignedInteger<NUM_LIMBS>, UnsignedInteger<NUM_LIMBS>) {
699        // NOTE: we use explicit `while` loops in this function because profiling pointed
700        // at iterators of the form `(<x>..<y>).rev()` as the main performance bottleneck.
701
702        let mut hi = Self {
703            limbs: [0u64; NUM_LIMBS],
704        };
705        let mut lo = Self {
706            limbs: [0u64; NUM_LIMBS],
707        };
708
709        // Compute products between a[i] and a[j] when i != j.
710        // The variable `index` below is the index of `lo` or
711        // `hi` to update
712        let mut i = NUM_LIMBS;
713        while i > 1 {
714            i -= 1;
715            let mut c: u128 = 0;
716            let mut j = i;
717            while j > 0 {
718                j -= 1;
719                let k = i + j;
720                if k >= NUM_LIMBS - 1 {
721                    let index = k + 1 - NUM_LIMBS;
722                    let cs = lo.limbs[index] as u128 + a.limbs[i] as u128 * a.limbs[j] as u128 + c;
723                    c = cs >> 64;
724                    lo.limbs[index] = cs as u64;
725                } else {
726                    let index = k + 1;
727                    let cs = hi.limbs[index] as u128 + a.limbs[i] as u128 * a.limbs[j] as u128 + c;
728                    c = cs >> 64;
729                    hi.limbs[index] = cs as u64;
730                }
731            }
732            hi.limbs[i] = c as u64;
733        }
734
735        // All these terms should appear twice each,
736        // so we have to multiply what we got so far by two.
737        let carry = lo.limbs[0] >> 63;
738        lo = lo << 1;
739        hi = hi << 1;
740        hi.limbs[NUM_LIMBS - 1] |= carry;
741
742        // Add the only remaning terms, which are the squares a[i] * a[i].
743        // The variable `index` below is the index of `lo` or
744        // `hi` to update
745        let mut c = 0;
746        let mut i = NUM_LIMBS;
747        while i > 0 {
748            i -= 1;
749            if NUM_LIMBS - 1 <= i * 2 {
750                let index = 2 * i + 1 - NUM_LIMBS;
751                let cs = lo.limbs[index] as u128 + a.limbs[i] as u128 * a.limbs[i] as u128 + c;
752                c = cs >> 64;
753                lo.limbs[index] = cs as u64;
754            } else {
755                let index = 2 * i + 1;
756                let cs = hi.limbs[index] as u128 + a.limbs[i] as u128 * a.limbs[i] as u128 + c;
757                c = cs >> 64;
758                hi.limbs[index] = cs as u64;
759            }
760            if NUM_LIMBS - 1 < i * 2 {
761                let index = 2 * i - NUM_LIMBS;
762                let cs = lo.limbs[index] as u128 + c;
763                c = cs >> 64;
764                lo.limbs[index] = cs as u64;
765            } else {
766                let index = 2 * i;
767                let cs = hi.limbs[index] as u128 + c;
768                c = cs >> 64;
769                hi.limbs[index] = cs as u64;
770            }
771        }
772        debug_assert_eq!(c, 0);
773        (hi, lo)
774    }
775
776    #[inline(always)]
777    /// Returns the number of bits needed to represent the number (0 for zero).
778    /// If nonzero, this is equivalent to one plus the floored log2 of the number.
779    pub const fn bits(&self) -> u32 {
780        let mut i = NUM_LIMBS;
781        while i > 0 {
782            if self.limbs[i - 1] != 0 {
783                return i as u32 * u64::BITS - self.limbs[i - 1].leading_zeros();
784            }
785            i -= 1;
786        }
787        0
788    }
789
790    /// Returns the truthy value if `self != 0` and the falsy value otherwise.
791    #[inline]
792    const fn ct_is_nonzero(ct: u64) -> u64 {
793        Self::ct_from_lsb((ct | ct.wrapping_neg()) >> (u64::BITS - 1))
794    }
795
796    /// Returns the truthy value if `value == 1`, and the falsy value if `value == 0`.
797    /// Panics for other values.
798    const fn ct_from_lsb(value: u64) -> u64 {
799        debug_assert!(value == 0 || value == 1);
800        value.wrapping_neg()
801    }
802
803    /// Return `b` if `c` is truthy, otherwise return `a`.
804    #[inline]
805    const fn ct_select_limb(a: u64, b: u64, ct: u64) -> u64 {
806        a ^ (ct & (a ^ b))
807    }
808
809    /// Return `b` if `c` is truthy, otherwise return `a`.
810    #[inline]
811    const fn ct_select(a: &Self, b: &Self, c: u64) -> Self {
812        let mut limbs = [0_u64; NUM_LIMBS];
813
814        let mut i = 0;
815        while i < NUM_LIMBS {
816            limbs[i] = Self::ct_select_limb(a.limbs[i], b.limbs[i], c);
817            i += 1;
818        }
819
820        Self { limbs }
821    }
822
823    /// Computes `self - (rhs + borrow)`, returning the result along with the new borrow.
824    #[inline(always)]
825    const fn sbb_limbs(lhs: u64, rhs: u64, borrow: u64) -> (u64, u64) {
826        let a = lhs as u128;
827        let b = rhs as u128;
828        let borrow = (borrow >> (u64::BITS - 1)) as u128;
829        let ret = a.wrapping_sub(b + borrow);
830        (ret as u64, (ret >> u64::BITS) as u64)
831    }
832
833    #[inline(always)]
834    /// Computes `a - (b + borrow)`, returning the result along with the new borrow.
835    pub fn sbb(&self, rhs: &Self, mut borrow: u64) -> (Self, u64) {
836        let mut limbs = [0; NUM_LIMBS];
837
838        for i in (0..NUM_LIMBS).rev() {
839            let (w, b) = Self::sbb_limbs(self.limbs[i], rhs.limbs[i], borrow);
840            limbs[i] = w;
841            borrow = b;
842        }
843
844        (Self { limbs }, borrow)
845    }
846
847    #[inline(always)]
848    /// Returns the number of bits needed to represent the number as little endian
849    pub const fn bits_le(&self) -> usize {
850        let mut i = 0;
851        while i < NUM_LIMBS {
852            if self.limbs[i] != 0 {
853                return u64::BITS as usize * (NUM_LIMBS - i)
854                    - self.limbs[i].leading_zeros() as usize;
855            }
856            i += 1;
857        }
858        0
859    }
860
861    /// Computes self / rhs, returns the quotient, remainder.
862    pub fn div_rem(&self, rhs: &Self) -> (Self, Self) {
863        debug_assert!(
864            *rhs != UnsignedInteger::from_u64(0),
865            "Attempted to divide by zero"
866        );
867        let mb = rhs.bits_le();
868        let mut bd = (NUM_LIMBS * u64::BITS as usize) - mb;
869        let mut rem = *self;
870        let mut quo = Self::from_u64(0);
871        let mut c = rhs.shl(bd);
872
873        loop {
874            let (mut r, borrow) = rem.sbb(&c, 0);
875            debug_assert!(borrow == 0 || borrow == u64::MAX);
876            rem = Self::ct_select(&r, &rem, borrow);
877            r = quo.bitor(Self::from_u64(1));
878            quo = Self::ct_select(&r, &quo, borrow);
879            if bd == 0 {
880                break;
881            }
882            bd -= 1;
883            c = c.shr(1);
884            quo = quo.shl(1);
885        }
886
887        let is_some = Self::ct_is_nonzero(mb as u64);
888        quo = Self::ct_select(&Self::from_u64(0), &quo, is_some);
889        (quo, rem)
890    }
891
892    /// Convert from a decimal string.
893    pub fn from_dec_str(value: &str) -> Result<Self, CreationError> {
894        if value.is_empty() {
895            return Err(CreationError::InvalidDecString);
896        }
897        let mut res = Self::from_u64(0);
898        for b in value.bytes().map(|b| b.wrapping_sub(b'0')) {
899            if b > 9 {
900                return Err(CreationError::InvalidDecString);
901            }
902            let (high, low) = Self::mul(&res, &Self::from(10_u64));
903            if high > Self::from_u64(0) {
904                return Err(CreationError::InvalidDecString);
905            }
906            res = low + Self::from(b as u64);
907        }
908        Ok(res)
909    }
910
911    #[cfg(feature = "proptest")]
912    pub fn nonzero_uint() -> impl Strategy<Value = UnsignedInteger<NUM_LIMBS>> {
913        any_uint::<NUM_LIMBS>().prop_filter("is_zero", |&x| x != UnsignedInteger::from_u64(0))
914    }
915}
916
917impl<const NUM_LIMBS: usize> IsUnsignedInteger for UnsignedInteger<NUM_LIMBS> {}
918
919impl<const NUM_LIMBS: usize> ByteConversion for UnsignedInteger<NUM_LIMBS> {
920    #[cfg(feature = "alloc")]
921    fn to_bytes_be(&self) -> alloc::vec::Vec<u8> {
922        self.limbs
923            .iter()
924            .flat_map(|limb| limb.to_be_bytes())
925            .collect()
926    }
927
928    #[cfg(feature = "alloc")]
929    fn to_bytes_le(&self) -> alloc::vec::Vec<u8> {
930        self.limbs
931            .iter()
932            .rev()
933            .flat_map(|limb| limb.to_le_bytes())
934            .collect()
935    }
936
937    fn from_bytes_be(bytes: &[u8]) -> Result<Self, ByteConversionError> {
938        // We cut off extra bytes, this is useful when you use this function to generate the element from randomness
939        // In the future with the right algorithm this shouldn't be needed
940
941        let needed_bytes = bytes
942            .get(0..NUM_LIMBS * 8)
943            .ok_or(ByteConversionError::FromBEBytesError)?;
944
945        let mut limbs: [u64; NUM_LIMBS] = [0; NUM_LIMBS];
946
947        needed_bytes
948            .chunks_exact(8)
949            .enumerate()
950            .try_for_each(|(i, chunk)| {
951                let limb = u64::from_be_bytes(
952                    chunk
953                        .try_into()
954                        .map_err(|_| ByteConversionError::FromBEBytesError)?,
955                );
956                limbs[i] = limb;
957                Ok::<_, ByteConversionError>(())
958            })?;
959
960        Ok(Self { limbs })
961    }
962
963    fn from_bytes_le(bytes: &[u8]) -> Result<Self, ByteConversionError> {
964        let needed_bytes = bytes
965            .get(0..NUM_LIMBS * 8)
966            .ok_or(ByteConversionError::FromBEBytesError)?;
967
968        let mut limbs: [u64; NUM_LIMBS] = [0; NUM_LIMBS];
969
970        needed_bytes
971            .chunks_exact(8)
972            .rev()
973            .enumerate()
974            .try_for_each(|(i, chunk)| {
975                let limb = u64::from_le_bytes(
976                    chunk
977                        .try_into()
978                        .map_err(|_| ByteConversionError::FromLEBytesError)?,
979                );
980                limbs[i] = limb;
981                Ok::<_, ByteConversionError>(())
982            })?;
983
984        Ok(Self { limbs })
985    }
986}
987
988impl<const NUM_LIMBS: usize> From<UnsignedInteger<NUM_LIMBS>> for u16 {
989    fn from(value: UnsignedInteger<NUM_LIMBS>) -> Self {
990        value.limbs[NUM_LIMBS - 1] as u16
991    }
992}
993
994#[cfg(feature = "alloc")]
995impl<const NUM_LIMBS: usize> AsBytes for UnsignedInteger<NUM_LIMBS> {
996    fn as_bytes(&self) -> alloc::vec::Vec<u8> {
997        self.limbs
998            .into_iter()
999            .fold(alloc::vec::Vec::new(), |mut acc, limb| {
1000                acc.extend_from_slice(&limb.as_bytes());
1001                acc
1002            })
1003    }
1004}
1005
1006#[cfg(feature = "alloc")]
1007impl<const NUM_LIMBS: usize> From<UnsignedInteger<NUM_LIMBS>> for alloc::vec::Vec<u8> {
1008    fn from(val: UnsignedInteger<NUM_LIMBS>) -> Self {
1009        val.as_bytes()
1010    }
1011}
1012
1013#[cfg(feature = "proptest")]
1014fn any_uint<const NUM_LIMBS: usize>() -> impl Strategy<Value = UnsignedInteger<NUM_LIMBS>> {
1015    any::<[u64; NUM_LIMBS]>().prop_map(UnsignedInteger::from_limbs)
1016}
1017
1018#[cfg(feature = "proptest")]
1019impl<const NUM_LIMBS: usize> Arbitrary for UnsignedInteger<NUM_LIMBS> {
1020    type Parameters = ();
1021
1022    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
1023        any_uint::<NUM_LIMBS>().sboxed()
1024    }
1025
1026    type Strategy = SBoxedStrategy<Self>;
1027}
1028
1029#[cfg(test)]
1030mod tests_u384 {
1031    use crate::traits::ByteConversion;
1032    use crate::unsigned_integer::element::{UnsignedInteger, U256, U384};
1033    #[cfg(feature = "proptest")]
1034    use proptest::prelude::*;
1035    #[cfg(feature = "proptest")]
1036    use std::ops::Shr;
1037
1038    #[cfg(feature = "proptest")]
1039    const N_LIMBS: usize = 8;
1040    #[cfg(feature = "proptest")]
1041    type Uint = UnsignedInteger<N_LIMBS>;
1042
1043    #[cfg(feature = "proptest")]
1044    proptest! {
1045        #[test]
1046        fn bitand(a in any::<Uint>(), b in any::<Uint>()) {
1047            let result = a & b;
1048
1049            for i in 0..N_LIMBS {
1050                assert_eq!(result.limbs[i], a.limbs[i] & b.limbs[i]);
1051            }
1052        }
1053
1054        #[test]
1055        fn bitand_assign(a in any::<Uint>(), b in any::<Uint>()) {
1056            let mut result = a;
1057            result &= b;
1058
1059            for i in 0..N_LIMBS {
1060                assert_eq!(result.limbs[i], a.limbs[i] & b.limbs[i]);
1061            }
1062        }
1063
1064        #[test]
1065        fn bitor(a in any::<Uint>(), b in any::<Uint>()) {
1066            let result = a | b;
1067
1068            for i in 0..N_LIMBS {
1069                assert_eq!(result.limbs[i], a.limbs[i] | b.limbs[i]);
1070            }
1071        }
1072
1073        #[test]
1074        fn bitor_assign(a in any::<Uint>(), b in any::<Uint>()) {
1075            let mut result = a;
1076            result |= b;
1077
1078            for i in 0..N_LIMBS {
1079                assert_eq!(result.limbs[i], a.limbs[i] | b.limbs[i]);
1080            }
1081        }
1082
1083        #[test]
1084        fn bitxor(a in any::<Uint>(), b in any::<Uint>()) {
1085            let result = a ^ b;
1086
1087            for i in 0..N_LIMBS {
1088                assert_eq!(result.limbs[i], a.limbs[i] ^ b.limbs[i]);
1089            }
1090        }
1091
1092        #[test]
1093        fn bitxor_assign(a in any::<Uint>(), b in any::<Uint>()) {
1094            let mut result = a;
1095            result ^= b;
1096
1097            for i in 0..N_LIMBS {
1098                assert_eq!(result.limbs[i], a.limbs[i] ^ b.limbs[i]);
1099            }
1100        }
1101
1102        #[test]
1103        fn div_rem(a in any::<Uint>(), b in any::<Uint>()) {
1104            let a = a.shr(256);
1105            let b = b.shr(256);
1106            assert_eq!((a * b).div_rem(&b), (a, Uint::from_u64(0)));
1107        }
1108    }
1109
1110    #[test]
1111    fn construct_new_integer_from_limbs() {
1112        let a: U384 = UnsignedInteger {
1113            limbs: [0, 1, 2, 3, 4, 5],
1114        };
1115        assert_eq!(U384::from_limbs([0, 1, 2, 3, 4, 5]), a);
1116    }
1117
1118    #[test]
1119    fn construct_new_integer_from_u64_1() {
1120        let a = U384::from_u64(1_u64);
1121        assert_eq!(a.limbs, [0, 0, 0, 0, 0, 1]);
1122    }
1123
1124    #[test]
1125    fn construct_new_integer_from_u54_2() {
1126        let a = U384::from_u64(u64::MAX);
1127        assert_eq!(a.limbs, [0, 0, 0, 0, 0, u64::MAX]);
1128    }
1129
1130    #[test]
1131    fn construct_new_integer_from_u128_1() {
1132        let a = U384::from_u128(u128::MAX);
1133        assert_eq!(a.limbs, [0, 0, 0, 0, u64::MAX, u64::MAX]);
1134    }
1135
1136    #[test]
1137    fn construct_new_integer_from_u128_2() {
1138        let a = U384::from_u128(276371540478856090688472252609570374439);
1139        assert_eq!(
1140            a.limbs,
1141            [0, 0, 0, 0, 14982131230017065096, 14596400355126379303]
1142        );
1143    }
1144
1145    #[test]
1146    fn construct_new_integer_from_hex_1() {
1147        let a = U384::from_hex_unchecked("1");
1148        assert_eq!(a.limbs, [0, 0, 0, 0, 0, 1]);
1149    }
1150
1151    #[test]
1152    fn construct_new_integer_from_zero_x_1() {
1153        let a = U384::from_hex_unchecked("0x1");
1154        assert_eq!(a.limbs, [0, 0, 0, 0, 0, 1]);
1155    }
1156
1157    #[test]
1158    fn construct_new_integer_from_hex_2() {
1159        let a = U384::from_hex_unchecked("f");
1160        assert_eq!(a.limbs, [0, 0, 0, 0, 0, 15]);
1161    }
1162
1163    #[test]
1164    fn construct_new_integer_from_hex_3() {
1165        let a = U384::from_hex_unchecked("10000000000000000");
1166        assert_eq!(a.limbs, [0, 0, 0, 0, 1, 0]);
1167    }
1168
1169    #[test]
1170    fn construct_new_integer_from_hex_4() {
1171        let a = U384::from_hex_unchecked("a0000000000000000");
1172        assert_eq!(a.limbs, [0, 0, 0, 0, 10, 0]);
1173    }
1174
1175    #[test]
1176    fn construct_new_integer_from_hex_5() {
1177        let a = U384::from_hex_unchecked("ffffffffffffffffff");
1178        assert_eq!(a.limbs, [0, 0, 0, 0, 255, u64::MAX]);
1179    }
1180
1181    #[test]
1182    fn construct_new_integer_from_hex_6() {
1183        let a = U384::from_hex_unchecked("eb235f6144d9e91f4b14");
1184        assert_eq!(a.limbs, [0, 0, 0, 0, 60195, 6872850209053821716]);
1185    }
1186
1187    #[test]
1188    fn construct_new_integer_from_hex_7() {
1189        let a = U384::from_hex_unchecked("2b20aaa5cf482b239e2897a787faf4660cc95597854beb2");
1190        assert_eq!(
1191            a.limbs,
1192            [
1193                0,
1194                0,
1195                0,
1196                194229460750598834,
1197                4171047363999149894,
1198                6975114134393503410
1199            ]
1200        );
1201    }
1202
1203    #[test]
1204    fn construct_new_integer_from_hex_checked_7() {
1205        let a = U384::from_hex("2b20aaa5cf482b239e2897a787faf4660cc95597854beb2").unwrap();
1206        assert_eq!(
1207            a.limbs,
1208            [
1209                0,
1210                0,
1211                0,
1212                194229460750598834,
1213                4171047363999149894,
1214                6975114134393503410
1215            ]
1216        );
1217    }
1218
1219    #[test]
1220    fn construct_new_integer_from_hex_checked_7_with_zero_x() {
1221        let a = U384::from_hex("0x2b20aaa5cf482b239e2897a787faf4660cc95597854beb2").unwrap();
1222        assert_eq!(
1223            a.limbs,
1224            [
1225                0,
1226                0,
1227                0,
1228                194229460750598834,
1229                4171047363999149894,
1230                6975114134393503410
1231            ]
1232        );
1233    }
1234
1235    #[test]
1236    fn construct_new_integer_from_non_hex_errs() {
1237        assert!(U384::from_hex("0xTEST").is_err());
1238    }
1239
1240    #[test]
1241    fn construct_new_integer_from_empty_string_errs() {
1242        assert!(U384::from_hex("").is_err());
1243    }
1244
1245    #[test]
1246    fn construct_new_integer_from_hex_checked_8() {
1247        let a = U384::from_hex("140f5177b90b4f96b61bb8ccb4f298ad2b20aaa5cf482b239e2897a787faf4660cc95597854beb235f6144d9e91f4b14").unwrap();
1248        assert_eq!(
1249            a.limbs,
1250            [
1251                1445463580056702870,
1252                13122285128622708909,
1253                3107671372009581347,
1254                11396525602857743462,
1255                921361708038744867,
1256                6872850209053821716
1257            ]
1258        );
1259    }
1260
1261    #[test]
1262    fn construct_new_integer_from_hex_8() {
1263        let a = U384::from_hex_unchecked("140f5177b90b4f96b61bb8ccb4f298ad2b20aaa5cf482b239e2897a787faf4660cc95597854beb235f6144d9e91f4b14");
1264        assert_eq!(
1265            a.limbs,
1266            [
1267                1445463580056702870,
1268                13122285128622708909,
1269                3107671372009581347,
1270                11396525602857743462,
1271                921361708038744867,
1272                6872850209053821716
1273            ]
1274        );
1275    }
1276
1277    #[test]
1278    fn from_hex_with_overflowing_hexstring_should_error() {
1279        let u256_from_big_string = U256::from_hex(&"f".repeat(65));
1280        assert!(u256_from_big_string.is_err());
1281        assert!(
1282            u256_from_big_string
1283                == Err(crate::unsigned_integer::element::CreationError::HexStringIsTooBig)
1284        );
1285    }
1286
1287    #[test]
1288    fn from_hex_with_non_overflowing_hexstring_should_work() {
1289        assert_eq!(U256::from_hex(&"0".repeat(64)).unwrap().limbs, [0, 0, 0, 0])
1290    }
1291
1292    #[test]
1293    fn construct_new_integer_from_dec_1() {
1294        let a = U384::from_dec_str("1").unwrap();
1295        assert_eq!(a.limbs, [0, 0, 0, 0, 0, 1]);
1296    }
1297
1298    #[test]
1299    fn construct_new_integer_from_dec_2() {
1300        let a = U384::from_dec_str("15").unwrap();
1301        assert_eq!(a.limbs, [0, 0, 0, 0, 0, 15]);
1302    }
1303
1304    #[test]
1305    fn construct_new_integer_from_dec_3() {
1306        let a = U384::from_dec_str("18446744073709551616").unwrap();
1307        assert_eq!(a.limbs, [0, 0, 0, 0, 1, 0]);
1308    }
1309
1310    #[test]
1311    fn construct_new_integer_from_dec_4() {
1312        let a = U384::from_dec_str("184467440737095516160").unwrap();
1313        assert_eq!(a.limbs, [0, 0, 0, 0, 10, 0]);
1314    }
1315
1316    #[test]
1317    fn construct_new_integer_from_dec_5() {
1318        let a = U384::from_dec_str("4722366482869645213695").unwrap();
1319        assert_eq!(a.limbs, [0, 0, 0, 0, 255, u64::MAX]);
1320    }
1321
1322    #[test]
1323    fn construct_new_integer_from_dec_6() {
1324        let a = U384::from_dec_str("1110408632367155513346836").unwrap();
1325        assert_eq!(a.limbs, [0, 0, 0, 0, 60195, 6872850209053821716]);
1326    }
1327
1328    #[test]
1329    fn construct_new_integer_from_dec_7() {
1330        let a =
1331            U384::from_dec_str("66092860629991288370279803883558073888453977263446474418").unwrap();
1332        assert_eq!(
1333            a.limbs,
1334            [
1335                0,
1336                0,
1337                0,
1338                194229460750598834,
1339                4171047363999149894,
1340                6975114134393503410
1341            ]
1342        );
1343    }
1344
1345    #[test]
1346    fn construct_new_integer_from_dec_8() {
1347        let a = U384::from_dec_str("3087491467896943881295768554872271030441880044814691421073017731442549147034464936390742057449079000462340371991316").unwrap();
1348        assert_eq!(
1349            a.limbs,
1350            [
1351                1445463580056702870,
1352                13122285128622708909,
1353                3107671372009581347,
1354                11396525602857743462,
1355                921361708038744867,
1356                6872850209053821716
1357            ]
1358        );
1359    }
1360
1361    #[test]
1362    fn construct_new_integer_from_dec_empty() {
1363        assert!(U384::from_dec_str("").is_err());
1364    }
1365
1366    #[test]
1367    fn construct_new_integer_from_dec_invalid() {
1368        assert!(U384::from_dec_str("0xff").is_err());
1369    }
1370
1371    #[test]
1372    fn equality_works_1() {
1373        let a = U384::from_hex_unchecked("1");
1374        let b = U384 {
1375            limbs: [0, 0, 0, 0, 0, 1],
1376        };
1377        assert_eq!(a, b);
1378    }
1379    #[test]
1380    fn equality_works_2() {
1381        let a = U384::from_hex_unchecked("f");
1382        let b = U384 {
1383            limbs: [0, 0, 0, 0, 0, 15],
1384        };
1385        assert_eq!(a, b);
1386    }
1387
1388    #[test]
1389    fn equality_works_3() {
1390        let a = U384::from_hex_unchecked("10000000000000000");
1391        let b = U384 {
1392            limbs: [0, 0, 0, 0, 1, 0],
1393        };
1394        assert_eq!(a, b);
1395    }
1396
1397    #[test]
1398    fn equality_works_4() {
1399        let a = U384::from_hex_unchecked("a0000000000000000");
1400        let b = U384 {
1401            limbs: [0, 0, 0, 0, 10, 0],
1402        };
1403        assert_eq!(a, b);
1404    }
1405
1406    #[test]
1407    fn equality_works_5() {
1408        let a = U384::from_hex_unchecked("ffffffffffffffffff");
1409        let b = U384 {
1410            limbs: [0, 0, 0, 0, u8::MAX as u64, u64::MAX],
1411        };
1412        assert_eq!(a, b);
1413    }
1414
1415    #[test]
1416    fn equality_works_6() {
1417        let a = U384::from_hex_unchecked("eb235f6144d9e91f4b14");
1418        let b = U384 {
1419            limbs: [0, 0, 0, 0, 60195, 6872850209053821716],
1420        };
1421        assert_eq!(a, b);
1422    }
1423
1424    #[test]
1425    fn equality_works_7() {
1426        let a = U384::from_hex_unchecked("2b20aaa5cf482b239e2897a787faf4660cc95597854beb2");
1427        let b = U384 {
1428            limbs: [
1429                0,
1430                0,
1431                0,
1432                194229460750598834,
1433                4171047363999149894,
1434                6975114134393503410,
1435            ],
1436        };
1437        assert_eq!(a, b);
1438    }
1439
1440    #[test]
1441    fn equality_works_8() {
1442        let a = U384::from_hex_unchecked("140f5177b90b4f96b61bb8ccb4f298ad2b20aaa5cf482b239e2897a787faf4660cc95597854beb235f6144d9e91f4b14");
1443        let b = U384 {
1444            limbs: [
1445                1445463580056702870,
1446                13122285128622708909,
1447                3107671372009581347,
1448                11396525602857743462,
1449                921361708038744867,
1450                6872850209053821716,
1451            ],
1452        };
1453        assert_eq!(a, b);
1454    }
1455
1456    #[test]
1457    fn equality_works_9() {
1458        let a = U384::from_hex_unchecked("fffffff");
1459        let b = U384::from_hex_unchecked("fefffff");
1460        assert_ne!(a, b);
1461    }
1462
1463    #[test]
1464    fn equality_works_10() {
1465        let a = U384::from_hex_unchecked("ffff000000000000");
1466        let b = U384::from_hex_unchecked("ffff000000100000");
1467        assert_ne!(a, b);
1468    }
1469
1470    #[test]
1471    fn const_ne_works_1() {
1472        let a = U384::from_hex_unchecked("ffff000000000000");
1473        let b = U384::from_hex_unchecked("ffff000000100000");
1474        assert!(U384::const_ne(&a, &b));
1475    }
1476
1477    #[test]
1478    fn const_ne_works_2() {
1479        let a = U384::from_hex_unchecked("140f5177b90b4f96b61bb8ccb4f298ad2b20aaa5cf482b239e2897a787faf4660cc95597854beb235f6144d9e91f4b14");
1480        let b = U384 {
1481            limbs: [
1482                1445463580056702870,
1483                13122285128622708909,
1484                3107671372009581347,
1485                11396525602857743462,
1486                921361708038744867,
1487                6872850209053821716,
1488            ],
1489        };
1490        assert!(!U384::const_ne(&a, &b));
1491    }
1492
1493    #[test]
1494    fn double_two_384_bit_integers() {
1495        let a = U384::from_u64(2);
1496        let b = U384::from_u64(5);
1497        let c = U384::from_u64(7);
1498        assert_eq!(U384::double(&a).0, a + a);
1499        assert_eq!(U384::double(&b).0, b + b);
1500        assert_eq!(U384::double(&c).0, c + c);
1501    }
1502
1503    #[test]
1504    fn add_two_384_bit_integers_1() {
1505        let a = U384::from_u64(2);
1506        let b = U384::from_u64(5);
1507        let c = U384::from_u64(7);
1508        assert_eq!(a + b, c);
1509    }
1510
1511    #[test]
1512    fn add_two_384_bit_integers_2() {
1513        let a = U384::from_u64(334);
1514        let b = U384::from_u64(666);
1515        let c = U384::from_u64(1000);
1516        assert_eq!(a + b, c);
1517    }
1518
1519    #[test]
1520    fn add_two_384_bit_integers_3() {
1521        let a = U384::from_hex_unchecked("ffffffffffffffff");
1522        let b = U384::from_hex_unchecked("1");
1523        let c = U384::from_hex_unchecked("10000000000000000");
1524        assert_eq!(a + b, c);
1525    }
1526
1527    #[test]
1528    fn add_two_384_bit_integers_4() {
1529        let a = U384::from_hex_unchecked("b58e1e0b66");
1530        let b = U384::from_hex_unchecked("55469d9619");
1531        let c = U384::from_hex_unchecked("10ad4bba17f");
1532        assert_eq!(a + b, c);
1533    }
1534
1535    #[test]
1536    fn add_two_384_bit_integers_5() {
1537        let a = U384::from_hex_unchecked("e8dff25cb6160f7705221da6f");
1538        let b = U384::from_hex_unchecked("ab879169b5f80dc8a7969f0b0");
1539        let c = U384::from_hex_unchecked("1946783c66c0e1d3facb8bcb1f");
1540        assert_eq!(a + b, c);
1541    }
1542
1543    #[test]
1544    fn add_two_384_bit_integers_6() {
1545        let a = U384::from_hex_unchecked("9adf291af3a64d59e14e7b440c850508014c551ed5");
1546        let b = U384::from_hex_unchecked("e7948474bce907f0feaf7e5d741a8cd2f6d1fb9448");
1547        let c = U384::from_hex_unchecked("18273ad8fb08f554adffdf9a1809f91daf81e50b31d");
1548        assert_eq!(a + b, c);
1549    }
1550
1551    #[test]
1552    fn add_two_384_bit_integers_7() {
1553        let a = U384::from_hex_unchecked(
1554            "f866aef803c92bf02e85c7fad0eccb4881c59825e499fa22f98e1a8fefed4cd9a03647cd3cc84",
1555        );
1556        let b = U384::from_hex_unchecked(
1557            "9b4000dccf01a010e196154a1b998408f949d734389626ba97cb3331ee87e01dd5badc58f41b2",
1558        );
1559        let c = U384::from_hex_unchecked(
1560            "193a6afd4d2cacc01101bdd44ec864f517b0f6f5a1d3020dd91594dc1de752cf775f1242630e36",
1561        );
1562        assert_eq!(a + b, c);
1563    }
1564
1565    #[test]
1566    fn add_two_384_bit_integers_8() {
1567        let a = U384::from_hex_unchecked("07df9c74fa9d5aafa74a87dbbf93215659d8a3e1706d4b06de9512284802580eb36ae12ea59f90db5b1799d0970a42e");
1568        let b = U384::from_hex_unchecked("d515e54973f0643a6a9957579c1f84020a6a91d5d5f27b75401c7538d2c9ea9cafff44a2c606877d46c49a3433cc85e");
1569        let c = U384::from_hex_unchecked("dcf581be6e8dbeea11e3df335bb2a558644335b7465fc67c1eb187611acc42ab636a25d16ba61858a1dc3404cad6c8c");
1570        assert_eq!(a + b, c);
1571    }
1572
1573    #[test]
1574    fn add_two_384_bit_integers_9() {
1575        let a = U384::from_hex_unchecked("92977527a0f8ba00d18c1b2f1900d965d4a70e5f5f54468ffb2d4d41519385f24b078a0e7d0281d5ad0c36724dc4233");
1576        let b = U384::from_hex_unchecked("46facf9953a9494822bf18836ffd7e55c48b30aa81e17fa1ace0b473015307e4622b8bd6fa68ef654796a183abde842");
1577        let c = U384::from_hex_unchecked("d99244c0f4a20348f44b33b288fe57bb99323f09e135c631a80e01b452e68dd6ad3315e5776b713af4a2d7f5f9a2a75");
1578        assert_eq!(a + b, c);
1579    }
1580
1581    #[test]
1582    fn add_two_384_bit_integers_10() {
1583        let a = U384::from_hex_unchecked("07df9c74fa9d5aafa74a87dbbf93215659d8a3e1706d4b06de9512284802580eb36ae12ea59f90db5b1799d0970a42e");
1584        let b = U384::from_hex_unchecked("d515e54973f0643a6a9957579c1f84020a6a91d5d5f27b75401c7538d2c9ea9cafff44a2c606877d46c49a3433cc85e");
1585        let c_expected = U384::from_hex_unchecked("dcf581be6e8dbeea11e3df335bb2a558644335b7465fc67c1eb187611acc42ab636a25d16ba61858a1dc3404cad6c8c");
1586        let (c, overflow) = U384::add(&a, &b);
1587        assert_eq!(c, c_expected);
1588        assert!(!overflow);
1589    }
1590
1591    #[test]
1592    fn add_two_384_bit_integers_11() {
1593        let a = U384::from_hex_unchecked("92977527a0f8ba00d18c1b2f1900d965d4a70e5f5f54468ffb2d4d41519385f24b078a0e7d0281d5ad0c36724dc4233");
1594        let b = U384::from_hex_unchecked("46facf9953a9494822bf18836ffd7e55c48b30aa81e17fa1ace0b473015307e4622b8bd6fa68ef654796a183abde842");
1595        let c_expected = U384::from_hex_unchecked("d99244c0f4a20348f44b33b288fe57bb99323f09e135c631a80e01b452e68dd6ad3315e5776b713af4a2d7f5f9a2a75");
1596        let (c, overflow) = U384::add(&a, &b);
1597        assert_eq!(c, c_expected);
1598        assert!(!overflow);
1599    }
1600
1601    #[test]
1602    fn add_two_384_bit_integers_12_with_overflow() {
1603        let a = U384::from_hex_unchecked("b07bc844363dd56467d9ebdd5929e9bb34a8e2577db77df6cf8f2ac45bd3d0bc2fc3078d265fe761af51d6aec5b59428");
1604        let b = U384::from_hex_unchecked("cbbc474761bb7995ff54e25fa5d30295604fe3545d0cde405e72d8c0acebb119e9158131679b6c34483a3dafb49deeea");
1605        let c_expected = U384::from_hex_unchecked("7c380f8b97f94efa672ece3cfefcec5094f8c5abdac45c372e02038508bf81d618d888be8dfb5395f78c145e7a538312");
1606        let (c, overflow) = U384::add(&a, &b);
1607        assert_eq!(c, c_expected);
1608        assert!(overflow);
1609    }
1610
1611    #[test]
1612    fn double_384_bit_integer_12_with_overflow() {
1613        let a = U384::from_hex_unchecked("b07bc844363dd56467d9ebdd5929e9bb34a8e2577db77df6cf8f2ac45bd3d0bc2fc3078d265fe761af51d6aec5b59428");
1614        assert_eq!(U384::double(&a), U384::add(&a, &a));
1615    }
1616
1617    #[test]
1618    fn sub_two_384_bit_integers_1() {
1619        let a = U384::from_u64(2);
1620        let b = U384::from_u64(5);
1621        let c = U384::from_u64(7);
1622        assert_eq!(c - a, b);
1623    }
1624
1625    #[test]
1626    fn sub_two_384_bit_integers_2() {
1627        let a = U384::from_u64(334);
1628        let b = U384::from_u64(666);
1629        let c = U384::from_u64(1000);
1630        assert_eq!(c - a, b);
1631    }
1632
1633    #[test]
1634    fn sub_two_384_bit_integers_3() {
1635        let a = U384::from_hex_unchecked("ffffffffffffffff");
1636        let b = U384::from_hex_unchecked("1");
1637        let c = U384::from_hex_unchecked("10000000000000000");
1638        assert_eq!(c - a, b);
1639    }
1640
1641    #[test]
1642    fn sub_two_384_bit_integers_4() {
1643        let a = U384::from_hex_unchecked("b58e1e0b66");
1644        let b = U384::from_hex_unchecked("55469d9619");
1645        let c = U384::from_hex_unchecked("10ad4bba17f");
1646        assert_eq!(c - a, b);
1647    }
1648
1649    #[test]
1650    fn sub_two_384_bit_integers_5() {
1651        let a = U384::from_hex_unchecked("e8dff25cb6160f7705221da6f");
1652        let b = U384::from_hex_unchecked("ab879169b5f80dc8a7969f0b0");
1653        let c = U384::from_hex_unchecked("1946783c66c0e1d3facb8bcb1f");
1654        assert_eq!(c - a, b);
1655    }
1656
1657    #[test]
1658    fn sub_two_384_bit_integers_6() {
1659        let a = U384::from_hex_unchecked("9adf291af3a64d59e14e7b440c850508014c551ed5");
1660        let b = U384::from_hex_unchecked("e7948474bce907f0feaf7e5d741a8cd2f6d1fb9448");
1661        let c = U384::from_hex_unchecked("18273ad8fb08f554adffdf9a1809f91daf81e50b31d");
1662        assert_eq!(c - a, b);
1663    }
1664
1665    #[test]
1666    fn sub_two_384_bit_integers_7() {
1667        let a = U384::from_hex_unchecked(
1668            "f866aef803c92bf02e85c7fad0eccb4881c59825e499fa22f98e1a8fefed4cd9a03647cd3cc84",
1669        );
1670        let b = U384::from_hex_unchecked(
1671            "9b4000dccf01a010e196154a1b998408f949d734389626ba97cb3331ee87e01dd5badc58f41b2",
1672        );
1673        let c = U384::from_hex_unchecked(
1674            "193a6afd4d2cacc01101bdd44ec864f517b0f6f5a1d3020dd91594dc1de752cf775f1242630e36",
1675        );
1676        assert_eq!(c - a, b);
1677    }
1678
1679    #[test]
1680    fn sub_two_384_bit_integers_8() {
1681        let a = U384::from_hex_unchecked("07df9c74fa9d5aafa74a87dbbf93215659d8a3e1706d4b06de9512284802580eb36ae12ea59f90db5b1799d0970a42e");
1682        let b = U384::from_hex_unchecked("d515e54973f0643a6a9957579c1f84020a6a91d5d5f27b75401c7538d2c9ea9cafff44a2c606877d46c49a3433cc85e");
1683        let c = U384::from_hex_unchecked("dcf581be6e8dbeea11e3df335bb2a558644335b7465fc67c1eb187611acc42ab636a25d16ba61858a1dc3404cad6c8c");
1684        assert_eq!(c - a, b);
1685    }
1686
1687    #[test]
1688    fn sub_two_384_bit_integers_9() {
1689        let a = U384::from_hex_unchecked("92977527a0f8ba00d18c1b2f1900d965d4a70e5f5f54468ffb2d4d41519385f24b078a0e7d0281d5ad0c36724dc4233");
1690        let b = U384::from_hex_unchecked("46facf9953a9494822bf18836ffd7e55c48b30aa81e17fa1ace0b473015307e4622b8bd6fa68ef654796a183abde842");
1691        let c = U384::from_hex_unchecked("d99244c0f4a20348f44b33b288fe57bb99323f09e135c631a80e01b452e68dd6ad3315e5776b713af4a2d7f5f9a2a75");
1692        assert_eq!(c - a, b);
1693    }
1694
1695    #[test]
1696    fn sub_two_384_bit_integers_11_without_overflow() {
1697        let a = U384::from_u64(334);
1698        let b_expected = U384::from_u64(666);
1699        let c = U384::from_u64(1000);
1700        let (b, underflow) = U384::sub(&c, &a);
1701        assert!(!underflow);
1702        assert_eq!(b_expected, b);
1703    }
1704
1705    #[test]
1706    fn sub_two_384_bit_integers_11_with_overflow() {
1707        let a = U384::from_u64(334);
1708        let b_expected = U384::from_hex_unchecked("fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd66");
1709        let c = U384::from_u64(1000);
1710        let (b, underflow) = U384::sub(&a, &c);
1711        assert!(underflow);
1712        assert_eq!(b_expected, b);
1713    }
1714
1715    #[test]
1716    fn partial_order_works() {
1717        assert!(U384::from_u64(10) <= U384::from_u64(10));
1718        assert!(U384::from_u64(1) < U384::from_u64(2));
1719        assert!(U384::from_u64(2) >= U384::from_u64(1));
1720
1721        assert!(U384::from_u64(10) >= U384::from_u64(10));
1722        assert!(U384::from_u64(2) > U384::from_u64(1));
1723        assert!(U384::from_u64(1) <= U384::from_u64(2));
1724
1725        let a = U384::from_hex_unchecked("92977527a0f8ba00d18c1b2f1900d965d4a70e5f5f54468ffb2d4d41519385f24b078a0e7d0281d5ad0c36724dc4233");
1726        let c = U384::from_hex_unchecked("d99244c0f4a20348f44b33b288fe57bb99323f09e135c631a80e01b452e68dd6ad3315e5776b713af4a2d7f5f9a2a75");
1727
1728        assert!(&a <= &a);
1729        assert!(&a >= &a);
1730        assert!(&a >= &a);
1731        assert!(&a <= &a);
1732        assert!(&a < &(&a + U384::from_u64(1)));
1733        assert!(&a <= &(&a + U384::from_u64(1)));
1734        assert!(&a + U384::from_u64(1) > a);
1735        assert!((&a + U384::from_u64(1) >= a));
1736        assert!(&a <= &c);
1737        assert!(&a < &c);
1738        assert!(&a < &c);
1739        assert!(&a <= &c);
1740        assert!(&c > &a);
1741        assert!(&c >= &a);
1742        assert!(&c >= &a);
1743        assert!(&c > &a);
1744        assert!(a < c);
1745    }
1746
1747    #[test]
1748    fn mul_two_384_bit_integers_works_1() {
1749        let a = U384::from_u64(3);
1750        let b = U384::from_u64(8);
1751        let c = U384::from_u64(3 * 8);
1752        assert_eq!(a * b, c);
1753    }
1754
1755    #[test]
1756    fn mul_two_384_bit_integers_works_2() {
1757        let a = U384::from_hex_unchecked("6131d99f840b3b0");
1758        let b = U384::from_hex_unchecked("6f5c466db398f43");
1759        let c = U384::from_hex_unchecked("2a47a603a77f871dfbb937af7e5710");
1760        assert_eq!(a * b, c);
1761    }
1762
1763    #[test]
1764    fn mul_two_384_bit_integers_works_3() {
1765        let a = U384::from_hex_unchecked("84a6add5db9e095b2e0f6b40eff8ee");
1766        let b = U384::from_hex_unchecked("2347db918f725461bec2d5c57");
1767        let c = U384::from_hex_unchecked("124805c476c9462adc0df6c88495d4253f5c38033afc18d78d920e2");
1768        assert_eq!(a * b, c);
1769    }
1770
1771    #[test]
1772    fn mul_two_384_bit_integers_works_4() {
1773        let a = U384::from_hex_unchecked("04050753dd7c0b06c404633016f87040");
1774        let b = U384::from_hex_unchecked("dc3830be041b3b4476445fcad3dac0f6f3a53e4ba12da");
1775        let c = U384::from_hex_unchecked(
1776            "375342999dab7f52f4010c4abc2e18b55218015931a55d6053ac39e86e2a47d6b1cb95f41680",
1777        );
1778        assert_eq!(a * b, c);
1779    }
1780
1781    #[test]
1782    fn mul_two_384_bit_integers_works_5() {
1783        let a = U384::from_hex_unchecked("7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8");
1784        let b = U384::from_hex_unchecked("2");
1785        let c_expected = U384::from_hex_unchecked(
1786            "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0",
1787        );
1788        assert_eq!(a * b, c_expected);
1789    }
1790
1791    #[test]
1792    #[should_panic]
1793    fn mul_two_384_bit_integers_works_6() {
1794        let a = U384::from_hex_unchecked("800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
1795        let b = U384::from_hex_unchecked("2");
1796        let _c = a * b;
1797    }
1798
1799    #[test]
1800    fn mul_two_384_bit_integers_works_7_hi_lo() {
1801        let a = U384::from_hex_unchecked("04050753dd7c0b06c404633016f87040");
1802        let b = U384::from_hex_unchecked("dc3830be041b3b4476445fcad3dac0f6f3a53e4ba12da");
1803        let hi_expected = U384::from_hex_unchecked("0");
1804        let lo_expected = U384::from_hex_unchecked(
1805            "375342999dab7f52f4010c4abc2e18b55218015931a55d6053ac39e86e2a47d6b1cb95f41680",
1806        );
1807        let (hi, lo) = U384::mul(&a, &b);
1808        assert_eq!(hi, hi_expected);
1809        assert_eq!(lo, lo_expected);
1810    }
1811
1812    #[test]
1813    fn mul_two_384_bit_integers_works_8_hi_lo() {
1814        let a = U384::from_hex_unchecked("5e2d939b602a50911232731d04fe6f40c05f97da0602307099fb991f9b414e2d52bef130349ec18db1a0215ea6caf76");
1815        let b = U384::from_hex_unchecked("3f3ad1611ab58212f92a2484e9560935b9ac4615fe61cfed1a4861e193a74d20c94f9f88d8b2cc089543c3f699969d9");
1816        let hi_expected = U384::from_hex_unchecked(
1817            "1742daad9c7861dd3499e7ece65467e337937b27e20d641b225bfe00323d33ed62715654eadc092b057a5f19f2ad6c",
1818        );
1819        let lo_expected = U384::from_hex_unchecked("9969c0417b9304d9c16b046c860447d3533999e16710d2e90a44959a168816c015ffb44b987e8cbb82bd46b08d9e2106");
1820        let (hi, lo) = U384::mul(&a, &b);
1821        assert_eq!(hi, hi_expected);
1822        assert_eq!(lo, lo_expected);
1823    }
1824
1825    #[test]
1826    fn mul_two_384_bit_integers_works_9_hi_lo() {
1827        let a = U384::from_hex_unchecked("800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
1828        let b = U384::from_hex_unchecked("2");
1829        let hi_expected = U384::from_hex_unchecked("1");
1830        let lo_expected = U384::from_hex_unchecked("0");
1831        let (hi, lo) = U384::mul(&a, &b);
1832        assert_eq!(hi, hi_expected);
1833        assert_eq!(lo, lo_expected);
1834    }
1835
1836    #[test]
1837    fn shift_left_on_384_bit_integer_works_1() {
1838        let a = U384::from_hex_unchecked("1");
1839        let b = U384::from_hex_unchecked("10");
1840        assert_eq!(a << 4, b);
1841    }
1842
1843    #[test]
1844    fn shift_left_on_384_bit_integer_works_2() {
1845        let a = U384::from_u64(1);
1846        let b = U384::from_u128(1_u128 << 64);
1847        assert_eq!(a << 64, b);
1848    }
1849
1850    #[test]
1851    fn shift_left_on_384_bit_integer_works_3() {
1852        let a = U384::from_hex_unchecked("10");
1853        let b = U384::from_hex_unchecked("1000");
1854        assert_eq!(&a << 8, b);
1855    }
1856
1857    #[test]
1858    fn shift_left_on_384_bit_integer_works_4() {
1859        let a = U384::from_hex_unchecked("e45542992b6844553f3cb1c5ac33e7fa5");
1860        let b = U384::from_hex_unchecked("391550a64ada11154fcf2c716b0cf9fe940");
1861        assert_eq!(a << 6, b);
1862    }
1863
1864    #[test]
1865    fn shift_left_on_384_bit_integer_works_5() {
1866        let a = U384::from_hex_unchecked(
1867            "03303f4d6c2d1caf0c24a6b0239b679a8390aa99bead76bc0093b1bc1a8101f5ce",
1868        );
1869        let b = U384::from_hex_unchecked("6607e9ad85a395e18494d604736cf35072155337d5aed7801276378350203eb9c0000000000000000000000000000000");
1870        assert_eq!(&a << 125, b);
1871    }
1872
1873    #[test]
1874    fn shift_left_on_384_bit_integer_works_6() {
1875        let a = U384::from_hex_unchecked("762e8968bc392ed786ab132f0b5b0cacd385dd51de3a");
1876        let b = U384::from_hex_unchecked(
1877            "762e8968bc392ed786ab132f0b5b0cacd385dd51de3a00000000000000000000000000000000",
1878        );
1879        assert_eq!(&a << (64 * 2), b);
1880    }
1881
1882    #[test]
1883    fn shift_left_on_384_bit_integer_works_7() {
1884        let a = U384::from_hex_unchecked("90823e0bd707f");
1885        let b = U384::from_hex_unchecked(
1886            "90823e0bd707f000000000000000000000000000000000000000000000000",
1887        );
1888        assert_eq!(&a << (64 * 3), b);
1889    }
1890
1891    #[test]
1892    fn shift_right_on_384_bit_integer_works_1() {
1893        let a = U384::from_hex_unchecked("1");
1894        let b = U384::from_hex_unchecked("10");
1895        assert_eq!(b >> 4, a);
1896    }
1897
1898    #[test]
1899    fn shift_right_on_384_bit_integer_works_2() {
1900        let a = U384::from_hex_unchecked("10");
1901        let b = U384::from_hex_unchecked("1000");
1902        assert_eq!(&b >> 8, a);
1903    }
1904
1905    #[test]
1906    fn shift_right_on_384_bit_integer_works_3() {
1907        let a = U384::from_hex_unchecked("e45542992b6844553f3cb1c5ac33e7fa5");
1908        let b = U384::from_hex_unchecked("391550a64ada11154fcf2c716b0cf9fe940");
1909        assert_eq!(b >> 6, a);
1910    }
1911
1912    #[test]
1913    fn shift_right_on_384_bit_integer_works_4() {
1914        let a = U384::from_hex_unchecked(
1915            "03303f4d6c2d1caf0c24a6b0239b679a8390aa99bead76bc0093b1bc1a8101f5ce",
1916        );
1917        let b = U384::from_hex_unchecked("6607e9ad85a395e18494d604736cf35072155337d5aed7801276378350203eb9c0000000000000000000000000000000");
1918        assert_eq!(&b >> 125, a);
1919    }
1920
1921    #[test]
1922    fn shift_right_on_384_bit_integer_works_5() {
1923        let a = U384::from_hex_unchecked("ba6ab46f9a9a2f20e4061b67ce4d8c3da98091cf990d7b14ef47ffe27370abbdeb6a3ce9f9cbf5df1b2430114c8558eb");
1924        let b =
1925            U384::from_hex_unchecked("174d568df35345e41c80c36cf9c9b187b5301239f321af629de8fffc4e6");
1926        assert_eq!(a >> 151, b);
1927    }
1928
1929    #[test]
1930    fn shift_right_on_384_bit_integer_works_6() {
1931        let a = U384::from_hex_unchecked(
1932            "076c075d2f65e39b9ecdde8bf6f8c94241962ce0f557b7739673200c777152eb7e772ad35",
1933        );
1934        let b = U384::from_hex_unchecked("ed80eba5ecbc7373d9bbd17edf19284832c59c1eaaf6ee7");
1935        assert_eq!(&a >> 99, b);
1936    }
1937
1938    #[test]
1939    fn shift_right_on_384_bit_integer_works_7() {
1940        let a = U384::from_hex_unchecked("6a9ce35d8940a5ebd29604ce9a182ade76f03f7e9965760b84a8cfd1d3dd2e612669fe000e58b2af688fd90");
1941        let b = U384::from_hex_unchecked("6a9ce35d8940a5ebd29604ce9a182ade76f03f7");
1942        assert_eq!(&a >> (64 * 3), b);
1943    }
1944
1945    #[test]
1946    fn shift_right_on_384_bit_integer_works_8() {
1947        let a = U384::from_hex_unchecked("5322c128ec84081b6c376c108ebd7fd36bbd44f71ee5e6ad6bcb3dd1c5265bd7db75c90b2665a0826d17600f0e9");
1948        let b =
1949            U384::from_hex_unchecked("5322c128ec84081b6c376c108ebd7fd36bbd44f71ee5e6ad6bcb3dd1c52");
1950        assert_eq!(&a >> (64 * 2), b);
1951    }
1952
1953    #[test]
1954    #[cfg(feature = "alloc")]
1955    fn to_be_bytes_works() {
1956        let number = U384::from_u64(1);
1957        let expected_bytes = [
1958            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1959            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1960        ];
1961
1962        assert_eq!(number.to_bytes_be(), expected_bytes);
1963    }
1964
1965    #[test]
1966    #[cfg(feature = "alloc")]
1967    fn to_le_bytes_works() {
1968        let number = U384::from_u64(1);
1969        let expected_bytes = [
1970            1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1971            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1972        ];
1973
1974        assert_eq!(number.to_bytes_le(), expected_bytes);
1975    }
1976
1977    #[test]
1978    fn from_bytes_be_works() {
1979        let bytes = [
1980            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1981            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1982        ];
1983        let expected_number = U384::from_u64(1);
1984
1985        assert_eq!(U384::from_bytes_be(&bytes).unwrap(), expected_number);
1986    }
1987
1988    #[test]
1989    fn from_bytes_le_works() {
1990        let bytes = [
1991            1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1992            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1993        ];
1994        let expected_number = U384::from_u64(1);
1995
1996        assert_eq!(U384::from_bytes_le(&bytes).unwrap(), expected_number);
1997    }
1998
1999    #[test]
2000    fn from_bytes_be_works_with_extra_data() {
2001        let bytes = [
2002            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2003            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2004        ];
2005        let expected_number = U384::from_u64(0);
2006
2007        assert_eq!(U384::from_bytes_be(&bytes).unwrap(), expected_number);
2008    }
2009
2010    #[test]
2011    #[should_panic]
2012    fn from_bytes_be_errs_with_less_data() {
2013        let bytes = [0, 0, 0, 0, 0];
2014        U384::from_bytes_be(&bytes).unwrap();
2015    }
2016
2017    #[test]
2018    #[should_panic]
2019    fn from_bytes_le_errs_with_less_data() {
2020        let bytes = [0, 0, 0, 0, 0];
2021        U384::from_bytes_le(&bytes).unwrap();
2022    }
2023
2024    #[test]
2025    fn from_bytes_le_works_with_extra_data() {
2026        let bytes = [
2027            1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2028            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,
2029        ];
2030        let expected_number = U384::from_u64(1);
2031
2032        assert_eq!(U384::from_bytes_le(&bytes).unwrap(), expected_number);
2033    }
2034
2035    #[test]
2036    fn test_square_0() {
2037        let a = U384::from_hex_unchecked("362e35606447fb568704026c25da7a304bc7bd0aea36a61d77d4151395078cfa332b9d4928a60721eece725bbc81e158");
2038        let (hi, lo) = U384::square(&a);
2039        assert_eq!(lo, U384::from_hex_unchecked("11724caeb10c4bce5319097d74aed2246e2942b56b7365b5b2f8ceb3bb847db4828862043299d798577996e210bce40"));
2040        assert_eq!(hi, U384::from_hex_unchecked("b7786dbe41375b7ff64dbdc65152ef7d3fdbf499485e26486201cdbfb71b5673c77eb355a1274d08cbfbc1a4cdfdfad"));
2041    }
2042
2043    #[test]
2044    fn test_square_1() {
2045        let a = U384::from_limbs([0, 0, 0, 0, 0, u64::MAX]);
2046        let (hi, lo) = U384::square(&a);
2047        assert_eq!(
2048            lo,
2049            U384::from_hex_unchecked("fffffffffffffffe0000000000000001")
2050        );
2051        assert_eq!(hi, U384::from_hex_unchecked("0"));
2052    }
2053
2054    #[test]
2055    fn test_square_2() {
2056        let a = U384::from_limbs([0, 0, 0, 0, u64::MAX, 0]);
2057        let (hi, lo) = U384::square(&a);
2058        assert_eq!(
2059            lo,
2060            U384::from_hex_unchecked(
2061                "fffffffffffffffe000000000000000100000000000000000000000000000000"
2062            )
2063        );
2064        assert_eq!(hi, U384::from_hex_unchecked("0"));
2065    }
2066
2067    #[test]
2068    fn test_square_3() {
2069        let a = U384::from_limbs([0, 0, 0, u64::MAX, 0, 0]);
2070        let (hi, lo) = U384::square(&a);
2071        assert_eq!(lo, U384::from_hex_unchecked("fffffffffffffffe00000000000000010000000000000000000000000000000000000000000000000000000000000000"));
2072        assert_eq!(hi, U384::from_hex_unchecked("0"));
2073    }
2074
2075    #[test]
2076    fn test_square_4() {
2077        let a = U384::from_limbs([0, 0, u64::MAX, 0, 0, 0]);
2078        let (hi, lo) = U384::square(&a);
2079        assert_eq!(lo, U384::from_hex_unchecked("0"));
2080        assert_eq!(
2081            hi,
2082            U384::from_hex_unchecked("fffffffffffffffe0000000000000001")
2083        );
2084    }
2085
2086    #[test]
2087    fn test_square_5() {
2088        let a = U384::from_limbs([0, 0, u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
2089        let (hi, lo) = U384::square(&a);
2090        assert_eq!(lo, U384::from_hex_unchecked("fffffffffffffffffffffffffffffffe0000000000000000000000000000000000000000000000000000000000000001"));
2091        assert_eq!(
2092            hi,
2093            U384::from_hex_unchecked("ffffffffffffffffffffffffffffffff")
2094        );
2095    }
2096
2097    #[test]
2098    fn test_square_6() {
2099        let a = U384::from_limbs([0, u64::MAX, u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
2100        let (hi, lo) = U384::square(&a);
2101        assert_eq!(lo, U384::from_hex_unchecked("fffffffffffffffe00000000000000000000000000000000000000000000000000000000000000000000000000000001"));
2102        assert_eq!(
2103            hi,
2104            U384::from_hex_unchecked(
2105                "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
2106            )
2107        );
2108    }
2109
2110    #[test]
2111    fn test_square_7() {
2112        let a = U384::from_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
2113        let (hi, lo) = U384::square(&a);
2114        assert_eq!(lo, U384::from_hex_unchecked("1"));
2115        assert_eq!(hi, U384::from_hex_unchecked("fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"));
2116    }
2117}
2118
2119#[cfg(test)]
2120mod tests_u256 {
2121    use crate::unsigned_integer::element::ByteConversion;
2122    use crate::unsigned_integer::element::{UnsignedInteger, U256};
2123    #[cfg(feature = "proptest")]
2124    use proptest::prelude::*;
2125    #[cfg(feature = "proptest")]
2126    use std::ops::Shr;
2127
2128    #[cfg(feature = "proptest")]
2129    const N_LIMBS: usize = 4;
2130    #[cfg(feature = "proptest")]
2131    type Uint = UnsignedInteger<N_LIMBS>;
2132
2133    #[cfg(feature = "proptest")]
2134    proptest! {
2135        #[test]
2136        fn bitand(a in any::<Uint>(), b in any::<Uint>()) {
2137            let result = a & b;
2138
2139            for i in 0..N_LIMBS {
2140                assert_eq!(result.limbs[i], a.limbs[i] & b.limbs[i]);
2141            }
2142        }
2143
2144        #[test]
2145        fn bitand_assign(a in any::<Uint>(), b in any::<Uint>()) {
2146            let mut result = a;
2147            result &= b;
2148
2149            for i in 0..N_LIMBS {
2150                assert_eq!(result.limbs[i], a.limbs[i] & b.limbs[i]);
2151            }
2152        }
2153
2154        #[test]
2155        fn bitor(a in any::<Uint>(), b in any::<Uint>()) {
2156            let result = a | b;
2157
2158            for i in 0..N_LIMBS {
2159                assert_eq!(result.limbs[i], a.limbs[i] | b.limbs[i]);
2160            }
2161        }
2162
2163        #[test]
2164        fn bitor_assign(a in any::<Uint>(), b in any::<Uint>()) {
2165            let mut result = a;
2166            result |= b;
2167
2168            for i in 0..N_LIMBS {
2169                assert_eq!(result.limbs[i], a.limbs[i] | b.limbs[i]);
2170            }
2171        }
2172
2173        #[test]
2174        fn bitxor(a in any::<Uint>(), b in any::<Uint>()) {
2175            let result = a ^ b;
2176
2177            for i in 0..N_LIMBS {
2178                assert_eq!(result.limbs[i], a.limbs[i] ^ b.limbs[i]);
2179            }
2180        }
2181
2182        #[test]
2183        fn bitxor_assign(a in any::<Uint>(), b in any::<Uint>()) {
2184            let mut result = a;
2185            result ^= b;
2186
2187            for i in 0..N_LIMBS {
2188                assert_eq!(result.limbs[i], a.limbs[i] ^ b.limbs[i]);
2189            }
2190        }
2191
2192        #[test]
2193        fn div_rem(a in any::<Uint>(), b in any::<Uint>()) {
2194            let a = a.shr(128);
2195            let b = b.shr(128);
2196            assert_eq!((a * b).div_rem(&b), (a, Uint::from_u64(0)));
2197        }
2198    }
2199
2200    #[test]
2201    fn construct_new_integer_from_limbs() {
2202        let a: U256 = UnsignedInteger {
2203            limbs: [0, 1, 2, 3],
2204        };
2205        assert_eq!(U256::from_limbs([0, 1, 2, 3]), a);
2206    }
2207
2208    #[test]
2209    fn construct_new_integer_from_u64_1() {
2210        let a = U256::from_u64(1_u64);
2211        assert_eq!(a.limbs, [0, 0, 0, 1]);
2212    }
2213
2214    #[test]
2215    fn construct_new_integer_from_u64_2() {
2216        let a = U256::from_u64(u64::MAX);
2217        assert_eq!(a.limbs, [0, 0, 0, u64::MAX]);
2218    }
2219
2220    #[test]
2221    fn construct_new_integer_from_u128_1() {
2222        let a = U256::from_u128(u128::MAX);
2223        assert_eq!(a.limbs, [0, 0, u64::MAX, u64::MAX]);
2224    }
2225
2226    #[test]
2227    fn construct_new_integer_from_u128_4() {
2228        let a = U256::from_u128(276371540478856090688472252609570374439);
2229        assert_eq!(a.limbs, [0, 0, 14982131230017065096, 14596400355126379303]);
2230    }
2231
2232    #[test]
2233    fn construct_new_integer_from_hex_1() {
2234        let a = U256::from_hex_unchecked("1");
2235        assert_eq!(a.limbs, [0, 0, 0, 1]);
2236    }
2237
2238    #[test]
2239    fn construct_new_integer_from_hex_2() {
2240        let a = U256::from_hex_unchecked("f");
2241        assert_eq!(a.limbs, [0, 0, 0, 15]);
2242    }
2243
2244    #[test]
2245    fn construct_new_integer_from_hex_3() {
2246        let a = U256::from_hex_unchecked("10000000000000000");
2247        assert_eq!(a.limbs, [0, 0, 1, 0]);
2248    }
2249
2250    #[test]
2251    fn construct_new_integer_from_hex_4() {
2252        let a = U256::from_hex_unchecked("a0000000000000000");
2253        assert_eq!(a.limbs, [0, 0, 10, 0]);
2254    }
2255
2256    #[test]
2257    fn construct_new_integer_from_hex_5() {
2258        let a = U256::from_hex_unchecked("ffffffffffffffffff");
2259        assert_eq!(a.limbs, [0, 0, 255, u64::MAX]);
2260    }
2261
2262    #[test]
2263    fn construct_new_integer_from_hex_6() {
2264        let a = U256::from_hex_unchecked("eb235f6144d9e91f4b14");
2265        assert_eq!(a.limbs, [0, 0, 60195, 6872850209053821716]);
2266    }
2267
2268    #[test]
2269    fn construct_new_integer_from_hex_7() {
2270        let a = U256::from_hex_unchecked("2b20aaa5cf482b239e2897a787faf4660cc95597854beb2");
2271        assert_eq!(
2272            a.limbs,
2273            [
2274                0,
2275                194229460750598834,
2276                4171047363999149894,
2277                6975114134393503410
2278            ]
2279        );
2280    }
2281
2282    #[test]
2283    fn construct_new_integer_from_hex_8() {
2284        let a = U256::from_hex_unchecked(
2285            "2B20AAA5CF482B239E2897A787FAF4660CC95597854BEB235F6144D9E91F4B14",
2286        );
2287        assert_eq!(
2288            a.limbs,
2289            [
2290                3107671372009581347,
2291                11396525602857743462,
2292                921361708038744867,
2293                6872850209053821716
2294            ]
2295        );
2296    }
2297
2298    #[test]
2299    fn construct_new_integer_from_dec_1() {
2300        let a = U256::from_dec_str("1").unwrap();
2301        assert_eq!(a.limbs, [0, 0, 0, 1]);
2302    }
2303
2304    #[test]
2305    fn construct_integer_from_invalid_hex_returns_error() {
2306        use crate::unsigned_integer::element::CreationError;
2307        assert_eq!(U256::from_hex("0xaO"), Err(CreationError::InvalidHexString));
2308        assert_eq!(U256::from_hex("0xOa"), Err(CreationError::InvalidHexString));
2309        assert_eq!(U256::from_hex("0xm"), Err(CreationError::InvalidHexString));
2310    }
2311
2312    #[test]
2313    fn construct_new_integer_from_dec_2() {
2314        let a = U256::from_dec_str("15").unwrap();
2315        assert_eq!(a.limbs, [0, 0, 0, 15]);
2316    }
2317
2318    #[test]
2319    fn construct_new_integer_from_dec_3() {
2320        let a = U256::from_dec_str("18446744073709551616").unwrap();
2321        assert_eq!(a.limbs, [0, 0, 1, 0]);
2322    }
2323
2324    #[test]
2325    fn construct_new_integer_from_dec_4() {
2326        let a = U256::from_dec_str("184467440737095516160").unwrap();
2327        assert_eq!(a.limbs, [0, 0, 10, 0]);
2328    }
2329
2330    #[test]
2331    fn construct_new_integer_from_dec_5() {
2332        let a = U256::from_dec_str("4722366482869645213695").unwrap();
2333        assert_eq!(a.limbs, [0, 0, 255, u64::MAX]);
2334    }
2335
2336    #[test]
2337    fn construct_new_integer_from_dec_6() {
2338        let a = U256::from_dec_str("1110408632367155513346836").unwrap();
2339        assert_eq!(a.limbs, [0, 0, 60195, 6872850209053821716]);
2340    }
2341
2342    #[test]
2343    fn construct_new_integer_from_dec_7() {
2344        let a =
2345            U256::from_dec_str("66092860629991288370279803883558073888453977263446474418").unwrap();
2346        assert_eq!(
2347            a.limbs,
2348            [
2349                0,
2350                194229460750598834,
2351                4171047363999149894,
2352                6975114134393503410
2353            ]
2354        );
2355    }
2356
2357    #[test]
2358    fn construct_new_integer_from_dec_8() {
2359        let a = U256::from_dec_str(
2360            "19507169362252850253634654373914901165934018806002526957372506333098895428372",
2361        )
2362        .unwrap();
2363        assert_eq!(
2364            a.limbs,
2365            [
2366                3107671372009581347,
2367                11396525602857743462,
2368                921361708038744867,
2369                6872850209053821716
2370            ]
2371        );
2372    }
2373
2374    #[test]
2375    fn construct_new_integer_from_dec_empty() {
2376        assert!(U256::from_dec_str("").is_err());
2377    }
2378
2379    #[test]
2380    fn construct_new_integer_from_dec_invalid() {
2381        assert!(U256::from_dec_str("0xff").is_err());
2382    }
2383
2384    #[test]
2385    fn equality_works_1() {
2386        let a = U256::from_hex_unchecked("1");
2387        let b = U256 {
2388            limbs: [0, 0, 0, 1],
2389        };
2390        assert_eq!(a, b);
2391    }
2392    #[test]
2393    fn equality_works_2() {
2394        let a = U256::from_hex_unchecked("f");
2395        let b = U256 {
2396            limbs: [0, 0, 0, 15],
2397        };
2398        assert_eq!(a, b);
2399    }
2400
2401    #[test]
2402    fn equality_works_3() {
2403        let a = U256::from_hex_unchecked("10000000000000000");
2404        let b = U256 {
2405            limbs: [0, 0, 1, 0],
2406        };
2407        assert_eq!(a, b);
2408    }
2409
2410    #[test]
2411    fn equality_works_4() {
2412        let a = U256::from_hex_unchecked("a0000000000000000");
2413        let b = U256 {
2414            limbs: [0, 0, 10, 0],
2415        };
2416        assert_eq!(a, b);
2417    }
2418
2419    #[test]
2420    fn equality_works_5() {
2421        let a = U256::from_hex_unchecked("ffffffffffffffffff");
2422        let b = U256 {
2423            limbs: [0, 0, u8::MAX as u64, u64::MAX],
2424        };
2425        assert_eq!(a, b);
2426    }
2427
2428    #[test]
2429    fn equality_works_6() {
2430        let a = U256::from_hex_unchecked("eb235f6144d9e91f4b14");
2431        let b = U256 {
2432            limbs: [0, 0, 60195, 6872850209053821716],
2433        };
2434        assert_eq!(a, b);
2435    }
2436
2437    #[test]
2438    fn equality_works_7() {
2439        let a = U256::from_hex_unchecked("2b20aaa5cf482b239e2897a787faf4660cc95597854beb2");
2440        let b = U256 {
2441            limbs: [
2442                0,
2443                194229460750598834,
2444                4171047363999149894,
2445                6975114134393503410,
2446            ],
2447        };
2448        assert_eq!(a, b);
2449    }
2450
2451    #[test]
2452    fn equality_works_8() {
2453        let a = U256::from_hex_unchecked(
2454            "2B20AAA5CF482B239E2897A787FAF4660CC95597854BEB235F6144D9E91F4B14",
2455        );
2456        let b = U256 {
2457            limbs: [
2458                3107671372009581347,
2459                11396525602857743462,
2460                921361708038744867,
2461                6872850209053821716,
2462            ],
2463        };
2464        assert_eq!(a, b);
2465    }
2466
2467    #[test]
2468    fn equality_works_9() {
2469        let a = U256::from_hex_unchecked("fffffff");
2470        let b = U256::from_hex_unchecked("fefffff");
2471        assert_ne!(a, b);
2472    }
2473
2474    #[test]
2475    fn equality_works_10() {
2476        let a = U256::from_hex_unchecked("ffff000000000000");
2477        let b = U256::from_hex_unchecked("ffff000000100000");
2478        assert_ne!(a, b);
2479    }
2480
2481    #[test]
2482    fn double_256_bit_integer_1() {
2483        let a = U256::from_u64(2);
2484        let b = U256::from_u64(5);
2485        let c = U256::from_u64(7);
2486        assert_eq!(U256::double(&a).0, a + a);
2487        assert_eq!(U256::double(&b).0, b + b);
2488        assert_eq!(U256::double(&c).0, c + c);
2489    }
2490
2491    #[test]
2492    fn add_two_256_bit_integers_1() {
2493        let a = U256::from_u64(2);
2494        let b = U256::from_u64(5);
2495        let c = U256::from_u64(7);
2496        assert_eq!(a + b, c);
2497    }
2498
2499    #[test]
2500    fn add_two_256_bit_integers_2() {
2501        let a = U256::from_u64(334);
2502        let b = U256::from_u64(666);
2503        let c = U256::from_u64(1000);
2504        assert_eq!(a + b, c);
2505    }
2506
2507    #[test]
2508    fn add_two_256_bit_integers_3() {
2509        let a = U256::from_hex_unchecked("ffffffffffffffff");
2510        let b = U256::from_hex_unchecked("1");
2511        let c = U256::from_hex_unchecked("10000000000000000");
2512        assert_eq!(a + b, c);
2513    }
2514
2515    #[test]
2516    fn add_two_256_bit_integers_4() {
2517        let a = U256::from_hex_unchecked("b58e1e0b66");
2518        let b = U256::from_hex_unchecked("55469d9619");
2519        let c = U256::from_hex_unchecked("10ad4bba17f");
2520        assert_eq!(a + b, c);
2521    }
2522
2523    #[test]
2524    fn add_two_256_bit_integers_5() {
2525        let a = U256::from_hex_unchecked("e8dff25cb6160f7705221da6f");
2526        let b = U256::from_hex_unchecked("ab879169b5f80dc8a7969f0b0");
2527        let c = U256::from_hex_unchecked("1946783c66c0e1d3facb8bcb1f");
2528        assert_eq!(a + b, c);
2529    }
2530
2531    #[test]
2532    fn add_two_256_bit_integers_6() {
2533        let a = U256::from_hex_unchecked("9adf291af3a64d59e14e7b440c850508014c551ed5");
2534        let b = U256::from_hex_unchecked("e7948474bce907f0feaf7e5d741a8cd2f6d1fb9448");
2535        let c = U256::from_hex_unchecked("18273ad8fb08f554adffdf9a1809f91daf81e50b31d");
2536        assert_eq!(a + b, c);
2537    }
2538
2539    #[test]
2540    fn add_two_256_bit_integers_7() {
2541        let a = U256::from_hex_unchecked(
2542            "10d3bc05496380cfe27bf5d97ddb99ac95eb5ecfbd3907eadf877a4c2dfa05f6",
2543        );
2544        let b = U256::from_hex_unchecked(
2545            "0866aef803c92bf02e85c7fad0eccb4881c59825e499fa22f98e1a8fefed4cd9",
2546        );
2547        let c = U256::from_hex_unchecked(
2548            "193a6afd4d2cacc01101bdd44ec864f517b0f6f5a1d3020dd91594dc1de752cf",
2549        );
2550        assert_eq!(a + b, c);
2551    }
2552
2553    #[test]
2554    fn add_two_256_bit_integers_8() {
2555        let a = U256::from_hex_unchecked(
2556            "07df9c74fa9d5aafa74a87dbbf93215659d8a3e1706d4b06de9512284802580f",
2557        );
2558        let b = U256::from_hex_unchecked(
2559            "d515e54973f0643a6a9957579c1f84020a6a91d5d5f27b75401c7538d2c9ea9c",
2560        );
2561        let c = U256::from_hex_unchecked(
2562            "dcf581be6e8dbeea11e3df335bb2a558644335b7465fc67c1eb187611acc42ab",
2563        );
2564        assert_eq!(a + b, c);
2565    }
2566
2567    #[test]
2568    fn add_two_256_bit_integers_9() {
2569        let a = U256::from_hex_unchecked(
2570            "92977527a0f8ba00d18c1b2f1900d965d4a70e5f5f54468ffb2d4d41519385f2",
2571        );
2572        let b = U256::from_hex_unchecked(
2573            "46facf9953a9494822bf18836ffd7e55c48b30aa81e17fa1ace0b473015307e4",
2574        );
2575        let c = U256::from_hex_unchecked(
2576            "d99244c0f4a20348f44b33b288fe57bb99323f09e135c631a80e01b452e68dd6",
2577        );
2578        assert_eq!(a + b, c);
2579    }
2580
2581    #[test]
2582    fn add_two_256_bit_integers_10() {
2583        let a = U256::from_hex_unchecked(
2584            "07df9c74fa9d5aafa74a87dbbf93215659d8a3e1706d4b06de9512284802580f",
2585        );
2586        let b = U256::from_hex_unchecked(
2587            "d515e54973f0643a6a9957579c1f84020a6a91d5d5f27b75401c7538d2c9ea9c",
2588        );
2589        let c_expected = U256::from_hex_unchecked(
2590            "dcf581be6e8dbeea11e3df335bb2a558644335b7465fc67c1eb187611acc42ab",
2591        );
2592        let (c, overflow) = U256::add(&a, &b);
2593        assert_eq!(c, c_expected);
2594        assert!(!overflow);
2595    }
2596
2597    #[test]
2598    fn add_two_256_bit_integers_11() {
2599        let a = U256::from_hex_unchecked(
2600            "92977527a0f8ba00d18c1b2f1900d965d4a70e5f5f54468ffb2d4d41519385f2",
2601        );
2602        let b = U256::from_hex_unchecked(
2603            "46facf9953a9494822bf18836ffd7e55c48b30aa81e17fa1ace0b473015307e4",
2604        );
2605        let c_expected = U256::from_hex_unchecked(
2606            "d99244c0f4a20348f44b33b288fe57bb99323f09e135c631a80e01b452e68dd6",
2607        );
2608        let (c, overflow) = U256::add(&a, &b);
2609        assert_eq!(c, c_expected);
2610        assert!(!overflow);
2611    }
2612
2613    #[test]
2614    fn add_two_256_bit_integers_12_with_overflow() {
2615        let a = U256::from_hex_unchecked(
2616            "b07bc844363dd56467d9ebdd5929e9bb34a8e2577db77df6cf8f2ac45bd3d0bc",
2617        );
2618        let b = U256::from_hex_unchecked(
2619            "cbbc474761bb7995ff54e25fa5d30295604fe3545d0cde405e72d8c0acebb119",
2620        );
2621        let c_expected = U256::from_hex_unchecked(
2622            "7c380f8b97f94efa672ece3cfefcec5094f8c5abdac45c372e02038508bf81d5",
2623        );
2624        let (c, overflow) = U256::add(&a, &b);
2625        assert_eq!(c, c_expected);
2626        assert!(overflow);
2627    }
2628
2629    #[test]
2630    fn double_256_bit_integer_12_with_overflow() {
2631        let a = U256::from_hex_unchecked(
2632            "b07bc844363dd56467d9ebdd5929e9bb34a8e2577db77df6cf8f2ac45bd3d0bc",
2633        );
2634        let b = U256::from_hex_unchecked(
2635            "cbbc474761bb7995ff54e25fa5d30295604fe3545d0cde405e72d8c0acebb119",
2636        );
2637        assert_eq!(U256::double(&a), U256::add(&a, &a));
2638        assert_eq!(U256::double(&b), U256::add(&b, &b));
2639    }
2640
2641    #[test]
2642    fn sub_two_256_bit_integers_1() {
2643        let a = U256::from_u64(2);
2644        let b = U256::from_u64(5);
2645        let c = U256::from_u64(7);
2646        assert_eq!(c - a, b);
2647    }
2648
2649    #[test]
2650    fn sub_two_256_bit_integers_2() {
2651        let a = U256::from_u64(334);
2652        let b = U256::from_u64(666);
2653        let c = U256::from_u64(1000);
2654        assert_eq!(c - a, b);
2655    }
2656
2657    #[test]
2658    fn sub_two_256_bit_integers_3() {
2659        let a = U256::from_hex_unchecked("ffffffffffffffff");
2660        let b = U256::from_hex_unchecked("1");
2661        let c = U256::from_hex_unchecked("10000000000000000");
2662        assert_eq!(c - a, b);
2663    }
2664
2665    #[test]
2666    fn sub_two_256_bit_integers_4() {
2667        let a = U256::from_hex_unchecked("b58e1e0b66");
2668        let b = U256::from_hex_unchecked("55469d9619");
2669        let c = U256::from_hex_unchecked("10ad4bba17f");
2670        assert_eq!(c - a, b);
2671    }
2672
2673    #[test]
2674    fn sub_two_256_bit_integers_5() {
2675        let a = U256::from_hex_unchecked("e8dff25cb6160f7705221da6f");
2676        let b = U256::from_hex_unchecked("ab879169b5f80dc8a7969f0b0");
2677        let c = U256::from_hex_unchecked("1946783c66c0e1d3facb8bcb1f");
2678        assert_eq!(c - a, b);
2679    }
2680
2681    #[test]
2682    fn sub_two_256_bit_integers_6() {
2683        let a = U256::from_hex_unchecked("9adf291af3a64d59e14e7b440c850508014c551ed5");
2684        let b = U256::from_hex_unchecked("e7948474bce907f0feaf7e5d741a8cd2f6d1fb9448");
2685        let c = U256::from_hex_unchecked("18273ad8fb08f554adffdf9a1809f91daf81e50b31d");
2686        assert_eq!(c - a, b);
2687    }
2688
2689    #[test]
2690    fn sub_two_256_bit_integers_7() {
2691        let a = U256::from_hex_unchecked(
2692            "9b4000dccf01a010e196154a1b998408f949d734389626ba97cb3331ee87e01d",
2693        );
2694        let b = U256::from_hex_unchecked(
2695            "5d26ae1b34c78bdf4cefb2b0b553473f887bc0f1ac03d36861c2e75e01656cbc",
2696        );
2697        let c = U256::from_hex_unchecked(
2698            "f866aef803c92bf02e85c7fad0eccb4881c59825e499fa22f98e1a8fefed4cd9",
2699        );
2700        assert_eq!(c - a, b);
2701    }
2702
2703    #[test]
2704    fn sub_two_256_bit_integers_8() {
2705        let a = U256::from_hex_unchecked(
2706            "07df9c74fa9d5aafa74a87dbbf93215659d8a3e1706d4b06de9512284802580e",
2707        );
2708        let b = U256::from_hex_unchecked(
2709            "d515e54973f0643a6a9957579c1f84020a6a91d5d5f27b75401c7538d2c9ea9d",
2710        );
2711        let c = U256::from_hex_unchecked(
2712            "dcf581be6e8dbeea11e3df335bb2a558644335b7465fc67c1eb187611acc42ab",
2713        );
2714        assert_eq!(c - a, b);
2715    }
2716
2717    #[test]
2718    fn sub_two_256_bit_integers_9() {
2719        let a = U256::from_hex_unchecked(
2720            "92977527a0f8ba00d18c1b2f1900d965d4a70e5f5f54468ffb2d4d41519385f2",
2721        );
2722        let b = U256::from_hex_unchecked(
2723            "46facf9953a9494822bf18836ffd7e55c48b30aa81e17fa1ace0b473015307e4",
2724        );
2725        let c = U256::from_hex_unchecked(
2726            "d99244c0f4a20348f44b33b288fe57bb99323f09e135c631a80e01b452e68dd6",
2727        );
2728        assert_eq!(c - a, b);
2729    }
2730
2731    #[test]
2732    fn sub_two_256_bit_integers_11_without_overflow() {
2733        let a = U256::from_u64(334);
2734        let b_expected = U256::from_u64(666);
2735        let c = U256::from_u64(1000);
2736        let (b, overflow) = U256::sub(&c, &a);
2737        assert!(!overflow);
2738        assert_eq!(b_expected, b);
2739    }
2740
2741    #[test]
2742    fn sub_two_256_bit_integers_11_with_overflow() {
2743        let a = U256::from_u64(334);
2744        let b_expected = U256::from_hex_unchecked(
2745            "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd66",
2746        );
2747        let c = U256::from_u64(1000);
2748        let (b, overflow) = U256::sub(&a, &c);
2749        assert!(overflow);
2750        assert_eq!(b_expected, b);
2751    }
2752
2753    #[test]
2754    fn const_le_works() {
2755        let a = U256::from_u64(334);
2756        let b = U256::from_u128(333);
2757        assert!(U256::const_le(&b, &a));
2758        assert!(U256::const_le(&a, &a));
2759        assert!(!U256::const_le(&a, &b));
2760    }
2761
2762    #[test]
2763    fn partial_order_works() {
2764        assert!(U256::from_u64(10) <= U256::from_u64(10));
2765        assert!(U256::from_u64(1) < U256::from_u64(2));
2766        assert!(U256::from_u64(2) >= U256::from_u64(1));
2767
2768        assert!(U256::from_u64(10) >= U256::from_u64(10));
2769        assert!(U256::from_u64(2) > U256::from_u64(1));
2770        assert!(U256::from_u64(1) <= U256::from_u64(2));
2771
2772        let a = U256::from_hex_unchecked(
2773            "5d4a70e5f5f54468ffb2d4d41519385f24b078a0e7d0281d5ad0c36724dc4233",
2774        );
2775        let c = U256::from_hex_unchecked(
2776            "b99323f09e135c631a80e01b452e68dd6ad3315e5776b713af4a2d7f5f9a2a75",
2777        );
2778
2779        assert!(&a <= &a);
2780        assert!(&a >= &a);
2781        assert!(&a >= &a);
2782        assert!(&a <= &a);
2783        assert!(&a < &(&a + U256::from_u64(1)));
2784        assert!(&a <= &(&a + U256::from_u64(1)));
2785        assert!(&a + U256::from_u64(1) > a);
2786        assert!((&a + U256::from_u64(1) >= a));
2787        assert!(&a <= &c);
2788        assert!(&a < &c);
2789        assert!(&a < &c);
2790        assert!(&a <= &c);
2791        assert!(&c > &a);
2792        assert!(&c >= &a);
2793        assert!(&c >= &a);
2794        assert!(&c > &a);
2795        assert!(a < c);
2796    }
2797
2798    #[test]
2799    fn mul_two_256_bit_integers_works_1() {
2800        let a = U256::from_u64(3);
2801        let b = U256::from_u64(8);
2802        let c = U256::from_u64(3 * 8);
2803        assert_eq!(a * b, c);
2804    }
2805
2806    #[test]
2807    fn mul_two_256_bit_integers_works_2() {
2808        let a = U256::from_hex_unchecked("6131d99f840b3b0");
2809        let b = U256::from_hex_unchecked("6f5c466db398f43");
2810        let c = U256::from_hex_unchecked("2a47a603a77f871dfbb937af7e5710");
2811        assert_eq!(a * b, c);
2812    }
2813
2814    #[test]
2815    fn mul_two_256_bit_integers_works_3() {
2816        let a = U256::from_hex_unchecked("84a6add5db9e095b2e0f6b40eff8ee");
2817        let b = U256::from_hex_unchecked("2347db918f725461bec2d5c57");
2818        let c = U256::from_hex_unchecked("124805c476c9462adc0df6c88495d4253f5c38033afc18d78d920e2");
2819        assert_eq!(a * b, c);
2820    }
2821
2822    #[test]
2823    fn mul_two_256_bit_integers_works_4() {
2824        let a = U256::from_hex_unchecked("15bf61fcf53a3f0ae1e8e555d");
2825        let b = U256::from_hex_unchecked("cbbc474761bb7995ff54e25fa5d5d0cde405e9f");
2826        let c_expected = U256::from_hex_unchecked(
2827            "114ec14db0c80d30b7dcb9c45948ef04cc149e612cb544f447b146553aff2ac3",
2828        );
2829        assert_eq!(a * b, c_expected);
2830    }
2831
2832    #[test]
2833    fn mul_two_256_bit_integers_works_5_hi_lo() {
2834        let a = U256::from_hex_unchecked(
2835            "8e2d939b602a50911232731d04fe6f40c05f97da0602307099fb991f9b414e2d",
2836        );
2837        let b = U256::from_hex_unchecked(
2838            "7f3ad1611ab58212f92a2484e9560935b9ac4615fe61cfed1a4861e193a74d20",
2839        );
2840        let hi_expected = U256::from_hex_unchecked(
2841            "46A946D6A984FE6507DE6B8D1354256D7A7BAE4283404733BDC876A264BCE5EE",
2842        );
2843        let lo_expected = U256::from_hex_unchecked(
2844            "43F24263F10930EBE3EA0307466C19B13B9C7DBA6B3F7604B7F32FB0E3084EA0",
2845        );
2846        let (hi, lo) = U256::mul(&a, &b);
2847        assert_eq!(hi, hi_expected);
2848        assert_eq!(lo, lo_expected);
2849    }
2850
2851    #[test]
2852    fn shift_left_on_256_bit_integer_works_1() {
2853        let a = U256::from_hex_unchecked("1");
2854        let b = U256::from_hex_unchecked("10");
2855        assert_eq!(a << 4, b);
2856    }
2857
2858    #[test]
2859    fn shift_left_on_256_bit_integer_works_2() {
2860        let a = U256::from_u64(1);
2861        let b = U256::from_u128(1_u128 << 64);
2862        assert_eq!(a << 64, b);
2863    }
2864
2865    #[test]
2866    fn shift_left_on_256_bit_integer_works_3() {
2867        let a = U256::from_hex_unchecked("10");
2868        let b = U256::from_hex_unchecked("1000");
2869        assert_eq!(&a << 8, b);
2870    }
2871
2872    #[test]
2873    fn shift_left_on_256_bit_integer_works_4() {
2874        let a = U256::from_hex_unchecked("e45542992b6844553f3cb1c5ac33e7fa5");
2875        let b = U256::from_hex_unchecked("391550a64ada11154fcf2c716b0cf9fe940");
2876        assert_eq!(a << 6, b);
2877    }
2878
2879    #[test]
2880    fn shift_left_on_256_bit_integer_works_5() {
2881        let a = U256::from_hex_unchecked("a8390aa99bead76bc0093b1bc1a8101f5ce");
2882        let b = U256::from_hex_unchecked(
2883            "72155337d5aed7801276378350203eb9c0000000000000000000000000000000",
2884        );
2885        assert_eq!(&a << 125, b);
2886    }
2887
2888    #[test]
2889    fn shift_left_on_256_bit_integer_works_6() {
2890        let a = U256::from_hex_unchecked("2ed786ab132f0b5b0cacd385dd51de3a");
2891        let b = U256::from_hex_unchecked(
2892            "2ed786ab132f0b5b0cacd385dd51de3a00000000000000000000000000000000",
2893        );
2894        assert_eq!(&a << (64 * 2), b);
2895    }
2896
2897    #[test]
2898    fn shift_left_on_256_bit_integer_works_7() {
2899        let a = U256::from_hex_unchecked("90823e0bd707f");
2900        let b = U256::from_hex_unchecked(
2901            "90823e0bd707f000000000000000000000000000000000000000000000000",
2902        );
2903        assert_eq!(&a << (64 * 3), b);
2904    }
2905
2906    #[test]
2907    fn shift_right_on_256_bit_integer_works_1() {
2908        let a = U256::from_hex_unchecked("1");
2909        let b = U256::from_hex_unchecked("10");
2910        assert_eq!(b >> 4, a);
2911    }
2912
2913    #[test]
2914    fn shift_right_on_256_bit_integer_works_2() {
2915        let a = U256::from_hex_unchecked("10");
2916        let b = U256::from_hex_unchecked("1000");
2917        assert_eq!(&b >> 8, a);
2918    }
2919
2920    #[test]
2921    fn shift_right_on_256_bit_integer_works_3() {
2922        let a = U256::from_hex_unchecked("e45542992b6844553f3cb1c5ac33e7fa5");
2923        let b = U256::from_hex_unchecked("391550a64ada11154fcf2c716b0cf9fe940");
2924        assert_eq!(b >> 6, a);
2925    }
2926
2927    #[test]
2928    fn shift_right_on_256_bit_integer_works_4() {
2929        let a = U256::from_hex_unchecked("390aa99bead76bc0093b1bc1a8101f5ce");
2930        let b = U256::from_hex_unchecked(
2931            "72155337d5aed7801276378350203eb9c0000000000000000000000000000000",
2932        );
2933        assert_eq!(&b >> 125, a);
2934    }
2935
2936    #[test]
2937    fn shift_right_on_256_bit_integer_works_5() {
2938        let a = U256::from_hex_unchecked(
2939            "ba6ab46f9a9a2f20e4061b67ce4d8c3da98091cf990d7b14ef47ffe27370abbd",
2940        );
2941        let b = U256::from_hex_unchecked("174d568df35345e41c80c36cf9c");
2942        assert_eq!(a >> 151, b);
2943    }
2944
2945    #[test]
2946    fn shift_right_on_256_bit_integer_works_6() {
2947        let a = U256::from_hex_unchecked(
2948            "076c075d2f65e39b9ecdde8bf6f8c94241962ce0f557b7739673200c777152eb",
2949        );
2950        let b = U256::from_hex_unchecked("ed80eba5ecbc7373d9bbd17edf19284832c59c");
2951        assert_eq!(&a >> 99, b);
2952    }
2953
2954    #[test]
2955    fn shift_right_on_256_bit_integer_works_7() {
2956        let a = U256::from_hex_unchecked(
2957            "6a9ce35d8940a5ebd29604ce9a182ade76f03f7e9965760b84a8cfd1d3dd2e61",
2958        );
2959        let b = U256::from_hex_unchecked("6a9ce35d8940a5eb");
2960        assert_eq!(&a >> (64 * 3), b);
2961    }
2962
2963    #[test]
2964    fn shift_right_on_256_bit_integer_works_8() {
2965        let a = U256::from_hex_unchecked(
2966            "5322c128ec84081b6c376c108ebd7fd36bbd44f71ee5e6ad6bcb3dd1c5265bd7",
2967        );
2968        let b = U256::from_hex_unchecked("5322c128ec84081b6c376c108ebd7fd3");
2969        assert_eq!(&a >> (64 * 2), b);
2970    }
2971
2972    #[test]
2973    #[cfg(feature = "alloc")]
2974    fn to_be_bytes_works() {
2975        let number = U256::from_u64(1);
2976        let expected_bytes = [
2977            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2978            0, 0, 1,
2979        ];
2980
2981        assert_eq!(number.to_bytes_be(), expected_bytes);
2982    }
2983
2984    #[test]
2985    #[cfg(feature = "alloc")]
2986    fn to_le_bytes_works() {
2987        let number = U256::from_u64(1);
2988        let expected_bytes = [
2989            1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2990            0, 0, 0,
2991        ];
2992
2993        assert_eq!(number.to_bytes_le(), expected_bytes);
2994    }
2995
2996    #[test]
2997    fn from_bytes_be_works() {
2998        let bytes = [
2999            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3000            0, 0, 1,
3001        ];
3002        let expected_number = U256::from_u64(1);
3003        assert_eq!(U256::from_bytes_be(&bytes).unwrap(), expected_number);
3004    }
3005
3006    #[test]
3007    fn from_bytes_le_works() {
3008        let bytes = [
3009            1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3010            0, 0, 0,
3011        ];
3012        let expected_number = U256::from_u64(1);
3013        assert_eq!(U256::from_bytes_le(&bytes).unwrap(), expected_number);
3014    }
3015
3016    #[test]
3017    fn shr_inplace_works_1() {
3018        let mut n = UnsignedInteger::<3>::from(4u64);
3019        n >>= 1;
3020
3021        assert_eq!(n, UnsignedInteger::<3>::from(2u64));
3022    }
3023
3024    #[test]
3025    fn shr_inplace_on_256_bit_integer_works_1() {
3026        let a = U256::from_hex_unchecked("e45542992b6844553f3cb1c5ac33e7fa5");
3027        let mut b = U256::from_hex_unchecked("391550a64ada11154fcf2c716b0cf9fe940");
3028        b >>= 6;
3029        assert_eq!(a, b);
3030    }
3031
3032    #[test]
3033    fn shr_inplace_on_254_bit_integer_works_2() {
3034        let a = U256::from_hex_unchecked("390aa99bead76bc0093b1bc1a8101f5ce");
3035        let mut b = U256::from_hex_unchecked(
3036            "72155337d5aed7801276378350203eb9c0000000000000000000000000000000",
3037        );
3038        b >>= 125;
3039        assert_eq!(a, b);
3040    }
3041
3042    #[test]
3043    fn shr_inplace_on_256_bit_integer_works_3() {
3044        let a = U256::from_hex_unchecked("2ed786ab132f0b5b0cacd385dd51de3a");
3045        let mut b = U256::from_hex_unchecked(
3046            "2ed786ab132f0b5b0cacd385dd51de3a00000000000000000000000000000000",
3047        );
3048        b >>= 64 * 2;
3049        assert_eq!(a, b);
3050    }
3051
3052    #[test]
3053    fn shr_inplace_on_256_bit_integer_works_4() {
3054        let a = U256::from_hex_unchecked("90823e0bd707f");
3055        let mut b = U256::from_hex_unchecked(
3056            "90823e0bd707f000000000000000000000000000000000000000000000000",
3057        );
3058        b >>= 64 * 3;
3059        assert_eq!(a, b);
3060    }
3061
3062    #[test]
3063    fn shr_inplace_on_256_bit_integer_works_5() {
3064        let a = U256::from_hex_unchecked("24208f");
3065        let mut b = U256::from_hex_unchecked(
3066            "90823e0bd707f000000000000000000000000000000000000000000000000",
3067        );
3068        b >>= 222;
3069        assert_eq!(a, b);
3070    }
3071
3072    #[test]
3073    fn multiplying_and_dividing_for_number_is_number_with_remainder_0() {
3074        let a = U256::from_u128(12678920202929299999999999282828);
3075        let b = U256::from_u128(9000000000000);
3076        assert_eq!((a * b).div_rem(&b), (a, U256::from_u64(0)));
3077    }
3078
3079    #[test]
3080    fn unsigned_int_8_div_rem_3_is_2_2() {
3081        let a: UnsignedInteger<4> = U256::from_u64(8);
3082        let b = U256::from_u64(3);
3083        assert_eq!(a.div_rem(&b), (U256::from_u64(2), U256::from_u64(2)));
3084    }
3085
3086    #[test]
3087    fn unsigned_int_500721_div_rem_5_is_100144_1() {
3088        let a = U256::from_u64(500721);
3089        let b = U256::from_u64(5);
3090        assert_eq!(a.div_rem(&b), (U256::from_u64(100144), U256::from_u64(1)));
3091    }
3092
3093    #[test]
3094    fn div_rem_works_with_big_numbers() {
3095        let a = U256::from_u128(4758402376589578934275873583589345);
3096        let b = U256::from_u128(43950384634609);
3097        assert_eq!(
3098            a.div_rem(&b),
3099            (
3100                U256::from_u128(108267593472721187331),
3101                U256::from_u128(12368508650766)
3102            )
3103        );
3104    }
3105
3106    #[cfg(feature = "std")]
3107    #[test]
3108    fn to_hex_test() {
3109        let a = U256::from_hex_unchecked("390aa99bead76bc0093b1bc1a8101f5ce");
3110        assert_eq!(U256::to_hex(&a), "390AA99BEAD76BC0093B1BC1A8101F5CE")
3111    }
3112}