Botan  1.10.9
divide.cpp
Go to the documentation of this file.
1 /*
2 * Division Algorithm
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/divide.h>
9 #include <botan/internal/mp_core.h>
10 
11 namespace Botan {
12 
13 namespace {
14 
15 /*
16 * Handle signed operands, if necessary
17 */
18 void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
19  {
20  if(x.sign() == BigInt::Negative)
21  {
22  q.flip_sign();
23  if(r.is_nonzero()) { --q; r = y.abs() - r; }
24  }
25  if(y.sign() == BigInt::Negative)
26  q.flip_sign();
27  }
28 
29 }
30 
31 /*
32 * Solve x = q * y + r
33 */
34 void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
35  {
36  if(y_arg.is_zero())
37  throw BigInt::DivideByZero();
38 
39  BigInt y = y_arg;
40  const size_t y_words = y.sig_words();
41 
42  r = x;
43  q = 0;
44 
47 
48  s32bit compare = r.cmp(y);
49 
50  if(compare == 0)
51  {
52  q = 1;
53  r = 0;
54  }
55  else if(compare > 0)
56  {
57  size_t shifts = 0;
58  word y_top = y[y.sig_words()-1];
59  while(y_top < MP_WORD_TOP_BIT) { y_top <<= 1; ++shifts; }
60  y <<= shifts;
61  r <<= shifts;
62 
63  const size_t n = r.sig_words() - 1, t = y_words - 1;
64 
65  if(n < t)
66  throw Internal_Error("BigInt division word sizes");
67 
68  q.get_reg().resize(n - t + 1);
69  if(n <= t)
70  {
71  while(r > y) { r -= y; ++q; }
72  r >>= shifts;
73  sign_fixup(x, y_arg, q, r);
74  return;
75  }
76 
77  BigInt temp = y << (MP_WORD_BITS * (n-t));
78 
79  while(r >= temp) { r -= temp; ++q[n-t]; }
80 
81  for(size_t j = n; j != t; --j)
82  {
83  const word x_j0 = r.word_at(j);
84  const word x_j1 = r.word_at(j-1);
85  const word y_t = y.word_at(t);
86 
87  if(x_j0 == y_t)
88  q[j-t-1] = MP_WORD_MAX;
89  else
90  q[j-t-1] = bigint_divop(x_j0, x_j1, y_t);
91 
92  while(bigint_divcore(q[j-t-1], y_t, y.word_at(t-1),
93  x_j0, x_j1, r.word_at(j-2)))
94  --q[j-t-1];
95 
96  r -= (q[j-t-1] * y) << (MP_WORD_BITS * (j-t-1));
97  if(r.is_negative())
98  {
99  r += y << (MP_WORD_BITS * (j-t-1));
100  --q[j-t-1];
101  }
102  }
103  r >>= shifts;
104  }
105 
106  sign_fixup(x, y_arg, q, r);
107  }
108 
109 }
word word_at(size_t n) const
Definition: bigint.h:238
size_t sig_words() const
Definition: bigint.h:290
void resize(size_t n)
Definition: secmem.h:211
void divide(const BigInt &x, const BigInt &y_arg, BigInt &q, BigInt &r)
Definition: divide.cpp:34
BigInt n
Definition: numthry.cpp:26
s32bit cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:132
SecureVector< word > & get_reg()
Definition: bigint.h:325
bool is_negative() const
Definition: bigint.h:245
word bigint_divop(word n1, word n0, word d)
Definition: mp_misc.cpp:67
signed int s32bit
Definition: types.h:37
const word MP_WORD_MAX
Definition: mp_types.h:29
size_t bigint_divcore(word q, word y2, word y1, word x3, word x2, word x1)
Definition: mp_misc.cpp:18
BigInt r
Definition: numthry.cpp:26
void flip_sign()
Definition: bigint.cpp:302
bool is_zero() const
Definition: bigint.h:176
void set_sign(Sign sign)
Definition: bigint.cpp:291
const word MP_WORD_TOP_BIT
Definition: mp_types.h:28
const size_t MP_WORD_BITS
Definition: mp_core.h:18