Base64: Jaki jest najgorszy możliwy wzrost wykorzystania przestrzeni?

168

Jeśli serwer otrzymał łańcuch base64 i chciał sprawdzić jego długość przed konwersją, powiedzmy, że chciał, aby końcowa tablica bajtów zawsze miała 16 KB. Jak duża może być tablica bajtów 16 KB po przekonwertowaniu na łańcuch Base64 (zakładając, że jeden bajt na znak)?

base64 expansion

— Bryan Field
źródło

245

Base64 koduje każdy zestaw trzech bajtów na cztery bajty. Ponadto dane wyjściowe są dopełniane, aby zawsze były wielokrotnością czterech.

Oznacza to, że rozmiar reprezentacji base-64 łańcucha o rozmiarze n wynosi:

ceil(n / 3) * 4

Tak więc dla tablicy 16kB reprezentacja base-64 będzie miała wartość ceil (16 * 1024/3) * 4 = długość 21848 bajtów ~ = 21,8kB.

Z grubsza można przyjąć, że rozmiar danych został zwiększony do 4/3 oryginału.

— R. Martinho Fernandes
źródło

Czy musimy dodać 2 do długości, czy nie?

— vIceBerg

@vIceBerg, to zależy od tego, czy korzystasz ceilz floatnumerami, lub po prostu intnumery. (i nie ceil)

— Bryan Field

7

Wydaje mi się, że prostszym sposobem jest dodanie 1/3 oryginalnego rozmiaru.

— mvmn

1

W zaproponowanym przykładzie pokazanie wyniku w tej samej kolejności podniosłoby nieco jakość odpowiedzi (21,3 KB zamiast 21848 bajtów).

— Ivan De Paz Centeno

36

Z Wikipedii

Zauważ, że przy danych wejściowych n bajtów, wyjście będzie miało długość (n + 2 - ((n + 2)% 3)) / 3 * 4 bajty, tak że liczba bajtów wyjściowych na bajt wejściowy zbiega się do 4/3 lub 1.33333 dla dużych n.

Zatem 16 kb * 4/3 daje niewiele ponad 21,3 kb, czyli, mówiąc ściślej, 21848 bajtów.

Mam nadzieję że to pomoże

— Binary Worrier
źródło

11

16 kb to 131072 bity. Base64 pakuje 24-bitowe bufory w cztery 6-bitowe znaki, więc masz 5462 * 4 = 21848 bajtów.

— Chris Heald
źródło

5

Ponieważ pytanie dotyczyło najgorszego możliwego wzrostu, muszę dodać, że zazwyczaj są przerwy między wierszami co około 80 znaków. Oznacza to, że jeśli zapisujesz dane zakodowane w base64 do pliku tekstowego w systemie Windows, doda to 2 bajty, w systemie Linux 1 bajt na każdy wiersz.

Wzrost w stosunku do faktycznego kodowania został opisany powyżej.

— Zsolt Sky
źródło

3

Czy nie jest to skrajny przypadek, że 1 bajt źródłowy staje się 4 bajtami base64, a więc 4x wzrost? Każdy dłuższy materiał źródłowy uzyskuje lepszy stosunek, dopóki, jak powiedzieli inni, asymptotycznie zbliża się do 1,333 ...

— Olie

1

To jest dla mnie odniesienie w przyszłości. Ponieważ pytanie jest najgorsze przypadku, powinniśmy wziąć pod uwagę podziały wierszy. Podczas gdy RFC 1421 definiuje maksymalną długość linii na 64 znaki, RFC 2045 (MIME) stwierdza, że w jednym wierszu będzie maksymalnie 76 znaków.

To ostatnie jest tym, co zaimplementowała biblioteka C #. Więc w środowisku Windows, gdzie koniec linii to 2 znaki (\ r \ n), otrzymujemy to:Length = Floor(Ceiling(N/3) * 4 * 78 / 76)

Uwaga: Podłoga jest taka, ponieważ podczas mojego testu z C #, jeśli ostatnia linia kończy się dokładnie na 76 znakach, nie następuje podział linii.

Mogę to udowodnić, uruchamiając następujący kod:

byte[] bytes = new byte[16 * 1024];
Console.WriteLine(Convert.ToBase64String(bytes, Base64FormattingOptions.InsertLineBreaks).Length);

Odpowiedź dla 16 KB zakodowanych do base64 z 76-znakowymi liniami: 22422 znaków

Załóżmy, że w Linuksie tak będzie, Length = Floor(Ceiling(N/3) * 4 * 77 / 76)ale nie udało mi się jeszcze przetestować tego na moim .NET core.

— Lionet Chen
źródło