DataMuseum.dk

top - metrics - download

    Length: 41498 (0xa21a)
    Types: TextFile
    Names: »BitString.cc«

└─⟦a05ed705a⟧ Bits:30007078 DKUUG GNU 2/12/89
    └─⟦cc8755de2⟧ »./libg++-1.36.1.tar.Z« 
        └─⟦23757c458⟧ 
            └─⟦this⟧ »libg++/src/BitString.cc« 

TextFile

/* 
Copyright (C) 1988 Free Software Foundation
    written by Doug Lea (dl@rocky.oswego.edu)

This file is part of GNU CC.

GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY.  No author or distributor
accepts responsibility to anyone for the consequences of using it
or for whether it serves any particular purpose or works at all,
unless he says so in writing.  Refer to the GNU CC General Public
License for full details.

Everyone is granted permission to copy, modify and redistribute
GNU CC, but only under the conditions described in the
GNU CC General Public License.   A copy of this license is
supposed to have been given to you along with GNU CC so you
can know your rights and responsibilities.  It should be in a
file named COPYING.  Among other things, the copyright notice
and this notice must be preserved on all copies.  
*/

/* 
  BitString class implementation
 */

#include <BitString.h>
#include <std.h>
#include <values.h>
#include <Obstack.h>
#include <AllocQueue.h>

void BitString::error(char* msg)
{
  (*lib_error_handler)("BitString", msg);
}

//  globals

BitStrRep    _nilBitStrRep = {  0, 1, {0} };

static BitString _nil_BitString;


#define MINBitStrRep_SIZE  8
#define MAXBitStrRep_SIZE  (1 << (SHORTBITS - 1) - 1)
#define MALLOC_OVERHEAD    4

#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(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(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(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(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(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 are the same 
// The g++ optimizer does very good things with the messy shift expressions!

static void bit_transfer(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;
      }
    }
  }
}
  

