#include <stdlib.h>
#include "util.h"
#include "bv.h"
#include <stdio.h>

unsigned int pm[32] =
    {0x00000001, 0x00000002, 0x00000004, 0x00000008,
     0x00000010, 0x00000020, 0x00000040, 0x00000080,
     0x00000100, 0x00000200, 0x00000400, 0x00000800,
     0x00001000, 0x00002000, 0x00004000, 0x00008000,
     0x00010000, 0x00020000, 0x00040000, 0x00080000,
     0x00100000, 0x00200000, 0x00400000, 0x00800000,
     0x01000000, 0x02000000, 0x04000000, 0x08000000,
     0x10000000, 0x20000000, 0x40000000, 0x80000000};
    
unsigned int nm[32] =
    {0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7,
     0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F,
     0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF,
     0xFFFFEFFF, 0xFFFFDFFF, 0xFFFFBFFF, 0xFFFF7FFF,
     0xFFFEFFFF, 0xFFFDFFFF, 0xFFFBFFFF, 0xFFF7FFFF,
     0xFFEFFFFF, 0xFFDFFFFF, 0xFFBFFFFF, 0xFF7FFFFF,
     0xFEFFFFFF, 0xFDFFFFFF, 0xFBFFFFFF, 0xF7FFFFFF,
     0xEFFFFFFF, 0xDFFFFFFF, 0xBFFFFFFF, 0x7FFFFFFF};

unsigned short bv_size;
unsigned short bv_size_rem;

#define POOLSIZE 128
static struct bv_pool {
    struct bv_pool * lastpool;
    BV lotsa_bvs;
    unsigned short next;
    } * bv_cache = 0;

static VOID repool() {
    struct bv_pool * new_pool = (struct bv_pool *) MALLOC (sizeof (*new_pool));
    new_pool -> lastpool = bv_cache;
    new_pool -> next = 0;
    new_pool -> lotsa_bvs = (BV) MALLOC ((sizeof (UINT) * POOLSIZE)*bv_size);
    bv_cache = new_pool;
    }

BV bv_alloc() {
   if (bv_cache -> next == POOLSIZE) repool();
   return bv_cache -> lotsa_bvs +
		(bv_cache -> next++ * bv_size);
   };

VOID bv_init(size) UINT size; {
   bv_size = ITOY(size);
   bv_size_rem = bv_size & 7;
   repool();
   };

BV bv_new() {
   REGISTER BV bv;
   REGISTER UINT i;
   REGISTER UINT size = bv_size;
   bv = bv_alloc();
   for (i = 0; i < size; i++) bv[i] = 0;
   return bv;
   }

BV bv_copy(bv) REGISTER BV bv; {
   REGISTER BV bvnew;
   REGISTER UINT i;
   REGISTER UINT size = bv_size;
   bvnew = bv_alloc();
   for (i = 0; i < size; i++) bvnew[i] = bv[i];
   return bvnew;
   }


UINT number_bits_set(bv) REGISTER BV bv; {
  REGISTER UINT i;
  REGISTER UINT size = bv_size;
  REGISTER UINT count = 0;
  REGISTER UINT b;
  for (i = 0; i < size; i++) {
    b = bv[i];
    while (b != 0)
      {
	if ((b & 1) == 1) count++;
	b = b >> 1;
      }
  }
  return count;
}

BV bv_assign(bv,bvnew) BV bv,bvnew; {
   REGISTER UINT size = bv_size;
   REGISTER UINT i;
   for (i = 0; i < size; i++) bvnew[i] = bv[i];
   return bvnew;
   }


BV bv_and(bv1,bv2) REGISTER BV bv1; REGISTER BV bv2; {
   REGISTER BV bvnew;
   REGISTER UINT i;
   UINT size = bv_size;
   bvnew = bv_alloc();

   for (i = 0; i < size; i++) {
      bvnew[i] = bv1[i] & bv2[i];
      }
   return bvnew;
   }

int bv_intersects(bv1,bv2) REGISTER BV bv1;
			    REGISTER BV bv2; {
/* REGISTER UINT size = bv_size;
   REGISTER UINT i;

   for (i = 0; i < size; i++) {
      if ( (bv1[i] & bv2[i]) != 0) return -1;
      }
*/
   REGISTER BV bv_end = bv_size + bv1;

   while (bv1 < bv_end) {
      if (*bv1++ & *bv2++) return -1;
      }
   return 0;
   }

