M4RI  20140914
Macros | Typedefs | Functions | Variables
misc.h File Reference

Helper functions. More...

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

Go to the source code of this file.

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,
 
)    (((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
wWord
spotInteger 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
wWord.
spotInteger 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
wWord
spotInteger with 0 <= spot < m4ri_radix
#define __M4RI_GNUC_PREREQ (   maj,
  min 
)    FALSE

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

Parameters
majThe major version.
minThe 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
nInteger 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
nInteger with 0 < n <= m4ri_radix - offset
offsetColumn 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
nInteger 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
wWord
spotInteger with 0 <= spot < m4ri_radix
#define __M4RI_TWOPOW (   i)    ((uint64_t)1 << (i))

$2^i$

Parameters
iInteger.
#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
wWord.
spotInteger with 0 <= spot < m4ri_radix.
valueEither 0 or 1.
#define MAX (   x,
 
)    (((x) > (y))?(x):(y))

Return the maximal element of x and y.

Parameters
xWord
yWord
#define MIN (   x,
 
)    (((x) < (y))?(x):(y))

Return the minimal element of x and y.

Parameters
xWord
yWord
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
errormessagea 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
aWord
bWord
static void* m4ri_mm_calloc ( size_t  count,
size_t  size 
)
inlinestatic

Calloc wrapper.

Parameters
countNumber of elements.
sizeSize 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
condemnedPointer.
Todo:
Allow user to register free function.
static void* m4ri_mm_malloc ( size_t  size)
inlinestatic

Malloc wrapper.

Parameters
sizeSize 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
sizeSize in bytes.
alignmentAlignment (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
frombitstring
Qarray with bit positions
lengthbitsize of the output
basesubtracted 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
frombitstring of length 'length' stored in a word
Qtable with new bit positions
lengthbitsize of input
basesubtracted 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
vThe 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
destinationAddress of buffer of length at least m4ri_radix*1.3
dataSource word
colonInsert a Colon after every 4-th bit.
Warning
Assumes destination has m4ri_radix*1.3 bytes available