← Back to branch summary

~ubuntu-branches/ubuntu/hardy/openssl/hardy-security

« back to all changes in this revision

Viewing changes to crypto/bn/bn_asm.c

  • Committer: Bazaar Package Importer
  • Author(s): Christoph Martin
  • Date: 2004-05-24 17:02:29 UTC
  • Revision ID: james.westby@ubuntu.com-20040524170229-ixlo08bbbly0xied
Tags: upstream-0.9.7d
Import upstream version 0.9.7d

Show diffs side-by-side

added added

removed removed

Lines of Context:
crypto/bn/bn_asm.c
 
1
/* crypto/bn/bn_asm.c */
 
2
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
 
3
 * All rights reserved.
 
4
 *
 
5
 * This package is an SSL implementation written
 
6
 * by Eric Young (eay@cryptsoft.com).
 
7
 * The implementation was written so as to conform with Netscapes SSL.
 
8
 * 
 
9
 * This library is free for commercial and non-commercial use as long as
 
10
 * the following conditions are aheared to.  The following conditions
 
11
 * apply to all code found in this distribution, be it the RC4, RSA,
 
12
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 
13
 * included with this distribution is covered by the same copyright terms
 
14
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
 
15
 * 
 
16
 * Copyright remains Eric Young's, and as such any Copyright notices in
 
17
 * the code are not to be removed.
 
18
 * If this package is used in a product, Eric Young should be given attribution
 
19
 * as the author of the parts of the library used.
 
20
 * This can be in the form of a textual message at program startup or
 
21
 * in documentation (online or textual) provided with the package.
 
22
 * 
 
23
 * Redistribution and use in source and binary forms, with or without
 
24
 * modification, are permitted provided that the following conditions
 
25
 * are met:
 
26
 * 1. Redistributions of source code must retain the copyright
 
27
 *    notice, this list of conditions and the following disclaimer.
 
28
 * 2. Redistributions in binary form must reproduce the above copyright
 
29
 *    notice, this list of conditions and the following disclaimer in the
 
30
 *    documentation and/or other materials provided with the distribution.
 
31
 * 3. All advertising materials mentioning features or use of this software
 
32
 *    must display the following acknowledgement:
 
33
 *    "This product includes cryptographic software written by
 
34
 *     Eric Young (eay@cryptsoft.com)"
 
35
 *    The word 'cryptographic' can be left out if the rouines from the library
 
36
 *    being used are not cryptographic related :-).
 
37
 * 4. If you include any Windows specific code (or a derivative thereof) from 
 
38
 *    the apps directory (application code) you must include an acknowledgement:
 
39
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
 
40
 * 
 
41
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 
42
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
43
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
44
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 
45
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
46
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
47
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
48
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
49
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
50
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
51
 * SUCH DAMAGE.
 
52
 * 
 
53
 * The licence and distribution terms for any publically available version or
 
54
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 
55
 * copied and put under another distribution licence
 
56
 * [including the GNU Public Licence.]
 
57
 */
 
58
 
 
59
#ifndef BN_DEBUG
 
60
# undef NDEBUG /* avoid conflicting definitions */
 
61
# define NDEBUG
 
62
#endif
 
63
 
 
64
#include <stdio.h>
 
65
#include <assert.h>
 
66
#include "cryptlib.h"
 
67
#include "bn_lcl.h"
 
68
 
 
69
#if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
 
70
 
 
71
BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
 
72
        {
 
73
        BN_ULONG c1=0;
 
74
 
 
75
        assert(num >= 0);
 
76
        if (num <= 0) return(c1);
 
77
 
 
78
        while (num&~3)
 
79
                {
 
80
                mul_add(rp[0],ap[0],w,c1);
 
81
                mul_add(rp[1],ap[1],w,c1);
 
82
                mul_add(rp[2],ap[2],w,c1);
 
83
                mul_add(rp[3],ap[3],w,c1);
 
84
                ap+=4; rp+=4; num-=4;
 
85
                }
 
86
        if (num)
 
87
                {
 
88
                mul_add(rp[0],ap[0],w,c1); if (--num==0) return c1;
 
89
                mul_add(rp[1],ap[1],w,c1); if (--num==0) return c1;
 
90
                mul_add(rp[2],ap[2],w,c1); return c1;
 
91
                }
 
92
        
 
93
        return(c1);
 
94
        } 
 
95
 
 
96
BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
 
