确定字节数组的前 n 位是否为“0”的快速方法

Question

我有一个函数可以按如下方式计算 checkLeadingZeroBits：


typedef std::array<uint8_t, 32> SHA256Hash;

bool checkLeadingZeroBits(SHA256Hash& hash, unsigned int challengeSize) {
    int bytes = challengeSize / 8;
    const uint8_t * a = hash.data();
    if (bytes == 0) {
        return a[0]>>(8-challengeSize) == 0;
    } else {
        for (int i = 0; i < bytes; i++) {
            if (a[i] != 0) return false;
        }
        int remainingBits = challengeSize - 8*bytes;
        if (remainingBits > 0) return a[bytes + 1]>>(8-remainingBits) == 0;
        else return true;
    }
    return false;
}

我也尝试了以下大致相同的运行时间：

    bool checkLeadingZeroBits(SHA256Hash& hash, unsigned int challengeSize) {
        int bytes = challengeSize / 8;
        const uint8_t * a = hash.data();
        if (bytes == 0) {
            return a[0]>>(8-challengeSize) == 0;
        } else {
            if (memcmp(NULL_SHA256_HASH.data(), a, bytes) != 0) return false;
            int remainingBits = challengeSize - 8*bytes;
            if (remainingBits > 0) return a[bytes + 1]>>(8-remainingBits) == 0;
            else return true;
        }
        return false;
    }

我想尽快将此功能优化到运行。有没有比使用我的实现中所示的 for 循环更简单的方法来检查前导位？

Answer 1

正如所写，没有。在位级别扫描原始字节数组的速度不能比逐字节比较操作快。

但是，如果您的目标平台具有计数前导零指令或等效指令，您可以通过检查块的大小来加快进程本机处理器字（32 位 x86/ARM、64 AMD64/AA64 位）。这会给您带来轻微的改善，但总体而言可能不足以在这种情况下发挥作用。

为此，您需要将数据转换为 C 指针，然后将其转换为与机器上的字大小相同的指针 (uintptr_t*)。从那里，您可以读出内存块，并将它们传递给计算该词前导零的编译器内部函数。

对此有一些注意事项。首先，您需要非常小心，不要让您最后一次从新指针读取的内容越界到您不拥有的内存中。此外，对于引入 lzcnt 之前的 x86 体系结构（在 AMD ABM 或 Intel Haswell 之前），您需要处理 bsr （位扫描反向，MSB 到 LSB）指令找不到位的情况，它设置零标志而不是返回真实结果（这可能对您不可见，或者由内在函数自动转换，但我知道 MSVC 的 _BitScanReverse 函数 returns true 或 false 基于有没有找到指令）。

最终，您的性能可能会略有提高，这可能会被您需要进行的内存访问所抵消，以从缓冲区中读取数据。总的来说，这并不值得——编译器在优化循环方面会比你使用世界上所有的指令做得更好。最好编写清晰且易于维护的代码，而不是脆弱、迟钝且依赖处理器特定指令的代码。

真可惜，因为我真的很喜欢 lzcnt、bsr/bsf 和 clz 指令。它们可以显着加快扫描位图的速度，但它们在这里并不是很有用。

Answer 2

有 SSE4.2 指令可用于批量比较字节并加速此算法。您可以使用一条指令一次比较 16 个字节。

https://github.com/WojciechMula/sse4-strstr/blob/master/sse4.2-strstr.cpp

Answer 3

这里的一个问题是 char 数组似乎是大端格式。在某些体系结构中，这可以通过字节交换来缓解，而在其他一些体系结构中，无论如何都可以读取 64 位，但专注于 LSB 位。

 //     MSB
 // x = 00 00 00 00 08 FE BB AB <-- as stored byte wise in memory
 // y = AB BB FE 08 00 00 00 00 <-- as read from memory in x86

 bool check(uint8_t const *x, int challenge_count) {
     uint64_t y;
     std::memcpy(&y, x, 8);
     if (y & (~0ull << (challenge_count & ~7))) {
     
     }
     ... check the remaining byte (or nibble)
 }

这里如果需要多次进行相同的比较，缓存(~0ull << (challenge_count & ~7))是有意义的。这里也省略了 challenge_count >= 64 的处理，可以通过 memcpy 然后比较零来实现。

确定字节数组的前 n 位是否为“0”的快速方法

FAST way to determine if first n bits of byte array are "0"

c++

optimization