Variable Length Arrays e alloca()…

Dessa vez não vou bancar o espertinho e te dizer o que é melhor. A decisão é sua, mas tome-a com cuidado!

Eis duas funções que fazem a mesma coisa:

#include <alloca.h>
#include <stdio.h>
#include <stddef.h>

// O tamanho do array vem de algum outro lugar...
extern size_t len;

void f(int x)
{
  if (x)
  {
    // Usando VLA.
    char buffer[len + 1];

    snprintf(buffer, len, "Valor: %d", x);
    printf("-> %s\n", buffer);
  }
}

void g(int x)
{
  if (x)
  {
    // Usando alloca().
    char *buffer = alloca(len + 1);

    snprintf(buffer, len, "Valor: %d", x);
    printf("-> %s\n", buffer);
  }
}

Ambas as funções alocam len + 1 bytes na pilha e dealocam assim que a função termina. Você pode supor que o compilador criará exatamente o mesmo código para as duas funções, mas não é isso que acontece:

f:                                 g:                            
  test  edi, edi                    test  edi, edi
  jne .L10                          jne .L19
  ret                               ret

.L10:                              .L19:
  push  rbp                         push  rbp

  mov r9d, edi                      mov r9d, edi
  mov r8d, .LC0                     mov r8d, .LC0
  mov rcx, -1                       mov rcx, -1
  mov edx, 1                        mov edx, 1

  mov rbp, rsp                      mov rbp, rsp
  push  rbx                         push  rbx
  sub rsp, 8                        sub rsp, 8

  mov rsi, [len]                    mov rsi, [len]

  mov rbx, rsp                        

  lea rax, [rsi+16]                 lea rax, [rsi+31]           
  and rax, -16                      and rax, -16              
  sub rsp, rax                      sub rsp, rax              
  xor eax, eax                      xor eax, eax              

                                    lea rbx, [rsp+15]         
                                    and rbx, -16              
  mov rdi, rsp                      mov rdi, rbx              
  call  __snprintf_chk              call  __snprintf_chk        
  mov rdx, rsp                      mov rdx, rbx               
  mov esi, .LC1                     mov esi, .LC1 
  mov edi, 1                        mov edi, 1                
  xor eax, eax                      xor eax, eax              
  call  __printf_chk                call  __printf_chk

  mov rsp, rbx                      
                                    
  mov rbx, [rbp-9]                  mov rbx, [rbp-8]  
  leave                             leave                       
  ret                               ret

Note que função f() é menor que a função g (os MOVs extras tomam apenas 2 bytes cada), enquanto que a função g() tem uma instrução LEA extra… Mas a função f() preserva, desnecessariamente, o stack pointer (que será recuperado na instrução LEAVE)… Ainda, g() usa um pouco mais de espaço na pilha do que f(). O único “pecado” da função g(), ao meu ver, é o segundo alinhamento feito com o ponteiro da pilha, agora mentido em RBX que é desnecessário, já que RSP foi inicializado e alinhado baseado em RAX, antes… Se não fosse isso, ela seria, necessariamente, pelo menos, 1 ciclo de clock mais rápida!

Fora isso… as duas funções são identicas e tendem a serem executadas com a mesmíssima quantidade de ciclos de clock. Qual vocẽ prefere?

Anúncios

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!

Resolvendo minha dúvida sobre a carga do bootloader (UEFI)

Uma das dúvidas que tive ao começar a estudar UEFI foi “Em que endereço físico o loader é carregado?”. No modo legado, via serviço da BIOS (INT 0x19), o Master Boot Record é carregado sempre no endereço físico 0x7C00 (endereço lógico 0:0x7c00). Isso dá uma boa base para trabalhar a carga de qualquer loader mais complexo que apenas 1 setor (512 bytes), mas não temos (em teoria) a mesma certeza com relação ao loader em modo protegido que o UEFI carrega na memória.

Felizmente, UEFI carrega o executável numa região bem alta da memória e deixa muito espaço disponível para carregarmos o “kernel”. Isso pode ser visto através do comando memmap.

A listagem abaixo foi obtida numa VM, usando QEMU (qemu-system-x86_64) e a BIOS OVMF, configurada com apenas 1 GiB de RAM (retirei os “atributos” para ficar melhor formatado aqui no blog):

