#include "sort.h"

Include dependency graph for util_m4ri.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	csr_t
struct	int_pair
struct	colmask_t
struct	cols_ws_t

Macros
#define	SWAPINT(a, b)
#define	ERROR(fmt, ...)
#define	MZD_FIRST_ROW(M)
#define	SETWD(pos)
#define	SETBT(pos)
#define	TIMESWORDSIZE(w)
#define	FIRSTBIT(x)
#define	SORT_NAME rci
#define	SORT_TYPE rci_t
#define	SORT_CMP(x, y)
#define	SORT_DEF static inline

Functions
size_t	mzd_weight (const mzd_t *A)
	Compute the number of set bits (Hamming weight) in a dense matrix A.
size_t	mzd_weight_naive (const mzd_t *A)
	Naive implementation to compute the Hamming weight of a dense matrix A.
size_t	mzd_weight_row (const mzd_t *A, rci_t i)
	Compute the Hamming weight of a specific row in a dense matrix.
rci_t	mzd_gauss_naive (mzd_t M, mzp_t q, int full)
	Perform Gaussian elimination (naive) and return pivot column list.
int	csr_max_row_wght (const csr_t *const p)
	Get the maximum row weight of a CSR sparse matrix.
csr_t *	csr_transpose (csr_t dst, const csr_t const p)
	Transpose a compressed CSR sparse matrix.
mzd_t *	mzd_from_csr (mzd_t dst, const csr_t p)
	Convert a CSR sparse matrix to an MZD dense matrix.
mzd_t *	mzd_generator_from_csr (mzd_t G, const csr_t const H)
	Construct the generator matrix from a parity check matrix in CSR form.
mzd_t *	csr_mzd_mul (mzd_t C, const csr_t S, const mzd_t *B, int clear)
	Multiply a sparse matrix by a dense matrix.
mzd_t *	syndrome_vector (mzd_t syndrome, mzd_t row, csr_t *spaQ, int clear)
	Calculate syndrome vector change.
size_t	product_weight_csr_mzd (const csr_t A, const mzd_t B, int transpose)
	Compute the weight of the product of a sparse matrix and a dense matrix.
int	rand_uniform (const int max)
	Return a uniformly distributed random integer in the range [0, max-1].
mzp_t *	mzp_rand_len (mzp_t *q, rci_t length)
	Generate a random permutation of a given length in-place.
void	mzp_out (mzp_t const *p)
	Print the permutation to stdout.
mzp_t *	perm_p (mzp_t q, const mzp_t p, rci_t start)
	Apply pivot permutation p to permutation q in-place starting from index.
mzp_t *	perm_p_trans (mzp_t q, const mzp_t p, const rci_t start)
	Apply transposed pivot permutation p to permutation q in-place.
csr_t *	csr_free (csr_t *p)
	Free memory allocated for a CSR sparse matrix.
csr_t *	csr_init (csr_t *mat, int rows, int cols, int nzmax)
	Initialize or reallocate a CSR sparse matrix to target size.
void	csr_compress (csr_t *mat)
	Compress CSR matrix (sort indices and remove duplicates/zeros).
csr_t *	csr_from_pairs (csr_t mat, const int nz, int_pair const prs, const int nrows, const int ncols)
	Construct a CSR sparse matrix from an array of coordinate pairs.
void	csr_out (const csr_t *mat)
	Print raw contents of a CSR matrix to stdout.
void	csr_print (const csr_t *const smat, const char str[])
	Print a CSR matrix with a label string (formatted output).
csr_t *	csr_mm_read (char fin, csr_t mat, int transpose)
	Read a sparse matrix from a Matrix Market (.mtx) file into CSR format.
csr_t *	csr_apply_perm (csr_t dst, const csr_t const src, const mzp_t *const perm)
	Permute columns of a CSR sparse matrix.
int	csr_csr_mul_non_zero (const csr_t const A, const csr_t const B)
	Check if the product of two sparse matrices A * B^T is non-zero.
int	syndrome_bit_count (const mzd_t const row, const csr_t const spaQ)
	Compute the Hamming weight of the syndrome of a dense row vector against spaQ.
int	do_reduce (mzd_t row, const mzd_t matP0, const rci_t rankP0)
	Reduce a row vector against a matrix in standard form.
void	make_err (mzd_t *row, double p)
	Generate a random binary error vector with error probability p.
int	do_dist_clus (const csr_t const P, const mzd_t const G, int debug, int wmax, int start, const int rankG)
	(Internal) Run cluster distance algorithm on matrices.
