fullmath.gno

  1// REF: https://github.com/Uniswap/v3-core/blob/main/contracts/libraries/FullMath.sol
  2
  3// fullmath implements Uniswap V3's FullMath library.
  4//
  5// This library provides advanced fixed-point math operations that are essential
  6// for Uniswap V3's tick math and liquidity calculations. It enables precise
  7// calculations of (a * b / denominator) with full 512-bit intermediate precision.
  8//
  9// NOTE: Unlike the base arithmetic methods in the uint256 package, which return
 10// low-256-bit values (or values plus overflow flags in their `*Overflow`
 11// variants), functions in this file panic on invalid inputs to maintain
 12// behavioral compatibility with the original Solidity implementation.
 13//
 14// This design choice is intentional because:
 15// 1. These functions are typically used in hot paths where error handling would add overhead
 16// 2. Invalid inputs (like zero denominator) represent programming errors, not runtime conditions
 17// 3. Staying close to the Solidity implementation makes protocol porting more reliable
 18//
 19// If you need error-returning versions, wrap these functions with appropriate error handling.
 20package uint256
 21
 22// MulDiv computes floor((a * b) / denominator) with a full 512-bit intermediate product.
 23//
 24// Parameters:
 25//   - a: First non-negative 256-bit multiplicand.
 26//   - b: Second non-negative 256-bit multiplicand.
 27//   - denominator: Non-zero 256-bit divisor.
 28//
 29// Returns:
 30//   - quotient: The exact floor quotient when it fits in 256 bits.
 31//
 32// Panics if denominator is zero or the quotient is at least 2^256.
 33func MulDiv(a, b, denominator *Uint) *Uint {
 34	if denominator.IsZero() {
 35		panic("denominator must be greater than 0")
 36	}
 37
 38	// 512-bit product (8 limbs of 64 bits)
 39	p := umul(a, b)
 40
 41	if (p[4] | p[5] | p[6] | p[7]) == 0 {
 42		var lo Uint
 43		lo[0], lo[1], lo[2], lo[3] = p[0], p[1], p[2], p[3]
 44		return new(Uint).Div(&lo, denominator)
 45	}
 46
 47	// optional early overflow check:
 48	// If hi >= denominator then floor((hi*2^256 + lo) / denominator) >= 2^256, which is overflow.
 49	{
 50		var hi Uint
 51		hi[0], hi[1], hi[2], hi[3] = p[4], p[5], p[6], p[7]
 52		if denominator.Lte(&hi) {
 53			panic("overflow: denominator(" + denominator.ToString() + ") must be greater than hi(" + hi.ToString() + ")")
 54		}
 55	}
 56
 57	// perform 512 / 256 division
 58	// udivrem stores quotient into `quot` (len(u) - len(d) + 1 words)
 59	// we pass 8 words to be safe.
 60	var quot [8]uint64
 61	udivrem(quot[:], p[:], denominator) // ignore remainder
 62
 63	if (quot[4] | quot[5] | quot[6] | quot[7]) != 0 {
 64		panic("uint256: MulDiv overflow (high quotient words non-zero)")
 65	}
 66
 67	// return lower 256 bits of quotient
 68	var z Uint
 69	copy(z[:], quot[:4])
 70	return &z
 71}
 72
 73// MulDivRoundingUp computes ceil((a * b) / denominator) with a full 512-bit intermediate product.
 74//
 75// Parameters:
 76//   - a: First non-negative 256-bit multiplicand.
 77//   - b: Second non-negative 256-bit multiplicand.
 78//   - denominator: Non-zero 256-bit divisor.
 79//
 80// Returns:
 81//   - quotient: The ceiling quotient; it is one greater than the floor quotient
 82//     exactly when the product has a non-zero remainder.
 83//
 84// Panics if denominator is zero or rounding the result exceeds 256 bits.
 85func MulDivRoundingUp(a, b, denominator *Uint) *Uint {
 86	result := MulDiv(a, b, denominator)
 87
 88	// Check if there's a remainder
 89	mulModResult := new(Uint).MulMod(a, b, denominator)
 90
 91	// If there's no remainder, return the result as-is
 92	if mulModResult.IsZero() {
 93		return result
 94	}
 95
 96	// Add 1 to round up, but check for overflow
 97	if result.Eq(MaxUint256()) {
 98		panic("overflow: result(" + result.ToString() + ") + 1 would exceed MAX_UINT256")
 99	}
100
101	return result.Add(result, &Uint{1, 0, 0, 0})
102}
103
104// DivRoundingUp computes ceil(x / y) for unsigned 256-bit operands.
105//
106// Parameters:
107//   - x: Non-negative 256-bit dividend.
108//   - y: Non-zero 256-bit divisor.
109//
110// Returns:
111//   - quotient: The quotient rounded toward positive infinity.
112//
113// Panics if y is zero.
114func DivRoundingUp(x, y *Uint) *Uint {
115	div, mod := new(Uint).DivMod(x, y, new(Uint))
116	if !mod.IsZero() {
117		div.Add(div, &Uint{1, 0, 0, 0})
118	}
119	return div
120}