您能否在一个汇编操作中检查一个字节的标志,并检索剩余的 7 位整数值?

Can you check a flag on a byte, AND retrieve the remaining 7-bit integer value, in one assembly operation?

获取 8 位、16 位、32 位或 64 位数字的最佳方法(fewest/fastest 操作)是什么,从中提取第一位,检查是否位为真,同时存储删除前导位后的结果数? (在汇编中)。

integerInBitsWithLeadingFlag = 10001000
flag == 1
integer == 0001000 = 1000

在汇编中,我知道在除法和保留余数方面有很多技巧,在结果中存储两个变量,或其他类似的东西。也许有一些方法可以在汇编中做到这一点。

我问的原因是因为我想在 8 位值序列中存储大量数字,其中前导位是标志,表示 "more" 值是否应该连接在一起,剩下的7位用来计算最后的integer/bigint。如果最好将标志存储在 last/trailing 位上,那么最好包含 :)

我是汇编的新手,所以我不太确定如何做到这一点。

; assembly pseudocode
start:
  AND rax, 10000000 ; AND the value with a leading 1 (or something like this)
  CMP rax, 1 ; compare the leading value with 1 to see if it matches.
  JE matches
  JNE notmatches

matches:
  ; remove bit from rax to get integer value.

notmatches:
  ; same, remove bit from rax to get integer value.

有没有什么我可以按照这些思路来做的:

start:
  ANDFLAGWITHREMAINDER rax, 10000000
  ; and now, after 1 operation,
  ; you have the flag and the integer.

如果不是,正确的方法是什么?

x86 Bit Test and Reset btr eax, 7 完全按照您的要求进行:清除位 7 并设置 CF = 该位的原始值。

