使用内在函数提取和移位 Odd/Even 位
Using Intrinsics to Extract And Shift Odd/Even Bits
有没有办法使用内部函数优化以下代码？它采用 16 位整数中的所有奇数索引位并将它们尽可能右移。
我在想也许可以使用 Fortran 中 ISHFTC 的 C++ 等价物（甚至有 C++ 等价物吗？）。但是我觉得还有更高效的方法。
int x = some16bitInt;
x = x&0x5555;
int y = 0;
for (int i = 0; i < 8; i++)
y = y | ((x >> i) & (0x01 << i));
'''
当然可以，方法如下：
int y = (int)_pext_u32( (unsigned int)some16bitInt, 0x5555 );
很遗憾，此指令来自 BMI2 集，需要相对较新的 CPU、Intel Haswell 或更新版本、AMD Excavator 或更新版本。但是在支持的地方，速度非常快。
x86：如果可用，使用 BMI2 pext，Zen2 或更早的 AMD 除外。
否则：@jorgbrown 建议对我的 bithack 进行一个很好的改进。
或者如果你在没有快速 pext 的情况下在循环中做很多这样的事情，那么在打包你想要的所有位之后，值得考虑 Jorg 的 table 查找想法some 顺序中的低 8，因此 table 只有 256 x 1 字节条目。
Fortran ISHFTC is just a rotate. C doesn't directly have this, but you can portably + safely write a function that compilers with pattern-recognize and compile to a single rotate instruction. Best practices for circular shift (rotate) operations in C++
我不确定这是一个有用的构建基块，但它是可用的。
在具有 BMI2 instruction-set 扩展 的 x86 上，有一条 pext bit-extract 指令，您可以将其与 0x5555控制输入。
请参阅 _pext_u32 和 _u64
的英特尔文档
在 Intel Haswell 及更高版本上速度非常快（1 uop，3 周期延迟，1/时钟吞吐量），
但是在 Zen 3 之前的 AMD 上很慢（Zen1/2：7 微指令，18 个周期 latency/throughput）。 https://agner.org/optimize/ and https://uops.info/。我认为这比我使用纯 C 提出的 shift/mask 更糟糕，特别是如果延迟很重要或在循环中执行此操作（不仅仅是 front-end 吞吐量）。
#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 内在函数。
Portable ISO C++
我认为通常的乘法技巧（将多个输入字节移位并添加到结果的最高字节）在这里不起作用；你有太多的比特，它们靠得太近了。 use-case 见 How to count the number of set bits in a 32-bit integer? :
((n & 0x0F0F0F0F) * 0x01010101) >> 24 水平添加 n.
中的所有字节
您可以想象在您的输入中使用类似的东西 * 0x08040201 以不同方式对齐来自不同字节的位。但这仍然存在未解决的重大问题。也许 SIMD 与 8 位元素相乘以获得位对一起移位？
但这并不比通过屏蔽、移位和 ORing 或将移动的位与 not-moving 位相加来四处移动位更好。 大约 log2(n_bits) 步，我们可以得到所有连续的位。
有多种方法可以做到这一点，请参阅 on Godbolt。这方面还有改进的余地，例如调整以针对一个 ISA 与另一个 ISA 进行更好的编译。例如帮助一些 ARM 编译器看到 0b0000011000000110 只是另一个常量 right-shifted，因此它可以 and r0, r1, r2, lsr #4 或其他东西。
或者将位向右而不是向左移动，对于不能对左进行任何特殊操作的 ISA。
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 可以 left-shift-and-add 一条指令 LEA。在其他 ISA 上，它可能会在最后保存一个移位以将位向右移动。
这对 AArch64 和 PowerPC64 以及 x86 编译得很好。 Clang 看穿了 PowerPC 的这种位操作，并使用了强大的 rlwinm（Rotate Left Word Immediate AND Mask）和 rlwimi（... Mask Insert）指令 :) 至少它做到了。不幸的是，当前的 clang t运行k 现在正在执行两个 mulli 乘法指令，在 rlwinm + 3x rlwimi 之前；下面的 asm 来自这个答案是新的。
# 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 的改进版本：通过自身相加来移动位
屏蔽以保留一些位，然后将其添加到原始位置，将清除原始位置并产生一个进位。假设下一个更高的 space 已经归零，这将移动这些位，同时保留其他位。
这也使用内联 asm 来解决 GCC/clang 错过的优化，他们不只是在 x86 上使用 movzx 到 zero-extend 一个字节。似乎有 re-arranged 一些周围的逻辑，最终会花费更多的指令。
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 , %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;
}
用测试代码查看 on Godbolt。它同样适用于 ARM64，适用于 PowerPC，适用于 x86 / x86-64。如果您将 AND 常量模式调整为重复 32 位，那么对于 ARM64 可能更好，这样 GCC 就可以将它们用作立即数。
另一种移动位的方法是用 XOR 将选定的位归零，然后用移位和加法将它们移位并存放到其他地方。
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
当只移动2个位置时，add + shift-and-add与xor + shift-and-add.
的依赖链长度基本相同
但是有条件地清除旧位而不是使用相反的掩码可能更糟。至少如果相反的掩码适合立即数，或者如果 ISA 有 ANDNOT 指令。或者对于 ARM，移位掩码。 AND 旧 x 上的 2 种方法可以 运行 并行，而 tmp = x & mask; x ^= tmp 如果按编写的方式编译，则使用数据依赖性序列化执行。 （事实并非如此；gcc 和 clang 足够聪明，知道 XOR 的作用并无条件地清除这些位。）
x86 中最灵活的位操作（实际上，几乎任何 CPU）都是从内存中读取索引。它可以在恒定时间内完成完全任意的映射，通常在 1-4 个周期内（假设内存已缓存）。
因为你只谈论 8 位，你可以很容易地将你想要的位放入寄存器的低 8 位，尽管顺序错误，你可以只使用查找 table .
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,
};
有没有办法使用内部函数优化以下代码？它采用 16 位整数中的所有奇数索引位并将它们尽可能右移。
我在想也许可以使用 Fortran 中 ISHFTC 的 C++ 等价物（甚至有 C++ 等价物吗？）。但是我觉得还有更高效的方法。
int x = some16bitInt;
x = x&0x5555;
int y = 0;
for (int i = 0; i < 8; i++)
y = y | ((x >> i) & (0x01 << i));
'''
当然可以，方法如下：
int y = (int)_pext_u32( (unsigned int)some16bitInt, 0x5555 );
很遗憾，此指令来自 BMI2 集，需要相对较新的 CPU、Intel Haswell 或更新版本、AMD Excavator 或更新版本。但是在支持的地方，速度非常快。
x86：如果可用，使用 BMI2
pext，Zen2 或更早的 AMD 除外。否则：@jorgbrown 建议对我的 bithack 进行一个很好的改进。
或者如果你在没有快速
pext的情况下在循环中做很多这样的事情，那么在打包你想要的所有位之后，值得考虑 Jorg 的 table 查找想法some 顺序中的低 8，因此 table 只有 256 x 1 字节条目。
Fortran ISHFTC is just a rotate. C doesn't directly have this, but you can portably + safely write a function that compilers with pattern-recognize and compile to a single rotate instruction. Best practices for circular shift (rotate) operations in C++
我不确定这是一个有用的构建基块，但它是可用的。
在具有 BMI2 instruction-set 扩展 的 x86 上，有一条 pext bit-extract 指令，您可以将其与 0x5555控制输入。
请参阅 _pext_u32 和 _u64
在 Intel Haswell 及更高版本上速度非常快（1 uop，3 周期延迟，1/时钟吞吐量），
但是在 Zen 3 之前的 AMD 上很慢（Zen1/2：7 微指令，18 个周期 latency/throughput）。 https://agner.org/optimize/ and https://uops.info/。我认为这比我使用纯 C 提出的 shift/mask 更糟糕，特别是如果延迟很重要或在循环中执行此操作（不仅仅是 front-end 吞吐量）。
#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 内在函数。
Portable ISO C++
我认为通常的乘法技巧（将多个输入字节移位并添加到结果的最高字节）在这里不起作用；你有太多的比特，它们靠得太近了。 use-case 见 How to count the number of set bits in a 32-bit integer? :
((n & 0x0F0F0F0F) * 0x01010101) >> 24 水平添加 n.
您可以想象在您的输入中使用类似的东西 * 0x08040201 以不同方式对齐来自不同字节的位。但这仍然存在未解决的重大问题。也许 SIMD 与 8 位元素相乘以获得位对一起移位？
但这并不比通过屏蔽、移位和 ORing 或将移动的位与 not-moving 位相加来四处移动位更好。 大约 log2(n_bits) 步，我们可以得到所有连续的位。
有多种方法可以做到这一点，请参阅 on Godbolt。这方面还有改进的余地，例如调整以针对一个 ISA 与另一个 ISA 进行更好的编译。例如帮助一些 ARM 编译器看到 0b0000011000000110 只是另一个常量 right-shifted，因此它可以 and r0, r1, r2, lsr #4 或其他东西。
或者将位向右而不是向左移动，对于不能对左进行任何特殊操作的 ISA。
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 可以 left-shift-and-add 一条指令 LEA。在其他 ISA 上，它可能会在最后保存一个移位以将位向右移动。
这对 AArch64 和 PowerPC64 以及 x86 编译得很好。 Clang 看穿了 PowerPC 的这种位操作，并使用了强大的 rlwinm（Rotate Left Word Immediate AND Mask）和 rlwimi（... Mask Insert）指令 :) 至少它做到了。不幸的是，当前的 clang t运行k 现在正在执行两个 mulli 乘法指令，在 rlwinm + 3x rlwimi 之前；下面的 asm 来自这个答案是新的。
# 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 的改进版本：通过自身相加来移动位
屏蔽以保留一些位，然后将其添加到原始位置，将清除原始位置并产生一个进位。假设下一个更高的 space 已经归零，这将移动这些位，同时保留其他位。
这也使用内联 asm 来解决 GCC/clang 错过的优化，他们不只是在 x86 上使用 movzx 到 zero-extend 一个字节。似乎有 re-arranged 一些周围的逻辑，最终会花费更多的指令。
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 , %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;
}
用测试代码查看 on Godbolt。它同样适用于 ARM64，适用于 PowerPC，适用于 x86 / x86-64。如果您将 AND 常量模式调整为重复 32 位，那么对于 ARM64 可能更好，这样 GCC 就可以将它们用作立即数。
另一种移动位的方法是用 XOR 将选定的位归零，然后用移位和加法将它们移位并存放到其他地方。
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
当只移动2个位置时，add + shift-and-add与xor + shift-and-add.
的依赖链长度基本相同但是有条件地清除旧位而不是使用相反的掩码可能更糟。至少如果相反的掩码适合立即数，或者如果 ISA 有 ANDNOT 指令。或者对于 ARM，移位掩码。 AND 旧 x 上的 2 种方法可以 运行 并行，而 tmp = x & mask; x ^= tmp 如果按编写的方式编译，则使用数据依赖性序列化执行。 （事实并非如此；gcc 和 clang 足够聪明，知道 XOR 的作用并无条件地清除这些位。）
x86 中最灵活的位操作（实际上，几乎任何 CPU）都是从内存中读取索引。它可以在恒定时间内完成完全任意的映射，通常在 1-4 个周期内（假设内存已缓存）。
因为你只谈论 8 位，你可以很容易地将你想要的位放入寄存器的低 8 位，尽管顺序错误，你可以只使用查找 table .
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,
};