97
        {
 
98
        BN_ULONG c1=0;
 
99
 
 
100
        assert(num >= 0);
 
101
        if (num <= 0) return(c1);
 
102
 
 
103
        while (num&~3)
 
104
                {
 
105
                mul(rp[0],ap[0],w,c1);
 
106
                mul(rp[1],ap[1],w,c1);
 
107
                mul(rp[2],ap[2],w,c1);
 
108
                mul(rp[3],ap[3],w,c1);
 
109
                ap+=4; rp+=4; num-=4;
 
110
                }
 
111
        if (num)
 
112
                {
 
113
                mul(rp[0],ap[0],w,c1); if (--num == 0) return c1;
 
114
                mul(rp[1],ap[1],w,c1); if (--num == 0) return c1;
 
115
                mul(rp[2],ap[2],w,c1);
 
116
                }
 
117
        return(c1);
 
118
        } 
 
119
 
 
120
void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
 
121
        {
 
122
        assert(n >= 0);
 
123
        if (n <= 0) return;
 
124
        while (n&~3)
 
125
                {
 
126
                sqr(r[0],r[1],a[0]);
 
127
                sqr(r[2],r[3],a[1]);
 
128
                sqr(r[4],r[5],a[2]);
 
129
                sqr(r[6],r[7],a[3]);
 
130
                a+=4; r+=8; n-=4;
 
131
                }
 
132
        if (n)
 
133
                {
 
134
                sqr(r[0],r[1],a[0]); if (--n == 0) return;
 
135
                sqr(r[2],r[3],a[1]); if (--n == 0) return;
 
136
                sqr(r[4],r[5],a[2]);
 
137
                }
 
138
        }
 
139
 
 
140
#else /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
 
141
 
 
142
BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
 
143
        {
 
144
        BN_ULONG c=0;
 
145
        BN_ULONG bl,bh;
 
146
 
 
147
        assert(num >= 0);
 
148
        if (num <= 0) return((BN_ULONG)0);
 
149
 
 
150
        bl=LBITS(w);
 
151
        bh=HBITS(w);
 
152
 
 
153
        for (;;)
 
154
                {
 
155
                mul_add(rp[0],ap[0],bl,bh,c);
 
156
                if (--num == 0) break;
 
157
                mul_add(rp[1],ap[1],bl,bh,c);
 
158
                if (--num == 0) break;
 
159
                mul_add(rp[2],ap[2],bl,bh,c);
 
160
                if (--num == 0) break;
 
161
                mul_add(rp[3],ap[3],bl,bh,c);
 
162
                if (--num == 0) break;
 
163
                ap+=4;
 
164
                rp+=4;
 
165
                }
 
166
        return(c);
 
167
        } 
 
168
 
 
169
BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
 
170
        {
 
171
        BN_ULONG carry=0;
 
172
        BN_ULONG bl,bh;
 
173
 
 
174
        assert(num >= 0);
 
175
        if (num <= 0) return((BN_ULONG)0);
 
176
 
 
177
        bl=LBITS(w);
 
178
        bh=HBITS(w);
 
179
 
 
180
        for (;;)
 
181
                {
 
182
                mul(rp[0],ap[0],bl,bh,carry);
 
183
                if (--num == 0) break;
 
184
                mul(rp[1],ap[1],bl,bh,carry);
 
185
                if (--num == 0) break;
 
186
                mul(rp[2],ap[2],bl,bh,carry);
 
187
                if (--num == 0) break;
 
188
                mul(rp[3],ap[3],bl,bh,carry);
 
189
                if (--num == 0) break;
 
190
                ap+=4;
 
191
                rp+=4;
 
192
                }
 
193
        return(carry);
 
194
        } 
 
195
 
 
196
void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
 
197
        {
 
198
        assert(n >= 0);
 
199
        if (n <= 0) return;
 
200
        for (;;)
 
201
                {
 
202
                sqr64(r[0],r[1],a[0]);
 
203
                if (--n == 0) break;
 
204
 
 
205
                sqr64(r[2],r[3],a[1]);
 
206
                if (--n == 0) break;
 
207
 
 
208
                sqr64(r[4],r[5],a[2]);
 
209
                if (--n == 0) break;
 
210
 
 
211
                sqr64(r[6],r[7],a[3]);
 
212
                if (--n == 0) break;
 
213
 
 
214
                a+=4;
 
215
                r+=8;
 
216
                }
 
217
        }
 
218
 
 
219
#endif /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
 
220
 
 
221
#if defined(BN_LLONG) && defined(BN_DIV2W)
 
222
 
 
223
BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
 
224
        {
 
225
        return((BN_ULONG)(((((BN_ULLONG)h)<<BN_BITS2)|l)/(BN_ULLONG)d));
 
226
        }
 
227
 
 
228
#else
 
229
 
 
230
/* Divide h,l by d and return the result. */
 
231
/* I need to test this some more :-( */
 
232
BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
 
