## Running a Z-machine on an AVR

This blog has moved and won’t be updated here anymore. It’s now at blog.dsp.id.au

.

Can you make a Z-machine console – a virtual machine for text adventure games –  complete with screen and keyboard on an AVR?

No. Well, probably not on a ATmega328P.

I got the code for ZIP, and stripped out all of the code for reading files and displaying stuff on the screen.  This let me compile it with avr-gcc.

I looked at the result of objdump:

$avr-objdump -h zip_linux zip_linux: file format elf32-avr Sections: Idx Name Size VMA LMA File off Algn 0 .data 000001e4 00800100 0000579c 00005830 2**0 CONTENTS, ALLOC, LOAD, DATA 1 .text 0000579c 00000000 00000000 00000094 2**1 CONTENTS, ALLOC, LOAD, READONLY, CODE 2 .bss 00000ac8 008002e4 008002e4 00005a14 2**0 ALLOC 3 .stab 0000dcec 00000000 00000000 00005a14 2**2 CONTENTS, READONLY, DEBUGGING 4 .stabstr 00003aad 00000000 00000000 00013700 2**0 CONTENTS, READONLY, DEBUGGING 5 .comment 00000022 00000000 00000000 000171ad 2**0 CONTENTS, READONLY  The good news is that the code (the .text section) fits into 22k. That leaves 10k for the screen rendering code (probably from TellyMate), the keyboard and the SD card code. The .data section is quite small too, which means there aren’t many strings in the interpreter itself. The problem is the .bss section, which gets copied to RAM on startup. It’s 2760 bytes, much more than the 2048 which this chip has. Let’s look at this further: $ avr-objdump -t zip_linux | grep bss | sort -t $'\t' -k 2 ... 0080030c g O .bss 00000004 pc 00800da6 g O .bss 00000006 __iob 00000114 g .text 00000010 __do_clear_bss 00800552 g O .bss 0000004e lookup_table 00800436 l O .bss 00000100 record_name 00800332 l O .bss 00000100 save_name 008005a0 g O .bss 00000800 stack There’s a 2048 byte stack, which fills the entire memory! The Infocom games might only need a 1k stack, which will help. Tellymate has a 38×25 screen, which needs 950 bytes. This could be brought down to 10 lines, but games might be tricky to play. The ZX80 didn’t store a full line if it didn’t fill the width of the screen, but adventure games tend to be wordy so this won’t help much. An SD card library needs about 600 bytes of RAM, which blows the budget. We’d have to go without a filesystem on the SD card, because it takes up too much flash space. It sounds like the 512 byte buffer might be optional. 4k of RAM should be plenty. But with ARM chips being much cheaper than the larger AVRs, that might be the way to go – if I can sort out the jittering image problems. You might be able to squeeze the interpreter only onto the chip, and communicate with it via its serial port, or another AVR running TellyMate. Update: It turns out I wasn’t the only one to look at this – Rossum implemented it on the 2560-byte ATmega32U4, but needed to store a 1MB swap file on the SD card! I don’t know why you need that much – maybe you don’t – but I forgot to include dynamic memory and room for the stack. ## OpenWRT on a Nokia N800 This is work in progress, so expect it to be added to/abandoned (probably the latter) at any time. I’ve got a Nokia N800 whose screen is on its way out that I’d like to find some other use for. Since Nokia seems to have abandoned this device, it looks like I’m on my own. (To think I used to like their products!) Good thing I still have a copy of the firmware, and found a copy of the flasher software. Let’s hope Nokia really doesn’t care, and lets this link stay here. Anyway it looks like OpenWRT supported it once upon a time – it’s still listed in the source tree, albeit broken. The omap24xx doesn’t seem to be in any of the branches or tags, so I don’t know how things get there. Revision 30798 seems to be before they added the “broken” tag, so maybe that’s a good place to start. $ git clone https://github.com/mirrors/openwrt.git
$cd openwrt.git$ git checkout 2f3210027ca1393766b0293b1bdd9fc6a13e88d7
$git branch n800$ git checkout n800

So now you apparently:

$make defconfig$ make menuconfig

select the N800/810 as the target

$make I had a problem with mklibs not working with GCC 4.7, which was easily fixed (I made it as a patch). And that worked for me! In bin, I have a kernel, root filesystem and so on. # Testing it out I happened to notice that you can boot a kernel that’s been loaded into RAM: $ sudo flasher-3.5 -k openwrt-omap24xx-zImage \
-r openwrt-omap24xx-root.squashfs -l -b"root=/dev/ram0"

