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!

Market prices in Acornsoft Elite

I wouldn't be exaggerating if I said that the original Elite game has had a huge impact on my life. Whilst I did play other games on my father's BBC Microcomputer, like Hopper and Pinball, I think Elite may still be top of the list in terms of hours played over my lifetime. Moreover, it was Elite that motivated me to badger my dad into teaching me the BASICs of programming, and from there, everything else followed naturally.

So, of course, I'm really excited about the upcoming sequel, Elite: Dangerous. I bought the beta yesterday, but haven't had time to properly play yet, so my verdict is still outstanding. First impressions are good, though.

But the best thing about Dangerous is that you get a copy of the original BBC Micro version of Elite for free. (You can also get it for free if you don't buy Dangerous, by the way.) So while the gigabytes of Dangerous were trickling down my narrow tubes, I fired up the BeebEm emulator and started playing my old childhood classic.

Back when I was a kid, I played very conservatively. Liquor/wines from Lave to Leesti, computers from Leesti back to Lave. Over and over again. Now, of course, I want a little more adventure – not in the least because loading and saving is so much faster. So I started looking deeply into market prices at planets of various types (Poor Industrial, Rich Agricultural), and noticed something weird. Almost everything is more expensive almost everywhere than the “average prices” printed in the Elite manual. What is going on?

Fortunately, back near the turn of the milennium, C.J. Pinder ported the original Elite 6502 assembly code to C, resulting in Elite: The New Kind. A while later, David Braben got wind of this, and ordered it to be taken down. Fortunately, I still had a copy of the ZIP file, which I religiously held on to. It seems Braben has softened since, or got some more sense, or wanted some free publicity, because The New Kind is back online again.

Anyway, I went into the source code of Elite: The New Kind and discovered the shocking truth of these market prices.

First off, no fractional credits exist in memory. Everything is stored in integer values of decicredits, 0.1 Cr. There is a table that contains all the items, together with some metadata about them. Here is the formula for computing an item's price:
item.price = ((item.base_price + (market_rnd & item.mask) + planet.economy * item.eco_adjust)) & 0xFF * 4;
The meaning of each of these fields:

• item.base_price is a constant read from the table of items. It's 19 for Food up to 235 for Narcotics, with the highest value for a legal substance being Luxuries at 196.
• market_rnd is a random byte, 0 to 255 inclusive, generated whenever we do a hyperspace jump.
• item.mask is also constant, varying from 0x01 for Food to 0x1F for Slaves, Alloys and Platinum. An outlier is Narcotics at 0x78, the only value that isn't a series of lower bits.
• planet.economy is set by the galaxy generator to 3 bits of the planet's random seed, so between 0 and 7, inclusive. Its meaning:
  • Bit 2 is the type, 0 for Industrial, 1 for Agricultural.
  • Bits 0 and 1 are the wealth: Rich, Average, Poor, Mainly. The order depends on whether the world is Industrial or Agricultural, and Mainly is in the middle: a Mainly Industrial world is leaning towards Agricultural and vice versa. That's that cleared up!
• item.eco_adjust is a signed number, ranging from -9 for Furs to 29 for Narcotics; the highest value for a legal, buyable item is 14 for Computers.

So how to make sense of all this? How to find out if the manual was wrong, or just my impressions? Let's turn to a tool I feel is undervalued by most programmers: the humble spreadsheet. This Google spreadsheet shows my results. A few things stand out:

• I was right, the manual was wrong. Prices are on average significantly higher than printed. Furs are almost 26% more expensive, and Minerals even 50%! Computers and Luxuries, on the other hand, are slightly cheaper.
• The prices in the manual are taken from the minimum possible price on a Mainly Agricultural world. Except for Narcotics, Minerals and Alien Items, the two are identical.
• My calculations are incorrect for Narcotics because it overflows its byte and wraps around. Calculating how to get the real maximum would be a bit more work, but it must be around 102 credits. With its odd bit mask, Narcotics are the biggest gamble with the biggest potential payoff.
• Planet classification doesn't have two axes (Industrial/Agricultural, Rich/Poor); it has just one. The range is from Rich Industrial to Poor Agricultural.
• The planet's government type doesn't play into it at all. You might think that it would pay better to ship Firearms to an Anarchy world than to a Democracy, but you'd be wrong.
• Prices on a single world are linked; they rise and fall together.
• Profit margins are obviously highest on illegal substances. The best you can do legally is ship Computers from a Rich Industrial world to a Poor Agricultural one, and bring Liquor/Wines back. (Food has an even higher profit margin, but is so cheap that your cargo bay becomes the limiting factor quickly.)

Now I'm back to playing Elite. The old or the new? It's hard to decide!

Password security hall of shame

With the recent Heartbleed vulnerability (wait, why am I even making that a link), I figured it was time to upgrade my password security. Like all proper nerds, I have dozens of accounts all over the web. And like most humans, I am unable to remember distinct passwords for all of them. I'll admit, I have sinned, and reused passwords all over the place. Today, I repent.

So far, my strategy has been to have three tiers of passwords:

• a very strong one for my email and banking
• a moderately strong one for accounts that I somewhat care about
• a laughably weak one for throwaway accounts

The reason that these aren't all strong passwords is that I started using increasingly strong passwords over the years, but never bothered to update lesser-used accounts.

After some research and asking around, my new strategy will be random unique passwords, stored in the password manager LastPass. There are several other password managers, but LastPass is the only one that ticks all but one of the boxes that I care about:

• Easy to use.
• Passwords are encrypted locally and never leave your computer.
• It's available as a browser plugin.
• It's available on Linux, OS X and Windows.
• It's available on mobile devices.

The one box it doesn't tick is being open source, which makes me a bit sad. Open source alternatives would be KeePass or Password Safe (the latter by security expert Bruce Schneier) but neither seems to have great usability.

So I spent a few hours today changing passwords on over 40 websites, and got a nice overview of how different sites approach password security. Here is my bottom-3 of the worst ones.

#3: Steam

You can log in to your account on the web, view purchases, chat with friends, and do many more of the things that nobody ever uses Steam for... but you cannot change your password on the web. You have to use the client for that. (Also, why haven't they bought steam.com yet?)

#2: HSBC

HSBC, the large multinational bank, have a very... interesting approach to login. Some banks use a username/password combination for their online banking. Most will then require two-factor authentication to actually do transactions. Some banks use username/OTP for logging in, where you sometimes need your bank card to generate the OTP.

HSBC does none of these things. Their login flow uses a username, a memorable question, and a 6-digit OTP. The admissible memorable questions are:

• What is your eldest child's middle name? (I don't have any children.)
• Who was your first employer? (Easy to find on LinkedIn.)
• What is your father's middle name? (Somewhat harder to find, probably not impossible.)
• What is the name of the street you grew up on? (Easy to guess if you know where I went to primary school.)
• What was the name of your first school? (And the name of that school is probably on the untrimmed version of my CV.)
• Name a memorable character from a film or book or TV (I wouldn't remember what I'd answered to this one.)
• What is the make and model of your first car? (I never owned a car. And if I still had it, it'd be parked outside my house for all the world to identify. Maybe even on Street View.)
• Name a memorable meal (What?!)
• Name a memorable restaurant (Actually, this one might work for me. But for close friends, my answer would be easy to guess.)
• What is your memorable answer?

Yes, really. The self-referentiality almost makes the entire banking world disappear in a puff of logic. But of course I chose this option, and just entered a password. I can only imagine how this option came about.

Management: "Passwords are too hard. I forgot the password to my email for the third time this month. IT people, make our site use a secret question instead."
IT person: "But they are less secure. They're easy to guess for outsiders. We're a bank, right? We manage people's money."
Management: "I have to rush off to a meeting. You know what to do."
IT person: "Just one more question – what secret questions should we use?"
Management: "You're the expert. Figure something out."
IT person (trying to suppress a grin): "OK, will do."

#1: Charles Schwab

Schwab is a big investment firm that manages stock portfolios, so you'd expect them to be secure, right? Let's take a look at their password policy:

• The password must be at least 6 characters. So far, so good.
• The password must contain at least one digit. OK.
• The digit must be between the first and last characters. What?
• The password must be at most 8 characters. What?!
• The password may not contain any symbols. WHAT?!
• The password is case insensitive. WHAT?!

Even LastPass had some trouble coming up with a password for that.

Well, at least they have recently added the ability to change your username, so I can stop being THOMAS3722. Or was it THOMAS9560? I forgot.

Hodor qualification

In the world of creative programming jargon, we already knew about Yoda conditions (“if three the size is”):

if (3 == size) {
  ...
}

And about Pokémon exception handling (“gotta catch 'em all!”):

try {
  ...
}
catch (Exception ex) {
  ...
}

Now I recently ran into a new antipattern, and decided to name it Hodor qualification after the character from Game of Thrones who can only say his own name.

Hodor qualification is to needlessly prefix calls to static methods by their class name, even from within the same class:

class Hodor {

  private static int foo(int x) { ... }

  private static void bar() {
    return Hodor.foo(1) + Hodor.foo(2) + Hodor.foo(3);
  }

}

Hodor!

Uninstalling old kernels in Ubuntu

One would think that Ubuntu would be smart enough to remove obsolete kernel packages by itself. One would be wrong.

I think the Computer Janitor can clean them up but you still have to run that manually. So I prefer the following command:

uname -r; sudo apt-get remove $(dpkg --get-selections 'linux-image-*' | grep '\binstall' | head -n-3 | cut -f1)

This removes all kernels except the latest two. It prints the currently running kernel version so you can easily check that it's not removing that one.

Turning off the screen saver in Ubuntu

TL;DR: xset s off

“That's easy,” I could hear you think when you read the title. Well, it took me hours to figure it out. It drove me crazy that I'd have to get up and move the mouse every 10 minutes while watching a movie¹, and I couldn't figure out how to disable this behaviour. And when something takes that much effort, I blog about it so that other people might find the solution more easily.

Of course you can easily disable the screen saver through the control panel thing. But I'm not using the Gnome panel, so I never know how to get to that GUI in the first place. Also, you may find, like me, that it just does not work and your screen will still turn black after 10 minutes.

From the console, you can disable the screen saver with:

$ gsettings set org.gnome.desktop.screensaver idle-activation-enabled false

This probably does the same thing as the check box in the GUI. But for me, it wasn't enough: the screen would still blank after 10 minutes!

As it turns out, this is a default built into Xorg itself. Try this:

$ xset q
...
Screen Saver:
  prefer blanking:  yes    allow exposures:  yes
  timeout:  600    cycle:  600
...

Yep, that's the problem. Once you've found it, the solution is simple:

$ xset s off
$ xset q
...
Screen Saver:
  prefer blanking:  yes    allow exposures:  yes
  timeout:  0    cycle:  600
...

This only works until the X server is restarted; put xset s off in your .xsession file to make this change permanent.

---

¹ At least for some movies. mplayer disables the screensaver automatically, but Flash doesn't.

Switching default PulseAudio device when USB microphone is plugged in

I have a PlayStation Eye for a USB webcam and microphone, which is supposed to be supported by Linux. Unfortunately the microphone won't work until I unplug it and plug it in again after boot.

But the unplugging causes PulseAudio to change its default device back to my on-board sound card, which doesn't have a microphone plugged into it. It won't change the default back to the Eye on its own. Here's a workaround, which took me several hours to develop, and isn't for the faint of heart. But it works now, dammit.

All we need to do is nudge PulseAudio a little via a udev event. First, install the daemon package:

sudo apt-get install daemon

Then create a new file /etc/udev/rules.d/99-pseye.rules with the following content (all on one line!):

SUBSYSTEMS=="usb", ATTR{idVendor}=="1415", ATTR{idProduct}=="2000", RUN+="/usr/bin/daemon -- /bin/su thomas -c 'sleep 1 && /usr/bin/pacmd set-default-source alsa_input.usb-OmniVision_Technologies__Inc._USB_Camera-B4.04.27.1-01-CameraB404271.input-4-channels'"

OmniVision is apparently the manufacturer of this camera. Reports around the internet have slightly different version numbers; type pacmd list-sources and use the name of your particular device (which shows up as name: <...>). You also want to replace thomas by your own username; this is used to find the running pulseaudio daemon.

There shouldn't be any need to restart the udev daemon, but if you find otherwise, do sudo restart udev.

The daemon command is needed because we need to delay the pacmd command a bit; if we run it right away, PulseAudio hasn't picked up the new device yet. The trouble is that udev tries very hard to wait for completion of all child processes of the RUN command before firing its events into userland, so PulseAudio will always get its event only after our script has already finished and failed. Even various combinations of & and nohup wouldn't convince udev not to wait, but daemon does the trick.

If this doesn't work, here are some debugging methods that I used. Try adding -o/tmp/daemon.log after /usr/bin/daemon and inspect the output. To watch udev events happen in real time, use udevadm monitor. Another good source of information is /var/log/syslog; do tail -f /var/log/syslog | grep pacmd to filter it. Also check the output of pacmd dump to see whether the set-default-source command has taken hold.

Oh, and the upstream PulseAudio people in all their wisdom decided (bug report) that 4-channel microphones like this one don't deserve to have a default profile, resulting in the message Failed to find a working profile in /var/log/syslog. The result is that PulseAudio will retry loading, and retry, and retry … causing brief and hard to debug system freezes once every minute or so. To make the microphone work at all in Ubuntu 12.04 (bug report), you also have to add the following at the end of /usr/share/pulseaudio/alsa-mixer/profile-sets/default.conf:

[Mapping input-4-channels]
device-strings = hw:%f
channel-map = front-left,front-right,rear-left,rear-right
description = 4 Channels Input
direction = input
priority = 5

[Profile input:mic-array]
description = Microphone Array
input-mappings = input-4-channels
priority = 2
skip-probe = yes

Then type pulseaudio -k to reload the daemon (it will be restarted on demand). Yes, this will be overwritten on upgrades. I've found no way to work around that yet.