amm.gno

  1package amm
  2
  3import (
  4	"math"
  5	"math/bits"
  6	"math/overflow"
  7)
  8
  9const bpsDen = int64(10000)
 10
 11// MulDiv returns floor(a * b / d) for non-negative a, b and d > 0.
 12// Fast path uses int64 product. Overflow path is 128-bit (a*b)/d — same as
 13// int64((bigint(a)*bigint(b))/bigint(d)) — and panics only if the quotient
 14// does not fit int64. Gno has no typed bigint(int64) conversion.
 15func MulDiv(a, b, d int64) int64 {
 16	return mulDiv(a, b, d, false)
 17}
 18
 19// MulDivCeil is ceil(a * b / d) for non-negative a, b and d > 0.
 20// Ceil only when remainder != 0.
 21func MulDivCeil(a, b, d int64) int64 {
 22	return mulDiv(a, b, d, true)
 23}
 24
 25func mulDiv(a, b, d int64, ceil bool) int64 {
 26	if a < 0 || b < 0 {
 27		panic("zdex: negative muldiv")
 28	}
 29	if d <= 0 {
 30		panic("zdex: division by zero")
 31	}
 32	if a == 0 || b == 0 {
 33		return 0
 34	}
 35	prod, ok := overflow.Mul64(a, b)
 36	if ok {
 37		q := prod / d
 38		if ceil && prod%d != 0 {
 39			return add64(q, 1)
 40		}
 41		return q
 42	}
 43	hi, lo := bits.Mul64(uint64(a), uint64(b))
 44	du := uint64(d)
 45	if hi >= du {
 46		panic("zdex: muldiv overflow")
 47	}
 48	q, r := bits.Div64(hi, lo, du)
 49	if ceil && r != 0 {
 50		if q == uint64(math.MaxInt64) {
 51			panic("zdex: muldiv overflow")
 52		}
 53		q++
 54	}
 55	if q > uint64(math.MaxInt64) {
 56		panic("zdex: muldiv overflow")
 57	}
 58	return int64(q)
 59}
 60
 61// Sqrt returns floor(sqrt(n)) for n >= 0 (Babylonian method).
 62func Sqrt(n int64) int64 {
 63	if n < 0 {
 64		panic("zdex: sqrt of negative")
 65	}
 66	if n < 2 {
 67		return n
 68	}
 69	x := n
 70	y := (x + 1) / 2
 71	for y < x {
 72		x = y
 73		y = (x + n/x) / 2
 74	}
 75	return x
 76}
 77
 78func add64(a, b int64) int64 {
 79	s, ok := overflow.Add64(a, b)
 80	if !ok {
 81		panic("zdex: add overflow")
 82	}
 83	return s
 84}
 85
 86// AmountOut is Uniswap-v2 getAmountOut against effective (real+virtual) reserves.
 87// Payout is capped by the real reserveOut — virtual offsets only affect price.
 88func AmountOut(amountIn, reserveIn, virtualIn, reserveOut, virtualOut, feeBps int64) int64 {
 89	if amountIn <= 0 {
 90		panic("zdex: amountIn must be positive")
 91	}
 92	if feeBps < 0 || feeBps >= bpsDen {
 93		panic("zdex: feeBps out of range")
 94	}
 95	x := add64(reserveIn, virtualIn)
 96	y := add64(reserveOut, virtualOut)
 97	if x <= 0 || y <= 0 {
 98		panic("zdex: empty effective reserves")
 99	}
100	fee := MulDiv(amountIn, feeBps, bpsDen)
101	net := amountIn - fee
102	if net <= 0 {
103		panic("zdex: fee consumes input")
104	}
105	out := MulDiv(net, y, add64(x, net))
106	if out <= 0 {
107		panic("zdex: zero output")
108	}
109	if out >= y {
110		panic("zdex: would drain effective reserve")
111	}
112	if out >= reserveOut {
113		panic("zdex: insufficient real reserve")
114	}
115	return out
116}
117
118// AmountIn is the ugnot/token that must be paid so AmountOut >= amountOut.
119// Rounded up so ExactOut does not underpay.
120func AmountIn(amountOut, reserveIn, virtualIn, reserveOut, virtualOut, feeBps int64) int64 {
121	if amountOut <= 0 {
122		panic("zdex: amountOut must be positive")
123	}
124	if feeBps < 0 || feeBps >= bpsDen {
125		panic("zdex: feeBps out of range")
126	}
127	if amountOut >= reserveOut {
128		panic("zdex: insufficient real reserve")
129	}
130	x := add64(reserveIn, virtualIn)
131	y := add64(reserveOut, virtualOut)
132	if x <= 0 || y <= 0 {
133		panic("zdex: empty effective reserves")
134	}
135	if amountOut >= y {
136		panic("zdex: would drain effective reserve")
137	}
138	net := MulDivCeil(amountOut, x, y-amountOut)
139	in := MulDivCeil(net, bpsDen, bpsDen-feeBps)
140	if in <= 0 {
141		panic("zdex: zero input")
142	}
143	got := AmountOut(in, reserveIn, virtualIn, reserveOut, virtualOut, feeBps)
144	if got < amountOut {
145		in = add64(in, 1)
146	}
147	return in
148}