1 | #include "../oscam-config.h"
|
---|
2 | #ifndef WITH_LIBCRYPTO
|
---|
3 | //FIXME Not checked on threadsafety yet; after checking please remove this line
|
---|
4 | /* crypto/bn/bn_div.c */
|
---|
5 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
|
---|
6 | * All rights reserved.
|
---|
7 | *
|
---|
8 | * This package is an SSL implementation written
|
---|
9 | * by Eric Young (eay@cryptsoft.com).
|
---|
10 | * The implementation was written so as to conform with Netscapes SSL.
|
---|
11 | *
|
---|
12 | * This library is free for commercial and non-commercial use as long as
|
---|
13 | * the following conditions are aheared to. The following conditions
|
---|
14 | * apply to all code found in this distribution, be it the RC4, RSA,
|
---|
15 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation
|
---|
16 | * included with this distribution is covered by the same copyright terms
|
---|
17 | * except that the holder is Tim Hudson (tjh@cryptsoft.com).
|
---|
18 | *
|
---|
19 | * Copyright remains Eric Young's, and as such any Copyright notices in
|
---|
20 | * the code are not to be removed.
|
---|
21 | * If this package is used in a product, Eric Young should be given attribution
|
---|
22 | * as the author of the parts of the library used.
|
---|
23 | * This can be in the form of a textual message at program startup or
|
---|
24 | * in documentation (online or textual) provided with the package.
|
---|
25 | *
|
---|
26 | * Redistribution and use in source and binary forms, with or without
|
---|
27 | * modification, are permitted provided that the following conditions
|
---|
28 | * are met:
|
---|
29 | * 1. Redistributions of source code must retain the copyright
|
---|
30 | * notice, this list of conditions and the following disclaimer.
|
---|
31 | * 2. Redistributions in binary form must reproduce the above copyright
|
---|
32 | * notice, this list of conditions and the following disclaimer in the
|
---|
33 | * documentation and/or other materials provided with the distribution.
|
---|
34 | * 3. All advertising materials mentioning features or use of this software
|
---|
35 | * must display the following acknowledgement:
|
---|
36 | * "This product includes cryptographic software written by
|
---|
37 | * Eric Young (eay@cryptsoft.com)"
|
---|
38 | * The word 'cryptographic' can be left out if the rouines from the library
|
---|
39 | * being used are not cryptographic related :-).
|
---|
40 | * 4. If you include any Windows specific code (or a derivative thereof) from
|
---|
41 | * the apps directory (application code) you must include an acknowledgement:
|
---|
42 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
|
---|
43 | *
|
---|
44 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
|
---|
45 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
---|
46 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
---|
47 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
|
---|
48 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
---|
49 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
|
---|
50 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
---|
51 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
---|
52 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
|
---|
53 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
---|
54 | * SUCH DAMAGE.
|
---|
55 | *
|
---|
56 | * The licence and distribution terms for any publically available version or
|
---|
57 | * derivative of this code cannot be changed. i.e. this code cannot simply be
|
---|
58 | * copied and put under another distribution licence
|
---|
59 | * [including the GNU Public Licence.]
|
---|
60 | */
|
---|
61 |
|
---|
62 | #include <stdio.h>
|
---|
63 | #include "openssl_mods.h"
|
---|
64 | #include "bn_lcl.h"
|
---|
65 |
|
---|
66 | /* The old slow way */
|
---|
67 | #if 0
|
---|
68 | int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
|
---|
69 | BN_CTX *ctx)
|
---|
70 | {
|
---|
71 | int i,nm,nd;
|
---|
72 | int ret = 0;
|
---|
73 | BIGNUM *D;
|
---|
74 |
|
---|
75 | bn_check_top(m);
|
---|
76 | bn_check_top(d);
|
---|
77 | if (BN_is_zero(d))
|
---|
78 | {
|
---|
79 | return(0);
|
---|
80 | }
|
---|
81 |
|
---|
82 | if (BN_ucmp(m,d) < 0)
|
---|
83 | {
|
---|
84 | if (rem != NULL)
|
---|
85 | { if (BN_copy(rem,m) == NULL) return(0); }
|
---|
86 | if (dv != NULL) BN_zero(dv);
|
---|
87 | return(1);
|
---|
88 | }
|
---|
89 |
|
---|
90 | BN_CTX_start(ctx);
|
---|
91 | D = BN_CTX_get(ctx);
|
---|
92 | if (dv == NULL) dv = BN_CTX_get(ctx);
|
---|
93 | if (rem == NULL) rem = BN_CTX_get(ctx);
|
---|
94 | if (D == NULL || dv == NULL || rem == NULL)
|
---|
95 | goto end;
|
---|
96 |
|
---|
97 | nd=BN_num_bits(d);
|
---|
98 | nm=BN_num_bits(m);
|
---|
99 | if (BN_copy(D,d) == NULL) goto end;
|
---|
100 | if (BN_copy(rem,m) == NULL) goto end;
|
---|
101 |
|
---|
102 | /* The next 2 are needed so we can do a dv->d[0]|=1 later
|
---|
103 | * since BN_lshift1 will only work once there is a value :-) */
|
---|
104 | BN_zero(dv);
|
---|
105 | bn_wexpand(dv,1);
|
---|
106 | dv->top=1;
|
---|
107 |
|
---|
108 | if (!BN_lshift(D,D,nm-nd)) goto end;
|
---|
109 | for (i=nm-nd; i>=0; i--)
|
---|
110 | {
|
---|
111 | if (!BN_lshift1(dv,dv)) goto end;
|
---|
112 | if (BN_ucmp(rem,D) >= 0)
|
---|
113 | {
|
---|
114 | dv->d[0]|=1;
|
---|
115 | if (!BN_usub(rem,rem,D)) goto end;
|
---|
116 | }
|
---|
117 | /* CAN IMPROVE (and have now :=) */
|
---|
118 | if (!BN_rshift1(D,D)) goto end;
|
---|
119 | }
|
---|
120 | rem->neg=BN_is_zero(rem)?0:m->neg;
|
---|
121 | dv->neg=m->neg^d->neg;
|
---|
122 | ret = 1;
|
---|
123 | end:
|
---|
124 | BN_CTX_end(ctx);
|
---|
125 | return(ret);
|
---|
126 | }
|
---|
127 |
|
---|
128 | #else
|
---|
129 |
|
---|
130 | #if !defined(NO_ASM) && !defined(NO_INLINE_ASM) && !defined(PEDANTIC) && !defined(BN_DIV3W)
|
---|
131 | # if defined(__GNUC__) && __GNUC__>=2
|
---|
132 | # if defined(__i386) || defined (__i386__)
|
---|
133 | /*
|
---|
134 | * There were two reasons for implementing this template:
|
---|
135 | * - GNU C generates a call to a function (__udivdi3 to be exact)
|
---|
136 | * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to
|
---|
137 | * understand why...);
|
---|
138 | * - divl doesn't only calculate quotient, but also leaves
|
---|
139 | * remainder in %edx which we can definitely use here:-)
|
---|
140 | *
|
---|
141 | * <appro@fy.chalmers.se>
|
---|
142 | */
|
---|
143 | # define bn_div_words(n0,n1,d0) \
|
---|
144 | ({ asm volatile ( \
|
---|
145 | "divl %4" \
|
---|
146 | : "=a"(q), "=d"(rem) \
|
---|
147 | : "a"(n1), "d"(n0), "g"(d0) \
|
---|
148 | : "cc"); \
|
---|
149 | q; \
|
---|
150 | })
|
---|
151 | # define REMAINDER_IS_ALREADY_CALCULATED
|
---|
152 | # endif /* __<cpu> */
|
---|
153 | # endif /* __GNUC__ */
|
---|
154 | #endif /* NO_ASM */
|
---|
155 |
|
---|
156 | int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
|
---|
157 | BN_CTX *ctx)
|
---|
158 | {
|
---|
159 | int norm_shift,i,j,loop;
|
---|
160 | BIGNUM *tmp,wnum,*snum,*sdiv,*res;
|
---|
161 | BN_ULONG *resp,*wnump;
|
---|
162 | BN_ULONG d0,d1;
|
---|
163 | int num_n,div_n;
|
---|
164 |
|
---|
165 | bn_check_top(num);
|
---|
166 | bn_check_top(divisor);
|
---|
167 |
|
---|
168 | if (BN_is_zero(divisor))
|
---|
169 | {
|
---|
170 | return(0);
|
---|
171 | }
|
---|
172 |
|
---|
173 | if (BN_ucmp(num,divisor) < 0)
|
---|
174 | {
|
---|
175 | if (rm != NULL)
|
---|
176 | { if (BN_copy(rm,num) == NULL) return(0); }
|
---|
177 | if (dv != NULL) BN_zero(dv);
|
---|
178 | return(1);
|
---|
179 | }
|
---|
180 |
|
---|
181 | BN_CTX_start(ctx);
|
---|
182 | tmp=BN_CTX_get(ctx);
|
---|
183 | snum=BN_CTX_get(ctx);
|
---|
184 | sdiv=BN_CTX_get(ctx);
|
---|
185 | if (dv == NULL)
|
---|
186 | res=BN_CTX_get(ctx);
|
---|
187 | else res=dv;
|
---|
188 | if (sdiv==NULL || res == NULL) goto err;
|
---|
189 | tmp->neg=0;
|
---|
190 |
|
---|
191 | /* First we normalise the numbers */
|
---|
192 | norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
|
---|
193 | BN_lshift(sdiv,divisor,norm_shift);
|
---|
194 | sdiv->neg=0;
|
---|
195 | norm_shift+=BN_BITS2;
|
---|
196 | BN_lshift(snum,num,norm_shift);
|
---|
197 | snum->neg=0;
|
---|
198 | div_n=sdiv->top;
|
---|
199 | num_n=snum->top;
|
---|
200 | loop=num_n-div_n;
|
---|
201 |
|
---|
202 | /* Lets setup a 'window' into snum
|
---|
203 | * This is the part that corresponds to the current
|
---|
204 | * 'area' being divided */
|
---|
205 | BN_init(&wnum);
|
---|
206 | wnum.d= &(snum->d[loop]);
|
---|
207 | wnum.top= div_n;
|
---|
208 | wnum.dmax= snum->dmax+1; /* a bit of a lie */
|
---|
209 |
|
---|
210 | /* Get the top 2 words of sdiv */
|
---|
211 | /* i=sdiv->top; */
|
---|
212 | d0=sdiv->d[div_n-1];
|
---|
213 | d1=(div_n == 1)?0:sdiv->d[div_n-2];
|
---|
214 |
|
---|
215 | /* pointer to the 'top' of snum */
|
---|
216 | wnump= &(snum->d[num_n-1]);
|
---|
217 |
|
---|
218 | /* Setup to 'res' */
|
---|
219 | res->neg= (num->neg^divisor->neg);
|
---|
220 | if (!bn_wexpand(res,(loop+1))) goto err;
|
---|
221 | res->top=loop;
|
---|
222 | resp= &(res->d[loop-1]);
|
---|
223 |
|
---|
224 | /* space for temp */
|
---|
225 | if (!bn_wexpand(tmp,(div_n+1))) goto err;
|
---|
226 |
|
---|
227 | if (BN_ucmp(&wnum,sdiv) >= 0)
|
---|
228 | {
|
---|
229 | if (!BN_usub(&wnum,&wnum,sdiv)) goto err;
|
---|
230 | *resp=1;
|
---|
231 | res->d[res->top-1]=1;
|
---|
232 | }
|
---|
233 | else
|
---|
234 | res->top--;
|
---|
235 | resp--;
|
---|
236 |
|
---|
237 | for (i=0; i<loop-1; i++)
|
---|
238 | {
|
---|
239 | BN_ULONG q,l0;
|
---|
240 | #if defined(BN_DIV3W) && !defined(NO_ASM)
|
---|
241 | BN_ULONG bn_div_3_words(BN_ULONG*,BN_ULONG,BN_ULONG);
|
---|
242 | q=bn_div_3_words(wnump,d1,d0);
|
---|
243 | #else
|
---|
244 | BN_ULONG n0,n1,rem=0;
|
---|
245 |
|
---|
246 | n0=wnump[0];
|
---|
247 | n1=wnump[-1];
|
---|
248 | if (n0 == d0)
|
---|
249 | q=BN_MASK2;
|
---|
250 | else /* n0 < d0 */
|
---|
251 | {
|
---|
252 | #ifdef BN_LLONG
|
---|
253 | BN_ULLONG t2;
|
---|
254 |
|
---|
255 | #if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words)
|
---|
256 | q=(BN_ULONG)(((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0);
|
---|
257 | #else
|
---|
258 | q=bn_div_words(n0,n1,d0);
|
---|
259 | #endif
|
---|
260 |
|
---|
261 | #ifndef REMAINDER_IS_ALREADY_CALCULATED
|
---|
262 | /*
|
---|
263 | * rem doesn't have to be BN_ULLONG. The least we
|
---|
264 | * know it's less that d0, isn't it?
|
---|
265 | */
|
---|
266 | rem=(n1-q*d0)&BN_MASK2;
|
---|
267 | #endif
|
---|
268 | t2=(BN_ULLONG)d1*q;
|
---|
269 |
|
---|
270 | for (;;)
|
---|
271 | {
|
---|
272 | if (t2 <= ((((BN_ULLONG)rem)<<BN_BITS2)|wnump[-2]))
|
---|
273 | break;
|
---|
274 | q--;
|
---|
275 | rem += d0;
|
---|
276 | if (rem < d0) break; /* don't let rem overflow */
|
---|
277 | t2 -= d1;
|
---|
278 | }
|
---|
279 | #else /* !BN_LLONG */
|
---|
280 | BN_ULONG t2l,t2h,ql,qh;
|
---|
281 |
|
---|
282 | q=bn_div_words(n0,n1,d0);
|
---|
283 | #ifndef REMAINDER_IS_ALREADY_CALCULATED
|
---|
284 | rem=(n1-q*d0)&BN_MASK2;
|
---|
285 | #endif
|
---|
286 |
|
---|
287 | #ifdef BN_UMULT_HIGH
|
---|
288 | t2l = d1 * q;
|
---|
289 | t2h = BN_UMULT_HIGH(d1,q);
|
---|
290 | #else
|
---|
291 | t2l=LBITS(d1); t2h=HBITS(d1);
|
---|
292 | ql =LBITS(q); qh =HBITS(q);
|
---|
293 | mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */
|
---|
294 | #endif
|
---|
295 |
|
---|
296 | for (;;)
|
---|
297 | {
|
---|
298 | if ((t2h < rem) ||
|
---|
299 | ((t2h == rem) && (t2l <= wnump[-2])))
|
---|
300 | break;
|
---|
301 | q--;
|
---|
302 | rem += d0;
|
---|
303 | if (rem < d0) break; /* don't let rem overflow */
|
---|
304 | if (t2l < d1) t2h--; t2l -= d1;
|
---|
305 | }
|
---|
306 | #endif /* !BN_LLONG */
|
---|
307 | }
|
---|
308 | #endif /* !BN_DIV3W */
|
---|
309 |
|
---|
310 | l0=bn_mul_words(tmp->d,sdiv->d,div_n,q);
|
---|
311 | wnum.d--; wnum.top++;
|
---|
312 | tmp->d[div_n]=l0;
|
---|
313 | for (j=div_n+1; j>0; j--)
|
---|
314 | if (tmp->d[j-1]) break;
|
---|
315 | tmp->top=j;
|
---|
316 |
|
---|
317 | j=wnum.top;
|
---|
318 | BN_sub(&wnum,&wnum,tmp);
|
---|
319 |
|
---|
320 | snum->top=snum->top+wnum.top-j;
|
---|
321 |
|
---|
322 | if (wnum.neg)
|
---|
323 | {
|
---|
324 | q--;
|
---|
325 | j=wnum.top;
|
---|
326 | BN_add(&wnum,&wnum,sdiv);
|
---|
327 | snum->top+=wnum.top-j;
|
---|
328 | }
|
---|
329 | *(resp--)=q;
|
---|
330 | wnump--;
|
---|
331 | }
|
---|
332 | if (rm != NULL)
|
---|
333 | {
|
---|
334 | BN_rshift(rm,snum,norm_shift);
|
---|
335 | rm->neg=num->neg;
|
---|
336 | }
|
---|
337 | BN_CTX_end(ctx);
|
---|
338 | return(1);
|
---|
339 | err:
|
---|
340 | BN_CTX_end(ctx);
|
---|
341 | return(0);
|
---|
342 | }
|
---|
343 |
|
---|
344 | #endif
|
---|
345 |
|
---|
346 | /* rem != m */
|
---|
347 | int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
|
---|
348 | {
|
---|
349 | #if 0 /* The old slow way */
|
---|
350 | int i,nm,nd;
|
---|
351 | BIGNUM *dv;
|
---|
352 |
|
---|
353 | if (BN_ucmp(m,d) < 0)
|
---|
354 | return((BN_copy(rem,m) == NULL)?0:1);
|
---|
355 |
|
---|
356 | BN_CTX_start(ctx);
|
---|
357 | dv=BN_CTX_get(ctx);
|
---|
358 |
|
---|
359 | if (!BN_copy(rem,m)) goto err;
|
---|
360 |
|
---|
361 | nm=BN_num_bits(rem);
|
---|
362 | nd=BN_num_bits(d);
|
---|
363 | if (!BN_lshift(dv,d,nm-nd)) goto err;
|
---|
364 | for (i=nm-nd; i>=0; i--)
|
---|
365 | {
|
---|
366 | if (BN_cmp(rem,dv) >= 0)
|
---|
367 | {
|
---|
368 | if (!BN_sub(rem,rem,dv)) goto err;
|
---|
369 | }
|
---|
370 | if (!BN_rshift1(dv,dv)) goto err;
|
---|
371 | }
|
---|
372 | BN_CTX_end(ctx);
|
---|
373 | return(1);
|
---|
374 | err:
|
---|
375 | BN_CTX_end(ctx);
|
---|
376 | return(0);
|
---|
377 | #else
|
---|
378 | return(BN_div(NULL,rem,m,d,ctx));
|
---|
379 | #endif
|
---|
380 | }
|
---|
381 |
|
---|
382 | #endif
|
---|