3.8.3 Base64 Encoding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

/*

Encodes binary data as printable ASCII using Base64, and decodes Base64 text back to bytes. Base64
is an encoding, not encryption or compression: it preserves all input data exactly, but usually
increases size by about one third. Each group of three input bytes is split into four 6-bit values,
each selecting one character of a 64-symbol alphabet, with `=` padding marking a final group of
only one or two bytes.

This implementation uses the standard alphabet with `+`, `/`, and `=` padding. Whitespace is not
skipped by the decoder; clean the input first if line breaks or spaces may appear.

- `base64_encode(bytes)` returns the Base64 representation of string `bytes`.
- `base64_decode(text)` returns the decoded byte string. It assumes `text` is valid padded Base64.

Time Complexity:
- O(n) per call, where $n$ is the input length.

Space Complexity:
- O(n) for the output string.

*/

#include <string>
#include <vector>
using std::string;

const string BASE64_ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

string base64_encode(const string &bytes) {
  string res;
  int val = 0, bits = -6;
  for (int i = 0; i < static_cast<int>(bytes.size()); i++) {
    val = (val << 8) + static_cast<unsigned char>(bytes[i]);
    bits += 8;
    while (bits >= 0) {
      res.push_back(BASE64_ALPHABET[(val >> bits) & 63]);
      bits -= 6;
    }
  }
  if (bits > -6) {
    res.push_back(BASE64_ALPHABET[((val << 8) >> (bits + 8)) & 63]);
  }
  while (res.size() % 4) {
    res.push_back('=');
  }
  return res;
}

string base64_decode(const string &text) {
  std::vector<int> table(256, -1);
  for (int i = 0; i < 64; i++) {
    table[static_cast<unsigned char>(BASE64_ALPHABET[i])] = i;
  }
  string res;
  int val = 0, bits = -8;
  for (int i = 0; i < static_cast<int>(text.size()); i++) {
    if (text[i] == '=') {
      break;
    }
    int x = table[static_cast<unsigned char>(text[i])];
    if (x < 0) {
      break;
    }
    val = (val << 6) + x;
    bits += 6;
    if (bits >= 0) {
      res.push_back(static_cast<char>(((val >> bits) & 255)));
      bits -= 8;
    }
  }
  return res;
}

/*** Example Usage ***/

#include <cassert>

int main() {
  assert(base64_encode("hello") == "aGVsbG8=");
  assert(base64_decode("aGVsbG8=") == "hello");
  assert(base64_decode(base64_encode("abc123!?")) == "abc123!?");
  return 0;
}