When the Last Group Is Short

By the end of this lesson your encoder handles any number of bytes: keep lesson 3's group encoder and add one rule for the 1 or 2 bytes left over.

How it works

Take as many whole 3-byte groups as you can; the leftover is 0, 1 or 2 bytes, never 3. One block is the four characters that one group -- or one padded tail -- produces.

Lesson 3's <<, >>, & 63 and | do the work again here, and a field is still one 6-bit chunk of a 24-bit block; lesson 2's alphabet turns a field's value into a character, so 0 is 'A', 6 'G', 18 'S', 36 'k', 48 'w', 63 '/'.

A short group is completed with zero BITS, never invented bytes; << puts them there. Trace the single byte 0x48 = 01001000, shifted to the top of 24 by n = b0 << 16:

bits    010010 000000 000000 000000
input   111111 11....                8 input bits; '.' is a zero the shift added
values  18     0      -      -
chars   S      A      =      =

(n >> 18) & 63 is 18 -> 'S' and (n >> 12) & 63 is 0 -> 'A'. Field 1 is worth zero and is still a real character, because 0x48's last two bits land in it; '=' is only for a field that no input bit reaches. The block is SA==.

Now the two bytes 0x48 0x69 = 01001000 01101001. The first byte is the most significant, so n = (b0 << 16) | (b1 << 8) = 0x486900:

bits    010010 000110 100100 000000
input   111111 111111 1111..         16 input bits; the last two are added zeros
values  18     6      36     -
chars   S      G      k      =

Count fields rather than memorise the two cases: a field becomes a character as soon as one input bit reaches it, so the character count is the bit count divided by 6, rounded up. 8 bits fill field 0 and spill 2 into field 1 -- two characters, field 1 topped up with four zero bits. 16 bits fill fields 0 and 1 and spill 4 into field 2 -- three characters, field 2 topped up with two. 24 bits fill all four exactly. Fields no input bit reaches print as '=': fields 2 and 3 after a 1-byte tail, field 3 after a 2-byte one -- lesson 1's pad count, now produced by code. Check yourself: 6162 -> YWI=.

'=' carries no bits: SA== is 4 characters but 1 byte of data. No block ends in three '=' -- that would be a group with no data.

The algorithm

encode(data):
    for each whole 3-byte group: out = out + encode_group(it)   # lesson 3
    if 1 or 2 bytes remain:      out = out + encode_tail(them)

encode_tail(tail):                 # 1 or 2 bytes
    pack them into one number, first byte most significant, shifted left to
        the top of 24 bits: 16 places for the first byte, 8 for a second
    read the fields holding an input bit, each with (n >> k) & 63:
        8 bits need two, 16 bits need three
    look each up in the alphabet, then append '=' until the block is 4 long

What the grader runs

Input is zero or more lines, each a non-empty lowercase hex string with an even digit count, 1 to 200 bytes. Print one line per input line: those bytes in standard base64, '=' padded to a multiple of 4 characters.

input:        output:
48            SA==
4869          SGk=
48656c6c6f21  SGVsbG8h
00            AA==
ff            /w==

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

Notes

• 00 is data: it encodes to AA==, not to nothing. Never pad a byte count that is a multiple of 3 (48656c -> SGVs), and empty stdin prints nothing.
• A whole group can precede a tail: 4 bytes are one group plus a 1-byte tail 48656c6c -> SGVsbA==. Hidden lines reach 100 bytes.
• The commonest mistake is dropping the leftover bits, so ff comes out /A== not /w==: its spare 11 must fill out to 110000 = 48 = 'w'. Next is swapping the 1- and 2-byte cases.
• Source: RFC 4648, https://www.rfc-editor.org/rfc/rfc4648

Your exercise

Implement encode_tail: 1 or 2 leftover bytes in, four characters out -- the 2 or 3 their bits produce plus '=' padding. The starter parses the hex lines, walks the whole groups and calls your function when bytes remain; the likeliest mistake is padding a byte count already a multiple of 3.