cscrypt/bn_div.c

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