timecat/utils/
bitboard.rs

1use super::*;
2
3#[repr(transparent)]
4#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
5#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Debug, Hash)]
6pub struct BitBoard(u64);
7
8impl BitBoard {
9    pub const EMPTY: Self = Self(0);
10    pub const ALL: Self = BitBoard::new(0xFFFFFFFFFFFFFFFF);
11
12    #[inline]
13    pub const fn new(bb: u64) -> Self {
14        unsafe { std::mem::transmute(bb) }
15    }
16
17    #[inline]
18    pub const fn set_mask(&mut self, mask: u64) {
19        self.0 = mask;
20    }
21
22    #[inline]
23    pub const fn from_rank_and_file(rank: Rank, file: File) -> Self {
24        Self::new(1 << ((rank.to_int() << 3) | file.to_int()))
25    }
26
27    #[inline]
28    pub const fn popcnt(self) -> u32 {
29        self.0.count_ones()
30    }
31
32    #[inline]
33    pub const fn reverse_colors(self) -> Self {
34        Self::new(self.0.swap_bytes())
35    }
36
37    #[inline]
38    pub const fn to_square_index_unchecked(self) -> usize {
39        self.0.trailing_zeros() as usize
40    }
41
42    #[inline]
43    pub fn to_square_unchecked(self) -> Square {
44        *get_item_unchecked!(ALL_SQUARES, self.to_square_index_unchecked())
45    }
46
47    #[inline]
48    pub const fn to_square_index(self) -> Option<usize> {
49        if self.is_empty() {
50            None
51        } else {
52            Some(self.to_square_index_unchecked())
53        }
54    }
55
56    #[inline]
57    pub fn to_square(self) -> Option<Square> {
58        if self.is_empty() {
59            None
60        } else {
61            Some(self.to_square_unchecked())
62        }
63    }
64
65    #[inline]
66    pub fn xor_square(&mut self, square: Square) {
67        self.0 ^= square.to_bitboard();
68    }
69
70    #[inline]
71    pub fn remove_square(&mut self, square: Square) {
72        self.0 &= !square.to_bitboard();
73    }
74
75    pub fn pop_square_unchecked(&mut self) -> Square {
76        let square = self.to_square_unchecked();
77        self.xor_square(square);
78        square
79    }
80
81    #[inline]
82    pub fn pop_square(&mut self) -> Option<Square> {
83        if self.is_empty() {
84            None
85        } else {
86            Some(self.pop_square_unchecked())
87        }
88    }
89
90    #[inline]
91    pub const fn wrapping_mul(self, rhs: Self) -> Self {
92        Self::new(self.0.wrapping_mul(rhs.0))
93    }
94
95    #[inline]
96    pub const fn is_empty(self) -> bool {
97        self.0 == Self::EMPTY.0
98    }
99
100    /// <https://www.chessprogramming.org/Flipping_Mirroring_and_Rotating#FlipVertically>
101    pub const fn flip_vertical(self) -> Self {
102        let mut bb = self.0;
103        bb = ((bb >> 8) & 0x00FF_00FF_00FF_00FF) | ((bb & 0x00FF_00FF_00FF_00FF) << 8);
104        bb = ((bb >> 16) & 0x0000_FFFF_0000_FFFF) | ((bb & 0x0000_FFFF_0000_FFFF) << 16);
105        bb = (bb >> 32) | ((bb & 0x0000_0000_FFFF_FFFF) << 32);
106        Self::new(bb)
107    }
108
109    /// <https://www.chessprogramming.org/Flipping_Mirroring_and_Rotating#MirrorHorizontally>
110    pub const fn flip_horizontal(self) -> Self {
111        let mut bb = self.0;
112        bb = ((bb >> 1) & 0x5555_5555_5555_5555) | ((bb & 0x5555_5555_5555_5555) << 1);
113        bb = ((bb >> 2) & 0x3333_3333_3333_3333) | ((bb & 0x3333_3333_3333_3333) << 2);
114        bb = ((bb >> 4) & 0x0F0F_0F0F_0F0F_0F0F) | ((bb & 0x0F0F_0F0F_0F0F_0F0F) << 4);
115        Self::new(bb)
116    }
117
118    /// <https://www.chessprogramming.org/Flipping_Mirroring_and_Rotating#FlipabouttheDiagonal>
119    pub const fn flip_diagonal(self) -> Self {
120        let mut bb = self.0;
121        let mut t = (bb ^ (bb << 28)) & 0x0F0F_0F0F_0000_0000;
122        bb = bb ^ t ^ (t >> 28);
123        t = (bb ^ (bb << 14)) & 0x3333_0000_3333_0000;
124        bb = bb ^ t ^ (t >> 14);
125        t = (bb ^ (bb << 7)) & 0x5500_5500_5500_5500;
126        bb = bb ^ t ^ (t >> 7);
127        Self::new(bb)
128    }
129
130    /// <https://www.chessprogramming.org/Flipping_Mirroring_and_Rotating#FlipabouttheAntidiagonal>
131    pub const fn flip_anti_diagonal(self) -> Self {
132        let mut bb = self.0;
133        let mut t = bb ^ (bb << 36);
134        bb = bb ^ ((t ^ (bb >> 36)) & 0xF0F0_F0F0_0F0F_0F0F);
135        t = (bb ^ (bb << 18)) & 0xCCCC_0000_CCCC_0000;
136        bb = bb ^ t ^ (t >> 18);
137        t = (bb ^ (bb << 9)) & 0xAA00_AA00_AA00_AA00;
138        bb = bb ^ t ^ (t >> 9);
139        Self::new(bb)
140    }
141
142    #[inline]
143    pub const fn shift_forward(self, color: Color) -> Self {
144        match color {
145            White => self.shift_up(),
146            Black => self.shift_down(),
147        }
148    }
149
150    #[inline]
151    pub const fn shift_backward(self, color: Color) -> Self {
152        match color {
153            White => self.shift_down(),
154            Black => self.shift_up(),
155        }
156    }
157
158    #[inline]
159    pub const fn shift_up(self) -> Self {
160        Self::new((self.0 & !BB_RANK_8.0) << 8)
161    }
162
163    #[inline]
164    pub const fn shift_down(self) -> Self {
165        Self::new(self.0 >> 8)
166    }
167
168    #[inline]
169    pub const fn shift_left(self) -> Self {
170        Self::new((self.0 & !BB_FILE_A.0) >> 1)
171    }
172
173    #[inline]
174    pub const fn shift_right(self) -> Self {
175        Self::new((self.0 & !BB_FILE_H.0) << 1)
176    }
177
178    pub const fn shift_up_n_times(self, n: u8) -> Self {
179        // TODO: Optimize the function
180        if n > 7 {
181            return BitBoard::EMPTY;
182        }
183        let mut bb = self.0;
184        let mut i = 0;
185        while i < n {
186            bb = (bb & !BB_RANK_8.0) << 8;
187            i += 1;
188        }
189        Self::new(bb)
190    }
191
192    pub const fn shift_down_n_times(self, n: u8) -> Self {
193        // TODO: Optimize the function
194        if n > 7 {
195            return BitBoard::EMPTY;
196        }
197        let mut bb = self.0;
198        let mut i = 0;
199        while i < n {
200            bb >>= 8;
201            i += 1;
202        }
203        Self::new(bb)
204    }
205
206    pub const fn shift_left_n_times(self, n: u8) -> Self {
207        // TODO: Optimize the function
208        if n > 7 {
209            return BitBoard::EMPTY;
210        }
211        let mut bb = self.0;
212        let mut i = 0;
213        while i < n {
214            bb = (bb & !BB_FILE_A.0) >> 1;
215            i += 1;
216        }
217        Self::new(bb)
218    }
219
220    pub const fn shift_right_n_times(self, n: u8) -> Self {
221        // TODO: Optimize the function
222        if n > 7 {
223            return BitBoard::EMPTY;
224        }
225        let mut bb = self.0;
226        let mut i = 0;
227        while i < n {
228            bb = (bb & !BB_FILE_H.0) << 1;
229            i += 1;
230        }
231        Self::new(bb)
232    }
233
234    #[inline]
235    pub fn contains(self, square: Square) -> bool {
236        !(self & square.to_bitboard()).is_empty()
237    }
238
239    #[inline]
240    pub const fn into_inner(self) -> u64 {
241        self.0
242    }
243
244    #[inline]
245    pub const fn to_usize(self) -> usize {
246        self.0 as usize
247    }
248}
249
250impl From<&BitBoard> for u64 {
251    #[inline]
252    fn from(value: &BitBoard) -> Self {
253        value.0
254    }
255}
256
257impl From<BitBoard> for u64 {
258    #[inline]
259    fn from(value: BitBoard) -> Self {
260        (&value).into()
261    }
262}
263
264impl From<u64> for BitBoard {
265    #[inline]
266    fn from(value: u64) -> Self {
267        Self::new(value)
268    }
269}
270
271impl From<&u64> for BitBoard {
272    #[inline]
273    fn from(value: &u64) -> Self {
274        (*value).into()
275    }
276}
277
278macro_rules! implement_u64_methods {
279    ($($visibility:vis const fn $function:ident(self $(, $argument:ident: $argument_type:ty)* $(,)?) -> $return_type:ty),* $(,)?) => {
280        impl BitBoard {
281            $(
282                #[inline]
283                $visibility const fn $function(&self, $($argument: $argument_type),*) -> $return_type {
284                    Self::new(self.0.$function($($argument),*))
285                }
286            )*
287        }
288    };
289}
290
291implement_u64_methods!(
292    pub const fn wrapping_shl(self, rhs: u32) -> Self,
293    pub const fn wrapping_shr(self, rhs: u32) -> Self,
294);
295
296macro_rules! implement_bitwise_operations {
297    (@bit_shifting $direct_trait: ident, $assign_trait: ident, $direct_func: ident, $assign_func: ident) => {
298        impl<T> $assign_trait<T> for BitBoard where u64: $assign_trait<T> {
299
300            #[inline]
301            fn $assign_func(&mut self, rhs: T) {
302                self.0.$assign_func(rhs)
303            }
304        }
305
306        impl<T> $direct_trait<T> for BitBoard where Self: $assign_trait<T> {
307            type Output = Self;
308
309            #[inline]
310            fn $direct_func(mut self, rhs: T) -> Self::Output {
311                self.$assign_func(rhs);
312                self
313            }
314        }
315
316        impl<T> $direct_trait<T> for &BitBoard where BitBoard: $direct_trait<T> {
317            type Output = <BitBoard as $direct_trait<T>>::Output;
318
319            #[inline]
320            fn $direct_func(self, rhs: T) -> Self::Output {
321                (*self).$direct_func(rhs)
322            }
323        }
324    };
325
326    ($direct_trait: ident, $assign_trait: ident, $direct_func: ident, $assign_func: ident) => {
327        implement_bitwise_operations!(@bigger_integer_implementation $direct_trait, $assign_trait, $direct_func, $assign_func, u128);
328        implement_bitwise_operations!(@bigger_integer_implementation $direct_trait, $assign_trait, $direct_func, $assign_func, u64);
329        implement_bitwise_operations!(@bigger_integer_implementation $direct_trait, $assign_trait, $direct_func, $assign_func, i128);
330
331        impl<T> $assign_trait<T> for BitBoard where u64: From<T> {
332
333            #[inline]
334            fn $assign_func(&mut self, rhs: T) {
335                self.0.$assign_func(u64::from(rhs))
336            }
337        }
338
339        impl<T> $direct_trait<T> for BitBoard where u64: From<T> {
340            type Output = Self;
341
342            #[inline]
343            fn $direct_func(mut self, rhs: T) -> Self::Output {
344                self.$assign_func(rhs);
345                self
346            }
347        }
348
349        impl<T> $direct_trait<T> for &BitBoard where u64: From<T> {
350            type Output = BitBoard;
351
352            #[inline]
353            fn $direct_func(self, rhs: T) -> Self::Output {
354                (*self).$direct_func(rhs)
355            }
356        }
357    };
358
359    (@bigger_integer_implementation $direct_trait: ident, $assign_trait: ident, $direct_func: ident, $assign_func: ident, $int_type: ident) => {
360        impl $assign_trait<&BitBoard> for $int_type {
361            #[inline]
362            fn $assign_func(&mut self, rhs: &BitBoard) {
363                self.$assign_func(rhs.0 as $int_type)
364            }
365        }
366
367        impl $assign_trait<BitBoard> for $int_type {
368            #[inline]
369            fn $assign_func(&mut self, rhs: BitBoard) {
370                self.$assign_func(&rhs)
371            }
372        }
373
374        impl $direct_trait<&BitBoard> for $int_type {
375            type Output = $int_type;
376
377            #[inline]
378            fn $direct_func(mut self, rhs: &BitBoard) -> Self::Output {
379                self.$assign_func(rhs);
380                self
381            }
382        }
383
384        impl $direct_trait<BitBoard> for $int_type {
385            type Output = $int_type;
386
387            #[inline]
388            fn $direct_func(self, rhs: BitBoard) -> Self::Output {
389                self.$direct_func(&rhs)
390            }
391        }
392
393        impl $direct_trait<&BitBoard> for &$int_type {
394            type Output = $int_type;
395
396            #[inline]
397            fn $direct_func(self, rhs: &BitBoard) -> Self::Output {
398                (*self).$direct_func(rhs)
399            }
400        }
401
402        impl $direct_trait<BitBoard> for &$int_type {
403            type Output = $int_type;
404
405            #[inline]
406            fn $direct_func(self, rhs: BitBoard) -> Self::Output {
407                self.$direct_func(&rhs)
408            }
409        }
410    };
411}
412
413implement_bitwise_operations!(BitAnd, BitAndAssign, bitand, bitand_assign);
414implement_bitwise_operations!(BitOr, BitOrAssign, bitor, bitor_assign);
415implement_bitwise_operations!(BitXor, BitXorAssign, bitxor, bitxor_assign);
416implement_bitwise_operations!(Mul, MulAssign, mul, mul_assign);
417implement_bitwise_operations!(@bit_shifting Shl, ShlAssign, shl, shl_assign);
418implement_bitwise_operations!(@bit_shifting Shr, ShrAssign, shr, shr_assign);
419
420impl Not for &BitBoard {
421    type Output = BitBoard;
422
423    #[inline]
424    fn not(self) -> BitBoard {
425        BitBoard::new(!self.0)
426    }
427}
428
429impl Not for BitBoard {
430    type Output = BitBoard;
431
432    #[inline]
433    fn not(self) -> BitBoard {
434        !&self
435    }
436}
437
438impl Iterator for BitBoard {
439    type Item = Square;
440
441    #[inline]
442    fn next(&mut self) -> Option<Square> {
443        self.pop_square()
444    }
445}
446
447impl fmt::Display for BitBoard {
448    #[inline]
449    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
450        let mut skeleton = get_board_skeleton();
451        let occupied_symbol = "X".colorize(BITBOARD_OCCUPIED_SQUARE_STYLE);
452        for square in SQUARES_HORIZONTAL_MIRROR {
453            skeleton = skeleton.replacen(
454                'O',
455                if self.contains(square) {
456                    &occupied_symbol
457                } else {
458                    " "
459                },
460                1,
461            );
462        }
463        write!(f, "{skeleton}")
464    }
465}
466
467#[cfg(feature = "pyo3")]
468impl<'source> FromPyObject<'source> for BitBoard {
469    fn extract_bound(ob: &Bound<'source, PyAny>) -> PyResult<Self> {
470        if let Ok(int) = ob.extract::<u64>() {
471            return Ok(Self::new(int));
472        }
473        Err(Pyo3Error::Pyo3TypeConversionError {
474            from: ob.to_string(),
475            to: std::any::type_name::<Self>().to_string(),
476        }
477        .into())
478    }
479}
timecat/utils/bitboard.rs

timecat/utils/
bitboard.rs
