多个单词之间的高效位混洗

Question

假设我有 8 个 32 位寄存器：

A 0-31        E 0-31
B 0-31        F 0-31
C 0-31        G 0-31
D 0-31        H 0-31

我希望他们的位重新排列如下：

A' := A0 E0 A8 E8 A16 E16 A24 E24 B0 F0 B8 F8 B16 F16 B24 F24 C0 G0 ...etc. H24
B' := A1 E1 A9 E9 A17 E17 A25 E25 B1 F1 B9 F9 B17 F17 B25 F25 C1 G1 ...etc. H25 
C' := A2 E2 A10 E10 A18 E18 A26 E26 B2 ... etc.
D' := ... etc.
E' := ... etc.
F' := ... etc.
G' := ... etc.
H' := ... etc.

在 C 或 ARM 汇编中计算这种改组的最有效方法是什么？（所以没有带有 SSE 的英特尔，没有 64 位寄存器，没有足够的寄存器来包含输入和输出。） http://programming.sirrida.de/calcperm.php 的计算器非常好，但它不容易扩展到多个单词。我相信它可以比当时选择一位的天真方式更有效地完成。

Answer 1

如果你制作组件 A0 _ _ _ _ _ _ _ A8 _ _ _ _ _ _ _ A16 等（只是微不足道的掩蔽）。和其他寄存器类似，你可以很容易地做到这一点：

A0 E0 B0 F0 C0 G0 D0 H0 A8 E8 ..

您可以用两个 bit_permute_step 将其转换为正确的顺序，如 calcperm 所给出的：

x = bit_permute_step(x, 0x00cc00cc, 6);  // Bit index swap 1,3
x = bit_permute_step(x, 0x0000f0f0, 12);  // Bit index swap 2,4

其他寄存器的情况类似，只是稍微偏移了一点。

基本上是一次移动 4 位，有一点修复，只发生 8 次。

Answer 2

; 1) Copy the top most 8 bits of H into the lowest bits of the output registers:

lsr H  ; H.31 -> carry
rol H' ; carry -> H'.0

lsr H  ; H.30 -> carry
rol G' ; carry -> G'.0

lsr H
rol F'

...

lsr H  ; H.24 -> carry
rol A' ; carry to A'.0

; 2) go on with top 8 bits of D

lsr D  ; D.31 -> carry
rol H' ; H'.0 -> H'.1 and carry -> H'.0

lsr D
rol G'

...

lsr D
rol A'

继续，直到所有位都到位。最后一步是

lsr A  ; A.0 -> carry
rol A' ; A'.0 -> A'.1 -> A'.2 ... and carry -> A'.0

Answer 3

我想出的最快版本：

// merges 32 bit a (low) and b (hi) into single 64 bit
#define m(a, b) (((uint64_t) (a)) | (((uint64_t) (b)) << 32))

// gets bit at position opos and moves it to position npos
#define s(a, opos, npos) (((opos) >= (npos)) ? (((a) & ( ((uint64_t)1) << (opos))) >> ((opos) - (npos))) : (((a) & (((uint64_t)1) << (opos))) << ((npos) - (opos))))

// gets 8 different bits from 64 bit number and puts them together into 1 byte, starting from idx
#define b(a, idx) (s(a, 0, idx) | s(a, 32, (idx - 1)) | s(a, 8, (idx - 2)) | s(a, 40, (idx - 3)) | s(a, 16, (idx - 4)) | s(a, 48, (idx - 5)) | s(a, 24, (idx - 6)) | s(a, 56, (idx - 7)))

// takes 8 32 bit registers in in, outputs in out
void shuffle(const uint32_t* in, uint32_t* out) {
    uint64_t t[4] = { m(in[0], in[4]), m(in[1], in[5]), m(in[2], in[6]), m(in[3], in[7]) };
    for (int i = 0; i < 8; i++, t[0] >>= 1, t[1] >>= 1, t[2] >>= 1, t[3] >>= 1)
        out[i] = b(t[0], 31) | b(t[1], 23) | b(t[2], 15) | b(t[3], 7);
}

与直接方法相比，唯一"optimization"是将两个 32 位寄存器合并为一个 64 位寄存器，因此我们可以减少循环中的移位次数

Answer 4

在带有 SSE 的 x86 上：punpcklbw（_mm_unpacklo_epi8 可以交错源代码的字节。

使用向量移位然后 pmovmskb 获取每个字节的高位，得到类似
的结果 A0 E0 A8 E8 A16 E16 A24 E24

然后结合这些字节结果得到8个dest寄存器。这种很糟糕，因为每个结果字节都需要 shift/pmovmskb。有 8 * 4 个结果字节，所以代码量很大。

Answer 5

我来晚了一点，但无论如何我都会post回答。

首先，请注意输出字中的每个字节仅使用一对输入字的 even/odd 位。将 A 的奇数位与 B 的偶数位组合得到 A、C、E、G 的第一个字节所需的所有位。生成排列的代码可以通过上面链接的计算器找到，并简化为每个字两个位交换操作。生成的字节可以在正确的位置写回内存，并在必要时读回。

置换一个字内的字节的成本与将字节写入内存的成本差不多，但也是可能的。

成本是每个字 17 位操作。在 ARM 上少一点，旋转是自由的。矢量化很容易，字节改组取代了最后一步。

下面的普通 C 代码应该可以做到：

#include <stdio.h>
#include <stdint.h>

int32_t inline bit_permute_step(int32_t x, int32_t m, int shift) {
    int32_t t;
    t = ((x >> shift) ^ x) & m;
    x = (x ^ t) ^ (t << shift);
    return x;
    }

void permute(int32_t input[8], int32_t output[8]){
    int8_t *outputc=(int8_t*)output;
    for(int i=0;i<4;i++){
        int32_t A=input[3-i];
        int32_t E=input[3-i+4];
        //swap the even bits of A/B/C/D with the odd bits of E/F/G/H
        int32_t t=(A^(E>>1))&0x55555555;
        A^=t;E^=t<<1;
        A = bit_permute_step(A, 0x00cc00cc, 6);  // Bit index swap 1,3
        E = bit_permute_step(E, 0x00cc00cc, 6);  // Bit index swap 1,3
        A = bit_permute_step(A, 0x0000f0f0, 12);  // Bit index swap 2,4
        E = bit_permute_step(E, 0x0000f0f0, 12);  // Bit index swap 2,4
        outputc[i+0 ]=A>>24;
        outputc[i+4 ]=E>>24;
        outputc[i+8 ]=A>>16;
        outputc[i+12]=E>>16;
        outputc[i+16]=A>>8;
        outputc[i+20]=E>>8;
        outputc[i+24]=A;
        outputc[i+28]=E;
        }
    }


void printBits(unsigned int num){
   for(int bit=31;bit>=0; bit--){
      printf("%i", (num>>bit)&1);
      if(bit && !(bit&7)){printf(" ");}
   }printf("\n");
}

int32_t main(){
    volatile int32_t input[8]=
{0xf<<0,0xf<<8,0xf<<16,0xf<<24,0xf<<4,0xf<<12,0xf<<20,0xf<<28};
    int32_t output[8]={-1,-1,-1,-1,-1,-1,-1,-1};
    printf("input\n");
    permute((int32_t*)input,output);
    for(int i=0;i<8;i++){
        printf("  %c:",'A'+i);
        printBits(input[i]);
    }
    printf("output\n");
    for(int i=0;i<8;i++){
        printf("  %c:",'A'+i);
        printBits(output[i]);
    }
    
}

多个单词之间的高效位混洗

Efficient bit shuffling between multiple words

c

assembly

arm

bit-manipulation

shuffle