Helper functions. More...

#include <m4ri/m4ri_config.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdint.h>

Macros
#define	__M4RI_CONVERT_TO_INT(w) ((int)(w))
	Explicit conversion macro. More...

#define	__M4RI_CONVERT_TO_BIT(w) ((BIT)(w))
	Explicit conversion macro. More...

#define	__M4RI_CONVERT_TO_UINT64_T(w) (w)
	Explicit conversion macro. More...

#define	__M4RI_CONVERT_TO_WORD(i) ((word)(i))
	Explicit conversion macro. More...

#define	MAX(x, y) (((x) > (y))?(x):(y))
	Return the maximal element of x and y. More...

#define	MIN(x, y) (((x) < (y))?(x):(y))
	Return the minimal element of x and y. More...

#define	TRUE 1
	Pretty for 1.

#define	FALSE 0
	Pretty for 0.

#define	__M4RI_TWOPOW(i) ((uint64_t)1 << (i))
	$2^i$ More...

#define	__M4RI_CLR_BIT(w, spot) ((w) &= ~(m4ri_one << (spot))
	Clear the bit spot (counting from the left) in the word w. More...

#define	__M4RI_SET_BIT(w, spot) ((w) \|= (m4ri_one << (spot)))
	Set the bit spot (counting from the left) in the word w. More...

#define	__M4RI_GET_BIT(w, spot) __M4RI_CONVERT_TO_BIT(((w) >> (spot)) & m4ri_one)
	Get the bit spot (counting from the left) in the word w. More...

#define	__M4RI_WRITE_BIT(w, spot, value) ((w) = (((w) & ~(m4ri_one << (spot))) \| (-__M4RI_CONVERT_TO_WORD(value) & (m4ri_one << (spot)))))
	Write the value to the bit spot in the word w. More...

#define	__M4RI_FLIP_BIT(w, spot) ((w) ^= (m4ri_one << (spot)))
	Flip the spot in the word w. More...

#define	__M4RI_LEFT_BITMASK(n) (m4ri_ffff >> (m4ri_radix - (n)) % m4ri_radix)
	create a bit mask to zero out all but the (n - 1) % m4ri_radix + 1 leftmost bits. More...

#define	__M4RI_RIGHT_BITMASK(n) (m4ri_ffff << (m4ri_radix - (n)))
	create a bit mask to zero out all but the n rightmost bits. More...

#define	__M4RI_MIDDLE_BITMASK(n, offset) (__M4RI_LEFT_BITMASK(n) << (offset))
	create a bit mask that is the combination of __M4RI_LEFT_BITMASK and __M4RI_RIGHT_BITMASK. More...

#define	__M4RI_ALIGNMENT(addr, n) (((unsigned long)(addr))%(n))
	Return alignment of addr w.r.t. n. For example the address 17 would be 1 aligned w.r.t. 16. More...

#define	__M4RI_GNUC_PREREQ(maj, min) FALSE
	Test for gcc >= maj.min, as per __GNUC_PREREQ in glibc. More...

#define	__M4RI_LIKELY(cond) __builtin_expect ((cond) != 0, 1)
	Macro to help with branch prediction.

#define	__M4RI_UNLIKELY(cond) __builtin_expect ((cond) != 0, 0)
	Macro to help with branch prediction.

Typedefs
typedef int	BIT
	Pretty for a boolean int. More...

typedef int	rci_t
	Type of row and column indexes. More...

typedef int	wi_t
	Type of word indexes. More...

typedef uint64_t	word
	A word is the typical packed data structure to represent packed bits.

Functions
static word	m4ri_swap_bits (word v)
	swap bits in the word v More...

static word	m4ri_shrink_bits (word const from, rci_t *const Q, int const length, int const base)
	pack bits (inverse of m4ri_spread_bits) More...

static word	m4ri_spread_bits (word const from, rci_t *const Q, int const length, int const base)
	spread bits More...

static int	m4ri_lesser_LSB (word a, word b)

void	m4ri_die (const char *errormessage,...)
	Print error message and abort(). More...

