bitvect.h

   1 #ifndef BITVECT_H
   2 #define BITVECT_H 1
   3
   4 /* === Bit vectors ========================================================= */
   5
   6 /* ... Generic macros ...................................................... */
   7
   8 #define INLINE_DECLARE(P) STATIC P
   9 #define INLINE_DEFINE
  10
  11 #ifndef BV_UNIT
  12 # define BV_UNIT unsigned char
  13 #endif
  14
  15 #define BV_SIZE(I) ((((I) % CHAR_BIT) != 0) + ((I) / CHAR_BIT))
  16
  17 #define BITS(T) (CHAR_BIT * sizeof(T))
  18
  19 /* 0 <= I <  CHAR_BIT * sizeof(T) */
  20 #define BV_MASK_LOWER(T, I)  (~((~((T) 0)) << (I)))
  21 /* 0 <  I <= CHAR_BIT * sizeof(T) */
  22 #define BV_MASK_HIGHER(T, I) ((~((T) 0)) << (BITS(T) - (I)))
  23
  24 #define BV_DO_ALIGNED_FORWARD(T, A)       \
  25  mask = BV_MASK_HIGHER(T, BITS(T) - fs);  \
  26  if (fs + l <= BITS(T)) {                 \
  27   /* Branching is apparently useless,     \
  28    * but since we can't portably shift    \
  29    * CHAR_BITS from a char...             \
  30    * Actually, we only copy up to this */ \
  31   if (fs + l < BITS(T))                   \
  32    mask &= BV_MASK_LOWER(T, fs + l);      \
  33   *t = (*t & ~mask) | (*f & mask);        \
  34  } else {                                 \
  35   size_t lo, lk;                          \
  36   *t = (*t & ~mask) | (*f & mask);        \
  37   ++t;                                    \
  38   ++f;                                    \
  39   l -= (BITS(T) - ts);                    \
  40   lo = l % BITS(T);                       \
  41   lk = l / BITS(T);                       \
  42   BV_##A##_UNIT_ALIGNED(T, t, f, lk);     \
  43   t += lk;                                \
  44   f += lk;                                \
  45   if (lo) {                               \
  46    mask = BV_MASK_LOWER(T, lo);           \
  47    *t = (*t & ~mask) | (*f & mask);       \
  48   }                                       \
  49  }
  50
  51 #define BV_DO_ALIGNED_BACKWARD(T, A)         \
  52  if (fs + l <= BITS(T)) {                    \
  53   mask = BV_MASK_HIGHER(T, BITS(T) - fs);    \
  54   /* Branching is apparently useless,        \
  55    * but since we can't portably shift       \
  56    * CHAR_BITS from a char...                \
  57    * Actually, we only copy up to this */    \
  58   if (fs + l < BITS(T))                      \
  59    mask &= BV_MASK_LOWER(T, fs + l);         \
  60   *t = (*t & ~mask) | (*f & mask);           \
  61  } else {                                    \
  62   size_t lo, lk;                             \
  63   l -= (BITS(T) - ts);                       \
  64   lo = l % BITS(T);                          \
  65   lk = l / BITS(T);                          \
  66   ++t;                                       \
  67   ++f;                                       \
  68   if (lo) {                                  \
  69    mask = BV_MASK_LOWER(T, lo);              \
  70    t[lk] = (t[lk] & ~mask) | (f[lk] & mask); \
  71   }                                          \
  72   BV_##A##_UNIT_ALIGNED(T, t, f, lk);        \
  73   mask = BV_MASK_HIGHER(T, BITS(T) - fs);    \
  74   t[-1] = (t[-1] & ~mask) | (f[-1] & mask);  \
  75  }
  76
  77 #define BV_DO_LEFT_FORWARD(T, A)                        \
  78  step = ts - fs;                                        \
  79  mask = BV_MASK_HIGHER(T, BITS(T) - ts);                \
  80  if (ts + l <= BITS(T)) {                               \
  81   if (ts + l < BITS(T))                                 \
  82    mask &= BV_MASK_LOWER(T, ts + l);                    \
  83   *t = (*t & ~mask) | ((*f & (mask >> step)) << step);  \
  84  } else {                                               \
  85   size_t pets = BITS(T) - step;                         \
  86   l -= (BITS(T) - ts);                                  \
  87   *t = (*t & ~mask) | ((*f & (mask >> step)) << step);  \
  88   ++t;                                                  \
  89   if (l <= step) {                                      \
  90    mask = BV_MASK_LOWER(T, l);                          \
  91    *t = (*t & ~mask) | ((*f & (mask << pets)) >> pets); \
  92   } else {                                              \
  93    ins = (*f & BV_MASK_HIGHER(T, step)) >> pets;        \
  94    ++f;                                                 \
  95    offset = l % BITS(T);                                \
  96    end    = t + l / BITS(T);                            \
  97    while (t < end) {                                    \
  98     BV_##A##_UNIT_LEFT_FORWARD(T, t, f, step);          \
  99     ++t; ++f;                                           \
 100    }                                                    \
 101    if (offset > step) {                                 \
 102     mask = BV_MASK_LOWER(T, offset - step);             \
 103     *t = (*t & (~mask << step))                         \
 104        | ((*f & mask) << step)                          \
 105        | ins;                                           \
 106    } else if (offset) {                                 \
 107     mask = BV_MASK_LOWER(T, offset);                    \
 108     *t = (*t & ~mask) | (ins & mask);                   \
 109    }                                                    \
 110   }                                                     \
 111  }
 112
 113 #define BV_DO_RIGHT_FORWARD(T, A)                            \
 114  step = fs - ts;                                             \
 115  mask = BV_MASK_HIGHER(T, BITS(T) - fs);                     \
 116  if (fs + l <= BITS(T)) {                                    \
 117   if (fs + l < BITS(T))                                      \
 118    mask &= BV_MASK_LOWER(T, fs + l);                         \
 119   *t = (*t & ~(mask >> step)) | ((*f & mask) >> step);       \
 120  } else {                                                    \
 121   l  -= (BITS(T) - fs);                                      \
 122   ins = ((*f & mask) >> step) | (*t & BV_MASK_LOWER(T, ts)); \
 123   ++f;                                                       \
 124   offset = l % BITS(T);                                      \
 125   end    = f + l / BITS(T) + (offset > step);                \
 126   while (f < end) {                                          \
 127    BV_##A##_UNIT_RIGHT_FORWARD(T, t, f, step);               \
 128    ++t; ++f;                                                 \
 129   }                                                          \
 130   if (!offset)                                               \
 131    offset += BITS(T);                                        \
 132   if (offset > step) {                                       \
 133    mask = BV_MASK_LOWER(T, offset - step);                   \
 134    *t = (*t & ~mask) | (ins & mask);                         \
 135   } else {                                                   \
 136    mask = BV_MASK_LOWER(T, offset);                          \
 137    *t = (*t & (~mask << (BITS(T) - step)))                   \
 138       | ((*f & mask) << (BITS(T) - step))                    \
 139       | ins;                                                 \
 140   }                                                          \
 141  }
 142
 143 #define BV_DO_LEFT_BACKWARD(T, A)                       \
 144  step = ts - fs;                                        \
 145  mask = BV_MASK_LOWER(T, BITS(T) - ts);                 \
 146  if (ts + l <= BITS(T)) {                               \
 147   if (ts + l < BITS(T))                                 \
 148    mask &= BV_MASK_HIGHER(T, ts + l);                   \
 149   *t = (*t & ~mask) | ((*f & (mask << step)) >> step);  \
 150  } else {                                               \
 151   size_t pets = BITS(T) - step;                         \
 152   l -= (BITS(T) - ts);                                  \
 153   *t = (*t & ~mask) | ((*f & (mask << step)) >> step);  \
 154   --t;                                                  \
 155   if (l <= step) {                                      \
 156    mask = BV_MASK_HIGHER(T, l);                         \
 157    *t = (*t & ~mask) | ((*f & (mask >> pets)) << pets); \
 158   } else {                                              \
 159    ins = (*f & BV_MASK_LOWER(T, step)) << pets;         \
 160    --f;                                                 \
 161    offset = l % BITS(T);                                \
 162    begin  = t - l / BITS(T);                            \
 163    while (t > begin) {                                  \
 164     BV_##A##_UNIT_LEFT_BACKWARD(T, t, f, step);         \
 165     --t; --f;                                           \
 166    }                                                    \
 167    if (offset > step) {                                 \
 168     mask = BV_MASK_HIGHER(T, offset - step);            \
 169     *t = (*t & (~mask >> step))                         \
 170        | ((*f & mask) >> step)                          \
 171        | ins;                                           \
 172    } else if (offset) {                                 \
 173     mask = BV_MASK_HIGHER(T, offset);                   \
 174     *t = (*t & ~mask) | (ins & mask);                   \
 175    }                                                    \
 176   }                                                     \
 177  }
 178
 179 #define BV_DO_RIGHT_BACKWARD(T, A)                            \
 180  step = fs - ts;                                              \
 181  mask = BV_MASK_LOWER(T, BITS(T) - fs);                       \
 182  if (fs + l <= BITS(T)) {                                     \
 183   if (fs + l < BITS(T))                                       \
 184    mask &= BV_MASK_HIGHER(T, fs + l);                         \
 185   *t = (*t & ~(mask << step)) | ((*f & mask) << step);        \
 186  } else {                                                     \
 187   l  -= (BITS(T) - fs);                                       \
 188   ins = ((*f & mask) << step);                                \
 189   if (ts)                                                     \
 190    ins |= (*t & BV_MASK_HIGHER(T, ts));                       \
 191   --f;                                                        \
 192   offset = l % BITS(T);                                       \
 193   begin  = f - l / BITS(T) + (offset <= step);                \
 194   while (f >= begin) {                                        \
 195    BV_##A##_UNIT_RIGHT_BACKWARD(T, t, f, step);               \
 196    --t; --f;                                                  \
 197   }                                                           \
 198   if (!offset)                                                \
 199    offset += BITS(T);                                         \
 200   if (offset > step) {                                        \
 201    mask = BV_MASK_HIGHER(T, offset - step);                   \
 202    *t = (*t & ~mask) | (ins & mask);                          \
 203   } else {                                                    \
 204    mask = BV_MASK_HIGHER(T, offset);                          \
 205    *t = (*t & (~mask >> (BITS(T) - step)))                    \
 206       | ((*f & mask) >> (BITS(T) - step))                     \
 207       | ins;                                                  \
 208   }                                                           \
 209  }
 210
 211 /* ... Copy ................................................................. */
 212
 213 #define BV_COPY_UNIT_ALIGNED(X, T, F, L) memcpy((T), (F), (L) * sizeof(X))
 214
 215 /* Save the O - B higher bits, shift B bits left, add B bits from f at right */
 216 #define BV_COPY_UNIT_LEFT_FORWARD(X, T, F, B) \
 217  *(T) = (*(F) << (B)) | ins;                  \
 218  ins  = *(F) >> (BITS(X) - (B));
 219
 220 /* Save the B lower bits, shift B bits right, add B bits from F at left */
 221 #define BV_COPY_UNIT_RIGHT_FORWARD(X, T, F, B) \
 222  *(T) = (*(F) << (BITS(X) - (B))) | ins;       \
 223  ins  = *(F) >> (B);
 224
 225 #define T BV_UNIT
 226 INLINE_DECLARE(void bv_copy(void *t_, size_t ts, const void *f_, size_t fs, size_t l))
 227 #ifdef INLINE_DEFINE
 228 {
 229  size_t offset, step;
 230  T ins, mask, *t = (T *) t_;
 231  const T *f = (const T *) f_, *end;
 232
 233  t  += ts / BITS(T);
 234  ts %= BITS(T);
 235
 236  f  += fs / BITS(T);
 237  fs %= BITS(T);
 238
 239  if (ts == fs) {
 240   BV_DO_ALIGNED_FORWARD(T, COPY);
 241  } else if (ts < fs) {
 242   BV_DO_RIGHT_FORWARD(T, COPY);
 243  } else { /* ts > fs */
 244   BV_DO_LEFT_FORWARD(T, COPY);
 245  }
 246
 247  return;
 248 }
 249 #endif /* INLINE_DEFINE */
 250 #undef T
 251
 252 /* ... Move ................................................................ */
 253
 254 #define BV_MOVE_UNIT_ALIGNED(X, T, F, L) memmove((T), (F), (L) * sizeof(X))
 255
 256 #define BV_MOVE_UNIT_LEFT_FORWARD(X, T, F, B) \
 257  tmp  = *(F) >> (BITS(X) - (B));              \
 258  *(T) = (*(F) << (B)) | ins;                  \
 259  ins  = tmp;
 260
 261 #define BV_MOVE_UNIT_RIGHT_FORWARD(X, T, F, B) \
 262  tmp  = *(F) >> (B);                           \
 263  *(T) = (*(F) << (BITS(X) - (B))) | ins;       \
 264  ins  = tmp;
 265
 266 #define BV_MOVE_UNIT_LEFT_BACKWARD(X, T, F, B) \
 267  tmp  = *(F) << (BITS(X) - (B));               \
 268  *(T) = (*(F) >> (B)) | ins;                   \
 269  ins  = tmp;
 270
 271 #define BV_MOVE_UNIT_RIGHT_BACKWARD(X, T, F, B) \
 272  tmp  = *(F) << (B);                            \
 273  *(T) = (*(F) >> (BITS(X) - (B))) | ins;        \
 274  ins  = tmp;
 275
 276 #define BV_MOVE_INIT_REVERSE(T, V, VS) \
 277  z     = (VS) + l;                     \
 278  (VS)  = z % BITS(T);                  \
 279  if ((VS) > 0) {                       \
 280   (V)  = bv + (z / BITS(T));           \
 281   (VS) = BITS(T) - (VS);               \
 282  } else {                              \
 283   /* z >= BITS(T) because l > 0 */     \
 284   (V)  = bv + (z / BITS(T)) - 1;       \
 285  }
 286
 287 #define T BV_UNIT
 288 INLINE_DECLARE(void bv_move(void *bv_, size_t ts, size_t fs, size_t l))
 289 #ifdef INLINE_DEFINE
 290 {
 291  size_t to, fo, offset, step;
 292  T ins, tmp, mask, *bv = (T *) bv_, *t, *f;
 293  const T *begin, *end;
 294
 295  if (ts == fs)
 296   return;
 297
 298  to = ts % BITS(T);
 299  fo = fs % BITS(T);
 300
 301  if (ts < fs) {
 302   t  = bv + ts / BITS(T);
 303   ts = to;
 304   f  = bv + fs / BITS(T);
 305   fs = fo;
 306   if (ts == fs) {
 307    BV_DO_ALIGNED_FORWARD(T, MOVE);
 308   } else if (ts < fs) {
 309    BV_DO_RIGHT_FORWARD(T, MOVE);
 310   } else { /* ts > fs */
 311    BV_DO_LEFT_FORWARD(T, MOVE);
 312   }
 313  } else if (to == fo) {
 314   t  = bv + ts / BITS(T);
 315   ts = to;
 316   f  = bv + fs / BITS(T);
 317   fs = fo;
 318   BV_DO_ALIGNED_BACKWARD(T, MOVE);
 319  } else { /* ts > fs */
 320   size_t z;
 321   BV_MOVE_INIT_REVERSE(T, t, ts);
 322   BV_MOVE_INIT_REVERSE(T, f, fs);
 323   if (ts < fs) {
 324    BV_DO_RIGHT_BACKWARD(T, MOVE);
 325   } else { /* ts > fs */
 326    BV_DO_LEFT_BACKWARD(T, MOVE);
 327   }
 328  }
 329
 330  return;
 331 }
 332 #endif /* INLINE_DEFINE */
 333 #undef T
 334
 335 /* ... Compare ............................................................. */
 336
 337 #define BV_EQ(T, B1, B2) \
 338  if (((T) (B1)) != ((T) (B2))) return 0;
 339
 340 #define BV_EQ_MASK(T, B1, B2, M) BV_EQ(T, (B1) & (M), (B2) & (M))
 341
 342 #define BV_EQ_LEFT(T, B1, B2, L, B)        \
 343  offset = (L) % BITS(T);                   \
 344  end    = (B1) + (L) / BITS(T);            \
 345  while ((B1) < end) {                      \
 346   BV_EQ(T, *(B1), (*(B2) << (B)) | ins);   \
 347   ins = *(B2) >> (BITS(T) - (B));          \
 348   ++(B1); ++(B2);                          \
 349  }                                         \
 350  if (offset > (B)) {                       \
 351   mask = BV_MASK_LOWER(T, offset - (B));   \
 352   BV_EQ(T, *(B1) & ~(~mask << (B)),        \
 353            ((*(B2) & mask) << (B)) | ins); \
 354  } else if (offset) {                      \
 355   mask = BV_MASK_LOWER(T, offset);         \
 356   BV_EQ_MASK(T, *(B1), ins, mask);         \
 357  }
 358
 359 #define BV_EQ_RIGHT(T, B1, B2, L, B)                   \
 360  offset = (L) % BITS(T);                               \
 361  end    = (B2) + (L) / BITS(T) + (offset >= (B));      \
 362  while ((B2) < end) {                                  \
 363   BV_EQ(T, *(B1), (*(B2) << (BITS(T) - (B))) | ins);   \
 364   ins = *(B2) >> (B);                                  \
 365   ++(B1); ++(B2);                                      \
 366  }                                                     \
 367  if (!offset)                                          \
 368   offset += BITS(T);                                   \
 369  if (offset >= (B)) {                                  \
 370   mask = BV_MASK_LOWER(T, offset - (B));               \
 371   BV_EQ_MASK(T, *(B1), ins, mask);                     \
 372  } else {                                              \
 373   mask = BV_MASK_LOWER(T, offset);                     \
 374   BV_EQ(T, *(B1) & ~(~mask << (BITS(T) - (B))),        \
 375            ((*(B2) & mask) << (BITS(T) - (B))) | ins); \
 376  }
 377
 378 #define T BV_UNIT
 379 INLINE_DECLARE(int bv_eq(const void *bv1_, size_t s1, const void *bv2_, size_t s2, size_t l))
 380 #ifdef INLINE_DEFINE
 381 {
 382  size_t offset, step;
 383  T ins, mask;
 384  const T *bv1 = (const T *) bv1_, *bv2 = (const T *) bv2_, *end;
 385
 386  bv1 += s1 / BITS(T);
 387  s1  %= BITS(T);
 388
 389  bv2 += s2 / BITS(T);
 390  s2  %= BITS(T);
 391
 392  if (s1 == s2) {
 393
 394   mask = BV_MASK_HIGHER(T, BITS(T) - s2);
 395   if (s2 + l <= BITS(T)) {
 396    if (s2 + l < BITS(T)) {
 397     mask &= BV_MASK_LOWER(T, s2 + l);
 398    }
 399    BV_EQ_MASK(T, *bv1, *bv2, mask);
 400   } else {
 401    int ret;
 402    size_t lo, lk;
 403    BV_EQ_MASK(T, *bv1, *bv2, mask);
 404    ++bv1;
 405    ++bv2;
 406    l -= (BITS(T) - s2);
 407    lo = l % BITS(T);
 408    lk = l / BITS(T);
 409    if ((ret = memcmp(bv1, bv2, lk * sizeof(T))) != 0)
 410     return 0;
 411    if (lo) {
 412     mask = BV_MASK_LOWER(T, lo);
 413     BV_EQ_MASK(T, *bv1, *bv2, mask);
 414    }
 415   }
 416
 417  } else if (s1 < s2) {
 418
 419   step = s2 - s1;
 420   mask = BV_MASK_HIGHER(T, BITS(T) - s2);
 421   if (s2 + l <= BITS(T)) {
 422    if (s2 + l < BITS(T))
 423     mask &= BV_MASK_LOWER(T, s2 + l);
 424    BV_EQ(T, *bv1 & (mask >> step), (*bv2 & mask) >> step);
 425   } else {
 426    l -= (BITS(T) - s2);
 427    ins = ((*bv2 & mask) >> step) | (*bv1 & BV_MASK_LOWER(T, s1));
 428    ++bv2;
 429    offset = l % BITS(T);
 430    end    = bv2 + l / BITS(T) + (offset >= step);
 431    while (bv2 < end) {
 432     BV_EQ(T, *bv1, (*bv2 << (BITS(T) - step)) | ins);
 433     ins = *bv2 >> step;
 434     ++bv1; ++bv2;
 435    }
 436    if (!offset)
 437     offset += BITS(T);
 438    if (offset >= step) {
 439     mask = BV_MASK_LOWER(T, offset - step);
 440     BV_EQ_MASK(T, *bv1, ins, mask);
 441    } else {
 442     mask = BV_MASK_LOWER(T, offset);
 443     BV_EQ(T, *bv1 & ~(~mask << (BITS(T) - step)),
 444              ((*bv2 & mask) << (BITS(T) - step)) | ins);
 445    }
 446 /*   BV_EQ_RIGHT(T, bv1, bv2, l, step); */
 447   }
 448
 449  } else { /* s1 > s2 */
 450
 451   step = s1 - s2;
 452   mask = BV_MASK_HIGHER(T, BITS(T) - s1);
 453   if (s1 + l <= BITS(T)) {
 454    if (s1 + l < BITS(T))
 455     mask &= BV_MASK_LOWER(T, s1 + l);
 456    BV_EQ(T, *bv1 & mask, (*bv2 & (mask >> step)) << step);
 457   } else {
 458    size_t pets = BITS(T) - step;
 459    l -= (BITS(T) - s1);
 460    BV_EQ(T, *bv1 & mask, (*bv2 & (mask >> step)) << step);
 461    ++bv1;
 462    if (l <= step) {
 463     mask = BV_MASK_LOWER(T, l);
 464     BV_EQ(T, *bv1 & mask, (*bv2 & (mask << pets)) >> pets);
 465    } else {
 466     ins = (*bv2 & BV_MASK_HIGHER(T, step)) >> pets;
 467     ++bv2;
 468     offset = l % BITS(T);
 469     end    = bv1 + l / BITS(T);
 470     while (bv1 < end) {
 471      BV_EQ(T, *bv1, (*bv2 << step) | ins);
 472      ins = *bv2 >> (BITS(T) - step);
 473      ++bv1; ++bv2;
 474     }
 475     if (offset > step) {
 476      mask = BV_MASK_LOWER(T, offset - step);
 477      BV_EQ(T, *bv1 & ~(~mask << step),
 478               ((*bv2 & mask) << step) | ins);
 479     } else if (offset) {
 480      mask = BV_MASK_LOWER(T, offset);
 481      BV_EQ_MASK(T, *bv1, ins, mask);
 482     }
 483 /*    BV_EQ_LEFT(T, bv1, bv2, l, step); */
 484    }
 485   }
 486
 487  }
 488
 489  return 1;
 490 }
 491 #endif /* INLINE_DEFINE */
 492 #undef T
 493
 494 /* ... Fill ................................................................ */
 495
 496 #define T unsigned char
 497 INLINE_DECLARE(void bv_fill(void *bv_, size_t s, size_t l, unsigned int f))
 498 #ifdef INLINE_DEFINE
 499 {
 500  size_t o, k;
 501  T mask, *bv = (T *) bv_;
 502
 503  if (f)
 504   f = ~0;
 505
 506  bv += s / BITS(T);
 507  o   = s % BITS(T);
 508
 509  mask = BV_MASK_HIGHER(T, BITS(T) - o);
 510  if (o + l <= BITS(T)) {
 511   if (o + l < BITS(T))
 512    mask &= BV_MASK_LOWER(T, o + l);
 513   *bv = (*bv & ~mask) | (f & mask);
 514  } else {
 515   *bv = (*bv & ~mask) | (f & mask);
 516   ++bv;
 517   l -= (BITS(T) - o);
 518   k = l / BITS(T);
 519   o = l % BITS(T);
 520   memset(bv, f, k);
 521   if (o) {
 522    mask = BV_MASK_LOWER(T, o);
 523    bv += k;
 524    *bv = (*bv & ~mask) | (f & mask);
 525   }
 526  }
 527
 528  return;
 529 }
 530 #endif /* INLINE_DEFINE */
 531 #undef T
 532
 533 /* ========================================================================= */
 534
 535 #endif /* BITVECT_H */