std.math

func i32.abs(self: i32) -> i32 {
  let mask: i32 = self >> 31;
  return (self ^ mask) - mask;
}

func i64.abs(self: i64) -> i64 {
  let mask: i64 = self >> 63;
  return (self ^ mask) - mask;
}

func i32.min(self: i32, rhs: i32) -> i32 {
  return self < rhs ? self : rhs;
}

func i32.max(self: i32, rhs: i32) -> i32 {
  return self > rhs ? self : rhs;
}

func i32.min_u(self: i32, rhs: i32) -> i32 {
  return self.lt_u(rhs) ? self : rhs;
}

func i32.max_u(self: i32, rhs: i32) -> i32 {
  return self.gt_u(rhs) ? self : rhs;
}

func i64.min(self: i64, rhs: i64) -> i64 {
  return self < rhs ? self : rhs;
}

func i64.max(self: i64, rhs: i64) -> i64 {
  return self > rhs ? self : rhs;
}

func i32.clamp(self: i32, lo: i32, hi: i32) -> i32 {
  if (self < lo) { return lo; }
  if (self > hi) { return hi; }
  return self;
}

func i32.signum(self: i32) -> i32 {
  return (self > 0 ? 1 : 0) - (self < 0 ? 1 : 0);
}

func i64.signum(self: i64) -> i32 {
  return (self > 0 ? 1 : 0) - (self < 0 ? 1 : 0);
}

func i32.isqrt(self: i32) -> i32 {
  if (self <= 0) { return 0; }
  var rem: i32 = self;
  var root: i32 = 0;
  // The highest even power of two not exceeding `self`, which is where the digit scan
  // must start. `clz` finds it directly rather than by looping down from 2^30.
  var bit: i32 = 1 << ((31 - self.clz()) & ~1);
  loop scan() {
    if (bit == 0) { break scan(); }
    if (rem >= root + bit) {
      rem = rem - (root + bit);
      root = (root >> 1) + bit;
    } else {
      root = root >> 1;
    }
    bit = bit >> 2;
    continue scan();
  }
  return root;
}

func i32.pow(self: i32, exp: i32) -> i32 {
  if (exp < 0) { return 0; }
  var result: i32 = 1;
  var base: i32 = self;
  var n: i32 = exp;
  loop square() {
    if (n == 0) { break square(); }
    if ((n & 1) == 1) { result = result * base; }
    base = base * base;
    n = n >> 1;
    continue square();
  }
  return result;
}

func i64.pow(self: i64, exp: i32) -> i64 {
  if (exp < 0) { return 0; }
  var result: i64 = 1;
  var base: i64 = self;
  var n: i32 = exp;
  loop square() {
    if (n == 0) { break square(); }
    if ((n & 1) == 1) { result = result * base; }
    base = base * base;
    n = n >> 1;
    continue square();
  }
  return result;
}

func i32.gcd(self: i32, rhs: i32) -> i32 {
  var a: i32 = self.abs();
  var b: i32 = rhs.abs();
  if (a == 0) { return b; }
  if (b == 0) { return a; }
  // Factor out the common powers of two; the loop below then only ever sees odd values.
  //
  // Both shifts are `>>>` (unsigned), not `>>`. A signed shift of `i32` minimum by its own
  // `ctz` of 31 sign-extends to `-1` instead of yielding `1`, so the values would never be
  // odd and the reduction below would never terminate.
  let shift: i32 = (a | b).ctz();
  a = a >>> a.ctz();
  loop reduce() {
    b = b >>> b.ctz();
    // **Unsigned** comparison, and this is load-bearing rather than stylistic. `abs` of
    // `i32` minimum is itself, still negative, so a signed `>` would never order it first;
    // the subtraction below would then run away from zero and the loop would never
    // terminate. Both values are magnitudes here, so unsigned is also the correct reading.
    if (a.gt_u(b)) {
      let t: i32 = a;
      a = b;
      b = t;
    }
    b = b - a;
    if (b == 0) { break reduce(); }
    continue reduce();
  }
  return a << shift;
}

func i32.lcm(self: i32, rhs: i32) -> i32 {
  if (self == 0 || rhs == 0) { return 0; }
  let g: i32 = self.gcd(rhs);
  return (self.abs() / g) * rhs.abs();
}

func i32.log2(self: i32) -> i32 {
  return 31 - self.clz();
}

func i32.log10(self: i32) -> i32 {
  if (self <= 0) { return -1; }
  var n: i32 = self;
  var digits: i32 = 0;
  loop count() {
    n = n / 10;
    if (n == 0) { break count(); }
    digits = digits + 1;
    continue count();
  }
  return digits;
}

func i32.is_pow2(self: i32) -> i32 {
  return self > 0 && (self & (self - 1)) == 0;
}

func i32.next_pow2(self: i32) -> i32 {
  if (self <= 1) { return 1; }
  return 1 << (32 - (self - 1).clz());
}

func i32.div_floor(self: i32, rhs: i32) -> i32 {
  let q: i32 = self / rhs;
  // Truncation and flooring differ exactly when the operands have opposite signs and the
  // division was not exact.
  if ((self % rhs != 0) && ((self < 0) != (rhs < 0))) { return q - 1; }
  return q;
}

func i32.mod_floor(self: i32, rhs: i32) -> i32 {
  let r: i32 = self % rhs;
  if (r != 0 && ((r < 0) != (rhs < 0))) { return r + rhs; }
  return r;
}

func i32.sat_add(self: i32, rhs: i32) -> i32 {
  let sum: i32 = self + rhs;
  // Overflow happened exactly when both operands share a sign that the result does not.
  if (((self ^ sum) & (rhs ^ sum)) < 0) {
    return self < 0 ? -2147483648 : 2147483647;
  }
  return sum;
}

func i32.sat_sub(self: i32, rhs: i32) -> i32 {
  let diff: i32 = self - rhs;
  if (((self ^ rhs) & (self ^ diff)) < 0) {
    return self < 0 ? -2147483648 : 2147483647;
  }
  return diff;
}

func i32.lerp(self: i32, to: i32, t: i32, scale: i32) -> i32 {
  return self + ((to - self) * t) / scale;
}

func i32.is_prime(self: i32) -> i32 {
  if (self < 2) { return 0; }
  if (self < 4) { return 1; }
  if (self % 2 == 0) { return 0; }
  if (self % 3 == 0) { return 0; }
  // The loop bound is compared against `isqrt(self)` rather than testing `f * f > self`.
  // That square overflows for any `f` above 46340, wrapping negative, so the guard silently
  // stops being true and the scan runs on until it hits a spurious "divisor" -- which made
  // `(2147483647).is_prime()` answer 0. Computing the limit once avoids the multiply
  // entirely and is faster besides.
  let limit: i32 = self.isqrt();
  // Every prime above 3 is 6k±1, so the scan can step by 6 and test two candidates.
  var f: i32 = 5;
  loop trial() {
    if (f > limit) { break trial(); }
    if (self % f == 0) { return 0; }
    if (self % (f + 2) == 0) { return 0; }
    f = f + 6;
    continue trial();
  }
  return 1;
}