Convertendo vídeos para texto com ffmpeg e caca-utils

Yep… você leu certo: caca-utils. Não me pergunte o que caca significa. Só sei que os caras chamam de Colour ASCII Art Library. O detalhe interessante é que alguns players conseguem renderizar vídeos usando essa biblioteca. É o caso do VLC e também do ffmpeg.

Então, dá para criar um vídeo usando ASCII art? Well… dá, mas não é direto. O problema desses codecs é que eles renderizam o vídeo em formato texto e, assim, não tem como incorporar cada “quadro” num container MP4, Matroska, AVI ou o raio que o parta… Infelizmente, temos que renderizar os quadros em formato gráfico para poder convertê-los e incorporá-los nos citados containers. Eis uma maneira de fazer:

  • O primeiro passo é converter o vídeo em quadros individuais e de tamanho bem definido. Isso pode ser feito com o ffmpeg da seguinte maneira:
$ ffmpeg -i video.mp4 -s hd720 -r 30 -f image2 %07d.png

Isso ai vai criar um porrilhão de arquivos PNG nomeados como 0000001.png, 0000002.png … até o último quadro do vídeo. Note que pedi, explicitamente, que o framerate seja de 30 quadros por segundo e que a resolução gráfica seja de 1280×720 (HD).

Aliás… esse é o método favorito de “misturar” vídeos, onde um deles (o sobreposto) tenha um canal Alpha, ou seja, transparência… A maioria dos editores de vídeo suporta essa feature. O OpenShot, por exemplo, usa esse recurso quando criamos um “efeito especial” usando Blender, por exemplo.

  • De posse de todos os quadros, temos que convertê-los para texto. É aqui que entra o caca-utils. Nele, temos um programinha chamado img2txt, que converte uma imagem qualquer (JPG, PNG etc) em texto, seja ASCII puro (sem cores), HTML, SVG ou um formato gráfico chamado TARGA. É esse que usarei, já que isso facilita a reconstrução do vídeo:
$ for i in *.png; do \
    img2txt -f tga -b ordered8 -W 160 "$i" > "${i%.*}.tga"; \
  done

A opção -b ordered8 usa subsampling em blocos de 8×8 para realizar uma emulação de dithering, em modo texto. A opção -W 160 informa ao img2txt que usaremos linhas com 160 caracteres… Você pode usar menos, como 80, que é o padrão para o modo terminal em muitas instalações (especialmente Windows), mas, veremos que usar linhas maiores (ou retângulos maiores) nos dará resoluções “textuais” melhores.

O loop acima converterá todos os PNG para TGA.

O padrão TARGA é muito usado por profissionais porque é um padrão lossless, se nenhuma compressão for usada.

  • Tudo o que temos que fazer agora é juntar todos esses arquivos TGA na mesma velocidade (framerate):
$ ffmpeg -r 30 -f image2 -i %07d.tga -s hd720 \
  -b:v 1200k -minrate 1200k -maxrate 1200k -bufsize 1200k \
  -c:v libx264 -an "out.mp4"

Voilà! Temos um arquivo out.mp4 com o vídeo em “ascii”. Para efeitos de comparação, eis um vídeozinho de 13 segundos (já usei ele por aqui antes) e o vídeo convertido logo abaixo:

E, abaixo, está a comparação da conversão dos PNGs com 80, 160 e 240 caracteres por linha:

Postmortem: Erros comuns que já vi em C++ e COM

Há mais ou menos uma década, ou um pouco mais, cheguei a trabalhar com consultoria a respeito de otimização e caça de erros em códigos de “frameworks” para algumas empresas. Lembro-me de 3 projetos grandes que apresentavam os mesmos erros que, até onde sei, jamais foram solucionados.

Como sempre acontece, trata-se do uso indiscriminado de “facilidades”, sem o devido conhecimento de como elas funcionam. Coisa comum no desenvolvimento usando “orientação a objetos”, afinal, alguns “comportamentos” estão “encapsulados” dentro de um conjunto de classes e o programador, em teoria, não deveria nem querer saber como, só usá-los, certo? Bem… errado!

Abaixo, mostro alguns erros que já encontrei e é apenas uma lista pequena contida num texto gigantesto, desculpe…

1º: Objetos anônimos temporários

O primeiro problema comum de ser encontrado em códigos escritos em C++ é o desconhecimento sobre como uma linguagem de programação funciona… E não estou falando somente de suas regras sintáticas, mas da semântica da resolução de expressões e passagem de argumentos de funções. Vejamos um exemplo simples com objetos de alguma classe complexa qualquer, usando sobrecarga de operadores:

a = b + c;

Essa simples expressão é composta de dois operadores (‘=’ e ‘+’), onde o operador de adição sempre retornará um “objeto anônimo temporário”. Por quê? Ora, nem o objeto ‘b’, nem o objeto ‘c’ devem ser molestados e, o que queremos, é a adição desses dois como resultado. Temos que criar, on-the-fly, um terceiro objeto que represente essa “adição”… É comum que um operador desse seja definido de acordo com a assinatura abaixo:

MyClass MyClass::operator+(const Myclass& o);

O objeto retornado por esse operador será usado como argumento para o operador “=”, que o copiará para o interior do objeto ‘a’ e, só então, o objeto anônimo temporário deixará de existir.

Para objetos pequenos, cuja cópia é simples de ser feita, a perda de performance é quase inócua, mas para objetos complexos, que contém em seu interior, agregações, listas, árvores etc, a operação de cópia pode ser bem demorada, bem como as necessidades de recursos podem crescer um bocado. Suponha que o objeto ‘c’ tenha uns 2 MiB de dados agregados em seu interior e o objeto ‘b’ tenha 1 MiB… Suponha, agora, que no processo de “adição” esses dados sejam manipulados de forma tal a gerar o consumo de 3 MiB (que pode ser bem mais, dependendo da transformação necessária!)… Temos o consumo de 3 MiB adicionais apenas no objeto anônimo temporário, retornado pelo operador ‘+’!

Nesses casos, para evitar a criação de objetos temporários, seria interessante usarmos funções-membro especializadas ao invés de operadores. A expressão acima poderia ser reescrita como:

a.append(b, c);

Onde a função-membro append aceitaria duas referências para os argumentos ‘b’ e ‘c’. Podemos controlar a criação de objetos temporários, se houver necessidade de um.

Mais um exemplo: Suponha agora que a expressão seja bem mais complexa, como a = -(b + c) * (d >>= e);. Dependendo do que os operadores ‘-‘ (unário), ‘*’ e ‘>>=’ fazem, teremos uns 3 objetos anônimos temporários em potencial (um para t1=(b + c), outro para t2=t1*(d >>= e) e outro para t3=-t2). Cada um com seus próprios recursos… Isso sem contar que podemos ter outras expressões que usem os objetos originais e, mesmo com a otimização de common subexpression elimination, que não funciona muito bem para classes customizadas, já que a semântica dos operadores muda radicalmente, podemos ter n objetos temporários anônimos em uso num mesmo bloco.

A criação de objetos temporários acontece, também, com chamadas de funções, mas, neste caso, os objetos não são “anônimos”, mas uma cópia do original, se fizermos algo assim:

MyClass f(MyClass a, MyClass b) { ... }

Ao passar instâncias para a função f(), automaticamente o compilador gerará uma cópia das instâncias originais, porque ‘a’ e ‘b’ não podem modificá-las, sendo locais à função… Note que a função retorna um objeto anônimo da classe ‘obj’ também!

É claro que para solucionar esse tipo de coisa, pelo menos no que se refere aos argumentos, podemos usar referèncias:

MyClass f(const MyClass& a, const MyClas& b) { ... }

