Coverage Report

Created: 2021-05-04 09:02

/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
96.5M
   {
31
96.5M
   const auto mask = CT::Mask<word>::expand(cnd);
32
33
1.87G
   for(size_t i = 0; i != size; ++i)
34
1.78G
      {
35
1.78G
      const word a = x[i];
36
1.78G
      const word b = y[i];
37
1.78G
      x[i] = mask.select(b, a);
38
1.78G
      y[i] = mask.select(a, b);
39
1.78G
      }
40
96.5M
   }
41
42
inline word bigint_cnd_add(word cnd, word x[], word x_size,
43
                           const word y[], size_t y_size)
44
226M
   {
45
226M
   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
46
47
226M
   const auto mask = CT::Mask<word>::expand(cnd);
48
49
226M
   word carry = 0;
50
51
226M
   const size_t blocks = y_size - (y_size % 8);
52
226M
   word z[8] = { 0 };
53
54
303M
   for(size_t i = 0; i != blocks; i += 8)
55
77.6M
      {
56
77.6M
      carry = word8_add3(z, x + i, y + i, carry);
57
77.6M
      mask.select_n(x + i, z, x + i, 8);
58
77.6M
      }
59
60
1.00G
   for(size_t i = blocks; i != y_size; ++i)
61
778M
      {
62
778M
      z[0] = word_add(x[i], y[i], &carry);
63
778M
      x[i] = mask.select(z[0], x[i]);
64
778M
      }
65
66
330M
   for(size_t i = y_size; i != x_size; ++i)
67
104M
      {
68
104M
      z[0] = word_add(x[i], 0, &carry);
69
104M
      x[i] = mask.select(z[0], x[i]);
70
104M
      }
71
72
226M
   return mask.if_set_return(carry);
73
226M
   }
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
129M
   {
81
129M
   return bigint_cnd_add(cnd, x, size, y, size);
82
129M
   }
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
209M
   {
92
209M
   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
93
94
209M
   const auto mask = CT::Mask<word>::expand(cnd);
95
96
209M
   word carry = 0;
97
98
209M
   const size_t blocks = y_size - (y_size % 8);
99
209M
   word z[8] = { 0 };
100
101
384M
   for(size_t i = 0; i != blocks; i += 8)
102
174M
      {
103
174M
      carry = word8_sub3(z, x + i, y + i, carry);
104
174M
      mask.select_n(x + i, z, x + i, 8);
105
174M
      }
106
107
519M
   for(size_t i = blocks; i != y_size; ++i)
108
310M
      {
109
310M
      z[0] = word_sub(x[i], y[i], &carry);
110
310M
      x[i] = mask.select(z[0], x[i]);
111
310M
      }
112
113
209M
   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
209M
   return mask.if_set_return(carry);
120
209M
   }
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
209M
   {
128
209M
   return bigint_cnd_sub(cnd, x, size, y, size);
129
209M
   }
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
276k
   {
141
276k
   const size_t blocks = size - (size % 8);
142
143
276k
   word carry = 0;
144
276k
   word borrow = 0;
145
146
276k
   word t0[8] = { 0 };
147
276k
   word t1[8] = { 0 };
148
149
1.99M
   for(size_t i = 0; i != blocks; i += 8)
150
1.71M
      {
151
1.71M
      carry = word8_add3(t0, x + i, y + i, carry);
152
1.71M
      borrow = word8_sub3(t1, x + i, y + i, borrow);
153
154
15.4M
      for(size_t j = 0; j != 8; ++j)
155
13.7M
         x[i+j] = mask.select(t0[j], t1[j]);
156
1.71M
      }
157
158
295k
   for(size_t i = blocks; i != size; ++i)
159
18.4k
      {
160
18.4k
      const word a = word_add(x[i], y[i], &carry);
161
18.4k
      const word s = word_sub(x[i], y[i], &borrow);
162
163
18.4k
      x[i] = mask.select(a, s);
164
18.4k
      }
165
276k
   }
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
128M
   {
180
128M
   const size_t blocks = size - (size % 8);
181
182
128M
   word carry = 0;
183
128M
   word borrow = 0;
184
185
128M
   word t0[8] = { 0 };
186
128M
   word t1[8] = { 0 };
187
188
201M
   for(size_t i = 0; i != blocks; i += 8)
189
73.7M
      {
190
73.7M
      carry = word8_add3(t0, x + i, y + i, carry);
191
73.7M
      borrow = word8_sub3(t1, x + i, z + i, borrow);
192
193
663M
      for(size_t j = 0; j != 8; ++j)
194
589M
         x[i+j] = mask.select(t0[j], t1[j]);
195
73.7M
      }
196
197
447M
   for(size_t i = blocks; i != size; ++i)
198
319M
      {
199
319M
      t0[0] = word_add(x[i], y[i], &carry);
200
319M
      t1[0] = word_sub(x[i], z[i], &borrow);
201
319M
      x[i] = mask.select(t0[0], t1[0]);
202
319M
      }
203
204
128M
   return mask.select(carry, borrow);
205
128M
   }
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
43.2M
   {
214
43.2M
   const auto mask = CT::Mask<word>::expand(cnd);
215
216
43.2M
   word carry = mask.if_set_return(1);
217
343M
   for(size_t i = 0; i != size; ++i)
218
300M
      {
219
300M
      const word z = word_add(~x[i], 0, &carry);
220
300M
      x[i] = mask.select(z, x[i]);
221
300M
      }
222
43.2M
   }
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
11.0M
   {
229
11.0M
   word carry = 0;
230
231
11.0M
   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
232
233
11.0M
   const size_t blocks = y_size - (y_size % 8);
234
235
20.9M
   for(size_t i = 0; i != blocks; i += 8)
236
9.92M
      carry = word8_add2(x + i, y + i, carry);
237
238
42.1M
   for(size_t i = blocks; i != y_size; ++i)
239
31.1M
      x[i] = word_add(x[i], y[i], &carry);
240
241
428M
   for(size_t i = y_size; i != x_size; ++i)
242
417M
      x[i] = word_add(x[i], 0, &carry);
243
244
11.0M
   return carry;
245
11.0M
   }
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
137M
   {
254
137M
   if(x_size < y_size)
255
124k
      { return bigint_add3_nc(z, y, y_size, x, x_size); }
256
257
137M
   word carry = 0;
258
259
137M
   const size_t blocks = y_size - (y_size % 8);
260
261
270M
   for(size_t i = 0; i != blocks; i += 8)
262
133M
      carry = word8_add3(z + i, x + i, y + i, carry);
263
264
296M
   for(size_t i = blocks; i != y_size; ++i)
265
158M
      z[i] = word_add(x[i], y[i], &carry);
266
267
137M
   for(size_t i = y_size; i != x_size; ++i)
268
533k
      z[i] = word_add(x[i], 0, &carry);
269
270
137M
   return carry;
271
137M
   }
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
9.35M
   {
283
9.35M
   x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
284
9.35M
   }
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.23M
   {
293
1.20M
   z[x_size > y_size ? x_size : y_size] +=
294
1.23M
      bigint_add3_nc(z, x, x_size, y, y_size);
295
1.23M
   }
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
99.2M
   {
303
99.2M
   word borrow = 0;
304
305
99.2M
   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
306
307
99.2M
   const size_t blocks = y_size - (y_size % 8);
308
309
125M
   for(size_t i = 0; i != blocks; i += 8)
310
26.1M
      borrow = word8_sub2(x + i, y + i, borrow);
311
312
607M
   for(size_t i = blocks; i != y_size; ++i)
313
507M
      x[i] = word_sub(x[i], y[i], &borrow);
314
315
202M
   for(size_t i = y_size; i != x_size; ++i)
316
102M
      x[i] = word_sub(x[i], 0, &borrow);
317
318
99.2M
   return borrow;
319
99.2M
   }
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
691k
   {
326
691k
   word borrow = 0;
327
328
691k
   const size_t blocks = y_size - (y_size % 8);
329
330
3.20M
   for(size_t i = 0; i != blocks; i += 8)
331
2.51M
      borrow = word8_sub2_rev(x + i, y + i, borrow);
332
333
3.06M
   for(size_t i = blocks; i != y_size; ++i)
334
2.37M
      x[i] = word_sub(y[i], x[i], &borrow);
335
336
691k
   BOTAN_ASSERT(borrow == 0, "y must be greater than x");
337
691k
   }
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
448M
   {
346
448M
   word borrow = 0;
347
348
448M
   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
349
350
448M
   const size_t blocks = y_size - (y_size % 8);
351
352
798M
   for(size_t i = 0; i != blocks; i += 8)
353
349M
      borrow = word8_sub3(z + i, x + i, y + i, borrow);
354
355
1.49G
   for(size_t i = blocks; i != y_size; ++i)
356
1.04G
      z[i] = word_sub(x[i], y[i], &borrow);
357
358
1.06G
   for(size_t i = y_size; i != x_size; ++i)
359
611M
      z[i] = word_sub(x[i], 0, &borrow);
360
361
448M
   return borrow;
362
448M
   }
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
813k
   {
381
   // Subtract in both direction then conditional copy out the result
382
383
813k
   word* ws0 = ws;
384
813k
   word* ws1 = ws + N;
385
386
813k
   word borrow0 = 0;
387
813k
   word borrow1 = 0;
388
389
813k
   const size_t blocks = N - (N % 8);
390
391
2.47M
   for(size_t i = 0; i != blocks; i += 8)
392
1.66M
      {
393
1.66M
      borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
394
1.66M
      borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
395
1.66M
      }
396
397
849k
   for(size_t i = blocks; i != N; ++i)
398
36.7k
      {
399
36.7k
      ws0[i] = word_sub(x[i], y[i], &borrow0);
400
36.7k
      ws1[i] = word_sub(y[i], x[i], &borrow1);
401
36.7k
      }
402
403
813k
   return CT::conditional_copy_mem(borrow0, z, ws1, ws0, N);
404
813k
   }
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.66M
   {
412
4.66M
   copy_mem(x + word_shift, x, x_words);
413
4.66M
   clear_mem(x, word_shift);
414
415
4.66M
   const auto carry_mask = CT::Mask<word>::expand(bit_shift);
416
4.66M
   const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
417
418
4.66M
   word carry = 0;
419
28.5M
   for(size_t i = word_shift; i != x_size; ++i)
420
23.9M
      {
421
23.9M
      const word w = x[i];
422
23.9M
      x[i] = (w << bit_shift) | carry;
423
23.9M
      carry = carry_mask.if_set_return(w >> carry_shift);
424
23.9M
      }
425
4.66M
   }
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
432
110M
   if(top > 0)
433
110M
      copy_mem(x, x + word_shift, top);
434
110M
   clear_mem(x + top, std::min(word_shift, x_size));
435
436
110M
   const auto carry_mask = CT::Mask<word>::expand(bit_shift);
437
110M
   const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
438
439
110M
   word carry = 0;
440
441
1.43G
   for(size_t i = 0; i != top; ++i)
442
1.32G
      {
443
1.32G
      const word w = x[top - i - 1];
444
1.32G
      x[top-i-1] = (w >> bit_shift) | carry;
445
1.32G
      carry = carry_mask.if_set_return(w << carry_shift);
446
1.32G
      }
447
110M
   }
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.33M
   {
452
2.33M
   copy_mem(y + word_shift, x, x_size);
453
454
2.33M
   const auto carry_mask = CT::Mask<word>::expand(bit_shift);
455
2.33M
   const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
456
457
2.33M
   word carry = 0;
458
15.3M
   for(size_t i = word_shift; i != x_size + word_shift + 1; ++i)
459
12.9M
      {
460
12.9M
      const word w = y[i];
461
12.9M
      y[i] = (w << bit_shift) | carry;
462
12.9M
      carry = carry_mask.if_set_return(w >> carry_shift);
463
12.9M
      }
464
2.33M
   }
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
126M
   {
469
126M
   const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
470
471
126M
   if(new_size > 0)
472
126M
      copy_mem(y, x + word_shift, new_size);
473
474
126M
   const auto carry_mask = CT::Mask<word>::expand(bit_shift);
475
126M
   const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
476
477
126M
   word carry = 0;
478
1.36G
   for(size_t i = new_size; i > 0; --i)
479
1.24G
      {
480
1.24G
      word w = y[i-1];
481
1.24G
      y[i-1] = (w >> bit_shift) | carry;
482
1.24G
      carry = carry_mask.if_set_return(w << carry_shift);
483
1.24G
      }
484
126M
   }
485
486
/*
487
* Linear Multiply - returns the carry
488
*/
489
[[nodiscard]] inline word bigint_linmul2(word x[], size_t x_size, word y)
490
96.5M
   {
491
96.5M
   const size_t blocks = x_size - (x_size % 8);
492
493
96.5M
   word carry = 0;
494
495
377M
   for(size_t i = 0; i != blocks; i += 8)
496
281M
      carry = word8_linmul2(x + i, y, carry);
497
498
202M
   for(size_t i = blocks; i != x_size; ++i)
499
105M
      x[i] = word_madd2(x[i], y, &carry);
500
501
96.5M
   return carry;
502
96.5M
   }
503
504
inline void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
505
4.74M
   {
506
4.74M
   const size_t blocks = x_size - (x_size % 8);
507
508
4.74M
   word carry = 0;
509
510
28.3M
   for(size_t i = 0; i != blocks; i += 8)
511
23.5M
      carry = word8_linmul3(z + i, x + i, y, carry);
512
513
21.1M
   for(size_t i = blocks; i != x_size; ++i)
514
16.4M
      z[i] = word_madd2(x[i], y, &carry);
515
516
4.74M
   z[x_size] = carry;
517
4.74M
   }
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
18.4M
   {
528
18.4M
   static_assert(sizeof(word) >= sizeof(uint32_t), "Size assumption");
529
530
18.4M
   const word LT = static_cast<word>(-1);
531
18.4M
   const word EQ = 0;
532
18.4M
   const word GT = 1;
533
534
18.4M
   const size_t common_elems = std::min(x_size, y_size);
535
536
18.4M
   word result = EQ; // until found otherwise
537
538
361M
   for(size_t i = 0; i != common_elems; i++)
539
343M
      {
540
343M
      const auto is_eq = CT::Mask<word>::is_equal(x[i], y[i]);
541
343M
      const auto is_lt = CT::Mask<word>::is_lt(x[i], y[i]);
542
543
343M
      result = is_eq.select(result, is_lt.select(LT, GT));
544
343M
      }
545
546
18.4M
   if(x_size < y_size)
547
6.23M
      {
548
6.23M
      word mask = 0;
549
36.6M
      for(size_t i = x_size; i != y_size; i++)
550
30.4M
         mask |= y[i];
551
552
      // If any bits were set in high part of y, then x < y
553
6.23M
      result = CT::Mask<word>::is_zero(mask).select(result, LT);
554
6.23M
      }
555
12.2M
   else if(y_size < x_size)
556
462k
      {
557
462k
      word mask = 0;
558
5.08M
      for(size_t i = y_size; i != x_size; i++)
559
4.62M
         mask |= x[i];
560
561
      // If any bits were set in high part of x, then x > y
562
462k
      result = CT::Mask<word>::is_zero(mask).select(result, GT);
563
462k
      }
564
565
18.4M
   CT::unpoison(result);
566
18.4M
   BOTAN_DEBUG_ASSERT(result == LT || result == GT || result == EQ);
567
18.4M
   return static_cast<int32_t>(result);
568
18.4M
   }
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
139M
   {
580
139M
   const size_t common_elems = std::min(x_size, y_size);
581
582
139M
   auto is_lt = CT::Mask<word>::expand(lt_or_equal);
583
584
1.08G
   for(size_t i = 0; i != common_elems; i++)
585
948M
      {
586
948M
      const auto eq = CT::Mask<word>::is_equal(x[i], y[i]);
587
948M
      const auto lt = CT::Mask<word>::is_lt(x[i], y[i]);
588
948M
      is_lt = eq.select_mask(is_lt, lt);
589
948M
      }
590
591
139M
   if(x_size < y_size)
592
129k
      {
593
129k
      word mask = 0;
594
816k
      for(size_t i = x_size; i != y_size; i++)
595
687k
         mask |= y[i];
596
      // If any bits were set in high part of y, then is_lt should be forced true
597
129k
      is_lt |= CT::Mask<word>::expand(mask);
598
129k
      }
599
139M
   else if(y_size < x_size)
600
285k
      {
601
285k
      word mask = 0;
602
1.38M
      for(size_t i = y_size; i != x_size; i++)
603
1.10M
         mask |= x[i];
604
605
      // If any bits were set in high part of x, then is_lt should be false
606
285k
      is_lt &= CT::Mask<word>::is_zero(mask);
607
285k
      }
608
609
139M
   return is_lt;
610
139M
   }
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
231k
   {
616
231k
   const size_t common_elems = std::min(x_size, y_size);
617
618
231k
   word diff = 0;
619
620
1.65M
   for(size_t i = 0; i != common_elems; i++)
621
1.41M
      {
622
1.41M
      diff |= (x[i] ^ y[i]);
623
1.41M
      }
624
625
   // If any bits were set in high part of x/y, then they are not equal
626
231k
   if(x_size < y_size)
627
5.36k
      {
628
22.8k
      for(size_t i = x_size; i != y_size; i++)
629
17.5k
         diff |= y[i];
630
5.36k
      }
631
226k
   else if(y_size < x_size)
632
2.83k
      {
633
13.6k
      for(size_t i = y_size; i != x_size; i++)
634
10.8k
         diff |= x[i];
635
2.83k
      }
636
637
231k
   return CT::Mask<word>::is_zero(diff);
638
231k
   }
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
13.0M
   {
658
13.0M
   const int32_t relative_size = bigint_cmp(x, x_size, y, y_size);
659
660
   // Swap if relative_size == -1
661
13.0M
   const bool need_swap = relative_size < 0;
662
13.0M
   CT::conditional_swap_ptr(need_swap, x, y);
663
13.0M
   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
13.0M
   y_size = std::min(x_size, y_size);
671
672
13.0M
   bigint_sub3(z, x, x_size, y, y_size);
673
674
13.0M
   return relative_size;
675
13.0M
   }
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
75.2M
   {
689
   // is t < s or not?
690
75.2M
   const auto is_lt = bigint_ct_is_lt(t, mod_sw, s, mod_sw);
691
692
   // ws = p - s
693
75.2M
   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
75.2M
   const word carry = bigint_cnd_addsub(is_lt, t, ws, s, mod_sw);
697
698
75.2M
   BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
699
75.2M
   BOTAN_UNUSED(carry, borrow);
700
75.2M
   }
701
702
template<size_t N>
703
inline void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
704
53.0M
   {
705
   // is t < s or not?
706
53.0M
   const auto is_lt = bigint_ct_is_lt(t, N, s, N);
707
708
   // ws = p - s
709
53.0M
   const word borrow = bigint_sub3(ws, mod, N, s, N);
710
711
   // Compute either (t - s) or (t + (p - s)) depending on mask
712
53.0M
   const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N);
713
714
53.0M
   BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
715
53.0M
   BOTAN_UNUSED(carry, borrow);
716
53.0M
   }
void Botan::bigint_mod_sub_n<4ul>(unsigned long*, unsigned long const*, unsigned long const*, unsigned long*)
Line
Count
Source
704
27.4M
   {
705
   // is t < s or not?
706
27.4M
   const auto is_lt = bigint_ct_is_lt(t, N, s, N);
707
708
   // ws = p - s
709
27.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
27.4M
   const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N);
713
714
27.4M
   BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
715
27.4M
   BOTAN_UNUSED(carry, borrow);
716
27.4M
   }
void Botan::bigint_mod_sub_n<6ul>(unsigned long*, unsigned long const*, unsigned long const*, unsigned long*)
Line
Count
Source
704
25.6M
   {
705
   // is t < s or not?
706
25.6M
   const auto is_lt = bigint_ct_is_lt(t, N, s, N);
707
708
   // ws = p - s
709
25.6M
   const word borrow = bigint_sub3(ws, mod, N, s, N);
710
711
   // Compute either (t - s) or (t + (p - s)) depending on mask
712
25.6M
   const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N);
