1use crate::arith::derive_arith;
6use crate::bigint::div::div_rem;
7use num_bigint::BigInt;
8use num_traits::{
9 Bounded, CheckedAdd, CheckedDiv, CheckedMul, CheckedNeg, CheckedRem, CheckedShl, CheckedShr,
10 CheckedSub, ConstOne, ConstZero, FromPrimitive, MulAdd, MulAddAssign, Num, One, SaturatingAdd,
11 SaturatingMul, SaturatingSub, Signed, ToPrimitive, WrappingAdd, WrappingMul, WrappingNeg,
12 WrappingShl, WrappingShr, WrappingSub, Zero, cast::AsPrimitive,
13};
14use std::cmp::Ordering;
15use std::num::ParseIntError;
16use std::ops::{BitAnd, BitOr, BitXor, Neg, Not, Shl, Shr};
17use std::str::FromStr;
18
19mod div;
20
21#[derive(Debug)]
23pub struct ParseI256Error {}
24
25impl From<ParseIntError> for ParseI256Error {
26 fn from(_: ParseIntError) -> Self {
27 Self {}
28 }
29}
30
31impl std::fmt::Display for ParseI256Error {
32 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
33 write!(f, "Failed to parse as i256")
34 }
35}
36impl std::error::Error for ParseI256Error {}
37
38enum DivRemError {
40 DivideByZero,
42 DivideOverflow,
44}
45
46#[derive(Copy, Clone, Default, Eq, PartialEq, Hash)]
48#[repr(C)]
49pub struct i256 {
50 low: u128,
51 high: i128,
52}
53
54impl std::fmt::Debug for i256 {
55 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
56 write!(f, "{self}")
57 }
58}
59
60impl std::fmt::Display for i256 {
61 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
62 if let Some(v) = Self::to_i128(*self) {
63 return write!(f, "{v}");
64 }
65
66 let chunk = Self::from_i128(10_i128.pow(38)).as_digits();
70 let (high, low) = div_rem(&self.wrapping_abs().as_digits(), &chunk);
71 let (top, mid) = div_rem(&high, &chunk);
72 let [top, mid, low] = [top, mid, low].map(|digits| Self::from_digits(digits).as_i128());
73
74 let sign = if self.is_negative() { "-" } else { "" };
75 if top != 0 {
76 write!(f, "{sign}{top}{mid:038}{low:038}")
77 } else {
78 write!(f, "{sign}{mid}{low:038}")
79 }
80 }
81}
82
83impl FromStr for i256 {
84 type Err = ParseI256Error;
85
86 fn from_str(s: &str) -> Result<Self, Self::Err> {
87 if s.len() <= 38 {
89 return Ok(Self::from_i128(i128::from_str(s)?));
90 }
91
92 let (negative, s) = match s.as_bytes()[0] {
93 b'-' => (true, &s[1..]),
94 b'+' => (false, &s[1..]),
95 _ => (false, s),
96 };
97
98 let s = s.trim_start_matches('0');
100 if s.is_empty() {
101 return Ok(i256::ZERO);
102 }
103
104 if !s.as_bytes()[0].is_ascii_digit() {
105 return Err(ParseI256Error {});
107 }
108
109 parse_impl(s, negative)
110 }
111}
112
113impl From<i8> for i256 {
114 fn from(value: i8) -> Self {
115 Self::from_i128(value.into())
116 }
117}
118
119impl From<i16> for i256 {
120 fn from(value: i16) -> Self {
121 Self::from_i128(value.into())
122 }
123}
124
125impl From<i32> for i256 {
126 fn from(value: i32) -> Self {
127 Self::from_i128(value.into())
128 }
129}
130
131impl From<i64> for i256 {
132 fn from(value: i64) -> Self {
133 Self::from_i128(value.into())
134 }
135}
136
137impl From<i128> for i256 {
138 fn from(value: i128) -> Self {
139 Self::from_i128(value)
140 }
141}
142
143fn parse_impl(s: &str, negative: bool) -> Result<i256, ParseI256Error> {
145 if s.len() <= 38 {
146 let low = i128::from_str(s)?;
147 return Ok(match negative {
148 true => i256::from_parts(low.neg() as _, -1),
149 false => i256::from_parts(low as _, 0),
150 });
151 }
152
153 let split = s.len() - 38;
154 if !s.as_bytes()[split].is_ascii_digit() {
155 return Err(ParseI256Error {});
157 }
158 let (hs, ls) = s.split_at(split);
159
160 let mut low = i128::from_str(ls)?;
161 let high = parse_impl(hs, negative)?;
162
163 if negative {
164 low = -low;
165 }
166
167 let low = i256::from_i128(low);
168
169 high.checked_mul(i256::from_i128(10_i128.pow(38)))
170 .and_then(|high| high.checked_add(low))
171 .ok_or(ParseI256Error {})
172}
173
174impl PartialOrd for i256 {
175 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
176 Some(self.cmp(other))
177 }
178}
179
180impl Ord for i256 {
181 fn cmp(&self, other: &Self) -> Ordering {
182 self.high.cmp(&other.high).then(self.low.cmp(&other.low))
185 }
186}
187
188impl i256 {
189 pub const ZERO: Self = i256 { low: 0, high: 0 };
191
192 pub const ONE: Self = i256 { low: 1, high: 0 };
194
195 pub const MINUS_ONE: Self = i256 {
197 low: u128::MAX,
198 high: -1,
199 };
200
201 pub const MAX: Self = i256 {
203 low: u128::MAX,
204 high: i128::MAX,
205 };
206
207 pub const MIN: Self = i256 {
209 low: u128::MIN,
210 high: i128::MIN,
211 };
212
213 #[inline]
215 pub const fn from_le_bytes(b: [u8; 32]) -> Self {
216 let (low, high) = split_array(b);
217 Self {
218 high: i128::from_le_bytes(high),
219 low: u128::from_le_bytes(low),
220 }
221 }
222
223 #[inline]
225 pub const fn from_be_bytes(b: [u8; 32]) -> Self {
226 let (high, low) = split_array(b);
227 Self {
228 high: i128::from_be_bytes(high),
229 low: u128::from_be_bytes(low),
230 }
231 }
232
233 pub const fn from_i128(v: i128) -> Self {
235 Self::from_parts(v as u128, v >> 127)
236 }
237
238 #[inline]
240 pub fn from_string(value_str: &str) -> Option<Self> {
241 value_str.parse().ok()
242 }
243
244 pub fn from_f64(v: f64) -> Option<Self> {
247 let (integer, overflow) = i256::from_bigint_with_overflow(BigInt::from_f64(v)?);
248 if overflow { None } else { Some(integer) }
249 }
250
251 #[inline]
253 pub const fn from_parts(low: u128, high: i128) -> Self {
254 Self { low, high }
255 }
256
257 pub const fn to_parts(self) -> (u128, i128) {
259 (self.low, self.high)
260 }
261
262 pub const fn to_i128(self) -> Option<i128> {
265 let as_i128 = self.low as i128;
266
267 let high_negative = self.high < 0;
268 let low_negative = as_i128 < 0;
269 let high_valid = self.high == -1 || self.high == 0;
270
271 if (high_negative == low_negative) && high_valid {
272 Some(self.low as i128)
273 } else {
274 None
275 }
276 }
277
278 pub const fn as_i128(self) -> i128 {
280 self.low as i128
281 }
282
283 #[inline]
285 pub const fn to_le_bytes(self) -> [u8; 32] {
286 let low = self.low.to_le_bytes();
287 let high = self.high.to_le_bytes();
288 let mut t = [0; 32];
289 let mut i = 0;
290 while i != 16 {
291 t[i] = low[i];
292 t[i + 16] = high[i];
293 i += 1;
294 }
295 t
296 }
297
298 #[inline]
300 pub const fn to_be_bytes(self) -> [u8; 32] {
301 let low = self.low.to_be_bytes();
302 let high = self.high.to_be_bytes();
303 let mut t = [0; 32];
304 let mut i = 0;
305 while i != 16 {
306 t[i] = high[i];
307 t[i + 16] = low[i];
308 i += 1;
309 }
310 t
311 }
312
313 fn from_bigint_with_overflow(v: BigInt) -> (Self, bool) {
316 let v_bytes = v.to_signed_bytes_le();
317 match v_bytes.len().cmp(&32) {
318 Ordering::Less => {
319 let mut bytes = if num_traits::Signed::is_negative(&v) {
320 [255_u8; 32]
321 } else {
322 [0; 32]
323 };
324 bytes[0..v_bytes.len()].copy_from_slice(&v_bytes[..v_bytes.len()]);
325 (Self::from_le_bytes(bytes), false)
326 }
327 Ordering::Equal => (Self::from_le_bytes(v_bytes.try_into().unwrap()), false),
328 Ordering::Greater => (Self::from_le_bytes(v_bytes[..32].try_into().unwrap()), true),
329 }
330 }
331
332 #[inline]
334 pub const fn wrapping_abs(self) -> Self {
335 let sa = self.high >> 127;
337 let sa = Self::from_parts(sa as u128, sa);
338
339 Self::from_parts(self.low ^ sa.low, self.high ^ sa.high).wrapping_sub(sa)
341 }
342
343 #[inline]
345 pub const fn checked_abs(self) -> Option<Self> {
346 if !self.is_eq(Self::MIN) {
347 Some(self.wrapping_abs())
348 } else {
349 None
350 }
351 }
352
353 #[inline]
355 pub const fn wrapping_neg(self) -> Self {
356 Self::from_parts(!self.low, !self.high).wrapping_add(i256::ONE)
357 }
358
359 #[inline]
361 pub const fn checked_neg(self) -> Option<Self> {
362 if !self.is_eq(Self::MIN) {
363 Some(self.wrapping_neg())
364 } else {
365 None
366 }
367 }
368
369 #[inline]
371 pub const fn wrapping_add(self, other: Self) -> Self {
372 let (low, carry) = self.low.overflowing_add(other.low);
373 let high = self.high.wrapping_add(other.high).wrapping_add(carry as _);
374 Self { low, high }
375 }
376
377 #[inline]
379 pub const fn checked_add(self, other: Self) -> Option<Self> {
380 let (r, overflow) = self.overflowing_add(other);
381
382 if overflow { None } else { Some(r) }
383 }
384
385 #[inline]
387 pub const fn wrapping_sub(self, other: Self) -> Self {
388 let (low, carry) = self.low.overflowing_sub(other.low);
389 let high = self.high.wrapping_sub(other.high).wrapping_sub(carry as _);
390 Self { low, high }
391 }
392
393 #[inline]
395 pub const fn checked_sub(self, other: Self) -> Option<Self> {
396 let (r, overflow) = self.overflowing_sub(other);
397
398 if overflow { None } else { Some(r) }
399 }
400
401 #[inline]
403 pub const fn wrapping_mul(self, other: Self) -> Self {
404 let (low, high) = mulx(self.low, other.low);
405
406 let hl = self.high.wrapping_mul(other.low as i128);
408 let lh = (self.low as i128).wrapping_mul(other.high);
409
410 Self {
411 low,
412 high: (high as i128).wrapping_add(hl).wrapping_add(lh),
413 }
414 }
415
416 const fn is_eq(&self, other: Self) -> bool {
418 (self.high == other.high) && (self.low == other.low)
419 }
420
421 #[inline]
423 pub const fn checked_mul(self, other: Self) -> Option<Self> {
424 if self.is_eq(Self::ZERO) || other.is_eq(Self::ZERO) {
425 return Some(i256::ZERO);
426 }
427
428 let l_sa = self.high >> 127;
430 let r_sa = other.high >> 127;
431 let out_sa = (l_sa ^ r_sa) as u128;
432
433 let l_abs = self.wrapping_abs();
435 let r_abs = other.wrapping_abs();
436
437 if l_abs.high != 0 && r_abs.high != 0 {
439 return None;
440 }
441
442 let (low, high) = mulx(l_abs.low, r_abs.low);
444
445 let Some(hl) = (l_abs.high as u128).checked_mul(r_abs.low) else {
447 return None;
448 };
449 let Some(lh) = l_abs.low.checked_mul(r_abs.high as u128) else {
450 return None;
451 };
452
453 let Some(high) = high.checked_add(hl) else {
454 return None;
455 };
456 let Some(high) = high.checked_add(lh) else {
457 return None;
458 };
459
460 let (low, c) = (low ^ out_sa).overflowing_sub(out_sa);
462 let high = (high ^ out_sa).wrapping_sub(out_sa).wrapping_sub(c as u128) as i128;
463
464 if high.is_negative() == (self.is_negative() ^ other.is_negative()) {
466 Some(Self { low, high })
467 } else {
468 None
469 }
470 }
471
472 #[inline]
475 fn div_rem(self, other: Self) -> Result<(Self, Self), DivRemError> {
476 if other == Self::ZERO {
477 return Err(DivRemError::DivideByZero);
478 }
479 if other == Self::MINUS_ONE && self == Self::MIN {
480 return Err(DivRemError::DivideOverflow);
481 }
482
483 let a = self.wrapping_abs();
484 let b = other.wrapping_abs();
485
486 let (div, rem) = if a.high == 0 && b.high == 0 {
487 (
489 Self::from_parts(a.low / b.low, 0),
490 Self::from_parts(a.low % b.low, 0),
491 )
492 } else {
493 let (div, rem) = div_rem(&a.as_digits(), &b.as_digits());
494 (Self::from_digits(div), Self::from_digits(rem))
495 };
496
497 Ok((
498 if self.is_negative() == other.is_negative() {
499 div
500 } else {
501 div.wrapping_neg()
502 },
503 if self.is_negative() {
504 rem.wrapping_neg()
505 } else {
506 rem
507 },
508 ))
509 }
510
511 fn as_digits(self) -> [u64; 4] {
513 [
514 self.low as u64,
515 (self.low >> 64) as u64,
516 self.high as u64,
517 (self.high as u128 >> 64) as u64,
518 ]
519 }
520
521 fn from_digits(digits: [u64; 4]) -> Self {
523 Self::from_parts(
524 digits[0] as u128 | ((digits[1] as u128) << 64),
525 digits[2] as i128 | ((digits[3] as i128) << 64),
526 )
527 }
528
529 #[inline]
537 pub fn wrapping_div(self, other: Self) -> Self {
538 self.wrapping_div_rem(other).0
539 }
540
541 #[inline]
543 pub fn checked_div(self, other: Self) -> Option<Self> {
544 self.div_rem(other).map(|(v, _)| v).ok()
545 }
546
547 #[inline]
555 pub fn wrapping_rem(self, other: Self) -> Self {
556 self.wrapping_div_rem(other).1
557 }
558
559 #[inline]
561 pub fn checked_rem(self, other: Self) -> Option<Self> {
562 self.div_rem(other).map(|(_, v)| v).ok()
563 }
564
565 #[inline]
587 pub fn wrapping_div_rem(self, other: Self) -> (Self, Self) {
588 match self.div_rem(other) {
589 Ok(v) => v,
590 Err(DivRemError::DivideByZero) => panic!("attempt to divide by zero"),
591 Err(DivRemError::DivideOverflow) => (Self::MIN, Self::ZERO),
592 }
593 }
594
595 #[inline]
616 pub fn checked_div_rem(self, other: Self) -> Option<(Self, Self)> {
617 self.div_rem(other).ok()
618 }
619
620 #[inline]
622 pub const fn checked_pow(self, mut exp: u32) -> Option<Self> {
623 if exp == 0 {
624 return Some(i256::from_i128(1));
625 }
626
627 let mut base = self;
628 let mut acc: Self = i256::from_i128(1);
629
630 while exp > 1 {
631 if (exp & 1) == 1 {
632 let Some(next) = acc.checked_mul(base) else {
633 return None;
634 };
635 acc = next;
636 }
637 exp /= 2;
638 let Some(next) = base.checked_mul(base) else {
639 return None;
640 };
641 base = next;
642 }
643 acc.checked_mul(base)
648 }
649
650 #[inline]
652 pub const fn wrapping_pow(self, mut exp: u32) -> Self {
653 if exp == 0 {
654 return i256::from_i128(1);
655 }
656
657 let mut base = self;
658 let mut acc: Self = i256::from_i128(1);
659
660 while exp > 1 {
661 if (exp & 1) == 1 {
662 acc = acc.wrapping_mul(base);
663 }
664 exp /= 2;
665 base = base.wrapping_mul(base);
666 }
667
668 acc.wrapping_mul(base)
673 }
674
675 pub const fn signum(self) -> Self {
681 if self.is_positive() {
682 i256::ONE
683 } else if self.is_negative() {
684 i256::MINUS_ONE
685 } else {
686 i256::ZERO
687 }
688 }
689
690 #[inline]
692 pub const fn is_negative(self) -> bool {
693 self.high.is_negative()
694 }
695
696 pub const fn is_positive(self) -> bool {
698 self.high.is_positive() || self.high == 0 && self.low != 0
699 }
700
701 pub const fn leading_zeros(&self) -> u32 {
703 match self.high {
704 0 => u128::BITS + self.low.leading_zeros(),
705 _ => self.high.leading_zeros(),
706 }
707 }
708
709 pub const fn trailing_zeros(&self) -> u32 {
711 match self.low {
712 0 => u128::BITS + self.high.trailing_zeros(),
713 _ => self.low.trailing_zeros(),
714 }
715 }
716
717 fn redundant_leading_sign_bits_i256(n: i256) -> u8 {
718 let mask = n >> 255; ((n ^ mask).leading_zeros() - 1) as u8 }
721
722 fn i256_to_f64(input: i256) -> f64 {
723 let k = i256::redundant_leading_sign_bits_i256(input);
724 let n = input << k; let sticky = n.low != 0 || (n.high as u64) != 0;
728 let n = ((n.high >> 64) as i64) | i64::from(sticky);
729 (n as f64) * f64::powi(2.0, 192 - (k as i32)) }
731
732 #[inline]
735 pub fn checked_ilog(self, base: i256) -> Option<u32> {
736 if base == Self::from(10) {
737 return self.checked_ilog10();
739 }
740
741 if self <= Self::ZERO {
742 return None;
743 }
744 if base <= Self::ONE {
745 return None;
746 }
747 if self < base {
748 return Some(0);
749 }
750
751 let mut val = 1;
752 let mut base_exp = base;
753
754 let boundary = self.checked_div(base)?;
755 while base_exp <= boundary {
756 val += 1;
757 base_exp = base_exp.checked_mul(base)?;
758 }
759 Some(val)
760 }
761
762 #[inline]
768 pub fn ilog(self, base: i256) -> u32 {
769 self.checked_ilog(base)
770 .unwrap_or_else(|| panic!("ilog overflow with {self} and base {base}"))
771 }
772
773 #[inline]
776 pub fn checked_ilog10(self) -> Option<u32> {
777 if self <= Self::ZERO {
778 return None;
779 }
780 if self < Self::from(10) {
781 return Some(0);
782 }
783
784 const POW10_32: i256 = i256::from_i128(100_000_000_000_000_000_000_000_000_000_000);
786
787 const POW10_64: i256 = i256::from_parts(
789 146_510_663_073_550_942_663_504_491_129_887_260_672,
790 29_387_358_770_557_187_699_218_413,
791 );
792
793 if self >= POW10_64 {
796 let value = self.checked_div(POW10_64)?;
797 debug_assert_eq!(value.high, 0);
801 Some(64 + value.low.checked_ilog10()?)
802 } else if self >= POW10_32 {
803 let value = self.checked_div(POW10_32)?;
804 debug_assert_eq!(value.high, 0);
808 Some(32 + value.low.checked_ilog10()?)
809 } else {
810 self.low.checked_ilog10()
812 }
813 }
814
815 #[inline]
821 pub fn ilog10(self) -> u32 {
822 self.checked_ilog10()
823 .unwrap_or_else(|| panic!("ilog10 overflow with {self}"))
824 }
825
826 #[inline]
829 pub fn checked_ilog2(self) -> Option<u32> {
830 self.checked_ilog(i256::from(2))
831 }
832
833 #[inline]
839 pub fn ilog2(self) -> u32 {
840 self.checked_ilog2()
841 .unwrap_or_else(|| panic!("ilog2 overflow with {self}"))
842 }
843
844 #[inline]
849 pub const fn overflowing_add(self, rhs: Self) -> (Self, bool) {
850 let (low, carry) = self.low.overflowing_add(rhs.low);
852
853 let high = (self.high as u128)
855 .wrapping_add(rhs.high as u128)
856 .wrapping_add(carry as u128) as i128;
857
858 let result = Self { low, high };
859
860 let overflow = (self.high < 0) == (rhs.high < 0) && (high < 0) != (self.high < 0);
864
865 (result, overflow)
866 }
867
868 #[inline]
873 pub const fn overflowing_sub(self, rhs: Self) -> (Self, bool) {
874 let (low, borrow) = self.low.overflowing_sub(rhs.low);
876
877 let high = (self.high as u128)
879 .wrapping_sub(rhs.high as u128)
880 .wrapping_sub(borrow as u128) as i128;
881
882 let result = Self { low, high };
883
884 let overflow = (self.high < 0) != (rhs.high < 0) && (high < 0) != (self.high < 0);
888
889 (result, overflow)
890 }
891}
892
893const fn split_array<const N: usize, const M: usize>(vals: [u8; N]) -> ([u8; M], [u8; M]) {
896 let mut a = [0; M];
897 let mut b = [0; M];
898 let mut i = 0;
899 while i != M {
900 a[i] = vals[i];
901 b[i] = vals[i + M];
902 i += 1;
903 }
904 (a, b)
905}
906
907#[inline]
913const fn mulx(a: u128, b: u128) -> (u128, u128) {
914 const fn split(a: u128) -> (u128, u128) {
915 (a & (u64::MAX as u128), a >> 64)
916 }
917
918 const MASK: u128 = u64::MAX as _;
919
920 let (a_low, a_high) = split(a);
921 let (b_low, b_high) = split(b);
922
923 let (mut low, mut carry) = split(a_low * b_low);
925 carry += a_high * b_low;
926
927 low += carry << 64;
929 let mut high = carry >> 64;
930
931 carry = low >> 64;
933 low &= MASK;
934
935 carry += b_high * a_low;
937
938 low += carry << 64;
940 high += carry >> 64;
941
942 high += a_high * b_high;
944
945 (low, high)
946}
947
948derive_arith!(
949 i256,
950 Add,
951 AddAssign,
952 add,
953 add_assign,
954 wrapping_add,
955 checked_add
956);
957derive_arith!(
958 i256,
959 Sub,
960 SubAssign,
961 sub,
962 sub_assign,
963 wrapping_sub,
964 checked_sub
965);
966derive_arith!(
967 i256,
968 Mul,
969 MulAssign,
970 mul,
971 mul_assign,
972 wrapping_mul,
973 checked_mul
974);
975derive_arith!(
976 i256,
977 Div,
978 DivAssign,
979 div,
980 div_assign,
981 wrapping_div,
982 checked_div
983);
984derive_arith!(
985 i256,
986 Rem,
987 RemAssign,
988 rem,
989 rem_assign,
990 wrapping_rem,
991 checked_rem
992);
993
994impl Neg for i256 {
995 type Output = i256;
996
997 #[cfg(debug_assertions)]
998 fn neg(self) -> Self::Output {
999 self.checked_neg().expect("i256 overflow")
1000 }
1001
1002 #[cfg(not(debug_assertions))]
1003 fn neg(self) -> Self::Output {
1004 self.wrapping_neg()
1005 }
1006}
1007
1008impl BitAnd for i256 {
1009 type Output = i256;
1010
1011 #[inline]
1012 fn bitand(self, rhs: Self) -> Self::Output {
1013 Self {
1014 low: self.low & rhs.low,
1015 high: self.high & rhs.high,
1016 }
1017 }
1018}
1019
1020impl BitOr for i256 {
1021 type Output = i256;
1022
1023 #[inline]
1024 fn bitor(self, rhs: Self) -> Self::Output {
1025 Self {
1026 low: self.low | rhs.low,
1027 high: self.high | rhs.high,
1028 }
1029 }
1030}
1031
1032impl BitXor for i256 {
1033 type Output = i256;
1034
1035 #[inline]
1036 fn bitxor(self, rhs: Self) -> Self::Output {
1037 Self {
1038 low: self.low ^ rhs.low,
1039 high: self.high ^ rhs.high,
1040 }
1041 }
1042}
1043
1044impl Shl<u8> for i256 {
1045 type Output = i256;
1046
1047 #[inline]
1048 fn shl(self, rhs: u8) -> Self::Output {
1049 if rhs == 0 {
1050 self
1051 } else if rhs < 128 {
1052 Self {
1053 high: (self.high << rhs) | (self.low >> (128 - rhs)) as i128,
1054 low: self.low << rhs,
1055 }
1056 } else {
1057 Self {
1058 high: (self.low << (rhs - 128)) as i128,
1059 low: 0,
1060 }
1061 }
1062 }
1063}
1064
1065impl Shr<u8> for i256 {
1066 type Output = i256;
1067
1068 #[inline]
1069 fn shr(self, rhs: u8) -> Self::Output {
1070 if rhs == 0 {
1071 self
1072 } else if rhs < 128 {
1073 Self {
1074 high: self.high >> rhs,
1075 low: (self.low >> rhs) | ((self.high as u128) << (128 - rhs)),
1076 }
1077 } else {
1078 Self {
1079 high: self.high >> 127,
1080 low: (self.high >> (rhs - 128)) as u128,
1081 }
1082 }
1083 }
1084}
1085
1086impl WrappingShl for i256 {
1087 #[inline]
1088 fn wrapping_shl(&self, rhs: u32) -> i256 {
1089 (*self).shl(rhs as u8)
1091 }
1092}
1093
1094impl WrappingShr for i256 {
1095 #[inline]
1096 fn wrapping_shr(&self, rhs: u32) -> i256 {
1097 (*self).shr(rhs as u8)
1099 }
1100}
1101
1102macro_rules! define_standard_shift {
1105 ($trait_name:ident, $method:ident, [$($t:ty),+]) => {
1107 $(define_standard_shift!($trait_name, $method, $t);)+
1108 };
1109 ($trait_name:ident, $method:ident, $t:ty) => {
1111 impl $trait_name<$t> for i256 {
1112 type Output = i256;
1113
1114 #[inline]
1115 fn $method(self, rhs: $t) -> Self::Output {
1116 let rhs = u8::try_from(rhs).expect("rhs overflow for shift");
1117 self.$method(rhs)
1119 }
1120 }
1121 };
1122}
1123
1124define_standard_shift!(
1125 Shl,
1126 shl,
1127 [u16, u32, u64, u128, usize, i16, i32, i64, i128, isize]
1128);
1129define_standard_shift!(
1130 Shr,
1131 shr,
1132 [u16, u32, u64, u128, usize, i16, i32, i64, i128, isize]
1133);
1134
1135macro_rules! define_as_primitive {
1136 ($native_ty:ty) => {
1137 impl AsPrimitive<i256> for $native_ty {
1138 fn as_(self) -> i256 {
1139 i256::from_i128(self as i128)
1140 }
1141 }
1142 };
1143}
1144
1145define_as_primitive!(i8);
1146define_as_primitive!(i16);
1147define_as_primitive!(i32);
1148define_as_primitive!(i64);
1149define_as_primitive!(u8);
1150define_as_primitive!(u16);
1151define_as_primitive!(u32);
1152define_as_primitive!(u64);
1153
1154impl ToPrimitive for i256 {
1155 fn to_i64(&self) -> Option<i64> {
1156 i64::try_from(i256::to_i128(*self)?).ok()
1157 }
1158
1159 fn to_f64(&self) -> Option<f64> {
1160 match *self {
1161 Self::MIN => Some(-2_f64.powi(255)),
1162 Self::ZERO => Some(0f64),
1163 Self::ONE => Some(1f64),
1164 n => Some(Self::i256_to_f64(n)),
1165 }
1166 }
1167
1168 fn to_u64(&self) -> Option<u64> {
1169 u64::try_from(i256::to_i128(*self)?).ok()
1170 }
1171}
1172
1173impl CheckedNeg for i256 {
1176 fn checked_neg(&self) -> Option<Self> {
1177 (*self).checked_neg()
1178 }
1179}
1180
1181impl CheckedAdd for i256 {
1182 fn checked_add(&self, v: &i256) -> Option<Self> {
1183 (*self).checked_add(*v)
1184 }
1185}
1186
1187impl CheckedSub for i256 {
1188 fn checked_sub(&self, v: &i256) -> Option<Self> {
1189 (*self).checked_sub(*v)
1190 }
1191}
1192
1193impl CheckedDiv for i256 {
1194 fn checked_div(&self, v: &i256) -> Option<Self> {
1195 (*self).checked_div(*v)
1196 }
1197}
1198
1199impl CheckedMul for i256 {
1200 #[inline]
1201 fn checked_mul(&self, v: &i256) -> Option<Self> {
1202 (*self).checked_mul(*v)
1203 }
1204}
1205
1206impl CheckedRem for i256 {
1207 fn checked_rem(&self, v: &i256) -> Option<Self> {
1208 (*self).checked_rem(*v)
1209 }
1210}
1211
1212impl CheckedShl for i256 {
1213 fn checked_shl(&self, rhs: u32) -> Option<Self> {
1214 let rhs = u8::try_from(rhs).ok()?;
1215 Some(self.shl(rhs))
1216 }
1217}
1218
1219impl CheckedShr for i256 {
1220 fn checked_shr(&self, rhs: u32) -> Option<Self> {
1221 let rhs = u8::try_from(rhs).ok()?;
1222 Some(self.shr(rhs))
1223 }
1224}
1225
1226impl WrappingAdd for i256 {
1229 fn wrapping_add(&self, v: &Self) -> Self {
1230 (*self).wrapping_add(*v)
1231 }
1232}
1233
1234impl WrappingSub for i256 {
1235 fn wrapping_sub(&self, v: &Self) -> Self {
1236 (*self).wrapping_sub(*v)
1237 }
1238}
1239
1240impl WrappingMul for i256 {
1241 fn wrapping_mul(&self, v: &Self) -> Self {
1242 (*self).wrapping_mul(*v)
1243 }
1244}
1245
1246impl WrappingNeg for i256 {
1247 fn wrapping_neg(&self) -> Self {
1248 (*self).wrapping_neg()
1249 }
1250}
1251
1252impl SaturatingAdd for i256 {
1255 fn saturating_add(&self, v: &Self) -> Self {
1256 self.checked_add(v).unwrap_or_else(|| {
1257 if v.is_negative() {
1258 i256::MIN
1259 } else {
1260 i256::MAX
1261 }
1262 })
1263 }
1264}
1265
1266impl SaturatingSub for i256 {
1267 fn saturating_sub(&self, v: &Self) -> Self {
1268 self.checked_sub(v).unwrap_or_else(|| {
1269 if v.is_negative() {
1270 i256::MAX
1271 } else {
1272 i256::MIN
1273 }
1274 })
1275 }
1276}
1277
1278impl SaturatingMul for i256 {
1279 fn saturating_mul(&self, v: &Self) -> Self {
1280 self.checked_mul(v).unwrap_or_else(|| {
1281 if v.is_negative() == self.is_negative() {
1282 i256::MAX
1283 } else {
1284 i256::MIN
1285 }
1286 })
1287 }
1288}
1289
1290impl MulAdd for i256 {
1291 type Output = i256;
1292
1293 fn mul_add(self, a: Self, b: Self) -> Self::Output {
1294 (self * a) + b
1295 }
1296}
1297
1298impl MulAddAssign for i256 {
1299 fn mul_add_assign(&mut self, a: Self, b: Self) {
1300 *self = self.mul_add(a, b)
1301 }
1302}
1303
1304impl Zero for i256 {
1305 fn zero() -> Self {
1306 i256::ZERO
1307 }
1308
1309 fn is_zero(&self) -> bool {
1310 *self == i256::ZERO
1311 }
1312}
1313
1314impl ConstZero for i256 {
1315 const ZERO: Self = i256::ZERO;
1316}
1317
1318impl One for i256 {
1319 fn one() -> Self {
1320 i256::ONE
1321 }
1322
1323 fn is_one(&self) -> bool {
1324 *self == i256::ONE
1325 }
1326}
1327
1328impl ConstOne for i256 {
1329 const ONE: Self = i256::ONE;
1330}
1331
1332impl Num for i256 {
1333 type FromStrRadixErr = ParseI256Error;
1334
1335 fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
1336 if radix == 10 {
1337 str.parse()
1338 } else {
1339 Err(ParseI256Error {})
1341 }
1342 }
1343}
1344
1345impl Signed for i256 {
1346 fn abs(&self) -> Self {
1347 self.wrapping_abs()
1348 }
1349
1350 fn abs_sub(&self, other: &Self) -> Self {
1351 if self > other {
1352 self.wrapping_sub(other)
1353 } else {
1354 i256::ZERO
1355 }
1356 }
1357
1358 fn signum(&self) -> Self {
1359 (*self).signum()
1360 }
1361
1362 fn is_positive(&self) -> bool {
1363 (*self).is_positive()
1364 }
1365
1366 fn is_negative(&self) -> bool {
1367 (*self).is_negative()
1368 }
1369}
1370
1371impl Bounded for i256 {
1372 fn min_value() -> Self {
1373 i256::MIN
1374 }
1375
1376 fn max_value() -> Self {
1377 i256::MAX
1378 }
1379}
1380
1381impl Not for i256 {
1382 type Output = i256;
1383
1384 #[inline]
1385 fn not(self) -> Self::Output {
1386 Self::from_parts(!self.low, !self.high)
1387 }
1388}
1389
1390#[cfg(test)]
1391mod tests {
1392 use super::*;
1393 use num_traits::Signed;
1394 use rand::{RngExt, SeedableRng, rng, rngs::StdRng};
1395
1396 #[test]
1397 fn test_signed_cmp() {
1398 let a = i256::from_parts(i128::MAX as u128, 12);
1399 let b = i256::from_parts(i128::MIN as u128, 12);
1400 assert!(a < b);
1401
1402 let a = i256::from_parts(i128::MAX as u128, 12);
1403 let b = i256::from_parts(i128::MIN as u128, -12);
1404 assert!(a > b);
1405 }
1406
1407 #[test]
1408 fn test_to_i128() {
1409 let vals = [
1410 BigInt::from_i128(-1).unwrap(),
1411 BigInt::from_i128(i128::MAX).unwrap(),
1412 BigInt::from_i128(i128::MIN).unwrap(),
1413 BigInt::from_u128(u128::MIN).unwrap(),
1414 BigInt::from_u128(u128::MAX).unwrap(),
1415 ];
1416
1417 for v in vals {
1418 let (t, overflow) = i256::from_bigint_with_overflow(v.clone());
1419 assert!(!overflow);
1420 assert_eq!(t.to_i128(), v.to_i128(), "{v} vs {t}");
1421 }
1422 }
1423
1424 fn test_ops(il: i256, ir: i256) {
1426 let bl = BigInt::from_signed_bytes_le(&il.to_le_bytes());
1427 let br = BigInt::from_signed_bytes_le(&ir.to_le_bytes());
1428
1429 assert_eq!(il.cmp(&ir), bl.cmp(&br), "{bl} cmp {br}");
1431
1432 assert_eq!(i256::from_le_bytes(il.to_le_bytes()), il);
1434 assert_eq!(i256::from_be_bytes(il.to_be_bytes()), il);
1435 assert_eq!(i256::from_le_bytes(ir.to_le_bytes()), ir);
1436 assert_eq!(i256::from_be_bytes(ir.to_be_bytes()), ir);
1437
1438 assert_eq!(il.to_i128(), bl.to_i128(), "{bl}");
1440 assert_eq!(ir.to_i128(), br.to_i128(), "{br}");
1441
1442 let (abs, overflow) = i256::from_bigint_with_overflow(bl.abs());
1444 assert_eq!(il.wrapping_abs(), abs);
1445 assert_eq!(il.checked_abs().is_none(), overflow);
1446
1447 let (abs, overflow) = i256::from_bigint_with_overflow(br.abs());
1448 assert_eq!(ir.wrapping_abs(), abs);
1449 assert_eq!(ir.checked_abs().is_none(), overflow);
1450
1451 let (neg, overflow) = i256::from_bigint_with_overflow(bl.clone().neg());
1453 assert_eq!(il.wrapping_neg(), neg);
1454 assert_eq!(il.checked_neg().is_none(), overflow);
1455
1456 let (neg, overflow) = i256::from_bigint_with_overflow(br.clone().neg());
1458 assert_eq!(ir.wrapping_neg(), neg);
1459 assert_eq!(ir.checked_neg().is_none(), overflow);
1460
1461 let actual = il.wrapping_add(ir);
1463 let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() + br.clone());
1464 assert_eq!(actual, expected);
1465 assert_eq!(il.overflowing_add(ir), (expected, overflow));
1466
1467 let checked = il.checked_add(ir);
1468 match overflow {
1469 true => assert!(checked.is_none()),
1470 false => assert_eq!(checked, Some(actual)),
1471 }
1472
1473 let actual = il.wrapping_sub(ir);
1475 let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() - br.clone());
1476 assert_eq!(actual.to_string(), expected.to_string());
1477 assert_eq!(il.overflowing_sub(ir), (expected, overflow));
1478
1479 let checked = il.checked_sub(ir);
1480 match overflow {
1481 true => assert!(checked.is_none()),
1482 false => assert_eq!(checked, Some(actual), "{bl} - {br} = {expected}"),
1483 }
1484
1485 let actual = il.wrapping_mul(ir);
1487 let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone() * br.clone());
1488 assert_eq!(actual.to_string(), expected.to_string());
1489
1490 let checked = il.checked_mul(ir);
1491 match overflow {
1492 true => assert!(
1493 checked.is_none(),
1494 "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
1495 ),
1496 false => assert_eq!(
1497 checked,
1498 Some(actual),
1499 "{il} * {ir} = {actual} vs {bl} * {br} = {expected}"
1500 ),
1501 }
1502
1503 test_div_rem(il, ir);
1505
1506 for exp in [0, 1, 2, 3, 8, 100] {
1508 let actual = il.wrapping_pow(exp);
1509 let (expected, overflow) = i256::from_bigint_with_overflow(bl.clone().pow(exp));
1510 assert_eq!(actual.to_string(), expected.to_string());
1511
1512 let checked = il.checked_pow(exp);
1513 match overflow {
1514 true => assert!(
1515 checked.is_none(),
1516 "{il} ^ {exp} = {actual} vs {bl} * {exp} = {expected}"
1517 ),
1518 false => assert_eq!(
1519 checked,
1520 Some(actual),
1521 "{il} ^ {exp} = {actual} vs {bl} ^ {exp} = {expected}"
1522 ),
1523 }
1524 }
1525
1526 let actual = il & ir;
1528 let (expected, _) = i256::from_bigint_with_overflow(bl.clone() & br.clone());
1529 assert_eq!(actual.to_string(), expected.to_string());
1530
1531 let actual = il | ir;
1532 let (expected, _) = i256::from_bigint_with_overflow(bl.clone() | br.clone());
1533 assert_eq!(actual.to_string(), expected.to_string());
1534
1535 let actual = il ^ ir;
1536 let (expected, _) = i256::from_bigint_with_overflow(bl.clone() ^ br);
1537 assert_eq!(actual.to_string(), expected.to_string());
1538
1539 for shift in [0_u8, 1, 4, 126, 128, 129, 254, 255] {
1540 let actual = il << shift;
1541 let (expected, _) = i256::from_bigint_with_overflow(bl.clone() << shift);
1542 assert_eq!(actual.to_string(), expected.to_string());
1543
1544 let wrapping_actual = <i256 as WrappingShl>::wrapping_shl(&il, shift as u32);
1545 assert_eq!(wrapping_actual.to_string(), expected.to_string());
1546
1547 let actual = il >> shift;
1548 let (expected, _) = i256::from_bigint_with_overflow(bl.clone() >> shift);
1549 assert_eq!(actual.to_string(), expected.to_string());
1550
1551 let wrapping_actual = <i256 as WrappingShr>::wrapping_shr(&il, shift as u32);
1552 assert_eq!(wrapping_actual.to_string(), expected.to_string());
1553
1554 let wrapping_actual = <i256 as WrappingShr>::wrapping_shr(&il, 512 + shift as u32);
1556 assert_eq!(wrapping_actual.to_string(), expected.to_string());
1557 }
1558 }
1559
1560 #[test]
1561 fn test_overflowing_add() {
1562 const POSITIVE_OVERFLOW: (i256, bool) = i256::MAX.overflowing_add(i256::ONE);
1563 const NEGATIVE_OVERFLOW: (i256, bool) = i256::MIN.overflowing_add(i256::MINUS_ONE);
1564
1565 assert_eq!(POSITIVE_OVERFLOW, (i256::MIN, true));
1566 assert_eq!(NEGATIVE_OVERFLOW, (i256::MAX, true));
1567 assert_eq!(
1568 i256::from_parts(u128::MAX, 0).overflowing_add(i256::ONE),
1569 (i256::from_parts(0, 1), false)
1570 );
1571 assert_eq!(
1572 i256::ONE.overflowing_add(i256::from_i128(2)),
1573 (i256::from_i128(3), false)
1574 );
1575 }
1576
1577 #[test]
1578 fn test_overflowing_sub() {
1579 const NEGATIVE_OVERFLOW: (i256, bool) = i256::MIN.overflowing_sub(i256::ONE);
1580 const POSITIVE_OVERFLOW: (i256, bool) = i256::MAX.overflowing_sub(i256::MINUS_ONE);
1581
1582 assert_eq!(NEGATIVE_OVERFLOW, (i256::MAX, true));
1583 assert_eq!(POSITIVE_OVERFLOW, (i256::MIN, true));
1584 assert_eq!(
1585 i256::from_parts(0, 1).overflowing_sub(i256::ONE),
1586 (i256::from_parts(u128::MAX, 0), false)
1587 );
1588 assert_eq!(
1589 i256::from_i128(3).overflowing_sub(i256::from_i128(2)),
1590 (i256::ONE, false)
1591 );
1592 }
1593
1594 #[test]
1595 #[cfg_attr(miri, ignore)] fn test_i256() {
1597 let candidates = [
1598 i256::ZERO,
1599 i256::ONE,
1600 i256::MINUS_ONE,
1601 ConstZero::ZERO,
1602 ConstOne::ONE,
1603 i256::from_i128(2),
1604 i256::from_i128(-2),
1605 i256::from_parts(u128::MAX, 1),
1606 i256::from_parts(u128::MAX, -1),
1607 i256::from_parts(0, 1),
1608 i256::from_parts(0, -1),
1609 i256::from_parts(1, -1),
1610 i256::from_parts(1, 1),
1611 i256::from_parts(0, i128::MAX),
1612 i256::from_parts(0, i128::MIN),
1613 i256::from_parts(1, i128::MAX),
1614 i256::from_parts(1, i128::MIN),
1615 i256::from_parts(u128::MAX, i128::MIN),
1616 i256::from_parts(100, 32),
1617 i256::MIN,
1618 i256::MAX,
1619 i256::MIN >> 1,
1620 i256::MAX >> 1,
1621 i256::ONE << 127,
1622 i256::ONE << 128,
1623 i256::ONE << 129,
1624 i256::MINUS_ONE << 127,
1625 i256::MINUS_ONE << 128,
1626 i256::MINUS_ONE << 129,
1627 ];
1628
1629 for il in candidates {
1630 for ir in candidates {
1631 test_ops(il, ir)
1632 }
1633 }
1634 }
1635
1636 fn test_div_rem(n: i256, d: i256) {
1637 if d == i256::ZERO {
1638 assert_eq!(n.checked_div(d), None);
1640 assert_eq!(n.checked_rem(d), None);
1641 assert_eq!(n.checked_div_rem(d), None);
1642 return;
1643 }
1644
1645 let bn = BigInt::from_signed_bytes_le(&n.to_le_bytes());
1646 let bd = BigInt::from_signed_bytes_le(&d.to_le_bytes());
1647
1648 let (q, overflow) = i256::from_bigint_with_overflow(bn.clone() / bd.clone());
1650 let (r, _) = i256::from_bigint_with_overflow(bn % bd);
1651
1652 assert_eq!(n.wrapping_div(d), q, "{n} / {d}");
1653 assert_eq!(n.wrapping_rem(d), r, "{n} % {d}");
1654 assert_eq!(n.wrapping_div_rem(d), (q, r), "{n} / {d}");
1655 assert_eq!(n.checked_div(d), (!overflow).then_some(q), "{n} / {d}");
1656 assert_eq!(n.checked_rem(d), (!overflow).then_some(r), "{n} % {d}");
1657 assert_eq!(
1658 n.checked_div_rem(d),
1659 (!overflow).then_some((q, r)),
1660 "{n} / {d}"
1661 );
1662 }
1663
1664 #[test]
1665 #[cfg_attr(miri, ignore)] fn test_div_rem_powers_of_ten() {
1667 let dividends = [
1668 i256::ZERO,
1669 i256::ONE,
1670 i256::MIN,
1671 i256::MAX,
1672 i256::from_i128(i128::MIN),
1673 i256::from_i128(i128::MAX),
1674 i256::from_i128(u64::MAX as i128),
1675 i256::from_i128(1 << 64),
1676 i256::from_i128((1 << 64) + 1),
1677 i256::from_parts(u128::MAX, 0),
1678 i256::from_parts(0, 1),
1679 i256::from_parts(1, 1),
1680 ];
1681
1682 for k in 0..=76 {
1684 let p = i256::from_i128(10).wrapping_pow(k);
1685 for d in [p - i256::ONE, p, p + i256::ONE] {
1686 for n in dividends
1687 .into_iter()
1688 .chain([p - i256::ONE, p, p + i256::ONE])
1689 {
1690 for (n, d) in [
1691 (n, d),
1692 (n.wrapping_neg(), d),
1693 (n, -d),
1694 (n.wrapping_neg(), -d),
1695 ] {
1696 test_div_rem(n, d);
1697 }
1698 }
1699 }
1700 }
1701 }
1702
1703 #[test]
1704 #[should_panic(expected = "attempt to divide by zero")]
1705 fn test_wrapping_div_rem_zero_panics() {
1706 let _ = i256::ONE.wrapping_div_rem(i256::ZERO);
1707 }
1708
1709 #[test]
1710 fn test_signed_ops() {
1711 assert_eq!(i256::from_i128(1).signum(), i256::ONE);
1713 assert_eq!(i256::from_i128(0).signum(), i256::ZERO);
1714 assert_eq!(i256::from_i128(-0).signum(), i256::ZERO);
1715 assert_eq!(i256::from_i128(-1).signum(), i256::MINUS_ONE);
1716
1717 assert!(i256::from_i128(1).is_positive());
1719 assert!(!i256::from_i128(0).is_positive());
1720 assert!(!i256::from_i128(-0).is_positive());
1721 assert!(!i256::from_i128(-1).is_positive());
1722
1723 assert!(!i256::from_i128(1).is_negative());
1725 assert!(!i256::from_i128(0).is_negative());
1726 assert!(!i256::from_i128(-0).is_negative());
1727 assert!(i256::from_i128(-1).is_negative());
1728 }
1729
1730 #[test]
1731 #[cfg_attr(miri, ignore)] fn test_i256_fuzz() {
1733 let mut rng = rng();
1734
1735 for _ in 0..1000 {
1736 let mut l = [0_u8; 32];
1737 let len = rng.random_range(0..=32);
1738 l.iter_mut().take(len).for_each(|x| *x = rng.random());
1739
1740 let mut r = [0_u8; 32];
1741 let len = rng.random_range(0..=32);
1742 r.iter_mut().take(len).for_each(|x| *x = rng.random());
1743
1744 let l = i256::from_le_bytes(l);
1746 let r = i256::from_le_bytes(r);
1747 let l = if rng.random() { l.wrapping_neg() } else { l };
1748 let r = if rng.random() { r.wrapping_neg() } else { r };
1749
1750 test_ops(l, r)
1751 }
1752 }
1753
1754 #[test]
1755 fn test_i256_to_primitive() {
1756 let a = i256::MAX;
1757 assert!(a.to_i64().is_none());
1758 assert!(a.to_u64().is_none());
1759
1760 let a = i256::from_i128(i128::MAX);
1761 assert!(a.to_i64().is_none());
1762 assert!(a.to_u64().is_none());
1763
1764 let a = i256::from_i128(i64::MAX as i128);
1765 assert_eq!(a.to_i64().unwrap(), i64::MAX);
1766 assert_eq!(a.to_u64().unwrap(), i64::MAX as u64);
1767
1768 let a = i256::from_i128(i64::MAX as i128 + 1);
1769 assert!(a.to_i64().is_none());
1770 assert_eq!(a.to_u64().unwrap(), i64::MAX as u64 + 1);
1771
1772 let a = i256::MIN;
1773 assert!(a.to_i64().is_none());
1774 assert!(a.to_u64().is_none());
1775
1776 let a = i256::from_i128(i128::MIN);
1777 assert!(a.to_i64().is_none());
1778 assert!(a.to_u64().is_none());
1779
1780 let a = i256::from_i128(i64::MIN as i128);
1781 assert_eq!(a.to_i64().unwrap(), i64::MIN);
1782 assert!(a.to_u64().is_none());
1783
1784 let a = i256::from_i128(i64::MIN as i128 - 1);
1785 assert!(a.to_i64().is_none());
1786 assert!(a.to_u64().is_none());
1787
1788 let a = i256::from_i128((1i128 << 64) + 5);
1791 assert!(a.to_i64().is_none());
1792 assert!(a.to_u64().is_none());
1793 assert!(a.to_i32().is_none());
1794 assert!(a.to_i8().is_none());
1795
1796 let a = i256::from_i128(-((1i128 << 64) + 5));
1797 assert!(a.to_i64().is_none());
1798 assert!(a.to_u64().is_none());
1799 assert!(a.to_i32().is_none());
1800 assert!(a.to_i8().is_none());
1801
1802 let a = i256::from_i128(u64::MAX as i128);
1803 assert!(a.to_i64().is_none());
1804 assert_eq!(a.to_u64().unwrap(), u64::MAX);
1805
1806 let a = i256::from_parts(5, 1);
1807 assert!(a.to_i64().is_none());
1808 assert!(a.to_u64().is_none());
1809
1810 let a = i256::from_parts(u64::MAX as u128 + 5, 0);
1811 assert!(a.to_i64().is_none());
1812 assert!(a.to_u64().is_none());
1813 }
1814
1815 #[test]
1816 fn test_i256_as_i128() {
1817 let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(1));
1818 let i128 = a.as_i128();
1819 assert_eq!(i128, i128::MIN);
1820
1821 let a = i256::from_i128(i128::MAX).wrapping_add(i256::from_i128(2));
1822 let i128 = a.as_i128();
1823 assert_eq!(i128, i128::MIN + 1);
1824
1825 let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(1));
1826 let i128 = a.as_i128();
1827 assert_eq!(i128, i128::MAX);
1828
1829 let a = i256::from_i128(i128::MIN).wrapping_sub(i256::from_i128(2));
1830 let i128 = a.as_i128();
1831 assert_eq!(i128, i128::MAX - 1);
1832 }
1833
1834 #[test]
1835 fn test_string_roundtrip() {
1836 let roundtrip_cases = [
1837 i256::ZERO,
1838 i256::ONE,
1839 i256::MINUS_ONE,
1840 i256::from_i128(123456789),
1841 i256::from_i128(-123456789),
1842 i256::from_i128(i128::MIN),
1843 i256::from_i128(i128::MAX),
1844 i256::MIN,
1845 i256::MAX,
1846 ];
1847 for case in roundtrip_cases {
1848 let formatted = case.to_string();
1849 let back: i256 = formatted.parse().unwrap();
1850 assert_eq!(case, back);
1851 }
1852 }
1853
1854 #[test]
1855 fn test_display_matches_bigint() {
1856 let ten_pow_38 = i256::from_i128(10_i128.pow(38));
1857 let mut cases = vec![
1858 i256::ZERO,
1859 i256::ONE,
1860 i256::MINUS_ONE,
1861 i256::from_i128(i128::MAX),
1862 i256::from_i128(i128::MIN),
1863 i256::from_i128(i128::MAX).wrapping_add(i256::ONE),
1864 i256::from_i128(i128::MIN).wrapping_sub(i256::ONE),
1865 ten_pow_38,
1866 ten_pow_38.wrapping_sub(i256::ONE),
1867 ten_pow_38.wrapping_neg(),
1868 ten_pow_38.wrapping_mul(ten_pow_38),
1869 ten_pow_38.wrapping_mul(ten_pow_38).wrapping_neg(),
1870 ten_pow_38.wrapping_mul(ten_pow_38).wrapping_add(i256::ONE),
1871 i256::MAX,
1872 i256::MIN,
1873 i256::MIN.wrapping_add(i256::ONE),
1874 ];
1875 let mut value = i256::ONE;
1877 while value != i256::ZERO {
1878 cases.push(value);
1879 cases.push(value.wrapping_sub(i256::ONE));
1880 cases.push(value.wrapping_neg());
1881 value = value.wrapping_mul(i256::from_i128(10));
1882 }
1883 for case in cases {
1884 let expected = BigInt::from_signed_bytes_le(&case.to_le_bytes()).to_string();
1885 assert_eq!(case.to_string(), expected);
1886 }
1887 }
1888
1889 #[test]
1890 fn test_from_string() {
1891 let cases = [
1892 (
1893 "000000000000000000000000000000000000000011",
1894 Some(i256::from_i128(11)),
1895 ),
1896 (
1897 "-000000000000000000000000000000000000000011",
1898 Some(i256::from_i128(-11)),
1899 ),
1900 (
1901 "-0000000000000000000000000000000000000000123456789",
1902 Some(i256::from_i128(-123456789)),
1903 ),
1904 ("-", None),
1905 ("+", None),
1906 ("--1", None),
1907 ("-+1", None),
1908 ("000000000000000000000000000000000000000", Some(i256::ZERO)),
1909 ("0000000000000000000000000000000000000000-11", None),
1910 ("11-1111111111111111111111111111111111111", None),
1911 (
1912 "115792089237316195423570985008687907853269984665640564039457584007913129639936",
1913 None,
1914 ),
1915 ];
1916 for (case, expected) in cases {
1917 assert_eq!(i256::from_string(case), expected)
1918 }
1919 }
1920
1921 #[expect(clippy::op_ref)]
1922 fn test_reference_op(il: i256, ir: i256) {
1923 let r1 = il + ir;
1924 let r2 = &il + ir;
1925 let r3 = il + &ir;
1926 let r4 = &il + &ir;
1927 assert_eq!(r1, r2);
1928 assert_eq!(r1, r3);
1929 assert_eq!(r1, r4);
1930
1931 let r1 = il - ir;
1932 let r2 = &il - ir;
1933 let r3 = il - &ir;
1934 let r4 = &il - &ir;
1935 assert_eq!(r1, r2);
1936 assert_eq!(r1, r3);
1937 assert_eq!(r1, r4);
1938
1939 let r1 = il * ir;
1940 let r2 = &il * ir;
1941 let r3 = il * &ir;
1942 let r4 = &il * &ir;
1943 assert_eq!(r1, r2);
1944 assert_eq!(r1, r3);
1945 assert_eq!(r1, r4);
1946
1947 let r1 = il / ir;
1948 let r2 = &il / ir;
1949 let r3 = il / &ir;
1950 let r4 = &il / &ir;
1951 assert_eq!(r1, r2);
1952 assert_eq!(r1, r3);
1953 assert_eq!(r1, r4);
1954 }
1955
1956 #[test]
1957 fn test_i256_reference_op() {
1958 let candidates = [
1959 i256::ONE,
1960 i256::MINUS_ONE,
1961 i256::from_i128(2),
1962 i256::from_i128(-2),
1963 i256::from_i128(3),
1964 i256::from_i128(-3),
1965 ];
1966
1967 for il in candidates {
1968 for ir in candidates {
1969 test_reference_op(il, ir)
1970 }
1971 }
1972 }
1973
1974 #[test]
1975 fn test_i256_to_f64_midpoint_rounding() {
1976 let integer = (1_i128 << 63) + 1024 + 1;
1978 assert_eq!(
1979 i256::from_i128(integer).to_f64().unwrap().to_bits(),
1980 (integer as f64).to_bits()
1981 );
1982
1983 let two = i256::from(2);
1984 for exponent in 53..=254 {
1989 let midpoint = two.wrapping_pow(exponent) + two.wrapping_pow(exponent - 53);
1990 for delta in -2_i64..=2 {
1991 for value in [
1992 midpoint + i256::from(delta),
1993 -(midpoint + i256::from(delta)),
1994 ] {
1995 let expected: f64 = value.to_string().parse().unwrap();
1996 assert_eq!(
1997 value.to_f64().unwrap().to_bits(),
1998 expected.to_bits(),
1999 "i256 {value} should round to nearest"
2000 );
2001 }
2002 }
2003 }
2004 }
2005
2006 #[test]
2007 fn test_i256_to_f64_fuzz() {
2008 for value in [i256::MIN, i256::MAX, i256::MINUS_ONE, i256::ZERO, i256::ONE] {
2010 let expected: f64 = value.to_string().parse().unwrap();
2011 assert_eq!(value.to_f64().unwrap().to_bits(), expected.to_bits());
2012 }
2013
2014 let mut rng = StdRng::seed_from_u64(42);
2015 for _ in 0..1_000 {
2016 let low = u128::from(rng.random::<u64>()) | (u128::from(rng.random::<u64>()) << 64);
2017 let high = u128::from(rng.random::<u64>()) | (u128::from(rng.random::<u64>()) << 64);
2018 let value = i256::from_parts(low, high as i128);
2019 let expected: f64 = value.to_string().parse().unwrap();
2020 assert_eq!(value.to_f64().unwrap().to_bits(), expected.to_bits());
2021 }
2022 }
2023
2024 #[test]
2025 fn test_decimal256_to_f64_typical_values() {
2026 let v = i256::from_i128(42_i128);
2027 assert_eq!(v.to_f64().unwrap(), 42.0);
2028
2029 let v = i256::from_i128(-123456789012345678i128);
2030 assert_eq!(v.to_f64().unwrap(), -123_456_789_012_345_680.0);
2031
2032 let v = i256::from_string("0").unwrap();
2033 assert_eq!(v.to_f64().unwrap(), 0.0);
2034
2035 let v = i256::from_string("1").unwrap();
2036 assert_eq!(v.to_f64().unwrap(), 1.0);
2037
2038 let mut rng = rng();
2039 for _ in 0..10 {
2040 let f64_value =
2041 (rng.random_range(i128::MIN..i128::MAX) as f64) * rng.random_range(0.0..1.0);
2042 let big = i256::from_f64(f64_value).unwrap();
2043 assert_eq!(big.to_f64().unwrap(), f64_value);
2044 }
2045 }
2046
2047 #[test]
2048 fn test_decimal256_to_f64_large_positive_value() {
2049 let max_f = f64::MAX;
2050 let big = i256::from_f64(max_f * 2.0).unwrap_or(i256::MAX);
2051 let out = big.to_f64().unwrap();
2052 assert!(out.is_finite() && out.is_sign_positive());
2053 }
2054
2055 #[test]
2056 fn test_decimal256_to_f64_large_negative_value() {
2057 let max_f = f64::MAX;
2058 let big_neg = i256::from_f64(-(max_f * 2.0)).unwrap_or(i256::MIN);
2059 let out = big_neg.to_f64().unwrap();
2060 assert!(out.is_finite() && out.is_sign_negative());
2061 }
2062
2063 #[test]
2064 fn test_num_traits() {
2065 let value = i256::from_i128(-5);
2066 assert_eq!(
2067 <i256 as CheckedNeg>::checked_neg(&value),
2068 Some(i256::from(5))
2069 );
2070
2071 assert_eq!(
2072 <i256 as CheckedAdd>::checked_add(&value, &value),
2073 Some(i256::from(-10))
2074 );
2075
2076 assert_eq!(
2077 <i256 as CheckedSub>::checked_sub(&value, &value),
2078 Some(i256::from(0))
2079 );
2080
2081 assert_eq!(
2082 <i256 as CheckedMul>::checked_mul(&value, &value),
2083 Some(i256::from(25))
2084 );
2085
2086 assert_eq!(
2087 <i256 as CheckedDiv>::checked_div(&value, &value),
2088 Some(i256::from(1))
2089 );
2090
2091 assert_eq!(
2092 <i256 as CheckedRem>::checked_rem(&value, &value),
2093 Some(i256::from(0))
2094 );
2095
2096 assert_eq!(
2097 <i256 as WrappingAdd>::wrapping_add(&value, &value),
2098 i256::from(-10)
2099 );
2100
2101 assert_eq!(
2102 <i256 as WrappingSub>::wrapping_sub(&value, &value),
2103 i256::from(0)
2104 );
2105
2106 assert_eq!(
2107 <i256 as WrappingMul>::wrapping_mul(&value, &value),
2108 i256::from(25)
2109 );
2110
2111 assert_eq!(<i256 as WrappingNeg>::wrapping_neg(&value), i256::from(5));
2112
2113 let result = <i256 as WrappingAdd>::wrapping_add(&i256::MAX, &i256::ONE);
2115 assert_eq!(result, i256::MIN);
2116
2117 assert_eq!(i256::MAX.saturating_add(&i256::ONE), i256::MAX);
2119 assert_eq!(i256::MIN.saturating_sub(&i256::ONE), i256::MIN);
2120 assert_eq!(i256::MIN.saturating_add(&i256::MINUS_ONE), i256::MIN);
2121 assert_eq!(i256::MAX.saturating_sub(&i256::MINUS_ONE), i256::MAX);
2122 assert_eq!(i256::MAX.saturating_mul(&i256::MAX), i256::MAX);
2123 assert_eq!(i256::MAX.saturating_mul(&i256::MIN), i256::MIN);
2124 assert_eq!(i256::MIN.saturating_mul(&i256::MAX), i256::MIN);
2125 assert_eq!(i256::MIN.saturating_mul(&i256::MIN), i256::MAX);
2126 assert_eq!(i256::MIN.saturating_mul(&i256::ONE), i256::MIN);
2127 assert_eq!(i256::MIN.saturating_mul(&i256::MINUS_ONE), i256::MAX);
2128 assert_eq!(
2129 i256::from(20).saturating_add(&i256::from(5)),
2130 i256::from(25)
2131 );
2132 assert_eq!(
2133 i256::from(20).saturating_sub(&i256::from(5)),
2134 i256::from(15)
2135 );
2136 assert_eq!(
2137 i256::from(20).saturating_mul(&i256::from(5)),
2138 i256::from(100)
2139 );
2140
2141 assert_eq!(
2143 i256::from(20).mul_add(i256::from(5), i256::from(10)),
2144 i256::from(110)
2145 );
2146
2147 let mut mul_add_value = i256::from(20);
2148 mul_add_value.mul_add_assign(i256::from(5), i256::from(10));
2149 assert_eq!(mul_add_value, i256::from(110));
2150
2151 let value = i256::from(-5);
2152 assert_eq!(<i256 as Signed>::abs(&value), i256::from(5));
2153
2154 assert_eq!(<i256 as One>::one(), i256::from(1));
2155 assert_eq!(<i256 as Zero>::zero(), i256::from(0));
2156
2157 assert_eq!(<i256 as Bounded>::min_value(), i256::MIN);
2158 assert_eq!(<i256 as Bounded>::max_value(), i256::MAX);
2159
2160 assert_eq!(!i256::ZERO, i256::MINUS_ONE);
2162 assert_eq!(!i256::MINUS_ONE, i256::ZERO);
2163 assert_eq!(!i256::ONE, i256::from_parts(u128::MAX - 1, -1));
2164 }
2165
2166 #[should_panic(expected = "rhs overflow for shift")]
2167 #[test]
2168 fn test_shl_panic_on_arg_overflow() {
2169 let value = i256::from(123);
2170 let rhs = std::hint::black_box(500);
2171 let _ = value << rhs;
2172 }
2173
2174 #[test]
2175 fn test_numtraits_from_str_radix() {
2176 assert_eq!(
2177 i256::from_str_radix("123456789", 10).expect("parsed"),
2178 i256::from(123456789)
2179 );
2180 assert_eq!(
2181 i256::from_str_radix("0", 10).expect("parsed"),
2182 i256::from(0)
2183 );
2184 assert!(i256::from_str_radix("abc", 10).is_err());
2185 assert!(i256::from_str_radix("0", 16).is_err());
2186 }
2187
2188 #[test]
2189 fn test_leading_zeros() {
2190 assert_eq!(i256::from(0).leading_zeros(), 256);
2192 assert_eq!(i256::from(1).leading_zeros(), 256 - 1);
2193 assert_eq!(i256::from(16).leading_zeros(), 256 - 5);
2194 assert_eq!(i256::from(17).leading_zeros(), 256 - 5);
2195
2196 assert_eq!(i256::from_parts(2, 16).leading_zeros(), 128 - 5);
2198 assert_eq!(i256::from_parts(2, i128::MAX).leading_zeros(), 1);
2199
2200 assert_eq!(i256::MAX.leading_zeros(), 1);
2201 assert_eq!(i256::from(-1).leading_zeros(), 0);
2202 }
2203
2204 #[test]
2205 fn test_trailing_zeros() {
2206 assert_eq!(i256::from(0).trailing_zeros(), 256);
2208 assert_eq!(i256::from(2).trailing_zeros(), 1);
2209 assert_eq!(i256::from(16).trailing_zeros(), 4);
2210 assert_eq!(i256::from(17).trailing_zeros(), 0);
2211 assert_eq!(i256::from_parts(0, i128::MAX).trailing_zeros(), 128);
2213 assert_eq!(i256::from_parts(0, 16).trailing_zeros(), 128 + 4);
2214 assert_eq!(i256::from_parts(2, i128::MAX).trailing_zeros(), 1);
2215
2216 assert_eq!(i256::MAX.trailing_zeros(), 0);
2217 assert_eq!(i256::from(-1).trailing_zeros(), 0);
2218 }
2219
2220 #[test]
2221 fn test_ilog() {
2222 let value = i256::from(128);
2223
2224 assert_eq!(value.ilog(i256::from(2)), 7);
2226 assert_eq!(value.ilog2(), 7);
2227
2228 assert_eq!(value.ilog(i256::from(10)), 2);
2230 assert_eq!(value.ilog10(), 2);
2231
2232 assert_eq!(value.checked_ilog(i256::from(-2)), None);
2234 assert_eq!(value.checked_ilog(i256::from(-10)), None);
2235 assert_eq!(value.checked_ilog(i256::from(0)), None);
2236 assert_eq!(value.checked_ilog(i256::from(1)), None);
2237
2238 let neg_value = i256::from(-128);
2240 assert_eq!(neg_value.checked_ilog(i256::from(2)), None);
2241 assert_eq!(neg_value.checked_ilog(i256::from(10)), None);
2242 assert_eq!(neg_value.checked_ilog10(), None);
2243 assert_eq!(neg_value.checked_ilog2(), None);
2244
2245 assert_eq!(i256::ZERO.checked_ilog(i256::from(2)), None);
2247 assert_eq!(i256::ZERO.checked_ilog(i256::from(10)), None);
2248 assert_eq!(i256::ZERO.checked_ilog10(), None);
2249 assert_eq!(i256::ZERO.checked_ilog2(), None);
2250
2251 assert_eq!(i256::from(2).checked_ilog(i256::from(2)), Some(1));
2253 assert_eq!(i256::from(3).checked_ilog(i256::from(3)), Some(1));
2254 assert_eq!(i256::from(5).checked_ilog(i256::from(5)), Some(1));
2255 assert_eq!(i256::from(1000).checked_ilog(i256::from(1000)), Some(1));
2256 assert_eq!(i256::from(2).checked_ilog2(), Some(1));
2257 assert_eq!(i256::from(2).ilog2(), 1);
2258 assert_eq!(i256::from(10).checked_ilog(i256::from(10)), Some(1));
2260
2261 assert_eq!(i256::from(3).checked_ilog(i256::from(5)), Some(0));
2263
2264 for base in [2i64, 3, 5, 7, 1000] {
2266 for v in 1i64..64 {
2267 let want = (v as u128).ilog(base as u128);
2268 assert_eq!(
2269 i256::from(v).checked_ilog(i256::from(base)),
2270 Some(want),
2271 "checked_ilog({v}, {base})"
2272 );
2273 }
2274 }
2275
2276 let value = i256::from_parts(100000000, 1234);
2277 assert_eq!(value.checked_ilog(i256::from(10)), Some(41));
2278 assert_eq!(value.checked_ilog10(), Some(41));
2279
2280 let large = i256::from_parts(100000000, i128::MAX);
2282 assert_eq!(large.checked_ilog(i256::from(2)), Some(254));
2284
2285 assert_eq!(large.checked_ilog(i256::from(10)), Some(76));
2287 assert_eq!(large.checked_ilog10(), Some(76));
2288
2289 assert_eq!(large.checked_ilog(i256::from(5)), Some(109));
2291
2292 assert!(i256::from(2).checked_pow(255).is_none());
2294 let value = i256::from(2).checked_pow(254).expect("construct");
2295 assert_eq!(value.checked_ilog(i256::from(2)), Some(254));
2296
2297 assert_eq!(i256::MAX.checked_ilog(i256::from(2)), Some(254));
2299 }
2300
2301 #[test]
2302 fn test_ilog10() {
2303 assert_eq!(i256::ZERO.checked_ilog10(), None);
2305 assert_eq!(i256::MINUS_ONE.checked_ilog10(), None);
2306 assert_eq!(i256::MAX.checked_ilog10(), Some(76));
2307 assert_eq!(i256::from(10).checked_ilog10(), Some(1));
2308
2309 assert_eq!(i256::from(1).checked_ilog10(), Some(0));
2311 assert_eq!(i256::from(9).checked_ilog10(), Some(0));
2312
2313 assert_eq!(i256::from(100).checked_ilog10(), Some(2));
2315 assert_eq!(i256::from_parts(u128::MAX, 0).checked_ilog10(), Some(38));
2317
2318 assert_eq!(i256::from_parts(0, 1).checked_ilog10(), Some(38));
2320
2321 let pow50 = i256::from(10).checked_pow(50).unwrap();
2323 assert_eq!(pow50.checked_ilog10(), Some(50));
2324
2325 let pow64 = i256::from(10).checked_pow(64).unwrap();
2327 assert_eq!(pow64.checked_ilog10(), Some(64));
2328 }
2329
2330 #[test]
2331 #[should_panic(expected = "ilog10 overflow")]
2332 fn test_ilog10_zero_panics() {
2333 let _ = i256::ZERO.ilog10();
2334 }
2335
2336 #[test]
2337 #[should_panic(expected = "ilog overflow")]
2338 fn test_ilog_zero_panics() {
2339 let _ = i256::ZERO.ilog(i256::from(5));
2340 }
2341
2342 #[test]
2343 #[should_panic(expected = "ilog2 overflow")]
2344 fn test_ilog2_zero_panics() {
2345 let _ = i256::ZERO.ilog2();
2346 }
2347}