Aqui, o qualificador const garante que a instância referenciada não poderá ser modificada no interior da função… Isso é óbvio para um desenvolvedor experiente, mas, nessa época de .NET e Java, onde argumentos de funções de tipos complexos são, na verdade, referências, costuma-se esquecer do fato acima, causando grande pressão por uso de recursos…

2º: Tipos primitivos versus objetos “constantes”

Outra coisa que já observei é a tendência a usar classes que oferecem facilidades, ao invés de tipos primitivos, especialmente quando estamos lidando com constantes. Um exemplo clássico é a definição de “constantes” do tipo “string”… Nesses “frameworks” era comum ver algo assim:

const std::string ERROR1 = "Erro genérico";
const std::string ERROR2 = "Erro de qualquer bobagem";
const std::string ERROR3 = "Erro errado";
...
const std::string ERROR1023 = "Erro de um monte de erros";

O problema aqui é que o programador não está criando constantes. Está criando instâncias do objeto basic_string contendo contantes. Todos esses 1023 objetos terão que ser construídos, ou seja, código de construtores serão chamados. Só para ilustrar, eis o código em assembly gerado pelo GCC, para x86-64 (linux), do construtor da “constante” ERROR1, acima:

_GLOBAL__sub_I_test.cc:
  movabs rax, 7954877705826234949 ; A string de ERROR1.
  mov rdx,__dso_handle
  mov rsi,_ZL6ERROR1   ; A referência ao objeto ERROR1.
  mov [_ZL6ERROR1+16],rax
  mov rdi, _ZNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEED1Ev
  mov eax, 28515
  mov qword [_ZL6ERROR1],_ZL6ERROR1+16
  mov dword [_ZL6ERROR1+24],1769122243
  mov [_ZL6ERROR1+28],ax
  mov qword [_ZL6ERROR1+8],14
  mov byte [_ZL6ERROR1+30],0
  jmp __cxa_atexit

É claro que a rotina também registra o destrutor (pulando para __cxa_atexit no fim das contas)… Mas, neste construtor, porque a string é pequena (14 bytes), ela cabe no registrador RAX e o valor atribuído no início da rotina é exatamente essa string parcial no formato little endian (os primeiros 8 bytes: 0x6E6567206F727245, formando “Erro gené”), a 5ª instrução, de cima para baixo completa a string (0x6972A9C3 ou “rico”), e a penúltima coloca o ‘\0’ final. Mas existem outras 8 instruções para esse simples construtor de apenas uma das “constantes” (dentre eles o ajuste do tamanho da string na ante-penúltima instrução). Para strings maiores que 16 bytes, contando o terminador ‘\0’, o construtor fica mais complicado… Assim, um código enorme será executado para inicializar os objetos.

Compare isso à simples declaração de arrays:

const char ERROR1[] = "Erro genérico";

O compilador só fará isso:

section .rodata

        global ERROR1
ERROR1: db 'Erro genérico',0

Nenhum construtor é criado.. Os dados simplesmanente são colocados no segmento de dados read-only e acessíveis por ponteiro. Existe outra vantagem nisso: O qualificador const, para tipos primitivos, tende a criar constantes de fato em C++. Por exemplo, se tivéssemos, em dois módulos separados:

// No módulo errors.cc
const char ERRO1[] = "Erro";

// No módulo xpto.cc
const char * const error = "Erro";

O linker tenderá a fazer os ponteiros ERROR1 e error apontarem para o mesmo lugar porque existirá apenas uma string “Erro” no código inteiro (otimização “merge duplicate strings“). E, como vimos no caso do uso de “objetos constantes”, eles são construídos e a string é copiada para o interior do objeto, triplicando o uso dos recursos (teriamos 3 strings “Erro” na memória se o objeto ERROR1 e ERROR2 foram inicializados com a string “Erro”).

Isso não parece ser um problema sério, mas considere que as classes definidas nesse framework eram usadas em objetos COM que, de acordo com o ambiente, podem ser carregados e descarregados da memória… Esse comportamento é comum, no que a Microsoft chama de “objetos interoperáveis” que é a mistura de COM (unmanaged code) com objetos .NET (managed code)

Ao usar constantes “reais”, definidos com tipos primitivos, o único problema é que para usá-las teremos que instanciar objetos temporários anônimos do tipo string, como em:

std::cerr << std::string(ERROR1) << '\n';

Mas, a criação deste objeto menos traumática. O compilador, provavelmente, criará uma única função com um construtor string::string(const char *); (ou um construtor de conversão). Diferente da criação de múltiplos objetos “constantes”, este objeto temporário é criado na hora de sua necessidade e destruído assim que sairmos do escopo do bloco onde ele existe.

3º: Conversão de tipos antes da hora

De maneira similar, outro fato relacionado às funções da Win32 API e objetos COM (OLE) é o uso de um tipo “especial” de string chamada BSTR. Em C e C++ uma string é definida como um array contendo os caracteres e terminada em ‘\0’. Note que não falei “array de chars” porque podemos ter arrays de wchar_t, onde cada item tem 16 bits de tamanho…

No caso de COM (OLE), algumas vezes é necessário usar uma estrutura diferente para strings, onde cada caracter é um wchar_t e o terminador é um ‘\0’, também com 16 bits de tamanho… Além disso, o primeiro wchar_t (ou unsigned short) do array contém o tamanho da string contida no array.

Tanto no Visual Studio quando no Borland C++ Builder (usado em dois dos projetos de que falei) contém classes especializadas para conter esse tipo de string e é comum a conversão do tipo de string ANSI (na nomenclatura do Windows, são strings de chars) ou Wide Strings (onde cada ítem é um wchar_t) para o tipo BSTR (ou _bstr_t). A conversão não pode ser mais simples, usando classes:

CBSTR bstr = str;

Dependendo do tipo de str (CString ou CStringW) a classe CBSTR poderá ter um construtor de conversão mais ou menos assim:

// Note: CString contém strings "ansi".
CBSTR::CBSTR(const CString& s)
{
  size_t i, length;
  char *p = s.c_str();

  length = strlen(p);
  this->str = new wchar_t[length+1];
  for (i = 1; i <= length; i++) this->str[i] = (wchar_t)*p++;
  this->str[i] = '\0';
  this->str[0] = (wchar_t)(length + 1); //?
}

A função acima, é claro, pode muito bem ser substituída por uma chamada a StrAllocString(), no caso de Wide Strings

O destrutor de CBSTR verifica se existe um ponteiro não nulo em this->str, efetua um delete [] this->str;, se for o caso, e zera this->length. Mas, o ponto aqui é que, cada conversão envolve a alocação de novo espaço e a cópia da string original, potencialmente duplicando o espaço originalmente usado, e triplicando o uso de recursos.

Assim, usar BSTRs antecipadamente é gasto de recursos. Deveriam manter as strings confinadas aos tipos genéricos (que ocupam 2 ou 3 bytes a menos, pelo menos, já que não contém o campo length) e só quando forem chamar uma função OLE, efetuassemos:

{ SomeAPIOLEFunction(CBSTR(str).bstr()); }

Onde o membro bstr() retorna o ponteiro para a string BSTR… Note o bloco… O objeto temporário seria destruído logo após o retorno da função…

O ponto aqui é que BSTRs são necessárias apenas para as chamadas dessas funções da Win32 API. Não há necessidade de mantê-las instanciadas mais do que o tempo necessário de seu uso. A mesma coisa acontece quando uma função da API devolver uma BSTR. Poderíamos fazer algo assim:

// Note: CStringW contém Wide string.
CStringW str;

