Unix Programming - Bit shifting

Author

Bit shifting

Captain Dondo

2007-02-05, 7:05 pm

OK, this is slightly OT, but I haven't been able to find a better group.

I am working with a piece of equipment that generates a 12-bit unsigned
int. The manufacturer provided a driver, but unfortunately the data comes
in garbled. The piece of equipment is connected by a 2-wire bus, and the
data comes in backwards. The driver then memory maps that to a location
where I should be able to read my int.

One would hope that the data comes in like this:

Highbyte + Low_byte
- - - - h3 h2 h1 h0 + l7 l6 l5 l4 l3 l2 l1 l0

Unfortunately it comes in like this:

l0 l1 l2 l3 l4 l5 l6 l7 + - - - - h0 h1 h2 h3

Now I could just brute-force move those bits around to the right order,
wiht a series of '&' and '>>' or whatever.

But I started looking at this as a puzzle; is there some neat way of
reversing the order of the bits in a byte in a small number of operations?

(I can't think of any...)

--Yan

Pascal Bourguignon

2007-02-05, 10:04 pm

Captain Dondo <yan@NsOeSiPnAeMr.com> writes:

> OK, this is slightly OT, but I haven't been able to find a better group.
>
> I am working with a piece of equipment that generates a 12-bit unsigned
> int. The manufacturer provided a driver, but unfortunately the data comes
> in garbled. The piece of equipment is connected by a 2-wire bus, and the
> data comes in backwards. The driver then memory maps that to a location
> where I should be able to read my int.
>
> One would hope that the data comes in like this:
>
> Highbyte + Low_byte
> - - - - h3 h2 h1 h0 + l7 l6 l5 l4 l3 l2 l1 l0
>
> Unfortunately it comes in like this:
>
> l0 l1 l2 l3 l4 l5 l6 l7 + - - - - h0 h1 h2 h3
>
> Now I could just brute-force move those bits around to the right order,
> wiht a series of '&' and '>>' or whatever.
>
> But I started looking at this as a puzzle; is there some neat way of
> reversing the order of the bits in a byte in a small number of operations?
>
> (I can't think of any...)

You can pre-compute a table of 256 octets, and index in it:

typedef unsigned char octet;
static octet swapped_bits[256];
octet swap_bits_in_octet(octet o){ return(swapped_bits[o]); }

Then you can get your int with:

swap_bits_in_octet(raw[0])|(swap_bits_in
_octet(raw[1]&0xF)<<4)

But since you've got probably a slow device, there's no point in
spending 256 precious bytes of L1 cache on that. Better loop 12 times.

--
__Pascal Bourguignon__ http://www.informatimago.com/

Pour moi, la grande question n'a jamais été: «Qui suis-je? Où vais-je?»
comme l'a formulé si adroitement notre ami Pascal, mais plutôt:
«Comment vais-je m'en tirer?» -- Jean Yanne

Christopher Layne

2007-02-05, 10:04 pm

Captain Dondo wrote:

> But I started looking at this as a puzzle; is there some neat way of
> reversing the order of the bits in a byte in a small number of operations?
>
> (I can't think of any...)
>
> --Yan

http://graphics.stanford.edu/~seand...tReverseObvious

Jens Thoms Toerring

2007-02-05, 10:04 pm

Captain Dondo <yan@nsoesipnaemr.com> wrote:
> OK, this is slightly OT, but I haven't been able to find a better group.

Another group that would fit might be comp.programming.

> I am working with a piece of equipment that generates a 12-bit unsigned
> int. The manufacturer provided a driver, but unfortunately the data comes
> in garbled. The piece of equipment is connected by a 2-wire bus, and the
> data comes in backwards. The driver then memory maps that to a location
> where I should be able to read my int.

> One would hope that the data comes in like this:

> Highbyte + Low_byte
> - - - - h3 h2 h1 h0 + l7 l6 l5 l4 l3 l2 l1 l0

You would hope for this if you are on a big-endian machine, one a low-
endian you probably would prefer

Low_byte + Highbyte
l7 l6 l5 l4 l3 l2 l1 l0 + - - - - h3 h2 h1 h0 +

(where x7 is the most significant bit and x0 the least significant and
with all the '-' being 0).

> Unfortunately it comes in like this:

> l0 l1 l2 l3 l4 l5 l6 l7 + - - - - h0 h1 h2 h3

Are you absolutely sure that the data come in that way (again assuming
that x7 is the MSB of that byte, but perhaps you are using a different
way to label them) and not in one that's most suitable for a low-endian
machine?

> Now I could just brute-force move those bits around to the right order,
> wiht a series of '&' and '>>' or whatever.

> But I started looking at this as a puzzle; is there some neat way of
> reversing the order of the bits in a byte in a small number of operations?

You may find this page interesting:

http://graphics.stanford.edu/~seander/bithacks.html

Look for "Reversing bit sequences". Perhaps you find some neat ideas of
how to do it in some unexpected ways;-)

Regards, Jens
--
\ Jens Thoms Toerring ___ jt@toerring.de
\__________________________ http://toerring.de

CptDondo

2007-02-06, 7:06 pm

Jens Thoms Toerring wrote:

> Are you absolutely sure that the data come in that way (again assuming
> that x7 is the MSB of that byte, but perhaps you are using a different
> way to label them) and not in one that's most suitable for a low-endian
> machine?

Yup. The data is part of a 128 byte pulsetrain; the engineers just
mapped the bitstream to the bit positions that made sense to them.
Unfortunately it's backwards from what most of us need... :-)

>
> You may find this page interesting:
>
> http://graphics.stanford.edu/~seander/bithacks.html
>
> Look for "Reversing bit sequences". Perhaps you find some neat ideas of
> how to do it in some unexpected ways;-)
>

OOF! Some of those make my brain hurt. :-)

Thanks.

--Yan

Vallabha

2007-02-09, 8:07 am

On Feb 6, 5:59 am, Captain Dondo <y...@NsOeSiPnAeMr.com> wrote:
> OK, this is slightly OT, but I haven't been able to find a better group.
>
> I am working with a piece of equipment that generates a 12-bit unsigned
> int. The manufacturer provided a driver, but unfortunately the data comes
> in garbled. The piece of equipment is connected by a 2-wire bus, and the
> data comes in backwards. The driver then memory maps that to a location
> where I should be able to read my int.
>
> One would hope that the data comes in like this:
>
> Highbyte + Low_byte
> - - - - h3 h2 h1 h0 + l7 l6 l5 l4 l3 l2 l1 l0
>
> Unfortunately it comes in like this:
>
> l0 l1 l2 l3 l4 l5 l6 l7 + - - - - h0 h1 h2 h3
>
> Now I could just brute-force move those bits around to the right order,
> wiht a series of '&' and '>>' or whatever.
>
> But I started looking at this as a puzzle; is there some neat way of
> reversing the order of the bits in a byte in a small number of operations?
>
> (I can't think of any...)
>
> --Yan

See if ntohl() call solves your problem.

Cheers
-Vallabha
S7 Software Solutions
http://www.s7solutions.com/

PS: These are my opinions... my company has no control over my
opinions.. so :)

Christopher Layne

2007-02-09, 7:06 pm

Vallabha wrote:

>
> See if ntohl() call solves your problem.

His issue was one of LSB vs MSB, where B = bits not bytes. ntohl() does not
affect bits, it only swaps the outer bytes and inner bytes with each other,
respectively.

Sponsored Links