/src/botan/build/include/botan/internal/mp_core.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * MPI Algorithms |
3 | | * (C) 1999-2010,2018 Jack Lloyd |
4 | | * 2006 Luca Piccarreta |
5 | | * 2016 Matthias Gierlings |
6 | | * |
7 | | * Botan is released under the Simplified BSD License (see license.txt) |
8 | | */ |
9 | | |
10 | | #ifndef BOTAN_MP_CORE_OPS_H_ |
11 | | #define BOTAN_MP_CORE_OPS_H_ |
12 | | |
13 | | #include <botan/types.h> |
14 | | #include <botan/exceptn.h> |
15 | | #include <botan/mem_ops.h> |
16 | | #include <botan/internal/mp_asmi.h> |
17 | | #include <botan/internal/ct_utils.h> |
18 | | #include <algorithm> |
19 | | |
20 | | namespace Botan { |
21 | | |
22 | | const word MP_WORD_MAX = ~static_cast<word>(0); |
23 | | |
24 | | /* |
25 | | * If cond == 0, does nothing. |
26 | | * If cond > 0, swaps x[0:size] with y[0:size] |
27 | | * Runs in constant time |
28 | | */ |
29 | | inline void bigint_cnd_swap(word cnd, word x[], word y[], size_t size) |
30 | 207M | { |
31 | 207M | const auto mask = CT::Mask<word>::expand(cnd); |
32 | 207M | |
33 | 7.22G | for(size_t i = 0; i != size; ++i) |
34 | 7.01G | { |
35 | 7.01G | const word a = x[i]; |
36 | 7.01G | const word b = y[i]; |
37 | 7.01G | x[i] = mask.select(b, a); |
38 | 7.01G | y[i] = mask.select(a, b); |
39 | 7.01G | } |
40 | 207M | } |
41 | | |
42 | | inline word bigint_cnd_add(word cnd, word x[], word x_size, |
43 | | const word y[], size_t y_size) |
44 | 223M | { |
45 | 223M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
46 | 223M | |
47 | 223M | const auto mask = CT::Mask<word>::expand(cnd); |
48 | 223M | |
49 | 223M | word carry = 0; |
50 | 223M | |
51 | 223M | const size_t blocks = y_size - (y_size % 8); |
52 | 223M | word z[8] = { 0 }; |
53 | 223M | |
54 | 395M | for(size_t i = 0; i != blocks; i += 8) |
55 | 172M | { |
56 | 172M | carry = word8_add3(z, x + i, y + i, carry); |
57 | 172M | mask.select_n(x + i, z, x + i, 8); |
58 | 172M | } |
59 | 223M | |
60 | 986M | for(size_t i = blocks; i != y_size; ++i) |
61 | 762M | { |
62 | 762M | z[0] = word_add(x[i], y[i], &carry); |
63 | 762M | x[i] = mask.select(z[0], x[i]); |
64 | 762M | } |
65 | 223M | |
66 | 318M | for(size_t i = y_size; i != x_size; ++i) |
67 | 95.6M | { |
68 | 95.6M | z[0] = word_add(x[i], 0, &carry); |
69 | 95.6M | x[i] = mask.select(z[0], x[i]); |
70 | 95.6M | } |
71 | 223M | |
72 | 223M | return mask.if_set_return(carry); |
73 | 223M | } |
74 | | |
75 | | /* |
76 | | * If cond > 0 adds x[0:size] and y[0:size] and returns carry |
77 | | * Runs in constant time |
78 | | */ |
79 | | inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size) |
80 | 127M | { |
81 | 127M | return bigint_cnd_add(cnd, x, size, y, size); |
82 | 127M | } |
83 | | |
84 | | /* |
85 | | * If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow |
86 | | * Runs in constant time |
87 | | */ |
88 | | inline word bigint_cnd_sub(word cnd, |
89 | | word x[], size_t x_size, |
90 | | const word y[], size_t y_size) |
91 | 195M | { |
92 | 195M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
93 | 195M | |
94 | 195M | const auto mask = CT::Mask<word>::expand(cnd); |
95 | 195M | |
96 | 195M | word carry = 0; |
97 | 195M | |
98 | 195M | const size_t blocks = y_size - (y_size % 8); |
99 | 195M | word z[8] = { 0 }; |
100 | 195M | |
101 | 420M | for(size_t i = 0; i != blocks; i += 8) |
102 | 225M | { |
103 | 225M | carry = word8_sub3(z, x + i, y + i, carry); |
104 | 225M | mask.select_n(x + i, z, x + i, 8); |
105 | 225M | } |
106 | 195M | |
107 | 489M | for(size_t i = blocks; i != y_size; ++i) |
108 | 294M | { |
109 | 294M | z[0] = word_sub(x[i], y[i], &carry); |
110 | 294M | x[i] = mask.select(z[0], x[i]); |
111 | 294M | } |
112 | 195M | |
113 | 195M | for(size_t i = y_size; i != x_size; ++i) |
114 | 0 | { |
115 | 0 | z[0] = word_sub(x[i], 0, &carry); |
116 | 0 | x[i] = mask.select(z[0], x[i]); |
117 | 0 | } |
118 | 195M | |
119 | 195M | return mask.if_set_return(carry); |
120 | 195M | } |
121 | | |
122 | | /* |
123 | | * If cond > 0 adds x[0:size] and y[0:size] and returns carry |
124 | | * Runs in constant time |
125 | | */ |
126 | | inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size) |
127 | 195M | { |
128 | 195M | return bigint_cnd_sub(cnd, x, size, y, size); |
129 | 195M | } |
130 | | |
131 | | |
132 | | /* |
133 | | * Equivalent to |
134 | | * bigint_cnd_add( mask, x, y, size); |
135 | | * bigint_cnd_sub(~mask, x, y, size); |
136 | | * |
137 | | * Mask must be either 0 or all 1 bits |
138 | | */ |
139 | | inline void bigint_cnd_add_or_sub(CT::Mask<word> mask, word x[], const word y[], size_t size) |
140 | 2.11M | { |
141 | 2.11M | const size_t blocks = size - (size % 8); |
142 | 2.11M | |
143 | 2.11M | word carry = 0; |
144 | 2.11M | word borrow = 0; |
145 | 2.11M | |
146 | 2.11M | word t0[8] = { 0 }; |
147 | 2.11M | word t1[8] = { 0 }; |
148 | 2.11M | |
149 | 16.7M | for(size_t i = 0; i != blocks; i += 8) |
150 | 14.6M | { |
151 | 14.6M | carry = word8_add3(t0, x + i, y + i, carry); |
152 | 14.6M | borrow = word8_sub3(t1, x + i, y + i, borrow); |
153 | 14.6M | |
154 | 132M | for(size_t j = 0; j != 8; ++j) |
155 | 117M | x[i+j] = mask.select(t0[j], t1[j]); |
156 | 14.6M | } |
157 | 2.11M | |
158 | 2.12M | for(size_t i = blocks; i != size; ++i) |
159 | 15.2k | { |
160 | 15.2k | const word a = word_add(x[i], y[i], &carry); |
161 | 15.2k | const word s = word_sub(x[i], y[i], &borrow); |
162 | 15.2k | |
163 | 15.2k | x[i] = mask.select(a, s); |
164 | 15.2k | } |
165 | 2.11M | } |
166 | | |
167 | | /* |
168 | | * Equivalent to |
169 | | * bigint_cnd_add( mask, x, size, y, size); |
170 | | * bigint_cnd_sub(~mask, x, size, z, size); |
171 | | * |
172 | | * Mask must be either 0 or all 1 bits |
173 | | * |
174 | | * Returns the carry or borrow resp |
175 | | */ |
176 | | inline word bigint_cnd_addsub(CT::Mask<word> mask, word x[], |
177 | | const word y[], const word z[], |
178 | | size_t size) |
179 | 105M | { |
180 | 105M | const size_t blocks = size - (size % 8); |
181 | 105M | |
182 | 105M | word carry = 0; |
183 | 105M | word borrow = 0; |
184 | 105M | |
185 | 105M | word t0[8] = { 0 }; |
186 | 105M | word t1[8] = { 0 }; |
187 | 105M | |
188 | 157M | for(size_t i = 0; i != blocks; i += 8) |
189 | 51.9M | { |
190 | 51.9M | carry = word8_add3(t0, x + i, y + i, carry); |
191 | 51.9M | borrow = word8_sub3(t1, x + i, z + i, borrow); |
192 | 51.9M | |
193 | 467M | for(size_t j = 0; j != 8; ++j) |
194 | 415M | x[i+j] = mask.select(t0[j], t1[j]); |
195 | 51.9M | } |
196 | 105M | |
197 | 413M | for(size_t i = blocks; i != size; ++i) |
198 | 307M | { |
199 | 307M | t0[0] = word_add(x[i], y[i], &carry); |
200 | 307M | t1[0] = word_sub(x[i], z[i], &borrow); |
201 | 307M | x[i] = mask.select(t0[0], t1[0]); |
202 | 307M | } |
203 | 105M | |
204 | 105M | return mask.select(carry, borrow); |
205 | 105M | } |
206 | | |
207 | | /* |
208 | | * 2s complement absolute value |
209 | | * If cond > 0 sets x to ~x + 1 |
210 | | * Runs in constant time |
211 | | */ |
212 | | inline void bigint_cnd_abs(word cnd, word x[], size_t size) |
213 | 42.5M | { |
214 | 42.5M | const auto mask = CT::Mask<word>::expand(cnd); |
215 | 42.5M | |
216 | 42.5M | word carry = mask.if_set_return(1); |
217 | 593M | for(size_t i = 0; i != size; ++i) |
218 | 550M | { |
219 | 550M | const word z = word_add(~x[i], 0, &carry); |
220 | 550M | x[i] = mask.select(z, x[i]); |
221 | 550M | } |
222 | 42.5M | } |
223 | | |
224 | | /** |
225 | | * Two operand addition with carry out |
226 | | */ |
227 | | inline word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size) |
228 | 33.8M | { |
229 | 33.8M | word carry = 0; |
230 | 33.8M | |
231 | 33.8M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
232 | 33.8M | |
233 | 33.8M | const size_t blocks = y_size - (y_size % 8); |
234 | 33.8M | |
235 | 79.9M | for(size_t i = 0; i != blocks; i += 8) |
236 | 46.0M | carry = word8_add2(x + i, y + i, carry); |
237 | 33.8M | |
238 | 79.8M | for(size_t i = blocks; i != y_size; ++i) |
239 | 45.9M | x[i] = word_add(x[i], y[i], &carry); |
240 | 33.8M | |
241 | 828M | for(size_t i = y_size; i != x_size; ++i) |
242 | 794M | x[i] = word_add(x[i], 0, &carry); |
243 | 33.8M | |
244 | 33.8M | return carry; |
245 | 33.8M | } |
246 | | |
247 | | /** |
248 | | * Three operand addition with carry out |
249 | | */ |
250 | | inline word bigint_add3_nc(word z[], |
251 | | const word x[], size_t x_size, |
252 | | const word y[], size_t y_size) |
253 | 132M | { |
254 | 132M | if(x_size < y_size) |
255 | 270k | { return bigint_add3_nc(z, y, y_size, x, x_size); } |
256 | 131M | |
257 | 131M | word carry = 0; |
258 | 131M | |
259 | 131M | const size_t blocks = y_size - (y_size % 8); |
260 | 131M | |
261 | 289M | for(size_t i = 0; i != blocks; i += 8) |
262 | 157M | carry = word8_add3(z + i, x + i, y + i, carry); |
263 | 131M | |
264 | 281M | for(size_t i = blocks; i != y_size; ++i) |
265 | 150M | z[i] = word_add(x[i], y[i], &carry); |
266 | 131M | |
267 | 136M | for(size_t i = y_size; i != x_size; ++i) |
268 | 4.67M | z[i] = word_add(x[i], 0, &carry); |
269 | 131M | |
270 | 131M | return carry; |
271 | 131M | } |
272 | | |
273 | | /** |
274 | | * Two operand addition |
275 | | * @param x the first operand (and output) |
276 | | * @param x_size size of x |
277 | | * @param y the second operand |
278 | | * @param y_size size of y (must be >= x_size) |
279 | | */ |
280 | | inline void bigint_add2(word x[], size_t x_size, |
281 | | const word y[], size_t y_size) |
282 | 10.0M | { |
283 | 10.0M | x[x_size] += bigint_add2_nc(x, x_size, y, y_size); |
284 | 10.0M | } |
285 | | |
286 | | /** |
287 | | * Three operand addition |
288 | | */ |
289 | | inline void bigint_add3(word z[], |
290 | | const word x[], size_t x_size, |
291 | | const word y[], size_t y_size) |
292 | 2.13M | { |
293 | 2.13M | z[x_size > y_size ? x_size : y_size] += |
294 | 2.13M | bigint_add3_nc(z, x, x_size, y, y_size); |
295 | 2.13M | } |
296 | | |
297 | | /** |
298 | | * Two operand subtraction |
299 | | */ |
300 | | inline word bigint_sub2(word x[], size_t x_size, |
301 | | const word y[], size_t y_size) |
302 | 104M | { |
303 | 104M | word borrow = 0; |
304 | 104M | |
305 | 104M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
306 | 104M | |
307 | 104M | const size_t blocks = y_size - (y_size % 8); |
308 | 104M | |
309 | 162M | for(size_t i = 0; i != blocks; i += 8) |
310 | 57.7M | borrow = word8_sub2(x + i, y + i, borrow); |
311 | 104M | |
312 | 602M | for(size_t i = blocks; i != y_size; ++i) |
313 | 497M | x[i] = word_sub(x[i], y[i], &borrow); |
314 | 104M | |
315 | 310M | for(size_t i = y_size; i != x_size; ++i) |
316 | 206M | x[i] = word_sub(x[i], 0, &borrow); |
317 | 104M | |
318 | 104M | return borrow; |
319 | 104M | } |
320 | | |
321 | | /** |
322 | | * Two operand subtraction, x = y - x; assumes y >= x |
323 | | */ |
324 | | inline void bigint_sub2_rev(word x[], const word y[], size_t y_size) |
325 | 115k | { |
326 | 115k | word borrow = 0; |
327 | 115k | |
328 | 115k | const size_t blocks = y_size - (y_size % 8); |
329 | 115k | |
330 | 280k | for(size_t i = 0; i != blocks; i += 8) |
331 | 164k | borrow = word8_sub2_rev(x + i, y + i, borrow); |
332 | 115k | |
333 | 549k | for(size_t i = blocks; i != y_size; ++i) |
334 | 433k | x[i] = word_sub(y[i], x[i], &borrow); |
335 | 115k | |
336 | 115k | BOTAN_ASSERT(borrow == 0, "y must be greater than x"); |
337 | 115k | } |
338 | | |
339 | | /** |
340 | | * Three operand subtraction |
341 | | */ |
342 | | inline word bigint_sub3(word z[], |
343 | | const word x[], size_t x_size, |
344 | | const word y[], size_t y_size) |
345 | 440M | { |
346 | 440M | word borrow = 0; |
347 | 440M | |
348 | 440M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
349 | 440M | |
350 | 440M | const size_t blocks = y_size - (y_size % 8); |
351 | 440M | |
352 | 1.24G | for(size_t i = 0; i != blocks; i += 8) |
353 | 800M | borrow = word8_sub3(z + i, x + i, y + i, borrow); |
354 | 440M | |
355 | 1.45G | for(size_t i = blocks; i != y_size; ++i) |
356 | 1.01G | z[i] = word_sub(x[i], y[i], &borrow); |
357 | 440M | |
358 | 1.74G | for(size_t i = y_size; i != x_size; ++i) |
359 | 1.30G | z[i] = word_sub(x[i], 0, &borrow); |
360 | 440M | |
361 | 440M | return borrow; |
362 | 440M | } |
363 | | |
364 | | /** |
365 | | * Return abs(x-y), ie if x >= y, then compute z = x - y |
366 | | * Otherwise compute z = y - x |
367 | | * No borrow is possible since the result is always >= 0 |
368 | | * |
369 | | * Returns ~0 if x >= y or 0 if x < y |
370 | | * @param z output array of at least N words |
371 | | * @param x input array of N words |
372 | | * @param y input array of N words |
373 | | * @param N length of x and y |
374 | | * @param ws array of at least 2*N words |
375 | | */ |
376 | | inline CT::Mask<word> |
377 | | bigint_sub_abs(word z[], |
378 | | const word x[], const word y[], size_t N, |
379 | | word ws[]) |
380 | 10.0M | { |
381 | 10.0M | // Subtract in both direction then conditional copy out the result |
382 | 10.0M | |
383 | 10.0M | word* ws0 = ws; |
384 | 10.0M | word* ws1 = ws + N; |
385 | 10.0M | |
386 | 10.0M | word borrow0 = 0; |
387 | 10.0M | word borrow1 = 0; |
388 | 10.0M | |
389 | 10.0M | const size_t blocks = N - (N % 8); |
390 | 10.0M | |
391 | 33.6M | for(size_t i = 0; i != blocks; i += 8) |
392 | 23.6M | { |
393 | 23.6M | borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0); |
394 | 23.6M | borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1); |
395 | 23.6M | } |
396 | 10.0M | |
397 | 10.0M | for(size_t i = blocks; i != N; ++i) |
398 | 35.5k | { |
399 | 35.5k | ws0[i] = word_sub(x[i], y[i], &borrow0); |
400 | 35.5k | ws1[i] = word_sub(y[i], x[i], &borrow1); |
401 | 35.5k | } |
402 | 10.0M | |
403 | 10.0M | return CT::conditional_copy_mem(borrow0, z, ws1, ws0, N); |
404 | 10.0M | } |
405 | | |
406 | | /* |
407 | | * Shift Operations |
408 | | */ |
409 | | inline void bigint_shl1(word x[], size_t x_size, size_t x_words, |
410 | | size_t word_shift, size_t bit_shift) |
411 | 5.15M | { |
412 | 5.15M | copy_mem(x + word_shift, x, x_words); |
413 | 5.15M | clear_mem(x, word_shift); |
414 | 5.15M | |
415 | 5.15M | const auto carry_mask = CT::Mask<word>::expand(bit_shift); |
416 | 5.15M | const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); |
417 | 5.15M | |
418 | 5.15M | word carry = 0; |
419 | 27.7M | for(size_t i = word_shift; i != x_size; ++i) |
420 | 22.6M | { |
421 | 22.6M | const word w = x[i]; |
422 | 22.6M | x[i] = (w << bit_shift) | carry; |
423 | 22.6M | carry = carry_mask.if_set_return(w >> carry_shift); |
424 | 22.6M | } |
425 | 5.15M | } |
426 | | |
427 | | inline void bigint_shr1(word x[], size_t x_size, |
428 | | size_t word_shift, size_t bit_shift) |
429 | 110M | { |
430 | 110M | const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0; |
431 | 110M | |
432 | 110M | copy_mem(x, x + word_shift, top); |
433 | 110M | clear_mem(x + top, std::min(word_shift, x_size)); |
434 | 110M | |
435 | 110M | const auto carry_mask = CT::Mask<word>::expand(bit_shift); |
436 | 110M | const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); |
437 | 110M | |
438 | 110M | word carry = 0; |
439 | 110M | |
440 | 2.01G | for(size_t i = 0; i != top; ++i) |
441 | 1.90G | { |
442 | 1.90G | const word w = x[top - i - 1]; |
443 | 1.90G | x[top-i-1] = (w >> bit_shift) | carry; |
444 | 1.90G | carry = carry_mask.if_set_return(w << carry_shift); |
445 | 1.90G | } |
446 | 110M | } |
447 | | |
448 | | inline void bigint_shl2(word y[], const word x[], size_t x_size, |
449 | | size_t word_shift, size_t bit_shift) |
450 | 2.57M | { |
451 | 2.57M | copy_mem(y + word_shift, x, x_size); |
452 | 2.57M | |
453 | 2.57M | const auto carry_mask = CT::Mask<word>::expand(bit_shift); |
454 | 2.57M | const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); |
455 | 2.57M | |
456 | 2.57M | word carry = 0; |
457 | 14.9M | for(size_t i = word_shift; i != x_size + word_shift + 1; ++i) |
458 | 12.3M | { |
459 | 12.3M | const word w = y[i]; |
460 | 12.3M | y[i] = (w << bit_shift) | carry; |
461 | 12.3M | carry = carry_mask.if_set_return(w >> carry_shift); |
462 | 12.3M | } |
463 | 2.57M | } |
464 | | |
465 | | inline void bigint_shr2(word y[], const word x[], size_t x_size, |
466 | | size_t word_shift, size_t bit_shift) |
467 | 113M | { |
468 | 113M | const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift); |
469 | 113M | |
470 | 113M | copy_mem(y, x + word_shift, new_size); |
471 | 113M | |
472 | 113M | const auto carry_mask = CT::Mask<word>::expand(bit_shift); |
473 | 113M | const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); |
474 | 113M | |
475 | 113M | word carry = 0; |
476 | 1.22G | for(size_t i = new_size; i > 0; --i) |
477 | 1.11G | { |
478 | 1.11G | word w = y[i-1]; |
479 | 1.11G | y[i-1] = (w >> bit_shift) | carry; |
480 | 1.11G | carry = carry_mask.if_set_return(w << carry_shift); |
481 | 1.11G | } |
482 | 113M | } |
483 | | |
484 | | /* |
485 | | * Linear Multiply - returns the carry |
486 | | */ |
487 | | inline word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y) |
488 | 203M | { |
489 | 203M | const size_t blocks = x_size - (x_size % 8); |
490 | 203M | |
491 | 203M | word carry = 0; |
492 | 203M | |
493 | 1.06G | for(size_t i = 0; i != blocks; i += 8) |
494 | 859M | carry = word8_linmul2(x + i, y, carry); |
495 | 203M | |
496 | 378M | for(size_t i = blocks; i != x_size; ++i) |
497 | 175M | x[i] = word_madd2(x[i], y, &carry); |
498 | 203M | |
499 | 203M | return carry; |
500 | 203M | } |
501 | | |
502 | | inline void bigint_linmul3(word z[], const word x[], size_t x_size, word y) |
503 | 6.18M | { |
504 | 6.18M | const size_t blocks = x_size - (x_size % 8); |
505 | 6.18M | |
506 | 6.18M | word carry = 0; |
507 | 6.18M | |
508 | 41.2M | for(size_t i = 0; i != blocks; i += 8) |
509 | 35.0M | carry = word8_linmul3(z + i, x + i, y, carry); |
510 | 6.18M | |
511 | 24.2M | for(size_t i = blocks; i != x_size; ++i) |
512 | 18.0M | z[i] = word_madd2(x[i], y, &carry); |
513 | 6.18M | |
514 | 6.18M | z[x_size] = carry; |
515 | 6.18M | } |
516 | | |
517 | | /** |
518 | | * Compare x and y |
519 | | * Return -1 if x < y |
520 | | * Return 0 if x == y |
521 | | * Return 1 if x > y |
522 | | */ |
523 | | inline int32_t bigint_cmp(const word x[], size_t x_size, |
524 | | const word y[], size_t y_size) |
525 | 20.3M | { |
526 | 20.3M | static_assert(sizeof(word) >= sizeof(uint32_t), "Size assumption"); |
527 | 20.3M | |
528 | 20.3M | const word LT = static_cast<word>(-1); |
529 | 20.3M | const word EQ = 0; |
530 | 20.3M | const word GT = 1; |
531 | 20.3M | |
532 | 20.3M | const size_t common_elems = std::min(x_size, y_size); |
533 | 20.3M | |
534 | 20.3M | word result = EQ; // until found otherwise |
535 | 20.3M | |
536 | 463M | for(size_t i = 0; i != common_elems; i++) |
537 | 442M | { |
538 | 442M | const auto is_eq = CT::Mask<word>::is_equal(x[i], y[i]); |
539 | 442M | const auto is_lt = CT::Mask<word>::is_lt(x[i], y[i]); |
540 | 442M | |
541 | 442M | result = is_eq.select(result, is_lt.select(LT, GT)); |
542 | 442M | } |
543 | 20.3M | |
544 | 20.3M | if(x_size < y_size) |
545 | 7.12M | { |
546 | 7.12M | word mask = 0; |
547 | 50.7M | for(size_t i = x_size; i != y_size; i++) |
548 | 43.6M | mask |= y[i]; |
549 | 7.12M | |
550 | 7.12M | // If any bits were set in high part of y, then x < y |
551 | 7.12M | result = CT::Mask<word>::is_zero(mask).select(result, LT); |
552 | 7.12M | } |
553 | 13.2M | else if(y_size < x_size) |
554 | 322k | { |
555 | 322k | word mask = 0; |
556 | 3.43M | for(size_t i = y_size; i != x_size; i++) |
557 | 3.10M | mask |= x[i]; |
558 | 322k | |
559 | 322k | // If any bits were set in high part of x, then x > y |
560 | 322k | result = CT::Mask<word>::is_zero(mask).select(result, GT); |
561 | 322k | } |
562 | 20.3M | |
563 | 20.3M | CT::unpoison(result); |
564 | 20.3M | BOTAN_DEBUG_ASSERT(result == LT || result == GT || result == EQ); |
565 | 20.3M | return static_cast<int32_t>(result); |
566 | 20.3M | } |
567 | | |
568 | | /** |
569 | | * Compare x and y |
570 | | * Return ~0 if x[0:x_size] < y[0:y_size] or 0 otherwise |
571 | | * If lt_or_equal is true, returns ~0 also for x == y |
572 | | */ |
573 | | inline CT::Mask<word> |
574 | | bigint_ct_is_lt(const word x[], size_t x_size, |
575 | | const word y[], size_t y_size, |
576 | | bool lt_or_equal = false) |
577 | 117M | { |
578 | 117M | const size_t common_elems = std::min(x_size, y_size); |
579 | 117M | |
580 | 117M | auto is_lt = CT::Mask<word>::expand(lt_or_equal); |
581 | 117M | |
582 | 879M | for(size_t i = 0; i != common_elems; i++) |
583 | 762M | { |
584 | 762M | const auto eq = CT::Mask<word>::is_equal(x[i], y[i]); |
585 | 762M | const auto lt = CT::Mask<word>::is_lt(x[i], y[i]); |
586 | 762M | is_lt = eq.select_mask(is_lt, lt); |
587 | 762M | } |
588 | 117M | |
589 | 117M | if(x_size < y_size) |
590 | 154k | { |
591 | 154k | word mask = 0; |
592 | 1.62M | for(size_t i = x_size; i != y_size; i++) |
593 | 1.46M | mask |= y[i]; |
594 | 154k | // If any bits were set in high part of y, then is_lt should be forced true |
595 | 154k | is_lt |= CT::Mask<word>::expand(mask); |
596 | 154k | } |
597 | 116M | else if(y_size < x_size) |
598 | 279k | { |
599 | 279k | word mask = 0; |
600 | 1.40M | for(size_t i = y_size; i != x_size; i++) |
601 | 1.12M | mask |= x[i]; |
602 | 279k | |
603 | 279k | // If any bits were set in high part of x, then is_lt should be false |
604 | 279k | is_lt &= CT::Mask<word>::is_zero(mask); |
605 | 279k | } |
606 | 117M | |
607 | 117M | return is_lt; |
608 | 117M | } |
609 | | |
610 | | inline CT::Mask<word> |
611 | | bigint_ct_is_eq(const word x[], size_t x_size, |
612 | | const word y[], size_t y_size) |
613 | 285k | { |
614 | 285k | const size_t common_elems = std::min(x_size, y_size); |
615 | 285k | |
616 | 285k | word diff = 0; |
617 | 285k | |
618 | 3.49M | for(size_t i = 0; i != common_elems; i++) |
619 | 3.21M | { |
620 | 3.21M | diff |= (x[i] ^ y[i]); |
621 | 3.21M | } |
622 | 285k | |
623 | 285k | // If any bits were set in high part of x/y, then they are not equal |
624 | 285k | if(x_size < y_size) |
625 | 8.92k | { |
626 | 25.2k | for(size_t i = x_size; i != y_size; i++) |
627 | 16.3k | diff |= y[i]; |
628 | 8.92k | } |
629 | 276k | else if(y_size < x_size) |
630 | 2.50k | { |
631 | 11.5k | for(size_t i = y_size; i != x_size; i++) |
632 | 9.02k | diff |= x[i]; |
633 | 2.50k | } |
634 | 285k | |
635 | 285k | return CT::Mask<word>::is_zero(diff); |
636 | 285k | } |
637 | | |
638 | | /** |
639 | | * Set z to abs(x-y), ie if x >= y, then compute z = x - y |
640 | | * Otherwise compute z = y - x |
641 | | * No borrow is possible since the result is always >= 0 |
642 | | * |
643 | | * Return the relative size of x vs y (-1, 0, 1) |
644 | | * |
645 | | * @param z output array of max(x_size,y_size) words |
646 | | * @param x input param |
647 | | * @param x_size length of x |
648 | | * @param y input param |
649 | | * @param y_size length of y |
650 | | */ |
651 | | inline int32_t |
652 | | bigint_sub_abs(word z[], |
653 | | const word x[], size_t x_size, |
654 | | const word y[], size_t y_size) |
655 | 15.9M | { |
656 | 15.9M | const int32_t relative_size = bigint_cmp(x, x_size, y, y_size); |
657 | 15.9M | |
658 | 15.9M | // Swap if relative_size == -1 |
659 | 15.9M | const bool need_swap = relative_size < 0; |
660 | 15.9M | CT::conditional_swap_ptr(need_swap, x, y); |
661 | 15.9M | CT::conditional_swap(need_swap, x_size, y_size); |
662 | 15.9M | |
663 | 15.9M | /* |
664 | 15.9M | * We know at this point that x >= y so if y_size is larger than |
665 | 15.9M | * x_size, we are guaranteed they are just leading zeros which can |
666 | 15.9M | * be ignored |
667 | 15.9M | */ |
668 | 15.9M | y_size = std::min(x_size, y_size); |
669 | 15.9M | |
670 | 15.9M | bigint_sub3(z, x, x_size, y, y_size); |
671 | 15.9M | |
672 | 15.9M | return relative_size; |
673 | 15.9M | } |
674 | | |
675 | | /** |
676 | | * Set t to t-s modulo mod |
677 | | * |
678 | | * @param t first integer |
679 | | * @param s second integer |
680 | | * @param mod the modulus |
681 | | * @param mod_sw size of t, s, and mod |
682 | | * @param ws workspace of size mod_sw |
683 | | */ |
684 | | inline void |
685 | | bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[]) |
686 | 53.6M | { |
687 | 53.6M | // is t < s or not? |
688 | 53.6M | const auto is_lt = bigint_ct_is_lt(t, mod_sw, s, mod_sw); |
689 | 53.6M | |
690 | 53.6M | // ws = p - s |
691 | 53.6M | const word borrow = bigint_sub3(ws, mod, mod_sw, s, mod_sw); |
692 | 53.6M | |
693 | 53.6M | // Compute either (t - s) or (t + (p - s)) depending on mask |
694 | 53.6M | const word carry = bigint_cnd_addsub(is_lt, t, ws, s, mod_sw); |
695 | 53.6M | |
696 | 53.6M | BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0); |
697 | 53.6M | BOTAN_UNUSED(carry, borrow); |
698 | 53.6M | } |
699 | | |
700 | | template<size_t N> |
701 | | inline void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[]) |
702 | 51.8M | { |
703 | 51.8M | // is t < s or not? |
704 | 51.8M | const auto is_lt = bigint_ct_is_lt(t, N, s, N); |
705 | 51.8M | |
706 | 51.8M | // ws = p - s |
707 | 51.8M | const word borrow = bigint_sub3(ws, mod, N, s, N); |
708 | 51.8M | |
709 | 51.8M | // Compute either (t - s) or (t + (p - s)) depending on mask |
710 | 51.8M | const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N); |
711 | 51.8M | |
712 | 51.8M | BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0); |
713 | 51.8M | BOTAN_UNUSED(carry, borrow); |
714 | 51.8M | } void Botan::bigint_mod_sub_n<4ul>(unsigned long*, unsigned long const*, unsigned long const*, unsigned long*) Line | Count | Source | 702 | 27.3M | { | 703 | 27.3M | // is t < s or not? | 704 | 27.3M | const auto is_lt = bigint_ct_is_lt(t, N, s, N); | 705 | 27.3M | | 706 | 27.3M | // ws = p - s | 707 | 27.3M | const word borrow = bigint_sub3(ws, mod, N, s, N); | 708 | 27.3M | | 709 | 27.3M | // Compute either (t - s) or (t + (p - s)) depending on mask | 710 | 27.3M | const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N); | 711 | 27.3M | | 712 | 27.3M | BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0); | 713 | 27.3M | BOTAN_UNUSED(carry, borrow); | 714 | 27.3M | } |
void Botan::bigint_mod_sub_n<6ul>(unsigned long*, unsigned long const*, unsigned long const*, unsigned long*) Line | Count | Source | 702 | 24.5M | { | 703 | 24.5M | // is t < s or not? | 704 | 24.5M | const auto is_lt = bigint_ct_is_lt(t, N, s, N); | 705 | 24.5M | | 706 | 24.5M | // ws = p - s | 707 | 24.5M | const word borrow = bigint_sub3(ws, mod, N, s, N); | 708 | 24.5M | | 709 | 24.5M | // Compute either (t - s) or (t + (p - s)) depending on mask | 710 | 24.5M | const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N); | 711 | 24.5M | | 712 | 24.5M | BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0); | 713 | 24.5M | BOTAN_UNUSED(carry, borrow); | 714 | 24.5M | } |
|
715 | | |
716 | | /** |
717 | | * Compute ((n1<<bits) + n0) / d |
718 | | */ |
719 | | inline word bigint_divop(word n1, word n0, word d) |
720 | 2.99M | { |
721 | 2.99M | if(d == 0) |
722 | 0 | throw Invalid_Argument("bigint_divop divide by zero"); |
723 | 2.99M | |
724 | 2.99M | #if defined(BOTAN_HAS_MP_DWORD) |
725 | 2.99M | return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) / d; |
726 | | #else |
727 | | |
728 | | word high = n1 % d; |
729 | | word quotient = 0; |
730 | | |
731 | | for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i) |
732 | | { |
733 | | const word high_top_bit = high >> (BOTAN_MP_WORD_BITS-1); |
734 | | |
735 | | high <<= 1; |
736 | | high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1; |
737 | | quotient <<= 1; |
738 | | |
739 | | if(high_top_bit || high >= d) |
740 | | { |
741 | | high -= d; |
742 | | quotient |= 1; |
743 | | } |
744 | | } |
745 | | |
746 | | return quotient; |
747 | | #endif |
748 | | } |
749 | | |
750 | | /** |
751 | | * Compute ((n1<<bits) + n0) % d |
752 | | */ |
753 | | inline word bigint_modop(word n1, word n0, word d) |
754 | 1.02k | { |
755 | 1.02k | if(d == 0) |
756 | 0 | throw Invalid_Argument("bigint_modop divide by zero"); |
757 | 1.02k | |
758 | 1.02k | #if defined(BOTAN_HAS_MP_DWORD) |
759 | 1.02k | return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) % d; |
760 | | #else |
761 | | word z = bigint_divop(n1, n0, d); |
762 | | word dummy = 0; |
763 | | z = word_madd2(z, d, &dummy); |
764 | | return (n0-z); |
765 | | #endif |
766 | | } |
767 | | |
768 | | /* |
769 | | * Comba Multiplication / Squaring |
770 | | */ |
771 | | void bigint_comba_mul4(word z[8], const word x[4], const word y[4]); |
772 | | void bigint_comba_mul6(word z[12], const word x[6], const word y[6]); |
773 | | void bigint_comba_mul8(word z[16], const word x[8], const word y[8]); |
774 | | void bigint_comba_mul9(word z[18], const word x[9], const word y[9]); |
775 | | void bigint_comba_mul16(word z[32], const word x[16], const word y[16]); |
776 | | void bigint_comba_mul24(word z[48], const word x[24], const word y[24]); |
777 | | |
778 | | void bigint_comba_sqr4(word out[8], const word in[4]); |
779 | | void bigint_comba_sqr6(word out[12], const word in[6]); |
780 | | void bigint_comba_sqr8(word out[16], const word in[8]); |
781 | | void bigint_comba_sqr9(word out[18], const word in[9]); |
782 | | void bigint_comba_sqr16(word out[32], const word in[16]); |
783 | | void bigint_comba_sqr24(word out[48], const word in[24]); |
784 | | |
785 | | /** |
786 | | * Montgomery Reduction |
787 | | * @param z integer to reduce, of size exactly 2*(p_size+1). |
788 | | Output is in the first p_size+1 words, higher |
789 | | words are set to zero. |
790 | | * @param p modulus |
791 | | * @param p_size size of p |
792 | | * @param p_dash Montgomery value |
793 | | * @param workspace array of at least 2*(p_size+1) words |
794 | | * @param ws_size size of workspace in words |
795 | | */ |
796 | | void bigint_monty_redc(word z[], |
797 | | const word p[], size_t p_size, |
798 | | word p_dash, |
799 | | word workspace[], |
800 | | size_t ws_size); |
801 | | |
802 | | /* |
803 | | * High Level Multiplication/Squaring Interfaces |
804 | | */ |
805 | | |
806 | | void bigint_mul(word z[], size_t z_size, |
807 | | const word x[], size_t x_size, size_t x_sw, |
808 | | const word y[], size_t y_size, size_t y_sw, |
809 | | word workspace[], size_t ws_size); |
810 | | |
811 | | void bigint_sqr(word z[], size_t z_size, |
812 | | const word x[], size_t x_size, size_t x_sw, |
813 | | word workspace[], size_t ws_size); |
814 | | |
815 | | } |
816 | | |
817 | | #endif |