util_io.c File Reference

#include <unistd.h>
#include <ctype.h>
#include <errno.h>
#include <string.h>
#include <math.h>
#include "util_io.h"

Include dependency graph for util_io.c:

Go to the source code of this file.

Classes
struct	help_entry_t
struct	dem_program_t
struct	dem_col_hash_t
struct	drop_queue_t
struct	drop_group_t
struct	cw_class_stats_t

Macros
#define	HELP_MAX_NAMES   8
#define	HELP_NAME_LEN   32
#define	HELP_MAX_MEMBERS   16

Enumerations
enum	{ DROP_UNK = 0 , DROP_YES = 1 , DROP_NO = 2 }

Functions
void	print_short_help (const char *prog)
	Print short help message listing all allowed parameters to stderr.
void	csr_dump (FILE *stream, const csr_t *const M, const char name[], const int debug)
	Print a binary CSR matrix row by row ('1': nonzero, '.': zero), for DBG_MATRICES.
void	var_init (int argc, char **argv, params_t *const p)
	Initialize parameters and load matrices from command line arguments.
void	var_kill (params_t *const p)
	Clean up and free memory allocated in the params_t structure.
void	read_dem_file (char *fnam, csr_t **p_spaH, csr_t **p_spaL, double pmin, int debug)
	Read a Detector Error Model (DEM) file and construct H and L matrices.
FILE *	nzlist_w_new (const char fnam[], const char comment[])
int	nzlist_w_append (FILE *f, const cw_vec_t *const vec)
FILE *	nzlist_r_open (const char fnam[], long long int *lineno)
cw_vec_t *	nzlist_r_one (FILE *f, cw_vec_t *vec, const char fnam[], long long int *lineno)
long long int	codeword_window_count (const params_t *const p)
	Number of codewords in the collection window (weight up to min_w + dW with outC or maxC, otherwise weight min_w): the codewords exported with outC and counted for maxC.
int	codeword_maxc_reached (const params_t *const p)
	Returns 1 if maxC > 0 and maxC codewords of the collection window are collected.
int	codeword_feed_limit (const params_t *const p)
	Weight limit (exclusive) of RW codewords needed for the min_hits statistic.
cw_vec_t *	codeword_add_maybe (params_t *const p, const int arr[], int weight, int src)
	Add a candidate codeword to the hash table, or count one more hit of a known codeword.
void	compute_min_w_hit_stats (const params_t *const p, int *min_cnt, int *max_cnt, double *avg_cnt, double *stdev_cnt)
	Compute hit count statistics (min, max, avg, stdev) for minimum-weight codewords.
void	codeword_hit_stats (const params_t *const p, cw_hit_stats_t *const st)
	Compute the hit statistics of the min_hits stopping criterion.
void	print_codeword_stats (FILE *stream, const params_t *const p)
	Print accumulated codeword and hit statistics to the given stream.
void	print_rw_step_stats (FILE *stream, const params_t *const p)
	DBG_SUMMARY: the codewords of the lowest three weights in hash found by the RW steps with a uniform random permutation and by those with a window (the distinct codewords and their hits), e.g., to see whether some codewords are found only by the uniform steps (not local in the column order).
int	check_min_hits_convergence (const params_t *const p)
	Check whether the QDistRnd-style hit count stopping condition is met.
int	codeword_hit_check (FILE *stream, const params_t *const p)
	Check the uniformity of the hit counts within each weight class of the representative set.
double	rw_infoset_find_prob (const int n, const int rank, const int w, const int pairs_l)
	Information-set estimate of the probability that a RW step finds a given codeword of weight w.
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)
	Print the information-set estimate of the probability that RW missed a codeword lighter than the upper bound found.
long long int	nzlist_read (const char fnam[], params_t *p)
	Read codewords from a .nz list file and add them to the codeword hash.
void	print_codeword_support (FILE *stream, const char *prefix, const int arr[], const int weight, const int debug)
	Print the support of a codeword (1-based column indices) in one line, for DBG_CODEWORDS.
long long int	nzlist_write (const char fnam[], const char comment[], params_t *p)
	Write the collected codewords from the hash table to a .nz file.

Variables
params_t	prm
params_t *const	p = &prm

Macro Definition Documentation

HELP_MAX_MEMBERS

#define HELP_MAX_MEMBERS   16

Definition at line 372 of file util_io.c.

HELP_MAX_NAMES

#define HELP_MAX_NAMES   8

Definition at line 370 of file util_io.c.

HELP_NAME_LEN

