FPGA based tabletop Pengo console

As a kid in the 1980ies, one of my favoured arcade games was Pengo, a maze action / puzzle game. I spent most of my pocket money playing it, and when I was introduced to dialup bulletin board systems in the same era, I chose Pengo as my online nick name, which stuck for some 10 years.

The adaptions of the game for home computers never sparked any fire in me, though, mostly because of the inferior graphics. The arcade version only had a display resolution of 224 by 288 pixels, but sprites and colors made it much prettier than what Sinclair ZX Spectrum, Amstrad CPC 464 or Commodore 64 could do.

At one point, a friend gave me an original Pengo arcade game logic board, which I have been carrying around for years, always wanting to make it playable at some point. Due to the non-standard video output generated by the board, I've never actually done it. Recently, I wanted to do something electronics related in my free time, and I picked the Pengo project up.

Arcade game emulation

Emulation is a common way nowadays to run ancient software. The older the software is, the harder it usually gets to find original hardware to run it on. Emulators provide a way to run original ancient software on current hardware, using software to impersonate the original hardware that the program expects to run on. Emulators exist for all kinds of systems and they are also useful when developing for embedded or other non-desktop environments.

Arcade game emulation is rather popular, with the open source MAME emulator being ubiquitous. MAME emulates all sorts of game hardware, starting in the 1970ies up to rather recently. Versions for most popular desktop operating systems are available, and there is MAME4ALL for the Raspberry Pi, too. MAME emulates the hardware for a huge number of games, but it is not distributed together with the ROM images for any of these games, for licensing reasons. ROM images are distributed through the familiar channels, though.

Another way to run older software is to use an FPGA to actually implement the original hardware. In the FPGA, almost arbitrary digital hardware can be created using configuration, so to run arcade software, one needs to recreate the original hardware in a hardware description language. Several arcade hardware systems have been implemented using FPGAs, and Pengo is one of them.

Compared to the software emulation approach that MAME uses, hardware emulation is less flexible as only one typically only one game fits into the configuration memory of one of the cheap FPGA boards. Also, fewer hardware emulations are available. FPGA based emulation boots quicker and requires less power, though.

FPGA based Pengo build

As I wanted to play with FPGAs again, I opted to use a Paplio Pro FPGA board for which a port of Pengo exists. The port includes a video scan doubler so that a standard VGA output signal is generated. All I/O is done through an Arcade MegaWing, which conveniently makes all I/O needed for emulating Arcade hardware accessible on standard connectors.

Wanting to finish up the project once and for all, I decided to get a cheap, used Dell 1504FP 15'' TFT monitor, a Zippyy Arcade and Fight Stick, a bunch of arcade buttons from eBay and talked my brother, who is a carpenter, into helping me build a proper desktop cabinet in his workshop.

To complete the hardware, I found myself a nice industrial 5V switched mode power supply to power the FPGA board and a small Kemo M031N audio amplifier module connected to a speaker.

The port of Pengo to the FPGA required some tweaking in the top level VHDL module to adapt it to the wiring that I used inside of the cabinet - The first joystick port is used for the coin and start signals, the second port is connected to the joystick. I also tweaked the DIP switch settings to suit my taste, which is something that must be done in VHDL as the Arcade MegaWing does not have switches that one could use for run-time reconfiguration.

More games!

At this point, my tabletop console only works for Pengo, and sure enough there are other games that one would want to play on it. Using a more flexible MAME based engine would get me there, and I experimentally swapped the FPGA board for a Raspberry Pi with MAME4ALL. While Pengo works fine on the Pi, the video display quality is much lower because MAME4ALL unconditionally uses antialiasing. This makes the resulting image blurry, no matter what physical resolution is chosen for the Pi. The FPGA based emulation uses simple scan doubling for video scaling which results in super-crisp display quality even though the TFT's physical resolution is not matched by the FPGA video output. So for now, I'm going to stick with the one game solution until MAME4ALL is fixed or I can find another way to run MAME.

Using Pogoplug as a OpenVPN server - with FreeBSD and VLAN

Recently, I needed to establish a VPN between my office, a colocated server and my home office. I generally prefer building networks on my own rather than buying cheap customer grade appliances, so here is what I've used.

Router

As router, I use a Pogoplug E02. It is marketed as a "private cloud device" and basically is a Linux based NAS with Internet sharing built in. Hardware wise, it is an ARM box with 256 MB RAM, four USB ports and one Gigabit Ethernet port in a funny looking plastic enclosure, with a built-in power supply. Kind of an industrialized Raspberry Pi, if you will. The E02 is from a previous generation and no longer marketed by Pogoplug, but it is available from a number of sources for prices below $50 - Mine cost 35 Euro a piece. I spent another 11 Euros for a high-speed USB Flash stick with 4GB and 10 Euros for a Nokia CA-42 cable that I installed to access the serial console port (which I actually did not need yet, but just in case).

Switch

