1 /*
2 * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #include <assert.h>
11 #include <openssl/crypto.h>
12 #include "internal/cryptlib.h"
13 #include "bn_local.h"
14
15 #if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
16
bn_mul_add_words(BN_ULONG * rp,const BN_ULONG * ap,int num,BN_ULONG w)17 BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num,
18 BN_ULONG w)
19 {
20 BN_ULONG c1 = 0;
21
22 assert(num >= 0);
23 if (num <= 0)
24 return c1;
25
26 #ifndef OPENSSL_SMALL_FOOTPRINT
27 while (num & ~3) {
28 mul_add(rp[0], ap[0], w, c1);
29 mul_add(rp[1], ap[1], w, c1);
30 mul_add(rp[2], ap[2], w, c1);
31 mul_add(rp[3], ap[3], w, c1);
32 ap += 4;
33 rp += 4;
34 num -= 4;
35 }
36 #endif
37 while (num) {
38 mul_add(rp[0], ap[0], w, c1);
39 ap++;
40 rp++;
41 num--;
42 }
43
44 return c1;
45 }
46
bn_mul_words(BN_ULONG * rp,const BN_ULONG * ap,int num,BN_ULONG w)47 BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
48 {
49 BN_ULONG c1 = 0;
50
51 assert(num >= 0);
52 if (num <= 0)
53 return c1;
54
55 #ifndef OPENSSL_SMALL_FOOTPRINT
56 while (num & ~3) {
57 mul(rp[0], ap[0], w, c1);
58 mul(rp[1], ap[1], w, c1);
59 mul(rp[2], ap[2], w, c1);
60 mul(rp[3], ap[3], w, c1);
61 ap += 4;
62 rp += 4;
63 num -= 4;
64 }
65 #endif
66 while (num) {
67 mul(rp[0], ap[0], w, c1);
68 ap++;
69 rp++;
70 num--;
71 }
72 return c1;
73 }
74
bn_sqr_words(BN_ULONG * r,const BN_ULONG * a,int n)75 void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
76 {
77 assert(n >= 0);
78 if (n <= 0)
79 return;
80
81 #ifndef OPENSSL_SMALL_FOOTPRINT
82 while (n & ~3) {
83 sqr(r[0], r[1], a[0]);
84 sqr(r[2], r[3], a[1]);
85 sqr(r[4], r[5], a[2]);
86 sqr(r[6], r[7], a[3]);
87 a += 4;
88 r += 8;
89 n -= 4;
90 }
91 #endif
92 while (n) {
93 sqr(r[0], r[1], a[0]);
94 a++;
95 r += 2;
96 n--;
97 }
98 }
99
100 #else /* !(defined(BN_LLONG) || \
101 * defined(BN_UMULT_HIGH)) */
102
bn_mul_add_words(BN_ULONG * rp,const BN_ULONG * ap,int num,BN_ULONG w)103 BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num,
104 BN_ULONG w)
105 {
106 BN_ULONG c = 0;
107 BN_ULONG bl, bh;
108
109 assert(num >= 0);
110 if (num <= 0)
111 return (BN_ULONG)0;
112
113 bl = LBITS(w);
114 bh = HBITS(w);
115
116 #ifndef OPENSSL_SMALL_FOOTPRINT
117 while (num & ~3) {
118 mul_add(rp[0], ap[0], bl, bh, c);
119 mul_add(rp[1], ap[1], bl, bh, c);
120 mul_add(rp[2], ap[2], bl, bh, c);
121 mul_add(rp[3], ap[3], bl, bh, c);
122 ap += 4;
123 rp += 4;
124 num -= 4;
125 }
126 #endif
127 while (num) {
128 mul_add(rp[0], ap[0], bl, bh, c);
129 ap++;
130 rp++;
131 num--;
132 }
133 return c;
134 }
135
bn_mul_words(BN_ULONG * rp,const BN_ULONG * ap,int num,BN_ULONG w)136 BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
137 {
138 BN_ULONG carry = 0;
139 BN_ULONG bl, bh;
140
141 assert(num >= 0);
142 if (num <= 0)
143 return (BN_ULONG)0;
144
145 bl = LBITS(w);
146 bh = HBITS(w);
147
148 #ifndef OPENSSL_SMALL_FOOTPRINT
149 while (num & ~3) {
150 mul(rp[0], ap[0], bl, bh, carry);
151 mul(rp[1], ap[1], bl, bh, carry);
152 mul(rp[2], ap[2], bl, bh, carry);
153 mul(rp[3], ap[3], bl, bh, carry);
154 ap += 4;
155 rp += 4;
156 num -= 4;
157 }
158 #endif
159 while (num) {
160 mul(rp[0], ap[0], bl, bh, carry);
161 ap++;
162 rp++;
163 num--;
164 }
165 return carry;
166 }
167
bn_sqr_words(BN_ULONG * r,const BN_ULONG * a,int n)168 void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
169 {
170 assert(n >= 0);
171 if (n <= 0)
172 return;
173
174 #ifndef OPENSSL_SMALL_FOOTPRINT
175 while (n & ~3) {
176 sqr64(r[0], r[1], a[0]);
177 sqr64(r[2], r[3], a[1]);
178 sqr64(r[4], r[5], a[2]);
179 sqr64(r[6], r[7], a[3]);
180 a += 4;
181 r += 8;
182 n -= 4;
183 }
184 #endif
185 while (n) {
186 sqr64(r[0], r[1], a[0]);
187 a++;
188 r += 2;
189 n--;
190 }
191 }
192
193 #endif /* !(defined(BN_LLONG) || \
194 * defined(BN_UMULT_HIGH)) */
195
196 #if defined(BN_LLONG) && defined(BN_DIV2W)
197
bn_div_words(BN_ULONG h,BN_ULONG l,BN_ULONG d)198 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
199 {
200 return ((BN_ULONG)(((((BN_ULLONG)h) << BN_BITS2) | l) / (BN_ULLONG)d));
201 }
202
203 #else
204
205 /* Divide h,l by d and return the result. */
206 /* I need to test this some more :-( */
bn_div_words(BN_ULONG h,BN_ULONG l,BN_ULONG d)207 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
208 {
209 BN_ULONG dh, dl, q, ret = 0, th, tl, t;
210 int i, count = 2;
211
212 if (d == 0)
213 return BN_MASK2;
214
215 i = BN_num_bits_word(d);
216 assert((i == BN_BITS2) || (h <= (BN_ULONG)1 << i));
217
218 i = BN_BITS2 - i;
219 if (h >= d)
220 h -= d;
221
222 if (i) {
223 d <<= i;
224 h = (h << i) | (l >> (BN_BITS2 - i));
225 l <<= i;
226 }
227 dh = (d & BN_MASK2h) >> BN_BITS4;
228 dl = (d & BN_MASK2l);
229 for (;;) {
230 if ((h >> BN_BITS4) == dh)
231 q = BN_MASK2l;
232 else
233 q = h / dh;
234
235 th = q * dh;
236 tl = dl * q;
237 for (;;) {
238 t = h - th;
239 if ((t & BN_MASK2h) || ((tl) <= ((t << BN_BITS4) | ((l & BN_MASK2h) >> BN_BITS4))))
240 break;
241 q--;
242 th -= dh;
243 tl -= dl;
244 }
245 t = (tl >> BN_BITS4);
246 tl = (tl << BN_BITS4) & BN_MASK2h;
247 th += t;
248
249 if (l < tl)
250 th++;
251 l -= tl;
252 if (h < th) {
253 h += d;
254 q--;
255 }
256 h -= th;
257
258 if (--count == 0)
259 break;
260
261 ret = q << BN_BITS4;
262 h = ((h << BN_BITS4) | (l >> BN_BITS4)) & BN_MASK2;
263 l = (l & BN_MASK2l) << BN_BITS4;
264 }
265 ret |= q;
266 return ret;
267 }
268 #endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
269
270 #ifdef BN_LLONG
bn_add_words(BN_ULONG * r,const BN_ULONG * a,const BN_ULONG * b,int n)271 BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
272 int n)
273 {
274 BN_ULLONG ll = 0;
275
276 assert(n >= 0);
277 if (n <= 0)
278 return (BN_ULONG)0;
279
280 #ifndef OPENSSL_SMALL_FOOTPRINT
281 while (n & ~3) {
282 ll += (BN_ULLONG)a[0] + b[0];
283 r[0] = (BN_ULONG)ll & BN_MASK2;
284 ll >>= BN_BITS2;
285 ll += (BN_ULLONG)a[1] + b[1];
286 r[1] = (BN_ULONG)ll & BN_MASK2;
287 ll >>= BN_BITS2;
288 ll += (BN_ULLONG)a[2] + b[2];
289 r[2] = (BN_ULONG)ll & BN_MASK2;
290 ll >>= BN_BITS2;
291 ll += (BN_ULLONG)a[3] + b[3];
292 r[3] = (BN_ULONG)ll & BN_MASK2;
293 ll >>= BN_BITS2;
294 a += 4;
295 b += 4;
296 r += 4;
297 n -= 4;
298 }
299 #endif
300 while (n) {
301 ll += (BN_ULLONG)a[0] + b[0];
302 r[0] = (BN_ULONG)ll & BN_MASK2;
303 ll >>= BN_BITS2;
304 a++;
305 b++;
306 r++;
307 n--;
308 }
309 return (BN_ULONG)ll;
310 }
311 #else /* !BN_LLONG */
bn_add_words(BN_ULONG * r,const BN_ULONG * a,const BN_ULONG * b,int n)312 BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
313 int n)
314 {
315 BN_ULONG c, l, t;
316
317 assert(n >= 0);
318 if (n <= 0)
319 return (BN_ULONG)0;
320
321 c = 0;
322 #ifndef OPENSSL_SMALL_FOOTPRINT
323 while (n & ~3) {
324 t = a[0];
325 t = (t + c) & BN_MASK2;
326 c = (t < c);
327 l = (t + b[0]) & BN_MASK2;
328 c += (l < t);
329 r[0] = l;
330 t = a[1];
331 t = (t + c) & BN_MASK2;
332 c = (t < c);
333 l = (t + b[1]) & BN_MASK2;
334 c += (l < t);
335 r[1] = l;
336 t = a[2];
337 t = (t + c) & BN_MASK2;
338 c = (t < c);
339 l = (t + b[2]) & BN_MASK2;
340 c += (l < t);
341 r[2] = l;
342 t = a[3];
343 t = (t + c) & BN_MASK2;
344 c = (t < c);
345 l = (t + b[3]) & BN_MASK2;
346 c += (l < t);
347 r[3] = l;
348 a += 4;
349 b += 4;
350 r += 4;
351 n -= 4;
352 }
353 #endif
354 while (n) {
355 t = a[0];
356 t = (t + c) & BN_MASK2;
357 c = (t < c);
358 l = (t + b[0]) & BN_MASK2;
359 c += (l < t);
360 r[0] = l;
361 a++;
362 b++;
363 r++;
364 n--;
365 }
366 return (BN_ULONG)c;
367 }
368 #endif /* !BN_LLONG */
369
bn_sub_words(BN_ULONG * r,const BN_ULONG * a,const BN_ULONG * b,int n)370 BN_ULONG bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
371 int n)
372 {
373 BN_ULONG t1, t2;
374 int c = 0;
375
376 assert(n >= 0);
377 if (n <= 0)
378 return (BN_ULONG)0;
379
380 #ifndef OPENSSL_SMALL_FOOTPRINT
381 while (n & ~3) {
382 t1 = a[0];
383 t2 = (t1 - c) & BN_MASK2;
384 c = (t2 > t1);
385 t1 = b[0];
386 t1 = (t2 - t1) & BN_MASK2;
387 r[0] = t1;
388 c += (t1 > t2);
389 t1 = a[1];
390 t2 = (t1 - c) & BN_MASK2;
391 c = (t2 > t1);
392 t1 = b[1];
393 t1 = (t2 - t1) & BN_MASK2;
394 r[1] = t1;
395 c += (t1 > t2);
396 t1 = a[2];
397 t2 = (t1 - c) & BN_MASK2;
398 c = (t2 > t1);
399 t1 = b[2];
400 t1 = (t2 - t1) & BN_MASK2;
401 r[2] = t1;
402 c += (t1 > t2);
403 t1 = a[3];
404 t2 = (t1 - c) & BN_MASK2;
405 c = (t2 > t1);
406 t1 = b[3];
407 t1 = (t2 - t1) & BN_MASK2;
408 r[3] = t1;
409 c += (t1 > t2);
410 a += 4;
411 b += 4;
412 r += 4;
413 n -= 4;
414 }
415 #endif
416 while (n) {
417 t1 = a[0];
418 t2 = (t1 - c) & BN_MASK2;
419 c = (t2 > t1);
420 t1 = b[0];
421 t1 = (t2 - t1) & BN_MASK2;
422 r[0] = t1;
423 c += (t1 > t2);
424 a++;
425 b++;
426 r++;
427 n--;
428 }
429 return c;
430 }
431
432 #if defined(BN_MUL_COMBA) && !defined(OPENSSL_SMALL_FOOTPRINT)
433
434 /* mul_add_c(a,b,c0,c1,c2) -- c+=a*b for three word number c=(c2,c1,c0) */
435 /* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
436 /* sqr_add_c(a,i,c0,c1,c2) -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
437 /*
438 * sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number
439 * c=(c2,c1,c0)
440 */
441
442 #ifdef BN_LLONG
443 /*
444 * Keep in mind that additions to multiplication result can not
445 * overflow, because its high half cannot be all-ones.
446 */
447 #define mul_add_c(a, b, c0, c1, c2) \
448 do { \
449 BN_ULONG hi; \
450 BN_ULLONG t = (BN_ULLONG)(a) * (b); \
451 t += c0; /* no carry */ \
452 c0 = (BN_ULONG)Lw(t); \
453 hi = (BN_ULONG)Hw(t); \
454 c1 = (c1 + hi) & BN_MASK2; \
455 c2 += (c1 < hi); \
456 } while (0)
457
458 #define mul_add_c2(a, b, c0, c1, c2) \
459 do { \
460 BN_ULONG hi; \
461 BN_ULLONG t = (BN_ULLONG)(a) * (b); \
462 BN_ULLONG tt = t + c0; /* no carry */ \
463 c0 = (BN_ULONG)Lw(tt); \
464 hi = (BN_ULONG)Hw(tt); \
465 c1 = (c1 + hi) & BN_MASK2; \
466 c2 += (c1 < hi); \
467 t += c0; /* no carry */ \
468 c0 = (BN_ULONG)Lw(t); \
469 hi = (BN_ULONG)Hw(t); \
470 c1 = (c1 + hi) & BN_MASK2; \
471 c2 += (c1 < hi); \
472 } while (0)
473
474 #define sqr_add_c(a, i, c0, c1, c2) \
475 do { \
476 BN_ULONG hi; \
477 BN_ULLONG t = (BN_ULLONG)a[i] * a[i]; \
478 t += c0; /* no carry */ \
479 c0 = (BN_ULONG)Lw(t); \
480 hi = (BN_ULONG)Hw(t); \
481 c1 = (c1 + hi) & BN_MASK2; \
482 c2 += (c1 < hi); \
483 } while (0)
484
485 #define sqr_add_c2(a, i, j, c0, c1, c2) \
486 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
487
488 #elif defined(BN_UMULT_LOHI)
489 /*
490 * Keep in mind that additions to hi can not overflow, because
491 * the high word of a multiplication result cannot be all-ones.
492 */
493 #define mul_add_c(a, b, c0, c1, c2) \
494 do { \
495 BN_ULONG ta = (a), tb = (b); \
496 BN_ULONG lo, hi; \
497 BN_UMULT_LOHI(lo, hi, ta, tb); \
498 c0 += lo; \
499 hi += (c0 < lo); \
500 c1 += hi; \
501 c2 += (c1 < hi); \
502 } while (0)
503
504 #define mul_add_c2(a, b, c0, c1, c2) \
505 do { \
506 BN_ULONG ta = (a), tb = (b); \
507 BN_ULONG lo, hi, tt; \
508 BN_UMULT_LOHI(lo, hi, ta, tb); \
509 c0 += lo; \
510 tt = hi + (c0 < lo); \
511 c1 += tt; \
512 c2 += (c1 < tt); \
513 c0 += lo; \
514 hi += (c0 < lo); \
515 c1 += hi; \
516 c2 += (c1 < hi); \
517 } while (0)
518
519 #define sqr_add_c(a, i, c0, c1, c2) \
520 do { \
521 BN_ULONG ta = (a)[i]; \
522 BN_ULONG lo, hi; \
523 BN_UMULT_LOHI(lo, hi, ta, ta); \
524 c0 += lo; \
525 hi += (c0 < lo); \
526 c1 += hi; \
527 c2 += (c1 < hi); \
528 } while (0)
529
530 #define sqr_add_c2(a, i, j, c0, c1, c2) \
531 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
532
533 #elif defined(BN_UMULT_HIGH)
534 /*
535 * Keep in mind that additions to hi can not overflow, because
536 * the high word of a multiplication result cannot be all-ones.
537 */
538 #define mul_add_c(a, b, c0, c1, c2) \
539 do { \
540 BN_ULONG ta = (a), tb = (b); \
541 BN_ULONG lo = ta * tb; \
542 BN_ULONG hi = BN_UMULT_HIGH(ta, tb); \
543 c0 += lo; \
544 hi += (c0 < lo); \
545 c1 += hi; \
546 c2 += (c1 < hi); \
547 } while (0)
548
549 #define mul_add_c2(a, b, c0, c1, c2) \
550 do { \
551 BN_ULONG ta = (a), tb = (b), tt; \
552 BN_ULONG lo = ta * tb; \
553 BN_ULONG hi = BN_UMULT_HIGH(ta, tb); \
554 c0 += lo; \
555 tt = hi + (c0 < lo); \
556 c1 += tt; \
557 c2 += (c1 < tt); \
558 c0 += lo; \
559 hi += (c0 < lo); \
560 c1 += hi; \
561 c2 += (c1 < hi); \
562 } while (0)
563
564 #define sqr_add_c(a, i, c0, c1, c2) \
565 do { \
566 BN_ULONG ta = (a)[i]; \
567 BN_ULONG lo = ta * ta; \
568 BN_ULONG hi = BN_UMULT_HIGH(ta, ta); \
569 c0 += lo; \
570 hi += (c0 < lo); \
571 c1 += hi; \
572 c2 += (c1 < hi); \
573 } while (0)
574
575 #define sqr_add_c2(a, i, j, c0, c1, c2) \
576 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
577
578 #else /* !BN_LLONG */
579 /*
580 * Keep in mind that additions to hi can not overflow, because
581 * the high word of a multiplication result cannot be all-ones.
582 */
583 #define mul_add_c(a, b, c0, c1, c2) \
584 do { \
585 BN_ULONG lo = LBITS(a), hi = HBITS(a); \
586 BN_ULONG bl = LBITS(b), bh = HBITS(b); \
587 mul64(lo, hi, bl, bh); \
588 c0 = (c0 + lo) & BN_MASK2; \
589 hi += (c0 < lo); \
590 c1 = (c1 + hi) & BN_MASK2; \
591 c2 += (c1 < hi); \
592 } while (0)
593
594 #define mul_add_c2(a, b, c0, c1, c2) \
595 do { \
596 BN_ULONG tt; \
597 BN_ULONG lo = LBITS(a), hi = HBITS(a); \
598 BN_ULONG bl = LBITS(b), bh = HBITS(b); \
599 mul64(lo, hi, bl, bh); \
600 tt = hi; \
601 c0 = (c0 + lo) & BN_MASK2; \
602 tt += (c0 < lo); \
603 c1 = (c1 + tt) & BN_MASK2; \
604 c2 += (c1 < tt); \
605 c0 = (c0 + lo) & BN_MASK2; \
606 hi += (c0 < lo); \
607 c1 = (c1 + hi) & BN_MASK2; \
608 c2 += (c1 < hi); \
609 } while (0)
610
611 #define sqr_add_c(a, i, c0, c1, c2) \
612 do { \
613 BN_ULONG lo, hi; \
614 sqr64(lo, hi, (a)[i]); \
615 c0 = (c0 + lo) & BN_MASK2; \
616 hi += (c0 < lo); \
617 c1 = (c1 + hi) & BN_MASK2; \
618 c2 += (c1 < hi); \
619 } while (0)
620
621 #define sqr_add_c2(a, i, j, c0, c1, c2) \
622 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
623 #endif /* !BN_LLONG */
624
bn_mul_comba8(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b)625 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
626 {
627 BN_ULONG c1, c2, c3;
628
629 c1 = 0;
630 c2 = 0;
631 c3 = 0;
632 mul_add_c(a[0], b[0], c1, c2, c3);
633 r[0] = c1;
634 c1 = 0;
635 mul_add_c(a[0], b[1], c2, c3, c1);
636 mul_add_c(a[1], b[0], c2, c3, c1);
637 r[1] = c2;
638 c2 = 0;
639 mul_add_c(a[2], b[0], c3, c1, c2);
640 mul_add_c(a[1], b[1], c3, c1, c2);
641 mul_add_c(a[0], b[2], c3, c1, c2);
642 r[2] = c3;
643 c3 = 0;
644 mul_add_c(a[0], b[3], c1, c2, c3);
645 mul_add_c(a[1], b[2], c1, c2, c3);
646 mul_add_c(a[2], b[1], c1, c2, c3);
647 mul_add_c(a[3], b[0], c1, c2, c3);
648 r[3] = c1;
649 c1 = 0;
650 mul_add_c(a[4], b[0], c2, c3, c1);
651 mul_add_c(a[3], b[1], c2, c3, c1);
652 mul_add_c(a[2], b[2], c2, c3, c1);
653 mul_add_c(a[1], b[3], c2, c3, c1);
654 mul_add_c(a[0], b[4], c2, c3, c1);
655 r[4] = c2;
656 c2 = 0;
657 mul_add_c(a[0], b[5], c3, c1, c2);
658 mul_add_c(a[1], b[4], c3, c1, c2);
659 mul_add_c(a[2], b[3], c3, c1, c2);
660 mul_add_c(a[3], b[2], c3, c1, c2);
661 mul_add_c(a[4], b[1], c3, c1, c2);
662 mul_add_c(a[5], b[0], c3, c1, c2);
663 r[5] = c3;
664 c3 = 0;
665 mul_add_c(a[6], b[0], c1, c2, c3);
666 mul_add_c(a[5], b[1], c1, c2, c3);
667 mul_add_c(a[4], b[2], c1, c2, c3);
668 mul_add_c(a[3], b[3], c1, c2, c3);
669 mul_add_c(a[2], b[4], c1, c2, c3);
670 mul_add_c(a[1], b[5], c1, c2, c3);
671 mul_add_c(a[0], b[6], c1, c2, c3);
672 r[6] = c1;
673 c1 = 0;
674 mul_add_c(a[0], b[7], c2, c3, c1);
675 mul_add_c(a[1], b[6], c2, c3, c1);
676 mul_add_c(a[2], b[5], c2, c3, c1);
677 mul_add_c(a[3], b[4], c2, c3, c1);
678 mul_add_c(a[4], b[3], c2, c3, c1);
679 mul_add_c(a[5], b[2], c2, c3, c1);
680 mul_add_c(a[6], b[1], c2, c3, c1);
681 mul_add_c(a[7], b[0], c2, c3, c1);
682 r[7] = c2;
683 c2 = 0;
684 mul_add_c(a[7], b[1], c3, c1, c2);
685 mul_add_c(a[6], b[2], c3, c1, c2);
686 mul_add_c(a[5], b[3], c3, c1, c2);
687 mul_add_c(a[4], b[4], c3, c1, c2);
688 mul_add_c(a[3], b[5], c3, c1, c2);
689 mul_add_c(a[2], b[6], c3, c1, c2);
690 mul_add_c(a[1], b[7], c3, c1, c2);
691 r[8] = c3;
692 c3 = 0;
693 mul_add_c(a[2], b[7], c1, c2, c3);
694 mul_add_c(a[3], b[6], c1, c2, c3);
695 mul_add_c(a[4], b[5], c1, c2, c3);
696 mul_add_c(a[5], b[4], c1, c2, c3);
697 mul_add_c(a[6], b[3], c1, c2, c3);
698 mul_add_c(a[7], b[2], c1, c2, c3);
699 r[9] = c1;
700 c1 = 0;
701 mul_add_c(a[7], b[3], c2, c3, c1);
702 mul_add_c(a[6], b[4], c2, c3, c1);
703 mul_add_c(a[5], b[5], c2, c3, c1);
704 mul_add_c(a[4], b[6], c2, c3, c1);
705 mul_add_c(a[3], b[7], c2, c3, c1);
706 r[10] = c2;
707 c2 = 0;
708 mul_add_c(a[4], b[7], c3, c1, c2);
709 mul_add_c(a[5], b[6], c3, c1, c2);
710 mul_add_c(a[6], b[5], c3, c1, c2);
711 mul_add_c(a[7], b[4], c3, c1, c2);
712 r[11] = c3;
713 c3 = 0;
714 mul_add_c(a[7], b[5], c1, c2, c3);
715 mul_add_c(a[6], b[6], c1, c2, c3);
716 mul_add_c(a[5], b[7], c1, c2, c3);
717 r[12] = c1;
718 c1 = 0;
719 mul_add_c(a[6], b[7], c2, c3, c1);
720 mul_add_c(a[7], b[6], c2, c3, c1);
721 r[13] = c2;
722 c2 = 0;
723 mul_add_c(a[7], b[7], c3, c1, c2);
724 r[14] = c3;
725 r[15] = c1;
726 }
727
bn_mul_comba4(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b)728 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
729 {
730 BN_ULONG c1, c2, c3;
731
732 c1 = 0;
733 c2 = 0;
734 c3 = 0;
735 mul_add_c(a[0], b[0], c1, c2, c3);
736 r[0] = c1;
737 c1 = 0;
738 mul_add_c(a[0], b[1], c2, c3, c1);
739 mul_add_c(a[1], b[0], c2, c3, c1);
740 r[1] = c2;
741 c2 = 0;
742 mul_add_c(a[2], b[0], c3, c1, c2);
743 mul_add_c(a[1], b[1], c3, c1, c2);
744 mul_add_c(a[0], b[2], c3, c1, c2);
745 r[2] = c3;
746 c3 = 0;
747 mul_add_c(a[0], b[3], c1, c2, c3);
748 mul_add_c(a[1], b[2], c1, c2, c3);
749 mul_add_c(a[2], b[1], c1, c2, c3);
750 mul_add_c(a[3], b[0], c1, c2, c3);
751 r[3] = c1;
752 c1 = 0;
753 mul_add_c(a[3], b[1], c2, c3, c1);
754 mul_add_c(a[2], b[2], c2, c3, c1);
755 mul_add_c(a[1], b[3], c2, c3, c1);
756 r[4] = c2;
757 c2 = 0;
758 mul_add_c(a[2], b[3], c3, c1, c2);
759 mul_add_c(a[3], b[2], c3, c1, c2);
760 r[5] = c3;
761 c3 = 0;
762 mul_add_c(a[3], b[3], c1, c2, c3);
763 r[6] = c1;
764 r[7] = c2;
765 }
766
bn_sqr_comba8(BN_ULONG * r,const BN_ULONG * a)767 void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
768 {
769 BN_ULONG c1, c2, c3;
770
771 c1 = 0;
772 c2 = 0;
773 c3 = 0;
774 sqr_add_c(a, 0, c1, c2, c3);
775 r[0] = c1;
776 c1 = 0;
777 sqr_add_c2(a, 1, 0, c2, c3, c1);
778 r[1] = c2;
779 c2 = 0;
780 sqr_add_c(a, 1, c3, c1, c2);
781 sqr_add_c2(a, 2, 0, c3, c1, c2);
782 r[2] = c3;
783 c3 = 0;
784 sqr_add_c2(a, 3, 0, c1, c2, c3);
785 sqr_add_c2(a, 2, 1, c1, c2, c3);
786 r[3] = c1;
787 c1 = 0;
788 sqr_add_c(a, 2, c2, c3, c1);
789 sqr_add_c2(a, 3, 1, c2, c3, c1);
790 sqr_add_c2(a, 4, 0, c2, c3, c1);
791 r[4] = c2;
792 c2 = 0;
793 sqr_add_c2(a, 5, 0, c3, c1, c2);
794 sqr_add_c2(a, 4, 1, c3, c1, c2);
795 sqr_add_c2(a, 3, 2, c3, c1, c2);
796 r[5] = c3;
797 c3 = 0;
798 sqr_add_c(a, 3, c1, c2, c3);
799 sqr_add_c2(a, 4, 2, c1, c2, c3);
800 sqr_add_c2(a, 5, 1, c1, c2, c3);
801 sqr_add_c2(a, 6, 0, c1, c2, c3);
802 r[6] = c1;
803 c1 = 0;
804 sqr_add_c2(a, 7, 0, c2, c3, c1);
805 sqr_add_c2(a, 6, 1, c2, c3, c1);
806 sqr_add_c2(a, 5, 2, c2, c3, c1);
807 sqr_add_c2(a, 4, 3, c2, c3, c1);
808 r[7] = c2;
809 c2 = 0;
810 sqr_add_c(a, 4, c3, c1, c2);
811 sqr_add_c2(a, 5, 3, c3, c1, c2);
812 sqr_add_c2(a, 6, 2, c3, c1, c2);
813 sqr_add_c2(a, 7, 1, c3, c1, c2);
814 r[8] = c3;
815 c3 = 0;
816 sqr_add_c2(a, 7, 2, c1, c2, c3);
817 sqr_add_c2(a, 6, 3, c1, c2, c3);
818 sqr_add_c2(a, 5, 4, c1, c2, c3);
819 r[9] = c1;
820 c1 = 0;
821 sqr_add_c(a, 5, c2, c3, c1);
822 sqr_add_c2(a, 6, 4, c2, c3, c1);
823 sqr_add_c2(a, 7, 3, c2, c3, c1);
824 r[10] = c2;
825 c2 = 0;
826 sqr_add_c2(a, 7, 4, c3, c1, c2);
827 sqr_add_c2(a, 6, 5, c3, c1, c2);
828 r[11] = c3;
829 c3 = 0;
830 sqr_add_c(a, 6, c1, c2, c3);
831 sqr_add_c2(a, 7, 5, c1, c2, c3);
832 r[12] = c1;
833 c1 = 0;
834 sqr_add_c2(a, 7, 6, c2, c3, c1);
835 r[13] = c2;
836 c2 = 0;
837 sqr_add_c(a, 7, c3, c1, c2);
838 r[14] = c3;
839 r[15] = c1;
840 }
841
bn_sqr_comba4(BN_ULONG * r,const BN_ULONG * a)842 void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
843 {
844 BN_ULONG c1, c2, c3;
845
846 c1 = 0;
847 c2 = 0;
848 c3 = 0;
849 sqr_add_c(a, 0, c1, c2, c3);
850 r[0] = c1;
851 c1 = 0;
852 sqr_add_c2(a, 1, 0, c2, c3, c1);
853 r[1] = c2;
854 c2 = 0;
855 sqr_add_c(a, 1, c3, c1, c2);
856 sqr_add_c2(a, 2, 0, c3, c1, c2);
857 r[2] = c3;
858 c3 = 0;
859 sqr_add_c2(a, 3, 0, c1, c2, c3);
860 sqr_add_c2(a, 2, 1, c1, c2, c3);
861 r[3] = c1;
862 c1 = 0;
863 sqr_add_c(a, 2, c2, c3, c1);
864 sqr_add_c2(a, 3, 1, c2, c3, c1);
865 r[4] = c2;
866 c2 = 0;
867 sqr_add_c2(a, 3, 2, c3, c1, c2);
868 r[5] = c3;
869 c3 = 0;
870 sqr_add_c(a, 3, c1, c2, c3);
871 r[6] = c1;
872 r[7] = c2;
873 }
874
875 #ifdef OPENSSL_NO_ASM
876 #ifdef OPENSSL_BN_ASM_MONT
877 #include <alloca.h>
878 /*
879 * This is essentially reference implementation, which may or may not
880 * result in performance improvement. E.g. on IA-32 this routine was
881 * observed to give 40% faster rsa1024 private key operations and 10%
882 * faster rsa4096 ones, while on AMD64 it improves rsa1024 sign only
883 * by 10% and *worsens* rsa4096 sign by 15%. Once again, it's a
884 * reference implementation, one to be used as starting point for
885 * platform-specific assembler. Mentioned numbers apply to compiler
886 * generated code compiled with and without -DOPENSSL_BN_ASM_MONT and
887 * can vary not only from platform to platform, but even for compiler
888 * versions. Assembler vs. assembler improvement coefficients can
889 * [and are known to] differ and are to be documented elsewhere.
890 */
bn_mul_mont(BN_ULONG * rp,const BN_ULONG * ap,const BN_ULONG * bp,const BN_ULONG * np,const BN_ULONG * n0p,int num)891 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
892 const BN_ULONG *np, const BN_ULONG *n0p, int num)
893 {
894 BN_ULONG c0, c1, ml, *tp, n0;
895 #ifdef mul64
896 BN_ULONG mh;
897 #endif
898 volatile BN_ULONG *vp;
899 int i = 0, j;
900
901 #if 0 /* template for platform-specific \
902 * implementation */
903 if (ap == bp)
904 return bn_sqr_mont(rp, ap, np, n0p, num);
905 #endif
906 vp = tp = alloca((num + 2) * sizeof(BN_ULONG));
907
908 n0 = *n0p;
909
910 c0 = 0;
911 ml = bp[0];
912 #ifdef mul64
913 mh = HBITS(ml);
914 ml = LBITS(ml);
915 for (j = 0; j < num; ++j)
916 mul(tp[j], ap[j], ml, mh, c0);
917 #else
918 for (j = 0; j < num; ++j)
919 mul(tp[j], ap[j], ml, c0);
920 #endif
921
922 tp[num] = c0;
923 tp[num + 1] = 0;
924 goto enter;
925
926 for (i = 0; i < num; i++) {
927 c0 = 0;
928 ml = bp[i];
929 #ifdef mul64
930 mh = HBITS(ml);
931 ml = LBITS(ml);
932 for (j = 0; j < num; ++j)
933 mul_add(tp[j], ap[j], ml, mh, c0);
934 #else
935 for (j = 0; j < num; ++j)
936 mul_add(tp[j], ap[j], ml, c0);
937 #endif
938 c1 = (tp[num] + c0) & BN_MASK2;
939 tp[num] = c1;
940 tp[num + 1] = (c1 < c0 ? 1 : 0);
941 enter:
942 c1 = tp[0];
943 ml = (c1 * n0) & BN_MASK2;
944 c0 = 0;
945 #ifdef mul64
946 mh = HBITS(ml);
947 ml = LBITS(ml);
948 mul_add(c1, np[0], ml, mh, c0);
949 #else
950 mul_add(c1, ml, np[0], c0);
951 #endif
952 for (j = 1; j < num; j++) {
953 c1 = tp[j];
954 #ifdef mul64
955 mul_add(c1, np[j], ml, mh, c0);
956 #else
957 mul_add(c1, ml, np[j], c0);
958 #endif
959 tp[j - 1] = c1 & BN_MASK2;
960 }
961 c1 = (tp[num] + c0) & BN_MASK2;
962 tp[num - 1] = c1;
963 tp[num] = tp[num + 1] + (c1 < c0 ? 1 : 0);
964 }
965
966 if (tp[num] != 0 || tp[num - 1] >= np[num - 1]) {
967 c0 = bn_sub_words(rp, tp, np, num);
968 if (tp[num] != 0 || c0 == 0) {
969 for (i = 0; i < num + 2; i++)
970 vp[i] = 0;
971 return 1;
972 }
973 }
974 for (i = 0; i < num; i++)
975 rp[i] = tp[i], vp[i] = 0;
976 vp[num] = 0;
977 vp[num + 1] = 0;
978 return 1;
979 }
980 #else
981 /*
982 * Return value of 0 indicates that multiplication/convolution was not
983 * performed to signal the caller to fall down to alternative/original
984 * code-path.
985 */
bn_mul_mont(BN_ULONG * rp,const BN_ULONG * ap,const BN_ULONG * bp,const BN_ULONG * np,const BN_ULONG * n0,int num)986 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
987 const BN_ULONG *np, const BN_ULONG *n0, int num)
988 {
989 return 0;
990 }
991 #endif /* OPENSSL_BN_ASM_MONT */
992 #endif
993
994 #else /* !BN_MUL_COMBA */
995
996 /* hmm... is it faster just to do a multiply? */
bn_sqr_comba4(BN_ULONG * r,const BN_ULONG * a)997 void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
998 {
999 BN_ULONG t[8];
1000 bn_sqr_normal(r, a, 4, t);
1001 }
1002
bn_sqr_comba8(BN_ULONG * r,const BN_ULONG * a)1003 void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
1004 {
1005 BN_ULONG t[16];
1006 bn_sqr_normal(r, a, 8, t);
1007 }
1008
bn_mul_comba4(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b)1009 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
1010 {
1011 r[4] = bn_mul_words(&(r[0]), a, 4, b[0]);
1012 r[5] = bn_mul_add_words(&(r[1]), a, 4, b[1]);
1013 r[6] = bn_mul_add_words(&(r[2]), a, 4, b[2]);
1014 r[7] = bn_mul_add_words(&(r[3]), a, 4, b[3]);
1015 }
1016
bn_mul_comba8(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b)1017 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
1018 {
1019 r[8] = bn_mul_words(&(r[0]), a, 8, b[0]);
1020 r[9] = bn_mul_add_words(&(r[1]), a, 8, b[1]);
1021 r[10] = bn_mul_add_words(&(r[2]), a, 8, b[2]);
1022 r[11] = bn_mul_add_words(&(r[3]), a, 8, b[3]);
1023 r[12] = bn_mul_add_words(&(r[4]), a, 8, b[4]);
1024 r[13] = bn_mul_add_words(&(r[5]), a, 8, b[5]);
1025 r[14] = bn_mul_add_words(&(r[6]), a, 8, b[6]);
1026 r[15] = bn_mul_add_words(&(r[7]), a, 8, b[7]);
1027 }
1028
1029 #ifdef OPENSSL_NO_ASM
1030 #ifdef OPENSSL_BN_ASM_MONT
1031 #include <alloca.h>
bn_mul_mont(BN_ULONG * rp,const BN_ULONG * ap,const BN_ULONG * bp,const BN_ULONG * np,const BN_ULONG * n0p,int num)1032 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
1033 const BN_ULONG *np, const BN_ULONG *n0p, int num)
1034 {
1035 BN_ULONG c0, c1, *tp, n0 = *n0p;
1036 volatile BN_ULONG *vp;
1037 int i = 0, j;
1038
1039 vp = tp = alloca((num + 2) * sizeof(BN_ULONG));
1040
1041 for (i = 0; i <= num; i++)
1042 tp[i] = 0;
1043
1044 for (i = 0; i < num; i++) {
1045 c0 = bn_mul_add_words(tp, ap, num, bp[i]);
1046 c1 = (tp[num] + c0) & BN_MASK2;
1047 tp[num] = c1;
1048 tp[num + 1] = (c1 < c0 ? 1 : 0);
1049
1050 c0 = bn_mul_add_words(tp, np, num, tp[0] * n0);
1051 c1 = (tp[num] + c0) & BN_MASK2;
1052 tp[num] = c1;
1053 tp[num + 1] += (c1 < c0 ? 1 : 0);
1054 for (j = 0; j <= num; j++)
1055 tp[j] = tp[j + 1];
1056 }
1057
1058 if (tp[num] != 0 || tp[num - 1] >= np[num - 1]) {
1059 c0 = bn_sub_words(rp, tp, np, num);
1060 if (tp[num] != 0 || c0 == 0) {
1061 for (i = 0; i < num + 2; i++)
1062 vp[i] = 0;
1063 return 1;
1064 }
1065 }
1066 for (i = 0; i < num; i++)
1067 rp[i] = tp[i], vp[i] = 0;
1068 vp[num] = 0;
1069 vp[num + 1] = 0;
1070 return 1;
1071 }
1072 #else
bn_mul_mont(BN_ULONG * rp,const BN_ULONG * ap,const BN_ULONG * bp,const BN_ULONG * np,const BN_ULONG * n0,int num)1073 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
1074 const BN_ULONG *np, const BN_ULONG *n0, int num)
1075 {
1076 return 0;
1077 }
1078 #endif /* OPENSSL_BN_ASM_MONT */
1079 #endif
1080
1081 #endif /* !BN_MUL_COMBA */
1082