Complemento 1 e a mudança do ponto “zero”

“Complemento 2” não é a única forma de “fazer de conta” que um valor inteiro, do conjunto dos números naturais, tem sinal. De fato, a primeira tentativa de usar “sinais” em aritmética binária foi, ao observar que o bit MSB poderia ser usado como “sinal”, usar o inverso dos bits para especificar o valor sinalizado. Em oposição à noção de “complemento 2”, isso ficou conhecido como “complemento 1″… Eis um exemplo de como funciona:

Se, com 4 bits (por exemplo), 0b0001 equivale ao valor +1, em decimal, invertendo os bits obteríamos 0b1110 que, tendo o MSB setado, “representa” um valor negativo do número natural 1.

Rapidamente essa maneira demonstrou-se ruim por dois motivos:

  1. Ao fazer a soma de +1 com -1 obtém-se 0b1111 (0b0001 + 0b1110);
  2. Ao inverter todos os bits de zero (0b0000), obtém-se 0b1111.

O segundo fato implica que temos dois valores “zero”: +0 e -0. Um com o MSB zerado e outro com o MSB setado. O que é meio estranho e, ainda, 4 bits nos daria a sequência sinalizada simétrica de -7 até +7, mas com dois “zeros” e criaria um problema: Ao subtrair 1 de +0 teríamos -0, ao invés de -1 e, de forma similar, ao adicionar 1 a -0 obteríamos +0.

Assim, o “complemento 1” foi abandonado e só existe para fins lógicos, com valores não sinalizados.

Retornando a faixa dos valores não sinalizados de 4 bits, outra forma de “fazer de conta” que temos sinal é mudando o ponto onde o valor zero se encontra. Note que, com 4 bits, temos valores de 0b0000 até 0b1111, sem sinal. ou seja, 16 combinações binárias que podem ser divididas em dois subconjuntos com 8 elementos cada. O que acontece se dissermos que 0b0111 é o novo “zero”? Ou seja, se v=N-V_{bias}, onde V_{bias} é o valor do meio da faixa (no caso, 7) e N seja o valor inteiro sem sinal que resultará num valor v com sinal. Neste caso, se N=0 obteremos -7, mas se N=15 (valor máximo sem sinal com 4 bits), obteremos 8.

Só para constar: bias, em inglês, é “polarização”. A ideia é que ao adotar esse novo valor “centralizador” estamos dividindo a faixa dos valores inteiros sem sinal em dois “polos” (um negativo e um positivo)…

Por que fazemos V_{bias}=7? Ora, porque se N_{max}=15, o meio da faixa é exatamente N=\left\lfloor\frac{N_{max}}{2}\right\rfloor. Note que, desse jeito, a assimetria dos valores extremos é a inversa da que ocorre no “complemento 2” (o valor positivo máximo é maior que o valor negativo mínimo). Fora isso, todo o resto funciona perfeitamente bem… Se subtrairmos 1 de 0 (que agora é 0b0111), obteremos N=6 (sem sinal), que é -1, com sinal (v=6-7=-1). Ou seja, em toda a faixa continuaremos a ter apenas um zero.

Esse esquema é usado no fator de escala de um valor em ponto flutuante (o expoente e, da equação v=(1+f)\cdot2^E), onde E=e-v_{bias} e e é um valor inteiro sem sinal… Como expliquei em outro artigo, f é uma fração do tipo f=\frac{F}{2^k}, onde F e k são inteiros e k depende da precisão (em bits) da parte fracionária.

Neste caso, o valor superior de e (e_{max}) é usado para expressar valores “não numéricos” (NaN e infinitos), tornando a faixa dos expoentes simétrica para todos os outros valores (adotando também um caso especial, quando e=0, é o menor expoente negativo possível (E), correspondendo à uma escala fixa para valores subnormais)…

De fato, podemos usar qualquer valor para V_{bias} que esteja dentro da faixa permissível para a quantidade de bits em questão, causando apenas uma assimetria maior entre os valores positivos e negativos, mas a aritmética continua perfeitamente válida. Se V_{bias}=0, teremos o zero e somente o polo positivo, mas se V_{bias}=15, teremos o polo negativo, onde o maior valor é o zero!

O último aviso, que acredito que tenha ficado óbvio, é que estou usando apenas 4 bits como exemplo aqui para ficar visualmente mais fácil. O número de bits estipula tanto N quanto V_{bias}.

Anúncios

Uma outra forma de explicar o “complemento 2”

Yep! Vira e mexe eu volto aos temas mais fundamentais. Eis-me aqui, de novo, falando de aritmética inteira binária pra você… Vou tentar explicar, de novo, mas de uma outra forma, o que significa usar “sinais” em valores binários inteiros e, para isso, vou recorrer à base numérica decimal. Aquela mesma a qual estamos mais que acostumados.

Números são representações simbólicas de quantidades e, portanto, não têm “sinal”. Você consegue contar 3 coisas (para citar um exemplo de quantidade), mas não consegue contar -3 coisas. O sinal ‘-‘ ai é usado para adicionar um sentido à quantidade. Pode ser que o sentido seja que “faltam” 3 coisas ou que você queira dizer 3, mas no sentido contrário ao convencional. No último caso a representação é relativa a algum ponto tomado como origem… O fato é que você adicionou o sinal ‘-‘ para colocar um sentido extra à quantidade 3. Isso significa que essa qualidade é “artificial”, em relação à quantidade de coisas… Ainda mais: significa que esse símbolo adicional complementa o significado da quantidade (lembre-se dessa palavra!).

