/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.42M | { |
20 | 2.42M | const size_t x_sw = x.sig_words(); |
21 | | |
22 | 2.42M | BigInt z(x.sign(), std::max(x_sw, y_words) + 1); |
23 | | |
24 | 2.42M | 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.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 | | |
32 | | //z.sign_fixup(relative_size, y_sign); |
33 | 1.25M | if(relative_size < 0) |
34 | 75.8k | z.set_sign(y_sign); |
35 | 1.17M | else if(relative_size == 0) |
36 | 325 | z.set_sign(BigInt::Positive); |
37 | 1.25M | } |
38 | | |
39 | 2.42M | return z; |
40 | 2.42M | } |
41 | | |
42 | | /* |
43 | | * Multiplication Operator |
44 | | */ |
45 | | BigInt operator*(const BigInt& x, const BigInt& y) |
46 | 1.16M | { |
47 | 1.16M | const size_t x_sw = x.sig_words(); |
48 | 1.16M | const size_t y_sw = y.sig_words(); |
49 | | |
50 | 1.16M | BigInt z(BigInt::Positive, x.size() + y.size()); |
51 | | |
52 | 1.16M | if(x_sw == 1 && y_sw) |
53 | 194k | bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0)); |
54 | 969k | else if(y_sw == 1 && x_sw) |
55 | 143k | bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0)); |
56 | 825k | else if(x_sw && y_sw) |
57 | 758k | { |
58 | 758k | secure_vector<word> workspace(z.size()); |
59 | | |
60 | 758k | bigint_mul(z.mutable_data(), z.size(), |
61 | 758k | x.data(), x.size(), x_sw, |
62 | 758k | y.data(), y.size(), y_sw, |
63 | 758k | workspace.data(), workspace.size()); |
64 | 758k | } |
65 | | |
66 | 1.16M | z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign()); |
67 | | |
68 | 1.16M | return z; |
69 | 1.16M | } |
70 | | |
71 | | /* |
72 | | * Multiplication Operator |
73 | | */ |
74 | | BigInt operator*(const BigInt& x, word y) |
75 | 4.79M | { |
76 | 4.79M | const size_t x_sw = x.sig_words(); |
77 | | |
78 | 4.79M | BigInt z(BigInt::Positive, x_sw + 1); |
79 | | |
80 | 4.79M | if(x_sw && y) |
81 | 2.39M | { |
82 | 2.39M | bigint_linmul3(z.mutable_data(), x.data(), x_sw, y); |
83 | 2.39M | z.set_sign(x.sign()); |
84 | 2.39M | } |
85 | | |
86 | 4.79M | return z; |
87 | 4.79M | } |
88 | | |
89 | | /* |
90 | | * Division Operator |
91 | | */ |
92 | | BigInt operator/(const BigInt& x, const BigInt& y) |
93 | 395 | { |
94 | 395 | if(y.sig_words() == 1) |
95 | 212 | { |
96 | 212 | return x / y.word_at(0); |
97 | 212 | } |
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.49M | { |
109 | 2.49M | if(y == 0) |
110 | 0 | throw Invalid_Argument("BigInt::operator/ divide by zero"); |
111 | 2.49M | else if(y == 1) |
112 | 0 | return x; |
113 | 2.49M | else if(y == 2) |
114 | 2.48M | return (x >> 1); |
115 | 212 | 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 | 208 | BigInt q, r; |
124 | 208 | vartime_divide(x, y, q, r); |
125 | 208 | return q; |
126 | 208 | } |
127 | | |
128 | | /* |
129 | | * Modulo Operator |
130 | | */ |
131 | | BigInt operator%(const BigInt& n, const BigInt& mod) |
132 | 2.55M | { |
133 | 2.55M | if(mod.is_zero()) |
134 | 0 | throw Invalid_Argument("BigInt::operator% divide by zero"); |
135 | 2.55M | if(mod.is_negative()) |
136 | 0 | throw Invalid_Argument("BigInt::operator% modulus must be > 0"); |
137 | 2.55M | if(n.is_positive() && mod.is_positive() && n < mod) |
138 | 74.7k | return n; |
139 | | |
140 | 2.47M | if(mod.sig_words() == 1) |
141 | 421k | { |
142 | 421k | return n % mod.word_at(0); |
143 | 421k | } |
144 | | |
145 | 2.05M | BigInt q, r; |
146 | 2.05M | vartime_divide(n, mod, q, r); |
147 | 2.05M | return r; |
148 | 2.05M | } |
149 | | |
150 | | /* |
151 | | * Modulo Operator |
152 | | */ |
153 | | word operator%(const BigInt& n, word mod) |
154 | 6.10M | { |
155 | 6.10M | if(mod == 0) |
156 | 0 | throw Invalid_Argument("BigInt::operator% divide by zero"); |
157 | | |
158 | 6.10M | if(mod == 1) |
159 | 8 | return 0; |
160 | | |
161 | 6.10M | word remainder = 0; |
162 | | |
163 | 6.10M | if(is_power_of_2(mod)) |
164 | 5.67M | { |
165 | 5.67M | remainder = (n.word_at(0) & (mod - 1)); |
166 | 5.67M | } |
167 | 421k | else |
168 | 421k | { |
169 | 421k | const size_t sw = n.sig_words(); |
170 | 900k | for(size_t i = sw; i > 0; --i) |
171 | 478k | { |
172 | 478k | remainder = bigint_modop(remainder, n.word_at(i-1), mod); |
173 | 478k | } |
174 | 421k | } |
175 | | |
176 | 6.10M | if(remainder && n.sign() == BigInt::Negative) |
177 | 274 | return mod - remainder; |
178 | 6.10M | return remainder; |
179 | 6.10M | } |
180 | | |
181 | | /* |
182 | | * Left Shift Operator |
183 | | */ |
184 | | BigInt operator<<(const BigInt& x, size_t shift) |
185 | 2.05M | { |
186 | 2.05M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS, |
187 | 2.05M | shift_bits = shift % BOTAN_MP_WORD_BITS; |
188 | | |
189 | 2.05M | const size_t x_sw = x.sig_words(); |
190 | | |
191 | 2.05M | BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0)); |
192 | 2.05M | bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); |
193 | 2.05M | return y; |
194 | 2.05M | } |
195 | | |
196 | | /* |
197 | | * Right Shift Operator |
198 | | */ |
199 | | BigInt operator>>(const BigInt& x, size_t shift) |
200 | 2.50M | { |
201 | 2.50M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
202 | 2.50M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
203 | 2.50M | const size_t x_sw = x.sig_words(); |
204 | | |
205 | 2.50M | BigInt y(x.sign(), x_sw - shift_words); |
206 | 2.50M | bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); |
207 | | |
208 | 2.50M | if(x.is_negative() && y.is_zero()) |
209 | 0 | y.set_sign(BigInt::Positive); |
210 | | |
211 | 2.50M | return y; |
212 | 2.50M | } |
213 | | |
214 | | } |