graycode.h File Reference

Gray code implementation. More...

Go to the source code of this file.

Data Structures
struct	code
	Gray codes. More...

Macros
#define	__M4RI_MAXKAY   16

Functions
int	m4ri_gray_code (int i, int l)
void	m4ri_build_code (int *ord, int *inc, int l)
void	m4ri_build_all_codes (void)
	Generates global code book. More...
void	m4ri_destroy_all_codes (void)
static int	log2_floor (int v)
int	m4ri_opt_k (int a, int b, int c)
	Return the optimal var k for the given parameters. More...

Variables
code **	m4ri_codebook

Detailed Description

Gray code implementation.

The Gray code is a binary numeral system where two successive values differ in only one digit.

Author

Gregory Bard bard@.nosp@m.ford.nosp@m.ham.e.nosp@m.du

Martin Albrecht M.R.A.nosp@m.lbre.nosp@m.cht@r.nosp@m.hul..nosp@m.ac.uk

Macro Definition Documentation

#define __M4RI_MAXKAY   16

Maximum allowed value for k.

Function Documentation

static int log2_floor ( int  v )

inlinestatic

floor(log_2(v))

void m4ri_build_all_codes

(

void

)

Generates global code book.

This function is called automatically when the shared library is loaded.

Warning

Not thread safe!

void m4ri_build_code	(	int *	ord,
		int *	inc,
		int	l
	)

Fills var ord and var inc with Gray code data for a Gray code of length \(2^l\).

Parameters

ord	Will hold gray code data, must be preallocated with correct size
inc	Will hold some increment data, must be preallocated with correct size
l	Logarithm of length of Gray code.

Note

Robert Miller had the idea for a non-recursive implementation.

void m4ri_destroy_all_codes

(

void

)

Frees memory from the global code book.

This function is called automatically when the shared library is unloaded.

Warning

Not thread safe!

int m4ri_gray_code	(	int	i,
		int	l
	)

Returns the i-th gray code entry for a gray code of length \(2^l\).

Parameters

i	The index in the Gray code table.
l	Length of the Gray code.

Returns

i-th Gray code entry.

int m4ri_opt_k	(	int	a,
		int	b,
		int	c
	)

Return the optimal var k for the given parameters.

If var c != 0 then var k for multiplication is returned, else var k for inversion. The optimal var k here means \(0.75 log_2(n)\) where \(n\) is \(min(a,b)\) for inversion and \(b\) for multiplication.

Parameters

a	Number of rows of (first) matrix
b	Number of columns of (first) matrix
c	Number of columns of second matrix (may be 0)

Returns

k

Variable Documentation

code** m4ri_codebook

Global m4ri_codebook.

Warning

Not thread safe!