Assembly vs BASIC

From Maze

There are many ways to program a computer. This is true in the general sense--that is, when setting out to work creatively with computers, a wide range of options are available. But it is also true in a more specific way: given a particular computer and a particular idea, there are often many different ways to accomplish a goal computationally.

In many cases, a computer platform will inspire certain kinds of creativity based on its abilities. For example, early microcomputers came with BASIC interpreters built into ROM, so that once the computer booted up, a user could immediately begin writing programs in that language. Unlike later generations, the manufacturers of these computers intended them to be programmed, and the operating manuals that came with the hardware offered instructions and ideas for new computer owners to write their own software. Such was the case with the Commodore 64, of course, with 10 Print among the suggested programs listed in the manual.

But in most cases, a particular platform offers multiple ways to accomplish a given program. Today's computing systems make such a fact obvious: if one wanted to produce a computer generated maze similar to 10 Print on a contemporary Mac, for example, a whole range of possibilites are available in which to program: a UNIX command line script like BASH or Perl; a MacOS-native environment like Cocoa; a cross-platform graphics rendering library like SDL, which is often programmed in C++; a cross-platform scripting environment like Python; an object-oriented graphics sketching tool like Processing; a multimedia authoring tool like Flash, a web-based environment like Javascript and the HTML5 Canvas, and many more.

The increase in computer programming environments notwithstanding, something remains as true today as it was during the reign of the C64 two and a half decades ago: eventually, computer programs must be translated into machine code and run on a microprocessor. The programs written in more human-legible, abstracted languages like BASIC or Flash ActionScript are sometimes called "high-level" languages, because they operate at a remove from the hardware of a particular computer. High-level languages often allow the programmer to avoid or to ignore details about how the CPU works or how memory is managed.

Conversely, "low-level" languages are those in which the programmer cannot ignore such hardware details, but must manipulate the microprocessor, memory, and the interfaces with other integrated circuits directly. Machine code itself exemplifies low-level programming, but it is difficult to do because it is difficult for human programmers to remember and accurately manipulate operations and operands in raw binary or hexadecimal notation. More commonly, low-level programming is done in assembly language. In both cases, the programmer provides instructions specific to the microprocessor, for example to load a value from a particular memory location into a particular processor register, or to perform a mathematical operation upon a memory location. But in assembly, the programmer need not recall the numerical equivalents of such instructions, but only human-readable mnemonics for them.

Like many microcomputers of the 1970s and 1980s, the Commodore 64 uses the MOS Technologies 6502 microprocessor. Introduced in 1975, the 6502 was simple in its circuit design and therefore much less expensive than competing chips of that era. Its low cost made it an important player in the popularization of the microcomputer in the decade after its introduction. While it is not necessary to know everything about the 6502 to appreciate either to C64 or the 10 Print program, it's worth noting that it essentially does one of three things: move values between memory and one of three microprocessor registers (named Accumulator--or A, X, and Y, respectively); perform mathematical operations on values in the accumulator, or change the address at which program execution takes place. The first type of operation is equivalent to high-level actions for loading or storing data (e.g. LET in BASIC), the second type is equivalent to the more familiar operator notation borrowed from mathematics (e.g., + - * / in BASIC), and the third is equivalent to jumps and subroutines (e.g. GOTO and GOSUB in BASIC).

Like every BASIC program, 10 Print is high-level. It relies on abstracted operations like PRINT and RND to perform complex tasks that would require considerably greater effort to accomplish at a low-level. For this reason, it is useful to compare the BASIC version of 10 Print on the C64 with its equivalent in 6502 assembly. Doing so will help clarify what features of the program, if any, are unique to its BASIC implementation.

10 Print is a "native" BASIC program, which is just to say that it was originally written in BASIC for the C64, and not first rendered in assembly and later reimplemented. For that reason, no canonical assembly program exists. As with literary translation or artistic adaptation, there are multiple ways to recast a computer program from one language into another, even on a relatively simple system like the C64, and even with a relatively simple program like 10 Print. The following rendition was authored by Ian Bogost, Stephane Hockenhull, and Nick Montfort, in the context of the demo scene event @party in July 2010.

*= $1000 ; starting memory location
lda #$80 ; set this value in...
sta $d40f ; ... the noise speed hi SID register
sta $d412 ; ... and the noise waveform SID register loop ; label for loop location lda $d41b ; load a random value and #1 ; lose all but the low bit adc #$6d ; value of "\" PETSCII jsr $ffd2 ; output character via kernal routine bne loop ; repeat

[Note: a complete, line-by-line explication of this program is needed, but I've omitted it for the time being, since such an act is really just an exercise and won't require much thinking to do, just time.]

The assembly version of 10 Print elucidate several features of the program from the low-level perspective of the platform.

