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