FS0:> memmap
Type       Start            End              # Pages
BS_Code    0000000000000000-0000000000000FFF 0000000000000001
Available  0000000000001000-000000000009FFFF 000000000000009F
Available  0000000000100000-00000000007FFFFF 0000000000000700
ACPI_NVS   0000000000800000-0000000000807FFF 0000000000000008
Available  0000000000808000-000000000080FFFF 0000000000000008
ACPI_NVS   0000000000810000-00000000008FFFFF 00000000000000F0
BS_Data    0000000000900000-00000000011FFFFF 0000000000000900
Available  0000000001200000-000000003BFBDFFF 000000000003ADBE
BS_Data    000000003BFBE000-000000003BFDDFFF 0000000000000020
Available  000000003BFDE000-000000003E55DFFF 0000000000002580
LoaderCode 000000003E55E000-000000003E686FFF 0000000000000129
Available  000000003E687000-000000003E72BFFF 00000000000000A5
BS_Data    000000003E72C000-000000003E748FFF 000000000000001D
Available  000000003E749000-000000003E765FFF 000000000000001D
BS_Data    000000003E766000-000000003E79BFFF 0000000000000036
Available  000000003E79C000-000000003E79DFFF 0000000000000002
BS_Data    000000003E79E000-000000003E7A6FFF 0000000000000009
Available  000000003E7A7000-000000003E7A7FFF 0000000000000001
BS_Data    000000003E7A8000-000000003E9F7FFF 0000000000000250
ACPI_NVS   000000003E9F8000-000000003EA0BFFF 0000000000000014
Reserved   000000003EA0C000-000000003EA29FFF 000000000000001E
BS_Code    000000003EA2A000-000000003ECBEFFF 0000000000000295
RT_Data    000000003ECBF000-000000003EDA4FFF 00000000000000E6
RT_Code    000000003EDA5000-000000003EE40FFF 000000000000009C
BS_Data    000000003EE41000-000000003FD40FFF 0000000000000F00
BS_Code    000000003FD41000-000000003FEC0FFF 0000000000000180
RT_Code    000000003FEC1000-000000003FEF0FFF 0000000000000030
RT_Data    000000003FEF1000-000000003FF14FFF 0000000000000024
Reserved   000000003FF15000-000000003FF18FFF 0000000000000004
ACPI_Recl  000000003FF19000-000000003FF20FFF 0000000000000008
ACPI_NVS   000000003FF21000-000000003FF24FFF 0000000000000004
BS_Data    000000003FF25000-000000003FFCFFFF 00000000000000AB
RT_Data    000000003FFD0000-000000003FFEFFFF 0000000000000020
Available  000000003FFF0000-000000003FFFFFFF 0000000000000010
 
  Reserved  :             34 Pages (139,264 Bytes)
  LoaderCode:            297 Pages (1,216,512 Bytes)
  LoaderData:              0 Pages (0 Bytes)
  BS_Code   :          1,046 Pages (4,284,416 Bytes)
  BS_Data   :          7,031 Pages (28,798,976 Bytes)
  RT_Code   :            204 Pages (835,584 Bytes)
  RT_Data   :            298 Pages (1,220,608 Bytes)
  ACPI_Recl :              8 Pages (32,768 Bytes)
  ACPI_NVS  :            272 Pages (1,114,112 Bytes)
  MMIO      :              0 Pages (0 Bytes)
  MMIO_Port :              0 Pages (0 Bytes)
  PalCode   :              0 Pages (0 Bytes)
  Available :        252,858 Pages (1,035,706,368 Bytes)
              -------------- 
Total Memory:          1,023 MB (1,073,209,344 Bytes)

Aqui o “BS” de BS_Code e BS_Data significa “Boot Services“, e “RT”, “RunTime services“… Existem áreas reservadas e reclamadas pelo ACPI e, lá no meio, temos “LoaderCode“:

LoaderCode 000000003E55E000-000000003E686FFF 0000000000000129

Com 297 páginas reservadas (ou, cerca de 1.16 MiB)… Note que temos 165 páginas (“disponíveis” logo à seguir, o que nos dá quase 700 KiB), provavlemente para o segmento de dados do loader.

Para um “loader”, 2 MiB é mais que suficiente! Considere agora que o endereço físico “tradicional” para a carga de kernels (0x100000) têm 1792 páginas disponíveis, ou 7 MiB! E, mesmo que seu kernel não caiba nesse espaço, temos, no total, quase 988 MiB disponíveis em 10 pedaços, onde as partes marcadas em verde são as realmente usáveis e a em vermelho será usada pelo loader:

Type       Start            End              # Pages
Available  0000000000001000-000000000009FFFF 000000000000009F
Available  0000000000100000-00000000007FFFFF 0000000000000700
Available  0000000000808000-000000000080FFFF 0000000000000008
Available  0000000001200000-000000003BFBDFFF 000000000003ADBE
Available  000000003BFDE000-000000003E55DFFF 0000000000002580
Available  000000003E687000-000000003E72BFFF 00000000000000A5
Available  000000003E749000-000000003E765FFF 000000000000001D
Available  000000003E79C000-000000003E79DFFF 0000000000000002
Available  000000003E7A7000-000000003E7A7FFF 0000000000000001
Available  000000003FFF0000-000000003FFFFFFF 0000000000000010

