]> git.vpit.fr Git - perl/modules/Scalar-Vec-Util.git/blob - bitvect.h
a62f472af79666e31bd8aa4c3b1e228b6b37642d
[perl/modules/Scalar-Vec-Util.git] / 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 */