29 November 2020
18 September 2016

EC Container 5

Applesoft, rewritten

I wrote the Apple IIgs emulator KEGS (see http://kegs.sourceforge.net). A big problem with releasing this emulator is that it needs the original ROMs to work, and I cannot release those (Apple won’t even discuss terms for licensing). So I release the emulator binary, and tell folks to copy their own ROMs. Most people pirate the ROMs online. I don’t like this situation.

On the Apple IIgs, the ROMs (for ROM01 systems, with 128KB of ROMs) consist of:

- 10KB for Applesoft, the BASIC interpreter that all Apple II’s use.
- 2KB for the Monitor, handy helper routines and basic system initialization.
- a KB to boot from 5.25” and 3.5” floppy disks, access the 80 column display, mouse, and modem.
- routines to initialize the system from reset.
- the Apple IIgs Toolbox, a collection of ROM routines for handling memory allocation, drawing to the Super Hires screen, etc of about 110KB.

So, can I rewrite enough of this to be useful?

I cannot rewrite the entire Apple IIgs Toolbox. However, when GSOS boots, it overrides most toolbox routines anyway in RAM. Plus, if I just want Apple IIe-like compatibility first, I don’t need the Toolbox. My long term goal here is to only write the tools for what’s needed to boot GSOS, and never write the ones which will be overridden. This avoids needing to rewrite QuickDraw II, and other complex routines.

The Monitor is non-trivial. The routines do things like: outputting chars to the screen, including scrolling the text screen; lores helper routines; a disassembler; and the Monitor (a basic debugger-like interface). The major problem is Woz wrote this code, so it’s incredibly dense. The disassembler is not needed at first, and so the rest are reasonable to re-implement.

And so we come to Applesoft. It really doesn’t make sense to start with it, but it’s the most interesting project, so I’m starting with it. It’s large enough that if I finish I will have accomplished something, but not so large that it’s impossible to see the end.

So, my medium term plan is to create a basic ROM image for KEGS with: a bare minimum Monitor clone and a working Applesoft BASIC clone called ASOFT, and try to do so in a way that other Apple II emulators could use it.

I have two major concerns with Applesoft: it will be hard to rewrite it to fit in 10KB (it takes times to shrink code, and I want to try to keep most Applesoft entry points working, which greatly limits me); it will be tricky to get 100% compatibility with real Applesoft.

I was never great at writing large 6502 assembly language programs. The largest 65816 assembly language program I ever wrote was a 1.5 pass assembler, which I never released. So writing Asoft directly as 6502 assembly would not be a great choice for me.

But I’ve written lots of C code. So my plan is to initially write a clone in C, work out the algorithms, and make it so it can load and run Applesoft programs from Unix. Then, once it is complete, begin coding it in 65c02 assembly. Why 65c02 instead of Applesoft’s 6502 code? I think being able to use: “LDA (zp)” and “STZ” will let me save enough bytes to help me stay under 10KB.

Writing 6502 code is a tradeoff between size and speed--there is almost always a very dense, yet slow, approach, or a faster but longer approach. My impression is Applesoft is somewhat dense--it’s not crazy Woz-like code (which is often very dense), but it’s not got obviously redundant code. And, allowing 65c02 still allows other emulators to use Asoft. Using 65816 would allow even denser code, but then it would only run on Apple IIgs emulators.

My plan is to write the clone based on available 2nd hand information--I won’t disassemble Applesoft, or look at disassemblies, but rather rely on 2nd-hand documentation. The book “What’s Where in the Apple II” names all the major entry points, and gives a detailed description of the variable memory layout, etc. Issue 1 of the Apple Orchard also has an excellent description of some major Applesoft entry points, the FP format, in a really dense 6-pages. I took that as a starting point, and just started implementing some routines.

I’ve begun writing this C code, and as of right now, I have the immediate command:

PRINT 2+(3*3)

working. It prints 11. I don’t have stored programs working, or variables, or strings. I spent a lot of time writing and testing the FP ADD, Multiply, and Divide routines. I spent time on FIN (read a constant and convert to FP, effectively scanf()) and FOUT (convert an FP value to string), but I’m not really happy with how those two work, yet. For more complex formulas, I get results like 10.9999 (I know why, it’s not a total mystery), but I don’t have a great solution yet.

I wrote helper functions to convert to/from the Applesoft 40-bit FP format to IEEE doubles, and then wrote comparison routines so that I could ensure my routines match the IEEE result (handling the rounding carefully). So, one helpful early routine I worked on was RND(), to generate random numbers, and used that as the basis of my testing.

And that leads to my major deviation from Applesoft: I’m not going to be 100% compatible with Applesoft. If I can be better, I will. I also cannot support every single Applesoft entry point. My basic plan is to try to work with as many utilities as possible, with basic utilities that do things like Renumber should always work, but more complex things like G.P.L.E. may not. I want to support “&” vector utilities, but there will be limits. Any routine relying on undocumented Applesoft features will almost certainly not work.

My plan is:

1) Get basic tokenizing and expression evaluation working (done, at least partially).
a) Add, Multiply, Divide, FIN, FOUT (done, mostly)
b) other functions, like COS(), SIN() (not done)
2) Get deferred program tokenizing working: ’10 PRINT “Hello”’
3) Get variable accesses working
a) FP variables
b) strings
c) integers “%”
4) Run short simple programs
5) Then, implement all Applesoft tokens.

And, I want to explore several areas for improvements:

1) I have a much better RND() function (Applesoft’s is notoriously buggy)
2) I want to implement pseudo-integers. This will need it’s own post.
3) I want to implement FAST GOTO (and GOSUB).
a) GOTO 1000 would change the tokenized program code from 0xab, 0x31, 0x30, 0x30, 0x30 to: 0xab, 0xff (token meaning encoded line number next), xx, yy, 0x30. Where xx and yy would be the address of the line to jump to. Asoft would change the tokenized code as it ran, to put in the direct address. Asoft would undo the FAST GOTO before allowing the program to be modified. The key problem with this type of change is DOS’s “SAVE” could write the FAST GOTO version to disk, which is actually fine for Asoft, but which hurts Applesoft compatibility. My current plan is GOTO 99 would not be converted (it would scan from the start of the program to find line 99), but GOTO 100 and higher numbers would be converted. It is possible to convert GOTO 99 to 0xfe, 0x63, but it adds another tokenized form to handle, which means more code.
b) When doing LIST, and we see token 0xff, follow the pointer to the line indicated, and get the real line number from that address. This is also how FAST GOTO is un-done when a line is added or deleted. I plan to use a ZP location to indicate the program may be using FAST GOTO, and go through the program fixing it when necessary.
4) Maybe: FAST Variables. This is more intrusive than FAST GOTO, and it’s unclear how much it helps, but again use unused tokenized space (such at 0x60-0x7f, 0xeb-0xfe) to encode variables. Single letter variables couldn’t be encoded, but 2-letter variables names and above can be encoded in two tokenized bytes: 0x01-0x1f or 0x60-0x7f gives 5 bits of info (these characters are not legal in Applesoft tokenized format), and the next byte can indicate another 8 bits, for 13 bits of address info. Multiply by 5 and add this to LOMEM to get the variable address, works for offsets into up to 40KB of variables, which is more than enough).
5) I want to do something clever for strings, but I don’t know what yet. In any case, garbage collection will be fast.

Why implement these improvements when KEGS runs Applesoft 100x faster than the original already? Well, because it’s cool to use new algorithms to make something old more efficient.
EC Container 6