233
        {
 
234
        BN_ULONG dh,dl,q,ret=0,th,tl,t;
 
235
        int i,count=2;
 
236
 
 
237
        if (d == 0) return(BN_MASK2);
 
238
 
 
239
        i=BN_num_bits_word(d);
 
240
        assert((i == BN_BITS2) || (h > (BN_ULONG)1<<i));
 
241
 
 
242
        i=BN_BITS2-i;
 
243
        if (h >= d) h-=d;
 
244
 
 
245
        if (i)
 
246
                {
 
247
                d<<=i;
 
248
                h=(h<<i)|(l>>(BN_BITS2-i));
 
249
                l<<=i;
 
250
                }
 
251
        dh=(d&BN_MASK2h)>>BN_BITS4;
 
252
        dl=(d&BN_MASK2l);
 
253
        for (;;)
 
254
                {
 
255
                if ((h>>BN_BITS4) == dh)
 
256
                        q=BN_MASK2l;
 
257
                else
 
258
                        q=h/dh;
 
259
 
 
260
                th=q*dh;
 
261
                tl=dl*q;
 
262
                for (;;)
 
263
                        {
 
264
                        t=h-th;
 
265
                        if ((t&BN_MASK2h) ||
 
266
                                ((tl) <= (
 
267
                                        (t<<BN_BITS4)|
 
268
                                        ((l&BN_MASK2h)>>BN_BITS4))))
 
269
                                break;
 
270
                        q--;
 
271
                        th-=dh;
 
272
                        tl-=dl;
 
273
                        }
 
274
                t=(tl>>BN_BITS4);
 
275
                tl=(tl<<BN_BITS4)&BN_MASK2h;
 
276
                th+=t;
 
277
 
 
278
                if (l < tl) th++;
 
279
                l-=tl;
 
280
                if (h < th)
 
281
                        {
 
282
                        h+=d;
 
283
                        q--;
 
284
                        }
 
285
                h-=th;
 
286
 
 
287
                if (--count == 0) break;
 
288
 
 
289
                ret=q<<BN_BITS4;
 
290
                h=((h<<BN_BITS4)|(l>>BN_BITS4))&BN_MASK2;
 
291
                l=(l&BN_MASK2l)<<BN_BITS4;
 
292
                }
 
293
        ret|=q;
 
294
        return(ret);
 
295
        }
 
296
#endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
 
297
 
 
298
#ifdef BN_LLONG
 
299
BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
 
300
        {
 
301
        BN_ULLONG ll=0;
 
302
 
 
303
        assert(n >= 0);
 
304
        if (n <= 0) return((BN_ULONG)0);
 
305
 
 
306
        for (;;)
 
307
                {
 
308
                ll+=(BN_ULLONG)a[0]+b[0];
 
309
                r[0]=(BN_ULONG)ll&BN_MASK2;
 
310
                ll>>=BN_BITS2;
 
311
                if (--n <= 0) break;
 
312
 
 
313
                ll+=(BN_ULLONG)a[1]+b[1];
 
314
                r[1]=(BN_ULONG)ll&BN_MASK2;
 
315
                ll>>=BN_BITS2;
 
316
                if (--n <= 0) break;
 
317
 
 
318
                ll+=(BN_ULLONG)a[2]+b[2];
 
319
                r[2]=(BN_ULONG)ll&BN_MASK2;
 
320
                ll>>=BN_BITS2;
 
321
                if (--n <= 0) break;
 
322
 
 
323
                ll+=(BN_ULLONG)a[3]+b[3];
 
324
                r[3]=(BN_ULONG)ll&BN_MASK2;
 
325
                ll>>=BN_BITS2;
 
326
                if (--n <= 0) break;
 
327
 
 
328
                a+=4;
 
329
                b+=4;
 
330
                r+=4;
 
331
                }
 
332
        return((BN_ULONG)ll);
 
333
        }
 
334
#else /* !BN_LLONG */
 
335
BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
 
