X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=src%2FSDCCbitv.c;h=987d5bef26575bbca758de62655e4f927bff7870;hb=eb7ad7a2f5c4bab308987f2de91ab37392e8ad06;hp=78b8f287a5fe391a4ae05808c1c2baad8215dd69;hpb=f6224daca530284743e68a8234854416234a6155;p=fw%2Fsdcc

diff --git a/src/SDCCbitv.c b/src/SDCCbitv.c
index 78b8f287..987d5bef 100644
--- a/src/SDCCbitv.c
+++ b/src/SDCCbitv.c
@@ -31,325 +31,443 @@ int bitVectDefault = 1024;
 /* genernal note about a bitvectors:
    bit vectors are stored from left to right i.e.
    bit position 0 is the MS bit of the first byte
-   this also means that bit positions must start from 0*/
+   this also means that bit positions must start from 0 */
 /*-----------------------------------------------------------------*/
 /* newBitVect - returns a new bitvector of size                    */
 /*-----------------------------------------------------------------*/
-bitVect *newBitVect (int size)
+bitVect *
+newBitVect (int size)
 {
-    bitVect *bvp;
-    int byteSize ;
+  bitVect *bvp;
+  int byteSize;
 
-    bvp = Safe_calloc(1,sizeof (bitVect));
+  bvp = Safe_calloc (1, sizeof (bitVect));
 
-    bvp->size = size;
-    bvp->bSize = byteSize = ( size / 8) + 1 ;
-    bvp->vect = Safe_calloc(1,byteSize);
-    return bvp;
+  bvp->size = size;
+  bvp->bSize = byteSize = (size / 8) + 1;
+  bvp->vect = Safe_calloc (1, byteSize);
+  return bvp;
 }
 
 /*-----------------------------------------------------------------*/
-/* bitVectResize - changes the size of a bit vector                */
+/* freeBitVect - frees the memory used by the bitVector            */
 /*-----------------------------------------------------------------*/
-bitVect *bitVectResize (bitVect *bvp, int size)
+void
+freeBitVect (bitVect * bvp)
 {
-    int bSize = ( size / 8) + 1  ;
+  if (!bvp)
+    return;
 
-    if (!bvp)
-  return newBitVect (size);
+  Safe_free (bvp->vect);
+  Safe_free (bvp);
+}
 
