strlen() usando SSE 4.2

Há uns meses atrás (ou será que já faz um ano?) topei com uma dica do amigo Cooler, em seu blog, mostrando como comparar duas strings usando SSE 4.2. A rotina é realmente rápida porque compara 16 bytes de cada vez, ao invés de byte por byte ou, até mesmo, dword por dword (ou qword, se otimizarmos para o modo x86-64). Confesso que não tinha nenhuma intimidade com a instrução PCMPISTRI, disponibilizada pelo SSE 4.2 e fiquei maravilhado com o achado.

A rotina que ele publicou foi essa (publico aqui apenas a versão x86-64):

; Original code by Cooler_  c00f3r[at]gmail[dot]com
bits 64
section .text

global strcmp_sse42

; int strcmp_sse42(char *ptr1, char *ptr2);
strcmp_sse42:
  mov    rax,rdi
  sub    rax,rsi
  sub    rsi,16
   
strloop:
  add    rsi,16
  movdqu xmm0,[rsi]
  pcmpistri xmm0,[rsi+rax],0b0011000
  ja     strloop
  jc     blockmov
  xor    eax,eax
  ret
  
blockmov:
  add    rax,rsi    
  movzx  rax,byte [rax+rcx]
  movzx  rsi,byte [rsi+rcx]
  sub    rax,rsi    
  ret

O detalhe, é claro, está na instrução PCMPISTRI e no byte de controle… Ele torna a instrução bastante flexível e, ao mesmo tempo, difícil de entender… Eis uma outra rotina da libc que pode ser acelerada (de novo, para x86-64, mas, agora, com meus comentários):

bits 64

section .rodata
; Pares de bytes contendo faixas (ranges).
  align 16
_ranges:
  db 1, 0xff      ; Faixa entre (char)1 e (char)0xff.
  times 14 db 0   ; As demais "faixas" não são "usadas".

section .text

global strlen_sse42

; size_t strlen_sse42(const char* s1)
  align 16
strlen_sse42:
  xor ecx,ecx           ; Necessário. Garante que os bits
                        ; superiores, [63:5], de RCX 
                        ; estejam zerados.

  lea rax,[rdi-16]
  movdqu xmm0,[_ranges]

.loop:
  add rax,16

  ; Compara os 16 bytes do buffer apontado por RAX
  ; Com os pares de faixas em XMM0...
  ;
  ; PCMPISTRI é "Packed Compare Implicit-ending String 
  ; returning Index" ou algo assim... "implícito" 
  ; significa string terminada com '\0'.
  ;
  ; O byte de controle da instrução representa:
  ;
  ; +-+-+---+---+-+-+
  ; |0|0|0 1|1 0|0|0|-----------> 0 = char
  ; +-+-+---+---+---+             1 = short
  ;    |  |   |  |
  ;    |  |   |  +--------------> 0 = unsigned
  ;    |  |   |                   1 = signed
  ;    |  |   |
  ;    |  |   |                   00 = Equal any
  ;    |  |   |                   01 = "Ranges"
  ;    |  |   +-----------------> 10 = Equal each (string compare)
  ;    |  |                       11 = Equal ordered
  ;    |  |
  ;    |  |                       00 = Positive Polarity
  ;    |  +---------------------> 01 = Negative Polarity
  ;    |                          10 = Masked (+)
  ;    |                          11 = Masked (-)
  ;    |
  ;    +------------------------> 0 = Least significant index
  ;                               1 = Most significant index

  pcmpistri xmm0,[rax],0b0_01_01_0_0  ; LSB InRes2 offset; 
                                      ; InRes2=~InRes1; 
                                      ; Range compare; 
                                      ; unsigned char.

  jnz .loop   ; ZF=1 só se um dos bytes de [rax] for 0 
              ; (o 'i' do mnemônico pcmp(i)stri garante isso).
              ; ECX é índice (dos 16 bytes) onde achou o '\0'.
              ; (o 'i' de pcmpistr(i) garante isso).

  add rax,rcx

  lea rdx,[rdi]
  sub rax,rdx
  ret

Bem… Como é que PCMPISTRI funciona? Ela toma dois valores de 16 bytes (sim! bytes!) e os comparara de acordo com os bits de 0 a 3 do valor imediato, segundo o comentário que você pode ver acima. No caso de usarmos “unsigned char”, cada byte comparado setará ou zerará um bit de um registrador interno chamado InRes1. Depois que a comparação for feita, podemos inverter ou não o valor contido em InRes1 e colocá-lo em InRes2 – a isso é dado o nome de “polarização” (informada nos bits 4 e 5).

No caso da instrução PCMPISTRI, o bit 6 diz como o valor de ECX será calculado. Isso é feito fazendo uma varredura em InRes2 e, o primeiro bit setado, encontrado (do primeiro ao último ou vice-versa) é colocado em ECX. Se todos os bits estiverem zerados, ECX retornará 16 (será?), mas o flag ZF também estará zerado por causa do I no final do nome do mnemônico (ou seja, a instrução não achou um fim-de-string, um char ‘\0’).

Na rotina acima eu peço para PCMPISTRI comparar cada byte da string com uma faixa de bytes variando de 1 a 255. Os valores zerados na faixa nao contam porque PCMPISTRI irá parar a busca ao encontrar um ‘\0’, de qualquer maneira…

Só um aviso… existem instruções similares, como PCMPESTRI, onde o tamanho da string tem que ser informado no par EDX:EAX. Existem também PCMPISTRM e PCMPESTRM que retornam uma “máscara”, isto é, o próprio InRes2.

Outra dica importante: Essas instruções são feitas para lidar com strings e, por isso, a Intel não impõe a necessidade dos dados estarem alinhados em 16 bytes, como é comum com as instruções SSE. Alinhei _range acima só por vício mesmo… :)

Anúncios