RE: [boost] Dynamic sized bitset

From: Cliff Green (cliffg_at_[hidden])
Date: 2001-12-11 03:38:33

It seems like there's some kind of Boost karma at work - every time I have
something I think is worthy of consideration someone contributes something
similar (and usually better). :)

I've developed and used (extensively) a class for a variable sized buffer of
bits that has additional (useful, IMO) functionality above and beyond
vector<bool>, bitset, and the proposed dyn_bitset. What I've needed (and
what my class provides) is:

1. A dynamically sized container of bits, with the size not known in advance
(i.e. bits are pushed on the container depending on dynamic run-time logic).
2. A simple mechanism to convert this container to a buffer of unsigned
chars, and the converse (the buffer, char type, etc is a template policy in
my class).
3. Simple "get" and "append" methods to get or append bits to / from
unsigned integral types (typically fundamental types, but could also be
classes that meet the concepts / requirements).
4. The usual bit access / manipulation that vector<bool> provides, and a few
that bitset provides but vector<bool> does not (e.g. "flip" a specified
bit).

I've used this in code interacting with very bit-oriented or
space-constrained protocols, such as wireless protocols or low-bandwidth
device interfaces. Frequently the bits contained in the container are
dependent on previous bits - e.g. a bit specifying whether a field is
present or not, or dynamic sized buffers embedded within the full message.
Even a buffer length field may be variable in size - e.g. if size < 128,
length field is 8 bits, else 8th bit set ("overflow bit") and length field
is 16 bits total, and so on.

Requirement 2 is simply there to provide a way to send / receive or read /
write this bit buffer to a network or disk.

The main limitations (for my needs) of the existing std lib classes (and the
proposed dyn_bitset) are:

1. vector<bool> does not meet my needs for requirements 2 and 3, and part of
4.
2. bitset does not meet my needs for requirements 1 through 3.
3. dyn_bitset does not meet my needs for requirements 1 through 3, although
1 would not be an issue if the final / complete size was pre-computed
(dynamically) before actually creating the bit container and setting the
bits.

Note that my requirement 2 is addressed in Herb Sutter's GOTW #72, although
I had written my original version before he published #72 (I ended up
re-writing my implementation based on Herb's solution, after he published it
on the web).

I'll be happy to post my complete code, but let me boil out the fundamental
interface, since that is what I'm most concerned with. And obviously, the
bigger question is whether my additional functionality (requirements 2 and
3) are general or useful enough to be worthy of Boost submission, or (what I
think would be a better solution) adding to dyn_bitset.

There are two template policies:

1. Storage policy - this defaults to vector<bool>, but is the underlying
container storing the bits. The basic requirements on the storage policy
class are default construction, size() method, push_back, and operator[]
(both const and non-const versions).
2. Binary Buffer policy - this defaults to std::basic_string<unsigned char>,
but could be any container capable of storing unsigned chars and supporting
default construction, size(), push_back, operator&, operator[] (both
versions), and a contiguous data buffer. Standards-wise, basic_string does
not guarantee the contiguous data buffer, so it's probably better to
disallow that class. There are numerous other available classes that would
work, including vector<unsigned char>, or Andrei's Typed Buffer class, or
the requirements / logic of the binary buffer interface could be changed to
allow basic_string.

There are various construction and get / append interfaces to stream in /
out the binary buffer. For example, assume the template class is named
BitBuffer, and the binary buffer is of type BinBuf:

   BitBuffer (BinBuf const& buf, size_t numBits) : mBits() {
appendBinaryBuf(buf, numBits); }
   void appendBinaryBuf( BinBuf const& buf, size_t numBits);
   BinBuf const getBinaryBuf() const { return getBinaryBuf(0, size()); }
   BinBuf const getBinaryBuf(size_t startBit, size_t numBits) const;

For dyn_bitset, it probably doesn't make sense to have either template
policy (as in my class design), but instead maybe provide binary buffer
streaming in / out solely through template member functions. The storage
policy could also be implicit in the dyn_bitset, or through the allocator as
it appears to be in the proposed interface.

The get / append for unsigned integral types are template member functions,
such as:

   template <typename T>
     void appendVal (T val, size_t numBits);
   template <typename T>
    T getVal (size_t startBit, size_t numBits) const;

The requirements for the unsigned integral type include the usual suspects -
bit shift, mod, divide by 2, etc. I'll be happy to share my implementation,
but I'm sure there are more efficient / elegant / less restrictive solutions
available.

Everything in the bit container is considered to be Most Significant Bit
first, so the "appendVal" and "getVal" template member functions have
corresponding logic.

Comments? I'd love to be able to use dyn_bitset and get rid of my existing
utility class / functions ... I was considering a re-write of my class,
including adding lots of Boost concepts checking and re-thinking the way I
have my template policy classes defined, but would rather put this effort
into something that might get wider usage, and / or synchronize with
existing efforts.

Cliff