Botan 3.14.1
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/exceptn.h>
12#include <botan/internal/bit_ops.h>
13#include <botan/internal/divide.h>
14#include <botan/internal/mp_core.h>
15#include <algorithm>
16
17namespace Botan {
18
19//static
20BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_size, BigInt::Sign y_sign) {
21 const size_t x_sw = x.sig_words();
22
23 BigInt z = BigInt::with_capacity(std::max(x_sw, y_size) + 1);
24
25 if(x.sign() == y_sign) {
26 const word carry = bigint_add3(z.mutable_data(), x._data(), x_sw, y, y_size);
27 z.mutable_data()[std::max(x_sw, y_size)] += carry;
28 z.set_sign(x.sign());
29 } else {
30 const int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_size);
31
32 if(relative_size < 0) {
33 // x < y so z = abs(y - x)
34 // NOLINTNEXTLINE(*-suspicious-call-argument) intentionally swapping x and y here
35 bigint_sub3(z.mutable_data(), y, y_size, x.data(), x_sw);
36 z.set_sign(y_sign);
37 } else if(relative_size == 0) {
38 // Positive zero (nothing to do in this case)
39 } else {
40 /*
41 * We know at this point that x >= y so if y_size is larger than
42 * x_sw, we are guaranteed they are just leading zeros which can
43 * be ignored
44 */
45 y_size = std::min(x_sw, y_size);
46 bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_size);
47 z.set_sign(x.sign());
48 }
49 }
50
51 return z;
52}
53
54/*
55* Multiplication Operator
56*/
57BigInt operator*(const BigInt& x, const BigInt& y) {
58 const size_t x_sw = x.sig_words();
59 const size_t y_sw = y.sig_words();
60
62
63 if(x_sw == 1 && y_sw > 0) {
64 bigint_linmul3(z.mutable_data(), y._data(), y_sw, x.word_at(0));
65 } else if(y_sw == 1 && x_sw > 0) {
66 bigint_linmul3(z.mutable_data(), x._data(), x_sw, y.word_at(0));
67 } else if(x_sw > 0 && y_sw > 0) {
68 secure_vector<word> workspace(z.size());
69
71 z.size(),
72 x._data(),
73 x.size(),
74 x_sw,
75 y._data(),
76 y.size(),
77 y_sw,
78 workspace.data(),
79 workspace.size());
80 }
81
82 z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
83
84 return z;
85}
86
87/*
88* Multiplication Operator
89*/
91 const size_t x_sw = x.sig_words();
92
93 BigInt z = BigInt::with_capacity(x_sw + 1);
94 bigint_linmul3(z.mutable_data(), x._data(), x_sw, y);
95 z.set_sign(x.sign());
96 return z;
97}
98
99/*
100* Division Operator
101*/
102BigInt operator/(const BigInt& x, const BigInt& y) {
103 if(y.sig_words() == 1 && y.signum() >= 0) {
104 return x / y.word_at(0);
105 }
106
107 BigInt q;
108 BigInt r;
109 ct_divide(x, y, q, r);
110 return q;
111}
112
113/*
114* Division Operator
115*/
117 if(y == 0) {
118 throw Invalid_Argument("BigInt::operator/ divide by zero");
119 }
120
121 BigInt q;
122 word r = 0;
123 ct_divide_word(x, y, q, r);
124 return q;
125}
126
127/*
128* Modulo Operator
129*/
130BigInt operator%(const BigInt& n, const BigInt& mod) {
131 if(mod.is_zero()) {
132 throw Invalid_Argument("BigInt::operator% divide by zero");
133 }
134 if(mod.signum() < 0) {
135 throw Invalid_Argument("BigInt::operator% modulus must be > 0");
136 }
137 if(n.signum() >= 0 && mod.signum() >= 0 && n < mod) {
138 return n;
139 }
140
141 if(mod.sig_words() == 1) {
142 return BigInt::from_word(n % mod.word_at(0));
143 }
144
145 BigInt q;
146 BigInt r;
147 ct_divide(n, mod, q, r);
148 return r;
149}
150
151/*
152* Modulo Operator
153*/
154word operator%(const BigInt& n, word mod) {
155 if(mod == 0) {
156 throw Invalid_Argument("BigInt::operator% divide by zero");
157 }
158
159 if(mod == 1) {
160 return 0;
161 }
162
163 word remainder = 0;
164
165 if(n.signum() >= 0 && is_power_of_2(mod)) {
166 remainder = (n.word_at(0) & (mod - 1));
167 } else {
168 const auto redc_mod = divide_precomp<word>::setup_vartime(mod);
169 const size_t sw = n.sig_words();
170 for(size_t i = sw; i > 0; --i) {
171 remainder = redc_mod.mod_2to1(remainder, n.word_at(i - 1));
172 }
173 }
174
175 if(remainder != 0 && n.sign() == BigInt::Negative) {
176 return mod - remainder;
177 }
178 return remainder;
179}
180
181/*
182* Left Shift Operator
183*/
184BigInt operator<<(const BigInt& x, size_t shift) {
185 if(shift >= 65536) {
186 throw Invalid_Argument("BigInt left shift count too large");
187 }
188
189 if(x.is_zero()) {
190 return BigInt::zero();
191 }
192
193 const size_t x_sw = x.sig_words();
194
195 const size_t new_size = x_sw + shift / WordInfo<word>::bits + 1;
196 BigInt y = BigInt::with_capacity(new_size);
197 bigint_shl2(y.mutable_data(), new_size, x._data(), x_sw, shift);
198 y.set_sign(x.sign());
199 return y;
200}
201
202/*
203* Right Shift Operator
204*/
205BigInt operator>>(const BigInt& x, size_t shift) {
206 const size_t shift_words = shift / WordInfo<word>::bits;
207 const size_t x_sw = x.sig_words();
208
209 if(shift_words >= x_sw) {
210 return BigInt::zero();
211 }
212
213 const size_t new_size = x_sw - shift_words;
214 BigInt y = BigInt::with_capacity(new_size);
215 bigint_shr2(y.mutable_data(), new_size, x._data(), x_sw, shift);
216
217 if(x.signum() < 0 && y.is_zero()) {
219 } else {
220 y.set_sign(x.sign());
221 }
222
223 return y;
224}
225
226} // namespace Botan
static BigInt zero()
Definition bigint.h:50
size_t sig_words() const
Definition bigint.h:687
BigInt()=default
word * mutable_data()
Definition bigint.h:712
size_t size() const
Definition bigint.h:681
static BigInt add2(const BigInt &x, const word y[], size_t y_words, Sign y_sign)
Definition big_ops3.cpp:20
const word * data() const
Definition bigint.h:718
int signum() const
Definition bigint.h:493
word word_at(size_t n) const
Definition bigint.h:601
void cond_flip_sign(bool predicate)
Definition bigint.cpp:524
const word * _data() const
Definition bigint.h:1033
Sign sign() const
Definition bigint.h:641
static BigInt from_word(word n)
Definition bigint.cpp:36
bool is_zero() const
Definition bigint.h:510
static BigInt with_capacity(size_t n)
Definition bigint.cpp:52
void set_sign(Sign sign)
Definition bigint.h:663
static constexpr divide_precomp setup_vartime(W divisor)
Definition mp_core.h:687
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:420
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:62
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:124
BigInt operator*(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:57
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:196
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_oid.cpp:308
BigInt operator/(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:102
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition big_ops3.cpp:130
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:463
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:180
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:205
constexpr void bigint_shr2(W y[], size_t y_size, const W x[], size_t x_size, size_t shift)
Definition mp_core.h:382
int operator>>(int fd, Pipe &pipe)
Definition fd_unix.cpp:43
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
constexpr void bigint_shl2(W y[], size_t y_size, const W x[], size_t x_size, size_t shift)
Definition mp_core.h:359
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131