In order to provide me with Ethernet ports which are part of the VPN, I use the Netgear GS108E 8-port managed Gigabit Ethernet switch. At some earlier point in my life, I swore that I will never buy a Netgear device again, but at a price tag of €37, I was willing to take a chance. Sure enough, the experience with this device is not totally pleasant. Configuration requires a Windows computer (or an obscure Linux utility that I could not get to run), the Windows configuration program uses Adobe AIR (wth?), and it never just works. But, with some patience, it does.

FreeBSD

The first step to transform the Pogoplug into a useable computer is to replace the Busybox based Linux with a real operating system. This requires replacing the boot loader with a new u-boot version which can boot from USB media, a procedure that is very well documented on the platform support page for running Arch Linux on the Pogoplug E02.

As a long-time FreeBSD user, I was very happy to discover that my favorite OS would run on the device, too. Detailed and very accurate installation instructions, together with quite some pre-built packages, are available on the excellent FreeBSD for Kirkwood page. I followed these instructions and got going very quickly. I had to build a new kernel in order to add the tun device driver and make some minor adjustments for the Pogoplug hardware, but again, the instructions on Nicole's page were accurate. I tried building a newer FreeBSD release with the same patches, but I did not succeed with that and thus sticked with FreeBSD-8.1.

Router configuration

In addition to the FreeBSD base installation, the openvpn and isc-dhcp41-server packages are required. I built them on the Pogoplug myself.

The Pogoplug only has one Ethernet port, so in order to talk to two separate Ethernet segments, I use a tagged VLAN. On the untagged VLAN, the router is connected to my "normal" home network. The VPN is in a VLAN with tag 1, and the Ethernet switch is used to make some ports into members of the VPN and some members of my home network.

The relevant configuration section from my /etc/rc.conf looks like this:

ifconfig_mge0="Home-LAN-IP/24"
static_routes="vpn_router"
route_vpn_router="VPN-GW-Public-IP Home-Router-IP"
defaultrouter="VPN-GW-VPN-IP"
cloned_interfaces="vlan0"
ifconfig_vlan0="vlan 1 vlandev mge0 Home-VPN-IP"
gateway_enable="YES"

Some explanation is in order: Home-LAN-IP is the (static) IP address of the router in my home LAN. DHCP can be used as well, but I prefer having my infrastructure devices on fixed addresses. A static route named "vpn_router" is established so that packets to the VPN router, on IP address VPN-GW-Public-IP, are always routed through my home LAN gateway with IP address Home-Router-IP. For all other packets, a default route to the VPN gateway with the address VPN-GW-VPN-IP is established. A VLAN interface named "vlan0" is created and the address Home-VPN-IP is assigned to that virtual interface. Finally, IP packet forwarding is enabled.

The OpenVPN router is started from /etc/rc.conf:

openvpn_enable="YES"
openvpn_configfile="/usr/local/etc/openvpn/client.conf"

On the VLAN segment, a DHCP server is run by the way of these lines in /etc/rc.conf:

dhcpd_enable="YES"
dhcpd_flags="-q"
dhcpd_conf="/usr/local/etc/dhcpd.conf"
dhcpd_ifaces="vlan0"
dhcpd_withumask="022"

DHCP server configuration

The DHCP server configuration for the vlan0 segment is placed in /usr/local/etc/dhcpd.conf and reproduced for completeness:

option domain-name-servers VPN-GW-VPN-IP;

default-lease-time 600;
max-lease-time 7200;

log-facility local7;

subnet Home-VPN-LAN netmask 255.255.255.0 {
  range 192.168.21.100 192.168.21.120;
  option routers VPN-GW-VPN-IP;
}

Obviously, the range needs to be adapted to the network in use.

OpenVPN configuration

OpenVPN uses SSL certificates to authenticate clients and servers. Creating and maintaining a certificate authority using the standard OpenSSL command line tools is too cumbersome for me. I am using the excellent and free XCA tool which makes managing a private certficate authority (CA) rather easy. I used XCA to create a CA, a server certificate for my central VPN router as well as a client certificate for my Pogoplug. Certificates and keys must be exported to PEM files for OpenVPN to use them.

I use a fairly standard LAN-to-LAN configuration for OpenVPN which is based on the server.conf and client.conf example configuration files which are located in /usr/local/share/examples/openvpn/sample-config-files. The client configuration used on the Pogoplug looks like this:

client
dev tun
proto udp
remote VPN-GW-Public-IP 1194
resolv-retry infinite
nobind
persist-key
persist-tun
ca ca.crt
cert client.crt
key client.key
ns-cert-type server
comp-lzo
verb 3

Again, VPN-GW-Public-IP is the public IP address of the central VPN router. The client certificate and key need to be placed in the client.crt and client.key files in /usr/local/etc/openvpn/ on the Pogoplug. The root CA certificate that you've created needs to be placed in the ca.crt file in the same directory.

On the server, the OpenVPN configuration is slightly more complex. Here is the server.conf file:

port 1194
proto udp
dev tun
ca ca.crt
cert server.crt
key server.key
dh dh1024.pem
server VPN-GW-VPN-IP 255.255.255.0
ifconfig-pool-persist ipp.txt

client-to-client

push "route 0.0.0.0 0.0.0.0"
push "route Home-VPN-LAN 255.255.255.0"

client-config-dir ccd
route Home-VPN-IP 255.255.255.0

keepalive 10 120
comp-lzo
persist-key
persist-tun
status openvpn-status.log
verb 3

Again, Home-VPN-IP is the IP address of the vlan0 interface on the Pogoplug. The Home-VPN-LAN is the network address of that interface, and the "push" directive is there to push a route to that network to other clients connecting, which may choose to ignore the default route. On the server, a ccd subdirectory needs to be created in /usr/local/etc/openvpn/ to contain client-specific configuration options. Each file needs to have the name that is put into the "Common Name" attribute of the certificate used by the client. For example, I have a file named strelitzer in that directory which is the Common Name of the certificate of my Pogoplug. That file contains this:

iroute 192.168.21.0 255.255.255.0

This directive announces my VPN LAN at home to the OpenVPN router.

Switch configuration

The GS108E switch must be configured for 802.1Q VLANs in "Advanced" mode. In that mode, it is possible to individually set up the VLAN membership for each port. The default VLAN for untagged packets can also be configured on a per-port fashion.

Here is how I configured my switch so that ports 1-4 are members of VLAN 1 (VPN) and ports 4-8 are member of VLAN 2 (Home Network):

Ports 1-3 use VLAN 1 for untagged packets. Port 4 uses VLAN 1 with tagged packets and VLAN 2 with untagged packets. Ports 5-8 use VLAN 2 with untagged packets:

Finally, I configured the PVIDs for each port like so:

Done

That is basically all that is to it. I'm sure I've left out some information that might be useful. Send me email if you have trouble with any of this. It should be possible to adapt this setup to FreeBSD running on other hardware, like the Raspberry Pi. Let me know if you get something like that to run, too!

How to convert your old-style Symbolics keyboard to USB

Peter got in touch with me because he tried to follow my instructions how to convert a Symbolics keyboard to USB with his old-style keyboard and he failed. He assumed, and that was what I would have assumed, that the color coding of the internal cabling of the old and new keyboards would match, but they don't. Here is a table that shows the pinout for both keyboard types:

New Style		Old Style		Function	Teensy Pin
Pin#	Color	Pin#	Color
1	blue	8	white	GND	GND
2	yellow		black	not	connected
3	green	2	red	5V	5V
4	red	3	green	DIN	D4
5	black	1	yellow	CLK	D5
6	white	5	blue	CLR	D6

Embracing the ARM

Last year, I worked on a project for visomat inc. which involved interfacing to a LED matrix display so that it could display some video. We had some latency problems and at one stage we decided to try out DMX instead of Ethernet as interface techniquce, hoping that we'd get better results that way. The idea was to feed the LED matrix, which consisted of 12 power supplies/controllers, with 12 DMX interfaces to make sure that data arrives at the LEDs synchronously.

DMX is an asynchronous serial protocol running at 250 kbits per second. I decided to try using an AVR microcontroller running at 16 Mhz and have it bit-bang the data out of a parallel port. For each bit, 64 machine cycles would be available which should be enough to set the port bits and also grab incoming data out of the USB interface that we wanted to use to interface to the host.

I built a prototype of the interface and we made some promising experiments with it, but in the end we found that the visual latency problems were not fixed. The problem was really in how the LED hardware worked and could not be repaired on the feeding side. The prototype went onto the shelf and we stuck with Ethernet for that project.

A few weeks ago, I discussed the project with a friend of mine and we thought that it'd be cool to turn the 16 port DMX interface into a product. We found someone who would want to use it in an OEM setting, and I made bringing the hardware to product level my weekend project.

Good bye AVR, hello ARM

The AVR based solution proved to be problematic, though. Even though the CPU has enough processing headroom, the lack of RAM requires that the data is fed into the interface "just in time". Any variance in the USB input data stream could result in visible hickups in the DMX streams. Getting it to work seemed like possible, but require too much work in the end. Thus, I decided to turn to using more capable hardware which would also give the DMX interface network connectivity and more local intelligence.

As new platform, I chose the ARM9 based Eddy-S4M board produced by the Korean manufacturer SystemBase. These boards are distributed by trenz electronic who I've found to be quick and reliable in the past.

Linux is the standard operating system on Eddy-S4M. I'm not a huge Linux fan, so I spent some time to find an alternative operating system, but neither eCos, nor FreeRTOS or RTEMS seemed to be ported to the AT91SAM9260 CPU with a free development system. As I was into application development, I decided not to port or write an operating system myself. Running on the bare hardware was not an option either as I need a working TCP stack in order to interface to the host.

SystemBase calls their Linux port "lemonix". It appears to be a relatively plain linux-2.6.20 with real-time patches, BusyBox and a bunch of C applications to control startup and configuration. The userland and kernel source code is available from SystemBase after registration, but the kernel tree that they make available is incomplete and needs to be augmented by some files that are available from a Google group so that it can be built. Getting the cross compilation environment to run on my Ubuntu 9.10 box worked flawlessly, and after removing the whole Eddy application stuff and most of the SystemBase drivers from the file tree I ended up with a relatively sane Linux that I could cross compile and install on the Eddy hardware through tftp.

