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