]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
edea42c6 | 2 | * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved. |
d02b48c6 | 3 | * |
4f22f405 RS |
4 | * Licensed under the OpenSSL license (the "License"). You may not use |
5 | * this file except in compliance with the License. You can obtain a copy | |
6 | * in the file LICENSE in the source distribution or at | |
7 | * https://www.openssl.org/source/license.html | |
d02b48c6 RE |
8 | */ |
9 | ||
84c15db5 | 10 | #include <openssl/bn.h> |
b39fc560 | 11 | #include "internal/cryptlib.h" |
d02b48c6 RE |
12 | #include "bn_lcl.h" |
13 | ||
14 | /* The old slow way */ | |
4a6222d7 | 15 | #if 0 |
0bde1089 | 16 | int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, |
0f113f3e MC |
17 | BN_CTX *ctx) |
18 | { | |
19 | int i, nm, nd; | |
20 | int ret = 0; | |
21 | BIGNUM *D; | |
22 | ||
23 | bn_check_top(m); | |
24 | bn_check_top(d); | |
25 | if (BN_is_zero(d)) { | |
26 | BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); | |
26a7d938 | 27 | return 0; |
0f113f3e MC |
28 | } |
29 | ||
30 | if (BN_ucmp(m, d) < 0) { | |
31 | if (rem != NULL) { | |
32 | if (BN_copy(rem, m) == NULL) | |
26a7d938 | 33 | return 0; |
0f113f3e MC |
34 | } |
35 | if (dv != NULL) | |
36 | BN_zero(dv); | |
208fb891 | 37 | return 1; |
0f113f3e MC |
38 | } |
39 | ||
40 | BN_CTX_start(ctx); | |
41 | D = BN_CTX_get(ctx); | |
42 | if (dv == NULL) | |
43 | dv = BN_CTX_get(ctx); | |
44 | if (rem == NULL) | |
45 | rem = BN_CTX_get(ctx); | |
46 | if (D == NULL || dv == NULL || rem == NULL) | |
47 | goto end; | |
48 | ||
49 | nd = BN_num_bits(d); | |
50 | nm = BN_num_bits(m); | |
51 | if (BN_copy(D, d) == NULL) | |
52 | goto end; | |
53 | if (BN_copy(rem, m) == NULL) | |
54 | goto end; | |
55 | ||
56 | /* | |
57 | * The next 2 are needed so we can do a dv->d[0]|=1 later since | |
58 | * BN_lshift1 will only work once there is a value :-) | |
59 | */ | |
60 | BN_zero(dv); | |
61 | if (bn_wexpand(dv, 1) == NULL) | |
62 | goto end; | |
63 | dv->top = 1; | |
64 | ||
65 | if (!BN_lshift(D, D, nm - nd)) | |
66 | goto end; | |
67 | for (i = nm - nd; i >= 0; i--) { | |
68 | if (!BN_lshift1(dv, dv)) | |
69 | goto end; | |
70 | if (BN_ucmp(rem, D) >= 0) { | |
71 | dv->d[0] |= 1; | |
72 | if (!BN_usub(rem, rem, D)) | |
73 | goto end; | |
74 | } | |
d02b48c6 | 75 | /* CAN IMPROVE (and have now :=) */ |
0f113f3e MC |
76 | if (!BN_rshift1(D, D)) |
77 | goto end; | |
78 | } | |
79 | rem->neg = BN_is_zero(rem) ? 0 : m->neg; | |
80 | dv->neg = m->neg ^ d->neg; | |
81 | ret = 1; | |
9b141126 | 82 | end: |
0f113f3e | 83 | BN_CTX_end(ctx); |
26a7d938 | 84 | return ret; |
0f113f3e | 85 | } |
d02b48c6 RE |
86 | |
87 | #else | |
88 | ||
0f113f3e | 89 | # if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ |
cf1b7d96 | 90 | && !defined(PEDANTIC) && !defined(BN_DIV3W) |
0f113f3e MC |
91 | # if defined(__GNUC__) && __GNUC__>=2 |
92 | # if defined(__i386) || defined (__i386__) | |
c80fd6b2 | 93 | /*- |
4a6222d7 UM |
94 | * There were two reasons for implementing this template: |
95 | * - GNU C generates a call to a function (__udivdi3 to be exact) | |
96 | * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to | |
97 | * understand why...); | |
98 | * - divl doesn't only calculate quotient, but also leaves | |
99 | * remainder in %edx which we can definitely use here:-) | |
4a6222d7 | 100 | */ |
0f113f3e MC |
101 | # undef bn_div_words |
102 | # define bn_div_words(n0,n1,d0) \ | |
103 | ({ asm volatile ( \ | |
104 | "divl %4" \ | |
105 | : "=a"(q), "=d"(rem) \ | |
68b4a6e9 | 106 | : "a"(n1), "d"(n0), "r"(d0) \ |
0f113f3e MC |
107 | : "cc"); \ |
108 | q; \ | |
109 | }) | |
110 | # define REMAINDER_IS_ALREADY_CALCULATED | |
111 | # elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG) | |
2f98abbc AP |
112 | /* |
113 | * Same story here, but it's 128-bit by 64-bit division. Wow! | |
2f98abbc | 114 | */ |
0f113f3e MC |
115 | # undef bn_div_words |
116 | # define bn_div_words(n0,n1,d0) \ | |
117 | ({ asm volatile ( \ | |
118 | "divq %4" \ | |
119 | : "=a"(q), "=d"(rem) \ | |
68b4a6e9 | 120 | : "a"(n1), "d"(n0), "r"(d0) \ |
0f113f3e MC |
121 | : "cc"); \ |
122 | q; \ | |
123 | }) | |
124 | # define REMAINDER_IS_ALREADY_CALCULATED | |
125 | # endif /* __<cpu> */ | |
126 | # endif /* __GNUC__ */ | |
127 | # endif /* OPENSSL_NO_ASM */ | |
78a0c1f1 | 128 | |
1d97c843 | 129 | /*- |
02e112a8 | 130 | * BN_div computes dv := num / divisor, rounding towards |
55525742 | 131 | * zero, and sets up rm such that dv*divisor + rm = num holds. |
78a0c1f1 BM |
132 | * Thus: |
133 | * dv->neg == num->neg ^ divisor->neg (unless the result is zero) | |
134 | * rm->neg == num->neg (unless the remainder is zero) | |
135 | * If 'dv' or 'rm' is NULL, the respective value is not returned. | |
136 | */ | |
84c15db5 | 137 | int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, |
0f113f3e MC |
138 | BN_CTX *ctx) |
139 | { | |
140 | int norm_shift, i, loop; | |
141 | BIGNUM *tmp, wnum, *snum, *sdiv, *res; | |
142 | BN_ULONG *resp, *wnump; | |
143 | BN_ULONG d0, d1; | |
144 | int num_n, div_n; | |
145 | int no_branch = 0; | |
146 | ||
147 | /* | |
148 | * Invalid zero-padding would have particularly bad consequences so don't | |
149 | * just rely on bn_check_top() here (bn_check_top() works only for | |
150 | * BN_DEBUG builds) | |
151 | */ | |
152 | if ((num->top > 0 && num->d[num->top - 1] == 0) || | |
153 | (divisor->top > 0 && divisor->d[divisor->top - 1] == 0)) { | |
154 | BNerr(BN_F_BN_DIV, BN_R_NOT_INITIALIZED); | |
155 | return 0; | |
156 | } | |
157 | ||
158 | bn_check_top(num); | |
159 | bn_check_top(divisor); | |
160 | ||
161 | if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) | |
162 | || (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) { | |
163 | no_branch = 1; | |
164 | } | |
165 | ||
166 | bn_check_top(dv); | |
167 | bn_check_top(rm); | |
168 | /*- bn_check_top(num); *//* | |
169 | * 'num' has been checked already | |
170 | */ | |
171 | /*- bn_check_top(divisor); *//* | |
172 | * 'divisor' has been checked already | |
173 | */ | |
174 | ||
175 | if (BN_is_zero(divisor)) { | |
176 | BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); | |
26a7d938 | 177 | return 0; |
0f113f3e MC |
178 | } |
179 | ||
180 | if (!no_branch && BN_ucmp(num, divisor) < 0) { | |
181 | if (rm != NULL) { | |
182 | if (BN_copy(rm, num) == NULL) | |
26a7d938 | 183 | return 0; |
0f113f3e MC |
184 | } |
185 | if (dv != NULL) | |
186 | BN_zero(dv); | |
208fb891 | 187 | return 1; |
0f113f3e MC |
188 | } |
189 | ||
190 | BN_CTX_start(ctx); | |
edea42c6 | 191 | res = (dv == NULL) ? BN_CTX_get(ctx) : dv; |
0f113f3e MC |
192 | tmp = BN_CTX_get(ctx); |
193 | snum = BN_CTX_get(ctx); | |
194 | sdiv = BN_CTX_get(ctx); | |
edea42c6 | 195 | if (sdiv == NULL) |
0f113f3e MC |
196 | goto err; |
197 | ||
198 | /* First we normalise the numbers */ | |
199 | norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2); | |
200 | if (!(BN_lshift(sdiv, divisor, norm_shift))) | |
201 | goto err; | |
202 | sdiv->neg = 0; | |
203 | norm_shift += BN_BITS2; | |
204 | if (!(BN_lshift(snum, num, norm_shift))) | |
205 | goto err; | |
206 | snum->neg = 0; | |
207 | ||
208 | if (no_branch) { | |
209 | /* | |
210 | * Since we don't know whether snum is larger than sdiv, we pad snum | |
211 | * with enough zeroes without changing its value. | |
212 | */ | |
213 | if (snum->top <= sdiv->top + 1) { | |
214 | if (bn_wexpand(snum, sdiv->top + 2) == NULL) | |
215 | goto err; | |
216 | for (i = snum->top; i < sdiv->top + 2; i++) | |
217 | snum->d[i] = 0; | |
218 | snum->top = sdiv->top + 2; | |
219 | } else { | |
220 | if (bn_wexpand(snum, snum->top + 1) == NULL) | |
221 | goto err; | |
222 | snum->d[snum->top] = 0; | |
223 | snum->top++; | |
224 | } | |
225 | } | |
226 | ||
227 | div_n = sdiv->top; | |
228 | num_n = snum->top; | |
229 | loop = num_n - div_n; | |
230 | /* | |
231 | * Lets setup a 'window' into snum This is the part that corresponds to | |
232 | * the current 'area' being divided | |
233 | */ | |
234 | wnum.neg = 0; | |
235 | wnum.d = &(snum->d[loop]); | |
236 | wnum.top = div_n; | |
305b68f1 | 237 | wnum.flags = BN_FLG_STATIC_DATA; |
0f113f3e MC |
238 | /* |
239 | * only needed when BN_ucmp messes up the values between top and max | |
240 | */ | |
241 | wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ | |
242 | ||
243 | /* Get the top 2 words of sdiv */ | |
244 | /* div_n=sdiv->top; */ | |
245 | d0 = sdiv->d[div_n - 1]; | |
246 | d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; | |
247 | ||
248 | /* pointer to the 'top' of snum */ | |
249 | wnump = &(snum->d[num_n - 1]); | |
250 | ||
251 | /* Setup to 'res' */ | |
0f113f3e MC |
252 | if (!bn_wexpand(res, (loop + 1))) |
253 | goto err; | |
38d1b3cc | 254 | res->neg = (num->neg ^ divisor->neg); |
0f113f3e MC |
255 | res->top = loop - no_branch; |
256 | resp = &(res->d[loop - 1]); | |
257 | ||
258 | /* space for temp */ | |
259 | if (!bn_wexpand(tmp, (div_n + 1))) | |
260 | goto err; | |
261 | ||
262 | if (!no_branch) { | |
263 | if (BN_ucmp(&wnum, sdiv) >= 0) { | |
264 | /* | |
265 | * If BN_DEBUG_RAND is defined BN_ucmp changes (via bn_pollute) | |
266 | * the const bignum arguments => clean the values between top and | |
267 | * max again | |
268 | */ | |
269 | bn_clear_top2max(&wnum); | |
270 | bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); | |
271 | *resp = 1; | |
272 | } else | |
273 | res->top--; | |
274 | } | |
275 | ||
acc60092 KR |
276 | /* Increase the resp pointer so that we never create an invalid pointer. */ |
277 | resp++; | |
278 | ||
0f113f3e MC |
279 | /* |
280 | * if res->top == 0 then clear the neg value otherwise decrease the resp | |
281 | * pointer | |
282 | */ | |
283 | if (res->top == 0) | |
284 | res->neg = 0; | |
285 | else | |
286 | resp--; | |
287 | ||
acc60092 | 288 | for (i = 0; i < loop - 1; i++, wnump--) { |
0f113f3e MC |
289 | BN_ULONG q, l0; |
290 | /* | |
291 | * the first part of the loop uses the top two words of snum and sdiv | |
292 | * to calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv | |
293 | */ | |
294 | # if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) | |
295 | BN_ULONG bn_div_3_words(BN_ULONG *, BN_ULONG, BN_ULONG); | |
296 | q = bn_div_3_words(wnump, d1, d0); | |
297 | # else | |
298 | BN_ULONG n0, n1, rem = 0; | |
299 | ||
300 | n0 = wnump[0]; | |
301 | n1 = wnump[-1]; | |
302 | if (n0 == d0) | |
303 | q = BN_MASK2; | |
304 | else { /* n0 < d0 */ | |
305 | ||
306 | # ifdef BN_LLONG | |
307 | BN_ULLONG t2; | |
308 | ||
309 | # if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) | |
310 | q = (BN_ULONG)(((((BN_ULLONG) n0) << BN_BITS2) | n1) / d0); | |
311 | # else | |
312 | q = bn_div_words(n0, n1, d0); | |
0f113f3e MC |
313 | # endif |
314 | ||
315 | # ifndef REMAINDER_IS_ALREADY_CALCULATED | |
316 | /* | |
317 | * rem doesn't have to be BN_ULLONG. The least we | |
318 | * know it's less that d0, isn't it? | |
319 | */ | |
320 | rem = (n1 - q * d0) & BN_MASK2; | |
321 | # endif | |
322 | t2 = (BN_ULLONG) d1 *q; | |
323 | ||
324 | for (;;) { | |
325 | if (t2 <= ((((BN_ULLONG) rem) << BN_BITS2) | wnump[-2])) | |
326 | break; | |
327 | q--; | |
328 | rem += d0; | |
329 | if (rem < d0) | |
330 | break; /* don't let rem overflow */ | |
331 | t2 -= d1; | |
332 | } | |
333 | # else /* !BN_LLONG */ | |
334 | BN_ULONG t2l, t2h; | |
335 | ||
336 | q = bn_div_words(n0, n1, d0); | |
0f113f3e MC |
337 | # ifndef REMAINDER_IS_ALREADY_CALCULATED |
338 | rem = (n1 - q * d0) & BN_MASK2; | |
339 | # endif | |
340 | ||
341 | # if defined(BN_UMULT_LOHI) | |
342 | BN_UMULT_LOHI(t2l, t2h, d1, q); | |
343 | # elif defined(BN_UMULT_HIGH) | |
344 | t2l = d1 * q; | |
345 | t2h = BN_UMULT_HIGH(d1, q); | |
346 | # else | |
347 | { | |
348 | BN_ULONG ql, qh; | |
349 | t2l = LBITS(d1); | |
350 | t2h = HBITS(d1); | |
351 | ql = LBITS(q); | |
352 | qh = HBITS(q); | |
353 | mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ | |
354 | } | |
355 | # endif | |
356 | ||
357 | for (;;) { | |
358 | if ((t2h < rem) || ((t2h == rem) && (t2l <= wnump[-2]))) | |
359 | break; | |
360 | q--; | |
361 | rem += d0; | |
362 | if (rem < d0) | |
363 | break; /* don't let rem overflow */ | |
364 | if (t2l < d1) | |
365 | t2h--; | |
366 | t2l -= d1; | |
367 | } | |
368 | # endif /* !BN_LLONG */ | |
369 | } | |
370 | # endif /* !BN_DIV3W */ | |
371 | ||
372 | l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); | |
373 | tmp->d[div_n] = l0; | |
374 | wnum.d--; | |
375 | /* | |
376 | * ingore top values of the bignums just sub the two BN_ULONG arrays | |
377 | * with bn_sub_words | |
378 | */ | |
379 | if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { | |
380 | /* | |
381 | * Note: As we have considered only the leading two BN_ULONGs in | |
382 | * the calculation of q, sdiv * q might be greater than wnum (but | |
383 | * then (q-1) * sdiv is less or equal than wnum) | |
384 | */ | |
385 | q--; | |
386 | if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) | |
387 | /* | |
388 | * we can't have an overflow here (assuming that q != 0, but | |
389 | * if q == 0 then tmp is zero anyway) | |
390 | */ | |
391 | (*wnump)++; | |
392 | } | |
393 | /* store part of the result */ | |
acc60092 | 394 | resp--; |
0f113f3e MC |
395 | *resp = q; |
396 | } | |
397 | bn_correct_top(snum); | |
398 | if (rm != NULL) { | |
399 | /* | |
400 | * Keep a copy of the neg flag in num because if rm==num BN_rshift() | |
401 | * will overwrite it. | |
402 | */ | |
403 | int neg = num->neg; | |
404 | BN_rshift(rm, snum, norm_shift); | |
405 | if (!BN_is_zero(rm)) | |
406 | rm->neg = neg; | |
407 | bn_check_top(rm); | |
408 | } | |
409 | if (no_branch) | |
410 | bn_correct_top(res); | |
411 | BN_CTX_end(ctx); | |
208fb891 | 412 | return 1; |
0f113f3e MC |
413 | err: |
414 | bn_check_top(rm); | |
415 | BN_CTX_end(ctx); | |
26a7d938 | 416 | return 0; |
0f113f3e | 417 | } |
d02b48c6 | 418 | #endif |