Sunday, June 17, 2012

Stone Soup

Exotic and Rare, the C Compiler

Once upon a time, a C compiler was a rare and exotic thing. They weren't commonly available outside of research labs or well funded corporations, and if you were working on a newly minted microprocessor-based machine, you were out of luck. In those days you were lucky to have an assembler - sometimes your day started by keying your program in address by address, byte by byte, or by laying some rudimentary tools into RAM from a tape and pushing the Go button. Once upon a time, lifting a machine by its bootstraps was an important start of the development process.


The bootstrapping process was well known to old school game coders. We knew all the Apple ][ system vectors and how to lay in boot loaders to hijack the startup process straight into a game. The boot ROM in the disk controller card loaded the first 256 bytes of code and jumped into it; increasingly complicated loaders were overlaid until finally your game was in memory, and you were off. The Apple ][ was a great to-the-metal playground for learning to code. Its primal tool was a marvelous mini-assembler - no symbols or branch calculation helpers, just a simple translator from opcode mnemonics to bytes, and its greatest treasure was the “L” command to list a few more lines of code. It was enough to put together a lot of fun, and reveal the innermost secrets of programming. Steve Wozniak wrote the mini-assembler, he was a teacher from the start, and the Apple ][ monitor program was the best school.

Early Console Hackery

But what about systems not quite so hacker friendly? One of my favorite bootstraps was the one we did at Interphase Technologies on the Colecovision. The Colecovision was an archetypical closed gaming console, popular long before the days of SDKs. When we started we knew nothing about the machine. Some components were sealed under epoxy blobs, some parts had numbers removed. Our first order of business was some radical deconstruction. This involved acids, sledgehammers, microscopes, and drops from high altitudes. It also involved diagramming out circuit diagrams and other down to earth engineering. We worked out the general capabilities of the machine; most importantly we found that it was sporting a Z80. Going back to an unpulverized unit, we desoldered the CPU and wired in a breakout header and carefully reattached the CPU above it. We attached a signal analyzer to the breakout header, and built a latch on the address lines so that we could halt the CPU when certain addresses were requested from the ROM. We wired LEDs to some outputs. Now we had a debugger! We dumped the system ROM worked out what routines and entry points we could use from it, and it was all straight forward from there. We hacked a TRS-80 assembler to target the features of the Colecovision, got some EPROM burners and UV lights to erase the ROMs for the next debugging sessions, and we had a development system. A couple of weeks later, an early success - I was able to display an X in the middle of the screen! It was only a small step from there to a fully functioning game. You can grab my first console ROM, Aquattack, from this link: (currently offline as site is reconstructed). It works in any Colecovision emulator. My proudest moment was when the Coleco engineers came by at CES because they had heard I had managed smooth scrolling. The advantage of not having any documentation or guidance was that we didn't know what the machine couldn't do! From the screenshot, you might notice that Aquattack scrolls in the opposite direction of every side scroller to follow. Since Zaxxon was the only isometric side scroller before it, there wasn't much precedent for which way things could go. I picked the direction where I could rotate the bits in a byte with the fewest cycles.

Coding in Silos

In those days we coded in silos. A little light came in from the top, but you might go weeks or months without actually talking with someone who was doing the same things as you. Occasionally you'd hear rumors of something called Siggraph or what have you, but it could take a really long time to track down those sorts of resources, and in the mean time you did the next best thing which was to work it out for yourself... At that time the C compiler was still a rare and exotic thing, but at last the great day arrived - I managed to dredge up the source code for a C compiler off usenet. It was a stunning surprise to discover that the C compiler was written in... C. The source code was not the most readable thing in the world, but I was determined to work out how it could be that C might be written in C. I turned to Forth, a language I was already familiar with from my work in robotics. Forth is the classic bootstrappable language.

Bootstrapping a Compiler

At its simplest level, Forth doesn't do much. Here's my implementation of the innermost bit, written in 68000 code (it was certainly a luxury to not have to build the assembler first!):

doNext MACRO movea.l (a5)+,a3 ; fetch cfa pointed to by ip, and inc ip 
             adda.l a4,a3     ; convert the base address to absolute 
             jmp (a3)         ; go execute the next word 
Every Forth command ends with the doNext macro which picks up the next opcode to execute, adjusts its address via the base pointer in a4, and jumps through it. To start Forth, a few registers are set up in assembly code to point to the first executable bit of Forth code, and the doNext macro is invoked. That drops into the cold start, written as a series of hard coded Forth word offsets, and so it begins.

cold bra doColon 
dc.l coldStuff    ; do all the neat power up stuff 
dc.l clrPage      ; clear screen 
dc.l adotqa       ; write the following message
dc.b 53 
dc.b 'FUSION FORTH 1.00',13,10 
dc.b 'by Nick Porcino and Don Palmer' 
dc.b 27,'e'       ; make cursor visible 
dc.b 27,'v'       ; wrap around 
dc.l cr           ; do a carriage return 
dc.l shell        ; start the command line stuff 
dc.l exit         ; end of definition
Once this much code was written in assembly, I wrote a few of the most basic bits such as “compile a Forth word definition”, “save to disk”, and “parse a number”. Little by little enough functionality came on line that more and more sophisticated parts of the language could be written directly in Forth, and the Forth implementation began to compile itself as part of the bootstrap sequence. The file below is part of the start up; it invokes bits of Forth code to keep building up more of the compiler and base libraries. The last file that is loaded is the saving code that allows new Forth programs to be saved out to disk.

( Fusion FORTH compilation link file ) 
CD . CD 
If you are interested in digging through the code, a version of Fusion Forth for the Atari ST is available at (currently offline as this site is reconstructed). Ultimately, I enlisted a couple of friends to help, and we built the language out completely, including a GUI, a text editor, a graphical IDE, some games and utilities, and more, and all of it bootstrapped up from only a few lines of initial assembly code. It's a bit like the old parable of Stone Soup. I never did get around to compiling that C compiler though!

Stone Soup

The process of bootstrapping goes on around us all the time, in the form of new platforms and protocols. When I think back on the humble beginnings of the computer revolution, and how recently it was a major effort just to display an X on the screen, I am simply awed at how complexity has enfolded upon complexity to turn the microprocessor into an engine of societal change.
  • A kindly, old stranger was walking through the land when he came upon a village. As he entered, the villagers moved towards their homes locking doors and windows. The stranger smiled and asked, "Why are you all so frightened? I am a simple traveler, looking for a soft place to stay for the night and a warm place for a meal."

    "There's not a bite to eat in the whole province," he was told. "We are weak and our children are starving. Better keep moving on."

    "Oh, I have everything I need," he said. "In fact, I was thinking of making some stone soup to share with all of you." He pulled an iron cauldron from his cloak, filled it with water, and began to build a fire under it. Then, with great ceremony, he drew an ordinary-looking stone from a silken bag and dropped it into the water. By now, hearing the rumor of food, most of the villagers had come out of their homes or watched from their windows. As the stranger sniffed the broth and licked his lips in anticipation, hunger began to overcome their fear.

    "Ahh," the stranger said to himself rather loudly, "I do like a tasty stone soup. Of course, stone soup with cabbage -- that's hard to beat." Soon a villager approached hesitantly, holding a small cabbage he'd retrieved from its hiding place, and added it to the pot.

    "Wonderful!!" cried the stranger. "You know, I once had stone soup with cabbage and a bit of salt beef as well, and it was fit for a king." The village butcher managed to find some salt beef . . . and so it went, through potatoes, onions, carrots, mushrooms, and so on, until there was indeed a delicious meal for everyone in the village to share. The villager elder offered the stranger a great deal of money for the stone, but he refused to sell it and traveled on the next day. As he left, the stranger came upon a group of village children standing near the road. He gave the silken bag containing the stone to the youngest child, whispering to the group that it was not the stone, but the villagers that had performed the magic.

1 comment: