c - 如何生成 256 位掩码

Question

我有一个 uint64_t[4] 数组，我需要生成一个掩码，这样数组，如果它是一个 256 位整数，等于(1 << w) - 1，其中 w 从 1 到 256。

我想出的最好的事情是无分支，但它需要很多指令。它在 Zig 中，因为 Clang 似乎没有暴露 llvm 的饱和减法。 http://localhost:10240/z/g8h1rV

有更好的方法吗？

var mask: [4]u64 = undefined;
for (mask) |_, i|
    mask[i] = 0xffffffffffffffff;
mask[3] ^= ((u64(1) << @intCast(u6, (inner % 64) + 1)) - 1) << @intCast(u6, 64 - (inner % 64));
mask[2] ^= ((u64(1) << @intCast(u6, (@satSub(u32, inner, 64) % 64) + 1)) - 1) << @intCast(u6, 64 - (inner % 64));
mask[1] ^= ((u64(1) << @intCast(u6, (@satSub(u32, inner, 128) % 64) + 1)) - 1) << @intCast(u6, 64 - (inner % 64));
mask[0] ^= ((u64(1) << @intCast(u6, (@satSub(u32, inner, 192) % 64) + 1)) - 1) << @intCast(u6, 64 - (inner % 64));

Answer 1

对于 256 位 vector ，您是否将 AVX2 定位为 x86-64？我认为这是一个有趣的案例。

如果是这样，您可以使用饱和减法和变量计数移位在几条指令中完成此操作。

x86 SIMD 转变为 vpsrlvq 使移位计数饱和，当计数 >= 元素宽度时将所有位移出。与整数移位不同，移位计数被屏蔽(因此环绕)。

求最低u64元素，从全一开始，我们需要为 bitpos 保留它不变>= 64。或者 对于较小的位位置，将其右移 64-bitpos 。正如您所观察到的，无符号饱和减法看起来像是为更大的位位置创建 0 的移位计数的方法。但是 x86 只有 SIMD 饱和减法，并且只针对字节或字元素。但如果我们不关心 bitpos > 256，那很好，我们可以在每个 u64 的底部使用 16 位元素，并让 0-0发生在 u64 的其余部分.

您的代码看起来过于复杂，创建了 (1<<n) - 1和异或。 我认为在 0xFFFF...FF 上使用可变计数移位要容易得多直接元素。

我不了解 Zig，所以尽你所能让它像这样发出 asm。希望这很有用，因为您标记了这个 assembly ;应该很容易转化为 C 的内在函数，或者 Zig(如果有的话)。

default rel
section .rodata
shift_offsets:  dw  64, 128, 192, 256        ; 16-bit elements, to be loaded with zero-extension to 64

section .text
pos_to_mask256:
    vpmovzxwq   ymm2, [shift_offsets]      ; _mm256_set1_epi64x(256, 192, 128, 64)
    vpcmpeqd    ymm1, ymm1,ymm1            ; ymm1 = all-ones
                                  ; set up vector constants, can be hoisted

    vmovd         xmm0, edi
    vpbroadcastq  ymm0, xmm0           ; ymm0 = _mm256_set1_epi64(bitpos)

    vpsubusw      ymm0, ymm2, ymm0     ; ymm0 = {256,192,128,64}-bitpos with unsigned saturation
    vpsrlvq       ymm0, ymm1, ymm0     ; mask[i] >>= count, where counts >= 64 create 0s.

    ret

如果输入整数从内存中开始，您当然可以有效地将其直接广播加载到 ymm 寄存器中。

shift-offsets vector 当然可以被提升到循环之外，全一也是如此。

---

输入 = 77 时，高 2 位元素通过移位 256-77=179 和 192-77=115 位归零。用NASM + GDB测试EDI=77，结果为

(gdb) p /x $ymm0.v4_int64
{0xffffffffffffffff, 0x1fff, 0x0, 0x0}

GDB 首先打印低元素，与 Intel 符号/图表相反。这个 vector 实际上是0, 0, 0x1fff, 0xffffffffffffffff ，即 64+13 = 77 个一位，其余全为零。其他测试用例

• edi=0 : mask = 全零
• edi=1 : 掩码 = 1
• ... : 掩码 = edi一位在底部，然后是零
• edi=255 : mask = 除了顶部元素的最高位之外的所有
• edi=256 : 掩码 = 所有
• edi>256 : 掩码 = 所有。 (无符号减法在任何地方都饱和为 0。)

---

您需要 AVX2 进行可变计数转换。 psubusb/w is SSE2 ，因此您可以考虑使用 SIMD 完成该部分，然后返回标量整数进行移位，或者一次只对一个元素使用 SSE2 移位。喜欢 psrlq xmm1, xmm0 它采用 xmm0 的低 64 位作为 xmm1 的所有元素的移位计数。

大多数 ISA 不具有饱和标量减法。我认为某些 ARM CPU 会处理整数标量，但 x86 不会。 IDK 你正在使用什么。

在 x86(和许多其他 ISA)上你有 2 个问题:

• 为低位元素保留全1(修改移位结果，或将移位计数饱和为0)
• 生产 0对于包含掩码最高位的元素之上的高元素。 x86 标量移位根本无法做到这一点，因此您可以为移位输入 0。对于那种情况。也许使用 cmov根据 sub 设置的标志创建它对于 192-w什么的。

    count = 192-w;
    shift_input = count<0 ? 0 : ~0ULL;
    shift_input >>= count & 63;      // mask to avoid UB in C.  Optimizes away on x86 where shr does this anyway.

嗯，不过，这不会处理将减法饱和到 0 以保留全一。

如果针对 x86 以外的 ISA 进行调优，也许可以查看其他一些选项。或者也许在 x86 上也有更好的东西。使用 sar reg,63 创建全一或全零是一个有趣的选项(广播符号位)，但是当 192-count 时我们实际上需要全一符号位 = 0。