Obliczanie długości Base64?

155

Po przeczytaniu wiki base64 ...

Próbuję dowiedzieć się, jak działa ta formuła:

Biorąc pod uwagę ciąg o długości n, długość base64 będzie wynosićwprowadź opis obrazu tutaj

Który jest : 4*Math.Ceiling(((double)s.Length/3)))

Wiem już, że długość base64 musi być taka, %4==0aby dekoder wiedział, jaka była oryginalna długość tekstu.

Maksymalna liczba wypełnienia sekwencji może wynosić =lub ==.

wiki: Liczba bajtów wyjściowych na bajt wejściowy wynosi około 4/3 (33% narzut)

Pytanie:

Jak powyższe informacje są zgodne z długością wyjściową wprowadź opis obrazu tutaj?

Royi Namir
źródło

Odpowiedzi:

210

Każdy znak reprezentuje 6 bitów ( log2(64) = 6).

Dlatego do reprezentacji używane są 4 znaki 4 * 6 = 24 bits = 3 bytes.

Potrzebujesz więc 4*(n/3)znaków do reprezentowania nbajtów, które należy zaokrąglić w górę do wielokrotności 4.

Liczba niewykorzystanych znaków wypełniających wynikająca z zaokrąglenia w górę do wielokrotności 4 będzie oczywiście wynosić 0, 1, 2 lub 3.

Paul R.
źródło
gdzie jest wypełnienie?
Royi Namir
1
Zastanów się, czy masz jeden bajt danych wejściowych. To da cztery znaki wyjścia. Ale do zakodowania danych wejściowych potrzebne są tylko dwa znaki wyjściowe. Więc dwa znaki będą wypełnione.
David Schwartz,
2
Długość wyjściowa jest zawsze zaokrąglana do wielokrotności 4, więc 1, 2 lub 3 bajty wejściowe => 4 znaki; 4, 5 lub 6 bajtów wejściowych => 8 znaków; 7, 8 lub 9 bajtów wejściowych => 12 znaków.
Paul R
5
Wyjaśniłem to wszystko w powyższej odpowiedzi: (i) każdy znak wyjściowy reprezentuje 6 bitów wejścia, (ii) 4 znaki wyjściowe reprezentują zatem 4 * 6 = 24 bity , (iii) 24 bity to 3 bajty , (iv) 3 bajty wejścia dają zatem 4 znaki wyjściowe, (v) stosunek znaków wyjściowych do bajtów wejściowych wynosi zatem 4/3.
Paul R
2
@ techie_28: Robię 27308 znaków na 20 * 1024 bajtów, ale nie piłem jeszcze kawy dziś rano.
Paul R
60

4 * n / 3 daje nieusztywnioną długość.

I zaokrąglij w górę do najbliższej wielokrotności 4 w celu wypełnienia, a ponieważ 4 to potęga 2, może używać bitowych operacji logicznych.

((4 * n / 3) + 3) & ~3
Ren
źródło
1
Masz rację! -> 4 * n / 3 daje niezakłóconą długość! powyższe odpowiedzi są nieprawidłowe. -> ((4 * n / 3) + 3) & ~ 3 zwraca właściwy wynik
Cadburry
Nie działa jako dane wejściowe dla interfejsu API okna CryptBinaryToStringA.
TarmoPikaro
aby przeliterować to dla ludzi używających powłoki:$(( ((4 * n / 3) + 3) & ~3 ))
starfry
1
4 * n / 3już się nie powiedzie n = 1, jeden bajt jest kodowany przy użyciu dwóch znaków, a wynikiem jest wyraźnie jeden znak.
Maarten Bodewes
1
@Crog Jak napisano, jeśli n = 1, otrzymasz 4/3 = 1 używając liczb całkowitych. Jak już wspomniałeś, oczekiwany wynik to 2, a nie 1.
Maarten Bodewes
25

Dla porównania, formuła długości kodera Base64 wygląda następująco:

Formuła długości kodera Base64

Jak powiedziałeś, koder Base64 z podanymi nbajtami danych wygeneruje ciąg znaków 4n/3Base64. Innymi słowy, każde 3 bajty danych dadzą 4 znaki Base64. EDYCJA : komentarz poprawnie wskazuje, że moja poprzednia grafika nie uwzględniała wypełnienia; poprawna formuła to Ceiling(4n/3) .

Artykuł w Wikipedii pokazuje dokładnie, jak łańcuch ASCII został Man zakodowany w łańcuchu Base64 TWFuw jego przykładzie. Łańcuch wejściowy 3 bajty, lub 24 bitów, w wielkości, a więc o wzorze prawidłowo przewiduje, że wyniki będą 4 bajty (32 bity) lub długi: TWFu. Proces koduje każde 6 bitów danych na jeden z 64 znaków Base64, więc 24-bitowe wejście podzielone przez 6 daje w wyniku 4 znaki Base64.

Pytasz w komentarzu, jaki 123456byłby rozmiar kodowania . Mając na uwadze, że każdy znak tego ciągu ma rozmiar 1 bajtu lub 8 bitów (zakładając kodowanie ASCII / UTF8), kodujemy 6 bajtów lub 48 bitów danych. Zgodnie z równaniem oczekujemy, że długość wyjściowa będzie wynosić (6 bytes / 3 bytes) * 4 characters = 8 characters.

Wprowadzenie 123456do kodera Base64 tworzy MTIzNDU28 znaków, tak jak oczekiwaliśmy.

David Schwartz
źródło
5
Używając tego wzoru, pamiętaj, że nie podaje on długości wyściełanej. Więc możesz mieć dłuższą długość.
Spilarix
Aby obliczyć oczekiwane zdekodowane bajty z tekstu base64, używam wzoru floor((3 * (length - padding)) / 4). Sprawdź następującą istotę .
Kurt Vangraefschepe
13

Liczby całkowite

Generalnie nie chcemy używać podwójnych, ponieważ nie chcemy używać operacji zmiennoprzecinkowych, błędów zaokrągleń itp. Po prostu nie są one potrzebne.

W tym celu warto pamiętać, jak wykonać podział sufitu: ceil(x / y)w podwójnych można zapisać jako (x + y - 1) / y(unikając liczb ujemnych, ale uważaj na przepełnienie).

Czytelny

Jeśli zależy Ci na czytelności, możesz oczywiście zaprogramować ją w ten sposób (na przykład w Javie, dla C możesz oczywiście użyć makr):

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));
    }
}

Podszewka

Watowany

Wiemy, że potrzebujemy jednocześnie 4 bloków znaków na każde 3 bajty (lub mniej). Zatem wzór wygląda następująco (dla x = n i y = 3):

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

lub połączone:

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

Twój kompilator zoptymalizuje plik 3 - 1, więc zostaw to tak, aby zachować czytelność.

Miękki

Mniej powszechny jest wariant bez wypełnienia, w tym celu pamiętamy, że każdy potrzebujemy znaku na każde 6 bitów, zaokrąglone w górę:

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

lub połączone:

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

możemy jednak jeszcze podzielić przez dwa (jeśli chcemy):

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

Nieczytelne

W przypadku, gdy nie ufasz swojemu kompilatorowi, który wykona za Ciebie ostateczne optymalizacje (lub jeśli chcesz zmylić kolegów):

Watowany

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

Miękki

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

Mamy więc dwa logiczne sposoby obliczania i nie potrzebujemy żadnych gałęzi, operacji bit-op lub modulo - chyba, że ​​naprawdę tego chcemy.

Uwagi:

  • Oczywiście może być konieczne dodanie 1 do obliczeń, aby uwzględnić zerowy bajt końcowy.
  • W przypadku Mime może być konieczne zajęcie się możliwymi znakami zakończenia linii i tym podobnymi (poszukaj innych odpowiedzi na to).
Maarten Bodewes
źródło
5

Myślę, że podane odpowiedzi pomijają sens pierwotnego pytania, czyli ile miejsca należy przydzielić, aby dopasować kodowanie base64 dla danego ciągu binarnego o długości n bajtów.

Odpowiedź to (floor(n / 3) + 1) * 4 + 1

Obejmuje to dopełnienie i kończący znak null. Możesz nie potrzebować wywołania piętra, jeśli wykonujesz arytmetykę liczb całkowitych.

Uwzględniając dopełnienie, ciąg base64 wymaga czterech bajtów na każdy trzy-bajtowy fragment oryginalnego ciągu, w tym wszystkie częściowe fragmenty. Jeden lub dwa dodatkowe bajty na końcu ciągu będą nadal konwertowane na cztery bajty w ciągu base64 po dodaniu wypełnienia. O ile nie masz bardzo konkretnego zastosowania, najlepiej jest dodać dopełnienie, zwykle znak równości. Dodałem dodatkowy bajt dla znaku null w C, ponieważ ciągi ASCII bez tego są trochę niebezpieczne i trzeba by było oddzielnie przenosić długość łańcucha.

