Creating a fast Basic interpreter

        For a retro boot-to-basic computer, I’d need an actual Basic interpreter. My first idea was to just grab an open-source implementation online somewhere and just port it over to my system, rather than reinvent the wheel myself. There had to be something suitable out there already, right?

        After a bit of searching, I decided to use Tony Wang’s MY-BASIC. This seemed idea –lightweight, packaged in a single code and header file, and easy to expand with hardware-specific commands. I copied it into my project, ported it over to deal with the idiosyncrasies of the MPLAB compiler, and added a handful of commands to make it work with the USB keyboard and text display. The trickiest part was converting it into a retro style line number dependent Basic instead of its more modern structured text style.

        This seemed to work great at first. I tried a few simple “Hello World” programs, and then coded a simple text mode Game of Life engine as a demo. This ran, but it was a lot slower than I expected, taking several seconds to calculate a single frame of the simulation. Well, that’s to be expected, I thought. Interpreted basic is slow, even on a modern 32 bit 200mhz CPU.

        The real problem came when I tried to write more complex programs. When I got to about 100 lines of code, the interpreter ran out of memory and crashed, even though most of the MCU’s 512KB of memory was set aside for it.

        It turned out that MY-BASIC is just not very memory-efficient. From looking through the code, there’s a lot of overhead to everything it does. It’s just not all that well optimized for microcontrollers with limited memory space like the one I was using.

        I looked at a few other options, but ultimately decided that I’d have to code my own Basic interpreter. One that was optimized for a lightweight memory footprint and high speed. It would turn out to be be my own unique dialog of Basic, as I looked at Commodore and Microsoft Basic for guidance but ended up reworking a few aspects of the language as I saw fit.

        The main guideline of my Basic interpreter would be to pre-calculate everything as much as possible. I was inspired by the tokenization pass that was performed by the Basic interpreter on Commodore machines, as well as the way that Python interpreters pre-process scripts into an easier to execute form. My Basic interpreter would scan every line of the program, first tokenizing them, and then processing them into a simple stack-orientated byte code, which would be what the actual execution process then ran.
The first step taken after the user types the RUN command, is actually to save the user’s entered program onto the attached SD card, clearing the memory space that would be taken up by the raw text. That file is then read back a line at a time, each line being processed by the tokenizer and parser.

        The tokenizer skims through each line, and breaks it down into a list of tokens. This is the part of the code that recognizes commands and functions, creates variable names and allocates space for variables as needed, and also recognizes strings and data and places those in specialized memory spaces.

        For example, the Basic line:

    b = 2*a*b+cb

will be broken down into the following list of tokens:

    [Index of variable b] [Assignment] [Integer 2] [Multiply operator] [Index of variable a] [Multiply operator] [Index of variable b] [Addition operator] [Index of variable cb]

        Each token is a 32 bit value, broken up into individual fields that can indicate token type (such as operator, variable, syntax, etc) and type within that token (such as type of operator, index of the variable, etc.). There is some complex logic in the tokenizer to distinguish different uses of syntax characters like equals signs and parentheses. The tokenizer will also catch many basic syntax errors and halt the process with an error message.

        After tokenizing, the list of tokens is handed to the parser. This code takes the list of tokens and converts it into a list of commands, which will be run by a virtual machine during runtime. This command language was chosen to be run as fast as I can get it to run, and also to take up minimal space in memory. Each command in the command list is a 32 bit value, which can have additional data for immediate parameters stored as part of the 32 bit command. Commands can also be followed by physical addresses in memory, as during the parsing process the addresses of variables, procedures, and operators are looked up and stored directly in the command list.

        Our previous Basic line, after going through the tokenizer and parser, will result in the following command list:

[Push variable contents to stack] [Address of variable a]
[Operation with immediate value 2] [Address of multiplication operator]
[Push variable contents to stack] [Address of variable b]
[Operation on top two values of stack] [Address of multiplication operator]
[Push variable contents to stack] [Address of variable ab]
[Operation on top two values of stack] [Address of addition operator]
[Pop top of stack to variable] [Address of variable b]

        This list of 14 instructions takes up 56 bytes. This is admittedly more than the 12 bytes of the raw Basic text, but it is much faster to execute than parsing the Basic itself every time that line needs to be run.
As an additional optimization, there is a final sweep through the code that identifies GOTO and GOSUB statements and replaces the associated line number with the address of that line in memory. This eliminated the need to search through the program list for the actual address every time a GOTO or GOSUB is encountered, although there still needs to be that capability for jumping to a line number that’s calculated at runtime.

        The resulting Basic interpreter is fast, running my Game of Life demo about 30 times faster than Tony Wang’s MY-BASIC. And it’s much more memory-efficient, I’ve written programs over 600 lines long without getting close to the memory limitations. I’d call it a success, for a part of the project that I never intended to develop from the start it’s working really well.

        The source code for the project can be found here.

Connecting a CPU: A change of direction

         My original plan for this project was to pair it with a 6502 CPU system and build a simple 8 bit homebrew computer. But as I approached the point where I’d need an external system to run code on, I had several realizations.

        The first problem was that I didn’t have a 6502 computer system to connect it to. And while it wouldn’t be that hard to build one, it was a project that I wasn’t really sure I wanted to undertake.

        Because the second problem is that I have zero experience with 6502 assembly programming. My early programming experience was all on Z80 and 68000 machines, and even there I was using interpreted and compiled languages and not touching the assembly myself. I didn’t start doing low-level assembly programming until much later.

        And that leads to the third problem: programming 6502 machines isn’t nostalgic for me. A homebrew 6502 system isn’t my dream retro machine. I never really did any programming on them. The vast majority of my actual programming experience has been with Microchip PIC series microcontrollers, starting with the simple 8 bit ones back in the 90s, and leading up to the PIC32 devices I work with today. 

        And as it turned out, I had a PIC32MZ development kit board sitting around unused, left over from a previous project, and the development and debugging environment already set up and ready to use.
It is true that the resulting system isn’t going to be all that retro, with a modern (200mhz, 32 bit) CPU, and a modern FPGA. But it would be a lot easier for me to develop, and it would at least look and act like a retro boot-to-basic machine.

        I created code in the FPGA to make it act like a 64K memory, with internal division between control registers, tile and text maps, sprite data, graphical data, etc. In the Microchip code project I configured a chunk of the PIC32’s memory space to connect to the FPGA through the MCU’s external bus interface. Then I just needed to connect 16 address, 8 data, and various control signals between the two of them.
With some fairly simple code I was able to write to the FPGA, clear the memory space, and make a simple hello world program to draw text to the screen.

Connections between the MCU and the FPGA 

 

 

Wired up with a ribbon cable, and a simple 3D printed frame to hold everything stable 

        The next step was to connect a keyboard, using the USB Host capability of the PIC32 MCU, and create a simple text interface. This wasn’t terribly difficult to do, although I had a little difficulty getting key repeat timing just right. I also added a SD card interface, and wrote a rudimentary DOS for saving and loading files.

        At this point I had a simple “TV Typewriter” type interface. But to make it really useful, I would need to implement a scripting language – preferably Basic, since that matches the type of computer I was trying to imitate.

Designing the graphics engines: Text, Tile, and Sprite graphics.

         

        At this point, I had a simple FPGA program to output a HDMI video signal consisting of a single static image. This was a start, but to be useful it needed a lot more functionality.

        I would eventually need to code a CPU interface to allow the contents of the frame memory to be written externally, but first, I wanted to code the actual GPU function. My goal was not to have a simple bitmap display, as that would require the external CPU to do a lot of work to draw simple text and tile graphics. Instead, I wanted to build graphics engines to make the CPU’s job easier. The system I was imagining needed an easy-to-use text mode, as well as multiple tile and sprite layers for implementing simple games. I quickly came up with a design that would have four independent graphics engines: text, tile A, tile B, and sprite, running simultaneously to generate different layers of the final screen image.

        The 75K frame buffer took up far too much of the FPGA’s limited memory, so it would have to go. Instead, the individual engines would each have a dedicated line buffer, and would generate the image to the screen line-by-line as needed, racing the beam as it moved down the screen. I actually created two line buffers for each graphics engine, with one of them being written to while the other one was being read out to generate the video output. After each line the buffers would be swapped, so the most recently generated one would be output while a new line was being generated.

        The block RAMs on the T20F256C3 are each 512 x 10 bits, which fit my needs for this well enough. I was only using 240 locations out of each block, but the 10 bit width came in handy. Of those I was using 8 bits for the color value, while the remaining 2 bits were used to encode a layer priority value. When reading data from the four line buffers, the priority values from each would be compared, and the color value with the highest priority would be used as the color value sent to the palette memory. With this each sprite in the sprite engine could have a different layer priority, allowing them to appear in front of or behind the tile layers as desired. Likewise different parts of the tiles generated by each tile engine could have different layer priorities relative to the sprites and each other.

Simplified block diagram of the graphics pipeline.

        The text engine stores a 64x32 page of text in memory, although only 40x30 characters are visible on the screen at once. While it would have been nice to be able to implement 80 column text mode, I haven’t come up with a clean way to fit it into this existing architecture yet. Each character is stored as 4 bytes in memory: one byte for letter ID, one byte for foreground color, one byte for background color, and one ‘attribute’ byte which encodes various bits for cursors, underline, blinking, and per-character layer priority. This came out to 8K for the text map, plus 2k for the 256 character font, which might seem a lot for a simple text display, but I wanted it to have a lot of built-in functionality. I also much later added a feature to allow this space to be repurposed for other uses by disabling the text engine.

         A single byte in a general-purpose control register space allows the text display to be shifted up and down on a per-line basis, allowing smooth scrolling if the external CPU wants to implement that.

        The two tile engines are identical, other than pointing to different line buffers and reading from different memory banks in memory. Similar to the text engine, each 8x8 tile on the screen is stored as 4 bytes in memory. One byte selects the tile image ID, one selects the transparency color (pixels on the tile matching this color will have their layer priority set to zero, allowing other layers to show through), and then there are two bytes encoding various special features. The tile map encodes 64x32 tiles, requiring a total of 8K of memory, and another 8K of memory is set aside for the tile graphics.

        There’s a lot of fancy functionality built into the tile engines. Each tile’s image can be encoded in 256 color, or 16 color with a per-tile palette selection. Tiles can be individually flipped horizontally, vertically, rotated, or any combination of those. There is also an automatic animation function where a tile’s image can be cycled at a per-tile adjustable speed. Each tile can have an individually adjustable layer priority, so you can have effects where some tiles are in front of the other layers and some are behind them. There’s also a collision bitmask for detecting sprite-to-tile collisions, although that feature hasn’t been well tested at this point.

        There are also scrolling registers in the general control register space which allow each tile layer to be scrolled in X and Y on a per-pixel level. It’s also possible to generate parallax scrolling effects by having the external CPU change the X scroll register between scanlines.

        Finally, there’s the sprite engine. This handles up to 128 sprites on the screen at once, and is one of the more complex bits of coding in the project. Each sprite requires 8 bytes of RAM, requiring 1K of RAM for the 128 sprites. Initially I set aside 16K of RAM for the sprite graphics, which turned out to be a fairly severe limitation. I later added provisions to increase the sprite graphics memory up to 64K, by allowing the sprite engine to use other areas of memory when the tile or text engines were disabled.

        Sprites have 10 bits of X position and 9 bits of Y position. These are signed integers, which allows a sprite to be partially off the top or left side of the screen with a negative location. Sprites must be square, but can be 8, 16, 32, or 64 pixels wide. Like tiles, sprite images can be flipped horizontally, vertically, and/or rotated, and their images can be stored as 16 or 256 colors. There is also a feature to automatically animate sprites, rotating their image through several with adjustable timing, and a sprite-to-sprite and sprite-to-tile collision detection system.

        The code of the sprite engine is more complicated than the other engines. First there is a scan process that iterates through the data for the 128 sprites, reading the next sprite's data from the sprite data registers and passing it to the sprite math block.

       The sprite math block determines if this sprite is potentially present on the current horizontal line being drawn to the line buffer. If the sprite is to potentially be drawn, the math block generates a command to be sent to the blitter. This command includes source address in memory, destination address on the line, and information about how much and in what direction to increment the source data pointer between each pixel - required for sprites which might be flipped or rotated. The math block also takes into account the animation cycle, moving the data pointer between animation frames as needed. This information is all packed into a 64 bit command which is sent to a command FIFO.

        The command FIFO holds up to 16 blit commands. If the FIFO happens to be full - possible if multiple large sprites are handled at once - the scan state engine gets paused until there is a free spot in the FIFO. When there is a command ready in the FIFO, the blitter engine takes the command and copies the indicated pixels from the sprite bitmap memory to the line buffer.

        There is no hard-coded limit to the number of sprites per line. In theory, if you draw too many large sprites to the same line at once, the blitter will at some point run out of time and be unable to finish drawing all of them before the line buffers get swapped and sent to the screen. I’m not entirely sure where that point is yet, I need to do more testing.

        I figured that these four engines should be enough for a machine that would be more than comparable to any early 80’s 8 bit boot-to-basic or home game machine. The next step would be to connect an external CPU and actually write code to run it.

