assembly 在x86-64程序集中使用SWAR加速strlen

zzoitvuj  于 2023-06-06  发布在  其他
关注(0)|答案(1)|浏览(170)

asm函数strlen以char - Array的形式接收到字符串的链接。为此,该函数可以在通用寄存器上使用SWAR,但不使用xmm寄存器或SSE指令。
函数检查位操作:(v - 0x01010101) & ~(v & 0x80808080)以8字节为步长,如果字包含零字节,则表示字符串的结束。如果是,则逐字节迭代,直到零,以避免页面错误。
对齐的工作方式如下GNU Libc implementation

for (char_ptr = str; ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; ++char_ptr){
    if (*char_ptr == '\0'){
        return char_ptr - str;
    }
}

有什么办法可以让它更快吗?

; rdi <- const *char
; rax <- counter + return value
; r10 <- current array for computation
; rcx,r8 <- Bitmask
; rsi <- Arr for calculation 
            
strlen:
    PUSH rbp
    SUB rsp,8
 
    XOR rax,rax    
    MOV r8,31
alignment:
    CMP byte [rdi+rax],0
    JE end
    
    MOV rsi,rdi
    ADD rsi,rax
    AND rsi,r8
    CMP rsi,0
    JE while_parallel
    INC rax
    JMP alignment       
          
while_parallel:  
    MOV rcx,0x01010101
    MOV r8,0x80808080
while_parallel_loop:  
    MOV r10,[rdi+rax]
    MOV rsi,r10
    
    NOT r10
    AND r10,r8
    SUB rsi,rcx
    AND rsi,r10
    
    CMP rsi,0
    JNE while_single
    ADD rax,8
    JMP while_parallel_loop
    
while_single:
    CMP byte [rdi+rax],0
    JE  end
    INC rax
    JMP while_single    
end:
    ADD rsp,8
    POP rbp
    RET

请注意,我不打算使用任何SSE指令或xmm寄存器。

9vw9lbht

9vw9lbht1#

问题中的代码似乎有一个缺陷:Mycroft的魔法常数还没有扩展到64位。关于效率:各种x86-64调用约定主要是基于寄存器的,因此不必为简单函数维护堆栈帧。发布的代码中的主循环似乎有点过于复杂;注意,大多数x86指令设置可用于分支的标志。达到下一个QWORD边界的逐字节处理可能会受益于完全展开。
下面是为Windows编写的x86-64代码,其中包含了这些建议。将其调整到Linux使用的System V ABI只需要循环交换寄存器。请注意,在具有BMI指令集扩展的CPU上,通过将not rcx与以下and rcx, r9合并为andn rcx, rcx, r9,可以将64位处理循环减少一条指令。

PUBLIC  strglen

_TEXT   SEGMENT

        ALIGN 16

;; Alan Mycroft's null-byte detection algorithm (newsgroup comp.lang.c, 1987/04/08,
;; https://groups.google.com/forum/#!original/comp.lang.c/2HtQXvg7iKc/xOJeipH6KLMJ):
;; null_byte(x) = ((x - 0x01010101) & (~x & 0x80808080))
 
mycroft_magic1 EQU 0101010101010101h
mycroft_magic2 EQU 8080808080808080h 

;; size_t strglen (const char *src);

;; Windows x86-64 calling convention:
;; function arguments: rcx, rdx, r8, r9
;; function return value: rax
;; scratch registers: rax, rcx, rdx, r8, r9, r10, r11

strglen PROC
        mov    rax, rcx             ; src pointer
        mov    r8, rcx              ; src pointer
        mov    r9, mycroft_magic2   ; 0x8080808080808080
        mov    r10, -mycroft_magic1 ; 0x0101010101010101

        and    rcx, 7               ; is src qword aligned ?
        jz     count_bytes          ; yes, process qword wise

BYTE_OFS = 7
REPT 6  
        cmp    byte ptr [rax], 0    ; *src == 0 ?
        je     done                 ; yes
        inc    rax                  ; src++
        cmp    rcx, BYTE_OFS        ; src now qword aligned?
        je     count_bytes          ; yes, process qword-wise
BYTE_OFS = BYTE_OFS-1
ENDM
        cmp    byte ptr [rax], 0    ; *src == 0 ?
        je     done                 ; yes
        inc    rax                  ; src++

        ALIGN 16

count_bytes:
        mov    rcx, [rax]           ; load aligned qword
        add    rax, 8               ; src += 8
        lea    rdx, [rcx + r10]     ; qword - 0x0101010101010101
        not    rcx                  ; ~qword
        and    rcx, r9              ; ~qword & 0x8080808080808080
        and    rcx, rdx             ; (qword - 0x0101010101010101) & (~qword & 0x8080808080808080)
        jz     count_bytes          ; if zero, no null byte found -- continue

has_zero_byte:
        bsf     rcx, rcx            ; find first set bit (null byte)
        shr     rcx, 3              ; convert bit position to byte position
        lea     rax, [rax + rcx - 8]; reverse pre-increment to compute byte count
done:
        sub     rax, r8             ; src - original src = length
        ret

strglen ENDP

        ALIGN 16

_TEXT   ENDS

        END

我使用下面的ISO-C99测试脚手架来检查上面的strglen实现的正确性。我使用Microsoft Macro Assembler和Intel C/C++编译器构建,如下所示:ml64 -c strglen.asmicl /Qstd=c99 /Ox /W4 strlen.c strglen.obj。我还用dumpbin /disasm strglen.obj检查了生成的机器代码,主要是为了确保对齐指令按预期工作,以及通过REPT宏展开的循环正确工作,因为我在过去的20年里没有使用过它。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

extern size_t strglen (const char* str);

int main (void)
{
    const char a[] = "0123456789 the quick brown fox jumps over the lazy dog";
    char* src =  malloc (sizeof(a));
    size_t ref, res;

    printf ("src=%p\n", a);

    for (int srcofs = 0; srcofs < 8; srcofs++) {
        for (size_t len = 0; len < sizeof(a); len++) {
            memcpy (src, a, sizeof(a));
            src [len] = 0;
            ref = strlen (src + srcofs);
            res = strglen (src + srcofs);
            if (res != ref) {
                printf ("error @ srcofs=%d  len=%zu  ref=%zu  res=%zu\n", 
                        srcofs, len, ref, res);
                return EXIT_FAILURE;
            }
        }
    }
    printf ("Test passed\n");
    return EXIT_SUCCESS;
}

相关问题