aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/bitboard.rs50
1 files changed, 35 insertions, 15 deletions
diff --git a/src/bitboard.rs b/src/bitboard.rs
index 3df4902..ed7ec1b 100644
--- a/src/bitboard.rs
+++ b/src/bitboard.rs
@@ -39,28 +39,47 @@ pub fn ls1b(bb: Bitboard) -> Bitboard {
bb & !(bb - 1)
}
-/// Log base 2 (aka Trailing Zero Count)
+const DE_BRUJIN_SEQUENCE: [u8; 64] = [
+ 0, 1, 48, 2, 57, 49, 28, 3,
+ 61, 58, 50, 42, 38, 29, 17, 4,
+ 62, 55, 59, 36, 53, 51, 43, 22,
+ 45, 39, 33, 30, 24, 18, 12, 5,
+ 63, 47, 56, 27, 60, 41, 37, 16,
+ 54, 35, 52, 21, 44, 32, 23, 11,
+ 46, 26, 40, 15, 34, 20, 31, 10,
+ 25, 14, 19, 9, 13, 8, 7, 6
+];
+
+/// Return the square corresponding to Least Single Bit
+/// using De Brujin method. For single Bitboards it works
+/// like a mapper from Bitboards to Squares.
///
-/// WARNING: Only works for SINGLE Bitboards
-/// Useful for calculating bit-index of LS1B
+/// ```rust
+/// # use chessnost::{bitboard::bitscan, square::Square};
+/// assert_eq!(bitscan(5), Square::from(0));
+/// assert_eq!(bitscan(4), Square::C1);
+/// ```
pub fn bitscan(bb: Bitboard) -> Square {
- debug_assert!(pop_count(bb) == 1, "Bitscan only works for SINGLE Bitboards!");
- Square::from(pop_count(bb - 1))
+ // TODO: generate private De Brujin routine
+ debug_assert!(bb != 0, "Can not bitscan empty bitboard");
+ let magic: u64 = 0x03f79d71b4cb0a89;
+ let ls1b = ls1b(bb);
+ let index = DE_BRUJIN_SEQUENCE[(((ls1b as u128 * magic as u128) as u64) >> 58) as usize];
+ Square::from(index)
}
-/// Finds and removes ls1b in the bitboard, returning it's index
+/// Perform bitscan and reset the *ls1b*
pub fn bitscan_and_reset(bb: &mut Bitboard) -> Square {
- let ls1b_bitboard = ls1b(*bb);
- *bb ^= ls1b_bitboard;
- bitscan(ls1b_bitboard)
+ let square = bitscan(*bb);
+ *bb &= *bb - 1; // Reset ls1b
+ square
}
/// Convert bitboard into the list of squares
-pub fn serialize_bitboard(bb: Bitboard) -> Vec<Square> {
+pub fn serialize_bitboard(mut bb: Bitboard) -> Vec<Square> {
let mut serialized = Vec::with_capacity(64);
- let mut bitboard = bb;
- while bitboard > 0 {
- serialized.push(bitscan_and_reset(&mut bitboard));
+ while bb > 0 {
+ serialized.push(bitscan_and_reset(&mut bb));
}
serialized
}
@@ -90,9 +109,10 @@ mod tests {
}
#[test]
- #[should_panic(expected = "Bitscan only works for SINGLE Bitboards!")]
fn test_bitscan_with_non_single_bb() {
- bitscan(5);
+ assert_eq!(bitscan(5), Square::from(0));
+ assert_eq!(bitscan(6), Square::from(1));
+ assert_eq!(bitscan(7), Square::from(0));
}
#[test]