Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 /*
18 * Addition Operator
19 */
20 BigInt operator+(const BigInt& x, const BigInt& y)
21 {
22 const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
23
24 BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
25
26 if((x.sign() == y.sign()))
27 bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
28 else
29 {
30 int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
31
32 if(relative_size < 0)
33 {
34 bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
35 z.set_sign(y.sign());
36 }
37 else if(relative_size == 0)
38 z.set_sign(BigInt::Positive);
39 else if(relative_size > 0)
40 bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
41 }
42
43 return z;
44 }
45
46 /*
47 * Subtraction Operator
48 */
49 BigInt operator-(const BigInt& x, const BigInt& y)
50 {
51 const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
52
53 int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
54
55 BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
56
57 if(relative_size < 0)
58 {
59 if(x.sign() == y.sign())
60 bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
61 else
62 bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
63 z.set_sign(y.reverse_sign());
64 }
65 else if(relative_size == 0)
66 {
67 if(x.sign() != y.sign())
68 bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1);
69 }
70 else if(relative_size > 0)
71 {
72 if(x.sign() == y.sign())
73 bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
74 else
75 bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
76 z.set_sign(x.sign());
77 }
78 return z;
79 }
80
81 /*
82 * Multiplication Operator
83 */
84 BigInt operator*(const BigInt& x, const BigInt& y)
85 {
86 const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
87
88 BigInt z(BigInt::Positive, x.size() + y.size());
89
90 if(x_sw == 1 && y_sw)
91 bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
92 else if(y_sw == 1 && x_sw)
93 bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
94 else if(x_sw && y_sw)
95 {
96 secure_vector<word> workspace(z.size());
97 bigint_mul(z, x, y, workspace.data());
98 }
99
100 if(x_sw && y_sw && x.sign() != y.sign())
101 z.flip_sign();
102 return z;
103 }
104
105 /*
106 * Division Operator
107 */
108 BigInt operator/(const BigInt& x, const BigInt& y)
109 {
110 BigInt q, r;
111 divide(x, y, q, r);
112 return q;
113 }
114
115 /*
116 * Modulo Operator
117 */
118 BigInt operator%(const BigInt& n, const BigInt& mod)
119 {
120 if(mod.is_zero())
121 throw BigInt::DivideByZero();
122 if(mod.is_negative())
123 throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
124 if(n.is_positive() && mod.is_positive() && n < mod)
125 return n;
126
127 BigInt q, r;
128 divide(n, mod, q, r);
129 return r;
130 }
131
132 /*
133 * Modulo Operator
134 */
135 word operator%(const BigInt& n, word mod)
136 {
137 if(mod == 0)
138 throw BigInt::DivideByZero();
139
140 if(is_power_of_2(mod))
141 return (n.word_at(0) & (mod - 1));
142
143 word remainder = 0;
144
145 for(size_t j = n.sig_words(); j > 0; --j)
146 remainder = bigint_modop(remainder, n.word_at(j-1), mod);
147
148 if(remainder && n.sign() == BigInt::Negative)
149 return mod - remainder;
150 return remainder;
151 }
152
153 /*
154 * Left Shift Operator
155 */
156 BigInt operator<<(const BigInt& x, size_t shift)
157 {
158 if(shift == 0)
159 return x;
160
161 const size_t shift_words = shift / MP_WORD_BITS,
162 shift_bits = shift % MP_WORD_BITS;
163
164 const size_t x_sw = x.sig_words();
165
166 BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
167 bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
168 return y;
169 }
170
171 /*
172 * Right Shift Operator
173 */
174 BigInt operator>>(const BigInt& x, size_t shift)
175 {
176 if(shift == 0)
177 return x;
178 if(x.bits() <= shift)
179 return 0;
180
181 const size_t shift_words = shift / MP_WORD_BITS,
182 shift_bits = shift % MP_WORD_BITS,
183 x_sw = x.sig_words();
184
185 BigInt y(x.sign(), x_sw - shift_words);
186 bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
187 return y;
188 }
189
190 }
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::Invalid_Argument
Definition: exceptn.h:34
Botan::divide
void divide(const BigInt &x, const BigInt &y_arg, BigInt &q, BigInt &r)
Definition: divide.cpp:58
Botan::BigInt
Definition: bigint.h:23
Botan::BigInt::Positive
Definition: bigint.h:34
Botan::bigint_shr2
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:356
Botan::operator>>
std::istream & operator>>(std::istream &in, X509_DN &dn)
Definition: x509_dn.cpp:325
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::operator<<
std::ostream & operator<<(std::ostream &out, const X509_DN &dn)
Definition: x509_dn.cpp:299
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::is_negative
bool is_negative() const
Definition: bigint.h:348
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::operator+
OID operator+(const OID &oid, uint32_t component)
Definition: asn1_oid.cpp:87
Botan::operator%
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:118
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::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::operator*
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:84
Botan
Definition: alg_id.cpp:13
Botan::CT::max
T max(T a, T b)
Definition: ct_utils.h:173
Botan::bigint_shl2
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:336
Botan::BigInt::is_positive
bool is_positive() const
Definition: bigint.h:354
Botan::bigint_mul
void bigint_mul(BigInt &z, const BigInt &x, const BigInt &y, word workspace[])
Definition: mp_karat.cpp:252
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:250
Botan::operator-
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:49
Botan::bigint_add3
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:147
Botan::BigInt::DivideByZero
Definition: bigint.h:39
Botan::operator/
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:108
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::MP_WORD_BITS
const size_t MP_WORD_BITS
Definition: mp_core.h:21
Botan::BigInt::sign
Sign sign() const
Definition: bigint.h:360