shift_subtract_branch_free.c

// dividend / divisor, remainder is stored in rem.
uint128 __udivmodti4(uint128 dividend, uint128 divisor, uint128* rem) {
  if (divisor > dividend) {
    if (rem)
      *rem = dividend;
    return 0;
  }
  // 64 bit divisor implementation
  ...
  // end
  // Calculate the distance between most significant bits, 128 > shift >= 0.
  int shift = Distance(dividend, divisor);
  divisor <<= shift;
  quotient.low = 0;
  quotient.high = 0;
  for (; shift >= 0; --shift) {
    quotient.low <<= 1;
    const int128 s = (int128)(divisor.all - dividend.all - 1) >> 127;
    quotient.low |= s & 1;
    dividend.all -= divisor.all & s;
    divisor >>= 1;
  }
  if (rem)
    *rem = dividend;
  return quotient;
}