util_io.h

Go to the documentation of this file.

#ifndef UTIL_IO_H
/************************************************************************ 
 * qLDPC code input utility routines for distance/decoder package               
 *                                                                      
 * currently: CSS only 
 *
 * author: Leonid Pryadko <leonid.pryadko@ucr.edu> 
 ************************************************************************/
#define UTIL_IO_H
 
#include <inttypes.h>
#include <strings.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <limits.h>
#include <m4ri/m4ri.h>
 
#include "mmio.h"
#include "uthash.h"
#include "util_hash.h"
#include "util_m4ri.h"
 
#define _maybe_unused __attribute__((unused))
 
/* Debug output bitmap (`debug=[int]`, see MORE_HELP), sorted by usability (lower bits are more informative).
 * Diagnostic output goes to stderr (the legacy dist_m4ri_old also prints to stdout).  Multiple `debug=` arguments
 * are OR-combined, the first one replaces the default DBG_DEFAULT.  Bits 512, 1024, and 8192..32768 are reserved;
 * bits 65536 and above are reserved for the Python wrapper dist_m4ri.py (ignored by the binaries).
 * (util_hash.h uses the literal value of DBG_LEGACY, as it may be included first.) */
#define DBG_SUMMARY   1    
#define DBG_PROGRESS  2    
#define DBG_STATUS    4    
#define DBG_TIMING    8    
#define DBG_PARAMS    16   
#define DBG_CODEWORDS 32   
#define DBG_ARGS      64   
#define DBG_MATRICES  128  
#define DBG_CWDUMP    256  
#define DBG_LARGE     2048 
#define DBG_LEGACY    4096 
#define DBG_DEFAULT   (DBG_SUMMARY | DBG_PROGRESS)
#define DBG_CW_MAX    25   
 
//static const int max_row_wt=10; 
 
#define MAX_W 100 
struct CW_VEC_T;
typedef struct CW_VEC_T cw_vec_t;
typedef struct{
  int debug; /* debug output bitmap, see DBG_SUMMARY etc. (default DBG_DEFAULT) */
  int classical; /* 1 for a classical code, i.e., no `G=Hz` matrix*/
  int css; /* 1: css, 0: non-css -- currently not supported */
  int method; /* bitmap. 1: random window; 2: cluster; 3: both */
  int steps; /* how many RW decoding steps */
  int smax; 
  int wmax; 
  int dmin; 
  int dmax; 
  int wmin; 
  int noscan; 
  int seed;/* rng seed, set=0 for automatic */
  int dist; /* target distance of the code */
  int dist_max; /* distance actually checked */
  int dist_min; /* distance actually checked */
  int max_row_wgt_H; /* needed for C */
  int max_col_wgt_H; /* needed ? */
  int swei[MAX_W]; 
  int *start_list; 
  int start_num;   
  int start_scan;  
  int cbeg; 
  int cend; 
  //  int linear; /* not supported */
  int n0;  /* code length, =nvar for css, (nvar/2) for non-css */
  int nvar; /* actual n = matrix size */
  int nchk; /* actual k = number of codewords */
  long long int maxC;
  int dW;
  char *finC;
  char *outC;
  int irred; /* 1 (default): only irreducible codewords are recorded, i.e., not the union of a codeword and a disjoint
              * nonzero zero-syndrome vector (CC codewords and RW pairs are filtered, finC codewords are replaced by an
              * irreducible nontrivial part); 0: expert, all codewords as before 0.14.8 */
  int ortho; /* 1 (default): with finG, check that the rows of H and G are orthogonal (H G^T = 0); 0: expert, not
              * checked (the caller guarantees it) */
  cw_vec_t *codewords; /* hash of codewords: the collection window (weight up to min_w + dW with outC or maxC)
                          and the representative set for `min_hits`, see codeword_add_maybe() */
  long long int num_cws; /* number of codewords in hash */
  int min_w;             /* minimum weight of the codewords in hash (INT_MAX: none) */
  int cw_max_w;          /* maximum weight of the codewords in hash (0: none) */
  long long int *cw_cnt_w;  /* number of codewords of each weight in hash (size nvar+2, allocated on first use) */
  long long int *cw_hits_w; /* total hits of the codewords of each weight in hash (same size) */
  char *fdem;
  double pmin;
  int merge;       /* 1: merge the equal columns of a DEM (same detectors and observables), see dem_merge_columns() */
  int nvar_orig;   /* number of columns before merging (and dropping) the columns of a DEM (0: not changed) */
  int *col_orig;   /* column -> its original column (the first one of its class; NULL: not changed) */
  int *col_class;  /* original column -> column (-1: dropped, see dem_drop_detectors(); NULL: not changed) */
  int nvar_merged; /* number of columns after merging the equal columns of a DEM (0: not merged) */
  char *fdrop;     /* file with the detectors to drop from a DEM if this is exact, see dem_drop_detectors() */
  int drop_mode;   /* drop=0: keep all detectors, drop=1 or drop=auto (default): find the detectors to drop
                      (dem_drop_auto()), 2: drop=FILE (fdrop) */
  int drop_set;    /* 1: drop= given explicitly */
  int drop_none;   /* 1: drop=auto found no detector which can be dropped exactly */
  int *drop_list;  /* the detectors dropped (0-based, increasing; ndrop of them), for outD */
  char *outD;      /* file to write the detectors dropped from a DEM to (outD=FILE) */
  int ndrop;       /* number of detectors dropped (0: none, or not verified) */
  int ndrop_rows;  /* number of detectors (rows of H) before dropping */
  int ndrop_cols;  /* number of columns which touch the dropped detectors (replaced by their twins) */
  int drop_A;      /* 1: the twins have other observables (L(twin) = L + A H with A != 0) */
  int sort_rows;   /* 1: sort the rows of H by increasing weight (stable) for CC, see csr_sort_rows_by_weight();
                      -1 (default): 1 for matrices, 0 for a DEM */
  int rows_sorted; /* 1: sort_rows changed the order of the rows of H */
  int cc_prune;    /* the CC search with smax = 0: 0 the walk of the first unsatisfied row (cc_walk(), before 0.15.0),
                      1 (default) the branch and bound (cc_bnb()), 2 the branch and bound with the cover bounds */
  char *finH;
  char *finG;
  char *finL;
  char *fin;
  csr_t *spaH;
  csr_t *spaG;
  csr_t *spaL;
  colmask_t *maskL; /* column masks of L for fast checks L c != 0 (NULL for a classical code), see var_init() */
  int threads; /* number of threads to use (0 for auto) */
  int dexp;    /* expected distance value (0 for auto/none) */
  int dstop;   /* stop target for the lower bound: the run ends once CC certifies dmin >= dstop (0: off); unlike dmax,
                  not an upper bound, and not reported as dmax */
  double timeout; /* timeout in seconds (default 60.0, 0 for infinite) */
  int nothrottle; /* 1: disable automatic thread throttling */
  int chunk_size; /* RW chunk/batch size (0 for auto) */
  int ksub;       /* RW subspace dimension sampled from ker(H) (0 for full H); experimental, should not be used */
  int kwin;       /* RW localized window size W, used in every step (0: uniform random permutations, and for n >= 500
                     an index window of win_hyb columns on every other step, see rw_hybrid_window(); < 0: no
                     windows) */
  int win_mode;   /* RW window mode: 0 = Tanner BFS, 1 = index proximity */
  int win_hyb;    /* window size of the hybrid RW steps (kwin=0, n >= 500: an index window on every other step); 0:
                     256 columns for a DEM, 512 for matrices (see rw_hybrid_window()) */
  int pairs;      /* RW pairs of non-pivot columns (p=2) agreeing on `pairs` random pivot rows (0: off; -1: auto, see
                     rw_pairs_bits()) */
  int round_D;    /* the rounds of a DEM (debug&1, see dem_round_estimate()): detectors per round (0: none found) */
  int round_L;    /* columns per round, n D / m (0: none found) */
  double round_score; /* the score of the estimate (accepted if >= 0.5; -1: not estimated) */
  int min_hits;   /* RW stopping criterion: average hits <n> per lowest-weight cw (0 = off) */
  int cov_cws;    /* RW stopping criterion: size of the representative set of lowest-weight cws (default 100) */
  int refresh;    /* RW steps interval for adaptive basis refresh (0 = off, auto 5000 if ksub>0) */
} params_t;
 
