[dynamic_bitset] Endianess and Adaption Vs Copying

I've noticed that the dynamic_bitset seems to have endian issues. For masking out the ith bit in a block, it uses 1 shifted left by i. As a result, the bits are not consecutive. For example if the block_type is uint8_t, and we have 16 bits in the bitset, then bits are numbered: 00 01 02 03 04 05 06 07 15 14 13 12 11 10 09 08 in memory. That doesn't seem right---7th and 8th bits should be adjacent. Does anyone have suggestions for controlling this? Second, has anyone adapted dynamic_bitset to be an adaptor for an existing memory range to avoid copying? Thanks! Joel

On Tue, May 1, 2012 at 4:35 PM, Joel <jdy@cryregarder.com> wrote:
I've noticed that the dynamic_bitset seems to have endian issues. For masking out the ith bit in a block, it uses 1 shifted left by i. As a result, the bits are not consecutive.
For example if the block_type is uint8_t, and we have 16 bits in the bitset, then bits are numbered:
00 01 02 03 04 05 06 07 15 14 13 12 11 10 09 08
in memory.
Wrong, in increasing address order, it would rather be 07 06 05 04 03 02 01 00 15 14 13 12 11 10 09 08
That doesn't seem right---7th and 8th bits should be adjacent. Does anyone have suggestions for controlling this?
Why? How is that a problem?
Second, has anyone adapted dynamic_bitset to be an adaptor for an existing memory range to avoid copying?
I haven't, but it sounds like a good idea :) -- François

Francois Duranleau <xiao.bai.xiong <at> gmail.com> writes:
Wrong, in increasing address order, it would rather be
07 06 05 04 03 02 01 00 15 14 13 12 11 10 09 08
You are, of course, correct. Brain fart on my part.
That doesn't seem right---7th and 8th bits should be adjacent. Does anyone have suggestions for controlling this?
Why? How is that a problem?
It isn't necessarily a problem. It is an arbitrary choice. However, dynamic_bitset provides a constructor that takes raw data as input. If the source for that input has the bits ordered consecutively (which would allow one to change the block type without changing the ordering of the bits) then the constructor will not function properly. At minimum, the bit-ordering imposed by dynamic-bitset should be explicitly documented.
Second, has anyone adapted dynamic_bitset to be an adaptor for an existing memory range to avoid copying?
I haven't, but it sounds like a good idea :)
Should it be part of dynamic_bitset or should it be a new class? Joel

