Real-time QR-code implementation for Z80

____ __                                                      __
\  // / -- ------------------------------------------- - -__/  \
 \ \    La QueRcia cured code by Mr.Spiv/Scoopex         /  \__/
--\ -------------------------------------------------- - \__/  \
                                                            \__/

In this writeup we take a brief look at a QR-code implementation used in this very Subliminal Extacy release. It is a realtime Z80 assembler implementation of a version '3' QR-code with 'L'ow error correction level. We refer to this as 3-L QRcode from now on. The implementation is available in Github. A generic python3 version with a lot of bells'n'whistles is here:
https://github.com/jounikor/qr_code/
A "full" Z80 3-L version is here:
https://github.com/jounikor/qr_code/tree/master/asm/
The size optimised byte mode version used in this Subliminal Extacy release is here:
https://github.com/jounikor/qr_code/tree/bytemode/asm/
The size optimised alphanumeric version is here:
https://github.com/jounikor/qr_code/tree/sizeopt/asm

Subliminal Extacy uses the byte mode version due to a better support for some unfortunate mobile phones that fail to understand (partially) upper case host/domain part of a URL is a valid URL. Maybe someone has not read RFC 3986 to a detail or then more likely, I guess, there are practises beyond standards and some client implementations are just better than others?

Anyway, I was also requested to provide a size optimised version of the encoder (you know, Lordcoxis is good at asking for codes never to be used).. so I did, but with the cost of semi-unreadable code and ossifying masks to most simple ones without calculating penalty scores.

Fixing the constraints:
The QR-code generation is extremely flexible. For our restricted target platforms it makes sense to cut corners a bit and fix some variables to friendly values. As already mentioned the implementation is a 3-L QR-code. Furthermore, we are going to only support alphanumeric or byte mode payloads. This allows the following:

• Fixing the QR-code size to 29x29 pixels (excluding the quiet zone)
• Precompute a QR-code template that includes
  • The locations and the number of alignment patterns
  • Positional patterns
  • Sync patterns
  • Dark module
• Limit the number of format strings (a single error correction level and 8 possible masks) to 8 and precompute the error correction bits for those (the table will need 16 octets)
• No need to compute the version information (needed only if version is >= 7)
• Use fixed values for padding pixels/modules
• Precompute the generator polynomial for the error correction code calculation
• Limit the QR-code to 55 octet data codewords in one group block and 15 error correction codewords per block.
• With 3-L there is just group 1 block. Since there is only one block interleaving of data and error correction codewords can be skipped, which is a major relaxation.
• Know the maximum length of the input character string i.e. 76 or 55 characters depending on the mode.

Both size optimised versions drop dynamic calculation of penalty scores to figure out the most suitable masking function. The mask function is just hardcoded to either mask pattern 0 or mask pattern 1. This provides a sizeable code saving but with a cost of possibly using suboptimal mask pattern. As a side note, changing from alphanumeric coding to byte mode coding also allows for further code size cuts due to simplicity of byte mode encoding over alphanumeric encoding (no multiplication with 45 and no ugly bit fiddling).

A note about the precomputed QR-code template. It is stored as two bitmaps. One bitmap defines the dynamic parts of the QRcode, and the other bitmap has static light and dark modules that reside outside the dynamic parts of the QR-code. The size of one bitmap is 4*29 (=116) bytes. Storing templates as bitmaps obviously imply a lot of bit level manipulations when encoding the QR-code. The QR-code implementation itself, excluding the example rendering code for ZX Spectrum, is target host independent. About 20% of the final code size is contributed by precomputed QR-code template alone.

Most of the things in the 'vanilla' Z80 implementation are not hardcoded except for the version and for size optimised versions the error correction level. There are certain shortcuts available such as bypassing the penalty score computations and thus the selection of the most appropriate masking algorithm. The programmer can preselect one of the 8 mask algorithms. A brief warning. The code is not optimised for speed. Some generic attempts have done to reduce the RAM usage but even that is not "stretched" in any way.

The standard for the QR-code, ISO/IEC 18004, is unfortunately behind a paywall. However, the Interweb has some "backups" available here and there. There are a couple of very informative QR-code tutorials available that also have a twist toward programmers:
https://medium.com/p/5a33e1e882b5/
https://www.thonky.com/qr-code-tutorial/
One of the most fascinating areas in QR-code is the calculation of error correction codes (Salomon Reed). Honestly, I got fascinated about that part particularly and loved implementing the Galois Field precalculator and the polynomial division routines.

Again, the polydiv() division routine has been hardcoded to earlier 3-L QR-code limits (55 data codewords, 15 error correction codewords) and cannot handle the case where the polynomial is shorter than the generator.

All the preparation and encoding of the QR-code is done in 4x29 sized byte buffer. When encoding the QR-code there is no precalculated "zig-zag" movement pattern but a simple state machine that is capable of traversing through the bit encoded QR-code template - it just avoids "permanent" pixels using one of the predefined templates defining dynamic areas of the QR-code. The state machine knows to which direction to go next. In places where a new position would again be a "permanent pixel" the state machine needs to be called again until a writeable pixel location is found ;)
The final words on masking kernels (selected either based on calculated penalties or forced). They make use of modulo 3.

Also, the math involves multiplying rows by columns etc in several places. The latter is not really 8-bit friendly since the QR-code template has maximum 29 rows and 29 columns, thus 2828 product would exceed 8 bits. Anyway, since multiplications and modulus operations are interchangeable we can make use of the following:
(ab)%c == ((a%c)(b%c))%c == ((a%c)b)%c and in our case that will always fit into 8-bit register, thus we are happy. Basically there's an implementation for an efficient divmod3_A() that returns both a remainder (modulo) and a quotient. The maximum value we can pass to this function is 192.

Similarly, there's a multiplication routine mul_B_C(), which returns (A*B)%256.

Phew.. I got this far actually not saying a thing that would be useful in the context of implementing QR-code encoder in Z80.

Study the code and provided links in Github. The code should be readable and even contain useful comments ;)
As I used to say back in day:

MOVEQ #0,D0
RTS     ; Successful exit