csr_t *	Lx_for_CSS_code (const csr_t const Hx, const csr_t const Hz)
	Construct the logical matrix Lx for a quantum CSS code given Hx and Hz.
mzd_t *	mzd_nullspace (const csr_t *const H)
	Compute the null space basis N = ker(H) of dimension nu x n.
colmask_t *	colmask_from_csr (const csr_t *const A)
	Construct the column bit masks of a sparse binary matrix (see colmask_t).
colmask_t *	colmask_free (colmask_t *cm)
	Free the column masks allocated by colmask_from_csr().
cols_ws_t *	cols_ws_init (const int m)
	Allocate the workspace of csr_cols_rank() and csr_cols_dependency() for a matrix H with m rows.
cols_ws_t *	cols_ws_free (cols_ws_t *ws)
	Free the workspace allocated by cols_ws_init().
int	csr_cols_rank (const csr_t const HT, const int cnt, const int cols[], cols_ws_t const ws)
	Rank of a set of columns of a sparse binary matrix H.
int	csr_cols_dependency (const csr_t const HT, const int cnt, const int cols[], cols_ws_t const ws, int sub[])
	A nonempty proper subset of a set of columns of H with zero sum, if there is one.
void	localized_window_perm (mzp_t perm, int nvar, int seed_col, int kwin, int win_mode, const csr_t spaH, const csr_t mHT, int visited_cols, int visited_checks, int col_queue, int visit_marker, uint64_t rng_state)
	Construct a column permutation with a localized window at the front.
void	refresh_nullspace_basis (mzd_t N, const int cw_arr, int cw_wt, uint64_t *rng_state)
	Refresh the null space basis N under a random column permutation and optionally inject a low-weight codeword via Steinitz exchange.
int	csr_all_ones_in_rowspan (const csr_t *const H)
	Check whether the all-ones vector lies in the row span of a binary CSR matrix H over GF(2).

Macro Definition Documentation

◆ ERROR

#define ERROR	(		fmt,
			... )

Value:

  do{ \
    fprintf (stderr, "%s:%d: *** ERROR in function '%s()' ***\n", __FILE__, __LINE__, __FUNCTION__); \
    fprintf(stderr, " ␛[31;1m " fmt " ␛[0m\n",##__VA_ARGS__); \
    exit(-1); \
  } \
  while(0)

Definition at line 13 of file util_m4ri.h.

Referenced by addto(), codeword_add_maybe(), colmask_from_csr(), cols_ws_init(), csr_all_ones_in_rowspan(), csr_apply_perm(), csr_compress(), csr_csr_mul_non_zero(), csr_dump(), csr_init(), csr_mm_read(), csr_mzd_mul(), csr_transpose(), do_CC_dist(), do_RW_dist(), Lx_for_CSS_code(), main(), make_err(), mzd_from_csr(), mzp_rand_len(), nzlist_r_one(), nzlist_read(), nzlist_w_append(), nzlist_w_new(), perm_p(), perm_p_trans(), read_dem_file(), syndrome_vector(), and var_init().

◆ FIRSTBIT

#define FIRSTBIT ( x )

Value:

__builtin_ctzll(x)

Definition at line 50 of file util_m4ri.h.

◆ MZD_FIRST_ROW

#define MZD_FIRST_ROW ( M )

Value:

((M)->data)

The first word of row 0 of a dense matrix, the start of the rows at distances of M->rowstride words: M->data (all rows in one array) with M4RI 20240729 and later. Older versions (e.g., 20200125, as in Ubuntu 24.04) have no field data: they keep the rows in blocks of up to 2^27 words (recognized by the macro __M4RI_MAX_MZD_BLOCKSIZE), at equal distances unless the matrix spans several blocks (see gauss_one_rows()).

Definition at line 37 of file util_m4ri.h.

◆ SETBT

#define SETBT ( pos )

Value:

((pos)&0x3F)

Definition at line 47 of file util_m4ri.h.

◆ SETWD

#define SETWD ( pos )

Value:

((pos)>>6)

macros from nauty.h SETWD(pos) gives the setword in which pos is located SETBT(pos) gives the location of bit pos in a setword

Definition at line 46 of file util_m4ri.h.

◆ SORT_CMP

#define SORT_CMP	(		x,
			y )

Value:

((x) - (y))

Definition at line 160 of file util_m4ri.h.

◆ SORT_DEF

#define SORT_DEF static inline

Definition at line 161 of file util_m4ri.h.

◆ SORT_NAME

