Botan  2.6.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_abs(word cnd, word x[], size_t size)
96  {
97  const word mask = CT::expand_mask(cnd);
98 
99  word carry = mask & 1;
100  for(size_t i = 0; i != size; ++i)
101  {
102  const word z = word_add(~x[i], 0, &carry);
103  x[i] = CT::select(mask, z, x[i]);
104  }
105  }
106 
107 /*
108 * Two Operand Addition, No Carry
109 */
110 word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
111  {
112  word carry = 0;
113 
114  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
115 
116  const size_t blocks = y_size - (y_size % 8);
117 
118  for(size_t i = 0; i != blocks; i += 8)
119  carry = word8_add2(x + i, y + i, carry);
120 
121  for(size_t i = blocks; i != y_size; ++i)
122  x[i] = word_add(x[i], y[i], &carry);
123 
124  for(size_t i = y_size; i != x_size; ++i)
125  x[i] = word_add(x[i], 0, &carry);
126 
127  return carry;
128  }
129 
130 /*
131 * Three Operand Addition, No Carry
132 */
133 word bigint_add3_nc(word z[], const word x[], size_t x_size,
134  const word y[], size_t y_size)
135  {
136  if(x_size < y_size)
137  { return bigint_add3_nc(z, y, y_size, x, x_size); }
138 
139  word carry = 0;
140 
141  const size_t blocks = y_size - (y_size % 8);
142 
143  for(size_t i = 0; i != blocks; i += 8)
144  carry = word8_add3(z + i, x + i, y + i, carry);
145 
146  for(size_t i = blocks; i != y_size; ++i)
147  z[i] = word_add(x[i], y[i], &carry);
148 
149  for(size_t i = y_size; i != x_size; ++i)
150  z[i] = word_add(x[i], 0, &carry);
151 
152  return carry;
153  }
154 
155 /*
156 * Two Operand Addition
157 */
158 void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
159  {
160  if(bigint_add2_nc(x, x_size, y, y_size))
161  x[x_size] += 1;
162  }
163 
164 /*
165 * Three Operand Addition
166 */
167 void bigint_add3(word z[], const word x[], size_t x_size,
168  const word y[], size_t y_size)
169  {
170  z[x_size > y_size ? x_size : y_size] +=
171  bigint_add3_nc(z, x, x_size, y, y_size);
172  }
173 
174 /*
175 * Two Operand Subtraction
176 */
177 word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
178  {
179  word borrow = 0;
180 
181  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
182 
183  const size_t blocks = y_size - (y_size % 8);
184 
185  for(size_t i = 0; i != blocks; i += 8)
186  borrow = word8_sub2(x + i, y + i, borrow);
187 
188  for(size_t i = blocks; i != y_size; ++i)
189  x[i] = word_sub(x[i], y[i], &borrow);
190 
191  for(size_t i = y_size; i != x_size; ++i)
192  x[i] = word_sub(x[i], 0, &borrow);
193 
194  return borrow;
195  }
196 
197 /*
198 * Two Operand Subtraction x = y - x
199 */
200 void bigint_sub2_rev(word x[], const word y[], size_t y_size)
201  {
202  word borrow = 0;
203 
204  const size_t blocks = y_size - (y_size % 8);
205 
206  for(size_t i = 0; i != blocks; i += 8)
207  borrow = word8_sub2_rev(x + i, y + i, borrow);
208 
209  for(size_t i = blocks; i != y_size; ++i)
210  x[i] = word_sub(y[i], x[i], &borrow);
211 
212  BOTAN_ASSERT(!borrow, "y must be greater than x");
213  }
214 
215 /*
216 * Three Operand Subtraction
217 */
218 word bigint_sub3(word z[], const word x[], size_t x_size,
219  const word y[], size_t y_size)
220  {
221  word borrow = 0;
222 
223  BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
224 
225  const size_t blocks = y_size - (y_size % 8);
226 
227  for(size_t i = 0; i != blocks; i += 8)
228  borrow = word8_sub3(z + i, x + i, y + i, borrow);
229 
230  for(size_t i = blocks; i != y_size; ++i)
231  z[i] = word_sub(x[i], y[i], &borrow);
232 
233  for(size_t i = y_size; i != x_size; ++i)
234  z[i] = word_sub(x[i], 0, &borrow);
235 
236  return borrow;
237  }
238 
239 /*
240 * Two Operand Linear Multiply
241 */
242 void bigint_linmul2(word x[], size_t x_size, word y)
243  {
244  const size_t blocks = x_size - (x_size % 8);
245 
246  word carry = 0;
247 
248  for(size_t i = 0; i != blocks; i += 8)
249  carry = word8_linmul2(x + i, y, carry);
250 
251  for(size_t i = blocks; i != x_size; ++i)
252  x[i] = word_madd2(x[i], y, &carry);
253 
254  x[x_size] = carry;
255  }
256 
257 /*
258 * Three Operand Linear Multiply
259 */
260 void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
261  {
262  const size_t blocks = x_size - (x_size % 8);
263 
264  word carry = 0;
265 
266  for(size_t i = 0; i != blocks; i += 8)
267  carry = word8_linmul3(z + i, x + i, y, carry);
268 
269  for(size_t i = blocks; i != x_size; ++i)
270  z[i] = word_madd2(x[i], y, &carry);
271 
272  z[x_size] = carry;
273  }
274 
275 /*
276 * Single Operand Left Shift
277 */
278 void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
279  {
280  if(word_shift)
281  {
282  copy_mem(x + word_shift, x, x_size);
283  clear_mem(x, word_shift);
284  }
285 
286  if(bit_shift)
287  {
288  word carry = 0;
289  for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
290  {
291  word temp = x[j];
292  x[j] = (temp << bit_shift) | carry;
293  carry = (temp >> (BOTAN_MP_WORD_BITS - bit_shift));
294  }
295  }
296  }
297 
298 /*
299 * Single Operand Right Shift
300 */
301 void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
302  {
303  if(x_size < word_shift)
304  {
305  clear_mem(x, x_size);
306  return;
307  }
308 
309  if(word_shift)
310  {
311  copy_mem(x, x + word_shift, x_size - word_shift);
312  clear_mem(x + x_size - word_shift, word_shift);
313  }
314 
315  if(bit_shift)
316  {
317  word carry = 0;
318 
319  size_t top = x_size - word_shift;
320 
321  while(top >= 4)
322  {
323  word w = x[top-1];
324  x[top-1] = (w >> bit_shift) | carry;
325  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
326 
327  w = x[top-2];
328  x[top-2] = (w >> bit_shift) | carry;
329  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
330 
331  w = x[top-3];
332  x[top-3] = (w >> bit_shift) | carry;
333  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
334 
335  w = x[top-4];
336  x[top-4] = (w >> bit_shift) | carry;
337  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
338 
339  top -= 4;
340  }
341 
342  while(top)
343  {
344  word w = x[top-1];
345  x[top-1] = (w >> bit_shift) | carry;
346  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
347 
348  top--;
349  }
350  }
351  }
352 
353 /*
354 * Two Operand Left Shift
355 */
356 void bigint_shl2(word y[], const word x[], size_t x_size,
357  size_t word_shift, size_t bit_shift)
358  {
359  for(size_t j = 0; j != x_size; ++j)
360  y[j + word_shift] = x[j];
361  if(bit_shift)
362  {
363  word carry = 0;
364  for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
365  {
366  word w = y[j];
367  y[j] = (w << bit_shift) | carry;
368  carry = (w >> (BOTAN_MP_WORD_BITS - bit_shift));
369  }
370  }
371  }
372 
373 /*
374 * Two Operand Right Shift
375 */
376 void bigint_shr2(word y[], const word x[], size_t x_size,
377  size_t word_shift, size_t bit_shift)
378  {
379  if(x_size < word_shift) return;
380 
381  for(size_t j = 0; j != x_size - word_shift; ++j)
382  y[j] = x[j + word_shift];
383  if(bit_shift)
384  {
385  word carry = 0;
386  for(size_t j = x_size - word_shift; j > 0; --j)
387  {
388  word w = y[j-1];
389  y[j-1] = (w >> bit_shift) | carry;
390  carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
391  }
392  }
393  }
394 
395 /*
396 * Compare two MP integers
397 */
398 int32_t bigint_cmp(const word x[], size_t x_size,
399  const word y[], size_t y_size)
400  {
401  if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
402 
403  while(x_size > y_size)
404  {
405  if(x[x_size-1])
406  return 1;
407  x_size--;
408  }
409 
410  for(size_t i = x_size; i > 0; --i)
411  {
412  if(x[i-1] > y[i-1])
413  return 1;
414  if(x[i-1] < y[i-1])
415  return -1;
416  }
417 
418  return 0;
419  }
420 
421 /*
422 * Do a 2-word/1-word Division
423 */
424 word bigint_divop(word n1, word n0, word d)
425  {
426  if(d == 0)
427  throw Invalid_Argument("bigint_divop divide by zero");
428 
429 #if defined(BOTAN_HAS_MP_DWORD)
430  return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) / d;
431 #else
432 
433  word high = n1 % d, quotient = 0;
434 
435  for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
436  {
437  word high_top_bit = (high & MP_WORD_TOP_BIT);
438 
439  high <<= 1;
440  high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1;
441  quotient <<= 1;
442 
443  if(high_top_bit || high >= d)
444  {
445  high -= d;
446  quotient |= 1;
447  }
448  }
449 
450  return quotient;
451 #endif
452  }
453 
454 /*
455 * Do a 2-word/1-word Modulo
456 */
457 word bigint_modop(word n1, word n0, word d)
458  {
459 #if defined(BOTAN_HAS_MP_DWORD)
460  return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) % d;
461 #else
462  word z = bigint_divop(n1, n0, d);
463  word dummy = 0;
464  z = word_madd2(z, d, &dummy);
465  return (n0-z);
466 #endif
467  }
468 
469 }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:301
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.cpp:200
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:376
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:398
void bigint_cnd_abs(word cnd, word x[], size_t size)
Definition: mp_core.cpp:95
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:177
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.cpp:242
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:133
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:218
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.cpp:424
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:59
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:30
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.cpp:260
T expand_mask(T x)
Definition: ct_utils.h:86
word word8_linmul2(word x[8], word y, word carry)
Definition: mp_asmi.h:488
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:106
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:110
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:356
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:278
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:158
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:167
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:457