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 *
  39 newBitVect (int size)
  40 {
  41   bitVect *bvp;
  42   int byteSize;
  43
  44   bvp = Safe_calloc (1, sizeof (bitVect));
  45
  46   bvp->size = size;
  47   bvp->bSize = byteSize = (size / 8) + 1;
  48   bvp->vect = Safe_calloc (1, byteSize);
  49   return bvp;
  50 }
  51
  52 /*-----------------------------------------------------------------*/
  53 /* bitVectResize - changes the size of a bit vector                */
  54 /*-----------------------------------------------------------------*/
  55 bitVect *
  56 bitVectResize (bitVect * bvp, int size)
  57 {
  58   int bSize = (size / 8) + 1;
  59
  60   if (!bvp)
  61     return newBitVect (size);
  62
  63   /* if we already have enough space */
  64   if (bvp->bSize >= bSize)
  65     {
  66       if (size > bvp->size)
  67         bvp->size = size;
  68       return bvp;
  69     }
  70
  71   bvp->vect = Clear_realloc (bvp->vect, bvp->bSize, bSize);
  72   bvp->size = size;
  73   bvp->bSize = bSize;
  74
  75   return bvp;
  76 }
  77
  78 /*-----------------------------------------------------------------*/
  79 /* bitVectSetBit - sets a given bit in the bit vector              */
  80 /*-----------------------------------------------------------------*/
  81 bitVect *
  82 bitVectSetBit (bitVect * bvp, int pos)
  83 {
  84   int byteSize;
  85   int offset;
  86
  87   /* if set is null then allocate it */
  88   if (!bvp)
  89     bvp = newBitVect (bitVectDefault);  /* allocate for twice the size */
  90
  91   if (bvp->size <= pos)
  92     bvp = bitVectResize (bvp, pos + 2);         /* conservatively resize */
  93
  94   byteSize = pos / 8;
  95   offset = pos % 8;
  96   bvp->vect[byteSize] |= (((unsigned char) 1) <<
  97                           (7 - offset));
  98   return bvp;
  99 }
 100
 101 /*-----------------------------------------------------------------*/
 102 /* bitVectUnSetBit - unsets the value of a bit in a bitvector      */
 103 /*-----------------------------------------------------------------*/
 104 void
 105 bitVectUnSetBit (bitVect * bvp, int pos)
 106 {
 107   int byteSize;
 108   int offset;
 109
 110   if (!bvp)
 111     return;
 112
 113   byteSize = pos / 8;
 114   if (bvp->bSize <= byteSize)
 115     return;
 116
 117   offset = pos % 8;
 118
 119   bvp->vect[byteSize] &= ~(((unsigned char) 1) <<
 120                            (7 - offset));
 121 }
 122
 123 /*-----------------------------------------------------------------*/
 124 /* bitVectBitValue - returns value value at bit position           */
 125 /*-----------------------------------------------------------------*/
 126 int
 127 bitVectBitValue (bitVect * bvp, int pos)
 128 {
 129   int byteSize;
 130   int offset;
 131
 132   if (!bvp)
 133     return 0;
 134
 135   byteSize = pos / 8;
 136
 137   if (bvp->bSize <= byteSize)
 138     return 0;
 139
 140   offset = pos % 8;
 141
 142   return ((bvp->vect[byteSize] >> (7 - offset)) & ((unsigned char) 1));
 143
 144 }
 145
 146 /*-----------------------------------------------------------------*/
 147 /* bitVectUnion - unions two bitvectors                            */
 148 /*-----------------------------------------------------------------*/
 149 bitVect *
 150 bitVectUnion (bitVect * bvp1, bitVect * bvp2)
 151 {
 152   int i;
 153   bitVect *newBvp;
 154   unsigned int *pn, *p1, *p2;
 155   int nbits;
 156
 157   /* if both null */
 158   if (!bvp1 && !bvp2)
 159     return NULL;
 160
 161   /* if one of them null then return the other */
 162   if (!bvp1 && bvp2)
 163     return bitVectCopy (bvp2);
 164
 165   if (bvp1 && !bvp2)
 166     return bitVectCopy (bvp1);
 167
 168   /* if they are not the same size */
 169   /* make them the same size */
 170   if (bvp1->bSize < bvp2->bSize)
 171     bvp1 = bitVectResize (bvp1, bvp2->size);
 172   else if (bvp2->bSize < bvp1->bSize)
 173     bvp2 = bitVectResize (bvp2, bvp1->size);
 174
 175   newBvp = newBitVect (bvp1->size);
 176   nbits = bvp1->bSize;
 177   i = 0;
 178
 179   pn = (unsigned int *)newBvp->vect;
 180   p1 = (unsigned int *)bvp1->vect;
 181   p2 = (unsigned int *)bvp2->vect;
 182
 183   while ((nbits - i) >= sizeof(*pn))
 184     {
 185       *pn++ = *p1++ | *p2++;
 186       i += sizeof(*pn);
 187     }
 188
 189   for (; i < nbits; i++)
 190     newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
 191
 192
 193   return newBvp;
 194 }
 195
 196 /*-----------------------------------------------------------------*/
 197 /* bitVectIntersect - intersect  two bitvectors                    */
 198 /*-----------------------------------------------------------------*/
 199 bitVect *
 200 bitVectIntersect (bitVect * bvp1, bitVect * bvp2)
 201 {
 202   int i;
 203   bitVect *newBvp;
 204   unsigned int *pn, *p1, *p2;
 205   int nbits;
 206
 207   if (!bvp2 || !bvp1)
 208     return NULL;
 209
 210   /* if they are not the same size */
 211   /* make them the same size */
 212   if (bvp1->bSize < bvp2->bSize)
 213     bvp1 = bitVectResize (bvp1, bvp2->bSize);
 214   else if (bvp2->size < bvp1->size)
 215     bvp2 = bitVectResize (bvp2, bvp1->size);
 216
 217   newBvp = newBitVect (bvp1->size);
 218   nbits = bvp1->bSize;
 219   i = 0;
 220
 221   pn = (unsigned int *)newBvp->vect;
 222   p1 = (unsigned int *)bvp1->vect;
 223   p2 = (unsigned int *)bvp2->vect;
 224
 225   while ((nbits - i) >= sizeof(*pn))
 226     {
 227       *pn++ = *p1++ & *p2++;
 228       i += sizeof(*pn);
 229     }
 230
 231   for (; i < nbits; i++)
 232     newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
 233
 234   return newBvp;
 235 }
 236
 237 /*-----------------------------------------------------------------*/
 238 /* bitVectBitsInCommon - special case of intersection determines   */
 239 /*                       if the vectors have any common bits set   */
 240 /*-----------------------------------------------------------------*/
 241 int
 242 bitVectBitsInCommon (bitVect * bvp1, bitVect * bvp2)
 243 {
 244   int i;
 245   int nbits;
 246   unsigned int *p1, *p2;
 247
 248   if (!bvp1 || !bvp2)
 249     return 0;
 250
 251   nbits = min (bvp1->bSize, bvp2->bSize);
 252   i = 0;
 253
 254   p1 = (unsigned int *)bvp1->vect;
 255   p2 = (unsigned int *)bvp2->vect;
 256
 257   while ((nbits-i) >= sizeof(*p1))
 258     {
 259       if (*p1 & *p2)
 260         return 1;
 261       p1++; p2++;
 262       i += sizeof(*p1);
 263     }
 264
 265   for (; i < nbits; i++)
 266     if (bvp1->vect[i] & bvp2->vect[i])
 267       return 1;
 268
 269   return 0;
 270 }
 271
 272 /*-----------------------------------------------------------------*/
 273 /* bitVectCplAnd - complement the second & and it with the first   */
 274 /*-----------------------------------------------------------------*/
 275 bitVect *
 276 bitVectCplAnd (bitVect * bvp1, bitVect * bvp2)
 277 {
 278   int i;
 279   unsigned int *p1, *p2;
 280   int nbits;
 281
 282   if (!bvp2)
 283     return bvp1;
 284
 285   if (!bvp1)
 286     return bvp1;
 287
 288   /* if they are not the same size */
 289   /* make them the same size */
 290   if (bvp1->bSize < bvp2->bSize)
 291     bvp1 = bitVectResize (bvp1, bvp2->bSize);
 292   else if (bvp2->size < bvp1->size)
 293     bvp2 = bitVectResize (bvp2, bvp1->size);
 294
 295   nbits = bvp1->bSize;
 296   i = 0;
 297
 298   p1 = (unsigned int *)bvp1->vect;
 299   p2 = (unsigned int *)bvp2->vect;
 300
 301   while ((nbits - i) >= sizeof(*p1))
 302     {
 303       *p1 = *p1 & (~*p2);
 304       p2++; p1++;
 305       i += sizeof(*p1);
 306     }
 307
 308   for (; i < nbits; i++)
 309     bvp1->vect[i] = bvp1->vect[i] & (~bvp2->vect[i]);
 310
 311   return bvp1;
 312 }
 313
 314 /*-----------------------------------------------------------------*/
 315 /* bitVectIsZero - bit vector has all bits turned off              */
 316 /*-----------------------------------------------------------------*/
 317 int
 318 bitVectIsZero (bitVect * bvp)
 319 {
 320   int i;
 321
 322   if (!bvp)
 323     return 1;
 324
 325   for (i = 0; i < bvp->bSize; i++)
 326     if (bvp->vect[i] != 0)
 327       return 0;
 328
 329   return 1;
 330 }
 331
 332 /*-----------------------------------------------------------------*/
 333 /* bitVectsEqual - returns 1 if the two bit vectors are equal      */
 334 /*-----------------------------------------------------------------*/
 335 int
 336 bitVectEqual (bitVect * bvp1, bitVect * bvp2)
 337 {
 338   int i;
 339
 340   if (!bvp1 || !bvp1)
 341     return 0;
 342
 343   if (bvp1 == bvp2)
 344     return 1;
 345
 346   if (bvp1->bSize != bvp2->bSize)
 347     return 0;
 348
 349   for (i = 0; i < bvp1->bSize; i++)
 350     if (bvp1->vect[i] != bvp2->vect[i])
 351       return 0;
 352
 353   return 1;
 354 }
 355
 356 /*-----------------------------------------------------------------*/
 357 /* bitVectCopy - creates a bitvector from another bit Vector       */
 358 /*-----------------------------------------------------------------*/
 359 bitVect *
 360 bitVectCopy (bitVect * bvp)
 361 {
 362   bitVect *newBvp;
 363   int i;
 364
 365   if (!bvp)
 366     return NULL;
 367
 368   newBvp = newBitVect (bvp->size);
 369   for (i = 0; i < bvp->bSize; i++)
 370     newBvp->vect[i] = bvp->vect[i];
 371
 372   return newBvp;
 373 }
 374
 375 /*-----------------------------------------------------------------*/
 376 /* bitVectnBitsOn - returns the number of bits that are on         */
 377 /*-----------------------------------------------------------------*/
 378 int
 379 bitVectnBitsOn (bitVect * bvp)
 380 {
 381   int i, j;
 382   unsigned char byte;
 383   int count = 0;
 384   unsigned int *p1;
 385
 386   /* The bit vector is highest to lowest.  Interesting. */
 387   unsigned int mask[] = {
 388     0, 128, 128+64, 128+64+32, 128+64+32+16,
 389     128+64+32+16+8, 128+64+32+16+8+4, 128+64+32+16+8+4+2
 390   };
 391
 392   if (!bvp)
 393     return 0;
 394
 395   /* j is the number of bytes in the bitvect */
 396   j = (bvp->size+7) / 8;
 397
 398   /* Fix up the highest bits in the top byte so that we can iterate over
 399      all of them. */
 400   if (bvp->size%8 != 0)
 401     {
 402       bvp->vect[j-1] &= mask[bvp->size&7];
 403     }
 404
 405   /* Take care of things in machine word chunks if possible.  As we
 406      are only counting bits it does not matter which order they are
 407      counted in.
 408   */
 409   i = 0;
 410   p1 = (unsigned int *)bvp->vect;
 411
 412   while ((j-i) >= sizeof(*p1))
 413     {
 414       unsigned int word = *p1++;
 415       while (word)
 416         {
 417           count++;
 418           word &= word-1;
 419         }
 420       i += sizeof(*p1);
 421     }
 422
 423   /* Take care of the rest of the bitvect. */
 424   for (; i < j; i++)
 425     {
 426       byte = bvp->vect[i];
 427       while (byte)
 428         {
 429           count++;
 430           byte &= byte-1;
 431         }
 432     }
 433   return count;
 434 }
 435
 436 /*-----------------------------------------------------------------*/
 437 /* bitVectFirstBit - returns the key for the first bit that is on  */
 438 /*-----------------------------------------------------------------*/
 439 int
 440 bitVectFirstBit (bitVect * bvp)
 441 {
 442   int i;
 443
 444   if (!bvp)
 445     return -1;
 446   for (i = 0; i < bvp->size; i++)
 447     if (bitVectBitValue (bvp, i))
 448       return i;
 449
 450   return -1;
 451 }
 452
 453 /*-----------------------------------------------------------------*/
 454 /* bitVectDebugOn - prints bits that are on                        */
 455 /*-----------------------------------------------------------------*/
 456 void
 457 bitVectDebugOn (bitVect * bvp, FILE * of)
 458 {
 459   int i;
 460
 461   if (of == NULL)
 462     of = stdout;
 463   if (!bvp)
 464     return;
 465
 466   fprintf (of, "bitvector Size = %d bSize = %d\n", bvp->size, bvp->bSize);
 467   fprintf (of, "Bits on { ");
 468   for (i = 0; i < bvp->size; i++)
 469     {
 470       if (bitVectBitValue (bvp, i))
 471         fprintf (of, "(%d) ", i);
 472     }
 473   fprintf (of, "}\n");
 474 }