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