Botan  2.19.1
Crypto and TLS for C++11
mp_core.h
Go to the documentation of this file.
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  {
31  const auto mask = CT::Mask<word>::expand(cnd);
32 
33  for(size_t i = 0; i != size; ++i)
34  {
35  const word a = x[i];
36  const word b = y[i];
37  x[i] = mask.select(b, a);
38  y[i] = mask.select(a, b);
39  }
40  }
41 
42 inline word bigint_cnd_add(word cnd, word x[], word x_size,
43  const word y[], size_t y_size)
44  {
45  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
46 
47  const auto mask = CT::Mask<word>::expand(cnd);
48 
49  word carry = 0;
50 
51  const size_t blocks = y_size - (y_size % 8);
52  word z[8] = { 0 };
53 
54  for(size_t i = 0; i != blocks; i += 8)
55  {
56  carry = word8_add3(z, x + i, y + i, carry);
57  mask.select_n(x + i, z, x + i, 8);
58  }
59 
60  for(size_t i = blocks; i != y_size; ++i)
61  {
62  z[0] = word_add(x[i], y[i], &carry);
63  x[i] = mask.select(z[0], x[i]);
64  }
65 
66  for(size_t i = y_size; i != x_size; ++i)
67  {
68  z[0] = word_add(x[i], 0, &carry);
69  x[i] = mask.select(z[0], x[i]);
70  }
71 
72  return mask.if_set_return(carry);
73  }
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  {
81  return bigint_cnd_add(cnd, x, size, y, size);
82  }
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  {
92  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
93 
94  const auto mask = CT::Mask<word>::expand(cnd);
95 
96  word carry = 0;
97 
98  const size_t blocks = y_size - (y_size % 8);
99  word z[8] = { 0 };
100 
101  for(size_t i = 0; i != blocks; i += 8)
102  {
103  carry = word8_sub3(z, x + i, y + i, carry);
104  mask.select_n(x + i, z, x + i, 8);
105  }
106 
107  for(size_t i = blocks; i != y_size; ++i)
108  {
109  z[0] = word_sub(x[i], y[i], &carry);
110  x[i] = mask.select(z[0], x[i]);
111  }
112 
113  for(size_t i = y_size; i != x_size; ++i)
114  {
115  z[0] = word_sub(x[i], 0, &carry);
116  x[i] = mask.select(z[0], x[i]);
117  }
118 
119  return mask.if_set_return(carry);
120  }
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  {
128  return bigint_cnd_sub(cnd, x, size, y, size);
129  }
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  {
141  const size_t blocks = size - (size % 8);
142 
143  word carry = 0;
144  word borrow = 0;
145 
146  word t0[8] = { 0 };
147  word t1[8] = { 0 };
148 
149  for(size_t i = 0; i != blocks; i += 8)
150  {
151  carry = word8_add3(t0, x + i, y + i, carry);
152  borrow = word8_sub3(t1, x + i, y + i, borrow);
153 
154  for(size_t j = 0; j != 8; ++j)
155  x[i+j] = mask.select(t0[j], t1[j]);
156  }
157 
158  for(size_t i = blocks; i != size; ++i)
159  {
160  const word a = word_add(x[i], y[i], &carry);
161  const word s = word_sub(x[i], y[i], &borrow);
162 
163  x[i] = mask.select(a, s);
164  }
165  }
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  {
180  const size_t blocks = size - (size % 8);
181 
182  word carry = 0;
183  word borrow = 0;
184 
185  word t0[8] = { 0 };
186  word t1[8] = { 0 };
187 
188  for(size_t i = 0; i != blocks; i += 8)
189  {
190  carry = word8_add3(t0, x + i, y + i, carry);
191  borrow = word8_sub3(t1, x + i, z + i, borrow);
192 
193  for(size_t j = 0; j != 8; ++j)
194  x[i+j] = mask.select(t0[j], t1[j]);
195  }
196 
197  for(size_t i = blocks; i != size; ++i)
198  {
199  t0[0] = word_add(x[i], y[i], &carry);
200  t1[0] = word_sub(x[i], z[i], &borrow);
201  x[i] = mask.select(t0[0], t1[0]);
202  }
203 
204  return mask.select(carry, borrow);
205  }
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  {
214  const auto mask = CT::Mask<word>::expand(cnd);
215 
216  word carry = mask.if_set_return(1);
217  for(size_t i = 0; i != size; ++i)
218  {
219  const word z = word_add(~x[i], 0, &carry);
220  x[i] = mask.select(z, x[i]);
221  }
222  }
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  {
229  word carry = 0;
230 
231  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
232 
233  const size_t blocks = y_size - (y_size % 8);
234 
235  for(size_t i = 0; i != blocks; i += 8)
236  carry = word8_add2(x + i, y + i, carry);
237 
238  for(size_t i = blocks; i != y_size; ++i)
239  x[i] = word_add(x[i], y[i], &carry);
240 
241  for(size_t i = y_size; i != x_size; ++i)
242  x[i] = word_add(x[i], 0, &carry);
243 
244  return carry;
245  }
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  {
254  if(x_size < y_size)
255  { return bigint_add3_nc(z, y, y_size, x, x_size); }
256 
257  word carry = 0;
258 
259  const size_t blocks = y_size - (y_size % 8);
260 
261  for(size_t i = 0; i != blocks; i += 8)
262  carry = word8_add3(z + i, x + i, y + i, carry);
263 
264  for(size_t i = blocks; i != y_size; ++i)
265  z[i] = word_add(x[i], y[i], &carry);
266 
267  for(size_t i = y_size; i != x_size; ++i)
268  z[i] = word_add(x[i], 0, &carry);
269 
270  return carry;
271  }
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  {
283  x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
284  }
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  {
293  z[x_size > y_size ? x_size : y_size] +=
294  bigint_add3_nc(z, x, x_size, y, y_size);
295  }
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  {
303  word borrow = 0;
304 
305  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
306 
307  const size_t blocks = y_size - (y_size % 8);
308 
309  for(size_t i = 0; i != blocks; i += 8)
310  borrow = word8_sub2(x + i, y + i, borrow);
311 
312  for(size_t i = blocks; i != y_size; ++i)
313  x[i] = word_sub(x[i], y[i], &borrow);
314 
315  for(size_t i = y_size; i != x_size; ++i)
316  x[i] = word_sub(x[i], 0, &borrow);
317 
318  return borrow;
319  }
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  {
326  word borrow = 0;
327 
328  const size_t blocks = y_size - (y_size % 8);
329 
330  for(size_t i = 0; i != blocks; i += 8)
331  borrow = word8_sub2_rev(x + i, y + i, borrow);
332 
333  for(size_t i = blocks; i != y_size; ++i)
334  x[i] = word_sub(y[i], x[i], &borrow);
335 
336  BOTAN_ASSERT(borrow == 0, "y must be greater than x");
337  }
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  {
346  word borrow = 0;
347 
348  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
349 
350  const size_t blocks = y_size - (y_size % 8);
351 
352  for(size_t i = 0; i != blocks; i += 8)
353  borrow = word8_sub3(z + i, x + i, y + i, borrow);
354 
355  for(size_t i = blocks; i != y_size; ++i)
356  z[i] = word_sub(x[i], y[i], &borrow);
357 
358  for(size_t i = y_size; i != x_size; ++i)
359  z[i] = word_sub(x[i], 0, &borrow);
360 
361  return borrow;
362  }
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  {
381  // Subtract in both direction then conditional copy out the result
382 
383  word* ws0 = ws;
384  word* ws1 = ws + N;
385 
386  word borrow0 = 0;
387  word borrow1 = 0;
388 
389  const size_t blocks = N - (N % 8);
390 
391  for(size_t i = 0; i != blocks; i += 8)
392  {
393  borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
394  borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
395  }
396 
397  for(size_t i = blocks; i != N; ++i)
398  {
399  ws0[i] = word_sub(x[i], y[i], &borrow0);
400  ws1[i] = word_sub(y[i], x[i], &borrow1);
401  }
402 
403  return CT::conditional_copy_mem(borrow0, z, ws1, ws0, N);
404  }
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  {
412  copy_mem(x + word_shift, x, x_words);
413  clear_mem(x, word_shift);
414 
415  const auto carry_mask = CT::Mask<word>::expand(bit_shift);
416  const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
417 
418  word carry = 0;
419  for(size_t i = word_shift; i != x_size; ++i)
420  {
421  const word w = x[i];
422  x[i] = (w << bit_shift) | carry;
423  carry = carry_mask.if_set_return(w >> carry_shift);
424  }
425  }
426 
427 inline void bigint_shr1(word x[], size_t x_size,
428  size_t word_shift, size_t bit_shift)
429  {
430  const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
431 
432  if(top > 0)
433  copy_mem(x, x + word_shift, top);
434  clear_mem(x + top, std::min(word_shift, x_size));
435 
436  const auto carry_mask = CT::Mask<word>::expand(bit_shift);
437  const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
438 
439  word carry = 0;
440 
441  for(size_t i = 0; i != top; ++i)
442  {
443  const word w = x[top - i - 1];
444  x[top-i-1] = (w >> bit_shift) | carry;
445  carry = carry_mask.if_set_return(w << carry_shift);
446  }
447  }
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  {
452  copy_mem(y + word_shift, x, x_size);
453 
454  const auto carry_mask = CT::Mask<word>::expand(bit_shift);
455  const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
456 
457  word carry = 0;
458  for(size_t i = word_shift; i != x_size + word_shift + 1; ++i)
459  {
460  const word w = y[i];
461  y[i] = (w << bit_shift) | carry;
462  carry = carry_mask.if_set_return(w >> carry_shift);
463  }
464  }
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  {
469  const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
470 
471  if(new_size > 0)
472  copy_mem(y, x + word_shift, new_size);
473 
474  const auto carry_mask = CT::Mask<word>::expand(bit_shift);
475  const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
476 
477  word carry = 0;
478  for(size_t i = new_size; i > 0; --i)
479  {
480  word w = y[i-1];
481  y[i-1] = (w >> bit_shift) | carry;
482  carry = carry_mask.if_set_return(w << carry_shift);
483  }
484  }
485 
486 /*
487 * Linear Multiply - returns the carry
488 */
489 inline word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y)
490  {
491  const size_t blocks = x_size - (x_size % 8);
492 
493  word carry = 0;
494 
495  for(size_t i = 0; i != blocks; i += 8)
496  carry = word8_linmul2(x + i, y, carry);
497 
498  for(size_t i = blocks; i != x_size; ++i)
499  x[i] = word_madd2(x[i], y, &carry);
500 
501  return carry;
502  }
503 
504 inline void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
505  {
506  const size_t blocks = x_size - (x_size % 8);
507 
508  word carry = 0;
509 
510  for(size_t i = 0; i != blocks; i += 8)
511  carry = word8_linmul3(z + i, x + i, y, carry);
512 
513  for(size_t i = blocks; i != x_size; ++i)
514  z[i] = word_madd2(x[i], y, &carry);
515 
516  z[x_size] = carry;
517  }
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  {
528  static_assert(sizeof(word) >= sizeof(uint32_t), "Size assumption");
529 
530  const word LT = static_cast<word>(-1);
531  const word EQ = 0;
532  const word GT = 1;
533 
534  const size_t common_elems = std::min(x_size, y_size);
535 
536  word result = EQ; // until found otherwise
537 
538  for(size_t i = 0; i != common_elems; i++)
539  {
540  const auto is_eq = CT::Mask<word>::is_equal(x[i], y[i]);
541  const auto is_lt = CT::Mask<word>::is_lt(x[i], y[i]);
542 
543  result = is_eq.select(result, is_lt.select(LT, GT));
544  }
545 
546  if(x_size < y_size)
547  {
548  word mask = 0;
549  for(size_t i = x_size; i != y_size; i++)
550  mask |= y[i];
551 
552  // If any bits were set in high part of y, then x < y
553  result = CT::Mask<word>::is_zero(mask).select(result, LT);
554  }
555  else if(y_size < x_size)
556  {
557  word mask = 0;
558  for(size_t i = y_size; i != x_size; i++)
559  mask |= x[i];
560 
561  // If any bits were set in high part of x, then x > y
562  result = CT::Mask<word>::is_zero(mask).select(result, GT);
563  }
564 
565  CT::unpoison(result);
566  BOTAN_DEBUG_ASSERT(result == LT || result == GT || result == EQ);
567  return static_cast<int32_t>(result);
568  }
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  {
580  const size_t common_elems = std::min(x_size, y_size);
581 
582  auto is_lt = CT::Mask<word>::expand(lt_or_equal);
583 
584  for(size_t i = 0; i != common_elems; i++)
585  {
586  const auto eq = CT::Mask<word>::is_equal(x[i], y[i]);
587  const auto lt = CT::Mask<word>::is_lt(x[i], y[i]);
588  is_lt = eq.select_mask(is_lt, lt);
589  }
590 
591  if(x_size < y_size)
592  {
593  word mask = 0;
594  for(size_t i = x_size; i != y_size; i++)
595  mask |= y[i];
596  // If any bits were set in high part of y, then is_lt should be forced true
597  is_lt |= CT::Mask<word>::expand(mask);
598  }
599  else if(y_size < x_size)
600  {
601  word mask = 0;
602  for(size_t i = y_size; i != x_size; i++)
603  mask |= x[i];
604 
605  // If any bits were set in high part of x, then is_lt should be false
606  is_lt &= CT::Mask<word>::is_zero(mask);
607  }
608 
609  return is_lt;
610  }
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  {
616  const size_t common_elems = std::min(x_size, y_size);
617 
618  word diff = 0;
619 
620  for(size_t i = 0; i != common_elems; i++)
621  {
622  diff |= (x[i] ^ y[i]);
623  }
624 
625  // If any bits were set in high part of x/y, then they are not equal
626  if(x_size < y_size)
627  {
628  for(size_t i = x_size; i != y_size; i++)
629  diff |= y[i];
630  }
631  else if(y_size < x_size)
632  {
633  for(size_t i = y_size; i != x_size; i++)
634  diff |= x[i];
635  }
636 
637  return CT::Mask<word>::is_zero(diff);
638  }
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  {
658  const int32_t relative_size = bigint_cmp(x, x_size, y, y_size);
659 
660  // Swap if relative_size == -1
661  const bool need_swap = relative_size < 0;
662  CT::conditional_swap_ptr(need_swap, x, y);
663  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  y_size = std::min(x_size, y_size);
671 
672  bigint_sub3(z, x, x_size, y, y_size);
673 
674  return relative_size;
675  }
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  {
689  // is t < s or not?
690  const auto is_lt = bigint_ct_is_lt(t, mod_sw, s, mod_sw);
691 
692  // ws = p - s
693  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  const word carry = bigint_cnd_addsub(is_lt, t, ws, s, mod_sw);
697 
698  BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
699  BOTAN_UNUSED(carry, borrow);
700  }
701 
702 template<size_t N>
703 inline void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
704  {
705  // is t < s or not?
706  const auto is_lt = bigint_ct_is_lt(t, N, s, N);
707 
708  // ws = p - s
709  const word borrow = bigint_sub3(ws, mod, N, s, N);
710 
711  // Compute either (t - s) or (t + (p - s)) depending on mask
712  const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N);
713 
714  BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
715  BOTAN_UNUSED(carry, borrow);
716  }
717 
718 /**
719 * Compute ((n1<<bits) + n0) / d
720 */
721 inline word bigint_divop(word n1, word n0, word d)
722  {
723  if(d == 0)
724  throw Invalid_Argument("bigint_divop divide by zero");
725 
726 #if defined(BOTAN_HAS_MP_DWORD)
727  return ((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  }
751 
752 /**
753 * Compute ((n1<<bits) + n0) % d
754 */
755 inline word bigint_modop(word n1, word n0, word d)
756  {
757  if(d == 0)
758  throw Invalid_Argument("bigint_modop divide by zero");
759 
760 #if defined(BOTAN_HAS_MP_DWORD)
761  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  }
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
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:427
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:324
word word8_sub2_rev(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:275
void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition: ct_utils.h:386
word word8_add2(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:138
word word8_linmul3(word z[8], const word x[8], word y, word carry)
Definition: mp_asmi.h:381
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:466
void carry(int64_t &h0, int64_t &h1)
word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:489
void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
Definition: mp_core.h:703
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:525
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:300
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:250
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
Definition: mp_comba.cpp:50
#define BOTAN_WARN_UNUSED_RESULT
Definition: compiler.h:86
word word8_sub2(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:240
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:342
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.h:721
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
Definition: mp_comba.cpp:474
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:357
uint64_t carry_shift(const donna128 &a, size_t shift)
Definition: donna128.h:116
word bigint_cnd_addsub(CT::Mask< word > mask, word x[], const word y[], const word z[], size_t size)
Definition: mp_core.h:176
T select(T x, T y) const
Definition: ct_utils.h:288
void bigint_comba_mul24(word z[48], const word x[24], const word y[24])
Definition: mp_comba.cpp:1535
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:46
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
void bigint_comba_sqr16(word z[32], const word x[16])
Definition: mp_comba.cpp:598
static Mask< T > expand(T v)
Definition: ct_utils.h:123
word bigint_cnd_sub(word cnd, word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:88
void bigint_shl1(word x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:409
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:377
void bigint_comba_sqr24(word z[48], const word x[24])
Definition: mp_comba.cpp:1132
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.h:29
word word8_linmul2(word x[8], word y, word carry)
Definition: mp_asmi.h:346
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
Definition: mp_core.h:42
CT::Mask< word > bigint_ct_is_eq(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:613
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:227
void bigint_cnd_add_or_sub(CT::Mask< word > mask, word x[], const word y[], size_t size)
Definition: mp_core.h:139
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:133
Definition: alg_id.cpp:13
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:363
void bigint_comba_sqr9(word z[18], const word x[9])
Definition: mp_comba.cpp:386
#define BOTAN_UNUSED(...)
Definition: assert.h:142
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:298
word word8_add3(word z[8], const word x[8], const word y[8], word carry)
Definition: mp_asmi.h:173
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:449
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
Definition: mp_comba.cpp:283
const word MP_WORD_MAX
Definition: mp_core.h:22
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:209
CT::Mask< word > bigint_ct_is_lt(const word x[], size_t x_size, const word y[], size_t y_size, bool lt_or_equal=false)
Definition: mp_core.h:576
void bigint_comba_sqr8(word z[16], const word x[8])
Definition: mp_comba.cpp:208
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:280
void bigint_comba_mul16(word z[32], const word x[16], const word y[16])
Definition: mp_comba.cpp:805
word word_add(word x, word y, word *carry)
Definition: mp_asmi.h:107
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
Definition: mp_comba.cpp:141
void bigint_cnd_abs(word cnd, word x[], size_t size)
Definition: mp_core.h:212
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141
word word8_sub3(word z[8], const word x[8], const word y[8], word carry)
Definition: mp_asmi.h:310
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:687
void bigint_comba_sqr4(word z[8], const word x[4])
Definition: mp_comba.cpp:17
void bigint_comba_sqr6(word z[12], const word x[6])
Definition: mp_comba.cpp:89
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:289
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:755
static Mask< T > is_lt(T x, T y)
Definition: ct_utils.h:157
void conditional_swap(bool cnd, T &x, T &y)
Definition: ct_utils.h:375