Pedro Lamarão

No artigo anterior, fizemos um breve estudo inicial do streaming, técnica capaz de consumir uma quantidade de memória constante para operar sobre uma quantidade indeterminada de dados.

Neste artigo, vamos dar sequência ao estudo do *streaming* avaliando alguns operadores simples porém “impuros”: a operação depende de algum estado.

Para começar, vamos observar um operador “puro” de uma máquina concreta convencional.

xor : function ( x : byte, y : byte ) -> ( z : byte ) 

O operador xor consome dois bytes x e y e produz um byte z tal que, para cada índice i, o bit i de z será obtido do bits i de x e y pela regra:

(1, 1) => 0
(1, 0) => 1
(0, 1) => 1
(0, 0) => 0

O operador xor é “puro” no sentido de que sua operação depende exclusivamente de x e y. Ele se define na menor unidade de representação da máquina. Essas características garantem a máxima capacidade de composição.

Agora, vamos supor que uma aplicação usará xor como cifra para obter o sigilo de uma coisa qualquer. A aplicação usará um valor fixo de comprimento 8 bytes como chave da cifra.

cipher : function ( key : byte(8), in : byte(8) ) -> ( out : byte(8) ) = {
  for (i ∈ [1, 8])
    out[i] = xor(key(i), in(i))
}

O operador cipher também é “puro”: seu resultado depende exclusivamente de key e in. Porém, seu domínio é um pouco mais restrito: ele opera sobre unidades de 8 bytes. Esta restrição tem um impacto curioso sobre a aplicação.

Se a aplicação tem algum controle sobre o tamanho da entrada, e pode impor alinhamento em 8 bytes, então tudo bem. Se a aplicação não tem controle nenhum sobre o tamanho da entrada, então existe a possibilidade desta estar desalinhada com o operador.

Vamos supor que source é tão simples quanto um produtor de 1 byte por vez.

source : function () -> ( byte )

I/O do mundo real não se faz assim, fato que trás problemas interessantes, que já se pode vislumbrar abaixo e pretendo discutir no futuro.

Tomando os bytes produzidos por source em sequência, e agrupando de oito em oito, o caso desalinhado será representado por um último bloco incompleto. cipher não está definido para este último bloco incompleto: o domínio de cipher são blocos completos de 8 bytes.

... (1, 2, 3, 4, 5, 6, 7, 8) (1, 2, 3, 4, 5, 6, 7, 8) (1, 2, ?, ?, ?, ?, ?)

É preciso portanto introduzir outro operador no pipeline, cuja entrada é informação desalinhada e saída é informação alinhada, algum tipo de operador alinhador. No contexto de cipher, isto se chama tipicamente padding.

padding (N) : ( in : byte(N) ) -> ( out : byte(8) )

A regra de padding é preencher, de alguma maneira, um bloco incompleto de modo a produzir um bloco completo. Um padding bem simples preenche as posições incompletas com o byte zero. Isto é aceitável se source jamais produz o byte zero. A regra é simples e tediosa: caso in sejam 8 bytes, copia in para out; caso in sejam 7 bytes, copia in mais 1 byte zero para out; caso sejam 6 bytes, copia in mais 2 bytes zero para out etc. Vou evitar o pseudo-código desta regra para não precisar enveredar no que “copia” e “mais” significam.

Com um operador deste tipo, podemos compor um pipeline com os estágios abaixo:

source | padder | encipher | sink

Este pipeline é correto: todo o elo têm fonte e destino compatíveis. Em particular, padder entrega o que encipher precisa: 8 bytes.

Agora, este operador padder é mais interessante do que o operador padding. Ele deve acumular os bytes produzidos por source. A cada 8 bytes acumulados, deve encaminhar intactos para encipher. Quando source estiver esgotado, N bytes estarão acumulados. Caso N seja maior que zero, padder deve utilizar padding e encaminhar o resultado. [1]

Vamos postergar dar uma definição, mesmo em pseudo-código, para padder, por duas razões: primeiro, nosso pseudo-código ainda não é poderoso o suficiente; segundo, porque seria preciso antes disso definir o que é um estágio de pipeline, algo muito, muito interessante que quero discutir depois. O melhor que podemos fazer por enquanto é algo assim:

dispatch (fluxo) {
  próximo -> {
    state.push próximo
    dispatch (state.size) {
      8       -> { state }
      default -> { }
    }
  }
  acabou -> {
    dispatch (state.size) {
      0       -> { }
      default -> { padding(state) }
    }
  }
}

Operadores como padder são “impuros”: seu resultado depende não somente dos seus argumentos, mas, adicionalmente, de estado acumulado. Neste caso, o estado mínimo que padder precisa acumular é a efetiva quantidade total de bytes produzidos por source, de modo a calcular o preenchimento do último bloco em função do desalinhamento.

É claro que a impureza de padder não é um problema. Ocorre somente que padder não será definido no fonte do programa como uma simples rotina: será necessário usar alguma construção mais interessante capaz de representar o estado acumulado ao longo das ativações.

Por razões que não pertencem a essa discussão, operadores de cifra jamais são utilizados diretamente como sugerido acima. Mesmo operadores sérios como AES são sempre compostos por algum tipo de “modo de operação”. Vamos analisar um modo comum, o cipher block chain, ou CBC.

O propósito de CBC é modificar um operador unário, criando um novo operador com propriedades adicionais. Ele é portanto um operador de segunda ordem definido sobre um operador unário qualquer. A regra geral de CBC é esta: transforma-se in e um estado interno por xor; então transforma-se o resultado pelo operador unário; então guarda-se o resultado no estado interno, aí retorna-se este resultado. O estado interno deve ser explicitamente definido ao configurar o operador; subsequentemente, ele se define pelo resultado da ativação anterior.

CBC : function ( operator, state ) -> ( ? ) = function (in) -> (out) {
    tmp = xor(in, state)
    state = operator(tmp)
    out = state
}

A intenção do pseudo-código acima é denotar que CBC é uma função cujo retorno é um closure sobre operator e state.

Tanto padding quanto CBC têm definições em poucas linhas de português mas suas regras já não se expressam facilmente por uma simples notação de rotina ou função. Ambos são operadores impuros cuja próxima ativação depende não somente dos seus argumentos mas também de estado mantido em algum lugar. Apesar das dificuldades de expressar as regras, em ambos os casos o estado é fácil de descrever. No próximo artigo, vamos estudar casos em que o estado não se expressa facilmente.

Notas

1. Há formatos de padding que exigem que padder acrescente um bloco extra caso N seja zero.