/* src/toolbox/bitvector.c - bitvector implementation

   Copyright (C) 2005, 2006
   CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
   Copyright (C) 2008 Theobroma Systems Ltd.

   This file is part of CACAO.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2, or (at
   your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.

*/


#include "config.h"

#include "mm/memory.hpp"
#include "toolbox/bitvector.h"


/******************************************************************************

Bitvector Implementation

******************************************************************************/

#ifdef BV_DEBUG_CHECK

  /* Number of ints needed for size bits */

# define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1)\
							/ sizeof(int) + 1)

  /* Get index in bitvector */

# define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) + 1)

  /* Get bit index inside int */

# define BV_BIT_INDEX(bit, index) ( (bit) - (index - 1) * sizeof(int) * 8 );

#else

  /* Number of ints needed for size bits */

# define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1) / sizeof(int))

  /* Get index in bitvector */

# define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) )

  /* Get bit index inside int */

# define BV_BIT_INDEX(bit, index) ( (bit) - (index) * sizeof(int) * 8 );

#endif

/************************************************************************
bv_to_string

Transforms the bitvector bv to a string of 1's and 0's.

IN: bitvector bv      bitvector created with bv_new()
    int       size    size of bitvector bv 

IN/OUT:   char      *string allocated buffer, at least size + 1 elements

RETURN:pointer to string
******************************************************************************/
char *bv_to_string(bitvector bv, char *string, int size) {
	int i;

	_BV_ASSERT(bv[0] == size);

	for(i = 0; i < size; i++) 
		if (bv_get_bit(bv, i))
			string[i]='1';
		else
			string[i]='0';

	string[i]=0;
	return string;
}

/******************************************************************************
bv_new

Creates a new bitvector and initializes all bits to 0.

IN: int       size    size of bitvector bv 

RETURN: bitvector

*******************************************************************************/
bitvector bv_new(int size) {
	int i,n;
	int *bv;

	/* Number of ints needed for size bits */
    /* n = (((size+7)/8) + sizeof(int) - 1)/sizeof(int);  */
	n = BV_NUM_INTS(size);

	bv = DumpMemory_allocate(sizeof(int) * n);

	for(i = 0; i < n; i++) bv[i] = 0;
   
#ifdef BV_DEBUG_CHECK
	bv[0] = size;
#endif

	return bv;
}

/******************************************************************************
bv_get_bit

Checks if a specific bit of the bitvector is set.

IN:   bitvector bv
      int       bit    Index of bit to check (0..size( 

RETURN:  bool      true if bit is set otherwise false
*******************************************************************************/
bool bv_get_bit(bitvector bv, int bit) {
	int i, n;

	_BV_ASSERT(bit >= 0);

	i = BV_INT_INDEX(bit);
	n = BV_BIT_INDEX(bit, i);

	_BV_ASSERT(i < (BV_NUM_INTS(bv[0])));
	return (bv[i] & (1<<n));
}

/******************************************************************************
bv_set_bit

Sets a specific bit of the bitvector

IN:   bitvector bv
      int       bit    Index of bit to set (0..size( 
*******************************************************************************/
void bv_set_bit(bitvector bv, int bit) {
	int i, n;

	_BV_ASSERT(bit >= 0);

	i = BV_INT_INDEX(bit);
	n = BV_BIT_INDEX(bit, i);

	_BV_ASSERT(i < BV_NUM_INTS(bv[0]));

	bv[i] |= 1<<n;
}

/******************************************************************************
bv_reset_bit

Resets a specific bit of the bitvector

IN:   bitvector bv
      int       bit    Index of bit to reset (0..size( 
*******************************************************************************/
void bv_reset_bit(bitvector bv, int bit) {
	int i, n;

	_BV_ASSERT(bit >= 0);

	i = BV_INT_INDEX(bit);
	n = BV_BIT_INDEX(bit, i);

	_BV_ASSERT(i < BV_NUM_INTS(bv[0]));

	bv[i] &= ~(1<<n);
}

/******************************************************************************
bv_reset

Resets all bits of the bitvector

IN:   bitvector bv
      int       size    Size of the bitvector
*******************************************************************************/
void bv_reset(bitvector bv, int size) {
	int i,n;

	_BV_ASSERT(bv[0] == size);

	n = BV_NUM_INTS(size);

#ifdef BV_DEBUG_CHECK
	for(i = 1; i < n; i++) 
#else
	for(i = 0; i < n; i++) 
#endif
		bv[i] = 0;
}

