-
Notifications
You must be signed in to change notification settings - Fork 961
/
TickMath.sol
238 lines (214 loc) · 12.1 KB
/
TickMath.sol
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import {BitMath} from "./BitMath.sol";
import {CustomRevert} from "./CustomRevert.sol";
/// @title Math library for computing sqrt prices from ticks and vice versa
/// @notice Computes sqrt price for ticks of size 1.0001, i.e. sqrt(1.0001^tick) as fixed point Q64.96 numbers. Supports
/// prices between 2**-128 and 2**128
library TickMath {
using CustomRevert for bytes4;
/// @notice Thrown when the tick passed to #getSqrtPriceAtTick is not between MIN_TICK and MAX_TICK
error InvalidTick(int24 tick);
/// @notice Thrown when the price passed to #getTickAtSqrtPrice does not correspond to a price between MIN_TICK and MAX_TICK
error InvalidSqrtPrice(uint160 sqrtPriceX96);
/// @dev The minimum tick that may be passed to #getSqrtPriceAtTick computed from log base 1.0001 of 2**-128
/// @dev If ever MIN_TICK and MAX_TICK are not centered around 0, the absTick logic in getSqrtPriceAtTick cannot be used
int24 internal constant MIN_TICK = -887272;
/// @dev The maximum tick that may be passed to #getSqrtPriceAtTick computed from log base 1.0001 of 2**128
/// @dev If ever MIN_TICK and MAX_TICK are not centered around 0, the absTick logic in getSqrtPriceAtTick cannot be used
int24 internal constant MAX_TICK = 887272;
/// @dev The minimum tick spacing value drawn from the range of type int16 that is greater than 0, i.e. min from the range [1, 32767]
int24 internal constant MIN_TICK_SPACING = 1;
/// @dev The maximum tick spacing value drawn from the range of type int16, i.e. max from the range [1, 32767]
int24 internal constant MAX_TICK_SPACING = type(int16).max;
/// @dev The minimum value that can be returned from #getSqrtPriceAtTick. Equivalent to getSqrtPriceAtTick(MIN_TICK)
uint160 internal constant MIN_SQRT_PRICE = 4295128739;
/// @dev The maximum value that can be returned from #getSqrtPriceAtTick. Equivalent to getSqrtPriceAtTick(MAX_TICK)
uint160 internal constant MAX_SQRT_PRICE = 1461446703485210103287273052203988822378723970342;
/// @dev A threshold used for optimized bounds check, equals `MAX_SQRT_PRICE - MIN_SQRT_PRICE - 1`
uint160 internal constant MAX_SQRT_PRICE_MINUS_MIN_SQRT_PRICE_MINUS_ONE =
1461446703485210103287273052203988822378723970342 - 4295128739 - 1;
/// @notice Given a tickSpacing, compute the maximum usable tick
function maxUsableTick(int24 tickSpacing) internal pure returns (int24) {
unchecked {
return (MAX_TICK / tickSpacing) * tickSpacing;
}
}
/// @notice Given a tickSpacing, compute the minimum usable tick
function minUsableTick(int24 tickSpacing) internal pure returns (int24) {
unchecked {
return (MIN_TICK / tickSpacing) * tickSpacing;
}
}
/// @notice Calculates sqrt(1.0001^tick) * 2^96
/// @dev Throws if |tick| > max tick
/// @param tick The input tick for the above formula
/// @return sqrtPriceX96 A Fixed point Q64.96 number representing the sqrt of the price of the two assets (currency1/currency0)
/// at the given tick
function getSqrtPriceAtTick(int24 tick) internal pure returns (uint160 sqrtPriceX96) {
unchecked {
uint256 absTick;
assembly ("memory-safe") {
tick := signextend(2, tick)
// mask = 0 if tick >= 0 else -1 (all 1s)
let mask := sar(255, tick)
// if tick >= 0, |tick| = tick = 0 ^ tick
// if tick < 0, |tick| = ~~|tick| = ~(-|tick| - 1) = ~(tick - 1) = (-1) ^ (tick - 1)
// either way, |tick| = mask ^ (tick + mask)
absTick := xor(mask, add(mask, tick))
}
if (absTick > uint256(int256(MAX_TICK))) InvalidTick.selector.revertWith(tick);
// The tick is decomposed into bits, and for each bit with index i that is set, the product of 1/sqrt(1.0001^(2^i))
// is calculated (using Q128.128). The constants used for this calculation are rounded to the nearest integer
// Equivalent to:
// price = absTick & 0x1 != 0 ? 0xfffcb933bd6fad37aa2d162d1a594001 : 0x100000000000000000000000000000000;
// or price = int(2**128 / sqrt(1.0001)) if (absTick & 0x1) else 1 << 128
uint256 price;
assembly ("memory-safe") {
price := xor(shl(128, 1), mul(xor(shl(128, 1), 0xfffcb933bd6fad37aa2d162d1a594001), and(absTick, 0x1)))
}
if (absTick & 0x2 != 0) price = (price * 0xfff97272373d413259a46990580e213a) >> 128;
if (absTick & 0x4 != 0) price = (price * 0xfff2e50f5f656932ef12357cf3c7fdcc) >> 128;
if (absTick & 0x8 != 0) price = (price * 0xffe5caca7e10e4e61c3624eaa0941cd0) >> 128;
if (absTick & 0x10 != 0) price = (price * 0xffcb9843d60f6159c9db58835c926644) >> 128;
if (absTick & 0x20 != 0) price = (price * 0xff973b41fa98c081472e6896dfb254c0) >> 128;
if (absTick & 0x40 != 0) price = (price * 0xff2ea16466c96a3843ec78b326b52861) >> 128;
if (absTick & 0x80 != 0) price = (price * 0xfe5dee046a99a2a811c461f1969c3053) >> 128;
if (absTick & 0x100 != 0) price = (price * 0xfcbe86c7900a88aedcffc83b479aa3a4) >> 128;
if (absTick & 0x200 != 0) price = (price * 0xf987a7253ac413176f2b074cf7815e54) >> 128;
if (absTick & 0x400 != 0) price = (price * 0xf3392b0822b70005940c7a398e4b70f3) >> 128;
if (absTick & 0x800 != 0) price = (price * 0xe7159475a2c29b7443b29c7fa6e889d9) >> 128;
if (absTick & 0x1000 != 0) price = (price * 0xd097f3bdfd2022b8845ad8f792aa5825) >> 128;
if (absTick & 0x2000 != 0) price = (price * 0xa9f746462d870fdf8a65dc1f90e061e5) >> 128;
if (absTick & 0x4000 != 0) price = (price * 0x70d869a156d2a1b890bb3df62baf32f7) >> 128;
if (absTick & 0x8000 != 0) price = (price * 0x31be135f97d08fd981231505542fcfa6) >> 128;
if (absTick & 0x10000 != 0) price = (price * 0x9aa508b5b7a84e1c677de54f3e99bc9) >> 128;
if (absTick & 0x20000 != 0) price = (price * 0x5d6af8dedb81196699c329225ee604) >> 128;
if (absTick & 0x40000 != 0) price = (price * 0x2216e584f5fa1ea926041bedfe98) >> 128;
if (absTick & 0x80000 != 0) price = (price * 0x48a170391f7dc42444e8fa2) >> 128;
assembly ("memory-safe") {
// if (tick > 0) price = type(uint256).max / price;
if sgt(tick, 0) { price := div(not(0), price) }
// this divides by 1<<32 rounding up to go from a Q128.128 to a Q128.96.
// we then downcast because we know the result always fits within 160 bits due to our tick input constraint
// we round up in the division so getTickAtSqrtPrice of the output price is always consistent
// `sub(shl(32, 1), 1)` is `type(uint32).max`
// `price + type(uint32).max` will not overflow because `price` fits in 192 bits
sqrtPriceX96 := shr(32, add(price, sub(shl(32, 1), 1)))
}
}
}
/// @notice Calculates the greatest tick value such that getSqrtPriceAtTick(tick) <= sqrtPriceX96
/// @dev Throws in case sqrtPriceX96 < MIN_SQRT_PRICE, as MIN_SQRT_PRICE is the lowest value getSqrtPriceAtTick may
/// ever return.
/// @param sqrtPriceX96 The sqrt price for which to compute the tick as a Q64.96
/// @return tick The greatest tick for which the getSqrtPriceAtTick(tick) is less than or equal to the input sqrtPriceX96
function getTickAtSqrtPrice(uint160 sqrtPriceX96) internal pure returns (int24 tick) {
unchecked {
// Equivalent: if (sqrtPriceX96 < MIN_SQRT_PRICE || sqrtPriceX96 >= MAX_SQRT_PRICE) revert InvalidSqrtPrice();
// second inequality must be >= because the price can never reach the price at the max tick
// if sqrtPriceX96 < MIN_SQRT_PRICE, the `sub` underflows and `gt` is true
// if sqrtPriceX96 >= MAX_SQRT_PRICE, sqrtPriceX96 - MIN_SQRT_PRICE > MAX_SQRT_PRICE - MIN_SQRT_PRICE - 1
if ((sqrtPriceX96 - MIN_SQRT_PRICE) > MAX_SQRT_PRICE_MINUS_MIN_SQRT_PRICE_MINUS_ONE) {
InvalidSqrtPrice.selector.revertWith(sqrtPriceX96);
}
uint256 price = uint256(sqrtPriceX96) << 32;
uint256 r = price;
uint256 msb = BitMath.mostSignificantBit(r);
if (msb >= 128) r = price >> (msb - 127);
else r = price << (127 - msb);
int256 log_2 = (int256(msb) - 128) << 64;
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(63, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(62, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(61, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(60, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(59, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(58, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(57, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(56, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(55, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(54, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(53, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(52, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(51, f))
r := shr(f, r)
}
assembly ("memory-safe") {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(50, f))
}
int256 log_sqrt10001 = log_2 * 255738958999603826347141; // Q22.128 number
// Magic number represents the ceiling of the maximum value of the error when approximating log_sqrt10001(x)
int24 tickLow = int24((log_sqrt10001 - 3402992956809132418596140100660247210) >> 128);
// Magic number represents the minimum value of the error when approximating log_sqrt10001(x), when
// sqrtPrice is from the range (2^-64, 2^64). This is safe as MIN_SQRT_PRICE is more than 2^-64. If MIN_SQRT_PRICE
// is changed, this may need to be changed too
int24 tickHi = int24((log_sqrt10001 + 291339464771989622907027621153398088495) >> 128);
tick = tickLow == tickHi ? tickLow : getSqrtPriceAtTick(tickHi) <= sqrtPriceX96 ? tickHi : tickLow;
}
}
}