336
        {
 
337
        BN_ULONG c,l,t;
 
338
 
 
339
        assert(n >= 0);
 
340
        if (n <= 0) return((BN_ULONG)0);
 
341
 
 
342
        c=0;
 
343
        for (;;)
 
344
                {
 
345
                t=a[0];
 
346
                t=(t+c)&BN_MASK2;
 
347
                c=(t < c);
 
348
                l=(t+b[0])&BN_MASK2;
 
349
                c+=(l < t);
 
350
                r[0]=l;
 
351
                if (--n <= 0) break;
 
352
 
 
353
                t=a[1];
 
354
                t=(t+c)&BN_MASK2;
 
355
                c=(t < c);
 
356
                l=(t+b[1])&BN_MASK2;
 
357
                c+=(l < t);
 
358
                r[1]=l;
 
359
                if (--n <= 0) break;
 
360
 
 
361
                t=a[2];
 
362
                t=(t+c)&BN_MASK2;
 
363
                c=(t < c);
 
364
                l=(t+b[2])&BN_MASK2;
 
365
                c+=(l < t);
 
366
                r[2]=l;
 
367
                if (--n <= 0) break;
 
368
 
 
369
                t=a[3];
 
370
                t=(t+c)&BN_MASK2;
 
371
                c=(t < c);
 
372
                l=(t+b[3])&BN_MASK2;
 
373
                c+=(l < t);
 
374
                r[3]=l;
 
375
                if (--n <= 0) break;
 
376
 
 
377
                a+=4;
 
378
                b+=4;
 
379
                r+=4;
 
380
                }
 
381
        return((BN_ULONG)c);
 
382
        }
 
383
#endif /* !BN_LLONG */
 
384
 
 
385
BN_ULONG bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
 
386
        {
 
387
        BN_ULONG t1,t2;
 
388
        int c=0;
 
389
 
 
390
        assert(n >= 0);
 
391
        if (n <= 0) return((BN_ULONG)0);
 
392
 
 
393
        for (;;)
 
394
                {
 
395
                t1=a[0]; t2=b[0];
 
396
                r[0]=(t1-t2-c)&BN_MASK2;
 
397
                if (t1 != t2) c=(t1 < t2);
 
398
                if (--n <= 0) break;
 
399
 
 
400
                t1=a[1]; t2=b[1];
 
401
                r[1]=(t1-t2-c)&BN_MASK2;
 
402
                if (t1 != t2) c=(t1 < t2);
 
403
                if (--n <= 0) break;
 
404
 
 
405
                t1=a[2]; t2=b[2];
 
406
                r[2]=(t1-t2-c)&BN_MASK2;
 
407
                if (t1 != t2) c=(t1 < t2);
 
408
                if (--n <= 0) break;
 
409
 
 
410
                t1=a[3]; t2=b[3];
 
411
                r[3]=(t1-t2-c)&BN_MASK2;
 
412
                if (t1 != t2) c=(t1 < t2);
 
413
                if (--n <= 0) break;
 
414
 
 
415
                a+=4;
 
416
                b+=4;
 
417
                r+=4;
 
418
                }
 
419
        return(c);
 
420
        }
 
421
 
 
422
#ifdef BN_MUL_COMBA
 
423
 
 
424
#undef bn_mul_comba8
 
425
#undef bn_mul_comba4
 
426
#undef bn_sqr_comba8
 
427
#undef bn_sqr_comba4
 
428
 
 
429
/* mul_add_c(a,b,c0,c1,c2)  -- c+=a*b for three word number c=(c2,c1,c0) */
 
430
/* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
 
431
/* sqr_add_c(a,i,c0,c1,c2)  -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
 
432
/* sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number c=(c2,c1,c0) */
 
433
 
 
434
#ifdef BN_LLONG
 
435
#define mul_add_c(a,b,c0,c1,c2) \
 
436
        t=(BN_ULLONG)a*b; \
 
437
        t1=(BN_ULONG)Lw(t); \
 
438
        t2=(BN_ULONG)Hw(t); \
 
439
        c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
 
440
        c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 
441
 
 
442
#define mul_add_c2(a,b,c0,c1,c2) \
 
443
        t=(BN_ULLONG)a*b; \
 
444
        tt=(t+t)&BN_MASK; \
 
445
        if (tt < t) c2++; \
 
446
        t1=(BN_ULONG)Lw(tt); \
 
447
        t2=(BN_ULONG)Hw(tt); \
 
448
        c0=(c0+t1)&BN_MASK2;  \
 
449
        if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
 
450
        c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 
451
 
 
452
#define sqr_add_c(a,i,c0,c1,c2) \
 
453
        t=(BN_ULLONG)a[i]*a[i]; \
 
454
        t1=(BN_ULONG)Lw(t); \
 
455
        t2=(BN_ULONG)Hw(t); \
 
456
        c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
 
457
        c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 
458
 
 
459
#define sqr_add_c2(a,i,j,c0,c1,c2) \
 
460
        mul_add_c2((a)[i],(a)[j],c0,c1,c2)
 
461
 
 
462
#elif defined(BN_UMULT_HIGH)
 
463
 
 
464
#define mul_add_c(a,b,c0,c1,c2) {       \
 
465
        BN_ULONG ta=(a),tb=(b);         \
 
466
        t1 = ta * tb;                   \
 
467
        t2 = BN_UMULT_HIGH(ta,tb);      \
 
