Coverage Report

Created: 2021-02-21 07:20

/src/botan/src/lib/math/bigint/big_ops3.cpp
Line
Count
Source (jump to first uncovered line)
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
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
2.46M
   {
20
2.46M
   const size_t x_sw = x.sig_words();
21
22
2.46M
   BigInt z(x.sign(), std::max(x_sw, y_words) + 1);
23
24
2.46M
   if(x.sign() == y_sign)
25
1.16M
      {
26
1.16M
      bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
27
1.16M
      }
28
1.30M
   else
29
1.30M
      {
30
1.30M
      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
1.30M
      if(relative_size < 0)
34
80.7k
         z.set_sign(y_sign);
35
1.22M
      else if(relative_size == 0)
36
321
         z.set_sign(BigInt::Positive);
37
1.30M
      }
38
39
2.46M
   return z;
40
2.46M
   }
41
42
/*
43
* Multiplication Operator
44
*/
45
BigInt operator*(const BigInt& x, const BigInt& y)
46
1.13M
   {
47
1.13M
   const size_t x_sw = x.sig_words();
48
1.13M
   const size_t y_sw = y.sig_words();
49
50
1.13M
   BigInt z(BigInt::Positive, x.size() + y.size());
51
52
1.13M
   if(x_sw == 1 && y_sw)
53
195k
      bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
54
943k
   else if(y_sw == 1 && x_sw)
55
145k
      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
56
798k
   else if(x_sw && y_sw)
57
739k
      {
58
739k
      secure_vector<word> workspace(z.size());
59
60
739k
      bigint_mul(z.mutable_data(), z.size(),
61
739k
                 x.data(), x.size(), x_sw,
62
739k
                 y.data(), y.size(), y_sw,
63
739k
                 workspace.data(), workspace.size());
64
739k
      }
65
66
1.13M
   z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
67
68
1.13M
   return z;
69
1.13M
   }
70
71
/*
72
* Multiplication Operator
73
*/
74
BigInt operator*(const BigInt& x, word y)
75
5.08M
   {
76
5.08M
   const size_t x_sw = x.sig_words();
77
78
5.08M
   BigInt z(BigInt::Positive, x_sw + 1);
79
80
5.08M
   if(x_sw && y)
81
2.53M
      {
82
2.53M
      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y);
83
2.53M
      z.set_sign(x.sign());
84
2.53M
      }
85
86
5.08M
   return z;
87
5.08M
   }
88
89
/*
90
* Division Operator
91
*/
92
BigInt operator/(const BigInt& x, const BigInt& y)
93
360
   {
94
360
   if(y.sig_words() == 1)
95
177
      {
96
177
      return x / y.word_at(0);
97
177
      }
98
99
183
   BigInt q, r;
100
183
   vartime_divide(x, y, q, r);
101
183
   return q;
102
183
   }
103
104
/*
105
* Division Operator
106
*/
107
BigInt operator/(const BigInt& x, word y)
108
2.59M
   {
109
2.59M
   if(y == 0)
110
0
      throw Invalid_Argument("BigInt::operator/ divide by zero");
111
2.59M
   else if(y == 1)
112
0
      return x;
113
2.59M
   else if(y == 2)
114
2.59M
      return (x >> 1);
115
177
   else if(y <= 255)
116
4
      {
117
4
      BigInt q;
118
4
      uint8_t r;
119
4
      ct_divide_u8(x, static_cast<uint8_t>(y), q, r);
120
4
      return q;
121
4
      }
122
123
173
   BigInt q, r;
124
173
   vartime_divide(x, y, q, r);
125
173
   return q;
126
173
   }
127
128
/*
129
* Modulo Operator
130
*/
131
BigInt operator%(const BigInt& n, const BigInt& mod)
132
2.72M
   {
133
2.72M
   if(mod.is_zero())
134
0
      throw Invalid_Argument("BigInt::operator% divide by zero");
135
2.72M
   if(mod.is_negative())
136
0
      throw Invalid_Argument("BigInt::operator% modulus must be > 0");
137
2.72M
   if(n.is_positive() && mod.is_positive() && n < mod)
138
76.6k
      return n;
139
140
2.64M
   if(mod.sig_words() == 1)
141
455k
      {
142
455k
      return n % mod.word_at(0);
143
455k
      }
144
145
2.19M
   BigInt q, r;
146
2.19M
   vartime_divide(n, mod, q, r);
147
2.19M
   return r;
148
2.19M
   }
149
150
/*
151
* Modulo Operator
152
*/
153
word operator%(const BigInt& n, word mod)
154
6.37M
   {
155
6.37M
   if(mod == 0)
156
0
      throw Invalid_Argument("BigInt::operator% divide by zero");
157
158
6.37M
   if(mod == 1)
159
613
      return 0;
160
161
6.37M
   word remainder = 0;
162
163
6.37M
   if(is_power_of_2(mod))
164
5.92M
      {
165
5.92M
      remainder = (n.word_at(0) & (mod - 1));
166
5.92M
      }
167
454k
   else
168
454k
      {
169
454k
      const size_t sw = n.sig_words();
170
966k
      for(size_t i = sw; i > 0; --i)
171
511k
         {
172
511k
         remainder = bigint_modop(remainder, n.word_at(i-1), mod);
173
511k
         }
174
454k
      }
175
176
6.37M
   if(remainder && n.sign() == BigInt::Negative)
177
270
      return mod - remainder;
178
6.37M
   return remainder;
179
6.37M
   }
180
181
/*
182
* Left Shift Operator
183
*/
184
BigInt operator<<(const BigInt& x, size_t shift)
185
2.19M
   {
186
2.19M
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
187
2.19M
                shift_bits  = shift % BOTAN_MP_WORD_BITS;
188
189
2.19M
   const size_t x_sw = x.sig_words();
190
191
2.19M
   BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
192
2.19M
   bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
193
2.19M
   return y;
194
2.19M
   }
195
196
/*
197
* Right Shift Operator
198
*/
199
BigInt operator>>(const BigInt& x, size_t shift)
200
2.61M
   {
201
2.61M
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
202
2.61M
   const size_t shift_bits  = shift % BOTAN_MP_WORD_BITS;
203
2.61M
   const size_t x_sw = x.sig_words();
204
205
2.61M
   BigInt y(x.sign(), x_sw - shift_words);
206
2.61M
   bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
207
208
2.61M
   if(x.is_negative() && y.is_zero())
209
0
      y.set_sign(BigInt::Positive);
210
211
2.61M
   return y;
212
2.61M
   }
213
214
}