BV bv_andto(bv1,bv2, bvnew) REGISTER BV bv1;
			    REGISTER BV bv2;
			    REGISTER BV bvnew; {
/* REGISTER UINT size = bv_size;
   REGISTER UINT i;

   for (i = 0; i < size; i++) {
      bvnew[i] = bv1[i] & bv2[i];
      }
*/
   REGISTER BV bv_end = bv_size + bv1;
   REGISTER BV bv_to = bvnew;
   
   switch(bv_size_rem) {
      case 0:
      while (bv1 < bv_end) {
         *bv_to++ = *bv1++ & *bv2++;
	 case 7:
         *bv_to++ = *bv1++ & *bv2++;
	 case 6:
         *bv_to++ = *bv1++ & *bv2++;
	 case 5:
         *bv_to++ = *bv1++ & *bv2++;
	 case 4:
         *bv_to++ = *bv1++ & *bv2++;
	 case 3:
         *bv_to++ = *bv1++ & *bv2++;
	 case 2:
         *bv_to++ = *bv1++ & *bv2++;
	 case 1:
         *bv_to++ = *bv1++ & *bv2++;
         }
      }
	 
   return bvnew;
   }

BV bv_orto(bv1,bv2, bvnew) REGISTER BV bv1;
			    REGISTER BV bv2;
			    REGISTER BV bvnew; {
   REGISTER UINT size = bv_size;
   REGISTER UINT i;

   for (i = 0; i < size; i++) {
      bvnew[i] = bv1[i] | bv2[i];
      }
   return bvnew;
   }

VOID bv_free(bv) BV bv; {
   return;
   }

int   bv_eq(bv1,bv2) REGISTER BV bv1; REGISTER BV bv2; {
/* UINT size = bv_size;
   REGISTER UINT i;
   for (i = 0; i < size; i++)
       if (bv1[i] != bv2[i]) return 0;
   return 1;
*/
   REGISTER BV bv_end = bv_size + bv1;
   switch(bv_size_rem) {
      case 0:
      while (bv1 < bv_end) {
         if (*bv1++ != *bv2++) goto return_zero;
         case 7:
         if (*bv1++ != *bv2++) goto return_zero;
         case 6:
         if (*bv1++ != *bv2++) goto return_zero;
         case 5:
         if (*bv1++ != *bv2++) goto return_zero;
         case 4:
         if (*bv1++ != *bv2++) goto return_zero;
         case 3:
         if (*bv1++ != *bv2++) goto return_zero;
         case 2:
         if (*bv1++ != *bv2++) goto return_zero;
         case 1:
         if (*bv1++ != *bv2++) goto return_zero;
         }
      }
   return 1;
return_zero:
   return 0;
   }

UINT bv_hash(bv) REGISTER BV bv; {
   REGISTER UINT h = 0;
/** REGISTER UINT i; **/
   REGISTER BV bv_end = bv + bv_size;
   
   switch(bv_size_rem) {
       case 0:
       while (bv < bv_end) {
          h = (h << 5) + (h >> 27) + *bv++;
          case 7:
          h = (h << 5) + (h >> 27) + *bv++;
          case 6:
          h = (h << 5) + (h >> 27) + *bv++;
          case 5:
          h = (h << 5) + (h >> 27) + *bv++;
          case 4:
          h = (h << 5) + (h >> 27) + *bv++;
          case 3:
          h = (h << 5) + (h >> 27) + *bv++;
          case 2:
          h = (h << 5) + (h >> 27) + *bv++;
          case 1:
          h = (h << 5) + (h >> 27) + *bv++;
          }
       }
   return h;

/**
   REGISTER UINT size = bv_size;
   for (i = 0; i < size; i++) {
       h = h * (h + i) + bv[i];
       }
   return h;
**/
   }

VOID bv_p(fd,bv) FILE * fd; BV bv; { 
    UINT size = YTOI(bv_size);
    UINT i;
    for (i = 0; i < size; i++) fprintf(fd, bv_in(bv, i) ? "1" : "0");
    }