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