source: EcnlProtoTool/trunk/openssl-1.1.0e/crypto/bn/bn_div.c@ 331

Last change on this file since 331 was 331, checked in by coas-nagasima, 6 years ago

prototoolに関連するプロジェクトをnewlibからmuslを使うよう変更・更新
ntshellをnewlibの下位の実装から、muslのsyscallの実装に変更・更新
以下のOSSをアップデート
・mruby-1.3.0
・musl-1.1.18
・onigmo-6.1.3
・tcc-0.9.27
以下のOSSを追加
・openssl-1.1.0e
・curl-7.57.0
・zlib-1.2.11
以下のmrbgemsを追加
・iij/mruby-digest
・iij/mruby-env
・iij/mruby-errno
・iij/mruby-iijson
・iij/mruby-ipaddr
・iij/mruby-mock
・iij/mruby-require
・iij/mruby-tls-openssl
  • Property svn:eol-style set to native
  • Property svn:mime-type set to text/x-csrc
File size: 12.1 KB
Line 
1/*
2 * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
3 *
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
8 */
9
10#include <openssl/bn.h>
11#include "internal/cryptlib.h"
12#include "bn_lcl.h"
13
14/* The old slow way */
15#if 0
16int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
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);
27 return (0);
28 }
29
30 if (BN_ucmp(m, d) < 0) {
31 if (rem != NULL) {
32 if (BN_copy(rem, m) == NULL)
33 return (0);
34 }
35 if (dv != NULL)
36 BN_zero(dv);
37 return (1);
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 }
75/* CAN IMPROVE (and have now :=) */
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;
82 end:
83 BN_CTX_end(ctx);
84 return (ret);
85}
86
87#else
88
89# if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \
90 && !defined(PEDANTIC) && !defined(BN_DIV3W)
91# if defined(__GNUC__) && __GNUC__>=2
92# if defined(__i386) || defined (__i386__)
93 /*-
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:-)
100 *
101 * <appro@fy.chalmers.se>
102 */
103# undef bn_div_words
104# define bn_div_words(n0,n1,d0) \
105 ({ asm volatile ( \
106 "divl %4" \
107 : "=a"(q), "=d"(rem) \
108 : "a"(n1), "d"(n0), "r"(d0) \
109 : "cc"); \
110 q; \
111 })
112# define REMAINDER_IS_ALREADY_CALCULATED
113# elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG)
114 /*
115 * Same story here, but it's 128-bit by 64-bit division. Wow!
116 * <appro@fy.chalmers.se>
117 */
118# undef bn_div_words
119# define bn_div_words(n0,n1,d0) \
120 ({ asm volatile ( \
121 "divq %4" \
122 : "=a"(q), "=d"(rem) \
123 : "a"(n1), "d"(n0), "r"(d0) \
124 : "cc"); \
125 q; \
126 })
127# define REMAINDER_IS_ALREADY_CALCULATED
128# endif /* __<cpu> */
129# endif /* __GNUC__ */
130# endif /* OPENSSL_NO_ASM */
131
132/*-
133 * BN_div computes dv := num / divisor, rounding towards
134 * zero, and sets up rm such that dv*divisor + rm = num holds.
135 * Thus:
136 * dv->neg == num->neg ^ divisor->neg (unless the result is zero)
137 * rm->neg == num->neg (unless the remainder is zero)
138 * If 'dv' or 'rm' is NULL, the respective value is not returned.
139 */
140int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
141 BN_CTX *ctx)
142{
143 int norm_shift, i, loop;
144 BIGNUM *tmp, wnum, *snum, *sdiv, *res;
145 BN_ULONG *resp, *wnump;
146 BN_ULONG d0, d1;
147 int num_n, div_n;
148 int no_branch = 0;
149
150 /*
151 * Invalid zero-padding would have particularly bad consequences so don't
152 * just rely on bn_check_top() here (bn_check_top() works only for
153 * BN_DEBUG builds)
154 */
155 if ((num->top > 0 && num->d[num->top - 1] == 0) ||
156 (divisor->top > 0 && divisor->d[divisor->top - 1] == 0)) {
157 BNerr(BN_F_BN_DIV, BN_R_NOT_INITIALIZED);
158 return 0;
159 }
160
161 bn_check_top(num);
162 bn_check_top(divisor);
163
164 if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0)
165 || (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) {
166 no_branch = 1;
167 }
168
169 bn_check_top(dv);
170 bn_check_top(rm);
171 /*- bn_check_top(num); *//*
172 * 'num' has been checked already
173 */
174 /*- bn_check_top(divisor); *//*
175 * 'divisor' has been checked already
176 */
177
178 if (BN_is_zero(divisor)) {
179 BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO);
180 return (0);
181 }
182
183 if (!no_branch && BN_ucmp(num, divisor) < 0) {
184 if (rm != NULL) {
185 if (BN_copy(rm, num) == NULL)
186 return (0);
187 }
188 if (dv != NULL)
189 BN_zero(dv);
190 return (1);
191 }
192
193 BN_CTX_start(ctx);
194 tmp = BN_CTX_get(ctx);
195 snum = BN_CTX_get(ctx);
196 sdiv = BN_CTX_get(ctx);
197 if (dv == NULL)
198 res = BN_CTX_get(ctx);
199 else
200 res = dv;
201 if (sdiv == NULL || res == NULL || tmp == NULL || snum == NULL)
202 goto err;
203
204 /* First we normalise the numbers */
205 norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2);
206 if (!(BN_lshift(sdiv, divisor, norm_shift)))
207 goto err;
208 sdiv->neg = 0;
209 norm_shift += BN_BITS2;
210 if (!(BN_lshift(snum, num, norm_shift)))
211 goto err;
212 snum->neg = 0;
213
214 if (no_branch) {
215 /*
216 * Since we don't know whether snum is larger than sdiv, we pad snum
217 * with enough zeroes without changing its value.
218 */
219 if (snum->top <= sdiv->top + 1) {
220 if (bn_wexpand(snum, sdiv->top + 2) == NULL)
221 goto err;
222 for (i = snum->top; i < sdiv->top + 2; i++)
223 snum->d[i] = 0;
224 snum->top = sdiv->top + 2;
225 } else {
226 if (bn_wexpand(snum, snum->top + 1) == NULL)
227 goto err;
228 snum->d[snum->top] = 0;
229 snum->top++;
230 }
231 }
232
233 div_n = sdiv->top;
234 num_n = snum->top;
235 loop = num_n - div_n;
236 /*
237 * Lets setup a 'window' into snum This is the part that corresponds to
238 * the current 'area' being divided
239 */
240 wnum.neg = 0;
241 wnum.d = &(snum->d[loop]);
242 wnum.top = div_n;
243 /*
244 * only needed when BN_ucmp messes up the values between top and max
245 */
246 wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */
247
248 /* Get the top 2 words of sdiv */
249 /* div_n=sdiv->top; */
250 d0 = sdiv->d[div_n - 1];
251 d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2];
252
253 /* pointer to the 'top' of snum */
254 wnump = &(snum->d[num_n - 1]);
255
256 /* Setup to 'res' */
257 if (!bn_wexpand(res, (loop + 1)))
258 goto err;
259 res->neg = (num->neg ^ divisor->neg);
260 res->top = loop - no_branch;
261 resp = &(res->d[loop - 1]);
262
263 /* space for temp */
264 if (!bn_wexpand(tmp, (div_n + 1)))
265 goto err;
266
267 if (!no_branch) {
268 if (BN_ucmp(&wnum, sdiv) >= 0) {
269 /*
270 * If BN_DEBUG_RAND is defined BN_ucmp changes (via bn_pollute)
271 * the const bignum arguments => clean the values between top and
272 * max again
273 */
274 bn_clear_top2max(&wnum);
275 bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n);
276 *resp = 1;
277 } else
278 res->top--;
279 }
280
281 /* Increase the resp pointer so that we never create an invalid pointer. */
282 resp++;
283
284 /*
285 * if res->top == 0 then clear the neg value otherwise decrease the resp
286 * pointer
287 */
288 if (res->top == 0)
289 res->neg = 0;
290 else
291 resp--;
292
293 for (i = 0; i < loop - 1; i++, wnump--) {
294 BN_ULONG q, l0;
295 /*
296 * the first part of the loop uses the top two words of snum and sdiv
297 * to calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv
298 */
299# if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM)
300 BN_ULONG bn_div_3_words(BN_ULONG *, BN_ULONG, BN_ULONG);
301 q = bn_div_3_words(wnump, d1, d0);
302# else
303 BN_ULONG n0, n1, rem = 0;
304
305 n0 = wnump[0];
306 n1 = wnump[-1];
307 if (n0 == d0)
308 q = BN_MASK2;
309 else { /* n0 < d0 */
310
311# ifdef BN_LLONG
312 BN_ULLONG t2;
313
314# if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words)
315 q = (BN_ULONG)(((((BN_ULLONG) n0) << BN_BITS2) | n1) / d0);
316# else
317 q = bn_div_words(n0, n1, d0);
318# endif
319
320# ifndef REMAINDER_IS_ALREADY_CALCULATED
321 /*
322 * rem doesn't have to be BN_ULLONG. The least we
323 * know it's less that d0, isn't it?
324 */
325 rem = (n1 - q * d0) & BN_MASK2;
326# endif
327 t2 = (BN_ULLONG) d1 *q;
328
329 for (;;) {
330 if (t2 <= ((((BN_ULLONG) rem) << BN_BITS2) | wnump[-2]))
331 break;
332 q--;
333 rem += d0;
334 if (rem < d0)
335 break; /* don't let rem overflow */
336 t2 -= d1;
337 }
338# else /* !BN_LLONG */
339 BN_ULONG t2l, t2h;
340
341 q = bn_div_words(n0, n1, d0);
342# ifndef REMAINDER_IS_ALREADY_CALCULATED
343 rem = (n1 - q * d0) & BN_MASK2;
344# endif
345
346# if defined(BN_UMULT_LOHI)
347 BN_UMULT_LOHI(t2l, t2h, d1, q);
348# elif defined(BN_UMULT_HIGH)
349 t2l = d1 * q;
350 t2h = BN_UMULT_HIGH(d1, q);
351# else
352 {
353 BN_ULONG ql, qh;
354 t2l = LBITS(d1);
355 t2h = HBITS(d1);
356 ql = LBITS(q);
357 qh = HBITS(q);
358 mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */
359 }
360# endif
361
362 for (;;) {
363 if ((t2h < rem) || ((t2h == rem) && (t2l <= wnump[-2])))
364 break;
365 q--;
366 rem += d0;
367 if (rem < d0)
368 break; /* don't let rem overflow */
369 if (t2l < d1)
370 t2h--;
371 t2l -= d1;
372 }
373# endif /* !BN_LLONG */
374 }
375# endif /* !BN_DIV3W */
376
377 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q);
378 tmp->d[div_n] = l0;
379 wnum.d--;
380 /*
381 * ingore top values of the bignums just sub the two BN_ULONG arrays
382 * with bn_sub_words
383 */
384 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) {
385 /*
386 * Note: As we have considered only the leading two BN_ULONGs in
387 * the calculation of q, sdiv * q might be greater than wnum (but
388 * then (q-1) * sdiv is less or equal than wnum)
389 */
390 q--;
391 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n))
392 /*
393 * we can't have an overflow here (assuming that q != 0, but
394 * if q == 0 then tmp is zero anyway)
395 */
396 (*wnump)++;
397 }
398 /* store part of the result */
399 resp--;
400 *resp = q;
401 }
402 bn_correct_top(snum);
403 if (rm != NULL) {
404 /*
405 * Keep a copy of the neg flag in num because if rm==num BN_rshift()
406 * will overwrite it.
407 */
408 int neg = num->neg;
409 BN_rshift(rm, snum, norm_shift);
410 if (!BN_is_zero(rm))
411 rm->neg = neg;
412 bn_check_top(rm);
413 }
414 if (no_branch)
415 bn_correct_top(res);
416 BN_CTX_end(ctx);
417 return (1);
418 err:
419 bn_check_top(rm);
420 BN_CTX_end(ctx);
421 return (0);
422}
423#endif
Note: See TracBrowser for help on using the repository browser.