Making it fast

Back to the DMX interface, I was now faced with a system that gave me about 400 machine cycles for each DMX bit sent. That should be plenty of time to get out some bits to the ports. The bit timing would be achived by a timer interrupt every 4 microseconds. Even with interrupt handling overhead, this should leave enough headroom for TCP processing.

The ARM architecture specifies two interrupts. The normal, vectored interrupt system is used by Linux and mapped to its own, portable interrupt architecture, ignoring the vectoring facilities that the hardware provides. The second, fast interrupt system (FIQ) that the ARM provides is not used by Linux, and it seemed like a good fit to my requirements. The FIQ is interesting because when the FIQ handler is entered, the CPU automatically switches six registers to a distinct bank. These six registers can then just be used without the need to save or restore them to the stack. Even though the FIQ is not used by Linux itself, ARM-Linux provides for an interface so that drivers can use it. FIQ support was missing in lemonix, but it was trivial to backport.

Writing a FIQ interrupt in ARM assembly was straightforward. The driver bottom half set up the FIQ register set and enabled the timer interrupt, the FIQ handler set the port bits and incremented the pointers accordingly.

Reducing jitter

When looking at the output ports with the logic analyzer, though, I could see variations in bit edges in the order of one microsecond, which is beyond what the DMX receivers would be able to tolerate. These variations were visible even when the FIQ handler just set the port bits without writing any real data. The source for this jitter, as it turned out, was virtual address translation. The ARM9 CPU includes a MMU and all software, including interrupt handlers, uses virtual addressing, even to access I/O ports. The virtual address maps are stored in SDRAM due to their size, and the hardware automatically traverses these maps if an address can not be found in the translation lookaside buffers in the MMU. So in the FIQ handler, when the output port address was not present in the TLB, the MMU would access the SDRAM, and SDRAM random access is rather slow.

Thus, I had to change the FIQ handler so that it never accesses the SDRAM, either directly (by reading the data buffer) or indirectly (by causing TLB misses). The AT91SAM9260 CPU has two internal SRAMs that are accessible in two machine cycles, and I use one of those as a data buffer. In order to prevent TLB misses, indivdual TLB entries can be locked down so that they're never removed by the MMU automatically. Thus, my driver locks down the I/O and the SRAM buffer addresses that the FIQ handler accesses.

Reducing jitter even more

Even with the TLBs locked down, I still saw some jitter in the leading edges of the DMX bytes. The cause for this were variations in interrupt response times, as that depends on the instruction being interrupted. The variations were below one microsecond, but that was long enough to bring the serial decoding routine in my logic analyzer out of sync. Wanting to play it safe, I decided to remove that jitter as well by synchronizing on the timer value inside of the FIQ handler: Instead of just banging out the next bit as fast as possible, the FIQ handler now waits until the free-running timer that triggered the interrupt reaches a certain value. That way, the effective FIQ response time is made mostly constant.

Wow, 2010!

In the last few years, I have been using various AVR CPUs for my embedded projects. It is a great CPU that is easy to use and fast, and the advent of LUFA and Teensy made my life a lot easier, as I was freed from USB serial dongles and driver installation. But then, being able to process serious amounts of data is nice, too, and this is were 8 bits just don't suffice. ARM based boards are cheap nowadays, and I'm looking forward to embedding JavaScript or maybe even Common Lisp in one of my future projects. When speed is needed, I can always fall back to C and assembler.

How to convert your Symbolics keyboard to USB

I spent another hour finishing up the Teensy based Symbolics keyboard converter. The software now works as well as the PS/2 version, and uses the same keyboard translation table generation tool. Converting a keyboard should now be doable for anyone who has basic soldering skills.
What you'll need:

• Teensy (The photos show a build with the obsolete Teensy 1.0)
• USB cable (B type)
• 6-pin .1'' header
• Some wire

First, you need to program the Teensy with the Firmware .hex file. Please note that this .HEX file is now for the Teensy 2.0 board, which also looks slightly different than the Teensy 1.0 board shown on the photos. Don't worry about customizing the firmware right now. If you decide that you want it to work differently than my version, you can update it later.
Get five pieces of wire, about 5 inches long. Solder them to the 6 pin header, leaving pin 2 unconnected. Connect the other ends to the Teensy.

pin #	color	teensy pad	function
1	blue	GND
2		(not connected)
3	green	5V
4	red	D4	DIN
5	black	D5	CLK
6	white	D6<	CLR

Yes, 5V and GND were swapped in my original post, sorry and thanks to Gene Diveglia for reporting
When building with a Teensy 2.0, connect the D4, D5, and D6 pins as printed on the Teensy PCB.

Open the Symbolics keyboard by removing the five screws at the bottom. Carefully remove the small PCB that sits on the larger one, unplug the spiral cable.  Using a tool like a large screwdriver, remove the strain relief by pushing it to the outside of the case. Remove the cable, take off the strain relief. Using a pliers, cut out some of the plastic so that the part can be used for the round USB cable.
Using a sharp knife, make the B type connector of the USB cable as small as possible.

