Three Bytes Become Four Characters

This lesson encodes whole groups: every 3 bytes in, exactly 4 alphabet characters out. Lesson 4 handles a short last group.

How it works

A bit is a single 0 or 1. A byte is 8 bits, so it holds 0 to 255, and three bytes end to end are 24 bits. 24 divides evenly by 6, so the bits regroup into four fields of 6 bits -- a field is just one of those 6-bit slices, numbered 0 to 3 from the left. A field is a number from 0 to 63: exactly one index into the alphabet from lesson 2. That is why base64 counts in threes.

Bytes here are written in hexadecimal, base 16: two digits per byte, digits 0-9 then a-f for 10-15, with a 0x prefix. 0x48 is 4*16 + 8 = 72 and 0x3f is 63. The grader's input lines use the same digits, no prefix.

Take the bytes 0x48 0x65 0x6c (the text Hel):

bytes    0x48       0x65       0x6c
bits     01001000   01100101   01101100
regroup  010010 000110 010101 101100
values       18      6     21     44
chars         S      G      V      s

Nothing is reordered: cut the 24 bits after every sixth, and Hel encodes to SGVs.

You pack the three bytes into one 24-bit number, then cut the fields out with shifts and masks. Bits are written left to right, biggest place value first, as in the table: those on the right are a number's low bits, those on the left its high or most significant bits. Four new operators:

• x << n shifts x left n bit positions: multiplying by 2 to the power n. 3 << 2 is 12 (3 * 4), and 0x48 << 16 moves b0's eight bits to the top of the 24, giving 4718592.
• x >> n shifts x right n bit positions, dropping the low n bits: integer division by 2 to the power n. 44 >> 2 is 11, and 4744556 >> 18 is 18 -- the first field of Hel, below.
• x & 63 keeps only the low 6 bits and drops the rest. That is masking, and 63 is the mask; it is the same as x % 64. 4744556 & 63 is 44 -- the last field of Hel.
• a | b merges two numbers sitting in different bit positions. 0x4800 | 0x65 is 0x4865.

Packing is n = (b0 << 16) | (b1 << 8) | b2, that is b0 * 65536 + b1 * 256 + b2; for Hel, 4744556. Now cut, most significant field first -- the leftmost 6 of the 24 bits, the ones from the top of b0:

field 0 = (n >> 18) & 63   ->  18  -> 'S'

Each next field starts six bits further right, and the last one needs no shift at all -- but it still needs its & 63, because n is 24 bits wide; the table gives the four values.

The & 63 is not decoration: n >> 12 is 1158 for Hel, no alphabet index at all; only & 63 trims it to 6. Without it the middle two fields run past the end of the alphabet.

The algorithm

for each input line:
    bytes = the line's hex digits, two digits per byte
    out = empty string
    for i = 0, 3, 6, ... while i < length(bytes):
        out = out + encode_group(bytes[i], bytes[i+1], bytes[i+2])
    print out

encode_group(b0, b1, b2):
    pack the three bytes into one 24-bit number
    cut four 6-bit fields out of it, most significant first
    return the four alphabet characters at those indices

What the grader runs

Each input line is a non-empty run of lowercase hex digits whose length is a multiple of 6, so the byte count is a multiple of 3: whole groups only, so no = padding character (lesson 4 adds those when the last group is short) ever appears in your output. Print one line per input line, 4 characters per 3 bytes.

input:
48656c
48656c6c6f21
ffffff
000000

output:
SGVs
SGVsbG8h
////
AAAA

input:
4d616e
00ff00

output:
TWFu
AP8A

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

Notes

• 000000 is three real bytes, not "nothing": it prints AAAA, and ffffff prints //// -- the quickest check that your masks are right.
• A missing & 63 on the middle two fields is invisible while every byte is below 0x40 (64), and broken the moment one is not.
• Groups are independent, lines run up to 300 bytes, and no input lines at all must produce no output at all: start a fresh output string for each line.
• Alphabet order and the 4-for-3 grouping are RFC 4648: https://www.rfc-editor.org/rfc/rfc4648

Your exercise

Implement encode_group: three byte values in, four characters out, using the alphabet the starter declares. The starter parses each hex line into bytes, walks them three at a time, joins your results and prints the line. The likeliest mistake: dropping & 63 on the middle fields.