Ram Cram: Squeezing Big Programs into Atari BASIC

Atari text screen reporting stack size 0 at start, 40 after ten leaked GOSUBs, 40 with POP, and 56 inside a FOR loop

In The Creative Atari, Robert A. Howell describes how he spent a summer squeezing the original Crowther and Woods Adventure, messages and all, into a 32K Atari 800 with only a cassette recorder. His article "Ram Cram Techniques for Atari" is one of the best pieces ever written on making Atari BASIC programs smaller. This guide works through his techniques, with every byte count re-measured on Atari BASIC revision C, plus a few extra tricks the measurements turned up.

Making Atari BASIC Faster (and Smaller) already gives the short checklist. This guide shows why each item works and how much it saves.

What you'll learn: how to measure memory, what each piece of a line costs, how to replace constants and arrays, how to pack data and text, and how to stop the GOSUB stack from slowly eating your free memory.

What you need: Atari BASIC. Some background on how lines are stored helps (see Inside a SAVEd Atari BASIC Program), but is not required.

1. Measure first

PRINT FRE(0) shows the free bytes. To see what a statement costs, note FRE(0), add or run it, and look again:

10 F=FRE(0):DIM A(100):? "DIM A(100): ";F-FRE(0)
20 F=FRE(0):DIM B$(100):? "DIM B$(100): ";F-FRE(0)
30 F=FRE(0):DIM C(9,9):? "DIM C(9,9): ";F-FRE(0)

This prints 606, 100 and 600. A numeric array element takes six bytes, and subscripts start at 0, so A(100) holds 101 numbers. A string takes one byte per character.

To measure program lines, let the program walk its own statement table. Each line's third byte is its length (see Inside a SAVEd Atari BASIC Program). Put this at the end of a program and GOTO 9000 to see every line's size:

9000 S=PEEK(136)+256*PEEK(137)
9010 L=PEEK(S)+256*PEEK(S+1):IF L>=9000 THEN END
9020 ? L;" LEN ";PEEK(S+2):S=S+PEEK(S+2):GOTO 9010

2. What things cost

Measured with the routine above:

Line Bytes
10 REM 6
20 REM HELLO 11
30 A=0 15
40 A=B 9
50 A=0:B=0 27
60 GOTO 1000 13
70 GOTO Z 7
100 PRINT "ABCDE" 13
110 DATA 1,2,3 11

From this you can derive the rules:

  • Every line has 6 bytes of overhead: line number, length, statement offset, the statement token, and the end-of-line marker. An extra statement on an existing line costs 3 bytes less than the same statement on a new line (compare lines 30 and 50).
  • A numeric constant costs 7 bytes wherever it appears, including line numbers after GOTO, GOSUB and THEN. A variable reference costs 1 byte.
  • A REM costs its text plus 6 bytes on its own line. It does nothing when the program runs, and it still occupies memory.
  • A string constant costs its length plus 2.
  • DATA is stored as plain text. DATA 1,2,3 costs 5 bytes for its contents, against 21 for the same three numbers as constants in a statement.

Spaces are not stored, and abbreviations such as GR. for GRAPHICS make no difference: LIST regenerates the full keyword from a one-byte token.

3. Turn constants into variables

Because BASIC re-stores a constant every time you type it, a program that says GOSUB 1000 fifty times holds fifty seven-byte copies of 1000. A variable costs about 9 bytes plus its name once (8 in the value table, the name in the name table, one more when it is used), then just 1 byte per use. Howell's rule of thumb: replace any constant or line number used four or more times.

He used a naming pattern so that constant-variables stood out from real ones: Z for 0, A to I for 1 to 9, A0 to I9 for 10 to 99, A00 and up for 100 and above. Real variables got names from J onwards. He loaded the constants in one READ at the start:

10 READ A,A0,A00,B50,F,I0,Z
20 DATA 1,10,100,250,6,90,0
40 DIM COUNT(A00)
50 FOR J=A TO A00
60 IF INT(RND(Z)*A0)+A>F THEN GOTO I0
70 GOSUB B50
80 COUNT(J)=COUNT(J)+A
90 NEXT J

Note THEN GOTO I0: a line number after THEN must be a constant, so a variable needs an explicit GOTO. For a constant used only two or three times, combine existing variables: GOTO D+E costs 3 bytes against 7. Converting 58 constants and line numbers saved Howell more than 3,500 bytes.

The ceiling is 128 variable names. Arrays take only one name each, however large they are.

4. Pack lines, but mind the IF

Joining statements saves 3 bytes each time. Howell's Adventure had about 720 statements on 325 lines, a saving of nearly 1,200 bytes. The trap is IF. Everything after THEN on the same line runs only when the condition is true:

100 SUM=0:FOR I=1 TO 10:IF A(I)>0 THEN SUM=SUM+A(I)
130 NEXT I:PRINT SUM

Putting NEXT I:PRINT SUM on line 100 would make them conditional too. Use the IF to your advantage instead. Setting a default and then overriding it removes a branch:

100 X=10:IF L=R THEN X=20

Two other one-line patterns: ON X-1 GOTO 200,300,400:T=0:GOTO 1000 falls through to the rest of the line when X is 1 (or out of range). And a NOT can fold a branch around a block into one line.

5. Shorter ways to say the same thing

Line sizes for some common idioms, measured:

Idiom Bytes
IF B=0 THEN B=1:GOTO 30 plus B=0 on the next line 52
B=ABS(B-1) 20
B=1-B 17
B=NOT B 10

All four flip B between 0 and 1. NOT returns 1 for zero and 0 for anything else. Similarly:

Condition Bytes
IF NOT (A=1 AND B>5) THEN B=B-1 42
IF A<>1 OR B<=5 THEN B=B-1 39

Rewriting a NOT with De Morgan's rule (swap AND and OR, invert each comparison) is shorter. Howell also advises always putting NOT and its operand in brackets, because of a known Atari BASIC bug.

Where the same statement appears many times, keep one copy and GOTO or GOSUB it. Howell found Z=B:GOTO 90 sixteen times and saved 90 bytes by keeping one.

6. Arrays: the biggest win

A numeric array costs six bytes per element. A table of 126 rooms by 10 exits would need 7,560 bytes. Howell had three alternatives:

Use a string for small values. A flag per room fits in a 100-byte string instead of a 606-byte array:

100 DIM R$(100):FOR I=1 TO 100:R$(I,I)="N":NEXT I
110 R$(ROOM,ROOM)="Y":REM MARK A VISITED ROOM

Any value from 0 to 255 fits in one character with CHR$ and ASC.

Leave constant tables in DATA. Put each room's exits on a DATA line whose number you can compute, then RESTORE straight to it:

100 RESTORE 10000+RC:FOR J=1 TO DR:READ RN:NEXT J

RESTORE to a line that does not exist starts at the next line that does. We checked this: RESTORE 75 with DATA on lines 70 and 80 reads line 80's value. Howell therefore put three rooms on every third line number (10003, 10006 …) and adjusted the loop, removing two-thirds of the line overhead.

Compress the data. Most exits were zero, so he replaced each run of n zeros with the single number −n and expanded it in the read loop. With these steps the room table fell from 7,560 bytes to 2,236.

One warning: DIM does not clear numeric arrays. In our test a value stored in A(5), followed by CLR and a fresh DIM A(10), was still there. If an array must start at zero, clear it with a one-line FOR loop. Simple variables are set to zero, and strings to empty, by RUN.

7. Text

About half of Adventure is text. Howell's methods:

  • Keep messages in DATA, one message per computable line number (RESTORE 15000+N*10), with a marker character at the end of each so a variable-length message can span several DATA lines.
  • Rewrite and abbreviate. One room description went from 204 to 147 characters without losing anything important.
  • Factor out common phrases. 63 descriptions began with "You are in ". He removed the phrase and had the print routine add it whenever a message did not begin with a capital letter, saving about 600 bytes.
  • Keep only the first five letters of vocabulary words, and truncate the player's input to match.

Keep an eye on speed. Searching a long DATA vocabulary from the start made responses take five to ten seconds. Grouping words by first letter on separate DATA lines, and RESTOREing to the right one, brought most responses down to one or two seconds.

8. Clean out the variable table

Every name you have ever typed, including typos and names used only in direct mode, stays in the tables and keeps its 8 value bytes. SAVE and CSAVE preserve the junk. Rebuild the tables instead:

LIST "D:PROG.LST"
NEW
ENTER "D:PROG.LST"

(Use LIST "C:" and ENTER "C:" on tape.) This also cures ERROR 4, too many variables, when the program no longer really uses 128 names.

9. Don't leak the stack

Howell's finished game had 50 bytes free, yet after an hour or two of play it died with ERROR 2, memory insufficient. The cause was subroutines that jumped out with GOTO instead of RETURN. Each GOSUB pushes an entry onto BASIC's run-time stack. We measured 4 bytes per GOSUB and 16 per active FOR loop, using MEMTOP minus RUNSTK (locations 144–145 and 142–143). Ten GOSUBs that never returned left 40 bytes on the stack. The same loop with a POP before each jump left nothing new.

Try it:

10 N=0:? "STACK AT START: ";PEEK(144)+256*PEEK(145)-(PEEK(142)+256*PEEK(143))
20 GOSUB 100
100 N=N+1:IF N<10 THEN 20
110 ? "AFTER 10 LEAKED GOSUBS: ";PEEK(144)+256*PEEK(145)-(PEEK(142)+256*PEEK(143))
120 N=0
130 GOSUB 150
150 POP :N=N+1:IF N<10 THEN 130
160 ? "WITH POP: ";PEEK(144)+256*PEEK(145)-(PEEK(142)+256*PEEK(143))
170 FOR I=1 TO 2:? "INSIDE FOR: ";PEEK(144)+256*PEEK(145)-(PEEK(142)+256*PEEK(143)):NEXT I

So: leave every subroutine by RETURN, or POP its entry before jumping away. Howell put a few POPs just before the main INPUT, where the stack should be empty anyway. A POP on an empty stack does nothing. Be careful inside FOR loops, though. FOR entries share the same stack, and popping one leads to ERROR 13 at the NEXT.

Troubleshooting

  • ERROR 2 after the program has run for a while: a stack leak (section 9), or strings and arrays DIMmed inside a loop.
  • ERROR 4: 128 names in use. Clean the table with LIST/ENTER, or combine variables into an array.
  • Savings smaller than expected: check that you used the variable everywhere. One forgotten constant still costs 7 bytes each time.
  • Program slower after cramming: DATA searches and RESTORE loops cost time. Group data so each lookup reads only a few items.

Further reading

  • Robert A. Howell, "Ram Cram Techniques for Atari: Original Adventure in 32K", in The Creative Atari (Creative Computing Press, 1983).
  • De Re Atari (Atari, Inc., 1982), the chapter on Atari BASIC: memory-saving checklist.
  • Carl M. Evans, Atari BASIC Faster and Better (IJG, 1983).
  • On this site: Making Atari BASIC Faster (and Smaller), Inside a SAVEd Atari BASIC Program, Atari BASIC String Handling and Tricks.

Credits