2 Copyright (c) 2011-2013 Ronald de Man
3 This file may be redistributed and/or modified without restrictions.
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++.
22 #define TBMAX_PIECE 254
23 #define TBMAX_PAWN 256
26 #define Swap(a,b) {int tmp=a;a=b;b=tmp;}
35 #define TB_WPAWN TB_PAWN
36 #define TB_BPAWN (TB_PAWN | 8)
38 static LOCK_T TB_mutex;
40 static bool initialized = false;
41 static int num_paths = 0;
42 static char *path_string = NULL;
43 static char **paths = NULL;
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];
49 static struct TBHashEntry TB_hash[1 << TBHASHBITS][HSHMAX];
51 #define DTZ_ENTRIES 64
53 static struct DTZTableEntry DTZ_table[DTZ_ENTRIES];
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);
60 static FD open_tb(const char *str, const char *suffix)
66 for (i = 0; i < num_paths; i++) {
67 strcpy(file, paths[i]);
72 fd = open(file, O_RDONLY);
74 fd = CreateFile(file, GENERIC_READ, FILE_SHARE_READ, NULL,
75 OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
77 if (fd != FD_ERR) return fd;
82 static void close_tb(FD fd)
91 static char *map_file(const char *name, const char *suffix, uint64 *mapping)
93 FD fd = open_tb(name, suffix);
99 *mapping = statbuf.st_size;
100 char *data = (char *)mmap(NULL, statbuf.st_size, PROT_READ,
102 if (data == (char *)(-1)) {
103 printf("Could not mmap() %s.\n", name);
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,
113 printf("CreateFileMapping() failed.\n");
116 *mapping = (uint64)map;
117 char *data = (char *)MapViewOfFile(map, FILE_MAP_READ, 0, 0, 0);
119 printf("MapViewOfFile() failed, name = %s%s, error = %lu.\n", name, suffix, GetLastError());
128 static void unmap_file(char *data, uint64 size)
134 static void unmap_file(char *data, uint64 mapping)
137 UnmapViewOfFile(data);
138 CloseHandle((HANDLE)mapping);
142 static void add_to_hash(struct TBEntry *ptr, uint64 key)
146 hshidx = key >> (64 - TBHASHBITS);
148 while (i < HSHMAX && TB_hash[hshidx][i].ptr)
151 printf("HSHMAX too low!\n");
154 TB_hash[hshidx][i].key = key;
155 TB_hash[hshidx][i].ptr = ptr;
159 static char pchr[] = {'K', 'Q', 'R', 'B', 'N', 'P'};
161 static void init_tb(char *str)
164 struct TBEntry *entry;
170 fd = open_tb(str, WDLSUFFIX);
171 if (fd == FD_ERR) return;
174 for (i = 0; i < 16; i++)
177 for (s = str; *s; s++)
180 pcs[TB_PAWN | color]++;
183 pcs[TB_KNIGHT | color]++;
186 pcs[TB_BISHOP | color]++;
189 pcs[TB_ROOK | color]++;
192 pcs[TB_QUEEN | color]++;
195 pcs[TB_KING | color]++;
201 for (i = 0; i < 8; i++)
202 if (pcs[i] != pcs[i+8])
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");
211 entry = (struct TBEntry *)&TB_piece[TBnum_piece++];
213 if (TBnum_pawn == TBMAX_PAWN) {
214 printf("TBMAX_PAWN limit too low!\n");
217 entry = (struct TBEntry *)&TB_pawn[TBnum_pawn++];
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;
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];
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 */
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);
252 add_to_hash(entry, key);
253 if (key2 != key) add_to_hash(entry, key2);
256 void Tablebases::init(const std::string& path)
264 struct TBEntry *entry;
265 for (i = 0; i < TBnum_piece; i++) {
266 entry = (struct TBEntry *)&TB_piece[i];
267 free_wdl_entry(entry);
269 for (i = 0; i < TBnum_pawn; i++) {
270 entry = (struct TBEntry *)&TB_pawn[i];
271 free_wdl_entry(entry);
273 for (i = 0; i < DTZ_ENTRIES; i++)
274 if (DTZ_table[i].entry)
275 free_dtz_entry(DTZ_table[i].entry);
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);
287 if (path_string[i] != SEP_CHAR)
289 while (path_string[i] && path_string[i] != SEP_CHAR)
291 if (!path_string[i]) break;
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++;
303 TBnum_piece = TBnum_pawn = 0;
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;
312 for (i = 0; i < DTZ_ENTRIES; i++)
313 DTZ_table[i].entry = NULL;
315 for (i = 1; i < 6; i++) {
316 sprintf(str, "K%cvK", pchr[i]);
320 for (i = 1; i < 6; i++)
321 for (j = i; j < 6; j++) {
322 sprintf(str, "K%cvK%c", pchr[i], pchr[j]);
326 for (i = 1; i < 6; i++)
327 for (j = i; j < 6; j++) {
328 sprintf(str, "K%c%cvK", pchr[i], pchr[j]);
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]);
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]);
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]);
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]);
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]);
370 printf("info string Found %d tablebases.\n", TBnum_piece + TBnum_pawn);
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
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
395 static const ubyte invtriangle[] = {
396 1, 2, 3, 10, 11, 19, 0, 9, 18, 27
399 static const ubyte invdiag[] = {
400 0, 9, 18, 27, 36, 45, 54, 63,
401 7, 14, 21, 28, 35, 42, 49, 56
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
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
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
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
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
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
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
473 static const ubyte file_to_file[] = {
474 0, 1, 2, 3, 3, 2, 1, 0
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 }
560 static int binomial[5][64];
561 static int pawnidx[5][24];
562 static int pfactor[5][4];
564 static void init_indices(void)
568 // binomial[k-1][n] = Bin(n, k)
569 for (i = 0; i < 5; i++)
570 for (j = 0; j < 64; j++) {
573 for (k = 1; k <= i; k++) {
577 binomial[i][j] = f / l;
580 for (i = 0; i < 5; i++) {
582 for (j = 0; j < 6; j++) {
584 s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
588 for (; j < 12; j++) {
590 s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
594 for (; j < 18; j++) {
596 s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
600 for (; j < 24; j++) {
602 s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
608 static uint64 encode_piece(struct TBEntry_piece *ptr, ubyte *norm, int *pos, int *factor)
611 int i, j, k, m, l, p;
615 for (i = 0; i < n; i++)
619 for (i = 0; i < n; i++)
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]];
629 switch (ptr->enc_type) {
632 i = (pos[1] > pos[0]);
633 j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
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]];
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);
647 j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
649 idx = KK_idx[triangle[pos[0]]][pos[1]];
651 idx = idx + 441 * (pos[2] - j);
653 idx = 441*62 + (idx - 441) + 21 * lower[pos[2]];
654 if (!offdiag[pos[2]])
661 idx = KK_idx[triangle[pos[0]]][pos[1]];
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]);
673 for (m = i; m < i + t; m++) {
675 for (l = 0, j = 0; l < i; l++)
677 s += binomial[m - i][p - j];
679 idx += ((uint64)s) * ((uint64)factor[i]);
686 // determine file of leftmost pawn and sort pawns
687 static int pawn_file(struct TBEntry_pawn *ptr, int *pos)
691 for (i = 1; i < ptr->pawns[0]; i++)
692 if (flap[pos[0]] > flap[pos[i]])
693 Swap(pos[0], pos[i]);
695 return file_to_file[pos[0] & 0x07];
698 static uint64 encode_pawn(struct TBEntry_pawn *ptr, ubyte *norm, int *pos, int *factor)
701 int i, j, k, m, s, t;
705 for (i = 0; i < n; i++)
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]);
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]]];
721 t = i + ptr->pawns[1];
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]);
727 for (m = i; m < t; m++) {
729 for (k = 0, j = 0; k < i; k++)
731 s += binomial[m - i][p - j - 8];
733 idx += ((uint64)s) * ((uint64)factor[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]);
743 for (m = i; m < i + t; m++) {
745 for (k = 0, j = 0; k < i; k++)
747 s += binomial[m - i][p - j];
749 idx += ((uint64)s) * ((uint64)factor[i]);
756 // place k like pieces on n squares
757 static int subfactor(int k, int n)
763 for (i = 1; i < k; i++) {
771 static uint64 calc_factors_piece(int *factor, int num, int order, ubyte *norm, ubyte enc_type)
775 static int pivfac[] = { 31332, 28056, 462 };
780 for (i = norm[0], k = 0; i < num || k == order; k++) {
782 factor[0] = static_cast<int>(f);
783 f *= pivfac[enc_type];
785 factor[i] = static_cast<int>(f);
786 f *= subfactor(norm[i], n);
795 static uint64 calc_factors_pawn(int *factor, int num, int order, int order2, ubyte *norm, int file)
801 if (order2 < 0x0f) i += norm[i];
805 for (k = 0; i < num || k == order || k == order2; k++) {
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]);
813 factor[i] = static_cast<int>(f);
814 f *= subfactor(norm[i], n);
823 static void set_norm_piece(struct TBEntry_piece *ptr, ubyte *norm, ubyte *pieces)
827 for (i = 0; i < ptr->num; i++)
830 switch (ptr->enc_type) {
838 norm[0] = ubyte(ptr->enc_type - 1);
842 for (i = norm[0]; i < ptr->num; i += norm[i])
843 for (j = i; j < ptr->num && pieces[j] == pieces[i]; j++)
847 static void set_norm_pawn(struct TBEntry_pawn *ptr, ubyte *norm, ubyte *pieces)
851 for (i = 0; i < ptr->num; i++)
854 norm[0] = ptr->pawns[0];
855 if (ptr->pawns[1]) norm[ptr->pawns[0]] = ptr->pawns[1];
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++)
862 static void setup_pieces_piece(struct TBEntry_piece *ptr, unsigned char *data, uint64 *tb_size)
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);
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);
880 static void setup_pieces_piece_dtz(struct DTZEntry_piece *ptr, unsigned char *data, uint64 *tb_size)
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);
892 static void setup_pieces_pawn(struct TBEntry_pawn *ptr, unsigned char *data, uint64 *tb_size, int f)
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);
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);
913 static void setup_pieces_pawn_dtz(struct DTZEntry_pawn *ptr, unsigned char *data, uint64 *tb_size, int f)
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);
927 static void calc_symlen(struct PairsData *d, int s, char *tmp)
931 ubyte* w = d->sympat + 3 * s;
932 s2 = (w[2] << 4) | (w[1] >> 4);
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);
944 ushort ReadUshort(ubyte* d) {
945 return ushort(d[0] | (d[1] << 8));
948 uint32 ReadUint32(ubyte* d) {
949 return d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24);
952 static struct PairsData *setup_pairs(unsigned char *data, uint64 tb_size, uint64 *size, unsigned char **next, ubyte *flags, int wdl)
958 if (data[0] & 0x80) {
959 d = (struct PairsData *)malloc(sizeof(struct PairsData));
962 d->min_len = data[1];
966 size[0] = size[1] = size[2] = 0;
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)];
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;
992 // char tmp[num_syms];
994 for (i = 0; i < num_syms; i++)
996 for (i = 0; i < num_syms; i++)
998 calc_symlen(d, i, tmp);
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);
1006 d->offset -= d->min_len;
1011 static int init_table_wdl(struct TBEntry *entry, char *str)
1019 // first mmap the table into memory
1021 entry->data = map_file(str, WDLSUFFIX, &entry->mapping);
1023 printf("Could not find %s" WDLSUFFIX, str);
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);
1038 int split = data[4] & 0x01;
1039 int files = data[4] & 0x02 ? 4 : 1;
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;
1049 ptr->precomp[0] = setup_pairs(data, tb_size[0], &size[0], &next, &flags, 1);
1052 ptr->precomp[1] = setup_pairs(data, tb_size[1], &size[3], &next, &flags, 1);
1055 ptr->precomp[1] = NULL;
1057 ptr->precomp[0]->indextable = (char *)data;
1060 ptr->precomp[1]->indextable = (char *)data;
1064 ptr->precomp[0]->sizetable = (ushort *)data;
1067 ptr->precomp[1]->sizetable = (ushort *)data;
1071 data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1072 ptr->precomp[0]->data = data;
1075 data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1076 ptr->precomp[1]->data = data;
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;
1085 data += ((uintptr_t)data) & 0x01;
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);
1091 ptr->file[f].precomp[1] = setup_pairs(data, tb_size[2 * f + 1], &size[6 * f + 3], &next, &flags, 1);
1094 ptr->file[f].precomp[1] = NULL;
1097 for (f = 0; f < files; f++) {
1098 ptr->file[f].precomp[0]->indextable = (char *)data;
1099 data += size[6 * f];
1101 ptr->file[f].precomp[1]->indextable = (char *)data;
1102 data += size[6 * f + 3];
1106 for (f = 0; f < files; f++) {
1107 ptr->file[f].precomp[0]->sizetable = (ushort *)data;
1108 data += size[6 * f + 1];
1110 ptr->file[f].precomp[1]->sizetable = (ushort *)data;
1111 data += size[6 * f + 4];
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];
1120 data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1121 ptr->file[f].precomp[1]->data = data;
1122 data += size[6 * f + 5];
1130 static int init_table_dtz(struct TBEntry *entry)
1132 ubyte *data = (ubyte *)entry->data;
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");
1149 int files = data[4] & 0x02 ? 4 : 1;
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;
1159 ptr->precomp = setup_pairs(data, tb_size[0], &size[0], &next, &(ptr->flags), 0);
1163 if (ptr->flags & 2) {
1165 for (i = 0; i < 4; i++) {
1166 ptr->map_idx[i] = static_cast<ushort>(data + 1 - ptr->map);
1167 data += 1 + data[0];
1169 data += ((uintptr_t)data) & 0x01;
1172 ptr->precomp->indextable = (char *)data;
1175 ptr->precomp->sizetable = (ushort *)data;
1178 data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1179 ptr->precomp->data = data;
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;
1188 data += ((uintptr_t)data) & 0x01;
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);
1196 for (f = 0; f < files; f++) {
1197 if (ptr->flags[f] & 2) {
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];
1205 data += ((uintptr_t)data) & 0x01;
1207 for (f = 0; f < files; f++) {
1208 ptr->file[f].precomp->indextable = (char *)data;
1209 data += size[3 * f];
1212 for (f = 0; f < files; f++) {
1213 ptr->file[f].precomp->sizetable = (ushort *)data;
1214 data += size[3 * f + 1];
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];
1227 template<bool LittleEndian>
1228 static ubyte decompress_pairs(struct PairsData *d, uint64 idx)
1231 return ubyte(d->min_len);
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);
1237 block = BSWAP32(block);
1239 ushort idxOffset = *(ushort *)(d->indextable + 6 * mainidx + 4);
1241 idxOffset = ushort((idxOffset << 8) | (idxOffset >> 8));
1242 litidx += idxOffset;
1246 litidx += d->sizetable[--block] + 1;
1247 } while (litidx < 0);
1249 while (litidx > d->sizetable[block])
1250 litidx -= d->sizetable[block++] + 1;
1253 uint32 *ptr = (uint32 *)(d->data + (block << d->blocksize));
1256 ushort *offset = d->offset;
1257 base_t *base = d->base - m;
1258 ubyte *symlen = d->symlen;
1261 uint64 code = *((uint64 *)ptr);
1263 code = BSWAP64(code);
1266 bitcnt = 0; // number of "empty bits" in code
1269 while (code < base[l]) l++;
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;
1280 uint32 tmp = *ptr++;
1283 code |= ((uint64)tmp) << bitcnt;
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)
1294 litidx -= (int)symlen[s1] + 1;
1295 sym = (w[2] << 4) | (w[1] >> 4);
1299 return sympat[3 * sym];
1302 void load_dtz_table(char *str, uint64 key1, uint64 key2)
1305 struct TBEntry *ptr, *ptr3;
1306 struct TBHashEntry *ptr2;
1308 DTZ_table[0].key1 = key1;
1309 DTZ_table[0].key2 = key2;
1310 DTZ_table[0].entry = NULL;
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;
1319 ptr3 = (struct TBEntry *)malloc(ptr->has_pawns
1320 ? sizeof(struct DTZEntry_pawn)
1321 : sizeof(struct DTZEntry_piece));
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];
1333 struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr3;
1334 entry->enc_type = ((struct TBEntry_piece *)ptr)->enc_type;
1336 if (!init_table_dtz(ptr3))
1339 DTZ_table[0].entry = ptr3;
1342 static void free_wdl_entry(struct TBEntry *entry)
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]);
1351 struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
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]);
1361 static void free_dtz_entry(struct TBEntry *entry)
1363 unmap_file(entry->data, entry->mapping);
1364 if (!entry->has_pawns) {
1365 struct DTZEntry_piece *ptr = (struct DTZEntry_piece *)entry;
1368 struct DTZEntry_pawn *ptr = (struct DTZEntry_pawn *)entry;
1370 for (f = 0; f < 4; f++)
1371 free(ptr->file[f].precomp);
1376 static int wdl_to_map[5] = { 1, 3, 0, 2, 0 };
1377 static ubyte pa_flags[5] = { 8, 0, 0, 0, 4 };