%%	options

copyright owner	=	Dirk Krause
copyright year	=	2011-2014
license		=	bsd

%%	header

#include "dk3conf.h"
#include "dk3types.h"

#ifdef __cplusplus
extern "C" {
#endif


/**	Open a bit field (bit array).
	@param	nbits	Number of bits.
	@param	app	Application structure for diagnostics, may be NULL.
	@return	Pointer to new bit field on success, NULL on error.
*/
dk3_bf_t *
dk3bf_open_app(size_t nbits, dk3_app_t *app);

/**	Close bit field.
	@param	b	Bit field to close.
*/
void
dk3bf_close(dk3_bf_t *b);

/**	Set or reset one bit.
	@param	b	Bit field.
	@param	n	Index of bit to set.
	@param	v	New bit value (1 or 0).
*/
void
dk3bf_set(dk3_bf_t *b, size_t n, int v);

/**	Get one bit value.
	@param	b	Bit field.
	@param	n	Index of bit.
	@return	1 or 0 depending on the bit value.
*/
int
dk3bf_get(dk3_bf_t const *b, size_t n);

/**	Open a bit matrix.
	@param	x	Number of columns.
	@param	y	Number of rows.
	@param	app	Application structure for diagnostics, may be NULL.
	@return	Pointer to new bit matrix on success, NULL on error.
*/
dk3_bm_t *
dk3bm_open(size_t x, size_t y, dk3_app_t *app);

/**	Close bit matrix.
	@param	b	Bit matrix to close.
*/
void
dk3bm_close(dk3_bm_t *b);

/**	Set cache size (threshold to switch between traditional
	algorithm for dk3bm_expand and cache friendly algorithm).
	@param	b	Bit matrix.
	@param	cs	Maximum matrix size for traditional algorithm.
*/
void
dk3bm_set_cache_size(dk3_bm_t *b, size_t cs);

/**	Set or reset  one bit.
	@param	b	Bit matrix.
	@param	x	Column number.
	@param	y	Row number.
	@param	v	New value for bit.
*/
void
dk3bm_set(dk3_bm_t *b, size_t x, size_t y, int v);

/**	Get one bit.
	@param	b	Bit matrix.
	@param	x	Column number.
	@param	y	Row number.
	@return	1 or 0 depending on the bit value.
*/
int
dk3bm_get(dk3_bm_t const *b, size_t x, size_t y);

/**	Expand bit matrix. The matrix must be square.
	@param	b	Bit matrix.
*/
void
dk3bm_expand(dk3_bm_t *b);


#ifdef __cplusplus
}
#endif



%%	module

#include "dk3all.h"
#include "dk3cores.h"


$!trace-include


/**	Bit mask to set/retrieve single bits in a byte.
*/
static unsigned char const dk3bf_bits_in_byte[] = {
0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
};



/**	Bit masks to reset a single bit in a byte
*/
static unsigned char const dk3bf_not_in_byte[] = {
0x7F, 0xBF, 0xDF, 0xEF, 0xF7, 0xFB, 0xFD, 0xFE
};



/**	Keywords used by the module, not localized.
*/
static dkChar const * const	dk3bf_kw[] = {
$!string-table	macro=dkT
#
#	0	Threshold to switch from traditional to cache friendly
#
/bitmatrix/expand/cache-friendly
#
#	1	Amount of cache available
#
/proc/cache/available
#
#	2	Percents of entire cache available to this program
#
/proc/cache/percent
$!end
};

void
dk3bf_close(dk3_bf_t *b)
{
  if(b) {
    dk3_release(b->data);
    b->nbits = 0; b->app = NULL;
    dk3_delete(b);
  }
}



dk3_bf_t *
dk3bf_open_app(size_t nbits, dk3_app_t *app)
{
  dk3_bf_t	*back = NULL;	
  size_t	sz = 0;		/* Number of bytes needed. */
  if(nbits) {
    sz = nbits / 8;
    if(nbits % 8) { sz++; }
    back = dk3_new_app(dk3_bf_t,1,app);
    if(back) {
      back->nbits = nbits; back->data = NULL; back->app = app;
      back->data = dk3_new_app(unsigned char,sz,app);
      if(back->data) {
	dk3mem_res((void *)(back->data), sz);
      } else {
        dk3bf_close(back); back = NULL;
      }
    }
  }
  return back;
}



void
dk3bf_set(dk3_bf_t *b, size_t n, int v)
{
  size_t	byteno = 0;	/* Byte index in data. */
  size_t	inbyte = 0;	/* Number of bit within the byte. */
  if(b) {
    if(n < b->nbits) {
      byteno = n / 8; inbyte = n % 8;
      if(v) {
        (b->data)[byteno] |= dk3bf_bits_in_byte[inbyte];
      } else {
        (b->data)[byteno] &= (~(dk3bf_bits_in_byte[inbyte]));
      }
    } else {
      if(b->app) {
        /* ERROR: Index out of range. */
	dk3app_log_i1(b->app, DK3_LL_ERROR, 200);
      }
    }
  }
}



int
dk3bf_get(dk3_bf_t const *b, size_t n)
{
  int back = 0;
  size_t	byteno = 0;	/* Byte index in data. */
  size_t	inbyte = 0;	/* Number of bit within the byte. */
  if(b) {
    if(n < b->nbits) {
      byteno = n / 8; inbyte = n % 8;
      if(((b->data)[byteno]) & (dk3bf_bits_in_byte[inbyte])) {
        back = 1;
      }
    } else {
      if(b->app) {
        /* ERROR: Index out of range. */
	dk3app_log_i1(b->app, DK3_LL_ERROR, 200);
      }
    }
  }
  return back;
}



#if VERSION_BEFORE_20140605

void
dk3bm_close(dk3_bm_t *b)
{
  size_t i = 0;		/* Index of current row to delete. */
  if(b) {
    if(b->data) {
      for(i = 0; i < b->rows; i++) {
        dk3_release((b->data)[i]);
      }
      dk3_delete(b->data);
    }
    b->data = NULL; b->app = NULL; b->columns = 0; b->rows = 0;
    dk3_delete(b);
  }
}



dk3_bm_t *
dk3bm_open(size_t x, size_t y, dk3_app_t *app)
{
  size_t	bytes_per_row = 0;	/* Number of bytes per row. */
  size_t	i = 0;			/* Current row to initialize. */
  int		ok = 0;			/* Flag: Success. */
  dk3_bm_t *back = NULL;
  if((x) && (y)) {
    back = dk3_new_app(dk3_bm_t,1,app);
    if(back) {
      back->columns = x; back->rows = y; back->app = app;
      back->data = NULL;
      bytes_per_row = x / 8;
      if(x % 8) { bytes_per_row++; }
      back->data = dk3_new_app(DK3_PUCHAR,y,app);
      if(back->data) {
        ok = 1;
        for(i = 0; i < y; i++) { (back->data)[i] = NULL; }
	for(i = 0; i < y; i++) {
	  (back->data)[i] = dk3_new_app(unsigned char,bytes_per_row,app);
	  if((back->data)[i]) {
	    dk3mem_res((void *)((back->data)[i]), bytes_per_row);
	  } else {
	    ok = 0;
	  }
	}
	if(ok == 0) {
	  dk3bm_close(back); back = NULL;
	}
      } else {
        dk3_delete(back); back = NULL;
      }
    }
  }
  return back;
}



void
dk3bm_set(dk3_bm_t *b, size_t x, size_t y, int v)
{
  unsigned char *pu = NULL;	/* Row pointer. */
  size_t	byteno = 0;	/* Index of byte in row. */
  size_t	bitno = 0;	/* Index of bit within the byte. */
  if(b) {
    if((x < b->columns) && (y < b->rows)) {
      pu = (b->data)[y];
      byteno = x / 8; bitno = x % 8;
      if(v) {
        pu[byteno] |= dk3bf_bits_in_byte[bitno];
      } else {
        pu[byteno] &= (~(dk3bf_bits_in_byte[bitno]));
      }
    }
  }
}



int
dk3bm_get(dk3_bm_t const *b, size_t x, size_t y)
{
  int back = 0;
  unsigned char *pu = NULL;	/* Row pointer. */
  size_t	byteno = 0;	/* Index of byte within the row. */
  size_t	bitno = 0;	/* Index of bit within the byte. */
  if(b) {
    if((x < b->columns) && (y < b->rows)) {
      pu = (b->data)[y];
      byteno = x / 8; bitno = x % 8;
      if((pu[byteno]) & (dk3bf_bits_in_byte[bitno])) {
        back = 1;
      }
    }
  }
  return back;
}



