+// Numbers in little-endian used by sparseIndex[] to point into blockLength[]
+struct SparseEntry {
+ char block[4]; // Number of block
+ char offset[2]; // Offset within the block
+};
+
+static_assert(sizeof(SparseEntry) == 6, "SparseEntry must be 6 bytes");
+
+using Sym = uint16_t; // Huffman symbol
+
+struct LR {
+ enum Side {
+ Left,
+ Right
+ };
+
+ uint8_t lr[3]; // The first 12 bits is the left-hand symbol, the second 12
+ // bits is the right-hand symbol. If the symbol has length 1,
+ // then the left-hand symbol is the stored value.
+ template<Side S>
+ Sym get() {
+ return S == Left ? ((lr[1] & 0xF) << 8) | lr[0]
+ : S == Right ? (lr[2] << 4) | (lr[1] >> 4)
+ : (assert(false), Sym(-1));
+ }
+};
+
+static_assert(sizeof(LR) == 3, "LR tree entry must be 3 bytes");
+
+// Tablebases data layout is structured as following:
+//
+// TBFile: memory maps/unmaps the physical .rtbw and .rtbz files
+// TBTable: one object for each file with corresponding indexing information
+// TBTables: has ownership of TBTable objects, keeping a list and a hash
+
+// class TBFile memory maps/unmaps the single .rtbw and .rtbz files. Files are
+// memory mapped for best performance. Files are mapped at first access: at init
+// time only existence of the file is checked.
+class TBFile: public std::ifstream {
+
+ std::string fname;
+
+ public:
+ // Look for and open the file among the Paths directories where the .rtbw
+ // and .rtbz files can be found. Multiple directories are separated by ";"
+ // on Windows and by ":" on Unix-based operating systems.
+ //
+ // Example:
+ // C:\tb\wdl345;C:\tb\wdl6;D:\tb\dtz345;D:\tb\dtz6
+ static std::string Paths;
+
+ TBFile(const std::string& f) {
+
+#ifndef _WIN32
+ constexpr char SepChar = ':';
+#else
+ constexpr char SepChar = ';';
+#endif
+ std::stringstream ss(Paths);
+ std::string path;
+
+ while (std::getline(ss, path, SepChar))
+ {
+ fname = path + "/" + f;
+ std::ifstream::open(fname);
+ if (is_open())
+ return;
+ }
+ }
+
+ // Memory map the file and check it.
+ uint8_t* map(void** baseAddress, uint64_t* mapping, TBType type) {
+ if (is_open())
+ close(); // Need to re-open to get native file descriptor
+
+#ifndef _WIN32
+ struct stat statbuf;
+ int fd = ::open(fname.c_str(), O_RDONLY);
+
+ if (fd == -1)
+ return *baseAddress = nullptr, nullptr;
+
+ fstat(fd, &statbuf);
+
+ if (statbuf.st_size % 64 != 16)
+ {
+ std::cerr << "Corrupt tablebase file " << fname << std::endl;
+ exit(EXIT_FAILURE);
+ }
+
+ *mapping = statbuf.st_size;
+ *baseAddress = mmap(nullptr, statbuf.st_size, PROT_READ, MAP_SHARED, fd, 0);
+ #if defined(MADV_RANDOM)
+ madvise(*baseAddress, statbuf.st_size, MADV_RANDOM);
+ #endif
+ ::close(fd);
+
+ if (*baseAddress == MAP_FAILED)
+ {
+ std::cerr << "Could not mmap() " << fname << std::endl;
+ exit(EXIT_FAILURE);
+ }
+#else
+ // Note FILE_FLAG_RANDOM_ACCESS is only a hint to Windows and as such may get ignored.
+ HANDLE fd = CreateFileA(fname.c_str(), GENERIC_READ, FILE_SHARE_READ, nullptr,
+ OPEN_EXISTING, FILE_FLAG_RANDOM_ACCESS, nullptr);
+
+ if (fd == INVALID_HANDLE_VALUE)
+ return *baseAddress = nullptr, nullptr;
+
+ DWORD size_high;
+ DWORD size_low = GetFileSize(fd, &size_high);
+
+ if (size_low % 64 != 16)
+ {
+ std::cerr << "Corrupt tablebase file " << fname << std::endl;
+ exit(EXIT_FAILURE);
+ }
+
+ HANDLE mmap = CreateFileMapping(fd, nullptr, PAGE_READONLY, size_high, size_low, nullptr);
+ CloseHandle(fd);
+
+ if (!mmap)
+ {
+ std::cerr << "CreateFileMapping() failed" << std::endl;
+ exit(EXIT_FAILURE);
+ }
+
+ *mapping = uint64_t(mmap);
+ *baseAddress = MapViewOfFile(mmap, FILE_MAP_READ, 0, 0, 0);
+
+ if (!*baseAddress)
+ {
+ std::cerr << "MapViewOfFile() failed, name = " << fname
+ << ", error = " << GetLastError() << std::endl;
+ exit(EXIT_FAILURE);
+ }
+#endif
+ uint8_t* data = (uint8_t*) *baseAddress;
+
+ constexpr uint8_t Magics[][4] = {{0xD7, 0x66, 0x0C, 0xA5}, {0x71, 0xE8, 0x23, 0x5D}};
+
+ if (memcmp(data, Magics[type == WDL], 4))
+ {
+ std::cerr << "Corrupted table in file " << fname << std::endl;
+ unmap(*baseAddress, *mapping);
+ return *baseAddress = nullptr, nullptr;
+ }
+
+ return data + 4; // Skip Magics's header
+ }
+
+ static void unmap(void* baseAddress, uint64_t mapping) {
+
+#ifndef _WIN32
+ munmap(baseAddress, mapping);
+#else
+ UnmapViewOfFile(baseAddress);
+ CloseHandle((HANDLE) mapping);
+#endif
+ }
+};
+
+std::string TBFile::Paths;
+
+// struct PairsData contains low-level indexing information to access TB data.
+// There are 8, 4, or 2 PairsData records for each TBTable, according to the type
+// of table and if positions have pawns or not. It is populated at first access.
+struct PairsData {
+ uint8_t flags; // Table flags, see enum TBFlag
+ uint8_t maxSymLen; // Maximum length in bits of the Huffman symbols
+ uint8_t minSymLen; // Minimum length in bits of the Huffman symbols
+ uint32_t blocksNum; // Number of blocks in the TB file
+ size_t sizeofBlock; // Block size in bytes
+ size_t span; // About every span values there is a SparseIndex[] entry
+ Sym* lowestSym; // lowestSym[l] is the symbol of length l with the lowest value
+ LR* btree; // btree[sym] stores the left and right symbols that expand sym
+ uint16_t* blockLength; // Number of stored positions (minus one) for each block: 1..65536
+ uint32_t blockLengthSize; // Size of blockLength[] table: padded so it's bigger than blocksNum
+ SparseEntry* sparseIndex; // Partial indices into blockLength[]
+ size_t sparseIndexSize; // Size of SparseIndex[] table
+ uint8_t* data; // Start of Huffman compressed data
+ std::vector<uint64_t>
+ base64; // base64[l - min_sym_len] is the 64bit-padded lowest symbol of length l
+ std::vector<uint8_t>
+ symlen; // Number of values (-1) represented by a given Huffman symbol: 1..256
+ Piece pieces[TBPIECES]; // Position pieces: the order of pieces defines the groups
+ uint64_t groupIdx[TBPIECES + 1]; // Start index used for the encoding of the group's pieces
+ int groupLen[TBPIECES + 1]; // Number of pieces in a given group: KRKN -> (3, 1)
+ uint16_t map_idx[4]; // WDLWin, WDLLoss, WDLCursedWin, WDLBlessedLoss (used in DTZ)
+};
+
+// struct TBTable contains indexing information to access the corresponding TBFile.
+// There are 2 types of TBTable, corresponding to a WDL or a DTZ file. TBTable
+// is populated at init time but the nested PairsData records are populated at
+// first access, when the corresponding file is memory mapped.
+template<TBType Type>
+struct TBTable {
+ using Ret = std::conditional_t<Type == WDL, WDLScore, int>;
+
+ static constexpr int Sides = Type == WDL ? 2 : 1;
+
+ std::atomic_bool ready;
+ void* baseAddress;
+ uint8_t* map;
+ uint64_t mapping;
+ Key key;
+ Key key2;
+ int pieceCount;
+ bool hasPawns;
+ bool hasUniquePieces;
+ uint8_t pawnCount[2]; // [Lead color / other color]
+ PairsData items[Sides][4]; // [wtm / btm][FILE_A..FILE_D or 0]
+
+ PairsData* get(int stm, int f) { return &items[stm % Sides][hasPawns ? f : 0]; }
+
+ TBTable() :
+ ready(false),
+ baseAddress(nullptr) {}
+ explicit TBTable(const std::string& code);
+ explicit TBTable(const TBTable<WDL>& wdl);
+
+ ~TBTable() {
+ if (baseAddress)
+ TBFile::unmap(baseAddress, mapping);
+ }
+};
+
+template<>
+TBTable<WDL>::TBTable(const std::string& code) :
+ TBTable() {
+
+ StateInfo st;
+ Position pos;
+
+ key = pos.set(code, WHITE, &st).material_key();
+ pieceCount = pos.count<ALL_PIECES>();
+ hasPawns = pos.pieces(PAWN);
+
+ hasUniquePieces = false;
+ for (Color c : {WHITE, BLACK})
+ for (PieceType pt = PAWN; pt < KING; ++pt)
+ if (popcount(pos.pieces(c, pt)) == 1)
+ hasUniquePieces = true;
+
+ // Set the leading color. In case both sides have pawns the leading color
+ // is the side with fewer pawns because this leads to better compression.
+ bool c = !pos.count<PAWN>(BLACK)
+ || (pos.count<PAWN>(WHITE) && pos.count<PAWN>(BLACK) >= pos.count<PAWN>(WHITE));
+
+ pawnCount[0] = pos.count<PAWN>(c ? WHITE : BLACK);
+ pawnCount[1] = pos.count<PAWN>(c ? BLACK : WHITE);
+
+ key2 = pos.set(code, BLACK, &st).material_key();