int BN_div()

in Sources/CCryptoBoringSSL/crypto/fipsmodule/bn/div.c [194:399]
152 lines of code
35 McCabe index (conditional complexity)

int BN_div(BIGNUM *quotient, BIGNUM *rem, const BIGNUM *numerator,
           const BIGNUM *divisor, BN_CTX *ctx) {
  int norm_shift, loop;
  BIGNUM wnum;
  BN_ULONG *resp, *wnump;
  BN_ULONG d0, d1;
  int num_n, div_n;

  // This function relies on the historical minimal-width |BIGNUM| invariant.
  // It is already not constant-time (constant-time reductions should use
  // Montgomery logic), so we shrink all inputs and intermediate values to
  // retain the previous behavior.

  // Invalid zero-padding would have particularly bad consequences.
  int numerator_width = bn_minimal_width(numerator);
  int divisor_width = bn_minimal_width(divisor);
  if ((numerator_width > 0 && numerator->d[numerator_width - 1] == 0) ||
      (divisor_width > 0 && divisor->d[divisor_width - 1] == 0)) {
    OPENSSL_PUT_ERROR(BN, BN_R_NOT_INITIALIZED);
    return 0;
  }

  if (BN_is_zero(divisor)) {
    OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO);
    return 0;
  }

  BN_CTX_start(ctx);
  BIGNUM *tmp = BN_CTX_get(ctx);
  BIGNUM *snum = BN_CTX_get(ctx);
  BIGNUM *sdiv = BN_CTX_get(ctx);
  BIGNUM *res = NULL;
  if (quotient == NULL) {
    res = BN_CTX_get(ctx);
  } else {
    res = quotient;
  }
  if (sdiv == NULL || res == NULL) {
    goto err;
  }

  // First we normalise the numbers
  norm_shift = BN_BITS2 - (BN_num_bits(divisor) % BN_BITS2);
  if (!BN_lshift(sdiv, divisor, norm_shift)) {
    goto err;
  }
  bn_set_minimal_width(sdiv);
  sdiv->neg = 0;
  norm_shift += BN_BITS2;
  if (!BN_lshift(snum, numerator, norm_shift)) {
    goto err;
  }
  bn_set_minimal_width(snum);
  snum->neg = 0;

  // Since we don't want to have special-case logic for the case where snum is
  // larger than sdiv, we pad snum with enough zeroes without changing its
  // value.
  if (snum->width <= sdiv->width + 1) {
    if (!bn_wexpand(snum, sdiv->width + 2)) {
      goto err;
    }
    for (int i = snum->width; i < sdiv->width + 2; i++) {
      snum->d[i] = 0;
    }
    snum->width = sdiv->width + 2;
  } else {
    if (!bn_wexpand(snum, snum->width + 1)) {
      goto err;
    }
    snum->d[snum->width] = 0;
    snum->width++;
  }

  div_n = sdiv->width;
  num_n = snum->width;
  loop = num_n - div_n;
  // Lets setup a 'window' into snum
  // This is the part that corresponds to the current
  // 'area' being divided
  wnum.neg = 0;
  wnum.d = &(snum->d[loop]);
  wnum.width = div_n;
  // only needed when BN_ucmp messes up the values between width and max
  wnum.dmax = snum->dmax - loop;  // so we don't step out of bounds

  // Get the top 2 words of sdiv
  // div_n=sdiv->width;
  d0 = sdiv->d[div_n - 1];
  d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2];

  // pointer to the 'top' of snum
  wnump = &(snum->d[num_n - 1]);

  // Setup |res|. |numerator| and |res| may alias, so we save |numerator->neg|
  // for later.
  const int numerator_neg = numerator->neg;
  res->neg = (numerator_neg ^ divisor->neg);
  if (!bn_wexpand(res, loop + 1)) {
    goto err;
  }
  res->width = loop - 1;
  resp = &(res->d[loop - 1]);

  // space for temp
  if (!bn_wexpand(tmp, div_n + 1)) {
    goto err;
  }

  // if res->width == 0 then clear the neg value otherwise decrease
  // the resp pointer
  if (res->width == 0) {
    res->neg = 0;
  } else {
    resp--;
  }

  for (int i = 0; i < loop - 1; i++, wnump--, resp--) {
    BN_ULONG q, l0;
    // the first part of the loop uses the top two words of snum and sdiv to
    // calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv
    BN_ULONG n0, n1, rm = 0;

    n0 = wnump[0];
    n1 = wnump[-1];
    if (n0 == d0) {
      q = BN_MASK2;
    } else {
      // n0 < d0
      bn_div_rem_words(&q, &rm, n0, n1, d0);

#ifdef BN_ULLONG
      BN_ULLONG t2 = (BN_ULLONG)d1 * q;
      for (;;) {
        if (t2 <= ((((BN_ULLONG)rm) << BN_BITS2) | wnump[-2])) {
          break;
        }
        q--;
        rm += d0;
        if (rm < d0) {
          break;  // don't let rm overflow
        }
        t2 -= d1;
      }
#else  // !BN_ULLONG
      BN_ULONG t2l, t2h;
      BN_UMULT_LOHI(t2l, t2h, d1, q);
      for (;;) {
        if (t2h < rm ||
            (t2h == rm && t2l <= wnump[-2])) {
          break;
        }
        q--;
        rm += d0;
        if (rm < d0) {
          break;  // don't let rm overflow
        }
        if (t2l < d1) {
          t2h--;
        }
        t2l -= d1;
      }
#endif  // !BN_ULLONG
    }

    l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q);
    tmp->d[div_n] = l0;
    wnum.d--;
    // ingore top values of the bignums just sub the two
    // BN_ULONG arrays with bn_sub_words
    if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) {
      // Note: As we have considered only the leading
      // two BN_ULONGs in the calculation of q, sdiv * q
      // might be greater than wnum (but then (q-1) * sdiv
      // is less or equal than wnum)
      q--;
      if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) {
        // we can't have an overflow here (assuming
        // that q != 0, but if q == 0 then tmp is
        // zero anyway)
        (*wnump)++;
      }
    }
    // store part of the result
    *resp = q;
  }

  bn_set_minimal_width(snum);

  if (rem != NULL) {
    if (!BN_rshift(rem, snum, norm_shift)) {
      goto err;
    }
    if (!BN_is_zero(rem)) {
      rem->neg = numerator_neg;
    }
  }

  bn_set_minimal_width(res);
  BN_CTX_end(ctx);
  return 1;

err:
  BN_CTX_end(ctx);
  return 0;
}