unityrs_core/version/
packed.rs1use std::cmp::Ordering;
5use std::fmt;
6
7#[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 Small(u128),
26 Big(Box<[u64]>),
29}
30
31impl Packed {
32 #[must_use]
34 pub const fn from_u128(v: u128) -> Self {
35 Self(Repr::Small(v))
36 }
37
38 #[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 #[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 #[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 #[must_use]
77 pub fn to_limbs(&self) -> Vec<u64> {
78 match &self.0 {
79 Repr::Small(v) => {
80 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 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 #[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
125pub(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 (Repr::Small(_), Repr::Big(_)) => Ordering::Less,
137 (Repr::Big(_), Repr::Small(_)) => Ordering::Greater,
138 (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 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
160 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 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 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 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}