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

arrow_buffer/bigint/
mod.rs