inline static BitStrRep* BSnew(int newlen)
{
  unsigned int siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(short) 
    + MALLOC_OVERHEAD;
  unsigned int allocsiz = MINBitStrRep_SIZE;;
  while (allocsiz < siz) allocsiz <<= 1;
  allocsiz -= MALLOC_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, 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, BitStrRep* src)
{
  if (old == src) return old; 
  BitStrRep* rep;
  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 == (BitString& x, 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 <= (BitString& x, BitString& y)
{
  unsigned int  xl = x.rep->len;
  unsigned int  yl = y.rep->len;
  if (xl > yl)
    return 0;

  unsigned short* xs = x.rep->s;
  unsigned short* ys = y.rep->s;
  unsigned short* topx = &(xs[BitStr_len(xl)]);

  while (xs < topx)
  {
    unsigned short a = *xs++;
    unsigned short b = *ys++;
    if ((a | b) != b)
      return 0;
  }
  return 1;
}

int operator < (BitString& x, BitString& y)
{
  unsigned short xl = x.rep->len;
  unsigned short yl = y.rep->len;
  if (xl > yl)
    return 0;

  unsigned short* xs = x.rep->s;
  unsigned short* ys = y.rep->s;
  unsigned short* topx = &(xs[BitStr_len(xl)]);
  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(BitString& x, BitString& y)
{
  unsigned int  xl = x.rep->len;
  unsigned int  yl = y.rep->len;

  unsigned short* xs = x.rep->s;
  unsigned short* topx = &(xs[BitStr_len(xl)]);
  unsigned short* ys = y.rep->s;
  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(int b = 1)
{
  check_last(rep);
  int xwds = BitStr_len(rep->len);
  int xlast = BitStr_pos(rep->len);
  int l = 0;
  unsigned short* s = rep->s;
  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(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(BitStrRep* x, BitStrRep* y, BitStrRep* r)
{
  int xrsame = x == r;
  int yrsame = y == r;

  unsigned int  rl = x->len <? y->len;
  r = BStr_resize(r, rl);

  unsigned short* rs = r->s;
  unsigned short* topr = &(rs[BitStr_len(rl)]);
  unsigned short* xs = (xrsame)? rs : x->s;
  unsigned short* ys = (yrsame)? rs : y->s;

  while (rs < topr) *rs++ = *xs++ & *ys++;
  check_last(r);
  return r;
}

BitStrRep* or(BitStrRep* x, 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;

  r = BStr_resize(r, rl);

  unsigned short* rs = r->s;
  unsigned short* xs = (xrsame)? rs : x->s;
  unsigned short* topx = &(xs[BitStr_len(xl)]);
  unsigned short* ys = (yrsame)? rs : y->s;
  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(BitStrRep* x, 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;

  r = BStr_resize(r, rl);

  unsigned short* rs = r->s;
  unsigned short* xs = (xrsame)? rs : x->s;
  unsigned short* topx = &(xs[BitStr_len(xl)]);
  unsigned short* ys = (yrsame)? rs : y->s;
  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* difference(BitStrRep* x, 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;
  unsigned short* xs = (xrsame)? rs : x->s;
  unsigned short* topx = &(xs[BitStr_len(xl)]);
  unsigned short* ys = (yrsame)? rs : y->s;
  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* concat(BitStrRep* x, 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* concat(BitStrRep* x, 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* rshift(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);
    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 (p >= rep->len) rep = BStr_resize(rep, p + 1);
  rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
}

void BitString::assign(int p, int bit)
{
  if (p < 0) error("Illegal bit index");
  if (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 (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 (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 (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 (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 (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)
{
  if (from < 0 || from > to || 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 (to >= rep->len)
  {
    ind2 = BitStr_index(rep->len - 1);
    pos2 = BitStr_pos(rep->len - 1);
  }

  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, int b = 1)
{
  if (++p >= rep->len)
    return -1;

  int ind = BitStr_index(p);
  int pos = BitStr_pos(p);
  int l = BitStr_len(rep->len);

  int j = ind;
  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, int b = 1)
{
  if (--p < 0)
    return -1;

  int ind = BitStr_index(p);
  int pos = BitStr_pos(p);

  unsigned short* s = rep->s;

  if (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, 
                      unsigned short* ys, int starty, int lengthy)
{
  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(unsigned short* xs, int startx, int lengthx)
{
  unsigned short* ys = pattern.rep->s;
  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, 
                     unsigned short* ys, int starty, int yl)
{
  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(unsigned short* xs, int startx, int lengthx, int exact)
{
  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;
  }
}

BitSubString::BitSubString(BitString* x, int first, int l)
{
  if (first < 0 || l <= 0 || first + l > x->rep->len)
  {
    S = &_nil_BitString; pos = len = 0;
  }
  else
  {
    S = x; pos = first; len = l;
  }
}



void BitSubString::operator = (BitString& y)
{
  if (S == &_nil_BitString) return;
  BitStrRep* targ = S->rep;

  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 = (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 BitSubString(this, first, len);
}

BitSubString BitString::before(int pos)
{
  return BitSubString(this, 0, pos);
}

BitSubString BitString::after(int pos)
{
  return BitSubString(this, pos + 1, rep->len - (pos + 1));
}

BitSubString BitString::at(BitString& y, int startpos = 0)
{
  int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  return BitSubString(this, first,  y.rep->len);
}

BitSubString BitString::before(BitString& y, int startpos = 0)
{
  int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  return BitSubString(this, 0, last);
}

BitSubString BitString::after(BitString& y, int startpos = 0)
{
  int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  if (first >= 0) first += y.rep->len;
  return BitSubString(this, first, rep->len - first);
}


BitSubString BitString::at(BitSubString& y, int startpos = 0)
{
  int first = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  return BitSubString(this, first, y.len);
}

BitSubString BitString::before(BitSubString& y, int startpos = 0)
{
  int last = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  return BitSubString(this, 0, last);
}

BitSubString BitString::after(BitSubString& y, int startpos = 0)
{
  int first = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  if (first >= 0) first += y.len;
  return BitSubString(this, first, rep->len - first);
}

BitSubString BitString::at(BitPattern& r, int startpos = 0)
{
  int first = r.search(rep->s, startpos, rep->len);
  return BitSubString(this, first, r.pattern.rep->len);
}


BitSubString BitString::before(BitPattern& r, int startpos = 0)
{
  int first = r.search(rep->s, startpos, rep->len);
  return BitSubString(this, 0, first);
}

BitSubString BitString::after(BitPattern& r, int startpos = 0)
{
  int first = r.search(rep->s, startpos, rep->len);
  if (first >= 0) first += r.pattern.rep->len;
  return BitSubString(this, first, rep->len - first);
}

BitStrTmp common_prefix(BitString& x, BitString& y, int startpos = 0)
{
  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 (&_nilBitStrRep);

  unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  unsigned short a = *xs++;
  int xp = startx;

  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++;
  }
  return (BStr_alloc(0, x.rep->s, startx, xp, xp - startx));
}


BitStrTmp common_suffix(BitString& x, BitString& y, int startpos = -1)
{
  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 (&_nilBitStrRep);

  unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  unsigned short a = *xs--;
  int xp = startx;

  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--;
  }
  return (BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp));
}

BitStrTmp reverse(BitString& x)
{
  unsigned int  yl = x.rep->len;
  BitStrRep* y = BStr_resize(0, yl);
  if (yl > 0)
  {
    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 (unsigned int  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;
    }
  }
  return y;
}

extern Obstack _libgxx_io_ob;
extern char* _libgxx_io_oblast;

extern AllocQueue _libgxx_fmtq;

const char* BitStringtoa(BitString& x, char f = '0', char t = '1')
{
  int wrksiz = x.length() + 2;
  char* fmtbase = _libgxx_fmtq.alloc(wrksiz);
  char* fmt = fmtbase;
  unsigned int  xl = x.rep->len;
  unsigned short* s = x.rep->s;
  unsigned short a = 0;

  for (unsigned int  i = 0; i < xl; ++i)
  {
    if (i % BITSTRBITS == 0)
      a = *s++;
    *fmt++ = (a & 1)? t : f;
    a >>= 1;
  }

  *fmt = 0;

  return fmtbase;
}

BitStrTmp atoBitString(const char* s, char f = '0', char t = '1')
{
  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);
  }
  return (r);
}

ostream& operator << (ostream& s, BitString& x)
{
  return s << BitStringtoa(x);
}


const char* BitPatterntoa(BitPattern& p, char f = '0',char t = '1',char x='X')
{
  unsigned int  pl = p.pattern.rep->len;
  unsigned int  ml = p.mask.rep->len;
  unsigned int  l = pl <? ml;

  int wrksiz = l + 2;
  char* fmtbase = _libgxx_fmtq.alloc(wrksiz);
  char* fmt = fmtbase;

  unsigned short* ps = p.pattern.rep->s;
  unsigned short* ms = p.mask.rep->s;
  unsigned short a = 0;
  unsigned short m = 0;

  for (unsigned int  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;
}

BitPattern atoBitPattern(const char* s,char f = '0',char t = '1',char x = 'X')
{
  BitPattern 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 r;
}

ostream& operator << (ostream& s, BitPattern& x)
{
  return s << BitPatterntoa(x);
}

int BitString::OK()
{
  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()
{
  int v = S != 0;               // point to a bitstring
  v &= S->OK();                 // that is valid
  v &= pos >= 0 && len >= 0;    // valid indices
  v &= pos + len <= S->rep->len; // within bounds of targ
  if (!v) (*lib_error_handler)("BitSubString", "invariant failure");
  return v;
}

int BitPattern::OK()
{
  int v = pattern.OK() && mask.OK();
  if (!v) (*lib_error_handler)("BitPattern", "invariant failure");
  return v;
}