Protector Code

/*
    Protector -- a UCI chess engine

    Copyright (C) 2008 Raimund Heid (Raimund_Heid@yahoo.com)

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#ifndef _bitboard_h_
#define _bitboard_h_

#include "protector.h"
#include <string.h>

#ifdef TARGET_WINDOWS
#include <intrin.h>
#endif

typedef UINT64 Bitboard;

#define EMPTY_BITBOARD ULONG_ZERO
#define IMAX_ROOK    4096
#define IMAX_BISHOP  512

typedef struct
{
   int hLane, vLane, uLane, dLane;
   BYTE hLaneSetMask, vLaneSetMask, uLaneSetMask, dLaneSetMask;
   BYTE hLaneClearMask, vLaneClearMask, uLaneClearMask, dLaneClearMask;
}
SquareLaneInfo;

typedef struct
{
   int numSetSquares;
   UINT8 setSquares[16];
}
SetSquaresInfo;

typedef struct
{
   int hLaneNumber, vLaneNumber, uLaneNumber, dLaneNumber;
   Bitboard hLane[256], vLane[256], uLane[256], dLane[256];
}
ObstacleSquareInfo;

typedef struct
{
   Bitboard preMask, magicNumber;
   Bitboard moves[IMAX_ROOK];
}
MagicSquareInfoRook;

typedef struct
{
   Bitboard preMask, magicNumber;
   Bitboard moves[IMAX_BISHOP];
}
MagicSquareInfoBishop;

#define SLI(square) (squareLaneInfo[(square)])

extern UINT64 minValue[_64_];
extern UINT64 maxValue[_64_];
extern INT8 highestBit[0x10000];
extern Bitboard hlane[_64_][256];
extern Bitboard vlane[_64_][256];
extern Bitboard ulane[_64_][256];
extern Bitboard dlane[_64_][256];
extern ObstacleSquareInfo obsi[_64_];
extern Bitboard castlings[2][16][256];
extern int castlingLane[2];
extern int castlingsOfColor[2];
extern SquareLaneInfo squareLaneInfo[_64_];
extern Bitboard generalMoves[0x0f][_64_];
extern Bitboard squaresOfFile[8];
extern Bitboard squaresOfRank[8];
extern Bitboard squaresOfLateralFiles[8];
extern Bitboard squaresOfFileRange[8][8];
extern Bitboard squaresOfRankRange[8][8];
extern Bitboard pawnMoves[2][_64_][256];
extern Bitboard promotionCandidates[2];
extern SetSquaresInfo setSquares[4][0x10000];
extern INT8 numSetBits[0x10000];
extern UINT8 rankOverlay[0x10000];
extern UINT8 bitshiftGap[8][256];
extern Bitboard squaresBehind[_64_][_64_];
extern Bitboard squaresBetween[_64_][_64_];
extern Bitboard squaresInDistance[8][_64_];
extern Bitboard squaresInTaxiDistance[15][_64_];
extern Bitboard squaresAbove[2][_64_];
extern Bitboard squaresBelow[2][_64_];
extern Bitboard orthoKingAttackers[_64_];
extern Bitboard diaKingAttackers[_64_];
extern Bitboard knightKingAttackers[_64_];
extern Bitboard pawnKingAttackers[2][_64_];
extern Bitboard interestedPawns[2][_64_][256];
extern Bitboard nonA, nonH, border, center, lightSquares, darkSquares,
   queenSide, kingSide, centerFiles, extendedCenter;
extern int hLaneNumber[_64_], vLaneNumber[_64_];
extern int uLaneNumber[_64_], dLaneNumber[_64_];
extern Bitboard preMaskRook[64], preMaskBishop[64];
extern Bitboard magicRookMoves[64][IMAX_ROOK];
extern Bitboard magicBishopMoves[64][IMAX_BISHOP];
extern const Bitboard magicRookNumber[64];
extern const Bitboard magicBishopNumber[64];
extern MagicSquareInfoRook magicSquareInfoRook[64];
extern MagicSquareInfoBishop magicSquareInfoBishop[64];

#define setSquare(bitboard,square) ((bitboard) |= minValue[(square)]);
#define clearSquare(bitboard,square) ((bitboard) &= maxValue[(square)]);
#define excludeSquares(bitboard,toBeExcluded) ((bitboard) &= ~(toBeExcluded))

INLINE bool testSquare(const Bitboard bitboard, const Square square)
{
   return (bool) (((bitboard) & minValue[(square)]) != EMPTY_BITBOARD);
}

/**
 * Get the king moves for the specified square.
 */
INLINE Bitboard getKingMoves(const Square square)
{
   return generalMoves[KING][square];
}

/**
 * Get castling moves depending from the castling rights and 
 * the current position.
 */
INLINE Bitboard getCastlingMoves(const Color color, const BYTE castlingRights,
                                 const Bitboard obstacles)
{
   if (color == WHITE)
   {
      return castlings[WHITE][castlingRights][obstacles & 0xFF];
   }
   else
   {
      return castlings[BLACK][castlingRights][obstacles >> 56];
   }
}

/**
 * Get the queen moves for the specified square.
 */
/*
INLINE Bitboard getQueenMoves(const Square square, const BYTE * obstacles)
{
   const ObstacleSquareInfo *_obsi = &obsi[square];

   return _obsi->hLane[obstacles[_obsi->hLaneNumber]] |
      _obsi->vLane[obstacles[_obsi->vLaneNumber]] |
      _obsi->uLane[obstacles[_obsi->uLaneNumber]] |
      _obsi->dLane[obstacles[_obsi->dLaneNumber]];
}
*/

INLINE int getWidth(const Bitboard set)
{
   if (set == EMPTY_BITBOARD)
   {
      return 0;
   }
   else
   {
      File leftMost = FILE_A, rightMost = FILE_H;

      while ((set & squaresOfFile[leftMost]) == EMPTY_BITBOARD)
      {
         leftMost++;
      }

      while ((set & squaresOfFile[rightMost]) == EMPTY_BITBOARD)
      {
         rightMost--;
      }

      return rightMost - leftMost;
   }
}

/**
 * Get the queen moves for the specified square.
 */
INLINE Bitboard getMagicQueenMoves(const Square square,
                                   const Bitboard obstacles)
{
   MagicSquareInfoRook *msir = &magicSquareInfoRook[square];
   MagicSquareInfoBishop *msib = &magicSquareInfoBishop[square];

   return
      msir->moves[((obstacles & msir->preMask) * msir->magicNumber) >> 52] |
      msib->moves[((obstacles & msib->preMask) * msib->magicNumber) >> 55];
}

/**
 * Get the rook moves for the specified square.
 */
INLINE Bitboard getRookMoves(const Square square, const BYTE * obstacles)
{
   const ObstacleSquareInfo *_obsi = &obsi[square];

   return _obsi->hLane[obstacles[_obsi->hLaneNumber]] |
      _obsi->vLane[obstacles[_obsi->vLaneNumber]];
}

/**
 * Get the rook moves for the specified square.
 */
INLINE Bitboard getMagicRookMoves(const Square square,
                                  const Bitboard obstacles)
{
   MagicSquareInfoRook *msir = &magicSquareInfoRook[square];

   return
      msir->moves[((obstacles & msir->preMask) * msir->magicNumber) >> 52];
}

/**
 * Get the bishop moves for the specified square.
 */
INLINE Bitboard getBishopMoves(const Square square, const BYTE * obstacles)
{
   const ObstacleSquareInfo *_obsi = &obsi[square];

   return _obsi->uLane[obstacles[_obsi->uLaneNumber]] |
      _obsi->dLane[obstacles[_obsi->dLaneNumber]];
}

/**
 * Get the bishop moves for the specified square.
 */
INLINE Bitboard getMagicBishopMoves(const Square square,
                                    const Bitboard obstacles)
{
   MagicSquareInfoBishop *msib = &magicSquareInfoBishop[square];

   return
      msib->moves[((obstacles & msib->preMask) * msib->magicNumber) >> 55];
}

/**
 * Get the knight moves for the specified square.
 */
INLINE Bitboard getKnightMoves(const Square square)
{
   return generalMoves[KNIGHT][square];
}

/**
 * Get the pawn captures for the specified square.
 */