Joel wrote:
dynamic_bitset provides a constructor that takes raw data as input. If the source for that input has the bits ordered consecutively (which would allow one to change the block type without changing the ordering of the bits) then the constructor will not function properly.
Perhaps you could post a short example of some code that you think would fail? I was a bit surprised to find that it has this: template <typename Block> class dynamic_bitset { template <typename BlockInputIter> dynamic_bitset(BlockInputIter first, BlockInputIter last) { ... So you can do this: const char* data = ......; // From a "platform independent" binary file. dynamic_bitset<unsigned int> b(data,data+size); This probably doesn't do what you want, but not for endianness reasons; it seems to initialise each int-sized block with one byte of data, leaving the other 24 bits unset. If you write this: const char* data = ......; // From a "platform independent" binary file. dynamic_bitset<unsigned char> b(data,data+size); then I believe it will always work. If you write this: const char* data = ......; // From a "platform independent" binary file. const int* data_i = static_cast<const int*>(data); dynamic_bitset<int> b(data_i,data_i+size); then you get endianness problems. But you would have the same trouble if you tried to initialise e.g. a vector<int> in that way.
At minimum, the bit-ordering imposed by dynamic-bitset should be explicitly documented.
The BIT ordering? No, bit ordering is always the same. You never need to re-order the bits within a byte. (What am I missing?) Regards, Phil.

On Thu, May 3, 2012 at 7:22 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
At minimum, the bit-ordering imposed by dynamic-bitset should be explicitly documented.
The BIT ordering? No, bit ordering is always the same. You never need to re-order the bits within a byte.
(What am I missing?)
Bit ordering between bytes? Or byte ordering? -- Olaf

Phil Endecott <spam_from_boost_dev <at> chezphil.org> writes:
Perhaps you could post a short example of some code that you think would fail?
If a C library created an internal bit vector where the bits were packed tightly and in order from left-to-right (low memory to high memory), dynamic_bitset would be able to correctly map the vector on a big-endian machine but would mess it up on a little-endian machine. The order that the bits are packed is completely arbitrary. This library has chosen to pack the bits from least-significant to most-significant within blocks and left-to-right across blocks.
I was a bit surprised to find that it has this:
template <typename Block> class dynamic_bitset { template <typename BlockInputIter> dynamic_bitset(BlockInputIter first, BlockInputIter last) { ...
That didn't surprise me, other than I wish it had a comment giving the expected bit-ordering.
So you can do this:
const char* data = ......; // From a "platform independent" binary file. dynamic_bitset<unsigned int> b(data,data+size);
Should be const uint32_t data = .....; in that case!
Joel say:
At minimum, the bit-ordering imposed by dynamic-bitset should be explicitly documented.
The BIT ordering? No, bit ordering is always the same. You never need to re-order the bits within a byte.
(What am I missing?)
Bit ordering is completely arbitrary. If the constructor for reference in dynamic_bitset.hpp is changed from: // the one and only non-copy ctor reference(block_type & b, block_type pos) :m_block(b), m_mask( (assert(pos < bits_per_block), block_type(1) << pos ) ) { } to: // the one and only non-copy ctor reference(block_type & b, block_type pos) :m_block(b), m_mask( (assert(pos < bits_per_block), ((block_type(1) << (bits_per_block-1)) >> pos )) ) { } and the ordering would be reversed. Now on little-endian machines, the ordering nicely goes always left-to-right. Joel

Joel wrote:
Bit ordering is completely arbitrary. If the constructor for reference in dynamic_bitset.hpp is changed from:
// the one and only non-copy ctor reference(block_type & b, block_type pos) :m_block(b), m_mask( (assert(pos < bits_per_block), block_type(1) << pos ) ) { }
to:
// the one and only non-copy ctor reference(block_type & b, block_type pos) :m_block(b), m_mask( (assert(pos < bits_per_block), ((block_type(1) << (bits_per_block-1)) >> pos )) ) { }
and the ordering would be reversed. Now on little-endian machines, the ordering nicely goes always left-to-right.
If you're thinking about individual bits being "next to" bits in other bytes, and bits or bytes being "left" or "right" of each other, your mental model of endianness is over-complicated. Because bits are not individually addressable, the only thing that matters is the order of bytes (which are addressable) within words. Ordering of bits only matters when someone draws a picture of something like a peripheral register. Regards, Phil.

Phil Endecott <spam_from_boost_dev <at> chezphil.org> writes:
If you're thinking about individual bits being "next to" bits in other bytes, and bits or bytes being "left" or "right" of each other, your mental model of endianness is over-complicated. Because bits are not individually addressable, the only thing that matters is the order of bytes (which are addressable) within words. Ordering of bits only matters when someone draws a picture of something like a peripheral register.
Granted. Sometimes you have to deal with (and understand) other people's mental models though. Joel

Hi Joel, Joel wrote:
I've noticed that the dynamic_bitset seems to have endian issues.
Do you have a test case that you can share?
For masking out the ith bit in a block, it uses 1 shifted left by i. As a result, the bits are not consecutive.
What do you mean by "consecutive"? Why do you think this matters? (I have just had a quick look at the code, and I've not seen anything like casts or unions that could cause endianness issues.) Regards, Phil.

Phil Endecott <spam_from_boost_dev <at> chezphil.org> writes:
Joel wrote:
I've noticed that the dynamic_bitset seems to have endian issues.
Do you have a test case that you can share?
This isn't a classic endian issue. I just needed to know in what order the bits were arranged within each block. This didn't match the bit ordering from the source I had.
For masking out the ith bit in a block, it uses 1 shifted left by i. As a result, the bits are not consecutive.
What do you mean by "consecutive"? Why do you think this matters?
If one has a need to use the raw memory managed by the bitset for some purpose one needs to know the ordering. Also, if one needed to change the block_type for that chunk of raw memory it would matter.
(I have just had a quick look at the code, and I've not seen anything like casts or unions that could cause endianness issues.)
You are right
Regards, Phil.
Thanks Phil. I do think the ordering should be documented for the constructor that takes start and end block iterators. Joel
participants (4)
-
Francois Duranleau
-
Joel
-
Olaf van der Spek
-
Phil Endecott