#define HELP_NAME_LEN   32

Definition at line 371 of file util_io.c.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
DROP_UNK
DROP_YES
DROP_NO

Definition at line 1961 of file util_io.c.

Function Documentation

check_min_hits_convergence()

int check_min_hits_convergence

(

const params_t *const

p

)

Check whether the QDistRnd-style hit count stopping condition is met.

Returns 1 if p->min_hits > 0 and the average number of hits <n> (see codeword_hit_stats()) reaches p->min_hits, both for the codewords of weight p->min_w and for the representative set of up to p->cov_cws lowest-weight codewords. A single codeword (e.g., for a classical code with k=1) suffices. Otherwise returns 0.

Parameters

p	Pointer to the params_t structure.

Returns

1 if convergence criterion is met, 0 otherwise.

Definition at line 2906 of file util_io.c.

References cw_hit_stats_t::avg, codeword_hit_stats(), p, and cw_hit_stats_t::set_cws.

Referenced by do_RW_dist().

codeword_add_maybe()

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

Add a candidate codeword to the hash table, or count one more hit of a known codeword.

A codeword already in the hash gets one more hit (cnt). A new codeword is added if:

• its weight is below the minimum weight min_w (always, also with maxC; min_w is updated);
• with outC or maxC (collecting), its weight is at most min_w + max(dW,0), unless maxC codewords of such weights are collected (see codeword_maxc_reached());
• without outC and maxC, its weight equals min_w, unless cov_cws > 0 such codewords are in hash;
• with min_hits > 0 and cov_cws > 0, it is heavier but helps to keep a representative set of cov_cws lowest-weight codewords: the hash holds fewer than cov_cws codewords, or the codeword is lighter than the heaviest codeword in hash. Heavier codewords are then gradually removed (whole weight classes, starting from the heaviest) as long as the remaining ones keep the collection window and at least cov_cws codewords.

Parameters

p	Pointer to the params_t structure.
arr	Array of indices representing the support of the codeword (sorted).
weight	Weight of the codeword (length of arr).
src	Where the codeword was found, for the hit counts of each kind of RW step (CW_SRC_RW_UNIFORM, CW_SRC_RW_WINDOW; CW_SRC_OTHER for CC and finC), see print_rw_step_stats().

Returns

The codeword hash (p->codewords).

Definition at line 2693 of file util_io.c.

References CW_VEC_T::arr, CW_VEC_T::cnt, CW_VEC_T::cnt_u, CW_VEC_T::cnt_w, codeword_maxc_reached(), CW_SRC_RW_UNIFORM, CW_SRC_RW_WINDOW, ERROR, HASH_ADD, HASH_FIND, p, and CW_VEC_T::weight.

Referenced by do_CC_dist(), do_RW_dist(), nzlist_read(), and start_CC_recurs().

codeword_feed_limit()

int codeword_feed_limit

(

const params_t *const

p

)

Weight limit (exclusive) of RW codewords needed for the min_hits statistic.

Returns 0 if min_hits <= 0, the weight min_w + 1 if only the minimum-weight codewords are used (cov_cws <= 0), INT_MAX (any weight) while the representative set is not filled, and otherwise the maximum weight in hash plus one.

Definition at line 2648 of file util_io.c.

References p.

Referenced by do_RW_dist(), and main().

codeword_hit_check()

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

Check the uniformity of the hit counts within each weight class of the representative set.

Codewords of the same weight found with the same probability per RW step have (zero-truncated) Poisson-distributed hit counts. For each weight class of the representative set with at least 2 codewords, the variance of the hit counts is compared with the Poisson variance. A warning is printed if it is significantly larger (p-value < 0.001), the spread (standard deviation) of the hit rates is at least their mean, and, for hit rates with this relative spread (gamma distribution), the probability to miss a lighter codeword is at least 3 times larger than exp(-mu) with equal hit rates (mu: average hits): some codewords are found much more often than others of the same weight, and the estimate exp(-<n>) is optimistic. Takes a single pass over the hash.

Parameters

stream	Output stream for the warnings (typically stderr).
p	Pointer to the params_t structure.

Returns

Number of weight classes with non-uniform hit counts.

Definition at line 2939 of file util_io.c.

References cw_class_stats_t::c_max, cw_class_stats_t::c_min, codeword_hit_stats(), cw_class_stats_t::hits, cw_class_stats_t::n, p, cw_hit_stats_t::set_cws, cw_class_stats_t::sumsq, cw_hit_stats_t::w_hi, and cw_hit_stats_t::w_lo.