void	m4ri_word_to_str (char *destination, word data, int colon)
	Write a sting representing the word data to destination. More...

static BIT	m4ri_coin_flip ()
	Return 1 or 0 uniformly randomly distributed. More...

word	m4ri_random_word ()
	Return uniformly randomly distributed random word. More...

void	m4ri_init (void)
	Initialize global data structures for the M4RI library. More...

void	m4ri_fini (void)
	De-initialize global data structures from the M4RI library. More...

static void *	m4ri_mm_calloc (size_t count, size_t size)
	Calloc wrapper. More...

static void *	m4ri_mm_malloc_aligned (size_t size, size_t alignment)
	Aligned malloc wrapper. More...

static void *	m4ri_mm_malloc (size_t size)
	Malloc wrapper. More...

static void	m4ri_mm_free (void *condemned,...)
	Free wrapper. More...

Variables
static int const	m4ri_radix = 64
	The number of bits in a word.

static word const	m4ri_one = __M4RI_CONVERT_TO_WORD(1)
	The number one as a word.

static word const	m4ri_ffff = __M4RI_CONVERT_TO_WORD(-1)
	A word with all bits set.

Detailed Description

Helper functions.

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; Carlo Wood carlo.nosp@m.@ali.nosp@m.noe.c.nosp@m.om

Macro Definition Documentation

#define __M4RI_ALIGNMENT	(	addr,
		n
	)	(((unsigned long)(addr))%(n))

Return alignment of addr w.r.t. n. For example the address 17 would be 1 aligned w.r.t. 16.

Parameters

addr
n

#define __M4RI_CLR_BIT	(	w,
		spot
	)	((w) &= ~(m4ri_one << (spot))

Clear the bit spot (counting from the left) in the word w.

Parameters

w	Word
spot	Integer with 0 <= spot < m4ri_radix

#define __M4RI_CONVERT_TO_BIT ( w ) ((BIT)(w))

Explicit conversion macro.

Explicit conversion of a word, representing 64 columns, to a BIT to be used as boolean: this is an int with value 0 (false) or 1 (true). No error checking is done that only the least significant bit is set (if any).

Note: This is a no-op. It's purpose it to track intention.

#define __M4RI_CONVERT_TO_INT ( w ) ((int)(w))

Explicit conversion macro.

Explicit conversion of a word, representing 64 columns, to an integer to be used as index into an array. This is used for Gray codes. No error checking is done that the most significant bits in w are zero.

Note: This is a no-op. It's purpose it to track intention.

#define __M4RI_CONVERT_TO_UINT64_T ( w ) (w)

Explicit conversion macro.

Explicit conversion of a word, representing 64 columns, to an uint64_t.

The returned value is the underlaying integer representation of these 64 columns, meaning in particular that if val is an uint64_t then __M4RI_CONVERT_TO_UINT64_T(__M4RI_CONVERT_TO_WORD(val)) == val.

Note: This is a no-op. It's purpose it to track intention.

#define __M4RI_CONVERT_TO_WORD ( i ) ((word)(i))

Explicit conversion macro.

Explicit conversion of an integer to a word.

Note: This is a no-op. It's purpose it to track intention.

#define __M4RI_FLIP_BIT	(	w,
		spot
	)	((w) ^= (m4ri_one << (spot)))

Flip the spot in the word w.

Parameters

w	Word.
spot	Integer with 0 <= spot < m4ri_radix.

#define __M4RI_GET_BIT	(	w,
		spot
	)	__M4RI_CONVERT_TO_BIT(((w) >> (spot)) & m4ri_one)

Get the bit spot (counting from the left) in the word w.

Parameters

w	Word
spot	Integer with 0 <= spot < m4ri_radix

#define __M4RI_GNUC_PREREQ	(	maj,
		min
	)	FALSE

Test for gcc >= maj.min, as per __GNUC_PREREQ in glibc.

Parameters

maj	The major version.
min	The minor version.

Returns: TRUE iff we are using a GNU compile of at least version maj.min.

#define __M4RI_LEFT_BITMASK ( n ) (m4ri_ffff >> (m4ri_radix - (n)) % m4ri_radix)

create a bit mask to zero out all but the (n - 1) % m4ri_radix + 1 leftmost bits.

This function returns 1..64 bits, never zero bits. This mask is mainly used to mask the valid bits in the most significant word, by using __M4RI_LEFT_BITMASK((M->ncols + M->offset) % m4ri_radix). In other words, the set bits represent the columns with the lowest index in the word.

Thus,

n Output 0=64 1111111111111111111111111111111111111111111111111111111111111111 1 0000000000000000000000000000000000000000000000000000000000000001 2 0000000000000000000000000000000000000000000000000000000000000011 . ... 62 0011111111111111111111111111111111111111111111111111111111111111 63 0111111111111111111111111111111111111111111111111111111111111111

Note that n == 64 is only passed from __M4RI_MIDDLE_BITMASK, and still works (behaves the same as n == 0): the input is modulo 64.

Parameters

n	Integer with 0 <= n <= m4ri_radix

#define __M4RI_MIDDLE_BITMASK	(	n,
		offset
	)	(__M4RI_LEFT_BITMASK(n) << (offset))

create a bit mask that is the combination of __M4RI_LEFT_BITMASK and __M4RI_RIGHT_BITMASK.

This function returns 1..64 bits, never zero bits. This mask is mainly used to mask the n valid bits in the only word with valid bits, when M->ncols + M->offset <= m4ri_radix), by using __M4RI_MIDDLE_BITMASK(M->ncols, M->offset). It is equivalent to __M4RI_LEFT_BITMASK(n + offset) & __M4RI_RIGHT_BITMASK(m4ri_radix - offset). In other words, the set bits represent the valid columns in the word.

Note that when n == m4ri_radix (and thus offset == 0) then __M4RI_LEFT_BITMASK is called with n == 64.

Parameters

n	Integer with 0 < n <= m4ri_radix - offset
offset	Column offset, with 0 <= offset < m4ri_radix

#define __M4RI_RIGHT_BITMASK ( n ) (m4ri_ffff << (m4ri_radix - (n)))

create a bit mask to zero out all but the n rightmost bits.

This function returns 1..64 bits, never zero bits. This mask is mainly used to mask the n valid bits in the least significant word with valid bits by using __M4RI_RIGHT_BITMASK(m4ri_radix - M->offset). In other words, the set bits represent the columns with the highest index in the word.

Thus,

n Output 1 1000000000000000000000000000000000000000000000000000000000000000 2 1100000000000000000000000000000000000000000000000000000000000000 3 1110000000000000000000000000000000000000000000000000000000000000 . ... 63 1111111111111111111111111111111111111111111111111111111111111110 64 1111111111111111111111111111111111111111111111111111111111111111

Note that n == 0 is never passed and would fail.

Parameters

n	Integer with 0 < n <= m4ri_radix

#define __M4RI_SET_BIT	(	w,
		spot
	)	((w) \|= (m4ri_one << (spot)))

Set the bit spot (counting from the left) in the word w.

Parameters

w	Word
spot	Integer with 0 <= spot < m4ri_radix

#define __M4RI_TWOPOW ( i ) ((uint64_t)1 << (i))

$2^i$

Parameters

i Integer.

#define __M4RI_WRITE_BIT	(	w,
		spot,
		value
	)	((w) = (((w) & ~(m4ri_one << (spot))) \| (-__M4RI_CONVERT_TO_WORD(value) & (m4ri_one << (spot)))))

Write the value to the bit spot in the word w.

Parameters

w	Word.
spot	Integer with 0 <= spot < m4ri_radix.
value	Either 0 or 1.

#define MAX	(	x,
		y
	)	(((x) > (y))?(x):(y))

Return the maximal element of x and y.

Parameters

x	Word
y	Word

#define MIN	(	x,
		y
	)	(((x) < (y))?(x):(y))

Return the minimal element of x and y.

Parameters

x	Word
y	Word

Examples:: testsuite/bench_elimination.c.

Typedef Documentation

typedef int BIT

Pretty for a boolean int.

The value of a BIT is either 0 or 1.

typedef int rci_t