-    /* if we already have enough space */
-    if (bvp->bSize >= bSize ) {
-  if (size > bvp->size)
-      bvp->size = size ;
-  return bvp;
+/*-----------------------------------------------------------------*/
+/* bitVectResize - changes the size of a bit vector                */
+/*-----------------------------------------------------------------*/
+bitVect *
+bitVectResize (bitVect * bvp, int size)
+{
+  int bSize = (size / 8) + 1;
+
+  if (!bvp)
+    return newBitVect (size);
+
+  /* if we already have enough space */
+  if (bvp->bSize >= bSize)
+    {
+      if (size > bvp->size)
+	bvp->size = size;
+      return bvp;
     }
 
-    bvp->vect = Clear_realloc(bvp->vect, bvp -> bSize, bSize);
-    bvp->size = size;
-    bvp->bSize= bSize;
+  bvp->vect = Clear_realloc (bvp->vect, bvp->bSize, bSize);
+  bvp->size = size;
+  bvp->bSize = bSize;
 
-    return bvp;
+  return bvp;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectSetBit - sets a given bit in the bit vector              */
 /*-----------------------------------------------------------------*/
-bitVect *bitVectSetBit (bitVect *bvp, int pos)
+bitVect *
+bitVectSetBit (bitVect * bvp, int pos)
 {
-    int byteSize;
-    int offset ;
+  int byteSize;
+  int offset;
 
-    /* if set is null then allocate it */
-    if (!bvp)
-  bvp = newBitVect(bitVectDefault) ; /* allocate for twice the size */
+  /* if set is null then allocate it */
+  if (!bvp)
+    bvp = newBitVect (bitVectDefault);	/* allocate for twice the size */
 
-    if (bvp->size <= pos )
-  bvp = bitVectResize (bvp,pos+2); /* conservatively resize */
+  if (bvp->size <= pos)
+    bvp = bitVectResize (bvp, pos + 2);		/* conservatively resize */
 
-    byteSize = pos / 8 ;
-    offset = pos % 8;
-    bvp->vect[byteSize] |= (((unsigned char)1) <<
-          (7 - offset));
-    return bvp;
+  byteSize = pos / 8;
+  offset = pos % 8;
+  bvp->vect[byteSize] |= (((unsigned char) 1) <<
+			  (7 - offset));
+  return bvp;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectUnSetBit - unsets the value of a bit in a bitvector      */
 /*-----------------------------------------------------------------*/
-void bitVectUnSetBit (bitVect *bvp, int pos)
+void 
+bitVectUnSetBit (bitVect * bvp, int pos)
 {
-    int byteSize ;
-    int offset ;
+  int byteSize;
+  int offset;
 
-    if (! bvp)
-  return ;
+  if (!bvp)
+    return;
 
-    byteSize = pos /8;
-    if (bvp->bSize <= byteSize)
-  return ;
+  byteSize = pos / 8;
+  if (bvp->bSize <= byteSize)
+    return;
 
-    offset = pos % 8 ;
+  offset = pos % 8;
 
-    bvp->vect[byteSize] &= ~ (((unsigned char)1) <<
-            (7 - offset));
+  bvp->vect[byteSize] &= ~(((unsigned char) 1) <<
+			   (7 - offset));
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectBitValue - returns value value at bit position           */
 /*-----------------------------------------------------------------*/
-int bitVectBitValue (bitVect *bvp, int pos)
+int 
+bitVectBitValue (bitVect * bvp, int pos)
 {
-    int byteSize;
-    int offset ;
+  int byteSize;
+  int offset;
 
-    if (! bvp)
-  return 0;
+  if (!bvp)
+    return 0;
 
-    byteSize = pos /8;
+  byteSize = pos / 8;
 
-    if ( bvp->bSize <= byteSize )
-  return 0;
+  if (bvp->bSize <= byteSize)
+    return 0;
 
-    offset = pos % 8 ;
+  offset = pos % 8;
 
-    return ((bvp->vect[byteSize] >> (7-offset)) & ((unsigned char)1) );
+  return ((bvp->vect[byteSize] >> (7 - offset)) & ((unsigned char) 1));
 
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectUnion - unions two bitvectors                            */
 /*-----------------------------------------------------------------*/
-bitVect *bitVectUnion ( bitVect *bvp1, bitVect *bvp2)
+bitVect *
+bitVectUnion (bitVect * bvp1, bitVect * bvp2)
 {
-    int i;
-    bitVect *newBvp;
-
-    /* if both null */
-    if (!bvp1 && !bvp2)
-  return NULL ;
-
-    /* if one of them null then return the other */
-    if (! bvp1 && bvp2 )
-  return bitVectCopy (bvp2);
-
-    if ( bvp1 && ! bvp2 )
-  return bitVectCopy (bvp1);
-
-    /* if they are not the same size */
-    /* make them the same size */
-    if (bvp1->bSize < bvp2->bSize)
-  bvp1 = bitVectResize (bvp1,bvp2->size);
-    else
-  if (bvp2->bSize < bvp1->bSize)
-      bvp2 = bitVectResize (bvp2,bvp1->size);
-
-    newBvp = newBitVect(bvp1->size);
+  int i;
+  bitVect *newBvp;
+  unsigned int *pn, *p1, *p2;
+  int nbits;
+
+  /* if both null */
+  if (!bvp1 && !bvp2)
+    return NULL;
+
+  /* if one of them null then return the other */
+  if (!bvp1 && bvp2)
+    return bitVectCopy (bvp2);
+
+  if (bvp1 && !bvp2)
+    return bitVectCopy (bvp1);
+
+  /* if they are not the same size */
+  /* make them the same size */
+  if (bvp1->bSize < bvp2->bSize)
+    bvp1 = bitVectResize (bvp1, bvp2->size);
+  else if (bvp2->bSize < bvp1->bSize)
+    bvp2 = bitVectResize (bvp2, bvp1->size);
+
+  newBvp = newBitVect (bvp1->size);
+  nbits = bvp1->bSize;
+  i = 0;
+
+  pn = (unsigned int *)newBvp->vect; 
+  p1 = (unsigned int *)bvp1->vect;
+  p2 = (unsigned int *)bvp2->vect;
+
+  while ((nbits - i) >= sizeof(*pn))
+    {
+      *pn++ = *p1++ | *p2++;
+      i += sizeof(*pn);
+    }
 
-    for ( i = 0 ; i < bvp1->bSize ;i++)
-  newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
+  for (; i < nbits; i++)
+    newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
 
 
-    return newBvp;
+  return newBvp;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectIntersect - intersect  two bitvectors                    */
 /*-----------------------------------------------------------------*/
-bitVect *bitVectIntersect ( bitVect *bvp1, bitVect *bvp2)
+bitVect *
+bitVectIntersect (bitVect * bvp1, bitVect * bvp2)
 {
-    int i;
-    bitVect *newBvp;
-
-    if (! bvp2 || ! bvp1 )
-  return NULL ;
-
-    /* if they are not the same size */
-    /* make them the same size */
-    if (bvp1->bSize < bvp2->bSize)
-  bvp1 = bitVectResize (bvp1,bvp2->bSize);
-    else
-  if (bvp2->size < bvp1->size)
-      bvp2 = bitVectResize (bvp2,bvp1->size);
-
-    newBvp = newBitVect(bvp1->size);
+  int i;
+  bitVect *newBvp;
+  unsigned int *pn, *p1, *p2;
+  int nbits;
+
+  if (!bvp2 || !bvp1)
+    return NULL;
+
+  /* if they are not the same size */
+  /* make them the same size */
+  if (bvp1->bSize < bvp2->bSize)
+    bvp1 = bitVectResize (bvp1, bvp2->bSize);
+  else if (bvp2->size < bvp1->size)
+    bvp2 = bitVectResize (bvp2, bvp1->size);
+
+  newBvp = newBitVect (bvp1->size);
+  nbits = bvp1->bSize;
+  i = 0;
+
+  pn = (unsigned int *)newBvp->vect; 
+  p1 = (unsigned int *)bvp1->vect;
+  p2 = (unsigned int *)bvp2->vect;
+
+  while ((nbits - i) >= sizeof(*pn))
+    {
+      *pn++ = *p1++ & *p2++;
+      i += sizeof(*pn);
+    }
 
-    for ( i = 0 ; i < bvp1->bSize ;i++)
-  newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
+  for (; i < nbits; i++)
+    newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
 
-    return newBvp;
+  return newBvp;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectBitsInCommon - special case of intersection determines   */
 /*                       if the vectors have any common bits set   */
 /*-----------------------------------------------------------------*/
-int bitVectBitsInCommon ( bitVect *bvp1, bitVect *bvp2 )
+int 
+bitVectBitsInCommon (bitVect * bvp1, bitVect * bvp2)
 {
-    int i ;
+  int i;
+  int nbits;
+  unsigned int *p1, *p2;
 
-    if ( ! bvp1 || ! bvp2 )
-  return 0;
+  if (!bvp1 || !bvp2)
+    return 0;
+
+  nbits = min (bvp1->bSize, bvp2->bSize);
+  i = 0;
+
+  p1 = (unsigned int *)bvp1->vect;
+  p2 = (unsigned int *)bvp2->vect;
+
+  while ((nbits-i) >= sizeof(*p1))
+    {
+      if (*p1 & *p2)
+        return 1;
+      p1++; p2++;
+      i += sizeof(*p1);
+    }
 
-    for ( i = 0 ; i < min(bvp1->bSize,bvp2->bSize) ; i ++ )
-  if ( bvp1->vect[i] & bvp2->vect[i] )
+  for (; i < nbits; i++)
+    if (bvp1->vect[i] & bvp2->vect[i])
       return 1;
 
-    return 0;
+  return 0;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectCplAnd - complement the second & and it with the first   */
 /*-----------------------------------------------------------------*/
-bitVect *bitVectCplAnd ( bitVect *bvp1, bitVect *bvp2)
+bitVect *
+bitVectCplAnd (bitVect * bvp1, bitVect * bvp2)
 {
-    int i;
+  int i;
+  unsigned int *p1, *p2;
+  int nbits;
 
-    if ( ! bvp2 )
-  return bvp1 ;
+  if (!bvp2)
+    return bvp1;
 
-    if ( ! bvp1 )
-  return bvp1 ;
+  if (!bvp1)
+    return bvp1;
 
-    /* if they are not the same size */
-    /* make them the same size */
-    if (bvp1->bSize < bvp2->bSize)
-  bvp1 = bitVectResize (bvp1,bvp2->bSize);
-    else
-  if (bvp2->size < bvp1->size)
-      bvp2 = bitVectResize (bvp2,bvp1->size);
+  /* if they are not the same size */
+  /* make them the same size */
+  if (bvp1->bSize < bvp2->bSize)
+    bvp1 = bitVectResize (bvp1, bvp2->bSize);
+  else if (bvp2->size < bvp1->size)
+    bvp2 = bitVectResize (bvp2, bvp1->size);
 
-    for ( i = 0 ; i < bvp1->bSize ;i++)
-  bvp1->vect[i] = bvp1->vect[i] & (~ bvp2->vect[i]);
+  nbits = bvp1->bSize;
+  i = 0;
 
-    return bvp1;
+  p1 = (unsigned int *)bvp1->vect;
+  p2 = (unsigned int *)bvp2->vect;
+
+  while ((nbits - i) >= sizeof(*p1))
+    {
+      *p1 = *p1 & (~*p2);
+      p2++; p1++;
+      i += sizeof(*p1);
+    }
+
+  for (; i < nbits; i++)
+    bvp1->vect[i] = bvp1->vect[i] & (~bvp2->vect[i]);
+
+  return bvp1;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectIsZero - bit vector has all bits turned off              */
 /*-----------------------------------------------------------------*/
-int bitVectIsZero (bitVect *bvp)
+int 
+bitVectIsZero (bitVect * bvp)
 {
-    int i ;
+  int i;
 
-    if (!bvp)
-  return 1;
+  if (!bvp)
+    return 1;
 
-    for ( i = 0 ; i < bvp->bSize ; i++ )
-  if (bvp->vect[i] != 0)
+  for (i = 0; i < bvp->bSize; i++)
+    if (bvp->vect[i] != 0)
       return 0;
 
-    return 1;
+  return 1;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectsEqual - returns 1 if the two bit vectors are equal      */
 /*-----------------------------------------------------------------*/
-int bitVectEqual ( bitVect *bvp1, bitVect *bvp2)
+int 
+bitVectEqual (bitVect * bvp1, bitVect * bvp2)
 {
-    int i ;
+  int i;
 
-    if ( !bvp1 || !bvp1)
-  return 0;
+  if (!bvp1 || !bvp1)
+    return 0;
 
-    if (bvp1 == bvp2)
-  return 1;
+  if (bvp1 == bvp2)
+    return 1;
 
-    if (bvp1->bSize != bvp2->bSize)
-  return 0;
+  if (bvp1->bSize != bvp2->bSize)
+    return 0;
 
-    for (i = 0 ; i < bvp1->bSize ; i++ )
-  if ( bvp1->vect[i] != bvp2->vect[i] )
+  for (i = 0; i < bvp1->bSize; i++)
+    if (bvp1->vect[i] != bvp2->vect[i])
       return 0;
 
-    return 1;
+  return 1;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectCopy - creates a bitvector from another bit Vector       */
 /*-----------------------------------------------------------------*/
-bitVect *bitVectCopy (bitVect *bvp)
+bitVect *
+bitVectCopy (bitVect * bvp)
 {
-    bitVect *newBvp;
-    int i;
+  bitVect *newBvp;
+  int i;
 
-    if (!bvp)
-  return NULL;
+  if (!bvp)
+    return NULL;
 
-    newBvp = newBitVect(bvp->size);
-    for ( i = 0 ; i < bvp->bSize; i++ )
-  newBvp->vect[i] = bvp->vect[i];
+  newBvp = newBitVect (bvp->size);
+  for (i = 0; i < bvp->bSize; i++)
+    newBvp->vect[i] = bvp->vect[i];
 
-    return newBvp;
+  return newBvp;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectnBitsOn - returns the number of bits that are on         */
 /*-----------------------------------------------------------------*/
-int bitVectnBitsOn (bitVect *bvp)
+int 
+bitVectnBitsOn (bitVect * bvp)
 {
-    int i, j, k;
-    unsigned char byte;
-    int count = 0 ;
+  int i, j;
+  unsigned char byte;
+  int count = 0;
+  unsigned int *p1;
 
-    if (!bvp)
-  return 0;
+  /* The bit vector is highest to lowest.  Interesting. */
+  unsigned int mask[] = {
+    0, 128, 128+64, 128+64+32, 128+64+32+16,
+    128+64+32+16+8, 128+64+32+16+8+4, 128+64+32+16+8+4+2
+  };
+
+  if (!bvp)
+    return 0;
 
-   /* rip through most of the data in byte sized chunks */
-   j = (bvp->size)/8;
-   for (i = 0 ; i < j; i++) {
-       byte = bvp->vect[i];
-       for (k=0; k<8; k++) { count += byte&1; byte = byte>>1; }
-   }
+  /* j is the number of bytes in the bitvect */
+  j = (bvp->size+7) / 8;
 
-   /* finish up the last fractional byte, if any */
-   for (i = j*8 ; i < bvp->size; i++)
-       count += bitVectBitValue(bvp,i);
+  /* Fix up the highest bits in the top byte so that we can iterate over
+     all of them. */
+  if (bvp->size%8 != 0)
+    {
+      bvp->vect[j-1] &= mask[bvp->size&7];
+    }
 
-   return count;
+  /* Take care of things in machine word chunks if possible.  As we
+     are only counting bits it does not matter which order they are
+     counted in.
+  */
+  i = 0;
+  p1 = (unsigned int *)bvp->vect;
+
+  while ((j-i) >= sizeof(*p1))
+    {
+      unsigned int word = *p1++;
+      while (word)
+        {
+          count++;
+          word &= word-1;
+        }
+      i += sizeof(*p1);
+    }
 
+  /* Take care of the rest of the bitvect. */
+  for (; i < j; i++)
+    {
+      byte = bvp->vect[i];
+      while (byte)
+        {
+          count++;
+          byte &= byte-1;
+        }
+    }
+  return count;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectFirstBit - returns the key for the first bit that is on  */
 /*-----------------------------------------------------------------*/
-int bitVectFirstBit (bitVect *bvp)
+int 
+bitVectFirstBit (bitVect * bvp)
 {
-    int i;
+  int i;
 
-    if (!bvp)
-  return -1;
-    for (i = 0; i < bvp->size ; i++ )
-  if (bitVectBitValue(bvp,i))
+  if (!bvp)
+    return -1;
+  for (i = 0; i < bvp->size; i++)
+    if (bitVectBitValue (bvp, i))
       return i;
 
-    return -1;
+  return -1;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectDebugOn - prints bits that are on                        */
 /*-----------------------------------------------------------------*/
-void bitVectDebugOn (bitVect *bvp, FILE *of)
+void 
+bitVectDebugOn (bitVect * bvp, FILE * of)
 {
   int i;
 
@@ -358,11 +476,12 @@ void bitVectDebugOn (bitVect *bvp, FILE *of)
   if (!bvp)
     return;
 
-  fprintf(of,"bitvector Size = %d bSize = %d\n",bvp->size,bvp->bSize);
-  fprintf(of,"Bits on { ");
-  for (i = 0 ; i < bvp->size ; i++) {
-    if (bitVectBitValue(bvp,i))
-      fprintf(of,"(%d) ",i);
-  }
-  fprintf(of,"}\n");
+  fprintf (of, "bitvector Size = %d bSize = %d\n", bvp->size, bvp->bSize);
+  fprintf (of, "Bits on { ");
+  for (i = 0; i < bvp->size; i++)
+    {
+      if (bitVectBitValue (bvp, i))
+	fprintf (of, "(%d) ", i);
+    }
+  fprintf (of, "}\n");
 }