Botan 3.9.0
Crypto and TLS for C&
big_ops3.cpp
Go to the documentation of this file.
1/*
2* BigInt Binary Operators
3* (C) 1999-2007,2018 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
11#include <botan/internal/bit_ops.h>
12#include <botan/internal/divide.h>
13#include <botan/internal/mp_core.h>
14#include <algorithm>
15
16namespace Botan {
17
18//static
19BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_size, BigInt::Sign y_sign) {
20 const size_t x_sw = x.sig_words();
21
22 BigInt z = BigInt::with_capacity(std::max(x_sw, y_size) + 1);
23
24 if(x.sign() == y_sign) {
25 word carry = bigint_add3(z.mutable_data(), x._data(), x_sw, y, y_size);
26 z.mutable_data()[std::max(x_sw, y_size)] += carry;
27 z.set_sign(x.sign());
28 } else {
29 const int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_size);
30
31 if(relative_size < 0) {
32 // x < y so z = abs(y - x)
33 // NOLINTNEXTLINE(*-suspicious-call-argument) intentionally swapping x and y here
34 bigint_sub3(z.mutable_data(), y, y_size, x.data(), x_sw);
35 z.set_sign(y_sign);
36 } else if(relative_size == 0) {
37 // Positive zero (nothing to do in this case)
38 } else {
39 /*
40 * We know at this point that x >= y so if y_size is larger than
41 * x_sw, we are guaranteed they are just leading zeros which can
42 * be ignored
43 */
44 y_size = std::min(x_sw, y_size);
45 bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_size);
46 z.set_sign(x.sign());
47 }
48 }
49
50 return z;
51}
52
53/*
54* Multiplication Operator
55*/
56BigInt operator*(const BigInt& x, const BigInt& y) {
57 const size_t x_sw = x.sig_words();
58 const size_t y_sw = y.sig_words();
59
61
62 if(x_sw == 1 && y_sw > 0) {
63 bigint_linmul3(z.mutable_data(), y._data(), y_sw, x.word_at(0));
64 } else if(y_sw == 1 && x_sw > 0) {
65 bigint_linmul3(z.mutable_data(), x._data(), x_sw, y.word_at(0));
66 } else if(x_sw > 0 && y_sw > 0) {
67 secure_vector<word> workspace(z.size());
68
70 z.size(),
71 x._data(),
72 x.size(),
73 x_sw,
74 y._data(),
75 y.size(),
76 y_sw,
77 workspace.data(),
78 workspace.size());
79 }
80
81 z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
82
83 return z;
84}
85
86/*
87* Multiplication Operator
88*/
90 const size_t x_sw = x.sig_words();
91
92 BigInt z = BigInt::with_capacity(x_sw + 1);
93
94 if(x_sw > 0 && y > 0) {
95 bigint_linmul3(z.mutable_data(), x._data(), x_sw, y);
96 z.set_sign(x.sign());
97 }
98
99 return z;
100}
101
102/*
103* Division Operator
104*/
105BigInt operator/(const BigInt& x, const BigInt& y) {
106 if(y.sig_words() == 1) {
107 return x / y.word_at(0);
108 }
109
110 BigInt q;
111 BigInt r;
112 vartime_divide(x, y, q, r);
113 return q;
114}
115
116/*
117* Division Operator
118*/
120 if(y == 0) {
121 throw Invalid_Argument("BigInt::operator/ divide by zero");
122 }
123
124 BigInt q;
125 word r = 0;
126 ct_divide_word(x, y, q, r);
127 return q;
128}
129
130/*
131* Modulo Operator
132*/
133BigInt operator%(const BigInt& n, const BigInt& mod) {
134 if(mod.is_zero()) {
135 throw Invalid_Argument("BigInt::operator% divide by zero");
136 }
137 if(mod.is_negative()) {
138 throw Invalid_Argument("BigInt::operator% modulus must be > 0");
139 }
140 if(n.is_positive() && mod.is_positive() && n < mod) {
141 return n;
142 }
143
144 if(mod.sig_words() == 1) {
145 return BigInt::from_word(n % mod.word_at(0));
146 }
147
148 BigInt q;
149 BigInt r;
150 vartime_divide(n, mod, q, r);
151 return r;
152}
153
154/*
155* Modulo Operator
156*/
157word operator%(const BigInt& n, word mod) {
158 if(mod == 0) {
159 throw Invalid_Argument("BigInt::operator% divide by zero");
160 }
161
162 if(mod == 1) {
163 return 0;
164 }
165
166 word remainder = 0;
167
168 if(is_power_of_2(mod)) {
169 remainder = (n.word_at(0) & (mod - 1));
170 } else {
171 const size_t sw = n.sig_words();
172 for(size_t i = sw; i > 0; --i) {
173 remainder = bigint_modop_vartime(remainder, n.word_at(i - 1), mod);
174 }
175 }
176
177 if(remainder != 0 && n.sign() == BigInt::Negative) {
178 return mod - remainder;
179 }
180 return remainder;
181}
182
183/*
184* Left Shift Operator
185*/
186BigInt operator<<(const BigInt& x, size_t shift) {
187 const size_t x_sw = x.sig_words();
188
189 const size_t new_size = x_sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
190 BigInt y = BigInt::with_capacity(new_size);
191 bigint_shl2(y.mutable_data(), x._data(), x_sw, shift);
192 y.set_sign(x.sign());
193 return y;
194}
195
196/*
197* Right Shift Operator
198*/
199BigInt operator>>(const BigInt& x, size_t shift) {
200 const size_t shift_words = shift / WordInfo<word>::bits;
201 const size_t x_sw = x.sig_words();
202
203 if(shift_words >= x_sw) {
204 return BigInt::zero();
205 }
206
207 BigInt y = BigInt::with_capacity(x_sw - shift_words);
208 bigint_shr2(y.mutable_data(), x._data(), x_sw, shift);
209
210 if(x.is_negative() && y.is_zero()) {
212 } else {
213 y.set_sign(x.sign());
214 }
215
216 return y;
217}
218
219} // namespace Botan
static BigInt zero()
Definition bigint.h:49
size_t sig_words() const
Definition bigint.h:615
BigInt()=default
word * mutable_data()
Definition bigint.h:640
size_t size() const
Definition bigint.h:609
static BigInt add2(const BigInt &x, const word y[], size_t y_words, Sign y_sign)
Definition big_ops3.cpp:19
const word * data() const
Definition bigint.h:646
word word_at(size_t n) const
Definition bigint.h:547
void cond_flip_sign(bool predicate)
Definition bigint.cpp:519
const word * _data() const
Definition bigint.h:936
Sign sign() const
Definition bigint.h:571
static BigInt from_word(word n)
Definition bigint.cpp:34
bool is_zero() const
Definition bigint.h:457
bool is_negative() const
Definition bigint.h:559
bool is_positive() const
Definition bigint.h:565
static BigInt with_capacity(size_t n)
Definition bigint.cpp:50
void set_sign(Sign sign)
Definition bigint.h:592
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:405
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:45
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:122
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:230
constexpr void bigint_shr2(W y[], const W x[], size_t x_size, size_t shift)
Definition mp_core.h:370
BigInt operator*(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:56
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:194
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:283
std::ostream & operator<<(std::ostream &out, const OID &oid)
Definition asn1_obj.h:334
BigInt operator/(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:105
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition big_ops3.cpp:133
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:428
constexpr void bigint_shl2(W y[], const W x[], size_t x_size, size_t shift)
Definition mp_core.h:352
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:123
void carry(int64_t &h0, int64_t &h1)
int operator>>(int fd, Pipe &pipe)
Definition fd_unix.cpp:39
constexpr auto bigint_modop_vartime(W n1, W n0, W d) -> W
Definition mp_core.h:568
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119