#!/usr/bin/env python3 """bellman.py -- supersolution certificate for the closed trails longer than 20 (rows 2-4 of Table tab:tail). Hexagon accepts only scripts and data files of a few types as ancillary files, so the C program bellman.c is stored in this file verbatim, as the string C_SOURCE below. Its sha256 digest is 7f5d7287f0c4ed4a74a9a04a75221224676e53b79cbb26bd021a9dd4d5b8f198 This script writes bellman.c to a directory, compiles it with gcc -O2 -fopenmp -frounding-math -ffp-contract=off bellman.c -lm -o bellman runs the program with the arguments given, and passes its standard output and standard error through unchanged. For one pair type X and one first direction d0 it enumerates the prefixes of length 20, proposes a function U on the box of radius R by improvement sweeps (OpenMP threads), and then verifies, in one thread with upward rounding, every inequality of the box lemma of Appendix C and prints the resulting bound for the trails longer than 20 (last line "TAIL ... PASS"). A run is valid only if it reports "violated rows = 0" and ends with PASS. One recorded case needs about 1.3 GB of memory and about ten minutes on four cores. Usage: python3 bellman.py --print-source print bellman.c to standard output and exit python3 bellman.py --write-source DIR write DIR/bellman.c and exit python3 bellman.py [--workdir DIR] [--cc CC] [--compile-only] [--verbose] [--] X D0 R SWEEPS [DEBUG] --workdir DIR build in DIR and keep bellman.c and the binary there (default: a temporary directory that is removed at the end) --cc CC the C compiler (default gcc; the flags above are always used) --compile-only compile and exit --verbose print the compiler command and the compiler's messages to standard error The compiler and floating-point environment must honor directed rounding. Keep -frounding-math and -ffp-contract=off when compiling with GCC. Example (the recorded run, see jobs.yaml): python3 bellman.py B 1 70 600 > bellman_B_1.log """ import hashlib, os, shutil, subprocess, sys, tempfile NAME = 'bellman' CFLAGS = ['-O2', '-fopenmp', '-frounding-math', '-ffp-contract=off'] LIBS = ['-lm'] SHA256 = '7f5d7287f0c4ed4a74a9a04a75221224676e53b79cbb26bd021a9dd4d5b8f198' C_SOURCE = r'''/* bellman.c -- stationary supersolution certificate for the tail (n > L) of the weighted closed-trail sums m_X(n). Usage: bellman X D0 R SWEEPS [DEBUG] X = B or C (pair type); D0 = first direction of the trail (1 = N, 2 = W, 3 = S; -1 = no split); R = radius of the box [-R,R]^2 around the centre c = (0,0); SWEEPS = maximal number of improvement sweeps. Constants: c_s = 0.961, c_t = 0.935, coefficients 1/6 and 9/25, weights h = (1, 5/4), memory m = 10, prefix L = 20. All quantities are sums of products of nonnegative numbers. Every operation that enters the final bound is carried out with rounding upward (FE_UPWARD); the only quantity rounded downward is the slack of the free vector Z. The improvement sweeps only propose the function U; the proof is the final single-threaded verification pass. */ #include #include #include #include #include #pragma STDC FENV_ACCESS ON #define M 10 #define L 20 static const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; static double xs, xt, ca, cb, hB, hC, third, fifth; static double diag[4][3]; /* phase x kind (0 = s, 1 = t, 2 = r) */ static void set_rounding(int mode) { if (fesetround(mode) != 0) { fprintf(stderr, "could not set floating-point rounding mode %d\n", mode); exit(EXIT_FAILURE); } } /* ---------------- windows and their quotient ---------------- */ static int nw = 0, cap = 0, *wcode, *lut, (*tgt)[4], *wlast, *cls, Q; static signed char (*wkind)[4]; static int (*qt)[4], *qlast; static signed char (*qk)[4]; static void wpos(const int *d, int len, int *px, int *py) { px[0] = py[0] = 0; for (int i = 0; i < len; i++) { px[i+1] = px[i] + dx[d[i]]; py[i+1] = py[i] + dy[d[i]]; } } static int is_trail(const int *d, int len) { int px[64], py[64]; wpos(d, len, px, py); for (int i = 0; i < len; i++) for (int j = i + 1; j < len; j++) { if (px[i] == px[j] && py[i] == py[j] && px[i+1] == px[j+1] && py[i+1] == py[j+1]) return 0; if (px[i] == px[j+1] && py[i] == py[j+1] && px[i+1] == px[j] && py[i+1] == py[j]) return 0; } return 1; } static void gen(int *d, int len) { if (len == M) { if (nw == cap) { cap = cap ? 2 * cap : 1024; wcode = realloc(wcode, cap * sizeof(int)); } int c = 0; for (int i = 0; i < M; i++) c = c * 4 + d[i]; wcode[nw++] = c; return; } for (int k = 0; k < 4; k++) { d[len] = k; if (is_trail(d, len + 1)) gen(d, len + 1); } } static int (*skey)[7]; static int cmpkey(const void *a, const void *b) { return memcmp(skey[*(const int *)a], skey[*(const int *)b], 6 * sizeof(int)); } static void build_windows(void) { int d[64]; gen(d, 0); lut = malloc(sizeof(int) << (2 * M)); for (long i = 0; i < (1L << (2 * M)); i++) lut[i] = -1; for (int i = 0; i < nw; i++) lut[wcode[i]] = i; tgt = malloc(nw * sizeof *tgt); wkind = malloc(nw * sizeof *wkind); wlast = malloc(nw * sizeof(int)); for (int w = 0; w < nw; w++) { int px[64], py[64], c = wcode[w]; for (int i = M - 1; i >= 0; i--) { d[i] = c & 3; c >>= 2; } wpos(d, M, px, py); wlast[w] = d[M-1]; int rev = 0; for (int i = 0; i < M; i++) if (px[i] == px[M] && py[i] == py[M]) rev = 1; for (int k = 0; k < 4; k++) { tgt[w][k] = -1; wkind[w][k] = -1; int nx = px[M] + dx[k], ny = py[M] + dy[k], bad = 0; for (int i = 0; i < M; i++) { if (px[i] == px[M] && py[i] == py[M] && px[i+1] == nx && py[i+1] == ny) bad = 1; if (px[i+1] == px[M] && py[i+1] == py[M] && px[i] == nx && py[i] == ny) bad = 1; } if (bad) continue; tgt[w][k] = lut[((wcode[w] << 2) | k) & ((1 << (2 * M)) - 1)]; if (tgt[w][k] < 0) { fprintf(stderr, "window lookup failed\n"); exit(1); } wkind[w][k] = rev ? 2 : (k == d[M-1] ? 0 : 1); } } /* coarsest partition that fixes the last direction and the kinds, and is compatible with the successors */ cls = malloc(nw * sizeof(int)); skey = malloc(nw * sizeof *skey); int *ord = malloc(nw * sizeof(int)), prev = -1; for (int w = 0; w < nw; w++) { int c = wlast[w]; for (int k = 0; k < 4; k++) c = c * 4 + (wkind[w][k] + 1); cls[w] = c; } for (;;) { for (int w = 0; w < nw; w++) { skey[w][0] = cls[w]; for (int k = 0; k < 4; k++) skey[w][k+1] = tgt[w][k] < 0 ? -1 : cls[tgt[w][k]]; skey[w][5] = 0; ord[w] = w; } qsort(ord, nw, sizeof(int), cmpkey); int n = 0; for (int i = 0; i < nw; i++) { if (i > 0 && cmpkey(&ord[i-1], &ord[i]) != 0) n++; skey[ord[i]][6] = n; } n++; for (int w = 0; w < nw; w++) cls[w] = skey[w][6]; if (n == prev) { Q = n; break; } prev = n; } qt = malloc(Q * sizeof *qt); qk = malloc(Q * sizeof *qk); qlast = malloc(Q * sizeof(int)); for (int q = 0; q < Q; q++) qlast[q] = -1; for (int w = 0; w < nw; w++) { int q = cls[w]; if (qlast[q] < 0) { qlast[q] = wlast[w]; for (int k = 0; k < 4; k++) { qk[q][k] = wkind[w][k]; qt[q][k] = tgt[w][k] < 0 ? -1 : cls[tgt[w][k]]; } } /* check that every window agrees with its class: this is what the quotient needs */ if (qlast[q] != wlast[w]) { fprintf(stderr, "quotient error\n"); exit(1); } for (int k = 0; k < 4; k++) if (qk[q][k] != wkind[w][k] || qt[q][k] != (tgt[w][k] < 0 ? -1 : cls[tgt[w][k]])) { fprintf(stderr, "quotient error\n"); exit(1); } } } /* ---------------- responses ---------------- */ /* h-weighted response at a first visit at (x,y), arrival direction ain, out-direction out; pairs containing a dead site are omitted; dead(x,y) is supplied by the caller */ static int cx_ = 0, cy_ = 0; static double kappa_gen(int x, int y, int ain, int out, int (*dead)(int, int)) { int back = (ain + 2) % 4, fx[2], fy[2], nf = 0; for (int k = 0; k < 4; k++) if (k != back && k != out) { fx[nf] = x + dx[k]; fy[nf] = y + dy[k]; nf++; } int ox = x + dx[out], oy = y + dy[out]; int Ax[3] = {fx[0], fx[0], fx[1]}, Ay[3] = {fy[0], fy[0], fy[1]}, Bx[3] = {fx[1], ox, ox}, By[3] = {fy[1], oy, oy}; double s = 0; for (int q = 0; q < 3; q++) { if (dead && (dead(Ax[q], Ay[q]) || dead(Bx[q], By[q]))) continue; int isB = (Ax[q] == Bx[q] || Ay[q] == By[q]); s += (q == 0 ? ca : cb) * (isB ? hB : hC); } return s; } static int dead_c(int x, int y) { return x == cx_ && y == cy_; } /* ---------------- exact prefixes of length L ---------------- */ #define GG 64 #define OFF 32 static unsigned char hb[GG][GG], vb[GG][GG]; static int nvis[GG][GG], nleft[GG][GG]; static int usedb(int x, int y, int k) { if (k == 0) return hb[x][y]; if (k == 2) return hb[x-1][y]; if (k == 1) return vb[x][y]; return vb[x][y-1]; } static void setb(int x, int y, int k, int v) { if (k == 0) hb[x][y] = v; else if (k == 2) hb[x-1][y] = v; else if (k == 1) vb[x][y] = v; else vb[x][y-1] = v; } static int dead_true(int x, int y) { return (x == OFF && y == OFF) || nleft[x][y] >= 2; } static int vx, vy, D0, pdir[L + 1]; static int PW = 2 * L + 3; /* prefix endpoints lie in [-L-1, L+1]^2 */ static double *Ivec; static long nprefix = 0; static void dfs(int x, int y, int ain, int depth, double wA, double wB, double wC, double wD) { if (depth == L) { int c = 0; for (int i = L - M; i < L; i++) c = c * 4 + pdir[i]; int w = lut[c]; if (w < 0) { fprintf(stderr, "prefix window missing\n"); exit(1); } long base = ((long)((y - OFF + L + 1) * PW + (x - OFF + L + 1)) * Q + cls[w]) * 4; Ivec[base] += wA; Ivec[base+1] += wB; Ivec[base+2] += wC; Ivec[base+3] += wD; nprefix++; return; } int rev = nvis[x][y] > 0; /* visited before this arrival */ for (int d = 0; d < 4; d++) { if (depth == 0 && D0 >= 0 && d != D0) continue; if (usedb(x, y, d)) continue; int nx = x + dx[d], ny = y + dy[d]; if (nx == OFF && ny == OFF) continue; /* the centre c is excluded */ if (nx == vx && ny == vy) continue; /* the target is not hit before the end */ int k = rev ? 2 : (d == ain ? 0 : 1); double nA, nB, nC, nD; if (k == 2) { nA = wA * fifth; nB = wB * fifth; nC = wC * fifth; nD = wD * fifth; } else { double kap = kappa_gen(x, y, ain, d, dead_true); nC = wC * diag[2][k] + (k == 1 ? wA * (xt * kap * third) : 0.0); nD = wD * diag[3][k] + (k == 0 ? wB * (xs * kap * third) : 0.0); nA = wA * diag[0][k]; nB = wB * diag[1][k]; } setb(x, y, d, 1); nvis[x][y]++; nleft[x][y]++; pdir[depth] = d; dfs(nx, ny, d, depth + 1, nA, nB, nC, nD); setb(x, y, d, 0); nvis[x][y]--; nleft[x][y]--; } } /* ---------------- the stationary walk on the box ---------------- */ static int R, BW, ux = -1, uy = 0, ax, ay; static long NP; static float *U; /* U[(pos * Q + q) * 4 + phase] */ static double kfree[4][4]; #define IDX(px, py, q) ((((long)((py) + R) * BW + ((px) + R)) * Q + (q)) * 4) /* value of the extension of U at (psi, q, x): 0 at c and outside the box, the reward at v */ static inline double val(int px, int py, int q, int psi, int proposing) { if (px < -R || px > R || py < -R || py > R) return 0.0; long index = IDX(px, py, q) + psi; if (proposing) { float value; #pragma omp atomic read value = U[index]; return value; } return U[index]; } /* upper bound of (T U)(phi, q, x) for all four phases; x is neither c nor v */ static void row(int px, int py, int q, int proposing, double out[4]) { out[0] = out[1] = out[2] = out[3] = 0.0; int special = (px == ux && py == uy) || (D0 >= 0 && px == ax && py == ay); int nearc = abs(px) + abs(py) == 1, a = qlast[q]; for (int d = 0; d < 4; d++) { int s = qt[q][d]; if (s < 0) continue; int nx = px + dx[d], ny = py + dy[d]; if (nx == 0 && ny == 0) continue; /* into the centre: zero */ if (special) { if (D0 >= 0 && ((px == ux && py == uy && nx == ax && ny == ay) || (px == ax && py == ay && nx == ux && ny == uy))) continue; for (int p = 0; p < 4; p++) out[p] += fifth * val(nx, ny, s, p, proposing); continue; } int k = qk[q][d]; if (k == 2) { for (int p = 0; p < 4; p++) out[p] += fifth * val(nx, ny, s, p, proposing); continue; } double vA = val(nx, ny, s, 0, proposing), vB = val(nx, ny, s, 1, proposing); double vC = val(nx, ny, s, 2, proposing), vD = val(nx, ny, s, 3, proposing); double kap = nearc ? kappa_gen(px, py, a, d, dead_c) : kfree[a][d]; out[0] += diag[0][k] * vA; out[1] += diag[1][k] * vB; out[2] += diag[2][k] * vC; out[3] += diag[3][k] * vD; if (k == 1) out[0] += (xt * kap * third) * vC; if (k == 0) out[1] += (xs * kap * third) * vD; } } int main(int argc, char **argv) { if (argc < 5) { fprintf(stderr, "usage: bellman X D0 R SWEEPS [DEBUG]\n"); return 1; } char X = argv[1][0]; D0 = atoi(argv[2]); R = atoi(argv[3]); int SW = atoi(argv[4]), DEBUG = argc > 5 ? atoi(argv[5]) : 0; int min_R = DEBUG ? L + 3 : L + 2; if (R < min_R) { fprintf(stderr, "R must be at least %d\n", min_R); return 1; } vx = X == 'B' ? 1 : 0; vy = X == 'B' ? 0 : 1; /* constants: thresholds rounded down, coefficients up, then everything upward */ double cs = nextafter(0.961, 0.0), ct = nextafter(0.935, 0.0); ca = nextafter(0.16666666666666667, INFINITY); cb = nextafter(0.36, INFINITY); hB = 1.0; hC = 1.25; set_rounding(FE_UPWARD); { volatile double one = 1.0, three = 3.0, five = 5.0; xs = one / cs; xt = one / ct; third = one / three; fifth = one / five; } double A_[3] = {xs * third, xt * third, fifth}, B_[3] = {xs * third, third, fifth}, D_[3] = {third, third, fifth}; for (int k = 0; k < 3; k++) { diag[0][k] = A_[k]; diag[1][k] = B_[k]; diag[2][k] = B_[k]; diag[3][k] = D_[k]; } build_windows(); for (int a = 0; a < 4; a++) for (int d = 0; d < 4; d++) kfree[a][d] = (d == (a + 2) % 4) ? 0.0 : kappa_gen(10, 10, a, d, NULL); printf("# bellman X=%c D0=%d R=%d m=%d L=%d windows=%d classes=%d cs=0.961 ct=0.935 a=1/6 b=9/25 h=(1,5/4)\n", X, D0, R, M, L, nw, Q); /* free vector Z on (phase, class): Z = sum_k W^k 1, and its slack Z - W Z > 0 */ double *Z = calloc(4 * Q, sizeof(double)), *Zn = malloc(4 * Q * sizeof(double)), *slack = malloc(4 * Q * sizeof(double)); #define FREEROW(src, q, out) do { out[0] = out[1] = out[2] = out[3] = 0.0; int a_ = qlast[q]; \ for (int d = 0; d < 4; d++) { int s = qt[q][d]; if (s < 0) continue; int k = qk[q][d]; \ if (k == 2) { for (int p = 0; p < 4; p++) out[p] += fifth * src[4*s+p]; continue; } \ for (int p = 0; p < 4; p++) out[p] += diag[p][k] * src[4*s+p]; \ if (k == 1) out[0] += (xt * kfree[a_][d] * third) * src[4*s+2]; \ if (k == 0) out[1] += (xs * kfree[a_][d] * third) * src[4*s+3]; } } while (0) for (int it = 0; it < 4000; it++) { double inc = 0; for (int q = 0; q < Q; q++) { double o[4]; FREEROW(Z, q, o); for (int p = 0; p < 4; p++) { Zn[4*q+p] = 1.0 + o[p]; if (Zn[4*q+p] - Z[4*q+p] > inc) inc = Zn[4*q+p] - Z[4*q+p]; } } memcpy(Z, Zn, 4 * Q * sizeof(double)); if (inc < 1e-3) break; } double zmax = 0, smin = 1e300; for (int q = 0; q < Q; q++) { double o[4]; FREEROW(Z, q, o); /* o >= exact W Z */ for (int p = 0; p < 4; p++) { set_rounding(FE_DOWNWARD); slack[4*q+p] = Z[4*q+p] - o[p]; set_rounding(FE_UPWARD); if (slack[4*q+p] < smin) smin = slack[4*q+p]; if (Z[4*q+p] > zmax) zmax = Z[4*q+p]; } } printf("# free vector: max Z = %.6e, min slack = %.6e\n", zmax, smin); if (!(smin > 0)) { printf("FAIL: no slack\n"); return 2; } /* exact prefixes */ ax = ux + (D0 >= 0 ? dx[D0] : 0); ay = uy + (D0 >= 0 ? dy[D0] : 0); Ivec = calloc((size_t)PW * PW * Q * 4, sizeof(double)); vx += OFF; vy += OFF; nvis[OFF-1][OFF] = 0; dfs(OFF - 1, OFF, 2, 0, 1.0, 1.0, 0.0, 0.0); vx -= OFF; vy -= OFF; printf("# prefixes of length %d: %ld\n", L, nprefix); /* the function U on the box, started from the free vector (a supersolution since Z >= 1 >= g and T <= W) */ BW = 2 * R + 1; NP = (long)BW * BW; U = malloc((size_t)NP * Q * 4 * sizeof(float)); for (int py = -R; py <= R; py++) for (int px = -R; px <= R; px++) for (int q = 0; q < Q; q++) { long b = IDX(px, py, q); for (int p = 0; p < 4; p++) U[b+p] = (px == 0 && py == 0) ? 0.0f : (px == vx && py == vy) ? (p >= 2 ? 1.0f : 0.0f) : (float)Z[4*q+p]; } if (DEBUG) { /* check of conventions: sum over prefixes of (T^2 g) bounds the trails of length L + 2 */ float *G1 = calloc((size_t)NP * Q * 4, sizeof(float)), *sv = U; double tot = 0; for (int py = -R; py <= R; py++) for (int px = -R; px <= R; px++) for (int q = 0; q < Q; q++) { long b = IDX(px, py, q); for (int p = 0; p < 4; p++) G1[b+p] = (px == vx && py == vy && p >= 2) ? 1.0f : 0.0f; } float *G2 = calloc((size_t)NP * Q * 4, sizeof(float)), *G3 = calloc((size_t)NP * Q * 4, sizeof(float)); U = G1; for (int py = -L-3; py <= L+3; py++) for (int px = -L-3; px <= L+3; px++) { if ((px == 0 && py == 0) || (px == vx && py == vy)) continue; for (int q = 0; q < Q; q++) { double o[4]; row(px, py, q, 0, o); long b = IDX(px, py, q); for (int p = 0; p < 4; p++) G2[b+p] = (float)o[p]; } } U = G2; for (int py = -L-2; py <= L+2; py++) for (int px = -L-2; px <= L+2; px++) { if ((px == 0 && py == 0) || (px == vx && py == vy)) continue; for (int q = 0; q < Q; q++) { double o[4]; row(px, py, q, 0, o); long b = IDX(px, py, q); for (int p = 0; p < 4; p++) G3[b+p] = (float)o[p]; } } for (int py = -L-1; py <= L+1; py++) for (int px = -L-1; px <= L+1; px++) for (int q = 0; q < Q; q++) { long ib = ((long)((py + L + 1) * PW + (px + L + 1)) * Q + q) * 4, b = IDX(px, py, q); for (int p = 0; p < 4; p++) tot += Ivec[ib+p] * G3[b+p]; } printf("# DEBUG bound for n = %d: %.12e\n", L + 2, tot); U = sv; free(G1); free(G2); free(G3); } double last = 1e300; for (int sw = 0; sw < SW; sw++) { #pragma omp parallel { set_rounding(FE_UPWARD); #pragma omp for schedule(static) for (int iy = 0; iy < BW; iy++) { int py = (sw & 1) ? R - iy : iy - R; for (int ix = 0; ix < BW; ix++) { int px = (sw & 2) ? R - ix : ix - R; if ((px == 0 && py == 0) || (px == vx && py == vy)) continue; for (int q = 0; q < Q; q++) { double o[4]; row(px, py, q, 1, o); long b = IDX(px, py, q); for (int p = 0; p < 4; p++) { float candidate = (float)o[p]; if (candidate < val(px, py, q, p, 1)) { /* This thread owns the row; neighboring rows may read it. */ #pragma omp atomic write U[b+p] = candidate; } } } } } } if (sw % 10 == 9 || sw == SW - 1) { double tot = 0; for (int py = -L-1; py <= L+1; py++) for (int px = -L-1; px <= L+1; px++) for (int q = 0; q < Q; q++) { long ib = ((long)((py + L + 1) * PW + (px + L + 1)) * Q + q) * 4, b = IDX(px, py, q); for (int p = 0; p < 4; p++) tot += Ivec[ib+p] * (double)U[b+p]; } printf("# sweep %d: sum I U = %.10e\n", sw + 1, tot); fflush(stdout); if (last - tot < 1e-9 * tot) break; last = tot; } } /* ---------------- verification (single thread, rounding upward) ---------------- */ set_rounding(FE_UPWARD); long bad = 0; for (int py = -R; py <= R; py++) for (int px = -R; px <= R; px++) { if (px == 0 && py == 0) { for (int q = 0; q < Q; q++) for (int p = 0; p < 4; p++) if (U[IDX(px, py, q) + p] != 0.0f) bad++; continue; } if (px == vx && py == vy) { for (int q = 0; q < Q; q++) for (int p = 0; p < 4; p++) if (U[IDX(px, py, q) + p] != (p >= 2 ? 1.0f : 0.0f)) bad++; continue; } for (int q = 0; q < Q; q++) { double o[4]; row(px, py, q, 0, o); long b = IDX(px, py, q); for (int p = 0; p < 4; p++) if (!(o[p] <= (double)U[b+p])) bad++; } } /* sites outside the box next to it: (T U) <= cc * slack, so that U + cc Z is a supersolution on the whole lattice */ double cc = 0; for (int t = -R; t <= R; t++) for (int side = 0; side < 4; side++) { int px = side == 0 ? R + 1 : side == 1 ? -R - 1 : t, py = side == 2 ? R + 1 : side == 3 ? -R - 1 : t; for (int q = 0; q < Q; q++) { double o[4]; row(px, py, q, 0, o); for (int p = 0; p < 4; p++) { double r = o[p] / slack[4*q+p]; if (r > cc) cc = r; } } } double tU = 0, tZ = 0; for (int py = -L-1; py <= L+1; py++) for (int px = -L-1; px <= L+1; px++) for (int q = 0; q < Q; q++) { long ib = ((long)((py + L + 1) * PW + (px + L + 1)) * Q + q) * 4, b = IDX(px, py, q); for (int p = 0; p < 4; p++) { tU += Ivec[ib+p] * (double)U[b+p]; tZ += Ivec[ib+p] * Z[4*q+p]; } } double bound = tU + cc * tZ; printf("# verification: violated rows = %ld, outside constant = %.6e, sum I U = %.10e, sum I Z = %.6e\n", bad, cc, tU, tZ); if (bad) { printf("FAIL\n"); return 2; } printf("TAIL X=%c D0=%d sum_{n>%d} <= %.9e PASS\n", X, D0, L, bound); return 0; } ''' def main(argv): workdir, cc, compile_only, verbose = None, 'gcc', False, False i = 0 while i < len(argv): a = argv[i] if a == '--print-source': sys.stdout.write(C_SOURCE) return 0 if a == '--write-source': os.makedirs(argv[i + 1], exist_ok=True) with open(os.path.join(argv[i + 1], NAME + '.c'), 'w') as f: f.write(C_SOURCE) return 0 if a == '--workdir': workdir = argv[i + 1]; i += 2; continue if a == '--cc': cc = argv[i + 1]; i += 2; continue if a == '--compile-only': compile_only = True; i += 1; continue if a == '--verbose': verbose = True; i += 1; continue if a == '--': i += 1 break args = argv[i:] if not compile_only and not args: sys.stderr.write(__doc__) return 1 tmp = workdir is None d = tempfile.mkdtemp(prefix=NAME + '-') if tmp else os.path.abspath(workdir) os.makedirs(d, exist_ok=True) try: with open(os.path.join(d, NAME + '.c'), 'w') as f: f.write(C_SOURCE) cmd = [cc] + CFLAGS + [NAME + '.c'] + LIBS + ['-o', NAME] r = subprocess.run(cmd, cwd=d, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, universal_newlines=True) if verbose or r.returncode != 0: sys.stderr.write('cd %s && %s\n%s' % (d, ' '.join(cmd), r.stdout)) if r.returncode != 0: sys.stderr.write('%s.py: compilation failed\n' % NAME) return 1 if compile_only: return 0 sys.stdout.flush() return subprocess.run([os.path.join(d, NAME)] + args).returncode finally: if tmp: shutil.rmtree(d, ignore_errors=True) if __name__ == '__main__': if hashlib.sha256(C_SOURCE.encode('ascii')).hexdigest() != SHA256: sys.exit('%s.py: the stored C source does not match its sha256 digest' % NAME) sys.exit(main(sys.argv[1:]))