ZBase32, Base32 and Base64 encoding algorithms

Hello!

Many people use Base64 encoding, less often Base32 and even less often ZBase32 (do you know about this?), But not everyone understands their algorithms. In the article I describe the advantages, disadvantages of these encodings, and also talk about their implementation.

Not so long ago, I had a need to use encoded data in the address of the http link. As is known, the standard http means are case not dependent url No-address and any proxy or browser can corrupt the data in the case of the use of case-sensitive coding.

Given these requirements, ZBase32 encoding was chosen as the algorithm.
As it turned out, there is no standard implementation in .net (unlike base64), so I had to write it myself. To my surprise, I ran into difficulties finding a clear explanation of Base32 and ZBase32. Some ready-made solutions were found, but I could not, without understanding the algorithm, apply them, and reading the magic of large formulas, bit shifts was difficult without a verbal description. Now that everything is behind me, I would like to share with you a little knowledge of elementary coding. The article is academic in nature.

Pros and cons

Base64

Allows you to encode information represented by a set of bytes using a total of 64 characters: AZ, az, 0-9, /, +. At the end of a coded sequence, several special characters (usually “=”) may be contained.

Benefits:

• Allows you to represent the sequence of any bytes in printed characters.
• Compared with other Base encodings, it gives a result that is only 133. (3)% of the length of the source data.

Disadvantages:

• Case-sensitive encoding.

Base32

Uses only 32 characters: AZ (or az), 2-7. It may contain several special characters at the end of the encoded sequence (similar to base64).

Benefits:

• The sequence of any bytes translates to printable characters.
• Case-insensitive encoding.
• Do not use numbers that are too similar to the letters (for example, 0 is like O, 1 is like l).

Disadvantages:

• Coded data is 160% of the original.

Zbase32

The encoding is similar to Base32, but has the following differences.

• 32-character human-oriented alphabet. The most elaborate symbol table to facilitate writing, pronunciation and memorization of encoded information. The authors rearranged the most convenient symbols for humans to the positions that are used most often. I don’t know how they did it. The alphabet is given below.
• There are no special characters at the end of the encoding result.

You can read more about each of the encodings on Wikipedia here and here , and now I would like to dwell directly on the implementation of ZBase32.

Description of ZBase32 Encoding Algorithm

I allow myself to show calculations in C # when describing the algorithm for a better understanding.

So, we have a 32-character alphabet of the following content:

static string EncodingTable = "ybndrfg8ejkmcpqxot1uwisza345h769";

The input is an array of bytes (of course, 8 bits each), which I would like to translate into characters from the alphabet.

public static string Encode(byte[] data)
{

The alphabet is a string of 32 elements, which means that each of its characters is encoded by a number from 0 to 31 (character indices in a string). As you know, any number from 0 to 31 in the binary number system can be written using 5 bits of a byte. It follows that if we represent the original set of bytes as a single array of bits and break it into pieces of 5 bits (see the figure below), then we get a set of coordinates of characters from the alphabet. That, in fact, is all.

Base32 and Base64 algorithms are similar to ZBase32, only different alphabets (in composition in the case of Base32, in composition and size in the case of Base64) and the size of the “nibbled” pieces of bits (6 bits for Base64).



So, I suggest, before you start dividing the source data into pieces of 5 bits, prepare a place where the result will be written. In order not to think about indexes in static arrays, let's use StringBuilder.

var encodedResult = new StringBuilder((int)Math.Ceiling(data.Length * 8.0 / 5.0));

When initializing, we immediately set the size of the resulting string (so as not to waste time expanding during the operation of the algorithm).

Now it remains to run through the original array of bytes and divide it into 5-bit pieces. For convenience, I suggest working with a group of 5 bytes, since this is 40 bits - a number that is a multiple of the length of the “pieces”. But do not forget that no one customized the initial data for us, so we take into account the possibility of shortages.

for (var i = 0; i < data.Length; i += 5)
{
     var byteCount = Math.Min(5, data.Length - i);

Since we are working with a group of 5 bytes, we need a buffer where a continuous set of bits will be generated (40 bits in total). We get a variable of type ulong (64 bits at our disposal) and put the current batch of bytes there.

ulong buffer = 0;
for (var j = 0; j < byteCount; ++j)
{
      buffer = (buffer << 8) | data[i + j];
}

And the final stage is “nipping off” from what happened, pieces of 5 bits and the formation of the result.

var bitCount = byteCount * 8;
while (bitCount > 0)
{                    
      var index = bitCount >= 5
                          ? (int)(buffer >> (bitCount - 5)) & 0x1f
                           : (int)(buffer & (ulong)(0x1f >> (5 - bitCount))) << (5 - bitCount);
      encodedResult.Append(EncodingTable[index]);
      bitCount -= 5;
}

Perhaps, in the last code example, at first glance, not everything is clear, but if you concentrate a little, then everything will fall into place.

The decoding process is similar to the encoding process, only in the opposite direction.

You can see the full implementation of ZBase32Encoder .

Conclusion

And, of course, in conclusion, I want to say the following.

4nq7bcgosuemmwcq4gy7ddbcrdeadwcn4napdysttuea6egosmembwfhrdemdwcm4n77bcby4n97bxsozzea9wcn4n67bcby4nhnbwf94n9pbq6oszemxwf74nanhegow8em9wfo4gy7bqgos8emhegos9emyegosmem5wfa4n6pbcgozzemtwfirr