]>
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 | 80 | BN_ULONG bn_sub_part_words(BN_ULONG *r, |
6343829a GT |
81 | const BN_ULONG *a, const BN_ULONG *b, |
82 | int cl, int dl) | |
baa257f1 RL |
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 | { | |
6343829a | 129 | int save_dl = dl; |
baa257f1 RL |
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, | |
6343829a GT |
208 | const BN_ULONG *a, const BN_ULONG *b, |
209 | int cl, int dl) | |
baa257f1 RL |
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 | { | |
6343829a | 225 | int save_dl = dl; |
baa257f1 RL |
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 | */ | |
70ba4ee5 | 392 | /* dnX may not be positive, but n2/2+dnX has to be */ |
6343829a GT |
393 | void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, |
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 |
70ba4ee5 | 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 | ||
6343829a | 508 | c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); |
dfeab068 RE |
509 | |
510 | if (neg) /* if t[32] is negative */ | |
d02b48c6 | 511 | { |
6343829a | 512 | c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); |
dfeab068 RE |
513 | } |
514 | else | |
515 | { | |
516 | /* Might have a carry */ | |
6343829a | 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 | */ | |
6343829a | 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 */ | |
70ba4ee5 | 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; |
83743ad0 | 554 | int c1,c2,neg,zero; |
dfeab068 | 555 | BN_ULONG ln,lo,*p; |
58964a49 | 556 | |
775c63fc | 557 | # ifdef BN_COUNT |
70ba4ee5 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); | |
688938fb UM |
570 | zero=neg=0; |
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: | |
578 | zero=1; | |
579 | /* break; */ | |
580 | case -2: | |
6a2347ee RL |
581 | bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ |
582 | bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ | |
688938fb UM |
583 | neg=1; |
584 | break; | |
585 | case -1: | |
586 | case 0: | |
587 | case 1: | |
588 | zero=1; | |
589 | /* break; */ | |
590 | case 2: | |
6a2347ee RL |
591 | bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ |
592 | bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ | |
688938fb UM |
593 | neg=1; |
594 | break; | |
595 | case 3: | |
596 | zero=1; | |
597 | /* break; */ | |
598 | case 4: | |
6a2347ee RL |
599 | bn_sub_part_words(t, a, &(a[n]),tna,n-tna); |
600 | bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); | |
688938fb UM |
601 | break; |
602 | } | |
603 | /* The zero case isn't yet implemented here. The speedup | |
604 | would probably be negligible. */ | |
775c63fc UM |
605 | # if 0 |
606 | if (n == 4) | |
dfeab068 RE |
607 | { |
608 | bn_mul_comba4(&(t[n2]),t,&(t[n])); | |
609 | bn_mul_comba4(r,a,b); | |
610 | bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); | |
611 | memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2)); | |
612 | } | |
775c63fc UM |
613 | else |
614 | # endif | |
615 | if (n == 8) | |
58964a49 | 616 | { |
dfeab068 RE |
617 | bn_mul_comba8(&(t[n2]),t,&(t[n])); |
618 | bn_mul_comba8(r,a,b); | |
6a2347ee RL |
619 | bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); |
620 | memset(&(r[n2+tna+tnb]),0,sizeof(BN_ULONG)*(n2-tna-tnb)); | |
58964a49 RE |
621 | } |
622 | else | |
623 | { | |
dfeab068 | 624 | p= &(t[n2*2]); |
6a2347ee RL |
625 | bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); |
626 | bn_mul_recursive(r,a,b,n,0,0,p); | |
dfeab068 RE |
627 | i=n/2; |
628 | /* If there is only a bottom half to the number, | |
629 | * just do it */ | |
6a2347ee RL |
630 | if (tna > tnb) |
631 | j = tna - i; | |
632 | else | |
633 | j = tnb - i; | |
dfeab068 RE |
634 | if (j == 0) |
635 | { | |
6a2347ee RL |
636 | bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]), |
637 | i,tna-i,tnb-i,p); | |
dfeab068 RE |
638 | memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2)); |
639 | } | |
640 | else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */ | |
641 | { | |
642 | bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]), | |
6a2347ee RL |
643 | i,tna-i,tnb-i,p); |
644 | memset(&(r[n2+tna+tnb]),0, | |
645 | sizeof(BN_ULONG)*(n2-tna-tnb)); | |
dfeab068 RE |
646 | } |
647 | else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ | |
648 | { | |
649 | memset(&(r[n2]),0,sizeof(BN_ULONG)*n2); | |
6a2347ee RL |
650 | if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL |
651 | && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) | |
dfeab068 | 652 | { |
6a2347ee | 653 | bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); |
dfeab068 RE |
654 | } |
655 | else | |
656 | { | |
657 | for (;;) | |
658 | { | |
659 | i/=2; | |
70ba4ee5 AP |
660 | /* these simplified conditions work |
661 | * exclusively because difference | |
662 | * between tna and tnb is 1 or 0 */ | |
663 | if (i < tna || i < tnb) | |
dfeab068 | 664 | { |
70ba4ee5 | 665 | bn_mul_part_recursive(&(r[n2]), |
dfeab068 | 666 | &(a[n]),&(b[n]), |
6a2347ee | 667 | i,tna-i,tnb-i,p); |
dfeab068 RE |
668 | break; |
669 | } | |
70ba4ee5 | 670 | else if (i == tna || i == tnb) |
dfeab068 | 671 | { |
70ba4ee5 | 672 | bn_mul_recursive(&(r[n2]), |
dfeab068 | 673 | &(a[n]),&(b[n]), |
6a2347ee | 674 | i,tna-i,tnb-i,p); |
dfeab068 RE |
675 | break; |
676 | } | |
677 | } | |
678 | } | |
679 | } | |
680 | } | |
681 | ||
682 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign | |
683 | * r[10] holds (a[0]*b[0]) | |
684 | * r[32] holds (b[1]*b[1]) | |
685 | */ | |
686 | ||
651d0aff | 687 | c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); |
688938fb UM |
688 | |
689 | if (neg) /* if t[32] is negative */ | |
690 | { | |
691 | c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); | |
692 | } | |
693 | else | |
694 | { | |
695 | /* Might have a carry */ | |
696 | c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2)); | |
697 | } | |
dfeab068 RE |
698 | |
699 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) | |
700 | * r[10] holds (a[0]*b[0]) | |
701 | * r[32] holds (b[1]*b[1]) | |
702 | * c1 holds the carry bits | |
703 | */ | |
651d0aff | 704 | c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); |
dfeab068 RE |
705 | if (c1) |
706 | { | |
707 | p= &(r[n+n2]); | |
708 | lo= *p; | |
709 | ln=(lo+c1)&BN_MASK2; | |
710 | *p=ln; | |
711 | ||
712 | /* The overflow will stop before we over write | |
713 | * words we should not overwrite */ | |
f5f7dffd | 714 | if (ln < (BN_ULONG)c1) |
dfeab068 RE |
715 | { |
716 | do { | |
717 | p++; | |
718 | lo= *p; | |
719 | ln=(lo+1)&BN_MASK2; | |
720 | *p=ln; | |
721 | } while (ln == 0); | |
722 | } | |
58964a49 | 723 | } |
58964a49 RE |
724 | } |
725 | ||
dfeab068 RE |
726 | /* a and b must be the same size, which is n2. |
727 | * r needs to be n2 words and t needs to be n2*2 | |
728 | */ | |
6b691a5c UM |
729 | void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, |
730 | BN_ULONG *t) | |
58964a49 | 731 | { |
dfeab068 RE |
732 | int n=n2/2; |
733 | ||
775c63fc | 734 | # ifdef BN_COUNT |
67d93e6f | 735 | fprintf(stderr," bn_mul_low_recursive %d * %d\n",n2,n2); |
775c63fc | 736 | # endif |
dfeab068 | 737 | |
6a2347ee | 738 | bn_mul_recursive(r,a,b,n,0,0,&(t[0])); |
dfeab068 RE |
739 | if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) |
740 | { | |
741 | bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2])); | |
742 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); | |
743 | bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2])); | |
744 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); | |
745 | } | |
746 | else | |
747 | { | |
748 | bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n); | |
749 | bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n); | |
750 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); | |
751 | bn_add_words(&(r[n]),&(r[n]),&(t[n]),n); | |
752 | } | |
58964a49 RE |
753 | } |
754 | ||
dfeab068 RE |
755 | /* a and b must be the same size, which is n2. |
756 | * r needs to be n2 words and t needs to be n2*2 | |
757 | * l is the low words of the output. | |
758 | * t needs to be n2*3 | |
759 | */ | |
6b691a5c UM |
760 | void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, |
761 | BN_ULONG *t) | |
58964a49 | 762 | { |
dfeab068 RE |
763 | int i,n; |
764 | int c1,c2; | |
765 | int neg,oneg,zero; | |
766 | BN_ULONG ll,lc,*lp,*mp; | |
767 | ||
775c63fc | 768 | # ifdef BN_COUNT |
67d93e6f | 769 | fprintf(stderr," bn_mul_high %d * %d\n",n2,n2); |
775c63fc | 770 | # endif |
a0a54079 | 771 | n=n2/2; |
dfeab068 RE |
772 | |
773 | /* Calculate (al-ah)*(bh-bl) */ | |
774 | neg=zero=0; | |
775 | c1=bn_cmp_words(&(a[0]),&(a[n]),n); | |
776 | c2=bn_cmp_words(&(b[n]),&(b[0]),n); | |
777 | switch (c1*3+c2) | |
778 | { | |
779 | case -4: | |
780 | bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n); | |
781 | bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n); | |
782 | break; | |
783 | case -3: | |
784 | zero=1; | |
785 | break; | |
786 | case -2: | |
787 | bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n); | |
788 | bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n); | |
789 | neg=1; | |
790 | break; | |
791 | case -1: | |
792 | case 0: | |
793 | case 1: | |
794 | zero=1; | |
795 | break; | |
796 | case 2: | |
797 | bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n); | |
798 | bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n); | |
799 | neg=1; | |
800 | break; | |
801 | case 3: | |
802 | zero=1; | |
803 | break; | |
804 | case 4: | |
805 | bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n); | |
806 | bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n); | |
807 | break; | |
808 | } | |
809 | ||
810 | oneg=neg; | |
811 | /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ | |
812 | /* r[10] = (a[1]*b[1]) */ | |
775c63fc | 813 | # ifdef BN_MUL_COMBA |
dfeab068 RE |
814 | if (n == 8) |
815 | { | |
816 | bn_mul_comba8(&(t[0]),&(r[0]),&(r[n])); | |
817 | bn_mul_comba8(r,&(a[n]),&(b[n])); | |
818 | } | |
819 | else | |
775c63fc | 820 | # endif |
dfeab068 | 821 | { |
6a2347ee RL |
822 | bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,0,0,&(t[n2])); |
823 | bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2])); | |
dfeab068 | 824 | } |
58964a49 | 825 | |
dfeab068 RE |
826 | /* s0 == low(al*bl) |
827 | * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) | |
828 | * We know s0 and s1 so the only unknown is high(al*bl) | |
829 | * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) | |
830 | * high(al*bl) == s1 - (r[0]+l[0]+t[0]) | |
831 | */ | |
832 | if (l != NULL) | |
58964a49 | 833 | { |
dfeab068 | 834 | lp= &(t[n2+n]); |
651d0aff | 835 | c1=(int)(bn_add_words(lp,&(r[0]),&(l[0]),n)); |
dfeab068 RE |
836 | } |
837 | else | |
838 | { | |
839 | c1=0; | |
840 | lp= &(r[0]); | |
841 | } | |
842 | ||
843 | if (neg) | |
651d0aff | 844 | neg=(int)(bn_sub_words(&(t[n2]),lp,&(t[0]),n)); |
dfeab068 RE |
845 | else |
846 | { | |
847 | bn_add_words(&(t[n2]),lp,&(t[0]),n); | |
848 | neg=0; | |
849 | } | |
850 | ||
851 | if (l != NULL) | |
852 | { | |
853 | bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n); | |
854 | } | |
855 | else | |
856 | { | |
857 | lp= &(t[n2+n]); | |
858 | mp= &(t[n2]); | |
859 | for (i=0; i<n; i++) | |
860 | lp[i]=((~mp[i])+1)&BN_MASK2; | |
861 | } | |
862 | ||
863 | /* s[0] = low(al*bl) | |
864 | * t[3] = high(al*bl) | |
865 | * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign | |
866 | * r[10] = (a[1]*b[1]) | |
867 | */ | |
868 | /* R[10] = al*bl | |
869 | * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) | |
870 | * R[32] = ah*bh | |
871 | */ | |
872 | /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) | |
873 | * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) | |
874 | * R[3]=r[1]+(carry/borrow) | |
875 | */ | |
876 | if (l != NULL) | |
877 | { | |
878 | lp= &(t[n2]); | |
651d0aff | 879 | c1= (int)(bn_add_words(lp,&(t[n2+n]),&(l[0]),n)); |
dfeab068 RE |
880 | } |
881 | else | |
882 | { | |
883 | lp= &(t[n2+n]); | |
884 | c1=0; | |
885 | } | |
651d0aff | 886 | c1+=(int)(bn_add_words(&(t[n2]),lp, &(r[0]),n)); |
dfeab068 | 887 | if (oneg) |
651d0aff | 888 | c1-=(int)(bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n)); |
dfeab068 | 889 | else |
651d0aff | 890 | c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n)); |
dfeab068 | 891 | |
651d0aff RE |
892 | c2 =(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n)); |
893 | c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(r[n]),n)); | |
dfeab068 | 894 | if (oneg) |
651d0aff | 895 | c2-=(int)(bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n)); |
dfeab068 | 896 | else |
651d0aff | 897 | c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n]),n)); |
dfeab068 RE |
898 | |
899 | if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */ | |
900 | { | |
901 | i=0; | |
902 | if (c1 > 0) | |
903 | { | |
904 | lc=c1; | |
905 | do { | |
906 | ll=(r[i]+lc)&BN_MASK2; | |
907 | r[i++]=ll; | |
908 | lc=(lc > ll); | |
909 | } while (lc); | |
910 | } | |
911 | else | |
912 | { | |
913 | lc= -c1; | |
914 | do { | |
915 | ll=r[i]; | |
916 | r[i++]=(ll-lc)&BN_MASK2; | |
917 | lc=(lc > ll); | |
918 | } while (lc); | |
919 | } | |
920 | } | |
921 | if (c2 != 0) /* Add starting at r[1] */ | |
922 | { | |
923 | i=n; | |
924 | if (c2 > 0) | |
925 | { | |
926 | lc=c2; | |
927 | do { | |
928 | ll=(r[i]+lc)&BN_MASK2; | |
929 | r[i++]=ll; | |
930 | lc=(lc > ll); | |
931 | } while (lc); | |
932 | } | |
933 | else | |
934 | { | |
935 | lc= -c2; | |
936 | do { | |
937 | ll=r[i]; | |
938 | r[i++]=(ll-lc)&BN_MASK2; | |
939 | lc=(lc > ll); | |
940 | } while (lc); | |
941 | } | |
58964a49 | 942 | } |
58964a49 | 943 | } |
775c63fc | 944 | #endif /* BN_RECURSION */ |
58964a49 | 945 | |
6a2347ee | 946 | int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) |
58964a49 | 947 | { |
6a2347ee | 948 | int ret=0; |
a0a54079 MC |
949 | int top,al,bl; |
950 | BIGNUM *rr; | |
775c63fc UM |
951 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
952 | int i; | |
953 | #endif | |
a0a54079 | 954 | #ifdef BN_RECURSION |
765e5311 | 955 | BIGNUM *t=NULL; |
2aff7727 | 956 | int j=0,k; |
a0a54079 | 957 | #endif |
dfeab068 RE |
958 | |
959 | #ifdef BN_COUNT | |
67d93e6f | 960 | fprintf(stderr,"BN_mul %d * %d\n",a->top,b->top); |
dfeab068 RE |
961 | #endif |
962 | ||
963 | bn_check_top(a); | |
964 | bn_check_top(b); | |
965 | bn_check_top(r); | |
58964a49 | 966 | |
dfeab068 RE |
967 | al=a->top; |
968 | bl=b->top; | |
dfeab068 RE |
969 | |
970 | if ((al == 0) || (bl == 0)) | |
58964a49 | 971 | { |
b6358c89 | 972 | BN_zero(r); |
dfeab068 | 973 | return(1); |
58964a49 | 974 | } |
dfeab068 | 975 | top=al+bl; |
a0a54079 | 976 | |
9b141126 | 977 | BN_CTX_start(ctx); |
a0a54079 | 978 | if ((r == a) || (r == b)) |
9b141126 UM |
979 | { |
980 | if ((rr = BN_CTX_get(ctx)) == NULL) goto err; | |
981 | } | |
a0a54079 | 982 | else |
9b141126 | 983 | rr = r; |
47ff5de8 | 984 | rr->neg=a->neg^b->neg; |
a0a54079 | 985 | |
dfeab068 | 986 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
775c63fc UM |
987 | i = al-bl; |
988 | #endif | |
989 | #ifdef BN_MUL_COMBA | |
990 | if (i == 0) | |
dfeab068 | 991 | { |
775c63fc UM |
992 | # if 0 |
993 | if (al == 4) | |
dfeab068 | 994 | { |
9b141126 | 995 | if (bn_wexpand(rr,8) == NULL) goto err; |
5965902e | 996 | rr->top=8; |
a0a54079 | 997 | bn_mul_comba4(rr->d,a->d,b->d); |
dfeab068 RE |
998 | goto end; |
999 | } | |
775c63fc UM |
1000 | # endif |
1001 | if (al == 8) | |
dfeab068 | 1002 | { |
9b141126 | 1003 | if (bn_wexpand(rr,16) == NULL) goto err; |
5965902e | 1004 | rr->top=16; |
a0a54079 | 1005 | bn_mul_comba8(rr->d,a->d,b->d); |
dfeab068 RE |
1006 | goto end; |
1007 | } | |
dfeab068 | 1008 | } |
775c63fc | 1009 | #endif /* BN_MUL_COMBA */ |
dfeab068 | 1010 | #ifdef BN_RECURSION |
775c63fc | 1011 | if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) |
dfeab068 | 1012 | { |
6a2347ee RL |
1013 | if (i >= -1 && i <= 1) |
1014 | { | |
1015 | int sav_j =0; | |
1016 | /* Find out the power of two lower or equal | |
1017 | to the longest of the two numbers */ | |
1018 | if (i >= 0) | |
1019 | { | |
1020 | j = BN_num_bits_word((BN_ULONG)al); | |
1021 | } | |
1022 | if (i == -1) | |
1023 | { | |
1024 | j = BN_num_bits_word((BN_ULONG)bl); | |
1025 | } | |
1026 | sav_j = j; | |
1027 | j = 1<<(j-1); | |
1028 | assert(j <= al || j <= bl); | |
1029 | k = j+j; | |
1030 | t = BN_CTX_get(ctx); | |
1031 | if (al > j || bl > j) | |
1032 | { | |
1033 | bn_wexpand(t,k*4); | |
1034 | bn_wexpand(rr,k*4); | |
1035 | bn_mul_part_recursive(rr->d,a->d,b->d, | |
1036 | j,al-j,bl-j,t->d); | |
1037 | } | |
1038 | else /* al <= j || bl <= j */ | |
1039 | { | |
1040 | bn_wexpand(t,k*2); | |
1041 | bn_wexpand(rr,k*2); | |
1042 | bn_mul_recursive(rr->d,a->d,b->d, | |
1043 | j,al-j,bl-j,t->d); | |
1044 | } | |
1045 | rr->top=top; | |
1046 | goto end; | |
1047 | } | |
1048 | #if 0 | |
775c63fc | 1049 | if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA)) |
dfeab068 | 1050 | { |
baa257f1 | 1051 | BIGNUM *tmp_bn = (BIGNUM *)b; |
9cdf87f1 | 1052 | if (bn_wexpand(tmp_bn,al) == NULL) goto err; |
baa257f1 | 1053 | tmp_bn->d[bl]=0; |
dfeab068 | 1054 | bl++; |
775c63fc | 1055 | i--; |
dfeab068 | 1056 | } |
775c63fc | 1057 | else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA)) |
dfeab068 | 1058 | { |
baa257f1 | 1059 | BIGNUM *tmp_bn = (BIGNUM *)a; |
9cdf87f1 | 1060 | if (bn_wexpand(tmp_bn,bl) == NULL) goto err; |
baa257f1 | 1061 | tmp_bn->d[al]=0; |
dfeab068 | 1062 | al++; |
775c63fc UM |
1063 | i++; |
1064 | } | |
1065 | if (i == 0) | |
1066 | { | |
1067 | /* symmetric and > 4 */ | |
1068 | /* 16 or larger */ | |
1069 | j=BN_num_bits_word((BN_ULONG)al); | |
1070 | j=1<<(j-1); | |
1071 | k=j+j; | |
1072 | t = BN_CTX_get(ctx); | |
1073 | if (al == j) /* exact multiple */ | |
1074 | { | |
9cdf87f1 RL |
1075 | if (bn_wexpand(t,k*2) == NULL) goto err; |
1076 | if (bn_wexpand(rr,k*2) == NULL) goto err; | |
775c63fc UM |
1077 | bn_mul_recursive(rr->d,a->d,b->d,al,t->d); |
1078 | } | |
1079 | else | |
1080 | { | |
9cdf87f1 RL |
1081 | if (bn_wexpand(t,k*4) == NULL) goto err; |
1082 | if (bn_wexpand(rr,k*4) == NULL) goto err; | |
775c63fc UM |
1083 | bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d); |
1084 | } | |
1085 | rr->top=top; | |
1086 | goto end; | |
dfeab068 | 1087 | } |
6a2347ee | 1088 | #endif |
dfeab068 | 1089 | } |
775c63fc | 1090 | #endif /* BN_RECURSION */ |
9b141126 | 1091 | if (bn_wexpand(rr,top) == NULL) goto err; |
a0a54079 MC |
1092 | rr->top=top; |
1093 | bn_mul_normal(rr->d,a->d,al,b->d,bl); | |
58964a49 | 1094 | |
a0a54079 | 1095 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
dfeab068 | 1096 | end: |
a0a54079 | 1097 | #endif |
d870740c | 1098 | bn_correct_top(rr); |
a0a54079 | 1099 | if (r != rr) BN_copy(r,rr); |
775c63fc | 1100 | ret=1; |
9b141126 | 1101 | err: |
d870740c | 1102 | bn_check_top(r); |
b6358c89 | 1103 | BN_CTX_end(ctx); |
775c63fc | 1104 | return(ret); |
dfeab068 | 1105 | } |
58964a49 | 1106 | |
6b691a5c | 1107 | void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) |
dfeab068 RE |
1108 | { |
1109 | BN_ULONG *rr; | |
58964a49 | 1110 | |
dfeab068 | 1111 | #ifdef BN_COUNT |
67d93e6f | 1112 | fprintf(stderr," bn_mul_normal %d * %d\n",na,nb); |
dfeab068 | 1113 | #endif |
58964a49 | 1114 | |
dfeab068 RE |
1115 | if (na < nb) |
1116 | { | |
1117 | int itmp; | |
1118 | BN_ULONG *ltmp; | |
58964a49 | 1119 | |
dfeab068 RE |
1120 | itmp=na; na=nb; nb=itmp; |
1121 | ltmp=a; a=b; b=ltmp; | |
58964a49 | 1122 | |
dfeab068 RE |
1123 | } |
1124 | rr= &(r[na]); | |
53b407da RL |
1125 | if (nb <= 0) |
1126 | { | |
1127 | (void)bn_mul_words(r,a,na,0); | |
1128 | return; | |
1129 | } | |
1130 | else | |
1131 | rr[0]=bn_mul_words(r,a,na,b[0]); | |
58964a49 | 1132 | |
dfeab068 RE |
1133 | for (;;) |
1134 | { | |
1135 | if (--nb <= 0) return; | |
1136 | rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]); | |
1137 | if (--nb <= 0) return; | |
1138 | rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]); | |
1139 | if (--nb <= 0) return; | |
1140 | rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]); | |
1141 | if (--nb <= 0) return; | |
1142 | rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]); | |
1143 | rr+=4; | |
1144 | r+=4; | |
1145 | b+=4; | |
1146 | } | |
58964a49 | 1147 | } |
dfeab068 | 1148 | |
6b691a5c | 1149 | void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) |
dfeab068 RE |
1150 | { |
1151 | #ifdef BN_COUNT | |
67d93e6f | 1152 | fprintf(stderr," bn_mul_low_normal %d * %d\n",n,n); |
58964a49 | 1153 | #endif |
dfeab068 RE |
1154 | bn_mul_words(r,a,n,b[0]); |
1155 | ||
1156 | for (;;) | |
1157 | { | |
1158 | if (--n <= 0) return; | |
1159 | bn_mul_add_words(&(r[1]),a,n,b[1]); | |
1160 | if (--n <= 0) return; | |
1161 | bn_mul_add_words(&(r[2]),a,n,b[2]); | |
1162 | if (--n <= 0) return; | |
1163 | bn_mul_add_words(&(r[3]),a,n,b[3]); | |
1164 | if (--n <= 0) return; | |
1165 | bn_mul_add_words(&(r[4]),a,n,b[4]); | |
1166 | r+=4; | |
1167 | b+=4; | |
1168 | } | |
1169 | } |