+#include "memory.h"
+#include "misc.h"
+#include "syzygy/tbprobe.h"
+#include "thread.h"
+
+namespace Stockfish {
+
+
+// TTEntry struct is the 10 bytes transposition table entry, defined as below:
+//
+// key 16 bit
+// depth 8 bit
+// generation 5 bit
+// pv node 1 bit
+// bound type 2 bit
+// move 16 bit
+// value 16 bit
+// evaluation 16 bit
+//
+// These fields are in the same order as accessed by TT::probe(), since memory is fastest sequentially.
+// Equally, the store order in save() matches this order.
+
+struct TTEntry {
+
+ // Convert internal bitfields to external types
+ TTData read() const {
+ return TTData{Move(move16), Value(value16),
+ Value(eval16), Depth(depth8 + DEPTH_ENTRY_OFFSET),
+ Bound(genBound8 & 0x3), bool(genBound8 & 0x4)};
+ }
+
+ bool is_occupied() const;
+ void save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev, uint8_t generation8);
+ // The returned age is a multiple of TranspositionTable::GENERATION_DELTA
+ uint8_t relative_age(const uint8_t generation8) const;
+
+ private:
+ friend class TranspositionTable;
+
+ uint16_t key16;
+ uint8_t depth8;
+ uint8_t genBound8;
+ Move move16;
+ int16_t value16;
+ int16_t eval16;
+};
+
+// `genBound8` is where most of the details are. We use the following constants to manipulate 5 leading generation bits
+// and 3 trailing miscellaneous bits.
+
+// These bits are reserved for other things.
+static constexpr unsigned GENERATION_BITS = 3;
+// increment for generation field
+static constexpr int GENERATION_DELTA = (1 << GENERATION_BITS);
+// cycle length
+static constexpr int GENERATION_CYCLE = 255 + GENERATION_DELTA;
+// mask to pull out generation number
+static constexpr int GENERATION_MASK = (0xFF << GENERATION_BITS) & 0xFF;
+
+// DEPTH_ENTRY_OFFSET exists because 1) we use `bool(depth8)` as the occupancy check, but
+// 2) we need to store negative depths for QS. (`depth8` is the only field with "spare bits":
+// we sacrifice the ability to store depths greater than 1<<8 less the offset, as asserted in `save`.)
+bool TTEntry::is_occupied() const { return bool(depth8); }
+
+// Populates the TTEntry with a new node's data, possibly
+// overwriting an old position. The update is not atomic and can be racy.
+void TTEntry::save(
+ Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev, uint8_t generation8) {
+
+ // Preserve the old ttmove if we don't have a new one
+ if (m || uint16_t(k) != key16)
+ move16 = m;
+
+ // Overwrite less valuable entries (cheapest checks first)
+ if (b == BOUND_EXACT || uint16_t(k) != key16 || d - DEPTH_ENTRY_OFFSET + 2 * pv > depth8 - 4
+ || relative_age(generation8))
+ {
+ assert(d > DEPTH_ENTRY_OFFSET);
+ assert(d < 256 + DEPTH_ENTRY_OFFSET);
+
+ key16 = uint16_t(k);
+ depth8 = uint8_t(d - DEPTH_ENTRY_OFFSET);
+ genBound8 = uint8_t(generation8 | uint8_t(pv) << 2 | b);
+ value16 = int16_t(v);
+ eval16 = int16_t(ev);
+ }
+}
+
+
+uint8_t TTEntry::relative_age(const uint8_t generation8) const {
+ // Due to our packed storage format for generation and its cyclic
+ // nature we add GENERATION_CYCLE (256 is the modulus, plus what
+ // is needed to keep the unrelated lowest n bits from affecting
+ // the result) to calculate the entry age correctly even after
+ // generation8 overflows into the next cycle.
+ return (GENERATION_CYCLE + generation8 - genBound8) & GENERATION_MASK;
+}
+
+
+// TTWriter is but a very thin wrapper around the pointer
+TTWriter::TTWriter(TTEntry* tte) :
+ entry(tte) {}
+
+void TTWriter::write(
+ Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev, uint8_t generation8) {
+ entry->save(k, v, pv, b, d, m, ev, generation8);
+}