INLINE Bitboard getPawnCaptures(const Piece piece, const Square square,
                                const Bitboard allPieces)
{
   return generalMoves[piece][square] & allPieces;
}

/**
 * Get the pawn advances for the specified square.
 */
INLINE Bitboard getPawnAdvances(const Color color, const Square square,
                                const Bitboard obstacles)
{
   Bitboard advances;

   if (color == WHITE)
   {
      advances = (minValue[square] << 8) & ~obstacles;

      if (rank(square) == RANK_2)
      {
         advances |= (advances << 8) & ~obstacles;
      }
   }
   else
   {
      advances = (minValue[square] >> 8) & ~obstacles;

      if (rank(square) == RANK_7)
      {
         advances |= (advances >> 8) & ~obstacles;
      }
   }

   return advances;
}

/**
 * Get the pawns interested in advancing to the specified square.
 */
INLINE Bitboard getInterestedPawns(const Color color, const Square square,
                                   const Bitboard obstacles)
{
   Bitboard interestedPawns;

   if (color == WHITE)
   {
      interestedPawns = minValue[square] >> 8;

      if (rank(square) == RANK_4 &&
          (interestedPawns & obstacles) == EMPTY_BITBOARD)
      {
         interestedPawns = minValue[square] >> 16;
      }
   }
   else
   {
      interestedPawns = minValue[square] << 8;

      if (rank(square) == RANK_5 &&
          (interestedPawns & obstacles) == EMPTY_BITBOARD)
      {
         interestedPawns = minValue[square] << 16;
      }
   }

   return interestedPawns;
}

/**
 * Get the squares between the two specified squares.
 */
INLINE Bitboard getSquaresBetween(const Square square1, const Square square2)
{
   return squaresBetween[square1][square2];
}

/**
 * Get the squares behind 'target', as seen from 'viewpoint'.
 */
INLINE Bitboard getSquaresBehind(const Square target, const Square viewpoint)
{
   return squaresBehind[target][viewpoint];
}

/**
 * Shift all set squares one file to the left.
 */
INLINE Bitboard shiftLeft(const Bitboard bitboard)
{
   return (bitboard & nonA) >> 1;
}

/**
 * Shift all set squares one file to the right.
 */
INLINE Bitboard shiftRight(const Bitboard bitboard)
{
   return (bitboard & nonH) << 1;
}

/**
 * Get all squares lateral to the specified squares.
 */
INLINE Bitboard getLateralSquares(const Bitboard squares)
{
   return ((squares & nonA) >> 1) | ((squares & nonH) << 1);
}

/**
 * Get the squares of the specified file.
 */
INLINE Bitboard getSquaresOfFile(const File file)
{
   return squaresOfFile[file];
}

/**
 * Get the squares of the specified rank.
 */
INLINE Bitboard getSquaresOfRank(const Rank rank)
{
   return squaresOfRank[rank];
}

#ifdef TARGET_WINDOWS
#define UHEX_FFFF 0xFFFFui64
#endif
#ifdef TARGET_LINUX
#define UHEX_FFFF 0xFFFFllu
#endif

/**
 * Get the number of set squares in the specified bitboard.
 */
INLINE int getNumberOfSetSquares(const Bitboard bitboard)
{
   return numSetBits[bitboard & UHEX_FFFF] +
      numSetBits[(bitboard >> 16) & UHEX_FFFF] +
      numSetBits[(bitboard >> 32) & UHEX_FFFF] +
      numSetBits[(bitboard >> 48) & UHEX_FFFF];
}

/**
 * Get the rank overlay of the specified bitboard.
 */
INLINE int getRankOverlay(const Bitboard bitboard)
{
   return rankOverlay[(bitboard) & UHEX_FFFF] |
      rankOverlay[(bitboard >> 16) & UHEX_FFFF] |
      rankOverlay[(bitboard >> 32) & UHEX_FFFF] |
      rankOverlay[(bitboard >> 48) & UHEX_FFFF];
}

/**
 * The number of lanes used to hold information
 * about the state of all files, rows and diagonals
 */
#define NUM_LANES 46

/**
 * Get the moves of the the specified piece.
 */
INLINE Bitboard getMoves(Square square, Piece piece, Bitboard allPieces)
{
   switch (pieceType(piece))
   {
   case PAWN:
      return getPawnCaptures(piece, square, allPieces) |
         getPawnAdvances(pieceColor(piece), square, allPieces);
   case KING:
      return getKingMoves(square);
   case KNIGHT:
      return getKnightMoves(square);
   case ROOK:
      return getMagicRookMoves(square, allPieces);
   case BISHOP:
      return getMagicBishopMoves(square, allPieces);
   default:
      return getMagicQueenMoves(square, allPieces);
   }
}

/**
 * Set a square in the specified vector of obstacles.
 */
INLINE void setObstacleSquare(Square square, BYTE obstacles[NUM_LANES])
{
   SquareLaneInfo *sqi = &squareLaneInfo[square];

   obstacles[sqi->hLane] |= sqi->hLaneSetMask;
   obstacles[sqi->vLane] |= sqi->vLaneSetMask;
   obstacles[sqi->uLane] |= sqi->uLaneSetMask;
   obstacles[sqi->dLane] |= sqi->dLaneSetMask;
}

/**
 * Clear a square in the specified vector of obstacles.
 */
INLINE void clearObstacleSquare(Square square, BYTE obstacles[NUM_LANES])
{
   SquareLaneInfo *sqi = &squareLaneInfo[square];

   obstacles[sqi->hLane] &= sqi->hLaneClearMask;
   obstacles[sqi->vLane] &= sqi->vLaneClearMask;
   obstacles[sqi->uLane] &= sqi->uLaneClearMask;
   obstacles[sqi->dLane] &= sqi->dLaneClearMask;
}

/**
 * Calculate all obstacles according to the specified bitboard.
 */
INLINE void calculateObstacles(Bitboard board, BYTE obstacles[NUM_LANES])
{
   Square square;

   memset(obstacles, 0x00, NUM_LANES);

   ITERATE(square)
   {
      if (board & minValue[square])
      {
         setObstacleSquare(square, obstacles);
      }
   }
}

/**
 * Initialize this module.
 *
 * @return 0 if no errors occurred.
 */
int initializeModuleBitboard(void);

/**
 * Test this module.
 *
 * @return 0 if all tests succeed.
 */
int testModuleBitboard(void);

/**
 * Get the number of a set square and clear the corresponding bit.
 *
 * @return NO_SQUARE if no square was set.
 */
INLINE Square getNextSquare(Bitboard * vector);

/**
 * Extend all set bits by one square into all directions.
 */
INLINE void floodBoard(Bitboard * board);

/**
 * Get the targets of all pawns specified by 'whitePawns'.
 */
INLINE Bitboard getWhitePawnTargets(const Bitboard whitePawns)
{
   return ((whitePawns & nonA) << 7) | ((whitePawns & nonH) << 9);
}

/**
 * Get the targets of all pawns specified by 'blackPawns'.
 */
INLINE Bitboard getBlackPawnTargets(const Bitboard blackPawns)
{
   return ((blackPawns & nonA) >> 9) | ((blackPawns & nonH) >> 7);
}

/**
 * Iteration shortcuts
 */
#define ITERATE_BITBOARD(b,sq) while ( ( sq = getNextSquare(b) ) >= 0 )

INLINE void floodBoard(Bitboard * board)
{
   const Bitboard toLeft = *board & nonA, toRight = *board & nonH;

   *board = (toLeft >> 1) | (toLeft << 7) | (*board >> 8) | (toLeft >> 9) |
      (toRight << 1) | (toRight >> 7) | (*board << 8) | (toRight << 9);
}

#ifdef TARGET_WINDOWS
#define UHEX_FFFFffff00000000 0xFFFFffff00000000ui64
#define UHEX_00000000FFFF0000 0x00000000FFFF0000ui64
#define UHEX_FFFF000000000000 0xFFFF000000000000ui64
#define UHEX_00000000FFFFffff 0x00000000FFFFffffui64
#endif
#ifdef TARGET_LINUX
#define UHEX_FFFFffff00000000 0xFFFFffff00000000llu
#define UHEX_00000000FFFF0000 0x00000000FFFF0000llu
#define UHEX_FFFF000000000000 0xFFFF000000000000llu
#define UHEX_00000000FFFFffff 0x00000000FFFFffffllu
#endif

