lib/libcrypto/bn/bn_div.c

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