summaryrefslogtreecommitdiff
path: root/src/lib
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/libcrypto/bn/bn_mul.c688
1 files changed, 344 insertions, 344 deletions
diff --git a/src/lib/libcrypto/bn/bn_mul.c b/src/lib/libcrypto/bn/bn_mul.c
index f6e6e9bf65..5437e7e883 100644
--- a/src/lib/libcrypto/bn/bn_mul.c
+++ b/src/lib/libcrypto/bn/bn_mul.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_mul.c,v 1.25 2023/01/16 16:53:19 jsing Exp $ */ 1/* $OpenBSD: bn_mul.c,v 1.26 2023/01/20 10:00:51 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -64,7 +64,6 @@
64 64
65#include "bn_local.h" 65#include "bn_local.h"
66 66
67#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
68/* Here follows specialised variants of bn_add_words() and 67/* Here follows specialised variants of bn_add_words() and
69 bn_sub_words(). They have the property performing operations on 68 bn_sub_words(). They have the property performing operations on
70 arrays of different sizes. The sizes of those arrays is expressed through 69 arrays of different sizes. The sizes of those arrays is expressed through
@@ -76,13 +75,13 @@
76 assembler counterparts for the systems that use assembler files. */ 75 assembler counterparts for the systems that use assembler files. */
77 76
78BN_ULONG 77BN_ULONG
79bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, 78bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl,
80 int dl) 79 int dl)
81{ 80{
82 BN_ULONG c, t; 81 BN_ULONG c, l, t;
83 82
84 assert(cl >= 0); 83 assert(cl >= 0);
85 c = bn_sub_words(r, a, b, cl); 84 c = bn_add_words(r, a, b, cl);
86 85
87 if (dl == 0) 86 if (dl == 0)
88 return c; 87 return c;
@@ -92,66 +91,99 @@ bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl,
92 b += cl; 91 b += cl;
93 92
94 if (dl < 0) { 93 if (dl < 0) {
95 for (;;) { 94 int save_dl = dl;
96 t = b[0]; 95 while (c) {
97 r[0] = (0 - t - c) & BN_MASK2; 96 l = (c + b[0]) & BN_MASK2;
98 if (t != 0) 97 c = (l < c);
99 c = 1; 98 r[0] = l;
100 if (++dl >= 0) 99 if (++dl >= 0)
101 break; 100 break;
102 101
103 t = b[1]; 102 l = (c + b[1]) & BN_MASK2;
104 r[1] = (0 - t - c) & BN_MASK2; 103 c = (l < c);
105 if (t != 0) 104 r[1] = l;
106 c = 1;
107 if (++dl >= 0) 105 if (++dl >= 0)
108 break; 106 break;
109 107
110 t = b[2]; 108 l = (c + b[2]) & BN_MASK2;
111 r[2] = (0 - t - c) & BN_MASK2; 109 c = (l < c);
112 if (t != 0) 110 r[2] = l;
113 c = 1;
114 if (++dl >= 0) 111 if (++dl >= 0)
115 break; 112 break;
116 113
117 t = b[3]; 114 l = (c + b[3]) & BN_MASK2;
118 r[3] = (0 - t - c) & BN_MASK2; 115 c = (l < c);
119 if (t != 0) 116 r[3] = l;
120 c = 1;
121 if (++dl >= 0) 117 if (++dl >= 0)
122 break; 118 break;
123 119
120 save_dl = dl;
124 b += 4; 121 b += 4;
125 r += 4; 122 r += 4;
126 } 123 }
124 if (dl < 0) {
125 if (save_dl < dl) {
126 switch (dl - save_dl) {
127 case 1:
128 r[1] = b[1];
129 if (++dl >= 0)
130 break;
131 case 2:
132 r[2] = b[2];
133 if (++dl >= 0)
134 break;
135 case 3:
136 r[3] = b[3];
137 if (++dl >= 0)
138 break;
139 }
140 b += 4;
141 r += 4;
142 }
143 }
144 if (dl < 0) {
145 for (;;) {
146 r[0] = b[0];
147 if (++dl >= 0)
148 break;
149 r[1] = b[1];
150 if (++dl >= 0)
151 break;
152 r[2] = b[2];
153 if (++dl >= 0)
154 break;
155 r[3] = b[3];
156 if (++dl >= 0)
157 break;
158
159 b += 4;
160 r += 4;
161 }
162 }
127 } else { 163 } else {
128 int save_dl = dl; 164 int save_dl = dl;
129 while (c) { 165 while (c) {
130 t = a[0]; 166 t = (a[0] + c) & BN_MASK2;
131 r[0] = (t - c) & BN_MASK2; 167 c = (t < c);
132 if (t != 0) 168 r[0] = t;
133 c = 0;
134 if (--dl <= 0) 169 if (--dl <= 0)
135 break; 170 break;
136 171
137 t = a[1]; 172 t = (a[1] + c) & BN_MASK2;
138 r[1] = (t - c) & BN_MASK2; 173 c = (t < c);
139 if (t != 0) 174 r[1] = t;
140 c = 0;
141 if (--dl <= 0) 175 if (--dl <= 0)
142 break; 176 break;
143 177
144 t = a[2]; 178 t = (a[2] + c) & BN_MASK2;
145 r[2] = (t - c) & BN_MASK2; 179 c = (t < c);
146 if (t != 0) 180 r[2] = t;
147 c = 0;
148 if (--dl <= 0) 181 if (--dl <= 0)
149 break; 182 break;
150 183
151 t = a[3]; 184 t = (a[3] + c) & BN_MASK2;
152 r[3] = (t - c) & BN_MASK2; 185 c = (t < c);
153 if (t != 0) 186 r[3] = t;
154 c = 0;
155 if (--dl <= 0) 187 if (--dl <= 0)
156 break; 188 break;
157 189
@@ -201,16 +233,16 @@ bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl,
201 } 233 }
202 return c; 234 return c;
203} 235}
204#endif
205 236
237#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
206BN_ULONG 238BN_ULONG
207bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, 239bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl,
208 int dl) 240 int dl)
209{ 241{
210 BN_ULONG c, l, t; 242 BN_ULONG c, t;
211 243
212 assert(cl >= 0); 244 assert(cl >= 0);
213 c = bn_add_words(r, a, b, cl); 245 c = bn_sub_words(r, a, b, cl);
214 246
215 if (dl == 0) 247 if (dl == 0)
216 return c; 248 return c;
@@ -220,99 +252,66 @@ bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl,
220 b += cl; 252 b += cl;
221 253
222 if (dl < 0) { 254 if (dl < 0) {
223 int save_dl = dl; 255 for (;;) {
224 while (c) { 256 t = b[0];
225 l = (c + b[0]) & BN_MASK2; 257 r[0] = (0 - t - c) & BN_MASK2;
226 c = (l < c); 258 if (t != 0)
227 r[0] = l; 259 c = 1;
228 if (++dl >= 0) 260 if (++dl >= 0)
229 break; 261 break;
230 262
231 l = (c + b[1]) & BN_MASK2; 263 t = b[1];
232 c = (l < c); 264 r[1] = (0 - t - c) & BN_MASK2;
233 r[1] = l; 265 if (t != 0)
266 c = 1;
234 if (++dl >= 0) 267 if (++dl >= 0)
235 break; 268 break;
236 269
237 l = (c + b[2]) & BN_MASK2; 270 t = b[2];
238 c = (l < c); 271 r[2] = (0 - t - c) & BN_MASK2;
239 r[2] = l; 272 if (t != 0)
273 c = 1;
240 if (++dl >= 0) 274 if (++dl >= 0)
241 break; 275 break;
242 276
243 l = (c + b[3]) & BN_MASK2; 277 t = b[3];
244 c = (l < c); 278 r[3] = (0 - t - c) & BN_MASK2;
245 r[3] = l; 279 if (t != 0)
280 c = 1;
246 if (++dl >= 0) 281 if (++dl >= 0)
247 break; 282 break;
248 283
249 save_dl = dl;
250 b += 4; 284 b += 4;
251 r += 4; 285 r += 4;
252 } 286 }
253 if (dl < 0) {
254 if (save_dl < dl) {
255 switch (dl - save_dl) {
256 case 1:
257 r[1] = b[1];
258 if (++dl >= 0)
259 break;
260 case 2:
261 r[2] = b[2];
262 if (++dl >= 0)
263 break;
264 case 3:
265 r[3] = b[3];
266 if (++dl >= 0)
267 break;
268 }
269 b += 4;
270 r += 4;
271 }
272 }
273 if (dl < 0) {
274 for (;;) {
275 r[0] = b[0];
276 if (++dl >= 0)
277 break;
278 r[1] = b[1];
279 if (++dl >= 0)
280 break;
281 r[2] = b[2];
282 if (++dl >= 0)
283 break;
284 r[3] = b[3];
285 if (++dl >= 0)
286 break;
287
288 b += 4;
289 r += 4;
290 }
291 }
292 } else { 287 } else {
293 int save_dl = dl; 288 int save_dl = dl;
294 while (c) { 289 while (c) {
295 t = (a[0] + c) & BN_MASK2; 290 t = a[0];
296 c = (t < c); 291 r[0] = (t - c) & BN_MASK2;
297 r[0] = t; 292 if (t != 0)
293 c = 0;
298 if (--dl <= 0) 294 if (--dl <= 0)
299 break; 295 break;
300 296
301 t = (a[1] + c) & BN_MASK2; 297 t = a[1];
302 c = (t < c); 298 r[1] = (t - c) & BN_MASK2;
303 r[1] = t; 299 if (t != 0)
300 c = 0;
304 if (--dl <= 0) 301 if (--dl <= 0)
305 break; 302 break;
306 303
307 t = (a[2] + c) & BN_MASK2; 304 t = a[2];
308 c = (t < c); 305 r[2] = (t - c) & BN_MASK2;
309 r[2] = t; 306 if (t != 0)
307 c = 0;
310 if (--dl <= 0) 308 if (--dl <= 0)
311 break; 309 break;
312 310
313 t = (a[3] + c) & BN_MASK2; 311 t = a[3];
314 c = (t < c); 312 r[3] = (t - c) & BN_MASK2;
315 r[3] = t; 313 if (t != 0)
314 c = 0;
316 if (--dl <= 0) 315 if (--dl <= 0)
317 break; 316 break;
318 317
@@ -362,8 +361,245 @@ bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl,
362 } 361 }
363 return c; 362 return c;
364} 363}
364#endif
365
366void
367bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
368{
369 BN_ULONG *rr;
370
371
372 if (na < nb) {
373 int itmp;
374 BN_ULONG *ltmp;
375
376 itmp = na;
377 na = nb;
378 nb = itmp;
379 ltmp = a;
380 a = b;
381 b = ltmp;
382
383 }
384 rr = &(r[na]);
385 if (nb <= 0) {
386 (void)bn_mul_words(r, a, na, 0);
387 return;
388 } else
389 rr[0] = bn_mul_words(r, a, na, b[0]);
390
391 for (;;) {
392 if (--nb <= 0)
393 return;
394 rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
395 if (--nb <= 0)
396 return;
397 rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
398 if (--nb <= 0)
399 return;
400 rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
401 if (--nb <= 0)
402 return;
403 rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
404 rr += 4;
405 r += 4;
406 b += 4;
407 }
408}
409
410void
411bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
412{
413 bn_mul_words(r, a, n, b[0]);
414
415 for (;;) {
416 if (--n <= 0)
417 return;
418 bn_mul_add_words(&(r[1]), a, n, b[1]);
419 if (--n <= 0)
420 return;
421 bn_mul_add_words(&(r[2]), a, n, b[2]);
422 if (--n <= 0)
423 return;
424 bn_mul_add_words(&(r[3]), a, n, b[3]);
425 if (--n <= 0)
426 return;
427 bn_mul_add_words(&(r[4]), a, n, b[4]);
428 r += 4;
429 b += 4;
430 }
431}
365 432
366#ifdef BN_RECURSION 433#ifdef BN_RECURSION
434/* a and b must be the same size, which is n2.
435 * r needs to be n2 words and t needs to be n2*2
436 * l is the low words of the output.
437 * t needs to be n2*3
438 */
439void
440bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
441 BN_ULONG *t)
442{
443 int i, n;
444 int c1, c2;
445 int neg, oneg, zero;
446 BN_ULONG ll, lc, *lp, *mp;
447
448 n = n2 / 2;
449
450 /* Calculate (al-ah)*(bh-bl) */
451 neg = zero = 0;
452 c1 = bn_cmp_words(&(a[0]), &(a[n]), n);
453 c2 = bn_cmp_words(&(b[n]), &(b[0]), n);
454 switch (c1 * 3 + c2) {
455 case -4:
456 bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
457 bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
458 break;
459 case -3:
460 zero = 1;
461 break;
462 case -2:
463 bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
464 bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
465 neg = 1;
466 break;
467 case -1:
468 case 0:
469 case 1:
470 zero = 1;
471 break;
472 case 2:
473 bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
474 bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
475 neg = 1;
476 break;
477 case 3:
478 zero = 1;
479 break;
480 case 4:
481 bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
482 bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
483 break;
484 }
485
486 oneg = neg;
487 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
488 /* r[10] = (a[1]*b[1]) */
489# ifdef BN_MUL_COMBA
490 if (n == 8) {
491 bn_mul_comba8(&(t[0]), &(r[0]), &(r[n]));
492 bn_mul_comba8(r, &(a[n]), &(b[n]));
493 } else
494# endif
495 {
496 bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2]));
497 bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2]));
498 }
499
500 /* s0 == low(al*bl)
501 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
502 * We know s0 and s1 so the only unknown is high(al*bl)
503 * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
504 * high(al*bl) == s1 - (r[0]+l[0]+t[0])
505 */
506 if (l != NULL) {
507 lp = &(t[n2 + n]);
508 c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n));
509 } else {
510 c1 = 0;
511 lp = &(r[0]);
512 }
513
514 if (neg)
515 neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n));
516 else {
517 bn_add_words(&(t[n2]), lp, &(t[0]), n);
518 neg = 0;
519 }
520
521 if (l != NULL) {
522 bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n);
523 } else {
524 lp = &(t[n2 + n]);
525 mp = &(t[n2]);
526 for (i = 0; i < n; i++)
527 lp[i] = ((~mp[i]) + 1) & BN_MASK2;
528 }
529
530 /* s[0] = low(al*bl)
531 * t[3] = high(al*bl)
532 * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
533 * r[10] = (a[1]*b[1])
534 */
535 /* R[10] = al*bl
536 * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
537 * R[32] = ah*bh
538 */
539 /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
540 * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
541 * R[3]=r[1]+(carry/borrow)
542 */
543 if (l != NULL) {
544 lp = &(t[n2]);
545 c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n));
546 } else {
547 lp = &(t[n2 + n]);
548 c1 = 0;
549 }
550 c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n));
551 if (oneg)
552 c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n));
553 else
554 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n));
555
556 c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n));
557 c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n));
558 if (oneg)
559 c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n));
560 else
561 c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n));
562
563 if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
564 {
565 i = 0;
566 if (c1 > 0) {
567 lc = c1;
568 do {
569 ll = (r[i] + lc) & BN_MASK2;
570 r[i++] = ll;
571 lc = (lc > ll);
572 } while (lc);
573 } else {
574 lc = -c1;
575 do {
576 ll = r[i];
577 r[i++] = (ll - lc) & BN_MASK2;
578 lc = (lc > ll);
579 } while (lc);
580 }
581 }
582 if (c2 != 0) /* Add starting at r[1] */
583 {
584 i = n;
585 if (c2 > 0) {
586 lc = c2;
587 do {
588 ll = (r[i] + lc) & BN_MASK2;
589 r[i++] = ll;
590 lc = (lc > ll);
591 } while (lc);
592 } else {
593 lc = -c2;
594 do {
595 ll = r[i];
596 r[i++] = (ll - lc) & BN_MASK2;
597 lc = (lc > ll);
598 } while (lc);
599 }
600 }
601}
602
367/* Karatsuba recursive multiplication algorithm 603/* Karatsuba recursive multiplication algorithm
368 * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ 604 * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
369 605
@@ -699,175 +935,6 @@ bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *t)
699 bn_add_words(&(r[n]), &(r[n]), &(t[n]), n); 935 bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
700 } 936 }
701} 937}
702
703/* a and b must be the same size, which is n2.
704 * r needs to be n2 words and t needs to be n2*2
705 * l is the low words of the output.
706 * t needs to be n2*3
707 */
708void
709bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
710 BN_ULONG *t)
711{
712 int i, n;
713 int c1, c2;
714 int neg, oneg, zero;
715 BN_ULONG ll, lc, *lp, *mp;
716
717 n = n2 / 2;
718
719 /* Calculate (al-ah)*(bh-bl) */
720 neg = zero = 0;
721 c1 = bn_cmp_words(&(a[0]), &(a[n]), n);
722 c2 = bn_cmp_words(&(b[n]), &(b[0]), n);
723 switch (c1 * 3 + c2) {
724 case -4:
725 bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
726 bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
727 break;
728 case -3:
729 zero = 1;
730 break;
731 case -2:
732 bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
733 bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
734 neg = 1;
735 break;
736 case -1:
737 case 0:
738 case 1:
739 zero = 1;
740 break;
741 case 2:
742 bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
743 bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
744 neg = 1;
745 break;
746 case 3:
747 zero = 1;
748 break;
749 case 4:
750 bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
751 bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
752 break;
753 }
754
755 oneg = neg;
756 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
757 /* r[10] = (a[1]*b[1]) */
758# ifdef BN_MUL_COMBA
759 if (n == 8) {
760 bn_mul_comba8(&(t[0]), &(r[0]), &(r[n]));
761 bn_mul_comba8(r, &(a[n]), &(b[n]));
762 } else
763# endif
764 {
765 bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2]));
766 bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2]));
767 }
768
769 /* s0 == low(al*bl)
770 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
771 * We know s0 and s1 so the only unknown is high(al*bl)
772 * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
773 * high(al*bl) == s1 - (r[0]+l[0]+t[0])
774 */
775 if (l != NULL) {
776 lp = &(t[n2 + n]);
777 c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n));
778 } else {
779 c1 = 0;
780 lp = &(r[0]);
781 }
782
783 if (neg)
784 neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n));
785 else {
786 bn_add_words(&(t[n2]), lp, &(t[0]), n);
787 neg = 0;
788 }
789
790 if (l != NULL) {
791 bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n);
792 } else {
793 lp = &(t[n2 + n]);
794 mp = &(t[n2]);
795 for (i = 0; i < n; i++)
796 lp[i] = ((~mp[i]) + 1) & BN_MASK2;
797 }
798
799 /* s[0] = low(al*bl)
800 * t[3] = high(al*bl)
801 * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
802 * r[10] = (a[1]*b[1])
803 */
804 /* R[10] = al*bl
805 * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
806 * R[32] = ah*bh
807 */
808 /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
809 * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
810 * R[3]=r[1]+(carry/borrow)
811 */
812 if (l != NULL) {
813 lp = &(t[n2]);
814 c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n));
815 } else {
816 lp = &(t[n2 + n]);
817 c1 = 0;
818 }
819 c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n));
820 if (oneg)
821 c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n));
822 else
823 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n));
824
825 c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n));
826 c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n));
827 if (oneg)
828 c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n));
829 else
830 c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n));
831
832 if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
833 {
834 i = 0;
835 if (c1 > 0) {
836 lc = c1;
837 do {
838 ll = (r[i] + lc) & BN_MASK2;
839 r[i++] = ll;
840 lc = (lc > ll);
841 } while (lc);
842 } else {
843 lc = -c1;
844 do {
845 ll = r[i];
846 r[i++] = (ll - lc) & BN_MASK2;
847 lc = (lc > ll);
848 } while (lc);
849 }
850 }
851 if (c2 != 0) /* Add starting at r[1] */
852 {
853 i = n;
854 if (c2 > 0) {
855 lc = c2;
856 do {
857 ll = (r[i] + lc) & BN_MASK2;
858 r[i++] = ll;
859 lc = (lc > ll);
860 } while (lc);
861 } else {
862 lc = -c2;
863 do {
864 ll = r[i];
865 r[i++] = (ll - lc) & BN_MASK2;
866 lc = (lc > ll);
867 } while (lc);
868 }
869 }
870}
871#endif /* BN_RECURSION */ 938#endif /* BN_RECURSION */
872 939
873int 940int
@@ -1023,70 +1090,3 @@ err:
1023 BN_CTX_end(ctx); 1090 BN_CTX_end(ctx);
1024 return (ret); 1091 return (ret);
1025} 1092}
1026
1027void
1028bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
1029{
1030 BN_ULONG *rr;
1031
1032
1033 if (na < nb) {
1034 int itmp;
1035 BN_ULONG *ltmp;
1036
1037 itmp = na;
1038 na = nb;
1039 nb = itmp;
1040 ltmp = a;
1041 a = b;
1042 b = ltmp;
1043
1044 }
1045 rr = &(r[na]);
1046 if (nb <= 0) {
1047 (void)bn_mul_words(r, a, na, 0);
1048 return;
1049 } else
1050 rr[0] = bn_mul_words(r, a, na, b[0]);
1051
1052 for (;;) {
1053 if (--nb <= 0)
1054 return;
1055 rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
1056 if (--nb <= 0)
1057 return;
1058 rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
1059 if (--nb <= 0)
1060 return;
1061 rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
1062 if (--nb <= 0)
1063 return;
1064 rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
1065 rr += 4;
1066 r += 4;
1067 b += 4;
1068 }
1069}
1070
1071void
1072bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
1073{
1074 bn_mul_words(r, a, n, b[0]);
1075
1076 for (;;) {
1077 if (--n <= 0)
1078 return;
1079 bn_mul_add_words(&(r[1]), a, n, b[1]);
1080 if (--n <= 0)
1081 return;
1082 bn_mul_add_words(&(r[2]), a, n, b[2]);
1083 if (--n <= 0)
1084 return;
1085 bn_mul_add_words(&(r[3]), a, n, b[3]);
1086 if (--n <= 0)
1087 return;
1088 bn_mul_add_words(&(r[4]), a, n, b[4]);
1089 r += 4;
1090 b += 4;
1091 }
1092}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-22 20:19:26 +0000