The Complete Encoder and Decoder

At the end of this lesson one program encodes and decodes both base64 variants and refuses malformed input.

How it works

Nothing inside a group is new; four lines carry it over.

• Group (lesson 3): n = (b0 << 16) | (b1 << 8) | b2, indices (n >> 18) & 63, (n >> 12) & 63, (n >> 6) & 63, n & 63.
• Tail (lesson 4): pack 1 or 2 leftover bytes the same way, missing bytes all zeros, keep the first 2 or 3 indices.
• Decode (lesson 5): n = (v0 << 18) | (v1 << 12) | (v2 << 6) | v3, bytes (n >> 16) & 255, (n >> 8) & 255, n & 255, keeping 3 - pads.
• Refuse (lesson 6): length, char, padding, bits in that order; the bits check wants v & 3 (one pad) or v & 15 (two) to be 0, v the last non-= index.

New is that it all exists exactly once. The two alphabets differ only at index 62 and 63 (+ / against - _), so the alphabet is a parameter, not a second copy of the code. encode_b64(data, alphabet, write_padding) looks indices up in the string it is handed; write_padding false only stops the = fill. decode_b64(text, alphabet, padding_optional) uses its alphabet for the char check too, so DECODE refuses - and _ while DECODE_URL refuses + and /. padding_optional touches the length rule alone: false rejects every length that is not a multiple of 4, true rejects only len % 4 == 1 and takes the unwritten pad count from the length, 3 -> 1 and 2 -> 2. The padding and bits rules are untouched.

ROUNDTRIP sets the halves against each other: encode standard and padded, print that text, then decode it and print OK if the bytes coming back are those that went in. <hex> is two lowercase hex digits per byte, so fefdfc80 is 254, 253, 252, 128 - a group and a 1-byte tail:

bits    11111110 11111101 11111100 | 10000000
6-bit   111111 101111 110111 111100| 100000 00[0000]
index       63     47     55     60|     32        0
char         /      v      3      8|      g        A

00[0000] is one index: the 2 remaining bits of 80 plus 4 zero-fill bits, value 0. The tail takes two =, giving /v38gA==. Decode that back: all four checks pass (A is index 0, 0 & 15 is 0), two pads drop two bytes, fe fd fc 80 come out - the line is /v38gA== OK.

The algorithm

function encode_b64(bytes, alphabet, write_padding):
    4 characters per whole 3-byte group            # lesson 3
    2 or 3 characters for a 1- or 2-byte tail      # lesson 4
    if write_padding: append '=' up to a multiple of 4

function decode_b64(text, alphabet, padding_optional):
    the first failing word, in order:              # lesson 6
      length  - len % 4 == 1; also 2 or 3 unless padding_optional
      char    - outside THIS alphabet and not '='
      padding - '=' outside a trailing run of 1 or 2, or len % 4 != 0
      bits    - last non-'=' index v: v & 3 (1 pad) or v & 15 (2) not 0
    pads = trailing '=' count, else from len % 4 (3 -> 1, 2 -> 2)
    decode groups of 4, '=' as value 0             # lesson 5
    drop the last `pads` bytes

ROUNDTRIP bytes:
    text = encode_b64(bytes, standard, padding yes)
    print text, a space, then OK if decode_b64(text, standard, optional no)
        gives those bytes back, else FAIL

What the grader runs

One command per line, <hex> being 1 to 200 bytes of lowercase hex, one output line each. ENCODE: standard, = padded. ENCODE_URL: base64url, never =. DECODE, DECODE_URL: the bytes as lowercase hex, or INVALID and the first failing word. ROUNDTRIP: your encoding, a space, then OK or FAIL.

ENCODE 48656c6c6f -> SGVsbG8=
ENCODE_URL 48656c6c6f3e3f -> SGVsbG8-Pw
DECODE_URL -_8 -> fbff
ROUNDTRIP 00 -> AA== OK
DECODE SGVsbG8-Pw== -> INVALID char
DECODE SGVsbG8 -> INVALID length
DECODE_URL SGVsbG8 -> 48656c6c6f

Print exactly this, one result per line, newline-terminated, nothing else. No input lines means no output at all.

Notes

• Hidden tests cross alphabets, hit every INVALID word both ways, all three tails, 100 bytes and empty stdin.
• DECODE SGVsbG8 is INVALID length but DECODE_URL SGVsbG8 decodes: unwritten padding is legal only on the URL-safe path.
• Both alphabets and both padding rules: RFC 4648, https://www.rfc-editor.org/rfc/rfc4648

Your exercise

Write your starter's two TODO functions, encode_b64 and decode_b64. The starter parses lines, converts hex, dispatches and prints. The mistake the grader catches: one decoder strict, the other lenient.