Referenced by main().

codeword_hit_stats()

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

Compute the hit statistics of the min_hits stopping criterion.

The representative set consists of the lowest weight classes (starting with min_w) in hash with at least cov_cws codewords in total (all classes if fewer; only min_w if cov_cws <= 0 or min_hits <= 0). As in QDistRnd, <n> estimates the average number of times a codeword is found; a lighter codeword is missed with probability about exp(-<n>), assuming lighter codewords are found at least as often. Heavier codewords make the estimate more conservative.

Parameters

p	Pointer to the params_t structure.
st	Output statistics.

Definition at line 2809 of file util_io.c.

References cw_hit_stats_t::avg, cw_hit_stats_t::min_cws, cw_hit_stats_t::min_hits, p, cw_hit_stats_t::set_cws, cw_hit_stats_t::set_hits, cw_hit_stats_t::w_hi, and cw_hit_stats_t::w_lo.

Referenced by check_min_hits_convergence(), codeword_hit_check(), and print_codeword_stats().

codeword_maxc_reached()

int codeword_maxc_reached

(

const params_t *const

p

)

Returns 1 if maxC > 0 and maxC codewords of the collection window are collected.

Definition at line 2644 of file util_io.c.

References codeword_window_count(), and p.

Referenced by codeword_add_maybe(), do_CC_dist(), do_RW_dist(), nzlist_read(), and start_CC_recurs().

codeword_window_count()

long long int codeword_window_count

(

const params_t *const

p

)

Number of codewords in the collection window (weight up to min_w + dW with outC or maxC, otherwise weight min_w): the codewords exported with outC and counted for maxC.

Definition at line 2635 of file util_io.c.

References p.

Referenced by codeword_maxc_reached().

compute_min_w_hit_stats()

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

Compute hit count statistics (min, max, avg, stdev) for minimum-weight codewords.

Parameters

p	Pointer to the params_t structure.
min_cnt	Output minimum hit count.
max_cnt	Output maximum hit count.
avg_cnt	Output average hit count.
stdev_cnt	Output standard deviation of hit counts.

Definition at line 2745 of file util_io.c.

References CW_VEC_T::cnt, HASH_ITER, p, and CW_VEC_T::weight.

csr_dump()

void csr_dump	(	FILE *	stream,
		const csr_t *const	M,
		const char	name[],
		const int	debug )

Print a binary CSR matrix row by row ('1': nonzero, '.': zero), for DBG_MATRICES.

Nothing is printed without DBG_MATRICES in debug; for n >= 150 columns, only the size is printed unless DBG_LARGE is set.

Parameters

stream	Output stream (typically stderr).
M	The matrix.
name	Name of the matrix, e.g., "H".
debug	Debug bitmap.

Definition at line 186 of file util_io.c.

References csr_t::cols, DBG_LARGE, DBG_MATRICES, ERROR, mzd_from_csr(), and csr_t::rows.

Referenced by do_CC_dist(), and var_init().

nzlist_r_one()

cw_vec_t * nzlist_r_one	(	FILE *	f,
		cw_vec_t *	vec,
		const char	fnam[],
		long long int *	lineno )

Definition at line 2566 of file util_io.c.

References CW_VEC_T::arr, CW_VEC_T::cnt, ERROR, and CW_VEC_T::weight.

Referenced by nzlist_read().

nzlist_r_open()

FILE * nzlist_r_open	(	const char	fnam[],
		long long int *	lineno )

Definition at line 2546 of file util_io.c.

Referenced by nzlist_read().

nzlist_read()

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

Read codewords from a .nz list file and add them to the codeword hash.

Reads the file, verifies that each codeword satisfies the code requirements (orthogonal to H, not orthogonal to L for quantum codes), and adds valid ones to the hash table in params_t.

Parameters

fnam	Path to the .nz file.
p	Pointer to the params_t structure containing the code matrices and hash.

Returns

Number of valid codewords successfully read and added, or -1 on error.

Definition at line 3073 of file util_io.c.

References CW_VEC_T::arr, codeword_add_maybe(), codeword_maxc_reached(), cols_ws_free(), cols_ws_init(), csr_free(), csr_transpose(), CW_SRC_OTHER, DBG_CODEWORDS, DBG_SUMMARY, ERROR, HASH_FIND, HASH_ITER, nzlist_r_one(), nzlist_r_open(), p, print_codeword_support(), and CW_VEC_T::weight.

Referenced by main().

nzlist_w_append()

