4

就像strlen()glibc 执行一个很好的位操作和每次检查 4 个字节使函数如此之快，与大多数其他人所做的逐字节例程相比，是否有这样的东西来比较汇编中的两个字符串？我正在阅读一些关于 C 语言代码实现的页面，对字符串处理部分非常感兴趣，但我仍然没有找到这样的内容。我必须使这个函数尽可能快，因为它是我的应用程序的核心。（不推荐哈希表）

欢迎任何汇编程序。但是我对intel的汇编语法有点熟悉，如果你要提供的汇编不同，请评论。

4

4 回答 4

6

您可以逐字比较（例如一次 32 位或 64 位）。您只需要小心不要超过字符串的末尾。如果您正在制作字符串，那么您可以用零填充它们，以便它们是字长的倍数，那么您甚至不需要检查。

于 2013-02-07T05:11:47.847 回答
4

假设以零结尾的字符串（尽管同样适用于memcmp()）；在汇编中进行字符串比较的最快方法取决于字符串的长度和特定的 CPU。

一般来说; SSE 或 AVX 的设置成本很高，但在运行后会提供更快的吞吐量，如果您要比较非常长的字符串（尤其是在大多数字符匹配时），这将使其成为最佳选择。

或者，使用通用寄存器一次处理一个字节的东西通常具有非常低的设置成本和较低的吞吐量，如果您要比较大量小字符串（甚至是大量大字符串，其中前几个字符可能不同）。

如果您为特定应用程序执行此操作，则可以确定比较的平均字符数并找到该平均值的最佳方法。您还可以针对不同的情况使用不同的功能 - 例如，如果存在混合，则实现 astrcmp_small()和 a 。strcmp_large()

尽管如此，如果字符串比较的性能很重要，那么比较字符串的最快方法很可能根本不比较字符串。基本上，“我必须尽可能快地实现这个功能，因为它是我的应用程序的核心”这句话应该让每个人都想知道为什么没有更好的方法来实现应用程序。

于 2013-02-07T14:15:15.263 回答
3

FreshLib /strlib.asm 库中实现的 StrCompCase（区分大小写） 。

这是一些使用双字比较的代码：

请注意，这是首先检查字符串的长度。那是因为在提到的库中，字符串是以长度为前缀的，所以 StrLen 是即时的 O(1) 并且仅提供扫描终止 NULL 作为后备（请参阅此答案的第二部分）。

在实际比较之前比较长度可以使不同字符串的速度为 O(1)，这在搜索大数组的情况下可能会显着提高性能。

然后在 dwords 上进行比较，最后，如果字符串长度不是 4 的倍数，则将剩余的 1..3 个字节逐个字节地进行比较。

proc StrCompCase, .str1, .str2
begin
        push    eax ecx esi edi

        mov     eax, [.str1]
        mov     ecx, [.str2]

        cmp     eax, ecx
        je      .equal

        test    eax, eax
        jz      .noteq

        test    ecx, ecx
        jz      .noteq

        stdcall StrLen, eax
        push    eax
        stdcall StrLen, ecx

        pop     ecx
        cmp     eax, ecx
        jne     .noteq

        stdcall StrPtr, [.str1]
        mov     esi,eax
        stdcall StrPtr, [.str2]
        mov     edi,eax

        mov     eax, ecx
        shr     ecx, 2
        repe cmpsd
        jne     .noteq
        mov     ecx, eax
        and     ecx, 3
        repe cmpsb
        jne     .noteq

.equal:
        stc
        pop     edi esi ecx eax
        return

.noteq:
        clc
        pop     edi esi ecx eax
        return
endp

关于 StrLen 代码：

这是StrLen的实现。

您可以看到，如果可能，它使用长度前缀字符串，这样执行时间为 O(1)。如果这是不可能的，它会退回到每个周期检查 8 个字节的扫描算法，它非常快，但仍然是 O(n)。

proc StrLen, .hString    ; proc StrLen [hString]
begin
        mov     eax, [.hString]
        cmp     eax, $c0000000
        jb      .pointer

        stdcall StrPtr, eax
        jc      .error

        mov     eax, [eax+string.len]
        clc
        return

.error:
        xor     eax, eax
        stc
        return

.pointer:
        push    ecx edx esi edi

; align on dword
.byte1:
        test    eax, 3
        jz      .scan

        cmp     byte [eax], 0
        je      .found

        inc     eax
        jmp     .byte1

.scan:
        mov     ecx, [eax]
        mov     edx, [eax+4]

        lea     eax, [eax+8]

        lea     esi, [ecx-$01010101]
        lea     edi, [edx-$01010101]

        not     ecx
        not     edx

        and     esi, ecx
        and     edi, edx

        and     esi, $80808080
        and     edi, $80808080

        or      esi, edi
        jz      .scan

        sub     eax, 9

; byte 0 was found: so search by bytes.
.byteloop:
        lea     eax, [eax+1]
        cmp     byte [eax], 0
        jne     .byteloop

.found:
        sub     eax, [.hString]
        clc
        pop     edi esi edx ecx
        return
endp

请注意，以零结尾的字符串同时存在性能和安全问题。

最好使用大小前缀字符串。例如，提到的库使用动态字符串，其中字符串包含偏移量 -4 的 dword 字段（上面代码中的 string.len ），其中包含字符串的当前长度。

于 2013-02-07T08:34:07.983 回答
3

更快的逐字节比较的第一条规则是对字符串或.align 16任何常量字符串进行 malloc 以确保

  • 针对安全违规的鲁棒性（读取过去分配的区域）
  • xxm（或 64 位）处理的最佳对齐方式
于 2013-02-07T11:13:07.107 回答