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

nautilus_model/defi/tick_map/
tick_bitmap.rs
