My first computer was a Texas Instruments TI-99/4A. Longtime readers may remember a previous article where we implemented TI-99/4A BASIC as a Scripting Language for modern computers. Recently I got nostalgic for the actual hardware so I got my 99 out of the closet where it had been for a decade or more. I hooked it up to the TV and turned it on. I was expecting to see something like this:

Instead I was greeted by this:

Well, that’s not right! It is in black and white. And what’s with all these vertical black lines? Clearly something’s wrong but what could it be?

New Meets Old

At first I suspected that it was my TV, which is a fairly new LCD. Old computers or game consoles sometimes played a bit fast and loose with the NTSC standard and it seemed unlikely that a new TV would ever have been tested with something as old as a TI-99/4A. Perhaps the TV just couldn’t interpret output from the 99. So I tried with a CRT TV:

Well the black bars are gone (or at least not as apparent) but it is still in black and white. Something must be wrong with the computer itself.

All About Video Signals

The output from the back of the computer is a composite video signal but using a 5-pin DIN connector (that also carries audio and power) instead of the usual RCA jack. Back when this computer was new that signal would usually to go an RF modulator which was then connected to a TV via a 300-ohm connector. Nowadays you can still do the same thing but since most TVs don’t have screw terminals on the back anymore it can be more convenient to take the composite video signal and hook it directly into the composite input on the TV. All that is required is a simple adapter cable that can be created yourself or purchased online.

I thought that perhaps the video circuitry was generating separate Luminance (Y) and Chrominance (C) signals and then combining them into the final composite output. If this were the case then it would suggest something was wrong in the C amplifier or the final combining stage. It turns out that this is not the case. The video chip in the TI-99/4A is referred to as the Video Display Processor (VDP) and is a TMS9918A, TMS9928A or TMS9929A depending on the region the computer was originally intended for and the television standard in use there (e.g. NTSC or PAL). My computer was made for the US market and outputs NTSC signals using the TMS9918A. This chip has a single video output pin that supplies composite video directly with the Y and C already mixed. So if something was wrong with just the C generation circuitry then it was something broken inside the VDP and my only recourse would be to try to find a replacement chip.

Mad Scientist Equipment

The VDP still seemed to work correctly in all other respects so I was hopeful that the true problem lay elsewhere. I thought I’d take a look at the signal on an oscilloscope. We’d expect to the see the NTSC colorburst and if it was missing that would explain why no color was showing up on the TVs. Here’s what it looked like:

And here’s a closeup of the interesting portion:

I’m no expert but that looks like a horizontal sync pulse followed by a colorburst to me. But there was still no color on the TV.

The composite video signal that the VDP generates is sent to a simple 2-transistor amplifier and then to the output jack. I didn’t think it was likely but perhaps something in the amplifier had given out and Y was still strong enough to get picked up by the TV but C wasn’t. To test this I took the computer apart and tapped the signal right as it came out of the chip and before it went through the amplifier. It was still black-and-white. This suggested that the problem was not in the amplifier.

The Healing Power of Crystals

At this point I knew that the VDP was mostly working correctly. It generated the right pattern on the screen so it must be able to communicate with both the video RAM and the CPU. That accounts for most of the pins on the VDP, the ones handling digital signals. The remaining pins are mostly for power and the connection to the quartz crystal that provides the timing. I checked the power and that seemed fine. So let’s take a closer look at the crystal:

The crystal is the gray-colored component in the middle. To the right is the VDP, covered in thermal paste. Just behind the crystal is a variable inductor.

A variable inductor: now that’s interesting! It is connected to the crystal and apparently used for fine tuning the frequency. Could the fix be as simple as turning an adjustment screw?

Alas, no. I turned it as far as it would go in both directions with no improvement to the video output. If the frequency was off it was beyond the ability of this adjustment to correct. I don’t have any equipment to allow precision measuring of the actual frequency this crystal was producing, but I do have the internet. A little Googling brought me to this post on the TI-99/4A mailing list. Yes, there’s still an active mailing list for a computer that hasn’t been manufactured in almost 30 years!

That post describes the symptoms that I was experiencing and indicated that the solution was to replace the crystal. This was somewhat surprising to me. I’d heard of electrolytic capacitors going bad in old equipment but a quartz crystal? They’re usually quite reliable. But you can’t argue with real-world experience.

The VDP takes the frequency of this crystal (10.738635 MHz) and divides it by 3 to produce the NTSC colorburst frequency (3.579545 MHz). If the frequency of the crystal was off then the generated colorburst would also be off and the TV wouldn’t be able to sync to it. Without seeing a valid colorburst the TV isn’t going to produce any color. That would certainly explain our symptoms!

So after deciding to replace this crystal we have to actually find a replacement part. We want a crystal that runs at exactly 10.738635 MHz. We also need it rated for the proper “load capacitance”. Running a crystal with the wrong capacitance will shift the frequency from the rated frequency. That would be bad since our entire goal is to get the frequency back to the ideal. The original crystal was rated for a load capacitance of 32pF (you can just make out the 32 in the above picture although it is partially obscured by the blue wire). So we want a replacement crystal that’s also rated for 32pF.

Let’s go internet shopping for 10.738635 MHz crystals. Jameco doesn’t carry any. Digikey has some but didn’t have any in stock with a 32pF load capacitance. Luckily Mouser came through for me! A few days later and I had a replacement crystal:

And after a little surgery on the motherboard:

Now for the moment of truth:

Success! Now to play some Parsec!

Bonus Oscilloscope Image

If you’re wondering what the colorburst looks like with the new crystal then wonder no longer.

Looks pretty similar to my eyes but apparently it makes a world of difference to a TV.

This is an article about the 6502 processor about the topic: how to “waste” a number of clock cycles stated in a register, in this case the X register. The principle is simple: you have a number of operations that do close to nothing. The more the code is jumped to at the “front”, the more clock cycles are needed to get to the actual code. If the code is jumped to more at the “end”, the CPU gets to the code in question more quickly.

This nice theory won’t work directly on the 6502, because every instruction takes at least two clock cycles to execute. If you want to get it down to the precision of one cycle, this is getting more difficult. The first half of this trick I found in code of Eckhard Stollberg, who is one of the guys that pionieered homebrew on the Atari 2600 VCS. There, I found some strange bytes:

C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C5 EA

The disassembly looks like this:

; CODE1
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP $EA  ; 3

To run through the code, you’ll need 15 clock cycles, and nothing changes except for some state registers. If the code is called with an offset of one byte, this code will be processed:

; CODE2
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP #$C9 ; 2
CMP #$C5 ; 2
NOP      ; 2

This makes 14 clock cycles, and only the status register will be changed. If the code is called with an offset of two bytes, it is started at the CODE1 segment at the second instruction. Add another one, you’ll get to the second instruction of the CODE2 segment, and so on. This way it is possible to specify the exact number of clock cycles to be “wasted”. With on exception: to be more specific there are 2 + X clock cycles that are wasted. There is no way to waste exactly one clock cycle.

Now we need a way to specify the “entry” of our “slide”. On a C=64 this would be done using self-modifying code. The operand of a JMP $XXXX instruction will be replaced with the calculated address. This is not possible on systems like the Atari 2600, since the code is run in ROM. One option for example would be to use JMP ($0080) after writing the entry point to $0080 and $0081.

My approach differs a bit from the usual way. RAM is scarce on the Atari, and I don’t want to “waste” up two of the 128 bytes available, when there is another way. When the CPU executes a JSR $XXXX (jump to subroutine) command, it writes the current address to the stack. To be more specific, it is the address of the JSR command + 2 which is the return address – 1. And this is what I do: I write my entry point – 1 to the stack and use the command RTS (return from subroutine) to jump into the clock slide. So, I’m still using two bytes of RAM, but only for a short time, without the need to evaluate which two bytes are available at this point.

; the X register specifies how many of the
; 15 clock cycles possible should be skipped
LDA #>clockslide
PHA
TXA
CLC
ADC #<clockslide
PHA
STA WSYNC ; <= this syncs to start of next scanline
clockslide:
RTS
CMP #$C9
CMP #$C9
CMP #$C9
CMP #$C9
CMP #$C9
CMP #$C9
CMP $EA
realcode:
; and here the real code continues

This approach still has one problem: between “clockslide” and “realcode”, no page crossing may occur. If this were the case, I’d have to increase the high byte on the stack by one. But since the position of the code segments is under my control, I left this out as an exercise for the reader. ;-)

While it has become far less relevant for non-system developers to write assembly than it was a few decades ago, by now CPUs have nevertheless made it much more comfortable to do so. Today we are used to a lot of things: fancy indirect addressing modes with scale, a galore of general purpose registers instead of an accumulator and maybe one or two crippled index registers, condition codes for nearly every instruction (on ARM)…

But also the basics themselves have evolved. Let’s take a look at what past programmers had to put up with in entirely simple, everyday things. We’ll start with the most trivial: writing to memory.

Our goal is to write a single immediate value of 3 into the memory location 5. In light of paging, segmenting and bank switching, we’ll use whatever is convenient as a definition for “memory location”. Also, we’ll let the CPU decide what the word size should be. Since you only need 2 bits to represent a 3, it should fit with every CPUs word size (except for 1 bit CPUs, which actually existed, but that’s a story for another posting). If we have the choice, we’ll just take the smallest.

We’ll work backwards, from the present to the past, to explore the wonders of direct addressing in Intel CPUs. (One precautionary warning though: I only really tested the 4004 code in an emulator, and my habits are highly tainted by current Intel CPUs. So if I made some mistake somewhere, kindly point it out and I’ll fix it!)

x86

On a modern x86 CPU, it is of course fairly easy to write the value 3 to memory cell 5. You just do it:

mov byte [5], 3

A single instruction, simple and obvious. I cheated a bit by not using a segment prefix, nor did I set up any segment registers/selectors beforehand. But assuming a nowadays common OS environment in protected mode, you probably don’t want to fiddle with those selectors anyway.

8085

The Intel 8085 is somewhat of a direct predecessor to the 8086, the first in the line of the excessively successful x86 processors. While the 8086 has a 16 bit data bus, the 8085 only has 8 bit. The address bus is already full 16 bit, but its 16 bit capabilities are limited. Specifically, there is no immediate 16 bit addressing (except for branches), leaving us no way to specify our memory location in the instruction that actually performs the move.

Memory is instead addressed with a pseudo register called M. This pseudo register is in reality just backed by the registers H and L paired together, each 8 bit wide, and accessing it accesses the memory location they point at (you may take a guess which register receives the High byte, and which the Low byte of the address).

Luckily, there are a few simple 16bit instructions for moving immediate values, so all in all we can write our byte with:

LXI H, 0005h ; unlucky syntax, as this actually means HL instead of just H

MOV M, 3

By the way, bonus points if you are somehow able to find out just when the address in HL is available on the address bus. The same applies to the 8080 and 8008. Does the CPU copy the register pair’s content to the address bus pins only when actual memory operations take place, or are the address bus pins somehow directly connected to H and L itself? Is that even feasible? I’d really like to find out…

8008

We continue going further back, skipping the 8080 because it was identical in that regard, and arrive at its direct predecessor instead, the Intel 8008. The 8080 and 8085 were source compatible to the 8008 (which, mind you, is not the same as binary compatible… also it may or may not have required some light automated translation), but in the downward direction we have something vital taking from us: While already using 16bit addresses (with only a 14bit address bus, resulting in 16k memory, though), the only instructions that were allowed to contain 16bit immediate values at all are jumps and branches. Consequently, we are left with no way to completely specify our destination address in one instruction!

Instead, we have to access H and L, together forming pseudo register M’s address, one at a time:

LHI 00h

LLI 05h

LMI 3

4004

It’s hardly possible to go back further than the Intel 4004, at least if you are only considering single chip CPUs (at the time of its conception in the early 70s, there were already famous multi-chip CPUs with comfortable orthogonal instruction sets, notably the PDPs). Indeed, it was the first widely available single chip CPU. This little thing was a 4-bit CPU with some strange quirks, which we will explore further. Overall, it bears little to no resemblance to its successor in name, the Intel 8008 (except for the internal stack, which both had–I will cover that in another posting).

But let’s just look at the code for writing a value of 3 into the memory location at 5 first:

FIM P0, 5; load address 05h into pair R0,R1

SRC P0   ; set address bus to contents of R0,R1

LDM 3    ; load 3 into accumulator

WRM      ; write accumulator content to memory

That looks a bit strange.

As a 4 bit CPU, the 4004 has 4 bit wide registers and addresses 4 bit nibbles as words in memory. It has only one accumulator on which the majority of operations is performed, but sixteen index registers (R0-R15).

Those index registers are handy for accessing memory: Besides loading values directly from ROM, an instruction exists to load data indirectly, which sets the address bus to the ROM cell’s content. Another instruction performs an indirect jump instead. Other than that, you can just increment index registers, albeit there is the interesting “ISZ” instruction that not only increments, but also branches if the result is not 0.

Because the 4004 uses 8 bits to address the 4 bit nibbles, every two consecutive index registers form a pair, which is then used for memory references.

Note that I explicitly said ROM above. This is because in the 4004 architecture, ROM and RAM are actually vastly different beasts, at least from the assembly programmer’s perspective. You can not directly access RAM. It always involves index register pairs, manually sending their content to the address bus (with a strangely named instruction “SRC”, which for some reason spells out send register control) and then issuing another instruction which transfers from or to the accumulator.

Interestingly, accessing regular RAM nibbles is not your only choice among the transfer instructions. You can also fetch from and to I/O ports. But the CPU does not have any direct I/O port, instead they are available on both RAM and ROM! You can also read and write “RAM status characters”, which to me look like plain regular RAM cells within another namespace. If someone knows, I’d love to hear what they were used for (and if they maybe did behave differently to normal RAM).

Take a look at the data sheet. Within its only 9 pages, the instruction set is depicted on page 4 and 5. Especially in the light that fairly reasonable orthogonal instruction sets appear to have been available in multi-chip CPUs, this first single-chip CPU is clearly a strange specialization towards the desk calculator it was meant for (the Busicom 141-PF). It has the aforementioned index register-centered RAM access, separate ROM (although there is a transfer instruction which strangely refers to some optional “read/write program memory”), a three level internal stack which is almost useless for general purpose programming and a lone special purpose instruction for “keyboard process” (KBP).

Original 4004 CPUs go from anything from a few to a few thousand dollars on eBay, depending on their packaging and revision. If you’d like to, you can instead play around with a virtual one in this java-script based, fully fledged assembler, disassembler and emulator, or read the rescued source code of the Busicom 141-PF calculator. There’s lots more of schematics, data sheets and other resources on the Intel’s anniversary project page.

That is, if you are brave enough.

[This is a follow-up to Thomas Tempelmann's Story of FCopy for the C-64.]

Ok, I have to make a confession … more than 25 years late:

I’ve reverse-engineered Thomas Tempelmann’s code, added various improvements and spread them around. I guess I’m at least partially responsible for the slew of fast-loaders, fast-copys etc. that circulated in the German C64 scene and beyond. Uh, oh …

I’ve only published AFLG (auto-fast-loader-generator) under my real name in the German “RUN” magazine. It owes quite a bit to TT’s original ideas. I guess I have to apologize to Thomas for not giving proper credit. But back then in the 80′s, intellectual property matters wasn’t exactly something a kid like me was overly concerned with.

Later on, everyone was soldering parallel-transfer cables to the VIA #1 of the 1541 and plugging them into the C64 userport. This provided extra bandwidth compared to the standard serial cable. It allowed much faster loading of programs with a tiny parallel loader (a file named “!”, that was prepended on all disks). Note that the commercial kits with cables, custom EPROMs and silly dongles followed only much later.

So I wrote “15 second copy”, which worked with a plain parallel cable. Yes, it copied a full 35 track disk in 15 seconds! There was only one down-side: this was only the time for reading/writing from and to disk — you had to swap the floppies seven times (!) and that usually took quite a bit more extra time! ;-)

It worked by transferring the “live” GCR-encoded data from the 1541′s disk head to the C64 and simultaneously doing a fast checksum. Part of the checksumming was done on the 1541, part was done on the C64. There simply weren’t enough cycles left on either side! Most of the transfer happened asynchronously by adjusting for the slightly different CPU frequencies and with only a minimum number of handshakes. This meant meticulous cycle counting and use of some odd tricks.

The raw GCR took up more space (684*324 bytes) in the C64 RAM, so that’s why it required 4 passes. Other copy programs fully decoded the GCR and required only 3 passes. But GCR decoding was rather time-consuming, so they had to skip some sectors and read every track multiple times. OTOH my program was able to read/write at the full 300rpm, i.e. 5 tracks per second plus stepper time, which boils down to 2x ~7.5 seconds for read and write. Yep, you had to swap the floppies every 2 seconds …

Ok, so I spread the program. For free. I even made a 40 track version, which took 17 seconds. Only to see these coming back in various mutations, with the original credits ripped out, decorated with multiple intros, different groups pretending they wrote it or cracked it (it was free, there was nothing to crack!). The only thing they left alone were the copy routines, probably because they were extremely fragile and hard to understand. So it was really easy to recognize my own code. Some of the commercial parallel-cable + ROM kits even bragged with “Backups in 15 seconds!”. These were blatant rip-offs: they basically changed the screen colors and added a check for their dongles. Duh.

Let’s just say this rather frustrating experience taught me a lot and that’s why I’m doing open source today.

So I shelved my plans to write an enhanced version which would try to compress the memory to reduce the number of passes. Ah, yes … I wrote quite a few packers, too … but I’ll save that story for another time.

I still have the disks with the source code somewhere in my basement. But I’m not so sure I’ll be able to read them anymore. They weren’t of high quality to begin with … and I’d have to find my homegrown toolchain, too. ;-)

But I took the time to reverse-engineer my own code from one of the copies that are floating around on the net. For better understanding on the C64/1541 handshake issues, refer to this article. If you’re wondering about the weird bvc * loops: the 6502 CPU of the 1541 has an SO pin, which is triggered by a full shift register for the data from the disk head. This directly sets the overflow flag in the CPU and allows reading the contents from the shift register with very low latency.

Yes, there’s a lot more weird code in there. For the sake of brevity, here are only the inner loops of the I/O routines for the read, write and verify pass for the C64 and the 1541 side. Enjoy!

  ;--- 1541: Read ---
  ldy #$20
f_read:
  bvc *        ; Wait for disk shift register to fill
  clv
  lda $1c01    ; Load data from disk
  sta $1801    ; Send byte to C64 via parallel cable
  inc $1800    ; Toggle serial pin
  eor $80      ; Compute checksum for 1st GCR byte in $80
  sta $80
  bvc *
  clv
  lda $1c01    ; Load data from disk
  sta $1801    ; Send byte to C64 via parallel cable
  dec $1800    ; Toggle serial pin
  eor $81      ; Compute checksum for 2nd GCR byte in $81
  sta $81
  ; ...
  ; Copy and checksum to $82 $83 $84
  ; And another time for $80 $81 $82 $83 $84 with inverted toggles
  ; ...
  dey
  beq f_read_end
  jmp f_read
f_read_end:
  ; Copy the remaining 4 bytes and checksum to $80 $81 $82
  ; Lots of bit-shifting and xoring to indirectly verify
  ; the sector checksum from the 5 byte xor of the raw GCR data

  ;--- C64: Read ---
  ; Setup ($5d) and ($5f) to point to GCR buffer
  ldy #$00
c_read:
  bit $dd00    ; Wait for serial pin to toggle
  bpl *-3
  lda $dd01    ; Read incoming data (from 1541)
  sta ($5d),y  ; Store to buffer
  iny
  bit $dd00    ; Wait for serial pin to toggle
  bmi *-3
  lda $dd01    ; Read incoming data (from 1541)
  sta ($5d),y  ; Store to buffer
  iny
  bne c_read
c_read2:
  bit $dd00    ; Wait for serial pin to toggle
  bpl *-3
  lda $dd01    ; Read incoming data (from 1541)
  sta ($5d),y  ; Store to buffer
  iny
  bit $dd00    ; Wait for serial pin to toggle
  bmi *-3
  lda $dd01    ; Read incoming data (from 1541)
  sta ($5d),y  ; Store to buffer
  iny
  cpy #$44
  bne c_read2

  ;--- C64: Write ---
  ; Setup ($5d) and ($5f) to point to GCR buffer
  ldy #$00
  tya
c_write:
  eor ($5d),y  ; Load from buffer and compute checksum
  bit $dd00    ; Wait for serial pin to toggle
  bpl *-3
  sta $dd01    ; Store xor'ed outgoing data (to 1541)
  iny
  eor ($5d),y  ; Load from buffer and compute checksum
  bit $dd00    ; Wait for serial pin to toggle
  bmi *-3
  sta $dd01    ; Store xor'ed outgoing data (to 1541)
  iny
  bne c_write
c_write2:
  eor ($5f),y  ; Load from buffer and compute checksum
  bit $dd00    ; Wait for serial pin to toggle
  bpl *-3
  sta $dd01    ; Store xor'ed outgoing data (to 1541)
  iny
  eor ($5f),y  ; Load from buffer and compute checksum
  bit $dd00    ; Wait for serial pin to toggle
  bmi *-3
  sta $dd01    ; Store xor'ed outgoing data (to 1541)
  iny
  cpy #$44
  bne c_write2
  ldx $5b
  sta $0200,x  ; Store checksum for verify pass
  inx
  stx $5b

  ;--- 1541: Write ---
  ldy #$a2
  lda #$00
f_write:
  bvc *        ; Wait for disk shift register to clear
  clv
  eor $1801    ; Xor with incoming data (from C64)
  sta $1c01    ; Write data to disk shift register
  dec $1800    ; Toggle serial pin
  lda $1801    ; Reload data to undo xor for next byte
  bvc *        ; Wait for disk shift register to clear
  clv
  eor $1801    ; Xor with incoming data (from C64)
  sta $1c01    ; Write data to disk shift register
  inc $1800    ; Toggle serial pin
  lda $1801    ; Reload data to undo xor for next byte
  dey
  bne f_write

  ;--- 1541: Verify ---
  ; Get checksum computed by c_write on the C64 side
  ldy #$a2
f_verify:
  bvc *        ; Wait for disk shift register to fill
  clv
  eor $1c01    ; Xor with data from disk
  bvc *        ; Wait for disk shift register to fill
  clv
  eor $1c01    ; Xor with data from disk
  dey
  bne f_verify
  ; Verify is ok if checksum is zero

Back in the 80s, the Commodore C-64 had an intelligent floppy drive, the 1541, i.e. an external unit that had its own CPU and everything.

The C-64 would send commands to the drive which in turn would then execute them on its own, reading files, and such, then send the data to the C-64, all over a propriatory serial cable.

The manual for the 1541 mentioned, besides the commands for reading and writing files, that one would read and write to its internal memory space. Even more exciting was that one could download 6502 code into the drive’s memory and have it executed there.

This got me hooked and I wanted to play with that – execute code on the drive. Of course, there was no documention on what code could be executed there, and which functions it could use.

A friend of mine had written a disassembler in BASIC, and so I read out all its ROM contents, which was 16KB of 6502 CPU code, and tried to understand what it does. The OS on the drive was quite amazing and advanced IMO – it had a kind of task management, with commands being sent from the communication unit to the disk I/O task handler.

I learned enough to understand how to use the disk I/O commands to read/write sectors of the disk. Actually, having read the Apple ]['s DOS 3.3 book which explained all of the workings of its disk format and algos in much detail, was a big help in understanding it all.

(I later learned that I could have also found reverse-eng'd info on the more 4032/4016 disk drives for the "business" Commodore models which worked quite much the same as the 1541, but that was not available to me as a rather disconnected hobby programmer at that time.)

Most importantly, I also learnt how the serial comms worked. I realized that the serial comms, using 4 lines, two for data, two for handshake, was programmed very inefficiently, all in software (though done properly, using classic serial handshaking).

Thus I managed to write a much faster comms routine, where I made fixed timing assumptions, using both the data and the handshake line for data transmission.

Now I was able to read and write sectors, and also transmit data faster than ever before.

Of course, it would have been great if one could simply load some code into the drive which speeds up the comms, and then use the normal commands to read a file, which in turn would use the faster comms. This was not possible, though, as the OS on the drive did not provide any hooks for that (mind that all of the OS was in ROM, unmodifiable).

Hence I was wondering how I could turn my exciting findings into a useful application.

Having been a programmer for a while already, dealing with data loss all the time (music tapes and floppy disks were not very realiable back then), I thought: Backup!

So I wrote a backup program which could duplicate a floppy disk in never-before seen speed: The first version did copy an entire 170 KB disk in only 8 minutes (yes, minutes), the second version did it even in about 4.5 minutes. Whereas the apps before mine took over 25 minutes. (Mind you, the Apple ][, which had its disk OS running on the Apple directly, with fast parallel data access, did this all in a minute or so).

And so FCopy for the C-64 was born.

It became soon extremely popular. Not as a backup program as I had intended it, but as the primary choice for anyone wanting to copy games and other software for their friends.

Turned out that a simplification in my code, which would simply skip unreadable sectors, writing a sector with a bad CRC to the copy, did circumvent most of the then-used copy protection schemes, making it possible to copy most formerly uncopyable disks.

I had tried to sell my app and sold it actually 70 times. When it got advertised in the magazines, claiming it would copy a disk in less than 5 minutes, customers would call and not believe it, “knowing better” that it can’t be done, yet giving it a try.

Not much later, others started to reverse engineer my app, and optimize it, making the comms even faster, leading to copy apps that did it even in 1.5 minutes. Faster was hardly possible, because, due to the limited amount of memory available on the 1541 and the C-64, you had to swap disks several times in the single disk drive to copy all 170 KB of its contents.

In the end, FCopy and its optimized successors were probably the most-popular software ever on the C-64 in the 80s. And even though it didn’t pay off financially for me, it still made me proud, and I learned a lot about reverse-engineering, futility of copy protection and how stardom feels. (Actually, Jim Butterfield, an editor for a C-64 magazine in Canada, told its readers my story, and soon he had a cheque for about 1000 CA$ for me – collected by the magazine from many grateful users sending 5$-cheques, which was a big bunch of money back then for me.)

Im Februar hat mich Tim Pritlove auf der Durchreise in Frankfurt abgefangen, wo ich mit einem Koffer voll mit zwölf Commodore 64 Motherboards in einem Hotelzimmer saß, und mit mir eine 2 Stunden und 42 Minuten lange Episode für Chaosradio Express aufgenommen.

Chaosradio Express #177: Commodore 64

Hier also nochmal der Hinweis auf die Folge, die jetzt schon ein paar Monate zurückliegt, für all diejenigen, die sie nicht schon anderweitig entdeckt haben. :-)

Richard Immers and Gerald G. Neufeld:
Inside Commodore DOS : the complete guide to the 1541 disk operating system.
Northridge, Calif. : Datamost, 1985.
ISBN 0-8359-3091-2

In my quest to preserve retrocomputing documents, here is the invaluable book “Inside Commodore DOS”, which describes most of the internals of the Commodore 1541 disk drive. The scanning was done in 2002 by Kenneth S. Moore, who in 2005 released an OCRed version, which unfortunately replaced the original page images. My version here comes with the original page images and a table of contents, and is nevertheless fully searchable.

Here is a fun quote from the book by the way:

Over the years numerous writers have advised Commodore owners not to use the save and replace command because it contained a bug. Our study of the ROM routines and a lot of testing has convinced us that the bug in the replace command is a myth.

Of course, this is wrong. Don’t use “SAVE@” on a 1541.

In the Pixar movie Monsters Inc., you can see the following file of a child at 12 min 40 sec:

Monsters scare children at night, and this is how they keep track of them. The file comes with a blueprint of the room, a list of date stamps, business-critical notes like “scared of snakes”, and the standard data like name, gender, age, and… uh, race??

Albert Lozano, age 8, seems to be “hispanic”, and for monsters, this is apparently a feature that is important to them.

Oh well, that’s Monstropolis, a world inhabited by monsters that scare little children. Modern societies, on the other hand, have understood that “race” is a detail that is just as useful to track as shoe size. Oh wait.

Commodore Business Machines.
Commodore 128 Programmer’s Reference Guide.
New York, NY: Bantam Books, 1986.
ISBN 0-553-34378-5

In my quest to preserve retrocomputing documents, here is the official Commodore 128 Programmer’s Reference Guide. As always, my scanned books come with a table of contents and are fully searchable.

SCUMM script was a little odd. When I first started designing the language, I was going to base it on Lisp. I was use to using it to customize emacs that we used to do all our coding. This was not on PCs, but on large multiuser UNIX machines. The Lucasfilm games group was part of the Lucasfilm computer division (which later became Pixar) and we had some very smart people that connected the C64 to the UNIX machine. From my UNIX terminal, I had complete control over the C64 and wrote a source level debugger for SCUMM. The 6502 assembler was custom written by Chip Morningstar and ran on the UNIX machine.

But I digress. So, SCUMM started out as Lisp based, but I quickly abandon that approach in favor of something that looked a little more C-like, but some aspects of Lisp remained, mostly in the naming conventions. Commands and variables used – (dashes) as separators.

sandy-rescued = 1

This was a single variable, not sandy minus rescued. So how did SCUMM do subtraction? You didn’t. Until Monkey Island, there was no way to do complex expressions. if you wanted to subtract a value you used:

count -= 5

If you had a complex expression, you had to chain them using +=, -=, /= and *= using temp variables. Ugly, but it made the interpreter much simpler.

(Side note, the C64 interpreter was not named SPUTM, that name didn’t come about until the PC version).

One of the goals I had for the SCUMM system was that non-programers could use it. I wanted SCUMM scripts to look more like movies scripts, so the language got a little too wordy. This goal was never really reached, you always needed to be a programmer. :-(

Some examples:

actor sandy walk-to 67,8

This is the command that walked an actor to a spot.

actor sandy face-right
actor sandy do-animation reach
walk-actor razor to-object microwave-oven
start-script watch-edna
stop-script
stop-script watch-edna
say-line dave "Don't be a tuna head."
say-line selected-kid "I don't want to use that right now."

if (melt-down) {
  say-line selected-kid "I don't think this game is very fun."
}

There were no functions, everything was a ‘script’, a small piece of code that looked a lot like a function, but it ran in it’s own virtual process.

script watch-clock {
  do {
    object clock state ON
    break-time 60
    object clock state OFF
    break-time 60
  }
}

Note the lack of a until/while on the do loop. The script would just continue until someone killed it.

Time was always measured in jiffies (1/60 second). Later on I added the ability to say ‘break-time 1 minute’ and the compiler just multiplied by 60 before emitting the opcode.

If you did…

start-script watch-edna
start-script clock-tick

…you now had 2 additional scripts running and they all ran at the same time using preemptive multitasking. It was a heck of a lot better than doing state engines. If you wanted to keep an eye on something, you’d just say…

start-script watch-edna

…and then forget about it. That one script could do whatever it needed and start a cut-scene if the need arose.

This may seem pretty tame today, but back then, it was like magic.

Bonus information: The SCUMM compiler was written in Yacc and Lex.

(This is a reprint from “Vandalism News” issue 52)

Maniac Mansion is a true classic – in many ways.

It’s a classic example of smart game play versus photorealistic graphics that is lacking in so many modern productions and it’s the first LucasArts Adventure that made use of the point and click verb parser. And it’s of course eponymous for the famous SCUMM – the scripting utility for Maniac Mansion. This is reason enough to talk about it in some more detail and as a side effect advertise the NEOram version for C64 released just now. :)

MM has a nice Wikipedia page (especially in Finnish – check it out :) so I think I shall concentrate on some technical specialties:

The original Scumm (version 0) was designed for C64 in ’87 and its idea was to be able to develop a game independently of the target machine and only port the SPUTM (script presentation utility TM (seriously)) to several architectures. However it started with C64 and for several reasons the C64 version was kind of special in comparison to all later ports. Hence Scumm version 0 is only used here. Even Zak McKracken already had important changes and fixes. The original version came on disk with some copy protection (not too bad, not many cracks are around) and hence there is no in-game copy protection unlike all other versions (except for the Apple). You may have seen that code door at 2nd floor on other computers and guess what: the door code is made of PETSCII graphics chars! Officially the protection was left out due to disk space. In fact the 2 disk sides are pretty crammed in the original. So the game design was done on PC (UNIX system) and assembled there. This explains the spaghetti like distribution of the data and some of the code. In general the data is split into rooms. A room contains all the data for a specific area in the game. I.e. the beginning with the beautiful moon in the background or the kitchen is one ‘room’ each. The data consists of one graphics charset in multicolour mode and its screen map (from 40×17 up to 160×17 chars big), one full charset for the clipping mask with its map (same size as screen map of course), a colourmap for the fourth colour per char (ranging only from 0-7) and then the scripts themselves. There is one room data set for each location and numerous scripts, one for each room and several additional ones.

The scripts are more or less freely distributed among the rooms by the original SCUMM. They differ a LOT between English and German versions, for example to have minimal waste of space at the end of a sector on disk. Beside the room graphics and script data there is also data for sound effects, the characters in the game and the objects. The people in the game are drawn as sprites, but not constructed from ordinary sprites but plotted into a semi static multiplexed sprite matrix in real time each frame (17 raster-splits per frame). The data for the characters is also attached to several rooms. Often the one they appear in first. The text charset is not the ROM font btw. Since usually $01 is set to $14, hence RAM, RAM, RAM…

Each actor has a vertical stripe of sprites covering the whole height and this allows for quite some actors on screen simultaneously. The sprite priorities are set according to the actors positions, so you can actually walk in front or behind other kids and even orbit them for hours… MM is so much fun. :)

The graphics are stored in sprite like format (3 bytes per line) but with a successive height of 16 pixels normally. To save space each person is only stored from front, back and its right side. Whenever someone is facing left, the graphics data is mirrored via table and then plotted. Oh, and all the facial expressions, well the mouth and the chin (being one pixel) are not part of the data but added during plotting. Btw, the explosion in the intro, chucky the plant and the mummy are stored and handled as actors as well. You can see that when you leave the bathroom: the mummy disappears just before the rest does. To prevent the secret phone number from being revealed the background graphics is distorted of course. :) The graphics replacements are stored among the objects. So an open radio is a replacement of the object graphics radio. Stored as x, y position in char steps inside the room area and its width. Each object has an owner attribute and a position x, y in chars where to walk to (which is not necessarily identical to its position). Also there is a byte containing the height of the object in pixels (using 6 bits) while the upper 2 bits give the direction the actor is facing when reaching the object. So when Dave opens the fridge we see his back but when reaching a door, he’s facing right for example. The object’s name is also given along with a pointer to the script dealing with it. Those pointers are 24bit wide. 1 byte for the room it is attached to (again, these data change between different language versions) and another 16bit offset inside that data chunk.

The scripting for MM is rather complex. The memory resident interpreter understands 82 opcodes and handles 256 global variables! There is lots of things are stored and swapped around. Like whose friend with Ed or the Tentacle or whether the highscore at the arcade is already set… It even has fancy stuff like a random number generator (yes, the numbers in the game like phone numbers, codes) are not always the same! (Look for the cheat in the NEOram version that displays Edna’s phone number, the safe combination, the radio frequency and the highscore once it’s played).

A typical script contains commands like these:

(0035) (42)   startScript(103)
(0037) (02)   startMusic(185)
(0039) (CE)   putActorAtObject(Var(225),162)
(003C) (82)   stopCurrentScript()
(003D) (04)   unless (Var(61) <= 73) goto 5A96
(0042) (66)   Var(66) = getClosestObjActor25(113)
(0045) (02)   startMusic(186)
(0047) (CF)   setState02()
(0048) (E2)   stopScript(Var(162))
(004A) (82)   stopCurrentScript()
(004B) (03)   doSentence(62,74,55)
(004F) (5B)   Var(69) = getActorBitVar(103,Var(64))

Unlike in later Scumm revisions, version 0 for C64 has quite some C64 specific hard coded stuff inside the data. A nice example: ALL actor graphics are stored the same way (you can simply try a PC based multicolour sprite ripper on the disk images) except for the breasts of Sandy =D They are stored completely separate. Maybe to prevent early nude-hacks? Back to the data formats. There is quite some graphics in this game - there is a total of 52 rooms, including the initial kid selection screen, save game screen or cut scenes which are all handled by the same interpreter and format. To make all this fit onto two disk sides, there is a specific RLE encoding. The four most common bytes of the data to follow are given for each data chunk. These were derived by the SCUMM on the PC during compilation already. The encoding is arranged as following:

• A data byte of < $40 gives the number of different single unpacked bytes to follow.
• $3f to < $80 represents the length of the run of the byte to follow (+$3f of course).
• $7f to < $a0 is the number of runs of most common byte 1,
• $9f to < $c0 and $bf to <$e0 and $df-$ff for common byte 2, 3 and 4 respectively.

This encoding is rather effective for the MM graphics. Walkable areas for a room are composed of a list of multiple boxes with varying size and positions and stored after the graphics data. You probably noticed the slowdown during scroll in the game. This is due to the double buffered scroll which waits for all the clipping and room data to be moved into the correct RAM areas. The colour scroll of $d800 is done with some sort of line based speed code. Rastertime and memory are both used almost to the max. At start-up some own drive code is loaded into the floppy (not in my NEOram version of course). Later on a room is loaded by checking which room we want to see next, then getting its corresponding disk side from a table, checking for correct disk, getting the track and sector at which the room data starts from another table, calling a function to set this t/s offset, then calling another function with the target address in memory and another one with the length to be transferred. Only then will the room data be actually loaded. Even worse, usually only the first few bytes are read since they contain the offset to the table of other offsets (actors, objects, and scripts) which are then loaded to the corresponding memory areas. As soon as the drive code is initialised that RAM area on C64 side is overwritten by data AND code again. So the only memory available for extra code in this version was the drive interface and some other routines handling disk sides etc. A major gain was for example the now obsolete "wrong disk" message. This game really uses all the RAM there is. Most of the stack is occupied by code as well. Some of the JMPs instead of JSRs in the interpreter I didn't get at first were due to that fact - to keep the stack pointer high (that was kind of sucky to debug).

I was able to rewrite some interpreter routines as well to gain more space for the mouse driver and save game selection.

And, err... I removed the checksum check for each room data. That was also quite some speedup btw and it probably prevented lots of people from making trivial changes to the game. Yet it is hardly possible to apply big changes in the game logic. All offsets are hard-coded to the data. Even changing the length of the name for i.e. the 'fridge' by 1 char, causes dozens of offsets to change (for costumes, scripts, sounds, other rooms and so on). Even the interpreter looks rather different from language to language. And the RLE nature of the data, makes it pretty hard to change graphics as well since they have to keep the same size.

For the NEOram version I only redistributed the room data and completely replaced its track/sector/disk side structure.

So unlike all other patches before this one no longer 'emulates' disk access anymore. MM handles the pointer on screen very arborescent and there is no such thing like an "open" function call. Instead pointer positions are stored as x, y chars on screen, x, y relative to room origin in chars, x, y as pixels on screen, x, y as pixel coordinates (half the x resolution 0-159) and as a delta to last frame. All of these are set by different functions. So when a verb is highlighted and you press fire, multiple addresses are set already in the background. The call itself is a self modified JMP in the end. To allow the OPEN and PICKUP command on the right mouse button I rewrote the button routine instead. The input from the mouse is faked as if it would point to the OPEN verb, the pointer is hidden (more or less), the old position stored and the mouse driver is skipped for the next 3 frames while the joystick readout is rerouted to an own routine that returns button pressed for the next frame, then 1 frame of button release and still no mouse action, one frame to return old pointer coordinates and run the routine to convert the mouse coordinates to all those mentioned before and finally enable pointer sprite and toggle mouse control back in. Sounds a bit weird but otherwise there isnt enough rastertime left. This is also why you shouldn't use the mouse on an NTSC system. The mouse is read every 2nd frame only for the very same reason. The evaluation of the new coordinates for the game engine (x, y in absolute and relative chars and check for verb activation) are only carried out when the mouse driver itself is skipped. This was the only way to get things done before the next rastersplit is due. Also the mouse is disabled as long as a button is pressed or actions with objects or scrolling the inventory would take too much rastertime. And sometimes you see a little jerky screen during loading when the I/O area has to be switched in to set NEOram registers and the rasterline hits the IRQ to switch back to text mode. I chose this part of the screen since its the least disturbing and usually works quite ok. MM is and was great fun - as soon as I've had some rest I will look into Zak McKracken deeper. Almost can't wait to do so (imagine both games on one cart). Have a lot of fun and try all the different solutions to the game.

Yes, Jeff HAS some more or less special ability and you can use the integrated room viewer to check for things yet unseen ;-)

Did you every finish the game without shooting that poor meteor (why is no one calling it accurately 'meteorite'?) into space? Go ahead and enjoy another game of Maniac Mansion. The NEOram image will work well under vice by the way but if you consider assembling your own NEOram card just look for schematics and part-lists on the web or contact maniac`enthusi.de - Quite likely there are some PCB boards still around.

Ok, let's go rescue Sandy!

/enthusi

In Zak McKracken, how can you get into the situation pictured below? Note that you need the CashCard in order to leave San Francisco, and Zak cannot give away his CashCard.

C64:

FM Towns:

Bonus points if you solve it by converting the SCUMM script into a graph and programmatically finding the shortest path to this state.

(Read the solution in the comments.)

Why is that?

C64:

Nintendo Entertainment System:

MS-DOS Enhanced:

(Read Maniac Mansion creator Ron Gilbert’s authoritative answer in the comments.)

(Read comments for solution.)

Here is an easy one, taken from a discussion on Facebook:

“Liberals make no sense at all. On the one hand, they complain about the war killing innocent people, and on the other hand, they are okay with killing innocent unborn children.”

This is the plain inverted version:

“Conservatives make no sense at all. On the one hand, they complain about killing innocent unborn children, and on the other hand, they are okay with the war killing innocent people.”

Of course, this requires some adjusted rhetorical decoration:

“Conservatives make no sense at all. On the one hand, they complain about abortion, and on the other hand, they are okay with the war killing innocent women and children.”

Here is another one, from Twitter (source not given to protect the individual):

“Don’t critisize German nuclear power plants, because Japan is far away”, say people who demand total surveillance in Germany whenever Bin Laden farts.

This one is full of rhetorical devices that need to swap sides. You could say something like:

“Ignore terrorist threats in Germany, because New York, London and Madrid are far away”, say people who want to immediately turn off 22% of Germany’s electricity because 8.9 earthquakes and tsunamis happen there, too!

Recently, German publisher heise.de interviewed Felix “fefe” von Leitner, a security expert and CCC spokesperson, on Mac OS X security:

heise.de: Apple has put protection mechanisms like Data Execution Prevention, Address Space Layout Randomization and Sandboxing into OS X. Shouldn’t that be enough?

Felix von Leitner: All these are mitigations that make exploiting the holes harder but not impossible. And: The underlying holes are still there! They have to close these holes, and not just make exploiting them harder. (Das sind alles Mitigations, die das Ausnutzen von Lücken schwerer, aber nicht unmöglich machen. Und: Die unterliegenden Lücken sind noch da! Genau die muss man schließen und nicht bloß das Ausnutzen schwieriger machen.)

Security mechanisms make certain bugs impossible to exploit

A lot is wrong about this statement. First of all, the term “harder” is used incorrectly in this context. Making “exploiting holes harder but not impossible” would mean that an attacker has to put more effort into writing exploit code for a certain security-relevant bug, but achieve the same at the end. While this is true for some special cases (with DEP on, certain code execution exploits can be converted into ROP exploits), but the whole point of mechanisms like DEP, ASLR and sandboxing is to make certain bugs impossible to exploit (e.g. directory traversal bugs can be made impossible with proper sandboxing) – while other bugs are unaffected (DEP can’t help against trashing of globals though an integer exploit). So mechanisms like DEP, ASLR and sandboxing make it harder to find exploitable bugs, not harder to exploit existing bugs. In other words: Every one of these mechanisms makes certain bugs non-exploitable, effectively decreasing the number of exploitable bugs in the system.

As a consequence, it does not matter whether the underlying bug is still there. It cannot be exploited. Imagine you have an application in a sandbox that restricts all file system accesses to /tmp – is it a bug if the application doesn’t check all user filenames redundantly? Does the US President have to lock the bedroom door in the White House or can he trust the building to be secure? Of course, a point can be made for diverse levels of barriers in systems of high security where a single breach can be desastrous and fixing a hole can be expensive (think: Xbox), but if you have to set priorities, it is smarter for the President to have security around the White House than locking every door behind himself.

Symmetric and asymmetric security work

When an operating systems company has to decide on how to allocate its resources, it needs to be aware of symmetric and asymmetric work. Finding and fixing bugs is symmetric work. You are as efficient finding and fixing bugs as attackers are finding and exploiting them. For every hour you spend fixing bugs, attackers have to spend one more hour searching for them, roughly speaking. Adding mechanisms like ASLR is asymmetric work. It may take you 1000 hours to get it implemented, but over time, it will waste more than 1000 hours of your attackers’ time – or make the attacker realize that it’s too much work and not worth attacking the system.

Leave security to security code

Divide your code into security code and non-security code. Security code needs to be written by people who have a security background, they keep the design and implementation simple and maintainable, and they are aware of common security pitfalls. Non-security is code that never deals with security. It can be written by anyone. If a non-security project requires a small module that deals with security (e.g. verifies a login), push it into a different process – which is then security code.

Imagine for example a small server application that just serves some data from your disk publicly. Attackers have exploited it to serve anything from disk or spread malware. Should you fix your application? Mind you, your application by itself has nothing to do with security. Why spend time on adding a security infrastructure to it, fixing some of the holes, ignoring others, and adding more, instead of properly partitioning responsibilities and having everyone do what they can do best: The kernel can sandbox the server so it can only access a single subdirectory, and it can’t write to the filesystem. And the server can stay simple as opposed to being bloated with security checks.

How many bugs in 1000 lines of code?

A lot of people seem to assume they can find and fix all bugs. Every non-trivial program contains at least one bug. The highly security-critical first-stage bootloader of the original Xbox was only 512 bytes in size. It consisted of about 200 hand-written assembly instructions. There was one bug in the design of the crypto system in the code, as well as two code execution bugs, one of which could be exploited in two different ways. In the revised version, one of the code execution bugs was fixed, and the crypto system had been replaced with one that had a different exploitable bug. Now extrapolate this to a 10+ MB binary like an HTML5 runtime (a.k.a web browser) and think about whether looking for holes and fixing them makes a lot of sense. And keep in mind that a web browser is not all security-critical assembly carefully handwritten by security professionals.

Conclusion

So stop looking for and fixing holes, this won’t make an impact. If the hackers find one, instead of researching “how this could happen” and educating the programmers responsible for it, construct a system that mitigates these attacks without the worker code having to be security aware. Leave security to security code.

This article presents a C64 “fast bootloader”: A small program that auto-starts when loaded into memory and chain-loads e.g. a game, but replacing the slow disk transfer routines in ROM with much faster ones – and all this fits into a single 256 bytes sector.

The C64 and the Drive 1541

The C64 is an 8-bit computer released in 1982 that is powered by a 1 MHz 6502-based CPU and has 64 KB of RAM. A typical C64 setup also consists of a Commodore 1541 disk drive (5.25″ SS/DD media, 170 KB per side) which is a 1 MHz 6502 computer with 2 KB of RAM itself.

The IEC Bus

The computer and the drive are connected through a serial cable that carries three lines from the computer to the drive (ATN, CLK, DATA) and two from the drive to the computer (CLK, DATA). This IEC bus supports several daisy-chained disk drives (and printers), and the computer uses the ATN line to arbitrate the bus.

IEC was introduced in the C64′s predecessor VIC-20 and its floppy drive 1540, as a cheaper version for the parallel IEE-488 bus. Each device had a 6522 “VIA” I/O controller that could do a simple serial protocol in hardware – in theory. The serial port in the VIAs never worked, so Commodore decided to work around the issue by just implementing the protocol in software, after all, both devices had programmable CPUs. The C64, running basically the same system software as the VIC-20, and the 1541, a slightly updated disk drive for the C64, inherited this design.

As a result of every single bit having to go through a software handshake, the ROM code in the C64 and the drive could only transfer about 400 bytes per second. A game that fills all of RAM would take more than two minutes to load. Another issue of the IEC code in the C64 ROM is that it turns off interrupts every once in a while, making it impossible to properly play music in the background while loading data from disk.

Fast Loaders

Practically every game and every demo therefore only had a small boot program that was loaded by the original ROM code, typically less than a kilobyte in size, which contained more efficient serial code for the computer side, as well as corresponding code for the drive, which was uploaded into the drive’s RAM using the original serial protocol.

The Protocol

The original IEC protocol uses one clock and one data line in each direction. The sender alternates the clock line on every bit of data, and the receiver has to acknowledge the receipt by alternating its clock line. The idea of a faster protocol is to send a whole byte, bit by bit without a clock signal: Whenever both devices are undisturbed by interrupts and device DMA, we can assume the clocks of both devices to be enough in sync for the duration of transmitting a byte. (In fact, the 1541 is clocked a little bit faster than a PAL C64, so there is one extra 1541 cycle for every 67 C64 cycles.) Since the clock line is now not necessary for the handshake, it can be used for data, so we can transmit two bits at a time, and transfer a byte in four steps.

Receiving a Byte

The IEC bus is controlled through port A of the C64′s second 6526 “CIA” I/O chip, which is accessible through the MMIO address $DD00:

We can signal the drive when we are ready to receive a byte through bits 4 and 5, and the drive can send data through bits 7 and 6. We need to be careful not to change bits 0 and 1, since these select the 16 KB memory bank that the video chip fetches its data from – typically, these bits are both 1.

The fastest way to receive a byte from the serial bus (given the sender is fast enough) is to repeatedly read two bits from $DD00, shift them down, then read the next two bits, and repeat all this four times:

    lda $DD00 ; get 2 bits into bits 6-7
    lsr
    lsr       ; move down into bits 4-5
    eor $DD00 ; get 2 more bits
    lsr
    lsr       ; move everything down to bits 2-5
    eor $DD00 ; get 2 more bits
    lsr
    lsr       ; move everything down to bits 0-5
    eor $DD00 ; get last 2 bits

The trick here is to XOR the new bits onto the already received and shifted bits, this way we avoid shifting, ANDing and ORing. An absolute load taking four cycles and a shift instruction two, receiving a byte takes 28 cycles total. We need to make sure the sending side has the same timing.

Sending a Byte

The 1541 disk drive has the IEC bus exposed through port A of its first “VIA” I/O chip, which is mapped at $1800:

The bits to write the data into are number 1 and number 3, which are not next to each other, so sending is a little more complicated than receiving. The following code assumes that the low 4 bits of the data byte are in register A, and the high 4 bits are in register Y:

    sta $1800 ; send bits 1 and 3 of A
    asl       ; bits 0 and 2 become bits 1 and 3
    and #$0F  ; mask off bit #4
    sta $1800 ; send bits 0 and 1 in A
    tya
    nop
    sta $1800 ; send bits 1 and 3 in Y
    asl       ; bits 0 and 2 become bits 1 and 3
    and #$0F  ; mask off bit #4
    sta $1800 ; send bits 0 and 1 in Y

The idea is to first just write the low 4 bits into the output port, therefore sending bits 1 and 3. Shifting the value left by one will put bits 0 and 2 into positions 1 and 3 and we can send them by writing them into the output port. Then we repeat this with the upper four bits.

The absolute stores are taking 4 cycles each, and “asl”, “and”, “tya” and “nop” all take 2 cycles each, so this code has exactly the same timing as the receiver side.

But unfortunately, this code sends the bits in the wrong order, so we need to correct it, either on the sending or on the receiving side. A simple lookup in a 256 byte table (on either side) would do the job, but storing the table in the fast loader would increase its size significantly – and therefore the time to load the fast loader with the original Commodore serial code. It would be possible to generate this table at runtime, but a good tradeoff between size and performance is this code (34 bytes; with a few bytes more, it could be converted into a generator for the table):

    eor #3        ; fix up bits 0-1 (VIC bank)
    pha           ; save original
    lsr
    lsr
    lsr
    lsr           ; get high nybble
    tax           ; to X
    ldy enc_tab,x ; super-encoded high nybble in Y
    pla
    and #$0F      ; lower nybble
    tax
    lda enc_tab,x ; super-encoded low nybble in A

enc_tab:
    .byte %1111, %0111, %1101, %0101, %1011, %0011, %1001, %0001
    .byte %1110, %0110, %1100, %0100, %1010, %0010, %1000, %0000

First, we invert the lowest two bits of the value to send, because the receiving side always reads back “11″ in the lowest bits of $DD00. Then we encode both the high and the low 4 bits using a 16 byte table, putting the results in the A (low) and Y (high) registers. This table interleaves the four bits so that 0123 becomes 3120 and inverts every bit: An interesting property of the lines from the drive to the computer is that all lines arrive inverted at the computer side. This is not the case for the lines from the computer to the drive. So after this conversion, the send code above can blindly send the bits, which will show up as the original value on the receiver side.

Handshake

But it is not enough to just bang the bits on the bus – after every byte, we need to do a handshake. In a perfect world, we could just send a complete sector (256 bytes on a 1541) in a go, maybe even in an unrolled loop for extra speed, but there are several reasons against it. One reason is that the floppy is clocked about 2% faster, so we’re off by one cycle every 67 cycles. The fastest possible send loop is about 50 cycles per byte (including the byte encoding), and the time between two pieces of data on the bus (i.e. $1800 writes/$DD00 reads) is 8 cycles, so after 8*67 = 536 cycles = 10 transfered bytes we have missed two bits. Getting the timing correct across such a long time becomes very tricky then.

Another problem is the fact that the video chip in the C64 (“VIC-II”) requires 40 cycles for DMA on every 8th line of the visible screen that it sends to the display, completely stopping the CPU, which would mess up all timing. One raster line on the C64 is exactly 63 cycles long, so these CPU stalls (“badlines”) happen every 504 cycles. If we start a transfer of several bytes just after one of these badlines, we have time for a maximum of about 9 bytes ((504-40)/50). Or we could only transfer data while the VIC is outside the visible area, but this is only in 112 of the 312 lines, so we would be wasting about 64% of the processing power. Most fast loaders just turn off the screen, so the VIC doesn’t do these fetches any more, but we don’t want to take this shortcut!

Badlines happen every time the vertical raster location (readable in register $D012 of the VIC) is between 50 and 249 and the the lowest 3 bits reach the value of 3. (Actually, this value is variable and corresponds to the lowest 3 bits in register $D011.) So the first thing to check is whether we are below 50 or above 249 (i.e. between 250 and 311). $D012 only holds the lowest 8 bits of the raster register (the MSB is stored in the MSB of $D011), but just checking for $D012 being below 50 already means that the raster register is between 0-49 or 256-305 – this easier check with some false positives is preferrable to a more compicated but slower check. So if we are in the visible area, we must watch out whenever we are are in a line that ends in “2″, because a badline will happen some time within the next 63 cycles. In every other case, a badline won’t happen within at least 63 cycles, so we are safe to spend our 28 cycles in the receiver code. The following code does this:

wait_raster:
    lda $D012           ; vertical raster position (bits 0-7)
    cmp #50             ; between 0-49 or 256-305?
    bcc wait_raster_end ; yes, so it's safe
    and #$07            ; lowest 3 bits
    cmp #$02            ; are we in the line before a badline?
    beq wait_raster     ; yes, then wait until we are not
wait_raster_end:

If sprites are visible on the screen, this also requires extra DMAs from the VIC, but we assume that there no sprites active. If in doubt, writing 0 into VIC register $D015 makes sure they are all turned off.

Now the actual handshake is rather easy. The protocol is this: At the beginning, both the computer and the drive set their handshake flags to “not ready”. When the drive has data in its buffer and is ready to send a byte, it sends its flag to “ready”. Then the C64 makes sure it is not in danger of a badline and sets its “ready” flag. Just after the transfer of the byte, both devices set their flags to “not ready” again. The drive signals readyness with CLK=0, and the computer does so with both CLK=0 and DATA=0, so the code looks like this:

;-----
; C64 at initialization time
    lda #VIC_OUT | DATA_OUT ; CLK=0 DATA=1
    sta $DD00               ; we're not ready to receive

;-----
; drive at initialization time
    lda #F_CLK_OUT          ; CLK=1 DATA=0
    sta $1800               ; drive code running, we're not ready to send

;-----
; C64 waiting for drive code running
wait_fast:
    bit $DD00
    bvs wait_fast           ; wait for CLK=1, i.e. drive code running

;-----
; drive when it is ready to send (i.e. byte in buffer and converted)
    lda #0                  ; CLK=0 DATA=0
    sta $1800               ; we're ready to send

;-----
; C64 waiting for drive ready to send
wait_byte:
    bit $DD00
    bvc wait_byte           ; wait for CLK=0, i.e. drive ready to send

;-----
; C64 when it is ready to receive (i.e. not in danger of badline)
    lda #VIC_OUT            ; CLK=0 DATA=0
    sta $DD00               ; we're ready, start sending!

;-----
; drive waiting for C64 ready to receive
wait_c64:
    ldx $1800
    bne wait_c64            ; needs all 0

;-----
; C64 after receiving a byte
    lda #VIC_OUT | DATA_OUT ; CLK=0 DATA=1
    sta $DD00               ; not ready any more, don't start sending

;-----
; drive after sending a byte
    jsr $E9AE               ; CLK=1 (use ROM code to opimize for size)

Please note that logic on all $DD00 reads on the computer side looks backwards, because the bits get inverted.

Timing after the Handshake

The send and the receive code have exactly the same timing, but we need to make sure that they also start at the same time. The C64 code cannot start reading data from the bus directly after telling the drive that it is ready to receive, because the drive is testing for the C64′s readiness in this loop:

;-----
; drive waiting for C64 ready to receive
wait_c64:
    ldx $1800
    bne wait_c64            ; needs all 0

The load takes 4 cycles, and the branch 2 or 3, depending on whether it is taken. The actual bus access for the read from $1800 takes place in the third cycle, so in the worst case, the computer signals that its ready exactly the fourth cycle: In this case, the LDX has read the old value and the branch is taken, the LDX reads the value again, gets the right value now, and doesn’t take the branch. So the maximum time until the 1541 reacts is 10 cycles: 1 for the last cycle in the LDX, 3 for the taken branch, 4 for another LDX, and 2 for the final non-taken branch. This is the code that delays for 10 cycles between the ready signalling and the reading of the first 2 bits:

    lda #VIC_OUT ; CLK=0 DATA=0
    sta $DD00    ; we're ready, start sending!
    pha          ; 3 cycles
    pla          ; 4 cycles
    bit $00      ; 3 cycles
    lda $DD00    ; get 2 bits into bits 6&7

Reading Sectors

Now that we have the transfer code for one byte in place, we can easily construct a loop on both sides that repeats the transfer 256 times for a full sector. But we also need code running inside the drive that reads sectors from disk in the first place. The easiest way to do this is use the ROM code. It will happily position the read head for us, wait for the sector to come by, read it, decode the on-disk bit encoding (6-to-4 Group-Code-Recording, GCR) and put it into a buffer:

    lda #TRACK
    sta $06
    lda #SECTOR
    sta $07
    lda #0
    sta $f9     ; buffer at $0300
    cli
    jsr $D586   ; read sector
    sei

The 1541 has 5 buffers, numbered 0 through 4, from $0300-$03FF to $0600-$06FF. The track and sector for buffer 0 are stored in zero page addresses 6 and 7, the ones for buffer one in addresses 8 and 9 and so on. Note that during the whole process of loading data into the C64, we have interrupts disabled (“SEI”), so we need to reenable them while reading from disk for the timers to work properly.

More advanced fastloaders don’t use the ROM code for reading, but implement a more optimized version, achieving another minor speedup. Bigger speedups can be achieved by changing the algorithm of reading completely: Tracks on a 1541 disk are up to 21 sectors, 256 bytes each, but the 1541 RAM is only 2 KB, so it cannot read a whole track into memory. Therefore it reads one sector, transfers it, reads another one and so on. After reading a sector, it needs to be decoded and sent, during which time the disk continues spinning, causing the drive to miss a few sectors. So it would be a bad idea to store files on consecutive sectors, since this would mean it has to wait for a whole turn of the disk (one fifth of a second) for that sector to arrive under the head again.

Instead files are stored in an interleaved fashion, typically with an interleave factor of 4, meaning a file is for example stored on sectors 0, 4, 8, 12 etc. When a fast loader is used, it would typically require a different interleave factor for optimal performance, but unfortunately the interleave factor is a property of the already written disk. A very advanced method of fast loading is therefore to always read the sector that comes by next and transfer it, unless it has been transfered before, until the complete track is in the C64. The C64 then sorts the sectors in the correct order. For smaller files, this does not work too well, since this method always reads and transfers complete tracks.

Even different fast loaders (like Heureka Sprint, used by Turrican and some other Rainbow Arts titles) require the data on disk to be encoded differently, making decoding more efficient. Some copy programs, like “Master Copy” don’t decode the sector data at all – but they can only do this because they write the same encoding, and the actual payload data is never required.

But in order to keep the implementation really small (custom read code is in the order of 600 bytes) let’s stay with the code in ROM.

Uploading the Code into the Drive

Let’s consider both pieces of code on the C64 and the 1541 side finished now, but what’s still missing is code to upload the drive code into the RAM of the 1541 and run it. There are several ways of doing this: The 1541 operating system over the original IEC protocol has a “memory-write” (“M-W”) command, allowing us to upload up to 36 bytes at a time, and a “memory-execute” (“M-E”) command that makes the CPU jump to the address we specify. Our 1541 code is about 100 bytes, which would take about a quarter of a second to upload with the original protocol.

But there is a way to avoid this cost: All code and data in the C64 came originally from disk, so why would we download it to the C64 and upload it to the 1541 again? We can just instruct the 1541 to read a sector and execute it. This can be done with block-read (“B-R”) and “memory-execute”, or with the specialized instruction “block-execute” (“B-E”). Unfortunately, “block-execute” does not work on the concept of buffers, but on the concept of channels which abstract buffers, making this more complex than it would have to be.

A common trick is to upload minimal 6502 code to the drive that reads a sector and jumps to it and execute that. And it’s even possible to avoid the “memory-write” command: When sending the “memory-execute”, we can send trailing bytes, for a command that is up to 42 bytes long. The code would just travel with the “memory-execute” command, and the execution address would point to this very code in the temporary command buffer:

    lda #$0f
    sta $b9   ; secondary address
    sta $b8   ; logical file number
    ldx #cmd
    lda #cmd_end - cmd
    jsr $fdf9 ; filnam
    jsr $f34a ; open
    brk

cmd:
    .byte "M-E"
    .word $0200 + cmd_code - cmd
cmd_code:
    lda #18   ; track 18, sector 18
    sta $08
    sta $09
    lda #1    ; buffer at $0400
    sta $f9
    jsr $d586 ; read sector
    jmp $0400 ; jump to the code we loaded
cmd_end:

The command buffer in the 1541 is located at $0200, so the “memory-execute” jumps to the first byte just after the command itself, at $0205. We choose to store the floppy code on track 18, sector 18: Track 18 is decidated to directory entries, so unless the disk has 144 files on it, it is unlikely all sectors of track 18 are in use. Reading the code from track 18 also means the head does not have to move if we store the C64 loader there, too.

Fitting C64 and Drive Code Into a Single Sector

But there is an even simpler and faster solution: If we manage to fit both the C64 code and the floppy code into a single sector, we don’t have to read another sector, but we can just send a “memory-execute” into the buffer that the block was loaded into:

cmd:
    .byte "M-E"
    .word $0482
cmd_end:

The default buffer is #1 at $0400 in the drive’s memory, so after the start program got loaded into the C64, the sector can still be found at $0400.

The default 1541 file system does not support random file access, therefore there is no central data structure that allows a lookup of the sector number following the current one. Instead, the link to the next track and sector is stored in the first two bytes of every sector, reducing the usable space in a sector to 254 bytes (and making seeks in a file very expensive). So the first byte in a sector is the track (1-35) and the second byte is the sector (0-20) of the following block. If it is the last block of a file, the track number is zero and the sector field contains the number of valid bytes in the block; all bytes afterwards will be ignored and not transfered. This allows files that are not a multiple of 254 bytes in size.

So the trick is to create a file that is about half a sector in size and contains the C64 code, and we store the drive code in the unused half of the sector. So the reason why we always optimized for code size when choosing algorithms before was because we really need to fit everything in 256 bytes!

Header

Now what is the executable file format, you may ask? What are the headers, how are they structured? How much data is used for headers? It is complicated.

The shell of the C64 was Commodore BASIC, a derivative of Microsoft BASIC for 6502. So you would load BASIC programs from disk with the “LOAD” command, you could have them printed on the screen with “LIST” and edit them; and if you wanted to run them, you would type “RUN”. This concept wasn’t really meant for programs not written in BASIC, but it was enough to have a small BASIC header in front of your assembly program, like this:

10 SYS2061

BASIC programs get loaded to $0801, so the machine code is stored directly after this small BASIC header which tells the interpreter to run machine code at 2061 = $080D. But this wastes 12 bytes and requires the user to type “RUN” after the program is loaded.

Autostart

It is much nicer to have the program autostart directly after the “LOAD” command. The trick here is to have the program load not into BASIC RAM, but into a region where it overwrites vectors – it’s basically a buffer exploit! Here is a rough memory map of the C64:

Commonly, autostart programs would overwrite the system vectors at $0300:

Your program would load to $0326, for example, overwriting the CHROUT vector as well as the 5 following vectors, and your code would be loaded into the tape buffer starting at $033C. When loading is finished, the BASIC interpreter wants to print “READY.”, jumping over the CHROUT vector at $0326 and therefore into your code.

The problem with this solution is that we have to preserve the values of some of the vectors between $0328 and $033B, because the original LOAD code in ROM calls the STOP vector to test whether the user pressed the STOP key. So our file would have to contain the original values, not only wasting 12 bytes, but also introducing potential incompatibilities if the user has a cartridge like the Final Cartridge III or the Action Replay VI attached – these devices were practically ROM extensions and hooked some of these vectors to provide improved functionality.

(Actually, overwriting the STOP vector is useful in a different scenario: This way, we can catch execution during the load operation as opposed to after it and continue loading the same file with a replacement bus protocol.)

A different way to gain control after loading is to load into the stack and overwriting the address returned to after the LOAD is finished. The stack on the 6502 is always located between $0100 and $01FF, so if we overwrite this complete area with a value of 2, we would put all “$0202″ vectors on the stack, catching execution as soon as the inner ROM LOAD code returns to its caller. Since the 6502 increments the return address after it fetches it from the stack, our payload would live at $0203, which is still pretty much directly after the stack area. But of course overwriting the complete stack is a waste: Experimentation shows that the one vector on the stack that actually counts is located at $01F8/$01F9.

Laying Out the Code

The problem with the payload starting at $0203 is that we can only use the memory up to $0258 (55 bytes) – this is the buffer for a BASIC input line. Unfortunately, this is not enough, since our code is more like 110 bytes. We can put the payload before the vector we overwrite, i.e. onto the stack. But we must be careful, because the LOAD code in ROM uses some stack, overwriting the area between $01ED to $01F7. So let’s have our code start somewhere in the stack area, going up to $01EC, and put a JMP to the code at $0203 to catch the stack return.

The 11 bytes at $01ED-$01F7 (stack that gets overwritten while loading) and the 9 bytes at $01FA-$0202 (area between the vector on the stack we overwrite and our first instruction at $0203) seems wasted – but not quite. We can use $01FE-$0202 to store our 5 byte “M-E” string, and we just fill all bytes from $01ED to $01FD with “2″. This gives us extra safety that our code will work machines with replacement ROMs or extended ROM routines that use a slightly different stack layout – as long as they don’t use more stack and overwrite our code.

Final Words

Fast loaders and autostart bootloaders have been around for almost as long as the C64. Fast loaders have used the stack trick before, and 26 cycle drive transfer code with the screen turned on has been in use before as well. So what’s really novel about the bootloader described in this article is the combination of the most optimized tricks into a single-block (256 byte) program. That’s the beauty of programming for the C64: Practically everything is implicitly open source, since the best algorithms fit in a few hundred bytes of code, and an experienced C64 hacker can reverse-engineer existing code and incorporate it into his own. That’s how it has always been done.

The Code

Here is the complete code, which can be assembled with the ca65 assembler of the cc65 compiler suite.

TARGET := $0400
TRACK := 18

DATA_OUT := $20 ; bit 5
CLK_OUT  := $10 ; bit 4
VIC_OUT  := $03 ; bits need to be on to keep VIC happy

seccnt = 2

;----------------------------------------------------------------------
; Hack to generate .PRG file with load address as first word
;----------------------------------------------------------------------
.segment "LOADADDR"
.addr *

;----------------------------------------------------------------------
; Send an "M-E" to the 1541 that jumps to floppy code.
; Then receive one block and run it.
; This code lives around $0190.
;----------------------------------------------------------------------
.segment "PART2"
main:
    lda #$0f
    sta $b9
    sta $b8
    ldx #<memory_execute
    ldy #>memory_execute
    lda #memory_execute_end - memory_execute
    jsr $fdf9 ; filnam
    jsr $f34a ; open

    sei
    lda #VIC_OUT | DATA_OUT ; CLK=0 DATA=1
    sta $DD00 ; we're not ready to receive

; wait until floppy code is active
wait_fast:
    bit $DD00
    bvs wait_fast ; wait for CLK=1 (inverted read!)

    lda #sector_table_end - sector_table ; number of sectors
    sta seccnt
    ldy #0
get_rest_loop:
    bit $DD00
    bvc get_rest_loop ; wait for CLK=0 (inverted read!)

; wait for raster
wait_raster:
    lda $D012
    cmp #50
    bcc wait_raster_end
    and #$07
    cmp #$02
    beq wait_raster
wait_raster_end:

    lda #VIC_OUT ; CLK=0 DATA=0
    sta $DD00 ; we're ready, start sending!
    pha ; 3 cycles
    pla ; 4 cycles
    bit $00 ; 3 cycles
    lda $DD00 ; get 2 bits into bits 6&7
    lsr
    lsr ; move down by 2 (bits 4&5)
    eor $DD00 ; get 2 more bits
    lsr
    lsr ; move everything down (bits 2-5)
    eor $DD00; get 2 more bits
    lsr
    lsr ; move everything down (bits 0-5)
    eor $DD00 ; get last 2 bits, now 0-7 are populated

    ldx #VIC_OUT | DATA_OUT ; CLK=0 DATA=1
    stx $DD00 ; not ready any more, don't start sending

selfmod1:
    sta TARGET,y
    iny
    bne get_rest_loop

    inc selfmod1+2
    dec seccnt
    bne get_rest_loop

inf:
    jmp inf

.segment "VECTOR"
; these bytes will be overwritten by the KERNAL stack while loading
; let's set them all to "2" so we have a chance that this will work
; on a modified KERNAL
    .byte 2,2,2,2,2,2,2,2,2,2,2
; This is the vector to the start of the code; RTS will jump to $0203
    .byte 2,2
; These bytes are on top of the return value on the stack. We could use
; them for data; or, fill them with "2" so different versions of KERNAL
; might work
    .byte 2,2,2,2

.segment "CMD"
memory_execute:
     .byte "M-E"
     .word $0480 + 2
memory_execute_end:

;----------------------------------------------------------------------
; Jump to code that receives data.
;----------------------------------------------------------------------
.segment "START"
    jmp main

;----------------------------------------------------------------------
;----------------------------------------------------------------------
; C64 -> Floppy: direct
; Floppy -> C64: inverted
;----------------------------------------------------------------------
;----------------------------------------------------------------------

.segment "FCODE"

F_DATA_OUT := $02
F_CLK_OUT  := $08

sec_index := $05

start1541:
    lda #F_CLK_OUT
    sta $1800 ; fast code is running!

    lda #0 ; sector
    sta sec_index
    sta $f9 ; buffer $0300 for the read
    lda #TRACK
    sta $06
read_loop:
    ldx sec_index
    lda sector_table,x
    inc sec_index
    bmi end
    sta $07
    cli
    jsr $D586       ; read sector
    sei

send_loop:
; we can use $f9 as the byte counter, since we'll return it to 0
; so it holds the correct buffer number "0" when we read the next sector
    ldx $f9
    lda $0300,x

; first encode
    eor #3 ; fix up for receiver side (VIC bank!)
    pha ; save original
    lsr
    lsr
    lsr
    lsr ; get high nybble
    tax ; to X
    ldy enc_tab,x ; super-encoded high nybble in Y
    ldx #0
    stx $1800 ; DATA=0, CLK=0 -> we're ready to send!
    pla
    and #$0F ; lower nybble
    tax
    lda enc_tab,x ; super-encoded low nybble in A
; then wait for C64 to be ready
wait_c64:
    ldx $1800
    bne wait_c64; needs all 0

; then send
    sta $1800
    asl
    and #$0F
    sta $1800
    tya
    nop
    sta $1800
    asl
    and #$0F
    sta $1800

    jsr $E9AE ; CLK=1 10 cycles later

    inc $f9
    bne send_loop
    beq read_loop

end:
    jmp *

enc_tab:
    .byte %1111, %0111, %1101, %0101, %1011, %0011, %1001, %0001
    .byte %1110, %0110, %1100, %0100, %1010, %0010, %1000, %0000

sector_table:
    .byte 0,1,2,3,$FF
sector_table_end:

This is the linker script:

MEMORY {
    # hack to get the load address as the first 2 bytes into the .PRG
    LOADADDR: start = $0188, size = 2;

    # the receive code, filled with $02s that overwrite the top few bytes of
    # the stack and make the KERNAL loader return to $0203
    PART2:    start = $0188, size = $0065, fill = yes, fillval = $FF, file = %O;

    VECTOR:   start = $01ED, size = $0011, fill = yes, fillval = $FF, file = %O;

    CMD:      start = $01FE, size = $0005, fill = yes, fillval = $FF, file = %O;

    # entry point $0203 due to stack overwritten with $02s
    # code that transfers M-E
    START:    start = $0203, size = $0003, fill = yes, fillval = $ff, file = %O;

    FCODE:    start = $482, size = $007E, fill = yes, fillval = $ff, file = %O;
}

SEGMENTS {
    LOADADDR:   load = LOADADDR,    type = ro;
    START:      load = START,       type = ro;
    PART2:      load = PART2,       type = ro;
    CMD:        load = CMD,         type = ro;
    VECTOR:     load = VECTOR,      type = ro;
    FCODE:      load = FCODE,       type = ro;
}

This script for the c1541 tool, which puts the code into a disk image:

format autostart,01
write "start.prg"

And this is the shell script that builds the whole thing:

ca65 start.s &&
ld65 -C start.cfg start.o -o start.prg &&
dd if=/dev/zero of=autostart.d64 bs=256 count=683 &&
c1541 autostart.d64 < c1541script.txt

Note that the c1541 tool creates a file with the whole block on disk, so in practice, the 1541 code will be loaded into the C64 as well, but never used. So the two link bytes of the block would have to be manually changed to decrease its size to achieve maximum speed.

But let us first examine the existing claims of 17, 22 and 30 million.

Jack Tramiel’s numbers

The numbers 22 and 30 million actually come from Commodore founder Jack Tramiel himself. At the “Impact of the Commodore 64: A 25th Anniversary Celebration” in December 2007 at the Computer History Museum, Tramiel claimed that Commodore sold nearly half a million C64s a month until he left the company in 1984, and he extrapolated this to “between 22 and 30 million units” during the lifetime of the C64. Tramiel’s assistant Michael Tomczyk, who left the company around the same time, uses the same 22 million figure in his 1984 book “Home Computer Wars – An Insider’s Account of Commodore and Jack Tramiel”.

Commodore’s Numbers

But these numbers contradict Commodore’s official sales numbers as researched by Marc Walters: The 1993 Annual Report supposedly states that 17 million units had been sold (production was stopped in April 1994, so this should be very close to the final number). Commodore employee Dr. Peter Kittel confirms the 17 million.

Walters quotes Commodore’s 1993 financial details for the sales numbers between 1990 and 1993:

The following figures are from Commodore annual reports:
Fiscal 1990: 700K - 800K (decline begins),
fiscal 1991: 800K (non official 1M)
fiscal 1992: 650K
fiscal 1993: 150K - 200K
1993 Annual Report: 17M total C64, 4.5M C128

Marc Walters’ estimates

Walters also gives his own estimates for 1982 through 1989:

1982: 150K - 300K
1983: 2M
1984: 2M-3M
1985: 2M -3M
1986: 2M -3M
1987: 1M - 2M
1988: 1M - 1.5M
1989: 1M - 1.5M

This data was later picked up by Jeremy Reimer for his Ars Technica article “Total share: 30 years of personal computer market share figures“.

With these numbers, Commodore would have sold between 13.5 and 19 million units. The following graph shows this, with the 17 million figure added as a scaled version of the ranges given:

Putting all reliable data together

This data is quite consistent, but generic sources contradict these steep numbers in the first years:

• At CES 1984: 1 million (floodgab retrobits)
• end of 1984: 3 million (c64-wiki.com)
• end of 1984: 3.5 million (pctimeline.info)
• end of 1986: 6 million (c64-wiki.com)
• end of 1987: 7 million (pctimeline.info)
• end of 1990: 11 million (Commodore Home Computer Museum (NZ))

This data, with Commodore’s own 1990-1993 data added and some of the missing numbers extrapolated, shows a rather flat and consistent sales curve with a single spike in 1984, totalling about 12.5 million units:

In 1984, about 2 to 2.5 million units were sold, which is about 200,000 units per month. There is no way Tramiel’s statement holds true, given the many sources of the early numbers and their consistency. This also falsifies claims of Tramiel’s 22 million and 30 million sold units, which could be approximated by extrapolating the 2.5 million units across a decade – but the existing data shows that the C64 clearly didn’t perform equally well afterwards.

Examining serial numbers

There are two projects that collect C64 serial numbers:

• The C64 Serial Registry by the C64 Preservation Project
• The C64 Inventory

While the former collects lots of details including case badges and board types, the latter contains information like the video standard as well as photos of all serial number stickers. For the following statistics, we only need the C64 Serial Registry.

Commodore 64 computers were produced in at least 11 different factories worldwide with different and not immediately obvious conventions for serial numbers. But all PCBs, of which there were 16 versions, were manufactured in Hong Kong, and most versions were numbered sequentially, starting at 0 for each new version. The serial number could be found on a sticker on the shield of the cartridge port.

The fact that serial numbers are indeed per board version and are reset to zero for every new board can be seen in the following graph, which was created by sorting the serial numbers by board first and then by number:

If the assumption is correct, serial numbers have to increase linearly until they approach the highest serial number of the board version. All boards should have about the same slope. This is true for all board versions except “250425/A” and “250425/B”, as well as the last two, “250469/A” and “250469/A”.

This can be explained by the bias towards machines from North America in the C64 Serial Registry: About one third of the entries in the database are from the US and Canadian market, but a much smaller percentage of units has actually been sold there – the C64 was very strong in Europe. The first, second and fourth of these board types with a much higher slope were all sold exclusively, and the third one predominantly to PAL markets, i.e. outside North America.

(If the slope there is roughly twice as steep, we can estimate NTSC units are overrepresented in the database by a factor of two, meaning that about 1/6 of all C64 were sold in North America.)

These are the 16 different versions and revisions, the year they first appeared in, the number of boards of this kind in the C64 Serial Registry (that have the board serial number field filled), and the maximum serial number observed:

(Note that four of the early versions do not have any easily discoverable serial numbers on them. Also note that the PET 64 and Educator 64 devices, which were basically “326298/A” C64 boards in an all-in-one computer, are also counted, but they sold in very small numbers. The same is true for the ill-fated “250469/B”-based C64GS game console. The portable SX-64 has a different board and is not counted.)

Now we can use the formula for the German Tank Problem to estimate the total number produced for each type of board for which we have the maximum observed serial number:

k is the sample size and m is the highest serial number observed.

For the board types without serial numbers, we can approximate the number of boards produced by scaling the result of board “326298/A” to the number of observed units of the missing ones. Since all boards without serials are from 1982 just like “326298/A”, it is probably not a very bad estimate.

(On the other hand, board “KU-14194HB” has only ever been put into machines produced in Germany and sold in Europe, so because of the bias of the database towards North America, this board type might be underrepresented.)

So according to this estimate, about 12.5 million Commodore 64 computers were produced, which matches the number above.

(By the way, about 6 million of these had the new smaller board “250469/X” with the HMOS chipset, and almost all machines since 1989, which is about 4.5 million, were sold in Europe.)

In the Commodore archive at zimmers.net, there is a collection of GIF images that are scans of the some very interesting technical documents on the TED series, originally provided by Tibor Biczo and published by William Levak and Marko Mäkelä. I sorted the pages and converted them into searchable PDFs that are much nicer to look at:

“TED System Hardware Manual”
(PDF, 48 pages, 7.6 MB)

“TED 7360R0 Preliminary Data Sheet” (Apr 1983)
(PDF, 23 pages, 5.8 MB)

“TED Extra Pages”
(PDF, 5 pages, 1.4 MB)

The “Extra Pages” contain a map of the circuit board, a Plus/4 memory map in German, a TED register map, and a German version of section 4.5.2 of the TED System Hardware Manual.

“Service Manual Model Plus 4 Computer.pdf” (Oct 1984, PN-314001-04)
(PDF, 25 pages, 4.9 MB)

The service manual is also taken from zimmers.net.

Hint:

• White t-shirt: get sued.
• Black t-shirt: do not get sued.

Oh, and Sony also fails, among other things, at the Spanish naming system.

In case you haven’t watched the video yet, you should do so now: Console Hacking 2010. I have a short cameo, repeating my age-old point that systems should be open, otherwise hackers will open them.

As it turns out, there are several undocumented instructions implemented in the Final Cartridge III.

Filtered Directory

DOS"$<filter>"

The DOS”$” command passes all characters following the “$” to the disk drive, allowing the user to specify filters, like this:

DOS"$A*" :REM SHOW ALL FILES THAT START WITH "A"

This feature is not available for the “@” command in the monitor.

Fast Format

DOS"F:NAME,ID"

The 26 second fast format known from the “DESKTOP” GUI is also available from the command line. Note that this also works with the “@” command in the monitor. If the ID is omitted, this only overwrites BAM and directory, just like the “N” command.

Disk Rename

DOS"D:NAME,ID

This commands renames the disk without erasing it. The ID can be up to 5 characters, so the default “2A” can be overwritten.

FC III ROM Banking

B<0..3>
B

B, followed by a digit between 0 to 3, in the monitor enables the view of the ROMs of the Final Cartridge III. The specified ROM bank will be visible between $8000 and $BFFF. B without a parameter switches the ROM back off.

The following commands in the machine language monitor can be used to dump the complete ROM of an FC3 to disk:

B 0
T 8000 BFFF 8000
S "B0",08,8000,C000
B 1
T 8000 BFFF 8000
S "B1",08,8000,C000
B 2
T 8000 BFFF 8000
S "B2",08,8000,C000
B 3
T 8000 BFFF 8000
S "B3",08,8000,C000

A high-quality MP4/H.264 video file of the presentation can be downloaded here.

P.S.: If you enjoyed this, you might also like my “Ultimate Commodore 64 Talk”

Update: The video recording is now available.

I managed to acquire nine different files (I own several licenses for this episode, and I downloaded without uploading). Some of these have non-english audio tracks and some have hard subtitles, but let’s concentrate on the quality of the deinterlacing. The following list is already sorted by overall quality, first by interlacing quality, then by resolution, then by data rate:

Files #1, #2 and #3 show heavy blending that goes beyond just blending the two interlaced frames per five frames. It is likely these files were encoded form a PAL source that was improperly converted from NTSC.

File #4 is detelecined (24 fps), but whenever the telecine pattern was not consistently PPPII (“Robot Hell” pan, end credits), the algorithm reverted to blending the two fields. It is likely this source was encoded from the NTSC DVD.

Files #6, #7, #8 and #9 all seem to be encoded from the same PAL source that was already deinterlaced properly, i.e. a detelecine was done to recover the 24 fps video, and then it was sped up by ~4% to get a 25 fps video. The detelecine is almost perfect: In the end credits, the algorithm properly reconstructed all frames without ever having to blend, but the “Robot Hell” pan is missing the six frames that that only existed as one field.

File #5 is interesting: It is 30 fps, so it has a duplicate frame after every fifth frame, but other than that, it was converted by the same high-quality detelecine as #6 through #9. Since I suspect that the #6-#9 detelecine was done professionally for the PAL DVD, it is weird to see the practically the same result (6 missing frames in “Robot Hell”, but perfect end credits etc.) with the NTSC frame rate here. It almost looks like someone took a PAL DVD (or one of the files #6-#9) and duplicated frames to get an NTSC-compatible signal.

Bittorent Summary

A rule of thumb is that an encoding found on BitTorrent is as good as its source. For those that had a blended source (#1-#3), nothing could fix it. For those that had an excellent progressive source (#6-#9), there was little to be done wrong. The one that had the original interlaced US master as a source did an okay job of deinterlacing.

Also: The PAL DVDs seem to be very high quality.

Comparison to properly licensed sources

Now how do these scene rips compare to legit internet video providers? Well, as my previous article stated, the files on Hulu, Netflix and iTunes have the deinterlacing done wrong, leading to visible and unnecessary degradations of the vertical resolution in some (Netflix, iTunes) or all (Hulu) of the video – but this is arguably still better than the blending of BitTorrent files #1-3. Amazon Video on Demand did an okay detelecine job, although inferior to BitTorrent file #4: On complicated scenes, Amazon halved the resolution, while file #4 did blending. The Microsoft Zune store did a perfect detelecine, which is even better than the one in BitTorrent files #4-9, since it did not miss the 6 frames in the “Robot Hell” pan, but otherwise performs as well as the PAL DVD.

So here are the final rankings of the different sources/files/enodings for the episode “Hell Is Other Robots” of Futurama:

0. NTSC DVD: original broadcast master, 720×480, interlaced, but with the full potential to be perfectly deinterlaced! ;-)

1. Microsoft Zune: perfect detelecine
2. PAL DVD: almost perfect detelecine
3. BitTorrent files #6-#9: almost perfect detelecine, like PAL DVD
4. BitTorrent file #4: okay detelecine
5. Amazon Video on Demand: okay detelecine, judder
6. iTunes, Netflix: buggy deinterlacing, judder
7. BitTorrent files #1-3: horrible blending
8. Hulu: Consistenly halved vertical resolution

So unless you want to do the deinterlacing yourself, the Zune version is the best choice. Which is, unless you actually want to play the video on the devices you care about, in which case you should get the effectively not copy-protected PAL DVDs.

If you have dealt with video formats before, you probably know about interlacing, a 1930s trick to achieve both high spatial and temporal resolution at half the (analog) data rate: In NTSC countries, there are 60 fields per second (PAL: 50), and every field is half the vertical resolution of a full frame. When film footage at 24 frames per second has to be played at 30 fps (NTSC), every frame has to be shown 1.25 times – in other words, every fourth frame has to be shown twice. This introduces jerky motion (judder), but it can be improved by using the 60 Hz temporal resolution: Frame A gets shown for 2 fields, frame B for 3 fields, frame C for 2 fields, and so on. This way, every source frame gets shown for 2.5 fields, i.e. 1.25 frames – this method is called a telecine 2:3 pulldown.

A lot of TV material is produced at 24 fps and telecined, for several reasons: Standard movie cameras can be used instead of TV cameras, 24 fps can be converted to 25 fps PAL more easily than 30 fps NTSC, and for cartoons, this means that only 24 (or 12) frames have to be drawn for every second.

Unfortunately, interlacing only works with ancient CRT TVs – modern LCD screens can only show progressive video. And while DVDs are specified to encode interlaced video, more modern formats like MPEG-4/H.264 and VC-1 usually carry progressive data. So when playing DVDs, the DVD player or the TV have to deal with the interlacing problem, and in case of modern file formats, it’s the job of the converter/encoder.

The naive way of converting an interlaced source to progressive is to combine every two fields into a frame. This works great if the original source material was 30 fps progressive (which is rare for NTSC but common for PAL), but for telecined video, since two out of every six frames are combined from two different fields, this leads to ugly combing effects.

If the source material was 24 fps, an inverse telecine can be done, recovering the original 24 frames per second. Unfortunately, it is not always this easy, since interlaced video may switch between methods, and sometimes use different methods at the same time, e.g. overlaying 30 fps interlaced captions on top of a 24 fps telecined picture, or compositing two telecined streams with a different phase. “Star Trek: The Next Generation” is a famous offender in this category – just single-step through the title…

In the following paragraphs, let us look at an episode of Futurama and how the deinterlacing was done by the different providers of the show. Futurama was produced in 24 fps and telecined. Some of the editing seems to have been done on the resulting interlaced video, so the telecine pattern is not 100% consistent.

NTSC DVD

The NTSC DVD is basically just an MPEG-2-compressed version of the US CCIR 601 broadcast master. It encodes 720×480 anamorphic pixels (which can be displayed as 640×480 or 720×540) and has all the original interlacing intact. This is a frame at 640×480 and properly inverse telecined:

Hulu

Hulu (480p version) took the original image without doing any cropping on the sides. You can clearly see this picture is only half the vertical resolution, meaning one of the fields got discarded. It seems this was Hulu’s deinterlacing strategy, since throughout the complete video, everything is half the vertical resolution, whether there is motion or not. This also keeps the video at 30 fps, and effectively shows every fourth frame twice, introducing stronger judder.

iTunes

iTunes crops the picture to get rid of the black pixels in the overscan area and scales it to 640×480. They run a full-blown 60 Hz deinterlace filter on the video. Such a filter is meant to take a live television signal as an input, with a temporal resolution of 60 Hz. While this looks fine on frames with no or little motion, vertical resolution is halved as soon as there is motion. Basically, it is the wrong filter. Like Hulu, iTunes preserves the 30 fps, introducing a stronger judder. (The video encoding is H.264 at 1500 kbit/sec.)

Netflix

Netflix seems to do the same as iTunes – maybe they even got the data from iTunes? The image is cropped and scaled to 640×480, they run a deinterlace-filter and retain the 30 fps, leading to halved resolution when there is motion, and stronger judder.

Amazon Video on Demand

Amazon Video on Demand with its horribly inconvenient Unbox Player (Windows only, requires 1 GB of extra downloads and two reboots) did a better job. Like Netflix and iTunes, they cropped the picture and scaled it to 640×480, but they actually did a real inverse telecine. In some segments (like the end credits), the algorithm failed because of inconsistencies of the original telecine, so it reverted to half the vertical resolution. And like the others, Amazon also encodes at 30 fps, i.e. judder. (The video encoding is VC-1 at 2600 kbit/sec.)

Zune

Microsoft’s Zune Store provides a cropped video at 640×480 at the original 24 fps and with a bitrate of 1500 kbit/sec (VC-1). Looking through it frame by frame reveals that they used a brilliant detelecine/deinterlace algorithm. On the DVD, the panning at the beginning of the “Robot Hell” song is very tricky: It breaks the standard telecine pattern (PPPIIPPPII becomes PPPIPPPI), it seems every fifth frame was removed.

The pan consists of a pattern of three progressive frames, and then one interlaced frame, which is composed of the previous frame and the current frame. Consequently, every fourth frame has half its resolution wasted by the repeated lines of the previous frame, i.e. every fourth frame only exists at half resolution in the DVD master material.

Hulu discards half the vertical resolution for every frame anyway, and the deinterlacing algorithms of iTunes and Netflix discard half the resolution whenever there is motion. The Amazon algorithm does a good job when the telecine pattern is correct, but in this case, it gets confused and encodes all frames of the pan in half resolution. The Zune algorithm does a brilliant job here: The progressive frames stay at full resolution, and it extracts the half-resolution picture out of every fourth frame:

This is the fourth picture at full size – you can see half the vertical resolution is missing (it was never there in the first place!), but the algorithm did a very good interpolation job:

The Zune video is almost perfect. It recombines all fields correctly and recovers all single fields, scaling them up so that it’s hardly visible there is information missing. If you ignore the 720 vs. 640 horizontal pixels, the resulting 24 fps video contains all information of the DVD version, but with all interlacing removed, and with zero judder. Too bad it’s not H.264, but DRMed and only plays on Windows (XP+), Zune and Windows Phone 7.

Summary

Note: H.264 and VC-1 compress significantly better than MPEG-2; a rule of thumb is to divide the MPEG-2 bitrate by 2.3 to get a comparable H.264/VC-1 bitrate. So the Amazon bitrate is fine and the video is about the same quality (sharp picture, no compression artefacts) as the DVD, but the iTunes and Zune versions are not (artifacts can be seen on single frames).

It is scary how little effort seems to be going into video conversion/encoding at major players like iTunes, Netflix and Hulu. Amazon did a kind of okay job converting the source material properly, and only Microsoft did an excellent job. The NTSC DVDs still give you the maximum quality – but of course, if you watch them on an LCD, the burden of deinterlacing is on your side. Handbrake with “detelecine” (for the bulk of it) and “decomb” (for exceptions) turned on, and with a target framerate of “same as source” will generate a rather good MP4 video similar to Amazon’s, but without the judder.

Are there any stores I missed? Can someone check the PAL DVD as well as digital PAL and NTSC broadcasts? What is the magical detelecine/deinterlace program Microsoft uses?

See also: Comparing Bittorrent Files of Interlaced TV Shows

Between October 2003 and January 2005, the Xbox Linux Project asked all visitors to their website to enter their Xbox serial numbers, date and country of manufacture, ROM version, hard disk and DVD drive brand and other properties, and gathered more than 14,000 entries. The original idea was to find a rule to deduce the hard disk and DVD drive types in an Xbox by only looking at the serial number, which was visible through the unopened packaging.

The serial sticker on an Xbox looks like this:

MFG. DATE  2002-03-03
SERIAL NO. 1166356 20903

After looking at several serial numbers, it was already clear that the last two digits (“03″ in my example) are the location of manufacture: 02 is Mexico, 03 is Hungary, 05 is China and 06 is Taiwan. The three digits before (“209″ in my example) are the one-digit year (“2″ for “2002″) and the two-digit calender week (“09″ for around the first week of March).

Now we want to find out how many devices were manufactured. A first approximation is to look at the manufacturing dates of all Xboxes in our database.

This gives us an idea when production was ramped up (in 2001 and 2002 in November, and in 2003 in August, September and October), but the statistics don’t give us absolute numbers, and they are biased towards older devices (newer devices are not entered yet, and visitors of our site tend to be early adopters).

But what about these first seven digits of the serial number? Shouldn’t these be actual “serial” numbers? Let’s look at all devices from August 2003 and sort the first seven digits by manufacturing date:

This does not look like a serial number. But all numbers are > 1,000,000, which implies that the first digit has a special meaning and is not part of the number. Let’s look at distribution of the first digit:

The first digit seems to be the number of the assembly line in the factory! So let’s look at the remaining 6 digits again:

This looks a lot better! But there are several things interleaved in this chart – because the serial numbers are of course counted independently in every factory. If we filter just all numbers form the Chinese factory, we get this:

We can see serial numbers are counted up every week, but we still see all assembly lines interleaved here, and the different lines don’t reset at the same time. Here is line 6 all by itself:

Looks almost perfect, if we assume the wild shots are caused by typos. Here is a manually fixed version of it:

Voilà! Serial numbers that count up monotonically and get reset on every Sunday.

By inspection of the graph, we can estimate that assembly line 6 of the factory in China produced about 275,000 devices per week in week 33 (mid August) of 2003. This works well, because we have so many samples; but for other weeks, we have as few as five. This is the formula for the German Tank Problem:

k is the sample size and m s the highest serial number observed.

The estimate of Xboxes produced by assembly line 6 in China in week 33 of 2003 is therefore 285,269. Applying this to every assembly line of every factory and every week, it should be easy to get great statistics on the productivity of the different lines and factories, as well as a very good estimate of the total number of devices produced. …and this is where you come in!

The Data

You want to do your own statistics? Here is the raw data:

xbox_serials.csv (2.5 MB)

It is a comma-separated-value file with the following columns:

Please note that people were able to fill some fields with arbitraty data, so they might not necessarily be in exactly the specified form. There are also lots of typos in the serial numbers and the month and day fields in the data fields have been mixed up sometimes. You probably want to run a script over the data first that sanitizes some of the input, e.g. removes dashes and spaces from serial numbers etc.

Here are some ideas on what you might want to find out:

1. Is there a better formula to estimate the number of Xboxes produced per week on a certain assembly line?
2. What day does a week start with? Does the factory produce Xboxes on Sundays? Do they produce just as many? Is it different in the respective countries?
3. How many Xboxes were produced per assembly line, per week and per factory?
4. Are all assembly lines in a certain factory just as productive?
5. Are all factories just as productive (per assembly line)?
6. Did productivity go up over time? Did it hit a maximum?
7. How many Xboxes were produced total?
8. Does an assembly line in a certain factory use all the same flash chips, hard drives and DVD drives in a certain week?
9. When did an assembly line in a certan factory switch between board revisions?
10. How long does it take an assembly line to be reconfigured for a different board revision?
11. When did factories open/close? When did assembly lines get created and torn down in certain factories? Is there a correlation? Did assembly lines get migrated between factories? How long does this take?
12. How long does it take on average for an Xbox from manufacuring to when it’s bought, per country? Does it change over the years?
13. Which factories serve which countries? Did it change?
14. How do ROM version, HD software version, motherboard version and video encoder brand correlate to each other?
15. Which countries have PAL, which have NTSC?
16. Where were the non-black Xboxes made?
17. What percentage of Xboxes has a Philips, a Samsung or a Thomson DVD drive?
18. What is the distribution of hard drive types?
19. Some people claim they have a 20 GB hard drive. How credible is this?
20. When and at which factories were certain DVD and HD types introduced?
21. Over time, how did the distribution of DVD and HD types change?
22. What is the distribution of flash chips, how did it change, and how does it correlate to factories?
23. Is there enough data to make statements about the refurbishment process (search for “refurb” in comments)?
24. What percentage of people misses a digit when trying to type in 12 digits?
25. What percentage of people replaced digits of the serial number with an ‘X’ or a ‘*’? What percentage of these chose the right digits to properly anonymize their serial numbers?
26. Any more interesting observations you can come up with?

Please share your ideas as well as your results (plus source code of your scripts, please)! If you know any statistics teachers looking for a large real-world data set and an interesting set of problems, feel free to refer them to this site! :-)

I’m sure all users will immediately associate a Sony 3.5″ Floppy Disk with “save”. It’s not like the stock icon library also had an OK button.

Wouldn’t it be nice if a modern i386/x86_64 CPU started at least in 32 bit protected mode? Can’t they make a legacy-free CPU that does not support 16 bit mode at all? Such a CPU exists, well, existed. It’s the 1989-2001 Intel 80376, an embedded version of the Intel i386.

The datasheet describes all the interesting differences. The 80376 does not support any 16 bit mode, so the “D” bit in segment descriptors must be set to 1 (page 25), forcing 32 bit code and data segments. 286-style descriptors are not supported either (page 27). (The 0×66 and 0×67 opcode prefixes still exists, so code can work on 16 bit registers and generate 16 bit addresses (page 14), just like an i386 in 32 bit mode.)

Since the CPU does not support 16 bit modes, it cannot do real mode, so CR0.PE is always 1. Consequently, a 80376 starts up in 32 bit protected mode, but otherwise, startup is just like on the i386 (page 19): EIP is 0x0000FFF0, CS is 0xF000, CS.BASE is 0xFFFF0000, CS.LIMIT is 0xFFFF, and the other segment registers are 0×0000, with a base of 0×00000000 and a limit of 0xFFFF. No GDT is set up, and in order to get the system into a sane state, loading a GDT and reloading the segment registers is still necessary. Too bad they didn’t set all bases to 0, all limits to 0xFFFFFFFF and EIP to 0xFFFFFFF0.

The 80376 is designed to be forward-compatible with the i386, so unsupported features are documented as “reserved” or “must be 0/1″, and legacy properties like the garbled segment descriptors are unchanged. All (properly written) 80376 software should also run on an i386 (page 1) – except for the first few startup instructions of course. Intel provides the following code sequence (page 20) that is to be executed directly after RESET to distinguish between the 80376 and the i386:

smsw bx
test bl, 1
jnz is_80376

This tests for CR0.PE, which is hardcoded to 1 on the 80376 and is 0 on RESET on an i386. The three instructions are bitness agnostic, i.e. the encoding is identical in 16 and 32 bit mode.

Sounds like the perfect CPU? Well, here comes the catch: The 80376 doesn’t do paging. CR2 and CR3 don’t exist (it is undocumented whether accessing them causes an exception), CR0.PG is hardcoded to 0 (page 8) and the #PF exception does not exist (page 17). A man can dream though… a man can dream.

There are a lot of web-based computer emulators out there for ancient machines – the Commodore 64 and MSX home computers or the more exotic Space Invaders arcade machines. Such emulators are nice to play with but they are incomplete – they lack an Input/Output subsystem.

Emu8080 is the first known Javascript-based emulator which adds a floppy disk system, a fast paper tape reader/writer, a line printer and a VT100 terminal emulator to the mix. Modern web browsers offer a local WebSQL database, which is used to implement block storage devices. Drag-and-Drop is used to mount a desktop file onto the virtual tape device. Together with CPU and RAM emulation, you have a complete machine inside your web browser…

Want to try out? Use Chrome6+ (or Safari5) and visit http://www.tramm.li/i8080

Now you are working inside a classical machine monitor for an 8080 microcomputer from the 70′s. Available commands are:

• m to modify memory
• d to dump memory on the screen
• l to disassemble a program (in Z80 Syntax)
• g to start execution
• <Enter> to perform a single step
• x to show and modify CPU registers
• h for help

So far this is pretty normal machine emulation.

The first important command is “r”. Without any parameters, it lists the available files on the tramm.li server. “r file” reads an Intel HEX file into memory, for example “r basic” will load the well-known Microsoft 8K BASIC interpreter for the Intel 8080.

But as already mentioned, a disk subsystem is also available. The first step in using it is to either insert a pre-formatted disk or to format an empty disk. To insert a pre-formatted CP/M disk, issue a “r 0 cpma” command.

This command expects the image of an 8-inch IBM formatted SS/SD diskette and writes it sector-wise into the browser-local WebSQL database. This needs to be done only once, causing the disk to now be loaded into your browser as Emu8080 drive 0. With the “b” command, the boot sector is loaded into “main memory”, starting at address 0. Now issue a “g” command to start execution. Ta da!, CP/M 2.2 has been loaded and started!

To go back to the monitor, you have two choices: Ctrl-. or via the “bye” executable.

Emu8080 supports four drives, so you can either format the other drives (“F” command) or search for other images on the internet and load them yourself. But how do we mount these drives? The “dsk” commands comes to rescue. It opens a new window, showing the current status of each drive. Every disk is also a drop-area, so you can mount disk images per drag-and-drop from your desktop into the emulator. Technically the FileReader API of Javascript is used, and this API is currently (November 2010) implemented only by Chrome (or Opera). Yes, you do not need the server anymore to transport data into a Javascript application.

Now you can mount disks and boot CP/M. You can edit files with ED.COM or Wordmaster, or write programs in 8080 assembler. But how to get the modified disk images out of the emulator again? The “dsk [n]” commands opens a new window, which allows to post the binary disk image to an arbitrary web server, e.g. localhost. (btw: there is no FileWriter API in HTML5). Just change the target URL and the form will post it where ever you want.

Sometimes mounting and posting whole images is overkill, transmitting a single file into the CP/M machine or getting it out may be all you want to do. And here comes the emulated paper tape device to rescue. Just drag a file onto the terminal’s main window and it will be mounted. Inside CP/M, just use the PIP command: “pip file.txt=rdr:” and you will have the tape’s content in FILE.TXT. Please keep in mind that CP/M is not 8-bit clean.

To get a single file out of the emulator, the paper tape puncher is used. Inside CP/M just use PIP again: “pip ptp:=rew.asm” to punch the file out. Then enter the monitor again (Ctrl-. or “bye”) and use the “ptp” command, which opens a window, where you either post the tape content to an arbitrary web server or simply copy-paste the content.

The final device is a line printer. It just opens a separate window where every character is shown. No escape sequences are implemented – therefore no bold or underlined characters.

In the unlikely case that the user has no clue about CP/M and its commands, the emulator includes a PDF of the original documentation by Digital Research.

Now, lets take a short look into the technical details:

1. WebSQL: The emulator uses the browser local SQL DB as block storage for the four disk drives. The storage is persistent and writable.
2. Drag-and-Drop / FileReader API: The emulator uses drag-and-drop and the FileReader API to read paper tape or disc images from your local machine.
3. HTML5 manifest: The emulator supports the browser local database and browser local file reading. To make it also runnable without an active internet connection, it is built as a HTML 5 App by providing an emu8080.manifest file. This file tells the browser which resources (HTML, JS, CSS, PNG, HEX, CPM, PDF files) must be cached. This means that if you bookmark http://www.tramm.li/i8080/emu8080.html, you can start the emulator and access the disk drives even without an internet connection — just like a local application.
4. ShellInABox: Without the fabulous VT100 emulation of ShellInABox, this emulator would not have been possible. The provided example of a BASIC interpreter was the starting point for the 8080 emulator.
5. z80pack: The C based implementation of a Z80 machine was the basis for the IO-subsystem implementation, the custom BIOS, and the boot disk image. The trick for reducing host CPU cycles in tight IO-Loops (eg. when CP/M is waiting for a key press) was taken from this package.
6. js8080: The Space Invaders emulator js8080 gifted the core CPU emulation.

One last word on performance. On a usual x86 processor the emulator performs like a 2 MHz 8080. With the monitor command “instr” you can tune the performance, by increasing the number of executed 8080 instructions per Javascript timeslice. With today’s hardware, you can expect the performance of a 8 MHz CPU (which was never available as real silicon).

And for Microsoft BASIC fans, try “r basic” and “g” afterwards instead of booting CP/M – welcome to 8K BASIC. Use “SAVE” to save your programs on the paper tape :-) and “LOAD” to read saved programs.

Neozeed provided the Zork adventure game disk image.

And now — happy hacking.

• http://www.tramm.li/i8080/
• http://www.tramm.li/i8080/emu8080.html

Other links:

• Neozeed blogged about the emulator, he also provides a very clear Howto, please take a look at: http://virtuallyfun.blogspot.com/2010/10/cpm-zork-in-java-script.html
• Emu8080 is also mentioned on the Z80 Info Pages (many thanks to Gaby from gaby.de for the reference!): http://www.z80.info/z80emu.htm#EMU_CPU_VAR

If you want to learn about the internals of modern filesystems, you can either read up on theory (e.g. Dominic Giampaolo’s excellent free book Practical File System Design), or you can dissect one using a tool like fileXray, which

• allows you to examine data structures on your Mac OS X HFS+ disk, like the volume header, the journal, regular and special files, etc., down to the B-tree level
• gives you insight into statistics like fragmentation and hot file clustering
• …
• lets you find out where all these deleted files really go, and what forensic analysis can tell someone about your disks!

You can only enter years from 1981 to 1995. That’s a span of 15 years – why? And what happens if the clock runs past the end of 1995?

Well, it wraps around to 1 Jan 1980.

But why does it not allow entering 1980 then? That’s why:

Whenever the clock is set to 1980, it thinks the clock is not set up properly. So it is a 4 bit counter. Too bad, a 5 bit counter could have made it into 2011, and we all know that’s way more than ever needed.

So now it fills me with joy that Ahmad Hawwash managed to get standalone Commodore BASIC into the App Store! His “Hand BASIC – CBM Flavor” is free of charge, runs on iPhone/iPod touch and iPad, and is based on pagetable.com’s Open Source cbmbasic project, a recompiled version of the original Commodore 64 binary, so the BASIC interpreter is itself not interpreted, but runs natively and at full speed, which is in the order of 500 times faster than on a C64.

“Hand BASIC” has LOAD/SAVE support and comes with several demo programs – just type LOAD"$",8 and LIST to see them and LOAD"NAME",8 and RUN to run them. Type the (nonstandard/added) HIDE keyword to hide the keyboard.

What would be very interesting now:

• Some cool BASIC programs that run in here – games, maybe?
• A compiler backend that produces Commodore BASIC code, so I can run any code on the iPhone through this – with a 38911 byte RAM limitation, of course. (Actually, a program is free to set the TOPMEM pointer higher, allowing up to 62 KB of RAM for code and variables.)

Any other ideas? :-)

The Specification

Let’s revisit the documented part first. The 6502 knows three vectors at the top of its address space:

• On a RESET, the CPU loads the vector from $FFFC/$FFFD into the program counter and continues fetching instructions from there.
• On an NMI, the CPU pushes the low byte and the high byte of the program counter as well as the processor status onto the stack, disables interrupts and loads the vector from $FFFA/$FFFB into the program counter and continues fetching instructions from there.
• On an IRQ, the CPU does the same as in the NMI case, but uses the vector at $FFFE/$FFFF.
• On a BRK instruction, the CPU does the same as in the IRQ case, but sets bit #4 (B flag) in the copy of the status register that is saved on the stack.

The four operations are very similar, they only differ in the location of the vector, whether they actually push data onto the stack, and whether they set the B flag.

BRK

Ignoring opcode fetches, the PLA ROM defines the following cycles of the BRK instruction (6502 Programming Manual, page 131):

• store PC(hi)
• store PC(lo)
• store P
• fetch PC(lo) from $FFFE
• fetch PC(hi) from $FFFF

IRQ

An IRQ does basically the same thing as a BRK, but it clears the B flag in the pushed status byte. The CPU goes through the same sequence of cycles as in the BRK case, which is done like this:

If there is an IRQ pending and the current instruction has just finished, the interrupt logic in the 6502 forces the instruction register (“IR”) to “0″, so instead of executing the next instruction, the PLA will decode the instruction with the opcode 0×00 – which is BRK! Of course it has to kick in a few cycles later again to make sure a B value of 0 is pushed, but otherwise, it’s just the BRK instruction executing.

NMI

Not surprisingly, NMI is done the same way: “0″ is injected into the instruction stream, but this time, some extra logic makes sure that the addresses $FFFA/$FFFB are put onto the address bus when fetching the vector.

RESET

RESET also runs through the same sequence, but it is the most different of the four cases, since it does not write the current PC and status onto the stack – but this was hacked trivially: The bus cycles exist, but the read/write line is not set to “write”, but “read” instead. The following trace was created with the transistor data from the Visual 6502 project and shows the first nine cycles after letting go of RESET:

#0 AB:00FF D:00 R/W:1 PC:00FF A:AA X:00 Y:00 SP:00 P:02 IR:00  READ $00FF = $00

Cycle 0: When a 6502 is turned on, the stack pointer is initialized with zero. The BRK/IRQ/NMI/RESET sequence pulls the instruction register (IR) to 0.

#1 AB:00FF D:00 R/W:1 PC:00FF A:AA X:00 Y:00 SP:00 P:02 IR:00  READ $00FF = $00
#2 AB:00FF D:00 R/W:1 PC:00FF A:AA X:00 Y:00 SP:00 P:02 IR:00  READ $00FF = $00
#3 AB:0100 D:00 R/W:1 PC:00FF A:AA X:00 Y:00 SP:00 P:02 IR:00  READ $0100 = $00

Cycle 3: The first stack access happens at address $0100 – a push first stores the value at $0100 + SP, then decrements SP. In the BRK/IRQ/NMI case, this would have stored the high-byte of the PC. But for RESET, it is a read cycle, not a write cycle, and the result is discarded.

#4 AB:01FF D:00 R/W:1 PC:00FF A:AA X:00 Y:00 SP:00 P:02 IR:00  READ $01FF = $00

Cycle 4: SP is now 0xFF (even if the internal state does not reflect that), so the second stack access (which would have been the low-byte of PC) targets 0x01FF. Again, the result is discarded, and SP decremented.

#5 AB:01FE D:00 R/W:1 PC:00FF A:AA X:00 Y:00 SP:00 P:02 IR:00  READ $01FE = $00

Cycle 5: SP is now 0xFE, and the third stack access, (the status register) happens at 0x01FE. SP is decremented again.

#6 AB:FFFC D:E2 R/W:1 PC:00FF A:AA X:00 Y:00 SP:FD P:06 IR:00  READ $FFFC = $E2

Cycle 6: The internal state of the CPU now shows that SP is 0xFD, because it got decremented 3 times for the three fake push operations. The low-byte of the vector is read.

#7 AB:FFFD D:FC R/W:1 PC:00FF A:AA X:00 Y:00 SP:FD P:16 IR:00  READ $FFFD = $FC

Cycle 7: The high-byte of the vector is read.

#8 AB:FCE2 D:A2 R/W:1 PC:FCE2 A:AA X:00 Y:00 SP:FD P:16 IR:00  READ $FCE2 = $A2

Cycle 8: The first actual instruction is fetched.

Since RESET is not timing critical, it doesn’t matter whether a few cycles are wasted by doing the fake stack cycles.

Simon C got my KIM-1 working again, which has a 6502 from week 51 of 1975. There are 512 possible inputs to ROR (8 bit A plus 1 bit C; assuming it doesn’t have dependencies on other registers), and roughly two bytes of output: the 8 bit result and the processor status (flags) register. We ran the following programs on the KIM-1 – note that we had to split the task into several programs, because the KIM-1 doesn’t have enough RAM to hold all results.

Program 1a: for A=00..FF, with C=0, execute “ROR A”, save result into array

.C:0200   A2 00      LDX #$00
.C:0202   8A         TXA
.C:0203   18         CLC
.C:0204   6A         ROR A
.C:0205   9D 00 03   STA $0300,X
.C:0208   E8         INX
.C:0209   D0 F7      BNE $0202
.C:020B   00         BRK

Program 1b: for A=00..FF, with C=1, execute “ROR A”, save result into array

.C:0200   A2 00      LDX #$00
.C:0202   8A         TXA
.C:0203   38         SEC
.C:0204   6A         ROR A
.C:0205   9D 00 03   STA $0300,X
.C:0208   E8         INX
.C:0209   D0 F7      BNE $0202
.C:020B   00         BRK

Program 2a: for A=00..FF, with C=0, execute “ROR A”, save flags into array

.C:0200   A2 00      LDX #$00
.C:0202   8A         TXA
.C:0203   38         SEC
.C:0204   6A         ROR A
.C:0205   08         PHP
.C:0206   68         PLA
.C:0207   9D 00 03   STA $0300,X
.C:020a   E8         INX
.C:020b   D0 F5      BNE $0202
.C:020d   00         BRK

Program 2b: for A=00..FF, with C=1, execute “ROR A”, save flags into array

.C:0200   A2 00      LDX #$00
.C:0202   8A         TXA
.C:0203   38         SEC
.C:0204   6A         ROR A
.C:0205   08         PHP
.C:0206   68         PLA
.C:0207   9D 00 03   STA $0300,X
.C:020a   E8         INX
.C:020b   D0 F5      BNE $0202
.C:020d   00         BRK

These are the results:

Program 1a and 1b (result with C=0 and C=1) produced the same output!

00 -> 00
01 -> 02
02 -> 04
03 -> 06
04 -> 08
05 -> 0A
[...]
FF -> FE

This is a shift left (!!!) of the input value; and it is independent of the carry flag – just like ASL.

Program 2a (status when C=0) produced the following output:

00:     7E (Z=1, N=0, C=0)
01..3F: 7C (Z=0, N=0, C=0)
40..7F: FC (Z=0, N=1, C=0)
80:     7E (Z=1, N=0, C=0)
81..BF: 7C (Z=0, N=0, C=0)
C0..FF: FC (Z=0, N=1, C=0)

Program 2b (status when C=1) produced the following output:

00:     7F (Z=1, N=0, C=1)
01..3F: 7D (Z=0, N=0, C=1)
40..7F: FD (Z=0, N=1, C=1)
80:     7F (Z=1, N=0, C=1)
81..BF: 7D (Z=0, N=0, C=1)
C0..FF: FD (Z=0, N=1, C=1)

These are the correct flags corresponding to the incorrect results in A. The carry flag is the same as the input carry flag, i.e. it is unmodified.

Our preliminary summary is this:

  ROR          Broken ROR on pre-June '76 CPU (Memory or Accumulator)
                   +-+-+-+-+-+-+-+-+
  Operation:       |7|6|5|4|3|2|1|0| <- 0
                   +-+-+-+-+-+-+-+-+                    N Z C I D V
                                                        / / _ _ _ _

So ROR on early 6502s does three things wrong:

1. It shifts left, instead of right (behaves like ASL)
2. It shifts a zero in, instead of C (behaves like ASL)
3. It doesn't update C (as if it wasn't a rotate instruction)

All three problems are flags that are sent to the ALU: the shift direction, the input bit, and the carry writeback.

Unresolved questions:

• We only tested ROR A; other addressing modes of ROR might behave differently. Other addressing modes might even be working - but I doubt that, since MOS would certainly have documented the working ones then.
• ROR might have more dependencies than A and C.
• What is it in the chip that causes the bug? I'm sure the fine guys at visual6502.org will be able to figure this one out soon. It is unlikely to be a bug in the PLA ROM, because a bug there would not affect different addressing modes of the same instruction with very different timings. It is more likely that it is in the "Random Control Logic" part.

You have probably already seen Visual 6502, a simulator of the 6502 that operates at the transistor level and visualizes what’s going on inside the CPU. The data the program operates on was derived by converting a high-resolution photograph of the 6502 die into polygons, and converting these polygons into the node and transistor configuration.

If you ignore the polygon data, which is only needed for visualization, the data to fully describe the 6502 consists of a set of nodes and a set of transistors.

There are 1725 nodes in the 6502, and 3510 transistors. Every transistor has one node as an input that turns the transistor on or off. If the transistor is on, it connects two other nodes, and if it is off, it separates them. Every node can either be neutral, or be a pullup – the latter means that the node will behave as if it was connected to VCC whenever the path through this node is otherwise floating, i.e. not connected to VCC or GND (or an external pulldown).

So the raw information that describes the 6502 is a set of nodes, for which there is one bit of information, whether it is a pullup node or a neutral node, as well as a set of transistors, which is a three-tuple consisting of gate, c1 and c2.

The file segdefs.js in visual6502 contains (next to the polygon information) the node state: “+” means pullup, “-” (or a missing node description) means neutral. The file transdefs.js contains the transistor tuples.

Stripped from irrelevant data, the 6502 description would look like this: The node states:

BOOL nodes[] = {
    /*  0 */ 1,
    /*  1 */ 0,
    /*  2 */ 0,
    /*  3 */ 1,
    /*  4 */ 1,
    /*  5 */ 1,
    /*  6 */ 1,
    /*  7 */ 0,
    /*  8 */ 1,
    /*  9 */ 0,
    /* 10 */ 1,
    [...]
}

…and the transistors:

struct {
	int gate;
	int c1;
	int c2;
} transistors[] = {
    {357, 558, 217},
    {1608, 657, 349},
    {412, 558, 1146},
    {558, 558, 943},
    {826, 230, 657},
    [...]
}

A quick estimate would be 1 bit per node (pullup or neutral), and 3 times 11 bits (3 node numbers from 1 to 1725) per transistor, resulting in about 117 kilobits; but there is still a lot of redundancy in this representation.

The transistor tuples can be represented in a much more compact way. First, there is no ordering for the transistors, so if we sort them by gate, we can encode just the difference between the current gate and the previous gate:

struct {
	int gate;
	int c1;
	int c2;
} transistors[] = {
    {1, 890, 558},
    {4, 558, 11},
    {5, 558, 146},
    {6, 558, 282},
    {6, 874, 657},
    {7, 657, 1591},
    {7, 657, 1591},
    {7, 657, 1591},
    {8, 150, 558},
    [...]
}

In practice, the difference between two gate nodes in the transistor list is a number between 0 and 4, so we could use 3 bits (instead of 11) for the gate. But in fact, it is enough to store a single bit: The nodes have no order either, so we can renumber them so that all nodes that are connected to a gate of a transistor are numbered from 0, and all nodes that are not connected to gates will be numbered above the ones with gates:

struct {
	int gate;
	int c1;
	int c2;
} transistors[] = {
    {0, 890, 558},
    {1, 558, 11},
    {2, 558, 146},
    {3, 558, 282},
    {3, 874, 657},
    {4, 657, 1591},
    {4, 657, 1591},
    {4, 657, 1591},
    {5, 150, 558},
    [...]
}

This way, there are no holes in the list of gates – a new transistor has either the next node number as its gate, or the same one again (i.e. a node is gate of several transistors). It is enough to store a single bit for the gate.

The example above already shows that the nodes 657 and 558 show up a lot: These are VCC and GND, respectively. In fact, 234 transistors connect to VCC, and 2493 connect to GND. We could Huffman-encode the c1 and c2 nodes, but in practice, all other nodes except these two are relatively uniformly distributed, so let’s just special case them.

There is also no ordering between the two nodes the transistor connects, and no transistor will ever connect VCC/GND to VCC/GND, so we only need to do the special VCC/GND encoding for c1, and leave c2 as it is. Let’s use a single “1″ bit to represent GND, “01″ as VCC, and all other 11 bit node numbers will be prefixed with “00″, making them occupy 13 bits.

This way, the 3510 values of c1 can be described in 2493 * 1 (the GNDs) + 234 * 2 (the VCCs) + 783 * (2 + 11) (the others) bits = 13140 bits. The c2 values occupy 3510 * 11 bits = 38610 bits. If you add the bit per transistor for the gate (i.e. 3510 bits), we’re at 55260 bits for the transistor description.

Using arithmetic coding, we can describe a node number in about 10.75 bits instead of 11. This way, we save (783 + 3510) * 0.25 bits = 1073 bits. The transistor description thus fits into 54187 bits.

As stated previously, we also need one bit per node for the pullup information. About half the nodes are pullup, and we don’t have the freedom of sorting and renaming the nodes any more (we’ve done that already for the transistor gates), so we’ll have to go with the 1725 raw bits.

So the final number is 54187 bits + 1725 bits = 55912 bits. That’s 6989 bytes, or roughly 56 kilobits, and about twice as big as H1N1.

With this number, we can estimate the complexity of a Commodore 64 to be about 200 kilobits (CPU, VIC, SID, 2xCIA, PLA) – plus another 160 kilobits of ROM.

But wait: Did you see the duplicate transistors in the sorted list? Yes, there are some duplicates, in fact, there are only 3288 unique transistors. And when looking at it on a higher level, the 130 entry instruction decode ROM has duplicates too: Only 115 are unique, leading to redundant paths in the node/transistor graph. The reason for this redundancy is routing: There are only two dimensions in a computer chip (plus layers), so you cannot just connect anything to anything.

The homework for today, dear reader, is to develop an algorithm that minimizes the description of the 6502 by removing duplicate transistors as well as equivalent paths.

I asked for his test code. It ran in kernel mode and looked roughly like this:

    int cpu_features[4];

    for (int i = 0; i < 100000; i++) {
        cpu_features[get_cur_cpu_number()] = cpuid_get_features();
        usleep(100);
    }

    for (int j = 0; j < 4; j++)
        printf("CPU %d features: %x\n", j, cpu_features[j]);

Questions to the reader:

1. What was the original idea, what is the algorithm?
2. Why did this work on a 2-way system, but not on a 4-way system?
3. Which two changes would at least make this code correct (albeit still horrible)?
4. How would you do it correctly?
5. Would you buy software from this company?

This is the original slide from 2007:

The table shows the relationship between the quality of a device’s security system and the time it took to hack it, as well as the original motivation for hacking and the side effects (collateral damage) it caused.

Correlation security/time to hack

There is a pretty clear correlation betwen the quality of the security system and the time required for hacking it – with the notable exception being the GameCube, which had rather weak security, but since its release coincided with the much more powerful Xbox, much of the hacker community neglected the GameCube until the Xbox was done. What can also be seen is that recently, devices tend to get hacked more quickly; probably simply because there are more and more people interested in hacking.

Correlation Linux/time to hack

The other exception is the PlayStation 3, which was not hacked until about three and a half years after its introduction. I argued that this was because there was only very little motivation to hack it: Sony shipped the devices with the “Other OS” option and even sponsored a port of Linux to it, allowing any user to install Linux if they wanted. Although Linux was running on top of a hypervisor and did not have access to all of the features of the device, it seems to have been enough to take the enough motivation to hack it out of the hacker community.

Linux/homebrew is the primary motivation

This is supported by the by the fact that the motivation for hacking every system in the table was either homebrew (i.e. running unautorized hobbyist applications) or Linux. Hackers seem to love to convert their devices into Linux computers to run a big library of existing software, or to hack the device to make it possible to run versions of existing emulators and games on the native OS.

Piracy is a side effect

None of the hacks in the table was done with the motivation to allow running copied games – but whenever the point of the security system was to prevent piracy, hacking it inevitably enabled piracy as a side effect. Some security systems protected other things like pay TV keys and SIM-locks; these also fell as side effects.

2010 update

In September 2009, Sony started shipping the “slim” model of the PlayStation 3, with the “Other OS” feature removed. With firmware 3.21 in April 2010, the feature was also removed from existing original models that users chose to upgrade – which was required for using any of the online features. The missing “Other OS” feature on the slim model motivated George Hotz (geohot) to hack into hypervisor mode (Jan 2010), but this approach did not lead to a working hack of the security system. In August 2010, the Australian company OzMods announced the commercial “PSJailbreak” USB dongle that hacks into non-hypervisor mode, allowing piracy and homebrew (“Backup Manager” says “backups and homebrew”).

Although this is the first time that a commercial company is first to hack a system, and the first time that piracy seems to have been a key motivation, removal of “Other OS” might have been another motivation, and geohot’s previous attempts might have helped as an entry point for this hack.

Usually, an open hacker community develops a hack, and commercial companies convert them into modchips. This time, a company developed a hack and a modchip, and the community reverse engineered it and ported the exploit code onto several other devices, allowing people to hack the PlayStation 3 without a dedicated device. And I’m sure Linux will be adapted soon to run in the new environment.

Conclusion

What do we learn from this? Linux is inevitable. Or maybe it should be “Homebrew is inevitable”. In the history of mankind, there has yet to be a popular system that is locked down to only allow certain software to run, but does not get hacked to run arbitrary code. I still dare to say that if Sony had not removed “Other OS”, the PlayStation 3 would have been the first system to not get hacked. At all.

(Here is an updated 2010 version of the table:)

Like many (but unfortunately not all) quirks of the i386/x86_64 architecture, this mess can be explained with history.

8086 – FLAGS

x86 history typically starts with the 16 bit 8086, but although it was not binary compatible with its predecessor, it was nevertheless a rather straightforward assembly-level compatible 16 bit extension of the 8 bit Intel 8080 with some ideas of the Zilog Z80. The 8086 is still a classic “home computer class” CPU, which was not meant for modern operating systems: It had no MMU of any kind, and no concept of privileged and unpriviliged modes. Therefore, control bits that we see as system state today were encoded into the 16 bit FLAGS register: The interrupt enable bit and the trap flag (which will cause a software interrupt after the next instruction and thus lets you single-step) are encoded into FLAGS right next to the ALU’s flags like Zero and Carry.

80286 – Machine Status Word

The 80286 then came with a simple form of memory management that allowed more sophisticated (but not yet “modern”) operating systems to run – like the original versions of OS/2. The 16 bit “Machine Status Word” was created to host the big switch between legacy mode (real mode) and the new memory-managed mode (protected mode) and a program could access it using the new instructions “lmsw” and “smsw”. The 80286 had more system state than just this bit: The GDT, the IDT and the TSS had its own registers and dedicated instructions to access them (“lgdt”/”sgdt”, “lidt”/”sidt”, “ltr”/”str”)

i386 – Control Registers

The i386 finally had a real MMU that allowed paging and thus modern operating systems. The MMU required two more registers in the system state, one for the base address of the pagetables, and one to read a fault address from. Intel decided against adding more special purpose registers with dedicated accessor instructions, but instead introduced eight indexed 32 bit wide “control registers” CR0 to CR7. The new accessors “mov crn, r32“/”mov r32, crn” allowed copying between registers and control registers and had the 3 bit CR index encoded in the opcode.

The old MSW was also wired into the lower 16 bits of CR0; but CR0 was also extended with new bits like the switch to turn on paging. CR1 was kept reserved, presumably as a second control register for miscellaneous control bits, and CR2 and CR3 were used for the aforementioned fault address and pagetable base pointer. The opcodes to access reserved control registers generated an “invalid opcode” fault, making it possible for Intel to reuse the opcodes later if they don’t use the control registers.

i486 – CR4

The i486 added a few more control bits, and some of them went into CR0. But instead of overflowing the new bits into CR1, Intel decided to skip it and open up CR4 instead – for unknown reasons.

Pentium – MSRs

On the Pentium, Intel added for the first time control bits that were a property of the implementation as opposed to the architecture, i.e. bits that are microarchitecture-specific and will therefore only work on certain CPUs and not necessarily be supported on later CPUs – like caching details and debug settings. In order not to waste the valuable CR space with throw-away control bits, Intel introduced the Model-specific Registers (MSRs). The MSR address space is 32 bits, and every MSR is 64 bits wide. The two new instructions “rdmsr” and “wrmsr” copy between an ECX-indexed MSR and the EDX:EAX registers.

Pentium II – SYSENTER MSR

The SYSENTER instruction that got introduced on the on the Pentium II is a fast way to switch between unprivileged and privileged mode. Instead of looking up the destination segment, instruction pointer and stack pointer in memory, the CPU holds this information in three special-purpose system registers. CR space is valuable, so Intel decided against filling up CR5, CR6 and CR7, so they put it into the MSR address space instead – at 0×174 through 0×176. This was practically an abuse of the MSR concept.

AMD K6 – EFER MSR

Who can blame AMD for doing similar things then? With the K6, which was introduced at the same time as the Pentium II, AMD diverged from just copying Intel for the first time and actually added features of their own: They added the SYSCALL instruction, and with it, a control bit that turns it on and off, and an extra control register with the target location. Being afraid to collide with Intel extensions they they didn’t know about, they put the extra system registers into the MSR space: the control register “EFER” (Extended Feature Enable Register) at 0xC000_0080 and the Syscall Target Register (STAR) at 0xC000_0081. Intel had been nicely lining up MSRs counting up from 0, so AMD decided to start counting at 0xC000_0080. Understandable as this is, it is basically the same abuse of the MSR concept as Intel’s with SYSENTER.

A very similar thing happened in the CPUID space, by the way: While Intel encoded all its feature bits in leaf 0x0000_0001, AMD defined leaf 0x8000_0001 for its features.

x86_64 – Chaos!

So far everything looked like it was getting a little more controlled. Both Intel and AMD are only adding new control registers in the MSR space, and since this is a big address space and AMD and Intel extend it on rather opposite locations, it all looks nicer. But then came x86_64: For the first time, Intel was copying a feature that AMD introduced, and it needed to be compatible with all its details. AMD had encoded the availibility of x86_64 in its own CPUID leaf in 0x8000_0001, so Intel had to support this leaf as well. And since Long Mode was turned on in the EFER MSR, Intel had to support an MSR in the AMD space of 0xC000_0000. Long mode also required supporting SYSCALL, so Intel also supported the STAR MSR.

Since x86_64 introduced the REX prefix to double the number of available general-purpose registers, AMD decided to allow this prefix also for “mov cr”, doubling the number of control registers and therefore introducing CR8 through CR15 – also doubling their width. And since AMD introduced them, they owned them, and decided to use CR8 for the “Task Priority Register” feature.

VMX and SVM

The architecture is messy, sure, but does it matter? Maybe not… as long as CPUs didn’t have virtualization extensions! Both Intel VMX and AMD SVM are designed so that they can automatically switch the complete privileged machine state including control registers and certain MSRs. Intel for example special cases CR0, CR3, CR4 and CR8, leaves CR2 to the user. AMD on the other hand has 16 fields for all CRs in its switcher. And because of the two different starting points of the MSR space, Intel VMX required a whitelist bitmap for 8192 MSRs starting at 0x0000_0000 and for another 8192 MSRs starting at 0xC000_0000 – and of course SYSENTER_CS, EFER, STAR and friends are special-cased. If you want to have a lot of fun, read the VMCS layout reference of Intel’s manual 3B!

Future?

• CR1 and CR5 to CR7 are still “owned” by Intel. AMD has shown that they don’t want to use them – and even Intel has not added a control register since 1989.
• CR9 through CR15 are technically owned by AMD, since they introduced them with x86_64 and decided to use CR8. Intel adopted the reserved ones when adopting x86_64, but it is unlikely that Intel will ever adopt smaller changes to the architecture from AMD, and AMD is unlikely to use them if they won’t be part of the architecture, so these will probably never be used either. On the other hand, AMD added these to the auto-switcher list of their SVM Virtual Machine Control Block (VMCB), showing that they haven’t given up on them yet.
• The MSR space is properly de-facto partitioned. Intel continues adding MSRs at 0 and AMD at 0xC000_0000 – but MSR have already lost their model-specificness in 1997. MSRs are the new CRs.

Dear Intel, dear AMD: I like the control registers, and I hate to see them wasted. Why don’t you finally define CR1 and give it a few control bits in the future? If you’re scared about collisions, I will be happy to be the arbiter. Ah, whatever: Intel, you get to define all even bits in CR1, and AMD, you get to define all odd bits. Okay? Cool.

Note that this is the original revision of the board (pre-Rev A), and the 6502 CPU is from week 51 of the year 1975 – so it has the ROR bug!

Does anyone know what the three digit numbers 002 and 003 on the 6530 RIOTs mean? Are these the indexes of the ROM images? If so, what is ROM #001 and was there a #000? Also, the back has the number “0372″ on it – is this a serial number? Looking at the dates of the chips, this seems to be the oldest KIM-1 of all those I could find on the internet.

Our machine had $29 of change. It started out with 25¢ coins, and after a while returned a combination of different coins (25¢ & 10¢, then 10¢ & 5¢), finally switching to all 5¢ coins at the end.

In total, it had

• 25¢ x 57 = $14.25
• 10¢ x 114 = $11.40
• 5¢ x 67= $3.35

After this, the machine refused to take bills, so it was either full with bills or, more likely, out of change.

But actually, it might still contain up to 95¢ of change – today’s homework is to find out how to measure the remaining change in the machine!

Therefore Intel had to add the VMCS, a 4 KB block in memory that holds the complete CPU state of both the host and the guest (segment registers, GDT and IDT pointer, certain MSRs etc.) as well as some control bits (for example, when to exit).

I also understand that Intel doesn’t allow me to just read and write memory in the VMCS, but abstracts accessing the virtualization state using a vmread/vmwrite interface. This way, the actual layout of this 4 KB page is an implementation detail and can be changed on later CPUs. It also allows for field indexes that are more spread out and encode what kind of field it is.

So I understand very well why Intel encodes into the VMCS field index whether it’s a control field (0), a read-only field (1), part of the guest state (2) or part of the host state (3), and whether it’s a 16 bit (0), 32 bit (2), 64 bit (1) or native-sized (3) field. This way, for example, all 16 bit guest state fields (like the guest’s CS) have indexes starting at 0×0800, and all 64 bit host state fields (like the hosts’s EFER MSR) start at 0x2C00.

Now what I don’t understand is what is so hard to be consistent with this convention (Intel Manual 3B, Appendix H).

• VMCS Link Pointer (0×2800): In the first revision of VT, it had already been already decided that there should be a mechanism for having a second 4 KB page in case later versions of VT need more than 4 KB of state. For this, there is there “VMCS Link Pointer”, which is a 64 bit physical address. Guess what category this belongs to? Guest state.
• “Guest Address Space Size” bit in the “VM Entry Controls” Field (0×4012): This is clearly guest state and not a control field.
• “Host Address Space Size” bit in the “VM Exit Controls” Field (0x400C): This is clearly host state and not a control field.
• VMX-preemption timer value (0x482E): This timer controls after how many ticks execution of the guest should end and control should be returned to the hypervisor. Intel put this into the “guest state” bucket: All other guest state fields are properties of the i386/x86_64 architecture that need to be switched, but not this one. This should really be a control field.

And here is another favorite of mine: the “Primary Execution Controls” field. The 32 bits specify which events in the guest will exit guest execution and trap into the hypervisor (Table 21-6). These events are, among others:

• exit on HLT
• exit on INVLPG
• exit on MOV CR3
• exit on PAUSE

Setting these bits to 1 enables the traps. So if you set all bits to 0, you basically have an unrestricted guest, and if you set all bits to 1, you have the most controlled guest, and you get a notification about every event in the guest. Or so you might think. Actually, there are two bits in the field that don’t work like this:

• Use MSR bitmaps
• Use I/O bitmaps

If these bits are set to 1, it checks a whitelist whether a certain MSR or I/O access is possible. If they are set to 0, all MSR and I/O accesses trap. Compared to all other bits, that’s backwards. Oh great.

Since Steve Jobs seems to be happy to explain his personal opinion on everything lately, I wrote him an email asking him about this, and he replied:

Return-path: <sjobs@apple.com>
Received: from bulkin002-bge351000.mac.com ([unknown] [10.150.69.129])
 by ms231.mac.com
 (Sun Java(tm) System Messaging Server 7u3-12.01 64bit (built Oct 15 2009))
 with ESMTP id <0L2X00HTAZ3Q6GF1@ms231.mac.com> for XXX@mac.com; Mon,
 24 May 2010 13:47:50 -0700 (PDT)
Original-recipient: rfc822;XXX@mac.com
Received: from relay13.apple.com ([17.128.113.29])
 by bulkin002.mac.com (Sun Java(tm) System Messaging Server 6.3-7.02 (built Jun
 27 2008; 32bit)) with ESMTP id <0L2X001EVZ3QKED0@bulkin002.mac.com> for
 XXX@mac.com (ORCPT XXX@mac.com); Mon, 24 May 2010 13:47:50 -0700 (PDT)
X-AuditID: 1180721d-b7c17fe00000693e-19-4bfae5f6545a
Received: from [17.201.27.84]
	(using TLS with cipher AES128-SHA (AES128-SHA/128 bits))
	(Client did not present a certificate)	by relay13.apple.com (Apple SCV relay)
 with SMTP id DB.14.26942.6F6EAFB4; Mon, 24 May 2010 13:47:50 -0700 (PDT)
From: Steve Jobs <sjobs@apple.com>
Content-type: text/plain
Content-transfer-encoding: 7bit
Subject: Re: Intel VT VMCS Layout
Date: Mon, 24 May 2010 13:47:48 -0700
Message-id: <3E789F1B-7E13-FFD2-80F6-8E8D4CDDE7FB@apple.com>
To: Michael Steil <XXX@mac.com>
MIME-version: 1.0 (Apple Message framework v1077)
X-Mailer: Apple Mail (2.1077)
X-Brightmail-Tracker: AAAAAQAAAZE=

The whole VMCS is a big mess, I hate it.

> Hi Steve, what do you think about the ordering of the VMCS fields in
> Intel's VT extenions?
>
>   Michael

Exercise for the reader: Change it.

(When you have run out of examples, you can try this game with other major players in the IT business.)

Let’s play this game in the comments to this blog entry: Just add as many of these pairs that you can think of – extra points if Microsoft’s technology has a closed specification.

“libcpu” is an open source library that emulates several CPU architectures, allowing itself to be used as the CPU core for different kinds of emulator projects. It uses its own frontends for the different CPU types, and uses LLVM for the backend. libcpu is supposed to be able to do user mode and system emulation, and dynamic as well as static recompilation.

Here are my slides: 26C3-libcpu.pdf

Here is the video recording: 26C3-libcpu.mp4

Read more at http://www.libcpu.org/

So in practice, you can put the instruction that would be before the branch right after the branch, if this instruction is independent of the branch instruction, i.e. doesn’t access the same registers. Otherwise, you can fill it with a NOP. Out-of-order architectures can do this reordering at runtime, so there would be no need for a delay slot. Nevertheless, the delay slot is a feature of the architecture, not the implementation.

Some RISCs like PowerPC and ARM do not have a delay slot, but for example MIPS, SPARC, PA-RISC have it. But there are some variations: MIPS and PA-RISC have an annihilation/nullify/likely bit in the instruction, so the programmer can choose that the instruction in the delay slot only gets executed if the branch is taken.

Other CPUs, like SPARC, PA-RISC or the ill-fated Motorola M88K have optional delay slots: The programmer can set a bit in the opcode if he cannot come up with a good instruction for the delay slot, and save the wasted NOP in the program code this way – the CPU will put a bubble into the pipeline.

Now the interesting question is what happens if the branch and the delay instruction are not independent. What if the delay instruction writes r5 and the branch jumps to r5? What if it’s a branch-and-link, and the delay instruction modifies the link register? On MIPS, this is illegal, and undefined.

In practice, MIPS won’t halt and catch fire though. As you would expect from the design of a CPU pipeline, the CPU basically executes the branch and the delay instruction in order, as they are stored in the instruction stream, and it only delays the write to PC, i.e. the actual jump until after the delay instruction. So, for example, if you modify a register that the branch depends on, it will not influence the branch, but be in effect after the jump.

On the aforementioned Motorola M88K, this behaviour is documented, and GCC even makes use of it:

820:   7d ad 00 08   cmp   r13,r13,0x08    ; compare

824:   d4 6d 00 05   bb0.n 0x03,r13,0x834  ; cond. branch
828:   63 df 00 00   addu  r30,r31,0       ; delay slot

82c:   cc 00 00 7f   bsr.n 0xa28           ; function call
830:   60 21 01 ac   addu  r1,r1,0x1ac     ; delay slot: fix up link

834:   00 00 00 00   nop

The first three instructions are a compare/branch sequence. If the branch is taken, execution will continue at 0×834, otherwise at 0x82c, after the delay slot. The delay instruction is independent of the branch, nothing special here yet.

But now look at the following two instructions: 0x82c and 0×830 are not independent. r1 is the M88K’s link register, so the “bsr” writes the addres of the following instruction after the delay slot (0×834) into r1. The delay slot also writes into r1: It adds 0x1ac to it. These instructions are executed in order, but the actual branch to 0xa28 will only be done after the delay instruction.

So what these two instructions effectively do is call a function, but set up the return address to skip the next 0x1ac bytes (107 instructions) after return. If the conditional branch at 0×824 is taken, the code at 0×834 will be executed, otherwise, 0xa28 is called, and the “taken” case of the conditional branch is skipped. This trick can be used whenever you have C code with an “if” statement of which one case is a single function call:

if (...) {
    call_something();
} else {
    [...]
}