assembly - 在汇编器中导出优化的 strlen？

Question

以下代码能够确定 DWORD 的一个或多个字节是否设置为 0。

mov eax, value
mov edx, 07EFEFEFFh
add edx, eax
xor eax, 0FFFFFFFFh
xor eax, edx
and eax, 081010100h

例如，如果我们输入34323331h，eax = 0然而，如果我们输入 1 个字节设置为 00 的内容，例如 34003231h，eax != 0

我知道这段代码的作用，但我不明白它是如何做到的。这在数学上是如何运作的？有人可以向我解释一下这个过程以及它是如何得出的吗？

应该比较简单，但是我就是看不出来

Answer 1

我将从右开始计算位。

简短回答:

当您将 11111111 添加到零字节 (00000000) 时，溢出位(第 8 位)不会与 不同值 + 0x7EFEFEFF 的相同溢出位。

当您将 11111111 添加到非零字节时，溢出位(第 8 位)与 值 + 0x7EFEFEFF 的不同相同的溢出位。

程序只是检查这些位。

长答案:

这是代码的数学表示(a 是值):

result = ((a + magic) ^ !a) & !magic

哪里

• 魔法是0x7EFEFEFF
• ^ 表示按位异或
• & 表示按位与
• ! 表示按位反转，也称为与 0xFFFFFFFF 进行异或

要了解 0x7EFEFEFF 的作用，请查看它的二进制表示形式:

01111110 11111110 11111110 11111111

0 是神奇的溢出位。这些是位号 8、16、24 和 31。

让我们看几个例子。

示例 1:eax = 0x00000000

a         = 00000000 00000000 00000000 00000000
a+magic   = 01111110 11111110 11111110 11111111
!a        = 11111111 11111111 11111111 11111111

当我们将 a+magic 与 !a 进行异或时，我们得到:

result    = 10000001 00000001 00000001 00000000

这里看看神奇的部分。它们都是1。

然后，我们只需通过 10000001 00000001 00000001 00000000 计算结果来清除其余位(此处均为 0)又名!magic。如您所知，and除以 0 只是将 0 分配给该位，and除以 1 对该位没有任何作用。

最终结果:

10000001 00000001 00000001 00000000

示例 2:eax = 0x00000001

a         = 00000000 00000000 00000000 00000001
a+magic   = 01111110 11111110 11111111 00000000
!a        = 11111111 11111111 11111111 11111110

当我们将 a+magic 与 !a 进行异或时，我们得到:

result    = 10000001 00000001 00000000 11111110

看看神奇的部分。位号 16、24 和 31 为 1。第 8 位为 0。

• 第 8 位表示第一个字节。如果第一个字节不为零，则此时第 8 位变为1。否则为0。
• 第16位代表第二个字节。同样的逻辑。
• 第 24 位代表第三个字节。
• 第 31 位表示第四个字节。

然后，我们再次通过并使用!magic计算结果来清除非魔术位。

最终结果:

10000001 00000001 00000000 00000000

示例 3:eax = 0x34003231

a         = 00110100 00000000 00110010 00110001
a+magic   = 10110010 11111111 00110001 00110000
!a        = 11001011 11111111 11001101 11001110

当我们将 a+magic 与 !a 进行异或时，我们得到:

result    = 01111001 00000000 11111100 11111110

只有第24位是1

清除非魔法位后，最终结果是:

00000001 00000000 00000000 00000000

示例 4:eax = 0x34323331

a         = 00110100 00110010 00110011 00110001
a+magic   = 10110011 00110001 00110010 00110000
!a        = 11001011 11001101 11001100 11001110

当我们将 a+magic 与 !a 进行异或时，我们得到:

result    = 01111000 11111100 11111110 11111110

清除非魔法位后，最终结果是:

00000000 00000000 00000000 00000000 (zero)

<小时/>

我写了一个测试用例来演示:

#include <stdint.h> // uint32_t
#include <stdio.h> // printf

//assumes little endian
void printBits(size_t const size, void const * const ptr)
{
    unsigned char *b = (unsigned char*) ptr;
    unsigned char byte;
    int i, j;

    for (i = size - 1; i >= 0; i--) {
        for (j = 7; j >= 0; j--) {
            byte = b[i] & (1 << j);
            byte >>= j;
            printf("%u", byte);
        }

        printf(" ");
    }
}

int main()
{
    uint32_t a = 0;
    uint32_t d = 0;
    const uint32_t magic = 0x7EFEFEFF;
    const uint32_t magicRev = magic ^ 0xFFFFFFFF;

    const uint32_t numbers[] = {
        0x00000000, 0x00000001, 0x34003231,
        0x34323331, 0x01010101
    };


    for (int i = 0; i != sizeof(numbers) / sizeof(numbers[ 0 ]); i++) {
        a = numbers[ i ];
        d = magic;

        printf("a:            ");
        printBits(sizeof(a), &a);
        printf("\n");

        d = a + d;

        printf("a+magic:      ");
        printBits(sizeof(d), &d);
        printf("\n");

        a = a ^ 0xFFFFFFFF;

        printf("!a:           ");
        printBits(sizeof(a), &a);
        printf("\n");

        a = a ^ d;

        printf("result:       ");
        printBits(sizeof(a), &a);
        printf("\n");

        a = a & magicRev;

        printf("              ");
        printBits(sizeof(a), &a);

        if (a == 0) {
            printf(" (zero)\n");
        } else {
            printf(" (at least one)\n");
        }

        printf("\n");
    }

    return 0;
}