7 int cto_fd, ctg_fd, ctb_fd;
9 unsigned int tbl2[] = {
10 0x3100d2bf, 0x3118e3de, 0x34ab1372, 0x2807a847,
11 0x1633f566, 0x2143b359, 0x26d56488, 0x3b9e6f59,
12 0x37755656, 0x3089ca7b, 0x18e92d85, 0x0cd0e9d8,
13 0x1a9e3b54, 0x3eaa902f, 0x0d9bfaae, 0x2f32b45b,
14 0x31ed6102, 0x3d3c8398, 0x146660e3, 0x0f8d4b76,
15 0x02c77a5f, 0x146c8799, 0x1c47f51f, 0x249f8f36,
16 0x24772043, 0x1fbc1e4d, 0x1e86b3fa, 0x37df36a6,
17 0x16ed30e4, 0x02c3148e, 0x216e5929, 0x0636b34e,
18 0x317f9f56, 0x15f09d70, 0x131026fb, 0x38c784b1,
19 0x29ac3305, 0x2b485dc5, 0x3c049ddc, 0x35a9fbcd,
20 0x31d5373b, 0x2b246799, 0x0a2923d3, 0x08a96e9d,
21 0x30031a9f, 0x08f525b5, 0x33611c06, 0x2409db98,
22 0x0ca4feb2, 0x1000b71e, 0x30566e32, 0x39447d31,
23 0x194e3752, 0x08233a95, 0x0f38fe36, 0x29c7cd57,
24 0x0f7b3a39, 0x328e8a16, 0x1e7d1388, 0x0fba78f5,
25 0x274c7e7c, 0x1e8be65c, 0x2fa0b0bb, 0x1eb6c371
28 signed char data[] = {
29 0x36, 0xb6, 0x0f, 0x79, 0x61, 0x1f, 0x50, 0xde, 0x61, 0xb9, 0x52, 0x24, 0xb3, 0xac, 0x6e, 0x5e, 0x0a, 0x69, 0xbd, 0x61, 0x61, 0xc5
32 void output_stats(char *result, int invert)
34 unsigned char *ptr = result;
40 printf("%u,", (ptr[0] << 16) | (ptr[1] << 8) | ptr[2]);
41 printf("%u,", (ptr[6] << 16) | (ptr[7] << 8) | ptr[8]);
42 printf("%u,", (ptr[3] << 16) | (ptr[4] << 8) | ptr[5]);
44 printf("%u,", (ptr[3] << 16) | (ptr[4] << 8) | ptr[5]);
45 printf("%u,", (ptr[6] << 16) | (ptr[7] << 8) | ptr[8]);
46 printf("%u,", (ptr[0] << 16) | (ptr[1] << 8) | ptr[2]);
55 int rat2_sum, rat2_div;
56 rat2_div = (ptr[0] << 16) | (ptr[1] << 8) | ptr[2];
57 rat2_sum = (ptr[3] << 24) | (ptr[4] << 16) | (ptr[5] << 8) | ptr[6];
62 printf("%u,%u", rat2_sum / rat2_div, rat2_div);
69 unsigned int gen_hash(signed char *ptr, unsigned len)
75 for (i = 0; i < len; ++i) {
76 signed char ch = *ptr++;
77 tmp += ((0x0f - (ch & 0x0f)) << 2) + 1;
78 hash += tbl2[tmp & 0x3f];
79 tmp += ((0xf0 - (ch & 0xf0)) >> 2) + 1;
80 hash += tbl2[tmp & 0x3f];
85 void decode_fen_board(char *str, char *board)
131 fprintf(stderr, "Unknown FEN board character '%c'\n", *str);
139 void invert_board(char *board)
144 for (y = 0; y < 4; ++y) {
145 for (x = 0; x < 8; ++x) {
146 char tmp = board[y * 8 + (x)];
147 board[y * 8 + (x)] = board[(7-y) * 8 + (x)];
148 board[(7-y) * 8 + (x)] = tmp;
153 for (y = 0; y < 8; ++y) {
154 for (x = 0; x < 8; ++x) {
155 if (board[y * 8 + x] == toupper(board[y * 8 + x])) {
156 board[y * 8 + x] = tolower(board[y * 8 + x]);
158 board[y * 8 + x] = toupper(board[y * 8 + x]);
164 unsigned char position[32];
170 position[pos_len] <<= 1;
172 position[pos_len] |= 1;
174 if (--bits_left == 0) {
180 void encode_position(char *board, int invert, char *castling_rights, char *ep_column)
186 memset(position, 0, 32);
188 // leave some room for the header byte, which will be filled last
192 // slightly unusual ordering
193 for (x = 0; x < 8; ++x) {
194 for (y = 0; y < 8; ++y) {
195 switch (board[(7-y) * 8 + x]) {
288 if (strcmp(ep_column, "-") != 0) {
289 int epcn = ep_column[0] - 'a';
291 // only encode en passant if a capture is actually possible
292 if ((epcn > 0 && board[3*8 + epcn - 1] == 'P') ||
293 (epcn < 7 && board[3*8 + epcn + 1] == 'P')) {
296 put_bit(epcn & 0x80);
297 put_bit(epcn & 0x40);
298 put_bit(epcn & 0x20);
299 put_bit(epcn & 0x10);
300 put_bit(epcn & 0x08);
301 put_bit(epcn & 0x04);
302 put_bit(epcn & 0x02);
303 put_bit(epcn & 0x01);
307 // really odd padding
309 int i, nb = bits_left - 4;
310 for (i = 0; i < nb; ++i) {
311 //printf("spare bit\n");
317 if (strcmp(castling_rights, "-") != 0) {
319 put_bit(strchr(castling_rights, 'K') != NULL);
320 put_bit(strchr(castling_rights, 'Q') != NULL);
321 put_bit(strchr(castling_rights, 'k') != NULL);
322 put_bit(strchr(castling_rights, 'q') != NULL);
324 put_bit(strchr(castling_rights, 'k') != NULL);
325 put_bit(strchr(castling_rights, 'q') != NULL);
326 put_bit(strchr(castling_rights, 'K') != NULL);
327 put_bit(strchr(castling_rights, 'Q') != NULL);
337 // and the header byte
338 position[0] = pos_len;
340 if (strcmp(castling_rights, "-") != 0)
349 for (i = 0; i < pos_len; ++i) {
350 printf("%02x ", position[i]);
357 int search_pos(unsigned c, char *result)
360 unsigned char pagebuf[4096];
364 lseek(cto_fd, c * 4 + 16, SEEK_SET);
366 read(cto_fd, buf, 4);
367 page = htonl(*((unsigned *)buf));
371 lseek(ctg_fd, page * 4096 + 4096, SEEK_SET);
372 read(ctg_fd, pagebuf, 4096);
377 int page_end = htons(*((short *)(pagebuf + 2)));
379 while (pos < page_end) {
380 if (pagebuf[pos] != position[0] ||
381 memcmp(pagebuf + pos, position, pos_len) != 0) {
382 // no match, skip through
383 pos += pagebuf[pos] & 0x1f;
388 pos += pagebuf[pos] & 0x1f;
389 memcpy(result, pagebuf + pos, pagebuf[pos] + 33);
397 int lookup_position(char *pos, unsigned len, char *result)
399 int hash = gen_hash(position, pos_len);
402 for (n = 0; n < 0x7fffffff; n = 2 * n + 1) {
403 unsigned c = (hash & n) + n;
405 // FIXME: adjust these bounds
409 if (search_pos(c, result))
425 struct moveenc movetable[] = {
427 0x01, 'N', 2, -1, -2,
436 0x0f, 'N', 1, -1, -2,
455 0x30, 'N', 2, -2, -1,
482 0x6b, 'K', 1, 0, 2, /* short castling */
501 0x8c, 'K', 1, -1, -1,
542 0xda, 'N', 1, -2, -1,
562 0xf6, 'K', 1, 0, -2, /* long castling */
567 int find_piece(char *board, char piece, int num)
570 for (x = 0; x < 8; ++x) {
571 for (y = 0; y < 8; ++y) {
572 if (board[(7-y) * 8 + x] != piece)
579 fprintf(stderr, "Couldn't find piece '%c' number %u\n", piece, num);
582 void execute_move(char *board, char *castling_rights, int inverted, char *ep_square, int from_square, int to_square)
584 int black_ks, black_qs, white_ks, white_qs;
587 from_square = (7 - (from_square / 8)) * 8 + (from_square % 8);
588 to_square = (7 - (to_square / 8)) * 8 + (to_square % 8);
590 // compute the new castling rights
591 black_ks = (strchr(castling_rights, 'k') != NULL);
592 black_qs = (strchr(castling_rights, 'q') != NULL);
593 white_ks = (strchr(castling_rights, 'K') != NULL);
594 white_qs = (strchr(castling_rights, 'Q') != NULL);
596 if (board[from_square] == 'K') {
598 black_ks = black_qs = 0;
600 white_ks = white_qs = 0;
601 } else if (board[from_square] == 'R') {
603 if (from_square == 0) // a1
605 else if (from_square == 7 * 8 + 0) // a8
608 if (from_square == 0) // a1
610 else if (from_square == 7 * 8 + 0) // a8
615 if ((black_ks | black_qs | white_ks | white_qs) == 0) {
616 strcpy(castling_rights, "-");
618 strcpy(castling_rights, "");
621 strcat(castling_rights, "K");
623 strcat(castling_rights, "Q");
625 strcat(castling_rights, "k");
627 strcat(castling_rights, "q");
631 if (board[from_square] == 'P' && to_square - from_square == -16) {
632 sprintf(ep_square, "%c%u", "abcdefgh"[from_square % 8], from_square / 8 + 2);
634 strcpy(ep_square, "-");
637 // is this move an en passant capture?
638 if (board[from_square] == 'P' && board[to_square] == ' ' &&
639 (to_square - from_square == -9 || to_square - from_square == -7)) {
640 board[to_square + 8] = ' ';
644 board[to_square] = board[from_square];
645 board[from_square] = ' ';
647 if (board[to_square] == 'K' && to_square - from_square == 2) {
649 board[to_square - 1] = 'R';
650 board[to_square + 1] = ' ';
651 } else if (board[to_square] == 'K' && to_square - from_square == -2) {
653 board[to_square + 1] = 'R';
654 board[to_square - 2] = ' ';
662 for (y = 0; y < 8; ++y) {
663 for (x = 0; x < 8; ++x) {
664 putchar(board[y * 8 + x]);
669 printf("cr='%s' ep='%s'\n", castling_rights, ep_square);
673 void dump_move(char *board, char *castling_rights, char *ep_col, int invert, char move, char annotation)
676 char newboard[64], nkr[5], neps[3];
677 for (i = 0; i < sizeof(movetable)/sizeof(movetable[0]); ++i) {
678 int from_square, from_row, from_col;
679 int to_square, to_row, to_col;
683 if (move != movetable[i].encoding)
686 from_square = find_piece(board, movetable[i].piece, movetable[i].num);
687 from_row = from_square / 8;
688 from_col = from_square % 8;
690 to_row = (from_row + 8 + movetable[i].forward) % 8;
691 to_col = (from_col + 8 + movetable[i].right) % 8;
692 to_square = to_row * 8 + to_col;
697 "abcdefgh"[from_square % 8], (7 - from_square / 8) + 1,
698 "abcdefgh"[to_square % 8], (7 - to_square / 8) + 1);
701 "abcdefgh"[from_square % 8], from_square / 8 + 1,
702 "abcdefgh"[to_square % 8], to_square / 8 + 1);
705 switch (annotation) {
727 printf(" (only move)");
730 printf(" (zugzwang)");
733 printf(" (unknown status 0x%02x)", annotation);
737 // do the move, and look up the new position
738 memcpy(newboard, board, 64);
739 strcpy(nkr, castling_rights);
740 execute_move(newboard, nkr, invert, neps, from_square, to_square);
741 invert_board(newboard);
743 encode_position(newboard, !invert, nkr, neps);
744 ret = lookup_position(position, pos_len, result);
746 fprintf(stderr, "Destination move not found in book.\n");
750 output_stats(result, invert);
754 fprintf(stderr, "ERROR: Unknown move 0x%02x\n", move);
757 void dump_info(char *board, char *castling_rights, char *ep_col, int invert, char *result)
759 int book_moves = result[0] >> 1;
763 output_stats(result, !invert);
765 for (i = 0; i < book_moves; ++i) {
766 dump_move(board, castling_rights, ep_col, invert, result[i * 2 + 1], result[i * 2 + 2]);
770 int main(int argc, char **argv)
772 // encode the position
773 char board[64], result[256];
777 ctg_fd = open("RybkaII.ctg", O_RDONLY);
778 cto_fd = open("RybkaII.cto", O_RDONLY);
779 ctb_fd = open("RybkaII.ctb", O_RDONLY);
780 decode_fen_board(argv[1], board);
782 // always from white's position
783 if (argv[2][0] == 'b') {
792 for (y = 0; y < 8; ++y) {
793 for (x = 0; x < 8; ++x) {
794 putchar(board[y * 8 + x]);
801 encode_position(board, invert, argv[3], argv[4]);
802 ret = lookup_position(position, pos_len, result);
804 printf("Not found in book.\n");
808 dump_info(board, argv[3], argv[4], invert, result);