得出优化strlen的汇编？ [英] Deriving optimized strlen in assembler?

问题描述

以下code是能够计算出，如果一个DWORD有一个或多个字节设置为0。

The following code is able to figure out if a DWORD has one or more of its bytes set to 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

For example, if we input 34323331h, eax = 0 Yet if we input something where 1 byte is set to 00, such as 34003231h, eax != 0

我知道这code做什么，但我不知道它是怎么做的。请问这个数学工作的？有人能位的过程中给我解释一下，这是怎么出来的？

I know what this code does, but I don't understand how it does it. How does this mathematically work? Can someone explain the process with bits to me and how this was derived?

这应该是比较简单的，但我就是不能看到它

It should be relatively simple, but I just can't see it

推荐答案

我数位从0开始的权利。

I'll count bits starting from 0 from right.

当您添加 11111111 零字节（ 00000000 ），那么溢出位（第8位）<强>不从值+ 0x7EFEFEFF 的相同的溢出位不同。

When you add 11111111 to zero byte (00000000), then the overflow bit (8th bit) does not differ from value + 0x7EFEFEFF's same overflow bit.

当您添加 11111111 非零字节，那么溢出位（第8位）的确实从不同值+ 0x7EFEFEFF 的相同的溢出位。

When you add 11111111 to non-zero byte, then the overflow bit (8th bit) does differ from value + 0x7EFEFEFF's same overflow bit.

该程序只检查那些位。

这是code的数学重新presentation（ A 是值）：

This is the mathematical representation of the code (a is the value):

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

其中，

• 魔术是 0x7EFEFEFF


• ^ 表示按位异或


• ＆安培; 表示按位和


• ！表示按位逆转，又名异或 0xFFFFFFFF的

• magic is 0x7EFEFEFF
• ^ means bitwise xor
• & means bitwise and
• ! means bitwise reversed, aka xor'd with 0xFFFFFFFF

要了解 0x7EFEFEFF 的角色，看它的二进制重新presenatation：

To understand the role of 0x7EFEFEFF, look at it's binary represenatation:

01111110 11111110 11111110 11111111

的 0 的亦幻溢出位。这些是位号码8，16，24和31。

The 0's are magic overflow bits. These are bits number 8, 16, 24 and 31.

让我们看几个例子。

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

当我们异或 A +魔法与 A 我们得到：！

When we xor a+magic with !a we get:

result    = 10000001 00000001 00000001 00000000

下面来看看魔术位。他们都是 1 。

Here look at the magic bits. They are all 1.

然后我们只需清除位的其余部分（这些都是 0 这里）由和 ING结果通过 10000001 00000001 00000001 00000000 又名！魔术。如你所知，和 ING由0只需1分配0到该位和和 ING无助于该位

Then we simply clear the rest of the bits (which are all 0 here) by anding the result by 10000001 00000001 00000001 00000000 aka !magic. As you know, anding by 0 simply assigns 0 to that bit and anding by 1 does nothing to that bit.

最终结果：

10000001 00000001 00000001 00000000

例2： EAX = 00000001

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

当我们异或 A +魔法与 A 我们得到：！

When we xor a+magic with !a we get:

result    = 10000001 00000001 00000000 11111110

看魔术位。位16号，24和31 1.第8位为0。

Look at the magic bits. Bits number 16, 24 and 31 are 1. 8th bit is 0.

• 重新$ P $ 8位psents的第一个字节。如果第一个字节不为零，8位变为 1 在这一点上。否则，它 0 。


• 第16位重新presents第二个字节。相同的逻辑。


• 重新$ P $第24位psents第三个字节。


• 重新$ P $ 31日位psents第四个字节。

• 8th bit represents the first byte. If the first byte is not zero, 8th bit becomes 1 at this point. Otherwise it's 0.
• 16th bit represents the second byte. Same logic.
• 24th bit represents the third byte.
• 31th bit represents the fourth byte.

然后我们再次明确非魔法位由和 ING与！神奇的结果。

Then again we clear non-magic bits by anding the result with !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 +魔法与 A 我们得到：！

When we xor a+magic with !a we get:

result    = 01111001 00000000 11111100 11111110

24日只有位为 1

在清理非魔法位最后的结果是：

After clearing non-magic bits the final result is:

00000001 00000000 00000000 00000000

例4： EAX = 0x34323331

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

当我们异或 A +魔法与 A 我们得到：！

When we xor a+magic with !a we get:

result    = 01111000 11111100 11111110 11111110

在清理非魔法位最后的结果是：

After clearing non-magic bits the final result is:

00000000 00000000 00000000 00000000 (zero)

---

我写了一个测试案例示范：

---

I wrote a test case for demonstration:

#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;
}

这篇关于得出优化strlen的汇编？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！