#include <m4ri/m4ri.h>
#include <m4ri/mzd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "mmio.h"
#include "util_m4ri.h"
#include "sort.h"

Include dependency graph for util_m4ri.c:

Macros
#define	SORT_NAME int_pair
#define	SORT_TYPE int_pair
#define	SORT_CMP(x, y)
#define	SORT_DEF static inline

Functions
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 *const A, const rci_t i)
	Compute the Hamming weight of a specific row in a dense matrix.
size_t	mzd_weight (const mzd_t *A)
	Compute the number of set bits (Hamming weight) in a dense matrix A.
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)
	return max row weight of CSR matrix p TODO: add code for List of Pairs
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.
void	addto (mzd_t row, const csr_t spaQ, const int i)
mzd_t *	syndrome_vector (mzd_t syndrome, mzd_t row, csr_t *spaQ, int clear)
	Calculate syndrome vector change.
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.
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	do_reduce (mzd_t row, const mzd_t matG0, const rci_t rankG0)
	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.
csr_t *	csr_from_mzd (csr_t mat, const mzd_t const orig)
	convert m4ri dense matrix to csr
csr_t *	Lx_for_CSS_code (const csr_t const Hx, const csr_t const Hz)
	Compute logical generator matrix Lx for a CSS code.
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

◆ SORT_CMP

#define SORT_CMP	(		x,
			y )

Value:

(((x).a != (y).a) ? ((x).a - (y).a) : ((x).b - (y).b))

Definition at line 567 of file util_m4ri.c.

◆ SORT_DEF

#define SORT_DEF static inline

Definition at line 568 of file util_m4ri.c.

Referenced by BINARY_INSERTION_SORT(), BITONIC_SORT(), HEAP_SORT(), MERGE_SORT(), MERGE_SORT_IN_PLACE(), MERGE_SORT_IN_PLACE_ASWAP(), MERGE_SORT_IN_PLACE_BACKMERGE(), MERGE_SORT_IN_PLACE_FRONTMERGE(), MERGE_SORT_IN_PLACE_RMERGE(), MERGE_SORT_RECURSIVE(), SHELL_SORT(), SORT_DELETE_BUFFER(), SORT_NEW_BUFFER(), and TIM_SORT().

◆ SORT_NAME

#define SORT_NAME int_pair

Definition at line 565 of file util_m4ri.c.

◆ SORT_TYPE

#define SORT_TYPE int_pair

Definition at line 566 of file util_m4ri.c.

Referenced by BINARY_INSERTION_SORT(), BITONIC_SORT(), HEAP_SORT(), MERGE_SORT(), MERGE_SORT_IN_PLACE(), MERGE_SORT_IN_PLACE_ASWAP(), MERGE_SORT_IN_PLACE_BACKMERGE(), MERGE_SORT_IN_PLACE_FRONTMERGE(), MERGE_SORT_IN_PLACE_RMERGE(), MERGE_SORT_RECURSIVE(), QUICK_SORT(), SHELL_SORT(), SORT_DELETE_BUFFER(), SORT_NEW_BUFFER(), and TIM_SORT().

Function Documentation

◆ addto()

void addto	(	mzd_t *	row,
		const csr_t *	spaQ,
		const int	i )

Add row=i of sparse matrix spaQ to row. no range check is done

Definition at line 280 of file util_m4ri.c.

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

◆ 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.

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).

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.

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_mzd()

csr_t * csr_from_mzd	(	csr_t *	mat,
		const mzd_t *const	orig )

convert m4ri dense matrix to csr

Optimized for sparse matrices.

Parameters

mat	pointer to existing matrix or NULL

will reallocate if needed

optimized version

Definition at line 899 of file util_m4ri.c.

References csr_init(), csr_t::i, mzd_weight(), csr_t::nz, csr_t::p, and csr_t::rows.

Referenced by Lx_for_CSS_code().

◆ 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.

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 )

return max row weight of CSR matrix p TODO: add code for List of Pairs

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.

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.

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.

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.

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_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.

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 )

Compute logical generator matrix Lx for a CSS code.

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.

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.

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.

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.

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.

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.

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.

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.

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].

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.

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.

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.

Macros

Functions

Macro Definition Documentation

◆ SORT_CMP

◆ SORT_DEF

◆ SORT_NAME

◆ SORT_TYPE

Function Documentation

◆ addto()

◆ 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_mzd()

◆ csr_from_pairs()

◆ csr_init()

◆ csr_max_row_wght()

◆ csr_mm_read()

◆ csr_mzd_mul()

◆ csr_out()

◆ csr_print()

◆ csr_transpose()

◆ 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()