How to eliminate the bitmap difference in little endian and big endian?

[Eric J.Hu]

Hi,

Such as I have following bitmap structure and assigned value:
struct bm
{
char high2bits:2;
char mid4bits:4;
char low2bits:2;
};
bm.high2bits = 3;
bm.mid4bits = 0;
bm.low2bits = 0;

The char value is 0x03 in little endian mode, and the char value is 0xc0 in
big endian mode. How to eliminate the bitmap difference?


Thanks,
Eric

 

[Marc Mutz]

Eric J.Hu wrote:

The char value is 0x03 in little endian mode, and the
char value is 0xc0 in big endian mode. How to eliminate
the bitmap difference?

<snip>

Do the bitshuffling yourself:

class bm {
unsigned char ch;
public:
void setHigh2Bits( unsigned char bits ) {
ch &= 0x3F;
ch |= (bits & 0x3) << 6;
}
unsigned char high2Bits() const {
return (ch >> 6) & 0x3;
}
// ...
unsigned char asUChar() const { return ch; }
};

Marc

 

[Greg]

Eric J.Hu wrote:

<snip>

Do the bitshuffling yourself:

class bm {
unsigned char ch;
public:
void setHigh2Bits( unsigned char bits ) {
ch &= 0x3F;
ch |= (bits & 0x3) << 6;
}
unsigned char high2Bits() const {
return (ch >> 6) & 0x3;
}
// ...
unsigned char asUChar() const { return ch; }
};

Marc

Presumably this routine has to reverse the bits for any value 0-255.
The code above does not do so.

The question is how to reverse the bits within a single byte
efficiently. One solution would be to calculate the value by reversing
the bits at runtime:

unsigned char ReverseByteSlowly(unsigned char inByte)
{
return ((inByte & 0x80) ? 0x01 : 0) +
((inByte & 0x40) ? 0x02 : 0) +
((inByte & 0x20) ? 0x04 : 0) +
((inByte & 0x10) ? 0x08 : 0) +
((inByte & 0x08) ? 0x10 : 0) +
((inByte & 0x04) ? 0x20 : 0) +
((inByte & 0x02) ? 0x40 : 0) +
((inByte & 0x01) ? 0x80 : 0);
}

This approach works but it is expensive. It requires eight if-then-else
clauses just to reverse the bits in a single byte.

A much faster method is illustrated by this routine:

unsigned char ReverseByteQuickly( unsigned char inByte)
{
static const char kReverseByteTable[256] = {
0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff };

return kReverseByteTable[ inByte ];
}

Although ReverseByteQuickly uses 256 more bytes of memory than
ReverseByteSlowly, the payoff is a huge improvement in speed. It's a
classic memory-for-speed tradeoff, but in this case the 256 byte
overhead is a very good investment indeed.

Greg

 

[Frank Chang]

Greg, I think your approach to solving Eric's question is excellent.
But I wonder suppose I want to convert a 32 bit or 64 bit struct from
little endian to big endian. Then , one would to have create a
humungous(sp?) lookup table. Is there an algorithm out there to handle
the 32 bit or 64 bit ..... cases. Thank you.

 

[mlimber]

Hi,

Such as I have following bitmap structure and assigned value:
struct bm
{
char high2bits:2;
char mid4bits:4;
char low2bits:2;
};
bm.high2bits = 3;
bm.mid4bits = 0;
bm.low2bits = 0;

The char value is 0x03 in little endian mode, and the char value is 0xc0 in
big endian mode. How to eliminate the bitmap difference?

See the other posts for possible solutions, but let me note that
bit-fields should be avoided if possible for two reasons:

1. They are non-portable, as you have learned the hard way. C++ARM says
that the layout of bit-fields "is highly implementation dependent, and
it is wise not to make any assumptions about it unless absolutely
necessary." On a previous project, we used bit-fields for mapping the
contents of hardware registers, but when we eventually ported the
project to another platform with the other endianness, we had to
manually reverse the order of our many bit-fields. If I had time and
was still working on that project, I might try to use template
metaprogramming (a la Boost and Modern C++ Design) to engineer a more
portable solution akin to the Boost Parameter library
(http://boost.org/libs/parameter/doc/html/index.html). (N.B., I haven't
looked to see if anything like that already exists, and you might want
to.)

2. Some programmers mistakenly see bit-fields as a good form of space
or speed optimization. Consult C++ARM section 9.6 and C++PL section
C.8.1 for reasons why these forms of premature optimization often have
the opposite effect. In your case, it sounds like you're trying to
communicate between two systems of differing endianness, and so
communication *may* be a bottleneck that can be eased by bit-packing.
Just remember not to prematurely optimize
(http://www.gotw.ca/publications/mill09.htm).

Cheers! --M

 

[Jim Langston]

Eric J.Hu wrote:

<snip>

Do the bitshuffling yourself:

class bm {
unsigned char ch;
public:
void setHigh2Bits( unsigned char bits ) {
ch &= 0x3F;
ch |= (bits & 0x3) << 6;
}
unsigned char high2Bits() const {
return (ch >> 6) & 0x3;
}
// ...
unsigned char asUChar() const { return ch; }
};

Marc

Presumably this routine has to reverse the bits for any value 0-255.
The code above does not do so.

The question is how to reverse the bits within a single byte
efficiently. One solution would be to calculate the value by reversing
the bits at runtime:

unsigned char ReverseByteSlowly(unsigned char inByte)
{
return ((inByte & 0x80) ? 0x01 : 0) +
((inByte & 0x40) ? 0x02 : 0) +
((inByte & 0x20) ? 0x04 : 0) +
((inByte & 0x10) ? 0x08 : 0) +
((inByte & 0x08) ? 0x10 : 0) +
((inByte & 0x04) ? 0x20 : 0) +
((inByte & 0x02) ? 0x40 : 0) +
((inByte & 0x01) ? 0x80 : 0);
}

This approach works but it is expensive. It requires eight if-then-else
clauses just to reverse the bits in a single byte.

A much faster method is illustrated by this routine:

unsigned char ReverseByteQuickly( unsigned char inByte)
{
static const char kReverseByteTable[256] = {
0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff };

return kReverseByteTable[ inByte ];
}

Although ReverseByteQuickly uses 256 more bytes of memory than
ReverseByteSlowly, the payoff is a huge improvement in speed. It's a
classic memory-for-speed tradeoff, but in this case the 256 byte
overhead is a very good investment indeed.

Greg

Umm.. whats wrong with:
return 255 - inByte;

 

[msalters]

Jim Langston schreef:

Umm.. whats wrong with:
return 255 - inByte;

Well, 255-0xc0 isn't 0x03, so that's one bug.

HTH,
Michiel Salters

 

[Jim Langston]

Jim Langston schreef:



Well, 255-0xc0 isn't 0x03, so that's one bug.

Ahh, yes, my bad. I didn't understand the OP problem fully.