检查按位操作中的借用

2020-05-04 07:28:40

在他关于使用AVX2进行排序的系列文章的第四部分中,@Damageboy有一个简短的说明,即在小于和大于或等于透视的元素已经处于正确顺序的情况下,如何检测分区(透视)模式:在这种情况下,分区例程不需要排列值块。实际细节与本文无关;重要的是,我们希望快速确定字节值是否与以下9种情况中的任何一种匹配:

看一下位模式,1操作员使用popcount和bitscan的解决方案是非常自然的。这些指令有些复杂(延迟更接近3个周期,而不是1个周期,而且通常端口受限),似乎是那种在SSE4最终为x86添加了人口计数指令之前就有了有效解决方案的问题。

在排序库的分区循环上下文中,popcnt和bsf可能已经足够好了:POST显示真正的问题是分支错误预测比无条件置换慢。

就popcountor位扫描而言,检测机器整数是否为2(或0)的幂是另一项具有简单解决方案的任务。对于这个问题,还有一个更简单的经典解决方案:

这个表达是怎么用的?假设x是2的幂。它的二进制表示是0b0.010.0:任意数量的前导零、2单个“1”位和尾随零(可能没有)。让我们看看当我们从x中减去1时会发生什么:

减法引发了整个尾随零的借用链,直到我们最终达到1位。在十进制数中,从10.0减去1得到09.9;而在二进制中,我们得到01.1。如果你研究过进位链的电路深度(延迟)(对我来说,那是为了电路复杂性理论),你就知道这很难做到。对我们来说,幸运的是,芯片制造商努力做到了这一点,我们可以把进位作为数据控制的原语,有效地翻转范围。(对我们来说,这是很难做到的)。对我们来说,幸运的是,芯片制造商努力做到了这一点,我们可以把进位作为数据控制的原语,有效地翻转范围。

当x是2的幂时,x和x-1没有共同的“1”位,因此按位取数并产生零。当x为0时也是如此,因为任何与0的AND都会得到0。让我们看看非零、非二次幂的值x=0bxx..xx10..0会发生什么,也就是说,其中x由任意非零位序列xx..xx后跟最小设置的位(至少有一个,因为x既不是0也不是2的幂)和尾随的零组成:

前导的非全零0bxx.xx不受减法的影响,因此它通过逐位且毫发无损(将任何位与自身进行AND运算产生相同的位),并且我们知道其中至少有一个非零位;我们的测试正确地拒绝了它!

当解码ULEB格式的可变长度整数时,例如对于协议缓冲器,很快就会清楚的是,为了避免一次一个字节的逻辑,我们必须快速分割(LEX或标记化,在某种程度上)我们的字节流,以确定每个ULEBend在哪里结束。让我们关注快速路径,当编码的ULEB适合机器寄存器时。

我们有uleb=0bnnnnnnnnmmmmmm.0zzzzzzz1yyyyyyy1.:一个字节序列3,最高位等于1,以最高位设置为0的字节结束,最后是任意麻烦字节(m.m,n.n等)。我们希望忽略。理想情况下,我们将提取数据=0b0000000000000000.?zzzzz?yyyyyy?.。from uleb:我们希望清除uisance字节,并且可以接受ULEB控制位中的任意值。

查找设置为1的位要比找到设置为0的位容易得多,因此首先要做的是对ULEB数据进行补码,并清除除潜在的ULEB控制位(每个字节的高位)之外的所有位,c=~uleb&;(128*(word_max/255)),即,使用每个字节中高位的位掩码计算~uleb的逐位与。

uleb=0bnnnnnnnmmmmmm.0zzzzz1yyyyyy1.。~ULEB=0b̅n̅m̅.1z̅z̅z0y̅y̅y0.。C=0b̅n̅0000000̅m̅0000000.10000000000000000.。

我们现在可以通过位扫描找到第一个1的索引(标记最后一个ULEB字节),然后生成掩码。然而,使用扫描生成索引,而只使用移位将其转换回位图空间似乎是浪费的。我们可能仍然希望该索引知道解码器的光标前进了多远,但我们有望在解码当前ULEB值的同时更新游标。

当我们试图检测2的幂时,我们从x中减去1,类似于c的值,以生成一个新值,该值在x的第一组(等于1)位之前的所有位上都与x不同,而在其余位上相同。然后,我们利用与自身进行AND运算产生相同比特的事实来检测余数中是否有任何非零比特。

这里,我们希望对剩余的未接触位做一些其他的事情,我们希望将它们全部设置为零。另一个按位运算符执行我们想要的操作:将位与自身进行异或始终产生零,而