%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.
97 lines
3.1 KiB
C++
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
|