Coverage Report

Created: 2022-08-24 06:37

/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
3.84M
   {
20
3.84M
   const size_t x_sw = x.sig_words();
21
22
3.84M
   BigInt z = BigInt::with_capacity(std::max(x_sw, y_words) + 1);
23
24
3.84M
   if(x.sign() == y_sign)
25
3.06M
      {
26
3.06M
      bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
27
3.06M
      z.set_sign(x.sign());
28
3.06M
      }
29
786k
   else
30
786k
      {
31
786k
      const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
32
33
      //z.sign_fixup(relative_size, y_sign);
34
786k
      if(relative_size < 0)
35
605k
         z.set_sign(y_sign);
36
180k
      else if(relative_size == 0)
37
921
         z.set_sign(BigInt::Positive);
38
179k
      else
39
179k
         z.set_sign(x.sign());
40
786k
      }
41
42
3.84M
   return z;
43
3.84M
   }
44
45
/*
46
* Multiplication Operator
47
*/
48
BigInt operator*(const BigInt& x, const BigInt& y)
49
3.32M
   {
50
3.32M
   const size_t x_sw = x.sig_words();
51
3.32M
   const size_t y_sw = y.sig_words();
52
53
3.32M
   BigInt z = BigInt::with_capacity(x.size() + y.size());
54
55
3.32M
   if(x_sw == 1 && y_sw)
56
1.09M
      bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
57
2.22M
   else if(y_sw == 1 && x_sw)
58
1.01M
      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
59
1.21M
   else if(x_sw && y_sw)
60
1.15M
      {
61
1.15M
      secure_vector<word> workspace(z.size());
62
63
1.15M
      bigint_mul(z.mutable_data(), z.size(),
64
1.15M
                 x.data(), x.size(), x_sw,
65
1.15M
                 y.data(), y.size(), y_sw,
66
1.15M
                 workspace.data(), workspace.size());
67
1.15M
      }
68
69
3.32M
   z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
70
71
3.32M
   return z;
72
3.32M
   }
73
74
/*
75
* Multiplication Operator
76
*/
77
BigInt operator*(const BigInt& x, word y)
78
295k
   {
79
295k
   const size_t x_sw = x.sig_words();
80
81
295k
   BigInt z = BigInt::with_capacity(x_sw + 1);
82
83
295k
   if(x_sw && y)
84
148k
      {
85
148k
      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y);
86
148k
      z.set_sign(x.sign());
87
148k
      }
88
89
295k
   return z;
90
295k
   }
91
92
/*
93
* Division Operator
94
*/
95
BigInt operator/(const BigInt& x, const BigInt& y)
96
9.27k
   {
97
9.27k
   if(y.sig_words() == 1)
98
1.98k
      {
99
1.98k
      return x / y.word_at(0);
100
1.98k
      }
101
102
7.29k
   BigInt q, r;
103
7.29k
   vartime_divide(x, y, q, r);
104
7.29k
   return q;
105
9.27k
   }
106
107
/*
108
* Division Operator
109
*/
110
BigInt operator/(const BigInt& x, word y)
111
101k
   {
112
101k
   if(y == 0)
113
0
      throw Invalid_Argument("BigInt::operator/ divide by zero");
114
115
101k
   BigInt q;
116
101k
   word r;
117
101k
   ct_divide_word(x, y, q, r);
118
101k
   return q;
119
101k
   }
120
121
/*
122
* Modulo Operator
123
*/
124
BigInt operator%(const BigInt& n, const BigInt& mod)
125
109k
   {
126
109k
   if(mod.is_zero())
127
171
      throw Invalid_Argument("BigInt::operator% divide by zero");
128
108k
   if(mod.is_negative())
129
49
      throw Invalid_Argument("BigInt::operator% modulus must be > 0");
130
108k
   if(n.is_positive() && mod.is_positive() && n < mod)
131
11.7k
      return n;
132
133
97.0k
   if(mod.sig_words() == 1)
134
21.6k
      {
135
21.6k
      return BigInt::from_word(n % mod.word_at(0));
136
21.6k
      }
137
138
75.3k
   BigInt q, r;
139
75.3k
   vartime_divide(n, mod, q, r);
140
75.3k
   return r;
141
97.0k
   }
142
143
/*
144
* Modulo Operator
145
*/
146
word operator%(const BigInt& n, word mod)
147
635k
   {
148
635k
   if(mod == 0)
149
0
      throw Invalid_Argument("BigInt::operator% divide by zero");
150
151
635k
   if(mod == 1)
152
42
      return 0;
153
154
635k
   word remainder = 0;
155
156
635k
   if(is_power_of_2(mod))
157
224k
      {
158
224k
      remainder = (n.word_at(0) & (mod - 1));
159
224k
      }
160
411k
   else
161
411k
      {
162
411k
      const size_t sw = n.sig_words();
163
2.74M
      for(size_t i = sw; i > 0; --i)
164
2.33M
         {
165
2.33M
         remainder = bigint_modop(remainder, n.word_at(i-1), mod);
166
2.33M
         }
167
411k
      }
168
169
635k
   if(remainder && n.sign() == BigInt::Negative)
170
1.06k
      return mod - remainder;
171
634k
   return remainder;
172
635k
   }
173
174
/*
175
* Left Shift Operator
176
*/
177
BigInt operator<<(const BigInt& x, size_t shift)
178
83.2k
   {
179
83.2k
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
180
83.2k
                shift_bits  = shift % BOTAN_MP_WORD_BITS;
181
182
83.2k
   const size_t x_sw = x.sig_words();
183
184
83.2k
   BigInt y = BigInt::with_capacity(x_sw + shift_words + (shift_bits ? 1 : 0));
185
83.2k
   bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
186
83.2k
   y.set_sign(x.sign());
187
83.2k
   return y;
188
83.2k
   }
189
190
/*
191
* Right Shift Operator
192
*/
193
BigInt operator>>(const BigInt& x, size_t shift)
194
93.2k
   {
195
93.2k
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
196
93.2k
   const size_t shift_bits  = shift % BOTAN_MP_WORD_BITS;
197
93.2k
   const size_t x_sw = x.sig_words();
198
199
93.2k
   if(shift_words >= x_sw)
200
759
      return BigInt::zero();
201
202
92.4k
   BigInt y = BigInt::with_capacity(x_sw - shift_words);
203
92.4k
   bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
204
205
92.4k
   if(x.is_negative() && y.is_zero())
206
5
      y.set_sign(BigInt::Positive);
207
92.4k
   else
208
92.4k
      y.set_sign(x.sign());
209
210
92.4k
   return y;
211
93.2k
   }
212
213
}