5 avril 2010
++++++++++++++++++++++++++++++++++++++++
B2AA (Binary to Alphanumeric Algorithm)
++++++++++++++++++++++++++++++++++++++++
Problèmatique
--------------
On cherche avec cet algorithme à transformer un fichier binaire en fichier "texte", c'est à dire en utilisant
que les charactères : A à Z, a à z, 0 à 1 et espace à ) selon la table ascii.
Le premier codage qui pourrait nous venir à l'esprit est de prendre l'hexadecimal du charactère puis de le passer
en ASCII de cette manière :
Par exemple 0x41 qui correspond à 'A' donnerait : "41" soit 0x34x31 avec ce système.
Le problème est qu'on double la taille du flux ce qui n'est guère apréciable sur de gros transfert de données.
On cherche donc une méthode hybride.
Algorithe d'encodage
----------------------
On ne peut utiliser que les charactères suivants '0' à '1', 'A' à 'Z', 'a' à 'z' et 'espace' à ')'.
Soit en représentation hexadécimale :
0-1 : 30 - 39
A-Z : 41 - 5A (pour simplifier l'algo on utilisera 'Y' soit 59)
a-z : 61 - 7A (pour simplifier l'algo on utilisera 'y' soit 79)
espace - ) : 20 - 29
Soit 3 tables : T1, T2 et T3.
T1 correspond à la table ASCII classique et T2, T3 sont nos nouvelles tables, soit :
Nom de la table T1 T2 T3
Possiblité sur la colonne 16 16 6 9 6 9 6 9
Possiblité totale de charactère 256 324 486
On a les représentations hexadécimales possibles :
T1 | {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
| {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
| {2,3,4,5,6,7}
T2 | {0,1,2,3,4,5,6,7,8,9}
| {2,3,4,5,6,7}
| {0,1,2,3,4,5,6,7,8,9}
T3 | {2,3,4,5,6,7}
| {0,1,2,3,4,5,6,7,8,9}
T2 et T3 sont des tables à entrées de 12 bits non complètes (certaines combinaisons sont interdites).
T1 est à entrée de 8 bits (un octet, table ASCII).
Soit 3 états E1, E2 et E3, soit H[N] le poiteur vers le bloc de données avec N la taille de ce bloc.
X est une variable, I est un compteur itératif.
I = 0
E1
~~
On cherche X pour lequel H[I] = T1[X]
On permute, soit T1[X] -> T2[X]
Si I+1 = N on fait un padding, puis on passe en E3, sinon on passe en E2
E2
~~
On cherche X pour lequel H[I+1] = T1[X]
On permute, soit T1[X] -> T3[X]
Si I+1 = N, on passe en E3, sinon I = I+1 et on passe en E1
E3
~~
FIN de l'encodage
Le padding rajoute 0x979 afin d'éviter d'avoir un octet "coupé en deux". il est supprimé lors de la
lecture.
Ainsi pour 2 octets ASCII on obtient 3 octets encodés. On a donc un rajout de 1/2 octet pour un octet.
Ce qui reste acceptable surtout si on ajoute une algorithme de compression.
Il suffit de faire l'opération inverse pour décoder le bloc de données.
Exemple, on veut coder la phrase H[] = { 0x01, 0x02, 0x03, 0x04 }
H[0] = 0x01, soit H[0] = T1[1] (sur la table ASCII, on aurait eu 0x41 = 65d, on aurait T1[65])
Donc, X = 1
on permute T1[1] -> T2[1], T2[1] = 0x203
on passe en E2
H[1] = 0x02, soit H[1] = T[2] (sur la table ASCII)
Donc, X = 2
on permute T1[2] -> T3[2], T3[2] = 0x022
on passe en E1
etc...
on a ainsi 0x0102 qui est codé 0x203022 soit [ 0"].
Notes
~~~~~~
Pour un autre algorithme, voir le Base64.
(c) by www.lsdlive.org [lsdlive@lsdlive.org] 2010 (GNU GPL License)