Bitwise transpose of 8 bytes

Question

I am looking for an efficient algorithm in C to bitwise-transpose 8 bytes of data. What I mean with this is that if I have 8 bytes like this:

I want to get the following 8 bytes:

And since I want to use this on an embedded platform, it should be as fast as possible :-)

All ideas are much appreciated!

What does this mean? I don't see the relationship between the input and the desired output. Do you want to use a simple (256 byte) lookup table? — Richard Pennington, Feb 11 '10 at 11:19
@Richard: It's a matrix transpose; row become columns and vice versa. If you read the leftmost column of the result, it's equal to the first row of the input. Since there are 64 independent bits of input, a look-up table becomes ... large. — unwind, Feb 11 '10 at 11:22
@Richard: as unwind says, a lookup table would need to be too big (64 * 8 bytes). Although it would result in a very fast solution! — Arnaud Gouder de Beauregard, Feb 11 '10 at 11:47
I'm curious to know the goal you're aiming to achieve. Bitmap font rotation? — Craig McQueen, Feb 24 '10 at 04:54
On Intel x86 SSE2 processors, the [PMOVMSKB, PINSRW](http://tommesani.com/index.php/simd/36-sse-primer.html) and [PSLLW](http://tommesani.com/index.php/simd/44-mmx-shift.html) instructions can be used together to perform a 8x16 bit transpose in about 24 instructions. — rwong, Dec 06 '13 at 21:30

score 25 · Accepted Answer · edited Feb 11 '10 at 11:18

25

See Hacker's Delight, Chapter 7-3.

edited Feb 11 '10 at 11:18

Josh Lee

answered Feb 11 '10 at 11:16

Johan Kotlinski

@Arnaud, that is really cool... but what is an application that would require this function? – vicatcu Feb 19 '10 at 23:30
1

@vicatcu This is useful if you need to output 8 serial data streams on one byte wide I/O port, for example. – jms Oct 31 '17 at 12:11

1 Answers1