Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

divide.cpp
Go to the documentation of this file.
1 /*
2 * Division Algorithm
3 * (C) 1999-2007,2012 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7
8 #include <botan/divide.h>
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/mp_madd.h>
11
12 namespace Botan {
13
14 namespace {
15
16 /*
17 * Handle signed operands, if necessary
18 */
19 void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
20 {
21 if(x.sign() == BigInt::Negative)
22 {
23 q.flip_sign();
24 if(r.is_nonzero()) { --q; r = y.abs() - r; }
25 }
26 if(y.sign() == BigInt::Negative)
27 q.flip_sign();
28 }
29
30 bool division_check(word q, word y2, word y1,
31 word x3, word x2, word x1)
32 {
33 // Compute (y3,y2,y1) = (y2,y1) * q
34
35 word y3 = 0;
36 y1 = word_madd2(q, y1, &y3);
37 y2 = word_madd2(q, y2, &y3);
38
39 // Return (y3,y2,y1) >? (x3,x2,x1)
40
41 if(y3 > x3) return true;
42 if(y3 < x3) return false;
43
44 if(y2 > x2) return true;
45 if(y2 < x2) return false;
46
47 if(y1 > x1) return true;
48 if(y1 < x1) return false;
49
50 return false;
51 }
52
53 }
54
55 /*
56 * Solve x = q * y + r
57 */
58 void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
59 {
60 if(y_arg.is_zero())
61 throw BigInt::DivideByZero();
62
63 BigInt y = y_arg;
64 const size_t y_words = y.sig_words();
65
66 r = x;
67 q = 0;
68
69 r.set_sign(BigInt::Positive);
70 y.set_sign(BigInt::Positive);
71
72 int32_t compare = r.cmp(y);
73
74 if(compare == 0)
75 {
76 q = 1;
77 r = 0;
78 }
79 else if(compare > 0)
80 {
81 size_t shifts = 0;
82 word y_top = y.word_at(y.sig_words()-1);
83 while(y_top < MP_WORD_TOP_BIT) { y_top <<= 1; ++shifts; }
84 y <<= shifts;
85 r <<= shifts;
86
87 const size_t n = r.sig_words() - 1, t = y_words - 1;
88
89 if(n < t)
90 throw Internal_Error("BigInt division word sizes");
91
92 q.grow_to(n - t + 1);
93
94 word* q_words = q.mutable_data();
95
96 if(n <= t)
97 {
98 while(r > y) { r -= y; ++q; }
99 r >>= shifts;
100 sign_fixup(x, y_arg, q, r);
101 return;
102 }
103
104 BigInt temp = y << (MP_WORD_BITS * (n-t));
105
106 while(r >= temp) { r -= temp; q_words[n-t] += 1; }
107
108 for(size_t j = n; j != t; --j)
109 {
110 const word x_j0 = r.word_at(j);
111 const word x_j1 = r.word_at(j-1);
112 const word y_t = y.word_at(t);
113
114 if(x_j0 == y_t)
115 q_words[j-t-1] = MP_WORD_MAX;
116 else
117 q_words[j-t-1] = bigint_divop(x_j0, x_j1, y_t);
118
119 while(division_check(q_words[j-t-1],
120 y_t, y.word_at(t-1),
121 x_j0, x_j1, r.word_at(j-2)))
122 {
123 q_words[j-t-1] -= 1;
124 }
125
126 r -= (q_words[j-t-1] * y) << (MP_WORD_BITS * (j-t-1));
127
128 if(r.is_negative())
129 {
130 r += y << (MP_WORD_BITS * (j-t-1));
131 q_words[j-t-1] -= 1;
132 }
133 }
134 r >>= shifts;
135 }
136
137 sign_fixup(x, y_arg, q, r);
138 }
139
140 }
Botan::BigInt::word_at
word word_at(size_t n) const
Definition: bigint.h:335
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:393
Botan::divide
void divide(const BigInt &x, const BigInt &y_arg, BigInt &q, BigInt &r)
Definition: divide.cpp:58
Botan::BigInt
Definition: bigint.h:23
Botan::BigInt::Positive
Definition: bigint.h:34
Botan::Internal_Error
Definition: exceptn.h:88
Botan::BigInt::mutable_data
word * mutable_data()
Definition: bigint.h:419
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:348
Botan::bigint_divop
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.cpp:404
Botan::word_madd2
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:59
Botan::BigInt::Negative
Definition: bigint.h:34
Botan::BigInt::cmp
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:98
Botan
Definition: alg_id.cpp:13
Botan::MP_WORD_MAX
const word MP_WORD_MAX
Definition: mp_types.h:29
Botan::BigInt::grow_to
void grow_to(size_t n)
Definition: bigint.cpp:261
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:250
Botan::BigInt::set_sign
void set_sign(Sign sign)
Definition: bigint.cpp:215
Botan::MP_WORD_TOP_BIT
const word MP_WORD_TOP_BIT
Definition: mp_types.h:28
Botan::BigInt::DivideByZero
Definition: bigint.h:39
Botan::MP_WORD_BITS
const size_t MP_WORD_BITS
Definition: mp_core.h:21