/*
 * =====================================================================================================
 *  A400000_view.c  --  print terms of OEIS A400000 (the city-building sequence) from the compressed
 *                      single-file archive (A4Z format), from a local file or straight from a URL
 * =====================================================================================================
 *
 *  The archive holds a(1), ..., a(N) (N = 10^14 for A400000_100T.a4z, about 16 GB).  This program finds
 *  the right part of it and decompresses only that, so any range of terms comes out in about a second.
 *  If the archive is given as an http(s) URL, only the parts that are needed are downloaded (with the
 *  curl program and HTTP range requests): a few hundred kilobytes per query, not the whole file.
 *
 *  BUILD (needs the zstd library):
 *      Linux:   cc -O2 -o A400000_view A400000_view.c -lzstd
 *               (Debian/Ubuntu: apt install libzstd-dev;  Fedora: dnf install libzstd-devel)
 *      macOS:   brew install zstd
 *               cc -O2 -I/opt/homebrew/include -L/opt/homebrew/lib -o A400000_view A400000_view.c -lzstd
 *  Without the library, using the zstd command-line program instead (it must be on the PATH):
 *               cc -O2 -DUSE_ZSTD_CLI -o A400000_view A400000_view.c
 *
 *  USAGE
 *      A400000_view ARCHIVE [command] [-f b|c|v] [-o FILE]
 *
 *      ARCHIVE         the archive file, or its http:// or https:// URL
 *      commands:
 *        info          what the archive holds (the default)
 *        N             the term a(N)
 *        A B           the terms a(A), ..., a(B); B may also be written +K, meaning K terms from A
 *        sum N         a(1) + ... + a(N), which is A397740(N)
 *        records       the records: each height taller than everything before it, and where (A399949,
 *                      A399950)
 *        first H       where the first building of height H stands (A399763(H))
 *        heights       every height that occurs, with its first index and its number of occurrences
 *        verify [A B]  decompress the chunks that hold a(A..B) (default: all) and check each one against
 *                      the index: number of terms, sum, and the running FNV-1a hash.  -j JOBS splits the
 *                      work among JOBS processes (each needs about 1 GB; the whole archive takes about
 *                      40 CPU-hours: 2 hours with 20 processes on an M2 Ultra)
 *      options:
 *        -f b          b-file lines "n a(n)", as on the OEIS (the default)
 *        -f c          comma-separated list "a(A), a(A+1), ..."
 *        -f v          the values only, one per line
 *        -o FILE       write to FILE instead of standard output
 *      Numbers may be written as 123456789, 1e13, 2^40, or sums and differences such as 1e13+5 or 2^40-1.
 *
 *  EXAMPLES
 *      A400000_view A400000_100T.a4z 1 100                     the first 100 terms, b-file format
 *      A400000_view A400000_100T.a4z 147875405265-5 +11 -f c   around the giant building 296961
 *      A400000_view A400000_100T.a4z 22433065737435            a(22433065737435) = 314463
 *      A400000_view A400000_100T.a4z 1e13 1e13+999999 -o b.txt a million terms from 10^13 into b.txt
 *      A400000_view A400000_100T.a4z first 381                  where height 381 first appears
 *      A400000_view https://example.org/A400000_100T.a4z 5e13 +10   read straight from a web server
 *
 *  Memory: decompressing a chunk needs about 1 GB (the compression window).  Time: up to about a second
 *  per chunk touched (a chunk is 2^31 consecutive terms), plus the time to print the terms.
 *
 *  ARCHIVE FORMAT (A4Z version 1; all integers are little-endian)
 *      bytes 0..4095     a plain-text description (try: head -c 4096 A400000_100T.a4z)
 *      bytes 4096..4351  the header (offsets below are from the start of the file):
 *                          0 "A4ZHDR01"       40 index offset         88 data offset
 *                          8 version (1)      48 index entry size     96 data size in bytes
 *                         16 N (terms)        56 heights offset      104 sum of a(1..N)
 *                         24 terms per chunk  64 number of heights   112 FNV-1a hash of a(1..N)
 *                         32 number of chunks 72 records offset      120 largest term
 *                                             80 number of records   128 its index   136 creation time
 *      index             one 48-byte entry per chunk: data offset, compressed size, index of its first
 *                        term, number of terms, then the FNV-1a hash and the sum of a(1..its last term)
 *      heights table     24 bytes per height that occurs: height, first index, number of occurrences
 *      records table     16 bytes per record: height, index
 *      data              the chunks, one zstd frame each (window 2^30 bytes).  A chunk holds 2^31
 *                        consecutive terms (the last chunk fewer), one byte per term; a term >= 255 is
 *                        written as 255 and 2 bytes, or as 255 FF FF and 4 bytes.
 *  The FNV-1a hash is the one used by the program that computed the sequence: h = 0xcbf29ce484222325, then
 *  h = (h XOR a(n)) * 0x100000001b3 (mod 2^64) for n = 1, 2, ...  So any chunk can be checked on its own:
 *  start from the previous chunk's hash and sum, run through the chunk, compare.
 */

