Botan  2.4.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  secure_vector<word> workspace(size());
120  bigint_mul(*this, BigInt(*this), y, workspace.data());
121  }
122 
123  return (*this);
124  }
125 
126 /*
127 * Division Operator
128 */
130  {
131  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
132  (*this) >>= (y.bits() - 1);
133  else
134  (*this) = (*this) / y;
135  return (*this);
136  }
137 
138 /*
139 * Modulo Operator
140 */
142  {
143  return (*this = (*this) % mod);
144  }
145 
146 /*
147 * Modulo Operator
148 */
149 word BigInt::operator%=(word mod)
150  {
151  if(mod == 0)
152  throw BigInt::DivideByZero();
153 
154  if(is_power_of_2(mod))
155  {
156  word result = (word_at(0) & (mod - 1));
157  clear();
158  grow_to(2);
159  m_reg[0] = result;
160  return result;
161  }
162 
163  word remainder = 0;
164 
165  for(size_t j = sig_words(); j > 0; --j)
166  remainder = bigint_modop(remainder, word_at(j-1), mod);
167  clear();
168  grow_to(2);
169 
170  if(remainder && sign() == BigInt::Negative)
171  m_reg[0] = mod - remainder;
172  else
173  m_reg[0] = remainder;
174 
176 
177  return word_at(0);
178  }
179 
180 /*
181 * Left Shift Operator
182 */
184  {
185  if(shift)
186  {
187  const size_t shift_words = shift / MP_WORD_BITS,
188  shift_bits = shift % MP_WORD_BITS,
189  words = sig_words();
190 
191  grow_to(words + shift_words + (shift_bits ? 1 : 0));
192  bigint_shl1(mutable_data(), words, shift_words, shift_bits);
193  }
194 
195  return (*this);
196  }
197 
198 /*
199 * Right Shift Operator
200 */
202  {
203  if(shift)
204  {
205  const size_t shift_words = shift / MP_WORD_BITS,
206  shift_bits = shift % MP_WORD_BITS;
207 
208  bigint_shr1(mutable_data(), sig_words(), shift_words, shift_bits);
209 
210  if(is_zero())
212  }
213 
214  return (*this);
215  }
216 
217 }
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
Sign reverse_sign() const
Definition: bigint.cpp:233
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
size_t bits() const
Definition: bigint.cpp:183
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 sign() const
Definition: bigint.h:365
bool is_zero() const
Definition: bigint.h:255
word * mutable_data()
Definition: bigint.h:424
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:198
word word_at(size_t n) const
Definition: bigint.h:340
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:183
const word * data() const
Definition: bigint.h:430
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:201
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:141
size_t size() const
Definition: bigint.h:392
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:398
BigInt & operator/=(const BigInt &y)
Definition: big_ops2.cpp:129
void clear()
Definition: bigint.h:222
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:260
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:253
BigInt()=default
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
void set_sign(Sign sign)
Definition: bigint.cpp:214
BigInt & operator+=(const BigInt &y)
Definition: big_ops2.cpp:19
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:437
bool is_power_of_2(T arg)
Definition: bit_ops.h:25
void zeroise(std::vector< T, Alloc > &vec)
Definition: secmem.h:181
const size_t MP_WORD_BITS
Definition: mp_core.h:22