Files
R8Forge/include/r8forge/r8veritas_phase_tt.hh
dsh da16c111cf Add a layout independent metric so a result can be cached and reused
%synth could optimise the real tape characters, but that price depends on where
the cells sit, so the answer was only good for one layout and the cache could
only be shared between call sites with the same addresses.

  metric chars   tape characters including the .tp walk   layout dependent
  metric flat    characters without the walk             layout independent
  metric blocks  block count                             layout independent

'flat' is the step-free mode: it counts biz/flb/rnz and the ops, ignores how
far apart the cells are, so one search result and one cache entry serve every
layout.  The price is a slightly longer tape when the layout happens to suit a
different program: 90 characters for chars, 95 for flat on the full adder.

Checked: examples/full_add_flat.r8asm hits the cache on the second run, and the
same block with 'layout 0 2 4 6 8 10' added hits the *same* entry and emits a
byte-identical tape (the key drops the layout for the layout-free metrics).
Both pass the eight combination check.
2026-11-06 18:39:49 +08:00

97 lines
3.1 KiB
C++

// Glue between r8veritas truthtables and the phase-parallel search: figures out
// which input bits matter, builds the start/goal keys and dispatches on K.
#ifndef R8VERITAS_PHASE_TT
#define R8VERITAS_PHASE_TT
#include "r8forge/r8veritas.hh"
#include "r8forge/r8veritas_phase.hh"
#include <array>
#include <cstddef>
#include <vector>
namespace r8par {
// every block of the classic model: one sacrifice plus every mask, both ops
template <int N>
std::vector<std::array<int, 3>> classic_blocks() {
std::vector<std::array<int, 3>> ins;
for (int s = 0; s < N; s++) {
ins.push_back({s, 0, 0});
for (int sub = 1; sub < (1 << (N - 1)); sub++) {
int m = 0, bit = 0;
for (int b = 0; b < N; b++)
if (b != s)
m |= ((sub >> bit++) & 1) << b;
ins.push_back({s, m, 0});
ins.push_back({s, m, 1});
}
}
return ins;
}
template <int N, int K>
result_t search_k(const typename r8veritas<N>::truthtable &tt,
const std::vector<int> &bit_of,
const std::array<int, N> &addr, int limit,
unsigned threads, size_t max_states,
bool count_travel = true) {
using E = engine<N, K>;
using key = typename E::key;
const size_t entries = size_t(1) << K;
std::vector<size_t> full(entries, 0);
for (size_t j = 0; j < entries; j++)
for (int b = 0; b < K; b++)
if (j & (size_t(1) << b))
full[j] |= size_t(1) << bit_of[size_t(b)];
key start = {}, goal = {};
for (size_t j = 0; j < entries; j++)
for (int b = 0; b < N; b++) {
if (j & (size_t(1) << b))
E::put(start, b, E::get(start, b) | (uint64_t(1) << j));
if ((*tt.second)[full[j]] & (1u << b))
E::put(goal, b, E::get(goal, b) | (uint64_t(1) << j));
}
return search<N, K>(start, goal, classic_blocks<N>(), addr, limit, threads,
max_states, count_travel);
}
template <int N>
result_t search_tt(const typename r8veritas<N>::truthtable &tt,
const std::array<int, N> &addr, int limit, unsigned threads,
size_t max_states, bool count_travel = true) {
std::vector<int> bit_of;
for (int i = 0; i < N; i++)
for (size_t j = 0; j < (size_t(1) << N); j++)
if ((*tt.second)[j] != (*tt.second)[j ^ (size_t(1) << i)]) {
bit_of.push_back(i);
break;
}
switch (bit_of.size()) {
case 1:
return search_k<N, 1>(tt, bit_of, addr, limit, threads, max_states, count_travel);
case 2:
return search_k<N, 2>(tt, bit_of, addr, limit, threads, max_states, count_travel);
case 3:
return search_k<N, 3>(tt, bit_of, addr, limit, threads, max_states, count_travel);
case 4:
return search_k<N, 4>(tt, bit_of, addr, limit, threads, max_states, count_travel);
case 5:
return search_k<N, 5>(tt, bit_of, addr, limit, threads, max_states, count_travel);
case 6:
return search_k<N, 6>(tt, bit_of, addr, limit, threads, max_states, count_travel);
default: {
result_t r;
r.message = "the answer depends on " + std::to_string(bit_of.size()) +
" inputs, which the packed state cannot hold";
return r;
}
}
}
} // namespace r8par
#endif