Como funciona a aritmética fundamental em ponto flutuante

Quando falamos em aritmética fundamental usando valores inteiros (adição, subtração, multiplicação e divisão) acredito que não há grandes dúvidas, quando os argumentos estão expressos em formato binário. Mas, e quanto à codificação em ponto flutuante que citei em artigos anteriores?

Adição e subtração

O problema que enfrentamos é que, além dos bits significativos, temos o escalonamento (ou o “deslocamento” do ponto). Na adição precisamos que ambos os valores tenham a mesma escala para poder adicioná-los. Um exemplo, em decimal, é a tentativa de adicionar 1.0\cdot10^0 ao valor 1.0\cdot10^2. Não podemos, simplesmente, somar 1.0 com 1.0! Temos que tornar as escalas (10^0 e 10^2) iguais e, para isso, adaptamos o menor valor:

\displaystyle 1.0\cdot10^2 + 0.01\cdot10^2=1.01\cdot10^0

Aqui, 1.0\cdot10^0 foi transformado em 0.01\cdot10^2. O motivo de adequarmos o menor valor é que os bits do menor valor serão deslocados para a direita e a adição tenderá a obter uma soma normalizada. Troque agora o valor normalizado por um valor inteiro binário (com o bit 23, implícito, setado) e a escala na base 2, ao invés de 10… Lembre-se que, no artigo anterior, demonstrei que o valor contido na “fração” da estrutura de um float é o valor inteiro do numerador, cujo denominador é sempre o mesmo, 2^{23}.

Embora esteja mostrando o funcionamento do ponto de vista de um valor fracionário, o coprocessador realiza a adição com o valor inteiro. Usando o programinha shwflt, do artigo anterior, temos:

$ ./shwflt 1e0
[Normal] 1 -> s=+, E=0, f=0 (0b1.00000000000000000000000)
$ ./shwflt 1e2
[Normal] 100 -> s=+, E=6, f=0x480000 (0b1.10010000000000000000000)

Consideremos a=1.0\cdot10^2 e b=1.0\cdot10^0. Com o procedimento descrito acima, temos que a>b e, portanto, b deve ser adequado. Em binário, considerando apenas as frações e o bit implícito, temos, em binário, a=0b110010000000000000000000 e b=0b100000000000000000000000, mas b deve ser deslocado 6 bits para a direita para que os expoentes sejam equalizados (E_a=E_b) e, portanto, b=0b000000100000000000000000. A adição das frações, então, dá a+b=0b110010100000000000000000 e o resultado final, na estrutura do float será f=0b10010100000000000000000,\,E=6, como pode ser visto aqui:

$ ./shwflt 1.01e2
[Normal] 101 -> s=+, E=6, f=0x4a0000 (0b1.10010100000000000000000)

Existe um detalhe interessante: Se a diferença entre os expoentes E_a e E_b for maior que 24, significa que o menor valor pode ser seguramente desconsiderado na adição. O motivo, óbvio, é que ele deverá ser deslocado 24 bits para a direita, fazendo com que todos os seus bits significativos “desapareçam”. Assim, a adição só é feita se E_a - E_b < 24 onde E_a > E_b.

A subtração segue as mesmas regras, mas a ordem com a qual os operandos aparecem é importante.

Renormalização

