Botan  2.7.0
Crypto and TLS for C++11
big_ops3.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Binary Operators
3 * (C) 1999-2007 Jack Lloyd
4 * 2016 Matthias Gierlings
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8 
9 #include <botan/bigint.h>
10 #include <botan/divide.h>
11 #include <botan/internal/mp_core.h>
12 #include <botan/internal/bit_ops.h>
13 #include <algorithm>
14 
15 namespace Botan {
16 
17 namespace {
18 
19 BigInt bigint_add(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign)
20  {
21  const size_t x_sw = x.sig_words();
22 
23  BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
24 
25  if(x.sign() == y_sign)
26  bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
27  else
28  {
29  int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw);
30 
31  if(relative_size < 0)
32  {
33  bigint_sub3(z.mutable_data(), y, y_sw, x.data(), x_sw);
34  z.set_sign(y_sign);
35  }
36  else if(relative_size == 0)
37  z.set_sign(BigInt::Positive);
38  else if(relative_size > 0)
39  bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw);
40  }
41 
42  return z;
43  }
44 
45 BigInt bigint_sub(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign)
46  {
47  const size_t x_sw = x.sig_words();
48 
49  int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw);
50 
51  BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
52 
53  if(relative_size < 0)
54  {
55  if(x.sign() == y_sign)
56  bigint_sub3(z.mutable_data(), y, y_sw, x.data(), x_sw);
57  else
58  bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
59  z.set_sign(y_sign == BigInt::Positive ? BigInt::Negative : BigInt::Positive);
60  }
61  else if(relative_size == 0)
62  {
63  if(x.sign() != y_sign)
64  bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1);
65  z.set_sign(y_sign == BigInt::Positive ? BigInt::Negative : BigInt::Positive);
66  }
67  else if(relative_size > 0)
68  {
69  if(x.sign() == y_sign)
70  bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw);
71  else
72  bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
73  z.set_sign(x.sign());
74  }
75  return z;
76  }
77 
78 }
79 
80 BigInt operator+(const BigInt& x, const BigInt& y)
81  {
82  return bigint_add(x, y.data(), y.sig_words(), y.sign());
83  }
84 
85 BigInt operator+(const BigInt& x, word y)
86  {
87  return bigint_add(x, &y, 1, BigInt::Positive);
88  }
89 
90 BigInt operator-(const BigInt& x, const BigInt& y)
91  {
92  return bigint_sub(x, y.data(), y.sig_words(), y.sign());
93  }
94 
95 BigInt operator-(const BigInt& x, word y)
96  {
97  return bigint_sub(x, &y, 1, BigInt::Positive);
98  }
99 
100 /*
101 * Multiplication Operator
102 */
103 BigInt operator*(const BigInt& x, const BigInt& y)
104  {
105  const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
106 
107  BigInt z(BigInt::Positive, x.size() + y.size());
108 
109  if(x_sw == 1 && y_sw)
110  bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
111  else if(y_sw == 1 && x_sw)
112  bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
113  else if(x_sw && y_sw)
114  {
115  secure_vector<word> workspace(z.size());
116 
117  bigint_mul(z.mutable_data(), z.size(),
118  x.data(), x.size(), x_sw,
119  y.data(), y.size(), y_sw,
120  workspace.data(), workspace.size());
121  }
122 
123  if(x_sw && y_sw && x.sign() != y.sign())
124  z.flip_sign();
125  return z;
126  }
127 
128 /*
129 * Division Operator
130 */
131 BigInt operator/(const BigInt& x, const BigInt& y)
132  {
133  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
134  return (x >> (y.bits() - 1));
135 
136  BigInt q, r;
137  divide(x, y, q, r);
138  return q;
139  }
140 
141 /*
142 * Modulo Operator
143 */
144 BigInt operator%(const BigInt& n, const BigInt& mod)
145  {
146  if(mod.is_zero())
147  throw BigInt::DivideByZero();
148  if(mod.is_negative())
149  throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
150  if(n.is_positive() && mod.is_positive() && n < mod)
151  return n;
152 
153  BigInt q, r;
154  divide(n, mod, q, r);
155  return r;
156  }
157 
158 /*
159 * Modulo Operator
160 */
161 word operator%(const BigInt& n, word mod)
162  {
163  if(mod == 0)
164  throw BigInt::DivideByZero();
165 
166  if(mod == 1)
167  return 0;
168 
169  if(is_power_of_2(mod))
170  return (n.word_at(0) & (mod - 1));
171 
172  word remainder = 0;
173 
174  for(size_t j = n.sig_words(); j > 0; --j)
175  remainder = bigint_modop(remainder, n.word_at(j-1), mod);
176 
177  if(remainder && n.sign() == BigInt::Negative)
178  return mod - remainder;
179  return remainder;
180  }
181 
182 /*
183 * Left Shift Operator
184 */
185 BigInt operator<<(const BigInt& x, size_t shift)
186  {
187  if(shift == 0)
188  return x;
189 
190  const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
191  shift_bits = shift % BOTAN_MP_WORD_BITS;
192 
193  const size_t x_sw = x.sig_words();
194 
195  BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
196  bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
197  return y;
198  }
199 
200 /*
201 * Right Shift Operator
202 */
203 BigInt operator>>(const BigInt& x, size_t shift)
204  {
205  if(shift == 0)
206  return x;
207  if(x.bits() <= shift)
208  return 0;
209 
210  const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
211  shift_bits = shift % BOTAN_MP_WORD_BITS,
212  x_sw = x.sig_words();
213 
214  BigInt y(x.sign(), x_sw - shift_words);
215  bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
216  return y;
217  }
218 
219 }
bool is_negative() const
Definition: bigint.h:460
int operator<<(int fd, Pipe &pipe)
Definition: fd_unix.cpp:17
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:434
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:456
size_t bits() const
Definition: bigint.cpp:228
Sign sign() const
Definition: bigint.h:472
bool is_zero() const
Definition: bigint.h:355
word * mutable_data()
Definition: bigint.h:545
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:90
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:276
word word_at(size_t n) const
Definition: bigint.h:440
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:131
const word * data() const
Definition: bigint.h:551
void divide(const BigInt &x, const BigInt &y_arg, BigInt &q, BigInt &r)
Definition: divide.cpp:58
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.cpp:318
size_t size() const
Definition: bigint.h:513
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:519
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:293
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:414
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:103
OID operator+(const OID &oid, uint32_t component)
Definition: asn1_oid.cpp:87
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:40
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:144
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:194
bool is_positive() const
Definition: bigint.h:466
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:515
bool is_power_of_2(T arg)
Definition: bit_ops.h:25