[boost] Proposed bit_struct submission to Boost

From: Kevin S. Van Horn (Kevin.VanHorn_at_[hidden])
Date: 2002-11-11 11:37:34

A local business had need of a facility to pack arbitrary-sized bitfields into
exactly 64 bits, with a guarantee of no padding.  I wrote this class as a
generalization of that need, and would like your comments as to whether this
would be appropriate for submission to Boost.  You can download the source
code, rough draft of documentation, and regression test from

  http://www.cs.ndsu.nodak.edu/~kvanhorn/bitstruct.tgz (gzipped tar file)

or

  http://www.cs.ndsu.nodak.edu//~kvanhorn/bitstruct.zip (ZIP file).

I have included the rough draft of the documentation below.

-------------------------------------------------------------------

BITSTRUCT

Explanation
-----------

Neither C nor C++ provides a portable means of packing integer fields of
arbitrary numbers of bits (up to the largest integer size) into a
struct as compactly as possible, with a known layout.  One might think
that bit-fields would do the job, but the C++ Standard makes very few
guarantees about bit-fields.  Section 9.6 states, "Allocation of
bit-fields within a class object is implementation-defined. Alignment
of bit-fields is implementation-defined... Note: bit-fields straddle
allocation units on some machines and not on others."  For example, suppose
that one defines the following struct with the expectation that it
will all fit into 64 bits, or two words on a 32-bit platform:

  struct mystruct {
    unsigned a : 3;
    unsigned b : 20;
    unsigned c : 20;
    unsigned d : 10;
    unsigned e : 11;
  };

On a 32-bit, platform, the layout is quite likely (but not
guaranteed) to be

  +--+-------------------+--------+ +-------------------+---------+-+
  |a |b                  |unused  | |c                  |d        | |
  +--+-------------------+--------+ +-------------------+---------+-+

  +----------+--------------------+
  |e         |unused              | 
  +----------+--------------------+

with the padding after b and d inserted to avoid bit-fields that
straddle word boundaries.

One therefore has to do one's own bit-twiddling in order to get
bit-fields packed in the desired manner.  This is usually done by
defining various macros or inline functions, which can be error-prone and
quite tedious when bit-fields cross word boundaries.  Furthermore, if one has
several different bit-field structures, there is no type checking to
ensure that one doesn't apply a macro to the wrong type.

The bit_struct class template is intended to solve this problem.  The bit
field sizes and positions are part of the type of the bit_struct, and so it is
impossible to mismatch operations on different kinds of bit-field structures.
Template metaprogramming is used so that all operations are as efficient as
hand-crafted inline functions or macros would be.

Here is the interface:

typedef bit_struct<N_0, ..., N_k> BS;
// REQUIRE: N_i > 0, 0 <= i <= k.
// REQUIRE: (SUM i: 0 <= i <= k: N_i) is a multiple of CHAR_BIT.
// REQUIRE: 0 <= k < MAX_FIELDS, where MAX_FIELDS is currently 8.

zero_fields
// PROMISE: A value of type zero_fields_t

BS x(zero);
// REQUIRE: zero has type zero_fields_t.
// PROMISE: x is initialized with all fields set to zero.

BS x;
// PROMISE: x in valid state, but fields are arbitrary.

BS x(init_arr);
// REQUIRE: init_arr is convertible to type U const * for some integer type U.
// REQUIRE: At most the first N_i bits of init_arr[i] are nonzero.
// PROMISE: field i initialized to value init_arr[i], for 0 <= i <= k.

trunc_field
// PROMISE: A value of type trunc_field_t.

BS x(trunc, init_arr);
// REQUIRE: trunc has type trunc_field_t.
// REQUIRE: init_arr is convertible to type U const * for some integer type U.
// PROMISE: field i initialized to the low-order N_i bits of init_arr[i],
//   for 0 <= i <= k.

BS::field<i>
// REQUIRE: 0 <= i < k.
// PROMISE: This is an empty type with the following members:
//   type: the value type of bit-field i -- boost::uint_t<N_i>::fast.
//   position: a compile-time integer constant giving the logical
//     position of the bit-field in the bit_struct.  Its value is
//     (SUM j: 0 <= j < i: N_j).
//   length: a compile-time integer constant equal to N_i.

BS::num_bits
// PROMISE: A compile-time integer constant equal to (SUM i: 0 <= i <= k:N_i).

BS::num_fields
// PROMISE: A compile-time integer constant equal to k+1 (the # of fields).

BS::uint_type
// PROMISE: An unsigned integer type whose size in bits evenly divides
//   BS::num_bits.

BS::num_uints
// PROMISE: A compile-time integer constant equal to
//   BS::num_bits / (size of BS::uint_type in bits).

BS::uint_type x.arr[BS::num_uints];
// Sole data member; representation of bit_struct.

x.put(field, val);
// REQUIRE: field has type BS::field<i> for some i <= k.
// REQUIRE: val has type convertible to boost::uint_t<N_i>::fast.
// REQUIRE: at most first N_i bits of val are nonzero.
// PROMISE: field i receives value val_i; other fields are unchanged.

x.put(trunc, field, val);
// REQUIRE: trunc has type trunc_field_t.
// REQUIRE: field has type BS::field<i> for some i <= k.
// REQUIRE: val has type convertible to boost::uint_t<N_i>::fast.
// PROMISE: field i set to the low-order N_i bits of val_i; other fields are
//   unchanged.

x.get(field)
// REQUIRE: field has type BS::field<i> for some i <= k.
// RETURNS: field i, as type boost::uint_t<N_i>::fast.

A typical usage of this class would look something like the following.  A
header file would contain these lines:

  typedef boost::bit_struct<5, 13, 2, 42, 28, 6> BS;
  BS::field<0> field0;
  BS::field<1> field1;
  BS::field<2> field2;
  BS::field<3> field3;
  BS::field<4> field4;
  BS::field<5> field5;
  typedef BS::field<0>::type field0_type;
  typedef BS::field<1>::type field1_type;
  typedef BS::field<2>::type field2_type;
  typedef BS::field<3>::type field3_type;
  typedef BS::field<4>::type field4_type;
  typedef BS::field<5>::type field5_type;

The code to manipulate BS would look something like this:

  BS w;
  BS x(zero_fields);
  unsigned const A[] = { 0, 1, 2, 3, 4, 5};
  BS y(A);
  BS z(trunc_field, A);

  x.put(field0, 16);
  x.put(trunc_field, field0, some_value);
  field0_type y0 = x.get(field0);

Possible extensions -- should I add in the following?

  x.or(field, val);              // faster than put if you know field is zero
  x.or(trunc_field, field, val);

There is no nead for x.clear(field), as x.put(field, 0) will do the same thing
and be just as fast with any reasonable optimizing compiler.