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…

Anúncios

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…

 

Deslocando uma string de bits

Eu falei, no post anterior, que precisei usar rotações para uma rotina que estou fazendo para o futuro (em breve, espero) artigo sobre BitBlt (Bit Block Transfers). A rotina será útil em manipulações de mapas de bits (ou em “superfícies” que tenham 1 bit por pixel – 1 bpp). Ficará mais claro quando chegarmos lá. Aqui eu quero apresentar a rotina de deslocamento de uma string de bits (não de “bytes”!), onde um conjunto de bits “no meio” de um conjunto de bytes, precisa ser alinhada com o bit 0 (ou a coordenada x=0)… O diagrama abaixo mostra como funciona:

Aqui temos uma string de 14 bits (que marquei com bolinhas vermelhas [1] e pretas [0]) que preciso deslocar 7 bits para a  “esquerda”. Acontece que todos os bits precisam sofrer esse deslocamento… Coloquei “esquerda” entre aspas porque, na realidade, o deslocamento será feito para a direita (node que representei o bit 0 à esquerda para coincidir com uma coordenada x, de uma “pixel”. Sabemos que o LSB, na verdade, encontra-se à direita…

A técnica é simples: O primeiro byte da string de bits é deslocada em 7 bits para a direita e os demais bytes são rotacionados em 7 bits, também para a direita… Cada byte central sofre dois mascaramentos para isolar os bits que serão copiados para o byte anterior e mantidos no próximo byte. Como o deslocamento foi de 7 bits, isso significa que só precisamos dos 7 bits superiores do 2º byte (no exemplo) e do primeiro bit, todos os demais bits são zerados para que, ao fazer um OR, eles sejam misturados corretamente. Isso é feito com todos os pares de bytes (o 1º com o 2º, o 2º com o 3º, etc… até chegamos ao byte n-1 e n).

Observe que, no final das contas, teremos apenas 2 bytes (porque temos apenas 13 bits que nos interessam) ou, se você quiser manter os 24 bits iniciais, os bits superiores deverão ser zerados! Claro que temos como saber, de antemão, que podemos alocar os bits deslocados em um número determinado de bytes: 14 bits é maior que 8 e menor que 17, então só pode caber em 2 bytes.

Não parece, mas a rotina é muito simples. Deixo pra você implementá-la. Só tome cuidado com uma coisa: zerar os bits superiores que não nos interessam! :)

“Ahhh! Eu sei de um jeito mais rápido, Fred!”

É mesmo… também sei! Afinal, mesmo que você esteja trabalhando no modo i386 (32 bits), pode também usar MMX (64 bits), SSE (128 bits), AVX (256 bits) ou, nos processadores mais modernos, AVX-512 (512 bits) de uma vez só, né? Perfeito! Mas imagine que tenha que manipular um bit string de 1920 bits (Full HD), ou 3840 (4k). A técnica acima, ainda assim, pode ser útil!

GCC: Que boa surpresa!

Bem… estou aqui me esgoelando para escrever um bom artigo sobre “Bit Block Transfers” e precisei efetuar rotações com grupos de bits. Em assembly é fácil: basta usar instruções como ROL e ROR, mas e em C?

Eu sei que os compiladores costumam usar um subconjunto das instruções disponíveis no processador e que, às vezes, isso leva a códigos menos que ótimos… Ainda, nos antigos Turbo C e Microsoft C 6.0, para MS-DOS, existiam as funções (não padronizadas) _rotl() e _rotr() para suprir a necessidade de realizar rotações de bits, coisa que não existe nos compiladores modernos (pelo menos eu não achei!).

Por padrão, C só disponibiliza os operadores << e >>, onde o shift para a direita, quando usado com tipos sinalizados, pode não funcionar como desejado (o comportamento é “dependente de implementação”, de acordo com as especificações da linguagem). Isso quer dizer que esse shift pode ser “lógico” ou “aritmético”, levando ou não em conta o sinal do valor sendo deslocado. Neste caso não há problemas: Basta sembre usar tipos não sinalizados… Mas, lembre-se, shift não é “rotação” e portanto, temos que usar um macete.

