quarta-feira, 3 de agosto de 2011

Turbinando o strcpy

o strcpy, como todos conhecem, é uma função que copia os bytes de um buffer para outro, até encontrar ZERO. Uma implementação simples desta função, implementada na maioria dos compiladores, seria algo como:

char* strcpy(char* dest, char* origem)
{
    char* ret = dest;
    while( *dest++ = *origem++ );
    return ret;
}

Bastante simples, não é? Parece impossível otimizá-la, mas não é.

Vamos pensar o que o loop desta função faz:

1. Copia o valor do ponteiro de origem para dest;
2. Incrementa ambos os ponteiros;
3. Verifica se o valor copiado foi ZERO.
4. Se não, volta ao passo 1. Se sim, cai fora.

Estes passos são executados de acordo com a quantidade de caracteres na string. Ou seja, se "origem" possui 39 caracteres mais o ZERO no final, os passos 1, 2, 3 e 4 serão executados 40 vezes.
Ora, se estamos numa plataforma 32 bits, nossos registradores da CPU conseguem copiar 4 bytes em praticamente o mesmo tempo que se leva para copiar 1 byte (se for um 64 bits é possível copiar 8 de uma vez).

Então por quê não copiamos de 4 em 4 bytes, e reduzimos o número de iterações para 10? Isso é fácil, mudando o tipo do ponteiro para long* (considerando que long seja 32 bits na sua plataforma).
Mas ainda há outro problema: somente 1 dos 4 bytes será nulo, então precisamos criar uma macro ou função inline que faça essa verificação, e depois copiar os bytes faltantes se houverem. Embora eu tenha preferência por utilizar funções inline quando em C++, quero que este código funcione em C também, portanto vou optar por definir uma macro.

Vamos ao código:

char* strcpy_turbo( char* dest, char* origem )
{
    register long* longdest = (long*)dest;
    register long* longorig = (long*)origem;
    register char* restodest;
    register char* restoorig;

    while( !TEM_BYTE_NULO( *longorig ) )
    {
        *longdest++ = *longorig++;
    }

    /* agora copiamos os bytes que ficaram faltando */
    restodest = (char*)longdest;
    restoorig = (char*)longorig;

    while( *restodest++ = *restoorig++ );
   
    return dest;
}

(se você não está familiarizado com declaração "register", elas servem para sugerir ao compilador que mantenha essas variáveis no registro. Não é garantido que ele vá mantê-las lá, mas elas terão preferência).

Agora precisamos definir a macro TEM_BYTE_NULO.

Uma forma seria:

#define TEM_BYTE_NULO( e ) ( (*e == 0) || (*(e + 1) == 0) || (*(e + 2) == 0) || (*(e + 3) == 0) )

Infelizmente, esta operação é muito custosa, e como nós queremos turbinar ao máximo a função, precisamos de algo mais eficiente.

Matematicamente, é possível utilizar a macro da seguinte forma:

#define TEM_BYTE_NULO( e ) (((e) - 0x01010101 ) & ~(e) & 0x80808080 )

Como é possível?

O segredo aqui é que o único byte que inverte o valor do bit mais significativo quando se decrementa 1 é o ZERO.

Assim, o bit mais significativo só ficará setado na expressão:
(BYTE -1) & ~BYTE

Se BYTE for ZERO. Para qualquer outro valor, o bit será zerado. Assim, é possível afirmar que:

(BYTE -1) & ~BYTE & 80

Só será true caso BYTE seja ZERO.

Para 4 bytes, a expressão seguinte segue a mesma lógica:

((LONG) - 0x01010101 ) & ~(LONG) & 0x80808080

Só retornará TRUE caso pelo menos 1 byte seja zero.


E este é o nosso strcpy turbinado :)

Nenhum comentário:

Postar um comentário