在汇编程序中派生优化的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

我将从0开始计算从右边开始的位数.

简短回答:

当您添加11111111到零字节(00000000)时,溢出位(第8位)与相同的溢出位没有区别value + 0x7EFEFEFF.

当您添加11111111到非零字节时,溢出位(第8位)确实与value + 0x7EFEFEFF相同的溢出位不同.

程序只检查这些位.

答案很长:

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

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

哪里

• magic 是 0x7EFEFEFF
• ^ 意味着按位xor
• & 按位和
• ! 意味着按位反转,也就是xor'd 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.

然后我们通过aka 的结果简单地清除其余的位(这些都0在这里).如你所知,从0开始只是将0分配给该位,而1加1对该位没有任何作用.and10000001 00000001 00000001 00000000!magicandand

最后结果:

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位代表第四个字节.

然后我们再次通过and结果清除非魔术位!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;
}