Files
R8VeritasCC-fork/include/r8veritas.hh
starcells e632fb4824 Rewrite the searcher: bit planes, and the last block searched backwards
The BFS used to walk the whole 1<<CELL_SIZE table for every edge, keep the
states in an unordered_set and the parents in a second unordered_map.  For
the six plane full adder layer 4 is 642729 states, and layer 5 never
finished (75s, heading for GBs).

A state is now CELL_SIZE bit planes, each a truth table over only the
inputs that influence the answer, so a state is CELL_SIZE * 2^K bits --
48 bits for every adder-shaped problem -- and a block is a handful of
64-bit ops.  The instruction list also lost its duplicated encodings
(378 instead of 762 for six planes).

The bigger win is not expanding the last layer at all.  A block clears its
own plane, so for the goal to be its target goal[s] must be 0; the
preimages of the goal under each such block are enumerated exactly and
looked up in the BFS table.  For full_add that is 9.3e3 lookups instead of
7.4e9 edges, which turns "unreachable" into "5 blocks, proven shortest,
7 seconds".

Results (r8veritas<6>, max_depth 5, MSVC /O2):

    copy          2   33 states
    clb_and       3   3398
    clb_half_add  4   32898
    half_add      4   32898
    full_add_S    4   656528
    full_add_Co   5   20388515
    full_add      5   20388515      7.2s

All of those lengths are proven minimal, and the old bit_raw_add needed
eight blocks for the same slice.

Richer instruction sets were tried as well -- per destination OR/XOR, and
adding set_0 on top (6144 blocks) -- and neither admits a four-block full
adder, so five is not an artifact of the model.

CELL_SIZE stays a template parameter; the truth table compression picks K
at run time and dispatches on it.  CMake flags got the same fix as r8asm:
stop clobbering CMAKE_CXX_FLAGS so Debug keeps /RTC1 and MSVC keeps /EHsc.
2026-11-05 23:35:56 +08:00

538 lines
17 KiB
C++

