src/netlist_eval.c

/* An evaluator of the SUBLEQ host family written in C against Definitions 5.1
 * (the tape transducer) and 5.2 (SUBLEQ) and the layout of the serialization,
 * sharing no code with the Python evaluators.
 *
 *   netlist_eval rand NET N SEED             one step of the netlist against
 *                                            SUBLEQ on N random states, 64 per
 *                                            batch, and the halted fixed point
 *   netlist_eval run NET MEM TAPE OUT MODE [CAP]
 *                                            run the transducer; MODE is ref, net
 *                                            or lock (lock runs both and compares
 *                                            the full state, the head and the
 *                                            output after every step); with CAP
 *                                            the run stops after CAP steps
 *   netlist_eval ref A MEM TAPE OUT [CAP]    the reference machine alone, for a
 *                                            word width A, without a netlist
 *   netlist_eval iter NET STATE K OUT        iterate any flat netlist K times
 *                                            from STATE (one byte per state bit)
 *                                            and write the final state
 *
 * NET is a flat netlist: the state width n, the unit count v and the edge count
 * E, then v biases, v fan-ins, E (index, weight) pairs and n next-state
 * indices, all little-endian int32. For the host family the state is the A
 * counter bits, the halt bit and 2^A words of A bits, most significant bit
 * first, and A is recovered from n = A + 1 + A 2^A. For the amplified host of
 * Section 8.2 the state is R copies of that, copy c occupying the block
 * c n0 .. (c+1) n0 - 1, and (R, A) is recovered from n = R (A + 1 + A 2^A) with
 * the smallest R; the device reads each bit of a cell as the majority of its
 * copies and writes every copy, and rand replicates each random state and
 * checks every copy of the result. MEM holds 2^A words of ceil(A/8)
 * little-endian bytes. The device cells are the top seven words, a request
 * fires on the value 1, and an emission writes the low byte of R_out.
 */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef _OPENMP
#include <omp.h>
#endif

static int n, v, E;
static int *bias, *fanin, *pairs, *nxt, *start, *kind;
/* units grouped by depth: level l holds order[lstart[l] .. lstart[l+1]); units of
 * one level read no unit of the same level, so a level is evaluated in parallel
 * when the netlist is large enough for the threads to pay */
static int *order, *lstart, nlev, parallel;
static uint64_t *tt;
static uint8_t *sig;
static uint64_t *sig64;

static int A = 8, rep = 1, n0;
static uint32_t SZ = 256, MASK = 255, SIGN = 128;
static uint32_t C_WR, C_EOT, C_RW, C_RD, R_IN, R_OUT, HALT_PC;

enum { K_TT, K_AND, K_OR, K_GEN };

static void set_width(int a)
{
    A = a;
    SZ = 1u << A;
    MASK = SZ - 1;
    SIGN = 1u << (A - 1);
    C_WR = SZ - 7; C_EOT = SZ - 6; C_RW = SZ - 5; C_RD = SZ - 4;
    R_IN = SZ - 3; R_OUT = SZ - 2; HALT_PC = SZ - 1;
}

static void load_net(const char *path)
{
    FILE *f = fopen(path, "rb");
    if (!f) { perror(path); exit(2); }
    int hdr[3];
    if (fread(hdr, 4, 3, f) != 3) exit(2);
    n = hdr[0]; v = hdr[1]; E = hdr[2];
    bias = malloc(4 * (size_t)v); fanin = malloc(4 * (size_t)v);
    pairs = malloc(8 * (size_t)E); nxt = malloc(4 * (size_t)n);
    if (fread(bias, 4, v, f) != (size_t)v || fread(fanin, 4, v, f) != (size_t)v ||
        fread(pairs, 8, E, f) != (size_t)E || fread(nxt, 4, n, f) != (size_t)n) {
        fprintf(stderr, "short read\n"); exit(2);
    }
    fclose(f);
    start = malloc(4 * (size_t)(v + 1));
    start[0] = 0;
    for (int j = 0; j < v; j++) start[j + 1] = start[j] + fanin[j];
    sig = malloc((size_t)(n + v));
    sig64 = malloc(8 * (size_t)(n + v));
    kind = malloc(4 * (size_t)(v > 0 ? v : 1));
    tt = calloc((size_t)(v > 0 ? v : 1), 8);
    int gen = 0;
    for (int j = 0; j < v; j++) {
        const int *p = pairs + 2 * start[j];
        int k = fanin[j], pos = 0, neg = 0;
        for (int e = 0; e < k; e++) {
            if (p[2 * e + 1] > 0) pos++;
            else neg++;
        }
        if (k <= 2) {
            kind[j] = K_TT;
            for (int x = 0; x < (1 << k); x++) {
                int acc = bias[j];
                for (int e = 0; e < k; e++) acc += p[2 * e + 1] * ((x >> e) & 1);
                if (acc >= 0) tt[j] |= 1ull << x;
            }
        } else if (bias[j] == -pos) kind[j] = K_AND;
        else if (bias[j] == neg - 1) kind[j] = K_OR;
        else { kind[j] = K_GEN; gen++; }
    }
    {
        int *depth = calloc((size_t)(n + v), 4);
        int dmax = 0;
        for (int j = 0; j < v; j++) {
            const int *p = pairs + 2 * start[j];
            int d = 0;
            for (int e = 0, k = fanin[j]; e < k; e++) if (depth[p[2 * e]] > d) d = depth[p[2 * e]];
            depth[n + j] = d + 1;
            if (d + 1 > dmax) dmax = d + 1;
        }
        nlev = dmax;
        lstart = calloc((size_t)nlev + 2, 4);
        for (int j = 0; j < v; j++) lstart[depth[n + j]]++;
        for (int l = 1, acc = 0; l <= nlev + 1; l++) { int c = lstart[l]; lstart[l] = acc; acc += c; }
        order = malloc(4 * (size_t)(v > 0 ? v : 1));
        int *fill = calloc((size_t)nlev + 2, 4);
        for (int j = 0; j < v; j++) { int l = depth[n + j]; order[lstart[l] + fill[l]++] = j; }
        free(fill);
        free(depth);
        parallel = E >= 200000;
#ifndef _OPENMP
        parallel = 0;
#endif
    }
    n0 = n;
    for (int r = 1; r < 64 && n0 == n; r++)
        for (int a = 3; a < 31; a++)
            if ((long)r * (a + 1 + (long)a * (1L << a)) == n) { set_width(a); rep = r; n0 = n / r; break; }
    fprintf(stderr, "net: %d state bits, %d units, %d edges, %d generic units, depth %d, A = %d, %d cop%s%s\n",
            n, v, E, gen, nlev, A, rep, rep == 1 ? "y" : "ies", parallel ? ", levels in parallel" : "");
}

static inline void unit_eval(int j)
{
    int acc = bias[j];
    const int *p = pairs + 2 * start[j];
    for (int e = 0, k = fanin[j]; e < k; e++) acc += p[2 * e + 1] * sig[p[2 * e]];
    sig[n + j] = acc >= 0;
}

static void net_step(const uint8_t *s, uint8_t *o)
{
    memcpy(sig, s, (size_t)n);
    if (!parallel) {
        for (int j = 0; j < v; j++) unit_eval(j);
    } else {
        for (int l = 1; l <= nlev; l++) {
            int lo = lstart[l], hi = lstart[l + 1];
#pragma omp parallel for schedule(static)
            for (int q = lo; q < hi; q++) unit_eval(order[q]);
        }
    }
    for (int i = 0; i < n; i++) {
        int k = nxt[i];
        o[i] = k >= 0 ? sig[k] : (k == -2);
    }
}

