matrix.h File Reference

Byte and binary matrices and associated functions. More...

#include "tifa_config.h"
#include <inttypes.h>
#include "bitstring_t.h"

Go to the source code of this file.

Data Structures

struct struct_binary_matrix_t

Defines a matrix of bits. More...

struct struct_byte_matrix_t

Defines a matrix of bytes. More...

Defines

#define _TIFA_MATRIX_H_

#define NO_SUCH_ROW UINT32_MAX

Typedefs

typedef struct
struct_binary_matrix_t binary_matrix_t

Equivalent to struct struct_binary_matrix_t.

typedef struct struct_byte_matrix_t byte_matrix_t

Equivalent to struct struct_byte_matrix_t.

Functions

binary_matrix_t * alloc_binary_matrix (uint32_t nrows, uint32_t ncols)

Allocates and returns a new binary_matrix_t.

binary_matrix_t * clone_binary_matrix (const binary_matrix_t *const matrix)

Allocates and returns a cloned binary_matrix_t.

void reset_binary_matrix (binary_matrix_t *const matrix)

Sets a binary_matrix_t to zero.

void free_binary_matrix (binary_matrix_t *const matrix)

Clears a binary_matrix_t.

void print_binary_matrix (const binary_matrix_t *const matrix)

Prints a binary_matrix_t.

static uint8_t get_matrix_bit (uint32_t row, uint32_t col, const binary_matrix_t *const matrix)

Returns the value of a given bit in a binary_matrix_t.

static void set_matrix_bit_to_one (uint32_t row, uint32_t col, binary_matrix_t *const matrix)

Sets to one the value of a given bit in a binary_matrix_t.

static void set_matrix_bit_to_zero (uint32_t row, uint32_t col, binary_matrix_t *const matrix)

Sets to zero the value of a given bit in a binary_matrix_t.

static void flip_matrix_bit (uint32_t row, uint32_t col, binary_matrix_t *const matrix)

Flips the value of a given bit in a binary_matrix_t.

static uint32_t first_row_with_one_on_col (uint32_t col, const binary_matrix_t *const matrix)

Returns the index of the first row of a binary_matrix_t with a one in a given column.

byte_matrix_t * alloc_byte_matrix (uint32_t nrows, uint32_t ncols)

Allocates and returns a new byte_matrix_t.

byte_matrix_t * clone_byte_matrix (const byte_matrix_t *const matrix)

Allocates and returns a cloned byte_matrix_t.

void reset_byte_matrix (byte_matrix_t *const matrix)

Sets a byte_matrix_t to zero.

void free_byte_matrix (byte_matrix_t *const matrix)

Clears a byte_matrix_t.

void print_byte_matrix (const byte_matrix_t *const matrix)

Prints a byte_matrix_t.

Detailed Description

Byte and binary matrices and associated functions.

Author:: Jerome Milan

Date:: Fri Jun 10 2011

Version:: 2011-06-10

Defines binary matrices (i.e. matrices over GF(2)), byte matrices, and their associated functions.

Definition in file matrix.h.

Define Documentation

#define _TIFA_MATRIX_H_

Standard include guard.

Definition at line 36 of file matrix.h.

#define NO_SUCH_ROW UINT32_MAX

Value returned by the first_row_with_one_on_col(col, matrix) function if no row of the matrix has a bit 1 in its col-th column.

Definition at line 53 of file matrix.h.

Referenced by first_row_with_one_on_col().

Function Documentation

binary_matrix_t* alloc_binary_matrix	(	uint32_t	nrows,
		uint32_t	ncols
	)

Allocates and returns a new binary_matrix_t.

Allocates and returns a new binary_matrix_t such that:

its nrows_alloced field is set to nrows.
its ncols_alloced field is set to the minimum number of TIFA_BITSTRING_T integers needed to store ncols bits.
its nrows field is set to nrows.
its ncols field is set to ncols.
its data array of arrays is completely filled with zeroes.

Note:: The behaviour of this alloc function differs from the ones in array.h . This discrepancy will be corrected in later versions.

Parameters:

`[in]`	nrows	The maximum number of rows of the `binary_matrix_t` to allocate.
`[in]`	ncols	The maximum number of bits per row of the `binary_matrix_t` to allocate.

Returns:: A pointer to the newly allocated binary_matrix_t structure. Note that this matrix may hold more that ncols bits per column if ncols is not a multiple of 8 * sizeof(TIFA_BITSTRING_T).

byte_matrix_t* alloc_byte_matrix	(	uint32_t	nrows,
		uint32_t	ncols
	)

Allocates and returns a new byte_matrix_t.

Allocates and returns a new byte_matrix_t such that:

its nrows_alloced field is set to nrows.
its ncols_alloced field is set to ncols.
its nrows field is set to nrows.
its ncols field is set to ncols.
its data array of arrays is completely filled with zeroes.

