使用 x86 或 x86_64 程序集反转字符串的最简洁方法是什么？

Question

我希望用尽可能少的汇编代码来反转字符串。

由于缺少 Unicorn 支持，我只能使用 SSSE3 或更少的扩展。我试过访问 ymm 和 zmm 指令，但每次都会中断。

即使 SSSE3 指令更简洁，但用于对 128 位 XMM 寄存器进行字节反转的 16 字节 pshufb 控制向量仍然占用 16 字节，甚至更长。我愿意接受任何想法，但以下是我最好的尝试。

我需要 32 字节或更少，越小越好。 到目前为止我得到的最好的是 42，但那是我假设里面字符串的大小rdx（或 ecx，如果使用 x86）是 30。

理想情况下，它可以通过检查空终止符来动态获取大小。

字符串地址位于 rdx 中（如果使用 x86，则为 ecx）。

附加限制：不使用堆栈 space。此代码块必须运行没有指向可用堆栈内存的 RSP。

标准 x86 / 64 - 42 字节

; get values in registers
mov rax, [rdx]            
mov rbx, [rdx + 8]
mov rcx, [rdx + 16]
mov r8, [rdx + 24]

; swap bytes around
bswap rax
bswap rbx
bswap rcx
bswap r8

; shift it right by 2 because of the nulls
sar r8, 16

; put it back
mov [rdx], r8
mov [rdx + 0x6], rcx
mov [rdx + 0xE], rbx
mov [rdx + 0x16], rax

SSE3 - 62字节（因为是字节数组，否则是46）

movdqu xmm3, [rip + 0x27]
movdqu xmm0, [rdx]
movdqu xmm1, [rdx] + 0x10
pshufb xmm0,xmm3
pshufb xmm1,xmm3


movdqu [rdx], xmm1
movdqu xmm1, [rdx+0x2]
movdqu [rdx], xmm1
movdqu [rdx+0xE], xmm0
hlt

; this would be tacked on to the end of the assembly as the rip + 0x27 value 
\x00\x0F\x0E\x0D\x0C\x0B\x0A\x09\x08\x07\x06\x05\x04\x03\x02\x01

Answer 1

反转字符串最简洁的方法是将"string"定义为1字节"direction and length"字节后跟最多127字节的字符。这允许您使用单个 neg byte [rdx] 指令反转字符串（仅花费 2 个字节！）。

示例（NASM）：

myString:
    db myString.end - myString.start
.start:
    db "Hello World!"
.end:

;Reverse a string
;
;Input
; rdx   Address of string to reverse

reverseString:
    neg byte [rdx]
    ret

当然，您必须编写其他例程来处理这种字符串格式。例如：

;Print a string
;
;Input
; rsi   Address of string to print

printString:
    movsz rcx,byte [rsi]    ;rcx = "direction and length" value
    inc rsi
    cmp rcx,0
    jg .l1
    je .done
    std
    neg rcx
.l1:
    lodsb
    call printChar          ;Print the character in AL
    loop .l1
    cld
.done:
    ret

;Get length of a string (in bytes)
;
;Input
; rsi   Address of string
;
;Output
; rcx   Length of string

getStringLength:
    movsz rcx,byte [rsi]    ;rcx = "direction and length" value
    cmp rcx,0
    jge .l1
    neg rcx
.l1:
    ret

Answer 2

void strrev(char* p) 的以下 31 字节 x86-64 汇编代码将就地反转任意长度的字符串（包括空字符串），只使用基本指令集。

但是，该例程需要指向寄存器 rdi 中的字符串的指针（与 System V ABI 一致），而不是 rdx。 mov rdi, rdx 将花费 3 个字节。此外，由于使用了两个隐式锁定 xchg，性能会很糟糕。

小尺寸部分是由于创造性地使用单字节 stosb/lodsb 指令的读取副作用和 incrementing/decrementing rdi 和rsi分别取决于方向标志，可以通过单字节指令设置和清除std/cld.

如果代码是 x86-32 或可以将其自身限制为小于 4GB 的字符串，则可以节省几个字节。

0000000000000000 <strrev>:
   0:   31 c0                   xor    eax,eax
   2:   48 8d 48 ff             lea    rcx,[rax-0x1]
   6:   48 89 fe                mov    rsi,rdi
   9:   f2 ae                   repnz scas al,BYTE PTR es:[rdi]
   b:   48 83 ef 02             sub    rdi,0x2
   f:   48 39 f7                cmp    rdi,rsi
  12:   7e 0a                   jle    1e <strrev+0x1e>
  14:   86 07                   xchg   BYTE PTR [rdi],al
  16:   86 06                   xchg   BYTE PTR [rsi],al
  18:   fd                      std
  19:   aa                      stos   BYTE PTR es:[rdi],al
  1a:   fc                      cld
  1b:   ac                      lods   al,BYTE PTR ds:[rsi]
  1c:   eb f1                   jmp    f <strrev+0xf>
  1e:   c3                      ret

使用 x86 或 x86_64 程序集反转字符串的最简洁方法是什么？

What's the most concise way to reverse a string using x86 or x86_64 assembly?

assembly

x86-64

micro-optimization

code-size