big_int/loose.rs
1//! Loosely packed big int implementations.
2//!
3//! ```
4//! use big_int::prelude::*;
5//!
6//! let mut a: Loose<10> = 13.into();
7//! a *= 500.into();
8//! assert_eq!(a, 6500.into());
9//!
10//! unsafe {
11//! a.shr_assign_inner(2);
12//! }
13//! a += 17.into();
14//! assert_eq!(a, 82.into());
15//! ```
16
17use big_int_proc::BigIntTraits;
18
19use crate::prelude::*;
20use std::{collections::VecDeque, vec};
21
22macro_rules! loose_definition {
23 (
24 $data_type:ty;
25
26 $(#[$denormal_meta:meta])*
27 $denormal_name:ident;
28
29 $(#[$type_meta:meta])*
30 $name:ident;
31
32 $(#[$builder_meta:meta])*
33 $builder_name:ident;
34 ) => {
35
36 $(#[$denormal_meta])*
37 pub type $denormal_name<const BASE: usize> = Denormal<BASE, $name<BASE>>;
38
39 $(#[$type_meta])*
40 #[derive(Clone, Debug, BigIntTraits)]
41 pub struct $name<const BASE: usize> {
42 sign: Sign,
43 digits: Vec<$data_type>,
44 }
45
46 impl<const BASE: usize> $name<BASE> {
47 /// Create a new loose int directly from a `Vec` of individual digits.
48 ///
49 /// Ensure the resulting int is properly normalized, and that no digits are greater than or
50 /// equal to the base, to preserve soundness.
51 ///
52 /// To construct a negative int from raw parts, simply apply the negation
53 /// operator (`-`) afterwards.
54 ///
55 /// ```
56 /// use big_int::prelude::*;
57 ///
58 /// assert_eq!(
59 /// -unsafe { Loose::<10>::from_raw_parts(vec![1, 5]) },
60 /// (-15).into()
61 /// );
62 /// ```
63 pub unsafe fn from_raw_parts(digits: Vec<Digit>) -> Self {
64 let sign = Positive;
65 let digits = digits.into_iter().map(|digit| digit as $data_type).collect();
66 $name { sign, digits }
67 }
68 }
69
70 impl<const BASE: usize> BigInt<BASE> for $name<BASE> {
71 type Builder = $builder_name<{ BASE }>;
72 type Denormal = Denormal<BASE, Self>;
73
74 fn len(&self) -> usize {
75 self.digits.len()
76 }
77
78 fn get_digit(&self, digit: usize) -> Option<Digit> {
79 self.digits.get(digit).map(|digit| *digit as Digit)
80 }
81
82 fn set_digit(&mut self, digit: usize, value: Digit) {
83 if let Some(digit) = self.digits.get_mut(digit) {
84 *digit = value as $data_type;
85 }
86 }
87
88 fn zero() -> Self {
89 let sign = Positive;
90 let digits = vec![0];
91 $name { sign, digits }
92 }
93
94 fn with_sign(self, sign: Sign) -> Self {
95 $name { sign, ..self }
96 }
97
98 /// Return a normalized version of the int. Remove trailing zeros, and disable the parity flag
99 /// if the resulting number is zero.
100 ///
101 /// ```
102 /// use big_int::prelude::*;
103 ///
104 /// let n = unsafe { Loose::<10>::from_raw_parts(vec![0, 0, 8, 3]) };
105 /// assert_eq!(n.normalized(), 83.into());
106 /// ```
107 fn normalized(self) -> Self {
108 match self.digits.iter().position(|digit| *digit != 0) {
109 None => Self::zero(),
110 Some(pos @ 1..) => $name {
111 digits: self.digits[pos..].to_vec(),
112 ..self
113 },
114 _ => self,
115 }
116 }
117
118 fn sign(&self) -> Sign {
119 self.sign
120 }
121
122 fn set_sign(&mut self, sign: Sign) {
123 self.sign = sign;
124 }
125
126 fn push_back(&mut self, digit: crate::Digit) {
127 self.digits.push(digit as $data_type);
128 }
129
130 unsafe fn push_front(&mut self, digit: crate::Digit) {
131 self.digits.insert(0, digit as $data_type);
132 }
133
134 unsafe fn shr_assign_inner(&mut self, amount: usize) {
135 self.digits =
136 self.digits[..self.digits.len().checked_sub(amount).unwrap_or_default()].to_vec();
137 }
138
139 unsafe fn shl_assign_inner(&mut self, amount: usize) {
140 self.digits.extend(vec![0; amount]);
141 }
142
143 unsafe fn pop_back(&mut self) -> Option<Digit> {
144 self.digits.pop().map(|digit| digit as Digit)
145 }
146
147 unsafe fn pop_front(&mut self) -> Option<Digit> {
148 (!self.digits.is_empty()).then(|| self.digits.remove(0) as Digit)
149 }
150 }
151
152 $(#[$builder_meta])*
153 #[derive(Debug)]
154 pub struct $builder_name<const BASE: usize> {
155 sign: Sign,
156 digits: VecDeque<$data_type>,
157 }
158
159 impl<const BASE: usize> BigIntBuilder<BASE> for $builder_name<BASE> {
160 fn new() -> Self {
161 $builder_name {
162 sign: Positive,
163 digits: VecDeque::new(),
164 }
165 }
166
167 fn push_front(&mut self, digit: Digit) {
168 self.digits.push_front(digit as $data_type);
169 }
170
171 fn push_back(&mut self, digit: Digit) {
172 self.digits.push_back(digit as $data_type);
173 }
174
175 fn with_sign(self, sign: Sign) -> Self {
176 $builder_name { sign, ..self }
177 }
178
179 fn is_empty(&self) -> bool {
180 self.digits.is_empty()
181 }
182 }
183
184 impl<const BASE: usize> From<$builder_name<BASE>> for Denormal<BASE, $name<BASE>> {
185 fn from(value: $builder_name<BASE>) -> Self {
186 let sign = value.sign;
187 let digits = value.digits.into();
188 Denormal($name { sign, digits })
189 }
190 }
191
192 impl<const BASE: usize> From<$builder_name<BASE>> for $name<BASE> {
193 fn from(value: $builder_name<BASE>) -> Self {
194 let denormal: <Self as BigInt<BASE>>::Denormal = value.into();
195 denormal.unwrap()
196 }
197 }
198 };
199}
200
201loose_definition!(
202 u8;
203
204 /// Shorthand to represent a denormalized `LooseBytes` int.
205 DenormalLooseBytes;
206
207 /// A loosely-packed arbitrary base big int implementation.
208 /// Supports any base from 2-u8::MAX.
209 ///
210 /// Each digit requires 1 byte of storage, making this a slightly space-inefficient
211 /// implementation for smaller bases. However, the lack of additional complexity
212 /// improves runtime efficiency over the tightly-packed implementation.
213 ///
214 /// ```
215 /// use big_int::prelude::*;
216 ///
217 /// let a: LooseBytes<10> = 593.into();
218 /// let b = a * 96.into();
219 /// assert_eq!(b, 56928.into());
220 /// ```
221 LooseBytes;
222
223 /// A builder for a `LooseBytes` int.
224 ///
225 /// You're most likely better off using one of the `From` implementations
226 /// as opposed to directly building your int via a builder.
227 ///
228 /// ```
229 /// use big_int::prelude::*;
230 ///
231 /// let mut a = LooseBytesBuilder::<10>::new();
232 /// a.push_back(5);
233 /// a.push_back(3);
234 /// a.push_back(0);
235 /// a.push_back(4);
236 /// let a: LooseBytes<10> = a.into();
237 /// assert_eq!(a, 5304.into());
238 /// ```
239 LooseBytesBuilder;
240);
241
242loose_definition!(
243 u16;
244
245 /// Shorthand to represent a denormalized `LooseShorts` int.
246 DenormalLooseShorts;
247
248 /// A loosely-packed arbitrary base big int implementation.
249 /// Supports any base from 2-u16::MAX.
250 ///
251 /// Each digit requires 2 bytes of storage, making this a somewhat space-inefficient
252 /// implementation for smaller bases. However, the lack of additional complexity
253 /// improves runtime efficiency over the tightly-packed implementation.
254 ///
255 /// ```
256 /// use big_int::prelude::*;
257 ///
258 /// let a: LooseShorts<10> = 593.into();
259 /// let b = a * 96.into();
260 /// assert_eq!(b, 56928.into());
261 /// ```
262 LooseShorts;
263
264 /// A builder for a `LooseShorts` int.
265 ///
266 /// You're most likely better off using one of the `From` implementations
267 /// as opposed to directly building your int via a builder.
268 ///
269 /// ```
270 /// use big_int::prelude::*;
271 ///
272 /// let mut a = LooseShortsBuilder::<10>::new();
273 /// a.push_back(5);
274 /// a.push_back(3);
275 /// a.push_back(0);
276 /// a.push_back(4);
277 /// let a: LooseShorts<10> = a.into();
278 /// assert_eq!(a, 5304.into());
279 /// ```
280 LooseShortsBuilder;
281);
282
283loose_definition!(
284 u32;
285
286 /// Shorthand to represent a denormalized `LooseWords` int.
287 DenormalLooseWords;
288
289 /// A loosely-packed arbitrary base big int implementation.
290 /// Supports any base from 2-u32::MAX.
291 ///
292 /// Each digit requires 4 bytes of storage, making this a fairly space-inefficient
293 /// implementation for smaller bases. However, the lack of additional complexity
294 /// improves runtime efficiency over the tightly-packed implementation.
295 ///
296 /// ```
297 /// use big_int::prelude::*;
298 ///
299 /// let a: LooseWords<10> = 593.into();
300 /// let b = a * 96.into();
301 /// assert_eq!(b, 56928.into());
302 /// ```
303 LooseWords;
304
305 /// A builder for a `LooseWords` int.
306 ///
307 /// You're most likely better off using one of the `From` implementations
308 /// as opposed to directly building your int via a builder.
309 ///
310 /// ```
311 /// use big_int::prelude::*;
312 ///
313 /// let mut a = LooseWordsBuilder::<10>::new();
314 /// a.push_back(5);
315 /// a.push_back(3);
316 /// a.push_back(0);
317 /// a.push_back(4);
318 /// let a: LooseWords<10> = a.into();
319 /// assert_eq!(a, 5304.into());
320 /// ```
321 LooseWordsBuilder;
322);
323
324loose_definition!(
325 u64;
326
327 /// Shorthand to represent a denormalized `Loose` int.
328 DenormalLoose;
329
330 /// A loosely-packed arbitrary base big int implementation.
331 /// Supports any base from 2-u64::MAX.
332 ///
333 /// Each digit requires 8 bytes of storage, making this a very space-inefficient
334 /// implementation for smaller bases. However, the lack of additional complexity
335 /// improves runtime efficiency over the tightly-packed implementation.
336 ///
337 /// ```
338 /// use big_int::prelude::*;
339 ///
340 /// let a: Loose<10> = 593.into();
341 /// let b = a * 96.into();
342 /// assert_eq!(b, 56928.into());
343 /// ```
344 Loose;
345
346 /// A builder for a `Loose` int.
347 ///
348 /// You're most likely better off using one of the `From` implementations
349 /// as opposed to directly building your int via a builder.
350 ///
351 /// ```
352 /// use big_int::prelude::*;
353 ///
354 /// let mut a = LooseBuilder::<10>::new();
355 /// a.push_back(5);
356 /// a.push_back(3);
357 /// a.push_back(0);
358 /// a.push_back(4);
359 /// let a: Loose<10> = a.into();
360 /// assert_eq!(a, 5304.into());
361 /// ```
362 LooseBuilder;
363);