Botan  2.19.1
Crypto and TLS for C++11
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/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 //static
18 BigInt 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(x.sign(), 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  }
28  else
29  {
30  const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
31 
32  //z.sign_fixup(relative_size, y_sign);
33  if(relative_size < 0)
34  z.set_sign(y_sign);
35  else if(relative_size == 0)
36  z.set_sign(BigInt::Positive);
37  }
38 
39  return z;
40  }
41 
42 /*
43 * Multiplication Operator
44 */
45 BigInt operator*(const BigInt& x, const BigInt& y)
46  {
47  const size_t x_sw = x.sig_words();
48  const size_t y_sw = y.sig_words();
49 
50  BigInt z(BigInt::Positive, x.size() + y.size());
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  {
58  secure_vector<word> workspace(z.size());
59 
60  bigint_mul(z.mutable_data(), z.size(),
61  x.data(), x.size(), x_sw,
62  y.data(), y.size(), y_sw,
63  workspace.data(), workspace.size());
64  }
65 
66  z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
67 
68  return z;
69  }
70 
71 /*
72 * Multiplication Operator
73 */
74 BigInt operator*(const BigInt& x, word y)
75  {
76  const size_t x_sw = x.sig_words();
77 
78  BigInt z(BigInt::Positive, x_sw + 1);
79 
80  if(x_sw && y)
81  {
82  bigint_linmul3(z.mutable_data(), x.data(), x_sw, y);
83  z.set_sign(x.sign());
84  }
85 
86  return z;
87  }
88 
89 /*
90 * Division Operator
91 */
92 BigInt operator/(const BigInt& x, const BigInt& y)
93  {
94  if(y.sig_words() == 1)
95  {
96  return x / y.word_at(0);
97  }
98 
99  BigInt q, r;
100  vartime_divide(x, y, q, r);
101  return q;
102  }
103 
104 /*
105 * Division Operator
106 */
107 BigInt operator/(const BigInt& x, word y)
108  {
109  if(y == 0)
110  throw BigInt::DivideByZero();
111  else if(y == 1)
112  return x;
113  else if(y == 2)
114  return (x >> 1);
115  else if(y <= 255)
116  {
117  BigInt q;
118  uint8_t r;
119  ct_divide_u8(x, static_cast<uint8_t>(y), q, r);
120  return q;
121  }
122 
123  BigInt q, r;
124  vartime_divide(x, y, q, r);
125  return q;
126  }
127 
128 /*
129 * Modulo Operator
130 */
131 BigInt operator%(const BigInt& n, const BigInt& mod)
132  {
133  if(mod.is_zero())
134  throw BigInt::DivideByZero();
135  if(mod.is_negative())
136  throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
137  if(n.is_positive() && mod.is_positive() && n < mod)
138  return n;
139 
140  if(mod.sig_words() == 1)
141  {
142  return n % mod.word_at(0);
143  }
144 
145  BigInt q, r;
146  vartime_divide(n, mod, q, r);
147  return r;
148  }
149 
150 /*
151 * Modulo Operator
152 */
153 word operator%(const BigInt& n, word mod)
154  {
155  if(mod == 0)
156  throw BigInt::DivideByZero();
157 
158  if(mod == 1)
159  return 0;
160 
161  word remainder = 0;
162 
163  if(is_power_of_2(mod))
164  {
165  remainder = (n.word_at(0) & (mod - 1));
166  }
167  else
168  {
169  const size_t sw = n.sig_words();
170  for(size_t i = sw; i > 0; --i)
171  {
172  remainder = bigint_modop(remainder, n.word_at(i-1), mod);
173  }
174  }
175 
176  if(remainder && n.sign() == BigInt::Negative)
177  return mod - remainder;
178  return remainder;
179  }
180 
181 /*
182 * Left Shift Operator
183 */
184 BigInt operator<<(const BigInt& x, size_t shift)
185  {
186  const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
187  shift_bits = shift % BOTAN_MP_WORD_BITS;
188 
189  const size_t x_sw = x.sig_words();
190 
191  BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
192  bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
193  return y;
194  }
195 
196 /*
197 * Right Shift Operator
198 */
199 BigInt operator>>(const BigInt& x, size_t shift)
200  {
201  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
202  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
203  const size_t x_sw = x.sig_words();
204 
205  BigInt y(x.sign(), x_sw - shift_words);
206  bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
207 
208  if(x.is_negative() && y.is_zero())
209  y.set_sign(BigInt::Positive);
210 
211  return y;
212  }
213 
214 }
word word_at(size_t n) const
Definition: bigint.h:508
size_t sig_words() const
Definition: bigint.h:586
int operator<<(int fd, Pipe &pipe)
Definition: fd_unix.cpp:17
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:159
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 * mutable_data()
Definition: bigint.h:614
bool is_negative() const
Definition: bigint.h:527
size_t size() const
Definition: bigint.h:580
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:92
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:377
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
const word * data() const
Definition: bigint.h:620
Definition: alg_id.cpp:13
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:298
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_u8(const BigInt &x, uint8_t y, BigInt &q_out, uint8_t &r_out)
Definition: divide.cpp:82
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:45
bool is_positive() const
Definition: bigint.h:533
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:40
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:131
bool is_zero() const
Definition: bigint.h:421
static BigInt add2(const BigInt &x, const word y[], size_t y_words, Sign y_sign)
Definition: big_ops3.cpp:18
void set_sign(Sign sign)
Definition: bigint.h:563
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:289
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:755
Sign sign() const
Definition: bigint.h:539