A Strict Decoder Refuses Bad Input

By the end of this lesson your decoder answers every line with either the bytes it decoded or one word saying why it refused: lesson 5's decoder with a gate in front.

How it works

A lenient decoder skips characters it does not recognise and accepts sloppy trailing bits, so two strings decode to the same bytes — what RFC 4648 calls non-canonical. A strict decoder accepts one spelling per value.

Four rules, checked in a fixed order, so a string breaking several still has one answer: the first broken. A data character is any character that is not =; a trailing run of = is one or more = at the very end, nothing after them.

Rule 1 follows from lesson 1: 3 bytes emit exactly 4 characters, so a legal encoding is never 5, 6 or 7 long. Rule 2 rejects rather than skips: a space, a tab, @, - and _ are refusals.

Lesson 4's encoder filled the unused low bits of the last data character with zeros, so they must still be zero coming back. The indexes below are binary, six digits wide; low bits are the rightmost, and clear means zero.

SGU=  'U' index 20 = 010100  low 2 bits 00   -> ok (48 65)
SGV=  'V' index 21 = 010101  low 2 bits 01   -> INVALID bits
SA==  'A' index 0  = 000000  low 4 bits 0000 -> ok (48)
SB==  'B' index 1  = 000001  low 4 bits 0001 -> INVALID bits

Index, value, and what the starter's lookup returns are three names for one 0-63 number. SGU= and SGV= give the same bytes; only the first is their encoding, and two = leave a four-bit tail, not a two-bit one.

To test those bits, use the bitwise AND operator &. Write v for the value of the character being checked — that same 0-63 number. v & 3 keeps only the low 2 bits of v, so (v & 3) == 0 is true exactly when both are zero; v & 15 covers the low 4.

End to end, SGU=: length 4 ok, characters ok, one trailing = ok, v is 20 and 20 & 3 = 0 ok — validate says ok and it prints 4865.

The algorithm

Pseudocode: s[i] is the character at index i, however your language spells it.

for each line on stdin:
    reason = validate(line)
    if reason == "ok":
        print decode(line) as lowercase hex   # lesson 5's decoder
    else:
        print "INVALID " + reason

validate(s):
    check 1  length   the character count of s is a multiple of 4
    check 2  char     every character of s is in the alphabet, or is '='
    check 3  padding  pads, the count of '=' at the end of s, is 0, 1 or 2,
                      and no '=' appears anywhere else
    check 4  bits     if pads is 0 this check passes; otherwise take v, the
                      value of the character pads + 1 places from the end:
                      low 2 bits clear when pads is 1, low 4 when pads is 2
    return the word of the FIRST check that fails, else "ok"

What the grader runs

Each line of stdin is one candidate string of up to 200 characters, spaces and tabs included. Print one line per input line: the decoded bytes as lowercase hex, or INVALID and one reason word.

SGVsbG8=  ->  48656c6c6f
SGVsbG8   ->  INVALID length
SGVs@G8=  ->  INVALID char
SG=lbG8=  ->  INVALID padding
SGV=      ->  INVALID bits

Print exactly this, one space between INVALID and the word, one result per line, newline-terminated, nothing else.

Notes

• The order is load-bearing: SGVs@G8 is 7 characters and holds a bad one, so the answer is length; SGVs@G8= is 8, so it is char.
• A blank line is valid (0 is a multiple of 4, nothing to reject: echo a blank line), and no = at all is fine too — SGVsbG8h uses every bit it has and decodes.
• Check 4 never runs off the front: checks 1 and 3 passed first, so the line has at least 4 characters and at most 2 =; it always reads a data character.
• Primary source: RFC 4648, https://www.rfc-editor.org/rfc/rfc4648

Your exercise

Write the validate function: it returns ok, or the first of length, char, padding, bits to fail. The starter has lesson 2's lookup, lesson 5's decoder, the input loop and the printing. The likeliest mistake is skipping the bits check, which lets SGV= and SB== decode.