#define _POSIX_C_SOURCE 200809L          /* fseeko, popen, mkstemp */
#define _FILE_OFFSET_BITS 64             /* 64-bit file offsets: the archive is larger than 4 GB */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#ifndef _WIN32
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#endif
#ifndef USE_ZSTD_CLI
#include <zstd.h>
#endif

typedef uint64_t u64;
typedef int64_t i64;
#define FNV_OFFSET 0xcbf29ce484222325ULL
#define FNV_PRIME 0x100000001b3ULL

#if defined(__GNUC__) || defined(__clang__)
#define NORETURN __attribute__((noreturn))
#else
#define NORETURN
#endif

NORETURN static void die(const char *fmt, const char *arg) {
    fprintf(stderr, "A400000_view: ");
    fprintf(stderr, fmt, arg ? arg : "");
    fprintf(stderr, "\n");
    exit(1);
}
static void *xmalloc(size_t n) { void *p = malloc(n ? n : 1); if (!p) die("out of memory%s", ""); return p; }
static u64 le64(const unsigned char *p) { u64 v = 0; for (int k = 7; k >= 0; k--) v = v << 8 | p[k]; return v; }

/* =====================================================================================================
 *  READING THE ARCHIVE: a local file, or byte ranges fetched with curl
 * ===================================================================================================== */
static FILE *arch_file;          /* local archive */
static char *arch_url;           /* or: remote archive, already quoted for the shell */

/* Read len bytes at offset off into buf. */
static void src_read(u64 off, u64 len, void *buf) {
    if (!len) return;
    if (arch_file) {
        if (fseeko(arch_file, (off_t)off, SEEK_SET) != 0 || fread(buf, 1, len, arch_file) != len) die("cannot read the archive (is it complete?)%s", "");
        return;
    }
    /* curl writes the body and then, because of -w, a newline and the HTTP status.  A server that honors
     * the range answers 206 with exactly len bytes; anything else is an error (a server that ignores
     * ranges would send the whole file from the start).  One retry, then a diagnosis. */
    char cmd[8192];
    for (int attempt = 0; attempt < 2; attempt++) {
        snprintf(cmd, sizeof cmd, "curl -s -L --fail -r %llu-%llu -w '\\n%%{http_code}' %s 2>/dev/null", (unsigned long long)off,
                 (unsigned long long)(off + len - 1), arch_url);
        FILE *p = popen(cmd, "r");
        if (!p) die("cannot run curl%s", "");
        size_t got = fread(buf, 1, len, p);
        char tail[16] = {0}; size_t t = fread(tail, 1, sizeof tail - 1, p);
        int rc = pclose(p);
        if (got == len && rc == 0 && t >= 4 && strncmp(tail, "\n206", 4) == 0) return;
    }
    snprintf(cmd, sizeof cmd, "curl -sS -L -o /dev/null -r 0-0 -w '%%{http_code}' %s 2>&1", arch_url);
    char msg[512] = ""; FILE *p = popen(cmd, "r");
    if (p) { if (!fgets(msg, sizeof msg, p)) msg[0] = 0; pclose(p); }
    msg[strcspn(msg, "\r\n")] = 0;
    if (!strncmp(msg, "200", 3)) die("the web server ignores HTTP range requests, so the archive cannot be read from it remotely; download the file and use it locally%s", "");
    if (!strncmp(msg, "206", 3)) die("the download was interrupted or incomplete; please try again%s", "");
    die("cannot download from the URL (HTTP status or curl error: %s)", msg[0] ? msg : "none");
}

