bitstring.cc

早期freebsd实现

    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 ((unsigned)(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 ((unsigned)(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 ((unsigned)(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 ((unsigned)(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 ((unsigned)(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 ((unsigned)(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 ((unsigned)(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 || (unsigned)(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 ((unsigned)(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 ((unsigned)(++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 ((unsigned)(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)
        {