Vale lembrar que, depois que o loader entrega o controle ao kernel, podemos descarregar todo o Boot Services e o RunTime services, liberando mais 34 MiB de RAM… E se tivermos mais que apenas 1 GiB de RAM, mais espaços serão disponibilizados…

É bom lembrar, também, que os espaços de endereços relativos aos dispositivos PCI, PCIe, LAPIC, I/O PIC e outros só não constam dessa lista porque não requisitei mais que 1 GiB, mas eles estão lá e disponíveis, no UEFI, via “protocolos”.

Double buffering sem paginação (dirty rectangles)

Double Buffering é a técnica onde temos dois buffers na memória de vídeo onde desenha-se no buffer “invisível” e muda-se o ponteiro do início do framebuffer para esse buffer, quando terminarmos, tornando o outro buffer (que estava “na frente”) o novo back buffer… É claro que existe a necessidade de “sincronizar” os buffers, copiando as modificações feitas no novo front buffer para o novo back buffer, para que os novos desenhos reflitam as modificações feitas…

Acontece que tem gente que está lidando com os modos gráficos VESA, em modo protegido, sem o auxílio da Protected Mode Interface, que não está disponível em máquinas virtuais como QEMU e VirtualBox (e, suspeito, também não exista no VMWare)… Nesse caso, esse esquema de double buffering não é lá muito útil, em termos de performance. A solução? “Retângulos Sujos” (dirty rectangles).

A técnica leva em consideração que podemos fazer BitBlt apenas das regiões que foram modificadas na back surface para a front surface. Essas superfícies podem ser mapeadas assim: A front surface contém, no seu ponteiro para o buffer, o endereço do linear framebuffer (0xE0000000, no QEMU, por exemplo) e a back surface pode ser alocada na memória do sistema (RAM). O estado inicial de ambas as superfícies devem ser idênticas e podemos conseguir isso “limpando” os buffers (preenchendo com zeros).

Daí para frente, quaisquer modificações na back surface cria regiões… Por exemplo, Se traçarmos uma linha de (x_0,y_0) para (x_1, y_1), cria-se um retângulo \{x_0,y_0,x_1+1,y_1+1\} (lembre-se do sistema de coordenadas que estamos usando!) e o colocamos (apenas suas coordenadas) numa lista… Claro, desenharemos, na back surface a linha desejada… Todas as outras modificações no back buffer acrescentarão coordenadas de retângulos na lista. Na hora de copiar as modificações feitas na back surface para a front surface teremos que fazer apenas duas coisas:

  1. Esperar pelo retraço vertical para não causar flickering;
  2. Percorrer a lista de retângulos, fazendo BitBltCopy da back surface para a front surface.

A espera pelo retraço vertical é simples… Embora os modos de vídeo não sejam padrão VGA, toda e qualquer placa de vídeo, inclusive as emuladas, suportam os controladores do padrão VGA. Retraço vertical é uma coisa simples de verificar:

inline unsigned char inb(unsigned short port)
{
  unsigned char result;

  __asm__ __volatile__ (
    "in %1,%b0" 
    : "=a" (result) : "dN" (port)
  );

  return result;
}

inline int vsync(void)
{
  // Se o bit 3 do registrador "VGA Input Status" for 1,
  // estamos no sincronismo vertical!
  return !!(inb(0x3da) & (1 << 3));
}

A lista de retângulos também é fácil de manter (veja este artigo aqui):

struct dirtyrect_entry {
  struct _list_head *next;
  struct rect rc;
};

// "Cabeça da lista"...
// Os itens que serão adicionados na lista são do tipo
// struct dirtyrect_entry, acima.
struct _list_head backsurf_dirtyrec_list =
  EMPTY_LIST(backsurf_dirtyrec_list);

Adicionar retângulos na lista é só uma questão de usar a função _list_add_after ou _list_add_tail, de acordo com suas necessidades… Uma vez que todos os retângulos “sujos” tenham sido adicionados à lista, a cópia para a front surface é tão simples quanto:

struct _list_head *p;
foreach(p, backsurf_dirtyrec_list)
{
  struct rect *rc = &((struct dirtyrect_entry *)p)->rc;

  BitBltCopy(frontsurfp, 
             rc->left, rc->top,
             backsurfp,
             rc);
}

Daí podemos nos livrar de todos os itens da lista e começar tudo de novo… Claro, se você fizer com carinho, pode retirar o item da lista no próprio loop acima…

O uso de transferências de blocos usando BitBltCopy tem a vantagem de que o recorte dos retângulos será “automático” (veja o artigo anterior), mas o ponto importante aqui é que, na back surface, devemos lidar apenas com regiões pequenas e/ou com a menor quantidade possível de regiões… Isso implica que se uma região já esteja na lista, ou parte dela, podemos simplesmente estender o retângulo ou deixá-lo como está… Por exemplo: Suponha que você traçou uma linha de (10,10) até (20,20). Isso te dará um retângulo de coordenadas (10,10,21,21) e ele é colocado na lista… Logo depois você traça outra linha de (19,18) para (11,11). O que fazer?