#define SORT_NAME rci

Definition at line 158 of file util_m4ri.h.

◆ SORT_TYPE

#define SORT_TYPE rci_t

Definition at line 159 of file util_m4ri.h.

◆ SWAPINT

#define SWAPINT	(		a,
			b )

Value:

do{ int t=a; a=b; b=t; } while(0)

Definition at line 11 of file util_m4ri.h.

Referenced by localized_window_perm(), perm_p(), and perm_p_trans().

◆ TIMESWORDSIZE

#define TIMESWORDSIZE ( w )

Value:

((w)<<6) /* w*WORDSIZE */

Definition at line 48 of file util_m4ri.h.

Function Documentation

◆ colmask_free()

colmask_t * colmask_free ( colmask_t * cm )

Free the column masks allocated by colmask_from_csr().

Parameters

cm	Column masks (may be NULL).

Returns: Always returns NULL.

Definition at line 1003 of file util_m4ri.c.

References colmask_t::mask.

Referenced by var_kill().

◆ colmask_from_csr()

colmask_t * colmask_from_csr ( const csr_t *const A )

Construct the column bit masks of a sparse binary matrix (see colmask_t).

Duplicate entries of A cancel (mod 2), as in sparse_syndrome_non_zero().

Parameters

A	Sparse matrix in CSR form.

Returns: Newly allocated column masks (free with colmask_free()).

Definition at line 985 of file util_m4ri.c.

References colmask_t::cols, csr_t::cols, ERROR, csr_t::i, colmask_t::kw, colmask_t::mask, csr_t::nz, csr_t::p, p, colmask_t::rows, and csr_t::rows.

Referenced by var_init().

◆ cols_ws_free()

cols_ws_t * cols_ws_free ( cols_ws_t * ws )

Free the workspace allocated by cols_ws_init().

Parameters

ws	Workspace (may be NULL).

Returns: Always returns NULL.

Definition at line 1022 of file util_m4ri.c.

References cols_ws_t::bits, cols_ws_t::rlist, and cols_ws_t::rmap.

Referenced by nzlist_read().

◆ cols_ws_init()

cols_ws_t * cols_ws_init ( const int m )

Allocate the workspace of csr_cols_rank() and csr_cols_dependency() for a matrix H with m rows.

Parameters

m	Number of rows of H.

Returns: Newly allocated workspace (free with cols_ws_free()).

Definition at line 1011 of file util_m4ri.c.

References ERROR, cols_ws_t::m, cols_ws_t::rlist, and cols_ws_t::rmap.

Referenced by nzlist_read().

◆ csr_all_ones_in_rowspan()

int csr_all_ones_in_rowspan ( const csr_t *const H )

Check whether the all-ones vector lies in the row span of a binary CSR matrix H over GF(2).

When 1_n is in rowspan(H), every vector c in ker(H) satisfies 1_n . c = 0 (mod 2), so all codewords have even Hamming weight.

Parameters

H	Binary matrix in compressed CSR form.

Returns: 1 if the all-ones vector is in rowspan(H), 0 otherwise.

Definition at line 1312 of file util_m4ri.c.

References csr_t::cols, ERROR, csr_t::i, mzd_from_csr(), csr_t::nz, csr_t::p, and csr_t::rows.

Referenced by main().

◆ csr_apply_perm()

csr_t * csr_apply_perm	(	csr_t *	dst,
		const csr_t *const	src,
		const mzp_t *const	perm )

Permute columns of a CSR sparse matrix.

Parameters

dst	Destination sparse matrix (can be NULL).
src	Source sparse matrix.
perm	Column permutation to apply.

Returns: Pointer to the permuted sparse matrix.

Permute columns of a CSR matrix with permutation perm.

Definition at line 798 of file util_m4ri.c.

References csr_t::cols, csr_compress(), csr_init(), ERROR, csr_t::i, csr_t::nz, csr_t::nzmax, csr_t::p, p, and csr_t::rows.

Referenced by Lx_for_CSS_code().

◆ csr_cols_dependency()

int csr_cols_dependency	(	const csr_t *const	HT,
		const int	cnt,
		const int	cols[],
		cols_ws_t *const	ws,
		int	sub[] )

A nonempty proper subset of a set of columns of H with zero sum, if there is one.

The kernel of the columns restricted to the rows they touch, from a Gaussian elimination which tracks the combinations of the columns: a kernel vector other than 0 and the all-ones vector, if the kernel has one.

Parameters

