Created
June 18, 2021 04:06
-
-
Save kassandraoftroy/c49987b80340a9da556ae36eb8db22d1 to your computer and use it in GitHub Desktop.
0.8 compatible TickMath
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // SPDX-License-Identifier: GPL-3.0 | |
| pragma solidity 0.8.4; | |
| /// @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 { | |
| /// @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; | |
| /// @dev The minimum value that can be returned from #getSqrtRatioAtTick. Equivalent to getSqrtRatioAtTick(MIN_TICK) | |
| uint160 internal constant MIN_SQRT_RATIO = 4295128739; | |
| /// @dev The maximum value that can be returned from #getSqrtRatioAtTick. Equivalent to getSqrtRatioAtTick(MAX_TICK) | |
| uint160 internal constant MAX_SQRT_RATIO = | |
| 1461446703485210103287273052203988822378723970342; | |
| /// @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 ratio of the two assets (token1/token0) | |
| /// at the given tick | |
| function getSqrtRatioAtTick(int24 tick) | |
| internal | |
| pure | |
| returns (uint160 sqrtPriceX96) | |
| { | |
| uint256 absTick = | |
| tick < 0 ? uint256(-int256(tick)) : uint256(int256(tick)); | |
| // EDIT: 0.8 compatibility | |
| 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) | |
| ); | |
| } | |
| /// @notice Calculates the greatest tick value such that getRatioAtTick(tick) <= ratio | |
| /// @dev Throws in case sqrtPriceX96 < MIN_SQRT_RATIO, as MIN_SQRT_RATIO is the lowest value getRatioAtTick may | |
| /// ever return. | |
| /// @param sqrtPriceX96 The sqrt ratio for which to compute the tick as a Q64.96 | |
| /// @return tick The greatest tick for which the ratio is less than or equal to the input ratio | |
| function getTickAtSqrtRatio(uint160 sqrtPriceX96) | |
| internal | |
| pure | |
| returns (int24 tick) | |
| { | |
| // second inequality must be < because the price can never reach the price at the max tick | |
| require( | |
| sqrtPriceX96 >= MIN_SQRT_RATIO && sqrtPriceX96 < MAX_SQRT_RATIO, | |
| "R" | |
| ); | |
| uint256 ratio = uint256(sqrtPriceX96) << 32; | |
| uint256 r = ratio; | |
| uint256 msb = 0; | |
| assembly { | |
| let f := shl(7, gt(r, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)) | |
| msb := or(msb, f) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| let f := shl(6, gt(r, 0xFFFFFFFFFFFFFFFF)) | |
| msb := or(msb, f) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| let f := shl(5, gt(r, 0xFFFFFFFF)) | |
| msb := or(msb, f) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| let f := shl(4, gt(r, 0xFFFF)) | |
| msb := or(msb, f) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| let f := shl(3, gt(r, 0xFF)) | |
| msb := or(msb, f) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| let f := shl(2, gt(r, 0xF)) | |
| msb := or(msb, f) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| let f := shl(1, gt(r, 0x3)) | |
| msb := or(msb, f) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| let f := gt(r, 0x1) | |
| msb := or(msb, f) | |
| } | |
| if (msb >= 128) r = ratio >> (msb - 127); | |
| else r = ratio << (127 - msb); | |
| int256 log_2 = (int256(msb) - 128) << 64; | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(63, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(62, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(61, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(60, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(59, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(58, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(57, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(56, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(55, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(54, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(53, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(52, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| r := shr(127, mul(r, r)) | |
| let f := shr(128, r) | |
| log_2 := or(log_2, shl(51, f)) | |
| r := shr(f, r) | |
| } | |
| assembly { | |
| 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; // 128.128 number | |
| int24 tickLow = | |
| int24( | |
| (log_sqrt10001 - 3402992956809132418596140100660247210) >> 128 | |
| ); | |
| int24 tickHi = | |
| int24( | |
| (log_sqrt10001 + 291339464771989622907027621153398088495) >> 128 | |
| ); | |
| tick = tickLow == tickHi | |
| ? tickLow | |
| : getSqrtRatioAtTick(tickHi) <= sqrtPriceX96 | |
| ? tickHi | |
| : tickLow; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment