Skip to main content

unityrs_core/version/
packed.rs

1//! [`Packed`]: a packed version, an unbounded integer with Python's `int`
2//! order, equality and hash.
3
4use std::cmp::Ordering;
5use std::fmt;
6
7/// The packed integer, exactly. Most versions fit `u128`; a major of 2^80 or
8/// more does not, and the canonical dump writes the exact integer. Ordered,
9/// compared and hashed as Python's `int` (implemented by the scaffold).
10///
11/// The representation is private and always canonical: a value below 2^128
12/// is held as a `u128`, and a larger one as little-endian limbs with a
13/// non-zero top limb. So [`Packed::from_limbs`] of a value written with
14/// leading zero limbs (a 4,300-digit group of leading zeros, sized from its
15/// digit count) equals, hashes and orders as the same value from
16/// [`Packed::from_u128`].
17#[derive(Clone, Debug, PartialEq, Eq, Hash)]
18pub struct Packed(Repr);
19
20const _: () = crate::send_sync::<Packed>();
21
22#[derive(Clone, Debug, PartialEq, Eq, Hash)]
23enum Repr {
24    /// Below 2^128.
25    Small(u128),
26    /// 2^128 or more: little-endian `u64` limbs, more than two, the last
27    /// one non-zero.
28    Big(Box<[u64]>),
29}
30
31impl Packed {
32    /// The value `v`.
33    #[must_use]
34    pub const fn from_u128(v: u128) -> Self {
35        Self(Repr::Small(v))
36    }
37
38    /// The value of little-endian `u64` limbs, any number of them, leading
39    /// (most significant) zero limbs included.
40    #[must_use]
41    pub fn from_limbs(limbs: &[u64]) -> Self {
42        let limbs = limbs.get(..significant(limbs)).unwrap_or_default();
43        match limbs {
44            [] => Self::from_u128(0),
45            [lo] => Self::from_u128(u128::from(*lo)),
46            [lo, hi] => Self::from_u128(u128::from(*lo) | (u128::from(*hi) << 64)),
47            _ => Self(Repr::Big(limbs.into())),
48        }
49    }
50
51    /// The value, when it is below 2^128.
52    #[must_use]
53    pub fn as_u128(&self) -> Option<u128> {
54        match &self.0 {
55            Repr::Small(v) => Some(*v),
56            Repr::Big(_) => None,
57        }
58    }
59
60    /// The limbs of a value of 2^128 or more, borrowed: little-endian, the
61    /// last one non-zero, at most [`super::MAX_LIMBS`] for a version a
62    /// parse packed. `None` below 2^128, where [`Self::as_u128`] is the
63    /// value. Unlike [`Self::to_limbs`] it copies nothing, so a writer of
64    /// an input's version needs no heap for it
65    /// (`unityrs_dump::json::write_packed`).
66    #[must_use]
67    pub fn big_limbs(&self) -> Option<&[u64]> {
68        match &self.0 {
69            Repr::Small(_) => None,
70            Repr::Big(limbs) => Some(limbs),
71        }
72    }
73
74    /// The value as little-endian `u64` limbs, without leading zero limbs
75    /// (empty for 0).
76    #[must_use]
77    pub fn to_limbs(&self) -> Vec<u64> {
78        match &self.0 {
79            Repr::Small(v) => {
80                // Both halves of a u128, the high one first cut away when zero.
81                let lo = u64::try_from(v & u128::from(u64::MAX)).unwrap_or(u64::MAX);
82                let hi = u64::try_from(v >> 64).unwrap_or(u64::MAX);
83                match (lo, hi) {
84                    (0, 0) => Vec::new(),
85                    (lo, 0) => vec![lo],
86                    (lo, hi) => vec![lo, hi],
87                }
88            }
89            Repr::Big(limbs) => limbs.to_vec(),
90        }
91    }
92
93    /// `(self >> shift) & ((1 << width) - 1)`, for `width` up to 64.
94    pub(super) fn bits(&self, shift: u32, width: u32) -> u64 {
95        let mask = if width >= 64 {
96            u64::MAX
97        } else {
98            (1u64 << width) - 1
99        };
100        match &self.0 {
101            Repr::Small(v) => {
102                u64::try_from(v.checked_shr(shift).unwrap_or(0) & u128::from(mask)).unwrap_or(0)
103            }
104            Repr::Big(limbs) => {
105                let word = usize::try_from(shift / 64).unwrap_or(usize::MAX);
106                let bit = shift % 64;
107                let lo = limbs.get(word).copied().unwrap_or(0);
108                let hi = limbs.get(word.saturating_add(1)).copied().unwrap_or(0);
109                let v = (u128::from(hi) << 64 | u128::from(lo)) >> bit;
110                u64::try_from(v & u128::from(mask)).unwrap_or(0)
111            }
112        }
113    }
114
115    /// The heap bytes the value owns (0 below 2^128).
116    #[must_use]
117    pub fn heap_bytes(&self) -> usize {
118        match &self.0 {
119            Repr::Small(_) => 0,
120            Repr::Big(limbs) => limbs.len() * 8,
121        }
122    }
123}
124
125/// The number of limbs up to and including the most significant non-zero
126/// one: what [`Packed::from_limbs`] keeps.
127pub(super) fn significant(limbs: &[u64]) -> usize {
128    limbs.iter().rposition(|l| *l != 0).map_or(0, |i| i + 1)
129}
130
131impl Ord for Packed {
132    fn cmp(&self, other: &Self) -> Ordering {
133        match (&self.0, &other.0) {
134            (Repr::Small(a), Repr::Small(b)) => a.cmp(b),
135            // Canonical: every `Big` is at least 2^128, above every `Small`.
136            (Repr::Small(_), Repr::Big(_)) => Ordering::Less,
137            (Repr::Big(_), Repr::Small(_)) => Ordering::Greater,
138            // Limbs are little-endian with a non-zero last limb: more limbs is
139            // larger, else compare from the most significant limb down.
140            (Repr::Big(a), Repr::Big(b)) => a
141                .len()
142                .cmp(&b.len())
143                .then_with(|| a.iter().rev().cmp(b.iter().rev())),
144        }
145    }
146}
147
148impl PartialOrd for Packed {
149    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
150        Some(self.cmp(other))
151    }
152}
153
154impl fmt::Display for Packed {
155    /// The exact decimal integer. Past 2^128 it costs a pass over the
156    /// limbs for each 19 digits, uncounted: the dump writes a packed
157    /// version with its own conversion, which counts each pass as the
158    /// input's work (`unityrs_dump::json::write_packed`).
159    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
160        // Repeated division by 10^19, least significant chunk first.
161        const CHUNK: u64 = 10_000_000_000_000_000_000;
162        let limbs = match &self.0 {
163            Repr::Small(v) => return write!(f, "{v}"),
164            Repr::Big(limbs) => limbs,
165        };
166        let mut n: Vec<u64> = limbs.to_vec();
167        let mut chunks: Vec<u64> = Vec::new();
168        while n.iter().any(|l| *l != 0) {
169            let mut rem: u128 = 0;
170            for l in n.iter_mut().rev() {
171                let cur = (rem << 64) | u128::from(*l);
172                *l = u64::try_from(cur / u128::from(CHUNK)).unwrap_or(u64::MAX);
173                rem = cur % u128::from(CHUNK);
174            }
175            chunks.push(u64::try_from(rem).unwrap_or(0));
176            while n.last() == Some(&0) {
177                n.pop();
178            }
179        }
180        let mut it = chunks.iter().rev();
181        if let Some(top) = it.next() {
182            write!(f, "{top}")?;
183        }
184        for c in it {
185            write!(f, "{c:019}")?;
186        }
187        Ok(())
188    }
189}
190
191#[cfg(test)]
192mod tests {
193    use super::Packed;
194
195    #[test]
196    fn a_value_has_one_form_whatever_its_leading_zeros() {
197        use std::collections::hash_map::DefaultHasher;
198        use std::hash::{Hash, Hasher};
199        let hash = |p: &Packed| {
200            let mut h = DefaultHasher::new();
201            p.hash(&mut h);
202            h.finish()
203        };
204        // "000…01" sized from its 4,300 digits: 224 limbs, value 1.
205        let mut limbs = vec![0_u64; 224];
206        limbs[0] = 1;
207        let padded = Packed::from_limbs(&limbs);
208        let one = Packed::from_u128(1);
209        assert_eq!(padded, one);
210        assert_eq!(hash(&padded), hash(&one));
211        assert_eq!(padded.cmp(&one), std::cmp::Ordering::Equal);
212        assert!(padded < Packed::from_u128(2));
213        // Two limbs fit u128; a zero top limb is dropped.
214        assert_eq!(
215            Packed::from_limbs(&[5, 7, 0]),
216            Packed::from_u128(5 | (7 << 64))
217        );
218        assert_eq!(Packed::from_limbs(&[]), Packed::from_u128(0));
219        assert_eq!(Packed::from_limbs(&[0, 0, 1]).to_limbs(), [0, 0, 1]);
220        assert_eq!(
221            Packed::from_u128(u128::MAX).to_limbs(),
222            [u64::MAX, u64::MAX]
223        );
224        assert_eq!(Packed::from_u128(0).to_limbs(), Vec::<u64>::new());
225        // Borrowed: a big value's own limbs, none below 2^128.
226        let big = Packed::from_limbs(&[1, 2, 3, 0]);
227        assert_eq!(big.big_limbs(), Some(&[1, 2, 3][..]));
228        assert_eq!(Packed::from_u128(u128::MAX).big_limbs(), None);
229    }
230
231    #[test]
232    fn big_packed_values_order_by_magnitude() {
233        let small = Packed::from_u128(u128::MAX);
234        let big_lo = Packed::from_limbs(&[u64::MAX, 0, 1]);
235        let big_hi = Packed::from_limbs(&[0, 1, 1]);
236        let bigger = Packed::from_limbs(&[0, 0, 0, 1]);
237        assert!(small < big_lo);
238        assert!(big_lo < big_hi, "compared from the most significant limb");
239        assert!(big_hi < bigger);
240        assert_eq!(big_lo.as_u128(), None);
241    }
242}