Base84, un encodage taillé pour les noms de fichiers

Ce qui se passe

TurboCrypt chiffre les noms de fichiers et encodait le résultat en Base91 : compact, et accepté sur Unix et macOS — la contrainte n'étant pas le système de fichiers mais les applications par-dessus, le Finder en tête. Puis le support de Windows a été demandé, et Windows interdit plusieurs caractères de cet alphabet. D'où une bascule vers Base84, un encodage que personne ne semblait avoir ni défini ni utilisé.

Comment on arrive à 84

Le décompte se refait à la main :

Étape	Reste
Caractères ASCII imprimables, espace exclu	94
Moins les 9 interdits par Windows : `< > : " / \	? *`
Moins le point	84

Le point part pour deux raisons : un nom terminé par un point ne passe pas de façon fiable à travers le shell et les API Windows, et l'exclure évite au passage les noms cachés sur Unix et les cas particuliers . et ...

L'alphabet, dans l'ordre d'encodage :

TEXT

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!#$%&'()+,-;=@[]^_`{}~

L'empaquetage

L'encodeur émet des groupes de cinq caractères, et cinq est le bon nombre : 84⁵ = 4 182 119 424, soit 2,6 % sous 2³². Il regarde les 31 bits suivants ; si leur valeur est inférieure à 84⁵ − 2³¹, il y a la place d'un 32ᵉ bit, sinon il n'en consomme que 31. Sur une entrée aléatoire : 31,95 bits par groupe, soit 6,39 bits par caractère.

Encodage	Expansion moyenne	Pire cas
Base64	33,3 %	33,3 %
Base84	25,2 %	29,0 %

Le pire cas s'obtient avec une entrée remplie de 0xff, qui force chaque groupe à 31 bits. Et comme 5 divise exactement les 255 octets auxquels la plupart des systèmes plafonnent un nom, même un nom maximal ne contient que des groupes complets : 197 octets utiles, contre 191 en Base64 sans remplissage.

L'effet de bord utile

Windows réserve des noms de périphériques — CON, NUL, PRN, AUX, COM1 à COM9, LPT1 à LPT9 — quelle que soit la casse. L'empaquetage par cinq les rend inexprimables, sans traitement particulier :

une sortie de 3 caractères finit toujours par une lettre de A à J, ce qui exclut CON, PRN, AUX et NUL ;
une sortie de 4 caractères finit toujours par une majuscule ou a, b, c — jamais un chiffre — donc COM1 à COM9 et LPT1 à LPT9 sont impossibles ;
l'alphabet ne contient pas de point, donc un nom réservé suivi d'une extension ne peut pas apparaître non plus.

À retenir

Pour des noms Unix uniquement, Base84 n'est pas le bon choix : la variante filesystem de zig-base91 remplace la barre oblique par une apostrophe et descend à environ 23 % d'expansion, pour 6,51 bits par caractère. Le Base91 standard, lui, contient encore /.

Base84 n'est pas un standard mais une proposition, avec une implémentation : jedisct1/zig-base84.