468
        c0 += t1; t2 += (c0<t1)?1:0;    \
 
469
        c1 += t2; c2 += (c1<t2)?1:0;    \
 
470
        }
 
471
 
 
472
#define mul_add_c2(a,b,c0,c1,c2) {      \
 
473
        BN_ULONG ta=(a),tb=(b),t0;      \
 
474
        t1 = BN_UMULT_HIGH(ta,tb);      \
 
475
        t0 = ta * tb;                   \
 
476
        t2 = t1+t1; c2 += (t2<t1)?1:0;  \
 
477
        t1 = t0+t0; t2 += (t1<t0)?1:0;  \
 
478
        c0 += t1; t2 += (c0<t1)?1:0;    \
 
479
        c1 += t2; c2 += (c1<t2)?1:0;    \
 
480
        }
 
481
 
 
482
#define sqr_add_c(a,i,c0,c1,c2) {       \
 
483
        BN_ULONG ta=(a)[i];             \
 
484
        t1 = ta * ta;                   \
 
485
        t2 = BN_UMULT_HIGH(ta,ta);      \
 
486
        c0 += t1; t2 += (c0<t1)?1:0;    \
 
487
        c1 += t2; c2 += (c1<t2)?1:0;    \
 
488
        }
 
489
 
 
490
#define sqr_add_c2(a,i,j,c0,c1,c2)      \
 
491
        mul_add_c2((a)[i],(a)[j],c0,c1,c2)
 
492
 
 
493
#else /* !BN_LLONG */
 
494
#define mul_add_c(a,b,c0,c1,c2) \
 
495
        t1=LBITS(a); t2=HBITS(a); \
 
496
        bl=LBITS(b); bh=HBITS(b); \
 
497
        mul64(t1,t2,bl,bh); \
 
498
        c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
 
499
        c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 
500
 
 
501
#define mul_add_c2(a,b,c0,c1,c2) \
 
502
        t1=LBITS(a); t2=HBITS(a); \
 
503
        bl=LBITS(b); bh=HBITS(b); \
 
504
        mul64(t1,t2,bl,bh); \
 
505
        if (t2 & BN_TBIT) c2++; \
 
506
        t2=(t2+t2)&BN_MASK2; \
 
507
        if (t1 & BN_TBIT) t2++; \
 
508
        t1=(t1+t1)&BN_MASK2; \
 
509
        c0=(c0+t1)&BN_MASK2;  \
 
510
        if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
 
511
        c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 
512
 
 
513
#define sqr_add_c(a,i,c0,c1,c2) \
 
514
        sqr64(t1,t2,(a)[i]); \
 
515
        c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
 
516
        c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
 
517
 
 
518
#define sqr_add_c2(a,i,j,c0,c1,c2) \
 
519
        mul_add_c2((a)[i],(a)[j],c0,c1,c2)
 
520
#endif /* !BN_LLONG */
 