Fiz uma comparação das duas rotinas abaixo, usando o GCC 5.2:

unsigned int rotate_right(unsigned int data, int bits)
{
  return (data >> bits) |        // desloca para direita,
         (data << (32 - bits));  // zerand bits superiores e
                                 // desloca para esquerda,
                                 // zerando bits inferiores e
                                 // junta tudo com OR.
}

unsigned int rotate_right_asm(unsigned int data, int bits)
{
  __asm__ __volatile__ (
    "rorl %%cl,%0"
    : "+rm" (data) : "c" (bits)
  );

  return data;
}

A primeira, rotate_right() faz a rotação na marra! A segunda, obviamente, usa a instrução ROR. Bem… qual foi a surpresa? Essa aqui, ó:

$ cc -O2 -c -o test.o test.c
$ objdump -SM intel test.o
...
Disassembly of section .text:

0000000000000000 : 
   0:	89 f8                	mov    eax,edi
   2:	89 f1                	mov    ecx,esi
   4:	d3 c8                	ror    eax,cl
   6:	c3                   	ret    

0000000000000010 : 
  10:	89 f8                	mov    eax,edi
  12:	89 f1                	mov    ecx,esi
  14:	d3 c8                	ror    eax,cl
  16:	c3                   	ret    

O compilador é esperto o suficiente para perceber que eu queria fazer uma rotação de bits!! Viva o GCC!

Ahhh, sim… testei também com o clang 3.8. A rotina em C ficou semelhante a que foi mostrada acima, com uma coisa estranha (mostro abaixo), mas a rotina em assembly inline ficou pior!

$ clang -O2 -c -o test.o test.c
$ objdump -SM intel test.o
...
Disassembly of section .text:

0000000000000000 : 
   0:	40 88 f1             	mov    cl,sil
   3:	d3 cf                	ror    edi,cl
   5:	89 f8                	mov    eax,edi
   7:	c3                   	ret    

0000000000000010 : 
  10:	89 7c 24 fc          	mov    DWORD PTR [rsp-0x4],edi
  14:	89 f1                	mov    ecx,esi
  16:	d3 cf                	ror    edi,cl
  18:	89 7c 24 fc          	mov    DWORD PTR [rsp-0x4],edi
  1c:	89 f8                	mov    eax,edi
  1e:	c3                   	ret

Quanto a rotina em C, por que diabos o clang resolveu inicializar o CL ao invés de ECX? Mesmo que ROR só vá usar CL, copiar ESI para ECX é mais rápido do que fazer a mesma coisa necessitando de um prefixo REX na instrução! E, mesmo que não seja mais “rápido” (supondo que o prefixo REX não adicione 1 ciclo de clock extra), a função ficou maior que o necessário!

No caso da rotina escrita em assembly inline, por que diabos o clang está salvando EDI na pilha duas vezes? Mesmo porque o conteúdo de EDI não vai ser reaproveitado!!!

Mau, clang! Feio!

Serigrafia no computador: Stencil Buffer

Você já viu como fazem aquelas camisetas com estampas desenhadas? Usa-se um filtro onde a tinta passa ou não por poros de uma malha muito fina. Nos poros onde a tinta passa ela é absorvida pelo tecido da camisa, onde não passa, ela é mascarada e fica na malha. Eis um exemplo de confecção de placa de circuito impresso pelo método serigráfico:

Serigrafia, usada para criar a máscara que não será corroída numa PCB

Na foto, a parte amarela da “malha” ou “tela” deixa passar a tinta, a parte verde, não deixa. A tinta, é claro, está do lado de lá do aplicador, sendo arrastada sobre a superfície da “malha”…

Mas, o que diabos isso tem a ver com “computação gráfica” fora a palavra “gráfica”?