Ian Nartowicz
źródło
5
Twoja formuła jest błędna. Rozważ n = 3, oczekiwany wynik (bez wypełnienia
zerami
5
Myślę też, że dołączenie terminatora zerowego jest głupie, zwłaszcza że mówimy tutaj o .net.
CodesInChaos
Działa poprawnie w systemie Windows, używając CryptBinaryToStringA. Mój głos na to.
TarmoPikaro
5

Oto funkcja obliczająca oryginalny rozmiar zakodowanego pliku Base 64 jako ciąg w 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
źródło
3

Podczas gdy wszyscy inni debatują nad wzorami algebraicznymi, wolałbym po prostu użyć samego BASE64, aby mi powiedzieć:

$ 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

Wygląda więc na to, że formuła 3 bajtów reprezentowanych przez 4 znaki base64 wydaje się poprawna.

Michael Adams
źródło
1
Mam coś przeciwko obliczeniom, które wymagają dużo pamięci i czasu procesora, podczas gdy obliczenia mogą być wykonywane w 1 ns i jednym lub dwóch rejestrach.
Maarten Bodewes
Więc kiedy próbujesz poradzić sobie z nieznanymi ilościami danych binarnych - jak to pomaga?
UKMonkey
Pytanie dotyczy formuł, które pomagają w obliczaniu rozmiaru wyjściowego bez wykonywania samego base64. Chociaż ta odpowiedź jest przydatna w niektórych sytuacjach, nie pomaga w przypadku tego pytania.
Alejandro,
3

(Próbując podać zwięzłe, ale pełne wyprowadzenie.)

Każdy bajt wejściowy ma 8 bitów, więc dla n bajtów wejściowych otrzymujemy:

n × 8 bitów wejściowych

Każde 6 bitów to bajt wyjściowy, więc:

ceil ( n × 8/6 ) =  ceil ( n × 4/3 ) bajty wyjściowe

To jest bez wypełnienia.

Z dopełnieniem zaokrąglamy to do wielokrotności czterech bajtów wyjściowych:

ceil ( ceil ( n × 4/3 ) / 4) × 4 =  ceil ( n × 4/3/4 ) × 4 =  ceil ( n / 3) × 4 bajty wyjściowe

Zobacz Zagnieżdżone podziały (Wikipedia), aby zapoznać się z pierwszym odpowiednikiem.

Używając arytmetyki liczb całkowitych, ceil ( n / m ) można obliczyć jako ( n + m - 1) div m , stąd otrzymujemy:

( n * 4 + 2) dział 3 bez dopełnienia

( n + 2) dział 3 * 4 z dopełnieniem

Na przykład:

 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

Wreszcie, w przypadku kodowania MIME Base64, potrzebne są dwa dodatkowe bajty (CR LF) na każde 76 bajtów wyjściowych, zaokrąglone w górę lub w dół, w zależności od tego, czy wymagany jest kończący znak nowej linii.

nmatt
źródło
Dzięki za szczegółową analizę
P Satish Patro
2

Wydaje mi się, że właściwą formułą powinno być:

n64 = 4 * (n / 3) + (n % 3 != 0 ? 4 : 0)
Valo
źródło
Ascii zero fill nie jest brane pod uwagę - nie działa w systemie Windows. (CryptBinaryToStringA)
TarmoPikaro
1

Uważam, że to jest dokładna odpowiedź, jeśli n% 3 nie jest zerem, nie?

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

Wersja Mathematica:

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

baw się dobrze

żołnierz amerykański

igerard
źródło
1

Prosta implementacja w javascript

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

Wszystkim osobom, które mówią w C, spójrz na te dwa makra:

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

Zaczerpnięte stąd .

Andreas
źródło
1

Nie widzę uproszczonej formuły w innych odpowiedziach. Logika jest omówiona, ale chciałem mieć najbardziej podstawową formę do mojego użytku osadzonego:

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

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

UWAGA: Obliczając niezmienianą liczbę zaokrąglamy w górę dzielenie liczb całkowitych, tj. Dodajemy dzielnik-1, który w tym przypadku wynosi +2

Crog
źródło
0

W oknach - chciałem oszacować rozmiar bufora o rozmiarze mime64, ale żadne precyzyjne formuły obliczeniowe nie działały dla mnie - w końcu otrzymałem przybliżony wzór taki:

Rozmiar alokacji ciągów Mine64 (przybliżony) = (((4 * ((rozmiar bufora binarnego) + 1)) / 3) + 1)

Więc ostatnie +1 - jest używane dla ascii-zero - ostatni znak musi być przydzielony do przechowywania zakończenia zerowego - ale dlaczego „binarny rozmiar bufora” to + 1 - podejrzewam, że jest jakiś znak kończący mime64? A może jest to jakiś problem z wyrównaniem.

TarmoPikaro
źródło
0

Jeśli jest ktoś zainteresowany osiągnięciem rozwiązania @Pedro Silva w JS, właśnie przeportowałem do niego to samo rozwiązanie:

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
źródło