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::{FromPrimitive, ToPrimitive, cast::AsPrimitive};
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 { None } else { Some(integer) }
236        })
237    }
238
239    /// Create an i256 from the provided low u128 and high i128
240    #[inline]
241    pub const fn from_parts(low: u128, high: i128) -> Self {
242        Self { low, high }
243    }
244
245    /// Returns this `i256` as a low u128 and high i128
246    pub const fn to_parts(self) -> (u128, i128) {
247        (self.low, self.high)
248    }
249
250    /// Converts this `i256` into an `i128` returning `None` if this would result
251    /// in truncation/overflow
252    pub fn to_i128(self) -> Option<i128> {
253        let as_i128 = self.low as i128;
254
255        let high_negative = self.high < 0;
256        let low_negative = as_i128 < 0;
257        let high_valid = self.high == -1 || self.high == 0;
258
259        (high_negative == low_negative && high_valid).then_some(self.low as i128)
260    }
261
262    /// Wraps this `i256` into an `i128`
263    pub fn as_i128(self) -> i128 {
264        self.low as i128
265    }
266
267    /// Return the memory representation of this integer as a byte array in little-endian byte order.
268    #[inline]
269    pub const fn to_le_bytes(self) -> [u8; 32] {
270        let low = self.low.to_le_bytes();
271        let high = self.high.to_le_bytes();
272        let mut t = [0; 32];
273        let mut i = 0;
274        while i != 16 {
275            t[i] = low[i];
276            t[i + 16] = high[i];
277            i += 1;
278        }
279        t
280    }
281
282    /// Return the memory representation of this integer as a byte array in big-endian byte order.
283    #[inline]
284    pub const fn to_be_bytes(self) -> [u8; 32] {
285        let low = self.low.to_be_bytes();
286        let high = self.high.to_be_bytes();
287        let mut t = [0; 32];
288        let mut i = 0;
289        while i != 16 {
290            t[i] = high[i];
291            t[i + 16] = low[i];
292            i += 1;
293        }
294        t
295    }
296
297    /// Create an i256 from the provided [`BigInt`] returning a bool indicating
298    /// if overflow occurred
299    fn from_bigint_with_overflow(v: BigInt) -> (Self, bool) {
300        let v_bytes = v.to_signed_bytes_le();
301        match v_bytes.len().cmp(&32) {
302            Ordering::Less => {
303                let mut bytes = if num_traits::Signed::is_negative(&v) {
304                    [255_u8; 32]
305                } else {
306                    [0; 32]
307                };
308                bytes[0..v_bytes.len()].copy_from_slice(&v_bytes[..v_bytes.len()]);
309                (Self::from_le_bytes(bytes), false)
310            }
311            Ordering::Equal => (Self::from_le_bytes(v_bytes.try_into().unwrap()), false),
312            Ordering::Greater => (Self::from_le_bytes(v_bytes[..32].try_into().unwrap()), true),
313        }
314    }
315
316    /// Computes the absolute value of this i256
317    #[inline]
318    pub fn wrapping_abs(self) -> Self {
319        // -1 if negative, otherwise 0
320        let sa = self.high >> 127;
321        let sa = Self::from_parts(sa as u128, sa);
322
323        // Inverted if negative
324        Self::from_parts(self.low ^ sa.low, self.high ^ sa.high).wrapping_sub(sa)
325    }
326
327    /// Computes the absolute value of this i256 returning `None` if `Self == Self::MIN`
328    #[inline]
329    pub fn checked_abs(self) -> Option<Self> {
330        (self != Self::MIN).then(|| self.wrapping_abs())
331    }
332
333    /// Negates this i256
334    #[inline]
335    pub fn wrapping_neg(self) -> Self {
336        Self::from_parts(!self.low, !self.high).wrapping_add(i256::ONE)
337    }
338
339    /// Negates this i256 returning `None` if `Self == Self::MIN`
340    #[inline]
341    pub fn checked_neg(self) -> Option<Self> {
342        (self != Self::MIN).then(|| self.wrapping_neg())
343    }
344
345    /// Performs wrapping addition
346    #[inline]
347    pub fn wrapping_add(self, other: Self) -> Self {
348        let (low, carry) = self.low.overflowing_add(other.low);
349        let high = self.high.wrapping_add(other.high).wrapping_add(carry as _);
350        Self { low, high }
351    }
352
353    /// Performs checked addition
354    #[inline]
355    pub fn checked_add(self, other: Self) -> Option<Self> {
356        let r = self.wrapping_add(other);
357        ((other.is_negative() && r < self) || (!other.is_negative() && r >= self)).then_some(r)
358    }
359
360    /// Performs wrapping subtraction
361    #[inline]
362    pub fn wrapping_sub(self, other: Self) -> Self {
363        let (low, carry) = self.low.overflowing_sub(other.low);
364        let high = self.high.wrapping_sub(other.high).wrapping_sub(carry as _);
365        Self { low, high }
366    }
367
368    /// Performs checked subtraction
369    #[inline]
370    pub fn checked_sub(self, other: Self) -> Option<Self> {
371        let r = self.wrapping_sub(other);
372        ((other.is_negative() && r > self) || (!other.is_negative() && r <= self)).then_some(r)
373    }
374
375    /// Performs wrapping multiplication
376    #[inline]
377    pub fn wrapping_mul(self, other: Self) -> Self {
378        let (low, high) = mulx(self.low, other.low);
379
380        // Compute the high multiples, only impacting the high 128-bits
381        let hl = self.high.wrapping_mul(other.low as i128);
382        let lh = (self.low as i128).wrapping_mul(other.high);
383
384        Self {
385            low,
386            high: (high as i128).wrapping_add(hl).wrapping_add(lh),
387        }
388    }
389
390    /// Performs checked multiplication
391    #[inline]
392    pub fn checked_mul(self, other: Self) -> Option<Self> {
393        if self == i256::ZERO || other == i256::ZERO {
394            return Some(i256::ZERO);
395        }
396
397        // Shift sign bit down to construct mask of all set bits if negative
398        let l_sa = self.high >> 127;
399        let r_sa = other.high >> 127;
400        let out_sa = (l_sa ^ r_sa) as u128;
401
402        // Compute absolute values
403        let l_abs = self.wrapping_abs();
404        let r_abs = other.wrapping_abs();
405
406        // Overflow if both high parts are non-zero
407        if l_abs.high != 0 && r_abs.high != 0 {
408            return None;
409        }
410
411        // Perform checked multiplication on absolute values
412        let (low, high) = mulx(l_abs.low, r_abs.low);
413
414        // Compute the high multiples, only impacting the high 128-bits
415        let hl = (l_abs.high as u128).checked_mul(r_abs.low)?;
416        let lh = l_abs.low.checked_mul(r_abs.high as u128)?;
417
418        let high = high.checked_add(hl)?.checked_add(lh)?;
419
420        // Reverse absolute value, if necessary
421        let (low, c) = (low ^ out_sa).overflowing_sub(out_sa);
422        let high = (high ^ out_sa).wrapping_sub(out_sa).wrapping_sub(c as u128) as i128;
423
424        // Check for overflow in final conversion
425        (high.is_negative() == (self.is_negative() ^ other.is_negative()))
426            .then_some(Self { low, high })
427    }
428
429    /// Division operation, returns (quotient, remainder).
430    /// This basically implements [Long division]: `<https://en.wikipedia.org/wiki/Division_algorithm>`
431    #[inline]
432    fn div_rem(self, other: Self) -> Result<(Self, Self), DivRemError> {
433        if other == Self::ZERO {
434            return Err(DivRemError::DivideByZero);
435        }
436        if other == Self::MINUS_ONE && self == Self::MIN {
437            return Err(DivRemError::DivideOverflow);
438        }
439
440        let a = self.wrapping_abs();
441        let b = other.wrapping_abs();
442
443        let (div, rem) = div_rem(&a.as_digits(), &b.as_digits());
444        let div = Self::from_digits(div);
445        let rem = Self::from_digits(rem);
446
447        Ok((
448            if self.is_negative() == other.is_negative() {
449                div
450            } else {
451                div.wrapping_neg()
452            },
453            if self.is_negative() {
454                rem.wrapping_neg()
455            } else {
456                rem
457            },
458        ))
459    }
460
461    /// Interpret this [`i256`] as 4 `u64` digits, least significant first
462    fn as_digits(self) -> [u64; 4] {
463        [
464            self.low as u64,
465            (self.low >> 64) as u64,
466            self.high as u64,
467            (self.high as u128 >> 64) as u64,
468        ]
469    }
470
471    /// Interpret 4 `u64` digits, least significant first, as a [`i256`]
472    fn from_digits(digits: [u64; 4]) -> Self {
473        Self::from_parts(
474            digits[0] as u128 | ((digits[1] as u128) << 64),
475            digits[2] as i128 | ((digits[3] as i128) << 64),
476        )
477    }
478
479    /// Performs wrapping division
480    #[inline]
481    pub fn wrapping_div(self, other: Self) -> Self {
482        match self.div_rem(other) {
483            Ok((v, _)) => v,
484            Err(DivRemError::DivideByZero) => panic!("attempt to divide by zero"),
485            Err(_) => Self::MIN,
486        }
487    }
488
489    /// Performs checked division
490    #[inline]
491    pub fn checked_div(self, other: Self) -> Option<Self> {
492        self.div_rem(other).map(|(v, _)| v).ok()
493    }
494
495    /// Performs wrapping remainder
496    #[inline]
497    pub fn wrapping_rem(self, other: Self) -> Self {
498        match self.div_rem(other) {
499            Ok((_, v)) => v,
500            Err(DivRemError::DivideByZero) => panic!("attempt to divide by zero"),
501            Err(_) => Self::ZERO,
502        }
503    }
504
505    /// Performs checked remainder
506    #[inline]
507    pub fn checked_rem(self, other: Self) -> Option<Self> {
508        self.div_rem(other).map(|(_, v)| v).ok()
509    }
510
511    /// Performs checked exponentiation
512    #[inline]
513    pub fn checked_pow(self, mut exp: u32) -> Option<Self> {
514        if exp == 0 {
515            return Some(i256::from_i128(1));
516        }
517
518        let mut base = self;
519        let mut acc: Self = i256::from_i128(1);
520
521        while exp > 1 {
522            if (exp & 1) == 1 {
523                acc = acc.checked_mul(base)?;
524            }
525            exp /= 2;
526            base = base.checked_mul(base)?;
527        }
528        // since exp!=0, finally the exp must be 1.
529        // Deal with the final bit of the exponent separately, since
530        // squaring the base afterwards is not necessary and may cause a
531        // needless overflow.
532        acc.checked_mul(base)
533    }
534
535    /// Performs wrapping exponentiation
536    #[inline]
537    pub fn wrapping_pow(self, mut exp: u32) -> Self {
538        if exp == 0 {
539            return i256::from_i128(1);
540        }
541
542        let mut base = self;
543        let mut acc: Self = i256::from_i128(1);
544
545        while exp > 1 {
546            if (exp & 1) == 1 {
547                acc = acc.wrapping_mul(base);
548            }
549            exp /= 2;
550            base = base.wrapping_mul(base);
551        }
552
553        // since exp!=0, finally the exp must be 1.
554        // Deal with the final bit of the exponent separately, since
555        // squaring the base afterwards is not necessary and may cause a
556        // needless overflow.
557        acc.wrapping_mul(base)
558    }
559
560    /// Returns a number [`i256`] representing sign of this [`i256`].
561    ///
562    /// 0 if the number is zero
563    /// 1 if the number is positive
564    /// -1 if the number is negative
565    pub const fn signum(self) -> Self {
566        if self.is_positive() {
567            i256::ONE
568        } else if self.is_negative() {
569            i256::MINUS_ONE
570        } else {
571            i256::ZERO
572        }
573    }
574
575    /// Returns `true` if this [`i256`] is negative
576    #[inline]
577    pub const fn is_negative(self) -> bool {
578        self.high.is_negative()
579    }
580
581    /// Returns `true` if this [`i256`] is positive
582    pub const fn is_positive(self) -> bool {
583        self.high.is_positive() || self.high == 0 && self.low != 0
584    }
585
586    fn leading_zeros(&self) -> u32 {
587        match self.high {
588            0 => u128::BITS + self.low.leading_zeros(),
589            _ => self.high.leading_zeros(),
590        }
591    }
592
593    fn redundant_leading_sign_bits_i256(n: i256) -> u8 {
594        let mask = n >> 255; // all ones or all zeros
595        ((n ^ mask).leading_zeros() - 1) as u8 // we only need one sign bit
596    }
597
598    fn i256_to_f64(input: i256) -> f64 {
599        let k = i256::redundant_leading_sign_bits_i256(input);
600        let n = input << k; // left-justify (no redundant sign bits)
601        let n = (n.high >> 64) as i64; // throw away the lower 192 bits
602        (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)
603    }
604}
605
606/// Temporary workaround due to lack of stable const array slicing
607/// See <https://github.com/rust-lang/rust/issues/90091>
608const fn split_array<const N: usize, const M: usize>(vals: [u8; N]) -> ([u8; M], [u8; M]) {
609    let mut a = [0; M];
610    let mut b = [0; M];
611    let mut i = 0;
612    while i != M {
613        a[i] = vals[i];
614        b[i] = vals[i + M];
615        i += 1;
616    }
617    (a, b)
618}
619
620/// Performs an unsigned multiplication of `a * b` returning a tuple of
621/// `(low, high)` where `low` contains the lower 128-bits of the result
622/// and `high` the higher 128-bits
623///
624/// This mirrors the x86 mulx instruction but for 128-bit types
625#[inline]
626fn mulx(a: u128, b: u128) -> (u128, u128) {
627    let split = |a: u128| (a & (u64::MAX as u128), a >> 64);
628
629    const MASK: u128 = u64::MAX as _;
630
631    let (a_low, a_high) = split(a);
632    let (b_low, b_high) = split(b);
633
634    // Carry stores the upper 64-bits of low and lower 64-bits of high
635    let (mut low, mut carry) = split(a_low * b_low);
636    carry += a_high * b_low;
637
638    // Update low and high with corresponding parts of carry
639    low += carry << 64;
640    let mut high = carry >> 64;
641
642    // Update carry with overflow from low
643    carry = low >> 64;
644    low &= MASK;
645
646    // Perform multiply including overflow from low
647    carry += b_high * a_low;
648
649    // Update low and high with values from carry
650    low += carry << 64;
651    high += carry >> 64;
652
653    // Perform 4th multiplication
654    high += a_high * b_high;
655
656    (low, high)
657}
658
659derive_arith!(
660    i256,
661    Add,
662    AddAssign,
663    add,
664    add_assign,
665    wrapping_add,
666    checked_add
667);
668derive_arith!(
669    i256,
670    Sub,
671    SubAssign,
672    sub,
673    sub_assign,
674    wrapping_sub,
675    checked_sub
676);
677derive_arith!(
678    i256,
679    Mul,
680    MulAssign,
681    mul,
682    mul_assign,
683    wrapping_mul,
684    checked_mul
685);
686derive_arith!(
687    i256,
688    Div,
689    DivAssign,
690    div,
691    div_assign,
692    wrapping_div,
693    checked_div
694);
695derive_arith!(
696    i256,
697    Rem,
698    RemAssign,
699    rem,
700    rem_assign,
701    wrapping_rem,
702    checked_rem
703);
704
705impl Neg for i256 {
706    type Output = i256;
707
708    #[cfg(debug_assertions)]
709    fn neg(self) -> Self::Output {
710        self.checked_neg().expect("i256 overflow")
711    }
712
713    #[cfg(not(debug_assertions))]
714    fn neg(self) -> Self::Output {
715        self.wrapping_neg()
716    }
717}
718
719impl BitAnd for i256 {
720    type Output = i256;
721
722    #[inline]
723    fn bitand(self, rhs: Self) -> Self::Output {
724        Self {
725            low: self.low & rhs.low,
726            high: self.high & rhs.high,
727        }
728    }
729}
730
731impl BitOr for i256 {
732    type Output = i256;
733
734    #[inline]
735    fn bitor(self, rhs: Self) -> Self::Output {
736        Self {
737            low: self.low | rhs.low,
738            high: self.high | rhs.high,
739        }
740    }
741}
742
743impl BitXor for i256 {
744    type Output = i256;
745
746    #[inline]
747    fn bitxor(self, rhs: Self) -> Self::Output {
748        Self {
749            low: self.low ^ rhs.low,
750            high: self.high ^ rhs.high,
751        }
752    }
753}
754
755impl Shl<u8> for i256 {
756    type Output = i256;
757
758    #[inline]
759    fn shl(self, rhs: u8) -> Self::Output {
760        if rhs == 0 {
761            self
762        } else if rhs < 128 {
763            Self {
764                high: (self.high << rhs) | (self.low >> (128 - rhs)) as i128,
765                low: self.low << rhs,
766            }
767        } else {
768            Self {
769                high: (self.low << (rhs - 128)) as i128,
770                low: 0,
771            }
772        }
773    }
774}
775
776impl Shr<u8> for i256 {
777    type Output = i256;
778
779    #[inline]
780    fn shr(self, rhs: u8) -> Self::Output {
781        if rhs == 0 {
782            self
783        } else if rhs < 128 {
784            Self {
785                high: self.high >> rhs,
786                low: (self.low >> rhs) | ((self.high as u128) << (128 - rhs)),
787            }
788        } else {
789            Self {
790                high: self.high >> 127,
791                low: (self.high >> (rhs - 128)) as u128,
792            }
793        }
794    }
795}
796
797macro_rules! define_as_primitive {
798    ($native_ty:ty) => {
799        impl AsPrimitive<i256> for $native_ty {
800            fn as_(self) -> i256 {
801                i256::from_i128(self as i128)
802            }
803        }
804    };
805}
806
807define_as_primitive!(i8);
808define_as_primitive!(i16);
809define_as_primitive!(i32);
810define_as_primitive!(i64);
811define_as_primitive!(u8);
812define_as_primitive!(u16);
813define_as_primitive!(u32);
814define_as_primitive!(u64);
815
816impl ToPrimitive for i256 {
817    fn to_i64(&self) -> Option<i64> {
818        let as_i128 = self.low as i128;
819
820        let high_negative = self.high < 0;
821        let low_negative = as_i128 < 0;
822        let high_valid = self.high == -1 || self.high == 0;
823
824        if high_negative == low_negative && high_valid {
825            let (low_bytes, high_bytes) = split_array(u128::to_le_bytes(self.low));
826            let high = i64::from_le_bytes(high_bytes);
827            let low = i64::from_le_bytes(low_bytes);
828
829            let high_negative = high < 0;
830            let low_negative = low < 0;
831            let high_valid = self.high == -1 || self.high == 0;
832
833            (high_negative == low_negative && high_valid).then_some(low)
834        } else {
835            None
836        }
837    }
838
839    fn to_f64(&self) -> Option<f64> {
840        match *self {
841            Self::MIN => Some(-2_f64.powi(255)),
842            Self::ZERO => Some(0f64),
843            Self::ONE => Some(1f64),
844            n => Some(Self::i256_to_f64(n)),
845        }
846    }
847
848    fn to_u64(&self) -> Option<u64> {
849        let as_i128 = self.low as i128;
850
851        let high_negative = self.high < 0;
852        let low_negative = as_i128 < 0;
853        let high_valid = self.high == -1 || self.high == 0;
854
855        if high_negative == low_negative && high_valid {
856            self.low.to_u64()
857        } else {
858            None
859        }
860    }
861}
862
863#[cfg(all(test, not(miri)))] // llvm.x86.subborrow.64 not supported by MIRI
864mod tests {
865    use super::*;
866    use num_traits::Signed;
867    use rand::{Rng, rng};
868
869    #[test]
870    fn test_signed_cmp() {
871        let a = i256::from_parts(i128::MAX as u128, 12);
872        let b = i256::from_parts(i128::MIN as u128, 12);
873        assert!(a < b);
874
875        let a = i256::from_parts(i128::MAX as u128, 12);
876        let b = i256::from_parts(i128::MIN as u128, -12);
877        assert!(a > b);
878    }
879
880    #[test]
881    fn test_to_i128() {
882        let vals = [
883            BigInt::from_i128(-1).unwrap(),
884            BigInt::from_i128(i128::MAX).unwrap(),
885            BigInt::from_i128(i128::MIN).unwrap(),
886            BigInt::from_u128(u128::MIN).unwrap(),
887            BigInt::from_u128(u128::MAX).unwrap(),
888        ];
889
890        for v in vals {
891            let (t, overflow) = i256::from_bigint_with_overflow(v.clone());
892            assert!(!overflow);
893            assert_eq!(t.to_i128(), v.to_i128(), "{v} vs {t}");
894        }
895    }
896
897    /// Tests operations against the two provided [`i256`]
898    fn test_ops(il: i256, ir: i256) {
899        let bl = BigInt::from_signed_bytes_le(&il.to_le_bytes());
900        let br = BigInt::from_signed_bytes_le(&ir.to_le_bytes());
901
902        // Comparison
903        assert_eq!(il.cmp(&ir), bl.cmp(&br), "{bl} cmp {br}");
904
905        // Conversions
906        assert_eq!(i256::from_le_bytes(il.to_le_bytes()), il);
907        assert_eq!(i256::from_be_bytes(il.to_be_bytes()), il);
908        assert_eq!(i256::from_le_bytes(ir.to_le_bytes()), ir);
909        assert_eq!(i256::from_be_bytes(ir.to_be_bytes()), ir);
910
911        // To i128
912        assert_eq!(il.to_i128(), bl.to_i128(), "{bl}");
913        assert_eq!(ir.to_i128(), br.to_i128(), "{br}");
914
915        // Absolute value
916        let (abs, overflow) = i256::from_bigint_with_overflow(bl.abs());
917        assert_eq!(il.wrapping_abs(), abs);
918        assert_eq!(il.checked_abs().is_none(), overflow);
919
920        let (abs, overflow) = i256::from_bigint_with_overflow(br.abs());
921        assert_eq!(ir.wrapping_abs(), abs);
922        assert_eq!(ir.checked_abs().is_none(), overflow);
923
924        // Negation
925        let (neg, overflow) = i256::from_bigint_with_overflow(bl.clone().neg());
926        assert_eq!(il.wrapping_neg(), neg);
927        assert_eq!(il.checked_neg().is_none(), overflow);
928
929        // Negation
930        let (neg, overflow) = i256::from_bigint_with_overflow(br.clone().neg());
931        assert_eq!(ir.wrapping_neg(), neg);
932        assert_eq!(ir.checked_neg().is_none(), overflow);
933
934        // Addition
935        let actual = il.wrapping_add(ir);
936        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() + br.clone());
937        assert_eq!(actual, expected);
938
939        let checked = il.checked_add(ir);
940        match overflow {
941            true => assert!(checked.is_none()),
942            false => assert_eq!(checked, Some(actual)),
943        }
944
945        // Subtraction
946        let actual = il.wrapping_sub(ir);
947        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() - br.clone());
948        assert_eq!(actual.to_string(), expected.to_string());
949
950        let checked = il.checked_sub(ir);
951        match overflow {
952            true => assert!(checked.is_none()),
953            false => assert_eq!(checked, Some(actual), "{bl} - {br} = {expected}"),
954        }
955
956        // Multiplication
957        let actual = il.wrapping_mul(ir);
958        let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() * br.clone());
959        assert_eq!(actual.to_string(), expected.to_string());
960
961        let checked = il.checked_mul(ir);
962        match overflow {
963            true => assert!(
964                checked.is_none(),
965                "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
966            ),
967            false => assert_eq!(
968                checked,
969                Some(actual),
970                "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
971            ),
972        }
973
974        // Division
975        if ir != i256::ZERO {
976            let actual = il.wrapping_div(ir);
977            let expected = bl.clone() / br.clone();
978            let checked = il.checked_div(ir);
979
980            if ir == i256::MINUS_ONE && il == i256::MIN {
981                // BigInt produces an integer over i256::MAX
982                assert_eq!(actual, i256::MIN);
983                assert!(checked.is_none());
984            } else {
985                assert_eq!(actual.to_string(), expected.to_string());
986                assert_eq!(checked.unwrap().to_string(), expected.to_string());
987            }
988        } else {
989            // `wrapping_div` panics on division by zero
990            assert!(il.checked_div(ir).is_none());
991        }
992
993        // Remainder
994        if ir != i256::ZERO {
995            let actual = il.wrapping_rem(ir);
996            let expected = bl.clone() % br.clone();
997            let checked = il.checked_rem(ir);
998
999            assert_eq!(actual.to_string(), expected.to_string(), "{il} % {ir}");
1000
1001            if ir == i256::MINUS_ONE && il == i256::MIN {
1002                assert!(checked.is_none());
1003            } else {
1004                assert_eq!(checked.unwrap().to_string(), expected.to_string());
1005            }
1006        } else {
1007            // `wrapping_rem` panics on division by zero
1008            assert!(il.checked_rem(ir).is_none());
1009        }
1010
1011        // Exponentiation
1012        for exp in vec![0, 1, 2, 3, 8, 100].into_iter() {
1013            let actual = il.wrapping_pow(exp);
1014            let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone().pow(exp));
1015            assert_eq!(actual.to_string(), expected.to_string());
1016
1017            let checked = il.checked_pow(exp);
1018            match overflow {
1019                true => assert!(
1020                    checked.is_none(),
1021                    "{il} ^ {exp} = {actual} vs {bl} * {exp} = {expected}"
1022                ),
1023                false => assert_eq!(
1024                    checked,
1025                    Some(actual),
1026                    "{il} ^ {exp} = {actual} vs {bl} ^ {exp} = {expected}"
1027                ),
1028            }
1029        }
1030
1031        // Bit operations
1032        let actual = il & ir;
1033        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() & br.clone());
1034        assert_eq!(actual.to_string(), expected.to_string());
1035
1036        let actual = il | ir;
1037        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() | br.clone());
1038        assert_eq!(actual.to_string(), expected.to_string());
1039
1040        let actual = il ^ ir;
1041        let (expected, _) = i256::from_bigint_with_overflow(bl.clone() ^ br);
1042        assert_eq!(actual.to_string(), expected.to_string());
1043
1044        for shift in [0_u8, 1, 4, 126, 128, 129, 254, 255] {
1045            let actual = il << shift;
1046            let (expected, _) = i256::from_bigint_with_overflow(bl.clone() << shift);
1047            assert_eq!(actual.to_string(), expected.to_string());
1048
1049            let actual = il >> shift;
1050            let (expected, _) = i256::from_bigint_with_overflow(bl.clone() >> shift);
1051            assert_eq!(actual.to_string(), expected.to_string());
1052        }
1053    }
1054
1055    #[test]
1056    fn test_i256() {
1057        let candidates = [
1058            i256::ZERO,
1059            i256::ONE,
1060            i256::MINUS_ONE,
1061            i256::from_i128(2),
1062            i256::from_i128(-2),
1063            i256::from_parts(u128::MAX, 1),
1064            i256::from_parts(u128::MAX, -1),
1065            i256::from_parts(0, 1),
1066            i256::from_parts(0, -1),
1067            i256::from_parts(1, -1),
1068            i256::from_parts(1, 1),
1069            i256::from_parts(0, i128::MAX),
1070            i256::from_parts(0, i128::MIN),
1071            i256::from_parts(1, i128::MAX),
1072            i256::from_parts(1, i128::MIN),
1073            i256::from_parts(u128::MAX, i128::MIN),
1074            i256::from_parts(100, 32),
1075            i256::MIN,
1076            i256::MAX,
1077            i256::MIN >> 1,
1078            i256::MAX >> 1,
1079            i256::ONE << 127,
1080            i256::ONE << 128,
1081            i256::ONE << 129,
1082            i256::MINUS_ONE << 127,
1083            i256::MINUS_ONE << 128,
1084            i256::MINUS_ONE << 129,
1085        ];
1086
1087        for il in candidates {
1088            for ir in candidates {
1089                test_ops(il, ir)
1090            }
1091        }
1092    }
1093
1094    #[test]
1095    fn test_signed_ops() {
1096        // signum
1097        assert_eq!(i256::from_i128(1).signum(), i256::ONE);
1098        assert_eq!(i256::from_i128(0).signum(), i256::ZERO);
1099        assert_eq!(i256::from_i128(-0).signum(), i256::ZERO);
1100        assert_eq!(i256::from_i128(-1).signum(), i256::MINUS_ONE);
1101
1102        // is_positive
1103        assert!(i256::from_i128(1).is_positive());
1104        assert!(!i256::from_i128(0).is_positive());
1105        assert!(!i256::from_i128(-0).is_positive());
1106        assert!(!i256::from_i128(-1).is_positive());
1107
1108        // is_negative
1109        assert!(!i256::from_i128(1).is_negative());
1110        assert!(!i256::from_i128(0).is_negative());
1111        assert!(!i256::from_i128(-0).is_negative());
1112        assert!(i256::from_i128(-1).is_negative());
1113    }
1114
1115    #[test]
1116    #[cfg_attr(miri, ignore)]
1117    fn test_i256_fuzz() {
1118        let mut rng = rng();
1119
1120        for _ in 0..1000 {
1121            let mut l = [0_u8; 32];
1122            let len = rng.random_range(0..32);
1123            l.iter_mut().take(len).for_each(|x| *x = rng.random());
1124
1125            let mut r = [0_u8; 32];
1126            let len = rng.random_range(0..32);
1127            r.iter_mut().take(len).for_each(|x| *x = rng.random());
1128
1129            test_ops(i256::from_le_bytes(l), i256::from_le_bytes(r))
1130        }
1131    }
1132
1133    #[test]
1134    fn test_i256_to_primitive() {
1135        let a = i256::MAX;
1136        assert!(a.to_i64().is_none());
1137        assert!(a.to_u64().is_none());
1138
1139        let a = i256::from_i128(i128::MAX);
1140        assert!(a.to_i64().is_none());
1141        assert!(a.to_u64().is_none());
1142
1143        let a = i256::from_i128(i64::MAX as i128);
1144        assert_eq!(a.to_i64().unwrap(), i64::MAX);
1145        assert_eq!(a.to_u64().unwrap(), i64::MAX as u64);
1146
1147        let a = i256::from_i128(i64::MAX as i128 + 1);
1148        assert!(a.to_i64().is_none());
1149        assert_eq!(a.to_u64().unwrap(), i64::MAX as u64 + 1);
1150
1151        let a = i256::MIN;
1152        assert!(a.to_i64().is_none());
1153        assert!(a.to_u64().is_none());
1154
1155        let a = i256::from_i128(i128::MIN);
1156        assert!(a.to_i64().is_none());
1157        assert!(a.to_u64().is_none());
1158
1159        let a = i256::from_i128(i64::MIN as i128);
1160        assert_eq!(a.to_i64().unwrap(), i64::MIN);
1161        assert!(a.to_u64().is_none());
1162
1163        let a = i256::from_i128(i64::MIN as i128 - 1);
1164        assert!(a.to_i64().is_none());
1165        assert!(a.to_u64().is_none());
1166    }
1167
1168    #[test]
1169    fn test_i256_as_i128() {
1170        let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(1));
1171        let i128 = a.as_i128();
1172        assert_eq!(i128, i128::MIN);
1173
1174        let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(2));
1175        let i128 = a.as_i128();
1176        assert_eq!(i128, i128::MIN + 1);
1177
1178        let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(1));
1179        let i128 = a.as_i128();
1180        assert_eq!(i128, i128::MAX);
1181
1182        let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(2));
1183        let i128 = a.as_i128();
1184        assert_eq!(i128, i128::MAX - 1);
1185    }
1186
1187    #[test]
1188    fn test_string_roundtrip() {
1189        let roundtrip_cases = [
1190            i256::ZERO,
1191            i256::ONE,
1192            i256::MINUS_ONE,
1193            i256::from_i128(123456789),
1194            i256::from_i128(-123456789),
1195            i256::from_i128(i128::MIN),
1196            i256::from_i128(i128::MAX),
1197            i256::MIN,
1198            i256::MAX,
1199        ];
1200        for case in roundtrip_cases {
1201            let formatted = case.to_string();
1202            let back: i256 = formatted.parse().unwrap();
1203            assert_eq!(case, back);
1204        }
1205    }
1206
1207    #[test]
1208    fn test_from_string() {
1209        let cases = [
1210            (
1211                "000000000000000000000000000000000000000011",
1212                Some(i256::from_i128(11)),
1213            ),
1214            (
1215                "-000000000000000000000000000000000000000011",
1216                Some(i256::from_i128(-11)),
1217            ),
1218            (
1219                "-0000000000000000000000000000000000000000123456789",
1220                Some(i256::from_i128(-123456789)),
1221            ),
1222            ("-", None),
1223            ("+", None),
1224            ("--1", None),
1225            ("-+1", None),
1226            ("000000000000000000000000000000000000000", Some(i256::ZERO)),
1227            ("0000000000000000000000000000000000000000-11", None),
1228            ("11-1111111111111111111111111111111111111", None),
1229            (
1230                "115792089237316195423570985008687907853269984665640564039457584007913129639936",
1231                None,
1232            ),
1233        ];
1234        for (case, expected) in cases {
1235            assert_eq!(i256::from_string(case), expected)
1236        }
1237    }
1238
1239    #[allow(clippy::op_ref)]
1240    fn test_reference_op(il: i256, ir: i256) {
1241        let r1 = il + ir;
1242        let r2 = &il + ir;
1243        let r3 = il + &ir;
1244        let r4 = &il + &ir;
1245        assert_eq!(r1, r2);
1246        assert_eq!(r1, r3);
1247        assert_eq!(r1, r4);
1248
1249        let r1 = il - ir;
1250        let r2 = &il - ir;
1251        let r3 = il - &ir;
1252        let r4 = &il - &ir;
1253        assert_eq!(r1, r2);
1254        assert_eq!(r1, r3);
1255        assert_eq!(r1, r4);
1256
1257        let r1 = il * ir;
1258        let r2 = &il * ir;
1259        let r3 = il * &ir;
1260        let r4 = &il * &ir;
1261        assert_eq!(r1, r2);
1262        assert_eq!(r1, r3);
1263        assert_eq!(r1, r4);
1264
1265        let r1 = il / ir;
1266        let r2 = &il / ir;
1267        let r3 = il / &ir;
1268        let r4 = &il / &ir;
1269        assert_eq!(r1, r2);
1270        assert_eq!(r1, r3);
1271        assert_eq!(r1, r4);
1272    }
1273
1274    #[test]
1275    fn test_i256_reference_op() {
1276        let candidates = [
1277            i256::ONE,
1278            i256::MINUS_ONE,
1279            i256::from_i128(2),
1280            i256::from_i128(-2),
1281            i256::from_i128(3),
1282            i256::from_i128(-3),
1283        ];
1284
1285        for il in candidates {
1286            for ir in candidates {
1287                test_reference_op(il, ir)
1288            }
1289        }
1290    }
1291
1292    #[test]
1293    fn test_decimal256_to_f64_typical_values() {
1294        let v = i256::from_i128(42_i128);
1295        assert_eq!(v.to_f64().unwrap(), 42.0);
1296
1297        let v = i256::from_i128(-123456789012345678i128);
1298        assert_eq!(v.to_f64().unwrap(), -123456789012345678.0);
1299
1300        let v = i256::from_string("0").unwrap();
1301        assert_eq!(v.to_f64().unwrap(), 0.0);
1302
1303        let v = i256::from_string("1").unwrap();
1304        assert_eq!(v.to_f64().unwrap(), 1.0);
1305
1306        let mut rng = rng();
1307        for _ in 0..10 {
1308            let f64_value =
1309                (rng.random_range(i128::MIN..i128::MAX) as f64) * rng.random_range(0.0..1.0);
1310            let big = i256::from_f64(f64_value).unwrap();
1311            assert_eq!(big.to_f64().unwrap(), f64_value);
1312        }
1313    }
1314
1315    #[test]
1316    fn test_decimal256_to_f64_large_positive_value() {
1317        let max_f = f64::MAX;
1318        let big = i256::from_f64(max_f * 2.0).unwrap_or(i256::MAX);
1319        let out = big.to_f64().unwrap();
1320        assert!(out.is_finite() && out.is_sign_positive());
1321    }
1322
1323    #[test]
1324    fn test_decimal256_to_f64_large_negative_value() {
1325        let max_f = f64::MAX;
1326        let big_neg = i256::from_f64(-(max_f * 2.0)).unwrap_or(i256::MIN);
1327        let out = big_neg.to_f64().unwrap();
1328        assert!(out.is_finite() && out.is_sign_negative());
1329    }
1330}
arrow_buffer/bigint/mod.rs

arrow_buffer/bigint/
mod.rs