That seemed to work, and the kernel output appears on my dodgy screen.  That stuff with the root filesystem didn’t seem to work, but I noticed that the kernel was trying to look for the root filesystem on an MMC card.  I grabbed a convenient SD card and put the root filesystem on it, and the boot process seemed to go a bit further.

One problem: I get “Press enter to activate this console”.  Without a keyboard, how will I do that?

Now that it boots, how am I going to communicate with it?  It’s alright for a N810, which has a keyboard, but the N800 doesn’t.  Apparently there’s a serial port in the back near the battery, but I don’t know how I’d attach cables to those pads.  Maybe I can plug a USB keyboard into the USB OTG port.

Maybe someone has sorted it out – Google to the rescue again!  Apparently you have to:

$make menuconfig Base system: <*> busybox: Linux System Utilities: <*> lsusb Kernel modules: USB Support: <M> kmod-usb-hid The kernel module was already selected for me. Exit, save, then make. Looking in the new root filesystem, lsusb is there. I just found out about 0xFFFF, another flasher for this device. Let’s give it a whirl: $ sudo 0xFFFF -i
...
Device's USB mode is 'client

Maybe the USB port needs to be switched into OTG mode.

$sudo src/0xFFFF -U 1 ... Set USB mode to: 'host'. I’ll try loading the kernel again, and… no luck Maybe OpenWRT doesn’t have any hotplugging function. I’ll try logging as much as possible on the console by setting klogconloglevel to 8 in /etc/config/system. But there are two problems with this: I want to see syslog, not the kernel log; and that property doesn’t seem to be used anyway. During random googling, I found a link to Qemu. It turns out Qemu can emulate the N800! There seemed to be no keyboard input – since the n800 doesn’t have a keyboard – but apparently the connector near the battery is the 3rd serial port. So you can solicit a terminal like this: $ qemu-system-arm -machine n800 -drive file=root,if=sd -kernel \
openwrt-omap24xx-zImage -serial vc -serial vc -serial stdio

where root is an SD card image containing the root filesystem.

Now I’ve got something I can interact with, which should make things easier! (It sounds like the Bluetooth module is connected to one of the UARTs, which the above command might upset.)

## Science Alive noise maker

For Science Alive, I made a simple circuit that made noises in response to light changes.  Being something which makes noise it was popular with the kids.  It’s based on circuits described in Nicolas Collins’ “Handmade Electronic Music“.  A few people asked me a circuit so I’ll describe it here.

The circuit contains four oscillators provided by a 4093 Schmitt Trigger quad 2-input NAND gateIndividual inverting Schmitt trigger gates can oscillate, and by having more than one I could get one to turn another on and off, and mix the output of different oscillators together.

You’ll need to play with different valued capacitors, I’ve listed the values I’ve used but try some different ones, particularly since your LDRs might be different to mine.

You’ll need:

• 1 4093 CMOS Schmitt trigger quad 2-input NAND gate
• 2 small value electrolytic capacitors (I used 1µF)
• 2 ceramic or greencap capacitors (I used 47pf)
• 2 diodes (I used 1n914)
• 4 light dependent resistors (LDRs) aka Cadmium Sulphide (CdS) cells
• Batteries which provide 3-12V (I used 4×AAs) and a way to connect them to the breadboard
• An amplifier and speaker, computer speakers or those battery powered speakers you get for music players should work
• A breadboard (mine is a 390 hole “half size” one), and suitable wire

Here’s the schematic.  I chose to pair my oscillators so that one turns the other on and off, and connected their outputs with diodes.  You can connect all four together in a line, or connect all of the outputs using diodes.  I’ve shown  a resistor to pull the output down when the oscillators are all low, but the amplifier probably has enough resistance at its input for that.

It looks like this wired up on a breadboard:

Mine looks like this:

You can also see this video of it in action.

## Synchronize a Linux box to a digital TV signal

I remembered seeing some command which could synchronize the system clock to the digital TV (DVB) signal. This is ideal for a MythTV box which isn’t connected to the internet.  It’s dvbdate. One problem: it ignores the system time zone. It can use the TZ environment variable, whose current value can be obtained using the date command:

date +'%z'

so this will set the date:

sudo TZ=$(date +'%:z') dvbdate --set so you can put this script in /etc/cron.hourly, and make it executable: #!/bin/sh -e TZ=$(date +'%:z') dvbdate --set

## Implementing the virtual guestbook

So how about implementing the virtual message board?  I’ll try it in a virtual machine first.

# The VM

