1 /*
2 Copyright (C) 1988 Free Software Foundation
3 written by Doug Lea (dl@rocky.oswego.edu)
4
5 This file is part of GNU CC.
6
7 GNU CC is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY. No author or distributor
9 accepts responsibility to anyone for the consequences of using it
10 or for whether it serves any particular purpose or works at all,
11 unless he says so in writing. Refer to the GNU CC General Public
12 License for full details.
13
14 Everyone is granted permission to copy, modify and redistribute
15 GNU CC, but only under the conditions described in the
16 GNU CC General Public License. A copy of this license is
17 supposed to have been given to you along with GNU CC so you
18 can know your rights and responsibilities. It should be in a
19 file named COPYING. Among other things, the copyright notice
20 and this notice must be preserved on all copies.
21 */
22
23 /*
24 BitString class implementation
25 */
26
27 #ifdef __GNUG__
28 #pragma implementation
29 #endif
30 #include <BitString.h>
31 #include <std.h>
32 #include <values.h>
33 #include <Obstack.h>
34 #include <AllocRing.h>
35 #include <new.h>
36
error(const char * msg) const37 volatile void BitString::error(const char* msg) const
38 {
39 (*lib_error_handler)("BitString", msg);
40 }
41
42 // globals
43
44 BitStrRep _nilBitStrRep = { 0, 1, {0} };
45
46 BitString _nil_BitString;
47
48 #define MINBitStrRep_SIZE 8
49 #define MAXBitStrRep_SIZE ((1 << (SHORTBITS - 1)) - 1)
50
51 #ifndef MALLOC_MIN_OVERHEAD
52 #define MALLOC_MIN_OVERHEAD 4
53 #endif
54
55 #define ONES ((unsigned short)(~0L))
56 #define MAXBIT (1 << (BITSTRBITS - 1))
57
58 /*
59 * bit manipulation utilities
60 */
61
62 // break things up into .s indices and positions
63
BitStr_len(int l)64 inline static int BitStr_len(int l)
65 {
66 return (unsigned)(l) / BITSTRBITS + 1;
67 }
68
69
70 // mask out low bits
71
lmask(int p)72 static inline unsigned short lmask(int p)
73 {
74 if (p <= 0)
75 return ONES;
76 else
77 return ONES << p;
78 }
79
80 // mask out high bits
81
rmask(int p)82 static inline unsigned short rmask(int p)
83 {
84 int s = BITSTRBITS - 1 - p;
85 if (s <= 0)
86 return ONES;
87 else
88 return ONES >> s;
89 }
90
91
92 // mask out unused bits in last word of rep
93
check_last(BitStrRep * r)94 inline static void check_last(BitStrRep* r)
95 {
96 r->s[r->len / BITSTRBITS] &= ONES >> (BITSTRBITS - (r->len & (BITSTRBITS - 1)));
97 }
98
99 // merge bits from next word
100
borrow_hi(const unsigned short a[],int ind,int maxind,int p)101 static inline unsigned short borrow_hi(const unsigned short a[], int ind,
102 int maxind, int p)
103 {
104 if (ind < maxind)
105 return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p));
106 else
107 return (a[ind] >> p);
108 }
109
110 // merge bits from prev word
111
borrow_lo(const unsigned short a[],int ind,int minind,int p)112 static inline unsigned short borrow_lo(const unsigned short a[], int ind,
113 int minind, int p)
114 {
115 if (ind > minind)
116 return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1));
117 else
118 return (a[ind] << (BITSTRBITS - 1 - p));
119 }
120
121 // same with bounds check (for masks shorter than patterns)
122
safe_borrow_hi(const unsigned short a[],int ind,int maxind,int p)123 static inline unsigned short safe_borrow_hi(const unsigned short a[], int ind,
124 int maxind, int p)
125 {
126 if (ind > maxind)
127 return 0;
128 else if (ind == maxind)
129 return(a[ind] >> p);
130 else
131 return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p));
132 }
133
134
safe_borrow_lo(const unsigned short a[],int ind,int minind,int p)135 static inline unsigned short safe_borrow_lo(const unsigned short a[], int ind,
136 int minind, int p)
137 {
138 if (ind < minind)
139 return 0;
140 else if (ind == minind)
141 return (a[ind] << (BITSTRBITS - 1 - p));
142 else
143 return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1));
144 }
145
146 // copy bits from a word boundary
147
bit_copy(const unsigned short * ss,unsigned short * ds,int nbits)148 static inline void bit_copy(const unsigned short* ss, unsigned short* ds,
149 int nbits)
150 {
151 if (ss != ds)
152 {
153 int n = (unsigned)(nbits) / BITSTRBITS;
154 if (n > 0) bcopy((void*)ss, (void*)ds, n * sizeof(short));
155 unsigned short m = ONES << (nbits & (BITSTRBITS - 1));
156 ds[n] = (ss[n] & ~m) | (ds[n] & m);
157 }
158 }
159
160 // clear bits from a word boundary
161
bit_clear(unsigned short * ds,int nbits)162 static inline void bit_clear(unsigned short* ds, int nbits)
163 {
164 int n = (unsigned)(nbits) / BITSTRBITS;
165 if (n > 0) bzero((void*)ds, n * sizeof(short));
166 ds[n] &= ONES << (nbits & (BITSTRBITS - 1));
167 }
168
169
170
171 // Copy ss from starts to fences-1 into ds starting at startd.
172 // This will work even if ss & ds overlap.
173 // The g++ optimizer does very good things with the messy shift expressions!
174
bit_transfer(const unsigned short * ss,int starts,int fences,unsigned short * ds,int startd)175 static void bit_transfer(const unsigned short* ss, int starts, int fences,
176 unsigned short* ds, int startd)
177 {
178 if (starts >= fences || ss == 0 || (ss == ds && starts == startd))
179 return;
180
181 int sind = BitStr_index(starts);
182 int spos = BitStr_pos(starts);
183 int dind = BitStr_index(startd);
184 int dpos = BitStr_pos(startd);
185
186 if (spos == 0 && dpos == 0)
187 {
188 bit_copy(&ss[sind], &ds[dind], fences - starts);
189 return;
190 }
191
192 int ends = fences - 1;
193 int endsind = BitStr_index(ends);
194 int endspos = BitStr_pos(ends);
195 int endd = startd + (ends - starts);
196 int enddind = BitStr_index(endd);
197 int enddpos = BitStr_pos(endd);
198
199 if (dind == enddind)
200 {
201 if (sind == endsind)
202 ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) |
203 (ONES << (enddpos + 1)))) |
204 (((ss[sind] >> spos) << dpos) &
205 ~((ONES >> (BITSTRBITS - dpos)) |
206 (ONES << (enddpos + 1))));
207 else
208 ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) |
209 (ONES << (enddpos + 1)))) |
210 ((((ss[sind] >> spos) |
211 (ss[sind+1] << (BITSTRBITS - spos)))
212 << dpos) &
213 ~((ONES >> (BITSTRBITS - dpos)) |
214 (ONES << (enddpos + 1))));
215 return;
216 }
217 else if (sind == endsind)
218 {
219 unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) |
220 (((ss[sind] << (BITSTRBITS - 1 - endspos)) >>
221 (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
222 ds[dind] = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) |
223 (((ss[sind] >> spos) << dpos) & ~(ONES >> (BITSTRBITS - dpos)));
224 ds[enddind] = saveend;
225 return;
226 }
227
228 unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) |
229 ((((ss[endsind] << (BITSTRBITS - 1 - endspos)) |
230 (ss[endsind-1] >> (endspos + 1))) >>
231 (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
232 unsigned short savestart = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) |
233 ((((ss[sind] >> spos) | (ss[sind+1] << (BITSTRBITS - spos))) << dpos)
234 & ~(ONES >> (BITSTRBITS - dpos)));
235
236
237 if (ds != ss || startd < starts)
238 {
239 int pos = spos - dpos;
240 if (pos < 0)
241 pos += BITSTRBITS;
242 else
243 ++sind;
244
245 for (;;) // lag by one in case of overlaps
246 {
247 if (dind == enddind - 1)
248 {
249 ds[dind] = savestart;
250 ds[enddind] = saveend;
251 return;
252 }
253 else
254 {
255 unsigned short tmp = ss[sind] >> pos;
256 if (++sind <= endsind) tmp |= ss[sind] << (BITSTRBITS - pos);
257 ds[dind++] = savestart;
258 savestart = tmp;
259 }
260 }
261 }
262 else
263 {
264 int pos = endspos - enddpos;
265 if (pos <= 0)
266 {
267 pos += BITSTRBITS;
268 --endsind;
269 }
270 for (;;)
271 {
272 if (enddind == dind + 1)
273 {
274 ds[enddind] = saveend;
275 ds[dind] = savestart;
276 return;
277 }
278 else
279 {
280 unsigned short tmp = ss[endsind] << (BITSTRBITS - pos);
281 if (--endsind >= sind) tmp |= ss[endsind] >> pos;
282 ds[enddind--] = saveend;
283 saveend = tmp;
284 }
285 }
286 }
287 }
288
289 // allocate a new rep; pad to near a power of two
290
BSnew(int newlen)291 inline static BitStrRep* BSnew(int newlen)
292 {
293 unsigned int siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(short)
294 + MALLOC_MIN_OVERHEAD;
295 unsigned int allocsiz = MINBitStrRep_SIZE;;
296 while (allocsiz < siz) allocsiz <<= 1;
297 allocsiz -= MALLOC_MIN_OVERHEAD;
298 if (allocsiz >= MAXBitStrRep_SIZE * sizeof(short))
299 (*lib_error_handler)("BitString", "Requested length out of range");
300
301 BitStrRep* rep = (BitStrRep *) new char[allocsiz];
302 bzero(rep, allocsiz);
303 rep->sz = (allocsiz - sizeof(BitStrRep) + sizeof(short)) / sizeof(short);
304 return rep;
305 }
306
BStr_alloc(BitStrRep * old,const unsigned short * src,int startpos,int endp,int newlen)307 BitStrRep* BStr_alloc(BitStrRep* old, const unsigned short* src,
308 int startpos, int endp, int newlen)
309 {
310 if (old == &_nilBitStrRep) old = 0;
311 if (newlen < 0) newlen = 0;
312 int news = BitStr_len(newlen);
313 BitStrRep* rep;
314 if (old == 0 || news > old->sz)
315 rep = BSnew(newlen);
316 else
317 rep = old;
318 rep->len = newlen;
319
320 if (src != 0 && endp > 0 && (src != rep->s || startpos > 0))
321 bit_transfer(src, startpos, endp, rep->s, 0);
322
323 check_last(rep);
324
325 if (old != rep && old != 0) delete old;
326
327 return rep;
328 }
329
BStr_resize(BitStrRep * old,int newlen)330 BitStrRep* BStr_resize(BitStrRep* old, int newlen)
331 {
332 BitStrRep* rep;
333 if (newlen < 0) newlen = 0;
334 int news = BitStr_len(newlen);
335 if (old == 0 || old == &_nilBitStrRep)
336 {
337 rep = BSnew(newlen);
338 }
339 else if (news > old->sz)
340 {
341 rep = BSnew(newlen);
342 bcopy(old->s, rep->s, BitStr_len(old->len) * sizeof(short));
343 delete old;
344 }
345 else
346 rep = old;
347
348 rep->len = newlen;
349 check_last(rep);
350 return rep;
351 }
352
BStr_copy(BitStrRep * old,const BitStrRep * src)353 BitStrRep* BStr_copy(BitStrRep* old, const BitStrRep* src)
354 {
355 BitStrRep* rep;
356 if (old == src && old != &_nilBitStrRep) return old;
357 if (old == &_nilBitStrRep) old = 0;
358 if (src == &_nilBitStrRep) src = 0;
359 if (src == 0)
360 {
361 if (old == 0)
362 rep = BSnew(0);
363 else
364 rep = old;
365 rep->len = 0;
366 }
367 else
368 {
369 int newlen = src->len;
370 int news = BitStr_len(newlen);
371 if (old == 0 || news > old->sz)
372 {
373 rep = BSnew(newlen);
374 if (old != 0) delete old;
375 }
376 else
377 rep = old;
378
379 bcopy(src->s, rep->s, news * sizeof(short));
380 rep->len = newlen;
381 }
382 check_last(rep);
383 return rep;
384 }
385
386
operator ==(const BitString & x,const BitString & y)387 int operator == (const BitString& x, const BitString& y)
388 {
389 return x.rep->len == y.rep->len &&
390 bcmp((void*)x.rep->s, (void*)y.rep->s,
391 BitStr_len(x.rep->len) * sizeof(short)) == 0;
392 }
393
operator <=(const BitString & x,const BitString & y)394 int operator <= (const BitString& x, const BitString& y)
395 {
396 unsigned int xl = x.rep->len;
397 unsigned int yl = y.rep->len;
398 if (xl > yl)
399 return 0;
400
401 const unsigned short* xs = x.rep->s;
402 const unsigned short* topx = &(xs[BitStr_len(xl)]);
403 const unsigned short* ys = y.rep->s;
404
405 while (xs < topx)
406 {
407 unsigned short a = *xs++;
408 unsigned short b = *ys++;
409 if ((a | b) != b)
410 return 0;
411 }
412 return 1;
413 }
414
operator <(const BitString & x,const BitString & y)415 int operator < (const BitString& x, const BitString& y)
416 {
417 unsigned short xl = x.rep->len;
418 unsigned short yl = y.rep->len;
419 if (xl > yl)
420 return 0;
421
422 const unsigned short* xs = x.rep->s;
423 const unsigned short* ys = y.rep->s;
424 const unsigned short* topx = &(xs[BitStr_len(xl)]);
425 const unsigned short* topy = &(ys[BitStr_len(yl)]);
426 int one_diff = 0;
427 while (xs < topx)
428 {
429 unsigned short a = *xs++;
430 unsigned short b = *ys++;
431 unsigned short c = a | b;
432 if (c != b)
433 return 0;
434 else if (c != a)
435 one_diff = 1;
436 }
437 if (one_diff)
438 return 1;
439 else
440 {
441 while (ys < topy)
442 if (*ys++ != 0)
443 return 1;
444 return 0;
445 }
446 }
447
lcompare(const BitString & x,const BitString & y)448 int lcompare(const BitString& x, const BitString& y)
449 {
450 unsigned int xl = x.rep->len;
451 unsigned int yl = y.rep->len;
452
453 const unsigned short* xs = x.rep->s;
454 const unsigned short* topx = &(xs[BitStr_len(xl)]);
455 const unsigned short* ys = y.rep->s;
456 const unsigned short* topy = &(ys[BitStr_len(yl)]);
457
458 while (xs < topx && ys < topy)
459 {
460 unsigned short a = *xs++;
461 unsigned short b = *ys++;
462 if (a != b)
463 {
464 unsigned short mask = 1;
465 for (;;)
466 {
467 unsigned short abit = (a & mask) != 0;
468 unsigned short bbit = (b & mask) != 0;
469 int diff = abit - bbit;
470 if (diff != 0)
471 return diff;
472 else
473 mask <<= 1;
474 }
475 }
476 }
477 return xl - yl;
478 }
479
count(unsigned int b) const480 int BitString::count(unsigned int b) const
481 {
482 check_last(rep);
483 int xwds = BitStr_len(rep->len);
484 int xlast = BitStr_pos(rep->len);
485 int l = 0;
486 const unsigned short* s = rep->s;
487 const unsigned short* tops = &(s[xwds - 1]);
488 unsigned short a;
489 int i;
490 if (b != 0)
491 {
492 while (s < tops)
493 {
494 a = *s++;
495 for (i = 0; i < BITSTRBITS && a != 0; ++i)
496 {
497 if (a & 1)
498 ++l;
499 a >>= 1;
500 }
501 }
502 a = *s;
503 for (i = 0; i < xlast && a != 0; ++i)
504 {
505 if (a & 1)
506 ++l;
507 a >>= 1;
508 }
509 }
510 else
511 {
512 unsigned short maxbit = 1 << (BITSTRBITS - 1);
513 while (s < tops)
514 {
515 a = *s++;
516 for (i = 0; i < BITSTRBITS; ++i)
517 {
518 if ((a & maxbit) == 0)
519 ++l;
520 a <<= 1;
521 }
522 }
523 maxbit = 1 << (xlast - 1);
524 a = *s;
525 for (i = 0; i < xlast; ++i)
526 {
527 if ((a & maxbit) == 0)
528 ++l;
529 a <<= 1;
530 }
531 }
532 return l;
533 }
534
535
cmpl(const BitStrRep * src,BitStrRep * r)536 BitStrRep* cmpl(const BitStrRep* src, BitStrRep* r)
537 {
538 r = BStr_copy(r, src);
539 unsigned short* rs = r->s;
540 unsigned short* topr = &(rs[BitStr_len(r->len)]);
541 while (rs < topr)
542 {
543 unsigned short cmp = ~(*rs);
544 *rs++ = cmp;
545 }
546 check_last(r);
547 return r;
548 }
549
550
and(const BitStrRep * x,const BitStrRep * y,BitStrRep * r)551 BitStrRep* and(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
552 {
553 int xrsame = x == r;
554 int yrsame = y == r;
555
556 unsigned int xl = x->len;
557 unsigned int yl = y->len;
558 unsigned int rl = (xl <= yl)? xl : yl;
559
560 r = BStr_resize(r, rl);
561
562 unsigned short* rs = r->s;
563 unsigned short* topr = &(rs[BitStr_len(rl)]);
564 const unsigned short* xs = (xrsame)? rs : x->s;
565 const unsigned short* ys = (yrsame)? rs : y->s;
566
567 while (rs < topr) *rs++ = *xs++ & *ys++;
568 check_last(r);
569 return r;
570 }
571
or(const BitStrRep * x,const BitStrRep * y,BitStrRep * r)572 BitStrRep* or(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
573 {
574 unsigned int xl = x->len;
575 unsigned int yl = y->len;
576 unsigned int rl = (xl >= yl)? xl : yl;
577 int xrsame = x == r;
578 int yrsame = y == r;
579
580 r = BStr_resize(r, rl);
581
582 unsigned short* rs = r->s;
583 const unsigned short* xs = (xrsame)? rs : x->s;
584 const unsigned short* topx = &(xs[BitStr_len(xl)]);
585 const unsigned short* ys = (yrsame)? rs : y->s;
586 const unsigned short* topy = &(ys[BitStr_len(yl)]);
587
588 if (xl <= yl)
589 {
590 while (xs < topx) *rs++ = *xs++ | *ys++;
591 if (rs != ys) while (ys < topy) *rs++ = *ys++;
592 }
593 else
594 {
595 while (ys < topy) *rs++ = *xs++ | *ys++;
596 if (rs != xs) while (xs < topx) *rs++ = *xs++;
597 }
598 check_last(r);
599 return r;
600 }
601
602
xor(const BitStrRep * x,const BitStrRep * y,BitStrRep * r)603 BitStrRep* xor(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
604 {
605 unsigned int xl = x->len;
606 unsigned int yl = y->len;
607 unsigned int rl = (xl >= yl)? xl : yl;
608 int xrsame = x == r;
609 int yrsame = y == r;
610
611 r = BStr_resize(r, rl);
612
613 unsigned short* rs = r->s;
614 const unsigned short* xs = (xrsame)? rs : x->s;
615 const unsigned short* topx = &(xs[BitStr_len(xl)]);
616 const unsigned short* ys = (yrsame)? rs : y->s;
617 const unsigned short* topy = &(ys[BitStr_len(yl)]);
618
619 if (xl <= yl)
620 {
621 while (xs < topx) *rs++ = *xs++ ^ *ys++;
622 if (rs != ys) while (ys < topy) *rs++ = *ys++;
623 }
624 else
625 {
626 while (ys < topy) *rs++ = *xs++ ^ *ys++;
627 if (rs != xs) while (xs < topx) *rs++ = *xs++;
628 }
629 check_last(r);
630 return r;
631 }
632
633
diff(const BitStrRep * x,const BitStrRep * y,BitStrRep * r)634 BitStrRep* diff(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
635 {
636 unsigned int xl = x->len;
637 unsigned int yl = y->len;
638 int xrsame = x == y;
639 int yrsame = y == r;
640
641 r = BStr_resize(r, xl);
642
643 unsigned short* rs = r->s;
644 const unsigned short* xs = (xrsame)? rs : x->s;
645 const unsigned short* topx = &(xs[BitStr_len(xl)]);
646 const unsigned short* ys = (yrsame)? rs : y->s;
647 const unsigned short* topy = &(ys[BitStr_len(yl)]);
648
649 if (xl <= yl)
650 {
651 while (xs < topx) *rs++ = *xs++ & ~(*ys++);
652 }
653 else
654 {
655 while (ys < topy) *rs++ = *xs++ & ~(*ys++);
656 if (rs != xs) while (xs < topx) *rs++ = *xs++;
657 }
658 check_last(r);
659 return r;
660 }
661
662
cat(const BitStrRep * x,const BitStrRep * y,BitStrRep * r)663 BitStrRep* cat(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
664 {
665 unsigned int xl = x->len;
666 unsigned int yl = y->len;
667 unsigned int rl = xl + yl;
668 int xrsame = x == r;
669 int yrsame = y == r;
670
671 if (yrsame)
672 {
673 if (xrsame)
674 {
675 r = BStr_resize(r, rl);
676 bit_transfer(r->s, 0, yl, r->s, xl);
677 }
678 else
679 {
680 BitStrRep* tmp = BStr_copy(0, y);
681 r = BStr_resize(r, rl);
682 bit_copy(x->s, r->s, xl);
683 bit_transfer(tmp->s, 0, yl, r->s, xl);
684 delete tmp;
685 }
686 }
687 else
688 {
689 r = BStr_resize(r, rl);
690 if (!xrsame) bit_copy(x->s, r->s, xl);
691 bit_transfer(y->s, 0, yl, r->s, xl);
692 }
693 check_last(r);
694 return r;
695 }
696
cat(const BitStrRep * x,unsigned int bit,BitStrRep * r)697 BitStrRep* cat(const BitStrRep* x, unsigned int bit, BitStrRep* r)
698 {
699 unsigned int xl = x->len;
700 int xrsame = x == r;
701 r = BStr_resize(r, xl+1);
702 if (!xrsame) bit_copy(x->s, r->s, xl);
703 if (bit)
704 r->s[BitStr_index(xl)] |= (1 << (BitStr_pos(xl)));
705 else
706 r->s[BitStr_index(xl)] &= ~(1 << (BitStr_pos(xl)));
707 check_last(r);
708 return r;
709 }
710
lshift(const BitStrRep * x,int s,BitStrRep * r)711 BitStrRep* lshift(const BitStrRep* x, int s, BitStrRep* r)
712 {
713 int xrsame = x == r;
714 int xl = x->len;
715 int rl = xl + s;
716 if (s == 0)
717 r = BStr_copy(r, x);
718 else if (rl <= 0)
719 {
720 r = BStr_resize(r, 0);
721 r->len = 0;
722 r->s[0] = 0;
723 }
724 else if (s > 0)
725 {
726 r = BStr_resize(r, rl);
727 const unsigned short* xs = (xrsame)? r->s : x->s;
728 bit_transfer(xs, 0, xl, r->s, s);
729 bit_clear(r->s, s);
730 }
731 else if (xrsame)
732 {
733 r = BStr_resize(r, xl);
734 r->len = rl;
735 bit_transfer(r->s, -s, xl, r->s, 0);
736 }
737 else
738 {
739 r = BStr_resize(r, rl);
740 bit_transfer(x->s, -s, xl, r->s, 0);
741 }
742 check_last(r);
743 return r;
744 }
745
746
set(int p)747 void BitString::set(int p)
748 {
749 if (p < 0) error("Illegal bit index");
750 if (p >= rep->len) rep = BStr_resize(rep, p + 1);
751 rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
752 }
753
assign(int p,unsigned int bit)754 void BitString::assign(int p, unsigned int bit)
755 {
756 if (p < 0) error("Illegal bit index");
757 if (p >= rep->len) rep = BStr_resize(rep, p + 1);
758 if (bit)
759 rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
760 else
761 rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p)));
762 }
763
clear(int p)764 void BitString::clear(int p)
765 {
766 if (p < 0) error("Illegal bit index");
767 if (p >= rep->len) rep = BStr_resize(rep, p + 1);
768 rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p)));
769 }
770
clear()771 void BitString::clear()
772 {
773 if (rep == &_nilBitStrRep) return;
774 bit_clear(rep->s, rep->len);
775 }
776
set()777 void BitString::set()
778 {
779 if (rep == &_nilBitStrRep) return;
780 unsigned short* s = rep->s;
781 unsigned short* tops = &(s[BitStr_len(rep->len)]);
782 while (s < tops) *s++ = ONES;
783 check_last(rep);
784 }
785
invert(int p)786 void BitString::invert(int p)
787 {
788 if (p < 0) error("Illegal bit index");
789 if (p >= rep->len) rep = BStr_resize(rep, p + 1);
790 rep->s[BitStr_index(p)] ^= (1 << (BitStr_pos(p)));
791 }
792
793
794
set(int from,int to)795 void BitString::set(int from, int to)
796 {
797 if (from < 0 || from > to) error("Illegal bit index");
798 if (to >= rep->len) rep = BStr_resize(rep, to+1);
799
800 int ind1 = BitStr_index(from);
801 int pos1 = BitStr_pos(from);
802 int ind2 = BitStr_index(to);
803 int pos2 = BitStr_pos(to);
804 unsigned short* s = &(rep->s[ind1]);
805 unsigned short m1 = lmask(pos1);
806 unsigned short m2 = rmask(pos2);
807 if (ind2 == ind1)
808 *s |= m1 & m2;
809 else
810 {
811 *s++ |= m1;
812 unsigned short* top = &(rep->s[ind2]);
813 *top |= m2;
814 while (s < top)
815 *s++ = ONES;
816 }
817 }
818
clear(int from,int to)819 void BitString::clear(int from, int to)
820 {
821 if (from < 0 || from > to) error("Illegal bit index");
822 if (to >= rep->len) rep = BStr_resize(rep, to+1);
823
824 int ind1 = BitStr_index(from);
825 int pos1 = BitStr_pos(from);
826 int ind2 = BitStr_index(to);
827 int pos2 = BitStr_pos(to);
828 unsigned short* s = &(rep->s[ind1]);
829 unsigned short m1 = lmask(pos1);
830 unsigned short m2 = rmask(pos2);
831 if (ind2 == ind1)
832 *s &= ~(m1 & m2);
833 else
834 {
835 *s++ &= ~m1;
836 unsigned short* top = &(rep->s[ind2]);
837 *top &= ~m2;
838 while (s < top)
839 *s++ = 0;
840 }
841 }
842
invert(int from,int to)843 void BitString::invert(int from, int to)
844 {
845 if (from < 0 || from > to) error("Illegal bit index");
846 if (to >= rep->len) rep = BStr_resize(rep, to+1);
847
848 int ind1 = BitStr_index(from);
849 int pos1 = BitStr_pos(from);
850 int ind2 = BitStr_index(to);
851 int pos2 = BitStr_pos(to);
852 unsigned short* s = &(rep->s[ind1]);
853 unsigned short m1 = lmask(pos1);
854 unsigned short m2 = rmask(pos2);
855 if (ind2 == ind1)
856 *s ^= m1 & m2;
857 else
858 {
859 *s++ ^= m1;
860 unsigned short* top = &(rep->s[ind2]);
861 *top ^= m2;
862 while (s < top)
863 {
864 unsigned short cmp = ~(*s);
865 *s++ = cmp;
866 }
867 }
868 }
869
870
test(int from,int to) const871 int BitString::test(int from, int to) const
872 {
873 if (from < 0 || from > to || from >= rep->len) return 0;
874
875 int ind1 = BitStr_index(from);
876 int pos1 = BitStr_pos(from);
877 int ind2 = BitStr_index(to);
878 int pos2 = BitStr_pos(to);
879
880 if (to >= rep->len)
881 {
882 ind2 = BitStr_index(rep->len - 1);
883 pos2 = BitStr_pos(rep->len - 1);
884 }
885
886 const unsigned short* s = &(rep->s[ind1]);
887 unsigned short m1 = lmask(pos1);
888 unsigned short m2 = rmask(pos2);
889
890 if (ind2 == ind1)
891 return (*s & m1 & m2) != 0;
892 else
893 {
894 if (*s++ & m1)
895 return 1;
896 unsigned short* top = &(rep->s[ind2]);
897 if (*top & m2)
898 return 1;
899 while (s < top)
900 if (*s++ != 0)
901 return 1;
902 return 0;
903 }
904 }
905
next(int p,unsigned int b) const906 int BitString::next(int p, unsigned int b) const
907 {
908 if (++p >= rep->len)
909 return -1;
910
911 int ind = BitStr_index(p);
912 int pos = BitStr_pos(p);
913 int l = BitStr_len(rep->len);
914
915 int j = ind;
916 const unsigned short* s = rep->s;
917 unsigned short a = s[j] >> pos;
918 int i = pos;
919
920 if (b != 0)
921 {
922 for (; i < BITSTRBITS && a != 0; ++i)
923 {
924 if (a & 1)
925 return j * BITSTRBITS + i;
926 a >>= 1;
927 }
928 for (++j; j < l; ++j)
929 {
930 a = s[j];
931 for (i = 0; i < BITSTRBITS && a != 0; ++i)
932 {
933 if (a & 1)
934 return j * BITSTRBITS + i;
935 a >>= 1;
936 }
937 }
938 return -1;
939 }
940 else
941 {
942 int last = BitStr_pos(rep->len);
943 if (j == l - 1)
944 {
945 for (; i < last; ++i)
946 {
947 if ((a & 1) == 0)
948 return j * BITSTRBITS + i;
949 a >>= 1;
950 }
951 return -1;
952 }
953
954 for (; i < BITSTRBITS; ++i)
955 {
956 if ((a & 1) == 0)
957 return j * BITSTRBITS + i;
958 a >>= 1;
959 }
960 for (++j; j < l - 1; ++j)
961 {
962 a = s[j];
963 if (a != ONES)
964 {
965 for (i = 0; i < BITSTRBITS; ++i)
966 {
967 if ((a & 1) == 0)
968 return j * BITSTRBITS + i;
969 a >>= 1;
970 }
971 }
972 }
973 a = s[j];
974 for (i = 0; i < last; ++i)
975 {
976 if ((a & 1) == 0)
977 return j * BITSTRBITS + i;
978 a >>= 1;
979 }
980 return -1;
981 }
982 }
983
previous(int p,unsigned int b) const984 int BitString::previous(int p, unsigned int b) const
985 {
986 if (--p < 0)
987 return -1;
988
989 int ind = BitStr_index(p);
990 int pos = BitStr_pos(p);
991
992 const unsigned short* s = rep->s;
993
994 if (p >= rep->len)
995 {
996 ind = BitStr_index(rep->len - 1);
997 pos = BitStr_pos(rep->len - 1);
998 }
999
1000 int j = ind;
1001 unsigned short a = s[j];
1002
1003 int i = pos;
1004 unsigned short maxbit = 1 << pos;
1005
1006 if (b != 0)
1007 {
1008 for (; i >= 0 && a != 0; --i)
1009 {
1010 if (a & maxbit)
1011 return j * BITSTRBITS + i;
1012 a <<= 1;
1013 }
1014 maxbit = 1 << (BITSTRBITS - 1);
1015 for (--j; j >= 0; --j)
1016 {
1017 a = s[j];
1018 for (i = BITSTRBITS - 1; i >= 0 && a != 0; --i)
1019 {
1020 if (a & maxbit)
1021 return j * BITSTRBITS + i;
1022 a <<= 1;
1023 }
1024 }
1025 return -1;
1026 }
1027 else
1028 {
1029 if (a != ONES)
1030 {
1031 for (; i >= 0; --i)
1032 {
1033 if ((a & maxbit) == 0)
1034 return j * BITSTRBITS + i;
1035 a <<= 1;
1036 }
1037 }
1038 maxbit = 1 << (BITSTRBITS - 1);
1039 for (--j; j >= 0; --j)
1040 {
1041 a = s[j];
1042 if (a != ONES)
1043 {
1044 for (i = BITSTRBITS - 1; i >= 0; --i)
1045 {
1046 if ((a & maxbit) == 0)
1047 return j * BITSTRBITS + i;
1048 a <<= 1;
1049 }
1050 }
1051 }
1052 return -1;
1053 }
1054 }
1055
1056
search(int startx,int lengthx,const unsigned short * ys,int starty,int lengthy) const1057 int BitString::search(int startx, int lengthx,
1058 const unsigned short* ys, int starty, int lengthy) const
1059 {
1060 const unsigned short* xs = rep->s;
1061 int ylen = lengthy - starty;
1062 int righty = lengthy - 1;
1063 int rev = startx < 0;
1064 if (rev)
1065 {
1066 int leftx = 0;
1067 int rightx = lengthx + startx;
1068 startx = rightx - ylen + 1;
1069 if (ylen == 0) return startx;
1070 if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
1071
1072 int xind = BitStr_index(startx);
1073 int xpos = BitStr_pos(startx);
1074 int yind = BitStr_index(starty);
1075 int ypos = BitStr_pos(starty);
1076
1077 int rightxind = BitStr_index(rightx);
1078
1079 unsigned short x = borrow_hi(xs, xind, rightxind, xpos);
1080
1081 int rightyind = BitStr_index(righty);
1082 int rightypos = BitStr_pos(righty);
1083 unsigned short y = borrow_hi(ys, yind, rightyind, ypos);
1084 unsigned short ymask;
1085 if (yind == rightyind)
1086 ymask = rmask(rightypos);
1087 else if (yind+1 == rightyind)
1088 ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
1089 else
1090 ymask = ONES;
1091
1092 int p = startx;
1093 for (;;)
1094 {
1095 if ((x & ymask) == y)
1096 {
1097 int xi = xind;
1098 int yi = yind;
1099 for (;;)
1100 {
1101 if (++yi > rightyind || ++xi > rightxind)
1102 return p;
1103 unsigned short tx = borrow_hi(xs, xi, rightxind, xpos);
1104 unsigned short ty = borrow_hi(ys, yi, rightyind, ypos);
1105 if (yi == rightyind)
1106 tx &= rmask(rightypos);
1107 else if (yi+1 == rightyind)
1108 tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
1109 if (tx != ty)
1110 break;
1111 }
1112 }
1113 if (--p < leftx)
1114 return -1;
1115 if (--xpos < 0)
1116 {
1117 xpos = BITSTRBITS - 1;
1118 --xind;
1119 }
1120 x = borrow_hi(xs, xind, rightxind, xpos);
1121 }
1122 }
1123 else
1124 {
1125
1126 int rightx = lengthx - 1;
1127 if (ylen == 0) return startx;
1128 if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
1129
1130 int xind = BitStr_index(startx);
1131 int xpos = BitStr_pos(startx);
1132 int yind = BitStr_index(starty);
1133 int ypos = BitStr_pos(starty);
1134
1135 int rightxind = BitStr_index(rightx);
1136
1137 unsigned short x = borrow_hi(xs, xind, rightxind, xpos);
1138 unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
1139
1140 int rightyind = BitStr_index(righty);
1141 int rightypos = BitStr_pos(righty);
1142 unsigned short y = borrow_hi(ys, yind, rightyind, ypos);
1143 unsigned short ymask;
1144 if (yind == rightyind)
1145 ymask = rmask(rightypos);
1146 else if (yind+1 == rightyind)
1147 ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
1148 else
1149 ymask = ONES;
1150
1151 int p = startx;
1152 for (;;)
1153 {
1154 if ((x & ymask) == y)
1155 {
1156 int xi = xind;
1157 int yi = yind;
1158 for (;;)
1159 {
1160 if (++yi > rightyind || ++xi > rightxind)
1161 return p;
1162 unsigned short tx = borrow_hi(xs, xi, rightxind, xpos);
1163 unsigned short ty = borrow_hi(ys, yi, rightyind, ypos);
1164 if (yi == rightyind)
1165 tx &= rmask(rightypos);
1166 else if (yi+1 == rightyind)
1167 tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
1168 if (tx != ty)
1169 break;
1170 }
1171 }
1172 if (++p > rightx)
1173 return -1;
1174 if (++xpos == BITSTRBITS)
1175 {
1176 xpos = 0;
1177 x = xs[++xind];
1178 nextx = (xind >= rightxind) ? 0 : xs[xind+1];
1179 }
1180 else
1181 {
1182 x >>= 1;
1183 if (nextx & 1)
1184 x |= MAXBIT;
1185 nextx >>= 1;
1186 }
1187 }
1188 }
1189 }
1190
1191
search(const unsigned short * xs,int startx,int lengthx) const1192 int BitPattern::search(const unsigned short* xs, int startx, int lengthx) const
1193 {
1194 const unsigned short* ys = pattern.rep->s;
1195 const unsigned short* ms = mask.rep->s;
1196 int righty = pattern.rep->len - 1;
1197 int rightm = mask.rep->len - 1;
1198
1199 int rev = startx < 0;
1200 if (rev)
1201 {
1202 int leftx = 0;
1203 int rightx = lengthx + startx;
1204 startx = rightx - righty;
1205
1206 if (righty < 0) return startx;
1207 if (startx < 0 || startx >= lengthx) return -1;
1208
1209 int xind = BitStr_index(startx);
1210 int xpos = BitStr_pos(startx);
1211
1212 int rightxind = BitStr_index(rightx);
1213
1214 int rightmind = BitStr_index(rightm);
1215 int rightyind = BitStr_index(righty);
1216
1217 unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos);
1218 unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0);
1219 unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
1220
1221 int p = startx;
1222 for (;;)
1223 {
1224 if ((x & m) == y)
1225 {
1226 int xi = xind;
1227 int yi = 0;
1228 for (;;)
1229 {
1230 if (++yi > rightyind || ++xi > rightxind)
1231 return p;
1232 unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0);
1233 unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0);
1234 unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos);
1235 if ((tx & tm) != (ty & tm))
1236 break;
1237 }
1238 }
1239 if (--p < leftx)
1240 return -1;
1241 if (--xpos < 0)
1242 {
1243 xpos = BITSTRBITS - 1;
1244 --xind;
1245 }
1246 x = safe_borrow_hi(xs, xind, rightxind, xpos);
1247 }
1248 }
1249 else
1250 {
1251
1252 int rightx = lengthx - 1;
1253
1254 if (righty < 0) return startx;
1255 if (startx < 0 || startx >= lengthx) return -1;
1256
1257 int xind = BitStr_index(startx);
1258 int xpos = BitStr_pos(startx);
1259
1260 int rightxind = BitStr_index(rightx);
1261
1262 int rightmind = BitStr_index(rightm);
1263 int rightyind = BitStr_index(righty);
1264
1265 unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos);
1266 unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0);
1267 unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
1268
1269 unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
1270
1271 int p = startx;
1272 for (;;)
1273 {
1274 if ((x & m) == y)
1275 {
1276 int xi = xind;
1277 int yi = 0;
1278 for (;;)
1279 {
1280 if (++yi > rightyind || ++xi > rightxind)
1281 return p;
1282 unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0);
1283 unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0);
1284 unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos);
1285 if ((tx & tm) != (ty & tm))
1286 break;
1287 }
1288 }
1289 if (++p > rightx)
1290 return -1;
1291 if (++xpos == BITSTRBITS)
1292 {
1293 xpos = 0;
1294 x = xs[++xind];
1295 nextx = (xind >= rightxind) ? 0 : xs[xind+1];
1296 }
1297 else
1298 {
1299 x >>= 1;
1300 if (nextx & 1)
1301 x |= MAXBIT;
1302 nextx >>= 1;
1303 }
1304 }
1305 }
1306 }
1307
match(int startx,int lengthx,int exact,const unsigned short * ys,int starty,int yl) const1308 int BitString::match(int startx, int lengthx, int exact,
1309 const unsigned short* ys, int starty, int yl) const
1310 {
1311 const unsigned short* xs = rep->s;
1312 int ylen = yl - starty;
1313 int righty = yl - 1;
1314
1315 int rightx;
1316 int rev = startx < 0;
1317 if (rev)
1318 {
1319 rightx = lengthx + startx;
1320 startx = rightx - ylen + 1;
1321 if (exact && startx != 0)
1322 return 0;
1323 }
1324 else
1325 {
1326 rightx = lengthx - 1;
1327 if (exact && rightx - startx != righty)
1328 return 0;
1329 }
1330
1331 if (ylen == 0) return 1;
1332 if (righty < 0 || startx < 0 || startx >= lengthx) return 0;
1333
1334 int xi = BitStr_index(startx);
1335 int xpos = BitStr_pos(startx);
1336 int yi = BitStr_index(starty);
1337 int ypos = BitStr_pos(starty);
1338
1339 int rightxind = BitStr_index(rightx);
1340 int rightyind = BitStr_index(righty);
1341 int rightypos = BitStr_pos(righty);
1342
1343 for (;;)
1344 {
1345 unsigned short x = borrow_hi(xs, xi, rightxind, xpos);
1346 unsigned short y = borrow_hi(ys, yi, rightyind, ypos);
1347 if (yi == rightyind)
1348 x &= rmask(rightypos);
1349 else if (yi+1 == rightyind)
1350 x &= rmask(BITSTRBITS - ypos + rightypos + 1);
1351 if (x != y)
1352 return 0;
1353 else if (++yi > rightyind || ++xi > rightxind)
1354 return 1;
1355 }
1356 }
1357
match(const unsigned short * xs,int startx,int lengthx,int exact) const1358 int BitPattern::match(const unsigned short* xs, int startx,
1359 int lengthx, int exact) const
1360 {
1361 const unsigned short* ys = pattern.rep->s;
1362 int righty = pattern.rep->len - 1;
1363 unsigned short* ms = mask.rep->s;
1364 int rightm = mask.rep->len - 1;
1365
1366 int rightx;
1367 int rev = startx < 0;
1368 if (rev)
1369 {
1370 rightx = lengthx + startx;
1371 startx = rightx - righty;
1372 if (exact && startx != 0)
1373 return 0;
1374 }
1375 else
1376 {
1377 rightx = lengthx - 1;
1378 if (exact && rightx - startx != righty)
1379 return 0;
1380 }
1381
1382 if (righty < 0) return 1;
1383 if (startx < 0 || startx >= lengthx) return 0;
1384
1385 int xind = BitStr_index(startx);
1386 int xpos = BitStr_pos(startx);
1387 int yind = 0;
1388
1389 int rightxind = BitStr_index(rightx);
1390 int rightyind = BitStr_index(righty);
1391 int rightmind = BitStr_index(rightm);
1392
1393 for(;;)
1394 {
1395 unsigned short m = safe_borrow_hi(ms, yind, rightmind, 0);
1396 unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos) & m;
1397 unsigned short y = safe_borrow_hi(ys, yind, rightyind, 0) & m;
1398 if (x != y)
1399 return 0;
1400 else if (++yind > rightyind || ++xind > rightxind)
1401 return 1;
1402 }
1403 }
1404
operator =(const BitString & y)1405 void BitSubString::operator = (const BitString& y)
1406 {
1407 if (&S == &_nil_BitString) return;
1408 BitStrRep* targ = S.rep;
1409
1410 int ylen = y.rep->len;
1411 int sl = targ->len - len + ylen;
1412
1413 if (y.rep == targ || ylen > len)
1414 {
1415 BitStrRep* oldtarg = targ;
1416 targ = BStr_alloc(0, 0, 0, 0, sl);
1417 bit_transfer(oldtarg->s, 0, pos, targ->s, 0);
1418 bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
1419 bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + ylen);
1420 delete oldtarg;
1421 }
1422 else if (len == ylen)
1423 bit_transfer(y.rep->s, 0, len, targ->s, pos);
1424 else if (ylen < len)
1425 {
1426 bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
1427 bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + ylen);
1428 targ->len = sl;
1429 }
1430 check_last(targ);
1431 S.rep = targ;
1432 }
1433
operator =(const BitSubString & y)1434 void BitSubString::operator = (const BitSubString& y)
1435 {
1436 if (&S == &_nil_BitString) return;
1437 BitStrRep* targ = S.rep;
1438
1439 if (len == 0 || pos >= targ->len)
1440 return;
1441
1442 int sl = targ->len - len + y.len;
1443
1444 if (y.S.rep == targ || y.len > len)
1445 {
1446 BitStrRep* oldtarg = targ;
1447 targ = BStr_alloc(0, 0, 0, 0, sl);
1448 bit_copy(oldtarg->s, targ->s, pos);
1449 bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
1450 bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + y.len);
1451 delete oldtarg;
1452 }
1453 else if (len == y.len)
1454 bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
1455 else if (y.len < len)
1456 {
1457 bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
1458 bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + y.len);
1459 targ->len = sl;
1460 }
1461 check_last(targ);
1462 S.rep = targ;
1463 }
1464
at(int first,int len)1465 BitSubString BitString::at(int first, int len)
1466 {
1467 return _substr(first, len);
1468 }
1469
before(int pos)1470 BitSubString BitString::before(int pos)
1471 {
1472 return _substr(0, pos);
1473 }
1474
after(int pos)1475 BitSubString BitString::after(int pos)
1476 {
1477 return _substr(pos + 1, rep->len - (pos + 1));
1478 }
1479
at(const BitString & y,int startpos)1480 BitSubString BitString::at(const BitString& y, int startpos)
1481 {
1482 int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
1483 return _substr(first, y.rep->len);
1484 }
1485
before(const BitString & y,int startpos)1486 BitSubString BitString::before(const BitString& y, int startpos)
1487 {
1488 int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
1489 return _substr(0, last);
1490 }
1491
after(const BitString & y,int startpos)1492 BitSubString BitString::after(const BitString& y, int startpos)
1493 {
1494 int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
1495 if (first >= 0) first += y.rep->len;
1496 return _substr(first, rep->len - first);
1497 }
1498
1499
at(const BitSubString & y,int startpos)1500 BitSubString BitString::at(const BitSubString& y, int startpos)
1501 {
1502 int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
1503 return _substr(first, y.len);
1504 }
1505
before(const BitSubString & y,int startpos)1506 BitSubString BitString::before(const BitSubString& y, int startpos)
1507 {
1508 int last = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
1509 return _substr(0, last);
1510 }
1511
after(const BitSubString & y,int startpos)1512 BitSubString BitString::after(const BitSubString& y, int startpos)
1513 {
1514 int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
1515 if (first >= 0) first += y.len;
1516 return _substr(first, rep->len - first);
1517 }
1518
at(const BitPattern & r,int startpos)1519 BitSubString BitString::at(const BitPattern& r, int startpos)
1520 {
1521 int first = r.search(rep->s, startpos, rep->len);
1522 return _substr(first, r.pattern.rep->len);
1523 }
1524
1525
before(const BitPattern & r,int startpos)1526 BitSubString BitString::before(const BitPattern& r, int startpos)
1527 {
1528 int first = r.search(rep->s, startpos, rep->len);
1529 return _substr(0, first);
1530 }
1531
after(const BitPattern & r,int startpos)1532 BitSubString BitString::after(const BitPattern& r, int startpos)
1533 {
1534 int first = r.search(rep->s, startpos, rep->len);
1535 if (first >= 0) first += r.pattern.rep->len;
1536 return _substr(first, rep->len - first);
1537 }
1538
1539 #if defined(__GNUG__) && !defined(NO_NRV)
1540
1541 BitString common_prefix(const BitString& x, const BitString& y, int startpos)
1542 return r
1543 {
1544 unsigned int xl = x.rep->len;
1545 unsigned int yl = y.rep->len;
1546
1547 int startx, starty;
1548 if (startpos < 0)
1549 {
1550 startx = xl + startpos;
1551 starty = yl + startpos;
1552 }
1553 else
1554 startx = starty = startpos;
1555
1556 if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
1557 return;
1558
1559 const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
1560 unsigned short a = *xs++;
1561 int xp = startx;
1562
1563 const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
1564 unsigned short b = *ys++;
1565 int yp = starty;
1566
1567 for(; xp < xl && yp < yl; ++xp, ++yp)
1568 {
1569 unsigned short xbit = 1 << (BitStr_pos(xp));
1570 unsigned short ybit = 1 << (BitStr_pos(yp));
1571 if (((a & xbit) == 0) != ((b & ybit) == 0))
1572 break;
1573 if (xbit == MAXBIT)
1574 a = *xs++;
1575 if (ybit == MAXBIT)
1576 b = *ys++;
1577 }
1578 r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx);
1579 }
1580
1581
1582 BitString common_suffix(const BitString& x, const BitString& y, int startpos)
1583 return r;
1584 {
1585 unsigned int xl = x.rep->len;
1586 unsigned int yl = y.rep->len;
1587
1588 int startx, starty;
1589 if (startpos < 0)
1590 {
1591 startx = xl + startpos;
1592 starty = yl + startpos;
1593 }
1594 else
1595 startx = starty = startpos;
1596
1597 if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
1598 return;
1599
1600 const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
1601 unsigned short a = *xs--;
1602 int xp = startx;
1603
1604 const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
1605 unsigned short b = *ys--;
1606 int yp = starty;
1607
1608 for(; xp >= 0 && yp >= 0; --xp, --yp)
1609 {
1610 unsigned short xbit = 1 << (BitStr_pos(xp));
1611 unsigned short ybit = 1 << (BitStr_pos(yp));
1612 if (((a & xbit) == 0) != ((b & ybit) == 0))
1613 break;
1614 if (xbit == 1)
1615 a = *xs--;
1616 if (ybit == 1)
1617 b = *ys--;
1618 }
1619 r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp);
1620 }
1621
1622 BitString reverse(const BitString& x) return r
1623 {
1624 unsigned int yl = x.rep->len;
1625 BitStrRep* y = BStr_resize(0, yl);
1626 if (yl > 0)
1627 {
1628 const unsigned short* ls = x.rep->s;
1629 unsigned short lm = 1;
1630 unsigned short* rs = &(y->s[BitStr_index(yl - 1)]);
1631 unsigned short rm = 1 << (BitStr_pos(yl - 1));
1632 for (unsigned int l = 0; l < yl; ++l)
1633 {
1634 if (*ls & lm)
1635 *rs |= rm;
1636 if (lm == MAXBIT)
1637 {
1638 ++ls;
1639 lm = 1;
1640 }
1641 else
1642 lm <<= 1;
1643 if (rm == 1)
1644 {
1645 --rs;
1646 rm = MAXBIT;
1647 }
1648 else
1649 rm >>= 1;
1650 }
1651 }
1652 r.rep = y;
1653 }
1654
1655 BitString atoBitString(const char* s, char f, char t) return res
1656 {
1657 int sl = strlen(s);
1658 BitStrRep* r = BStr_resize(0, sl);
1659 if (sl != 0)
1660 {
1661 unsigned int rl = 0;
1662 unsigned short* rs = r->s;
1663 unsigned short a = 0;
1664 unsigned short m = 1;
1665 unsigned int i = 0;
1666 for(;;)
1667 {
1668 char ch = s[i];
1669 if (ch != t && ch != f)
1670 {
1671 *rs = a;
1672 break;
1673 }
1674 ++rl;
1675 if (ch == t)
1676 a |= m;
1677 if (++i == sl)
1678 {
1679 *rs = a;
1680 break;
1681 }
1682 else if (i % BITSTRBITS == 0)
1683 {
1684 *rs++ = a;
1685 a = 0;
1686 m = 1;
1687 }
1688 else
1689 m <<= 1;
1690 }
1691 r = BStr_resize(r, rl);
1692 }
1693 res.rep = r;
1694 }
1695
1696 BitPattern atoBitPattern(const char* s, char f,char t,char x) return r
1697 {
1698 int sl = strlen(s);
1699 if (sl != 0)
1700 {
1701 unsigned int rl = 0;
1702 r.pattern.rep = BStr_resize(r.pattern.rep, sl);
1703 r.mask.rep = BStr_resize(r.mask.rep, sl);
1704 unsigned short* rs = r.pattern.rep->s;
1705 unsigned short* ms = r.mask.rep->s;
1706 unsigned short a = 0;
1707 unsigned short b = 0;
1708 unsigned short m = 1;
1709 unsigned int i = 0;
1710 for(;;)
1711 {
1712 char ch = s[i];
1713 if (ch != t && ch != f && ch != x)
1714 {
1715 *rs = a;
1716 *ms = b;
1717 break;
1718 }
1719 ++rl;
1720 if (ch == t)
1721 {
1722 a |= m;
1723 b |= m;
1724 }
1725 else if (ch == f)
1726 {
1727 b |= m;
1728 }
1729 if (++i == sl)
1730 {
1731 *rs = a;
1732 *ms = b;
1733 break;
1734 }
1735 else if (i % BITSTRBITS == 0)
1736 {
1737 *rs++ = a;
1738 *ms++ = b;
1739 a = 0;
1740 b = 0;
1741 m = 1;
1742 }
1743 else
1744 m <<= 1;
1745 }
1746 r.pattern.rep = BStr_resize(r.pattern.rep, rl);
1747 r.mask.rep = BStr_resize(r.mask.rep, rl);
1748 }
1749 return;
1750 }
1751
1752 #else /* NO_NRV */
1753
1754 BitString common_prefix(const BitString& x, const BitString& y, int startpos)
1755 {
1756 BitString r;
1757
1758 unsigned int xl = x.rep->len;
1759 unsigned int yl = y.rep->len;
1760
1761 int startx, starty;
1762 if (startpos < 0)
1763 {
1764 startx = xl + startpos;
1765 starty = yl + startpos;
1766 }
1767 else
1768 startx = starty = startpos;
1769
1770 if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
1771 return r;
1772
1773 const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
1774 unsigned short a = *xs++;
1775 int xp = startx;
1776
1777 const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
1778 unsigned short b = *ys++;
1779 int yp = starty;
1780
1781 for(; xp < xl && yp < yl; ++xp, ++yp)
1782 {
1783 unsigned short xbit = 1 << (BitStr_pos(xp));
1784 unsigned short ybit = 1 << (BitStr_pos(yp));
1785 if (((a & xbit) == 0) != ((b & ybit) == 0))
1786 break;
1787 if (xbit == MAXBIT)
1788 a = *xs++;
1789 if (ybit == MAXBIT)
1790 b = *ys++;
1791 }
1792 r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx);
1793 return r;
1794 }
1795
1796
1797 BitString common_suffix(const BitString& x, const BitString& y, int startpos)
1798 {
1799 BitString r;
1800 unsigned int xl = x.rep->len;
1801 unsigned int yl = y.rep->len;
1802
1803 int startx, starty;
1804 if (startpos < 0)
1805 {
1806 startx = xl + startpos;
1807 starty = yl + startpos;
1808 }
1809 else
1810 startx = starty = startpos;
1811
1812 if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
1813 return r;
1814
1815 const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
1816 unsigned short a = *xs--;
1817 int xp = startx;
1818
1819 const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
1820 unsigned short b = *ys--;
1821 int yp = starty;
1822
1823 for(; xp >= 0 && yp >= 0; --xp, --yp)
1824 {
1825 unsigned short xbit = 1 << (BitStr_pos(xp));
1826 unsigned short ybit = 1 << (BitStr_pos(yp));
1827 if (((a & xbit) == 0) != ((b & ybit) == 0))
1828 break;
1829 if (xbit == 1)
1830 a = *xs--;
1831 if (ybit == 1)
1832 b = *ys--;
1833 }
1834 r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp);
1835 return r;
1836 }
1837
1838 BitString reverse(const BitString& x)
1839 {
1840 BitString r;
1841 unsigned int yl = x.rep->len;
1842 BitStrRep* y = BStr_resize(0, yl);
1843 if (yl > 0)
1844 {
1845 const unsigned short* ls = x.rep->s;
1846 unsigned short lm = 1;
1847 unsigned short* rs = &(y->s[BitStr_index(yl - 1)]);
1848 unsigned short rm = 1 << (BitStr_pos(yl - 1));
1849 for (unsigned int l = 0; l < yl; ++l)
1850 {
1851 if (*ls & lm)
1852 *rs |= rm;
1853 if (lm == MAXBIT)
1854 {
1855 ++ls;
1856 lm = 1;
1857 }
1858 else
1859 lm <<= 1;
1860 if (rm == 1)
1861 {
1862 --rs;
1863 rm = MAXBIT;
1864 }
1865 else
1866 rm >>= 1;
1867 }
1868 }
1869 r.rep = y;
1870 return r;
1871 }
1872
1873 BitString atoBitString(const char* s, char f, char t)
1874 {
1875 BitString res;
1876 int sl = strlen(s);
1877 BitStrRep* r = BStr_resize(0, sl);
1878 if (sl != 0)
1879 {
1880 unsigned int rl = 0;
1881 unsigned short* rs = r->s;
1882 unsigned short a = 0;
1883 unsigned short m = 1;
1884 unsigned int i = 0;
1885 for(;;)
1886 {
1887 char ch = s[i];
1888 if (ch != t && ch != f)
1889 {
1890 *rs = a;
1891 break;
1892 }
1893 ++rl;
1894 if (ch == t)
1895 a |= m;
1896 if (++i == sl)
1897 {
1898 *rs = a;
1899 break;
1900 }
1901 else if (i % BITSTRBITS == 0)
1902 {
1903 *rs++ = a;
1904 a = 0;
1905 m = 1;
1906 }
1907 else
1908 m <<= 1;
1909 }
1910 r = BStr_resize(r, rl);
1911 }
1912 res.rep = r;
1913 return res;
1914 }
1915
1916 BitPattern atoBitPattern(const char* s, char f,char t,char x)
1917 {
1918 BitPattern r;
1919 int sl = strlen(s);
1920 if (sl != 0)
1921 {
1922 unsigned int rl = 0;
1923 r.pattern.rep = BStr_resize(r.pattern.rep, sl);
1924 r.mask.rep = BStr_resize(r.mask.rep, sl);
1925 unsigned short* rs = r.pattern.rep->s;
1926 unsigned short* ms = r.mask.rep->s;
1927 unsigned short a = 0;
1928 unsigned short b = 0;
1929 unsigned short m = 1;
1930 unsigned int i = 0;
1931 for(;;)
1932 {
1933 char ch = s[i];
1934 if (ch != t && ch != f && ch != x)
1935 {
1936 *rs = a;
1937 *ms = b;
1938 break;
1939 }
1940 ++rl;
1941 if (ch == t)
1942 {
1943 a |= m;
1944 b |= m;
1945 }
1946 else if (ch == f)
1947 {
1948 b |= m;
1949 }
1950 if (++i == sl)
1951 {
1952 *rs = a;
1953 *ms = b;
1954 break;
1955 }
1956 else if (i % BITSTRBITS == 0)
1957 {
1958 *rs++ = a;
1959 *ms++ = b;
1960 a = 0;
1961 b = 0;
1962 m = 1;
1963 }
1964 else
1965 m <<= 1;
1966 }
1967 r.pattern.rep = BStr_resize(r.pattern.rep, rl);
1968 r.mask.rep = BStr_resize(r.mask.rep, rl);
1969 }
1970 return r;
1971 }
1972
1973 #endif
1974
1975 extern AllocRing _libgxx_fmtq;
1976
BitStringtoa(const BitString & x,char f,char t)1977 const char* BitStringtoa(const BitString& x, char f, char t)
1978 {
1979 int wrksiz = x.length() + 2;
1980 char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
1981 char* fmt = fmtbase;
1982 unsigned int xl = x.rep->len;
1983 const unsigned short* s = x.rep->s;
1984 unsigned short a = 0;
1985
1986 for (unsigned int i = 0; i < xl; ++i)
1987 {
1988 if (i % BITSTRBITS == 0)
1989 a = *s++;
1990 *fmt++ = (a & 1)? t : f;
1991 a >>= 1;
1992 }
1993
1994 *fmt = 0;
1995
1996 return fmtbase;
1997 }
1998
1999
operator <<(ostream & s,const BitString & x)2000 ostream& operator << (ostream& s, const BitString& x)
2001 {
2002 return s << BitStringtoa(x);
2003 }
2004
BitPatterntoa(const BitPattern & p,char f,char t,char x)2005 const char* BitPatterntoa(const BitPattern& p, char f,char t,char x)
2006 {
2007 unsigned int pl = p.pattern.rep->len;
2008 unsigned int ml = p.mask.rep->len;
2009 unsigned int l = (pl <= ml)? pl : ml;
2010
2011 int wrksiz = l + 2;
2012 char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
2013 char* fmt = fmtbase;
2014
2015 const unsigned short* ps = p.pattern.rep->s;
2016 const unsigned short* ms = p.mask.rep->s;
2017 unsigned short a = 0;
2018 unsigned short m = 0;
2019
2020 for (unsigned int i = 0; i < l; ++i)
2021 {
2022 if (i % BITSTRBITS == 0)
2023 {
2024 a = *ps++;
2025 m = *ms++;
2026 }
2027 if (m & 1)
2028 *fmt++ =(a & 1)? t : f;
2029 else
2030 *fmt++ = x;
2031 a >>= 1;
2032 m >>= 1;
2033 }
2034
2035 *fmt = 0;
2036 return fmtbase;
2037 }
2038
2039
operator <<(ostream & s,const BitPattern & x)2040 ostream& operator << (ostream& s, const BitPattern& x)
2041 {
2042 return s << BitPatterntoa(x);
2043 }
2044
2045
OK() const2046 int BitString::OK() const
2047 {
2048 int v = rep != 0; // have a rep;
2049 v &= BitStr_len(rep->len) <= rep->sz; // within allocated size
2050 if (!v) error("invariant failure");
2051 return v;
2052 }
2053
OK() const2054 int BitSubString::OK() const
2055 {
2056 int v = S.OK(); // valid BitString
2057 v &= pos >= 0 && len >= 0; // valid indices
2058 v &= pos + len <= S.rep->len; // within bounds of targ
2059 if (!v) S.error("BitSubString invariant failure");
2060 return v;
2061 }
2062
OK() const2063 int BitPattern::OK() const
2064 {
2065 int v = pattern.OK() && mask.OK();
2066 if (!v) pattern.error("BitPattern invariant failure");
2067 return v;
2068 }
2069
2070