{
  wchar_t *p;
  
  SomeAPIOLEFuncionGetsBSTR((BSTR *)p);
  str = CBSTR((BSTR *)p); // supondo que CBSTR aceite um ponteiro void...
                          // supondo que CStringW tenha um construtor de
                          //   conversão para BSTR *.
  // A expressão acima poderia ser substituída por:
  //
  //   str = (BSTR *)p;
  //
  // Se CStringW tiver alguma conversão de ponteiros desse tipo.

  // Pode ser necessário chamar SysFreeString((BSTR *)p) aqui!
}

Do mesmo jeito, CBSTR “morrerá” assim que o bloco for encerrado… Apenas por um breve momento teremos muito recurso em uso, mas strings deste tipo não são tão grandes assim (64 KiB, no máximo) e logo o final dos blocos as destruiriam…

4º: Agregações com containers errados

É comum, nessas classes complexas de frameworks, que o desenvolvedor queira manter listas, filas, pilhas e outras estruturas. O que é comum encontrar é o uso de containers errados para a finalidade que o objeto se dispõe a resolver. Por exemplo, já vi muita classe agregando vector<T> ou list<T> para conter uma lista de objetos ordenados. É clarqo que dá para fazer isso e a STL disponibliza a função sort() no header algorithm. Só que existem containers que são feitos para manterem itens ordenados à medida que os inserimos… É o exemplo de set e map (e seus irmãos que aceitam várias chaves idênticas, multiset e multimap). Eles usam uma red black tree para implementar esse comportamento e, portanto, têm tempo de pesquisa na ordem de \log n. Sendo bem mais rápidos do que os containers mais “fáceis” de usar.

5º: O preconceito contra ponteiros

Eis um dos motivos da “fuga” da programação procedural para a “orientada a objetos”. Tem um monte de gente que tem medo de ponteiros! Embora a construção e destruição “automática” de objetos seja bem interessante, a alocação e dealocação dinâmica de blocos de dados é bem mais rápida e gera código mais eficiente. Isso pode ser visto nos dois fragmentos de código abaixo:

// Usando um array de objetos como uma lista.
// O último item é NULL (para emular o end()
// do iterator, abaixo).
obj *list, *p;

for (p = list; p; p++)
  p->doSomething();
-----%<-----%<-----
// Usando um container vector<>:
std::vector<obj> list;
std::vector<obj>::iterator i;

for (i = list.begin(); i != list.end(); i++)
  i->doSomething();

O segundo código parece ser mais limpo e simples que o primeiro, mas ele esconde um monte de detalhes de implementação. Para objetos simples os dois códigos são quase que exatamente os mesmos (quase! o primeiro é mais eficiente), mas se seu objeto tiver funções virtuais, herança múltipla (comum no caso de COM), classes base virtuais, … o container vector pode gerar código mais complicado (lembre-se que ele é um template). E, como demonstrei neste artigo, um container não se comporta exatamente como se espera, às vezes.

Além disso, graças ao conceito de “referência”, a turma do C++ prefere usá-las, ao invés de ponteiros só porque a “notação” é mais simples, do ponto de vista da linguagem. Mas, note que lidar com ponteiros é coisa que o processador faz com facilidade. Ao adicionar comportamentos à classes, a abstração permite ao programador mais liberdade, com o custo de uma pequena, mas significativa, ineficiência.

6º: O uso cego da MFC ou da VCL não é a melhor maneira de implementar um objeto COM

Ambas a Microsoft Foundation Classes (no Visual Studio) e a Visual Components Library (no Borland C++ Builder ou Delphi) contém templates prontinhos para usar herança na implementação de classes baseadas nas interfaces IUnknown ou IDispatch, que são as mais usadas nesse tipo de codificação. Esses templates, geralmente, são construídos através de wizzards que constroem classes com nossas funções membro hardcoded na classe, mais ou menos assim:

class IMyClass : public IUnknown {
public:
  virtual void doSomething(void);
};

Onde tudo o que você tem que fazer é criar o código de doSomething(). No entanto, especialmente com a interface IDispatch, graças ao conceito de late binding, esse tipo de artifício pode tornar seu código bem complicado.

Não parece, mas é bem mais fácil usarmos “composição” para criarmos essas classes, mais ou menos assim (este é apenas um código de exemplo não testado… Não me lembro se a MFC ou a VCL implementam as funções virtuais de IUnknown – estou assumindo que sim!):

class IMyClass : public IUnknown {
private:
  MyClassInternal *myobjptr;
public:
  IMyClass() : myobjptr(NULL) {}

  // métodos virtuais sobrecarregados de IUnknown.
  ULONG Release(void);
  HRESULT QueryInterface(REFIID riid, void **pObj);

  virtual void doSomething(void);
};

ULONG IMyClass::Release(void)
{
  ULONG ref;

  ref = IUnknonwn::Release();

  if (!ref && myobjptr)
  {  
    delete myobjptr;
    myobjptr = NULL;
  }

  // Quando retorna 0 a COM Library
  // faz um "garbage collection" e livra-se
  // da instância.
  return ref;
}

HRESULT IMyClass::QueryInterface(REFIID riid, void **pObj)
{
  // Se a interface que o usuário quer é
  // a de nosso objeto...
  if (riid == IID_MyClass)
  {
    // Cria o objeto interno
    if (!myobjptr)
    {
      myobjptr = new MyClassInternal;

      // Se não conseguiu alocar
      // objeto interno, retorna erro.
      if (!myobjptr)
      {
        // QueryInterface() exige isso,
        // em caso de erro.
        *pObj = NULL;

        // Retorna erro (E_NOINTERFACE é o ideal?)
        return E_NOINTERFACE;
      }
    }

    // Devolve o objeto, adiciona 1 à referência
    // e retorna S_OK.
    *pObj = this;
    AddRef();
    return S_OK;
  }

  return IUnknown::QueryInterface(riid, pObj);
}

// Wrapper.
void IMyClass::doSomething(void)
{ myobjptr->doSomething(); }

Na construção do objeto, via QueryInterface devemos instanciar o objeto da classe MyClassInternal, caso o GUID correto seja informado. Isso implica em realizar uma chamada a IUnknown::AddRef() para reference counting, que, de outra forma, seria feita pela função-membro base virtual, sobrecarregada.

As vantagens estão no fato que as funções-membro de MyClassInternal podem ser codificadas sem que tenhamos que nos preocupar com as regras impostas pela COM (OLE), a não ser no caso de multithreading… Ainda, no caso da sobrecarga de IUnknown::AddRef(), que criará a instância na sua primeira chamada, devemos também sobrecarregar IUnknown::Release() que se livrará de nosso objeto “interno” quando o contador chegar a zero, garantindo que não teremos memory leakage. A outra vantagem é que a classe interna pode ser desenvolvida de forma independente do contexto de um objeto COM. Ela pode até mesmo ser testada separadamente.

A desvantagem óbvia é que toda chamada é feita indiretamente e à partir de uma função virtual (implicando em tripla indireção). No entanto, não há motivos para que a função membro da classe interna também seja virtual…

7º: O seu objeto pode não estar no seu computador!

Quanto lidamos com COM ou OLE isso é importante: Os seus objetos podem estar em qualquer lugar onde haja maneira de comunicação… Por exemplo, o seu programa, que é um cliente de um objeto, pede ao Windows que instancie o objeto cuja identificação é IID_MyClass (um GUID). Graças às configurações no “arquivo de registro”, o sistema sabe que este objeto pode estar num servidor do outro lado do mundo, dai ele envia uma mensagem (marshalling) encapsulando tanto o tipo de objeto desejado quanto os métodos sendo chamados… Do outro lado, a OLE Library recebe a mensagem, a decodifica (unmarshalling), instancia o objeto desejado, chama a função membro indicada e monta uma mensagem de resposta (marshalling, de novo). A OLE Library, do seu lado, recebe a mensagem, decodifica (unmarshalling, de novo) e faz a função retornar o valor desejado.