#ifndef R8VERITAS
#define R8VERITAS
// R8Veritas -- shortest program search over the rot-8 "sacrifice block":
//
// .tp s
// biz
// .tp b ; once per b in the mask
// set_1 / flb ; OR / XOR
// .tp s
// flb
// rnz
//
// A state is the whole truth table of the working cell: for every input
// combination, what the cell holds. Written as bit planes -- plane b is bit
// b of the cell, over all inputs -- one block becomes a handful of 64-bit
// operations:
//
// cond = plane[s]; plane[s] = 0;
// for b in mask: plane[b] |= cond (set_1)
// plane[b] ^= cond (flb)
//
// Search strategy:
// * only the input bits that influence the answer survive (the old
// compress_stat_space), so a plane is a 2^K bit truth table instead of
// 2^CELL_SIZE, and the whole state is CELL_SIZE * 2^K bits
// * forward BFS keeps every reachable state of depth < d plus the block
// that produced it
// * the last block is not searched forward. A block clears its own
// plane, so the goal can only be its target if goal[s] == 0; for each
// such block every preimage of the goal is generated and looked up in
// the BFS table. A hit is the shortest program, and "nothing below d,
// something at d" is a proof.
//
// The backward step enumerates 2^K values of the condition, so it is only
// used while K <= 3; above that the last layer is expanded forward like the
// others (still a lot cheaper than the old implementation).
#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <optional>
#include <ostream>
#include <set>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>
template <int CELL_SIZE> class r8veritas {
public:
using cell = uint8_t;
using stat = std::array<cell, (size_t(1) << CELL_SIZE)>;
using stat_ref = const stat *;
using truthtable = std::pair<stat_ref, stat_ref>;
using op = std::function<cell(cell)>;
// one biz block
struct instruction {
uint8_t sacrifice = 0; // plane whose bit is tested and cleared
uint8_t mask = 0; // bit b set: plane b is a destination
bool or_mode = false; // true: set_1 (|), false: flb (^)
};
struct options {
int max_depth = 5; // longest program to look for
size_t max_states = 80'000'000; // memory guard
bool verbose = false;
};
struct result {
bool found = false;
// true when every program shorter than program.size() was ruled out
bool proven_optimal = false;
std::vector<instruction> program;
size_t states = 0; // states kept by the BFS
int depth_reached = 0; // deepest layer fully expanded
double seconds = 0;
std::string message;
};
std::array<std::string, CELL_SIZE> nicknames;
std::array<std::string, CELL_SIZE> tp_paths;
void initialize_nicknames() {
for (int i = 0; i < CELL_SIZE; i++)
nicknames[i] = "%" + std::to_string(i + 1);
}
void initialize_tp_paths() {
for (int i = 0; i < CELL_SIZE; i++)
tp_paths[i] = ".tp " + nicknames[i];
}
// ---------------------------------------------------------------- states
stat_ref generate_empty_stat() {
stat arr{};
arr.fill(0);
return keep(arr);
}
truthtable generate_truthtable(const op &operation) {
stat in{}, out{};
for (size_t i = 0; i < (size_t(1) << CELL_SIZE); i++) {
in[i] = cell(i);
out[i] = operation(cell(i));
}
return {keep(in), keep(out)};
}
// Clears the input bits that never influence the answer, so the search
// starts from a canonical state.
truthtable compress_stat_space(const truthtable &raw) {
stat start = *raw.first;
for (int i = 0; i < CELL_SIZE; i++) {
bool influences = false;
for (size_t j = 0; j < (size_t(1) << CELL_SIZE); j++)
if ((*raw.second)[j] != (*raw.second)[j ^ (size_t(1) << i)])
influences = true;
if (!influences)
for (size_t j = 0; j < (size_t(1) << CELL_SIZE); j++)
start[j] = cell(start[j] & ~(1u << i));
}
return {keep(start), raw.second};
}
// Applies a program with the reference semantics (one state at a time) and
// tells whether it lands on the target.
bool run_program(const truthtable &raw, const std::vector<instruction> &p,
bool verbose = false) const {
stat cur = *raw.first;
for (const auto &i : p) {
for (size_t j = 0; j < cur.size(); j++)
if (cur[j] & (1u << i.sacrifice)) {
cur[j] = cell(cur[j] & ~(1u << i.sacrifice));
for (int b = 0; b < CELL_SIZE; b++)
if (i.mask & (1 << b))
cur[j] = i.or_mode ? cell(cur[j] | (1u << b))
: cell(cur[j] ^ (1u << b));
}
if (verbose) {
output_stat(cur);
std::cout << "\n";
}
}
return cur == *raw.second;
}
// ---------------------------------------------------------------- output
void output_stat(const stat &s) const {
for (auto v : s)
std::cout << std::bitset<CELL_SIZE>(v).to_string() << " ";
}
void output_ins(const instruction &ins, std::ostream &os,
bool debug_output = true) const {
if (debug_output) {
os << "SACRIFICE: " << int(ins.sacrifice);
if (ins.mask) {
os << (ins.or_mode ? ", SET1: {" : ", FLIP: {");
bool first = true;
for (int b = 0; b < CELL_SIZE; b++)
if (ins.mask & (1 << b)) {
if (!first)
os << ',';
os << b;
first = false;
}
os << '}';
}
os << ';';
return;
}
os << tp_paths[ins.sacrifice] << "\n";
os << "biz\n";
for (int b = 0; b < CELL_SIZE; b++)
if (ins.mask & (1 << b)) {
os << '\t' << tp_paths[b] << "\n";
os << '\t' << (ins.or_mode ? "set_1" : "flb") << "\n";
}
os << '\t' << tp_paths[ins.sacrifice] << "\n";
os << "\tflb\n";
os << "rnz\n";
}
void print_program(const std::vector<instruction> &p, std::ostream &os,
bool debug_output = false) const {
for (const auto &i : p) {
output_ins(i, os, debug_output);
os << "\n";
}
}
// ---------------------------------------------------------------- search
result solve(const truthtable &raw, const options &opt = {}) {
result r;
const auto t0 = std::chrono::steady_clock::now();
auto finish = [&]() {
r.seconds =
std::chrono::duration<double>(std::chrono::steady_clock::now() - t0)
.count();
return r;
};
// which input bits matter, in compression order
std::array<int, CELL_SIZE> bit_of{};
int k = 0;
for (int i = 0; i < CELL_SIZE; i++) {
for (size_t j = 0; j < (size_t(1) << CELL_SIZE); j++)
if ((*raw.second)[j] != (*raw.second)[j ^ (size_t(1) << i)]) {
bit_of[k++] = i;
break;
}
}
if (k > 6) {
r.message = "the answer depends on more than 6 inputs; the packed state "
"does not fit and the search would be hopeless anyway";
return finish();
}
// compressed index j -> index in the full truth table
std::vector<size_t> full(size_t(1) << k, 0);
for (size_t j = 0; j < full.size(); j++)
for (int b = 0; b < k; b++)
if (j & (size_t(1) << b))
full[j] |= size_t(1) << bit_of[b];
switch (k) {
case 0:
return solve_with<0>(raw, full, opt, r, finish);
case 1:
return solve_with<1>(raw, full, opt, r, finish);
case 2:
return solve_with<2>(raw, full, opt, r, finish);
case 3:
return solve_with<3>(raw, full, opt, r, finish);
case 4:
return solve_with<4>(raw, full, opt, r, finish);
case 5:
return solve_with<5>(raw, full, opt, r, finish);
default:
return solve_with<6>(raw, full, opt, r, finish);
}
}
private:
std::set<stat> pool;
stat_ref keep(const stat &s) { return &*pool.insert(s).first; }
// ---------------------------------------------------------------- engine
// K relevant inputs: every plane is a 2^K bit truth table, the whole state
// is CELL_SIZE * 2^K bits packed into KEYW words.
template <int K> struct engine {
static constexpr int M = 1 << K; // bits per plane
static constexpr int KEYW = (CELL_SIZE * M + 63) / 64;
static constexpr uint64_t PMASK =
(M >= 64) ? ~uint64_t(0) : ((uint64_t(1) << (M & 63)) - 1);
using key = std::array<uint64_t, KEYW>;
static uint64_t get(const key &k, int b) {
const int off = b * M;
return (k[off >> 6] >> (off & 63)) & PMASK;
}
static void put(key &k, int b, uint64_t v) {
const int off = b * M;
k[off >> 6] =
(k[off >> 6] & ~(PMASK << (off & 63))) | ((v & PMASK) << (off & 63));
}
static key zero() {
key k{};
return k;
}
static uint64_t cond(const key &k, const instruction &i) {
return get(k, i.sacrifice);
}
static key step(const key &k, const instruction &i) {
key n = k;
const uint64_t c = get(k, i.sacrifice);
put(n, i.sacrifice, 0);
for (int b = 0; b < CELL_SIZE; b++)
if (i.mask & (1 << b))
put(n, b, i.or_mode ? (get(k, b) | c) : (get(k, b) ^ c));
return n;
}
static uint64_t hash(const key &k) {
uint64_t h = 0xcbf29ce484222325ULL;
for (int i = 0; i < KEYW; i++) {
h ^= k[i];
h *= 0x100000001b3ULL;
h ^= h >> 29;
h *= 0xbf58476d1ce4e5b9ULL;
h ^= h >> 32;
}
return h;
}
struct slot {
key k{};
key parent{};
uint16_t ins = 0xFFFF; // 0xFFFF free, 0xFFFE start of a program
};
struct table {
std::vector<slot> v;
uint64_t mask = 0;
size_t used = 0;
static constexpr uint16_t FREE = 0xFFFF, ROOT = 0xFFFE;
static uint64_t capacity_for(size_t n) {
uint64_t c = 1 << 12;
while (c * 3 < n * 4 + 4)
c <<= 1;
return c;
}
void init(uint64_t cap) {
v.assign(cap, slot{});
mask = cap - 1;
used = 0;
}
void grow() {
std::vector<slot> old = std::move(v);
init(old.size() * 2);
for (const auto &s : old)
if (s.ins != FREE)
insert(s.k, s.parent, s.ins);
}
bool insert(const key &k, const key &parent, uint16_t ins) {
uint64_t j = hash(k) & mask;
while (v[j].ins != FREE) {
if (v[j].k == k)
return false;
j = (j + 1) & mask;
}
v[j].k = k;
v[j].parent = parent;
v[j].ins = ins;
if (++used * 4 > (mask + 1) * 3)
grow();
return true;
}
const slot *find(const key &k) const {
uint64_t j = hash(k) & mask;
while (v[j].ins != FREE) {
if (v[j].k == k)
return &v[j];
j = (j + 1) & mask;
}
return nullptr;
}
};
};
template <int K>
result solve_with(const truthtable &raw, const std::vector<size_t> &full,
const options &opt, result &r,
const std::function<result()> &finish) {
using E = engine<K>;
using table_t = typename E::table;
using key = typename E::key;
constexpr uint16_t ROOT = table_t::ROOT;
const std::vector<instruction> insns = build_instructions();
// start = identity over the compressed inputs, goal = the target
key start = E::zero(), goal = E::zero();
for (size_t j = 0; j < full.size(); j++)
for (int b = 0; b < CELL_SIZE; b++) {
if (j & (size_t(1) << b))
E::put(start, b, E::get(start, b) | (uint64_t(1) << j));
if ((*raw.second)[full[j]] & (1u << b))
E::put(goal, b, E::get(goal, b) | (uint64_t(1) << j));
}
table_t tab;
tab.init(table_t::capacity_for(1 << 16));
tab.insert(start, E::zero(), ROOT);
std::vector<key> frontier{start};
auto path_to = [&](const key &k, int extra) {
std::vector<instruction> p;
if (extra >= 0)
p.push_back(insns[size_t(extra)]);
key cur = k;
while (true) {
const auto *s = tab.find(cur);
if (s == nullptr || s->ins == ROOT)
break;
p.push_back(insns[s->ins]);
cur = s->parent;
}
std::reverse(p.begin(), p.end());
return p;
};
if (start == goal) {
r.found = r.proven_optimal = true;
return finish();
}
for (int d = 1; d <= opt.max_depth; d++) {
// ---- close the last block: enumerate the goal's preimages ----
// Only worth it while 2^K is small enough to walk every condition.
if (K <= 3) {
for (uint16_t ii = 0; ii < insns.size(); ii++) {
const instruction &i = insns[ii];
if (E::get(goal, i.sacrifice) != 0)
continue; // the block clears its own plane
for (uint64_t c = 1; c <= E::PMASK; c++) {
bool hit = false;
for_each_preimage<E>(
goal, i, c, [&](const key &p) {
if (tab.find(p) != nullptr) {
r.program = path_to(p, int(ii));
r.found = true;
r.proven_optimal = true;
hit = true;
return true;
}
return false;
});
if (hit)
return finish();
}
}
// the backward step has covered this length already
if (d == opt.max_depth)
break;
}
// ---- expand the BFS by one layer ----
std::vector<key> next;
next.reserve(frontier.size());
for (const auto &k : frontier) {
for (uint16_t ii = 0; ii < insns.size(); ii++) {
if (E::cond(k, insns[ii]) == 0)
continue; // nothing to sacrifice, the block would do nothing
key n = E::step(k, insns[ii]);
if (n == goal) {
r.program = path_to(k, int(ii));
r.found = true;
r.proven_optimal = true;
r.states = tab.used;
r.depth_reached = d;
return finish();
}
if (tab.insert(n, k, ii))
next.push_back(n);
}
if (tab.used > opt.max_states) {
r.message = "state budget exhausted: the search is not complete";
r.states = tab.used;
r.depth_reached = d;
return finish();
}
}
r.states = tab.used;
r.depth_reached = d;
if (opt.verbose)
std::cout << " depth " << d << ": " << next.size() << " new, "
<< tab.used << " kept\n";
frontier.swap(next);
}
r.proven_optimal = (r.message.empty());
if (r.message.empty())
r.message = "no program of length <= " + std::to_string(opt.max_depth);
return finish();
}
// Calls f on every preimage of `post` under `ins` with condition `c`.
// XOR destinations are forced, OR destinations are free on the bits of c
// they contain, so walk the destinations and branch where needed.
template <class E, class F>
static bool for_each_preimage(const typename E::key &post,
const instruction &ins, uint64_t c, F &&f) {
using key = typename E::key;
key pre = post;
E::put(pre, ins.sacrifice, c);
return preimage_walk<E>(post, ins, c, pre, 0, f);
}
template <class E, class F>
static bool preimage_walk(const typename E::key &post,
const instruction &ins, uint64_t c,
typename E::key pre, int b, F &f) {
using key = typename E::key;
for (; b < CELL_SIZE; b++)
if (ins.mask & (1 << b))
break;
if (b == CELL_SIZE)
return f(pre);
const uint64_t T = E::get(post, b);
if (!ins.or_mode) {
E::put(pre, b, T ^ c);
return preimage_walk<E>(post, ins, c, pre, b + 1, f);
}
if ((T & c) != c)
return false; // a destination bit can only be set, not cleared
const uint64_t fixed = T & ~c, free = T & c;
for (uint64_t sub = free;; sub = (sub - 1) & free) {
E::put(pre, b, fixed | sub);
if (preimage_walk<E>(post, ins, c, pre, b + 1, f))
return true;
if (sub == 0)
break;
}
return false;
}
// ---------------------------------------------------------------- syntax
std::vector<instruction> build_instructions() const {
std::vector<instruction> out;
out.reserve(CELL_SIZE * (2 * (1 << (CELL_SIZE - 1)) + 1));
for (int s = 0; s < CELL_SIZE; s++) {
out.push_back({uint8_t(s), 0, false}); // pure sacrifice: clear plane s
for (int sub = 1; sub < (1 << (CELL_SIZE - 1)); sub++) {
uint8_t m = 0;
int bit = 0;
for (int b = 0; b < CELL_SIZE; b++)
if (b != s)
m |= uint8_t(((sub >> bit++) & 1) << b);
out.push_back({uint8_t(s), m, false});
out.push_back({uint8_t(s), m, true});
}
}
return out;
}
};
#endif