HT	The transpose of H in CSR form (row j: the rows of the column j of H).
cnt	Number of columns.
cols	The columns (distinct).
ws	Workspace for H (see cols_ws_init()).
sub	Output: the columns of the subset, in the order of cols (at most cnt - 1 of them).

Returns: The size of the subset, or 0 if there is none (e.g., for an irreducible codeword).

Definition at line 1123 of file util_m4ri.c.

◆ csr_cols_rank()

int csr_cols_rank	(	const csr_t *const	HT,
		const int	cnt,
		const int	cols[],
		cols_ws_t *const	ws )

Rank of a set of columns of a sparse binary matrix H.

A dense Gaussian elimination of the cnt columns restricted to the rows they touch (duplicate entries cancel mod 2). A nonempty codeword C (H 1_C = 0) is irreducible, i.e., it is not the union of two disjoint nonempty codewords (no nonempty proper subset of C has zero syndrome), if and only if the rank of its columns is |C| - 1.

Parameters

HT	The transpose of H in CSR form (row j: the rows of the column j of H).
cnt	Number of columns.
cols	The columns (distinct).
ws	Workspace for H (see cols_ws_init()).

Returns: The rank of the columns.

Definition at line 1110 of file util_m4ri.c.

◆ csr_compress()

void csr_compress ( csr_t * mat )

Compress CSR matrix (sort indices and remove duplicates/zeros).

Compresses the representation of the sparse matrix and sorts column indices within each row to ensure consistency (critical for binary search / merging).

Parameters

mat	Pointer to the CSR matrix to compress in-place.

compress a CSR matrix

Definition at line 574 of file util_m4ri.c.

References int_pair::a, int_pair::b, ERROR, csr_t::i, csr_t::nz, csr_t::p, and csr_t::rows.

Referenced by csr_apply_perm(), csr_mm_read(), and csr_transpose().

◆ csr_csr_mul_non_zero()

int csr_csr_mul_non_zero	(	const csr_t *const	A,
		const csr_t *const	B )

Check if the product of two sparse matrices A * B^T is non-zero.

Uses the columns of A (its transpose): O(nnz(A) + nnz(B) * column weight of A) operations. A column repeated in a row counts once, as in mzd_from_csr().

Parameters

A	First sparse matrix (compressed form).
B	Second sparse matrix (compressed form, the same number of columns).

Returns: 1 if the product is non-zero (matrices are not orthogonal), 0 otherwise.

Definition at line 342 of file util_m4ri.c.

References csr_t::cols, csr_free(), csr_transpose(), ERROR, csr_t::i, csr_t::nz, csr_t::p, p, and csr_t::rows.

Referenced by var_init().

◆ csr_free()

csr_t * csr_free ( csr_t * p )

Free memory allocated for a CSR sparse matrix.

Parameters

p	Pointer to the CSR sparse matrix to free.

Returns: Always returns NULL.

kill a CSR matrix

Definition at line 522 of file util_m4ri.c.

References p.

Referenced by csr_csr_mul_non_zero(), do_CC_dist(), do_RW_dist(), Lx_for_CSS_code(), main(), nzlist_read(), var_init(), and var_kill().

◆ csr_from_pairs()

csr_t * csr_from_pairs	(	csr_t *	mat,
		const int	nz,
		int_pair *const	prs,
		const int	nrows,
		const int	ncols )

Construct a CSR sparse matrix from an array of coordinate pairs.

Parameters

mat	Destination CSR matrix (can be NULL).
nz	Number of coordinate pairs.
prs	Array of row-column index pairs.
nrows	Number of rows in the matrix.
ncols	Number of columns in the matrix.

Returns: Pointer to the constructed CSR matrix.

Definition at line 597 of file util_m4ri.c.

References int_pair::b, csr_init(), csr_t::i, csr_t::nz, and csr_t::p.

Referenced by read_dem_file().

◆ csr_init()

csr_t * csr_init	(	csr_t *	mat,
		int	rows,
		int	cols,
		int	nzmax )

Initialize or reallocate a CSR sparse matrix to target size.

Checks dimensions and nzmax of mat, reallocating arrays if they are too small.

Parameters

mat	Existing matrix structure (can be NULL, in which case it is allocated).
rows	Target number of rows.
cols	Target number of columns.
nzmax	Target capacity (number of non-zero entries).

Returns: Pointer to the initialized/reallocated CSR matrix.

initialize a CSR matrix check existing size and (re)allocate if needded

keep allocated mat

Definition at line 539 of file util_m4ri.c.

