Botan  2.9.0
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_MASK = ~static_cast<word>(0);
23 const word MP_WORD_TOP_BIT = static_cast<word>(1) << (8*sizeof(word) - 1);
25 
26 /*
27 * If cond == 0, does nothing.
28 * If cond > 0, swaps x[0:size] with y[0:size]
29 * Runs in constant time
30 */
31 inline void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
32  {
33  const auto mask = CT::Mask<word>::expand(cnd);
34 
35  for(size_t i = 0; i != size; ++i)
36  {
37  const word a = x[i];
38  const word b = y[i];
39  x[i] = mask.select(b, a);
40  y[i] = mask.select(a, b);
41  }
42  }
43 
44 inline word bigint_cnd_add(word cnd, word x[], word x_size,
45  const word y[], size_t y_size)
46  {
47  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
48 
49  const auto mask = CT::Mask<word>::expand(cnd);
50 
51  word carry = 0;
52 
53  const size_t blocks = y_size - (y_size % 8);
54  word z[8] = { 0 };
55 
56  for(size_t i = 0; i != blocks; i += 8)
57  {
58  carry = word8_add3(z, x + i, y + i, carry);
59  mask.select_n(x + i, z, x + i, 8);
60  }
61 
62  for(size_t i = blocks; i != y_size; ++i)
63  {
64  z[0] = word_add(x[i], y[i], &carry);
65  x[i] = mask.select(z[0], x[i]);
66  }
67 
68  for(size_t i = y_size; i != x_size; ++i)
69  {
70  z[0] = word_add(x[i], 0, &carry);
71  x[i] = mask.select(z[0], x[i]);
72  }
73 
74  return mask.if_set_return(carry);
75  }
76 
77 /*
78 * If cond > 0 adds x[0:size] and y[0:size] and returns carry
79 * Runs in constant time
80 */
81 inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
82  {
83  return bigint_cnd_add(cnd, x, size, y, size);
84  }
85 
86 /*
87 * If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow
88 * Runs in constant time
89 */
90 inline word bigint_cnd_sub(word cnd,
91  word x[], size_t x_size,
92  const word y[], size_t y_size)
93  {
94  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
95 
96  const auto mask = CT::Mask<word>::expand(cnd);
97 
98  word carry = 0;
99 
100  const size_t blocks = y_size - (y_size % 8);
101  word z[8] = { 0 };
102 
103  for(size_t i = 0; i != blocks; i += 8)
104  {
105  carry = word8_sub3(z, x + i, y + i, carry);
106  mask.select_n(x + i, z, x + i, 8);
107  }
108 
109  for(size_t i = blocks; i != y_size; ++i)
110  {
111  z[0] = word_sub(x[i], y[i], &carry);
112  x[i] = mask.select(z[0], x[i]);
113  }
114 
115  for(size_t i = y_size; i != x_size; ++i)
116  {
117  z[0] = word_sub(x[i], 0, &carry);
118  x[i] = mask.select(z[0], x[i]);
119  }
120 
121  return mask.if_set_return(carry);
122  }
123 
124 /*
125 * If cond > 0 adds x[0:size] and y[0:size] and returns carry
126 * Runs in constant time
127 */
128 inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
129  {
130  return bigint_cnd_sub(cnd, x, size, y, size);
131  }
132 
133 
134 /*
135 * Equivalent to
136 * bigint_cnd_add( mask, x, y, size);
137 * bigint_cnd_sub(~mask, x, y, size);
138 *
139 * Mask must be either 0 or all 1 bits
140 */
141 inline void bigint_cnd_add_or_sub(CT::Mask<word> mask, word x[], const word y[], size_t size)
142  {
143  const size_t blocks = size - (size % 8);
144 
145  word carry = 0;
146  word borrow = 0;
147 
148  word t0[8] = { 0 };
149  word t1[8] = { 0 };
150 
151  for(size_t i = 0; i != blocks; i += 8)
152  {
153  carry = word8_add3(t0, x + i, y + i, carry);
154  borrow = word8_sub3(t1, x + i, y + i, borrow);
155 
156  for(size_t j = 0; j != 8; ++j)
157  x[i+j] = mask.select(t0[j], t1[j]);
158  }
159 
160  for(size_t i = blocks; i != size; ++i)
161  {
162  const word a = word_add(x[i], y[i], &carry);
163  const word s = word_sub(x[i], y[i], &borrow);
164 
165  x[i] = mask.select(a, s);
166  }
167  }
168 
169 /*
170 * Equivalent to
171 * bigint_cnd_add( mask, x, size, y, size);
172 * bigint_cnd_sub(~mask, x, size, z, size);
173 *
174 * Mask must be either 0 or all 1 bits
175 *
176 * Returns the carry or borrow resp
177 */
178 inline word bigint_cnd_addsub(CT::Mask<word> mask, word x[],
179  const word y[], const word z[],
180  size_t size)
181  {
182  const size_t blocks = size - (size % 8);
183 
184  word carry = 0;
185  word borrow = 0;
186 
187  word t0[8] = { 0 };
188  word t1[8] = { 0 };
189 
190  for(size_t i = 0; i != blocks; i += 8)
191  {
192  carry = word8_add3(t0, x + i, y + i, carry);
193  borrow = word8_sub3(t1, x + i, z + i, borrow);
194 
195  for(size_t j = 0; j != 8; ++j)
196  x[i+j] = mask.select(t0[j], t1[j]);
197  }
198 
199  for(size_t i = blocks; i != size; ++i)
200  {
201  t0[0] = word_add(x[i], y[i], &carry);
202  t1[0] = word_sub(x[i], z[i], &borrow);
203  x[i] = mask.select(t0[0], t1[0]);
204  }
205 
206  return mask.select(carry, borrow);
207  }
208 
209 /*
210 * 2s complement absolute value
211 * If cond > 0 sets x to ~x + 1
212 * Runs in constant time
213 */
214 inline void bigint_cnd_abs(word cnd, word x[], size_t size)
215  {
216  const auto mask = CT::Mask<word>::expand(cnd);
217 
218  word carry = mask.if_set_return(1);
219  for(size_t i = 0; i != size; ++i)
220  {
221  const word z = word_add(~x[i], 0, &carry);
222  x[i] = mask.select(z, x[i]);
223  }
224  }
225 
226 /**
227 * Two operand addition with carry out
228 */
229 inline word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
230  {
231  word carry = 0;
232 
233  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
234 
235  const size_t blocks = y_size - (y_size % 8);
236 
237  for(size_t i = 0; i != blocks; i += 8)
238  carry = word8_add2(x + i, y + i, carry);
239 
240  for(size_t i = blocks; i != y_size; ++i)
241  x[i] = word_add(x[i], y[i], &carry);
242 
243  for(size_t i = y_size; i != x_size; ++i)
244  x[i] = word_add(x[i], 0, &carry);
245 
246  return carry;
247  }
248 
249 /**
250 * Three operand addition with carry out
251 */
252 inline word bigint_add3_nc(word z[],
253  const word x[], size_t x_size,
254  const word y[], size_t y_size)
255  {
256  if(x_size < y_size)
257  { return bigint_add3_nc(z, y, y_size, x, x_size); }
258 
259  word carry = 0;
260 
261  const size_t blocks = y_size - (y_size % 8);
262 
263  for(size_t i = 0; i != blocks; i += 8)
264  carry = word8_add3(z + i, x + i, y + i, carry);
265 
266  for(size_t i = blocks; i != y_size; ++i)
267  z[i] = word_add(x[i], y[i], &carry);
268 
269  for(size_t i = y_size; i != x_size; ++i)
270  z[i] = word_add(x[i], 0, &carry);
271 
272  return carry;
273  }
274 
275 /**
276 * Two operand addition
277 * @param x the first operand (and output)
278 * @param x_size size of x
279 * @param y the second operand
280 * @param y_size size of y (must be >= x_size)
281 */
282 inline void bigint_add2(word x[], size_t x_size,
283  const word y[], size_t y_size)
284  {
285  x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
286  }
287 
288 /**
289 * Three operand addition
290 */
291 inline void bigint_add3(word z[],
292  const word x[], size_t x_size,
293  const word y[], size_t y_size)
294  {
295  z[x_size > y_size ? x_size : y_size] +=
296  bigint_add3_nc(z, x, x_size, y, y_size);
297  }
298 
299 /**
300 * Two operand subtraction
301 */
302 inline word bigint_sub2(word x[], size_t x_size,
303  const word y[], size_t y_size)
304  {
305  word borrow = 0;
306 
307  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
308 
309  const size_t blocks = y_size - (y_size % 8);
310 
311  for(size_t i = 0; i != blocks; i += 8)
312  borrow = word8_sub2(x + i, y + i, borrow);
313 
314  for(size_t i = blocks; i != y_size; ++i)
315  x[i] = word_sub(x[i], y[i], &borrow);
316 
317  for(size_t i = y_size; i != x_size; ++i)
318  x[i] = word_sub(x[i], 0, &borrow);
319 
320  return borrow;
321  }
322 
323 /**
324 * Two operand subtraction, x = y - x; assumes y >= x
325 */
326 inline void bigint_sub2_rev(word x[], const word y[], size_t y_size)
327  {
328  word borrow = 0;
329 
330  const size_t blocks = y_size - (y_size % 8);
331 
332  for(size_t i = 0; i != blocks; i += 8)
333  borrow = word8_sub2_rev(x + i, y + i, borrow);
334 
335  for(size_t i = blocks; i != y_size; ++i)
336  x[i] = word_sub(y[i], x[i], &borrow);
337 
338  BOTAN_ASSERT(borrow == 0, "y must be greater than x");
339  }
340 
341 /**
342 * Three operand subtraction
343 */
344 inline word bigint_sub3(word z[],
345  const word x[], size_t x_size,
346  const word y[], size_t y_size)
347  {
348  word borrow = 0;
349 
350  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
351 
352  const size_t blocks = y_size - (y_size % 8);
353 
354  for(size_t i = 0; i != blocks; i += 8)
355  borrow = word8_sub3(z + i, x + i, y + i, borrow);
356 
357  for(size_t i = blocks; i != y_size; ++i)
358  z[i] = word_sub(x[i], y[i], &borrow);
359 
360  for(size_t i = y_size; i != x_size; ++i)
361  z[i] = word_sub(x[i], 0, &borrow);
362 
363  return borrow;
364  }
365 
366 /**
367 * Return abs(x-y), ie if x >= y, then compute z = x - y
368 * Otherwise compute z = y - x
369 * No borrow is possible since the result is always >= 0
370 *
371 * Returns ~0 if x >= y or 0 if x < y
372 * @param z output array of at least N words
373 * @param x input array of N words
374 * @param y input array of N words
375 * @param N length of x and y
376 * @param ws array of at least 2*N words
377 */
378 inline CT::Mask<word>
379 bigint_sub_abs(word z[],
380  const word x[], const word y[], size_t N,
381  word ws[])
382  {
383  // Subtract in both direction then conditional copy out the result
384 
385  word* ws0 = ws;
386  word* ws1 = ws + N;
387 
388  word borrow0 = 0;
389  word borrow1 = 0;
390 
391  const size_t blocks = N - (N % 8);
392 
393  for(size_t i = 0; i != blocks; i += 8)
394  {
395  borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
396  borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
397  }
398 
399  for(size_t i = blocks; i != N; ++i)
400  {
401  ws0[i] = word_sub(x[i], y[i], &borrow0);
402  ws1[i] = word_sub(y[i], x[i], &borrow1);
403  }
404 
405  return CT::conditional_copy_mem(borrow0, z, ws1, ws0, N);
406  }
407 
408 /*
409 * Shift Operations
410 */
411 inline void bigint_shl1(word x[], size_t x_size, size_t x_words,
412  size_t word_shift, size_t bit_shift)
413  {
414  copy_mem(x + word_shift, x, x_words);
415  clear_mem(x, word_shift);
416 
417  const auto carry_mask = CT::Mask<word>::expand(bit_shift);
418  const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
419 
420  word carry = 0;
421  for(size_t i = word_shift; i != x_size; ++i)
422  {
423  const word w = x[i];
424  x[i] = (w << bit_shift) | carry;
425  carry = carry_mask.if_set_return(w >> carry_shift);
426  }
427  }
428 
429 inline void bigint_shr1(word x[], size_t x_size,
430  size_t word_shift, size_t bit_shift)
431  {
432  const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
433 
434  copy_mem(x, x + word_shift, top);
435  clear_mem(x + top, std::min(word_shift, x_size));
436 
437  const auto carry_mask = CT::Mask<word>::expand(bit_shift);
438  const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
439 
440  word carry = 0;
441 
442  for(size_t i = 0; i != top; ++i)
443  {
444  const word w = x[top - i - 1];
445  x[top-i-1] = (w >> bit_shift) | carry;
446  carry = carry_mask.if_set_return(w << carry_shift);
447  }
448  }
449 
450 inline void bigint_shl2(word y[], const word x[], size_t x_size,
451  size_t word_shift, size_t bit_shift)
452  {
453  copy_mem(y + word_shift, x, x_size);
454 
455  const auto carry_mask = CT::Mask<word>::expand(bit_shift);
456  const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
457 
458  word carry = 0;
459  for(size_t i = word_shift; i != x_size + word_shift + 1; ++i)
460  {
461  const word w = y[i];
462  y[i] = (w << bit_shift) | carry;
463  carry = carry_mask.if_set_return(w >> carry_shift);
464  }
465  }
466 
467 inline void bigint_shr2(word y[], const word x[], size_t x_size,
468  size_t word_shift, size_t bit_shift)
469  {
470  const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
471 
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
488 */
489 inline void 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  x[x_size] = 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  CT::conditional_swap_ptr(relative_size < 0, x, y);
662  CT::conditional_swap(relative_size < 0, x_size, y_size);
663 
664  /*
665  * We know at this point that x >= y so if y_size is larger than
666  * x_size, we are guaranteed they are just leading zeros which can
667  * be ignored
668  */
669  y_size = std::min(x_size, y_size);
670 
671  bigint_sub3(z, x, x_size, y, y_size);
672 
673  return relative_size;
674  }
675 
676 /**
677 * Set t to t-s modulo mod
678 *
679 * @param t first integer
680 * @param s second integer
681 * @param mod the modulus
682 * @param mod_sw size of t, s, and mod
683 * @param ws workspace of size mod_sw
684 */
685 inline void
686 bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
687  {
688  // is t < s or not?
689  const auto is_lt = bigint_ct_is_lt(t, mod_sw, s, mod_sw);
690 
691  // ws = p - s
692  const word borrow = bigint_sub3(ws, mod, mod_sw, s, mod_sw);
693 
694  // Compute either (t - s) or (t + (p - s)) depending on mask
695  const word carry = bigint_cnd_addsub(is_lt, t, ws, s, mod_sw);
696 
697  BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
698  BOTAN_UNUSED(carry, borrow);
699  }
700 
701 template<size_t N>
702 inline void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
703  {
704  // is t < s or not?
705  const auto is_lt = bigint_ct_is_lt(t, N, s, N);
706 
707  // ws = p - s
708  const word borrow = bigint_sub3(ws, mod, N, s, N);
709 
710  // Compute either (t - s) or (t + (p - s)) depending on mask
711  const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N);
712 
713  BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
714  BOTAN_UNUSED(carry, borrow);
715  }
716 
717 /**
718 * Compute ((n1<<bits) + n0) / d
719 */
720 inline word bigint_divop(word n1, word n0, word d)
721  {
722  if(d == 0)
723  throw Invalid_Argument("bigint_divop divide by zero");
724 
725 #if defined(BOTAN_HAS_MP_DWORD)
726  return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) / d;
727 #else
728 
729  word high = n1 % d;
730  word quotient = 0;
731 
732  for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
733  {
734  word high_top_bit = (high & MP_WORD_TOP_BIT);
735 
736  high <<= 1;
737  high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1;
738  quotient <<= 1;
739 
740  if(high_top_bit || high >= d)
741  {
742  high -= d;
743  quotient |= 1;
744  }
745  }
746 
747  return quotient;
748 #endif
749  }
750 
751 /**
752 * Compute ((n1<<bits) + n0) % d
753 */
754 inline word bigint_modop(word n1, word n0, word d)
755  {
756  if(d == 0)
757  throw Invalid_Argument("bigint_modop divide by zero");
758 
759 #if defined(BOTAN_HAS_MP_DWORD)
760  return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) % d;
761 #else
762  word z = bigint_divop(n1, n0, d);
763  word dummy = 0;
764  z = word_madd2(z, d, &dummy);
765  return (n0-z);
766 #endif
767  }
768 
769 /*
770 * Comba Multiplication / Squaring
771 */
772 void bigint_comba_mul4(word z[8], const word x[4], const word y[4]);
773 void bigint_comba_mul6(word z[12], const word x[6], const word y[6]);
774 void bigint_comba_mul8(word z[16], const word x[8], const word y[8]);
775 void bigint_comba_mul9(word z[18], const word x[9], const word y[9]);
776 void bigint_comba_mul16(word z[32], const word x[16], const word y[16]);
777 void bigint_comba_mul24(word z[48], const word x[24], const word y[24]);
778 
779 void bigint_comba_sqr4(word out[8], const word in[4]);
780 void bigint_comba_sqr6(word out[12], const word in[6]);
781 void bigint_comba_sqr8(word out[16], const word in[8]);
782 void bigint_comba_sqr9(word out[18], const word in[9]);
783 void bigint_comba_sqr16(word out[32], const word in[16]);
784 void bigint_comba_sqr24(word out[48], const word in[24]);
785 
786 /**
787 * Montgomery Reduction
788 * @param z integer to reduce, of size exactly 2*(p_size+1).
789  Output is in the first p_size+1 words, higher
790  words are set to zero.
791 * @param p modulus
792 * @param p_size size of p
793 * @param p_dash Montgomery value
794 * @param workspace array of at least 2*(p_size+1) words
795 * @param ws_size size of workspace in words
796 */
797 void bigint_monty_redc(word z[],
798  const word p[], size_t p_size,
799  word p_dash,
800  word workspace[],
801  size_t ws_size);
802 
803 /*
804 * High Level Multiplication/Squaring Interfaces
805 */
806 
807 void bigint_mul(word z[], size_t z_size,
808  const word x[], size_t x_size, size_t x_sw,
809  const word y[], size_t y_size, size_t y_sw,
810  word workspace[], size_t ws_size);
811 
812 void bigint_sqr(word z[], size_t z_size,
813  const word x[], size_t x_size, size_t x_sw,
814  word workspace[], size_t ws_size);
815 
816 }
817 
818 #endif
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:429
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:326
word word8_sub2_rev(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:381
void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition: ct_utils.h:362
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:585
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:467
void carry(int64_t &h0, int64_t &h1)
void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
Definition: mp_core.h:702
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:111
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:302
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:489
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:252
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
Definition: mp_comba.cpp:50
word word8_sub2(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:311
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:344
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.h:720
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:178
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:52
#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:90
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:411
#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:379
T select(T x, T y) const
Definition: ct_utils.h:264
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:31
word word8_linmul2(word x[8], word y, word carry)
Definition: mp_asmi.h:488
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
Definition: mp_core.h:44
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:229
void bigint_cnd_add_or_sub(CT::Mask< word > mask, word x[], const word y[], size_t size)
Definition: mp_core.h:141
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:122
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:339
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:200
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:450
const word MP_WORD_MASK
Definition: mp_core.h:22
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:24
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:280
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:282
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:214
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:416
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:686
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
const word MP_WORD_TOP_BIT
Definition: mp_core.h:23
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:291
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:754
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:351