arrow_buffer/bigint/
mod.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18use crate::arith::derive_arith;
19use crate::bigint::div::div_rem;
20use num_bigint::BigInt;
21use num_traits::{
22    Bounded, CheckedAdd, CheckedDiv, CheckedMul, CheckedNeg, CheckedRem, CheckedSub, FromPrimitive,
23    Num, One, Signed, ToPrimitive, WrappingAdd, WrappingMul, WrappingNeg, WrappingSub, Zero,
24    cast::AsPrimitive,
25};
26use std::cmp::Ordering;
27use std::num::ParseIntError;
28use std::ops::{BitAnd, BitOr, BitXor, Neg, Shl, Shr};
29use std::str::FromStr;
30
31mod div;
32
33/// An opaque error similar to [`std::num::ParseIntError`]
34#[derive(Debug)]
35pub struct ParseI256Error {}
36
37impl From<ParseIntError> for ParseI256Error {
38    fn from(_: ParseIntError) -> Self {
39        Self {}
40    }
41}
42
43impl std::fmt::Display for ParseI256Error {
44    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
45        write!(f, "Failed to parse as i256")
46    }
47}
48impl std::error::Error for ParseI256Error {}
49
50/// Error returned by i256::DivRem
51enum DivRemError {
52    /// Division by zero
53    DivideByZero,
54    /// Division overflow
55    DivideOverflow,
56}
57
58/// A signed 256-bit integer
59#[allow(non_camel_case_types)]
60#[derive(Copy, Clone, Default, Eq, PartialEq, Hash)]
61#[repr(C)]
62pub struct i256 {
63    low: u128,
64    high: i128,
65}
66
67impl std::fmt::Debug for i256 {
68    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
69        write!(f, "{self}")
70    }
71}
72
73impl std::fmt::Display for i256 {
74    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
75        write!(f, "{}", BigInt::from_signed_bytes_le(&self.to_le_bytes()))
76    }
77}
78
79impl FromStr for i256 {
80    type Err = ParseI256Error;
81
82    fn from_str(s: &str) -> Result<Self, Self::Err> {
83        // i128 can store up to 38 decimal digits
84        if s.len() <= 38 {
85            return Ok(Self::from_i128(i128::from_str(s)?));
86        }
87
88        let (negative, s) = match s.as_bytes()[0] {
89            b'-' => (true, &s[1..]),
90            b'+' => (false, &s[1..]),
91            _ => (false, s),
92        };
93
94        // Trim leading 0s
95        let s = s.trim_start_matches('0');
96        if s.is_empty() {
97            return Ok(i256::ZERO);
98        }
99
100        if !s.as_bytes()[0].is_ascii_digit() {
101            // Ensures no duplicate sign
102            return Err(ParseI256Error {});
103        }
104
105        parse_impl(s, negative)
106    }
107}
108
109impl From<i8> for i256 {
110    fn from(value: i8) -> Self {
111        Self::from_i128(value.into())
112    }
113}
114
115impl From<i16> for i256 {
116    fn from(value: i16) -> Self {
117        Self::from_i128(value.into())
118    }
119}
120
121impl From<i32> for i256 {
122    fn from(value: i32) -> Self {
123        Self::from_i128(value.into())
124    }
125}
126
127impl From<i64> for i256 {
128    fn from(value: i64) -> Self {
129        Self::from_i128(value.into())
130    }
131}
132
133/// Parse `s` with any sign and leading 0s removed
134fn parse_impl(s: &str, negative: bool) -> Result<i256, ParseI256Error> {
135    if s.len() <= 38 {
136        let low = i128::from_str(s)?;
137        return Ok(match negative {
138            true => i256::from_parts(low.neg() as _, -1),
139            false => i256::from_parts(low as _, 0),
140        });
141    }
142
143    let split = s.len() - 38;
144    if !s.as_bytes()[split].is_ascii_digit() {
145        // Ensures not splitting codepoint and no sign
146        return Err(ParseI256Error {});
147    }
148    let (hs, ls) = s.split_at(split);
149
150    let mut low = i128::from_str(ls)?;
151    let high = parse_impl(hs, negative)?;
152
153    if negative {
154        low = -low;
155    }
156
157    let low = i256::from_i128(low);
158
159    high.checked_mul(i256::from_i128(10_i128.pow(38)))
160        .and_then(|high| high.checked_add(low))
161        .ok_or(ParseI256Error {})
162}
163
164impl PartialOrd for i256 {
165    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
166        Some(self.cmp(other))
167    }
168}
169
170impl Ord for i256 {
171    fn cmp(&self, other: &Self) -> Ordering {
172        // This is 25x faster than using a variable length encoding such
173        // as BigInt as it avoids allocation and branching
174        self.high.cmp(&other.high).then(self.low.cmp(&other.low))
175    }
176}
177
178impl i256 {
179    /// The additive identity for this integer type, i.e. `0`.
180    pub const ZERO: Self = i256 { low: 0, high: 0 };
181
182    /// The multiplicative identity for this integer type, i.e. `1`.
183    pub const ONE: Self = i256 { low: 1, high: 0 };
184
185    /// The multiplicative inverse for this integer type, i.e. `-1`.
186    pub const MINUS_ONE: Self = i256 {
187        low: u128::MAX,
188        high: -1,
189    };
190
191    /// The maximum value that can be represented by this integer type
192    pub const MAX: Self = i256 {
193        low: u128::MAX,
194        high: i128::MAX,
195    };
196
197    /// The minimum value that can be represented by this integer type
198    pub const MIN: Self = i256 {
199        low: u128::MIN,
200        high: i128::MIN,
201    };
202
203    /// Create an integer value from its representation as a byte array in little-endian.
204    #[inline]
205    pub const fn from_le_bytes(b: [u8; 32]) -> Self {
206        let (low, high) = split_array(b);
207        Self {
208            high: i128::from_le_bytes(high),
209            low: u128::from_le_bytes(low),
210        }
211    }
212
213    /// Create an integer value from its representation as a byte array in big-endian.
214    #[inline]
215    pub const fn from_be_bytes(b: [u8; 32]) -> Self {
216        let (high, low) = split_array(b);
217        Self {
218            high: i128::from_be_bytes(high),
219            low: u128::from_be_bytes(low),
220        }
221    }
222
223    /// Create an `i256` value from a 128-bit value.
224    pub const fn from_i128(v: i128) -> Self {
225        Self::from_parts(v as u128, v >> 127)
226    }
227
228    /// Create an integer value from its representation as string.
229    #[inline]
230    pub fn from_string(value_str: &str) -> Option<Self> {
231        value_str.parse().ok()
232    }
233
234    /// Create an optional i256 from the provided `f64`. Returning `None`
235    /// if overflow occurred
236    pub fn from_f64(v: f64) -> Option<Self> {
237        BigInt::from_f64(v).and_then(|i| {
238            let (integer, overflow) = i256::from_bigint_with_overflow(i);
239            if overflow { None } else { Some(integer) }
240        })
241    }
242
243    /// Create an i256 from the provided low u128 and high i128
244    #[inline]
245    pub const fn from_parts(low: u128, high: i128) -> Self {
246        Self { low, high }
247    }
248
249    /// Returns this `i256` as a low u128 and high i128
250    pub const fn to_parts(self) -> (u128, i128) {
251        (self.low, self.high)
252    }
253
254    /// Converts this `i256` into an `i128` returning `None` if this would result
255    /// in truncation/overflow
256    pub fn to_i128(self) -> Option<i128> {
257        let as_i128 = self.low as i128;
258
259        let high_negative = self.high < 0;
260        let low_negative = as_i128 < 0;
261        let high_valid = self.high == -1 || self.high == 0;
262
263        (high_negative == low_negative && high_valid).then_some(self.low as i128)
264    }
265
266    /// Wraps this `i256` into an `i128`
267    pub fn as_i128(self) -> i128 {
268        self.low as i128
269    }
270
271    /// Return the memory representation of this integer as a byte array in little-endian byte order.
272    #[inline]
273    pub const fn to_le_bytes(self) -> [u8; 32] {
274        let low = self.low.to_le_bytes();
275        let high = self.high.to_le_bytes();
276        let mut t = [0; 32];
277        let mut i = 0;
278        while i != 16 {
279            t[i] = low[i];
280            t[i + 16] = high[i];
281            i += 1;
282        }
283        t
284    }
285
286    /// Return the memory representation of this integer as a byte array in big-endian byte order.
287    #[inline]
288    pub const fn to_be_bytes(self) -> [u8; 32] {
289        let low = self.low.to_be_bytes();
290        let high = self.high.to_be_bytes();
291        let mut t = [0; 32];
292        let mut i = 0;
293        while i != 16 {
294            t[i] = high[i];
295            t[i + 16] = low[i];
296            i += 1;
297        }
298        t
299    }
300
301    /// Create an i256 from the provided [`BigInt`] returning a bool indicating
302    /// if overflow occurred
303    fn from_bigint_with_overflow(v: BigInt) -> (Self, bool) {
304        let v_bytes = v.to_signed_bytes_le();
305        match v_bytes.len().cmp(&32) {
306            Ordering::Less => {
307                let mut bytes = if num_traits::Signed::is_negative(&v) {
308                    [255_u8; 32]
309                } else {
310                    [0; 32]
311                };
312                bytes[0..v_bytes.len()].copy_from_slice(&v_bytes[..v_bytes.len()]);
313                (Self::from_le_bytes(bytes), false)
314            }
315            Ordering::Equal => (Self::from_le_bytes(v_bytes.try_into().unwrap()), false),
316            Ordering::Greater => (Self::from_le_bytes(v_bytes[..32].try_into().unwrap()), true),
317        }
318    }
319
320    /// Computes the absolute value of this i256
321    #[inline]
322    pub fn wrapping_abs(self) -> Self {
323        // -1 if negative, otherwise 0
324        let sa = self.high >> 127;
325        let sa = Self::from_parts(sa as u128, sa);
326
327        // Inverted if negative
328        Self::from_parts(self.low ^ sa.low, self.high ^ sa.high).wrapping_sub(sa)
329    }
330
331    /// Computes the absolute value of this i256 returning `None` if `Self == Self::MIN`
332    #[inline]
333    pub fn checked_abs(self) -> Option<Self> {
334        (self != Self::MIN).then(|| self.wrapping_abs())
335    }
336
337    /// Negates this i256
338    #[inline]
339    pub fn wrapping_neg(self) -> Self {
340        Self::from_parts(!self.low, !self.high).wrapping_add(i256::ONE)
341    }
342
343    /// Negates this i256 returning `None` if `Self == Self::MIN`
344    #[inline]
345    pub fn checked_neg(self) -> Option<Self> {
346        (self != Self::MIN).then(|| self.wrapping_neg())
347    }
348
349    /// Performs wrapping addition
350    #[inline]
351    pub fn wrapping_add(self, other: Self) -> Self {
352        let (low, carry) = self.low.overflowing_add(other.low);
353        let high = self.high.wrapping_add(other.high).wrapping_add(carry as _);
354        Self { low, high }
355    }
356
357    /// Performs checked addition
358    #[inline]
359    pub fn checked_add(self, other: Self) -> Option<Self> {
360        let r = self.wrapping_add(other);
361        ((other.is_negative() && r < self) || (!other.is_negative() && r >= self)).then_some(r)
362    }
363
364    /// Performs wrapping subtraction
365    #[inline]
366    pub fn wrapping_sub(self, other: Self) -> Self {
367        let (low, carry) = self.low.overflowing_sub(other.low);
368        let high = self.high.wrapping_sub(other.high).wrapping_sub(carry as _);
369        Self { low, high }
370    }
371
372    /// Performs checked subtraction
373    #[inline]
374    pub fn checked_sub(self, other: Self) -> Option<Self> {
375        let r = self.wrapping_sub(other);
376        ((other.is_negative() && r > self) || (!other.is_negative() && r <= self)).then_some(r)
377    }
378
379    /// Performs wrapping multiplication
380    #[inline]
381    pub fn wrapping_mul(self, other: Self) -> Self {
382        let (low, high) = mulx(self.low, other.low);
383
384        // Compute the high multiples, only impacting the high 128-bits
385        let hl = self.high.wrapping_mul(other.low as i128);
386        let lh = (self.low as i128).wrapping_mul(other.high);
387
388        Self {
389            low,
390            high: (high as i128).wrapping_add(hl).wrapping_add(lh),
391        }
392    }
393
394    /// Performs checked multiplication
395    #[inline]
396    pub fn checked_mul(self, other: Self) -> Option<Self> {
397        if self == i256::ZERO || other == i256::ZERO {
398            return Some(i256::ZERO);
399        }
400
401        // Shift sign bit down to construct mask of all set bits if negative
402        let l_sa = self.high >> 127;
403        let r_sa = other.high >> 127;
404        let out_sa = (l_sa ^ r_sa) as u128;
405
406        // Compute absolute values
407        let l_abs = self.wrapping_abs();
408        let r_abs = other.wrapping_abs();
409
410        // Overflow if both high parts are non-zero
411        if l_abs.high != 0 && r_abs.high != 0 {
412            return None;
413        }
414
415        // Perform checked multiplication on absolute values
416        let (low, high) = mulx(l_abs.low, r_abs.low);
417
418        // Compute the high multiples, only impacting the high 128-bits
419        let hl = (l_abs.high as u128).checked_mul(r_abs.low)?;
420        let lh = l_abs.low.checked_mul(r_abs.high as u128)?;
421
422        let high = high.checked_add(hl)?.checked_add(lh)?;
423
424        // Reverse absolute value, if necessary
425        let (low, c) = (low ^ out_sa).overflowing_sub(out_sa);
426        let high = (high ^ out_sa).wrapping_sub(out_sa).wrapping_sub(c as u128) as i128;
427
428        // Check for overflow in final conversion
429        (high.is_negative() == (self.is_negative() ^ other.is_negative()))
430            .then_some(Self { low, high })
431    }
432
433    /// Division operation, returns (quotient, remainder).
434    /// This basically implements [Long division]: `<https://en.wikipedia.org/wiki/Division_algorithm>`
435    #[inline]
436    fn div_rem(self, other: Self) -> Result<(Self, Self), DivRemError> {
437        if other == Self::ZERO {
438            return Err(DivRemError::DivideByZero);
439        }
440        if other == Self::MINUS_ONE && self == Self::MIN {
441            return Err(DivRemError::DivideOverflow);
442        }
443
444        let a = self.wrapping_abs();
445        let b = other.wrapping_abs();
446
447        let (div, rem) = div_rem(&a.as_digits(), &b.as_digits());
448        let div = Self::from_digits(div);
449        let rem = Self::from_digits(rem);
450
451        Ok((
452            if self.is_negative() == other.is_negative() {
453                div
454            } else {
455                div.wrapping_neg()
456            },
457            if self.is_negative() {
458                rem.wrapping_neg()
459            } else {
460                rem
461            },
462        ))
463    }
464
465    /// Interpret this [`i256`] as 4 `u64` digits, least significant first
466    fn as_digits(self) -> [u64; 4] {
467        [
468            self.low as u64,
469            (self.low >> 64) as u64,
470            self.high as u64,
471            (self.high as u128 >> 64) as u64,
472        ]
473    }
474
475    /// Interpret 4 `u64` digits, least significant first, as a [`i256`]
476    fn from_digits(digits: [u64; 4]) -> Self {
477        Self::from_parts(
478            digits[0] as u128 | ((digits[1] as u128) << 64),
479            digits[2] as i128 | ((digits[3] as i128) << 64),
480        )
481    }
482
483    /// Performs wrapping division
484    #[inline]
485    pub fn wrapping_div(self, other: Self) -> Self {
486        match self.div_rem(other) {
487            Ok((v, _)) => v,
488            Err(DivRemError::DivideByZero) => panic!("attempt to divide by zero"),
489            Err(_) => Self::MIN,
490        }
491    }
492
493    /// Performs checked division
494    #[inline]
495    pub fn checked_div(self, other: Self) -> Option<Self> {
496        self.div_rem(other).map(|(v, _)| v).ok()
497    }
498
499    /// Performs wrapping remainder
500    #[inline]
501    pub fn wrapping_rem(self, other: Self) -> Self {
502        match self.div_rem(other) {
503            Ok((_, v)) => v,
504            Err(DivRemError::DivideByZero) => panic!("attempt to divide by zero"),
505            Err(_) => Self::ZERO,
506        }
507    }
508
509    /// Performs checked remainder
510    #[inline]
511    pub fn checked_rem(self, other: Self) -> Option<Self> {
512        self.div_rem(other).map(|(_, v)| v).ok()
513    }
514
515    /// Performs checked exponentiation
516    #[inline]
517    pub fn checked_pow(self, mut exp: u32) -> Option<Self> {
518        if exp == 0 {
519            return Some(i256::from_i128(1));
520        }
521
522        let mut base = self;
523        let mut acc: Self = i256::from_i128(1);
524
525        while exp > 1 {
526            if (exp & 1) == 1 {
527                acc = acc.checked_mul(base)?;
528            }
529            exp /= 2;
530            base = base.checked_mul(base)?;
531        }
532        // since exp!=0, finally the exp must be 1.
533        // Deal with the final bit of the exponent separately, since
534        // squaring the base afterwards is not necessary and may cause a
535        // needless overflow.
536        acc.checked_mul(base)
537    }
538
539    /// Performs wrapping exponentiation
540    #[inline]
541    pub fn wrapping_pow(self, mut exp: u32) -> Self {
542        if exp == 0 {
543            return i256::from_i128(1);
544        }
545
546        let mut base = self;
547        let mut acc: Self = i256::from_i128(1);
548
549        while exp > 1 {
550            if (exp & 1) == 1 {
551                acc = acc.wrapping_mul(base);
552            }
553            exp /= 2;
554            base = base.wrapping_mul(base);
555        }
556
557        // since exp!=0, finally the exp must be 1.
558        // Deal with the final bit of the exponent separately, since
559        // squaring the base afterwards is not necessary and may cause a
560        // needless overflow.
561        acc.wrapping_mul(base)
562    }
563
564    /// Returns a number [`i256`] representing sign of this [`i256`].
565    ///
566    /// 0 if the number is zero
567    /// 1 if the number is positive
568    /// -1 if the number is negative
569    pub const fn signum(self) -> Self {
570        if self.is_positive() {
571            i256::ONE
572        } else if self.is_negative() {
573            i256::MINUS_ONE
574        } else {
575            i256::ZERO
576        }
577    }
578
579    /// Returns `true` if this [`i256`] is negative
580    #[inline]
581    pub const fn is_negative(self) -> bool {
582        self.high.is_negative()
583    }
584
585    /// Returns `true` if this [`i256`] is positive
586    pub const fn is_positive(self) -> bool {
587        self.high.is_positive() || self.high == 0 && self.low != 0
588    }
589
590    /// Returns the number of leading zeros in the binary representation of this [`i256`].
591    pub const fn leading_zeros(&self) -> u32 {
592        match self.high {
593            0 => u128::BITS + self.low.leading_zeros(),
594            _ => self.high.leading_zeros(),
595        }
596    }
597
598    /// Returns the number of trailing zeros in the binary representation of this [`i256`].
599    pub const fn trailing_zeros(&self) -> u32 {
600        match self.low {
601            0 => u128::BITS + self.high.trailing_zeros(),
602            _ => self.low.trailing_zeros(),
603        }
604    }
605
606    fn redundant_leading_sign_bits_i256(n: i256) -> u8 {
607        let mask = n >> 255; // all ones or all zeros
608        ((n ^ mask).leading_zeros() - 1) as u8 // we only need one sign bit
609    }
610
611    fn i256_to_f64(input: i256) -> f64 {
612        let k = i256::redundant_leading_sign_bits_i256(input);
613        let n = input << k; // left-justify (no redundant sign bits)
614        let n = (n.high >> 64) as i64; // throw away the lower 192 bits
615        (n as f64) * f64::powi(2.0, 192 - (k as i32)) // convert to f64 and scale it, as we left-shift k bit previous, so we need to scale it by 2^(192-k)
616    }
617}
618
619/// Temporary workaround due to lack of stable const array slicing
620/// See <https://github.com/rust-lang/rust/issues/90091>
621const fn split_array<const N: usize, const M: usize>(vals: [u8; N]) -> ([u8; M], [u8; M]) {
622    let mut a = [0; M];
623    let mut b = [0; M];
624    let mut i = 0;
625    while i != M {
626        a[i] = vals[i];
627        b[i] = vals[i + M];
628        i += 1;
629    }
630    (a, b)
631}
632
633/// Performs an unsigned multiplication of `a * b` returning a tuple of
634/// `(low, high)` where `low` contains the lower 128-bits of the result
635/// and `high` the higher 128-bits
636///
637/// This mirrors the x86 mulx instruction but for 128-bit types
638#[inline]
639fn mulx(a: u128, b: u128) -> (u128, u128) {
640    let split = |a: u128| (a & (u64::MAX as u128), a >> 64);
641
642    const MASK: u128 = u64::MAX as _;
643
644    let (a_low, a_high) = split(a);
645    let (b_low, b_high) = split(b);
646
647    // Carry stores the upper 64-bits of low and lower 64-bits of high
648    let (mut low, mut carry) = split(a_low * b_low);
649    carry += a_high * b_low;
650
651    // Update low and high with corresponding parts of carry
652    low += carry << 64;
653    let mut high = carry >> 64;
654
655    // Update carry with overflow from low
656    carry = low >> 64;
657    low &= MASK;
658
659    // Perform multiply including overflow from low
660    carry += b_high * a_low;
661
662    // Update low and high with values from carry
663    low += carry << 64;
664    high += carry >> 64;
665
666    // Perform 4th multiplication
667    high += a_high * b_high;
668
669    (low, high)
670}
671
672derive_arith!(
673    i256,
674    Add,
675    AddAssign,
676    add,
677    add_assign,
678    wrapping_add,
679    checked_add
680);
681derive_arith!(
682    i256,
683    Sub,
684    SubAssign,
685    sub,
686    sub_assign,
687    wrapping_sub,
688    checked_sub
689);
690derive_arith!(
691    i256,
692    Mul,
693    MulAssign,
694    mul,
695    mul_assign,
696    wrapping_mul,
697    checked_mul
698);
699derive_arith!(
700    i256,
701    Div,
702    DivAssign,
703    div,
704    div_assign,
705    wrapping_div,
706    checked_div
707);
708derive_arith!(
709    i256,
710    Rem,
711    RemAssign,
712    rem,
713    rem_assign,
714    wrapping_rem,
715    checked_rem
716);
717
718impl Neg for i256 {
719    type Output = i256;
720
721    #[cfg(debug_assertions)]
722    fn neg(self) -> Self::Output {
723        self.checked_neg().expect("i256 overflow")
724    }
725
726    #[cfg(not(debug_assertions))]
727    fn neg(self) -> Self::Output {
728        self.wrapping_neg()
729    }
730}
731
732impl BitAnd for i256 {
733    type Output = i256;
734
735    #[inline]
736    fn bitand(self, rhs: Self) -> Self::Output {
737        Self {
738            low: self.low & rhs.low,
739            high: self.high & rhs.high,
740        }
741    }
742}
743
744impl BitOr for i256 {
745    type Output = i256;
746
747    #[inline]
748    fn bitor(self, rhs: Self) -> Self::Output {
749        Self {
750            low: self.low | rhs.low,
751            high: self.high | rhs.high,
752        }
753    }
754}
755
756impl BitXor for i256 {
757    type Output = i256;
758
759    #[inline]
760    fn bitxor(self, rhs: Self) -> Self::Output {
761        Self {
762            low: self.low ^ rhs.low,
763            high: self.high ^ rhs.high,
764        }
765    }
766}
767
768impl Shl<u8> for i256 {
769    type Output = i256;
770
771    #[inline]
772    fn shl(self, rhs: u8) -> Self::Output {
773        if rhs == 0 {
774            self
775        } else if rhs < 128 {
776            Self {
777                high: (self.high << rhs) | (self.low >> (128 - rhs)) as i128,
778                low: self.low << rhs,
779            }
780        } else {
781            Self {
782                high: (self.low << (rhs - 128)) as i128,
783                low: 0,
784            }
785        }
786    }
787}
788
789impl Shr<u8> for i256 {
790    type Output = i256;
791
792    #[inline]
793    fn shr(self, rhs: u8) -> Self::Output {
794        if rhs == 0 {
795            self
796        } else if rhs < 128 {
797            Self {
798                high: self.high >> rhs,
799                low: (self.low >> rhs) | ((self.high as u128) << (128 - rhs)),
800            }
801        } else {
802            Self {
803                high: self.high >> 127,
804                low: (self.high >> (rhs - 128)) as u128,
805            }
806        }
807    }
808}
809
810macro_rules! define_as_primitive {
811    ($native_ty:ty) => {
812        impl AsPrimitive<i256> for $native_ty {
813            fn as_(self) -> i256 {
814                i256::from_i128(self as i128)
815            }
816        }
817    };
818}
819
820define_as_primitive!(i8);
821define_as_primitive!(i16);
822define_as_primitive!(i32);
823define_as_primitive!(i64);
824define_as_primitive!(u8);
825define_as_primitive!(u16);
826define_as_primitive!(u32);
827define_as_primitive!(u64);
828
829impl ToPrimitive for i256 {
830    fn to_i64(&self) -> Option<i64> {
831        let as_i128 = self.low as i128;
832
833        let high_negative = self.high < 0;
834        let low_negative = as_i128 < 0;
835        let high_valid = self.high == -1 || self.high == 0;
836
837        if high_negative == low_negative && high_valid {
838            let (low_bytes, high_bytes) = split_array(u128::to_le_bytes(self.low));
839            let high = i64::from_le_bytes(high_bytes);
840            let low = i64::from_le_bytes(low_bytes);
841
842            let high_negative = high < 0;
843            let low_negative = low < 0;
844            let high_valid = self.high == -1 || self.high == 0;
845
846            (high_negative == low_negative && high_valid).then_some(low)
847        } else {
848            None
849        }
850    }
851
852    fn to_f64(&self) -> Option<f64> {
853        match *self {
854            Self::MIN => Some(-2_f64.powi(255)),
855            Self::ZERO => Some(0f64),
856            Self::ONE => Some(1f64),
857            n => Some(Self::i256_to_f64(n)),
858        }
859    }
860
861    fn to_u64(&self) -> Option<u64> {
862        let as_i128 = self.low as i128;
863
864        let high_negative = self.high < 0;
865        let low_negative = as_i128 < 0;
866        let high_valid = self.high == -1 || self.high == 0;
867
868        if high_negative == low_negative && high_valid {
869            self.low.to_u64()
870        } else {
871            None
872        }
873    }
874}
875
876// num_traits checked implementations
877
878impl CheckedNeg for i256 {
879    fn checked_neg(&self) -> Option<Self> {
880        (*self).checked_neg()
881    }
882}
883
884impl CheckedAdd for i256 {
885    fn checked_add(&self, v: &i256) -> Option<Self> {
886        (*self).checked_add(*v)
887    }
888}
889
890impl CheckedSub for i256 {
891    fn checked_sub(&self, v: &i256) -> Option<Self> {
892        (*self).checked_sub(*v)
893    }
894}
895
896impl CheckedDiv for i256 {
897    fn checked_div(&self, v: &i256) -> Option<Self> {
898        (*self).checked_div(*v)
899    }
900}
901
902impl CheckedMul for i256 {
903    fn checked_mul(&self, v: &i256) -> Option<Self> {
904        (*self).checked_mul(*v)
905    }
906}
907
908impl CheckedRem for i256 {
909    fn checked_rem(&self, v: &i256) -> Option<Self> {
910        (*self).checked_rem(*v)
911    }
912}
913
914impl WrappingAdd for i256 {
915    fn wrapping_add(&self, v: &Self) -> Self {
916        (*self).wrapping_add(*v)
917    }
918}
919
920impl WrappingSub for i256 {
921    fn wrapping_sub(&self, v: &Self) -> Self {
922        (*self).wrapping_sub(*v)
923    }
924}
925
926impl WrappingMul for i256 {
927    fn wrapping_mul(&self, v: &Self) -> Self {
928        (*self).wrapping_mul(*v)
929    }
930}
931
932impl WrappingNeg for i256 {
933    fn wrapping_neg(&self) -> Self {
934        (*self).wrapping_neg()
935    }
936}
937
938impl Zero for i256 {
939    fn zero() -> Self {
940        i256::ZERO
941    }
942
943    fn is_zero(&self) -> bool {
944        *self == i256::ZERO
945    }
946}
947
948impl One for i256 {
949    fn one() -> Self {
950        i256::ONE
951    }
952
953    fn is_one(&self) -> bool {
954        *self == i256::ONE
955    }
956}
957
958impl Num for i256 {
959    type FromStrRadixErr = ParseI256Error;
960
961    fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
962        if radix == 10 {
963            str.parse()
964        } else {
965            // Parsing from non-10 baseseeÎ is not supported
966            Err(ParseI256Error {})
967        }
968    }
969}
970
971impl Signed for i256 {
972    fn abs(&self) -> Self {
973        self.wrapping_abs()
974    }
975
976    fn abs_sub(&self, other: &Self) -> Self {
977        if self > other {
978            self.wrapping_sub(other)
979        } else {
980            i256::ZERO
981        }
982    }
983
984    fn signum(&self) -> Self {
985        (*self).signum()
986    }
987
988    fn is_positive(&self) -> bool {
989        (*self).is_positive()
990    }
991
992    fn is_negative(&self) -> bool {
993        (*self).is_negative()
994    }
995}
996
997impl Bounded for i256 {
998    fn min_value() -> Self {
999        i256::MIN
1000    }
1001
1002    fn max_value() -> Self {
1003        i256::MAX
1004    }
1005}
1006
1007#[cfg(all(test, not(miri)))] // llvm.x86.subborrow.64 not supported by MIRI
1008mod tests {
1009    use super::*;
1010    use num_traits::Signed;
1011    use rand::{Rng, rng};
1012
1013    #[test]
1014    fn test_signed_cmp() {
1015        let a = i256::from_parts(i128::MAX as u128, 12);
1016        let b = i256::from_parts(i128::MIN as u128, 12);
1017        assert!(a < b);
1018
1019        let a = i256::from_parts(i128::MAX as u128, 12);
1020        let b = i256::from_parts(i128::MIN as u128, -12);
1021        assert!(a > b);
1022    }
1023
1024    #[test]
1025    fn test_to_i128() {
1026        let vals = [
1027            BigInt::from_i128(-1).unwrap(),
1028            BigInt::from_i128(i128::MAX).unwrap(),
1029            BigInt::from_i128(i128::MIN).unwrap(),
1030            BigInt::from_u128(u128::MIN).unwrap(),
1031            BigInt::from_u128(u128::MAX).unwrap(),
1032        ];
1033
1034        for v in vals {
1035            let (t, overflow) = i256::from_bigint_with_overflow(v.clone());
1036            assert!(!overflow);
1037            assert_eq!(t.to_i128(), v.to_i128(), "{v} vs {t}");
1038        }
1039    }
1040
1041    /// Tests operations against the two provided [`i256`]
1042    fn test_ops(il: i256, ir: i256) {
1043        let bl = BigInt::from_signed_bytes_le(&il.to_le_bytes());
1044        let br = BigInt::from_signed_bytes_le(&ir.to_le_bytes());
1045
1046        // Comparison
1047        assert_eq!(il.cmp(&ir), bl.cmp(&br), "{bl} cmp {br}");
1048
1049        // Conversions
1050        assert_eq!(i256::from_le_bytes(il.to_le_bytes()), il);
1051        assert_eq!(i256::from_be_bytes(il.to_be_bytes()), il);
1052        assert_eq!(i256::from_le_bytes(ir.to_le_bytes()), ir);
1053        assert_eq!(i256::from_be_bytes(ir.to_be_bytes()), ir);
1054
1055        // To i128
1056        assert_eq!(il.to_i128(), bl.to_i128(), "{bl}");
1057        assert_eq!(ir.to_i128(), br.to_i128(), "{br}");
1058
1059        // Absolute value
1060        let (abs, overflow) = i256::from_bigint_with_overflow(bl.abs());
1061        assert_eq!(il.wrapping_abs(), abs);
1062        assert_eq!(il.checked_abs().is_none(), overflow);
1063
1064        let (abs, overflow) = i256::from_bigint_with_overflow(br.abs());
1065        assert_eq!(ir.wrapping_abs(), abs);
1066        assert_eq!(ir.checked_abs().is_none(), overflow);
1067
1068        // Negation
1069        let (neg, overflow) = i256::from_bigint_with_overflow(bl.clone().neg());
1070        assert_eq!(il.wrapping_neg(), neg);
1071        assert_eq!(il.checked_neg().is_none(), overflow);
1072
1073        // Negation
1074        let (neg, overflow) = i256::from_bigint_with_overflow(br.clone().neg());
1075        assert_eq!(ir.wrapping_neg(), neg);
1076        assert_eq!(ir.checked_neg().is_none(), overflow);
1077
1078        // Addition
1079        let actual = il.wrapping_add(ir);
1080        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() + br.clone());
1081        assert_eq!(actual, expected);
1082
1083        let checked = il.checked_add(ir);
1084        match overflow {
1085            true => assert!(checked.is_none()),
1086            false => assert_eq!(checked, Some(actual)),
1087        }
1088
1089        // Subtraction
1090        let actual = il.wrapping_sub(ir);
1091        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() - br.clone());
1092        assert_eq!(actual.to_string(), expected.to_string());
1093
1094        let checked = il.checked_sub(ir);
1095        match overflow {
1096            true => assert!(checked.is_none()),
1097            false => assert_eq!(checked, Some(actual), "{bl} - {br} = {expected}"),
1098        }
1099
1100        // Multiplication
1101        let actual = il.wrapping_mul(ir);
1102        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() * br.clone());
1103        assert_eq!(actual.to_string(), expected.to_string());
1104
1105        let checked = il.checked_mul(ir);
1106        match overflow {
1107            true => assert!(
1108                checked.is_none(),
1109                "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
1110            ),
1111            false => assert_eq!(
1112                checked,
1113                Some(actual),
1114                "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
1115            ),
1116        }
1117
1118        // Division
1119        if ir != i256::ZERO {
1120            let actual = il.wrapping_div(ir);
1121            let expected = bl.clone() / br.clone();
1122            let checked = il.checked_div(ir);
1123
1124            if ir == i256::MINUS_ONE && il == i256::MIN {
1125                // BigInt produces an integer over i256::MAX
1126                assert_eq!(actual, i256::MIN);
1127                assert!(checked.is_none());
1128            } else {
1129                assert_eq!(actual.to_string(), expected.to_string());
1130                assert_eq!(checked.unwrap().to_string(), expected.to_string());
1131            }
1132        } else {
1133            // `wrapping_div` panics on division by zero
1134            assert!(il.checked_div(ir).is_none());
1135        }
1136
1137        // Remainder
1138        if ir != i256::ZERO {
1139            let actual = il.wrapping_rem(ir);
1140            let expected = bl.clone() % br.clone();
1141            let checked = il.checked_rem(ir);
1142
1143            assert_eq!(actual.to_string(), expected.to_string(), "{il} % {ir}");
1144
1145            if ir == i256::MINUS_ONE && il == i256::MIN {
1146                assert!(checked.is_none());
1147            } else {
1148                assert_eq!(checked.unwrap().to_string(), expected.to_string());
1149            }
1150        } else {
1151            // `wrapping_rem` panics on division by zero
1152            assert!(il.checked_rem(ir).is_none());
1153        }
1154
1155        // Exponentiation
1156        for exp in vec![0, 1, 2, 3, 8, 100].into_iter() {
1157            let actual = il.wrapping_pow(exp);
1158            let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone().pow(exp));
1159            assert_eq!(actual.to_string(), expected.to_string());
1160
1161            let checked = il.checked_pow(exp);
1162            match overflow {
1163                true => assert!(
1164                    checked.is_none(),
1165                    "{il} ^ {exp} = {actual} vs {bl} * {exp} = {expected}"
1166                ),
1167                false => assert_eq!(
1168                    checked,
1169                    Some(actual),
1170                    "{il} ^ {exp} = {actual} vs {bl} ^ {exp} = {expected}"
1171                ),
1172            }
1173        }
1174
1175        // Bit operations
1176        let actual = il & ir;
1177        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() & br.clone());
1178        assert_eq!(actual.to_string(), expected.to_string());
1179
1180        let actual = il | ir;
1181        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() | br.clone());
1182        assert_eq!(actual.to_string(), expected.to_string());
1183
1184        let actual = il ^ ir;
1185        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() ^ br);
1186        assert_eq!(actual.to_string(), expected.to_string());
1187
1188        for shift in [0_u8, 1, 4, 126, 128, 129, 254, 255] {
1189            let actual = il << shift;
1190            let (expected, _) = i256::from_bigint_with_overflow(bl.clone() << shift);
1191            assert_eq!(actual.to_string(), expected.to_string());
1192
1193            let actual = il >> shift;
1194            let (expected, _) = i256::from_bigint_with_overflow(bl.clone() >> shift);
1195            assert_eq!(actual.to_string(), expected.to_string());
1196        }
1197    }
1198
1199    #[test]
1200    fn test_i256() {
1201        let candidates = [
1202            i256::ZERO,
1203            i256::ONE,
1204            i256::MINUS_ONE,
1205            i256::from_i128(2),
1206            i256::from_i128(-2),
1207            i256::from_parts(u128::MAX, 1),
1208            i256::from_parts(u128::MAX, -1),
1209            i256::from_parts(0, 1),
1210            i256::from_parts(0, -1),
1211            i256::from_parts(1, -1),
1212            i256::from_parts(1, 1),
1213            i256::from_parts(0, i128::MAX),
1214            i256::from_parts(0, i128::MIN),
1215            i256::from_parts(1, i128::MAX),
1216            i256::from_parts(1, i128::MIN),
1217            i256::from_parts(u128::MAX, i128::MIN),
1218            i256::from_parts(100, 32),
1219            i256::MIN,
1220            i256::MAX,
1221            i256::MIN >> 1,
1222            i256::MAX >> 1,
1223            i256::ONE << 127,
1224            i256::ONE << 128,
1225            i256::ONE << 129,
1226            i256::MINUS_ONE << 127,
1227            i256::MINUS_ONE << 128,
1228            i256::MINUS_ONE << 129,
1229        ];
1230
1231        for il in candidates {
1232            for ir in candidates {
1233                test_ops(il, ir)
1234            }
1235        }
1236    }
1237
1238    #[test]
1239    fn test_signed_ops() {
1240        // signum
1241        assert_eq!(i256::from_i128(1).signum(), i256::ONE);
1242        assert_eq!(i256::from_i128(0).signum(), i256::ZERO);
1243        assert_eq!(i256::from_i128(-0).signum(), i256::ZERO);
1244        assert_eq!(i256::from_i128(-1).signum(), i256::MINUS_ONE);
1245
1246        // is_positive
1247        assert!(i256::from_i128(1).is_positive());
1248        assert!(!i256::from_i128(0).is_positive());
1249        assert!(!i256::from_i128(-0).is_positive());
1250        assert!(!i256::from_i128(-1).is_positive());
1251
1252        // is_negative
1253        assert!(!i256::from_i128(1).is_negative());
1254        assert!(!i256::from_i128(0).is_negative());
1255        assert!(!i256::from_i128(-0).is_negative());
1256        assert!(i256::from_i128(-1).is_negative());
1257    }
1258
1259    #[test]
1260    #[cfg_attr(miri, ignore)]
1261    fn test_i256_fuzz() {
1262        let mut rng = rng();
1263
1264        for _ in 0..1000 {
1265            let mut l = [0_u8; 32];
1266            let len = rng.random_range(0..32);
1267            l.iter_mut().take(len).for_each(|x| *x = rng.random());
1268
1269            let mut r = [0_u8; 32];
1270            let len = rng.random_range(0..32);
1271            r.iter_mut().take(len).for_each(|x| *x = rng.random());
1272
1273            test_ops(i256::from_le_bytes(l), i256::from_le_bytes(r))
1274        }
1275    }
1276
1277    #[test]
1278    fn test_i256_to_primitive() {
1279        let a = i256::MAX;
1280        assert!(a.to_i64().is_none());
1281        assert!(a.to_u64().is_none());
1282
1283        let a = i256::from_i128(i128::MAX);
1284        assert!(a.to_i64().is_none());
1285        assert!(a.to_u64().is_none());
1286
1287        let a = i256::from_i128(i64::MAX as i128);
1288        assert_eq!(a.to_i64().unwrap(), i64::MAX);
1289        assert_eq!(a.to_u64().unwrap(), i64::MAX as u64);
1290
1291        let a = i256::from_i128(i64::MAX as i128 + 1);
1292        assert!(a.to_i64().is_none());
1293        assert_eq!(a.to_u64().unwrap(), i64::MAX as u64 + 1);
1294
1295        let a = i256::MIN;
1296        assert!(a.to_i64().is_none());
1297        assert!(a.to_u64().is_none());
1298
1299        let a = i256::from_i128(i128::MIN);
1300        assert!(a.to_i64().is_none());
1301        assert!(a.to_u64().is_none());
1302
1303        let a = i256::from_i128(i64::MIN as i128);
1304        assert_eq!(a.to_i64().unwrap(), i64::MIN);
1305        assert!(a.to_u64().is_none());
1306
1307        let a = i256::from_i128(i64::MIN as i128 - 1);
1308        assert!(a.to_i64().is_none());
1309        assert!(a.to_u64().is_none());
1310    }
1311
1312    #[test]
1313    fn test_i256_as_i128() {
1314        let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(1));
1315        let i128 = a.as_i128();
1316        assert_eq!(i128, i128::MIN);
1317
1318        let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(2));
1319        let i128 = a.as_i128();
1320        assert_eq!(i128, i128::MIN + 1);
1321
1322        let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(1));
1323        let i128 = a.as_i128();
1324        assert_eq!(i128, i128::MAX);
1325
1326        let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(2));
1327        let i128 = a.as_i128();
1328        assert_eq!(i128, i128::MAX - 1);
1329    }
1330
1331    #[test]
1332    fn test_string_roundtrip() {
1333        let roundtrip_cases = [
1334            i256::ZERO,
1335            i256::ONE,
1336            i256::MINUS_ONE,
1337            i256::from_i128(123456789),
1338            i256::from_i128(-123456789),
1339            i256::from_i128(i128::MIN),
1340            i256::from_i128(i128::MAX),
1341            i256::MIN,
1342            i256::MAX,
1343        ];
1344        for case in roundtrip_cases {
1345            let formatted = case.to_string();
1346            let back: i256 = formatted.parse().unwrap();
1347            assert_eq!(case, back);
1348        }
1349    }
1350
1351    #[test]
1352    fn test_from_string() {
1353        let cases = [
1354            (
1355                "000000000000000000000000000000000000000011",
1356                Some(i256::from_i128(11)),
1357            ),
1358            (
1359                "-000000000000000000000000000000000000000011",
1360                Some(i256::from_i128(-11)),
1361            ),
1362            (
1363                "-0000000000000000000000000000000000000000123456789",
1364                Some(i256::from_i128(-123456789)),
1365            ),
1366            ("-", None),
1367            ("+", None),
1368            ("--1", None),
1369            ("-+1", None),
1370            ("000000000000000000000000000000000000000", Some(i256::ZERO)),
1371            ("0000000000000000000000000000000000000000-11", None),
1372            ("11-1111111111111111111111111111111111111", None),
1373            (
1374                "115792089237316195423570985008687907853269984665640564039457584007913129639936",
1375                None,
1376            ),
1377        ];
1378        for (case, expected) in cases {
1379            assert_eq!(i256::from_string(case), expected)
1380        }
1381    }
1382
1383    #[allow(clippy::op_ref)]
1384    fn test_reference_op(il: i256, ir: i256) {
1385        let r1 = il + ir;
1386        let r2 = &il + ir;
1387        let r3 = il + &ir;
1388        let r4 = &il + &ir;
1389        assert_eq!(r1, r2);
1390        assert_eq!(r1, r3);
1391        assert_eq!(r1, r4);
1392
1393        let r1 = il - ir;
1394        let r2 = &il - ir;
1395        let r3 = il - &ir;
1396        let r4 = &il - &ir;
1397        assert_eq!(r1, r2);
1398        assert_eq!(r1, r3);
1399        assert_eq!(r1, r4);
1400
1401        let r1 = il * ir;
1402        let r2 = &il * ir;
1403        let r3 = il * &ir;
1404        let r4 = &il * &ir;
1405        assert_eq!(r1, r2);
1406        assert_eq!(r1, r3);
1407        assert_eq!(r1, r4);
1408
1409        let r1 = il / ir;
1410        let r2 = &il / ir;
1411        let r3 = il / &ir;
1412        let r4 = &il / &ir;
1413        assert_eq!(r1, r2);
1414        assert_eq!(r1, r3);
1415        assert_eq!(r1, r4);
1416    }
1417
1418    #[test]
1419    fn test_i256_reference_op() {
1420        let candidates = [
1421            i256::ONE,
1422            i256::MINUS_ONE,
1423            i256::from_i128(2),
1424            i256::from_i128(-2),
1425            i256::from_i128(3),
1426            i256::from_i128(-3),
1427        ];
1428
1429        for il in candidates {
1430            for ir in candidates {
1431                test_reference_op(il, ir)
1432            }
1433        }
1434    }
1435
1436    #[test]
1437    fn test_decimal256_to_f64_typical_values() {
1438        let v = i256::from_i128(42_i128);
1439        assert_eq!(v.to_f64().unwrap(), 42.0);
1440
1441        let v = i256::from_i128(-123456789012345678i128);
1442        assert_eq!(v.to_f64().unwrap(), -123456789012345678.0);
1443
1444        let v = i256::from_string("0").unwrap();
1445        assert_eq!(v.to_f64().unwrap(), 0.0);
1446
1447        let v = i256::from_string("1").unwrap();
1448        assert_eq!(v.to_f64().unwrap(), 1.0);
1449
1450        let mut rng = rng();
1451        for _ in 0..10 {
1452            let f64_value =
1453                (rng.random_range(i128::MIN..i128::MAX) as f64) * rng.random_range(0.0..1.0);
1454            let big = i256::from_f64(f64_value).unwrap();
1455            assert_eq!(big.to_f64().unwrap(), f64_value);
1456        }
1457    }
1458
1459    #[test]
1460    fn test_decimal256_to_f64_large_positive_value() {
1461        let max_f = f64::MAX;
1462        let big = i256::from_f64(max_f * 2.0).unwrap_or(i256::MAX);
1463        let out = big.to_f64().unwrap();
1464        assert!(out.is_finite() && out.is_sign_positive());
1465    }
1466
1467    #[test]
1468    fn test_decimal256_to_f64_large_negative_value() {
1469        let max_f = f64::MAX;
1470        let big_neg = i256::from_f64(-(max_f * 2.0)).unwrap_or(i256::MIN);
1471        let out = big_neg.to_f64().unwrap();
1472        assert!(out.is_finite() && out.is_sign_negative());
1473    }
1474
1475    #[test]
1476    fn test_num_traits() {
1477        let value = i256::from_i128(-5);
1478        assert_eq!(
1479            <i256 as CheckedNeg>::checked_neg(&value),
1480            Some(i256::from(5))
1481        );
1482
1483        assert_eq!(
1484            <i256 as CheckedAdd>::checked_add(&value, &value),
1485            Some(i256::from(-10))
1486        );
1487
1488        assert_eq!(
1489            <i256 as CheckedSub>::checked_sub(&value, &value),
1490            Some(i256::from(0))
1491        );
1492
1493        assert_eq!(
1494            <i256 as CheckedMul>::checked_mul(&value, &value),
1495            Some(i256::from(25))
1496        );
1497
1498        assert_eq!(
1499            <i256 as CheckedDiv>::checked_div(&value, &value),
1500            Some(i256::from(1))
1501        );
1502
1503        assert_eq!(
1504            <i256 as CheckedRem>::checked_rem(&value, &value),
1505            Some(i256::from(0))
1506        );
1507
1508        assert_eq!(
1509            <i256 as WrappingAdd>::wrapping_add(&value, &value),
1510            i256::from(-10)
1511        );
1512
1513        assert_eq!(
1514            <i256 as WrappingSub>::wrapping_sub(&value, &value),
1515            i256::from(0)
1516        );
1517
1518        assert_eq!(
1519            <i256 as WrappingMul>::wrapping_mul(&value, &value),
1520            i256::from(25)
1521        );
1522
1523        assert_eq!(<i256 as WrappingNeg>::wrapping_neg(&value), i256::from(5));
1524
1525        // A single check for wrapping behavior, rely on trait implementation for others
1526        let result = <i256 as WrappingAdd>::wrapping_add(&i256::MAX, &i256::ONE);
1527        assert_eq!(result, i256::MIN);
1528
1529        assert_eq!(<i256 as Signed>::abs(&value), i256::from(5));
1530
1531        assert_eq!(<i256 as One>::one(), i256::from(1));
1532        assert_eq!(<i256 as Zero>::zero(), i256::from(0));
1533
1534        assert_eq!(<i256 as Bounded>::min_value(), i256::MIN);
1535        assert_eq!(<i256 as Bounded>::max_value(), i256::MAX);
1536    }
1537
1538    #[test]
1539    fn test_numtraits_from_str_radix() {
1540        assert_eq!(
1541            i256::from_str_radix("123456789", 10).expect("parsed"),
1542            i256::from(123456789)
1543        );
1544        assert_eq!(
1545            i256::from_str_radix("0", 10).expect("parsed"),
1546            i256::from(0)
1547        );
1548        assert!(i256::from_str_radix("abc", 10).is_err());
1549        assert!(i256::from_str_radix("0", 16).is_err());
1550    }
1551
1552    #[test]
1553    fn test_leading_zeros() {
1554        // Without high part
1555        assert_eq!(i256::from(0).leading_zeros(), 256);
1556        assert_eq!(i256::from(1).leading_zeros(), 256 - 1);
1557        assert_eq!(i256::from(16).leading_zeros(), 256 - 5);
1558        assert_eq!(i256::from(17).leading_zeros(), 256 - 5);
1559
1560        // With high part
1561        assert_eq!(i256::from_parts(2, 16).leading_zeros(), 128 - 5);
1562        assert_eq!(i256::from_parts(2, i128::MAX).leading_zeros(), 1);
1563
1564        assert_eq!(i256::MAX.leading_zeros(), 1);
1565        assert_eq!(i256::from(-1).leading_zeros(), 0);
1566    }
1567
1568    #[test]
1569    fn test_trailing_zeros() {
1570        // Without high part
1571        assert_eq!(i256::from(0).trailing_zeros(), 256);
1572        assert_eq!(i256::from(2).trailing_zeros(), 1);
1573        assert_eq!(i256::from(16).trailing_zeros(), 4);
1574        assert_eq!(i256::from(17).trailing_zeros(), 0);
1575        // With high part
1576        assert_eq!(i256::from_parts(0, i128::MAX).trailing_zeros(), 128);
1577        assert_eq!(i256::from_parts(0, 16).trailing_zeros(), 128 + 4);
1578        assert_eq!(i256::from_parts(2, i128::MAX).trailing_zeros(), 1);
1579
1580        assert_eq!(i256::MAX.trailing_zeros(), 0);
1581        assert_eq!(i256::from(-1).trailing_zeros(), 0);
1582    }
1583}
arrow_buffer/bigint/mod.rs

arrow_buffer/bigint/
mod.rs
