Sunday, January 18, 2015

QR codes on the BBC Micro, Part 1 of 6: The beginning

In which I revel in nostalgia and explain what this series is all about.

On a shelf in my dad's study, there is an old photograph, made some time in the late '80s. In it is my dad, with 3-year-old me sitting in his lap, looking at this very device:

My first computer, the BBC Micro.
Some of you might recognize this beauty as a BBC Microcomputer. One of the best things to come out of the '80s, the BBC Micro (or “Beeb” for short) became hugely popular in the UK, and to a lesser extent in the rest of the world. They were used at the school where my dad worked, and that's how this specimen ended up in our house. I'm not exaggerating if I say it has been a defining influence on the rest of my life.

But at some point, the PC took over the world, and our house. At first the Beeb was moved to my bedroom, but it eventually ended up in a box in the attic when I got a PC of my own. The reason it's now sitting on my desk again is that my parents are moving house, and would rather have thrown it away than move it to a different, much smaller attic. I couldn't let that happen. Having moved all my possessions between four countries I'm not one to get attached to inanimate objects, but this little machine is special.

On the other hand, in the digital world, I'm a bit of a hoarder. My fileserver still contains my university coursework, the Word documents that I wrote for school assignments at the age of 14, and the source code of the games I made on my first PC and tried to sell to people on floppy disks. But the record becomes harder to access beyond that: my very first programs were written on the BBC Micro, and are stored on these old 5¼" floppy disks, which don't fit into my PC's USB 3.0 port or its BluRay drive.

Sadly, these old floppy disks don't have eternal life. Nor does the Beeb. Nor its disk drive; these drives are notoriously fragile, and a replacement might be hard to find. So I set out to salvage the earliest work in my programming career and back it up onto more modern media. It would be the completion of the earliest records of my digital life.

From the low-level software point of view, a floppy disk contains just a series of bytes. If we transfer all the bytes and put them into a file on the PC, we have created an image of the floppy: an exact replica, which can be loaded into an emulator like BeebEm and used as if it were the real thing. And since the image is just a file, it can be backed up on any of the many storage media available today and in the future.

But as I mentioned, my PC does not have a floppy drive. The PC I had before this one didn't either. The one before that might have had a drive for the “modern” 3½" not-so-floppy disks, not the 5¼" that the BBC Micro uses. Old IBM hardware, like 286 and 386 PCs, typically did use these floppies, but I think they were in an incompatible format. Even if not, the flatcable that connects the computer to the drive is definitely different.

So my best bet seemed to be to let the BBC Micro itself read the disks into memory, and somehow transfer the data to the PC. Easier said than done. The Beeb predates the Wifi era and even the Ethernet era. It does come with its own type of networking interface, called Econet, but of course no modern machine has any clue how it works.

Another option would be the 5V analogue I/O port. I once used this to transfer data between the Beeb and my TI-83 graphical calculator, so I knew it was possible. Most PCs built in the 90's came with an RS-232 serial port, but the voltage levels are different. I would need to build some kind of adapter, but I'm not an electrical engineer, and I was terrified of blowing up my only remaining Beeb by accident. Moreover, my PC lacks such a serial port to begin with.

So I started considering more arcane options. The first thing I thought of was sound. The BBC Micro comes with a pretty cool 4-channel audio chip, and even from BASIC you can make it play 256 different pitches. That's one tone to transfer one byte – great! On the other end, we could do an FFT to detect the pitch, and map it back into a byte. However, the minimum duration of such a tone is 1/20th of a second, so the maximum transfer rate would be 20 bytes/s. At that rate, copying a single 180 kB floppy disk would take over 2.5 hours of listening to noisy bleeping and blooping. Not fun, but definitely doable! I was encouraged.

However, there is a drawback. We need an exact copy of the signal. Misinterpret a single byte, and the program ceases to work. Worse, if we lose or gain a byte halfway the stream, the entire alignment of the data is thrown off and the floppy image becomes unreadable.

So at the very least, we need a checksum. CRC32 is relatively easy to implement and might work well enough to detect errors. But checksums are just a class of error-detecting codes, so while they can tell me that the transfer went wrong, they cannot tell me where or how, and that would be 2.5 hours of bleeping and blooping down the drain.

What we really need here is an error-correcting code. The most well-known is the Reed-Solomon code, used for data transfers from the Voyager space craft, and more recently also on CDs, DVDs and Blu-ray discs. But there's another place where RS codes are used.

A QR code containing the text “HELLO WORLD”.
The ubiquitous QR code, used on posters, milk cartons, websites and even tattoos, is little more than a bunch of 1s and 0s encoded as black and white squares, with Reed-Solomon error correction codes on top, and some markers thrown in to help the scanner. Would it be possible to display a floppy's contents on the screen as a series of QR codes, scan each of them with a smartphone, and assemble them at the other end into a disk image?

Let's see. Most QR codes are fairly small, as they contain just a web address or some such. But they can actually grow to the “Level 40” monster code of 177×177 squares, which (at the lowest error correction setting) can hold 2953 bytes of arbitrary binary data. That's about 60 QR codes to transfer the contents of one floppy. At a conservative rate of one QR code per minute, I'd be able to reliably transfer an entire floppy in an hour.
A level 40 QR code from Wikipedia. I haven't checked whether it contains anything NSFW.
Encouraged, I did some back-of-the-envelope time and memory calculations. About 4 kB for the QR code data bits, and maybe another kB for scratch data. In screen mode 4, we have about 16 kB to play with, so that leaves 11 kB for the BASIC program and its assembly output. A tight squeeze, perhaps, but not impossible.

On to calculating time. Maybe it takes 1000 clock cycles to generate one pixel, so at the 2 MHz that the Beeb runs at, we should be able to generate a QR code in 16 seconds. Even if I'm off by an order of magnitude, that's still fine.

So let's do this!

No comments: