assembly - 测试所有真实位是否相邻

Question

我正在遍历树来构建霍夫曼前缀代码LUT。我正在使用寄存器来跟踪当前前缀。

我退出分析树的算法的条件使用以下条件，必须为true：


树中的当前元素必须是叶子
当前的前缀代码将所有位设置为无假位。


对于第二个条件，我还跟踪前缀字符串的当前长度（以位为单位）。

如何测试寄存器的位设置是否超过1位，并且所有设置位彼此相邻？

编辑：设置位组必须从位0开始并且与前缀长度一样长（存储在另一个寄存器中）

Answer 1

构造单元将是：在连续组的低位加1将清除所有这些位并带进位，而在该组上方保留1位。例如0xff +1 = 0x100。

如果未设置任何位，则进位将不会一直传播，例如0b01101 + 1 = 0b01110，未设置位＃4。 （并且不保留某些现有设置位的翻转，因此x & (x+1)为true。）

这适用于寄存器底部（加1）或更高位置的位组（用(-x) & x隔离最低的设置位并添加它，例如用BMI1 blsi或mov / neg / and）。

一个相关的bithack是y & (y-1)测试，该整数仅设置一个位（通过清除最低的设置位）来设置整数：https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2。但是，由于我们使用y生成x+1，因此我们可以将其优化到x & (x+1)以检测寄存器底部的连续掩码。



您的情况很简单：


位范围的底部必须为位0
位范围恰好是n位宽（前缀长度）


这些限制意味着恰好有1个整数可以同时满足这两个要求，因此您应该对其进行预先计算，并简单地与cmp/je比较是否相等。底部设置n位的数字为prefix_mask = (1<<n) - 1。减法的进位（借位）将所有位设置为低于该隔离的高位，并清除原始位。高于该位的位保持不变，因为该高位满足了借入要求。

给定前缀长度n，您可以使用1<<n（在Intel CPU上为单-uop，在AMD为https://agner.org/optimize/上为2 oups）来计算bts。

;; input: prefix length in EDX
;; output: prefix mask in ESI
xor    esi, esi
bts    esi, edx         ; set bit n;  eax |= 1<<n
dec    esi              ; set all the bits BELOW that power of 2

 ; then later, inside a loop: input in EAX
  cmp   eax, esi
  je    all_bits_set_up_to_prefix

@fuz为此提出了一个LUT，但这听起来是个坏主意，即使您不得不非常频繁地考虑不同的前缀长度。如果缺少寄存器，则可以在计算后将其溢出到堆栈内存中，并使用 cmp [rsp+16], edx代替静态LUT，同时使用相同的前缀长度循环。

或者，如果您暂时不需要在寄存器中使用前缀长度，则可以将前缀长度溢出到内存中，而只需保留掩码即可。

您甚至可以使用 lea edx, [eax+1] / bsr edx,edx将掩码转换回前缀长度，以找到 mask+1的最高设置位的位索引。 （或者，如果前缀长度可以为32，但不能为零，则 bsr / inc。输入值为0的 BSR保留目标不变，并设置ZF。AMD对此进行了说明，Intel的文档说“ undefined”，但其当前HW确实使目标保持不变，这就是指令对输出具有“ false”依赖性的原因。）



或不进行预先计算

低位 n位全为1，而EDN的无损检测，位#n本身为0。（如果是这种情况，则加1清除低位并设置位 n）。如果以后没有用处，可以使用 inc edx代替LEA进行复制和添加。

;;; check the low n bits, ignoring whether higher bits are set or not
;;; inputs: prefix length in ECX, candidate in EDX
    lea  eax, [rdx+1]             
    bt   eax, ecx
;;; output: CF = 1 if all the bits from 0..len-1 were set, else 0

如果您还想排除设置更高的位，则需要再执行一条指令，但是它可以是一条 test指令，它将与 jcc宏融合，因此在Intel CPU上，这不会花费任何额外的指令。 。在 btr为2 oups而 bt为1的AMD CPU上，这会额外增加1 uop。 （test / jcc可以在AMD Bulldozer系列及更高版本上融合。）

;;; input: prefix length in ECX, candidate in EDX
   lea     eax, [rdx+1]      ; produces a single set bit?
   btr     eax, ecx          ; reset that bit, leaving eax=0 if no other bits were set
   test    eax, eax          ; compare against zero
;;; output: ZF=1 (and eax=0) if EDX == (1<<ECX)-1 with no higher bits set.

   jz     contiguous_bitmask_of_length_ecx

在这种情况下，包括宏融合测试/ jz在内，这在英特尔（AMD为4）上总共要花费3 uops。而且它不会破坏输入寄存器。



我们可以使用 x & (x+1)在寄存器的底部检查未知长度的单个连续位组，该组确实会检测是否设置了更高的位。如果有一个高位未被进位传播所翻转，则AND或TEST将产生非零结果。

但这将 0和 1与像 0b0111这样的多位组相同。在此测试之前，您可能需要 cmp eax, 3 / jb not_multibit_prefix。

; check for a contiguous bit-group at the bottom of a reg of arbitrary length, including 0
;;; input: candidate in EDX
   lea   eax, [rdx+1]              ; carry-out clears all the set bits at the bottom
   test  eax, edx                  ; set flags from x & (x+1)
;;; output: ZF=1 if the only set bits in EDX were a contiguous group at the bottom

我看着 lea eax, [rdx+1] / test eax, edx（ZF = 1：仅设置了连续的低位）/ bt eax, ecx（CF = 1：它结束于我们想要的位置）的怪异部分标志。但是x86没有需要CF = 1和ZF = 1的 jcc condition。如果使用 ja，则使用 (CF=0 and ZF=0)；如果使用 jbe，则使用 (CF=1 or ZF=1)，因此两者均无效。当然，如果没有有效的部分标志合并，这在CPU上将是可怕的，从而导致部分标志停顿。



一般情况：位组不必从底部开始。

这排除了简单的预计算。

如上所述，我们可以使用 (-x) & x隔离最低的设置位。 BMI1为此添加了一条指令 blsi。因此，如果可以假设支持BMI1，则可以1 uop进行无损检测。否则需要3。

unsigned bits_contiguous(unsigned x) {
    unsigned lowest_set = (-x) & x;  // isolate lowest set bit
    unsigned add = x + lowest_set;   // carry flips all the contiguous set bits
    return (add & x) == 0;           // did add+carry leave any bits un-flipped?
}

我将其放在Godbolt编译器资源管理器上，以查看gcc或clang是否发现了我没有想到的任何优化。当然，您实际上并不想像我们要求编译器那样具体化一个0/1整数，但是由于他们选择使用 test / setcc，所以我们可以看看他们为创建正确的整数所做的工作标志条件。

我们可以编写一些测试函数，以确保使用 #define TEST(n) int test##n(){return bits_contiguous(n);}的某些编译时常量的逻辑正确（并查看asm是 xor eax,eax还是 mov eax,1）。请参见 C + asm on the Godbolt compiler explorer。一些有趣的情况是 TEST(0) = 1，因为该条件基本上检查是否存在多个位组。 （因此，对于此检查，零位组与1位组相同。） TEST(0xFFFFFFFF) = 1：具有 x+1 = 0也不是问题。

使用gcc8.3 -O3，我们得到

# gcc8.3 -O3 -march=haswell  (enables BMI1 and BMI2)
bits_contiguous:
    blsi    eax, edi
    add     eax, edi
    test    eax, edi         # x & (x+lowest_set)

    sete    al
    movzx   eax, al
    ret

没有BMI1，对于 blsi，我们需要3条指令，而不是1条指令：

    mov     eax, edi
    neg     eax
    and     eax, edi         # eax = isolate_lowest(x)
    add     eax, edi
    test    eax, edi

为了也检查位组的特定长度，@ fuz有一个好主意： popcnt以确保设置了正确的位数（并分别检查它们是否连续）。 Popcnt不是基线，Nehalem之前的CPU没有它，并且如果尝试运行它会出错。

;input: prefix len in ECX, candidate in EDX
;clobbers: EAX
    popcnt  eax, edx
    cmp     eax, ecx
    jne     wrong_number_of_bits_set  ; skip the contiguousness test

    blsi    eax, edi
    add     eax, edi
    test    eax, edi         # x & (x+lowest_set)
    jz     contiguous_bitgroup_of_length_ecx

wrong_number_of_bits_set: