use std::ops;
use std::fmt;
use std::fmt::Write;
use std::iter::FromIterator;
use crate::square::{File, Rank, Square};
use crate::types::Color;
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
pub struct Bitboard(pub u64);
impl Bitboard {
#[inline]
pub fn from_square(sq: Square) -> Bitboard {
Bitboard(SQUARES[usize::from(sq)])
}
#[inline]
pub fn rank(rank: Rank) -> Bitboard {
Bitboard(RANKS[usize::from(rank)])
}
#[inline]
pub fn file(file: File) -> Bitboard {
Bitboard(FILES[usize::from(file)])
}
#[inline]
pub fn relative_rank(color: Color, rank: Rank) -> Bitboard {
Bitboard::rank(color.fold(rank, rank.flip_vertical()))
}
#[must_use]
#[inline]
pub fn relative_shift(self, color: Color, shift: u32) -> Bitboard {
match color {
Color::White => Bitboard(self.0 << shift),
Color::Black => Bitboard(self.0 >> shift),
}
}
#[must_use]
#[inline]
pub fn any(self) -> bool {
self.0 != 0
}
#[inline]
pub fn is_empty(self) -> bool {
self.0 == 0
}
#[inline]
pub fn contains(self, sq: Square) -> bool {
!(self & Bitboard::from_square(sq)).is_empty()
}
#[inline]
pub fn add<T: Into<Bitboard>>(&mut self, squares: T) {
*self |= squares;
}
#[inline]
pub fn toggle<T: Into<Bitboard>>(&mut self, squares: T) {
*self ^= squares;
}
#[inline]
pub fn discard<T: Into<Bitboard>>(&mut self, squares: T) {
*self &= !squares.into();
}
#[must_use]
#[inline]
pub fn remove(&mut self, sq: Square) -> bool {
if self.contains(sq) {
self.toggle(sq);
true
} else {
false
}
}
#[inline]
pub fn set(&mut self, sq: Square, v: bool) {
if v {
self.add(sq);
} else {
self.discard(sq);
}
}
#[inline]
pub fn clear(&mut self) {
self.0 = 0;
}
#[must_use]
#[inline]
pub fn with<T: Into<Bitboard>>(self, squares: T) -> Bitboard {
self | squares
}
#[must_use]
#[inline]
pub fn without<T: Into<Bitboard>>(self, squares: T) -> Bitboard {
self & !squares.into()
}
#[inline]
pub fn is_disjoint<T: Into<Bitboard>>(self, other: T) -> bool {
(self & other).is_empty()
}
#[inline]
pub fn is_subset<T: Into<Bitboard>>(self, other: T) -> bool {
(self & !other.into()).is_empty()
}
#[inline]
pub fn is_superset<T: Into<Bitboard>>(self, other: T) -> bool {
other.into().is_subset(self)
}
#[inline]
pub fn pop_front(&mut self) -> Option<Square> {
let square = self.first();
self.0 &= self.0.wrapping_sub(1);
square
}
#[inline]
pub fn first(self) -> Option<Square> {
if self.is_empty() {
None
} else {
Some(unsafe { Square::new_unchecked(self.0.trailing_zeros()) })
}
}
#[inline]
pub fn pop_back(&mut self) -> Option<Square> {
let square = self.last();
*self ^= Bitboard::from_iter(square);
square
}
#[inline]
pub fn last(self) -> Option<Square> {
if self.is_empty() {
None
} else {
Some(unsafe { Square::new_unchecked(63 - self.0.leading_zeros()) })
}
}
#[inline]
pub fn count(self) -> usize {
self.0.count_ones() as usize
}
#[inline]
pub fn more_than_one(self) -> bool {
self.0 & self.0.wrapping_sub(1) != 0
}
#[inline]
pub fn single_square(self) -> Option<Square> {
if self.more_than_one() {
None
} else {
self.first()
}
}
#[inline]
pub fn carry_rippler(self) -> CarryRippler {
CarryRippler {
bb: self.0,
subset: 0,
first: true,
}
}
#[must_use]
#[inline]
pub fn flip_vertical(self) -> Bitboard {
Bitboard(self.0.swap_bytes())
}
#[must_use]
pub fn flip_horizontal(self) -> Bitboard {
let k1 = 0x5555_5555_5555_5555;
let k2 = 0x3333_3333_3333_3333;
let k4 = 0x0f0f_0f0f_0f0f_0f0f;
let x = self.0;
let x = ((x >> 1) & k1) | ((x & k1) << 1);
let x = ((x >> 2) & k2) | ((x & k2) << 2);
let x = ((x >> 4) & k4) | ((x & k4) << 4);
Bitboard(x)
}
#[must_use]
pub fn flip_diagonal(self) -> Bitboard {
let k1 = 0x5500_5500_5500_5500;
let k2 = 0x3333_0000_3333_0000;
let k4 = 0x0f0f_0f0f_0000_0000;
let mut x = self.0;
let t = k4 & (x ^ (x << 28));
x ^= t ^ (t >> 28);
let t = k2 & (x ^ (x << 14));
x ^= t ^ (t >> 14);
let t = k1 & (x ^ (x << 7));
x ^= t ^ (t >> 7);
Bitboard(x)
}
#[must_use]
pub fn flip_anti_diagonal(self) -> Bitboard {
let k1 = 0xaa00_aa00_aa00_aa00;
let k2 = 0xcccc_0000_cccc_0000;
let k4 = 0xf0f0_f0f0_0f0f_0f0f;
let mut x = self.0;
let t = x ^ (x << 36);
x ^= k4 & (t ^ (x >> 36));
let t = k2 & (x ^ (x << 18));
x ^= t ^ (t >> 18);
let t = k1 & (x ^ (x << 9));
x ^= t ^ (t >> 9);
Bitboard(x)
}
#[must_use]
pub fn rotate_90(self) -> Bitboard {
self.flip_diagonal().flip_vertical()
}
#[must_use]
#[inline]
pub fn rotate_180(self) -> Bitboard {
Bitboard(self.0.reverse_bits())
}
#[must_use]
pub fn rotate_270(self) -> Bitboard {
self.flip_vertical().flip_diagonal()
}
pub const EMPTY: Bitboard = Bitboard(0);
pub const ALL: Bitboard = Bitboard(!0u64);
pub const DARK_SQUARES: Bitboard = Bitboard(0xaa55_aa55_aa55_aa55);
pub const LIGHT_SQUARES: Bitboard = Bitboard(0x55aa_55aa_55aa_55aa);
pub const CORNERS: Bitboard = Bitboard(0x8100_0000_0000_0081);
pub const BACKRANKS: Bitboard = Bitboard(0xff00_0000_0000_00ff);
pub const CENTER: Bitboard = Bitboard(0x0000_0018_1800_0000);
}
static SQUARES: [u64; 64] = [0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x100,
0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x1_0000, 0x2_0000,
0x4_0000, 0x8_0000, 0x10_0000, 0x20_0000, 0x40_0000, 0x80_0000, 0x100_0000,
0x200_0000, 0x400_0000, 0x800_0000, 0x1000_0000, 0x2000_0000, 0x4000_0000,
0x8000_0000, 0x1_0000_0000, 0x2_0000_0000, 0x4_0000_0000, 0x8_0000_0000,
0x10_0000_0000, 0x20_0000_0000, 0x40_0000_0000, 0x80_0000_0000,
0x100_0000_0000, 0x200_0000_0000, 0x400_0000_0000, 0x800_0000_0000,
0x1000_0000_0000, 0x2000_0000_0000, 0x4000_0000_0000, 0x8000_0000_0000,
0x1_0000_0000_0000, 0x2_0000_0000_0000, 0x4_0000_0000_0000,
0x8_0000_0000_0000, 0x10_0000_0000_0000, 0x20_0000_0000_0000,
0x40_0000_0000_0000, 0x80_0000_0000_0000, 0x100_0000_0000_0000,
0x200_0000_0000_0000, 0x400_0000_0000_0000, 0x800_0000_0000_0000,
0x1000_0000_0000_0000, 0x2000_0000_0000_0000, 0x4000_0000_0000_0000,
0x8000_0000_0000_0000
];
static RANKS: [u64; 8] = [0xff, 0xff00, 0xff_0000, 0xff00_0000, 0xff_0000_0000, 0xff00_0000_0000, 0xff_0000_0000_0000, 0xff00_0000_0000_0000];
static FILES: [u64; 8] = [0x0101_0101_0101_0101, 0x0202_0202_0202_0202, 0x0404_0404_0404_0404, 0x0808_0808_0808_0808, 0x1010_1010_1010_1010, 0x2020_2020_2020_2020, 0x4040_4040_4040_4040, 0x8080_8080_8080_8080];
impl fmt::Debug for Bitboard {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
for rank in (0..8).map(Rank::new).rev() {
for file in (0..8).map(File::new) {
let sq = Square::from_coords(file, rank);
f.write_char(if self.contains(sq) { '1' } else { '.' })?;
f.write_char(if file < File::H { ' ' } else { '\n' })?;
}
}
Ok(())
}
}
impl fmt::UpperHex for Bitboard {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{:X}", self.0)
}
}
impl fmt::LowerHex for Bitboard {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{:x}", self.0)
}
}
impl fmt::Octal for Bitboard {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{:o}", self.0)
}
}
impl fmt::Binary for Bitboard {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{:b}", self.0)
}
}
impl From<Square> for Bitboard {
#[inline]
fn from(sq: Square) -> Bitboard {
Bitboard::from_square(sq)
}
}
impl From<Rank> for Bitboard {
#[inline]
fn from(rank: Rank) -> Bitboard {
Bitboard::rank(rank)
}
}
impl From<File> for Bitboard {
#[inline]
fn from(file: File) -> Bitboard {
Bitboard::file(file)
}
}
impl From<u64> for Bitboard {
#[inline]
fn from(bb: u64) -> Bitboard {
Bitboard(bb)
}
}
impl From<Bitboard> for u64 {
#[inline]
fn from(bb: Bitboard) -> u64 {
bb.0
}
}
impl<T> ops::BitAnd<T> for Bitboard
where
T: Into<Bitboard>,
{
type Output = Bitboard;
#[inline]
fn bitand(self, rhs: T) -> Bitboard {
let Bitboard(rhs) = rhs.into();
Bitboard(self.0 & rhs)
}
}
impl<T> ops::BitAndAssign<T> for Bitboard
where
T: Into<Bitboard>,
{
#[inline]
fn bitand_assign(&mut self, rhs: T) {
let Bitboard(rhs) = rhs.into();
self.0 &= rhs;
}
}
impl<T> ops::BitOr<T> for Bitboard
where
T: Into<Bitboard>,
{
type Output = Bitboard;
#[inline]
fn bitor(self, rhs: T) -> Bitboard {
let Bitboard(rhs) = rhs.into();
Bitboard(self.0 | rhs)
}
}
impl<T> ops::BitOrAssign<T> for Bitboard
where
T: Into<Bitboard>,
{
#[inline]
fn bitor_assign(&mut self, rhs: T) {
let Bitboard(rhs) = rhs.into();
self.0 |= rhs;
}
}
impl<T> ops::BitXor<T> for Bitboard
where
T: Into<Bitboard>,
{
type Output = Bitboard;
#[inline]
fn bitxor(self, rhs: T) -> Bitboard {
let Bitboard(rhs) = rhs.into();
Bitboard(self.0 ^ rhs)
}
}
impl<T> ops::BitXorAssign<T> for Bitboard
where
T: Into<Bitboard>,
{
#[inline]
fn bitxor_assign(&mut self, rhs: T) {
let Bitboard(rhs) = rhs.into();
self.0 ^= rhs;
}
}
impl ops::Not for Bitboard {
type Output = Bitboard;
#[inline]
fn not(self) -> Bitboard {
Bitboard(!self.0)
}
}
impl FromIterator<Square> for Bitboard {
fn from_iter<T>(iter: T) -> Self
where
T: IntoIterator<Item = Square>,
{
let mut result = Bitboard(0);
result.extend(iter);
result
}
}
impl Extend<Square> for Bitboard {
fn extend<T: IntoIterator<Item = Square>>(&mut self, iter: T) {
for square in iter {
self.add(square);
}
}
}
impl IntoIterator for Bitboard {
type Item = Square;
type IntoIter = IntoIter;
#[inline]
fn into_iter(self) -> IntoIter {
IntoIter(self)
}
}
#[derive(Debug, Clone)]
pub struct IntoIter(Bitboard);
impl Iterator for IntoIter {
type Item = Square;
#[inline]
fn next(&mut self) -> Option<Square> {
self.0.pop_front()
}
#[inline]
fn count(self) -> usize {
self.0.count()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.0.count();
(len, Some(len))
}
#[inline]
fn last(self) -> Option<Square> {
self.0.last()
}
}
impl ExactSizeIterator for IntoIter {
#[inline]
fn len(&self) -> usize {
self.0.count()
}
}
impl ::std::iter::FusedIterator for IntoIter {}
impl DoubleEndedIterator for IntoIter {
#[inline]
fn next_back(&mut self) -> Option<Square> {
self.0.pop_back()
}
}
#[derive(Debug, Clone)]
pub struct CarryRippler {
bb: u64,
subset: u64,
first: bool,
}
impl Iterator for CarryRippler {
type Item = Bitboard;
#[inline]
fn next(&mut self) -> Option<Bitboard> {
let subset = self.subset;
if subset != 0 || self.first {
self.first = false;
self.subset = self.subset.wrapping_sub(self.bb) & self.bb;
Some(Bitboard(subset))
} else {
None
}
}
#[inline]
fn last(self) -> Option<Bitboard> {
if self.subset != 0 || self.first {
Some(Bitboard(self.bb))
} else {
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(0, 1usize.checked_shl(self.bb.count_ones()))
}
}
impl ::std::iter::FusedIterator for CarryRippler {}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_more_than_one() {
assert_eq!(Bitboard(0).more_than_one(), false);
assert_eq!(Bitboard(1).more_than_one(), false);
assert_eq!(Bitboard(2).more_than_one(), false);
assert_eq!(Bitboard(3).more_than_one(), true);
assert_eq!(Bitboard::ALL.more_than_one(), true);
}
#[test]
fn test_first() {
assert_eq!(Bitboard::from_square(Square::A1).first(), Some(Square::A1));
assert_eq!(Bitboard::from_square(Square::D2).first(), Some(Square::D2));
assert_eq!(Bitboard(0).first(), None);
}
#[test]
fn test_last() {
assert_eq!(Bitboard::from_square(Square::A1).last(), Some(Square::A1));
assert_eq!(Bitboard(0).with(Square::A1).with(Square::H1).last(),
Some(Square::H1));
assert_eq!(Bitboard(0).last(), None);
}
#[test]
fn test_is_empty() {
assert!(Bitboard(0).is_empty());
assert!(!Bitboard(1).is_empty());
}
#[test]
fn test_rank() {
assert_eq!(Bitboard::rank(Rank::Fourth), Bitboard(0xff00_0000));
}
#[test]
fn test_from_iter() {
assert_eq!(Bitboard::from_iter(None), Bitboard(0));
assert_eq!(Bitboard::from_iter(Some(Square::D2)),
Bitboard::from_square(Square::D2));
}
}