From abb303329c9a1628c6f1e5d29fb1a48021a87879 Mon Sep 17 00:00:00 2001
From: eug-vs <eugene@eug-vs.xyz>
Date: Thu, 2 Feb 2023 20:24:53 +0300
Subject: perf: use De Bruijn algorithm for bitscanning

---
 src/bitboard.rs | 50 +++++++++++++++++++++++++++++++++++---------------
 1 file 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]
-- 
cgit v1.2.3