Botan  2.4.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  }
70  else if(relative_size > 0)
71  {
72  if(x.sign() == y.sign())
73  bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
74  else
75  bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
76  z.set_sign(x.sign());
77  }
78  return z;
79  }
80 
81 /*
82 * Multiplication Operator
83 */
84 BigInt operator*(const BigInt& x, const BigInt& y)
85  {
86  const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
87 
88  BigInt z(BigInt::Positive, x.size() + y.size());
89 
90  if(x_sw == 1 && y_sw)
91  bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
92  else if(y_sw == 1 && x_sw)
93  bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
94  else if(x_sw && y_sw)
95  {
96  secure_vector<word> workspace(z.size());
97  bigint_mul(z, x, y, workspace.data());
98  }
99 
100  if(x_sw && y_sw && x.sign() != y.sign())
101  z.flip_sign();
102  return z;
103  }
104 
105 /*
106 * Division Operator
107 */
108 BigInt operator/(const BigInt& x, const BigInt& y)
109  {
110  BigInt q, r;
111  divide(x, y, q, r);
112  return q;
113  }
114 
115 /*
116 * Modulo Operator
117 */
118 BigInt operator%(const BigInt& n, const BigInt& mod)
119  {
120  if(mod.is_zero())
121  throw BigInt::DivideByZero();
122  if(mod.is_negative())
123  throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
124  if(n.is_positive() && mod.is_positive() && n < mod)
125  return n;
126 
127  BigInt q, r;
128  divide(n, mod, q, r);
129  return r;
130  }
131 
132 /*
133 * Modulo Operator
134 */
135 word operator%(const BigInt& n, word mod)
136  {
137  if(mod == 0)
138  throw BigInt::DivideByZero();
139 
140  if(is_power_of_2(mod))
141  return (n.word_at(0) & (mod - 1));
142 
143  word remainder = 0;
144 
145  for(size_t j = n.sig_words(); j > 0; --j)
146  remainder = bigint_modop(remainder, n.word_at(j-1), mod);
147 
148  if(remainder && n.sign() == BigInt::Negative)
149  return mod - remainder;
150  return remainder;
151  }
152 
153 /*
154 * Left Shift Operator
155 */
156 BigInt operator<<(const BigInt& x, size_t shift)
157  {
158  if(shift == 0)
159  return x;
160 
161  const size_t shift_words = shift / MP_WORD_BITS,
162  shift_bits = shift % MP_WORD_BITS;
163 
164  const size_t x_sw = x.sig_words();
165 
166  BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
167  bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
168  return y;
169  }
170 
171 /*
172 * Right Shift Operator
173 */
174 BigInt operator>>(const BigInt& x, size_t shift)
175  {
176  if(shift == 0)
177  return x;
178  if(x.bits() <= shift)
179  return 0;
180 
181  const size_t shift_words = shift / MP_WORD_BITS,
182  shift_bits = shift % MP_WORD_BITS,
183  x_sw = x.sig_words();
184 
185  BigInt y(x.sign(), x_sw - shift_words);
186  bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
187  return y;
188  }
189 
190 }
Sign reverse_sign() const
Definition: bigint.cpp:233
bool is_negative() const
Definition: bigint.h:353
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:356
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:378
size_t bits() const
Definition: bigint.cpp:183
Sign sign() const
Definition: bigint.h:365
bool is_zero() const
Definition: bigint.h:255
word * mutable_data()
Definition: bigint.h:424
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:198
word word_at(size_t n) const
Definition: bigint.h:340
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:108
const word * data() const
Definition: bigint.h:430
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:240
size_t size() const
Definition: bigint.h:392
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:398
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:336
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:84
OID operator+(const OID &oid, uint32_t component)
Definition: asn1_oid.cpp:87
void bigint_mul(BigInt &z, const BigInt &x, const BigInt &y, word workspace[])
Definition: mp_karat.cpp:253
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:40
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:118
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:147
bool is_positive() const
Definition: bigint.h:359
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:437
bool is_power_of_2(T arg)
Definition: bit_ops.h:25
const size_t MP_WORD_BITS
Definition: mp_core.h:22