c++ - 将 16 位掩码转换为 16 字节掩码

Question

有什么办法可以转换以下代码：

int mask16 = 0b1010101010101010; // int or short, signed or unsigned, it does not matter

至

__uint128_t mask128 = ((__uint128_t)0x0100010001000100 << 64) | 0x0100010001000100;

所以要特别清楚，比如：

int mask16 = 0b1010101010101010; 
__uint128_t mask128 = intrinsic_bits_to_bytes(mask16);

或直接涂抹面膜：

int mask16 = 0b1010101010101010; 
__uint128_t v = ((__uint128_t)0x2828282828282828 << 64) | 0x2828282828282828;
__uint128_t w = intrinsic_bits_to_bytes_mask(v, mask16); // w = ((__uint128_t)0x2928292829282928 << 64) | 0x2928292829282928;

标签： c++cbit-manipulationsseintrinsics

Answer 1

位/字节顺序：除非另有说明，否则这些都跟在问题后面，将 LSB 放在（little-endian x86 上的最低内存地址）的最低uint16_t有效字节中。__uint128_t例如，对于位图的 ASCII 转储，这是您想要的，但它与单个 16 位数字的 base-2 表示形式的位值打印顺序相反。

有效地将值（返回）到 RDX:RAX 整数寄存器的讨论与大多数正常用例无关，因为您只需从向量寄存器存储到内存中，无论是0/1字节整数还是 ASCII '0'/'1'数字（你可以得到在 a中没有0/1整数的情况下最有效__m128i，更不用说在 a 中了unsigned __int128）。

目录：

• SSE2 / SSSE3 版本：如果您希望将结果保存在 vector中，例如用于存储 char 数组，则很好。
  （SSE2 NASM 版本，改组为 MSB 优先打印顺序并转换为 ASCII。）
• BMI2 pdep：unsigned __int128如果您要在标量寄存器中使用结果，则适用于带有 BMI2 的 Intel CPU 上的标量。AMD慢。
• 带有乘法 bithack 的纯 C++：对于标量来说非常合理
• AVX-512：AVX-512 使用标量位图将掩码作为一级操作。pdep如果您将结果用作标量一半，则可能不如 BMI2 ，否则甚至比 SSSE3 更好。
• 32 位整数的AVX2打印顺序（最低地址的 MSB）转储。
• 另请参阅intel avx2 中的 movemask 指令是否有逆指令？对于元素大小和掩码宽度的其他变化。（SSE2 和乘法 bithack 改编自该集合链接的答案。）

使用 SSE2（最好是 SSSE3）

请参阅@aqrit 的如何使用 x86 SIMD答案有效地将 8 位位图转换为 0/1 整数数组

调整它以使用 16 位 -> 16 字节，我们需要一个 shuffle 将掩码的第一个字节复制到向量的前 8 个字节，并将第二个掩码字节复制到高 8 个向量字节。使用一个 SSSE3pshufb或使用punpcklbw same,same++最终复制最多两个 64 位 qwordspunpcklwd same,same是可行的。punpckldq same,same

typedef unsigned __int128  u128;

u128 mask_to_u128_SSSE3(unsigned bitmap)
{
    const __m128i shuffle = _mm_setr_epi32(0,0, 0x01010101, 0x01010101);
    __m128i v = _mm_shuffle_epi8(_mm_cvtsi32_si128(bitmap), shuffle);  // SSSE3 pshufb

    const __m128i bitselect = _mm_setr_epi8(
        1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1U<<7,
        1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1U<<7 );
    v = _mm_and_si128(v, bitselect);
    v = _mm_min_epu8(v, _mm_set1_epi8(1));       // non-zero -> 1  :  0 -> 0
    // return v;   // if you want a SIMD vector result

    alignas(16) u128 tmp;
    _mm_store_si128((__m128i*)&tmp, v);
    return tmp;   // optimizes to movq / pextrq (with SSE4)
}

（要获得 0 / 0xFF 而不是 0 / 1，请替换_mm_min_epu8为v= _mm_cmpeq_epi8(v, bitselect)。 如果您想要一串 ASCII '0'/'1'字符，请执行 cmpeq 和_mm_sub_epi8(_mm_set1_epi8('0'), v)。这样可以避免 set1(1) 向量常数。）

Godbolt包括测试用例。（对于这个和其他非 AVX-512 版本。）

# clang -O3 for Skylake
mask_to_u128_SSSE3(unsigned int):
        vmovd   xmm0, edi                                  # _mm_cvtsi32_si128
        vpshufb xmm0, xmm0, xmmword ptr [rip + .LCPI2_0] # xmm0 = xmm0[0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1]
        vpand   xmm0, xmm0, xmmword ptr [rip + .LCPI2_1]    # 1<<0, 1<<1, etc.
        vpminub xmm0, xmm0, xmmword ptr [rip + .LCPI2_2]    # set1_epi8(1)

  # done here if you return __m128i v or store the u128 to memory
        vmovq   rax, xmm0
        vpextrq rdx, xmm0, 1
        ret

---

BMI2 pdep：对 Intel 好，对 AMD 不好

BMI2pdep在拥有它的 Intel CPU 上速度很快（从 Haswell 开始），但在 AMD 上却非常慢（超过 12 个微指令，高延迟。）

typedef unsigned __int128  u128;
inline u128 assemble_halves(uint64_t lo, uint64_t hi) {
    return ((u128)hi << 64) | lo; }
// could replace this with __m128i using _mm_set_epi64x(hi, lo) to see how that compiles

#ifdef __BMI2__
#include <immintrin.h>
auto mask_to_u128_bmi2(unsigned bitmap) {
    // fast on Intel, slow on AMD
    uint64_t tobytes = 0x0101010101010101ULL;
    uint64_t lo = _pdep_u64(bitmap, tobytes);
    uint64_t hi = _pdep_u64(bitmap>>8, tobytes);
    return assemble_halves(lo, hi);
}

如果您希望在标量寄存器（不是一个向量）中得到结果，那很好，否则可能更喜欢 SSSE3 方式。

# clang -O3
mask_to_u128_bmi2(unsigned int):
        movabs  rcx, 72340172838076673    # 0x0101010101010101
        pdep    rax, rdi, rcx
        shr     edi, 8
        pdep    rdx, rdi, rcx
        ret
      # returns in RDX:RAX

---

带有魔法乘法位黑客的便携式 C++

在 x86-64 上还不错；自 Zen 以来的 AMD 拥有快速的 64 位乘法，而英特尔自 Nehalem 以来就有。一些低功耗的 CPU 仍然慢imul r64, r64

这个版本可能是最佳的__uint128_t结果，至少对于没有 BMI2 的 Intel 和 AMD 的延迟，因为它避免了到 XMM 寄存器的往返。但是对于吞吐量，它是相当多的指令

请参阅@phuclv 关于如何从 8 个布尔值中创建一个字节的答案（反之亦然）？有关乘法的解释，以及相反的方向。对. unpack8bools_mask

//#include <endian.h>     // glibc / BSD
auto mask_to_u128_magic_mul(uint32_t bitmap) {
    //uint64_t MAGIC = htobe64(0x0102040810204080ULL); // For MSB-first printing order in a char array after memcpy.  0x8040201008040201ULL on little-endian.
    uint64_t MAGIC = 0x0102040810204080ULL;    // LSB -> LSB of the u128, regardless of memory order
    uint64_t MASK  = 0x0101010101010101ULL;
    uint64_t lo = ((MAGIC*(uint8_t)bitmap) ) >> 7;
    uint64_t hi = ((MAGIC*(bitmap>>8)) ) >> 7;

    return assemble_halves(lo & MASK, hi & MASK);
}