void
dk3bm_expand(dk3_bm_t *b)
{
  int		f_change_found = 0;	/* Flag: Change found in this pass. */
  size_t	i = 0;			/* Source node number. */
  size_t 	j = 0;			/* Destination node number. */
  size_t 	k = 0;			/* Intermediate node number. */
  size_t 	p = 0;			/* Number of current pass. */
  if(b) {
    if(b->columns == b->rows) {
      p = 0;
      do {
        f_change_found = 0;
	for(i = 0; i < b->columns; i++) {
	  for(j = 0; j < b->rows; j++) {
	    if(!dk3bm_get(b, i, j)) {
	      for(k = 0; k < b->columns; k++) {
	        if(dk3bm_get(b, i, k)) {
		  if(dk3bm_get(b, k, j)) {
		    dk3bm_set(b, i, j, 1);
		    f_change_found = 1;
		  }
		}
	      }
	    }
	  }
	}
	p++;
      } while((f_change_found) && (p < b->columns));
    } else {
      if(b->app) {
        /* ERROR: Matrix must be a square! */
	dk3app_log_i1(b->app, DK3_LL_ERROR, 201);
      }
    }
  }
}


#else



void
dk3bm_close(dk3_bm_t *b)
{
  size_t	i;
  if (b) {
    if (b->data) {
      if (b->columns < b->rows) {
        for (i = 0; i < b->columns; i++) {
	  dk3_release((b->data)[i]);
	}
      } else {
        for (i = 0; i < b->rows; i++) {
	  dk3_release((b->data)[i]);
	}
      }
      dk3_delete(b->data);
    }
    b->data = NULL;
    b->app = NULL;
    b->columns = 0;
    b->rows = 0;
    b->cachesize = 0;
    dk3_delete(b);
  }
}



#if VERSION_BEFORE_20140809

/**	Find cache size available to this bit matrix expansion.
	@param	app	Application structure.
	@return	Cache size if preferences found, 0 otherwise.
*/
static
size_t
dk3bf_get_cache_size(dk3_app_t *app)
{
  dkChar		 buf[128];
  unsigned long		 ul	= 0UL;
  size_t		 back = 0;
  int			 found = 0;
  int			 ec = 0;
  $? "+ dk3bf_get_cache_size"
  if (dk3app_get_pref(app, dk3bf_kw[0], buf, DK3_SIZEOF(buf,dkChar))) {
#if VERSION_BEFORE_20140716
    if (1 == dk3sf_sscanf3(buf, dkT("%lu"), &ul))
#else
    if (0 != dk3ma_ul_from_string(&ul, buf, NULL))
#endif
    {
      back = (size_t)ul;
      found = 1;
      if ((unsigned long)back != ul) {
        back = 0;
	found = 0;
      }
    }
  }
  if (!(found)) {
    if (dk3app_get_pref(app, dk3bf_kw[1], buf, DK3_SIZEOF(buf,dkChar))) {
#if VERSION_BEFORE_20140716
      if (1 == dk3sf_sscanf3(buf, dkT("%lu"), &ul))
#else
      if (0 != dk3ma_ul_from_string(&ul, buf, NULL))
#endif
      {
        back = (size_t)ul;
	found = 1;
	if ((unsigned long)back != ul) {
	  back = 0;
	  found = 0;
	}
	if (found) {
	  found = 0;
	  if (dk3app_get_pref(app, dk3bf_kw[2], buf, DK3_SIZEOF(buf,dkChar))) {
#if VERSION_BEFORE_20140716
	    if (1 == dk3sf_sscanf3(buf, dkT("%lu"), &ul))
#else
	    if (0 != dk3ma_ul_from_string(&ul, buf, NULL))
#endif
	    {
	      back = dk3mem_mul_size_t(back, (size_t)ul, &ec) / 100;
	      if (ec) {
	        back = 0;
	      } else {
	        found = 1;
	      }
	    }
	  }
	  if ((back) && (!(found))) {
	    back = back / 4;
	    if (0 < back) { back = 1; }
	  }
	}
      }
    }
  } $? "- dk3bf_get_cache_size %lu", (unsigned long)back
  return back;
}

#else

