src/nsim.c

/* Exact and noisy runs of Lev(N_host) and of its r-fold amplification, written
 * independently of the artifact. A row of the r-fold map reads every copy of its
 * inputs, so all r copies of row i share the pre-activation
 *     z = sum_j w_ij cnt_j + r b_i + (r - 1) / 2,   cnt_j = copies of input j at 1,
 * and copy c outputs H(z) unless its noise crosses the comparator at -1/2, which
 * under centred Gaussian noise of deviation s happens with probability
 * Q(|z + 1/2| / s). Each copy of each row draws that event independently.
 *
 *   nsim FILE exact INST T HSTEPS HISTOUT        exact orbit: histogram of z, K*, A*, output
 *   nsim FILE curve INST s COPIES T SEED R       first step at which a copy of the state deviates
 *   nsim FILE run   s R SEED                     one noisy run of Omega* to its end
 *   nsim FILE fail  s COPIES T SEED R            first wrong majority-read state, per copy
 * INST 0 is the self-describing instance (m_P, r_H), 1 the self-reproducing one.
 */
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <omp.h>

static int n, L, M, nnz;
static int *width, *rowoff;          /* rowoff[l]: first row of layer l (1-based layers) */
static int *bias, *fanin, *estart, *esrc, *ew;
static int maxw;
static int PCB, HALT, MEMB;
static int C_WR, C_EOT, C_RW, C_RD, R_IN, R_OUT, HALT_PC;
static unsigned char *blob[5];
static int bloblen[5];

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

static void load(const char *path) {
    FILE *f = fopen(path, "rb");
    int h[4]; rd(h, 4, 4, f); n = h[0]; L = h[1]; M = h[2]; nnz = h[3];
    width = malloc(sizeof(int) * (L + 1)); rd(width, 4, L + 1, f);
    rowoff = malloc(sizeof(int) * (L + 2));
    rowoff[1] = 0; for (int l = 1; l <= L; l++) rowoff[l + 1] = rowoff[l] + width[l];
    maxw = 0; for (int l = 0; l <= L; l++) if (width[l] > maxw) maxw = width[l];
    bias = malloc(sizeof(int) * M); fanin = malloc(sizeof(int) * M); estart = malloc(sizeof(int) * (M + 1));
    for (int i = 0; i < M; i++) { int bf[2]; rd(bf, 4, 2, f); bias[i] = bf[0]; fanin[i] = bf[1]; }
    estart[0] = 0; for (int i = 0; i < M; i++) estart[i + 1] = estart[i] + fanin[i];
    esrc = malloc(sizeof(int) * nnz); ew = malloc(sizeof(int) * nnz);
    for (int e = 0; e < nnz; e++) { int sw[2]; rd(sw, 4, 2, f); esrc[e] = sw[0]; ew[e] = sw[1]; }
    int lay[3]; rd(lay, 4, 3, f); PCB = lay[0]; HALT = lay[1]; MEMB = lay[2];
    int io[7]; rd(io, 4, 7, f);
    C_WR = io[0]; C_EOT = io[1]; C_RW = io[2]; C_RD = io[3]; R_IN = io[4]; R_OUT = io[5]; HALT_PC = io[6];
    for (int k = 0; k < 5; k++) { rd(&bloblen[k], 4, 1, f); blob[k] = malloc(bloblen[k]); rd(blob[k], 1, bloblen[k], f); }
    fclose(f);
}

/* ---- random numbers: xoshiro256** seeded by splitmix64 ---- */
typedef struct { uint64_t s[4]; } rng_t;
static uint64_t splitmix(uint64_t *x) { uint64_t z = (*x += 0x9e3779b97f4a7c15ULL); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL; z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL; return z ^ (z >> 31); }
static void rng_seed(rng_t *r, uint64_t seed) { for (int i = 0; i < 4; i++) r->s[i] = splitmix(&seed); }
static inline uint64_t rotl(uint64_t x, int k) { return (x << k) | (x >> (64 - k)); }
static inline uint64_t rng_next(rng_t *r) {
    uint64_t *s = r->s, res = rotl(s[1] * 5, 7) * 9, t = s[1] << 17;
    s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3]; s[2] ^= t; s[3] = rotl(s[3], 45); return res;
}

