Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 */
19 BigInt& BigInt::operator+=(const BigInt& y)
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);
42 set_sign(Positive);
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 */
54 BigInt& BigInt::operator-=(const BigInt& y)
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
70 set_sign(y.reverse_sign());
71 }
72 else if(relative_size == 0)
73 {
74 if(sign() == y.sign())
75 {
76 clear();
77 set_sign(Positive);
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 */
96 BigInt& BigInt::operator*=(const BigInt& y)
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();
104 set_sign(Positive);
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 */
131 BigInt& BigInt::operator/=(const BigInt& y)
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 */
143 BigInt& BigInt::operator%=(const BigInt& mod)
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
177 set_sign(BigInt::Positive);
178
179 return word_at(0);
180 }
181
182 /*
183 * Left Shift Operator
184 */
185 BigInt& BigInt::operator<<=(size_t shift)
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 */
203 BigInt& BigInt::operator>>=(size_t shift)
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())
213 set_sign(Positive);
214 }
215
216 return (*this);
217 }
218
219 }
Botan::bigint_shr1
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:281
Botan::bigint_sub2_rev
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.cpp:180
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::BigInt
Definition: bigint.h:23
Botan::BigInt::Positive
Definition: bigint.h:34
Botan::BigInt::operator*=
BigInt & operator*=(const BigInt &y)
Definition: big_ops2.cpp:96
Botan::bigint_cmp
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:378
Botan::bigint_sub2
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:157
Botan::bigint_linmul2
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.cpp:222
Botan::BigInt::reverse_sign
Sign reverse_sign() const
Definition: bigint.cpp:234
Botan::BigInt::mutable_data
word * mutable_data()
Definition: bigint.h:419
Botan::bigint_sub3
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:198
Botan::BigInt::size
size_t size() const
Definition: bigint.h:387
Botan::BigInt::operator<<=
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:185
Botan::BigInt::operator>>=
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:203
Botan::bigint_linmul3
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.cpp:240
Botan::BigInt::Negative
Definition: bigint.h:34
Botan::BigInt::operator%=
BigInt & operator%=(const BigInt &y)
Definition: big_ops2.cpp:143
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:184
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
Botan::BigInt::data
const word * data() const
Definition: bigint.h:425
Botan
Definition: alg_id.cpp:13
Botan::CT::max
T max(T a, T b)
Definition: ct_utils.h:173
Botan::BigInt::operator/=
BigInt & operator/=(const BigInt &y)
Definition: big_ops2.cpp:131
Botan::BigInt::clear
void clear()
Definition: bigint.h:217
Botan::BigInt::operator-=
BigInt & operator-=(const BigInt &y)
Definition: big_ops2.cpp:54
Botan::bigint_shl1
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:258
Botan::BigInt::grow_to
void grow_to(size_t n)
Definition: bigint.cpp:261
Botan::bigint_add2
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:138
Botan::bigint_mul
void bigint_mul(BigInt &z, const BigInt &x, const BigInt &y, word workspace[])
Definition: mp_karat.cpp:252
Botan::BigInt::BigInt
BigInt()=default
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::BigInt::DivideByZero
Definition: bigint.h:39
Botan::BigInt::operator+=
BigInt & operator+=(const BigInt &y)
Definition: big_ops2.cpp:19
Botan::bigint_modop
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:432
Botan::is_power_of_2
bool is_power_of_2(T arg)
Definition: bit_ops.h:25
Botan::zeroise
void zeroise(std::vector< T, Alloc > &vec)
Definition: secmem.h:211
Botan::MP_WORD_BITS
const size_t MP_WORD_BITS
Definition: mp_core.h:21
Botan::BigInt::sign
Sign sign() const
Definition: bigint.h:360