Put the strain relief onto the USB cable, about 4 inches away from the scaled down B connector. Using a tool, firmly put it back into the keyboard case. Fixate the cable to the bottom shell of the case like shown. Connect the Teensy to the USB cable, plug the header into the keyboard PCB.
Put some protective plastic around the Teensy so that it does not short circuit anything on the keyboard PCB.
Finally, reassemble the keyboard. It should be easy to put the daughter PCB back onto the main PCB and fit the two shells together. You're done.
Make sure that you've read the README.txt file for the converter firmware. Note that if you want to convert your old-style keyboard, you need to know that the internal color coding of the cables is different with those keyboards. This blog post has a table with the information that you need. Have fun!

Reimplementing the Symbolics Keyboard Adapter with Teensy

In a recent post on the AVR Freaks blog, Teensy, a new AVR based development board was announced. At $19, it is rather cheap and it comes with an on-chip USB controller. The neat thing about this is that applications are not restricted to some sort of serial emulation protocol, as Arduino-like boards with a separate, FTDI chip base USB controller, are. Instead, Teensy has a full USB 2.0 controller available to the application, and it comes with libraries that makes implementing custom USB keyboard controllers that require no special drivers very easy.
I was a little unsatisfied with the state of the kbdbabel based Symbolics keyboard adapter. The adapter works so far, but there are still some caps lock related bugs and I don't know 8051 assembler. Thus, I decided to give Teensy a first spin by implementing the protocol adapter in C, utilizing the Teensy HID USB keyboard library. As I did the protocol analysis for the Symbolics keyboard years ago, implementing that part was easy enough. I did make some mistakes with respect to accessing program memory on the AVR which took me several hours to sort out, but in the end, I now have a neat little program that runs on a Teensy and that requires no external circuitry to convert a Symbolics keyboard to a USB keyboard. Just solder on a few wires, flash the Teensy, replace the RJ11 cable by an USB cable and off you go.
I'll still support the kbdbabel based Symbolics adapter, but for users who want to hook up a Symbolics keyboard to a modern, USB equipped system, I now recommend getting a Teensy. I'm willing to do the conversion for those who don't have soldering skills, but the shipping will not be cheap. If you want the Teensy firmware, see my github repository.
Next on my list: Make Teensy talk MIDI. If you've done it already, please share what you know.

ACIA fixed, S3E SK sucks

In the last two weeks, I was making good progress with my attempt to fully support the Spartan-3E starter kit by Maisforth. I had to improve my SPI controller slightly so that it works better for programming the serial Flash, worked on implementing the (ancient) standard Block I/O vocabulary so that the serial Flash can be used like a floppy disk in the old days and almost got the beautiful vibe full screen block editor to work.

One thing that was began to bother me a lot was the development cycle for Forth programs: I use Emacs to edit stuff, then copy and paste it to the real hardware. As my programs grow, this begins to take considerable time, but for some reason I could not send the data through the serial port at full speed: Maisforth reproduceably lost characters, and I had to insert a small delay after each character sent which made uploads slow. Too slow.

Thus, I went to pinpoint the reason for this character loss. At first, I thought that what I saw was a problem related to the lack of flow control. The serial port on the Spartan-3E Starter Kit is only equipped with RX and TX signals, so no hardware flow control is possible and software flow control is not implemented. After some investigation and experiments it became clear to me, though, that the problem was not flow control related. Both hardware (RTS/CTS) and software (XON/XOFF) flow control work under the assumption that data is buffered in larger chunks, but my character loss happened even when I sent short bursts at full speed to the FPGA.

The problem really was related to the lack of double buffering in the transmitter of the System09 UART. This meant that the transmitter signalled the "transmit buffer full" condition for the whole duration of the actual send operation, even though the data had already been copied from the transmit buffer to the shift register. As the serial port echo in Maisforth is generated by Forth itself, processing of every character and sending it back out through the serial port introduced a pause between every character echoed, which quickly caused problems when characters to be echoed came in at full serial port speed.

The fix for the problem was to introduce double buffering. As soon as the character to be transmitted has been copied over to the transmitter shift register, the UART module now signals the host that the transmit buffer is available for the next character to be sent. This made the problem disappear as Forth echo processing can now take place while the previous character echo is transmitted. Given the slow serial port and the high clock rate of System09, there now is plenty of time for all processing needed.

The Spartan-3E Starter Kit sucks

Well, not really. It is a nice cheap board with a good load of on-board peripherals, useful documentation and nice example designs, but it also has severe limitations: The on-board FPGA is a XC3S500E, which has 40 kByte of block RAM. In my current Maisforth setup, I use 16k for the Forth kernel ROM, 16k for RAM, and 6k for the VGA controller. This leaves only 2k free, so that makes playing with table based waveform synthesis really hard. What I hoped for was that I could put the Forth kernel and the board support Forth library into the parallel NOR flash of the S3ESK and map the Flash into the 6809 address space.