/* flip thresholds: a copy at distance k + 1/2 from the comparator flips when a draw is below thr[k] */
#define KMAX 4096
static uint64_t thr[KMAX];
static void set_noise(double s) {
    for (int k = 0; k < KMAX; k++) {
        double q = 0.5 * erfc((k + 0.5) / s / sqrt(2.0));
        double v = q * 18446744073709551616.0;
        thr[k] = v >= 18446744073709551615.0 ? UINT64_MAX : (uint64_t)v;
    }
}

/* ---- the device of Definition 5.1 on copies of the state ---- */
typedef struct { int head; long nout; } devst;

static int get_byte(const unsigned char *x, int r, int j) {     /* majority of the r copies */
    int v = 0;
    for (int k = 0; k < 8; k++) {
        int c = 0; for (int q = 0; q < r; q++) c += x[q * n + MEMB + 8 * j + k];
        v = (v << 1) | (2 * c > r);
    }
    return v;
}
static void put_byte(unsigned char *x, int r, int j, int v) {
    for (int k = 0; k < 8; k++) { int b = (v >> (7 - k)) & 1; for (int q = 0; q < r; q++) x[q * n + MEMB + 8 * j + k] = b; }
}
/* returns the byte emitted, or -1 */
static int device(unsigned char *x, int r, devst *d, const unsigned char *tape, int tlen) {
    int emit = -1;
    if (get_byte(x, r, C_WR) == 1) { emit = get_byte(x, r, R_OUT); put_byte(x, r, R_OUT, 0); d->nout++; }
    if (get_byte(x, r, C_RD) == 1) {
        if (d->head < tlen) { put_byte(x, r, R_IN, tape[d->head]); put_byte(x, r, C_EOT, 0); d->head++; }
        else put_byte(x, r, C_EOT, 1);
    }
    if (get_byte(x, r, C_RW) == 1) d->head = 0;
    put_byte(x, r, C_RD, 0); put_byte(x, r, C_RW, 0); put_byte(x, r, C_WR, 0);
    return emit;
}
static int halted(const unsigned char *x, int r) {
    int c = 0; for (int q = 0; q < r; q++) c += x[q * n + HALT]; return 2 * c > r;
}

/* ---- one step of the r-fold map on x (r copies of n bits) into y ---- */
typedef struct { unsigned char *a, *b; } buf_t;
static buf_t newbuf(int r) { buf_t B; B.a = malloc((size_t)r * maxw); B.b = malloc((size_t)r * maxw); return B; }

/* noisy: rng may be NULL for the exact map. hist (exact, r = 1): counts of k per step. stats: K*, A* */
static void step(const unsigned char *x, unsigned char *y, int r, rng_t *g, buf_t *B,
                 long *hist, int *kstar, int *astar) {
    unsigned char *in = B->a, *out = B->b;
    for (int q = 0; q < r; q++) memcpy(in + (size_t)q * maxw, x + (size_t)q * n, n);
    int half = (r - 1) / 2;
    for (int l = 1; l <= L; l++) {
        int W = width[l], Wp = width[l - 1];
        int active = 0;
        if (astar) for (int j = 0; j < Wp; j++) active += in[j];
        for (int i = 0; i < W; i++) {
            int row = rowoff[l] + i, z = r * bias[row] + half, k1 = 0;
            for (int e = estart[row]; e < estart[row + 1]; e++) {
                int c = 0; for (int q = 0; q < r; q++) c += in[(size_t)q * maxw + esrc[e]];
                z += ew[e] * c; k1 += c;
            }
            int v = z >= 0, kk = z >= 0 ? z : -z - 1;
            if (hist) hist[kk < KMAX ? kk : KMAX - 1]++;
            if (kstar && k1 > *kstar) *kstar = k1;
            if (astar && active - k1 > *astar) *astar = active - k1;
            for (int q = 0; q < r; q++) {
                int o = v;
                if (g && kk < KMAX && thr[kk] && rng_next(g) < thr[kk]) o ^= 1;
                out[(size_t)q * maxw + i] = o;
            }
        }
        unsigned char *t = in; in = out; out = t;
    }
    for (int q = 0; q < r; q++) memcpy(y + (size_t)q * n, in + (size_t)q * maxw, n);
}

static unsigned char *initial(int inst, int r) {
    const unsigned char *m = blob[inst == 0 ? 0 : 2];
    unsigned char *x = calloc((size_t)r * n, 1);
    for (int j = 0; j < 256; j++) put_byte(x, r, j, m[j]);
    return x;
}

int main(int argc, char **argv) {
    load(argv[1]);
    const char *mode = argv[2];
    if (!strcmp(mode, "exact")) {
        int inst = atoi(argv[3]); long T = atol(argv[4]); long H = atol(argv[5]);
        FILE *hf = fopen(argv[6], "wb");
        const unsigned char *tape = blob[inst == 0 ? 1 : 3]; int tlen = bloblen[inst == 0 ? 1 : 3];
        const unsigned char *expect = inst == 0 ? NULL : blob[4];
        unsigned char *x = initial(inst, 1), *y = malloc(n);
        buf_t B = newbuf(1); devst d = {0, 0};
        long *hist = calloc(KMAX, sizeof(long));
        int kstar = 0, astar = 0, kstar_h = 0, astar_h = 0; long t; long wrong = 0; long out = 0;
        unsigned char *outbuf = malloc(1 << 20);
        for (t = 0; t < T; t++) {
            memset(hist, 0, KMAX * sizeof(long));
            step(x, y, 1, NULL, &B, hist, &kstar, &astar);
            if (t < H) { fwrite(hist, sizeof(long), 64, hf); kstar_h = kstar; astar_h = astar; }
            int e = device(y, 1, &d, tape, tlen);
            if (e >= 0) { if (expect && (out >= bloblen[4] || e != expect[out])) wrong++; if (out < (1 << 20)) outbuf[out] = e; out++; }
            memcpy(x, y, n);
            if (halted(x, 1)) { t++; break; }
        }
        fclose(hf);
        printf("{\"steps\": %ld, \"halted\": %d, \"bytes\": %ld, \"wrong_bytes\": %ld, \"Kstar_first\": %d, \"Astar_first\": %d, \"Kstar\": %d, \"Astar\": %d, \"head\": %d}\n",
               t, halted(x, 1), out, wrong, kstar_h, astar_h, kstar, astar, d.head);
        return 0;
    }
    if (!strcmp(mode, "curve")) {
        int inst = atoi(argv[3]); double s = atof(argv[4]); int C = atoi(argv[5]); long T = atol(argv[6]);
        uint64_t seed = strtoull(argv[7], NULL, 10); int r = atoi(argv[8]);
        set_noise(s);
        const unsigned char *tape = blob[inst == 0 ? 1 : 3]; int tlen = bloblen[inst == 0 ? 1 : 3];
        /* the exact orbit and the device state along it */
        unsigned char *orb = malloc((size_t)(T + 1) * r * n); int *heads = malloc(sizeof(int) * (T + 1));
        unsigned char *x0 = initial(inst, r); memcpy(orb, x0, (size_t)r * n);
        buf_t B = newbuf(r); devst d = {0, 0}; heads[0] = 0;
        for (long t = 0; t < T; t++) {
            step(orb + (size_t)t * r * n, orb + (size_t)(t + 1) * r * n, r, NULL, &B, NULL, NULL, NULL);
            device(orb + (size_t)(t + 1) * r * n, r, &d, tape, tlen); heads[t + 1] = d.head;
        }
        long *first = calloc(C, sizeof(long));
        #pragma omp parallel
        {
            buf_t Bt = newbuf(r); unsigned char *y = malloc((size_t)r * n);
            #pragma omp for schedule(dynamic, 1)
            for (int c = 0; c < C; c++) {
                rng_t g; rng_seed(&g, seed * 1000003ULL + c);
                for (long t = 0; t < T; t++) {
                    step(orb + (size_t)t * r * n, y, r, &g, &Bt, NULL, NULL, NULL);
                    devst dc = {heads[t], 0};
                    device(y, r, &dc, tape, tlen);
                    if (memcmp(y, orb + (size_t)(t + 1) * r * n, (size_t)r * n)) { first[c] = t + 1; break; }
                }
            }
        }
        printf("[");
        for (int c = 0; c < C; c++) printf("%ld%s", first[c], c + 1 < C ? ", " : "");
        printf("]\n");
        return 0;
    }
    if (!strcmp(mode, "run")) {
        double s = atof(argv[3]); int r = atoi(argv[4]); uint64_t seed = strtoull(argv[5], NULL, 10);
        set_noise(s);
        const unsigned char *tape = blob[3]; int tlen = bloblen[3]; const unsigned char *expect = blob[4];
        unsigned char *x = initial(1, r), *y = malloc((size_t)r * n);
        buf_t B = newbuf(r); devst d = {0, 0}; rng_t g; rng_seed(&g, seed);
        long t, out = 0; const char *why = "steps exhausted";
        for (t = 0; t < 4000000; t++) {
            step(x, y, r, &g, &B, NULL, NULL, NULL);
            int e = device(y, r, &d, tape, tlen);
            memcpy(x, y, (size_t)r * n);
            if (e >= 0) {
                if (out >= bloblen[4] || e != expect[out]) { why = "a wrong byte"; t++; break; }
                out++;
            }
            if (halted(x, r)) { why = out == bloblen[4] ? "the whole instance" : "the halt bit set"; t++; break; }
        }
        printf("{\"s\": %g, \"r\": %d, \"seed\": %llu, \"steps\": %ld, \"bytes\": %ld, \"outcome\": \"%s\"}\n",
               s, r, (unsigned long long)seed, t, out, why);
        return 0;
    }
    if (!strcmp(mode, "fail")) {
        double s = atof(argv[3]); int C = atoi(argv[4]); long T = atol(argv[5]);
        uint64_t seed = strtoull(argv[6], NULL, 10); int r = atoi(argv[7]);
        set_noise(s);
        const unsigned char *tape = blob[1]; int tlen = bloblen[1];
        /* the exact orbit, one copy suffices: majority reads are compared with it */
        unsigned char *orb = malloc((size_t)(T + 1) * n); int *heads = malloc(sizeof(int) * (T + 1));
        unsigned char *x0 = initial(0, 1); memcpy(orb, x0, n);
        buf_t B = newbuf(1); devst d = {0, 0}; heads[0] = 0;
        for (long t = 0; t < T; t++) {
            step(orb + (size_t)t * n, orb + (size_t)(t + 1) * n, 1, NULL, &B, NULL, NULL, NULL);
            device(orb + (size_t)(t + 1) * n, 1, &d, tape, tlen); heads[t + 1] = d.head;
        }
        long *first = calloc(C, sizeof(long));
        #pragma omp parallel
        {
            buf_t Bt = newbuf(r); unsigned char *x = malloc((size_t)r * n), *y = malloc((size_t)r * n);
            #pragma omp for schedule(dynamic, 1)
            for (int c = 0; c < C; c++) {
                rng_t g; rng_seed(&g, seed * 1000003ULL + c);
                unsigned char *xi = initial(0, r); memcpy(x, xi, (size_t)r * n); free(xi);
                for (long t = 0; t < T; t++) {
                    step(x, y, r, &g, &Bt, NULL, NULL, NULL);
                    devst dc = {heads[t], 0};
                    device(y, r, &dc, tape, tlen);
                    int bad = 0;
                    for (int i = 0; i < n && !bad; i++) {
                        int cnt = 0; for (int q = 0; q < r; q++) cnt += y[(size_t)q * n + i];
                        bad = (2 * cnt > r) != orb[(size_t)(t + 1) * n + i];
                    }
                    if (bad) { first[c] = t + 1; break; }
                    memcpy(x, y, (size_t)r * n);
                }
            }
        }
        printf("[");
        for (int c = 0; c < C; c++) printf("%ld%s", first[c], c + 1 < C ? ", " : "");
        printf("]\n");
        return 0;
    }
    fprintf(stderr, "unknown mode\n");
    return 1;
}