1f28f64abbfaad29f494c81b13ef97844b676944
[openssl.git] / crypto / bn / bn_mul.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 "internal/cryptlib.h"
12 #include "bn_lcl.h"
13
14 #if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
15 /*
16  * Here follows specialised variants of bn_add_words() and bn_sub_words().
17  * They have the property performing operations on arrays of different sizes.
18  * The sizes of those arrays is expressed through cl, which is the common
19  * length ( basically, min(len(a),len(b)) ), and dl, which is the delta
20  * between the two lengths, calculated as len(a)-len(b). All lengths are the
21  * number of BN_ULONGs...  For the operations that require a result array as
22  * parameter, it must have the length cl+abs(dl). These functions should
23  * probably end up in bn_asm.c as soon as there are assembler counterparts
24  * for the systems that use assembler files.
25  */
26
27 BN_ULONG bn_sub_part_words(BN_ULONG *r,
28                            const BN_ULONG *a, const BN_ULONG *b,
29                            int cl, int dl)
30 {
31     BN_ULONG c, t;
32
33     assert(cl >= 0);
34     c = bn_sub_words(r, a, b, cl);
35
36     if (dl == 0)
37         return c;
38
39     r += cl;
40     a += cl;
41     b += cl;
42
43     if (dl < 0) {
44         for (;;) {
45             t = b[0];
46             r[0] = (0 - t - c) & BN_MASK2;
47             if (t != 0)
48                 c = 1;
49             if (++dl >= 0)
50                 break;
51
52             t = b[1];
53             r[1] = (0 - t - c) & BN_MASK2;
54             if (t != 0)
55                 c = 1;
56             if (++dl >= 0)
57                 break;
58
59             t = b[2];
60             r[2] = (0 - t - c) & BN_MASK2;
61             if (t != 0)
62                 c = 1;
63             if (++dl >= 0)
64                 break;
65
66             t = b[3];
67             r[3] = (0 - t - c) & BN_MASK2;
68             if (t != 0)
69                 c = 1;
70             if (++dl >= 0)
71                 break;
72
73             b += 4;
74             r += 4;
75         }
76     } else {
77         int save_dl = dl;
78         while (c) {
79             t = a[0];
80             r[0] = (t - c) & BN_MASK2;
81             if (t != 0)
82                 c = 0;
83             if (--dl <= 0)
84                 break;
85
86             t = a[1];
87             r[1] = (t - c) & BN_MASK2;
88             if (t != 0)
89                 c = 0;
90             if (--dl <= 0)
91                 break;
92
93             t = a[2];
94             r[2] = (t - c) & BN_MASK2;
95             if (t != 0)
96                 c = 0;
97             if (--dl <= 0)
98                 break;
99
100             t = a[3];
101             r[3] = (t - c) & BN_MASK2;
102             if (t != 0)
103                 c = 0;
104             if (--dl <= 0)
105                 break;
106
107             save_dl = dl;
108             a += 4;
109             r += 4;
110         }
111         if (dl > 0) {
112             if (save_dl > dl) {
113                 switch (save_dl - dl) {
114                 case 1:
115                     r[1] = a[1];
116                     if (--dl <= 0)
117                         break;
118                 case 2:
119                     r[2] = a[2];
120                     if (--dl <= 0)
121                         break;
122                 case 3:
123                     r[3] = a[3];
124                     if (--dl <= 0)
125                         break;
126                 }
127                 a += 4;
128                 r += 4;
129             }
130         }
131         if (dl > 0) {
132             for (;;) {
133                 r[0] = a[0];
134                 if (--dl <= 0)
135                     break;
136                 r[1] = a[1];
137                 if (--dl <= 0)
138                     break;
139                 r[2] = a[2];
140                 if (--dl <= 0)
141                     break;
142                 r[3] = a[3];
143                 if (--dl <= 0)
144                     break;
145
146                 a += 4;
147                 r += 4;
148             }
149         }
150     }
151     return c;
152 }
153 #endif
154
155 #ifdef BN_RECURSION
156 /*
157  * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of
158  * Computer Programming, Vol. 2)
159  */
160
161 /*-
162  * r is 2*n2 words in size,
163  * a and b are both n2 words in size.
164  * n2 must be a power of 2.
165  * We multiply and return the result.
166  * t must be 2*n2 words in size
167  * We calculate
168  * a[0]*b[0]
169  * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
170  * a[1]*b[1]
171  */
172 /* dnX may not be positive, but n2/2+dnX has to be */
173 void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
174                       int dna, int dnb, BN_ULONG *t)
175 {
176     int n = n2 / 2, c1, c2;
177     int tna = n + dna, tnb = n + dnb;
178     unsigned int neg, zero;
179     BN_ULONG ln, lo, *p;
180
181 # ifdef BN_MUL_COMBA
182 #  if 0
183     if (n2 == 4) {
184         bn_mul_comba4(r, a, b);
185         return;
186     }
187 #  endif
188     /*
189      * Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete
190      * [steve]
191      */
192     if (n2 == 8 && dna == 0 && dnb == 0) {
193         bn_mul_comba8(r, a, b);
194         return;
195     }
196 # endif                         /* BN_MUL_COMBA */
197     /* Else do normal multiply */
198     if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
199         bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
200         if ((dna + dnb) < 0)
201             memset(&r[2 * n2 + dna + dnb], 0,
202                    sizeof(BN_ULONG) * -(dna + dnb));
203         return;
204     }
205     /* r=(a[0]-a[1])*(b[1]-b[0]) */
206     c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
207     c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
208     zero = neg = 0;
209     switch (c1 * 3 + c2) {
210     case -4:
211         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
212         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
213         break;
214     case -3:
215         zero = 1;
216         break;
217     case -2:
218         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
219         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
220         neg = 1;
221         break;
222     case -1:
223     case 0:
224     case 1:
225         zero = 1;
226         break;
227     case 2:
228         bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
229         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
230         neg = 1;
231         break;
232     case 3:
233         zero = 1;
234         break;
235     case 4:
236         bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
237         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
238         break;
239     }
240
241 # ifdef BN_MUL_COMBA
242     if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take
243                                            * extra args to do this well */
244         if (!zero)
245             bn_mul_comba4(&(t[n2]), t, &(t[n]));
246         else
247             memset(&t[n2], 0, sizeof(*t) * 8);
248
249         bn_mul_comba4(r, a, b);
250         bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
251     } else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could
252                                                   * take extra args to do
253                                                   * this well */
254         if (!zero)
255             bn_mul_comba8(&(t[n2]), t, &(t[n]));
256         else
257             memset(&t[n2], 0, sizeof(*t) * 16);
258
259         bn_mul_comba8(r, a, b);
260         bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
261     } else
262 # endif                         /* BN_MUL_COMBA */
263     {
264         p = &(t[n2 * 2]);
265         if (!zero)
266             bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
267         else
268             memset(&t[n2], 0, sizeof(*t) * n2);
269         bn_mul_recursive(r, a, b, n, 0, 0, p);
270         bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
271     }
272
273     /*-
274      * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
275      * r[10] holds (a[0]*b[0])
276      * r[32] holds (b[1]*b[1])
277      */
278
279     c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
280
281     if (neg) {                  /* if t[32] is negative */
282         c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
283     } else {
284         /* Might have a carry */
285         c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
286     }
287
288     /*-
289      * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
290      * r[10] holds (a[0]*b[0])
291      * r[32] holds (b[1]*b[1])
292      * c1 holds the carry bits
293      */
294     c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
295     if (c1) {
296         p = &(r[n + n2]);
297         lo = *p;
298         ln = (lo + c1) & BN_MASK2;
299         *p = ln;
300
301         /*
302          * The overflow will stop before we over write words we should not
303          * overwrite
304          */
305         if (ln < (BN_ULONG)c1) {
306             do {
307                 p++;
308                 lo = *p;
309                 ln = (lo + 1) & BN_MASK2;
310                 *p = ln;
311             } while (ln == 0);
312         }
313     }
314 }
315
316 /*
317  * n+tn is the word length t needs to be n*4 is size, as does r
318  */
319 /* tnX may not be negative but less than n */
320 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
321                            int tna, int tnb, BN_ULONG *t)
322 {
323     int i, j, n2 = n * 2;
324     int c1, c2, neg;
325     BN_ULONG ln, lo, *p;
326
327     if (n < 8) {
328         bn_mul_normal(r, a, n + tna, b, n + tnb);
329         return;
330     }
331
332     /* r=(a[0]-a[1])*(b[1]-b[0]) */
333     c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
334     c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
335     neg = 0;
336     switch (c1 * 3 + c2) {
337     case -4:
338         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
339         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
340         break;
341     case -3:
342         /* break; */
343     case -2:
344         bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
345         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
346         neg = 1;
347         break;
348     case -1:
349     case 0:
350     case 1:
351         /* break; */
352     case 2:
353         bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
354         bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
355         neg = 1;
356         break;
357     case 3:
358         /* break; */
359     case 4:
360         bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
361         bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
362         break;
363     }
364     /*
365      * The zero case isn't yet implemented here. The speedup would probably
366      * be negligible.
367      */
368 # if 0
369     if (n == 4) {
370         bn_mul_comba4(&(t[n2]), t, &(t[n]));
371         bn_mul_comba4(r, a, b);
372         bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
373         memset(&r[n2 + tn * 2], 0, sizeof(*r) * (n2 - tn * 2));
374     } else
375 # endif
376     if (n == 8) {
377         bn_mul_comba8(&(t[n2]), t, &(t[n]));
378         bn_mul_comba8(r, a, b);
379         bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
380         memset(&r[n2 + tna + tnb], 0, sizeof(*r) * (n2 - tna - tnb));
381     } else {
382         p = &(t[n2 * 2]);
383         bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
384         bn_mul_recursive(r, a, b, n, 0, 0, p);
385         i = n / 2;
386         /*
387          * If there is only a bottom half to the number, just do it
388          */
389         if (tna > tnb)
390             j = tna - i;
391         else
392             j = tnb - i;
393         if (j == 0) {
394             bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
395                              i, tna - i, tnb - i, p);
396             memset(&r[n2 + i * 2], 0, sizeof(*r) * (n2 - i * 2));
397         } else if (j > 0) {     /* eg, n == 16, i == 8 and tn == 11 */
398             bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
399                                   i, tna - i, tnb - i, p);
400             memset(&(r[n2 + tna + tnb]), 0,
401                    sizeof(BN_ULONG) * (n2 - tna - tnb));
402         } else {                /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
403
404             memset(&r[n2], 0, sizeof(*r) * n2);
405             if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL
406                 && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
407                 bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
408             } else {
409                 for (;;) {
410                     i /= 2;
411                     /*
412                      * these simplified conditions work exclusively because
413                      * difference between tna and tnb is 1 or 0
414                      */
415                     if (i < tna || i < tnb) {
416                         bn_mul_part_recursive(&(r[n2]),
417                                               &(a[n]), &(b[n]),
418                                               i, tna - i, tnb - i, p);
419                         break;
420                     } else if (i == tna || i == tnb) {
421                         bn_mul_recursive(&(r[n2]),
422                                          &(a[n]), &(b[n]),
423                                          i, tna - i, tnb - i, p);
424                         break;
425                     }
426                 }
427             }
428         }
429     }
430
431     /*-
432      * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
433      * r[10] holds (a[0]*b[0])
434      * r[32] holds (b[1]*b[1])
435      */
436
437     c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
438
439     if (neg) {                  /* if t[32] is negative */
440         c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
441     } else {
442         /* Might have a carry */
443         c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
444     }
445
446     /*-
447      * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
448      * r[10] holds (a[0]*b[0])
449      * r[32] holds (b[1]*b[1])
450      * c1 holds the carry bits
451      */
452     c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
453     if (c1) {
454         p = &(r[n + n2]);
455         lo = *p;
456         ln = (lo + c1) & BN_MASK2;
457         *p = ln;
458
459         /*
460          * The overflow will stop before we over write words we should not
461          * overwrite
462          */
463         if (ln < (BN_ULONG)c1) {
464             do {
465                 p++;
466                 lo = *p;
467                 ln = (lo + 1) & BN_MASK2;
468                 *p = ln;
469             } while (ln == 0);
470         }
471     }
472 }
473
474 /*-
475  * a and b must be the same size, which is n2.
476  * r needs to be n2 words and t needs to be n2*2
477  */
478 void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
479                           BN_ULONG *t)
480 {
481     int n = n2 / 2;
482
483     bn_mul_recursive(r, a, b, n, 0, 0, &(t[0]));
484     if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
485         bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
486         bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
487         bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
488         bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
489     } else {
490         bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
491         bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
492         bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
493         bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
494     }
495 }
496 #endif                          /* BN_RECURSION */
497
498 int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
499 {
500     int ret = 0;
501     int top, al, bl;
502     BIGNUM *rr;
503 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
504     int i;
505 #endif
506 #ifdef BN_RECURSION
507     BIGNUM *t = NULL;
508     int j = 0, k;
509 #endif
510
511     bn_check_top(a);
512     bn_check_top(b);
513     bn_check_top(r);
514
515     al = a->top;
516     bl = b->top;
517
518     if ((al == 0) || (bl == 0)) {
519         BN_zero(r);
520         return (1);
521     }
522     top = al + bl;
523
524     BN_CTX_start(ctx);
525     if ((r == a) || (r == b)) {
526         if ((rr = BN_CTX_get(ctx)) == NULL)
527             goto err;
528     } else
529         rr = r;
530
531 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
532     i = al - bl;
533 #endif
534 #ifdef BN_MUL_COMBA
535     if (i == 0) {
536 # if 0
537         if (al == 4) {
538             if (bn_wexpand(rr, 8) == NULL)
539                 goto err;
540             rr->top = 8;
541             bn_mul_comba4(rr->d, a->d, b->d);
542             goto end;
543         }
544 # endif
545         if (al == 8) {
546             if (bn_wexpand(rr, 16) == NULL)
547                 goto err;
548             rr->top = 16;
549             bn_mul_comba8(rr->d, a->d, b->d);
550             goto end;
551         }
552     }
553 #endif                          /* BN_MUL_COMBA */
554 #ifdef BN_RECURSION
555     if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
556         if (i >= -1 && i <= 1) {
557             /*
558              * Find out the power of two lower or equal to the longest of the
559              * two numbers
560              */
561             if (i >= 0) {
562                 j = BN_num_bits_word((BN_ULONG)al);
563             }
564             if (i == -1) {
565                 j = BN_num_bits_word((BN_ULONG)bl);
566             }
567             j = 1 << (j - 1);
568             assert(j <= al || j <= bl);
569             k = j + j;
570             t = BN_CTX_get(ctx);
571             if (t == NULL)
572                 goto err;
573             if (al > j || bl > j) {
574                 if (bn_wexpand(t, k * 4) == NULL)
575                     goto err;
576                 if (bn_wexpand(rr, k * 4) == NULL)
577                     goto err;
578                 bn_mul_part_recursive(rr->d, a->d, b->d,
579                                       j, al - j, bl - j, t->d);
580             } else {            /* al <= j || bl <= j */
581
582                 if (bn_wexpand(t, k * 2) == NULL)
583                     goto err;
584                 if (bn_wexpand(rr, k * 2) == NULL)
585                     goto err;
586                 bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);
587             }
588             rr->top = top;
589             goto end;
590         }
591 # if 0
592         if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) {
593             BIGNUM *tmp_bn = (BIGNUM *)b;
594             if (bn_wexpand(tmp_bn, al) == NULL)
595                 goto err;
596             tmp_bn->d[bl] = 0;
597             bl++;
598             i--;
599         } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
600             BIGNUM *tmp_bn = (BIGNUM *)a;
601             if (bn_wexpand(tmp_bn, bl) == NULL)
602                 goto err;
603             tmp_bn->d[al] = 0;
604             al++;
605             i++;
606         }
607         if (i == 0) {
608             /* symmetric and > 4 */
609             /* 16 or larger */
610             j = BN_num_bits_word((BN_ULONG)al);
611             j = 1 << (j - 1);
612             k = j + j;
613             t = BN_CTX_get(ctx);
614             if (al == j) {      /* exact multiple */
615                 if (bn_wexpand(t, k * 2) == NULL)
616                     goto err;
617                 if (bn_wexpand(rr, k * 2) == NULL)
618                     goto err;
619                 bn_mul_recursive(rr->d, a->d, b->d, al, t->d);
620             } else {
621                 if (bn_wexpand(t, k * 4) == NULL)
622                     goto err;
623                 if (bn_wexpand(rr, k * 4) == NULL)
624                     goto err;
625                 bn_mul_part_recursive(rr->d, a->d, b->d, al - j, j, t->d);
626             }
627             rr->top = top;
628             goto end;
629         }
630 # endif
631     }
632 #endif                          /* BN_RECURSION */
633     if (bn_wexpand(rr, top) == NULL)
634         goto err;
635     rr->top = top;
636     bn_mul_normal(rr->d, a->d, al, b->d, bl);
637
638 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
639  end:
640 #endif
641     rr->neg = a->neg ^ b->neg;
642     bn_correct_top(rr);
643     if (r != rr && BN_copy(r, rr) == NULL)
644         goto err;
645
646     ret = 1;
647  err:
648     bn_check_top(r);
649     BN_CTX_end(ctx);
650     return (ret);
651 }
652
653 void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
654 {
655     BN_ULONG *rr;
656
657     if (na < nb) {
658         int itmp;
659         BN_ULONG *ltmp;
660
661         itmp = na;
662         na = nb;
663         nb = itmp;
664         ltmp = a;
665         a = b;
666         b = ltmp;
667
668     }
669     rr = &(r[na]);
670     if (nb <= 0) {
671         (void)bn_mul_words(r, a, na, 0);
672         return;
673     } else
674         rr[0] = bn_mul_words(r, a, na, b[0]);
675
676     for (;;) {
677         if (--nb <= 0)
678             return;
679         rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
680         if (--nb <= 0)
681             return;
682         rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
683         if (--nb <= 0)
684             return;
685         rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
686         if (--nb <= 0)
687             return;
688         rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
689         rr += 4;
690         r += 4;
691         b += 4;
692     }
693 }
694
695 void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
696 {
697     bn_mul_words(r, a, n, b[0]);
698
699     for (;;) {
700         if (--n <= 0)
701             return;
702         bn_mul_add_words(&(r[1]), a, n, b[1]);
703         if (--n <= 0)
704             return;
705         bn_mul_add_words(&(r[2]), a, n, b[2]);
706         if (--n <= 0)
707             return;
708         bn_mul_add_words(&(r[3]), a, n, b[3]);
709         if (--n <= 0)
710             return;
711         bn_mul_add_words(&(r[4]), a, n, b[4]);
712         r += 4;
713         b += 4;
714     }
715 }