Botan 3.3.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_words, 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_words) + 1);
23
24 if(x.sign() == y_sign) {
25 bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
26 z.set_sign(x.sign());
27 } else {
28 const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
29
30 //z.sign_fixup(relative_size, y_sign);
31 if(relative_size < 0) {
32 z.set_sign(y_sign);
33 } else if(relative_size == 0) {
35 } else {
36 z.set_sign(x.sign());
37 }
38 }
39
40 return z;
41}
42
43/*
44* Multiplication Operator
45*/
46BigInt operator*(const BigInt& x, const BigInt& y) {
47 const size_t x_sw = x.sig_words();
48 const size_t y_sw = y.sig_words();
49
51
52 if(x_sw == 1 && y_sw) {
53 bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
54 } else if(y_sw == 1 && x_sw) {
55 bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
56 } else if(x_sw && y_sw) {
57 secure_vector<word> workspace(z.size());
58
60 z.size(),
61 x.data(),
62 x.size(),
63 x_sw,
64 y.data(),
65 y.size(),
66 y_sw,
67 workspace.data(),
68 workspace.size());
69 }
70
71 z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
72
73 return z;
74}
75
76/*
77* Multiplication Operator
78*/
79BigInt operator*(const BigInt& x, word y) {
80 const size_t x_sw = x.sig_words();
81
82 BigInt z = BigInt::with_capacity(x_sw + 1);
83
84 if(x_sw && y) {
85 bigint_linmul3(z.mutable_data(), x.data(), x_sw, y);
86 z.set_sign(x.sign());
87 }
88
89 return z;
90}
91
92/*
93* Division Operator
94*/
95BigInt operator/(const BigInt& x, const BigInt& y) {
96 if(y.sig_words() == 1) {
97 return x / y.word_at(0);
98 }
99
100 BigInt q, r;
101 vartime_divide(x, y, q, r);
102 return q;
103}
104
105/*
106* Division Operator
107*/
108BigInt operator/(const BigInt& x, word y) {
109 if(y == 0) {
110 throw Invalid_Argument("BigInt::operator/ divide by zero");
111 }
112
113 BigInt q;
114 word r;
115 ct_divide_word(x, y, q, r);
116 return q;
117}
118
119/*
120* Modulo Operator
121*/
122BigInt operator%(const BigInt& n, const BigInt& mod) {
123 if(mod.is_zero()) {
124 throw Invalid_Argument("BigInt::operator% divide by zero");
125 }
126 if(mod.is_negative()) {
127 throw Invalid_Argument("BigInt::operator% modulus must be > 0");
128 }
129 if(n.is_positive() && mod.is_positive() && n < mod) {
130 return n;
131 }
132
133 if(mod.sig_words() == 1) {
134 return BigInt::from_word(n % mod.word_at(0));
135 }
136
137 BigInt q, r;
138 vartime_divide(n, mod, q, r);
139 return r;
140}
141
142/*
143* Modulo Operator
144*/
145word operator%(const BigInt& n, word mod) {
146 if(mod == 0) {
147 throw Invalid_Argument("BigInt::operator% divide by zero");
148 }
149
150 if(mod == 1) {
151 return 0;
152 }
153
154 word remainder = 0;
155
156 if(is_power_of_2(mod)) {
157 remainder = (n.word_at(0) & (mod - 1));
158 } else {
159 const size_t sw = n.sig_words();
160 for(size_t i = sw; i > 0; --i) {
161 remainder = bigint_modop_vartime(remainder, n.word_at(i - 1), mod);
162 }
163 }
164
165 if(remainder && n.sign() == BigInt::Negative) {
166 return mod - remainder;
167 }
168 return remainder;
169}
170
171/*
172* Left Shift Operator
173*/
174BigInt operator<<(const BigInt& x, size_t shift) {
175 const size_t shift_words = shift / BOTAN_MP_WORD_BITS, shift_bits = shift % BOTAN_MP_WORD_BITS;
176
177 const size_t x_sw = x.sig_words();
178
179 BigInt y = BigInt::with_capacity(x_sw + shift_words + (shift_bits ? 1 : 0));
180 bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
181 y.set_sign(x.sign());
182 return y;
183}
184
185/*
186* Right Shift Operator
187*/
188BigInt operator>>(const BigInt& x, size_t shift) {
189 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
190 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
191 const size_t x_sw = x.sig_words();
192
193 if(shift_words >= x_sw) {
194 return BigInt::zero();
195 }
196
197 BigInt y = BigInt::with_capacity(x_sw - shift_words);
198 bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
199
200 if(x.is_negative() && y.is_zero()) {
202 } else {
203 y.set_sign(x.sign());
204 }
205
206 return y;
207}
208
209} // namespace Botan
static BigInt zero()
Definition bigint.h:45
size_t sig_words() const
Definition bigint.h:584
word * mutable_data()
Definition bigint.h:609
size_t size() const
Definition bigint.h:578
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:615
word word_at(size_t n) const
Definition bigint.h:518
void cond_flip_sign(bool predicate)
Definition bigint.cpp:475
Sign sign() const
Definition bigint.h:540
static BigInt from_word(word n)
Definition bigint.cpp:42
bool is_zero() const
Definition bigint.h:428
bool is_negative() const
Definition bigint.h:528
bool is_positive() const
Definition bigint.h:534
static BigInt with_capacity(size_t n)
Definition bigint.cpp:58
void set_sign(Sign sign)
Definition bigint.h:561
#define BOTAN_MP_WORD_BITS
Definition build.h:50
word bigint_modop_vartime(word n1, word n0, word d)
Definition mp_core.h:697
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:155
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition mp_core.h:468
constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:45
BigInt operator*(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:46
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_core.h:266
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition mp_core.h:355
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:282
std::ostream & operator<<(std::ostream &out, const OID &oid)
Definition asn1_oid.cpp:140
BigInt operator/(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:95
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition big_ops3.cpp:122
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition mp_core.h:417
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:80
int operator>>(int fd, Pipe &pipe)
Definition fd_unix.cpp:39
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition mp_core.h:431