tick_math.gno
10.95 Kb ยท 326 lines
1package common
2
3import (
4 "gno.land/p/nt/ufmt"
5
6 i256 "gno.land/p/gnoswap/int256"
7 u256 "gno.land/p/gnoswap/uint256"
8)
9
10// Pre-calculated ratio constants for performance optimization.
11// These values are pre-computed to avoid runtime decimal parsing.
12var (
13 // Initial ratio constants - exactly matching Uniswap V3
14 ratio0 = u256.MustFromDecimal("340265354078544963557816517032075149313") // 0xfffcb933bd6fad37aa2d162d1a594001
15 ratio1 = u256.MustFromDecimal("340282366920938463463374607431768211456") // 0x100000000000000000000000000000000 (2^128)
16
17 // Bit mask ratio constants in order (bit 1 to bit 19)
18 ratioConstants = []*u256.Uint{
19 u256.MustFromDecimal("340248342086729790484326174814286782778"), // 0xfff97272373d413259a46990580e213a (bit 1)
20 u256.MustFromDecimal("340214320654664324051920982716015181260"), // 0xfff2e50f5f656932ef12357cf3c7fdcc (bit 2)
21 u256.MustFromDecimal("340146287995602323631171512101879684304"), // 0xffe5caca7e10e4e61c3624eaa0941cd0 (bit 3)
22 u256.MustFromDecimal("340010263488231146823593991679159461444"), // 0xffcb9843d60f6159c9db58835c926644 (bit 4)
23 u256.MustFromDecimal("339738377640345403697157401104375502016"), // 0xff973b41fa98c081472e6896dfb254c0 (bit 5)
24 u256.MustFromDecimal("339195258003219555707034227454543997025"), // 0xff2ea16466c96a3843ec78b326b52861 (bit 6)
25 u256.MustFromDecimal("338111622100601834656805679988414885971"), // 0xfe5dee046a99a2a811c461f1969c3053 (bit 7)
26 u256.MustFromDecimal("335954724994790223023589805789778977700"), // 0xfcbe86c7900a88aedcffc83b479aa3a4 (bit 8)
27 u256.MustFromDecimal("331682121138379247127172139078559817300"), // 0xf987a7253ac413176f2b074cf7815e54 (bit 9)
28 u256.MustFromDecimal("323299236684853023288211250268160618739"), // 0xf3392b0822b70005940c7a398e4b70f3 (bit 10)
29 u256.MustFromDecimal("307163716377032989948697243942600083929"), // 0xe7159475a2c29b7443b29c7fa6e889d9 (bit 11)
30 u256.MustFromDecimal("277268403626896220162999269216087595045"), // 0xd097f3bdfd2022b8845ad8f792aa5825 (bit 12)
31 u256.MustFromDecimal("225923453940442621947126027127485391333"), // 0xa9f746462d870fdf8a65dc1f90e061e5 (bit 13)
32 u256.MustFromDecimal("149997214084966997727330242082538205943"), // 0x70d869a156d2a1b890bb3df62baf32f7 (bit 14)
33 u256.MustFromDecimal("66119101136024775622716233608466517926"), // 0x31be135f97d08fd981231505542fcfa6 (bit 15)
34 u256.MustFromDecimal("12847376061809297530290974190478138313"), // 0x9aa508b5b7a84e1c677de54f3e99bc9 (bit 16)
35 u256.MustFromDecimal("485053260817066172746253684029974020"), // 0x5d6af8dedb81196699c329225ee604 (bit 17)
36 u256.MustFromDecimal("691415978906521570653435304214168"), // 0x2216e584f5fa1ea926041bedfe98 (bit 18)
37 u256.MustFromDecimal("1404880482679654955896180642"), // 0x48a170391f7dc42444e8fa2 (bit 19)
38 }
39
40 // Pre-computed constants for optimization
41 maxUint256 = u256.MustFromDecimal("115792089237316195423570985008687907853269984665640564039457584007913129639935") // 2^256 - 1
42 minSqrtRatio = u256.MustFromDecimal("4295128739") // same as TickMathGetSqrtRatioAtTick(minTick)
43 maxSqrtRatio = u256.MustFromDecimal("1461446703485210103287273052203988822378723970342") // same as TickMathGetSqrtRatioAtTick(maxTick)
44
45 // MSB calculation thresholds - pre-computed for performance
46 msb128Threshold = u256.MustFromDecimal("340282366920938463463374607431768211455") // 2^128 - 1
47 msb64Threshold = u256.MustFromDecimal("18446744073709551615") // 2^64 - 1
48 msb32Threshold = u256.MustFromDecimal("4294967295") // 2^32 - 1
49 msb16Threshold = u256.NewUint(65535) // 2^16 - 1
50 msb8Threshold = u256.NewUint(255) // 2^8 - 1
51 msb4Threshold = u256.NewUint(15) // 2^4 - 1
52 msb2Threshold = u256.NewUint(3) // 2^2 - 1
53 msb1Threshold = u256.One() // 1
54
55 // Pre-computed constants for tick calculation
56 log2Multiplier = i256.MustFromDecimal("255738958999603826347141")
57 tickLowOffset = i256.MustFromDecimal("3402992956809132418596140100660247210")
58 tickHiOffset = i256.MustFromDecimal("291339464771989622907027621153398088495")
59
60 oneLsh32 = u256.Zero().Lsh(u256.One(), 32) // 1 << 32
61)
62
63// TickMathGetSqrtRatioAtTick calculates sqrt price ratio for given tick.
64//
65// Converts tick index to square root price in Q64.96 fixed-point format.
66// Based on Uniswap V3's mathematical formula: price = 1.0001^tick.
67// Uses bit manipulation for gas-efficient calculation.
68//
69// Parameters:
70// - tick: Tick index in range [-887272, 887272]
71//
72// Returns:
73// - Square root of price ratio as Q64.96 fixed-point
74// - Result represents sqrt(token1/token0) price
75//
76// Mathematical formula:
77//
78// sqrtPriceX96 = sqrt(1.0001^tick) * 2^96
79//
80// Panics if tick outside valid range.
81// Critical for all price calculations in concentrated liquidity.
82func TickMathGetSqrtRatioAtTick(tick int32) *u256.Uint {
83 assertValidTickRange(tick)
84 absTick := abs(tick)
85
86 // Validate critical constants are initialized
87 if ratio0 == nil || ratio1 == nil {
88 panic(newErrorWithDetail(
89 errInvalidInput,
90 "ratio constants are not initialized",
91 ))
92 }
93
94 // Initialize ratio based on LSB - exactly like Uniswap V3
95 var ratio *u256.Uint
96
97 if absTick&0x1 != 0 {
98 ratio = ratio0.Clone()
99 } else {
100 ratio = ratio1.Clone()
101 }
102
103 temp := u256.Zero()
104
105 // Apply bit masks using optimized loop - maintains exact same logic
106 for i := 1; i < 20; i++ {
107 if absTick&(1<<uint(i)) != 0 {
108 // Use temporary variables to avoid memory allocation in hot path
109 r := ratioConstants[i-1]
110 if r == nil {
111 panic(newErrorWithDetail(
112 errInvalidInput,
113 "ratio constants are not initialized",
114 ))
115 }
116 temp, overflow := temp.MulOverflow(ratio, r)
117 if overflow {
118 panic(errOverflow)
119 }
120 ratio = ratio.Rsh(temp, 128)
121 }
122 }
123
124 // Invert ratio for positive ticks
125 if tick > 0 {
126 ratio = temp.Div(maxUint256, ratio)
127 }
128
129 // Convert from Q128.128 to Q128.96 with rounding up.
130 // This divides by 1<<32 rounding up to go from a Q128.128 to a Q128.96
131 upper := u256.Zero().Rsh(ratio, 32) // ratio >> 32
132 remainder := u256.Zero().Mod(ratio, oneLsh32) // ratio % (1 << 32)
133
134 // Round up: add 1 if remainder != 0
135 if !remainder.IsZero() {
136 upper = u256.Zero().Add(upper, u256.One())
137 }
138
139 return upper
140}
141
142// getMostSignificantBit returns the position of the most significant bit (MSB) in a uint256 value.
143// Uses binary search with pre-computed thresholds for efficient calculation.
144//
145// Parameters:
146// - r: uint256 value to find MSB for
147//
148// Returns:
149// - msb: position of the most significant bit (0-255)
150//
151// Used internally for logarithm calculations in tick math.
152func getMostSignificantBit(r *u256.Uint) (msb uint64) {
153 temp := r.Clone()
154
155 // Optimized MSB calculation using pre-computed thresholds
156 if temp.Gt(msb128Threshold) {
157 msb |= 128
158 temp = temp.Rsh(temp, 128)
159 }
160
161 if temp.Gt(msb64Threshold) {
162 msb |= 64
163 temp = temp.Rsh(temp, 64)
164 }
165
166 if temp.Gt(msb32Threshold) {
167 msb |= 32
168 temp = temp.Rsh(temp, 32)
169 }
170
171 if temp.Gt(msb16Threshold) {
172 msb |= 16
173 temp = temp.Rsh(temp, 16)
174 }
175
176 if temp.Gt(msb8Threshold) {
177 msb |= 8
178 temp = temp.Rsh(temp, 8)
179 }
180
181 if temp.Gt(msb4Threshold) {
182 msb |= 4
183 temp = temp.Rsh(temp, 4)
184 }
185
186 if temp.Gt(msb2Threshold) {
187 msb |= 2
188 temp = temp.Rsh(temp, 2)
189 }
190
191 if temp.Gt(msb1Threshold) {
192 msb |= 1
193 }
194
195 return
196}
197
198// TickMathGetTickAtSqrtRatio calculates the tick index for a given square root price ratio.
199//
200// Converts a square root price ratio in Q64.96 format back to its tick index,
201// returning the greatest tick where TickMathGetSqrtRatioAtTick(tick) <= sqrtPriceX96.
202// This matches Uniswap V3's behavior exactly.
203//
204// Parameters:
205// - sqrtPriceX96: Square root price ratio in Q64.96 format
206//
207// Returns:
208// - Tick index corresponding to the price
209//
210// Algorithm:
211// 1. Scales ratio from Q64.96 to Q96.128 by left-shifting 32 bits
212// 2. Finds MSB (most significant bit) to determine magnitude
213// 3. Calculates log_2 using fixed-point arithmetic
214// 4. Converts log_2 to log_sqrt(1.0001) to get tick
215// 5. Returns appropriate tick based on bounds checking
216//
217// Panics if sqrtPriceX96 is nil or outside valid range [minSqrtRatio, maxSqrtRatio).
218// Critical for converting prices to ticks for position management.
219func TickMathGetTickAtSqrtRatio(sqrtPriceX96 *u256.Uint) int32 {
220 if sqrtPriceX96 == nil {
221 panic(newErrorWithDetail(
222 errInvalidInput,
223 "sqrtPriceX96 cannot be nil",
224 ))
225 }
226
227 if sqrtPriceX96.Lt(minSqrtRatio) || sqrtPriceX96.Gte(maxSqrtRatio) {
228 panic(newErrorWithDetail(
229 errOutOfRange,
230 ufmt.Sprintf("sqrtPriceX96(%s) is out of range", sqrtPriceX96.ToString()),
231 ))
232 }
233
234 // Scale ratio by 32 bits to convert from Q64.96 to Q96.128
235 ratio := u256.Zero().Lsh(sqrtPriceX96, 32)
236
237 // Find MSB using optimized calculation
238 msb := getMostSignificantBit(ratio)
239
240 // Adjust ratio based on MSB
241 var r *u256.Uint
242
243 if msb >= 128 {
244 r = u256.Zero().Rsh(ratio, uint(msb-127))
245 } else {
246 r = u256.Zero().Lsh(ratio, uint(127-msb))
247 }
248
249 // Calculate log_2 using fixed-point arithmetic
250 log2 := i256.NewInt(int64(msb) - 128)
251 log2 = i256.Zero().Lsh(log2, 64)
252
253 // Define temporary variables for optimization
254 tempR := u256.Zero()
255 tempF := u256.Zero()
256 tempI256 := i256.Zero()
257
258 // Optimized iterative calculation using loop - maintains exact same logic
259 for i := 0; i < 14; i++ {
260 tempR, overflow := tempR.MulOverflow(r, r)
261 if overflow {
262 panic(errOverflow)
263 }
264 r = tempR.Rsh(tempR, 127)
265
266 tempF = tempF.Rsh(r, 128)
267 tempI256 = i256.FromUint256(tempF)
268 f := tempF
269
270 tempI256 = tempI256.Lsh(tempI256, uint(63-i))
271 log2 = log2.Or(log2, tempI256)
272 r = r.Rsh(r, uint(f.Uint64()))
273 }
274
275 // Calculate tick from log_sqrt10001
276 logSqrt10001, overflow := i256.Zero().MulOverflow(log2, log2Multiplier)
277 if overflow {
278 panic(errOverflow)
279 }
280
281 // Calculate tick bounds
282 tickLow := i256.Zero().Sub(logSqrt10001, tickLowOffset)
283 tickLow = tickLow.Rsh(tickLow, 128)
284 tickLowInt32 := int32(tickLow.Int64())
285
286 tickHi := i256.Zero().Add(logSqrt10001, tickHiOffset)
287 tickHi = tickHi.Rsh(tickHi, 128)
288 tickHiInt32 := int32(tickHi.Int64())
289
290 // Select the appropriate tick
291 if tickLowInt32 == tickHiInt32 {
292 return tickLowInt32
293 }
294
295 if TickMathGetSqrtRatioAtTick(tickHiInt32).Lte(sqrtPriceX96) {
296 return tickHiInt32
297 }
298
299 return tickLowInt32
300}
301
302// abs returns the absolute value of a signed 32-bit integer.
303// Used internally for tick math calculations to handle negative tick indices.
304func abs(x int32) int32 {
305 if x < 0 {
306 return -x
307 }
308
309 return x
310}
311
312// assertValidTickRange panics if tick is outside valid range [-887272, 887272].
313func assertValidTickRange(tick int32) {
314 if tick > maxTick {
315 panic(newErrorWithDetail(
316 errOutOfRange,
317 ufmt.Sprintf("tick is out of range (larger than 887272), tick: %d", tick),
318 ))
319 }
320 if tick < minTick {
321 panic(newErrorWithDetail(
322 errOutOfRange,
323 ufmt.Sprintf("tick is out of range (smaller than -887272), tick: %d", tick),
324 ))
325 }
326}
