Botan  2.1.0
Crypto and TLS for C++11
big_ops2.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Assignment 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/internal/mp_core.h>
11 #include <botan/internal/bit_ops.h>
12 #include <algorithm>
13 
14 namespace Botan {
15 
16 /*
17 * Addition Operator
18 */
20  {
21  const size_t x_sw = sig_words(), y_sw = y.sig_words();
22 
23  const size_t reg_size = std::max(x_sw, y_sw) + 1;
24  grow_to(reg_size);
25 
26  if(sign() == y.sign())
27  bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
28  else
29  {
30  int32_t relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
31 
32  if(relative_size < 0)
33  {
34  secure_vector<word> z(reg_size - 1);
35  bigint_sub3(z.data(), y.data(), reg_size - 1, data(), x_sw);
36  std::swap(m_reg, z);
37  set_sign(y.sign());
38  }
39  else if(relative_size == 0)
40  {
41  zeroise(m_reg);
43  }
44  else if(relative_size > 0)
45  bigint_sub2(mutable_data(), x_sw, y.data(), y_sw);
46  }
47 
48  return (*this);
49  }
50 
51 /*
52 * Subtraction Operator
53 */
55  {
56  const size_t x_sw = sig_words(), y_sw = y.sig_words();
57 
58  int32_t relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
59 
60  const size_t reg_size = std::max(x_sw, y_sw) + 1;
61  grow_to(reg_size);
62 
63  if(relative_size < 0)
64  {
65  if(sign() == y.sign())
66  bigint_sub2_rev(mutable_data(), y.data(), y_sw);
67  else
68  bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
69 
71  }
72  else if(relative_size == 0)
73  {
74  if(sign() == y.sign())
75  {
76  clear();
78  }
79  else
80  bigint_shl1(mutable_data(), x_sw, 0, 1);
81  }
82  else if(relative_size > 0)
83  {
84  if(sign() == y.sign())
85  bigint_sub2(mutable_data(), x_sw, y.data(), y_sw);
86  else
87  bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
88  }
89 
90  return (*this);
91  }
92 
93 /*
94 * Multiplication Operator
95 */
97  {
98  const size_t x_sw = sig_words(), y_sw = y.sig_words();
99  set_sign((sign() == y.sign()) ? Positive : Negative);
100 
101  if(x_sw == 0 || y_sw == 0)
102  {
103  clear();
105  }
106  else if(x_sw == 1 && y_sw)
107  {
108  grow_to(y_sw + 2);
109  bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
110  }
111  else if(y_sw == 1 && x_sw)
112  {
113  grow_to(x_sw + 2);
114  bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
115  }
116  else
117  {
118  grow_to(size() + y.size());
119 
120  secure_vector<word> z(data(), data() + x_sw);
121  secure_vector<word> workspace(size());
122  bigint_mul(*this, BigInt(*this), y, workspace.data());
123  }
124 
125  return (*this);
126  }
127 
128 /*
129 * Division Operator
130 */
132  {
133  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
134  (*this) >>= (y.bits() - 1);
135  else
136  (*this) = (*this) / y;
137  return (*this);
138  }
139 
140 /*
141 * Modulo Operator
142 */
144  {
145  return (*this = (*this) % mod);
146  }
147 
148 /*
149 * Modulo Operator
150 */
151 word BigInt::operator%=(word mod)
152  {
153  if(mod == 0)
154  throw BigInt::DivideByZero();
155 
156  if(is_power_of_2(mod))
157  {
158  word result = (word_at(0) & (mod - 1));
159  clear();
160  grow_to(2);
161  m_reg[0] = result;
162  return result;
163  }
164 
165  word remainder = 0;
166 
167  for(size_t j = sig_words(); j > 0; --j)
168  remainder = bigint_modop(remainder, word_at(j-1), mod);
169  clear();
170  grow_to(2);
171 
172  if(remainder && sign() == BigInt::Negative)
173  m_reg[0] = mod - remainder;
174  else
175  m_reg[0] = remainder;
176 
178 
179  return word_at(0);
180  }
181 
182 /*
183 * Left Shift Operator
184 */
186  {
187  if(shift)
188  {
189  const size_t shift_words = shift / MP_WORD_BITS,
190  shift_bits = shift % MP_WORD_BITS,
191  words = sig_words();
192 
193  grow_to(words + shift_words + (shift_bits ? 1 : 0));
194  bigint_shl1(mutable_data(), words, shift_words, shift_bits);
195  }
196 
197  return (*this);
198  }
199 
200 /*
201 * Right Shift Operator
202 */
204  {
205  if(shift)
206  {
207  const size_t shift_words = shift / MP_WORD_BITS,
208  shift_bits = shift % MP_WORD_BITS;
209 
210  bigint_shr1(mutable_data(), sig_words(), shift_words, shift_bits);
211 
212  if(is_zero())
214  }
215 
216  return (*this);
217  }
218 
219 }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:281
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.cpp:180
word word_at(size_t n) const
Definition: bigint.h:335
size_t sig_words() const
Definition: bigint.h:393
BigInt & operator*=(const BigInt &y)
Definition: big_ops2.cpp:96
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:378
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:157
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.cpp:222
Sign reverse_sign() const
Definition: bigint.cpp:234
word * mutable_data()
Definition: bigint.h:419
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:198
size_t size() const
Definition: bigint.h:387
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:185
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:203
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.cpp:240
BigInt & operator%=(const BigInt &y)
Definition: big_ops2.cpp:143
size_t bits() const
Definition: bigint.cpp:184
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
const word * data() const
Definition: bigint.h:425
Definition: alg_id.cpp:13
T max(T a, T b)
Definition: ct_utils.h:173
BigInt & operator/=(const BigInt &y)
Definition: big_ops2.cpp:131
void clear()
Definition: bigint.h:217
BigInt & operator-=(const BigInt &y)
Definition: big_ops2.cpp:54
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:258
void grow_to(size_t n)
Definition: bigint.cpp:261
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:138
void bigint_mul(BigInt &z, const BigInt &x, const BigInt &y, word workspace[])
Definition: mp_karat.cpp:252
BigInt()=default
bool is_zero() const
Definition: bigint.h:250
void set_sign(Sign sign)
Definition: bigint.cpp:215
BigInt & operator+=(const BigInt &y)
Definition: big_ops2.cpp:19
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:432
bool is_power_of_2(T arg)
Definition: bit_ops.h:25
void zeroise(std::vector< T, Alloc > &vec)
Definition: secmem.h:211
const size_t MP_WORD_BITS
Definition: mp_core.h:21
Sign sign() const
Definition: bigint.h:360