O que é o Base91?
O Base91 é uma forma de escrever bytes arbitrários usando apenas caracteres ASCII imprimíveis, o mesmo trabalho que o Base64 faz, mas encaixa mais bits em cada carácter. Em vez de cortar a entrada em grupos de 6 bits e imprimir um carácter por grupo, junta bits até ter pelo menos 13, e depois imprime dois caracteres que juntos nomeiam o valor desses 13 (ou 14) bits.
Dois caracteres de um alfabeto de 91 conseguem nomear 91 × 91 = 8281 valores diferentes, e 213 = 8192, por isso dois caracteres têm sempre espaço para 13 bits — com 89 valores de sobra. Esse é todo o truque: 13 bits por 2 caracteres são 6,5 bits por carácter, contra os 6 do Base64, e isso dá cerca de 23% de sobrecarga em vez de 33%.
A versão de 30 segundos: test torna-se fPNKd, e Hello, World! torna-se >OwJh>}AQ;r@@Y?F. A descodificação é o inverso exato, e precisa do mesmo alfabeto de 91 caracteres — um alfabeto diferente dá uma saída diferente a partir dos mesmos bytes.
De onde vêm os 13 e os 14 bits
91 × 91 = 8281 valores podem ser nomeados por um par de caracteres, o que é mais do que 213 = 8192 mas menos do que 214 = 16384. Por isso um par de caracteres pode sempre transportar 13 bits, e às vezes 14. O codificador tenta primeiro 13 bits: se o valor de 13 bits for maior do que 88, imprime esse valor como dois caracteres; caso contrário, toma um 14.º bit e imprime o valor resultante de 14 bits.
A fronteira em 88 não é arbitrária. O maior valor que dois caracteres conseguem nomear é 90 + 91 × 90 = 8280, e 8192 + 89 = 8281 já o ultrapassa. Por isso nenhum grupo de 14 bits pode ter uma janela inferior de 13 bits igual ou superior a 89, o que significa que o descodificador consegue distinguir os dois casos olhando apenas para o próprio valor:
| O que o descodificador vê | Bits consumidos | Porquê |
|---|
| valor & 8191 está entre 89 e 8191 | 13 bits | Valores a partir de 89 só podem vir do ramo de 13 bits, porque um grupo de 14 bits com uma janela inferior de 13 bits tão alta teria de ser pelo menos 8281 — o que nenhum par de caracteres consegue nomear. |
| valor & 8191 está entre 0 e 88 | 14 bits | O codificador só recorre aos 14 bits quando a leitura de 13 bits foi 88 ou menos, por isso este ramo é o recurso e mais nada. |
O que sobra no fim — entre 1 e 13 bits — é impresso como um carácter, mais um segundo carácter quando o resto realmente precisava de mais de 7 bits. É por isso que o comprimento codificado cresce em passos de dois caracteres e às vezes termina numa contagem ímpar.
O alfabeto, e os três caracteres que deixa de fora
O ASCII imprimível tem 94 caracteres, de ! (0x21) a ~ (0x7E). O Base91 usa 91 deles, e os três que deixa de fora são o hífen -, o apóstrofo ' e a barra invertida \. Letras, dígitos e quase toda a pontuação estão no alfabeto exatamente uma vez, pela ordem mostrada na tabela acima; o 92.º a o 94.º caracteres imprimíveis simplesmente não são endereçáveis.
Como o alfabeto tem uma ordem fixa, o carácter de um valor é uma consulta e não uma fórmula. Duas implementações que ordenem o alfabeto de forma diferente serão ambas « Base91 » e não conseguirão ler a saída uma da outra, que é a fonte mais comum de resultados confusos. Esta página imprime o seu alfabeto para que a saída possa ser sempre rastreada até ele.
Base91 ao lado das outras codificações imprimíveis
| Codificação | Bits por carácter | Tamanho face à entrada | Notas |
|---|
| Base16 (hex) | 4 | 200% | Dois caracteres por byte, trivialmente legível, sem alfabeto para consultar. |
| Base32 | 5 | 160% | Não distingue maiúsculas e é seguro para ditado humano, mas é o mais desperdiçador do grupo. |
| Base58 | ~5,86 | ~137% | Escolhido para endereços, não para densidade: evita caracteres parecidos. |
| Base64 | 6 | 133% | O predefinido em todo o lado: 4 caracteres por cada 3 bytes, com os 6 bits não usados do último carácter desperdiçados. |
| Ascii85 / Base85 | 6,4 | 125% | 5 caracteres por 4 bytes, sem tabela de consulta, mas divide por 85 — ver o conversor Ascii85. |
| Base91 | ~6,5 | ~123% | O mais denso destes: 13 bits por 2 caracteres, ao custo de um grupo de 14 bits aqui e ali. |
As percentagens são o custo assintótico de cada codificação, arredondado; as contagens de caracteres medidas para uma entrada real de 92 bytes estão na tabela mais acima nesta página. O Base91 está perto do melhor que qualquer codificação consegue fazer com ASCII imprimível: 7 bits por carácter exigiriam 128 caracteres distintos, o que a gama imprimível não consegue oferecer.
O que o Base91 não é
- Não é uma norma. Não há RFC. A implementação de referência é a basE91 0.6.0 de Joachim Henke, distribuída sob a licença BSD de 3 cláusulas; « Base91 » é também usado para alfabetos que não são este.
- Não é encriptação. Cada carácter é uma reformatação direta dos bits de entrada, e quem tiver o alfabeto reverte-a numa só passagem.
- Não é seguro para URL. O alfabeto contém
#, %, &, /, ? e ", todos com significado especial num URL, por isso a saída Base91 tem de ser codificada em percentagem antes de entrar numa query string. - Não é seguro para HTML. Contém também
<, >, & e ", por isso uma cadeia Base91 colocada em marcação tem de ser escapada com o conversor de entidades HTML. - Não tem comprimento fixo. O comprimento da saída depende do padrão de bits, não apenas do número de bytes, por isso duas entradas do mesmo tamanho podem imprimir-se com um carácter de diferença.
Armadilhas que de facto mordem
- O alfabeto desta página é o de referência. Se outra ferramenta produzir saída diferente para a mesma entrada, compare o alfabeto dela antes de assumir que um dos lados está avariado. Os 91 caracteres têm de aparecer pela mesma ordem.
- Um único carácter errado pode mudar toda a cauda. As fronteiras dos grupos são decididas pelos valores que vieram antes, por isso uma edição no início da cadeia desloca tudo o que vem depois, e a cauda é descodificada apenas com os bits que sobram do último grupo.
- Um comprimento de saída ímpar é normal. Não quer dizer que a cadeia foi cortada; o grupo final imprime um carácter quando o valor que sobra cabe em 7 bits ou menos.
- Um exemplo publicado pode trazer uma quebra de linha que não escreveu. Um comando de shell que acrescenta um fim de linha é a razão habitual para um valor Base91 bem conhecido ter um carácter a mais do que o mesmo texto produz aqui:
echo "Hello, World!" entrega ao codificador 14 bytes e imprime >OwJh>}AQ;r@@Y?FF, enquanto os 13 bytes só do texto imprimem >OwJh>}AQ;r@@Y?F. Ambos estão corretos, para contagens de bytes diferentes, e a contagem por baixo da caixa de saída diz qual dos dois tem na mão. - Descodificar dados binários como texto não funciona. Se os bytes descodificados não forem UTF-8 válido, não há texto sensato para mostrar, e é para isso que serve o modo de saída hexadecimal.
Respostas rápidas
« Porque é que esta página mostra um valor com um carácter de diferença em relação a outra ferramenta Base91? »
Quase sempre um alfabeto diferente. A segunda causa mais comum é uma ferramenta que só usa o ramo de 13 bits e nunca o recurso de 14 bits; essa variante é mais pequena em código mas produz saída diferente do algoritmo de referência usado aqui.
Há também um caso exato que se resolve contando bytes, e que explica o exemplo mais citado de todos: uma quebra de linha final. A maioria dos vetores publicados foi produzida por um comando de shell, e a shell acrescenta o fim de linha que termina a linha. Os 13 bytes de Hello, World! imprimem 16 caracteres aqui, enquanto os 14 bytes de Hello, World! seguidos de uma quebra de linha imprimem o carácter 17 >OwJh>}AQ;r@@Y?FF. Cole qualquer um dos valores em Descodificar: esta página indica a contagem de bytes, para que as duas leituras possam ser distinguidas em vez de discutidas. O botão Exemplo carrega o que pertence ao leitor que está a usar, e segue o comutador Codificar / Descodificar e o seletor A entrada é / Saída como: o leitor de texto recebe o valor de 16 caracteres, o leitor hexadecimal recebe o de 17 caracteres com o seu byte final 0A à vista, e o codificador recebe o texto a codificar em vez de uma cadeia Base91.
« O Base91 é menor do que o Base64? »
Sim, em cerca de 8% do tamanho codificado: 13 bits por 2 caracteres contra 6 bits por carácter. Em 92 bytes de texto, o Base64 imprime 124 caracteres e o Base91 imprime 114.
« Posso descodificar isto com um descodificador Base64, ou ao contrário? »
Não. Os alfabetos sobrepõem-se nas letras e nos dígitos, por isso um descodificador Base64 aceitará uma cadeia Base91 como caracteres « válidos » e produzirá lixo em silêncio. Os dois só concordam na forma geral do esquema.
« A saída termina com preenchimento como o Base64? »
Não. O Base91 não tem nenhum carácter de preenchimento: os bits que sobram no fim são impressos como o último grupo, por isso nada tem de ser acrescentado nem retirado.
« Como sei que o resultado desta página está certo? »
Prima Autoteste de 0 a 64 bytes. Codifica e descodifica 130 padrões de bytes que cobrem todos os comprimentos onde a divisão de 13 e 14 bits muda, e compara os bytes que voltam com os que entraram. Os vetores do botão Exemplo são ainda verificados contra uma segunda implementação escrita para as ferramentas de teste deste site.
Normas e créditos
Esta página implementa o algoritmo da implementação de referência basE91 (versão 0.6.0) de Joachim Henke, distribuída sob a licença BSD de 3 cláusulas, com o alfabeto impresso acima. A descodificação aceita e ignora os espaços em branco, como a ferramenta de referência.
O texto desta página foi escrito para este site; o algoritmo não foi copiado de lado nenhum. Os valores do botão Exemplo são o único exemplo que vem com o pacote de referência (assinalado como « exemplo de referência ») mais valores produzidos por uma segunda implementação independente, guardada nas ferramentas de teste deste site (assinalados como « verificação cruzada »).
