nautilus_model/defi/tick_map/
tick_bitmap.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2025 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 std::collections::HashMap;
17
18use alloy_primitives::U256;
19
20use crate::defi::tick_map::bit_math::{least_significant_bit, most_significant_bit};
21
22/// Calculate word position and bit position for the target tick.
23fn tick_position(tick: i32) -> (i16, u8) {
24    let word_pos = (tick >> 8) as i16;
25    let bit_pos = (tick & 0xFF) as u8;
26    (word_pos, bit_pos)
27}
28
29/// Represents a tick bitmap similar to Uniswap V3 with tick spacing
30#[derive(Debug, Clone, Default)]
31pub struct TickBitmap {
32    /// Mapping of word positions to bitmap words (256 bits each)
33    words: HashMap<i16, U256>,
34    /// Minimum spacing between valid ticks for the pool
35    tick_spacing: i32,
36}
37
38impl TickBitmap {
39    /// Create a new empty bitmap
40    pub fn new(tick_spacing: u32) -> Self {
41        Self {
42            words: HashMap::new(),
43            tick_spacing: tick_spacing as i32,
44        }
45    }
46
47    fn compress_tick(&self, tick: i32) -> i32 {
48        tick / self.tick_spacing
49    }
50
51    /// Flip a bit in the bitmap for the given tick (toggle on/off).
52    ///
53    /// # Panics
54    ///
55    /// Panics if `tick` is not a multiple of the configured tick spacing.
56    pub fn flip_tick(&mut self, tick: i32) {
57        let remainder = tick % self.tick_spacing;
58        if remainder != 0 {
59            panic!(
60                "Tick must be multiple of tick spacing: tick={}, tick_spacing={}, remainder={}",
61                tick, self.tick_spacing, remainder
62            );
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////////////////////////////////////////////////////////////////////////////////
145// Tests
146////////////////////////////////////////////////////////////////////////////////
147
148#[cfg(test)]
149mod tests {
150    use rstest::{fixture, rstest};
151
152    use super::*;
153
154    #[fixture]
155    fn tick_bitmap() -> TickBitmap {
156        TickBitmap::new(1)
157    }
158
159    #[rstest]
160    fn test_tick_to_positions() {
161        // Test positive tick
162        assert_eq!(tick_position(256), (1, 0));
163
164        // Test negative tick
165        assert_eq!(tick_position(-256), (-1, 0));
166
167        // Test tick within a word
168        assert_eq!(tick_position(100), (0, 100));
169    }
170
171    #[rstest]
172    fn test_flip_tick_toggle(mut tick_bitmap: TickBitmap) {
173        // Initially tick should not be initialized
174        assert!(!tick_bitmap.is_initialized(100));
175
176        // Toggle tick (should initialize it)
177        tick_bitmap.flip_tick(100);
178        assert!(tick_bitmap.is_initialized(100));
179
180        // Toggle again (should clear it)
181        tick_bitmap.flip_tick(100);
182        assert!(!tick_bitmap.is_initialized(100));
183
184        // Check that other ticks are not affected
185        assert!(!tick_bitmap.is_initialized(99));
186        assert!(!tick_bitmap.is_initialized(101));
187    }
188
189    #[rstest]
190    fn test_multiple_ticks_same_word(mut tick_bitmap: TickBitmap) {
191        // Initialize multiple ticks in the same word (0-255)
192        tick_bitmap.flip_tick(50);
193        tick_bitmap.flip_tick(100);
194        tick_bitmap.flip_tick(200);
195
196        assert!(tick_bitmap.is_initialized(50));
197        assert!(tick_bitmap.is_initialized(100));
198        assert!(tick_bitmap.is_initialized(200));
199        assert!(!tick_bitmap.is_initialized(51));
200    }
201
202    #[rstest]
203    fn test_multiple_ticks_different_words(mut tick_bitmap: TickBitmap) {
204        // Initialize ticks in different words
205        tick_bitmap.flip_tick(100); // Word 0
206        tick_bitmap.flip_tick(300); // Word 1
207        tick_bitmap.flip_tick(-100); // Word -1
208
209        assert!(tick_bitmap.is_initialized(100));
210        assert!(tick_bitmap.is_initialized(300));
211        assert!(tick_bitmap.is_initialized(-100));
212    }
213
214    #[rstest]
215    fn test_next_initialized_tick_within_one_word_basic(mut tick_bitmap: TickBitmap) {
216        // Initialize compressed ticks (these represent tick indices, not raw ticks)
217        tick_bitmap.flip_tick(2); // Compressed tick 2
218        tick_bitmap.flip_tick(3); // Compressed tick 3
219
220        // Search forward from tick 60 (compressed: 60/60 = 1)
221        let (tick, initialized) = tick_bitmap.next_initialized_tick_within_one_word(1, false);
222        assert!(initialized);
223        assert_eq!(tick, 2); // Should find compressed tick 2
224    }
225
226    #[rstest]
227    fn test_next_initialized_tick_within_one_word_backward(mut tick_bitmap: TickBitmap) {
228        // Initialize compressed ticks
229        tick_bitmap.flip_tick(1); // Compressed tick 1
230        tick_bitmap.flip_tick(2); // Compressed tick 2
231
232        // Search backward from tick 3
233        let (tick, initialized) = tick_bitmap.next_initialized_tick_within_one_word(3, true);
234        assert!(initialized);
235        assert_eq!(tick, 2); // Should find tick 2
236    }
237
238    #[rstest]
239    fn test_next_initialized_tick_within_one_word_no_match(tick_bitmap: TickBitmap) {
240        // Search in empty bitmap
241        let (_, initialized) = tick_bitmap.next_initialized_tick_within_one_word(60, false);
242        assert!(!initialized);
243
244        let (_, initialized) = tick_bitmap.next_initialized_tick_within_one_word(60, true);
245        assert!(!initialized);
246    }
247
248    #[rstest]
249    fn test_next_initialized_tick_with_negative_ticks(mut tick_bitmap: TickBitmap) {
250        // Initialize compressed negative ticks
251        tick_bitmap.flip_tick(-2); // Compressed tick -2
252        tick_bitmap.flip_tick(-1); // Compressed tick -1
253
254        // Search forward from -3
255        let (tick, initialized) = tick_bitmap.next_initialized_tick_within_one_word(-3, false);
256        assert!(initialized);
257        assert_eq!(tick, -2); // Should find tick -2
258    }
259
260    #[fixture]
261    fn tick_bitmap_uniswapv3_testing() -> TickBitmap {
262        // Based on values in https://github.com/Uniswap/v3-core/blob/main/test/TickBitmap.spec.ts#L89
263        let mut tick_bitmap = TickBitmap::new(1);
264        tick_bitmap.flip_tick(-200);
265        tick_bitmap.flip_tick(-55);
266        tick_bitmap.flip_tick(-4);
267        tick_bitmap.flip_tick(70);
268        tick_bitmap.flip_tick(78);
269        tick_bitmap.flip_tick(84);
270        tick_bitmap.flip_tick(139);
271        tick_bitmap.flip_tick(240);
272        tick_bitmap.flip_tick(535);
273
274        tick_bitmap
275    }
276
277    #[rstest]
278    fn test_uniswapv3_test_cases_lte_false(tick_bitmap_uniswapv3_testing: TickBitmap) {
279        let mut bitmap = tick_bitmap_uniswapv3_testing;
280
281        // Returns the tick to the right if at initialized tick.
282        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(78, false);
283        assert_eq!(next, 84);
284        assert!(initialized);
285        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(-55, false);
286        assert_eq!(next, -4);
287        assert!(initialized);
288        // Returns the tick directly to the right.
289        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(77, false);
290        assert_eq!(next, 78);
291        assert!(initialized);
292        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(-56, false);
293        assert_eq!(next, -55);
294        assert!(initialized);
295        // Returns the next words initialized tick if on the right boundary.
296        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(255, false);
297        assert_eq!(next, 511); // (255 + 255 = 510, and next is 511)
298        assert!(!initialized); // This is not an initialized tick
299        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(-257, false);
300        assert_eq!(next, -200);
301        assert!(initialized);
302        // Returns the next initialized tick from the next word.
303        bitmap.flip_tick(340);
304        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(328, false);
305        assert_eq!(next, 340);
306        assert!(initialized);
307        // It does not exceed the boundary.
308        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(508, false);
309        assert_eq!(next, 511);
310        assert!(!initialized);
311        // Skips the half-word.
312        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(383, false);
313        assert_eq!(next, 511);
314        assert!(!initialized);
315    }
316
317    #[rstest]
318    fn test_uniswapv3_test_cases_lte_true(tick_bitmap_uniswapv3_testing: TickBitmap) {
319        let mut bitmap = tick_bitmap_uniswapv3_testing;
320
321        // Returns them same tick if initialized
322        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(78, true);
323        assert_eq!(next, 78);
324        assert!(initialized);
325        // Returns tick directly to the left of input tick if not initialized.
326        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(79, true);
327        assert_eq!(next, 78);
328        assert!(initialized);
329        // It should not exceed the word boundary.
330        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(258, true);
331        assert_eq!(next, 256);
332        assert!(!initialized);
333        // At the word boundary should be correct.
334        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(256, true);
335        assert_eq!(next, 256);
336        assert!(!initialized);
337        // Left or word boundary should be correct.
338        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(255, true);
339        assert_eq!(next, 240);
340        assert!(initialized);
341        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(72, true);
342        assert_eq!(next, 70);
343        assert!(initialized);
344        // Word boundary negative.
345        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(-257, true);
346        assert_eq!(next, -512);
347        assert!(!initialized);
348        // Entire empty word
349        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(1023, true);
350        assert_eq!(next, 768);
351        assert!(!initialized);
352        // Halfway through empty word
353        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(900, true);
354        assert_eq!(next, 768);
355        assert!(!initialized);
356        // If boundary is initialized
357        bitmap.flip_tick(768);
358        let (next, initialized) = bitmap.next_initialized_tick_within_one_word(900, true);
359        assert_eq!(next, 768);
360        assert!(initialized);
361    }
362}
nautilus_model/defi/tick_map/tick_bitmap.rs

nautilus_model/defi/tick_map/
tick_bitmap.rs
