/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 | 223M | { |
31 | 223M | const auto mask = CT::Mask<word>::expand(cnd); |
32 | | |
33 | 8.87G | for(size_t i = 0; i != size; ++i) |
34 | 8.64G | { |
35 | 8.64G | const word a = x[i]; |
36 | 8.64G | const word b = y[i]; |
37 | 8.64G | x[i] = mask.select(b, a); |
38 | 8.64G | y[i] = mask.select(a, b); |
39 | 8.64G | } |
40 | 223M | } |
41 | | |
42 | | inline word bigint_cnd_add(word cnd, word x[], word x_size, |
43 | | const word y[], size_t y_size) |
44 | 234M | { |
45 | 234M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
46 | | |
47 | 234M | const auto mask = CT::Mask<word>::expand(cnd); |
48 | | |
49 | 234M | word carry = 0; |
50 | | |
51 | 234M | const size_t blocks = y_size - (y_size % 8); |
52 | 234M | word z[8] = { 0 }; |
53 | | |
54 | 414M | for(size_t i = 0; i != blocks; i += 8) |
55 | 179M | { |
56 | 179M | carry = word8_add3(z, x + i, y + i, carry); |
57 | 179M | mask.select_n(x + i, z, x + i, 8); |
58 | 179M | } |
59 | | |
60 | 1.05G | for(size_t i = blocks; i != y_size; ++i) |
61 | 817M | { |
62 | 817M | z[0] = word_add(x[i], y[i], &carry); |
63 | 817M | x[i] = mask.select(z[0], x[i]); |
64 | 817M | } |
65 | | |
66 | 340M | for(size_t i = y_size; i != x_size; ++i) |
67 | 106M | { |
68 | 106M | z[0] = word_add(x[i], 0, &carry); |
69 | 106M | x[i] = mask.select(z[0], x[i]); |
70 | 106M | } |
71 | | |
72 | 234M | return mask.if_set_return(carry); |
73 | 234M | } |
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 | 134M | { |
81 | 134M | return bigint_cnd_add(cnd, x, size, y, size); |
82 | 134M | } |
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 | 253M | { |
92 | 253M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
93 | | |
94 | 253M | const auto mask = CT::Mask<word>::expand(cnd); |
95 | | |
96 | 253M | word carry = 0; |
97 | | |
98 | 253M | const size_t blocks = y_size - (y_size % 8); |
99 | 253M | word z[8] = { 0 }; |
100 | | |
101 | 536M | for(size_t i = 0; i != blocks; i += 8) |
102 | 282M | { |
103 | 282M | carry = word8_sub3(z, x + i, y + i, carry); |
104 | 282M | mask.select_n(x + i, z, x + i, 8); |
105 | 282M | } |
106 | | |
107 | 622M | for(size_t i = blocks; i != y_size; ++i) |
108 | 369M | { |
109 | 369M | z[0] = word_sub(x[i], y[i], &carry); |
110 | 369M | x[i] = mask.select(z[0], x[i]); |
111 | 369M | } |
112 | | |
113 | 253M | 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 | | |
119 | 253M | return mask.if_set_return(carry); |
120 | 253M | } |
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 | 253M | { |
128 | 253M | return bigint_cnd_sub(cnd, x, size, y, size); |
129 | 253M | } |
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 | 4.24M | { |
141 | 4.24M | const size_t blocks = size - (size % 8); |
142 | | |
143 | 4.24M | word carry = 0; |
144 | 4.24M | word borrow = 0; |
145 | | |
146 | 4.24M | word t0[8] = { 0 }; |
147 | 4.24M | word t1[8] = { 0 }; |
148 | | |
149 | 33.5M | for(size_t i = 0; i != blocks; i += 8) |
150 | 29.2M | { |
151 | 29.2M | carry = word8_add3(t0, x + i, y + i, carry); |
152 | 29.2M | borrow = word8_sub3(t1, x + i, y + i, borrow); |
153 | | |
154 | 263M | for(size_t j = 0; j != 8; ++j) |
155 | 234M | x[i+j] = mask.select(t0[j], t1[j]); |
156 | 29.2M | } |
157 | | |
158 | 4.26M | for(size_t i = blocks; i != size; ++i) |
159 | 18.6k | { |
160 | 18.6k | const word a = word_add(x[i], y[i], &carry); |
161 | 18.6k | const word s = word_sub(x[i], y[i], &borrow); |
162 | | |
163 | 18.6k | x[i] = mask.select(a, s); |
164 | 18.6k | } |
165 | 4.24M | } |
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 | 139M | { |
180 | 139M | const size_t blocks = size - (size % 8); |
181 | | |
182 | 139M | word carry = 0; |
183 | 139M | word borrow = 0; |
184 | | |
185 | 139M | word t0[8] = { 0 }; |
186 | 139M | word t1[8] = { 0 }; |
187 | | |
188 | 219M | for(size_t i = 0; i != blocks; i += 8) |
189 | 79.8M | { |
190 | 79.8M | carry = word8_add3(t0, x + i, y + i, carry); |
191 | 79.8M | borrow = word8_sub3(t1, x + i, z + i, borrow); |
192 | | |
193 | 718M | for(size_t j = 0; j != 8; ++j) |
194 | 638M | x[i+j] = mask.select(t0[j], t1[j]); |
195 | 79.8M | } |
196 | | |
197 | 510M | for(size_t i = blocks; i != size; ++i) |
198 | 370M | { |
199 | 370M | t0[0] = word_add(x[i], y[i], &carry); |
200 | 370M | t1[0] = word_sub(x[i], z[i], &borrow); |
201 | 370M | x[i] = mask.select(t0[0], t1[0]); |
202 | 370M | } |
203 | | |
204 | 139M | return mask.select(carry, borrow); |
205 | 139M | } |
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 | 44.7M | { |
214 | 44.7M | const auto mask = CT::Mask<word>::expand(cnd); |
215 | | |
216 | 44.7M | word carry = mask.if_set_return(1); |
217 | 620M | for(size_t i = 0; i != size; ++i) |
218 | 576M | { |
219 | 576M | const word z = word_add(~x[i], 0, &carry); |
220 | 576M | x[i] = mask.select(z, x[i]); |
221 | 576M | } |
222 | 44.7M | } |
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 | 66.8M | { |
229 | 66.8M | word carry = 0; |
230 | | |
231 | 66.8M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
232 | | |
233 | 66.8M | const size_t blocks = y_size - (y_size % 8); |
234 | | |
235 | 165M | for(size_t i = 0; i != blocks; i += 8) |
236 | 98.8M | carry = word8_add2(x + i, y + i, carry); |
237 | | |
238 | 140M | for(size_t i = blocks; i != y_size; ++i) |
239 | 73.3M | x[i] = word_add(x[i], y[i], &carry); |
240 | | |
241 | 1.21G | for(size_t i = y_size; i != x_size; ++i) |
242 | 1.14G | x[i] = word_add(x[i], 0, &carry); |
243 | | |
244 | 66.8M | return carry; |
245 | 66.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 | 199M | { |
254 | 199M | if(x_size < y_size) |
255 | 163k | { return bigint_add3_nc(z, y, y_size, x, x_size); } |
256 | | |
257 | 198M | word carry = 0; |
258 | | |
259 | 198M | const size_t blocks = y_size - (y_size % 8); |
260 | | |
261 | 458M | for(size_t i = 0; i != blocks; i += 8) |
262 | 260M | carry = word8_add3(z + i, x + i, y + i, carry); |
263 | | |
264 | 407M | for(size_t i = blocks; i != y_size; ++i) |
265 | 208M | z[i] = word_add(x[i], y[i], &carry); |
266 | | |
267 | 199M | for(size_t i = y_size; i != x_size; ++i) |
268 | 638k | z[i] = word_add(x[i], 0, &carry); |
269 | | |
270 | 198M | return carry; |
271 | 198M | } |
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 | 11.4M | { |
283 | 11.4M | x[x_size] += bigint_add2_nc(x, x_size, y, y_size); |
284 | 11.4M | } |
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 | 1.57M | { |
293 | 1.52M | z[x_size > y_size ? x_size : y_size] += |
294 | 1.57M | bigint_add3_nc(z, x, x_size, y, y_size); |
295 | 1.57M | } |
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 | 116M | { |
303 | 116M | word borrow = 0; |
304 | | |
305 | 116M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
306 | | |
307 | 116M | const size_t blocks = y_size - (y_size % 8); |
308 | | |
309 | 213M | for(size_t i = 0; i != blocks; i += 8) |
310 | 96.7M | borrow = word8_sub2(x + i, y + i, borrow); |
311 | | |
312 | 637M | for(size_t i = blocks; i != y_size; ++i) |
313 | 520M | x[i] = word_sub(x[i], y[i], &borrow); |
314 | | |
315 | 480M | for(size_t i = y_size; i != x_size; ++i) |
316 | 364M | x[i] = word_sub(x[i], 0, &borrow); |
317 | | |
318 | 116M | return borrow; |
319 | 116M | } |
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 | 712k | { |
326 | 712k | word borrow = 0; |
327 | | |
328 | 712k | const size_t blocks = y_size - (y_size % 8); |
329 | | |
330 | 3.28M | for(size_t i = 0; i != blocks; i += 8) |
331 | 2.57M | borrow = word8_sub2_rev(x + i, y + i, borrow); |
332 | | |
333 | 3.17M | for(size_t i = blocks; i != y_size; ++i) |
334 | 2.45M | x[i] = word_sub(y[i], x[i], &borrow); |
335 | | |
336 | 712k | BOTAN_ASSERT(borrow == 0, "y must be greater than x"); |
337 | 712k | } |
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 | 539M | { |
346 | 539M | word borrow = 0; |
347 | | |
348 | 539M | BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); |
349 | | |
350 | 539M | const size_t blocks = y_size - (y_size % 8); |
351 | | |
352 | 1.61G | for(size_t i = 0; i != blocks; i += 8) |
353 | 1.07G | borrow = word8_sub3(z + i, x + i, y + i, borrow); |
354 | | |
355 | 1.73G | for(size_t i = blocks; i != y_size; ++i) |
356 | 1.19G | z[i] = word_sub(x[i], y[i], &borrow); |
357 | | |
358 | 1.98G | for(size_t i = y_size; i != x_size; ++i) |
359 | 1.44G | z[i] = word_sub(x[i], 0, &borrow); |
360 | | |
361 | 539M | return borrow; |
362 | 539M | } |
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 | 22.7M | { |
381 | | // Subtract in both direction then conditional copy out the result |
382 | | |
383 | 22.7M | word* ws0 = ws; |
384 | 22.7M | word* ws1 = ws + N; |
385 | | |
386 | 22.7M | word borrow0 = 0; |
387 | 22.7M | word borrow1 = 0; |
388 | | |
389 | 22.7M | const size_t blocks = N - (N % 8); |
390 | | |
391 | 74.9M | for(size_t i = 0; i != blocks; i += 8) |
392 | 52.2M | { |
393 | 52.2M | borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0); |
394 | 52.2M | borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1); |
395 | 52.2M | } |
396 | | |
397 | 22.7M | for(size_t i = blocks; i != N; ++i) |
398 | 38.1k | { |
399 | 38.1k | ws0[i] = word_sub(x[i], y[i], &borrow0); |
400 | 38.1k | ws1[i] = word_sub(y[i], x[i], &borrow1); |
401 | 38.1k | } |
402 | | |
403 | 22.7M | return CT::conditional_copy_mem(borrow0, z, ws1, ws0, N); |
404 | 22.7M | } |
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 | 4.61M | { |
412 | 4.61M | copy_mem(x + word_shift, x, x_words); |
413 | 4.61M | clear_mem(x, word_shift); |
414 | | |
415 | 4.61M | const auto carry_mask = CT::Mask<word>::expand(bit_shift); |
416 | 4.61M | const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); |
417 | | |
418 | 4.61M | word carry = 0; |
419 | 27.8M | for(size_t i = word_shift; i != x_size; ++i) |
420 | 23.2M | { |
421 | 23.2M | const word w = x[i]; |
422 | 23.2M | x[i] = (w << bit_shift) | carry; |
423 | 23.2M | carry = carry_mask.if_set_return(w >> carry_shift); |
424 | 23.2M | } |
425 | 4.61M | } |
426 | | |
427 | | inline void bigint_shr1(word x[], size_t x_size, |
428 | | size_t word_shift, size_t bit_shift) |
429 | 118M | { |
430 | 117M | const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0; |
431 | | |
432 | 118M | if(top > 0) |
433 | 117M | copy_mem(x, x + word_shift, top); |
434 | 118M | clear_mem(x + top, std::min(word_shift, x_size)); |
435 | | |
436 | 118M | const auto carry_mask = CT::Mask<word>::expand(bit_shift); |
437 | 118M | const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); |
438 | | |
439 | 118M | word carry = 0; |
440 | | |
441 | 2.18G | for(size_t i = 0; i != top; ++i) |
442 | 2.06G | { |
443 | 2.06G | const word w = x[top - i - 1]; |
444 | 2.06G | x[top-i-1] = (w >> bit_shift) | carry; |
445 | 2.06G | carry = carry_mask.if_set_return(w << carry_shift); |
446 | 2.06G | } |
447 | 118M | } |
448 | | |
449 | | inline void bigint_shl2(word y[], const word x[], size_t x_size, |
450 | | size_t word_shift, size_t bit_shift) |
451 | 2.31M | { |
452 | 2.31M | copy_mem(y + word_shift, x, x_size); |
453 | | |
454 | 2.31M | const auto carry_mask = CT::Mask<word>::expand(bit_shift); |
455 | 2.31M | const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); |
456 | | |
457 | 2.31M | word carry = 0; |
458 | 14.9M | for(size_t i = word_shift; i != x_size + word_shift + 1; ++i) |
459 | 12.5M | { |
460 | 12.5M | const word w = y[i]; |
461 | 12.5M | y[i] = (w << bit_shift) | carry; |
462 | 12.5M | carry = carry_mask.if_set_return(w >> carry_shift); |
463 | 12.5M | } |
464 | 2.31M | } |
465 | | |
466 | | inline void bigint_shr2(word y[], const word x[], size_t x_size, |
467 | | size_t word_shift, size_t bit_shift) |
468 | 167M | { |
469 | 167M | const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift); |
470 | | |
471 | 167M | if(new_size > 0) |
472 | 167M | copy_mem(y, x + word_shift, new_size); |
473 | | |
474 | 167M | const auto carry_mask = CT::Mask<word>::expand(bit_shift); |
475 | 167M | const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); |
476 | | |
477 | 167M | word carry = 0; |
478 | 1.82G | for(size_t i = new_size; i > 0; --i) |
479 | 1.65G | { |
480 | 1.65G | word w = y[i-1]; |
481 | 1.65G | y[i-1] = (w >> bit_shift) | carry; |
482 | 1.65G | carry = carry_mask.if_set_return(w << carry_shift); |
483 | 1.65G | } |
484 | 167M | } |
485 | | |
486 | | /* |
487 | | * Linear Multiply - returns the carry |
488 | | */ |
489 | | [[nodiscard]] inline word bigint_linmul2(word x[], size_t x_size, word y) |
490 | 229M | { |
491 | 229M | const size_t blocks = x_size - (x_size % 8); |
492 | | |
493 | 229M | word carry = 0; |
494 | | |
495 | 1.34G | for(size_t i = 0; i != blocks; i += 8) |
496 | 1.11G | carry = word8_linmul2(x + i, y, carry); |
497 | | |
498 | 361M | for(size_t i = blocks; i != x_size; ++i) |
499 | 132M | x[i] = word_madd2(x[i], y, &carry); |
500 | | |
501 | 229M | return carry; |
502 | 229M | } |
503 | | |
504 | | inline void bigint_linmul3(word z[], const word x[], size_t x_size, word y) |
505 | 6.17M | { |
506 | 6.17M | const size_t blocks = x_size - (x_size % 8); |
507 | | |
508 | 6.17M | word carry = 0; |
509 | | |
510 | 42.0M | for(size_t i = 0; i != blocks; i += 8) |
511 | 35.8M | carry = word8_linmul3(z + i, x + i, y, carry); |
512 | | |
513 | 25.1M | for(size_t i = blocks; i != x_size; ++i) |
514 | 19.0M | z[i] = word_madd2(x[i], y, &carry); |
515 | | |
516 | 6.17M | z[x_size] = carry; |
517 | 6.17M | } |
518 | | |
519 | | /** |
520 | | * Compare x and y |
521 | | * Return -1 if x < y |
522 | | * Return 0 if x == y |
523 | | * Return 1 if x > y |
524 | | */ |
525 | | inline int32_t bigint_cmp(const word x[], size_t x_size, |
526 | | const word y[], size_t y_size) |
527 | 22.3M | { |
528 | 22.3M | static_assert(sizeof(word) >= sizeof(uint32_t), "Size assumption"); |
529 | | |
530 | 22.3M | const word LT = static_cast<word>(-1); |
531 | 22.3M | const word EQ = 0; |
532 | 22.3M | const word GT = 1; |
533 | | |
534 | 22.3M | const size_t common_elems = std::min(x_size, y_size); |
535 | | |
536 | 22.3M | word result = EQ; // until found otherwise |
537 | | |
538 | 509M | for(size_t i = 0; i != common_elems; i++) |
539 | 486M | { |
540 | 486M | const auto is_eq = CT::Mask<word>::is_equal(x[i], y[i]); |
541 | 486M | const auto is_lt = CT::Mask<word>::is_lt(x[i], y[i]); |
542 | | |
543 | 486M | result = is_eq.select(result, is_lt.select(LT, GT)); |
544 | 486M | } |
545 | | |
546 | 22.3M | if(x_size < y_size) |
547 | 7.95M | { |
548 | 7.95M | word mask = 0; |
549 | 57.0M | for(size_t i = x_size; i != y_size; i++) |
550 | 49.0M | mask |= y[i]; |
551 | | |
552 | | // If any bits were set in high part of y, then x < y |
553 | 7.95M | result = CT::Mask<word>::is_zero(mask).select(result, LT); |
554 | 7.95M | } |
555 | 14.4M | else if(y_size < x_size) |
556 | 357k | { |
557 | 357k | word mask = 0; |
558 | 5.62M | for(size_t i = y_size; i != x_size; i++) |
559 | 5.26M | mask |= x[i]; |
560 | | |
561 | | // If any bits were set in high part of x, then x > y |
562 | 357k | result = CT::Mask<word>::is_zero(mask).select(result, GT); |
563 | 357k | } |
564 | | |
565 | 22.3M | CT::unpoison(result); |
566 | 22.3M | BOTAN_DEBUG_ASSERT(result == LT || result == GT || result == EQ); |
567 | 22.3M | return static_cast<int32_t>(result); |
568 | 22.3M | } |
569 | | |
570 | | /** |
571 | | * Compare x and y |
572 | | * Return ~0 if x[0:x_size] < y[0:y_size] or 0 otherwise |
573 | | * If lt_or_equal is true, returns ~0 also for x == y |
574 | | */ |
575 | | inline CT::Mask<word> |
576 | | bigint_ct_is_lt(const word x[], size_t x_size, |
577 | | const word y[], size_t y_size, |
578 | | bool lt_or_equal = false) |
579 | 151M | { |
580 | 151M | const size_t common_elems = std::min(x_size, y_size); |
581 | | |
582 | 151M | auto is_lt = CT::Mask<word>::expand(lt_or_equal); |
583 | | |
584 | 1.20G | for(size_t i = 0; i != common_elems; i++) |
585 | 1.04G | { |
586 | 1.04G | const auto eq = CT::Mask<word>::is_equal(x[i], y[i]); |
587 | 1.04G | const auto lt = CT::Mask<word>::is_lt(x[i], y[i]); |
588 | 1.04G | is_lt = eq.select_mask(is_lt, lt); |
589 | 1.04G | } |
590 | | |
591 | 151M | if(x_size < y_size) |
592 | 174k | { |
593 | 174k | word mask = 0; |
594 | 1.92M | for(size_t i = x_size; i != y_size; i++) |
595 | 1.74M | mask |= y[i]; |
596 | | // If any bits were set in high part of y, then is_lt should be forced true |
597 | 174k | is_lt |= CT::Mask<word>::expand(mask); |
598 | 174k | } |
599 | 151M | else if(y_size < x_size) |
600 | 315k | { |
601 | 315k | word mask = 0; |
602 | 1.82M | for(size_t i = y_size; i != x_size; i++) |
603 | 1.51M | mask |= x[i]; |
604 | | |
605 | | // If any bits were set in high part of x, then is_lt should be false |
606 | 315k | is_lt &= CT::Mask<word>::is_zero(mask); |
607 | 315k | } |
608 | | |
609 | 151M | return is_lt; |
610 | 151M | } |
611 | | |
612 | | inline CT::Mask<word> |
613 | | bigint_ct_is_eq(const word x[], size_t x_size, |
614 | | const word y[], size_t y_size) |
615 | 418k | { |
616 | 418k | const size_t common_elems = std::min(x_size, y_size); |
617 | | |
618 | 418k | word diff = 0; |
619 | | |
620 | 7.58M | for(size_t i = 0; i != common_elems; i++) |
621 | 7.17M | { |
622 | 7.17M | diff |= (x[i] ^ y[i]); |
623 | 7.17M | } |
624 | | |
625 | | // If any bits were set in high part of x/y, then they are not equal |
626 | 418k | if(x_size < y_size) |
627 | 12.5k | { |
628 | 32.8k | for(size_t i = x_size; i != y_size; i++) |
629 | 20.2k | diff |= y[i]; |
630 | 12.5k | } |
631 | 406k | else if(y_size < x_size) |
632 | 2.67k | { |
633 | 12.3k | for(size_t i = y_size; i != x_size; i++) |
634 | 9.71k | diff |= x[i]; |
635 | 2.67k | } |
636 | | |
637 | 418k | return CT::Mask<word>::is_zero(diff); |
638 | 418k | } |
639 | | |
640 | | /** |
641 | | * Set z to abs(x-y), ie if x >= y, then compute z = x - y |
642 | | * Otherwise compute z = y - x |
643 | | * No borrow is possible since the result is always >= 0 |
644 | | * |
645 | | * Return the relative size of x vs y (-1, 0, 1) |
646 | | * |
647 | | * @param z output array of max(x_size,y_size) words |
648 | | * @param x input param |
649 | | * @param x_size length of x |
650 | | * @param y input param |
651 | | * @param y_size length of y |
652 | | */ |
653 | | inline int32_t |
654 | | bigint_sub_abs(word z[], |
655 | | const word x[], size_t x_size, |
656 | | const word y[], size_t y_size) |
657 | 16.9M | { |
658 | 16.9M | const int32_t relative_size = bigint_cmp(x, x_size, y, y_size); |
659 | | |
660 | | // Swap if relative_size == -1 |
661 | 16.9M | const bool need_swap = relative_size < 0; |
662 | 16.9M | CT::conditional_swap_ptr(need_swap, x, y); |
663 | 16.9M | CT::conditional_swap(need_swap, x_size, y_size); |
664 | | |
665 | | /* |
666 | | * We know at this point that x >= y so if y_size is larger than |
667 | | * x_size, we are guaranteed they are just leading zeros which can |
668 | | * be ignored |
669 | | */ |
670 | 16.9M | y_size = std::min(x_size, y_size); |
671 | | |
672 | 16.9M | bigint_sub3(z, x, x_size, y, y_size); |
673 | | |
674 | 16.9M | return relative_size; |
675 | 16.9M | } |
676 | | |
677 | | /** |
678 | | * Set t to t-s modulo mod |
679 | | * |
680 | | * @param t first integer |
681 | | * @param s second integer |
682 | | * @param mod the modulus |
683 | | * @param mod_sw size of t, s, and mod |
684 | | * @param ws workspace of size mod_sw |
685 | | */ |
686 | | inline void |
687 | | bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[]) |
688 | 81.5M | { |
689 | | // is t < s or not? |
690 | 81.5M | const auto is_lt = bigint_ct_is_lt(t, mod_sw, s, mod_sw); |
691 | | |
692 | | // ws = p - s |
693 | 81.5M | const word borrow = bigint_sub3(ws, mod, mod_sw, s, mod_sw); |
694 | | |
695 | | // Compute either (t - s) or (t + (p - s)) depending on mask |
696 | 81.5M | const word carry = bigint_cnd_addsub(is_lt, t, ws, s, mod_sw); |
697 | | |
698 | 81.5M | BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0); |
699 | 81.5M | BOTAN_UNUSED(carry, borrow); |
700 | 81.5M | } |
701 | | |
702 | | template<size_t N> |
703 | | inline void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[]) |
704 | 58.4M | { |
705 | | // is t < s or not? |
706 | 58.4M | const auto is_lt = bigint_ct_is_lt(t, N, s, N); |
707 | | |
708 | | // ws = p - s |
709 | 58.4M | const word borrow = bigint_sub3(ws, mod, N, s, N); |
710 | | |
711 | | // Compute either (t - s) or (t + (p - s)) depending on mask |
712 | 58.4M | const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N); |
713 | | |
714 | 58.4M | BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0); |
715 | 58.4M | BOTAN_UNUSED(carry, borrow); |
716 | 58.4M | } void Botan::bigint_mod_sub_n<4ul>(unsigned long*, unsigned long const*, unsigned long const*, unsigned long*) Line | Count | Source | 704 | 29.3M | { | 705 | | // is t < s or not? | 706 | 29.3M | const auto is_lt = bigint_ct_is_lt(t, N, s, N); | 707 | | | 708 | | // ws = p - s | 709 | 29.3M | const word borrow = bigint_sub3(ws, mod, N, s, N); | 710 | | | 711 | | // Compute either (t - s) or (t + (p - s)) depending on mask | 712 | 29.3M | const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N); | 713 | | | 714 | 29.3M | BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0); | 715 | 29.3M | BOTAN_UNUSED(carry, borrow); | 716 | 29.3M | } |
void Botan::bigint_mod_sub_n<6ul>(unsigned long*, unsigned long const*, unsigned long const*, unsigned long*) Line | Count | Source | 704 | 29.1M | { | 705 | | // is t < s or not? | 706 | 29.1M | const auto is_lt = bigint_ct_is_lt(t, N, s, N); | 707 | | | 708 | | // ws = p - s | 709 | 29.1M | const word borrow = bigint_sub3(ws, mod, N, s, N); | 710 | | | 711 | | // Compute either (t - s) or (t + (p - s)) depending on mask | 712 | 29.1M | const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N); | 713 | | | 714 | 29.1M | BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0); | 715 | 29.1M | BOTAN_UNUSED(carry, borrow); | 716 | 29.1M | } |
|
717 | | |
718 | | /** |
719 | | * Compute ((n1<<bits) + n0) / d |
720 | | */ |
721 | | inline word bigint_divop(word n1, word n0, word d) |
722 | 2.68M | { |
723 | 2.68M | if(d == 0) |
724 | 0 | throw Invalid_Argument("bigint_divop divide by zero"); |
725 | | |
726 | 2.68M | #if defined(BOTAN_HAS_MP_DWORD) |
727 | 2.68M | return static_cast<word>(((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) / d); |
728 | | #else |
729 | | |
730 | | word high = n1 % d; |
731 | | word quotient = 0; |
732 | | |
733 | | for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i) |
734 | | { |
735 | | const word high_top_bit = high >> (BOTAN_MP_WORD_BITS-1); |
736 | | |
737 | | high <<= 1; |
738 | | high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1; |
739 | | quotient <<= 1; |
740 | | |
741 | | if(high_top_bit || high >= d) |
742 | | { |
743 | | high -= d; |
744 | | quotient |= 1; |
745 | | } |
746 | | } |
747 | | |
748 | | return quotient; |
749 | | #endif |
750 | 2.68M | } |
751 | | |
752 | | /** |
753 | | * Compute ((n1<<bits) + n0) % d |
754 | | */ |
755 | | inline word bigint_modop(word n1, word n0, word d) |
756 | 547k | { |
757 | 547k | if(d == 0) |
758 | 0 | throw Invalid_Argument("bigint_modop divide by zero"); |
759 | | |
760 | 547k | #if defined(BOTAN_HAS_MP_DWORD) |
761 | 547k | return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) % d; |
762 | | #else |
763 | | word z = bigint_divop(n1, n0, d); |
764 | | word dummy = 0; |
765 | | z = word_madd2(z, d, &dummy); |
766 | | return (n0-z); |
767 | | #endif |
768 | 547k | } |
769 | | |
770 | | /* |
771 | | * Comba Multiplication / Squaring |
772 | | */ |
773 | | void bigint_comba_mul4(word z[8], const word x[4], const word y[4]); |
774 | | void bigint_comba_mul6(word z[12], const word x[6], const word y[6]); |
775 | | void bigint_comba_mul8(word z[16], const word x[8], const word y[8]); |
776 | | void bigint_comba_mul9(word z[18], const word x[9], const word y[9]); |
777 | | void bigint_comba_mul16(word z[32], const word x[16], const word y[16]); |
778 | | void bigint_comba_mul24(word z[48], const word x[24], const word y[24]); |
779 | | |
780 | | void bigint_comba_sqr4(word out[8], const word in[4]); |
781 | | void bigint_comba_sqr6(word out[12], const word in[6]); |
782 | | void bigint_comba_sqr8(word out[16], const word in[8]); |
783 | | void bigint_comba_sqr9(word out[18], const word in[9]); |
784 | | void bigint_comba_sqr16(word out[32], const word in[16]); |
785 | | void bigint_comba_sqr24(word out[48], const word in[24]); |
786 | | |
787 | | /** |
788 | | * Montgomery Reduction |
789 | | * @param z integer to reduce, of size exactly 2*(p_size+1). |
790 | | Output is in the first p_size+1 words, higher |
791 | | words are set to zero. |
792 | | * @param p modulus |
793 | | * @param p_size size of p |
794 | | * @param p_dash Montgomery value |
795 | | * @param workspace array of at least 2*(p_size+1) words |
796 | | * @param ws_size size of workspace in words |
797 | | */ |
798 | | void bigint_monty_redc(word z[], |
799 | | const word p[], size_t p_size, |
800 | | word p_dash, |
801 | | word workspace[], |
802 | | size_t ws_size); |
803 | | |
804 | | /* |
805 | | * High Level Multiplication/Squaring Interfaces |
806 | | */ |
807 | | |
808 | | void bigint_mul(word z[], size_t z_size, |
809 | | const word x[], size_t x_size, size_t x_sw, |
810 | | const word y[], size_t y_size, size_t y_sw, |
811 | | word workspace[], size_t ws_size); |
812 | | |
813 | | void bigint_sqr(word z[], size_t z_size, |
814 | | const word x[], size_t x_size, size_t x_sw, |
815 | | word workspace[], size_t ws_size); |
816 | | |
817 | | } |
818 | | |
819 | | #endif |