Este caso de instanciamento fora do seu computador, chamamos de instancia Out-of-Process e o objeto cliente contém um “pseudo” objeto com as mesmas características do objeto original, mas sem a sua implementação. Trata-se de um “proxy” (ou um “procurador”, que age em benefício do cliente). Do lado do objeto real temos um “stub” (um “toco” ou “ponta”, em tradução livre), que receberá a mensagem e lidará com o objeto como se fosse o próprio cliente.

No caso do instanciamento ser feito na mesma máquina e na mesma thread, chamamos de In-Process, onde o par proxy/stub não é necessário:

Proxy/Stub

A falha em entender esse simples conceito causa grandes problemas no uso de COM…

8º: Modelo de threading errado

Nesses projetos que lidei não encontrei um objeto COM sequer que implementasse multithreading. Todos usavam o conceito de STA (Single Threaded Appartment). Isso porque este é o modelo mais simples, que deixa a COM Library lidar com a sincronização entre chamadas de várias threads para o mesma função-membro, bloqueando todas, exceto uma. De fato, apenas uma thread pode usar um objeto STA, se multiplas threads quiserem usar um objeto, cada uma delas terá que instanciar o seu…

O conceito de “Apartamento” é o mesmo do da vida normal: Existem apartamentos onde vivem pessoas sozinhas e outros onde vivem uma família com várias pessoas. No caso, não estamos falando de pessoas, mas threads.

É fácil desenvolver objetos COM em apartamentos de solteiros (STA), mas a desvantagem é que, num ambiente WEB, por exemplo, apenas um cliente terá acesso ao objeto por vez e, mesmo que vários clientes tenham seus próprios objetos, o consumo de recursos será enorme. Ou seja, seus objetos serão o “gargalo” de performance de todo o seu sistema.

Usar um modelo de threading diferente, como MTA (Multithreading Appartment) ou NTA (Neutral Threading Appartment) não é tarefa para o fraco de coração, especialmente porque a documentação detalhada sobre o assundo não é facilmente compreensível nas páginas da MSDN (ou seja, como diabos COM realmente funciona? De qualquer maneira, você pode ler muito aqui).

A escolha de um modelo de threading é essencial para que seus objetos possam ser usados com a máxima performance possível, de acordo com o ambiente. No caso de MTAs, o sincronismo entre threads deve ser feito pelo próprio objeto (usando critical sections, por exemplo), diferente das STAs, onde a COM Library usa um loop de mensagens para sincronia… Isso implica que o termo “Apartamento” é apenas um método de “marshaling” diferente, ou seja, de comunicação entre objetos (o cliente e o servidor, ou seja, a COM Library), o que torna todo o conceito ainda mais complicado… Por que essa comunicação? É que o objeto pode existir tanto no contexto do seu processo, quanto em algum outro processo ou até mesmo em um outro computador. COM pressupõe o uso de RPC (Remote Procedure Call), onde o objeto em uso pode estar, teóricamente, em qualquer lugar.

Não vou mostrar um objeto MTA e muito menos um NTA. A “neutralidade” foi uma modelo implementado no Windows 2000 para tornar MTAs ainda mais rápidos… Deixo esses detalhes para seus estudos ou, quem sabe, um dia volto a falar neles…

9º: Para complicar as coisas: COM+

Felizmente nunca peguei um projeto sério que usasse COM+… COM e OLE estão presentes no Windows desde a versão 3.1, para MS-DOS. COM+ é uma extensão do COM onde “transações” são incorporadas à complexidade do modelo. A ideia é criar objetos que permitam automatizar commits e rollbacks, do mesmo jeito que ocorre com bancos de dados. Garantindo que certas operações sejam atômicas.

Mas, sinceramente, COM e OLE já é um assunto complicado demais e eu quis ressaltar, ai em cima, que nos projetos que vi os desenvolvedores não faziam ideia do que fosse isso… Aliás, conheço poucos que fazem ideia, ainda hoje.

Quem tem medo de otimizações?

Já me disseram que eu não deveria usar as opções -O3 ou -Ofast em meus projetos. Bem… elas tendem a oferecer as melhores otimizações possíveis e, na tabela abaixo, mostro a diferença entre elas e a compilação sem opções de otimização (que chamei de “generic”) e a opção de “nenhuma” otimização (-O0). A opção -Os, em teoria, gera código pequeno (‘s’ de smaller), mas essencialmente, ele é a mesma coisa que -O2, exceto pela possível otimização de chamadas à strlen (que, na minha experiência, quase nunca o compilador consegue otimizar):

generic -Os -O0 -O1 -O2 -O3 -Ofast
-faggressive-loop-optimizations
-fasynchronous-unwind-tables
-fauto-inc-dec
-fchkp-check-incomplete-type
-fchkp-check-read
-fchkp-check-write
-fchkp-instrument-calls
-fchkp-narrow-bounds
-fchkp-optimize
-fchkp-store-bounds
-fchkp-use-static-bounds
-fchkp-use-static-const-bounds
-fchkp-use-wrappers
-fcommon
-fearly-inlining
-ffunction-cse
-fgcse-lm
-fira-hoist-pressure
-fira-share-save-slots
-fira-share-spill-slots
-fivopts
-fkeep-static-consts
-fleading-underscore
-flifetime-dse
-flto-odr-type-merging
-fpeephole
-fprefetch-loop-arrays
-freg-struct-return
-fsched-critical-path-heuristic
-fsched-dep-count-heuristic
-fsched-group-heuristic
-fsched-interblock
-fsched-last-insn-heuristic
-fsched-rank-heuristic
-fsched-spec
-fsched-spec-insn-heuristic
-fsched-stalled-insns-dep
-fschedule-fusion
-fsemantic-interposition
-fshow-column
-fsplit-ivs-in-unroller
-fstack-protector-strong
-fstdarg-opt
-fstrict-volatile-bitfields
-fsync-libcalls
-ftree-loop-if-convert
-ftree-loop-im
-ftree-loop-ivcanon
-ftree-loop-optimize
-ftree-parallelize-loops
-ftree-phiprop
-ftree-reassoc
-ftree-scev-cprop
-funit-at-a-time
-funwind-tables
-malign-stringops
-mavx256-split-unaligned-load
-mavx256-split-unaligned-store
-mfancy-math-387
-mfp-ret-in-387
-mfxsr
-mglibc
-mno-sse4
-mpush-args
-mred-zone
-msse
-msse2
-mtls-direct-seg-refs
-mvzeroupper
-fsigned-zeroes
-fdelete-null-pointer-checks
-fident
-finline-atomics
-ftrapping-math
-fbranch-count-reg
-fcombine-stack-adjustments
-fcompare_elim
-fcprop-registers
-fdefer-pop
-fforward-propagate
-fguess-branch-probability
-fhoist-adjacent-loads
-fif-conversion
-fif-conversion2
-finline
-finline-functions-called-once
-fipa-profile
-fipa-pure-const
-fipa-reference
-fmerge-constants
-fmove-loop-invariants
-fomit-frame-pointer
-fshrink-wrap
-fsplit-wide-types
-fssa-phiopt
-ftoplevel-reorder
-ftree-bit-ccp
-ftree-ccp
-ftree-ch
-ftree-coalesce-vars
-ftree-copy-prop
-ftree-copyrename
-ftree-cselim
-ftree-dce
-ftree-dominator-opts
-ftree-dse
-ftree-forwprop
-ftree-fre
-ftree-pta
-ftree-sink
-ftree-slsr
-ftree-sra
-ftree-ter
-falign-labels
-fcaller-saves
-fcrossjumping
-fcse-follow-jumps
-fdevirtualize
-fdevirtualize-speculatively
-fexpensive-optimizations
-fgcse
-findirect-inlining
-finline-small-functions
-fipa-cp
-fipa-cp-alignment
-fipa-icf
-fipa-icf-functions
-fipa-icf-variables
-fipa-ra
-fipa-sra
-fisolate-erroneous-paths-dereference
-flra-remat
-foptimize-sibling-calls
-fpartial-inlining
-fpeephole2
-free
-freorder-blocks
-freorder-blocks-and-partition
-freorder-functions
-frerun-cse-after-loop
-fschedule-insns2
-fstrict-aliasing
-fstrict-overflow
-fthread-jumps
-ftree-builtin-call-dce
-ftree-switch-conversion
-ftree-tail-merge
-ftree-vrp
-foptimize-strlen
-ftree-pre
-finline-functions
-fgcse-after-reload
-fipa-cp-clone
-fpredictive-commoning
-ftree-loop-distribute-patterns
-ftree-loop-vectorize
-ftree-partial-pre
-ftree-slp-vectorize
-funswitch-loops
-fassociative-math
-fcx-limited-range
-ffinite-math-only
-freciprocal-math
-funsafe-math-optimizations

