« back to all changes in this revision
Viewing changes to crypto/bn_mul.c
- browse files at revision 4
- compare with another revision
- download diff
- download tarball
- view history from revision 4
- Committer: Bazaar Package Importer
- Author(s): Tomas Fasth
- Date: 2005-05-24 13:31:34 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20050524133134-6hn24gprfmo91sfv
Tags: 1.4.1-1
New upstream release.
- files added:
- Makefile.in
- files removed:
- ChangeLog
- crypto
- files modified:
- README
- doc/keymap-names.txt *
added
removed
crypto/bn_mul.c
1
/* crypto/bn/bn_mul.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
#include <stdio.h>
60
#include "bn_lcl.h"
61
62
#ifdef BN_RECURSION
63
/* Karatsuba recursive multiplication algorithm
64
* (cf. Knuth, The Art of Computer Programming, Vol. 2) */
65
66
/* r is 2*n2 words in size,
67
* a and b are both n2 words in size.
68
* n2 must be a power of 2.
69
* We multiply and return the result.
70
* t must be 2*n2 words in size
71
* We calculate
72
* a[0]*b[0]
73
* a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
74
* a[1]*b[1]
75
*/
76
void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
77
BN_ULONG *t)
78
{
79
int n=n2/2,c1,c2;
80
unsigned int neg,zero;
81
BN_ULONG ln,lo,*p;
82
83
# ifdef BN_COUNT
84
printf(" bn_mul_recursive %d * %d\n",n2,n2);
85
# endif
86
# ifdef BN_MUL_COMBA
87
# if 0
88
if (n2 == 4)
89
{
90
bn_mul_comba4(r,a,b);
91
return;
92
}
93
# endif
94
if (n2 == 8)
95
{
96
bn_mul_comba8(r,a,b);
97
return;
98
}
99
# endif /* BN_MUL_COMBA */
100
if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
101
{
102
/* This should not happen */
103
bn_mul_normal(r,a,n2,b,n2);
104
return;
105
}
106
/* r=(a[0]-a[1])*(b[1]-b[0]) */
107
c1=bn_cmp_words(a,&(a[n]),n);
108
c2=bn_cmp_words(&(b[n]),b,n);
109
zero=neg=0;
110
switch (c1*3+c2)
111
{
112
case -4:
113
bn_sub_words(t, &(a[n]),a, n); /* - */
114
bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
115
break;
116
case -3:
117
zero=1;
118
break;
119
case -2:
120
bn_sub_words(t, &(a[n]),a, n); /* - */
121
bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
122
neg=1;
123
break;
124
case -1:
125
case 0:
126
case 1:
127
zero=1;
128
break;
129
case 2:
130
bn_sub_words(t, a, &(a[n]),n); /* + */
131
bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
132
neg=1;
133
break;
134
case 3:
135
zero=1;
136
break;
137
case 4:
138
bn_sub_words(t, a, &(a[n]),n);
139
bn_sub_words(&(t[n]),&(b[n]),b, n);
140
break;
141
}
142
143
# ifdef BN_MUL_COMBA
144
if (n == 4)
145
{
146
if (!zero)
147
bn_mul_comba4(&(t[n2]),t,&(t[n]));
148
else
149
memset(&(t[n2]),0,8*sizeof(BN_ULONG));
150
151
bn_mul_comba4(r,a,b);
152
bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n]));
153
}
154
else if (n == 8)
155
{
156
if (!zero)
157
bn_mul_comba8(&(t[n2]),t,&(t[n]));
158
else
159
memset(&(t[n2]),0,16*sizeof(BN_ULONG));
160
161
bn_mul_comba8(r,a,b);
162
bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
163
}
164
else
165
# endif /* BN_MUL_COMBA */
166
{
167
p= &(t[n2*2]);
168
if (!zero)
169
bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
170
else
171
memset(&(t[n2]),0,n2*sizeof(BN_ULONG));
172
bn_mul_recursive(r,a,b,n,p);
173
bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p);
174
}
175
176
/* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
177
* r[10] holds (a[0]*b[0])
178
* r[32] holds (b[1]*b[1])
179
*/
180
181
c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
182
183
if (neg) /* if t[32] is negative */
184
{
185
c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
186
}
187
else
188
{
189
/* Might have a carry */
190
c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
191
}
192
193
/* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
194
* r[10] holds (a[0]*b[0])
195
* r[32] holds (b[1]*b[1])
196
* c1 holds the carry bits
197
*/
198
c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
199
if (c1)
200
{
201
p= &(r[n+n2]);
202
lo= *p;
203
ln=(lo+c1)&BN_MASK2;
204
*p=ln;
205
206
/* The overflow will stop before we over write
207
* words we should not overwrite */
208
if (ln < (BN_ULONG)c1)
209
{
210
do {
211
p++;
212
lo= *p;
213
ln=(lo+1)&BN_MASK2;
214
*p=ln;
215
} while (ln == 0);
216
}
217
}
218
}
219
220
/* n+tn is the word length
221
* t needs to be n*4 is size, as does r */
222
void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
223
int n, BN_ULONG *t)
224
{
225
int i,j,n2=n*2;
226
unsigned int c1,c2,neg,zero;
227
BN_ULONG ln,lo,*p;
228
229
# ifdef BN_COUNT
230
printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
231
# endif
232
if (n < 8)
233
{
234
i=tn+n;
235
bn_mul_normal(r,a,i,b,i);
236
return;
237
}
238
239
/* r=(a[0]-a[1])*(b[1]-b[0]) */
240
c1=bn_cmp_words(a,&(a[n]),n);
241
c2=bn_cmp_words(&(b[n]),b,n);
242
zero=neg=0;
243
switch (c1*3+c2)
244
{
245
case -4:
246
bn_sub_words(t, &(a[n]),a, n); /* - */
247
bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
248
break;
249
case -3:
250
zero=1;
251
/* break; */
252
case -2:
253
bn_sub_words(t, &(a[n]),a, n); /* - */
254
bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
255
neg=1;
256
break;
257
case -1:
258
case 0:
259
case 1:
260
zero=1;
261
/* break; */
262
case 2:
263
bn_sub_words(t, a, &(a[n]),n); /* + */
264
bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
265
neg=1;
266
break;
267
case 3:
268
zero=1;
269
/* break; */
270
case 4:
271
bn_sub_words(t, a, &(a[n]),n);
272
bn_sub_words(&(t[n]),&(b[n]),b, n);
273
break;
274
}
275
/* The zero case isn't yet implemented here. The speedup
276
would probably be negligible. */
277
# if 0
278
if (n == 4)
279
{
280
bn_mul_comba4(&(t[n2]),t,&(t[n]));
281
bn_mul_comba4(r,a,b);
282
bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
283
memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
284
}
285
else
286
# endif
287
if (n == 8)
288
{
289
bn_mul_comba8(&(t[n2]),t,&(t[n]));
290
bn_mul_comba8(r,a,b);
291
bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
292
memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
293
}
294
else
295
{
296
p= &(t[n2*2]);
297
bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
298
bn_mul_recursive(r,a,b,n,p);
299
i=n/2;
300
/* If there is only a bottom half to the number,
301
* just do it */
302
j=tn-i;
303
if (j == 0)
304
{
305
bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p);
306
memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2));
307
}
308
else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
309
{
310
bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]),
311
j,i,p);
312
memset(&(r[n2+tn*2]),0,
313
sizeof(BN_ULONG)*(n2-tn*2));
314
}
315
else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
316
{
317
memset(&(r[n2]),0,sizeof(BN_ULONG)*n2);
318
if (tn < BN_MUL_RECURSIVE_SIZE_NORMAL)
319
{
320
bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
321
}
322
else
323
{
324
for (;;)
325
{
326
i/=2;
327
if (i < tn)
328
{
329
bn_mul_part_recursive(&(r[n2]),
330
&(a[n]),&(b[n]),
331
tn-i,i,p);
332
break;
333
}
334
else if (i == tn)
335
{
336
bn_mul_recursive(&(r[n2]),
337
&(a[n]),&(b[n]),
338
i,p);
339
break;
340
}
341
}
342
}
343
}
344
}
345
346
/* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
347
* r[10] holds (a[0]*b[0])
348
* r[32] holds (b[1]*b[1])
349
*/
350
351
c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
352
353
if (neg) /* if t[32] is negative */
354
{
355
c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
356
}
357
else
358
{
359
/* Might have a carry */
360
c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
361
}
362
363
/* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
364
* r[10] holds (a[0]*b[0])
365
* r[32] holds (b[1]*b[1])
366
* c1 holds the carry bits
367
*/
368
c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
369
if (c1)
370
{
371
p= &(r[n+n2]);
372
lo= *p;
373
ln=(lo+c1)&BN_MASK2;
374
*p=ln;
375
376
/* The overflow will stop before we over write
377
* words we should not overwrite */
378
if (ln < c1)
379
{
380
do {
381
p++;
382
lo= *p;
383
ln=(lo+1)&BN_MASK2;
384
*p=ln;
385
} while (ln == 0);
386
}
387
}
388
}
389
390
/* a and b must be the same size, which is n2.
391
* r needs to be n2 words and t needs to be n2*2
392
*/
393
void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
394
BN_ULONG *t)
395
{
396
int n=n2/2;
397
398
# ifdef BN_COUNT
399
printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
400
# endif
401
402
bn_mul_recursive(r,a,b,n,&(t[0]));
403
if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
404
{
405
bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2]));
406
bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
407
bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2]));
408
bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
409
}
410
else
411
{
412
bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n);
413
bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n);
414
bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
415
bn_add_words(&(r[n]),&(r[n]),&(t[n]),n);
416
}
417
}
418
419
/* a and b must be the same size, which is n2.
420
* r needs to be n2 words and t needs to be n2*2
421
* l is the low words of the output.
422
* t needs to be n2*3
423
*/
424
void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
425
BN_ULONG *t)
426
{
427
int i,n;
428
int c1,c2;
429
int neg,oneg,zero;
430
BN_ULONG ll,lc,*lp,*mp;
431
432
# ifdef BN_COUNT
433
printf(" bn_mul_high %d * %d\n",n2,n2);
434
# endif
435
n=n2/2;
436
437
/* Calculate (al-ah)*(bh-bl) */
438
neg=zero=0;
439
c1=bn_cmp_words(&(a[0]),&(a[n]),n);
440
c2=bn_cmp_words(&(b[n]),&(b[0]),n);
441
switch (c1*3+c2)
442
{
443
case -4:
444
bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
445
bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
446
break;
447
case -3:
448
zero=1;
449
break;
450
case -2:
451
bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
452
bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
453
neg=1;
454
break;
455
case -1:
456
case 0:
457
case 1:
458
zero=1;
459
break;
460
case 2:
461
bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
462
bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
463
neg=1;
464
break;
465
case 3:
466
zero=1;
467
break;
468
case 4:
469
bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
470
bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
471
break;
472
}
473
474
oneg=neg;
475
/* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
476
/* r[10] = (a[1]*b[1]) */
477
# ifdef BN_MUL_COMBA
478
if (n == 8)
479
{
480
bn_mul_comba8(&(t[0]),&(r[0]),&(r[n]));
481
bn_mul_comba8(r,&(a[n]),&(b[n]));
482
}
483
else
484
# endif
485
{
486
bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
487
bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
488
}
489
490
/* s0 == low(al*bl)
491
* s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
492
* We know s0 and s1 so the only unknown is high(al*bl)
493
* high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
494
* high(al*bl) == s1 - (r[0]+l[0]+t[0])
495
*/
496
if (l != NULL)
497
{
498
lp= &(t[n2+n]);
499
c1=(int)(bn_add_words(lp,&(r[0]),&(l[0]),n));
500
}
501
else
502
{
503
c1=0;
504
lp= &(r[0]);
505
}
506
507
if (neg)
508
neg=(int)(bn_sub_words(&(t[n2]),lp,&(t[0]),n));
509
else
510
{
511
bn_add_words(&(t[n2]),lp,&(t[0]),n);
512
neg=0;
513
}
514
515
if (l != NULL)
516
{
517
bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n);
518
}
519
else
520
{
521
lp= &(t[n2+n]);
522
mp= &(t[n2]);
523
for (i=0; i<n; i++)
524
lp[i]=((~mp[i])+1)&BN_MASK2;
525
}
526
527
/* s[0] = low(al*bl)
528
* t[3] = high(al*bl)
529
* t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
530
* r[10] = (a[1]*b[1])
531
*/
532
/* R[10] = al*bl
533
* R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
534
* R[32] = ah*bh
535
*/
536
/* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
537
* R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
538
* R[3]=r[1]+(carry/borrow)
539
*/
540
if (l != NULL)
541
{
542
lp= &(t[n2]);
543
c1= (int)(bn_add_words(lp,&(t[n2+n]),&(l[0]),n));
544
}
545
else
546
{
547
lp= &(t[n2+n]);
548
c1=0;
549
}
550
c1+=(int)(bn_add_words(&(t[n2]),lp, &(r[0]),n));
551
if (oneg)
552
c1-=(int)(bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n));
553
else
554
c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n));
555
556
c2 =(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n));
557
c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(r[n]),n));
558
if (oneg)
559
c2-=(int)(bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n));
560
else
561
c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n]),n));
562
563
if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
564
{
565
i=0;
566
if (c1 > 0)
567
{
568
lc=c1;
569
do {
570
ll=(r[i]+lc)&BN_MASK2;
571
r[i++]=ll;
572
lc=(lc > ll);
573
} while (lc);
574
}
575
else
576
{
577
lc= -c1;
578
do {
579
ll=r[i];
580
r[i++]=(ll-lc)&BN_MASK2;
581
lc=(lc > ll);
582
} while (lc);
583
}
584
}
585
if (c2 != 0) /* Add starting at r[1] */
586
{
587
i=n;
588
if (c2 > 0)
589
{
590
lc=c2;
591
do {
592
ll=(r[i]+lc)&BN_MASK2;
593
r[i++]=ll;
594
lc=(lc > ll);
595
} while (lc);
596
}
597
else
598
{
599
lc= -c2;
600
do {
601
ll=r[i];
602
r[i++]=(ll-lc)&BN_MASK2;
603
lc=(lc > ll);
604
} while (lc);
605
}
606
}
607
}
608
#endif /* BN_RECURSION */
609
610
int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
611
{
612
int top,al,bl;
613
BIGNUM *rr;
614
int ret = 0;
615
#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
616
int i;
617
#endif
618
#ifdef BN_RECURSION
619
BIGNUM *t;
620
int j,k;
621
#endif
622
623
#ifdef BN_COUNT
624
printf("BN_mul %d * %d\n",a->top,b->top);
625
#endif
626
627
bn_check_top(a);
628
bn_check_top(b);
629
bn_check_top(r);
630
631
al=a->top;
632
bl=b->top;
633
634
if ((al == 0) || (bl == 0))
635
{
636
if (!BN_zero(r)) goto err;
637
return(1);
638
}
639
top=al+bl;
640
641
BN_CTX_start(ctx);
642
if ((r == a) || (r == b))
643
{
644
if ((rr = BN_CTX_get(ctx)) == NULL) goto err;
645
}
646
else
647
rr = r;
648
rr->neg=a->neg^b->neg;
649
650
#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
651
i = al-bl;
652
#endif
653
#ifdef BN_MUL_COMBA
654
if (i == 0)
655
{
656
# if 0
657
if (al == 4)
658
{
659
if (bn_wexpand(rr,8) == NULL) goto err;
660
rr->top=8;
661
bn_mul_comba4(rr->d,a->d,b->d);
662
goto end;
663
}
664
# endif
665
if (al == 8)
666
{
667
if (bn_wexpand(rr,16) == NULL) goto err;
668
rr->top=16;
669
bn_mul_comba8(rr->d,a->d,b->d);
670
goto end;
671
}
672
}
673
#endif /* BN_MUL_COMBA */
674
#ifdef BN_RECURSION
675
if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL))
676
{
677
if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA))
678
{
679
if (bn_wexpand(b,al) == NULL) goto err;
680
b->d[bl]=0;
681
bl++;
682
i--;
683
}
684
else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA))
685
{
686
if (bn_wexpand(a,bl) == NULL) goto err;
687
a->d[al]=0;
688
al++;
689
i++;
690
}
691
if (i == 0)
692
{
693
/* symmetric and > 4 */
694
/* 16 or larger */
695
j=BN_num_bits_word((BN_ULONG)al);
696
j=1<<(j-1);
697
k=j+j;
698
t = BN_CTX_get(ctx);
699
if (al == j) /* exact multiple */
700
{
701
if (bn_wexpand(t,k*2) == NULL) goto err;
702
if (bn_wexpand(rr,k*2) == NULL) goto err;
703
bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
704
}
705
else
706
{
707
if (bn_wexpand(a,k) == NULL ) goto err;
708
if (bn_wexpand(b,k) == NULL ) goto err;
709
if (bn_wexpand(t,k*4) == NULL ) goto err;
710
if (bn_wexpand(rr,k*4) == NULL ) goto err;
711
for (i=a->top; i<k; i++)
712
a->d[i]=0;
713
for (i=b->top; i<k; i++)
714
b->d[i]=0;
715
bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
716
}
717
rr->top=top;
718
goto end;
719
}
720
}
721
#endif /* BN_RECURSION */
722
if (bn_wexpand(rr,top) == NULL) goto err;
723
rr->top=top;
724
bn_mul_normal(rr->d,a->d,al,b->d,bl);
725
726
#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
727
end:
728
#endif
729
bn_fix_top(rr);
730
if (r != rr) BN_copy(r,rr);
731
ret=1;
732
err:
733
BN_CTX_end(ctx);
734
return(ret);
735
}
736
737
void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
738
{
739
BN_ULONG *rr;
740
741
#ifdef BN_COUNT
742
printf(" bn_mul_normal %d * %d\n",na,nb);
743
#endif
744
745
if (na < nb)
746
{
747
int itmp;
748
BN_ULONG *ltmp;
749
750
itmp=na; na=nb; nb=itmp;
751
ltmp=a; a=b; b=ltmp;
752
753
}
754
rr= &(r[na]);
755
rr[0]=bn_mul_words(r,a,na,b[0]);
756
757
for (;;)
758
{
759
if (--nb <= 0) return;
760
rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]);
761
if (--nb <= 0) return;
762
rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]);
763
if (--nb <= 0) return;
764
rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]);
765
if (--nb <= 0) return;
766
rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]);
767
rr+=4;
768
r+=4;
769
b+=4;
770
}
771
}
772
773
void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
774
{
775
#ifdef BN_COUNT
776
printf(" bn_mul_low_normal %d * %d\n",n,n);
777
#endif
778
bn_mul_words(r,a,n,b[0]);
779
780
for (;;)
781
{
782
if (--n <= 0) return;
783
bn_mul_add_words(&(r[1]),a,n,b[1]);
784
if (--n <= 0) return;
785
bn_mul_add_words(&(r[2]),a,n,b[2]);
786
if (--n <= 0) return;
787
bn_mul_add_words(&(r[3]),a,n,b[3]);
788
if (--n <= 0) return;
789
bn_mul_add_words(&(r[4]),a,n,b[4]);
790
r+=4;
791
b+=4;
792
}
793
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1