Chapter Three



Memory Usage 


		



Many of BASIC's functions are controlled by a set of tables 

built in RAM not already occupied by BASIC or the Operating 

System (OS). Figure 3.1 is a diagram of memory use by both 

programs. Every time a BASIC programmer enters a statement, 

memory requirements for the RAM tables change. Memory use 

by the OS also varies. Different graphics modes, for example, 

require different amounts of memory.

    These changing memory requirements are monitored, and 

this series of pointers keeps BASIC and the OS from overlaying 

each other in memory:

When a graphics mode requires larger screen space, the OS checks the application high memory address (APHM) that has been set by BASIC. If there is enough room for the new screen, the OS uses the upper portion of space and sets the pointer HMADR to the bottom of the screen to tell the application how much space the OS is now using. BASIC builds its table toward high memory from low memory. The pointer to the lowest memory available to an application, called LMADR in the BASIC listing, is set by the OS to tell BASIC the lowest memory address that BASIC can use. When BASIC needs more room for one of its tables, BASIC checks HMADR. If there is enough room, BASIC uses the space and puts the highest address it has used into APHM for OS. BASIC's operation consists primarily of building, reading, and modifying tables. Pointers to the RAM tables are kept in consecutive locations in zero page starting at $80. These tables are, in order,

13

Chapter Three

BASIC reserves space for a buffer at LMADR. It then builds the tables contiguously (without gaps), starting at the top of the buffer and extending as far as necessary towards APHM. When a new entry needs to be added to a table, all data in the tables above is moved upward the exact amount needed to fit the new entry into the right place. Figure 3-1. Memory usage ---------------------- FFFF | Operating System | | ROM | E000 ---------------------- | Floating Point | | ROM | D800 ---------------------- | Hardware Registers | D000 ---------------------- | Unused | BFFF ---------------------- | BASIC ROM | A000 ---------------------- | Screen | ----------------------<----HMADR Free RAM ----------------------<---- APHM | BASIC | | RAM | | Tables | ----------------------<---- LMADR | Operating System | | RAM | 0000 ---------------------- 14

Chapter Three Variable Name Table The Variable Name Table (VNT) is built during the pre-compile process. It is read, but not modified, during execution but only by the LIST statement. The VNT contains the names of the variables used in the program in the order in which they were entered. The length of entries in the Variable Name Table depends on the length of the variable name. The high order bit of the last character of the name is on. For example, the ATASCII code for the variable name ABC is 414243 (expressed in hexadecimal). In the Variable Name Table it looks like this: 41 42 C3 The $ character of a string name and the ( character of an array element name are stored as part of the variable name. The table entries for variables C, AA$, and X(3) would look like this: C C3 AA$ 41 41 A4 X(3) 58 A8 It takes only two bytes to store X(3) because this table stores only X(. A variable is represented in BASIC by a token. The value of this token is the position (relative to zero) of the variable name in the Variable Name Table, plus $80. BASIC references an entry in the table by using the token, minus $80, as an index. The Variable Name Table is not changed during execution time. The zero page pointer to the Variable Name Table is called VNTP in the BASIC listing. Variable Value Table The Variable Value Table (VVT) is also built during the pre– compile process. It is both read and modified during execution. There is a one-to-one correspondence in the order of entries between the Variable Name Table and the Variable Value Table. If XXX is the fifth variable in the Variable Name Table, then XXX's value is the fifth entry in the Variable Value Table. BASIC references a table entry by using the variable token, minus $80, as an index Each entry in the Variable Value Table consists of eight bytes. The first two bytes have the following meaning: 15
Chapter Three 1 2 --------------- | | | --------------- type vnum type = one byte, which indicates the type of variable $00 for floating point variable $40 for array variable $80 for string variable vnum = one byte, which indicates the relative position of the variable in the tables The meaning of the next six bytes varies, depending on the type of variable (floating point, string, or array). In all three cases, these bytes are initialized to zero during syntaxing and during the execution of the RUN or CLR. When the variable is a floating point number, the six bytes represent its value. When the variable is an array, the remaining six bytes have the following format 1 2 3 4 5 6 7 8 ------------------------- | | | | | | | | | ------------------------- |disp | dim1| dim2 disp = the two-byte displacement into string/array space of this array variable dim1 = two bytes indicating the first dimension value dim2 = two bytes indicating the second dimension value All three of these values are set appropriately when the array is DIMensioned during execution. When the variable is a string, the remaining six bytes have the following meaning: 1 2 3 4 5 6 7 8 ------------------------- | | | | | | | | | ------------------------- |disp | curl| maxl 16
Chapter Three disp = the two-byte displacement into string/array space of this string variable. This value is set when the string is DIMensioned during execution. curl = the two-byte current length of the string. This value changes as the length of the string changes during execution. maxl = the two-byte maximum possible length of this string. This value is set to the DIM value during execution. When either a string or an array is DIMensioned during execution, the low-order bit in the type byte is turned on, so that the array type is set to $41 and the string type to $81. The zero page pointer to the Variable Value Table is called VVTP in the BASIC listing. Statement Table The Statement Table, built as each statement is entered during editing, contains tokenized forms of the statements that were entered. This table determines what happens during execution. The format of a Statement Table entry is shown in Figure 3-2. There can be several tokens per statement and several statements per line. Figure 3-2. Format of a Statement Table Entry ---+----------------------- ----------------------- --------------- | | | | | .... | | | | .... | | | ---+----------------------- ----------------------- --------------- |lnum | llen| slen| snt | toks | eos |slen | snt | toks | eos | eol | lnum = the two-byte line number (low-order, high-order) llen = the one-byte line length (the displacement to the next line in the table) slen = the one-byte statement length (the displacement to the next statement in the line) snt = the one-byte Statement Name Token toks = the other tokens that make up the statement (this is variable in length) eos = the one-byte end of statement token eol = the one-byte end of line token The zero page pointer to the Statement Table is called STMTAB in the BASIC listing. 17
Chapter Three String/Array Table The String/Array Table (also called String/Array Space) is created and modified during execution. Strings and arrays can be intermixed in the table, but they have different formats. Each array or string is pointed to by an entry in the Variable Value Table. The entry in the String/Array Table is created when the string or array is DIMensioned during execution. The data in the entry changes during execution as the value of the string or an element of the array changes. An entry in the String/Array Table is not initialized to any particular value when it is created. The elements of arrays and the characters in a string cannot be counted upon to have any particular value. They can be zero, but they can also be garbage - data previously stored at those locations. Array Entry For an array, the String/Array Table contains one six-byte entry for each array element. Each element is a floating point number, stored in raveled order. For example, the entry in the String/Array Table for an array that was dimensioned as A(1,2) contains six elements, in this order: A(0,0) A(0,1) A(0,2) A(1,0) A(1,1) A(1,2) String Entry A string entry in the String/Array Table is created during execution, when the string is DiMensioned. The size of the entry is determined by the DIM value. The "value" of the string to BASIC at any time is determined by the data in the String/Array Table and the current length of the string as set in the Variable Value Table. The zero page pointer to the String/Array Table is called STARP in the BASIC listing. The Runtime Stack is created during execution. BASIC uses this LIFO stack to control processing of FOR/NEXT loops and GOSUBs. When either a FOR or a GOSUB statement is encountered during execution, an entry is put on the Runtime Stack. When a NEXT, RETURN, or a POP statement is encountered, entries are pulled off the stack. Both the FOR entry and the GOSUB entry have a four-byte header: 18
Chapter Three ----------------- | | + | | ----------------- type lnum disp type = one byte indicating the type of element GOSUB type = 0 FOR type = non-zero lnum = the two-byte number of the line which contains the statement (low-order, high-order) disp = one byte indicating the displacement into the line in the Statement Table of the token which caused this stack entry. The FOR-type byte is actually the token representing the loop control variable from the FOR statement. (In the statement FOR I = I to 10, I is the loop control variable.) So the FOR-type byte will have a value of $80 through $FF - the possible values of a variable token. The FOR entry contains 12 additional bytes, formatted like this: 1 2 3 4 5 6 7 8 9 10 11 12 -----+----+----+----+----+---------+----+----+----+----+----- | | | -----+----+----+----+----+---------+----+----+----+----+----- sval step sval = the six-byte (floating point) limit value at which to stop the loop step = the six-byte (floating point) STEP value to increment by The GOSUB entry consists entirely of the four-byte header. The LIST and READ statements also put a GOSUB type entry on the Runtime Stack, so that the line containing the LIST or READ can be found again when the statement has finished executing. The zero page pointer to the Runtime Stack is called RUNSTK in the BASIC listing. 19
Chapter Three Zero Page Table Pointers The starting addresses of the tables change dynamically during both program construction and program execution. BASIC keeps the current start addresses of the tables and other pointers required to manage memory space in contiguous zero- page cells. Each pointer is a two-byte address, low byte first. Since these zero page cell addresses remain constant, BASIC is always able to find the tables. Here are the zero page pointers used in memory management, their names in the BASIC listing, and their addresses: Multipurpose Buffer $80,$81 Variable Name Table VNTP $82,$83 VNT dummy end VNTD $84,$85 Variable Value Table VVTP $86,$87 Statement Table STMTAB $88,$89 Current Statement Pointer STMCUR $8A,$8B StringlArray Table STARP $8C,$8D Runtime Stack RUNSTK $8C,$8E Top of used memory MEMTOP $90,$91 Memory Management Routines Memory Management routines allocate space to the BASIC tables as needed. There are two routines: expand, to add space, and contract, to delete space. Each routine has one entry point for cases in which the number of bytes to be added or deleted is less than 256, and another when it is greater than or equal to 256. The EXPAND and CONTRACT routines often move many thousands of bytes each time they are called. The 6502 microprocessor is designed to move fewer than 256 bytes of data very quickly. When larger blocks of data are moved, the additional 6502 instructions required can make the process very slow. The EXPAND and CONTRACT routines circumvent this by using the less-than-256-byte fast-move capabilities in the movement of thousands of bytes. The end result is a set of very fast and very complex data movement routines. All of this complexity does have a drawback. The infamous Atari BASIC lock-up problem lives in these two routines. If an EXPAND or CONTRACT requires that an exact multiple of 256 bytes be moved, then the routines move things from the wrong 20
Chapter Three place in memory to the wrong place in memory, whereupon the computer locks up and won't respond. The only way to avoid losing hours of work this way is to SAVE to disk or cassette frequently. EXPAND ($A881) Parameters at entry: register X = the zero page address containing the pointer to the location after which space is to be added Y = the low-order part of the number of bytes to expand A = the high-order part of the number of bytes to expand The routine creates a hole in the table memory, starting at a requested location and continuing the requested number of bytes. The routine first checks to see that there is enough free memory space to satisfy the request. It adds the requested expand size to each of the zero-page table pointers between the one pointed to by the X register and MEMTOP. Then each pointer will point to the correct address when EXPAND is done. EXPAND then creates space at the address indicated by the X register. The number of bytes required is contained in the Y and A registers. (Y contains the least significant byte, while A contains the most significant.) All data from the requested address to the address pointed to by MEMTOP is moved toward high memory by the requested number of bytes. This creates a hole of the proper size. The routine then sets Application High Memory (APHM) to the value in MEMTOP. This tells the OS the highest memory address that BASIC is currently using. EXPLOW ($A87F) Parameters at entry: register X = zero page address containing the pointer to the location after which space is to be added Y = number of bytes to expand (low-order byte only) 21
Chapter Three This is an additional entry point for the EXPAND routine. It is used when the number of bytes to be added to the table is less than 256. This routine first loads the 6502 accumulator with zero to indicate the most significant byte of the expand length. It then functions exactly like EXPAND. CONTRACT ($A8FD) Parameters at entry: register X = zero page address containing the pointer to the starting location where space is to be removed Y = the low-order part of the number of bytes to contract A = the high-order part of the number of bytes to contract This routine removes a requested number of bytes at a requested location by moving all the data from higher in the tables downward the exact amount needed to replace the unwanted bytes. It subtracts the requested contract size from each of the zero page table pointers between the one pointed to by the X register and MEMTOP. Then each pointer will point to the correct address when CONTRACT is done. The routine sets application high memory (APHM) to the value in MEMTOP to indicate to the OS the highest memory address that BASIC is currently using. The block of data to be moved downward is defined by starting at the address pointed to by the zero-page address pointed to in X, plus the offset number stored in Y and A, and then continuing to the address specified at MEMTOP. Each byte of data in that block is moved downward in memory by the number of bytes specified in Y and A, effectively erasing all the data between the specified address and that address plus the requested offset. CONTLOW ($A8FB) Parameters at entry: register X = the zero page address containing the pointer to the location at which space is to be removed 22
Chapter Three Y = the number of bytes to contract (low-order byte only) This routine is used to remove fewer than 256 bytes from the tables at a requested location by moving all the data from higher in the tables downward the exact amount needed to replace the unwanted bytes. This routine first loads the 6502 accumulator with zero to serve as the most significant byte of the contract length. It then functions exactly like CONThACT. Miscellaneous Memory Allocations Besides the tables, which change dynamically, BASIC also uses buffers and stacks at fixed locations. The Argument/Operator Stack is allocated at BASIC's low memory address and occupies 256 bytes. During pre-compiling it is used as the output buffer for the tokens. During execution, it is used while evaluating an expression. This buffer/stack is referenced by a pointer at location $80. This pointer has several names in the BASIC listing: LOMEM, ARGOPS, ARGSTK, and OUTBUFF. The Syntax Stack is used during the process of syntaxing a statement. It is referenced directly that is, not through a pointer. It is located at $480 and is 256 bytes long. The Line Buffer is the storage area where the statement is placed when it is EN'TERed. It is the input buffer for the edit and pre-compile processes. It is 128 bytes long and is referenced directly as LBUFF. Often the address of LBUFF is also put into INBUFF so that the buffer can be referenced through a pointer, though INBUFF can point to other locations during various phases of BASIC's execution.

<-Chapter 02Chapter 04->