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