/* The header. */
typedef struct {
    u64 version, nterms, chunk_terms, nchunks, index_off, index_entry, heights_off, nheights, records_off, nrecords,
        data_off, data_bytes, total_sum, total_hash, max_height, max_index, created;
} Header;
static Header H;

static void open_archive(const char *name) {
    if (!strncmp(name, "http://", 7) || !strncmp(name, "https://", 8)) {
        size_t n = strlen(name);
        arch_url = xmalloc(4 * n + 3);                     /* single-quote it for the shell */
        char *q = arch_url; *q++ = '\'';
        for (const char *s = name; *s; s++) { if (*s == '\'') { memcpy(q, "'\\''", 4); q += 4; } else *q++ = *s; }
        *q++ = '\''; *q = 0;
    } else if (!(arch_file = fopen(name, "rb"))) die("cannot open %s", name);
    unsigned char b[256];
    src_read(4096, 256, b);
    if (memcmp(b, "A4ZHDR01", 8) != 0) die("%s is not an A4Z archive", name);
    u64 *f = &H.version;
    for (int k = 0; k < 17; k++) f[k] = le64(b + 8 + 8 * k);
    if (H.version != 1 || H.index_entry != 48 || H.chunk_terms == 0) die("unsupported archive version%s", "");
}

/* Chunk index entries. */
typedef struct { u64 off, csize, first, nterms, hash_end, sum_end; } Chunk;
/* Entries k0..k1 (inclusive) into c[0..]. */
static void read_chunks(u64 k0, u64 k1, Chunk *c) {
    u64 n = k1 - k0 + 1;
    unsigned char *b = xmalloc(48 * n);
    src_read(H.index_off + 48 * k0, 48 * n, b);
    for (u64 j = 0; j < n; j++) {
        const unsigned char *e = b + 48 * j;
        c[j] = (Chunk){le64(e), le64(e + 8), le64(e + 16), le64(e + 24), le64(e + 32), le64(e + 40)};
    }
    free(b);
}
/* The chunk that holds a(n). */
static u64 chunk_of(u64 n) { return (n - 1) / H.chunk_terms; }

/* =====================================================================================================
 *  DECOMPRESSING A CHUNK
 *  dec_open() takes the compressed bytes of one chunk; dec_fill() makes the next piece of decompressed
 *  data available in d->buf[d->pos .. d->len).
 * ===================================================================================================== */
#define DBUF (1 << 22)
#ifdef USE_ZSTD_CLI
static char tmp_path[64];                /* the temporary file of the chunk being decompressed */
static void remove_tmp(void) { if (tmp_path[0]) unlink(tmp_path); }
#endif
typedef struct {
    unsigned char *src; size_t srclen;   /* the compressed chunk */
    unsigned char *buf; size_t len, pos; /* decompressed bytes not yet used */
#ifdef USE_ZSTD_CLI
    FILE *pipe; int at_end;              /* at_end: zstd's whole output was read (then its exit status counts) */
#else
    ZSTD_DCtx *dctx; ZSTD_inBuffer in; int ended;
#endif
} Dec;