Note:: The behaviour of this alloc function differs from the ones in array.h. This discrepancy will be corrected in later versions.

Parameters:

`[in]`	nrows	The maximum number of rows of the `byte_matrix_t` to allocate.
`[in]`	ncols	The maximum number of columns `byte_matrix_t` to allocate.

Returns:: A pointer to the newly allocated byte_matrix_t structure.

binary_matrix_t* clone_binary_matrix ( const binary_matrix_t *const matrix )

Allocates and returns a cloned binary_matrix_t.

Allocates and returns a clone of the binary_matrix_t pointed by matrix.

Parameters:

[in] matrix A pointer to the binary matrix to clone.

Returns:: A pointer to the newly allocated binary_matrix_t clone.

byte_matrix_t* clone_byte_matrix ( const byte_matrix_t *const matrix )

Allocates and returns a cloned byte_matrix_t.

Allocates and returns a clone of the byte_matrix_t pointed by matrix.

Parameters:

[in] matrix A pointer to the byte matrix to clone.

Returns:: A pointer to the newly allocated byte_matrix_t clone.

static uint32_t first_row_with_one_on_col	(	uint32_t	col,
		const binary_matrix_t *const	matrix
	)			`[inline, static]`

Returns the index of the first row of a binary_matrix_t with a one in a given column.

Returns the index of the first row of a binary_matrix_t which has a one on its col-th column. It returns NO_SUCH_ROW if no such row is found.

Parameters:

`[in]`	col	The column of the matrix.
`[in]`	matrix	A pointer to the `binary_matrix_t`.

Returns:

An unsigned integer row between 0 and matrix->nrows-1 such that (matrix->data[row][col] == 1)
NO_SUCH_ROW if, for all valid i, (matrix->data[i][col] != 1).

Note:: This function is needed in the gaussian elimination algorithm described in the paper "A compact algorithm for Gaussian elimination over GF(2) implemented on highly parallel computers", by D. Parkinson and M. Wunderlich (Parallel Computing 1 (1984) 65-73).

It could be argued that such a function should then be declared and implemented in the files relevant to the aforementionned algorithm. However, this would lead to a very inefficient implementation of this function since proprer programming pratices would lead to consider the matrix as some kind of opaque structure. Granted, nothing could have prevented us to implement first_row_with_one_on_col exactly as in matrix.c, but the future maintainer would have the burden to check and update code scattered around several files should the inner structure of binary_matrix_t be modified.

This can be seen as a moot point: after all, the TIFA code does not strictly enforce type encapsulation. Indeed, some parts of the code do assume (a minimal!) knowledge of the internal structures of some types (have a look at siqs.c for instance). That does not make it the right thing to do though. Unless when facing a real bottleneck, let's try to keep the "programmer's omniscience" to a manageable level...

Definition at line 316 of file matrix.h.

References struct_binary_matrix_t::data, NO_SUCH_ROW, and struct_binary_matrix_t::nrows.

static void flip_matrix_bit	(	uint32_t	row,
		uint32_t	col,
		binary_matrix_t *const	matrix
	)			`[inline, static]`

Flips the value of a given bit in a binary_matrix_t.

Flips the value of the bit at the row-th row and the col-th column of the binary_array_t pointed by array.

Parameters:

`[in]`	row	The row of the bit to flip.
`[in]`	col	The column of the bit to flip.
`[in]`	matrix	A pointer to the `binary_matrix_t`.

Definition at line 265 of file matrix.h.

References struct_binary_matrix_t::data.

void free_binary_matrix ( binary_matrix_t *const matrix )

Clears a binary_matrix_t.

Clears a binary_matrix_t, or, more precisely, clears the memory space used by the arrays pointed by the data field of a binary_matrix_t. Also set its nrows_alloced , ncols_alloced , nrows and ncols fields to zero.

Parameters:

[in] matrix A pointer to the binary_matrix_t to clear.

void free_byte_matrix ( byte_matrix_t *const matrix )

Clears a byte_matrix_t.

Clears a byte_matrix_t, or, more precisely, clears the memory space used by the arrays pointed by the data field of a byte_matrix_t. Also set its nrows_alloced, ncols_alloced, nrows and ncols fields to zero.

Parameters:

[in] matrix A pointer to the byte_matrix_t to clear.

static uint8_t get_matrix_bit	(	uint32_t	row,
		uint32_t	col,
		const binary_matrix_t *const	matrix
	)			`[inline, static]`

Returns the value of a given bit in a binary_matrix_t.

Returns the value of the bit at the row-th row and the col-th column of the binary_array_t pointed by array, as either 0 or 1.

Parameters:

`[in]`	row	The row of the bit to read.
`[in]`	col	The column of the bit to read.
`[in]`	matrix	A pointer to the `binary_matrix_t`.

Returns:: The value of the bit at the (row,col) position: either 0 or 1.

Definition at line 186 of file matrix.h.

