bit_math.gno

  1package gnsmath
  2
  3import (
  4	u256 "gno.land/p/gnoswap/uint256"
  5)
  6
  7// bitShift represents a bit pattern and corresponding shift amount for bit manipulation.
  8type bitShift struct {
  9	bitPattern *u256.Uint
 10	shift      uint
 11}
 12
 13// newMsbShifts returns the descending power-of-two thresholds used by
 14// BitMathMostSignificantBit. It is a constructor (not a package-level var) so
 15// each call yields freshly allocated bit patterns that callers never share.
 16// Values are built from little-endian [4]uint64 literals to avoid runtime
 17// shift computations.
 18func newMsbShifts() []bitShift {
 19	return []bitShift{
 20		{&u256.Uint{0, 0, 1, 0}, 128},         // 2^128
 21		{&u256.Uint{0, 1, 0, 0}, 64},          // 2^64
 22		{&u256.Uint{4294967296, 0, 0, 0}, 32}, // 2^32
 23		{&u256.Uint{65536, 0, 0, 0}, 16},      // 2^16
 24		{&u256.Uint{256, 0, 0, 0}, 8},         // 2^8
 25		{&u256.Uint{16, 0, 0, 0}, 4},          // 2^4
 26		{&u256.Uint{4, 0, 0, 0}, 2},           // 2^2
 27		{&u256.Uint{2, 0, 0, 0}, 1},           // 2^1
 28	}
 29}
 30
 31// newLsbShifts returns the descending (2^n - 1) masks used by
 32// BitMathLeastSignificantBit. See newMsbShifts for rationale.
 33func newLsbShifts() []bitShift {
 34	return []bitShift{
 35		{&u256.Uint{18446744073709551615, 18446744073709551615, 0, 0}, 128}, // 2^128 - 1
 36		{&u256.Uint{18446744073709551615, 0, 0, 0}, 64},                     // 2^64 - 1
 37		{&u256.Uint{4294967295, 0, 0, 0}, 32},                               // 2^32 - 1
 38		{&u256.Uint{65535, 0, 0, 0}, 16},                                    // 2^16 - 1
 39		{&u256.Uint{255, 0, 0, 0}, 8},                                       // 2^8 - 1
 40		{&u256.Uint{0xf, 0, 0, 0}, 4},                                       // 2^4 - 1 = 15
 41		{&u256.Uint{0x3, 0, 0, 0}, 2},                                       // 2^2 - 1 = 3
 42		{&u256.Uint{0x1, 0, 0, 0}, 1},                                       // 2^1 - 1 = 1
 43	}
 44}
 45
 46// BitMathMostSignificantBit returns the 0-based position of the most significant bit in x.
 47// This function is essential for AMM calculations involving price ranges and tick boundaries.
 48//
 49// Parameters:
 50//   - x: the value for which to compute the most significant bit
 51//
 52// Returns the index of the most significant bit (0-255).
 53//
 54// Panics if x is zero.
 55func BitMathMostSignificantBit(x *u256.Uint) uint8 {
 56	if x.IsZero() {
 57		panic(errMSBZeroInput)
 58	}
 59
 60	temp := x.Clone()
 61	r := uint8(0)
 62
 63	for _, s := range newMsbShifts() {
 64		if temp.Gte(s.bitPattern) {
 65			temp = temp.Rsh(temp, s.shift)
 66			r += uint8(s.shift)
 67		}
 68	}
 69
 70	return r
 71}
 72
 73// BitMathLeastSignificantBit returns the 0-based position of the least significant bit in x.
 74// This function is used in AMM calculations for efficient bit manipulation and range queries.
 75//
 76// Parameters:
 77//   - x: the value for which to compute the least significant bit
 78//
 79// Returns the index of the least significant bit (0-255).
 80//
 81// Panics if x is zero.
 82func BitMathLeastSignificantBit(x *u256.Uint) uint8 {
 83	if x.IsZero() {
 84		panic(errLSBZeroInput)
 85	}
 86
 87	temp := x.Clone()
 88	hasSetBits := u256.Zero()
 89	r := uint8(255)
 90
 91	for _, s := range newLsbShifts() {
 92		hasSetBits = hasSetBits.And(temp, s.bitPattern)
 93		if !hasSetBits.IsZero() {
 94			r -= uint8(s.shift)
 95		} else {
 96			temp = temp.Rsh(temp, s.shift)
 97		}
 98	}
 99
100	return r
101}