]>
Commit | Line | Data |
---|---|---|
d02b48c6 | 1 | /* crypto/bn/bn_mul.c */ |
58964a49 | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
d02b48c6 RE |
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 | ||
90e7ce36 UM |
59 | #ifndef BN_DEBUG |
60 | # undef NDEBUG /* avoid conflicting definitions */ | |
61 | # define NDEBUG | |
62 | #endif | |
63 | ||
d02b48c6 | 64 | #include <stdio.h> |
baa257f1 | 65 | #include <assert.h> |
d02b48c6 RE |
66 | #include "cryptlib.h" |
67 | #include "bn_lcl.h" | |
68 | ||
699543e4 | 69 | #if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) |
52a1bab2 UM |
70 | /* Here follows specialised variants of bn_add_words() and |
71 | bn_sub_words(). They have the property performing operations on | |
baa257f1 RL |
72 | arrays of different sizes. The sizes of those arrays is expressed through |
73 | cl, which is the common length ( basicall, min(len(a),len(b)) ), and dl, | |
74 | which is the delta between the two lengths, calculated as len(a)-len(b). | |
75 | All lengths are the number of BN_ULONGs... For the operations that require | |
76 | a result array as parameter, it must have the length cl+abs(dl). | |
77 | These functions should probably end up in bn_asm.c as soon as there are | |
78 | assembler counterparts for the systems that use assembler files. */ | |
79 | ||
baa257f1 RL |
80 | BN_ULONG bn_sub_part_words(BN_ULONG *r, |
81 | const BN_ULONG *a, const BN_ULONG *b, | |
82 | int cl, int dl) | |
83 | { | |
84 | BN_ULONG c, t; | |
85 | ||
86 | assert(cl >= 0); | |
87 | c = bn_sub_words(r, a, b, cl); | |
88 | ||
89 | if (dl == 0) | |
90 | return c; | |
91 | ||
92 | r += cl; | |
93 | a += cl; | |
94 | b += cl; | |
95 | ||
96 | if (dl < 0) | |
97 | { | |
98 | #ifdef BN_COUNT | |
99 | fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); | |
100 | #endif | |
101 | for (;;) | |
102 | { | |
103 | t = b[0]; | |
c7997700 | 104 | r[0] = (0-t-c)&BN_MASK2; |
baa257f1 RL |
105 | if (t != 0) c=1; |
106 | if (++dl >= 0) break; | |
107 | ||
108 | t = b[1]; | |
c7997700 | 109 | r[1] = (0-t-c)&BN_MASK2; |
baa257f1 RL |
110 | if (t != 0) c=1; |
111 | if (++dl >= 0) break; | |
112 | ||
113 | t = b[2]; | |
c7997700 | 114 | r[2] = (0-t-c)&BN_MASK2; |
baa257f1 RL |
115 | if (t != 0) c=1; |
116 | if (++dl >= 0) break; | |
117 | ||
118 | t = b[3]; | |
c7997700 | 119 | r[3] = (0-t-c)&BN_MASK2; |
baa257f1 RL |
120 | if (t != 0) c=1; |
121 | if (++dl >= 0) break; | |
122 | ||
123 | b += 4; | |
124 | r += 4; | |
125 | } | |
126 | } | |
127 | else | |
128 | { | |
129 | int save_dl = dl; | |
130 | #ifdef BN_COUNT | |
131 | fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, dl, c); | |
132 | #endif | |
133 | while(c) | |
134 | { | |
135 | t = a[0]; | |
136 | r[0] = (t-c)&BN_MASK2; | |
137 | if (t != 0) c=0; | |
138 | if (--dl <= 0) break; | |
139 | ||
140 | t = a[1]; | |
141 | r[1] = (t-c)&BN_MASK2; | |
142 | if (t != 0) c=0; | |
143 | if (--dl <= 0) break; | |
144 | ||
145 | t = a[2]; | |
146 | r[2] = (t-c)&BN_MASK2; | |
147 | if (t != 0) c=0; | |
148 | if (--dl <= 0) break; | |
149 | ||
150 | t = a[3]; | |
151 | r[3] = (t-c)&BN_MASK2; | |
152 | if (t != 0) c=0; | |
153 | if (--dl <= 0) break; | |
154 | ||
155 | save_dl = dl; | |
156 | a += 4; | |
157 | r += 4; | |
158 | } | |
159 | if (dl > 0) | |
160 | { | |
161 | #ifdef BN_COUNT | |
162 | fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); | |
163 | #endif | |
164 | if (save_dl > dl) | |
165 | { | |
166 | switch (save_dl - dl) | |
167 | { | |
168 | case 1: | |
169 | r[1] = a[1]; | |
170 | if (--dl <= 0) break; | |
171 | case 2: | |
172 | r[2] = a[2]; | |
173 | if (--dl <= 0) break; | |
174 | case 3: | |
175 | r[3] = a[3]; | |
176 | if (--dl <= 0) break; | |
177 | } | |
178 | a += 4; | |
179 | r += 4; | |
180 | } | |
181 | } | |
182 | if (dl > 0) | |
183 | { | |
184 | #ifdef BN_COUNT | |
185 | fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", cl, dl); | |
186 | #endif | |
187 | for(;;) | |
188 | { | |
189 | r[0] = a[0]; | |
190 | if (--dl <= 0) break; | |
191 | r[1] = a[1]; | |
192 | if (--dl <= 0) break; | |
193 | r[2] = a[2]; | |
194 | if (--dl <= 0) break; | |
195 | r[3] = a[3]; | |
196 | if (--dl <= 0) break; | |
197 | ||
198 | a += 4; | |
199 | r += 4; | |
200 | } | |
201 | } | |
202 | } | |
203 | return c; | |
204 | } | |
240f5169 | 205 | #endif |
baa257f1 RL |
206 | |
207 | BN_ULONG bn_add_part_words(BN_ULONG *r, | |
208 | const BN_ULONG *a, const BN_ULONG *b, | |
209 | int cl, int dl) | |
210 | { | |
211 | BN_ULONG c, l, t; | |
212 | ||
213 | assert(cl >= 0); | |
0135e335 | 214 | c = bn_add_words(r, a, b, cl); |
baa257f1 RL |
215 | |
216 | if (dl == 0) | |
217 | return c; | |
218 | ||
219 | r += cl; | |
220 | a += cl; | |
221 | b += cl; | |
222 | ||
223 | if (dl < 0) | |
224 | { | |
225 | int save_dl = dl; | |
226 | #ifdef BN_COUNT | |
227 | fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); | |
228 | #endif | |
229 | while (c) | |
230 | { | |
231 | l=(c+b[0])&BN_MASK2; | |
232 | c=(l < c); | |
233 | r[0]=l; | |
234 | if (++dl >= 0) break; | |
235 | ||
236 | l=(c+b[1])&BN_MASK2; | |
237 | c=(l < c); | |
238 | r[1]=l; | |
239 | if (++dl >= 0) break; | |
240 | ||
241 | l=(c+b[2])&BN_MASK2; | |
242 | c=(l < c); | |
243 | r[2]=l; | |
244 | if (++dl >= 0) break; | |
245 | ||
246 | l=(c+b[3])&BN_MASK2; | |
247 | c=(l < c); | |
248 | r[3]=l; | |
249 | if (++dl >= 0) break; | |
250 | ||
251 | save_dl = dl; | |
252 | b+=4; | |
253 | r+=4; | |
254 | } | |
255 | if (dl < 0) | |
256 | { | |
257 | #ifdef BN_COUNT | |
258 | fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", cl, dl); | |
259 | #endif | |
260 | if (save_dl < dl) | |
261 | { | |
262 | switch (dl - save_dl) | |
263 | { | |
264 | case 1: | |
265 | r[1] = b[1]; | |
266 | if (++dl >= 0) break; | |
267 | case 2: | |
268 | r[2] = b[2]; | |
269 | if (++dl >= 0) break; | |
270 | case 3: | |
271 | r[3] = b[3]; | |
272 | if (++dl >= 0) break; | |
273 | } | |
274 | b += 4; | |
275 | r += 4; | |
276 | } | |
277 | } | |
278 | if (dl < 0) | |
279 | { | |
280 | #ifdef BN_COUNT | |
281 | fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", cl, dl); | |
282 | #endif | |
283 | for(;;) | |
284 | { | |
285 | r[0] = b[0]; | |
286 | if (++dl >= 0) break; | |
287 | r[1] = b[1]; | |
288 | if (++dl >= 0) break; | |
289 | r[2] = b[2]; | |
290 | if (++dl >= 0) break; | |
291 | r[3] = b[3]; | |
292 | if (++dl >= 0) break; | |
293 | ||
294 | b += 4; | |
295 | r += 4; | |
296 | } | |
297 | } | |
298 | } | |
299 | else | |
300 | { | |
301 | int save_dl = dl; | |
302 | #ifdef BN_COUNT | |
303 | fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl); | |
304 | #endif | |
305 | while (c) | |
306 | { | |
307 | t=(a[0]+c)&BN_MASK2; | |
308 | c=(t < c); | |
309 | r[0]=t; | |
310 | if (--dl <= 0) break; | |
311 | ||
312 | t=(a[1]+c)&BN_MASK2; | |
313 | c=(t < c); | |
314 | r[1]=t; | |
315 | if (--dl <= 0) break; | |
316 | ||
317 | t=(a[2]+c)&BN_MASK2; | |
318 | c=(t < c); | |
319 | r[2]=t; | |
320 | if (--dl <= 0) break; | |
321 | ||
322 | t=(a[3]+c)&BN_MASK2; | |
323 | c=(t < c); | |
324 | r[3]=t; | |
325 | if (--dl <= 0) break; | |
326 | ||
327 | save_dl = dl; | |
328 | a+=4; | |
329 | r+=4; | |
330 | } | |
331 | #ifdef BN_COUNT | |
332 | fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); | |
333 | #endif | |
334 | if (dl > 0) | |
335 | { | |
336 | if (save_dl > dl) | |
337 | { | |
338 | switch (save_dl - dl) | |
339 | { | |
340 | case 1: | |
341 | r[1] = a[1]; | |
342 | if (--dl <= 0) break; | |
343 | case 2: | |
344 | r[2] = a[2]; | |
345 | if (--dl <= 0) break; | |
346 | case 3: | |
347 | r[3] = a[3]; | |
348 | if (--dl <= 0) break; | |
349 | } | |
350 | a += 4; | |
351 | r += 4; | |
352 | } | |
353 | } | |
354 | if (dl > 0) | |
355 | { | |
356 | #ifdef BN_COUNT | |
357 | fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", cl, dl); | |
358 | #endif | |
359 | for(;;) | |
360 | { | |
361 | r[0] = a[0]; | |
362 | if (--dl <= 0) break; | |
363 | r[1] = a[1]; | |
364 | if (--dl <= 0) break; | |
365 | r[2] = a[2]; | |
366 | if (--dl <= 0) break; | |
367 | r[3] = a[3]; | |
368 | if (--dl <= 0) break; | |
369 | ||
370 | a += 4; | |
371 | r += 4; | |
372 | } | |
373 | } | |
374 | } | |
375 | return c; | |
376 | } | |
377 | ||
dfeab068 | 378 | #ifdef BN_RECURSION |
2d092edf BM |
379 | /* Karatsuba recursive multiplication algorithm |
380 | * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ | |
8782a426 | 381 | |
dfeab068 RE |
382 | /* r is 2*n2 words in size, |
383 | * a and b are both n2 words in size. | |
384 | * n2 must be a power of 2. | |
385 | * We multiply and return the result. | |
386 | * t must be 2*n2 words in size | |
657e60fa | 387 | * We calculate |
dfeab068 RE |
388 | * a[0]*b[0] |
389 | * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) | |
390 | * a[1]*b[1] | |
391 | */ | |
231a737a | 392 | /* dnX may not be positive, but n2/2+dnX has to be */ |
6b691a5c | 393 | void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, |
6a2347ee | 394 | int dna, int dnb, BN_ULONG *t) |
d02b48c6 | 395 | { |
dfeab068 | 396 | int n=n2/2,c1,c2; |
6a2347ee | 397 | int tna=n+dna, tnb=n+dnb; |
dfeab068 RE |
398 | unsigned int neg,zero; |
399 | BN_ULONG ln,lo,*p; | |
d02b48c6 | 400 | |
775c63fc | 401 | # ifdef BN_COUNT |
231a737a | 402 | fprintf(stderr," bn_mul_recursive %d%+d * %d%+d\n",n2,dna,n2,dnb); |
775c63fc UM |
403 | # endif |
404 | # ifdef BN_MUL_COMBA | |
405 | # if 0 | |
406 | if (n2 == 4) | |
d02b48c6 | 407 | { |
dfeab068 RE |
408 | bn_mul_comba4(r,a,b); |
409 | return; | |
410 | } | |
775c63fc | 411 | # endif |
dc014d43 DSH |
412 | /* Only call bn_mul_comba 8 if n2 == 8 and the |
413 | * two arrays are complete [steve] | |
414 | */ | |
415 | if (n2 == 8 && dna == 0 && dnb == 0) | |
dfeab068 RE |
416 | { |
417 | bn_mul_comba8(r,a,b); | |
418 | return; | |
419 | } | |
775c63fc | 420 | # endif /* BN_MUL_COMBA */ |
dc014d43 | 421 | /* Else do normal multiply */ |
dfeab068 RE |
422 | if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) |
423 | { | |
dc014d43 DSH |
424 | bn_mul_normal(r,a,n2+dna,b,n2+dnb); |
425 | if ((dna + dnb) < 0) | |
426 | memset(&r[2*n2 + dna + dnb], 0, | |
427 | sizeof(BN_ULONG) * -(dna + dnb)); | |
dfeab068 RE |
428 | return; |
429 | } | |
430 | /* r=(a[0]-a[1])*(b[1]-b[0]) */ | |
6a2347ee RL |
431 | c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); |
432 | c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); | |
dfeab068 RE |
433 | zero=neg=0; |
434 | switch (c1*3+c2) | |
435 | { | |
436 | case -4: | |
6a2347ee RL |
437 | bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ |
438 | bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ | |
dfeab068 RE |
439 | break; |
440 | case -3: | |
441 | zero=1; | |
442 | break; | |
443 | case -2: | |
6a2347ee RL |
444 | bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ |
445 | bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ | |
dfeab068 RE |
446 | neg=1; |
447 | break; | |
448 | case -1: | |
449 | case 0: | |
450 | case 1: | |
451 | zero=1; | |
452 | break; | |
453 | case 2: | |
6a2347ee RL |
454 | bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ |
455 | bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ | |
dfeab068 RE |
456 | neg=1; |
457 | break; | |
458 | case 3: | |
459 | zero=1; | |
460 | break; | |
461 | case 4: | |
6a2347ee RL |
462 | bn_sub_part_words(t, a, &(a[n]),tna,n-tna); |
463 | bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); | |
dfeab068 | 464 | break; |
d02b48c6 RE |
465 | } |
466 | ||
775c63fc | 467 | # ifdef BN_MUL_COMBA |
765e5311 RL |
468 | if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take |
469 | extra args to do this well */ | |
dfeab068 RE |
470 | { |
471 | if (!zero) | |
472 | bn_mul_comba4(&(t[n2]),t,&(t[n])); | |
473 | else | |
474 | memset(&(t[n2]),0,8*sizeof(BN_ULONG)); | |
475 | ||
476 | bn_mul_comba4(r,a,b); | |
477 | bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n])); | |
478 | } | |
765e5311 RL |
479 | else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could |
480 | take extra args to do this | |
481 | well */ | |
dfeab068 RE |
482 | { |
483 | if (!zero) | |
484 | bn_mul_comba8(&(t[n2]),t,&(t[n])); | |
485 | else | |
486 | memset(&(t[n2]),0,16*sizeof(BN_ULONG)); | |
487 | ||
488 | bn_mul_comba8(r,a,b); | |
489 | bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n])); | |
490 | } | |
491 | else | |
775c63fc | 492 | # endif /* BN_MUL_COMBA */ |
dfeab068 RE |
493 | { |
494 | p= &(t[n2*2]); | |
495 | if (!zero) | |
6a2347ee | 496 | bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); |
dfeab068 RE |
497 | else |
498 | memset(&(t[n2]),0,n2*sizeof(BN_ULONG)); | |
6a2347ee RL |
499 | bn_mul_recursive(r,a,b,n,0,0,p); |
500 | bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,dna,dnb,p); | |
dfeab068 | 501 | } |
d02b48c6 | 502 | |
dfeab068 RE |
503 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign |
504 | * r[10] holds (a[0]*b[0]) | |
505 | * r[32] holds (b[1]*b[1]) | |
506 | */ | |
507 | ||
651d0aff | 508 | c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); |
dfeab068 RE |
509 | |
510 | if (neg) /* if t[32] is negative */ | |
d02b48c6 | 511 | { |
651d0aff | 512 | c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); |
dfeab068 RE |
513 | } |
514 | else | |
515 | { | |
516 | /* Might have a carry */ | |
651d0aff | 517 | c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2)); |
d02b48c6 | 518 | } |
d02b48c6 | 519 | |
dfeab068 RE |
520 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) |
521 | * r[10] holds (a[0]*b[0]) | |
522 | * r[32] holds (b[1]*b[1]) | |
523 | * c1 holds the carry bits | |
524 | */ | |
651d0aff | 525 | c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); |
dfeab068 RE |
526 | if (c1) |
527 | { | |
528 | p= &(r[n+n2]); | |
529 | lo= *p; | |
530 | ln=(lo+c1)&BN_MASK2; | |
531 | *p=ln; | |
58964a49 | 532 | |
dfeab068 RE |
533 | /* The overflow will stop before we over write |
534 | * words we should not overwrite */ | |
535 | if (ln < (BN_ULONG)c1) | |
536 | { | |
537 | do { | |
538 | p++; | |
539 | lo= *p; | |
540 | ln=(lo+1)&BN_MASK2; | |
541 | *p=ln; | |
542 | } while (ln == 0); | |
543 | } | |
544 | } | |
545 | } | |
58964a49 | 546 | |
dfeab068 RE |
547 | /* n+tn is the word length |
548 | * t needs to be n*4 is size, as does r */ | |
231a737a | 549 | /* tnX may not be negative but less than n */ |
6a2347ee RL |
550 | void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, |
551 | int tna, int tnb, BN_ULONG *t) | |
58964a49 | 552 | { |
dfeab068 | 553 | int i,j,n2=n*2; |
d8869758 | 554 | int c1,c2,neg; |
dfeab068 | 555 | BN_ULONG ln,lo,*p; |
58964a49 | 556 | |
775c63fc | 557 | # ifdef BN_COUNT |
231a737a AP |
558 | fprintf(stderr," bn_mul_part_recursive (%d%+d) * (%d%+d)\n", |
559 | n, tna, n, tnb); | |
775c63fc | 560 | # endif |
dfeab068 RE |
561 | if (n < 8) |
562 | { | |
6a2347ee | 563 | bn_mul_normal(r,a,n+tna,b,n+tnb); |
dfeab068 RE |
564 | return; |
565 | } | |
566 | ||
567 | /* r=(a[0]-a[1])*(b[1]-b[0]) */ | |
6a2347ee RL |
568 | c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); |
569 | c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); | |
d8869758 | 570 | neg=0; |
688938fb UM |
571 | switch (c1*3+c2) |
572 | { | |
573 | case -4: | |
6a2347ee RL |
574 | bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ |
575 | bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ | |
688938fb UM |
576 | break; |
577 | case -3: | |
688938fb UM |
578 | /* break; */ |
579 | case -2: | |
6a2347ee RL |
580 | bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ |
581 | bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ | |
688938fb UM |
582 | neg=1; |
583 | break; | |
584 | case -1: | |
585 | case 0: | |
586 | case 1: | |
688938fb UM |
587 | /* break; */ |
588 | case 2: | |
6a2347ee RL |
589 | bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ |
590 | bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ | |
688938fb UM |
591 | neg=1; |
592 | break; | |
593 | case 3: | |
688938fb UM |
594 | /* break; */ |
595 | case 4: | |
6a2347ee RL |
596 | bn_sub_part_words(t, a, &(a[n]),tna,n-tna); |
597 | bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); | |
688938fb UM |
598 | break; |
599 | } | |
600 | /* The zero case isn't yet implemented here. The speedup | |
601 | would probably be negligible. */ | |
775c63fc UM |
602 | # if 0 |
603 | if (n == 4) | |
dfeab068 RE |
604 | { |
605 | bn_mul_comba4(&(t[n2]),t,&(t[n])); | |
606 | bn_mul_comba4(r,a,b); | |
607 | bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); | |
608 | memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2)); | |
609 | } | |
775c63fc UM |
610 | else |
611 | # endif | |
612 | if (n == 8) | |
58964a49 | 613 | { |
dfeab068 RE |
614 | bn_mul_comba8(&(t[n2]),t,&(t[n])); |
615 | bn_mul_comba8(r,a,b); | |
6a2347ee RL |
616 | bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); |
617 | memset(&(r[n2+tna+tnb]),0,sizeof(BN_ULONG)*(n2-tna-tnb)); | |
58964a49 RE |
618 | } |
619 | else | |
620 | { | |
dfeab068 | 621 | p= &(t[n2*2]); |
6a2347ee RL |
622 | bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); |
623 | bn_mul_recursive(r,a,b,n,0,0,p); | |
dfeab068 RE |
624 | i=n/2; |
625 | /* If there is only a bottom half to the number, | |
626 | * just do it */ | |
6a2347ee RL |
627 | if (tna > tnb) |
628 | j = tna - i; | |
629 | else | |
630 | j = tnb - i; | |
dfeab068 RE |
631 | if (j == 0) |
632 | { | |
6a2347ee RL |
633 | bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]), |
634 | i,tna-i,tnb-i,p); | |
dfeab068 RE |
635 | memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2)); |
636 | } | |
637 | else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */ | |
638 | { | |
639 | bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]), | |
6a2347ee RL |
640 | i,tna-i,tnb-i,p); |
641 | memset(&(r[n2+tna+tnb]),0, | |
642 | sizeof(BN_ULONG)*(n2-tna-tnb)); | |
dfeab068 RE |
643 | } |
644 | else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ | |
645 | { | |
646 | memset(&(r[n2]),0,sizeof(BN_ULONG)*n2); | |
6a2347ee RL |
647 | if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL |
648 | && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) | |
dfeab068 | 649 | { |
6a2347ee | 650 | bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); |
dfeab068 RE |
651 | } |
652 | else | |
653 | { | |
654 | for (;;) | |
655 | { | |
656 | i/=2; | |
231a737a AP |
657 | /* these simplified conditions work |
658 | * exclusively because difference | |
659 | * between tna and tnb is 1 or 0 */ | |
660 | if (i < tna || i < tnb) | |
dfeab068 | 661 | { |
231a737a | 662 | bn_mul_part_recursive(&(r[n2]), |
dfeab068 | 663 | &(a[n]),&(b[n]), |
6a2347ee | 664 | i,tna-i,tnb-i,p); |
dfeab068 RE |
665 | break; |
666 | } | |
231a737a | 667 | else if (i == tna || i == tnb) |
dfeab068 | 668 | { |
231a737a | 669 | bn_mul_recursive(&(r[n2]), |
dfeab068 | 670 | &(a[n]),&(b[n]), |
6a2347ee | 671 | i,tna-i,tnb-i,p); |
dfeab068 RE |
672 | break; |
673 | } | |
674 | } | |
675 | } | |
676 | } | |
677 | } | |
678 | ||
679 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign | |
680 | * r[10] holds (a[0]*b[0]) | |
681 | * r[32] holds (b[1]*b[1]) | |
682 | */ | |
683 | ||
651d0aff | 684 | c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); |
688938fb UM |
685 | |
686 | if (neg) /* if t[32] is negative */ | |
687 | { | |
688 | c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); | |
689 | } | |
690 | else | |
691 | { | |
692 | /* Might have a carry */ | |
693 | c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2)); | |
694 | } | |
dfeab068 RE |
695 | |
696 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) | |
697 | * r[10] holds (a[0]*b[0]) | |
698 | * r[32] holds (b[1]*b[1]) | |
699 | * c1 holds the carry bits | |
700 | */ | |
651d0aff | 701 | c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); |
dfeab068 RE |
702 | if (c1) |
703 | { | |
704 | p= &(r[n+n2]); | |
705 | lo= *p; | |
706 | ln=(lo+c1)&BN_MASK2; | |
707 | *p=ln; | |
708 | ||
709 | /* The overflow will stop before we over write | |
710 | * words we should not overwrite */ | |
f5f7dffd | 711 | if (ln < (BN_ULONG)c1) |
dfeab068 RE |
712 | { |
713 | do { | |
714 | p++; | |
715 | lo= *p; | |
716 | ln=(lo+1)&BN_MASK2; | |
717 | *p=ln; | |
718 | } while (ln == 0); | |
719 | } | |
58964a49 | 720 | } |
58964a49 RE |
721 | } |
722 | ||
dfeab068 RE |
723 | /* a and b must be the same size, which is n2. |
724 | * r needs to be n2 words and t needs to be n2*2 | |
725 | */ | |
6b691a5c UM |
726 | void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, |
727 | BN_ULONG *t) | |
58964a49 | 728 | { |
dfeab068 RE |
729 | int n=n2/2; |
730 | ||
775c63fc | 731 | # ifdef BN_COUNT |
67d93e6f | 732 | fprintf(stderr," bn_mul_low_recursive %d * %d\n",n2,n2); |
775c63fc | 733 | # endif |
dfeab068 | 734 | |
6a2347ee | 735 | bn_mul_recursive(r,a,b,n,0,0,&(t[0])); |
dfeab068 RE |
736 | if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) |
737 | { | |
738 | bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2])); | |
739 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); | |
740 | bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2])); | |
741 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); | |
742 | } | |
743 | else | |
744 | { | |
745 | bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n); | |
746 | bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n); | |
747 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); | |
748 | bn_add_words(&(r[n]),&(r[n]),&(t[n]),n); | |
749 | } | |
58964a49 RE |
750 | } |
751 | ||
dfeab068 RE |
752 | /* a and b must be the same size, which is n2. |
753 | * r needs to be n2 words and t needs to be n2*2 | |
754 | * l is the low words of the output. | |
755 | * t needs to be n2*3 | |
756 | */ | |
6b691a5c UM |
757 | void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, |
758 | BN_ULONG *t) | |
58964a49 | 759 | { |
dfeab068 RE |
760 | int i,n; |
761 | int c1,c2; | |
762 | int neg,oneg,zero; | |
763 | BN_ULONG ll,lc,*lp,*mp; | |
764 | ||
775c63fc | 765 | # ifdef BN_COUNT |
67d93e6f | 766 | fprintf(stderr," bn_mul_high %d * %d\n",n2,n2); |
775c63fc | 767 | # endif |
a0a54079 | 768 | n=n2/2; |
dfeab068 RE |
769 | |
770 | /* Calculate (al-ah)*(bh-bl) */ | |
771 | neg=zero=0; | |
772 | c1=bn_cmp_words(&(a[0]),&(a[n]),n); | |
773 | c2=bn_cmp_words(&(b[n]),&(b[0]),n); | |
774 | switch (c1*3+c2) | |
775 | { | |
776 | case -4: | |
777 | bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n); | |
778 | bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n); | |
779 | break; | |
780 | case -3: | |
781 | zero=1; | |
782 | break; | |
783 | case -2: | |
784 | bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n); | |
785 | bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n); | |
786 | neg=1; | |
787 | break; | |
788 | case -1: | |
789 | case 0: | |
790 | case 1: | |
791 | zero=1; | |
792 | break; | |
793 | case 2: | |
794 | bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n); | |
795 | bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n); | |
796 | neg=1; | |
797 | break; | |
798 | case 3: | |
799 | zero=1; | |
800 | break; | |
801 | case 4: | |
802 | bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n); | |
803 | bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n); | |
804 | break; | |
805 | } | |
806 | ||
807 | oneg=neg; | |
808 | /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ | |
809 | /* r[10] = (a[1]*b[1]) */ | |
775c63fc | 810 | # ifdef BN_MUL_COMBA |
dfeab068 RE |
811 | if (n == 8) |
812 | { | |
813 | bn_mul_comba8(&(t[0]),&(r[0]),&(r[n])); | |
814 | bn_mul_comba8(r,&(a[n]),&(b[n])); | |
815 | } | |
816 | else | |
775c63fc | 817 | # endif |
dfeab068 | 818 | { |
6a2347ee RL |
819 | bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,0,0,&(t[n2])); |
820 | bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2])); | |
dfeab068 | 821 | } |
58964a49 | 822 | |
dfeab068 RE |
823 | /* s0 == low(al*bl) |
824 | * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) | |
825 | * We know s0 and s1 so the only unknown is high(al*bl) | |
826 | * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) | |
827 | * high(al*bl) == s1 - (r[0]+l[0]+t[0]) | |
828 | */ | |
829 | if (l != NULL) | |
58964a49 | 830 | { |
dfeab068 | 831 | lp= &(t[n2+n]); |
651d0aff | 832 | c1=(int)(bn_add_words(lp,&(r[0]),&(l[0]),n)); |
dfeab068 RE |
833 | } |
834 | else | |
835 | { | |
836 | c1=0; | |
837 | lp= &(r[0]); | |
838 | } | |
839 | ||
840 | if (neg) | |
651d0aff | 841 | neg=(int)(bn_sub_words(&(t[n2]),lp,&(t[0]),n)); |
dfeab068 RE |
842 | else |
843 | { | |
844 | bn_add_words(&(t[n2]),lp,&(t[0]),n); | |
845 | neg=0; | |
846 | } | |
847 | ||
848 | if (l != NULL) | |
849 | { | |
850 | bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n); | |
851 | } | |
852 | else | |
853 | { | |
854 | lp= &(t[n2+n]); | |
855 | mp= &(t[n2]); | |
856 | for (i=0; i<n; i++) | |
857 | lp[i]=((~mp[i])+1)&BN_MASK2; | |
858 | } | |
859 | ||
860 | /* s[0] = low(al*bl) | |
861 | * t[3] = high(al*bl) | |
862 | * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign | |
863 | * r[10] = (a[1]*b[1]) | |
864 | */ | |
865 | /* R[10] = al*bl | |
866 | * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) | |
867 | * R[32] = ah*bh | |
868 | */ | |
869 | /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) | |
870 | * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) | |
871 | * R[3]=r[1]+(carry/borrow) | |
872 | */ | |
873 | if (l != NULL) | |
874 | { | |
875 | lp= &(t[n2]); | |
651d0aff | 876 | c1= (int)(bn_add_words(lp,&(t[n2+n]),&(l[0]),n)); |
dfeab068 RE |
877 | } |
878 | else | |
879 | { | |
880 | lp= &(t[n2+n]); | |
881 | c1=0; | |
882 | } | |
651d0aff | 883 | c1+=(int)(bn_add_words(&(t[n2]),lp, &(r[0]),n)); |
dfeab068 | 884 | if (oneg) |
651d0aff | 885 | c1-=(int)(bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n)); |
dfeab068 | 886 | else |
651d0aff | 887 | c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n)); |
dfeab068 | 888 | |
651d0aff RE |
889 | c2 =(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n)); |
890 | c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(r[n]),n)); | |
dfeab068 | 891 | if (oneg) |
651d0aff | 892 | c2-=(int)(bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n)); |
dfeab068 | 893 | else |
651d0aff | 894 | c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n]),n)); |
dfeab068 RE |
895 | |
896 | if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */ | |
897 | { | |
898 | i=0; | |
899 | if (c1 > 0) | |
900 | { | |
901 | lc=c1; | |
902 | do { | |
903 | ll=(r[i]+lc)&BN_MASK2; | |
904 | r[i++]=ll; | |
905 | lc=(lc > ll); | |
906 | } while (lc); | |
907 | } | |
908 | else | |
909 | { | |
910 | lc= -c1; | |
911 | do { | |
912 | ll=r[i]; | |
913 | r[i++]=(ll-lc)&BN_MASK2; | |
914 | lc=(lc > ll); | |
915 | } while (lc); | |
916 | } | |
917 | } | |
918 | if (c2 != 0) /* Add starting at r[1] */ | |
919 | { | |
920 | i=n; | |
921 | if (c2 > 0) | |
922 | { | |
923 | lc=c2; | |
924 | do { | |
925 | ll=(r[i]+lc)&BN_MASK2; | |
926 | r[i++]=ll; | |
927 | lc=(lc > ll); | |
928 | } while (lc); | |
929 | } | |
930 | else | |
931 | { | |
932 | lc= -c2; | |
933 | do { | |
934 | ll=r[i]; | |
935 | r[i++]=(ll-lc)&BN_MASK2; | |
936 | lc=(lc > ll); | |
937 | } while (lc); | |
938 | } | |
58964a49 | 939 | } |
58964a49 | 940 | } |
775c63fc | 941 | #endif /* BN_RECURSION */ |
58964a49 | 942 | |
6a2347ee | 943 | int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) |
58964a49 | 944 | { |
6a2347ee | 945 | int ret=0; |
a0a54079 MC |
946 | int top,al,bl; |
947 | BIGNUM *rr; | |
775c63fc UM |
948 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
949 | int i; | |
950 | #endif | |
a0a54079 | 951 | #ifdef BN_RECURSION |
765e5311 | 952 | BIGNUM *t=NULL; |
2aff7727 | 953 | int j=0,k; |
a0a54079 | 954 | #endif |
dfeab068 RE |
955 | |
956 | #ifdef BN_COUNT | |
67d93e6f | 957 | fprintf(stderr,"BN_mul %d * %d\n",a->top,b->top); |
dfeab068 RE |
958 | #endif |
959 | ||
960 | bn_check_top(a); | |
961 | bn_check_top(b); | |
962 | bn_check_top(r); | |
58964a49 | 963 | |
dfeab068 RE |
964 | al=a->top; |
965 | bl=b->top; | |
dfeab068 RE |
966 | |
967 | if ((al == 0) || (bl == 0)) | |
58964a49 | 968 | { |
b6358c89 | 969 | BN_zero(r); |
dfeab068 | 970 | return(1); |
58964a49 | 971 | } |
dfeab068 | 972 | top=al+bl; |
a0a54079 | 973 | |
9b141126 | 974 | BN_CTX_start(ctx); |
a0a54079 | 975 | if ((r == a) || (r == b)) |
9b141126 UM |
976 | { |
977 | if ((rr = BN_CTX_get(ctx)) == NULL) goto err; | |
978 | } | |
a0a54079 | 979 | else |
9b141126 | 980 | rr = r; |
47ff5de8 | 981 | rr->neg=a->neg^b->neg; |
a0a54079 | 982 | |
dfeab068 | 983 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
775c63fc UM |
984 | i = al-bl; |
985 | #endif | |
986 | #ifdef BN_MUL_COMBA | |
987 | if (i == 0) | |
dfeab068 | 988 | { |
775c63fc UM |
989 | # if 0 |
990 | if (al == 4) | |
dfeab068 | 991 | { |
9b141126 | 992 | if (bn_wexpand(rr,8) == NULL) goto err; |
5965902e | 993 | rr->top=8; |
a0a54079 | 994 | bn_mul_comba4(rr->d,a->d,b->d); |
dfeab068 RE |
995 | goto end; |
996 | } | |
775c63fc UM |
997 | # endif |
998 | if (al == 8) | |
dfeab068 | 999 | { |
9b141126 | 1000 | if (bn_wexpand(rr,16) == NULL) goto err; |
5965902e | 1001 | rr->top=16; |
a0a54079 | 1002 | bn_mul_comba8(rr->d,a->d,b->d); |
dfeab068 RE |
1003 | goto end; |
1004 | } | |
dfeab068 | 1005 | } |
775c63fc | 1006 | #endif /* BN_MUL_COMBA */ |
dfeab068 | 1007 | #ifdef BN_RECURSION |
775c63fc | 1008 | if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) |
dfeab068 | 1009 | { |
6a2347ee RL |
1010 | if (i >= -1 && i <= 1) |
1011 | { | |
6a2347ee RL |
1012 | /* Find out the power of two lower or equal |
1013 | to the longest of the two numbers */ | |
1014 | if (i >= 0) | |
1015 | { | |
1016 | j = BN_num_bits_word((BN_ULONG)al); | |
1017 | } | |
1018 | if (i == -1) | |
1019 | { | |
1020 | j = BN_num_bits_word((BN_ULONG)bl); | |
1021 | } | |
6a2347ee RL |
1022 | j = 1<<(j-1); |
1023 | assert(j <= al || j <= bl); | |
1024 | k = j+j; | |
1025 | t = BN_CTX_get(ctx); | |
15684f58 DSH |
1026 | if (t == NULL) |
1027 | goto err; | |
6a2347ee RL |
1028 | if (al > j || bl > j) |
1029 | { | |
1ff44a99 DSH |
1030 | if (bn_wexpand(t,k*4) == NULL) goto err; |
1031 | if (bn_wexpand(rr,k*4) == NULL) goto err; | |
6a2347ee RL |
1032 | bn_mul_part_recursive(rr->d,a->d,b->d, |
1033 | j,al-j,bl-j,t->d); | |
1034 | } | |
1035 | else /* al <= j || bl <= j */ | |
1036 | { | |
1ff44a99 DSH |
1037 | if (bn_wexpand(t,k*2) == NULL) goto err; |
1038 | if (bn_wexpand(rr,k*2) == NULL) goto err; | |
6a2347ee RL |
1039 | bn_mul_recursive(rr->d,a->d,b->d, |
1040 | j,al-j,bl-j,t->d); | |
1041 | } | |
1042 | rr->top=top; | |
1043 | goto end; | |
1044 | } | |
1045 | #if 0 | |
775c63fc | 1046 | if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA)) |
dfeab068 | 1047 | { |
baa257f1 | 1048 | BIGNUM *tmp_bn = (BIGNUM *)b; |
9cdf87f1 | 1049 | if (bn_wexpand(tmp_bn,al) == NULL) goto err; |
baa257f1 | 1050 | tmp_bn->d[bl]=0; |
dfeab068 | 1051 | bl++; |
775c63fc | 1052 | i--; |
dfeab068 | 1053 | } |
775c63fc | 1054 | else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA)) |
dfeab068 | 1055 | { |
baa257f1 | 1056 | BIGNUM *tmp_bn = (BIGNUM *)a; |
9cdf87f1 | 1057 | if (bn_wexpand(tmp_bn,bl) == NULL) goto err; |
baa257f1 | 1058 | tmp_bn->d[al]=0; |
dfeab068 | 1059 | al++; |
775c63fc UM |
1060 | i++; |
1061 | } | |
1062 | if (i == 0) | |
1063 | { | |
1064 | /* symmetric and > 4 */ | |
1065 | /* 16 or larger */ | |
1066 | j=BN_num_bits_word((BN_ULONG)al); | |
1067 | j=1<<(j-1); | |
1068 | k=j+j; | |
1069 | t = BN_CTX_get(ctx); | |
1070 | if (al == j) /* exact multiple */ | |
1071 | { | |
9cdf87f1 RL |
1072 | if (bn_wexpand(t,k*2) == NULL) goto err; |
1073 | if (bn_wexpand(rr,k*2) == NULL) goto err; | |
775c63fc UM |
1074 | bn_mul_recursive(rr->d,a->d,b->d,al,t->d); |
1075 | } | |
1076 | else | |
1077 | { | |
9cdf87f1 RL |
1078 | if (bn_wexpand(t,k*4) == NULL) goto err; |
1079 | if (bn_wexpand(rr,k*4) == NULL) goto err; | |
775c63fc UM |
1080 | bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d); |
1081 | } | |
1082 | rr->top=top; | |
1083 | goto end; | |
dfeab068 | 1084 | } |
6a2347ee | 1085 | #endif |
dfeab068 | 1086 | } |
775c63fc | 1087 | #endif /* BN_RECURSION */ |
9b141126 | 1088 | if (bn_wexpand(rr,top) == NULL) goto err; |
a0a54079 MC |
1089 | rr->top=top; |
1090 | bn_mul_normal(rr->d,a->d,al,b->d,bl); | |
58964a49 | 1091 | |
a0a54079 | 1092 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
dfeab068 | 1093 | end: |
a0a54079 | 1094 | #endif |
d870740c | 1095 | bn_correct_top(rr); |
a0a54079 | 1096 | if (r != rr) BN_copy(r,rr); |
775c63fc | 1097 | ret=1; |
9b141126 | 1098 | err: |
d870740c | 1099 | bn_check_top(r); |
b6358c89 | 1100 | BN_CTX_end(ctx); |
775c63fc | 1101 | return(ret); |
dfeab068 | 1102 | } |
58964a49 | 1103 | |
6b691a5c | 1104 | void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) |
dfeab068 RE |
1105 | { |
1106 | BN_ULONG *rr; | |
58964a49 | 1107 | |
dfeab068 | 1108 | #ifdef BN_COUNT |
67d93e6f | 1109 | fprintf(stderr," bn_mul_normal %d * %d\n",na,nb); |
dfeab068 | 1110 | #endif |
58964a49 | 1111 | |
dfeab068 RE |
1112 | if (na < nb) |
1113 | { | |
1114 | int itmp; | |
1115 | BN_ULONG *ltmp; | |
58964a49 | 1116 | |
dfeab068 RE |
1117 | itmp=na; na=nb; nb=itmp; |
1118 | ltmp=a; a=b; b=ltmp; | |
58964a49 | 1119 | |
dfeab068 RE |
1120 | } |
1121 | rr= &(r[na]); | |
53b407da RL |
1122 | if (nb <= 0) |
1123 | { | |
1124 | (void)bn_mul_words(r,a,na,0); | |
1125 | return; | |
1126 | } | |
1127 | else | |
1128 | rr[0]=bn_mul_words(r,a,na,b[0]); | |
58964a49 | 1129 | |
dfeab068 RE |
1130 | for (;;) |
1131 | { | |
1132 | if (--nb <= 0) return; | |
1133 | rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]); | |
1134 | if (--nb <= 0) return; | |
1135 | rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]); | |
1136 | if (--nb <= 0) return; | |
1137 | rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]); | |
1138 | if (--nb <= 0) return; | |
1139 | rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]); | |
1140 | rr+=4; | |
1141 | r+=4; | |
1142 | b+=4; | |
1143 | } | |
58964a49 | 1144 | } |
dfeab068 | 1145 | |
6b691a5c | 1146 | void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) |
dfeab068 RE |
1147 | { |
1148 | #ifdef BN_COUNT | |
67d93e6f | 1149 | fprintf(stderr," bn_mul_low_normal %d * %d\n",n,n); |
58964a49 | 1150 | #endif |
dfeab068 RE |
1151 | bn_mul_words(r,a,n,b[0]); |
1152 | ||
1153 | for (;;) | |
1154 | { | |
1155 | if (--n <= 0) return; | |
1156 | bn_mul_add_words(&(r[1]),a,n,b[1]); | |
1157 | if (--n <= 0) return; | |
1158 | bn_mul_add_words(&(r[2]),a,n,b[2]); | |
1159 | if (--n <= 0) return; | |
1160 | bn_mul_add_words(&(r[3]),a,n,b[3]); | |
1161 | if (--n <= 0) return; | |
1162 | bn_mul_add_words(&(r[4]),a,n,b[4]); | |
1163 | r+=4; | |
1164 | b+=4; | |
1165 | } | |
1166 | } |