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:

00011100
00111000
00000001
00000000
11000000
00000000
11111111
01010101

I want to get the following 8 bytes:

00001010
00001011
01000010
11000011
11000010
10000011
00000010
00100011

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

All ideas are much appreciated!

Nylanylghau

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? – Godfearing

@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. – Twi

Columns are getting rows and vice versa. – Stantonstanway

@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! – Nylanylghau

I'm curious to know the goal you're aiming to achieve. Bitmap font rotation? – Rothenberg

On Intel x86 SSE2 processors, the PMOVMSKB, PINSRW and PSLLW instructions can be used together to perform a 8x16 bit transpose in about 24 instructions. – Newsworthy

Answer 1

See Hacker's Delight, Chapter 7-3.

Salsala

@Arnaud, that is really cool... but what is an application that would require this function? – Megavolt

@Megavolt This is useful if you need to output 8 serial data streams on one byte wide I/O port, for example. – Llywellyn

icodeguru.com/Embedded/Hacker's-Delight/048.htm – Stab