Chess position representation with FEN parser

Question

I'm developing a UCI chess engine and as part of my engine I need a position representation that stores the position of every piece on the board and all the information about the game, like castling rights, en passant square, etc. The standard way of representing a chess position in a human readable format is the Forsyth–Edwards Notation (FEN), which is also used in the UCI protocol and takes the following form:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

The first part is the piece placement, following by the side to move, castling rights (if any), en passant square (if any), halfmove clock, and finally the fullmove counter. Here is the FEN grammar according to the Chess Programming Wiki:

<FEN> ::=  <Piece Placement>
       ' ' <Side to move>
       ' ' <Castling ability>
       ' ' <En passant target square>
       ' ' <Halfmove clock>
       ' ' <Fullmove counter>

<Piece Placement> ::= <rank8>'/'<rank7>'/'<rank6>'/'<rank5>'/'<rank4>'/'<rank3>'/'<rank2>'/'<rank1>
<ranki>       ::= [<digit17>]<piece> {[<digit17>]<piece>} [<digit17>] | '8'
<piece>       ::= <white Piece> | <black Piece>
<digit17>     ::= '1' | '2' | '3' | '4' | '5' | '6' | '7'
<white Piece> ::= 'P' | 'N' | 'B' | 'R' | 'Q' | 'K'
<black Piece> ::= 'p' | 'n' | 'b' | 'r' | 'q' | 'k'

<Side to move> ::= {'w' | 'b'}

<Castling ability> ::= '-' | ['K'] ['Q'] ['k'] ['q'] (1..4)

<En passant target square> ::= '-' | <epsquare>
<epsquare>   ::= <fileLetter> <eprank>
<fileLetter> ::= 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h'
<eprank>     ::= '3' | '6'

<Halfmove Clock> ::= <digit> {<digit>}
<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

<Fullmove counter> ::= <digit19> {<digit>}
<digit19> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<digit>   ::= '0' | <digit19>

Also, since this is part of a chess engine, the position representation must be small for cache performance, and the operations like moving pieces, getting castling rights, etc, must be fast because the position is modified in a recursive function that searches for the best next move.

Here's the code for pos.c:

#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <check.h>

#include "pos.h"

/*
 * The piece placement is stored in two formats, in piece-centric bitboard
 * arrays and in a square-centric array.
 * 
 * In the piece-centric format there are two arrays, one indexed by the color
 * and one indexed by the piece type, both storing bitboards where the set bits
 * represent a piece of that color or type at a square, where the square is
 * counted from the least significant bit to the most significant bit, from 0
 * to 63. The bitboards store pieces using a Little-Endian Rank-File mapping
 * (LERF), which means each byte, from the least significant byte to the most
 * significant byte represent a rank, and each bit of these bytes represent a
 * square on that rank. Which means that A1 is square 0, H1 is square 7, A2 is
 * square 8, H2 is square 15 and so on.
 * 
 * The square-centric format is just a flat array indexed by the square number
 * in a LERF mapping and each element of the array is a piece, or PIECE_NONE if
 * the square is empty.
 * 
 * The castling rights are stored in a nibble, the 2 least significant bits are
 * for white and the next 2 bits for black, the least significant and most
 * significant bits of each are for the queen and king sides respectively. A
 * set bit means that the king has the right to castle. Notice that having
 * right to castle does not mean that castling really is possible
 * (castling ability), it only means that neither the king nor the rook
 * corresponding to the castling side have moved throughout the game. In order
 * for castling to be possible, the following conditions must be met:
 * - The side must have castling rights;
 * - There are no pieces between the king and rook;
 * - The king will not be in check after castling.
 * 
 * The en passant square is not stored, but instead only its file. This is to
 * save space, since it is possible to recover the square by using the color of
 * the side to move. Because there are only 8 files the file is stored in just
 * the 3 least significant bits of a nibble and the most significant bit of the
 * nibble is set when there is an en passant square and unset otherwise. Since
 * both the castling rights and en passant file are stored in a nibble, I
 * stored both together in one byte.
 * 
 * Because changes to some of the position data can't be undone, like the
 * castling ability (if the rook moves back and forth there's no way to know
 * that it happened later on), all this irreversibe state is stored in a stack
 * where the top is the current state and to undo a move one only has to pop
 * the last irreversible state off the stack and undo the changes to the
 * reversibe data.
 */

struct irreversible_state {
    u8 castling_rights_and_enpassant;
    u8 halfmove_clock;
    u8 captured_piece;
    struct irreversible_state *previous;
};

struct position {
    struct irreversible_state *irreversible;
    u8 side_to_move;
    short fullmove_counter;
    u64 color_bb[2];
    u64 type_bb[6];
    Piece board[64];
};

static size_t parse_fen(Position *pos, const char *fen);
static size_t parse_fullmove_counter(Position *pos, const char *str);
static size_t parse_halfmove_clock(Position *pos, const char *str);
static size_t parse_enpassant(Position *pos, const char *str);
static size_t parse_castling(Position *pos, const char *str);
static size_t parse_side(Position *pos, const char *str);
static size_t parse_pieces(Position *pos, const char *str);
static int is_one_of(const char *str, char ch);
static char *trim(char *str);
static int get_index_of_first_bit(u64 n);
static int count_bits(u64 n);

int
main(int argc, char **argv)
{
    if (argc > 1) {
        if (!strlen(argv[1])) {
            fprintf(stderr, "FEN not provided.\n");
            return EXIT_FAILURE;
        }
        Position *pos = pos_create(trim(argv[1]));
        if (!pos) {
            fprintf(stderr, "Invalid FEN.\n");
            return EXIT_FAILURE;
        }
        pos_print(pos);
        pos_destroy(pos);
    } else {
        fprintf(stderr, "FEN not provided.\n");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

void pos_print(const Position *pos)
{
    const char piece_table[] = {
        [PIECE_TYPE_PAWN ] = 'p', [PIECE_TYPE_KNIGHT] = 'n',
        [PIECE_TYPE_ROOK ] = 'r', [PIECE_TYPE_BISHOP] = 'b',
        [PIECE_TYPE_QUEEN] = 'q', [PIECE_TYPE_KING  ] = 'k',
    };

    Rank rank = RANK_8;
    File file = FILE_A;
    for (rank = RANK_8, file = FILE_A; file <= FILE_H || rank > RANK_1;) {
        if (file > FILE_H) {
            --rank;
            file = FILE_A;
            putchar('\n');
        }

        Square sq = pos_file_rank_to_square(file, rank);
        Piece piece = pos_get_piece_at(pos, sq);
        char ch = '\0';
        if (piece == PIECE_NONE) {
            ch = '0';
        } else {
            PieceType piece_type = pos_get_piece_type(piece);
            Color color = pos_get_piece_color(piece);
            ch = piece_table[piece_type];
            if (color == COLOR_WHITE)
                ch = toupper(ch);
        }
        printf("%c ", ch);
        ++file;
    }
    printf("\n\n");

    Color color = pos_get_side_to_move(pos);
    if (color == COLOR_WHITE)
        printf("Turn: white\n");
    else
        printf("Turn: black\n");

    printf("En passant: ");
    if (pos_enpassant_possible(pos)) {
        Square sq = pos_get_enpassant(pos);
        file = pos_get_file_of_square(sq);
        rank = pos_get_rank_of_square(sq);
        printf("%c%d\n", file + 'A', rank + 1);
    } else {
        printf("-\n");
    }

    printf("Castling rights: ");
    if (pos_has_castling_right(pos, COLOR_WHITE, CASTLING_SIDE_KING))
        putchar('K');
    if (pos_has_castling_right(pos, COLOR_WHITE, CASTLING_SIDE_QUEEN))
        putchar('Q');
    if (pos_has_castling_right(pos, COLOR_BLACK, CASTLING_SIDE_KING))
        putchar('k');
    if (pos_has_castling_right(pos, COLOR_BLACK, CASTLING_SIDE_QUEEN))
        putchar('q');
    printf("\n");

    printf("Halfmove clock: %d\n", pos_get_halfmove_clock(pos));
    printf("Fullmove counter: %d\n", pos_get_fullmove_counter(pos));
}

void pos_decrement_fullmove_counter(Position *pos)
{
    --pos->fullmove_counter;
}

void pos_increment_fullmove_counter(Position *pos)
{
    ++pos->fullmove_counter;
}

void pos_remove_castling(Position *pos, Color c, CastlingSide side)
{
    pos->irreversible->castling_rights_and_enpassant &= ~(1 << side <<
                                                          2 * c);
}

void pos_add_castling(Position *pos, Color c, CastlingSide side)
{
    pos->irreversible->castling_rights_and_enpassant |= 1 << side <<
                                                        2 * c;
}

void pos_flip_side_to_move(Position *pos)
{
    if (pos->side_to_move == COLOR_WHITE)
        pos->side_to_move = COLOR_BLACK;
    else
        pos->side_to_move = COLOR_WHITE;
}

void pos_set_captured_piece(Position *pos, Piece piece)
{
    pos->irreversible->captured_piece = piece;
}

/*
 * Remove a piece from a square.
 */
void pos_remove_piece(Position *pos, Square sq)
{
    const Piece piece = pos_get_piece_at(pos, sq);
    const u64 bb = U64(0x1) << sq;
    pos->color_bb[pos_get_piece_color(piece)] &= ~bb;
    pos->type_bb[pos_get_piece_type(piece)]  &= ~bb;
    pos->board[sq] = PIECE_NONE;
}

/*
 * Place a piece at a square, if another piece is at this square, it will be
 * removed first.
 * 
 * There's an important detail about this function. The bitboards are stored in
 * a piece centric format, so we can't just overwrite the old piece with the
 * new one if the pieces are of different types, the bitboard of the piece
 * being replaced would still store the piece as if it's still on the board,
 * because only the new piece's board would be modified. Because of that, the
 * old piece must be removed first with the pos_remove_piece function by the
 * caller. The reason why this is not done here is to avoid slowing down code
 * that places a piece in an empty square.
 */
void pos_place_piece(Position *pos, Square sq, Piece piece)
{
    const u64 bb = U64(0x1) << sq;
    if (pos->board[sq] != PIECE_NONE)
        pos_remove_piece(pos, sq);
    pos->color_bb[pos_get_piece_color(piece)] |= bb;
    pos->type_bb[pos_get_piece_type(piece)]  |= bb;
    pos->board[sq] = piece;
}

void pos_reset_halfmove_clock(Position *pos)
{
    pos->irreversible->halfmove_clock = 0;
}

void pos_increment_halfmove_clock(Position *pos)
{
    ++pos->irreversible->halfmove_clock;
}

void pos_unset_enpassant(Position *pos)
{
    pos->irreversible->castling_rights_and_enpassant &= 0xf;
}

/*
 * Set the possibility of en passant and store the file.
 */
void pos_set_enpassant(Position *pos, File file)
{
    pos->irreversible->castling_rights_and_enpassant &= 0x8f;
    pos->irreversible->castling_rights_and_enpassant |= 0x80;
    pos->irreversible->castling_rights_and_enpassant |= (file & 0x7) << 4;
}

Piece pos_get_captured_piece(const Position *pos)
{
    return pos->irreversible->captured_piece;
}

int pos_has_castling_right(const Position *pos, Color c, CastlingSide side)
{
    return (pos->irreversible->castling_rights_and_enpassant &
            0x1 << side << 2 * c) != 0;
}

int pos_get_fullmove_counter(const Position *pos)
{
    return pos->fullmove_counter;
}

int pos_get_halfmove_clock(const Position *pos)
{
    return pos->irreversible->halfmove_clock;
}

int pos_enpassant_possible(const Position *pos)
{
    return pos->irreversible->castling_rights_and_enpassant & 0x80;
}

Square pos_get_enpassant(const Position *pos)
{
    const File f = (pos->irreversible->castling_rights_and_enpassant
                    & 0x70) >> 4;
    const Rank r = pos->side_to_move == COLOR_WHITE ? RANK_6 : RANK_3;
    return pos_file_rank_to_square(f, r);
}

Color pos_get_side_to_move(const Position *pos)
{
    return pos->side_to_move;
}

Square pos_get_king_square(const Position *pos, Color c)
{
    const Piece piece = pos_make_piece(PIECE_TYPE_KING, c);
    const u64 bb = pos_get_piece_bitboard(pos, piece);
    return get_index_of_first_bit(bb);
}

Piece pos_get_piece_at(const Position *pos, Square sq)
{
    return pos->board[sq];
}

int pos_get_number_of_pieces(const Position *pos, Piece piece)
{
    const u64 bb = pos_get_piece_bitboard(pos, piece);

    return count_bits(bb);
}

u64 pos_get_piece_bitboard(const Position *pos, Piece piece)
{
    const PieceType type = pos_get_piece_type(piece);
    const Color color = pos_get_piece_color(piece);
    const u64 bb = pos->type_bb[type] & pos->color_bb[color];
    return bb;
}

u64 pos_get_color_bitboard(const Position *pos, Color c)
{
    return pos->color_bb[c];
}

void pos_backtrack_irreversible_state(Position *pos)
{
    struct irreversible_state *const current = pos->irreversible;
    pos->irreversible = pos->irreversible->previous;
    free(current);
}

/*
 * This function must be called before externally calling any function that
 * modifies the irreversible state of the position.
 *
 * It creates a new copy of the old irreversible state and pushes
 * it onto the stack, making it the current one. The reversible state is
 * preserved since changes can be undone.
 */
void pos_start_new_irreversible_state(Position *pos)
{
    struct irreversible_state *current = pos->irreversible;
    struct irreversible_state *new = malloc(sizeof(*new));
    if (!new) {
        fprintf(stderr, "Could not allocate memory.\n");
        exit(1);
    }
    memcpy(new, current, sizeof(struct irreversible_state));
    new->previous = current;
    pos->irreversible = new;
}

/*
 * Create a new position using FEN. It returns NULL if the FEN is invalid. It is
 * assumed that the string it not empty and that there are no leading or trailing
 * white spaces. Keep in mind that whether the position is actually valid
 * according to the rules of chess is not checked, so even if the FEN string is a
 * valid FEN string according to the grammar, the position might be illegal. For
 * example, the number of pawns in the board is not checked, so it is possible to
 * set up a position using a FEN string that describes a board with 9 pawns. This
 * is intentional, as the user might want to set up a non-standard board.
 */
Position *pos_create(const char *fen)
{
    Position *pos = malloc(sizeof(Position));
    if (!pos) {
        fprintf(stderr, "Could not allocate memory.\n");
        exit(1);
    }
    pos->irreversible = malloc(sizeof(struct irreversible_state));
    if (!pos->irreversible) {
        fprintf(stderr, "Could not allocate memory.\n");
        exit(1);
    }

    pos->fullmove_counter = 0;
    pos->irreversible->previous = NULL;
    pos->irreversible->captured_piece = PIECE_NONE;
    pos_reset_halfmove_clock(pos);
    pos_unset_enpassant(pos);
    pos_remove_castling(pos, COLOR_WHITE, CASTLING_SIDE_KING);
    pos_remove_castling(pos, COLOR_WHITE, CASTLING_SIDE_QUEEN);
    pos_remove_castling(pos, COLOR_BLACK, CASTLING_SIDE_KING);
    pos_remove_castling(pos, COLOR_BLACK, CASTLING_SIDE_QUEEN);
    for (Square sq = A1; sq <= H8; ++sq)
        pos->board[sq] = PIECE_NONE;
    for (size_t i = 0; i < 6; ++i)
        pos->type_bb[i] = 0;
    for (size_t i = 0; i < 2; ++i)
        pos->color_bb[i] = 0;

    size_t rc = parse_fen(pos, fen);
    if (rc != strlen(fen)) {
        pos_destroy(pos);
        return NULL;
    }
    return pos;
}

void pos_destroy(Position *pos)
{
    struct irreversible_state *prev = NULL;

    for (struct irreversible_state *p = pos->irreversible; p; p = prev) {
        prev = p->previous;
        free(p);
    }
    free(pos);
}

Square pos_file_rank_to_square(File f, Rank r)
{
    return 8 * r + f;
}

File pos_get_file_of_square(Square sq)
{
    return sq % 8;
}

Rank pos_get_rank_of_square(Square sq)
{
    return sq / 8;
}

Color pos_get_piece_color(Piece piece)
{
    return piece & 0x1;
}

PieceType pos_get_piece_type(Piece piece)
{
    return piece >> 1;
}

Piece pos_make_piece(PieceType pt, Color c)
{
    return pt << 1 | c;
}

/*
 * Modifies a position by parsing a FEN string and returns the number of
 * characters read, if it's less than the length then an error ocurred. Each of
 * the parse_* functions return the number of characters that were read, and if
 * the sequence of characters is invalid they return 0.
 */
static size_t parse_fen(Position *pos, const char *fen)
{
    size_t (*const steps[])(Position *, const char *) = {
        parse_pieces,
        parse_side,
        parse_castling,
        parse_enpassant,
        parse_halfmove_clock,
        parse_fullmove_counter,
    };
    const size_t num_steps = sizeof(steps) / sizeof(steps[0]);

    size_t rc = 0, ret = 0;
    for (size_t i = 0; i < num_steps; ++i) {
        ret = steps[i](pos, fen);
        if (!ret)
            return 0;
        fen += ret;
        rc += ret;
        if (i < num_steps - 1) {
            if (fen[0] != ' ')
                return 0;
            else
                ++rc;
        }
        ++fen;
    }

    return rc;
}

/*
 * Both the parse_fullmove_counter and parse_halfmove_clock functions parse the
 * number up to the first invalid character (a character that is not part of a
 * number). So the functions will not fail because of the space character after
 * the number in the FEN string.
 */
static size_t parse_fullmove_counter(Position *pos, const char *str)
{
    char *endptr = NULL;
    errno = 0;
    unsigned long counter = strtoul(str, &endptr, 10);
    if (errno == ERANGE)
        return 0;
    else if (endptr == str)
        return 0;
    else if (counter > SHRT_MAX)
        return 0;
    pos->fullmove_counter = (short)counter;
    return endptr - str;
}

static size_t parse_halfmove_clock(Position *pos, const char *str)
{
    char *endptr = NULL;
    errno = 0;
    unsigned long clock = strtoul(str, &endptr, 10);
    if (errno == ERANGE)
        return 0;
    else if (endptr == str)
        return 0;
    else if (clock > SHRT_MAX)
        return 0;
    pos->irreversible->halfmove_clock = (u8)clock;
    return endptr - str;
}

static size_t parse_enpassant(Position *pos, const char *str)
{
    if (str[0] == '-')
        return 1;
    if (!str[0] || !str[1])
        return 0;
    else if (str[0] < 'a' || str[0] > 'h' ||
         (str[1] != '3' && str[1] != '6'))
        return 0;
    File file = str[0] - 'a';
    pos_set_enpassant(pos, file);
    return 2;
}

static size_t parse_castling(Position *pos, const char *str)
{
    if (str[0] == '-')
        return 1;
    int Kcnt = 0, Qcnt = 0, kcnt = 0, qcnt = 0;
    size_t rc = 0;
    for (; str[rc] && str[rc] != ' '; ++rc) {
        switch (str[rc]) {
        case 'K':
            pos_add_castling(pos, COLOR_WHITE,  CASTLING_SIDE_KING);
            ++Kcnt;
            break;
        case 'Q':
            pos_add_castling(pos, COLOR_WHITE, CASTLING_SIDE_QUEEN);
            ++Qcnt;
            break;
        case 'k':
            pos_add_castling(pos, COLOR_BLACK, CASTLING_SIDE_KING);
            ++kcnt;
            break;
        case 'q':
            pos_add_castling(pos, COLOR_BLACK,  CASTLING_SIDE_QUEEN);
            ++qcnt;
            break;
        default:
            return 0;
        }
        if (Kcnt > 1 || Qcnt > 1 || kcnt > 1 || qcnt > 1)
            return 0;
    }
    return rc;
}

static size_t parse_side(Position *pos, const char *str)
{
    switch (str[0]) {
    case 'w':
        pos->side_to_move = COLOR_WHITE;
        break;
    case 'b':
        pos->side_to_move = COLOR_BLACK;
        break;
    default:
        return 0;
    }
    return 1;
}

static size_t parse_pieces(Position *pos, const char *str)
{
    const Piece table[] = {
        ['P'] = PIECE_WHITE_PAWN,   ['p'] = PIECE_BLACK_PAWN,
        ['N'] = PIECE_WHITE_KNIGHT, ['n'] = PIECE_BLACK_KNIGHT,
        ['R'] = PIECE_WHITE_ROOK,   ['r'] = PIECE_BLACK_ROOK,
        ['B'] = PIECE_WHITE_BISHOP, ['b'] = PIECE_BLACK_BISHOP,
        ['Q'] = PIECE_WHITE_QUEEN,  ['q'] = PIECE_BLACK_QUEEN,
        ['K'] = PIECE_WHITE_KING,   ['k'] = PIECE_BLACK_KING,
    };

    size_t rc = 0;
    File file = FILE_A;
    Rank rank = RANK_8;
    for (size_t i = 0; file <= FILE_H || rank > RANK_1; ++i) {
        if (!str[i])
            return 0;
        char ch = str[i];
        ++rc;

        if (file > FILE_H) {
            if (str[i] && str[i] != '/')
                return 0;
            --rank;
            file = FILE_A;
            continue;
        }

        if (isdigit(ch)) {
            int digit = ch - '0';
            if (digit > 8 || digit < 1 || !digit || file + digit > 8)
                return 0;
            file += digit;
        } else if (is_one_of("PNRBQKpnrbqk", ch)) {
            Piece piece = table[(size_t)ch];
            Square sq = pos_file_rank_to_square(file, rank);
            pos_place_piece(pos, sq, piece);
            ++file;
        } else {
            return 0;
        }
    }

    return rc;
}

/*
 * Check if ch is one of the characters in str, where str is a string containing
 * all characters to be checked and not separated by space.
 * For example:
 * is_one_of("ar4h", 'r')
 * returns 1, but
 * is_one_of("r57g", '9')
 * returns 0.
 */
static int is_one_of(const char *str, char ch)
{
    if (!ch || !strchr(str, ch))
        return 0;
    return 1;
}

static char *trim(char *str)
{
    char *end;

    while (isspace(*str))
        ++str;
    if (!*str)
        return str;
    end = str + strlen(str) - 1;
    while (end > str && isspace(*end))
        --end;
    end[1] = '\0';
    return str;
}

static int
get_index_of_first_bit(u64 n)
{
#if defined(__clang__) || defined(__GNUC__)
    return __builtin_ffsll(n) - 1;
#else
    static const int index[64] = {
        0,  47,  1, 56, 48, 27,  2, 60,
        57, 49, 41, 37, 28, 16,  3, 61,
        54, 58, 35, 52, 50, 42, 21, 44,
        38, 32, 29, 23, 17, 11,  4, 62,
        46, 55, 26, 59, 40, 36, 15, 53,
        34, 51, 20, 43, 31, 22, 10, 45,
        25, 39, 14, 33, 19, 30,  9, 24,
        13, 18,  8, 12,  7,  6,  5, 63,
    };
    static const u64 debruijn = U64(0x03f79d71b4cb0a89);

    return index[((n ^ (n - 1)) * debruijn) >> 58];
#endif
}

static int
count_bits(u64 n)
{
#if defined(__clang__) || defined(__GNUC__)
    return __builtin_popcountll(n);
#else
    static const u64 m1  = 0x5555555555555555;
    static const u64 m2  = 0x3333333333333333;
    static const u64 m4  = 0x0f0f0f0f0f0f0f0f;
    static const u64 m8  = 0x00ff00ff00ff00ff;
    static const u64 m16 = 0x0000ffff0000ffff;
    static const u64 m32 = 0x00000000ffffffff;
    static const u64 h01 = 0x0101010101010101;

    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    return (x * h01) >> 56;
#endif
}

And here's the code for pos.h:

#ifndef POSITION_H
#define POSITION_H

#define U64(n) n##ull

typedef uint64_t u64;
typedef uint8_t u8;

typedef enum direction {
    NORTH,
    NORTHEAST,
    EAST,
    SOUTHEAST,
    SOUTH,
    SOUTHWEST,
    WEST,
    NORTHWEST,
} Direction;

typedef enum file {
    FILE_A, FILE_B, FILE_C, FILE_D,
    FILE_E, FILE_F, FILE_G, FILE_H,
} File;

typedef enum rank {
    RANK_1, RANK_2, RANK_3, RANK_4,
    RANK_5, RANK_6, RANK_7, RANK_8,
} Rank;

typedef enum square {
    A1, B1, C1, D1, E1, F1, G1, H1,
    A2, B2, C2, D2, E2, F2, G2, H2,
    A3, B3, C3, D3, E3, F3, G3, H3,
    A4, B4, C4, D4, E4, F4, G4, H4,
    A5, B5, C5, D5, E5, F5, G5, H5,
    A6, B6, C6, D6, E6, F6, G6, H6,
    A7, B7, C7, D7, E7, F7, G7, H7,
    A8, B8, C8, D8, E8, F8, G8, H8,
} Square;

/*
 * It's safe to get the opposite color with the ! operator on the color.
 */
typedef enum color {
    COLOR_WHITE,
    COLOR_BLACK,
} Color;

typedef enum piece_type {
    PIECE_TYPE_PAWN,
    PIECE_TYPE_KNIGHT,
    PIECE_TYPE_ROOK,
    PIECE_TYPE_BISHOP,
    PIECE_TYPE_QUEEN,
    PIECE_TYPE_KING,
} PieceType;

typedef enum piece {
    PIECE_WHITE_PAWN   = COLOR_WHITE | PIECE_TYPE_PAWN   << 1,
    PIECE_WHITE_KNIGHT = COLOR_WHITE | PIECE_TYPE_KNIGHT << 1,
    PIECE_WHITE_ROOK   = COLOR_WHITE | PIECE_TYPE_ROOK   << 1,
    PIECE_WHITE_BISHOP = COLOR_WHITE | PIECE_TYPE_BISHOP << 1,
    PIECE_WHITE_QUEEN  = COLOR_WHITE | PIECE_TYPE_QUEEN  << 1,
    PIECE_WHITE_KING   = COLOR_WHITE | PIECE_TYPE_KING   << 1,

    PIECE_BLACK_PAWN   = COLOR_BLACK | PIECE_TYPE_PAWN   << 1,
    PIECE_BLACK_KNIGHT = COLOR_BLACK | PIECE_TYPE_KNIGHT << 1,
    PIECE_BLACK_ROOK   = COLOR_BLACK | PIECE_TYPE_ROOK   << 1,
    PIECE_BLACK_BISHOP = COLOR_BLACK | PIECE_TYPE_BISHOP << 1,
    PIECE_BLACK_QUEEN  = COLOR_BLACK | PIECE_TYPE_QUEEN  << 1,
    PIECE_BLACK_KING   = COLOR_BLACK | PIECE_TYPE_KING   << 1,

    PIECE_NONE = 0xff /* Only used for the array board. */
} Piece;

typedef enum castling_side {
    CASTLING_SIDE_QUEEN,
    CASTLING_SIDE_KING,
} CastlingSide;

struct position;
typedef struct position Position;

void pos_print(const Position *pos);
void pos_decrement_fullmove_counter(Position *pos);
void pos_increment_fullmove_counter(Position *pos);
void pos_remove_castling(Position *pos, Color c, CastlingSide side);
void pos_add_castling(Position *pos, Color c, CastlingSide side);
void pos_flip_side_to_move(Position *pos);
void pos_set_captured_piece(Position *pos, Piece piece);
void pos_remove_piece(Position *pos, Square sq);
void pos_place_piece(Position *pos, Square sq, Piece piece);
void pos_reset_halfmove_clock(Position *pos);
void pos_increment_halfmove_clock(Position *pos);
void pos_unset_enpassant(Position *pos);
void pos_set_enpassant(Position *pos, File file);
Piece pos_get_captured_piece(const Position *pos);
int pos_has_castling_right(const Position *pos, Color c, CastlingSide side);
int pos_get_fullmove_counter(const Position *pos);
int pos_get_halfmove_clock(const Position *pos);
int pos_enpassant_possible(const Position *pos);
Square pos_get_enpassant(const Position *pos);
Color pos_get_side_to_move(const Position *pos);
Square pos_get_king_square(const Position *pos, Color c);
Piece pos_get_piece_at(const Position *pos, Square sq);
int pos_get_number_of_pieces(const Position *pos, Piece piece);
u64 pos_get_piece_bitboard(const Position *pos, Piece piece);
u64 pos_get_color_bitboard(const Position *pos, Color c);
void pos_backtrack_irreversible_state(Position *pos);
void pos_start_new_irreversible_state(Position *pos);
Position *pos_create(const char *fen);
void pos_destroy(Position *pos);
Square pos_file_rank_to_square(File f, Rank r);
File pos_get_file_of_square(Square sq);
Rank pos_get_rank_of_square(Square sq);
Color pos_get_piece_color(Piece piece);
PieceType pos_get_piece_type(Piece piece);
Piece pos_make_piece(PieceType pt, Color c);

#endif

I added that main function just to have an output, it is not part of the final program, and the get_index_of_first_bit and count_bits functions along with the type definitions of u8 and u64 are supposed to be part of another file, I added them to pos.c just to avoid adding another file to the question.

If you run this program on a terminal with a FEN string as the first argument the output should look like this:

r n b q k b n r
p p p p p p p p
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
P P P P P P P P
R N B Q K B N R

Turn: white
En passant: -
Castling rights: KQkq
Halfmove clock: 0
Fullmove counter: 1

This is the output for the input string "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1". If no input is provided or the string is not a valid FEN string the program will complain.

I want some feedback on the correctness of the code, the board representation and the looks of the code in general, while keeping in mind that the code was written for performance. Note that the FEN parser does not need to be fast since it's only run once when the chess GUI sends a command for setting a position to the engine.

Answer 1

Doc review

It is possible code takes some of these issues into account.

What if rook has not moved but is not there

With "it only means that neither the king nor the rook corresponding to the castling side have moved throughout the game", a rook should be considered moved if it is taken, even if from its original square. Else one could castle with the ghost rook since it never moved.

50 move rule

FEN lacks info indicating the last time a piece taken or pawn advanced.

3 repetitions

FEN lacks info needed for check of the possible outcomes repeating 3 times.

For this and the pervious 50-move concern, a collection of prior and current FEN lines would be enough to record the state. One FEN is not enough to house the state.

Castling

Needs 2 more:

The king is not in check when attempting to castle.

The king will not move across check.

Stalemate and others

What if the side lacks a legal move?
What if the FEN state is invalid due to position? (castling flag OK yet no rook, en pass with no pawn, white to move yet no piece.)
How much error checking is desired?

---

Code review

Good use of const

Good use of pop prefix

Could de more. pop.h creates many named items like NORTH, FILE_A, A1, Square, Color, etc. that may conflict with other code. Consider a more universal use of pop prefix.

Good use of sizeof

Use standard names

u8, u64 may be useful to quickly code, yet lack the clarity of uint8_t, uint64_t. Use the standard.

Avoid assuming unsigned long long and uint64_t are the same

unsigned long long is common today as uint64_t yet is specified to be at least 64-bit. Rather than make unsigned long long constants with #define U64(n) n##ull, use the standard UINT64_C(value) from <stdint.h>.

Allocate to the referenced object, not type

Consider the 2 below. Which do you find easier to code, review and maintain? Which one requires coder to correctly sync type and object?

pos->irreversible = malloc(sizeof(struct irreversible_state));
// vs.
pos->irreversible = malloc(sizeof pos->irreversible[0]);

Magic numbers

Why 6?

for (size_t i = 0; i < 6; ++i)
  pos->type_bb[i] = 0;

Instead:

size_t n = sizeof type_bb / sizeof type_bb[0];
for (size_t i = 0; i < n; ++i)
  pos->type_bb[i] = 0;

Or simply

memset(pos->type_bb, sizeof pos->type_bb, 0);

Style: Why hex?

Surprising use of 0x.

// return piece & 0x1;
return piece & 1;

Style: ()

Even after years of C, code like pt << 1 | c cause me to pause and review those precedence rules. Consider (pt << 1) | c for code that otherwise relies on the less common precedence rules.

Style: {}

Even for 1 line blocks, consider {}.

    //if (!ret)
    //    return 0;
    if (!ret) {
        return 0;
    }

Documentation

The various static functions lack documentation.

Pedantic: is...(negative)

if (isdigit(ch)) is UB when ch < 0 (and not EOF). Use unsigned char ch.

enum size

Note that Piece board[64]; may be wider than 64-bytes as enum piece, which only needs 8-bits, may be wider. Use uint8_t board[64] if reduced size is important.

Speed vs. space

Do not assume smaller memory footprint is faster - often it is the other way around.

In general, use minimal width objects when an array of them is needed. Otherwise use int, unsigned, double and then wider as needed.

For a balance of speed vs. space, consider dropping the bit dibbling of castling, en passant and use struct members. Yet use uint8_t board[64].

short?

Little reason for short

 // short fullmove_counter
 int fullmove_counter

Non-standard board support

Hmm, with more than 2 rooks, 1 king, I see a need for more than 2 castling flags.