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
  25 #include "common.h"
  26
  27 #include "newalloc.h"
  28
  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     bvp = Safe_calloc(1,sizeof (bitVect));
  44
  45     bvp->size = size;
  46     bvp->bSize = byteSize = ( size / 8) + 1 ;
  47     bvp->vect = Safe_calloc(1,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->vect = Clear_realloc(bvp->vect, bvp -> bSize, bSize);
  69     bvp->size = size;
  70     bvp->bSize= bSize;
  71
  72     return bvp;
  73 }
  74
  75 /*-----------------------------------------------------------------*/
  76 /* bitVectSetBit - sets a given bit in the bit vector              */
  77 /*-----------------------------------------------------------------*/
  78 bitVect *bitVectSetBit (bitVect *bvp, int pos)
  79 {
  80     int byteSize;
  81     int offset ;
  82
  83     /* if set is null then allocate it */
  84     if (!bvp)
  85   bvp = newBitVect(bitVectDefault) ; /* allocate for twice the size */
  86
  87     if (bvp->size <= pos )
  88   bvp = bitVectResize (bvp,pos+2); /* conservatively resize */
  89
  90     byteSize = pos / 8 ;
  91     offset = pos % 8;
  92     bvp->vect[byteSize] |= (((unsigned char)1) <<
  93           (7 - offset));
  94     return bvp;
  95 }
  96
  97 /*-----------------------------------------------------------------*/
  98 /* bitVectUnSetBit - unsets the value of a bit in a bitvector      */
  99 /*-----------------------------------------------------------------*/
 100 void bitVectUnSetBit (bitVect *bvp, int pos)
 101 {
 102     int byteSize ;
 103     int offset ;
 104
 105     if (! bvp)
 106   return ;
 107
 108     byteSize = pos /8;
 109     if (bvp->bSize <= byteSize)
 110   return ;
 111
 112     offset = pos % 8 ;
 113
 114     bvp->vect[byteSize] &= ~ (((unsigned char)1) <<
 115             (7 - offset));
 116 }
 117
 118 /*-----------------------------------------------------------------*/
 119 /* bitVectBitValue - returns value value at bit position           */
 120 /*-----------------------------------------------------------------*/
 121 int bitVectBitValue (bitVect *bvp, int pos)
 122 {
 123     int byteSize;
 124     int offset ;
 125
 126     if (! bvp)
 127   return 0;
 128
 129     byteSize = pos /8;
 130
 131     if ( bvp->bSize <= byteSize )
 132   return 0;
 133
 134     offset = pos % 8 ;
 135
 136     return ((bvp->vect[byteSize] >> (7-offset)) & ((unsigned char)1) );
 137
 138 }
 139
 140 /*-----------------------------------------------------------------*/
 141 /* bitVectUnion - unions two bitvectors                            */
 142 /*-----------------------------------------------------------------*/
 143 bitVect *bitVectUnion ( bitVect *bvp1, bitVect *bvp2)
 144 {
 145     int i;
 146     bitVect *newBvp;
 147
 148     /* if both null */
 149     if (!bvp1 && !bvp2)
 150   return NULL ;
 151
 152     /* if one of them null then return the other */
 153     if (! bvp1 && bvp2 )
 154   return bitVectCopy (bvp2);
 155
 156     if ( bvp1 && ! bvp2 )
 157   return bitVectCopy (bvp1);
 158
 159     /* if they are not the same size */
 160     /* make them the same size */
 161     if (bvp1->bSize < bvp2->bSize)
 162   bvp1 = bitVectResize (bvp1,bvp2->size);
 163     else
 164   if (bvp2->bSize < bvp1->bSize)
 165       bvp2 = bitVectResize (bvp2,bvp1->size);
 166
 167     newBvp = newBitVect(bvp1->size);
 168
 169     for ( i = 0 ; i < bvp1->bSize ;i++)
 170   newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
 171
 172
 173     return newBvp;
 174 }
 175
 176 /*-----------------------------------------------------------------*/
 177 /* bitVectIntersect - intersect  two bitvectors                    */
 178 /*-----------------------------------------------------------------*/
 179 bitVect *bitVectIntersect ( bitVect *bvp1, bitVect *bvp2)
 180 {
 181     int i;
 182     bitVect *newBvp;
 183
 184     if (! bvp2 || ! bvp1 )
 185   return NULL ;
 186
 187     /* if they are not the same size */
 188     /* make them the same size */
 189     if (bvp1->bSize < bvp2->bSize)
 190   bvp1 = bitVectResize (bvp1,bvp2->bSize);
 191     else
 192   if (bvp2->size < bvp1->size)
 193       bvp2 = bitVectResize (bvp2,bvp1->size);
 194
 195     newBvp = newBitVect(bvp1->size);
 196
 197     for ( i = 0 ; i < bvp1->bSize ;i++)
 198   newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
 199
 200     return newBvp;
 201 }
 202
 203 /*-----------------------------------------------------------------*/
 204 /* bitVectBitsInCommon - special case of intersection determines   */
 205 /*                       if the vectors have any common bits set   */
 206 /*-----------------------------------------------------------------*/
 207 int bitVectBitsInCommon ( bitVect *bvp1, bitVect *bvp2 )
 208 {
 209     int i ;
 210
 211     if ( ! bvp1 || ! bvp2 )
 212   return 0;
 213
 214     for ( i = 0 ; i < min(bvp1->bSize,bvp2->bSize) ; i ++ )
 215   if ( bvp1->vect[i] & bvp2->vect[i] )
 216       return 1;
 217
 218     return 0;
 219 }
 220
 221 /*-----------------------------------------------------------------*/
 222 /* bitVectCplAnd - complement the second & and it with the first   */
 223 /*-----------------------------------------------------------------*/
 224 bitVect *bitVectCplAnd ( bitVect *bvp1, bitVect *bvp2)
 225 {
 226     int i;
 227
 228     if ( ! bvp2 )
 229   return bvp1 ;
 230
 231     if ( ! bvp1 )
 232   return bvp1 ;
 233
 234     /* if they are not the same size */
 235     /* make them the same size */
 236     if (bvp1->bSize < bvp2->bSize)
 237   bvp1 = bitVectResize (bvp1,bvp2->bSize);
 238     else
 239   if (bvp2->size < bvp1->size)
 240       bvp2 = bitVectResize (bvp2,bvp1->size);
 241
 242     for ( i = 0 ; i < bvp1->bSize ;i++)
 243   bvp1->vect[i] = bvp1->vect[i] & (~ bvp2->vect[i]);
 244
 245     return bvp1;
 246 }
 247
 248 /*-----------------------------------------------------------------*/
 249 /* bitVectIsZero - bit vector has all bits turned off              */
 250 /*-----------------------------------------------------------------*/
 251 int bitVectIsZero (bitVect *bvp)
 252 {
 253     int i ;
 254
 255     if (!bvp)
 256   return 1;
 257
 258     for ( i = 0 ; i < bvp->bSize ; i++ )
 259   if (bvp->vect[i] != 0)
 260       return 0;
 261
 262     return 1;
 263 }
 264
 265 /*-----------------------------------------------------------------*/
 266 /* bitVectsEqual - returns 1 if the two bit vectors are equal      */
 267 /*-----------------------------------------------------------------*/
 268 int bitVectEqual ( bitVect *bvp1, bitVect *bvp2)
 269 {
 270     int i ;
 271
 272     if ( !bvp1 || !bvp1)
 273   return 0;
 274
 275     if (bvp1 == bvp2)
 276   return 1;
 277
 278     if (bvp1->bSize != bvp2->bSize)
 279   return 0;
 280
 281     for (i = 0 ; i < bvp1->bSize ; i++ )
 282   if ( bvp1->vect[i] != bvp2->vect[i] )
 283       return 0;
 284
 285     return 1;
 286 }
 287
 288 /*-----------------------------------------------------------------*/
 289 /* bitVectCopy - creates a bitvector from another bit Vector       */
 290 /*-----------------------------------------------------------------*/
 291 bitVect *bitVectCopy (bitVect *bvp)
 292 {
 293     bitVect *newBvp;
 294     int i;
 295
 296     if (!bvp)
 297   return NULL;
 298
 299     newBvp = newBitVect(bvp->size);
 300     for ( i = 0 ; i < bvp->bSize; i++ )
 301   newBvp->vect[i] = bvp->vect[i];
 302
 303     return newBvp;
 304 }
 305
 306 /*-----------------------------------------------------------------*/
 307 /* bitVectnBitsOn - returns the number of bits that are on         */
 308 /*-----------------------------------------------------------------*/
 309 int bitVectnBitsOn (bitVect *bvp)
 310 {
 311     int i, j, k;
 312     unsigned char byte;
 313     int count = 0 ;
 314
 315     if (!bvp)
 316   return 0;
 317
 318    /* rip through most of the data in byte sized chunks */
 319    j = (bvp->size)/8;
 320    for (i = 0 ; i < j; i++) {
 321        byte = bvp->vect[i];
 322        for (k=0; k<8; k++) { count += byte&1; byte = byte>>1; }
 323    }
 324
 325    /* finish up the last fractional byte, if any */
 326    for (i = j*8 ; i < bvp->size; i++)
 327        count += bitVectBitValue(bvp,i);
 328
 329    return count;
 330
 331 }
 332
 333 /*-----------------------------------------------------------------*/
 334 /* bitVectFirstBit - returns the key for the first bit that is on  */
 335 /*-----------------------------------------------------------------*/
 336 int bitVectFirstBit (bitVect *bvp)
 337 {
 338     int i;
 339
 340     if (!bvp)
 341   return -1;
 342     for (i = 0; i < bvp->size ; i++ )
 343   if (bitVectBitValue(bvp,i))
 344       return i;
 345
 346     return -1;
 347 }
 348
 349 /*-----------------------------------------------------------------*/
 350 /* bitVectDebugOn - prints bits that are on                        */
 351 /*-----------------------------------------------------------------*/
 352 void bitVectDebugOn (bitVect *bvp, FILE *of)
 353 {
 354   int i;
 355
 356   if (of == NULL)
 357     of = stdout;
 358   if (!bvp)
 359     return;
 360
 361   fprintf(of,"bitvector Size = %d bSize = %d\n",bvp->size,bvp->bSize);
 362   fprintf(of,"Bits on { ");
 363   for (i = 0 ; i < bvp->size ; i++) {
 364     if (bitVectBitValue(bvp,i))
 365       fprintf(of,"(%d) ",i);
 366   }
 367   fprintf(of,"}\n");
 368 }