Cópia de blocos: um detalhe importante

De tempos em tempos me fazem perguntas sobre tópicos realmente básicos. Eis uma delas: “Qual é a melhor forma de copiar um bloco de dados? Do início para o fim ou do fim para o início?”. Resposta: depende!

Consideremos, para esse estudo que temos um array de 10 elementos, assim:

int a[] = { 1,2,3,4,5,6,7,8,9,0 };

Em C temos a função memcpy que toma os ponteiros do início do buffer destino e do início do buffer origem, bem como o tamanho (em bytes) que copiaremos os dados de um buffer para o outro. Mas, para responder a pergunta acima usarei algumas variações da rotina mais simples, abaixo:

void ArrayCopy(int *dest, int *src, size_t items)
{
  while (items--)
    *dest++ = *src++;
}

A rotina, obviamente, faz a cópia dos itens do array apontado por src para os itens do array apontado por dest, do início para o final. Eis um problema que pode aparecer:

#include <stdio.h>

static void ArrayCopy(int *, int *, size_t);
static void ShowArray(int *, size_t);

int a[] = { 1,2,3,4,5,6,7,8,9,0 };

void main(void)
{
  ShowArray(a, 10);
  ArrayCopy(a + 1, a, 9);
  ShowArray(a, 10);
}

void ArrayCopy(int *dest, int *src, size_t items)
{
  while (items--)
    *dest++ = *src++;
}

void ShowArray(int *p, size_t items)
{
  size_t i;

  fputs("{ ", stdout);
  if (items)
  {
    for (i = 1; i < items; i++, p++)
      printf("%d, ", *p);
    printf("%d ", *p);
  }
  puts("}");
}

Ao compilar e linkar:

$ cc -o test test.c
$ ./test
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

O que aconteceu foi que, ao copiar a[0] sobre a[1], na próxima iteração o mesmo valor será copiado para o próximo. É evidente que, o que o programador queria era uma sequência do tipo:

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Mas, infelizmente, só conseguirá isso se copiar o array de trás para frente. Repare que não há problemas se fizéssemos uma chamada do tipo ArrayCopy(a, a + 1, 9), já que sobrescrever o item anterior não modifica o próximo item do array de origem.

No contexto das rotinas contidas no header string.h, além de memcpy temos a rotina memmove, que é definida no ISO 9989 (a especificação da linguagem C) desde sempre… Essa outra rotina lida com a possibilidade de existir uma sobreposição como mostrada no exemplo acima e, neste caso, a rotina fará a cópia de trás para frente pra você.

É sempre bom lembrar que esse tipo de coisa (sobreposições) podem acontecer e são fonte de bugs… mas, não é interessante que o programador dê preferência à chamada a memmove ao invés de memcpy… A primeira é lenta, em relação à segunda, e deve ser usada apenas nos casos onde há possibilidade de sobreposições onde o ponteiro alvo está além do início do ponteiro fonte e, ao mesmo tempo, dentro da faixa de endereços do ponteiro fonte. Ou seja, a funçao faz algo mais ou menos assim:

void memmove(void *dest, void *src, size_t size)
{
  void *last_src;

  last_src = src + size;
  if (dest > src && dest < last_src)
    _rmemcpy(dest, src, size);
  else
    memcpy(dest, src, size);
}

Onde rmemcpy faz a mesma coisa que memcpy, mas copia de trás para frente:

void _rmemcpy(void *dest, void *src, size_t size)
{
  char *srcptr = src + size - 1;
  char *destptr = dest + size - 1;

  // Não tem sentido copiar um buffer para si mesmo.
  if (dest != src)
    while (size--)
      *destptr-- = *srcptr--;
}

Ok, mas e em assembly?

Ao invés de usarmos loops, como nas rotinas em C acima, temos as instruções de movimentação de DS:RSI para ES:RDI e o prefixo REP, que “repete” a instrução RCX vezes (ou DS:ESI para ES:EDI, ECX vezes, ou ainda o equivalente em 16 bits, dependendo do modo usado). Lembre-se, também, que temos um flag DF (Direction Flag) que incrementa ou decrementa RSI e/ou RDI, de acordo com a instrução.

Ou seja, ao invés de uma cópia explícita com pós incrementos ou pós decrementos, usando loops, podemos subsituir por REP MOVS? (MOVSB, MOVSW, MOVSD, MOVSQ)… De fato, no caso dos exemplos, fiz questão de usar o contador como variável de controle do loop. Isso é a mesma coisa que usar RCX como contador para REP MOVS.

Um detalhe importante: Alterar DF pode ser problemático! Se você modificá-lo, tenha certeza de recuperá-lo antes de realizar qualquer outra chamada de funções de bibliotecas (como a própria libc, por exemplo). Por default, tanto o seu sistema operacional, quantos as bibliotecas que você usa, esperam que este flag esteja zerado ou, pelo menos, que tenha um estado conhecido pelas rotinas. Assim, a cópia reversa deve ser feita assim:

inline void _rmemcpy(void *dest, void *src; size_t size)
{
  void *srcptr = src + size - 1;
  void *destptr = dest + size - 1;

  // Não tem sentido copiar um buffer para si mesmo.
  if (dest != src)
    __asm__ ___volatile__ (
      "std\t\n"
      "rep; movsb\t\n"
      "cld\t\n"
      : : "S" (srcptr), "D" (destptr), "c" (size)
    );
}

Você pode ficar tentado a usar o clobbercc” para preservar os flags, mas é minha experiência de que isso nem sempre funciona!

Anúncios