git.gag.com Git - fw/sdcc/blob - src/SDCCbitv.c

   1 /*-----------------------------------------------------------------
   2     SDCCbitv.c - contains support routines for bitvectors
   3
   4     Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
   5
   6     This program is free software; you can redistribute it and/or modify it
   7     under the terms of the GNU General Public License as published by the
   8     Free Software Foundation; either version 2, or (at your option) any
   9     later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19
  20     In other words, you are welcome to use, share and improve this program.
  21     You are forbidden to forbid anyone else to use, share and improve
  22     what you give them.   Help stamp out software-hoarding!
  23 -------------------------------------------------------------------------*/
  24 #include <stdio.h>
  25 #include "SDCCbitv.h"
  26 #ifndef ALLOC
  27 #include "SDCCglobl.h"
  28 #endif
  29 int bitVectDefault = 1024;
  30
  31 /* genernal note about a bitvectors:
  32    bit vectors are stored from left to right i.e.
  33    bit position 0 is the MS bit of the first byte
  34    this also means that bit positions must start from 0*/
  35 /*-----------------------------------------------------------------*/
  36 /* newBitVect - returns a new bitvector of size                    */
  37 /*-----------------------------------------------------------------*/
  38 bitVect *newBitVect (int size)
  39 {
  40     bitVect *bvp;
  41     int byteSize ;
  42
  43     ALLOC(bvp,sizeof (bitVect));
  44
  45     bvp->size = size;
  46     bvp->bSize = byteSize = ( size / 8) + 1 ;
  47     ALLOC(bvp->vect,byteSize);
  48     return bvp;
  49 }
  50
  51 /*-----------------------------------------------------------------*/
  52 /* bitVectResize - changes the size of a bit vector                */
  53 /*-----------------------------------------------------------------*/
  54 bitVect *bitVectResize (bitVect *bvp, int size)
  55 {
  56     int bSize = ( size / 8) + 1  ;
  57
  58     if (!bvp)
  59         return newBitVect (size);
  60
  61     /* if we already have enough space */
  62     if (bvp->bSize >= bSize ) {
  63         if (size > bvp->size)
  64             bvp->size = size ;
  65         return bvp;
  66     }
  67
  68     bvp->size = size;
  69     bvp->bSize= bSize;
  70     bvp->vect = GC_realloc(bvp->vect, bSize);
  71     return bvp;
  72 }
  73
  74 /*-----------------------------------------------------------------*/
  75 /* bitVectSetBit - sets a given bit in the bit vector              */
  76 /*-----------------------------------------------------------------*/
  77 bitVect *bitVectSetBit (bitVect *bvp, int pos)
  78 {
  79     int byteSize;
  80     int offset ;
  81
  82     /* if set is null then allocate it */
  83     if (!bvp)
  84         bvp = newBitVect(bitVectDefault) ; /* allocate for twice the size */
  85
  86     if (bvp->size <= pos )
  87         bvp = bitVectResize (bvp,pos+2); /* conservatively resize */
  88
  89     byteSize = pos / 8 ;
  90     offset = pos % 8;
  91     bvp->vect[byteSize] |= (((unsigned char)1) <<
  92                             (7 - offset));
  93     return bvp;
  94 }
  95
  96 /*-----------------------------------------------------------------*/
  97 /* bitVectUnSetBit - unsets the value of a bit in a bitvector      */
  98 /*-----------------------------------------------------------------*/
  99 void bitVectUnSetBit (bitVect *bvp, int pos)
 100 {
 101     int byteSize ;
 102     int offset ;
 103
 104     if (! bvp)
 105         return ;
 106
 107     byteSize = pos /8;
 108     if (bvp->bSize <= byteSize)
 109         return ;
 110
 111     offset = pos % 8 ;
 112
 113     bvp->vect[byteSize] &= ~ (((unsigned char)1) <<
 114                               (7 - offset));
 115 }
 116
 117 /*-----------------------------------------------------------------*/
 118 /* bitVectBitValue - returns value value at bit position           */
 119 /*-----------------------------------------------------------------*/
 120 int bitVectBitValue (bitVect *bvp, int pos)
 121 {
 122     int byteSize;
 123     int offset ;
 124
 125     if (! bvp)
 126         return 0;
 127
 128     byteSize = pos /8;
 129
 130     if ( bvp->bSize <= byteSize )
 131         return 0;
 132
 133     offset = pos % 8 ;
 134
 135     return ((bvp->vect[byteSize] >> (7-offset)) & ((unsigned char)1) );
 136
 137 }
 138
 139 /*-----------------------------------------------------------------*/
 140 /* bitVectUnion - unions two bitvectors                            */
 141 /*-----------------------------------------------------------------*/
 142 bitVect *bitVectUnion ( bitVect *bvp1, bitVect *bvp2)
 143 {
 144     int i;
 145     bitVect *newBvp;
 146
 147     /* if both null */
 148     if (!bvp1 && !bvp2)
 149         return NULL ;
 150
 151     /* if one of them null then return the other */
 152     if (! bvp1 && bvp2 )
 153         return bitVectCopy (bvp2);
 154
 155     if ( bvp1 && ! bvp2 )
 156         return bitVectCopy (bvp1);
 157
 158     /* if they are not the same size */
 159     /* make them the same size */
 160     if (bvp1->bSize < bvp2->bSize)
 161         bvp1 = bitVectResize (bvp1,bvp2->size);
 162     else
 163         if (bvp2->bSize < bvp1->bSize)
 164             bvp2 = bitVectResize (bvp2,bvp1->size);
 165
 166     newBvp = newBitVect(bvp1->size);
 167
 168     for ( i = 0 ; i < bvp1->bSize ;i++)
 169         newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
 170
 171
 172     return newBvp;
 173 }
 174
 175 /*-----------------------------------------------------------------*/
 176 /* bitVectIntersect - intersect  two bitvectors                    */
 177 /*-----------------------------------------------------------------*/
 178 bitVect *bitVectIntersect ( bitVect *bvp1, bitVect *bvp2)
 179 {
 180     int i;
 181     bitVect *newBvp;
 182
 183     if (! bvp2 || ! bvp1 )
 184         return NULL ;
 185
 186     /* if they are not the same size */
 187     /* make them the same size */
 188     if (bvp1->bSize < bvp2->bSize)
 189         bvp1 = bitVectResize (bvp1,bvp2->bSize);
 190     else
 191         if (bvp2->size < bvp1->size)
 192             bvp2 = bitVectResize (bvp2,bvp1->size);
 193
 194     newBvp = newBitVect(bvp1->size);
 195
 196     for ( i = 0 ; i < bvp1->bSize ;i++)
 197         newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
 198
 199     return newBvp;
 200 }
 201
 202 /*-----------------------------------------------------------------*/
 203 /* bitVectBitsInCommon - special case of intersection determines   */
 204 /*                       if the vectors have any common bits set   */
 205 /*-----------------------------------------------------------------*/
 206 int bitVectBitsInCommon ( bitVect *bvp1, bitVect *bvp2 )
 207 {
 208     int i ;
 209
 210     if ( ! bvp1 || ! bvp2 )
 211         return 0;
 212
 213     for ( i = 0 ; i < min(bvp1->bSize,bvp2->bSize) ; i ++ )
 214         if ( bvp1->vect[i] & bvp2->vect[i] )
 215             return 1;
 216
 217     return 0;
 218 }
 219
 220 /*-----------------------------------------------------------------*/
 221 /* bitVectCplAnd - complement the second & and it with the first   */
 222 /*-----------------------------------------------------------------*/
 223 bitVect *bitVectCplAnd ( bitVect *bvp1, bitVect *bvp2)
 224 {
 225     int i;
 226
 227     if ( ! bvp2 )
 228         return bvp1 ;
 229
 230     if ( ! bvp1 )
 231         return bvp1 ;
 232
 233     /* if they are not the same size */
 234     /* make them the same size */
 235     if (bvp1->bSize < bvp2->bSize)
 236         bvp1 = bitVectResize (bvp1,bvp2->bSize);
 237     else
 238         if (bvp2->size < bvp1->size)
 239             bvp2 = bitVectResize (bvp2,bvp1->size);
 240
 241     for ( i = 0 ; i < bvp1->bSize ;i++)
 242         bvp1->vect[i] = bvp1->vect[i] & (~ bvp2->vect[i]);
 243
 244     return bvp1;
 245 }
 246
 247 /*-----------------------------------------------------------------*/
 248 /* bitVectIsZero - bit vector has all bits turned off              */
 249 /*-----------------------------------------------------------------*/
 250 int bitVectIsZero (bitVect *bvp)
 251 {
 252     int i ;
 253
 254     if (!bvp)
 255         return 1;
 256
 257     for ( i = 0 ; i < bvp->bSize ; i++ )
 258         if (bvp->vect[i] != 0)
 259             return 0;
 260
 261     return 1;
 262 }
 263
 264 /*-----------------------------------------------------------------*/
 265 /* bitVectsEqual - returns 1 if the two bit vectors are equal      */
 266 /*-----------------------------------------------------------------*/
 267 int bitVectEqual ( bitVect *bvp1, bitVect *bvp2)
 268 {
 269     int i ;
 270
 271     if ( !bvp1 || !bvp1)
 272         return 0;
 273
 274     if (bvp1 == bvp2)
 275         return 1;
 276
 277     if (bvp1->bSize != bvp2->bSize)
 278         return 0;
 279
 280     for (i = 0 ; i < bvp1->bSize ; i++ )
 281         if ( bvp1->vect[i] != bvp2->vect[i] )
 282             return 0;
 283
 284     return 1;
 285 }
 286
 287 /*-----------------------------------------------------------------*/
 288 /* bitVectCopy - creates a bitvector from another bit Vector       */
 289 /*-----------------------------------------------------------------*/
 290 bitVect *bitVectCopy (bitVect *bvp)
 291 {
 292     bitVect *newBvp;
 293     int i;
 294
 295     if (!bvp)
 296         return NULL;
 297
 298     newBvp = newBitVect(bvp->size);
 299     for ( i = 0 ; i < bvp->bSize; i++ )
 300         newBvp->vect[i] = bvp->vect[i];
 301
 302     return newBvp;
 303 }
 304
 305 /*-----------------------------------------------------------------*/
 306 /* bitVectnBitsOn - returns the number of bits that are on         */
 307 /*-----------------------------------------------------------------*/
 308 int bitVectnBitsOn (bitVect *bvp)
 309 {
 310     int i, j, k;
 311     unsigned char byte;
 312     int count = 0 ;
 313
 314     if (!bvp)
 315         return 0;
 316
 317    /* rip through most of the data in byte sized chunks */
 318    j = (bvp->size)/8;
 319    for (i = 0 ; i < j; i++) {
 320        byte = bvp->vect[i];
 321        for (k=0; k<8; k++) { count += byte&1; byte = byte>>1; }
 322    }
 323
 324    /* finish up the last fractional byte, if any */
 325    for (i = j*8 ; i < bvp->size; i++)
 326        count += bitVectBitValue(bvp,i);
 327
 328    return count;
 329
 330 }
 331
 332 /*-----------------------------------------------------------------*/
 333 /* bitVectFirstBit - returns the key for the first bit that is on  */
 334 /*-----------------------------------------------------------------*/
 335 int bitVectFirstBit (bitVect *bvp)
 336 {
 337     int i;
 338
 339     if (!bvp)
 340         return -1;
 341     for (i = 0; i < bvp->size ; i++ )
 342         if (bitVectBitValue(bvp,i))
 343             return i;
 344
 345     return -1;
 346 }
 347
 348 /*-----------------------------------------------------------------*/
 349 /* bitVectDebugOn - prints bits that are on                        */
 350 /*-----------------------------------------------------------------*/
 351 void bitVectDebugOn (bitVect *bvp, FILE *of)
 352 {
 353         int i;
 354
 355         if (of == NULL)
 356                 of = stdout;
 357         if (!bvp)
 358                 return;
 359
 360         fprintf(of,"bitvector Size = %d bSize = %d\n",bvp->size,bvp->bSize);
 361         fprintf(of,"Bits on { ");
 362         for (i = 0 ; i < bvp->size ; i++) {
 363                 if (bitVectBitValue(bvp,i))
 364                         fprintf(of,"(%d) ",i);
 365         }
 366         fprintf(of,"}\n");
 367 }