Files
R8VeritasCC-fork/tests/r8_test.cc
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

114 lines
3.1 KiB
C++

#include "r8veritas.hh"
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using problem_t = r8veritas<6>;
static problem_t::cell func_copy(problem_t::cell inp) {
const unsigned A = inp & 0b1;
return problem_t::cell((A << 1) | A);
}
static problem_t::cell func_clb_and(problem_t::cell inp) {
bool A = inp & 0b1;
bool B = inp & 0b10;
return (A & B) << 2;
}
static problem_t::cell func_clb_half_add(problem_t::cell inp) {
bool A = inp & 0b1;
bool B = inp & 0b10;
return ((A ^ B) << 1) | (A & B);
}
static problem_t::cell func_half_add(problem_t::cell inp) {
bool A = inp & 0b1;
bool B = inp & 0b10;
return ((A ^ B) << 3) | ((A & B) << 2) | (inp & 0b11);
}
static problem_t::cell func_full_add_Co(problem_t::cell inp) {
bool A = inp & 0b1;
bool B = inp & 0b10;
bool C = inp & 0b100;
bool Co = (A & B) | (A & C) | (B & C);
return (Co << 4) | (inp & 0b111);
}
static problem_t::cell func_full_add_S(problem_t::cell inp) {
bool A = inp & 0b1;
bool B = inp & 0b10;
bool C = inp & 0b100;
bool S = A ^ B ^ C;
return (S << 3) | (inp & 0b111);
}
static problem_t::cell func_full_add(problem_t::cell inp) {
bool A = inp & 0b1;
bool B = inp & 0b10;
bool C = inp & 0b100;
bool S = A ^ B ^ C;
bool Co = (A & B) | (A & C) | (B & C);
return (Co << 4) | (S << 3) | (inp & 0b111);
}
struct problem {
const char *name;
problem_t::op fn;
};
int main(int argc, char **argv) {
const int max_depth = argc > 1 ? std::atoi(argv[1]) : 5;
const bool verbose = argc > 2 ? std::atoi(argv[2]) != 0 : false;
std::vector<problem> problems = {
{"copy", func_copy},
{"clb_and", func_clb_and},
{"clb_half_add", func_clb_half_add},
{"half_add", func_half_add},
{"full_add_S", func_full_add_S},
{"full_add_Co", func_full_add_Co},
{"full_add", func_full_add},
};
for (const auto &p : problems) {
problem_t problem_obj;
problem_obj.initialize_nicknames();
problem_obj.initialize_tp_paths();
auto raw = problem_obj.generate_truthtable(p.fn);
auto compressed = problem_obj.compress_stat_space(raw);
problem_t::options opt;
opt.max_depth = max_depth;
opt.verbose = verbose;
auto res = problem_obj.solve(compressed, opt);
std::cout << "==== " << p.name << "\n";
if (!res.found) {
std::cout << " no program of length <= " << max_depth << " ("
<< res.states << " states, " << res.seconds << "s) "
<< res.message << "\n\n";
continue;
}
const bool ok = problem_obj.run_program(compressed, res.program);
std::cout << " length " << res.program.size()
<< (res.proven_optimal ? " (proven shortest)" : " (unproven)")
<< " " << res.states << " states, " << res.seconds << "s"
<< " replay: " << (ok ? "ok" : "MISMATCH") << "\n ";
problem_obj.print_program(res.program, std::cout, true);
std::cout << "\n";
if (std::string(p.name) == "full_add") {
std::cout << " r8asm:\n";
for (const auto &i : res.program) {
problem_obj.output_ins(i, std::cout, false);
std::cout << "\n";
}
}
}
return (0);
}