Coverage Report

Created: 2020-06-30 13:58

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