static inline int minint(const int a, const int b) { return (a < b) ? a : b; }
// #define MININT(a,b) do{ int t1=(a); int t2=(b); t1<t2? t1 :t2; } while(0)
 
/* The original (1-based in output: + 1) column of the column j: different only after merging the equal columns of a
 * DEM (see dem_merge_columns()) */
static inline int col_orig_index(const params_t * const p, const int j) { return p->col_orig ? p->col_orig[j] : j; }
 
extern params_t prm;
void var_init(int argc, char **argv, params_t * const p);

void var_kill(params_t * const p);

void read_dem_file(char *fnam, csr_t **p_spaH, csr_t **p_spaL, double pmin, int debug);

long long int nzlist_read(const char fnam[], params_t *p);

long long int nzlist_write(const char fnam[], const char comment[], params_t *p);

cw_vec_t * codeword_add_maybe(params_t * const p, const int arr[], int weight, int src);

enum { CW_SRC_OTHER = 0, CW_SRC_RW_UNIFORM = 1, CW_SRC_RW_WINDOW = 2 };

void print_rw_step_stats(FILE *stream, const params_t * const p);

static inline int rw_hybrid_window(const params_t * const p, const int nvar) {
  const int w = (p->win_hyb > 0) ? p->win_hyb : (p->fdem ? 256 : 512);
  const int cap = (nvar * 3) / 4;
  return (w < cap) ? w : cap;
}

#define RW_PAIRS_MAX_BITS 64

#define RW_PAIRS_KEEP 0.8

#define RW_PAIRS_WORK 16.0

#define RW_PAIRS_FREE 1048576.0

static inline double rw_pairs_keep(const int rank, const int w, const int l) {
  double q = 1.0;
  for (int i = 0; i < w - 2; i++) {
    if (rank - l - i <= 0) return 0.0;
    q *= (double)(rank - l - i) / (double)(rank - i);
  }
  return q;
}

static inline int rw_pairs_min_bits(const int nvar, const int rank) {
  const double k = (double)(nvar - rank);
  double budget = (double)rank * (double)nvar / RW_PAIRS_WORK;
  if (budget < RW_PAIRS_FREE) budget = RW_PAIRS_FREE;
  int l = 1;
  double pairs = k * k / 4.0; /* (n - r)^2 / 2^(l+1) */
  while ((l < RW_PAIRS_MAX_BITS) && (pairs > budget)) {
    l++;
    pairs /= 2.0;
  }
  return l;
}

static inline int rw_pairs_bits(const params_t * const p, const int nvar, const int rank, const int w) {
  const int k = nvar - rank;
  if ((p->pairs == 0) || (k < 2) || (rank < 1) || (w < 2)) return 0;
  int l = p->pairs;
  if (l < 0) {
    l = 1;
    while ((l < RW_PAIRS_MAX_BITS) && (((uint64_t)1 << l) < (uint64_t)k)) l++;
    const int lmin = rw_pairs_min_bits(nvar, rank);
    while ((l > 1) && (l > lmin) && (rw_pairs_keep(rank, w, l) < RW_PAIRS_KEEP)) l--;
  }
  return (l < rank) ? l : rank;
}

long long int codeword_window_count(const params_t * const p);

int codeword_maxc_reached(const params_t * const p);

int codeword_feed_limit(const params_t * const p);

static inline int codeword_rw_limit(const params_t * const p, const int cur_dmax, const int feed) {
  const int lim_max = p->nvar + 1;
  if (cur_dmax <= 0) return lim_max;
  long long int lim = cur_dmax;
  if ((p->outC != NULL || p->maxC > 0) && p->dW >= 0) lim = (long long int)cur_dmax + p->dW + 1;
  if (feed > lim) lim = feed;
  return (lim < lim_max) ? (int)lim : lim_max;
}