References csr_t::cols, ERROR, csr_t::i, MAX, csr_t::nz, csr_t::nzmax, csr_t::p, and csr_t::rows.

Referenced by csr_apply_perm(), csr_from_mzd(), csr_from_pairs(), csr_mm_read(), and csr_transpose().

◆ csr_max_row_wght()

int csr_max_row_wght ( const csr_t *const p )

Get the maximum row weight of a CSR sparse matrix.

Parameters

p	Pointer to the CSR sparse matrix.

Returns: Maximum row weight.

Get the maximum row weight of a CSR sparse matrix.

Definition at line 145 of file util_m4ri.c.

References p.

Referenced by do_CC_dist(), and main().

◆ csr_mm_read()

csr_t * csr_mm_read	(	char *	fin,
		csr_t *	mat,
		int	transpose )

Read a sparse matrix from a Matrix Market (.mtx) file into CSR format.

Parameters

fin	Path to the Matrix Market file.
mat	Destination CSR matrix (can be NULL).
transpose	Set to 1 to transpose the matrix while reading.

Returns: Pointer to the loaded CSR matrix.

read sparse matrix into a (binary) CSR (all entries default to 1) (re)allocate mat if needed use transpose=1 to transpose.

Definition at line 655 of file util_m4ri.c.

References csr_compress(), csr_init(), ERROR, csr_t::i, mm_is_coordinate, mm_is_general, mm_is_integer, mm_is_matrix, mm_is_pattern, mm_is_symmetric, mm_read_banner(), mm_read_mtx_array_size(), mm_read_mtx_crd_size(), mm_typecode_to_str(), csr_t::nz, and csr_t::p.

Referenced by var_init().

◆ csr_mzd_mul()

mzd_t * csr_mzd_mul	(	mzd_t *	C,
		const csr_t *	S,
		const mzd_t *	B,
		int	clear )

Multiply a sparse matrix by a dense matrix.

Computes C = S * B (if clear is 1) or C = C + S * B (if clear is 0).

Parameters

C	Destination dense matrix (can be NULL).
S	Source sparse matrix.
B	Source dense matrix.
clear	Flag to clear C before adding the product.

Returns: Pointer to the resulting dense matrix C.

sparse-S by dense B multiplication C=C+S*B; allocate C if needed.

Definition at line 257 of file util_m4ri.c.

References csr_t::cols, ERROR, csr_t::i, csr_t::p, p, and csr_t::rows.

◆ csr_out()

void csr_out ( const csr_t * mat )

Print raw contents of a CSR matrix to stdout.

Parameters

mat	Pointer to the CSR matrix.

output a CSR matrix

Definition at line 616 of file util_m4ri.c.

References csr_t::cols, csr_t::i, csr_t::nz, csr_t::nzmax, csr_t::p, p, and csr_t::rows.

◆ csr_print()

void csr_print	(	const csr_t *const	smat,
		const char	str[] )

Print a CSR matrix with a label string (formatted output).

Parameters

smat	Pointer to the CSR matrix.
str	Label/name of the matrix.

Definition at line 638 of file util_m4ri.c.

References mzd_from_csr().

◆ csr_transpose()

csr_t * csr_transpose	(	csr_t *	dst,
		const csr_t *const	p )

Transpose a compressed CSR sparse matrix.

Transposes matrix p and stores the result in dst. (Re)allocates dst if needed.

Parameters

dst	Destination sparse matrix (can be NULL, in which case it is allocated).
p	Source sparse matrix.

Returns: Pointer to the transposed sparse matrix (dst or newly allocated).

transpose compressed CSR matrix, (re) allocate if needed return resulting matrix TODO: add code for List of Pairs

Definition at line 163 of file util_m4ri.c.

References csr_t::cols, csr_compress(), csr_init(), ERROR, csr_t::i, MAX, csr_t::nz, csr_t::nzmax, csr_t::p, p, and csr_t::rows.

Referenced by csr_csr_mul_non_zero(), do_CC_dist(), do_RW_dist(), main(), and nzlist_read().

◆ do_dist_clus()

int do_dist_clus	(	const csr_t *const	P,
		const mzd_t *const	G,
		int	debug,
		int	wmax,
		int	start,
		const int	rankG )

(Internal) Run cluster distance algorithm on matrices.

◆ do_reduce()

int do_reduce	(	mzd_t *	row,
		const mzd_t *	matG0,
		const rci_t	rankG0 )

Reduce a row vector against a matrix in standard form.

Checks if row is linearly dependent on the rows of matP0 (using rankP0 rows). Modifies row in place.

