summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/old/bn_ka.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/old/bn_ka.c')
-rw-r--r--src/lib/libcrypto/bn/old/bn_ka.c567
1 files changed, 0 insertions, 567 deletions
diff --git a/src/lib/libcrypto/bn/old/bn_ka.c b/src/lib/libcrypto/bn/old/bn_ka.c
index 378c94dc5a..e69de29bb2 100644
--- a/src/lib/libcrypto/bn/old/bn_ka.c
+++ b/src/lib/libcrypto/bn/old/bn_ka.c
@@ -1,567 +0,0 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <strings.h>
4#include "bn_lcl.h"
5
6/* r is 2*n2 words in size,
7 * a and b are both n2 words in size.
8 * n2 must be a power of 2.
9 * We multiply and return the result.
10 * t must be 2*n2 words in size
11 * We calulate
12 * a[0]*b[0]
13 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
14 * a[1]*b[1]
15 */
16void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
17 BN_ULONG *t)
18 {
19 int n=n2/2;
20 int neg,zero,c1,c2;
21 BN_ULONG ln,lo,*p;
22
23#ifdef BN_COUNT
24printf(" bn_mul_recursive %d * %d\n",n2,n2);
25#endif
26 if (n2 <= 8)
27 {
28 if (n2 == 8)
29 bn_mul_comba8(r,a,b);
30 else
31 bn_mul_normal(r,a,n2,b,n2);
32 return;
33 }
34
35 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
36 {
37 /* This should not happen */
38 /*abort(); */
39 bn_mul_normal(r,a,n2,b,n2);
40 return;
41 }
42 /* r=(a[0]-a[1])*(b[1]-b[0]) */
43 c1=bn_cmp_words(a,&(a[n]),n);
44 c2=bn_cmp_words(&(b[n]),b,n);
45 zero=neg=0;
46 switch (c1*3+c2)
47 {
48 case -4:
49 bn_sub_words(t, &(a[n]),a, n); /* - */
50 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
51 break;
52 case -3:
53 zero=1;
54 break;
55 case -2:
56 bn_sub_words(t, &(a[n]),a, n); /* - */
57 bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
58 neg=1;
59 break;
60 case -1:
61 case 0:
62 case 1:
63 zero=1;
64 break;
65 case 2:
66 bn_sub_words(t, a, &(a[n]),n); /* + */
67 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
68 neg=1;
69 break;
70 case 3:
71 zero=1;
72 break;
73 case 4:
74 bn_sub_words(t, a, &(a[n]),n);
75 bn_sub_words(&(t[n]),&(b[n]),b, n);
76 break;
77 }
78
79 if (n == 8)
80 {
81 if (!zero)
82 bn_mul_comba8(&(t[n2]),t,&(t[n]));
83 else
84 memset(&(t[n2]),0,8*sizeof(BN_ULONG));
85
86 bn_mul_comba8(r,a,b);
87 bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
88 }
89 else
90 {
91 p= &(t[n2*2]);
92 if (!zero)
93 bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
94 else
95 memset(&(t[n2]),0,n*sizeof(BN_ULONG));
96 bn_mul_recursive(r,a,b,n,p);
97 bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p);
98 }
99
100 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
101 * r[10] holds (a[0]*b[0])
102 * r[32] holds (b[1]*b[1])
103 */
104
105 c1=bn_add_words(t,r,&(r[n2]),n2);
106
107 if (neg) /* if t[32] is negative */
108 {
109 c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
110 }
111 else
112 {
113 /* Might have a carry */
114 c1+=bn_add_words(&(t[n2]),&(t[n2]),t,n2);
115 }
116
117 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
118 * r[10] holds (a[0]*b[0])
119 * r[32] holds (b[1]*b[1])
120 * c1 holds the carry bits
121 */
122 c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
123 if (c1)
124 {
125 p= &(r[n+n2]);
126 lo= *p;
127 ln=(lo+c1)&BN_MASK2;
128 *p=ln;
129
130 /* The overflow will stop before we over write
131 * words we should not overwrite */
132 if (ln < c1)
133 {
134 do {
135 p++;
136 lo= *p;
137 ln=(lo+1)&BN_MASK2;
138 *p=ln;
139 } while (ln == 0);
140 }
141 }
142 }
143
144/* n+tn is the word length
145 * t needs to be n*4 is size, as does r */
146void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
147 int n, BN_ULONG *t)
148 {
149 int n2=n*2,i,j;
150 int c1;
151 BN_ULONG ln,lo,*p;
152
153#ifdef BN_COUNT
154printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
155#endif
156 if (n < 8)
157 {
158 i=tn+n;
159 bn_mul_normal(r,a,i,b,i);
160 return;
161 }
162
163 /* r=(a[0]-a[1])*(b[1]-b[0]) */
164 bn_sub_words(t, a, &(a[n]),n); /* + */
165 bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
166
167 if (n == 8)
168 {
169 bn_mul_comba8(&(t[n2]),t,&(t[n]));
170 bn_mul_comba8(r,a,b);
171 bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
172 memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
173 }
174 else
175 {
176 p= &(t[n2*2]);
177 bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
178 bn_mul_recursive(r,a,b,n,p);
179 i=n/2;
180 /* If there is only a bottom half to the number,
181 * just do it */
182 j=tn-i;
183 if (j == 0)
184 {
185 bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p);
186 memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2));
187 }
188 else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
189 {
190 bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]),
191 j,i,p);
192 memset(&(r[n2+tn*2]),0,
193 sizeof(BN_ULONG)*(n2-tn*2));
194 }
195 else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
196 {
197 memset(&(r[n2]),0,sizeof(BN_ULONG)*(tn*2));
198 for (;;)
199 {
200 i/=2;
201 if (i < tn)
202 {
203 bn_mul_part_recursive(&(r[n2]),
204 &(a[n]),&(b[n]),
205 tn-i,i,p);
206 break;
207 }
208 else if (i == tn)
209 {
210 bn_mul_recursive(&(r[n2]),
211 &(a[n]),&(b[n]),
212 i,p);
213 break;
214 }
215 }
216 }
217 }
218
219 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
220 * r[10] holds (a[0]*b[0])
221 * r[32] holds (b[1]*b[1])
222 */
223
224 c1=bn_add_words(t,r,&(r[n2]),n2);
225 c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
226
227 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
228 * r[10] holds (a[0]*b[0])
229 * r[32] holds (b[1]*b[1])
230 * c1 holds the carry bits
231 */
232 c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
233 if (c1)
234 {
235 p= &(r[n+n2]);
236 lo= *p;
237 ln=(lo+c1)&BN_MASK2;
238 *p=ln;
239
240 /* The overflow will stop before we over write
241 * words we should not overwrite */
242 if (ln < c1)
243 {
244 do {
245 p++;
246 lo= *p;
247 ln=(lo+1)&BN_MASK2;
248 *p=ln;
249 } while (ln == 0);
250 }
251 }
252 }
253
254/* r is 2*n words in size,
255 * a and b are both n words in size.
256 * n must be a power of 2.
257 * We multiply and return the result.
258 * t must be 2*n words in size
259 * We calulate
260 * a[0]*b[0]
261 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
262 * a[1]*b[1]
263 */
264void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *t)
265 {
266 int n=n2/2;
267 int zero,c1;
268 BN_ULONG ln,lo,*p;
269
270#ifdef BN_COUNT
271printf(" bn_sqr_recursive %d * %d\n",n2,n2);
272#endif
273 if (n2 == 4)
274 {
275 bn_sqr_comba4(r,a);
276 return;
277 }
278 else if (n2 == 8)
279 {
280 bn_sqr_comba8(r,a);
281 return;
282 }
283 if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL)
284 {
285 bn_sqr_normal(r,a,n2,t);
286 return;
287 abort();
288 }
289 /* r=(a[0]-a[1])*(a[1]-a[0]) */
290 c1=bn_cmp_words(a,&(a[n]),n);
291 zero=0;
292 if (c1 > 0)
293 bn_sub_words(t,a,&(a[n]),n);
294 else if (c1 < 0)
295 bn_sub_words(t,&(a[n]),a,n);
296 else
297 zero=1;
298
299 /* The result will always be negative unless it is zero */
300
301 if (n == 8)
302 {
303 if (!zero)
304 bn_sqr_comba8(&(t[n2]),t);
305 else
306 memset(&(t[n2]),0,8*sizeof(BN_ULONG));
307
308 bn_sqr_comba8(r,a);
309 bn_sqr_comba8(&(r[n2]),&(a[n]));
310 }
311 else
312 {
313 p= &(t[n2*2]);
314 if (!zero)
315 bn_sqr_recursive(&(t[n2]),t,n,p);
316 else
317 memset(&(t[n2]),0,n*sizeof(BN_ULONG));
318 bn_sqr_recursive(r,a,n,p);
319 bn_sqr_recursive(&(r[n2]),&(a[n]),n,p);
320 }
321
322 /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
323 * r[10] holds (a[0]*b[0])
324 * r[32] holds (b[1]*b[1])
325 */
326
327 c1=bn_add_words(t,r,&(r[n2]),n2);
328
329 /* t[32] is negative */
330 c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
331
332 /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
333 * r[10] holds (a[0]*a[0])
334 * r[32] holds (a[1]*a[1])
335 * c1 holds the carry bits
336 */
337 c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
338 if (c1)
339 {
340 p= &(r[n+n2]);
341 lo= *p;
342 ln=(lo+c1)&BN_MASK2;
343 *p=ln;
344
345 /* The overflow will stop before we over write
346 * words we should not overwrite */
347 if (ln < c1)
348 {
349 do {
350 p++;
351 lo= *p;
352 ln=(lo+1)&BN_MASK2;
353 *p=ln;
354 } while (ln == 0);
355 }
356 }
357 }
358
359#if 1
360/* a and b must be the same size, which is n2.
361 * r needs to be n2 words and t needs to be n2*2
362 */
363void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
364 BN_ULONG *t)
365 {
366 int n=n2/2;
367
368#ifdef BN_COUNT
369printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
370#endif
371
372 bn_mul_recursive(r,a,b,n,&(t[0]));
373 if (n > BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
374 {
375 bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2]));
376 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
377 bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2]));
378 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
379 }
380 else
381 {
382 bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n);
383 bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n);
384 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
385 bn_add_words(&(r[n]),&(r[n]),&(t[n]),n);
386 }
387 }
388
389/* a and b must be the same size, which is n2.
390 * r needs to be n2 words and t needs to be n2*2
391 * l is the low words of the output.
392 * t needs to be n2*3
393 */
394void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
395 BN_ULONG *t)
396 {
397 int j,i,n,c1,c2;
398 int neg,oneg,zero;
399 BN_ULONG ll,lc,*lp,*mp;
400
401#ifdef BN_COUNT
402printf(" bn_mul_high %d * %d\n",n2,n2);
403#endif
404 n=(n2+1)/2;
405
406 /* Calculate (al-ah)*(bh-bl) */
407 neg=zero=0;
408 c1=bn_cmp_words(&(a[0]),&(a[n]),n);
409 c2=bn_cmp_words(&(b[n]),&(b[0]),n);
410 switch (c1*3+c2)
411 {
412 case -4:
413 bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
414 bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
415 break;
416 case -3:
417 zero=1;
418 break;
419 case -2:
420 bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
421 bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
422 neg=1;
423 break;
424 case -1:
425 case 0:
426 case 1:
427 zero=1;
428 break;
429 case 2:
430 bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
431 bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
432 neg=1;
433 break;
434 case 3:
435 zero=1;
436 break;
437 case 4:
438 bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
439 bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
440 break;
441 }
442
443 oneg=neg;
444 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
445 bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
446 /* r[10] = (a[1]*b[1]) */
447 bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
448
449 /* s0 == low(al*bl)
450 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
451 * We know s0 and s1 so the only unknown is high(al*bl)
452 * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
453 * high(al*bl) == s1 - (r[0]+l[0]+t[0])
454 */
455 if (l != NULL)
456 {
457 lp= &(t[n2+n]);
458 c1=bn_add_words(lp,&(r[0]),&(l[0]),n);
459 }
460 else
461 {
462 c1=0;
463 lp= &(r[0]);
464 }
465
466 if (neg)
467 neg=bn_sub_words(&(t[n2]),lp,&(t[0]),n);
468 else
469 {
470 bn_add_words(&(t[n2]),lp,&(t[0]),n);
471 neg=0;
472 }
473
474 if (l != NULL)
475 {
476 bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n);
477 }
478 else
479 {
480 lp= &(t[n2+n]);
481 mp= &(t[n2]);
482 for (i=0; i<n; i++)
483 lp[i]=((~mp[i])+1)&BN_MASK2;
484 }
485
486 /* s[0] = low(al*bl)
487 * t[3] = high(al*bl)
488 * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
489 * r[10] = (a[1]*b[1])
490 */
491 /* R[10] = al*bl
492 * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
493 * R[32] = ah*bh
494 */
495 /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
496 * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
497 * R[3]=r[1]+(carry/borrow)
498 */
499 if (l != NULL)
500 {
501 lp= &(t[n2]);
502 c1= bn_add_words(lp,&(t[n2+n]),&(l[0]),n);
503 }
504 else
505 {
506 lp= &(t[n2+n]);
507 c1=0;
508 }
509 c1+=bn_add_words(&(t[n2]),lp, &(r[0]),n);
510 if (oneg)
511 c1-=bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n);
512 else
513 c1+=bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n);
514
515 c2 =bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n);
516 c2+=bn_add_words(&(r[0]),&(r[0]),&(r[n]),n);
517 if (oneg)
518 c2-=bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n);
519 else
520 c2+=bn_add_words(&(r[0]),&(r[0]),&(t[n]),n);
521
522 if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
523 {
524 i=0;
525 if (c1 > 0)
526 {
527 lc=c1;
528 do {
529 ll=(r[i]+lc)&BN_MASK2;
530 r[i++]=ll;
531 lc=(lc > ll);
532 } while (lc);
533 }
534 else
535 {
536 lc= -c1;
537 do {
538 ll=r[i];
539 r[i++]=(ll-lc)&BN_MASK2;
540 lc=(lc > ll);
541 } while (lc);
542 }
543 }
544 if (c2 != 0) /* Add starting at r[1] */
545 {
546 i=n;
547 if (c2 > 0)
548 {
549 lc=c2;
550 do {
551 ll=(r[i]+lc)&BN_MASK2;
552 r[i++]=ll;
553 lc=(lc > ll);
554 } while (lc);
555 }
556 else
557 {
558 lc= -c2;
559 do {
560 ll=r[i];
561 r[i++]=(ll-lc)&BN_MASK2;
562 lc=(lc > ll);
563 } while (lc);
564 }
565 }
566 }
567#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-04 22:30:04 +0000