spelling fixes, just comments and readme.
[openssl.git] / crypto / bn / bn_asm.c
1 /*
2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (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_lcl.h"
14
15 #if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
16
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
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
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
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
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
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
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 :-( */
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) ||
240                 ((tl) <= ((t << BN_BITS4) | ((l & BN_MASK2h) >> BN_BITS4))))
241                 break;
242             q--;
243             th -= dh;
244             tl -= dl;
245         }
246         t = (tl >> BN_BITS4);
247         tl = (tl << BN_BITS4) & BN_MASK2h;
248         th += t;
249
250         if (l < tl)
251             th++;
252         l -= tl;
253         if (h < th) {
254             h += d;
255             q--;
256         }
257         h -= th;
258
259         if (--count == 0)
260             break;
261
262         ret = q << BN_BITS4;
263         h = ((h << BN_BITS4) | (l >> BN_BITS4)) & BN_MASK2;
264         l = (l & BN_MASK2l) << BN_BITS4;
265     }
266     ret |= q;
267     return (ret);
268 }
269 #endif                          /* !defined(BN_LLONG) && defined(BN_DIV2W) */
270
271 #ifdef BN_LLONG
272 BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
273                       int n)
274 {
275     BN_ULLONG ll = 0;
276
277     assert(n >= 0);
278     if (n <= 0)
279         return ((BN_ULONG)0);
280
281 # ifndef OPENSSL_SMALL_FOOTPRINT
282     while (n & ~3) {
283         ll += (BN_ULLONG) a[0] + b[0];
284         r[0] = (BN_ULONG)ll & BN_MASK2;
285         ll >>= BN_BITS2;
286         ll += (BN_ULLONG) a[1] + b[1];
287         r[1] = (BN_ULONG)ll & BN_MASK2;
288         ll >>= BN_BITS2;
289         ll += (BN_ULLONG) a[2] + b[2];
290         r[2] = (BN_ULONG)ll & BN_MASK2;
291         ll >>= BN_BITS2;
292         ll += (BN_ULLONG) a[3] + b[3];
293         r[3] = (BN_ULONG)ll & BN_MASK2;
294         ll >>= BN_BITS2;
295         a += 4;
296         b += 4;
297         r += 4;
298         n -= 4;
299     }
300 # endif
301     while (n) {
302         ll += (BN_ULLONG) a[0] + b[0];
303         r[0] = (BN_ULONG)ll & BN_MASK2;
304         ll >>= BN_BITS2;
305         a++;
306         b++;
307         r++;
308         n--;
309     }
310     return ((BN_ULONG)ll);
311 }
312 #else                           /* !BN_LLONG */
313 BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
314                       int n)
315 {
316     BN_ULONG c, l, t;
317
318     assert(n >= 0);
319     if (n <= 0)
320         return ((BN_ULONG)0);
321
322     c = 0;
323 # ifndef OPENSSL_SMALL_FOOTPRINT
324     while (n & ~3) {
325         t = a[0];
326         t = (t + c) & BN_MASK2;
327         c = (t < c);
328         l = (t + b[0]) & BN_MASK2;
329         c += (l < t);
330         r[0] = l;
331         t = a[1];
332         t = (t + c) & BN_MASK2;
333         c = (t < c);
334         l = (t + b[1]) & BN_MASK2;
335         c += (l < t);
336         r[1] = l;
337         t = a[2];
338         t = (t + c) & BN_MASK2;
339         c = (t < c);
340         l = (t + b[2]) & BN_MASK2;
341         c += (l < t);
342         r[2] = l;
343         t = a[3];
344         t = (t + c) & BN_MASK2;
345         c = (t < c);
346         l = (t + b[3]) & BN_MASK2;
347         c += (l < t);
348         r[3] = l;
349         a += 4;
350         b += 4;
351         r += 4;
352         n -= 4;
353     }
354 # endif
355     while (n) {
356         t = a[0];
357         t = (t + c) & BN_MASK2;
358         c = (t < c);
359         l = (t + b[0]) & BN_MASK2;
360         c += (l < t);
361         r[0] = l;
362         a++;
363         b++;
364         r++;
365         n--;
366     }
367     return ((BN_ULONG)c);
368 }
369 #endif                          /* !BN_LLONG */
370
371 BN_ULONG bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
372                       int n)
373 {
374     BN_ULONG t1, t2;
375     int c = 0;
376
377     assert(n >= 0);
378     if (n <= 0)
379         return ((BN_ULONG)0);
380
381 #ifndef OPENSSL_SMALL_FOOTPRINT
382     while (n & ~3) {
383         t1 = a[0];
384         t2 = b[0];
385         r[0] = (t1 - t2 - c) & BN_MASK2;
386         if (t1 != t2)
387             c = (t1 < t2);
388         t1 = a[1];
389         t2 = b[1];
390         r[1] = (t1 - t2 - c) & BN_MASK2;
391         if (t1 != t2)
392             c = (t1 < t2);
393         t1 = a[2];
394         t2 = b[2];
395         r[2] = (t1 - t2 - c) & BN_MASK2;
396         if (t1 != t2)
397             c = (t1 < t2);
398         t1 = a[3];
399         t2 = b[3];
400         r[3] = (t1 - t2 - c) & BN_MASK2;
401         if (t1 != t2)
402             c = (t1 < t2);
403         a += 4;
404         b += 4;
405         r += 4;
406         n -= 4;
407     }
408 #endif
409     while (n) {
410         t1 = a[0];
411         t2 = b[0];
412         r[0] = (t1 - t2 - c) & BN_MASK2;
413         if (t1 != t2)
414             c = (t1 < t2);
415         a++;
416         b++;
417         r++;
418         n--;
419     }
420     return (c);
421 }
422
423 #if defined(BN_MUL_COMBA) && !defined(OPENSSL_SMALL_FOOTPRINT)
424
425 # undef bn_mul_comba8
426 # undef bn_mul_comba4
427 # undef bn_sqr_comba8
428 # undef bn_sqr_comba4
429
430 /* mul_add_c(a,b,c0,c1,c2)  -- c+=a*b for three word number c=(c2,c1,c0) */
431 /* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
432 /* sqr_add_c(a,i,c0,c1,c2)  -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
433 /*
434  * sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number
435  * c=(c2,c1,c0)
436  */
437
438 # ifdef BN_LLONG
439 /*
440  * Keep in mind that additions to multiplication result can not
441  * overflow, because its high half cannot be all-ones.
442  */
443 #  define mul_add_c(a,b,c0,c1,c2)       do {    \
444         BN_ULONG hi;                            \
445         BN_ULLONG t = (BN_ULLONG)(a)*(b);       \
446         t += c0;                /* no carry */  \
447         c0 = (BN_ULONG)Lw(t);                   \
448         hi = (BN_ULONG)Hw(t);                   \
449         c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
450         } while(0)
451
452 #  define mul_add_c2(a,b,c0,c1,c2)      do {    \
453         BN_ULONG hi;                            \
454         BN_ULLONG t = (BN_ULLONG)(a)*(b);       \
455         BN_ULLONG tt = t+c0;    /* no carry */  \
456         c0 = (BN_ULONG)Lw(tt);                  \
457         hi = (BN_ULONG)Hw(tt);                  \
458         c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
459         t += c0;                /* no carry */  \
460         c0 = (BN_ULONG)Lw(t);                   \
461         hi = (BN_ULONG)Hw(t);                   \
462         c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
463         } while(0)
464
465 #  define sqr_add_c(a,i,c0,c1,c2)       do {    \
466         BN_ULONG hi;                            \
467         BN_ULLONG t = (BN_ULLONG)a[i]*a[i];     \
468         t += c0;                /* no carry */  \
469         c0 = (BN_ULONG)Lw(t);                   \
470         hi = (BN_ULONG)Hw(t);                   \
471         c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
472         } while(0)
473
474 #  define sqr_add_c2(a,i,j,c0,c1,c2) \
475         mul_add_c2((a)[i],(a)[j],c0,c1,c2)
476
477 # elif defined(BN_UMULT_LOHI)
478 /*
479  * Keep in mind that additions to hi can not overflow, because
480  * the high word of a multiplication result cannot be all-ones.
481  */
482 #  define mul_add_c(a,b,c0,c1,c2)       do {    \
483         BN_ULONG ta = (a), tb = (b);            \
484         BN_ULONG lo, hi;                        \
485         BN_UMULT_LOHI(lo,hi,ta,tb);             \
486         c0 += lo; hi += (c0<lo)?1:0;            \
487         c1 += hi; c2 += (c1<hi)?1:0;            \
488         } while(0)
489
490 #  define mul_add_c2(a,b,c0,c1,c2)      do {    \
491         BN_ULONG ta = (a), tb = (b);            \
492         BN_ULONG lo, hi, tt;                    \
493         BN_UMULT_LOHI(lo,hi,ta,tb);             \
494         c0 += lo; tt = hi+((c0<lo)?1:0);        \
495         c1 += tt; c2 += (c1<tt)?1:0;            \
496         c0 += lo; hi += (c0<lo)?1:0;            \
497         c1 += hi; c2 += (c1<hi)?1:0;            \
498         } while(0)
499
500 #  define sqr_add_c(a,i,c0,c1,c2)       do {    \
501         BN_ULONG ta = (a)[i];                   \
502         BN_ULONG lo, hi;                        \
503         BN_UMULT_LOHI(lo,hi,ta,ta);             \
504         c0 += lo; hi += (c0<lo)?1:0;            \
505         c1 += hi; c2 += (c1<hi)?1:0;            \
506         } while(0)
507
508 #  define sqr_add_c2(a,i,j,c0,c1,c2)    \
509         mul_add_c2((a)[i],(a)[j],c0,c1,c2)
510
511 # elif defined(BN_UMULT_HIGH)
512 /*
513  * Keep in mind that additions to hi can not overflow, because
514  * the high word of a multiplication result cannot be all-ones.
515  */
516 #  define mul_add_c(a,b,c0,c1,c2)       do {    \
517         BN_ULONG ta = (a), tb = (b);            \
518         BN_ULONG lo = ta * tb;                  \
519         BN_ULONG hi = BN_UMULT_HIGH(ta,tb);     \
520         c0 += lo; hi += (c0<lo)?1:0;            \
521         c1 += hi; c2 += (c1<hi)?1:0;            \
522         } while(0)
523
524 #  define mul_add_c2(a,b,c0,c1,c2)      do {    \
525         BN_ULONG ta = (a), tb = (b), tt;        \
526         BN_ULONG lo = ta * tb;                  \
527         BN_ULONG hi = BN_UMULT_HIGH(ta,tb);     \
528         c0 += lo; tt = hi + ((c0<lo)?1:0);      \
529         c1 += tt; c2 += (c1<tt)?1:0;            \
530         c0 += lo; hi += (c0<lo)?1:0;            \
531         c1 += hi; c2 += (c1<hi)?1:0;            \
532         } while(0)
533
534 #  define sqr_add_c(a,i,c0,c1,c2)       do {    \
535         BN_ULONG ta = (a)[i];                   \
536         BN_ULONG lo = ta * ta;                  \
537         BN_ULONG hi = BN_UMULT_HIGH(ta,ta);     \
538         c0 += lo; hi += (c0<lo)?1:0;            \
539         c1 += hi; c2 += (c1<hi)?1:0;            \
540         } while(0)
541
542 #  define sqr_add_c2(a,i,j,c0,c1,c2)      \
543         mul_add_c2((a)[i],(a)[j],c0,c1,c2)
544
545 # else                          /* !BN_LLONG */
546 /*
547  * Keep in mind that additions to hi can not overflow, because
548  * the high word of a multiplication result cannot be all-ones.
549  */
550 #  define mul_add_c(a,b,c0,c1,c2)       do {    \
551         BN_ULONG lo = LBITS(a), hi = HBITS(a);  \
552         BN_ULONG bl = LBITS(b), bh = HBITS(b);  \
553         mul64(lo,hi,bl,bh);                     \
554         c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
555         c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
556         } while(0)
557
558 #  define mul_add_c2(a,b,c0,c1,c2)      do {    \
559         BN_ULONG tt;                            \
560         BN_ULONG lo = LBITS(a), hi = HBITS(a);  \
561         BN_ULONG bl = LBITS(b), bh = HBITS(b);  \
562         mul64(lo,hi,bl,bh);                     \
563         tt = hi;                                \
564         c0 = (c0+lo)&BN_MASK2; if (c0<lo) tt++; \
565         c1 = (c1+tt)&BN_MASK2; if (c1<tt) c2++; \
566         c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
567         c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
568         } while(0)
569
570 #  define sqr_add_c(a,i,c0,c1,c2)       do {    \
571         BN_ULONG lo, hi;                        \
572         sqr64(lo,hi,(a)[i]);                    \
573         c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
574         c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
575         } while(0)
576
577 #  define sqr_add_c2(a,i,j,c0,c1,c2) \
578         mul_add_c2((a)[i],(a)[j],c0,c1,c2)
579 # endif                         /* !BN_LLONG */
580
581 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
582 {
583     BN_ULONG c1, c2, c3;
584
585     c1 = 0;
586     c2 = 0;
587     c3 = 0;
588     mul_add_c(a[0], b[0], c1, c2, c3);
589     r[0] = c1;
590     c1 = 0;
591     mul_add_c(a[0], b[1], c2, c3, c1);
592     mul_add_c(a[1], b[0], c2, c3, c1);
593     r[1] = c2;
594     c2 = 0;
595     mul_add_c(a[2], b[0], c3, c1, c2);
596     mul_add_c(a[1], b[1], c3, c1, c2);
597     mul_add_c(a[0], b[2], c3, c1, c2);
598     r[2] = c3;
599     c3 = 0;
600     mul_add_c(a[0], b[3], c1, c2, c3);
601     mul_add_c(a[1], b[2], c1, c2, c3);
602     mul_add_c(a[2], b[1], c1, c2, c3);
603     mul_add_c(a[3], b[0], c1, c2, c3);
604     r[3] = c1;
605     c1 = 0;
606     mul_add_c(a[4], b[0], c2, c3, c1);
607     mul_add_c(a[3], b[1], c2, c3, c1);
608     mul_add_c(a[2], b[2], c2, c3, c1);
609     mul_add_c(a[1], b[3], c2, c3, c1);
610     mul_add_c(a[0], b[4], c2, c3, c1);
611     r[4] = c2;
612     c2 = 0;
613     mul_add_c(a[0], b[5], c3, c1, c2);
614     mul_add_c(a[1], b[4], c3, c1, c2);
615     mul_add_c(a[2], b[3], c3, c1, c2);
616     mul_add_c(a[3], b[2], c3, c1, c2);
617     mul_add_c(a[4], b[1], c3, c1, c2);
618     mul_add_c(a[5], b[0], c3, c1, c2);
619     r[5] = c3;
620     c3 = 0;
621     mul_add_c(a[6], b[0], c1, c2, c3);
622     mul_add_c(a[5], b[1], c1, c2, c3);
623     mul_add_c(a[4], b[2], c1, c2, c3);
624     mul_add_c(a[3], b[3], c1, c2, c3);
625     mul_add_c(a[2], b[4], c1, c2, c3);
626     mul_add_c(a[1], b[5], c1, c2, c3);
627     mul_add_c(a[0], b[6], c1, c2, c3);
628     r[6] = c1;
629     c1 = 0;
630     mul_add_c(a[0], b[7], c2, c3, c1);
631     mul_add_c(a[1], b[6], c2, c3, c1);
632     mul_add_c(a[2], b[5], c2, c3, c1);
633     mul_add_c(a[3], b[4], c2, c3, c1);
634     mul_add_c(a[4], b[3], c2, c3, c1);
635     mul_add_c(a[5], b[2], c2, c3, c1);
636     mul_add_c(a[6], b[1], c2, c3, c1);
637     mul_add_c(a[7], b[0], c2, c3, c1);
638     r[7] = c2;
639     c2 = 0;
640     mul_add_c(a[7], b[1], c3, c1, c2);
641     mul_add_c(a[6], b[2], c3, c1, c2);
642     mul_add_c(a[5], b[3], c3, c1, c2);
643     mul_add_c(a[4], b[4], c3, c1, c2);
644     mul_add_c(a[3], b[5], c3, c1, c2);
645     mul_add_c(a[2], b[6], c3, c1, c2);
646     mul_add_c(a[1], b[7], c3, c1, c2);
647     r[8] = c3;
648     c3 = 0;
649     mul_add_c(a[2], b[7], c1, c2, c3);
650     mul_add_c(a[3], b[6], c1, c2, c3);
651     mul_add_c(a[4], b[5], c1, c2, c3);
652     mul_add_c(a[5], b[4], c1, c2, c3);
653     mul_add_c(a[6], b[3], c1, c2, c3);
654     mul_add_c(a[7], b[2], c1, c2, c3);
655     r[9] = c1;
656     c1 = 0;
657     mul_add_c(a[7], b[3], c2, c3, c1);
658     mul_add_c(a[6], b[4], c2, c3, c1);
659     mul_add_c(a[5], b[5], c2, c3, c1);
660     mul_add_c(a[4], b[6], c2, c3, c1);
661     mul_add_c(a[3], b[7], c2, c3, c1);
662     r[10] = c2;
663     c2 = 0;
664     mul_add_c(a[4], b[7], c3, c1, c2);
665     mul_add_c(a[5], b[6], c3, c1, c2);
666     mul_add_c(a[6], b[5], c3, c1, c2);
667     mul_add_c(a[7], b[4], c3, c1, c2);
668     r[11] = c3;
669     c3 = 0;
670     mul_add_c(a[7], b[5], c1, c2, c3);
671     mul_add_c(a[6], b[6], c1, c2, c3);
672     mul_add_c(a[5], b[7], c1, c2, c3);
673     r[12] = c1;
674     c1 = 0;
675     mul_add_c(a[6], b[7], c2, c3, c1);
676     mul_add_c(a[7], b[6], c2, c3, c1);
677     r[13] = c2;
678     c2 = 0;
679     mul_add_c(a[7], b[7], c3, c1, c2);
680     r[14] = c3;
681     r[15] = c1;
682 }
683
684 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
685 {
686     BN_ULONG c1, c2, c3;
687
688     c1 = 0;
689     c2 = 0;
690     c3 = 0;
691     mul_add_c(a[0], b[0], c1, c2, c3);
692     r[0] = c1;
693     c1 = 0;
694     mul_add_c(a[0], b[1], c2, c3, c1);
695     mul_add_c(a[1], b[0], c2, c3, c1);
696     r[1] = c2;
697     c2 = 0;
698     mul_add_c(a[2], b[0], c3, c1, c2);
699     mul_add_c(a[1], b[1], c3, c1, c2);
700     mul_add_c(a[0], b[2], c3, c1, c2);
701     r[2] = c3;
702     c3 = 0;
703     mul_add_c(a[0], b[3], c1, c2, c3);
704     mul_add_c(a[1], b[2], c1, c2, c3);
705     mul_add_c(a[2], b[1], c1, c2, c3);
706     mul_add_c(a[3], b[0], c1, c2, c3);
707     r[3] = c1;
708     c1 = 0;
709     mul_add_c(a[3], b[1], c2, c3, c1);
710     mul_add_c(a[2], b[2], c2, c3, c1);
711     mul_add_c(a[1], b[3], c2, c3, c1);
712     r[4] = c2;
713     c2 = 0;
714     mul_add_c(a[2], b[3], c3, c1, c2);
715     mul_add_c(a[3], b[2], c3, c1, c2);
716     r[5] = c3;
717     c3 = 0;
718     mul_add_c(a[3], b[3], c1, c2, c3);
719     r[6] = c1;
720     r[7] = c2;
721 }
722
723 void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
724 {
725     BN_ULONG c1, c2, c3;
726
727     c1 = 0;
728     c2 = 0;
729     c3 = 0;
730     sqr_add_c(a, 0, c1, c2, c3);
731     r[0] = c1;
732     c1 = 0;
733     sqr_add_c2(a, 1, 0, c2, c3, c1);
734     r[1] = c2;
735     c2 = 0;
736     sqr_add_c(a, 1, c3, c1, c2);
737     sqr_add_c2(a, 2, 0, c3, c1, c2);
738     r[2] = c3;
739     c3 = 0;
740     sqr_add_c2(a, 3, 0, c1, c2, c3);
741     sqr_add_c2(a, 2, 1, c1, c2, c3);
742     r[3] = c1;
743     c1 = 0;
744     sqr_add_c(a, 2, c2, c3, c1);
745     sqr_add_c2(a, 3, 1, c2, c3, c1);
746     sqr_add_c2(a, 4, 0, c2, c3, c1);
747     r[4] = c2;
748     c2 = 0;
749     sqr_add_c2(a, 5, 0, c3, c1, c2);
750     sqr_add_c2(a, 4, 1, c3, c1, c2);
751     sqr_add_c2(a, 3, 2, c3, c1, c2);
752     r[5] = c3;
753     c3 = 0;
754     sqr_add_c(a, 3, c1, c2, c3);
755     sqr_add_c2(a, 4, 2, c1, c2, c3);
756     sqr_add_c2(a, 5, 1, c1, c2, c3);
757     sqr_add_c2(a, 6, 0, c1, c2, c3);
758     r[6] = c1;
759     c1 = 0;
760     sqr_add_c2(a, 7, 0, c2, c3, c1);
761     sqr_add_c2(a, 6, 1, c2, c3, c1);
762     sqr_add_c2(a, 5, 2, c2, c3, c1);
763     sqr_add_c2(a, 4, 3, c2, c3, c1);
764     r[7] = c2;
765     c2 = 0;
766     sqr_add_c(a, 4, c3, c1, c2);
767     sqr_add_c2(a, 5, 3, c3, c1, c2);
768     sqr_add_c2(a, 6, 2, c3, c1, c2);
769     sqr_add_c2(a, 7, 1, c3, c1, c2);
770     r[8] = c3;
771     c3 = 0;
772     sqr_add_c2(a, 7, 2, c1, c2, c3);
773     sqr_add_c2(a, 6, 3, c1, c2, c3);
774     sqr_add_c2(a, 5, 4, c1, c2, c3);
775     r[9] = c1;
776     c1 = 0;
777     sqr_add_c(a, 5, c2, c3, c1);
778     sqr_add_c2(a, 6, 4, c2, c3, c1);
779     sqr_add_c2(a, 7, 3, c2, c3, c1);
780     r[10] = c2;
781     c2 = 0;
782     sqr_add_c2(a, 7, 4, c3, c1, c2);
783     sqr_add_c2(a, 6, 5, c3, c1, c2);
784     r[11] = c3;
785     c3 = 0;
786     sqr_add_c(a, 6, c1, c2, c3);
787     sqr_add_c2(a, 7, 5, c1, c2, c3);
788     r[12] = c1;
789     c1 = 0;
790     sqr_add_c2(a, 7, 6, c2, c3, c1);
791     r[13] = c2;
792     c2 = 0;
793     sqr_add_c(a, 7, c3, c1, c2);
794     r[14] = c3;
795     r[15] = c1;
796 }
797
798 void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
799 {
800     BN_ULONG c1, c2, c3;
801
802     c1 = 0;
803     c2 = 0;
804     c3 = 0;
805     sqr_add_c(a, 0, c1, c2, c3);
806     r[0] = c1;
807     c1 = 0;
808     sqr_add_c2(a, 1, 0, c2, c3, c1);
809     r[1] = c2;
810     c2 = 0;
811     sqr_add_c(a, 1, c3, c1, c2);
812     sqr_add_c2(a, 2, 0, c3, c1, c2);
813     r[2] = c3;
814     c3 = 0;
815     sqr_add_c2(a, 3, 0, c1, c2, c3);
816     sqr_add_c2(a, 2, 1, c1, c2, c3);
817     r[3] = c1;
818     c1 = 0;
819     sqr_add_c(a, 2, c2, c3, c1);
820     sqr_add_c2(a, 3, 1, c2, c3, c1);
821     r[4] = c2;
822     c2 = 0;
823     sqr_add_c2(a, 3, 2, c3, c1, c2);
824     r[5] = c3;
825     c3 = 0;
826     sqr_add_c(a, 3, c1, c2, c3);
827     r[6] = c1;
828     r[7] = c2;
829 }
830
831 # ifdef OPENSSL_NO_ASM
832 #  ifdef OPENSSL_BN_ASM_MONT
833 #   include <alloca.h>
834 /*
835  * This is essentially reference implementation, which may or may not
836  * result in performance improvement. E.g. on IA-32 this routine was
837  * observed to give 40% faster rsa1024 private key operations and 10%
838  * faster rsa4096 ones, while on AMD64 it improves rsa1024 sign only
839  * by 10% and *worsens* rsa4096 sign by 15%. Once again, it's a
840  * reference implementation, one to be used as starting point for
841  * platform-specific assembler. Mentioned numbers apply to compiler
842  * generated code compiled with and without -DOPENSSL_BN_ASM_MONT and
843  * can vary not only from platform to platform, but even for compiler
844  * versions. Assembler vs. assembler improvement coefficients can
845  * [and are known to] differ and are to be documented elsewhere.
846  */
847 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
848                 const BN_ULONG *np, const BN_ULONG *n0p, int num)
849 {
850     BN_ULONG c0, c1, ml, *tp, n0;
851 #   ifdef mul64
852     BN_ULONG mh;
853 #   endif
854     volatile BN_ULONG *vp;
855     int i = 0, j;
856
857 #   if 0                        /* template for platform-specific
858                                  * implementation */
859     if (ap == bp)
860         return bn_sqr_mont(rp, ap, np, n0p, num);
861 #   endif
862     vp = tp = alloca((num + 2) * sizeof(BN_ULONG));
863
864     n0 = *n0p;
865
866     c0 = 0;
867     ml = bp[0];
868 #   ifdef mul64
869     mh = HBITS(ml);
870     ml = LBITS(ml);
871     for (j = 0; j < num; ++j)
872         mul(tp[j], ap[j], ml, mh, c0);
873 #   else
874     for (j = 0; j < num; ++j)
875         mul(tp[j], ap[j], ml, c0);
876 #   endif
877
878     tp[num] = c0;
879     tp[num + 1] = 0;
880     goto enter;
881
882     for (i = 0; i < num; i++) {
883         c0 = 0;
884         ml = bp[i];
885 #   ifdef mul64
886         mh = HBITS(ml);
887         ml = LBITS(ml);
888         for (j = 0; j < num; ++j)
889             mul_add(tp[j], ap[j], ml, mh, c0);
890 #   else
891         for (j = 0; j < num; ++j)
892             mul_add(tp[j], ap[j], ml, c0);
893 #   endif
894         c1 = (tp[num] + c0) & BN_MASK2;
895         tp[num] = c1;
896         tp[num + 1] = (c1 < c0 ? 1 : 0);
897  enter:
898         c1 = tp[0];
899         ml = (c1 * n0) & BN_MASK2;
900         c0 = 0;
901 #   ifdef mul64
902         mh = HBITS(ml);
903         ml = LBITS(ml);
904         mul_add(c1, np[0], ml, mh, c0);
905 #   else
906         mul_add(c1, ml, np[0], c0);
907 #   endif
908         for (j = 1; j < num; j++) {
909             c1 = tp[j];
910 #   ifdef mul64
911             mul_add(c1, np[j], ml, mh, c0);
912 #   else
913             mul_add(c1, ml, np[j], c0);
914 #   endif
915             tp[j - 1] = c1 & BN_MASK2;
916         }
917         c1 = (tp[num] + c0) & BN_MASK2;
918         tp[num - 1] = c1;
919         tp[num] = tp[num + 1] + (c1 < c0 ? 1 : 0);
920     }
921
922     if (tp[num] != 0 || tp[num - 1] >= np[num - 1]) {
923         c0 = bn_sub_words(rp, tp, np, num);
924         if (tp[num] != 0 || c0 == 0) {
925             for (i = 0; i < num + 2; i++)
926                 vp[i] = 0;
927             return 1;
928         }
929     }
930     for (i = 0; i < num; i++)
931         rp[i] = tp[i], vp[i] = 0;
932     vp[num] = 0;
933     vp[num + 1] = 0;
934     return 1;
935 }
936 #  else
937 /*
938  * Return value of 0 indicates that multiplication/convolution was not
939  * performed to signal the caller to fall down to alternative/original
940  * code-path.
941  */
942 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
943                 const BN_ULONG *np, const BN_ULONG *n0, int num)
944 {
945     return 0;
946 }
947 #  endif                        /* OPENSSL_BN_ASM_MONT */
948 # endif
949
950 #else                           /* !BN_MUL_COMBA */
951
952 /* hmm... is it faster just to do a multiply? */
953 # undef bn_sqr_comba4
954 # undef bn_sqr_comba8
955 void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
956 {
957     BN_ULONG t[8];
958     bn_sqr_normal(r, a, 4, t);
959 }
960
961 void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
962 {
963     BN_ULONG t[16];
964     bn_sqr_normal(r, a, 8, t);
965 }
966
967 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
968 {
969     r[4] = bn_mul_words(&(r[0]), a, 4, b[0]);
970     r[5] = bn_mul_add_words(&(r[1]), a, 4, b[1]);
971     r[6] = bn_mul_add_words(&(r[2]), a, 4, b[2]);
972     r[7] = bn_mul_add_words(&(r[3]), a, 4, b[3]);
973 }
974
975 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
976 {
977     r[8] = bn_mul_words(&(r[0]), a, 8, b[0]);
978     r[9] = bn_mul_add_words(&(r[1]), a, 8, b[1]);
979     r[10] = bn_mul_add_words(&(r[2]), a, 8, b[2]);
980     r[11] = bn_mul_add_words(&(r[3]), a, 8, b[3]);
981     r[12] = bn_mul_add_words(&(r[4]), a, 8, b[4]);
982     r[13] = bn_mul_add_words(&(r[5]), a, 8, b[5]);
983     r[14] = bn_mul_add_words(&(r[6]), a, 8, b[6]);
984     r[15] = bn_mul_add_words(&(r[7]), a, 8, b[7]);
985 }
986
987 # ifdef OPENSSL_NO_ASM
988 #  ifdef OPENSSL_BN_ASM_MONT
989 #   include <alloca.h>
990 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
991                 const BN_ULONG *np, const BN_ULONG *n0p, int num)
992 {
993     BN_ULONG c0, c1, *tp, n0 = *n0p;
994     volatile BN_ULONG *vp;
995     int i = 0, j;
996
997     vp = tp = alloca((num + 2) * sizeof(BN_ULONG));
998
999     for (i = 0; i <= num; i++)
1000         tp[i] = 0;
1001
1002     for (i = 0; i < num; i++) {
1003         c0 = bn_mul_add_words(tp, ap, num, bp[i]);
1004         c1 = (tp[num] + c0) & BN_MASK2;
1005         tp[num] = c1;
1006         tp[num + 1] = (c1 < c0 ? 1 : 0);
1007
1008         c0 = bn_mul_add_words(tp, np, num, tp[0] * n0);
1009         c1 = (tp[num] + c0) & BN_MASK2;
1010         tp[num] = c1;
1011         tp[num + 1] += (c1 < c0 ? 1 : 0);
1012         for (j = 0; j <= num; j++)
1013             tp[j] = tp[j + 1];
1014     }
1015
1016     if (tp[num] != 0 || tp[num - 1] >= np[num - 1]) {
1017         c0 = bn_sub_words(rp, tp, np, num);
1018         if (tp[num] != 0 || c0 == 0) {
1019             for (i = 0; i < num + 2; i++)
1020                 vp[i] = 0;
1021             return 1;
1022         }
1023     }
1024     for (i = 0; i < num; i++)
1025         rp[i] = tp[i], vp[i] = 0;
1026     vp[num] = 0;
1027     vp[num + 1] = 0;
1028     return 1;
1029 }
1030 #  else
1031 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
1032                 const BN_ULONG *np, const BN_ULONG *n0, int num)
1033 {
1034     return 0;
1035 }
1036 #  endif                        /* OPENSSL_BN_ASM_MONT */
1037 # endif
1038
1039 #endif                          /* !BN_MUL_COMBA */