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

everscale_types/num/
varuint248.rs
