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