dbm

mingraph_write.c File Reference

Contains implementation of analysis of DBM to minimal graph and its encoding. More...

#include "base/bitstring.h"
#include "dbm/mingraph.h"
#include "mingraph_coding.h"
#include "dbm.h"
#include "debug/macros.h"

Functions

static int32_t * mingraph_encode (const raw_t *dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt, BOOL constraints16, allocator_t c_alloc, size_t offset)

Estimate cheapest encoding and call the corresponding encoding function.

static size_t mingraph_analyzeForMinDBM (const raw_t *dbm, cindex_t dim, uint32_t *bitMatrix)

Analyze a DBM (internal function):

minimal graph reduction information
maximal bits needed
# of contraints needed to save.

static int32_t * mingraph_writeMinDBMDim2 (const raw_t *dbm, cindex_t dim, allocator_t c_alloc, size_t offset)

Save function for dim <= 2.

static void mingraph_writeCopy32 (int32_t *save, const raw_t *dbm, cindex_t dim)

static void mingraph_writeCopy16 (int32_t *save, const raw_t *dbm, cindex_t dim)

static void mingraph_writeMinCouplesij32 (int32_t *where, const raw_t *dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt, uint32_t bitCode)

static void mingraph_writeMinCouplesij16 (int32_t *where, const raw_t *dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt, uint32_t bitCode)

static void mingraph_writeMinBitMatrix32 (int32_t *where, const raw_t *dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt)

static void mingraph_writeMinBitMatrix16 (int32_t *where, const raw_t *dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt)

static uint32_t * mingraph_jumpInt16 (int16_t *ints, size_t n)

Jump int16 integers, padded int32.

size_t dbm_analyzeForMinDBM (const raw_t *dbm, cindex_t dim, uint32_t *bitMatrix)

Analyze a DBM for its minimal graph representation.

int32_t * dbm_writeToMinDBMWithOffset (const raw_t *dbm, cindex_t dim, BOOL minimizeGraph, BOOL tryConstraints16, allocator_t c_alloc, size_t offset)

Save a DBM in minimal representation.

int32_t * dbm_writeAnalyzedDBM (const raw_t *dbm, cindex_t dim, uint32_t *bitMatrix, size_t nbConstraints, BOOL tryConstraints16, allocator_t c_alloc, size_t offset)

Save a pre-analyzed DBM in minimal representation.

size_t dbm_cleanBitMatrix (const raw_t *dbm, cindex_t dim, uint32_t *bitMatrix, size_t nbConstraints)

This is a post-processing function for dbm_analyzeForMinDBM to remove constraints of the form x>=0 that are part of the minimal graph but that do not give much information.

Detailed Description

Contains implementation of analysis of DBM to minimal graph and its encoding.

Function Documentation

size_t dbm_analyzeForMinDBM ( const raw_t * dbm,

cindex_t dim,

uint32_t * bitMatrix

)

Analyze a DBM for its minimal graph representation.
Computes the smallest number of constraints needed to represent the same zone as the full DBM in dbm. The result in returned in bitMatrix: If the bit $i \cdot dim + j$ is set, then the constraint $(i,j)$ of dbm is needed.
Parameters:

dbm,: DBM.

dim,: dimension.

bitMatrix,: bit matrix.

Returns:

number of needed constraints to save
bit matrix that marks which constraints belong to the minimal graph

Precondition:
bitMatrix is a uint32_t[bits2intsize(dim*dim)]

size_t dbm_cleanBitMatrix ( const raw_t * dbm,

cindex_t dim,

uint32_t * bitMatrix,

size_t nbConstraints

)

This is a post-processing function for dbm_analyzeForMinDBM to remove constraints of the form x>=0 that are part of the minimal graph but that do not give much information.

Parameters:

dbm,dim,: DBM of dimension dim

bitMatrix,: bit matrix (already computed minimal graph)

nbConstraints,: the number of constraints of the minimal graph.

Returns:
the updated number of constraints of the modified minimal graph where constraints x>=0 may have been removed.

Precondition:
dbm_analyzeForMinDBM has been called before and nbConstraints corresponds to the number of constraints of the minimal graph.

