expansion - Base64: What is the worst possible increase in space usage?

ID : 20150

viewed : 25

Tags : base64expansionbase64

Top 5 Answer for expansion - Base64: What is the worst possible increase in space usage?

vote vote

97

Base64 encodes each set of three bytes into four bytes. In addition the output is padded to always be a multiple of four.

This means that the size of the base-64 representation of a string of size n is:

ceil(n / 3) * 4 

So, for a 16kB array, the base-64 representation will be ceil(16*1024/3)*4 = 21848 bytes long ~= 21.8kB.

A rough approximation would be that the size of the data is increased to 4/3 of the original.

vote vote

90

From Wikipedia

Note that given an input of n bytes, the output will be (n + 2 - ((n + 2) % 3)) / 3 * 4 bytes long, so that the number of output bytes per input byte converges to 4 / 3 or 1.33333 for large n.

So 16kb * 4 / 3 gives very little over 21.3' kb, or 21848 bytes, to be exact.

Hope this helps

vote vote

72

16kb is 131,072 bits. Base64 packs 24-bit buffers into four 6-bit characters apiece, so you would have 5,462 * 4 = 21,848 bytes.

vote vote

65

Since the question was about the worst possible increase, I must add that there are usually line breaks at around each 80 characters. This means that if you are saving base64 encoded data into a text file on Windows it will add 2 bytes, on Linux 1 byte for each line.

The increase from the actual encoding has been described above.

vote vote

55

This is a future reference for myself. Since the question is on worst case, we should take line breaks into account. While RFC 1421 defines maximum line length to be 64 char, RFC 2045 (MIME) states there'd be 76 char in one line at most.

The latter is what C# library has implemented. So in Windows environment where a line break is 2 chars (\r\n), we get this: Length = Floor(Ceiling(N/3) * 4 * 78 / 76)

Note: Flooring is because during my test with C#, if the last line ends at exactly 76 chars, no line-break follows.

I can prove it by running the following code:

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

The answer for 16 kBytes encoded to base64 with 76-char lines: 22422 chars

Assume in Linux it'd be Length = Floor(Ceiling(N/3) * 4 * 77 / 76) but I didn't get around to test it on my .NET core yet.

Top 3 video Explaining expansion - Base64: What is the worst possible increase in space usage?

Related QUESTION?