djb.h File Reference

Dan Bernstein's "Optimizing linear maps mod 2". More...

#include <m4ri/mzd.h>

Go to the source code of this file.

Data Structures
struct	djb_t
	DJB's optimized linear maps mod 2. More...

Macros
#define	M4RI_DJB_BASE_SIZE   64

Enumerations
enum	srctyp_t { source_target, source_source }
	Specify source type of addition.

Functions
static djb_t *	djb_init (rci_t nrows, rci_t ncols)
static void	djb_free (djb_t *m)
static void	djb_push_back (djb_t *z, rci_t target, rci_t source, srctyp_t srctyp)
djb_t *	djb_compile (mzd_t *A)
void	djb_apply_mzd (djb_t *z, mzd_t *W, const mzd_t *V)
	W = m*V. More...
static void	djb_info (djb_t *z)

Detailed Description

Dan Bernstein's "Optimizing linear maps mod 2".

This code is a port of sort1.cpp available at http://binary.cr.yp.to/linearmod2.html

Given a matrix A djb_compile(A) will compute a djb_t data structure which realises A with (heuristically) (m * n)/(log m - loglog m) XORs.

It makes use of a binary heap written by Martin Kunev which is available at https://gist.github.com/martinkunev/1365481

Author

Martin Albrecht marti.nosp@m.nral.nosp@m.brech.nosp@m.t@go.nosp@m.oglem.nosp@m.ail..nosp@m.com

Macro Definition Documentation

#define M4RI_DJB_BASE_SIZE   64

Standard allocation chunk

Function Documentation

void djb_apply_mzd	(	djb_t *	z,
		mzd_t *	W,
		const mzd_t *	V
	)

W = m*V.

Apply the linear map m to V and write the result in W.

Parameters

z	DJB linear map.
W	Output matrix
V	Input matrix

djb_t* djb_compile

(

mzd_t *

A

)

Compile a new DJB linear map from A.

Parameters

A

static void djb_free ( djb_t *  m )

inlinestatic

Free a DJB linear maps

Parameters

m

Map

static void djb_info ( djb_t *  z )

inlinestatic

Print infomrmation on linear map mA

static djb_t* djb_init ( rci_t  nrows, rci_t  ncols  )

inlinestatic

Allocate a new DJB linear map

Parameters

nrows	Number of rows
ncols	Number of columns

static void djb_push_back ( djb_t *  z, rci_t  target, rci_t  source, srctyp_t  srctyp  )

inlinestatic

Add a new operation out[target] ^= srctype[source] to queue.

Parameters

z	DJB linear map.
target	Output index
source	Input index
srctyp	Type of input (source_source or source_target)