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