Consideremos o caso de adicionarmos o valor fracionário, binário, 0b1.0 a ele mesmo. Teremos que obter o valor 2.0 ou 0b10.0. No entanto o bit MSB é implícito e precisa estar isolado da parte fracionária. Por isso, na adição, precisamos ter espaço suficiente para o armazenamento para um bit extra à esquerda, no valor inteiro. Ou seja, o resultado por ter 25 bits de tamanho: Assim, se R=0x800000+0x800000=0x1000000, o valor de R precisa ser deslocado 1 bit para a direita (R\text{ shr }1 e o expoente E é incrementado. Vejamos:

$ ./shwflt 2
[Normal] 2 -> s=+, E=1, f=0 (0b1.00000000000000000000000)

Repare que f=0, do mesmo jeito que acontece com o valor 1.0, mas o expoente E=1 por causa da renormalização.

Da mesma forma, isso também pode ocorrer com a subtração. O MSB sempre tem que ser igual a 0b1, a não ser que obtenhamos um valor subnormal. Se o MSB obtido for zero o valor final será deslocado para a esquerda tantos bits quantos forem necessários para que ele seja igual a 0b1, mas o expoente E, do resultado, será subtraído dessa mesma quantidade de bits, normalizando o valor. Se o coprocessador perceber que E será menor que -126, então o valor é subnormal e a renormalização não é feita.

Multiplicação e divisão

Diferente da adição (e da subtração), a multiplicação não precisa sofrer adequações das frações. Isso fica claro quando você percebe que basta somar os dois expoentes de mesma base para obter a escala correta e, as frações, só precisam ser multiplicadas:

\displaystyle (f_a\cdot2^{E_a})\cdot(f_b\cdot2^{E_b}) = (f_a\cdot f_b)\cdot2^{E_a + E_b}

O detalhe é que, ao obtermos a fração com o bit implícito, teremos um valor de 24 bits de tamanho que, ao multiplicar por outro valor de 24 bits de tamanho nos dará um valor de 48 bits de tamanho. Considere o caso de multiplicarmos 1.0 por ele mesmo. Esse valor é codificado, em hexadecimal, como 0x800000. Depois da multiplicação obtemos 0x400000000000. Não é óbvio, mas o resultado encontra-se 23 bits deslocado para a esquerda, ou seja, justamente os 23 bits da parte fracionária dos argumentos originais! A resposta é justamente \left[(a\cdot b)\text{ shr }23\right]\cdot2^{E_a+E_b}, onde a e b são os valores inteiros de 24 bits com o bit implícito!

A divisão, é claro, segue o sentido inverso. os bits significativos devem ser divididos e os expoentes subtraídos, mas diferente da multiplicação, o dividendo deve ser deslocado 23 bits para a esquerda antes que a divisão possa ser feita. Novamente, vamos tentar dividir 1.0 por ele mesmo… Se dividirmos 0x800000 por ele mesmo obteremos o quociente 1. Mas 1 é apenas o bit 0 da fração, ou seja, 2^{-23}. Mas, se deslocarmos a para esquerda em 23 bits, teremos \frac{0x400000000000}{0x800000}=0x800000. Assim, a divisão binária fica \frac{a\text{ shl }23}{b}\cdot2^{E_a-E_b}. Claro que temos que considerar o caso espacial onde $label b=0$.

Atenção que a renormalização também pode ser necessária depois de multiplicações e divisões. Tomemos o caso onde todos os bits significativos estejam setados e E=0. Se quisermos elevar esse valor ao quadrado, neste caso, a será 0xffffff e obteremos 0xfffffe000001. Ao deslocarmos 23 bits para a direita teremos 0x1fffffc, que tem 25 bits de tamanho! Isso deve ser deslocado em 1 bit para a direita e o valor de E incrementado. De fato, o programinha abaixo atesta esse fato:

#include <stdio.h>

union flt_u {
  float v;
  struct {
    unsigned int f:23;
    unsigned int e:8;
    unsigned int s:1;
  };
};

void main(void)
{
  /* Todos os bits significativos setados.
     E=0. 
     s=+ */
  union flt_u flt = { f:~0, e:127 };

  float b;

  b = flt.v * flt.v;

  printf("a = %.18f, a*a = %.18f, "
         "f[a*a]=%#x, E[a*a]=%d\n",
    flt.v,
    b,
    (*(union flt_u *)&b).f,
    (*(union flt_u *)&b).e-127);
}

Ao executar o código acima, temos:

a = 1.999999880790710449, a*a = 3.999999523162841797, f[a*a]=0x7ffffe, E[a*a]=1

Como os dois valores originais tẽm expoente zerado, o expoente final deveria ser zerado também (E_a+E_b=0+0=0, mas a renormalização nos deu um expoente unitário, sendo fácil perceber que a parte fracionária é resultante do shift para a direita do valor que expus anteriormente. Na divisão algo similar pode acontecer, mas no sentido contrário.

Underflows. overflows e NaNs

O que acontece se tivermos f_a com todos os bits setados e E_a=127 (o maior expoente possível em base 2), pegarmos esse valor máximo e adicionarmos 2^{104}? O valor 2^{104} é precisamente o bit 0 da estrutura do float com um expoente 127. O que ocorrerá que o coprocessador fará o cálculo, mas obterá um valor “estranho” com expoente 128 que, por definição do padrão, corresponde a ∞ ou a NaN. No caso da adição, ao ocorrer um overflow termos o resultado ±∞, dependendo do sinal. Mas, divisões podem causar resultados NaN. É o caso da divisão \frac{0}{0}.

Ao obter, no resultado, um expoente maior que 127 ou menor que -127 (para valores subnormais) o coprocessador decide o que vai deixar na fração… Se o valor for “infinito”, a fração será zerada. Se for um NaN, geralmente temos algum “lixo” armazenado por lá… O bit 22 será 0 se tivermos um qNaN e 1 se tivermos um sNaN, mas não podemos usar os demais bits para qualquer coisa, senão forçarmos um NaN (para o caso do qNaN).

Parece “ponto fixo”, não é?

Não sei se escrevi algo sobre ponto fixo neste blog (espero que sim, me avisem caso contrário, ok?), mas esse esquema de usarmos os bits significativos como se fossem valores inteiros lembra muito a maneira como ponto fixo funciona, com uma grande vantagem: Se dividirmos os 32 bits em partes iguais entre o componente inteiro e o fracionário poderemos, em ponto fixo, expressar o valor mínimo de 2^{-16} e o máximo de \frac{2^{32} - 1}{2^{16}}. Ponto flutuante, do mesmo tamanho, em contrapartida, nos garante a faixa entre o valor mínimo subnormal de 2^{-149}\approx1.4\cdot10^{-45} até o máximo de \frac{2^{25} - 1}{2^{23}}\cdot2^{127}\approx6.8\cdot10^{38}. Uma faixa bem maior e com maior precisão usando menos bits significativos (apenas 24).

Note que, para ser exato, os 32 bits de um ponto fixo deveriam ser divididos em 31 bits significativos e um de sinal. E, no neste caso, é comum usarmos o bit de sinal para conter valores inteiros em complemento 2, coisa que não é feita com ponto flutuante. Os bits significativos, neste último caso, são sempre armazenados de forma positiva. Fica a cargo dos algoritmos determinar se, por exemplo, estamos realizando operações com valores com sinais iguais ou diferentes, o que adiciona alguma complexidade (pouca!). E, é claro, o padrão IEEE 754 ainda fornece alguns valores especiais, o que não é diretamente possível com ponto fixo.

Mais alguns detalhes sobre ponto flutuante

Tenho escrito sobre ponto flutuante aqui para alertar aos desavisados de que realizar cálculos com esses tipos não é a mesma coisa que lidar com números “reais”, na matemática tradicional. Realmente, espero que esses textos criem a consciência de que nem tudo é tão simples quanto parece.

Neste texto vou tentar esmiuçar alguns detalhes adicionais sobre a estrutura do tipo float, usado na linguagem C ou, mais precisamente, do tipo single precision, como especificado no padrão IEEE 754. A discussão, claro, aplica-se aos outros tipos (double precision e extended double precision, bem como às “novos” tipos descritos na revisão de 2008 da referida especificação).

Lembrando sobre a estrutura de um float:

O tipo float, ou single precision, tem 32 bits de tamanho e a seguinte estrutura:

Estrutura de um float

O valor decimal, normalizado, codificado nessa estrutura, é obtido através da equação abaixo:

\displaystyle v=(-1)^s\cdot\left(1+f\right)\cdot2^e

Onde s corresponde ao bit de sinal (0 significa + e 1, -); o valor f é uma “fração”, ou seja, um valor entre 0 e 1 (0\leqslant f<1). Repare que ao valor de f adicionamos o valor 1 que não está presente na estrutura acima. Esse valor é implícito e segue a regra daquilo que é conhecido como notação científica, onde o primeiro algarismo significativo deve sempre maior que zero e ser o único algarismo “inteiro”. No caso de valores binários não temos alternativa a não ser usarmos o algarismo 1.

O componente e é o expoente do escalonamento que indica para que lado o “ponto” flutuará. Valores positivos fazem o ponto flutuar para a direita e negativos, para a esquerda. O expoente e merece alguma atenção, já que ele é codificado de forma “polarizada” (biased), onde o valor central, zero, com os 8 bits disponíveis, corresponde a 127 (ou 0b01111111, em binário). Daqui por diante usarei nomenclatura maiúscula para expressar o expoente “real” da escala, de acordo com a equação: E=e-127 e quando vir o expoente e, minúsculo, trata-se do valor armazenado na estrutura do float.

Porque chamamos os bits significativos de “fração”?

Era comum vermos, na literatura especializada, o fragmento (1+f) ser chamado de “mantissa”, mas essa nomenclatura está errada. Não porque o uso do termo seja mais comum com logaritmos, mas porque ela significa “a parte quebrada ou excedente”, ou seja, justamente a parte fracionária, excluindo o componente inteiro. Isso poderia ser aplicado apenas ao compoennte f, mas é preferível chamar (1+f) de bits significativos e o componente f de “fração”.

O termo “fração” é apropriado. Como o valor expresso na estrutura é binário, podemos simplesmente “deslocar a vírgula” 23 bits para a direita e obtermos um valor inteiro. Isso quer dizer que o valor expresso nos bits significativos é, de facto, um número inteiro que compõe uma fração somada a uma unidade:

v=(-1)^s\cdot\left(1 + \frac{n}{2^{23}}\right)\cdot2^E

O valor 2^{23} no denominador vem do fato de que f sempre será menor que 1 e essa é quantidade máxima de arranjos binários possíveis para esse campo.

Como a fração é obtida?

Graças ao MSB, implícito nos bits significativos, o valor inteiro 1.0 é expresso simplesmente como (1+0), mas se fossemos usar todos os 24 bits significativos ele seria expresso como 0x800000 ou 8388608. Se queremos converter um valor d, decimal, para a base binária (num valor b) que contenha o MSB implícito, podemos fazer:

\displaystyle f=\frac{n}{2^{23}}\,\therefore\,n=f\cdot2^{23}

Vou usar o programinha abaixo para mostrar a estrutura de um float. Isso nos auxiliará a corroborar a alegação acima.

/* shwflt.c */
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

/* Usada para decompor um float
   em seus componentes. */
union float_u {
  float v;
  struct {
    unsigned int f:23;
    unsigned int e:8;
    unsigned int s:1;
  };
};

/* Retorna string com os 23 
   bits em binário. */
static char *binfrac(unsigned int f)
{
  static char bits[24];
  char *p;
  int i;

  p = bits;
  i = 23;
  while (i--)
  {
    /* Isola o bit 22 */
    *p++ = (f & (1U << 22)) ? '1' : '0';
    f <<= 1;
  }

  /* fim da string. */
  *p = 0;

  return bits;
}

int main(int argc, char *argv[])
{
  union float_u flt;
  char sign;

  /* Precisamos de 1 argumento */
  if (!*++argv)
  {
    puts("Usage:\n"
         "  shwflt <value>");
    return 1;
  }

  errno = 0;
  flt.v = strtof(*argv, NULL);
  if (errno == ERANGE)
  {
    fprintf(stderr, 
            "ERROR: Invalid value: '%s'\n",
            *argv);
    return 1;
  }

  sign = flt.s ? '-' : '+';

  /* NaN ou Infinito? */
  if (flt.e == 255)
  {
    if (!flt.f)
      printf("%c\xe2\x88\x9e", sign); /* utf-8 */
    else
      printf("%cNaN\n", sign);

    return 0;
  }

  /* Valor normalizado? */
  if (flt.e)
  {
    printf("[Normal] %.8g -> "
           "s=%c, E=%d, f=%#x (0b1.%s)\n",
      flt.v,
      sign,
      flt.e-127,
      flt.f,
      binfrac(flt.f));
  }
  else
  {
    printf("[SubNormal] %.8g -> "
           "s=%c, E=-126, f=%#x (0b0.%s)\n",
      flt.v,
      sign,
      flt.f,
      binfrac(flt.f));
  }

  return 0;
}

Tomemos o valor 1.0 como exemplo: Temos b=1.0\cdot2^{23} ou, em binário, 0b100000000000000000000000. Esse número binário tem exatamente 24 bits de tamanho na sua parte inteira e, então, não há necessidade de escalonar a fração (deslocar o “ponto”, lembra?):

./shwflt 1
[Normal] 1 -> s=+, E=0, f=0 (0b1.00000000000000000000000)

Note que O 24º bit é, como comentei antes, implícito e, portanto, não aparece no componente f. Ele é indicado aqui como “0b1.”. Outro ponto digno de nota é que estou multiplicando o valor decimal “real” por 2^{23}, ao invés de apenas a fração. Isso pode ser feito porque, de qualquer maneira, vamos descartar o 24º bit.

Consideremos, agora, o valor 0.1: Temos 0.1\cdot2^{23} ou, em binário, 0b11001100110011001100.11, que tem apenas 20 bits na parte inteira. Esse valor, normalizado e limitado a 24 bits, acabará sendo 0b1.10011001100110011001100_1. O bit extra, mais à direita (depois do separador ‘_’), é chamado de bit de guarda, usado no arredondamento. Ele deve ser somado ao LSB do valor binário normalizado (é o equivalente a somar 0,5 a um valor com “uma casa decimal” para obter o valor inteiro mais próximo). Assim, o valor de f será 0b10011001100110011001101 ou, em hexadecimal, 0x4ccccd.

$ ./shwflt 0.1
[Normal] 0.1 -> s=+, E=-4, f=0x4ccccd (0b1.10011001100110011001101)

Voltando ao fato do valor binário obtido ter 20 bits na sua parte inteira, isso significa que temos que deslocar o ponto 4 bits para a direita. Ou seja, o valor real é 0b0.000110011001100110011001100…. Temos, então E=-4, aplicado ao valor normalizado. Então, a estrutura do valor 0.1 num float nos dá: v=(-1)^0\cdot\left(1+\frac{5033165}{8388608}\right)\cdot2^{-4}\approx0.1.

Outro exemplo: Vamos ver como fica o valor aproximado de π (3.141593):

./shwflt 3.141593
[Normal] 3.141593 -> s=+, E=1, f=0x490fdc (0b1.10010010000111111011100)

De acordo com nosso esquema, n=3.141593\cdot2^{23}, ou seja:

0b1100100100001111110111000.00101100001010111101

A parte inteira tem 25 bits e os primeiros 24 podem ser normalizados (e arredondados), obtendo 0b1.10010010000111111011100. Além disso, se temos 25 bits no valor original, isso significa que precisaremos adicionar 1 bit extra à esquerda do valor inteiro. Assim, E=1 e f=0x499fdc, exatamente como esperávamos. Isso nos dá v=(-1)^0\cdot\left(1+\frac{4788188}{8388608}\right)\cdot2^1\approx3.141593.

Minha trapaça e o que falta…

Como consegui obter a representação fracionária dos valores decimais em binário? Eu trapaceei… Fiz uso do Big number Calculator (bc):

$ bc
obase=2

0.1*(2^23)
11001100110011001100.1100

10*(2^23)
101000000000000000000000000

3.141593*(2^23)
1100100100001111110111000.00101100001010111101

A multiplicação por 2^{23} serve apenas para obtermos o valor inteiro que será colocado no componente f do valor em ponto flutuante, para o tipo float, onde devemos excluir o MSB.

Isso é uma “trapaça” no sentido de que estou usando um software que converte o valor fracionário corretamente para nós. Na prática, não deveria usar esse tipo de auxílio e te mostrar como os valores fracionários são obtidos através de operações elementares usando valores inteiros apenas (suponha que o processador não tenha uma unidade de ponto flutuante, como é o caso dos antigos 386).

Sinto dizer, mas existe outra trapaça ai… O valor binário obtido tem tamanho arbitrário e, na prática, temos apenas uma quantidade de bits limitada para trabalhar. Nos processadores Intel modernos temos registradores de até 64 bits de tamanho e, se usarmos AVX, podemos chegar até 256 bits. Lembre-se que o valor binário final pode ser escalonado até 2^{126}, ou seja, além dos 24 bits significativos, podemos ter até 127 bits adicionais, totalizando 151 bits (para valores normalizados)… E olha que estou falando apenas do tipo float… Com o tipo double, que tem 53 bits significativos e o expoente E pode chegar até 1023, o que nos dá um total de 1080 bits. Muito além até mesmo do AVX-512, que não está disponível em todos os processadores modernos.

Isso significa que aritmética de múltipla precisão não é usada nem mesmo pelo co-processador. As rotinas têm que levar em conta o tamanho dos registradores da arquitetura em questão e, ainda assim, serem o mais rápidas possíveis… Não discuti neste artigo como essas rotinas funcionam, mas o farei, em breve…

Ambientes gráficos – Não é tão simples como você pensa!

Um leitor amigo me pediu para falar um cadinho sobre ambientes gráficos. Infelizmente o assunto é tão extenso que é meio difícil cobrir aqui. Pretendo mostrar, superficialmente, uma técnica usada ma maioria das GUIs…

Já reparou como suas janelas são desenhadas na tela? Observe isso:

01-2-windows

Para os propósitos deste texto, esqueça os efeitos especiais como a sombra projetada da janela do terminal sobre a janela do browser e de ambas as janelas sobre o desktop.

A janela do browser, embaixo da do terminal, é parcialmente desenhada. O pedaço onde o terminal está não pode aparecer para o usuário (a não ser que você seja um daqueles que goste de usar terminais “transparentes”). No caso de janelas com conteúdos estáticos isso pode parecer bem simples de fazer. Mas, e quanto a vídeos?

Nada de dstrações com a beleza da moça!
Nada de distrações com a beleza da moça!

Vídeos são apenas sequências de imagens desenhadas em intervalos regulares para causar a sensação de movimento. No caso do vídeo da moça acima (linda, não?), o mesmo pedaço da janela, à esquerda, não é tocado pelas imagens que compõem o vídeo… Como isso é feito?

A GUI divide a janela sobreposta em “sub janelas” ou regiões. Ele faz isso porque só sabe manipular áreas retangulares e, então, a divisão em regiões da janela do vídeo fica assim:

grab3-2-regions

No exemplo acima usei as cores verde e azul para exemplificar a divisão da janela em regiões… Todos os pixels que não estão nessas áreas simplesmente não são desenhados. Mas, como fica quando temos várias janelas sobrepostas? A GUI monta uma lista de regiões retangulares, por exemplo:

03-3-regions

Aqui temos 3 “regiões” (verde, azul e vermelha).

Obviamente que quanto mais janelas na tela, mais complexa tende a ficar. Especialmente se algum efeito especial é usado (sombras e janelas não retangulares, por exemplo). Sem contar que, às vezes, teremos que lidar com casos onde a janela é subdividida em diversas regiões de apenas 1 pixel…

Hoje em dia é mais provável que as GUIs usem stencil buffers para mascarar os bits que não serão plotados. No caso do Linux, por exemplo, os ambientes X11 modernos costumam usar OpenGL para esse fim. É provável que cada janela tenha seu próprio stencil buffer e o sistema mantenha uma lista das janelas visíveis e suas coordenadas z (quem está na frente de quem). Assim, para cada janela, as janelas com z>z_{corrente} são desenhadas no stencil buffer da janela em questão (apenas os contornos e preenchidas de branco), criando a máscara.

Assim, quando a GUI for, de fato, desenhar a janela, basta aplicar o stencil… É como serigrafia: As áreas mascaradas não deixam passar a tinta… Isso evita a complicação de manter uma lista de regiões. E, como raster operations são o default nas placas de vídeo atuais, é pouco provável que existam problemas com processamento ao lidarmos com áreas grandes ou com múltiplas subdivisões.

B-Trees

Lembram-se das árvores 2,3,4? Já falei delas aqui antes (aqui). Essas árvores tem a capacidade de acumular uma, duas ou três chaves num único nó. Os nome “2,3,4” refere-se à quantidade de links para os nós filhos de cada nó…

Bem… as B-Trees são parecidas. A diferença está na possibilidade de usarmos n chaves em cada nó, onde n é um valor ímpar maior ou igual a 3. Quero dizer, que nós podem ter duas ou mais chaves, mas o limite superior da quantidade deve ser 3 ou mais… Não há limites matemáticos para a quantidade de chaves num nó. Podemos ter nós com 1001 chaves, por exemplo… Na prática, a quantidade de nós é limitada para que não tenhamos que manter listas ordenadas muito grandes. Usarei exemplos com 5 chaves por nó neste texto.

Características das B-Trees e a inserção de chaves:

Cada chave num único nó deve ser arranjada de maneira que a lista esteja em ordem (usarei a ordem crescente aqui, para facilitar o entendimento). Isso quer dizer que:

K_1\leqslant K_2\leqslant\dots\leqslant K_{n-1}\leqslant K_{n}

Enquanto inserimos novas chaves no nó raiz, elas vão sendo colocadas na lista de forma ordenada até a lista ficar cheia (com 5 chaves), a próxima chave inserida, K_6 faz com que o nó sofra uma “divisão” (split). Num split retiramos a chave central e fazemos com que ela “suba” para o nó pai… Quando só temos o nó raiz, essa chave selecionada torna-se o novo nó raiz com dois nós filhos com duas chaves cada:

01-split

Só depois do split a chave K_6 é inserido no nó folha… Todas as inserções sempre são feitas em nós folhas:

02-insert

Outra características menos óbvia é que os nós intermediários e folhas sempre terão \left\lfloor\frac{n}{2}\right\rfloor chaves, no mínimo. Isso fica evidente quando pensamos no processo de split… Apenas nós cheios sofrem split e retirando a chave central (que “sobe”), sobram a quantidade de chaves citada acima para cada lado… A única exceção é o nó raiz, que pode ter apenas uma chave!

Vejamos agora o que acontece se tivermos um nó folha cheio e queremos inserir um item K_9:

03-insert-new-on-full-leaf

Ao percorrer a árvore, determinamos que a chave K_9 deve ser inserida no nó folha mais a direita, que está cheio. Por isso, este nó deve sofrer um split, fazendo com que a chave K_6 “suba” para o nó pai (raiz), dividindo o nó folha em dois e liberando espaço para a inserção de K_9, como mostrado acima.

A regra aqui é: Se formos inserir um item, a cada vez que encontrarmos um nó cheio ao “caminhar” pela árvore (de acordo com o critério da chave), devemos fazer um split. Se ambos o nó raiz e o nó folha estivessem cheios, deveríamos fazer o split do nó raiz e, ao pularmos para o nó folha, fazer o split dele também, subindo a chave central para o nó intermediário… Vejamos como isso funciona neste exemplo mais complexo, ao tentarmos inserir K_9:

04-insert-raiz-e-folha-cheios

Assim, a inserção sempre segue duas regras simples:

  1. Ao “caminhar” pela árvore, ao encontrar um nó cheio, faça um split;
  2. Ao encontrar o nó folha correspondente, insira a chave lá.

Outra característica que não é evidente (embora você possa percebê-la dando uma olhada nos exemplos acima) é que todos os nós folha sempre estarão no mesmo nível. Ou seja, uma B-Tree é “auto balanceada”.

Apagar chaves sempre é mais complicado, né?

Inserir chaves é moleza. As duas regras simples, acima, garantem que a inserção sempre será feita apenas nos nós folha. Não temos esse luxo no caso de apagamento de chaves. Quer dizer, qualquer chave deve poder ser apagada, certo?

O algoritmo de deleção é dividido em duas possibilidades: Uma para chaves contidas em nós folhas e outra para chaves contidas em nós intermediários ou raiz. Ainda assim, cada uma dessas possibilidades tem 5 regras simples.

  1. Se o nó onde a chave se encontra for folha e este nó tiver mais que \left\lfloor\frac{n}{2}\right\rfloor itens (ou seja: n_{itens}>\left\lfloor\frac{n}{2}\right\rfloor), então basta apagar a chave da lista. No exemplo com nós de 5 chaves, se o nó folha tiver 3 chaves ou mais essa regra se aplica, caso contrário, teremos que lidar com a segunda possibilidade;
  2. Se o nó for folha e tiver \left\lfloor\frac{n}{2}\right\rfloor itens, uma das sub regras abaixo se aplica (lembre-se: exceto pelo nó raiz, nenhum outro nó pode ter menos que \left\lfloor\frac{n}{2}\right\rfloor chaves!):
    • Se um dos nós folha irmãos do nó contendo a chave a ser apagada tiver mais que \left\lfloor\frac{n}{2}\right\rfloor itens, apaga-se a chave desejada e realiza-se uma rotação de chaves, onde a chave do nó pai “desce” para o nó folha e uma chave do nó irmão “sobe” para o nó pai. Eis um exemplo ao apagarmos a chave K_6 da árvore abaixo:
      delete2a
      Note que, neste exemplo, tanto faz se escolhermos o nó irmão da direita ou esquerda. O que vai mudar é o sentido da rotação. No caso da árvore resultante, se quiséssemos apagar a chave K_7, por exemplo, teríamos que realizar uma rotação o sentido horário à partir do nó irmão do lado direito (K_3) e a chave K_4 do nó pai;
    • Se os nós folha irmãos do nó contendo a chave a ser apagada tiverem \left\lfloor\frac{n}{2}\right\rfloor itens, então a chave deve ser apagada do nó folha atual e ele deve ser “juntado” com um nó irmão e a chave do nó pai que os divide “desce”, formando um nó cheio. Isso criará um nó “semi-cheio” e diminuirá o nó pai em um item. Eis um exemplo, apagando a chave K_5:delete2b
      De novo, tanto faz usarmos o nó irmão da direita ou da esquerda.A diminuição do nó pai pode ser problemática se ele não for o nó raiz e tiver \left\lfloor\frac{n}{2}\right\rfloor itens. Este caso é discutido abaixo…;
  3. Se o nó não for folha, mas for um nó interno (entre um nó folha e o nó raiz):
    • Se o um dos nós filhos da chave em questão tiver mais que \left\lfloor\frac{n}{2}\right\rfloor, basta apagar a chave desejada, substituíndo-a por uma das chaves de um extremo de um nó filho. Por exemplo, apagando K_6 da subárvore abaixo:
      delee3a
    • Se os nós filhos tiverem \left\lfloor\frac{n}{2}\right\rfloor itens, basta juntá-los e deletar a chave no nó pai (exemplo, deletando K_8):
      delete3b
      Este é o mesmo segundo sub caso do caso 2, lá em cima.

Neste ponto vale a pena especificar o que seria “juntar” dois nós filhos com \left\lfloor\frac{n}{2}\right\rfloor itens… Trata-se do inverso de um split (chamarei de unsplit)… A chave do nó pai é apagada deste nó, trazida para o centro do nó filho “juntado” e, recursivamente, deletada do novo nó filho… Dessa forma ela pode propagar-se até um nó folha, onde será apagada de acordo com as regras propostas acima. Essa “propagação” não é importante, já que apenas ocorrerá n-1 vezes, onde n é o número de níveis da árvore.

Determinando o tamanho máximo de uma B-Tree:

Como cada nó tem tamanho máximo, podemos calcular, no caso extremo, onde temos todos os nós completamente preenchidos, o tamanho máximo da árvore:

\displaystyle n=1+\left(\sum_{x=1}^k K^x\right)

Onde k é o número máximo de níveis, excluindo o nó raiz (nível 0) e K é o número de chaves por nó. Uma árvore com nós de 5 chaves e 4 níveis tem 781 nós, uma de 5 níveis terá 3901, no máximo. A equação acima poderia ser simplificada para n=\sum_{x=0}^k K^x, mas preferi deixar o “1 +” evidente para explicitar a existência incondicional do nó raiz.

Considere agora como um nó estaria codificado na memória: Em primeiro lugar, precisamos manter registro de quantas chaves existem no nó. Depois, precisamos manter as chaves e os links. Ajuda também manter um “bit” extra, indicando se o nó é folha o não (esse bit pode ser codificado junto com o byte contendo a quantidade de chaves). Por exemplo:

#define MAX_KEYS 5
#define MIN_KEYS ((int)MAX_KEYS / 2)

struct node_s {
  uint8_t type:2;  // 0=root, 1=intermediário, 2=folha
  uint8_t num_keys:6;
  key_t keys[MAX_KEYS];
  struct node_s *children[MAX_KEYS+1];
};

A estrutura acima permite que tenhamos um máximo de 64 chaves num único nó (se num_keys começar a contagem de 1). O tamanho do nó depende do tipo da chave e do número delas. Vamos supor que nossas chaves sejam do tipo uint32_t. A estrutura node_s terá 69 bytes, para as 5 chaves por nó. Parece demasiado, mas considere uma árvore AVL, por exemplo… Cada nó dessa árvore tem dois bits com o valor do balanceamento, a chave e dois nós. Ou seja, nas mesmas condições, 21 bytes. Mas, para guardamos 5 chaves precisaríamos de 5 nós ou 105 bytes… No caso extremo, com 64 chaves por nó, a B-Tree teria nós com 777 bytes. Uma árvore AVL com a mesma quantidade de nós consumiria 1344 bytes… A B-Tree é mais econômica!

Revisando as vantagens das B-Trees sobre as árvores AVL e Red-Black

Vimos que as B-Trees tendem a ser mais econômicas… Outra vantagem é que a rotina de inserção é mais rápida, eventualmente exigindo splits de alguns nós. A rotina de deleção, embora pareça mais complicada, geralmente é tão veloz quanto as das suas irmãs…

No caso das árvores red-black, algumas vezes elas ficam “capengas” ou “desbalanceadas”. As B-Trees não ficam e ainda têm a vantagem de que todos os nós folha sempre ficam no mesmo nível.

Outra vantagem é a alocação de nós… No caso das B-Trees, uma razoável quantidade de chaves é alocada de uma tacada só… Mas, é claro, a taxa de aproveitamento desses nós inicia-se em pouco menos de 50% da alocação. Considerando a economia que as B-Trees nos dão, mesmo assim, é um bom negócio.

Uma coisa que pode ser vista como desvantagem é a necessidade de manter as chaves num nó em ordem. Ao invés de lidarmos apenas com os algoritmos de inserção e deleção, teremos que lidar com ordenação linear também. Considerando que um nó tem tamanho limitado de chaves, esses algoritmos são bem simples e, mesmo que nós grandes fossem usados, alguma variação de qsort poderia ser usado… Da mesma forma, uma vez que as chaves são ordenadas, para encontrar uma chave dentro de um nó, podemos usar algoritmos como binary search, o que acelera bastante a busca.

Mesmo que a pesquisa por nó seja linear, a quantidade de níveis de uma B-Tree é menor que a de uma árvore AVL equivalente, tendendo a torná-la mais rápida.

Num outro artigo mostrarei formas de otimizar as B-Trees. Existem variações desse tipo de árvore de multinível, como as B+Trees e B*Trees.

Senhas

Acho que você, provavelmente, já topou com esse tipo de regra para criação de senhas: Mínimo de 6 caracteres, contendo letras, números e caracteres especiais. E troque a senha de tempos em tempos… A maioria das empresas que conheço usam essas regra simples. Sabe de onde elas vieram?

Tem um monte de gente que acha que isso é uma daquelas coisas de “senso comum”, mas a regra veio de uma recomendação do NIST (National Institute of Stantards and Technology), um instituto governamental norte-americano que dita normas usadas pelo governo e que acabam sendo acatadas pela indústria em geral… Pois bem, este padrão foi criado em 2009 e aposentado em 2016 (veja aqui) porque este tipo de metodologia não ajuda muita coisa, ao contrário do que pensam alguns “especialistas” em segurança! Na realidade, só atrapalham o maior interessado: o usuário!

Hoje, com GPUs mais poderosas, é possível “adivinhar” uma senha de 6 caracteres em poucos segundos, usando força bruta! Alguns algoritmos conseguem testar bilhões de senhas possíveis por segundo. Uma senha montada de acordo com a regra citada anteriormente, mesmo considerando que as letras possam ser diferenciadas entre maiúsculas e minúsculas, pode ser quebrada em menos de 1 dia num PC (alguns minutos num supercomputador ou num cluster de GPUs).

Recomendo que você dê uma olhada no site GPC’s Password Haystacks para avaliar a sua senha…

Um outro esquema usado é a transmissão e armazenamento de hashs (MD5 ainda é usado em aplicações, hoje em dia!) e, ainda por cima, com um “salzinho” para tornar a coisa mais difícil… Acontece que o argumento acima continua valendo: Embora uma senha com hash SHA256 seja mais difícil de “quebrar”, processadores e GPUs modernas são capazes de testarem, literalmente, bilhões de possibilidades por segundo… Se você usar um cluster de GPUs, através de OpenCL, literalmente trilhões de testes por segundo podem ser feitos… Eis um deles:

Computador do meio com 7 placas GTX1080 em SLi, só para cracking!</small)
Computador do meio com 7 placas GTX1080 em SLi, só para cracking!

O software usado? Está disponível gratuitamente e é FOSS. Por exemplo, o ocl-hashcat e o rainbowcrack.

Senhas de 6 caracteres e, hoje em dia, inferiores a 12 (até 2016, pelo menos!), são facilmente quebráveis… Mas, e quanto a trocar a senha frequentemente?

Existe o fator psicológico aqui… Forçar o usuário a trocar a senha frequentemente faz com que ele tenta a usar a mesma senha, com algumas pequenas modificações… Por exemplo, se a senha for “secreta” (exemplo de senha!), das próximas vezes ele mudará para “secreta2”, “secreta3”, “secreta!”, “secreta?!” etc. É claro que o usuário tende a fazer isso porque não precisará se lembrar das novas senhas, mas apenas da pequena modificação.

O que fazer?

A primeira coisa é evitar usar esquemas de autorização de acesso que peçam login/senha. Por exemplo, uma grande quantidade de sites vêm usando a estrutura de autenticação do Google e do Facebook para permitirem acesso de usuários… O Google e o Facebook tiveram um trabalhão para criarem um esquema de login que seja seguro o suficiente e, como eles fornecem isso como serviço, tendem a manter o esquema cada vez mais seguro… Se seu sistema é online, usar a autenticação do Google pode ser uma boa idéia, especialmente por causa do Android…

Mas, se sua aplicação não for online, ao invés de usar login e senha, vale a pena investir um pouco num “security token”… Esses “tokens” podem ser usados na forma de smartcards, cartões RFI ou pendrives. Em essência, você tem um certificado do usuário, assinado pelo proprietário do software, que lhe permitirá tanto verificar a autenticidade da identidade do usuário (assumindo que só ele tem o token) quanto a autorização para o acesso… NENHUMA SENHA É NECESSÁRIA!

Mas, mesmo que login/senha seja algo que você não quer abrir mão, forçar um conjunto de regras pode ser uma boa ideia desde que matematicamente eficientes (“senso comum” não vale de nada!)… Por exemplo: Forçar o mínimo de 6 caracteres com letras, números e especiais é boboca porque uma senha como “aaaa@1” é válida e, provavelmente, uma das primeiras que vai ser testada num método de força bruta… A regra mais interessante é garantir que a entropia da senha seja maior que um certo valor… Infelizmente, calcular entropia de informação é algo um tanto quanto complicado (veja aqui) e, quando se aplica a senhas, meio subjetivo…

Não tema! Um dos meios mais seguros, do ponto de vista do usuário, atualmente, é o uso de passphrases e pode ser exemplificado por essas tirinhas do xkcd:

password_strength

Como qualquer pessoa pode perceber, bolar uma frase sem sentido, engraçada e que lembre alguma coisa apenas para o usuário em questão, além de aumentar a quantidade de bits de entropia (calculado como n\lg\,c, onde c é a quantidade de caracteres que podem ser usados numa única posição e n é o tamanho da string), torna a senha muito mais fácil de lembrar e difícil de ser “adivinhada”.

Durante algum tempo usei a senha (cunhada por um conhecido) “chuta que dá, certo?”…

MyToyOS: Usandao a lib gnu-efi

Podemos, é claro, codificar um bootloader EFI manualmente, mas também podemos usar a libgnuefi e aproveitarmos todos os recursos que o padrão e a BIOS podem nos oferecer. Para tanto, basta instalar:

$ sudo apt-get install gnu-efi

Eis um “hello, world”:

#include <efi/efi.h>
#include <efi/efilib.h>
 
EFI_STATUS EFIAPI efi_main(
    EFI_HANDLE ImageHandle, 
    EFI_SYSTEM_TABLE *SystemTable)
{
  InitializeLib(ImageHandle, SystemTable);
  Print(L"Hello, world!\n");
  return EFI_SUCCESS;
}

O detalhe é como compilar e montar o arquivo UEFI. Eis um Makefile:

#
# HELLO.EFI makefile
#

hello.efi: hello.so
    objcopy -j .text \
      -j .sdata \
      -j .data \
      -j .dynamic \
      -j .dynsym \
      -j .rel \
      -j .rela \
      -j .reloc \
      --target=efi-app-x86_64 \
      $^ $@

hello.so: hello.o
    ld $^ \
      /usr/lib/crt0-efi-x86_64.o \
      -nostdlib \
      -znocombreloc \
      -T /usr/lib/elf_x86_64_efi.lds \
      -shared \
      -Bsymbolic \
      -L /usr/lib \
      -l:libgnuefi.a \
      -l:libefi.a \
      -o $@

hello.o: hello.c
    gcc -c \
      -fno-stack-protector \
      -fpic \
      -fshort-wchar \
      -mno-red-zone \
      -I /usr/include/efi \
      -I /usr/include/efi/x86_64 \
      -DEFI_FUNCTION_WRAPPER \
      -o $@ $<

Eis a explicação para os comandos. O compilador, obviamente, irá criar um objeto que não contém referências à libc e código independente de posição (Position Independent Code, ou PIC). É necessário informar o diretório dos headers da gnu-efi… Logo depois criamos um shared object “linkando” o objeto com as libs estáticas libgnuefi.a e libefi.a, também com o objeto de inicialização crt0-efi-x86_64.o. A opção -Bsymbolic é importante para manter todos símbolos auto contidos no shared object.

É claro que UEFI não suporta o formato ELF e, por isso, usa-se o utilitário objcopy para copiar as sessões dela para o novo arquivo EFI. As opções -j dizem quais sessões devem ser copiadas (se existirem) e --target informa o formato do arquivo de saída: efi-app-x86_64 para aplicações EFI, efi-bsd-x86_64 para “bootstrap driver” (ou bootloader) e efi-rtd-x86_64 para “runtime driver”.

Pode ser uma boa idéia acrescentar as opções -ffreestanding e -nostdlib na linha de comando do GCC… Se não retirarmos o stack-protector e as red-zones (esse código ai é para x86-64!), o executável não funcionará!

Criando uma partição GPT de teste

Para criarmos um disco “virtual” de 100 MiB (195312 setores) com uma partição GPT e colocarmos o programinha acima na partição EFI, podemos fazer:

# dd if=/dev/zero of=disk.img bs=512 count=195312
# gdisk disk.img
GPT fdisk (gdisk) version 1.0.1

Partition table scan:
  MBR: not present
  BSD: not present
  APM: not present
  GPT: not present

Creating new GPT entries.

Command (? for help): o
This option deletes all partitions and creates a new protective MBR.
Proceed? (Y/N): Y

Command (? for help): n
Partition number (1-128, default 1): 1
First sector (34-63966, default = 2048) or {+-}size{KMGTP}: 
Last sector (2048-63966, default = 195279) or {+-}size{KMGTP}: 
Current type is 'Linux filesystem'
Hex code or GUID (L to show codes, Enter = 8300): ef00
Changed type of partition to 'EFI System'

Command (? for help): w

Final checks complete. About to write GPT data. THIS WILL OVERWRITE EXISTING
PARTITIONS!!

Do you want to proceed? (Y/N): Y
OK; writing new GUID partition table (GPT) to disk.img.
Warning: The kernel is still using the old partition table.
The new table will be used at the next reboot or after you
run partprobe(8) or kpartx(8)
The operation has completed successfully.

# losetup --offset 1048576 --sizelimit 98934272 /dev/loop0 disk.img
# mkdosfs -F32 /dev/loop0
mkfs.fat 3.0.28 (2015-05-16)
Loop device does not match a floppy size, using default hd params
# mount /dev/loop0 /mnt
# cp hello.efi /mnt/
# umount /dev/loop0
# losetup -d /dev/loop0

Os valores passados para losetup merecem uma explicação. Como criamos a partição EFI no setor 2048 (como sugerido pelo gdisk), o offset inicial é 2048\cdot512. O tamanho dessa partição é de (195279-2048)\cdot512=98934272 bytes, onde 195279 é o último setor da partição. Usar losetup permite mapear um pedaço de um arquivo num dispositivo de loopback e ai podemos formatá-lo e montá-lo…

Se você pretende criar uma imagem de um disco mais “realista”, coloque uma partição pequena para EFI (FAT32) — digamos, uns 32 MiB — e outra partição vazia que será formatada depois (com o sistema de arquivos do MyToyOS).

Testando o novo “HD” no QEMU

Temos que, antes, instalar um pacote chamado ovmf. Ele contém uma BIOS que suporta UEFI 2.6 e, para iniciar a emulação basta fazer:

$ qemu-system-x86_64 -bios /usr/share/ovmf/OVMF.fd \
  -drive file=disk.img,if=ide

Repare que não temos um bootstrap, mas uma aplicação EFI. Podemos executá-la do shell, bastando selecionar o drive FS0: e digitar hello.efi:

efiapp
Grab da tela do qemu-system-x86_64

Vantagens e desvantagens:

As óbvias vantagens são as de que este programinha executa no modo protegido x86-64! A lib gnu-efi toma conta disso pra você… A outra é que todas as funções padronizadas EFI estão a sua disposição…

A desvantagem, também óbvia, é que o executável fica grande. Note que para imprimir uma simples string de 14 caracteres (incluindo o salto de linha final) criou um arquivão de quase 45 KiB!

MyToyOS: UEFI, a assombração reaparece!

Quanto mais eu penso que me livrei dos padrões da Microsoft, mais eles me perseguem…

Recentemente, no grupo “C & Assembly para x86-64”, no Facebook, eu disse que migraria o esboço do bootloader do MyToyOS para o padrão UEFI. O motivo é simples: O particionamento tradicional não permite discos muito grandes e UEFI tem a vantagem de não precisamos lidar com vários estágios de carga do bootloader.

Como UEFI funciona?

Nada mais simples: Trata-se de um simples arquivo executável (.EXE, mas com a extensão .EFI) no formato Portable Executable da Microsoft! Eis a assombração! O formato é esse:

Teremos que lidar com essa "engronha"...
Teremos que lidar com essa “engronha”…

O significado de cada campo pode ser obtido na especificação do padrão UEFI (aqui) e na especificação do formato PE (aqui).

Mas é interessante notar: O formato usado no UEFI é simplificado com relação a esse ai. Algumas sessões não existem nos arquivo .efi e a diferenciação sobre o que o executável faz é determinada pelo subsistema… Existem, pelo menos, 3 tipos de executáveis: Aplicações, bootloaders e firmware drivers.

Em essência, tudo o que temos que fazer é um arquivo em assembly contendo o header do formato cima, preenchido, e todas as demais rotinas podem ser feitas com o GCC (4.9 ou superior, porque eles permitem geração de código em 16 bits!).

Sim… o código é em 16 bits, como um executável para MS-DOS…

O que a ROM BIOS de sistemas que suportam UEFI faz é obter o arquivo da partição EFI e executá-lo… O arquivo pode ter, em teoria, até 2 GiB de tamanho. Na prática, é prudente mantê-lo com um tamanho inferior a 128 KiB (dois segmentos – não sei onde esse arquivo é carregado!), mas isso não é um limite rígido… A vantagem, é claro, é que não estamos mais restritos a um único setor de boot carregado pela BIOS! De fato, o código do MBR (Master Boot Record) desaparece completamente. Em uma de minhas máquinas de teste, onde tenho somente o UBUNTU 16.04 instalado. Obtendo o setor da MBR (LBA 0):

# dd if=/dev/sda of=disk.img bs=512 count=1

Obtenho isso:

part
Cadê a MBR? Não existe! Ou seja, temos apenas uma única entrada da tabela de partição tradicional (a partir do offset 0x1be, usada pela especificação da GUID Partition Table) e, mesmo assim, trata-se de uma entrada desabilitada, pois começa com 0x00, ao invés de 0x80. Provavelmente essa entrada aponta para a partição EFI.

A partição EFI, por sua vez, é uma partição FAT32:

# fdisk -l /dev/sda
Disk /dev/sda: 465,8 GiB, 500107862016 bytes, 976773168 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disklabel type: gpt
Disk identifier: 55DC090F-5E38-4521-A4E6-7B669BBB9ED6

Device         Start       End   Sectors   Size Type
/dev/sda1       2048   1050623   1048576   512M EFI System
/dev/sda2    1050624 960253951 959203328 457,4G Linux filesystem
/dev/sda3  960253952 976771071  16517120   7,9G Linux swap

# fdisk -l /dev/sda1
Disk /dev/sda1: 512 MiB, 536870912 bytes, 1048576 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disklabel type: dos
Disk identifier: 0x00000000

O que tem dentro dessa partição? Os arquivos executáveis e, eventualmente, configurações:

# df /dev/sda1
Filesystem     1K-blocks  Used Available Use% Mounted on
/dev/sda1         523248  3684    519564   1% /boot/efi

# tree /boot/efi/
/boot/efi/
└── EFI
    └── ubuntu
        ├── fw/
        ├── fwupx64.efi
        ├── grub.cfg
        ├── grubx64.efi
        ├── MokManager.efi
        └── shimx64.efi

O grub colocou esses arquivos todos ai… Cada um deles, se estiver no formato correto, é executado pela BIOS quanto o sistema inicia. Simples assim. No caso, grubx64.efi lê o arquivo grub.cfg para “bootar” o sistema na partição correta. O executável fwupx64.efi, provavelmente, é usado pelo grub para o caso de termos firmwares fora do padrão, onde drivers são colocados no diretório fw/. Não me pergunte o que seria o MokManager e o shimx64… pergunte à documentação do grub 2.

Por que a especificação é tão grande?

O documento da especificação UEFI mostra um conjunto de facilidades disponíveis quando você usa o UEFI SDK (Software Development Kit). Por exemplo, o executável pode pedir para a BIOS iniciar o modo protegido pra você, tanto em 32 bits quanto em 64… Mas, prepare-se para adotar um esquema bem diferente de convenções de chamadas de funções e obter um executável gigantesco no processo…

Não recomendo o uso do SDK por esse motivo e por outro mais prático: Uma das reclamações da adoção do padrão EFI é justamente o lobby que empresas como a Microsoft têm feito para criar bootloaders “seguros” que exijam o uso de criptografia. Na prática, eles querem controlar quem tenta instalar seus sistemas (somente comprando uma chave vocẽ poderia “bootar” o Windows, por exemplo)… Isso só é possível ao usar o UEFI SDK.

E quanto ao MyToyOS?

Bem… sem a limitação do tamanho dos estágios 0 e 1 podemos criar um bootloader mais complexo, até mesmo em modo gráfico (320×200 de 256 cores, VGA, por exemplo, ou usando um dos modos VESA). Além do header MZ e PE, o código pode ser quase totalmente feito em C e terá que achar onde se encontra a partição na GPT, pular para o modo protegido, carregar o kernel na memória alta e pular para ele… Vale a pena dar uma olhada no código de boot do Linux (no diretório arch/x86/boot/ dos fontes mais recentes). O arquivo header.S é o início de tudo…

Em teoria, tudo o que temos que fazer é colocar o executável num diretório EFI/mytoyos/ na partição EFI… Bem como criar a partição com o kernel… Dá até vontade de fazer uma brincadeira como o logo do AmigaDOS:

amigados

Hehehe…

Softwares de virtualização aceitam EFI?

Aceitam… No VirtualBox basta habilitar a opção:

vbox

No caso do QEMU, provavelmente você terá que instalar o pacote ovmf.

Ao que parece, no VMWare, existe um tweaker que habilita EFI também (não tenho certeza, não uso VMWare!).