The Game Engine: A homebrew boot-to-basic retrocomputer built with modern hardware.

 

 

Current appearance of the GameEngine as of this year. 

        The GameEngine is a project I've been working on intermittently for the last five or so years. It's an excuse to learn FPGA programming, a fun exercise in making my own fast Basic interpreter, and a demonstration of how you can build a flexible GPU system with relatively low-end components. Functionally, it's a modern retrocomputer, a machine inspired by the 8-bit computers that I grew up with in the 80s, but built with modern components. The current version uses USB peripherals, stores files on a SD card, and outputs HDMI video, but acts like a text interface boot-to-BASIC computer similar to classic machines from Commodore, Texas Instruments, or Apple.

        This project’s inspiration came from multiple sources. It was partly inspired by the Commander X16 project, which got me thinking about how I would build the kind of classic computer I would have liked to have while growing up. It was also inspired by looking at many other homebrew 8-bit computers, and noticing that they were at best producing VGA video output. HDMI output was apparently too difficult to do in a homebrew system, at least while still using discrete logic. This started me wondering what the minimal hardware system that could generate HDMI video would be. I figured that a FPGA would be required, but that was fine with me as I was looking to get more FPGA programming experience anyway.  

        My initial idea was to develop a custom computer system, a board containing a 6502 CPU, RAM and ROM, and a FPGA on a dedicated daughterboard plugged into a standard DIP socket. The FPGA would generate video and sound output, and would also take over much of the glue logic functions, generating clock and reset, address decoding for the RAM and ROM, possibly keyboard handling and maybe even smart interrupt and DMA functions. But first I needed to demonstrate the basic video function with a devkit board.

        The really low-end FPGAs from Lattice and Microchip were too small to do what I wanted, while the powerful high-end ones from companies like AMD were expensive and at the time had very long lead times. I decided on the mid-range FPGAs from Efinix, as they were relatively inexpensive yet had enough LUTs and on-chip RAM to do what I needed. For this project I chose a development board based around the Efinix T20F256C3.

        The T20F256C3 does not have a built-in HDMI driver, but it does have multiple LVDS output channels.  LVDS signals don’t quite match the required voltage levels of the HDMI data channels, but a simple RC network was enough to get them close enough to work. I built up an adaptor board to plug into the devkit and output close-enough HDMI video signals.

 

 

 A simple LVDS to HDMI adapter circuit.

 

 

 The circuit built up on breadboard, plugged into the FPGA devboard.

        The  ideal thing to do would be to use an actual HDMI signal driver chip to get the proper voltage levels and drive strengths, but I didn't want to bother with having to set up an entire breakout board for that. The simple RC network seems to work well enough, even if the signal levels here only marginally meet the HDMI signal specifications.

        My first goal was to see if I could simply display a static color bar image.  HDMI digital video output consists of four differential channels: red, green, blue, and clock. The color channels are transmitted as ten bits per pixel data signals. The fourth channel is simply a clock signal which cycles once per pixel. Horizontal and vertical sync are added to the blue channel, and additionally audio data can be included during the sync period on the red and green channels.

 

 

        I was aiming for a 640x480 pixel image, the baseline screen image that all HDMI monitors should accept. With horizontal and vertical sync and blanking periods, each screen consists of 800x525 pixels, or 420,000 pixel clocks per frame. A 60hz update rate would require a 25.2mhz pixel clock. Unfortunately the FPGA I was using couldn’t easily generate this exact clock rate from the clock signal on the devkit, but it could easily make 25mhz, which would give me a frame rate of 59.524hz. This seems to be close enough for the monitor to recognize.

        The data on the red, green, and blue channels is TMDS encoded, which converts the data from 8 bits of raw color information to a 10 bit signal encoded to balance voltage levels and minimize transitions. The blue channel also has some additional encoding for indicating horizontal and vertical sync signals. For this part I simply grabbed some open source TMDS encoder code and pasted it into the project, rather than bothering to write my own from scratch.  Thanks to Scott Larson for creating and publishing that code for me to use.

        I wrote up a simple timing block to count through the horizontal and vertical pixels, and generate the blanking and sync signals as needed. A simple case statement based on the horizontal position was used to generate color signals to the encoders.

 

