1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Custom arbitrary-precision number (bignum) implementation.
13 //! This is designed to avoid the heap allocation at expense of stack memory.
14 //! The most used bignum type, `Big32x40`, is limited by 32 × 40 = 1,280 bits
15 //! and will take at most 160 bytes of stack memory. This is more than enough
16 //! for round-tripping all possible finite `f64` values.
18 //! In principle it is possible to have multiple bignum types for different
19 //! inputs, but we don't do so to avoid the code bloat. Each bignum is still
20 //! tracked for the actual usages, so it normally doesn't matter.
22 // This module is only for dec2flt and flt2dec, and only public because of libcoretest.
23 // It is not intended to ever be stabilized.
25 #![unstable(feature = "core_private_bignum",
26 reason
= "internal routines only exposed for testing",
33 /// Arithmetic operations required by bignums.
34 pub trait FullOps
: Sized
{
35 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self + other + carry`,
36 /// where `W` is the number of bits in `Self`.
37 fn full_add(self, other
: Self, carry
: bool
) -> (bool
/* carry */, Self);
39 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + carry`,
40 /// where `W` is the number of bits in `Self`.
41 fn full_mul(self, other
: Self, carry
: Self) -> (Self /* carry */, Self);
43 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + other2 + carry`,
44 /// where `W` is the number of bits in `Self`.
45 fn full_mul_add(self, other
: Self, other2
: Self, carry
: Self) -> (Self /* carry */, Self);
47 /// Returns `(quo, rem)` such that `borrow * 2^W + self = quo * other + rem`
48 /// and `0 <= rem < other`, where `W` is the number of bits in `Self`.
52 -> (Self /* quotient */, Self /* remainder */);
55 macro_rules
! impl_full_ops
{
56 ($
($ty
:ty
: add($addfn
:path
), mul
/div($bigty
:ident
);)*) => (
58 impl FullOps
for $ty
{
59 fn full_add(self, other
: $ty
, carry
: bool
) -> (bool
, $ty
) {
60 // this cannot overflow, the output is between 0 and 2*2^nbits - 1
61 // FIXME will LLVM optimize this into ADC or similar???
62 let (v
, carry1
) = unsafe { intrinsics::add_with_overflow(self, other) }
;
63 let (v
, carry2
) = unsafe {
64 intrinsics
::add_with_overflow(v
, if carry {1}
else {0}
)
69 fn full_mul(self, other
: $ty
, carry
: $ty
) -> ($ty
, $ty
) {
70 // this cannot overflow, the output is between 0 and 2^nbits * (2^nbits - 1)
71 let nbits
= mem
::size_of
::<$ty
>() * 8;
72 let v
= (self as $bigty
) * (other
as $bigty
) + (carry
as $bigty
);
73 ((v
>> nbits
) as $ty
, v
as $ty
)
76 fn full_mul_add(self, other
: $ty
, other2
: $ty
, carry
: $ty
) -> ($ty
, $ty
) {
77 // this cannot overflow, the output is between 0 and 2^(2*nbits) - 1
78 let nbits
= mem
::size_of
::<$ty
>() * 8;
79 let v
= (self as $bigty
) * (other
as $bigty
) + (other2
as $bigty
) +
81 ((v
>> nbits
) as $ty
, v
as $ty
)
84 fn full_div_rem(self, other
: $ty
, borrow
: $ty
) -> ($ty
, $ty
) {
85 debug_assert
!(borrow
< other
);
86 // this cannot overflow, the dividend is between 0 and other * 2^nbits - 1
87 let nbits
= mem
::size_of
::<$ty
>() * 8;
88 let lhs
= ((borrow
as $bigty
) << nbits
) | (self as $bigty
);
89 let rhs
= other
as $bigty
;
90 ((lhs
/ rhs
) as $ty
, (lhs
% rhs
) as $ty
)
98 u8: add(intrinsics
::u8_add_with_overflow
), mul
/div(u16);
99 u16: add(intrinsics
::u16_add_with_overflow
), mul
/div(u32);
100 u32: add(intrinsics
::u32_add_with_overflow
), mul
/div(u64);
101 // u64: add(intrinsics::u64_add_with_overflow), mul/div(u128); // see RFC #521 for enabling this.
104 /// Table of powers of 5 representable in digits. Specifically, the largest {u8, u16, u32} value
105 /// that's a power of five, plus the corresponding exponent. Used in `mul_pow5`.
106 const SMALL_POW5
: [(u64, usize); 3] = [(125, 3), (15625, 6), (1_220_703_125, 13)];
108 macro_rules
! define_bignum
{
109 ($name
:ident
: type=$ty
:ty
, n
=$n
:expr
) => (
110 /// Stack-allocated arbitrary-precision (up to certain limit) integer.
112 /// This is backed by a fixed-size array of given type ("digit").
113 /// While the array is not very large (normally some hundred bytes),
114 /// copying it recklessly may result in the performance hit.
115 /// Thus this is intentionally not `Copy`.
117 /// All operations available to bignums panic in the case of over/underflows.
118 /// The caller is responsible to use large enough bignum types.
120 /// One plus the offset to the maximum "digit" in use.
121 /// This does not decrease, so be aware of the computation order.
122 /// `base[size..]` should be zero.
124 /// Digits. `[a, b, c, ...]` represents `a + b*2^W + c*2^(2W) + ...`
125 /// where `W` is the number of bits in the digit type.
130 /// Makes a bignum from one digit.
131 pub fn from_small(v
: $ty
) -> $name
{
132 let mut base
= [0; $n
];
134 $name { size: 1, base: base }
137 /// Makes a bignum from `u64` value.
138 pub fn from_u64(mut v
: u64) -> $name
{
141 let mut base
= [0; $n
];
145 v
>>= mem
::size_of
::<$ty
>() * 8;
148 $name { size: sz, base: base }
151 /// Return the internal digits as a slice `[a, b, c, ...]` such that the numeric
152 /// value is `a + b * 2^W + c * 2^(2W) + ...` where `W` is the number of bits in
154 pub fn digits(&self) -> &[$ty
] {
155 &self.base
[..self.size
]
158 /// Return the `i`-th bit where bit 0 is the least significant one.
159 /// In other words, the bit with weight `2^i`.
160 pub fn get_bit(&self, i
: usize) -> u8 {
163 let digitbits
= mem
::size_of
::<$ty
>() * 8;
164 let d
= i
/ digitbits
;
165 let b
= i
% digitbits
;
166 ((self.base
[d
] >> b
) & 1) as u8
169 /// Returns true if the bignum is zero.
170 pub fn is_zero(&self) -> bool
{
171 self.digits().iter().all(|&v
| v
== 0)
174 /// Returns the number of bits necessary to represent this value. Note that zero
175 /// is considered to need 0 bits.
176 pub fn bit_length(&self) -> usize {
179 // Skip over the most significant digits which are zero.
180 let digits
= self.digits();
181 let zeros
= digits
.iter().rev().take_while(|&&x
| x
== 0).count();
182 let end
= digits
.len() - zeros
;
183 let nonzero
= &digits
[..end
];
185 if nonzero
.is_empty() {
186 // There are no non-zero digits, i.e. the number is zero.
189 // This could be optimized with leading_zeros() and bit shifts, but that's
190 // probably not worth the hassle.
191 let digitbits
= mem
::size_of
::<$ty
>()* 8;
192 let mut i
= nonzero
.len() * digitbits
- 1;
193 while self.get_bit(i
) == 0 {
199 /// Adds `other` to itself and returns its own mutable reference.
200 pub fn add
<'a
>(&'a
mut self, other
: &$name
) -> &'a
mut $name
{
202 use num
::bignum
::FullOps
;
204 let mut sz
= cmp
::max(self.size
, other
.size
);
205 let mut carry
= false;
206 for (a
, b
) in self.base
[..sz
].iter_mut().zip(&other
.base
[..sz
]) {
207 let (c
, v
) = (*a
).full_add(*b
, carry
);
219 pub fn add_small(&mut self, other
: $ty
) -> &mut $name
{
220 use num
::bignum
::FullOps
;
222 let (mut carry
, v
) = self.base
[0].full_add(other
, false);
226 let (c
, v
) = self.base
[i
].full_add(0, carry
);
237 /// Subtracts `other` from itself and returns its own mutable reference.
238 pub fn sub
<'a
>(&'a
mut self, other
: &$name
) -> &'a
mut $name
{
240 use num
::bignum
::FullOps
;
242 let sz
= cmp
::max(self.size
, other
.size
);
243 let mut noborrow
= true;
244 for (a
, b
) in self.base
[..sz
].iter_mut().zip(&other
.base
[..sz
]) {
245 let (c
, v
) = (*a
).full_add(!*b
, noborrow
);
254 /// Multiplies itself by a digit-sized `other` and returns its own
255 /// mutable reference.
256 pub fn mul_small(&mut self, other
: $ty
) -> &mut $name
{
257 use num
::bignum
::FullOps
;
259 let mut sz
= self.size
;
261 for a
in &mut self.base
[..sz
] {
262 let (c
, v
) = (*a
).full_mul(other
, carry
);
267 self.base
[sz
] = carry
;
274 /// Multiplies itself by `2^bits` and returns its own mutable reference.
275 pub fn mul_pow2(&mut self, bits
: usize) -> &mut $name
{
278 let digitbits
= mem
::size_of
::<$ty
>() * 8;
279 let digits
= bits
/ digitbits
;
280 let bits
= bits
% digitbits
;
282 assert
!(digits
< $n
);
283 debug_assert
!(self.base
[$n
-digits
..].iter().all(|&v
| v
== 0));
284 debug_assert
!(bits
== 0 || (self.base
[$n
-digits
-1] >> (digitbits
- bits
)) == 0);
286 // shift by `digits * digitbits` bits
287 for i
in (0..self.size
).rev() {
288 self.base
[i
+digits
] = self.base
[i
];
294 // shift by `bits` bits
295 let mut sz
= self.size
+ digits
;
298 let overflow
= self.base
[last
-1] >> (digitbits
- bits
);
300 self.base
[last
] = overflow
;
303 for i
in (digits
+1..last
).rev() {
304 self.base
[i
] = (self.base
[i
] << bits
) |
305 (self.base
[i
-1] >> (digitbits
- bits
));
307 self.base
[digits
] <<= bits
;
308 // self.base[..digits] is zero, no need to shift
315 /// Multiplies itself by `5^e` and returns its own mutable reference.
316 pub fn mul_pow5(&mut self, mut e
: usize) -> &mut $name
{
318 use num
::bignum
::SMALL_POW5
;
320 // There are exactly n trailing zeros on 2^n, and the only relevant digit sizes
321 // are consecutive powers of two, so this is well suited index for the table.
322 let table_index
= mem
::size_of
::<$ty
>().trailing_zeros() as usize;
323 let (small_power
, small_e
) = SMALL_POW5
[table_index
];
324 let small_power
= small_power
as $ty
;
326 // Multiply with the largest single-digit power as long as possible ...
328 self.mul_small(small_power
);
332 // ... then finish off the remainder.
333 let mut rest_power
= 1;
337 self.mul_small(rest_power
);
343 /// Multiplies itself by a number described by `other[0] + other[1] * 2^W +
344 /// other[2] * 2^(2W) + ...` (where `W` is the number of bits in the digit type)
345 /// and returns its own mutable reference.
346 pub fn mul_digits
<'a
>(&'a
mut self, other
: &[$ty
]) -> &'a
mut $name
{
347 // the internal routine. works best when aa.len() <= bb.len().
348 fn mul_inner(ret
: &mut [$ty
; $n
], aa
: &[$ty
], bb
: &[$ty
]) -> usize {
349 use num
::bignum
::FullOps
;
352 for (i
, &a
) in aa
.iter().enumerate() {
353 if a
== 0 { continue; }
354 let mut sz
= bb
.len();
356 for (j
, &b
) in bb
.iter().enumerate() {
357 let (c
, v
) = a
.full_mul_add(b
, ret
[i
+ j
], carry
);
372 let mut ret
= [0; $n
];
373 let retsz
= if self.size
< other
.len() {
374 mul_inner(&mut ret
, &self.digits(), other
)
376 mul_inner(&mut ret
, other
, &self.digits())
383 /// Divides itself by a digit-sized `other` and returns its own
384 /// mutable reference *and* the remainder.
385 pub fn div_rem_small(&mut self, other
: $ty
) -> (&mut $name
, $ty
) {
386 use num
::bignum
::FullOps
;
392 for a
in self.base
[..sz
].iter_mut().rev() {
393 let (q
, r
) = (*a
).full_div_rem(other
, borrow
);
400 /// Divide self by another bignum, overwriting `q` with the quotient and `r` with the
402 pub fn div_rem(&self, d
: &$name
, q
: &mut $name
, r
: &mut $name
) {
405 // Stupid slow base-2 long division taken from
406 // https://en.wikipedia.org/wiki/Division_algorithm
407 // FIXME use a greater base ($ty) for the long division.
408 assert
!(!d
.is_zero());
409 let digitbits
= mem
::size_of
::<$ty
>() * 8;
410 for digit
in &mut q
.base
[..] {
413 for digit
in &mut r
.base
[..] {
418 let mut q_is_zero
= true;
419 let end
= self.bit_length();
420 for i
in (0..end
).rev() {
422 r
.base
[0] |= self.get_bit(i
) as $ty
;
425 // Set bit `i` of q to 1.
426 let digit_idx
= i
/ digitbits
;
427 let bit_idx
= i
% digitbits
;
429 q
.size
= digit_idx
+ 1;
432 q
.base
[digit_idx
] |= 1 << bit_idx
;
435 debug_assert
!(q
.base
[q
.size
..].iter().all(|&d
| d
== 0));
436 debug_assert
!(r
.base
[r
.size
..].iter().all(|&d
| d
== 0));
440 impl ::cmp
::PartialEq
for $name
{
441 fn eq(&self, other
: &$name
) -> bool { self.base[..] == other.base[..] }
444 impl ::cmp
::Eq
for $name
{
447 impl ::cmp
::PartialOrd
for $name
{
448 fn partial_cmp(&self, other
: &$name
) -> ::option
::Option
<::cmp
::Ordering
> {
449 ::option
::Option
::Some(self.cmp(other
))
453 impl ::cmp
::Ord
for $name
{
454 fn cmp(&self, other
: &$name
) -> ::cmp
::Ordering
{
456 let sz
= max(self.size
, other
.size
);
457 let lhs
= self.base
[..sz
].iter().cloned().rev();
458 let rhs
= other
.base
[..sz
].iter().cloned().rev();
463 impl ::clone
::Clone
for $name
{
464 fn clone(&self) -> $name
{
465 $name { size: self.size, base: self.base }
469 impl ::fmt
::Debug
for $name
{
470 fn fmt(&self, f
: &mut ::fmt
::Formatter
) -> ::fmt
::Result
{
473 let sz
= if self.size
< 1 {1}
else {self.size}
;
474 let digitlen
= mem
::size_of
::<$ty
>() * 2;
476 write
!(f
, "{:#x}", self.base
[sz
-1])?
;
477 for &v
in self.base
[..sz
-1].iter().rev() {
478 write
!(f
, "_{:01$x}", v
, digitlen
)?
;
480 ::result
::Result
::Ok(())
486 /// The digit type for `Big32x40`.
487 pub type Digit32
= u32;
489 define_bignum
!(Big32x40
: type=Digit32
, n
=40);
491 // this one is used for testing only.
494 define_bignum
!(Big8x3
: type=u8, n
=3);