Note que somente com as opções -O3 e -Ofast podemos ter o recurso de vetorização de um loop que, é claro, poderia ser “ligada” usando a chave -ftree-loop-vectorize, mas, de qualquer maneira, Essas duas opções oferencem muitas vantagens, tanto do ponto de vista da performance e do tamanho do código gerado pelo compilador.

Se você usa apenas a opção -O2, note que algumas coisas não são oferecidas, como o recurso de organizar funções de pouco uso como inline, algumas otimizações inter process também são são realizadas e além da vetorização, algumas eliminações de sub expressões globais e da previsão de loops (para auxiliar no branching predition) podem ficar seriamente comprometidas.

Tá certo que a opção -Ofast só é realmente útil em dois pontos: Quando não precisamos da conformidade estrita com IEEE 754 e quanto otimizações ainda mais agressivas (porém “unsafe”) sejam interessantes. Eu evitaria o -Ofast a não ser que você saiba o que faz. Mas adotaria -O3 como padrão.

UPDATE: Eu já tinha observado isso antes mas fiz questão de fazer alguns testes… Ao que parece, -O2 realmente gera código mais rápido que -O3 ou -Ofast!

strlen_sse42() usando função “intrínseca”.

Pode parecer que a instrução PCMPISTRI seja meio complicada de usar em C, já que ela oferece dois resultados diferentes: ECX, contendo um índice de acordo com a comparação, e os flags. Mas, felizmente, o valor de ECX será 16 se InRes2 estiver totalmente zerado! Assim, a função anterior, escrita em assembly, pode ser reescrita em C assim:

/* test.c

  Compilar com:
    gcc -Ofast -msse4.2 -o test test.c
*/
#include <stddef.h>
#include <x86intrin.h>

size_t strlen_sse42_c(const char *s)
{
  unsigned int index;
  size_t result;
  static const char ranges[16] = { 1, 255 };

  result = 0;
  do
  {
    index = _mm_cmpistri(*(__m128i *)ranges, 
                         *(__m128i *)s,
                         _SIDD_UBYTE_OPS         | 
                         _SIDD_CMP_RANGES        | 
                         _SIDD_NEGATIVE_POLARITY |
                         _SIDD_LEAST_SIGNIFICANT);

    result += index;
    s += sizeof(__m128i);
  } while (count == 16);

  return result;
}

O código final ficará semelhante, mas menos performático, ao anterior:

bits 64

section .rodata

  align 16
_ranges:  db 1, 255
          times 14 db 0

section .text

global strlen_sse42:
  align 16
strlen_sse42:
  movdqa xmm0,[_ranges]
  xor    eax,eax

.loop:
  pcmpistri xmm0, [rdi], 0x0_01_01_0_0  
  mov    edx,ecx
  add    rdi,16
  add    rax,rdx
  cmp    ecx,16
  jz     .loop
  
  ret

Algumas diferenças óbvias: a instrução MOVDQA é mais rápida que MOVDQU e exige que o array _ranges esteja alinhado. Eu deveria ter previsto isso no código em assembly no artigo anterior… O compilador escolheu fazer DUAS comparações, como instruído. Como não temos como verificar o flag ZF à partir da função intrínseca _mm_cmpistri, só nos restava comparar o valor retornado com 16.

Agora… é evidente que PCMPISTRI só está disponível se seu processador suportar SSE 4.2. Um método bem simples de usar essa função OU a função padrão do compilador é este:

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

// Daqui para frente, strlen será chamada por esse ponteiro!
size_t (*__strlen)(const char *);

static size_t strlen_sse42_c(const char *s)
{ ... }

// Esse atributo faz com que a função seja executada
// ANTES de main(). É interessante ter apenas uma dessas
// funções em seu programa, embora o atributo permita definir
// a ordem de execução...
static __attribute__((constructor)) void ctor(void)
{
  if (__builtin_cpu_supports("sse4.2"))
    __strlen = strlen_sse42_c;
  else
    __strlen = strlen;
}

As chamadas a __stlen, evidentemente, serão sempre indiretas, mas assim você garante a compatibilidade entre processadores ao usar a rotina. Além do mais, a quase totalidade das funções da libc são chamadas de forma indireta, já que localizam-se em libc6.so.

strlen() usando SSE 4.2

Há uns meses atrás (ou será que já faz um ano?) topei com uma dica do amigo Cooler, em seu blog, mostrando como comparar duas strings usando SSE 4.2. A rotina é realmente rápida porque compara 16 bytes de cada vez, ao invés de byte por byte ou, até mesmo, dword por dword (ou qword, se otimizarmos para o modo x86-64). Confesso que não tinha nenhuma intimidade com a instrução PCMPISTRI, disponibilizada pelo SSE 4.2 e fiquei maravilhado com o achado.

A rotina que ele publicou foi essa (publico aqui apenas a versão x86-64):

; Original code by Cooler_  c00f3r[at]gmail[dot]com
bits 64
section .text

global strcmp_sse42

; int strcmp_sse42(char *ptr1, char *ptr2);
strcmp_sse42:
  mov    rax,rdi
  sub    rax,rsi
  sub    rsi,16
   
strloop:
  add    rsi,16
  movdqu xmm0,[rsi]
  pcmpistri xmm0,[rsi+rax],0b0011000
  ja     strloop
  jc     blockmov
  xor    eax,eax
  ret
  
blockmov:
  add    rax,rsi    
  movzx  rax,byte [rax+rcx]
  movzx  rsi,byte [rsi+rcx]
  sub    rax,rsi    
  ret

O detalhe, é claro, está na instrução PCMPISTRI e no byte de controle… Ele torna a instrução bastante flexível e, ao mesmo tempo, difícil de entender… Eis uma outra rotina da libc que pode ser acelerada (de novo, para x86-64, mas, agora, com meus comentários):

bits 64

section .rodata
; Pares de bytes contendo faixas (ranges).
  align 16
_ranges:
  db 1, 0xff      ; Faixa entre (char)1 e (char)0xff.
  times 14 db 0   ; As demais "faixas" não são "usadas".

section .text

global strlen_sse42

; size_t strlen_sse42(const char* s1)
  align 16
strlen_sse42:
  xor ecx,ecx           ; Necessário. Garante que os bits
                        ; superiores, [63:5], de RCX 
                        ; estejam zerados.

  lea rax,[rdi-16]
  movdqu xmm0,[_ranges]

