tick_bitmap.gno

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