path: root/src/bitboard.rs

use crate::square::Square;

/// Finite set of up to 64 bits representing chess board squares
pub type Bitboard = u64;

pub trait BitboardFns {
    /// Print bitboard on the screen
    fn print(self, title: &str);

    /// Return bitboard cardinality, aka number of elements in the set
    fn pop_count(self) -> u8;

    /// Return Bitboard with only Least Single Bit
    fn ls1b(self) -> Self;

    /// Return the square corresponding to Least Single Bit
    /// using De Brujin method. For single Bitboards it works
    /// like a mapper from Bitboards to Squares.
    ///
    /// ```rust
    /// # use chessnost::{bitboard::BitboardFns, square::Square};
    /// assert_eq!(5.bitscan(), Square::from(0));
    /// assert_eq!(4.bitscan(), Square::C1);
    /// ```
    fn bitscan(self) -> Square;

    /// Perform bitscan and reset the *ls1b*
    fn bitscan_and_reset(&mut self) -> Square;

    /// Convert bitboard into the list of squares
    fn serialize(self) -> Vec<Square>;

    /// Return bitboard shifted nort, no wrap occurs
    fn nort_one(self) -> Self;
    /// Return bitboard shifted sout, no wrap occurs
    fn sout_one(self) -> Self;
    /// Return bitboard shifted east, no wrap occurs
    fn east_one(self) -> Self;
    /// Return bitboard shifted west, no wrap occurs
    fn west_one(self) -> Self;

    /// Return bitboard with a nort fill
    fn nort_fill(self) -> Self;
    /// Return bitboard with a sout fill
    fn sout_fill(self) -> Self;

}

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
];

static NOT_A_FILE: Bitboard = 0xFEFEFEFEFEFEFEFE;
static NOT_H_FILE: Bitboard = 0x7F7F7F7F7F7F7F7F;

impl BitboardFns for Bitboard {
    fn print(self, title: &str) {
        println!("\n  {}", title);
        for rank in (0..8).rev() {
            print!("{}|", rank + 1);
            for file in 0..8 {
                let index = rank * 8 + file;
                print!("{}", if self >> index & 1 == 1 { "⚫" } else { ". " });
                if file == 7 {
                    println!();
                }
            }
        }
        println!("  a b c d e f g h");
    }

    fn pop_count(mut self) -> u8 {
        let mut count = 0;
        while self > 0 {
            count += 1;
            self &= self - 1;
        }
        count
    }


    fn ls1b(self) -> Self {
        if self == 0 {
            return 0
        }
        self & !(self - 1)
    }


    fn bitscan(self) -> Square {
        // TODO: generate private De Brujin routine
        debug_assert!(self != 0, "Can not bitscan empty bitboard");
        let magic: u64 = 0x03f79d71b4cb0a89;
        let ls1b = self.ls1b();
        let index = DE_BRUJIN_SEQUENCE[(((ls1b as u128 * magic as u128) as u64) >> 58) as usize];
        Square::from(index)
    }

    fn bitscan_and_reset(&mut self) -> Square {
        let square = self.bitscan();
        *self &= *self - 1; // Reset ls1b
        square
    }

    fn serialize(mut self) -> Vec<Square> {
        let mut serialized = Vec::with_capacity(64);
        while self > 0 {
            serialized.push(self.bitscan_and_reset());
        }
        serialized
    }

    fn nort_one(self) -> Self {
        self << 8
    }

    fn sout_one(self) -> Self {
        self >> 8
    }

    fn east_one(self) -> Self {
        (self << 1) & NOT_A_FILE
    }

    fn west_one(self) -> Self {
        (self >> 1) & NOT_H_FILE
    }

    fn nort_fill(self) -> Self {
        let mut fill = self;
        fill |= fill << 8;
        fill |= fill << 16;
        fill |= fill << 32;
        fill
    }

    fn sout_fill(self) -> Self {
        let mut fill = self;
        fill |= fill >> 8;
        fill |= fill >> 16;
        fill |= fill >> 32;
        fill
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_pop_count() {
        assert_eq!(127.pop_count(), 7);
    }

    #[test]
    fn test_ls1b() {
        assert_eq!(38.ls1b(), 2);
        assert_eq!(16.ls1b(), 16);
        assert_eq!(20.ls1b(), 4);
    }

    #[test]
    fn test_bitscan() {
        assert_eq!(4.bitscan(), Square::from(2));
        assert_eq!(16.bitscan(), Square::from(4));
        assert_eq!(64.bitscan(), Square::from(6));
        assert_eq!(128.bitscan(), Square::from(7));
    }

    #[test]
    fn test_bitscan_with_non_single_bb() {
        assert_eq!(5.bitscan(), Square::from(0));
        assert_eq!(6.bitscan(), Square::from(1));
        assert_eq!(7.bitscan(), Square::from(0));
    }

    #[test]
    fn test_serialize_bitboard() {
        let bb = 1 << 4 | 1 << 15 | 1 << 60;
        let serialized = bb.serialize();
        assert_eq!(serialized[0], Square::from(4));
        assert_eq!(serialized[1], Square::from(15));
        assert_eq!(serialized[2], Square::from(60));
    }

    #[test]
    fn shifts() {
        let bb = Square::E4.to_bitboard();
        assert_eq!(bb.nort_one(), Square::E5.to_bitboard());
        assert_eq!(bb.sout_one(), Square::E3.to_bitboard());
        assert_eq!(bb.west_one(), Square::D4.to_bitboard());
        assert_eq!(bb.east_one(), Square::F4.to_bitboard());
    }

    #[test]
    fn shifts_wraps() {
        assert_eq!(Square::A1.to_bitboard().sout_one(), 0);
        assert_eq!(Square::A1.to_bitboard().west_one(), 0);
        assert_eq!(Square::H8.to_bitboard().nort_one(), 0);
        assert_eq!(Square::H8.to_bitboard().east_one(), 0);
    }

    #[test]
    fn fills() {
        let bb = Square::A4.to_bitboard() | Square::E4.to_bitboard();
        let nort = bb.nort_fill();
        let sout = bb.sout_fill();

        assert_eq!(nort.pop_count(), 10);
        assert!(nort & Square::A8.to_bitboard() != 0);
        assert!(nort & Square::E8.to_bitboard() != 0);

        assert_eq!(sout.pop_count(), 8);
        assert!(sout & Square::A1.to_bitboard() != 0);
        assert!(sout & Square::E1.to_bitboard() != 0);
    }
}