nautilus_model/defi/tick_map/
tick_bitmap.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16use ahash::AHashMap;
17use alloy_primitives::U256;
18
19use crate::defi::tick_map::bit_math::{least_significant_bit, most_significant_bit};
20
21/// Calculate word position and bit position for the target tick.
22fn tick_position(tick: i32) -> (i16, u8) {
23    let word_pos = (tick >> 8) as i16;
24    let bit_pos = (tick & 0xFF) as u8;
25    (word_pos, bit_pos)
26}
27
28/// Represents a tick bitmap similar to Uniswap V3 with tick spacing
29#[derive(Debug, Clone, Default)]
30pub struct TickBitmap {
31    /// Mapping of word positions to bitmap words (256 bits each)
32    words: AHashMap<i16, U256>,
33    /// Minimum spacing between valid ticks for the pool
34    tick_spacing: i32,
35}
36
37impl TickBitmap {
38    /// Create a new empty bitmap
39    pub fn new(tick_spacing: u32) -> Self {
40        Self {
41            words: AHashMap::new(),
42            tick_spacing: tick_spacing as i32,
43        }
44    }
45
46    fn compress_tick(&self, tick: i32) -> i32 {
47        tick / self.tick_spacing
48    }
49
50    /// Flip a bit in the bitmap for the given tick (toggle on/off).
51    ///
52    /// # Panics
53    ///
54    /// Panics if `tick` is not a multiple of the configured tick spacing.
55    pub fn flip_tick(&mut self, tick: i32) {
56        let remainder = tick % self.tick_spacing;
57        assert!(
58            remainder == 0,
59            "Tick must be multiple of tick spacing: tick={}, tick_spacing={}, remainder={}",
60            tick,
61            self.tick_spacing,
62            remainder
63        );
64
65        let compressed_tick = self.compress_tick(tick);
66        let (word_position, bit_position) = tick_position(compressed_tick);
67
68        let word = self.words.entry(word_position).or_insert(U256::ZERO);
69
70        // Toggle the bit using XOR
71        *word ^= U256::from(1u128) << bit_position;
72
73        // Remove empty words to save storage
74        if *word == U256::ZERO {
75            self.words.remove(&word_position);
76        }
77    }
78
79    /// Check if a tick is initialized (bit is set) in the bitmap
80    pub fn is_initialized(&self, tick: i32) -> bool {
81        let compressed_tick = self.compress_tick(tick);
82        let (word_position, bit_position) = tick_position(compressed_tick);
83
84        if let Some(&word) = self.words.get(&word_position) {
85            (word & (U256::from(1u128) << bit_position)) != U256::ZERO
86        } else {
87            false
88        }
89    }
90
91    /// Returns the next initialized tick contained in the same word (or adjacent word) as the tick that is either
92    /// to the left (less than or equal to) or right (greater than) of the given tick
93    pub fn next_initialized_tick_within_one_word(
94        &self,
95        tick: i32,
96        less_than_or_equal: bool,
97    ) -> (i32, bool) {
98        let mut compressed_tick = self.compress_tick(tick);
99        // Subtract 1 for negative non-multiples
100        if tick < 0 && tick % self.tick_spacing != 0 {
101            compressed_tick -= 1;
102        }
103
104        if less_than_or_equal {
105            let (word_pos, bit_pos) = tick_position(compressed_tick);
106            // all the 1s at or to the right of the current bitPos
107            let mask =
108                (U256::from(1u128) << bit_pos) - U256::from(1u128) + (U256::from(1u128) << bit_pos);
109            let word = self.words.get(&word_pos).copied().unwrap_or(U256::ZERO);
110            let masked = word & mask;
111
112            // if there are no initialized ticks to the right of or at the current tick, return rightmost in the word
113            let initialized = !masked.is_zero();
114            // overflow/underflow is possible, but prevented externally by limiting both tickSpacing and tick
115            let next = if initialized {
116                (compressed_tick - (bit_pos as i32) + most_significant_bit(masked))
117                    * self.tick_spacing
118            } else {
119                (compressed_tick - (bit_pos as i32)) * self.tick_spacing
120            };
121            (next, initialized)
122        } else {
123            // start from the word of the next tick, since the current tick state doesn't matter
124            let (word_pos, bit_pos) = tick_position(compressed_tick + 1);
125            // all the 1s at or to the left of the bitPos
126            let mask = !((U256::from(1u128) << bit_pos) - U256::from(1u128));
127            let word = self.words.get(&word_pos).copied().unwrap_or(U256::ZERO);
128            let masked = word & mask;
129
130            // if there are no initialized ticks to the left of the current tick, return leftmost in the word
131            let initialized = !masked.is_zero();
132            // overflow/underflow is possible, but prevented externally by limiting both tickSpacing and tick
133            let next = if initialized {
134                (compressed_tick + 1 + least_significant_bit(masked) - (bit_pos as i32))
135                    * self.tick_spacing
136            } else {
137                (compressed_tick + 1 + (255i32) - (bit_pos as i32)) * self.tick_spacing // type(uint8).max = 255
138            };
139            (next, initialized)
140        }
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use rstest::{fixture, rstest};
147
148    use super::*;
149
150    #[fixture]
151    fn tick_bitmap() -> TickBitmap {
152        TickBitmap::new(1)
153    }
154
155    #[rstest]
156    fn test_tick_to_positions() {
157        // Test positive tick
158        assert_eq!(tick_position(256), (1, 0));
159
160        // Test negative tick
161        assert_eq!(tick_position(-256), (-1, 0));
162
163        // Test tick within a word
164        assert_eq!(tick_position(100), (0, 100));
165    }
166
167    #[rstest]
168    fn test_flip_tick_toggle(mut tick_bitmap: TickBitmap) {
169        // Initially tick should not be initialized
170        assert!(!tick_bitmap.is_initialized(100));
171
172        // Toggle tick (should initialize it)
173        tick_bitmap.flip_tick(100);
174        assert!(tick_bitmap.is_initialized(100));
175
176        // Toggle again (should clear it)
177        tick_bitmap.flip_tick(100);
178        assert!(!tick_bitmap.is_initialized(100));
179
180        // Check that other ticks are not affected
181        assert!(!tick_bitmap.is_initialized(99));
182        assert!(!tick_bitmap.is_initialized(101));
183    }
184
185    #[rstest]
186    fn test_multiple_ticks_same_word(mut tick_bitmap: TickBitmap) {
187        // Initialize multiple ticks in the same word (0-255)
188        tick_bitmap.flip_tick(50);
189        tick_bitmap.flip_tick(100);
190        tick_bitmap.flip_tick(200);
191
192        assert!(tick_bitmap.is_initialized(50));
193        assert!(tick_bitmap.is_initialized(100));
194        assert!(tick_bitmap.is_initialized(200));
195        assert!(!tick_bitmap.is_initialized(51));
196    }
197
198    #[rstest]
199    fn test_multiple_ticks_different_words(mut tick_bitmap: TickBitmap) {
200        // Initialize ticks in different words
201        tick_bitmap.flip_tick(100); // Word 0
202        tick_bitmap.flip_tick(300); // Word 1
203        tick_bitmap.flip_tick(-100); // Word -1
204
205        assert!(tick_bitmap.is_initialized(100));
206        assert!(tick_bitmap.is_initialized(300));
207        assert!(tick_bitmap.is_initialized(-100));
208    }
209
210    #[rstest]
211    fn test_next_initialized_tick_within_one_word_basic(mut tick_bitmap: TickBitmap) {
212        // Initialize compressed ticks (these represent tick indices, not raw ticks)
213        tick_bitmap.flip_tick(2); // Compressed tick 2
214        tick_bitmap.flip_tick(3); // Compressed tick 3
215
216        // Search forward from tick 60 (compressed: 60/60 = 1)
217        let (tick, initialized) = tick_bitmap.next_initialized_tick_within_one_word(1, false);
218        assert!(initialized);
219        assert_eq!(tick, 2); // Should find compressed tick 2
220    }
221
222    #[rstest]
223    fn test_next_initialized_tick_within_one_word_backward(mut tick_bitmap: TickBitmap) {
224        // Initialize compressed ticks
225        tick_bitmap.flip_tick(1); // Compressed tick 1
226        tick_bitmap.flip_tick(2); // Compressed tick 2
227
228        // Search backward from tick 3
229        let (tick, initialized) = tick_bitmap.next_initialized_tick_within_one_word(3, true);
230        assert!(initialized);
231        assert_eq!(tick, 2); // Should find tick 2
232    }
233
234    #[rstest]
235    fn test_next_initialized_tick_within_one_word_no_match(tick_bitmap: TickBitmap) {
236        // Search in empty bitmap
237        let (_, initialized) = tick_bitmap.next_initialized_tick_within_one_word(60, false);
238        assert!(!initialized);
239
240        let (_, initialized) = tick_bitmap.next_initialized_tick_within_one_word(60, true);
241        assert!(!initialized);
242    }
243
244    #[rstest]
245    fn test_next_initialized_tick_with_negative_ticks(mut tick_bitmap: TickBitmap) {
246        // Initialize compressed negative ticks
247        tick_bitmap.flip_tick(-2); // Compressed tick -2
248        tick_bitmap.flip_tick(-1); // Compressed tick -1
249
250        // Search forward from -3
251        let (tick, initialized) = tick_bitmap.next_initialized_tick_within_one_word(-3, false);
252        assert!(initialized);
253        assert_eq!(tick, -2); // Should find tick -2
254    }
255
256    #[fixture]
257    fn tick_bitmap_uniswapv3_testing() -> TickBitmap {
258        // Based on values in https://github.com/Uniswap/v3-core/blob/main/test/TickBitmap.spec.ts#L89
259        let mut tick_bitmap = TickBitmap::new(1);
260        tick_bitmap.flip_tick(-200);
261        tick_bitmap.flip_tick(-55);
262        tick_bitmap.flip_tick(-4);
263        tick_bitmap.flip_tick(70);
264        tick_bitmap.flip_tick(78);
265        tick_bitmap.flip_tick(84);
266        tick_bitmap.flip_tick(139);
267        tick_bitmap.flip_tick(240);
268        tick_bitmap.flip_tick(535);
269
270        tick_bitmap
271    }
272
273    #[rstest]
274    fn test_uniswapv3_test_cases_lte_false(tick_bitmap_uniswapv3_testing: TickBitmap) {
275        let mut bitmap = tick_bitmap_uniswapv3_testing;
276
277        // Returns the tick to the right if at initialized tick.
278        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(78, false);
279        assert_eq!(next, 84);
280        assert!(initialized);
281        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(-55, false);
282        assert_eq!(next, -4);
283        assert!(initialized);
284        // Returns the tick directly to the right.
285        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(77, false);
286        assert_eq!(next, 78);
287        assert!(initialized);
288        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(-56, false);
289        assert_eq!(next, -55);
290        assert!(initialized);
291        // Returns the next words initialized tick if on the right boundary.
292        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(255, false);
293        assert_eq!(next, 511); // (255 + 255 = 510, and next is 511)
294        assert!(!initialized); // This is not an initialized tick
295        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(-257, false);
296        assert_eq!(next, -200);
297        assert!(initialized);
298        // Returns the next initialized tick from the next word.
299        bitmap.flip_tick(340);
300        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(328, false);
301        assert_eq!(next, 340);
302        assert!(initialized);
303        // It does not exceed the boundary.
304        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(508, false);
305        assert_eq!(next, 511);
306        assert!(!initialized);
307        // Skips the half-word.
308        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(383, false);
309        assert_eq!(next, 511);
310        assert!(!initialized);
311    }
312
313    #[rstest]
314    fn test_uniswapv3_test_cases_lte_true(tick_bitmap_uniswapv3_testing: TickBitmap) {
315        let mut bitmap = tick_bitmap_uniswapv3_testing;
316
317        // Returns them same tick if initialized
318        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(78, true);
319        assert_eq!(next, 78);
320        assert!(initialized);
321        // Returns tick directly to the left of input tick if not initialized.
322        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(79, true);
323        assert_eq!(next, 78);
324        assert!(initialized);
325        // It should not exceed the word boundary.
326        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(258, true);
327        assert_eq!(next, 256);
328        assert!(!initialized);
329        // At the word boundary should be correct.
330        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(256, true);
331        assert_eq!(next, 256);
332        assert!(!initialized);
333        // Left or word boundary should be correct.
334        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(255, true);
335        assert_eq!(next, 240);
336        assert!(initialized);
337        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(72, true);
338        assert_eq!(next, 70);
339        assert!(initialized);
340        // Word boundary negative.
341        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(-257, true);
342        assert_eq!(next, -512);
343        assert!(!initialized);
344        // Entire empty word
345        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(1023, true);
346        assert_eq!(next, 768);
347        assert!(!initialized);
348        // Halfway through empty word
349        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(900, true);
350        assert_eq!(next, 768);
351        assert!(!initialized);
352        // If boundary is initialized
353        bitmap.flip_tick(768);
354        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(900, true);
355        assert_eq!(next, 768);
356        assert!(initialized);
357    }
358}
nautilus_model/defi/tick_map/tick_bitmap.rs

nautilus_model/defi/tick_map/
tick_bitmap.rs