如果您打算将 存储__uint128_t到内存中memcpy，您可能希望通过使用htole64(0x0102040810204080ULL);（来自GNU / BSD <endian.h>）或等效于始终将输入的低位映射到输出的最低字节来控制主机字节序，即到一个char或bool数组的第一个元素。或htobe64其他订单，例如打印。在常量而不是变量数据上使用该函数允许在编译时进行常量传播。

否则，如果你真的想要一个低位与 u16 输入的低位匹配的 128 位整数，则乘数常数与主机字节序无关；没有对更广泛类型的字节访问。

x86-64 的铿锵声 12.0 -O3：

mask_to_u128_magic_mul(unsigned int):
        movzx   eax, dil
        movabs  rdx, 72624976668147840   # 0x0102040810204080
        imul    rax, rdx
        shr     rax, 7
        shr     edi, 8
        imul    rdx, rdi
        shr     rdx, 7
        movabs  rcx, 72340172838076673   # 0x0101010101010101
        and     rax, rcx
        and     rdx, rcx
        ret

---

AVX-512

使用 AVX-512BW很容易；0x01您可以将掩码用于来自重复常数的零掩码负载。

__m128i bits_to_bytes_avx512bw(unsigned mask16) {
    return _mm_maskz_mov_epi8(mask16, _mm_set1_epi8(1));

//    alignas(16) unsigned __int128 tmp;
//    _mm_store_si128((__m128i*)&u128, v);  // should optimize into vmovq / vpextrq
//    return tmp;
}

或者避免使用内存常量（因为编译器可以set1(-1) 只使用 avpcmpeqd xmm0,xmm0）：对-1. 常量设置可以提升，与 set1(1) 相同。

__m128i bits_to_bytes_avx512bw_noconst(unsigned mask16) {
    __m128i ones = _mm_set1_epi8(-1);    // extra instruction *off* the critical path
    return _mm_maskz_abs_epi8(mask16, ones);
}

但请注意，如果做进一步的向量操作，结果maskz_mov可能会优化到其他操作中。例如 vec += maskz_mov 可以优化为合并屏蔽添加。但如果没有，vmovdqu8 xmm{k}{z}, xmm需要一个类似的 ALU 端口vpabsb xmm{k}{z}, xmm，但vpabsb不能在 Skylake/Ice Lake 的端口 5 上运行。（从零寄存器中进行零掩码vpsubb可以避免这种可能的吞吐量问题，但是您将设置 2 个寄存器只是为了避免加载常量。在手写 asm 中，如果您愿意，您只需set1(1)使用vpcmpeqd/vpabsb自己实现以避免常量的 4 字节广播负载。）

（带有 gcc 和 clang的Godbolt 编译器资源管理器。Clang-O3 -march=skylake-avx512看穿了掩码vpabsb并编译它与第一个版本相同，具有内存常量。）

如果您可以使用向量 0 / -1 而不是 0 / 1，那就更好了：使用return _mm_movm_epi8(mask16). 编译为kmovd k0, edi/vpmovm2b xmm0, k0

如果你想要一个 ASCII 字符的向量，比如'0'or'1'，你可以使用_mm_mask_blend_epi8(mask, ones, zeroes). （这应该比将合并掩码添加到需要额外寄存器副本的向量中更有效，并且set1(1)也比需要 2 条指令的 sub between 更好：一个将掩码转换为向量，以及一个单独的 vpsubb .)set1('0')_mm_movm_epi8(mask16)

---

AVX2 位按打印顺序（MSB 在最低地址），字节按内存顺序，ASCII '0' / '1'

使用此输出格式的[]分隔符和制表符，来自此 codereview Q&A：\t

[01000000]      [01000010]      [00001111]      [00000000]

显然，如果您希望所有 16 或 32 个 ASCII 数字都是连续的，那会更容易，并且不需要打乱输出以分别存储每个 8 字节块。在这里发布的主要原因是它具有正确的打印顺序的 shuffle 和 mask 常量，并在结果证明这是问题真正想要的之后显示针对 ASCII 输出优化的版本。

使用如何执行 _mm256_movemask_epi8 (VPMOVMSKB) 的逆运算？，基本上是256位版本的SSSE3代码。

#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <immintrin.h>
#include <string.h>

// https://stackoverflow.com/questions/21622212/how-to-perform-the-inverse-of-mm256-movemask-epi8-vpmovmskb
void binary_dump_4B_avx2(const void *input)
{
    char buf[CHAR_BIT*4 + 2*4 + 3 + 1 + 1];  // bits, 4x [], 3x \t, \n, 0
    buf[0] = '[';
    for (int i=9 ; i<sizeof(buf) - 8; i+=11){ // GCC strangely doesn't unroll this loop
        memcpy(&buf[i], "]\t[", 4);       // 4-byte store as a single; we overlap the 0 later
    }
    __m256i  v = _mm256_castps_si256(_mm256_broadcast_ss(input));         // aliasing-safe load; use _mm256_set1_epi32 if you know you have an int
    const __m256i shuffle = _mm256_setr_epi64x(0x0000000000000000,        // low byte first, bytes in little-endian memory order
      0x0101010101010101, 0x0202020202020202, 0x0303030303030303);
    v =  _mm256_shuffle_epi8(v, shuffle);

//    __m256i bit_mask = _mm256_set1_epi64x(0x8040201008040201);    // low bits to low bytes
    __m256i bit_mask = _mm256_set1_epi64x(0x0102040810204080);      // MSB to lowest byte; printing order

    v = _mm256_and_si256(v, bit_mask);               // x & mask == mask
//    v = _mm256_cmpeq_epi8(v, _mm256_setzero_si256());       // -1  /  0  bytes
//    v = _mm256_add_epi8(v, _mm256_set1_epi8('1'));          // '0' / '1' bytes

    v = _mm256_cmpeq_epi8(v, bit_mask);              // 0 / -1  bytes
    v = _mm256_sub_epi8(_mm256_set1_epi8('0'), v);   // '0' / '1' bytes
    __m128i lo = _mm256_castsi256_si128(v);
    _mm_storeu_si64(buf+1, lo);
    _mm_storeh_pi((__m64*)&buf[1+8+3], _mm_castsi128_ps(lo));

    // TODO?: shuffle first and last bytes into the high lane initially to allow 16-byte vextracti128 stores, with later stores overlapping to replace garbage.
    __m128i hi = _mm256_extracti128_si256(v, 1);
    _mm_storeu_si64(buf+1+11*2, hi);
    _mm_storeh_pi((__m64*)&buf[1+11*3], _mm_castsi128_ps(hi));
//    buf[32 + 2*4 + 3] = '\n';
//    buf[32 + 2*4 + 3 + 1] = '\0';
//    fputs
    memcpy(&buf[32 + 2*4 + 2], "]", 2);  // including '\0'
    puts(buf);                           // appends a newline
     // appending our own newline and using fputs or fwrite is probably more efficient.
}

void binary_dump(const void *input, size_t bytecount) {
}
 // not shown: portable version, see Godbolt, or my or @chux's answer on the codereview question


int main(void)
{
    int t = 1000000;
    binary_dump_4B_avx2(&t);
    binary_dump(&t, sizeof(t));
    t++;
    binary_dump_4B_avx2(&t);
    binary_dump(&t, sizeof(t));
}

可运行的Godbolt 演示，带有gcc -O3 -march=haswell.

请注意，GCC10.3 和更早版本是哑的，并且复制 AND/CMPEQ 向量常量，一次作为字节，一次作为 qwords。（在这种情况下，与零比较会更好，或者使用带有反转掩码的 OR 并与全一比较）。GCC11.1 使用 a 修复了该问题.set .LC1,.LC2，但仍将其加载两次，作为内存操作数，而不是将一次加载到寄存器中。Clang 没有这些问题。

有趣的事实：clang-march=icelake-client设法将其第二部分转换为 AVX-512 掩码'0'和'1'向量之间的混合，但kmov它不仅仅使用广播加载、vpermb字节洗牌，然后使用位掩码进行测试掩码。