Color bars. I had the red and blue channels swapped here, but that was an easy fix.

 

        At this point, I had a valid video output from the FPGA, with surprisingly little code. Next step was to see if I could make it display a static bitmap image.

        The video output at this point was a 640x480 pixel, 24 bit color image. Storing that image at full resolution and color depth would require over 900KB of RAM. The Efinix T20F256C3 FPGA only has about 100KB of block memory, so I would have to make some sacrifices to  get a raw bitmap image to fit.
First thing I did was halve the resolution. Doubling up each pixel horizontally and vertically meant I only had to store 320x240 pixels in RAM. This was about the graphics resolution I was aiming for with the final design anyway.

        The second step was to switch to 8 bit indexed color. I created a palette lookup table, three 256x8 bit memory banks holding the red, green, and blue values of each indexed color. Instead of holding raw color values, each byte in the bitmap image would have the index of a color to use from the palette RAMs.  

 

256 color demonstration, using the standard ANSI color table.

 

        I created a quick Python script to take a raw image, find the closest color in the palette, and then output a raw memory file. I even added a feature to dither between two colors when the raw color in the image was roughly between two choices.

        With the reduced resolution and indexed color, the memory required for the image was reduced to only 75K, which would fit in the block ram of the FPGA. I created a single block RAM to hold the image, with its contents initialized from the memory file created previously, and replaced my simple color bar generator with a lookup function to fetch the required pixel from the block RAM. This worked, and I now had a simple FPGA code to display a static image over HDMI.

 

 256 color parrots, in 320x240 resolution.

 

        That's video output. The next step will be designing the interfaces that would let an external CPU do something useful with this.

 

        The latest FPGA code for this project can be found in my github repository at https://github.com/ellindsey/graphics_engine/.