Botan  2.10.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,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 && is_power_of_2(y.word_at(0)))
95  return (x >> (y.bits() - 1));
96 
97  BigInt q, r;
98  divide(x, y, q, r);
99  return q;
100  }
101 
102 /*
103 * Modulo Operator
104 */
105 BigInt operator%(const BigInt& n, const BigInt& mod)
106  {
107  if(mod.is_zero())
108  throw BigInt::DivideByZero();
109  if(mod.is_negative())
110  throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
111  if(n.is_positive() && mod.is_positive() && n < mod)
112  return n;
113 
114  BigInt q, r;
115  divide(n, mod, q, r);
116  return r;
117  }
118 
119 /*
120 * Modulo Operator
121 */
122 word operator%(const BigInt& n, word mod)
123  {
124  if(mod == 0)
125  throw BigInt::DivideByZero();
126 
127  if(mod == 1)
128  return 0;
129 
130  word remainder = 0;
131 
132  if(is_power_of_2(mod))
133  {
134  remainder = (n.word_at(0) & (mod - 1));
135  }
136  else
137  {
138  const size_t sw = n.sig_words();
139  for(size_t i = sw; i > 0; --i)
140  {
141  remainder = bigint_modop(remainder, n.word_at(i-1), mod);
142  }
143  }
144 
145  if(remainder && n.sign() == BigInt::Negative)
146  return mod - remainder;
147  return remainder;
148  }
149 
150 /*
151 * Left Shift Operator
152 */
153 BigInt operator<<(const BigInt& x, size_t shift)
154  {
155  const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
156  shift_bits = shift % BOTAN_MP_WORD_BITS;
157 
158  const size_t x_sw = x.sig_words();
159 
160  BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
161  bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
162  return y;
163  }
164 
165 /*
166 * Right Shift Operator
167 */
168 BigInt operator>>(const BigInt& x, size_t shift)
169  {
170  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
171  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
172  const size_t x_sw = x.sig_words();
173 
174  BigInt y(x.sign(), x_sw - shift_words);
175  bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
176 
177  if(x.is_negative() && y.is_zero())
178  y.set_sign(BigInt::Positive);
179 
180  return y;
181  }
182 
183 }
bool is_negative() const
Definition: bigint.h:530
int operator<<(int fd, Pipe &pipe)
Definition: fd_unix.cpp:17
void 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:467
size_t bits() const
Definition: bigint.cpp:281
Sign sign() const
Definition: bigint.h:542
bool is_zero() const
Definition: bigint.h:420
word * mutable_data()
Definition: bigint.h:617
word word_at(size_t n) const
Definition: bigint.h:511
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:92
const word * data() const
Definition: bigint.h:623
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:379
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
size_t size() const
Definition: bigint.h:583
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:589
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:450
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:45
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:40
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:105
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
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:566
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:291
bool is_positive() const
Definition: bigint.h:536
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:754