521
 
 
522
void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 
523
        {
 
524
#ifdef BN_LLONG
 
525
        BN_ULLONG t;
 
526
#else
 
527
        BN_ULONG bl,bh;
 
528
#endif
 
529
        BN_ULONG t1,t2;
 
530
        BN_ULONG c1,c2,c3;
 
531
 
 
532
        c1=0;
 
533
        c2=0;
 
534
        c3=0;
 
535
        mul_add_c(a[0],b[0],c1,c2,c3);
 
536
        r[0]=c1;
 
537
        c1=0;
 
538
        mul_add_c(a[0],b[1],c2,c3,c1);
 
539
        mul_add_c(a[1],b[0],c2,c3,c1);
 
540
        r[1]=c2;
 
541
        c2=0;
 
542
        mul_add_c(a[2],b[0],c3,c1,c2);
 
543
        mul_add_c(a[1],b[1],c3,c1,c2);
 
544
        mul_add_c(a[0],b[2],c3,c1,c2);
 
545
        r[2]=c3;
 
546
        c3=0;
 
547
        mul_add_c(a[0],b[3],c1,c2,c3);
 
548
        mul_add_c(a[1],b[2],c1,c2,c3);
 
549
        mul_add_c(a[2],b[1],c1,c2,c3);
 
550
        mul_add_c(a[3],b[0],c1,c2,c3);
 
551
        r[3]=c1;
 
552
        c1=0;
 
553
        mul_add_c(a[4],b[0],c2,c3,c1);
 
554
        mul_add_c(a[3],b[1],c2,c3,c1);
 
555
        mul_add_c(a[2],b[2],c2,c3,c1);
 
556
        mul_add_c(a[1],b[3],c2,c3,c1);
 
557
        mul_add_c(a[0],b[4],c2,c3,c1);
 
558
        r[4]=c2;
 
559
        c2=0;
 
560
        mul_add_c(a[0],b[5],c3,c1,c2);
 
561
        mul_add_c(a[1],b[4],c3,c1,c2);
 
562
        mul_add_c(a[2],b[3],c3,c1,c2);
 
563
        mul_add_c(a[3],b[2],c3,c1,c2);
 
564
        mul_add_c(a[4],b[1],c3,c1,c2);
 
565
        mul_add_c(a[5],b[0],c3,c1,c2);
 
566
        r[5]=c3;
 
567
        c3=0;
 
568
        mul_add_c(a[6],b[0],c1,c2,c3);
 
569
        mul_add_c(a[5],b[1],c1,c2,c3);
 
570
        mul_add_c(a[4],b[2],c1,c2,c3);
 
571
        mul_add_c(a[3],b[3],c1,c2,c3);
 
572
        mul_add_c(a[2],b[4],c1,c2,c3);
 
573
        mul_add_c(a[1],b[5],c1,c2,c3);
 
574
        mul_add_c(a[0],b[6],c1,c2,c3);
 
575
        r[6]=c1;
 
576
        c1=0;
 
577
        mul_add_c(a[0],b[7],c2,c3,c1);
 
578
        mul_add_c(a[1],b[6],c2,c3,c1);
 
579
        mul_add_c(a[2],b[5],c2,c3,c1);
 
580
        mul_add_c(a[3],b[4],c2,c3,c1);
 
581
        mul_add_c(a[4],b[3],c2,c3,c1);
 
582
        mul_add_c(a[5],b[2],c2,c3,c1);
 
583
        mul_add_c(a[6],b[1],c2,c3,c1);
 
584
        mul_add_c(a[7],b[0],c2,c3,c1);
 
585
        r[7]=c2;
 
586
        c2=0;
 
587
        mul_add_c(a[7],b[1],c3,c1,c2);
 
588
        mul_add_c(a[6],b[2],c3,c1,c2);
 
589
        mul_add_c(a[5],b[3],c3,c1,c2);
 
590
        mul_add_c(a[4],b[4],c3,c1,c2);
 
591
        mul_add_c(a[3],b[5],c3,c1,c2);
 
592
        mul_add_c(a[2],b[6],c3,c1,c2);
 
593
        mul_add_c(a[1],b[7],c3,c1,c2);
 
594
        r[8]=c3;
 
595
        c3=0;
 
596
        mul_add_c(a[2],b[7],c1,c2,c3);
 
597
        mul_add_c(a[3],b[6],c1,c2,c3);
 
598
        mul_add_c(a[4],b[5],c1,c2,c3);
 
599
        mul_add_c(a[5],b[4],c1,c2,c3);
 
600
        mul_add_c(a[6],b[3],c1,c2,c3);
 
601
        mul_add_c(a[7],b[2],c1,c2,c3);
 
602
        r[9]=c1;
 
603
        c1=0;
 
604
        mul_add_c(a[7],b[3],c2,c3,c1);
 
605
        mul_add_c(a[6],b[4],c2,c3,c1);
 
606
        mul_add_c(a[5],b[5],c2,c3,c1);
 
607
        mul_add_c(a[4],b[6],c2,c3,c1);
 
608
        mul_add_c(a[3],b[7],c2,c3,c1);
 
609
        r[10]=c2;
 
610
        c2=0;
 
611
        mul_add_c(a[4],b[7],c3,c1,c2);
 
612
        mul_add_c(a[5],b[6],c3,c1,c2);
 
613
        mul_add_c(a[6],b[5],c3,c1,c2);
 
614
        mul_add_c(a[7],b[4],c3,c1,c2);
 
615
        r[11]=c3;
 
616
        c3=0;
 
617
        mul_add_c(a[7],b[5],c1,c2,c3);
 
618
        mul_add_c(a[6],b[6],c1,c2,c3);
 
619
        mul_add_c(a[5],b[7],c1,c2,c3);
 
620
        r[12]=c1;
 
621
        c1=0;
 
622
        mul_add_c(a[6],b[7],c2,c3,c1);
 
623
        mul_add_c(a[7],b[6],c2,c3,c1);
 
624
        r[13]=c2;
 
625
        c2=0;
 
626
        mul_add_c(a[7],b[7],c3,c1,c2);
 
627
        r[14]=c3;
 
628
        r[15]=c1;
 
629
        }
 
