M4RI 1.0.1
Data Structures | Defines | Typedefs | Functions | Variables
misc.h File Reference

Helper functions. More...

#include <stdlib.h>
#include <assert.h>
#include <string.h>

Go to the source code of this file.

Data Structures

struct  _mm_block

Defines

#define RADIX   (sizeof(word)<<3)
 The number of bits in a word.
#define ONE   ((word)1)
 The number one as a word.
#define FFFF   ((word)0xffffffffffffffffull)
 The number 2^64-1 as a word.
#define MAX(x, y)   (((x) > (y))?(x):(y))
 Return the maximal element of x and y.
#define MIN(x, y)   (((x) < (y))?(x):(y))
 Return the minimal element of x and y.
#define DIV_CEIL(x, y)   (((x)%(y))?(x)/(y)+1:(x)/(y))
 Return r such that x elements fit into r blocks of length y.
#define TRUE   1
 Pretty for 1.
#define FALSE   0
 Pretty for 0.
#define TWOPOW(i)   (ONE<<(i))
 $2^i$
#define CLR_BIT(w, spot)   ((w) &= ~(ONE<<(RADIX - (spot) - 1)))
 Clear the bit spot (counting from the left) in the word w.
#define SET_BIT(w, spot)   ((w) |= (ONE<<(RADIX - (spot) - 1)))
 Set the bit spot (counting from the left) in the word w.
#define GET_BIT(w, spot)   (((w) & (ONE<<(RADIX - (spot) - 1))) >> (RADIX - (spot) - 1))
 Get the bit spot (counting from the left) in the word w.
#define WRITE_BIT(w, spot, value)   ((w) = (((w) &~(ONE<<(RADIX - (spot) - 1))) | (((word)(value))<<(RADIX - (spot) - 1))))
 Write the value to the bit spot in the word w.
#define FLIP_BIT(w, spot)   ((w) ^= (ONE<<(RADIX - (spot) - 1)))
 Flip the spot in the word w.
#define LEFTMOST_BITS(w, n)   ((w) & ~((ONE<<(RADIX-(n)))-1))>>(RADIX-(n))
 Return the n leftmost bits of the word w.
#define RIGHTMOST_BITS(w, n)   (((w)<<(RADIX-(n)-1))>>(RADIX-(n)-1))
 Return the n rightmost bits of the word w.
#define LEFT_BITMASK(n)   (~((ONE << ((RADIX - (n % RADIX))%RADIX) ) - 1))
 creat a bit mask to zero out all but the nRADIX leftmost bits.
#define RIGHT_BITMASK(n)   (FFFF>>( (RADIX - (n%RADIX))%RADIX ))
 creat a bit mask to zero out all but the nRADIX rightmost bits.
#define BITMASK(n)   (ONE<<(RADIX-((n)%RADIX)-1))
 creat a bit mask to zero out all but the nRADIX bit.
#define 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.
#define CPU_L2_CACHE   524288
#define CPU_L1_CACHE   16384
#define MM_MAX_MALLOC   ((1ULL)<<30)
 Maximum number of bytes allocated in one malloc() call.
#define ENABLE_MMC
 Enable memory block cache (default: disabled)
#define M4RI_MMC_NBLOCKS   16
 Number of blocks that are cached.
#define M4RI_MMC_THRESHOLD   CPU_L2_CACHE
 Maximal size of blocks stored in cache.

Typedefs

typedef unsigned long long word
typedef unsigned char BIT
 Pretty for unsigned char.
typedef struct _mm_block mmb_t

Functions

static int leftmost_bit (word a)
void m4ri_die (const char *errormessage,...)
 Print error message and abort().
void m4ri_word_to_str (char *destination, word data, int colon)
 Write a sting representing the word data to destination.
static BIT m4ri_coin_flip ()
 Return 1 or 0 uniformly randomly distributed.
word m4ri_random_word ()
 Return uniformly randomly distributed random word.
void m4ri_init (void)
 Initialize global data structures for the M4RI library.
void m4ri_fini (void)
 De-initialize global data structures from the M4RI library.
static void * m4ri_mm_calloc (int count, int size)
 Calloc wrapper.
static void * m4ri_mm_malloc (int size)
 Malloc wrapper.
static void m4ri_mm_free (void *condemned,...)
 Free wrapper.
static mmb_tm4ri_mmc_handle (void)
 Return handle for locale memory management cache.
static void * m4ri_mmc_malloc (size_t size)
 Allocate size bytes.
static void * m4ri_mmc_calloc (size_t size, size_t count)
 Allocate size times count zeroed bytes.
static void m4ri_mmc_free (void *condemned, size_t size)
 Free the data pointed to by condemned of the given size.
static void m4ri_mmc_cleanup (void)
 Cleans up the cache.

Variables

mmb_t m4ri_mmc_cache [M4RI_MMC_NBLOCKS]

Detailed Description

Helper functions.

Author:
Gregory Bard <bard@fordham.edu>
Martin Albrecht <M.R.Albrecht@rhul.ac.uk>

Define Documentation

#define 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 BITMASK (   n)    (ONE<<(RADIX-((n)%RADIX)-1))

