Botan 3.0.0-alpha0
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#include <botan/internal/divide.h>
11#include <botan/internal/mp_core.h>
12#include <botan/internal/bit_ops.h>
13#include <algorithm>
14
15namespace Botan {
16
17//static
18BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_words, BigInt::Sign y_sign)
19 {
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 {
26 bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
27 z.set_sign(x.sign());
28 }
29 else
30 {
31 const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
32
33 //z.sign_fixup(relative_size, y_sign);
34 if(relative_size < 0)
35 z.set_sign(y_sign);
36 else if(relative_size == 0)
38 else
39 z.set_sign(x.sign());
40 }
41
42 return z;
43 }
44
45/*
46* Multiplication Operator
47*/
48BigInt operator*(const BigInt& x, const BigInt& y)
49 {
50 const size_t x_sw = x.sig_words();
51 const size_t y_sw = y.sig_words();
52
54
55 if(x_sw == 1 && y_sw)
56 bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
57 else if(y_sw == 1 && x_sw)
58 bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
59 else if(x_sw && y_sw)
60 {
61 secure_vector<word> workspace(z.size());
62
64 x.data(), x.size(), x_sw,
65 y.data(), y.size(), y_sw,
66 workspace.data(), workspace.size());
67 }
68
69 z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
70
71 return z;
72 }
73
74/*
75* Multiplication Operator
76*/
77BigInt operator*(const BigInt& x, word y)
78 {
79 const size_t x_sw = x.sig_words();
80
81 BigInt z = BigInt::with_capacity(x_sw + 1);
82
83 if(x_sw && y)
84 {
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 {
97 if(y.sig_words() == 1)
98 {
99 return x / y.word_at(0);
100 }
101
102 BigInt q, r;
103 vartime_divide(x, y, q, r);
104 return q;
105 }
106
107/*
108* Division Operator
109*/
110BigInt operator/(const BigInt& x, word y)
111 {
112 if(y == 0)
113 throw Invalid_Argument("BigInt::operator/ divide by zero");
114
115 BigInt q;
116 word r;
117 ct_divide_word(x, y, q, r);
118 return q;
119 }
120
121/*
122* Modulo Operator
123*/
124BigInt operator%(const BigInt& n, const BigInt& mod)
125 {
126 if(mod.is_zero())
127 throw Invalid_Argument("BigInt::operator% divide by zero");
128 if(mod.is_negative())
129 throw Invalid_Argument("BigInt::operator% modulus must be > 0");
130 if(n.is_positive() && mod.is_positive() && n < mod)
131 return n;
132
133 if(mod.sig_words() == 1)
134 {
135 return BigInt::from_word(n % mod.word_at(0));
136 }
137
138 BigInt q, r;
139 vartime_divide(n, mod, q, r);
140 return r;
141 }
142
143/*
144* Modulo Operator
145*/
146word operator%(const BigInt& n, word mod)
147 {
148 if(mod == 0)
149 throw Invalid_Argument("BigInt::operator% divide by zero");
150
151 if(mod == 1)
152 return 0;
153
154 word remainder = 0;
155
156 if(is_power_of_2(mod))
157 {
158 remainder = (n.word_at(0) & (mod - 1));
159 }
160 else
161 {
162 const size_t sw = n.sig_words();
163 for(size_t i = sw; i > 0; --i)
164 {
165 remainder = bigint_modop(remainder, n.word_at(i-1), mod);
166 }
167 }
168
169 if(remainder && n.sign() == BigInt::Negative)
170 return mod - remainder;
171 return remainder;
172 }
173
174/*
175* Left Shift Operator
176*/
177BigInt operator<<(const BigInt& x, size_t shift)
178 {
179 const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
180 shift_bits = shift % BOTAN_MP_WORD_BITS;
181
182 const size_t x_sw = x.sig_words();
183
184 BigInt y = BigInt::with_capacity(x_sw + shift_words + (shift_bits ? 1 : 0));
185 bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
186 y.set_sign(x.sign());
187 return y;
188 }
189
190/*
191* Right Shift Operator
192*/
193BigInt operator>>(const BigInt& x, size_t shift)
194 {
195 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
196 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
197 const size_t x_sw = x.sig_words();
198
199 if(shift_words >= x_sw)
200 return BigInt::zero();
201
202 BigInt y = BigInt::with_capacity(x_sw - shift_words);
203 bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
204
205 if(x.is_negative() && y.is_zero())
207 else
208 y.set_sign(x.sign());
209
210 return y;
211 }
212
213}
static BigInt zero()
Definition: bigint.h:45
size_t sig_words() const
Definition: bigint.h:600
word * mutable_data()
Definition: bigint.h:628
size_t size() const
Definition: bigint.h:594
static BigInt add2(const BigInt &x, const word y[], size_t y_words, Sign y_sign)
Definition: big_ops3.cpp:18
const word * data() const
Definition: bigint.h:634
word word_at(size_t n) const
Definition: bigint.h:522
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:471
Sign sign() const
Definition: bigint.h:553
static BigInt from_word(word n)
Definition: bigint.cpp:43
bool is_zero() const
Definition: bigint.h:430
bool is_negative() const
Definition: bigint.h:541
bool is_positive() const
Definition: bigint.h:547
static BigInt with_capacity(size_t n)
Definition: bigint.cpp:60
void set_sign(Sign sign)
Definition: bigint.h:577
#define BOTAN_MP_WORD_BITS
Definition: build.h:52
Definition: alg_id.cpp:13
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:165
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:48
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:289
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:377
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:297
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:124
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:449
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition: divide.cpp:84
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:40
int operator<<(int fd, Pipe &pipe)
Definition: fd_unix.cpp:17
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:466
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:755
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43