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