src/ring_run.c

/* Generations of the ring machine M^alpha_{K,S,L}, and optionally its netlist stepped beside it.
 *
 *   ring_run IN GENERATIONS [NETLIST]
 *
 * IN, written by src/twohead.py, holds little-endian int32 alpha, K, S, L and kappa; the 2^alpha cells
 * of the window; the K banks of S (8 + 3 alpha) bits; the K tapes of L bits; the slots, the bits and
 * the cells of the K heads (int32); then an image of a bank and of a tape, one byte per bit. A step
 * evaluates the record at the active head on the cells it names, writes v = H(w0 x0 + w1 x1 + beta)
 * into the window, under the arm or under the copy head, carries out the requests the window then
 * holds, turns the active head by one slot and clears the requests. The active bank is never written,
 * so its records are decoded once each time the bank bit changes, and a run of empty records is
 * passed in one move unless the netlist is stepped as well.
 *
 * After every hand-over the program prints the steps of the generation, the bank bit, how many banks
 * hold the image and how many tapes the tape, whether the new active head and read head are at their
 * origins, and whether the full state equals the state K generations before. With NETLIST, the file
 * src/twohead.py writes for the same machine, every step of the netlist is compared with the step
 * of the machine on the whole state, and the mismatches are counted.
 */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { SINK, RD, ARM, CPY, AR, AA, AC, RR, RA, RC, CB, CT, HO };

typedef struct { int a0, w0, a1, w1, beta, ao; } rec_t;

static int ALPHA, W, B, K, S, L, kap;
static long N;
static unsigned char *win, **Q, **D;
static int *hs, *hj, *ht;

static void *xmalloc(size_t n) { void *p = malloc(n ? n : 1); if (!p) { fprintf(stderr, "out of memory\n"); exit(2); } return p; }

static void rd(FILE *f, void *p, size_t sz, size_t k) {
    if (fread(p, sz, k, f) != k) { fprintf(stderr, "short input\n"); exit(2); }
}

static rec_t decode(const unsigned char *bits) {
    int p = 0;
#define GET(w) ({ int v_ = 0; for (int j_ = 0; j_ < (w); j_++) v_ = (v_ << 1) | bits[p++]; v_; })
    int c0 = GET(2), c1 = GET(2), beta = GET(4);
    int a0 = GET(ALPHA), a1 = GET(ALPHA), ao = GET(ALPHA);
#undef GET
    rec_t r;
    r.w0 = c0 == 1 ? 1 : c0 == 2 ? -1 : 0;
    r.w1 = c1 == 1 ? 1 : c1 == 2 ? -1 : 0;
    r.beta = beta >= 8 ? beta - 16 : beta;
    r.a0 = a0; r.a1 = a1; r.ao = ao;
    return r;
}

static inline int cell(int a, int k, int i) {
    switch (a) {
    case SINK: return 0;
    case RD: return D[k][ht[k]];
    case ARM: return Q[i][(long)hs[i] * B + hj[i]];
    case CPY: return D[i][ht[i]];
    default: return win[a];
    }
}

static void step(const rec_t *r) {
    int k = kap, i = k + 1 == K ? 0 : k + 1;
    int x0 = r->w0 ? cell(r->a0, k, i) : 0, x1 = r->w1 ? cell(r->a1, k, i) : 0;
    int v = r->w0 * x0 + r->w1 * x1 + r->beta >= 0;
    if (r->ao == ARM) Q[i][(long)hs[i] * B + hj[i]] = v;
    else if (r->ao == CPY) D[i][ht[i]] = v;
    else if (r->ao > CPY) win[r->ao] = v;
    if (win[RR]) ht[k] = 0; else if (win[AR]) ht[k] = ht[k] + 1 == L ? 0 : ht[k] + 1;
    if (win[CB]) memset(Q[i], 0, N);
    if (win[RA]) hs[i] = hj[i] = 0;
    else if (win[AA]) { if (++hj[i] == B) { hj[i] = 0; hs[i] = hs[i] + 1 == S ? 0 : hs[i] + 1; } }
    if (win[CT]) memset(D[i], 0, L);
    if (win[RC]) ht[i] = 0; else if (win[AC]) ht[i] = ht[i] + 1 == L ? 0 : ht[i] + 1;
    hs[k] = hs[k] + 1 == S ? 0 : hs[k] + 1;
    if (win[HO]) kap = i;
    memset(win + AR, 0, HO - AR + 1);
}

/* the netlist: units in order, each reading earlier signals; the state bits first */
static int nn, U, E, *bias, *fan, *pred, *nxt, *ustart;
static unsigned char *sig, *xs, *ys;

static long encode(unsigned char *x) {
    long p = 0;
    for (int c = 4; c < W; c++) x[p++] = win[c];
    for (int k = 0; k < K; k++) x[p++] = k == kap;
    for (int k = 0; k < K; k++) {
        memcpy(x + p, Q[k], N); p += N;
        for (int s = 0; s < S; s++) x[p++] = s == hs[k];
        for (int j = 0; j < B; j++) x[p++] = j == hj[k];
    }
    for (int k = 0; k < K; k++) {
        memcpy(x + p, D[k], L); p += L;
        for (int i = 0; i < L; i++) x[p++] = i == ht[k];
    }
    return p;
}

static void net_step(void) {
    memcpy(sig, xs, nn);
    for (int u = 0; u < U; u++) {
        int s = bias[u];
        for (int e = ustart[u]; e < ustart[u + 1]; e++) { int q = pred[e]; s += q > 0 ? sig[q - 1] : -sig[-q - 1]; }
        sig[nn + u] = s >= 0;
    }
    for (int i = 0; i < nn; i++) ys[i] = sig[nxt[i]];
}

