bobcat_maths/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2
3use core::{
4    cmp::{Eq, Ordering},
5    ops::{Add, Deref, DerefMut, Div, Index, Mul, Rem, Sub},
6};
7
8use num_traits::{One, Zero};
9
10#[cfg(feature = "borsh")]
11use borsh::{BorshDeserialize, BorshSerialize};
12
13#[cfg(feature = "alloc")]
14extern crate alloc;
15
16#[cfg(feature = "std")]
17use core::fmt::{Display, Formatter};
18
19pub type Address = [u8; 20];
20
21#[link(wasm_import_module = "vm_hooks")]
22#[cfg(not(feature = "alloy-enabled"))]
23unsafe extern "C" {
24    fn math_div(x: *mut u8, y: *const u8);
25    fn math_mod(x: *mut u8, y: *const u8);
26    fn math_add_mod(a: *mut u8, b: *const u8, c: *const u8);
27    fn math_mul_mod(a: *mut u8, b: *const u8, c: *const u8);
28}
29
30#[cfg(feature = "alloy-enabled")]
31mod alloy {
32    use core::ptr::copy_nonoverlapping;
33
34    pub(crate) use alloy_primitives::U256;
35
36    #[cfg(test)]
37    pub(crate) use alloy_primitives::I256;
38
39    pub(crate) unsafe fn math_div(out: *mut u8, y: *const u8) {
40        unsafe {
41            let x = U256::from_be_slice(&*(out as *const [u8; 32]));
42            let y = U256::from_be_slice(&*(y as *const [u8; 32]));
43            let z = if y.is_zero() {
44                // TODO: I think the node returns 0 when this is the case.
45                U256::ZERO
46            } else {
47                x / y
48            };
49            copy_nonoverlapping(z.to_be_bytes::<32>().as_ptr(), out, 32);
50        }
51    }
52
53    pub(crate) unsafe fn math_mod(out: *mut u8, y: *const u8) {
54        unsafe {
55            let x = U256::from_be_slice(&*(out as *const [u8; 32]));
56            let y = U256::from_be_slice(&*(y as *const [u8; 32]));
57            let z = x % y;
58            copy_nonoverlapping(z.to_be_bytes::<32>().as_ptr(), out, 32);
59        }
60    }
61
62    pub(crate) unsafe fn math_add_mod(a: *mut u8, b: *const u8, c: *const u8) {
63        unsafe {
64            let x = U256::from_be_slice(&*(a as *const [u8; 32]));
65            let y = U256::from_be_slice(&*(b as *const [u8; 32]));
66            let z = U256::from_be_slice(&*(c as *const [u8; 32]));
67            let x = x.add_mod(y, z);
68            copy_nonoverlapping(x.to_be_bytes::<32>().as_ptr(), a, 32);
69        }
70    }
71
72    pub(crate) unsafe fn math_mul_mod(a: *mut u8, b: *const u8, c: *const u8) {
73        unsafe {
74            let x = U256::from_be_slice(&*(a as *const [u8; 32]));
75            let y = U256::from_be_slice(&*(b as *const [u8; 32]));
76            let z = U256::from_be_slice(&*(c as *const [u8; 32]));
77            let x = x.mul_mod(y, z);
78            copy_nonoverlapping(x.to_be_bytes::<32>().as_ptr(), a, 32);
79        }
80    }
81}
82
83#[cfg(feature = "alloy-enabled")]
84use alloy::*;
85
86#[derive(Copy, Clone, Debug, PartialEq, Hash)]
87#[cfg_attr(feature = "proptest", derive(proptest_derive::Arbitrary))]
88#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
89#[cfg_attr(feature = "borsh", derive(BorshDeserialize, BorshSerialize))]
90#[repr(transparent)]
91pub struct U(pub [u8; 32]);
92
93#[derive(Copy, Clone, Debug, PartialEq, Hash)]
94#[cfg_attr(feature = "proptest", derive(proptest_derive::Arbitrary))]
95#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
96#[cfg_attr(feature = "borsh", derive(BorshDeserialize, BorshSerialize))]
97#[repr(transparent)]
98pub struct I(pub [u8; 32]);
99
100pub fn wrapping_div(x: &U, y: &U) -> U {
101    assert!(y.is_some(), "divide by zero");
102    let mut b = *x;
103    unsafe { math_div(b.as_mut_ptr(), y.as_ptr()) }
104    b
105}
106
107fn wrapping_div_quo_rem_b<const C: usize>(x: &[u8; C], denom: &[u8; C]) -> ([u8; C], [u8; C]) {
108    if denom == &[0u8; C] {
109        return ([0u8; C], [0u8; C])
110    }
111    let mut q = [0u8; C];
112    let mut r = [0u8; C];
113    let mut one = [0u8; C];
114    one[C - 1] = 1;
115    let mut two = [0u8; C];
116    two[C - 1] = 2;
117    let mut i = 0;
118    while i < C * 8 {
119        let bit = (x[i / 8] >> (7 - (i % 8))) & 1;
120        r = wrapping_mul_b::<C>(&r, &two);
121        if bit == 1 {
122            r = wrapping_add_b::<C>(&r, &one);
123        }
124        if r >= *denom {
125            r = wrapping_sub_b::<C>(&r, denom);
126            q[i / 8] |= 1 << (7 - (i % 8));
127        }
128        i += 1;
129    }
130    (q, r)
131}
132
133pub fn const_wrapping_div(x: &U, y: &U) -> U {
134    U(wrapping_div_quo_rem_b::<32>(&x.0, &y.0).0)
135}
136
137#[cfg_attr(test, mutants::skip)]
138pub fn checked_div(x: &U, y: &U) -> Option<U> {
139    if y.is_zero() {
140        None
141    } else {
142        Some(wrapping_div(x, y))
143    }
144}
145
146pub fn modd(x: &U, y: &U) -> U {
147    let mut b = *x;
148    unsafe { math_mod(b.as_mut_ptr(), y.as_ptr()) }
149    b
150}
151
152const fn wrapping_add_b<const C: usize>(x: &[u8; C], y: &[u8; C]) -> [u8; C] {
153    let mut r = [0u8; C];
154    let mut c = 0;
155    let mut i = C - 1;
156    loop {
157        let s = x[i] as u16 + y[i] as u16 + c;
158        r[i] = s as u8;
159        c = s >> 8;
160        if i == 0 {
161            break;
162        }
163        i -= 1;
164    }
165    r
166}
167
168pub const fn wrapping_add(x: &U, y: &U) -> U {
169    U(wrapping_add_b(&x.0, &y.0))
170}
171
172#[cfg_attr(test, mutants::skip)]
173pub fn checked_add(x: &U, y: &U) -> Option<U> {
174    if x > &(U::MAX - *y) {
175        None
176    } else {
177        let z = x.add_mod(y, &U::MAX);
178        if z.is_zero() && (x.is_some() || y.is_some()) {
179            Some(U::MAX)
180        } else {
181            Some(z)
182        }
183    }
184}
185
186#[cfg_attr(test, mutants::skip)]
187pub fn saturating_add(x: &U, y: &U) -> U {
188    checked_add(x, y).unwrap_or(U::MAX)
189}
190
191const fn wrapping_sub_b<const C: usize>(x: &[u8; C], y: &[u8; C]) -> [u8; C] {
192    let mut neg_y = *y;
193    let mut i = 0;
194    while i < C {
195        neg_y[i] = !neg_y[i];
196        i += 1;
197    }
198    let mut c = 1u16;
199    let mut i = C - 1;
200    loop {
201        let sum = neg_y[i] as u16 + c;
202        neg_y[i] = sum as u8;
203        c = sum >> 8;
204        if i == 0 {
205            break;
206        }
207        i -= 1;
208    }
209    wrapping_add_b(x, &neg_y)
210}
211
212pub const fn wrapping_sub(x: &U, y: &U) -> U {
213    U(wrapping_sub_b::<32>(&x.0, &y.0))
214}
215
216pub fn saturating_sub(x: &U, y: &U) -> U {
217    checked_sub(x, y).unwrap_or(U::ZERO)
218}
219
220#[cfg_attr(test, mutants::skip)]
221pub fn checked_sub(x: &U, y: &U) -> Option<U> {
222    if x < y {
223        None
224    } else {
225        Some(wrapping_sub(x, y))
226    }
227}
228
229pub const fn wrapping_mul_b<const C: usize>(x: &[u8; C], y: &[u8; C]) -> [u8; C] {
230    let mut r = [0u8; C];
231    let mut i = 0;
232    while i < C {
233        let mut c = 0u16;
234        let mut j = 0;
235        while j < C {
236            let i_r = i + j;
237            if i_r >= C {
238                break;
239            }
240            let r_idx = C - 1 - i_r;
241            let xi = x[C - 1 - i] as u16;
242            let yj = y[C - 1 - j] as u16;
243            let prod = xi * yj + r[r_idx] as u16 + c;
244            r[r_idx] = prod as u8;
245            c = prod >> 8;
246            j += 1;
247        }
248        if i + j < C {
249            let idx = 31 - (i + j);
250            r[idx] = r[idx] + c as u8;
251        }
252        i += 1;
253    }
254    r
255}
256
257pub const fn wrapping_mul(x: &U, y: &U) -> U {
258    U(wrapping_mul_b(&x.0, &y.0))
259}
260
261#[cfg_attr(test, mutants::skip)]
262pub fn checked_mul(x: &U, y: &U) -> Option<U> {
263    if x.is_zero() || y.is_zero() {
264        return Some(U::ZERO);
265    }
266    if x > &(U::MAX / *y) {
267        None
268    } else {
269        let z = x.mul_mod(y, &U::MAX);
270        if z.is_zero() { Some(U::MAX) } else { Some(z) }
271    }
272}
273
274pub fn saturating_mul(x: &U, y: &U) -> U {
275    checked_mul(x, y).unwrap_or(U::MAX)
276}
277
278impl Add for U {
279    type Output = U;
280
281    fn add(self, rhs: U) -> U {
282        cfg_if::cfg_if! {
283            if #[cfg(debug_assertions)] {
284                checked_add(&self, &rhs).expect("overflow when add")
285            } else {
286                wrapping_add(&self, &rhs)
287            }
288        }
289    }
290}
291
292impl Add for &U {
293    type Output = U;
294
295    fn add(self, rhs: &U) -> U {
296        cfg_if::cfg_if! {
297            if #[cfg(debug_assertions)] {
298                checked_add(self, rhs).expect("overflow when add")
299            } else {
300                wrapping_add(self, rhs)
301            }
302        }
303    }
304}
305
306impl Sub for U {
307    type Output = U;
308
309    fn sub(self, rhs: U) -> U {
310        cfg_if::cfg_if! {
311            if #[cfg(debug_assertions)] {
312                checked_sub(&self, &rhs).expect("overflow when sub")
313            } else {
314                wrapping_sub(&self, &rhs)
315            }
316        }
317    }
318}
319
320impl Sub for &U {
321    type Output = U;
322
323    fn sub(self, rhs: &U) -> U {
324        cfg_if::cfg_if! {
325            if #[cfg(debug_assertions)] {
326                checked_sub(self, rhs).expect("overflow when sub")
327            } else {
328                wrapping_sub(self, rhs)
329            }
330        }
331    }
332}
333
334impl Mul for U {
335    type Output = U;
336
337    fn mul(self, rhs: U) -> U {
338        cfg_if::cfg_if! {
339            if #[cfg(debug_assertions)] {
340                checked_mul(&self, &rhs).expect("overflow when mul")
341            } else {
342                wrapping_mul(&self, &rhs)
343            }
344        }
345    }
346}
347
348impl Mul for &U {
349    type Output = U;
350
351    fn mul(self, rhs: &U) -> U {
352        cfg_if::cfg_if! {
353            if #[cfg(debug_assertions)] {
354                checked_mul(self, rhs).expect("overflow when mul")
355            } else {
356                wrapping_mul(self, rhs)
357            }
358        }
359    }
360}
361
362impl Div for U {
363    type Output = U;
364
365    fn div(self, rhs: U) -> U {
366        cfg_if::cfg_if! {
367            if #[cfg(debug_assertions)] {
368                checked_div(&self, &rhs).expect("overflow when div")
369            } else {
370                wrapping_div(&self, &rhs)
371            }
372        }
373    }
374}
375
376impl Div for &U {
377    type Output = U;
378
379    fn div(self, rhs: &U) -> U {
380        cfg_if::cfg_if! {
381            if #[cfg(debug_assertions)] {
382                checked_div(self, rhs).expect("overflow when div")
383            } else {
384                wrapping_div(self, rhs)
385            }
386        }
387    }
388}
389
390impl Rem for U {
391    type Output = U;
392
393    fn rem(self, rhs: U) -> U {
394        modd(&self, &rhs)
395    }
396}
397
398impl Rem for &U {
399    type Output = U;
400
401    fn rem(self, rhs: &U) -> U {
402        modd(self, rhs)
403    }
404}
405
406impl Eq for U {}
407
408impl PartialOrd for U {
409    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
410        Some(self.cmp(other))
411    }
412}
413
414impl Ord for U {
415    fn cmp(&self, other: &Self) -> Ordering {
416        self.0.cmp(&other.0)
417    }
418}
419
420impl U {
421    pub const ZERO: Self = U([0u8; 32]);
422
423    pub const MAX: Self = U([u8::MAX; 32]);
424
425    pub const ONE: Self = U([
426        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
427        0, 1,
428    ]);
429
430    pub fn is_true(&self) -> bool {
431        self.0[31] == 1
432    }
433
434    pub fn is_zero(&self) -> bool {
435        *self == Self::ZERO
436    }
437
438    pub fn is_some(&self) -> bool {
439        !self.is_zero()
440    }
441
442    pub fn as_slice(&self) -> &[u8; 32] {
443        &self.0
444    }
445
446    pub fn checked_add(&self, y: &Self) -> Option<Self> {
447        checked_add(self, y)
448    }
449
450    pub fn checked_mul(&self, y: &Self) -> Option<Self> {
451        checked_mul(self, y)
452    }
453
454    pub fn checked_sub(&self, y: &Self) -> Option<Self> {
455        checked_sub(self, y)
456    }
457
458    pub fn checked_div(&self, y: &Self) -> Option<Self> {
459        checked_div(self, y)
460    }
461
462    pub fn wrapping_add(&self, y: &Self) -> U {
463        wrapping_add(self, y)
464    }
465
466    pub fn wrapping_sub(&self, y: &Self) -> U {
467        wrapping_sub(self, y)
468    }
469
470    pub fn wrapping_mul(&self, y: &Self) -> U {
471        wrapping_mul(self, y)
472    }
473
474    pub fn wrapping_div(&self, y: &Self) -> U {
475        wrapping_div(self, y)
476    }
477
478    pub fn saturating_add(&self, y: &Self) -> U {
479        saturating_add(self, y)
480    }
481
482    pub fn saturating_sub(&self, y: &Self) -> U {
483        saturating_sub(self, y)
484    }
485
486    pub fn saturating_mul(&self, y: &Self) -> U {
487        saturating_mul(self, y)
488    }
489
490    pub fn mul_mod(&self, y: &Self, z: &Self) -> Self {
491        let mut b = self.0;
492        unsafe { math_mul_mod(b.as_mut_ptr(), y.as_ptr(), z.as_ptr()) }
493        Self(b)
494    }
495
496    pub fn add_mod(&self, y: &Self, z: &Self) -> Self {
497        let mut b = self.0;
498        unsafe { math_add_mod(b.as_mut_ptr(), y.as_ptr(), z.as_ptr()) }
499        Self(b)
500    }
501
502    pub fn widening_mul(&self, y: &U) -> [u8; 64] {
503        let shift_128 = &U([
504            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
505            0, 0, 0,
506        ]);
507        let x_hi = self / shift_128;
508        let x_lo = self % shift_128;
509        let y_hi = y / shift_128;
510        let y_lo = y % shift_128;
511        let t0 = x_lo.mul_mod(&y_lo, &U::MAX);
512        let t1 = x_hi.mul_mod(&y_lo, &U::MAX);
513        let t2 = x_lo.mul_mod(&y_hi, &U::MAX);
514        let t3 = x_hi.mul_mod(&y_hi, &U::MAX);
515        let t0_hi = &t0 / shift_128;
516        let t0_lo = &t0 % shift_128;
517        let t1_hi = &t1 / shift_128;
518        let t1_lo = &t1 % shift_128;
519        let t2_hi = &t2 / shift_128;
520        let t2_lo = &t2 % shift_128;
521        let mid = (t0_hi + t1_lo) + t2_lo;
522        let mid_hi = &mid / shift_128;
523        let mid_lo = &mid % shift_128;
524        let mid_lo_shifted = mid_lo.mul_mod(shift_128, &U::MAX);
525        let out_low = t0_lo + mid_lo_shifted;
526        let out_high = t3 + t1_hi + t2_hi + mid_hi;
527        let mut o = [0u8; 64];
528        o[..32].copy_from_slice(&out_high.0);
529        o[32..].copy_from_slice(&out_low.0);
530        o
531    }
532
533    pub fn mul_div(&self, y: &U, denom: &U) -> Option<(U, bool)> {
534        // TODO: this most certainly could be more efficient!
535        if denom.is_zero() {
536            return None;
537        }
538        let x = self.widening_mul(y);
539        let mut d = [0u8; 64];
540        d[32..].copy_from_slice(&denom.0);
541        let (q, rem) = wrapping_div_quo_rem_b::<64>(&x, &d);
542        if q[..32] != [0u8; 32] {
543            return None;
544        }
545        let l: [u8; 32] = q[32..].try_into().unwrap();
546        let l = U::from(l);
547        let has_carry = rem[32..] != [0u8; 32];
548        Some((l, has_carry))
549    }
550
551    pub fn mul_div_round_up(&self, y: &U, denom_and_rem: &U) -> Option<U> {
552        let (x, y) = self.mul_div(y, denom_and_rem)?;
553        Some(if y { x + U::ONE } else { x })
554    }
555}
556
557#[cfg(feature = "std")]
558impl Display for U {
559    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
560        let mut result = vec![0u8];
561        for &byte in &self.0 {
562            let mut carry = byte as u32;
563            for digit in result.iter_mut() {
564                let temp = (*digit as u32) * 256 + carry;
565                *digit = (temp % 10) as u8;
566                carry = temp / 10;
567            }
568            while carry > 0 {
569                result.push((carry % 10) as u8);
570                carry /= 10;
571            }
572        }
573        if result.iter().all(|&d| d == 0) {
574            return write!(f, "0");
575        }
576        write!(
577            f,
578            "{}",
579            result
580                .iter()
581                .rev()
582                .skip_while(|&&d| d == 0)
583                .map(|&d| (d + b'0') as char)
584                .collect::<String>()
585        )
586    }
587}
588
589impl From<U> for [u8; 32] {
590    fn from(x: U) -> Self {
591        x.0
592    }
593}
594
595impl From<U> for bool {
596    fn from(x: U) -> Self {
597        x.0[31] == 1
598    }
599}
600
601impl From<&[u8; 32]> for &U {
602    fn from(x: &[u8; 32]) -> Self {
603        unsafe { &*(x as *const [u8; 32] as *const U) }
604    }
605}
606
607impl From<[u8; 32]> for U {
608    fn from(x: [u8; 32]) -> Self {
609        U(x)
610    }
611}
612
613impl Deref for U {
614    type Target = [u8; 32];
615
616    fn deref(&self) -> &Self::Target {
617        &self.0
618    }
619}
620
621impl DerefMut for U {
622    fn deref_mut(&mut self) -> &mut Self::Target {
623        &mut self.0
624    }
625}
626
627impl From<bool> for U {
628    fn from(x: bool) -> Self {
629        U::from(&[x as u8])
630    }
631}
632
633impl Zero for U {
634    fn zero() -> Self {
635        U::ZERO
636    }
637
638    fn is_zero(&self) -> bool {
639        self.0.iter().all(|&b| b == 0)
640    }
641}
642
643impl Default for U {
644    fn default() -> Self {
645        U::ZERO
646    }
647}
648
649impl One for U {
650    fn one() -> Self {
651        U::ONE
652    }
653}
654
655impl Index<usize> for U {
656    type Output = u8;
657
658    fn index(&self, index: usize) -> &Self::Output {
659        &self.0[index]
660    }
661}
662
663impl I {
664    fn is_neg(&self) -> bool {
665        self.0[0] & 0x80 != 0
666    }
667
668    pub fn is_zero(&self) -> bool {
669        *self == Self::ZERO
670    }
671
672    pub fn is_some(&self) -> bool {
673        !self.is_zero()
674    }
675
676    pub fn as_slice(&self) -> &[u8; 32] {
677        &self.0
678    }
679
680    fn neg(&self) -> Self {
681        let x = wrapping_add(&U(self.0.map(|b| !b)), &U::ONE);
682        I(x.0)
683    }
684
685    fn abs(self) -> U {
686        if self.is_neg() {
687            U(self.neg().0)
688        } else {
689            U(self.0)
690        }
691    }
692}
693
694macro_rules! from_slices {
695    ($($n:expr),+ $(,)?) => {
696        $(
697            impl From<&[u8; $n]> for U {
698                fn from(x: &[u8; $n]) -> Self {
699                    let mut b = [0u8; 32];
700                    b[32 - $n..].copy_from_slice(x);
701                    U(b)
702                }
703            }
704
705            impl From<[u8; $n]> for U {
706                fn from(x: [u8; $n]) -> Self {
707                    U::from(&x)
708                }
709            }
710
711            impl From<U> for [u8; $n] {
712                fn from(x: U) -> Self {
713                    unsafe { *(x.as_ptr().add(32 - $n) as *const [u8; $n]) }
714                }
715            }
716        )+
717    };
718}
719
720from_slices!(
721    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
722    27, 28, 29, 30, 31
723);
724
725impl From<&U> for Address {
726    fn from(x: &U) -> Self {
727        (*x).into()
728    }
729}
730
731macro_rules! from_ints {
732    ($($t:ty),+ $(,)?) => {
733        $(
734            impl From<$t> for U {
735                fn from(x: $t) -> Self {
736                    let mut b = [0u8; 32];
737                    b[32 - core::mem::size_of::<$t>()..].copy_from_slice(&x.to_be_bytes());
738                    U(b)
739                }
740            }
741
742            impl From<U> for $t {
743                fn from(x: U) -> Self {
744                    Self::from_be_bytes(x.into())
745                }
746            }
747        )+
748    };
749}
750
751from_ints! { u8, u16, u32, u64, u128, usize }
752
753impl From<I> for [u8; 32] {
754    fn from(x: I) -> Self {
755        x.0
756    }
757}
758
759impl From<[u8; 32]> for I {
760    fn from(x: [u8; 32]) -> Self {
761        I(x)
762    }
763}
764
765fn i_add(x: &I, y: &I) -> I {
766    I(wrapping_add(&U(x.0), &U(y.0)).0)
767}
768
769fn i_sub(x: &I, y: &I) -> I {
770    I(wrapping_sub(&U(x.0), &U(y.0)).0)
771}
772
773fn i_mul(x: &I, y: &I) -> I {
774    let result = wrapping_mul(&U(x.0), &U(y.0));
775    I(result.0)
776}
777
778fn i_div(x: &I, y: &I) -> I {
779    let r = wrapping_div(&x.abs(), &y.abs());
780    if x.is_neg() ^ y.is_neg() {
781        I(r.0).neg()
782    } else {
783        I(r.0)
784    }
785}
786
787fn i_rem(x: &I, y: &I) -> I {
788    let r = modd(&x.abs(), &y.abs());
789    if x.is_neg() { I(r.0).neg() } else { I(r.0) }
790}
791
792impl Add for I {
793    type Output = I;
794    fn add(self, rhs: I) -> I {
795        i_add(&self, &rhs)
796    }
797}
798
799impl Add for &I {
800    type Output = I;
801    fn add(self, rhs: &I) -> I {
802        i_add(self, rhs)
803    }
804}
805
806impl Sub for I {
807    type Output = I;
808    fn sub(self, rhs: I) -> I {
809        i_sub(&self, &rhs)
810    }
811}
812
813impl Sub for &I {
814    type Output = I;
815    fn sub(self, rhs: &I) -> I {
816        i_sub(self, rhs)
817    }
818}
819
820impl Mul for I {
821    type Output = I;
822    fn mul(self, rhs: I) -> I {
823        i_mul(&self, &rhs)
824    }
825}
826
827impl Mul for &I {
828    type Output = I;
829    fn mul(self, rhs: &I) -> I {
830        i_mul(self, rhs)
831    }
832}
833
834impl Div for I {
835    type Output = I;
836    fn div(self, rhs: I) -> I {
837        i_div(&self, &rhs)
838    }
839}
840
841impl Div for &I {
842    type Output = I;
843    fn div(self, rhs: &I) -> I {
844        i_div(self, rhs)
845    }
846}
847
848impl Rem for I {
849    type Output = I;
850    fn rem(self, rhs: I) -> I {
851        i_rem(&self, &rhs)
852    }
853}
854
855impl Eq for I {}
856
857impl PartialOrd for I {
858    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
859        Some(self.cmp(other))
860    }
861}
862
863impl Ord for I {
864    fn cmp(&self, other: &Self) -> Ordering {
865        let self_sign = self.0[0] & 0x80;
866        let other_sign = other.0[0] & 0x80;
867        match (self_sign, other_sign) {
868            (0, 0x80) => Ordering::Greater,
869            (0x80, 0) => Ordering::Less,
870            _ => self.0.cmp(&other.0),
871        }
872    }
873}
874
875impl Rem for &I {
876    type Output = I;
877    fn rem(self, rhs: &I) -> I {
878        i_rem(self, rhs)
879    }
880}
881
882impl I {
883    pub const ZERO: Self = I([0u8; 32]);
884
885    pub const ONE: Self = I([
886        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
887        0, 1,
888    ]);
889}
890
891impl Zero for I {
892    fn zero() -> Self {
893        I::ZERO
894    }
895    fn is_zero(&self) -> bool {
896        self.0.iter().all(|&b| b == 0)
897    }
898}
899
900impl Default for I {
901    fn default() -> Self {
902        I::ZERO
903    }
904}
905
906impl One for I {
907    fn one() -> Self {
908        I::ONE
909    }
910}
911
912#[test]
913fn test_is_zeroes() {
914    assert!(U::ZERO.is_zero());
915    assert!(U::ONE.is_some());
916    assert!(I::ZERO.is_zero());
917    assert!(I::ONE.is_some());
918}
919
920#[cfg(all(
921    test,
922    feature = "alloy-enabled",
923    feature = "proptest-enabled",
924    feature = "std",
925    not(target_arch = "wasm32")
926))]
927mod test {
928    use proptest::prelude::*;
929
930    use super::*;
931
932    fn u_from_u64(value: u64) -> U {
933        U::from(value)
934    }
935
936    proptest! {
937        #[test]
938        fn wrapping_div_b_zero_denominator_yields_zero(numerator in any::<[u8; 4]>()) {
939            let zero = [0u8; 4];
940            prop_assert_eq!(wrapping_div_quo_rem_b::<4>(&numerator, &zero).0, zero);
941        }
942
943        #[test]
944        fn wrapping_div_b_matches_integer_division(
945            numerator in any::<[u8; 4]>(),
946            denominator in any::<[u8; 4]>().prop_filter("denominator must be non-zero", |d| *d != [0u8; 4])
947        ) {
948            let numerator_u32 = u32::from_be_bytes(numerator);
949            let denominator_u32 = u32::from_be_bytes(denominator);
950            let expected = numerator_u32 / denominator_u32;
951            prop_assert_eq!(
952                wrapping_div_quo_rem_b::<4>(&numerator, &denominator).0,
953                expected.to_be_bytes()
954            );
955        }
956
957        #[test]
958        fn wrapping_mod_b_matches_integer_modulo(
959            numerator in any::<[u8; 4]>(),
960            denominator in any::<[u8; 4]>().prop_filter("denominator must be non-zero", |d| *d != [0u8; 4])
961        ) {
962            let numerator_u32 = u32::from_be_bytes(numerator);
963            let denominator_u32 = u32::from_be_bytes(denominator);
964            let expected = numerator_u32 % denominator_u32;
965            prop_assert_eq!(
966                wrapping_div_quo_rem_b::<4>(&numerator, &denominator).1,
967                expected.to_be_bytes()
968            );
969        }
970
971        #[test]
972        fn wrapping_add_b_handles_carry(lhs in any::<[u8; 4]>(), rhs in any::<[u8; 4]>()) {
973            let lhs_u32 = u32::from_be_bytes(lhs);
974            let rhs_u32 = u32::from_be_bytes(rhs);
975            let expected = lhs_u32.wrapping_add(rhs_u32);
976            prop_assert_eq!(wrapping_add_b::<4>(&lhs, &rhs), expected.to_be_bytes());
977        }
978
979        #[test]
980        fn wrapping_sub_b_handles_borrow(lhs in any::<[u8; 4]>(), rhs in any::<[u8; 4]>()) {
981            let lhs_u32 = u32::from_be_bytes(lhs);
982            let rhs_u32 = u32::from_be_bytes(rhs);
983            let expected = lhs_u32.wrapping_sub(rhs_u32);
984            prop_assert_eq!(wrapping_sub_b::<4>(&lhs, &rhs), expected.to_be_bytes());
985        }
986
987        #[test]
988        fn wrapping_mul_b_matches_wrapping_arithmetic(lhs in any::<[u8; 32]>(), rhs in any::<[u8; 32]>()) {
989            let lhs_u = U::from(lhs);
990            let rhs_u = U::from(rhs);
991            let expected = lhs_u.wrapping_mul(&rhs_u);
992            prop_assert_eq!(wrapping_mul_b::<32>(&lhs, &rhs), expected.0);
993        }
994
995        #[test]
996        fn const_wrapping_div_agrees_with_wrapping_div_b(
997            numerator in any::<[u8; 32]>(),
998            denominator in any::<[u8; 32]>().prop_filter("denominator must be non-zero", |d| *d != [0u8; 32])
999        ) {
1000            let numerator_u = U::from(numerator);
1001            let denominator_u = U::from(denominator);
1002            prop_assert_eq!(
1003                const_wrapping_div(&numerator_u, &denominator_u).0,
1004                wrapping_div_quo_rem_b::<32>(&numerator, &denominator).0
1005            );
1006        }
1007
1008        #[test]
1009        fn u_predicates_track_zero_and_true(bytes in any::<[u8; 32]>()) {
1010            let value = U::from(bytes);
1011            let is_zero = bytes.iter().all(|&b| b == 0);
1012            prop_assert_eq!(value.is_zero(), is_zero);
1013            prop_assert_eq!(value.is_some(), !is_zero);
1014            prop_assert_eq!(value.is_true(), bytes[31] == 1);
1015        }
1016
1017        #[test]
1018        fn mul_div_returns_expected_quotient_and_carry(
1019            lhs in any::<u64>(),
1020            rhs in any::<u64>(),
1021            denom in any::<u64>().prop_filter("denominator must be non-zero", |d| *d != 0)
1022        ) {
1023            let lhs_u = u_from_u64(lhs);
1024            let rhs_u = u_from_u64(rhs);
1025            let denom_u = u_from_u64(denom);
1026            let (q, carry) = lhs_u.mul_div(&rhs_u, &denom_u).expect("division should succeed");
1027
1028            let product = (lhs as u128) * (rhs as u128);
1029            let denom_u128 = denom as u128;
1030            let expected_q = product / denom_u128;
1031            let expected_rem = product % denom_u128;
1032
1033            prop_assert_eq!(u128::from(q), expected_q);
1034            prop_assert_eq!(carry, expected_rem != 0);
1035        }
1036
1037        #[test]
1038        fn mul_div_round_up_accounts_for_carry(
1039            lhs in any::<u64>(),
1040            rhs in any::<u64>(),
1041            denom in any::<u64>().prop_filter("denominator must be non-zero", |d| *d != 0)
1042        ) {
1043            let lhs_u = u_from_u64(lhs);
1044            let rhs_u = u_from_u64(rhs);
1045            let denom_u = u_from_u64(denom);
1046            let rounded = lhs_u
1047                .mul_div_round_up(&rhs_u, &denom_u)
1048                .expect("rounding should succeed");
1049
1050            let product = (lhs as u128) * (rhs as u128);
1051            let denom_u128 = denom as u128;
1052            let expected = if product % denom_u128 == 0 {
1053                product / denom_u128
1054            } else {
1055                (product / denom_u128) + 1
1056            };
1057
1058            prop_assert_eq!(u128::from(rounded), expected);
1059        }
1060
1061        #[test]
1062        fn test_u_is_zero(x in any::<[u8; 32]>()) {
1063            let x = U::from(x);
1064            let ex = U256::from_be_bytes(x.0);
1065            assert_eq!(ex.is_zero(), x.is_zero());
1066        }
1067
1068        #[test]
1069        fn test_u_div(x in any::<U>(), y in any::<U>()) {
1070            let ex = U256::from_be_bytes(x.0);
1071            let ey = U256::from_be_bytes(y.0);
1072            assert_eq!((ex.wrapping_div(ey)).to_be_bytes(), x.wrapping_div(&y).0);
1073        }
1074
1075        #[test]
1076        fn test_u_mul(x in any::<U>(), y in any::<U>()) {
1077            let ex = U256::from_be_bytes(x.0);
1078            let ey = U256::from_be_bytes(y.0);
1079            assert_eq!((ex.wrapping_mul(ey)).to_be_bytes(), wrapping_mul(&x,  &y).0);
1080        }
1081
1082        #[test]
1083        fn test_u_mod(x in any::<U>(), y in any::<U>()) {
1084            let ex = U256::from_be_bytes(x.0);
1085            let ey = U256::from_be_bytes(y.0);
1086            assert_eq!((ex % ey).to_be_bytes(), (x % y).0);
1087        }
1088
1089        #[test]
1090        fn test_u_add(x in any::<U>(), y in any::<U>()) {
1091            let ex = U256::from_be_bytes(x.0);
1092            let ey = U256::from_be_bytes(y.0);
1093            let e = U::from(ex.wrapping_add(ey).to_be_bytes::<32>());
1094            assert_eq!(e, x.wrapping_add(&y), "{e} != {}", x + y);
1095        }
1096
1097        #[test]
1098        fn test_u_sub(x in any::<U>(), y in any::<U>()) {
1099            let ex = U256::from_be_bytes(x.0);
1100            let ey = U256::from_be_bytes(y.0);
1101            assert_eq!((ex.wrapping_sub(ey)).to_be_bytes(), x.wrapping_sub(&y).0);
1102        }
1103
1104        #[test]
1105        fn test_u_cmp(x in any::<U>(), y in any::<U>()) {
1106            let ex = U256::from_be_bytes(x.0);
1107            let ey = U256::from_be_bytes(y.0);
1108            assert_eq!(ex.cmp(&ey), x.cmp(&y));
1109        }
1110
1111        #[test]
1112        #[cfg(feature = "alloc")]
1113        fn test_u_str(x in any::<U>()) {
1114            assert_eq!(U256::from_be_bytes(x.0).to_string(), x.to_string());
1115        }
1116
1117        #[test]
1118        fn test_i_is_zero(x in any::<U>()) {
1119            let ex = I256::from_be_bytes(x.0);
1120            assert_eq!(ex.is_zero(), x.is_zero());
1121        }
1122
1123        #[test]
1124        fn test_i_div(x in any::<I>(), y in any::<I>()) {
1125            let ex = I256::from_be_bytes(x.0);
1126            let ey = I256::from_be_bytes(y.0);
1127            assert_eq!((ex / ey).to_be_bytes(), (x / y).0);
1128        }
1129
1130        #[test]
1131        fn test_i_mul(x in any::<I>(), y in any::<I>()) {
1132            let ex = I256::from_be_bytes(x.0);
1133            let ey = I256::from_be_bytes(y.0);
1134            assert_eq!((ex.wrapping_mul(ey)).to_be_bytes(), (x * y).0);
1135        }
1136
1137        #[test]
1138        fn test_i_mod(x in any::<I>(), y in any::<I>()) {
1139            let ex = I256::from_be_bytes(x.0);
1140            let ey = I256::from_be_bytes(y.0);
1141            assert_eq!((ex % ey).to_be_bytes(), (x % y).0);
1142        }
1143
1144        #[test]
1145        fn test_i_add(x in any::<I>(), y in any::<I>()) {
1146            let ex = I256::from_be_bytes(x.0);
1147            let ey = I256::from_be_bytes(y.0);
1148            assert_eq!((ex.wrapping_add(ey)).to_be_bytes(), (x + y).0);
1149        }
1150
1151        #[test]
1152        fn test_i_sub(x in any::<I>(), y in any::<I>()) {
1153            let ex = I256::from_be_bytes(x.0);
1154            let ey = I256::from_be_bytes(y.0);
1155            assert_eq!((ex.wrapping_sub(ey)).to_be_bytes(), (x - y).0);
1156        }
1157
1158        #[test]
1159        fn test_i_cmp(x in any::<I>(), y in any::<I>()) {
1160            let ex = I256::from_be_bytes(x.0);
1161            let ey = I256::from_be_bytes(y.0);
1162            assert_eq!(ex.cmp(&ey), x.cmp(&y));
1163        }
1164
1165        #[test]
1166        fn test_u_u8(x in any::<u8>()) {
1167            let mut b = [0u8; 32];
1168            b[32-std::mem::size_of::<u8>()..].copy_from_slice(&x.to_be_bytes());
1169            assert_eq!(&U256::from_be_bytes(b).to_be_bytes(), U::from(x).as_slice());
1170        }
1171
1172        #[test]
1173        fn test_u_u16(x in any::<u16>()) {
1174            let mut b = [0u8; 32];
1175            b[32-std::mem::size_of::<u16>()..].copy_from_slice(&x.to_be_bytes());
1176            assert_eq!(&U256::from_be_bytes(b).to_be_bytes(), U::from(x).as_slice());
1177        }
1178
1179        #[test]
1180        fn test_u_u32(x in any::<u32>()) {
1181            let mut b = [0u8; 32];
1182            b[32-std::mem::size_of::<u32>()..].copy_from_slice(&x.to_be_bytes());
1183            assert_eq!(&U256::from_be_bytes(b).to_be_bytes(), U::from(x).as_slice());
1184        }
1185
1186        #[test]
1187        fn test_u_u64(x in any::<u64>()) {
1188            let mut b = [0u8; 32];
1189            b[32-std::mem::size_of::<u64>()..].copy_from_slice(&x.to_be_bytes());
1190            assert_eq!(&U256::from_be_bytes(b).to_be_bytes(), U::from(x).as_slice());
1191        }
1192
1193        #[test]
1194        fn test_u_u128(x in any::<u128>()) {
1195            let mut b = [0u8; 32];
1196            b[32-std::mem::size_of::<u128>()..].copy_from_slice(&x.to_be_bytes());
1197            assert_eq!(&U256::from_be_bytes(b).to_be_bytes(), U::from(x).as_slice());
1198        }
1199
1200        #[test]
1201        fn test_to_and_from_addrs(x in any::<Address>()) {
1202            let y: Address = U::from(x).into();
1203            assert_eq!(x, y)
1204        }
1205
1206        #[test]
1207        fn test_u_conv_to_and_from_u8(x in any::<u8>()) {
1208            assert_eq!(x.wrapping_add(1), U::from(x).wrapping_add(&U::ONE).into());
1209        }
1210    }
1211}
bobcat_maths/lib.rs

bobcat_maths/
lib.rs
