/* #define TESTING */

/*      bitset.c        bitset definition and manipulation routines
 *
 *	version hx	v1.0 : initial release to CIS : 09-07-87 : (jrh)
 *
 *	author		Richard Hargrove
 *			Texas Instruments, Inc.
 *			P.O. Box 869305, m/s 8473
 *			Plano, TX 75086
 *			214/575-4128
 *
 *	CIS		74756,664
 *
 *	usenet		...{inhp4|cbosgd}!killer!richardh
 *				 	       \!warble!richardh
 */

#if defined(TESTING)
#include <stdio.h>
#define STATIC
#else
#define STATIC static
#endif TESTING

#include <alloc.h>
#include "bitset.h"

#define FALSE	0
#define TRUE	1

/* private bitset type */

typedef struct {
   unsigned size;		/* bitset size */
   unsigned char bits [1];	/* hook for the bitset */
} BITSET, *BITPTR;

/* binary operations with common algorithms */

#define UNION           0
#define INTERSECTION    1
#define EX_OR           2
#define DIFFERENCE      3

#define NUMCHARS(bitsize)	(((bitsize) >> 3) + ((bitsize) & 0x07 ? 1 : 0))

/* Package work vars used to avoid casting operation parameters on every use
 * and to get local bitset pointer refs off of the stack.
 */

STATIC BITPTR local1, local2;

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

bitset makebitset (unsigned size)
{
        /*      Create a bitset containing size bits. Return a pointer to the 
		bitset if successful, NULL otherwise.
         */

#ifdef TESTING
        printf ("Making a %d bit BITSET (%d bytes required)\n", 
		size, NUMCHARS(size));
#endif TESTING

	/* packet size is adjusted for hook byte */
        if ((local1 = (BITPTR) malloc (NUMCHARS(size) - 1 + sizeof(BITSET))) 
		!= (BITPTR) NULL) {
	  /* init the bitset */
          local1->size = size;
	  clear_set ((bitset) local1);
	}
        return ((bitset) local1);
}

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

BOOLEAN setbit (bitset set, unsigned bit, unsigned val)
{
        /*      Set bit# bit in set to the value of the least significant bit 
	 *	in val. Return TRUE if successful, FALSE otherwise.
         */

	BOOLEAN ret_val = FALSE;
         
        local1 = (BITPTR) set;
        if (bit < local1->size) {
          if ((val & 0x01) == 1) {			/* set the bit */
	    local1->bits [bit >> 3] |= (1 << (bit & 0x07));
          }
          else {					/* clear the bit */
            local1->bits [bit >> 3] &= (~(1 << (bit & 0x07)));
          }
	  ret_val = TRUE;
	}
        return (ret_val);
}

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

BOOLEAN testbit (bitset set, unsigned bit)
{
        /*      If bit# bit in set is 1 return TRUE else return FALSE.
         */

        local1 = (BITPTR) set;
        return ((bit < local1->size) &&
	  	(local1->bits [bit >> 3] & (1 << (bit & 0x07))));
}

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

void clear_set (bitset set)
{
        /*      Clear the bitset pointed to by set.
         */
         
        unsigned numchars;
        char *localbits;

	local1 = (BITPTR) set;
	localbits = local1->bits;
	numchars = NUMCHARS(local1->size);
        while (numchars--) {
          *localbits++ = '\0';
        }
}

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

void compl_set (bitset set)
{
        /*      Complement the bitset pointed to by set.
         */

        unsigned numchars;
        char *localbits;

	local1 = (BITPTR) set;
	localbits = local1->bits;
	numchars = NUMCHARS(local1->size);
        while (numchars--) {
          *localbits++ ^= 0xff;
        }
}

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

STATIC void binsetop (int op)
{
	char *localbits1 = local1->bits;
	char *localbits2 = local2->bits;
        unsigned numchars = (local1->size > local2->size) 
				? NUMCHARS(local2->size)
				: NUMCHARS(local1->size);
        while (numchars--) {
          switch (op) {
            case UNION:         *localbits1++ |= *localbits2++;
                                continue;
            case INTERSECTION:  *localbits1++ &= *localbits2++;
                                continue;
            case EX_OR:         *localbits1++ ^= *localbits2++;
                                continue;
            case DIFFERENCE:    *localbits1 &= (~(*localbits1 & *localbits2++));
                                localbits1++;
          }
        }
}

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

void union_set (bitset set1, bitset set2)
{
        /*      Transform the bitset pointed to by set1 into the union of
         *      the bitsets pointed to by set1 and set2.
         */

	local1 = (BITPTR) set1;
	local2 = (BITPTR) set2;
        binsetop (UNION);
}

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

void intrsct_set (bitset set1, bitset set2)
{
        /*      Transform the bitset pointed to by set1 into the intersection
         *      of the bitsets pointed to by set1 and set2.
         */

	local1 = (BITPTR) set1;
	local2 = (BITPTR) set2;
        binsetop (INTERSECTION);

}

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

void xor_set (bitset set1, bitset set2)
{
        /*      Transform the bitset pointed to by set1 into the exclusive-or
         *      of the bitsets pointed to by set1 and set2.
         */

	local1 = (BITPTR) set1;
	local2 = (BITPTR) set2;
	binsetop (EX_OR);
}

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

void diff_set (bitset set1, bitset set2)
{
        /*      Transform the bitset pointed to by set1 into the set
         *      difference of the bitsets pointed to by set1 and set2.
         */

	local1 = (BITPTR) set1;
	local2 = (BITPTR) set2;
        binsetop (DIFFERENCE);
}

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

