How was a line of Commodore 64 BASIC code stored in its memory?

Question

I am reading up on old C64 stuff and I am using the Vice emulator to play with it. Currently I am studying about how the C64 stored BASIC programs in RAM.

This is quite clear (it starts on address $0800 and goes from there, etc) and the Vice monitor shows me everything.

When reading about this on Wikipedia, and also on c64-wiki, it says it stored the line number first, followed by a pointer to the next line. However, when I check the memory in the Vice monitor, I can see it is the other way round: first a pointer, then the line number:

10 PRINT "HELLO WORLD"
20 PRINT "BYE BYE"

C:0800  00 15 08 0a  00 99 20 22  48 45 4c 4c   ...... "HELL
C:080c  4f 20 57 4f  52 4c 44 22  00 25 08 14   O WORLD".%..
C:0818  00 99 20 22  42 59 45 20  42 59 45 22   .. "BYE BYE"

The 15 08 before 0a 00 is clearly a pointer and 0a 00 is clearly a line number.

My question is simple, are the docs wrong, or is the Vice emulator different from the 'real thing' ?

Answer 1

Trust Vice.

The information you obtained elsewhere is incorrect. Each line of the BASIC program is preceded by a pointer to the next line. Then, comes the line number.

Following this is the tokens that make up the actual BASIC code of the line, and terminated by a null ($00). Then starts the next line (#2) with a pointer to line #3. The end of the BASIC program is indicated when the pointer to the next line equals $0000. That is, three nulls in a row.

Technically, your BASIC program actually starts at $0801, as that is the location of the low-byte of the first pointer to the next line (line #2).

This is the start of BASIC for the C64. The VIC-20 and PET start at $0401 and the C128 starts at $1C01.

Notes:

1. On the VIC-20, the start of BASIC actually moves around, depending on expansion memory being installed.

2. Interestingly, the Commodore disk drives, which return a directory listing in the format of a BASIC program (i.e. LOAD "$",8), always use $0401 as the base, and this behavior dates back to the PET. However, later Commodore kernals "fix-up" the directory listing to move it to the start of BASIC for that machine.

Answer 2

As discussed and linked in this thread, Norbert Landsteiner has written a series of blog posts on masswerk.at that cover Commodore BASIC V2 internal program and data representation in detail and giving some code to do renumbering of BASIC programs and other interesting things. (He does this on a PET with v2 ROM; C64 is substantially similar but see my further notes below.)

• BASIC (Re)Numbering — with Commodore
• BASIC Variables & Strings - with Commodore
• Writing a PET 2001 Ten-Line Cañon Run Video Game

His first article gives some excellent diagrams and breakdowns of the binary format. The program lines are stored as a linked list with the link to the next address in the first two bytes, the line number in the following two bytes, and then the line text and tokens followed by a zero byte:

The full breakdown of the first line of his sample program is:

The whole series is well worth reading; you'll learn a lot about the internal formats and the tricks you can play with them.

Pointers to BASIC Data Structures

Landsteiner's examples are done on a PET with V2 ROMs, but the VIC-20 and the C64 also use V2 BASIC are substantially similar, except for the zero page locations, given below. You'll have noticed that the start address of BASIC (program) text in his examples above is $401 whereas in your C64 it's $801; this is actually variable not only across models but within a particular model (for example, on the VIC-20 it depends on whether and how the memory has been expanded).

So rather than using a fixed location, you and your programs should always use the value in the TXTTAB pointer from the zero page. You should do the same for the start locations of other areas used by BASIC as well. Landsteiner provides the details of these:

label    loc.hex   loc.dec  description

• C64 and VIC-20
TXTTAB  002B-002C   43-44   Pointer: Start of BASIC Text
VARTAB  002D-002E   45-46   Pointer: Start of BASIC Variables
ARYTAB  002F-0030   47-48   Pointer: Start of BASIC Arrays
STREND  0031-0032   49-50   Pointer: End of BASIC Arrays (+1)
FRETOP  0033-0034   51-52   Pointer: Bottom of String Storage
FRESPC  0035-0036   53-54   Utility String Pointer
MEMSIZ  0037-0038   55-56   Pointer: Highest Address Used by BASIC

• PET 2001 ROM 2.0 ("new ROM")
TXTTAB  0028-0029   40-41   Pointer: Start of BASIC Text
VARTAB  002A-002B   42-42   Pointer: Start of BASIC Variables
ARYTAB  002C-002D   44-45   Pointer: Start of BASIC Arrays
STREND  002E-002F   46-47   Pointer: End of BASIC Arrays (+1)
FRETOP  0030-0031   48-49   Pointer: Bottom of String Storage
FRESPC  0032-0033   50-51   Utility String Pointer
MEMSIZ  0034-0035   52-52   Pointer: Highest Address Used by BASIC

• PET 2001 ROM 1.0 ("old ROM")
TXTTAB  007C-007D  124-125  Pointer: Start of BASIC Text
VARTAB  007E-007F  126-127  Pointer: Start of BASIC Variables
ARYTAB  0080-0081  128-129  Pointer: Start of BASIC Arrays
STREND  0082-0083  130-131  Pointer: End of BASIC Arrays (+1)
FRETOP  0084-0085  132-133  Pointer: Bottom of String Storage
FRESPC  0086-0087  134-135  Utility String Pointer
MEMSIZ  0088-008A  136-137  Pointer: Highest Address Used by BASIC

• TXTTAB is none other than our old friend, the start of BASIC.
• VARTAB is the start of the variable space. It follows immediately after the end of the program in memory (the final empty line-link.) Simple variables are stored here. Each variable occupies 7 bytes of memory, regardless of the type. ARYTAB points to the next available space.
• ARYTAB is (also) the beginning of the space allocated for array storage. It points to the location following immediately after the last byte allocated for simple variables. Note: Since arrays are stored directly above simple variables, adding a new simple variable requires all arrays to be moved in memory in order to provide the required space!
• STREND is the lower end of the space used for storing string literals. (Strings grow from top to bottom.) This is also the beginning of any free memory, which hasn’t been allocated yet, between the array space and any stored string literals. FRETOP marks the top end of the unallocated memory, below the last allocated string.
• FRESPC Is a utility pointer used internally by BASIC. It is not directly involved in variable management, but used for string handling (scratch space, etc).
• MEMSIZ is the top address of accessible memory. Strings start growing down from here.

You can find the full set of C64 zero page locations and the purposes in the "Commodore 64 Memory Map" section starting on page 310 of the Comodore 64 Programmer's Reference Guide.