Calcul de la longueur en base64?

Après avoir lu le wiki base64 ...

J'essaie de comprendre comment fonctionne la formule:

Étant donné une chaîne de longueur n, la longueur base64 sera

Lequel est : 4*Math.Ceiling(((double)s.Length/3)))

Je sais déjà que la longueur en base64 doit être %4==0pour permettre au décodeur de savoir quelle était la longueur du texte d'origine.

Le nombre maximum de remplissage pour une séquence peut être =ou ==.

wiki: le nombre d'octets de sortie par octet d'entrée est d'environ 4/3 (33% de surcharge)

Question:

Comment les informations ci-dessus s'accordent-elles avec la longueur de sortie ?

Chaque caractère est utilisé pour représenter 6 bits ( log2(64) = 6).

Par conséquent, 4 caractères sont utilisés pour représenter 4 * 6 = 24 bits = 3 bytes.

Vous avez donc besoin de 4*(n/3)caractères pour représenter les noctets, et cela doit être arrondi à un multiple de 4.

Le nombre de caractères de remplissage inutilisés résultant de l'arrondi à un multiple de 4 sera évidemment 0, 1, 2 ou 3.

4 * n / 3 donne une longueur non rembourrée.

Et arrondissez au multiple de 4 le plus proche pour le remplissage, et comme 4 est une puissance de 2, vous pouvez utiliser des opérations logiques au niveau du bit.

((4 * n / 3) + 3) & ~3

Pour référence, la formule de longueur du codeur Base64 est la suivante:

Comme vous l'avez dit, un encodeur Base64 doté d' noctets de données produira une chaîne de 4n/3caractères Base64. En d'autres termes, tous les 3 octets de données donneront 4 caractères Base64. EDIT : Un commentaire souligne correctement que mon graphique précédent ne tenait pas compte du rembourrage; la bonne formule est Ceiling(4n/3) .

L'article de Wikipedia montre exactement comment la chaîne ASCII est Man encodée dans la chaîne Base64 TWFudans son exemple. La chaîne d'entrée a une taille de 3 octets, ou 24 bits, de sorte que la formule prédit correctement que la sortie aura une longueur de 4 octets (ou 32 bits):TWFu . Le processus encode tous les 6 bits de données dans l'un des 64 caractères Base64, de sorte que l'entrée 24 bits divisée par 6 donne 4 caractères Base64.

Vous demandez dans un commentaire quelle 123456serait la taille de l'encodage . En gardant à l'esprit que chaque caractère de cette chaîne a une taille de 1 octet, ou 8 bits, (en supposant un encodage ASCII / UTF8), nous encodons 6 octets, ou 48 bits, de données. Selon l'équation, nous nous attendons à ce que la longueur de sortie soit (6 bytes / 3 bytes) * 4 characters = 8 characters.

Mettre 123456dans un encodeur Base64 crée MTIzNDU2, qui est de 8 caractères, exactement comme prévu.

Entiers

En général, nous ne voulons pas utiliser de doubles parce que nous ne voulons pas utiliser les opérations en virgule flottante, les erreurs d'arrondi, etc. Elles ne sont tout simplement pas nécessaires.

Pour cela, il est bon de se rappeler comment effectuer la division du plafond: ceil(x / y)en double peut être écrit comme(x + y - 1) / y (en évitant les nombres négatifs, mais attention aux débordements).

Lisible

Si vous optez pour la lisibilité, vous pouvez bien sûr également le programmer comme ceci (exemple en Java, pour C, vous pouvez utiliser des macros, bien sûr):

public static int ceilDiv(int x, int y) {
    return (x + y - 1) / y;
}

public static int paddedBase64(int n) {
    int blocks = ceilDiv(n, 3);
    return blocks * 4;
}

public static int unpaddedBase64(int n) {
    int bits = 8 * n;
    return ceilDiv(bits, 6);
}

// test only
public static void main(String[] args) {
    for (int n = 0; n < 21; n++) {
        System.out.println("Base 64 padded: " + paddedBase64(n));
        System.out.println("Base 64 unpadded: " + unpaddedBase64(n));
    }
}

Inline

Rembourré

Nous savons que nous avons besoin de 4 blocs de caractères à la fois pour chaque 3 octets (ou moins). Alors la formule devient (pour x = n et y = 3):

blocks = (bytes + 3 - 1) / 3
chars = blocks * 4

ou combiné:

chars = ((bytes + 3 - 1) / 3) * 4

votre compilateur optimisera le 3 - 1, alors laissez-le comme ceci pour maintenir la lisibilité.

