big_int/
tight.rs

1//! tightly packed big int implementation, for better memory efficiency.
2//!
3//! ```
4//! use big_int::prelude::*;
5//!
6//! let mut a: Tight<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;
18use std::collections::VecDeque;
19
20use crate::prelude::*;
21
22mod tests;
23
24/// Represents a single datum of information within a `Tight` int.
25/// The size of this value has no impact on the size of individual
26/// digits that the number can represent; it only impacts memory and
27/// runtime performance. Could be any unsigned type from u8-u128.
28pub type Datum = u8;
29
30/// Size of the chosen datum unit, in bits.
31pub const DATUM_SIZE: usize = std::mem::size_of::<Datum>() * 8;
32
33/// Shorthand for a denormalized loose int.
34pub type DenormalTight<const BASE: usize> = Denormal<BASE, Tight<BASE>>;
35
36/// A tightly-packed arbitrary base big int implementation.
37/// Supports any base from 2-u64::MAX.
38///
39/// In this implementation, bits are tightly packed against one another,
40/// requiring only `ceil(log_2(BASE))` bits per digit. Signficiantly more space-efficient for
41/// smaller bases compared to the loose implementation. However, the extra indirection contributes
42/// to some added overhead.
43///
44/// ```
45/// use big_int::prelude::*;
46///
47/// let a: Tight<10> = 593.into();
48/// let b = a * 96.into();
49/// assert_eq!(b, 56928.into());
50/// ```
51#[derive(Debug, Clone, BigIntTraits)]
52pub struct Tight<const BASE: usize> {
53    sign: Sign,
54    data: VecDeque<Datum>,
55    start_offset: usize,
56    end_offset: usize,
57}
58
59impl<const BASE: usize> Tight<BASE> {
60
61    /// Construct a `Tight` int directly from raw parts.
62    ///
63    /// Ensure the following invariants hold true to maintain soundness:
64    /// * `start_offset <= end_offset`
65    /// * `end_offset <= data.len() * big_int::tight::DATUM_SIZE`
66    /// * `(end_offset - start_offset) % Tight::<BASE>::BITS_PER_DIGIT == 0`
67    ///
68    /// ```
69    /// use big_int::prelude::*;
70    ///
71    /// let a: Tight<10> = unsafe { Tight::from_raw_parts(
72    ///     vec![0b0001_1001, 0b0101_0000].into(),
73    ///     0, 16
74    /// ) };
75    ///
76    /// assert_eq!(a, 1950.into());
77    /// ```
78    pub unsafe fn from_raw_parts(
79        data: VecDeque<Datum>,
80        start_offset: usize,
81        end_offset: usize,
82    ) -> Self {
83        Self {
84            sign: Positive,
85            data,
86            start_offset,
87            end_offset,
88        }
89    }
90
91    /// Return the int with the bits within aligned to the beginning of the data segment
92    /// and unnecessary extra data truncated.
93    ///
94    /// It's likely unnecessary to invoke this directly unless using `Tight::from_raw_parts`.
95    ///
96    /// ```
97    /// use big_int::prelude::*;
98    ///
99    /// let mut a: Tight<10> = unsafe { Tight::from_raw_parts(
100    ///     vec![0b0000_0000, 0b0000_1001, 0b0101_0000, 0b0000_0000].into(),
101    ///     12, 20
102    /// ) };
103    /// assert_eq!(a.aligned(), unsafe { Tight::from_raw_parts(
104    ///     vec![0b1001_0101].into(),
105    ///     0, 8
106    /// ) });
107    /// ```
108    pub fn aligned(mut self) -> Self {
109        let empty_cells = self.start_offset / DATUM_SIZE;
110        self.start_offset -= empty_cells * DATUM_SIZE;
111        self.end_offset -= empty_cells * DATUM_SIZE;
112        let data_cells = self.data.into_iter().skip(empty_cells);
113        self.data = if self.start_offset == 0 {
114            data_cells.collect()
115        } else {
116            let data_length = (self.end_offset - self.start_offset).div_ceil(DATUM_SIZE);
117            let mut data = VecDeque::new();
118            let left_half_offset = DATUM_SIZE - self.start_offset;
119            let left_half_mask = mask!(self.start_offset) << left_half_offset;
120            let right_half_mask = mask!(DATUM_SIZE - self.start_offset);
121            let mut right_half = None;
122            for datum in data_cells {
123                if let Some(right_half) = right_half {
124                    let left_half = (datum & left_half_mask) >> left_half_offset;
125                    let aligned_datum = left_half | right_half;
126                    data.push_back(aligned_datum);
127                    if data.len() >= data_length {
128                        break;
129                    }
130                }
131                right_half = Some((datum & right_half_mask) << self.start_offset);
132            }
133            if let Some(right_half) = right_half {
134                if data.len() < data_length {
135                    data.push_back(right_half);
136                }
137            }
138            self.end_offset -= self.start_offset;
139            self.start_offset = 0;
140            data
141        };
142        self
143    }
144}
145
146impl<const BASE: usize> BigInt<{ BASE }> for Tight<BASE> {
147    type Builder = TightBuilder<{ BASE }>;
148    type Denormal = Denormal<BASE, Self>;
149
150    fn len(&self) -> usize {
151        (self.end_offset - self.start_offset) / Self::BITS_PER_DIGIT
152    }
153
154    fn get_digit(&self, digit: usize) -> Option<Digit> {
155        let mut digit_offset = self.start_offset + digit * Self::BITS_PER_DIGIT;
156        if digit_offset >= self.end_offset {
157            None
158        } else {
159            let mut digit_value = 0;
160            let mut bits_left_to_pull = Self::BITS_PER_DIGIT;
161            while bits_left_to_pull > 0 {
162                let datum_index = digit_offset / DATUM_SIZE;
163                let bit_in_datum = digit_offset % DATUM_SIZE;
164                let bits_available_in_datum = DATUM_SIZE - bit_in_datum;
165                let bits_to_take = bits_available_in_datum.min(bits_left_to_pull);
166                digit_offset += bits_to_take;
167                bits_left_to_pull -= bits_to_take;
168                let datum_offset = bits_available_in_datum - bits_to_take;
169                let datum_mask: Datum = mask!(bits_to_take) << datum_offset;
170                let piece_of_digit = ((self.data[datum_index] & datum_mask) as Digit
171                    >> datum_offset)
172                    << bits_left_to_pull;
173                digit_value |= piece_of_digit;
174            }
175            Some(digit_value)
176        }
177    }
178
179    fn set_digit(&mut self, digit: usize, value: Digit) {
180        let mut digit_offset = self.start_offset + digit * Self::BITS_PER_DIGIT;
181        if digit_offset < self.end_offset {
182            let mut bits_left_to_set = Self::BITS_PER_DIGIT;
183            while bits_left_to_set > 0 {
184                let datum_index = digit_offset / DATUM_SIZE;
185                let bit_in_datum = digit_offset % DATUM_SIZE;
186                let bits_left_in_datum = DATUM_SIZE - bit_in_datum;
187                let bits_to_set = bits_left_in_datum.min(bits_left_to_set);
188                digit_offset += bits_to_set;
189                bits_left_to_set -= bits_to_set;
190                let datum_offset = bits_left_in_datum - bits_to_set;
191                let piece_mask = mask!(bits_to_set) << bits_left_to_set;
192                let piece_of_digit = ((value & piece_mask) >> bits_left_to_set) << datum_offset;
193                let datum_mask = mask!(bits_to_set) << datum_offset;
194                self.data[datum_index] &= !datum_mask;
195                self.data[datum_index] |= piece_of_digit as Datum;
196            }
197        }
198    }
199
200    fn zero() -> Self {
201        Self {
202            sign: Positive,
203            data: VecDeque::from(vec![0; Self::BITS_PER_DIGIT.div_ceil(DATUM_SIZE)]),
204            start_offset: 0,
205            end_offset: Self::BITS_PER_DIGIT,
206        }
207    }
208
209    fn sign(&self) -> Sign {
210        self.sign
211    }
212
213    fn with_sign(self, sign: Sign) -> Self {
214        Self { sign, ..self }
215    }
216
217    fn set_sign(&mut self, sign: Sign) {
218        self.sign = sign;
219    }
220
221    fn push_back(&mut self, digit: Digit) {
222        let mut bits_left_to_set = Self::BITS_PER_DIGIT;
223        while bits_left_to_set > 0 {
224            let datum_index = self.end_offset / DATUM_SIZE;
225            if datum_index >= self.data.len() {
226                self.data.push_back(0);
227            }
228            let bit_in_datum = self.end_offset % DATUM_SIZE;
229            let space_left_in_datum = DATUM_SIZE - bit_in_datum;
230            let bits_to_take = space_left_in_datum.min(bits_left_to_set);
231            self.end_offset += bits_to_take;
232            bits_left_to_set -= bits_to_take;
233            let digit_mask = mask!(bits_to_take) << bits_left_to_set;
234            let piece_of_digit = (((digit_mask & digit) >> bits_left_to_set)
235                << (DATUM_SIZE - bits_to_take))
236                >> bit_in_datum;
237            self.data[datum_index] |= piece_of_digit as Datum;
238        }
239    }
240
241    unsafe fn push_front(&mut self, digit: Digit) {
242        let mut bits_left_to_set = Self::BITS_PER_DIGIT;
243        while bits_left_to_set > 0 {
244            if self.start_offset == 0 {
245                self.data.push_front(0);
246                self.start_offset += DATUM_SIZE;
247                self.end_offset += DATUM_SIZE;
248            }
249            let datum_index = (self.start_offset - 1) / DATUM_SIZE;
250            let space_left_in_datum = (self.start_offset - 1) % DATUM_SIZE + 1;
251            let bits_to_take = space_left_in_datum.min(bits_left_to_set);
252            self.start_offset -= bits_to_take;
253            let mask_offset = Self::BITS_PER_DIGIT - bits_left_to_set;
254            let digit_mask = mask!(bits_to_take) << mask_offset;
255            bits_left_to_set -= bits_to_take;
256            let piece_of_digit =
257                ((digit_mask & digit) >> mask_offset) << (DATUM_SIZE - space_left_in_datum);
258            self.data[datum_index] |= piece_of_digit as Datum;
259        }
260    }
261
262    unsafe fn shr_assign_inner(&mut self, amount: usize) {
263        self.end_offset = self
264            .end_offset
265            .checked_sub(amount * Self::BITS_PER_DIGIT)
266            .unwrap_or_default()
267            .max(self.start_offset);
268        self.normalize();
269    }
270
271    unsafe fn shl_assign_inner(&mut self, amount: usize) {
272        self.end_offset += Self::BITS_PER_DIGIT * amount;
273        let new_len = self.end_offset.div_ceil(DATUM_SIZE);
274        let cur_len = self.data.len();
275        self.data.extend(vec![0; new_len - cur_len]);
276    }
277
278    /// Return a normalized version of the int. Remove trailing zeros, disable the parity flag
279    /// if the resulting number is zero, and align the internal bits to the beginning of the
280    /// data array.
281    fn normalized(mut self) -> Self {
282        while self.start_offset < self.end_offset && self.get_digit(0) == Some(0) {
283            self.start_offset += Self::BITS_PER_DIGIT;
284        }
285        if self.start_offset >= self.end_offset {
286            Self::zero()
287        } else if self.start_offset > 0 {
288            self.aligned()
289        } else {
290            if self.data.len() * DATUM_SIZE >= self.end_offset + DATUM_SIZE {
291                self.data = self
292                    .data
293                    .into_iter()
294                    .take(self.end_offset.div_ceil(DATUM_SIZE))
295                    .collect();
296            }
297            self
298        }
299    }
300
301    unsafe fn pop_front(&mut self) -> Option<Digit> {
302        let digit = self.get_digit(0);
303        if digit.is_some() {
304            self.start_offset += Self::BITS_PER_DIGIT;
305            if self.start_offset >= DATUM_SIZE {
306                let new_start_offset = self.start_offset % DATUM_SIZE;
307                let offset_shift = self.start_offset - new_start_offset;
308                for _ in 0..self.start_offset / DATUM_SIZE {
309                    self.data.pop_front();
310                }
311                self.start_offset = new_start_offset;
312                self.end_offset -= offset_shift;
313            }
314        }
315        digit
316    }
317
318    unsafe fn pop_back(&mut self) -> Option<Digit> {
319        let digit = self.get_back(1);
320        if digit.is_some() {
321            self.end_offset = self
322                .end_offset
323                .checked_sub(Self::BITS_PER_DIGIT)
324                .unwrap_or_default()
325                .max(self.start_offset);
326            for _ in 0..self.data.len() - self.end_offset.div_ceil(DATUM_SIZE) {
327                self.data.pop_back();
328            }
329        }
330        digit
331    }
332}
333
334/// A builder for a `Tight` int.
335///
336/// You're most likely better off using one of the `From` implementations
337/// as opposed to directly building your int via a builder.
338///
339/// ```
340/// use big_int::prelude::*;
341///
342/// let mut a = TightBuilder::<10>::new();
343/// a.push_back(5);
344/// a.push_back(3);
345/// a.push_back(0);
346/// a.push_back(4);
347/// let a: Tight<10> = a.into();
348/// assert_eq!(a, 5304.into());
349/// ```
350#[derive(Debug)]
351pub struct TightBuilder<const BASE: usize>(Tight<BASE>);
352
353impl<const BASE: usize> BigIntBuilder<BASE> for TightBuilder<BASE> {
354    fn new() -> Self {
355        Self(Tight {
356            sign: Positive,
357            data: VecDeque::new(),
358            start_offset: 0,
359            end_offset: 0,
360        })
361    }
362
363    fn push_front(&mut self, digit: Digit) {
364        unsafe { self.0.push_front(digit) };
365    }
366
367    fn push_back(&mut self, digit: Digit) {
368        self.0.push_back(digit);
369    }
370
371    fn is_empty(&self) -> bool {
372        self.0.start_offset >= self.0.end_offset
373    }
374
375    fn with_sign(self, sign: Sign) -> Self {
376        Self(self.0.with_sign(sign))
377    }
378}
379
380impl<const BASE: usize> From<TightBuilder<BASE>> for Denormal<BASE, Tight<BASE>> {
381    fn from(value: TightBuilder<BASE>) -> Self {
382        Denormal(value.0)
383    }
384}
385
386impl<const BASE: usize> From<TightBuilder<BASE>> for Tight<BASE> {
387    fn from(value: TightBuilder<BASE>) -> Self {
388        let denormal: <Self as BigInt<BASE>>::Denormal = value.into();
389        denormal.unwrap()
390    }
391}
big_int/tight.rs

big_int/
tight.rs