static void dec_open(Dec *d, const Chunk *c) {
    d->srclen = c->csize; d->src = xmalloc(c->csize);
    src_read(c->off, c->csize, d->src);
    d->buf = xmalloc(DBUF); d->len = d->pos = 0;
#ifdef USE_ZSTD_CLI
    /* zstd reads the compressed chunk from a temporary file (removed again in dec_close or at exit) */
    strcpy(tmp_path, "/tmp/A400000_view.XXXXXX");
    int fd = mkstemp(tmp_path);
    if (fd < 0) die("cannot create a temporary file%s", "");
    FILE *t = fdopen(fd, "wb");
    if (!t || fwrite(d->src, 1, d->srclen, t) != d->srclen || fclose(t) != 0) die("cannot write a temporary file%s", "");
    char cmd[256]; snprintf(cmd, sizeof cmd, "zstd -dcq --long=31 '%s' 2>/dev/null", tmp_path);
    if (!(d->pipe = popen(cmd, "r"))) die("cannot run zstd%s", "");
    d->at_end = 0;
#else
    d->dctx = ZSTD_createDCtx();
    if (!d->dctx) die("out of memory%s", "");
    ZSTD_DCtx_setParameter(d->dctx, ZSTD_d_windowLogMax, 31);    /* the chunks use a 2^30-byte window */
    d->in = (ZSTD_inBuffer){d->src, d->srclen, 0}; d->ended = 0;
#endif
}
/* More decompressed data; 0 at the end of the chunk. */
static int dec_fill(Dec *d) {
    d->pos = 0;
#ifdef USE_ZSTD_CLI
    d->len = fread(d->buf, 1, DBUF, d->pipe);
    if (d->len == 0) d->at_end = 1;
    return d->len > 0;
#else
    d->len = 0;
    while (d->len == 0) {
        if (d->ended) return 0;
        ZSTD_outBuffer out = {d->buf, DBUF, 0};
        size_t r = ZSTD_decompressStream(d->dctx, &out, &d->in);
        if (ZSTD_isError(r)) die("corrupt chunk: %s", ZSTD_getErrorName(r));
        d->len = out.pos;
        if (r == 0) d->ended = 1;                                 /* end of the frame (its checksum was verified) */
        else if (d->in.pos == d->in.size && out.pos == 0) die("truncated chunk%s", "");
    }
    return 1;
#endif
}
static void dec_close(Dec *d) {
#ifdef USE_ZSTD_CLI
    /* Closing the pipe before the end makes zstd fail with "broken pipe"; that is expected.  Only a run
     * that delivered its whole output must also have succeeded (zstd checks the frame's checksum). */
    int rc = pclose(d->pipe);
    unlink(tmp_path); tmp_path[0] = 0;
    if (d->at_end && rc != 0) die("zstd failed: the chunk is damaged, or zstd is missing%s", "");
#else
    ZSTD_freeDCtx(d->dctx);
#endif
    free(d->src); free(d->buf);
}
static inline int dec_byte(Dec *d, unsigned *b) {
    if (d->pos == d->len && !dec_fill(d)) return 0;
    *b = d->buf[d->pos++];
    return 1;
}
/* The next term of the chunk: one byte below 255, or 255 + 2 bytes, or 255 FF FF + 4 bytes. */
static int dec_term(Dec *d, u64 *v) {
    unsigned b, lo, hi;
    if (!dec_byte(d, &b)) return 0;
    if (b < 255) { *v = b; return 1; }
    if (!dec_byte(d, &lo) || !dec_byte(d, &hi)) die("truncated term in a chunk%s", "");
    u64 x = lo | (u64)hi << 8;
    if (x < 65535) { *v = x; return 1; }
    x = 0;
    for (int k = 0; k < 4; k++) { if (!dec_byte(d, &b)) die("truncated term in a chunk%s", ""); x |= (u64)b << (8 * k); }
    *v = x;
    return 1;
}
/* Skip m terms.  Bytes below 255 are one term each, so whole stretches are skipped with memchr. */
static void dec_skip(Dec *d, u64 m) {
    while (m > 0) {
        if (d->pos == d->len && !dec_fill(d)) die("a chunk is shorter than the index says%s", "");
        size_t take = d->len - d->pos; if (take > m) take = (size_t)m;
        unsigned char *p = d->buf + d->pos, *q = memchr(p, 255, take);
        if (!q) { d->pos += take; m -= take; continue; }
        d->pos += (size_t)(q - p); m -= (u64)(q - p);
        u64 v; dec_term(d, &v); m--;
    }
}

/* =====================================================================================================
 *  OUTPUT (b-file lines, comma list, or values; indices are kept as a decimal string and incremented)
 * ===================================================================================================== */