.loop:
  add rax,16

  ; Compara os 16 bytes do buffer apontado por RAX
  ; Com os pares de faixas em XMM0...
  ;
  ; PCMPISTRI é "Packed Compare Implicit-ending String 
  ; returning Index" ou algo assim... "implícito" 
  ; significa string terminada com '\0'.
  ;
  ; O byte de controle da instrução representa:
  ;
  ; +-+-+---+---+-+-+
  ; |0|0|0 1|1 0|0|0|-----------> 0 = char
  ; +-+-+---+---+---+             1 = short
  ;    |  |   |  |
  ;    |  |   |  +--------------> 0 = unsigned
  ;    |  |   |                   1 = signed
  ;    |  |   |
  ;    |  |   |                   00 = Equal any
  ;    |  |   |                   01 = "Ranges"
  ;    |  |   +-----------------> 10 = Equal each (string compare)
  ;    |  |                       11 = Equal ordered
  ;    |  |
  ;    |  |                       00 = Positive Polarity
  ;    |  +---------------------> 01 = Negative Polarity
  ;    |                          10 = Masked (+)
  ;    |                          11 = Masked (-)
  ;    |
  ;    +------------------------> 0 = Least significant index
  ;                               1 = Most significant index

  pcmpistri xmm0,[rax],0b0_01_01_0_0  ; LSB InRes2 offset; 
                                      ; InRes2=~InRes1; 
                                      ; Range compare; 
                                      ; unsigned char.

  jnz .loop   ; ZF=1 só se um dos bytes de [rax] for 0 
              ; (o 'i' do mnemônico pcmp(i)stri garante isso).
              ; ECX é índice (dos 16 bytes) onde achou o '\0'.
              ; (o 'i' de pcmpistr(i) garante isso).

  add rax,rcx

  lea rdx,[rdi]
  sub rax,rdx
  ret

Bem… Como é que PCMPISTRI funciona? Ela toma dois valores de 16 bytes (sim! bytes!) e os comparara de acordo com os bits de 0 a 3 do valor imediato, segundo o comentário que você pode ver acima. No caso de usarmos “unsigned char”, cada byte comparado setará ou zerará um bit de um registrador interno chamado InRes1. Depois que a comparação for feita, podemos inverter ou não o valor contido em InRes1 e colocá-lo em InRes2 – a isso é dado o nome de “polarização” (informada nos bits 4 e 5).

No caso da instrução PCMPISTRI, o bit 6 diz como o valor de ECX será calculado. Isso é feito fazendo uma varredura em InRes2 e, o primeiro bit setado, encontrado (do primeiro ao último ou vice-versa) é colocado em ECX. Se todos os bits estiverem zerados, ECX retornará 16 (será?), mas o flag ZF também estará zerado por causa do I no final do nome do mnemônico (ou seja, a instrução não achou um fim-de-string, um char ‘\0’).

Na rotina acima eu peço para PCMPISTRI comparar cada byte da string com uma faixa de bytes variando de 1 a 255. Os valores zerados na faixa nao contam porque PCMPISTRI irá parar a busca ao encontrar um ‘\0’, de qualquer maneira…

Só um aviso… existem instruções similares, como PCMPESTRI, onde o tamanho da string tem que ser informado no par EDX:EAX. Existem também PCMPISTRM e PCMPESTRM que retornam uma “máscara”, isto é, o próprio InRes2.

Outra dica importante: Essas instruções são feitas para lidar com strings e, por isso, a Intel não impõe a necessidade dos dados estarem alinhados em 16 bytes, como é comum com as instruções SSE. Alinhei _range acima só por vício mesmo… :)

Surpresa! Contar ciclos no ring0 não é tão bom assim!

Estive aqui testando um módulo para o kernel para medir os ciclos de clock gastos por uma função qualquer e comparando isso com a minha rotina para fazer o mesmo, no userspace. A rotina sob teste é simples:

/* test.c */

// Não vamos usar esse array fora daqui,
// por enquanto...
int a[100] = { 0 };

void f(void)
{
  for (int i = 1; i < 100; i++)
    a[i] = a[i-1] + 1;
}

No userspace basta usar as funções inline begin_tsc e end_tsc, como mostradas abaixo:

/* cycle_counting.h */

#ifdef __x86_64__
# define REGS1 "rbx", "rcx"
# define REGS2 "rax, "rbx", "rcx", "rdx"
#else
# ifdef __i386__
# define REGS1 "ebx", "ecx"
# define REGS2 "eax, "ebx", "ecx", "edx"
# else
#  error "Need x86-64 or i386 platforms to use cycle counting!"
# endif
#endif

unsigned long long __local_tsc;

inline void begin_tsc(void)
{
  unsigned int a, d;

  __asm__ __volatile__ ("xorl %%eax,%%eax\n"
                        "cpuid\n"
                        "rdtsc"
                        : "=a" (a), "=d" (d)
                        :: REGS1);

  __local_tsc = ((unsigned long long)d << 32) | a;
}

inline unsigned long long end_tsc(void)
{
  unsigned int a, d;

  __asm__ __volatile__ ("rdtscp\n"
                        "movl %%eax,%0\n"
                        "movl %%edx,%1\n"
                        "xorl %%eax,%%eax\n"
                        "cpuid"
                        : "=m" (a), "=m" (d)
                        :: REGS2);

  // Retorna a contagem de ciclos.
  return ((unsigned long long)d << 32) + a - __local_tsc;
}

Já para usá-las no kernelspace, temos que criar um módulo:

/* cyclemod.c */
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/hardirq.h>
#include <linux/preempt.h>
#include "cycle_counting.h"

//extern int a[];
extern void f(void);

static int __init cyclecnt_start ( void )
{
  int i;
  unsigned long flags;
  unsigned long long c;

  printk ( KERN_INFO "Loading Cycle-Counting module...\n" );

  preempt_disable();
  raw_local_irq_save(flags);

  begin_tsc();
  f();
  c = end_tsc();

  raw_local_irq_restore(flags);
  preempt_enable();

  printk ( KERN_INFO "\tCycles: %llu\n", c);

  return 0;
}

static void __exit cyclecnt_end ( void )
{
  printk ( KERN_INFO "Goodbye Cycle-Counter.\n" );
}

module_init ( cyclecnt_start );
module_exit ( cyclecnt_end );

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Frederico L. Pissarra");
MODULE_DESCRIPTION("Cycle Counting Module");

Para compilar esse bicho, crie o makefile abaixo e simplesmente execute make. Você verá diversos arquivos, mas o módulo é o com extensão .ko (kernel object).

ccflags-y := -Ofast
obj-m := cyclescount.o
cyclescounter-objs := cyclemod.o test.o

KVERSION = $(shell uname -r)

all:
  make -C /lib/modules/$(KVERSION)/build M=$(PWD) modules

clean:
  make -C /lib/modules/$(KVERSION)/build M=$(PWD) clean

A diferença na rotina acima é que desabilitamos as interrupções para o processador local (provavelmente o kernel usa apenas a instrução CLI) e a preempção (não haverá chaveamento de tarefa para essa thread)… Isso deveria eliminar algum custo que existe no userspace e nos dar uma contagem mais “precisa”, mas veja só… Não é isso o que acontece:

$ ./cnttest    # userspace app
Cycles: 552
$ sudo insmod cyclecounter.ko
$ sudo rmmod cyclecounter
$ dmesg | sed -n '/Load.\+Cycle-Count/,+2p'
[17630.739459] Loading Cycle-Counting module...
[17630.739464] 	Cycles: 748
[17630.747001] Goodbye Cycle-Counter.

Como assim, no userspace obtive uma contagem menor de ciclos do que no kernspace?

