tick_math.gno
9.08 Kb · 254 lines
1package gnsmath
2
3import (
4 "errors"
5
6 ufmt "gno.land/p/nt/ufmt/v0"
7
8 "gno.land/p/gnoswap/consts/v1"
9 i256 "gno.land/p/gnoswap/int256/v1"
10 u256 "gno.land/p/gnoswap/uint256/v1"
11)
12
13// Pre-calculated ratio constants for performance optimization.
14//
15// These were previously package-level vars (a slice plus 19 exposed pointers),
16// the exact "globally exposed mutable array" anti-pattern. They are now
17// constructors: each call returns freshly allocated values built from
18// little-endian [4]uint64 literals, so no caller shares a mutable instance and
19// no runtime decimal parsing happens. Values match Uniswap V3 exactly.
20
21// initialRatio returns the LSB-selected initial ratio.
22// absTick&0x1 != 0 selects ratio0 (0xfffcb933bd6fad37aa2d162d1a594001),
23// otherwise ratio1 (2^128).
24func initialRatio(odd bool) *u256.Uint {
25 if odd {
26 return &u256.Uint{12262481743371124737, 18445821805675392311, 0, 0} // 0xfffcb933bd6fad37aa2d162d1a594001
27 }
28 return &u256.Uint{0, 0, 1, 0} // 0x100000000000000000000000000000000 (2^128)
29}
30
31// ratioConstants returns the bit-mask ratio constants in order (bit 1 to bit 19).
32func ratioConstants() []*u256.Uint {
33 return []*u256.Uint{
34 {6459403834229662010, 18444899583751176498, 0, 0}, // 0xfff97272373d413259a46990580e213a (bit 1)
35 {17226890335427755468, 18443055278223354162, 0, 0}, // 0xfff2e50f5f656932ef12357cf3c7fdcc (bit 2)
36 {2032852871939366096, 18439367220385604838, 0, 0}, // 0xffe5caca7e10e4e61c3624eaa0941cd0 (bit 3)
37 {14545316742740207172, 18431993317065449817, 0, 0}, // 0xffcb9843d60f6159c9db58835c926644 (bit 4)
38 {5129152022828963008, 18417254355718160513, 0, 0}, // 0xff973b41fa98c081472e6896dfb254c0 (bit 5)
39 {4894419605888772193, 18387811781193591352, 0, 0}, // 0xff2ea16466c96a3843ec78b326b52861 (bit 6)
40 {1280255884321894483, 18329067761203520168, 0, 0}, // 0xfe5dee046a99a2a811c461f1969c3053 (bit 7)
41 {15924666964335305636, 18212142134806087854, 0, 0}, // 0xfcbe86c7900a88aedcffc83b479aa3a4 (bit 8)
42 {8010504389359918676, 17980523815641551639, 0, 0}, // 0xf987a7253ac413176f2b074cf7815e54 (bit 9)
43 {10668036004952895731, 17526086738831147013, 0, 0}, // 0xf3392b0822b70005940c7a398e4b70f3 (bit 10)
44 {4878133418470705625, 16651378430235024244, 0, 0}, // 0xe7159475a2c29b7443b29c7fa6e889d9 (bit 11)
45 {9537173718739605541, 15030750278693429944, 0, 0}, // 0xd097f3bdfd2022b8845ad8f792aa5825 (bit 12)
46 {9972618978014552549, 12247334978882834399, 0, 0}, // 0xa9f746462d870fdf8a65dc1f90e061e5 (bit 13)
47 {10428997489610666743, 8131365268884726200, 0, 0}, // 0x70d869a156d2a1b890bb3df62baf32f7 (bit 14)
48 {9305304367709015974, 3584323654723342297, 0, 0}, // 0x31be135f97d08fd981231505542fcfa6 (bit 15)
49 {14301143598189091785, 696457651847595233, 0, 0}, // 0x9aa508b5b7a84e1c677de54f3e99bc9 (bit 16)
50 {7393154844743099908, 26294789957452057, 0, 0}, // 0x5d6af8dedb81196699c329225ee604 (bit 17)
51 {2209338891292245656, 37481735321082, 0, 0}, // 0x2216e584f5fa1ea926041bedfe98 (bit 18)
52 {10518117631919034274, 76158723, 0, 0}, // 0x48a170391f7dc42444e8fa2 (bit 19)
53 }
54}
55
56// Pre-computed constants for tick calculation - returned as fresh instances per call.
57func log2Multiplier() *i256.Int { return &i256.Int{11745905768312294533, 13863, 0, 0} } // 255738958999603826347141
58
59func tickLowOffset() *i256.Int { return &i256.Int{6552757943157144234, 184476617836266586, 0, 0} } // 3402992956809132418596140100660247210
60
61func tickHiOffset() *i256.Int { return &i256.Int{4998474450511881007, 15793544031827761793, 0, 0} } // 291339464771989622907027621153398088495
62
63// oneLsh32 returns 1 << 32.
64func oneLsh32() *u256.Uint { return &u256.Uint{4294967296, 0, 0, 0} }
65
66// TickMathGetSqrtRatioAtTick calculates sqrt price ratio for given tick.
67//
68// Converts tick index to square root price in Q64.96 fixed-point format.
69// Based on Uniswap V3's mathematical formula: price = 1.0001^tick.
70// Uses bit manipulation for gas-efficient calculation.
71//
72// Parameters:
73// - tick: tick index in range [-887272, 887272]
74//
75// Returns:
76// - sqrtPriceX96: the Q64.96 square root of the token1/token0 price, rounded up
77//
78// Mathematical formula:
79//
80// sqrtPriceX96 = sqrt(1.0001^tick) * 2^96
81//
82// Panics if tick outside valid range.
83// Critical for all price calculations in concentrated liquidity.
84func TickMathGetSqrtRatioAtTick(tick int32) *u256.Uint {
85 assertValidTickRange(tick)
86 absTick := abs(tick)
87
88 // Initialize ratio based on LSB - exactly like Uniswap V3
89 ratio := initialRatio(absTick&0x1 != 0)
90
91 temp := u256.Zero()
92 masks := ratioConstants()
93
94 // Apply bit masks using optimized loop - maintains exact same logic
95 for i := 1; i < 20; i++ {
96 if absTick&(1<<uint(i)) != 0 {
97 // Use temporary variables to avoid memory allocation in hot path
98 r := masks[i-1]
99 temp, overflow := temp.MulOverflow(ratio, r)
100 if overflow {
101 panic(errors.New(errTickMathOverflow))
102 }
103 ratio = ratio.Rsh(temp, 128)
104 }
105 }
106
107 // Invert ratio for positive ticks
108 if tick > 0 {
109 ratio = temp.Div(consts.MaxUint256(), ratio)
110 }
111
112 // Convert from Q128.128 to Q128.96 with rounding up.
113 // This divides by 1<<32 rounding up to go from a Q128.128 to a Q128.96
114 upper := u256.Zero().Rsh(ratio, 32) // ratio >> 32
115 remainder := u256.Zero().Mod(ratio, oneLsh32()) // ratio % (1 << 32)
116
117 // Round up: add 1 if remainder != 0
118 if !remainder.IsZero() {
119 upper = u256.Zero().Add(upper, u256.One())
120 }
121
122 return upper
123}
124
125// TickMathGetTickAtSqrtRatio calculates the tick index for a given square root price ratio.
126//
127// Converts a square root price ratio in Q64.96 format back to its tick index,
128// returning the greatest tick where TickMathGetSqrtRatioAtTick(tick) <= sqrtPriceX96.
129// For this inverse API, sqrtPriceX96 must be in `[MinSqrtRatio, MaxSqrtRatio)`;
130// the upper bound equals the max-tick output but is itself excluded.
131//
132// Parameters:
133// - sqrtPriceX96: square root price ratio in Q64.96 format within [MinSqrtRatio, MaxSqrtRatio)
134//
135// Returns:
136// - tick: the greatest tick whose calculated ratio is at most sqrtPriceX96
137//
138// Algorithm:
139// 1. Scales ratio from Q64.96 to Q96.128 by left-shifting 32 bits
140// 2. Finds MSB (most significant bit) to determine magnitude
141// 3. Calculates log_2 using fixed-point arithmetic
142// 4. Converts log_2 to log_sqrt(1.0001) to get tick
143// 5. Returns appropriate tick based on bounds checking
144//
145// Panics if sqrtPriceX96 is nil or outside valid range [minSqrtRatio, maxSqrtRatio).
146// Critical for converting prices to ticks for position management.
147func TickMathGetTickAtSqrtRatio(sqrtPriceX96 *u256.Uint) int32 {
148 if sqrtPriceX96 == nil {
149 panic(newErrorWithDetail(
150 errTickMathInvalidInput,
151 "sqrtPriceX96 cannot be nil",
152 ))
153 }
154
155 if sqrtPriceX96.Lt(consts.MinSqrtRatio()) || sqrtPriceX96.Gte(consts.MaxSqrtRatio()) {
156 panic(newErrorWithDetail(
157 errTickMathOutOfRange,
158 ufmt.Sprintf("sqrtPriceX96(%s) is out of range", sqrtPriceX96.ToString()),
159 ))
160 }
161
162 // Scale ratio by 32 bits to convert from Q64.96 to Q96.128
163 ratio := u256.Zero().Lsh(sqrtPriceX96, 32)
164
165 // The validated ratio is nonzero; its bit length gives the MSB directly.
166 msb := uint64(ratio.BitLen() - 1)
167
168 // Adjust ratio based on MSB
169 var r *u256.Uint
170
171 if msb >= 128 {
172 r = u256.Zero().Rsh(ratio, uint(msb-127))
173 } else {
174 r = u256.Zero().Lsh(ratio, uint(127-msb))
175 }
176
177 // Calculate log_2 using fixed-point arithmetic
178 log2 := i256.NewInt(int64(msb) - 128)
179 log2 = i256.Zero().Lsh(log2, 64)
180
181 // Define temporary variables for optimization
182 tempR := u256.Zero()
183 tempF := u256.Zero()
184 tempI256 := i256.Zero()
185
186 // Optimized iterative calculation using loop - maintains exact same logic
187 for i := 0; i < 14; i++ {
188 tempR, overflow := tempR.MulOverflow(r, r)
189 if overflow {
190 panic(errors.New(errTickMathOverflow))
191 }
192 r = tempR.Rsh(tempR, 127)
193
194 tempF = tempF.Rsh(r, 128)
195 tempI256 = i256.FromUint256(tempF)
196 f := tempF
197
198 tempI256 = tempI256.Lsh(tempI256, uint(63-i))
199 log2 = log2.Or(log2, tempI256)
200 r = r.Rsh(r, uint(f.Uint64()))
201 }
202
203 // Calculate tick from log_sqrt10001
204 logSqrt10001, overflow := i256.Zero().MulOverflow(log2, log2Multiplier())
205 if overflow {
206 panic(errors.New(errTickMathOverflow))
207 }
208
209 // Calculate tick bounds
210 tickLow := i256.Zero().Sub(logSqrt10001, tickLowOffset())
211 tickLow = tickLow.Rsh(tickLow, 128)
212 tickLowInt32 := int32(tickLow.Int64())
213
214 tickHi := i256.Zero().Add(logSqrt10001, tickHiOffset())
215 tickHi = tickHi.Rsh(tickHi, 128)
216 tickHiInt32 := int32(tickHi.Int64())
217
218 // Select the appropriate tick
219 if tickLowInt32 == tickHiInt32 {
220 return tickLowInt32
221 }
222
223 if TickMathGetSqrtRatioAtTick(tickHiInt32).Lte(sqrtPriceX96) {
224 return tickHiInt32
225 }
226
227 return tickLowInt32
228}
229
230// abs returns the absolute value of a signed 32-bit integer.
231// Used internally for tick math calculations to handle negative tick indices.
232func abs(x int32) int32 {
233 if x < 0 {
234 return -x
235 }
236
237 return x
238}
239
240// assertValidTickRange panics if tick is outside valid range [-887272, 887272].
241func assertValidTickRange(tick int32) {
242 if tick > maxTick {
243 panic(newErrorWithDetail(
244 errTickMathOutOfRange,
245 ufmt.Sprintf("tick is out of range (larger than 887272), tick: %d", tick),
246 ))
247 }
248 if tick < minTick {
249 panic(newErrorWithDetail(
250 errTickMathOutOfRange,
251 ufmt.Sprintf("tick is out of range (smaller than -887272), tick: %d", tick),
252 ))
253 }
254}