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

nautilus_model/defi/tick_map/
tick_bitmap.rs
