]> git.vpit.fr Git - perl/modules/Scalar-Vec-Util.git/blob - bitvect.h
Point the repository to the gitweb instead of the bare repo
[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(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 */