Create a new Virtualbox VM, give it 32MB of RAM, and get it to boot of the x86 image.  Give it two network adapters: one on an “internal network” – this will represent the wireless network – and one set to NAT, this will be the ethernet port that we can log in with.  You can forward a port through the second adapter for telnet access, that way you can cut and paste stuff.  Start it up.

# Cleaning up

We don’t need anything related to the GUI configuration, since it probably won’t work when we’re done.  Remove any packages starting with luci, then remove lua and uhttpd.  opkg doesn’t seem to have the concept of an automatically installed package, so you’ll need to remove dependent packages yourself.

# Networking

The “wireless” network needs a static IP address, because it needs to be the DNS and DHCP server for whatever connects.  The other network adapter is used to get to the internet, and needs connect to some other gateway instead.  I put this in /etc/config/network:

config interface lan
option ifname eth0
option proto static
option auto 1

config interface wan
option ifname eth1
option proto dhcp
option auto 1

# The web user

Add a user to run the web server as.  There doesn’t seem to be a command to do this, so add this to /etc/passwd:

www-data:*:99:99:daemon:/var:/bin/false

# The web server

Install Hiawatha.  It doesn’t seem to come with a startup script, so stick this in /etc/init.d/hiawatha:

#!/bin/sh /etc/rc.common

START=98

SERVICE_DAEMONIZE=1
SERVICE_WRITE_PID=1
SERVICE_PID_FILE=/var/run/hiawatha.pid

start() {
mkdir -p /var/lib/hiawatha
mkdir -p /var/log/hiawatha
service_start /usr/sbin/hiawatha -d
}

stop() {
service_stop /usr/sbin/hiawatha
}

The OpenWRT init scripts are a bit unusual, but it keeps track of the process ID and things like that.

Run /etc/init.d/hiawatha enable to make the script work.

## Configuration

Some basic Hiawatha configuration. These go in /etc/hiawatha/hiawatha.conf:

I’d like to limit the size of POST messages, so nobody fills up the disk. Hiawatha has an option for this (this sets it to 4kB):

MaxRequestSize=4

This doesn’t work with the (rather dated) version of Hiawatha in OpenWRT.
It should run as our www-data user:

ServerId = www-data

Hiawatha needs to be told what to do when it sees a PHP file.  I’ll use FastCGI so I can limit the maximum number of PHP processes that run at once:

FastCGIserver {
FastCGIid = PHP5
ConnectTo = /tmp/guestbook-fastcgi
Extension = php
SessionTimeout = 30
}

This describes how to handle the “php” extension, but it doesn’t tell it to actually use it.  Note the “FastCGIid” line, this needs to go later in the file where the “default” site is configured – that is, where WebsiteRoot is.

UseFastCGI = PHP5

There will be more configuration later.

# PHP

Install php-fastcgi.  We’ll need a socket for the web server to talk fastcgi to, so put this in /etc/config/php5-fastcgi:

config php5-fastcgi
option enabled 1
option port /tmp/guestbook-fastcgi

I’m sure /tmp isn’t the place to put this but since /tmp is a ramdisk and is empty on each boot, this should be fine.

I had to add this near the top of /etc/init.d/php5-fastcgi to stop it running as root:

SERVICE_UID=99

Also, to limit the number of connections that PHP handles at once, change the service_start line to look like this:

        PHP_FCGI_CHILDREN='4' \
PHP_FCGI_MAX_REQUESTS='50' \
service_start /usr/bin/php-fcgi -b \$port

Hopefully this means that if more than 4 clients connect, the others will have to wait until another request finishes.

# dnsmasq

I want to get clients to connect to some website – presumably their home page – to be redirected to the guestbook.  One way to do this is to change each name lookup to redirect to the router instead.

It turns out that’s not hard; this goes in /etc/dnsmasq.conf:

address=/#/192.168.199.1

This tells dnsmasq to resolve all adresses to the router.

It’s also probably bad to do this on the wired interface though, so this line should do this:

interface=eth0

(or whatever the wired interface is)

## The Virtual Guestbook

This is work in progress, so there’s plenty of gaps!

I’ve been asked to look at using a venerable TP-Link TL-WR703N as a virtual guestbook, where people can connect using Wi-fi and leave a message.  I plan to use OpenWRT on it, since they support that device.

It will have a USB stick attached to it, so there will be plenty of storage space (kind of, see below) and the CPU is adequate, but the system needs to fit in 32MB of RAM, so there’s a few things to consider.

# The web server

The OpenWRT wiki lists a bunch of available web servers.  Here’s what I think of them:

Server Notes
Apache HTTPD ✗ Big. Not really designed for this kind of thing.
Hiawatha ✓ Small
✓ Virtual hosts
✓ CGI
✓ FastCGI
✗ No CGI process limiting
Busybox HTTPD ✓ Small
✓ FastCGI
✗ No logging to Syslog
✗ No connection limiting
lighttpd ✓ Very configurable
✓ FastCGI
✓ Built-in PHP support
✓ Virtual hosts
✗ No 302 redirection support
✗ A bit big
mini-httpd ✓ Small
✓ CGI
✗ No virtual hosts
✗ No connection limiting
nginx ✓ Very configurable
✓ CGI and FastCGI
✓ Virtual hosts
✗ No CGI connection limiting
uhttpd ✗ No setuid
An inetd wrapper ✓ Control of the number of processes
✗ I’d have to write stuff myself, with the associated performance, conformance and security gotchas.

I need virtual hosts so when people open their web browser and go to some random site (whatever their home page is), they get redirected to the guestbook. Ideally this won’t be a 301 permanent redirect, so when people go to their Kittenwar home page they don’t end up being sent to the (now non-existent) guestbook.

None of these can log to syslog. I’d rather not log to a file because it causes extra flash wear. Busybox provides a ring buffer for logging. I tried messing around with fifos instead but couldn’t get it to work.  Maybe I’ll use a tmpfs for /var/log and logrotate them to flash.  (Actually /var already points to /tmp, which is tmpfs.)

I can only run a few processes at a time before the RAM fills up. This could be handled by the web server, or if fastCGI is used, the runtime for the script. I first thought I’d only server one at a time, but if one client isn’t responding that will block all other users. 4 processes should be enough.

Setuid would be handy so the server can run at port 80 as an unprivileged process, but I could use iptables to redirect the port instead.

Hiawatha looks like the most suitable, but nginx would be OK too. Neither can control how many CGI processes are run, but PHP has a FastCGI option that does this.

# The post script

Something needs to handle the form submission. For a small environment C would be the ideal choice, but it’s hard to avoid security problems and I’d rather avoid having to use the OpenWRT build environment.

The options I see are PHP, Perl and Lua. PHP is good for this kind of thing and I’ve actually used it before, so it will do. PHP also has control over POST sizes (I don’t want people filling up the storage) and how many processes it starts.

While running, PHP seems to use about 1MB of private space per instance, so a few processes can run. I’ll need to try it in FastCGI mode too.

# The filesystem

The device only has 4MB of storage, so jamming the web server and PHP into that could take some doing. I do have perfectly good and relatively unlimited storage on the USB stick. I’d like to overlay a filesystem on the USB stick over the stock OpenWRT image to give me plenty of space.  I’ll also know exactly what I’ve changed by looking at the overlay filesystem.

One problem with this system is it can have its power cut at any time. I’ll have to live with that risk. ext4’s journal should help avoid fscks, and there won’t be that many writes so the journal shouldn’t make much difference to the flash life (I’d expect hundreds of writes a day, not millions).

# The database

I can think of three options for this: one flat file, one file per post and sqlite.  I’ll rule out sqlite because I don’t know what its memory consumption is like, and PHP doesn’t seem to give you access to any memory tuning options.

One flat file would be the most space efficient, but corruption could be a problem if the device loses power or I stuff up the post script and there’s concurrent access.  I don’t get random access either, should I want to “show the last few messages” or something.

One small file for each post allows random access and reduces the chance of corruption.  It wastes a lot of space, but I have a whole USB stick to use, and using smaller clusters on the filesystem should limit that.

# Recording stuff

There are some other small problems: the device has no idea what time it is or where it is.  This information can come from Javascript in the browser.

# The captive portal

When you use some wireless hotspots, they first redirect you to a page with their legalese on it.  This is called a Captive Portal.  I can use the same thing here to redirect the user to the guestbook when they open their browser.

The idea in this case is to tell the client computers to use the router as the default gateway.  iptables then redirects all connections to a web server, which does a temporary redirect to the real web server.  If the clients have cached DNS entries, this method should affect that the least.  This is why virtual hosts are useful in a web server – any host but the correct one will get the redirect page.

## Frickin’ lasers

I purchased a quantity of cheap laser modules for a project.  They were advertised as 3V modules, but they all have 39Ω resistors in series for current limiting.  When connected to two AAA batteries, I measured 15mA and a forward voltage of 2.15V.  This makes the resistor value 0.85V/15mA=57Ω though.

## Video signal output circuitry

I’ll need a simple circuit to mix my video signals together. The Arduino TV Out library shows how to do this, but that works with 5V IOs, but the STM32L Discovery (and all ARM chips AFAIK) uses 3.3V.

