Encodage / décodage Base91

Le Base91 est une façon d’écrire des octets quelconques en n’utilisant que des caractères ASCII imprimables, le même travail que fait le Base64, mais il place davantage de bits dans chaque caractère. Au lieu de découper l’entrée en groupes de 6 bits et d’imprimer un caractère par groupe, il accumule les bits jusqu’à en avoir au moins 13, puis imprime deux caractères qui, ensemble, désignent la valeur de ces 13 (ou 14) bits.

Deux caractères pris dans un alphabet de 91 peuvent désigner 91 × 91 = 8281 valeurs différentes, et 2¹³ = 8192 : deux caractères ont donc toujours la place de 13 bits, avec 89 valeurs à revendre. C’est toute l’astuce : 13 bits pour 2 caractères, soit 6,5 bits par caractère, contre 6 pour le Base64, et cela ne coûte qu’environ 23 % de surcharge au lieu de 33 %.

Une paire de caractères peut désigner 91 × 91 = 8281 valeurs, ce qui dépasse 2¹³ = 8192 mais reste inférieur à 2¹⁴ = 16384. Une paire peut donc toujours porter 13 bits, et parfois 14. L’encodeur essaie d’abord 13 bits : si la valeur sur 13 bits est supérieure à 88, il l’imprime sous forme de deux caractères ; sinon, il prend un 14e bit et imprime la valeur obtenue sur 14 bits.

La frontière à 88 n’a rien d’arbitraire. La plus grande valeur que deux caractères peuvent désigner est 90 + 91 × 90 = 8280, et 8192 + 89 = 8281 la dépasse déjà. Aucun groupe de 14 bits ne peut donc avoir une fenêtre basse de 13 bits égale à 89 ou plus, ce qui permet au décodeur de distinguer les deux cas en regardant la seule valeur :

Ce que voit le décodeur	Bits consommés	Pourquoi
valeur & 8191 vaut 89 à 8191	13 bits	Les valeurs à partir de 89 ne peuvent provenir que de la branche à 13 bits, car un groupe de 14 bits dont la fenêtre basse de 13 bits serait aussi haute devrait valoir au moins 8281 — ce qu’aucune paire de caractères ne peut désigner.
valeur & 8191 vaut 0 à 88	14 bits	L’encodeur ne se replie sur 14 bits que lorsque la lecture sur 13 bits valait 88 ou moins : cette branche est donc le repli, et rien d’autre.

Ce qui reste à la fin — de 1 à 13 bits — s’imprime en un caractère, plus un second caractère lorsque le reste nécessitait vraiment plus de 7 bits. C’est pourquoi la longueur encodée croît par pas de deux caractères et se termine parfois sur un nombre impair.

L’ASCII imprimable compte 94 caractères, de ! (0x21) à ~ (0x7E). Le Base91 en utilise 91, et les trois qu’il laisse de côté sont le trait d’union -, l’apostrophe ' et la barre oblique inverse \. Les lettres, les chiffres et presque toute la ponctuation figurent dans l’alphabet une seule fois, dans l’ordre du tableau ci-dessus ; les 92e à 94e caractères imprimables ne sont tout simplement pas adressables.

Comme l’alphabet suit un ordre fixe, le caractère associé à une valeur est une recherche et non une formule. Deux implémentations qui ordonnent différemment l’alphabet seront toutes deux « Base91 » sans pouvoir lire la sortie de l’autre : c’est la source la plus fréquente de résultats déroutants. Cette page affiche son alphabet, afin que la sortie puisse toujours être rattachée à lui.

Encodage	Bits par caractère	Taille par rapport à l’entrée	Remarques
Base16 (hex)	4	200%	Deux caractères par octet, immédiatement lisibles, sans alphabet à consulter.
Base32	5	160%	Insensible à la casse et sûr pour la dictée, mais le plus gaspilleur du groupe.
Base58	~5,86	~137%	Choisi pour les adresses, non pour la densité : il évite les caractères qui se ressemblent.
Base64	6	133%	La valeur par défaut partout : 4 caractères pour 3 octets, avec les 6 bits inutilisés du dernier caractère perdus.
Ascii85 / Base85	6,4	125%	5 caractères pour 4 octets, sans table de recherche, mais il divise par 85 — voir le convertisseur Ascii85.
Base91	~6,5	~123%	Le plus dense de ceux-ci : 13 bits pour 2 caractères, au prix d’un groupe de 14 bits de temps à autre.

Les pourcentages sont le coût asymptotique de chaque encodage, arrondi ; les nombres de caractères mesurés pour une entrée réelle de 92 octets figurent dans le tableau plus haut sur cette page. Le Base91 est proche du meilleur qu’un encodage puisse atteindre avec l’ASCII imprimable : 7 bits par caractère supposeraient 128 caractères distincts, ce que la plage imprimable ne peut pas fournir.

• Ce n’est pas une norme. Il n’existe pas de RFC. L’implémentation de référence est basE91 0.6.0 de Joachim Henke, publiée sous licence BSD à trois clauses ; le nom « Base91 » est aussi utilisé pour d’autres alphabets que celui-ci.
• Ce n’est pas du chiffrement. Chaque caractère est une simple réorganisation des bits d’entrée, et quiconque possède l’alphabet peut l’inverser en une seule passe.
• Ce n’est pas sûr dans une URL. L’alphabet contient #, %, &, /, ? et ", qui changent tous de sens dans une URL : la sortie Base91 doit donc être encodée en pourcentage avant d’entrer dans une chaîne de requête.
• Ce n’est pas sûr dans du HTML. Il contient aussi <, >, & et ", si bien qu’une chaîne Base91 placée dans un balisage doit être échappée avec le convertisseur d’entités HTML.
• Ce n’est pas de longueur fixe. La longueur de la sortie dépend de la configuration des bits, et pas seulement du nombre d’octets : deux entrées de même taille peuvent donc s’imprimer avec un caractère d’écart.

