Botan  1.10.9
big_ops2.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Assignment Operators
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/bigint.h>
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/bit_ops.h>
11 #include <algorithm>
12 
13 namespace Botan {
14 
15 /*
16 * Addition Operator
17 */
19  {
20  const size_t x_sw = sig_words(), y_sw = y.sig_words();
21 
22  const size_t reg_size = std::max(x_sw, y_sw) + 1;
23  grow_to(reg_size);
24 
25  if(sign() == y.sign())
26  bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw);
27  else
28  {
29  s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
30 
31  if(relative_size < 0)
32  {
33  SecureVector<word> z(reg_size - 1);
34  bigint_sub3(z, y.data(), reg_size - 1, data(), x_sw);
35  copy_mem(&reg[0], &z[0], z.size());
36  set_sign(y.sign());
37  }
38  else if(relative_size == 0)
39  {
40  zeroise(reg);
42  }
43  else if(relative_size > 0)
44  bigint_sub2(get_reg(), x_sw, y.data(), y_sw);
45  }
46 
47  return (*this);
48  }
49 
50 /*
51 * Subtraction Operator
52 */
54  {
55  const size_t x_sw = sig_words(), y_sw = y.sig_words();
56 
57  s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
58 
59  const size_t reg_size = std::max(x_sw, y_sw) + 1;
60  grow_to(reg_size);
61 
62  if(relative_size < 0)
63  {
64  if(sign() == y.sign())
65  bigint_sub2_rev(get_reg(), y.data(), y_sw);
66  else
67  bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw);
68 
70  }
71  else if(relative_size == 0)
72  {
73  if(sign() == y.sign())
74  {
75  clear();
77  }
78  else
79  bigint_shl1(get_reg(), x_sw, 0, 1);
80  }
81  else if(relative_size > 0)
82  {
83  if(sign() == y.sign())
84  bigint_sub2(get_reg(), x_sw, y.data(), y_sw);
85  else
86  bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw);
87  }
88 
89  return (*this);
90  }
91 
92 /*
93 * Multiplication Operator
94 */
96  {
97  const size_t x_sw = sig_words(), y_sw = y.sig_words();
98  set_sign((sign() == y.sign()) ? Positive : Negative);
99 
100  if(x_sw == 0 || y_sw == 0)
101  {
102  clear();
104  }
105  else if(x_sw == 1 && y_sw)
106  {
107  grow_to(y_sw + 2);
108  bigint_linmul3(get_reg(), y.data(), y_sw, word_at(0));
109  }
110  else if(y_sw == 1 && x_sw)
111  {
112  grow_to(x_sw + 2);
113  bigint_linmul2(get_reg(), x_sw, y.word_at(0));
114  }
115  else
116  {
117  grow_to(size() + y.size());
118 
119  SecureVector<word> z(data(), x_sw);
120  SecureVector<word> workspace(size());
121 
122  bigint_mul(get_reg(), size(), workspace,
123  z, z.size(), x_sw,
124  y.data(), y.size(), y_sw);
125  }
126 
127  return (*this);
128  }
129 
130 /*
131 * Division Operator
132 */
134  {
135  if(y.sig_words() == 1 && power_of_2(y.word_at(0)))
136  (*this) >>= (y.bits() - 1);
137  else
138  (*this) = (*this) / y;
139  return (*this);
140  }
141 
142 /*
143 * Modulo Operator
144 */
146  {
147  return (*this = (*this) % mod);
148  }
149 
150 /*
151 * Modulo Operator
152 */
154  {
155  if(mod == 0)
156  throw BigInt::DivideByZero();
157  if(power_of_2(mod))
158  {
159  word result = (word_at(0) & (mod - 1));
160  clear();
161  grow_to(2);
162  get_reg()[0] = result;
163  return result;
164  }
165 
166  word remainder = 0;
167 
168  for(size_t j = sig_words(); j > 0; --j)
169  remainder = bigint_modop(remainder, word_at(j-1), mod);
170  clear();
171  grow_to(2);
172 
173  if(remainder && sign() == BigInt::Negative)
174  get_reg()[0] = mod - remainder;
175  else
176  get_reg()[0] = remainder;
177 
179 
180  return word_at(0);
181  }
182 
183 /*
184 * Left Shift Operator
185 */
187  {
188  if(shift)
189  {
190  const size_t shift_words = shift / MP_WORD_BITS,
191  shift_bits = shift % MP_WORD_BITS,
192  words = sig_words();
193 
194  grow_to(words + shift_words + (shift_bits ? 1 : 0));
195  bigint_shl1(get_reg(), words, shift_words, shift_bits);
196  }
197 
198  return (*this);
199  }
200 
201 /*
202 * Right Shift Operator
203 */
205  {
206  if(shift)
207  {
208  const size_t shift_words = shift / MP_WORD_BITS,
209  shift_bits = shift % MP_WORD_BITS;
210 
211  bigint_shr1(get_reg(), sig_words(), shift_words, shift_bits);
212 
213  if(is_zero())
215  }
216 
217  return (*this);
218  }
219 
220 }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_shift.cpp:42
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_asm.cpp:108
word word_at(size_t n) const
Definition: bigint.h:238
size_t sig_words() const
Definition: bigint.h:290
BigInt & operator*=(const BigInt &y)
Definition: big_ops2.cpp:95
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_asm.cpp:87
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_asm.cpp:149
Sign reverse_sign() const
Definition: bigint.cpp:310
SecureVector< word > & get_reg()
Definition: bigint.h:325
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_asm.cpp:127
size_t size() const
Definition: bigint.h:284
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:186
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:204
signed int s32bit
Definition: types.h:37
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_asm.cpp:167
BigInt & operator%=(const BigInt &y)
Definition: big_ops2.cpp:145
size_t bits() const
Definition: bigint.cpp:253
const word * data() const
Definition: bigint.h:317
GMP_MPZ mod
Definition: gmp_powm.cpp:29
size_t size() const
Definition: secmem.h:29
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:22
BigInt & operator/=(const BigInt &y)
Definition: big_ops2.cpp:133
void clear()
Definition: bigint.h:143
bool power_of_2(T arg)
Definition: bit_ops.h:21
BigInt & operator-=(const BigInt &y)
Definition: big_ops2.cpp:53
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_shift.cpp:18
void bigint_mul(word z[], size_t z_size, word workspace[], const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw)
Definition: mp_karat.cpp:248
void grow_to(size_t n)
Definition: bigint.cpp:123
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_asm.cpp:68
bool is_zero() const
Definition: bigint.h:176
void set_sign(Sign sign)
Definition: bigint.cpp:291
void zeroise(MemoryRegion< T > &vec)
Definition: secmem.h:415
s32bit bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_misc.cpp:41
BigInt & operator+=(const BigInt &y)
Definition: big_ops2.cpp:18
word bigint_modop(word n1, word n0, word d)
Definition: mp_misc.cpp:92
const size_t MP_WORD_BITS
Definition: mp_core.h:18
Sign sign() const
Definition: bigint.h:257