CoCalc -- bn

GitHub Repository: freebsd/freebsd-src
Path: blob/main/crypto/openssl/crypto/bn/bn_asm.c
¹⁰⁶⁷⁵¹ views
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

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) || ((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
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 */
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

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

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

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

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

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
 */
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
 */
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? */
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

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

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

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>
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
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

1083
Product

Resources

Company
