tick_math.gno
11.04 Kb · 320 lines
1package gnsmath
2
3import (
4 "errors"
5
6 ufmt "gno.land/p/nt/ufmt/v0"
7
8 "gno.land/p/gnoswap/consts"
9 i256 "gno.land/p/gnoswap/int256"
10 u256 "gno.land/p/gnoswap/uint256"
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 &u256.Uint{6459403834229662010, 18444899583751176498, 0, 0}, // 0xfff97272373d413259a46990580e213a (bit 1)
35 &u256.Uint{17226890335427755468, 18443055278223354162, 0, 0}, // 0xfff2e50f5f656932ef12357cf3c7fdcc (bit 2)
36 &u256.Uint{2032852871939366096, 18439367220385604838, 0, 0}, // 0xffe5caca7e10e4e61c3624eaa0941cd0 (bit 3)
37 &u256.Uint{14545316742740207172, 18431993317065449817, 0, 0}, // 0xffcb9843d60f6159c9db58835c926644 (bit 4)
38 &u256.Uint{5129152022828963008, 18417254355718160513, 0, 0}, // 0xff973b41fa98c081472e6896dfb254c0 (bit 5)
39 &u256.Uint{4894419605888772193, 18387811781193591352, 0, 0}, // 0xff2ea16466c96a3843ec78b326b52861 (bit 6)
40 &u256.Uint{1280255884321894483, 18329067761203520168, 0, 0}, // 0xfe5dee046a99a2a811c461f1969c3053 (bit 7)
41 &u256.Uint{15924666964335305636, 18212142134806087854, 0, 0}, // 0xfcbe86c7900a88aedcffc83b479aa3a4 (bit 8)
42 &u256.Uint{8010504389359918676, 17980523815641551639, 0, 0}, // 0xf987a7253ac413176f2b074cf7815e54 (bit 9)
43 &u256.Uint{10668036004952895731, 17526086738831147013, 0, 0}, // 0xf3392b0822b70005940c7a398e4b70f3 (bit 10)
44 &u256.Uint{4878133418470705625, 16651378430235024244, 0, 0}, // 0xe7159475a2c29b7443b29c7fa6e889d9 (bit 11)
45 &u256.Uint{9537173718739605541, 15030750278693429944, 0, 0}, // 0xd097f3bdfd2022b8845ad8f792aa5825 (bit 12)
46 &u256.Uint{9972618978014552549, 12247334978882834399, 0, 0}, // 0xa9f746462d870fdf8a65dc1f90e061e5 (bit 13)
47 &u256.Uint{10428997489610666743, 8131365268884726200, 0, 0}, // 0x70d869a156d2a1b890bb3df62baf32f7 (bit 14)
48 &u256.Uint{9305304367709015974, 3584323654723342297, 0, 0}, // 0x31be135f97d08fd981231505542fcfa6 (bit 15)
49 &u256.Uint{14301143598189091785, 696457651847595233, 0, 0}, // 0x9aa508b5b7a84e1c677de54f3e99bc9 (bit 16)
50 &u256.Uint{7393154844743099908, 26294789957452057, 0, 0}, // 0x5d6af8dedb81196699c329225ee604 (bit 17)
51 &u256.Uint{2209338891292245656, 37481735321082, 0, 0}, // 0x2216e584f5fa1ea926041bedfe98 (bit 18)
52 &u256.Uint{10518117631919034274, 76158723, 0, 0}, // 0x48a170391f7dc42444e8fa2 (bit 19)
53 }
54}
55
56// MSB calculation thresholds - returned as fresh instances per call.
57func msb128Threshold() *u256.Uint {
58 return &u256.Uint{18446744073709551615, 18446744073709551615, 0, 0}
59} // 2^128 - 1
60func msb64Threshold() *u256.Uint { return &u256.Uint{18446744073709551615, 0, 0, 0} } // 2^64 - 1
61func msb32Threshold() *u256.Uint { return &u256.Uint{4294967295, 0, 0, 0} } // 2^32 - 1
62func msb16Threshold() *u256.Uint { return &u256.Uint{65535, 0, 0, 0} } // 2^16 - 1
63func msb8Threshold() *u256.Uint { return &u256.Uint{255, 0, 0, 0} } // 2^8 - 1
64func msb4Threshold() *u256.Uint { return &u256.Uint{15, 0, 0, 0} } // 2^4 - 1
65func msb2Threshold() *u256.Uint { return &u256.Uint{3, 0, 0, 0} } // 2^2 - 1
66func msb1Threshold() *u256.Uint { return &u256.Uint{1, 0, 0, 0} } // 1
67
68// Pre-computed constants for tick calculation - returned as fresh instances per call.
69func log2Multiplier() *i256.Int { return &i256.Int{11745905768312294533, 13863, 0, 0} } // 255738958999603826347141
70func tickLowOffset() *i256.Int { return &i256.Int{6552757943157144234, 184476617836266586, 0, 0} } // 3402992956809132418596140100660247210
71func tickHiOffset() *i256.Int { return &i256.Int{4998474450511881007, 15793544031827761793, 0, 0} } // 291339464771989622907027621153398088495
72
73// oneLsh32 returns 1 << 32.
74func oneLsh32() *u256.Uint { return &u256.Uint{4294967296, 0, 0, 0} }
75
76// TickMathGetSqrtRatioAtTick calculates sqrt price ratio for given tick.
77//
78// Converts tick index to square root price in Q64.96 fixed-point format.
79// Based on Uniswap V3's mathematical formula: price = 1.0001^tick.
80// Uses bit manipulation for gas-efficient calculation.
81//
82// Parameters:
83// - tick: Tick index in range [-887272, 887272]
84//
85// Returns:
86// - Square root of price ratio as Q64.96 fixed-point
87// - Result represents sqrt(token1/token0) price
88//
89// Mathematical formula:
90//
91// sqrtPriceX96 = sqrt(1.0001^tick) * 2^96
92//
93// Panics if tick outside valid range.
94// Critical for all price calculations in concentrated liquidity.
95func TickMathGetSqrtRatioAtTick(tick int32) *u256.Uint {
96 assertValidTickRange(tick)
97 absTick := abs(tick)
98
99 // Initialize ratio based on LSB - exactly like Uniswap V3
100 ratio := initialRatio(absTick&0x1 != 0)
101
102 temp := u256.Zero()
103 masks := ratioConstants()
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 := masks[i-1]
110 temp, overflow := temp.MulOverflow(ratio, r)
111 if overflow {
112 panic(errors.New(errTickMathOverflow))
113 }
114 ratio = ratio.Rsh(temp, 128)
115 }
116 }
117
118 // Invert ratio for positive ticks
119 if tick > 0 {
120 ratio = temp.Div(consts.MaxUint256(), ratio)
121 }
122
123 // Convert from Q128.128 to Q128.96 with rounding up.
124 // This divides by 1<<32 rounding up to go from a Q128.128 to a Q128.96
125 upper := u256.Zero().Rsh(ratio, 32) // ratio >> 32
126 remainder := u256.Zero().Mod(ratio, oneLsh32()) // ratio % (1 << 32)
127
128 // Round up: add 1 if remainder != 0
129 if !remainder.IsZero() {
130 upper = u256.Zero().Add(upper, u256.One())
131 }
132
133 return upper
134}
135
136// getMostSignificantBit returns the position of the most significant bit (MSB) in a uint256 value.
137// Uses binary search with pre-computed thresholds for efficient calculation.
138//
139// Parameters:
140// - r: uint256 value to find MSB for
141//
142// Returns:
143// - msb: position of the most significant bit (0-255)
144//
145// Used internally for logarithm calculations in tick math.
146func getMostSignificantBit(r *u256.Uint) (msb uint64) {
147 temp := r.Clone()
148
149 // Optimized MSB calculation using pre-computed thresholds
150 if temp.Gt(msb128Threshold()) {
151 msb |= 128
152 temp = temp.Rsh(temp, 128)
153 }
154
155 if temp.Gt(msb64Threshold()) {
156 msb |= 64
157 temp = temp.Rsh(temp, 64)
158 }
159
160 if temp.Gt(msb32Threshold()) {
161 msb |= 32
162 temp = temp.Rsh(temp, 32)
163 }
164
165 if temp.Gt(msb16Threshold()) {
166 msb |= 16
167 temp = temp.Rsh(temp, 16)
168 }
169
170 if temp.Gt(msb8Threshold()) {
171 msb |= 8
172 temp = temp.Rsh(temp, 8)
173 }
174
175 if temp.Gt(msb4Threshold()) {
176 msb |= 4
177 temp = temp.Rsh(temp, 4)
178 }
179
180 if temp.Gt(msb2Threshold()) {
181 msb |= 2
182 temp = temp.Rsh(temp, 2)
183 }
184
185 if temp.Gt(msb1Threshold()) {
186 msb |= 1
187 }
188
189 return
190}
191
192// TickMathGetTickAtSqrtRatio calculates the tick index for a given square root price ratio.
193//
194// Converts a square root price ratio in Q64.96 format back to its tick index,
195// returning the greatest tick where TickMathGetSqrtRatioAtTick(tick) <= sqrtPriceX96.
196// This matches Uniswap V3's behavior exactly.
197//
198// Parameters:
199// - sqrtPriceX96: Square root price ratio in Q64.96 format
200//
201// Returns:
202// - Tick index corresponding to the price
203//
204// Algorithm:
205// 1. Scales ratio from Q64.96 to Q96.128 by left-shifting 32 bits
206// 2. Finds MSB (most significant bit) to determine magnitude
207// 3. Calculates log_2 using fixed-point arithmetic
208// 4. Converts log_2 to log_sqrt(1.0001) to get tick
209// 5. Returns appropriate tick based on bounds checking
210//
211// Panics if sqrtPriceX96 is nil or outside valid range [minSqrtRatio, maxSqrtRatio).
212// Critical for converting prices to ticks for position management.
213func TickMathGetTickAtSqrtRatio(sqrtPriceX96 *u256.Uint) int32 {
214 if sqrtPriceX96 == nil {
215 panic(newErrorWithDetail(
216 errTickMathInvalidInput,
217 "sqrtPriceX96 cannot be nil",
218 ))
219 }
220
221 if sqrtPriceX96.Lt(consts.MinSqrtRatio()) || sqrtPriceX96.Gte(consts.MaxSqrtRatio()) {
222 panic(newErrorWithDetail(
223 errTickMathOutOfRange,
224 ufmt.Sprintf("sqrtPriceX96(%s) is out of range", sqrtPriceX96.ToString()),
225 ))
226 }
227
228 // Scale ratio by 32 bits to convert from Q64.96 to Q96.128
229 ratio := u256.Zero().Lsh(sqrtPriceX96, 32)
230
231 // Find MSB using optimized calculation
232 msb := getMostSignificantBit(ratio)
233
234 // Adjust ratio based on MSB
235 var r *u256.Uint
236
237 if msb >= 128 {
238 r = u256.Zero().Rsh(ratio, uint(msb-127))
239 } else {
240 r = u256.Zero().Lsh(ratio, uint(127-msb))
241 }
242
243 // Calculate log_2 using fixed-point arithmetic
244 log2 := i256.NewInt(int64(msb) - 128)
245 log2 = i256.Zero().Lsh(log2, 64)
246
247 // Define temporary variables for optimization
248 tempR := u256.Zero()
249 tempF := u256.Zero()
250 tempI256 := i256.Zero()
251
252 // Optimized iterative calculation using loop - maintains exact same logic
253 for i := 0; i < 14; i++ {
254 tempR, overflow := tempR.MulOverflow(r, r)
255 if overflow {
256 panic(errors.New(errTickMathOverflow))
257 }
258 r = tempR.Rsh(tempR, 127)
259
260 tempF = tempF.Rsh(r, 128)
261 tempI256 = i256.FromUint256(tempF)
262 f := tempF
263
264 tempI256 = tempI256.Lsh(tempI256, uint(63-i))
265 log2 = log2.Or(log2, tempI256)
266 r = r.Rsh(r, uint(f.Uint64()))
267 }
268
269 // Calculate tick from log_sqrt10001
270 logSqrt10001, overflow := i256.Zero().MulOverflow(log2, log2Multiplier())
271 if overflow {
272 panic(errors.New(errTickMathOverflow))
273 }
274
275 // Calculate tick bounds
276 tickLow := i256.Zero().Sub(logSqrt10001, tickLowOffset())
277 tickLow = tickLow.Rsh(tickLow, 128)
278 tickLowInt32 := int32(tickLow.Int64())
279
280 tickHi := i256.Zero().Add(logSqrt10001, tickHiOffset())
281 tickHi = tickHi.Rsh(tickHi, 128)
282 tickHiInt32 := int32(tickHi.Int64())
283
284 // Select the appropriate tick
285 if tickLowInt32 == tickHiInt32 {
286 return tickLowInt32
287 }
288
289 if TickMathGetSqrtRatioAtTick(tickHiInt32).Lte(sqrtPriceX96) {
290 return tickHiInt32
291 }
292
293 return tickLowInt32
294}
295
296// abs returns the absolute value of a signed 32-bit integer.
297// Used internally for tick math calculations to handle negative tick indices.
298func abs(x int32) int32 {
299 if x < 0 {
300 return -x
301 }
302
303 return x
304}
305
306// assertValidTickRange panics if tick is outside valid range [-887272, 887272].
307func assertValidTickRange(tick int32) {
308 if tick > maxTick {
309 panic(newErrorWithDetail(
310 errTickMathOutOfRange,
311 ufmt.Sprintf("tick is out of range (larger than 887272), tick: %d", tick),
312 ))
313 }
314 if tick < minTick {
315 panic(newErrorWithDetail(
316 errTickMathOutOfRange,
317 ufmt.Sprintf("tick is out of range (smaller than -887272), tick: %d", tick),
318 ))
319 }
320}
