Method magic

ext/src/llvm/APInt.cpp:1224–1260

Calculate the magic numbers required to implement a signed integer division by a constant as a sequence of multiplies, adds and shifts. Requires that the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S. Warren, Jr., chapter 10.

/// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
/// Warren, Jr., chapter 10.
APInt::ms APInt::magic() const {
  const APInt& d = *this;
  unsigned p;
  APInt ad, anc, delta, q1, r1, q2, r2, t;
  APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
  struct ms mag;

  ad = d.abs();
  t = signedMin + (d.lshr(d.getBitWidth() - 1));
  anc = t - 1 - t.urem(ad);   // absolute value of nc
  p = d.getBitWidth() - 1;    // initialize p
  q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
  r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
  q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
  r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
  do {
    p = p + 1;
    q1 = q1<<1;          // update q1 = 2p/abs(nc)
    r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
    if (r1.uge(anc)) {  // must be unsigned comparison
      q1 = q1 + 1;
      r1 = r1 - anc;
    }
    q2 = q2<<1;          // update q2 = 2p/abs(d)
    r2 = r2<<1;          // update r2 = rem(2p/abs(d))
    if (r2.uge(ad)) {   // must be unsigned comparison
      q2 = q2 + 1;
      r2 = r2 - ad;
    }
    delta = ad - r2;
  } while (q1.ult(delta) || (q1 == delta && r1 == 0));

  mag.m = q2 + 1;
  if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
  mag.s = p - d.getBitWidth();          // resulting shift
  return mag;
}

/// Calculate the magic numbers required to implement an unsigned integer
/// division by a constant as a sequence of multiplies, adds and shifts.