static void net_step64(const uint64_t *s, uint64_t *o)
{
    memcpy(sig64, s, 8 * (size_t)n);
    for (int j = 0; j < v; j++) {
        const int *p = pairs + 2 * start[j];
        int k = fanin[j];
        uint64_t r;
        if (kind[j] == K_TT) {
            uint64_t t = tt[j];
            if (k == 0) r = -(t & 1);
            else if (k == 1) {
                uint64_t x = sig64[p[0]];
                r = (x & -(t >> 1 & 1)) | (~x & -(t & 1));
            } else {
                uint64_t x = sig64[p[0]], y = sig64[p[2]];
                r = (~x & ~y & -(t & 1)) | (x & ~y & -(t >> 1 & 1)) |
                    (~x & y & -(t >> 2 & 1)) | (x & y & -(t >> 3 & 1));
            }
        } else if (kind[j] == K_AND) {
            r = ~0ull;
            for (int e = 0; e < k; e++) {
                uint64_t x = sig64[p[2 * e]];
                r &= p[2 * e + 1] > 0 ? x : ~x;
            }
        } else if (kind[j] == K_OR) {
            r = 0;
            for (int e = 0; e < k; e++) {
                uint64_t x = sig64[p[2 * e]];
                r |= p[2 * e + 1] > 0 ? x : ~x;
            }
        } else {
            r = 0;
            for (int l = 0; l < 64; l++) {
                int acc = bias[j];
                for (int e = 0; e < k; e++) acc += p[2 * e + 1] * (int)(sig64[p[2 * e]] >> l & 1);
                if (acc >= 0) r |= 1ull << l;
            }
        }
        sig64[n + j] = r;
    }
    for (int i = 0; i < n; i++) {
        int k = nxt[i];
        o[i] = k >= 0 ? sig64[k] : (k == -2 ? ~0ull : 0);
    }
}

/* ---- the machine of Definition 5.2 ------------------------------------ */
static void ref_step(uint32_t *M, uint32_t *pc)
{
    uint32_t p = *pc;
    uint32_t a = M[p], b = M[(p + 1) & MASK], c = M[(p + 2) & MASK];
    uint32_t r = (M[b] - M[a]) & MASK;
    M[b] = r;
    *pc = (r == 0 || (r & SIGN)) ? c : (p + 3) & MASK;
}

/* ---- the device of Definition 5.1 on a memory image --------------------- */
typedef struct { const uint8_t *tau; long len, h; uint8_t *out; long olen, ocap; } Dev;

static void dev_apply(Dev *d, uint32_t *M)
{
    if (M[C_WR] == 1) {
        if (d->olen == d->ocap) { d->ocap = d->ocap ? 2 * d->ocap : 1 << 16; d->out = realloc(d->out, (size_t)d->ocap); }
        d->out[d->olen++] = (uint8_t)(M[R_OUT] & 255);
        M[R_OUT] = 0;
    }
    if (M[C_RD] == 1) {
        if (d->h < d->len) { M[R_IN] = d->tau[d->h]; M[C_EOT] = 0; d->h++; }
        else M[C_EOT] = 1;
    }
    if (M[C_RW] == 1) d->h = 0;
    M[C_WR] = 0; M[C_RD] = 0; M[C_RW] = 0;
}

/* copy c of the state occupies s + c n0; a word is read from one copy or as the
 * bitwise majority of all copies, and written to every copy */
static uint32_t get_word_c(const uint8_t *s, int c, uint32_t j)
{
    uint32_t x = 0;
    const uint8_t *b = s + (size_t)c * n0 + A + 1 + (size_t)A * j;
    for (int k = 0; k < A; k++) x = (x << 1) | b[k];
    return x;
}
static uint32_t get_word(const uint8_t *s, uint32_t j)
{
    if (rep == 1) return get_word_c(s, 0, j);
    uint32_t x = 0;
    for (int k = 0; k < A; k++) {
        int ones = 0;
        for (int c = 0; c < rep; c++) ones += s[(size_t)c * n0 + A + 1 + (size_t)A * j + k];
        x = (x << 1) | (2 * ones > rep);
    }
    return x;
}
static void set_word(uint8_t *s, uint32_t j, uint32_t val)
{
    for (int c = 0; c < rep; c++) {
        uint8_t *b = s + (size_t)c * n0 + A + 1 + (size_t)A * j;
        for (int k = 0; k < A; k++) b[k] = (uint8_t)((val >> (A - 1 - k)) & 1);
    }
}
static uint32_t get_pc_c(const uint8_t *s, int c)
{
    uint32_t x = 0;
    for (int k = 0; k < A; k++) x = (x << 1) | s[(size_t)c * n0 + k];
    return x;
}

