Hex Artifact Content
Not logged in

Artifact 2ab20725ff95a317c699597fef80c2f21b987e18:


0000: 2f 2f 20 43 6f 70 79 72 69 67 68 74 20 32 30 31  // Copyright 201
0010: 35 20 54 68 65 20 52 75 73 74 20 50 72 6f 6a 65  5 The Rust Proje
0020: 63 74 20 44 65 76 65 6c 6f 70 65 72 73 2e 20 53  ct Developers. S
0030: 65 65 20 74 68 65 20 43 4f 50 59 52 49 47 48 54  ee the COPYRIGHT
0040: 0a 2f 2f 20 66 69 6c 65 20 61 74 20 74 68 65 20  .// file at the 
0050: 74 6f 70 2d 6c 65 76 65 6c 20 64 69 72 65 63 74  top-level direct
0060: 6f 72 79 20 6f 66 20 74 68 69 73 20 64 69 73 74  ory of this dist
0070: 72 69 62 75 74 69 6f 6e 20 61 6e 64 20 61 74 0a  ribution and at.
0080: 2f 2f 20 68 74 74 70 3a 2f 2f 72 75 73 74 2d 6c  // http://rust-l
0090: 61 6e 67 2e 6f 72 67 2f 43 4f 50 59 52 49 47 48  ang.org/COPYRIGH
00a0: 54 2e 0a 2f 2f 0a 2f 2f 20 4c 69 63 65 6e 73 65  T..//.// License
00b0: 64 20 75 6e 64 65 72 20 74 68 65 20 41 70 61 63  d under the Apac
00c0: 68 65 20 4c 69 63 65 6e 73 65 2c 20 56 65 72 73  he License, Vers
00d0: 69 6f 6e 20 32 2e 30 20 3c 4c 49 43 45 4e 53 45  ion 2.0 <LICENSE
00e0: 2d 41 50 41 43 48 45 20 6f 72 0a 2f 2f 20 68 74  -APACHE or.// ht
00f0: 74 70 3a 2f 2f 77 77 77 2e 61 70 61 63 68 65 2e  tp://www.apache.
0100: 6f 72 67 2f 6c 69 63 65 6e 73 65 73 2f 4c 49 43  org/licenses/LIC
0110: 45 4e 53 45 2d 32 2e 30 3e 20 6f 72 20 74 68 65  ENSE-2.0> or the
0120: 20 4d 49 54 20 6c 69 63 65 6e 73 65 0a 2f 2f 20   MIT license.// 
0130: 3c 4c 49 43 45 4e 53 45 2d 4d 49 54 20 6f 72 20  <LICENSE-MIT or 
0140: 68 74 74 70 3a 2f 2f 6f 70 65 6e 73 6f 75 72 63  http://opensourc
0150: 65 2e 6f 72 67 2f 6c 69 63 65 6e 73 65 73 2f 4d  e.org/licenses/M
0160: 49 54 3e 2c 20 61 74 20 79 6f 75 72 0a 2f 2f 20  IT>, at your.// 
0170: 6f 70 74 69 6f 6e 2e 20 54 68 69 73 20 66 69 6c  option. This fil
0180: 65 20 6d 61 79 20 6e 6f 74 20 62 65 20 63 6f 70  e may not be cop
0190: 69 65 64 2c 20 6d 6f 64 69 66 69 65 64 2c 20 6f  ied, modified, o
01a0: 72 20 64 69 73 74 72 69 62 75 74 65 64 0a 2f 2f  r distributed.//
01b0: 20 65 78 63 65 70 74 20 61 63 63 6f 72 64 69 6e   except accordin
01c0: 67 20 74 6f 20 74 68 6f 73 65 20 74 65 72 6d 73  g to those terms
01d0: 2e 0a 0a 2f 2f 21 20 43 75 73 74 6f 6d 20 61 72  ...//! Custom ar
01e0: 62 69 74 72 61 72 79 2d 70 72 65 63 69 73 69 6f  bitrary-precisio
01f0: 6e 20 6e 75 6d 62 65 72 20 28 62 69 67 6e 75 6d  n number (bignum
0200: 29 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e  ) implementation
0210: 2e 0a 2f 2f 21 0a 2f 2f 21 20 54 68 69 73 20 69  ..//!.//! This i
0220: 73 20 64 65 73 69 67 6e 65 64 20 74 6f 20 61 76  s designed to av
0230: 6f 69 64 20 74 68 65 20 68 65 61 70 20 61 6c 6c  oid the heap all
0240: 6f 63 61 74 69 6f 6e 20 61 74 20 65 78 70 65 6e  ocation at expen
0250: 73 65 20 6f 66 20 73 74 61 63 6b 20 6d 65 6d 6f  se of stack memo
0260: 72 79 2e 0a 2f 2f 21 20 54 68 65 20 6d 6f 73 74  ry..//! The most
0270: 20 75 73 65 64 20 62 69 67 6e 75 6d 20 74 79 70   used bignum typ
0280: 65 2c 20 60 42 69 67 33 32 78 34 30 60 2c 20 69  e, `Big32x40`, i
0290: 73 20 6c 69 6d 69 74 65 64 20 62 79 20 33 32 20  s limited by 32 
02a0: c3 97 20 34 30 20 3d 20 31 2c 32 38 30 20 62 69  .. 40 = 1,280 bi
02b0: 74 73 0a 2f 2f 21 20 61 6e 64 20 77 69 6c 6c 20  ts.//! and will 
02c0: 74 61 6b 65 20 61 74 20 6d 6f 73 74 20 31 36 30  take at most 160
02d0: 20 62 79 74 65 73 20 6f 66 20 73 74 61 63 6b 20   bytes of stack 
02e0: 6d 65 6d 6f 72 79 2e 20 54 68 69 73 20 69 73 20  memory. This is 
02f0: 6d 6f 72 65 20 74 68 61 6e 20 65 6e 6f 75 67 68  more than enough
0300: 0a 2f 2f 21 20 66 6f 72 20 72 6f 75 6e 64 2d 74  .//! for round-t
0310: 72 69 70 70 69 6e 67 20 61 6c 6c 20 70 6f 73 73  ripping all poss
0320: 69 62 6c 65 20 66 69 6e 69 74 65 20 60 66 36 34  ible finite `f64
0330: 60 20 76 61 6c 75 65 73 2e 0a 2f 2f 21 0a 2f 2f  ` values..//!.//
0340: 21 20 49 6e 20 70 72 69 6e 63 69 70 6c 65 20 69  ! In principle i
0350: 74 20 69 73 20 70 6f 73 73 69 62 6c 65 20 74 6f  t is possible to
0360: 20 68 61 76 65 20 6d 75 6c 74 69 70 6c 65 20 62   have multiple b
0370: 69 67 6e 75 6d 20 74 79 70 65 73 20 66 6f 72 20  ignum types for 
0380: 64 69 66 66 65 72 65 6e 74 0a 2f 2f 21 20 69 6e  different.//! in
0390: 70 75 74 73 2c 20 62 75 74 20 77 65 20 64 6f 6e  puts, but we don
03a0: 27 74 20 64 6f 20 73 6f 20 74 6f 20 61 76 6f 69  't do so to avoi
03b0: 64 20 74 68 65 20 63 6f 64 65 20 62 6c 6f 61 74  d the code bloat
03c0: 2e 20 45 61 63 68 20 62 69 67 6e 75 6d 20 69 73  . Each bignum is
03d0: 20 73 74 69 6c 6c 0a 2f 2f 21 20 74 72 61 63 6b   still.//! track
03e0: 65 64 20 66 6f 72 20 74 68 65 20 61 63 74 75 61  ed for the actua
03f0: 6c 20 75 73 61 67 65 73 2c 20 73 6f 20 69 74 20  l usages, so it 
0400: 6e 6f 72 6d 61 6c 6c 79 20 64 6f 65 73 6e 27 74  normally doesn't
0410: 20 6d 61 74 74 65 72 2e 0a 0a 2f 2f 20 54 68 69   matter...// Thi
0420: 73 20 6d 6f 64 75 6c 65 20 69 73 20 6f 6e 6c 79  s module is only
0430: 20 66 6f 72 20 64 65 63 32 66 6c 74 20 61 6e 64   for dec2flt and
0440: 20 66 6c 74 32 64 65 63 2c 20 61 6e 64 20 6f 6e   flt2dec, and on
0450: 6c 79 20 70 75 62 6c 69 63 20 62 65 63 61 75 73  ly public becaus
0460: 65 20 6f 66 20 63 6f 72 65 74 65 73 74 73 2e 0a  e of coretests..
0470: 2f 2f 20 49 74 20 69 73 20 6e 6f 74 20 69 6e 74  // It is not int
0480: 65 6e 64 65 64 20 74 6f 20 65 76 65 72 20 62 65  ended to ever be
0490: 20 73 74 61 62 69 6c 69 7a 65 64 2e 0a 23 21 5b   stabilized..#![
04a0: 64 6f 63 28 68 69 64 64 65 6e 29 5d 0a 23 21 5b  doc(hidden)].#![
04b0: 75 6e 73 74 61 62 6c 65 28 66 65 61 74 75 72 65  unstable(feature
04c0: 20 3d 20 22 63 6f 72 65 5f 70 72 69 76 61 74 65   = "core_private
04d0: 5f 62 69 67 6e 75 6d 22 2c 0a 20 20 20 20 20 20  _bignum",.      
04e0: 20 20 20 20 20 20 72 65 61 73 6f 6e 20 3d 20 22        reason = "
04f0: 69 6e 74 65 72 6e 61 6c 20 72 6f 75 74 69 6e 65  internal routine
0500: 73 20 6f 6e 6c 79 20 65 78 70 6f 73 65 64 20 66  s only exposed f
0510: 6f 72 20 74 65 73 74 69 6e 67 22 2c 0a 20 20 20  or testing",.   
0520: 20 20 20 20 20 20 20 20 20 69 73 73 75 65 20 3d           issue =
0530: 20 22 30 22 29 5d 0a 23 21 5b 6d 61 63 72 6f 5f   "0")].#![macro_
0540: 75 73 65 5d 0a 0a 75 73 65 20 6d 65 6d 3b 0a 75  use]..use mem;.u
0550: 73 65 20 69 6e 74 72 69 6e 73 69 63 73 3b 0a 0a  se intrinsics;..
0560: 2f 2f 2f 20 41 72 69 74 68 6d 65 74 69 63 20 6f  /// Arithmetic o
0570: 70 65 72 61 74 69 6f 6e 73 20 72 65 71 75 69 72  perations requir
0580: 65 64 20 62 79 20 62 69 67 6e 75 6d 73 2e 0a 70  ed by bignums..p
0590: 75 62 20 74 72 61 69 74 20 46 75 6c 6c 4f 70 73  ub trait FullOps
05a0: 3a 20 53 69 7a 65 64 20 7b 0a 20 20 20 20 2f 2f  : Sized {.    //
05b0: 2f 20 52 65 74 75 72 6e 73 20 60 28 63 61 72 72  / Returns `(carr
05c0: 79 27 2c 20 76 27 29 60 20 73 75 63 68 20 74 68  y', v')` such th
05d0: 61 74 20 60 63 61 72 72 79 27 20 2a 20 32 5e 57  at `carry' * 2^W
05e0: 20 2b 20 76 27 20 3d 20 73 65 6c 66 20 2b 20 6f   + v' = self + o
05f0: 74 68 65 72 20 2b 20 63 61 72 72 79 60 2c 0a 20  ther + carry`,. 
0600: 20 20 20 2f 2f 2f 20 77 68 65 72 65 20 60 57 60     /// where `W`
0610: 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   is the number o
0620: 66 20 62 69 74 73 20 69 6e 20 60 53 65 6c 66 60  f bits in `Self`
0630: 2e 0a 20 20 20 20 66 6e 20 66 75 6c 6c 5f 61 64  ..    fn full_ad
0640: 64 28 73 65 6c 66 2c 20 6f 74 68 65 72 3a 20 53  d(self, other: S
0650: 65 6c 66 2c 20 63 61 72 72 79 3a 20 62 6f 6f 6c  elf, carry: bool
0660: 29 20 2d 3e 20 28 62 6f 6f 6c 20 2f 2a 20 63 61  ) -> (bool /* ca
0670: 72 72 79 20 2a 2f 2c 20 53 65 6c 66 29 3b 0a 0a  rry */, Self);..
0680: 20 20 20 20 2f 2f 2f 20 52 65 74 75 72 6e 73 20      /// Returns 
0690: 60 28 63 61 72 72 79 27 2c 20 76 27 29 60 20 73  `(carry', v')` s
06a0: 75 63 68 20 74 68 61 74 20 60 63 61 72 72 79 27  uch that `carry'
06b0: 20 2a 20 32 5e 57 20 2b 20 76 27 20 3d 20 73 65   * 2^W + v' = se
06c0: 6c 66 20 2a 20 6f 74 68 65 72 20 2b 20 63 61 72  lf * other + car
06d0: 72 79 60 2c 0a 20 20 20 20 2f 2f 2f 20 77 68 65  ry`,.    /// whe
06e0: 72 65 20 60 57 60 20 69 73 20 74 68 65 20 6e 75  re `W` is the nu
06f0: 6d 62 65 72 20 6f 66 20 62 69 74 73 20 69 6e 20  mber of bits in 
0700: 60 53 65 6c 66 60 2e 0a 20 20 20 20 66 6e 20 66  `Self`..    fn f
0710: 75 6c 6c 5f 6d 75 6c 28 73 65 6c 66 2c 20 6f 74  ull_mul(self, ot
0720: 68 65 72 3a 20 53 65 6c 66 2c 20 63 61 72 72 79  her: Self, carry
0730: 3a 20 53 65 6c 66 29 20 2d 3e 20 28 53 65 6c 66  : Self) -> (Self
0740: 20 2f 2a 20 63 61 72 72 79 20 2a 2f 2c 20 53 65   /* carry */, Se
0750: 6c 66 29 3b 0a 0a 20 20 20 20 2f 2f 2f 20 52 65  lf);..    /// Re
0760: 74 75 72 6e 73 20 60 28 63 61 72 72 79 27 2c 20  turns `(carry', 
0770: 76 27 29 60 20 73 75 63 68 20 74 68 61 74 20 60  v')` such that `
0780: 63 61 72 72 79 27 20 2a 20 32 5e 57 20 2b 20 76  carry' * 2^W + v
0790: 27 20 3d 20 73 65 6c 66 20 2a 20 6f 74 68 65 72  ' = self * other
07a0: 20 2b 20 6f 74 68 65 72 32 20 2b 20 63 61 72 72   + other2 + carr
07b0: 79 60 2c 0a 20 20 20 20 2f 2f 2f 20 77 68 65 72  y`,.    /// wher
07c0: 65 20 60 57 60 20 69 73 20 74 68 65 20 6e 75 6d  e `W` is the num
07d0: 62 65 72 20 6f 66 20 62 69 74 73 20 69 6e 20 60  ber of bits in `
07e0: 53 65 6c 66 60 2e 0a 20 20 20 20 66 6e 20 66 75  Self`..    fn fu
07f0: 6c 6c 5f 6d 75 6c 5f 61 64 64 28 73 65 6c 66 2c  ll_mul_add(self,
0800: 20 6f 74 68 65 72 3a 20 53 65 6c 66 2c 20 6f 74   other: Self, ot
0810: 68 65 72 32 3a 20 53 65 6c 66 2c 20 63 61 72 72  her2: Self, carr
0820: 79 3a 20 53 65 6c 66 29 20 2d 3e 20 28 53 65 6c  y: Self) -> (Sel
0830: 66 20 2f 2a 20 63 61 72 72 79 20 2a 2f 2c 20 53  f /* carry */, S
0840: 65 6c 66 29 3b 0a 0a 20 20 20 20 2f 2f 2f 20 52  elf);..    /// R
0850: 65 74 75 72 6e 73 20 60 28 71 75 6f 2c 20 72 65  eturns `(quo, re
0860: 6d 29 60 20 73 75 63 68 20 74 68 61 74 20 60 62  m)` such that `b
0870: 6f 72 72 6f 77 20 2a 20 32 5e 57 20 2b 20 73 65  orrow * 2^W + se
0880: 6c 66 20 3d 20 71 75 6f 20 2a 20 6f 74 68 65 72  lf = quo * other
0890: 20 2b 20 72 65 6d 60 0a 20 20 20 20 2f 2f 2f 20   + rem`.    /// 
08a0: 61 6e 64 20 60 30 20 3c 3d 20 72 65 6d 20 3c 20  and `0 <= rem < 
08b0: 6f 74 68 65 72 60 2c 20 77 68 65 72 65 20 60 57  other`, where `W
08c0: 60 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20  ` is the number 
08d0: 6f 66 20 62 69 74 73 20 69 6e 20 60 53 65 6c 66  of bits in `Self
08e0: 60 2e 0a 20 20 20 20 66 6e 20 66 75 6c 6c 5f 64  `..    fn full_d
08f0: 69 76 5f 72 65 6d 28 73 65 6c 66 2c 0a 20 20 20  iv_rem(self,.   
0900: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0910: 20 6f 74 68 65 72 3a 20 53 65 6c 66 2c 0a 20 20   other: Self,.  
0920: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0930: 20 20 62 6f 72 72 6f 77 3a 20 53 65 6c 66 29 0a    borrow: Self).
0940: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0950: 20 20 20 20 2d 3e 20 28 53 65 6c 66 20 2f 2a 20      -> (Self /* 
0960: 71 75 6f 74 69 65 6e 74 20 2a 2f 2c 20 53 65 6c  quotient */, Sel
0970: 66 20 2f 2a 20 72 65 6d 61 69 6e 64 65 72 20 2a  f /* remainder *
0980: 2f 29 3b 0a 7d 0a 0a 6d 61 63 72 6f 5f 72 75 6c  /);.}..macro_rul
0990: 65 73 21 20 69 6d 70 6c 5f 66 75 6c 6c 5f 6f 70  es! impl_full_op
09a0: 73 20 7b 0a 20 20 20 20 28 24 28 24 74 79 3a 74  s {.    ($($ty:t
09b0: 79 3a 20 61 64 64 28 24 61 64 64 66 6e 3a 70 61  y: add($addfn:pa
09c0: 74 68 29 2c 20 6d 75 6c 2f 64 69 76 28 24 62 69  th), mul/div($bi
09d0: 67 74 79 3a 69 64 65 6e 74 29 3b 29 2a 29 20 3d  gty:ident);)*) =
09e0: 3e 20 28 0a 20 20 20 20 20 20 20 20 24 28 0a 20  > (.        $(. 
09f0: 20 20 20 20 20 20 20 20 20 20 20 69 6d 70 6c 20             impl 
0a00: 46 75 6c 6c 4f 70 73 20 66 6f 72 20 24 74 79 20  FullOps for $ty 
0a10: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  {.              
0a20: 20 20 66 6e 20 66 75 6c 6c 5f 61 64 64 28 73 65    fn full_add(se
0a30: 6c 66 2c 20 6f 74 68 65 72 3a 20 24 74 79 2c 20  lf, other: $ty, 
0a40: 63 61 72 72 79 3a 20 62 6f 6f 6c 29 20 2d 3e 20  carry: bool) -> 
0a50: 28 62 6f 6f 6c 2c 20 24 74 79 29 20 7b 0a 20 20  (bool, $ty) {.  
0a60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0a70: 20 20 2f 2f 20 74 68 69 73 20 63 61 6e 6e 6f 74    // this cannot
0a80: 20 6f 76 65 72 66 6c 6f 77 2c 20 74 68 65 20 6f   overflow, the o
0a90: 75 74 70 75 74 20 69 73 20 62 65 74 77 65 65 6e  utput is between
0aa0: 20 30 20 61 6e 64 20 32 2a 32 5e 6e 62 69 74 73   0 and 2*2^nbits
0ab0: 20 2d 20 31 0a 20 20 20 20 20 20 20 20 20 20 20   - 1.           
0ac0: 20 20 20 20 20 20 20 20 20 2f 2f 20 46 49 58 4d           // FIXM
0ad0: 45 20 77 69 6c 6c 20 4c 4c 56 4d 20 6f 70 74 69  E will LLVM opti
0ae0: 6d 69 7a 65 20 74 68 69 73 20 69 6e 74 6f 20 41  mize this into A
0af0: 44 43 20 6f 72 20 73 69 6d 69 6c 61 72 3f 3f 3f  DC or similar???
0b00: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0b10: 20 20 20 20 20 6c 65 74 20 28 76 2c 20 63 61 72       let (v, car
0b20: 72 79 31 29 20 3d 20 75 6e 73 61 66 65 20 7b 20  ry1) = unsafe { 
0b30: 69 6e 74 72 69 6e 73 69 63 73 3a 3a 61 64 64 5f  intrinsics::add_
0b40: 77 69 74 68 5f 6f 76 65 72 66 6c 6f 77 28 73 65  with_overflow(se
0b50: 6c 66 2c 20 6f 74 68 65 72 29 20 7d 3b 0a 20 20  lf, other) };.  
0b60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0b70: 20 20 6c 65 74 20 28 76 2c 20 63 61 72 72 79 32    let (v, carry2
0b80: 29 20 3d 20 75 6e 73 61 66 65 20 7b 0a 20 20 20  ) = unsafe {.   
0b90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0ba0: 20 20 20 20 20 69 6e 74 72 69 6e 73 69 63 73 3a       intrinsics:
0bb0: 3a 61 64 64 5f 77 69 74 68 5f 6f 76 65 72 66 6c  :add_with_overfl
0bc0: 6f 77 28 76 2c 20 69 66 20 63 61 72 72 79 20 7b  ow(v, if carry {
0bd0: 31 7d 20 65 6c 73 65 20 7b 30 7d 29 0a 20 20 20  1} else {0}).   
0be0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0bf0: 20 7d 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20   };.            
0c00: 20 20 20 20 20 20 20 20 28 63 61 72 72 79 31 20          (carry1 
0c10: 7c 7c 20 63 61 72 72 79 32 2c 20 76 29 0a 20 20  || carry2, v).  
0c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a                }.
0c30: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0c40: 20 66 6e 20 66 75 6c 6c 5f 6d 75 6c 28 73 65 6c   fn full_mul(sel
0c50: 66 2c 20 6f 74 68 65 72 3a 20 24 74 79 2c 20 63  f, other: $ty, c
0c60: 61 72 72 79 3a 20 24 74 79 29 20 2d 3e 20 28 24  arry: $ty) -> ($
0c70: 74 79 2c 20 24 74 79 29 20 7b 0a 20 20 20 20 20  ty, $ty) {.     
0c80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
0c90: 2f 20 74 68 69 73 20 63 61 6e 6e 6f 74 20 6f 76  / this cannot ov
0ca0: 65 72 66 6c 6f 77 2c 20 74 68 65 20 6f 75 74 70  erflow, the outp
0cb0: 75 74 20 69 73 20 62 65 74 77 65 65 6e 20 30 20  ut is between 0 
0cc0: 61 6e 64 20 32 5e 6e 62 69 74 73 20 2a 20 28 32  and 2^nbits * (2
0cd0: 5e 6e 62 69 74 73 20 2d 20 31 29 0a 20 20 20 20  ^nbits - 1).    
0ce0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0cf0: 6c 65 74 20 6e 62 69 74 73 20 3d 20 6d 65 6d 3a  let nbits = mem:
0d00: 3a 73 69 7a 65 5f 6f 66 3a 3a 3c 24 74 79 3e 28  :size_of::<$ty>(
0d10: 29 20 2a 20 38 3b 0a 20 20 20 20 20 20 20 20 20  ) * 8;.         
0d20: 20 20 20 20 20 20 20 20 20 20 20 6c 65 74 20 76             let v
0d30: 20 3d 20 28 73 65 6c 66 20 61 73 20 24 62 69 67   = (self as $big
0d40: 74 79 29 20 2a 20 28 6f 74 68 65 72 20 61 73 20  ty) * (other as 
0d50: 24 62 69 67 74 79 29 20 2b 20 28 63 61 72 72 79  $bigty) + (carry
0d60: 20 61 73 20 24 62 69 67 74 79 29 3b 0a 20 20 20   as $bigty);.   
0d70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0d80: 20 28 28 76 20 3e 3e 20 6e 62 69 74 73 29 20 61   ((v >> nbits) a
0d90: 73 20 24 74 79 2c 20 76 20 61 73 20 24 74 79 29  s $ty, v as $ty)
0da0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0db0: 20 7d 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20   }..            
0dc0: 20 20 20 20 66 6e 20 66 75 6c 6c 5f 6d 75 6c 5f      fn full_mul_
0dd0: 61 64 64 28 73 65 6c 66 2c 20 6f 74 68 65 72 3a  add(self, other:
0de0: 20 24 74 79 2c 20 6f 74 68 65 72 32 3a 20 24 74   $ty, other2: $t
0df0: 79 2c 20 63 61 72 72 79 3a 20 24 74 79 29 20 2d  y, carry: $ty) -
0e00: 3e 20 28 24 74 79 2c 20 24 74 79 29 20 7b 0a 20  > ($ty, $ty) {. 
0e10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0e20: 20 20 20 2f 2f 20 74 68 69 73 20 63 61 6e 6e 6f     // this canno
0e30: 74 20 6f 76 65 72 66 6c 6f 77 2c 20 74 68 65 20  t overflow, the 
0e40: 6f 75 74 70 75 74 20 69 73 20 62 65 74 77 65 65  output is betwee
0e50: 6e 20 30 20 61 6e 64 20 32 5e 28 32 2a 6e 62 69  n 0 and 2^(2*nbi
0e60: 74 73 29 20 2d 20 31 0a 20 20 20 20 20 20 20 20  ts) - 1.        
0e70: 20 20 20 20 20 20 20 20 20 20 20 20 6c 65 74 20              let 
0e80: 6e 62 69 74 73 20 3d 20 6d 65 6d 3a 3a 73 69 7a  nbits = mem::siz
0e90: 65 5f 6f 66 3a 3a 3c 24 74 79 3e 28 29 20 2a 20  e_of::<$ty>() * 
0ea0: 38 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  8;.             
0eb0: 20 20 20 20 20 20 20 6c 65 74 20 76 20 3d 20 28         let v = (
0ec0: 73 65 6c 66 20 61 73 20 24 62 69 67 74 79 29 20  self as $bigty) 
0ed0: 2a 20 28 6f 74 68 65 72 20 61 73 20 24 62 69 67  * (other as $big
0ee0: 74 79 29 20 2b 20 28 6f 74 68 65 72 32 20 61 73  ty) + (other2 as
0ef0: 20 24 62 69 67 74 79 29 20 2b 0a 20 20 20 20 20   $bigty) +.     
0f00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0f10: 20 20 20 20 20 20 20 28 63 61 72 72 79 20 61 73         (carry as
0f20: 20 24 62 69 67 74 79 29 3b 0a 20 20 20 20 20 20   $bigty);.      
0f30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 28 28                ((
0f40: 76 20 3e 3e 20 6e 62 69 74 73 29 20 61 73 20 24  v >> nbits) as $
0f50: 74 79 2c 20 76 20 61 73 20 24 74 79 29 0a 20 20  ty, v as $ty).  
0f60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a                }.
0f70: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0f80: 20 66 6e 20 66 75 6c 6c 5f 64 69 76 5f 72 65 6d   fn full_div_rem
0f90: 28 73 65 6c 66 2c 20 6f 74 68 65 72 3a 20 24 74  (self, other: $t
0fa0: 79 2c 20 62 6f 72 72 6f 77 3a 20 24 74 79 29 20  y, borrow: $ty) 
0fb0: 2d 3e 20 28 24 74 79 2c 20 24 74 79 29 20 7b 0a  -> ($ty, $ty) {.
0fc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0fd0: 20 20 20 20 64 65 62 75 67 5f 61 73 73 65 72 74      debug_assert
0fe0: 21 28 62 6f 72 72 6f 77 20 3c 20 6f 74 68 65 72  !(borrow < other
0ff0: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  );.             
1000: 20 20 20 20 20 20 20 2f 2f 20 74 68 69 73 20 63         // this c
1010: 61 6e 6e 6f 74 20 6f 76 65 72 66 6c 6f 77 2c 20  annot overflow, 
1020: 74 68 65 20 64 69 76 69 64 65 6e 64 20 69 73 20  the dividend is 
1030: 62 65 74 77 65 65 6e 20 30 20 61 6e 64 20 6f 74  between 0 and ot
1040: 68 65 72 20 2a 20 32 5e 6e 62 69 74 73 20 2d 20  her * 2^nbits - 
1050: 31 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  1.              
1060: 20 20 20 20 20 20 6c 65 74 20 6e 62 69 74 73 20        let nbits 
1070: 3d 20 6d 65 6d 3a 3a 73 69 7a 65 5f 6f 66 3a 3a  = mem::size_of::
1080: 3c 24 74 79 3e 28 29 20 2a 20 38 3b 0a 20 20 20  <$ty>() * 8;.   
1090: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
10a0: 20 6c 65 74 20 6c 68 73 20 3d 20 28 28 62 6f 72   let lhs = ((bor
10b0: 72 6f 77 20 61 73 20 24 62 69 67 74 79 29 20 3c  row as $bigty) <
10c0: 3c 20 6e 62 69 74 73 29 20 7c 20 28 73 65 6c 66  < nbits) | (self
10d0: 20 61 73 20 24 62 69 67 74 79 29 3b 0a 20 20 20   as $bigty);.   
10e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
10f0: 20 6c 65 74 20 72 68 73 20 3d 20 6f 74 68 65 72   let rhs = other
1100: 20 61 73 20 24 62 69 67 74 79 3b 0a 20 20 20 20   as $bigty;.    
1110: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1120: 28 28 6c 68 73 20 2f 20 72 68 73 29 20 61 73 20  ((lhs / rhs) as 
1130: 24 74 79 2c 20 28 6c 68 73 20 25 20 72 68 73 29  $ty, (lhs % rhs)
1140: 20 61 73 20 24 74 79 29 0a 20 20 20 20 20 20 20   as $ty).       
1150: 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20           }.     
1160: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20         }.       
1170: 20 29 2a 0a 20 20 20 20 29 0a 7d 0a 0a 69 6d 70   )*.    ).}..imp
1180: 6c 5f 66 75 6c 6c 5f 6f 70 73 21 20 7b 0a 20 20  l_full_ops! {.  
1190: 20 20 75 38 3a 20 20 61 64 64 28 69 6e 74 72 69    u8:  add(intri
11a0: 6e 73 69 63 73 3a 3a 75 38 5f 61 64 64 5f 77 69  nsics::u8_add_wi
11b0: 74 68 5f 6f 76 65 72 66 6c 6f 77 29 2c 20 20 6d  th_overflow),  m
11c0: 75 6c 2f 64 69 76 28 75 31 36 29 3b 0a 20 20 20  ul/div(u16);.   
11d0: 20 75 31 36 3a 20 61 64 64 28 69 6e 74 72 69 6e   u16: add(intrin
11e0: 73 69 63 73 3a 3a 75 31 36 5f 61 64 64 5f 77 69  sics::u16_add_wi
11f0: 74 68 5f 6f 76 65 72 66 6c 6f 77 29 2c 20 6d 75  th_overflow), mu
1200: 6c 2f 64 69 76 28 75 33 32 29 3b 0a 20 20 20 20  l/div(u32);.    
1210: 75 33 32 3a 20 61 64 64 28 69 6e 74 72 69 6e 73  u32: add(intrins
1220: 69 63 73 3a 3a 75 33 32 5f 61 64 64 5f 77 69 74  ics::u32_add_wit
1230: 68 5f 6f 76 65 72 66 6c 6f 77 29 2c 20 6d 75 6c  h_overflow), mul
1240: 2f 64 69 76 28 75 36 34 29 3b 0a 2f 2f 20 20 75  /div(u64);.//  u
1250: 36 34 3a 20 61 64 64 28 69 6e 74 72 69 6e 73 69  64: add(intrinsi
1260: 63 73 3a 3a 75 36 34 5f 61 64 64 5f 77 69 74 68  cs::u64_add_with
1270: 5f 6f 76 65 72 66 6c 6f 77 29 2c 20 6d 75 6c 2f  _overflow), mul/
1280: 64 69 76 28 75 31 32 38 29 3b 20 2f 2f 20 73 65  div(u128); // se
1290: 65 20 52 46 43 20 23 35 32 31 20 66 6f 72 20 65  e RFC #521 for e
12a0: 6e 61 62 6c 69 6e 67 20 74 68 69 73 2e 0a 7d 0a  nabling this..}.
12b0: 0a 2f 2f 2f 20 54 61 62 6c 65 20 6f 66 20 70 6f  ./// Table of po
12c0: 77 65 72 73 20 6f 66 20 35 20 72 65 70 72 65 73  wers of 5 repres
12d0: 65 6e 74 61 62 6c 65 20 69 6e 20 64 69 67 69 74  entable in digit
12e0: 73 2e 20 53 70 65 63 69 66 69 63 61 6c 6c 79 2c  s. Specifically,
12f0: 20 74 68 65 20 6c 61 72 67 65 73 74 20 7b 75 38   the largest {u8
1300: 2c 20 75 31 36 2c 20 75 33 32 7d 20 76 61 6c 75  , u16, u32} valu
1310: 65 0a 2f 2f 2f 20 74 68 61 74 27 73 20 61 20 70  e./// that's a p
1320: 6f 77 65 72 20 6f 66 20 66 69 76 65 2c 20 70 6c  ower of five, pl
1330: 75 73 20 74 68 65 20 63 6f 72 72 65 73 70 6f 6e  us the correspon
1340: 64 69 6e 67 20 65 78 70 6f 6e 65 6e 74 2e 20 55  ding exponent. U
1350: 73 65 64 20 69 6e 20 60 6d 75 6c 5f 70 6f 77 35  sed in `mul_pow5
1360: 60 2e 0a 63 6f 6e 73 74 20 53 4d 41 4c 4c 5f 50  `..const SMALL_P
1370: 4f 57 35 3a 20 5b 28 75 36 34 2c 20 75 73 69 7a  OW5: [(u64, usiz
1380: 65 29 3b 20 33 5d 20 3d 20 5b 28 31 32 35 2c 20  e); 3] = [(125, 
1390: 33 29 2c 20 28 31 35 36 32 35 2c 20 36 29 2c 20  3), (15625, 6), 
13a0: 28 31 5f 32 32 30 5f 37 30 33 5f 31 32 35 2c 20  (1_220_703_125, 
13b0: 31 33 29 5d 3b 0a 0a 6d 61 63 72 6f 5f 72 75 6c  13)];..macro_rul
13c0: 65 73 21 20 64 65 66 69 6e 65 5f 62 69 67 6e 75  es! define_bignu
13d0: 6d 20 7b 0a 20 20 20 20 28 24 6e 61 6d 65 3a 69  m {.    ($name:i
13e0: 64 65 6e 74 3a 20 74 79 70 65 3d 24 74 79 3a 74  dent: type=$ty:t
13f0: 79 2c 20 6e 3d 24 6e 3a 65 78 70 72 29 20 3d 3e  y, n=$n:expr) =>
1400: 20 28 0a 20 20 20 20 20 20 20 20 2f 2f 2f 20 53   (.        /// S
1410: 74 61 63 6b 2d 61 6c 6c 6f 63 61 74 65 64 20 61  tack-allocated a
1420: 72 62 69 74 72 61 72 79 2d 70 72 65 63 69 73 69  rbitrary-precisi
1430: 6f 6e 20 28 75 70 20 74 6f 20 63 65 72 74 61 69  on (up to certai
1440: 6e 20 6c 69 6d 69 74 29 20 69 6e 74 65 67 65 72  n limit) integer
1450: 2e 0a 20 20 20 20 20 20 20 20 2f 2f 2f 0a 20 20  ..        ///.  
1460: 20 20 20 20 20 20 2f 2f 2f 20 54 68 69 73 20 69        /// This i
1470: 73 20 62 61 63 6b 65 64 20 62 79 20 61 20 66 69  s backed by a fi
1480: 78 65 64 2d 73 69 7a 65 20 61 72 72 61 79 20 6f  xed-size array o
1490: 66 20 67 69 76 65 6e 20 74 79 70 65 20 28 22 64  f given type ("d
14a0: 69 67 69 74 22 29 2e 0a 20 20 20 20 20 20 20 20  igit")..        
14b0: 2f 2f 2f 20 57 68 69 6c 65 20 74 68 65 20 61 72  /// While the ar
14c0: 72 61 79 20 69 73 20 6e 6f 74 20 76 65 72 79 20  ray is not very 
14d0: 6c 61 72 67 65 20 28 6e 6f 72 6d 61 6c 6c 79 20  large (normally 
14e0: 73 6f 6d 65 20 68 75 6e 64 72 65 64 20 62 79 74  some hundred byt
14f0: 65 73 29 2c 0a 20 20 20 20 20 20 20 20 2f 2f 2f  es),.        ///
1500: 20 63 6f 70 79 69 6e 67 20 69 74 20 72 65 63 6b   copying it reck
1510: 6c 65 73 73 6c 79 20 6d 61 79 20 72 65 73 75 6c  lessly may resul
1520: 74 20 69 6e 20 74 68 65 20 70 65 72 66 6f 72 6d  t in the perform
1530: 61 6e 63 65 20 68 69 74 2e 0a 20 20 20 20 20 20  ance hit..      
1540: 20 20 2f 2f 2f 20 54 68 75 73 20 74 68 69 73 20    /// Thus this 
1550: 69 73 20 69 6e 74 65 6e 74 69 6f 6e 61 6c 6c 79  is intentionally
1560: 20 6e 6f 74 20 60 43 6f 70 79 60 2e 0a 20 20 20   not `Copy`..   
1570: 20 20 20 20 20 2f 2f 2f 0a 20 20 20 20 20 20 20       ///.       
1580: 20 2f 2f 2f 20 41 6c 6c 20 6f 70 65 72 61 74 69   /// All operati
1590: 6f 6e 73 20 61 76 61 69 6c 61 62 6c 65 20 74 6f  ons available to
15a0: 20 62 69 67 6e 75 6d 73 20 70 61 6e 69 63 20 69   bignums panic i
15b0: 6e 20 74 68 65 20 63 61 73 65 20 6f 66 20 6f 76  n the case of ov
15c0: 65 72 2f 75 6e 64 65 72 66 6c 6f 77 73 2e 0a 20  er/underflows.. 
15d0: 20 20 20 20 20 20 20 2f 2f 2f 20 54 68 65 20 63         /// The c
15e0: 61 6c 6c 65 72 20 69 73 20 72 65 73 70 6f 6e 73  aller is respons
15f0: 69 62 6c 65 20 74 6f 20 75 73 65 20 6c 61 72 67  ible to use larg
1600: 65 20 65 6e 6f 75 67 68 20 62 69 67 6e 75 6d 20  e enough bignum 
1610: 74 79 70 65 73 2e 0a 20 20 20 20 20 20 20 20 70  types..        p
1620: 75 62 20 73 74 72 75 63 74 20 24 6e 61 6d 65 20  ub struct $name 
1630: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 2f 2f  {.            //
1640: 2f 20 4f 6e 65 20 70 6c 75 73 20 74 68 65 20 6f  / One plus the o
1650: 66 66 73 65 74 20 74 6f 20 74 68 65 20 6d 61 78  ffset to the max
1660: 69 6d 75 6d 20 22 64 69 67 69 74 22 20 69 6e 20  imum "digit" in 
1670: 75 73 65 2e 0a 20 20 20 20 20 20 20 20 20 20 20  use..           
1680: 20 2f 2f 2f 20 54 68 69 73 20 64 6f 65 73 20 6e   /// This does n
1690: 6f 74 20 64 65 63 72 65 61 73 65 2c 20 73 6f 20  ot decrease, so 
16a0: 62 65 20 61 77 61 72 65 20 6f 66 20 74 68 65 20  be aware of the 
16b0: 63 6f 6d 70 75 74 61 74 69 6f 6e 20 6f 72 64 65  computation orde
16c0: 72 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 2f  r..            /
16d0: 2f 2f 20 60 62 61 73 65 5b 73 69 7a 65 2e 2e 5d  // `base[size..]
16e0: 60 20 73 68 6f 75 6c 64 20 62 65 20 7a 65 72 6f  ` should be zero
16f0: 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 73 69  ..            si
1700: 7a 65 3a 20 75 73 69 7a 65 2c 0a 20 20 20 20 20  ze: usize,.     
1710: 20 20 20 20 20 20 20 2f 2f 2f 20 44 69 67 69 74         /// Digit
1720: 73 2e 20 60 5b 61 2c 20 62 2c 20 63 2c 20 2e 2e  s. `[a, b, c, ..
1730: 2e 5d 60 20 72 65 70 72 65 73 65 6e 74 73 20 60  .]` represents `
1740: 61 20 2b 20 62 2a 32 5e 57 20 2b 20 63 2a 32 5e  a + b*2^W + c*2^
1750: 28 32 57 29 20 2b 20 2e 2e 2e 60 0a 20 20 20 20  (2W) + ...`.    
1760: 20 20 20 20 20 20 20 20 2f 2f 2f 20 77 68 65 72          /// wher
1770: 65 20 60 57 60 20 69 73 20 74 68 65 20 6e 75 6d  e `W` is the num
1780: 62 65 72 20 6f 66 20 62 69 74 73 20 69 6e 20 74  ber of bits in t
1790: 68 65 20 64 69 67 69 74 20 74 79 70 65 2e 0a 20  he digit type.. 
17a0: 20 20 20 20 20 20 20 20 20 20 20 62 61 73 65 3a             base:
17b0: 20 5b 24 74 79 3b 20 24 6e 5d 0a 20 20 20 20 20   [$ty; $n].     
17c0: 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 69 6d     }..        im
17d0: 70 6c 20 24 6e 61 6d 65 20 7b 0a 20 20 20 20 20  pl $name {.     
17e0: 20 20 20 20 20 20 20 2f 2f 2f 20 4d 61 6b 65 73         /// Makes
17f0: 20 61 20 62 69 67 6e 75 6d 20 66 72 6f 6d 20 6f   a bignum from o
1800: 6e 65 20 64 69 67 69 74 2e 0a 20 20 20 20 20 20  ne digit..      
1810: 20 20 20 20 20 20 70 75 62 20 66 6e 20 66 72 6f        pub fn fro
1820: 6d 5f 73 6d 61 6c 6c 28 76 3a 20 24 74 79 29 20  m_small(v: $ty) 
1830: 2d 3e 20 24 6e 61 6d 65 20 7b 0a 20 20 20 20 20  -> $name {.     
1840: 20 20 20 20 20 20 20 20 20 20 20 6c 65 74 20 6d             let m
1850: 75 74 20 62 61 73 65 20 3d 20 5b 30 3b 20 24 6e  ut base = [0; $n
1860: 5d 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ];.             
1870: 20 20 20 62 61 73 65 5b 30 5d 20 3d 20 76 3b 0a     base[0] = v;.
1880: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1890: 24 6e 61 6d 65 20 7b 20 73 69 7a 65 3a 20 31 2c  $name { size: 1,
18a0: 20 62 61 73 65 3a 20 62 61 73 65 20 7d 0a 20 20   base: base }.  
18b0: 20 20 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20            }..   
18c0: 20 20 20 20 20 20 20 20 20 2f 2f 2f 20 4d 61 6b           /// Mak
18d0: 65 73 20 61 20 62 69 67 6e 75 6d 20 66 72 6f 6d  es a bignum from
18e0: 20 60 75 36 34 60 20 76 61 6c 75 65 2e 0a 20 20   `u64` value..  
18f0: 20 20 20 20 20 20 20 20 20 20 70 75 62 20 66 6e            pub fn
1900: 20 66 72 6f 6d 5f 75 36 34 28 6d 75 74 20 76 3a   from_u64(mut v:
1910: 20 75 36 34 29 20 2d 3e 20 24 6e 61 6d 65 20 7b   u64) -> $name {
1920: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1930: 20 75 73 65 20 6d 65 6d 3b 0a 0a 20 20 20 20 20   use mem;..     
1940: 20 20 20 20 20 20 20 20 20 20 20 6c 65 74 20 6d             let m
1950: 75 74 20 62 61 73 65 20 3d 20 5b 30 3b 20 24 6e  ut base = [0; $n
1960: 5d 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ];.             
1970: 20 20 20 6c 65 74 20 6d 75 74 20 73 7a 20 3d 20     let mut sz = 
1980: 30 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  0;.             
1990: 20 20 20 77 68 69 6c 65 20 76 20 3e 20 30 20 7b     while v > 0 {
19a0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
19b0: 20 20 20 20 20 62 61 73 65 5b 73 7a 5d 20 3d 20       base[sz] = 
19c0: 76 20 61 73 20 24 74 79 3b 0a 20 20 20 20 20 20  v as $ty;.      
19d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 76 20                v 
19e0: 3e 3e 3d 20 6d 65 6d 3a 3a 73 69 7a 65 5f 6f 66  >>= mem::size_of
19f0: 3a 3a 3c 24 74 79 3e 28 29 20 2a 20 38 3b 0a 20  ::<$ty>() * 8;. 
1a00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1a10: 20 20 20 73 7a 20 2b 3d 20 31 3b 0a 20 20 20 20     sz += 1;.    
1a20: 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20              }.  
1a30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 24 6e                $n
1a40: 61 6d 65 20 7b 20 73 69 7a 65 3a 20 73 7a 2c 20  ame { size: sz, 
1a50: 62 61 73 65 3a 20 62 61 73 65 20 7d 0a 20 20 20  base: base }.   
1a60: 20 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20           }..    
1a70: 20 20 20 20 20 20 20 20 2f 2f 2f 20 52 65 74 75          /// Retu
1a80: 72 6e 73 20 74 68 65 20 69 6e 74 65 72 6e 61 6c  rns the internal
1a90: 20 64 69 67 69 74 73 20 61 73 20 61 20 73 6c 69   digits as a sli
1aa0: 63 65 20 60 5b 61 2c 20 62 2c 20 63 2c 20 2e 2e  ce `[a, b, c, ..
1ab0: 2e 5d 60 20 73 75 63 68 20 74 68 61 74 20 74 68  .]` such that th
1ac0: 65 20 6e 75 6d 65 72 69 63 0a 20 20 20 20 20 20  e numeric.      
1ad0: 20 20 20 20 20 20 2f 2f 2f 20 76 61 6c 75 65 20        /// value 
1ae0: 69 73 20 60 61 20 2b 20 62 20 2a 20 32 5e 57 20  is `a + b * 2^W 
1af0: 2b 20 63 20 2a 20 32 5e 28 32 57 29 20 2b 20 2e  + c * 2^(2W) + .
1b00: 2e 2e 60 20 77 68 65 72 65 20 60 57 60 20 69 73  ..` where `W` is
1b10: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 62   the number of b
1b20: 69 74 73 20 69 6e 0a 20 20 20 20 20 20 20 20 20  its in.         
1b30: 20 20 20 2f 2f 2f 20 74 68 65 20 64 69 67 69 74     /// the digit
1b40: 20 74 79 70 65 2e 0a 20 20 20 20 20 20 20 20 20   type..         
1b50: 20 20 20 70 75 62 20 66 6e 20 64 69 67 69 74 73     pub fn digits
1b60: 28 26 73 65 6c 66 29 20 2d 3e 20 26 5b 24 74 79  (&self) -> &[$ty
1b70: 5d 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ] {.            
1b80: 20 20 20 20 26 73 65 6c 66 2e 62 61 73 65 5b 2e      &self.base[.
1b90: 2e 73 65 6c 66 2e 73 69 7a 65 5d 0a 20 20 20 20  .self.size].    
1ba0: 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20          }..     
1bb0: 20 20 20 20 20 20 20 2f 2f 2f 20 52 65 74 75 72         /// Retur
1bc0: 6e 73 20 74 68 65 20 60 69 60 2d 74 68 20 62 69  ns the `i`-th bi
1bd0: 74 20 77 68 65 72 65 20 62 69 74 20 30 20 69 73  t where bit 0 is
1be0: 20 74 68 65 20 6c 65 61 73 74 20 73 69 67 6e 69   the least signi
1bf0: 66 69 63 61 6e 74 20 6f 6e 65 2e 0a 20 20 20 20  ficant one..    
1c00: 20 20 20 20 20 20 20 20 2f 2f 2f 20 49 6e 20 6f          /// In o
1c10: 74 68 65 72 20 77 6f 72 64 73 2c 20 74 68 65 20  ther words, the 
1c20: 62 69 74 20 77 69 74 68 20 77 65 69 67 68 74 20  bit with weight 
1c30: 60 32 5e 69 60 2e 0a 20 20 20 20 20 20 20 20 20  `2^i`..         
1c40: 20 20 20 70 75 62 20 66 6e 20 67 65 74 5f 62 69     pub fn get_bi
1c50: 74 28 26 73 65 6c 66 2c 20 69 3a 20 75 73 69 7a  t(&self, i: usiz
1c60: 65 29 20 2d 3e 20 75 38 20 7b 0a 20 20 20 20 20  e) -> u8 {.     
1c70: 20 20 20 20 20 20 20 20 20 20 20 75 73 65 20 6d             use m
1c80: 65 6d 3b 0a 0a 20 20 20 20 20 20 20 20 20 20 20  em;..           
1c90: 20 20 20 20 20 6c 65 74 20 64 69 67 69 74 62 69       let digitbi
1ca0: 74 73 20 3d 20 6d 65 6d 3a 3a 73 69 7a 65 5f 6f  ts = mem::size_o
1cb0: 66 3a 3a 3c 24 74 79 3e 28 29 20 2a 20 38 3b 0a  f::<$ty>() * 8;.
1cc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1cd0: 6c 65 74 20 64 20 3d 20 69 20 2f 20 64 69 67 69  let d = i / digi
1ce0: 74 62 69 74 73 3b 0a 20 20 20 20 20 20 20 20 20  tbits;.         
1cf0: 20 20 20 20 20 20 20 6c 65 74 20 62 20 3d 20 69         let b = i
1d00: 20 25 20 64 69 67 69 74 62 69 74 73 3b 0a 20 20   % digitbits;.  
1d10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 28 28                ((
1d20: 73 65 6c 66 2e 62 61 73 65 5b 64 5d 20 3e 3e 20  self.base[d] >> 
1d30: 62 29 20 26 20 31 29 20 61 73 20 75 38 0a 20 20  b) & 1) as u8.  
1d40: 20 20 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20            }..   
1d50: 20 20 20 20 20 20 20 20 20 2f 2f 2f 20 52 65 74           /// Ret
1d60: 75 72 6e 73 20 60 74 72 75 65 60 20 69 66 20 74  urns `true` if t
1d70: 68 65 20 62 69 67 6e 75 6d 20 69 73 20 7a 65 72  he bignum is zer
1d80: 6f 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 70  o..            p
1d90: 75 62 20 66 6e 20 69 73 5f 7a 65 72 6f 28 26 73  ub fn is_zero(&s
1da0: 65 6c 66 29 20 2d 3e 20 62 6f 6f 6c 20 7b 0a 20  elf) -> bool {. 
1db0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 73                 s
1dc0: 65 6c 66 2e 64 69 67 69 74 73 28 29 2e 69 74 65  elf.digits().ite
1dd0: 72 28 29 2e 61 6c 6c 28 7c 26 76 7c 20 76 20 3d  r().all(|&v| v =
1de0: 3d 20 30 29 0a 20 20 20 20 20 20 20 20 20 20 20  = 0).           
1df0: 20 7d 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20   }..            
1e00: 2f 2f 2f 20 52 65 74 75 72 6e 73 20 74 68 65 20  /// Returns the 
1e10: 6e 75 6d 62 65 72 20 6f 66 20 62 69 74 73 20 6e  number of bits n
1e20: 65 63 65 73 73 61 72 79 20 74 6f 20 72 65 70 72  ecessary to repr
1e30: 65 73 65 6e 74 20 74 68 69 73 20 76 61 6c 75 65  esent this value
1e40: 2e 20 4e 6f 74 65 20 74 68 61 74 20 7a 65 72 6f  . Note that zero
1e50: 0a 20 20 20 20 20 20 20 20 20 20 20 20 2f 2f 2f  .            ///
1e60: 20 69 73 20 63 6f 6e 73 69 64 65 72 65 64 20 74   is considered t
1e70: 6f 20 6e 65 65 64 20 30 20 62 69 74 73 2e 0a 20  o need 0 bits.. 
1e80: 20 20 20 20 20 20 20 20 20 20 20 70 75 62 20 66             pub f
1e90: 6e 20 62 69 74 5f 6c 65 6e 67 74 68 28 26 73 65  n bit_length(&se
1ea0: 6c 66 29 20 2d 3e 20 75 73 69 7a 65 20 7b 0a 20  lf) -> usize {. 
1eb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 75                 u
1ec0: 73 65 20 6d 65 6d 3b 0a 0a 20 20 20 20 20 20 20  se mem;..       
1ed0: 20 20 20 20 20 20 20 20 20 2f 2f 20 53 6b 69 70           // Skip
1ee0: 20 6f 76 65 72 20 74 68 65 20 6d 6f 73 74 20 73   over the most s
1ef0: 69 67 6e 69 66 69 63 61 6e 74 20 64 69 67 69 74  ignificant digit
1f00: 73 20 77 68 69 63 68 20 61 72 65 20 7a 65 72 6f  s which are zero
1f10: 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
1f20: 20 20 6c 65 74 20 64 69 67 69 74 73 20 3d 20 73    let digits = s
1f30: 65 6c 66 2e 64 69 67 69 74 73 28 29 3b 0a 20 20  elf.digits();.  
1f40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6c 65                le
1f50: 74 20 7a 65 72 6f 73 20 3d 20 64 69 67 69 74 73  t zeros = digits
1f60: 2e 69 74 65 72 28 29 2e 72 65 76 28 29 2e 74 61  .iter().rev().ta
1f70: 6b 65 5f 77 68 69 6c 65 28 7c 26 26 78 7c 20 78  ke_while(|&&x| x
1f80: 20 3d 3d 20 30 29 2e 63 6f 75 6e 74 28 29 3b 0a   == 0).count();.
1f90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1fa0: 6c 65 74 20 65 6e 64 20 3d 20 64 69 67 69 74 73  let end = digits
1fb0: 2e 6c 65 6e 28 29 20 2d 20 7a 65 72 6f 73 3b 0a  .len() - zeros;.
1fc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1fd0: 6c 65 74 20 6e 6f 6e 7a 65 72 6f 20 3d 20 26 64  let nonzero = &d
1fe0: 69 67 69 74 73 5b 2e 2e 65 6e 64 5d 3b 0a 0a 20  igits[..end];.. 
1ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69                 i
2000: 66 20 6e 6f 6e 7a 65 72 6f 2e 69 73 5f 65 6d 70  f nonzero.is_emp
2010: 74 79 28 29 20 7b 0a 20 20 20 20 20 20 20 20 20  ty() {.         
2020: 20 20 20 20 20 20 20 20 20 20 20 2f 2f 20 54 68             // Th
2030: 65 72 65 20 61 72 65 20 6e 6f 20 6e 6f 6e 2d 7a  ere are no non-z
2040: 65 72 6f 20 64 69 67 69 74 73 2c 20 69 2e 65 2e  ero digits, i.e.
2050: 20 74 68 65 20 6e 75 6d 62 65 72 20 69 73 20 7a   the number is z
2060: 65 72 6f 2e 0a 20 20 20 20 20 20 20 20 20 20 20  ero..           
2070: 20 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20           return 
2080: 30 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  0;.             
2090: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20     }.           
20a0: 20 20 20 20 20 2f 2f 20 54 68 69 73 20 63 6f 75       // This cou
20b0: 6c 64 20 62 65 20 6f 70 74 69 6d 69 7a 65 64 20  ld be optimized 
20c0: 77 69 74 68 20 6c 65 61 64 69 6e 67 5f 7a 65 72  with leading_zer
20d0: 6f 73 28 29 20 61 6e 64 20 62 69 74 20 73 68 69  os() and bit shi
20e0: 66 74 73 2c 20 62 75 74 20 74 68 61 74 27 73 0a  fts, but that's.
20f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2100: 2f 2f 20 70 72 6f 62 61 62 6c 79 20 6e 6f 74 20  // probably not 
2110: 77 6f 72 74 68 20 74 68 65 20 68 61 73 73 6c 65  worth the hassle
2120: 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
2130: 20 20 6c 65 74 20 64 69 67 69 74 62 69 74 73 20    let digitbits 
2140: 3d 20 6d 65 6d 3a 3a 73 69 7a 65 5f 6f 66 3a 3a  = mem::size_of::
2150: 3c 24 74 79 3e 28 29 2a 20 38 3b 0a 20 20 20 20  <$ty>()* 8;.    
2160: 20 20 20 20 20 20 20 20 20 20 20 20 6c 65 74 20              let 
2170: 6d 75 74 20 69 20 3d 20 6e 6f 6e 7a 65 72 6f 2e  mut i = nonzero.
2180: 6c 65 6e 28 29 20 2a 20 64 69 67 69 74 62 69 74  len() * digitbit
2190: 73 20 2d 20 31 3b 0a 20 20 20 20 20 20 20 20 20  s - 1;.         
21a0: 20 20 20 20 20 20 20 77 68 69 6c 65 20 73 65 6c         while sel
21b0: 66 2e 67 65 74 5f 62 69 74 28 69 29 20 3d 3d 20  f.get_bit(i) == 
21c0: 30 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  0 {.            
21d0: 20 20 20 20 20 20 20 20 69 20 2d 3d 20 31 3b 0a          i -= 1;.
21e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
21f0: 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  }.              
2200: 20 20 69 20 2b 20 31 0a 20 20 20 20 20 20 20 20    i + 1.        
2210: 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 20      }..         
2220: 20 20 20 2f 2f 2f 20 41 64 64 73 20 60 6f 74 68     /// Adds `oth
2230: 65 72 60 20 74 6f 20 69 74 73 65 6c 66 20 61 6e  er` to itself an
2240: 64 20 72 65 74 75 72 6e 73 20 69 74 73 20 6f 77  d returns its ow
2250: 6e 20 6d 75 74 61 62 6c 65 20 72 65 66 65 72 65  n mutable refere
2260: 6e 63 65 2e 0a 20 20 20 20 20 20 20 20 20 20 20  nce..           
2270: 20 70 75 62 20 66 6e 20 61 64 64 3c 27 61 3e 28   pub fn add<'a>(
2280: 26 27 61 20 6d 75 74 20 73 65 6c 66 2c 20 6f 74  &'a mut self, ot
2290: 68 65 72 3a 20 26 24 6e 61 6d 65 29 20 2d 3e 20  her: &$name) -> 
22a0: 26 27 61 20 6d 75 74 20 24 6e 61 6d 65 20 7b 0a  &'a mut $name {.
22b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
22c0: 75 73 65 20 63 6d 70 3b 0a 20 20 20 20 20 20 20  use cmp;.       
22d0: 20 20 20 20 20 20 20 20 20 75 73 65 20 6e 75 6d           use num
22e0: 3a 3a 62 69 67 6e 75 6d 3a 3a 46 75 6c 6c 4f 70  ::bignum::FullOp
22f0: 73 3b 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20  s;..            
2300: 20 20 20 20 6c 65 74 20 6d 75 74 20 73 7a 20 3d      let mut sz =
2310: 20 63 6d 70 3a 3a 6d 61 78 28 73 65 6c 66 2e 73   cmp::max(self.s
2320: 69 7a 65 2c 20 6f 74 68 65 72 2e 73 69 7a 65 29  ize, other.size)
2330: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
2340: 20 20 6c 65 74 20 6d 75 74 20 63 61 72 72 79 20    let mut carry 
2350: 3d 20 66 61 6c 73 65 3b 0a 20 20 20 20 20 20 20  = false;.       
2360: 20 20 20 20 20 20 20 20 20 66 6f 72 20 28 61 2c           for (a,
2370: 20 62 29 20 69 6e 20 73 65 6c 66 2e 62 61 73 65   b) in self.base
2380: 5b 2e 2e 73 7a 5d 2e 69 74 65 72 5f 6d 75 74 28  [..sz].iter_mut(
2390: 29 2e 7a 69 70 28 26 6f 74 68 65 72 2e 62 61 73  ).zip(&other.bas
23a0: 65 5b 2e 2e 73 7a 5d 29 20 7b 0a 20 20 20 20 20  e[..sz]) {.     
23b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6c                 l
23c0: 65 74 20 28 63 2c 20 76 29 20 3d 20 28 2a 61 29  et (c, v) = (*a)
23d0: 2e 66 75 6c 6c 5f 61 64 64 28 2a 62 2c 20 63 61  .full_add(*b, ca
23e0: 72 72 79 29 3b 0a 20 20 20 20 20 20 20 20 20 20  rry);.          
23f0: 20 20 20 20 20 20 20 20 20 20 2a 61 20 3d 20 76            *a = v
2400: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
2410: 20 20 20 20 20 20 63 61 72 72 79 20 3d 20 63 3b        carry = c;
2420: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2430: 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20   }.             
2440: 20 20 20 69 66 20 63 61 72 72 79 20 7b 0a 20 20     if carry {.  
2450: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2460: 20 20 73 65 6c 66 2e 62 61 73 65 5b 73 7a 5d 20    self.base[sz] 
2470: 3d 20 31 3b 0a 20 20 20 20 20 20 20 20 20 20 20  = 1;.           
2480: 20 20 20 20 20 20 20 20 20 73 7a 20 2b 3d 20 31           sz += 1
2490: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
24a0: 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20    }.            
24b0: 20 20 20 20 73 65 6c 66 2e 73 69 7a 65 20 3d 20      self.size = 
24c0: 73 7a 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  sz;.            
24d0: 20 20 20 20 73 65 6c 66 0a 20 20 20 20 20 20 20      self.       
24e0: 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20       }..        
24f0: 20 20 20 20 70 75 62 20 66 6e 20 61 64 64 5f 73      pub fn add_s
2500: 6d 61 6c 6c 28 26 6d 75 74 20 73 65 6c 66 2c 20  mall(&mut self, 
2510: 6f 74 68 65 72 3a 20 24 74 79 29 20 2d 3e 20 26  other: $ty) -> &
2520: 6d 75 74 20 24 6e 61 6d 65 20 7b 0a 20 20 20 20  mut $name {.    
2530: 20 20 20 20 20 20 20 20 20 20 20 20 75 73 65 20              use 
2540: 6e 75 6d 3a 3a 62 69 67 6e 75 6d 3a 3a 46 75 6c  num::bignum::Ful
2550: 6c 4f 70 73 3b 0a 0a 20 20 20 20 20 20 20 20 20  lOps;..         
2560: 20 20 20 20 20 20 20 6c 65 74 20 28 6d 75 74 20         let (mut 
2570: 63 61 72 72 79 2c 20 76 29 20 3d 20 73 65 6c 66  carry, v) = self
2580: 2e 62 61 73 65 5b 30 5d 2e 66 75 6c 6c 5f 61 64  .base[0].full_ad
2590: 64 28 6f 74 68 65 72 2c 20 66 61 6c 73 65 29 3b  d(other, false);
25a0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
25b0: 20 73 65 6c 66 2e 62 61 73 65 5b 30 5d 20 3d 20   self.base[0] = 
25c0: 76 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  v;.             
25d0: 20 20 20 6c 65 74 20 6d 75 74 20 69 20 3d 20 31     let mut i = 1
25e0: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
25f0: 20 20 77 68 69 6c 65 20 63 61 72 72 79 20 7b 0a    while carry {.
2600: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2610: 20 20 20 20 6c 65 74 20 28 63 2c 20 76 29 20 3d      let (c, v) =
2620: 20 73 65 6c 66 2e 62 61 73 65 5b 69 5d 2e 66 75   self.base[i].fu
2630: 6c 6c 5f 61 64 64 28 30 2c 20 63 61 72 72 79 29  ll_add(0, carry)
2640: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
2650: 20 20 20 20 20 20 73 65 6c 66 2e 62 61 73 65 5b        self.base[
2660: 69 5d 20 3d 20 76 3b 0a 20 20 20 20 20 20 20 20  i] = v;.        
2670: 20 20 20 20 20 20 20 20 20 20 20 20 63 61 72 72              carr
2680: 79 20 3d 20 63 3b 0a 20 20 20 20 20 20 20 20 20  y = c;.         
2690: 20 20 20 20 20 20 20 20 20 20 20 69 20 2b 3d 20             i += 
26a0: 31 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  1;.             
26b0: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20     }.           
26c0: 20 20 20 20 20 69 66 20 69 20 3e 20 73 65 6c 66       if i > self
26d0: 2e 73 69 7a 65 20 7b 0a 20 20 20 20 20 20 20 20  .size {.        
26e0: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
26f0: 2e 73 69 7a 65 20 3d 20 69 3b 0a 20 20 20 20 20  .size = i;.     
2700: 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20             }.   
2710: 20 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c               sel
2720: 66 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a  f.            }.
2730: 0a 20 20 20 20 20 20 20 20 20 20 20 20 2f 2f 2f  .            ///
2740: 20 53 75 62 74 72 61 63 74 73 20 60 6f 74 68 65   Subtracts `othe
2750: 72 60 20 66 72 6f 6d 20 69 74 73 65 6c 66 20 61  r` from itself a
2760: 6e 64 20 72 65 74 75 72 6e 73 20 69 74 73 20 6f  nd returns its o
2770: 77 6e 20 6d 75 74 61 62 6c 65 20 72 65 66 65 72  wn mutable refer
2780: 65 6e 63 65 2e 0a 20 20 20 20 20 20 20 20 20 20  ence..          
2790: 20 20 70 75 62 20 66 6e 20 73 75 62 3c 27 61 3e    pub fn sub<'a>
27a0: 28 26 27 61 20 6d 75 74 20 73 65 6c 66 2c 20 6f  (&'a mut self, o
27b0: 74 68 65 72 3a 20 26 24 6e 61 6d 65 29 20 2d 3e  ther: &$name) ->
27c0: 20 26 27 61 20 6d 75 74 20 24 6e 61 6d 65 20 7b   &'a mut $name {
27d0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
27e0: 20 75 73 65 20 63 6d 70 3b 0a 20 20 20 20 20 20   use cmp;.      
27f0: 20 20 20 20 20 20 20 20 20 20 75 73 65 20 6e 75            use nu
2800: 6d 3a 3a 62 69 67 6e 75 6d 3a 3a 46 75 6c 6c 4f  m::bignum::FullO
2810: 70 73 3b 0a 0a 20 20 20 20 20 20 20 20 20 20 20  ps;..           
2820: 20 20 20 20 20 6c 65 74 20 73 7a 20 3d 20 63 6d       let sz = cm
2830: 70 3a 3a 6d 61 78 28 73 65 6c 66 2e 73 69 7a 65  p::max(self.size
2840: 2c 20 6f 74 68 65 72 2e 73 69 7a 65 29 3b 0a 20  , other.size);. 
2850: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6c                 l
2860: 65 74 20 6d 75 74 20 6e 6f 62 6f 72 72 6f 77 20  et mut noborrow 
2870: 3d 20 74 72 75 65 3b 0a 20 20 20 20 20 20 20 20  = true;.        
2880: 20 20 20 20 20 20 20 20 66 6f 72 20 28 61 2c 20          for (a, 
2890: 62 29 20 69 6e 20 73 65 6c 66 2e 62 61 73 65 5b  b) in self.base[
28a0: 2e 2e 73 7a 5d 2e 69 74 65 72 5f 6d 75 74 28 29  ..sz].iter_mut()
28b0: 2e 7a 69 70 28 26 6f 74 68 65 72 2e 62 61 73 65  .zip(&other.base
28c0: 5b 2e 2e 73 7a 5d 29 20 7b 0a 20 20 20 20 20 20  [..sz]) {.      
28d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6c 65                le
28e0: 74 20 28 63 2c 20 76 29 20 3d 20 28 2a 61 29 2e  t (c, v) = (*a).
28f0: 66 75 6c 6c 5f 61 64 64 28 21 2a 62 2c 20 6e 6f  full_add(!*b, no
2900: 62 6f 72 72 6f 77 29 3b 0a 20 20 20 20 20 20 20  borrow);.       
2910: 20 20 20 20 20 20 20 20 20 20 20 20 20 2a 61 20               *a 
2920: 3d 20 76 3b 0a 20 20 20 20 20 20 20 20 20 20 20  = v;.           
2930: 20 20 20 20 20 20 20 20 20 6e 6f 62 6f 72 72 6f           noborro
2940: 77 20 3d 20 63 3b 0a 20 20 20 20 20 20 20 20 20  w = c;.         
2950: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20         }.       
2960: 20 20 20 20 20 20 20 20 20 61 73 73 65 72 74 21           assert!
2970: 28 6e 6f 62 6f 72 72 6f 77 29 3b 0a 20 20 20 20  (noborrow);.    
2980: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
2990: 2e 73 69 7a 65 20 3d 20 73 7a 3b 0a 20 20 20 20  .size = sz;.    
29a0: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
29b0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 0a  .            }..
29c0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2f 2f 20              /// 
29d0: 4d 75 6c 74 69 70 6c 69 65 73 20 69 74 73 65 6c  Multiplies itsel
29e0: 66 20 62 79 20 61 20 64 69 67 69 74 2d 73 69 7a  f by a digit-siz
29f0: 65 64 20 60 6f 74 68 65 72 60 20 61 6e 64 20 72  ed `other` and r
2a00: 65 74 75 72 6e 73 20 69 74 73 20 6f 77 6e 0a 20  eturns its own. 
2a10: 20 20 20 20 20 20 20 20 20 20 20 2f 2f 2f 20 6d             /// m
2a20: 75 74 61 62 6c 65 20 72 65 66 65 72 65 6e 63 65  utable reference
2a30: 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 70 75  ..            pu
2a40: 62 20 66 6e 20 6d 75 6c 5f 73 6d 61 6c 6c 28 26  b fn mul_small(&
2a50: 6d 75 74 20 73 65 6c 66 2c 20 6f 74 68 65 72 3a  mut self, other:
2a60: 20 24 74 79 29 20 2d 3e 20 26 6d 75 74 20 24 6e   $ty) -> &mut $n
2a70: 61 6d 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20  ame {.          
2a80: 20 20 20 20 20 20 75 73 65 20 6e 75 6d 3a 3a 62        use num::b
2a90: 69 67 6e 75 6d 3a 3a 46 75 6c 6c 4f 70 73 3b 0a  ignum::FullOps;.
2aa0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2ab0: 20 6c 65 74 20 6d 75 74 20 73 7a 20 3d 20 73 65   let mut sz = se
2ac0: 6c 66 2e 73 69 7a 65 3b 0a 20 20 20 20 20 20 20  lf.size;.       
2ad0: 20 20 20 20 20 20 20 20 20 6c 65 74 20 6d 75 74           let mut
2ae0: 20 63 61 72 72 79 20 3d 20 30 3b 0a 20 20 20 20   carry = 0;.    
2af0: 20 20 20 20 20 20 20 20 20 20 20 20 66 6f 72 20              for 
2b00: 61 20 69 6e 20 26 6d 75 74 20 73 65 6c 66 2e 62  a in &mut self.b
2b10: 61 73 65 5b 2e 2e 73 7a 5d 20 7b 0a 20 20 20 20  ase[..sz] {.    
2b20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2b30: 6c 65 74 20 28 63 2c 20 76 29 20 3d 20 28 2a 61  let (c, v) = (*a
2b40: 29 2e 66 75 6c 6c 5f 6d 75 6c 28 6f 74 68 65 72  ).full_mul(other
2b50: 2c 20 63 61 72 72 79 29 3b 0a 20 20 20 20 20 20  , carry);.      
2b60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2a 61                *a
2b70: 20 3d 20 76 3b 0a 20 20 20 20 20 20 20 20 20 20   = v;.          
2b80: 20 20 20 20 20 20 20 20 20 20 63 61 72 72 79 20            carry 
2b90: 3d 20 63 3b 0a 20 20 20 20 20 20 20 20 20 20 20  = c;.           
2ba0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20       }.         
2bb0: 20 20 20 20 20 20 20 69 66 20 63 61 72 72 79 20         if carry 
2bc0: 3e 20 30 20 7b 0a 20 20 20 20 20 20 20 20 20 20  > 0 {.          
2bd0: 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e 62            self.b
2be0: 61 73 65 5b 73 7a 5d 20 3d 20 63 61 72 72 79 3b  ase[sz] = carry;
2bf0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2c00: 20 20 20 20 20 73 7a 20 2b 3d 20 31 3b 0a 20 20       sz += 1;.  
2c10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a                }.
2c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2c30: 73 65 6c 66 2e 73 69 7a 65 20 3d 20 73 7a 3b 0a  self.size = sz;.
2c40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2c50: 73 65 6c 66 0a 20 20 20 20 20 20 20 20 20 20 20  self.           
2c60: 20 7d 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20   }..            
2c70: 2f 2f 2f 20 4d 75 6c 74 69 70 6c 69 65 73 20 69  /// Multiplies i
2c80: 74 73 65 6c 66 20 62 79 20 60 32 5e 62 69 74 73  tself by `2^bits
2c90: 60 20 61 6e 64 20 72 65 74 75 72 6e 73 20 69 74  ` and returns it
2ca0: 73 20 6f 77 6e 20 6d 75 74 61 62 6c 65 20 72 65  s own mutable re
2cb0: 66 65 72 65 6e 63 65 2e 0a 20 20 20 20 20 20 20  ference..       
2cc0: 20 20 20 20 20 70 75 62 20 66 6e 20 6d 75 6c 5f       pub fn mul_
2cd0: 70 6f 77 32 28 26 6d 75 74 20 73 65 6c 66 2c 20  pow2(&mut self, 
2ce0: 62 69 74 73 3a 20 75 73 69 7a 65 29 20 2d 3e 20  bits: usize) -> 
2cf0: 26 6d 75 74 20 24 6e 61 6d 65 20 7b 0a 20 20 20  &mut $name {.   
2d00: 20 20 20 20 20 20 20 20 20 20 20 20 20 75 73 65               use
2d10: 20 6d 65 6d 3b 0a 0a 20 20 20 20 20 20 20 20 20   mem;..         
2d20: 20 20 20 20 20 20 20 6c 65 74 20 64 69 67 69 74         let digit
2d30: 62 69 74 73 20 3d 20 6d 65 6d 3a 3a 73 69 7a 65  bits = mem::size
2d40: 5f 6f 66 3a 3a 3c 24 74 79 3e 28 29 20 2a 20 38  _of::<$ty>() * 8
2d50: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
2d60: 20 20 6c 65 74 20 64 69 67 69 74 73 20 3d 20 62    let digits = b
2d70: 69 74 73 20 2f 20 64 69 67 69 74 62 69 74 73 3b  its / digitbits;
2d80: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2d90: 20 6c 65 74 20 62 69 74 73 20 3d 20 62 69 74 73   let bits = bits
2da0: 20 25 20 64 69 67 69 74 62 69 74 73 3b 0a 0a 20   % digitbits;.. 
2db0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 61                 a
2dc0: 73 73 65 72 74 21 28 64 69 67 69 74 73 20 3c 20  ssert!(digits < 
2dd0: 24 6e 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20  $n);.           
2de0: 20 20 20 20 20 64 65 62 75 67 5f 61 73 73 65 72       debug_asser
2df0: 74 21 28 73 65 6c 66 2e 62 61 73 65 5b 24 6e 2d  t!(self.base[$n-
2e00: 64 69 67 69 74 73 2e 2e 5d 2e 69 74 65 72 28 29  digits..].iter()
2e10: 2e 61 6c 6c 28 7c 26 76 7c 20 76 20 3d 3d 20 30  .all(|&v| v == 0
2e20: 29 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ));.            
2e30: 20 20 20 20 64 65 62 75 67 5f 61 73 73 65 72 74      debug_assert
2e40: 21 28 62 69 74 73 20 3d 3d 20 30 20 7c 7c 20 28  !(bits == 0 || (
2e50: 73 65 6c 66 2e 62 61 73 65 5b 24 6e 2d 64 69 67  self.base[$n-dig
2e60: 69 74 73 2d 31 5d 20 3e 3e 20 28 64 69 67 69 74  its-1] >> (digit
2e70: 62 69 74 73 20 2d 20 62 69 74 73 29 29 20 3d 3d  bits - bits)) ==
2e80: 20 30 29 3b 0a 0a 20 20 20 20 20 20 20 20 20 20   0);..          
2e90: 20 20 20 20 20 20 2f 2f 20 73 68 69 66 74 20 62        // shift b
2ea0: 79 20 60 64 69 67 69 74 73 20 2a 20 64 69 67 69  y `digits * digi
2eb0: 74 62 69 74 73 60 20 62 69 74 73 0a 20 20 20 20  tbits` bits.    
2ec0: 20 20 20 20 20 20 20 20 20 20 20 20 66 6f 72 20              for 
2ed0: 69 20 69 6e 20 28 30 2e 2e 73 65 6c 66 2e 73 69  i in (0..self.si
2ee0: 7a 65 29 2e 72 65 76 28 29 20 7b 0a 20 20 20 20  ze).rev() {.    
2ef0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2f00: 73 65 6c 66 2e 62 61 73 65 5b 69 2b 64 69 67 69  self.base[i+digi
2f10: 74 73 5d 20 3d 20 73 65 6c 66 2e 62 61 73 65 5b  ts] = self.base[
2f20: 69 5d 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  i];.            
2f30: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20      }.          
2f40: 20 20 20 20 20 20 66 6f 72 20 69 20 69 6e 20 30        for i in 0
2f50: 2e 2e 64 69 67 69 74 73 20 7b 0a 20 20 20 20 20  ..digits {.     
2f60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 73                 s
2f70: 65 6c 66 2e 62 61 73 65 5b 69 5d 20 3d 20 30 3b  elf.base[i] = 0;
2f80: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2f90: 20 7d 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20   }..            
2fa0: 20 20 20 20 2f 2f 20 73 68 69 66 74 20 62 79 20      // shift by 
2fb0: 60 62 69 74 73 60 20 62 69 74 73 0a 20 20 20 20  `bits` bits.    
2fc0: 20 20 20 20 20 20 20 20 20 20 20 20 6c 65 74 20              let 
2fd0: 6d 75 74 20 73 7a 20 3d 20 73 65 6c 66 2e 73 69  mut sz = self.si
2fe0: 7a 65 20 2b 20 64 69 67 69 74 73 3b 0a 20 20 20  ze + digits;.   
2ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20               if 
3000: 62 69 74 73 20 3e 20 30 20 7b 0a 20 20 20 20 20  bits > 0 {.     
3010: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6c                 l
3020: 65 74 20 6c 61 73 74 20 3d 20 73 7a 3b 0a 20 20  et last = sz;.  
3030: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3040: 20 20 6c 65 74 20 6f 76 65 72 66 6c 6f 77 20 3d    let overflow =
3050: 20 73 65 6c 66 2e 62 61 73 65 5b 6c 61 73 74 2d   self.base[last-
3060: 31 5d 20 3e 3e 20 28 64 69 67 69 74 62 69 74 73  1] >> (digitbits
3070: 20 2d 20 62 69 74 73 29 3b 0a 20 20 20 20 20 20   - bits);.      
3080: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66                if
3090: 20 6f 76 65 72 66 6c 6f 77 20 3e 20 30 20 7b 0a   overflow > 0 {.
30a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
30b0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 62 61 73          self.bas
30c0: 65 5b 6c 61 73 74 5d 20 3d 20 6f 76 65 72 66 6c  e[last] = overfl
30d0: 6f 77 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ow;.            
30e0: 20 20 20 20 20 20 20 20 20 20 20 20 73 7a 20 2b              sz +
30f0: 3d 20 31 3b 0a 20 20 20 20 20 20 20 20 20 20 20  = 1;.           
3100: 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20           }.     
3110: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66                 f
3120: 6f 72 20 69 20 69 6e 20 28 64 69 67 69 74 73 2b  or i in (digits+
3130: 31 2e 2e 6c 61 73 74 29 2e 72 65 76 28 29 20 7b  1..last).rev() {
3140: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
3150: 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e 62 61           self.ba
3160: 73 65 5b 69 5d 20 3d 20 28 73 65 6c 66 2e 62 61  se[i] = (self.ba
3170: 73 65 5b 69 5d 20 3c 3c 20 62 69 74 73 29 20 7c  se[i] << bits) |
3180: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
3190: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
31a0: 20 20 20 20 20 20 20 20 28 73 65 6c 66 2e 62 61          (self.ba
31b0: 73 65 5b 69 2d 31 5d 20 3e 3e 20 28 64 69 67 69  se[i-1] >> (digi
31c0: 74 62 69 74 73 20 2d 20 62 69 74 73 29 29 3b 0a  tbits - bits));.
31d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
31e0: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20      }.          
31f0: 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e 62            self.b
3200: 61 73 65 5b 64 69 67 69 74 73 5d 20 3c 3c 3d 20  ase[digits] <<= 
3210: 62 69 74 73 3b 0a 20 20 20 20 20 20 20 20 20 20  bits;.          
3220: 20 20 20 20 20 20 20 20 20 20 2f 2f 20 73 65 6c            // sel
3230: 66 2e 62 61 73 65 5b 2e 2e 64 69 67 69 74 73 5d  f.base[..digits]
3240: 20 69 73 20 7a 65 72 6f 2c 20 6e 6f 20 6e 65 65   is zero, no nee
3250: 64 20 74 6f 20 73 68 69 66 74 0a 20 20 20 20 20  d to shift.     
3260: 20 20 20 20 20 20 20 20 20 20 20 7d 0a 0a 20 20             }..  
3270: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 73 65                se
3280: 6c 66 2e 73 69 7a 65 20 3d 20 73 7a 3b 0a 20 20  lf.size = sz;.  
3290: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 73 65                se
32a0: 6c 66 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d  lf.            }
32b0: 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 2f 2f  ..            //
32c0: 2f 20 4d 75 6c 74 69 70 6c 69 65 73 20 69 74 73  / Multiplies its
32d0: 65 6c 66 20 62 79 20 60 35 5e 65 60 20 61 6e 64  elf by `5^e` and
32e0: 20 72 65 74 75 72 6e 73 20 69 74 73 20 6f 77 6e   returns its own
32f0: 20 6d 75 74 61 62 6c 65 20 72 65 66 65 72 65 6e   mutable referen
3300: 63 65 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20  ce..            
3310: 70 75 62 20 66 6e 20 6d 75 6c 5f 70 6f 77 35 28  pub fn mul_pow5(
3320: 26 6d 75 74 20 73 65 6c 66 2c 20 6d 75 74 20 65  &mut self, mut e
3330: 3a 20 75 73 69 7a 65 29 20 2d 3e 20 26 6d 75 74  : usize) -> &mut
3340: 20 24 6e 61 6d 65 20 7b 0a 20 20 20 20 20 20 20   $name {.       
3350: 20 20 20 20 20 20 20 20 20 75 73 65 20 6d 65 6d           use mem
3360: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
3370: 20 20 75 73 65 20 6e 75 6d 3a 3a 62 69 67 6e 75    use num::bignu
3380: 6d 3a 3a 53 4d 41 4c 4c 5f 50 4f 57 35 3b 0a 0a  m::SMALL_POW5;..
3390: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
33a0: 2f 2f 20 54 68 65 72 65 20 61 72 65 20 65 78 61  // There are exa
33b0: 63 74 6c 79 20 6e 20 74 72 61 69 6c 69 6e 67 20  ctly n trailing 
33c0: 7a 65 72 6f 73 20 6f 6e 20 32 5e 6e 2c 20 61 6e  zeros on 2^n, an
33d0: 64 20 74 68 65 20 6f 6e 6c 79 20 72 65 6c 65 76  d the only relev
33e0: 61 6e 74 20 64 69 67 69 74 20 73 69 7a 65 73 0a  ant digit sizes.
33f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3400: 2f 2f 20 61 72 65 20 63 6f 6e 73 65 63 75 74 69  // are consecuti
3410: 76 65 20 70 6f 77 65 72 73 20 6f 66 20 74 77 6f  ve powers of two
3420: 2c 20 73 6f 20 74 68 69 73 20 69 73 20 77 65 6c  , so this is wel
3430: 6c 20 73 75 69 74 65 64 20 69 6e 64 65 78 20 66  l suited index f
3440: 6f 72 20 74 68 65 20 74 61 62 6c 65 2e 0a 20 20  or the table..  
3450: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6c 65                le
3460: 74 20 74 61 62 6c 65 5f 69 6e 64 65 78 20 3d 20  t table_index = 
3470: 6d 65 6d 3a 3a 73 69 7a 65 5f 6f 66 3a 3a 3c 24  mem::size_of::<$
3480: 74 79 3e 28 29 2e 74 72 61 69 6c 69 6e 67 5f 7a  ty>().trailing_z
3490: 65 72 6f 73 28 29 20 61 73 20 75 73 69 7a 65 3b  eros() as usize;
34a0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
34b0: 20 6c 65 74 20 28 73 6d 61 6c 6c 5f 70 6f 77 65   let (small_powe
34c0: 72 2c 20 73 6d 61 6c 6c 5f 65 29 20 3d 20 53 4d  r, small_e) = SM
34d0: 41 4c 4c 5f 50 4f 57 35 5b 74 61 62 6c 65 5f 69  ALL_POW5[table_i
34e0: 6e 64 65 78 5d 3b 0a 20 20 20 20 20 20 20 20 20  ndex];.         
34f0: 20 20 20 20 20 20 20 6c 65 74 20 73 6d 61 6c 6c         let small
3500: 5f 70 6f 77 65 72 20 3d 20 73 6d 61 6c 6c 5f 70  _power = small_p
3510: 6f 77 65 72 20 61 73 20 24 74 79 3b 0a 0a 20 20  ower as $ty;..  
3520: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2f                //
3530: 20 4d 75 6c 74 69 70 6c 79 20 77 69 74 68 20 74   Multiply with t
3540: 68 65 20 6c 61 72 67 65 73 74 20 73 69 6e 67 6c  he largest singl
3550: 65 2d 64 69 67 69 74 20 70 6f 77 65 72 20 61 73  e-digit power as
3560: 20 6c 6f 6e 67 20 61 73 20 70 6f 73 73 69 62 6c   long as possibl
3570: 65 20 2e 2e 2e 0a 20 20 20 20 20 20 20 20 20 20  e ....          
3580: 20 20 20 20 20 20 77 68 69 6c 65 20 65 20 3e 3d        while e >=
3590: 20 73 6d 61 6c 6c 5f 65 20 7b 0a 20 20 20 20 20   small_e {.     
35a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 73                 s
35b0: 65 6c 66 2e 6d 75 6c 5f 73 6d 61 6c 6c 28 73 6d  elf.mul_small(sm
35c0: 61 6c 6c 5f 70 6f 77 65 72 29 3b 0a 20 20 20 20  all_power);.    
35d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
35e0: 65 20 2d 3d 20 73 6d 61 6c 6c 5f 65 3b 0a 20 20  e -= small_e;.  
35f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a                }.
3600: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
3610: 20 2f 2f 20 2e 2e 2e 20 74 68 65 6e 20 66 69 6e   // ... then fin
3620: 69 73 68 20 6f 66 66 20 74 68 65 20 72 65 6d 61  ish off the rema
3630: 69 6e 64 65 72 2e 0a 20 20 20 20 20 20 20 20 20  inder..         
3640: 20 20 20 20 20 20 20 6c 65 74 20 6d 75 74 20 72         let mut r
3650: 65 73 74 5f 70 6f 77 65 72 20 3d 20 31 3b 0a 20  est_power = 1;. 
3660: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66                 f
3670: 6f 72 20 5f 20 69 6e 20 30 2e 2e 65 20 7b 0a 20  or _ in 0..e {. 
3680: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3690: 20 20 20 72 65 73 74 5f 70 6f 77 65 72 20 2a 3d     rest_power *=
36a0: 20 35 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20   5;.            
36b0: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20      }.          
36c0: 20 20 20 20 20 20 73 65 6c 66 2e 6d 75 6c 5f 73        self.mul_s
36d0: 6d 61 6c 6c 28 72 65 73 74 5f 70 6f 77 65 72 29  mall(rest_power)
36e0: 3b 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ;..             
36f0: 20 20 20 73 65 6c 66 0a 20 20 20 20 20 20 20 20     self.        
3700: 20 20 20 20 7d 0a 0a 0a 20 20 20 20 20 20 20 20      }...        
3710: 20 20 20 20 2f 2f 2f 20 4d 75 6c 74 69 70 6c 69      /// Multipli
3720: 65 73 20 69 74 73 65 6c 66 20 62 79 20 61 20 6e  es itself by a n
3730: 75 6d 62 65 72 20 64 65 73 63 72 69 62 65 64 20  umber described 
3740: 62 79 20 60 6f 74 68 65 72 5b 30 5d 20 2b 20 6f  by `other[0] + o
3750: 74 68 65 72 5b 31 5d 20 2a 20 32 5e 57 20 2b 0a  ther[1] * 2^W +.
3760: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2f 2f 20              /// 
3770: 6f 74 68 65 72 5b 32 5d 20 2a 20 32 5e 28 32 57  other[2] * 2^(2W
3780: 29 20 2b 20 2e 2e 2e 60 20 28 77 68 65 72 65 20  ) + ...` (where 
3790: 60 57 60 20 69 73 20 74 68 65 20 6e 75 6d 62 65  `W` is the numbe
37a0: 72 20 6f 66 20 62 69 74 73 20 69 6e 20 74 68 65  r of bits in the
37b0: 20 64 69 67 69 74 20 74 79 70 65 29 0a 20 20 20   digit type).   
37c0: 20 20 20 20 20 20 20 20 20 2f 2f 2f 20 61 6e 64           /// and
37d0: 20 72 65 74 75 72 6e 73 20 69 74 73 20 6f 77 6e   returns its own
37e0: 20 6d 75 74 61 62 6c 65 20 72 65 66 65 72 65 6e   mutable referen
37f0: 63 65 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20  ce..            
3800: 70 75 62 20 66 6e 20 6d 75 6c 5f 64 69 67 69 74  pub fn mul_digit
3810: 73 3c 27 61 3e 28 26 27 61 20 6d 75 74 20 73 65  s<'a>(&'a mut se
3820: 6c 66 2c 20 6f 74 68 65 72 3a 20 26 5b 24 74 79  lf, other: &[$ty
3830: 5d 29 20 2d 3e 20 26 27 61 20 6d 75 74 20 24 6e  ]) -> &'a mut $n
3840: 61 6d 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20  ame {.          
3850: 20 20 20 20 20 20 2f 2f 20 74 68 65 20 69 6e 74        // the int
3860: 65 72 6e 61 6c 20 72 6f 75 74 69 6e 65 2e 20 77  ernal routine. w
3870: 6f 72 6b 73 20 62 65 73 74 20 77 68 65 6e 20 61  orks best when a
3880: 61 2e 6c 65 6e 28 29 20 3c 3d 20 62 62 2e 6c 65  a.len() <= bb.le
3890: 6e 28 29 2e 0a 20 20 20 20 20 20 20 20 20 20 20  n()..           
38a0: 20 20 20 20 20 66 6e 20 6d 75 6c 5f 69 6e 6e 65       fn mul_inne
38b0: 72 28 72 65 74 3a 20 26 6d 75 74 20 5b 24 74 79  r(ret: &mut [$ty
38c0: 3b 20 24 6e 5d 2c 20 61 61 3a 20 26 5b 24 74 79  ; $n], aa: &[$ty
38d0: 5d 2c 20 62 62 3a 20 26 5b 24 74 79 5d 29 20 2d  ], bb: &[$ty]) -
38e0: 3e 20 75 73 69 7a 65 20 7b 0a 20 20 20 20 20 20  > usize {.      
38f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 75 73                us
3900: 65 20 6e 75 6d 3a 3a 62 69 67 6e 75 6d 3a 3a 46  e num::bignum::F
3910: 75 6c 6c 4f 70 73 3b 0a 0a 20 20 20 20 20 20 20  ullOps;..       
3920: 20 20 20 20 20 20 20 20 20 20 20 20 20 6c 65 74               let
3930: 20 6d 75 74 20 72 65 74 73 7a 20 3d 20 30 3b 0a   mut retsz = 0;.
3940: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3950: 20 20 20 20 66 6f 72 20 28 69 2c 20 26 61 29 20      for (i, &a) 
3960: 69 6e 20 61 61 2e 69 74 65 72 28 29 2e 65 6e 75  in aa.iter().enu
3970: 6d 65 72 61 74 65 28 29 20 7b 0a 20 20 20 20 20  merate() {.     
3980: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3990: 20 20 20 69 66 20 61 20 3d 3d 20 30 20 7b 20 63     if a == 0 { c
39a0: 6f 6e 74 69 6e 75 65 3b 20 7d 0a 20 20 20 20 20  ontinue; }.     
39b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
39c0: 20 20 20 6c 65 74 20 6d 75 74 20 73 7a 20 3d 20     let mut sz = 
39d0: 62 62 2e 6c 65 6e 28 29 3b 0a 20 20 20 20 20 20  bb.len();.      
39e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
39f0: 20 20 6c 65 74 20 6d 75 74 20 63 61 72 72 79 20    let mut carry 
3a00: 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 20 20 20  = 0;.           
3a10: 20 20 20 20 20 20 20 20 20 20 20 20 20 66 6f 72               for
3a20: 20 28 6a 2c 20 26 62 29 20 69 6e 20 62 62 2e 69   (j, &b) in bb.i
3a30: 74 65 72 28 29 2e 65 6e 75 6d 65 72 61 74 65 28  ter().enumerate(
3a40: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ) {.            
3a50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3a60: 6c 65 74 20 28 63 2c 20 76 29 20 3d 20 61 2e 66  let (c, v) = a.f
3a70: 75 6c 6c 5f 6d 75 6c 5f 61 64 64 28 62 2c 20 72  ull_mul_add(b, r
3a80: 65 74 5b 69 20 2b 20 6a 5d 2c 20 63 61 72 72 79  et[i + j], carry
3a90: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  );.             
3aa0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 72                 r
3ab0: 65 74 5b 69 20 2b 20 6a 5d 20 3d 20 76 3b 0a 20  et[i + j] = v;. 
3ac0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3ad0: 20 20 20 20 20 20 20 20 20 20 20 63 61 72 72 79             carry
3ae0: 20 3d 20 63 3b 0a 20 20 20 20 20 20 20 20 20 20   = c;.          
3af0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a                }.
3b00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3b10: 20 20 20 20 20 20 20 20 69 66 20 63 61 72 72 79          if carry
3b20: 20 3e 20 30 20 7b 0a 20 20 20 20 20 20 20 20 20   > 0 {.         
3b30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3b40: 20 20 20 72 65 74 5b 69 20 2b 20 73 7a 5d 20 3d     ret[i + sz] =
3b50: 20 63 61 72 72 79 3b 0a 20 20 20 20 20 20 20 20   carry;.        
3b60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3b70: 20 20 20 20 73 7a 20 2b 3d 20 31 3b 0a 20 20 20      sz += 1;.   
3b80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3b90: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20       }.         
3ba0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69                 i
3bb0: 66 20 72 65 74 73 7a 20 3c 20 69 20 2b 20 73 7a  f retsz < i + sz
3bc0: 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20   {.             
3bd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 72                 r
3be0: 65 74 73 7a 20 3d 20 69 20 2b 20 73 7a 3b 0a 20  etsz = i + sz;. 
3bf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3c00: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20         }.       
3c10: 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20               }. 
3c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3c30: 20 20 20 72 65 74 73 7a 0a 20 20 20 20 20 20 20     retsz.       
3c40: 20 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20           }..    
3c50: 20 20 20 20 20 20 20 20 20 20 20 20 6c 65 74 20              let 
3c60: 6d 75 74 20 72 65 74 20 3d 20 5b 30 3b 20 24 6e  mut ret = [0; $n
3c70: 5d 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ];.             
3c80: 20 20 20 6c 65 74 20 72 65 74 73 7a 20 3d 20 69     let retsz = i
3c90: 66 20 73 65 6c 66 2e 73 69 7a 65 20 3c 20 6f 74  f self.size < ot
3ca0: 68 65 72 2e 6c 65 6e 28 29 20 7b 0a 20 20 20 20  her.len() {.    
3cb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3cc0: 6d 75 6c 5f 69 6e 6e 65 72 28 26 6d 75 74 20 72  mul_inner(&mut r
3cd0: 65 74 2c 20 26 73 65 6c 66 2e 64 69 67 69 74 73  et, &self.digits
3ce0: 28 29 2c 20 6f 74 68 65 72 29 0a 20 20 20 20 20  (), other).     
3cf0: 20 20 20 20 20 20 20 20 20 20 20 7d 20 65 6c 73             } els
3d00: 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  e {.            
3d10: 20 20 20 20 20 20 20 20 6d 75 6c 5f 69 6e 6e 65          mul_inne
3d20: 72 28 26 6d 75 74 20 72 65 74 2c 20 6f 74 68 65  r(&mut ret, othe
3d30: 72 2c 20 26 73 65 6c 66 2e 64 69 67 69 74 73 28  r, &self.digits(
3d40: 29 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  )).             
3d50: 20 20 20 7d 3b 0a 20 20 20 20 20 20 20 20 20 20     };.          
3d60: 20 20 20 20 20 20 73 65 6c 66 2e 62 61 73 65 20        self.base 
3d70: 3d 20 72 65 74 3b 0a 20 20 20 20 20 20 20 20 20  = ret;.         
3d80: 20 20 20 20 20 20 20 73 65 6c 66 2e 73 69 7a 65         self.size
3d90: 20 3d 20 72 65 74 73 7a 3b 0a 20 20 20 20 20 20   = retsz;.      
3da0: 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 0a 20            self. 
3db0: 20 20 20 20 20 20 20 20 20 20 20 7d 0a 0a 20 20             }..  
3dc0: 20 20 20 20 20 20 20 20 20 20 2f 2f 2f 20 44 69            /// Di
3dd0: 76 69 64 65 73 20 69 74 73 65 6c 66 20 62 79 20  vides itself by 
3de0: 61 20 64 69 67 69 74 2d 73 69 7a 65 64 20 60 6f  a digit-sized `o
3df0: 74 68 65 72 60 20 61 6e 64 20 72 65 74 75 72 6e  ther` and return
3e00: 73 20 69 74 73 20 6f 77 6e 0a 20 20 20 20 20 20  s its own.      
3e10: 20 20 20 20 20 20 2f 2f 2f 20 6d 75 74 61 62 6c        /// mutabl
3e20: 65 20 72 65 66 65 72 65 6e 63 65 20 2a 61 6e 64  e reference *and
3e30: 2a 20 74 68 65 20 72 65 6d 61 69 6e 64 65 72 2e  * the remainder.
3e40: 0a 20 20 20 20 20 20 20 20 20 20 20 20 70 75 62  .            pub
3e50: 20 66 6e 20 64 69 76 5f 72 65 6d 5f 73 6d 61 6c   fn div_rem_smal
3e60: 6c 28 26 6d 75 74 20 73 65 6c 66 2c 20 6f 74 68  l(&mut self, oth
3e70: 65 72 3a 20 24 74 79 29 20 2d 3e 20 28 26 6d 75  er: $ty) -> (&mu
3e80: 74 20 24 6e 61 6d 65 2c 20 24 74 79 29 20 7b 0a  t $name, $ty) {.
3e90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3ea0: 75 73 65 20 6e 75 6d 3a 3a 62 69 67 6e 75 6d 3a  use num::bignum:
3eb0: 3a 46 75 6c 6c 4f 70 73 3b 0a 0a 20 20 20 20 20  :FullOps;..     
3ec0: 20 20 20 20 20 20 20 20 20 20 20 61 73 73 65 72             asser
3ed0: 74 21 28 6f 74 68 65 72 20 3e 20 30 29 3b 0a 0a  t!(other > 0);..
3ee0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3ef0: 6c 65 74 20 73 7a 20 3d 20 73 65 6c 66 2e 73 69  let sz = self.si
3f00: 7a 65 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ze;.            
3f10: 20 20 20 20 6c 65 74 20 6d 75 74 20 62 6f 72 72      let mut borr
3f20: 6f 77 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20  ow = 0;.        
3f30: 20 20 20 20 20 20 20 20 66 6f 72 20 61 20 69 6e          for a in
3f40: 20 73 65 6c 66 2e 62 61 73 65 5b 2e 2e 73 7a 5d   self.base[..sz]
3f50: 2e 69 74 65 72 5f 6d 75 74 28 29 2e 72 65 76 28  .iter_mut().rev(
3f60: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ) {.            
3f70: 20 20 20 20 20 20 20 20 6c 65 74 20 28 71 2c 20          let (q, 
3f80: 72 29 20 3d 20 28 2a 61 29 2e 66 75 6c 6c 5f 64  r) = (*a).full_d
3f90: 69 76 5f 72 65 6d 28 6f 74 68 65 72 2c 20 62 6f  iv_rem(other, bo
3fa0: 72 72 6f 77 29 3b 0a 20 20 20 20 20 20 20 20 20  rrow);.         
3fb0: 20 20 20 20 20 20 20 20 20 20 20 2a 61 20 3d 20             *a = 
3fc0: 71 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  q;.             
3fd0: 20 20 20 20 20 20 20 62 6f 72 72 6f 77 20 3d 20         borrow = 
3fe0: 72 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  r;.             
3ff0: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20     }.           
4000: 20 20 20 20 20 28 73 65 6c 66 2c 20 62 6f 72 72       (self, borr
4010: 6f 77 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  ow).            
4020: 7d 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 2f  }..            /
4030: 2f 2f 20 44 69 76 69 64 65 20 73 65 6c 66 20 62  // Divide self b
4040: 79 20 61 6e 6f 74 68 65 72 20 62 69 67 6e 75 6d  y another bignum
4050: 2c 20 6f 76 65 72 77 72 69 74 69 6e 67 20 60 71  , overwriting `q
4060: 60 20 77 69 74 68 20 74 68 65 20 71 75 6f 74 69  ` with the quoti
4070: 65 6e 74 20 61 6e 64 20 60 72 60 20 77 69 74 68  ent and `r` with
4080: 20 74 68 65 0a 20 20 20 20 20 20 20 20 20 20 20   the.           
4090: 20 2f 2f 2f 20 72 65 6d 61 69 6e 64 65 72 2e 0a   /// remainder..
40a0: 20 20 20 20 20 20 20 20 20 20 20 20 70 75 62 20              pub 
40b0: 66 6e 20 64 69 76 5f 72 65 6d 28 26 73 65 6c 66  fn div_rem(&self
40c0: 2c 20 64 3a 20 26 24 6e 61 6d 65 2c 20 71 3a 20  , d: &$name, q: 
40d0: 26 6d 75 74 20 24 6e 61 6d 65 2c 20 72 3a 20 26  &mut $name, r: &
40e0: 6d 75 74 20 24 6e 61 6d 65 29 20 7b 0a 20 20 20  mut $name) {.   
40f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 75 73 65               use
4100: 20 6d 65 6d 3b 0a 0a 20 20 20 20 20 20 20 20 20   mem;..         
4110: 20 20 20 20 20 20 20 2f 2f 20 53 74 75 70 69 64         // Stupid
4120: 20 73 6c 6f 77 20 62 61 73 65 2d 32 20 6c 6f 6e   slow base-2 lon
4130: 67 20 64 69 76 69 73 69 6f 6e 20 74 61 6b 65 6e  g division taken
4140: 20 66 72 6f 6d 0a 20 20 20 20 20 20 20 20 20 20   from.          
4150: 20 20 20 20 20 20 2f 2f 20 68 74 74 70 73 3a 2f        // https:/
4160: 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f 72  /en.wikipedia.or
4170: 67 2f 77 69 6b 69 2f 44 69 76 69 73 69 6f 6e 5f  g/wiki/Division_
4180: 61 6c 67 6f 72 69 74 68 6d 0a 20 20 20 20 20 20  algorithm.      
4190: 20 20 20 20 20 20 20 20 20 20 2f 2f 20 46 49 58            // FIX
41a0: 4d 45 20 75 73 65 20 61 20 67 72 65 61 74 65 72  ME use a greater
41b0: 20 62 61 73 65 20 28 24 74 79 29 20 66 6f 72 20   base ($ty) for 
41c0: 74 68 65 20 6c 6f 6e 67 20 64 69 76 69 73 69 6f  the long divisio
41d0: 6e 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  n..             
41e0: 20 20 20 61 73 73 65 72 74 21 28 21 64 2e 69 73     assert!(!d.is
41f0: 5f 7a 65 72 6f 28 29 29 3b 0a 20 20 20 20 20 20  _zero());.      
4200: 20 20 20 20 20 20 20 20 20 20 6c 65 74 20 64 69            let di
4210: 67 69 74 62 69 74 73 20 3d 20 6d 65 6d 3a 3a 73  gitbits = mem::s
4220: 69 7a 65 5f 6f 66 3a 3a 3c 24 74 79 3e 28 29 20  ize_of::<$ty>() 
4230: 2a 20 38 3b 0a 20 20 20 20 20 20 20 20 20 20 20  * 8;.           
4240: 20 20 20 20 20 66 6f 72 20 64 69 67 69 74 20 69       for digit i
4250: 6e 20 26 6d 75 74 20 71 2e 62 61 73 65 5b 2e 2e  n &mut q.base[..
4260: 5d 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ] {.            
4270: 20 20 20 20 20 20 20 20 2a 64 69 67 69 74 20 3d          *digit =
4280: 20 30 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20   0;.            
4290: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20      }.          
42a0: 20 20 20 20 20 20 66 6f 72 20 64 69 67 69 74 20        for digit 
42b0: 69 6e 20 26 6d 75 74 20 72 2e 62 61 73 65 5b 2e  in &mut r.base[.
42c0: 2e 5d 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20  .] {.           
42d0: 20 20 20 20 20 20 20 20 20 2a 64 69 67 69 74 20           *digit 
42e0: 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 20 20 20  = 0;.           
42f0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20       }.         
4300: 20 20 20 20 20 20 20 72 2e 73 69 7a 65 20 3d 20         r.size = 
4310: 64 2e 73 69 7a 65 3b 0a 20 20 20 20 20 20 20 20  d.size;.        
4320: 20 20 20 20 20 20 20 20 71 2e 73 69 7a 65 20 3d          q.size =
4330: 20 31 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20   1;.            
4340: 20 20 20 20 6c 65 74 20 6d 75 74 20 71 5f 69 73      let mut q_is
4350: 5f 7a 65 72 6f 20 3d 20 74 72 75 65 3b 0a 20 20  _zero = true;.  
4360: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6c 65                le
4370: 74 20 65 6e 64 20 3d 20 73 65 6c 66 2e 62 69 74  t end = self.bit
4380: 5f 6c 65 6e 67 74 68 28 29 3b 0a 20 20 20 20 20  _length();.     
4390: 20 20 20 20 20 20 20 20 20 20 20 66 6f 72 20 69             for i
43a0: 20 69 6e 20 28 30 2e 2e 65 6e 64 29 2e 72 65 76   in (0..end).rev
43b0: 28 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20  () {.           
43c0: 20 20 20 20 20 20 20 20 20 72 2e 6d 75 6c 5f 70           r.mul_p
43d0: 6f 77 32 28 31 29 3b 0a 20 20 20 20 20 20 20 20  ow2(1);.        
43e0: 20 20 20 20 20 20 20 20 20 20 20 20 72 2e 62 61              r.ba
43f0: 73 65 5b 30 5d 20 7c 3d 20 73 65 6c 66 2e 67 65  se[0] |= self.ge
4400: 74 5f 62 69 74 28 69 29 20 61 73 20 24 74 79 3b  t_bit(i) as $ty;
4410: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
4420: 20 20 20 20 20 69 66 20 26 2a 72 20 3e 3d 20 64       if &*r >= d
4430: 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20   {.             
4440: 20 20 20 20 20 20 20 20 20 20 20 72 2e 73 75 62             r.sub
4450: 28 64 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20  (d);.           
4460: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2f 20               // 
4470: 53 65 74 20 62 69 74 20 60 69 60 20 6f 66 20 71  Set bit `i` of q
4480: 20 74 6f 20 31 2e 0a 20 20 20 20 20 20 20 20 20   to 1..         
4490: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6c                 l
44a0: 65 74 20 64 69 67 69 74 5f 69 64 78 20 3d 20 69  et digit_idx = i
44b0: 20 2f 20 64 69 67 69 74 62 69 74 73 3b 0a 20 20   / digitbits;.  
44c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
44d0: 20 20 20 20 20 20 6c 65 74 20 62 69 74 5f 69 64        let bit_id
44e0: 78 20 3d 20 69 20 25 20 64 69 67 69 74 62 69 74  x = i % digitbit
44f0: 73 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  s;.             
4500: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 71 5f             if q_
4510: 69 73 5f 7a 65 72 6f 20 7b 0a 20 20 20 20 20 20  is_zero {.      
4520: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4530: 20 20 20 20 20 20 71 2e 73 69 7a 65 20 3d 20 64        q.size = d
4540: 69 67 69 74 5f 69 64 78 20 2b 20 31 3b 0a 20 20  igit_idx + 1;.  
4550: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4560: 20 20 20 20 20 20 20 20 20 20 71 5f 69 73 5f 7a            q_is_z
4570: 65 72 6f 20 3d 20 66 61 6c 73 65 3b 0a 20 20 20  ero = false;.   
4580: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4590: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20       }.         
45a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 71                 q
45b0: 2e 62 61 73 65 5b 64 69 67 69 74 5f 69 64 78 5d  .base[digit_idx]
45c0: 20 7c 3d 20 31 20 3c 3c 20 62 69 74 5f 69 64 78   |= 1 << bit_idx
45d0: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
45e0: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20        }.        
45f0: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20          }.      
4600: 20 20 20 20 20 20 20 20 20 20 64 65 62 75 67 5f            debug_
4610: 61 73 73 65 72 74 21 28 71 2e 62 61 73 65 5b 71  assert!(q.base[q
4620: 2e 73 69 7a 65 2e 2e 5d 2e 69 74 65 72 28 29 2e  .size..].iter().
4630: 61 6c 6c 28 7c 26 64 7c 20 64 20 3d 3d 20 30 29  all(|&d| d == 0)
4640: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  );.             
4650: 20 20 20 64 65 62 75 67 5f 61 73 73 65 72 74 21     debug_assert!
4660: 28 72 2e 62 61 73 65 5b 72 2e 73 69 7a 65 2e 2e  (r.base[r.size..
4670: 5d 2e 69 74 65 72 28 29 2e 61 6c 6c 28 7c 26 64  ].iter().all(|&d
4680: 7c 20 64 20 3d 3d 20 30 29 29 3b 0a 20 20 20 20  | d == 0));.    
4690: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20          }.      
46a0: 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 69 6d 70    }..        imp
46b0: 6c 20 3a 3a 63 6d 70 3a 3a 50 61 72 74 69 61 6c  l ::cmp::Partial
46c0: 45 71 20 66 6f 72 20 24 6e 61 6d 65 20 7b 0a 20  Eq for $name {. 
46d0: 20 20 20 20 20 20 20 20 20 20 20 66 6e 20 65 71             fn eq
46e0: 28 26 73 65 6c 66 2c 20 6f 74 68 65 72 3a 20 26  (&self, other: &
46f0: 24 6e 61 6d 65 29 20 2d 3e 20 62 6f 6f 6c 20 7b  $name) -> bool {
4700: 20 73 65 6c 66 2e 62 61 73 65 5b 2e 2e 5d 20 3d   self.base[..] =
4710: 3d 20 6f 74 68 65 72 2e 62 61 73 65 5b 2e 2e 5d  = other.base[..]
4720: 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a 0a 20 20   }.        }..  
4730: 20 20 20 20 20 20 69 6d 70 6c 20 3a 3a 63 6d 70        impl ::cmp
4740: 3a 3a 45 71 20 66 6f 72 20 24 6e 61 6d 65 20 7b  ::Eq for $name {
4750: 0a 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20  .        }..    
4760: 20 20 20 20 69 6d 70 6c 20 3a 3a 63 6d 70 3a 3a      impl ::cmp::
4770: 50 61 72 74 69 61 6c 4f 72 64 20 66 6f 72 20 24  PartialOrd for $
4780: 6e 61 6d 65 20 7b 0a 20 20 20 20 20 20 20 20 20  name {.         
4790: 20 20 20 66 6e 20 70 61 72 74 69 61 6c 5f 63 6d     fn partial_cm
47a0: 70 28 26 73 65 6c 66 2c 20 6f 74 68 65 72 3a 20  p(&self, other: 
47b0: 26 24 6e 61 6d 65 29 20 2d 3e 20 3a 3a 6f 70 74  &$name) -> ::opt
47c0: 69 6f 6e 3a 3a 4f 70 74 69 6f 6e 3c 3a 3a 63 6d  ion::Option<::cm
47d0: 70 3a 3a 4f 72 64 65 72 69 6e 67 3e 20 7b 0a 20  p::Ordering> {. 
47e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 3a                 :
47f0: 3a 6f 70 74 69 6f 6e 3a 3a 4f 70 74 69 6f 6e 3a  :option::Option:
4800: 3a 53 6f 6d 65 28 73 65 6c 66 2e 63 6d 70 28 6f  :Some(self.cmp(o
4810: 74 68 65 72 29 29 0a 20 20 20 20 20 20 20 20 20  ther)).         
4820: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a 0a     }.        }..
4830: 20 20 20 20 20 20 20 20 69 6d 70 6c 20 3a 3a 63          impl ::c
4840: 6d 70 3a 3a 4f 72 64 20 66 6f 72 20 24 6e 61 6d  mp::Ord for $nam
4850: 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  e {.            
4860: 66 6e 20 63 6d 70 28 26 73 65 6c 66 2c 20 6f 74  fn cmp(&self, ot
4870: 68 65 72 3a 20 26 24 6e 61 6d 65 29 20 2d 3e 20  her: &$name) -> 
4880: 3a 3a 63 6d 70 3a 3a 4f 72 64 65 72 69 6e 67 20  ::cmp::Ordering 
4890: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  {.              
48a0: 20 20 75 73 65 20 63 6d 70 3a 3a 6d 61 78 3b 0a    use cmp::max;.
48b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
48c0: 6c 65 74 20 73 7a 20 3d 20 6d 61 78 28 73 65 6c  let sz = max(sel
48d0: 66 2e 73 69 7a 65 2c 20 6f 74 68 65 72 2e 73 69  f.size, other.si
48e0: 7a 65 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20  ze);.           
48f0: 20 20 20 20 20 6c 65 74 20 6c 68 73 20 3d 20 73       let lhs = s
4900: 65 6c 66 2e 62 61 73 65 5b 2e 2e 73 7a 5d 2e 69  elf.base[..sz].i
4910: 74 65 72 28 29 2e 63 6c 6f 6e 65 64 28 29 2e 72  ter().cloned().r
4920: 65 76 28 29 3b 0a 20 20 20 20 20 20 20 20 20 20  ev();.          
4930: 20 20 20 20 20 20 6c 65 74 20 72 68 73 20 3d 20        let rhs = 
4940: 6f 74 68 65 72 2e 62 61 73 65 5b 2e 2e 73 7a 5d  other.base[..sz]
4950: 2e 69 74 65 72 28 29 2e 63 6c 6f 6e 65 64 28 29  .iter().cloned()
4960: 2e 72 65 76 28 29 3b 0a 20 20 20 20 20 20 20 20  .rev();.        
4970: 20 20 20 20 20 20 20 20 6c 68 73 2e 63 6d 70 28          lhs.cmp(
4980: 72 68 73 29 0a 20 20 20 20 20 20 20 20 20 20 20  rhs).           
4990: 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a 0a 20 20   }.        }..  
49a0: 20 20 20 20 20 20 69 6d 70 6c 20 3a 3a 63 6c 6f        impl ::clo
49b0: 6e 65 3a 3a 43 6c 6f 6e 65 20 66 6f 72 20 24 6e  ne::Clone for $n
49c0: 61 6d 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20  ame {.          
49d0: 20 20 66 6e 20 63 6c 6f 6e 65 28 26 73 65 6c 66    fn clone(&self
49e0: 29 20 2d 3e 20 24 6e 61 6d 65 20 7b 0a 20 20 20  ) -> $name {.   
49f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 24 6e 61               $na
4a00: 6d 65 20 7b 20 73 69 7a 65 3a 20 73 65 6c 66 2e  me { size: self.
4a10: 73 69 7a 65 2c 20 62 61 73 65 3a 20 73 65 6c 66  size, base: self
4a20: 2e 62 61 73 65 20 7d 0a 20 20 20 20 20 20 20 20  .base }.        
4a30: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a      }.        }.
4a40: 0a 20 20 20 20 20 20 20 20 69 6d 70 6c 20 3a 3a  .        impl ::
4a50: 66 6d 74 3a 3a 44 65 62 75 67 20 66 6f 72 20 24  fmt::Debug for $
4a60: 6e 61 6d 65 20 7b 0a 20 20 20 20 20 20 20 20 20  name {.         
4a70: 20 20 20 66 6e 20 66 6d 74 28 26 73 65 6c 66 2c     fn fmt(&self,
4a80: 20 66 3a 20 26 6d 75 74 20 3a 3a 66 6d 74 3a 3a   f: &mut ::fmt::
4a90: 46 6f 72 6d 61 74 74 65 72 29 20 2d 3e 20 3a 3a  Formatter) -> ::
4aa0: 66 6d 74 3a 3a 52 65 73 75 6c 74 20 7b 0a 20 20  fmt::Result {.  
4ab0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 75 73                us
4ac0: 65 20 6d 65 6d 3b 0a 0a 20 20 20 20 20 20 20 20  e mem;..        
4ad0: 20 20 20 20 20 20 20 20 6c 65 74 20 73 7a 20 3d          let sz =
4ae0: 20 69 66 20 73 65 6c 66 2e 73 69 7a 65 20 3c 20   if self.size < 
4af0: 31 20 7b 31 7d 20 65 6c 73 65 20 7b 73 65 6c 66  1 {1} else {self
4b00: 2e 73 69 7a 65 7d 3b 0a 20 20 20 20 20 20 20 20  .size};.        
4b10: 20 20 20 20 20 20 20 20 6c 65 74 20 64 69 67 69          let digi
4b20: 74 6c 65 6e 20 3d 20 6d 65 6d 3a 3a 73 69 7a 65  tlen = mem::size
4b30: 5f 6f 66 3a 3a 3c 24 74 79 3e 28 29 20 2a 20 32  _of::<$ty>() * 2
4b40: 3b 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ;..             
4b50: 20 20 20 77 72 69 74 65 21 28 66 2c 20 22 7b 3a     write!(f, "{:
4b60: 23 78 7d 22 2c 20 73 65 6c 66 2e 62 61 73 65 5b  #x}", self.base[
4b70: 73 7a 2d 31 5d 29 3f 3b 0a 20 20 20 20 20 20 20  sz-1])?;.       
4b80: 20 20 20 20 20 20 20 20 20 66 6f 72 20 26 76 20           for &v 
4b90: 69 6e 20 73 65 6c 66 2e 62 61 73 65 5b 2e 2e 73  in self.base[..s
4ba0: 7a 2d 31 5d 2e 69 74 65 72 28 29 2e 72 65 76 28  z-1].iter().rev(
4bb0: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ) {.            
4bc0: 20 20 20 20 20 20 20 20 77 72 69 74 65 21 28 66          write!(f
4bd0: 2c 20 22 5f 7b 3a 30 31 24 78 7d 22 2c 20 76 2c  , "_{:01$x}", v,
4be0: 20 64 69 67 69 74 6c 65 6e 29 3f 3b 0a 20 20 20   digitlen)?;.   
4bf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20               }. 
4c00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 3a                 :
4c10: 3a 72 65 73 75 6c 74 3a 3a 52 65 73 75 6c 74 3a  :result::Result:
4c20: 3a 4f 6b 28 28 29 29 0a 20 20 20 20 20 20 20 20  :Ok(()).        
4c30: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a      }.        }.
4c40: 20 20 20 20 29 0a 7d 0a 0a 2f 2f 2f 20 54 68 65      ).}../// The
4c50: 20 64 69 67 69 74 20 74 79 70 65 20 66 6f 72 20   digit type for 
4c60: 60 42 69 67 33 32 78 34 30 60 2e 0a 70 75 62 20  `Big32x40`..pub 
4c70: 74 79 70 65 20 44 69 67 69 74 33 32 20 3d 20 75  type Digit32 = u
4c80: 33 32 3b 0a 0a 64 65 66 69 6e 65 5f 62 69 67 6e  32;..define_bign
4c90: 75 6d 21 28 42 69 67 33 32 78 34 30 3a 20 74 79  um!(Big32x40: ty
4ca0: 70 65 3d 44 69 67 69 74 33 32 2c 20 6e 3d 34 30  pe=Digit32, n=40
4cb0: 29 3b 0a 0a 2f 2f 20 74 68 69 73 20 6f 6e 65 20  );..// this one 
4cc0: 69 73 20 75 73 65 64 20 66 6f 72 20 74 65 73 74  is used for test
4cd0: 69 6e 67 20 6f 6e 6c 79 2e 0a 23 5b 64 6f 63 28  ing only..#[doc(
4ce0: 68 69 64 64 65 6e 29 5d 0a 70 75 62 20 6d 6f 64  hidden)].pub mod
4cf0: 20 74 65 73 74 73 20 7b 0a 20 20 20 20 64 65 66   tests {.    def
4d00: 69 6e 65 5f 62 69 67 6e 75 6d 21 28 42 69 67 38  ine_bignum!(Big8
4d10: 78 33 3a 20 74 79 70 65 3d 75 38 2c 20 6e 3d 33  x3: type=u8, n=3
4d20: 29 3b 0a 7d 0a                                   );.}.