/**	Find cache size available to this bit matrix expansion.
	@param	app	Application structure.
	@return	Cache size if preferences found, 0 otherwise.
*/
static
size_t
dk3bf_get_cache_size(dk3_app_t *app)
{

  dkChar		buf[128];	/* Preference value text */
  dk3_um_t		um1;		/* From preferences */
  dk3_um_t		um2;		/* From preferences */
  size_t		back	= 0;	
  int			ec	= 0;	/* Error code */
  $? "+ dk3bf_get_cache_size"
  if (dk3app_get_pref(app, dk3bf_kw[0], buf, DK3_SIZEOF(buf,dkChar))) {
#if VERSION_BEFORE_20140716
    if (dk3ma_string_to_um(&um1, buf))
#else
    if (0 != dk3ma_um_from_string(&um1, buf, NULL))
#endif
    {
#if VERSION_BEFORE_20140716
      back = dk3ma_um_to_sz(um1, NULL);
#else
#if DK3_SIZEOF_SIZE_T >= DK3_SIZEOF_UM
      back = (size_t)um1;
#else
      if ((dk3_um_t)DK3_SIZE_T_MAX >= um1) {
        back = (size_t)um1;
      }
#endif
#endif
    }
  }
  if (0 == back) {
    if (dk3app_get_pref(app, dk3bf_kw[1], buf, DK3_SIZEOF(buf,dkChar))) {
#if VERSION_BEFORE_20140716
      if (dk3ma_string_to_um(&um1, buf))
#else
      if (0 != dk3ma_um_from_string(&um1, buf, NULL))
#endif
      {
        if (dk3app_get_pref(app, dk3bf_kw[2], buf, DK3_SIZEOF(buf,dkChar))) {
#if VERSION_BEFORE_20140716
	  if (dk3ma_string_to_um(&um2, buf))
#else
	  if (0 != dk3ma_um_from_string(&um2, buf, NULL))
#endif
	  {
	    if (DK3_UM_0 < um2) {
	      if ((dk3_um_t)100U >= um2) {
	        back = dk3ma_um_to_sz(
		  (dk3ma_um_mul_ok(um1, um2, &ec) / ((dk3_um_t)100U)),
		  &ec
		);
		if (0 != ec) { back = 0; }
	      }
	    }
	  }
	}
	if (0 == back) {
	  ec = 0;
	  back = dk3ma_um_to_sz((um1 / ((dk3_um_t)4U)), &ec);
	  if (0 != ec) { back = 0; }
	}
      }
    }
  }
  $? "- dk3bf_get_cache_size"
  return back;
}

#endif



dk3_bm_t *
dk3bm_open(size_t x, size_t y, dk3_app_t *app)
{
  dk3_bm_t	*back	= NULL;
  size_t	 bpstr	= 0;		/* Bytes per strip */
  size_t	 i	= 0;		/* Current strip index */
  int		 ok	= 0;		/* Flag: Successfully */
  $? "+ dk3bm_open %lu %lu", (unsigned long)x, (unsigned long)y
  if ((x) && (y)) {
    back = dk3_new_app(dk3_bm_t,1,app);
    if (back) {
      back->columns = x;
      back->rows = y;
      back->app = app;
      back->cachesize = 0;
      back->data = NULL;
      if (x < y) {			$? ". saving column by column"
        bpstr = y / 8;
	if (y % 8) { bpstr++; }
	back->data = dk3_new_app(DK3_PUCHAR,x,app);
	if (back->data) {		$? ". array allocation ok"
	  ok = 1;
	  for (i = 0; i < x; i++) { (back->data)[i] = NULL; }
	  for (i = 0; i < x; i++) {
	    (back->data)[i] = dk3_new_app(unsigned char,bpstr,app);
	    if ((back->data)[i]) {
	      dk3mem_res((void *)((back->data)[i]), bpstr);
	    } else {
	      ok = 0;
	    }
	  }
	  if (!(ok)) {			$? "! stripe(s) allocation failed"
	    dk3bm_close(back); back = NULL;
	  }
	} else {			$? "! array allocation failed"
	  dk3_release(back);
	}
      } else {				$? ". saving row by row"
        bpstr = x / 8;
	if (x % 8) { bpstr++; }
	back->data = dk3_new_app(DK3_PUCHAR,y,app);
	if (back->data) {		$? ". array allocation ok"
	  ok = 1;
	  for (i = 0; i < y; i++) { (back->data)[i] = NULL; }
	  for (i = 0; i < y; i++) {
	    (back->data)[i] = dk3_new_app(unsigned char,bpstr,app);
	    if ((back->data)[i]) {
	      dk3mem_res((void *)((back->data)[i]), bpstr);
	    } else {
	      ok = 0;
	    }
	  }
	  if (!(ok)) {			$? "! failure(s) in stripe allocation"
	    dk3bm_close(back); back = NULL;
	  }
	} else {			$? "! array allocation failed"
	  dk3_release(back);
	}
      } 
      if (back) {
        if (app) {
	  back->cachesize = dk3bf_get_cache_size(app);
	}
      }
    } else {				$? "! allocation failed"
    }
  } else {				$? "! wrong arguments"
  }
  $? "- dk3bm_open %s", TR_PTR(back)
  return back;
}



