Obliczanie długości Base64?

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ć

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ą ?

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.

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

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

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.

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

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.

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

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.

(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.

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

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

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

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

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 .

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

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.

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
}