tycho_types/num/
varuint248.rs

1use std::mem::MaybeUninit;
2use std::str::FromStr;
3
4use crate::cell::{CellBuilder, CellContext, CellSlice, ExactSize, Load, Size, Store};
5use crate::error::Error;
6use crate::util::unlikely;
7
8/// Variable-length 248-bit integer.
9///
10/// Stored as 5 bits of `len` (`0..=31`), followed by `len` bytes.
11#[derive(Debug, Default, Clone, Copy, Hash, PartialEq, Eq)]
12#[repr(transparent)]
13pub struct VarUint248([u128; 2]);
14
15impl VarUint248 {
16    /// The additive identity for this integer type, i.e. `0`.
17    pub const ZERO: Self = Self([0, 0]);
18
19    /// The multiplicative identity for this integer type, i.e. `1`.
20    pub const ONE: Self = Self([1, 0]);
21
22    /// The smallest value that can be represented by this integer type.
23    pub const MIN: Self = Self::new(1);
24
25    /// The largest value that can be represented by this integer type.
26    pub const MAX: Self = Self::from_words(u128::MAX >> 8, u128::MAX);
27
28    /// The number of data bits that the length occupies.
29    pub const LEN_BITS: u16 = 5;
30
31    /// The maximum number of data bits that this struct occupies.
32    pub const MAX_BITS: u16 = Self::LEN_BITS + 31 * 8;
33
34    /// Creates a new integer value from a primitive integer.
35    #[inline]
36    pub const fn new(value: u128) -> Self {
37        Self::from_words(0, value)
38    }
39
40    /// Constructs self from a pair of high and low underlying integers.
41    #[inline]
42    pub const fn from_words(hi: u128, lo: u128) -> Self {
43        #[cfg(target_endian = "little")]
44        {
45            Self([lo, hi])
46        }
47        #[cfg(target_endian = "big")]
48        {
49            Self([hi, lo])
50        }
51    }
52
53    /// Returns a tuple of high and low underlying integers.
54    #[inline]
55    pub const fn into_words(self) -> (u128, u128) {
56        #[cfg(target_endian = "little")]
57        {
58            (self.0[1], self.0[0])
59        }
60        #[cfg(target_endian = "big")]
61        {
62            (self.0[0], self.0[1])
63        }
64    }
65
66    /// Converts a string slice in a given base to an integer.
67    pub fn from_str_radix(src: &str, radix: u32) -> Result<Self, std::num::ParseIntError> {
68        from_str_radix(src, radix, None)
69    }
70
71    /// Returns `true` if an underlying primitive integer is zero.
72    #[inline]
73    pub const fn is_zero(&self) -> bool {
74        self.0[0] == 0 && self.0[1] == 0
75    }
76
77    /// Returns `true` if an underlying primitive integer fits into the repr.
78    #[inline]
79    pub const fn is_valid(&self) -> bool {
80        *self.high() <= (u128::MAX >> 8)
81    }
82
83    /// Returns number of data bits that this struct occupies.
84    /// Returns `None` if an underlying primitive integer is too large.
85    pub const fn bit_len(&self) -> Option<u16> {
86        let bytes = (32 - self.leading_zeros() / 8) as u8;
87        if unlikely(bytes > 31) {
88            None
89        } else {
90            Some(Self::LEN_BITS + bytes as u16 * 8)
91        }
92    }
93
94    /// Returns the number of leading zeros in the binary representation of self.
95    pub const fn leading_zeros(&self) -> u32 {
96        let (hi, lo) = self.into_words();
97        if hi == 0 {
98            128 + lo.leading_zeros()
99        } else {
100            hi.leading_zeros()
101        }
102    }
103
104    /// Saturating integer addition. Computes `self + rhs`,
105    /// saturating at the numeric bounds instead of overflowing.
106    #[must_use]
107    pub const fn saturating_add(self, rhs: &Self) -> Self {
108        match self.checked_add(rhs) {
109            Some(value) => value,
110            None => Self::MAX,
111        }
112    }
113
114    /// Saturating integer addition. Computes `self - rhs`,
115    /// saturating at the numeric bounds instead of overflowing.
116    #[must_use]
117    pub const fn saturating_sub(self, rhs: &Self) -> Self {
118        let (lo, carry_lo) = self.low().overflowing_sub(*rhs.low());
119        let (hi, carry_c) = self.high().overflowing_sub(carry_lo as _);
120        let (hi, carry_hi) = hi.overflowing_sub(*rhs.high());
121
122        if carry_c || carry_hi {
123            return Self::ZERO;
124        }
125
126        let res = Self::from_words(hi, lo);
127        if res.is_valid() {
128            res
129        } else {
130            Self::MAX
131        }
132    }
133
134    /// Saturating integer multiplication. Computes `self * rhs`,
135    /// returning `None` if overflow occurred.
136    #[must_use]
137    pub fn saturating_mul(self, rhs: &Self) -> Self {
138        match self.checked_mul(rhs) {
139            Some(value) => value,
140            None => Self::MAX,
141        }
142    }
143
144    /// Checked integer addition. Computes `self + rhs`,
145    /// returning `None` if overflow occurred.
146    #[must_use]
147    pub const fn checked_add(&self, rhs: &Self) -> Option<Self> {
148        let (lo, carry_lo) = self.low().overflowing_add(*rhs.low());
149        let (hi, carry_c) = self.high().overflowing_add(carry_lo as _);
150        let (hi, carry_hi) = hi.overflowing_add(*rhs.high());
151
152        if carry_c || carry_hi {
153            return None;
154        }
155
156        let res = Self::from_words(hi, lo);
157        if res.is_valid() {
158            Some(res)
159        } else {
160            None
161        }
162    }
163
164    /// Checked integer subtraction. Computes `self - rhs`,
165    /// returning `None` if overflow occurred.
166    #[must_use]
167    pub const fn checked_sub(&self, rhs: &Self) -> Option<Self> {
168        let (lo, carry_lo) = self.low().overflowing_sub(*rhs.low());
169        let (hi, carry_c) = self.high().overflowing_sub(carry_lo as _);
170        let (hi, carry_hi) = hi.overflowing_sub(*rhs.high());
171
172        if carry_c || carry_hi {
173            return None;
174        }
175
176        let res = Self::from_words(hi, lo);
177        if res.is_valid() {
178            Some(res)
179        } else {
180            None
181        }
182    }
183
184    /// Checked integer multiplication. Computes `self * rhs`,
185    /// returning `None` if overflow occurred.
186    #[must_use]
187    pub fn checked_mul(&self, rhs: &Self) -> Option<Self> {
188        let mut res = umulddi3(self.low(), rhs.low());
189
190        let (hi_lo, overflow_hi_lo) = self.high().overflowing_mul(*rhs.low());
191        let (lo_hi, overflow_lo_hi) = self.low().overflowing_mul(*rhs.high());
192        let (hi, overflow_hi) = hi_lo.overflowing_add(lo_hi);
193        let (high, overflow_high) = res.high().overflowing_add(hi);
194        *res.high_mut() = high;
195
196        let overflow_hi_hi = (*self.high() != 0) & (*rhs.high() != 0);
197
198        if overflow_hi_lo
199            || overflow_lo_hi
200            || overflow_hi
201            || overflow_high
202            || overflow_hi_hi
203            || !self.is_valid()
204        {
205            None
206        } else {
207            Some(res)
208        }
209    }
210
211    /// The lower part of the integer.
212    pub const fn low(&self) -> &u128 {
213        &self.0[0]
214    }
215
216    /// The higher part of the integer.
217    pub const fn high(&self) -> &u128 {
218        &self.0[1]
219    }
220
221    /// A mutable reference to the lower part of the integer.
222    pub fn low_mut(&mut self) -> &mut u128 {
223        &mut self.0[0]
224    }
225
226    /// A mutable reference to the higher part of the integer.
227    pub fn high_mut(&mut self) -> &mut u128 {
228        &mut self.0[1]
229    }
230
231    /// Cast to a primitive `isize`.
232    #[inline]
233    pub const fn as_isize(self) -> isize {
234        let (_, lo) = self.into_words();
235        lo as _
236    }
237
238    /// Cast to a primitive `usize`.
239    #[inline]
240    pub const fn as_usize(self) -> usize {
241        let (_, lo) = self.into_words();
242        lo as _
243    }
244}
245
246macro_rules! impl_from {
247    ($($ty:ty),*$(,)?) => {
248        $(impl From<$ty> for VarUint248 {
249            #[inline]
250            fn from(value: $ty) -> Self {
251                Self::new(value as _)
252            }
253        })*
254    };
255}
256
257impl_from! { u8, u16, u32, u64, u128, usize }
258
259#[cfg(feature = "bigint")]
260impl From<VarUint248> for num_bigint::BigInt {
261    #[inline]
262    fn from(value: VarUint248) -> Self {
263        num_bigint::BigUint::from(value).into()
264    }
265}
266
267#[cfg(feature = "bigint")]
268impl From<VarUint248> for num_bigint::BigUint {
269    fn from(value: VarUint248) -> Self {
270        let (high, low) = value.into_words();
271        if high == 0 {
272            return Self::from(low);
273        }
274
275        let mut res = Self::from(high);
276        res <<= 128;
277        res += low;
278        res
279    }
280}
281
282impl ExactSize for VarUint248 {
283    #[inline]
284    fn exact_size(&self) -> Size {
285        Size {
286            bits: self.bit_len().unwrap_or_default(),
287            refs: 0,
288        }
289    }
290}
291
292impl PartialEq<u128> for VarUint248 {
293    fn eq(&self, other: &u128) -> bool {
294        self.into_words() == (0, *other)
295    }
296}
297
298impl Ord for VarUint248 {
299    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
300        self.into_words().cmp(&other.into_words())
301    }
302}
303
304impl PartialOrd for VarUint248 {
305    #[inline]
306    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
307        Some(self.cmp(other))
308    }
309}
310
311impl PartialOrd<u128> for VarUint248 {
312    #[inline]
313    fn partial_cmp(&self, other: &u128) -> Option<std::cmp::Ordering> {
314        Some(self.into_words().cmp(&(0, *other)))
315    }
316}
317
318impl Store for VarUint248 {
319    fn store_into(&self, builder: &mut CellBuilder, _: &dyn CellContext) -> Result<(), Error> {
320        let bytes = (32 - self.leading_zeros() / 8) as u8;
321        let mut bits = bytes as u16 * 8;
322
323        if unlikely(bytes > 31 || !builder.has_capacity(Self::LEN_BITS + bits, 0)) {
324            return Err(Error::CellOverflow);
325        }
326
327        ok!(builder.store_small_uint(bytes, Self::LEN_BITS));
328
329        let (hi, lo) = self.into_words();
330        if let Some(high_bits) = bits.checked_sub(128) {
331            ok!(super::store_u128(builder, hi, high_bits));
332            bits -= high_bits;
333        }
334        super::store_u128(builder, lo, bits)
335    }
336}
337
338impl<'a> Load<'a> for VarUint248 {
339    fn load_from(slice: &mut CellSlice<'a>) -> Result<Self, Error> {
340        let mut bytes = ok!(slice.load_small_uint(Self::LEN_BITS));
341
342        let mut hi: u128 = 0;
343        if let Some(high_bytes) = bytes.checked_sub(16) {
344            if high_bytes > 0 {
345                hi = ok!(super::load_u128(slice, high_bytes));
346                bytes -= high_bytes;
347            }
348        }
349
350        match super::load_u128(slice, bytes) {
351            Ok(lo) => Ok(Self::from_words(hi, lo)),
352            Err(e) => Err(e),
353        }
354    }
355}
356
357#[cfg(feature = "serde")]
358impl serde::Serialize for VarUint248 {
359    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
360    where
361        S: serde::Serializer,
362    {
363        if serializer.is_human_readable() {
364            serializer.collect_str(self)
365        } else {
366            self.0.serialize(serializer)
367        }
368    }
369}
370
371#[cfg(feature = "serde")]
372impl<'de> serde::Deserialize<'de> for VarUint248 {
373    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
374    where
375        D: serde::Deserializer<'de>,
376    {
377        use serde::de::{Error, Unexpected, Visitor};
378
379        struct VarUint248Visitor;
380
381        impl Visitor<'_> for VarUint248Visitor {
382            type Value = VarUint248;
383
384            fn expecting(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
385                f.write_str("a formatted 248-bit integer")
386            }
387
388            fn visit_str<E>(self, v: &str) -> Result<Self::Value, E>
389            where
390                E: Error,
391            {
392                from_str_radix(v, 10, None).map_err(Error::custom)
393            }
394
395            fn visit_bytes<E>(self, v: &[u8]) -> Result<Self::Value, E>
396            where
397                E: Error,
398            {
399                let Ok(string) = std::str::from_utf8(v) else {
400                    return Err(Error::invalid_value(Unexpected::Bytes(v), &self));
401                };
402                self.visit_str(string)
403            }
404        }
405
406        if deserializer.is_human_readable() {
407            deserializer.deserialize_str(VarUint248Visitor)
408        } else {
409            <_>::deserialize(deserializer).map(Self)
410        }
411    }
412}
413
414#[cfg(feature = "arbitrary")]
415impl<'a> arbitrary::Arbitrary<'a> for VarUint248 {
416    #[inline]
417    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
418        Ok(Self::from_words(
419            u.int_in_range(0..=(u128::MAX >> 8))?,
420            u.arbitrary()?,
421        ))
422    }
423
424    #[inline]
425    fn size_hint(_: usize) -> (usize, Option<usize>) {
426        (32, Some(32))
427    }
428}
429
430impl std::ops::Add<u128> for VarUint248 {
431    type Output = Self;
432
433    #[inline]
434    fn add(mut self, rhs: u128) -> Self::Output {
435        self += Self::new(rhs);
436        self
437    }
438}
439
440impl std::ops::Add for VarUint248 {
441    type Output = Self;
442
443    #[inline]
444    fn add(mut self, rhs: Self) -> Self::Output {
445        self += &rhs;
446        self
447    }
448}
449
450impl std::ops::Add<&Self> for VarUint248 {
451    type Output = Self;
452
453    #[inline]
454    fn add(mut self, rhs: &Self) -> Self::Output {
455        self += rhs;
456        self
457    }
458}
459
460impl std::ops::AddAssign<u128> for VarUint248 {
461    fn add_assign(&mut self, rhs: u128) {
462        std::ops::AddAssign::<&Self>::add_assign(self, &Self::new(rhs))
463    }
464}
465
466impl std::ops::AddAssign for VarUint248 {
467    fn add_assign(&mut self, rhs: Self) {
468        std::ops::AddAssign::<&Self>::add_assign(self, &rhs)
469    }
470}
471
472impl std::ops::AddAssign<&Self> for VarUint248 {
473    fn add_assign(&mut self, rhs: &Self) {
474        let (lo, carry) = self.low().overflowing_add(*rhs.low());
475        *self.low_mut() = lo;
476        *self.high_mut() = rhs
477            .high()
478            .wrapping_add(carry as _)
479            .wrapping_add(*rhs.high());
480    }
481}
482
483impl std::ops::Sub<u128> for VarUint248 {
484    type Output = Self;
485
486    #[inline]
487    fn sub(mut self, rhs: u128) -> Self::Output {
488        self -= &Self::new(rhs);
489        self
490    }
491}
492
493impl std::ops::Sub for VarUint248 {
494    type Output = Self;
495
496    #[inline]
497    fn sub(mut self, rhs: Self) -> Self::Output {
498        self -= &rhs;
499        self
500    }
501}
502
503impl std::ops::Sub<&Self> for VarUint248 {
504    type Output = Self;
505
506    #[inline]
507    fn sub(mut self, rhs: &Self) -> Self::Output {
508        self -= rhs;
509        self
510    }
511}
512
513impl std::ops::SubAssign<u128> for VarUint248 {
514    fn sub_assign(&mut self, rhs: u128) {
515        std::ops::SubAssign::<&Self>::sub_assign(self, &Self::new(rhs))
516    }
517}
518
519impl std::ops::SubAssign for VarUint248 {
520    #[inline]
521    fn sub_assign(&mut self, rhs: Self) {
522        std::ops::SubAssign::<&Self>::sub_assign(self, &rhs)
523    }
524}
525
526impl std::ops::SubAssign<&Self> for VarUint248 {
527    fn sub_assign(&mut self, rhs: &Self) {
528        let (lo, carry) = self.low().overflowing_sub(*rhs.low());
529        *self.low_mut() = lo;
530        *self.high_mut() = self
531            .high()
532            .wrapping_sub(carry as _)
533            .wrapping_sub(*rhs.high());
534    }
535}
536
537impl std::ops::Shr<i32> for VarUint248 {
538    type Output = Self;
539
540    #[inline]
541    fn shr(mut self, rhs: i32) -> Self::Output {
542        self >>= rhs as usize;
543        self
544    }
545}
546
547impl std::ops::Shr<u32> for VarUint248 {
548    type Output = Self;
549
550    #[inline]
551    fn shr(mut self, rhs: u32) -> Self::Output {
552        self >>= rhs as usize;
553        self
554    }
555}
556
557impl std::ops::Shr<usize> for VarUint248 {
558    type Output = Self;
559
560    #[inline]
561    fn shr(mut self, rhs: usize) -> Self::Output {
562        self >>= rhs;
563        self
564    }
565}
566
567impl std::ops::ShrAssign<usize> for VarUint248 {
568    fn shr_assign(&mut self, n: usize) {
569        debug_assert!(n < 256, "shr overflow");
570
571        match n {
572            0 => {}
573            1..=127 => {
574                let hi = *self.high();
575                *self.high_mut() >>= n;
576                *self.low_mut() >>= n;
577                *self.low_mut() |= hi << (128 - n);
578            }
579            _ => {
580                let hi = *self.high();
581                *self.high_mut() = 0;
582                *self.low_mut() = hi >> (n & 127);
583            }
584        }
585    }
586}
587
588impl std::ops::Shl<i32> for VarUint248 {
589    type Output = Self;
590
591    #[inline]
592    fn shl(mut self, rhs: i32) -> Self::Output {
593        self <<= rhs as usize;
594        self
595    }
596}
597
598impl std::ops::Shl<u32> for VarUint248 {
599    type Output = Self;
600
601    #[inline]
602    fn shl(mut self, rhs: u32) -> Self::Output {
603        self <<= rhs as usize;
604        self
605    }
606}
607
608impl std::ops::Shl<usize> for VarUint248 {
609    type Output = Self;
610
611    fn shl(mut self, rhs: usize) -> Self::Output {
612        self <<= rhs;
613        self
614    }
615}
616
617impl std::ops::ShlAssign<usize> for VarUint248 {
618    fn shl_assign(&mut self, n: usize) {
619        debug_assert!(n < 256, "shl overflow");
620
621        match n {
622            0 => {}
623            1..=127 => {
624                let lo = *self.low();
625                *self.low_mut() <<= n;
626                *self.high_mut() <<= n;
627                *self.high_mut() |= lo >> (128 - n);
628            }
629            _ => {
630                let lo = *self.low();
631                *self.low_mut() = 0;
632                *self.high_mut() = lo << (n & 127);
633            }
634        }
635    }
636}
637
638impl std::ops::Mul<u128> for VarUint248 {
639    type Output = Self;
640
641    #[inline]
642    fn mul(mut self, rhs: u128) -> Self::Output {
643        self *= rhs;
644        self
645    }
646}
647
648impl std::ops::Mul for VarUint248 {
649    type Output = Self;
650
651    #[inline]
652    fn mul(mut self, rhs: Self) -> Self::Output {
653        self *= rhs;
654        self
655    }
656}
657
658impl std::ops::Mul<&Self> for VarUint248 {
659    type Output = Self;
660
661    #[inline]
662    fn mul(mut self, rhs: &Self) -> Self::Output {
663        self *= rhs;
664        self
665    }
666}
667
668impl std::ops::MulAssign<u128> for VarUint248 {
669    #[inline]
670    fn mul_assign(&mut self, rhs: u128) {
671        std::ops::MulAssign::<&Self>::mul_assign(self, &Self::new(rhs))
672    }
673}
674
675impl std::ops::MulAssign for VarUint248 {
676    #[inline]
677    fn mul_assign(&mut self, rhs: Self) {
678        std::ops::MulAssign::<&Self>::mul_assign(self, &rhs)
679    }
680}
681
682impl std::ops::MulAssign<&Self> for VarUint248 {
683    fn mul_assign(&mut self, rhs: &Self) {
684        // See https://github.com/nlordell/ethnum-rs/blob/main/src/intrinsics/native/mul.rs
685
686        let mut r = umulddi3(self.low(), rhs.low());
687        let a_hi_mul_b_lo = self.high().wrapping_mul(*rhs.low());
688        let a_lo_mul_b_hi = self.low().wrapping_mul(*rhs.high());
689        *r.high_mut() = r
690            .high()
691            .wrapping_add(a_hi_mul_b_lo.wrapping_add(a_lo_mul_b_hi));
692
693        *self = r;
694    }
695}
696
697impl std::ops::Div<u128> for VarUint248 {
698    type Output = Self;
699
700    #[inline]
701    fn div(mut self, rhs: u128) -> Self::Output {
702        self /= VarUint248::new(rhs);
703        self
704    }
705}
706
707impl std::ops::Div for VarUint248 {
708    type Output = Self;
709
710    #[inline]
711    fn div(mut self, rhs: Self) -> Self::Output {
712        self /= rhs;
713        self
714    }
715}
716
717impl std::ops::Div<&Self> for VarUint248 {
718    type Output = Self;
719
720    #[inline]
721    fn div(mut self, rhs: &Self) -> Self::Output {
722        self /= rhs;
723        self
724    }
725}
726
727impl std::ops::DivAssign<u128> for VarUint248 {
728    #[inline]
729    fn div_assign(&mut self, rhs: u128) {
730        std::ops::DivAssign::<&Self>::div_assign(self, &VarUint248::new(rhs))
731    }
732}
733
734impl std::ops::DivAssign for VarUint248 {
735    #[inline]
736    fn div_assign(&mut self, rhs: Self) {
737        std::ops::DivAssign::<&Self>::div_assign(self, &rhs)
738    }
739}
740
741impl std::ops::DivAssign<&Self> for VarUint248 {
742    fn div_assign(&mut self, rhs: &Self) {
743        let (a, b) = (*self, rhs);
744
745        // SAFETY: `udivmod` does not write `MaybeUninit::uninit()` to `res` and
746        // `VarUint248` does not implement `Drop`.
747        let res = unsafe { &mut *(self as *mut Self).cast() };
748        udivmod(res, &a, b, None);
749    }
750}
751
752impl std::ops::Rem<u128> for VarUint248 {
753    type Output = Self;
754
755    #[inline]
756    fn rem(mut self, rhs: u128) -> Self::Output {
757        self %= VarUint248::new(rhs);
758        self
759    }
760}
761
762impl std::ops::Rem for VarUint248 {
763    type Output = Self;
764
765    #[inline]
766    fn rem(mut self, rhs: Self) -> Self::Output {
767        self %= rhs;
768        self
769    }
770}
771
772impl std::ops::Rem<&Self> for VarUint248 {
773    type Output = Self;
774
775    #[inline]
776    fn rem(mut self, rhs: &Self) -> Self::Output {
777        self %= rhs;
778        self
779    }
780}
781
782impl std::ops::RemAssign<u128> for VarUint248 {
783    fn rem_assign(&mut self, rhs: u128) {
784        std::ops::RemAssign::<&Self>::rem_assign(self, &VarUint248::new(rhs))
785    }
786}
787
788impl std::ops::RemAssign for VarUint248 {
789    #[inline]
790    fn rem_assign(&mut self, rhs: Self) {
791        std::ops::RemAssign::<&Self>::rem_assign(self, &rhs)
792    }
793}
794
795impl std::ops::RemAssign<&Self> for VarUint248 {
796    fn rem_assign(&mut self, rhs: &Self) {
797        let mut res = MaybeUninit::uninit();
798        let (a, b) = (*self, rhs);
799
800        // SAFETY: `udivmod` does not write `MaybeUninit::uninit()` to `rem` and
801        // `VarUint248` does not implement `Drop`.
802        let r = unsafe { &mut *(self as *mut Self).cast() };
803        udivmod(&mut res, &a, b, Some(r));
804    }
805}
806
807#[inline]
808pub fn umulddi3(a: &u128, b: &u128) -> VarUint248 {
809    const BITS_IN_DWORD_2: u32 = 64;
810    const LOWER_MASK: u128 = u128::MAX >> BITS_IN_DWORD_2;
811
812    let mut low = (a & LOWER_MASK) * (b & LOWER_MASK);
813    let mut t = low >> BITS_IN_DWORD_2;
814    low &= LOWER_MASK;
815    t += (a >> BITS_IN_DWORD_2) * (b & LOWER_MASK);
816    low += (t & LOWER_MASK) << BITS_IN_DWORD_2;
817    let mut high = t >> BITS_IN_DWORD_2;
818    t = low >> BITS_IN_DWORD_2;
819    low &= LOWER_MASK;
820    t += (b >> BITS_IN_DWORD_2) * (a & LOWER_MASK);
821    low += (t & LOWER_MASK) << BITS_IN_DWORD_2;
822    high += t >> BITS_IN_DWORD_2;
823    high += (a >> BITS_IN_DWORD_2) * (b >> BITS_IN_DWORD_2);
824
825    VarUint248::from_words(high, low)
826}
827
828fn udivmod(
829    res: &mut MaybeUninit<VarUint248>,
830    a: &VarUint248,
831    b: &VarUint248,
832    rem: Option<&mut MaybeUninit<VarUint248>>,
833) {
834    // See https://github.com/nlordell/ethnum-rs/blob/main/src/intrinsics/native/divmod.rs
835
836    if a.high() | b.high() == 0 {
837        if let Some(rem) = rem {
838            rem.write(VarUint248::from_words(0, a.low() % b.low()));
839        }
840        res.write(VarUint248::from_words(0, a.low() / b.low()));
841        return;
842    }
843
844    let dividend = *a;
845    let divisor = *b;
846    let quotient: VarUint248;
847    let mut remainder: VarUint248;
848
849    if divisor > dividend {
850        if let Some(rem) = rem {
851            rem.write(dividend);
852        }
853        res.write(VarUint248::ZERO);
854        return;
855    }
856    // When the divisor fits in 128 bits, we can use an optimized path.
857    if *divisor.high() == 0 {
858        remainder = VarUint248::ZERO;
859        if dividend.high() < divisor.low() {
860            // The result fits in 128 bits.
861            quotient = VarUint248::from_words(
862                0,
863                udiv256_by_128_to_128(
864                    *dividend.high(),
865                    *dividend.low(),
866                    *divisor.low(),
867                    remainder.low_mut(),
868                ),
869            );
870        } else {
871            // First, divide with the high part to get the remainder in dividend.s.high.
872            // After that dividend.s.high < divisor.s.low.
873            quotient = VarUint248::from_words(
874                dividend.high() / divisor.low(),
875                udiv256_by_128_to_128(
876                    dividend.high() % divisor.low(),
877                    *dividend.low(),
878                    *divisor.low(),
879                    remainder.low_mut(),
880                ),
881            );
882        }
883        if let Some(rem) = rem {
884            rem.write(remainder);
885        }
886        res.write(quotient);
887        return;
888    }
889
890    (quotient, remainder) = div_mod_knuth(&dividend, &divisor);
891
892    if let Some(rem) = rem {
893        rem.write(remainder);
894    }
895    res.write(quotient);
896}
897
898#[inline(always)]
899fn udiv256_by_128_to_128(u1: u128, u0: u128, mut v: u128, r: &mut u128) -> u128 {
900    // See https://github.com/nlordell/ethnum-rs/blob/main/src/intrinsics/native/divmod.rs
901
902    const N_UDWORD_BITS: u32 = 128;
903    const B: u128 = 1 << (N_UDWORD_BITS / 2); // Number base (128 bits)
904    let (un1, un0): (u128, u128); // Norm. dividend LSD's
905    let (vn1, vn0): (u128, u128); // Norm. divisor digits
906    let (mut q1, mut q0): (u128, u128); // Quotient digits
907    let (un128, un21, un10): (u128, u128, u128); // Dividend digit pairs
908
909    let s = v.leading_zeros();
910    if s > 0 {
911        // Normalize the divisor.
912        v <<= s;
913        un128 = (u1 << s) | (u0 >> (N_UDWORD_BITS - s));
914        un10 = u0 << s; // Shift dividend left
915    } else {
916        // Avoid undefined behavior of (u0 >> 64).
917        un128 = u1;
918        un10 = u0;
919    }
920
921    // Break divisor up into two 64-bit digits.
922    vn1 = v >> (N_UDWORD_BITS / 2);
923    vn0 = v & 0xFFFF_FFFF_FFFF_FFFF;
924
925    // Break right half of dividend into two digits.
926    un1 = un10 >> (N_UDWORD_BITS / 2);
927    un0 = un10 & 0xFFFF_FFFF_FFFF_FFFF;
928
929    // Compute the first quotient digit, q1.
930    q1 = un128 / vn1;
931    let mut rhat = un128 - q1 * vn1;
932
933    // q1 has at most error 2. No more than 2 iterations.
934    while q1 >= B || q1 * vn0 > B * rhat + un1 {
935        q1 -= 1;
936        rhat += vn1;
937        if rhat >= B {
938            break;
939        }
940    }
941
942    un21 = un128
943        .wrapping_mul(B)
944        .wrapping_add(un1)
945        .wrapping_sub(q1.wrapping_mul(v));
946
947    // Compute the second quotient digit.
948    q0 = un21 / vn1;
949    rhat = un21 - q0 * vn1;
950
951    // q0 has at most error 2. No more than 2 iterations.
952    while q0 >= B || q0 * vn0 > B * rhat + un0 {
953        q0 -= 1;
954        rhat += vn1;
955        if rhat >= B {
956            break;
957        }
958    }
959
960    *r = (un21
961        .wrapping_mul(B)
962        .wrapping_add(un0)
963        .wrapping_sub(q0.wrapping_mul(v)))
964        >> s;
965    q1 * B + q0
966}
967
968#[inline]
969pub fn div_mod_knuth(u: &VarUint248, v: &VarUint248) -> (VarUint248, VarUint248) {
970    // See https://github.com/nlordell/ethnum-rs/blob/main/src/intrinsics/native/divmod.rs
971
972    const N_UDWORD_BITS: u32 = 128;
973
974    #[inline]
975    fn full_shl(a: &VarUint248, shift: u32) -> [u128; 3] {
976        debug_assert!(shift < N_UDWORD_BITS);
977        let mut u = [0_u128; 3];
978        let u_lo = a.low() << shift;
979        let u_hi = *a >> (N_UDWORD_BITS - shift);
980        u[0] = u_lo;
981        u[1] = *u_hi.low();
982        u[2] = *u_hi.high();
983
984        u
985    }
986
987    #[inline]
988    fn full_shr(u: &[u128; 3], shift: u32) -> VarUint248 {
989        debug_assert!(shift < N_UDWORD_BITS);
990        let mut res = VarUint248::ZERO;
991        *res.low_mut() = u[0] >> shift;
992        *res.high_mut() = u[1] >> shift;
993        // carry
994        if shift > 0 {
995            let sh = N_UDWORD_BITS - shift;
996            *res.low_mut() |= u[1] << sh;
997            *res.high_mut() |= u[2] << sh;
998        }
999
1000        res
1001    }
1002
1003    // returns (lo, hi)
1004    #[inline]
1005    const fn split_u128_to_u128(a: u128) -> (u128, u128) {
1006        (a & 0xFFFFFFFFFFFFFFFF, a >> (N_UDWORD_BITS / 2))
1007    }
1008
1009    // returns (lo, hi)
1010    #[inline]
1011    const fn fullmul_u128(a: u128, b: u128) -> (u128, u128) {
1012        let (a0, a1) = split_u128_to_u128(a);
1013        let (b0, b1) = split_u128_to_u128(b);
1014
1015        let mut t = a0 * b0;
1016        let mut k: u128;
1017        let w3: u128;
1018        (w3, k) = split_u128_to_u128(t);
1019
1020        t = a1 * b0 + k;
1021        let (w1, w2) = split_u128_to_u128(t);
1022        t = a0 * b1 + w1;
1023        k = t >> 64;
1024
1025        let w_hi = a1 * b1 + w2 + k;
1026        let w_lo = (t << 64) + w3;
1027
1028        (w_lo, w_hi)
1029    }
1030
1031    #[inline]
1032    fn fullmul_u256_u128(a: &VarUint248, b: u128) -> [u128; 3] {
1033        let mut acc = [0_u128; 3];
1034        let mut lo: u128;
1035        let mut carry: u128;
1036        let c: bool;
1037        if b != 0 {
1038            (lo, carry) = fullmul_u128(*a.low(), b);
1039            acc[0] = lo;
1040            acc[1] = carry;
1041            (lo, carry) = fullmul_u128(*a.high(), b);
1042            (acc[1], c) = acc[1].overflowing_add(lo);
1043            acc[2] = carry + c as u128;
1044        }
1045
1046        acc
1047    }
1048
1049    #[inline]
1050    const fn add_carry(a: u128, b: u128, c: bool) -> (u128, bool) {
1051        let (res1, overflow1) = b.overflowing_add(c as u128);
1052        let (res2, overflow2) = u128::overflowing_add(a, res1);
1053
1054        (res2, overflow1 || overflow2)
1055    }
1056
1057    #[inline]
1058    const fn sub_carry(a: u128, b: u128, c: bool) -> (u128, bool) {
1059        let (res1, overflow1) = b.overflowing_add(c as u128);
1060        let (res2, overflow2) = u128::overflowing_sub(a, res1);
1061
1062        (res2, overflow1 || overflow2)
1063    }
1064
1065    // D1.
1066    // Make sure 128th bit in v's highest word is set.
1067    // If we shift both u and v, it won't affect the quotient
1068    // and the remainder will only need to be shifted back.
1069    let shift = v.high().leading_zeros();
1070    debug_assert!(shift < N_UDWORD_BITS);
1071    let v = *v << shift;
1072    debug_assert!(v.high() >> (N_UDWORD_BITS - 1) == 1);
1073    // u will store the remainder (shifted)
1074    let mut u = full_shl(u, shift);
1075
1076    // quotient
1077    let mut q = VarUint248::ZERO;
1078    let v_n_1 = *v.high();
1079    let v_n_2 = *v.low();
1080
1081    // D2. D7. - unrolled loop j == 0, n == 2, m == 0 (only one possible iteration)
1082    let mut r_hat: u128 = 0;
1083    let u_jn = u[2];
1084
1085    // D3.
1086    // q_hat is our guess for the j-th quotient digit
1087    // q_hat = min(b - 1, (u_{j+n} * b + u_{j+n-1}) / v_{n-1})
1088    // b = 1 << WORD_BITS
1089    // Theorem B: q_hat >= q_j >= q_hat - 2
1090    let mut q_hat = if u_jn < v_n_1 {
1091        // let (mut q_hat, mut r_hat) = _div_mod_u128(u_jn, u[j + n - 1], v_n_1);
1092        let mut q_hat = udiv256_by_128_to_128(u_jn, u[1], v_n_1, &mut r_hat);
1093        let mut overflow: bool;
1094        // this loop takes at most 2 iterations
1095        loop {
1096            let another_iteration = {
1097                // check if q_hat * v_{n-2} > b * r_hat + u_{j+n-2}
1098                let (lo, hi) = fullmul_u128(q_hat, v_n_2);
1099                hi > r_hat || (hi == r_hat && lo > u[0])
1100            };
1101            if !another_iteration {
1102                break;
1103            }
1104            q_hat -= 1;
1105            (r_hat, overflow) = r_hat.overflowing_add(v_n_1);
1106            // if r_hat overflowed, we're done
1107            if overflow {
1108                break;
1109            }
1110        }
1111        q_hat
1112    } else {
1113        // here q_hat >= q_j >= q_hat - 1
1114        u128::MAX
1115    };
1116
1117    // ex. 20:
1118    // since q_hat * v_{n-2} <= b * r_hat + u_{j+n-2},
1119    // either q_hat == q_j, or q_hat == q_j + 1
1120
1121    // D4.
1122    // let's assume optimistically q_hat == q_j
1123    // subtract (q_hat * v) from u[j..]
1124    let q_hat_v = fullmul_u256_u128(&v, q_hat);
1125    // u[j..] -= q_hat_v;
1126    let mut c = false;
1127    (u[0], c) = sub_carry(u[0], q_hat_v[0], c);
1128    (u[1], c) = sub_carry(u[1], q_hat_v[1], c);
1129    (u[2], c) = sub_carry(u[2], q_hat_v[2], c);
1130
1131    // D6.
1132    // actually, q_hat == q_j + 1 and u[j..] has overflowed
1133    // highly unlikely ~ (1 / 2^127)
1134    if c {
1135        q_hat -= 1;
1136        // add v to u[j..]
1137        c = false;
1138        (u[0], c) = add_carry(u[0], *v.low(), c);
1139        (u[1], c) = add_carry(u[1], *v.high(), c);
1140        u[2] = u[2].wrapping_add(c as u128);
1141    }
1142
1143    // D5.
1144    *q.low_mut() = q_hat;
1145
1146    // D8.
1147    let remainder = full_shr(&u, shift);
1148
1149    (q, remainder)
1150}
1151
1152impl std::fmt::Display for VarUint248 {
1153    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1154        fmt_var_uint248(*self, f)
1155    }
1156}
1157
1158const DEC_DIGITS_LUT: &[u8; 200] = b"\
1159    0001020304050607080910111213141516171819\
1160    2021222324252627282930313233343536373839\
1161    4041424344454647484950515253545556575859\
1162    6061626364656667686970717273747576777879\
1163    8081828384858687888990919293949596979899";
1164
1165fn fmt_var_uint248(mut n: VarUint248, f: &mut std::fmt::Formatter) -> std::fmt::Result {
1166    // See https://github.com/nlordell/ethnum-rs/blob/main/src/fmt.rs
1167
1168    // 2^256 is about 1*10^78, so 79 gives an extra byte of space
1169    let mut buf = [MaybeUninit::<u8>::uninit(); 79];
1170    let mut curr = buf.len() as isize;
1171    let buf_ptr = &mut buf[0] as *mut _ as *mut u8;
1172    let lut_ptr = DEC_DIGITS_LUT.as_ptr();
1173
1174    // SAFETY: Since `d1` and `d2` are always less than or equal to `198`, we
1175    // can copy from `lut_ptr[d1..d1 + 1]` and `lut_ptr[d2..d2 + 1]`. To show
1176    // that it's OK to copy into `buf_ptr`, notice that at the beginning
1177    // `curr == buf.len() == 39 > log(n)` since `n < 2^128 < 10^39`, and at
1178    // each step this is kept the same as `n` is divided. Since `n` is always
1179    // non-negative, this means that `curr > 0` so `buf_ptr[curr..curr + 1]`
1180    // is safe to access.
1181    unsafe {
1182        // eagerly decode 4 characters at a time
1183        while n >= 10000 {
1184            let rem = (n % 10000).as_isize();
1185            n /= 10000;
1186
1187            let d1 = (rem / 100) << 1;
1188            let d2 = (rem % 100) << 1;
1189            curr -= 4;
1190
1191            // We are allowed to copy to `buf_ptr[curr..curr + 3]` here since
1192            // otherwise `curr < 0`. But then `n` was originally at least `10000^10`
1193            // which is `10^40 > 2^128 > n`.
1194            std::ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
1195            std::ptr::copy_nonoverlapping(lut_ptr.offset(d2), buf_ptr.offset(curr + 2), 2);
1196        }
1197
1198        // if we reach here numbers are <= 9999, so at most 4 chars long
1199        let mut n = n.as_isize(); // possibly reduce 64bit math
1200
1201        // decode 2 more chars, if > 2 chars
1202        if n >= 100 {
1203            let d1 = (n % 100) << 1;
1204            n /= 100;
1205            curr -= 2;
1206            std::ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
1207        }
1208
1209        // decode last 1 or 2 chars
1210        if n < 10 {
1211            curr -= 1;
1212            *buf_ptr.offset(curr) = (n as u8) + b'0';
1213        } else {
1214            let d1 = n << 1;
1215            curr -= 2;
1216            std::ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2);
1217        }
1218    }
1219
1220    // SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
1221    // UTF-8 since `DEC_DIGITS_LUT` is
1222    let buf_slice = unsafe {
1223        std::str::from_utf8_unchecked(std::slice::from_raw_parts(
1224            buf_ptr.offset(curr),
1225            buf.len() - curr as usize,
1226        ))
1227    };
1228    f.pad_integral(true, "", buf_slice)
1229}
1230
1231impl FromStr for VarUint248 {
1232    type Err = std::num::ParseIntError;
1233
1234    fn from_str(s: &str) -> Result<Self, Self::Err> {
1235        from_str_radix(s, 10, None)
1236    }
1237}
1238
1239fn from_str_radix(
1240    src: &str,
1241    radix: u32,
1242    prefix: Option<&str>,
1243) -> Result<VarUint248, std::num::ParseIntError> {
1244    use std::num::IntErrorKind::*;
1245
1246    // See https://github.com/nlordell/ethnum-rs/blob/main/src/parse.rs
1247
1248    const fn pie(kind: std::num::IntErrorKind) -> std::num::ParseIntError {
1249        unsafe { std::mem::transmute(kind) }
1250    }
1251
1252    assert!(
1253        (2..=36).contains(&radix),
1254        "from_str_radix_int: must lie in the range `[2, 36]` - found {radix}",
1255    );
1256
1257    if src.is_empty() {
1258        return Err(pie(Empty));
1259    }
1260
1261    // all valid digits are ascii, so we will just iterate over the utf8 bytes
1262    // and cast them to chars. .to_digit() will safely return None for anything
1263    // other than a valid ascii digit for the given radix, including the first-byte
1264    // of multi-byte sequences
1265    let src = src.as_bytes();
1266
1267    let prefixed_digits = match src[0] {
1268        b'+' | b'-' if src[1..].is_empty() => {
1269            return Err(pie(InvalidDigit));
1270        }
1271        b'+' => &src[1..],
1272        _ => src,
1273    };
1274
1275    let digits = match prefix {
1276        Some(prefix) => prefixed_digits
1277            .strip_prefix(prefix.as_bytes())
1278            .ok_or(pie(InvalidDigit))?,
1279        None => prefixed_digits,
1280    };
1281    if digits.is_empty() {
1282        return Err(pie(InvalidDigit));
1283    }
1284
1285    let mut result = VarUint248::ZERO;
1286
1287    if radix <= 16 && digits.len() <= 64 {
1288        for &c in digits {
1289            result *= radix as u128;
1290            let Some(x) = (c as char).to_digit(radix) else {
1291                return Err(pie(InvalidDigit));
1292            };
1293            result += x as u128;
1294        }
1295    } else {
1296        for &c in digits {
1297            match result.checked_mul(&VarUint248::from(radix)) {
1298                Some(mul) => result = mul,
1299                None => return Err(pie(PosOverflow)),
1300            }
1301
1302            let Some(x) = (c as char).to_digit(radix) else {
1303                return Err(pie(InvalidDigit));
1304            };
1305
1306            match result.checked_add(&VarUint248::from(x)) {
1307                Some(add) => result = add,
1308                None => return Err(pie(PosOverflow)),
1309            }
1310        }
1311    }
1312
1313    Ok(result)
1314}
1315
1316#[cfg(test)]
1317mod tests {
1318    use super::*;
1319
1320    #[test]
1321    fn valid_range_is_correct() {
1322        assert!(VarUint248::ZERO.is_valid());
1323        assert!(VarUint248::ONE.is_valid());
1324        assert!(VarUint248::new(123123).is_valid());
1325        assert!(VarUint248::new(u128::MAX).is_valid());
1326        // ...
1327        assert!(VarUint248::from_words(u128::MAX >> 8, u128::MAX).is_valid());
1328
1329        assert!(!VarUint248::from_words(u128::MAX >> 7, u128::MAX).is_valid());
1330        assert!(!VarUint248::from_words(u128::MAX, u128::MAX).is_valid());
1331
1332        assert_eq!(
1333            VarUint248::new(123).saturating_sub(&VarUint248::new(321)),
1334            VarUint248::ZERO
1335        );
1336
1337        assert_eq!(
1338            VarUint248::from_words(u128::MAX, u128::MAX).saturating_sub(&VarUint248::new(1)),
1339            VarUint248::MAX
1340        );
1341        assert_eq!(
1342            VarUint248::from_words(u128::MAX, u128::MAX)
1343                .saturating_sub(&VarUint248::from_words(u128::MAX, u128::MAX)),
1344            VarUint248::ZERO
1345        );
1346    }
1347
1348    #[test]
1349    fn store_into_cell() {
1350        for i in 0..128 {
1351            let lo = 1u128 << i;
1352
1353            let value = VarUint248::new(lo);
1354            let cell = CellBuilder::build_from(value).unwrap();
1355            assert_eq!(value.bit_len().unwrap(), cell.bit_len());
1356        }
1357    }
1358
1359    #[test]
1360    fn load_from_cell() {
1361        let mut lo: u128 = 0xababcdef89abcdefdeadbeeffafacafe;
1362        for _ in 0..=128 {
1363            let value = VarUint248::new(lo);
1364
1365            let cell = CellBuilder::build_from(value).unwrap();
1366
1367            let parsed_value = cell.parse::<VarUint248>().unwrap();
1368            assert_eq!(parsed_value, value);
1369
1370            lo >>= 1;
1371        }
1372    }
1373
1374    #[test]
1375    fn identity() {
1376        assert_eq!(VarUint248::ZERO + VarUint248::ZERO, VarUint248::ZERO);
1377        assert_eq!(VarUint248::ONE * VarUint248::ZERO, VarUint248::ZERO);
1378        assert_eq!(VarUint248::ONE * VarUint248::ONE, VarUint248::ONE);
1379    }
1380
1381    #[test]
1382    fn cmp() {
1383        // 1e38
1384        let x = VarUint248::from_words(0, 100000000000000000000000000000000000000);
1385        // 1e48
1386        let y = VarUint248::from_words(2938735877, 18960114910927365649471927446130393088);
1387        assert!(x < y);
1388        assert_eq!(x.cmp(&y), std::cmp::Ordering::Less);
1389        assert!(y > x);
1390        assert_eq!(y.cmp(&x), std::cmp::Ordering::Greater);
1391
1392        let x = VarUint248::new(100);
1393        let y = VarUint248::new(100);
1394        assert!(x <= y);
1395        assert_eq!(x.cmp(&y), std::cmp::Ordering::Equal);
1396    }
1397
1398    #[test]
1399    fn mul() {
1400        assert_eq!(VarUint248::new(6) * 7, VarUint248::new(42));
1401        assert_eq!(
1402            VarUint248::new(6).checked_mul(&VarUint248::new(7)),
1403            Some(VarUint248::new(42))
1404        );
1405
1406        assert_eq!(
1407            VarUint248::MAX.checked_mul(&VarUint248::ONE),
1408            Some(VarUint248::MAX)
1409        );
1410        assert_eq!(
1411            VarUint248::MAX.checked_mul(&VarUint248::ZERO),
1412            Some(VarUint248::ZERO)
1413        );
1414
1415        assert_eq!(
1416            VarUint248::new(u128::MAX) * u128::MAX,
1417            VarUint248::from_words(!0 << 1, 1),
1418        );
1419        assert_eq!(
1420            VarUint248::new(u128::MAX).checked_mul(&VarUint248::new(u128::MAX)),
1421            Some(VarUint248::from_words(!0 << 1, 1))
1422        );
1423
1424        assert_eq!(VarUint248::MAX.checked_mul(&VarUint248::new(257)), None);
1425        assert_eq!(VarUint248::MAX.checked_mul(&VarUint248::MAX), None);
1426    }
1427
1428    #[test]
1429    fn division() {
1430        // 0 X
1431        // ---
1432        // 0 X
1433        assert_eq!(VarUint248::new(100) / 9, 11);
1434
1435        // 0 X
1436        // ---
1437        // K X
1438        assert_eq!(VarUint248::new(!0u128) / (VarUint248::ONE << 128), 0u128);
1439
1440        // K 0
1441        // ---
1442        // K 0
1443        assert_eq!(
1444            VarUint248::from_words(100, 0) / VarUint248::from_words(10, 0),
1445            10
1446        );
1447
1448        // K K
1449        // ---
1450        // K 0
1451        assert_eq!(
1452            VarUint248::from_words(100, 1337) / (VarUint248::ONE << 130u32),
1453            25
1454        );
1455        assert_eq!(
1456            VarUint248::from_words(1337, !0) / VarUint248::from_words(63, 0),
1457            21
1458        );
1459
1460        // K X
1461        // ---
1462        // 0 K
1463        assert_eq!(
1464            VarUint248::from_words(42, 0) / VarUint248::ONE,
1465            VarUint248::from_words(42, 0),
1466        );
1467        assert_eq!(
1468            VarUint248::from_words(42, 42) / (VarUint248::ONE << 42),
1469            42u128 << (128 - 42),
1470        );
1471        assert_eq!(
1472            VarUint248::from_words(1337, !0) / 0xc0ffee,
1473            35996389033280467545299711090127855,
1474        );
1475        assert_eq!(
1476            VarUint248::from_words(42, 0) / 99,
1477            144362216269489045105674075880144089708,
1478        );
1479
1480        // K X
1481        // ---
1482        // K K
1483        assert_eq!(
1484            VarUint248::from_words(100, 100) / VarUint248::from_words(1000, 1000),
1485            0,
1486        );
1487        assert_eq!(
1488            VarUint248::from_words(1337, !0) / VarUint248::from_words(43, !0),
1489            30,
1490        );
1491    }
1492
1493    #[test]
1494    #[should_panic]
1495    fn division_by_zero() {
1496        _ = VarUint248::ONE / 0;
1497    }
1498
1499    #[test]
1500    fn remainder() {
1501        // 0 X
1502        // ---
1503        // 0 X
1504        assert_eq!(VarUint248::new(100) % 9, 1);
1505
1506        // 0 X
1507        // ---
1508        // K X
1509        assert_eq!(
1510            VarUint248::new(!0u128) % (VarUint248::ONE << 128u32),
1511            !0u128
1512        );
1513
1514        // K 0
1515        // ---
1516        // K 0
1517        assert_eq!(
1518            VarUint248::from_words(100, 0) % VarUint248::from_words(10, 0),
1519            0
1520        );
1521
1522        // K K
1523        // ---
1524        // K 0
1525        assert_eq!(
1526            VarUint248::from_words(100, 1337) % (VarUint248::ONE << 130u32),
1527            1337
1528        );
1529        assert_eq!(
1530            VarUint248::from_words(1337, !0) % VarUint248::from_words(63, 0),
1531            VarUint248::from_words(14, !0),
1532        );
1533
1534        // K X
1535        // ---
1536        // 0 K
1537        assert_eq!(VarUint248::from_words(42, 0) % VarUint248::ONE, 0);
1538        assert_eq!(
1539            VarUint248::from_words(42, 42) % (VarUint248::ONE << 42),
1540            42u128
1541        );
1542        assert_eq!(VarUint248::from_words(1337, !0) % 0xc0ffee, 1910477);
1543        assert_eq!(VarUint248::from_words(42, 0) % 99, 60);
1544
1545        // K X
1546        // ---
1547        // K K
1548        assert_eq!(
1549            VarUint248::from_words(100, 100) % VarUint248::from_words(1000, 1000),
1550            VarUint248::from_words(100, 100),
1551        );
1552        assert_eq!(
1553            VarUint248::from_words(1337, !0) % VarUint248::from_words(43, !0),
1554            VarUint248::from_words(18, 29),
1555        );
1556    }
1557
1558    #[test]
1559    #[should_panic]
1560    fn remainder_by_zero() {
1561        _ = VarUint248::ONE % 0;
1562    }
1563}
tycho_types/num/varuint248.rs

tycho_types/num/
varuint248.rs
