1//! Custom arbitrary-precision number (bignum) implementation.
2//!
3//! This is designed to avoid the heap allocation at expense of stack memory.
4//! The most used bignum type, `Big32x40`, is limited by 32 × 40 = 1,280 bits
5//! and will take at most 160 bytes of stack memory. This is more than enough
6//! for round-tripping all possible finite `f64` values.
7//!
8//! In principle it is possible to have multiple bignum types for different
9//! inputs, but we don't do so to avoid the code bloat. Each bignum is still
10//! tracked for the actual usages, so it normally doesn't matter.
11
12// This module is only for dec2flt and flt2dec, and only public because of coretests.
13// It is not intended to ever be stabilized.
14#![doc(hidden)]
15#![unstable(
16 feature = "core_private_bignum",
17 reason = "internal routines only exposed for testing",
18 issue = "none"
19)]
20#![macro_use]
21
22/// Arithmetic operations required by bignums.
23pub trait FullOps: Sized {
24 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + other2 + carry`,
25 /// where `W` is the number of bits in `Self`.
26 fn full_mul_add(self, other: Self, other2: Self, carry: Self) -> (Self /* carry */, Self);
27
28 /// Returns `(quo, rem)` such that `borrow * 2^W + self = quo * other + rem`
29 /// and `0 <= rem < other`, where `W` is the number of bits in `Self`.
30 fn full_div_rem(self, other: Self, borrow: Self)
31 -> (Self /* quotient */, Self /* remainder */);
32}
33
34macro_rules! impl_full_ops {
35 ($($ty:ty: add($addfn:path), mul/div($bigty:ident);)*) => (
36 $(
37 impl FullOps for $ty {
38 fn full_mul_add(self, other: $ty, other2: $ty, carry: $ty) -> ($ty, $ty) {
39 // This cannot overflow;
40 // the output is between `0` and `2^nbits * (2^nbits - 1)`.
41 let (lo, hi) = self.carrying_mul_add(other, other2, carry);
42 (hi, lo)
43 }
44
45 fn full_div_rem(self, other: $ty, borrow: $ty) -> ($ty, $ty) {
46 debug_assert!(borrow < other);
47 // This cannot overflow; the output is between `0` and `other * (2^nbits - 1)`.
48 let lhs = ((borrow as $bigty) << <$ty>::BITS) | (self as $bigty);
49 let rhs = other as $bigty;
50 ((lhs / rhs) as $ty, (lhs % rhs) as $ty)
51 }
52 }
53 )*
54 )
55}
56
57impl_full_ops! {
58 u8: add(intrinsics::u8_add_with_overflow), mul/div(u16);
59 u16: add(intrinsics::u16_add_with_overflow), mul/div(u32);
60 u32: add(intrinsics::u32_add_with_overflow), mul/div(u64);
61 u64: add(intrinsics::u64_add_with_overflow), mul/div(u128);
62}
63
64/// Table of powers of 5 representable in digits. Specifically, the largest {u8, u16, u32} value
65/// that's a power of five, plus the corresponding exponent. Used in `mul_pow5`.
66const SMALL_POW5: [(u64, usize); 3] = [(125, 3), (15625, 6), (1_220_703_125, 13)];
67
68macro_rules! define_bignum {
69 ($name:ident: type=$ty:ty, n=$n:expr) => {
70 /// Stack-allocated arbitrary-precision (up to certain limit) integer.
71 ///
72 /// This is backed by a fixed-size array of given type ("digit").
73 /// While the array is not very large (normally some hundred bytes),
74 /// copying it recklessly may result in the performance hit.
75 /// Thus this is intentionally not `Copy`.
76 ///
77 /// All operations available to bignums panic in the case of overflows.
78 /// The caller is responsible to use large enough bignum types.
79 pub struct $name {
80 /// One plus the offset to the maximum "digit" in use.
81 /// This does not decrease, so be aware of the computation order.
82 /// `base[size..]` should be zero.
83 size: usize,
84 /// Digits. `[a, b, c, ...]` represents `a + b*2^W + c*2^(2W) + ...`
85 /// where `W` is the number of bits in the digit type.
86 base: [$ty; $n],
87 }
88
89 impl $name {
90 /// Makes a bignum from one digit.
91 pub fn from_small(v: $ty) -> $name {
92 let mut base = [0; $n];
93 base[0] = v;
94 $name { size: 1, base }
95 }
96
97 /// Makes a bignum from `u64` value.
98 pub fn from_u64(mut v: u64) -> $name {
99 let mut base = [0; $n];
100 let mut sz = 0;
101 while v > 0 {
102 base[sz] = v as $ty;
103 v >>= <$ty>::BITS;
104 sz += 1;
105 }
106 $name { size: sz, base }
107 }
108
109 /// Returns the internal digits as a slice `[a, b, c, ...]` such that the numeric
110 /// value is `a + b * 2^W + c * 2^(2W) + ...` where `W` is the number of bits in
111 /// the digit type.
112 pub fn digits(&self) -> &[$ty] {
113 &self.base[..self.size]
114 }
115
116 /// Returns the `i`-th bit where bit 0 is the least significant one.
117 /// In other words, the bit with weight `2^i`.
118 pub fn get_bit(&self, i: usize) -> u8 {
119 let digitbits = <$ty>::BITS as usize;
120 let d = i / digitbits;
121 let b = i % digitbits;
122 ((self.base[d] >> b) & 1) as u8
123 }
124
125 /// Returns `true` if the bignum is zero.
126 pub fn is_zero(&self) -> bool {
127 self.digits().iter().all(|&v| v == 0)
128 }
129
130 /// Returns the number of bits necessary to represent this value. Note that zero
131 /// is considered to need 0 bits.
132 pub fn bit_length(&self) -> usize {
133 let digitbits = <$ty>::BITS as usize;
134 let digits = self.digits();
135 // Find the most significant non-zero digit.
136 let msd = digits.iter().rposition(|&x| x != 0);
137 match msd {
138 Some(msd) => msd * digitbits + digits[msd].ilog2() as usize + 1,
139 // There are no non-zero digits, i.e., the number is zero.
140 _ => 0,
141 }
142 }
143
144 /// Adds `other` to itself and returns its own mutable reference.
145 pub fn add<'a>(&'a mut self, other: &$name) -> &'a mut $name {
146 use crate::{cmp, iter};
147
148 let mut sz = cmp::max(self.size, other.size);
149 let mut carry = false;
150 for (a, b) in iter::zip(&mut self.base[..sz], &other.base[..sz]) {
151 let (v, c) = (*a).carrying_add(*b, carry);
152 *a = v;
153 carry = c;
154 }
155 if carry {
156 self.base[sz] = 1;
157 sz += 1;
158 }
159 self.size = sz;
160 self
161 }
162
163 pub fn add_small(&mut self, other: $ty) -> &mut $name {
164 let (v, mut carry) = self.base[0].carrying_add(other, false);
165 self.base[0] = v;
166 let mut i = 1;
167 while carry {
168 let (v, c) = self.base[i].carrying_add(0, carry);
169 self.base[i] = v;
170 carry = c;
171 i += 1;
172 }
173 if i > self.size {
174 self.size = i;
175 }
176 self
177 }
178
179 /// Subtracts `other` from itself and returns its own mutable reference.
180 pub fn sub<'a>(&'a mut self, other: &$name) -> &'a mut $name {
181 use crate::{cmp, iter};
182
183 let sz = cmp::max(self.size, other.size);
184 let mut noborrow = true;
185 for (a, b) in iter::zip(&mut self.base[..sz], &other.base[..sz]) {
186 let (v, c) = (*a).carrying_add(!*b, noborrow);
187 *a = v;
188 noborrow = c;
189 }
190 assert!(noborrow);
191 self.size = sz;
192 self
193 }
194
195 /// Multiplies itself by a digit-sized `other` and returns its own
196 /// mutable reference.
197 pub fn mul_small(&mut self, other: $ty) -> &mut $name {
198 let mut sz = self.size;
199 let mut carry = 0;
200 for a in &mut self.base[..sz] {
201 let (v, c) = (*a).carrying_mul(other, carry);
202 *a = v;
203 carry = c;
204 }
205 if carry > 0 {
206 self.base[sz] = carry;
207 sz += 1;
208 }
209 self.size = sz;
210 self
211 }
212
213 /// Multiplies itself by `2^bits` and returns its own mutable reference.
214 pub fn mul_pow2(&mut self, bits: usize) -> &mut $name {
215 let digitbits = <$ty>::BITS as usize;
216 let digits = bits / digitbits;
217 let bits = bits % digitbits;
218
219 assert!(digits < $n);
220 debug_assert!(self.base[$n - digits..].iter().all(|&v| v == 0));
221 debug_assert!(bits == 0 || (self.base[$n - digits - 1] >> (digitbits - bits)) == 0);
222
223 // shift by `digits * digitbits` bits
224 for i in (0..self.size).rev() {
225 self.base[i + digits] = self.base[i];
226 }
227 for i in 0..digits {
228 self.base[i] = 0;
229 }
230
231 // shift by `bits` bits
232 let mut sz = self.size + digits;
233 if bits > 0 {
234 let last = sz;
235 let overflow = self.base[last - 1] >> (digitbits - bits);
236 if overflow > 0 {
237 self.base[last] = overflow;
238 sz += 1;
239 }
240 for i in (digits + 1..last).rev() {
241 self.base[i] =
242 (self.base[i] << bits) | (self.base[i - 1] >> (digitbits - bits));
243 }
244 self.base[digits] <<= bits;
245 // self.base[..digits] is zero, no need to shift
246 }
247
248 self.size = sz;
249 self
250 }
251
252 /// Multiplies itself by `5^e` and returns its own mutable reference.
253 pub fn mul_pow5(&mut self, mut e: usize) -> &mut $name {
254 use crate::num::bignum::SMALL_POW5;
255
256 // There are exactly n trailing zeros on 2^n, and the only relevant digit sizes
257 // are consecutive powers of two, so this is well suited index for the table.
258 let table_index = size_of::<$ty>().trailing_zeros() as usize;
259 let (small_power, small_e) = SMALL_POW5[table_index];
260 let small_power = small_power as $ty;
261
262 // Multiply with the largest single-digit power as long as possible ...
263 while e >= small_e {
264 self.mul_small(small_power);
265 e -= small_e;
266 }
267
268 // ... then finish off the remainder.
269 let mut rest_power = 1;
270 for _ in 0..e {
271 rest_power *= 5;
272 }
273 self.mul_small(rest_power);
274
275 self
276 }
277
278 /// Multiplies itself by a number described by `other[0] + other[1] * 2^W +
279 /// other[2] * 2^(2W) + ...` (where `W` is the number of bits in the digit type)
280 /// and returns its own mutable reference.
281 pub fn mul_digits<'a>(&'a mut self, other: &[$ty]) -> &'a mut $name {
282 // the internal routine. works best when aa.len() <= bb.len().
283 fn mul_inner(ret: &mut [$ty; $n], aa: &[$ty], bb: &[$ty]) -> usize {
284 use crate::num::bignum::FullOps;
285
286 let mut retsz = 0;
287 for (i, &a) in aa.iter().enumerate() {
288 if a == 0 {
289 continue;
290 }
291 let mut sz = bb.len();
292 let mut carry = 0;
293 for (j, &b) in bb.iter().enumerate() {
294 let (c, v) = a.full_mul_add(b, ret[i + j], carry);
295 ret[i + j] = v;
296 carry = c;
297 }
298 if carry > 0 {
299 ret[i + sz] = carry;
300 sz += 1;
301 }
302 if retsz < i + sz {
303 retsz = i + sz;
304 }
305 }
306 retsz
307 }
308
309 let mut ret = [0; $n];
310 let retsz = if self.size < other.len() {
311 mul_inner(&mut ret, &self.digits(), other)
312 } else {
313 mul_inner(&mut ret, other, &self.digits())
314 };
315 self.base = ret;
316 self.size = retsz;
317 self
318 }
319
320 /// Divides itself by a digit-sized `other` and returns its own
321 /// mutable reference *and* the remainder.
322 pub fn div_rem_small(&mut self, other: $ty) -> (&mut $name, $ty) {
323 use crate::num::bignum::FullOps;
324
325 assert!(other > 0);
326
327 let sz = self.size;
328 let mut borrow = 0;
329 for a in self.base[..sz].iter_mut().rev() {
330 let (q, r) = (*a).full_div_rem(other, borrow);
331 *a = q;
332 borrow = r;
333 }
334 (self, borrow)
335 }
336 }
337
338 impl crate::cmp::PartialEq for $name {
339 fn eq(&self, other: &$name) -> bool {
340 self.base[..] == other.base[..]
341 }
342 }
343
344 impl crate::cmp::Eq for $name {}
345
346 impl crate::cmp::PartialOrd for $name {
347 fn partial_cmp(&self, other: &$name) -> crate::option::Option<crate::cmp::Ordering> {
348 crate::option::Option::Some(self.cmp(other))
349 }
350 }
351
352 impl crate::cmp::Ord for $name {
353 fn cmp(&self, other: &$name) -> crate::cmp::Ordering {
354 use crate::cmp::max;
355 let sz = max(self.size, other.size);
356 let lhs = self.base[..sz].iter().cloned().rev();
357 let rhs = other.base[..sz].iter().cloned().rev();
358 lhs.cmp(rhs)
359 }
360 }
361
362 impl crate::clone::Clone for $name {
363 fn clone(&self) -> Self {
364 Self { size: self.size, base: self.base }
365 }
366 }
367
368 impl crate::clone::UseCloned for $name {}
369
370 impl crate::fmt::Debug for $name {
371 fn fmt(&self, f: &mut crate::fmt::Formatter<'_>) -> crate::fmt::Result {
372 let sz = if self.size < 1 { 1 } else { self.size };
373 let digitlen = <$ty>::BITS as usize / 4;
374
375 write!(f, "{:#x}", self.base[sz - 1])?;
376 for &v in self.base[..sz - 1].iter().rev() {
377 write!(f, "_{:01$x}", v, digitlen)?;
378 }
379 crate::result::Result::Ok(())
380 }
381 }
382 };
383}
384
385/// The digit type for `Big32x40`.
386pub type Digit32 = u32;
387
388define_bignum!(Big32x40: type=Digit32, n=40);
389
390// this one is used for testing only.
391#[doc(hidden)]
392pub mod tests {
393 define_bignum!(Big8x3: type=u8, n=3);
394}
395