ab_core_primitives/sectors/
nano_u256.rs

1use core::ops::Rem;
2
3// Minimal `u256` implementation that is needed for sectors and optimized for producing the
4// remainder of division by `u64`
5#[derive(Clone, Copy, PartialEq, Eq)]
6pub(super) struct NanoU256 {
7    lo: u128,
8    hi: u128,
9}
10
11impl NanoU256 {
12    #[inline(always)]
13    pub(super) const fn from_le_bytes(bytes: [u8; 32]) -> Self {
14        let lo = u128::from_le_bytes([
15            bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7],
16            bytes[8], bytes[9], bytes[10], bytes[11], bytes[12], bytes[13], bytes[14], bytes[15],
17        ]);
18        let hi = u128::from_le_bytes([
19            bytes[16], bytes[17], bytes[18], bytes[19], bytes[20], bytes[21], bytes[22], bytes[23],
20            bytes[24], bytes[25], bytes[26], bytes[27], bytes[28], bytes[29], bytes[30], bytes[31],
21        ]);
22
23        Self { lo, hi }
24    }
25}
26
27impl Rem<u64> for NanoU256 {
28    type Output = u64;
29
30    #[inline(always)]
31    fn rem(self, rhs: u64) -> u64 {
32        if rhs == 0 {
33            panic!("division by zero");
34        }
35
36        let rhs = rhs as u128;
37
38        // If `hi` is 0, we can directly compute the remainder from `lo`
39        if self.hi == 0 {
40            return (self.lo % rhs) as u64;
41        }
42
43        // Process the high 128 bits first
44        let hi_rem = self.hi % rhs;
45
46        // Combine a high remainder with low 128 bits
47        // hi_rem * 2^128 + lo
48        let combined = (hi_rem << 64) | (self.lo >> 64);
49        let combined_rem = combined % rhs;
50
51        // Process the remaining low 64 bits
52        let low = self.lo & 0xffffffffffffffff;
53        let final_rem = ((combined_rem << 64) | low) % rhs;
54
55        final_rem as u64
56    }
57}
58
59#[cfg(test)]
60mod tests {
61    use super::NanoU256;
62    use crate::hashes::blake3_hash;
63
64    #[test]
65    fn basic() {
66        let input = NanoU256::from_le_bytes(*blake3_hash(&[1, 2, 3]));
67        let vectors = [
68            (749265838, 96295755),
69            (4294967296, 468481969),
70            (9588891412677391755, 5746309610232603432),
71            (3050220159935725727, 1594047135082657684),
72            (9163698234407261922, 137811727784537481),
73            (8110910621974504463, 772103028532207994),
74            (10066003301207900840, 3710011681387425537),
75            (6326525170861459176, 4054803448573033593),
76            (16971852880362673803, 14857223653279674036),
77            (5479364763909636908, 2217175580314974257),
78            (14850578606861073142, 5959274540802056661),
79            (6477421758110557520, 2913281736886846177),
80            (u64::MAX, 11641615165612301982),
81        ];
82
83        for (n, rem) in vectors {
84            assert_eq!(input % n, rem);
85        }
86    }
87
88    #[test]
89    #[should_panic]
90    fn no_division_by_zero() {
91        let input = NanoU256::from_le_bytes(*blake3_hash(&[1, 2, 3]));
92        let _ = input % 0;
93    }
94}
ab_core_primitives/sectors/nano_u256.rs

ab_core_primitives/sectors/
nano_u256.rs