• L’alphabet de cette page est celui de référence. Si un autre outil produit une sortie différente pour la même entrée, comparez son alphabet avant de supposer que l’un des deux est défaillant. Les 91 caractères doivent apparaître dans le même ordre.
• Un seul caractère erroné peut modifier toute la fin. Les frontières de groupes sont décidées par les valeurs précédentes : une modification au début de la chaîne décale donc tout ce qui suit, et la fin n’est décodée qu’avec les bits restants du dernier groupe.
• Une longueur de sortie impaire est normale. Cela ne signifie pas que la chaîne a été tronquée : le dernier groupe n’imprime qu’un caractère lorsque sa valeur restante tient sur 7 bits ou moins.
• Un exemple publié peut contenir un saut de ligne que vous n’avez pas tapé. Une commande shell qui ajoute une fin de ligne est la raison habituelle pour laquelle une valeur Base91 bien connue fait un caractère de plus que le même texte produit ici : echo "Hello, World!" donne 14 octets à l’encodeur et imprime >OwJh>}AQ;r@@Y?FF, tandis que les 13 octets du seul texte impriment >OwJh>}AQ;r@@Y?F. Les deux sont corrects, pour des nombres d’octets différents, et le décompte sous la zone de sortie indique lequel vous avez en main.
• Décoder des données binaires comme du texte ne fonctionnera pas. Si les octets décodés ne sont pas de l’UTF-8 valide, il n’y a pas de texte raisonnable à afficher : c’est à cela que sert le mode de sortie hexadécimal.

« Pourquoi cette page affiche-t-elle une valeur différée d’un caractère par rapport à un autre outil Base91 ? »

Presque toujours un alphabet différent. La deuxième cause la plus fréquente est un outil qui n’utilise que la branche à 13 bits et jamais le repli à 14 bits ; cette variante est plus petite en code, mais produit une sortie différente de l’algorithme de référence utilisé ici.

Il existe aussi un cas précis qui se règle en comptant les octets, et qui explique l’exemple le plus cité de tous : un saut de ligne final. La plupart des vecteurs publiés ont été produits par une commande shell, et le shell ajoute la fin de ligne qui clôt la ligne. Les 13 octets de Hello, World! donnent 16 caractères ici, tandis que les 14 octets de Hello, World! suivis d’un saut de ligne donnent les 17 caractères >OwJh>}AQ;r@@Y?FF. Collez l’une ou l’autre valeur dans le décodage : cette page indique le nombre d’octets, si bien que les deux lectures peuvent être distinguées au lieu d’être discutées. Le bouton Exemple charge celle des deux qui correspond au lecteur que vous utilisez, et il suit le sélecteur Encoder / Décoder ainsi que le sélecteur L’entrée est / Sortie sous forme de : le lecteur de texte reçoit la valeur de 16 caractères, le lecteur hexadécimal celle de 17 caractères avec son octet 0A final bien visible, et l’encodeur reçoit le texte à encoder plutôt qu’une chaîne Base91.

« Le Base91 est-il plus petit que le Base64 ? »

Oui, d’environ 8 % de la taille encodée : 13 bits pour 2 caractères, contre 6 bits par caractère. Sur 92 octets de texte, le Base64 imprime 124 caractères et le Base91 en imprime 114.

« Puis-je décoder ceci avec un décodeur Base64, ou l’inverse ? »

Non. Les alphabets se recouvrent sur les lettres et les chiffres : un décodeur Base64 acceptera donc une chaîne Base91 comme des caractères « valides » et produira des données illisibles sans aucun signal. Les deux ne s’accordent sur rien, sauf sur la forme générale du schéma.

« La sortie se termine-t-elle par un remplissage comme le Base64 ? »

Non. Le Base91 n’a aucun caractère de remplissage : les bits restants à la fin sont imprimés comme dernier groupe, si bien qu’il n’y a rien à ajouter ni à retirer.

« Comment savoir que le résultat de cette page est juste ? »

Appuyez sur Autotest de 0 à 64 octets. Il encode et décode 130 motifs d’octets couvrant chaque longueur où la répartition 13 / 14 bits change, et compare les octets restitués aux octets saisis. Les vecteurs du bouton Exemple sont en outre contre-vérifiés par une seconde implémentation écrite pour l’outillage de test de ce site.

Cette page implémente l’algorithme de l’implémentation de référence basE91 (version 0.6.0) de Joachim Henke, distribuée sous licence BSD à trois clauses, avec l’alphabet affiché plus haut. Le décodage accepte et ignore les espaces, comme le fait l’outil de référence.

Le texte de cette page a été écrit pour ce site ; l’algorithme n’a été copié nulle part. Les valeurs du bouton Exemple sont l’exemple unique livré avec le paquet de référence (marqué « exemple de référence ») ainsi que des valeurs produites par une seconde implémentation indépendante conservée dans l’outillage de test de ce site (marquées « contre-vérification »).