int nzlist_w_append	(	FILE *	f,
		const cw_vec_t *const	vec )

Definition at line 2534 of file util_io.c.

References CW_VEC_T::arr, ERROR, prm, and CW_VEC_T::weight.

Referenced by nzlist_write().

nzlist_w_new()

FILE * nzlist_w_new	(	const char	fnam[],
		const char	comment[] )

Definition at line 2522 of file util_io.c.

References ERROR.

Referenced by nzlist_write().

nzlist_write()

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

Write the collected codewords from the hash table to a .nz file.

Exports the codewords in the collection window, i.e., of weight up to min_w + dW (min_w: the minimum weight found), in NZLIST format. Heavier codewords kept in the hash only for the min_hits statistic are not exported.

Parameters

fnam	Path to the output .nz file.
comment	An optional comment string to include in the file header.
p	Pointer to the params_t structure containing the codeword hash.

Returns

Number of codewords written, or -1 on error.

Definition at line 3197 of file util_io.c.

References CW_VEC_T::hh, UT_hash_handle::next, nzlist_w_append(), nzlist_w_new(), p, and CW_VEC_T::weight.

Referenced by main().

print_codeword_stats()

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

Print accumulated codeword and hit statistics to the given stream.

One line for the minimum weight (with the min_hits statistic), and one line for each heavier weight class in hash; without DBG_LARGE in p->debug, the weight classes after the 4 lightest heavier ones share one line.

Parameters

stream	Output stream (typically stderr).
p	Pointer to the params_t structure.

Definition at line 2828 of file util_io.c.

References cw_hit_stats_t::avg, cw_class_stats_t::c_max, cw_class_stats_t::c_min, codeword_hit_stats(), DBG_LARGE, cw_class_stats_t::hits, cw_class_stats_t::n, p, cw_hit_stats_t::set_cws, cw_class_stats_t::sumsq, cw_hit_stats_t::w_hi, and cw_hit_stats_t::w_lo.

Referenced by main().

print_codeword_support()

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

Print the support of a codeword (1-based column indices) in one line, for DBG_CODEWORDS.

Prints prefix, the weight, and the first DBG_CW_MAX positions (all of them with DBG_LARGE).

Parameters

stream	Output stream (typically stderr).
prefix	Line prefix, e.g., "# RW codeword".
arr	Sorted 0-based column indices.
weight	Number of indices.
debug	Debug bitmap (DBG_LARGE: no size cutoff).

Definition at line 3186 of file util_io.c.

References DBG_CW_MAX, DBG_LARGE, and prm.

Referenced by nzlist_read().

print_rw_infoset_estimate()

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 )

Print the information-set estimate of the probability that RW missed a codeword lighter than the upper bound found.

Among the weights w_lo..w_hi (not excluded by CC), the weight w with the smallest P1(w) (see rw_infoset_find_prob()) is used: a single codeword of this weight is missed in steps RW steps with uniform random permutations with probability (1 - P1)^steps. Also prints the total number of RW steps for a 1% miss probability (with the fraction steps / steps_total of uniform steps, as in this run; localized windows, used in about half of the steps for n >= 500, are not counted) and, if t_step > 0, the corresponding time.

Parameters

stream	Output stream (typically stderr).
n	Block length (number of columns of H).
rank	Rank of H.
w_lo	Smallest weight to consider (dmin, at least 1).
w_hi	Largest weight to consider (dmax - 1).
steps	Number of completed RW steps with uniform random permutations.
steps_total	Number of all completed RW steps.
t_step	Wall time per RW step in seconds (0: unknown).
pairs_l	The number l of random pivot rows of the buckets of the RW pairs (0: no pairs).

Definition at line 3010 of file util_io.c.

References rw_infoset_find_prob().

Referenced by main().

print_rw_step_stats()

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

DBG_SUMMARY: the codewords of the lowest three weights in hash found by the RW steps with a uniform random permutation and by those with a window (the distinct codewords and their hits), e.g., to see whether some codewords are found only by the uniform steps (not local in the column order).

Definition at line 2881 of file util_io.c.

References CW_VEC_T::cnt_u, CW_VEC_T::cnt_w, HASH_ITER, p, and CW_VEC_T::weight.

Referenced by main().

print_short_help()

void print_short_help

(

const char *

prog

)

Print short help message listing all allowed parameters to stderr.

Parameters

prog	Program name (argv[0]).

Definition at line 95 of file util_io.c.

References DIST_M4RI_VERSION, and SHORT_HELP.

Referenced by var_init().

read_dem_file()

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

