This project was written in the first semester at BFH TI. It is intended to encode any input-string to Base32 and backwards.
- Difficulties when encoding to Base32
- Road to the perfect algorithm
- Explaining the final code
- Explanation on decoding
- Copyright, license and usage for BFH TI
The original difficulty is to transform an input of 8 bit blocks into blocks of 5 bits prefixed with 3 zeros. Because this requires us to keep a transactional byte as well as making the next byte transactional.
The problem is visualized in this short note with two bytes of numeric bits:
I started very simple: By visualizing my mind onto a paper. This is what my first solution looked like:
This is how I thought it may work:
// Read first byte
1234 5678
// Shift until the first 5 bits left
0001 2345
But to calculate the next 5 bits I realized that i needed the second byte too. I ended up like this:
// Read first byte and some zeros
1234 5678 | 0000 0000
// Shift right until the first 5 bits left
0000 0000 | 0001 2345
// Now reset it to the inital state
1234 5678 | 0000 0000
// And read the second byte
1234 5678 | 1234 5678
Now how do you read the next 5 bits?
I used a trick which I like to call the "shift-left-right":
// Shift left to remove previously processed bits
6781 2345 | 6780 0000
// Shift right until next 5 bits left
0000 0000 | 0006 7810
Based on this I noticed the need to know how meany bits were left from the previous byte. I thought of a modulo calculation but had no idea on which values it should be based on. After a quick brainstorming the following seemed to be obvious:
// Calculate transactional bits
a = input-bytes-read (2) * 8 = 16
// Calculate processed bits
b = turns-done (2) * 5 = 10
// Calculate how meany bits of the current input-byte are still processable
a (16) % b (10) = 6
If the result is exactly or greater than 5, there exists another Base32 encoded value in the current input-byte. Otherwise there are not enough transactional bits left and you must read another byte from the input.
This process is (simplified) repeated until all bytes were converted to 5 bit blocks.
The ending is really easy. Just add as much '='s to your output until the byte-count reaches a multiple of 8. Attention: You do not add any '='s if your output already is on a multiple of 8! (Took me quite a time to detect and fix this error..)
Based on all this I wrote another pseudo code onto a paper. This time a bit more readable (at least I tried):
Of course this is not THE solution. It just IS a solution.
// TODO
There is no explanation on decoding from Base32 as this is literally the exact same algorithm just in reverse.
This project is licensed under the terms of MIT License.
This means you have the permission to use the code for commercial as well as for private use. You may modify and contribute to the code, in addition you may distribute it. But: I do not guarantee warranty nor am I liable in any case.
It is meant to help other students understanding the complex topic of encoding and decoding to or from Base32, to get them a first idea. It is not intended to be copied! Keep in mind that I (bbortt) am the original owner of this code in any case of plagiarism conflict.