QR Decoding
Time limit1sMemory limit128 MB
Parse a 19-byte QR data payload bit by bit and decode its numeric, alphanumeric, byte, and kanji mode segments into a formatted output string.
- Level
Medium6 of 10
- Topics
- Bit manipulation, String, Implementation, Simulation
- Solved
- No attempts yet
Problem
A QR code is a square black-and-white matrix made of unit pixels. Its pixels are divided into finder patterns, timing patterns, format information, data and error-correction codewords, and, for larger QR codes, alignment patterns and version information.
This problem only uses the data part of a 21\u00D721 QR code. A QR code of this size has 26 data/error-correction codewords, and the first 19 of them are data codewords. Each data codeword is 8 bits. The input gives these 19 data codewords as a 38-character hexadecimal string. Recover the original information from the given data codewords.
Read bits from the first bit of the 19 bytes to the last. Each segment starts with 4 mode bits, followed by count bits and payload bits whose format depends on the mode.
Mode 0000 terminates the data. If there is not enough room, the termination mode may be omitted or only partially present. Bits after termination, including padding bytes 11101100 and 00010001, are ignored.
Numeric mode stores a string of decimal digits. After mode bits 0001, the next 10 bits give the number of digits. The digits are split from the left into groups of three; each group is stored as a 10-bit integer. If two digits remain, they are stored in 7 bits. If one digit remains, it is stored in 4 bits. For instance, 12345678 is split as 123, 456, 78 and encoded as 0001111011, 0111001000, 1001110.
Alphanumeric mode stores strings over the following 45 characters, in this exact order.
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:
After mode bits 0010, the next 9 bits give the number of characters. Characters are processed in pairs. A pair is encoded as first character code \u00D7 45 + second character code, stored in 11 bits. If one character remains, its code is stored in 6 bits. For instance, AC-42 has character codes 10, 12, 41, 4, 2, so the two pairs have values 462 and 1849.
8 bit byte mode uses mode bits 0100, then an 8-bit byte count, then one 8-bit value per character. Kanji mode uses mode bits 1000, then an 8-bit character count, then one 13-bit value per character.
Concatenate the decoded characters from all segments in order.
Input
The first line contains the number of test cases P. (1 \u2264 P \u2264 1000)
Each test case is given on one line. The line represents 19 data codewords and contains exactly 38 hexadecimal characters. Only the characters 0-9 and A-F appear.
Output
For each test case, print one line.
First print one integer: the number of decoded characters before output escaping is applied. Then print one space and the decoded string.
For a value decoded in 8 bit byte mode, if it is a printable ASCII character from 0x20 through 0x7e, print that character as is. However, print a backslash () as \, and print # as #.
For any 8-bit value that is not a printable ASCII character, print it as \xx, where xx is its two-digit uppercase hexadecimal value. For example, 0xAE is printed as \AE.
For every 13-bit value decoded in Kanji mode, print #bxxx, where bxxx is the four-digit uppercase hexadecimal value and b is 0 or 1. For example, 0x13AC is printed as #13AC.