static size_t state_size(void) { return (size_t)W + 1 + (size_t)K * (N + 2 * sizeof(int) + L + sizeof(int)); }

static void save_state(unsigned char *p) {
    memcpy(p, win, W); p += W; *p++ = (unsigned char)kap;
    for (int k = 0; k < K; k++) { memcpy(p, Q[k], N); p += N; memcpy(p, &hs[k], sizeof(int)); p += sizeof(int);
                                  memcpy(p, &hj[k], sizeof(int)); p += sizeof(int); }
    for (int k = 0; k < K; k++) { memcpy(p, D[k], L); p += L; memcpy(p, &ht[k], sizeof(int)); p += sizeof(int); }
}

int main(int argc, char **argv) {
    if (argc < 3) { fprintf(stderr, "ring_run IN GENERATIONS [NETLIST]\n"); return 2; }
    FILE *f = fopen(argv[1], "rb");
    if (!f) return 2;
    int gens = atoi(argv[2]);
    int hdr[5];
    rd(f, hdr, 4, 5);
    ALPHA = hdr[0]; K = hdr[1]; S = hdr[2]; L = hdr[3]; kap = hdr[4];
    W = 1 << ALPHA; B = 8 + 3 * ALPHA; N = (long)S * B;
    win = xmalloc(W); rd(f, win, 1, W);
    Q = xmalloc(K * sizeof *Q); D = xmalloc(K * sizeof *D);
    for (int k = 0; k < K; k++) { Q[k] = xmalloc(N); rd(f, Q[k], 1, N); }
    for (int k = 0; k < K; k++) { D[k] = xmalloc(L); rd(f, D[k], 1, L); }
    hs = xmalloc(K * sizeof(int)); hj = xmalloc(K * sizeof(int)); ht = xmalloc(K * sizeof(int));
    rd(f, hs, 4, K); rd(f, hj, 4, K); rd(f, ht, 4, K);
    unsigned char *image = xmalloc(N), *tape = xmalloc(L);
    rd(f, image, 1, N); rd(f, tape, 1, L);
    fclose(f);
    int with_net = argc > 3;
    if (with_net) {
        f = fopen(argv[3], "rb");
        if (!f) return 2;
        int h3[3]; rd(f, h3, 4, 3); nn = h3[0]; U = h3[1]; E = h3[2];
        bias = xmalloc(4L * U); fan = xmalloc(4L * U); pred = xmalloc(4L * E); nxt = xmalloc(4L * nn);
        rd(f, bias, 4, U); rd(f, fan, 4, U); rd(f, pred, 4, E); rd(f, nxt, 4, nn);
        fclose(f);
        ustart = xmalloc(4L * (U + 1)); ustart[0] = 0;
        for (int u = 0; u < U; u++) ustart[u + 1] = ustart[u] + fan[u];
        sig = xmalloc(nn + U); xs = xmalloc(nn); ys = xmalloc(nn);
        if (encode(xs) != nn) { fprintf(stderr, "the netlist is for another machine\n"); return 2; }
    }
    rec_t *recs = xmalloc(sizeof(rec_t) * S);
    long *next_full = xmalloc(sizeof(long) * (S + 1));
    unsigned char *full = xmalloc(S);
    size_t ssz = state_size();
    unsigned char **hist = xmalloc(sizeof(unsigned char *) * (gens + 1));
    long long mism = 0, total = 0;
    for (int gen = 1; gen <= gens; gen++) {
        int k0 = kap;
        for (int s = 0; s < S; s++) {
            recs[s] = decode(Q[k0] + (long)s * B);
            full[s] = recs[s].w0 || recs[s].w1 || recs[s].beta || recs[s].a0 || recs[s].a1 || recs[s].ao;
        }
        next_full[S] = S;
        for (int s = S - 1; s >= 0; s--) next_full[s] = full[s] ? s : next_full[s + 1];
        long long steps = 0;
        while (kap == k0) {
            int s = hs[k0];
            if (!with_net && !full[s]) {
                long e = next_full[s];
                if (e == S) { steps += S - s; hs[k0] = 0; } else { steps += e - s; hs[k0] = (int)e; }
                continue;
            }
            if (with_net) { encode(xs); net_step(); }
            step(&recs[s]);
            steps++;
            if (with_net) {
                encode(xs);
                if (memcmp(xs, ys, nn) != 0 && mism++ < 3) fprintf(stderr, "mismatch at step %lld\n", total + steps);
            }
        }
        total += steps;
        int copies = 0, descs = 0;
        for (int k = 0; k < K; k++) { copies += memcmp(Q[k], image, N) == 0; descs += memcmp(D[k], tape, L) == 0; }
        hist[gen] = xmalloc(ssz);
        save_state(hist[gen]);
        int periodic = gen > K ? memcmp(hist[gen], hist[gen - K], ssz) == 0 : -1;
        printf("{\"generation\": %d, \"steps\": %lld, \"kappa\": %d, \"copies\": %d, \"descriptions\": %d, "
               "\"heads_at_origin\": %d, \"equals_generation_minus_K\": %d", gen, steps, kap, copies, descs,
               hs[kap] == 0 && ht[kap] == 0, periodic);
        if (with_net) printf(", \"netlist_mismatches\": %lld", mism);
        printf("}\n");
        fflush(stdout);
    }
    return with_net && mism ? 1 : 0;
}