For one, the most important high-level abstractions of the BASIC program prove to be just as abstracted in the low-level assembly rendition. There are two such abstractions of note in the original, PRINT and RND, which constitute the majority of the program's computational work. PRINT renders a character to the screen in the next available cursor position, advancing that position by one after doing so, and RND generates a random number between 0 and 1, which the program manipulates mathematically to produce one of the two PETSCII codes associated with the \ and / characters. Individually, these are relatively complex operations that involve multiple steps to carry out on the computer.

BASIC makes both of these acts compact and accessible. Print a character, generate a random number. Normally, carrying out either of these in assembly is an arduous task. Here's an example of a commonly used routine for generating a random 8-bit number in 6502 assembly:

Rand8 lda random ; get seed from memory (must be non-zero) asl ; shift byte bcc Rand8.no_eor ; branch if carry flag not set after shift eor #$CF ; otherwise EOR with literal $CF Rand8.no_eor sta random ; save number as next seed

This routine is nine bytes long, or 25% of the space needed for the entire 10 Print program in BASIC. That's not surprising; a high-level language is supposed to abstract more complex, lower-level routines into more easily usable functions. But such functions can also be built into the hardware itself, stored in ROM as executable instructions, or produced through a combination of seemingly unrelated affordances.

On the C64, it turns out not to be necessary to write a more extensive assembly random number routine like the one above, because the hardware has the facility to generate such numbers built-in. One way is through the BASIC interpreter itself: the RND function can be found in memory at address $e097, and the assembly programmer could simply jump to that subroutine by accessing address $e09a (i.e., "jsr $e09a) [NOTE: why are these two addresses different? Cf. http://www.atarimagazines.com/compute/issue72/random_numbers.php].

But an even stranger approach to random number generation on the machine involves the C64 sound chip, another MOS Technologies integrated circuit, part 6581, also known as the Sound Interface Device or SID. The SID is a programmable sound generator chip which was responsible for the C64's distinctive audio abilities. Apart from its sonic functions, the SID also has he ability to generate random values. To do so, the programmer must select the noise waveform on the SID's voice 3 oscillator and set that voice's frequency to a non-zero value. Setting a higher frequency value will cause the noise values to change more rapidly, yielding a greater variety of random numbers. The first three instructions of the assembly program above accomplish these settings:

lda #$80 ; set this value in... sta $d40f ; ... the noise speed hi SID register sta $d412 ; ... and the noise waveform SID register

... and once done, the program can get a new 8-bit random number by reading from memory location $d41b. While it looks a little messier than just calling RND in BASIC, the result is equally abstracted from the programmer's perspective--it's just abstracted to a different place, namely the SID chip.

Drawing a character to the screen is an equally complex task that can prove challenging in 6502 assembly on the C64. When the computer is set to text mode (instead of graphics mode, which was commonly used for games), the values for each textual character can be set by writing the desired PETSCII value into the a memory location corresponding to the desired position on the screen. The screen is 40 columns wide and 25 rows tall, for a total of 1,000 visible character "slots" at a time. Memory for this space starts at address $0400 (decimal 1024) and continues to address $07e7 (decimal 2023). To write to one of these character slots, the assembly programmer would load a desired PETSCII value and store it to one of those locations.

That's easy enough, unless the programmer wanted to mimic the operation of the BASIC program, as indeed we do. Recall that 10 Print spits out the next character in the maze at the current cursor position, making the maze appear to lay itself out column by column, row by row. To reproduce this behavior manually, the assembly programmer would seem to have to do considerable work to render the start of a screen, to pause, then to render a new screen with one more character than the last, and then to repeat until the screen filled. At this point, the BASIC program scrolls the top line up and off the display, moving everything else up a line. The assembly programmer would have to implement such a scrolling behavior by hand.

But as with the SID random number solution, the C64's underlying hardware ROM provides a much simpler solution. The C64 has a low-level operating system core, most of which it inherited from the earlier Commodore PET. This core is referred to as the KERNAL, and it occupies the last 8KB of the machine's address space ($E000-$FFFF). The KERNAL handles keyboard input and screen output, among other functions, including a routine that will send the PETSCII character value currently in the 6502 processor's accumulator to the current output device (the screen by default). That routine lives at memory address $ffd2, and it can be executed by jumping to subroutine at that address. This is just what the 10 Print assembly rendition above does, after loading a random value and manipulating it to insure that it will be one of the two slash characters that comprise the maze:

jsr $ffd2 ; output character via kernal routine

The output of the assembly program is essentially identical to 10 Print (it runs a bit faster, because the microprocessor is running machine instructions directly, rather than interpreting them first as BASIC commands and functions. But the program that generates that output is really no more or less lengthy or complex than is the BASIC program. When measured in bytes, the assembly program is even shorter than its BASIC cousin (22 bytes for the assembly program, compared to 36 bytes, or characters, for the BASIC program). While the assembly program is clearly more esoteric and less human readable than the BASIC one, its implementation teaches us that the abstraction that makes the emergent elegance of 10 Print's output possible in such a small set of instructions is not a feature of the BASIC interpreter, but of the underlying hardware itself.