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