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",
35 /// Arithmetic operations required by bignums.
37 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self + other + carry`,
38 /// where `W` is the number of bits in `Self`.
39 fn full_add(self, other
: Self, carry
: bool
) -> (bool
/*carry*/, Self);
41 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + carry`,
42 /// where `W` is the number of bits in `Self`.
43 fn full_mul(self, other
: Self, carry
: Self) -> (Self /*carry*/, Self);
45 /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + other2 + carry`,
46 /// where `W` is the number of bits in `Self`.
47 fn full_mul_add(self, other
: Self, other2
: Self, carry
: Self) -> (Self /*carry*/, Self);
49 /// Returns `(quo, rem)` such that `borrow * 2^W + self = quo * other + rem`
50 /// and `0 <= rem < other`, where `W` is the number of bits in `Self`.
51 fn full_div_rem(self, other
: Self, borrow
: Self) -> (Self /*quotient*/, Self /*remainder*/);
54 macro_rules
! impl_full_ops
{
55 ($
($ty
:ty
: add($addfn
:path
), mul
/div($bigty
:ident
);)*) => (
57 impl FullOps
for $ty
{
58 fn full_add(self, other
: $ty
, carry
: bool
) -> (bool
, $ty
) {
59 // this cannot overflow, the output is between 0 and 2*2^nbits - 1
60 // FIXME will LLVM optimize this into ADC or similar???
61 let (v
, carry1
) = unsafe { intrinsics::add_with_overflow(self, other) }
;
62 let (v
, carry2
) = unsafe {
63 intrinsics
::add_with_overflow(v
, if carry {1}
else {0}
)
68 fn full_mul(self, other
: $ty
, carry
: $ty
) -> ($ty
, $ty
) {
69 // this cannot overflow, the output is between 0 and 2^nbits * (2^nbits - 1)
70 let nbits
= mem
::size_of
::<$ty
>() * 8;
71 let v
= (self as $bigty
) * (other
as $bigty
) + (carry
as $bigty
);
72 ((v
>> nbits
) as $ty
, v
as $ty
)
75 fn full_mul_add(self, other
: $ty
, other2
: $ty
, carry
: $ty
) -> ($ty
, $ty
) {
76 // this cannot overflow, the output is between 0 and 2^(2*nbits) - 1
77 let nbits
= mem
::size_of
::<$ty
>() * 8;
78 let v
= (self as $bigty
) * (other
as $bigty
) + (other2
as $bigty
) +
80 ((v
>> nbits
) as $ty
, v
as $ty
)
83 fn full_div_rem(self, other
: $ty
, borrow
: $ty
) -> ($ty
, $ty
) {
84 debug_assert
!(borrow
< other
);
85 // this cannot overflow, the dividend is between 0 and other * 2^nbits - 1
86 let nbits
= mem
::size_of
::<$ty
>() * 8;
87 let lhs
= ((borrow
as $bigty
) << nbits
) | (self as $bigty
);
88 let rhs
= other
as $bigty
;
89 ((lhs
/ rhs
) as $ty
, (lhs
% rhs
) as $ty
)
97 u8: add(intrinsics
::u8_add_with_overflow
), mul
/div(u16);
98 u16: add(intrinsics
::u16_add_with_overflow
), mul
/div(u32);
99 u32: add(intrinsics
::u32_add_with_overflow
), mul
/div(u64);
100 // u64: add(intrinsics::u64_add_with_overflow), mul/div(u128); // see RFC #521 for enabling this.
103 /// Table of powers of 5 representable in digits. Specifically, the largest {u8, u16, u32} value
104 /// that's a power of five, plus the corresponding exponent. Used in `mul_pow5`.
105 const SMALL_POW5
: [(u64, usize); 3] = [
111 macro_rules
! define_bignum
{
112 ($name
:ident
: type=$ty
:ty
, n
=$n
:expr
) => (
113 /// Stack-allocated arbitrary-precision (up to certain limit) integer.
115 /// This is backed by a fixed-size array of given type ("digit").
116 /// While the array is not very large (normally some hundred bytes),
117 /// copying it recklessly may result in the performance hit.
118 /// Thus this is intentionally not `Copy`.
120 /// All operations available to bignums panic in the case of over/underflows.
121 /// The caller is responsible to use large enough bignum types.
123 /// One plus the offset to the maximum "digit" in use.
124 /// This does not decrease, so be aware of the computation order.
125 /// `base[size..]` should be zero.
127 /// Digits. `[a, b, c, ...]` represents `a + b*2^W + c*2^(2W) + ...`
128 /// where `W` is the number of bits in the digit type.
133 /// Makes a bignum from one digit.
134 pub fn from_small(v
: $ty
) -> $name
{
135 let mut base
= [0; $n
];
137 $name { size: 1, base: base }
140 /// Makes a bignum from `u64` value.
141 pub fn from_u64(mut v
: u64) -> $name
{
144 let mut base
= [0; $n
];
148 v
>>= mem
::size_of
::<$ty
>() * 8;
151 $name { size: sz, base: base }
154 /// Return the internal digits as a slice `[a, b, c, ...]` such that the numeric
155 /// value is `a + b * 2^W + c * 2^(2W) + ...` where `W` is the number of bits in
157 pub fn digits(&self) -> &[$ty
] {
158 &self.base
[..self.size
]
161 /// Return the `i`-th bit where bit 0 is the least significant one.
162 /// In other words, the bit with weight `2^i`.
163 pub fn get_bit(&self, i
: usize) -> u8 {
166 let digitbits
= mem
::size_of
::<$ty
>() * 8;
167 let d
= i
/ digitbits
;
168 let b
= i
% digitbits
;
169 ((self.base
[d
] >> b
) & 1) as u8
172 /// Returns true if the bignum is zero.
173 pub fn is_zero(&self) -> bool
{
174 self.digits().iter().all(|&v
| v
== 0)
177 /// Returns the number of bits necessary to represent this value. Note that zero
178 /// is considered to need 0 bits.
179 pub fn bit_length(&self) -> usize {
182 // Skip over the most significant digits which are zero.
183 let digits
= self.digits();
184 let zeros
= digits
.iter().rev().take_while(|&&x
| x
== 0).count();
185 let end
= digits
.len() - zeros
;
186 let nonzero
= &digits
[..end
];
188 if nonzero
.is_empty() {
189 // There are no non-zero digits, i.e. the number is zero.
192 // This could be optimized with leading_zeros() and bit shifts, but that's
193 // probably not worth the hassle.
194 let digitbits
= mem
::size_of
::<$ty
>()* 8;
195 let mut i
= nonzero
.len() * digitbits
- 1;
196 while self.get_bit(i
) == 0 {
202 /// Adds `other` to itself and returns its own mutable reference.
203 pub fn add
<'a
>(&'a
mut self, other
: &$name
) -> &'a
mut $name
{
205 use num
::bignum
::FullOps
;
207 let mut sz
= cmp
::max(self.size
, other
.size
);
208 let mut carry
= false;
209 for (a
, b
) in self.base
[..sz
].iter_mut().zip(&other
.base
[..sz
]) {
210 let (c
, v
) = (*a
).full_add(*b
, carry
);
222 pub fn add_small(&mut self, other
: $ty
) -> &mut $name
{
223 use num
::bignum
::FullOps
;
225 let (mut carry
, v
) = self.base
[0].full_add(other
, false);
229 let (c
, v
) = self.base
[i
].full_add(0, carry
);
240 /// Subtracts `other` from itself and returns its own mutable reference.
241 pub fn sub
<'a
>(&'a
mut self, other
: &$name
) -> &'a
mut $name
{
243 use num
::bignum
::FullOps
;
245 let sz
= cmp
::max(self.size
, other
.size
);
246 let mut noborrow
= true;
247 for (a
, b
) in self.base
[..sz
].iter_mut().zip(&other
.base
[..sz
]) {
248 let (c
, v
) = (*a
).full_add(!*b
, noborrow
);
257 /// Multiplies itself by a digit-sized `other` and returns its own
258 /// mutable reference.
259 pub fn mul_small(&mut self, other
: $ty
) -> &mut $name
{
260 use num
::bignum
::FullOps
;
262 let mut sz
= self.size
;
264 for a
in &mut self.base
[..sz
] {
265 let (c
, v
) = (*a
).full_mul(other
, carry
);
270 self.base
[sz
] = carry
;
277 /// Multiplies itself by `2^bits` and returns its own mutable reference.
278 pub fn mul_pow2(&mut self, bits
: usize) -> &mut $name
{
281 let digitbits
= mem
::size_of
::<$ty
>() * 8;
282 let digits
= bits
/ digitbits
;
283 let bits
= bits
% digitbits
;
285 assert
!(digits
< $n
);
286 debug_assert
!(self.base
[$n
-digits
..].iter().all(|&v
| v
== 0));
287 debug_assert
!(bits
== 0 || (self.base
[$n
-digits
-1] >> (digitbits
- bits
)) == 0);
289 // shift by `digits * digitbits` bits
290 for i
in (0..self.size
).rev() {
291 self.base
[i
+digits
] = self.base
[i
];
297 // shift by `bits` bits
298 let mut sz
= self.size
+ digits
;
301 let overflow
= self.base
[last
-1] >> (digitbits
- bits
);
303 self.base
[last
] = overflow
;
306 for i
in (digits
+1..last
).rev() {
307 self.base
[i
] = (self.base
[i
] << bits
) |
308 (self.base
[i
-1] >> (digitbits
- bits
));
310 self.base
[digits
] <<= bits
;
311 // self.base[..digits] is zero, no need to shift
318 /// Multiplies itself by `5^e` and returns its own mutable reference.
319 pub fn mul_pow5(&mut self, mut e
: usize) -> &mut $name
{
321 use num
::bignum
::SMALL_POW5
;
323 // There are exactly n trailing zeros on 2^n, and the only relevant digit sizes
324 // are consecutive powers of two, so this is well suited index for the table.
325 let table_index
= mem
::size_of
::<$ty
>().trailing_zeros() as usize;
326 let (small_power
, small_e
) = SMALL_POW5
[table_index
];
327 let small_power
= small_power
as $ty
;
329 // Multiply with the largest single-digit power as long as possible ...
331 self.mul_small(small_power
);
335 // ... then finish off the remainder.
336 let mut rest_power
= 1;
340 self.mul_small(rest_power
);
346 /// Multiplies itself by a number described by `other[0] + other[1] * 2^W +
347 /// other[2] * 2^(2W) + ...` (where `W` is the number of bits in the digit type)
348 /// and returns its own mutable reference.
349 pub fn mul_digits
<'a
>(&'a
mut self, other
: &[$ty
]) -> &'a
mut $name
{
350 // the internal routine. works best when aa.len() <= bb.len().
351 fn mul_inner(ret
: &mut [$ty
; $n
], aa
: &[$ty
], bb
: &[$ty
]) -> usize {
352 use num
::bignum
::FullOps
;
355 for (i
, &a
) in aa
.iter().enumerate() {
356 if a
== 0 { continue; }
357 let mut sz
= bb
.len();
359 for (j
, &b
) in bb
.iter().enumerate() {
360 let (c
, v
) = a
.full_mul_add(b
, ret
[i
+ j
], carry
);
375 let mut ret
= [0; $n
];
376 let retsz
= if self.size
< other
.len() {
377 mul_inner(&mut ret
, &self.digits(), other
)
379 mul_inner(&mut ret
, other
, &self.digits())
386 /// Divides itself by a digit-sized `other` and returns its own
387 /// mutable reference *and* the remainder.
388 pub fn div_rem_small(&mut self, other
: $ty
) -> (&mut $name
, $ty
) {
389 use num
::bignum
::FullOps
;
395 for a
in self.base
[..sz
].iter_mut().rev() {
396 let (q
, r
) = (*a
).full_div_rem(other
, borrow
);
403 /// Divide self by another bignum, overwriting `q` with the quotient and `r` with the
405 pub fn div_rem(&self, d
: &$name
, q
: &mut $name
, r
: &mut $name
) {
408 // Stupid slow base-2 long division taken from
409 // https://en.wikipedia.org/wiki/Division_algorithm
410 // FIXME use a greater base ($ty) for the long division.
411 assert
!(!d
.is_zero());
412 let digitbits
= mem
::size_of
::<$ty
>() * 8;
413 for digit
in &mut q
.base
[..] {
416 for digit
in &mut r
.base
[..] {
421 let mut q_is_zero
= true;
422 let end
= self.bit_length();
423 for i
in (0..end
).rev() {
425 r
.base
[0] |= self.get_bit(i
) as $ty
;
428 // Set bit `i` of q to 1.
429 let digit_idx
= i
/ digitbits
;
430 let bit_idx
= i
% digitbits
;
432 q
.size
= digit_idx
+ 1;
435 q
.base
[digit_idx
] |= 1 << bit_idx
;
438 debug_assert
!(q
.base
[q
.size
..].iter().all(|&d
| d
== 0));
439 debug_assert
!(r
.base
[r
.size
..].iter().all(|&d
| d
== 0));
443 impl ::cmp
::PartialEq
for $name
{
444 fn eq(&self, other
: &$name
) -> bool { self.base[..] == other.base[..] }
447 impl ::cmp
::Eq
for $name
{
450 impl ::cmp
::PartialOrd
for $name
{
451 fn partial_cmp(&self, other
: &$name
) -> ::option
::Option
<::cmp
::Ordering
> {
452 ::option
::Option
::Some(self.cmp(other
))
456 impl ::cmp
::Ord
for $name
{
457 fn cmp(&self, other
: &$name
) -> ::cmp
::Ordering
{
459 let sz
= max(self.size
, other
.size
);
460 let lhs
= self.base
[..sz
].iter().cloned().rev();
461 let rhs
= other
.base
[..sz
].iter().cloned().rev();
466 impl ::clone
::Clone
for $name
{
467 fn clone(&self) -> $name
{
468 $name { size: self.size, base: self.base }
472 impl ::fmt
::Debug
for $name
{
473 fn fmt(&self, f
: &mut ::fmt
::Formatter
) -> ::fmt
::Result
{
476 let sz
= if self.size
< 1 {1}
else {self.size}
;
477 let digitlen
= mem
::size_of
::<$ty
>() * 2;
479 try
!(write
!(f
, "{:#x}", self.base
[sz
-1]));
480 for &v
in self.base
[..sz
-1].iter().rev() {
481 try
!(write
!(f
, "_{:01$x}", v
, digitlen
));
483 ::result
::Result
::Ok(())
489 /// The digit type for `Big32x40`.
490 pub type Digit32
= u32;
492 define_bignum
!(Big32x40
: type=Digit32
, n
=40);
494 // this one is used for testing only.
498 define_bignum
!(Big8x3
: type=u8, n
=3);