Pedro Lamarão

No post anterior desta série, investigamos operadores capazes de “expandir” uma sequência de unidades em uma sequência de blocos através do acréscimo de “preenchimento” i.e. padding. Operadores deste tipo são frequentemente utilizados em composições com operadores de cifra em bloco como AES/CBC para cifrar dados de tamanho arbitrário.

source | pad(16) | aes-cbc | sink

Nosso objetivo é construir máquinas que correspondam ao modelo de uma “tubulação de dados”. Por exemplo, no caso da cifra, queremos conectar uma fonte de dados a uma máquina de cifra, por sua vez conectada a uma saída de dados. O operador pad é necessário para satisfazer o requisito da entrada da máquina de cifra: um bloco de tamanho N.

Tubulações de dados com estágios que exigem propriedades da entrada, ou impõe propriedades na saída, são comuns. No caso anterior, o operador aes-cbc impõe uma propriedade estrutural na sua entrada e na sua saída: deve ser um bloco de 16 bytes. Fora isso, este fluxo é bem simples.

Uma das simplicidades desse fluxo está na fontes: nada está dito sobre ela. Supõe-se que ela apenas cospe unidades e pronto. Este pode ser o caso, por exemplo, para fontes como um “sistema de arquivos”, que sabe muito sobre a informação armazenada, em particular o seu comprimento. Sabe-se onde começa, sabe-se onde termina, então, a fonte começa a produzir do início e termina de produzir no fim. O problema do que este “fim” significa estamos deixando para outra oportunidade.

Existem fontes de dados que não conhecem nada sobre o que está fluindo, em particular o seu comprimento. Este é o caso de uma “porta serial” que apenas entrega as unidades uma por uma indefinidamente. Ao comunicar informação por uma “porta serial”, caso uma única unidade seja suficiente para transportar a informação inteira, pois bem. Caso isso não seja verdade, caso seja necessário mais de uma unidade para transportar a informação inteira, então vejamos. Caso uma quantidade fixa de informação seja suficiente, problema resolvido: os blocos são identificados pelo comprimento. Este é o caso de um bloco cifrado AES/CBC. Caso contrário, vejamos. Caso seja possível reservar uma unidade para representar um “marcador”, problema resolvido: quando aparecer um marcador, o bloco anterior terminou, e um novo bloco será iniciado. Este é o caso de uma NTBS (null-terminated byte string), cujo valor marcador é o byte 0 (zero). De um modo geral, trata-se de conhecer onde a informação termina “antes” ou “depois”.

Caso a informação tenha tamanho variável e todas as unidades tenham significado, é preciso impor algum tipo de estrutura ao fluxo, de modo a permitir algum dos casos anteriores: conhecer o fim da informação “antes” ou “depois”.

A técnica básica para introduzir o conhecimento do fim “antes” é fazer isso literalmente, introduzir esta informação no fluxo, ou seja, impor ao fluxo um estrutura em que antes da informação está o comprimento da informação. Considere o seguinte fluxo:

3 0 0 0 4 0 0 0 0 5 1 2 3 4 5 2 0 0

Se nós interpretamos este fluxo como sendo estruturado primeiro comprimento depois informação, então, este fluxo de unidade representa o seguinte fluxo de informações:

[ 0, 0, 0 ] [ 0, 0, 0, 0 ] [ 1, 2, 3, 4, 5 ] [ 0, 0 ]

Nós somos capazes de identificar o “comprimento” dentro do fluxo com facilidade porque ele está representado em uma única unidade. Porém, é suficiente que esta meta-informação seja identificável, quer seja por conhecimento “antes” ou “depois”. Neste caso, nós temos conhecimento “antes” do seu comprimento 1 (um). Sem prejuízo algum para a técnica, qualquer comprimento fixo serve. Por exemplo, caso o comprimento 256 seja insuficiente para representar o que interessa, podemos usar um prefixo maior de duas unidades. Considere o seguinte fluxo:

0 3 0 0 0 0 4 0 0 0 0 0 5 1 2 3 4 5 0 2 0 0

Se nós interpretamos como anteriormente, exceto agora o prefixo sendo um número inteiro little endian de comprimento dois, encontramos o mesmo fluxo de informação que no caso anterior.

Vejamos como seria um operador unprefixer(N) para um prefixo simples little endian de comprimento N. O operador tem basicamente dois estados: prefixo e informação. No estado A, o operador está acumulando as unidades que compõe o prefixo, transitando para “informação” após N unidades obtidas. No estado B o operador está acumulando as unidades que compõe a informação, transitando para “prefixo” após prefix unidades obtidas.

unprefixer (unit) -> (maybe_block) {
  dispatch (state) {
    A -> {      
      append(prefix, unit)
      increment(prefix_count)
      if (prefix_count == N) { state = B }
      else { return nothing }
    }
    B -> {
      append(block, unit)
      decrement(prefix)
      if (prefix > 0) { return nothing }
      else {
        prefix_count = 0
        state = A
        return block
      }
    }
  }
}

Usamos unprefixer para construir pipelines com estágios foo que exigem uma dessas informações de tamanho variável na sua entrada.

source | unprefixer | foo | ...

Na notação procedural que estávamos usando antes, isso se parece com:

while (flowing):
  in = source()
  maybe_block = unprefixer(in)
  if (not maybe_block) continue
  etc = foo(maybe_block)
  …

A técnica básica de length-prefixing pode ser expandida para uma técnica geral de prefixing onde o prefixo transporta todo tipo de meta-informação útil. Protocolos como IP definem exatamente um “cabeçalho” de tamanho fixo que contém, além do comprimento do “pacote”, meta-informação de roteamento como remetente e destinatário. Formatos estruturados como DER aplicam uma estrutura type-length-value que permite distinguir diferentes tipos de valores, como “string”, “integer” ou “sequence”.

Nas discussões até aqui, muitas coisas nós deixamos como exercício para o leitor, como a ideia do “fim” de um fluxo, ou a ideia de um valor “nenhum” para representar o fato de que um operador ainda não está pronto para dar saída. No próximo artigo, vamos procurar investigar essas coisas e o seu impacto na definição de operadores em uma linguagem de programação real.