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, CheckedShl, CheckedShr,
23    CheckedSub, ConstOne, ConstZero, FromPrimitive, MulAdd, MulAddAssign, Num, One, SaturatingAdd,
24    SaturatingMul, SaturatingSub, Signed, ToPrimitive, WrappingAdd, WrappingMul, WrappingNeg,
25    WrappingShl, WrappingShr, WrappingSub, Zero, cast::AsPrimitive,
26};
27use std::cmp::Ordering;
28use std::num::ParseIntError;
29use std::ops::{BitAnd, BitOr, BitXor, Neg, Not, Shl, Shr};
30use std::str::FromStr;
31
32mod div;
33
34/// An opaque error similar to [`std::num::ParseIntError`]
35#[derive(Debug)]
36pub struct ParseI256Error {}
37
38impl From<ParseIntError> for ParseI256Error {
39    fn from(_: ParseIntError) -> Self {
40        Self {}
41    }
42}
43
44impl std::fmt::Display for ParseI256Error {
45    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
46        write!(f, "Failed to parse as i256")
47    }
48}
49impl std::error::Error for ParseI256Error {}
50
51/// Error returned by i256::DivRem
52enum DivRemError {
53    /// Division by zero
54    DivideByZero,
55    /// Division overflow
56    DivideOverflow,
57}
58
59/// A signed 256-bit integer
60#[allow(non_camel_case_types)]
61#[derive(Copy, Clone, Default, Eq, PartialEq, Hash)]
62#[repr(C)]
63pub struct i256 {
64    low: u128,
65    high: i128,
66}
67
68impl std::fmt::Debug for i256 {
69    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
70        write!(f, "{self}")
71    }
72}
73
74impl std::fmt::Display for i256 {
75    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
76        write!(f, "{}", BigInt::from_signed_bytes_le(&self.to_le_bytes()))
77    }
78}
79
80impl FromStr for i256 {
81    type Err = ParseI256Error;
82
83    fn from_str(s: &str) -> Result<Self, Self::Err> {
84        // i128 can store up to 38 decimal digits
85        if s.len() <= 38 {
86            return Ok(Self::from_i128(i128::from_str(s)?));
87        }
88
89        let (negative, s) = match s.as_bytes()[0] {
90            b'-' => (true, &s[1..]),
91            b'+' => (false, &s[1..]),
92            _ => (false, s),
93        };
94
95        // Trim leading 0s
96        let s = s.trim_start_matches('0');
97        if s.is_empty() {
98            return Ok(i256::ZERO);
99        }
100
101        if !s.as_bytes()[0].is_ascii_digit() {
102            // Ensures no duplicate sign
103            return Err(ParseI256Error {});
104        }
105
106        parse_impl(s, negative)
107    }
108}
109
110impl From<i8> for i256 {
111    fn from(value: i8) -> Self {
112        Self::from_i128(value.into())
113    }
114}
115
116impl From<i16> for i256 {
117    fn from(value: i16) -> Self {
118        Self::from_i128(value.into())
119    }
120}
121
122impl From<i32> for i256 {
123    fn from(value: i32) -> Self {
124        Self::from_i128(value.into())
125    }
126}
127
128impl From<i64> for i256 {
129    fn from(value: i64) -> Self {
130        Self::from_i128(value.into())
131    }
132}
133
134impl From<i128> for i256 {
135    fn from(value: i128) -> Self {
136        Self::from_i128(value)
137    }
138}
139
140/// Parse `s` with any sign and leading 0s removed
141fn parse_impl(s: &str, negative: bool) -> Result<i256, ParseI256Error> {
142    if s.len() <= 38 {
143        let low = i128::from_str(s)?;
144        return Ok(match negative {
145            true => i256::from_parts(low.neg() as _, -1),
146            false => i256::from_parts(low as _, 0),
147        });
148    }
149
150    let split = s.len() - 38;
151    if !s.as_bytes()[split].is_ascii_digit() {
152        // Ensures not splitting codepoint and no sign
153        return Err(ParseI256Error {});
154    }
155    let (hs, ls) = s.split_at(split);
156
157    let mut low = i128::from_str(ls)?;
158    let high = parse_impl(hs, negative)?;
159
160    if negative {
161        low = -low;
162    }
163
164    let low = i256::from_i128(low);
165
166    high.checked_mul(i256::from_i128(10_i128.pow(38)))
167        .and_then(|high| high.checked_add(low))
168        .ok_or(ParseI256Error {})
169}
170
171impl PartialOrd for i256 {
172    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
173        Some(self.cmp(other))
174    }
175}
176
177impl Ord for i256 {
178    fn cmp(&self, other: &Self) -> Ordering {
179        // This is 25x faster than using a variable length encoding such
180        // as BigInt as it avoids allocation and branching
181        self.high.cmp(&other.high).then(self.low.cmp(&other.low))
182    }
183}
184
185impl i256 {
186    /// The additive identity for this integer type, i.e. `0`.
187    pub const ZERO: Self = i256 { low: 0, high: 0 };
188
189    /// The multiplicative identity for this integer type, i.e. `1`.
190    pub const ONE: Self = i256 { low: 1, high: 0 };
191
192    /// The multiplicative inverse for this integer type, i.e. `-1`.
193    pub const MINUS_ONE: Self = i256 {
194        low: u128::MAX,
195        high: -1,
196    };
197
198    /// The maximum value that can be represented by this integer type
199    pub const MAX: Self = i256 {
200        low: u128::MAX,
201        high: i128::MAX,
202    };
203
204    /// The minimum value that can be represented by this integer type
205    pub const MIN: Self = i256 {
206        low: u128::MIN,
207        high: i128::MIN,
208    };
209
210    /// Create an integer value from its representation as a byte array in little-endian.
211    #[inline]
212    pub const fn from_le_bytes(b: [u8; 32]) -> Self {
213        let (low, high) = split_array(b);
214        Self {
215            high: i128::from_le_bytes(high),
216            low: u128::from_le_bytes(low),
217        }
218    }
219
220    /// Create an integer value from its representation as a byte array in big-endian.
221    #[inline]
222    pub const fn from_be_bytes(b: [u8; 32]) -> Self {
223        let (high, low) = split_array(b);
224        Self {
225            high: i128::from_be_bytes(high),
226            low: u128::from_be_bytes(low),
227        }
228    }
229
230    /// Create an `i256` value from a 128-bit value.
231    pub const fn from_i128(v: i128) -> Self {
232        Self::from_parts(v as u128, v >> 127)
233    }
234
235    /// Create an integer value from its representation as string.
236    #[inline]
237    pub fn from_string(value_str: &str) -> Option<Self> {
238        value_str.parse().ok()
239    }
240
241    /// Create an optional i256 from the provided `f64`. Returning `None`
242    /// if overflow occurred
243    pub fn from_f64(v: f64) -> Option<Self> {
244        BigInt::from_f64(v).and_then(|i| {
245            let (integer, overflow) = i256::from_bigint_with_overflow(i);
246            if overflow { None } else { Some(integer) }
247        })
248    }
249
250    /// Create an i256 from the provided low u128 and high i128
251    #[inline]
252    pub const fn from_parts(low: u128, high: i128) -> Self {
253        Self { low, high }
254    }
255
256    /// Returns this `i256` as a low u128 and high i128
257    pub const fn to_parts(self) -> (u128, i128) {
258        (self.low, self.high)
259    }
260
261    /// Converts this `i256` into an `i128` returning `None` if this would result
262    /// in truncation/overflow
263    pub fn to_i128(self) -> Option<i128> {
264        let as_i128 = self.low as i128;
265
266        let high_negative = self.high < 0;
267        let low_negative = as_i128 < 0;
268        let high_valid = self.high == -1 || self.high == 0;
269
270        (high_negative == low_negative && high_valid).then_some(self.low as i128)
271    }
272
273    /// Wraps this `i256` into an `i128`
274    pub fn as_i128(self) -> i128 {
275        self.low as i128
276    }
277
278    /// Return the memory representation of this integer as a byte array in little-endian byte order.
279    #[inline]
280    pub const fn to_le_bytes(self) -> [u8; 32] {
281        let low = self.low.to_le_bytes();
282        let high = self.high.to_le_bytes();
283        let mut t = [0; 32];
284        let mut i = 0;
285        while i != 16 {
286            t[i] = low[i];
287            t[i + 16] = high[i];
288            i += 1;
289        }
290        t
291    }
292
293    /// Return the memory representation of this integer as a byte array in big-endian byte order.
294    #[inline]
295    pub const fn to_be_bytes(self) -> [u8; 32] {
296        let low = self.low.to_be_bytes();
297        let high = self.high.to_be_bytes();
298        let mut t = [0; 32];
299        let mut i = 0;
300        while i != 16 {
301            t[i] = high[i];
302            t[i + 16] = low[i];
303            i += 1;
304        }
305        t
306    }
307
308    /// Create an i256 from the provided [`BigInt`] returning a bool indicating
309    /// if overflow occurred
310    fn from_bigint_with_overflow(v: BigInt) -> (Self, bool) {
311        let v_bytes = v.to_signed_bytes_le();
312        match v_bytes.len().cmp(&32) {
313            Ordering::Less => {
314                let mut bytes = if num_traits::Signed::is_negative(&v) {
315                    [255_u8; 32]
316                } else {
317                    [0; 32]
318                };
319                bytes[0..v_bytes.len()].copy_from_slice(&v_bytes[..v_bytes.len()]);
320                (Self::from_le_bytes(bytes), false)
321            }
322            Ordering::Equal => (Self::from_le_bytes(v_bytes.try_into().unwrap()), false),
323            Ordering::Greater => (Self::from_le_bytes(v_bytes[..32].try_into().unwrap()), true),
324        }
325    }
326
327    /// Computes the absolute value of this i256
328    #[inline]
329    pub fn wrapping_abs(self) -> Self {
330        // -1 if negative, otherwise 0
331        let sa = self.high >> 127;
332        let sa = Self::from_parts(sa as u128, sa);
333
334        // Inverted if negative
335        Self::from_parts(self.low ^ sa.low, self.high ^ sa.high).wrapping_sub(sa)
336    }
337
338    /// Computes the absolute value of this i256 returning `None` if `Self == Self::MIN`
339    #[inline]
340    pub fn checked_abs(self) -> Option<Self> {
341        (self != Self::MIN).then(|| self.wrapping_abs())
342    }
343
344    /// Negates this i256
345    #[inline]
346    pub fn wrapping_neg(self) -> Self {
347        Self::from_parts(!self.low, !self.high).wrapping_add(i256::ONE)
348    }
349
350    /// Negates this i256 returning `None` if `Self == Self::MIN`
351    #[inline]
352    pub fn checked_neg(self) -> Option<Self> {
353        (self != Self::MIN).then(|| self.wrapping_neg())
354    }
355
356    /// Performs wrapping addition
357    #[inline]
358    pub fn wrapping_add(self, other: Self) -> Self {
359        let (low, carry) = self.low.overflowing_add(other.low);
360        let high = self.high.wrapping_add(other.high).wrapping_add(carry as _);
361        Self { low, high }
362    }
363
364    /// Performs checked addition
365    #[inline]
366    pub fn checked_add(self, other: Self) -> Option<Self> {
367        let r = self.wrapping_add(other);
368        ((other.is_negative() && r < self) || (!other.is_negative() && r >= self)).then_some(r)
369    }
370
371    /// Performs wrapping subtraction
372    #[inline]
373    pub fn wrapping_sub(self, other: Self) -> Self {
374        let (low, carry) = self.low.overflowing_sub(other.low);
375        let high = self.high.wrapping_sub(other.high).wrapping_sub(carry as _);
376        Self { low, high }
377    }
378
379    /// Performs checked subtraction
380    #[inline]
381    pub fn checked_sub(self, other: Self) -> Option<Self> {
382        let r = self.wrapping_sub(other);
383        ((other.is_negative() && r > self) || (!other.is_negative() && r <= self)).then_some(r)
384    }
385
386    /// Performs wrapping multiplication
387    #[inline]
388    pub fn wrapping_mul(self, other: Self) -> Self {
389        let (low, high) = mulx(self.low, other.low);
390
391        // Compute the high multiples, only impacting the high 128-bits
392        let hl = self.high.wrapping_mul(other.low as i128);
393        let lh = (self.low as i128).wrapping_mul(other.high);
394
395        Self {
396            low,
397            high: (high as i128).wrapping_add(hl).wrapping_add(lh),
398        }
399    }
400
401    /// Performs checked multiplication
402    #[inline]
403    pub fn checked_mul(self, other: Self) -> Option<Self> {
404        if self == i256::ZERO || other == i256::ZERO {
405            return Some(i256::ZERO);
406        }
407
408        // Shift sign bit down to construct mask of all set bits if negative
409        let l_sa = self.high >> 127;
410        let r_sa = other.high >> 127;
411        let out_sa = (l_sa ^ r_sa) as u128;
412
413        // Compute absolute values
414        let l_abs = self.wrapping_abs();
415        let r_abs = other.wrapping_abs();
416
417        // Overflow if both high parts are non-zero
418        if l_abs.high != 0 && r_abs.high != 0 {
419            return None;
420        }
421
422        // Perform checked multiplication on absolute values
423        let (low, high) = mulx(l_abs.low, r_abs.low);
424
425        // Compute the high multiples, only impacting the high 128-bits
426        let hl = (l_abs.high as u128).checked_mul(r_abs.low)?;
427        let lh = l_abs.low.checked_mul(r_abs.high as u128)?;
428
429        let high = high.checked_add(hl)?.checked_add(lh)?;
430
431        // Reverse absolute value, if necessary
432        let (low, c) = (low ^ out_sa).overflowing_sub(out_sa);
433        let high = (high ^ out_sa).wrapping_sub(out_sa).wrapping_sub(c as u128) as i128;
434
435        // Check for overflow in final conversion
436        (high.is_negative() == (self.is_negative() ^ other.is_negative()))
437            .then_some(Self { low, high })
438    }
439
440    /// Division operation, returns (quotient, remainder).
441    /// This basically implements [Long division]: `<https://en.wikipedia.org/wiki/Division_algorithm>`
442    #[inline]
443    fn div_rem(self, other: Self) -> Result<(Self, Self), DivRemError> {
444        if other == Self::ZERO {
445            return Err(DivRemError::DivideByZero);
446        }
447        if other == Self::MINUS_ONE && self == Self::MIN {
448            return Err(DivRemError::DivideOverflow);
449        }
450
451        let a = self.wrapping_abs();
452        let b = other.wrapping_abs();
453
454        let (div, rem) = div_rem(&a.as_digits(), &b.as_digits());
455        let div = Self::from_digits(div);
456        let rem = Self::from_digits(rem);
457
458        Ok((
459            if self.is_negative() == other.is_negative() {
460                div
461            } else {
462                div.wrapping_neg()
463            },
464            if self.is_negative() {
465                rem.wrapping_neg()
466            } else {
467                rem
468            },
469        ))
470    }
471
472    /// Interpret this [`i256`] as 4 `u64` digits, least significant first
473    fn as_digits(self) -> [u64; 4] {
474        [
475            self.low as u64,
476            (self.low >> 64) as u64,
477            self.high as u64,
478            (self.high as u128 >> 64) as u64,
479        ]
480    }
481
482    /// Interpret 4 `u64` digits, least significant first, as a [`i256`]
483    fn from_digits(digits: [u64; 4]) -> Self {
484        Self::from_parts(
485            digits[0] as u128 | ((digits[1] as u128) << 64),
486            digits[2] as i128 | ((digits[3] as i128) << 64),
487        )
488    }
489
490    /// Performs wrapping division
491    #[inline]
492    pub fn wrapping_div(self, other: Self) -> Self {
493        match self.div_rem(other) {
494            Ok((v, _)) => v,
495            Err(DivRemError::DivideByZero) => panic!("attempt to divide by zero"),
496            Err(_) => Self::MIN,
497        }
498    }
499
500    /// Performs checked division
501    #[inline]
502    pub fn checked_div(self, other: Self) -> Option<Self> {
503        self.div_rem(other).map(|(v, _)| v).ok()
504    }
505
506    /// Performs wrapping remainder
507    #[inline]
508    pub fn wrapping_rem(self, other: Self) -> Self {
509        match self.div_rem(other) {
510            Ok((_, v)) => v,
511            Err(DivRemError::DivideByZero) => panic!("attempt to divide by zero"),
512            Err(_) => Self::ZERO,
513        }
514    }
515
516    /// Performs checked remainder
517    #[inline]
518    pub fn checked_rem(self, other: Self) -> Option<Self> {
519        self.div_rem(other).map(|(_, v)| v).ok()
520    }
521
522    /// Performs checked exponentiation
523    #[inline]
524    pub fn checked_pow(self, mut exp: u32) -> Option<Self> {
525        if exp == 0 {
526            return Some(i256::from_i128(1));
527        }
528
529        let mut base = self;
530        let mut acc: Self = i256::from_i128(1);
531
532        while exp > 1 {
533            if (exp & 1) == 1 {
534                acc = acc.checked_mul(base)?;
535            }
536            exp /= 2;
537            base = base.checked_mul(base)?;
538        }
539        // since exp!=0, finally the exp must be 1.
540        // Deal with the final bit of the exponent separately, since
541        // squaring the base afterwards is not necessary and may cause a
542        // needless overflow.
543        acc.checked_mul(base)
544    }
545
546    /// Performs wrapping exponentiation
547    #[inline]
548    pub fn wrapping_pow(self, mut exp: u32) -> Self {
549        if exp == 0 {
550            return i256::from_i128(1);
551        }
552
553        let mut base = self;
554        let mut acc: Self = i256::from_i128(1);
555
556        while exp > 1 {
557            if (exp & 1) == 1 {
558                acc = acc.wrapping_mul(base);
559            }
560            exp /= 2;
561            base = base.wrapping_mul(base);
562        }
563
564        // since exp!=0, finally the exp must be 1.
565        // Deal with the final bit of the exponent separately, since
566        // squaring the base afterwards is not necessary and may cause a
567        // needless overflow.
568        acc.wrapping_mul(base)
569    }
570
571    /// Returns a number [`i256`] representing sign of this [`i256`].
572    ///
573    /// 0 if the number is zero
574    /// 1 if the number is positive
575    /// -1 if the number is negative
576    pub const fn signum(self) -> Self {
577        if self.is_positive() {
578            i256::ONE
579        } else if self.is_negative() {
580            i256::MINUS_ONE
581        } else {
582            i256::ZERO
583        }
584    }
585
586    /// Returns `true` if this [`i256`] is negative
587    #[inline]
588    pub const fn is_negative(self) -> bool {
589        self.high.is_negative()
590    }
591
592    /// Returns `true` if this [`i256`] is positive
593    pub const fn is_positive(self) -> bool {
594        self.high.is_positive() || self.high == 0 && self.low != 0
595    }
596
597    /// Returns the number of leading zeros in the binary representation of this [`i256`].
598    pub const fn leading_zeros(&self) -> u32 {
599        match self.high {
600            0 => u128::BITS + self.low.leading_zeros(),
601            _ => self.high.leading_zeros(),
602        }
603    }
604
605    /// Returns the number of trailing zeros in the binary representation of this [`i256`].
606    pub const fn trailing_zeros(&self) -> u32 {
607        match self.low {
608            0 => u128::BITS + self.high.trailing_zeros(),
609            _ => self.low.trailing_zeros(),
610        }
611    }
612
613    fn redundant_leading_sign_bits_i256(n: i256) -> u8 {
614        let mask = n >> 255; // all ones or all zeros
615        ((n ^ mask).leading_zeros() - 1) as u8 // we only need one sign bit
616    }
617
618    fn i256_to_f64(input: i256) -> f64 {
619        let k = i256::redundant_leading_sign_bits_i256(input);
620        let n = input << k; // left-justify (no redundant sign bits)
621        let n = (n.high >> 64) as i64; // throw away the lower 192 bits
622        (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)
623    }
624
625    /// Computes the `base` logarithm of the number `self`
626    /// Returns `None` if `self` is less than or equal to zero, or if `base` is less than 2.
627    #[inline]
628    pub fn checked_ilog(self, base: i256) -> Option<u32> {
629        if base == Self::from(10) {
630            // Faster implementation for base 10
631            return self.checked_ilog10();
632        }
633
634        if self <= Self::ZERO {
635            return None;
636        }
637        if base <= Self::ONE {
638            return None;
639        }
640        if self < base {
641            return Some(0);
642        }
643
644        let mut val = 1;
645        let mut base_exp = base;
646
647        let boundary = self.checked_div(base)?;
648        while base_exp <= boundary {
649            val += 1;
650            base_exp = base_exp.checked_mul(base)?;
651        }
652        Some(val)
653    }
654
655    /// Computes the `base` logarithm of the number `self`
656    /// Panic if `self` is less than or equal to zero, or if `base` is less than 2.
657    #[inline]
658    pub fn ilog(self, base: i256) -> u32 {
659        self.checked_ilog(base)
660            .unwrap_or_else(|| panic!("ilog overflow with {self} and base {base}"))
661    }
662
663    /// Computes the decimal logarithm of the number `self`
664    /// Returns `None` if `self` is less than or equal to zero.
665    #[inline]
666    pub fn checked_ilog10(self) -> Option<u32> {
667        if self <= Self::ZERO {
668            return None;
669        }
670        if self < Self::from(10) {
671            return Some(0);
672        }
673
674        // Layered approach to calculate logarithm using i128 log operations only
675        // Consult int_log10.rs stdlib implementiation for u128
676        let pow_64: i256 = i256::from(10).checked_pow(64).unwrap();
677        let pow_32: i256 = i256::from(10).checked_pow(32).unwrap();
678        if self >= pow_64 {
679            let value = self.checked_div(pow_64)?;
680            // self is between 10^64 and 10^77 (~i256::MAX).
681            // `value` is 14 digits max (10^77 / 10^64 = 10^13),
682            // so it fits to `low` u128
683            debug_assert!(value.high == 0);
684            Some(64 + value.low.checked_ilog10()?)
685        } else if self >= pow_32 {
686            let value = self.checked_div(pow_32)?;
687            // self is between 10^32 and 10^64.
688            // `value` is 33 digits max (10^64/10^32=10^32)
689            // so it fits to `low` 128-bit value
690            debug_assert!(value.high == 0);
691            Some(32 + value.low.checked_ilog10()?)
692        } else {
693            // self fits within u128 (high == 0 and self > 0).
694            self.low.checked_ilog10()
695        }
696    }
697
698    /// Computes the decimal logarithm of the number `self`
699    /// Panics if `self` is less than or equal to zero.
700    #[inline]
701    pub fn ilog10(self) -> u32 {
702        self.checked_ilog10()
703            .unwrap_or_else(|| panic!("ilog10 overflow with {self}"))
704    }
705
706    /// Computes the binary logarithm of the number `self`
707    /// Returns `None` if `self` is less than or equal to zero.
708    #[inline]
709    pub fn checked_ilog2(self) -> Option<u32> {
710        self.checked_ilog(i256::from(2))
711    }
712
713    /// Computes the base 2 logarithm of the number, rounded down.
714    #[inline]
715    pub fn ilog2(self) -> u32 {
716        self.checked_ilog2()
717            .unwrap_or_else(|| panic!("ilog2 overflow with {self}"))
718    }
719}
720
721/// Temporary workaround due to lack of stable const array slicing
722/// See <https://github.com/rust-lang/rust/issues/90091>
723const fn split_array<const N: usize, const M: usize>(vals: [u8; N]) -> ([u8; M], [u8; M]) {
724    let mut a = [0; M];
725    let mut b = [0; M];
726    let mut i = 0;
727    while i != M {
728        a[i] = vals[i];
729        b[i] = vals[i + M];
730        i += 1;
731    }
732    (a, b)
733}
734
735/// Performs an unsigned multiplication of `a * b` returning a tuple of
736/// `(low, high)` where `low` contains the lower 128-bits of the result
737/// and `high` the higher 128-bits
738///
739/// This mirrors the x86 mulx instruction but for 128-bit types
740#[inline]
741fn mulx(a: u128, b: u128) -> (u128, u128) {
742    let split = |a: u128| (a & (u64::MAX as u128), a >> 64);
743
744    const MASK: u128 = u64::MAX as _;
745
746    let (a_low, a_high) = split(a);
747    let (b_low, b_high) = split(b);
748
749    // Carry stores the upper 64-bits of low and lower 64-bits of high
750    let (mut low, mut carry) = split(a_low * b_low);
751    carry += a_high * b_low;
752
753    // Update low and high with corresponding parts of carry
754    low += carry << 64;
755    let mut high = carry >> 64;
756
757    // Update carry with overflow from low
758    carry = low >> 64;
759    low &= MASK;
760
761    // Perform multiply including overflow from low
762    carry += b_high * a_low;
763
764    // Update low and high with values from carry
765    low += carry << 64;
766    high += carry >> 64;
767
768    // Perform 4th multiplication
769    high += a_high * b_high;
770
771    (low, high)
772}
773
774derive_arith!(
775    i256,
776    Add,
777    AddAssign,
778    add,
779    add_assign,
780    wrapping_add,
781    checked_add
782);
783derive_arith!(
784    i256,
785    Sub,
786    SubAssign,
787    sub,
788    sub_assign,
789    wrapping_sub,
790    checked_sub
791);
792derive_arith!(
793    i256,
794    Mul,
795    MulAssign,
796    mul,
797    mul_assign,
798    wrapping_mul,
799    checked_mul
800);
801derive_arith!(
802    i256,
803    Div,
804    DivAssign,
805    div,
806    div_assign,
807    wrapping_div,
808    checked_div
809);
810derive_arith!(
811    i256,
812    Rem,
813    RemAssign,
814    rem,
815    rem_assign,
816    wrapping_rem,
817    checked_rem
818);
819
820impl Neg for i256 {
821    type Output = i256;
822
823    #[cfg(debug_assertions)]
824    fn neg(self) -> Self::Output {
825        self.checked_neg().expect("i256 overflow")
826    }
827
828    #[cfg(not(debug_assertions))]
829    fn neg(self) -> Self::Output {
830        self.wrapping_neg()
831    }
832}
833
834impl BitAnd for i256 {
835    type Output = i256;
836
837    #[inline]
838    fn bitand(self, rhs: Self) -> Self::Output {
839        Self {
840            low: self.low & rhs.low,
841            high: self.high & rhs.high,
842        }
843    }
844}
845
846impl BitOr for i256 {
847    type Output = i256;
848
849    #[inline]
850    fn bitor(self, rhs: Self) -> Self::Output {
851        Self {
852            low: self.low | rhs.low,
853            high: self.high | rhs.high,
854        }
855    }
856}
857
858impl BitXor for i256 {
859    type Output = i256;
860
861    #[inline]
862    fn bitxor(self, rhs: Self) -> Self::Output {
863        Self {
864            low: self.low ^ rhs.low,
865            high: self.high ^ rhs.high,
866        }
867    }
868}
869
870impl Shl<u8> for i256 {
871    type Output = i256;
872
873    #[inline]
874    fn shl(self, rhs: u8) -> Self::Output {
875        if rhs == 0 {
876            self
877        } else if rhs < 128 {
878            Self {
879                high: (self.high << rhs) | (self.low >> (128 - rhs)) as i128,
880                low: self.low << rhs,
881            }
882        } else {
883            Self {
884                high: (self.low << (rhs - 128)) as i128,
885                low: 0,
886            }
887        }
888    }
889}
890
891impl Shr<u8> for i256 {
892    type Output = i256;
893
894    #[inline]
895    fn shr(self, rhs: u8) -> Self::Output {
896        if rhs == 0 {
897            self
898        } else if rhs < 128 {
899            Self {
900                high: self.high >> rhs,
901                low: (self.low >> rhs) | ((self.high as u128) << (128 - rhs)),
902            }
903        } else {
904            Self {
905                high: self.high >> 127,
906                low: (self.high >> (rhs - 128)) as u128,
907            }
908        }
909    }
910}
911
912impl WrappingShl for i256 {
913    #[inline]
914    fn wrapping_shl(&self, rhs: u32) -> i256 {
915        // Limit shift to 256 (max valid shift for i256)
916        (*self).shl(rhs as u8)
917    }
918}
919
920impl WrappingShr for i256 {
921    #[inline]
922    fn wrapping_shr(&self, rhs: u32) -> i256 {
923        // Limit shift to 256 (max valid shift for i256)
924        (*self).shr(rhs as u8)
925    }
926}
927
928// Define Shl<T> and Shr<T> for specified integer types using
929// an existing Shl<u8> and Shr<u8> implementation
930macro_rules! define_standard_shift {
931    // Handle multiple types
932    ($trait_name:ident, $method:ident, [$($t:ty),+]) => {
933        $(define_standard_shift!($trait_name, $method, $t);)+
934    };
935    // Handle single type
936    ($trait_name:ident, $method:ident, $t:ty) => {
937        impl $trait_name<$t> for i256 {
938            type Output = i256;
939
940            #[inline]
941            fn $method(self, rhs: $t) -> Self::Output {
942                let rhs = u8::try_from(rhs).expect("rhs overflow for shift");
943                // Other possible overflows are handled by Shl<u8> implementation
944                self.$method(rhs)
945            }
946        }
947    };
948}
949
950define_standard_shift!(
951    Shl,
952    shl,
953    [u16, u32, u64, u128, usize, i16, i32, i64, i128, isize]
954);
955define_standard_shift!(
956    Shr,
957    shr,
958    [u16, u32, u64, u128, usize, i16, i32, i64, i128, isize]
959);
960
961macro_rules! define_as_primitive {
962    ($native_ty:ty) => {
963        impl AsPrimitive<i256> for $native_ty {
964            fn as_(self) -> i256 {
965                i256::from_i128(self as i128)
966            }
967        }
968    };
969}
970
971define_as_primitive!(i8);
972define_as_primitive!(i16);
973define_as_primitive!(i32);
974define_as_primitive!(i64);
975define_as_primitive!(u8);
976define_as_primitive!(u16);
977define_as_primitive!(u32);
978define_as_primitive!(u64);
979
980impl ToPrimitive for i256 {
981    fn to_i64(&self) -> Option<i64> {
982        let as_i128 = self.low as i128;
983
984        let high_negative = self.high < 0;
985        let low_negative = as_i128 < 0;
986        let high_valid = self.high == -1 || self.high == 0;
987
988        if high_negative == low_negative && high_valid {
989            let (low_bytes, high_bytes) = split_array(u128::to_le_bytes(self.low));
990            let high = i64::from_le_bytes(high_bytes);
991            let low = i64::from_le_bytes(low_bytes);
992
993            let high_negative = high < 0;
994            let low_negative = low < 0;
995            let high_valid = self.high == -1 || self.high == 0;
996
997            (high_negative == low_negative && high_valid).then_some(low)
998        } else {
999            None
1000        }
1001    }
1002
1003    fn to_f64(&self) -> Option<f64> {
1004        match *self {
1005            Self::MIN => Some(-2_f64.powi(255)),
1006            Self::ZERO => Some(0f64),
1007            Self::ONE => Some(1f64),
1008            n => Some(Self::i256_to_f64(n)),
1009        }
1010    }
1011
1012    fn to_u64(&self) -> Option<u64> {
1013        let as_i128 = self.low as i128;
1014
1015        let high_negative = self.high < 0;
1016        let low_negative = as_i128 < 0;
1017        let high_valid = self.high == -1 || self.high == 0;
1018
1019        if high_negative == low_negative && high_valid {
1020            self.low.to_u64()
1021        } else {
1022            None
1023        }
1024    }
1025}
1026
1027// num_traits checked implementations
1028
1029impl CheckedNeg for i256 {
1030    fn checked_neg(&self) -> Option<Self> {
1031        (*self).checked_neg()
1032    }
1033}
1034
1035impl CheckedAdd for i256 {
1036    fn checked_add(&self, v: &i256) -> Option<Self> {
1037        (*self).checked_add(*v)
1038    }
1039}
1040
1041impl CheckedSub for i256 {
1042    fn checked_sub(&self, v: &i256) -> Option<Self> {
1043        (*self).checked_sub(*v)
1044    }
1045}
1046
1047impl CheckedDiv for i256 {
1048    fn checked_div(&self, v: &i256) -> Option<Self> {
1049        (*self).checked_div(*v)
1050    }
1051}
1052
1053impl CheckedMul for i256 {
1054    fn checked_mul(&self, v: &i256) -> Option<Self> {
1055        (*self).checked_mul(*v)
1056    }
1057}
1058
1059impl CheckedRem for i256 {
1060    fn checked_rem(&self, v: &i256) -> Option<Self> {
1061        (*self).checked_rem(*v)
1062    }
1063}
1064
1065impl CheckedShl for i256 {
1066    fn checked_shl(&self, rhs: u32) -> Option<Self> {
1067        let rhs = u8::try_from(rhs).ok()?;
1068        Some(self.shl(rhs))
1069    }
1070}
1071
1072impl CheckedShr for i256 {
1073    fn checked_shr(&self, rhs: u32) -> Option<Self> {
1074        let rhs = u8::try_from(rhs).ok()?;
1075        Some(self.shr(rhs))
1076    }
1077}
1078
1079// num_traits wrapping implementations
1080
1081impl WrappingAdd for i256 {
1082    fn wrapping_add(&self, v: &Self) -> Self {
1083        (*self).wrapping_add(*v)
1084    }
1085}
1086
1087impl WrappingSub for i256 {
1088    fn wrapping_sub(&self, v: &Self) -> Self {
1089        (*self).wrapping_sub(*v)
1090    }
1091}
1092
1093impl WrappingMul for i256 {
1094    fn wrapping_mul(&self, v: &Self) -> Self {
1095        (*self).wrapping_mul(*v)
1096    }
1097}
1098
1099impl WrappingNeg for i256 {
1100    fn wrapping_neg(&self) -> Self {
1101        (*self).wrapping_neg()
1102    }
1103}
1104
1105// num_traits saturating implementations
1106
1107impl SaturatingAdd for i256 {
1108    fn saturating_add(&self, v: &Self) -> Self {
1109        self.checked_add(v).unwrap_or_else(|| {
1110            if v.is_negative() {
1111                i256::MIN
1112            } else {
1113                i256::MAX
1114            }
1115        })
1116    }
1117}
1118
1119impl SaturatingSub for i256 {
1120    fn saturating_sub(&self, v: &Self) -> Self {
1121        self.checked_sub(v).unwrap_or_else(|| {
1122            if v.is_negative() {
1123                i256::MAX
1124            } else {
1125                i256::MIN
1126            }
1127        })
1128    }
1129}
1130
1131impl SaturatingMul for i256 {
1132    fn saturating_mul(&self, v: &Self) -> Self {
1133        self.checked_mul(v).unwrap_or_else(|| {
1134            if v.is_negative() == self.is_negative() {
1135                i256::MAX
1136            } else {
1137                i256::MIN
1138            }
1139        })
1140    }
1141}
1142
1143impl MulAdd for i256 {
1144    type Output = i256;
1145
1146    fn mul_add(self, a: Self, b: Self) -> Self::Output {
1147        (self * a) + b
1148    }
1149}
1150
1151impl MulAddAssign for i256 {
1152    fn mul_add_assign(&mut self, a: Self, b: Self) {
1153        *self = self.mul_add(a, b)
1154    }
1155}
1156
1157impl Zero for i256 {
1158    fn zero() -> Self {
1159        i256::ZERO
1160    }
1161
1162    fn is_zero(&self) -> bool {
1163        *self == i256::ZERO
1164    }
1165}
1166
1167impl ConstZero for i256 {
1168    const ZERO: Self = i256::ZERO;
1169}
1170
1171impl One for i256 {
1172    fn one() -> Self {
1173        i256::ONE
1174    }
1175
1176    fn is_one(&self) -> bool {
1177        *self == i256::ONE
1178    }
1179}
1180
1181impl ConstOne for i256 {
1182    const ONE: Self = i256::ONE;
1183}
1184
1185impl Num for i256 {
1186    type FromStrRadixErr = ParseI256Error;
1187
1188    fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
1189        if radix == 10 {
1190            str.parse()
1191        } else {
1192            // Parsing from non-10 baseseeÎ is not supported
1193            Err(ParseI256Error {})
1194        }
1195    }
1196}
1197
1198impl Signed for i256 {
1199    fn abs(&self) -> Self {
1200        self.wrapping_abs()
1201    }
1202
1203    fn abs_sub(&self, other: &Self) -> Self {
1204        if self > other {
1205            self.wrapping_sub(other)
1206        } else {
1207            i256::ZERO
1208        }
1209    }
1210
1211    fn signum(&self) -> Self {
1212        (*self).signum()
1213    }
1214
1215    fn is_positive(&self) -> bool {
1216        (*self).is_positive()
1217    }
1218
1219    fn is_negative(&self) -> bool {
1220        (*self).is_negative()
1221    }
1222}
1223
1224impl Bounded for i256 {
1225    fn min_value() -> Self {
1226        i256::MIN
1227    }
1228
1229    fn max_value() -> Self {
1230        i256::MAX
1231    }
1232}
1233
1234impl Not for i256 {
1235    type Output = i256;
1236
1237    #[inline]
1238    fn not(self) -> Self::Output {
1239        Self::from_parts(!self.low, !self.high)
1240    }
1241}
1242
1243#[cfg(all(test, not(miri)))] // llvm.x86.subborrow.64 not supported by MIRI
1244mod tests {
1245    use super::*;
1246    use num_traits::Signed;
1247    use rand::{Rng, rng};
1248
1249    #[test]
1250    fn test_signed_cmp() {
1251        let a = i256::from_parts(i128::MAX as u128, 12);
1252        let b = i256::from_parts(i128::MIN as u128, 12);
1253        assert!(a < b);
1254
1255        let a = i256::from_parts(i128::MAX as u128, 12);
1256        let b = i256::from_parts(i128::MIN as u128, -12);
1257        assert!(a > b);
1258    }
1259
1260    #[test]
1261    fn test_to_i128() {
1262        let vals = [
1263            BigInt::from_i128(-1).unwrap(),
1264            BigInt::from_i128(i128::MAX).unwrap(),
1265            BigInt::from_i128(i128::MIN).unwrap(),
1266            BigInt::from_u128(u128::MIN).unwrap(),
1267            BigInt::from_u128(u128::MAX).unwrap(),
1268        ];
1269
1270        for v in vals {
1271            let (t, overflow) = i256::from_bigint_with_overflow(v.clone());
1272            assert!(!overflow);
1273            assert_eq!(t.to_i128(), v.to_i128(), "{v} vs {t}");
1274        }
1275    }
1276
1277    /// Tests operations against the two provided [`i256`]
1278    fn test_ops(il: i256, ir: i256) {
1279        let bl = BigInt::from_signed_bytes_le(&il.to_le_bytes());
1280        let br = BigInt::from_signed_bytes_le(&ir.to_le_bytes());
1281
1282        // Comparison
1283        assert_eq!(il.cmp(&ir), bl.cmp(&br), "{bl} cmp {br}");
1284
1285        // Conversions
1286        assert_eq!(i256::from_le_bytes(il.to_le_bytes()), il);
1287        assert_eq!(i256::from_be_bytes(il.to_be_bytes()), il);
1288        assert_eq!(i256::from_le_bytes(ir.to_le_bytes()), ir);
1289        assert_eq!(i256::from_be_bytes(ir.to_be_bytes()), ir);
1290
1291        // To i128
1292        assert_eq!(il.to_i128(), bl.to_i128(), "{bl}");
1293        assert_eq!(ir.to_i128(), br.to_i128(), "{br}");
1294
1295        // Absolute value
1296        let (abs, overflow) = i256::from_bigint_with_overflow(bl.abs());
1297        assert_eq!(il.wrapping_abs(), abs);
1298        assert_eq!(il.checked_abs().is_none(), overflow);
1299
1300        let (abs, overflow) = i256::from_bigint_with_overflow(br.abs());
1301        assert_eq!(ir.wrapping_abs(), abs);
1302        assert_eq!(ir.checked_abs().is_none(), overflow);
1303
1304        // Negation
1305        let (neg, overflow) = i256::from_bigint_with_overflow(bl.clone().neg());
1306        assert_eq!(il.wrapping_neg(), neg);
1307        assert_eq!(il.checked_neg().is_none(), overflow);
1308
1309        // Negation
1310        let (neg, overflow) = i256::from_bigint_with_overflow(br.clone().neg());
1311        assert_eq!(ir.wrapping_neg(), neg);
1312        assert_eq!(ir.checked_neg().is_none(), overflow);
1313
1314        // Addition
1315        let actual = il.wrapping_add(ir);
1316        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() + br.clone());
1317        assert_eq!(actual, expected);
1318
1319        let checked = il.checked_add(ir);
1320        match overflow {
1321            true => assert!(checked.is_none()),
1322            false => assert_eq!(checked, Some(actual)),
1323        }
1324
1325        // Subtraction
1326        let actual = il.wrapping_sub(ir);
1327        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() - br.clone());
1328        assert_eq!(actual.to_string(), expected.to_string());
1329
1330        let checked = il.checked_sub(ir);
1331        match overflow {
1332            true => assert!(checked.is_none()),
1333            false => assert_eq!(checked, Some(actual), "{bl} - {br} = {expected}"),
1334        }
1335
1336        // Multiplication
1337        let actual = il.wrapping_mul(ir);
1338        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() * br.clone());
1339        assert_eq!(actual.to_string(), expected.to_string());
1340
1341        let checked = il.checked_mul(ir);
1342        match overflow {
1343            true => assert!(
1344                checked.is_none(),
1345                "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
1346            ),
1347            false => assert_eq!(
1348                checked,
1349                Some(actual),
1350                "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
1351            ),
1352        }
1353
1354        // Division
1355        if ir != i256::ZERO {
1356            let actual = il.wrapping_div(ir);
1357            let expected = bl.clone() / br.clone();
1358            let checked = il.checked_div(ir);
1359
1360            if ir == i256::MINUS_ONE && il == i256::MIN {
1361                // BigInt produces an integer over i256::MAX
1362                assert_eq!(actual, i256::MIN);
1363                assert!(checked.is_none());
1364            } else {
1365                assert_eq!(actual.to_string(), expected.to_string());
1366                assert_eq!(checked.unwrap().to_string(), expected.to_string());
1367            }
1368        } else {
1369            // `wrapping_div` panics on division by zero
1370            assert!(il.checked_div(ir).is_none());
1371        }
1372
1373        // Remainder
1374        if ir != i256::ZERO {
1375            let actual = il.wrapping_rem(ir);
1376            let expected = bl.clone() % br.clone();
1377            let checked = il.checked_rem(ir);
1378
1379            assert_eq!(actual.to_string(), expected.to_string(), "{il} % {ir}");
1380
1381            if ir == i256::MINUS_ONE && il == i256::MIN {
1382                assert!(checked.is_none());
1383            } else {
1384                assert_eq!(checked.unwrap().to_string(), expected.to_string());
1385            }
1386        } else {
1387            // `wrapping_rem` panics on division by zero
1388            assert!(il.checked_rem(ir).is_none());
1389        }
1390
1391        // Exponentiation
1392        for exp in vec![0, 1, 2, 3, 8, 100].into_iter() {
1393            let actual = il.wrapping_pow(exp);
1394            let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone().pow(exp));
1395            assert_eq!(actual.to_string(), expected.to_string());
1396
1397            let checked = il.checked_pow(exp);
1398            match overflow {
1399                true => assert!(
1400                    checked.is_none(),
1401                    "{il} ^ {exp} = {actual} vs {bl} * {exp} = {expected}"
1402                ),
1403                false => assert_eq!(
1404                    checked,
1405                    Some(actual),
1406                    "{il} ^ {exp} = {actual} vs {bl} ^ {exp} = {expected}"
1407                ),
1408            }
1409        }
1410
1411        // Bit operations
1412        let actual = il & ir;
1413        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() & br.clone());
1414        assert_eq!(actual.to_string(), expected.to_string());
1415
1416        let actual = il | ir;
1417        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() | br.clone());
1418        assert_eq!(actual.to_string(), expected.to_string());
1419
1420        let actual = il ^ ir;
1421        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() ^ br);
1422        assert_eq!(actual.to_string(), expected.to_string());
1423
1424        for shift in [0_u8, 1, 4, 126, 128, 129, 254, 255] {
1425            let actual = il << shift;
1426            let (expected, _) = i256::from_bigint_with_overflow(bl.clone() << shift);
1427            assert_eq!(actual.to_string(), expected.to_string());
1428
1429            let wrapping_actual = <i256 as WrappingShl>::wrapping_shl(&il, shift as u32);
1430            assert_eq!(wrapping_actual.to_string(), expected.to_string());
1431
1432            let actual = il >> shift;
1433            let (expected, _) = i256::from_bigint_with_overflow(bl.clone() >> shift);
1434            assert_eq!(actual.to_string(), expected.to_string());
1435
1436            let wrapping_actual = <i256 as WrappingShr>::wrapping_shr(&il, shift as u32);
1437            assert_eq!(wrapping_actual.to_string(), expected.to_string());
1438
1439            // Check wrapping of the shift argument
1440            let wrapping_actual = <i256 as WrappingShr>::wrapping_shr(&il, 512 + shift as u32);
1441            assert_eq!(wrapping_actual.to_string(), expected.to_string());
1442        }
1443    }
1444
1445    #[test]
1446    fn test_i256() {
1447        let candidates = [
1448            i256::ZERO,
1449            i256::ONE,
1450            i256::MINUS_ONE,
1451            ConstZero::ZERO,
1452            ConstOne::ONE,
1453            i256::from_i128(2),
1454            i256::from_i128(-2),
1455            i256::from_parts(u128::MAX, 1),
1456            i256::from_parts(u128::MAX, -1),
1457            i256::from_parts(0, 1),
1458            i256::from_parts(0, -1),
1459            i256::from_parts(1, -1),
1460            i256::from_parts(1, 1),
1461            i256::from_parts(0, i128::MAX),
1462            i256::from_parts(0, i128::MIN),
1463            i256::from_parts(1, i128::MAX),
1464            i256::from_parts(1, i128::MIN),
1465            i256::from_parts(u128::MAX, i128::MIN),
1466            i256::from_parts(100, 32),
1467            i256::MIN,
1468            i256::MAX,
1469            i256::MIN >> 1,
1470            i256::MAX >> 1,
1471            i256::ONE << 127,
1472            i256::ONE << 128,
1473            i256::ONE << 129,
1474            i256::MINUS_ONE << 127,
1475            i256::MINUS_ONE << 128,
1476            i256::MINUS_ONE << 129,
1477        ];
1478
1479        for il in candidates {
1480            for ir in candidates {
1481                test_ops(il, ir)
1482            }
1483        }
1484    }
1485
1486    #[test]
1487    fn test_signed_ops() {
1488        // signum
1489        assert_eq!(i256::from_i128(1).signum(), i256::ONE);
1490        assert_eq!(i256::from_i128(0).signum(), i256::ZERO);
1491        assert_eq!(i256::from_i128(-0).signum(), i256::ZERO);
1492        assert_eq!(i256::from_i128(-1).signum(), i256::MINUS_ONE);
1493
1494        // is_positive
1495        assert!(i256::from_i128(1).is_positive());
1496        assert!(!i256::from_i128(0).is_positive());
1497        assert!(!i256::from_i128(-0).is_positive());
1498        assert!(!i256::from_i128(-1).is_positive());
1499
1500        // is_negative
1501        assert!(!i256::from_i128(1).is_negative());
1502        assert!(!i256::from_i128(0).is_negative());
1503        assert!(!i256::from_i128(-0).is_negative());
1504        assert!(i256::from_i128(-1).is_negative());
1505    }
1506
1507    #[test]
1508    #[cfg_attr(miri, ignore)]
1509    fn test_i256_fuzz() {
1510        let mut rng = rng();
1511
1512        for _ in 0..1000 {
1513            let mut l = [0_u8; 32];
1514            let len = rng.random_range(0..32);
1515            l.iter_mut().take(len).for_each(|x| *x = rng.random());
1516
1517            let mut r = [0_u8; 32];
1518            let len = rng.random_range(0..32);
1519            r.iter_mut().take(len).for_each(|x| *x = rng.random());
1520
1521            test_ops(i256::from_le_bytes(l), i256::from_le_bytes(r))
1522        }
1523    }
1524
1525    #[test]
1526    fn test_i256_to_primitive() {
1527        let a = i256::MAX;
1528        assert!(a.to_i64().is_none());
1529        assert!(a.to_u64().is_none());
1530
1531        let a = i256::from_i128(i128::MAX);
1532        assert!(a.to_i64().is_none());
1533        assert!(a.to_u64().is_none());
1534
1535        let a = i256::from_i128(i64::MAX as i128);
1536        assert_eq!(a.to_i64().unwrap(), i64::MAX);
1537        assert_eq!(a.to_u64().unwrap(), i64::MAX as u64);
1538
1539        let a = i256::from_i128(i64::MAX as i128 + 1);
1540        assert!(a.to_i64().is_none());
1541        assert_eq!(a.to_u64().unwrap(), i64::MAX as u64 + 1);
1542
1543        let a = i256::MIN;
1544        assert!(a.to_i64().is_none());
1545        assert!(a.to_u64().is_none());
1546
1547        let a = i256::from_i128(i128::MIN);
1548        assert!(a.to_i64().is_none());
1549        assert!(a.to_u64().is_none());
1550
1551        let a = i256::from_i128(i64::MIN as i128);
1552        assert_eq!(a.to_i64().unwrap(), i64::MIN);
1553        assert!(a.to_u64().is_none());
1554
1555        let a = i256::from_i128(i64::MIN as i128 - 1);
1556        assert!(a.to_i64().is_none());
1557        assert!(a.to_u64().is_none());
1558    }
1559
1560    #[test]
1561    fn test_i256_as_i128() {
1562        let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(1));
1563        let i128 = a.as_i128();
1564        assert_eq!(i128, i128::MIN);
1565
1566        let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(2));
1567        let i128 = a.as_i128();
1568        assert_eq!(i128, i128::MIN + 1);
1569
1570        let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(1));
1571        let i128 = a.as_i128();
1572        assert_eq!(i128, i128::MAX);
1573
1574        let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(2));
1575        let i128 = a.as_i128();
1576        assert_eq!(i128, i128::MAX - 1);
1577    }
1578
1579    #[test]
1580    fn test_string_roundtrip() {
1581        let roundtrip_cases = [
1582            i256::ZERO,
1583            i256::ONE,
1584            i256::MINUS_ONE,
1585            i256::from_i128(123456789),
1586            i256::from_i128(-123456789),
1587            i256::from_i128(i128::MIN),
1588            i256::from_i128(i128::MAX),
1589            i256::MIN,
1590            i256::MAX,
1591        ];
1592        for case in roundtrip_cases {
1593            let formatted = case.to_string();
1594            let back: i256 = formatted.parse().unwrap();
1595            assert_eq!(case, back);
1596        }
1597    }
1598
1599    #[test]
1600    fn test_from_string() {
1601        let cases = [
1602            (
1603                "000000000000000000000000000000000000000011",
1604                Some(i256::from_i128(11)),
1605            ),
1606            (
1607                "-000000000000000000000000000000000000000011",
1608                Some(i256::from_i128(-11)),
1609            ),
1610            (
1611                "-0000000000000000000000000000000000000000123456789",
1612                Some(i256::from_i128(-123456789)),
1613            ),
1614            ("-", None),
1615            ("+", None),
1616            ("--1", None),
1617            ("-+1", None),
1618            ("000000000000000000000000000000000000000", Some(i256::ZERO)),
1619            ("0000000000000000000000000000000000000000-11", None),
1620            ("11-1111111111111111111111111111111111111", None),
1621            (
1622                "115792089237316195423570985008687907853269984665640564039457584007913129639936",
1623                None,
1624            ),
1625        ];
1626        for (case, expected) in cases {
1627            assert_eq!(i256::from_string(case), expected)
1628        }
1629    }
1630
1631    #[allow(clippy::op_ref)]
1632    fn test_reference_op(il: i256, ir: i256) {
1633        let r1 = il + ir;
1634        let r2 = &il + ir;
1635        let r3 = il + &ir;
1636        let r4 = &il + &ir;
1637        assert_eq!(r1, r2);
1638        assert_eq!(r1, r3);
1639        assert_eq!(r1, r4);
1640
1641        let r1 = il - ir;
1642        let r2 = &il - ir;
1643        let r3 = il - &ir;
1644        let r4 = &il - &ir;
1645        assert_eq!(r1, r2);
1646        assert_eq!(r1, r3);
1647        assert_eq!(r1, r4);
1648
1649        let r1 = il * ir;
1650        let r2 = &il * ir;
1651        let r3 = il * &ir;
1652        let r4 = &il * &ir;
1653        assert_eq!(r1, r2);
1654        assert_eq!(r1, r3);
1655        assert_eq!(r1, r4);
1656
1657        let r1 = il / ir;
1658        let r2 = &il / ir;
1659        let r3 = il / &ir;
1660        let r4 = &il / &ir;
1661        assert_eq!(r1, r2);
1662        assert_eq!(r1, r3);
1663        assert_eq!(r1, r4);
1664    }
1665
1666    #[test]
1667    fn test_i256_reference_op() {
1668        let candidates = [
1669            i256::ONE,
1670            i256::MINUS_ONE,
1671            i256::from_i128(2),
1672            i256::from_i128(-2),
1673            i256::from_i128(3),
1674            i256::from_i128(-3),
1675        ];
1676
1677        for il in candidates {
1678            for ir in candidates {
1679                test_reference_op(il, ir)
1680            }
1681        }
1682    }
1683
1684    #[test]
1685    fn test_decimal256_to_f64_typical_values() {
1686        let v = i256::from_i128(42_i128);
1687        assert_eq!(v.to_f64().unwrap(), 42.0);
1688
1689        let v = i256::from_i128(-123456789012345678i128);
1690        assert_eq!(v.to_f64().unwrap(), -123456789012345678.0);
1691
1692        let v = i256::from_string("0").unwrap();
1693        assert_eq!(v.to_f64().unwrap(), 0.0);
1694
1695        let v = i256::from_string("1").unwrap();
1696        assert_eq!(v.to_f64().unwrap(), 1.0);
1697
1698        let mut rng = rng();
1699        for _ in 0..10 {
1700            let f64_value =
1701                (rng.random_range(i128::MIN..i128::MAX) as f64) * rng.random_range(0.0..1.0);
1702            let big = i256::from_f64(f64_value).unwrap();
1703            assert_eq!(big.to_f64().unwrap(), f64_value);
1704        }
1705    }
1706
1707    #[test]
1708    fn test_decimal256_to_f64_large_positive_value() {
1709        let max_f = f64::MAX;
1710        let big = i256::from_f64(max_f * 2.0).unwrap_or(i256::MAX);
1711        let out = big.to_f64().unwrap();
1712        assert!(out.is_finite() && out.is_sign_positive());
1713    }
1714
1715    #[test]
1716    fn test_decimal256_to_f64_large_negative_value() {
1717        let max_f = f64::MAX;
1718        let big_neg = i256::from_f64(-(max_f * 2.0)).unwrap_or(i256::MIN);
1719        let out = big_neg.to_f64().unwrap();
1720        assert!(out.is_finite() && out.is_sign_negative());
1721    }
1722
1723    #[test]
1724    fn test_num_traits() {
1725        let value = i256::from_i128(-5);
1726        assert_eq!(
1727            <i256 as CheckedNeg>::checked_neg(&value),
1728            Some(i256::from(5))
1729        );
1730
1731        assert_eq!(
1732            <i256 as CheckedAdd>::checked_add(&value, &value),
1733            Some(i256::from(-10))
1734        );
1735
1736        assert_eq!(
1737            <i256 as CheckedSub>::checked_sub(&value, &value),
1738            Some(i256::from(0))
1739        );
1740
1741        assert_eq!(
1742            <i256 as CheckedMul>::checked_mul(&value, &value),
1743            Some(i256::from(25))
1744        );
1745
1746        assert_eq!(
1747            <i256 as CheckedDiv>::checked_div(&value, &value),
1748            Some(i256::from(1))
1749        );
1750
1751        assert_eq!(
1752            <i256 as CheckedRem>::checked_rem(&value, &value),
1753            Some(i256::from(0))
1754        );
1755
1756        assert_eq!(
1757            <i256 as WrappingAdd>::wrapping_add(&value, &value),
1758            i256::from(-10)
1759        );
1760
1761        assert_eq!(
1762            <i256 as WrappingSub>::wrapping_sub(&value, &value),
1763            i256::from(0)
1764        );
1765
1766        assert_eq!(
1767            <i256 as WrappingMul>::wrapping_mul(&value, &value),
1768            i256::from(25)
1769        );
1770
1771        assert_eq!(<i256 as WrappingNeg>::wrapping_neg(&value), i256::from(5));
1772
1773        // A single check for wrapping behavior, rely on trait implementation for others
1774        let result = <i256 as WrappingAdd>::wrapping_add(&i256::MAX, &i256::ONE);
1775        assert_eq!(result, i256::MIN);
1776
1777        // Saturating operations
1778        assert_eq!(i256::MAX.saturating_add(&i256::ONE), i256::MAX);
1779        assert_eq!(i256::MIN.saturating_sub(&i256::ONE), i256::MIN);
1780        assert_eq!(i256::MIN.saturating_add(&i256::MINUS_ONE), i256::MIN);
1781        assert_eq!(i256::MAX.saturating_sub(&i256::MINUS_ONE), i256::MAX);
1782        assert_eq!(i256::MAX.saturating_mul(&i256::MAX), i256::MAX);
1783        assert_eq!(i256::MAX.saturating_mul(&i256::MIN), i256::MIN);
1784        assert_eq!(i256::MIN.saturating_mul(&i256::MAX), i256::MIN);
1785        assert_eq!(i256::MIN.saturating_mul(&i256::MIN), i256::MAX);
1786        assert_eq!(i256::MIN.saturating_mul(&i256::ONE), i256::MIN);
1787        assert_eq!(i256::MIN.saturating_mul(&i256::MINUS_ONE), i256::MAX);
1788        assert_eq!(
1789            i256::from(20).saturating_add(&i256::from(5)),
1790            i256::from(25)
1791        );
1792        assert_eq!(
1793            i256::from(20).saturating_sub(&i256::from(5)),
1794            i256::from(15)
1795        );
1796        assert_eq!(
1797            i256::from(20).saturating_mul(&i256::from(5)),
1798            i256::from(100)
1799        );
1800
1801        // Mul-add
1802        assert_eq!(
1803            i256::from(20).mul_add(i256::from(5), i256::from(10)),
1804            i256::from(110)
1805        );
1806
1807        let mut mul_add_value = i256::from(20);
1808        mul_add_value.mul_add_assign(i256::from(5), i256::from(10));
1809        assert_eq!(mul_add_value, i256::from(110));
1810
1811        let value = i256::from(-5);
1812        assert_eq!(<i256 as Signed>::abs(&value), i256::from(5));
1813
1814        assert_eq!(<i256 as One>::one(), i256::from(1));
1815        assert_eq!(<i256 as Zero>::zero(), i256::from(0));
1816
1817        assert_eq!(<i256 as Bounded>::min_value(), i256::MIN);
1818        assert_eq!(<i256 as Bounded>::max_value(), i256::MAX);
1819
1820        // Bitwise not
1821        assert_eq!(!i256::ZERO, i256::MINUS_ONE);
1822        assert_eq!(!i256::MINUS_ONE, i256::ZERO);
1823        assert_eq!(!i256::ONE, i256::from_parts(u128::MAX - 1, -1));
1824    }
1825
1826    #[should_panic]
1827    #[test]
1828    fn test_shl_panic_on_arg_overflow() {
1829        let value = i256::from(123);
1830        let rhs = std::hint::black_box(500);
1831        let _ = value << rhs;
1832    }
1833
1834    #[test]
1835    fn test_numtraits_from_str_radix() {
1836        assert_eq!(
1837            i256::from_str_radix("123456789", 10).expect("parsed"),
1838            i256::from(123456789)
1839        );
1840        assert_eq!(
1841            i256::from_str_radix("0", 10).expect("parsed"),
1842            i256::from(0)
1843        );
1844        assert!(i256::from_str_radix("abc", 10).is_err());
1845        assert!(i256::from_str_radix("0", 16).is_err());
1846    }
1847
1848    #[test]
1849    fn test_leading_zeros() {
1850        // Without high part
1851        assert_eq!(i256::from(0).leading_zeros(), 256);
1852        assert_eq!(i256::from(1).leading_zeros(), 256 - 1);
1853        assert_eq!(i256::from(16).leading_zeros(), 256 - 5);
1854        assert_eq!(i256::from(17).leading_zeros(), 256 - 5);
1855
1856        // With high part
1857        assert_eq!(i256::from_parts(2, 16).leading_zeros(), 128 - 5);
1858        assert_eq!(i256::from_parts(2, i128::MAX).leading_zeros(), 1);
1859
1860        assert_eq!(i256::MAX.leading_zeros(), 1);
1861        assert_eq!(i256::from(-1).leading_zeros(), 0);
1862    }
1863
1864    #[test]
1865    fn test_trailing_zeros() {
1866        // Without high part
1867        assert_eq!(i256::from(0).trailing_zeros(), 256);
1868        assert_eq!(i256::from(2).trailing_zeros(), 1);
1869        assert_eq!(i256::from(16).trailing_zeros(), 4);
1870        assert_eq!(i256::from(17).trailing_zeros(), 0);
1871        // With high part
1872        assert_eq!(i256::from_parts(0, i128::MAX).trailing_zeros(), 128);
1873        assert_eq!(i256::from_parts(0, 16).trailing_zeros(), 128 + 4);
1874        assert_eq!(i256::from_parts(2, i128::MAX).trailing_zeros(), 1);
1875
1876        assert_eq!(i256::MAX.trailing_zeros(), 0);
1877        assert_eq!(i256::from(-1).trailing_zeros(), 0);
1878    }
1879
1880    #[test]
1881    fn test_ilog() {
1882        let value = i256::from(128);
1883
1884        // log2
1885        assert_eq!(value.ilog(i256::from(2)), 7);
1886        assert_eq!(value.ilog2(), 7);
1887
1888        // log10
1889        assert_eq!(value.ilog(i256::from(10)), 2);
1890        assert_eq!(value.ilog10(), 2);
1891
1892        // negative base
1893        assert_eq!(value.checked_ilog(i256::from(-2)), None);
1894        assert_eq!(value.checked_ilog(i256::from(-10)), None);
1895        assert_eq!(value.checked_ilog(i256::from(0)), None);
1896        assert_eq!(value.checked_ilog(i256::from(1)), None);
1897
1898        // negative self
1899        let neg_value = i256::from(-128);
1900        assert_eq!(neg_value.checked_ilog(i256::from(2)), None);
1901        assert_eq!(neg_value.checked_ilog(i256::from(10)), None);
1902        assert_eq!(neg_value.checked_ilog10(), None);
1903        assert_eq!(neg_value.checked_ilog2(), None);
1904
1905        // zero self
1906        assert_eq!(i256::ZERO.checked_ilog(i256::from(2)), None);
1907        assert_eq!(i256::ZERO.checked_ilog(i256::from(10)), None);
1908        assert_eq!(i256::ZERO.checked_ilog10(), None);
1909        assert_eq!(i256::ZERO.checked_ilog2(), None);
1910
1911        // self == base, matches std: `n.ilog(n) == 1`
1912        assert_eq!(i256::from(2).checked_ilog(i256::from(2)), Some(1));
1913        assert_eq!(i256::from(3).checked_ilog(i256::from(3)), Some(1));
1914        assert_eq!(i256::from(5).checked_ilog(i256::from(5)), Some(1));
1915        assert_eq!(i256::from(1000).checked_ilog(i256::from(1000)), Some(1));
1916        assert_eq!(i256::from(2).checked_ilog2(), Some(1));
1917        assert_eq!(i256::from(2).ilog2(), 1);
1918        // base 10 goes through the checked_ilog10 fast path
1919        assert_eq!(i256::from(10).checked_ilog(i256::from(10)), Some(1));
1920
1921        // self < base is 0
1922        assert_eq!(i256::from(3).checked_ilog(i256::from(5)), Some(0));
1923
1924        // cross-check small results (0 and 1) against u128::ilog
1925        for base in [2i64, 3, 5, 7, 1000] {
1926            for v in 1i64..64 {
1927                let want = (v as u128).ilog(base as u128);
1928                assert_eq!(
1929                    i256::from(v).checked_ilog(i256::from(base)),
1930                    Some(want),
1931                    "checked_ilog({v}, {base})"
1932                );
1933            }
1934        }
1935
1936        let value = i256::from_parts(100000000, 1234);
1937        assert_eq!(value.checked_ilog(i256::from(10)), Some(41));
1938        assert_eq!(value.checked_ilog10(), Some(41));
1939
1940        // Large i256 values
1941        let large = i256::from_parts(100000000, i128::MAX);
1942        // log2 of 2 powered to approximately 255 should be 254
1943        assert_eq!(large.checked_ilog(i256::from(2)), Some(254));
1944
1945        // log10(large)=76
1946        assert_eq!(large.checked_ilog(i256::from(10)), Some(76));
1947        assert_eq!(large.checked_ilog10(), Some(76));
1948
1949        // log5(large)
1950        assert_eq!(large.checked_ilog(i256::from(5)), Some(109));
1951
1952        // Maximum representable value is 2^254
1953        assert!(i256::from(2).checked_pow(255).is_none());
1954        let value = i256::from(2).checked_pow(254).expect("construct");
1955        assert_eq!(value.checked_ilog(i256::from(2)), Some(254));
1956
1957        // Logarithm of a maximum representable value is 254
1958        assert_eq!(i256::MAX.checked_ilog(i256::from(2)), Some(254));
1959    }
1960
1961    #[test]
1962    fn test_ilog10() {
1963        // Edge cases
1964        assert_eq!(i256::ZERO.checked_ilog10(), None);
1965        assert_eq!(i256::MINUS_ONE.checked_ilog10(), None);
1966        assert_eq!(i256::MAX.checked_ilog10(), Some(76));
1967        assert_eq!(i256::from(10).checked_ilog10(), Some(1));
1968
1969        // small values
1970        assert_eq!(i256::from(1).checked_ilog10(), Some(0));
1971        assert_eq!(i256::from(9).checked_ilog10(), Some(0));
1972
1973        // case with high == 0
1974        assert_eq!(i256::from(100).checked_ilog10(), Some(2));
1975        // case with high == 0 and full low
1976        assert_eq!(i256::from_parts(u128::MAX, 0).checked_ilog10(), Some(38));
1977
1978        // case with high > 0
1979        assert_eq!(i256::from_parts(0, 1).checked_ilog10(), Some(38));
1980
1981        // case with non-null high and low, slow branch
1982        let pow50 = i256::from(10).checked_pow(50).unwrap();
1983        assert_eq!(pow50.checked_ilog10(), Some(50));
1984
1985        // case with non-null high and low, fast branch
1986        let pow64 = i256::from(10).checked_pow(64).unwrap();
1987        assert_eq!(pow64.checked_ilog10(), Some(64));
1988    }
1989
1990    #[test]
1991    #[should_panic(expected = "ilog10 overflow")]
1992    fn test_ilog10_zero_panics() {
1993        let _ = i256::ZERO.ilog10();
1994    }
1995
1996    #[test]
1997    #[should_panic(expected = "ilog overflow")]
1998    fn test_ilog_zero_panics() {
1999        let _ = i256::ZERO.ilog(i256::from(5));
2000    }
2001
2002    #[test]
2003    #[should_panic(expected = "ilog2 overflow")]
2004    fn test_ilog2_zero_panics() {
2005        let _ = i256::ZERO.ilog2();
2006    }
2007}
arrow_buffer/bigint/mod.rs

arrow_buffer/bigint/
mod.rs
