Subversion Repositories Games.Chess Giants

Rev

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