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(sizeof (bitVect));
  44
  45     bvp->size = size;
  46     bvp->bSize = byteSize = ( size / 8) + 1 ;
  47     bvp->vect = Safe_calloc(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 }