tick_bitmap.gno
5.55 Kb ยท 165 lines
1package v1
2
3import (
4 "strconv"
5
6 plp "gno.land/p/gnoswap/gnsmath"
7 u256 "gno.land/p/gnoswap/uint256"
8 "gno.land/p/nt/ufmt"
9 pl "gno.land/r/gnoswap/pool"
10)
11
12// bitMask8 is used for efficient modulo 256 operations
13const bitMask8 = 0xff // 256 - 1
14
15// tickBitmapFlipTick flips the state of a tick in the tick bitmap.
16//
17// This function toggles the "initialized" state of a tick in the tick bitmap.
18// It ensures that the tick aligns with the specified tick spacing and then
19// flips the corresponding bit in the bitmap representation.
20//
21// Parameters:
22// - tick: int32, the tick index to toggle.
23// - tickSpacing: int32, the spacing between valid ticks.
24// The tick must align with this spacing.
25//
26// Workflow:
27// 1. Validates that the `tick` aligns with `tickSpacing` using `checkTickSpacing`.
28// 2. Computes the position of the bit in the tick bitmap:
29// - `wordPos`: Determines which word in the bitmap contains the bit.
30// - `bitPos`: Identifies the position of the bit within the word.
31// 3. Creates a bitmask using `Lsh` (Left Shift) to target the bit at `bitPos`.
32// 4. Toggles (flips) the bit using XOR with the current value of the tick bitmap.
33// 5. Updates the tick bitmap with the modified word.
34//
35// Behavior:
36// - If the bit is `0` (uninitialized), it will be flipped to `1` (initialized).
37// - If the bit is `1` (initialized), it will be flipped to `0` (uninitialized).
38//
39// Example:
40//
41// pool.tickBitmapFlipTick(120, 60)
42// // This flips the bit for tick 120 with a tick spacing of 60.
43//
44// Notes:
45// - The `tick` must be divisible by `tickSpacing`. If not, the function will panic.
46func tickBitmapFlipTick(
47 p *pl.Pool,
48 tick int32,
49 tickSpacing int32,
50) {
51 checkTickSpacing(tick, tickSpacing)
52 wordPos, bitPos := tickBitmapPosition(tick / tickSpacing)
53
54 mask := u256.Zero().Lsh(u256.One(), uint(bitPos))
55 current := getTickBitmap(p, wordPos)
56 setTickBitmap(p, wordPos, u256.Zero().Xor(current, mask))
57}
58
59// tickBitmapNextInitializedTickWithInOneWord finds the next initialized tick within
60// one word of the bitmap.
61func tickBitmapNextInitializedTickWithInOneWord(
62 p *pl.Pool,
63 tick int32,
64 tickSpacing int32,
65 lte bool,
66) (int32, bool) {
67 compress := tick / tickSpacing
68 // Round towards negative infinity for negative ticks
69 if tick < 0 && tick%tickSpacing != 0 {
70 compress--
71 }
72
73 wordPos, bitPos := getWordAndBitPos(compress, lte)
74 mask := getMaskBit(uint(bitPos), lte)
75 masked := u256.Zero().And(getTickBitmap(p, wordPos), mask)
76 initialized := !masked.IsZero()
77
78 nextTick := getNextTick(lte, initialized, compress, bitPos, tickSpacing, masked)
79 return nextTick, initialized
80}
81
82// getTickBitmap gets the tick bitmap for the given word position
83// if the tick bitmap is not initialized, initialize it to zero
84func getTickBitmap(p *pl.Pool, wordPos int16) *u256.Uint {
85 wordPosStr := strconv.Itoa(int(wordPos))
86
87 value, exist := p.TickBitmaps().Get(wordPosStr)
88 if !exist {
89 setTickBitmap(p, wordPos, u256.Zero())
90 value, exist = p.TickBitmaps().Get(wordPosStr)
91 if !exist {
92 panic(newErrorWithDetail(
93 errDataNotFound,
94 ufmt.Sprintf("failed to initialize tickBitmap(%d)", wordPos),
95 ))
96 }
97 }
98
99 bitmap, ok := value.(*u256.Uint)
100 if !ok {
101 panic(ufmt.Sprintf("failed to cast tickBitmap to *u256.Uint: %T", value))
102 }
103 return bitmap
104}
105
106// setTickBitmap sets the tick bitmap for the given word position
107func setTickBitmap(p *pl.Pool, wordPos int16, tickBitmap *u256.Uint) {
108 wordPosStr := strconv.Itoa(int(wordPos))
109 p.TickBitmaps().Set(wordPosStr, tickBitmap)
110}
111
112// tickBitmapPosition calculates the word and bit position for a given tick
113func tickBitmapPosition(tick int32) (int16, uint8) {
114 return int16(tick >> 8), uint8(tick) & bitMask8
115}
116
117// getWordAndBitPos gets tick's wordPos and bitPos depending on the swap direction
118func getWordAndBitPos(tick int32, lte bool) (int16, uint8) {
119 if !lte {
120 tick++
121 }
122 return tickBitmapPosition(tick)
123}
124
125// getMaskBit generates a mask based on the provided bit position (bitPos) and a boolean flag (lte).
126// The function constructs a bitmask with a shift depending on the bit position and the boolean value.
127// It either returns the mask or its negation, based on the value of 'lte' (swap direction).
128//
129// NOTE: should always use a newly created `u256.One()` object.
130func getMaskBit(bitPos uint, lte bool) *u256.Uint {
131 if lte {
132 if bitPos == bitMask8 {
133 return u256.Zero().SetAllOne()
134 }
135 return u256.Zero().Sub(u256.Zero().Lsh(u256.One(), bitPos+1), u256.One())
136 }
137 if bitPos == 0 {
138 return u256.Zero().SetAllOne()
139 }
140 return u256.Zero().Not(u256.Zero().Sub(u256.Zero().Lsh(u256.One(), bitPos), u256.One()))
141}
142
143// getNextTick gets the next tick depending on the initialized state and the swap direction
144func getNextTick(lte, initialized bool, compress int32, bitPos uint8, tickSpacing int32, masked *u256.Uint) int32 {
145 if initialized {
146 return getTickIfInitialized(compress, tickSpacing, bitPos, masked, lte)
147 }
148 return getTickIfNotInitialized(compress, tickSpacing, bitPos, lte)
149}
150
151// getTickIfInitialized gets the next tick if the tick bitmap is initialized
152func getTickIfInitialized(compress, tickSpacing int32, bitPos uint8, masked *u256.Uint, lte bool) int32 {
153 if lte {
154 return (compress - int32(bitPos-plp.BitMathMostSignificantBit(masked))) * tickSpacing
155 }
156 return (compress + 1 + int32(plp.BitMathLeastSignificantBit(masked)-bitPos)) * tickSpacing
157}
158
159// getTickIfNotInitialized gets the next tick if the tick bitmap is not initialized
160func getTickIfNotInitialized(compress, tickSpacing int32, bitPos uint8, lte bool) int32 {
161 if lte {
162 return (compress - int32(bitPos)) * tickSpacing
163 }
164 return (compress + 1 + int32(bitMask8-bitPos)) * tickSpacing
165}
