利用Intrinsics提取和移位奇偶位

Question

是否有一种方法可以使用本质优化下面的代码？它接受16位整数中的所有奇数索引位，并尽可能地将它们向右移动。

我在想，也许使用来自Fortran的c++等效的ISHFTC (甚至有一个c++等价于此吗？)但我觉得有一个更有效的方法。

int x = some16bitInt;
x = x&0x5555;
int y = 0;
for (int i = 0; i < 8; i++)
    y = y | ((x >> i) & (0x01 << i));
'''

Answer 1

• x86:如果可用，可以使用BMI2 pext，但Zen2或更早的Zen2除外。
• 否则：@jorgbrown建议比我的bithack做一个很好的改进。
• 或者，如果您在没有快速pext的循环中做了很多这样的工作，那么在按一定的顺序将所有想要的位打包到低8中之后，Jorg的表查找思想是值得考虑的，因此表只有256个1字节条目。

ISHFTC只是一个旋转。C不直接具有这种功能，但是您可以通过移植+安全地编写一个具有模式识别的编译器并将其编译为单个旋转指令的函数。C++中循环移位(旋转)操作的最佳实践

我不确定这是一个有用的构建块，但它是可用的。

On x86具有BMI2指令集扩展，有一个pext位提取指令，可以与0x5555控件输入一起使用。见英特尔的_pext_u32和_u64文档

它在Intel Haswell和以后非常快(1 uop，3周期延迟，1/时钟吞吐量)，

但在Zen 3之前，AMD的速度相当慢(Zen1/2: 7 uops，18个周期延迟/吞吐量)。https://agner.org/optimize/和https://uops.info/.我认为这比我使用纯C实现的shift/掩码更糟糕，尤其是如果延迟很重要，或者在循环中这样做(不仅仅是前端吞吐量)。

#include <immintrin.h>

// Good on Intel, and AMD Zen3 and later.
unsigned extract_even_bits_bmi2(unsigned a) {
   return _pext_u32(a, 0x5555);
}

使用GCC / clang，您必须使用-mbmi2 (或者更好的是-march=haswell)进行编译，以便能够使用BMI2本质。

便携式ISO C++

我不认为通常的乘法技巧(将多个输入字节移动并添加到结果的顶部字节)在这里工作；您有太多的位，它们太近了。有关用例，请参见如何计算32位整数中的设置位数？：

((n & 0x0F0F0F0F) * 0x01010101) >> 24以水平方式添加n中的所有字节。

您可以想象在您的输入中使用类似的东西与* 0x08040201对齐来自不同字节的位。但这仍然留下了重大的未解决问题。也许SIMD与8位元素相乘，使对位移动在一起？

但这并不比通过掩蔽、移位和ORing或ADDing移动比特来移动移动比特更好。和关于log2(n_bits)的步骤，我们可以得到所有的位连续.

有多种方法可以做到这一点，请参阅论哥德波特。在这方面还有改进的余地，比如对一个ISA和另一个ISA进行更好的编译。例如，帮助一些ARM编译器看到0b0000011000000110只是另一个常量右移，所以它可以and r0, r1, r2, lsr #4或其他什么。

或者把位移到右边而不是左边，对于那些不能为左做任何特别的事情的ISAs。

unsigned pack_even_bits16_v2(unsigned x)
{
      // ARM / ARM64: repeat these bit-patterns to fill 32 bits,
      // so they fit in an immediate for AND.
      // but that's worse for other RISCs like PowerPC
    x &= 0x5555;        // 0a0b0c0d0e0f0g0h
    x += x<<1;          // aabbccddeeffgghh    // x86 LEA eax, [rdi + rdi*2]
    unsigned move = x &  0b0000011000000110;   // bits to move
    unsigned keep = x &  0b0110000001100000;   // bits to keep
    x = keep + (move << 2);  // 0abcd000 0efgh000

                       // 0abcd000 0efgh000    // with byte boundary shown
    unsigned tmp = x >> 7;  // high group into place, shifting out the low bits
    x &= 0xFF;    // grab the whole low byte ; possibly with a zero-latency movzx
    x = (x>>3) | tmp;
    return x;
}

我向左移动低位，而不是右移高位，因为x86可以用一条指令左移并加一条指令LEA。在其他国际审计准则上，它可能会节省一次最后的转移，将比特移向右边。

这对于AArch64和PowerPC64以及x86来说都是很好的编译。Clang看穿了PowerPC的这个位操作，并使用了强大的rlwinm (旋转左字立即和掩码)和rlwimi (.(掩码插入)说明:)至少它做到了。不幸的是，当前的clang主干现在正在执行两个mulli乘指令开始，在rlwinm +3xrlwimi之前；下面的mulli是从这个答案是新的时候开始的。

# clang trunk -O3 for PowerPC64.
# Compiling the  x += x & 0x1111;  version, not the  x += x<<1 version where we get a multiply
        andi. 4, 3, 21845        # x & 0x5555
        andi. 3, 3, 4369         # x & 0x1111
        add 4, 4, 3              # 
        rlwinm 3, 4, 31, 30, 31  # isolate the low 2 bits.  PPC counts bits from MSB=0 LSB=31 for 32-bit registers
        rlwimi 3, 4, 29, 28, 29  # insert the next 2-bit bitfield
        rlwimi 3, 4, 27, 26, 27  # ...
        rlwimi 3, 4, 25, 24, 25
        blr

最好是组合成对，而不是形成一个大链。

Jorg的改进版本:通过自己添加移动位

掩蔽保持一些位，然后添加到原来，将清除原来的位置，并产生一个携带一个位置剩下。假设下一个更高的空间已经被归零，这会移动这些位，同时留下其他位。

这还使用内联asm来解决GCC/clang错过的优化问题，在这里，他们不只是在x86上使用movzx来对字节进行零扩展。似乎已经重新安排了一些周围的逻辑，最终花费了更多的指令。

unsigned pack_even_bits16_jorg(unsigned x) {
  //      x = ?a?b?c?d ?e?f?g?h
  x  &=     0b01010101'01010101;
  //      x = 0a0b0c0d 0e0f0g0h
  x += (x & 0b00010001'00010001);  // move bits left by adding to themselves
  //      x = 0ab00cd0 0ef00gh0
  x += x << 2;
  //      x = 0abcdcde fefghgh0
  x >>= 3;
  //      x = 0000abcd cdefefgh
  x  &=     0b00001111'00001111;
  //      x = 0000abcd 0000efgh
  unsigned out;

  #if 0 || !defined(__GNUC__) || !( defined(__x86__)||defined(__x86_64__) )
    out = (unsigned char)x;   // MSVC correctly uses MOVZX here.
  #else  // Work around gcc/clang missed optimization.  TODO: __builtin_constant_p(x) to use pure C for constprop.
    asm("movzb {%b1, %0 | %0, %b1}" : "=r"(out) : "r"(x));  // AT&T | Intel dialect alternatives so it compiles ok with -masm=intel
    // alternatively  shl $4, %ah  ; or %ah, %al   avoids a movzx if you only need the low byte.  But that writes AH, renaming it separately on Intel.
  #endif

  out += x >> 4;
  return out;
}

使用测试代码查看论哥德波特。它在ARM64、PowerPC和x86 / x86-64中编译得都很好。如果调整和常量模式，使之重复到32位，这样GCC就可以直接使用它们，这对ARM64来说可能更好。

移动位的另一种方法是用异或对所选位进行零化，然后移位并将其存放在其他地方，然后使用shift和add。

   unsigned tmp = x & mask;
    x += tmp;          // left shift those bits
    x += tmp<<1;       // left shift them again.  (x86 can do this with LEA eax, [rax + rdx*2])

或

    unsigned tmp = x &   0b0000011000000110;   // bits to move
    x ^= tmp;          // clear those bits
    x += tmp << 2;     // LEA eax, [eax + edx*4]  1 fast instruction on x86

当只移动两个位置时，add + shift-and-add与xor + shift-and-add的依赖链长度基本相同。

但是有条件地清除旧比特而不是相反的掩码可能更糟。至少，如果相反的掩码适合在一个直接，或如果ISA有一个an指令。或者是手臂，一个变形的面具。在旧的x上有两种方式可以并行运行，如果按编写方式编译，则可以使用tmp = x & mask; x ^= tmp序列化数据依赖项来序列化执行。(没有；gcc和clang足够聪明地知道异或的作用，并无条件地清除这些比特。)

Answer 2

x86中最灵活的位操作(实际上，几乎任何CPU)都是从内存中读取索引的.它可以在常数时间内执行完全任意的映射，通常是在1-4个周期内(假设内存是缓存的)。

由于您只谈论8位，而且您可以轻松地将您想要的位放入寄存器的较低的8位，尽管顺序不对，所以您可以只使用一个查找表。

unsigned pack_even_bits16_table(unsigned x) {  // x = ?a?b?c?d ?e?f?g?h
  size_t m1 = x & 0x55;         //  m1 = 0e0f0g0h
  size_t m2 = (x >> 7) & 0xAA;  //  m2 = a0b0c0d0
  return map[m1 + m2];          // sum = aebfcgdh
}

地图在哪里

const unsigned char map[256] = {
    0,   1,   16,  17,  2,   3,   18,  19,  32,  33,  48,  49,  34,  35,  50,  51,
    4,   5,   20,  21,  6,   7,   22,  23,  36,  37,  52,  53,  38,  39,  54,  55,
    64,  65,  80,  81,  66,  67,  82,  83,  96,  97,  112, 113, 98,  99,  114, 115,
    68,  69,  84,  85,  70,  71,  86,  87,  100, 101, 116, 117, 102, 103, 118, 119,
    8,   9,   24,  25,  10,  11,  26,  27,  40,  41,  56,  57,  42,  43,  58,  59,
    12,  13,  28,  29,  14,  15,  30,  31,  44,  45,  60,  61,  46,  47,  62,  63,
    72,  73,  88,  89,  74,  75,  90,  91,  104, 105, 120, 121, 106, 107, 122, 123,
    76,  77,  92,  93,  78,  79,  94,  95,  108, 109, 124, 125, 110, 111, 126, 127,
    128, 129, 144, 145, 130, 131, 146, 147, 160, 161, 176, 177, 162, 163, 178, 179,
    132, 133, 148, 149, 134, 135, 150, 151, 164, 165, 180, 181, 166, 167, 182, 183,
    192, 193, 208, 209, 194, 195, 210, 211, 224, 225, 240, 241, 226, 227, 242, 243,
    196, 197, 212, 213, 198, 199, 214, 215, 228, 229, 244, 245, 230, 231, 246, 247,
    136, 137, 152, 153, 138, 139, 154, 155, 168, 169, 184, 185, 170, 171, 186, 187,
    140, 141, 156, 157, 142, 143, 158, 159, 172, 173, 188, 189, 174, 175, 190, 191,
    200, 201, 216, 217, 202, 203, 218, 219, 232, 233, 248, 249, 234, 235, 250, 251,
    204, 205, 220, 221, 206, 207, 222, 223, 236, 237, 252, 253, 238, 239, 254, 255,
};

Answer 3

当然，以下是如何：

int y = (int)_pext_u32( (unsigned int)some16bitInt, 0x5555 );

不幸的是，这个指令是从BMI2集，需要相对较新的CPU，英特尔哈斯韦尔或更新，挖掘机或更新。但是在支持它的地方，它是非常快的。