630
 
 
631
void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 
632
        {
 
633
#ifdef BN_LLONG
 
634
        BN_ULLONG t;
 
635
#else
 
636
        BN_ULONG bl,bh;
 
637
#endif
 
638
        BN_ULONG t1,t2;
 
639
        BN_ULONG c1,c2,c3;
 
640
 
 
641
        c1=0;
 
642
        c2=0;
 
643
        c3=0;
 
644
        mul_add_c(a[0],b[0],c1,c2,c3);
 
645
        r[0]=c1;
 
646
        c1=0;
 
647
        mul_add_c(a[0],b[1],c2,c3,c1);
 
648
        mul_add_c(a[1],b[0],c2,c3,c1);
 
649
        r[1]=c2;
 
650
        c2=0;
 
651
        mul_add_c(a[2],b[0],c3,c1,c2);
 
652
        mul_add_c(a[1],b[1],c3,c1,c2);
 
653
        mul_add_c(a[0],b[2],c3,c1,c2);
 
654
        r[2]=c3;
 
655
        c3=0;
 
656
        mul_add_c(a[0],b[3],c1,c2,c3);
 
657
        mul_add_c(a[1],b[2],c1,c2,c3);
 
658
        mul_add_c(a[2],b[1],c1,c2,c3);
 
659
        mul_add_c(a[3],b[0],c1,c2,c3);
 
660
        r[3]=c1;
 
661
        c1=0;
 
662
        mul_add_c(a[3],b[1],c2,c3,c1);
 
663
        mul_add_c(a[2],b[2],c2,c3,c1);
 
664
        mul_add_c(a[1],b[3],c2,c3,c1);
 
665
        r[4]=c2;
 
666
        c2=0;
 
667
        mul_add_c(a[2],b[3],c3,c1,c2);
 
668
        mul_add_c(a[3],b[2],c3,c1,c2);
 
669
        r[5]=c3;
 
670
        c3=0;
 
671
        mul_add_c(a[3],b[3],c1,c2,c3);
 
672
        r[6]=c1;
 
673
        r[7]=c2;
 
674
        }
 
675
 
 
676
void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
 
677
        {
 
678
#ifdef BN_LLONG
 
679
        BN_ULLONG t,tt;
 
680
#else
 
681
        BN_ULONG bl,bh;
 
682
#endif
 
683
        BN_ULONG t1,t2;
 
684
        BN_ULONG c1,c2,c3;
 
685
 
 
686
        c1=0;
 
687
        c2=0;
 
688
        c3=0;
 
689
        sqr_add_c(a,0,c1,c2,c3);
 
690
        r[0]=c1;
 
691
        c1=0;
 
692
        sqr_add_c2(a,1,0,c2,c3,c1);
 
693
        r[1]=c2;
 
694
        c2=0;
 
695
        sqr_add_c(a,1,c3,c1,c2);
 
696
        sqr_add_c2(a,2,0,c3,c1,c2);
 
697
        r[2]=c3;
 
698
        c3=0;
 
699
        sqr_add_c2(a,3,0,c1,c2,c3);
 
700
        sqr_add_c2(a,2,1,c1,c2,c3);
 
701
        r[3]=c1;
 
702
        c1=0;
 
703
        sqr_add_c(a,2,c2,c3,c1);
 
704
        sqr_add_c2(a,3,1,c2,c3,c1);
 
705
        sqr_add_c2(a,4,0,c2,c3,c1);
 
706
        r[4]=c2;
 
707
        c2=0;
 
708
        sqr_add_c2(a,5,0,c3,c1,c2);
 
709
        sqr_add_c2(a,4,1,c3,c1,c2);
 
710
        sqr_add_c2(a,3,2,c3,c1,c2);
 
711
        r[5]=c3;
 
712
        c3=0;
 
713
        sqr_add_c(a,3,c1,c2,c3);
 
714
        sqr_add_c2(a,4,2,c1,c2,c3);
 
715
        sqr_add_c2(a,5,1,c1,c2,c3);
 
716
        sqr_add_c2(a,6,0,c1,c2,c3);
 
717
        r[6]=c1;
 
718
        c1=0;
 
719
        sqr_add_c2(a,7,0,c2,c3,c1);
 
720
        sqr_add_c2(a,6,1,c2,c3,c1);
 
721
        sqr_add_c2(a,5,2,c2,c3,c1);
 
722
        sqr_add_c2(a,4,3,c2,c3,c1);
 
723
        r[7]=c2;
 
724
        c2=0;
 
725
        sqr_add_c(a,4,c3,c1,c2);
 
726
        sqr_add_c2(a,5,3,c3,c1,c2);
 
727
        sqr_add_c2(a,6,2,c3,c1,c2);
 
728
        sqr_add_c2(a,7,1,c3,c1,c2);
 
729
        r[8]=c3;
 
730
        c3=0;
 
731
        sqr_add_c2(a,7,2,c1,c2,c3);
 
732
        sqr_add_c2(a,6,3,c1,c2,c3);
 
733
        sqr_add_c2(a,5,4,c1,c2,c3);
 
734
        r[9]=c1;
 
735
        c1=0;
 
736
        sqr_add_c(a,5,c2,c3,c1);
 
737
        sqr_add_c2(a,6,4,c2,c3,c1);
 
738
        sqr_add_c2(a,7,3,c2,c3,c1);
 
739
        r[10]=c2;
 
740
        c2=0;
 
741
        sqr_add_c2(a,7,4,c3,c1,c2);
 
742
        sqr_add_c2(a,6,5,c3,c1,c2);
 
743
        r[11]=c3;
 
744
        c3=0;
 
745
        sqr_add_c(a,6,c1,c2,c3);
 
746
        sqr_add_c2(a,7,5,c1,c2,c3);
 
747
        r[12]=c1;
 
748
        c1=0;
 
749
        sqr_add_c2(a,7,6,c2,c3,c1);
 
750
        r[13]=c2;
 
751
        c2=0;
 
752
        sqr_add_c(a,7,c3,c1,c2);
 
753
        r[14]=c3;
 
754
        r[15]=c1;
 
755
        }
 
