AppleCSP/open_ssl/bn/bn_div.c

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