bit_math.gno

 1package gnsmath
 2
 3import (
 4	u256 "gno.land/p/gnoswap/uint256"
 5)
 6
 7var (
 8	msbShifts = []bitShift{
 9		{u256.Zero().Lsh(u256.One(), 128), 128}, // 2^128
10		{u256.Zero().Lsh(u256.One(), 64), 64},   // 2^64
11		{u256.Zero().Lsh(u256.One(), 32), 32},   // 2^32
12		{u256.Zero().Lsh(u256.One(), 16), 16},   // 2^16
13		{u256.Zero().Lsh(u256.One(), 8), 8},     // 2^8
14		{u256.Zero().Lsh(u256.One(), 4), 4},     // 2^4
15		{u256.Zero().Lsh(u256.One(), 2), 2},     // 2^2
16		{u256.Zero().Lsh(u256.One(), 1), 1},     // 2^1
17	}
18
19	lsbShifts = []bitShift{
20		{u256.Zero().Sub(u256.Zero().Lsh(u256.One(), 128), u256.One()), 128}, // 2^128 - 1
21		{u256.Zero().Sub(u256.Zero().Lsh(u256.One(), 64), u256.One()), 64},   // 2^64 - 1
22		{u256.Zero().Sub(u256.Zero().Lsh(u256.One(), 32), u256.One()), 32},   // 2^32 - 1
23		{u256.Zero().Sub(u256.Zero().Lsh(u256.One(), 16), u256.One()), 16},   // 2^16 - 1
24		{u256.Zero().Sub(u256.Zero().Lsh(u256.One(), 8), u256.One()), 8},     // 2^8 - 1
25		{u256.NewUint(0xf), 4}, // 2^4 - 1 = 15
26		{u256.NewUint(0x3), 2}, // 2^2 - 1 = 3
27		{u256.NewUint(0x1), 1}, // 2^1 - 1 = 1
28	}
29)
30
31// bitShift represents a bit pattern and corresponding shift amount for bit manipulation.
32type bitShift struct {
33	bitPattern *u256.Uint
34	shift      uint
35}
36
37// BitMathMostSignificantBit returns the 0-based position of the most significant bit in x.
38// This function is essential for AMM calculations involving price ranges and tick boundaries.
39//
40// Parameters:
41//   - x: the value for which to compute the most significant bit
42//
43// Returns the index of the most significant bit (0-255).
44//
45// Panics if x is zero.
46func BitMathMostSignificantBit(x *u256.Uint) uint8 {
47	if x.IsZero() {
48		panic(errMSBZeroInput)
49	}
50
51	temp := x.Clone()
52	r := uint8(0)
53
54	for _, s := range msbShifts {
55		if temp.Gte(s.bitPattern) {
56			temp = temp.Rsh(temp, s.shift)
57			r += uint8(s.shift)
58		}
59	}
60
61	return r
62}
63
64// BitMathLeastSignificantBit returns the 0-based position of the least significant bit in x.
65// This function is used in AMM calculations for efficient bit manipulation and range queries.
66//
67// Parameters:
68//   - x: the value for which to compute the least significant bit
69//
70// Returns the index of the least significant bit (0-255).
71//
72// Panics if x is zero.
73func BitMathLeastSignificantBit(x *u256.Uint) uint8 {
74	if x.IsZero() {
75		panic(errLSBZeroInput)
76	}
77
78	temp := x.Clone()
79	hasSetBits := u256.Zero()
80	r := uint8(255)
81
82	for _, s := range lsbShifts {
83		hasSetBits = hasSetBits.And(temp, s.bitPattern)
84		if !hasSetBits.IsZero() {
85			r -= uint8(s.shift)
86		} else {
87			temp = temp.Rsh(temp, s.shift)
88		}
89	}
90
91	return r
92}