So which resistors will I need?  To produce a white signal, the sync and video lines will be high.  The equivalent circuit looks like this:

(The 75Ω resistor is the resistance inside the TV).

To show a black signal, the sync line will be high, and the video line will be low, which looks like this:

Wikipedia gives the formula for a voltage divider, so the resistors in the first diagram can be calculated with this formula:

$1= {75 \over {75+{1 \over { {1 \over V} + {1 \over S} }}}}\times 3.3$

and in the second:

$0.3= {{1 \over {{1 \over V} + {1 \over 75}}} \over {1 \over {{1 \over V} + {1 \over 75}}} + S} \times 3.3$

I tried solving these, but that’s well beyond my mathematical ability.  Instead I found some online site that could plot the two formulas (edit: I could have used Wolfram Alpha).  The lines crossed at about RV=250Ω and RS=580Ω. These resistor values don’t exist, so RV=270Ω and RS=560Ω is close enough.  They seem to work fine in the circuit.

## Whiteboard bot’s first drawing

Here’s the first drawing from my whiteboard robot! It doesn’t draw anything by itself because I must have messed up the maths, but I was able to operate it manually and draw some circles. The lines are wonky because the wall the board was attached to was shaking. I didn’t get the pen to move in and out, to draw separate lines.

The robot suspends a whiteboard marker from two strings.  The strings are wrapped around pulleys.  The strings are wound onto spools, driven by motors connected via a serial link to a PC.  The PC interprets an SVG image, and calculates how much each motor needs to turn to draw each line segment.

It’s currently being driven with a Pololu Baby Oranguatan and some DC motors  that were lent to me, and various 3D printed parts to hold the pen and wind the string.

I have a few complaints about the Baby Orangutan.  First is their choice to use two wires to connect the H-bridge driver.  This makes the motors slightly easier to move, but means that to drive two motors, you need to use both 8-bit timers on the AVR.  With a 3-wire connection (two for direction, one for PWM), I would only have needed to use one timer, leaving the other one for Arduino compatibility or to drive the servo which moves the pen in and out.  My other issue is the placement of the status LED: I would have thought it goes on port B5 – like the Arduino – but they put it on one of the serial port pins, making it useless if you’re using the serial port.

I had the circuit powered at Science Alive for a few hours, but the manual movement function stopped working.  I connected the circuit on perfboard using very thin enamelled wire.  I doubled the wires between the H-bridge chip and the motors, but wasn’t smart enough to do the same for the power supply, so there might have been some brownouts when the motors started.  I should add some capacitors too.  The motors were less powerful than I expected, so my 10cm reels put a bit too much strain on the motors.  I’ll have to get some smaller reels printed.

I think I’ll get the simulator running again – hopefully that will help me get the calculations for the reel movement correct.

## Whiteboard robot number crunching

I’m thinking of building a robot that suspends a whiteboard marker from two strings, and draws on a whiteboard. There would be two motors that can change the length of the strings.

I was playing with some calculations for this robot, literally on the back of an envelope. I need to calculate how long each string will be for a particular coordinate.

Pythagoras’ theorem gives:

$l_1^2=x^2+y^2$

and

$l_1^2=r^2+s^2$

If we smash them together, we get:

$r^2 + s_1^2 = x^2 + y^2$

$s_1 = \sqrt{x^2+y^2-r^2}$

and of course

$s_2 = \sqrt{(w-x)^2+y^2-r^2}$

That was easier than I expected – the maths wasn’t too hard! This should be enough to draw short segments with linear interpolation.

But, I’d like to know how the string length changes as I draw a straight line. Imagine a line being drawn perpendicular to the string; when the length of the string gets very long, it should lengthen at the same rate as the line. This suggests that the string length and the line length forms a hyperbola.

Consider a horizontal line beneath one of the wheels. Let x be the distance from the closest point on the line to the wheel. s is the string length. If the line went through the wheel, the graph

$\frac{x}{s}=1$

would give the line where the x position is the same as the string length.

If the line does not pass through the wheel, this equation from earlier where r is the wheel radius and y is the shortest distance from the wheel to the line:

$s^2 = x^2 + y^2 - r^2$

can become

$1 = \frac{x^2 + y^2 - r^2}{s^2}$

which should produce a hyperbola. When the string is long enough, y²-r² becomes negligible.

Previously I’ve implemented Bresenham’s algorithm to interpolate values on an AVR; it would be nice to do the same thing to calculate this parabola while drawing a straight line segment. It turns out someone has worked out how to use calculations like this for hyperbolae.