BOOLEAN equal_sets (bitset set1, bitset set2)
{
        /*      If the bitsets pointed to by set1 and set2 are the same
         *      size and contain the same bit pattern then return TRUE
         *      else return FALSE
         */

        BOOLEAN areequal;

	local1 = (BITPTR) set1;
	local2 = (BITPTR) set2;

        if ((areequal = (local1->size == local2->size)) != FALSE) {
	  char *localbits1 = local1->bits;
	  char *localbits2 = local2->bits;
          unsigned numchars = NUMCHARS(local1->size);

          while (areequal && numchars--) {
            areequal = (*localbits1++ == *localbits2++);
          }
        }
        return (areequal);
}

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

BOOLEAN in_set (bitset set1, bitset set2)
{
        /*      If the bitset pointed to by set1 is a subset of the bitset
         *      pointed to by set2 then return TRUE else return FALSE.
         *
         *      This rotuine requires that the size of *set1 be less than
         *      or equal to the size of *set2 in order to return TRUE.
         */

        BOOLEAN isinset;

	local1 = (BITPTR) set1;
	local2 = (BITPTR) set2;

        if ((isinset = (local1->size <= local2->size)) != FALSE) {
	  char *localbits1 = local1->bits;
	  char *localbits2 = local2->bits;
          unsigned numchars = NUMCHARS(local1->size);

          while (isinset && numchars--) {
            isinset = ((*localbits1 & *localbits2++) == *localbits1);
            localbits1++;
          }
        }
        return (isinset);
}
#if defined(TESTING)

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

#define NUMBITS 21      /* vary these for different tests */

put_set (msg, set)
char *msg;
bitset set;
{
        int i;

        printf ("%s", msg);
        for (i = 0; i < NUMBITS; i++) {
          if (i % 4 == 0) putchar (' ');
          fputc (testbit (set, i) ? '1' : '0', stdout);
        }
}

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

main (void)
{
	/*	Test the bitset package
	 */
	
	bitset set, x, y, z;
	unsigned bitnum, val, i;
	char buf [16];

        puts ("Making a 32 bit wide bitset");
        if ((set = makebitset (32)) == (bitset) NULL) {
          puts ("Can't make the bitset");
	  exit (1);
        }

	/* test setbit and testbit */
        do {
	  /* Output the bitset */
	  for (i = 0; i <= 31; i++) {
	    fputc (testbit (set, i) ? '1' : '0', stdout);
	  }
	  fputc ('\n', stdout);
	  
	  fputs ("Which bit? ", stderr);
	  bitnum = atoi (fgets (buf, 16, stdin));
	  fputs ("val ([^0-1] quits)? ", stderr);
	  val = atoi (fgets (buf, 16, stdin));

	  printf ("bitnum == %d   val == %d\n", bitnum, val);

	  if (!setbit (set, bitnum, val)) {
	    printf ("Bit out of range\n");
	  }
	} while ((val >= 0) && (val <= 1));

	/* test the set operations */
	x = makebitset (NUMBITS);
	z = makebitset (NUMBITS);
	y = makebitset (NUMBITS);
	if ((x == (bitset) NULL) || (y == (bitset) NULL) || 
	    (z == (bitset) NULL)) {
	  printf ("Can't make the bitsets\n");
	  exit (1);
	}

	setbit (x, 3, 1);  setbit (x, 6, 1);    /* vary these for  */
	setbit (x, 10, 1); setbit (x, 11, 1);   /* different tests */
	setbit (x, 13, 1); setbit (x, 17, 1);
	setbit (x, 19, 1);

	setbit (y, 0, 1);  setbit (y, 4, 1);    /* vary these for  */
	setbit (y, 7, 1);  setbit (y, 8, 1);    /* different tests */
	setbit (y, 10, 1); setbit (y, 12, 1);
	setbit (y, 14, 1); setbit (y, 15, 1);
	setbit (y, 16, 1); setbit (y, 17, 1);
	setbit (y, 20, 1);

	put_set ("\nbitset x:", x);
	put_set ("\nbitset y:", y);
	put_set ("\nbitset z:", z);

	union_set (z, x);
	put_set ("\n\nz union x:", z);

	if (equal_sets (z, x))
	  printf ("\nz is equal to x");
	else
	  printf ("\nz is not equal to x");

	if (equal_sets (y, x))
	  printf ("\ny is equal to x");
	else
	  printf ("\ny is not equal to x");

	intrsct_set (z, y);
	put_set ("\nz intersection y:", z);

	clear_set (z);
	put_set ("\n\nz cleared:", z);

	compl_set (z);
	put_set ("\nz complement:", z);

	xor_set (z, x);
	put_set ("\nz xor x:", z);

	clear_set (z);
	setbit (z, 0, 1);
	setbit (z, 7, 1);
	setbit (z, 8, 1);
	setbit (z, 14, 1);
	setbit (z, 17, 1);
	put_set ("\n\nz is", z);
	if (in_set (z, y))
	  printf (" and is a subset of y");
	else
	  printf (" and is not a subset of y");

	if (in_set (x, y))
	  printf ("\nx is a subset of y");
	else
	  printf ("\nx is not a subset of y");

	if (in_set (y, y))
	  printf ("\ny is a subset of y");
	else
	  printf ("\ny is not a subset of y");

	compl_set (z);
	put_set ("\n\nz is", z);
	put_set ("\ny is", y);
	diff_set (z, y);
	put_set ("\nz diff y:", z);

	putchar ('\n');
	exit (0);
}
#endif TESTING