Read a Detector Error Model (DEM) file and construct H and L matrices.

Parses a DEM file (e.g. from Stim), filters error events based on pmin, and builds the corresponding sparse check matrix H and logical matrix L.

Parameters

fnam	Path to the DEM file.
p_spaH	Pointer to store the constructed sparse check matrix H.
p_spaL	Pointer to store the constructed sparse logical matrix L.
pmin	Minimum error probability threshold to keep an error event.
debug	Debug print level bitmap.

Definition at line 1728 of file util_io.c.

References csr_from_pairs(), DBG_ARGS, and ERROR.

Referenced by var_init().

rw_infoset_find_prob()

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

Information-set estimate of the probability that a RW step finds a given codeword of weight w.

Model: uniform random information sets. A RW step reduces H (rank r) with a random column order; a codeword is found if exactly one of its w positions is among the k = n - r non-pivot columns: P1(w) = w C(n-w, k-1) / C(n, k). Codewords of weight w > r + 1 are never found (P1 = 0). With the RW pairs (pairs_l > 0, see rw_pairs_bits()), also if exactly two of its positions are non-pivot columns and its other w - 2 positions avoid the pivot rows of the buckets: P2(w) = C(w, 2) C(n-w, k-2) / C(n, k) * C(r - w + 2, l) / C(r, l), and the probability is P1 + P2.

Parameters

n	Block length (number of columns of H).
rank	Rank r of H.
w	Codeword weight.
pairs_l	The number l of random pivot rows of the buckets of the RW pairs (0: no pairs).

Returns

P1(w) + P2(w).

Definition at line 2990 of file util_io.c.

References p.

Referenced by print_rw_infoset_estimate().

var_init()

void var_init	(	int	argc,
		char **	argv,
		params_t *const	p )

Initialize parameters and load matrices from command line arguments.

Parses command line arguments, sets up the parameter structure, loads matrices from specified files (Matrix Market or DEM), constructs logical matrices if needed, and performs consistency checks.

Parameters

argc	Number of command line arguments.
argv	Array of command line argument strings.
p	Pointer to the params_t structure to initialize.

debug: already parsed above

finH

< allow space before file name

finL

< allow space before file name

finG degeneracy generator matrix

< allow space before file name

< allow space before file name

start=a,b,c list of CC start columns

clusters from a listed start column c use only columns > c

dstop: stop once CC certifies dmin >= dstop

create Lx

WARNING: this does not necessarily have minimal row weights

Definition at line 766 of file util_io.c.

References colmask_from_csr(), csr_csr_mul_non_zero(), csr_dump(), csr_free(), csr_mm_read(), DBG_ARGS, DBG_PARAMS, DBG_SUMMARY, DIST_M4RI_VERSION, ERROR, Lx_for_CSS_code(), MAX_W, MORE_HELP, p, print_short_help(), read_dem_file(), RW_PAIRS_MAX_BITS, and USAGE.

Referenced by main().

var_kill()

void var_kill

(

params_t *const

p

)

Clean up and free memory allocated in the params_t structure.

Frees sparse matrices (spaH, spaG, spaL) and codeword lists.

Parameters

p	Pointer to the params_t structure to clean up.

Definition at line 1492 of file util_io.c.

References colmask_free(), csr_free(), HASH_DEL, HASH_ITER, and p.

Referenced by main().

Variable Documentation

p

params_t* const p = &prm

Definition at line 93 of file util_io.c.

Referenced by addto(), check_min_hits_convergence(), codeword_add_maybe(), codeword_feed_limit(), codeword_hit_check(), codeword_hit_stats(), codeword_maxc_reached(), codeword_window_count(), colmask_from_csr(), compute_min_w_hit_stats(), csr_apply_perm(), csr_csr_mul_non_zero(), csr_free(), csr_max_row_wght(), csr_mzd_mul(), csr_out(), csr_transpose(), do_CC_dist(), do_RW_dist(), localized_window_perm(), main(), make_err(), MERGE_SORT_IN_PLACE(), mm_read_banner(), mzd_from_csr(), mzp_out(), nzlist_read(), nzlist_write(), perm_p(), perm_p_trans(), print_codeword_stats(), print_rw_step_stats(), rw_infoset_find_prob(), start_CC_recurs(), syndrome_bit_count(), syndrome_vector(), var_init(), and var_kill().

prm

params_t prm

Definition at line 8 of file util_io.c.

Referenced by main(), mzd_generator_from_csr(), nzlist_w_append(), and print_codeword_support().