static int fmt = 'b';
static FILE *out;
static char *obuf; static size_t obn;
#define OBUF (1 << 22)
static char idx[32]; static int idxlen; static u64 nout;
static void out_flush(void) { if (obn && fwrite(obuf, 1, obn, out) != obn) die("write error%s", ""); obn = 0; }
static void out_start(u64 n) { obuf = xmalloc(OBUF); idxlen = snprintf(idx, sizeof idx, "%llu", (unsigned long long)n); }
static inline void out_term(u64 v) {
    if (obn + 64 > OBUF) out_flush();
    char *p = obuf + obn;
    if (fmt == 'b') { memcpy(p, idx, (size_t)idxlen); p += idxlen; *p++ = ' '; }
    else if (fmt == 'c' && nout) { *p++ = ','; *p++ = ' '; }
    if (v < 10) *p++ = (char)('0' + v);
    else p += snprintf(p, 24, "%llu", (unsigned long long)v);
    if (fmt != 'c') *p++ = '\n';
    obn = (size_t)(p - obuf); nout++;
    int k = idxlen - 1;                                   /* next index */
    while (k >= 0 && idx[k] == '9') idx[k--] = '0';
    if (k >= 0) idx[k]++; else { memmove(idx + 1, idx, (size_t)idxlen); idx[0] = '1'; idxlen++; }
}
static void out_end(void) {
    if (fmt == 'c' && nout) obuf[obn++] = '\n';
    out_flush();
    if (fflush(out) != 0) die("write error%s", "");
}

/* =====================================================================================================
 *  COMMANDS
 * ===================================================================================================== */
/* a(A..B) */
static void cmd_terms(u64 A, u64 B) {
    u64 k0 = chunk_of(A), k1 = chunk_of(B);
    Chunk *c = xmalloc((size_t)(k1 - k0 + 1) * sizeof(Chunk));
    read_chunks(k0, k1, c);
    out_start(A);
    for (u64 k = k0; k <= k1; k++) {
        Chunk *ck = &c[k - k0];
        u64 lo = A > ck->first ? A : ck->first, last = ck->first + ck->nterms - 1, hi = B < last ? B : last;
        Dec d; dec_open(&d, ck);
        dec_skip(&d, lo - ck->first);
        for (u64 n = lo; n <= hi; n++) { u64 v; if (!dec_term(&d, &v)) die("a chunk is shorter than the index says%s", ""); out_term(v); }
        dec_close(&d);
    }
    out_end();
    free(c);
}
/* a(1) + ... + a(N): the stored sum up to the previous chunk, plus the start of N's chunk. */
static void cmd_sum(u64 N) {
    u64 k = chunk_of(N), s = 0;
    Chunk c[2];
    if (k > 0) { read_chunks(k - 1, k, c); s = c[0].sum_end; c[0] = c[1]; } else read_chunks(0, 0, c);
    Dec d; dec_open(&d, &c[0]);
    for (u64 n = c[0].first; n <= N; n++) { u64 v; if (!dec_term(&d, &v)) die("a chunk is shorter than the index says%s", ""); s += v; }
    dec_close(&d);
    fprintf(out, "%llu\n", (unsigned long long)s);
}
/* The height and record tables (small; read whole). */
static unsigned char *read_table(u64 off, u64 n, u64 width) {
    unsigned char *b = xmalloc((size_t)(n * width));
    src_read(off, n * width, b);
    return b;
}
static void cmd_records(void) {
    unsigned char *r = read_table(H.records_off, H.nrecords, 16);
    fprintf(out, "# records of A400000(1..%llu): k, height (A399949(k)), index (A399950(k))\n", (unsigned long long)H.nterms);
    for (u64 k = 0; k < H.nrecords; k++) fprintf(out, "%llu %llu %llu\n", (unsigned long long)k + 1, (unsigned long long)le64(r + 16 * k), (unsigned long long)le64(r + 16 * k + 8));
    free(r);
}
static void cmd_heights(void) {
    unsigned char *t = read_table(H.heights_off, H.nheights, 24);
    fprintf(out, "# every height h in A400000(1..%llu): h, first index (A399763(h)), number of occurrences\n", (unsigned long long)H.nterms);
    for (u64 k = 0; k < H.nheights; k++)
        fprintf(out, "%llu %llu %llu\n", (unsigned long long)le64(t + 24 * k), (unsigned long long)le64(t + 24 * k + 8), (unsigned long long)le64(t + 24 * k + 16));
    free(t);
}
static void cmd_first(u64 h) {
    unsigned char *t = read_table(H.heights_off, H.nheights, 24);
    for (u64 k = 0; k < H.nheights; k++) if (le64(t + 24 * k) == h) {
        fprintf(out, "%llu\n", (unsigned long long)le64(t + 24 * k + 8));
        fprintf(stderr, "(the first building of height %llu is a(%llu); height %llu occurs %llu times in a(1..%llu))\n", (unsigned long long)h,
                (unsigned long long)le64(t + 24 * k + 8), (unsigned long long)h, (unsigned long long)le64(t + 24 * k + 16), (unsigned long long)H.nterms);
        free(t); return;
    }
    fprintf(stderr, "height %llu does not occur in a(1..%llu)\n", (unsigned long long)h, (unsigned long long)H.nterms);
    free(t); exit(1);
}
static void cmd_info(const char *name) {
    unsigned char *t = read_table(H.heights_off, H.nheights, 24);
    u64 mex = 0; for (u64 k = 0; k < H.nheights && le64(t + 24 * k) == mex; k++) mex++;
    free(t);
    char when[64] = "?"; time_t ct = (time_t)H.created; struct tm *tm = gmtime(&ct);
    if (tm) strftime(when, sizeof when, "%Y-%m-%d %H:%M UTC", tm);
    fprintf(out, "%s: A4Z archive of OEIS A400000 (the city-building sequence), created %s\n", name, when);
    fprintf(out, "  terms     a(1) .. a(%llu)\n", (unsigned long long)H.nterms);
    fprintf(out, "  chunks    %llu of %llu terms each (the last %llu), %.2f GB compressed\n", (unsigned long long)H.nchunks,
            (unsigned long long)H.chunk_terms, (unsigned long long)(H.nterms - (H.nchunks - 1) * H.chunk_terms), (double)H.data_bytes / 1e9);
    fprintf(out, "  sum       %llu   (A397740(%llu))\n", (unsigned long long)H.total_sum, (unsigned long long)H.nterms);
    fprintf(out, "  hash      %016llx   (FNV-1a over all terms)\n", (unsigned long long)H.total_hash);
    fprintf(out, "  max       %llu = a(%llu)\n", (unsigned long long)H.max_height, (unsigned long long)H.max_index);
    fprintf(out, "  heights   %llu distinct; the smallest height that does not occur is %llu; %llu records\n", (unsigned long long)H.nheights,
            (unsigned long long)mex, (unsigned long long)H.nrecords);
}
/* Decompress whole chunks k0..k1 and check each against the index; returns the number of bad chunks. */
static u64 verify_chunks(u64 k0, u64 k1, u64 *nterms, int progress) {
    u64 bad = 0, nt = 0;
    Chunk *c = xmalloc((size_t)(k1 - k0 + 2) * sizeof(Chunk));
    if (k0 > 0) read_chunks(k0 - 1, k1, c);
    else { read_chunks(0, k1, c + 1); c[0].hash_end = FNV_OFFSET; c[0].sum_end = 0; c[0].first = 1; c[0].nterms = 0; }
    for (u64 k = k0; k <= k1; k++) {
        const Chunk *p = &c[k - k0], *ck = &c[k - k0 + 1];       /* p: the previous chunk (its running hash and sum) */
        u64 h = p->hash_end, s = p->sum_end, n = 0;
        Dec d; dec_open(&d, ck);
        while (d.pos < d.len || dec_fill(&d)) {                 /* plain bytes in a tight loop, escapes rarely */
            const unsigned char *b = d.buf; size_t j = d.pos, e = d.len;
            while (j < e && b[j] < 255) { h = (h ^ b[j]) * FNV_PRIME; s += b[j]; j++; n++; }
            d.pos = j;
            if (j < e) { u64 v; dec_term(&d, &v); h = (h ^ v) * FNV_PRIME; s += v; n++; }
        }
        dec_close(&d);
        int ok = n == ck->nterms && h == ck->hash_end && s == ck->sum_end && ck->first == p->first + p->nterms;
        if (!ok) { bad++; fprintf(stderr, "FAIL chunk %llu (a(%llu..%llu))\n", (unsigned long long)k, (unsigned long long)ck->first, (unsigned long long)(ck->first + ck->nterms - 1)); }
        nt += n;
        if (progress && k1 > k0 && ((k - k0) % 64 == 63 || k == k1))
            fprintf(stderr, "verified chunks %llu..%llu of %llu..%llu (%llu bad)\n", (unsigned long long)k0, (unsigned long long)k,
                    (unsigned long long)k0, (unsigned long long)k1, (unsigned long long)bad);
    }
    free(c);
    *nterms = nt;
    return bad;
}
/* verify [A B] [-j JOBS]: with JOBS > 1 the chunks are split among that many processes (each needs about 1 GB). */
static const char *arch_name;
static void cmd_verify(u64 A, u64 B, int jobs) {
    u64 k0 = chunk_of(A), k1 = chunk_of(B), nt = 0, bad = 0;
    if (jobs > (int)(k1 - k0 + 1)) jobs = (int)(k1 - k0 + 1);
#ifndef _WIN32
    if (jobs > 1) {
        u64 per = (k1 - k0 + 1 + (u64)jobs - 1) / (u64)jobs; int failed = 0, started = 0;
        fflush(NULL);
        for (int j = 0; j < jobs; j++) {
            u64 lo = k0 + (u64)j * per, hi = lo + per - 1 < k1 ? lo + per - 1 : k1;
            if (lo > k1) break;
            pid_t pid = fork();
            if (pid < 0) die("cannot start a verify process%s", "");
            if (pid == 0) {                                       /* child: its own file handle, its own share */
                if (arch_file && !(arch_file = fopen(arch_name, "rb"))) _exit(3);
                u64 n; u64 b = verify_chunks(lo, hi, &n, 0);
                fprintf(stderr, "chunks %llu..%llu: %s\n", (unsigned long long)lo, (unsigned long long)hi, b ? "FAILED" : "OK");
                _exit(b ? 1 : 0);
            }
            started++;
        }
        for (int j = 0; j < started; j++) { int st; if (wait(&st) < 0 || !WIFEXITED(st) || WEXITSTATUS(st) != 0) failed++; }
        u64 last = k1 + 1 == H.nchunks ? H.nterms : (k1 + 1) * H.chunk_terms;
        fprintf(out, "%s: %llu chunks, a(%llu..%llu), checked against the index by %d processes%s\n", failed ? "FAILED" : "OK",
                (unsigned long long)(k1 - k0 + 1), (unsigned long long)(k0 * H.chunk_terms + 1), (unsigned long long)last, started,
                failed ? "; see the FAIL lines above" : "");
        if (failed) exit(1);
        return;
    }
#endif
    bad = verify_chunks(k0, k1, &nt, 1);
    fprintf(out, "%s: %llu chunks, a(%llu..%llu), %llu terms checked against the index%s\n", bad ? "FAILED" : "OK",
            (unsigned long long)(k1 - k0 + 1), (unsigned long long)(k0 * H.chunk_terms + 1),
            (unsigned long long)(k1 * H.chunk_terms + (k1 + 1 == H.nchunks ? H.nterms - k1 * H.chunk_terms : H.chunk_terms)),
            (unsigned long long)nt, bad ? "; some chunks are wrong" : "");
    if (bad) exit(1);
}

