[Support] Add MathExtrasHEADmaster

3 files changed, 1148 insertions, 0 deletions

diff --git a/rcc/include/rcc/Support/MathExtras.h b/rcc/include/rcc/Support/MathExtras.h
new file mode 100644
index 0000000..6ea2a1f
--- /dev/null
+++ b/rcc/include/rcc/Support/MathExtras.h
@@ -0,0 +1,1050 @@
+/*
+ RCC-Project
+
+ Copyright (C) 2026 Richard Qin
+
+ This file is part of RCC-Project.
+
+ RCC-Project is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your option) any
+ later version.
+
+ RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ RCC-Project; see the file COPYING.  If not see
+ <http://www.gnu.org/licenses/>.
+*/
+
+//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains some functions that are useful for math stuff.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef RCC_SUPPORT_MATHEXTRAS_H
+#define RCC_SUPPORT_MATHEXTRAS_H
+
+#include "rcc/Support/Compiler.h"
+#include <bit>
+#include <cassert>
+#include <climits>
+#include <cstdint>
+#include <cstring>
+#include <limits>
+#include <numbers>
+#include <type_traits>
+#include <utility>
+
+namespace rcc
+{
+/// Some template parameter helpers to optimize for bitwidth, for functions that
+/// take multiple arguments.
+
+// We can't verify signedness, since callers rely on implicit coercions to
+// signed/unsigned.
+template <typename T, typename U>
+using enableif_int =
+    std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>;
+
+// Use std::common_type_t to widen only up to the widest argument.
+template <typename T, typename U, typename = enableif_int<T, U>>
+using common_uint =
+    std::common_type_t<std::make_unsigned_t<T>, std::make_unsigned_t<U>>;
+template <typename T, typename U, typename = enableif_int<T, U>>
+using common_sint =
+    std::common_type_t<std::make_signed_t<T>, std::make_signed_t<U>>;
+
+/// Mathematical constants.
+namespace numbers
+{
+// clang-format off
+inline constexpr float ef          = std::numbers::e_v<float>;
+inline constexpr float egammaf     = std::numbers::egamma_v<float>;
+inline constexpr float ln2f        = std::numbers::ln2_v<float>;
+inline constexpr float ln10f       = std::numbers::ln10_v<float>;
+inline constexpr float log2ef      = std::numbers::log2e_v<float>;
+inline constexpr float log10ef     = std::numbers::log10e_v<float>;
+inline constexpr float pif         = std::numbers::pi_v<float>;
+inline constexpr float inv_pif     = std::numbers::inv_pi_v<float>;
+inline constexpr float inv_sqrtpif = std::numbers::inv_sqrtpi_v<float>;
+inline constexpr float sqrt2f      = std::numbers::sqrt2_v<float>;
+inline constexpr float inv_sqrt2f  = 1.0f / std::numbers::sqrt2_v<float>;
+inline constexpr float sqrt3f      = std::numbers::sqrt3_v<float>;
+inline constexpr float inv_sqrt3f  = std::numbers::inv_sqrt3_v<float>;
+inline constexpr float phif        = std::numbers::phi_v<float>;
+
+// sqrtpi is not in C++20 std::numbers.
+template <typename T, typename = std::enable_if_t<std::is_floating_point_v<T>>>
+inline constexpr T sqrtpi_v = T(0x1.c5bf891b4ef6bP+0); // (1.7724538509055160273) https://oeis.org/A002161
+inline constexpr double sqrtpi  = sqrtpi_v<double>;
+inline constexpr float  sqrtpif = sqrtpi_v<float>;
+
+// These string literals are taken from below:
+// https://github.com/bminor/glibc/blob/8543577b04ded6d979ffcc5a818930e4d74d0645/math/math.h#L1215-L1229
+constexpr const char *pis     = "3.141592653589793238462643383279502884",
+                     *inv_pis = "0.318309886183790671537767526745028724";
+// clang-format on
+} // namespace numbers
+
+/// Create a bitmask with the N right-most bits set to 1, and all other
+/// bits set to 0.  Only unsigned types are allowed.
+template <typename T>
+constexpr T
+maskTrailingOnes (unsigned N)
+{
+  static_assert (std::is_unsigned_v<T>, "Invalid type!");
+  const unsigned Bits = CHAR_BIT * sizeof (T);
+  assert (N <= Bits && "Invalid bit index");
+  if (N == 0)
+  {
+    return 0;
+  }
+  return T (-1) >> (Bits - N);
+}
+
+/// Create a bitmask with the N left-most bits set to 1, and all other
+/// bits set to 0.  Only unsigned types are allowed.
+template <typename T>
+constexpr T
+maskLeadingOnes (unsigned N)
+{
+  return ~maskTrailingOnes<T> (CHAR_BIT * sizeof (T) - N);
+}
+
+/// Create a bitmask with the N right-most bits set to 0, and all other
+/// bits set to 1.  Only unsigned types are allowed.
+template <typename T>
+constexpr T
+maskTrailingZeros (unsigned N)
+{
+  return maskLeadingOnes<T> (CHAR_BIT * sizeof (T) - N);
+}
+
+/// Create a bitmask with the N left-most bits set to 0, and all other
+/// bits set to 1.  Only unsigned types are allowed.
+template <typename T>
+constexpr T
+maskLeadingZeros (unsigned N)
+{
+  return maskTrailingOnes<T> (CHAR_BIT * sizeof (T) - N);
+}
+
+/// Macro compressed bit reversal table for 256 bits.
+///
+/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
+static const unsigned char BitReverseTable256[256] = {
+#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
+#define R4(n) R2 (n), R2 (n + 2 * 16), R2 (n + 1 * 16), R2 (n + 3 * 16)
+#define R6(n) R4 (n), R4 (n + 2 * 4), R4 (n + 1 * 4), R4 (n + 3 * 4)
+    R6 (0), R6 (2), R6 (1), R6 (3)
+#undef R2
+#undef R4
+#undef R6
+};
+
+/// Reverse the bits in \p Val.
+template <typename T>
+constexpr T
+reverseBits (T Val)
+{
+#if __has_builtin(__builtin_bitreverse8)
+  if constexpr (std::is_same_v<T, uint8_t>)
+  {
+    return __builtin_bitreverse8 (Val);
+  }
+#endif
+#if __has_builtin(__builtin_bitreverse16)
+  if constexpr (std::is_same_v<T, uint16_t>)
+  {
+    return __builtin_bitreverse16 (Val);
+  }
+#endif
+#if __has_builtin(__builtin_bitreverse32)
+  if constexpr (std::is_same_v<T, uint32_t>)
+  {
+    return __builtin_bitreverse32 (Val);
+  }
+#endif
+#if __has_builtin(__builtin_bitreverse64)
+  if constexpr (std::is_same_v<T, uint64_t>)
+  {
+    return __builtin_bitreverse64 (Val);
+  }
+#endif
+
+  unsigned char in[sizeof (Val)];
+  unsigned char out[sizeof (Val)];
+  std::memcpy (in, &Val, sizeof (Val));
+  for (unsigned i = 0; i < sizeof (Val); ++i)
+  {
+    out[(sizeof (Val) - i) - 1] = BitReverseTable256[in[i]];
+  }
+  std::memcpy (&Val, out, sizeof (Val));
+  return Val;
+}
+
+// NOTE: The following support functions use the _32/_64 extensions instead of
+// type overloading so that signed and unsigned integers can be used without
+// ambiguity.
+
+/// Return the high 32 bits of a 64 bit value.
+constexpr uint32_t
+Hi_32 (uint64_t Value)
+{
+  return static_cast<uint32_t> (Value >> 32);
+}
+
+/// Return the low 32 bits of a 64 bit value.
+constexpr uint32_t
+Lo_32 (uint64_t Value)
+{
+  return static_cast<uint32_t> (Value);
+}
+
+/// Make a 64-bit integer from a high / low pair of 32-bit integers.
+constexpr uint64_t
+Make_64 (uint32_t High, uint32_t Low)
+{
+  return ((uint64_t)High << 32) | (uint64_t)Low;
+}
+
+/// Checks if an integer fits into the given bit width.
+template <unsigned N>
+constexpr bool
+isInt (int64_t x)
+{
+  if constexpr (N == 0)
+  {
+    return 0 == x;
+  }
+  if constexpr (N == 8)
+  {
+    return static_cast<int8_t> (x) == x;
+  }
+  if constexpr (N == 16)
+  {
+    return static_cast<int16_t> (x) == x;
+  }
+  if constexpr (N == 32)
+  {
+    return static_cast<int32_t> (x) == x;
+  }
+  if constexpr (N < 64)
+  {
+    return -(INT64_C (1) << (N - 1)) <= x && x < (INT64_C (1) << (N - 1));
+  }
+  (void)x; // MSVC v19.25 warns that x is unused.
+  return true;
+}
+
+/// Checks if a signed integer is an N bit number shifted left by S.
+template <unsigned N, unsigned S>
+constexpr bool
+isShiftedInt (int64_t x)
+{
+  static_assert (S < 64, "isShiftedInt<N, S> with S >= 64 is too much.");
+  static_assert (N + S <= 64,
+                 "isShiftedInt<N, S> with N + S > 64 is too wide.");
+  return isInt<N + S> (x) && (x % (UINT64_C (1) << S) == 0);
+}
+
+/// Checks if an unsigned integer fits into the given bit width.
+template <unsigned N>
+constexpr bool
+isUInt (uint64_t x)
+{
+  if constexpr (N < 64)
+  {
+    return (x >> N) == 0;
+  }
+  (void)x; // MSVC v19.25 warns that x is unused.
+  return true;
+}
+
+/// Checks if a unsigned integer is an N bit number shifted left by S.
+template <unsigned N, unsigned S>
+constexpr bool
+isShiftedUInt (uint64_t x)
+{
+  static_assert (S < 64, "isShiftedUInt<N, S> with S >= 64 is too much.");
+  static_assert (N + S <= 64,
+                 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
+  // S must be strictly less than 64. So 1 << S is not undefined behavior.
+  return isUInt<N + S> (x) && (x % (UINT64_C (1) << S) == 0);
+}
+
+/// Gets the maximum value for a N-bit unsigned integer.
+inline constexpr uint64_t
+maxUIntN (uint64_t N)
+{
+  assert (N <= 64 && "integer width out of range");
+
+  // uint64_t(1) << 64 is undefined behavior, so we can't do
+  //   (uint64_t(1) << N) - 1
+  // without checking first that N != 64.  But this works and doesn't have a
+  // branch for N != 0.
+  // Unfortunately, shifting a uint64_t right by 64 bit is undefined
+  // behavior, so the condition on N == 0 is necessary. Fortunately, most
+  // optimizers do not emit branches for this check.
+  if (N == 0)
+  {
+    return 0;
+  }
+  return UINT64_MAX >> (64 - N);
+}
+
+/// Gets the minimum value for a N-bit signed integer.
+inline constexpr int64_t
+minIntN (int64_t N)
+{
+  assert (N <= 64 && "integer width out of range");
+
+  if (N == 0)
+  {
+    return 0;
+  }
+  return UINT64_MAX << (N - 1);
+}
+
+/// Gets the maximum value for a N-bit signed integer.
+inline constexpr int64_t
+maxIntN (int64_t N)
+{
+  assert (N <= 64 && "integer width out of range");
+
+  // This relies on two's complement wraparound when N == 64, so we convert to
+  // int64_t only at the very end to avoid UB.
+  if (N == 0)
+  {
+    return 0;
+  }
+  return (UINT64_C (1) << (N - 1)) - 1;
+}
+
+/// Checks if an unsigned integer fits into the given (dynamic) bit width.
+inline constexpr bool
+isUIntN (unsigned N, uint64_t x)
+{
+  return N >= 64 || (x >> N) == 0;
+}
+
+/// Checks if an signed integer fits into the given (dynamic) bit width.
+inline constexpr bool
+isIntN (unsigned N, int64_t x)
+{
+  return N >= 64 || (minIntN (N) <= x && x <= maxIntN (N));
+}
+
+/// Return true if the argument is a non-empty sequence of ones starting at the
+/// least significant bit with the remainder zero (32 bit version).
+/// Ex. isMask_32(0x0000FFFFU) == true.
+constexpr bool
+isMask_32 (uint32_t Value)
+{
+  return Value && ((Value + 1) & Value) == 0;
+}
+
+/// Return true if the argument is a non-empty sequence of ones starting at the
+/// least significant bit with the remainder zero (64 bit version).
+constexpr bool
+isMask_64 (uint64_t Value)
+{
+  return Value && ((Value + 1) & Value) == 0;
+}
+
+/// Return true if the argument contains a non-empty sequence of ones with the
+/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
+constexpr bool
+isShiftedMask_32 (uint32_t Value)
+{
+  return Value && isMask_32 ((Value - 1) | Value);
+}
+
+/// Return true if the argument contains a non-empty sequence of ones with the
+/// remainder zero (64 bit version.)
+constexpr bool
+isShiftedMask_64 (uint64_t Value)
+{
+  return Value && isMask_64 ((Value - 1) | Value);
+}
+
+/// Return true if the argument is a power of two > 0.
+/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
+constexpr bool
+isPowerOf2_32 (uint32_t Value)
+{
+  return std::has_single_bit (Value);
+}
+
+/// Return true if the argument is a power of two > 0 (64 bit edition.)
+constexpr bool
+isPowerOf2_64 (uint64_t Value)
+{
+  return std::has_single_bit (Value);
+}
+
+/// Return true if the argument contains a non-empty sequence of ones with the
+/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
+/// If true, \p MaskIdx will specify the index of the lowest set bit and \p
+/// MaskLen is updated to specify the length of the mask, else neither are
+/// updated.
+inline bool
+isShiftedMask_32 (uint32_t Value, unsigned &MaskIdx, unsigned &MaskLen)
+{
+  if (!isShiftedMask_32 (Value))
+  {
+    return false;
+  }
+  MaskIdx = std::countr_zero (Value);
+  MaskLen = std::popcount (Value);
+  return true;
+}
+
+/// Return true if the argument contains a non-empty sequence of ones with the
+/// remainder zero (64 bit version.) If true, \p MaskIdx will specify the index
+/// of the lowest set bit and \p MaskLen is updated to specify the length of the
+/// mask, else neither are updated.
+inline bool
+isShiftedMask_64 (uint64_t Value, unsigned &MaskIdx, unsigned &MaskLen)
+{
+  if (!isShiftedMask_64 (Value))
+  {
+    return false;
+  }
+  MaskIdx = std::countr_zero (Value);
+  MaskLen = std::popcount (Value);
+  return true;
+}
+
+/// Compile time Log2.
+/// Valid only for positive powers of two.
+template <size_t kValue>
+constexpr size_t
+ConstantLog2 ()
+{
+  static_assert (rcc::isPowerOf2_64 (kValue),
+                 "Value is not a valid power of 2");
+  return std::countr_zero (kValue);
+}
+
+/// Return the floor log base 2 of the specified value, -1 if the value is zero.
+/// (32 bit edition.)
+/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
+inline unsigned
+Log2_32 (uint32_t Value)
+{
+  return 31 - std::countl_zero (Value);
+}
+
+/// Return the floor log base 2 of the specified value, -1 if the value is zero.
+/// (64 bit edition.)
+inline unsigned
+Log2_64 (uint64_t Value)
+{
+  return 63 - std::countl_zero (Value);
+}
+
+/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
+/// (32 bit edition).
+/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
+inline unsigned
+Log2_32_Ceil (uint32_t Value)
+{
+  return 32 - std::countl_zero (Value - 1);
+}
+
+/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
+/// (64 bit edition.)
+inline unsigned
+Log2_64_Ceil (uint64_t Value)
+{
+  return 64 - std::countl_zero (Value - 1);
+}
+
+/// A and B are either alignments or offsets. Return the minimum alignment that
+/// may be assumed after adding the two together.
+template <typename U, typename V, typename T = common_uint<U, V>>
+constexpr T
+MinAlign (U A, V B)
+{
+  // The largest power of 2 that divides both A and B.
+  //
+  // Replace "-Value" by "1+~Value" in the following commented code to avoid
+  // MSVC warning C4146
+  //    return (A | B) & -(A | B);
+  return (A | B) & (1 + ~(A | B));
+}
+
+/// Fallback when arguments aren't integral.
+constexpr uint64_t
+MinAlign (uint64_t A, uint64_t B)
+{
+  return (A | B) & (1 + ~(A | B));
+}
+
+/// Returns the next power of two (in 64-bits) that is strictly greater than A.
+/// Returns zero on overflow.
+constexpr uint64_t
+NextPowerOf2 (uint64_t A)
+{
+  A |= (A >> 1);
+  A |= (A >> 2);
+  A |= (A >> 4);
+  A |= (A >> 8);
+  A |= (A >> 16);
+  A |= (A >> 32);
+  return A + 1;
+}
+
+/// Returns the power of two which is greater than or equal to the given value.
+/// Essentially, it is a ceil operation across the domain of powers of two.
+inline uint64_t
+PowerOf2Ceil (uint64_t A)
+{
+  if (!A || A > UINT64_MAX / 2)
+  {
+    return 0;
+  }
+  return UINT64_C (1) << Log2_64_Ceil (A);
+}
+
+/// Returns the integer ceil(Numerator / Denominator). Unsigned version.
+/// Guaranteed to never overflow.
+template <typename U, typename V, typename T = common_uint<U, V>>
+constexpr T
+divideCeil (U Numerator, V Denominator)
+{
+  assert (Denominator && "Division by zero");
+  T Bias = (Numerator != 0);
+  return (Numerator - Bias) / Denominator + Bias;
+}
+
+/// Fallback when arguments aren't integral.
+constexpr uint64_t
+divideCeil (uint64_t Numerator, uint64_t Denominator)
+{
+  assert (Denominator && "Division by zero");
+  uint64_t Bias = (Numerator != 0);
+  return (Numerator - Bias) / Denominator + Bias;
+}
+
+// Check whether divideCeilSigned or divideFloorSigned would overflow. This
+// happens only when Numerator = INT_MIN and Denominator = -1.
+template <typename U, typename V>
+constexpr bool
+divideSignedWouldOverflow (U Numerator, V Denominator)
+{
+  return Numerator == std::numeric_limits<U>::min () && Denominator == -1;
+}
+
+/// Returns the integer ceil(Numerator / Denominator). Signed version.
+/// Overflow is explicitly forbidden with an assert.
+template <typename U, typename V, typename T = common_sint<U, V>>
+constexpr T
+divideCeilSigned (U Numerator, V Denominator)
+{
+  assert (Denominator && "Division by zero");
+  assert (!divideSignedWouldOverflow (Numerator, Denominator) &&
+          "Divide would overflow");
+  if (!Numerator)
+  {
+    return 0;
+  }
+  // C's integer division rounds towards 0.
+  T Bias = Denominator >= 0 ? 1 : -1;
+  bool SameSign = (Numerator >= 0) == (Denominator >= 0);
+  return SameSign ? (Numerator - Bias) / Denominator + 1
+                  : Numerator / Denominator;
+}
+
+/// Returns the integer floor(Numerator / Denominator). Signed version.
+/// Overflow is explicitly forbidden with an assert.
+template <typename U, typename V, typename T = common_sint<U, V>>
+constexpr T
+divideFloorSigned (U Numerator, V Denominator)
+{
+  assert (Denominator && "Division by zero");
+  assert (!divideSignedWouldOverflow (Numerator, Denominator) &&
+          "Divide would overflow");
+  if (!Numerator)
+  {
+    return 0;
+  }
+  // C's integer division rounds towards 0.
+  T Bias = Denominator >= 0 ? -1 : 1;
+  bool SameSign = (Numerator >= 0) == (Denominator >= 0);
+  return SameSign ? Numerator / Denominator
+                  : (Numerator - Bias) / Denominator - 1;
+}
+
+/// Returns the remainder of the Euclidean division of LHS by RHS. Result is
+/// always non-negative.
+template <typename U, typename V, typename T = common_sint<U, V>>
+constexpr T
+mod (U Numerator, V Denominator)
+{
+  assert (Denominator >= 1 && "Mod by non-positive number");
+  T Mod = Numerator % Denominator;
+  return Mod < 0 ? Mod + Denominator : Mod;
+}
+
+/// Returns (Numerator / Denominator) rounded by round-half-up. Guaranteed to
+/// never overflow.
+template <typename U, typename V, typename T = common_uint<U, V>>
+constexpr T
+divideNearest (U Numerator, V Denominator)
+{
+  assert (Denominator && "Division by zero");
+  T Mod = Numerator % Denominator;
+  return (Numerator / Denominator) +
+         (Mod > (static_cast<T> (Denominator) - 1) / 2);
+}
+
+/// Returns the next integer (mod 2**nbits) that is greater than or equal to
+/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
+///
+/// Examples:
+/// \code
+///   alignTo(5, 8) = 8
+///   alignTo(17, 8) = 24
+///   alignTo(~0LL, 8) = 0
+///   alignTo(321, 255) = 510
+/// \endcode
+///
+/// Will overflow only if result is not representable in T.
+template <typename U, typename V, typename T = common_uint<U, V>>
+constexpr T
+alignTo (U Value, V Align)
+{
+  assert (Align != 0u && "Align can't be 0.");
+  T CeilDiv = divideCeil (Value, Align);
+  return CeilDiv * Align;
+}
+
+/// Fallback when arguments aren't integral.
+constexpr uint64_t
+alignTo (uint64_t Value, uint64_t Align)
+{
+  assert (Align != 0u && "Align can't be 0.");
+  uint64_t CeilDiv = divideCeil (Value, Align);
+  return CeilDiv * Align;
+}
+
+/// Will overflow only if result is not representable in T.
+template <typename U, typename V, typename T = common_uint<U, V>>
+constexpr T
+alignToPowerOf2 (U Value, V Align)
+{
+  assert (Align != 0 && (Align & (Align - 1)) == 0 &&
+          "Align must be a power of 2");
+  T NegAlign = static_cast<T> (0) - Align;
+  return (Value + (Align - 1)) & NegAlign;
+}
+
+/// Fallback when arguments aren't integral.
+constexpr uint64_t
+alignToPowerOf2 (uint64_t Value, uint64_t Align)
+{
+  assert (Align != 0 && (Align & (Align - 1)) == 0 &&
+          "Align must be a power of 2");
+  uint64_t NegAlign = 0 - Align;
+  return (Value + (Align - 1)) & NegAlign;
+}
+
+/// If non-zero \p Skew is specified, the return value will be a minimal integer
+/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
+/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
+/// Skew mod \p A'. \p Align must be non-zero.
+///
+/// Examples:
+/// \code
+///   alignTo(5, 8, 7) = 7
+///   alignTo(17, 8, 1) = 17
+///   alignTo(~0LL, 8, 3) = 3
+///   alignTo(321, 255, 42) = 552
+/// \endcode
+///
+/// May overflow.
+template <typename U, typename V, typename W,
+          typename T = common_uint<common_uint<U, V>, W>>
+constexpr T
+alignTo (U Value, V Align, W Skew)
+{
+  assert (Align != 0u && "Align can't be 0.");
+  Skew %= Align;
+  return alignTo (Value - Skew, Align) + Skew;
+}
+
+/// Returns the next integer (mod 2**nbits) that is greater than or equal to
+/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
+///
+/// Will overflow only if result is not representable in T.
+template <auto Align, typename V, typename T = common_uint<decltype (Align), V>>
+constexpr T
+alignTo (V Value)
+{
+  static_assert (Align != 0u, "Align must be non-zero");
+  T CeilDiv = divideCeil (Value, Align);
+  return CeilDiv * Align;
+}
+
+/// Returns the largest unsigned integer less than or equal to \p Value and is
+/// \p Skew mod \p Align. \p Align must be non-zero. Guaranteed to never
+/// overflow.
+template <typename U, typename V, typename W = uint8_t,
+          typename T = common_uint<common_uint<U, V>, W>>
+constexpr T
+alignDown (U Value, V Align, W Skew = 0)
+{
+  assert (Align != 0u && "Align can't be 0.");
+  Skew %= Align;
+  return (Value - Skew) / Align * Align + Skew;
+}
+
+/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
+/// Requires B <= 32.
+template <unsigned B>
+constexpr int32_t
+SignExtend32 (uint32_t X)
+{
+  static_assert (B <= 32, "Bit width out of range.");
+  if constexpr (B == 0)
+  {
+    return 0;
+  }
+  return int32_t (X << (32 - B)) >> (32 - B);
+}
+
+/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
+/// Requires B <= 32.
+inline int32_t
+SignExtend32 (uint32_t X, unsigned B)
+{
+  assert (B <= 32 && "Bit width out of range.");
+  if (B == 0)
+  {
+    return 0;
+  }
+  return int32_t (X << (32 - B)) >> (32 - B);
+}
+
+/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
+/// Requires B <= 64.
+template <unsigned B>
+constexpr int64_t
+SignExtend64 (uint64_t x)
+{
+  static_assert (B <= 64, "Bit width out of range.");
+  if constexpr (B == 0)
+  {
+    return 0;
+  }
+  return int64_t (x << (64 - B)) >> (64 - B);
+}
+
+/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
+/// Requires B <= 64.
+inline int64_t
+SignExtend64 (uint64_t X, unsigned B)
+{
+  assert (B <= 64 && "Bit width out of range.");
+  if (B == 0)
+  {
+    return 0;
+  }
+  return int64_t (X << (64 - B)) >> (64 - B);
+}
+
+/// Return the absolute value of a signed integer, converted to the
+/// corresponding unsigned integer type. Avoids undefined behavior in std::abs
+/// when you pass it INT_MIN or similar.
+template <typename T, typename U = std::make_unsigned_t<T>>
+constexpr U
+AbsoluteValue (T X)
+{
+  // If X is negative, cast it to the unsigned type _before_ negating it.
+  return X < 0 ? -static_cast<U> (X) : X;
+}
+
+/// Subtract two unsigned integers, X and Y, of type T and return the absolute
+/// value of the result.
+template <typename U, typename V, typename T = common_uint<U, V>>
+constexpr T
+AbsoluteDifference (U X, V Y)
+{
+  return X > Y ? (X - Y) : (Y - X);
+}
+
+/// Add two unsigned integers, X and Y, of type T.  Clamp the result to the
+/// maximum representable value of T on overflow.  ResultOverflowed indicates if
+/// the result is larger than the maximum representable value of type T.
+template <typename T>
+std::enable_if_t<std::is_unsigned_v<T>, T>
+SaturatingAdd (T X, T Y, bool *ResultOverflowed = nullptr)
+{
+  bool Dummy;
+  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
+  // Hacker's Delight, p. 29
+  T Z = X + Y;
+  Overflowed = (Z < X || Z < Y);
+  if (Overflowed)
+  {
+    return std::numeric_limits<T>::max ();
+  }
+  else
+  {
+    return Z;
+  }
+}
+
+/// Add multiple unsigned integers of type T.  Clamp the result to the
+/// maximum representable value of T on overflow.
+template <class T, class... Ts>
+std::enable_if_t<std::is_unsigned_v<T>, T>
+SaturatingAdd (T X, T Y, T Z, Ts... Args)
+{
+  bool Overflowed = false;
+  T XY = SaturatingAdd (X, Y, &Overflowed);
+  if (Overflowed)
+  {
+    return SaturatingAdd (std::numeric_limits<T>::max (), T (1), Args...);
+  }
+  return SaturatingAdd (XY, Z, Args...);
+}
+
+/// Multiply two unsigned integers, X and Y, of type T.  Clamp the result to the
+/// maximum representable value of T on overflow.  ResultOverflowed indicates if
+/// the result is larger than the maximum representable value of type T.
+template <typename T>
+std::enable_if_t<std::is_unsigned_v<T>, T>
+SaturatingMultiply (T X, T Y, bool *ResultOverflowed = nullptr)
+{
+  bool Dummy;
+  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
+
+  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
+  // because it fails for uint16_t (where multiplication can have undefined
+  // behavior due to promotion to int), and requires a division in addition
+  // to the multiplication.
+
+  Overflowed = false;
+
+  // Log2(Z) would be either Log2Z or Log2Z + 1.
+  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
+  // will necessarily be less than Log2Max as desired.
+  int Log2Z = Log2_64 (X) + Log2_64 (Y);
+  const T Max = std::numeric_limits<T>::max ();
+  int Log2Max = Log2_64 (Max);
+  if (Log2Z < Log2Max)
+  {
+    return X * Y;
+  }
+  if (Log2Z > Log2Max)
+  {
+    Overflowed = true;
+    return Max;
+  }
+
+  // We're going to use the top bit, and maybe overflow one
+  // bit past it. Multiply all but the bottom bit then add
+  // that on at the end.
+  T Z = (X >> 1) * Y;
+  if (Z & ~(Max >> 1))
+  {
+    Overflowed = true;
+    return Max;
+  }
+  Z <<= 1;
+  if (X & 1)
+  {
+    return SaturatingAdd (Z, Y, ResultOverflowed);
+  }
+
+  return Z;
+}
+
+/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
+/// the product. Clamp the result to the maximum representable value of T on
+/// overflow. ResultOverflowed indicates if the result is larger than the
+/// maximum representable value of type T.
+template <typename T>
+std::enable_if_t<std::is_unsigned_v<T>, T>
+SaturatingMultiplyAdd (T X, T Y, T A, bool *ResultOverflowed = nullptr)
+{
+  bool Dummy;
+  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
+
+  T Product = SaturatingMultiply (X, Y, &Overflowed);
+  if (Overflowed)
+  {
+    return Product;
+  }
+
+  return SaturatingAdd (A, Product, &Overflowed);
+}
+
+/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
+RCC_ABI extern const float huge_valf;
+
+/// Add two signed integers, computing the two's complement truncated result,
+/// returning a pair {result, overflow}, where "overflow" is a boolean value
+/// indicating whether an overflow occurred.
+template <typename T>
+constexpr std::enable_if_t<std::is_signed_v<T>, std::pair<T, bool>>
+AddOverflow (T X, T Y)
+{
+  // Perform the unsigned addition.
+  using U = std::make_unsigned_t<T>;
+  const U UX = static_cast<U> (X);
+  const U UY = static_cast<U> (Y);
+  const U UResult = UX + UY;
+
+  // Convert to signed.
+  auto Result = static_cast<T> (UResult);
+
+  // Adding two positive numbers should result in a positive number.
+  if (X > 0 && Y > 0)
+  {
+    return {Result, Result <= 0};
+  }
+  // Adding two negatives should result in a negative number.
+  if (X < 0 && Y < 0)
+  {
+    return {Result, Result >= 0};
+  }
+  return {Result, false};
+}
+
+/// Add two signed integers, computing the two's complement truncated result,
+/// returning true if overflow occurred.
+template <typename T>
+std::enable_if_t<std::is_signed_v<T>, bool>
+AddOverflow (T X, T Y, T &Result)
+{
+#if __has_builtin(__builtin_add_overflow)
+  return __builtin_add_overflow (X, Y, &Result);
+#else
+  auto [Res, Ovf] = AddOverflow (X, Y);
+  Result = Res;
+  return Ovf;
+#endif
+}
+
+/// Subtract two signed integers, computing the two's complement truncated
+/// result, returning a pair {result, overflow}, where "overflow" is a
+/// boolean value indicating whether an overflow occurred.
+template <typename T>
+constexpr std::enable_if_t<std::is_signed_v<T>, std::pair<T, bool>>
+SubOverflow (T X, T Y)
+{
+  // Perform the unsigned addition.
+  using U = std::make_unsigned_t<T>;
+  const U UX = static_cast<U> (X);
+  const U UY = static_cast<U> (Y);
+  const U UResult = UX - UY;
+
+  // Convert to signed.
+  auto Result = static_cast<T> (UResult);
+
+  // Subtracting a positive number from a negative results in a negative number.
+  if (X <= 0 && Y > 0)
+  {
+    return {Result, Result >= 0};
+  }
+  // Subtracting a negative number from a positive results in a positive number.
+  if (X >= 0 && Y < 0)
+  {
+    return {Result, Result <= 0};
+  }
+  return {Result, false};
+}
+
+/// Subtract two signed integers, computing the two's complement truncated
+/// result, returning true if an overflow occurred.
+template <typename T>
+std::enable_if_t<std::is_signed_v<T>, bool>
+SubOverflow (T X, T Y, T &Result)
+{
+#if __has_builtin(__builtin_sub_overflow)
+  return __builtin_sub_overflow (X, Y, &Result);
+#else
+  auto [Res, Ovf] = SubOverflow (X, Y);
+  Result = Res;
+  return Ovf;
+#endif
+}
+
+/// Multiply two signed integers, computing the two's complement truncated
+/// result, returning a pair {result, overflow}, where "overflow" is a
+/// boolean value indicating whether an overflow occurred.
+template <typename T>
+constexpr std::enable_if_t<std::is_signed_v<T>, std::pair<T, bool>>
+MulOverflow (T X, T Y)
+{
+  // Perform the unsigned multiplication on absolute values.
+  using U = std::make_unsigned_t<T>;
+  const U UX = X < 0 ? (0 - static_cast<U> (X)) : static_cast<U> (X);
+  const U UY = Y < 0 ? (0 - static_cast<U> (Y)) : static_cast<U> (Y);
+  const U UResult = UX * UY;
+
+  // Convert to signed.
+  const bool IsNegative = (X < 0) ^ (Y < 0);
+  auto Result = IsNegative ? (0 - UResult) : UResult;
+
+  // If any of the args was 0, result is 0 and no overflow occurs.
+  if (UX == 0 || UY == 0)
+  {
+    return {Result, false};
+  }
+
+  // UX and UY are in [1, 2^n], where n is the number of digits.
+  // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
+  // positive) divided by an argument compares to the other.
+  bool Overflow =
+      IsNegative
+          ? UX > (static_cast<U> (std::numeric_limits<T>::max ()) + U (1)) / UY
+          : UX > (static_cast<U> (std::numeric_limits<T>::max ())) / UY;
+
+  return {Result, Overflow};
+}
+
+/// Multiply two signed integers, computing the two's complement truncated
+/// result, returning true if an overflow occurred.
+template <typename T>
+std::enable_if_t<std::is_signed_v<T>, bool>
+MulOverflow (T X, T Y, T &Result)
+{
+#if __has_builtin(__builtin_mul_overflow)
+  return __builtin_mul_overflow (X, Y, &Result);
+#else
+  auto [Res, Ovf] = MulOverflow (X, Y);
+  Result = Res;
+  return Ovf;
+#endif
+}
+
+/// Type to force float point values onto the stack, so that x86 doesn't add
+/// hidden precision, avoiding rounding differences on various platforms.
+#if defined(__i386__) || defined(_M_IX86)
+using stack_float_t = volatile float;
+#else
+using stack_float_t = float;
+#endif
+
+/// Returns the number of digits in the given integer.
+RCC_ABI int
+NumDigitsBase10 (uint64_t X);
+
+} // namespace rcc
+
+#endif
diff --git a/rcc/lib/CMakeLists.txt b/rcc/lib/CMakeLists.txt
index 366e6d2..6ab18c4 100644
--- a/rcc/lib/CMakeLists.txt
+++ b/rcc/lib/CMakeLists.txt
@@ -3,4 +3,5 @@
 add_rcc_library(RCCSupport
   STATIC
   Support/Errno.cc
+  Support/MathExtras.cc
 )
diff --git a/rcc/lib/Support/MathExtras.cc b/rcc/lib/Support/MathExtras.cc
new file mode 100644
index 0000000..f0db3a4
--- /dev/null
+++ b/rcc/lib/Support/MathExtras.cc
@@ -0,0 +1,97 @@
+/*
+ RCC-Project
+
+ Copyright (C) 2026 Richard Qin
+
+ This file is part of RCC-Project.
+
+ RCC-Project is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your option) any
+ later version.
+
+ RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ RCC-Project; see the file COPYING.  If not see
+ <http://www.gnu.org/licenses/>.
+*/
+
+//===-- MathExtras.cpp - Implement the MathExtras header --------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the MathExtras.h header
+//
+//===----------------------------------------------------------------------===//
+
+#include "rcc/Support/MathExtras.h"
+
+#ifdef _MSC_VER
+#include <limits>
+#else
+#include <cmath>
+#endif
+
+namespace rcc
+{
+
+#if defined(_MSC_VER)
+// Visual Studio defines the HUGE_VAL class of macros using purposeful
+// constant arithmetic overflow, which it then warns on when encountered.
+const float huge_valf = std::numeric_limits<float>::infinity ();
+#else
+const float huge_valf = HUGE_VALF;
+#endif
+
+/// Returns the number of digits in the given integer.
+int
+NumDigitsBase10 (uint64_t X)
+{
+  static constexpr struct ConstexprData
+  {
+    uint8_t AtLeast[65] = {};
+    uint64_t Boundaries[20] = {};
+    static constexpr int
+    NumDigitsConstexpr (uint64_t N)
+    {
+      int res = 1;
+      while (N >= 10)
+      {
+        res++;
+        N /= 10;
+      }
+      return res;
+    }
+    constexpr ConstexprData ()
+    {
+      uint64_t Val = ~0ull;
+      for (uint64_t i = 0; i <= 64; i++)
+      {
+        uint64_t Digits = NumDigitsConstexpr (Val) - 1;
+        AtLeast[i] = Digits;
+        Val >>= 1;
+      }
+      // Special case because X=0 should return 1 and not 0
+      Boundaries[0] = 0;
+      Val = 10;
+      for (uint64_t i = 1; i < 20; i++)
+      {
+        Boundaries[i] = Val;
+        Val *= 10;
+      }
+    }
+  } Data;
+
+  uint64_t Base2 = X ? std::countl_zero (X) : 64;
+  uint64_t Digits = Data.AtLeast[Base2];
+  return Digits + (X >= Data.Boundaries[Digits]);
+}
+
+} // namespace rcc