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  if (!l)
 234   return;
 235
 236  t  += ts / BITS(T);
 237  ts %= BITS(T);
 238
 239  f  += fs / BITS(T);
 240  fs %= BITS(T);
 241
 242  if (ts == fs) {
 243   BV_DO_ALIGNED_FORWARD(T, COPY);
 244  } else if (ts < fs) {
 245   BV_DO_RIGHT_FORWARD(T, COPY);
 246  } else { /* ts > fs */
 247   BV_DO_LEFT_FORWARD(T, COPY);
 248  }
 249
 250  return;
 251 }
 252 #endif /* INLINE_DEFINE */
 253 #undef T
 254
 255 /* ... Move ................................................................ */
 256
 257 #define BV_MOVE_UNIT_ALIGNED(X, T, F, L) memmove((T), (F), (L) * sizeof(X))
 258
 259 #define BV_MOVE_UNIT_LEFT_FORWARD(X, T, F, B) \
 260  tmp  = *(F) >> (BITS(X) - (B));              \
 261  *(T) = (*(F) << (B)) | ins;                  \
 262  ins  = tmp;
 263
 264 #define BV_MOVE_UNIT_RIGHT_FORWARD(X, T, F, B) \
 265  tmp  = *(F) >> (B);                           \
 266  *(T) = (*(F) << (BITS(X) - (B))) | ins;       \
 267  ins  = tmp;
 268
 269 #define BV_MOVE_UNIT_LEFT_BACKWARD(X, T, F, B) \
 270  tmp  = *(F) << (BITS(X) - (B));               \
 271  *(T) = (*(F) >> (B)) | ins;                   \
 272  ins  = tmp;
 273
 274 #define BV_MOVE_UNIT_RIGHT_BACKWARD(X, T, F, B) \
 275  tmp  = *(F) << (B);                            \
 276  *(T) = (*(F) >> (BITS(X) - (B))) | ins;        \
 277  ins  = tmp;
 278
 279 #define BV_MOVE_INIT_REVERSE(T, V, VS) \
 280  z     = (VS) + l;                     \
 281  (VS)  = z % BITS(T);                  \
 282  if ((VS) > 0) {                       \
 283   (V)  = bv + (z / BITS(T));           \
 284   (VS) = BITS(T) - (VS);               \
 285  } else {                              \
 286   /* z >= BITS(T) because l > 0 */     \
 287   (V)  = bv + (z / BITS(T)) - 1;       \
 288  }
 289
 290 #define T BV_UNIT
 291 INLINE_DECLARE(void bv_move(void *bv_, size_t ts, size_t fs, size_t l))
 292 #ifdef INLINE_DEFINE
 293 {
 294  size_t to, fo, offset, step;
 295  T ins, tmp, mask, *bv = (T *) bv_, *t, *f;
 296  const T *begin, *end;
 297
 298  if (!l || ts == fs)
 299   return;
 300
 301  to = ts % BITS(T);
 302  fo = fs % BITS(T);
 303
 304  if (ts < fs) {
 305   t  = bv + ts / BITS(T);
 306   ts = to;
 307   f  = bv + fs / BITS(T);
 308   fs = fo;
 309   if (ts == fs) {
 310    BV_DO_ALIGNED_FORWARD(T, MOVE);
 311   } else if (ts < fs) {
 312    BV_DO_RIGHT_FORWARD(T, MOVE);
 313   } else { /* ts > fs */
 314    BV_DO_LEFT_FORWARD(T, MOVE);
 315   }
 316  } else if (to == fo) {
 317   t  = bv + ts / BITS(T);
 318   ts = to;
 319   f  = bv + fs / BITS(T);
 320   fs = fo;
 321   BV_DO_ALIGNED_BACKWARD(T, MOVE);
 322  } else { /* ts > fs */
 323   size_t z;
 324   BV_MOVE_INIT_REVERSE(T, t, ts);
 325   BV_MOVE_INIT_REVERSE(T, f, fs);
 326   if (ts < fs) {
 327    BV_DO_RIGHT_BACKWARD(T, MOVE);
 328   } else { /* ts > fs */
 329    BV_DO_LEFT_BACKWARD(T, MOVE);
 330   }
 331  }
 332
 333  return;
 334 }
 335 #endif /* INLINE_DEFINE */
 336 #undef T
 337
 338 /* ... Compare ............................................................. */
 339
 340 #define BV_EQ(T, B1, B2) \
 341  if (((T) (B1)) != ((T) (B2))) return 0;
 342
 343 #define BV_EQ_MASK(T, B1, B2, M) BV_EQ(T, (B1) & (M), (B2) & (M))
 344
 345 #define BV_EQ_LEFT(T, B1, B2, L, B)        \
 346  offset = (L) % BITS(T);                   \
 347  end    = (B1) + (L) / BITS(T);            \
 348  while ((B1) < end) {                      \
 349   BV_EQ(T, *(B1), (*(B2) << (B)) | ins);   \
 350   ins = *(B2) >> (BITS(T) - (B));          \
 351   ++(B1); ++(B2);                          \
 352  }                                         \
 353  if (offset > (B)) {                       \
 354   mask = BV_MASK_LOWER(T, offset - (B));   \
 355   BV_EQ(T, *(B1) & ~(~mask << (B)),        \
 356            ((*(B2) & mask) << (B)) | ins); \
 357  } else if (offset) {                      \
 358   mask = BV_MASK_LOWER(T, offset);         \
 359   BV_EQ_MASK(T, *(B1), ins, mask);         \
 360  }
 361
 362 #define BV_EQ_RIGHT(T, B1, B2, L, B)                   \
 363  offset = (L) % BITS(T);                               \
 364  end    = (B2) + (L) / BITS(T) + (offset >= (B));      \
 365  while ((B2) < end) {                                  \
 366   BV_EQ(T, *(B1), (*(B2) << (BITS(T) - (B))) | ins);   \
 367   ins = *(B2) >> (B);                                  \
 368   ++(B1); ++(B2);                                      \
 369  }                                                     \
 370  if (!offset)                                          \
 371   offset += BITS(T);                                   \
 372  if (offset >= (B)) {                                  \
 373   mask = BV_MASK_LOWER(T, offset - (B));               \
 374   BV_EQ_MASK(T, *(B1), ins, mask);                     \
 375  } else {                                              \
 376   mask = BV_MASK_LOWER(T, offset);                     \
 377   BV_EQ(T, *(B1) & ~(~mask << (BITS(T) - (B))),        \
 378            ((*(B2) & mask) << (BITS(T) - (B))) | ins); \
 379  }
 380
 381 #define T BV_UNIT
 382 INLINE_DECLARE(int bv_eq(const void *bv1_, size_t s1, const void *bv2_, size_t s2, size_t l))
 383 #ifdef INLINE_DEFINE
 384 {
 385  size_t offset, step;
 386  T ins, mask;
 387  const T *bv1 = (const T *) bv1_, *bv2 = (const T *) bv2_, *end;
 388
 389  bv1 += s1 / BITS(T);
 390  s1  %= BITS(T);
 391
 392  bv2 += s2 / BITS(T);
 393  s2  %= BITS(T);
 394
 395  if (s1 == s2) {
 396
 397   mask = BV_MASK_HIGHER(T, BITS(T) - s2);
 398   if (s2 + l <= BITS(T)) {
 399    if (s2 + l < BITS(T)) {
 400     mask &= BV_MASK_LOWER(T, s2 + l);
 401    }
 402    BV_EQ_MASK(T, *bv1, *bv2, mask);
 403   } else {
 404    int ret;
 405    size_t lo, lk;
 406    BV_EQ_MASK(T, *bv1, *bv2, mask);
 407    ++bv1;
 408    ++bv2;
 409    l -= (BITS(T) - s2);
 410    lo = l % BITS(T);
 411    lk = l / BITS(T);
 412    if ((ret = memcmp(bv1, bv2, lk * sizeof(T))) != 0)
 413     return 0;
 414    if (lo) {
 415     mask = BV_MASK_LOWER(T, lo);
 416     BV_EQ_MASK(T, *bv1, *bv2, mask);
 417    }
 418   }
 419
 420  } else if (s1 < s2) {
 421
 422   step = s2 - s1;
 423   mask = BV_MASK_HIGHER(T, BITS(T) - s2);
 424   if (s2 + l <= BITS(T)) {
 425    if (s2 + l < BITS(T))
 426     mask &= BV_MASK_LOWER(T, s2 + l);
 427    BV_EQ(T, *bv1 & (mask >> step), (*bv2 & mask) >> step);
 428   } else {
 429    l -= (BITS(T) - s2);
 430    ins = ((*bv2 & mask) >> step) | (*bv1 & BV_MASK_LOWER(T, s1));
 431    ++bv2;
 432    offset = l % BITS(T);
 433    end    = bv2 + l / BITS(T) + (offset >= step);
 434    while (bv2 < end) {
 435     BV_EQ(T, *bv1, (*bv2 << (BITS(T) - step)) | ins);
 436     ins = *bv2 >> step;
 437     ++bv1; ++bv2;
 438    }
 439    if (!offset)
 440     offset += BITS(T);
 441    if (offset >= step) {
 442     mask = BV_MASK_LOWER(T, offset - step);
 443     BV_EQ_MASK(T, *bv1, ins, mask);
 444    } else {
 445     mask = BV_MASK_LOWER(T, offset);
 446     BV_EQ(T, *bv1 & ~(~mask << (BITS(T) - step)),
 447              ((*bv2 & mask) << (BITS(T) - step)) | ins);
 448    }
 449 /*   BV_EQ_RIGHT(T, bv1, bv2, l, step); */
 450   }
 451
 452  } else { /* s1 > s2 */
 453
 454   step = s1 - s2;
 455   mask = BV_MASK_HIGHER(T, BITS(T) - s1);
 456   if (s1 + l <= BITS(T)) {
 457    if (s1 + l < BITS(T))
 458     mask &= BV_MASK_LOWER(T, s1 + l);
 459    BV_EQ(T, *bv1 & mask, (*bv2 & (mask >> step)) << step);
 460   } else {
 461    size_t pets = BITS(T) - step;
 462    l -= (BITS(T) - s1);
 463    BV_EQ(T, *bv1 & mask, (*bv2 & (mask >> step)) << step);
 464    ++bv1;
 465    if (l <= step) {
 466     mask = BV_MASK_LOWER(T, l);
 467     BV_EQ(T, *bv1 & mask, (*bv2 & (mask << pets)) >> pets);
 468    } else {
 469     ins = (*bv2 & BV_MASK_HIGHER(T, step)) >> pets;
 470     ++bv2;
 471     offset = l % BITS(T);
 472     end    = bv1 + l / BITS(T);
 473     while (bv1 < end) {
 474      BV_EQ(T, *bv1, (*bv2 << step) | ins);
 475      ins = *bv2 >> (BITS(T) - step);
 476      ++bv1; ++bv2;
 477     }
 478     if (offset > step) {
 479      mask = BV_MASK_LOWER(T, offset - step);
 480      BV_EQ(T, *bv1 & ~(~mask << step),
 481               ((*bv2 & mask) << step) | ins);
 482     } else if (offset) {
 483      mask = BV_MASK_LOWER(T, offset);
 484      BV_EQ_MASK(T, *bv1, ins, mask);
 485     }
 486 /*    BV_EQ_LEFT(T, bv1, bv2, l, step); */
 487    }
 488   }
 489
 490  }
 491
 492  return 1;
 493 }
 494 #endif /* INLINE_DEFINE */
 495 #undef T
 496
 497 /* ... Fill ................................................................ */
 498
 499 #define T unsigned char
 500 INLINE_DECLARE(void bv_fill(void *bv_, size_t s, size_t l, unsigned int f))
 501 #ifdef INLINE_DEFINE
 502 {
 503  size_t o, k;
 504  T mask, *bv = (T *) bv_;
 505
 506  if (!l)
 507   return;
 508
 509  if (f)
 510   f = ~0;
 511
 512  bv += s / BITS(T);
 513  o   = s % BITS(T);
 514
 515  mask = BV_MASK_HIGHER(T, BITS(T) - o);
 516  if (o + l <= BITS(T)) {
 517   if (o + l < BITS(T))
 518    mask &= BV_MASK_LOWER(T, o + l);
 519   *bv = (*bv & ~mask) | (f & mask);
 520  } else {
 521   *bv = (*bv & ~mask) | (f & mask);
 522   ++bv;
 523   l -= (BITS(T) - o);
 524   k = l / BITS(T);
 525   o = l % BITS(T);
 526   memset(bv, f, k);
 527   if (o) {
 528    mask = BV_MASK_LOWER(T, o);
 529    bv += k;
 530    *bv = (*bv & ~mask) | (f & mask);
 531   }
 532  }
 533
 534  return;
 535 }
 536 #endif /* INLINE_DEFINE */
 537 #undef T
 538
 539 /* ========================================================================= */
 540
 541 #endif /* BITVECT_H */