Coverage Report

Created: 2020-05-23 13:54

/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/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.52M
   {
20
2.52M
   const size_t x_sw = x.sig_words();
21
2.52M
22
2.52M
   BigInt z(x.sign(), std::max(x_sw, y_words) + 1);
23
2.52M
24
2.52M
   if(x.sign() == y_sign)
25
1.27M
      {
26
1.27M
      bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
27
1.27M
      }
28
1.25M
   else
29
1.25M
      {
30
1.25M
      const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
31
1.25M
32
1.25M
      //z.sign_fixup(relative_size, y_sign);
33
1.25M
      if(relative_size < 0)
34
161k
         z.set_sign(y_sign);
35
1.09M
      else if(relative_size == 0)
36
317
         z.set_sign(BigInt::Positive);
37
1.25M
      }
38
2.52M
39
2.52M
   return z;
40
2.52M
   }
41
42
/*
43
* Multiplication Operator
44
*/
45
BigInt operator*(const BigInt& x, const BigInt& y)
46
1.40M
   {
47
1.40M
   const size_t x_sw = x.sig_words();
48
1.40M
   const size_t y_sw = y.sig_words();
49
1.40M
50
1.40M
   BigInt z(BigInt::Positive, x.size() + y.size());
51
1.40M
52
1.40M
   if(x_sw == 1 && y_sw)
53
285k
      bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
54
1.12M
   else if(y_sw == 1 && x_sw)
55
242k
      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
56
881k
   else if(x_sw && y_sw)
57
818k
      {
58
818k
      secure_vector<word> workspace(z.size());
59
818k
60
818k
      bigint_mul(z.mutable_data(), z.size(),
61
818k
                 x.data(), x.size(), x_sw,
62
818k
                 y.data(), y.size(), y_sw,
63
818k
                 workspace.data(), workspace.size());
64
818k
      }
65
1.40M
66
1.40M
   z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
67
1.40M
68
1.40M
   return z;
69
1.40M
   }
70
71
/*
72
* Multiplication Operator
73
*/
74
BigInt operator*(const BigInt& x, word y)
75
5.30M
   {
76
5.30M
   const size_t x_sw = x.sig_words();
77
5.30M
78
5.30M
   BigInt z(BigInt::Positive, x_sw + 1);
79
5.30M
80
5.30M
   if(x_sw && y)
81
2.64M
      {
82
2.64M
      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y);
83
2.64M
      z.set_sign(x.sign());
84
2.64M
      }
85
5.30M
86
5.30M
   return z;
87
5.30M
   }
88
89
/*
90
* Division Operator
91
*/
92
BigInt operator/(const BigInt& x, const BigInt& y)
93
2.29M
   {
94
2.29M
   if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
95
2.29M
      return (x >> (y.bits() - 1));
96
453
97
453
   BigInt q, r;
98
453
   divide(x, y, q, r);
99
453
   return q;
100
453
   }
101
102
/*
103
* Modulo Operator
104
*/
105
BigInt operator%(const BigInt& n, const BigInt& mod)
106
2.34M
   {
107
2.34M
   if(mod.is_zero())
108
0
      throw BigInt::DivideByZero();
109
2.34M
   if(mod.is_negative())
110
0
      throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
111
2.34M
   if(n.is_positive() && mod.is_positive() && n < mod)
112
64.7k
      return n;
113
2.27M
114
2.27M
   BigInt q, r;
115
2.27M
   divide(n, mod, q, r);
116
2.27M
   return r;
117
2.27M
   }
118
119
/*
120
* Modulo Operator
121
*/
122
word operator%(const BigInt& n, word mod)
123
5.20M
   {
124
5.20M
   if(mod == 0)
125
0
      throw BigInt::DivideByZero();
126
5.20M
127
5.20M
   if(mod == 1)
128
0
      return 0;
129
5.20M
130
5.20M
   word remainder = 0;
131
5.20M
132
5.20M
   if(is_power_of_2(mod))
133
5.20M
      {
134
5.20M
      remainder = (n.word_at(0) & (mod - 1));
135
5.20M
      }
136
256
   else
137
256
      {
138
256
      const size_t sw = n.sig_words();
139
1.28k
      for(size_t i = sw; i > 0; --i)
140
1.02k
         {
141
1.02k
         remainder = bigint_modop(remainder, n.word_at(i-1), mod);
142
1.02k
         }
143
256
      }
144
5.20M
145
5.20M
   if(remainder && n.sign() == BigInt::Negative)
146
0
      return mod - remainder;
147
5.20M
   return remainder;
148
5.20M
   }
149
150
/*
151
* Left Shift Operator
152
*/
153
BigInt operator<<(const BigInt& x, size_t shift)
154
2.27M
   {
155
2.27M
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
156
2.27M
                shift_bits  = shift % BOTAN_MP_WORD_BITS;
157
2.27M
158
2.27M
   const size_t x_sw = x.sig_words();
159
2.27M
160
2.27M
   BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
161
2.27M
   bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
162
2.27M
   return y;
163
2.27M
   }
164
165
/*
166
* Right Shift Operator
167
*/
168
BigInt operator>>(const BigInt& x, size_t shift)
169
2.31M
   {
170
2.31M
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
171
2.31M
   const size_t shift_bits  = shift % BOTAN_MP_WORD_BITS;
172
2.31M
   const size_t x_sw = x.sig_words();
173
2.31M
174
2.31M
   BigInt y(x.sign(), x_sw - shift_words);
175
2.31M
   bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
176
2.31M
177
2.31M
   if(x.is_negative() && y.is_zero())
178
0
      y.set_sign(BigInt::Positive);
179
2.31M
180
2.31M
   return y;
181
2.31M
   }
182
183
}