Quel est le moyen le plus concis de renverser une chaîne en utilisant l'assembly x86 ou x86_64?

Question

Je cherche à inverser une chaîne de caractères en utilisant le moins de code assembleur possible.

Je ne peux utiliser que des extensions SSSE3 ou moins en raison du manque de support d' Unicorn. J'ai essayé d'accéder aux instructions ymm & zmm mais ça plante à chaque fois.

Même si les instructions SSSE3 sont plus concises, le vecteur de contrôle de 16 octets pshufb pour inverser les octets d'un registre XMM de 128 bits prend toujours 16 octets et rend le code encore plus long. Je suis ouvert à toutes les idées mais voici mes meilleures tentatives.

J'ai besoin de 32 octets ou moins et moins c'est mieux. Le meilleur que j'ai obtenu jusqu'à présent est 42 mais c'est en supposant que la taille de la chaîne dans rdx (ou ecx si on utilise x86) est de 30.

Idéalement, il devrait pouvoir obtenir dynamiquement la taille en vérifiant un caractère nul.

L'adresse de la chaîne est située dans rdx (ou ecx si on utilise x86).

Restriction supplémentaire : pas d'utilisation de l'espace de la pile. Ce bloc de code doit s'exécuter sans que RSP pointe vers une mémoire de pile utilisable.

---

Standard x86 / 64 - 42 octets

; obtenir les valeurs dans les registres
mov rax, [rdx]            
mov rbx, [rdx + 8]
mov rcx, [rdx + 16]
mov r8, [rdx + 24]

; inverser les octets
bswap rax
bswap rbx
bswap rcx
bswap r8

; décaler vers la droite de 2 à cause des caractères nuls
sar r8, 16

; remettre en place
mov [rdx], r8
mov [rdx + 0x6], rcx
mov [rdx + 0xE], rbx
mov [rdx + 0x16], rax

SSE3 - 62 bytes (à cause du tableau d'octets, sinon c'est 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

; ce serait ajouté à la fin de l'assemblage en tant que valeur rip + 0x27 
\x00\x0F\x0E\x0D\x0C\x0B\x0A\x09\x08\x07\x06\x05\x04\x03\x02\x01

Answer 1

La façon la plus concise de inverser une chaîne est de définir "string" comme un "direction and length" d'un octet suivi d'au plus 127 octets de caractères. Cela vous permet d'inverser la chaîne avec une seule instruction neg byte [rdx] (qui ne coûte que 2 octets!).

Exemple (pour NASM):

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

;Inverser une chaîne
;
;Entrée
; rdx   Adresse de la chaîne à inverser

reverseString:
    neg byte [rdx]
    ret

Évidemment, vous devriez écrire d'autres routines pour gérer ce format de chaîne. Par exemple:

;Afficher une chaîne
;
;Entrée
; rsi   Adresse de la chaîne à afficher

printString:
    movsz rcx,byte [rsi]    ;rcx = valeur de "direction and length"
    inc rsi
    cmp rcx,0
    jg .l1
    je .done
    std
    neg rcx
.l1:
    lodsb
    call printChar          ;Afficher le caractère dans AL
    loop .l1
    cld
.done:
    ret

;Obtenir la longueur d'une chaîne (en octets)
;
;Entrée
; rsi   Adresse de la chaîne
;
;Sortie
; rcx   Longueur de la chaîne

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

Answer 2

Les 31 octets de code assembleur x86-64 suivants pour void strrev(char* p) inverseront une chaîne de n'importe quelle longueur (y compris la chaîne vide) sur place, n'utilisant rien d'autre que l'ensemble d'instructions de base.

Cependant, la routine exige que le pointeur de la chaîne soit dans le registre rdi (conformément à l'ABI System V), et non rdx. Un mov rdi, rdx coûterait 3 octets. De plus, en raison de l'utilisation de deux xchg implicitement verrouillés, les performances vont être médiocres.

La petite taille est en partie due à l'utilisation créative des effets secondaires des instructions stosb et lodsb d'un seul octet qui lisent et incrémentent/décrémentent respectivement rdi et rsi en fonction du drapeau de direction, qui peut être activé et désactivé au moyen des instructions d'un seul octet std / cld.

Si le code était x86-32 ou pouvait se limiter à des chaînes de moins de 4 Go, quelques octets d'économies supplémentaires pourraient être réalisés.

0000000000000000 :
   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 
  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 
  1e:   c3                      ret