Base64

·

Base64

Base64 is an algorithm to encode binary data by only 64 characters(plus `=` as a placeholder). Let's first see how the algorithm works and them implement it from scratch.

Say we want to encode string `ab` into base64 string.

First, let encode this string into UTF8 encoding binary data first.

``````ab
=> [97, 98]
``````

Then we express it in binary format.

``````[97, 98]
=> [01100001, 01100010]
``````

Then we split bits, each 6 bits into one group. Note that here, if the last group donesn't has enough 6 bits, just append 0's at the end.

``````[01100001, 01100010]
=> [011000, 010110, 001000]
``````

Then we make every element as a valid uint8 value by padding 2 zeros from element's top.

``````[011000, 010110, 001000]
=> [00011000, 00010110, 00001000]
``````

Let's see it now in 10 base format.

``````[00011000, 00010110, 00001000]
=> [24, 22, 8]
``````

Next, we map each value with a table to get the corresponding characters. The table is as below.

``````// used for encode
const table = [
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',

'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',

'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',

'+', '/'
];

// used for decode
const reverseTable = table.reduce((pre: Record<string, number>, cur: string, i: number) => {
pre[cur] = i;
return pre;
}, {});
``````
``````// value as table's index
[24, 22, 8]
=> [Y, W, I]
``````

At last, we append `=` at the end according to the value of `original binary array's length % 3`. If the value is 2, then append `=`. If the value is 1, then append `==`.

That's all of it. Simple.

Code

Let's implement the process in code.

``````function encode(text: string): string {
const before = new TextEncoder().encode(text);
const after = new Uint8Array(Math.ceil(before.length * 8 / 6));

let i = 0; // index of before
let j = 7; // index of current bit(all bit)

let x = 0; // index of after
let y = 5; // index of current bit(right 6 bit)

// bit index
// 76543210
// 00000000

while (true) {
// current j, need to be y
const diff = j - y;
let v = (before[i] & (1 << j));
if (diff >= 0) {
v >>= diff;
} else {
v <<= -1 * diff;
}
after[x] |= v;

if (j > 0) {
j -= 1;
} else {
if (i < before.length - 1) {
i += 1;
j = 7;
} else {
break;
}
}

if (y > 0) {
y -= 1;
} else {
x += 1;
y = 5;
}
}

let result = [...after].map(i => table[i]);

const remainder = before.length % 3;
if (remainder === 2) {
result.push("==");
} else if (remainder === 1) {
result.push("=");
}

return result.join("");
}

function decode(text: string): string {
let result = [...text.replace(/=+\$/, "")];
let after = new Uint8Array(result.map(char => reverseTable[char]));
let before = new Uint8Array(Math.floor(after.length * 6 / 8));

let i = 0; // index of before
let j = 7; // index of current bit(all bit)

let x = 0; // index of after
let y = 5; // index of current bit(right 6 bit)

// bit index
// 76543210
// 00000000

while (true) {
// current y, need to be j
let v = (after[x] & (1 << y));
const diff = y - j;
if (diff >= 0) {
v >>= diff;
} else {
v <<= -1 * diff;
}
before[i] |= v;

if (j > 0) {
j -= 1;
} else {
i += 1;
j = 7;
}

if (y > 0) {
y -= 1;
} else {
if (x < after.length - 1) {
x += 1;
y = 5;
} else {
break;
}
}
}

return new TextDecoder().decode(before);
}
``````

Lastly, make some tests.

``````const text1 = "ab";
const encoded1 = encode(text1);
const decoded1 = decode(encoded1);
console.log({ text1, encoded1, decoded1 }, text1 === decoded1);

const text2 = "こ";
const encoded2 = encode(text2);
const decoded2 = decode(encoded2);
console.log({ text2, encoded2, decoded2 }, text2 === decoded2);

const text3 = "速对表";
const encoded3 = encode(text3);
const decoded3 = decode(encoded3);
console.log({ text3, encoded3, decoded3 }, text3 === decoded3);
``````

And the result.

``````{ text1: "ab", encoded1: "YWI==", decoded1: "ab" } true
{ text2: "こ", encoded2: "44GT", decoded2: "こ" } true
{ text3: "速对表", encoded3: "6YCf5a+56KGo", decoded3: "速对表" } true
``````