Cos'è il Base91?
Il Base91 è un modo di scrivere byte arbitrari usando soltanto caratteri ASCII stampabili, lo stesso compito svolto dal Base64, ma inserisce più bit in ogni carattere. Invece di dividere l'input in gruppi da 6 bit e stampare un carattere per gruppo, raccoglie i bit finché ne ha almeno 13, poi stampa due caratteri che insieme indicano il valore di quei 13 (o 14) bit.
Due caratteri di un alfabeto da 91 possono indicare 91 × 91 = 8281 valori diversi, e 213 = 8192, quindi due caratteri hanno sempre spazio per 13 bit — con 89 valori in più. È questo il trucco: 13 bit ogni 2 caratteri equivalgono a 6,5 bit per carattere, contro i 6 del Base64, e ciò porta a circa il 23% di overhead invece del 33%.
La versione in 30 secondi: test diventa fPNKd, e Hello, World! diventa >OwJh>}AQ;r@@Y?F. La decodifica è l'inverso esatto, e richiede lo stesso alfabeto di 91 caratteri — un alfabeto diverso produce un output diverso dagli stessi byte.
Da dove vengono i 13 e i 14 bit
91 × 91 = 8281 valori possono essere indicati da una coppia di caratteri, più di 213 = 8192 ma meno di 214 = 16384. Quindi una coppia di caratteri può sempre trasportare 13 bit, e a volte 14. Il codificatore prova prima con 13 bit: se il valore a 13 bit è maggiore di 88 lo stampa come due caratteri; altrimenti prende un quattordicesimo bit e stampa il valore risultante a 14 bit.
Il limite a 88 non è arbitrario. Il valore più grande che due caratteri possono indicare è 90 + 91 × 90 = 8280, e 8192 + 89 = 8281 lo supera già. Quindi nessun gruppo a 14 bit può mai avere una finestra inferiore a 13 bit pari o superiore a 89, il che significa che il decodificatore può distinguere i due casi guardando soltanto il valore:
| Cosa vede il decodificatore | Bit consumati | Perché |
|---|
| valore & 8191 è da 89 a 8191 | 13 bit | I valori da 89 in su possono provenire solo dal ramo a 13 bit, perché un gruppo a 14 bit con una finestra inferiore a 13 bit così alta dovrebbe valere almeno 8281 — che nessuna coppia di caratteri può indicare. |
| valore & 8191 è da 0 a 88 | 14 bit | Il codificatore ricorre ai 14 bit solo quando la lettura a 13 bit era 88 o meno, quindi questo ramo è il ripiego e nient'altro. |
Ciò che rimane alla fine — da 1 a 13 bit — viene stampato come un carattere, più un secondo carattere quando il resto richiedeva davvero più di 7 bit. Per questo la lunghezza codificata cresce a passi di due caratteri e a volte termina con un numero dispari di caratteri.
L'alfabeto, e i tre caratteri che esclude
L'ASCII stampabile conta 94 caratteri, da ! (0x21) a ~ (0x7E). Il Base91 ne usa 91, e i tre che lascia fuori sono il trattino -, l'apostrofo ' e la barra rovesciata \. Lettere, cifre e quasi tutta la punteggiatura compaiono nell'alfabeto esattamente una volta, nell'ordine mostrato nella tabella sopra; il 92°, il 93° e il 94° caratteri stampabili semplicemente non sono indirizzabili.
Poiché l'alfabeto ha un ordine fisso, il carattere corrispondente a un valore si trova con una ricerca e non con una formula. Due implementazioni che ordinano diversamente l'alfabeto saranno entrambe "Base91" e non sapranno leggere reciprocamente l'output dell'altra, che è la fonte più comune di risultati confusi. Questa pagina riporta il proprio alfabeto così che l'output possa sempre essere ricondotto a esso.
Il Base91 accanto alle altre codifiche stampabili
| Codifica | Bit per carattere | Dimensione rispetto all'input | Note |
|---|
| Base16 (esadecimale) | 4 | 200% | Due caratteri per byte, facilmente leggibile, nessun alfabeto da consultare. |
| Base32 | 5 | 160% | Non distingue maiuscole e minuscole e si presta alla dettatura, ma è la più dispersiva del gruppo. |
| Base58 | ~5,86 | ~137% | Scelto per gli indirizzi, non per la densità: evita i caratteri facilmente confondibili. |
| Base64 | 6 | 133% | Il default ovunque: 4 caratteri ogni 3 byte, con i 6 bit inutilizzati dell'ultimo carattere sprecati. |
| Ascii85 / Base85 | 6,4 | 125% | 5 caratteri ogni 4 byte, senza bisogno di una tabella di ricerca, ma divide per 85 — vedi il convertitore Ascii85. |
| Base91 | ~6,5 | ~123% | La più densa di queste: 13 bit ogni 2 caratteri, al costo di un blocco a 14 bit ogni tanto. |
Le percentuali sono il costo asintotico di ciascuna codifica, arrotondato; le dimensioni misurate per un input reale di 92 byte sono nella tabella più in alto in questa pagina. Il Base91 è vicino al meglio che qualsiasi codifica possa ottenere con l'ASCII stampabile: 7 bit per carattere richiederebbero 128 caratteri distinti, cosa che l'intervallo stampabile non può offrire.
Cosa il Base91 non è
- Non è uno standard. Non esiste una RFC. L'implementazione di riferimento è basE91 0.6.0 di Joachim Henke, distribuita con licenza BSD a 3 clausole; "Base91" è usato anche per alfabeti diversi da questo.
- Non è crittografia. Ogni carattere è una semplice riorganizzazione dei bit dell'input, e chiunque conosca l'alfabeto può invertirla in un solo passaggio.
- Non è sicuro per URL. L'alfabeto contiene
#, %, &, /, ? e ", tutti con un significato particolare in un URL, quindi l'output del Base91 va codificato in percentuale prima di essere inserito in una query string. - Non è sicuro per HTML. Contiene anche
<, >, & e ", quindi una stringa Base91 inserita nel markup va sottoposta a escape con il convertitore di entità HTML. - Non ha lunghezza fissa. La lunghezza dell'output dipende dalla configurazione dei bit, non solo dal numero di byte, quindi due input della stessa dimensione possono produrre un carattere di differenza.
Insidie che si presentano davvero
- L'alfabeto di questa pagina è quello di riferimento. Se un altro strumento produce output diverso per lo stesso input, confronti il proprio alfabeto prima di supporre che uno dei due sia sbagliato. I 91 caratteri devono comparire nello stesso ordine.
- Un solo carattere sbagliato può cambiare tutta la coda. I confini dei gruppi sono decisi dai valori che li precedono, quindi una modifica all'inizio della stringa sposta tutto ciò che viene dopo, e la coda viene decodificata solo con i bit residui dell'ultimo gruppo.
- Una lunghezza di output dispari è normale. Non significa che la stringa sia stata troncata; l'ultimo gruppo stampa un solo carattere quando il suo valore residuo sta in 7 bit o meno.
- Un esempio pubblicato può contenere un a capo che lei non ha digitato. Un comando di shell che aggiunge un carattere di fine riga è il motivo abituale per cui un valore Base91 noto è un carattere più lungo di quello che il testo produce qui:
echo "Hello, World!" passa al codificatore 14 byte e stampa >OwJh>}AQ;r@@Y?FF, mentre i 13 byte del solo testo stampano >OwJh>}AQ;r@@Y?F. Entrambi sono corretti, per conteggi di byte diversi, e il conteggio sotto la casella di output indica quale dei due sta tenendo. - Decodificare dati binari come testo non funziona. Se i byte decodificati non sono UTF-8 valido non c'è testo sensato da mostrare, ed è per questo che esiste la modalità di output esadecimale.
Risposte rapide
«Perché questa pagina mostra un valore che differisce di un carattere da quello di un altro strumento Base91?»
Quasi sempre per un alfabeto diverso. La seconda causa più comune è uno strumento che usa solo il ramo a 13 bit e non il ripiego a 14 bit; questa variante è più corta nel codice ma produce un output diverso dall'algoritmo di riferimento usato qui.
C'è anche un caso preciso che si può risolvere contando i byte, e spiega l'esempio più citato in assoluto: un a capo finale. La maggior parte dei valori pubblicati è stata prodotta con un comando di shell, e la shell aggiunge il carattere di fine riga che chiude la riga. I 13 byte di Hello, World! stampano qui 16 caratteri, mentre i 14 byte di Hello, World! seguiti da un a capo stampano il valore di 17 caratteri >OwJh>}AQ;r@@Y?FF. Incolli uno dei due valori in Decodifica: questa pagina riporta il conteggio dei byte, così le due letture si distinguono senza discussioni. Il pulsante Esempio carica il valore che corrisponde al lettore che sta usando, e segue l'interruttore Codifica / Decodifica e il selettore L'input è / L'output è: il lettore di testo riceve il valore di 16 caratteri, il lettore esadecimale quello di 17 caratteri con il suo byte finale 0A in bella vista, e il codificatore riceve il testo da codificare e non una stringa Base91.
«Il Base91 è più corto del Base64?»
Sì, di circa l'8% della dimensione codificata: 13 bit ogni 2 caratteri contro 6 bit per carattere. Su 92 byte di testo, il Base64 stampa 124 caratteri e il Base91 ne stampa 114.
«Posso decodificarlo con un decodificatore Base64, o viceversa?»
No. Gli alfabeti si sovrappongono nelle lettere e nelle cifre, quindi un decodificatore Base64 accetterà una stringa Base91 come caratteri "validi" e produrrà output senza senso senza segnalare errori. I due concordano soltanto sulla forma generale dello schema.
«L'output termina con un riempimento come nel Base64?»
No. Il Base91 non ha alcun carattere di riempimento: i bit residui alla fine vengono stampati come ultimo gruppo, quindi non va aggiunto né rimosso nulla.
«Come faccio a sapere che il risultato di questa pagina è corretto?»
Prema Autotest da 0 a 64 byte. Codifica e decodifica 130 sequenze di byte che coprono ogni lunghezza in cui cambia la suddivisione tra 13 e 14 bit, e confronta i byte ottenuti con quelli inseriti. I valori del pulsante Esempio sono inoltre verificati incrociatamente con una seconda implementazione scritta per gli strumenti di test di questo sito.
Standard e crediti
Questa pagina implementa l'algoritmo dell'implementazione di riferimento basE91 (versione 0.6.0) di Joachim Henke, distribuita con licenza BSD a 3 clausole, con l'alfabeto riportato sopra. La decodifica accetta e ignora gli spazi, come fa lo strumento di riferimento.
Il testo della pagina è stato scritto per questo sito; l'algoritmo non è stato copiato da nessuna parte. I valori del pulsante Esempio sono l'unico esempio incluso nel pacchetto di riferimento (contrassegnato come "esempio di riferimento") più valori prodotti da una seconda implementazione indipendente conservata negli strumenti di test di questo sito (contrassegnati come "verifica incrociata").