typedef struct {
  long long int min_cws;  
  long long int min_hits; 
  long long int set_cws;  
  long long int set_hits; 
  int w_lo;               
  int w_hi;               
  double avg;             
} cw_hit_stats_t;

void codeword_hit_stats(const params_t * const p, cw_hit_stats_t * const st);

int check_min_hits_convergence(const params_t * const p);

int codeword_hit_check(FILE *stream, const params_t * const p);

double rw_infoset_find_prob(const int n, const int rank, const int w, const int pairs_l);

void print_rw_infoset_estimate(FILE *stream, const int n, const int rank, const int w_lo, const int w_hi,
                               const long steps, const long steps_total, const double t_step, const int pairs_l);

void compute_min_w_hit_stats(const params_t * const p, int *min_cnt, int *max_cnt,
                             double *avg_cnt, double *stdev_cnt);

void print_codeword_stats(FILE *stream, const params_t * const p);

void print_codeword_support(FILE *stream, const char *prefix, const int arr[], const int weight, const int debug);

void csr_dump(FILE *stream, const csr_t * const M, const char name[], const int debug);
 
#define DIST_M4RI_VERSION "0.16.1"

void print_short_help(const char *prog);
 
#define SHORT_HELP \
  "%s (version %s): calculate distance of a classical or quantum CSS code\n" \
  "Usage: %s [method=1|2|3] [parameter=value ...]\n\n" \
  "Allowed parameters:\n" \
  "  method, finH, finG, finL, fin, fdem, pmin, merge, drop, outD, classical, css,\n" \
  "  steps, wmin, wmax, dmin, dmax, dstop, dexp (dest), smax, start, start_scan,\n" \
  "  sort_rows, cc_prune, cbeg, cend, noscan, threads, timeout, nothrottle,\n" \
  "  chunk_size (batch), ksub, kwin (win), win_mode, win_hyb, pairs, min_hits,\n" \
  "  cov_cws, refresh, finC, outC, maxC, dW, irred, ortho, seed, debug\n\n" \
  "Help options:\n" \
  "  -h, --help    : display help for commonly used parameters (fits 80 rows; --help TOPIC: as --morehelp TOPIC)\n" \
  "  --morehelp    : display full help for all available parameters (or for TOPIC: --morehelp TOPIC)\n"
 
#define USAGE \
  "%s (version %s): calculate distance of a classical or quantum CSS code\n" \
  "Usage: %s [method=1|2|3] [parameter=value ...]\n\n" \
  "Calculation method:\n" \
  "  method=[int]       1: Random Window (RW) algorithm (upper bound)\n" \
  "                     2: Connected Cluster (CC) algorithm (lower bound / exact)\n" \
  "                     3: Bracketing mode (concurrent RW and CC) (default: 3)\n\n" \
  "Input matrices (Matrix Market .mmx/.mtx format or Stim DEM):\n" \
  "  finH=[file]        Parity check matrix H (classical) or Hx (CSS quantum)\n" \
  "  finG=[file]        Hz check matrix (quantum CSS code only)\n" \
  "  finL=[file]        Lx logical operator matrix (quantum CSS code only)\n" \
  "                     Note: Either L=Lx or G=Hz is required for quantum CSS codes\n" \
  "  fin=[str]          Base name for CSS matrices (loads ${fin}X.mtx, ${fin}Z.mtx)\n" \
  "  fdem=[file]        Stim detector error model (DEM) file\n" \
  "  pmin=[float]       Minimum error probability threshold to keep for DEM (0.0)\n" \
  "  merge=[0|1]        Merge equal DEM columns (exact; codewords use the first one) (1)\n" \
  "  drop=[auto|file]   DEM detectors to drop if exact: auto=1 (default), 0 (none), or a file\n" \
  "  outD=[file]        Write the DEM detectors dropped (0-based) to file\n" \
  "  classical=[0|1]    1: classical code (Hx only), 0: quantum CSS (auto-detected)\n\n" \
  "Distance bounds and guidance:\n" \
  "  dmin=[int]         Certified lower bound on distance (CC starts from dmin) (1)\n" \
  "  dmax=[int]         Known upper bound on distance (CC up to w=dmax-1 only) (0)\n" \
  "  dstop=[int]        Stop once CC certifies dmin>=dstop (not an upper bound) (0)\n" \
  "  dexp=[int]         Expected distance for method=3 thread allocation (alias: dest) (0)\n\n" \
  "Search limits and stopping criteria:\n" \
  "  steps=[int]        Maximum RW decoding steps / information sets (100000)\n" \
  "  wmax=[int]         Maximum cluster weight to search in CC (0=until bound/timeout)\n" \
  "  wmin=[int]         Stop immediately if cw with weight <= wmin is found (1)\n" \
  "  min_hits=[int]     Stop RW when lowest-wt cws are hit min_hits times on average (5)\n" \
  "  timeout=[sec]      Execution timeout in seconds, 0 for infinite (60.0)\n\n" \
  "Multithreading and RW optimization:\n" \
  "  threads=[int]      Max worker threads to use (0: all logical CPUs) (0)\n" \
  "  ksub=[int]         EXPERIMENTAL, do not use: subspace dimension sampled from ker(H) for RW (0)\n" \
  "  kwin=[int]         Localized column permutation window size W (0: auto/hybrid) (0)\n\n" \
  "Codeword collection:\n" \
  "  outC=[file]        Export found min-weight codewords (up to +dW) to file (.nz format)\n" \
  "  finC=[file]        Import initial codewords from file (.nz format)\n" \
  "  maxC=[int]         Maximum number of codewords to collect (0 for unlimited) (0)\n" \
  "  dW=[int]           Collect codewords up to the minimum weight found + dW (0)\n\n" \
  "Extra parameters (see --morehelp for details):\n" \
  "  smax=[int] (0)         Max syndrome weight for confinement profile (0 to disable)\n" \
  "  noscan=[0|1] (0)       Expert, method 2: CC at w=wmax only (no lower bound!)\n" \
  "  start=[list] (-1)      Expert: CC from listed columns only, e.g. start=0,48\n" \
  "  start_scan=[0|1] (0)   Expert, with start: clusters from column c use only columns > c\n" \
  "  cbeg/cend=[int] (-1)   Expert: CC start column range, for split runs\n" \
  "  irred=[0|1] (1)        Expert: 0 records also reducible codewords (cw + disjoint 0-syndrome vector)\n" \
  "  ortho=[0|1] (1)        Expert: 0 skips the check H G^T = 0 of finG (valid only if it holds)\n" \
  "  sort_rows=[0|1] (1)    Sort the rows of H by weight for CC (default 0 with fdem)\n" \
  "  cc_prune=[0|1|2] (1)   CC search: 0 first-row walk, 1 branch and bound, 2 also cover bounds\n" \
  "  nothrottle=[0|1] (0)   Disable thread throttling (also --no-throttle)\n" \
  "  chunk_size=[int] (0)   RW batch chunk size (0: auto, alias: batch)\n" \
  "  win_mode=[0|1] (0)     Window mode: 0=Tanner BFS, 1=index proximity\n" \
  "  win_hyb=[int] (0)      Hybrid RW window size (0: 256 for a DEM, 512 otherwise)\n" \
  "  pairs=[int] (-1)       RW pairs of non-pivot columns (p=2; -1: auto, 0: off)\n" \
  "  cov_cws=[int] (100)    Number of lowest-wt cws used for the min_hits statistic\n" \
  "  refresh=[int] (0)      RW steps between ker(H) basis refreshes (experimental ksub only; 5000 if ksub>0)\n" \
  "  seed=[int] (0)         RNG seed [0 for time(NULL)]\n" \
  "  debug=[int] (3)        Debug bitmask (0: silent, 1: summary, 2: progress, ...)\n\n" \
  "Help options:\n" \
  "  -h, --help         Display this help message (--help TOPIC: the same as --morehelp TOPIC)\n" \
  "  --morehelp         Display full help for all parameters (--morehelp TOPIC: only TOPIC, e.g., maxC or windows)\n" \
  "  --version          Display program version\n"
 
#define MORE_HELP \
  "%s (version %s): calculate distance of a classical or quantum CSS code\n" \
  "Usage: %s [method=1|2|3] [parameter=value ...]\n\n" \
  "Calculation method:\n" \
  "  method=[int]       Bitmap / identifier for calculation method (default: 3):\n" \
  "                     1: Random Window (RW) algorithm (upper bound)\n" \
  "                        Finds an upper bound on distance by testing random\n" \
  "                        information sets. Fast for finding small codewords.\n" \
  "                     2: Connected Cluster (CC) algorithm (lower bound / exact)\n" \
  "                        Exhaustive cluster search finding a lower bound or exact\n" \
  "                        minimum distance. Guaranteed to find the true code\n" \
  "                        distance if run to completion.\n" \
  "                     3: Bracketing mode (concurrent RW and CC)\n" \
  "                        Dynamically balances CC (lower bound) and RW (upper\n" \
  "                        bound) worker threads based on measured CC and RW times,\n" \
  "                        current bounds [dmin, dmax], remaining timeout, and the\n" \
  "                        distance estimate (dexp).\n\n" \
  "Input matrices and code specification:\n" \
  "  finH=[file]        Parity check matrix H (for classical codes) or Hx (for\n" \
  "                     quantum CSS codes) in Matrix Market (.mmx / .mtx) format.\n" \
  "  finG=[file]        Generator / Hz matrix for quantum CSS codes in Matrix Market\n" \
  "                     format. Used to verify orthogonality (see ortho) and\n" \
  "                     construct logicals.\n" \
  "  ortho=[0|1]        Expert option: 1 (default) checks that the rows of H and G\n" \
  "                     (finG) are orthogonal, H G^T = 0, and stops with an error\n" \
  "                     otherwise; 0 skips the check (a WARNING is printed), e.g.,\n" \
  "                     to screen many codes which are orthogonal by construction\n" \
  "                     (the check takes O(nnz(G) times the column weight of H)\n" \
  "                     operations).  The result is valid only if H G^T = 0.\n" \
  "                     Ignored (with a WARNING) without finG.\n" \
  "  finL=[file]        Logical operator matrix Lx for quantum CSS codes in Matrix\n" \
  "                     Market format.\n" \
  "                     Note: For a quantum CSS code, either finL (Lx) or finG (Hz)\n" \
  "                     must be provided.\n" \
  "  fin=[str]          Base name for the matrix files (default: ../examples/try).\n" \
  "                     Automatically looks for \"${fin}X.mtx\" as finH and\n" \
  "                     \"${fin}Z.mtx\" as finG.  A later finH, finG, or finL\n" \
  "                     cancels fin (with a warning; then no file is taken from\n" \
  "                     fin, so that finH must be given); fin after them is an\n" \
  "                     error.\n" \
  "  fdem=[file]        Detector Error Model file (.dem) generated by Stim.\n" \
  "                     Automatically constructs H and L matrices. Cannot be\n" \
  "                     combined with finH, finG, finL, or fin.\n" \
  "  pmin=[float]       Minimum error probability threshold for DEM parsing (0.0).\n" \
  "                     Error mechanisms with probability < pmin are ignored.\n" \
  "                     Only valid when fdem is specified. The column indices\n" \
  "                     (start, finC, outC) count only the error mechanisms kept:\n" \
  "                     they change with pmin.\n" \
  "  merge=[0|1]        Merge the equal columns of a DEM (error mechanisms with the\n" \
  "                     same detectors and observables) when reading it (default:\n" \
  "                     1; ignored without fdem). Exact: dropping two equal columns\n" \
  "                     of a codeword gives a lighter one, so the distance does not\n" \
  "                     change. Column indices (outC, finC, start, cbeg, cend, and\n" \
  "                     the printed codewords) are those of the DEM; the codewords\n" \
  "                     found use the first one of each set of equal columns (use\n" \
  "                     merge=0 to enumerate the codewords with each of them, or\n" \
  "                     expand=1 of dist_m4ri.py to expand the list found).\n" \
  "  drop=[auto|file]   Detectors of a DEM to drop if this is verified to be exact\n" \
  "                     (default: auto; also drop=1; drop=0 keeps all detectors;\n" \
  "                     only with fdem; not with classical=1): every column\n" \
  "                     touching them has a twin, a column with the same other\n" \
  "                     detectors which touches none of them (no column if it has\n" \
  "                     no other detector), with observables L + A H for one\n" \
  "                     matrix A.  Then the twins replace the columns touching the\n" \
  "                     dropped detectors in any codeword, without increasing its\n" \
  "                     weight, and the search runs on the other detectors and the\n" \
  "                     columns which touch none of them: every codeword found\n" \
  "                     (outC) is a codeword of the full DEM (using only these\n" \
  "                     columns), and the distance is exact.  finC codewords are\n" \
  "                     mapped to the twins.\n" \
  "                     auto: a search for the largest such set (with A = 0) in the\n" \
  "                     DEM, e.g., the minority-basis detectors of a CSS circuit\n" \
  "                     (with the usual noise): a column which contains no other\n" \
  "                     column with the same observables is dropped all or nothing,\n" \
  "                     and the detectors of the other columns follow by propagation\n" \
  "                     (see README.md).\n" \
  "                     file: the detectors listed (0-based, k for Dk, separated by\n" \
  "                     white space or commas; lines starting with '#' or '%%' are\n" \
  "                     comments; write ./1 for a file named 1); if dropping them is\n" \
  "                     not exact, a note is printed and the full DEM is used.\n" \
  "  outD=[file]        Write the detectors dropped from the DEM (0-based, in the\n" \
  "                     format of a drop file; only the comment line if none) to\n" \
  "                     file.  Only valid with fdem.\n" \
  "  classical=[0|1]    Code type override:\n" \
  "                     1: Treat as a classical linear code (H only: finG,\n" \
  "                        finL, or fin is an error, and the observables L of a\n" \
  "                        DEM are discarded).\n" \
  "                     0: Treat as a quantum CSS code (requires L or G matrix).\n" \
  "                     Default: 1 if only finH is given; 0 if finG, finL, fin,\n" \
  "                     or fdem is provided.\n" \
  "  css=[int]          Reserved for future non-CSS quantum code support (1).\n\n" \
  "Distance bounds and search guidance:\n" \
  "  dmin=[int]         Known certified lower bound on distance (default: 1).\n" \
  "                     In CC (method 2/3), cluster search begins at w = dmin.\n" \
  "  dmax=[int]         Known upper bound on distance (default: 0).\n" \
  "                     CC (method 2/3) ends once dmin = dmax (with outC, after the\n" \
  "                     rounds w = dmax..dmax+dW).  In RW (method 1/3), codewords\n" \
  "                     of weight >= dmax are ignored unless collecting codewords\n" \
  "                     or needed for min_hits.\n" \
  "  dstop=[int]        Stop target for the lower bound (default: 0 = off): the run\n" \
  "                     (method 2/3) ends once CC has certified dmin >= dstop, that\n" \
  "                     is, that there is no codeword of weight < dstop (with outC,\n" \
  "                     after the rounds w = dstop..dstop+dW), unless a lighter\n" \
  "                     codeword is found (then the search goes on as usual).\n" \
  "                     Unlike dmax, dstop is not an upper bound and is not\n" \
  "                     reported as dmax: the output is 'dmin w steps', where w is\n" \
  "                     the weight of the lightest codeword found (0: none).  E.g.,\n" \
  "                     dstop=U wmin=U-1 decides whether d >= U, and for a CSS code\n" \
  "                     with d = min(dX, dZ) <= U, dstop=U is all that is needed.\n" \
  "                     With method=1, it only applies to a supplied dmin >= dstop.\n" \
  "  dexp=[int]         Expected code distance (alias: dest) (default: 0).\n" \
  "                     Hint for method=3 (bracketing): as long as RW has found no\n" \
  "                     codeword, CC rounds at w > dexp run only on threads which\n" \
  "                     cannot run RW (CC pauses if RW can use all threads); CC\n" \
  "                     resumes once RW finds a codeword or ends.\n\n" \
  "Search limits and Connected Cluster (CC) options:\n" \
  "  steps=[int]        Maximum number of RW decoding steps / information sets\n" \
  "                     (default: 100000). Ignored in method=2.\n" \
  "  wmin=[int]         Minimum distance threshold (default: 1).\n" \
  "                     If a codeword of weight w <= wmin is found, execution\n" \
  "                     terminates immediately (not when collecting codewords with\n" \
  "                     outC or maxC). Useful for screening codes.\n" \
  "  wmax=[int]         Maximum cluster weight to analyze in CC (default: 0).\n" \
  "                     In method=2, CC terminates after checking weight wmax.\n" \
  "                     0 means continue until a codeword is found, the bounds\n" \
  "                     meet, dmin >= dstop, or timeout (method=2 then needs\n" \
  "                     timeout>0, dmax>0, or dstop>0).\n" \
  "  smax=[int]         Maximum syndrome weight for confinement profile (default: 0).\n" \
  "                     When smax > 0, tracks minimum syndrome weights for each\n" \
  "                     error weight. When smax=0, confinement is not computed.\n" \
  "                     Disabled (with a WARNING) with noscan=1 or dmin > 1, as the\n" \
  "                     small cluster weights are then skipped.\n" \
  "  sort_rows=[0|1]    Sort the rows of H by increasing weight (stable) after\n" \
  "                     reading the input (default: 1 for matrices, finH or fin;\n" \
  "                     0 for a DEM, fdem).  With cc_prune=0, CC extends a cluster\n" \
  "                     by the columns of the first row of its syndrome (in row\n" \
  "                     order), so that light rows first reduce the CC work for\n" \
  "                     matrices with very different row weights, e.g., 1.7-4x\n" \
  "                     with the hook columns of an extended CSS distance, while\n" \
  "                     the detectors of a DEM are in time order, which is better\n" \
  "                     (sorting them made CC 1.3-4x slower).  With cc_prune=1 or\n" \
  "                     2, the order of the rows only breaks ties.  The distance\n" \
  "                     and RW do not depend on the order of the rows; CC finds the\n" \
  "                     same codewords (outC), possibly in another order (with\n" \
  "                     cc_prune=0, also with other hit counts).\n" \
  "  cc_prune=[0|1|2]   The CC search with smax=0 (default: 1).  0: the walk of\n" \
  "                     the versions before 0.15.0: a cluster is extended by the\n" \
  "                     columns of the first unsatisfied row of its syndrome, and\n" \
  "                     a branch is pruned if its syndrome weight exceeds what the\n" \
  "                     columns left can cancel.  1: branch and bound: it branches\n" \
  "                     on the unsatisfied row with the fewest available columns,\n" \
  "                     the columns of the earlier branches are forbidden in the\n" \
  "                     later ones (each codeword is found once: one CC hit), and\n" \
  "                     a branch is pruned by lower bounds on the number of columns\n" \
  "                     needed (an unsatisfied row without available columns, or a\n" \
  "                     packing of unsatisfied rows with disjoint sets of available\n" \
  "                     columns).  2: also the coverage and fractional cover bounds\n" \
  "                     (fewer nodes, more work per node).  All values find the\n" \
  "                     same codewords and distances (doc/cc_completeness.tex);\n" \
  "                     with the expert start list (and start_scan=0), cc_prune=1\n" \
  "                     and 2 forbid the columns listed before the start column.\n" \
  "  noscan=[0|1]       Expert option: 1: run CC only at weight w = wmax, skipping\n" \
  "                     the scan over weights w < wmax (default: 0). Only valid for\n" \
  "                     method=2. WARNING: lower weights are not checked, so a\n" \
  "                     codeword found only sets dmax, and dmin is not raised above\n" \
  "                     the supplied dmin. Certified only if dmin=wmax is given.\n" \
  "  start=[list]       Expert option: comma-separated list of CC start columns,\n" \
  "                     e.g., start=0,48,96 (default: -1 = all columns). Clusters\n" \
  "                     grown from a listed column are NOT limited to larger column\n" \
  "                     indices (unless start_scan=1). Use, e.g., one column per\n" \
  "                     block of a quasi-cyclic code. WARNING: dmin is valid only\n" \
  "                     if a code symmetry maps every minimum-weight codeword to one\n" \
  "                     containing a listed column. Cannot be combined with\n" \
  "                     cbeg/cend.\n" \
  "  start_scan=[0|1]   Expert option, with start (default: 0).  1: a cluster grown\n" \
  "                     from a listed column c only uses the columns > c, as in the\n" \
  "                     scan of all columns (see cbeg).  WARNING: dmin is valid\n" \
  "                     only if a code symmetry maps every minimum-weight codeword\n" \
  "                     to one whose smallest column is listed, e.g., if the listed\n" \
  "                     columns are the smallest columns of the orbits of a group of\n" \
  "                     code automorphisms, one per orbit (start=0,l for the two\n" \
  "                     blocks of a two-block group-algebra code of length 2l over\n" \
  "                     an abelian group).  The later start columns then need less\n" \
  "                     work, the least if each orbit is a range of consecutive\n" \
  "                     columns.  Not with fdem.\n" \
  "  cbeg=[int]         Expert option for split runs: first CC start column\n" \
  "                     (default: -1 = column 0). A cluster started at column i\n" \
  "                     only uses columns > i, so every codeword is found starting\n" \
  "                     from its smallest column.\n" \
  "  cend=[int]         Expert option for split runs: last CC start column\n" \
  "                     (default: -1 = column n-1). WARNING: with cbeg/cend, dmin\n" \
  "                     only covers codewords whose smallest column is in\n" \
  "                     [cbeg,cend]; combine runs covering all columns 0..n-1 by\n" \
  "                     taking the minimum of dmin (and of dmax) over the runs.\n\n" \
  "Codeword collection and export:\n" \
  "  outC=[file]        Export found codewords of weight up to min_w + dW (min_w:\n" \
  "                     minimum weight found) to file in .nz list format.  In\n" \
  "                     method=2/3, once dmin = dmax = d, CC rounds w = d..d+dW\n" \
  "                     enumerate all such irreducible codewords (see irred; unless\n" \
  "                     the timeout is hit; for a DEM, up to the choice of equal\n" \
  "                     columns: see merge).\n" \
  "  finC=[file]        Import initial candidate codewords from file in .nz format.\n" \
  "                     A reducible codeword is replaced by an irreducible part with\n" \
  "                     a nonzero syndrome of L (see irred).  If finC is the same\n" \
  "                     file name as outC, a missing file is not an error.\n" \
  "  maxC=[int]         Maximum number of codewords to collect (default: 0).\n" \
  "                     0 means collect all valid codewords found up to wmax or stop\n" \
  "                     flag. If maxC > 0, halts when maxC codewords are collected.\n" \
  "  dW=[int]           Extra weight window above minimum distance (default: 0).\n" \
  "                     Collects codewords with weight up to min_w + dW.\n" \
  "  irred=[0|1]        Expert option: 1 (default) records only irreducible\n" \
  "                     codewords: a codeword which is the union of a codeword and a\n" \
  "                     disjoint nonzero vector with zero syndrome (e.g., a trivial\n" \
  "                     weight-3 vector of a circuit DEM, from weight d+3 on) is not\n" \
  "                     recorded.  Minimum-weight codewords are always irreducible.\n" \
  "                     Tested for the CC codewords (the rank of their columns of\n" \
  "                     H) and for the RW pairs (the sum of two disjoint vectors\n" \
  "                     with zero syndrome is skipped); a finC codeword is replaced\n" \
  "                     by an irreducible part with a nonzero syndrome of L.\n" \
  "                     0: all codewords are recorded, as before version 0.14.8.\n" \
  "                     (dist_m4ri_old: finC only.)\n\n" \
  "Execution, multithreading, and timing:\n" \
  "  threads=[int]      Maximum number of worker threads to use (default: 0 = all\n" \
  "                     logical CPUs available, i.e., the CPU affinity mask, e.g.,\n" \
  "                     with taskset). Subject to throttling for small codes or\n" \
  "                     large matrices unless nothrottle=1 is set.\n" \
  "  timeout=[sec]      Execution timeout in seconds (default: 60.0, 0 = infinite).\n" \
  "                     In method=3, it guides the CC vs RW thread balance, and a\n" \
  "                     CC round predicted not to finish in time is not started\n" \
  "                     while RW runs (in method=2, and with steps=0, it is started\n" \
  "                     anyway: it may still find a codeword of weight w=dmin).\n" \
  "  nothrottle=[0|1]   Disable automatic thread throttling (default: 0).\n" \
  "                     Aliases: --no-throttle, -no-throttle, nothrottle.\n" \
  "                     By default, threads are throttled for very small codes or\n" \
  "                     large matrices to avoid cache and memory bus thrashing.\n" \
  "                     The limits for small codes (by the RW work) apply in methods\n" \
  "                     1 and 3; method=2 starts 4 threads, and the others once a CC\n" \
  "                     round takes longer (> 2 ms). The limits for large matrices\n" \
  "                     (above 15 MB of dense RW memory per thread: at most 32 RW\n" \
  "                     threads, within a quarter of the physical memory) and for\n" \
  "                     small step counts (ceil(steps/10)) apply to RW threads only;\n" \
  "                     in method=3, CC rounds can use all threads.\n" \
  "  chunk_size=[int]   Maximum RW batch per claim of a worker (default: 0 = adaptive,\n" \
  "                     25 to 500 steps by n and steps). Near the end of the steps,\n" \
  "                     batches shrink to ceil(remaining/(4*RW threads)) steps, so\n" \
  "                     that the RW threads finish together. Alias: batch=[int].\n" \
  "  ksub=[int]         EXPERIMENTAL, should not be used (a warning is printed):\n" \
  "                     subspace dimension sampled from ker(H) in RW (default: 0 =\n" \
  "                     original full-matrix RW). E.g. ksub=32 or 64 keeps working\n" \
  "                     matrices inside L1/L2 cache. Automatically falls back to\n" \
  "                     ksub=0 if m < nu = dim(ker(H)) (with a warning if debug&1).\n" \
  "                     Each step reduces the span of ksub distinct rows of a fixed\n" \
  "                     basis of ker(H), so that a few codewords are found much\n" \
  "                     more often than others, and min_hits may end RW early.\n" \
  "  kwin=[int]         Localized column permutation window size W, used in every RW\n" \
  "                     step (alias: win=[int]).  Default: 0 = automatic hybrid for\n" \
  "                     n>=500: every other step uses an index window (win_mode=1)\n" \
  "                     of win_hyb columns, the other steps uniform random\n" \
  "                     permutations (also for codewords which are not local).\n" \
  "                     kwin=-1 (any negative value): no windows, uniform random\n" \
  "                     permutations in every step.\n" \
  "  win_mode=[0|1]     Window construction mode when kwin > 0 (default: 0):\n" \
  "                     0: Tanner graph BFS neighbors around random seed column.\n" \
  "                     1: Contiguous index proximity window around seed column.\n" \
  "  win_hyb=[int]      Window size of the hybrid RW steps (kwin=0, n>=500; at most\n" \
  "                     3n/4).  Default: 0 = 256 columns for a DEM, 512 for\n" \
  "                     matrices.  The window columns come first in the elimination\n" \
  "                     order; in a DEM, they are errors close in time, which touch\n" \
  "                     few detectors: windows of 192-256 columns find circuit\n" \
  "                     codewords 2-10 times faster than 512, and windows of one\n" \
  "                     round of columns much slower.  With debug&1, the binary\n" \
  "                     prints the rounds of a DEM (estimated from the time\n" \
  "                     translation of its errors: D detectors and L columns per\n" \
  "                     round) and the codewords found by the uniform and by the\n" \
  "                     window steps.\n" \
  "  pairs=[int]        RW pairs of non-pivot columns (p=2, as in Lee-Brickell and\n" \
  "                     Stern): a RW step also finds the codewords with exactly two\n" \
  "                     non-pivot columns, checking only the pairs of columns which\n" \
  "                     agree on pairs=l random pivot rows (at most 64; 0 = off).\n" \
  "                     Default: -1 = auto, about one non-pivot column per bucket,\n" \
  "                     with fewer rows while a codeword of the weight of the upper\n" \
  "                     bound would be kept with probability below 0.8, but enough\n" \
  "                     rows to keep the pairs of a step within about the work of\n" \
  "                     its elimination (e.g., l >= 6 for large circuit DEMs while\n" \
  "                     the upper bound is far above the distance).  The pairs\n" \
  "                     find the minimum-weight codewords of circuit DEMs 7 to 26\n" \
  "                     times faster, and lighter codewords of codes with a large\n" \
  "                     distance.  Not with ksub.  With debug&1, the binary prints\n" \
  "                     the pairs checked per step and the codewords found by pairs\n" \
  "                     and by single columns.\n" \
  "  min_hits=[int]     QDistRnd-style RW stopping criterion (default: 5, 0 = off;\n" \
  "                     alias: max_hits).  Stops RW when the average number of hits\n" \
  "                     <n> per codeword (by all RW steps, with or without windows,\n" \
  "                     and by CC or finC) reaches min_hits, both for the codewords\n" \
  "                     of the minimum weight found and for a representative set of\n" \
  "                     cov_cws lowest-weight codewords (heavier codewords are kept\n" \
  "                     until enough lighter ones are found).  A single codeword\n" \
  "                     suffices.  A lighter codeword is missed with probability\n" \
  "                     about exp(-<n>), assuming that lighter codewords are found\n" \
  "                     at least as often.  With debug&1, a warning is printed at\n" \
  "                     the end if the hit counts of codewords of the same weight\n" \
  "                     are strongly non-uniform (then exp(-<n>) is optimistic),\n" \
  "                     together with an information-set estimate (uniform random\n" \
  "                     information sets) of the probability to miss a lighter\n" \
  "                     codeword and of the RW steps needed for 1%%.\n" \
  "                     With min_hits=0, RW records only the codewords lighter than\n" \
  "                     the upper bound (unless collecting codewords with outC or\n" \
  "                     maxC), so that the repeated hits are not counted.\n" \
  "  cov_cws=[int]      Size of the representative set of lowest-weight codewords\n" \
  "                     for min_hits (default: 100; 0 = only the minimum weight).\n" \
  "                     Without outC and maxC, at most cov_cws minimum-weight\n" \
  "                     codewords are tracked (all if cov_cws=0).  With fewer\n" \
  "                     minimum-weight codewords, a smaller cov_cws may stop RW\n" \
  "                     earlier.\n" \
  "  refresh=[int]      RW steps interval for adaptive ker(H) basis refresh via\n" \
  "                     low-weight codeword exchange and re-echelonization, only\n" \
  "                     with the experimental ksub > 0 (default: 5000 when\n" \
  "                     ksub > 0, 0 = off).\n" \
  "  seed=[int]         Random number generator seed (default: 0; seed<=0 is\n" \
  "                     replaced by time(NULL) + 10*pid - 1000*seed).\n\n" \
  "Debug output bitmap (debug=[int], default: 3):\n" \
  "  Diagnostic output goes to stderr (stdout only has the result line); lower\n" \
  "  bits are more informative.  The value is decimal or hexadecimal (0x...).\n" \
  "  Multiple debug arguments are OR-combined, where the first one replaces the\n" \
  "  default: e.g., debug=0 alone is silent, while debug=4 and debug=0 debug=4\n" \
  "  both give only the periodic status.\n" \
  "    0    : Silent: errors, warnings on the validity of the result (expert\n" \
  "           options, experimental ksub, invalid finC codewords) and on ignored\n" \
  "           or overridden parameters, and the confinement profile with smax > 0\n" \
  "    1    : Summary (default): input matrices (and the rounds of a DEM, RW\n" \
  "           windows), warnings, stop reason, codeword and hit statistics,\n" \
  "           RW information sets, pairs, and step types, export\n" \
  "    2    : Progress (default): run plan (threads, steps, timeout, seed),\n" \
  "           finished CC rounds, new upper bounds, RW convergence\n" \
  "    4    : Periodic status (after 1, 2, 4, ... s, then every 60 s): bounds,\n" \
  "           RW steps and rate, <n>, progress of the current CC round\n" \
  "    8    : Thread allocation and timing: throttling, CC round planning and\n" \
  "           re-planning, waits for RW, predicted vs measured CC work, and the\n" \
  "           nodes of each CC round (calls of the recursion)\n" \
  "    16   : Code parameters rank(H), rank(L) or rank(G), and k (dense\n" \
  "           elimination at startup, slow for large matrices)\n" \
  "    32   : Support (1-based) of each new lightest codeword (RW, CC, finC)\n" \
  "    64   : Command-line arguments, rng seed, and files read\n" \
  "    128  : Matrices H, G, L (if n < 150, unless 2048 is set)\n" \
  "    256  : All codewords in hash with their hit counts (at the end)\n" \
  "    2048 : No size cutoff for matrices, codeword supports, and per-weight\n" \
  "           codeword statistics\n" \
  "    4096 : dist_m4ri_old only: CC recursion and confinement hash traces\n" \
  "  Bits 512, 1024, and 8192 to 32768 are reserved.  Bits 65536 and above are\n" \
  "  reserved for the Python wrapper dist_m4ri.py (ignored by the binary).\n" \
  "  E.g., debug=7 adds the periodic status to the default output, and debug=11\n" \
  "  the thread allocation and timing.\n\n" \
  "Output format (stdout):\n" \
  "  Standard output produces a single line with three space-separated integers:\n" \
  "    dmin dmax rw_steps\n" \
  "  where:\n" \
  "    dmin-1   : Maximum cluster weight analyzed by CC without finding any codeword.\n" \
  "               If CC finds an exact minimum-weight codeword, dmin = dmax = weight.\n" \
  "               With the expert options noscan, start, or cbeg/cend, see the\n" \
  "               warnings above for the validity of dmin.\n" \
  "    dmax     : Smallest weight of a codeword found (by RW or CC, or read with\n" \
  "               finC), or the supplied dmax if smaller (0 if none).\n" \
  "    rw_steps : Number of completed RW steps (0 if CC found exact or method=2).\n\n" \
  "Option groups (--help GROUP prints all entries of GROUP):\n" \
  "  windows            kwin, win_mode, win_hyb\n" \
  "  stopping, stop     steps, wmin, timeout, min_hits, cov_cws\n" \
  "  bounds             dmin, dmax, dstop, dexp, wmax\n" \
  "  dem                fdem, pmin, merge, drop, outD\n" \
  "  matrices, matrix   finH, finG, finL, fin, classical, ortho\n" \
  "  codewords          outC, finC, maxC, dW, irred\n" \
  "  threading          threads, nothrottle, chunk_size\n" \
  "  expert             noscan, start, start_scan, cbeg, cend\n" \
  "  experimental       ksub, refresh\n\n" \
  "Help options:\n" \
  "  -h, --help         Display help for commonly used parameters (fits 80 rows);\n" \
  "                     --help TOPIC is the same as --morehelp TOPIC.\n" \
  "  --morehelp         Display this full help message listing all parameters;\n" \
  "                     --morehelp TOPIC (also --morehelp=TOPIC) displays only the\n" \
  "                     entries of TOPIC, e.g., --morehelp maxC: one or more names\n" \
  "                     separated by commas (e.g., maxC,dW), case-insensitive,\n" \
  "                     without '-' or '_' (and '=VALUE' in --help=TOPIC and\n" \
  "                     --morehelp=TOPIC: a separate argument with '=' is not a\n" \
  "                     TOPIC), including aliases such as dest or batch (and debug\n" \
  "                     for the debug output bitmap); an unknown name gives the\n" \
  "                     closest names on stderr, and the exit code 1.  A group\n" \
  "                     name (see Option groups, also as singular or plural, e.g.,\n" \
  "                     window) gives all entries of the group, and a parameter of\n" \
  "                     a group also the other entries of its group (see also).\n" \
  "  --version          Display program version\n"
 
#define BRIEF_HELP \
  "try \"%s -h\" for help"
 
#endif /* UTIL_IO_H */