1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
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>;
}
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
];
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!();
}
}
}
return 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;
}
return 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
}
}
#[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));
}
}
|
