reversing bit order

Hi folks -

I'm writing some code for a checksum algorithm and I need to reverse the
order of bits in an unsigned char array, in 4-bit chunks (half byte, or
nibble).

Example.. the array contains BYTE data:
0001 0110, 0000 0010, 1000 0000
0x16, 0x02, 0x80

Each nibble gets reversed:
1000 0110, 0000 0100, 0001 0000
0x86, 0x04, 0x10

Each nibble will then be added and the results become a checksum nibble.

I can do this brute force, one bit at a time, but I'm hoping someone out
there will recognize a possible elegant solution. There will always be 5
bytes (40 bits, 10 nibbles) to deal with.

Any ideas?

Thanks.

Steve
Thu Jul 21 11:15:40 CDT 2005

Dave Cullen wrote:
> Hi folks -
>
> I'm writing some code for a checksum algorithm and I need to reverse the
> order of bits in an unsigned char array, in 4-bit chunks (half byte, or
> nibble).
>
> Example.. the array contains BYTE data:
> 0001 0110, 0000 0010, 1000 0000
> 0x16, 0x02, 0x80
>
> Each nibble gets reversed:
> 1000 0110, 0000 0100, 0001 0000
> 0x86, 0x04, 0x10
>
> Each nibble will then be added and the results become a checksum nibble.
>
> I can do this brute force, one bit at a time, but I'm hoping someone out
> there will recognize a possible elegant solution. There will always be 5
> bytes (40 bits, 10 nibbles) to deal with.
>
> Any ideas?

Why not use a struct to define some bit fields of size 4 inside a union. Also
construct an array of 16 entries indexed by a nibble and has a value
corresponding to the nibble reversed?

/steveA

--
Steve Alpert
my email Fgrir_Nycreg @ vqk.pbz is encrypted with ROT13 (www.rot13.org) and spaces

Dan
Thu Jul 21 12:19:36 CDT 2005

"Dave Cullen" <no_spam@mail.com> wrote in message
news:42DFC77B.D6A9E9F1@mail.com...
> Hi folks -
>
> I'm writing some code for a checksum algorithm and I need to reverse the
> order of bits in an unsigned char array, in 4-bit chunks (half byte, or
> nibble).
>
> Example.. the array contains BYTE data:
> 0001 0110, 0000 0010, 1000 0000
> 0x16, 0x02, 0x80
>
> Each nibble gets reversed:
> 1000 0110, 0000 0100, 0001 0000
> 0x86, 0x04, 0x10
>
> Each nibble will then be added and the results become a checksum nibble.
>
> I can do this brute force, one bit at a time, but I'm hoping someone out
> there will recognize a possible elegant solution. There will always be 5
> bytes (40 bits, 10 nibbles) to deal with.
>
> Any ideas?

If you are looking for speed, simply create an array of 256 BYTE's. Use the
original BYTE as the index into the array. Each element in the array would
contain the already-reversed nibbles. Given your example, array[0x16] =
0x86, array[0x02] = 0x04, and array[0x80] = 0x10.

DanB

Joe
Thu Jul 21 13:19:14 CDT 2005

Dave Cullen wrote:
> Hi folks -
>
> I'm writing some code for a checksum algorithm and I need to reverse
> the order of bits in an unsigned char array, in 4-bit chunks (half
> byte, or nibble).
>
> Example.. the array contains BYTE data:
> 0001 0110, 0000 0010, 1000 0000
> 0x16, 0x02, 0x80
>
> Each nibble gets reversed:
> 1000 0110, 0000 0100, 0001 0000
> 0x86, 0x04, 0x10
>
> Each nibble will then be added and the results become a checksum
> nibble.
>
> I can do this brute force, one bit at a time, but I'm hoping someone
> out there will recognize a possible elegant solution. There will
> always be 5 bytes (40 bits, 10 nibbles) to deal with.
>
> Any ideas?
>
> Thanks.

Dave,

As others have mentioned, a lookup table would provide
optimal speed.

If not using a lookup table, the following function should
give the result you need:

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

unsigned char reverse_nibbles(unsigned char data)
{
data = (unsigned char) (((data & 0xAA) >> 1) | ((data & 0x55) << 1));
data = (unsigned char) (((data & 0xCC) >> 2) | ((data & 0x33) << 2));

return data;
}
----------------------------------------------------------------------------
-


Joe

Lopat
Fri Jul 29 11:37:05 CDT 2005

Check out structures and lookup tables

"Dave Cullen" wrote:

> Hi folks -
>
> I'm writing some code for a checksum algorithm and I need to reverse the
> order of bits in an unsigned char array, in 4-bit chunks (half byte, or
> nibble).
>
> Example.. the array contains BYTE data:
> 0001 0110, 0000 0010, 1000 0000
> 0x16, 0x02, 0x80
>
> Each nibble gets reversed:
> 1000 0110, 0000 0100, 0001 0000
> 0x86, 0x04, 0x10
>
> Each nibble will then be added and the results become a checksum nibble.
>
> I can do this brute force, one bit at a time, but I'm hoping someone out
> there will recognize a possible elegant solution. There will always be 5
> bytes (40 bits, 10 nibbles) to deal with.
>
> Any ideas?
>
> Thanks.
>