Ascii85

Ascii85, également appelé Base85, est une forme d'encodage binaire vers texte développé par Paul Rutter pour l'utilitaire btoa. Le fait d'utiliser cinq caractères ASCII pour représenter quatre octets de données binaires (rendant la taille codée 25 % plus grosse que l'original, en supposant que chaque caractère ASCII est représenté sur huit bits), il est plus efficace que uuencode ou Base64, qui utilisent quatre caractères pour représenter trois octets de données (ce qui fait une augmentation de taille de 33 %, en supposant que chaque caractère ASCII est représenté sur huit bits).

Ses principaux usages actuels sont les formats de fichier PostScript et Portable Document Format d'Adobe, et aussi l'encodage des correctifs pour les fichiers binaires utilisés par Git[1].

Description

Le besoin fondamental d'un encodage binaire vers texte provient du besoin de communiquer des données binaires quelconques sur des protocoles de communication préexistants qui ont été conçus pour transporter uniquement du texte lisible par un être humain et écrit en anglais. Ces protocoles de communication peuvent ne fonctionner correctement qu'avec des octets sur 7 bits (voire ne pas supporter certains codes de contrôle ASCII) ; ils peuvent ne pas supporter des lignes de texte trop longues, imposant alors l'insertion de sauts de ligne à intervalle régulier ; enfin, ils peuvent supprimer les espaces. Ainsi, seuls les 95 caractères ASCII imprimables peuvent de manière « sure » être utilisés pour transmettre des données.

Quatre octets permettent de représenter 232=4 294 967 296 valeurs possibles. Cinq chiffres en base 85 fournissent 855=4 437 053 125 valeurs possibles, ce qui suffit pour fournir une représentation unique pour chaque valeur possible de 32 bits. C'est aussi la plus petite base possible pour pouvoir représenter quatre octets en cinq caractères, car en base 84, cinq chiffres ne fournissent que 845=4 182 119 424 valeurs représentables, c'est-à-dire moins que les 232 valeurs à représenter.

Lors de l'encodage, chaque groupe de 4 octets est pris comme un nombre binaire de 32 bits, l'octet le plus significatif d'abord (Ascii85 utilise une convention gros-boutiste). Il est converti sous la forme d'un nombre de 5 chiffres en base 85, en divisant à plusieurs reprises par 85 et en prenant à chaque fois le reste de la division euclidienne. Ensuite, en partant du chiffre de poids le plus fort, à chaque chiffre est ajouté 33, puis est codé comme un caractère imprimable ASCII, ce qui donne un caractère ASCII de code compris entre 33 (!) et 117 (u).

Parce que les séries de données à zéro sont courantes, on fait une exception pour permettre leur compression : un groupe à zéro est codé comme un seul caractère z au lieu de !!!!!.

Les groupes de caractères dont la valeur décodée est supérieure à 232 - 1 (encodés en s8W-!) provoquent une erreur de décodage, tout comme les caractères z au milieu d'un groupe. Un blanc entre caractères est ignoré ; il peut apparaître n'importe où pour permettre de respecter les limitations de longueur de ligne.

L'un des inconvénients de Ascii85 est que les données ainsi encodées peuvent contenir des caractères d'échappement, comme des barres obliques inversées ou des guillemets, qui ont une signification particulière dans de nombreux langages de programmation et dans certains protocoles basés sur du texte. D'autres encodages en base 85 comme Z85 sont conçus pour pouvoir être inclus de manière sure dans du code source[2].

Historique

Version btoa

Le programme btoa initial encodait toujours des groupes complets (en complétant la source si nécessaire), et ajoutant une ligne de préfixe « xbtoa Begin », et une ligne de suffixe « xbtoa End » suivie de la longueur du fichier original (en décimal et en hexadécimal) et de 3 sommes de contrôle sur 32 bits. Le décodeur devait utiliser la longueur du fichier pour savoir quel remplissage du groupe avait été effectué. La proposition initiale de codage btoa utilisait un alphabet de codage allant du caractère "espace" jusqu'au t, mais il a été ensuite remplacé par un alphabet allant de ! à u pour éviter « les problèmes rencontrés avec certains expéditeurs (qui coupent les espaces de fin) »[3]. Ce programme a également introduit le raccourci "z pour un groupe rempli d'octets à zéro. La version 4.2 a ajouté une seconde exception y pour encode un groupe de caractères espace (0x20202020).

Version ZMODEM

LE « ZMODEM Pack-7 encoding » encode des groupes de 4 octets en groupes de 5 caractères ASCII imprimables, semblables à Ascii85. Lorsque les programmes ZMODEM envoient des fichiers de données 8 bits précomprimées sur des canaux de données 7 bits, ils utilisent le « ZMODEM Pack-7 encoding »(en) « "Recent Developments in ZMODEM" ».

Version Adobe

Adobe a adopté l'encodage btoa de base, en y apportant de légères modifications, et en le renommant en Ascii85. Les caractères utilisés sont les caractères ASCII de code compris entre 33 (!) et 117 (u) (pour représenter les 85 signes de la base 85), plus la lettre z pour représenter un mot de 32 bits égal à zéro. Les blancs sont ignorés. Adobe utilise le délimiteur ~> pour marquer la fin d'une chaîne codée en Ascii85. La longueur du fichier non encodé est implicitement précisée en tronquant le groupe final : si le dernier bloc d'octets du texte source contient moins de 4 octets, le bloc est complété par trois octets nuls avant encodage. Après encodage, on retire autant d'octets que ce qui a été ajouté pour remplissage avant encodage.

Pour décoder, l'opération inverse est effectuée : le dernier bloc est complété avec le caractère u Ascii85 pour atteindre 5 octets, et après décodage, on retire le même nombre d'octets que ce qui a été ajouté pour remplissage (voir l'exemple ci-dessous).

Remarque : le remplissage n'est pas arbitraire. La conversion de données binaires en base 64 ne fait que regrouper les bits ; il ne les modifie pas et il ne change pas leur ordre (un bit de poids fort en binaire n'affecte pas les bits de poids faible dans la représentation base64). Par contre, comme 85 n'est pas une puissance de 2, les bits de poids fort affectent les chiffres de base de poids faible85, et inversement, quand on convertit un nombre binaire en base85. Le remplissage du dernier groupe d'octets avec des bits à zéro avant encodage, et le remplissage du dernier groupe d'octets avec le signe le plus élevé de l'alphabet base85 (u) avant décodage assure que les bits de poids fort sont préservés (le remplissage zéro dans le binaire donne assez d'espace pour éviter tout risque d'addition avec « retenue »).

Dans les blocs codés en Ascii85, des espaces et des sauts de ligne peuvent apparaître n'importe où, y compris au milieu d'un bloc de 5 caractères, mais ils doivent être ignorés.

La spécification d'Adobe ne prend pas en charge l'exception y.

Version ZeroMQ (Z85)

Z85, l'algorithme d'encodage en base 85 de ZeroMQ, est une variante de Base85 qui permet d'insérer des textes encodés dans des sources de programmes informatiques ou des instructions pour interpréteur en ligne de commande. Il utilise les caractères 0...9, a...z, A...Z, ., -, :, +, =, ^, !, /, *, ?, &, <, >, (, ), [, ], {, }, @, %, $, #, évitant donc les caractères guillemet, apostrophe et barre oblique inversée[4].

Exemple d'encodage Ascii85

Prenons ces deux célèbres vers de Nicolas Boileau :

Ce qui se conçoit bien s'énonce clairement, / Et les mots pour le dire viennent aisément.

S'il est initialement codé en utilisant les caractères ISO-Latin-1, ce texte peut être réencodé comme suit en Ascii85 :

<~6Y.B[F_Mt>AKYK$DSrAjBlkJ,Bk;0)F!nl)DJsE&AKYK!@;0anD.RU,/0HSg7<BYgATJu2D
fg%CE,Tl>+DbU3A8-'q+EhI1DJj$'F<G"+F2OtoASuTB~>
Texte C e q ... e n t .
ASCII 67 101 32 113 ... 101 110 116 46
Binaire 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 ... 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0
Valeur 32 bits 1 130 700 913 = 21×854 + 56×853 + 13×852 + 33×85 + 58 ... 1 701 737 518 = 32×854 + 50×853 + 84×852 + 51×85 + 33
Base 85 (+33) 21 (54) 56 (89) 13 (46) 33 (66) 58 (91) ... 32 (65) 50 (83) 84 (117) 51 (84) 33 (66)
ASCII 6 Y . B [ ... A S u T B

Comme le dernier 4-tuple est incomplet, il faut le compléter avec trois octets à zéro :

Texte . \0 \0 \0
ASCII 46 0 0 0
Binaire 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Valeur 32 bits 771 751 936 = 14×854 + 66×853 + 56×852 + 74×85 + 46
Base 85 (+33) 14 (47) 66 (99) 56 (89) 74 (107) 46 (79)
ASCII / c Y k O

Puisqu'on a dû ajouter trois octets de remplissage en moment d'encoder, on va retirer les trois derniers caractères 'YkO' du résultat.

Le décodage est effectué de la même manière, sauf que le dernier groupe de 5 octets est complété avec des caractères 'u':

ASCII / c u u u
Base 85 (+33) 14 (47) 66 (99) 84 (117) 84 (117) 84 (117)
Valeur 32 bits 771,955,124 = 14×854 + 66×853 + 84×852 + 84×85 + 84
Binaire 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0
ASCII 46 3 25 180
Texte . [ ETX ] [ EM ] ´ (ASCII étendu)

Puisqu'on a dû compléter le texte encodé avec trois octets u, on ignore les trois derniers octets en fin de décodage, ce qui nous fait retomber sur le texte d'origine.

Comme le texte d'exemple ne contient aucune suite de 4 octets consécutifs à zéro, il n'illustre pas l'utilisation de l'abréviation z.

Compatibilité

L'encodage Ascii85 est compatible avec MIME 7 bits et 8 bits, et fait moins grossir les fichiers que Base64.

Cependant, Ascii85 peut poser un problème de compatibilité, dans la mesure où il utilise les apostrophes ('), les guillemets (""), les signes 'inférieur à' (<) et 'supérieur à' (>) et les esperluettes ((&). Les textes encodés en Ascii85 ne peuvent donc pas être utilisés tel quels dans les langages de balisage comme XML ou SGML : ils exigent d'y ajouter des caractères d'échappement.

Version RFC 1924

Publiée le 1er avril 1996, la RFC 1924 informative propose d'utiliser « une représentation compacte des adresses IPv6 ». Initiée par Robert Elz, cette RFC propose d'utiliser un ensemble de 85 caractères ASCII différent, et de faire toute l'arithmétique sur des nombres de 128 bits plutôt que 32 bits, en les convertissant en nombres de 20 chiffres en base 85 (les espaces intérieurs étant non autorisés).

Le jeu de caractères proposé est, dans l'ordre, 09, AZ, az, puis les 23 caractères !#$%&()*+-;<=>?@^_`{|}~. Le nombre représentable le plus élevé, 2128−1 = 74×8519 + 53×8518 + 5×8517 + ..., serait encodé en =r54lj&NUUO~Hi%c2ym0.

Ce jeu de caractères exclut les caractères "',./:[\] , ce qui le rend utilisable dans les chaînes JSON (où " et \ exigent un échappement). Cependant, pour les protocoles basés sur SGML, y compris notamment XML, les caractères <, > et & exigeraient malgré tout d'être échappés explicitement.

Voir aussi

Notes et références

  1. (en) Junio Hamano, « binary patch »,
  2. (en) « Z85 - ZeroMQ Base-85 Encoding Algorithm »
  3. (en) Joe Orost, « Re: COMPRESSING of binary data into mailable ASCII Re: Encoding of binary data into mailable ASCII », sur Google Groups (consulté le 11 avril 2015)
  4. (en) Pieter Hintjens, « RFC 32/Z85 - ZeroMQ Base-85 Encoding Algorithm »

Liens externes