713
714
25.6M
   BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
715
25.6M
   BOTAN_UNUSED(carry, borrow);
716
25.6M
   }
717
718
/**
719
* Compute ((n1<<bits) + n0) / d
720
*/
721
inline word bigint_divop(word n1, word n0, word d)
722
2.65M
   {
723
2.65M
   if(d == 0)
724
0
      throw Invalid_Argument("bigint_divop divide by zero");
725
726
2.65M
#if defined(BOTAN_HAS_MP_DWORD)
727
2.65M
   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.65M
   }
751
752
/**
753
* Compute ((n1<<bits) + n0) % d
754
*/
755
inline word bigint_modop(word n1, word n0, word d)
756
513k
   {
757
513k
   if(d == 0)
758
0
      throw Invalid_Argument("bigint_modop divide by zero");
759
760
513k
#if defined(BOTAN_HAS_MP_DWORD)
761
513k
   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
513k
   }
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
*
790
* Each of these functions makes the following assumptions:
791
*
792
* z_size >= 2*(p_size + 1)
793
* ws_size >= z_size
794
*/
795
void bigint_monty_redc_4(word z[], const word p[], word p_dash, word ws[]);
796
void bigint_monty_redc_6(word z[], const word p[], word p_dash, word ws[]);
797
void bigint_monty_redc_8(word z[], const word p[], word p_dash, word ws[]);
798
void bigint_monty_redc_16(word z[], const word p[], word p_dash, word ws[]);
799
void bigint_monty_redc_24(word z[], const word p[], word p_dash, word ws[]);
800
void bigint_monty_redc_32(word z[], const word p[], word p_dash, word ws[]);
801
802
void bigint_monty_redc_generic(word z[], size_t z_size,
803
                               const word p[], size_t p_size, word p_dash,
804
                               word ws[]);
