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

Question

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

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

尽管 SSSE3 指令更加简洁，但用于对 128 位 XMM 寄存器进行字节反转的 16 字节pshufb控制向量仍然占用 16 个字节，并使其更长。我对任何想法都持开放态度，但以下是我最好的尝试。

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

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

字符串地址位于 rdx 内部(如果使用 x86，则为 ecx(。

附加限制：不使用堆栈空间。 此代码块必须在没有指向可用堆栈内存的 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 
x00x0Fx0Ex0Dx0Cx0Bx0Ax09x08x07x06x05x04x03x02x01

Answer 1

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

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

小尺寸部分是由于创造性地使用单字节stosb/lodsb指令的副作用，分别根据方向标志读取和递增/递减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

Answer 2

反转字符串的最简洁方法是将"字符串"定义为 1 字节的"方向和长度"字节，后跟最多 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