tick_bitmap.gno

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