Encoder le web

Cette semaine, c'est Jonathan qui vous propose un #KataOfTheWeek : L'encodage Base64

Briefing du Kata : ### Qu'est ce que c'est ? Base64 est un type d'encodage (comme md5, sha1, etc) qui permet d'encoder des données binaires en une chaine de caractères ASCII. Son principal avantage est de pouvoir transférer des données complexes (par exemple une image) au travers de médias ne supportant que des données textuelles (URI, inclusion d'une image directement dans un fichier CSS, …). Pour les fronteux, peut être utilisez vous un plugin de votre bundler préféré (plugin url-loader pour webpack) qui permet d'effectuer cette transformation.

Cependant, il faut noter que l'encodage Base64 n'a accès qu'aux caractères ASCII basiques et donc que les ressources encodées par ce biais pèseront environ 30% de plus que leur original.

Comment ça marche ?

Le codage Base64 utilise un alphabet de 64 caractères. La table de correspondance est la suivante :

IndexBinaryCharIndexBinaryCharIndexBinaryCharIndexBinaryChar0000000A16010000Q32100000g48110000w1000001B17010001R33100001h49110001x2000010C18010010S34100010i50110010y3000011D19010011T35100011j51110011z4000100E20010100U36100100k5211010005000101F21010101V37100101l5311010116000110G22010110W38100110m5411011027000111H23010111X39100111n5511011138001000I24011000Y40101000o5611100049001001J25011001Z41101001p57111001510001010K26011010a42101010q58111010611001011L27011011b43101011r59111011712001100M28011100c44101100s60111100813001101N29011101d45101101t61111101914001110O30011110e46101110u62111110+15001111P31011111f47101111v63111111/(padding)=

Voici en quoi consiste l'algorithme d'encodage :

1. La première étape consiste à diviser les données binaires d'entrée en n paquets de 3 octets (24 bits). Le nombre n de paquets à faire suit les règles suivantes :

• Si le nombre de bits disponibles est bien de 24 (le cas général), faire n=4 sous-paquets de 6 bits
• Sinon, si le nombre de bits disponible x est inférieur à 24 (cas possible en fin de parcours de données) :
• Si x=8 (1 seul octet) : ajouter 4 bits de zéro et former n=2 sous paquets de 6 bits.
• Si x=16 (2 octets): ajouter 2 bits de zéro et former n=3 sous paquets de 6 bits.

1. On utilise maintenant la table de correspondance pour traduire chaque sous-paquet de 6 bits formés dans l'étape précédente en un caractère de l'alphabet base64.
2. Il ne faut pas oublier de rajouter un caractère de padding '=' pour chaque octet manquant en fin de donnée :

• Pour x=8, rajouter 2 caractères de padding
• Pour x=16, en rajouter un seul

1. Le résultat est une chaîne de caractère encodée en base64 !

Par exemple (essayez de le faire vous même sur un papier !), prenons la suite binaire suivante : 01000010 01100001 01110011 01100101 00110110 00110100

1. En appliquant l'étape 1, on se retrouve avec :

• 1er paquet de 3 octets répartis en 4 sous paquets de 6 bits: 010000 100110 000101 110011
• 2ème paquet: 011001 010011 011000 110100

1. La traduction nous donne : QmFzZTY0
2. Il n'y a pas de caractère de padding à ajouter !
3. Notre chaîne de caractère encodée en base64 est donc QmFzZTY0 !

Le décodage fonctionne comme suit :

1. Pour chaque caractère de la chaîne de caractère d'entrée encodée en Base64, trouver son équivalent en binaire dans l'alphabet Base64.
2. Si le nombre de caracère de padding p est positif :

• Si p=1, enlever les deux derniers bits de la chaine binaire trouvée dans l'étape précédente.
• Si p=2, enlever les quatres derniers bits.

1. Convertir octet par octet la chaine binaire obtenue par sa valeur ascii.
2. Le résultat est la chaîne de caractère décodée !

Par exemple, si l'on décode l'exemple encodé précédemment :

1. Q = 010000 m = 100110 F = 000101 z = 110011 Z = 011001 T = 010011 Y = 011000 0 = 110100
2. Pas de caractère de padding
3. On rassemble la chaîne binaire précédente et on la sépare par octet. Puis on traduit chaque octet : 01000010 = B 01100001 = a 01110011 = s 01100101 = e 00110110 = 6 00110100 = 4
4. Le résultat est Base64 !

Le challenge

En JS par exemple, les fonctions atob() et btoa() permettent respectivement de décoder une string base64 et de créer cette string encodée en base64 à partir d'une resource binaire. Le challenge d'aujourd'hui est de proposer notre propre implémentation pour ces fonctions à partir des indications sur l'algorithme d'encodage et de décodage Base64.

Arriverez vous à trouver ce qu'il se cache derrière chacune de ces string base64 ?

→ SGVsbG8gdGFraW1hICE=

→ Vml2ZSBsZSBjb25maW5lbWVudCAh

Vu qu'on ne manipule que des strings, vous pouvez considérer que l'entrée de la fonction d'encodage ne peut être qu'une string, mais il ne faudra donc pas oublier de la convertir en chaîne binaire au préalable.

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur en JavaScript :

const ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
const BYTES_LEN = 24;
const BYTE_LEN = 8;
const ENCODE_64_LEN = 6;

class Base64 {

    static encode = (strToEncode) => {
        let binaryString = strToEncode.split('').reduce((acc, char) => {
            const binaryChar = char.charCodeAt(0).toString(2);
            return acc + '0'.repeat(BYTE_LEN - binaryChar.length) + binaryChar
        }, '');

        const missingBytes = (binaryString.length % BYTES_LEN) / BYTE_LEN;
        binaryString += (missingBytes === 1 ? '0000' : missingBytes === 2 ? '00' : '');

        let base64String = '';
        for (let i = 0; i < binaryString.length; i += ENCODE_64_LEN) {
            base64String += ALPHABET[parseInt(binaryString.substring(i, i + ENCODE_64_LEN), 2)];
        }
        return base64String + (missingBytes === 1 ? '==' : missingBytes === 2 ? '=' : '');
    };

    static decode = (str) => {
        const indexPaddingChar = str.indexOf('=');
        const nbPaddingChar = indexPaddingChar < 0 ? 0 : str.length - indexPaddingChar;

        const stringToDecode = nbPaddingChar > 0 ? str.slice(0, str.length - nbPaddingChar) : str;
        let binaryString = stringToDecode.split('').reduce((acc, char) => {
          const binaryCode = ALPHABET.indexOf(char).toString(2);
          return acc + '0'.repeat(ENCODE_64_LEN - binaryCode.length) + binaryCode;
        }, '');

        binaryString = binaryString.slice(0, binaryString.length - nbPaddingChar * 2);

        let decodedString = '';
        for (let i = 0; i < binaryString.length; i += BYTE_LEN) {
          decodedString += String.fromCharCode(parseInt(binaryString.substring(i, i + BYTE_LEN), 2));
        }
        return decodedString;
    };
};

const firstExample = 'SGVsbG8gdGFraW1hICE=';
const secondExample = 'Vml2ZSBsZSBjb25maW5lbWVudCAh';

const firstResult = Base64.decode(firstExample);
const secondResult = Base64.decode(secondExample);
console.log(`first example -> ${firstResult}`);
console.log(`second example -> ${secondResult}`);

const firstEncoded = Base64.encode(firstResult);
const secondEncoded = Base64.encode(secondResult);
console.assert(firstEncoded === firstExample, "Oups");
console.assert(secondEncoded === secondExample, "Ouch"); 

Votre équipe TakiVeille