atomic_movegen/
magic.rs

1//! Magic bitboards for sliding piece attacks.
2//!
3//! Replaces the ray-casting loop with a constant-time table lookup
4//! using precomputed magic multipliers.
5//!
6//! Tables are initialized once at first use via `OnceLock`; masks,
7//! magic numbers, and index bits are `const` arrays (zero indirection).
8
9use crate::types::*;
10use std::sync::OnceLock;
11
12const ROOK_MAGICS: [u64; 64] = [
13    0xa8002c000108020,
14    0x6c00049b0002001,
15    0x100200010090040,
16    0x2480041000800801,
17    0x280028004000800,
18    0x900410008040022,
19    0x280020001001080,
20    0x2880002041000080,
21    0xa000800080400034,
22    0x4808020004000,
23    0x2290802004801000,
24    0x411000d00100020,
25    0x402800800040080,
26    0xb000401004208,
27    0x2409000100040200,
28    0x1002100004082,
29    0x22878001e24000,
30    0x1090810021004010,
31    0x801030040200012,
32    0x500808008001000,
33    0xa08018014000880,
34    0x8000808004000200,
35    0x201008080010200,
36    0x801020000441091,
37    0x800080204005,
38    0x1040200040100048,
39    0x120200402082,
40    0xd14880480100080,
41    0x12040280080080,
42    0x100040080020080,
43    0x9020010080800200,
44    0x813241200148449,
45    0x491604001800080,
46    0x100401000402001,
47    0x4820010021001040,
48    0x400402202000812,
49    0x209009005000802,
50    0x810800601800400,
51    0x4301083214000150,
52    0x204026458e001401,
53    0x40204000808000,
54    0x8001008040010020,
55    0x8410820820420010,
56    0x1003001000090020,
57    0x804040008008080,
58    0x12000810020004,
59    0x1000100200040208,
60    0x430000a044020001,
61    0x280009023410300,
62    0xe0100040002240,
63    0x200100401700,
64    0x2244100408008080,
65    0x8000400801980,
66    0x2000810040200,
67    0x8010100228810400,
68    0x2000009044210200,
69    0x4080008040102101,
70    0x40002080411d01,
71    0x2005524060000901,
72    0x502001008400422,
73    0x489a000810200402,
74    0x1004400080a13,
75    0x4000011008020084,
76    0x26002114058042,
77];
78
79const BISHOP_MAGICS: [u64; 64] = [
80    0x89a1121896040240,
81    0x2004844802002010,
82    0x2068080051921000,
83    0x62880a0220200808,
84    0x4042004000000,
85    0x100822020200011,
86    0xc00444222012000a,
87    0x28808801216001,
88    0x400492088408100,
89    0x201c401040c0084,
90    0x840800910a0010,
91    0x82080240060,
92    0x2000840504006000,
93    0x30010c4108405004,
94    0x1008005410080802,
95    0x8144042209100900,
96    0x208081020014400,
97    0x4800201208ca00,
98    0xf18140408012008,
99    0x1004002802102001,
100    0x841000820080811,
101    0x40200200a42008,
102    0x800054042000,
103    0x88010400410c9000,
104    0x520040470104290,
105    0x1004040051500081,
106    0x2002081833080021,
107    0x400c00c010142,
108    0x941408200c002000,
109    0x658810000806011,
110    0x188071040440a00,
111    0x4800404002011c00,
112    0x104442040404200,
113    0x511080202091021,
114    0x4022401120400,
115    0x80c0040400080120,
116    0x8040010040820802,
117    0x480810700020090,
118    0x102008e00040242,
119    0x809005202050100,
120    0x8002024220104080,
121    0x431008804142000,
122    0x19001802081400,
123    0x200014208040080,
124    0x3308082008200100,
125    0x41010500040c020,
126    0x4012020c04210308,
127    0x208220a202004080,
128    0x111040120082000,
129    0x6803040141280a00,
130    0x2101004202410000,
131    0x8200000041108022,
132    0x21082088000,
133    0x2410204010040,
134    0x40100400809000,
135    0x822088220820214,
136    0x40808090012004,
137    0x910224040218c9,
138    0x402814422015008,
139    0x90014004842410,
140    0x1000042304105,
141    0x10008830412a00,
142    0x2520081090008908,
143    0x40102000a0a60140,
144];
145
146const ROOK_INDEX_BITS: [u32; 64] = [
147    12, 11, 11, 11, 11, 11, 11, 12, 11, 10, 10, 10, 10, 10, 10, 11, 11, 10, 10, 10, 10, 10, 10, 11,
148    11, 10, 10, 10, 10, 10, 10, 11, 11, 10, 10, 10, 10, 10, 10, 11, 11, 10, 10, 10, 10, 10, 10, 11,
149    11, 10, 10, 10, 10, 10, 10, 11, 12, 11, 11, 11, 11, 11, 11, 12,
150];
151
152const BISHOP_INDEX_BITS: [u32; 64] = [
153    6, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 5, 5, 5, 5, 7, 9, 9, 7, 5, 5,
154    5, 5, 7, 9, 9, 7, 5, 5, 5, 5, 7, 7, 7, 7, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 5, 5, 6,
155];
156
157pub(crate) const ROOK_MASKS: [Bitboard; 64] = [
158    Bitboard(0x000101010101017e),
159    Bitboard(0x000202020202027c),
160    Bitboard(0x000404040404047a),
161    Bitboard(0x0008080808080876),
162    Bitboard(0x001010101010106e),
163    Bitboard(0x002020202020205e),
164    Bitboard(0x004040404040403e),
165    Bitboard(0x008080808080807e),
166    Bitboard(0x0001010101017e00),
167    Bitboard(0x0002020202027c00),
168    Bitboard(0x0004040404047a00),
169    Bitboard(0x0008080808087600),
170    Bitboard(0x0010101010106e00),
171    Bitboard(0x0020202020205e00),
172    Bitboard(0x0040404040403e00),
173    Bitboard(0x0080808080807e00),
174    Bitboard(0x00010101017e0100),
175    Bitboard(0x00020202027c0200),
176    Bitboard(0x00040404047a0400),
177    Bitboard(0x0008080808760800),
178    Bitboard(0x00101010106e1000),
179    Bitboard(0x00202020205e2000),
180    Bitboard(0x00404040403e4000),
181    Bitboard(0x00808080807e8000),
182    Bitboard(0x000101017e010100),
183    Bitboard(0x000202027c020200),
184    Bitboard(0x000404047a040400),
185    Bitboard(0x0008080876080800),
186    Bitboard(0x001010106e101000),
187    Bitboard(0x002020205e202000),
188    Bitboard(0x004040403e404000),
189    Bitboard(0x008080807e808000),
190    Bitboard(0x0001017e01010100),
191    Bitboard(0x0002027c02020200),
192    Bitboard(0x0004047a04040400),
193    Bitboard(0x0008087608080800),
194    Bitboard(0x0010106e10101000),
195    Bitboard(0x0020205e20202000),
196    Bitboard(0x0040403e40404000),
197    Bitboard(0x0080807e80808000),
198    Bitboard(0x00017e0101010100),
199    Bitboard(0x00027c0202020200),
200    Bitboard(0x00047a0404040400),
201    Bitboard(0x0008760808080800),
202    Bitboard(0x00106e1010101000),
203    Bitboard(0x00205e2020202000),
204    Bitboard(0x00403e4040404000),
205    Bitboard(0x00807e8080808000),
206    Bitboard(0x007e010101010100),
207    Bitboard(0x007c020202020200),
208    Bitboard(0x007a040404040400),
209    Bitboard(0x0076080808080800),
210    Bitboard(0x006e101010101000),
211    Bitboard(0x005e202020202000),
212    Bitboard(0x003e404040404000),
213    Bitboard(0x007e808080808000),
214    Bitboard(0x7e01010101010100),
215    Bitboard(0x7c02020202020200),
216    Bitboard(0x7a04040404040400),
217    Bitboard(0x7608080808080800),
218    Bitboard(0x6e10101010101000),
219    Bitboard(0x5e20202020202000),
220    Bitboard(0x3e40404040404000),
221    Bitboard(0x7e80808080808000),
222];
223
224pub(crate) const BISHOP_MASKS: [Bitboard; 64] = [
225    Bitboard(0x0040201008040200),
226    Bitboard(0x0000402010080400),
227    Bitboard(0x0000004020100a00),
228    Bitboard(0x0000000040221400),
229    Bitboard(0x0000000002442800),
230    Bitboard(0x0000000204085000),
231    Bitboard(0x0000020408102000),
232    Bitboard(0x0002040810204000),
233    Bitboard(0x0020100804020000),
234    Bitboard(0x0040201008040000),
235    Bitboard(0x00004020100a0000),
236    Bitboard(0x0000004022140000),
237    Bitboard(0x0000000244280000),
238    Bitboard(0x0000020408500000),
239    Bitboard(0x0002040810200000),
240    Bitboard(0x0004081020400000),
241    Bitboard(0x0010080402000200),
242    Bitboard(0x0020100804000400),
243    Bitboard(0x004020100a000a00),
244    Bitboard(0x0000402214001400),
245    Bitboard(0x0000024428002800),
246    Bitboard(0x0002040850005000),
247    Bitboard(0x0004081020002000),
248    Bitboard(0x0008102040004000),
249    Bitboard(0x0008040200020400),
250    Bitboard(0x0010080400040800),
251    Bitboard(0x0020100a000a1000),
252    Bitboard(0x0040221400142200),
253    Bitboard(0x0002442800284400),
254    Bitboard(0x0004085000500800),
255    Bitboard(0x0008102000201000),
256    Bitboard(0x0010204000402000),
257    Bitboard(0x0004020002040800),
258    Bitboard(0x0008040004081000),
259    Bitboard(0x00100a000a102000),
260    Bitboard(0x0022140014224000),
261    Bitboard(0x0044280028440200),
262    Bitboard(0x0008500050080400),
263    Bitboard(0x0010200020100800),
264    Bitboard(0x0020400040201000),
265    Bitboard(0x0002000204081000),
266    Bitboard(0x0004000408102000),
267    Bitboard(0x000a000a10204000),
268    Bitboard(0x0014001422400000),
269    Bitboard(0x0028002844020000),
270    Bitboard(0x0050005008040200),
271    Bitboard(0x0020002010080400),
272    Bitboard(0x0040004020100800),
273    Bitboard(0x0000020408102000),
274    Bitboard(0x0000040810204000),
275    Bitboard(0x00000a1020400000),
276    Bitboard(0x0000142240000000),
277    Bitboard(0x0000284402000000),
278    Bitboard(0x0000500804020000),
279    Bitboard(0x0000201008040200),
280    Bitboard(0x0000402010080400),
281    Bitboard(0x0002040810204000),
282    Bitboard(0x0004081020400000),
283    Bitboard(0x000a102040000000),
284    Bitboard(0x0014224000000000),
285    Bitboard(0x0028440200000000),
286    Bitboard(0x0050080402000000),
287    Bitboard(0x0020100804020000),
288    Bitboard(0x0040201008040200),
289];
290
291const fn compute_offsets(index_bits: &[u32; 64]) -> [usize; 64] {
292    let mut offsets = [0usize; 64];
293    let mut total = 0usize;
294    let mut i = 0;
295    while i < 64 {
296        offsets[i] = total;
297        total += 1usize << index_bits[i];
298        i += 1;
299    }
300    offsets
301}
302
303const fn total_table_size(index_bits: &[u32; 64]) -> usize {
304    let mut total = 0usize;
305    let mut i = 0;
306    while i < 64 {
307        total += 1usize << index_bits[i];
308        i += 1;
309    }
310    total
311}
312
313const ROOK_OFFSETS: [usize; 64] = compute_offsets(&ROOK_INDEX_BITS);
314const BISHOP_OFFSETS: [usize; 64] = compute_offsets(&BISHOP_INDEX_BITS);
315const ROOK_TABLE_SIZE: usize = total_table_size(&ROOK_INDEX_BITS);
316const BISHOP_TABLE_SIZE: usize = total_table_size(&BISHOP_INDEX_BITS);
317
318pub(crate) const ROOK_DIRS: [(i8, i8); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
319pub(crate) const BISHOP_DIRS: [(i8, i8); 4] = [(1, 1), (1, -1), (-1, 1), (-1, -1)];
320
321/// Per-square constant data for a magic bitboard lookup.
322///
323/// Packed into 24 bytes (Bitboard + u64 + u32 + u32) to fit in one
324/// 64-byte cache line, with room for a second entry.
325#[derive(Debug, Clone, Copy)]
326pub(crate) struct MagicEntry {
327    pub mask: Bitboard,
328    pub magic: u64,
329    /// `64 - index_bits` — the right-shift amount for the magic index.
330    pub shift: u32,
331    /// Offset into the flat attack table for this square.
332    pub offset: u32,
333}
334
335/// Compute `ROOK_ENTRIES` at compile time from the raw parallel arrays.
336const fn compute_rook_entries() -> [MagicEntry; 64] {
337    let mut entries = [MagicEntry {
338        mask: Bitboard(0),
339        magic: 0,
340        shift: 0,
341        offset: 0,
342    }; 64];
343    let mut total: u32 = 0;
344    let mut i = 0;
345    while i < 64 {
346        entries[i] = MagicEntry {
347            mask: ROOK_MASKS[i],
348            magic: ROOK_MAGICS[i],
349            shift: 64 - ROOK_INDEX_BITS[i],
350            offset: total,
351        };
352        total += 1u32 << ROOK_INDEX_BITS[i];
353        i += 1;
354    }
355    entries
356}
357
358/// Compute `BISHOP_ENTRIES` at compile time from the raw parallel arrays.
359const fn compute_bishop_entries() -> [MagicEntry; 64] {
360    let mut entries = [MagicEntry {
361        mask: Bitboard(0),
362        magic: 0,
363        shift: 0,
364        offset: 0,
365    }; 64];
366    let mut total: u32 = 0;
367    let mut i = 0;
368    while i < 64 {
369        entries[i] = MagicEntry {
370            mask: BISHOP_MASKS[i],
371            magic: BISHOP_MAGICS[i],
372            shift: 64 - BISHOP_INDEX_BITS[i],
373            offset: total,
374        };
375        total += 1u32 << BISHOP_INDEX_BITS[i];
376        i += 1;
377    }
378    entries
379}
380
381pub(crate) const ROOK_ENTRIES: [MagicEntry; 64] = compute_rook_entries();
382pub(crate) const BISHOP_ENTRIES: [MagicEntry; 64] = compute_bishop_entries();
383
384/// Compute sliding-piece attacks by ray-casting in the given directions.
385///
386/// Walks along each direction from `sq` until hitting the edge of the board
387/// or an occupied square (inclusive). Used as the reference implementation
388/// for building magic and PEXT tables.
389pub(crate) fn sliding_attack(directions: &[(i8, i8)], sq: Square, occupied: Bitboard) -> Bitboard {
390    let mut result = 0u64;
391    let s_idx = sq as i8;
392    let sf = s_idx % 8;
393    let sr = s_idx / 8;
394
395    for &(df, dr) in directions {
396        let mut f = sf + df;
397        let mut r = sr + dr;
398        while (0..8).contains(&f) && (0..8).contains(&r) {
399            let idx = (r * 8 + f) as usize;
400            result |= 1u64 << idx;
401            if occupied.0 & (1u64 << idx) != 0 {
402                break;
403            }
404            f += df;
405            r += dr;
406        }
407    }
408    Bitboard(result)
409}
410
411/// Build a magic-bitboard attack table for a given piece type.
412///
413/// Enumerates all occupancy subsets of each square's mask, computes the
414/// reference attack via [`sliding_attack`], and stores the result at the
415/// magic-indexed position in the flat table.
416fn build_magic_table(
417    directions: &[(i8, i8)],
418    masks: &[Bitboard; 64],
419    magics: &[u64; 64],
420    index_bits: &[u32; 64],
421    offsets: &[usize; 64],
422    total_size: usize,
423) -> Box<[Bitboard]> {
424    let mut table = vec![Bitboard::EMPTY; total_size].into_boxed_slice();
425
426    for sq in 0..64 {
427        let mask = masks[sq].0;
428        let magic = magics[sq];
429        let shift = 64 - index_bits[sq];
430        let offset = offsets[sq];
431        let size_check = 1usize << index_bits[sq];
432        let sq_enum = Square::from_u8(sq as u8);
433
434        // Enumerate all subsets of the mask using the carry-rippler trick.
435        let mut subset = 0u64;
436        let mut count = 0usize;
437        loop {
438            let attacks = sliding_attack(directions, sq_enum, Bitboard(subset));
439            let idx = (subset.wrapping_mul(magic) >> shift) as usize;
440            debug_assert!(
441                idx < size_check,
442                "index {} out of bounds for square {}",
443                idx,
444                sq
445            );
446            table[offset + idx] = attacks;
447            count += 1;
448
449            // Carry-rippler: compute next subset
450            subset = subset.wrapping_sub(mask) & mask;
451            if subset == 0 {
452                break;
453            }
454        }
455
456        debug_assert_eq!(
457            count, size_check,
458            "wrong number of subsets for square {}",
459            sq
460        );
461    }
462
463    table
464}
465
466static ROOK_TABLE: OnceLock<&[Bitboard]> = OnceLock::new();
467static BISHOP_TABLE: OnceLock<&[Bitboard]> = OnceLock::new();
468
469/// Initialize the magic attack tables. Must be called before any lookup.
470pub(crate) fn init() {
471    _ = ROOK_TABLE.set(Box::leak(build_magic_table(
472        &ROOK_DIRS,
473        &ROOK_MASKS,
474        &ROOK_MAGICS,
475        &ROOK_INDEX_BITS,
476        &ROOK_OFFSETS,
477        ROOK_TABLE_SIZE,
478    )));
479    _ = BISHOP_TABLE.set(Box::leak(build_magic_table(
480        &BISHOP_DIRS,
481        &BISHOP_MASKS,
482        &BISHOP_MAGICS,
483        &BISHOP_INDEX_BITS,
484        &BISHOP_OFFSETS,
485        BISHOP_TABLE_SIZE,
486    )));
487}
488
489/// Return the attack set for a bishop on `sq` given the `occupied` board.
490#[inline(always)]
491pub fn bishop_attacks(sq: Square, occupied: Bitboard) -> Bitboard {
492    let table = BISHOP_TABLE
493        .get()
494        .expect("magic tables not initialized — call attacks::init()");
495    let e = &BISHOP_ENTRIES[sq as usize];
496    let idx = ((occupied & e.mask).0.wrapping_mul(e.magic)) >> e.shift;
497    table[e.offset as usize + idx as usize]
498}
499
500/// Return the attack set for a rook on `sq` given the `occupied` board.
501#[inline(always)]
502pub fn rook_attacks(sq: Square, occupied: Bitboard) -> Bitboard {
503    let table = ROOK_TABLE
504        .get()
505        .expect("magic tables not initialized — call attacks::init()");
506    let e = &ROOK_ENTRIES[sq as usize];
507    let idx = ((occupied & e.mask).0.wrapping_mul(e.magic)) >> e.shift;
508    table[e.offset as usize + idx as usize]
509}
510
511/// Return the attack set for a queen (bishop + rook).
512#[inline(always)]
513pub fn queen_attacks(sq: Square, occupied: Bitboard) -> Bitboard {
514    bishop_attacks(sq, occupied) | rook_attacks(sq, occupied)
515}
516
517#[cfg(test)]
518pub fn bishop_attacks_loop(sq: Square, occupied: Bitboard) -> Bitboard {
519    sliding_attack(&BISHOP_DIRS, sq, occupied)
520}
521
522#[cfg(test)]
523pub fn rook_attacks_loop(sq: Square, occupied: Bitboard) -> Bitboard {
524    sliding_attack(&ROOK_DIRS, sq, occupied)
525}
526
527#[cfg(test)]
528mod tests {
529    use super::*;
530
531    /// Verify that magic lookups match the loop-based reference for every
532    /// square and every possible occupancy pattern.
533    #[test]
534    fn test_magic_vs_loop_bishop() {
535        super::init();
536        for sq_idx in 0..64 {
537            let sq = Square::from_u8(sq_idx as u8);
538            let mask = BISHOP_MASKS[sq_idx];
539            let size = 1 << BISHOP_INDEX_BITS[sq_idx];
540            let mut count = 0;
541            let mut subset = 0u64;
542            loop {
543                let occ = Bitboard(subset);
544                let magic_atk = bishop_attacks(sq, occ);
545                let loop_atk = bishop_attacks_loop(sq, occ);
546                assert_eq!(
547                    magic_atk, loop_atk,
548                    "Bishop mismatch at sq={:?}, occ=0x{:x}",
549                    sq, subset
550                );
551                count += 1;
552                subset = subset.wrapping_sub(mask.0) & mask.0;
553                if subset == 0 {
554                    break;
555                }
556            }
557            assert_eq!(count, size, "Bishop count mismatch at sq={:?}", sq);
558        }
559    }
560
561    #[test]
562    fn test_magic_vs_loop_rook() {
563        super::init();
564        for sq_idx in 0..64 {
565            let sq = Square::from_u8(sq_idx as u8);
566            let mask = ROOK_MASKS[sq_idx];
567            let size = 1 << ROOK_INDEX_BITS[sq_idx];
568            let mut count = 0;
569            let mut subset = 0u64;
570            loop {
571                let occ = Bitboard(subset);
572                let magic_atk = rook_attacks(sq, occ);
573                let loop_atk = rook_attacks_loop(sq, occ);
574                assert_eq!(
575                    magic_atk, loop_atk,
576                    "Rook mismatch at sq={:?}, occ=0x{:x}",
577                    sq, subset
578                );
579                count += 1;
580                subset = subset.wrapping_sub(mask.0) & mask.0;
581                if subset == 0 {
582                    break;
583                }
584            }
585            assert_eq!(count, size, "Rook count mismatch at sq={:?}", sq);
586        }
587    }
588}
atomic_movegen/magic.rs

atomic_movegen/
magic.rs