btr reg, immreg, reg 在 Intel 上是 1 微指令,在 AMD 上是 2 微指令。但是,当后跟 jcc 指令时,它不能像 test al, 1<<7 / jnz 那样宏融合为单个比较和分支 uop。 (https://agner.org/optimize/)。 指令数不是影响性能的唯一因素。良好的 ILP 和较短的关键路径延迟,尤其是避免不必要的循环携带依赖链,也很重要。但是计算代码中快速路径的前端 uops 绝对值得考虑。

x86 移位(像大多数 ISA)将移出的最后一位放入进位标志。所以 shr al, 1 设置 CF = orig & 1 并更新 AL = orig >> 1。可能有一种方法可以将其与跨字节移动位结合起来,以便像 shrd 或部分寄存器技巧那样合并它们...

由于您正在操作字节,因此如果您正在考虑如何将多个位域组合成一个寄存器中的一个连续的较大整数,则可能需要了解


I want to store large numbers in a sequence of 8-bit values

我希望您不打算直接使用该格式的数字进行计算。这听起来很合理,作为一种紧凑的可变长度序列化格式/编码,对于小值可以小于 int,但如果需要,仍然可以达到 uint64_t 甚至更大。

如果整体速度更重要,则以至少 32 位的块工作,这样每个 CPU 操作将获得更多的结果位。或者说,组合成单个连续二进制整数的解包步骤更少。 (例如 AVX2 变量移位 vpsrlvd 将一个双字的顶部与下一个更高元素中的双字的底部相邻,然后使用 qword 变量移位在 128 位通道的中间做同样的事情。然后字节移位或随机播放。

(但是,您可以使用 16 位 pmullw 对 16 位元素执行此操作 如果您使用 16 位块,则乘以 2(或 1)的幂。或 AVX512BW 可变计数或合并屏蔽 16 位移位。或带有 pmaddubsw 的 8 位块甚至可以使用正确的乘数组合到 SIMD 元素的底部:11<<7 用于每对的低字节和高字节,在屏蔽掉信号位。)

字节通常是 BigInteger 东西的一般错误。请参阅 BigInt class in C++ 上的此代码审查答案(不明智地计划将数字存储为 ASCII 十进制数字数组)。 32 位块中的 30 个值位对于可移植的东西(如 Python 内部使用)可能很有用。如果您进行大量转换 to/from 十进制字符串,则可以使用 10^9 这样的基数,否则可以使用 2^30。

不使用每个分支的所有位允许您延迟 SIMD 的进位(不归一化):Can long integer routines benefit from SSE?。这可以使用 1 个备用位进行进位,最高位专用于隐式长度的信号策略而不是存储长度。 (许多 x86 SIMD 指令,如 blendvpsmovmskps 使双字 SIMD 元素的最高位变得特殊,或者使整数 SIMD 的每个字节的最高位如 pmovmskbpshufbpblendvb。所以你可以获得高位的位掩码,你可以使用 bsfbsr 进行位扫描以找到第一个设置位。)


开箱思路:

如果您选择整数中每个字节的高位 = 0,并选择 1 表示结束,则可以避免必须清除的杂散设置位。

如前所述,pmaddubsw 是 SIMD 将字节组合成 16 位字的好选择,具有正确的 11<<7 乘数。

然后 pmaddwd 的另一个步骤可以将单词与 11<<14 组合成双字,然后您就可以为 AVX2 vpsrlv 设置或只是移动和混合.然后所有这些都采用 log2(vector_length) 步数而不是 vector_length 步数。

没有 SIMD,您可以使用 x += x 作为左移,但通过执行 x += x & mask 使其仅移动 一些 位。这适用于标量,如果您没有 SSSE3 pmaddubsw,则适用于 paddb。 (或者使用 AVX512BW 字节掩码 vpaddb 比 pmadd 延迟更低。)

   x = ... (bits) 0abcdefg 0ABCDEFG
   +  (hex) x & 0x...00FF00FF
                  0abcdefg ABCDEFG0

这为您提供了包含 14 个值位的连续 16 位块。不过,这次每个块由 two 0 位分隔,因此掩码加法并不是最有效的处理方式。可能从那里开始,AND 与 0xFFFF0000FFFF0000 并将其右移 2,然后以另一种方式掩盖原件并与 OR 混合。


使用 BMI2 反序列化此格式 pext 并行位 EXTract

pext 在 AMD 上运行缓慢(微编码,非专用硬件,即使在 Zen2 上也是如此),并且 BMI2 并非随处可用。但是在 Intel CPUs 上它是 1 uop,3 周期延迟,1/时钟吞吐量。 https://uops.info/

请注意,您可以在 C 中使用内在函数:Intel 的online intrinsics guide / search。 (非 SIMD 标量内部函数跨编译器的可移植性可能参差不齐,但用于 popcnt 和 BMI 等新指令的移植性通常很好。)编译器可能不擅长使用 btr 到 CSE x&(1<<7)x &= ~(1<<7) 成一个单一的操作,但他们应该处理这段代码,即使你写的东西像 (~mask) & x 而不是内在函数。尽管编译器可能会进行常量传播并实现 and 的倒置常量,而不是 andn.

给定一个指向此格式的未知长度数字的指针,加载最多 8 个字节并从中提取最多 56 个值位。 (假设 qword 加载是安全的:可能加载垃圾,但不会进入未映射的页面和错误:

; input pointer in RDI: a set bit 7 indicates end of number
; clobbers RCX, RDX
; result in RAX
;; great on Intel, probably can do better on AMD one byte at a time or with SIMD pmaddubsw 

    mov    rcx, [rdi]                     ; 8 bytes, including possible trailing garbage
    mov    rdx, 0x7F7F7F7F7F7F7F7F
    andn   rsi, rdx, rcx                  ; isolate high bits: (~rdx) & rcx

    blsmsk rax, rsi                       ; get mask up to lowest set bit: (rsi-1) XOR rsi = mask up to (and including) the first signal bit
    and    rax, rcx                       ; clear high garbage
       ; RAX = 0 above the number.  The end-of-number flag is still set but pext only grabs bits 6:0 from each byte.

    pext   rax, rax, rdx                  ; rax = 8x 7-bit fields packed down to low 56
   ; uint64_t result in RAX, from the first 1 to 8 bytes of [rdi],
   ; depending on where the first number-end flag was

如果没有字节设置其高位,blsmsk 全零输入会产生全一输出。因此,我们为数字未结束的情况以及设置输入的最高位的情况提取所有 8 个字节。

andnblsmsk 是单 uop 单周期延迟,但它们在导致 pext 的依赖链中,因为在这个块中没有指令级并行性一次迭代。它非常短,所以如果我们对另外 8 个字节的数据进行另一次迭代,OoO exec 可以很好地重叠。

如果我们可以 运行 pext 与计算我们可以在其 输出 而不是输入上使用的掩码并行计算,那就太好了。但是那个 7:8 比例是个问题。我们可以并行 运行 pext 两次(使用不同的掩码)将每个字节的高位与 blsmsk 需要的位置对齐。或者我们可以 tzcnt 找到最低设置位的位置,然后以某种方式乘以 7/8。该位置是 8 的倍数,因此我们可以 tzcnt 并执行 x - (x>>3) 或其他操作,然后将该位索引用于 BMI2 bzhi.

如果您有这种格式的压缩数字流,您会想要找到下一个数字的开始位置。从 rsi 独立的结束标志模式,您可以 rsi = tzcnt(rsi) 然后 rsi >>= 3 找到第一个数字结束位的字节索引。

你需要比那个多加 1 才能过去。你可以做 lea rdi, [rdi + rsi + 1] 但与 inc rdi / add rdi, rsi 相比有额外的延迟,因为 3 组件 LEA(两个 + 操作)。

或者如果你在tzcnt之前左移掩码tzcnt,你可以直接这样做,作为奖励它会将无终止符视为8 而不是 9.

    add   rsi, rsi               ; left-shift the end-of-number flags to the bottom of the next byte (or out)
    tzcnt rsi, rsi               ; rsi = bit-index of first bit of next number, 64 if RSI=0

 ; shrx  rcx, rcx, rsi           ; shift to the bottom and restart instead of reloading

    shr   esi, 3                 ; bit index -> byte index.  We know it's a small integer so 32-bit operand-size is fine and more saves code-size
    add   rdi, rsi               ; advance the pointer

这项工作可以 运行 与 blsmsk 和 pext 并行进行。尽管如果我们正在做 tzcnt 工作,也许我们应该使用 bzhi 而不是 blsmsk/and。这可能对吞吐量更好,但对延迟更糟:add -> tzcnt 是从 RSI 开始准备的 4 个延迟周期,然后输入已准备好 [=7​​0=],所有这些都在通往 pext 的关键路径。对比 blsmsk/and 只有 2 个周期。


或者如果我们想循环直到找到单个数字(超过 8 个字节)的结尾,RSI 仍然持有隔离信号位。这就是为什么我 andn 进入 RSI,而不是进入 RAX。

    ... continuing from above to keep going until the end of large number
    ... do something with the 56-bit RAX chunks, like overlapping stores into memory?
    ; rsi still holds the isolated signal bits
    add    rdi, 8
    test   rsi, rsi
    jnz   .loop                     ; }while(end of number not found)

blsmsk 如果其输入为零则设置 CF,因此如果我们可以在底部使用 blsmsk 构建我们的循环,我们可以将其用作循环分支。它还设置了 FLAGS,因此可能带有循环旋转和剥离 first/later 迭代


BMI2 PEXT 部分是一些杂乱的想法,而不是一个连贯的完全优化的实现。根据您可以做出的任何保证,根据需要进行调整。例如每个数字 8 个字节的上限会有所帮助。

需要关注的一个主要问题是涉及指针增量的循环传送的 dep 链的延迟。如果找到下一个数字的开始的延迟很高,乱序执行将无法交错多次迭代的工作。


半相关,另一个位打包/解包问题: