/* Copyright (C) 1988 Free Software Foundation written by Doug Lea (dl@rocky.oswego.edu) This file is part of the GNU C++ Library. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; if not, write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ /* BitString class implementation */ #ifdef __GNUG__ #pragma implementation #endif #include #include #include #include #include #include #include void BitString::error(const char* msg) const { (*lib_error_handler)("BitString", msg); } // globals BitStrRep _nilBitStrRep = { 0, 1, {0} }; BitString _nil_BitString; #define MINBitStrRep_SIZE 8 #define MAXBitStrRep_SIZE ((1 << (SHORTBITS - 1)) - 1) #ifndef MALLOC_MIN_OVERHEAD #define MALLOC_MIN_OVERHEAD 4 #endif #define ONES ((unsigned short)(~0L)) #define MAXBIT (1 << (BITSTRBITS - 1)) /* * bit manipulation utilities */ // break things up into .s indices and positions inline static int BitStr_len(int l) { return (unsigned)(l) / BITSTRBITS + 1; } // mask out low bits static inline unsigned short lmask(int p) { if (p <= 0) return ONES; else return ONES << p; } // mask out high bits static inline unsigned short rmask(int p) { int s = BITSTRBITS - 1 - p; if (s <= 0) return ONES; else return ONES >> s; } // mask out unused bits in last word of rep inline static void check_last(BitStrRep* r) { r->s[r->len / BITSTRBITS] &= ONES >> (BITSTRBITS - (r->len & (BITSTRBITS - 1))); } // merge bits from next word static inline unsigned short borrow_hi(const unsigned short a[], int ind, int maxind, int p) { if (ind < maxind) return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p)); else return (a[ind] >> p); } // merge bits from prev word static inline unsigned short borrow_lo(const unsigned short a[], int ind, int minind, int p) { if (ind > minind) return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1)); else return (a[ind] << (BITSTRBITS - 1 - p)); } // same with bounds check (for masks shorter than patterns) static inline unsigned short safe_borrow_hi(const unsigned short a[], int ind, int maxind, int p) { if (ind > maxind) return 0; else if (ind == maxind) return(a[ind] >> p); else return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p)); } static inline unsigned short safe_borrow_lo(const unsigned short a[], int ind, int minind, int p) { if (ind < minind) return 0; else if (ind == minind) return (a[ind] << (BITSTRBITS - 1 - p)); else return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1)); } // copy bits from a word boundary static inline void bit_copy(const unsigned short* ss, unsigned short* ds, int nbits) { if (ss != ds) { int n = (unsigned)(nbits) / BITSTRBITS; if (n > 0) bcopy((void*)ss, (void*)ds, n * sizeof(short)); unsigned short m = ONES << (nbits & (BITSTRBITS - 1)); ds[n] = (ss[n] & ~m) | (ds[n] & m); } } // clear bits from a word boundary static inline void bit_clear(unsigned short* ds, int nbits) { int n = (unsigned)(nbits) / BITSTRBITS; if (n > 0) bzero((void*)ds, n * sizeof(short)); ds[n] &= ONES << (nbits & (BITSTRBITS - 1)); } // Copy ss from starts to fences-1 into ds starting at startd. // This will work even if ss & ds overlap. // The g++ optimizer does very good things with the messy shift expressions! static void bit_transfer(const unsigned short* ss, int starts, int fences, unsigned short* ds, int startd) { if (starts >= fences || ss == 0 || (ss == ds && starts == startd)) return; int sind = BitStr_index(starts); int spos = BitStr_pos(starts); int dind = BitStr_index(startd); int dpos = BitStr_pos(startd); if (spos == 0 && dpos == 0) { bit_copy(&ss[sind], &ds[dind], fences - starts); return; } int ends = fences - 1; int endsind = BitStr_index(ends); int endspos = BitStr_pos(ends); int endd = startd + (ends - starts); int enddind = BitStr_index(endd); int enddpos = BitStr_pos(endd); if (dind == enddind) { if (sind == endsind) ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | (ONES << (enddpos + 1)))) | (((ss[sind] >> spos) << dpos) & ~((ONES >> (BITSTRBITS - dpos)) | (ONES << (enddpos + 1)))); else ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | (ONES << (enddpos + 1)))) | ((((ss[sind] >> spos) | (ss[sind+1] << (BITSTRBITS - spos))) << dpos) & ~((ONES >> (BITSTRBITS - dpos)) | (ONES << (enddpos + 1)))); return; } else if (sind == endsind) { unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | (((ss[sind] << (BITSTRBITS - 1 - endspos)) >> (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1))); ds[dind] = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) | (((ss[sind] >> spos) << dpos) & ~(ONES >> (BITSTRBITS - dpos))); ds[enddind] = saveend; return; } unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | ((((ss[endsind] << (BITSTRBITS - 1 - endspos)) | (ss[endsind-1] >> (endspos + 1))) >> (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1))); unsigned short savestart = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) | ((((ss[sind] >> spos) | (ss[sind+1] << (BITSTRBITS - spos))) << dpos) & ~(ONES >> (BITSTRBITS - dpos))); if (ds != ss || startd < starts) { int pos = spos - dpos; if (pos < 0) pos += BITSTRBITS; else ++sind; for (;;) // lag by one in case of overlaps { if (dind == enddind - 1) { ds[dind] = savestart; ds[enddind] = saveend; return; } else { unsigned short tmp = ss[sind] >> pos; if (++sind <= endsind) tmp |= ss[sind] << (BITSTRBITS - pos); ds[dind++] = savestart; savestart = tmp; } } } else { int pos = endspos - enddpos; if (pos <= 0) { pos += BITSTRBITS; --endsind; } for (;;) { if (enddind == dind + 1) { ds[enddind] = saveend; ds[dind] = savestart; return; } else { unsigned short tmp = ss[endsind] << (BITSTRBITS - pos); if (--endsind >= sind) tmp |= ss[endsind] >> pos; ds[enddind--] = saveend; saveend = tmp; } } } } // allocate a new rep; pad to near a power of two inline static BitStrRep* BSnew(int newlen) { size_t siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(short) + MALLOC_MIN_OVERHEAD; size_t allocsiz = MINBitStrRep_SIZE;; while (allocsiz < siz) allocsiz <<= 1; allocsiz -= MALLOC_MIN_OVERHEAD; if (allocsiz >= MAXBitStrRep_SIZE * sizeof(short)) (*lib_error_handler)("BitString", "Requested length out of range"); BitStrRep* rep = (BitStrRep *) new char[allocsiz]; bzero(rep, allocsiz); rep->sz = (allocsiz - sizeof(BitStrRep) + sizeof(short)) / sizeof(short); return rep; } BitStrRep* BStr_alloc(BitStrRep* old, const unsigned short* src, int startpos, int endp, int newlen) { if (old == &_nilBitStrRep) old = 0; if (newlen < 0) newlen = 0; int news = BitStr_len(newlen); BitStrRep* rep; if (old == 0 || news > old->sz) rep = BSnew(newlen); else rep = old; rep->len = newlen; if (src != 0 && endp > 0 && (src != rep->s || startpos > 0)) bit_transfer(src, startpos, endp, rep->s, 0); check_last(rep); if (old != rep && old != 0) delete old; return rep; } BitStrRep* BStr_resize(BitStrRep* old, int newlen) { BitStrRep* rep; if (newlen < 0) newlen = 0; int news = BitStr_len(newlen); if (old == 0 || old == &_nilBitStrRep) { rep = BSnew(newlen); } else if (news > old->sz) { rep = BSnew(newlen); bcopy(old->s, rep->s, BitStr_len(old->len) * sizeof(short)); delete old; } else rep = old; rep->len = newlen; check_last(rep); return rep; } BitStrRep* BStr_copy(BitStrRep* old, const BitStrRep* src) { BitStrRep* rep; if (old == src && old != &_nilBitStrRep) return old; if (old == &_nilBitStrRep) old = 0; if (src == &_nilBitStrRep) src = 0; if (src == 0) { if (old == 0) rep = BSnew(0); else rep = old; rep->len = 0; } else { int newlen = src->len; int news = BitStr_len(newlen); if (old == 0 || news > old->sz) { rep = BSnew(newlen); if (old != 0) delete old; } else rep = old; bcopy(src->s, rep->s, news * sizeof(short)); rep->len = newlen; } check_last(rep); return rep; } int operator == (const BitString& x, const BitString& y) { return x.rep->len == y.rep->len && bcmp((void*)x.rep->s, (void*)y.rep->s, BitStr_len(x.rep->len) * sizeof(short)) == 0; } int operator <= (const BitString& x, const BitString& y) { unsigned int xl = x.rep->len; unsigned int yl = y.rep->len; if (xl > yl) return 0; const unsigned short* xs = x.rep->s; const unsigned short* topx = &(xs[BitStr_len(xl)]); const unsigned short* ys = y.rep->s; while (xs < topx) { unsigned short a = *xs++; unsigned short b = *ys++; if ((a | b) != b) return 0; } return 1; } int operator < (const BitString& x, const BitString& y) { unsigned short xl = x.rep->len; unsigned short yl = y.rep->len; if (xl > yl) return 0; const unsigned short* xs = x.rep->s; const unsigned short* ys = y.rep->s; const unsigned short* topx = &(xs[BitStr_len(xl)]); const unsigned short* topy = &(ys[BitStr_len(yl)]); int one_diff = 0; while (xs < topx) { unsigned short a = *xs++; unsigned short b = *ys++; unsigned short c = a | b; if (c != b) return 0; else if (c != a) one_diff = 1; } if (one_diff) return 1; else { while (ys < topy) if (*ys++ != 0) return 1; return 0; } } int lcompare(const BitString& x, const BitString& y) { unsigned int xl = x.rep->len; unsigned int yl = y.rep->len; const unsigned short* xs = x.rep->s; const unsigned short* topx = &(xs[BitStr_len(xl)]); const unsigned short* ys = y.rep->s; const unsigned short* topy = &(ys[BitStr_len(yl)]); while (xs < topx && ys < topy) { unsigned short a = *xs++; unsigned short b = *ys++; if (a != b) { unsigned short mask = 1; for (;;) { unsigned short abit = (a & mask) != 0; unsigned short bbit = (b & mask) != 0; int diff = abit - bbit; if (diff != 0) return diff; else mask <<= 1; } } } return xl - yl; } int BitString::count(unsigned int b) const { check_last(rep); int xwds = BitStr_len(rep->len); int xlast = BitStr_pos(rep->len); int l = 0; const unsigned short* s = rep->s; const unsigned short* tops = &(s[xwds - 1]); unsigned short a; int i; if (b != 0) { while (s < tops) { a = *s++; for (i = 0; i < BITSTRBITS && a != 0; ++i) { if (a & 1) ++l; a >>= 1; } } a = *s; for (i = 0; i < xlast && a != 0; ++i) { if (a & 1) ++l; a >>= 1; } } else { unsigned short maxbit = 1 << (BITSTRBITS - 1); while (s < tops) { a = *s++; for (i = 0; i < BITSTRBITS; ++i) { if ((a & maxbit) == 0) ++l; a <<= 1; } } maxbit = 1 << (xlast - 1); a = *s; for (i = 0; i < xlast; ++i) { if ((a & maxbit) == 0) ++l; a <<= 1; } } return l; } BitStrRep* cmpl(const BitStrRep* src, BitStrRep* r) { r = BStr_copy(r, src); unsigned short* rs = r->s; unsigned short* topr = &(rs[BitStr_len(r->len)]); while (rs < topr) { unsigned short cmp = ~(*rs); *rs++ = cmp; } check_last(r); return r; } BitStrRep* and(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) { int xrsame = x == r; int yrsame = y == r; unsigned int xl = x->len; unsigned int yl = y->len; unsigned int rl = (xl <= yl)? xl : yl; r = BStr_resize(r, rl); unsigned short* rs = r->s; unsigned short* topr = &(rs[BitStr_len(rl)]); const unsigned short* xs = (xrsame)? rs : x->s; const unsigned short* ys = (yrsame)? rs : y->s; while (rs < topr) *rs++ = *xs++ & *ys++; check_last(r); return r; } BitStrRep* or(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) { unsigned int xl = x->len; unsigned int yl = y->len; unsigned int rl = (xl >= yl)? xl : yl; int xrsame = x == r; int yrsame = y == r; r = BStr_resize(r, rl); unsigned short* rs = r->s; const unsigned short* xs = (xrsame)? rs : x->s; const unsigned short* topx = &(xs[BitStr_len(xl)]); const unsigned short* ys = (yrsame)? rs : y->s; const unsigned short* topy = &(ys[BitStr_len(yl)]); if (xl <= yl) { while (xs < topx) *rs++ = *xs++ | *ys++; if (rs != ys) while (ys < topy) *rs++ = *ys++; } else { while (ys < topy) *rs++ = *xs++ | *ys++; if (rs != xs) while (xs < topx) *rs++ = *xs++; } check_last(r); return r; } BitStrRep* xor(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) { unsigned int xl = x->len; unsigned int yl = y->len; unsigned int rl = (xl >= yl)? xl : yl; int xrsame = x == r; int yrsame = y == r; r = BStr_resize(r, rl); unsigned short* rs = r->s; const unsigned short* xs = (xrsame)? rs : x->s; const unsigned short* topx = &(xs[BitStr_len(xl)]); const unsigned short* ys = (yrsame)? rs : y->s; const unsigned short* topy = &(ys[BitStr_len(yl)]); if (xl <= yl) { while (xs < topx) *rs++ = *xs++ ^ *ys++; if (rs != ys) while (ys < topy) *rs++ = *ys++; } else { while (ys < topy) *rs++ = *xs++ ^ *ys++; if (rs != xs) while (xs < topx) *rs++ = *xs++; } check_last(r); return r; } BitStrRep* diff(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) { unsigned int xl = x->len; unsigned int yl = y->len; int xrsame = x == y; int yrsame = y == r; r = BStr_resize(r, xl); unsigned short* rs = r->s; const unsigned short* xs = (xrsame)? rs : x->s; const unsigned short* topx = &(xs[BitStr_len(xl)]); const unsigned short* ys = (yrsame)? rs : y->s; const unsigned short* topy = &(ys[BitStr_len(yl)]); if (xl <= yl) { while (xs < topx) *rs++ = *xs++ & ~(*ys++); } else { while (ys < topy) *rs++ = *xs++ & ~(*ys++); if (rs != xs) while (xs < topx) *rs++ = *xs++; } check_last(r); return r; } BitStrRep* cat(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) { unsigned int xl = x->len; unsigned int yl = y->len; unsigned int rl = xl + yl; int xrsame = x == r; int yrsame = y == r; if (yrsame) { if (xrsame) { r = BStr_resize(r, rl); bit_transfer(r->s, 0, yl, r->s, xl); } else { BitStrRep* tmp = BStr_copy(0, y); r = BStr_resize(r, rl); bit_copy(x->s, r->s, xl); bit_transfer(tmp->s, 0, yl, r->s, xl); delete tmp; } } else { r = BStr_resize(r, rl); if (!xrsame) bit_copy(x->s, r->s, xl); bit_transfer(y->s, 0, yl, r->s, xl); } check_last(r); return r; } BitStrRep* cat(const BitStrRep* x, unsigned int bit, BitStrRep* r) { unsigned int xl = x->len; int xrsame = x == r; r = BStr_resize(r, xl+1); if (!xrsame) bit_copy(x->s, r->s, xl); if (bit) r->s[BitStr_index(xl)] |= (1 << (BitStr_pos(xl))); else r->s[BitStr_index(xl)] &= ~(1 << (BitStr_pos(xl))); check_last(r); return r; } BitStrRep* lshift(const BitStrRep* x, int s, BitStrRep* r) { int xrsame = x == r; int xl = x->len; int rl = xl + s; if (s == 0) r = BStr_copy(r, x); else if (rl <= 0) { r = BStr_resize(r, 0); r->len = 0; r->s[0] = 0; } else if (s > 0) { r = BStr_resize(r, rl); const unsigned short* xs = (xrsame)? r->s : x->s; bit_transfer(xs, 0, xl, r->s, s); bit_clear(r->s, s); } else if (xrsame) { r = BStr_resize(r, xl); r->len = rl; bit_transfer(r->s, -s, xl, r->s, 0); } else { r = BStr_resize(r, rl); bit_transfer(x->s, -s, xl, r->s, 0); } check_last(r); return r; } void BitString::set(int p) { if (p < 0) error("Illegal bit index"); if ((size_t)(p) >= rep->len) rep = BStr_resize(rep, p + 1); rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p))); } void BitString::assign(int p, unsigned int bit) { if (p < 0) error("Illegal bit index"); if ((size_t)(p) >= rep->len) rep = BStr_resize(rep, p + 1); if (bit) rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p))); else rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p))); } void BitString::clear(int p) { if (p < 0) error("Illegal bit index"); if ((size_t)(p) >= rep->len) rep = BStr_resize(rep, p + 1); rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p))); } void BitString::clear() { if (rep == &_nilBitStrRep) return; bit_clear(rep->s, rep->len); } void BitString::set() { if (rep == &_nilBitStrRep) return; unsigned short* s = rep->s; unsigned short* tops = &(s[BitStr_len(rep->len)]); while (s < tops) *s++ = ONES; check_last(rep); } void BitString::invert(int p) { if (p < 0) error("Illegal bit index"); if ((size_t)(p) >= rep->len) rep = BStr_resize(rep, p + 1); rep->s[BitStr_index(p)] ^= (1 << (BitStr_pos(p))); } void BitString::set(int from, int to) { if (from < 0 || from > to) error("Illegal bit index"); if ((size_t)(to) >= rep->len) rep = BStr_resize(rep, to+1); int ind1 = BitStr_index(from); int pos1 = BitStr_pos(from); int ind2 = BitStr_index(to); int pos2 = BitStr_pos(to); unsigned short* s = &(rep->s[ind1]); unsigned short m1 = lmask(pos1); unsigned short m2 = rmask(pos2); if (ind2 == ind1) *s |= m1 & m2; else { *s++ |= m1; unsigned short* top = &(rep->s[ind2]); *top |= m2; while (s < top) *s++ = ONES; } } void BitString::clear(int from, int to) { if (from < 0 || from > to) error("Illegal bit index"); if ((size_t)(to) >= rep->len) rep = BStr_resize(rep, to+1); int ind1 = BitStr_index(from); int pos1 = BitStr_pos(from); int ind2 = BitStr_index(to); int pos2 = BitStr_pos(to); unsigned short* s = &(rep->s[ind1]); unsigned short m1 = lmask(pos1); unsigned short m2 = rmask(pos2); if (ind2 == ind1) *s &= ~(m1 & m2); else { *s++ &= ~m1; unsigned short* top = &(rep->s[ind2]); *top &= ~m2; while (s < top) *s++ = 0; } } void BitString::invert(int from, int to) { if (from < 0 || from > to) error("Illegal bit index"); if ((size_t)(to) >= rep->len) rep = BStr_resize(rep, to+1); int ind1 = BitStr_index(from); int pos1 = BitStr_pos(from); int ind2 = BitStr_index(to); int pos2 = BitStr_pos(to); unsigned short* s = &(rep->s[ind1]); unsigned short m1 = lmask(pos1); unsigned short m2 = rmask(pos2); if (ind2 == ind1) *s ^= m1 & m2; else { *s++ ^= m1; unsigned short* top = &(rep->s[ind2]); *top ^= m2; while (s < top) { unsigned short cmp = ~(*s); *s++ = cmp; } } } int BitString::test(int from, int to) const { if (from < 0 || from > to || (size_t)(from) >= rep->len) return 0; int ind1 = BitStr_index(from); int pos1 = BitStr_pos(from); int ind2 = BitStr_index(to); int pos2 = BitStr_pos(to); if ((size_t)(to) >= rep->len) { ind2 = BitStr_index(rep->len - 1); pos2 = BitStr_pos(rep->len - 1); } const unsigned short* s = &(rep->s[ind1]); unsigned short m1 = lmask(pos1); unsigned short m2 = rmask(pos2); if (ind2 == ind1) return (*s & m1 & m2) != 0; else { if (*s++ & m1) return 1; unsigned short* top = &(rep->s[ind2]); if (*top & m2) return 1; while (s < top) if (*s++ != 0) return 1; return 0; } } int BitString::next(int p, unsigned int b) const { if ((size_t)(++p) >= rep->len) return -1; int ind = BitStr_index(p); int pos = BitStr_pos(p); int l = BitStr_len(rep->len); int j = ind; const unsigned short* s = rep->s; unsigned short a = s[j] >> pos; int i = pos; if (b != 0) { for (; i < BITSTRBITS && a != 0; ++i) { if (a & 1) return j * BITSTRBITS + i; a >>= 1; } for (++j; j < l; ++j) { a = s[j]; for (i = 0; i < BITSTRBITS && a != 0; ++i) { if (a & 1) return j * BITSTRBITS + i; a >>= 1; } } return -1; } else { int last = BitStr_pos(rep->len); if (j == l - 1) { for (; i < last; ++i) { if ((a & 1) == 0) return j * BITSTRBITS + i; a >>= 1; } return -1; } for (; i < BITSTRBITS; ++i) { if ((a & 1) == 0) return j * BITSTRBITS + i; a >>= 1; } for (++j; j < l - 1; ++j) { a = s[j]; if (a != ONES) { for (i = 0; i < BITSTRBITS; ++i) { if ((a & 1) == 0) return j * BITSTRBITS + i; a >>= 1; } } } a = s[j]; for (i = 0; i < last; ++i) { if ((a & 1) == 0) return j * BITSTRBITS + i; a >>= 1; } return -1; } } int BitString::previous(int p, unsigned int b) const { if (--p < 0) return -1; int ind = BitStr_index(p); int pos = BitStr_pos(p); const unsigned short* s = rep->s; if ((size_t)(p) >= rep->len) { ind = BitStr_index(rep->len - 1); pos = BitStr_pos(rep->len - 1); } int j = ind; unsigned short a = s[j]; int i = pos; unsigned short maxbit = 1 << pos; if (b != 0) { for (; i >= 0 && a != 0; --i) { if (a & maxbit) return j * BITSTRBITS + i; a <<= 1; } maxbit = 1 << (BITSTRBITS - 1); for (--j; j >= 0; --j) { a = s[j]; for (i = BITSTRBITS - 1; i >= 0 && a != 0; --i) { if (a & maxbit) return j * BITSTRBITS + i; a <<= 1; } } return -1; } else { if (a != ONES) { for (; i >= 0; --i) { if ((a & maxbit) == 0) return j * BITSTRBITS + i; a <<= 1; } } maxbit = 1 << (BITSTRBITS - 1); for (--j; j >= 0; --j) { a = s[j]; if (a != ONES) { for (i = BITSTRBITS - 1; i >= 0; --i) { if ((a & maxbit) == 0) return j * BITSTRBITS + i; a <<= 1; } } } return -1; } } int BitString::search(int startx, int lengthx, const unsigned short* ys, int starty, int lengthy) const { const unsigned short* xs = rep->s; int ylen = lengthy - starty; int righty = lengthy - 1; int rev = startx < 0; if (rev) { int leftx = 0; int rightx = lengthx + startx; startx = rightx - ylen + 1; if (ylen == 0) return startx; if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1; int xind = BitStr_index(startx); int xpos = BitStr_pos(startx); int yind = BitStr_index(starty); int ypos = BitStr_pos(starty); int rightxind = BitStr_index(rightx); unsigned short x = borrow_hi(xs, xind, rightxind, xpos); int rightyind = BitStr_index(righty); int rightypos = BitStr_pos(righty); unsigned short y = borrow_hi(ys, yind, rightyind, ypos); unsigned short ymask; if (yind == rightyind) ymask = rmask(rightypos); else if (yind+1 == rightyind) ymask = rmask(BITSTRBITS - ypos + rightypos + 1); else ymask = ONES; int p = startx; for (;;) { if ((x & ymask) == y) { int xi = xind; int yi = yind; for (;;) { if (++yi > rightyind || ++xi > rightxind) return p; unsigned short tx = borrow_hi(xs, xi, rightxind, xpos); unsigned short ty = borrow_hi(ys, yi, rightyind, ypos); if (yi == rightyind) tx &= rmask(rightypos); else if (yi+1 == rightyind) tx &= rmask(BITSTRBITS - ypos + rightypos + 1); if (tx != ty) break; } } if (--p < leftx) return -1; if (--xpos < 0) { xpos = BITSTRBITS - 1; --xind; } x = borrow_hi(xs, xind, rightxind, xpos); } } else { int rightx = lengthx - 1; if (ylen == 0) return startx; if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1; int xind = BitStr_index(startx); int xpos = BitStr_pos(startx); int yind = BitStr_index(starty); int ypos = BitStr_pos(starty); int rightxind = BitStr_index(rightx); unsigned short x = borrow_hi(xs, xind, rightxind, xpos); unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos); int rightyind = BitStr_index(righty); int rightypos = BitStr_pos(righty); unsigned short y = borrow_hi(ys, yind, rightyind, ypos); unsigned short ymask; if (yind == rightyind) ymask = rmask(rightypos); else if (yind+1 == rightyind) ymask = rmask(BITSTRBITS - ypos + rightypos + 1); else ymask = ONES; int p = startx; for (;;) { if ((x & ymask) == y) { int xi = xind; int yi = yind; for (;;) { if (++yi > rightyind || ++xi > rightxind) return p; unsigned short tx = borrow_hi(xs, xi, rightxind, xpos); unsigned short ty = borrow_hi(ys, yi, rightyind, ypos); if (yi == rightyind) tx &= rmask(rightypos); else if (yi+1 == rightyind) tx &= rmask(BITSTRBITS - ypos + rightypos + 1); if (tx != ty) break; } } if (++p > rightx) return -1; if (++xpos == BITSTRBITS) { xpos = 0; x = xs[++xind]; nextx = (xind >= rightxind) ? 0 : xs[xind+1]; } else { x >>= 1; if (nextx & 1) x |= MAXBIT; nextx >>= 1; } } } } int BitPattern::search(const unsigned short* xs, int startx, int lengthx) const { const unsigned short* ys = pattern.rep->s; const unsigned short* ms = mask.rep->s; int righty = pattern.rep->len - 1; int rightm = mask.rep->len - 1; int rev = startx < 0; if (rev) { int leftx = 0; int rightx = lengthx + startx; startx = rightx - righty; if (righty < 0) return startx; if (startx < 0 || startx >= lengthx) return -1; int xind = BitStr_index(startx); int xpos = BitStr_pos(startx); int rightxind = BitStr_index(rightx); int rightmind = BitStr_index(rightm); int rightyind = BitStr_index(righty); unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos); unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0); unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m; int p = startx; for (;;) { if ((x & m) == y) { int xi = xind; int yi = 0; for (;;) { if (++yi > rightyind || ++xi > rightxind) return p; unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0); unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0); unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos); if ((tx & tm) != (ty & tm)) break; } } if (--p < leftx) return -1; if (--xpos < 0) { xpos = BITSTRBITS - 1; --xind; } x = safe_borrow_hi(xs, xind, rightxind, xpos); } } else { int rightx = lengthx - 1; if (righty < 0) return startx; if (startx < 0 || startx >= lengthx) return -1; int xind = BitStr_index(startx); int xpos = BitStr_pos(startx); int rightxind = BitStr_index(rightx); int rightmind = BitStr_index(rightm); int rightyind = BitStr_index(righty); unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos); unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0); unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m; unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos); int p = startx; for (;;) { if ((x & m) == y) { int xi = xind; int yi = 0; for (;;) { if (++yi > rightyind || ++xi > rightxind) return p; unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0); unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0); unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos); if ((tx & tm) != (ty & tm)) break; } } if (++p > rightx) return -1; if (++xpos == BITSTRBITS) { xpos = 0; x = xs[++xind]; nextx = (xind >= rightxind) ? 0 : xs[xind+1]; } else { x >>= 1; if (nextx & 1) x |= MAXBIT; nextx >>= 1; } } } } int BitString::match(int startx, int lengthx, int exact, const unsigned short* ys, int starty, int yl) const { const unsigned short* xs = rep->s; int ylen = yl - starty; int righty = yl - 1; int rightx; int rev = startx < 0; if (rev) { rightx = lengthx + startx; startx = rightx - ylen + 1; if (exact && startx != 0) return 0; } else { rightx = lengthx - 1; if (exact && rightx - startx != righty) return 0; } if (ylen == 0) return 1; if (righty < 0 || startx < 0 || startx >= lengthx) return 0; int xi = BitStr_index(startx); int xpos = BitStr_pos(startx); int yi = BitStr_index(starty); int ypos = BitStr_pos(starty); int rightxind = BitStr_index(rightx); int rightyind = BitStr_index(righty); int rightypos = BitStr_pos(righty); for (;;) { unsigned short x = borrow_hi(xs, xi, rightxind, xpos); unsigned short y = borrow_hi(ys, yi, rightyind, ypos); if (yi == rightyind) x &= rmask(rightypos); else if (yi+1 == rightyind) x &= rmask(BITSTRBITS - ypos + rightypos + 1); if (x != y) return 0; else if (++yi > rightyind || ++xi > rightxind) return 1; } } int BitPattern::match(const unsigned short* xs, int startx, int lengthx, int exact) const { const unsigned short* ys = pattern.rep->s; int righty = pattern.rep->len - 1; unsigned short* ms = mask.rep->s; int rightm = mask.rep->len - 1; int rightx; int rev = startx < 0; if (rev) { rightx = lengthx + startx; startx = rightx - righty; if (exact && startx != 0) return 0; } else { rightx = lengthx - 1; if (exact && rightx - startx != righty) return 0; } if (righty < 0) return 1; if (startx < 0 || startx >= lengthx) return 0; int xind = BitStr_index(startx); int xpos = BitStr_pos(startx); int yind = 0; int rightxind = BitStr_index(rightx); int rightyind = BitStr_index(righty); int rightmind = BitStr_index(rightm); for(;;) { unsigned short m = safe_borrow_hi(ms, yind, rightmind, 0); unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos) & m; unsigned short y = safe_borrow_hi(ys, yind, rightyind, 0) & m; if (x != y) return 0; else if (++yind > rightyind || ++xind > rightxind) return 1; } } void BitSubString::operator = (const BitString& y) { if (&S == &_nil_BitString) return; BitStrRep* targ = S.rep; unsigned int ylen = y.rep->len; int sl = targ->len - len + ylen; if (y.rep == targ || ylen > len) { BitStrRep* oldtarg = targ; targ = BStr_alloc(0, 0, 0, 0, sl); bit_transfer(oldtarg->s, 0, pos, targ->s, 0); bit_transfer(y.rep->s, 0, ylen, targ->s, pos); bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + ylen); delete oldtarg; } else if (len == ylen) bit_transfer(y.rep->s, 0, len, targ->s, pos); else if (ylen < len) { bit_transfer(y.rep->s, 0, ylen, targ->s, pos); bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + ylen); targ->len = sl; } check_last(targ); S.rep = targ; } void BitSubString::operator = (const BitSubString& y) { if (&S == &_nil_BitString) return; BitStrRep* targ = S.rep; if (len == 0 || pos >= targ->len) return; int sl = targ->len - len + y.len; if (y.S.rep == targ || y.len > len) { BitStrRep* oldtarg = targ; targ = BStr_alloc(0, 0, 0, 0, sl); bit_copy(oldtarg->s, targ->s, pos); bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos); bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + y.len); delete oldtarg; } else if (len == y.len) bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos); else if (y.len < len) { bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos); bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + y.len); targ->len = sl; } check_last(targ); S.rep = targ; } BitSubString BitString::at(int first, int len) { return _substr(first, len); } BitSubString BitString::before(int pos) { return _substr(0, pos); } BitSubString BitString::after(int pos) { return _substr(pos + 1, rep->len - (pos + 1)); } BitSubString BitString::at(const BitString& y, int startpos) { int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len); return _substr(first, y.rep->len); } BitSubString BitString::before(const BitString& y, int startpos) { int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len); return _substr(0, last); } BitSubString BitString::after(const BitString& y, int startpos) { int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len); if (first >= 0) first += y.rep->len; return _substr(first, rep->len - first); } BitSubString BitString::at(const BitSubString& y, int startpos) { int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len); return _substr(first, y.len); } BitSubString BitString::before(const BitSubString& y, int startpos) { int last = search(startpos, rep->len, y.S.rep->s, y.pos, y.len); return _substr(0, last); } BitSubString BitString::after(const BitSubString& y, int startpos) { int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len); if (first >= 0) first += y.len; return _substr(first, rep->len - first); } BitSubString BitString::at(const BitPattern& r, int startpos) { int first = r.search(rep->s, startpos, rep->len); return _substr(first, r.pattern.rep->len); } BitSubString BitString::before(const BitPattern& r, int startpos) { int first = r.search(rep->s, startpos, rep->len); return _substr(0, first); } BitSubString BitString::after(const BitPattern& r, int startpos) { int first = r.search(rep->s, startpos, rep->len); if (first >= 0) first += r.pattern.rep->len; return _substr(first, rep->len - first); } #if defined(__GNUG__) && !defined(NO_NRV) BitString common_prefix(const BitString& x, const BitString& y, int startpos) return r { unsigned int xl = x.rep->len; unsigned int yl = y.rep->len; unsigned int startx, starty; if (startpos < 0) { startx = xl + startpos; starty = yl + startpos; } else startx = starty = startpos; if (startx >= xl || starty >= yl) return; const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]); unsigned short a = *xs++; unsigned int xp = startx; const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]); unsigned short b = *ys++; unsigned int yp = starty; for(; xp < xl && yp < yl; ++xp, ++yp) { unsigned short xbit = 1 << (BitStr_pos(xp)); unsigned short ybit = 1 << (BitStr_pos(yp)); if (((a & xbit) == 0) != ((b & ybit) == 0)) break; if (xbit == MAXBIT) a = *xs++; if (ybit == MAXBIT) b = *ys++; } r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx); } BitString common_suffix(const BitString& x, const BitString& y, int startpos) return r; { unsigned int xl = x.rep->len; unsigned int yl = y.rep->len; unsigned int startx, starty; if (startpos < 0) { startx = xl + startpos; starty = yl + startpos; } else startx = starty = startpos; if (startx >= xl || starty >= yl) return; const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]); unsigned short a = *xs--; int xp = startx; const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]); unsigned short b = *ys--; int yp = starty; for(; xp >= 0 && yp >= 0; --xp, --yp) { unsigned short xbit = 1 << (BitStr_pos(xp)); unsigned short ybit = 1 << (BitStr_pos(yp)); if (((a & xbit) == 0) != ((b & ybit) == 0)) break; if (xbit == 1) a = *xs--; if (ybit == 1) b = *ys--; } r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp); } BitString reverse(const BitString& x) return r { size_t yl = x.rep->len; BitStrRep* y = BStr_resize(0, yl); if (yl > 0) { const unsigned short* ls = x.rep->s; unsigned short lm = 1; unsigned short* rs = &(y->s[BitStr_index(yl - 1)]); unsigned short rm = 1 << (BitStr_pos(yl - 1)); for (size_t l = 0; l < yl; ++l) { if (*ls & lm) *rs |= rm; if (lm == MAXBIT) { ++ls; lm = 1; } else lm <<= 1; if (rm == 1) { --rs; rm = MAXBIT; } else rm >>= 1; } } r.rep = y; } BitString atoBitString(const char* s, char f, char t) return res { int sl = strlen(s); BitStrRep* r = BStr_resize(0, sl); if (sl != 0) { unsigned int rl = 0; unsigned short* rs = r->s; unsigned short a = 0; unsigned short m = 1; unsigned int i = 0; for(;;) { char ch = s[i]; if (ch != t && ch != f) { *rs = a; break; } ++rl; if (ch == t) a |= m; if (++i == sl) { *rs = a; break; } else if (i % BITSTRBITS == 0) { *rs++ = a; a = 0; m = 1; } else m <<= 1; } r = BStr_resize(r, rl); } res.rep = r; } BitPattern atoBitPattern(const char* s, char f,char t,char x) return r { int sl = strlen(s); if (sl != 0) { unsigned int rl = 0; r.pattern.rep = BStr_resize(r.pattern.rep, sl); r.mask.rep = BStr_resize(r.mask.rep, sl); unsigned short* rs = r.pattern.rep->s; unsigned short* ms = r.mask.rep->s; unsigned short a = 0; unsigned short b = 0; unsigned short m = 1; unsigned int i = 0; for(;;) { char ch = s[i]; if (ch != t && ch != f && ch != x) { *rs = a; *ms = b; break; } ++rl; if (ch == t) { a |= m; b |= m; } else if (ch == f) { b |= m; } if (++i == sl) { *rs = a; *ms = b; break; } else if (i % BITSTRBITS == 0) { *rs++ = a; *ms++ = b; a = 0; b = 0; m = 1; } else m <<= 1; } r.pattern.rep = BStr_resize(r.pattern.rep, rl); r.mask.rep = BStr_resize(r.mask.rep, rl); } return; } #else /* NO_NRV */ BitString common_prefix(const BitString& x, const BitString& y, int startpos) { BitString r; unsigned int xl = x.rep->len; unsigned int yl = y.rep->len; int startx, starty; if (startpos < 0) { startx = xl + startpos; starty = yl + startpos; } else startx = starty = startpos; if (startx < 0 || startx >= xl || starty < 0 || starty >= yl) return r; const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]); unsigned short a = *xs++; int xp = startx; const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]); unsigned short b = *ys++; int yp = starty; for(; xp < xl && yp < yl; ++xp, ++yp) { unsigned short xbit = 1 << (BitStr_pos(xp)); unsigned short ybit = 1 << (BitStr_pos(yp)); if (((a & xbit) == 0) != ((b & ybit) == 0)) break; if (xbit == MAXBIT) a = *xs++; if (ybit == MAXBIT) b = *ys++; } r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx); return r; } BitString common_suffix(const BitString& x, const BitString& y, int startpos) { BitString r; unsigned int xl = x.rep->len; unsigned int yl = y.rep->len; int startx, starty; if (startpos < 0) { startx = xl + startpos; starty = yl + startpos; } else startx = starty = startpos; if (startx < 0 || startx >= xl || starty < 0 || starty >= yl) return r; const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]); unsigned short a = *xs--; int xp = startx; const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]); unsigned short b = *ys--; int yp = starty; for(; xp >= 0 && yp >= 0; --xp, --yp) { unsigned short xbit = 1 << (BitStr_pos(xp)); unsigned short ybit = 1 << (BitStr_pos(yp)); if (((a & xbit) == 0) != ((b & ybit) == 0)) break; if (xbit == 1) a = *xs--; if (ybit == 1) b = *ys--; } r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp); return r; } BitString reverse(const BitString& x) { BitString r; size_t yl = x.rep->len; BitStrRep* y = BStr_resize(0, yl); if (yl > 0) { const unsigned short* ls = x.rep->s; unsigned short lm = 1; unsigned short* rs = &(y->s[BitStr_index(yl - 1)]); unsigned short rm = 1 << (BitStr_pos(yl - 1)); for (size_t l = 0; l < yl; ++l) { if (*ls & lm) *rs |= rm; if (lm == MAXBIT) { ++ls; lm = 1; } else lm <<= 1; if (rm == 1) { --rs; rm = MAXBIT; } else rm >>= 1; } } r.rep = y; return r; } BitString atoBitString(const char* s, char f, char t) { BitString res; size_t sl = strlen(s); BitStrRep* r = BStr_resize(0, sl); if (sl != 0) { size_t rl = 0; unsigned short* rs = r->s; unsigned short a = 0; unsigned short m = 1; size_t i = 0; for(;;) { char ch = s[i]; if (ch != t && ch != f) { *rs = a; break; } ++rl; if (ch == t) a |= m; if (++i == sl) { *rs = a; break; } else if (i % BITSTRBITS == 0) { *rs++ = a; a = 0; m = 1; } else m <<= 1; } r = BStr_resize(r, rl); } res.rep = r; return res; } BitPattern atoBitPattern(const char* s, char f,char t,char x) { BitPattern r; size_t sl = strlen(s); if (sl != 0) { size_t rl = 0; r.pattern.rep = BStr_resize(r.pattern.rep, sl); r.mask.rep = BStr_resize(r.mask.rep, sl); unsigned short* rs = r.pattern.rep->s; unsigned short* ms = r.mask.rep->s; unsigned short a = 0; unsigned short b = 0; unsigned short m = 1; size_t i = 0; for(;;) { char ch = s[i]; if (ch != t && ch != f && ch != x) { *rs = a; *ms = b; break; } ++rl; if (ch == t) { a |= m; b |= m; } else if (ch == f) { b |= m; } if (++i == sl) { *rs = a; *ms = b; break; } else if (i % BITSTRBITS == 0) { *rs++ = a; *ms++ = b; a = 0; b = 0; m = 1; } else m <<= 1; } r.pattern.rep = BStr_resize(r.pattern.rep, rl); r.mask.rep = BStr_resize(r.mask.rep, rl); } return r; } #endif extern AllocRing _libgxx_fmtq; const char* BitStringtoa(const BitString& x, char f, char t) { int wrksiz = x.length() + 2; char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz); char* fmt = fmtbase; size_t xl = x.rep->len; const unsigned short* s = x.rep->s; unsigned short a = 0; for (size_t i = 0; i < xl; ++i) { if (i % BITSTRBITS == 0) a = *s++; *fmt++ = (a & 1)? t : f; a >>= 1; } *fmt = 0; return fmtbase; } ostream& operator << (ostream& s, const BitString& x) { return s << BitStringtoa(x); } const char* BitPatterntoa(const BitPattern& p, char f,char t,char x) { size_t pl = p.pattern.rep->len; size_t ml = p.mask.rep->len; size_t l = (pl <= ml)? pl : ml; size_t wrksiz = l + 2; char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz); char* fmt = fmtbase; const unsigned short* ps = p.pattern.rep->s; const unsigned short* ms = p.mask.rep->s; unsigned short a = 0; unsigned short m = 0; for (size_t i = 0; i < l; ++i) { if (i % BITSTRBITS == 0) { a = *ps++; m = *ms++; } if (m & 1) *fmt++ =(a & 1)? t : f; else *fmt++ = x; a >>= 1; m >>= 1; } *fmt = 0; return fmtbase; } ostream& operator << (ostream& s, const BitPattern& x) { return s << BitPatterntoa(x); } int BitString::OK() const { int v = rep != 0; // have a rep; v &= BitStr_len(rep->len) <= rep->sz; // within allocated size if (!v) error("invariant failure"); return v; } int BitSubString::OK() const { int v = S.OK(); // valid BitString v &= pos + len <= S.rep->len; // within bounds of targ if (!v) S.error("BitSubString invariant failure"); return v; } int BitPattern::OK() const { int v = pattern.OK() && mask.OK(); if (!v) pattern.error("BitPattern invariant failure"); return v; }