E agora, Zé?!

Wanna laugh? Ou criptografia no refúgio dos elfos?

Neste artigo vou tentar debulhar, de leve, sem detalhes profundos, o padrão AES (Advanced Encryption Standard, que pode ser obtido aqui), mas acho necessário (e inconveniente, me desculpem) explicar as duas piadinhas contidas no título:

No ano em que escrevo esse texto houve um “ataque massivo”, no mundo tudo, de um ramsonware chamado Wanna Crypt0r, que ficou conhecido como “Wanna Cry?” (Quer chorar?). Daí o quase click bait “Wanna Laugh?” (Quer rir?)… A outra piadinha é com o nome do algoritmo original do AES, chamado de “Rijndael” (junção dos nomes de seus inventores) e o refúgio dos elfos no Senhor dos Anéis, “Rivendell”. Embora a pronúncia seja diferente, a grafia é bem parecida, não?

Criptografia simétrica de blocos

O objetivo de um algoritmo de criptografia de blocos, do qual o AES faz parte, é transformar um bloco de dados original (que é chamado de plain text ou, aqui, chamarei de “texto”) em um bloco de dados criptografado (chamado de cipher — e não estou falando do sacana que traiu Neo e a turma do Morpheus em Matrix — ou “texto cifrado”, que chamarei de “cifra”), mediante uma chave. O algoritmo, é claro, “embaralha” o texto e obtém uma cifra que não seja facilmente transformada de volta em texto, a não ser que a chave correta seja fornecida.

A maioria dos algoritmos de criptografia de blocos usa blocos de tamanho fixo, tanto para o texto, quando para a cifra e a chave. É o caso do AES que vem em 3 sabores: AES-128, AES-192 e AES-256. Os valores referem-se ao tamanho da chave. Tanto o texto quanto a cifra têm tamanhos fixos de 128 bits (ou 16 bytes). Neste ponto você pode estar um pouco confuso, afinal de contas, tanto o texto quanto a chave deveriam ter tamanhos arbitrários. Acontece que o algoritmo só lida com esses tamanhos fixos e deve ser usado diversas vezes para criptografar blocos maiores. Mais adiante digo como isso pode ser feito.

Quanto à chave, se ela tiver tamanho diferente do padrão, deve-se adequá-la e existem diversos métodos para fazer isso. Um deles é usar um hash ou um valor único correspondente ao texto da chave, ao invés da própria.

Como o AES-128 funciona?

A justificativa matemática por trás do AES (ou Rijndael) é complicada. É baseada num troço chamado “campo de Galois” e não é interessante explorar isso aqui neste pequeno artigo (que, provavelmente ficará grande demais para o meu gosto), mas como ele funciona, do ponto de vista do que ele faz, é simples: Consiste em executar uma sequência de passos n vezes, de acordo com o tamanho da chave. São 10 passos para chaves de 128 bits, 12 para chaves de 192 bits e 14 para 256. Daqui por diante, o meu foco estará restrito à chaves de 128 bits. Porque é o caso mais simples e porque o meu exemplo usará as instruções AES disponíveis nos mais recentes processadores Intel.

Tanto para o texto quanto para a cifra, o bloco de 128 bits é encarado como uma matriz de 4×4 bytes onde a orientação é feita por coluna. Ou seja, o byte 0 está na posição (0,0), o byte 1 na posição (0,1), o byte 2 em (0,2) e assim por diante. AES-128 realiza um conjunto de operações tomando as matrizes do texto e chave como entrada e obtém uma matriz cifra. Na realidade a especificação chama as matrizes intermediárias de estado (state), mas prefiro encará-las como se fossem matrizes crifra intermediárias ou texto intermediárias, de acordo com o ponto de vista.

Eis, em pseudo código, o conjunto de operações que o AES-128 usa para criptografar um texto:

AddRoundKey();
for (i = 0; i < 9; i++)
{
  SubBytes();
  ShiftRows();
  MixColumns();
  AddRoundKey();
}
SubBytes();
ShiftRows();
AddRoundKey();

A operação AddRoundKey efetua a adição de cada byte do texto com cada byte da chave e obtém uma matriz intermediária. Essa “adição” é, na verdade, um “ou exclusivo” (XOR) entre os bytes (por isso o símbolo usado é ⨁). É bom notar que a primeira chamada apenas “adiciona” a chave ao texto.

Antes que a rotina acima possa ser usada outras 9 chaves são criadas com base na chave inicial, com o objetivo de adicionar entropia ao processo criptográfico. Cada chave “derivada” é usada em uma das 8 chamadas, dentro do loop, a AddRoundKey e na chamada final da mesma rotina. Esse processo de derivar novas chaves chama-se key expansion, ou expansão de chave.

Depois da primeira “adição”, a operação SubBytes efetua uma substituição dos bytes da matriz intermediária de acordo com a seguinte transformação:

\displaystyle\begin{bmatrix} y_0\\ y_1\\ y_2\\ y_3\\ y_4\\ y_5\\ y_6\\ y_7 \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}\cdot\begin{bmatrix} x_0\\ x_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\\ x_7 \end{bmatrix}+\begin{bmatrix} 1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0 \end{bmatrix}

Onde x_n corresponde ao bit n do texto e y_n ao bit n do byte “substituído”. Essa substituição não precisa ser feita com cálculo matricial, podemos usar uma tabela de substituição, chamada de Reijndael subtitution box ou “S-Box”:

unsigned char sbox[] = {
// 0     1     2     3     4     5     6     7     8     9     A     B     C     D     E     F
  0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, //0n
  0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, //1n
  0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, //2n
  0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, //3n
  0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, //4n
  0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, //5n
  0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, //6n
  0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, //7n
  0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, //8n
  0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, //9n
  0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, //An
  0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, //Bn
  0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, //Cn
  0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, //Dn
  0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, //En
  0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16  //Fn
};

Agora temos uma matriz intermediária que não lembra em nada o texto, mas AES faz mais: A operação ShiftRows embaralha as linhas fazendo a rotação de cada uma para a esquerda. A primeira linha é deixada como está, a segunda é rotacionada em 1 byte a terceira em 2 e a quarta em 3 (veja a figura abaixo)

A operação MixColumns é a parte complicada de explicar e é a parte mais intimamente ligada aos “campos de Galois”. Trata-se de multiplicação polinomial que ocorre entre as colunas da matriz intermediária (veja a especificação para entender o “atalho” usado na multiplicação matricial).

As operações do AES

No fim das contas, o bloco de 16 bytes final está criptografado. Depois dessa complicação toda, é muito difícil obter o texto a partir da cifra sem a chave e, mesmo assim, precisaremos realizar todas essas operações de forma inversa:

AddRoundKey();
for (i = 0; i < 9; i++)
{
  InvShiftRows();
  InvSubBytes();
  AddRoundKey();
  InvMixColumns();
}
InvShiftRows();
InvSubBytes();
AddRoundKey();

Onde a chave é também expandida, mas informada na ordem inversa, ou seja, o último AddRoundKey é o XOR com a chave original. As operações InvShiftRows, InvSubBytes e InvMixColumns faz a operação inversa de suas irmãs… InvShiftRows é óbvia: O que foi rotacionado para a direita será rotacionado para a esquerda. Já InvSubBytes e InvMixColumns usam as funções inversas daquelas especificadas na criptografia. Assim como SubBytes, InvSubBytes pode ser implementado por uma consulta em tabela, chamada de “Inverse Subtitution Box” ou InvS-Box:

