Pedro Lamarão

No post anterior desta série, investigamos o desalinhamento entre estágios de um pipeline e o uso de padding para corrigir o alinhamento. Em resumo, se a sua fonte entrega uma quantidade qualquer de unidades e a transformação consome sempre blocos de N unidades, é necessário introduzir uma etapa intermediária para alinhamento.

Pressupondo então um source que produz uma unidade por vez e transform consome & produz uma quantidade fixa N de unidades por vez, a composição de source e tranform exige um alinhador. Vamos assumir que pad é um alinhador adequado. Algo assim, talvez?

while (flowing):
  in = source()
  in_block = pad(next_byte)
  out_block = transform(in_block)
  …

Não, isso não pode ser. Primeiramente, enquanto flowing, pad só pode produzir um bloco de N em N unidades; quando finalmente not flowing, pad deve produzir o último bloco alinhado artificialmente. Portanto, sobre pad, existe uma operação “medial” e uma operação” final”, sendo que a operação “medial” pode produzir resultado “nada” ou “bloco alinhado”.

Vamos ajustar a notação de modo que as duas operações estão definidas como acima, pad_middle e pad_final, e o estado atual do alinhador fica como exercício para o leitor.

while (flowing) {
  in = source()
  maybe_in_block = pad_middle(in)
  if (not maybe_in_block) continue
  out_block = transform(maybe_in_block)
  …
}
final_in_block = pad_final()
final_out_block = transform(final_in_block)
…

Vamos ver. Quando source a primeira unidade, pad_middle acumula e continua; isto prossegue até a unidade índice N - 1; quando chega a unidade N, pad_middle fica satisfeito e produz um bloco de tamanho N, adequado para transform. Quando flowing chega ao fim, pad_final completa as unidades faltantes pela regra de padding, produzindo o último bloco e assim por diante.

Mas, infelizmente, ainda não chegamos lá. O que acontece se flowing termina imediatamente após um bloco, ou seja, após produzir uma unidade índice múltiplo de N? Neste caso, pad_middle produziu um bloco e pad_state retorna para o estado inicial. Por acaso deveríamos produzir um final_in_block inteiramente constituído de padding?

Esta é a opção do algoritmo de alinhamento definido em PKCS #5. Sua regra grosso modo é: para um alinhador em N, calcular a quantidade P de unidades que precisa completar e então completar o último bloco com P unidades de valor P; sendo que se P = N, produzir um bloco extra conforme a regra. Ou seja, o alinhador PKCS #5 é capaz de fazer a informação crescer em um bloco inteiro, ou seja, para uma quantidade de S unidades da entrada, ele produz o quociente inteiro (S + (N - 1)) / N blocos na saída.

Certo. Como seria uma implementação para o alinhador PKCS #5?

pad_middle : ( unit ) -> ( maybe_block ) = {
  append(buffer, unit)
  increment(count)
  dispatch (count % N) {
    0       -> maybe_block = buffer
    default -> maybe_block = nothing
  }
}

pad_final : ( ) -> ( block ) = {
  padding = N - (count % N)
  for (i ∈ [1, padding])
    append(buffer, padding)
  block = buffer
}

Neste pseudo-código, buffer e count representam estado acumulado pelo alinhador: buffer um tanto de armazenagem e count a quantidade de unidades que foi “vista” pelo alinhador. Não tomamos muito cuidado para definir as operações sobre buffer porque gerenciamento de armazenagem não é o problema em pauta.

Caso o acréscimo de um bloco extra seja inaceitável então pad_final deve talvez produzir “nenhum”, de modo que:

while (flowing) {
  in = source()
  maybe_in_block = pad_middle(in)
  if (not maybe_in_block) continue
  out_block = transform(maybe_in_block)
  …
}
maybe_final_in_block = pad_final()
if (not maybe_final_in_block) return
final_out_block = transform(maybe_final_in_block)
…

Um alinhador que apenas acrescenta unidades zero sem bloco extra seria algo assim:

pad_middle : ( unit ) -> ( maybe_block ) = {
  append(buffer, unit)
  increment(count)
  dispatch (count % N) {
    0       -> maybe_block = buffer
    default -> maybe_block = nothing
  }
}

pad_final : ( ) -> ( maybe_block ) = {
  padding = N - (count % N)
  dispatch (padding) {
    N       -> maybe_block = nothing
    default -> {
      for (i ∈ [1, padding])
        append(buffer, 0)
      maybe_block = buffer
    }
  }
}

Algumas implementações exigem consumir a última unidade em pad_final. Neste caso, assim seria pad_final para alinhador PKCS #5:

pad_final : ( unit ) -> ( block ) = {
  append(buffer, unit)
  increment(count)
  padding = N - (count % N)
  for (i ∈ [1, padding])
    append(buffer, padding)
  block = buffer
}

E assim pad_final para o alinhador com zero:

pad_final : ( unit ) -> ( block ) = {
  append(buffer, unit)
  increment(count)
  padding = N - (count % N)
  for (i ∈ [1, padding])
    append(buffer, 0)
  block = buffer
}

Enquanto a implementação do alinhador PKCS #5 não se beneficia muito, a implementação do alinhador com zero se torna bem mais simples. Qual é o impacto na composição do usuário?

current = source()
while (flowing) {
  next = source()
  maybe_in_block = pad_middle(current)
  current = next
  if (not maybe_in_block) continue
  out_block = transform(maybe_in_block)
  …
}
final_in_block = pad_final(current)
final_out_block = transform(final_in_block)
…

O impacto não parece muito grande. Trata-se do acréscimo de uma espécie de “double buffering” com current e next. Observe que tivemos preguiça de lidar com o caso de começar not flowing.

Este exercício com alinhadores de bloco mostra como composições um tantinho mais complexas já exigem abandonar estruturas de controle simplórias.

Na sequência, vamos investigar uma quantidade adicional de complexidade com a introdução de objetos estruturados e a necessidade de operadores de estruturação ou desestruturação.