805
806
807
/**
808
* Montgomery Reduction
809
* @param z integer to reduce, of size exactly 2*(p_size+1).
810
           Output is in the first p_size+1 words, higher
811
           words are set to zero.
812
* @param p modulus
813
* @param p_size size of p
814
* @param p_dash Montgomery value
815
* @param ws array of at least 2*(p_size+1) words
816
* @param ws_size size of ws in words
817
*/
818
inline void bigint_monty_redc(word z[],
819
                              const word p[], size_t p_size,
820
                              word p_dash,
821
                              word ws[],
822
                              size_t ws_size)
823
91.8M
   {
824
91.8M
   const size_t z_size = 2*(p_size+1);
825
826
91.8M
   BOTAN_ARG_CHECK(ws_size >= z_size, "ws too small");
827
828
91.8M
   if(p_size == 4)
829
30.3M
      bigint_monty_redc_4(z, p, p_dash, ws);
830
61.5M
   else if(p_size == 6)
831
4.65M
      bigint_monty_redc_6(z, p, p_dash, ws);
832
56.8M
   else if(p_size == 8)
833
48.9M
      bigint_monty_redc_8(z, p, p_dash, ws);
834
7.90M
   else if(p_size == 16)
835
140k
      bigint_monty_redc_16(z, p, p_dash, ws);
836
7.76M
   else if(p_size == 24)
837
34.9k
      bigint_monty_redc_24(z, p, p_dash, ws);
838
7.72M
   else if(p_size == 32)
839
175k
      bigint_monty_redc_32(z, p, p_dash, ws);
840
7.54M
   else
841
7.54M
      bigint_monty_redc_generic(z, z_size, p, p_size, p_dash, ws);
842
91.8M
   }
843
844
845
/*
846
* High Level Multiplication/Squaring Interfaces
847
*/
848
849
void bigint_mul(word z[], size_t z_size,
850
                const word x[], size_t x_size, size_t x_sw,
851
                const word y[], size_t y_size, size_t y_sw,
852
                word workspace[], size_t ws_size);
853
854
void bigint_sqr(word z[], size_t z_size,
855
                const word x[], size_t x_size, size_t x_sw,
856
                word workspace[], size_t ws_size);
857
858
}
859
860
#endif