Tick Bitmap Index

# Tick Bitmap Index #

As the first step towards dynamic swaps, we need to implement an index of ticks. In the previous milestone, we used to calculate the target tick when making a swap:

function swap(address recipient, bytes calldata data)
public
returns (int256 amount0, int256 amount1)
{
int24 nextTick = 85184;
...
}


When there’s liquidity provided in different price ranges, we cannot simply calculate the target tick. We need to find it. Thus, we need to index all ticks that have liquidity and then use the index to find ticks to “inject” enough liquidity for a swap. In this step, we’re going to implement such index.

## Bitmap #

Bitmap is a popular technique of indexing data in a compact way. A bitmap is simply a number represented in the binary system, e.g. 31337 is 111101001101001. We can look at it as an array of zeros and ones, with each digit having an index. We then say that 0 means a flag is not set and 1 means it’s set. So what we get is a very compact array of indexed flags: each byte can fit 8 flags. In Solidity, we can have integers up to 256 bits, which means one uint256 can hold 256 flags.

Uniswap V3 uses this technique to store the information about initialized ticks, that is ticks with some liquidity. When a flag is set (1), the tick has liquidity; when a flag is not set (0), the tick is not initialized. Let’s look at the implementation.

## TickBitmap Contract #

In the pool contract, the tick index is stored in a state variable:

contract UniswapV3Pool {
using TickBitmap for mapping(int16 => uint256);
mapping(int16 => uint256) public tickBitmap;
...
}


This is mapping where keys are int16’s and values are words (uint256). Imagine an infinite continuous array of ones and zeros:

Each element in this array corresponds to a tick. To navigate in this array, we break it into words: sub-arrays of length 256 bits. To find tick’s position in this array, we do:

function position(int24 tick) private pure returns (int16 wordPos, uint8 bitPos) {
wordPos = int16(tick >> 8);
bitPos = uint8(uint24(tick % 256));
}


That is: we find its word position and then its bit in this word. >> 8 is identical to integer division by 256. So, word position is the integer part of a tick index divided by 256, and bit position is the remainder.

As an example, let’s calculate word and bit positions for one of our ticks:

tick = 85176
word_pos = tick >> 8 # or tick // 2**8
bit_pos = tick % 256
print(f"Word {word_pos}, bit {bit_pos}")
# Word 332, bit 184


### Flipping Flags #

When adding liquidity into a pool, we need to set a couple of tick flags in the bitmap: one for the lower tick and one for the upper tick. We do this in flipTick method of the bitmap mapping:

function flipTick(
mapping(int16 => uint256) storage self,
int24 tick,
int24 tickSpacing
) internal {
require(tick % tickSpacing == 0); // ensure that the tick is spaced
(int16 wordPos, uint8 bitPos) = position(tick / tickSpacing);
uint256 mask = 1 << bitPos;
}


Until later in the book, tickSpacing is always 1.

After finding word and bit positions, we need to make a mask. A mask is a number that has a single 1 flag set at the bit position of the tick. To find the mask, we simply calculate 2**bit_pos (equivalent of 1 << bit_pos):

mask = 2**bit_pos # or 1 << bit_pos
#0b10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


Next, to flip a flag, we apply the mask to the tick’s word via bitwise XOR:

word = (2**256) - 1 # set word to all ones
#0b1111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111


You’ll see that 184th bit (counting from the right starting at 0) has flipped to 0.

If a bit is zero, it’ll set it to 1:

word = 0
#0b10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


### Finding Next Tick #

Next step is finding ticks with liquidity using the bitmap index.

During swapping, we need to find a tick with liquidity that’s before or after the current tick (that is: to the left or to the right of it). In the previous milestone, we used to calculate and hard code it, but now we need to find such tick using the bitmap index. We’ll do this in the TickBitmap.nextInitializedTickWithinOneWord function. In this function, we’ll need to implement two scenarios:

1. When selling token $x$ (ETH in our case), find next initialized tick in the current tick’s word and to the right of the current tick.
2. When selling token $y$ (USDC in our case), find next initialized tick in the next (current + 1) tick’s word and to the left of the current tick.

This corresponds to the price movement when making swaps in either directions:

Be aware that, in the code, the direction is flipped: when buying token $x$, we search for initialized ticks to the left of the current; when selling token $x$, we search ticks to the right. But this is only true within a word; words are ordered from left to right.

When there’s no initialized tick in the current word, we’ll continue searching in an adjacent word in the next loop cycle.

Now, let’s look at the implementation:

function nextInitializedTickWithinOneWord(
mapping(int16 => uint256) storage self,
int24 tick,
int24 tickSpacing,
bool lte
) internal view returns (int24 next, bool initialized) {
int24 compressed = tick / tickSpacing;
...

1. First arguments makes this function a method of mapping(int16 => uint256).
2. tick is the current tick.
3. tickSpacing is always 1 until we start using it in Milestone 4.
4. lte is the flag that sets the direction. When true, we’re selling token $x$ and searching for next initialized tick to the right of the current one. When false, it’s the other way around. lte equals to the swap direction: true when selling token $x$, false otherwise.
if (lte) {
(int16 wordPos, uint8 bitPos) = position(compressed);
uint256 mask = (1 << bitPos) - 1 + (1 << bitPos);
...


When selling $x$, we’re:

1. taking current tick’s word and bit positions;
2. making a mask where all bits to the right of the current bit position, including it, are ones (mask is all ones, its length = bitPos);
3. applying the mask to the current tick’s word.
    ...
next = initialized
? (compressed - int24(uint24(bitPos - BitMath.mostSignificantBit(masked)))) * tickSpacing
: (compressed - int24(uint24(bitPos))) * tickSpacing;
...


Next, masked won’t equal 0 if at least one bit of it is set to 1. If so, there’s an initialized tick; if not, there isn’t (not in the current word). Depending on the result, we either return the index of the next initialized tick or the leftmost bit in the next word–this will allow to search for initialized ticks in the word during another loop cycle.

    ...
} else {
(int16 wordPos, uint8 bitPos) = position(compressed + 1);
uint256 mask = ~((1 << bitPos) - 1);
...


Similarly, when selling $y$, we’re:

1. taking next tick’s word and bit positions;
2. making a different mask, where all bits to the left of next tick bit position are ones and all the bits to the right are zeros;
3. applying the mask to the next tick’s word.

Again, if there’s no initialized ticks to the left, the rightmost bit of the previous word is returned:

    ...

As you can see, nextInitializedTickWithinOneWord doesn’t find the exact tick if it’s far away–it’s scope of search is current or next tick’s word. Indeed, we don’t want to iterate over the infinite bitmap index.