]> git.vpit.fr Git - perl/modules/Scalar-Vec-Util.git/blob - bitvect.h
Explicitely require a C compiler
[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 BITS(T) (CHAR_BIT * sizeof(T))
16
17 #define BV_SIZE(I) (((((I) % BITS(BV_UNIT)) != 0) + ((I) / BITS(BV_UNIT))) * sizeof(BV_UNIT))
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 /* ... Test if zero ........................................................ */
336
337 #define T BV_UNIT
338 INLINE_DECLARE(int bv_zero(const void *bv_, size_t s, size_t l))
339 #ifdef INLINE_DEFINE
340 {
341  size_t o;
342  T mask;
343  const T *bv = (const T *) bv_, *end;
344
345  bv += s / BITS(T);
346  o   = s % BITS(T);
347
348  mask = BV_MASK_HIGHER(T, BITS(T) - o);
349  if (o + l <= BITS(T)) {
350   if (o + l < BITS(T))
351    mask &= BV_MASK_LOWER(T, o + l);
352   if (*bv & mask)
353    return 0;
354  } else {
355   if (*bv & mask)
356    return 0;
357   ++bv;
358   l  -= (BITS(T) - o);
359   end = bv + l / BITS(T);
360   for (; bv < end; ++bv) {
361    if (*bv)
362     return 0;
363   }
364   o = l % BITS(T);
365   if (o) {
366    mask = BV_MASK_LOWER(T, o);
367    if (*bv & mask)
368     return 0;
369   }
370  }
371
372  return 1;
373 }
374 #endif /* INLINE_DEFINE */
375 #undef T
376
377 /* ... Compare ............................................................. */
378
379 #define BV_EQ(T, B1, B2) \
380  if (((T) (B1)) != ((T) (B2))) return 0;
381
382 #define BV_EQ_MASK(T, B1, B2, M) BV_EQ(T, (B1) & (M), (B2) & (M))
383
384 #define BV_EQ_LEFT(T, B1, B2, L, B)        \
385  offset = (L) % BITS(T);                   \
386  end    = (B1) + (L) / BITS(T);            \
387  while ((B1) < end) {                      \
388   BV_EQ(T, *(B1), (*(B2) << (B)) | ins);   \
389   ins = *(B2) >> (BITS(T) - (B));          \
390   ++(B1); ++(B2);                          \
391  }                                         \
392  if (offset > (B)) {                       \
393   mask = BV_MASK_LOWER(T, offset - (B));   \
394   BV_EQ(T, *(B1) & ~(~mask << (B)),        \
395            ((*(B2) & mask) << (B)) | ins); \
396  } else if (offset) {                      \
397   mask = BV_MASK_LOWER(T, offset);         \
398   BV_EQ_MASK(T, *(B1), ins, mask);         \
399  }
400
401 #define BV_EQ_RIGHT(T, B1, B2, L, B)                   \
402  offset = (L) % BITS(T);                               \
403  end    = (B2) + (L) / BITS(T) + (offset >= (B));      \
404  while ((B2) < end) {                                  \
405   BV_EQ(T, *(B1), (*(B2) << (BITS(T) - (B))) | ins);   \
406   ins = *(B2) >> (B);                                  \
407   ++(B1); ++(B2);                                      \
408  }                                                     \
409  if (!offset)                                          \
410   offset += BITS(T);                                   \
411  if (offset >= (B)) {                                  \
412   mask = BV_MASK_LOWER(T, offset - (B));               \
413   BV_EQ_MASK(T, *(B1), ins, mask);                     \
414  } else {                                              \
415   mask = BV_MASK_LOWER(T, offset);                     \
416   BV_EQ(T, *(B1) & ~(~mask << (BITS(T) - (B))),        \
417            ((*(B2) & mask) << (BITS(T) - (B))) | ins); \
418  }
419
420 #define T BV_UNIT
421 INLINE_DECLARE(int bv_eq(const void *bv1_, size_t s1, const void *bv2_, size_t s2, size_t l))
422 #ifdef INLINE_DEFINE
423 {
424  size_t offset, step;
425  T ins, mask;
426  const T *bv1 = (const T *) bv1_, *bv2 = (const T *) bv2_, *end;
427
428  bv1 += s1 / BITS(T);
429  s1  %= BITS(T);
430
431  bv2 += s2 / BITS(T);
432  s2  %= BITS(T);
433
434  if (s1 == s2) {
435
436   mask = BV_MASK_HIGHER(T, BITS(T) - s2);
437   if (s2 + l <= BITS(T)) {
438    if (s2 + l < BITS(T)) {
439     mask &= BV_MASK_LOWER(T, s2 + l);
440    }
441    BV_EQ_MASK(T, *bv1, *bv2, mask);
442   } else {
443    int ret;
444    size_t lo, lk;
445    BV_EQ_MASK(T, *bv1, *bv2, mask);
446    ++bv1;
447    ++bv2;
448    l -= (BITS(T) - s2);
449    lo = l % BITS(T);
450    lk = l / BITS(T);
451    if ((ret = memcmp(bv1, bv2, lk * sizeof(T))) != 0)
452     return 0;
453    if (lo) {
454     mask = BV_MASK_LOWER(T, lo);
455     BV_EQ_MASK(T, *bv1, *bv2, mask);
456    }
457   }
458
459  } else if (s1 < s2) {
460
461   step = s2 - s1;
462   mask = BV_MASK_HIGHER(T, BITS(T) - s2);
463   if (s2 + l <= BITS(T)) {
464    if (s2 + l < BITS(T))
465     mask &= BV_MASK_LOWER(T, s2 + l);
466    BV_EQ(T, *bv1 & (mask >> step), (*bv2 & mask) >> step);
467   } else {
468    l -= (BITS(T) - s2);
469    ins = ((*bv2 & mask) >> step) | (*bv1 & BV_MASK_LOWER(T, s1));
470    ++bv2;
471    offset = l % BITS(T);
472    end    = bv2 + l / BITS(T) + (offset >= step);
473    while (bv2 < end) {
474     BV_EQ(T, *bv1, (*bv2 << (BITS(T) - step)) | ins);
475     ins = *bv2 >> step;
476     ++bv1; ++bv2;
477    }
478    if (!offset)
479     offset += BITS(T);
480    if (offset >= step) {
481     mask = BV_MASK_LOWER(T, offset - step);
482     BV_EQ_MASK(T, *bv1, ins, mask);
483    } else {
484     mask = BV_MASK_LOWER(T, offset);
485     BV_EQ(T, *bv1 & ~(~mask << (BITS(T) - step)),
486              ((*bv2 & mask) << (BITS(T) - step)) | ins);
487    }
488 /*   BV_EQ_RIGHT(T, bv1, bv2, l, step); */
489   }
490
491  } else { /* s1 > s2 */
492
493   step = s1 - s2;
494   mask = BV_MASK_HIGHER(T, BITS(T) - s1);
495   if (s1 + l <= BITS(T)) {
496    if (s1 + l < BITS(T))
497     mask &= BV_MASK_LOWER(T, s1 + l);
498    BV_EQ(T, *bv1 & mask, (*bv2 & (mask >> step)) << step);
499   } else {
500    size_t pets = BITS(T) - step;
501    l -= (BITS(T) - s1);
502    BV_EQ(T, *bv1 & mask, (*bv2 & (mask >> step)) << step);
503    ++bv1;
504    if (l <= step) {
505     mask = BV_MASK_LOWER(T, l);
506     BV_EQ(T, *bv1 & mask, (*bv2 & (mask << pets)) >> pets);
507    } else {
508     ins = (*bv2 & BV_MASK_HIGHER(T, step)) >> pets;
509     ++bv2;
510     offset = l % BITS(T);
511     end    = bv1 + l / BITS(T);
512     while (bv1 < end) {
513      BV_EQ(T, *bv1, (*bv2 << step) | ins);
514      ins = *bv2 >> (BITS(T) - step);
515      ++bv1; ++bv2;
516     }
517     if (offset > step) {
518      mask = BV_MASK_LOWER(T, offset - step);
519      BV_EQ(T, *bv1 & ~(~mask << step),
520               ((*bv2 & mask) << step) | ins);
521     } else if (offset) {
522      mask = BV_MASK_LOWER(T, offset);
523      BV_EQ_MASK(T, *bv1, ins, mask);
524     }
525 /*    BV_EQ_LEFT(T, bv1, bv2, l, step); */
526    }
527   }
528
529  }
530
531  return 1;
532 }
533 #endif /* INLINE_DEFINE */
534 #undef T
535
536 /* ... Fill ................................................................ */
537
538 #define T unsigned char
539 INLINE_DECLARE(void bv_fill(void *bv_, size_t s, size_t l, unsigned int f))
540 #ifdef INLINE_DEFINE
541 {
542  size_t o, k;
543  T mask, *bv = (T *) bv_;
544
545  if (f)
546   f = ~0u;
547
548  bv += s / BITS(T);
549  o   = s % BITS(T);
550
551  mask = BV_MASK_HIGHER(T, BITS(T) - o);
552  if (o + l <= BITS(T)) {
553   if (o + l < BITS(T))
554    mask &= BV_MASK_LOWER(T, o + l);
555   *bv = (*bv & ~mask) | (f & mask);
556  } else {
557   *bv = (*bv & ~mask) | (f & mask);
558   ++bv;
559   l -= (BITS(T) - o);
560   k = l / BITS(T);
561   o = l % BITS(T);
562   memset(bv, f, k);
563   if (o) {
564    mask = BV_MASK_LOWER(T, o);
565    bv += k;
566    *bv = (*bv & ~mask) | (f & mask);
567   }
568  }
569
570  return;
571 }
572 #endif /* INLINE_DEFINE */
573 #undef T
574
575 /* ========================================================================= */
576
577 #endif /* BITVECT_H */