如何生成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位向量使用AVX2定位x86-64？我认为这是一个有趣的案例可以回答。

如果是这样，您可以使用饱和减法和可变计数移位在一些指令中执行此操作。

像vpsrlvq这样的x86 SIMD移位使移位计数饱和，当计数> =元素宽度时将所有位移出。与整数移位不同，移位计数被屏蔽（因此包裹）。

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

您的代码看起来非常复杂，创建了(1<<n) - 1和XORing。我认为直接在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寄存器中。

移位偏移矢量当然可以从循环中提升，全部也可以。

---

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

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

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

• edi=0：mask =全零
• edi=1：mask = 1
• ...：mask = edi底部有一位，然后是0
• edi=255：mask =除顶部元素的顶部位之外的所有部分
• edi=256：mask =所有的
• edi>256：mask =所有的。 （无符号减法到处都是饱和的。）

---

您需要AVX2进行可变计数转换。 psubusb/w is SSE2，所以你可以考虑用SIMD做那个部分，然后回到标量整数来换班，或者也许只是一次使用一个元素的SSE2转换。像psrlq xmm1, xmm0一样，它将低位64位的xmm0作为xmm1所有元素的移位计数。

大多数ISA没有饱和标量减法。我认为有些ARM CPU会用于标量整数，但x86却没有。 IDK你在用什么。

在x86（以及许多其他ISA）上，您有两个问题：

• 保留所有低值元素（修改移位结果，或将移位计数饱和为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创建全0或全零是一个有趣的选项（广播符号位），但是当192-count的符号位= 0时，我们实际上需要全1。