Type of row and column indexes.

This type is used for integer values that hold row/colum sized values.

typedef int wi_t

Type of word indexes.

This type is used for the array of words that make up a row.

Function Documentation

static BIT m4ri_coin_flip ( )

inlinestatic

Return 1 or 0 uniformly randomly distributed.

Todo:: Allow user to provide her own random() function.

void m4ri_die	(	const char *	errormessage,
			...
	)

Print error message and abort().

The function accepts additional parameters like printf, so e.g. m4ri_die("foo %d bar %f\n",1 ,2.0) is valid and will print the string "foo 1 bar 2.0" before dying.

Parameters

errormessage a string to be printed.

Todo:: Allow user to register callback which is called on m4ri_die().

Warning: The provided string is not free'd.

Examples:: testsuite/bench_elimination.c.

void m4ri_fini ( void )

De-initialize global data structures from the M4RI library.

On Linux/Solaris this is called automatically when the shared library is unloaded, but it doesn't harm if it is called twice.

void m4ri_init ( void )

Initialize global data structures for the M4RI library.

On Linux/Solaris this is called automatically when the shared library is loaded, but it doesn't harm if it is called twice.

static int m4ri_lesser_LSB	(	word	a,
		word	b
	)

inlinestatic

Return true if a's least significant bit is smaller than b's least significant bit.

return true if LSBI(a) < LSBI(b), where LSBI(w) is the index of the least significant bit that is set in w, or 64 if w is zero.

Parameters

a	Word
b	Word

static void* m4ri_mm_calloc	(	size_t	count,
		size_t	size
	)

inlinestatic

Calloc wrapper.

Parameters

count	Number of elements.
size	Size of each element.

Returns: pointer to allocated memory block.

Todo:: Allow user to register calloc function.

static void m4ri_mm_free	(	void *	condemned,
			...
	)

inlinestatic

Free wrapper.

Parameters

condemned Pointer.

Todo:: Allow user to register free function.

static void* m4ri_mm_malloc ( size_t size )

inlinestatic

Malloc wrapper.

Parameters

size	Size in bytes.

Returns: pointer to allocated memory block.

Todo:: Allow user to register malloc function.

static void* m4ri_mm_malloc_aligned	(	size_t	size,
		size_t	alignment
	)

inlinestatic

Aligned malloc wrapper.

This function will attempt to align memory, but does not guarantee success in case neither _mm_malloc nor posix_memalign are available.

Parameters

size	Size in bytes.
alignment	Alignment (16,64,...).

Returns: pointer to allocated memory block.

Todo:: Allow user to register malloc function.

word m4ri_random_word ( )

Return uniformly randomly distributed random word.

Todo:: Allow user to provide her own random() function.

static word m4ri_shrink_bits	(	word const	from,
		rci_t *const	Q,
		int const	length,
		int const	base
	)

inlinestatic

pack bits (inverse of m4ri_spread_bits)

Parameters

from	bitstring
Q	array with bit positions
length	bitsize of the output
base	subtracted from every value in Q

Returns: inverse of m4ri_spread_bits)

See also: m4ri_spread_bits

static word m4ri_spread_bits	(	word const	from,
		rci_t *const	Q,
		int const	length,
		int const	base
	)

inlinestatic

spread bits

Given a bitstring 'from' and a spreading table Q, return a bitstring where the bits of 'from' are in the positions indicated by Q.

Parameters

from	bitstring of length 'length' stored in a word
Q	table with new bit positions
length	bitsize of input
base	subtracted from every value in Q

Returns: bitstring having the same bits as from but spread using Q

See also: m4ri_shrink_bits

static word m4ri_swap_bits ( word v )

inlinestatic

swap bits in the word v

Parameters

v	The word whose bits need to be reversed.

void m4ri_word_to_str	(	char *	destination,
		word	data,
		int	colon
	)

Write a sting representing the word data to destination.

Parameters

destination	Address of buffer of length at least m4ri_radix*1.3
data	Source word
colon	Insert a Colon after every 4-th bit.

Warning: Assumes destination has m4ri_radix*1.3 bytes available

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation