This is the legendary 1977 KIM-1 computer, the oldest home computer on eBay.
This particular example is a rare Revision A and is housed in a complete double backplane
of expansion boards ranging from text and graphics to disk controllers and eprom burners.
The only thing it's lacking is a C compiler, and I'm going to solve that today.
For the first time in 45 years, the KIM-1 is going to drink code from the firehose of
the CC65 compiler until prime numbers come out its nose.
[Intro] Hey, I'm Dave, welcome to my shop!
I'm Dave Plummer, a retired operating systems engineer from Microsoft going back to the
MS-DOS and Windows 95 days, and today we're going to make a C compiler work for the KIM-1.
We're going to port CC65 to the KIM1 by providing all the code and plumbing needed.
I'm going to write a rudimentary HAL, or Hardware Abstraction Layer, for the KIM1 itself.
Then we'll code up a wickedly fast prime sieve and test it live on my real KIM1 hardware.
I'm not one of those static collectors, in that I don't want to just buy old computer
equipment to live on a shelf in some static display looking cool.
It's critical to me that everything works, and perhaps even more important, I want the
machines I keep to be able to do something interesting.
Even my old VT220 terminal is used to keep tabs on the build machine that does continual
content integration on the language racing Primes project.
My PET 2001 serves as an accurate 24-hour clock.
My TRS-80 Model 1 has been upgraded with Ethernet and serves files on the Internet.
As a more complex example, my friend Rutger and I created this spectrum analyzer and audio
visualizer for the Commodore 64, writing the whole thing in hand-coded assembly language
and then building it with the CL65 assembler.
The CL65 assembler, however, is just one component in the set of tools that comes with the CC65
compiler, which is a reasonably complete open source C compiler for the 6502 processor.
I became stoked about the idea of being able to use a C compiler to put some modern code
on the old KIM-1, but unfortunately CC65 does not support the KIM-1.
Now certainly it could compile some library code into pure 6502 instructions, but it would
have no way to interact with the world or even the machine around it.
How would it even know where RAM was located on the machine?
Consider the simple case of printf("Hello World").
In order for that statement to operate, it needs to handle text output.
Behind the scenes, printf is going to use the file stream for stdout and push the text
string out to it, but absent a library implementation of stdout, the compiler has no idea how the
underlying system does its actual I/O. After all, a KIM-1 that does its I/O over a serial
TTY is very different from a Commodore 64 that displays text on a CRT via a two-dimensional
screen editor.
And how the C64 handles text is going to be quite different from how an Atari would do
it.
Those differences are all accounted for in the standard library, and the CC65 compiler
uses the notion of a target.
A target is a supported platform variant, and CC65 supports dozens of targets, ranging
from the familiar Vic20 and Atari and Apple II to the more obscure PCEngine and Lynx.
And yet, there's no KIM-1 support.
Put simply, no one has wanted it enough to sit down and write it - until today, that
is.
I really want to make this work, so we're going to have to dig into CC65 to understand
how it works and what I need to do to add an entirely new platform, or target, to the
compiler.
I'll update the compiler itself with the new KIM-1 target code and then write the assembly
code needed for the standard library.
Then I'll write a prime number sieve in C to test it all out and demo it live for you.
Fortunately for me, someone named Wayne Parham had already implemented at least one single-board
computer of the same general era: the SYM-1 trainer.
The SYM-1 is like a super KIM-1, adding things like more RAM, EPROM sockets, an RS-232 port,
and so on.
None of that SYM-1 stuff would work directly, but it would still be highly valuable for
showing me precisely what and where I had to supply code and configuration for the KIM-1.
By standing on the shoulders of the giant that wrote the SYM-1 support we should be
able to see far enough to implement our KIM-1 support.
The first thing I need to do, then, is to fork the CC65 project in Github.
That will give me a personal copy of the source code that is still linked to the original,
and that will allow me to request that my changes be propagated back into the original
project at some point in the future.
Once I have a fork of the code, we can clone it into a local folder.
My setup is a little unconventional.
I'm running Windows 11, but I'll be using Ubuntu Linux under WSL2 as my command line
environment, except for building CC65 itself, where I'll be doing that inside the MinGW
environment, since I want to build compiler binaries targeted to Windows.
I'll be editing the code in Visual Studio code as I go.
Perhaps the most important piece of the puzzle that we'll need to create today in order to
add KIM-1 support to the compiler is to create a configuration file that describes the KIM-1
hardware.
By that I mean it lists all the details of the machine - what parts of zero page are
available, where the stack is, where RAM starts, where ROM starts, where code should live,
where the heap can go, and so on.
It's everything that the compiler needs to know about the system memory map.
Rather than making you watch me type and debug, I'll get each step along the way working and
then review that file with you.
For example, here's the configuration file I've just created.
This config file format is proprietary and looks a little alien, but after this it's
all regular code and headers, so hang in there.
One highly important declaration is the default start address - where our apps should be loaded
into memory.
Remember, because 6502 code uses all kinds of absolute addressing, it's not relocatable
in any way.
A program is compiled and assembled to live at a particular address and that's the only
address it will work at.
For a non-expanded KIM-1, we can see from the memory map in the system manual that our
available memory starts at hex 200, right after the stack and zero page, and that's
where we should base and load our apps.
For an expanded KIM-1 its more complicated.
I'll need to create a separate configuration for the expanded 60K edition, but the system
RIOT chips are mapped into memory around 1700 hex, and then RAM picks up again at 2000.
We would need to define those sections separately, and perhaps we could put the code at 200 and
the heap at 2000.
Or we could base everything at 2000 and make use of the low memory in some other way.
Regardless, we need a configuration file for each and every different KIM-1 configuration.
I'll only be supporting two: the unexpanded 1K version and the full-ride 60K version.
In the MEMORY section I've put the definitions for the zero page, the stack, the main RAM,
and the ROM that my Corsham I/O board has.
The SEGMENTS section defines important things like where in memory the code should be loaded.
Code goes into a read-only section of memory, even though there's nothing to actually STOP
you from writing to it, unless it was burned to ROM.
DATA goes into a read-write area, and zero-page is special.
Since the KIM-1 itself uses some of the zero page we put a ceiling on the available addresses
of hex EE.
The means the compiler will only use addresses 0 through ED.
Now that the compiler has some notion of how to generate code for the KIM, we need to implement
the very basic core of the C runtime library.
That comes down to doing two things: at a minimum, implementing the basic I/O functions
and then adding any ROM functions from the KIM-1 itself that we wish to expose.
The only ones I will worry about today are to load and save from tape.
I'll implement those as sort of a demo of how to expose machine-specific features.
The first step to exposing machine functionality is to create a header file for assembly language
that defines your symbols.
I've created this file which details basically all I currently know about the KIM-1 ROM routines
- the routine to output a single character to the TTY, to read one, to load and save
from tape, and where the address and ID information for the tape image live in memory.
One language level higher up, we next define a header file called kim1.h, and this can
be included by any C programs that wish to access KIM-1 specific behaviors.
As noted, the only two custom examples that we'll be adding are the load and save routines
- loadt and dumpt.
LoadT takes a single byte as the tape ID, and dumpt takes the ID as well as the start
and end addresses to be written out.
Now that we've defined an ultra-simple interface with the KIM-1 we need to actually write the
assembly code for two standard routines - read and write - and our two custom routines, loadt
and dumpt.
This code will go into a new kim1 subfolder in the existing libsrc folder.
Each target, like the PET and the Atari and now the KIM-1, has its own subfolder.
The CRT0.s file implements the program startup logic.
This is the most complicated part of the setup, and I basically just did what Wayne did in
his SYM-1 example.
When a program starts your _init function is called, which in our case sets the program
stack pointer, zeros out bss memory for you, copies data into place and then initializes
any library code that needs it.
It then jumps to your main function, which you will supply in your C program.
The bulk of the work here in the runtime library was spent in putting together the required
read and write functions.
They are the functions that do the actual TTY input and output.
When you call a function like printf, after it's completed all of its parsing and formatting
magic it's ultimately going to send its output to the _write function, which is prototyped
to take a C file descriptor, a text buffer, and a count of characters.
Your job as the library author is to take those parameters and output that buffer to
your machine hardware.
My write function takes that buffer and count and walks through the buffer outputting characters
while decrementing the count until the count hits zero, at which point it branches to the
done label and returns to the caller.
It does the actual work of sending a single character to the TTY by calling the OUTCHR
function.
We defined that a moment ago in kim1.inc as a ROM routine at $1EA0.
I actually deduced these function entry points by looking at Microsoft's BASIC to see what
it did.
Our read function is the essentially a mirror of our write function - It calls the machine
language monitor's routine to input a single character, INTCHR then stores that character
in the buffer.
It decrements the count and continues until the buffer is full or the number of characters
is satisfied.
With those two functions the compiler now has everything it needs to implement functions
like printf, gets, and all of the other console IO functions.
In the file named tapeio.c I've placed the code for loading and saving via tape.
The loadt function just sets the tape ID and then calls the ROM routine in the Kim Monitor
for loading from tape.
The dumpt routine is marginally more complicated in that it has to set up the start and end
addresses in memory before then calling the monitor rom's DUMPT save routine.
You'll notice a few shortcuts here for returning either a zero or one.
Because the return0 and return1 functions end with an return from subroutine instruction,
if we jump to them directly the RTS at their end will actually return from our subroutine.
It saves a couple of bytes each time you need to return a result.
The rest of the changes to the compiler are just to add the target.
Essentially, I added a new symbol called Target KIM1 to the enumeration of available targets,
and then everywhere the target was evaluated in the code, I added a new case to handle
the KIM1 target.
But what of the rest of the C runtime library?
What if I call clock(), for example, where is it going to get a hardware timer without
any knowledge of how the system keeps time?
Well, if you call the C function clock(), it will in turn call the assembly language
symbol underscore-clock.
You then must provide that function in the libsrc folder or you'll get a linker error
for an unresolved external.
And in this way, you can start small and build on it as you go.
Take FILE IO for example.
Although the KIM1 has no provision for file IO natively, my system is equipped with a
disc controller and a copy of CODOS extensions for Microsoft BASIC.
Since it in turn exposes a mechanism for reading and writing to disk files, your next step
would be to expose that functionality through your read and write calls by actually looking
at and making use of the file descriptor, which we entirely ignored in our implementation.
For now, I've added two examples to the samples folder.
The first is a simple hello world application to confirm that console input and output are
both working as expected.
It prints out Hello World and a welcome string and then it reads a line of input from the
console.
This should exercise both our read and write functions.
It also displays back the text we entered so that I can test backspace and make it works
during text entry and so on.
The next sample is more substantial, in that it uses heap memory to calculate the prime
numbers up to some set limit.
The highest we can do with available ram is about 750,000.
How, on an 8 bit machine?
Well, I store our sieve in a packed bitarray in memory and I ignore even numbers, so one
byte represents 16 numbers.
On the Corsham expansion board we have 60K of RAM which equates to something on the order
of 48000 bytes of free memory.
At 16 numbers per byte, that's 768,000.
Our sieve needs to be able to get, set, and clear bits in the bit array so that it can
keep track of which factors are potential primes.
To that end I added three macros, where each takes the address of the bit array and the
bit index into the array.
It then calculated the byte offset as well as the mask for the current bit within that
byte.
It then uses the array and mask to fetch or set the value of an individual bit in the
array without disturbing any of its neighbors.
This saves us memory by factor of 16 over a na ve array of bools in C.
Sadly, CC65 is a pure C compiler - no C++ yet, so no bitarray class to make life simpler.
It also has a number of other restrictions, like it doesn't support floating point.
You can't mix code and data, so like old school C you have to declare all of your variables
at the beginning of any scope block.
a There's no sqrt function provided in the CC65
runtime, so I was on my own there.
I'd like to say I wrote this from scratch, but just like you probably would, I copied
and pasted it from a Stackoverflow thread.
You'll notice that the main function is prototyped as void, so there are no arguments passed.
Absent any kind of shell or parent process beyond the machine language monitor itself,
I suppose arguments wouldn't make a lot of sense anyway.
The first thing we do is get the square root of the limit.
Next, we allocate enough memory to hold our bits at a 16:1 ratio.
We print out a banner showing the number of bits and bytes to aid in debugging, and then
do the actual memory allocation.
If it succeeds, we set all the bits to one, meaning the number represented by each index
starts out as potentially prime until eliminated.
Starting with the number 3, we scan through the array for the next available factor that
hasn't yet been crossed off out of the array.
When we find one, we start at its square and then walk through the bit array marking off
every second factor, since we know the even multiples are already nonprime.
We then step ahead to the next odd number and repeat, checking to see if it's a surviving
factor and so on.
When we're done we count the number of primes so we can sanity check the results against
known totals.
We then free the memory and return to the caller, which will ultimately fire a break
instruction and take us back to the monitor.
To test it, I used the srecord toolkit to create a paper tape file and load that into
memory.
That process is a little slow and painful, so if you want to see it live in action, check
out my video where I run Microsoft BASIC on the KIM1, where I show that entire paper tape
file process.
For now, I've got the sieve loaded up at 2000 hex.
I enter that address into the monitor and press G, at which point it runs the application.
The app prints our banner, reports that its working on 100,000 primes, and using a square
root of 316, all of which seems correct.
It tells us that it had to allocate 6,250 bytes to hold those 100,000 slots, and checking
the math, 6,250 times 16 is 100,000, so it has indeed allocated the precise number of
bits required.
I've tested 500,000 as well, and if nothing else that confirms that malloc can access
a large sequential block of memory when needed.
About a second later we get our result.
I know that 9394 plots out approximately right for the number of primes up to 100,000, but
I think it's actually off by a little bit.
It was perfect for 10,000, which I had checked before recording, however, so there may be
a sign extension bug.
Big kudos to anyone who can spot the bug and call it out in the comments!
How fast is one second?
Well, in Microsoft BASIC, the fastest I could ever achieve was six seconds for the primes
up to 1000.
This is doing several orders of magnitude more work and completing it within about one
second, so its no exaggeration to say that the C version is massively faster than the
BASIC version.
It's not even close.
It also compares favorably to the pure assembly language version that can be found in the
language racing project.
By the way, if you've never seen the language racing series, be sure to check it out next
- we port this prime sieve to more than 70 other languages, from Ada to Zig, and rank
their performance while touring the languages.
And there you have it!
Assuming they want it, I'll contribute these changes back to the master CC65 repo shortly.
Until then you can find it as a repo at PlummersSoftwareLLC, right alongside the language drag racing Prime
Number series, Nightdriver, and other cool source code projects from the channel.
As always, thanks to Rutger for all his hard work in acting as code czar and maintaining
sanity in our source repos, even when I break the build now and then.
If along the way you found today's episode to be any combination of entertaining or informative,
or if you'd like to see the upcoming NSA Key episode, I'd be honored if you'd consider
leaving it a like and subscribing to my channel.
If you have any interest in matters related to Autism, Asperger's, or ASD, please check
out my book on Amazon, Secrets of the Autistic Millionaire.
It's got nothing to do with money and everything to do with living a successful life on the
spectrum.
It's everything I know now that I wish I'd known back then.
Remember I'm mostly in this for the subs and likes, so please be sure to leave me one of
each before you go today.
In the meantime, and in between time, I hope to see you next time, right here in Dave's
Garage.