Monday, January 19, 2015

QR codes on the BBC Micro, Part 2 of 6: Proof of concept

In which I learn about weird video memory conventions and run a small-scale experiment.

Before diving in and writing assembly code to generate QR codes on the BBC Microcomputer, it seemed wise to check whether those could be read from the screen at all. After all, it's an old monochrome 50 Hz interlaced CRT monitor, and although the pixels are quite large by modern standards, they are far from stable, crisp squares. The picture flickers, and bright pixels tend to bleed into darker areas. Would my phone's camera and QR app even be able to recognize the code?

So I took the example QR code from this excellent guide, and started to convert it to a bunch of bytes. This is a 1-Q code, the smallest variant, easy enough to type in by hand once I've got the raw bytes printed on my PC screen. It contains the text “HELLO WORLD” in alphanumeric encoding.

Using the Gimp to downscale the image, remove the border and convert it to a PGM file was easy enough. PGM is an image format that supports an ASCII-based variant, so it's trivial to read such a file in a C++ program.

The idea was to have the C++ program pack the pixels into bytes, as a monochrome image at 1 bit per pixel. The Beeb's display memory is a part of its main memory, so we can put things onto the screen simply by writing the bytes into this memory.

So where exactly is this display memory? This depends on the screen mode. The Beeb has 8 screen modes, 0 through 7, each with its own characteristics: resolution, colour depth, and memory usage. The largest possible QR code is 177×177 modules (“pixels”), so I'd need at least that much resolution, but I didn't care about colours and would be fine with monochrome (1 bit). Moreover, the pixels must be more or less square; mode 2 in particular has very squashed pixels. It seemed like mode 4 would be my best bet: 2 colours (black and white), at 320×256 pixels, taking up 10 kB of the computer's 32 kB of RAM. These 10 kB are mapped into the addresses &5800&7FFF. (On the Beeb, & is used to denote hexadecimal numbers).

But here the fun begins. You'd expect the pixels to be stored linearly in memory: the first byte contains the 8 leftmost pixels in the top row, the next byte contains the 8 pixels right to those, and so on. But on the BBC Micro, things work differently: the first 8 bytes go down to form the first character cell, then we jump back up and to the right to the second character cell, and so on:

The memory layout for graphics mode 4.
I guess it works this way to make displaying characters faster, because they can be written into 8 contiguous bytes of memory. This mapping will probably cause me headaches down the road, but once you know the system it's easy enough to code for. After a while I had a BASIC program to poke the right bytes into the right place in memory:


I typed it in, fixed the typos, and tada! A QR code! On 30 year old hardware!

A QR code displayed on the Beeb's monitor. Maybe the first ever?
Now the big question… will it scan? I launched the ZXing Barcode Scanner app, pointed it at the screen, waited for the camera to focus, and… nothing. I fiddled with the brightness and contrast knobs on the CRT, but to no avail. The scanner showed brief blips of partial recognition everywhere but in the actual code.

Would this project be doomed to fail before it even got properly started? Let's try one more thing. The QR code specification says that it's legal to invert the colours on a code, like we've done here: what is normally dark is here shown as light, and vice versa. However, this is an addition to the 2005 edition of the spec. Perhaps it's not implemented? So let's invert the screen and find out:

200FORI%=&5800TO&7FFF:?I%=?I% EOR &FF:NEXTI%

A quick explanation for the uninitiated is probably in order. It's just a for loop from &5800 to &7FFF, inclusive. The loop counter is I%, one of 26 resident integer variables, presumably a bit faster than a plain I. Spaces are optional in most of BBC BASIC, which means you can write stuff like FORI and it will recognize the FOR keyword just fine. (This also means that you are in for a surprise if you name your variable ANDY, DIVA or COST.) For each of these addresses, the ? operator is used to query the byte (“peek”), EOR is used invert it by xor'ing it with &FF, and ? is used again to store it back.

So I waited for some 15 seconds while this loop ran and inverted the screen, and ended up with a properly uninverted (outverted?) QR code.

An uninverted QR code displayed on the Beeb's monitor.
The big question again… will it scan? And after lowering the brightness on the monitor to reduce blooming, the answer is a resounding YES! The code was recognized almost instantly, and the text HELLO WORLD appeared on my phone's screen.

ZXing Barcode Scanner correctly recognizing the above code.
Even at a distance sufficient to scan a screen-size QR code, it still worked quickly and reliably. So far, so good!


Alex Taylor said...
This comment has been removed by the author.
Alex Taylor said...

You can invert the screen much more easily than that by redefining the colour palette with VDU 19.