References struct_binary_matrix_t::data.

void print_binary_matrix ( const binary_matrix_t *const matrix )

Prints a binary_matrix_t.

Prints a binary_matrix_t's on the standard output.

Parameters:

[in] matrix A pointer to the binary_matrix_t to print.

void print_byte_matrix ( const byte_matrix_t *const matrix )

Prints a byte_matrix_t.

Prints a byte_matrix_t's on the standard output.

Parameters:

[in] matrix A pointer to the byte_matrix_t to print.

void reset_binary_matrix ( binary_matrix_t *const matrix )

Sets a binary_matrix_t to zero.

Sets the binary_matrix_t matrix to the zero matrix.

Parameters:

[in] matrix A pointer to the binary_matrix_t to reset.

void reset_byte_matrix ( byte_matrix_t *const matrix )

Sets a byte_matrix_t to zero.

Sets the byte_matrix_t matrix to the zero matrix.

Parameters:

[in] matrix A pointer to the byte_matrix_t to reset.

static void set_matrix_bit_to_one	(	uint32_t	row,
		uint32_t	col,
		binary_matrix_t *const	matrix
	)			`[inline, static]`

Sets to one the value of a given bit in a binary_matrix_t.

Sets to one the value of the bit at the row-th row and the col-th column of the binary_array_t pointed by array.

Parameters:

`[in]`	row	The row of the bit to set.
`[in]`	col	The column of the bit to set.
`[in]`	matrix	A pointer to the `binary_matrix_t`.

Definition at line 214 of file matrix.h.

References struct_binary_matrix_t::data.

static void set_matrix_bit_to_zero	(	uint32_t	row,
		uint32_t	col,
		binary_matrix_t *const	matrix
	)			`[inline, static]`

Sets to zero the value of a given bit in a binary_matrix_t.

Sets to zero the value of the bit at the row-th row and the col-th column of the binary_array_t pointed by array.

Parameters:

`[in]`	row	The row of the bit to set.
`[in]`	col	The column of the bit to set.
`[in]`	matrix	A pointer to the `binary_matrix_t`.

Definition at line 240 of file matrix.h.

References struct_binary_matrix_t::data.


Data Structures
struct	struct_binary_matrix_t
	Defines a matrix of bits. More...
struct	struct_byte_matrix_t
	Defines a matrix of bytes. More...
Defines
#define	_TIFA_MATRIX_H_
#define	NO_SUCH_ROW UINT32_MAX
Typedefs
typedef struct struct_binary_matrix_t	binary_matrix_t
	Equivalent to `struct struct_binary_matrix_t`.
typedef struct struct_byte_matrix_t	byte_matrix_t
	Equivalent to `struct struct_byte_matrix_t`.
Functions
binary_matrix_t *	alloc_binary_matrix (uint32_t nrows, uint32_t ncols)
	Allocates and returns a new `binary_matrix_t`.
binary_matrix_t *	clone_binary_matrix (const binary_matrix_t *const matrix)
	Allocates and returns a cloned `binary_matrix_t`.
void	reset_binary_matrix (binary_matrix_t *const matrix)
	Sets a `binary_matrix_t` to zero.
void	free_binary_matrix (binary_matrix_t *const matrix)
	Clears a `binary_matrix_t`.
void	print_binary_matrix (const binary_matrix_t *const matrix)
	Prints a `binary_matrix_t`.
static uint8_t	get_matrix_bit (uint32_t row, uint32_t col, const binary_matrix_t *const matrix)
	Returns the value of a given bit in a `binary_matrix_t`.
static void	set_matrix_bit_to_one (uint32_t row, uint32_t col, binary_matrix_t *const matrix)
	Sets to one the value of a given bit in a `binary_matrix_t`.
static void	set_matrix_bit_to_zero (uint32_t row, uint32_t col, binary_matrix_t *const matrix)
	Sets to zero the value of a given bit in a `binary_matrix_t`.
static void	flip_matrix_bit (uint32_t row, uint32_t col, binary_matrix_t *const matrix)
	Flips the value of a given bit in a `binary_matrix_t`.
static uint32_t	first_row_with_one_on_col (uint32_t col, const binary_matrix_t *const matrix)
	Returns the index of the first row of a `binary_matrix_t` with a one in a given column.
byte_matrix_t *	alloc_byte_matrix (uint32_t nrows, uint32_t ncols)
	Allocates and returns a new `byte_matrix_t`.
byte_matrix_t *	clone_byte_matrix (const byte_matrix_t *const matrix)
	Allocates and returns a cloned `byte_matrix_t`.
void	reset_byte_matrix (byte_matrix_t *const matrix)
	Sets a `byte_matrix_t` to zero.
void	free_byte_matrix (byte_matrix_t *const matrix)
	Clears a `byte_matrix_t`.
void	print_byte_matrix (const byte_matrix_t *const matrix)
	Prints a `byte_matrix_t`.