X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=src%2FSDCCbitv.c;h=987d5bef26575bbca758de62655e4f927bff7870;hb=80972b2e54c9b88f11c27b878874fd2a6a681391;hp=c5ec50daa9197442c87858dd47efe9e0c2f4ad78;hpb=aed2b39c46fcdfdd017adbf9e50c254efc5dea42;p=fw%2Fsdcc

diff --git a/src/SDCCbitv.c b/src/SDCCbitv.c
index c5ec50da..987d5bef 100644
--- a/src/SDCCbitv.c
+++ b/src/SDCCbitv.c
@@ -1,25 +1,25 @@
 /*-----------------------------------------------------------------
     SDCCbitv.c - contains support routines for bitvectors
-                
+
     Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
 
     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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-    
+
     In other words, you are welcome to use, share and improve this program.
     You are forbidden to forbid anyone else to use, share and improve
-    what you give them.   Help stamp out software-hoarding!  
+    what you give them.   Help stamp out software-hoarding!
 -------------------------------------------------------------------------*/
 
 #include "common.h"
@@ -29,340 +29,459 @@
 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*/
+   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 */
 /*-----------------------------------------------------------------*/
 /* 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(sizeof (bitVect));
+  bvp = Safe_calloc (1, sizeof (bitVect));
 
-    bvp->size = size;    
-    bvp->bSize = byteSize = ( size / 8) + 1 ;
-    bvp->vect = Safe_calloc(byteSize);
-    return bvp;
+  bvp->size = size;
+  bvp->bSize = byteSize = (size / 8) + 1;
+  bvp->vect = Safe_calloc (1, byteSize);
+  return bvp;
+}
+
+/*-----------------------------------------------------------------*/
+/* freeBitVect - frees the memory used by the bitVector            */
+/*-----------------------------------------------------------------*/
+void
+freeBitVect (bitVect * bvp)
+{
+  if (!bvp)
+    return;
+
+  Safe_free (bvp->vect);
+  Safe_free (bvp);
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectResize - changes the size of a bit vector                */
 /*-----------------------------------------------------------------*/
-bitVect *bitVectResize (bitVect *bvp, int size)
+bitVect *
+bitVectResize (bitVect * bvp, int size)
 {
-    int bSize = ( size / 8) + 1  ;
+  int bSize = (size / 8) + 1;
 
-    if (!bvp)
-	return newBitVect (size);
+  if (!bvp)
+    return newBitVect (size);
 
-    /* if we already have enough space */
-    if (bvp->bSize >= bSize ) {
-	if (size > bvp->size)
-	    bvp->size = size ;
-	return bvp;
+  /* 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 ;
-
-    /* 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 */
-    
-    byteSize = pos / 8 ;
-    offset = pos % 8;
-    bvp->vect[byteSize] |= (((unsigned char)1) << 
-			    (7 - offset));
-    return bvp;
+  int byteSize;
+  int offset;
+
+  /* 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 */
+
+  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;
+
+  offset = pos % 8;
 
-    if ( bvp->bSize <= byteSize )
-	return 0;
+  return ((bvp->vect[byteSize] >> (7 - offset)) & ((unsigned char) 1));
 
-    offset = pos % 8 ;
-  
-    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);
-       
-    for ( i = 0 ; i < bvp1->bSize ;i++)
-	newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
-   
-
-    return newBvp;
+  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 < nbits; i++)
+    newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
+
+
+  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 ;
-
-    if ( ! bvp1 || ! bvp2 )
-	return 0;
-    
-    for ( i = 0 ; i < min(bvp1->bSize,bvp2->bSize) ; i ++ ) 
-	if ( bvp1->vect[i] & bvp2->vect[i] )
-	    return 1;
+  int i;
+  int nbits;
+  unsigned int *p1, *p2;
 
+  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 < nbits; i++)
+    if (bvp1->vect[i] & bvp2->vect[i])
+      return 1;
+
+  return 0;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectCplAnd - complement the second & and it with the first   */
 /*-----------------------------------------------------------------*/
-bitVect *bitVectCplAnd ( bitVect *bvp1, bitVect *bvp2)
-{    
-    int i;    
+bitVect *
+bitVectCplAnd (bitVect * bvp1, bitVect * bvp2)
+{
+  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);       
+  nbits = bvp1->bSize;
+  i = 0;
 
-    for ( i = 0 ; i < bvp1->bSize ;i++)
-	bvp1->vect[i] = bvp1->vect[i] & (~ bvp2->vect[i]);
+  p1 = (unsigned int *)bvp1->vect;
+  p2 = (unsigned int *)bvp2->vect;
 
-    return bvp1;
+  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 ;
-
-    if (!bvp)
-	return 1;
-    
-    for ( i = 0 ; i < bvp->bSize ; i++ )
-	if (bvp->vect[i] != 0)
-	    return 0;
+  int i;
 
+  if (!bvp)
     return 1;
+
+  for (i = 0; i < bvp->bSize; i++)
+    if (bvp->vect[i] != 0)
+      return 0;
+
+  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] )
-	    return 0;
-    
-    return 1;
+  for (i = 0; i < bvp1->bSize; i++)
+    if (bvp1->vect[i] != bvp2->vect[i])
+      return 0;
+
+  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 ; 
-
-    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; } 
-   } 
-    
-   /* finish up the last fractional byte, if any */ 
-   for (i = j*8 ; i < bvp->size; i++) 
-       count += bitVectBitValue(bvp,i); 
-
-   return count; 
+  int i, j;
+  unsigned char byte;
+  int count = 0;
+  unsigned int *p1;
+
+  /* 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;
+
+  /* j is the number of bytes in the bitvect */
+  j = (bvp->size+7) / 8;
+
+  /* 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];
+    }
+
+  /* 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;
-
-    if (!bvp)
-	return -1;
-    for (i = 0; i < bvp->size ; i++ )
-	if (bitVectBitValue(bvp,i))
-	    return i;
+  int i;
 
+  if (!bvp)
     return -1;
+  for (i = 0; i < bvp->size; i++)
+    if (bitVectBitValue (bvp, i))
+      return i;
+
+  return -1;
 }
 
 /*-----------------------------------------------------------------*/
 /* bitVectDebugOn - prints bits that are on                        */
 /*-----------------------------------------------------------------*/
-void bitVectDebugOn (bitVect *bvp, FILE *of)
+void 
+bitVectDebugOn (bitVect * bvp, FILE * of)
 {
-	int i;
-	
-	if (of == NULL)
-		of = stdout;
-	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");
+  int i;
+
+  if (of == NULL)
+    of = stdout;
+  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");
 }