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