← Back to branch summary

~ubuntu-branches/ubuntu/dapper/rdesktop/dapper

« back to all changes in this revision

Viewing changes to crypto/bn_div.c

  • Committer: Bazaar Package Importer
  • Author(s): Sam Johnston
  • Date: 2004-02-04 17:52:26 UTC
  • Revision ID: james.westby@ubuntu.com-20040204175226-87kz4bzs1nimji68
Tags: upstream-1.3.1
Import upstream version 1.3.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
crypto/bn_div.c
 
1
/* crypto/bn/bn_div.c */
 
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
#include "bn.h"
 
61
#include "bn_lcl.h"
 
62
 
 
63
/* The old slow way */
 
64
#if 0
 
65
int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
 
66
           BN_CTX *ctx)
 
67
        {
 
68
        int i,nm,nd;
 
69
        int ret = 0;
 
70
        BIGNUM *D;
 
71
 
 
72
        bn_check_top(m);
 
73
        bn_check_top(d);
 
74
        if (BN_is_zero(d))
 
75
                {
 
76
                BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
 
77
                return(0);
 
78
                }
 
79
 
 
80
        if (BN_ucmp(m,d) < 0)
 
81
                {
 
82
                if (rem != NULL)
 
83
                        { if (BN_copy(rem,m) == NULL) return(0); }
 
84
                if (dv != NULL) BN_zero(dv);
 
85
                return(1);
 
86
                }
 
87
 
 
88
        BN_CTX_start(ctx);
 
89
        D = BN_CTX_get(ctx);
 
90
        if (dv == NULL) dv = BN_CTX_get(ctx);
 
91
        if (rem == NULL) rem = BN_CTX_get(ctx);
 
92
        if (D == NULL || dv == NULL || rem == NULL)
 
93
                goto end;
 
94
 
 
95
        nd=BN_num_bits(d);
 
96
        nm=BN_num_bits(m);
 
97
        if (BN_copy(D,d) == NULL) goto end;
 
98
        if (BN_copy(rem,m) == NULL) goto end;
 
99
 
 
100
        /* The next 2 are needed so we can do a dv->d[0]|=1 later
 
101
         * since BN_lshift1 will only work once there is a value :-) */
 
102
        BN_zero(dv);
 
103
        bn_wexpand(dv,1);
 
104
        dv->top=1;
 
105
 
 
106
        if (!BN_lshift(D,D,nm-nd)) goto end;
 
107
        for (i=nm-nd; i>=0; i--)
 
108
                {
 
109
                if (!BN_lshift1(dv,dv)) goto end;
 
110
                if (BN_ucmp(rem,D) >= 0)
 
111
                        {
 
112
                        dv->d[0]|=1;
 
113
                        if (!BN_usub(rem,rem,D)) goto end;
 
114
                        }
 
115
/* CAN IMPROVE (and have now :=) */
 
116
                if (!BN_rshift1(D,D)) goto end;
 
117
                }
 
118
        rem->neg=BN_is_zero(rem)?0:m->neg;
 
119
        dv->neg=m->neg^d->neg;
 
120
        ret = 1;
 
121
 end:
 
122
        BN_CTX_end(ctx);
 
123
        return(ret);
 
124
        }
 
125
 
 
126
#else
 
127
 
 
128
#if !defined(NO_ASM) && !defined(NO_INLINE_ASM) && !defined(PEDANTIC) && !defined(BN_DIV3W)
 
129
# if defined(__GNUC__) && __GNUC__>=2
 
130
#  if defined(__i386) || defined (__i386__)
 
131
   /*
 
132
    * There were two reasons for implementing this template:
 
133
    * - GNU C generates a call to a function (__udivdi3 to be exact)
 
134
    *   in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to
 
135
    *   understand why...);
 
136
    * - divl doesn't only calculate quotient, but also leaves
 
137
    *   remainder in %edx which we can definitely use here:-)
 
138
    *
 
139
    *                                   <appro@fy.chalmers.se>
 
140
    */
 
141
#  define bn_div_words(n0,n1,d0)                \
 
142
        ({  asm volatile (                      \
 
143
                "divl   %4"                     \
 
144
                : "=a"(q), "=d"(rem)            \
 
145
                : "a"(n1), "d"(n0), "g"(d0)     \
 
146
                : "cc");                        \
 
147
            q;                                  \
 
148
        })
 
149
#  define REMAINDER_IS_ALREADY_CALCULATED
 
150
#  endif /* __<cpu> */
 
151
# endif /* __GNUC__ */
 
152
#endif /* NO_ASM */
 
153
 
 
154
int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
 
155
           BN_CTX *ctx)
 
