Botan  2.8.0
Crypto and TLS for C++11
mp_core.cpp
Go to the documentation of this file.
1 /*
2 * MPI Add, Subtract, Word Multiply
3 * (C) 1999-2010,2016 Jack Lloyd
4 * 2006 Luca Piccarreta
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8 
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/mp_asmi.h>
11 #include <botan/internal/ct_utils.h>
12 #include <botan/exceptn.h>
13 #include <botan/mem_ops.h>
14 
15 namespace Botan {
16 
17 /*
18 * If cond == 0, does nothing.
19 * If cond > 0, swaps x[0:size] with y[0:size]
20 * Runs in constant time
21 */
22 void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
23  {
24  const word mask = CT::expand_mask(cnd);
25 
26  for(size_t i = 0; i != size; ++i)
27  {
28  const word a = x[i];
29  const word b = y[i];
30  x[i] = CT::select(mask, b, a);
31  y[i] = CT::select(mask, a, b);
32  }
33  }
34 
35 /*
36 * If cond > 0 adds x[0:size] to y[0:size] and returns carry
37 * Runs in constant time
38 */
39 word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
40  {
41  const word mask = CT::expand_mask(cnd);
42 
43  word carry = 0;
44 
45  const size_t blocks = size - (size % 8);
46  word z[8] = { 0 };
47 
48  for(size_t i = 0; i != blocks; i += 8)
49  {
50  carry = word8_add3(z, x + i, y + i, carry);
51 
52  for(size_t j = 0; j != 8; ++j)
53  x[i+j] = CT::select(mask, z[j], x[i+j]);
54  }
55 
56  for(size_t i = blocks; i != size; ++i)
57  {
58  z[0] = word_add(x[i], y[i], &carry);
59  x[i] = CT::select(mask, z[0], x[i]);
60  }
61 
62  return carry & mask;
63  }
64 
65 /*
66 * If cond > 0 subs x[0:size] to y[0:size] and returns borrow
67 * Runs in constant time
68 */
69 word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
70  {
71  const word mask = CT::expand_mask(cnd);
72 
73  word carry = 0;
74 
75  const size_t blocks = size - (size % 8);
76  word z[8] = { 0 };
77 
78  for(size_t i = 0; i != blocks; i += 8)
79  {
80  carry = word8_sub3(z, x + i, y + i, carry);
81 
82  for(size_t j = 0; j != 8; ++j)
83  x[i+j] = CT::select(mask, z[j], x[i+j]);
84  }
85 
86  for(size_t i = blocks; i != size; ++i)
87  {
88  z[0] = word_sub(x[i], y[i], &carry);
89  x[i] = CT::select(mask, z[0], x[i]);
90  }
91 
92  return carry & mask;
93  }
94 
95 void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size)
96  {
97  const size_t blocks = size - (size % 8);
98 
99  word carry = 0;
100  word borrow = 0;
101 
102  word t0[8] = { 0 };
103  word t1[8] = { 0 };
104 
105  for(size_t i = 0; i != blocks; i += 8)
106  {
107  carry = word8_add3(t0, x + i, y + i, carry);
108  borrow = word8_sub3(t1, x + i, y + i, borrow);
109 
110  for(size_t j = 0; j != 8; ++j)
111  x[i+j] = CT::select(mask, t0[j], t1[j]);
112  }
113 
114  for(size_t i = blocks; i != size; ++i)
115  {
116  const word a = word_add(x[i], y[i], &carry);
117  const word s = word_sub(x[i], y[i], &borrow);
118 
119  x[i] = CT::select(mask, a, s);
120  }
121  }
122 
123 void bigint_cnd_abs(word cnd, word x[], size_t size)
124  {
125  const word mask = CT::expand_mask(cnd);
126 
127  word carry = mask & 1;
128  for(size_t i = 0; i != size; ++i)
129  {
130  const word z = word_add(~x[i], 0, &carry);
131  x[i] = CT::select(mask, z, x[i]);
132  }
133  }
134 
135 /*
136 * Two Operand Addition, No Carry
137 */
138 word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
139  {
140  word carry = 0;
141 
142  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
143 
144  const size_t blocks = y_size - (y_size % 8);
145 
146  for(size_t i = 0; i != blocks; i += 8)
147  carry = word8_add2(x + i, y + i, carry);
148 
149  for(size_t i = blocks; i != y_size; ++i)
150  x[i] = word_add(x[i], y[i], &carry);
151 
152  for(size_t i = y_size; i != x_size; ++i)
153  x[i] = word_add(x[i], 0, &carry);
154 
155  return carry;
156  }
157 
158 /*
159 * Three Operand Addition, No Carry
160 */
161 word bigint_add3_nc(word z[], const word x[], size_t x_size,
162  const word y[], size_t y_size)
163  {
164  if(x_size < y_size)
165  { return bigint_add3_nc(z, y, y_size, x, x_size); }
166 
167  word carry = 0;
168 
169  const size_t blocks = y_size - (y_size % 8);
170 
171  for(size_t i = 0; i != blocks; i += 8)
172  carry = word8_add3(z + i, x + i, y + i, carry);
173 
174  for(size_t i = blocks; i != y_size; ++i)
175  z[i] = word_add(x[i], y[i], &carry);
176 
177  for(size_t i = y_size; i != x_size; ++i)
178  z[i] = word_add(x[i], 0, &carry);
179 
180  return carry;
181  }
182 
183 /*
184 * Two Operand Addition
185 */
186 void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
187  {
188  x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
189  }
190 
191 /*
192 * Three Operand Addition
193 */
194 void bigint_add3(word z[], const word x[], size_t x_size,
195  const word y[], size_t y_size)
196  {
197  z[x_size > y_size ? x_size : y_size] +=
198  bigint_add3_nc(z, x, x_size, y, y_size);
199  }
200 
201 /*
202 * Two Operand Subtraction
203 */
204 word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
205  {
206  word borrow = 0;
207 
208  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
209 
210  const size_t blocks = y_size - (y_size % 8);
211 
212  for(size_t i = 0; i != blocks; i += 8)
213  borrow = word8_sub2(x + i, y + i, borrow);
214 
215  for(size_t i = blocks; i != y_size; ++i)
216  x[i] = word_sub(x[i], y[i], &borrow);
217 
218  for(size_t i = y_size; i != x_size; ++i)
219  x[i] = word_sub(x[i], 0, &borrow);
220 
221  return borrow;
222  }
223 
224 /*
225 * Two Operand Subtraction x = y - x
226 */
227 void bigint_sub2_rev(word x[], const word y[], size_t y_size)
228  {
229  word borrow = 0;
230 
231  const size_t blocks = y_size - (y_size % 8);
232 
233  for(size_t i = 0; i != blocks; i += 8)
234  borrow = word8_sub2_rev(x + i, y + i, borrow);
235 
236  for(size_t i = blocks; i != y_size; ++i)
237  x[i] = word_sub(y[i], x[i], &borrow);
238 
239  BOTAN_ASSERT(!borrow, "y must be greater than x");
240  }
241 
242 word bigint_sub_abs(word z[],
243  const word x[], const word y[], size_t N,
244  word ws[])
245  {
246  // Subtract in both direction then conditional copy out the result
247 
248  word* ws0 = ws;
249  word* ws1 = ws + N;
250 
251  word borrow0 = 0;
252  word borrow1 = 0;
253 
254  const size_t blocks = N - (N % 8);
255 
256  for(size_t i = 0; i != blocks; i += 8)
257  {
258  borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
259  borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
260  }
261 
262  for(size_t i = blocks; i != N; ++i)
263  {
264  ws0[i] = word_sub(x[i], y[i], &borrow0);
265  ws1[i] = word_sub(y[i], x[i], &borrow1);
266  }
267 
268  word mask = CT::conditional_copy_mem(borrow1, z, ws0, ws1, N);
269 
270  return CT::select<word>(mask, 0, 1);
271  }
272 
273 /*
274 * Three Operand Subtraction
275 */
276 word bigint_sub3(word z[], const word x[], size_t x_size,
277  const word y[], size_t y_size)
278  {
279  word borrow = 0;
280 
281  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
282 
283  const size_t blocks = y_size - (y_size % 8);
284 
285  for(size_t i = 0; i != blocks; i += 8)
286  borrow = word8_sub3(z + i, x + i, y + i, borrow);
287 
288  for(size_t i = blocks; i != y_size; ++i)
289  z[i] = word_sub(x[i], y[i], &borrow);
290 
291  for(size_t i = y_size; i != x_size; ++i)
292  z[i] = word_sub(x[i], 0, &borrow);
293 
294  return borrow;
295  }
296 
297 /*
298 * Two Operand Linear Multiply
299 */
300 void bigint_linmul2(word x[], size_t x_size, word y)
301  {
302  const size_t blocks = x_size - (x_size % 8);
303 
304  word carry = 0;
305 
306  for(size_t i = 0; i != blocks; i += 8)
307  carry = word8_linmul2(x + i, y, carry);
308 
309  for(size_t i = blocks; i != x_size; ++i)
310  x[i] = word_madd2(x[i], y, &carry);
311 
312  x[x_size] = carry;
313  }
314 
315 /*
316 * Three Operand Linear Multiply
317 */
318 void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
319  {
320  const size_t blocks = x_size - (x_size % 8);
321 
322  word carry = 0;
323 
324  for(size_t i = 0; i != blocks; i += 8)
325  carry = word8_linmul3(z + i, x + i, y, carry);
326 
327  for(size_t i = blocks; i != x_size; ++i)
328  z[i] = word_madd2(x[i], y, &carry);
329 
330  z[x_size] = carry;
331  }
332 
333 /*
334 * Single Operand Left Shift
335 */
336 void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
337  {
338  if(word_shift)
339  {
340  copy_mem(x + word_shift, x, x_size);
341  clear_mem(x, word_shift);
342  }
343 
344  if(bit_shift)
345  {
346  word carry = 0;
347  for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
348  {
349  word temp = x[j];
350  x[j] = (temp << bit_shift) | carry;
351  carry = (temp >> (BOTAN_MP_WORD_BITS - bit_shift));
352  }
353  }
354  }
355 
356 namespace {
357 
358 void bigint_shift_right_1(word x[], size_t x_size)
359  {
360  word carry = 0;
361  size_t top = x_size;
362 
363  while(top)
364  {
365  word w = x[top-1];
366  x[top-1] = (w >> 1) | carry;
367  carry = (w << (BOTAN_MP_WORD_BITS - 1));
368 
369  top--;
370  }
371  }
372 
373 }
374 
375 /*
376 * Single Operand Right Shift
377 */
378 void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
379  {
380  if(word_shift == 0 && bit_shift == 1)
381  return bigint_shift_right_1(x, x_size);
382 
383  if(x_size < word_shift)
384  {
385  clear_mem(x, x_size);
386  return;
387  }
388 
389  if(word_shift)
390  {
391  copy_mem(x, x + word_shift, x_size - word_shift);
392  clear_mem(x + x_size - word_shift, word_shift);
393  }
394 
395  if(bit_shift)
396  {
397  word carry = 0;
398 
399  size_t top = x_size - word_shift;
400 
401  while(top >= 4)
402  {
403  word w = x[top-1];
404  x[top-1] = (w >> bit_shift) | carry;
405  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
406 
407  w = x[top-2];
408  x[top-2] = (w >> bit_shift) | carry;
409  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
410 
411  w = x[top-3];
412  x[top-3] = (w >> bit_shift) | carry;
413  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
414 
415  w = x[top-4];
416  x[top-4] = (w >> bit_shift) | carry;
417  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
418 
419  top -= 4;
420  }
421 
422  while(top)
423  {
424  word w = x[top-1];
425  x[top-1] = (w >> bit_shift) | carry;
426  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
427 
428  top--;
429  }
430  }
431  }
432 
433 /*
434 * Two Operand Left Shift
435 */
436 void bigint_shl2(word y[], const word x[], size_t x_size,
437  size_t word_shift, size_t bit_shift)
438  {
439  for(size_t j = 0; j != x_size; ++j)
440  y[j + word_shift] = x[j];
441  if(bit_shift)
442  {
443  word carry = 0;
444  for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
445  {
446  word w = y[j];
447  y[j] = (w << bit_shift) | carry;
448  carry = (w >> (BOTAN_MP_WORD_BITS - bit_shift));
449  }
450  }
451  }
452 
453 /*
454 * Two Operand Right Shift
455 */
456 void bigint_shr2(word y[], const word x[], size_t x_size,
457  size_t word_shift, size_t bit_shift)
458  {
459  if(x_size < word_shift) return;
460 
461  for(size_t j = 0; j != x_size - word_shift; ++j)
462  y[j] = x[j + word_shift];
463  if(bit_shift)
464  {
465  word carry = 0;
466  for(size_t j = x_size - word_shift; j > 0; --j)
467  {
468  word w = y[j-1];
469  y[j-1] = (w >> bit_shift) | carry;
470  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
471  }
472  }
473  }
474 
475 /*
476 * Compare two MP integers
477 */
478 int32_t bigint_cmp(const word x[], size_t x_size,
479  const word y[], size_t y_size)
480  {
481  if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
482 
483  while(x_size > y_size)
484  {
485  if(x[x_size-1])
486  return 1;
487  x_size--;
488  }
489 
490  for(size_t i = x_size; i > 0; --i)
491  {
492  if(x[i-1] > y[i-1])
493  return 1;
494  if(x[i-1] < y[i-1])
495  return -1;
496  }
497 
498  return 0;
499  }
500 
501 /*
502 * Do a 2-word/1-word Division
503 */
504 word bigint_divop(word n1, word n0, word d)
505  {
506  if(d == 0)
507  throw Invalid_Argument("bigint_divop divide by zero");
508 
509 #if defined(BOTAN_HAS_MP_DWORD)
510  return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) / d;
511 #else
512 
513  word high = n1 % d, quotient = 0;
514 
515  for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
516  {
517  word high_top_bit = (high & MP_WORD_TOP_BIT);
518 
519  high <<= 1;
520  high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1;
521  quotient <<= 1;
522 
523  if(high_top_bit || high >= d)
524  {
525  high -= d;
526  quotient |= 1;
527  }
528  }
529 
530  return quotient;
531 #endif
532  }
533 
534 /*
535 * Do a 2-word/1-word Modulo
536 */
537 word bigint_modop(word n1, word n0, word d)
538  {
539 #if defined(BOTAN_HAS_MP_DWORD)
540  return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) % d;
541 #else
542  word z = bigint_divop(n1, n0, d);
543  word dummy = 0;
544  z = word_madd2(z, d, &dummy);
545  return (n0-z);
546 #endif
547  }
548 
549 }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:378
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.cpp:227
void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size)
Definition: mp_core.cpp:95
word word8_sub2_rev(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:381
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.cpp:456
void carry(int64_t &h0, int64_t &h1)
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:478
void bigint_cnd_abs(word cnd, word x[], size_t size)
Definition: mp_core.cpp:123
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:97
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:204
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.cpp:300
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:161
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.cpp:22
word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
Definition: mp_core.cpp:39
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.cpp:276
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.cpp:504
T conditional_copy_mem(T value, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:161
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.cpp:318
T expand_mask(T x)
Definition: ct_utils.h:103
word word8_linmul2(word x[8], word y, word carry)
Definition: mp_asmi.h:488
word bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.cpp:242
word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
Definition: mp_core.cpp:69
T select(T mask, T from0, T from1)
Definition: ct_utils.h:110
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:138
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:108
Definition: alg_id.cpp:13
word word8_add3(word z[8], const word x[8], const word y[8], word carry)
Definition: mp_asmi.h:200
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:436
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:336
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:280
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:186
word word_add(word x, word y, word *carry)
Definition: mp_asmi.h:107
word word8_sub3(word z[8], const word x[8], const word y[8], word carry)
Definition: mp_asmi.h:416
const word MP_WORD_TOP_BIT
Definition: mp_core.h:18
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:194
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:537