static void net_dev_apply(Dev *d, uint8_t *s)
{
    static uint32_t *W = NULL;
    if (!W) W = calloc(SZ, 4);
    uint32_t cells[6] = { C_WR, C_EOT, C_RW, C_RD, R_IN, R_OUT };
    for (int c = 0; c < 6; c++) W[cells[c]] = get_word(s, cells[c]);
    dev_apply(d, W);
    for (int c = 0; c < 6; c++) set_word(s, cells[c], W[cells[c]]);
}

static uint8_t *slurp(const char *path, long *len)
{
    FILE *f = fopen(path, "rb");
    if (!f) { perror(path); exit(2); }
    fseek(f, 0, SEEK_END); *len = ftell(f); fseek(f, 0, SEEK_SET);
    uint8_t *b = malloc((size_t)*len + 1);
    if (*len && fread(b, 1, (size_t)*len, f) != (size_t)*len) exit(2);
    fclose(f);
    return b;
}

static uint32_t *load_mem(const char *path)
{
    long mlen;
    uint8_t *m = slurp(path, &mlen);
    int wb = (A + 7) / 8;
    if (mlen != (long)SZ * wb) {
        fprintf(stderr, "memory image is %ld bytes, expected %ld\n", mlen, (long)SZ * wb);
        exit(2);
    }
    uint32_t *M = calloc(SZ, 4);
    for (uint32_t j = 0; j < SZ; j++) {
        uint32_t x = 0;
        for (int b = 0; b < wb; b++) x |= (uint32_t)m[(size_t)j * wb + b] << (8 * b);
        M[j] = x & MASK;
    }
    free(m);
    return M;
}

static uint64_t rng = 88172645463325252ull;
static uint64_t xr(void) { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; return rng; }

static int cmd_rand(long N)
{
    uint64_t *s = malloc(8 * (size_t)n), *o = malloc(8 * (size_t)n);
    uint32_t *M = calloc(SZ, 4);
    long bad = 0, tested = 0, fixed_bad = 0, latch_bad = 0;
    for (long b = 0; b * 64 < N; b++) {
        for (int i = 0; i < n0; i++) s[i] = xr();
        s[A] = 0;
        for (int c = 1; c < rep; c++) memcpy(s + (size_t)c * n0, s, 8 * (size_t)n0);
        net_step64(s, o);
        for (int l = 0; l < 64; l++) {
            uint32_t pc = 0;
            for (int k = 0; k < A; k++) pc = (pc << 1) | (uint32_t)(s[k] >> l & 1);
            for (uint32_t j = 0; j < SZ; j++) {
                uint32_t x = 0;
                for (int k = 0; k < A; k++) x = (x << 1) | (uint32_t)(s[A + 1 + (size_t)A * j + k] >> l & 1);
                M[j] = x;
            }
            ref_step(M, &pc);
            int ok = 1;
            for (int c = 0; c < rep && ok; c++) {
                const uint64_t *oc = o + (size_t)c * n0;
                uint32_t npc = 0;
                for (int k = 0; k < A; k++) npc = (npc << 1) | (uint32_t)(oc[k] >> l & 1);
                if (npc != pc) ok = 0;
                for (uint32_t j = 0; j < SZ && ok; j++) {
                    uint32_t x = 0;
                    for (int k = 0; k < A; k++) x = (x << 1) | (uint32_t)(oc[A + 1 + (size_t)A * j + k] >> l & 1);
                    if (x != M[j]) ok = 0;
                }
                if ((int)(oc[A] >> l & 1) != (pc == HALT_PC)) latch_bad++;
            }
            bad += !ok;
            tested++;
        }
        for (int i = 0; i < n0; i++) s[i] = xr();
        s[A] = ~0ull;
        for (int c = 1; c < rep; c++) memcpy(s + (size_t)c * n0, s, 8 * (size_t)n0);
        net_step64(s, o);
        for (int i = 0; i < n; i++) if (s[i] != o[i]) { fixed_bad++; break; }
    }
    printf("random states: %ld tested, %ld disagree with SUBLEQ, %ld halt-latch mismatches, "
           "%ld halted batches not fixed\n", tested, bad, latch_bad, fixed_bad);
    return bad || latch_bad || fixed_bad;
}