The show stopper for this plan is the fact that data bit 0 of the NOR flash is shared with the SPI bus data signal. Thus, one can either access the flash or the SPI, but not both at the same time. Seemingly, the idea is to copy the contents of the NOR flash into SDRAM and then run from there, but I'm still reluctant to try getting the SDRAM to work. The easy path is blocked, though, and maybe using SDRAM is the best option.

Rekonstrukt - A "New" Forth Machine

I have been a Fan of Forth since the 1980ies, and when I picked up my FPGA stuff a few weeks, I decided to put some more effort into getting a complete Forth based FPGA system to run before turning back to the SECD reimplementation project. This new Forth machine is called "Rekonstrukt", and I have created a Google Code project to publish the source code.

My last FPGA productivity rush ended with Maisforth running on the Spartan-3E Starter Kit. Maisforth is a ANS-like 8 bit Forth originally written by Albert Nijhof for the somewhat obscure MC6809 based computer called "Maiskastje" built by a dutch computer club a few years ago. Porting Maisforth to System09 was rather easy; all that was needed was a little tweaking of the serial I/O routines so that the System09 MC6850-lookalike serial port was properly handled.

My next goal is to support most of the Hardware that the Spartan-3E Starter Kit has to offer by Forth. This will require some VHDL hacking in order to implement the low level interfaces as well as implementing Forth libraries.

Implementing a SPI controller

I started by implementing an SPI interface. SPI is a serial bus protocol for moderately high speed connections between devices inside one system. On the Spartan-3E board, the analog capture unit, analog preamplifier, digital to analog converter, serial flash and platform flash chips are all connected to one shared SPI bus. It would be possible to operate this bus by bit-banging in software, but this would be rather slow. In hardware, it is easily possible to operate the SPI bus at a bit rate of 10 Mhz.

While other open source VHDL SPI controllers exist, none of them easily interfaced with the "proprietary" bus protocol of System09. I took this as an opportunity to freshen up my VHDL and FPGA design skills. Again, I learned that it does not make sense to synthesize to the real hardware before simulation has shown that the design basically works, but that successful simulation does not automatically mean that the design works in the real hardware. With the help of some regulars in the #fpga IRC channel on freenode.net, I got the SPI controller to run.

Implementing vectorized I/O in Maisforth

System09 comes with a VGA controller that provides for a 80x25 text console, named vdu8. vdu8 is register based, i.e. to write a character onto the screen, the host CPU needs to write the screen position where the character should go into the cursor address registers, then write the character to be shown into the data registers. In order to make vdu8 useable as I/O device for Forth, a small terminal emulator is needed that interprets standard control sequences like Linefeed, Carriage Return and Backspace properly so that it can be used to handle EMIT calls.

The VGA console should be useable as an alternative to the serial console and switching between the two should be possible at run time. The common technique to achieve that is to make the words that need to be switched between alternative implementations be vectored, or "deferred" words. What this means is that a pointer to the word that actually implements the word is stored in the word that is being called by the system, and this pointer can be modified at run time in order to switch to the desired implementation.

Normally, the Forth compiler performs a name lookup when compiling a word, not when executing it. Thus, once a word has been compiled, the addresses of the words that are being called are fixed, and the implementations of these words cannot be changed in retrospect.

For normal, RAM based operation, implementing deferred words is quite simple:

: alias ( xt -- ) create , does> @ execute ;
: noop ( -- ) ;
: defer (  -- ) ['] noop alias ;
: is ( xt  -- ) ' >body ! ;

alias is used to set up an alias for a word. defer is used to set up an alias for the do-nothing word alias. The implementation of such a word can later be changed using the is word.

This works well for RAM based Forth in which the , word can be used to compile a number into the dictionary and change that later. For a ROM based Forth like Maisforth, the default dictionary is read only and as we are interested in vectorizing words that are used by the system, the vectors need to be put somewhere else. Maisforth provides for a "user space" for this purpose. The "user space" is located in RAM at the beginning of the address space, and the IVEC word can be used to allocate a cell from that space in the cross compiler. When adding new user vectors, the USERBYTES constant needs to be increased so that the cross compiler knows the changed memory layout. I did not find out how I could get the vectors initialized automatically by the cross compiler, so I added a new 'EMIT vector initialized to 0 which would be called in the (EMIT word, and changed the COLD word to intialize the 'EMIT vector when rekonstrukt starts.

More information about vectorized functions can be found in Leo Brodie's excellent book Starting Forth in the Chapter Under the Hood.

Revisiting SECD and the power of Lisp

While visiting the ICFP Conference 2008, I was discussing my SECD microprocessor reimplementation project with my co-worker Kilian. The SECD is a classic virtual machine architecture supporting functional programming languages invented by Peter J. Landin in the early 1960ies. It is a relatively unusual architecture in that it is commonly described by transformations of the machine state represented as four registers containing cons cells. In fact, the virtual machine's memory conceptionally consists of linked cons cells, not of a vector of words that is addressed by integer addresses. Jia-Huai You of University of Alberta has a good description of how the SECD virtual machine works.

Quoting SECD: DESIGN ISSUES, here is the specification of the SECD virtual machine. There is one line for each machine instruction, describing the state of the four machine registers before and after the particular instruction has been executed:

While we were discussing my hardware project, Kilian suggested that we should implement a SECD in Common Lisp in order to bridge some time that we had until the next break. Given that Lisp supports lists nicely, we chose to use Lisp lists to represent the SECD memory. We first fooled around with imperative code that mimicked the required state transformations, but soon realised that it would be much easier to directly transform the specification for each machine instruction into executable Lisp. Following common practice, we started writing down how we wanted to type in the specification for each of the SECD instructions. As an example, the LD instruction would be defined by this:

(define-instr 1 LD
  (s e (LD (m . n) . c) d)
  `((,(locate m n e) . ,s) ,e ,c ,d))

The literal "1" is the op code, the "LD" is the symbolic name of the instruction, the first list is the state before the instruction is executed (with the four list elements representing the state of the four registers), and the rest specifying the code to execute for the instruction. The executed code again returns a four element list representing the new state of the machine registers.

We then wrote a macro to transform this specification syntax into Lisp code. Our DEFINE-INSTR macro uses the first list as an argument to DESTRUCTURING-BIND, binding all the names that we then use in the transformed state:

(defmacro define-instr (code name pre post)
  (let ((name* (intern (format nil "~A-INSTR" name))))
    `(progn
       (setf (gethash ,code *instr-hash*) ',name*)
       (defun ,name* ()
         (multiple-value-setq (s e c d)
           (destructuring-bind ,pre (list s e c d)
             (assert (= ,name ,code))
             (values-list ,post)))))))

We were quite happy with our virtual machine, and we were able to run several of the precompiled SECD "binaries" from the ancient LispKit software collection. Getting the macro right and implementing the 21 instructions took little time, and it was easy to, say, instrument the macro for tracing or augmenting it with checks to make sure that we got the original syntax right. It would certainly be possible to polish the macro more - for example, having to specify the mnemonic of the operation twice is not so pretty. We just meant to create something that we could use to explore the behavior of the SECD architecture, so we did not care polishing.

The next day, I attended an introductory Erlang workshop and as I had some prior knowledge of Erlang (Programming Erlang by Joe Armstrong is a good read), I decided to try implementing a SECD VM in Erlang instead of doing the exercises suggested by the lecturer. Erlang has built-in pattern matching, so I used a transliteration scheme of the VM specification very similar to what I used in Lisp. Also, Erlang has lists, so representing the SECD memory as Erlang lists should be a one to one match, too.

So, here is the CAR instruction implemented in Erlang:

secd(S = [ [ CAR | _ ] | _ ],
     E,
     [ ?CAR | C ],
     D) ->
    secd([ CAR | S ],
         E,
         C,
         D);

In Erlang, function dispatch is based on pattern matching, and there is total flexibility to match structures and bind variables to what has matched. For example, in the implementation of the car operation above, we bind the variable S to the previous stack contents, and at the same time bind the variable CAR to the car of the cons cell that is sitting on top of the stack.

The Erlang version of the VM grew well, and the source code looked as nice as the Lisp version. Yet, as I tried to implement the the RAP instruction, I faced a major stumbling block.

The RAP instruction is used to support recursive function calls and works by replacing a previously created dummy environment on the stack, called OMEGA, by one which contains all the functions that are visible in the recursive scope. The specification uses RPLACA to denote that replacement operation, and that is what we used in our Lisp implementation of SECD, too:

(define-instr 7 RAP
  (((c* . e*) v . s) (om . e) (rap . c) d)
  (progn
    (assert (equal om 'omega))
    `(nil ,(rplaca e* v) ,c* (,s ,e ,c . ,d))))

When trying to implement RAP in Erlang, I got stuck because there are no destructive operations on lists. Not in the standard API, and seemingly not in the system API either. So, the Erlang SECD looks nice, only it does not run. Frankly, our Lisp based SECD has bugs, too, and I am not totally sure whether the problem is not in the RAP instruction.

Curiously, getting the RAP instruction right is harder than one wants to expect: In the SECD hardware implementation that I worked on, I used the original microcode of the SECD chip developed at the University of Calgary as part of a verification project. I found two major bugs in this microcode which, ironically, was part of the file set that compromises the proof that the SECD hardware implementation was correct according to its abstract specification. One bug was the garbage collector which did not work at all, and the other was in the RAP instruction which did not work either. I have trouble not concluding something regarding academia in general from these findings.

Anyway.... this was another time when I realized how much I like Common Lisp and why it will propably not be replaced by another language anytime soon. Common Lisp is teh tool of choice for my exploratory programming, as it does not have a terrible lot of restrictions, yet supports some advanced programming abstractions. There are domains where Common Lisp does not have much to offer, though. Concurrent programming currently is the one area where the lack of support in Common Lisp hurts me most. Erlang may be my cure, and I hope to look into Lisp Flavoured Erlang in order to spare myself the arcane syntax that Erlang provides by default.

Symbolics Keyboard on PS/2 port

I have been busy with hacking Hunchentoot and flexi-streams at daytime during the last few weeks, and wrote a thread-safe version of a simple deterministic profiler for Clozure CL so that I could isolate performance problems. I'm going to blog about that stuff in a few days, but as that is daytime work, I had to find something else to relax on the weekend. Thus, I turned my attention to the kbdbabel hardware that I received last week. A few months ago, I emailed Alexander Kurz, who is the creator of the kbdbabel project, whether he could help me getting a PS/2 adapter for the Symbolics keyboard to work. At the time, he had created PS/2 adapters for various vintage keyboards and he expressed his interest. We could not make much progress, though, as he did not have a keyboard and I lacked the knowledge to adopt the 8051 based assembler code to the needs of the Symbolics protocol. I'm mostly an AVR guy when it comes to microcontrollers. Alexander was intimidated enough by the pictures of the various Symbolics keyboards that he decided to get one and make a kbdbabel for it. I was more than happy when he contacted me out of the blue a few weeks ago and told me that he now has a solution. The hardware he sent did not work right away with my Thinkpad, but that was because the Thinkpad's PS/2 port do not quite work like most other PS/2 ports do. Thus, I had to get a PS/2 to USB adapter for 10 Euros. With that, the adapter worked as advertised. I had to complete the keyboard mapping so that all keys in the default Open Genera map are mapped to a key on the Symbolics keyboard. This means that there are no mappings for several keys (the square, circle and star keys among them). Supporting those keys will require changing the Open Genera X11 keyboard mapping code, which is something I'll put onto my "weekend projects" list now. I have not yet tested the adapter with the "slim" keyboard - I only have a 3600 one right now and the two "slim" keyboards I bought from David K. Schmidt are still in Cambridge and won't be with me until next month. Contrasted to the 3600 keyboard, the "slim" keyboard is microcontroller based and will most likely require different timing than the TTL based old-style keyboard. Other than that, the keyboards should be compatible and the adapter should work with both variants. I'm going to build a few adapters for myself and some friends of mine. If you want one as well and don't like to do the soldering yourself, contact me.

Hardware woes

When I put the SECD project aside, it was because I could not get the RAM controller to run. I felt rather stupid, as the RAM is a very simple asynchronous chip that requires no special timing, yet all my attempts to reliably write the RAM from the 6809 host failed - And as long as that does not work, I can't start any program on the SECD coprocessor. Today I finally found the source of my problems. It appears that even though there is an address bit ram_a(0) in the constraints file for the Trenz retrocomputing base board, it is not connected to the RAM. Supposedly, it is not connected because the RAM works word-wise. It took writing a standalone RAM tester in VHDL and a lot of staring at the logic analyzer and Chipscope outputs to find out that I actually had an addressing problem. Also, John Kent was of great help again as he assured me that, prinicipially, the VHDL that accesses the RAM looks right. He also suggested that I might have a problem related to my constraints file, which appeared to be true. Now, finally, I can turn to actually getting the LispKit compiler to work and see the fixed hardware garbage collection in action. Stay tuned.

Back to SECD

I have finally returned to debugging the SECD implementation on the FPGA. When I stopped with this, I had problems getting the dual ported RAM controller to run. The SECD CPU is designed as a coprocessor and relies on a host CPU to set up the program in its memory and to start itself. Once the program has finished to run, the host CPU reads out the results from the SECD memory. My host CPU is a 6809, based on System09 written by John Kent. This is a historic coincidence, too, as the original SECD implementation used an 6809 as host CPU, too, at least for the testing. The 6809 software that has originally been used is not available anymore, so I needed to find a way to quickly write some diagnosis and debugging routines. System09 is designed to run the FLEX operating system and there is a BASIC interpreter for Flex available, but somehow I did not like that too much. My first attempt to create a diagnostic monitor was to write a C program and compile it with gcc6809. This worked, but I did not like the turnaround times too much. Thus, I tried to find a Forth implementation for the 6809 that I could use as a diagnostics monitor. My search led me to Maisforth, which is a Forth implementation for a custom computer called the "mais kastje" which was built and used by a group of dutch Forth enthusiasts. I changed my System09 based 6809 system so that its memory map matches that of the "mais kastje" and hacked the Forth interpreter so that it properly initializes and uses the ACIA serial port in System09. Getting Maisforth to run was not too hard, but I certainly would not have finished that without the help of the excellent Logicport logic analyzer that I have bought earlier this year. Logicport is a PC based logic analyzer that retails at $389, with 34 channels, complex triggering and 500 Mhz sample rate. The Windows software is very usable, and it comes with interpreters for a few serial protocols (I2C, SPI, RS232) which helped me to track down my ACIA initialization problem in a short timespan. I'm a very happy customer of this and can recommend Logicport to anyone who can't afford a "real" logic analyzer. Now that I have Forth running on the FPGA, I am back to debugging the memory controller problems. I use Forth as a scriptable debug monitor, so in addition to examine and change memory contents, I can define symbolic addresses, write little test programs and thus automate debugging quite a bit. With Forth and the logic analyzer, I quickly found that my problem lies in how I set up the low and high byte select bits of the RAM chip, which has a 16 bit datapath.