int32_t* dbm_writeAnalyzedDBM ( const raw_t * dbm,

cindex_t dim,

uint32_t * bitMatrix,

size_t nbConstraints,

BOOL tryConstraints16,

allocator_t c_alloc,

size_t offset

)

Save a pre-analyzed DBM in minimal representation.

Parameters:

dbm,: the DBM to save.

dim,: its dimension.

bitMatrix,: bit matrix resulting from the analysis (ie dbm_analyzeForMinDBM).

nbConstraints,: number of constraints in the bit matrix.

tryConstraints16,: flag to try to save constraints on 16 bits, will cost dim*dim time.

allocFunction,: the allocation function.

offset,: offset for allocation.

Returns:
allocated memory.

Precondition:

dbm is a raw_t[dim*dim]
allocFunction allocates memory in integer units
dbm is closed.
dim > 0 (at least ref clock)
bitMatrix != NULL, obtained from dbm_analyzeForMinDBM
nbConstraints = number of bits set in bitMatrix
bitMatrix is a uint32_t[bits2intsize(dim*dim)]

Postcondition:

the returned memory is of size offset+something unknown from the caller point of view.
bitMatrix is cleaned from the constraints xi >= 0

int32_t* dbm_writeToMinDBMWithOffset ( const raw_t * dbm,

cindex_t dim,

BOOL minimizeGraph,

BOOL tryConstraints16,

allocator_t c_alloc,

size_t offset

)

Save a DBM in minimal representation.
The API supports allocation of larger data structures than needed for the actual zone representation. When the offset argument is bigger than zero, offset extra integers are allocated and the zone is written with the given offset. Thus when int32_t[data_size] is needed to represent the reduced zone, an int32_t array of size +data_sizeis allocated. The first offset elements can be used by the caller. It is important to notice that the other functions typically expect a pointer to the actual zone data and not to the beginning of the allocated block. Thus in the following piece of code, most functions expect mg and not memory:

int32_t *memory = dbm_writeToMinDBMWithOffset(...); mingraph_t mg = &memory[offset];
NOTES:

if offset is 0 and dim is 1, NULL may be returned. NULL is valid as an input to the other functions.
it could be possible to send as argument the maximal value of the constraints that can be deduced from the maximal constants but this would tie the algorithm to the extrapolation.

Parameters:

dbm,: the DBM to save.

dim,: its dimension.

minimizeGraph,: activate minimized graph reduction. If it is FALSE, then the DBM is copied without its diagonal.

tryConstraints16,: flag to try to save constraints on 16 bits, will cost dim*dim time.

c_alloc,: C allocator wrapper

offset,: offset for allocation.

Returns:
allocated memory.

Precondition:

dbm is a raw_t[dim*dim]
allocFunction allocates memory in integer units
dbm is closed.
dim > 0 (at least ref clock)

Postcondition:
the returned memory is of size offset+something unknown from the caller point of view.

static size_t mingraph_analyzeForMinDBM ( const raw_t * dbm,

cindex_t dim,

uint32_t * bitMatrix

) [static]

Analyze a DBM (internal function):

minimal graph reduction information
maximal bits needed
# of contraints needed to save.

Parameters:

dbm,: DBM to analyze

dim,: dimension

bitMatrix,: bit matrix to write results in

Precondition:

dim > 2
bitMatrix is a uint32_t[bits2intsize(dim*dim)]

static int32_t * mingraph_encode ( const raw_t * dbm,

cindex_t dim,

const uint32_t * bitMatrix,

size_t cnt,

BOOL constraints16,

allocator_t c_alloc,

size_t offset

) [static]

Estimate cheapest encoding and call the corresponding encoding function.

Parameters:

dbm,: dbm to save.

dim,: dimension.

bitMatrix,: bit matrix for the constraints to take.

cnt,: number of constraints to save.

maxConstraint,: maximal (!=infinity) constraint value.

allocFunction,: allocation function.

allocData,: custom data for the allocation function.

offset,: offset to use for the allocation.

Returns:
encoded minimal graph.

Precondition:
dim > 2, otherwise always copy.

static uint32_t* mingraph_jumpInt16 ( int16_t * ints,

size_t n

) [inline, static]

Jump int16 integers, padded int32.

Parameters:

ints,: int16 starting point (padded int32)

n,: nb of int16 to jump

Returns:
ints+n padded int32 as int32*

static void mingraph_writeCopy16 ( int32_t * save,

const raw_t * dbm,

cindex_t dim

) [static]

static void mingraph_writeCopy32 ( int32_t * save,

const raw_t * dbm,

cindex_t dim

) [static]

static void mingraph_writeMinBitMatrix16 ( int32_t * where,

const raw_t * dbm,

cindex_t dim,

const uint32_t * bitMatrix,

size_t cnt

) [static]

static void mingraph_writeMinBitMatrix32 ( int32_t * where,

const raw_t * dbm,

cindex_t dim,

const uint32_t * bitMatrix,

size_t cnt

) [static]

static void mingraph_writeMinCouplesij16 ( int32_t * where,

const raw_t * dbm,

cindex_t dim,

const uint32_t * bitMatrix,

size_t cnt,

uint32_t bitCode

) [static]

static void mingraph_writeMinCouplesij32 ( int32_t * where,

const raw_t * dbm,

cindex_t dim,

const uint32_t * bitMatrix,

size_t cnt,

uint32_t bitCode

) [static]

static int32_t * mingraph_writeMinDBMDim2 ( const raw_t * dbm,

cindex_t dim,

allocator_t c_alloc,

size_t offset

) [static]

Save function for dim <= 2.

Parameters:

dbm,dim,: DBM of dimension dim

allocFunction,allocData,: allocation function and its data

offset,: offset to use for allocation

Precondition:
dim <= 2

Returns:
allocated memory with mingraph in it.

Generated on Fri Jun 30 00:02:45 2006 for Module dbm by

1.4.2


Functions
static int32_t *	mingraph_encode (const raw_t dbm, cindex_t dim, const uint32_t bitMatrix, size_t cnt, BOOL constraints16, allocator_t c_alloc, size_t offset)
	Estimate cheapest encoding and call the corresponding encoding function.
static size_t	mingraph_analyzeForMinDBM (const raw_t dbm, cindex_t dim, uint32_t bitMatrix)
	Analyze a DBM (internal function): minimal graph reduction information maximal bits needed # of contraints needed to save.
static int32_t *	mingraph_writeMinDBMDim2 (const raw_t *dbm, cindex_t dim, allocator_t c_alloc, size_t offset)
	Save function for dim <= 2.
static void	mingraph_writeCopy32 (int32_t save, const raw_t dbm, cindex_t dim)
static void	mingraph_writeCopy16 (int32_t save, const raw_t dbm, cindex_t dim)
static void	mingraph_writeMinCouplesij32 (int32_t where, const raw_t dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt, uint32_t bitCode)
static void	mingraph_writeMinCouplesij16 (int32_t where, const raw_t dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt, uint32_t bitCode)
static void	mingraph_writeMinBitMatrix32 (int32_t where, const raw_t dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt)
static void	mingraph_writeMinBitMatrix16 (int32_t where, const raw_t dbm, cindex_t dim, const uint32_t *bitMatrix, size_t cnt)
static uint32_t *	mingraph_jumpInt16 (int16_t *ints, size_t n)
	Jump int16 integers, padded int32.
size_t	dbm_analyzeForMinDBM (const raw_t dbm, cindex_t dim, uint32_t bitMatrix)
	Analyze a DBM for its minimal graph representation.
int32_t *	dbm_writeToMinDBMWithOffset (const raw_t *dbm, cindex_t dim, BOOL minimizeGraph, BOOL tryConstraints16, allocator_t c_alloc, size_t offset)
	Save a DBM in minimal representation.
int32_t *	dbm_writeAnalyzedDBM (const raw_t dbm, cindex_t dim, uint32_t bitMatrix, size_t nbConstraints, BOOL tryConstraints16, allocator_t c_alloc, size_t offset)
	Save a pre-analyzed DBM in minimal representation.
size_t	dbm_cleanBitMatrix (const raw_t dbm, cindex_t dim, uint32_t bitMatrix, size_t nbConstraints)
	This is a post-processing function for dbm_analyzeForMinDBM to remove constraints of the form x>=0 that are part of the minimal graph but that do not give much information.