Non rembourré

Moins commune est la variante non rembourrée, pour cela, nous nous souvenons que chacun nous avons besoin d'un caractère pour chaque 6 bits, arrondi:

bits = bytes * 8
chars = (bits + 6 - 1) / 6

ou combiné:

chars = (bytes * 8 + 6 - 1) / 6

on peut cependant encore diviser par deux (si on veut):

chars = (bytes * 4 + 3 - 1) / 3

Illisible

Si vous ne faites pas confiance à votre compilateur pour faire les optimisations finales à votre place (ou si vous voulez confondre vos collègues):

Rembourré

((n + 2) / 3) << 2

Non rembourré

((n << 2) | 2) / 3

Nous sommes donc là, deux méthodes logiques de calcul, et nous n'avons pas besoin de branches, d'opérations de bits ou d'opérations modulo - à moins que nous ne le voulions vraiment.

Remarques:

• De toute évidence, vous devrez peut-être ajouter 1 aux calculs pour inclure un octet de terminaison nul.
• Pour Mime, vous devrez peut-être faire attention aux éventuels caractères de terminaison de ligne et autres (cherchez d'autres réponses pour cela).

Je pense que les réponses données manquent le point de la question originale, à savoir combien d'espace doit être alloué pour s'adapter au codage base64 pour une chaîne binaire donnée de longueur n octets.

La réponse est (floor(n / 3) + 1) * 4 + 1

Cela inclut le remplissage et un caractère nul de fin. Vous n'aurez peut-être pas besoin de l'appel d'étage si vous faites de l'arithmétique entière.

Y compris le remplissage, une chaîne base64 nécessite quatre octets pour chaque morceau de trois octets de la chaîne d'origine, y compris les morceaux partiels. Un ou deux octets supplémentaires à la fin de la chaîne seront toujours convertis en quatre octets dans la chaîne base64 lorsque le remplissage est ajouté. Sauf si vous avez une utilisation très spécifique, il est préférable d'ajouter le remplissage, généralement un caractère égal. J'ai ajouté un octet supplémentaire pour un caractère nul en C, car les chaînes ASCII sans cela sont un peu dangereuses et vous devrez transporter la longueur de la chaîne séparément.

Voici une fonction pour calculer la taille d'origine d'un fichier Base 64 encodé sous forme de chaîne en Ko:

private Double calcBase64SizeInKBytes(String base64String) {
    Double result = -1.0;
    if(StringUtils.isNotEmpty(base64String)) {
        Integer padding = 0;
        if(base64String.endsWith("==")) {
            padding = 2;
        }
        else {
            if (base64String.endsWith("=")) padding = 1;
        }
        result = (Math.ceil(base64String.length() / 4) * 3 ) - padding;
    }
    return result / 1000;
}

Alors que tout le monde débat des formules algébriques, je préfère utiliser BASE64 lui-même pour me dire:

$ echo "Including padding, a base64 string requires four bytes for every three-byte chunk of the original string, including any partial chunks. One or two bytes extra at the end of the string will still get converted to four bytes in the base64 string when padding is added. Unless you have a very specific use, it is best to add the padding, usually an equals character. I added an extra byte for a null character in C, because ASCII strings without this are a little dangerous and you'd need to carry the string length separately."| wc -c

525

$ echo "Including padding, a base64 string requires four bytes for every three-byte chunk of the original string, including any partial chunks. One or two bytes extra at the end of the string will still get converted to four bytes in the base64 string when padding is added. Unless you have a very specific use, it is best to add the padding, usually an equals character. I added an extra byte for a null character in C, because ASCII strings without this are a little dangerous and you'd need to carry the string length separately." | base64 | wc -c

710

Il semble donc que la formule de 3 octets représentée par 4 caractères base64 semble correcte.

(Dans une tentative de donner une dérivation succincte mais complète.)

Chaque octet d'entrée a 8 bits, donc pour n octets d'entrée, nous obtenons:

n × 8 bits d'entrée

Tous les 6 bits sont un octet de sortie, donc:

ceil ( n × 8/6 ) =  ceil ( n × 4/3 ) octets de sortie

Ceci est sans rembourrage.

Avec le remplissage, nous arrondissons cela à plusieurs octets de sortie sur quatre:

ceil ( ceil ( n × 4/3 ) / 4) × 4 =  ceil ( n × 4/3/4 ) × 4 =  ceil ( n / 3) × 4 octets de sortie

Voir les divisions imbriquées (Wikipedia) pour la première équivalence.

En utilisant l'arithmétique entière, ceil ( n / m ) peut être calculé comme ( n + m - 1) div m , d'où nous obtenons:

( n * 4 + 2) div 3 sans remplissage

( n + 2) div 3 * 4 avec rembourrage

À titre d'illustration:

 n   with padding    (n + 2) div 3 * 4    without padding   (n * 4 + 2) div 3 
------------------------------------------------------------------------------
 0                           0                                      0
 1   AA==                    4            AA                        2
 2   AAA=                    4            AAA                       3
 3   AAAA                    4            AAAA                      4
 4   AAAAAA==                8            AAAAAA                    6
 5   AAAAAAA=                8            AAAAAAA                   7
 6   AAAAAAAA                8            AAAAAAAA                  8
 7   AAAAAAAAAA==           12            AAAAAAAAAA               10
 8   AAAAAAAAAAA=           12            AAAAAAAAAAA              11
 9   AAAAAAAAAAAA           12            AAAAAAAAAAAA             12
10   AAAAAAAAAAAAAA==       16            AAAAAAAAAAAAAA           14
11   AAAAAAAAAAAAAAA=       16            AAAAAAAAAAAAAAA          15
12   AAAAAAAAAAAAAAAA       16            AAAAAAAAAAAAAAAA         16

Enfin, dans le cas du codage MIME Base64, deux octets supplémentaires (CR LF) sont nécessaires tous les 76 octets de sortie, arrondis vers le haut ou vers le bas selon si une nouvelle ligne de fin est nécessaire.

Il me semble que la bonne formule devrait être:

n64 = 4 * (n / 3) + (n % 3 != 0 ? 4 : 0)

Je crois que celui-ci est une réponse exacte si n% 3 n'est pas nul, non?

    (n + 3-n%3)
4 * ---------
       3

Version Mathematica:

SizeB64[n_] := If[Mod[n, 3] == 0, 4 n/3, 4 (n + 3 - Mod[n, 3])/3]

S'amuser

GI

Implémentation simple en javascript

function sizeOfBase64String(base64String) {
    if (!base64String) return 0;
    const padding = (base64String.match(/(=*)$/) || [])[1].length;
    return 4 * Math.ceil((base64String.length / 3)) - padding;
}

Pour toutes les personnes qui parlent C, jetez un œil à ces deux macros:

// calculate the size of 'output' buffer required for a 'input' buffer of length x during Base64 encoding operation
#define B64ENCODE_OUT_SAFESIZE(x) ((((x) + 3 - 1)/3) * 4 + 1) 

// calculate the size of 'output' buffer required for a 'input' buffer of length x during Base64 decoding operation
#define B64DECODE_OUT_SAFESIZE(x) (((x)*3)/4) 

Pris d' ici .

Je ne vois pas la formule simplifiée dans d'autres réponses. La logique est couverte mais je voulais une forme la plus basique pour mon utilisation intégrée:

  Unpadded = ((4 * n) + 2) / 3

  Padded = 4 * ((n + 2) / 3)

REMARQUE: Lors du calcul du nombre non complété, nous arrondissons la division entière, c'est-à-dire ajoutons Divisor-1 qui est +2 dans ce cas

Sous Windows - je voulais estimer la taille du tampon de taille mime64, mais toutes les formules de calcul précises ne fonctionnaient pas pour moi - enfin, je me suis retrouvé avec une formule approximative comme celle-ci:

Taille d'allocation de chaîne Mine64 (approximative) = (((4 * ((taille du tampon binaire) + 1)) / 3) + 1)

Donc le dernier +1 - il est utilisé pour ascii-zéro - le dernier caractère doit être alloué pour stocker la fin de zéro - mais pourquoi "la taille du tampon binaire" est + 1 - je soupçonne qu'il y a un caractère de terminaison mime64? Ou peut-être s'agit-il d'un problème d'alignement.

S'il y a quelqu'un intéressé à réaliser la solution @Pedro Silva dans JS, je viens de porter cette même solution pour cela:

const getBase64Size = (base64) => {
  let padding = base64.length
    ? getBase64Padding(base64)
    : 0
  return ((Math.ceil(base64.length / 4) * 3 ) - padding) / 1000
}

const getBase64Padding = (base64) => {
  return endsWith(base64, '==')
    ? 2
    : 1
}

const endsWith = (str, end) => {
  let charsFromEnd = end.length
  let extractedEnd = str.slice(-charsFromEnd)
  return extractedEnd === end
}