summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_div.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_div.c')
-rw-r--r--src/lib/libcrypto/bn/bn_div.c381
1 files changed, 0 insertions, 381 deletions
diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c
deleted file mode 100644
index fefc53f9fa..0000000000
--- a/src/lib/libcrypto/bn/bn_div.c
+++ /dev/null
@@ -1,381 +0,0 @@
1/* $OpenBSD: bn_div.c,v 1.23 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#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 */
119int
120BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
121 BN_CTX *ctx)
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) {
134 BNerr(BN_F_BN_DIV, BN_R_NOT_INITIALIZED);
135 return 0;
136 }
137
138 bn_check_top(num);
139
140 if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) ||
141 (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) {
142 no_branch = 1;
143 }
144
145 bn_check_top(dv);
146 bn_check_top(rm);
147 /* bn_check_top(num); */ /* 'num' has been checked already */
148 bn_check_top(divisor);
149
150 if (BN_is_zero(divisor)) {
151 BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO);
152 return (0);
153 }
154
155 if (!no_branch && BN_ucmp(num, divisor) < 0) {
156 if (rm != NULL) {
157 if (BN_copy(rm, num) == NULL)
158 return (0);
159 }
160 if (dv != NULL)
161 BN_zero(dv);
162 return (1);
163 }
164
165 BN_CTX_start(ctx);
166 tmp = BN_CTX_get(ctx);
167 snum = BN_CTX_get(ctx);
168 sdiv = BN_CTX_get(ctx);
169 if (dv == NULL)
170 res = BN_CTX_get(ctx);
171 else
172 res = dv;
173 if (tmp == NULL || snum == NULL || sdiv == NULL || res == NULL)
174 goto err;
175
176 /* First we normalise the numbers */
177 norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2);
178 if (!(BN_lshift(sdiv, divisor, norm_shift)))
179 goto err;
180 sdiv->neg = 0;
181 norm_shift += BN_BITS2;
182 if (!(BN_lshift(snum, num, norm_shift)))
183 goto err;
184 snum->neg = 0;
185
186 if (no_branch) {
187 /* Since we don't know whether snum is larger than sdiv,
188 * we pad snum with enough zeroes without changing its
189 * value.
190 */
191 if (snum->top <= sdiv->top + 1) {
192 if (bn_wexpand(snum, sdiv->top + 2) == NULL)
193 goto err;
194 for (i = snum->top; i < sdiv->top + 2; i++)
195 snum->d[i] = 0;
196 snum->top = sdiv->top + 2;
197 } else {
198 if (bn_wexpand(snum, snum->top + 1) == NULL)
199 goto err;
200 snum->d[snum->top] = 0;
201 snum->top ++;
202 }
203 }
204
205 div_n = sdiv->top;
206 num_n = snum->top;
207 loop = num_n - div_n;
208 /* Lets setup a 'window' into snum
209 * This is the part that corresponds to the current
210 * 'area' being divided */
211 wnum.neg = 0;
212 wnum.d = &(snum->d[loop]);
213 wnum.top = div_n;
214 /* only needed when BN_ucmp messes up the values between top and max */
215 wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */
216 wnum.flags = snum->flags | BN_FLG_STATIC_DATA;
217
218 /* Get the top 2 words of sdiv */
219 /* div_n=sdiv->top; */
220 d0 = sdiv->d[div_n - 1];
221 d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2];
222
223 /* pointer to the 'top' of snum */
224 wnump = &(snum->d[num_n - 1]);
225
226 /* Setup to 'res' */
227 res->neg = (num->neg ^ divisor->neg);
228 if (!bn_wexpand(res, (loop + 1)))
229 goto err;
230 res->top = loop - no_branch;
231 resp = &(res->d[loop - 1]);
232
233 /* space for temp */
234 if (!bn_wexpand(tmp, (div_n + 1)))
235 goto err;
236
237 if (!no_branch) {
238 if (BN_ucmp(&wnum, sdiv) >= 0) {
239 /* If BN_DEBUG_RAND is defined BN_ucmp changes (via
240 * bn_pollute) the const bignum arguments =>
241 * clean the values between top and max again */
242 bn_clear_top2max(&wnum);
243 bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n);
244 *resp = 1;
245 } else
246 res->top--;
247 }
248
249 /* if res->top == 0 then clear the neg value otherwise decrease
250 * the resp pointer */
251 if (res->top == 0)
252 res->neg = 0;
253 else
254 resp--;
255
256 for (i = 0; i < loop - 1; i++, wnump--, resp--) {
257 BN_ULONG q, l0;
258 /* the first part of the loop uses the top two words of
259 * snum and sdiv to calculate a BN_ULONG q such that
260 * | wnum - sdiv * q | < sdiv */
261#if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM)
262 BN_ULONG bn_div_3_words(BN_ULONG*, BN_ULONG, BN_ULONG);
263 q = bn_div_3_words(wnump, d1, d0);
264#else
265 BN_ULONG n0, n1, rem = 0;
266
267 n0 = wnump[0];
268 n1 = wnump[-1];
269 if (n0 == d0)
270 q = BN_MASK2;
271 else /* n0 < d0 */
272 {
273#ifdef BN_LLONG
274 BN_ULLONG t2;
275
276#if defined(BN_DIV2W) && !defined(bn_div_words)
277 q = (BN_ULONG)(((((BN_ULLONG)n0) << BN_BITS2)|n1)/d0);
278#else
279 q = bn_div_words(n0, n1, d0);
280#endif
281
282#ifndef REMAINDER_IS_ALREADY_CALCULATED
283 /*
284 * rem doesn't have to be BN_ULLONG. The least we
285 * know it's less that d0, isn't it?
286 */
287 rem = (n1 - q * d0) & BN_MASK2;
288#endif
289 t2 = (BN_ULLONG)d1*q;
290
291 for (;;) {
292 if (t2 <= ((((BN_ULLONG)rem) << BN_BITS2) |
293 wnump[-2]))
294 break;
295 q--;
296 rem += d0;
297 if (rem < d0) break; /* don't let rem overflow */
298 t2 -= d1;
299 }
300#else /* !BN_LLONG */
301 BN_ULONG t2l, t2h;
302
303 q = bn_div_words(n0, n1, d0);
304#ifndef REMAINDER_IS_ALREADY_CALCULATED
305 rem = (n1 - q*d0)&BN_MASK2;
306#endif
307
308#if defined(BN_UMULT_LOHI)
309 BN_UMULT_LOHI(t2l, t2h, d1, q);
310#elif defined(BN_UMULT_HIGH)
311 t2l = d1 * q;
312 t2h = BN_UMULT_HIGH(d1, q);
313#else
314 {
315 BN_ULONG ql, qh;
316 t2l = LBITS(d1);
317 t2h = HBITS(d1);
318 ql = LBITS(q);
319 qh = HBITS(q);
320 mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */
321 }
322#endif
323
324 for (;;) {
325 if ((t2h < rem) ||
326 ((t2h == rem) && (t2l <= wnump[-2])))
327 break;
328 q--;
329 rem += d0;
330 if (rem < d0)
331 break; /* don't let rem overflow */
332 if (t2l < d1)
333 t2h--;
334 t2l -= d1;
335 }
336#endif /* !BN_LLONG */
337 }
338#endif /* !BN_DIV3W */
339
340 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q);
341 tmp->d[div_n] = l0;
342 wnum.d--;
343 /* ingore top values of the bignums just sub the two
344 * BN_ULONG arrays with bn_sub_words */
345 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) {
346 /* Note: As we have considered only the leading
347 * two BN_ULONGs in the calculation of q, sdiv * q
348 * might be greater than wnum (but then (q-1) * sdiv
349 * is less or equal than wnum)
350 */
351 q--;
352 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n))
353 /* we can't have an overflow here (assuming
354 * that q != 0, but if q == 0 then tmp is
355 * zero anyway) */
356 (*wnump)++;
357 }
358 /* store part of the result */
359 *resp = q;
360 }
361 bn_correct_top(snum);
362 if (rm != NULL) {
363 /* Keep a copy of the neg flag in num because if rm==num
364 * BN_rshift() will overwrite it.
365 */
366 int neg = num->neg;
367 BN_rshift(rm, snum, norm_shift);
368 if (!BN_is_zero(rm))
369 rm->neg = neg;
370 bn_check_top(rm);
371 }
372 if (no_branch)
373 bn_correct_top(res);
374 BN_CTX_end(ctx);
375 return (1);
376
377err:
378 bn_check_top(rm);
379 BN_CTX_end(ctx);
380 return (0);
381}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-05-08 07:38:05 +0000