756
 
 
757
void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
 
758
        {
 
759
#ifdef BN_LLONG
 
760
        BN_ULLONG t,tt;
 
761
#else
 
762
        BN_ULONG bl,bh;
 
763
#endif
 
764
        BN_ULONG t1,t2;
 
765
        BN_ULONG c1,c2,c3;
 
766
 
 
767
        c1=0;
 
768
        c2=0;
 
769
        c3=0;
 
770
        sqr_add_c(a,0,c1,c2,c3);
 
771
        r[0]=c1;
 
772
        c1=0;
 
773
        sqr_add_c2(a,1,0,c2,c3,c1);
 
774
        r[1]=c2;
 
775
        c2=0;
 
776
        sqr_add_c(a,1,c3,c1,c2);
 
777
        sqr_add_c2(a,2,0,c3,c1,c2);
 
778
        r[2]=c3;
 
779
        c3=0;
 
780
        sqr_add_c2(a,3,0,c1,c2,c3);
 
781
        sqr_add_c2(a,2,1,c1,c2,c3);
 
782
        r[3]=c1;
 
783
        c1=0;
 
784
        sqr_add_c(a,2,c2,c3,c1);
 
785
        sqr_add_c2(a,3,1,c2,c3,c1);
 
786
        r[4]=c2;
 
787
        c2=0;
 
788
        sqr_add_c2(a,3,2,c3,c1,c2);
 
789
        r[5]=c3;
 
790
        c3=0;
 
791
        sqr_add_c(a,3,c1,c2,c3);
 
792
        r[6]=c1;
 
793
        r[7]=c2;
 
794
        }
 
795
#else /* !BN_MUL_COMBA */
 
796
 
 
797
/* hmm... is it faster just to do a multiply? */
 
798
#undef bn_sqr_comba4
 
799
void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a)
 
800
        {
 
801
        BN_ULONG t[8];
 
802
        bn_sqr_normal(r,a,4,t);
 
803
        }
 
804
 
 
805
#undef bn_sqr_comba8
 
806
void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a)
 
807
        {
 
808
        BN_ULONG t[16];
 
809
        bn_sqr_normal(r,a,8,t);
 
810
        }
 
811
 
 
812
void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 
813
        {
 
814
        r[4]=bn_mul_words(    &(r[0]),a,4,b[0]);
 
815
        r[5]=bn_mul_add_words(&(r[1]),a,4,b[1]);
 
816
        r[6]=bn_mul_add_words(&(r[2]),a,4,b[2]);
 
817
        r[7]=bn_mul_add_words(&(r[3]),a,4,b[3]);
 
818
        }
 
819
 
 
820
void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 
821
        {
 
822
        r[ 8]=bn_mul_words(    &(r[0]),a,8,b[0]);
 
823
        r[ 9]=bn_mul_add_words(&(r[1]),a,8,b[1]);
 
824
        r[10]=bn_mul_add_words(&(r[2]),a,8,b[2]);
 
825
        r[11]=bn_mul_add_words(&(r[3]),a,8,b[3]);
 
826
        r[12]=bn_mul_add_words(&(r[4]),a,8,b[4]);
 
827
        r[13]=bn_mul_add_words(&(r[5]),a,8,b[5]);
 
828
        r[14]=bn_mul_add_words(&(r[6]),a,8,b[6]);
 
829
        r[15]=bn_mul_add_words(&(r[7]),a,8,b[7]);
 
830
        }
 
831
 
 
832
#endif /* !BN_MUL_COMBA */