M4RI 20250128
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_tdjb_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_tdjb_compile (mzd_t *A)
void djb_apply_mzd (djb_t *z, mzd_t *W, const mzd_t *V)
 W = m*V.
static void djb_info (const 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

◆ M4RI_DJB_BASE_SIZE

#define M4RI_DJB_BASE_SIZE   64

Standard allocation chunk

Function Documentation

◆ djb_apply_mzd()

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
zDJB linear map.
WOutput matrix
VInput matrix

◆ djb_compile()

djb_t * djb_compile ( mzd_t * A)

Compile a new DJB linear map from A.

Parameters
A

◆ djb_free()

void djb_free ( djb_t * m)
inlinestatic

Free a DJB linear maps

Parameters
mMap

◆ djb_info()

void djb_info ( const djb_t * z)
inlinestatic

Print infomrmation on linear map mA

◆ djb_init()

djb_t * djb_init ( rci_t nrows,
rci_t ncols )
inlinestatic

Allocate a new DJB linear map

Parameters
nrowsNumber of rows
ncolsNumber of columns

◆ djb_push_back()

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
zDJB linear map.
targetOutput index
sourceInput index
srctypType of input (source_source or source_target)