O primeiro passo é varrer a lista para ver se já existe um retângulo onde essas coordenadas se encaixam, senão, criar um retângulo (11,11,20,19) e colocá-lo na lista. No exemplo acima, já temos o retânculo (10,10,21,21) e, portanto, já que o novo retângulo encontra-se “dentro” deste, nenhum retângulo adicional é necessário.

Existe o caso, também, de termos um retângulo (10,10,21,21) na lista e queremos colocar outro de coordenadas (5,5,12,12). Neste caso, como há uma sobreposição de retângulos, podemos modificar o de coordenadas (10,10,21,21) para (5,5,21,21), sem adicionar nenhum retângulo novo.

Como você fará para decidir se o retângulo adicionado é grande demais ou pequeno demais, fica a cargo da sua rotina de gerência de retângulos. A ideia é apenas copiar blocos menores que uma superfície inteira para outra…

Bit Block Transfers (BitBlt)

Deixe-me mostrar, caso a caso, como a transferência de pixels de uma superfície para outra pode ser feito. A ideia é criar uma função que faça isso “sozinha”, com base em 5 argumentos:

int BitBltCopy(struct surface *dest,
               int x, int y,
               struct surface *src,
               struct rect *rc);

Aqui, queremos trasferir pixels da região do retângulo rc da superfície src para a posição (x,y) da superfície dest. A rotina deverá levar em conta o formato de pixels das duas superfícies, seus tamanhos (e o da região) e os casos especiais citados no artigo anterior (aqui). Para facilitar, vou considerar apenas o formato PELFMT_RGBA aqui, mas, no final do artigo, farei considerações sobre os outros formatos.

O endereço do primeiro pixel do retângulo, considerando-o totalmente dentro da superfície src pode ser facilmente calculado como:

static size_t surface_getpelsize(struct surface *surfp)
{
  switch (surfp->pelfmt)
  {
  case PELFMT_INT: return sizeof(int);
  case PELFMT_RGB: return 3;
  case PELFMT_RGBA: return 4;  
  }
  return 1;
}
void *surface_getptr(struct surface *surfp, uint32_t x, uint32_t y)
{
  return surfp->buffp + (y * surfp->width + x) * surface_getpelsize(surfp);
}

Claro, o caso onde temos PELFMT_1BPP é um caso especial e não deve ser considerado aqui.
Considerando que a região “fonte” esteja totalmente dentro da superfície “fonte” e a posição (x,y) “destino” esteja dentro da superfície “destino”. e que ambas as superfícies tenham o mesmo formato, a função BitBltCopy fica bem simples:

int BitBltCopy(struct surface *dest,
               int x, int y,
               struct surface *src,
               struct rect *rc)
{
  char *srcptr, *destptr;
  size_t row,
         pixel_size, 
         src_scanline_size, dest_scanline_size;

  srcptr = surface_getptr(src, rc->left, rc->top);
  destptr = surface_getptr(dest, x, y);
  pixel_size = surface_getpelsize(src);
  src_scanline_size = src->width * pixel_size;
  dest_scanline_size = dest->width * pixel_size;

  for (row = rc->top; row < row->bottom; row++)
  {
    _memcpy(destptr, srcptr, (rc->right - rc->left) * pixel_size);
    srcptr += src_scanline_size;
    destptr += dest_scanline_size;
  }

  return 1;
}

Um ponto importante aqui é o uso da função _memcpy. Lembre sempre: A ideia aqui é fazer transferência de blocos, nunca (ou quase nunca) bytes ou bits individuais… Dito isso, a rotina acima faz o trabalho nas condições ideais citadas, no entanto, temos os casos especiais…

A posição (x,y) pode não estar dentro da surperfície destino:

Se (x,y) estiver além da área da superfície, podemos desconsiderar a cópia. E mais: Se o retângulo fonte estiver totalmente fora da superfície destino, também desconsideraremos a cópia:

 ...
  if (x >= dest->width || y >= dest->height) return 0;
  if (x <= (int)src->width || y <= (int)src->height) return 0;

  /* ... o resto da rotina ... */
  srcptr = surface_getptr(src, rc->left, rc->top);
  destptr = surface_getptr(dest, x, y);

Este é apenas um exemplo dos testes de casos especiais que podemos colocar na rotina. Deixo os detalhes para você, dadas as explicações deste artigo…

A posição (x,y) pode estar “parcialmente” dentro da surperfície destino:

É o caso, por exemplo, das regiões periféricas no diagrama abaixo. Note que temos 8 casos especiais onde as áreas em verde-escuro da região fonte serão copiadas para a superfície destino. Isso significa que teremos que mudar o cálculo dos ponteiros iniciais e do tamanho da linha de varredura para esses casos.

Casos de uso

A rgião pode estar, também, “parcialmente” dentro da superfície fonte:

Este caso é análogo ao diagrama acima, mas ao invés de considerarmos os bits copiados temos que considerar os bits que iremos copiar. Por exemplo, considere o caso do canto superior direito… Apenas os pixels verde-escuros devem ser copiados para a superfície destino… Isso poderia ser feito recalculando o retângulo fonte, mas os pixels “invisíveis” devem permanecer invisíveis na superfície destino.

O caso acima pode ser exemplificado com o caso citado acima, em relação à superfície fonte e o caso central para a superfície destino. O diagrama abaixo demonstra o problema… A região em vermelho contem os pixels que serão copiados na superfície destino, a área verde dessa superfície não deve ser alterada.

Claro que teremos que modificar o retângulo a ser copiado, mas temos que modificar também as coordenadas (x,y) para onde o retângulo efetivo será copiado na superfície destino… Isso faz com que a cópia seja bem mais rápida…

Considere, também o caso onde, na superfície destino, apenas um pedaço do regângulo efetivo tenha que ser copiado, como abaixo:

Aqui, apenas a área “vermelha mais escura” será copiada, todo o resto deve ser ignorado (incluindo o “vermelho menos escuro”).

BitBltCopy() não considera retângulos de tamanhos diferentes entre fonte e destino!

Você pode querer fazer algo como copiar uma região fonte de tamanho definido para uma região destino com outro tamanho definido, mas diferente do tamanho da origem… Ou seja, pode querer mudar a escala (para criar um efeito de zoom in ou zoon out). Isso não é feito pela função BitBltCopy, que já deve ser complicada o suficiente com todos esses casos especiais. A assinatura da função seria similar à BitBltCopy, com uma diferença. Ao invés de especificarmos a posição (x,y), na superfície destino, especificamos o retângulo destino:

int BitBltStrech(struct surface *dest,
               struct rect *rcDest,
               struct surface *src,
               struct rect *rcSrc);

Todos os casos especiais acima continuam válidos, exceto pelo fato de que teremos uma superfície intermediária que conterá a região efetiva, da superfície fonte, interpolada que, depois, será copiada para o retângulo destino da superfície destino.

Essa função, obviamente, é mais lenta que BitBltCopy, já que essa superfície intermediária precisa ser calculada, possivelmente usando ponto flutuante.

Não se esqueça dos formatos de pixels:

As explicações acima não levam em conta a diferença de formatos de pixels entre superfícies. Podemos separar as funções naquelas que não levam em conta essa distinção e outras que serial “independentes de dispositivo”, que as levariam. Essa diferenciação tem um custo alto: Não podemos, simplesmente, copiar blocos via _memcpy, mas teríamos que lidar com pixels individuais, implicando em um loop interno para cada posição X que queiramos copiar.

Outra solução viável, mas também um pouco custosa, é converter as regiões fonte para uma superfície intermediária com o mesmo formato da superfície destino. Essas conversões podem ser especializadas, do tipo funções nomeadas surface_create_rgba_from_rgb() ou surface_create_rgb_from_8bpp(), por exemplo. Uma função mais genérica como surface_create_intermediary() poderia fazer a mágica verificando os formatos de pixel das superfícies fonte e destino e criando a superfície intermediária com base nelas e usaríamos essa nova superfície num BitBltCopy para finalizar o processo. A vantagem é que teremos uma superfície intermediária menor que a fonte (supostamente)…

Preparando para copiar blocos de bytes das superfícies

Acredito que eu já tenha falado disso por aqui (só não encontrei onde), mas precisaremos fazer cópias de blocos de dados, para cada scanline, da superfície fonte para a superfície destino, se formos usar a abstração das “superfícies” que citei no artigo anterior… Obviamente, queremos fazer isso da maneira mais rápida possível… Podemos, por exemplo, determinar se o bloco tem tamanho maior que 128 bits (16 bytes) e usarmos instruções SSE que não lidam com ponto flutuante para mover tantos bytes quanto possíveis numa só tacada e deixar os bytes restantes para serem copiados por outros métodos…

A primeira tentativa de criar uma rotina memcpy customizada poderia ser essa:

#include <x86intrin.h>

void _memcpy_sse(void *dest, void *src, size_t size)
{
  __m128i *xdest, *xsrc;
  size_t xmm_blocks;
  size_t remaining;

  xmm_blocks = size / 16;
  remaining = size % 16;

  // Copia blocos de 16 em 16 bytes.
  xdest = dest; xsrc = src;
  while (xmm_blocks--)
    *xdest++ = *xsrc++;

  // Copia os bytes que restaram.
  dest = xdest; src = xsrc;
  while (remaining--)
    *(char *)dest++ = *(char *)src++;
}

