-
Notifications
You must be signed in to change notification settings - Fork 1
Writing small programs
This page explains the techniques that I used to fit the program into 1K.
TokenList is a data structure used to lookup strings (keywords and operators) and return a single byte token value associated with the string. In ASCII bit 7 is unused, so this is used to mark the end of the string. The single byte token associated with a string immediately precedes the string in TokenList to make it easy to lookup the token string when LIST runs. The token value is the low byte of the address of the subroutine that implements the command or operator.
In 1K Tiny BASIC information contained in the address of a subroutine is treated like a resource to be exploited. These means that there are constraints on the addresses and lengths of some subroutines.
Operator precedence depends on defining an order for operators. This order is defined by placing the operator subroutines in that order, so that token values can be used for operator precedence. This requires that no operators have equal precedence, but because we want * and / to have equal precedence, there is a special rule that checks for * and treats it as equal precedence to /
Testing whether a token is a statement, function or operator depends on the address of the token subroutine. Statements have lower token values than functions or operators. Operators have higher token values than statements or functions.
During tokenisation, the subroutine that handles the double quote character has its lowest bit different from all other character handling subroutines. This means that when parsing a string, the end of the string can be detected without any additional work over and above detecting whether the next character is in a different class, which is done using XOR (if it is in a different class and bit 0 is set, it must be the end of the string).
The 8080 has 8 single byte RST instructions that call 8 8-byte subroutines in the first 64 bytes of the memory space. By placing frequently used subroutines in this area, 2 bytes can be saved per subroutine call.
Whenever two sections of code have more than a few bytes of code in common, the common section is either put into a subroutine, or if the part in common is at the end, one section of code jumps to the end of another.
Sometimes code can be arranged so that execution falls through from one section to another, avoiding a jump.
One section of code that relies heavily on this is the operator subroutines - all 8 of the arithmetic and comparison operators except for * and / fit in just 29 bytes plus two 8-byte subroutines that these operators share with several other sections of code.
Jumping over one byte of code can be done using MVI, CPI or any other instruction that fetches a second byte, provided that the instruction will execute harmlessly without interfering with the program. Similarly LXI can be used to skip 2 bytes.
Sometimes 3 byte instructions can be skipped using LXI if the last byte of the instruction is a harmless opcode. For example, jumps to page zero have 0 as the last byte of the instruction, and this is the opcode for NOP.
Subroutines can access constant parameters that follow the subroutine call using XTHL to get the address immediately after the call instruction. This is used by the CompareJump subroutine to fetch a constant value to compare A with, and a single byte in-page address to jump to if equal. This subroutine is placed at an RST location, so a 3-byte sequence can be used in place of the 5-byte CPI JZ combination.
When BASIC 1K encounters an error it calls the “Error” subroutine, which displays an error code starting with E, followed by an integer. This is the address that was on the stack, so it gives the location of the call. Producing a human readable lookup table for each code can’t be done until the code is stable, and will change from one release to another.
A memory rotate subroutine (MemoryRotate) is used for both of these operations: this subroutine permutes the contents of a block of memory by rotating it by k bytes, so it can be used to shift memory down for deletion, or rotate a new line into the right location between 2 other lines. This subroutine is 27 bytes long. Set up is required for deletion (25 bytes) and insertion (21 bytes).