Subversion Repositories Games.Chess Giants

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.   Copyright (c) 2011-2013 Ronald de Man
  3.   This file may be redistributed and/or modified without restrictions.
  4.  
  5.   tbcore.c contains engine-independent routines of the tablebase probing code.
  6.   This file should not need to much adaptation to add tablebase probing to
  7.   a particular engine, provided the engine is written in C or C++.
  8. */
  9.  
  10. #include <stdio.h>
  11. #include <stdint.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include <sys/stat.h>
  15. #include <fcntl.h>
  16. #include <mutex>
  17. #include <atomic>
  18. #ifndef _WIN32
  19. #include <unistd.h>
  20. #include <sys/mman.h>
  21. #endif
  22. #include "rtb-core.hpp"
  23.  
  24.  
  25. #define TBMAX_PIECE 254
  26. #define TBMAX_PAWN 256
  27. #define HSHMAX 4
  28.  
  29. #define Swap(a,b) {int tmp=a;a=b;b=tmp;}
  30.  
  31. #define TB_PAWN 1
  32. #define TB_KNIGHT 2
  33. #define TB_BISHOP 3
  34. #define TB_ROOK 4
  35. #define TB_QUEEN 5
  36. #define TB_KING 6
  37.  
  38. #define TB_WPAWN TB_PAWN
  39. #define TB_BPAWN (TB_PAWN | 8)
  40.  
  41. static std::mutex TB_mutex;
  42.  
  43. static bool initialized = false;
  44. static int num_paths = 0;
  45. static char *path_string = NULL;
  46. static char **paths = NULL;
  47.  
  48. static int TBnum_piece, TBnum_pawn;
  49. static struct TBEntry_piece TB_piece[TBMAX_PIECE];
  50. static struct TBEntry_pawn TB_pawn[TBMAX_PAWN];
  51.  
  52. static struct TBHashEntry WDL_hash[1 << TBHASHBITS][HSHMAX];
  53. static struct DTZTableEntry DTZ_hash[1 << TBHASHBITS][HSHMAX];
  54.  
  55. static void init_indices(void);
  56. static uint64_t calc_key_from_pcs(const int *pcs, bool mirror);
  57. static void free_wdl_entry(struct TBEntry *entry);
  58. static void free_dtz_entry(struct TBEntry *entry);
  59.  
  60. static FD open_tb(const char *str, const char *suffix)
  61. {
  62.     for (int  i = 0; i < num_paths; i++) {
  63.         std::string file(paths[i]);
  64.         file += '/';
  65.         file += str;
  66.         file += suffix;
  67. #ifndef _WIN32
  68.         FD fd = open(file.c_str(), O_RDONLY);
  69. #else
  70.         FD fd = CreateFile(file.c_str(), GENERIC_READ, FILE_SHARE_READ, NULL,
  71.                            OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
  72. #endif
  73.         if (fd != FD_ERR) return fd;
  74.     }
  75.     return FD_ERR;
  76. }
  77.  
  78. static void close_tb(FD fd)
  79. {
  80. #ifndef _WIN32
  81.     close(fd);
  82. #else
  83.     CloseHandle(fd);
  84. #endif
  85. }
  86.  
  87. static char *map_file(const char *name, const char *suffix, uint64_t *mapping)
  88. {
  89.     FD fd = open_tb(name, suffix);
  90.     if (fd == FD_ERR)
  91.         return NULL;
  92. #ifndef _WIN32
  93.     struct stat statbuf;
  94.     fstat(fd, &statbuf);
  95.     *mapping = statbuf.st_size;
  96.     char *data = (char *)mmap(NULL, statbuf.st_size, PROT_READ,
  97.                               MAP_SHARED, fd, 0);
  98.     if (data == (char *)(-1)) {
  99.         std::cout << "Could not mmap() " << name << std::endl;
  100.         close_tb(fd);
  101.         return NULL;
  102.     }
  103. #else
  104.     DWORD size_low, size_high;
  105.     size_low = GetFileSize(fd, &size_high);
  106.     //  *size = ((uint64_t)size_high) << 32 | ((uint64_t)size_low);
  107.     HANDLE map = CreateFileMapping(fd, NULL, PAGE_READONLY, size_high, size_low,
  108.                                    NULL);
  109.     if (map == NULL) {
  110.         std::cout << "CreateFileMapping() failed" << std::endl;
  111.         close_tb(fd);
  112.         return NULL;
  113.     }
  114.     *mapping = (uint64_t)map;
  115.     char *data = (char *)MapViewOfFile(map, FILE_MAP_READ, 0, 0, 0);
  116.     if (data == NULL) {
  117.         std::cout << "MapViewOfFile() failed, name = " << name << suffix << ", error = " << GetLastError() << std::endl;
  118.         close_tb(fd);
  119.         return NULL;
  120.     }
  121. #endif
  122.     close_tb(fd);
  123.     return data;
  124. }
  125.  
  126. #ifndef _WIN32
  127. static void unmap_file(char *data, uint64_t size)
  128. {
  129.     if (!data) return;
  130.     munmap(data, size);
  131. }
  132. #else
  133. static void unmap_file(char *data, uint64_t mapping)
  134. {
  135.     if (!data) return;
  136.     UnmapViewOfFile(data);
  137.     CloseHandle((HANDLE)mapping);
  138. }
  139. #endif
  140.  
  141. static void add_to_hash(struct TBEntry *ptr, uint64_t key)
  142. {
  143.     int i, hshidx;
  144.  
  145.     hshidx = key >> (64 - TBHASHBITS);
  146.     i = 0;
  147.     while (i < HSHMAX && WDL_hash[hshidx][i].ptr)
  148.         i++;
  149.     assert(i < HSHMAX);
  150.     WDL_hash[hshidx][i].key = key;
  151.     WDL_hash[hshidx][i].ptr = ptr;
  152. }
  153.  
  154. static void add_to_dtz_hash(uint64_t key1, uint64_t key2)
  155. {
  156.     int i, hshidx;
  157.  
  158.     hshidx = key1 >> (64 - TBHASHBITS);
  159.     i = 0;
  160.     while (i < HSHMAX && DTZ_hash[hshidx][i].key1)
  161.         i++;
  162.     assert(i < HSHMAX);
  163.     DTZ_hash[hshidx][i].key1 = key1;
  164.     DTZ_hash[hshidx][i].key2 = key2;
  165.     DTZ_hash[hshidx][i].entry = NULL;
  166. }
  167.  
  168. static char pchr[] = {'K', 'Q', 'R', 'B', 'N', 'P'};
  169.  
  170. static void init_tb(char *str)
  171. {
  172.     FD fd;
  173.     struct TBEntry *entry;
  174.     int i, j, pcs[16];
  175.     uint64_t key, key2;
  176.     int color;
  177.     char *s;
  178.  
  179.     fd = open_tb(str, WDLSUFFIX);
  180.     if (fd == FD_ERR) return;
  181.     close_tb(fd);
  182.  
  183.     for (i = 0; i < 16; i++)
  184.         pcs[i] = 0;
  185.     color = 0;
  186.     for (s = str; *s; s++)
  187.         switch (*s) {
  188.         case 'P':
  189.             pcs[TB_PAWN | color]++;
  190.             break;
  191.         case 'N':
  192.             pcs[TB_KNIGHT | color]++;
  193.             break;
  194.         case 'B':
  195.             pcs[TB_BISHOP | color]++;
  196.             break;
  197.         case 'R':
  198.             pcs[TB_ROOK | color]++;
  199.             break;
  200.         case 'Q':
  201.             pcs[TB_QUEEN | color]++;
  202.             break;
  203.         case 'K':
  204.             pcs[TB_KING | color]++;
  205.             break;
  206.         case 'v':
  207.             color = 0x08;
  208.             break;
  209.         }
  210.     for (i = 0; i < 8; i++)
  211.         if (pcs[i] != pcs[i+8])
  212.             break;
  213.     key = calc_key_from_pcs(pcs, false);
  214.     key2 = calc_key_from_pcs(pcs, true);
  215.     if (pcs[TB_WPAWN] + pcs[TB_BPAWN] == 0) {
  216.         assert(TBnum_piece < TBMAX_PIECE);
  217.         entry = (struct TBEntry *)&TB_piece[TBnum_piece++];
  218.     } else {
  219.         assert(TBnum_pawn < TBMAX_PAWN);
  220.         entry = (struct TBEntry *)&TB_pawn[TBnum_pawn++];
  221.     }
  222.     entry->key = key;
  223.     entry->ready = 0;
  224.     entry->num = 0;
  225.     for (i = 0; i < 16; i++)
  226.         entry->num += pcs[i];
  227.     entry->symmetric = (key == key2);
  228.     entry->has_pawns = (pcs[TB_WPAWN] + pcs[TB_BPAWN] > 0);
  229.     if (entry->num > Syzygy::TBLargest)
  230.         Syzygy::TBLargest = entry->num;
  231.  
  232.     if (entry->has_pawns) {
  233.         struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
  234.         ptr->pawns[0] = pcs[TB_WPAWN];
  235.         ptr->pawns[1] = pcs[TB_BPAWN];
  236.         if (pcs[TB_BPAWN] > 0
  237.             && (pcs[TB_WPAWN] == 0 || pcs[TB_BPAWN] < pcs[TB_WPAWN])) {
  238.             ptr->pawns[0] = pcs[TB_BPAWN];
  239.             ptr->pawns[1] = pcs[TB_WPAWN];
  240.         }
  241.     } else {
  242.         struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
  243.         for (i = 0, j = 0; i < 16; i++)
  244.             if (pcs[i] == 1) j++;
  245.         if (j >= 3) ptr->enc_type = 0;
  246.         else if (j == 2) ptr->enc_type = 2;
  247.         else { /* only for suicide */
  248.             j = 16;
  249.             for (i = 0; i < 16; i++) {
  250.                 if (pcs[i] < j && pcs[i] > 1) j = pcs[i];
  251.                 ptr->enc_type = 1 + j;
  252.             }
  253.         }
  254.     }
  255.     add_to_hash(entry, key);
  256.     if (key2 != key) add_to_hash(entry, key2);
  257.     add_to_dtz_hash(key, key2);
  258. }
  259.  
  260. void Syzygy::init(const std::string& path)
  261. {
  262.     char str[16];
  263.     int i, j, k, l;
  264.  
  265.     { // The probing code currently expects a little-endian architecture
  266.         static_assert(sizeof(uint32_t) == 4, "Unsupported architecture");
  267.         uint32_t test = 0x01020304;
  268.         unsigned char* p = (unsigned char*)&test;
  269.         if (p[0] != 4 || p[1] != 3 || p[2] != 2 || p[3] != 1)
  270.             return;
  271.     }
  272.  
  273.     if (initialized) {
  274.         free(path_string); path_string = NULL;
  275.         free(paths); paths = NULL;
  276.         struct TBEntry *entry;
  277.         for (i = 0; i < TBnum_piece; i++) {
  278.             entry = (struct TBEntry *)&TB_piece[i];
  279.             free_wdl_entry(entry);
  280.         }
  281.         for (i = 0; i < TBnum_pawn; i++) {
  282.             entry = (struct TBEntry *)&TB_pawn[i];
  283.             free_wdl_entry(entry);
  284.         }
  285.         for (i = 0; i < (1 << TBHASHBITS); i++)
  286.             for (j = 0; j < HSHMAX; j++) {
  287.                 if ((void*) DTZ_hash[i][j].entry) { // Pierre-Marie Baty -- added type cast
  288.                     free_dtz_entry(DTZ_hash[i][j].entry);
  289.                     DTZ_hash[i][j].entry = NULL;
  290.                 }
  291.             }
  292.         TBnum_piece = TBnum_pawn = 0;
  293.         TBLargest = 0;
  294.     } else {
  295.         init_indices();
  296.         initialized = true;
  297.     }
  298.  
  299.     const char *p = path.c_str();
  300.     if (strlen(p) == 0)
  301.         return;
  302.     path_string = (char *)malloc(strlen(p) + 1);
  303.     strcpy_s(path_string, strlen(p) + 1, p); // Pierre-Marie Baty -- use strcpy_s() instead of strcpy
  304.     num_paths = 0;
  305.     for (i = 0;; i++) {
  306.         if (path_string[i] && path_string[i] != SEP_CHAR)
  307.             num_paths++;
  308.         while (path_string[i] && path_string[i] != SEP_CHAR)
  309.             i++;
  310.         if (!path_string[i]) break;
  311.         path_string[i] = 0;
  312.     }
  313.     paths = (char **)malloc(num_paths * sizeof(char *));
  314.     for (i = j = 0; i < num_paths; i++) {
  315.         while (!path_string[j]) j++;
  316.         paths[i] = &path_string[j];
  317.         while (path_string[j]) j++;
  318.     }
  319.  
  320.     for (i = 0; i < (1 << TBHASHBITS); i++)
  321.         for (j = 0; j < HSHMAX; j++) {
  322.             WDL_hash[i][j].key = 0ULL;
  323.             WDL_hash[i][j].ptr = NULL;
  324.         }
  325.  
  326.     for (i = 0; i < (1 << TBHASHBITS); i++)
  327.         for (j = 0; j < HSHMAX; j++) {
  328.             DTZ_hash[i][j].key1 = 0ULL;
  329.             DTZ_hash[i][j].key2 = 0ULL;
  330.             DTZ_hash[i][j].entry = NULL;
  331.         }
  332.  
  333.     for (i = 1; i < 6; i++) {
  334.         sprintf_s(str, sizeof(str), "K%cvK", pchr[i]); // Pierre-Marie Baty -- using sprintf_s() instead of sprintf
  335.         init_tb(str);
  336.     }
  337.  
  338.     for (i = 1; i < 6; i++)
  339.         for (j = i; j < 6; j++) {
  340.             sprintf_s(str, sizeof(str), "K%cvK%c", pchr[i], pchr[j]); // Pierre-Marie Baty -- using sprintf_s() instead of sprintf
  341.             init_tb(str);
  342.         }
  343.  
  344.     for (i = 1; i < 6; i++)
  345.         for (j = i; j < 6; j++) {
  346.             sprintf_s(str, sizeof(str), "K%c%cvK", pchr[i], pchr[j]); // Pierre-Marie Baty -- using sprintf_s() instead of sprintf
  347.             init_tb(str);
  348.         }
  349.  
  350.     for (i = 1; i < 6; i++)
  351.         for (j = i; j < 6; j++)
  352.             for (k = 1; k < 6; k++) {
  353.                 sprintf_s(str, sizeof(str), "K%c%cvK%c", pchr[i], pchr[j], pchr[k]); // Pierre-Marie Baty -- using sprintf_s() instead of sprintf
  354.                 init_tb(str);
  355.             }
  356.  
  357.     for (i = 1; i < 6; i++)
  358.         for (j = i; j < 6; j++)
  359.             for (k = j; k < 6; k++) {
  360.                 sprintf_s(str, sizeof(str), "K%c%c%cvK", pchr[i], pchr[j], pchr[k]); // Pierre-Marie Baty -- using sprintf_s() instead of sprintf
  361.                 init_tb(str);
  362.             }
  363.  
  364.     // 6-piece tables are only supported for 64-bit, because tables are mmap()ed into memory
  365.     if (sizeof(char*) >= 8) {
  366.         for (i = 1; i < 6; i++)
  367.             for (j = i; j < 6; j++)
  368.                 for (k = i; k < 6; k++)
  369.                     for (l = (i == k) ? j : k; l < 6; l++) {
  370.                         sprintf_s(str, sizeof(str), "K%c%cvK%c%c", pchr[i], pchr[j], pchr[k], pchr[l]); // Pierre-Marie Baty -- using sprintf_s() instead of sprintf
  371.                         init_tb(str);
  372.                     }
  373.  
  374.         for (i = 1; i < 6; i++)
  375.             for (j = i; j < 6; j++)
  376.                 for (k = j; k < 6; k++)
  377.                     for (l = 1; l < 6; l++) {
  378.                         sprintf_s(str, sizeof(str), "K%c%c%cvK%c", pchr[i], pchr[j], pchr[k], pchr[l]); // Pierre-Marie Baty -- using sprintf_s() instead of sprintf
  379.                         init_tb(str);
  380.                     }
  381.  
  382.         for (i = 1; i < 6; i++)
  383.             for (j = i; j < 6; j++)
  384.                 for (k = j; k < 6; k++)
  385.                     for (l = k; l < 6; l++) {
  386.                         sprintf_s(str, sizeof(str), "K%c%c%c%cvK", pchr[i], pchr[j], pchr[k], pchr[l]); // Pierre-Marie Baty -- using sprintf_s() instead of sprintf
  387.                         init_tb(str);
  388.                     }
  389.     }
  390.  
  391.     std::cout << "info string Found " << (TBnum_piece + TBnum_pawn) << " syzygy tablebases" << std::endl;
  392. }
  393.  
  394. static const signed char offdiag[] = {
  395.     0,-1,-1,-1,-1,-1,-1,-1,
  396.     1, 0,-1,-1,-1,-1,-1,-1,
  397.     1, 1, 0,-1,-1,-1,-1,-1,
  398.     1, 1, 1, 0,-1,-1,-1,-1,
  399.     1, 1, 1, 1, 0,-1,-1,-1,
  400.     1, 1, 1, 1, 1, 0,-1,-1,
  401.     1, 1, 1, 1, 1, 1, 0,-1,
  402.     1, 1, 1, 1, 1, 1, 1, 0
  403. };
  404.  
  405. static const ubyte triangle[] = {
  406.     6, 0, 1, 2, 2, 1, 0, 6,
  407.     0, 7, 3, 4, 4, 3, 7, 0,
  408.     1, 3, 8, 5, 5, 8, 3, 1,
  409.     2, 4, 5, 9, 9, 5, 4, 2,
  410.     2, 4, 5, 9, 9, 5, 4, 2,
  411.     1, 3, 8, 5, 5, 8, 3, 1,
  412.     0, 7, 3, 4, 4, 3, 7, 0,
  413.     6, 0, 1, 2, 2, 1, 0, 6
  414. };
  415.  
  416. static const ubyte invtriangle[] = {
  417.     1, 2, 3, 10, 11, 19, 0, 9, 18, 27
  418. };
  419.  
  420. static const ubyte invdiag[] = {
  421.     0, 9, 18, 27, 36, 45, 54, 63,
  422.     7, 14, 21, 28, 35, 42, 49, 56
  423. };
  424.  
  425. static const ubyte flipdiag[] = {
  426.     0,  8, 16, 24, 32, 40, 48, 56,
  427.     1,  9, 17, 25, 33, 41, 49, 57,
  428.     2, 10, 18, 26, 34, 42, 50, 58,
  429.     3, 11, 19, 27, 35, 43, 51, 59,
  430.     4, 12, 20, 28, 36, 44, 52, 60,
  431.     5, 13, 21, 29, 37, 45, 53, 61,
  432.     6, 14, 22, 30, 38, 46, 54, 62,
  433.     7, 15, 23, 31, 39, 47, 55, 63
  434. };
  435.  
  436. static const ubyte lower[] = {
  437.     28,  0,  1,  2,  3,  4,  5,  6,
  438.     0, 29,  7,  8,  9, 10, 11, 12,
  439.     1,  7, 30, 13, 14, 15, 16, 17,
  440.     2,  8, 13, 31, 18, 19, 20, 21,
  441.     3,  9, 14, 18, 32, 22, 23, 24,
  442.     4, 10, 15, 19, 22, 33, 25, 26,
  443.     5, 11, 16, 20, 23, 25, 34, 27,
  444.     6, 12, 17, 21, 24, 26, 27, 35
  445. };
  446.  
  447. static const ubyte diag[] = {
  448.     0,  0,  0,  0,  0,  0,  0,  8,
  449.     0,  1,  0,  0,  0,  0,  9,  0,
  450.     0,  0,  2,  0,  0, 10,  0,  0,
  451.     0,  0,  0,  3, 11,  0,  0,  0,
  452.     0,  0,  0, 12,  4,  0,  0,  0,
  453.     0,  0, 13,  0,  0,  5,  0,  0,
  454.     0, 14,  0,  0,  0,  0,  6,  0,
  455.     15,  0,  0,  0,  0,  0,  0,  7
  456. };
  457.  
  458. static const ubyte flap[] = {
  459.     0, 0, 0, 0, 0, 0, 0, 0,
  460.     0, 6, 12, 18, 18, 12, 6, 0,
  461.     1, 7, 13, 19, 19, 13, 7, 1,
  462.     2, 8, 14, 20, 20, 14, 8, 2,
  463.     3, 9, 15, 21, 21, 15, 9, 3,
  464.     4, 10, 16, 22, 22, 16, 10, 4,
  465.     5, 11, 17, 23, 23, 17, 11, 5,
  466.     0, 0, 0, 0, 0, 0, 0, 0
  467. };
  468.  
  469. static const ubyte ptwist[] = {
  470.     0, 0, 0, 0, 0, 0, 0, 0,
  471.     47, 35, 23, 11, 10, 22, 34, 46,
  472.     45, 33, 21, 9, 8, 20, 32, 44,
  473.     43, 31, 19, 7, 6, 18, 30, 42,
  474.     41, 29, 17, 5, 4, 16, 28, 40,
  475.     39, 27, 15, 3, 2, 14, 26, 38,
  476.     37, 25, 13, 1, 0, 12, 24, 36,
  477.     0, 0, 0, 0, 0, 0, 0, 0
  478. };
  479.  
  480. static const ubyte invflap[] = {
  481.     8, 16, 24, 32, 40, 48,
  482.     9, 17, 25, 33, 41, 49,
  483.     10, 18, 26, 34, 42, 50,
  484.     11, 19, 27, 35, 43, 51
  485. };
  486.  
  487. static const ubyte invptwist[] = {
  488.     52, 51, 44, 43, 36, 35, 28, 27, 20, 19, 12, 11,
  489.     53, 50, 45, 42, 37, 34, 29, 26, 21, 18, 13, 10,
  490.     54, 49, 46, 41, 38, 33, 30, 25, 22, 17, 14, 9,
  491.     55, 48, 47, 40, 39, 32, 31, 24, 23, 16, 15, 8
  492. };
  493.  
  494. static const ubyte file_to_file[] = {
  495.     0, 1, 2, 3, 3, 2, 1, 0
  496. };
  497.  
  498. static const short KK_idx[10][64] = {
  499.     { -1, -1, -1,  0,  1,  2,  3,  4,
  500.       -1, -1, -1,  5,  6,  7,  8,  9,
  501.       10, 11, 12, 13, 14, 15, 16, 17,
  502.       18, 19, 20, 21, 22, 23, 24, 25,
  503.       26, 27, 28, 29, 30, 31, 32, 33,
  504.       34, 35, 36, 37, 38, 39, 40, 41,
  505.       42, 43, 44, 45, 46, 47, 48, 49,
  506.       50, 51, 52, 53, 54, 55, 56, 57 },
  507.     { 58, -1, -1, -1, 59, 60, 61, 62,
  508.       63, -1, -1, -1, 64, 65, 66, 67,
  509.       68, 69, 70, 71, 72, 73, 74, 75,
  510.       76, 77, 78, 79, 80, 81, 82, 83,
  511.       84, 85, 86, 87, 88, 89, 90, 91,
  512.       92, 93, 94, 95, 96, 97, 98, 99,
  513.       100,101,102,103,104,105,106,107,
  514.       108,109,110,111,112,113,114,115},
  515.     {116,117, -1, -1, -1,118,119,120,
  516.      121,122, -1, -1, -1,123,124,125,
  517.      126,127,128,129,130,131,132,133,
  518.      134,135,136,137,138,139,140,141,
  519.      142,143,144,145,146,147,148,149,
  520.      150,151,152,153,154,155,156,157,
  521.      158,159,160,161,162,163,164,165,
  522.      166,167,168,169,170,171,172,173 },
  523.     {174, -1, -1, -1,175,176,177,178,
  524.      179, -1, -1, -1,180,181,182,183,
  525.      184, -1, -1, -1,185,186,187,188,
  526.      189,190,191,192,193,194,195,196,
  527.      197,198,199,200,201,202,203,204,
  528.      205,206,207,208,209,210,211,212,
  529.      213,214,215,216,217,218,219,220,
  530.      221,222,223,224,225,226,227,228 },
  531.     {229,230, -1, -1, -1,231,232,233,
  532.      234,235, -1, -1, -1,236,237,238,
  533.      239,240, -1, -1, -1,241,242,243,
  534.      244,245,246,247,248,249,250,251,
  535.      252,253,254,255,256,257,258,259,
  536.      260,261,262,263,264,265,266,267,
  537.      268,269,270,271,272,273,274,275,
  538.      276,277,278,279,280,281,282,283 },
  539.     {284,285,286,287,288,289,290,291,
  540.      292,293, -1, -1, -1,294,295,296,
  541.      297,298, -1, -1, -1,299,300,301,
  542.      302,303, -1, -1, -1,304,305,306,
  543.      307,308,309,310,311,312,313,314,
  544.      315,316,317,318,319,320,321,322,
  545.      323,324,325,326,327,328,329,330,
  546.      331,332,333,334,335,336,337,338 },
  547.     { -1, -1,339,340,341,342,343,344,
  548.       -1, -1,345,346,347,348,349,350,
  549.       -1, -1,441,351,352,353,354,355,
  550.       -1, -1, -1,442,356,357,358,359,
  551.       -1, -1, -1, -1,443,360,361,362,
  552.       -1, -1, -1, -1, -1,444,363,364,
  553.       -1, -1, -1, -1, -1, -1,445,365,
  554.       -1, -1, -1, -1, -1, -1, -1,446 },
  555.     { -1, -1, -1,366,367,368,369,370,
  556.       -1, -1, -1,371,372,373,374,375,
  557.       -1, -1, -1,376,377,378,379,380,
  558.       -1, -1, -1,447,381,382,383,384,
  559.       -1, -1, -1, -1,448,385,386,387,
  560.       -1, -1, -1, -1, -1,449,388,389,
  561.       -1, -1, -1, -1, -1, -1,450,390,
  562.       -1, -1, -1, -1, -1, -1, -1,451 },
  563.     {452,391,392,393,394,395,396,397,
  564.      -1, -1, -1, -1,398,399,400,401,
  565.      -1, -1, -1, -1,402,403,404,405,
  566.      -1, -1, -1, -1,406,407,408,409,
  567.      -1, -1, -1, -1,453,410,411,412,
  568.      -1, -1, -1, -1, -1,454,413,414,
  569.      -1, -1, -1, -1, -1, -1,455,415,
  570.      -1, -1, -1, -1, -1, -1, -1,456 },
  571.     {457,416,417,418,419,420,421,422,
  572.      -1,458,423,424,425,426,427,428,
  573.      -1, -1, -1, -1, -1,429,430,431,
  574.      -1, -1, -1, -1, -1,432,433,434,
  575.      -1, -1, -1, -1, -1,435,436,437,
  576.      -1, -1, -1, -1, -1,459,438,439,
  577.      -1, -1, -1, -1, -1, -1,460,440,
  578.      -1, -1, -1, -1, -1, -1, -1,461 }
  579. };
  580.  
  581. static int binomial[5][64];
  582. static int pawnidx[5][24];
  583. static int pfactor[5][4];
  584.  
  585. static void init_indices(void)
  586. {
  587.     int i, j, k;
  588.  
  589.     // binomial[k-1][n] = Bin(n, k)
  590.     for (i = 0; i < 5; i++)
  591.         for (j = 0; j < 64; j++) {
  592.             int f = j;
  593.             int l = 1;
  594.             for (k = 1; k <= i; k++) {
  595.                 f *= (j - k);
  596.                 l *= (k + 1);
  597.             }
  598.             binomial[i][j] = f / l;
  599.         }
  600.  
  601.     for (i = 0; i < 5; i++) {
  602.         int s = 0;
  603.         for (j = 0; j < 6; j++) {
  604.             pawnidx[i][j] = s;
  605.             s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
  606.         }
  607.         pfactor[i][0] = s;
  608.         s = 0;
  609.         for (; j < 12; j++) {
  610.             pawnidx[i][j] = s;
  611.             s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
  612.         }
  613.         pfactor[i][1] = s;
  614.         s = 0;
  615.         for (; j < 18; j++) {
  616.             pawnidx[i][j] = s;
  617.             s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
  618.         }
  619.         pfactor[i][2] = s;
  620.         s = 0;
  621.         for (; j < 24; j++) {
  622.             pawnidx[i][j] = s;
  623.             s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
  624.         }
  625.         pfactor[i][3] = s;
  626.     }
  627. }
  628.  
  629. static uint64_t encode_piece(struct TBEntry_piece *ptr, ubyte *norm, int *pos, int *factor)
  630. {
  631.     uint64_t idx = 0;
  632.     int i, j, k, m, l, p;
  633.     int n = ptr->num;
  634.  
  635.     if (pos[0] & 0x04) {
  636.         for (i = 0; i < n; i++)
  637.             pos[i] ^= 0x07;
  638.     }
  639.     if (pos[0] & 0x20) {
  640.         for (i = 0; i < n; i++)
  641.             pos[i] ^= 0x38;
  642.     }
  643.  
  644.     for (i = 0; i < n; i++)
  645.         if (offdiag[pos[i]]) break;
  646.     if (i < (ptr->enc_type == 0 ? 3 : 2) && offdiag[pos[i]] > 0)
  647.         for (i = 0; i < n; i++)
  648.             pos[i] = flipdiag[pos[i]];
  649.  
  650.     switch (ptr->enc_type) {
  651.  
  652.     case 0: /* 111 */
  653.         i = (pos[1] > pos[0]);
  654.         j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
  655.  
  656.         if (offdiag[pos[0]])
  657.             idx = triangle[pos[0]] * 63*62 + (pos[1] - i) * 62 + (pos[2] - j);
  658.         else if (offdiag[pos[1]])
  659.             idx = 6*63*62 + diag[pos[0]] * 28*62 + lower[pos[1]] * 62 + pos[2] - j;
  660.         else if (offdiag[pos[2]])
  661.             idx = 6*63*62 + 4*28*62 + (diag[pos[0]]) * 7*28 + (diag[pos[1]] - i) * 28 + lower[pos[2]];
  662.         else
  663.             idx = 6*63*62 + 4*28*62 + 4*7*28 + (diag[pos[0]] * 7*6) + (diag[pos[1]] - i) * 6 + (diag[pos[2]] - j);
  664.         i = 3;
  665.         break;
  666.  
  667.     case 1: /* K3 */
  668.         j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
  669.  
  670.         idx = KK_idx[triangle[pos[0]]][pos[1]];
  671.         if (idx < 441)
  672.             idx = idx + 441 * (pos[2] - j);
  673.         else {
  674.             idx = 441*62 + (idx - 441) + 21 * lower[pos[2]];
  675.             if (!offdiag[pos[2]])
  676.                 idx -= j * 21;
  677.         }
  678.         i = 3;
  679.         break;
  680.  
  681.     default: /* K2 */
  682.         idx = KK_idx[triangle[pos[0]]][pos[1]];
  683.         i = 2;
  684.         break;
  685.     }
  686.     idx *= factor[0];
  687.  
  688.     for (; i < n;) {
  689.         int t = norm[i];
  690.         for (j = i; j < i + t; j++)
  691.             for (k = j + 1; k < i + t; k++)
  692.                 if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
  693.         int s = 0;
  694.         for (m = i; m < i + t; m++) {
  695.             p = pos[m];
  696.             for (l = 0, j = 0; l < i; l++)
  697.                 j += (p > pos[l]);
  698.             s += binomial[m - i][p - j];
  699.         }
  700.         idx += ((uint64_t)s) * ((uint64_t)factor[i]);
  701.         i += t;
  702.     }
  703.  
  704.     return idx;
  705. }
  706.  
  707. // determine file of leftmost pawn and sort pawns
  708. static int pawn_file(struct TBEntry_pawn *ptr, int *pos)
  709. {
  710.     int i;
  711.  
  712.     for (i = 1; i < ptr->pawns[0]; i++)
  713.         if (flap[pos[0]] > flap[pos[i]])
  714.             Swap(pos[0], pos[i]);
  715.  
  716.     return file_to_file[pos[0] & 0x07];
  717. }
  718.  
  719. static uint64_t encode_pawn(struct TBEntry_pawn *ptr, ubyte *norm, int *pos, int *factor)
  720. {
  721.     uint64_t idx;
  722.     int i, j, k, m, s, t;
  723.     int n = ptr->num;
  724.  
  725.     if (pos[0] & 0x04)
  726.         for (i = 0; i < n; i++)
  727.             pos[i] ^= 0x07;
  728.  
  729.     for (i = 1; i < ptr->pawns[0]; i++)
  730.         for (j = i + 1; j < ptr->pawns[0]; j++)
  731.             if (ptwist[pos[i]] < ptwist[pos[j]])
  732.                 Swap(pos[i], pos[j]);
  733.  
  734.     t = ptr->pawns[0] - 1;
  735.     idx = pawnidx[t][flap[pos[0]]];
  736.     for (i = t; i > 0; i--)
  737.         idx += binomial[t - i][ptwist[pos[i]]];
  738.     idx *= factor[0];
  739.  
  740.     // remaining pawns
  741.     i = ptr->pawns[0];
  742.     t = i + ptr->pawns[1];
  743.     if (t > i) {
  744.         for (j = i; j < t; j++)
  745.             for (k = j + 1; k < t; k++)
  746.                 if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
  747.         s = 0;
  748.         for (m = i; m < t; m++) {
  749.             int p = pos[m];
  750.             for (k = 0, j = 0; k < i; k++)
  751.                 j += (p > pos[k]);
  752.             s += binomial[m - i][p - j - 8];
  753.         }
  754.         idx += ((uint64_t)s) * ((uint64_t)factor[i]);
  755.         i = t;
  756.     }
  757.  
  758.     for (; i < n;) {
  759.         t = norm[i];
  760.         for (j = i; j < i + t; j++)
  761.             for (k = j + 1; k < i + t; k++)
  762.                 if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
  763.         s = 0;
  764.         for (m = i; m < i + t; m++) {
  765.             int p = pos[m];
  766.             for (k = 0, j = 0; k < i; k++)
  767.                 j += (p > pos[k]);
  768.             s += binomial[m - i][p - j];
  769.         }
  770.         idx += ((uint64_t)s) * ((uint64_t)factor[i]);
  771.         i += t;
  772.     }
  773.  
  774.     return idx;
  775. }
  776.  
  777. static ubyte decompress_pairs(struct PairsData *d, uint64_t index);
  778.  
  779. // place k like pieces on n squares
  780. static int subfactor(int k, int n)
  781. {
  782.     int i, f, l;
  783.  
  784.     f = n;
  785.     l = 1;
  786.     for (i = 1; i < k; i++) {
  787.         f *= n - i;
  788.         l *= i + 1;
  789.     }
  790.  
  791.     return f / l;
  792. }
  793.  
  794. static uint64_t calc_factors_piece(int *factor, int num, int order, ubyte *norm, ubyte enc_type)
  795. {
  796.     int i, k, n;
  797.     uint64_t f;
  798.     static int pivfac[] = { 31332, 28056, 462 };
  799.  
  800.     n = 64 - norm[0];
  801.  
  802.     f = 1;
  803.     for (i = norm[0], k = 0; i < num || k == order; k++) {
  804.         if (k == order) {
  805.             factor[0] = (int)f; // Pierre-Marie Baty -- added type cast
  806.             f *= pivfac[enc_type];
  807.         } else {
  808.             factor[i] = (int)f; // Pierre-Marie Baty -- added type cast
  809.             f *= subfactor(norm[i], n);
  810.             n -= norm[i];
  811.             i += norm[i];
  812.         }
  813.     }
  814.  
  815.     return f;
  816. }
  817.  
  818. static uint64_t calc_factors_pawn(int *factor, int num, int order, int order2, ubyte *norm, int file)
  819. {
  820.     int i, k, n;
  821.     uint64_t f;
  822.  
  823.     i = norm[0];
  824.     if (order2 < 0x0f) i += norm[i];
  825.     n = 64 - i;
  826.  
  827.     f = 1;
  828.     for (k = 0; i < num || k == order || k == order2; k++) {
  829.         if (k == order) {
  830.             factor[0] = (int)f; // Pierre-Marie Baty -- added type cast
  831.             f *= pfactor[norm[0] - 1][file];
  832.         } else if (k == order2) {
  833.             factor[norm[0]] = (int)f; // Pierre-Marie Baty -- added type cast
  834.             f *= subfactor(norm[norm[0]], 48 - norm[0]);
  835.         } else {
  836.             factor[i] = (int)f; // Pierre-Marie Baty -- added type cast
  837.             f *= subfactor(norm[i], n);
  838.             n -= norm[i];
  839.             i += norm[i];
  840.         }
  841.     }
  842.  
  843.     return f;
  844. }
  845.  
  846. static void set_norm_piece(struct TBEntry_piece *ptr, ubyte *norm, ubyte *pieces)
  847. {
  848.     int i, j;
  849.  
  850.     for (i = 0; i < ptr->num; i++)
  851.         norm[i] = 0;
  852.  
  853.     switch (ptr->enc_type) {
  854.     case 0:
  855.         norm[0] = 3;
  856.         break;
  857.     case 2:
  858.         norm[0] = 2;
  859.         break;
  860.     default:
  861.         norm[0] = ptr->enc_type - 1;
  862.         break;
  863.     }
  864.  
  865.     for (i = norm[0]; i < ptr->num; i += norm[i])
  866.         for (j = i; j < ptr->num && pieces[j] == pieces[i]; j++)
  867.             norm[i]++;
  868. }
  869.  
  870. static void set_norm_pawn(struct TBEntry_pawn *ptr, ubyte *norm, ubyte *pieces)
  871. {
  872.     int i, j;
  873.  
  874.     for (i = 0; i < ptr->num; i++)
  875.         norm[i] = 0;
  876.  
  877.     norm[0] = ptr->pawns[0];
  878.     if (ptr->pawns[1]) norm[ptr->pawns[0]] = ptr->pawns[1];
  879.  
  880.     for (i = ptr->pawns[0] + ptr->pawns[1]; i < ptr->num; i += norm[i])
  881.         for (j = i; j < ptr->num && pieces[j] == pieces[i]; j++)
  882.             norm[i]++;
  883. }
  884.  
  885. static void setup_pieces_piece(struct TBEntry_piece *ptr, unsigned char *data, uint64_t *tb_size)
  886. {
  887.     int i;
  888.     int order;
  889.  
  890.     for (i = 0; i < ptr->num; i++)
  891.         ptr->pieces[0][i] = data[i + 1] & 0x0f;
  892.     order = data[0] & 0x0f;
  893.     set_norm_piece(ptr, ptr->norm[0], ptr->pieces[0]);
  894.     tb_size[0] = calc_factors_piece(ptr->factor[0], ptr->num, order, ptr->norm[0], ptr->enc_type);
  895.  
  896.     for (i = 0; i < ptr->num; i++)
  897.         ptr->pieces[1][i] = data[i + 1] >> 4;
  898.     order = data[0] >> 4;
  899.     set_norm_piece(ptr, ptr->norm[1], ptr->pieces[1]);
  900.     tb_size[1] = calc_factors_piece(ptr->factor[1], ptr->num, order, ptr->norm[1], ptr->enc_type);
  901. }
  902.  
  903. static void setup_pieces_piece_dtz(struct DTZEntry_piece *ptr, unsigned char *data, uint64_t *tb_size)
  904. {
  905.     int i;
  906.     int order;
  907.  
  908.     for (i = 0; i < ptr->num; i++)
  909.         ptr->pieces[i] = data[i + 1] & 0x0f;
  910.     order = data[0] & 0x0f;
  911.     set_norm_piece((struct TBEntry_piece *)ptr, ptr->norm, ptr->pieces);
  912.     tb_size[0] = calc_factors_piece(ptr->factor, ptr->num, order, ptr->norm, ptr->enc_type);
  913. }
  914.  
  915. static void setup_pieces_pawn(struct TBEntry_pawn *ptr, unsigned char *data, uint64_t *tb_size, int f)
  916. {
  917.     int i, j;
  918.     int order, order2;
  919.  
  920.     j = 1 + (ptr->pawns[1] > 0);
  921.     order = data[0] & 0x0f;
  922.     order2 = ptr->pawns[1] ? (data[1] & 0x0f) : 0x0f;
  923.     for (i = 0; i < ptr->num; i++)
  924.         ptr->file[f].pieces[0][i] = data[i + j] & 0x0f;
  925.     set_norm_pawn(ptr, ptr->file[f].norm[0], ptr->file[f].pieces[0]);
  926.     tb_size[0] = calc_factors_pawn(ptr->file[f].factor[0], ptr->num, order, order2, ptr->file[f].norm[0], f);
  927.  
  928.     order = data[0] >> 4;
  929.     order2 = ptr->pawns[1] ? (data[1] >> 4) : 0x0f;
  930.     for (i = 0; i < ptr->num; i++)
  931.         ptr->file[f].pieces[1][i] = data[i + j] >> 4;
  932.     set_norm_pawn(ptr, ptr->file[f].norm[1], ptr->file[f].pieces[1]);
  933.     tb_size[1] = calc_factors_pawn(ptr->file[f].factor[1], ptr->num, order, order2, ptr->file[f].norm[1], f);
  934. }
  935.  
  936. static void setup_pieces_pawn_dtz(struct DTZEntry_pawn *ptr, unsigned char *data, uint64_t *tb_size, int f)
  937. {
  938.     int i, j;
  939.     int order, order2;
  940.  
  941.     j = 1 + (ptr->pawns[1] > 0);
  942.     order = data[0] & 0x0f;
  943.     order2 = ptr->pawns[1] ? (data[1] & 0x0f) : 0x0f;
  944.     for (i = 0; i < ptr->num; i++)
  945.         ptr->file[f].pieces[i] = data[i + j] & 0x0f;
  946.     set_norm_pawn((struct TBEntry_pawn *)ptr, ptr->file[f].norm, ptr->file[f].pieces);
  947.     tb_size[0] = calc_factors_pawn(ptr->file[f].factor, ptr->num, order, order2, ptr->file[f].norm, f);
  948. }
  949.  
  950. static void calc_symlen(struct PairsData *d, int s, char *tmp)
  951. {
  952.     int s1, s2;
  953.  
  954.     int w = *(int *)(d->sympat + 3 * s);
  955.     s2 = (w >> 12) & 0x0fff;
  956.     if (s2 == 0x0fff)
  957.         d->symlen[s] = 0;
  958.     else {
  959.         s1 = w & 0x0fff;
  960.         if (!tmp[s1]) calc_symlen(d, s1, tmp);
  961.         if (!tmp[s2]) calc_symlen(d, s2, tmp);
  962.         d->symlen[s] = d->symlen[s1] + d->symlen[s2] + 1;
  963.     }
  964.     tmp[s] = 1;
  965. }
  966.  
  967. static struct PairsData *setup_pairs(unsigned char *data, uint64_t tb_size, uint64_t *size, unsigned char **next, ubyte *flags, int wdl)
  968. {
  969.     struct PairsData *d;
  970.     int i;
  971.  
  972.     *flags = data[0];
  973.     if (data[0] & 0x80) {
  974.         d = (struct PairsData *)malloc(sizeof(struct PairsData));
  975.         d->idxbits = 0;
  976.         if (wdl)
  977.             d->min_len = data[1];
  978.         else
  979.             d->min_len = 0;
  980.         *next = data + 2;
  981.         size[0] = size[1] = size[2] = 0;
  982.         return d;
  983.     }
  984.  
  985.     int blocksize = data[1];
  986.     int idxbits = data[2];
  987.     int real_num_blocks = *(uint32_t *)(&data[4]);
  988.     int num_blocks = real_num_blocks + *(ubyte *)(&data[3]);
  989.     int max_len = data[8];
  990.     int min_len = data[9];
  991.     int h = max_len - min_len + 1;
  992.     int num_syms = *(ushort *)(&data[10 + 2 * h]);
  993.     d = (struct PairsData *)malloc(sizeof(struct PairsData) + (h - 1) * sizeof(base_t) + num_syms);
  994.     d->blocksize = blocksize;
  995.     d->idxbits = idxbits;
  996.     d->offset = (ushort *)(&data[10]);
  997.     d->symlen = ((ubyte *)d) + sizeof(struct PairsData) + (h - 1) * sizeof(base_t);
  998.     d->sympat = &data[12 + 2 * h];
  999.     d->min_len = min_len;
  1000.     *next = &data[12 + 2 * h + 3 * num_syms + (num_syms & 1)];
  1001.  
  1002.     int num_indices = (int)((tb_size + (1ULL << idxbits) - 1) >> idxbits); // Pierre-Marie Baty -- added type cast
  1003.     size[0] = 6ULL * num_indices;
  1004.     size[1] = 2ULL * num_blocks;
  1005.     size[2] = (1ULL << blocksize) * real_num_blocks;
  1006.  
  1007.     // char tmp[num_syms];
  1008.     char tmp[4096];
  1009.     for (i = 0; i < num_syms; i++)
  1010.         tmp[i] = 0;
  1011.     for (i = 0; i < num_syms; i++)
  1012.         if (!tmp[i])
  1013.             calc_symlen(d, i, tmp);
  1014.  
  1015.     d->base[h - 1] = 0;
  1016.     for (i = h - 2; i >= 0; i--)
  1017.         d->base[i] = (d->base[i + 1] + d->offset[i] - d->offset[i + 1]) / 2;
  1018.     for (i = 0; i < h; i++)
  1019.         d->base[i] <<= 64 - (min_len + i);
  1020.  
  1021.     d->offset -= d->min_len;
  1022.  
  1023.     return d;
  1024. }
  1025.  
  1026. static int init_table_wdl(struct TBEntry *entry, const char *str)
  1027. {
  1028.     ubyte *next;
  1029.     int f, s;
  1030.     uint64_t tb_size[8];
  1031.     uint64_t size[8 * 3];
  1032.     ubyte flags;
  1033.  
  1034.     // first mmap the table into memory
  1035.  
  1036.     entry->data = map_file(str, WDLSUFFIX, &entry->mapping);
  1037.     if (!entry->data) {
  1038.         std::cout << "Could not find " << str << WDLSUFFIX << std::endl;
  1039.         return 0;
  1040.     }
  1041.  
  1042.     ubyte *data = (ubyte *)entry->data;
  1043.     if (((uint32_t *)data)[0] != WDL_MAGIC) {
  1044.         std::cout << "Corrupted table" << std::endl;
  1045.         unmap_file(entry->data, entry->mapping);
  1046.         entry->data = 0;
  1047.         return 0;
  1048.     }
  1049.  
  1050.     int split = data[4] & 0x01;
  1051.     int files = data[4] & 0x02 ? 4 : 1;
  1052.  
  1053.     data += 5;
  1054.  
  1055.     if (!entry->has_pawns) {
  1056.         struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
  1057.         setup_pieces_piece(ptr, data, &tb_size[0]);
  1058.         data += ptr->num + 1;
  1059.         data += ((uintptr_t)data) & 0x01;
  1060.  
  1061.         ptr->precomp[0] = setup_pairs(data, tb_size[0], &size[0], &next, &flags, 1);
  1062.         data = next;
  1063.         if (split) {
  1064.             ptr->precomp[1] = setup_pairs(data, tb_size[1], &size[3], &next, &flags, 1);
  1065.             data = next;
  1066.         } else
  1067.             ptr->precomp[1] = NULL;
  1068.  
  1069.         ptr->precomp[0]->indextable = (char *)data;
  1070.         data += size[0];
  1071.         if (split) {
  1072.             ptr->precomp[1]->indextable = (char *)data;
  1073.             data += size[3];
  1074.         }
  1075.  
  1076.         ptr->precomp[0]->sizetable = (ushort *)data;
  1077.         data += size[1];
  1078.         if (split) {
  1079.             ptr->precomp[1]->sizetable = (ushort *)data;
  1080.             data += size[4];
  1081.         }
  1082.  
  1083.         data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
  1084.         ptr->precomp[0]->data = data;
  1085.         data += size[2];
  1086.         if (split) {
  1087.             data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
  1088.             ptr->precomp[1]->data = data;
  1089.         }
  1090.     } else {
  1091.         struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
  1092.         s = 1 + (ptr->pawns[1] > 0);
  1093.         for (f = 0; f < 4; f++) {
  1094.             setup_pieces_pawn((struct TBEntry_pawn *)ptr, data, &tb_size[2 * f], f);
  1095.             data += ptr->num + s;
  1096.         }
  1097.         data += ((uintptr_t)data) & 0x01;
  1098.  
  1099.         for (f = 0; f < files; f++) {
  1100.             ptr->file[f].precomp[0] = setup_pairs(data, tb_size[2 * f], &size[6 * f], &next, &flags, 1);
  1101.             data = next;
  1102.             if (split) {
  1103.                 ptr->file[f].precomp[1] = setup_pairs(data, tb_size[2 * f + 1], &size[6 * f + 3], &next, &flags, 1);
  1104.                 data = next;
  1105.             } else
  1106.                 ptr->file[f].precomp[1] = NULL;
  1107.         }
  1108.  
  1109.         for (f = 0; f < files; f++) {
  1110.             ptr->file[f].precomp[0]->indextable = (char *)data;
  1111.             data += size[6 * f];
  1112.             if (split) {
  1113.                 ptr->file[f].precomp[1]->indextable = (char *)data;
  1114.                 data += size[6 * f + 3];
  1115.             }
  1116.         }
  1117.  
  1118.         for (f = 0; f < files; f++) {
  1119.             ptr->file[f].precomp[0]->sizetable = (ushort *)data;
  1120.             data += size[6 * f + 1];
  1121.             if (split) {
  1122.                 ptr->file[f].precomp[1]->sizetable = (ushort *)data;
  1123.                 data += size[6 * f + 4];
  1124.             }
  1125.         }
  1126.  
  1127.         for (f = 0; f < files; f++) {
  1128.             data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
  1129.             ptr->file[f].precomp[0]->data = data;
  1130.             data += size[6 * f + 2];
  1131.             if (split) {
  1132.                 data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
  1133.                 ptr->file[f].precomp[1]->data = data;
  1134.                 data += size[6 * f + 5];
  1135.             }
  1136.         }
  1137.     }
  1138.  
  1139.     return 1;
  1140. }
  1141.  
  1142. static int init_table_dtz(struct TBEntry *entry)
  1143. {
  1144.     ubyte *data = (ubyte *)entry->data;
  1145.     ubyte *next;
  1146.     int f, s;
  1147.     uint64_t tb_size[4];
  1148.     uint64_t size[4 * 3];
  1149.  
  1150.     if (!data)
  1151.         return 0;
  1152.  
  1153.     if (((uint32_t *)data)[0] != DTZ_MAGIC) {
  1154.         std::cout << "Corrupted table" << std::endl;
  1155.         return 0;
  1156.     }
  1157.  
  1158.     int files = data[4] & 0x02 ? 4 : 1;
  1159.  
  1160.     data += 5;
  1161.  
  1162.     if (!entry->has_pawns) {
  1163.         struct DTZEntry_piece *ptr = (struct DTZEntry_piece *)entry;
  1164.         setup_pieces_piece_dtz(ptr, data, &tb_size[0]);
  1165.         data += ptr->num + 1;
  1166.         data += ((uintptr_t)data) & 0x01;
  1167.  
  1168.         ptr->precomp = setup_pairs(data, tb_size[0], &size[0], &next, &(ptr->flags), 0);
  1169.         data = next;
  1170.  
  1171.         ptr->map = data;
  1172.         if (ptr->flags & 2) {
  1173.             int i;
  1174.             for (i = 0; i < 4; i++) {
  1175.                 ptr->map_idx[i] = (data + 1 - ptr->map);
  1176.                 data += 1 + data[0];
  1177.             }
  1178.             data += ((uintptr_t)data) & 0x01;
  1179.         }
  1180.  
  1181.         ptr->precomp->indextable = (char *)data;
  1182.         data += size[0];
  1183.  
  1184.         ptr->precomp->sizetable = (ushort *)data;
  1185.         data += size[1];
  1186.  
  1187.         data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
  1188.         ptr->precomp->data = data;
  1189.         data += size[2];
  1190.     } else {
  1191.         struct DTZEntry_pawn *ptr = (struct DTZEntry_pawn *)entry;
  1192.         s = 1 + (ptr->pawns[1] > 0);
  1193.         for (f = 0; f < 4; f++) {
  1194.             setup_pieces_pawn_dtz(ptr, data, &tb_size[f], f);
  1195.             data += ptr->num + s;
  1196.         }
  1197.         data += ((uintptr_t)data) & 0x01;
  1198.  
  1199.         for (f = 0; f < files; f++) {
  1200.             ptr->file[f].precomp = setup_pairs(data, tb_size[f], &size[3 * f], &next, &(ptr->flags[f]), 0);
  1201.             data = next;
  1202.         }
  1203.  
  1204.         ptr->map = data;
  1205.         for (f = 0; f < files; f++) {
  1206.             if (ptr->flags[f] & 2) {
  1207.                 int i;
  1208.                 for (i = 0; i < 4; i++) {
  1209.                     ptr->map_idx[f][i] = (data + 1 - ptr->map);
  1210.                     data += 1 + data[0];
  1211.                 }
  1212.             }
  1213.         }
  1214.         data += ((uintptr_t)data) & 0x01;
  1215.  
  1216.         for (f = 0; f < files; f++) {
  1217.             ptr->file[f].precomp->indextable = (char *)data;
  1218.             data += size[3 * f];
  1219.         }
  1220.  
  1221.         for (f = 0; f < files; f++) {
  1222.             ptr->file[f].precomp->sizetable = (ushort *)data;
  1223.             data += size[3 * f + 1];
  1224.         }
  1225.  
  1226.         for (f = 0; f < files; f++) {
  1227.             data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
  1228.             ptr->file[f].precomp->data = data;
  1229.             data += size[3 * f + 2];
  1230.         }
  1231.     }
  1232.  
  1233.     return 1;
  1234. }
  1235.  
  1236. static inline uint64_t bswap64(uint64_t val) {
  1237. #ifndef _MSC_VER
  1238.     return __builtin_bswap64(val);
  1239. #else
  1240.     return _byteswap_uint64(val);
  1241. #endif
  1242. }
  1243.  
  1244. static inline uint32_t bswap32(uint32_t val) {
  1245. #ifndef _MSC_VER
  1246.     return __builtin_bswap32(val);
  1247. #else
  1248.     return _byteswap_ulong(val);
  1249. #endif
  1250. }
  1251.  
  1252. static ubyte decompress_pairs(struct PairsData *d, uint64_t idx)
  1253. {
  1254.     if (!d->idxbits)
  1255.         return d->min_len;
  1256.  
  1257.     uint32_t mainidx = (uint32_t)(idx >> d->idxbits); // Pierre-Marie Baty -- added type cast
  1258.     int litidx = (idx & ((1LL << d->idxbits) - 1)) - (1LL << (d->idxbits - 1)); // Pierre-Marie Baty -- added constant casts
  1259.     uint32_t block = *(uint32_t *)(d->indextable + 6 * mainidx);
  1260.     litidx += *(ushort *)(d->indextable + 6 * mainidx + 4);
  1261.     if (litidx < 0) {
  1262.         do {
  1263.             litidx += d->sizetable[--block] + 1;
  1264.         } while (litidx < 0);
  1265.     } else {
  1266.         while (litidx > d->sizetable[block])
  1267.             litidx -= d->sizetable[block++] + 1;
  1268.     }
  1269.  
  1270.     uint32_t *ptr = (uint32_t *)(d->data + (block << d->blocksize));
  1271.  
  1272.     int m = d->min_len;
  1273.     ushort *offset = d->offset;
  1274.     base_t *base = d->base - m;
  1275.     ubyte *symlen = d->symlen;
  1276.     int sym, bitcnt;
  1277.  
  1278.     uint64_t code = bswap64(*((uint64_t *)ptr));
  1279.     ptr += 2;
  1280.     bitcnt = 0; // number of "empty bits" in code
  1281.     for (;;) {
  1282.         int l = m;
  1283.         while (code < base[l]) l++;
  1284.         sym = (int)(offset[l] + ((code - base[l]) >> (64 - l))); // Pierre-Marie Baty -- added type cast
  1285.         if (litidx < (int)symlen[sym] + 1) break;
  1286.         litidx -= (int)symlen[sym] + 1;
  1287.         code <<= l;
  1288.         bitcnt += l;
  1289.         if (bitcnt >= 32) {
  1290.             bitcnt -= 32;
  1291.             code |= ((uint64_t)(bswap32(*ptr++))) << bitcnt;
  1292.         }
  1293.     }
  1294.  
  1295.     ubyte *sympat = d->sympat;
  1296.     while (symlen[sym] != 0) {
  1297.         int w = *(int *)(sympat + 3 * sym);
  1298.         int s1 = w & 0x0fff;
  1299.         if (litidx < (int)symlen[s1] + 1)
  1300.             sym = s1;
  1301.         else {
  1302.             litidx -= (int)symlen[s1] + 1;
  1303.             sym = (w >> 12) & 0x0fff;
  1304.         }
  1305.     }
  1306.  
  1307.     return *(sympat + 3 * sym);
  1308. }
  1309.  
  1310. TBEntry* load_dtz_table(const char* str, uint64_t key1, uint64_t key2)
  1311. {
  1312.     int i;
  1313.     struct TBEntry *ptr, *ptr3;
  1314.     struct TBHashEntry *ptr2;
  1315.  
  1316.     // find corresponding WDL entry
  1317.     ptr2 = WDL_hash[key1 >> (64 - TBHASHBITS)];
  1318.     for (i = 0; i < HSHMAX; i++)
  1319.         if (ptr2[i].key == key1) break;
  1320.     if (i == HSHMAX) return NULL;
  1321.     ptr = ptr2[i].ptr;
  1322.  
  1323.     ptr3 = (struct TBEntry *)malloc(ptr->has_pawns
  1324.                                     ? sizeof(struct DTZEntry_pawn)
  1325.                                     : sizeof(struct DTZEntry_piece));
  1326.  
  1327.     ptr3->data = map_file(str, DTZSUFFIX, &ptr3->mapping);
  1328.     ptr3->key = ptr->key;
  1329.     ptr3->num = ptr->num;
  1330.     ptr3->symmetric = ptr->symmetric;
  1331.     ptr3->has_pawns = ptr->has_pawns;
  1332.     if (ptr3->has_pawns) {
  1333.         struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *)ptr3;
  1334.         entry->pawns[0] = ((struct TBEntry_pawn *)ptr)->pawns[0];
  1335.         entry->pawns[1] = ((struct TBEntry_pawn *)ptr)->pawns[1];
  1336.     } else {
  1337.         struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr3;
  1338.         entry->enc_type = ((struct TBEntry_piece *)ptr)->enc_type;
  1339.     }
  1340.     if (!init_table_dtz(ptr3)) {
  1341.         free(ptr3);
  1342.         return NULL;
  1343.     }
  1344.     return ptr3;
  1345. }
  1346.  
  1347. static void free_wdl_entry(struct TBEntry *entry)
  1348. {
  1349.     unmap_file(entry->data, entry->mapping);
  1350.     entry->data = NULL;
  1351.     if (!entry->has_pawns) {
  1352.         struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
  1353.         free(ptr->precomp[0]); ptr->precomp[0] = NULL;
  1354.         free(ptr->precomp[1]); ptr->precomp[1] = NULL;
  1355.     } else {
  1356.         struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
  1357.         int f;
  1358.         for (f = 0; f < 4; f++) {
  1359.             free(ptr->file[f].precomp[0]); ptr->file[f].precomp[0] = NULL;
  1360.             free(ptr->file[f].precomp[1]); ptr->file[f].precomp[1] = NULL;
  1361.         }
  1362.     }
  1363. }
  1364.  
  1365. static void free_dtz_entry(struct TBEntry *entry)
  1366. {
  1367.     unmap_file(entry->data, entry->mapping);
  1368.     entry->data = NULL;
  1369.     if (!entry->has_pawns) {
  1370.         struct DTZEntry_piece *ptr = (struct DTZEntry_piece *)entry;
  1371.         free(ptr->precomp); ptr->precomp = NULL;
  1372.     } else {
  1373.         struct DTZEntry_pawn *ptr = (struct DTZEntry_pawn *)entry;
  1374.         int f;
  1375.         for (f = 0; f < 4; f++) {
  1376.             free(ptr->file[f].precomp); ptr->file[f].precomp = NULL;
  1377.         }
  1378.     }
  1379.     free(entry);
  1380. }
  1381.  
  1382. static int wdl_to_map[5] = { 1, 3, 0, 2, 0 };
  1383. static ubyte pa_flags[5] = { 8, 0, 0, 0, 4 };
  1384.