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