/* =====================================================================================================
 *  MAIN
 * ===================================================================================================== */
/* A whole number: 123, 1e13, 2.5e9, 2^40, or a sum/difference of those (1e13+5, 2^40-1). */
static int parse_atom(const char *s, size_t len, double *v) {
    char t[64]; if (len == 0 || len >= sizeof t) return 0;
    memcpy(t, s, len); t[len] = 0;
    char *end, *c = strchr(t, '^');
    if (c) {                                             /* b^e with whole numbers b, e */
        *c = 0;
        unsigned long long b = strtoull(t, &end, 10); if (*end || end == t) return 0;
        unsigned long long x = strtoull(c + 1, &end, 10); if (*end || end == c + 1 || x > 63) return 0;
        double r = 1; while (x--) r *= (double)b;
        *v = r;
    } else { *v = strtod(t, &end); if (*end || end == t) return 0; }
    return 1;
}
static int parse_num(const char *s, u64 *out) {
    i64 total = 0; const char *p = s; int sign = 1;
    if (*p == '+') p++;
    for (;;) {
        const char *q = p;
        while (*q && !(*q == '+' || *q == '-') ) q++;
        if (q > p && (q[-1] == 'e' || q[-1] == 'E') && *q) { q++; while (*q && *q != '+' && *q != '-') q++; }   /* 1e+13 */
        int digits = 1; for (const char *r = p; r < q; r++) if (*r < '0' || *r > '9') digits = 0;
        if (digits && q > p && q - p <= 18) { i64 x = 0; for (const char *r = p; r < q; r++) x = 10 * x + (*r - '0'); total += sign * x; }
        else { double v; if (!parse_atom(p, (size_t)(q - p), &v) || v < 0 || v > 9e18 || (double)(i64)v != v) return 0; total += sign * (i64)v; }
        if (!*q) break;
        sign = *q == '-' ? -1 : 1; p = q + 1;
    }
    if (total < 0) return 0;
    *out = (u64)total;
    return 1;
}
static u64 num(const char *s) { u64 v; if (!parse_num(s, &v)) die("not a number: %s", s); return v; }
static void usage(void) {
    fprintf(stderr,
        "usage: A400000_view ARCHIVE [command] [-f b|c|v] [-o FILE]\n"
        "  ARCHIVE       the .a4z file, or its http(s):// URL\n"
        "  info          what the archive holds (default)\n"
        "  N             a(N)\n"
        "  A B           a(A..B); B may be +K for K terms\n"
        "  sum N         a(1) + ... + a(N)\n"
        "  records       record heights and their indices\n"
        "  first H       index of the first building of height H\n"
        "  heights       every height with its first index and count\n"
        "  verify [A B]  check the chunks holding a(A..B) against the index (default: all);\n"
        "                -j JOBS splits the work among JOBS processes (about 1 GB each)\n"
        "  -f b|c|v      b-file lines (default), comma list, or values only\n"
        "  -o FILE       write to FILE\n"
        "  numbers: 123, 1e13, 2^40, 1e13+5, ...\n");
    exit(2);
}

