Base64 Längenberechnung?

153

Nach dem Lesen des base64- Wikis ...

Ich versuche herauszufinden, wie die Formel funktioniert:

Bei einer Zeichenfolge mit der Länge von nist die base64-LängeGeben Sie hier die Bildbeschreibung ein

Welches ist : 4*Math.Ceiling(((double)s.Length/3)))

Ich weiß bereits, dass die base64-Länge sein muss %4==0, damit der Decoder weiß, wie lang der ursprüngliche Text war.

Die maximale Anzahl von Auffüllungen für eine Sequenz kann =oder sein ==.

Wiki: Die Anzahl der Ausgabebytes pro Eingabebyte beträgt ungefähr 4/3 (33% Overhead)

Frage:

Wie stimmen die obigen Informationen mit der Ausgabelänge überein Geben Sie hier die Bildbeschreibung ein?

Royi Namir
quelle

Antworten:

206

Jedes Zeichen wird verwendet, um 6 Bits ( log2(64) = 6) darzustellen .

Daher werden 4 Zeichen zur Darstellung verwendet 4 * 6 = 24 bits = 3 bytes.

Sie benötigen also 4*(n/3)Zeichen, um nBytes darzustellen , und dies muss auf ein Vielfaches von 4 aufgerundet werden.

Die Anzahl der nicht verwendeten Füllzeichen, die sich aus der Aufrundung auf ein Vielfaches von 4 ergeben, beträgt offensichtlich 0, 1, 2 oder 3.

Paul R.
quelle
Woher kommt die Polsterung?
Royi Namir
1
Überlegen Sie, ob Sie ein Byte Eingabe haben. Das erzeugt vier Ausgabezeichen. Es werden jedoch nur zwei Ausgabezeichen benötigt, um die Eingabe zu codieren. Es werden also zwei Zeichen aufgefüllt.
David Schwartz
2
Die Ausgabelänge wird immer auf ein Vielfaches von 4 aufgerundet, also 1, 2 oder 3 Eingabebytes => 4 Zeichen; 4, 5 oder 6 Eingangsbytes => 8 Zeichen; 7, 8 oder 9 Eingangsbytes => 12 Zeichen.
Paul R
5
I erläuterte all dies in der Antwort oben: (i) Jeder Ausgang char repräsentiert 6 Bits von Eingängen, (ii) 4 Ausgang Zeichen stellen daher 4 * 6 = 24 Bits , (iii) 24 Bits betragen 3 Byte , (iv) 3 bytes daher von Eingang in 4 führen Zeichen des Ausgangs, (v) das Verhältnis von Ausgang Zeichen zur Eingabe Bytes ist daher 4/3
Paul R
2
@ techie_28: Ich mache es 27308 Zeichen für 20 * 1024 Bytes, aber ich habe heute Morgen noch keinen Kaffee getrunken.
Paul R
59

4 * n / 3 gibt ungepolsterte Länge.

Und runden Sie zum Auffüllen auf das nächste Vielfache von 4 auf, und da 4 eine Potenz von 2 ist, können bitweise logische Operationen verwendet werden.

((4 * n / 3) + 3) & ~3
Ren
quelle
1
Sie haben Recht! -> 4 * n / 3 ergibt ungepolsterte Länge! Die obigen Antworten sind nicht korrekt. -> ((4 * n / 3) + 3) & ~ 3 liefert das richtige Ergebnis
Cadburry
Funktioniert nicht als Eingabe für die API CryptBinaryToStringA des Fensters.
TarmoPikaro
um es für Leute zu buchstabieren, die Shell benutzen:$(( ((4 * n / 3) + 3) & ~3 ))
starfry
1
4 * n / 3schlägt bereits fehl n = 1, ein Byte wird mit zwei Zeichen codiert und das Ergebnis ist eindeutig ein Zeichen.
Maarten Bodewes
1
@Crog Wie geschrieben, wenn n = 1 ist, erhalten Sie 4/3 = 1 mit ganzen Zahlen. Wie Sie angegeben haben, ist das erwartete Ergebnis 2, nicht 1.
Maarten Bodewes
25

Als Referenz lautet die Längenformel des Base64-Encoders wie folgt:

Längenformel des Base64-Encoders

Wie Sie sagten, erzeugt ein Base64-Encoder, dem nDatenbytes gegeben sind, eine Folge von 4n/3Base64-Zeichen. Anders ausgedrückt, alle 3 Datenbytes ergeben 4 Base64-Zeichen. BEARBEITEN : Ein Kommentar weist korrekt darauf hin, dass meine vorherige Grafik das Auffüllen nicht berücksichtigt hat. Die richtige Formel lautet Ceiling(4n/3) .

Der Wikipedia-Artikel zeigt genau, wie die ASCII- Man Zeichenfolge TWFuin ihrem Beispiel in die Base64-Zeichenfolge codiert wurde . Die Eingabezeichenfolge ist 3 Byte oder 24 Bit groß, sodass die Formel korrekt vorhersagt, dass die Ausgabe 4 Byte (oder 32 Bit) lang sein wird : TWFu. Der Prozess codiert alle 6 Datenbits in eines der 64 Base64-Zeichen. Die 24-Bit-Eingabe geteilt durch 6 ergibt 4 Base64-Zeichen.

Sie fragen in einem Kommentar nach der Größe der Codierung 123456. Unter Berücksichtigung der Tatsache, dass jedes Zeichen dieser Zeichenfolge 1 Byte oder 8 Bit groß ist (unter der Annahme einer ASCII / UTF8-Codierung), codieren wir 6 Byte oder 48 Bit Daten. Nach der Gleichung erwarten wir eine Ausgangslänge von (6 bytes / 3 bytes) * 4 characters = 8 characters.

Durch das Einfügen 123456in einen Base64-Encoder werden MTIzNDU2genau wie erwartet 8 Zeichen erstellt .

David Schwartz
quelle
5
Beachten Sie bei dieser Formel, dass die gepolsterte Länge nicht angegeben wird. Sie können also eine längere Länge haben.
Spilarix
Um die erwarteten dekodierten Bytes aus dem base64-Text zu berechnen, verwende ich die Formel floor((3 * (length - padding)) / 4). Schauen Sie sich das folgende Wesentliche an .
Kurt Vangraefschepe
13

Ganzzahlen

Im Allgemeinen möchten wir keine Doubles verwenden, da wir keine Gleitkommaoperationen, Rundungsfehler usw. verwenden möchten. Sie sind einfach nicht erforderlich.

Aus diesem Grund ist es eine gute Idee, sich daran zu erinnern, wie die Deckenteilung durchgeführt wird: ceil(x / y)In Doppel kann geschrieben werden als (x + y - 1) / y(unter Vermeidung negativer Zahlen, aber Vorsicht vor Überlauf).

Lesbar

Wenn Sie sich für die Lesbarkeit entscheiden, können Sie es natürlich auch so programmieren (Beispiel in Java, für C könnten Sie natürlich Makros verwenden):

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

Gepolstert

Wir wissen, dass wir jeweils 4 Zeichenblöcke für jeweils 3 Bytes (oder weniger) benötigen. Dann lautet die Formel (für x = n und y = 3):

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

oder kombiniert:

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

Ihr Compiler optimiert das 3 - 1, lassen Sie es also einfach so, um die Lesbarkeit zu gewährleisten.

Ungepolstert

Weniger verbreitet ist die ungepolsterte Variante, dafür erinnern wir uns, dass wir jeweils ein Zeichen für jeweils 6 Bits benötigen, aufgerundet:

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

oder kombiniert:

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

wir können jedoch immer noch durch zwei teilen (wenn wir wollen):

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

Unlesbar

Falls Sie Ihrem Compiler nicht vertrauen, dass er die endgültigen Optimierungen für Sie vornimmt (oder wenn Sie Ihre Kollegen verwirren möchten):

Gepolstert

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

Ungepolstert

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

Es gibt also zwei logische Berechnungsmethoden, und wir brauchen keine Verzweigungen, Bit-Ops oder Modulo-Ops - es sei denn, wir wollen es wirklich.

Anmerkungen:

  • Offensichtlich müssen Sie möglicherweise 1 zu den Berechnungen hinzufügen, um ein Nullterminierungsbyte einzuschließen.
  • Für Mime müssen Sie sich möglicherweise um mögliche Zeilenabschlusszeichen und dergleichen kümmern (suchen Sie nach anderen Antworten dafür).
Maarten Bodewes
quelle
5

Ich denke, die gegebenen Antworten verfehlen den Punkt der ursprünglichen Frage, nämlich wie viel Speicherplatz zugewiesen werden muss, um zur base64-Codierung für eine gegebene binäre Zeichenfolge mit einer Länge von n Bytes zu passen.

Die Antwort ist (floor(n / 3) + 1) * 4 + 1

Dies umfasst das Auffüllen und ein abschließendes Nullzeichen. Möglicherweise benötigen Sie den Floor-Aufruf nicht, wenn Sie Ganzzahlarithmetik ausführen.

Inklusive Auffüllen benötigt eine base64-Zeichenfolge vier Bytes für jeden Drei-Byte-Block der ursprünglichen Zeichenfolge, einschließlich aller Teilblöcke. Ein oder zwei zusätzliche Bytes am Ende der Zeichenfolge werden weiterhin in vier Bytes in der Base64-Zeichenfolge konvertiert, wenn Padding hinzugefügt wird. Sofern Sie keine ganz bestimmte Verwendung haben, ist es am besten, die Polsterung hinzuzufügen, normalerweise ein Gleichheitszeichen. Ich habe ein zusätzliches Byte für ein Nullzeichen in C hinzugefügt, da ASCII-Zeichenfolgen ohne dieses Zeichen etwas gefährlich sind und Sie die Zeichenfolgenlänge separat tragen müssen.

Ian Nartowicz
quelle
5
Ihre Formel ist falsch. Betrachten Sie n = 3, das erwartete Ergebnis (ohne Null-Auffüllung) ist 4, aber Ihre Formel gibt 8 zurück.
CodesInChaos
5
Ich denke auch, dass es dumm ist, den Null-Terminator einzuschließen, zumal wir hier über .net sprechen.
CodesInChaos
Funktioniert in Windows mit CryptBinaryToStringA ordnungsgemäß. Meine Stimme dafür.
TarmoPikaro
5

Hier ist eine Funktion zum Berechnen der Originalgröße einer codierten Base 64-Datei als Zeichenfolge in KB:

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;
}
Pedro Silva
quelle
3

Während alle anderen über algebraische Formeln diskutieren, verwende ich lieber BASE64 selbst, um mir zu sagen:

$ 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

Die Formel von 3 Bytes, die durch 4 base64-Zeichen dargestellt werden, scheint also korrekt zu sein.

Michael Adams
quelle
1
Ich habe etwas gegen Berechnungen, die viel Speicher und CPU-Zeit erfordern, während die Berechnungen in 1 ns und einem oder zwei Registern durchgeführt werden können.
Maarten Bodewes
Wie hilft dies, wenn Sie versuchen, mit unbekannten Mengen von Binärdaten umzugehen?
UKMonkey
Die Frage dreht sich alles um Formeln, die bei der Berechnung der Ausgabegröße helfen, ohne die base64 selbst auszuführen. Obwohl diese Antwort in einigen Situationen hilfreich ist, hilft sie bei dieser Frage nicht weiter.
Alejandro
2

Mir scheint, dass die richtige Formel sein sollte:

n64 = 4 * (n / 3) + (n % 3 != 0 ? 4 : 0)
Valo
quelle
Ascii Zero Fill wird nicht berücksichtigt - funktioniert nicht unter Windows. (CryptBinaryToStringA)
TarmoPikaro
2

(In einem Versuch, eine prägnante und dennoch vollständige Ableitung zu geben.)

Jedes Eingangsbyte hat 8 Bits, also erhalten wir für n Eingangsbytes:

n × 8 Eingangsbits

Alle 6 Bits ist ein Ausgangsbyte, also:

Ceil ( n × 8/6 ) =  Ceil ( n × 4/3 ) Ausgangsbytes

Dies ist ohne Polsterung.

Mit dem Auffüllen runden wir das auf ein Vielfaches von vier Ausgabebytes auf:

Ceil ( Ceil ( n × 4/3 ) / 4) × 4 =  Ceil ( n × 4/3/4 ) × 4 =  Ceil ( n / 3) × 4 Ausgabebytes

Die erste Äquivalenz finden Sie unter Verschachtelte Abteilungen (Wikipedia).

Unter Verwendung ganzzahliger Arithmetik kann Ceil ( n / m ) als ( n + m - 1) div m berechnet werden , daher erhalten wir:

( n * 4 + 2) div 3 ohne Polsterung

( n + 2) div 3 * 4 mit Polsterung

Zur Veranschaulichung:

 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

Schließlich werden im Fall der MIME Base64-Codierung zwei zusätzliche Bytes (CR LF) pro 76 Ausgangsbytes benötigt, die auf- oder abgerundet werden, je nachdem, ob eine abschließende neue Zeile erforderlich ist.

nmatt
quelle
Vielen Dank für die detaillierte Analyse
P Satish Patro
1

Ich glaube, dass dies eine genaue Antwort ist, wenn n% 3 nicht Null ist, nein?

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

Mathematica-Version:

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

Habe Spaß

GI

igerard
quelle
1

Einfache Implementierung in Javascript

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

Schauen Sie sich für alle Personen, die C sprechen, diese beiden Makros an:

// 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) 

Von hier genommen .

Andreas
quelle
0

In Windows - ich wollte die Größe des Puffers mit der Größe mime64 schätzen, aber alle genauen Berechnungsformeln haben bei mir nicht funktioniert - habe ich schließlich eine ungefähre Formel wie diese erhalten:

Mine64-String-Zuordnungsgröße (ungefähr) = (((4 * ((binäre Puffergröße) + 1)) / 3) + 1)

Das letzte +1 - es wird für ASCII-Null verwendet - das letzte Zeichen muss zugewiesen werden, um die Null-Endung zu speichern - aber warum ist die "Binärpuffergröße" + 1 - ich vermute, dass es ein mime64-Abschlusszeichen gibt? Oder dies ist möglicherweise ein Ausrichtungsproblem.

TarmoPikaro
quelle
0

Wenn jemand daran interessiert ist, die @ Pedro Silva-Lösung in JS zu erreichen, habe ich dieselbe Lösung dafür portiert:

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
}
elverde
quelle
0

Ich sehe die vereinfachte Formel nicht in anderen Antworten. Die Logik wird behandelt, aber ich wollte eine grundlegendste Form für meine eingebettete Verwendung:

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

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

HINWEIS: Bei der Berechnung der ungepolsterten Anzahl wird die ganzzahlige Division aufgerundet, dh Divisor-1 hinzugefügt, in diesem Fall +2

Crog
quelle