void
dk3bm_set_cache_size(dk3_bm_t *b, size_t cs)
{
  if (b) { b->cachesize = cs; }
}



void
dk3bm_set(dk3_bm_t *b, size_t x, size_t y, int v)
{
  unsigned char		*pu	= NULL;	/* Stripe pointer */
  size_t		 byteno	= 0;	/* Index of byte in stripe */
  size_t		 bitno	= 0;	/* Index of bit within the byte */
  $? "+ dk3bm_set %lu %lu %d", (unsigned long)x, (unsigned long)y, v
  if (b) {
    if ((x < b->columns) && (y < b->rows)) {
      if (b->columns < b->rows) {
        pu = (b->data)[x];
	byteno = y / 8;
	bitno  = y % 8;
      } else {
        pu = (b->data)[y];
	byteno = x / 8;
	bitno  = x % 8;
      }
      if (v) {
        pu[byteno] |= dk3bf_bits_in_byte[bitno];
      } else {
        pu[byteno] &= dk3bf_not_in_byte[bitno];
      }
    }
  }
  $? "- dk3bm_set"
}



int
dk3bm_get(dk3_bm_t const *b, size_t x, size_t y)
{
  unsigned char		*pu	= NULL;	/* Stripe pointer */
  size_t		 byteno	= 0;	/* Index of byte within stripe */
  size_t		 bitno	= 0;	/* Index of bit within byte */
  int			 back	= 0;

  $? "+ dk3bm_get %lu %lu", (unsigned long)x, (unsigned long)y
  if (b) {
    if ((x < b->columns) && (y < b->rows)) {
      if (b->columns < b->rows) {
        pu = (b->data)[x];
	byteno = y / 8;
	bitno  = y % 8;
      } else {
        pu = (b->data)[y];
	byteno = x / 8;
	bitno  = x % 8;
      }
      if((pu[byteno]) & (dk3bf_bits_in_byte[bitno])) {
        back = 1;
      }
    }
  }
  $? "- dk3bm_get %d", back
  return back;
}



void
dk3bm_expand(dk3_bm_t *b)
{
  int		f_cache_fr	=	1;	/* Flag: Cache friendly */
  int		f_change_found	=	0;	/* Flag: Change found */
  size_t	i		=	0;	/* Source node number */
  size_t	j		=	0;	/* Destination node number */
  size_t	k		=	0;	/* Intermediate node */
  size_t	mxs		=	0;	/* Matrix size */
  int		ec		=	0;	/* Math error code */
  $? "+ dk3bm_expand"
  if (b) {					$? ". b ok"
    if (b->columns == b->rows) {		$? ". square"
      if (b->cachesize) {
        mxs = dk3mem_mul_size_t(b->rows, b->columns, &ec);
	if (mxs % 8) { mxs = mxs / 8 + 1; } else { mxs = mxs / 8; }
	if (0 == ec) { if (mxs <= b->cachesize) { f_cache_fr = 0; } }
      } else {
        f_cache_fr = 0;
      }
      if (f_cache_fr) {				$? ". cache friendly"
        do {
	  f_change_found = 0;
	  for (j = 0; j < b->rows; j++) {
	    for (k = 0; k < b->columns; k++) {
	      for (i = 0; i < b->columns; i++) {
	        if (!(dk3bm_get(b, i, j))) {
		  if (dk3bm_get(b, k, j)) {
		    if (dk3bm_get(b, i, k)) {
		      dk3bm_set(b, i, j, 1);
		      f_change_found = 1;
		    }
		  }
		}
	      }
	    }
	  }
	} while(f_change_found);
      } else {					$? ". traditional"
        do {
	  f_change_found = 0;
	  for (i = 0; i < b->columns; i++) {
	    for (j = 0; j < b->rows; j++) {
	      if (!(dk3bm_get(b, i, j))) {
	        for (k = 0; k < b->columns; k++) {
		  if (dk3bm_get(b, i, k)) {
		    if (dk3bm_get(b, k, j)) {
		      dk3bm_set(b, i, j, 1);
		      f_change_found = 1;
		    }
		  }
		}
	      }
	    }
	  }
	} while(f_change_found);
      }
    } else {					$? "! not square"
      if (b->app) {
        /* ERROR: Matrix must be a square! */
	dk3app_log_i1(b->app, DK3_LL_ERROR, 201);
      }
    }
  } $? "- dk3bm_expand"			
}


#endif

/* vim: set ai sw=2 : */