git.sesse.net Git - stockfish/blob - src/syzygy/tbcore.cpp

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