File Coverage

File:bitvect.h
Coverage:100.0%

linestmtbranpathcondsubtimecode
1
2
3#define BITVECT_H 1
4
5
6
7
8
9
10
11#define INLINE_DECLARE(P) STATIC P
12
13
14#define INLINE_DEFINE
15
16
17
18
19# define BV_UNIT unsigned char
20
21
22
23
24#define BV_SIZE(I) ((((I) % CHAR_BIT) != 0) + ((I) / CHAR_BIT))
25
26
27
28#define BITS(T) (CHAR_BIT * sizeof(T))
29
30
31
32
33#define BV_MASK_LOWER(T, I) (~((~((T) 0)) << (I)))
34
35
36
37#define BV_MASK_HIGHER(T, I) ((~((T) 0)) << (BITS(T) - (I)))
38
39#define BV_DO_ALIGNED_FORWARD(T, A) \
40 mask = BV_MASK_HIGHER(T, BITS(T) - fs); \
41 if (fs + l <= BITS(T)) { \
42  /* Branching is apparently useless, \
43   * but since we can't portably shift \
44   * CHAR_BITS from a char... \
45   * Actually, we only copy up to this */ \
46  if (fs + l < BITS(T)) \
47   mask &= BV_MASK_LOWER(T, fs + l); \
48  *t = (*t & ~mask) | (*f & mask); \
49 } else { \
50  size_t lo, lk; \
51  *t = (*t & ~mask) | (*f & mask); \
52  ++t; \
53  ++f; \
54  l -= (BITS(T) - ts); \
55  lo = l % BITS(T); \
56  lk = l / BITS(T); \
57  BV_##A##_UNIT_ALIGNED(T, t, f, lk); \
58  t += lk; \
59  f += lk; \
60  if (lo) { \
61   mask = BV_MASK_LOWER(T, lo); \
62   *t = (*t & ~mask) | (*f & mask); \
63  } \
64 }
65
66#define BV_DO_ALIGNED_BACKWARD(T, A) \
67 if (fs + l <= BITS(T)) { \
68  mask = BV_MASK_HIGHER(T, BITS(T) - fs); \
69  /* Branching is apparently useless, \
70   * but since we can't portably shift \
71   * CHAR_BITS from a char... \
72   * Actually, we only copy up to this */ \
73  if (fs + l < BITS(T)) \
74   mask &= BV_MASK_LOWER(T, fs + l); \
75  *t = (*t & ~mask) | (*f & mask); \
76 } else { \
77  size_t lo, lk; \
78  l -= (BITS(T) - ts); \
79  lo = l % BITS(T); \
80  lk = l / BITS(T); \
81  ++t; \
82  ++f; \
83  if (lo) { \
84   mask = BV_MASK_LOWER(T, lo); \
85   t[lk] = (t[lk] & ~mask) | (f[lk] & mask); \
86  } \
87  BV_##A##_UNIT_ALIGNED(T, t, f, lk); \
88  mask = BV_MASK_HIGHER(T, BITS(T) - fs); \
89  t[-1] = (t[-1] & ~mask) | (f[-1] & mask); \
90 }
91
92#define BV_DO_LEFT_FORWARD(T, A) \
93 step = ts - fs; \
94 mask = BV_MASK_HIGHER(T, BITS(T) - ts); \
95 if (ts + l <= BITS(T)) { \
96  if (ts + l < BITS(T)) \
97   mask &= BV_MASK_LOWER(T, ts + l); \
98  *t = (*t & ~mask) | ((*f & (mask >> step)) << step); \
99 } else { \
100  size_t pets = BITS(T) - step; \
101  l -= (BITS(T) - ts); \
102  *t = (*t & ~mask) | ((*f & (mask >> step)) << step); \
103  ++t; \
104  if (l <= step) { \
105   mask = BV_MASK_LOWER(T, l); \
106   *t = (*t & ~mask) | ((*f & (mask << pets)) >> pets); \
107  } else { \
108   ins = (*f & BV_MASK_HIGHER(T, step)) >> pets; \
109   ++f; \
110   offset = l % BITS(T); \
111   end = t + l / BITS(T); \
112   while (t < end) { \
113    BV_##A##_UNIT_LEFT_FORWARD(T, t, f, step); \
114    ++t; ++f; \
115   } \
116   if (offset > step) { \
117    mask = BV_MASK_LOWER(T, offset - step); \
118    *t = (*t & (~mask << step)) \
119       | ((*f & mask) << step) \
120       | ins; \
121   } else if (offset) { \
122    mask = BV_MASK_LOWER(T, offset); \
123    *t = (*t & ~mask) | (ins & mask); \
124   } \
125  } \
126 }
127
128#define BV_DO_RIGHT_FORWARD(T, A) \
129 step = fs - ts; \
130 mask = BV_MASK_HIGHER(T, BITS(T) - fs); \
131 if (fs + l <= BITS(T)) { \
132  if (fs + l < BITS(T)) \
133   mask &= BV_MASK_LOWER(T, fs + l); \
134  *t = (*t & ~(mask >> step)) | ((*f & mask) >> step); \
135 } else { \
136  l -= (BITS(T) - fs); \
137  ins = ((*f & mask) >> step) | (*t & BV_MASK_LOWER(T, ts)); \
138  ++f; \
139  offset = l % BITS(T); \
140  end = f + l / BITS(T) + (offset > step); \
141  while (f < end) { \
142   BV_##A##_UNIT_RIGHT_FORWARD(T, t, f, step); \
143   ++t; ++f; \
144  } \
145  if (!offset) \
146   offset += BITS(T); \
147  if (offset > step) { \
148   mask = BV_MASK_LOWER(T, offset - step); \
149   *t = (*t & ~mask) | (ins & mask); \
150  } else { \
151   mask = BV_MASK_LOWER(T, offset); \
152   *t = (*t & (~mask << (BITS(T) - step))) \
153      | ((*f & mask) << (BITS(T) - step)) \
154      | ins; \
155  } \
156 }
157
158#define BV_DO_LEFT_BACKWARD(T, A) \
159 step = ts - fs; \
160 mask = BV_MASK_LOWER(T, BITS(T) - ts); \
161 if (ts + l <= BITS(T)) { \
162  if (ts + l < BITS(T)) \
163   mask &= BV_MASK_HIGHER(T, ts + l); \
164  *t = (*t & ~mask) | ((*f & (mask << step)) >> step); \
165 } else { \
166  size_t pets = BITS(T) - step; \
167  l -= (BITS(T) - ts); \
168  *t = (*t & ~mask) | ((*f & (mask << step)) >> step); \
169  --t; \
170  if (l <= step) { \
171   mask = BV_MASK_HIGHER(T, l); \
172   *t = (*t & ~mask) | ((*f & (mask >> pets)) << pets); \
173  } else { \
174   ins = (*f & BV_MASK_LOWER(T, step)) << pets; \
175   --f; \
176   offset = l % BITS(T); \
177   begin = t - l / BITS(T); \
178   while (t > begin) { \
179    BV_##A##_UNIT_LEFT_BACKWARD(T, t, f, step); \
180    --t; --f; \
181   } \
182   if (offset > step) { \
183    mask = BV_MASK_HIGHER(T, offset - step); \
184    *t = (*t & (~mask >> step)) \
185       | ((*f & mask) >> step) \
186       | ins; \
187   } else if (offset) { \
188    mask = BV_MASK_HIGHER(T, offset); \
189    *t = (*t & ~mask) | (ins & mask); \
190   } \
191  } \
192 }
193
194#define BV_DO_RIGHT_BACKWARD(T, A) \
195 step = fs - ts; \
196 mask = BV_MASK_LOWER(T, BITS(T) - fs); \
197 if (fs + l <= BITS(T)) { \
198  if (fs + l < BITS(T)) \
199   mask &= BV_MASK_HIGHER(T, fs + l); \
200  *t = (*t & ~(mask << step)) | ((*f & mask) << step); \
201 } else { \
202  l -= (BITS(T) - fs); \
203  ins = ((*f & mask) << step); \
204  if (ts) \
205   ins |= (*t & BV_MASK_HIGHER(T, ts)); \
206  --f; \
207  offset = l % BITS(T); \
208  begin = f - l / BITS(T) + (offset <= step); \
209  while (f >= begin) { \
210   BV_##A##_UNIT_RIGHT_BACKWARD(T, t, f, step); \
211   --t; --f; \
212  } \
213  if (!offset) \
214   offset += BITS(T); \
215  if (offset > step) { \
216   mask = BV_MASK_HIGHER(T, offset - step); \
217   *t = (*t & ~mask) | (ins & mask); \
218  } else { \
219   mask = BV_MASK_HIGHER(T, offset); \
220   *t = (*t & (~mask >> (BITS(T) - step))) \
221      | ((*f & mask) >> (BITS(T) - step)) \
222      | ins; \
223  } \
224 }
225
226
227
228
229
230#define BV_COPY_UNIT_ALIGNED(X, T, F, L) memcpy((T), (F), (L) * sizeof(X))
231
232
233
234
235
236
237#define BV_COPY_UNIT_LEFT_FORWARD(X, T, F, B) \
238 *(T) = (*(F) << (B)) | ins; \
239 ins = *(F) >> (BITS(X) - (B));
240
241
242
243
244
245
246#define BV_COPY_UNIT_RIGHT_FORWARD(X, T, F, B) \
247 *(T) = (*(F) << (BITS(X) - (B))) | ins; \
248 ins = *(F) >> (B);
249
250
251
252#define T BV_UNIT
253
254STATIC void
255bv_copy (void *t_, size_t ts, const void *f_, size_t fs, size_t l)
256
11172
{
257  size_t offset, step;
258
11172
  unsigned char ins, mask, *t = (unsigned char *) t_;
259
11172
  const unsigned char *f = (const unsigned char *) f_, *end;
260
261
11172
  t += ts / (CHAR_BIT * sizeof (unsigned char));
262
11172
  ts %= (CHAR_BIT * sizeof (unsigned char));
263
264
11172
  f += fs / (CHAR_BIT * sizeof (unsigned char));
265
11172
  fs %= (CHAR_BIT * sizeof (unsigned char));
266
267
11172
  if (ts == fs)
268    {
269
1904
      mask =
270        ((~((unsigned char) 0)) <<
271         ((CHAR_BIT * sizeof (unsigned char)) -
272          ((CHAR_BIT * sizeof (unsigned char)) - fs)));
273
1904
      if (fs + l <= (CHAR_BIT * sizeof (unsigned char)))
274        {
275
970
          if (fs + l < (CHAR_BIT * sizeof (unsigned char)))
276
947
            mask &= (~((~((unsigned char) 0)) << (fs + l)));
277
970
          *t = (*t & ~mask) | (*f & mask);
278        }
279      else
280        {
281          size_t lo, lk;
282
934
          *t = (*t & ~mask) | (*f & mask);
283
934
          ++t;
284
934
          ++f;
285
934
          l -= ((CHAR_BIT * sizeof (unsigned char)) - ts);
286
934
          lo = l % (CHAR_BIT * sizeof (unsigned char));
287
934
          lk = l / (CHAR_BIT * sizeof (unsigned char));
288
934
          memcpy ((t), (f), (lk) * sizeof (unsigned char));
289
934
          t += lk;
290
934
          f += lk;
291
934
          if (lo)
292            {
293
866
              mask = (~((~((unsigned char) 0)) << (lo)));
294
866
              *t = (*t & ~mask) | (*f & mask);
295            }
296        }
297      ;
298    }
299
9268
  else if (ts < fs)
300    {
301
4634
      step = fs - ts;
302
4634
      mask =
303        ((~((unsigned char) 0)) <<
304         ((CHAR_BIT * sizeof (unsigned char)) -
305          ((CHAR_BIT * sizeof (unsigned char)) - fs)));
306
4634
      if (fs + l <= (CHAR_BIT * sizeof (unsigned char)))
307        {
308
1481
          if (fs + l < (CHAR_BIT * sizeof (unsigned char)))
309
1141
            mask &= (~((~((unsigned char) 0)) << (fs + l)));
310
1481
          *t = (*t & ~(mask >> step)) | ((*f & mask) >> step);
311        }
312      else
313        {
314
3153
          l -= ((CHAR_BIT * sizeof (unsigned char)) - fs);
315
3153
          ins =
316            ((*f & mask) >> step) | (*t &
317                                     (~((~((unsigned char) 0)) << (ts))));
318
3153
          ++f;
319
3153
          offset = l % (CHAR_BIT * sizeof (unsigned char));
320
3153
          end = f + l / (CHAR_BIT * sizeof (unsigned char)) + (offset > step);
321
10123
          while (f < end)
322            {
323
3817
              *(t) =
324                (*(f) << ((CHAR_BIT * sizeof (unsigned char)) - (step))) |
325                ins;
326
3817
              ins = *(f) >> (step);
327              ;
328
3817
              ++t;
329
3817
              ++f;
330            }
331
3153
          if (!offset)
332
261
            offset += (CHAR_BIT * sizeof (unsigned char));
333
3153
          if (offset > step)
334            {
335
1287
              mask = (~((~((unsigned char) 0)) << (offset - step)));
336
1287
              *t = (*t & ~mask) | (ins & mask);
337            }
338          else
339            {
340
1866
              mask = (~((~((unsigned char) 0)) << (offset)));
341
1866
              *t =
342                (*t & (~mask << ((CHAR_BIT * sizeof (unsigned char)) - step)))
343                | ((*f & mask) <<
344                   ((CHAR_BIT * sizeof (unsigned char)) - step)) | ins;
345            }
346        }
347      ;
348    }
349  else
350    {
351
4634
      step = ts - fs;
352
4634
      mask =
353        ((~((unsigned char) 0)) <<
354         ((CHAR_BIT * sizeof (unsigned char)) -
355          ((CHAR_BIT * sizeof (unsigned char)) - ts)));
356
4634
      if (ts + l <= (CHAR_BIT * sizeof (unsigned char)))
357        {
358
1481
          if (ts + l < (CHAR_BIT * sizeof (unsigned char)))
359
1141
            mask &= (~((~((unsigned char) 0)) << (ts + l)));
360
1481
          *t = (*t & ~mask) | ((*f & (mask >> step)) << step);
361        }
362      else
363        {
364
3153
          size_t pets = (CHAR_BIT * sizeof (unsigned char)) - step;
365
3153
          l -= ((CHAR_BIT * sizeof (unsigned char)) - ts);
366
3153
          *t = (*t & ~mask) | ((*f & (mask >> step)) << step);
367
3153
          ++t;
368
3153
          if (l <= step)
369            {
370
1015
              mask = (~((~((unsigned char) 0)) << (l)));
371
1015
              *t = (*t & ~mask) | ((*f & (mask << pets)) >> pets);
372            }
373          else
374            {
375
2138
              ins =
376                (*f &
377                 ((~((unsigned char) 0)) <<
378                  ((CHAR_BIT * sizeof (unsigned char)) - (step)))) >> pets;
379
2138
              ++f;
380
2138
              offset = l % (CHAR_BIT * sizeof (unsigned char));
381
2138
              end = t + l / (CHAR_BIT * sizeof (unsigned char));
382
7067
              while (t < end)
383                {
384
2791
                  *(t) = (*(f) << (step)) | ins;
385
2791
                  ins =
386                    *(f) >> ((CHAR_BIT * sizeof (unsigned char)) - (step));
387                  ;
388
2791
                  ++t;
389
2791
                  ++f;
390                }
391
2138
              if (offset > step)
392                {
393
1026
                  mask = (~((~((unsigned char) 0)) << (offset - step)));
394
1026
                  *t = (*t & (~mask << step)) | ((*f & mask) << step) | ins;
395                }
396
1112
              else if (offset)
397                {
398
851
                  mask = (~((~((unsigned char) 0)) << (offset)));
399
851
                  *t = (*t & ~mask) | (ins & mask);
400                }
401            }
402        }
403      ;
404    }
405
406  return;
407}
408
409
410#undef T
411
412
413
414
415
416#define BV_MOVE_UNIT_ALIGNED(X, T, F, L) memmove((T), (F), (L) * sizeof(X))
417
418
419
420
421
422
423#define BV_MOVE_UNIT_LEFT_FORWARD(X, T, F, B) \
424 tmp = *(F) >> (BITS(X) - (B)); \
425 *(T) = (*(F) << (B)) | ins; \
426 ins = tmp;
427
428
429
430
431
432
433#define BV_MOVE_UNIT_RIGHT_FORWARD(X, T, F, B) \
434 tmp = *(F) >> (B); \
435 *(T) = (*(F) << (BITS(X) - (B))) | ins; \
436 ins = tmp;
437
438
439
440
441
442
443#define BV_MOVE_UNIT_LEFT_BACKWARD(X, T, F, B) \
444 tmp = *(F) << (BITS(X) - (B)); \
445 *(T) = (*(F) >> (B)) | ins; \
446 ins = tmp;
447
448
449
450
451
452
453#define BV_MOVE_UNIT_RIGHT_BACKWARD(X, T, F, B) \
454 tmp = *(F) << (B); \
455 *(T) = (*(F) >> (BITS(X) - (B))) | ins; \
456 ins = tmp;
457
458#define BV_MOVE_INIT_REVERSE(T, V, VS) \
459 z = (VS) + l; \
460 (VS) = z % BITS(T); \
461 if ((VS) > 0) { \
462  (V) = bv + (z / BITS(T)); \
463  (VS) = BITS(T) - (VS); \
464 } else { \
465  /* z >= BITS(T) because l > 0 */ \
466  (V) = bv + (z / BITS(T)) - 1; \
467 }
468
469
470
471#define T BV_UNIT
472
473STATIC void
474bv_move (void *bv_, size_t ts, size_t fs, size_t l)
475
11323
{
476  size_t to, fo, offset, step;
477
11323
  unsigned char ins, tmp, mask, *bv = (unsigned char *) bv_, *t, *f;
478  const unsigned char *begin, *end;
479
480
11323
  if (ts == fs)
481
1131
    return;
482
483
10192
  to = ts % (CHAR_BIT * sizeof (unsigned char));
484
10192
  fo = fs % (CHAR_BIT * sizeof (unsigned char));
485
486
10192
  if (ts < fs)
487    {
488
5088
      t = bv + ts / (CHAR_BIT * sizeof (unsigned char));
489
5088
      ts = to;
490
5088
      f = bv + fs / (CHAR_BIT * sizeof (unsigned char));
491
5088
      fs = fo;
492
5088
      if (ts == fs)
493        {
494
429
          mask =
495            ((~((unsigned char) 0)) <<
496             ((CHAR_BIT * sizeof (unsigned char)) -
497              ((CHAR_BIT * sizeof (unsigned char)) - fs)));
498
429
          if (fs + l <= (CHAR_BIT * sizeof (unsigned char)))
499            {
500
14
              if (fs + l < (CHAR_BIT * sizeof (unsigned char)))
501
7
                mask &= (~((~((unsigned char) 0)) << (fs + l)));
502
14
              *t = (*t & ~mask) | (*f & mask);
503            }
504          else
505            {
506              size_t lo, lk;
507
415
              *t = (*t & ~mask) | (*f & mask);
508
415
              ++t;
509
415
              ++f;
510
415
              l -= ((CHAR_BIT * sizeof (unsigned char)) - ts);
511
415
              lo = l % (CHAR_BIT * sizeof (unsigned char));
512
415
              lk = l / (CHAR_BIT * sizeof (unsigned char));
513
415
              memmove ((t), (f), (lk) * sizeof (unsigned char));
514
415
              t += lk;
515
415
              f += lk;
516
415
              if (lo)
517                {
518
351
                  mask = (~((~((unsigned char) 0)) << (lo)));
519
351
                  *t = (*t & ~mask) | (*f & mask);
520                }
521            }
522          ;
523        }
524
4659
      else if (ts < fs)
525        {
526
2840
          step = fs - ts;
527
2840
          mask =
528            ((~((unsigned char) 0)) <<
529             ((CHAR_BIT * sizeof (unsigned char)) -
530              ((CHAR_BIT * sizeof (unsigned char)) - fs)));
531
2840
          if (fs + l <= (CHAR_BIT * sizeof (unsigned char)))
532            {
533
256
              if (fs + l < (CHAR_BIT * sizeof (unsigned char)))
534
200
                mask &= (~((~((unsigned char) 0)) << (fs + l)));
535
256
              *t = (*t & ~(mask >> step)) | ((*f & mask) >> step);
536            }
537          else
538            {
539
2584
              l -= ((CHAR_BIT * sizeof (unsigned char)) - fs);
540
2584
              ins =
541                ((*f & mask) >> step) | (*t &
542                                         (~((~((unsigned char) 0)) << (ts))));
543
2584
              ++f;
544
2584
              offset = l % (CHAR_BIT * sizeof (unsigned char));
545
2584
              end =
546                f + l / (CHAR_BIT * sizeof (unsigned char)) + (offset > step);
547
14765
              while (f < end)
548                {
549
9597
                  tmp = *(f) >> (step);
550
9597
                  *(t) =
551                    (*(f) << ((CHAR_BIT * sizeof (unsigned char)) - (step))) |
552                    ins;
553
9597
                  ins = tmp;
554                  ;
555
9597
                  ++t;
556
9597
                  ++f;
557                }
558
2584
              if (!offset)
559
302
                offset += (CHAR_BIT * sizeof (unsigned char));
560
2584
              if (offset > step)
561                {
562
1540
                  mask = (~((~((unsigned char) 0)) << (offset - step)));
563
1540
                  *t = (*t & ~mask) | (ins & mask);
564                }
565              else
566                {
567
1044
                  mask = (~((~((unsigned char) 0)) << (offset)));
568
1044
                  *t =
569                    (*t &
570                     (~mask << ((CHAR_BIT * sizeof (unsigned char)) - step)))
571                    | ((*f & mask) <<
572                       ((CHAR_BIT * sizeof (unsigned char)) - step)) | ins;
573                }
574            }
575          ;
576        }
577      else
578        {
579
1819
          step = ts - fs;
580
1819
          mask =
581            ((~((unsigned char) 0)) <<
582             ((CHAR_BIT * sizeof (unsigned char)) -
583              ((CHAR_BIT * sizeof (unsigned char)) - ts)));
584
1819
          if (ts + l <= (CHAR_BIT * sizeof (unsigned char)))
585            {
586
76
              if (ts + l < (CHAR_BIT * sizeof (unsigned char)))
587
31
                mask &= (~((~((unsigned char) 0)) << (ts + l)));
588
76
              *t = (*t & ~mask) | ((*f & (mask >> step)) << step);
589            }
590          else
591            {
592
1743
              size_t pets = (CHAR_BIT * sizeof (unsigned char)) - step;
593
1743
              l -= ((CHAR_BIT * sizeof (unsigned char)) - ts);
594
1743
              *t = (*t & ~mask) | ((*f & (mask >> step)) << step);
595
1743
              ++t;
596
1743
              if (l <= step)
597                {
598
140
                  mask = (~((~((unsigned char) 0)) << (l)));
599
140
                  *t = (*t & ~mask) | ((*f & (mask << pets)) >> pets);
600                }
601              else
602                {
603
1603
                  ins =
604                    (*f &
605                     ((~((unsigned char) 0)) <<
606                      ((CHAR_BIT * sizeof (unsigned char)) -
607                       (step)))) >> pets;
608
1603
                  ++f;
609
1603
                  offset = l % (CHAR_BIT * sizeof (unsigned char));
610
1603
                  end = t + l / (CHAR_BIT * sizeof (unsigned char));
611
8428
                  while (t < end)
612                    {
613
5222
                      tmp =
614                        *(f) >> ((CHAR_BIT * sizeof (unsigned char)) -
615                                 (step));
616
5222
                      *(t) = (*(f) << (step)) | ins;
617
5222
                      ins = tmp;
618                      ;
619
5222
                      ++t;
620
5222
                      ++f;
621                    }
622
1603
                  if (offset > step)
623                    {
624
651
                      mask = (~((~((unsigned char) 0)) << (offset - step)));
625
651
                      *t =
626                        (*t & (~mask << step)) | ((*f & mask) << step) | ins;
627                    }
628
952
                  else if (offset)
629                    {
630
756
                      mask = (~((~((unsigned char) 0)) << (offset)));
631
756
                      *t = (*t & ~mask) | (ins & mask);
632                    }
633                }
634            }
635          ;
636        }
637    }
638
5104
  else if (to == fo)
639    {
640
442
      t = bv + ts / (CHAR_BIT * sizeof (unsigned char));
641
442
      ts = to;
642
442
      f = bv + fs / (CHAR_BIT * sizeof (unsigned char));
643
442
      fs = fo;
644
442
      if (fs + l <= (CHAR_BIT * sizeof (unsigned char)))
645        {
646
15
          mask =
647            ((~((unsigned char) 0)) <<
648             ((CHAR_BIT * sizeof (unsigned char)) -
649              ((CHAR_BIT * sizeof (unsigned char)) - fs)));
650
15
          if (fs + l < (CHAR_BIT * sizeof (unsigned char)))
651
7
            mask &= (~((~((unsigned char) 0)) << (fs + l)));
652
15
          *t = (*t & ~mask) | (*f & mask);
653        }
654      else
655        {
656          size_t lo, lk;
657
427
          l -= ((CHAR_BIT * sizeof (unsigned char)) - ts);
658
427
          lo = l % (CHAR_BIT * sizeof (unsigned char));
659
427
          lk = l / (CHAR_BIT * sizeof (unsigned char));
660
427
          ++t;
661
427
          ++f;
662
427
          if (lo)
663            {
664
351
              mask = (~((~((unsigned char) 0)) << (lo)));
665
351
              t[lk] = (t[lk] & ~mask) | (f[lk] & mask);
666            }
667
427
          memmove ((t), (f), (lk) * sizeof (unsigned char));
668
427
          mask =
669            ((~((unsigned char) 0)) <<
670             ((CHAR_BIT * sizeof (unsigned char)) -
671              ((CHAR_BIT * sizeof (unsigned char)) - fs)));
672
427
          t[-1] = (t[-1] & ~mask) | (f[-1] & mask);
673        }
674      ;
675    }
676  else
677    {
678      size_t z;
679
4662
      z = (ts) + l;
680
4662
      (ts) = z % (CHAR_BIT * sizeof (unsigned char));
681
4662
      if ((ts) > 0)
682        {
683
4078
          (t) = bv + (z / (CHAR_BIT * sizeof (unsigned char)));
684
4078
          (ts) = (CHAR_BIT * sizeof (unsigned char)) - (ts);
685        }
686      else
687        {
688
584
          (t) = bv + (z / (CHAR_BIT * sizeof (unsigned char))) - 1;
689        }
690      ;
691
4662
      z = (fs) + l;
692
4662
      (fs) = z % (CHAR_BIT * sizeof (unsigned char));
693
4662
      if ((fs) > 0)
694        {
695
4109
          (f) = bv + (z / (CHAR_BIT * sizeof (unsigned char)));
696
4109
          (fs) = (CHAR_BIT * sizeof (unsigned char)) - (fs);
697        }
698      else
699        {
700
553
          (f) = bv + (z / (CHAR_BIT * sizeof (unsigned char))) - 1;
701        }
702      ;
703
4662
      if (ts < fs)
704        {
705
2695
          step = fs - ts;
706
2695
          mask =
707            (~
708             ((~((unsigned char) 0)) <<
709              ((CHAR_BIT * sizeof (unsigned char)) - fs)));
710
2695
          if (fs + l <= (CHAR_BIT * sizeof (unsigned char)))
711            {
712
259
              if (fs + l < (CHAR_BIT * sizeof (unsigned char)))
713
144
                mask &=
714                  ((~((unsigned char) 0)) <<
715                   ((CHAR_BIT * sizeof (unsigned char)) - (fs + l)));
716
259
              *t = (*t & ~(mask << step)) | ((*f & mask) << step);
717            }
718          else
719            {
720
2436
              l -= ((CHAR_BIT * sizeof (unsigned char)) - fs);
721
2436
              ins = ((*f & mask) << step);
722
2436
              if (ts)
723
1909
                ins |=
724                  (*t &
725                   ((~((unsigned char) 0)) <<
726                    ((CHAR_BIT * sizeof (unsigned char)) - (ts))));
727
2436
              --f;
728
2436
              offset = l % (CHAR_BIT * sizeof (unsigned char));
729
2436
              begin =
730                f - l / (CHAR_BIT * sizeof (unsigned char)) + (offset <=
731                                                               step);
732
14122
              while (f >= begin)
733                {
734
9250
                  tmp = *(f) << (step);
735
9250
                  *(t) =
736                    (*(f) >> ((CHAR_BIT * sizeof (unsigned char)) - (step))) |
737                    ins;
738
9250
                  ins = tmp;
739                  ;
740
9250
                  --t;
741
9250
                  --f;
742                }
743
2436
              if (!offset)
744
832
                offset += (CHAR_BIT * sizeof (unsigned char));
745
2436
              if (offset > step)
746                {
747
1540
                  mask =
748                    ((~((unsigned char) 0)) <<
749                     ((CHAR_BIT * sizeof (unsigned char)) - (offset - step)));
750
1540
                  *t = (*t & ~mask) | (ins & mask);
751                }
752              else
753                {
754
896
                  mask =
755                    ((~((unsigned char) 0)) <<
756                     ((CHAR_BIT * sizeof (unsigned char)) - (offset)));
757
896
                  *t =
758                    (*t &
759                     (~mask >> ((CHAR_BIT * sizeof (unsigned char)) - step)))
760                    | ((*f & mask) >>
761                       ((CHAR_BIT * sizeof (unsigned char)) - step)) | ins;
762                }
763            }
764          ;
765        }
766      else
767        {
768
1967
          step = ts - fs;
769
1967
          mask =
770            (~
771             ((~((unsigned char) 0)) <<
772              ((CHAR_BIT * sizeof (unsigned char)) - ts)));
773
1967
          if (ts + l <= (CHAR_BIT * sizeof (unsigned char)))
774            {
775
76
              if (ts + l < (CHAR_BIT * sizeof (unsigned char)))
776
38
                mask &=
777                  ((~((unsigned char) 0)) <<
778                   ((CHAR_BIT * sizeof (unsigned char)) - (ts + l)));
779
76
              *t = (*t & ~mask) | ((*f & (mask << step)) >> step);
780            }
781          else
782            {
783
1891
              size_t pets = (CHAR_BIT * sizeof (unsigned char)) - step;
784
1891
              l -= ((CHAR_BIT * sizeof (unsigned char)) - ts);
785
1891
              *t = (*t & ~mask) | ((*f & (mask << step)) >> step);
786
1891
              --t;
787
1891
              if (l <= step)
788                {
789
163
                  mask =
790                    ((~((unsigned char) 0)) <<
791                     ((CHAR_BIT * sizeof (unsigned char)) - (l)));
792
163
                  *t = (*t & ~mask) | ((*f & (mask >> pets)) << pets);
793                }
794              else
795                {
796
1728
                  ins = (*f & (~((~((unsigned char) 0)) << (step)))) << pets;
797
1728
                  --f;
798
1728
                  offset = l % (CHAR_BIT * sizeof (unsigned char));
799
1728
                  begin = t - l / (CHAR_BIT * sizeof (unsigned char));
800
9072
                  while (t > begin)
801                    {
802
5616
                      tmp =
803                        *(f) << ((CHAR_BIT * sizeof (unsigned char)) -
804                                 (step));
805
5616
                      *(t) = (*(f) >> (step)) | ins;
806
5616
                      ins = tmp;
807                      ;
808
5616
                      --t;
809
5616
                      --f;
810                    }
811
1728
                  if (offset > step)
812                    {
813
604
                      mask =
814                        ((~((unsigned char) 0)) <<
815                         ((CHAR_BIT * sizeof (unsigned char)) -
816                          (offset - step)));
817
604
                      *t =
818                        (*t & (~mask >> step)) | ((*f & mask) >> step) | ins;
819                    }
820
1124
                  else if (offset)
821                    {
822
881
                      mask =
823                        ((~((unsigned char) 0)) <<
824                         ((CHAR_BIT * sizeof (unsigned char)) - (offset)));
825
881
                      *t = (*t & ~mask) | (ins & mask);
826                    }
827                }
828            }
829          ;
830        }
831    }
832
833
10192
  return;
834}
835
836
837#undef T
838
839
840
841
842
843
844#define BV_EQ(T, B1, B2) \
845 if (((T) (B1)) != ((T) (B2))) return 0;
846
847
848
849#define BV_EQ_MASK(T, B1, B2, M) BV_EQ(T, (B1) & (M), (B2) & (M))
850
851#define BV_EQ_LEFT(T, B1, B2, L, B) \
852 offset = (L) % BITS(T); \
853 end = (B1) + (L) / BITS(T); \
854 while ((B1) < end) { \
855  BV_EQ(T, *(B1), (*(B2) << (B)) | ins); \
856  ins = *(B2) >> (BITS(T) - (B)); \
857  ++(B1); ++(B2); \
858 } \
859 if (offset > (B)) { \
860  mask = BV_MASK_LOWER(T, offset - (B)); \
861  BV_EQ(T, *(B1) & ~(~mask << (B)), \
862           ((*(B2) & mask) << (B)) | ins); \
863 } else if (offset) { \
864  mask = BV_MASK_LOWER(T, offset); \
865  BV_EQ_MASK(T, *(B1), ins, mask); \
866 }
867
868#define BV_EQ_RIGHT(T, B1, B2, L, B) \
869 offset = (L) % BITS(T); \
870 end = (B2) + (L) / BITS(T) + (offset >= (B)); \
871 while ((B2) < end) { \
872  BV_EQ(T, *(B1), (*(B2) << (BITS(T) - (B))) | ins); \
873  ins = *(B2) >> (B); \
874  ++(B1); ++(B2); \
875 } \
876 if (!offset) \
877  offset += BITS(T); \
878 if (offset >= (B)) { \
879  mask = BV_MASK_LOWER(T, offset - (B)); \
880  BV_EQ_MASK(T, *(B1), ins, mask); \
881 } else { \
882  mask = BV_MASK_LOWER(T, offset); \
883  BV_EQ(T, *(B1) & ~(~mask << (BITS(T) - (B))), \
884           ((*(B2) & mask) << (BITS(T) - (B))) | ins); \
885 }
886
887
888
889#define T BV_UNIT
890
891STATIC int
892bv_eq (const void *bv1_, size_t s1, const void *bv2_, size_t s2, size_t l)
893
1717
{
894  size_t offset, step;
895  unsigned char ins, mask;
896
1717
  const unsigned char *bv1 = (const unsigned char *) bv1_, *bv2 =
897
1717
    (const unsigned char *) bv2_, *end;
898
899
1717
  bv1 += s1 / (CHAR_BIT * sizeof (unsigned char));
900
1717
  s1 %= (CHAR_BIT * sizeof (unsigned char));
901
902
1717
  bv2 += s2 / (CHAR_BIT * sizeof (unsigned char));
903
1717
  s2 %= (CHAR_BIT * sizeof (unsigned char));
904
905
1717
  if (s1 == s2)
906    {
907
908
446
      mask =
909        ((~((unsigned char) 0)) <<
910         ((CHAR_BIT * sizeof (unsigned char)) -
911          ((CHAR_BIT * sizeof (unsigned char)) - s2)));
912
446
      if (s2 + l <= (CHAR_BIT * sizeof (unsigned char)))
913        {
914
40
          if (s2 + l < (CHAR_BIT * sizeof (unsigned char)))
915            {
916
33
              mask &= (~((~((unsigned char) 0)) << (s2 + l)));
917            }
918
40
          if (((unsigned char) ((*bv1) & (mask))) !=
919              ((unsigned char) ((*bv2) & (mask))))
920
24
            return 0;
921          ;
922        }
923      else
924        {
925          int ret;
926          size_t lo, lk;
927
406
          if (((unsigned char) ((*bv1) & (mask))) !=
928              ((unsigned char) ((*bv2) & (mask))))
929
118
            return 0;
930          ;
931
288
          ++bv1;
932
288
          ++bv2;
933
288
          l -= ((CHAR_BIT * sizeof (unsigned char)) - s2);
934
288
          lo = l % (CHAR_BIT * sizeof (unsigned char));
935
288
          lk = l / (CHAR_BIT * sizeof (unsigned char));
936
288
          if ((ret = memcmp (bv1, bv2, lk * sizeof (unsigned char))) != 0)
937
14
            return 0;
938
274
          if (lo)
939            {
940
252
              mask = (~((~((unsigned char) 0)) << (lo)));
941
252
              if (((unsigned char) ((*bv1) & (mask))) !=
942                  ((unsigned char) ((*bv2) & (mask))))
943
14
                return 0;
944              ;
945            }
946        }
947
948    }
949
1271
  else if (s1 < s2)
950    {
951
952
637
      step = s2 - s1;
953
637
      mask =
954        ((~((unsigned char) 0)) <<
955         ((CHAR_BIT * sizeof (unsigned char)) -
956          ((CHAR_BIT * sizeof (unsigned char)) - s2)));
957
637
      if (s2 + l <= (CHAR_BIT * sizeof (unsigned char)))
958        {
959
28
          if (s2 + l < (CHAR_BIT * sizeof (unsigned char)))
960
18
            mask &= (~((~((unsigned char) 0)) << (s2 + l)));
961
28
          if (((unsigned char) (*bv1 & (mask >> step))) !=
962              ((unsigned char) ((*bv2 & mask) >> step)))
963
19
            return 0;
964          ;
965        }
966      else
967        {
968
609
          l -= ((CHAR_BIT * sizeof (unsigned char)) - s2);
969
609
          ins =
970            ((*bv2 & mask) >> step) | (*bv1 &
971                                       (~((~((unsigned char) 0)) << (s1))));
972
609
          ++bv2;
973
609
          offset = l % (CHAR_BIT * sizeof (unsigned char));
974
609
          end =
975            bv2 + l / (CHAR_BIT * sizeof (unsigned char)) + (offset >= step);
976
2822
          while (bv2 < end)
977            {
978
1811
              if (((unsigned char) (*bv1)) !=
979                  ((unsigned
980                    char) ((*bv2 <<
981                            ((CHAR_BIT * sizeof (unsigned char)) -
982                             step)) | ins)))
983
207
                return 0;
984              ;
985
1604
              ins = *bv2 >> step;
986
1604
              ++bv1;
987
1604
              ++bv2;
988            }
989
402
          if (!offset)
990
51
            offset += (CHAR_BIT * sizeof (unsigned char));
991
402
          if (offset >= step)
992            {
993
188
              mask = (~((~((unsigned char) 0)) << (offset - step)));
994
188
              if (((unsigned char) ((*bv1) & (mask))) !=
995                  ((unsigned char) ((ins) & (mask))))
996
94
                return 0;
997              ;
998            }
999          else
1000            {
1001
214
              mask = (~((~((unsigned char) 0)) << (offset)));
1002
214
              if (((unsigned char) (*bv1 &
1003                                    ~(~mask <<
1004                                      ((CHAR_BIT * sizeof (unsigned char)) -
1005                                       step)))) !=
1006                  ((unsigned
1007                    char) (((*bv2 & mask) <<
1008                            ((CHAR_BIT * sizeof (unsigned char)) -
1009                             step)) | ins)))
1010
126
                return 0;
1011              ;
1012
1013            }
1014
1015        }
1016
1017    }
1018  else
1019    {
1020
1021
634
      step = s1 - s2;
1022
634
      mask =
1023        ((~((unsigned char) 0)) <<
1024         ((CHAR_BIT * sizeof (unsigned char)) -
1025          ((CHAR_BIT * sizeof (unsigned char)) - s1)));
1026
634
      if (s1 + l <= (CHAR_BIT * sizeof (unsigned char)))
1027        {
1028
34
          if (s1 + l < (CHAR_BIT * sizeof (unsigned char)))
1029
24
            mask &= (~((~((unsigned char) 0)) << (s1 + l)));
1030
34
          if (((unsigned char) (*bv1 & mask)) !=
1031              ((unsigned char) ((*bv2 & (mask >> step)) << step)))
1032
25
            return 0;
1033          ;
1034        }
1035      else
1036        {
1037
600
          size_t pets = (CHAR_BIT * sizeof (unsigned char)) - step;
1038
600
          l -= ((CHAR_BIT * sizeof (unsigned char)) - s1);
1039
600
          if (((unsigned char) (*bv1 & mask)) !=
1040              ((unsigned char) ((*bv2 & (mask >> step)) << step)))
1041
248
            return 0;
1042          ;
1043
352
          ++bv1;
1044
352
          if (l <= step)
1045            {
1046
18
              mask = (~((~((unsigned char) 0)) << (l)));
1047
18
              if (((unsigned char) (*bv1 & mask)) !=
1048                  ((unsigned char) ((*bv2 & (mask << pets)) >> pets)))
1049
4
                return 0;
1050              ;
1051            }
1052          else
1053            {
1054
334
              ins =
1055                (*bv2 &
1056                 ((~((unsigned char) 0)) <<
1057                  ((CHAR_BIT * sizeof (unsigned char)) - (step)))) >> pets;
1058
334
              ++bv2;
1059
334
              offset = l % (CHAR_BIT * sizeof (unsigned char));
1060
334
              end = bv1 + l / (CHAR_BIT * sizeof (unsigned char));
1061
1809
              while (bv1 < end)
1062                {
1063
1162
                  if (((unsigned char) (*bv1)) !=
1064                      ((unsigned char) ((*bv2 << step) | ins)))
1065
21
                    return 0;
1066                  ;
1067
1141
                  ins = *bv2 >> ((CHAR_BIT * sizeof (unsigned char)) - step);
1068
1141
                  ++bv1;
1069
1141
                  ++bv2;
1070                }
1071
313
              if (offset > step)
1072                {
1073
168
                  mask = (~((~((unsigned char) 0)) << (offset - step)));
1074
168
                  if (((unsigned char) (*bv1 & ~(~mask << step))) !=
1075                      ((unsigned char) (((*bv2 & mask) << step) | ins)))
1076
119
                    return 0;
1077                  ;
1078
1079                }
1080
145
              else if (offset)
1081                {
1082
124
                  mask = (~((~((unsigned char) 0)) << (offset)));
1083
124
                  if (((unsigned char) ((*bv1) & (mask))) !=
1084                      ((unsigned char) ((ins) & (mask))))
1085
27
                    return 0;
1086                  ;
1087                }
1088
1089            }
1090        }
1091
1092    }
1093
1094
657
  return 1;
1095}
1096
1097
1098#undef T
1099
1100
1101
1102
1103
1104#define T unsigned char
1105
1106STATIC void
1107bv_fill (void *bv_, size_t s, size_t l, unsigned int f)
1108
2750
{
1109  size_t o, k;
1110
2750
  unsigned char mask, *bv = (unsigned char *) bv_;
1111
1112
2750
  if (f)
1113
1479
    f = ~0;
1114
1115
2750
  bv += s / (CHAR_BIT * sizeof (unsigned char));
1116
2750
  o = s % (CHAR_BIT * sizeof (unsigned char));
1117
1118
2750
  mask =
1119    ((~((unsigned char) 0)) <<
1120     ((CHAR_BIT * sizeof (unsigned char)) -
1121      ((CHAR_BIT * sizeof (unsigned char)) - o)));
1122
2750
  if (o + l <= (CHAR_BIT * sizeof (unsigned char)))
1123    {
1124
303
      if (o + l < (CHAR_BIT * sizeof (unsigned char)))
1125
238
        mask &= (~((~((unsigned char) 0)) << (o + l)));
1126
303
      *bv = (*bv & ~mask) | (f & mask);
1127    }
1128  else
1129    {
1130
2447
      *bv = (*bv & ~mask) | (f & mask);
1131
2447
      ++bv;
1132
2447
      l -= ((CHAR_BIT * sizeof (unsigned char)) - o);
1133
2447
      k = l / (CHAR_BIT * sizeof (unsigned char));
1134
2447
      o = l % (CHAR_BIT * sizeof (unsigned char));
1135
2447
      memset (bv, f, k);
1136
2447
      if (o)
1137        {
1138
2144
          mask = (~((~((unsigned char) 0)) << (o)));
1139
2144
          bv += k;
1140
2144
          *bv = (*bv & ~mask) | (f & mask);
1141        }
1142    }
1143
1144  return;
1145}
1146
1147
1148#undef T