Author: | Wojciech Muła |
---|---|

Added on: | 2010-03-31 |

Method presented here allows to get any bit permutation, transposition is just one of possible operations. Lookup-based approach would be faster, but algorithm is worth to (re)show.

Algorithm outline for 8-byte vector (with SSE instruction it is possible to get 2 operations in parallel):

fill vector with given byte:

[11010001] => [11010001|11010001|11010001|11010001|11010001|11010001|11010001|11010001]

leave one bit per byte:

[10000000|01000000|00000000|00010000|00000000|00000000|00000000|00000001]

perform desired transposition ("move" bits around):

[00000001|00000010|00000000|00001000|00000000|00000000|00000000|10000000]

perform horizontal OR of all bytes:

[10001011]

Here is my old MMX code (polish text); below SSE/SSE5 implementation details.

Ad 1. Series of punpcklbw/punpcklwb/shufps or pshufb if CPU supports SSSE3.

# 1.1 movd %eax, %xmm0 shufps $0x00, %xmm0, %xmm0 punpcklbw %xmm0, %xmm0 punpcklwd %xmm0, %xmm0 # 1.2 pxor %xmm1, %xmm1 movd %eax, %xmm0 pshufb %xmm1, %xmm0

Ad 2. Simple pand with mask packed_qword(0x8040201008040201).

pand MASK1, %xmm0

Ad 3. If plain SSE instructions are supported this step requires some
work. First, each bit is populated to fill the whole byte (using
`pcmpeq` — we get negated result), then mask bits on desired positons.

SSE5 has powerful instruction `protb` that can do perform rotation of
each byte with independent amount — so in this case just one
instruction is needed.

# SSE pcmpeq %xmm1, %xmm0 pandn MASK2, %xmm0 # pandn - to negate # SSE5 protb ROT, %xmm0, %xmm0

Ad 4. Since bits are placed on distinct positions, we can use
instruction `psadbw`, that calculate horizontal sums of bytewide
differences from two registers (separately for low and high registers
halves). If one register is full of zeros, we get sum of bytes from
other register.

psadbw %xmm1, %xmm0 movd %xmm0, %eax

Depending on instruction set, three (SSE) or two (SSE5) additional tables are needed.