]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
1212818e | 2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. |
0f113f3e | 3 | * |
367ace68 | 4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
4f22f405 RS |
5 | * this file except in compliance with the License. You can obtain a copy |
6 | * in the file LICENSE in the source distribution or at | |
7 | * https://www.openssl.org/source/license.html | |
d02b48c6 RE |
8 | */ |
9 | ||
baa257f1 | 10 | #include <assert.h> |
b39fc560 | 11 | #include "internal/cryptlib.h" |
706457b7 | 12 | #include "bn_local.h" |
d02b48c6 | 13 | |
699543e4 | 14 | #if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) |
0f113f3e MC |
15 | /* |
16 | * Here follows specialised variants of bn_add_words() and bn_sub_words(). | |
17 | * They have the property performing operations on arrays of different sizes. | |
18 | * The sizes of those arrays is expressed through cl, which is the common | |
0d4fb843 | 19 | * length ( basically, min(len(a),len(b)) ), and dl, which is the delta |
0f113f3e MC |
20 | * between the two lengths, calculated as len(a)-len(b). All lengths are the |
21 | * number of BN_ULONGs... For the operations that require a result array as | |
22 | * parameter, it must have the length cl+abs(dl). These functions should | |
23 | * probably end up in bn_asm.c as soon as there are assembler counterparts | |
24 | * for the systems that use assembler files. | |
25 | */ | |
baa257f1 | 26 | |
baa257f1 | 27 | BN_ULONG bn_sub_part_words(BN_ULONG *r, |
0f113f3e MC |
28 | const BN_ULONG *a, const BN_ULONG *b, |
29 | int cl, int dl) | |
30 | { | |
31 | BN_ULONG c, t; | |
32 | ||
33 | assert(cl >= 0); | |
34 | c = bn_sub_words(r, a, b, cl); | |
35 | ||
36 | if (dl == 0) | |
37 | return c; | |
38 | ||
39 | r += cl; | |
40 | a += cl; | |
41 | b += cl; | |
42 | ||
43 | if (dl < 0) { | |
44 | for (;;) { | |
45 | t = b[0]; | |
46 | r[0] = (0 - t - c) & BN_MASK2; | |
47 | if (t != 0) | |
48 | c = 1; | |
49 | if (++dl >= 0) | |
50 | break; | |
51 | ||
52 | t = b[1]; | |
53 | r[1] = (0 - t - c) & BN_MASK2; | |
54 | if (t != 0) | |
55 | c = 1; | |
56 | if (++dl >= 0) | |
57 | break; | |
58 | ||
59 | t = b[2]; | |
60 | r[2] = (0 - t - c) & BN_MASK2; | |
61 | if (t != 0) | |
62 | c = 1; | |
63 | if (++dl >= 0) | |
64 | break; | |
65 | ||
66 | t = b[3]; | |
67 | r[3] = (0 - t - c) & BN_MASK2; | |
68 | if (t != 0) | |
69 | c = 1; | |
70 | if (++dl >= 0) | |
71 | break; | |
72 | ||
73 | b += 4; | |
74 | r += 4; | |
75 | } | |
76 | } else { | |
77 | int save_dl = dl; | |
78 | while (c) { | |
79 | t = a[0]; | |
80 | r[0] = (t - c) & BN_MASK2; | |
81 | if (t != 0) | |
82 | c = 0; | |
83 | if (--dl <= 0) | |
84 | break; | |
85 | ||
86 | t = a[1]; | |
87 | r[1] = (t - c) & BN_MASK2; | |
88 | if (t != 0) | |
89 | c = 0; | |
90 | if (--dl <= 0) | |
91 | break; | |
92 | ||
93 | t = a[2]; | |
94 | r[2] = (t - c) & BN_MASK2; | |
95 | if (t != 0) | |
96 | c = 0; | |
97 | if (--dl <= 0) | |
98 | break; | |
99 | ||
100 | t = a[3]; | |
101 | r[3] = (t - c) & BN_MASK2; | |
102 | if (t != 0) | |
103 | c = 0; | |
104 | if (--dl <= 0) | |
105 | break; | |
106 | ||
107 | save_dl = dl; | |
108 | a += 4; | |
109 | r += 4; | |
110 | } | |
111 | if (dl > 0) { | |
112 | if (save_dl > dl) { | |
113 | switch (save_dl - dl) { | |
114 | case 1: | |
115 | r[1] = a[1]; | |
116 | if (--dl <= 0) | |
117 | break; | |
018fcbec | 118 | /* fall thru */ |
0f113f3e MC |
119 | case 2: |
120 | r[2] = a[2]; | |
121 | if (--dl <= 0) | |
122 | break; | |
018fcbec | 123 | /* fall thru */ |
0f113f3e MC |
124 | case 3: |
125 | r[3] = a[3]; | |
126 | if (--dl <= 0) | |
127 | break; | |
128 | } | |
129 | a += 4; | |
130 | r += 4; | |
131 | } | |
132 | } | |
133 | if (dl > 0) { | |
134 | for (;;) { | |
135 | r[0] = a[0]; | |
136 | if (--dl <= 0) | |
137 | break; | |
138 | r[1] = a[1]; | |
139 | if (--dl <= 0) | |
140 | break; | |
141 | r[2] = a[2]; | |
142 | if (--dl <= 0) | |
143 | break; | |
144 | r[3] = a[3]; | |
145 | if (--dl <= 0) | |
146 | break; | |
147 | ||
148 | a += 4; | |
149 | r += 4; | |
150 | } | |
151 | } | |
152 | } | |
153 | return c; | |
154 | } | |
240f5169 | 155 | #endif |
baa257f1 | 156 | |
dfeab068 | 157 | #ifdef BN_RECURSION |
0f113f3e MC |
158 | /* |
159 | * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of | |
160 | * Computer Programming, Vol. 2) | |
161 | */ | |
8782a426 | 162 | |
1d97c843 TH |
163 | /*- |
164 | * r is 2*n2 words in size, | |
dfeab068 RE |
165 | * a and b are both n2 words in size. |
166 | * n2 must be a power of 2. | |
167 | * We multiply and return the result. | |
168 | * t must be 2*n2 words in size | |
657e60fa | 169 | * We calculate |
dfeab068 RE |
170 | * a[0]*b[0] |
171 | * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) | |
172 | * a[1]*b[1] | |
173 | */ | |
70ba4ee5 | 174 | /* dnX may not be positive, but n2/2+dnX has to be */ |
6343829a | 175 | void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, |
0f113f3e MC |
176 | int dna, int dnb, BN_ULONG *t) |
177 | { | |
178 | int n = n2 / 2, c1, c2; | |
179 | int tna = n + dna, tnb = n + dnb; | |
180 | unsigned int neg, zero; | |
181 | BN_ULONG ln, lo, *p; | |
d02b48c6 | 182 | |
775c63fc UM |
183 | # ifdef BN_MUL_COMBA |
184 | # if 0 | |
0f113f3e MC |
185 | if (n2 == 4) { |
186 | bn_mul_comba4(r, a, b); | |
187 | return; | |
188 | } | |
775c63fc | 189 | # endif |
0f113f3e MC |
190 | /* |
191 | * Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete | |
192 | * [steve] | |
193 | */ | |
194 | if (n2 == 8 && dna == 0 && dnb == 0) { | |
195 | bn_mul_comba8(r, a, b); | |
196 | return; | |
197 | } | |
198 | # endif /* BN_MUL_COMBA */ | |
199 | /* Else do normal multiply */ | |
200 | if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { | |
201 | bn_mul_normal(r, a, n2 + dna, b, n2 + dnb); | |
202 | if ((dna + dnb) < 0) | |
203 | memset(&r[2 * n2 + dna + dnb], 0, | |
204 | sizeof(BN_ULONG) * -(dna + dnb)); | |
205 | return; | |
206 | } | |
207 | /* r=(a[0]-a[1])*(b[1]-b[0]) */ | |
208 | c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); | |
209 | c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); | |
210 | zero = neg = 0; | |
211 | switch (c1 * 3 + c2) { | |
212 | case -4: | |
213 | bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ | |
214 | bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ | |
215 | break; | |
216 | case -3: | |
217 | zero = 1; | |
218 | break; | |
219 | case -2: | |
220 | bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ | |
221 | bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ | |
222 | neg = 1; | |
223 | break; | |
224 | case -1: | |
225 | case 0: | |
226 | case 1: | |
227 | zero = 1; | |
228 | break; | |
229 | case 2: | |
230 | bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ | |
231 | bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ | |
232 | neg = 1; | |
233 | break; | |
234 | case 3: | |
235 | zero = 1; | |
236 | break; | |
237 | case 4: | |
238 | bn_sub_part_words(t, a, &(a[n]), tna, n - tna); | |
239 | bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); | |
240 | break; | |
241 | } | |
d02b48c6 | 242 | |
775c63fc | 243 | # ifdef BN_MUL_COMBA |
0f113f3e MC |
244 | if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take |
245 | * extra args to do this well */ | |
246 | if (!zero) | |
247 | bn_mul_comba4(&(t[n2]), t, &(t[n])); | |
248 | else | |
16f8d4eb | 249 | memset(&t[n2], 0, sizeof(*t) * 8); |
0f113f3e MC |
250 | |
251 | bn_mul_comba4(r, a, b); | |
252 | bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n])); | |
253 | } else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could | |
254 | * take extra args to do | |
255 | * this well */ | |
256 | if (!zero) | |
257 | bn_mul_comba8(&(t[n2]), t, &(t[n])); | |
258 | else | |
16f8d4eb | 259 | memset(&t[n2], 0, sizeof(*t) * 16); |
0f113f3e MC |
260 | |
261 | bn_mul_comba8(r, a, b); | |
262 | bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n])); | |
263 | } else | |
264 | # endif /* BN_MUL_COMBA */ | |
265 | { | |
266 | p = &(t[n2 * 2]); | |
267 | if (!zero) | |
268 | bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); | |
269 | else | |
16f8d4eb | 270 | memset(&t[n2], 0, sizeof(*t) * n2); |
0f113f3e MC |
271 | bn_mul_recursive(r, a, b, n, 0, 0, p); |
272 | bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p); | |
273 | } | |
274 | ||
50e735f9 MC |
275 | /*- |
276 | * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign | |
277 | * r[10] holds (a[0]*b[0]) | |
278 | * r[32] holds (b[1]*b[1]) | |
279 | */ | |
0f113f3e MC |
280 | |
281 | c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); | |
282 | ||
283 | if (neg) { /* if t[32] is negative */ | |
284 | c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); | |
285 | } else { | |
286 | /* Might have a carry */ | |
287 | c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); | |
288 | } | |
289 | ||
50e735f9 MC |
290 | /*- |
291 | * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) | |
292 | * r[10] holds (a[0]*b[0]) | |
293 | * r[32] holds (b[1]*b[1]) | |
294 | * c1 holds the carry bits | |
295 | */ | |
0f113f3e MC |
296 | c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); |
297 | if (c1) { | |
298 | p = &(r[n + n2]); | |
299 | lo = *p; | |
300 | ln = (lo + c1) & BN_MASK2; | |
301 | *p = ln; | |
302 | ||
303 | /* | |
304 | * The overflow will stop before we over write words we should not | |
305 | * overwrite | |
306 | */ | |
307 | if (ln < (BN_ULONG)c1) { | |
308 | do { | |
309 | p++; | |
310 | lo = *p; | |
311 | ln = (lo + 1) & BN_MASK2; | |
312 | *p = ln; | |
313 | } while (ln == 0); | |
314 | } | |
315 | } | |
316 | } | |
317 | ||
318 | /* | |
319 | * n+tn is the word length t needs to be n*4 is size, as does r | |
320 | */ | |
70ba4ee5 | 321 | /* tnX may not be negative but less than n */ |
6a2347ee | 322 | void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, |
0f113f3e MC |
323 | int tna, int tnb, BN_ULONG *t) |
324 | { | |
325 | int i, j, n2 = n * 2; | |
326 | int c1, c2, neg; | |
327 | BN_ULONG ln, lo, *p; | |
328 | ||
329 | if (n < 8) { | |
330 | bn_mul_normal(r, a, n + tna, b, n + tnb); | |
331 | return; | |
332 | } | |
333 | ||
334 | /* r=(a[0]-a[1])*(b[1]-b[0]) */ | |
335 | c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); | |
336 | c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); | |
337 | neg = 0; | |
338 | switch (c1 * 3 + c2) { | |
339 | case -4: | |
340 | bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ | |
341 | bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ | |
342 | break; | |
343 | case -3: | |
0f113f3e MC |
344 | case -2: |
345 | bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ | |
346 | bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ | |
347 | neg = 1; | |
348 | break; | |
349 | case -1: | |
350 | case 0: | |
351 | case 1: | |
0f113f3e MC |
352 | case 2: |
353 | bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ | |
354 | bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ | |
355 | neg = 1; | |
356 | break; | |
357 | case 3: | |
0f113f3e MC |
358 | case 4: |
359 | bn_sub_part_words(t, a, &(a[n]), tna, n - tna); | |
360 | bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); | |
361 | break; | |
362 | } | |
363 | /* | |
364 | * The zero case isn't yet implemented here. The speedup would probably | |
365 | * be negligible. | |
366 | */ | |
775c63fc | 367 | # if 0 |
0f113f3e MC |
368 | if (n == 4) { |
369 | bn_mul_comba4(&(t[n2]), t, &(t[n])); | |
370 | bn_mul_comba4(r, a, b); | |
371 | bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn); | |
16f8d4eb | 372 | memset(&r[n2 + tn * 2], 0, sizeof(*r) * (n2 - tn * 2)); |
0f113f3e | 373 | } else |
775c63fc | 374 | # endif |
0f113f3e MC |
375 | if (n == 8) { |
376 | bn_mul_comba8(&(t[n2]), t, &(t[n])); | |
377 | bn_mul_comba8(r, a, b); | |
378 | bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); | |
16f8d4eb | 379 | memset(&r[n2 + tna + tnb], 0, sizeof(*r) * (n2 - tna - tnb)); |
0f113f3e MC |
380 | } else { |
381 | p = &(t[n2 * 2]); | |
382 | bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); | |
383 | bn_mul_recursive(r, a, b, n, 0, 0, p); | |
384 | i = n / 2; | |
385 | /* | |
386 | * If there is only a bottom half to the number, just do it | |
387 | */ | |
388 | if (tna > tnb) | |
389 | j = tna - i; | |
390 | else | |
391 | j = tnb - i; | |
392 | if (j == 0) { | |
393 | bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), | |
394 | i, tna - i, tnb - i, p); | |
16f8d4eb | 395 | memset(&r[n2 + i * 2], 0, sizeof(*r) * (n2 - i * 2)); |
0f113f3e MC |
396 | } else if (j > 0) { /* eg, n == 16, i == 8 and tn == 11 */ |
397 | bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), | |
398 | i, tna - i, tnb - i, p); | |
399 | memset(&(r[n2 + tna + tnb]), 0, | |
400 | sizeof(BN_ULONG) * (n2 - tna - tnb)); | |
401 | } else { /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ | |
402 | ||
16f8d4eb | 403 | memset(&r[n2], 0, sizeof(*r) * n2); |
0f113f3e MC |
404 | if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL |
405 | && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { | |
406 | bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); | |
407 | } else { | |
408 | for (;;) { | |
409 | i /= 2; | |
410 | /* | |
411 | * these simplified conditions work exclusively because | |
412 | * difference between tna and tnb is 1 or 0 | |
413 | */ | |
414 | if (i < tna || i < tnb) { | |
415 | bn_mul_part_recursive(&(r[n2]), | |
416 | &(a[n]), &(b[n]), | |
417 | i, tna - i, tnb - i, p); | |
418 | break; | |
419 | } else if (i == tna || i == tnb) { | |
420 | bn_mul_recursive(&(r[n2]), | |
421 | &(a[n]), &(b[n]), | |
422 | i, tna - i, tnb - i, p); | |
423 | break; | |
424 | } | |
425 | } | |
426 | } | |
427 | } | |
428 | } | |
429 | ||
50e735f9 MC |
430 | /*- |
431 | * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign | |
432 | * r[10] holds (a[0]*b[0]) | |
433 | * r[32] holds (b[1]*b[1]) | |
434 | */ | |
0f113f3e MC |
435 | |
436 | c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); | |
437 | ||
438 | if (neg) { /* if t[32] is negative */ | |
439 | c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); | |
440 | } else { | |
441 | /* Might have a carry */ | |
442 | c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); | |
443 | } | |
444 | ||
50e735f9 MC |
445 | /*- |
446 | * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) | |
447 | * r[10] holds (a[0]*b[0]) | |
448 | * r[32] holds (b[1]*b[1]) | |
449 | * c1 holds the carry bits | |
450 | */ | |
0f113f3e MC |
451 | c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); |
452 | if (c1) { | |
453 | p = &(r[n + n2]); | |
454 | lo = *p; | |
455 | ln = (lo + c1) & BN_MASK2; | |
456 | *p = ln; | |
457 | ||
458 | /* | |
459 | * The overflow will stop before we over write words we should not | |
460 | * overwrite | |
461 | */ | |
462 | if (ln < (BN_ULONG)c1) { | |
463 | do { | |
464 | p++; | |
465 | lo = *p; | |
466 | ln = (lo + 1) & BN_MASK2; | |
467 | *p = ln; | |
468 | } while (ln == 0); | |
469 | } | |
470 | } | |
471 | } | |
58964a49 | 472 | |
1d97c843 TH |
473 | /*- |
474 | * a and b must be the same size, which is n2. | |
dfeab068 RE |
475 | * r needs to be n2 words and t needs to be n2*2 |
476 | */ | |
6b691a5c | 477 | void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, |
0f113f3e MC |
478 | BN_ULONG *t) |
479 | { | |
480 | int n = n2 / 2; | |
481 | ||
482 | bn_mul_recursive(r, a, b, n, 0, 0, &(t[0])); | |
483 | if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) { | |
484 | bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2])); | |
485 | bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); | |
486 | bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2])); | |
487 | bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); | |
488 | } else { | |
489 | bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n); | |
490 | bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n); | |
491 | bn_add_words(&(r[n]), &(r[n]), &(t[0]), n); | |
492 | bn_add_words(&(r[n]), &(r[n]), &(t[n]), n); | |
493 | } | |
494 | } | |
0f113f3e | 495 | #endif /* BN_RECURSION */ |
58964a49 | 496 | |
6a2347ee | 497 | int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) |
fcc4ee09 AP |
498 | { |
499 | int ret = bn_mul_fixed_top(r, a, b, ctx); | |
500 | ||
501 | bn_correct_top(r); | |
502 | bn_check_top(r); | |
503 | ||
504 | return ret; | |
505 | } | |
506 | ||
507 | int bn_mul_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | |
0f113f3e MC |
508 | { |
509 | int ret = 0; | |
510 | int top, al, bl; | |
511 | BIGNUM *rr; | |
775c63fc | 512 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
0f113f3e | 513 | int i; |
775c63fc | 514 | #endif |
a0a54079 | 515 | #ifdef BN_RECURSION |
0f113f3e MC |
516 | BIGNUM *t = NULL; |
517 | int j = 0, k; | |
a0a54079 | 518 | #endif |
dfeab068 | 519 | |
0f113f3e MC |
520 | bn_check_top(a); |
521 | bn_check_top(b); | |
522 | bn_check_top(r); | |
523 | ||
524 | al = a->top; | |
525 | bl = b->top; | |
526 | ||
527 | if ((al == 0) || (bl == 0)) { | |
528 | BN_zero(r); | |
208fb891 | 529 | return 1; |
0f113f3e MC |
530 | } |
531 | top = al + bl; | |
532 | ||
533 | BN_CTX_start(ctx); | |
534 | if ((r == a) || (r == b)) { | |
535 | if ((rr = BN_CTX_get(ctx)) == NULL) | |
536 | goto err; | |
537 | } else | |
538 | rr = r; | |
a0a54079 | 539 | |
dfeab068 | 540 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
0f113f3e | 541 | i = al - bl; |
775c63fc UM |
542 | #endif |
543 | #ifdef BN_MUL_COMBA | |
0f113f3e | 544 | if (i == 0) { |
775c63fc | 545 | # if 0 |
0f113f3e MC |
546 | if (al == 4) { |
547 | if (bn_wexpand(rr, 8) == NULL) | |
548 | goto err; | |
549 | rr->top = 8; | |
550 | bn_mul_comba4(rr->d, a->d, b->d); | |
551 | goto end; | |
552 | } | |
775c63fc | 553 | # endif |
0f113f3e MC |
554 | if (al == 8) { |
555 | if (bn_wexpand(rr, 16) == NULL) | |
556 | goto err; | |
557 | rr->top = 16; | |
558 | bn_mul_comba8(rr->d, a->d, b->d); | |
559 | goto end; | |
560 | } | |
561 | } | |
562 | #endif /* BN_MUL_COMBA */ | |
dfeab068 | 563 | #ifdef BN_RECURSION |
0f113f3e MC |
564 | if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) { |
565 | if (i >= -1 && i <= 1) { | |
566 | /* | |
567 | * Find out the power of two lower or equal to the longest of the | |
568 | * two numbers | |
569 | */ | |
570 | if (i >= 0) { | |
571 | j = BN_num_bits_word((BN_ULONG)al); | |
572 | } | |
573 | if (i == -1) { | |
574 | j = BN_num_bits_word((BN_ULONG)bl); | |
575 | } | |
576 | j = 1 << (j - 1); | |
577 | assert(j <= al || j <= bl); | |
578 | k = j + j; | |
579 | t = BN_CTX_get(ctx); | |
580 | if (t == NULL) | |
581 | goto err; | |
582 | if (al > j || bl > j) { | |
583 | if (bn_wexpand(t, k * 4) == NULL) | |
584 | goto err; | |
585 | if (bn_wexpand(rr, k * 4) == NULL) | |
586 | goto err; | |
587 | bn_mul_part_recursive(rr->d, a->d, b->d, | |
588 | j, al - j, bl - j, t->d); | |
589 | } else { /* al <= j || bl <= j */ | |
590 | ||
591 | if (bn_wexpand(t, k * 2) == NULL) | |
592 | goto err; | |
593 | if (bn_wexpand(rr, k * 2) == NULL) | |
594 | goto err; | |
595 | bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d); | |
596 | } | |
597 | rr->top = top; | |
598 | goto end; | |
599 | } | |
0f113f3e MC |
600 | } |
601 | #endif /* BN_RECURSION */ | |
602 | if (bn_wexpand(rr, top) == NULL) | |
603 | goto err; | |
604 | rr->top = top; | |
605 | bn_mul_normal(rr->d, a->d, al, b->d, bl); | |
58964a49 | 606 | |
a0a54079 | 607 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) |
0f113f3e | 608 | end: |
a0a54079 | 609 | #endif |
38d1b3cc | 610 | rr->neg = a->neg ^ b->neg; |
fcc4ee09 | 611 | rr->flags |= BN_FLG_FIXED_TOP; |
78e09b53 RS |
612 | if (r != rr && BN_copy(r, rr) == NULL) |
613 | goto err; | |
614 | ||
0f113f3e MC |
615 | ret = 1; |
616 | err: | |
617 | bn_check_top(r); | |
618 | BN_CTX_end(ctx); | |
26a7d938 | 619 | return ret; |
0f113f3e | 620 | } |
58964a49 | 621 | |
6b691a5c | 622 | void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) |
0f113f3e MC |
623 | { |
624 | BN_ULONG *rr; | |
625 | ||
626 | if (na < nb) { | |
627 | int itmp; | |
628 | BN_ULONG *ltmp; | |
629 | ||
630 | itmp = na; | |
631 | na = nb; | |
632 | nb = itmp; | |
633 | ltmp = a; | |
634 | a = b; | |
635 | b = ltmp; | |
636 | ||
637 | } | |
638 | rr = &(r[na]); | |
639 | if (nb <= 0) { | |
640 | (void)bn_mul_words(r, a, na, 0); | |
641 | return; | |
642 | } else | |
643 | rr[0] = bn_mul_words(r, a, na, b[0]); | |
644 | ||
645 | for (;;) { | |
646 | if (--nb <= 0) | |
647 | return; | |
648 | rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); | |
649 | if (--nb <= 0) | |
650 | return; | |
651 | rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); | |
652 | if (--nb <= 0) | |
653 | return; | |
654 | rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); | |
655 | if (--nb <= 0) | |
656 | return; | |
657 | rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); | |
658 | rr += 4; | |
659 | r += 4; | |
660 | b += 4; | |
661 | } | |
662 | } | |
dfeab068 | 663 | |
6b691a5c | 664 | void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) |
0f113f3e MC |
665 | { |
666 | bn_mul_words(r, a, n, b[0]); | |
667 | ||
668 | for (;;) { | |
669 | if (--n <= 0) | |
670 | return; | |
671 | bn_mul_add_words(&(r[1]), a, n, b[1]); | |
672 | if (--n <= 0) | |
673 | return; | |
674 | bn_mul_add_words(&(r[2]), a, n, b[2]); | |
675 | if (--n <= 0) | |
676 | return; | |
677 | bn_mul_add_words(&(r[3]), a, n, b[3]); | |
678 | if (--n <= 0) | |
679 | return; | |
680 | bn_mul_add_words(&(r[4]), a, n, b[4]); | |
681 | r += 4; | |
682 | b += 4; | |
683 | } | |
684 | } |