unsigned char invsbox[] = {
// 0     1     2     3     4     5     6     7     8     9     A     B     C     D     E     F
  0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb, //0n
  0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb, //1n
  0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e, //2n
  0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25, //3n
  0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92, //4n
  0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84, //5n
  0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06, //6n
  0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b, //7n
  0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73, //8n
  0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e, //9n
  0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b, //An
  0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4, //Bn
  0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f, //Cn
  0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef, //Dn
  0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61, //En
  0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d  //Fn
};

As instruções AES

A Intel disponibiliza, em algumas arquiteturas (Haswell em diante), algumas instruções que efetuam os passos necessários para criptografar ou descriptografar blocos de 128 bits usando AES aproveitando-se do fato de que um registrador usado em SSE tem exatamente 128 bits de tamanho! A instrução AESENC  é usada para os primeiros 9 passos e AESENCLAST para o último (onde falta o MixColumns). Existe também a instrução AESKEYGENASSIST, que auxilia na expansão da chave.

Já para a de-criptografia, existem as instruções AESDEC e AESDECLAST. O único problema é que a expansão da chave é diferente para esse processo por causa da maneira como a Intel implementou essas instruções! Para facilitar o processo a instrução AESIMC (que é a mesma InvMixColumns de antes) é usada para derivar a expansão reversa da chave.

Eis um exemplo de código usando essas instruções, sob a forma de funções intrínsecas:

// Compilar usando as chaves -maes e -msse2 (se no modo i386).

#include <string.h>
#include <x86intrin.h>

// Criptografa um bloco.
#define DO_ENC_BLOCK(m,k) \
  do{ \
    m = _mm_xor_si128    (m, k[0]); \
    m = _mm_aesenc_si128 (m, k[1]); \
    m = _mm_aesenc_si128 (m, k[2]); \
    m = _mm_aesenc_si128 (m, k[3]); \
    m = _mm_aesenc_si128 (m, k[4]); \
    m = _mm_aesenc_si128 (m, k[5]); \
    m = _mm_aesenc_si128 (m, k[6]); \
    m = _mm_aesenc_si128 (m, k[7]); \
    m = _mm_aesenc_si128 (m, k[8]); \
    m = _mm_aesenc_si128 (m, k[9]); \
    m = _mm_aesenclast_si128(m, k[10]); \
  } while(0)

// Decriptografa um bloco.
#define DO_DEC_BLOCK(m,k) \
  do{ \
    m = _mm_xor_si128 (m, k[10]); \
    m = _mm_aesdec_si128 (m, k[11]); \
    m = _mm_aesdec_si128 (m, k[12]); \
    m = _mm_aesdec_si128 (m, k[13]); \
    m = _mm_aesdec_si128 (m, k[14]); \
    m = _mm_aesdec_si128 (m, k[15]); \
    m = _mm_aesdec_si128 (m, k[16]); \
    m = _mm_aesdec_si128 (m, k[17]); \
    m = _mm_aesdec_si128 (m, k[18]); \
    m = _mm_aesdec_si128 (m, k[19]); \
    m = _mm_aesdeclast_si128(m, k[0]);  \
  } while(0)

// Conterá a chave expandida e a inversa.
static __m128i key_schedule[20];

static __m128i aes_128_key_expansion(__m128i key,
                                     __m128i keygened)
{
  keygened = _mm_shuffle_epi32(keygened,
               _MM_SHUFFLE(3, 3, 3, 3));
  key = _mm_xor_si128(key, _mm_slli_si128(key, 4));
  key = _mm_xor_si128(key, _mm_slli_si128(key, 4));
  key = _mm_xor_si128(key, _mm_slli_si128(key, 4));
  return _mm_xor_si128(key, keygened);
}

#define AES_128_key_exp(k, rcon) \
  aes_128_key_expansion(k, \
    _mm_aeskeygenassist_si128(k, rcon))

// Carrega a chave e a expande.
void aes128_load_key(char *key)
{
  key_schedule[0] = _mm_loadu_si128((const __m128i *) key);

  key_schedule[1] = AES_128_key_exp(key_schedule[0], 1);
  key_schedule[2] = AES_128_key_exp(key_schedule[1], 2);
  key_schedule[3] = AES_128_key_exp(key_schedule[2], 4);
  key_schedule[4] = AES_128_key_exp(key_schedule[3], 8);
  key_schedule[5] = AES_128_key_exp(key_schedule[4], 16);
  key_schedule[6] = AES_128_key_exp(key_schedule[5], 32);
  key_schedule[7] = AES_128_key_exp(key_schedule[6], 64);
  key_schedule[8] = AES_128_key_exp(key_schedule[7], 128);
  key_schedule[9] = AES_128_key_exp(key_schedule[8], 27);
  key_schedule[10] = AES_128_key_exp(key_schedule[9], 54);

  // A expansão inversa!
  key_schedule[11] = _mm_aesimc_si128(key_schedule[9]);
  key_schedule[12] = _mm_aesimc_si128(key_schedule[8]);
  key_schedule[13] = _mm_aesimc_si128(key_schedule[7]);
  key_schedule[14] = _mm_aesimc_si128(key_schedule[6]);
  key_schedule[15] = _mm_aesimc_si128(key_schedule[5]);
  key_schedule[16] = _mm_aesimc_si128(key_schedule[4]);
  key_schedule[17] = _mm_aesimc_si128(key_schedule[3]);
  key_schedule[18] = _mm_aesimc_si128(key_schedule[2]);
  key_schedule[19] = _mm_aesimc_si128(key_schedule[1]);
}

// Faz a criptografia de um texto e obtém a cifra.
void aes128_enc(char *cipherText, char *plainText)
{
  __m128i m = _mm_loadu_si128((__m128i *) plainText);
  DO_ENC_BLOCK(m, key_schedule);
  _mm_storeu_si128((__m128i *) cipherText, m);
}

// Faz a decriptografia de uma cifra e obtém o texto.
void aes128_dec(char *plainText, char *cipherText)
{
  __m128i m = _mm_loadu_si128((__m128i *) cipherText);
  DO_DEC_BLOCK(m, key_schedule);
  _mm_storeu_si128((__m128i *) plainText, m);
}

As instruções AES da Intel são úteis em dois sentidos: As tabelas sbox e invsbox não estão visíveis porque estão dentro de seu processador e, portanto, não podem ser modificadas por um atacante. Além disso, as instruções usam SIMD, o que aceleram as coisas um cadinho.

Criptografando diversos blocos

Obviamente temos que dividir os dados que serão criptografados em blocos de 16 bytes. Cuidados devem ser tomados para o caso em que o tamanho de algum bloco seja menor que 16 bytes e algum esquema de padding deve ser feito. Fora isso, assumindo que todos os sub blocos tenham exatamente 16 bytes de tamanho, o método mais ingênuo é usar a mesma chave para todos. Esse método é chamado de ECB (Electronic CodeBook). Ele é “ingênuo” porque, com blocos diferentes do texto sendo criptografados pela mesma chave, usando o mesmo algoritmo, é possível (porém improvável) que um atacante consiga uma “dica” de qual seja a chave.

Para evitar isso, outro método bastante usado é o CBC (Cipher Block Chaining), onde o bloco cifrado anterior é usado como chave para criptografar o próximo. Junte esse encadeamento (chaining) e a complexidade do AES e fica muito difícil alguém obter alguma “dica” sobre a chave original.

O modo CBC exige, também, uma chave extra, não necessariamente secreta, e totalmente aleatória para garantir um melhor embaralhamento… chama-se IV (de Initialization Vector) e, geralmente, é criado por algum gerador de valores aleatórios criptográficos (como a instrução RDRAND, por exemplo). Daí a necessidade de usar um RNG confiável em processos de criptografia.

Existem outros esquemas, como CFB e CTR (dê uma olhada neste artigo para ver a diferença).