No sistema decimal isso é fácil fazer, especialmente quando você se acostuma com o conceito de “menos” (de falta ou “sentido contrário”), mas a coisa é mais difícil quando estamos falando de representações de valores no interior de um computador… Por exemplo, poderíamos ter bits  sinalizados se usássemos 3 níveis de tensão, por exemplo, +5 V, 0 e -5V. A tensão mais alta corresponderia a ‘1’ e a mais baixa a ‘-1’, mas, neste caso, deixaríamos de ter uma base binária para trabalharmos com um sistema ternário porque 3 níveis em cada “algarismo” caracteriza um sistema de base 3… Existe também um outro problema em usar a simbologia do ‘+’ ou ‘-‘: No sistema decimal podemos escrever a quantidade do tamanho que quisermos, se tivermos paciência e tempo, e só colocarmos o sinal ‘-‘ na frente para “inverter o sentido” do valor. Num computador, a quantidade de bits disponíveis para operações aritméticas é limitado. Então, em binário, em termos de circuitos eletrônicos, não dá para usar 3 níveis e também não dá para representar um valor indefinidamente. Um bit não pode ser “negativo” (em oposição a um “positivo”) e não podemos ter tantos bits quanto quisermos. É nesse sentido que sempre digo que não existem valores inteiros negativos em binário.

Acontece que precisamos, em certos casos, representar valores binários como se fossem negativos. Ao invés de usarmos um símbolo especial como ‘-‘ para isso usamos um bit extra… Por exemplo, com um único bit podemos representar apenas dois valores: 0 e 1. Mas, se usarmos 2 bits e fizermos de conta que o bit de mais alta ordem nos diz se o valor é positivo ou negativo, então temos a nossa representação sinalizada de um valor… Por convenção, se esse bit extra for 0, o outro bit representa um valor positivo (0b01 representa o valor +1), mas se esse bit extra for 1, então o outro bit representa um valor negativo (0b11 representa -1). É como se o último bit fosse + ou -. Mas há um problema ai…

E se tivermos uma quantidade maior de bits? O que significa 0b1111 (para citar um exemplo com apenas 4 bits) em termos de valor sinalizado? Se usarmos a definição simples de que o bit de alta ordem significa ‘-‘ e os demais bits nos dão o valor, esse exemplo deveria representar -7. Mas ele, de fato, representa -1. O bit de alta ordem complementa o significado do valor adicionando -2^N ao valor dos bits inferiores (no caso N=3, que corresponde à posição do bit “de sinal”, no valor). Ou seja, 0b1111 é convertido para decimal realizando a operação -2^3+(2^2+2^1+2^0)=-8+7=-1. Note que, no caso de usarmos 2 bits apenas, o complemento é -2. Então 0b11 é calculado como -2+1=-1… Se o bit de alta ordem for zero, o complemento simplesmente não é adicionado ao valor. Repare que, -2 é o valor 2 com a complementação ‘-‘ na frente, em decimal. Acredito que daí aparece o termo “complemento 2”.

Outra explicação interessante é o do porquê do “macete” de inverter os bits e somar 1 se o último bit estiver setado, para obtermos a representação do valor como se fosse negativo. Note que, com dois bits, temos o conjunto de valores binários B={0b00, 0b01, 0b10, 0b11} que pode ser dividido em dois subconjuntos (P=\{0b00,0b01\} e M=\{0b10,0b11\}, onde B=P\cup M (dei o nome dos subconjuntos de P e M para significarem Plus e Minus, o conjunto B é dos Bits). O conjunto B é assimétrico no que se refere aos valores extremos! Do lado positivo temos, em decimal, 0 e +1, e do lado negativo, -1 e -2. Isso quer dizer que o valor -2 não pode ser “espelhado” para obtermos a representação “positiva” +2, usando apenas dois bits. Quer dizer mais ainda: temos 1 quantidade a mais do lado negativo. Assim, para obtermos -1 à partir de 1, já que temos uma quantidade extra do lado negativo, temos que “somar um” à inversão dos bits (“menos” 0b01 é o seu inverso, 0b10,  “mais 1”). No sentido contrário teremos que “tirar” esse um que colocamos, “somando” +1 ao valor negativo (x-(-1)=x+1)… Essa é a origem do “macete”.

Minha ideia com o MyToyOS…

“Fred, cadê o MyToyOS?” — Well… minha ideia com o projeto, desde o início, é não seguir padrões pré definidos, na medida do possível. Algumas coisas são necessárias por questões do hardware (chipsets, processadores) e a necessidade de aproveitar alguns recursos que “facilitam” (UEFI, por exemplo). Neste aspecto, eu não quero implementar um filesystem tradicional (FAT, por exemplo), não quero usar formatos pré-definidos de particionamento de discos (embora tenda para o formato GPT) e sequer o mapa de memória tradicional, a não ser que seja delimitado pelo hardware.

O lance do UEFI deve-se ao fato de que, provavelmente, daqui a alguns anos o bootstrap, via INT 0x18, estará extinto. Se não fosse isso eu ficaria com a carga da MBR como ponto inicial.

O MyToyOS é um daqueles projetos que, possivelmente, jamais sairá dos testes porque a carga de estudos e de trabalho é enorme, já que eu quero não depender de padrões. Isso não significa que não tenha que estudá-los.

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?

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…