creat a bit mask to zero out all but the nRADIX bit.

Parameters:
nInteger
#define CLR_BIT (   w,
  spot 
)    ((w) &= ~(ONE<<(RADIX - (spot) - 1)))

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

Parameters:
wWord
spotInteger with 0 <= spot < RADIX
#define CPU_L1_CACHE   16384

Fix some standard value for L1 cache size if it couldn't be determined by configure.

#define CPU_L2_CACHE   524288

Fix some standard value for L2 cache size if it couldn't be determined by configure.

#define DIV_CEIL (   x,
 
)    (((x)%(y))?(x)/(y)+1:(x)/(y))

Return r such that x elements fit into r blocks of length y.

Parameters:
xNumber of elements
yBlock size
#define FLIP_BIT (   w,
  spot 
)    ((w) ^= (ONE<<(RADIX - (spot) - 1)))

Flip the spot in the word w.

Parameters:
wWord.
spotInteger with 0 <= spot < RADIX.
#define GET_BIT (   w,
  spot 
)    (((w) & (ONE<<(RADIX - (spot) - 1))) >> (RADIX - (spot) - 1))

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

Parameters:
wWord
spotInteger with 0 <= spot < RADIX
#define LEFT_BITMASK (   n)    (~((ONE << ((RADIX - (n % RADIX))%RADIX) ) - 1))

creat a bit mask to zero out all but the nRADIX leftmost bits.

Parameters:
nInteger
#define LEFTMOST_BITS (   w,
 
)    ((w) & ~((ONE<<(RADIX-(n)))-1))>>(RADIX-(n))

Return the n leftmost bits of the word w.

Parameters:
wWord
nInteger with 0 <= spot < RADIX
#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
#define RIGHT_BITMASK (   n)    (FFFF>>( (RADIX - (n%RADIX))%RADIX ))

creat a bit mask to zero out all but the nRADIX rightmost bits.

Parameters:
nInteger
Warning:
Does not handle multiples of RADIX correctly
#define RIGHTMOST_BITS (   w,
 
)    (((w)<<(RADIX-(n)-1))>>(RADIX-(n)-1))

Return the n rightmost bits of the word w.

Parameters:
wWord
nInteger with 0 <= spot < RADIX
#define SET_BIT (   w,
  spot 
)    ((w) |= (ONE<<(RADIX - (spot) - 1)))

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

Parameters:
wWord
spotInteger with 0 <= spot < RADIX
#define TWOPOW (   i)    (ONE<<(i))

$2^i$

Parameters:
iInteger.
#define WRITE_BIT (   w,
  spot,
  value 
)    ((w) = (((w) &~(ONE<<(RADIX - (spot) - 1))) | (((word)(value))<<(RADIX - (spot) - 1))))

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

Parameters:
wWord.
spotInteger with 0 <= spot < RADIX.
valueEither 0 or 1.

Typedef Documentation

typedef struct _mm_block mmb_t

The mmc memory management functions check a cache for re-usable unused memory before asking the system for it.

typedef unsigned long long word

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


Function Documentation

static int leftmost_bit ( word  a) [inline, static]

Return the index of the leftmost bit in a for a nonzero.

Parameters:
aWord
static BIT m4ri_coin_flip ( ) [inline, static]

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 void* m4ri_mm_calloc ( int  count,
int  size 
) [inline, static]

Calloc wrapper.

Parameters:
countNumber of elements.
sizeSize of each element.
Todo:
Allow user to register calloc function.
static void m4ri_mm_free ( void *  condemned,
  ... 
) [inline, static]

Free wrapper.

Parameters:
condemnedPointer.
Todo:
Allow user to register free function.
static void* m4ri_mm_malloc ( int  size) [inline, static]

Malloc wrapper.

Parameters:
sizeSize in bytes.
Todo:
Allow user to register malloc function.
static void* m4ri_mmc_calloc ( size_t  size,
size_t  count 
) [inline, static]

Allocate size times count zeroed bytes.

Parameters:
sizeNumber of bytes per block.
countNumber of blocks.
Warning:
Not thread safe.
static void m4ri_mmc_cleanup ( void  ) [inline, static]

Cleans up the cache.

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

Warning:
Not thread safe.
static void m4ri_mmc_free ( void *  condemned,
size_t  size 
) [inline, static]

Free the data pointed to by condemned of the given size.

Parameters:
condemnedPointer to memory.
sizeNumber of bytes.
Warning:
Not thread safe.
static mmb_t* m4ri_mmc_handle ( void  ) [inline, static]

Return handle for locale memory management cache.

Attention:
Not thread safe.
static void* m4ri_mmc_malloc ( size_t  size) [inline, static]

Allocate size bytes.

Parameters:
sizeNumber of bytes.
word m4ri_random_word ( )

Return uniformly randomly distributed random word.

Todo:
Allow user to provide her own random() function.
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 RADIX*1.3
dataSource word
colonInsert a Colon after every 4-th bit.
Warning:
Assumes destination has RADIX*1.3 bytes available

Variable Documentation

mmb_t m4ri_mmc_cache[M4RI_MMC_NBLOCKS]

The actual memory block cache.