Parameters

row	Dense row vector to reduce (modified in place).
matP0	Dense matrix in standard form.
rankP0	Rank of matP0 (number of active rows).

Returns: 1 if row was reduced to zero (linearly dependent), 0 otherwise.

Check if row is linearly dependent with the rows of matG0 which is assumed to be in standard form. rankG0 is the number of non-zero rows in rankG0. return: -1 if empty line after simplification otherwise position of the first non-zero bit in the simplified vector

Definition at line 832 of file util_m4ri.c.

◆ localized_window_perm()

void localized_window_perm	(	mzp_t *	perm,
		int	nvar,
		int	seed_col,
		int	kwin,
		int	win_mode,
		const csr_t *	spaH,
		const csr_t *	mHT,
		int *	visited_cols,
		int *	visited_checks,
		int *	col_queue,
		int *	visit_marker,
		uint64_t *	rng_state )

Construct a column permutation with a localized window at the front.

Places kwin columns around seed_col (via Tanner BFS if win_mode == 0, or contiguous index proximity if win_mode == 1) in perm->values[0 .. kwin-1], internally shuffled, followed by the shuffled remaining columns.

Definition at line 1160 of file util_m4ri.c.

References csr_t::i, csr_t::p, p, csr_t::rows, and SWAPINT.

Referenced by do_RW_dist().

◆ Lx_for_CSS_code()

csr_t * Lx_for_CSS_code	(	const csr_t *const	Hx,
		const csr_t *const	Hz )

Construct the logical matrix Lx for a quantum CSS code given Hx and Hz.

Parameters

Hx	Sparse X-check matrix.
Hz	Sparse Z-check matrix (passed as Hz).

Returns: Pointer to the constructed sparse logical matrix Lx.

Construct the logical matrix Lx for a quantum CSS code given Hx and Hz.

Given a pair of binary CSS generator matrices in CSR format, Hx*Hz^T=0, compute a sparse matrix Lx s.t. Lx*Hz^T=0 and rows of Lx be linearly independent from those of Hx. TODO: see if sparsity of Lx can be improved.

permute columns to make std form [ I C ]

verify orthogonality

Definition at line 934 of file util_m4ri.c.

References csr_t::cols, csr_apply_perm(), csr_free(), csr_from_mzd(), ERROR, mzd_from_csr(), mzd_gauss_naive(), mzd_generator_from_csr(), perm_p(), perm_p_trans(), product_weight_csr_mzd(), and csr_t::rows.

Referenced by var_init().

◆ make_err()

void make_err	(	mzd_t *	row,
		double	p )

Generate a random binary error vector with error probability p.

Parameters

row	Dense row vector to store the error (modified in place).
p	Bit-flip probability.

Definition at line 870 of file util_m4ri.c.

References ERROR, and p.

◆ mzd_from_csr()

mzd_t * mzd_from_csr	(	mzd_t *	dst,
		const csr_t *	p )

Convert a CSR sparse matrix to an MZD dense matrix.

Parameters

dst	Destination dense matrix (can be NULL or must have correct dimensions).
p	Source sparse matrix.

Returns: Pointer to the dense matrix.

Convert CSR sparse binary matrix to MZD allocate dst if needed (must be correct size or NULL)

Definition at line 186 of file util_m4ri.c.

References ERROR, and p.

Referenced by csr_all_ones_in_rowspan(), csr_dump(), csr_print(), do_RW_dist(), Lx_for_CSS_code(), mzd_generator_from_csr(), mzd_nullspace(), and product_weight_csr_mzd().

◆ mzd_gauss_naive()

rci_t mzd_gauss_naive	(	mzd_t *	M,
		mzp_t *	q,
		int	full )

Perform Gaussian elimination (naive) and return pivot column list.

Performs row reduction on M. If full is 1, performs full row reduction (RREF), otherwise only upper triangular. Stores the pivot column indices in q.

Parameters

M	Matrix to reduce (modified in place).
q	Permutation structure to store pivot columns.
full	Flag for full reduction (1) or triangular (0).

Returns: Rank of the matrix.

Copy of mzd_gauss_delayed from mzd.c (m4ri package) except additionally returns the list of pivot columns in second argument permutation q must be initialized!

Definition at line 104 of file util_m4ri.c.

Referenced by Lx_for_CSS_code(), and mzd_generator_from_csr().

◆ mzd_generator_from_csr()

mzd_t * mzd_generator_from_csr	(	mzd_t *	G,
		const csr_t *const	H )

Construct the generator matrix from a parity check matrix in CSR form.

Permutes columns of H to bring it to standard form [ I C ], computes the generator matrix G = [ C^T I ], and permutes columns of G back to align with the original H.

Parameters

G	Destination dense matrix for generator (can be NULL).
H	Parity check matrix in CSR format.

Returns: Pointer to the generator matrix G.

Convert a sparse binary matrix CSR into a standard form [ I C ], with some col permutations if needed, create the dense generator [ CT I ], and permute the cols back.
(re)allocate G if needed.

Definition at line 213 of file util_m4ri.c.

References csr_t::cols, mzd_from_csr(), mzd_gauss_naive(), mzp_out(), and prm.

Referenced by Lx_for_CSS_code().

◆ mzd_nullspace()

mzd_t * mzd_nullspace ( const csr_t *const H )

Compute the null space basis N = ker(H) of dimension nu x n.

Uses M4RI's mzd_kernel_left_pluq to find X such that H * X = 0, and returns N = X^T of size (n - rank(H)) x n.

Parameters

H	Sparse parity check matrix in CSR form.

Returns: Newly allocated dense matrix N, or NULL if kernel is trivial.

Definition at line 974 of file util_m4ri.c.

References mzd_from_csr().

Referenced by do_RW_dist(), and main().

◆ mzd_weight()

size_t mzd_weight ( const mzd_t * A )

Compute the number of set bits (Hamming weight) in a dense matrix A.

Parameters

A	Pointer to the dense matrix.

Returns: Hamming weight of the matrix.

Definition at line 74 of file util_m4ri.c.

Referenced by csr_from_mzd(), and product_weight_csr_mzd().

◆ mzd_weight_naive()

size_t mzd_weight_naive ( const mzd_t * A )

Naive implementation to compute the Hamming weight of a dense matrix A.

Parameters

A	Pointer to the dense matrix.

Returns: Hamming weight of the matrix.

Definition at line 46 of file util_m4ri.c.

◆ mzd_weight_row()

size_t mzd_weight_row	(	const mzd_t *	A,
		rci_t	i )

Compute the Hamming weight of a specific row in a dense matrix.

Parameters

A	Pointer to the dense matrix.
i	Index of the row.

Returns: Hamming weight of row i.

Definition at line 55 of file util_m4ri.c.

Referenced by refresh_nullspace_basis().

◆ mzp_out()

void mzp_out ( mzp_t const * p )

Print the permutation to stdout.

Parameters

p	Pointer to the permutation structure.

print out the permutation (only needed under windows)

Definition at line 475 of file util_m4ri.c.

References p.

Referenced by mzd_generator_from_csr().

◆ mzp_rand_len()

mzp_t * mzp_rand_len	(	mzp_t *	q,
		rci_t	length )

Generate a random permutation of a given length in-place.

Modifies the permutation q by randomizing the first 'length' positions. Uses LAPACK style pivot permutations.

Parameters

q	Permutation structure to modify.
length	Number of positions to permute.

Returns: Pointer to the modified permutation q.

replace pivot q with a random pivot smaller or equal length (second parameter); remaining positions in place, *** note: LAPACK style pivot permutations! *** return pointer to q. input: perm – existing permutation

Definition at line 459 of file util_m4ri.c.

References ERROR, and rand_uniform().

◆ perm_p()

mzp_t * perm_p	(	mzp_t *	q,
		const mzp_t *	p,
		rci_t	start )

Apply pivot permutation p to permutation q in-place starting from index.

Parameters

q	Destination permutation (initialized to identity if NULL).
p	Source pivot permutation.
start	Index to start applying the permutation from.

Returns: Pointer to the updated permutation q.

apply pivot p to permutation q in place from start; initialize q to identity permutation if NULL return q

Definition at line 487 of file util_m4ri.c.

References ERROR, p, and SWAPINT.

Referenced by Lx_for_CSS_code().

◆ perm_p_trans()

mzp_t * perm_p_trans	(	mzp_t *	q,
		const mzp_t *	p,
		const rci_t	start )

Apply transposed pivot permutation p to permutation q in-place.

Parameters

q	Destination permutation (initialized to identity if NULL).
p	Source pivot permutation.
start	Index to start applying the permutation from.

Returns: Pointer to the updated permutation q.

apply pivot p (transposed) to permutation q in place from start; initialize q to identity permutation if NULL return q

Definition at line 505 of file util_m4ri.c.

References ERROR, p, and SWAPINT.

Referenced by do_RW_dist(), Lx_for_CSS_code(), and refresh_nullspace_basis().

◆ product_weight_csr_mzd()

size_t product_weight_csr_mzd	(	const csr_t *	A,
		const mzd_t *	B,
		int	transpose )

Compute the weight of the product of a sparse matrix and a dense matrix.

Computes Hamming weight of A * B (if transpose is 0) or A * B^T (if transpose is 1).

Parameters

A	Source sparse matrix.
B	Source dense matrix.
transpose	Flag to transpose B.

Returns: Hamming weight of the product.

helper function to compute the weight of the product A*B (transpose == 0) or A*B^T (transpose == 1) with A sparse, B dense binary matrices

Definition at line 419 of file util_m4ri.c.

References mzd_from_csr(), and mzd_weight().

Referenced by Lx_for_CSS_code().

◆ rand_uniform()

int rand_uniform ( const int max )

Return a uniformly distributed random integer in the range [0, max-1].

Parameters

max	Upper bound (exclusive).

Returns: Random integer.

return uniformly distributed random number in the range [0,...,max-1]

Definition at line 439 of file util_m4ri.c.

Referenced by do_RW_dist(), and mzp_rand_len().

◆ refresh_nullspace_basis()

void refresh_nullspace_basis	(	mzd_t *	N,
		const int *	cw_arr,
		int	cw_wt,
		uint64_t *	rng_state )

Refresh the null space basis N under a random column permutation and optionally inject a low-weight codeword via Steinitz exchange.

Definition at line 1249 of file util_m4ri.c.

References mzd_weight_row(), and perm_p_trans().

Referenced by do_RW_dist().

◆ syndrome_bit_count()

int syndrome_bit_count	(	const mzd_t *const	row,
		const csr_t *const	spaQ )

Compute the Hamming weight of the syndrome of a dense row vector against spaQ.

Parameters

row	Dense row vector (1 row).
spaQ	Sparse check matrix.

Returns: Hamming weight of the syndrome.

just check whether syndrome is zero or not

Definition at line 396 of file util_m4ri.c.

References csr_t::i, csr_t::p, p, and csr_t::rows.

◆ syndrome_vector()

mzd_t * syndrome_vector	(	mzd_t *	syndrome,
		mzd_t *	row,
		csr_t *	spaQ,
		int	clear )

Calculate syndrome vector change.

Computes syndrome = syndrome + row * spaQ (or sets it if clear is 1).

Parameters

syndrome	Destination syndrome vector.
row	Error vector (dense, 1 row).
spaQ	Sparse check matrix.
clear	Flag to clear syndrome before accumulation.

Returns: Pointer to the updated syndrome vector.

Calculate the syndrome vector change: syndrome=syndrome +row.spaQ optionally clear the destination

Definition at line 314 of file util_m4ri.c.

References csr_t::cols, ERROR, csr_t::i, csr_t::p, p, and csr_t::rows.

Classes

Macros

Functions

Macro Definition Documentation

◆ ERROR

◆ FIRSTBIT

◆ MZD_FIRST_ROW

◆ SETBT

◆ SETWD

◆ SORT_CMP

◆ SORT_DEF

◆ SORT_NAME

◆ SORT_TYPE

◆ SWAPINT

◆ TIMESWORDSIZE

Function Documentation

◆ colmask_free()

◆ colmask_from_csr()

◆ cols_ws_free()

◆ cols_ws_init()

◆ csr_all_ones_in_rowspan()

◆ csr_apply_perm()

◆ csr_cols_dependency()

◆ csr_cols_rank()

◆ csr_compress()

◆ csr_csr_mul_non_zero()

◆ csr_free()

◆ csr_from_pairs()

◆ csr_init()

◆ csr_max_row_wght()

◆ csr_mm_read()

◆ csr_mzd_mul()

◆ csr_out()

◆ csr_print()

◆ csr_transpose()

◆ do_dist_clus()

◆ do_reduce()

◆ localized_window_perm()

◆ Lx_for_CSS_code()

◆ make_err()

◆ mzd_from_csr()

◆ mzd_gauss_naive()

◆ mzd_generator_from_csr()

◆ mzd_nullspace()

◆ mzd_weight()

◆ mzd_weight_naive()

◆ mzd_weight_row()

◆ mzp_out()

◆ mzp_rand_len()

◆ perm_p()

◆ perm_p_trans()

◆ product_weight_csr_mzd()

◆ rand_uniform()

◆ refresh_nullspace_basis()

◆ syndrome_bit_count()

◆ syndrome_vector()