static int cmd_run(const char *memp, const char *tapep, const char *outp, const char *mode, long cap)
{
    long tlen;
    uint8_t *tau = slurp(tapep, &tlen);
    uint32_t *M = load_mem(memp);
    int use_ref = strcmp(mode, "net") != 0, use_net = strcmp(mode, "ref") != 0;
    uint32_t pc = 0;
    uint8_t *s = NULL, *y = NULL;
    if (use_net) {
        s = calloc((size_t)n, 1); y = calloc((size_t)n, 1);
        for (uint32_t j = 0; j < SZ; j++) set_word(s, j, M[j]);
    }
    Dev dr = { tau, tlen, 0, NULL, 0, 0 }, dn = { tau, tlen, 0, NULL, 0, 0 };
    long steps = 0;
    int halted = 0;
    for (;;) {
        int halt_r = 0, halt_n = 0;
        if (use_ref) { ref_step(M, &pc); dev_apply(&dr, M); halt_r = pc == HALT_PC; }
        if (use_net) { net_step(s, y); halt_n = y[A]; net_dev_apply(&dn, y); uint8_t *t = s; s = y; y = t; }
        steps++;
        if (use_ref && use_net) {
            int ok = halt_n == halt_r && dr.h == dn.h && dr.olen == dn.olen &&
                     (dr.olen == 0 || dr.out[dr.olen - 1] == dn.out[dn.olen - 1]);
            for (int c = 0; c < rep && ok; c++) {
                ok = get_pc_c(s, c) == pc && s[(size_t)c * n0 + A] == halt_r;
                for (uint32_t j = 0; j < SZ && ok; j++) ok = get_word_c(s, c, j) == M[j];
            }
            if (!ok) { printf("lockstep divergence at step %ld\n", steps); return 1; }
        }
        if ((use_ref && halt_r) || (!use_ref && halt_n)) { halted = 1; break; }
        if (cap && steps >= cap) break;
    }
    Dev *d = use_ref ? &dr : &dn;
    FILE *f = fopen(outp, "wb");
    if (d->olen) fwrite(d->out, 1, (size_t)d->olen, f);
    fclose(f);
    printf("mode %s: %s after %ld steps, head %ld of %ld, %ld bytes emitted\n",
           mode, halted ? "halted" : "stopped", steps, d->h, tlen, d->olen);
    return 0;
}

static int cmd_iter(const char *statep, long K, const char *outp)
{
    long len;
    uint8_t *s = slurp(statep, &len);
    if (len != n) { fprintf(stderr, "state has %ld bits, the netlist %d\n", len, n); return 2; }
    uint8_t *y = malloc((size_t)n);
    for (long t = 0; t < K; t++) {
        net_step(s, y);
        uint8_t *tmp = s; s = y; y = tmp;
    }
    FILE *f = fopen(outp, "wb");
    fwrite(s, 1, (size_t)n, f);
    fclose(f);
    return 0;
}

int main(int argc, char **argv)
{
    if (argc >= 6 && !strcmp(argv[1], "iter")) {
        load_net(argv[2]);
        return cmd_iter(argv[3], atol(argv[4]), argv[5]);
    }
    if (argc >= 5 && !strcmp(argv[1], "rand")) {
        load_net(argv[2]);
        rng ^= (uint64_t)atoll(argv[4]) * 0x9E3779B97F4A7C15ull;
        return cmd_rand(atol(argv[3]));
    }
    if (argc >= 7 && !strcmp(argv[1], "run")) {
        load_net(argv[2]);
        return cmd_run(argv[3], argv[4], argv[5], argv[6], argc >= 8 ? atol(argv[7]) : 0);
    }
    if (argc >= 6 && !strcmp(argv[1], "ref")) {
        set_width(atoi(argv[2]));
        return cmd_run(argv[3], argv[4], argv[5], "ref", argc >= 7 ? atol(argv[6]) : 0);
    }
    fprintf(stderr, "usage: netlist_eval rand NET N SEED | run NET MEM TAPE OUT ref|net|lock [CAP]"
                    " | ref A MEM TAPE OUT [CAP] | iter NET STATE K OUT\n");
    return 2;
}