/******************************************************************************
bv_is_empty

Checks if no bits of the bitvector are set == bitvector is "empty"

IN:   bitvector bv
      int       size    Size of the bitvector

RETURN: bool  return true if bv is empty, false otherwise
*******************************************************************************/
bool bv_is_empty(bitvector bv, int size) {
	int i,n;
	bool empty;

	_BV_ASSERT(bv[0] == size);

	n = BV_NUM_INTS(size);

	empty = true;
#ifdef BV_DEBUG_CHECK
	for(i = 1; (i < n) && empty; i++) 
#else
	for(i = 0; (i < n) && empty; i++) 
#endif
		empty = empty && (bv[i] == 0);
	return empty;
}

/******************************************************************************
bv_copy

Copyes bitvector src to dst

IN:   bitvector dst     bitvector created with bv_new
      bitvector src     bitvector created with bv_new
      int       size    Size of the bitvector
*******************************************************************************/
void bv_copy(bitvector dst, bitvector src, int size) {
	int i,n;
	/* copy the whole bitvector    */
	_BV_ASSERT(dst[0] == size);
	_BV_ASSERT(src[0] == size);
	n = BV_NUM_INTS(size);

#ifdef BV_DEBUG_CHECK
	for(i = 1; i < n; i++) 
#else
	for(i = 0; i < n; i++) 
#endif
		dst[i] = src[i];
}

/******************************************************************************
bv_equal

Compares two  bitvectors

IN:   bitvector s1      bitvector created with bv_new
      bitvector s2      bitvector created with bv_new
      int       size    Size of the bitvector

RETURN: bool    true if s1==s1, false otherwise
*******************************************************************************/
bool bv_equal(bitvector s1, bitvector s2, int size) {
	int i,n;
	int mask;
	bool equal = true;
	/* copy the whole bitvector    */
	_BV_ASSERT(s1[0] == size);
	_BV_ASSERT(s2[0] == size);

	if (size == 0)
		return true;

	n = BV_NUM_INTS(size);

#ifdef BV_DEBUG_CHECK
	for(i = 1; equal && (i < n-1); i++) 
#else
	for(i = 0; equal && (i < n-1); i++) 
#endif
		equal = (s1[i] == s2[i]);

	/* Last compare maybe has to be masked! */

	i = BV_INT_INDEX(size - 1);
	n = BV_BIT_INDEX(size - 1, i);

	_BV_ASSERT(i < BV_NUM_INTS(s1[0]));
	_BV_ASSERT(i < BV_NUM_INTS(s2[0]));

	if (n == (sizeof(int) * 8 - 1)) {
		/* full mask */
		mask = -1;
	} else {
		mask = (1<<(n+1)) - 1;
	}
	
	equal = equal && ( (s1[i]&mask) == (s2[i]&mask));

	return equal;
}

/******************************************************************************
bv_minus

d = s1 \ s2. ( set minus operator )

IN:    bitvector s1      bitvector created with bv_new
       bitvector s2      bitvector created with bv_new
       int       size    Size of the bitvector

IN/OUT:bitvector d       bitvector created with bv_new

*******************************************************************************/
void bv_minus(bitvector d, bitvector s1, bitvector s2, int size) {
	int i,n;
    /* d = s1 - s2     */
	_BV_ASSERT(d[0] == size);
	_BV_ASSERT(s1[0] == size);
	_BV_ASSERT(s2[0] == size);
	n = BV_NUM_INTS(size);
#ifdef BV_DEBUG_CHECK
	for(i = 1; i < n; i++) 
#else
	for(i = 0; i < n; i++) 
#endif
		d[i] = s1[i] & (~s2[i]);
}

/******************************************************************************
bv_minus

d = s1 "union" s2. ( set union operator )

IN:    bitvector s1      bitvector created with bv_new
       bitvector s2      bitvector created with bv_new
       int       size    Size of the bitvector

IN/OUT:bitvector d       bitvector created with bv_new

*******************************************************************************/
void bv_union(bitvector d, bitvector s1, bitvector s2, int size) {
	int i,n;
    /* d = s1 union s2 */
	_BV_ASSERT(d[0] == size);
	_BV_ASSERT(s1[0] == size);
	_BV_ASSERT(s2[0] == size);
	n = BV_NUM_INTS(size);
#ifdef BV_DEBUG_CHECK
	for(i = 1; i < n; i++) 
#else
	for(i = 0; i < n; i++) 
#endif
		d[i] = s1[i] | s2[i];
}

/*
 * These are local overrides for various environment variables in Emacs.
 * Please do not remove this and leave it at the end of the file, where
 * Emacs will automagically detect them.
 * ---------------------------------------------------------------------
 * Local variables:
 * mode: c
 * indent-tabs-mode: t
 * c-basic-offset: 4
 * tab-width: 4
 * End:
 */