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