A rotina tem o potencial de ser 16 vezes mais rápida que um simples memcpy que, supostamente, copia dados byte por byte. Mesmo que memcpy leve em consideração que você tem um processador capaz de lidar com 32 bits por vez, a rotina acima tem o potencial de ser, pelo menos, 4 vezes mais rápida… Considere agora a aproximação “ingênua”:

void _memcpy_asm(void *dest, void *src, size_t size)
{
  __asm__ __volatile__ (
    "rep; movsb"
    :: "D" (dest), "S" (src), "c" (size)
}

Ahhh… isso deve ser muito ruim, não? Afinal, mesmo usando uma única instrução em assembly (MOVSB) com o prefixo REP, estamos copiando bytes individuais de um buffer para outro! Algo parecido com _memcpy_sse poderia ser mais útil e rápido…

O problema é quando medimos a performance (usando minhas macros):

void main(void)
{
  static char buff1[65535], buff2[65535];
  uint64_t clocks1, clocks2;

  BEGIN_TSC;
  _memcpy_sse(buff1, buff2, sizeof buff1);
  END_TSC(clocks1);

  BEGIN_TSC;
  _memcpy_asm(buff1, buff2, sizeof buff1);
  END_TSC(clocks2);

  printf("_memcpy_sse: %" PRIu64 " cycles\n"
         "_memcpy_asm: %" PRIu64 " cycles\n",
         clocks1, clocks2);
}

Eis o resultado que obtenho num i5-3570 de 3.40 GHz:

$ ./test
_memcpy_sse: 90404 cycles
_memcpy_asm: 6296 cycles

Ou seja, _memcpy_asm, usando uma simples instrução prefixada é cerca de 14 vezes mais rápida que a função que copia de 16 em 16 bytes! Como isso é possível?

Alinhamento e caches

O primeiro motivo da lentidão de _memcpy_sse são os caches. Copiar blocos de 16 bytes via instruções SSE exigem que os dados estejam alinhados de 16 em 16 bytes para que não existam acessos entre duas linhas de cache simultaneamente. A rotina não pode lidar com isso porque os endereços contidos nos ponteiros dest e src podem, de fato, estar desalinhados (considere o caso de um formato de pixel PELFMT_RGB, onde cada pixel tem 3 bytes de tamanho). De fato, o compilador cria o loop de cópia via SSE assim:

; R8 = xsrc
; RCX = xdest
; RAX = xmm_blocks
...
.loop:
  add r8, 16
  movdqa  xmm0, XMMWORD PTR [r8-16]
  add rcx, 16
  sub rax, 1
  movaps  XMMWORD PTR [rcx-16], xmm0
  cmp rax, -1
  jne .loop
...

Repare nas instruções MOVDQA e MOVAPS. Esse A em ambos os mnemônicos significa Aligned, ou seja, é assumido que os ponteiros tenham alinhamento com 16 bytes (ou seja, que o endereço contenha os 4 bits inferiores zerados)… Se não tiver, 1 ciclo de clock adicional pode ser gasto… Usar as instruções “desalinhadas” como MOVDQU e MOVAPU (U de Unaligned) não ajuda, porque essas instruções são, de fato, sempre mais lerdas que as que assumem alinhamento.

Você pode estar pensando que existirão casos onde o alinhamento será obedecido e _memcpy_sse será de fato mais rápida… Infelizmente não… Acontece que, pelo que sei, desde a arquitetura Sandy Bridge a instrução MOVSB prefixada por REP tem um tratamento especial. Ela automaticamente copiará os maiores blocos possíveis e, internamente, leva em conta os problemas de alinhamento! Acho que ela lida diretamente com o tamanho de uma linha de cache (64 bytes). Se o bloco tiver mais que 64 bytes de tamanho, ela copiará uma linha inteira do cache, de um lugar para o outro… Em essência, ela funciona como _memcpy_sse, porém não lida com SSE e sempre lidará com blocos de tamanho tal onde a cópia seja mais eficiente… Os detalhes, são obscuros.

E quanto a memcpy?

Claro, podemos usar a função da libc, declarada em string.h: memcpy ou até mesmo a memmove. Infelizmente elas são mais lentas. A função memcpy é cerca de 60% mais lenta (cerca de 10000 ciclos) que um simples REP MOVSB e memmove é cerca de 160% mais lenta (cerca de 16300 ciclos)! Ambas ainda ganham de nossa _memcpy_sse e, neste caso, memcpy deve ser a nossa escolha preferida se o processador não tiver a otimização de REP MOVSB. Isso porque é injusto comparar a performance de memmove, que é projetada para lidar com blocos sobrepostos.

Para detectar se essa otimização do REP MOVSB existe, nada mais simples:

// Retorna 0 se não suporta, caso contrário, suporta!
int supports_enhanced_repmovsb(void)
{
  int result;

  __asm__ __volatile__ (
    "cpuid\n"
    : "=b" (result) : "a" (7) :
#ifdef __x86_64
      "%rcx", "%rdx"
#else
      "%ecx", "%edx"
#endif
  );

  return result & (1U << 9);
}

Mesmo assim, recomendo que use a função __builtin_memcpy do GCC, já que o compilador pode resolver substituí-la por REP MOVSB por si mesmo… Geralmente ele usa a libc (talvez não no modo freestanding)…

Então, a melhor maneira de lidamos com as rotinas é essa:

#include <stddef.h>
#include <string.h>

extern int supports_enhanced_repmovsb(void);
extern void _memcpy_asm(void *, void *, size_t);

// Ponteiro para a nossa "memcpy".
// retorna void * para manter a chamada compatível
// com a memcpy original!
void *(*_memcpy)(void *, void *, size_t);

// Essa rotina será chamada antes mesmo de main!
__attribute__((constructor))
void __init_memcpy(void)
{
  if (supports_enhanced_repmovsb())
    // Ignoro o "retorno" para manter a rotina "compatível"
    // com memcpy original!
    _memcpy =
      (void *(*)(void *, void *, size_t))_memcpy_asm;
  else
    _memcpy = memcpy; // ou __builtin_memcpy.
}

E, voilà, possivelmente você a rotina de cópia de blocos mais rápida para a máquina onde o código será executado! A única diferença é que, ao invés de usar memcpy ou _memcpy_asm, você chamará a função através do ponteiro _memcpy, que, efetivamente, criará uma chamada no estilo call [_memcpy], que “gasta” apenas 2 ciclos de clock adicionais, em comparação à chamada direta e poderá gastar mais, se o ponteiro não estiver no cache L1d. Mais ainda, se a própria função apontada não estiver no cache L1i, mas isso também acontece com as chamadas diretas.

De qualquer maneira, essa chamada indireta é sempre mais rápida que a rotina original, usando SSE. Mas, caso você ainda esteja cético com relação às performances, experimente modifica o loop final de _memcpy_sse que, se o último bloco a ser copiado tiver menos que 16 bytes, ele será executado… Poderíamos substituí-lo por:

  // Copia os bytes que restaram.
  //dest = xdest; src = xsrc;
  //while (remaining--)
  //  *(char *)dest++ = *(char *)src++;
  memcpy(xdest, xsrc, remaining);

Meça a performance e verá que não faz muita diferença se usarmos esse loop ou a a chamada a memcpy. Também não fará diferença se usarmos _memcpy_asm no lugar desse memset porque temos, no máximo, 15 bytes para mover, ou seja, menos que uma linha de cache.

GUI: Superfícies

Ao invés de lidarmos diretamente com bitmaps, podemos usar algum nível de abstração. Chamarei essa abstração de superfícies, que são áreas retangulares contidas em buffers com tamanhos, alturas e formatos de pixel e, é claro, ponteiros para arrays contendo os pixels:

struct surface {
  uint32_t width, height; // em "pixels".
  enum pixel_format pelfmt;
  void *buffp;
  struct palette *palp;
};

O campo pelfmt pode assumir (por enquanto) os valores de PELFMT_1BPP, PELFMT_8BPP, PELFMT_INT, PELFMT_RGB e PELFMT_RGBA, onde os dois últimos implicam em 1 byte por componente…O primeiro é usado para bitmaps que tenham 1 bit por pixel e, por consequência, 8 pixels por byte; e o segundo para bitmaps indexados, de 256 cores, onde uma paleta de cores é necessária. A paleta, usada apenas neste caso, tem a estrutura:

struct palette {
  size_t numentries;
  char entries[0]; // triplets RGB para cada entrada.
};

O formato PELFMT_INT é usado, primariamente, para quando formos mexer com Z Buffering, onde precisaremos armazenar apenas a componente Z de cada pixel.

Podemos ter valores diferentes, como PELFMT_R5G6B5 para pixels de 16 bits, por exemplo, mas esses 5 iniciais, acredito, são mais que suficientes.

A ideia da superfície é manter essa área total que pode ser manipulada em sub áreas ou “regiões” (retângulos) interiores. Por exemplo:

Superfície com uma região interna

A área cinzenta corresponde a totalidade da superfície e a região é especificada, na API, através de uma simples estrutura de retângulo:

struct rect {
  int left, top;
  int right, bottom;
};

Não uso pares de coordenadas nomeadas (x0,y0) e (x1,y1) para não causar confusão… (left,top) e (right,bottom) implica que os pontos do retângulo são posicionados exatamente como mostrados na figura…

Assim, com a API que lida com essa abstração, podemos fazer cópias de regiões de uma superfície para outra usando métodos de chamados de Bit Block Transfers ou BitBlt. É bom notar que mesmo uma linha horizontal ou vertical estão contidas numa região retangular de uma superfície se usarmos o sistema de coordenadas relacionado às bordas dos pixels, como mostrei neste artigo. Mas, em que, especificamente isso tudo é útil?

O framebuffer, por exemplo, pode ser definido como uma superfície de tamanho 1024×768 pixels, com formato RGBA assim:

struct surface frontvbuffer = {
  .width = 1024,
  .height = 768,
  .pelfmt = PELFMT_RGBA,
  .buffp = (void *)0xe0000000 // pointer para o framebuffer.
};

Qualquer manipulação com essa superfície fará com que os pixels vão diretamente para a tela. E, com o conceito de regiões, podemos também ter uma lista delas que indicam áreas da superfície que foram modificadas na última atualização da tela:

struct region_item {
  struct _list_head *next;
  struct rect rc;
};

// Cria uma lista vazia de regiões.
struct _list_head region_head = INIT_LIST;

Com essa lista, toda vez que modificarmos um lugar na superfície do frontvbuffer podemos acrescentar uma região (ou expandimos uma que já existe na lista), nos informando que essa é uma das regiões que teremos que copiar de ou para algum outro lugar (back buffer?). De qualquer maneira, é mais fácil fazer transferências de blocos de regiões do que de uma superfície inteira porque temos menos bytes para manipular!

Mais adiante mostrarei a técnica de manter essa lista de regiões modificadas num troço chamado de “Dirty Rectangles“.

As superfícies são mais flexíveis do que citei acima porque podem ser usadas, por exemplo, para manter “texturas”, “stencil buffers”, “Z buffers”, etc, bastando implementar um “formato de pixel” diferente e, é claro, essas superfícies secundárias podem ser alocadas dinamicamente e dealocadas ao bel prazer… No caso de texturas, imagine o caso onde você tem uma fonte bit-mapeada. Poderia ter uma textura como abaixo dentro de uma superfície:

Essa superfície pode ser dividida, claramente, em várias regiões. Cada “região” mapeada para um índice correspondente ao caractere ASCII que você quer desenhar numa outra superfície. Basta achar a região desejada e fazer um BitBlt dessa superfície para uma posição (x,y) desejada na superfície onde o caractere será desenhado (no frontvbuffer, por exemplo)…

A implementação do gerenciamento de regiões e as rotinas de BitBlt eu deixarei para outro artigo, mas considere que temos agora um container único para todo o tipo de gráficos que quisermos manipular e teremos meios unificados e rápidos para fazê-lo… As funções BitBlt levam em conta coisas interessantes, como o comprimento de uma scanline da região (podemos também usar registradores maiores para mover mais dados de uma tacada só) e se a região encontra-se totalmente dentro da superfície. Considere esse caso:

Parte da região está fora da superfície

Neste caso a parte mais “escura” da região poderá ser copiada e a parte mais clara será, obviamente, totalmente transparente ou ignorada… Esse tipo de cópia de região entre superfícies fica simples de ser feita, mas temos dois casos mais complicados. Considere este outro:

O lado esquerdo deverá ser transparente

Claro que o lado esquerdo da região será transparente, mas, quando ela for copiada para outra superfície, os pixels na área mais “verde-escura” estarão deslocados no mesmo tanto da quantidade de pixels transparentes (na área “verde-clara”), na superfície destino! A mesma coisa acontece se a região sendo copiada for maior do que a área da superfície inteira, em qualquer sentido (x ou y)…

ATENÇÃO!!!

É importante lembrar que essa “superfície” é uma abstração. É uma área retangular limitante onde podemos manipular “regiões” retangulares de seu interior: Preenchendo-as e copiando-as para outras regiões ou outras superfícies. E as rotinas que farão isso precisam levar em conta os casos especiais (como mostrei acima) e outros até: O que acontece se quisermos copiar uma região de uma superfície que tem um retângulo menor que o retângulo para o qual vamos copiar na superfície destino? Que tipo de filtragem faremos? Linear? Cúbica? Bi-Cubica? A mesma coisa se for o contrário (região fonte maior que a região destino)?

Existem ainda detalhes que podemos implementar usando a analogia da superfície. Por exemplo, multisampling, onde um pixel real é composto, na verdade, por muitos pixels na superfície… Isso permitirá alguma interpolação para implementar melhor antialiasing, mas consumirá alguma memória adicional e processamento.

De qualquer maneira, a junção do conceito de superfícies, regiões e do sistema de coordenadas que mostrei anteriormente forma uma ferramenta simples, mas poderosa para lidarmos com gráficos…