Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_div.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | /* $OpenBSD: bn_div.c,v 1.25 2017/01/29 17:49:22 beck 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 | #include <stdio.h> | - | ||||||||||||||||||||||||
60 | - | |||||||||||||||||||||||||
61 | #include <openssl/opensslconf.h> | - | ||||||||||||||||||||||||
62 | - | |||||||||||||||||||||||||
63 | #include <openssl/bn.h> | - | ||||||||||||||||||||||||
64 | #include <openssl/err.h> | - | ||||||||||||||||||||||||
65 | - | |||||||||||||||||||||||||
66 | #include "bn_lcl.h" | - | ||||||||||||||||||||||||
67 | - | |||||||||||||||||||||||||
68 | #if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ | - | ||||||||||||||||||||||||
69 | && !defined(BN_DIV3W) | - | ||||||||||||||||||||||||
70 | # if defined(__GNUC__) && __GNUC__>=2 | - | ||||||||||||||||||||||||
71 | # if defined(__i386) || defined (__i386__) | - | ||||||||||||||||||||||||
72 | /* | - | ||||||||||||||||||||||||
73 | * There were two reasons for implementing this template: | - | ||||||||||||||||||||||||
74 | * - GNU C generates a call to a function (__udivdi3 to be exact) | - | ||||||||||||||||||||||||
75 | * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to | - | ||||||||||||||||||||||||
76 | * understand why...); | - | ||||||||||||||||||||||||
77 | * - divl doesn't only calculate quotient, but also leaves | - | ||||||||||||||||||||||||
78 | * remainder in %edx which we can definitely use here:-) | - | ||||||||||||||||||||||||
79 | * | - | ||||||||||||||||||||||||
80 | * <appro@fy.chalmers.se> | - | ||||||||||||||||||||||||
81 | */ | - | ||||||||||||||||||||||||
82 | #undef bn_div_words | - | ||||||||||||||||||||||||
83 | # define bn_div_words(n0,n1,d0) \ | - | ||||||||||||||||||||||||
84 | ({ asm volatile ( \ | - | ||||||||||||||||||||||||
85 | "divl %4" \ | - | ||||||||||||||||||||||||
86 | : "=a"(q), "=d"(rem) \ | - | ||||||||||||||||||||||||
87 | : "a"(n1), "d"(n0), "g"(d0) \ | - | ||||||||||||||||||||||||
88 | : "cc"); \ | - | ||||||||||||||||||||||||
89 | q; \ | - | ||||||||||||||||||||||||
90 | }) | - | ||||||||||||||||||||||||
91 | # define REMAINDER_IS_ALREADY_CALCULATED | - | ||||||||||||||||||||||||
92 | # elif defined(__x86_64) | - | ||||||||||||||||||||||||
93 | /* | - | ||||||||||||||||||||||||
94 | * Same story here, but it's 128-bit by 64-bit division. Wow! | - | ||||||||||||||||||||||||
95 | * <appro@fy.chalmers.se> | - | ||||||||||||||||||||||||
96 | */ | - | ||||||||||||||||||||||||
97 | # undef bn_div_words | - | ||||||||||||||||||||||||
98 | # define bn_div_words(n0,n1,d0) \ | - | ||||||||||||||||||||||||
99 | ({ asm volatile ( \ | - | ||||||||||||||||||||||||
100 | "divq %4" \ | - | ||||||||||||||||||||||||
101 | : "=a"(q), "=d"(rem) \ | - | ||||||||||||||||||||||||
102 | : "a"(n1), "d"(n0), "g"(d0) \ | - | ||||||||||||||||||||||||
103 | : "cc"); \ | - | ||||||||||||||||||||||||
104 | q; \ | - | ||||||||||||||||||||||||
105 | }) | - | ||||||||||||||||||||||||
106 | # define REMAINDER_IS_ALREADY_CALCULATED | - | ||||||||||||||||||||||||
107 | # endif /* __<cpu> */ | - | ||||||||||||||||||||||||
108 | # endif /* __GNUC__ */ | - | ||||||||||||||||||||||||
109 | #endif /* OPENSSL_NO_ASM */ | - | ||||||||||||||||||||||||
110 | - | |||||||||||||||||||||||||
111 | - | |||||||||||||||||||||||||
112 | /* BN_div computes dv := num / divisor, rounding towards | - | ||||||||||||||||||||||||
113 | * zero, and sets up rm such that dv*divisor + rm = num holds. | - | ||||||||||||||||||||||||
114 | * Thus: | - | ||||||||||||||||||||||||
115 | * dv->neg == num->neg ^ divisor->neg (unless the result is zero) | - | ||||||||||||||||||||||||
116 | * rm->neg == num->neg (unless the remainder is zero) | - | ||||||||||||||||||||||||
117 | * If 'dv' or 'rm' is NULL, the respective value is not returned. | - | ||||||||||||||||||||||||
118 | */ | - | ||||||||||||||||||||||||
119 | static int | - | ||||||||||||||||||||||||
120 | BN_div_internal(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, | - | ||||||||||||||||||||||||
121 | BN_CTX *ctx, int ct) | - | ||||||||||||||||||||||||
122 | { | - | ||||||||||||||||||||||||
123 | int norm_shift, i, loop; | - | ||||||||||||||||||||||||
124 | BIGNUM *tmp, wnum, *snum, *sdiv, *res; | - | ||||||||||||||||||||||||
125 | BN_ULONG *resp, *wnump; | - | ||||||||||||||||||||||||
126 | BN_ULONG d0, d1; | - | ||||||||||||||||||||||||
127 | int num_n, div_n; | - | ||||||||||||||||||||||||
128 | int no_branch = 0; | - | ||||||||||||||||||||||||
129 | - | |||||||||||||||||||||||||
130 | /* Invalid zero-padding would have particularly bad consequences | - | ||||||||||||||||||||||||
131 | * in the case of 'num', so don't just rely on bn_check_top() for this one | - | ||||||||||||||||||||||||
132 | * (bn_check_top() works only for BN_DEBUG builds) */ | - | ||||||||||||||||||||||||
133 | if (num->top > 0 && num->d[num->top - 1] == 0) {
| 0-458458 | ||||||||||||||||||||||||
134 | BNerror(BN_R_NOT_INITIALIZED); | - | ||||||||||||||||||||||||
135 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||
136 | } | - | ||||||||||||||||||||||||
137 | - | |||||||||||||||||||||||||
138 | bn_check_top(num); | - | ||||||||||||||||||||||||
139 | - | |||||||||||||||||||||||||
140 | if (ct)
| 1421-457664 | ||||||||||||||||||||||||
141 | no_branch = 1; executed 457664 times by 14 tests: no_branch = 1; Executed by:
| 457664 | ||||||||||||||||||||||||
142 | - | |||||||||||||||||||||||||
143 | bn_check_top(dv); | - | ||||||||||||||||||||||||
144 | bn_check_top(rm); | - | ||||||||||||||||||||||||
145 | /* bn_check_top(num); */ /* 'num' has been checked already */ | - | ||||||||||||||||||||||||
146 | bn_check_top(divisor); | - | ||||||||||||||||||||||||
147 | - | |||||||||||||||||||||||||
148 | if (BN_is_zero(divisor)) {
| 6-459079 | ||||||||||||||||||||||||
149 | BNerror(BN_R_DIV_BY_ZERO); | - | ||||||||||||||||||||||||
150 | return (0); executed 6 times by 1 test: return (0); Executed by:
| 6 | ||||||||||||||||||||||||
151 | } | - | ||||||||||||||||||||||||
152 | - | |||||||||||||||||||||||||
153 | if (!no_branch && BN_ucmp(num, divisor) < 0) {
| 281-457659 | ||||||||||||||||||||||||
154 | if (rm != NULL) {
| 0-281 | ||||||||||||||||||||||||
155 | if (BN_copy(rm, num) == NULL)
| 0-281 | ||||||||||||||||||||||||
156 | return (0); never executed: return (0); | 0 | ||||||||||||||||||||||||
157 | } executed 281 times by 2 tests: end of block Executed by:
| 281 | ||||||||||||||||||||||||
158 | if (dv != NULL)
| 51-230 | ||||||||||||||||||||||||
159 | BN_zero(dv); executed 51 times by 1 test: (BN_set_word((dv),0)); Executed by:
| 51 | ||||||||||||||||||||||||
160 | return (1); executed 281 times by 2 tests: return (1); Executed by:
| 281 | ||||||||||||||||||||||||
161 | } | - | ||||||||||||||||||||||||
162 | - | |||||||||||||||||||||||||
163 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||
164 | tmp = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
165 | snum = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
166 | sdiv = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
167 | if (dv == NULL)
| 119825-338973 | ||||||||||||||||||||||||
168 | res = BN_CTX_get(ctx); executed 119825 times by 14 tests: res = BN_CTX_get(ctx); Executed by:
| 119825 | ||||||||||||||||||||||||
169 | else | - | ||||||||||||||||||||||||
170 | res = dv; executed 338973 times by 14 tests: res = dv; Executed by:
| 338973 | ||||||||||||||||||||||||
171 | if (tmp == NULL || snum == NULL || sdiv == NULL || res == NULL)
| 0-458798 | ||||||||||||||||||||||||
172 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
173 | - | |||||||||||||||||||||||||
174 | /* First we normalise the numbers */ | - | ||||||||||||||||||||||||
175 | norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2); | - | ||||||||||||||||||||||||
176 | if (!(BN_lshift(sdiv, divisor, norm_shift)))
| 0-458798 | ||||||||||||||||||||||||
177 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
178 | sdiv->neg = 0; | - | ||||||||||||||||||||||||
179 | norm_shift += BN_BITS2; | - | ||||||||||||||||||||||||
180 | if (!(BN_lshift(snum, num, norm_shift)))
| 0-458798 | ||||||||||||||||||||||||
181 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
182 | snum->neg = 0; | - | ||||||||||||||||||||||||
183 | - | |||||||||||||||||||||||||
184 | if (no_branch) {
| 1139-457659 | ||||||||||||||||||||||||
185 | /* Since we don't know whether snum is larger than sdiv, | - | ||||||||||||||||||||||||
186 | * we pad snum with enough zeroes without changing its | - | ||||||||||||||||||||||||
187 | * value. | - | ||||||||||||||||||||||||
188 | */ | - | ||||||||||||||||||||||||
189 | if (snum->top <= sdiv->top + 1) {
| 79263-378396 | ||||||||||||||||||||||||
190 | if (bn_wexpand(snum, sdiv->top + 2) == NULL)
| 0-79263 | ||||||||||||||||||||||||
191 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
192 | for (i = snum->top; i < sdiv->top + 2; i++)
| 79263-89981 | ||||||||||||||||||||||||
193 | snum->d[i] = 0; executed 89981 times by 14 tests: snum->d[i] = 0; Executed by:
| 89981 | ||||||||||||||||||||||||
194 | snum->top = sdiv->top + 2; | - | ||||||||||||||||||||||||
195 | } else { executed 79263 times by 14 tests: end of block Executed by:
| 79263 | ||||||||||||||||||||||||
196 | if (bn_wexpand(snum, snum->top + 1) == NULL)
| 0-378396 | ||||||||||||||||||||||||
197 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
198 | snum->d[snum->top] = 0; | - | ||||||||||||||||||||||||
199 | snum->top ++; | - | ||||||||||||||||||||||||
200 | } executed 378396 times by 14 tests: end of block Executed by:
| 378396 | ||||||||||||||||||||||||
201 | } | - | ||||||||||||||||||||||||
202 | - | |||||||||||||||||||||||||
203 | div_n = sdiv->top; | - | ||||||||||||||||||||||||
204 | num_n = snum->top; | - | ||||||||||||||||||||||||
205 | loop = num_n - div_n; | - | ||||||||||||||||||||||||
206 | /* Lets setup a 'window' into snum | - | ||||||||||||||||||||||||
207 | * This is the part that corresponds to the current | - | ||||||||||||||||||||||||
208 | * 'area' being divided */ | - | ||||||||||||||||||||||||
209 | wnum.neg = 0; | - | ||||||||||||||||||||||||
210 | wnum.d = &(snum->d[loop]); | - | ||||||||||||||||||||||||
211 | wnum.top = div_n; | - | ||||||||||||||||||||||||
212 | /* only needed when BN_ucmp messes up the values between top and max */ | - | ||||||||||||||||||||||||
213 | wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ | - | ||||||||||||||||||||||||
214 | wnum.flags = snum->flags | BN_FLG_STATIC_DATA; | - | ||||||||||||||||||||||||
215 | - | |||||||||||||||||||||||||
216 | /* Get the top 2 words of sdiv */ | - | ||||||||||||||||||||||||
217 | /* div_n=sdiv->top; */ | - | ||||||||||||||||||||||||
218 | d0 = sdiv->d[div_n - 1]; | - | ||||||||||||||||||||||||
219 | d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2];
| 130955-327843 | ||||||||||||||||||||||||
220 | - | |||||||||||||||||||||||||
221 | /* pointer to the 'top' of snum */ | - | ||||||||||||||||||||||||
222 | wnump = &(snum->d[num_n - 1]); | - | ||||||||||||||||||||||||
223 | - | |||||||||||||||||||||||||
224 | /* Setup to 'res' */ | - | ||||||||||||||||||||||||
225 | res->neg = (num->neg ^ divisor->neg); | - | ||||||||||||||||||||||||
226 | if (!bn_wexpand(res, (loop + 1)))
| 0-458798 | ||||||||||||||||||||||||
227 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
228 | res->top = loop - no_branch; | - | ||||||||||||||||||||||||
229 | resp = &(res->d[loop - 1]); | - | ||||||||||||||||||||||||
230 | - | |||||||||||||||||||||||||
231 | /* space for temp */ | - | ||||||||||||||||||||||||
232 | if (!bn_wexpand(tmp, (div_n + 1)))
| 0-458798 | ||||||||||||||||||||||||
233 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
234 | - | |||||||||||||||||||||||||
235 | if (!no_branch) {
| 1139-457659 | ||||||||||||||||||||||||
236 | if (BN_ucmp(&wnum, sdiv) >= 0) {
| 23-1116 | ||||||||||||||||||||||||
237 | /* If BN_DEBUG_RAND is defined BN_ucmp changes (via | - | ||||||||||||||||||||||||
238 | * bn_pollute) the const bignum arguments => | - | ||||||||||||||||||||||||
239 | * clean the values between top and max again */ | - | ||||||||||||||||||||||||
240 | bn_clear_top2max(&wnum); | - | ||||||||||||||||||||||||
241 | bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); | - | ||||||||||||||||||||||||
242 | *resp = 1; | - | ||||||||||||||||||||||||
243 | } else executed 23 times by 2 tests: end of block Executed by:
| 23 | ||||||||||||||||||||||||
244 | res->top--; executed 1116 times by 2 tests: res->top--; Executed by:
| 1116 | ||||||||||||||||||||||||
245 | } | - | ||||||||||||||||||||||||
246 | - | |||||||||||||||||||||||||
247 | /* if res->top == 0 then clear the neg value otherwise decrease | - | ||||||||||||||||||||||||
248 | * the resp pointer */ | - | ||||||||||||||||||||||||
249 | if (res->top == 0)
| 0-458798 | ||||||||||||||||||||||||
250 | res->neg = 0; never executed: res->neg = 0; | 0 | ||||||||||||||||||||||||
251 | else | - | ||||||||||||||||||||||||
252 | resp--; executed 458798 times by 14 tests: resp--; Executed by:
| 458798 | ||||||||||||||||||||||||
253 | - | |||||||||||||||||||||||||
254 | for (i = 0; i < loop - 1; i++, wnump--, resp--) {
| 458798-1385068 | ||||||||||||||||||||||||
255 | BN_ULONG q, l0; | - | ||||||||||||||||||||||||
256 | /* the first part of the loop uses the top two words of | - | ||||||||||||||||||||||||
257 | * snum and sdiv to calculate a BN_ULONG q such that | - | ||||||||||||||||||||||||
258 | * | wnum - sdiv * q | < sdiv */ | - | ||||||||||||||||||||||||
259 | #if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) | - | ||||||||||||||||||||||||
260 | BN_ULONG bn_div_3_words(BN_ULONG*, BN_ULONG, BN_ULONG); | - | ||||||||||||||||||||||||
261 | q = bn_div_3_words(wnump, d1, d0); | - | ||||||||||||||||||||||||
262 | #else | - | ||||||||||||||||||||||||
263 | BN_ULONG n0, n1, rem = 0; | - | ||||||||||||||||||||||||
264 | - | |||||||||||||||||||||||||
265 | n0 = wnump[0]; | - | ||||||||||||||||||||||||
266 | n1 = wnump[-1]; | - | ||||||||||||||||||||||||
267 | if (n0 == d0)
| 110-1384958 | ||||||||||||||||||||||||
268 | q = BN_MASK2; executed 110 times by 4 tests: q = (0xffffffffffffffffL); Executed by:
| 110 | ||||||||||||||||||||||||
269 | else /* n0 < d0 */ | - | ||||||||||||||||||||||||
270 | { | - | ||||||||||||||||||||||||
271 | #ifdef BN_LLONG | - | ||||||||||||||||||||||||
272 | BN_ULLONG t2; | - | ||||||||||||||||||||||||
273 | - | |||||||||||||||||||||||||
274 | #if defined(BN_DIV2W) && !defined(bn_div_words) | - | ||||||||||||||||||||||||
275 | q = (BN_ULONG)(((((BN_ULLONG)n0) << BN_BITS2)|n1)/d0); | - | ||||||||||||||||||||||||
276 | #else | - | ||||||||||||||||||||||||
277 | q = bn_div_words(n0, n1, d0); | - | ||||||||||||||||||||||||
278 | #endif | - | ||||||||||||||||||||||||
279 | - | |||||||||||||||||||||||||
280 | #ifndef REMAINDER_IS_ALREADY_CALCULATED | - | ||||||||||||||||||||||||
281 | /* | - | ||||||||||||||||||||||||
282 | * rem doesn't have to be BN_ULLONG. The least we | - | ||||||||||||||||||||||||
283 | * know it's less that d0, isn't it? | - | ||||||||||||||||||||||||
284 | */ | - | ||||||||||||||||||||||||
285 | rem = (n1 - q * d0) & BN_MASK2; | - | ||||||||||||||||||||||||
286 | #endif | - | ||||||||||||||||||||||||
287 | t2 = (BN_ULLONG)d1*q; | - | ||||||||||||||||||||||||
288 | - | |||||||||||||||||||||||||
289 | for (;;) { | - | ||||||||||||||||||||||||
290 | if (t2 <= ((((BN_ULLONG)rem) << BN_BITS2) | | - | ||||||||||||||||||||||||
291 | wnump[-2])) | - | ||||||||||||||||||||||||
292 | break; | - | ||||||||||||||||||||||||
293 | q--; | - | ||||||||||||||||||||||||
294 | rem += d0; | - | ||||||||||||||||||||||||
295 | if (rem < d0) break; /* don't let rem overflow */ | - | ||||||||||||||||||||||||
296 | t2 -= d1; | - | ||||||||||||||||||||||||
297 | } | - | ||||||||||||||||||||||||
298 | #else /* !BN_LLONG */ | - | ||||||||||||||||||||||||
299 | BN_ULONG t2l, t2h; | - | ||||||||||||||||||||||||
300 | - | |||||||||||||||||||||||||
301 | q = bn_div_words(n0, n1, d0); | - | ||||||||||||||||||||||||
302 | #ifndef REMAINDER_IS_ALREADY_CALCULATED | - | ||||||||||||||||||||||||
303 | rem = (n1 - q*d0)&BN_MASK2; | - | ||||||||||||||||||||||||
304 | #endif | - | ||||||||||||||||||||||||
305 | - | |||||||||||||||||||||||||
306 | #if defined(BN_UMULT_LOHI) | - | ||||||||||||||||||||||||
307 | BN_UMULT_LOHI(t2l, t2h, d1, q); | - | ||||||||||||||||||||||||
308 | #elif defined(BN_UMULT_HIGH) | - | ||||||||||||||||||||||||
309 | t2l = d1 * q; | - | ||||||||||||||||||||||||
310 | t2h = BN_UMULT_HIGH(d1, q); | - | ||||||||||||||||||||||||
311 | #else | - | ||||||||||||||||||||||||
312 | { | - | ||||||||||||||||||||||||
313 | BN_ULONG ql, qh; | - | ||||||||||||||||||||||||
314 | t2l = LBITS(d1); | - | ||||||||||||||||||||||||
315 | t2h = HBITS(d1); | - | ||||||||||||||||||||||||
316 | ql = LBITS(q); | - | ||||||||||||||||||||||||
317 | qh = HBITS(q); | - | ||||||||||||||||||||||||
318 | mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ | - | ||||||||||||||||||||||||
319 | } | - | ||||||||||||||||||||||||
320 | #endif | - | ||||||||||||||||||||||||
321 | - | |||||||||||||||||||||||||
322 | for (;;) { | - | ||||||||||||||||||||||||
323 | if ((t2h < rem) ||
| 187633-1307965 | ||||||||||||||||||||||||
324 | ((t2h == rem) && (t2l <= wnump[-2])))
| 83-178122 | ||||||||||||||||||||||||
325 | break; executed 1317393 times by 14 tests: break; Executed by:
| 1317393 | ||||||||||||||||||||||||
326 | q--; | - | ||||||||||||||||||||||||
327 | rem += d0; | - | ||||||||||||||||||||||||
328 | if (rem < d0)
| 67565-110640 | ||||||||||||||||||||||||
329 | break; /* don't let rem overflow */ executed 67565 times by 12 tests: break; Executed by:
| 67565 | ||||||||||||||||||||||||
330 | if (t2l < d1)
| 45740-64900 | ||||||||||||||||||||||||
331 | t2h--; executed 64900 times by 12 tests: t2h--; Executed by:
| 64900 | ||||||||||||||||||||||||
332 | t2l -= d1; | - | ||||||||||||||||||||||||
333 | } executed 110640 times by 12 tests: end of block Executed by:
| 110640 | ||||||||||||||||||||||||
334 | #endif /* !BN_LLONG */ | - | ||||||||||||||||||||||||
335 | } executed 1384958 times by 14 tests: end of block Executed by:
| 1384958 | ||||||||||||||||||||||||
336 | #endif /* !BN_DIV3W */ | - | ||||||||||||||||||||||||
337 | - | |||||||||||||||||||||||||
338 | l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); | - | ||||||||||||||||||||||||
339 | tmp->d[div_n] = l0; | - | ||||||||||||||||||||||||
340 | wnum.d--; | - | ||||||||||||||||||||||||
341 | /* ingore top values of the bignums just sub the two | - | ||||||||||||||||||||||||
342 | * BN_ULONG arrays with bn_sub_words */ | - | ||||||||||||||||||||||||
343 | if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) {
| 413-1384655 | ||||||||||||||||||||||||
344 | /* Note: As we have considered only the leading | - | ||||||||||||||||||||||||
345 | * two BN_ULONGs in the calculation of q, sdiv * q | - | ||||||||||||||||||||||||
346 | * might be greater than wnum (but then (q-1) * sdiv | - | ||||||||||||||||||||||||
347 | * is less or equal than wnum) | - | ||||||||||||||||||||||||
348 | */ | - | ||||||||||||||||||||||||
349 | q--; | - | ||||||||||||||||||||||||
350 | if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n))
| 0-413 | ||||||||||||||||||||||||
351 | /* we can't have an overflow here (assuming | - | ||||||||||||||||||||||||
352 | * that q != 0, but if q == 0 then tmp is | - | ||||||||||||||||||||||||
353 | * zero anyway) */ | - | ||||||||||||||||||||||||
354 | (*wnump)++; executed 413 times by 6 tests: (*wnump)++; Executed by:
| 413 | ||||||||||||||||||||||||
355 | } executed 413 times by 6 tests: end of block Executed by:
| 413 | ||||||||||||||||||||||||
356 | /* store part of the result */ | - | ||||||||||||||||||||||||
357 | *resp = q; | - | ||||||||||||||||||||||||
358 | } executed 1385068 times by 14 tests: end of block Executed by:
| 1385068 | ||||||||||||||||||||||||
359 | bn_correct_top(snum); executed 450459 times by 14 tests: break; Executed by:
executed 458798 times by 14 tests: end of block Executed by:
| 0-1869162 | ||||||||||||||||||||||||
360 | if (rm != NULL) {
| 3331-455467 | ||||||||||||||||||||||||
361 | /* Keep a copy of the neg flag in num because if rm==num | - | ||||||||||||||||||||||||
362 | * BN_rshift() will overwrite it. | - | ||||||||||||||||||||||||
363 | */ | - | ||||||||||||||||||||||||
364 | int neg = num->neg; | - | ||||||||||||||||||||||||
365 | BN_rshift(rm, snum, norm_shift); | - | ||||||||||||||||||||||||
366 | if (!BN_is_zero(rm))
| 5458-450009 | ||||||||||||||||||||||||
367 | rm->neg = neg; executed 450009 times by 14 tests: rm->neg = neg; Executed by:
| 450009 | ||||||||||||||||||||||||
368 | bn_check_top(rm); | - | ||||||||||||||||||||||||
369 | } executed 455467 times by 14 tests: end of block Executed by:
| 455467 | ||||||||||||||||||||||||
370 | if (no_branch)
| 1139-457659 | ||||||||||||||||||||||||
371 | bn_correct_top(res); executed 454359 times by 14 tests: break; Executed by:
executed 457659 times by 14 tests: end of block Executed by:
executed 457659 times by 14 tests: end of block Executed by:
| 0-835683 | ||||||||||||||||||||||||
372 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
373 | return (1); executed 458798 times by 14 tests: return (1); Executed by:
| 458798 | ||||||||||||||||||||||||
374 | - | |||||||||||||||||||||||||
375 | err: | - | ||||||||||||||||||||||||
376 | bn_check_top(rm); | - | ||||||||||||||||||||||||
377 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
378 | return (0); never executed: return (0); | 0 | ||||||||||||||||||||||||
379 | } | - | ||||||||||||||||||||||||
380 | - | |||||||||||||||||||||||||
381 | int | - | ||||||||||||||||||||||||
382 | BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, | - | ||||||||||||||||||||||||
383 | BN_CTX *ctx) | - | ||||||||||||||||||||||||
384 | { | - | ||||||||||||||||||||||||
385 | int ct = ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) ||
| 0-1421 | ||||||||||||||||||||||||
386 | (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0));
| 0-1421 | ||||||||||||||||||||||||
387 | - | |||||||||||||||||||||||||
388 | return BN_div_internal(dv, rm, num, divisor, ctx, ct); executed 1421 times by 2 tests: return BN_div_internal(dv, rm, num, divisor, ctx, ct); Executed by:
| 1421 | ||||||||||||||||||||||||
389 | } | - | ||||||||||||||||||||||||
390 | - | |||||||||||||||||||||||||
391 | int | - | ||||||||||||||||||||||||
392 | BN_div_nonct(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, | - | ||||||||||||||||||||||||
393 | BN_CTX *ctx) | - | ||||||||||||||||||||||||
394 | { | - | ||||||||||||||||||||||||
395 | return BN_div_internal(dv, rm, num, divisor, ctx, 0); never executed: return BN_div_internal(dv, rm, num, divisor, ctx, 0); | 0 | ||||||||||||||||||||||||
396 | } | - | ||||||||||||||||||||||||
397 | - | |||||||||||||||||||||||||
398 | int | - | ||||||||||||||||||||||||
399 | BN_div_ct(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, | - | ||||||||||||||||||||||||
400 | BN_CTX *ctx) | - | ||||||||||||||||||||||||
401 | { | - | ||||||||||||||||||||||||
402 | return BN_div_internal(dv, rm, num, divisor, ctx, 1); executed 457664 times by 14 tests: return BN_div_internal(dv, rm, num, divisor, ctx, 1); Executed by:
| 457664 | ||||||||||||||||||||||||
403 | } | - | ||||||||||||||||||||||||
Source code | Switch to Preprocessed file |