This posts begins the analysis of the BASIC program's runtime state management. I'll start with a quick introduction to how the runtime state management works and then work through a few TRAPs that use runtime state storage.
For context and a list of other posts on this topic, see the PDP-11 BASIC reverse engineering project page.
The BASIC program's runtime state
When a program is running it needs to be able to remember what it's doing. For example, what was the last command executed or what value does the variable created ten lines ago currently have. When programming in C, for example, there's the stack where local variables and function return values are stored and the heap (where memory is allocated for use across multiple functions using system calls like malloc()).
On the PDP-11 we have the stack, for example, which has been used extensively by the BASIC code throughout the analysis carried out so far. There are also certain specific memory locations used to store certain elements of runtime state, such as the currently executing line of the BASIC program (these are basically all global variables). We have also seen the program storage area, which is the area of memory used for storing the BASIC code that the user has entered/loaded.
The complicating issue in the case of BASIC comes when we think about running a program, because now we have a running program (the BASIC application) running another program (the user's BASIC program). Therefore, we have two distinct runtime states to maintain.
So, how is the BASIC program runtime state maintained? Well, here's a rough memory map (you'll have to excuse my terrible artistic skills):
On the left is the low end of memory and on the right is the high end of memory. Starting at the left, at the very lowest addresses are the interrupt vectors used for TRAP handling and this is followed by the BASIC application itself. On the right hand side, at the highest available memory addresses, we have the optional EXF code, which is an external assembly language program that can be invoked from within BASIC using the EXF command. In the middle is a big chunk of space that I have called "working memory" which is used by the BASIC application.
I have broken out the structure of working memory a bit further in the diagram above.
At the extreme right hand side of the working memory is the stack. The stack pointer will start at the highest available memory address and the stack will grow downwards in memory from there. At the opposite side of working memory, immediately after the BASIC application, is the memory area where the user's BASIC program is stored. This is the "program storage area". As the user is typing/loading a program the program storage area will grow from the left to the right.
When a program is not running, R5 is used to track the extent of the program storage area as the program grows. If R5 ever exceeds the stack pointer value (plus a small buffer) that means the program code has used up all of the available memory and the user will receive an error. The test to see if there is enough free memory available to store another BASIC command is performed with TRAP 104, which I described in Part 7.
When the user RUNs their BASIC program, the remaining working memory is used to hold the runtime state of the executing program. It operates a bit like another stack that grows upwards in memory, with R5 being used as a second "stack pointer". When the program is running, the BASIC program storage area will be of a fixed size, because you can't edit a running program. Therefore, when a program is starting to run, the value of R5 is saved to a specific memory address and then R5 is used to track the use of the remaining working memory.
That's the general idea, which I hope is clear. I will describe the details in the coming series of posts.
For simplicity, when I refer to the "runtime state" in this post and future posts, unless otherwise specified, I'm talking about the BASIC program's runtime state.
TRAP 130
Before I start talking about reading and writing the runtime state, I need to describe TRAP 130 and 122, which are used below. The purpose of TRAP 130 is very simple, multiply the value in R0 by 6. Here's the code:
002346 000241 CLC
002350 006300 ASL R0
002352 010046 MOV R0, -(SP)
002354 006300 ASL R0
002356 062600 ADD (SP)+, R0
002360 000207 RTS PCFirst we clear the carry flag. Then, R0 is shifted left, which multiplies it by 2. The result is pushed to the stack. So, the value (2 x R0) is now stored on the stack. Then, R0 is shifted left again, so now R0 has been multiplied by 4. Finally, the value from the top of the stack is added to R0. So, we're adding (2 x R0) to (4 x R0), which will result in 6 x R0...and then we return.
TRAP 122
Two-dimensional arrays can be specified using DIM. For example:
DIM A(20,20) Unlike defining an array in, say C, what you are specifying here is the maximum possible index for each dimension. Since these arrays are indexed from zero in both dimensions, this command defines a variable called A, which is a 21 x 21 array.
TRAP 112 is used to calculate the storage space required for a two-dimensional array. The input to the TRAP is as follows:
R0 contains the dimensions; the high byte contains the "x" dimension and the low byte contains the "y" dimension.
R1 also contains the dimensions; the high byte contains the "y" dimension and the low byte contains the "x" dimension.
The output is the number of words of runtime state required to store the array, stored in R0. If the calculation is successful, all flags will be cleared. If there is not enough runtime state memory available to store the array, the overflow flag will be set.
Here's the code:
001536 042700 BIC #177400, R0
001542 042701 BIC #177400, R1
001546 005200 INC R0
001550 005201 INC R1
001552 010446 MOV R4, -(SP)
001554 010346 MOV R3, -(SP)
001556 104416 TRAP 16
001560 012603 MOV (SP)+, R3
001562 012604 MOV (SP)+, R4
001564 005701 TST R1
001566 001006 BNE 1604
001570 020027 CMP R0, #22000
001574 103003 BCC 1604
001576 104530 TRAP 130
001600 000257 CCC
001602 000207 RTS PC
001604 000262 SEV
001606 000207 RTS PCLet's see what this does.
001536 042700 BIC #177400, R0
001542 042701 BIC #177400, R1
001546 005200 INC R0
001550 005201 INC R1Firstly the high word of R0 and R1 are cleared, leaving the y and x dimensions of the array in R0 and R1 respectively. Both values are incremented because they are the maximum indices for each dimension, and the zeroth element needs to be included in the calculation as well.
001552 010446 MOV R4, -(SP)
001554 010346 MOV R3, -(SP)
001556 104416 TRAP 16
001560 012603 MOV (SP)+, R3
001562 012604 MOV (SP)+, R4Now R3 and R4 are pushed onto the stack and TRAP 16 is invoked. TRAP 16 is not one that I have written about yet, but it multiplies the values in R0 and R1 together and places the high word of the result in R0 and the low word of the result in R1. The values of R3 and R4 are then restored from the stack.
001564 005701 TST R1
001566 001006 BNE 1604
001570 020027 CMP R0, #22000
001574 103003 BCC 1604The resulting value is checked to see if it's not too big. R1 is checked and if not equal to zero, control jumps to 1604, sets the overflow flag and returns. Similarly, R0 is compared to the octal value 22000 (decimal 9216) and if it's greater than that, control jumps to 1604, sets the overflow flag and returns.
To be honest, I'm not totally clear on the operation of these lines because I haven't fully reverse engineered TRAP 16 yet. I am inferring for now that it is checking that the value is within acceptable bounds.
001576 104530 TRAP 130
001600 000257 CCC
001602 000207 RTS PCTRAP 130 is then used to multiply the value in R0 by 6. This is because each variable value will require six words of runtime state. Then, all status flags are cleared and control is returned from the routine.
001604 000262 SEV
001606 000207 RTS PCIn case of errors, the overflow flag is set and then control is returned to the calling code.
TRAP 112
TRAP 112 is used to store a word from R0 into the runtime state. Here's the full TRAP 112 code:
001340 010446 MOV R4, -(SP)
001342 010504 MOV R5, R4
001344 062704 ADD #24, R4
001350 020406 CMP R4, SP
001352 103014 BCC 1404
001354 005767 TST 13666
001360 001006 BNE 1376
001362 010567 MOV R5, 13666
001366 005205 INC R5
001370 006205 ASR R5
001372 000241 CLC
001374 006305 ASL R5
001376 010025 MOV R0, (R5)+
001400 012604 MOV (SP)+, R4
001402 000207 RTS PC
001404 104401 TRAP 1Let's see how it works.
001340 010446 MOV R4, -(SP)
001342 010504 MOV R5, R4
001344 062704 ADD #24, R4
001350 020406 CMP R4, SP
001352 103014 BCC 1404First we see if there is enough available memory. R4 is pushed onto the stack and then R5 is copied into R4. 24 (octal) is then added to R4 and the resulting value is compared to the value of the stack pointer. This tests whether there are more than 24 words remaining between the current value of R5 and the stack pointer. If there are not, this means there isn't enough memory left so control jumps to address 1404, which will produce an error.
001354 005767 TST 13666
001360 001006 BNE 1376When the program code is running, memory address 13666 is used to store the topmost address of the program code area. When the code is not running, R5 is used for this purpose and the value at address 13666 will be zero.
So, before using the value in R5 we check whether the topmost address of the program code area has been stored by testing the value at memory address 13666. If it is not equal to zero, that means we have already saved the top of the program code area and R5 contains the current top of the runtime state, so we jump ahead to 1376.
Otherwise, we need to set up the runtime state:
001362 010567 MOV R5, 13666
001366 005205 INC R5
001370 006205 ASR R5
001372 000241 CLC
001374 006305 ASL R5We begin by moving R5, which currently stores the topmost address of the program code area, into memory location 13666. Then there is a small issue to be dealt with. It's possible that the program code consists of an odd number of bytes, so we need to align R5 with the next highest even word after the end of the program code area. To achieve this, R5 is incremented and then shifted right, which will push the rightmost bit out of R5 and into the carry flag. We then clear the carry flag and shift R5 left again. This will have the effect of making sure that the lowest bit of R5 is always zero, in other words, R5 is always even.
001376 010025 MOV R0, (R5)+Now we store the value from R0 into the address pointed to by R5, and R5 is incremented. This is the line that actually stores R0 into the runtime state.
001400 012604 MOV (SP)+, R4
001402 000207 RTS PC
001404 104401 TRAP 1Finally, we pop R4 from the stack and return. The TRAP 1 at line 1404 is invoked whenever there is not enough memory available to store a value into the runtime state.
TRAP 114
TRAP 114 is used to retrieve data from the runtime state. At first glance the TRAP 114 code is going to seem much more complicated than you might intuitively think it needs to be. However, there are other TRAPs that I will describe in later posts that use multiple TRAP 112 calls to store multi-word entries into the runtime state.
For example, the DEF BASIC command, used to define user functions, pushes a structure into the runtime state representing the function. Each entry in the runtime storage has an identifying word at the start, of the following form:
Identifying values of the form 1xxxxx (in octal) are variables
Identifying values of the form 2xxxxx are return values from subroutines
Identifying values of the form 4xxxxx have got something to do with FOR loops (not sure exactly yet).
Identifying values of the form 6xxxxx are functions.
As far as I can tell, TRAP 114 works as follows, the input is:
R3 contains the memory address of the beginning of the runtime storage, or the location within the runtime storage from which to start searching.
R4 contains the identifying value to be searched for in the runtime storage.
R0 contains a mask, optionally zero, to indicate which bits of the value in R4 to match and which bits don't matter (i.e. any entry in the runtime storage that matches the unmasked element of R4 will return).
and the output is:
R3 will contain the memory address of the matching runtime storage entry or zero if no matching entry is found.
The zero flag will also be set if no matching entry is found.
Here's the code (note the entry point is at address 1436, not at the top of the code snippet shown):
001406 011300 MOV (R3), R0
001410 041600 BIC (SP), R0
001412 020004 CMP R0, R4
001414 001423 BEQ 1464
001416 042700 BIC #17777, R0
001422 022700 CMP #40000, R0
001426 001022 BNE 1474
001430 062703 ADD #20, R3
001434 000406 BR 1452
; TRAP 114 handler starts here
001436 005703 TST R3
001440 001414 BEQ 1472
001442 020506 CMP R5, SP
001444 103357 BCC 1404
001446 010146 MOV R1, -(SP)
001450 010046 MOV R0, -(SP)
001452 020306 CMP R3, SP
001454 103353 BCC 1404
001456 020305 CMP R3, R5
001460 103752 BCS 1406
001462 005003 CLR R3
001464 012600 MOV (SP)+, R0
001466 012601 MOV (SP)+, R1
001470 005703 TST R3
001472 000207 RTS PC
001474 003005 BGT 1510
001476 062703 ADD #2, R3
001502 062703 ADD #4, R3
001506 000761 BR 1452
001510 005700 TST R0
001512 001402 BEQ 1520
001514 005723 TST (R3)+
001516 000755 BR 1452
001520 116300 MOVB 2(R3), R0
001524 116301 MOVB 3(R3), R1
001530 104522 TRAP 122
001532 060003 ADD R0, R3
001534 000762 BR 1502Let's see how this works. The first few pieces of code perform santity checks to make sure everything is consistent.
001436 005703 TST R3
001440 001414 BEQ 1472First we test R3 and if it is zero we branch to 1472, which will immediately return. In other words, if R3 does not point into the runtime storage, this code does nothing.
001442 020506 CMP R5, SP
001444 103357 BCC 1404Next we test whether the runtime storage has exceeded the stack pointer, which would mean we are out of memory. If so, this is an error and control branches to 1404, which is the TRAP 1 at the bottom of the TRAP 112 code above.
001446 010146 MOV R1, -(SP)
001450 010046 MOV R0, -(SP)Now that we know we have some memory available, R1 and R0 are then pushed onto the stack.
001452 020306 CMP R3, SP
001454 103353 BCC 1404We now compare R3 to the stack pointer and if it is greater, again this would be an error so we branch to 1404, which is the TRAP 1 at the end of the TRAP 112 code above.
001456 020305 CMP R3, R5
001460 103752 BCS 1406
001462 005003 CLR R3R3 is now compared to R5. R3, in this case, is the current location we are searching in the runtime state and R5 is the upper limit of the runtime state. In other words, this is a test to see if we have searched the entire runtime state. If not, branch to 1406 to test the next word.
Otherwise, we have searched the entire runtime state so we clear R3 to indicate that the value requested was not found and return from the TRAP:
001464 012600 MOV (SP)+, R0
001466 012601 MOV (SP)+, R1
001470 005703 TST R3
001472 000207 RTS PCTo return we pop R0 and R1 from the stack, test the value in R3 to set the flags appropriately, and then return. Note that this same return code is used when returning with a successful result as well.
So if we have not yet searched the entire runtime state, we have branched to 1406, and execution continues from there:
001406 011300 MOV (R3), R0
001410 041600 BIC (SP), R0
001412 020004 CMP R0, R4
001414 001423 BEQ 1464These instructions are the real core of this TRAP. A word is moved from the runtime state into R0. The value is then masked by clearing all bits as specified in the mask parameter, which was the most recent item pushed onto the stack. The value now in R0 is compared to the value in R4, which is the value we are looking for. If they are equal we have found what we are looking for so we branch to address 1464 and return.
Otherwise, the value we are currently looking at in R3 is not the value we want, so we need to skip ahead to the next entry in the runtime state. However, how far we need to jump ahead in the runtime state depends on the type of entry that we are currently pointed at, so, the remainder of this TRAP is simply logic to determine how far to move ahead, based on the size of the current entry, in the runtime state.
001416 042700 BIC #17777, R0R0 contains the value of the word that we are currently pointed at in the runtime state. We mask this value, clearing all bits except for the top three. These top three bits represent the "type" of the entry.
Then we compare the value in R0 to 40000. This type represents the state of a FOR loop (not sure of the exact details yet). If the value in R0 does not equal 40000 we jump to 1474 to deal with the other types. If it does equal 40000 then we add 20 onto the value in R3, skipping the FOR loop state entry, and then branch back to address 1452 to test the next runtime state entry (or exit if we have reached the end of the runtime state).
In cases where we have determined that R0 is not equal to 40000, we continue here by checking whether 40000 is greater than the value in R0. The only "type" with a value greater than 40000 is a function entry (which has a type of 60000), and in this case we add 6 onto R3 and then branch back to 1452 to test the next runtime state entry (or return if we have reached the end of the runtime state).
Otherwise, for types less than 40000 (variables and return addresses) control branches to 1510.
001510 005700 TST R0
001512 001402 BEQ 1520
001514 005723 TST (R3)+
001516 000755 BR 1452Next we test to see whether the "type" is zero, which would be a variable. If it is, we branch to 1520. If not, there is only one type left which is a return address (which is only one word long). In that case we test the value in R3, increment R3, and then branch back to 1452 to test the next runtime state entry (or return if we have reached the end of the runtime state).
001520 116300 MOVB 2(R3), R0
001524 116301 MOVB 3(R3), R1
001530 104522 TRAP 122
001532 060003 ADD R0, R3
001534 000762 BR 1502Finally, we deal with the case where the current entry is a variable. The word after the identification word contains the size of the variable, because the variable may be a multi-dimensional array specified with DIM. So, the low byte of the next word (R3+2) is moved into R0 and the high byte of the next word (R3+3) is moved into R1.
Then TRAP 122 multiplies the values in R1 and R0 together, and multiplies the result by six. This resulting value is then added to R3 and control branches to address 1502. At 1502, an additional 4 is added to R3 to complete the calculation of the size of the variable storage, and then control branches back to 1452 to test the next runtime state entry (or return if we have reached the end of the runtime state).
Using this new knowledge
That's it for now. We've seen the structure of runtime state storage and how values are stored and read from runtime state. In the next post I'm going to provide some examples of the use of the runtime state by BASIC commands, starting with GOSUB and RETURN.