Coverage Report

Created: 2024-11-21 07:03

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