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::cast::AsPrimitive;
21use num::{BigInt, FromPrimitive, ToPrimitive};
22use std::cmp::Ordering;
23use std::num::ParseIntError;
24use std::ops::{BitAnd, BitOr, BitXor, Neg, Shl, Shr};
25use std::str::FromStr;
26
27mod div;
28
29/// An opaque error similar to [`std::num::ParseIntError`]
30#[derive(Debug)]
31pub struct ParseI256Error {}
32
33impl From<ParseIntError> for ParseI256Error {
34    fn from(_: ParseIntError) -> Self {
35        Self {}
36    }
37}
38
39impl std::fmt::Display for ParseI256Error {
40    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
41        write!(f, "Failed to parse as i256")
42    }
43}
44impl std::error::Error for ParseI256Error {}
45
46/// Error returned by i256::DivRem
47enum DivRemError {
48    /// Division by zero
49    DivideByZero,
50    /// Division overflow
51    DivideOverflow,
52}
53
54/// A signed 256-bit integer
55#[allow(non_camel_case_types)]
56#[derive(Copy, Clone, Default, Eq, PartialEq, Hash)]
57#[repr(C)]
58pub struct i256 {
59    low: u128,
60    high: i128,
61}
62
63impl std::fmt::Debug for i256 {
64    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
65        write!(f, "{self}")
66    }
67}
68
69impl std::fmt::Display for i256 {
70    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
71        write!(f, "{}", BigInt::from_signed_bytes_le(&self.to_le_bytes()))
72    }
73}
74
75impl FromStr for i256 {
76    type Err = ParseI256Error;
77
78    fn from_str(s: &str) -> Result<Self, Self::Err> {
79        // i128 can store up to 38 decimal digits
80        if s.len() <= 38 {
81            return Ok(Self::from_i128(i128::from_str(s)?));
82        }
83
84        let (negative, s) = match s.as_bytes()[0] {
85            b'-' => (true, &s[1..]),
86            b'+' => (false, &s[1..]),
87            _ => (false, s),
88        };
89
90        // Trim leading 0s
91        let s = s.trim_start_matches('0');
92        if s.is_empty() {
93            return Ok(i256::ZERO);
94        }
95
96        if !s.as_bytes()[0].is_ascii_digit() {
97            // Ensures no duplicate sign
98            return Err(ParseI256Error {});
99        }
100
101        parse_impl(s, negative)
102    }
103}
104
105impl From<i8> for i256 {
106    fn from(value: i8) -> Self {
107        Self::from_i128(value.into())
108    }
109}
110
111impl From<i16> for i256 {
112    fn from(value: i16) -> Self {
113        Self::from_i128(value.into())
114    }
115}
116
117impl From<i32> for i256 {
118    fn from(value: i32) -> Self {
119        Self::from_i128(value.into())
120    }
121}
122
123impl From<i64> for i256 {
124    fn from(value: i64) -> Self {
125        Self::from_i128(value.into())
126    }
127}
128
129/// Parse `s` with any sign and leading 0s removed
130fn parse_impl(s: &str, negative: bool) -> Result<i256, ParseI256Error> {
131    if s.len() <= 38 {
132        let low = i128::from_str(s)?;
133        return Ok(match negative {
134            true => i256::from_parts(low.neg() as _, -1),
135            false => i256::from_parts(low as _, 0),
136        });
137    }
138
139    let split = s.len() - 38;
140    if !s.as_bytes()[split].is_ascii_digit() {
141        // Ensures not splitting codepoint and no sign
142        return Err(ParseI256Error {});
143    }
144    let (hs, ls) = s.split_at(split);
145
146    let mut low = i128::from_str(ls)?;
147    let high = parse_impl(hs, negative)?;
148
149    if negative {
150        low = -low;
151    }
152
153    let low = i256::from_i128(low);
154
155    high.checked_mul(i256::from_i128(10_i128.pow(38)))
156        .and_then(|high| high.checked_add(low))
157        .ok_or(ParseI256Error {})
158}
159
160impl PartialOrd for i256 {
161    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
162        Some(self.cmp(other))
163    }
164}
165
166impl Ord for i256 {
167    fn cmp(&self, other: &Self) -> Ordering {
168        // This is 25x faster than using a variable length encoding such
169        // as BigInt as it avoids allocation and branching
170        self.high.cmp(&other.high).then(self.low.cmp(&other.low))
171    }
172}
173
174impl i256 {
175    /// The additive identity for this integer type, i.e. `0`.
176    pub const ZERO: Self = i256 { low: 0, high: 0 };
177
178    /// The multiplicative identity for this integer type, i.e. `1`.
179    pub const ONE: Self = i256 { low: 1, high: 0 };
180
181    /// The multiplicative inverse for this integer type, i.e. `-1`.
182    pub const MINUS_ONE: Self = i256 {
183        low: u128::MAX,
184        high: -1,
185    };
186
187    /// The maximum value that can be represented by this integer type
188    pub const MAX: Self = i256 {
189        low: u128::MAX,
190        high: i128::MAX,
191    };
192
193    /// The minimum value that can be represented by this integer type
194    pub const MIN: Self = i256 {
195        low: u128::MIN,
196        high: i128::MIN,
197    };
198
199    /// Create an integer value from its representation as a byte array in little-endian.
200    #[inline]
201    pub const fn from_le_bytes(b: [u8; 32]) -> Self {
202        let (low, high) = split_array(b);
203        Self {
204            high: i128::from_le_bytes(high),
205            low: u128::from_le_bytes(low),
206        }
207    }
208
209    /// Create an integer value from its representation as a byte array in big-endian.
210    #[inline]
211    pub const fn from_be_bytes(b: [u8; 32]) -> Self {
212        let (high, low) = split_array(b);
213        Self {
214            high: i128::from_be_bytes(high),
215            low: u128::from_be_bytes(low),
216        }
217    }
218
219    /// Create an `i256` value from a 128-bit value.
220    pub const fn from_i128(v: i128) -> Self {
221        Self::from_parts(v as u128, v >> 127)
222    }
223
224    /// Create an integer value from its representation as string.
225    #[inline]
226    pub fn from_string(value_str: &str) -> Option<Self> {
227        value_str.parse().ok()
228    }
229
230    /// Create an optional i256 from the provided `f64`. Returning `None`
231    /// if overflow occurred
232    pub fn from_f64(v: f64) -> Option<Self> {
233        BigInt::from_f64(v).and_then(|i| {
234            let (integer, overflow) = i256::from_bigint_with_overflow(i);
235            if overflow {
236                None
237            } else {
238                Some(integer)
239            }
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::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
591/// Temporary workaround due to lack of stable const array slicing
592/// See <https://github.com/rust-lang/rust/issues/90091>
593const fn split_array<const N: usize, const M: usize>(vals: [u8; N]) -> ([u8; M], [u8; M]) {
594    let mut a = [0; M];
595    let mut b = [0; M];
596    let mut i = 0;
597    while i != M {
598        a[i] = vals[i];
599        b[i] = vals[i + M];
600        i += 1;
601    }
602    (a, b)
603}
604
605/// Performs an unsigned multiplication of `a * b` returning a tuple of
606/// `(low, high)` where `low` contains the lower 128-bits of the result
607/// and `high` the higher 128-bits
608///
609/// This mirrors the x86 mulx instruction but for 128-bit types
610#[inline]
611fn mulx(a: u128, b: u128) -> (u128, u128) {
612    let split = |a: u128| (a & (u64::MAX as u128), a >> 64);
613
614    const MASK: u128 = u64::MAX as _;
615
616    let (a_low, a_high) = split(a);
617    let (b_low, b_high) = split(b);
618
619    // Carry stores the upper 64-bits of low and lower 64-bits of high
620    let (mut low, mut carry) = split(a_low * b_low);
621    carry += a_high * b_low;
622
623    // Update low and high with corresponding parts of carry
624    low += carry << 64;
625    let mut high = carry >> 64;
626
627    // Update carry with overflow from low
628    carry = low >> 64;
629    low &= MASK;
630
631    // Perform multiply including overflow from low
632    carry += b_high * a_low;
633
634    // Update low and high with values from carry
635    low += carry << 64;
636    high += carry >> 64;
637
638    // Perform 4th multiplication
639    high += a_high * b_high;
640
641    (low, high)
642}
643
644derive_arith!(
645    i256,
646    Add,
647    AddAssign,
648    add,
649    add_assign,
650    wrapping_add,
651    checked_add
652);
653derive_arith!(
654    i256,
655    Sub,
656    SubAssign,
657    sub,
658    sub_assign,
659    wrapping_sub,
660    checked_sub
661);
662derive_arith!(
663    i256,
664    Mul,
665    MulAssign,
666    mul,
667    mul_assign,
668    wrapping_mul,
669    checked_mul
670);
671derive_arith!(
672    i256,
673    Div,
674    DivAssign,
675    div,
676    div_assign,
677    wrapping_div,
678    checked_div
679);
680derive_arith!(
681    i256,
682    Rem,
683    RemAssign,
684    rem,
685    rem_assign,
686    wrapping_rem,
687    checked_rem
688);
689
690impl Neg for i256 {
691    type Output = i256;
692
693    #[cfg(debug_assertions)]
694    fn neg(self) -> Self::Output {
695        self.checked_neg().expect("i256 overflow")
696    }
697
698    #[cfg(not(debug_assertions))]
699    fn neg(self) -> Self::Output {
700        self.wrapping_neg()
701    }
702}
703
704impl BitAnd for i256 {
705    type Output = i256;
706
707    #[inline]
708    fn bitand(self, rhs: Self) -> Self::Output {
709        Self {
710            low: self.low & rhs.low,
711            high: self.high & rhs.high,
712        }
713    }
714}
715
716impl BitOr for i256 {
717    type Output = i256;
718
719    #[inline]
720    fn bitor(self, rhs: Self) -> Self::Output {
721        Self {
722            low: self.low | rhs.low,
723            high: self.high | rhs.high,
724        }
725    }
726}
727
728impl BitXor for i256 {
729    type Output = i256;
730
731    #[inline]
732    fn bitxor(self, rhs: Self) -> Self::Output {
733        Self {
734            low: self.low ^ rhs.low,
735            high: self.high ^ rhs.high,
736        }
737    }
738}
739
740impl Shl<u8> for i256 {
741    type Output = i256;
742
743    #[inline]
744    fn shl(self, rhs: u8) -> Self::Output {
745        if rhs == 0 {
746            self
747        } else if rhs < 128 {
748            Self {
749                high: (self.high << rhs) | (self.low >> (128 - rhs)) as i128,
750                low: self.low << rhs,
751            }
752        } else {
753            Self {
754                high: (self.low << (rhs - 128)) as i128,
755                low: 0,
756            }
757        }
758    }
759}
760
761impl Shr<u8> for i256 {
762    type Output = i256;
763
764    #[inline]
765    fn shr(self, rhs: u8) -> Self::Output {
766        if rhs == 0 {
767            self
768        } else if rhs < 128 {
769            Self {
770                high: self.high >> rhs,
771                low: (self.low >> rhs) | ((self.high as u128) << (128 - rhs)),
772            }
773        } else {
774            Self {
775                high: self.high >> 127,
776                low: (self.high >> (rhs - 128)) as u128,
777            }
778        }
779    }
780}
781
782macro_rules! define_as_primitive {
783    ($native_ty:ty) => {
784        impl AsPrimitive<i256> for $native_ty {
785            fn as_(self) -> i256 {
786                i256::from_i128(self as i128)
787            }
788        }
789    };
790}
791
792define_as_primitive!(i8);
793define_as_primitive!(i16);
794define_as_primitive!(i32);
795define_as_primitive!(i64);
796define_as_primitive!(u8);
797define_as_primitive!(u16);
798define_as_primitive!(u32);
799define_as_primitive!(u64);
800
801impl ToPrimitive for i256 {
802    fn to_i64(&self) -> Option<i64> {
803        let as_i128 = self.low as i128;
804
805        let high_negative = self.high < 0;
806        let low_negative = as_i128 < 0;
807        let high_valid = self.high == -1 || self.high == 0;
808
809        if high_negative == low_negative && high_valid {
810            let (low_bytes, high_bytes) = split_array(u128::to_le_bytes(self.low));
811            let high = i64::from_le_bytes(high_bytes);
812            let low = i64::from_le_bytes(low_bytes);
813
814            let high_negative = high < 0;
815            let low_negative = low < 0;
816            let high_valid = self.high == -1 || self.high == 0;
817
818            (high_negative == low_negative && high_valid).then_some(low)
819        } else {
820            None
821        }
822    }
823
824    fn to_f64(&self) -> Option<f64> {
825        let mag = if let Some(u) = self.checked_abs() {
826            let (low, high) = u.to_parts();
827            (high as f64) * 2_f64.powi(128) + (low as f64)
828        } else {
829            // self == MIN
830            2_f64.powi(255)
831        };
832        if *self < i256::ZERO {
833            Some(-mag)
834        } else {
835            Some(mag)
836        }
837    }
838    fn to_u64(&self) -> Option<u64> {
839        let as_i128 = self.low as i128;
840
841        let high_negative = self.high < 0;
842        let low_negative = as_i128 < 0;
843        let high_valid = self.high == -1 || self.high == 0;
844
845        if high_negative == low_negative && high_valid {
846            self.low.to_u64()
847        } else {
848            None
849        }
850    }
851}
852
853#[cfg(all(test, not(miri)))] // llvm.x86.subborrow.64 not supported by MIRI
854mod tests {
855    use super::*;
856    use num::Signed;
857    use rand::{rng, Rng};
858
859    #[test]
860    fn test_signed_cmp() {
861        let a = i256::from_parts(i128::MAX as u128, 12);
862        let b = i256::from_parts(i128::MIN as u128, 12);
863        assert!(a < b);
864
865        let a = i256::from_parts(i128::MAX as u128, 12);
866        let b = i256::from_parts(i128::MIN as u128, -12);
867        assert!(a > b);
868    }
869
870    #[test]
871    fn test_to_i128() {
872        let vals = [
873            BigInt::from_i128(-1).unwrap(),
874            BigInt::from_i128(i128::MAX).unwrap(),
875            BigInt::from_i128(i128::MIN).unwrap(),
876            BigInt::from_u128(u128::MIN).unwrap(),
877            BigInt::from_u128(u128::MAX).unwrap(),
878        ];
879
880        for v in vals {
881            let (t, overflow) = i256::from_bigint_with_overflow(v.clone());
882            assert!(!overflow);
883            assert_eq!(t.to_i128(), v.to_i128(), "{v} vs {t}");
884        }
885    }
886
887    /// Tests operations against the two provided [`i256`]
888    fn test_ops(il: i256, ir: i256) {
889        let bl = BigInt::from_signed_bytes_le(&il.to_le_bytes());
890        let br = BigInt::from_signed_bytes_le(&ir.to_le_bytes());
891
892        // Comparison
893        assert_eq!(il.cmp(&ir), bl.cmp(&br), "{bl} cmp {br}");
894
895        // Conversions
896        assert_eq!(i256::from_le_bytes(il.to_le_bytes()), il);
897        assert_eq!(i256::from_be_bytes(il.to_be_bytes()), il);
898        assert_eq!(i256::from_le_bytes(ir.to_le_bytes()), ir);
899        assert_eq!(i256::from_be_bytes(ir.to_be_bytes()), ir);
900
901        // To i128
902        assert_eq!(il.to_i128(), bl.to_i128(), "{bl}");
903        assert_eq!(ir.to_i128(), br.to_i128(), "{br}");
904
905        // Absolute value
906        let (abs, overflow) = i256::from_bigint_with_overflow(bl.abs());
907        assert_eq!(il.wrapping_abs(), abs);
908        assert_eq!(il.checked_abs().is_none(), overflow);
909
910        let (abs, overflow) = i256::from_bigint_with_overflow(br.abs());
911        assert_eq!(ir.wrapping_abs(), abs);
912        assert_eq!(ir.checked_abs().is_none(), overflow);
913
914        // Negation
915        let (neg, overflow) = i256::from_bigint_with_overflow(bl.clone().neg());
916        assert_eq!(il.wrapping_neg(), neg);
917        assert_eq!(il.checked_neg().is_none(), overflow);
918
919        // Negation
920        let (neg, overflow) = i256::from_bigint_with_overflow(br.clone().neg());
921        assert_eq!(ir.wrapping_neg(), neg);
922        assert_eq!(ir.checked_neg().is_none(), overflow);
923
924        // Addition
925        let actual = il.wrapping_add(ir);
926        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() + br.clone());
927        assert_eq!(actual, expected);
928
929        let checked = il.checked_add(ir);
930        match overflow {
931            true => assert!(checked.is_none()),
932            false => assert_eq!(checked, Some(actual)),
933        }
934
935        // Subtraction
936        let actual = il.wrapping_sub(ir);
937        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() - br.clone());
938        assert_eq!(actual.to_string(), expected.to_string());
939
940        let checked = il.checked_sub(ir);
941        match overflow {
942            true => assert!(checked.is_none()),
943            false => assert_eq!(checked, Some(actual), "{bl} - {br} = {expected}"),
944        }
945
946        // Multiplication
947        let actual = il.wrapping_mul(ir);
948        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() * br.clone());
949        assert_eq!(actual.to_string(), expected.to_string());
950
951        let checked = il.checked_mul(ir);
952        match overflow {
953            true => assert!(
954                checked.is_none(),
955                "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
956            ),
957            false => assert_eq!(
958                checked,
959                Some(actual),
960                "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
961            ),
962        }
963
964        // Division
965        if ir != i256::ZERO {
966            let actual = il.wrapping_div(ir);
967            let expected = bl.clone() / br.clone();
968            let checked = il.checked_div(ir);
969
970            if ir == i256::MINUS_ONE && il == i256::MIN {
971                // BigInt produces an integer over i256::MAX
972                assert_eq!(actual, i256::MIN);
973                assert!(checked.is_none());
974            } else {
975                assert_eq!(actual.to_string(), expected.to_string());
976                assert_eq!(checked.unwrap().to_string(), expected.to_string());
977            }
978        } else {
979            // `wrapping_div` panics on division by zero
980            assert!(il.checked_div(ir).is_none());
981        }
982
983        // Remainder
984        if ir != i256::ZERO {
985            let actual = il.wrapping_rem(ir);
986            let expected = bl.clone() % br.clone();
987            let checked = il.checked_rem(ir);
988
989            assert_eq!(actual.to_string(), expected.to_string(), "{il} % {ir}");
990
991            if ir == i256::MINUS_ONE && il == i256::MIN {
992                assert!(checked.is_none());
993            } else {
994                assert_eq!(checked.unwrap().to_string(), expected.to_string());
995            }
996        } else {
997            // `wrapping_rem` panics on division by zero
998            assert!(il.checked_rem(ir).is_none());
999        }
1000
1001        // Exponentiation
1002        for exp in vec![0, 1, 2, 3, 8, 100].into_iter() {
1003            let actual = il.wrapping_pow(exp);
1004            let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone().pow(exp));
1005            assert_eq!(actual.to_string(), expected.to_string());
1006
1007            let checked = il.checked_pow(exp);
1008            match overflow {
1009                true => assert!(
1010                    checked.is_none(),
1011                    "{il} ^ {exp} = {actual} vs {bl} * {exp} = {expected}"
1012                ),
1013                false => assert_eq!(
1014                    checked,
1015                    Some(actual),
1016                    "{il} ^ {exp} = {actual} vs {bl} ^ {exp} = {expected}"
1017                ),
1018            }
1019        }
1020
1021        // Bit operations
1022        let actual = il & ir;
1023        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() & br.clone());
1024        assert_eq!(actual.to_string(), expected.to_string());
1025
1026        let actual = il | ir;
1027        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() | br.clone());
1028        assert_eq!(actual.to_string(), expected.to_string());
1029
1030        let actual = il ^ ir;
1031        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() ^ br);
1032        assert_eq!(actual.to_string(), expected.to_string());
1033
1034        for shift in [0_u8, 1, 4, 126, 128, 129, 254, 255] {
1035            let actual = il << shift;
1036            let (expected, _) = i256::from_bigint_with_overflow(bl.clone() << shift);
1037            assert_eq!(actual.to_string(), expected.to_string());
1038
1039            let actual = il >> shift;
1040            let (expected, _) = i256::from_bigint_with_overflow(bl.clone() >> shift);
1041            assert_eq!(actual.to_string(), expected.to_string());
1042        }
1043    }
1044
1045    #[test]
1046    fn test_i256() {
1047        let candidates = [
1048            i256::ZERO,
1049            i256::ONE,
1050            i256::MINUS_ONE,
1051            i256::from_i128(2),
1052            i256::from_i128(-2),
1053            i256::from_parts(u128::MAX, 1),
1054            i256::from_parts(u128::MAX, -1),
1055            i256::from_parts(0, 1),
1056            i256::from_parts(0, -1),
1057            i256::from_parts(1, -1),
1058            i256::from_parts(1, 1),
1059            i256::from_parts(0, i128::MAX),
1060            i256::from_parts(0, i128::MIN),
1061            i256::from_parts(1, i128::MAX),
1062            i256::from_parts(1, i128::MIN),
1063            i256::from_parts(u128::MAX, i128::MIN),
1064            i256::from_parts(100, 32),
1065            i256::MIN,
1066            i256::MAX,
1067            i256::MIN >> 1,
1068            i256::MAX >> 1,
1069            i256::ONE << 127,
1070            i256::ONE << 128,
1071            i256::ONE << 129,
1072            i256::MINUS_ONE << 127,
1073            i256::MINUS_ONE << 128,
1074            i256::MINUS_ONE << 129,
1075        ];
1076
1077        for il in candidates {
1078            for ir in candidates {
1079                test_ops(il, ir)
1080            }
1081        }
1082    }
1083
1084    #[test]
1085    fn test_signed_ops() {
1086        // signum
1087        assert_eq!(i256::from_i128(1).signum(), i256::ONE);
1088        assert_eq!(i256::from_i128(0).signum(), i256::ZERO);
1089        assert_eq!(i256::from_i128(-0).signum(), i256::ZERO);
1090        assert_eq!(i256::from_i128(-1).signum(), i256::MINUS_ONE);
1091
1092        // is_positive
1093        assert!(i256::from_i128(1).is_positive());
1094        assert!(!i256::from_i128(0).is_positive());
1095        assert!(!i256::from_i128(-0).is_positive());
1096        assert!(!i256::from_i128(-1).is_positive());
1097
1098        // is_negative
1099        assert!(!i256::from_i128(1).is_negative());
1100        assert!(!i256::from_i128(0).is_negative());
1101        assert!(!i256::from_i128(-0).is_negative());
1102        assert!(i256::from_i128(-1).is_negative());
1103    }
1104
1105    #[test]
1106    #[cfg_attr(miri, ignore)]
1107    fn test_i256_fuzz() {
1108        let mut rng = rng();
1109
1110        for _ in 0..1000 {
1111            let mut l = [0_u8; 32];
1112            let len = rng.random_range(0..32);
1113            l.iter_mut().take(len).for_each(|x| *x = rng.random());
1114
1115            let mut r = [0_u8; 32];
1116            let len = rng.random_range(0..32);
1117            r.iter_mut().take(len).for_each(|x| *x = rng.random());
1118
1119            test_ops(i256::from_le_bytes(l), i256::from_le_bytes(r))
1120        }
1121    }
1122
1123    #[test]
1124    fn test_i256_to_primitive() {
1125        let a = i256::MAX;
1126        assert!(a.to_i64().is_none());
1127        assert!(a.to_u64().is_none());
1128
1129        let a = i256::from_i128(i128::MAX);
1130        assert!(a.to_i64().is_none());
1131        assert!(a.to_u64().is_none());
1132
1133        let a = i256::from_i128(i64::MAX as i128);
1134        assert_eq!(a.to_i64().unwrap(), i64::MAX);
1135        assert_eq!(a.to_u64().unwrap(), i64::MAX as u64);
1136
1137        let a = i256::from_i128(i64::MAX as i128 + 1);
1138        assert!(a.to_i64().is_none());
1139        assert_eq!(a.to_u64().unwrap(), i64::MAX as u64 + 1);
1140
1141        let a = i256::MIN;
1142        assert!(a.to_i64().is_none());
1143        assert!(a.to_u64().is_none());
1144
1145        let a = i256::from_i128(i128::MIN);
1146        assert!(a.to_i64().is_none());
1147        assert!(a.to_u64().is_none());
1148
1149        let a = i256::from_i128(i64::MIN as i128);
1150        assert_eq!(a.to_i64().unwrap(), i64::MIN);
1151        assert!(a.to_u64().is_none());
1152
1153        let a = i256::from_i128(i64::MIN as i128 - 1);
1154        assert!(a.to_i64().is_none());
1155        assert!(a.to_u64().is_none());
1156    }
1157
1158    #[test]
1159    fn test_i256_as_i128() {
1160        let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(1));
1161        let i128 = a.as_i128();
1162        assert_eq!(i128, i128::MIN);
1163
1164        let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(2));
1165        let i128 = a.as_i128();
1166        assert_eq!(i128, i128::MIN + 1);
1167
1168        let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(1));
1169        let i128 = a.as_i128();
1170        assert_eq!(i128, i128::MAX);
1171
1172        let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(2));
1173        let i128 = a.as_i128();
1174        assert_eq!(i128, i128::MAX - 1);
1175    }
1176
1177    #[test]
1178    fn test_string_roundtrip() {
1179        let roundtrip_cases = [
1180            i256::ZERO,
1181            i256::ONE,
1182            i256::MINUS_ONE,
1183            i256::from_i128(123456789),
1184            i256::from_i128(-123456789),
1185            i256::from_i128(i128::MIN),
1186            i256::from_i128(i128::MAX),
1187            i256::MIN,
1188            i256::MAX,
1189        ];
1190        for case in roundtrip_cases {
1191            let formatted = case.to_string();
1192            let back: i256 = formatted.parse().unwrap();
1193            assert_eq!(case, back);
1194        }
1195    }
1196
1197    #[test]
1198    fn test_from_string() {
1199        let cases = [
1200            (
1201                "000000000000000000000000000000000000000011",
1202                Some(i256::from_i128(11)),
1203            ),
1204            (
1205                "-000000000000000000000000000000000000000011",
1206                Some(i256::from_i128(-11)),
1207            ),
1208            (
1209                "-0000000000000000000000000000000000000000123456789",
1210                Some(i256::from_i128(-123456789)),
1211            ),
1212            ("-", None),
1213            ("+", None),
1214            ("--1", None),
1215            ("-+1", None),
1216            ("000000000000000000000000000000000000000", Some(i256::ZERO)),
1217            ("0000000000000000000000000000000000000000-11", None),
1218            ("11-1111111111111111111111111111111111111", None),
1219            (
1220                "115792089237316195423570985008687907853269984665640564039457584007913129639936",
1221                None,
1222            ),
1223        ];
1224        for (case, expected) in cases {
1225            assert_eq!(i256::from_string(case), expected)
1226        }
1227    }
1228
1229    #[allow(clippy::op_ref)]
1230    fn test_reference_op(il: i256, ir: i256) {
1231        let r1 = il + ir;
1232        let r2 = &il + ir;
1233        let r3 = il + &ir;
1234        let r4 = &il + &ir;
1235        assert_eq!(r1, r2);
1236        assert_eq!(r1, r3);
1237        assert_eq!(r1, r4);
1238
1239        let r1 = il - ir;
1240        let r2 = &il - ir;
1241        let r3 = il - &ir;
1242        let r4 = &il - &ir;
1243        assert_eq!(r1, r2);
1244        assert_eq!(r1, r3);
1245        assert_eq!(r1, r4);
1246
1247        let r1 = il * ir;
1248        let r2 = &il * ir;
1249        let r3 = il * &ir;
1250        let r4 = &il * &ir;
1251        assert_eq!(r1, r2);
1252        assert_eq!(r1, r3);
1253        assert_eq!(r1, r4);
1254
1255        let r1 = il / ir;
1256        let r2 = &il / ir;
1257        let r3 = il / &ir;
1258        let r4 = &il / &ir;
1259        assert_eq!(r1, r2);
1260        assert_eq!(r1, r3);
1261        assert_eq!(r1, r4);
1262    }
1263
1264    #[test]
1265    fn test_i256_reference_op() {
1266        let candidates = [
1267            i256::ONE,
1268            i256::MINUS_ONE,
1269            i256::from_i128(2),
1270            i256::from_i128(-2),
1271            i256::from_i128(3),
1272            i256::from_i128(-3),
1273        ];
1274
1275        for il in candidates {
1276            for ir in candidates {
1277                test_reference_op(il, ir)
1278            }
1279        }
1280    }
1281
1282    #[test]
1283    fn test_decimal256_to_f64_typical_values() {
1284        let v = i256::from_i128(42_i128);
1285        assert_eq!(v.to_f64().unwrap(), 42.0);
1286
1287        let v = i256::from_i128(-123456789012345678i128);
1288        assert_eq!(v.to_f64().unwrap(), -123456789012345678.0);
1289    }
1290
1291    #[test]
1292    fn test_decimal256_to_f64_large_positive_value() {
1293        let max_f = f64::MAX;
1294        let big = i256::from_f64(max_f * 2.0).unwrap_or(i256::MAX);
1295        let out = big.to_f64().unwrap();
1296        assert!(out.is_finite() && out.is_sign_positive());
1297    }
1298
1299    #[test]
1300    fn test_decimal256_to_f64_large_negative_value() {
1301        let max_f = f64::MAX;
1302        let big_neg = i256::from_f64(-(max_f * 2.0)).unwrap_or(i256::MIN);
1303        let out = big_neg.to_f64().unwrap();
1304        assert!(out.is_finite() && out.is_sign_negative());
1305    }
1306}
arrow_buffer/bigint/mod.rs

arrow_buffer/bigint/
mod.rs