int main(int argc, char **argv) {
    const char *arg[8]; int na = 0, jobs = 1; const char *outpath = NULL;
    for (int k = 1; k < argc; k++) {
        if (!strcmp(argv[k], "-f") && k + 1 < argc) { fmt = argv[++k][0]; if (fmt != 'b' && fmt != 'c' && fmt != 'v') usage(); }
        else if (!strcmp(argv[k], "-j") && k + 1 < argc) { jobs = atoi(argv[++k]); if (jobs < 1) usage(); }
        else if (!strcmp(argv[k], "-o") && k + 1 < argc) outpath = argv[++k];
        else if (!strcmp(argv[k], "-h") || !strcmp(argv[k], "--help")) usage();
        else if (na < 8) arg[na++] = argv[k];
        else usage();
    }
    if (na < 1) usage();
#ifdef USE_ZSTD_CLI
    atexit(remove_tmp);
#endif
    arch_name = arg[0];
    open_archive(arg[0]);
    out = outpath ? fopen(outpath, "w") : stdout;
    if (!out) die("cannot open %s", outpath);
    const char *cmd = na > 1 ? arg[1] : "info";
    if (!strcmp(cmd, "info") && na == 2) cmd_info(arg[0]);
    else if (na == 1) cmd_info(arg[0]);
    else if (!strcmp(cmd, "records") && na == 2) cmd_records();
    else if (!strcmp(cmd, "heights") && na == 2) cmd_heights();
    else if (!strcmp(cmd, "first") && na == 3) cmd_first(num(arg[2]));
    else if (!strcmp(cmd, "sum") && na == 3) {
        u64 n = num(arg[2]); if (n < 1 || n > H.nterms) die("the archive holds a(1..N) only; N = %s", "see 'info'");
        cmd_sum(n);
    } else if (!strcmp(cmd, "verify") && (na == 2 || na == 4)) {
        u64 a = na == 4 ? num(arg[2]) : 1, b = na == 4 ? (arg[3][0] == '+' ? a + num(arg[3] + 1) - 1 : num(arg[3])) : H.nterms;
        if (a < 1 || b < a || b > H.nterms) die("bad range%s", "");
        cmd_verify(a, b, jobs);
    } else if (na == 2 || na == 3) {
        u64 a = num(arg[1]), b = na == 3 ? (arg[2][0] == '+' ? a + num(arg[2] + 1) - 1 : num(arg[2])) : a;
        if (a < 1 || b < a) die("bad range%s", "");
        if (b > H.nterms) { fprintf(stderr, "A400000_view: the archive holds a(1..%llu)\n", (unsigned long long)H.nterms); exit(1); }
        cmd_terms(a, b);
    } else usage();
    if (out != stdout && fclose(out) != 0) die("write error%s", "");
    return 0;
}