#ifdef WIN64
INLINE Square getNextSquare(Bitboard * vector)
{
   unsigned long index;

   if (_BitScanReverse64(&index, *vector))
   {
      _bittestandreset64((__int64 *) vector, index);

      return (Square) index;
   }
   else
   {
      return NO_SQUARE;
   }
}
#else
#if !defined NDEBUG || defined TARGET_LINUX
INLINE Square getNextSquare(Bitboard * vector)
{
   Square nextSquare;

   if ((*vector & UHEX_FFFFffff00000000) == ULONG_ZERO)
   {
      if ((*vector & UHEX_00000000FFFF0000) == ULONG_ZERO)
      {
         if ((nextSquare = (Square) highestBit[(int) *vector]) >= 0)
         {
            *vector &= maxValue[nextSquare];
         }

         return nextSquare;
      }
      else
      {
         nextSquare = (Square) (highestBit[(int) (*vector >> 16)] + 16);
         *vector &= maxValue[nextSquare];

         return nextSquare;
      }
   }
   else
   {
      if ((*vector & UHEX_FFFF000000000000) == ULONG_ZERO)
      {
         nextSquare = (Square) (highestBit[(int) (*vector >> 32)] + 32);
         *vector &= maxValue[nextSquare];

         return nextSquare;
      }
      else
      {
         nextSquare = (Square) (highestBit[(int) (*vector >> 48)] + 48);
         *vector &= maxValue[nextSquare];

         return nextSquare;
      }
   }
}
#else
INLINE Square getNextSquare(Bitboard * vector)
{
   unsigned long index;

   if (*vector > UHEX_00000000FFFFffff)
   {
      unsigned long *uw = ((unsigned long *) (vector)) + 1;

      _BitScanReverse(&index, *uw);
      _bittestandreset((long *) uw, index);

      return (Square) index + 32;
   }
   else
   {
      if (_BitScanReverse(&index, (unsigned long) *vector))
      {
         _bittestandreset((long *) vector, index);

         return (Square) index;
      }
      else
      {
         return NO_SQUARE;
      }
   }
}
#endif
#endif

INLINE int getSetSquares(const Bitboard board, UINT8 squares[_64_])
{
   int index;
   UINT8 *currentSquare = &squares[0];

   if ((index = (int) (0xFFFF & board)) != 0)
   {
      const SetSquaresInfo *info = &setSquares[0][index];

      memcpy(currentSquare, info->setSquares, info->numSetSquares);
      currentSquare += info->numSetSquares;
   }

   if ((index = (int) (0xFFFF & (board >> 16))) != 0)
   {
      const SetSquaresInfo *info = &setSquares[1][index];

      memcpy(currentSquare, info->setSquares, info->numSetSquares);
      currentSquare += info->numSetSquares;
   }

   if ((index = (int) (0xFFFF & (board >> 32))) != 0)
   {
      const SetSquaresInfo *info = &setSquares[2][index];

      memcpy(currentSquare, info->setSquares, info->numSetSquares);
      currentSquare += info->numSetSquares;
   }

   if ((index = (int) (board >> 48)) != 0)
   {
      const SetSquaresInfo *info = &setSquares[3][index];

      memcpy(currentSquare, info->setSquares, info->numSetSquares);
      currentSquare += info->numSetSquares;
   }

   return (int) (currentSquare - &squares[0]);
}

INLINE Bitboard getMultipleSquaresBetween(const Square origin,
                                          Bitboard targets)
{
   Bitboard squares = targets;
   Square targetSquare;
   Bitboard *sqb = &(squaresBetween[origin][0]);

   ITERATE_BITBOARD(&targets, targetSquare)
   {
      squares |= sqb[targetSquare];
   }

   return squares;
}

unsigned int getMinimumDistance(const Bitboard targets, const Square square);
unsigned int getMaximumDistance(const Bitboard targets, const Square square);
int getFloodValue(const Square origin, const Bitboard targets,
                  const Bitboard permittedSquares);

#endif