Botan  2.6.0
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 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 /*
18 * Addition Operator
19 */
20 BigInt operator+(const BigInt& x, const BigInt& y)
21  {
22  const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
23 
24  BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
25 
26  if(x.sign() == y.sign())
27  bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
28  else
29  {
30  int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
31 
32  if(relative_size < 0)
33  {
34  bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
35  z.set_sign(y.sign());
36  }
37  else if(relative_size == 0)
38  z.set_sign(BigInt::Positive);
39  else if(relative_size > 0)
40  bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
41  }
42 
43  return z;
44  }
45 
46 /*
47 * Subtraction Operator
48 */
49 BigInt operator-(const BigInt& x, const BigInt& y)
50  {
51  const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
52 
53  int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
54 
55  BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
56 
57  if(relative_size < 0)
58  {
59  if(x.sign() == y.sign())
60  bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
61  else
62  bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
63  z.set_sign(y.reverse_sign());
64  }
65  else if(relative_size == 0)
66  {
67  if(x.sign() != y.sign())
68  bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1);
69  z.set_sign(y.reverse_sign());
70  }
71  else if(relative_size > 0)
72  {
73  if(x.sign() == y.sign())
74  bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
75  else
76  bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
77  z.set_sign(x.sign());
78  }
79  return z;
80  }
81 
82 /*
83 * Multiplication Operator
84 */
85 BigInt operator*(const BigInt& x, const BigInt& y)
86  {
87  const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
88 
89  BigInt z(BigInt::Positive, x.size() + y.size());
90 
91  if(x_sw == 1 && y_sw)
92  bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
93  else if(y_sw == 1 && x_sw)
94  bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
95  else if(x_sw && y_sw)
96  {
97  secure_vector<word> workspace(z.size());
98 
99  bigint_mul(z.mutable_data(), z.size(),
100  x.data(), x.size(), x_sw,
101  y.data(), y.size(), y_sw,
102  workspace.data(), workspace.size());
103  }
104 
105  if(x_sw && y_sw && x.sign() != y.sign())
106  z.flip_sign();
107  return z;
108  }
109 
110 /*
111 * Division Operator
112 */
113 BigInt operator/(const BigInt& x, const BigInt& y)
114  {
115  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
116  return (x >> (y.bits() - 1));
117 
118  BigInt q, r;
119  divide(x, y, q, r);
120  return q;
121  }
122 
123 /*
124 * Modulo Operator
125 */
126 BigInt operator%(const BigInt& n, const BigInt& mod)
127  {
128  if(mod.is_zero())
129  throw BigInt::DivideByZero();
130  if(mod.is_negative())
131  throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
132  if(n.is_positive() && mod.is_positive() && n < mod)
133  return n;
134 
135  BigInt q, r;
136  divide(n, mod, q, r);
137  return r;
138  }
139 
140 /*
141 * Modulo Operator
142 */
143 word operator%(const BigInt& n, word mod)
144  {
145  if(mod == 0)
146  throw BigInt::DivideByZero();
147 
148  if(mod == 1)
149  return 0;
150 
151  if(is_power_of_2(mod))
152  return (n.word_at(0) & (mod - 1));
153 
154  word remainder = 0;
155 
156  for(size_t j = n.sig_words(); j > 0; --j)
157  remainder = bigint_modop(remainder, n.word_at(j-1), mod);
158 
159  if(remainder && n.sign() == BigInt::Negative)
160  return mod - remainder;
161  return remainder;
162  }
163 
164 /*
165 * Left Shift Operator
166 */
167 BigInt operator<<(const BigInt& x, size_t shift)
168  {
169  if(shift == 0)
170  return x;
171 
172  const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
173  shift_bits = shift % BOTAN_MP_WORD_BITS;
174 
175  const size_t x_sw = x.sig_words();
176 
177  BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
178  bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
179  return y;
180  }
181 
182 /*
183 * Right Shift Operator
184 */
185 BigInt operator>>(const BigInt& x, size_t shift)
186  {
187  if(shift == 0)
188  return x;
189  if(x.bits() <= shift)
190  return 0;
191 
192  const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
193  shift_bits = shift % BOTAN_MP_WORD_BITS,
194  x_sw = x.sig_words();
195 
196  BigInt y(x.sign(), x_sw - shift_words);
197  bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
198  return y;
199  }
200 
201 }
bool is_negative() const
Definition: bigint.h:413
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.cpp:376
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:398
size_t bits() const
Definition: bigint.cpp:216
Sign sign() const
Definition: bigint.h:425
bool is_zero() const
Definition: bigint.h:314
word * mutable_data()
Definition: bigint.h:498
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:49
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:218
word word_at(size_t n) const
Definition: bigint.h:399
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:113
const word * data() const
Definition: bigint.h:504
void divide(const BigInt &x, const BigInt &y_arg, BigInt &q, BigInt &r)
Definition: divide.cpp:58
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.cpp:260
Sign reverse_sign() const
Definition: bigint.h:430
size_t size() const
Definition: bigint.h:466
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:472
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:296
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:356
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:85
OID operator+(const OID &oid, uint32_t component)
Definition: asn1_oid.cpp:87
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:40
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:126
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:167
bool is_positive() const
Definition: bigint.h:419
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:457
bool is_power_of_2(T arg)
Definition: bit_ops.h:25