Base64URL, With and Without Padding

Base64url is ordinary base64 with two characters swapped and the = thrown away. By the end of this lesson your program encodes and decodes it, rejecting malformed text the same four ways.

How it works

Two facts from earlier lessons carry this one. A character's index is its position in the 64-character alphabet, 0 to 63 (A is 0, / is 63). And one base64 character stands for 6 of a byte's 8 bits, so 4 characters spell exactly 3 bytes — one group.

A URL cannot carry two characters of lesson 2's alphabet: + reads as a space in a query string, / separates the parts of a path. RFC 4648 section 5 swaps those two and nothing else: index 62 becomes -, index 63 becomes _.

The second change: base64url drops the trailing =, since = has its own meaning in a URL. Nothing is lost — the length says how many were dropped.

len % 4 | dropped '=' | bytes in last group
   0    |      0      |  3
   2    |      2      |  1
   3    |      1      |  2

No row for len % 4 == 1: one leftover character is 6 bits, too few for an 8-bit byte.

Encode 48 65 6c 6c 6f 3e 3f: lesson 4's encoder gives SGVsbG8+Pw==; swapping index 62 and dropping the = gives SGVsbG8-Pw. Back again: 10 % 4 == 2, two = went missing, so lesson 5's group decoder runs on SGVsbG8-Pw== and returns the seven bytes. Shorter: SGk, 3 % 4 == 3, so the decoder gets SGk= and returns 48 69.

Validation is lesson 6's four rules in the same order — length, char, padding, bits — reporting the first to fire: AA=== is length, not padding. Three change:

• length: only len % 4 == 1 is bad; a missing = is normal here.
• char: - and _ are legal now, + and / are not, = still allowed.
• padding: 1 or 2 =, all at the very end of the text, and only when the total length is a multiple of 4 — so SA= is padding.
• bits: unchanged, and a dropped = counts like a written one. With one = the last data character carries 4 real bits and 2 leftover ones, so the leftover is zero exactly when its index divides by 4; with two = it carries 2 real and 4 leftover, so the test is 16. SA: A is index 0, 0 % 16 == 0, canonical. SB: index 1, 1 % 16 == 1, so bits. -_-: - is index 62, 62 % 4 == 2, so bits.

The algorithm

reject W below means stop and return the word INVALID, a space, then W.

encode_url(bytes):
    run the supplied standard encoder
    replace '+' with '-' and '/' with '_', then drop every trailing '='

decode_url(text):
    n = length of text
    if n mod 4 == 1: reject "length"
    if a character is outside the url alphabet and not '=': reject "char"
    if text contains '=':
        k = how many '=' sit at the end of text
        reject "padding" unless k is 1 or 2, n mod 4 == 0, no '=' earlier
        data = text without those k; pads = k
    else:
        data = text
        pads = 0 if n mod 4 == 0, else 2 if n mod 4 == 2, else 1
    if pads > 0:
        v = url index of the last character of data
        reject "bits" if (pads == 1 and v mod 4 > 0) or (pads == 2 and v mod 16 > 0)
    run the supplied group decoder on data plus pads '='
    return those bytes as lowercase hex, two characters per byte

What the grader runs

Each line is one command: ENCODE_URL <hex> (lowercase hex, 1 to 200 bytes) or DECODE_URL <text> (up to 200 non-space characters). Print one line per command: the encoding with no =, the bytes as lowercase hex (two characters per byte, so byte 72 prints as 48), or INVALID, a space, and one reason word.

ENCODE_URL 48656c6c6f3e3f -> SGVsbG8-Pw
DECODE_URL SGVsbG8+Pw== -> INVALID char
DECODE_URL SGVsbG8gV -> INVALID length

Print exactly this, one result per line, newline-terminated, nothing else.

Notes

• Hidden tests check both substitutions (ffffff gives ____, fbefbe gives ----), that 00 gives AA, that padded and bare spellings agree, and //// is rejected.
• The commonest mistake calls a missing = a length error; only len % 4 == 1 is one.
• Primary source: RFC 4648, https://www.rfc-editor.org/rfc/rfc4648

Your exercise

Write the starter's two TODO functions: encode_url runs the supplied encoder, swaps the two characters and strips the =; decode_url applies the four rules in order, recovers the dropped = from the length and calls the supplied group decoder, returning lowercase hex. The grader most often catches + or / accepted by DECODE_URL.