A maneira de implementar o método serigráfico num computador é criando um buffer onde cada bit equivale ao “deixa passar” ou “não deixa passar” da malha que será exposta à tinta. A tinta, neste caso é um pixel, que “passará” ou não pelo teste do bit (1, deixa passar, 0, não deixa).

Considere que você tem uma tela de 1280 por 720 pixels. Se cada bit é um filtro para um único pixel, então o buffer “stencil” (é assim que gringos chamam o processo serigráfico) poderia ser composto de 1280 por 720 bits. 1280 bits por linha dá 160 bytes por linha, o que nos dá 115200 bytes para a tela inteira (que no formato RGBA terá pouco mais de 3,5 MiB. Ou seja, o stencil buffer terá apenas cerca de 3% do tamanho da tela real).

Considerando que cada byte do stencil buffer está associado a 8 pixels e o bit zero está associado ao pixel onde x=0, na linha corrente, então, nessa resolução gráfica, para achar o bit correspondente da posição (x,y) da tela, basta fazer:

  // divide x por 8 para obter o offset da linha.
  size_t offset = (size_t)x >> 3;

  // Obtem o resto da divisão por 8 para obter o 
  // bit correspondente.
  size_t bit = 1 << (x & 7);

  // stencilbase é o ponteiro para o stencil buffer bitmap.
  // stencilwidth é o comprimento, em bytes, de cada linha.
  char *stencilp = (char *)stencilbase +
                      (stencilwidth*y) + offset;

  // basta agora testar o bit para decidir se devemos ou 
  // não modificar o pixel.
  if (*stencilp & bit) 
    setpixel(x,y,color);

Essa pequena rotina poderia ser chamada de stencil_setpixel(), onde passaríamos, pelo menos, o ponteiro para uma estrutura contendo os dados do stencil, as coordenadas (x,y) e a cor do pixel.

Note que esse método só tem um problema: Para ele funcionar, o comprimento (width) do buffer tem que ser, sempre, múltiplo de 8. Se o comprimento não for múltiplo de 8 podemos complementá-lo com bits zerados, considere um retângulo de 70 por 70 pixels. Teremos 70 linhas e isso não é problema, mas 70 não é múltiplo de 8… Teremos que colocar 00 nos dois últimos bits do último byte da linha (que terá 9 bytes por linha: 9\cdot8=72).

Eis um exemplo de uso de stencil buffers, mas para partes da tela. Por exemplo, no auxílio de desenho de janelas com bordas não retangulares:

Pequeno stencil para uma janela de 320×200 pixels

Deixei uma borda preta de 1 pixel de tamanho em cada canto dessa imagem para que ela ficasse perfeitamente visível contra o fundo branco deste blog. Essas linhas não existem neste stencil de exemplo… E esse meu stencil também é de baixa resolução porque quero mostrá-lo para vocẽ (por isso a “ampliação” central)… Neste caso ai, o stencil será usado numa área retangular de 320 por 200 pixels e os bits 0 (pretos) simplesmente não alterarão a cor do “fundo” dessa área… toda a área “branca” (bits setados) será afetada pelos pixels correspondentes da imagem original…

Vale lembrar que isso ai não é uma “transparência”, já que este outro efeito exige uma “mistura” (blending) de cores e é para isso que existe o canal alpha no esquema RGBA de cores. O stencil é somente uma máscara de bits… uma “máscara” que mais mostra do que esconde, neste caso em particular.

No desenho acima fiz, propositalmente, o zoom do canto superior direito e o separei em um bloco de 16 por 16 bits… Note que não precisamos, em certos casos, do stencil buffer inteiro. Numa janela retangular poderíamos aplicar stencils apenas aos cantos para arredondá-los e o restanet da área seria desenhada sem passar por essa filtragem. É claro, vale a pena limitar os tamanhos horizontal e vertical mínimos para qualquer janela para que isso funciona… Neste caso, nossa janela jamais poderia ter tamanho menor que 32 por 32 pixels, por causa dos 4 cantos…