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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
use super::{errors::ErrorCodes, u256::*};
use anyhow::Result;
/// Library that calculates number "tick" and "ratioX48" from this: ratioX48 = (1.0015^tick) * 2^48
/// This library is optimized for u128 calculations in Solana programs.
/// "tick" supports between -16383 and 16383.
/// "ratioX48" supports between 6093 and 13002088133096036565414295
pub struct TickMath;
impl TickMath {
/// The minimum tick that can be passed in get_ratio_at_tick. 1.0015**-16383
pub const MIN_TICK: i32 = -16383;
/// The maximum tick that can be passed in get_ratio_at_tick. 1.0015**16383
pub const MAX_TICK: i32 = 16383;
/// The spacing between two consecutive ticks. 1.0015
pub const TICK_SPACING: u128 = 10015;
/// The cold tick is used to represent that tick is not set
pub const COLD_TICK: i32 = i32::MIN;
// script to verify values - https://play.instadapp.io/ioH-QHu1qaJ4pvQEh_OZB
const FACTOR00: u128 = 0x10000000000000000; // 2^64
const FACTOR01: u128 = 0xff9dd7de423466c2; // 2^64/1.0015**1 = 18419115400608638658
const FACTOR02: u128 = 0xff3bd55f4488ad27; // 2^64/1.0015**2 = 18391528108445969703
const FACTOR03: u128 = 0xfe78410fd6498b74; // 2^64/1.0015**4 = 18336477419114433396
const FACTOR04: u128 = 0xfcf2d9987c9be179; // 2^64/1.0015**8 = 18226869890870665593
const FACTOR05: u128 = 0xf9ef02c4529258b0; // 2^64/1.0015**16 = 18009616477100071088
const FACTOR06: u128 = 0xf402d288133a85a1; // 2^64/1.0015**32 = 17582847377087825313
const FACTOR07: u128 = 0xe895615b5beb6386; // 2^64/1.0015**64 = 16759408633341240198
const FACTOR08: u128 = 0xd34f17a00ffa00a8; // 2^64/1.0015**128 = 15226414841393184936
const FACTOR09: u128 = 0xae6b7961714e2055; // 2^64/1.0015**256 = 12568272644527235157
const FACTOR10: u128 = 0x76d6461f27082d75; // 2^64/1.0015**512 = 8563108841104354677
const FACTOR11: u128 = 0x372a3bfe0745d8b7; // 2^64/1.0015**1024 = 3975055583337633975
const FACTOR12: u128 = 0xbe32cbee4897976; // 2^64/1.0015**2048 = 856577552520149366
const FACTOR13: u128 = 0x8d4f70c9ff4925; // 2^64/1.0015**4096 = 39775317560084773
const FACTOR14: u128 = 0x4e009ae55194; // 2^64/1.0015**8192 = 85764505686420
/// The minimum value that can be returned from get_ratio_at_tick.
/// Equivalent to get_ratio_at_tick(MIN_TICK). ~ Equivalent to `(1 << 48) * (1.0015**-16383)`
pub const MIN_RATIOX48: u128 = 6093;
/// The maximum value that can be returned from get_ratio_at_tick.
/// Equivalent to get_ratio_at_tick(MAX_TICK). ~ Equivalent to `(1 << 48) * (1.0015**16383)`
pub const MAX_RATIOX48: u128 = 13002088133096036565414295;
pub const ZERO_TICK_SCALED_RATIO: u128 = 0x1000000000000; // 1 << 48
const _1E13: u128 = 10000000000000; // 1e13
pub const SHIFT: u128 = 48;
/// Calculate ratioX48 = (1.0015^tick) * 2^48
///
/// # Arguments
/// * `tick` - The input tick for the above formula
///
/// # Returns
/// * `Result<u128, ProgramError>` - The ratio or an error if tick is out of bounds
///
/// # Errors
/// * Returns error if |tick| > MAX_TICK
pub fn get_ratio_at_tick(tick: i32) -> Result<u128> {
if !(tick >= Self::MIN_TICK && tick <= Self::MAX_TICK) {
return Err(ErrorCodes::TickOutOfBounds.into());
}
let abs_tick = tick.unsigned_abs();
let mut factor = Self::FACTOR00;
if abs_tick & 0x1 != 0 {
factor = Self::FACTOR01;
}
if abs_tick & 0x2 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR02)?;
}
if abs_tick & 0x4 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR03)?;
}
if abs_tick & 0x8 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR04)?;
}
if abs_tick & 0x10 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR05)?;
}
if abs_tick & 0x20 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR06)?;
}
if abs_tick & 0x40 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR07)?;
}
if abs_tick & 0x80 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR08)?;
}
if abs_tick & 0x100 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR09)?;
}
if abs_tick & 0x200 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR10)?;
}
if abs_tick & 0x400 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR11)?;
}
if abs_tick & 0x800 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR12)?;
}
if abs_tick & 0x1000 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR13)?;
}
if abs_tick & 0x2000 != 0 {
factor = Self::mul_shift_64(factor, Self::FACTOR14)?;
}
let mut precision = 0u128;
if tick >= 0 {
// For positive ticks, take reciprocal to get 1.0015^|tick|
factor = u128::MAX / factor;
// Round up for precision
if factor % 0x10000 != 0 {
precision = 1;
}
}
let ratio_x48 = (factor >> 16) + precision;
Ok(ratio_x48)
}
/// Calculate tick from ratioX48 where ratioX48 = (1.0015^tick) * 2^48
///
/// # Arguments
/// * `ratio_x48` - The input ratio
///
/// # Returns
/// * `Result<(i32, u128), ProgramError>` - (tick, perfect_ratio_x48) or error
///
/// # Errors
/// * Returns error if ratio_x48 is out of valid bounds
pub fn get_tick_at_ratio(ratio_x48: u128) -> Result<(i32, u128)> {
if !(ratio_x48 >= Self::MIN_RATIOX48 && ratio_x48 <= Self::MAX_RATIOX48) {
return Err(ErrorCodes::TickRatioOutOfBounds.into());
}
let is_negative = ratio_x48 < Self::ZERO_TICK_SCALED_RATIO;
let mut factor = if is_negative {
// For ratios < 1 (negative ticks)
Self::checked_mul_div(Self::ZERO_TICK_SCALED_RATIO, Self::_1E13, ratio_x48)?
} else {
// For ratios >= 1 (positive ticks)
Self::checked_mul_div(ratio_x48, Self::_1E13, Self::ZERO_TICK_SCALED_RATIO)?
};
let mut tick = 0i32;
// Binary search through powers of 2
// Thresholds are (1.0015^(2^n)) * 1E13
// https://play.instadapp.io/Z_QfIaO0h8kUQ2A-GwkP9
if factor >= 2150859953785115391 {
// 2^13 = 8192
tick |= 0x2000;
factor = Self::checked_mul_div(factor, Self::_1E13, 2150859953785115391)?;
}
if factor >= 4637736467054931 {
// 2^12 = 4096
tick |= 0x1000;
factor = Self::checked_mul_div(factor, Self::_1E13, 4637736467054931)?;
}
if factor >= 215354044936586 {
// 2^11 = 2048
tick |= 0x800;
factor = Self::checked_mul_div(factor, Self::_1E13, 215354044936586)?;
}
if factor >= 46406254420777 {
// 2^10 = 1024
tick |= 0x400;
factor = Self::checked_mul_div(factor, Self::_1E13, 46406254420777)?;
}
if factor >= 21542110950596 {
// 2^9 = 512
tick |= 0x200;
factor = Self::checked_mul_div(factor, Self::_1E13, 21542110950596)?;
}
if factor >= 14677230989051 {
// 2^8 = 256
tick |= 0x100;
factor = Self::checked_mul_div(factor, Self::_1E13, 14677230989051)?;
}
if factor >= 12114962232319 {
// 2^7 = 128
tick |= 0x80;
factor = Self::checked_mul_div(factor, Self::_1E13, 12114962232319)?;
}
if factor >= 11006798913544 {
// 2^6 = 64
tick |= 0x40;
factor = Self::checked_mul_div(factor, Self::_1E13, 11006798913544)?;
}
if factor >= 10491329235871 {
// 2^5 = 32
tick |= 0x20;
factor = Self::checked_mul_div(factor, Self::_1E13, 10491329235871)?;
}
if factor >= 10242718992470 {
// 2^4 = 16
tick |= 0x10;
factor = Self::checked_mul_div(factor, Self::_1E13, 10242718992470)?;
}
if factor >= 10120631893548 {
// 2^3 = 8
tick |= 0x8;
factor = Self::checked_mul_div(factor, Self::_1E13, 10120631893548)?;
}
if factor >= 10060135135051 {
// 2^2 = 4
tick |= 0x4;
factor = Self::checked_mul_div(factor, Self::_1E13, 10060135135051)?;
}
if factor >= 10030022500000 {
// 2^1 = 2
tick |= 0x2;
factor = Self::checked_mul_div(factor, Self::_1E13, 10030022500000)?;
}
if factor >= 10015000000000 {
// 2^0 = 1
tick |= 0x1;
factor = Self::checked_mul_div(factor, Self::_1E13, 10015000000000)?;
}
let perfect_ratio_x48 = if is_negative {
// For negative ticks
tick = !tick; // Bitwise NOT to make negative
Self::checked_mul_div(ratio_x48, factor, 10015000000000)?
} else {
// For positive ticks
Self::checked_mul_div(ratio_x48, Self::_1E13, factor)?
};
// Verify perfect ratio is not greater than input ratio
if !(perfect_ratio_x48 <= ratio_x48) {
return Err(ErrorCodes::TickInvalidPerfectRatio.into());
}
Ok((tick, perfect_ratio_x48))
}
fn mul_shift_64(n0: u128, n1: u128) -> Result<u128> {
mul_u256(n0, n1).shift_right(64).try_into_u128()
}
/// Helper function for safe multiply-divide operations
fn checked_mul_div(a: u128, b: u128, c: u128) -> Result<u128> {
let result = safe_multiply_divide(a, b, c)?;
Ok(result)
}
}