-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFullMath.sol
179 lines (164 loc) · 8.09 KB
/
FullMath.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
pragma solidity >=0.8.0;
// FullMath & TickMath use unsupported features in 0.8, need to copy paste code
// https://github.com/Uniswap/v3-core/issues/489
// import '@uniswap/v3-core/contracts/libraries/TickMath.sol';
// import '@uniswap/v3-core/contracts/libraries/FullMath.sol';
library FullMath {
/// @notice Calculates floor(a×b÷denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
/// @param a The multiplicand
/// @param b The multiplier
/// @param denominator The divisor
/// @return result The 256-bit result
/// @dev Credit to Remco Bloemen under MIT license https://xn--2-umb.com/21/muldiv
function mulDiv(
uint256 a,
uint256 b,
uint256 denominator
) internal pure returns (uint256 result) {
unchecked {
// 512-bit multiply [prod1 prod0] = a * b
// Compute the product mod 2**256 and mod 2**256 - 1
// then use the Chinese Remainder Theorem to reconstruct
// the 512 bit result. The result is stored in two 256
// variables such that product = prod1 * 2**256 + prod0
uint256 prod0; // Least significant 256 bits of the product
uint256 prod1; // Most significant 256 bits of the product
assembly {
let mm := mulmod(a, b, not(0))
prod0 := mul(a, b)
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
}
// Handle non-overflow cases, 256 by 256 division
if (prod1 == 0) {
require(denominator > 0);
assembly {
result := div(prod0, denominator)
}
return result;
}
// Make sure the result is less than 2**256.
// Also prevents denominator == 0
require(denominator > prod1);
///////////////////////////////////////////////
// 512 by 256 division.
///////////////////////////////////////////////
// Make division exact by subtracting the remainder from [prod1 prod0]
// Compute remainder using mulmod
uint256 remainder;
assembly {
remainder := mulmod(a, b, denominator)
}
// Subtract 256 bit number from 512 bit number
assembly {
prod1 := sub(prod1, gt(remainder, prod0))
prod0 := sub(prod0, remainder)
}
// Factor powers of two out of denominator
// Compute largest power of two divisor of denominator.
// Always >= 1.
uint256 twos = (~denominator + 1) & denominator;
// Divide denominator by power of two
assembly {
denominator := div(denominator, twos)
}
// Divide [prod1 prod0] by the factors of two
assembly {
prod0 := div(prod0, twos)
}
// Shift in bits from prod1 into prod0. For this we need
// to flip `twos` such that it is 2**256 / twos.
// If twos is zero, then it becomes one
assembly {
twos := add(div(sub(0, twos), twos), 1)
}
prod0 |= prod1 * twos;
// Invert denominator mod 2**256
// Now that denominator is an odd number, it has an inverse
// modulo 2**256 such that denominator * inv = 1 mod 2**256.
// Compute the inverse by starting with a seed that is correct
// correct for four bits. That is, denominator * inv = 1 mod 2**4
uint256 inv = (3 * denominator) ^ 2;
// Now use Newton-Raphson iteration to improve the precision.
// Thanks to Hensel's lifting lemma, this also works in modular
// arithmetic, doubling the correct bits in each step.
inv *= 2 - denominator * inv; // inverse mod 2**8
inv *= 2 - denominator * inv; // inverse mod 2**16
inv *= 2 - denominator * inv; // inverse mod 2**32
inv *= 2 - denominator * inv; // inverse mod 2**64
inv *= 2 - denominator * inv; // inverse mod 2**128
inv *= 2 - denominator * inv; // inverse mod 2**256
// Because the division is now exact we can divide by multiplying
// with the modular inverse of denominator. This will give us the
// correct result modulo 2**256. Since the precoditions guarantee
// that the outcome is less than 2**256, this is the final result.
// We don't need to compute the high bits of the result and prod1
// is no longer required.
result = prod0 * inv;
return result;
}
}
/// @dev The minimum tick that may be passed to #getSqrtRatioAtTick computed from log base 1.0001 of 2**-128
int24 internal constant MIN_TICK = -887272;
/// @dev The maximum tick that may be passed to #getSqrtRatioAtTick computed from log base 1.0001 of 2**128
int24 internal constant MAX_TICK = -MIN_TICK;
function getSqrtRatioAtTick(int24 tick)
internal
pure
returns (uint160 sqrtPriceX96)
{
unchecked {
uint256 absTick = tick < 0
? uint256(-int256(tick))
: uint256(int256(tick));
require(absTick <= uint256(int256(MAX_TICK)), "T");
uint256 ratio = absTick & 0x1 != 0
? 0xfffcb933bd6fad37aa2d162d1a594001
: 0x100000000000000000000000000000000;
if (absTick & 0x2 != 0)
ratio = (ratio * 0xfff97272373d413259a46990580e213a) >> 128;
if (absTick & 0x4 != 0)
ratio = (ratio * 0xfff2e50f5f656932ef12357cf3c7fdcc) >> 128;
if (absTick & 0x8 != 0)
ratio = (ratio * 0xffe5caca7e10e4e61c3624eaa0941cd0) >> 128;
if (absTick & 0x10 != 0)
ratio = (ratio * 0xffcb9843d60f6159c9db58835c926644) >> 128;
if (absTick & 0x20 != 0)
ratio = (ratio * 0xff973b41fa98c081472e6896dfb254c0) >> 128;
if (absTick & 0x40 != 0)
ratio = (ratio * 0xff2ea16466c96a3843ec78b326b52861) >> 128;
if (absTick & 0x80 != 0)
ratio = (ratio * 0xfe5dee046a99a2a811c461f1969c3053) >> 128;
if (absTick & 0x100 != 0)
ratio = (ratio * 0xfcbe86c7900a88aedcffc83b479aa3a4) >> 128;
if (absTick & 0x200 != 0)
ratio = (ratio * 0xf987a7253ac413176f2b074cf7815e54) >> 128;
if (absTick & 0x400 != 0)
ratio = (ratio * 0xf3392b0822b70005940c7a398e4b70f3) >> 128;
if (absTick & 0x800 != 0)
ratio = (ratio * 0xe7159475a2c29b7443b29c7fa6e889d9) >> 128;
if (absTick & 0x1000 != 0)
ratio = (ratio * 0xd097f3bdfd2022b8845ad8f792aa5825) >> 128;
if (absTick & 0x2000 != 0)
ratio = (ratio * 0xa9f746462d870fdf8a65dc1f90e061e5) >> 128;
if (absTick & 0x4000 != 0)
ratio = (ratio * 0x70d869a156d2a1b890bb3df62baf32f7) >> 128;
if (absTick & 0x8000 != 0)
ratio = (ratio * 0x31be135f97d08fd981231505542fcfa6) >> 128;
if (absTick & 0x10000 != 0)
ratio = (ratio * 0x9aa508b5b7a84e1c677de54f3e99bc9) >> 128;
if (absTick & 0x20000 != 0)
ratio = (ratio * 0x5d6af8dedb81196699c329225ee604) >> 128;
if (absTick & 0x40000 != 0)
ratio = (ratio * 0x2216e584f5fa1ea926041bedfe98) >> 128;
if (absTick & 0x80000 != 0)
ratio = (ratio * 0x48a170391f7dc42444e8fa2) >> 128;
if (tick > 0) ratio = type(uint256).max / ratio;
// 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 getTickAtSqrtRatio of the output price is always consistent
sqrtPriceX96 = uint160(
(ratio >> 32) + (ratio % (1 << 32) == 0 ? 0 : 1)
);
}
}
}