156
        {
 
157
        int norm_shift,i,j,loop;
 
158
        BIGNUM *tmp,wnum,*snum,*sdiv,*res;
 
159
        BN_ULONG *resp,*wnump;
 
160
        BN_ULONG d0,d1;
 
161
        int num_n,div_n;
 
162
 
 
163
        bn_check_top(num);
 
164
        bn_check_top(divisor);
 
165
 
 
166
        if (BN_is_zero(divisor))
 
167
                {
 
168
                BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
 
169
                return(0);
 
170
                }
 
171
 
 
172
        if (BN_ucmp(num,divisor) < 0)
 
173
                {
 
174
                if (rm != NULL)
 
175
                        { if (BN_copy(rm,num) == NULL) return(0); }
 
176
                if (dv != NULL) BN_zero(dv);
 
177
                return(1);
 
178
                }
 
179
 
 
180
        BN_CTX_start(ctx);
 
181
        tmp=BN_CTX_get(ctx);
 
182
        snum=BN_CTX_get(ctx);
 
183
        sdiv=BN_CTX_get(ctx);
 
184
        if (dv == NULL)
 
185
                res=BN_CTX_get(ctx);
 
186
        else    res=dv;
 
187
        if (sdiv==NULL || res == NULL) goto err;
 
188
        tmp->neg=0;
 
189
 
 
190
        /* First we normalise the numbers */
 
191
        norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
 
192
        if (!(BN_lshift(sdiv,divisor,norm_shift))) goto err;
 
193
        sdiv->neg=0;
 
194
        norm_shift+=BN_BITS2;
 
195
        if (!(BN_lshift(snum,num,norm_shift))) goto err;
 
196
        snum->neg=0;
 
197
        div_n=sdiv->top;
 
198
        num_n=snum->top;
 
199
        loop=num_n-div_n;
 
200
 
 
201
        /* Lets setup a 'window' into snum
 
202
         * This is the part that corresponds to the current
 
203
         * 'area' being divided */
 
204
        BN_init(&wnum);
 
205
        wnum.d=  &(snum->d[loop]);
 
206
        wnum.top= div_n;
 
207
        wnum.dmax= snum->dmax+1; /* a bit of a lie */
 
208
 
 
209
        /* Get the top 2 words of sdiv */
 
210
        /* i=sdiv->top; */
 
211
        d0=sdiv->d[div_n-1];
 
212
        d1=(div_n == 1)?0:sdiv->d[div_n-2];
 
213
 
 
214
        /* pointer to the 'top' of snum */
 
215
        wnump= &(snum->d[num_n-1]);
 
216
 
 
217
        /* Setup to 'res' */
 
218
        res->neg= (num->neg^divisor->neg);
 
219
        if (!bn_wexpand(res,(loop+1))) goto err;
 
220
        res->top=loop;
 
221
        resp= &(res->d[loop-1]);
 
222
 
 
223
        /* space for temp */
 
224
        if (!bn_wexpand(tmp,(div_n+1))) goto err;
 
225
 
 
226
        if (BN_ucmp(&wnum,sdiv) >= 0)
 
227
                {
 
228
                if (!BN_usub(&wnum,&wnum,sdiv)) goto err;
 
229
                *resp=1;
 
230
                res->d[res->top-1]=1;
 
231
                }
 
232
        else
 
233
                res->top--;
 
234
        resp--;
 
235
 
 
236
        for (i=0; i<loop-1; i++)
 
237
                {
 
238
                BN_ULONG q,l0;
 
239
#if defined(BN_DIV3W) && !defined(NO_ASM)
 
240
                BN_ULONG bn_div_3_words(BN_ULONG*,BN_ULONG,BN_ULONG);
 
241
                q=bn_div_3_words(wnump,d1,d0);
 
242
#else
 
243
                BN_ULONG n0,n1,rem=0;
 
244
 
 
245
                n0=wnump[0];
 
246
                n1=wnump[-1];
 
247
                if (n0 == d0)
 
248
                        q=BN_MASK2;
 
249
                else                    /* n0 < d0 */
 
250
                        {
 
251
#ifdef BN_LLONG
 
252
                        BN_ULLONG t2;
 
253
 
 
254
#if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words)
 
255
                        q=(BN_ULONG)(((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0);
 
256
#else
 
257
                        q=bn_div_words(n0,n1,d0);
 
258
#endif
 
259
 
 
260
#ifndef REMAINDER_IS_ALREADY_CALCULATED
 
261
                        /*
 
262
                         * rem doesn't have to be BN_ULLONG. The least we
 
263
                         * know it's less that d0, isn't it?
 
264
                         */
 
265
                        rem=(n1-q*d0)&BN_MASK2;
 
266
#endif
 
267
                        t2=(BN_ULLONG)d1*q;
 
268
 
 
269
                        for (;;)
 
270
                                {
 
271
                                if (t2 <= ((((BN_ULLONG)rem)<<BN_BITS2)|wnump[-2]))
 
272
                                        break;
 
273
                                q--;
 
274
                                rem += d0;
 
275
                                if (rem < d0) break; /* don't let rem overflow */
 
276
                                t2 -= d1;
 
277
                                }
 
278
#else /* !BN_LLONG */
 
279
                        BN_ULONG t2l,t2h,ql,qh;
 
280
 
 
281
                        q=bn_div_words(n0,n1,d0);
 
282
#ifndef REMAINDER_IS_ALREADY_CALCULATED
 
283
                        rem=(n1-q*d0)&BN_MASK2;
 
284
#endif
 
285
 
 
286
#ifdef BN_UMULT_HIGH
 
287
                        t2l = d1 * q;
 
288
                        t2h = BN_UMULT_HIGH(d1,q);
 
289
#else
 
290
                        t2l=LBITS(d1); t2h=HBITS(d1);
 
291
                        ql =LBITS(q);  qh =HBITS(q);
 
292
                        mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */
 
293
#endif
 
294
 
 
295
                        for (;;)
 
296
                                {
 
297
                                if ((t2h < rem) ||
 
298
                                        ((t2h == rem) && (t2l <= wnump[-2])))
 
299
                                        break;
 
300
                                q--;
 
301
                                rem += d0;
 
302
                                if (rem < d0) break; /* don't let rem overflow */
 
303
                                if (t2l < d1) t2h--; t2l -= d1;
 
304
                                }
 
305
#endif /* !BN_LLONG */
 
306
                        }
 
307
#endif /* !BN_DIV3W */
 
308
 
 
309
                l0=bn_mul_words(tmp->d,sdiv->d,div_n,q);
 
310
                wnum.d--; wnum.top++;
 
311
                tmp->d[div_n]=l0;
 
312
                for (j=div_n+1; j>0; j--)
 
313
                        if (tmp->d[j-1]) break;
 
314
                tmp->top=j;
 
315
 
 
316
                j=wnum.top;
 
317
                if (!BN_sub(&wnum,&wnum,tmp)) goto err;
 
318
 
 
319
                snum->top=snum->top+wnum.top-j;
 
320
 
 
321
                if (wnum.neg)
 
322
                        {
 
323
                        q--;
 
324
                        j=wnum.top;
 
325
                        if (!BN_add(&wnum,&wnum,sdiv)) goto err;
 
326
                        snum->top+=wnum.top-j;
 
327
                        }
 
328
                *(resp--)=q;
 
329
                wnump--;
 
330
                }
 
331
        if (rm != NULL)
 
332
                {
 
333
                BN_rshift(rm,snum,norm_shift);
 
334
                rm->neg=num->neg;
 
335
                }
 
336
        BN_CTX_end(ctx);
 
337
        return(1);
 
338
err:
 
339
        BN_CTX_end(ctx);
 
340
        return(0);
 
341
        }
 
342
 
 
343
#endif
 
344
 
 
345
/* rem != m */
 
346
int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
 
347
        {
 
348
#if 0 /* The old slow way */
 
349
        int i,nm,nd;
 
350
        BIGNUM *dv;
 
351
 
 
352
        if (BN_ucmp(m,d) < 0)
 
353
                return((BN_copy(rem,m) == NULL)?0:1);
 
354
 
 
355
        BN_CTX_start(ctx);
 
356
        dv=BN_CTX_get(ctx);
 
357
 
 
358
        if (!BN_copy(rem,m)) goto err;
 
359
 
 
360
        nm=BN_num_bits(rem);
 
361
        nd=BN_num_bits(d);
 
362
        if (!BN_lshift(dv,d,nm-nd)) goto err;
 
363
        for (i=nm-nd; i>=0; i--)
 
364
                {
 
365
                if (BN_cmp(rem,dv) >= 0)
 
366
                        {
 
367
                        if (!BN_sub(rem,rem,dv)) goto err;
 
368
                        }
 
369
                if (!BN_rshift1(dv,dv)) goto err;
 
370
                }
 
371
        BN_CTX_end(ctx);
 
372
        return(1);
 
373
 err:
 
374
        BN_CTX_end(ctx);
 
375
        return(0);
 
376
#else
 
377
        return(BN_div(NULL,rem,m,d,ctx));
 
378
#endif
 
379
        }
 
380