Monthly Archives: February 2017

Color BASIC String Theory, part 1

See also: part 1 and part 2.

Many aspects of Microsoft Color BASIC have always been magic to me. I never gave too much thought to how the BASIC interpreter does what it does.

String variables are one thing we all had to know a bit about. By default, Color BASIC sets aside 200 bytes for strings. If you use more, or less, you learned about using the the CLEAR command:

CLEAR 1000 'RESERVE 100 BYTES FOR STRINGS

CLEAR erases all variables, so it has to be done before you define any:

10 A=1
20 PRINT A
30 CLEAR
40 PRINT A
RUN
1
0

We can test CLEAR from BASIC.

If we reserve only ten bytes for strings:

CLEAR 10

…then we should be able to create a ten-character or less string:

A$="1234567890"

But, if we try to create anything longer than ten characters, we get an Out of String Space error (?OS ERROR):

CLEAR 10 means 11-character strings need not apply.

Any variables you create from the command line will be stored in string memory. But, strings can also be embedded in a BASIC program and not use any string memory:

10 CLEAR 10
20 A$="THIS STRING TAKES UP NO STRING MEMORY"

In the above example, A$ points to the text embedded inside the BASIC program. It can, therefore, be as long as a string can be since it takes up no string memory.

Consider this example… If you have 30 bytes reserved for strings, you should be able to make three 10-byte strings in memory:

10 CLEAR 30
20 A1$="1234567890" 'WORKS
30 A2$="1234567890" 'WORKS
40 A3$="1234567890" 'WORKS
50 A4$="X" '?OS ERROR!

Oops!

If you run that, it works just fine because those strings are being stored in the program, and NOT in string memory. I caught myself not paying attention to my own article!

To force a string to live in string memory, we have to do something to force BASIC to move it there. If the string is NOT declared as a contiguous string of text, BASIC has no choice but to make it in string memory:

20 A1$="12345"+"67890"

That is enough to do it. A1$ will be represented as “1234567890” somewhere in string memory.

And BASIC is not too smart. In this example, it looks like BASIC still COULD keep it in program memory (the string is contiguous), but it does not:

20 A1$="1234567890"+""

That will force the string in to string memory, and now the program will fail with an ?OS ERROR on line 40:

NO STRING MEMORY FOR YOU!

With that said, let’s see what we must do to avoid a program from crashing due to running out of string space…

First, we need to understand how much string memory the program needs and make sure we CLEAR that much. Suppose we wanted the user to enter a password of up to 10 characters. We could do this:

10 CLEAR 10
20 LINE INPUT "PASSWORD?";A$

If we run that, we can type up to 10 characters and press ENTER and it should work fine. BUT, if the user typed more than 10 characters, it will crash with an ?OS ERROR.

The INPUT and LINE INPUT commands actually lets you type up to 249 characters before it stops you, so if the programmer didn’t CLEAR extra string space, typing in a long line might be enough to crash the program.

As a programmer, if we plan to use INPUT, we need to have 249 bytes more than whatever string space we plan to use.

If we are going to be doing any string manipulation, we need to leave extra room for that, too.

Thus, if I was expecting the user to type in a 10 character password, and a 20 character username, and I know INPUT allows the user to type up to 249 characters, I guess I need this:

10 CLEAR 10+20+249

BUT, it will be important that the username and password strings are limited to just 10 and 20 characters. We can use LEFT$ to trim them down in case someone “accidentally” types too much:

10 CLEAR 10+20+249
20 LINE INPUT "USERNAME:";NM$:NM$=LEFT$(NM$,10)
30 LINE INPUT "PASSWORD:";PW$:PW$=LEFT$(PW$,20)

That code should now be bulletproof against a user typing in long strings at both those input prompts.

Side Note: The 249 value may be specific to the Microsoft Color BASIC on the Radio Shack Color Computer. Other versions of BASIC may have different input lengths and differences. I’d be curious to know what is similar or different on Atari BASIC, Commodore BASIC, etc.)

Basically, we must make sure our CLEAR command covers the maximum characters the variable is allowed to contain, plus any extra required by something like INPUT.

However, there are other things that use temporary string space we must also account for. Suppose we were going to combine the username and password along with a numeric access level (say, 0-255) in to a string, using some character to separate them:

USERNAME\PASSWORD\255

This is basically what I did for my 1983 ALLRAM BBS for the userlog. Rather than using three different arrays – an array of usernames, an array of passwords, and an array of levels – wanted to just use one string array. This was because every variable (or array element) uses 5-7 bytes of memory (more details on this in a future article). The less variables, the less memory you use, so combining multiple elements in to one string saved me quite a bit.

My maximum size for a userlog “record” becomes:

  • 20 bytes for the username
  • 1 byte for the delimiter character
  • 10 bytes for the password
  • 1 byte for the delimiter character
  • 3 bytes for the level number

A fully loaded userlong string would be:

12345678901234567890\1234567890\123 = 35 bytes

Therefore, if I was going to make such a record, I’d need 35 bytes for each record I allowed. For example, if I wanted five users, I’d need to reserve enough memory for five of those userlog strings, plus room to input a username and password, and the extra overhead for the INPUT buffer just in case the user tries to type too much:

10 CLEAR 5*35+20+10+249
20 DIM UL$(4) 'BASE 0, SO 0-4
30 FOR A=0 TO 4
40 PRINT "USERNAME";A;":";
50 LINE INPUT NM$:NM$=LEFT$(NM$,20)
60 PRINT "PASSWORD";A;":";
70 LINE INPUT PW$:PW$=LEFT$(PW$,10)
80 UL$(A)=NM$+"\"+PW$+"\0"
90 NEXT

If you run that, you can enter a username and password for each of the five users. There is enough memory reserved that even if every name uses the full 20 characters, and every password the full 10, it still shouldn’t crash from an Out of String Space error.

BUT … we got lucky. That extra 249 bytes we reserved for the INPUT buffer is actually keeping this from crashing on line 80. This is because line 80 has to create a new temporary string, so there has to be room to hold the original NM$ and PW$ plus room to create the new copies of those strings with the delimiter characters and the level at the end. Even though this string only exists for a moment, it still has to exist somewhere.

Let’s remove the 249, and ONLY TYPE the max characters (10 or 20):

10 CLEAR 5*35+20+10

Now if we run, we get a different result:

Sorry my program crashed, sir. I thought I covered all the string memory usage…

Even though we had enough memory to hold our temporary 20 character username (used by INPUT) and 10 character password (also used by INPUT), plus enough memory to hold the combined userlog strings, line 80 needed even more to create the new string.

Usually we just give CLEAR more memory and be done with it, which is fine for casual BASIC programming and if you have plenty of memory. But if you are needing every last byte of memory for a huge program or one with tons of variables and strings, maybe we can’t waste any.

I wondered how much this needed, so I wrote this test:

10 CLEAR 20+10+35
20 NM$="12345678901234567890"+""
30 PW$="1234567890"+""
40 UL$=NM$+"\"+PW$+"\255"

I used the +”” to force the strings to be placed in string memory.

It looks like this should work since the new UL$ will only contain the 20 character username plus 1 character delimiter plus 10 character password plus 1 character delimiter plus 3 character level…

But, during the process of building the UL$, it seems multiple temporary strings are created.

From trial and error, I found that adding 31 bytes was enough to make it work:

10 CLEAR 20+10+35+31

31 bytes doesn’t really fit anything we have. That’s the 20 character name plus delimiter plus password … but what about the rest? There’s still the delimiter plus three character level at the end: “\255”

Look at line 40 … see the “\255”? That’s where the extra four bytes are. It looks like BASIC doesn’t need to count that string since it’s already in the code. It still needed one byte for the first delimiter, though, so perhaps being at the end matters?

If I try this:

40 UL$=NM$+"\255\"+PW$

…then it works with 25 extra bytes. Er… It looks like it’s not that the last part was a four character string. It looks like it’s just the “last” element. In this case, the password is 10 characters, so that would get us back to our 35 character string size we reserved.

Let’s test this further:

40 UL$=PW$+"\255\"+NM$

Now it works with 15 extra bytes. That’s the password (10 characters) plus the bit in the middle (5 characters, “\255\”).

This tells me that whatever string manipulation is happening, BASIC only needs string memory for everything but the last manipulation. Thus, if I had something like this:

10 CLEAR 11+10
20 A$="12345"+"67890"+"X"

As I expected … I need enough reserve string space for it to build the first part of the string in a temporary location, before doing the final assignment of temporary + final bit.

Thus:

10 CLEAR 10+9
20 A$="123"+"456"+"789"+"0"

Now that I work through it, it makes perfect sense. Above, BASIC is creating a temporary string and doing this:

  • store “123” in temporary string (usage: 3 bytes)
  • store “456” in temporary string (usage: 6 bytes)
  • store “789” in temporary string (usage: 9 bytes)
  • copy temporary string to A$ and append “0” (usage: 10 bytes)

This seems to be a good educated guess, but could be confirmed by consulting the source code.

I guess it looks like the amount of temporary string usage can be predicted just by looking at all the places in the code where string manipulation is done, and calculating which one is the largest and adding that much extra string space.

BUT, there are other rules for things like LEFT$, MID$, RIGHT$, HEX$, etc.

10 CLEAR 9+4
20 A$="12345"+HEX$(65535)

Above, that needs 4 extra bytes to create the HEX$ string (“FFFF”) and then append it.

10 CLEAR 10+5
20 A$="12345"+LEFT$("67890ABCDEF",5)

Above, we need 5 extra bytes for the temporary 5 byte string that LEFT$ is going to create and append.

10 CLEAR 10+5
20 A$="12345"+MID$("ABCDEFG",1,5)

Above, 5 extra bytes are needed because MID$ creates a 5 byte string to append.

Now it all makes sense.

Wow. That was one heck of a tangent.

I am going to say it’s probably save to just add an extra 255 to whatever string space you think you are using, since no string can ever be larger than 255. I guess I’ll have to test that sometime, too.

Next time, I’ll get back to my point…

Building a Better BASIC Input

It looks like I am going to be writing an update to my 1983 *ALLRAM* BBS. It was a simple bulletin board system that could be operated from cassette (no disk drives required!).

I have decided to use this as an excuse to create a few more articles that will allow me to experiment with better ways to do things a BBS might need to do.

Today … Custom input.

Custom Input

BASIC’s INPUT and LINE INPUT commands are very useful, but no matter how much data you really want, on the CoCo’s Color BASIC these commands allow the user to enter up to 249 characters. Because of this, you always have to truncate the string to what you really want it to be after input:

10 LINE INPUT "NAME :";NM$:NM$=LEFT$(NM$,20)

Still, since BASIC is in control, the user could easily type well more than 20 characters and clutter up the display. Allowing the user to type super-huge strings can also be the cause of a program crash due to Out of String Space errors (more on this in an upcoming article about Strings).

If you want more control over how much, and even what. is allowed to be typed, you can write your own custom input routine.

In a previous article, we looked at using INKEY$ to respond to single-key presses. A brute-force version might look like this:

10 PRINT "YES OR NO? ";
20 A$=INKEY$:IF A$="" THEN 20
30 IF A$="Y" THEN 100
40 IF A$="N" THEN 200
50 PRINT "YES OR NO ONLY, PLEASE!"
60 GOTO 10
100 PRINT "YES!"
110 END
200 PRINT "NO!"
210 END

You could turn that in to a subroutine and call it any time you wanted a YES or NO answer.

One problem with that is it only checks for UPPERCASE “Y” and “N”, so it won’t recognize lowercase. We’d need to add a bit more…

30 IF A$="Y" OR A$="y" THEN 100
40 IF A$="N" OR A$="n" THEN 200

If you had a dozen choices, that would get messy real quick.

To easily handle more choices (and make it faster), we also looked at using INSTR to turn the keyboard choice in to a number, and dispatching it with ON GOTO/GOSUB. Here is a routine that would handle UPPERCASE and lowercase:

10 PRINT "YES OR NO? ";
20 A$=INKEY$:IF A$="" THEN 20
30 LN=INSTR("YyNn",A$):IF LN=0 THEN PRINT"YES OR NO ONLY!":GOTO 20
40 ON LN GOTO 100,100,200,200
50 GOTO 20
100 PRINT "YES!"
110 END
200 PRINT "NO!"
210 END

See what we did there? Now we scan for four characters, “YyNn”, and if it’s one of the first two, we go to the Yes routine on line 100, or for the last two, we go to the No routine on line 200.

We could have also checked the key pressed to see if it was in lowercase and, if it was, convert it to uppercase. Then we only have to compare for uppercase:

10 PRINT "YES OR NO?"
20 A$=INKEY$:IF A$="" THEN 20
25 CH=ASC(A$):IF CH>96 AND CH<123 THEN A$=CHR$(CH-32)
30 LN=INSTR("YN",A$):IF LN=0 THEN PRINT"YES OR NO ONLY!":GOTO 20
40 ON LN GOTO 100,200
50 GOTO 20
100 PRINT "YES!"
110 END
200 PRINT "NO!"
210 END

Line 25 converts the key the user pressed in to the ASCII value. If that value is greater than 96 (the character right before lowercase “a”) and lower than character 123 (the character right after lowercase “z”) it makes A$ the character 32 lower from it, which shifts it from where the lowercase ASCII characters are (97-122) down to the uppercase ASCII characters (65-90).

Benchmark Digression

Note that I chose to check CH>96 (the character BEFORE “a”) instead of CH>=97 (it’s easier to understand what that is, since 97 is “a”). I figured doing “>” instead of “>=” would be a bit quicker since there is less to parse.

I could have also compared the string directly:

40 IF A$>="a" AND A$<="z" THEN A$=CHR$(ASC(A$)-32)

…but I figured that would be slower.

I don’t need to “figure.” Let’s do a few quick tests using the benchmark program:

0 DIM A$,C:A$="*"
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
40 C=ASC(A$):IF C>=97 AND C<=122 THEN A$=CHR$(C-32)
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

Converting the string to a number, then comparing using >= and <= produces 960. Wow. That’s slow.

By adjusting the range being compared so we can remove the “=”:

40 C=ASC(A$):IF C>96 AND C<123 THEN A$=CHR$(C-32)

..produces 950. Okay, so the overhead of “>=” versus “>” is not very significant (parsing one extra byte). But, if every little bit helps…

We also learned that HEX numbers were faster, so one quick speed improvement would be to try them like this:

40 C=ASC(A$):IF C>&H60 AND C<&H7B THEN A$=CHR$(C-32)

This drops the 950 to 721. At the very least, we should be using HEX.

What about using string comparisons instead?

40 IF A$>="a" AND A$<="z" THEN A$=CHR$(ASC(A$)-32)

Comparing a one character string variable to a constant string character produces 537! I think we have a winner. It’s almost twice as fast as the original version in this benchmark. And, dropping the “=” would make it a tad faster. But what character is that?

From the Wikipedia ASCII table, before “a” is some backwards apostrophe thing, “`”… But I don’t know how to type that on the CoCo keyboard in BASIC. After the “z” is the left curly brace, “{” and I’m not sure how to type that in BASIC either.

I *could* put them both in strings, like:

X$=CHR$(96):Y$=CHR$(123)

…then later, compare against those:

IF A$>X$ AND A$<Y$ THEN ...

…but the tiny speed saving might not be worth the loss of memory for two extra variables. I guess my point is, this could still be made a tad faster, but it seems using strings is faster, so let me revise my original example:

10 PRINT "YES OR NO?"
20 A$=INKEY$:IF A$="" THEN 20
25 IF A$>="a" AND A$<="z" THEN A$=CHR$(ASC(A$)-32)
30 LN=INSTR("YN",A$):IF LN=0 THEN PRINT"YES OR NO ONLY!":GOTO 20
40 ON LN GOTO 100,200
50 GOTO 20
100 PRINT "YES!"
110 END
200 PRINT "NO!"
210 END

But I digress…

End of Benchmark Digression

Now we only check for UPPERCASE letters. Since we compare against the “a-z” range, numbers and other characters are untouched. I could have just as easily made an input routine that only allowed numbers to be pressed, or a simple “Press any key to continue” routine.

These are just some simple examples of writing  a custom input routine.

But why bother?

No, not why bother with the speed optimizations above (those will make sense later). Why bother making a custom input routing at all?

Many years ago, I needed my own version of LINE INPUT that would prevent the user from typing too much. In BASIC, if you just want the first 10 characters that the user types, as I showed earlier, you can chop off just those ten characters using the LEFT$() function:

10 LINE INPUT "PASSWORD (10 CHARS MAX):";PW$
20 PW$=LEFT$(PW$,10)
30 PRINT "YOU ENTERED: ";PW$
Using LEFT$ to limit how much input you get.

This works fine, but as you can see, the user could still type more text, going down to the next line of the screen. If this input were at the bottom of the screen, the user could type so much that it would start causing the screen to scroll up. This could look messy and ruin your carefully laid out text user interface.

In my case, I was writing input routines for software we (Sub-Etha Software) would be selling and we didn’t want out carefully laid out text user interface to be ruined and look messy.

So, I put together a very simple input routine that used INKEY$ to read each character and add it to a string until the size limit was reached. When you do it yourself, you are responsible for printing the typed characters to the screen and handling things like BACKSPACE and ENTER.

A VERY simple custom input routine might look like this:

10 CLS
20 PRINT@196,"USER ID : [........]"
30 PRINT@228,"PASSWORD: [............]"
40 PRINT@196+11,;:IM=8:GOSUB 1000:ID$=IN$
50 PRINT@228+11,;:IM=12:GOSUB 1000:PW$=IN$
60 PRINT@294,"VERIFYING ACCOUNT..."
70 REM SEARCH FOR ID$ AND PW$
999 END
1000 REM IN : IM=INPUT MAX
1001 REM RET: IN$=STR, IN=SIZE
1002 REM USE: CH$
1010 IN$="":IN=0
1020 CH$=INKEY$:IF CH$="" THEN 1020
1030 CH=ASC(CH$)
1040 IF CH=8 THEN IF IN=0 THEN 1090 ELSE IN=IN-1:IN$=LEFT$(IN$,IN):PRINT CH$;:GOTO 1020
1050 IF CH=13 THEN RETURN
1060 IF CH>=32 AND CH<=127 AND IN<IM THEN IN$=IN$+CH$:IN=IN+1:PRINT CH$;:GOTO 1020
1090 SOUND 200,1:GOTO 1020
Behold! Custom INPUT!

Now we can limit what the user can type (visible characters only) and how much of them they type.

There are some problems with this… There is no cursor, so the user won’t see where they are typing. We could fix that by printing a block character before waiting for a keypress, and erasing it before updating the display:

1000 REM IN : IM=INPUT MAX
1001 REM RET: IN$=STR, IN=SIZE
1002 REM USE: CH$
1010 IN$="":IN=0
1015 IF IN<IM THEN PRINT CHR$(128);
1020 CH$=INKEY$:IF CH$="" THEN 1020
1025 IF IN<IM THEN PRINT CHR$(8);
1030 CH=ASC(CH$)
1040 IF CH=8 THEN IF IN=0 THEN 1090 ELSE IN=IN-1:IN$=LEFT$(IN$,IN):PRINT CH$;:GOTO 1015
1050 IF CH=13 THEN RETURN
1060 IF CH>=32 AND CH<=127 AND IN<IM THEN IN$=IN$+CH$:IN=IN+1:PRINT CH$;:GOTO 1015
1090 SOUND 200,1:GOTO 1015

Now we get a black block for the cursor, but it could be any printable character. I had to add some special checks so the cursor did not print if we were at the max length. That was causing it to print the cursor over the “]” on the screen. Since I control the display and input, I customized this routine specifically for that.

We could also add special modes to this routine to force all the input to be uppercase, or only allow numbers to be typed. But, the more code we add, the slower this routine gets. Fast typists may find this annoying. This is where the speed optimizations can come in handy. Some optimization ideas:

  • Remove all spaces and compact lines together.
  • The comparison numbers can be turned to HEX values, which is faster.
  • The variables used inside the loop can be declared first/earlier, so they are found faster.
  • By relocating this subroutine to the top of the program, all the GOTOs will be found faster.

I was only aware of the first point back in the 1980s when I wrote my original input routines. It looks like this time I have more optimizations to try.

And now, with the BASICs (pun intended) of an INPUT routine discussed, my next goal is to create a fast, and fancy, input routine I can use for the BBS project. I am still deciding how much I want to put in it, such as doing word wrap at the end of typing in messages and such, but I will share my progress here.

Until then…

Optimizing Color BASIC, part 9

See also: part 1, part 2, part 3, part 4, part 5, part 6, part 7, part 8 and part 9.

Have no fear! Today’s installment is a short one. It will address a few miscellaneous things I have been told about.

“.” versus “0”

In a comment posted to Part 5, Darren Atkinson (designer of the fabulous CoCoSDC interface) pointed out a place where a decimal point makes things faster!

One place where a decimal point will give an improvement is when using the value 0 in an expression. Basic will accept a stand-alone decimal point as the number 0, but it will process it faster than the ‘0’ character.

Try comparing the speed of:
IF N < 0 THEN …

with that of:
IF N < . THEN …

– Darren Atkinson

I, of course, had to test this. Using the benchmark program:

0 DIM Z
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 Z=0
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

Setting Z=0 1000 times produced the value of 178.

30 Z=&H0

Using a hexadecimal zero produced 164.

30 Z=.

And using just a period to represent zero produces … 141!

Okay, no more zeros.

Fake FOR

George Phillips chimed in about GOTO and GOSUB with a sneaky way to jump around faster:

However, because BASIC stores lines as a singly linked list the fastest places to GOTO and GOSUB are either the top of the program or anywhere after you do the GOTO/GOSUB. BASIC is clever enough to look forward if the line # is after the current one, otherwise it must search from the top.
Using a “fake” FOR/NEXT loop instead of GOTO could well be faster in such cases since it doesn’t have to search for the start of the FOR. If you have:

… whole bunch of code

1000 PRINT”Here we go.”

… do some stuff

2000 GOTO1000

It is likely faster to do this:

1000 FORX=0TO1STEP0:PRINT”Here we go.”

2000 NEXT

Possibly tricky to use in practice, but you can have a lot of FOR/NEXT loops on the stack and skip over interior ones. Fairly unpleasant, but optimizing BASIC is not a pretty undertaking.

– George Phillips

Wow. James Gerrie and Johann Klasek also mentioned this in response to Part 4. Johann gave an example:

I think something like that was in mind:

20 FOR A=. TO 1: A=. : REM FOREVER
30 ON INSTR(” UDLR”,INKEY$) GOTO 100,200,300,400,500
35 REM FALL THROUGH ACTION
40 NEXT
50 END
100 REM IDLE LOOP
110 NEXT
200 REM MOVE UP
210 NEXT
300 REM MOVE DOWN
310 NEXT
400 REM MOVE LEFT
410 NEXT
500 REM MOVE RIGHT
510 NEXT

Compared to the ON GOSUB this is some kind of “redo” or “loop retry” not reaching the fall through action in 35.

– Johann Klasek

Anytime the overhead of scanning through lines (from first line to destination) is more than the overhead of a RETURN, this would be faster (and only use a bit of extra memory for remembering where to RETURN to).

I don’t have any benchmarks for this one, but there is probably a threshold where the number of lines before the GOTO has to be more than X before this is always faster.

Thanks, Darren, James and Johann (and any others I might have missed).

Until next time…

Optimizing Color BASIC, part 8

See also: part 1, part 2, part 3, part 4, part 5, part 6, part 7, part 8 and part 9.

Arrays and Variable Length

In part 3, I demonstrated a simple “game” where you could move a character around the screen and try to avoid running in to enemies. The original version hard coded four enemies, each with their own variable. It looked like this:

0 REM GAME.BAS
5 KB$=CHR$(94)+CHR$(10)+CHR$(8)+CHR$(9)
10 CLS:P=256+16
15 E1=32:E2=63:E3=448:E4=479
20 PRINT@P,"*";:PRINT@E1,"X";:PRINT@E2,"X";:PRINT@E3,"X";:PRINT@E4,"X";
30 A$=INKEY$:IF A$="" THEN 30
40 LN=INSTR(KB$,A$):IF LN=0 THEN 30
45 PRINT@P," ";
50 ONLN GOSUB100,200,300,400
60 IF P=E1 OR P=E2 OR P=E3 OR P=E4 THEN 90
80 GOTO 20
90 PRINT@267,"GAME OVER!":END
100 IF P>31 THEN P=P-32
110 RETURN
200 IF P<479 THEN P=P+32:RETURN
210 RETURN
300 IF P>0 THEN P=P-1
310 RETURN
400 IF P<510 THEN P=P+1
410 RETURN

I then modified it to use an array for the enemy variables, so less code was needed to cycle through them, while also allowing easy changing of the amount of enemies. It looked like this:

0 REM GAME2.BAS
1 EN=10-1 'ENEMIES
2 DIM E(EN)
5 KB$=CHR$(94)+CHR$(10)+CHR$(8)+CHR$(9)
10 CLS:P=256+16
15 FOR A=0 TO EN:E(A)=RND(510):NEXT
20 PRINT@P,"*";
25 FOR A=0 TO EN:PRINT@E(A),"X";:NEXT
30 A$=INKEY$:IF A$="" THEN 30
40 LN=INSTR(KB$,A$):IF LN=0 THEN 30
45 PRINT@P," ";
50 ONLN GOSUB100,200,300,400
60 FOR A=0 TO EN:IF P=E(A) THEN 90 ELSE NEXT
80 GOTO 20
90 PRINT@267,"GAME OVER!":END
100 IF P>31 THEN P=P-32
110 RETURN
200 IF P<479 THEN P=P+32:RETURN
210 RETURN
300 IF P>0 THEN P=P-1
310 RETURN
400 IF P<510 THEN P=P+1
410 RETURN

Arrays are an easy way to reduce code. What I did not realize is how slow they are! Consider this example:

4 DIM E1,E2,E3,E4
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 E1=1:E2=1:E3=1:E4=1
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

In the test loop we simply set four different variables. Notice that the ones we use most often (inside the test loop) I have declared first in line 4. This makes them faster, since they are found earlier when BASIC looks up the variables.

This results in 576.

Instead of using four separate variables, we could use an array of four elements:

4 DIM E(3)
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 FORC=0TO3:E(C)=1:NEXT
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

Although this simplifies the code, and allows us to easily change it from 3 to more variables, it adds another FOR/NEXT loop.

The speed drops to 1408! And that’s using a one-character variable name. It might be a tad slower if I had chosen “EN” for the array or something two-characters to match the original.

It seems that, if you can get away with it, manually handling separate variables is much faster.

Arrays will win for code size, but lose for speed. I probably won’t want to use arrays to track the enemies in my BASIC arcade action games.

Can we make arrays faster? Let’s remove the FOR/NEXT loop and access them manually, so it’s as direct a compare to non-arrays as we can get:

4 DIM E(3)
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 E(0)=1:E(1)=1:E(2)=1:E(3)=1
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

Now we are doing “E(0)=1” versus “E1=1”. Arrays should still be slower because there are more characters to parse, and an array lookup as to be done.

This produces 1021. It appears that setting the variable takes about a third of the time, looking up the array another third, and the FOR/NEXT loop a third third. Or something.

As brute-force as it looks, it appears that is the faster way for handling variables even though it produces more code.

And speaking of more code…

Variable Length

One character variable names can get confusing real quick, but the two-character limit in Color BASIC isn’t much better. Well, you can specify longer variable names, but only the first two characters are honored:

USERNUM=1

…turns in to…

US=1

If you could make sure the first two characters were unique, you could make your program more readable, but you would be wasting speed and code size.

Consider this benchmark example, which uses a 10-character variable:

0 REM VARLEN.BAS '211
4 DIM USERCOUNT
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 USERCOUNT=1
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

This produces 211. It’s wasteful, since BASIC is only honoring the first two characters. Let’s try this:

0 REM VARLEN.BAS '182
4 DIM US
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 US=1
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

This produces 182. All those extra useless characters did nothing but slow things down a tad.

But using a one-character variable is the fastest we can get:

0 REM VARLEN.BAS '177
4 DIM U
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 U=1
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

This produces 177.

For the most-used variables, use a one-character variable name for the best speed.

And remember, every time a variable is references, BASIC has to start with the first variable it knows about and walk through all of them until it finds a match. That is the purpose of the DIM statements in lines 4 and 4. They are declaring variables in the priority of most-used to least, sorta. The variable used in the inner FOR/NEXT loop is U, so I declare it first.

If I had done U last:

0 REM VARLEN.BAS '177
5 DIM TE,TM,B,A,TT
6 DIM U
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 U=1
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

This slows it down to 188.

Putting it all together: Avoid arrays, use one-character variable names, and variables you want to be the fastest should be declared earlier.

Just an FYI.

Interfacing assembly with BASIC via DEFUSR, part 6

See also: part 1, part 2, part 3, part 4, part 5 and part 6.

Previously, we finally got to do something semi-useful with assembly: we replaced a slow full-screen scrolling routine in BASIC with a turbo-charged assembly routine, all called via the DEFUSR command.

Today, let’s apply this concept a bit further with the shell of a Pac-Man style video game written in BASIC, but enhanced with assembly.

In my Optimizing Color BASIC, part 3 article, I set the groundwork for writing a game in BASIC that involved moving a character around the screen and detecting collisions with enemy characters. Today I will combine that with the previous maze demo and create the world’s easiest Pac-Man game (no enemies, and no bothersome dots to eat).

The Maze

A few years ago, I started toying with a video output project for the Arduino computers. I began by simply bouncing a circle around the screen and then, for some reason, turned that in to an animated Pac-Man. This led me to digging in to some wonderful websites that had reverse engineered the original Pac-Man source code to explain how everything worked. You can find the series here:

http://subethasoftware.com/2014/02/09/arduino-pac-man-project/

Although I have yet to finish the game, I learned quite a bit about how Pac-Man works, including how the ghosts behave. I don’t know if BASIC would be fast enough to handle the logic of four ghosts and all the other stuff, but it sure would be fun to try — it would be much easier to write it in BASIC than C, I think.

But I digress.

The reason I mention this series is so I can show this picture:

Pac-Man!

For the Arduino project, I started with a screen shot of the original game and downsized it to fit the low resolution, black and white Arduino TVOut graphics library. It ended up looking like this:

Arduino Pac-Man!

Pac-Man was designed on a tile system. The original game resolution was 224×288. The screen was made up of 8×8 tiles, 28 across and 36 down. Without the score lines at the top and the players left lines at the bottom, the playfield itself was 28×31. The maze tiles looked like this:

Pac-Man maze tiles.

…and since the CoCo’s screen is 32×16, if we used one character per tile, we could replicate the same horizontal dimensions, but we’d need to scroll up and down to get to all 31 lines of the maze.

I was initially working on this for a 4K programming challenge I started (and have yet to complete). Using ASCII, the make looks like this:

XXXXXXXXXXXXXXXXXXXXXXXXXXXX
X            XX            X
X XXXX XXXXX XX XXXXX XXXX X
X X  X X   X XX X   X X  X X
X XXXX XXXXX XX XXXXX XXXX X
X                          X
X XXXX XX XXXXXXXX XX XXXX X
X XXXX XX XXXXXXXX XX XXXX X
X      XX    XX    XX      X
XXXXXX XXXXX XX XXXXX XXXXXX
     X XXXXX XX XXXXX X     
     X XX          XX X     
     X XX XXX--XXX XX X     
XXXXXX XX X      X XX XXXXXX
          X      X          
XXXXXX XX X      X XX XXXXXX
     X XX XXXXXXXX XX X     
     X XX          XX X     
     X XX XXXXXXXX XX X     
XXXXXX XX XXXXXXXX XX XXXXXX
X            XX            X
X XXXX XXXXX XX XXXXX XXXX X
X XXXX XXXXX XX XXXXX XXXX X
X   XX                XX   X
XXX XX XX XXXXXXXX XX XX XXX
XXX XX XX XXXXXXXX XX XX XXX
X      XX    XX    XX      X
X XXXXXXXXXX XX XXXXXXXXXX X
X XXXXXXXXXX XX XXXXXXXXXX X
X                          X
XXXXXXXXXXXXXXXXXXXXXXXXXXXX

It may look odd presented as Xs. and the aspect ratio is different, but it’s the exact Pac-Man layout used in the arcade. Here is the full play field that will scroll on the CoCo’s 32×16 screen:

Pac-Man full maze.

Since the original Pac-Man played on a monitor that was turned sideways, it was taller than it was wider. Most home ports either shrink the screen down, or flatten it out. By scrolling, maybe we can keep the aspect ratio similar.

And this is how my ASCII Pac-Man maze came to be.

As I referenced at the top of this article, I have been covering ways to Optimize Color BASIC in another article series. A recent part discussed reading the keyboard and moving a character around the screen. I took some of this code and used it to place a character in the Pac-Man maze and move it around. I also added collision detection making sure the player could not run through any of the walls.

Today I would like to present my work-in-progress Pac-Man maze, entirely in BASIC, and the changes I made to integrate the screen moving assembly routines. The assembly calls (and all the DATA statements) are in this listing, but are commented out. The ‘commented-out ines in red are what lines to uncomment to see the assembly-enhanced version, and any line just in red is the BASIC version that would need to be commented out.

The Listing

Here is the current listing, with comments to follow explaining how it works. I have been writing this on my Mac in a text editor, then loading it in to the XRoar emulator for testing. Because of this, you will notice I put spaces between program sections to make them easier to see. When this loads in to an emulator as an ASCII program, those empty lines are ignored. It works out nice.

0 REM
1 REM      PAC-MAZE 1.00
2 REM   BY ALLEN C. HUFFMAN
3 REM WWW.SUBETHASOFTWARE.COM
4 REM
6 REM
7 REM
8 REM
9 'CLEAR200,&H3F00

10 DIM MZ$(30)

15 REM
16 REM READ MAZE IN TO ARRAY
17 REM
20 FOR A=0 TO 30:READ MZ$(A):NEXT
21 'GOSUB2000:DEFUSR0=&H3F00

25 REM
26 REM UP+DOWN+LEFT+RGHT CHARS
27 REM
30 KB$=CHR$(94)+CHR$(10)+CHR$(8)+CHR$(9)

35 REM
36 REM PLAYER/WALL/BG CHARS
37 REM
40 PC=159 'PAC-MAN CHAR
41 WC=ASC("X") 'WALL CHAR
42 BG=96 'BACKGRND CHAR

50 REM
51 REM INITIALIZATION
52 REM
60 ST=7 'SCRN START LINE
61 PM=1360 'PAC-MAN START LOC
62 DR=0 'CURRENT DIRECTION
63 DN=0 'NEXT DIRECTION

80 REM
81 REM DRAW INITIAL MAZE
82 REM
90 CLS:FOR A=0 TO 15:PRINT @A*32+2,MZ$(A+ST);:NEXT

100 REM
101 REM MAIN LOOP
102 REM
110 POKE PM,PC
120 A$=INKEY$:IF A$="" THEN 140
130 KB=INSTR(KB$,A$):IF KB=0 THEN 140 ELSE DN=KB
135 REM TRY NEXT DIRECTION
140 ON DN GOSUB 500,600,700,800
145 REM THEN TRY CURRENT DIR
150 IF DR<>DN THEN ON DR GOSUB 500,600,700,800
160 GOTO 100

500 REM
501 REM UP
502 REM
510 IF PEEK(PM-32)<>BG THEN RETURN
520 POKE PM,BG:DR=1
530 IF PM<1183 AND ST>0 THEN ST=ST-1:GOSUB 950 ELSE PM=PM-32
540 RETURN

600 REM
601 REM DOWN
602 REM
610 IF PEEK(PM+32)<>BG THEN RETURN
620 POKE PM,BG:DR=2
630 IF PM>1376 AND ST<15 THEN ST=ST+1:GOSUB 900 ELSE PM=PM+32
640 RETURN

700 REM
701 REM LEFT
702 REM
710 IF PEEK(PM-1)<>BG THEN RETURN
720 POKE PM,BG:DR=3
730 PM=PM-1:RETURN

800 REM
801 REM RIGHT
802 REM
810 IF PEEK(PM+1)<>BG THEN RETURN
820 POKE PM,BG:DR=4
830 PM=PM+1:RETURN

900 REM
901 REM SCROLL SCREEN UP
902 REM
910 FOR A=0 TO 15:PRINT @A*32+2,MZ$(A+ST);:NEXT
915 'Z=USR0(1):PRINT@482,MZ$(ST+15);
920 RETURN

950 REM
951 REM SCROLL SCREEN DOWN
952 REM
960 FOR A=0 TO 15:PRINT @A*32+2,MZ$(A+ST);:NEXT
965 'Z=USR0(2):PRINT@2,MZ$(ST);
970 RETURN

999 GOTO 999

1000 DATA "XXXXXXXXXXXXXXXXXXXXXXXXXXXX"
1001 DATA "X            XX            X"
1002 DATA "X XXXX XXXXX XX XXXXX XXXX X"
1003 DATA "X X  X X   X XX X   X X  X X"
1004 DATA "X XXXX XXXXX XX XXXXX XXXX X"
1005 DATA "X                          X"
1006 DATA "X XXXX XX XXXXXXXX XX XXXX X"
1007 DATA "X XXXX XX XXXXXXXX XX XXXX X"
1008 DATA "X      XX    XX    XX      X"
1009 DATA "XXXXXX XXXXX XX XXXXX XXXXXX"
1010 DATA "     X XXXXX XX XXXXX X     "
1011 DATA "     X XX          XX X     "
1012 DATA "     X XX XXX--XXX XX X     "
1013 DATA "XXXXXX XX X      X XX XXXXXX"
1014 DATA "<         X      X         >"
1015 DATA "XXXXXX XX X      X XX XXXXXX"
1016 DATA "     X XX XXXXXXXX XX X     "
1017 DATA "     X XX          XX X     "
1018 DATA "     X XX XXXXXXXX XX X     "
1019 DATA "XXXXXX XX XXXXXXXX XX XXXXXX"
1020 DATA "X            XX            X"
1021 DATA "X XXXX XXXXX XX XXXXX XXXX X"
1022 DATA "X XXXX XXXXX XX XXXXX XXXX X"
1023 DATA "X   XX                XX   X"
1024 DATA "XXX XX XX XXXXXXXX XX XX XXX"
1025 DATA "XXX XX XX XXXXXXXX XX XX XXX"
1026 DATA "X      XX    XX    XX      X"
1027 DATA "X XXXXXXXXXX XX XXXXXXXXXX X"
1028 DATA "X XXXXXXXXXX XX XXXXXXXXXX X"
1029 DATA "X                          X"
1030 DATA "XXXXXXXXXXXXXXXXXXXXXXXXXXXX"
1100 REM
1101 REM MAZE ARRAY TO GRAPHICS
1102 REM
1110 FOR R=0 TO 30
1120 DIM P,PL,PS,C:P=VARPTR(MZ$(R))
1130 PL=PEEK(P):PS=PEEK(P+2)*256+PEEK(P+3)
1140 FOR C=PS TO PS+PL-1
1150 PRINT CHR$(PEEK(C));
1155 IF PEEK(C)=ASC("X") THEN POKEC,175
1160 NEXT:PRINT
1170 NEXT

2000 REM
2001 REM LOAD ASSEMBLY ROUTINE
2002
2010 READ A,B
2020 IF A=-1 THEN 2070
2030 FOR C = A TO B
2040 READ D:POKE C,D
2050 NEXT C
2060 GOTO 2010
2070 RETURN 'END
2080 DATA 16128,16217,189,179,237,90,39,14,90,39,28,90,39,42,90,39,55,204,255,255,32,67,142,4,32,166,132,167,136,224,48,1,140,5,255,47,244,32,47,142,5,223,166,132,167,136,32,48,31,140,4,0,44,244,32,30,142,4,1,166,132,167,31,48,1,140,5,255,47,245,32,14
2090 DATA 142,5,254,166,132,167,1,48,31,140,4,0,44,245,204,0,0,126,180,244,-1,-1

As listed, this will do the game entirely in BASIC. Using the arrow keys, you can move around the yellow PAC-BLOCK and explore the maze. When you get near the top or bottom of the maze, the screen will sluggishly scroll so you can access the rest of the maze.

Give that a try and explore the top and bottom of the maze so you can get an idea of the speed BASIC scrolls at.

Then, to make it use the assembly language routines:

  1. Uncomment line 9. This protects memory beyond &H3F00 for the assembly language code.
  2. Uncomment line 21. This will GOSUB to the routine that reads in the assembly language and POKEs it in to memory starting at &H3F00.
  3. Comment line 910 (BASIC redraw/scroll up code).
  4. Uncomment line 915. This calls the assembly routine to scroll the screen up, then redraws a new line at the bottom.
  5. Comment line 960 (BASIC redraw/scroll down code).
  6. Uncomment line 965. This calls the assembly routine to scroll the screen down, then redraws a new line at the top.

Make those changes and re-run the program then move from top to bottom and see how much faster the scree “scrolls.”

Assembly!

And, the assembly could be made almost twice as fast, and the BASIC code could be optimized to be faster, too.

But before we do that, let’s dig in to how the code actually works.

Dissection

  • 20-21 read in all the maze lines in to an array called MZ$. The maze strings are in the DATA statements starting at line 1000.
  • 30 builds a string that contains the ASCII characters for Up, Down, Left and Right. It is much faster to use INSTR and parse through a string rather than have to build one with CHR$() inside the INSTR call every time.
  • 40-42 sets some default variables:
    • PC is the character of Pac-Man to POKE to the screen (159 is a yellow block).
    • WC is what character to use for wall detection (an ASCII “X” letter). The move code will PEEK screen memory, and not let you move in any direction that contains an “X”.
    • BG is the background character (a space) that will be used to erase Pac-Man before moving him.
  • 60-63 initialize some game play variables:
    • ST is which of the 31 lines of the maze should be the first line to display. Thus, ST=7 means we will initially draw lines 7-22 on the screen to display that middle section of the maze.
    • PM is the memory location where Pac-Man will be POKEd. The screen memory starts at 1024, so this default is somewhere in the middle of the screen under the ghost house.
    • DR is the direction Pac-Man is currently moving.
    • DN is the next direction the Pac-Man will try to move at an intersection. Like the arcade, this version will let you press UP while Pac-Man is moving left, and as soon as there is an opening in the wall, the direction will turn UP.
  • 90 draws the initial 16 maze lines that will fit on the screen.
  • 110 POKEs the Pac-Man character on to the screen (showing the yellow block).
  • 120-130 wait for one of the four keys in KB$ (up, down, left or right) to be pressed. If no key is pressed, it skips to line 140, else it sets DN (direction next) to match the key that was pressed.
  • 140 uses DN (next direction) to call a routine to try to move Pac-Man up, down, left or right.
  • 150 assumes that if DN and DR don’t match, a new direction has been pressed, so it will use DR (current direction) to call the up, down, left or right routine.
  • 160 goes back to 100 to keep doing this forever.
  • 510 is the UP routine. It will PEEK the memory location 32 bytes higher in memory (one line up from the current Pac-Man PM location) and if it is NOT the background character (ie, not some place we can move), it returns.
  • 520 POKEs the background character where Pac-Man is, erasing him, then sets DR (direction) to 1 for up.
  • 530 checks to see if the Pac-Man location is before a certain spot on the screen and that the screen is starting at a line later than the first one. If so, then the screen is allowed to scroll up (start line ST is decremented). A GOSUB to 950 will handle scrolling the screen. Otherwise, we don’t need to scroll and can just subtract 32 from the Pac-Man location, moving him up one line.
  • 540 returns us back to the main loop.
  • 610-640 is the same process for moving Pac-Man down, but we check for locations at the bottom of the screen and memory +32 from Pac-Man.
  • 710-730 is the same code for moving Pac-Man left. We never scroll left or right so we don’t have to do as much here.
  • 810-830 is the same code for moving Pac-Man right.
  • 910-920 is the routine to scroll the screen up:
    • 910 scrolls the screen up in BASIC by redrawing all 16 lines of the maze.
    • 915 uses the assembly language routine to move the screen up, then PRINTs the next line at the bottom that would be displayed.
  • 960-970 are the same thing for scrolling down.
  • 1000-1030 is the 31 line maze.
  • 2000-2090 is the assembly language loader generated by lwasm and renumbered to fix. It READs in the assembly from DATA statements and POKEs it in to memory.

Baby steps.

Next time, let’s improve this a bit.

Optimizing Color BASIC, part 7

See also: part 1, part 2, part 3, part 4, part 5, part 6, part 7, part 8 and part 9.

GOSUB Revisited

In response to part 4, William Astle wrote a very nice expansion to my musings about INKEY and GOTO versus GOSUB. If you have been following my ramblings, I highly recommend you check out his posting. Unlike me, he actually understands what is going on behind the scenes:

http://lost.l-w.ca/0x05/optimizing-color-basic-on-goto-vs-on-gosub/

One of the things he pointed out, then explained further in a comment after I didn’t understand, was how the GOSUB processing works. After the GOSUB keyword is found, BASIC acquires the line number and then scans to the end of the line or the next colon. That is where RETURN will RETURN to. This sounds as one might expect, but there was a bit of weirdness I didn’t “get” at first.

William demonstrated that anything after the line number is ignored, thus:

GOSUB 1000 I CAN TYPE STUFF HERE WITHOUT ERROR

…is valid. This surprised me. If you do this:

GOSUB 1000 I CAN TYPE STUFF HERE WITHOUT ERROR:PRINT "BACK FROM GOSUB"

…when the RETURN returns, you will see the “BACK FROM GOSUB” message printed as expected. Anything between the line number and the colon (or start of next line, whichever is found first) is ignored. William explains what is going on in his article.

This, of course, made me do some more stupid testing. First, I modified my benchmark program to run multiple tests and then average out the results. It looks like this:

0 REM BENCH.BAS
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 REM
40 REM PUT CODE TO BENCHMARK
50 REM HERE.
60 REM
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END

Then I reran my GOSUB test:

0 REM GOSUB3.BAS
5 DIM TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 GOSUB100
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END
100 RETURN

When I run this, it prints the time taken for each run, and then the average:

GOSUB benchmarks.

Now for the stupid test, I added some junk after “GOSUB 100” and filled it up to the end of the line.

Side Note: I am loading BASIC programs in ASCII, so the program lines load in as if they were being typed in. Thus, it counts the characters “100 GOSUB ” as part of it. But, as soon as you press ENTER, that line is tokenized and GOSUB becomes a 1-byte token (is it 1-byte?). Then you can EDIT the line and Xtend it and type in a few more characters. So what I show here isn’t the max line size, but it is the max line size I could load in from an ASCII BASIC file. But I digress.

My line looks like this:

30 GOSUB100 ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRST*

Now when I run this, the extra “scan to the end” time causes the benchmark to show 1507!

But who would do that? If anything, you would have a colon and real stuff after the GOSUB. So I tried this by changing the space after “GOSUB 100” to a colon and “REM”:

30 GOSUB100:REMABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOP*

Now that’s a completely legitimate line. (Pretend the ABC/123 gibberish is a really long comment.)

This benchmark shows 1508, so no real difference. When GOSUB is encountered, BASIC has to scan to the end of line or a colon, whichever comes first, so it should find the colon instantly, BUT, after the RETURN it still has to scan through that REM to find the next line. Thus, it’s the same amount of scanning.

This is a meaningless test.

With real code, you might be doing something like this:

30 GOSUB 100:PRINT "BACK FROM ROUTINE"

Or you could have written it out as two lines:

30 GOSUB 100
40 PRINT "BACK FROM ROUTINE"

I thought the first one should be faster, since it has one less line.

And combining lines is good.

Right?

Well, in my silly example #2 above, what if I moved the REM to the next line, like this:

30 GOSUB100
40 REMABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRST*

That’s basically the same, just with an extra line number.

When I run this, I get a benchmark value of … 860!

Look how much faster it is by moving code to a separate line! I guess we should use separate lines after all, then…

What’s going on here? The key seems to be the “REM” keyword. When BASIC encounters a REM, it can just skip to the next line. That makes it faster. But, it seems to be doing something different when a REM is in the middle of a line.

It appears it is faster to NOT put REMarks after a GOSUB.

30 GOSUB 100:REM MOVE PLAYER UP

…shows 266. This is slower than…

30 GOSUB 100
40 REM MOVE PLAYER UP

…which shows 220. And I’ve certainly seen programmers make use of the apostrophe REMark shortcut.

The apostrophe represents “:REM” (colon REM) so these two are the same:

30 GOSUB 100:REM MOVE PLAYER UP
30 GOSUB 100' MOVE PLAYER UP
REM versus ‘ for comments.

Thus, using the one character apostrophe may look like it saves code space versus “:REM” but it does not. It does save printer paper, though :)

But I digress…

It looks like I’m going to need another test. In the meantime, don’t put things after a GOSUB om the same line. It appears to be faster to put them on the next line:

30 REM MOVE PLAYER UP
40 GOSUB100

That is 219.

30 GOSUB100:REM MOVE PLAYER UP

That is 266!

30 GOSUB100
40 REM MOVE PLAYER UP

That is backwards. But it produces 220, so it doesn’t penalize you for being backwards.

Oh, and as Steve Bjork pointed out in the Facebook group, a faster solution is not to use REMs at all. I think I need smarter examples. There are too many real programmers watching. For you folks:

0 REM THIS TAKES 371
5 DIM Z,TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 GOSUB100:Z=Z+1
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END
100 RETURN
0 REM THIS TAKES 357
5 DIM Z,TE,TM,B,A,TT
10 FORA=0TO4:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 GOSUB100
40 Z=Z+1
70 NEXT:TE=TIMER-TM
80 TT=TT+TE:PRINTA,TE
90 NEXT:PRINTTT/A:END
100 RETURN

Easy peasy.

A few additional REMarks…

Above, I mentioned that the apostrophe represented “:REM”. Thus, doing something like this:

100 'MOVE UP

Is slower than doing:

100 REM MOVE UP

It may look smaller, but the first example is like scanning “:REM MOVE UP” and the second is just “REM MOVE UP” so it has less work to do.

And yes, I tested it inside the benchmark program:

30 REM

…is 82.

30 '

…is 90.

30 :REM

…is also 90.

I guess it’s just treating the apostrophe as “:REM” internally, or maybe it’s a 2-byte token for “:REM” versus a different 1-byte token just for “REM” or something. Dunno.

But interesting.

Until next time…

Optimizing Color BASIC, part 6

See also: part 1, part 2, part 3, part 4, part 5, part 6, part 7, part 8 and part 9.

Size Matters. Or Space Matters. You decide.

Sometimes we want to optimize for code space, and other times for variable and string space. For example, if you want to create a 32 character string like this:

<------------------------------->

…you could either declare it as a static string:

A$="<------------------------------->"

Or build it programatically like this:

A$="<"+STRING$(30,"-")+">"

The second version takes about 16 bytes less of program space because the string is generated dynamically in string memory rather than being stored in the tokenized BASIC program.

Doing it the second way seems like a good idea, but keep in mind when you make this string, somewhere in string memory will be those 32 characters, PLUS you still have the BASIC statements that created it. It’s actually larger, overall, to do it this way.

BUT, any temporary strings like that might make sense to create on-the-fly as you need them since that memory can be reused by other strings.

10 A$="<------------------------------->"
20 PRINT A$:PRINT "MAIN MENU":PRINT A$
30 INPUT "COMMAND";C$

In the above example, A$ points to that sequence of characters INSIDE the BASIC program itself. It is always there. But, if you generated the string only when needed, the memory used by A$ could be used for other purposes:

10 A$="<"+STRING$(30,"-")+">"
20 PRINT A$:PRINT "MAIN MENU":PRINT A$
30 INPUT "COMMAND";A$

Above, A$ is allocated and turned in to the long 32 character string, printed, and then the memory used by A$ can be reused by INPUT. I suppose just setting it to A$=”” might give it back, too.

This would come with a speed penalty since the creation and destruction of strings takes more CPU time than just using a static string.

I think I may have also mentioned that, even if a string is part of the BASIC program, if you do anything to it, it has to duplicate it in string memory which creates a second copy of it:

10 A$="<------------------------------->"
20 A$=A$+"HELLO"

Above, A$ initially starts out pointing inside the program itself, taking up none of that string memory. At line 20, the entire A$ gets copied in to string memory and then the extra characters are added to it. At that point, that string is now using over twice the memory (program space plus string space).

Let’s try to prove that. The CLEAR command is used to reserve memory for strings. By default, 200 bytes are reserved. We can change that by doing CLEAR 0. Here is a program that has no string memory, yet it works because the string is inside the program space:

10 CLEAR 0
20 A$="<------------------------------->"

If you run this, you can PRINT A$ and prove it exists, but the moment you try to declare a second string like B$=”HELLO” or even manipulate A$ like A$=A$+”” you will get an Out of String Space errors (?OS ERROR):

Proving strings can live inside program space.

Sometimes you choose speed over size, and sometimes you choose size over speed. Thus, you can optimize for speed (which we have been doing so far), or optimize for size.

But I digress.

Elementary, my dear DATA

Today I want to discuss DATA statements. In my assembly language series, I showed how the lwasm assembler can generate a small BASIC program that has the assembly code in DATA statements, and a small loader which will READ them and POKE them in to memory:

10 READ A,B
20 IF A=-1 THEN 70
30 FOR C = A TO B
40 READ D:POKE C,D
50 NEXT C
60 GOTO 10
70 END
80 DATA 16128,16167,142,63,14,166,128,39,6,173,159,160,2,32,246,57,84,104,105,115,32,105,115,32,97,32,115,101,99,114,101,116,32,109,101,115,115,97,103,101,46,0,-1,-1

DATA statements can contain base-10 numbers, base-16 hexadecimal numbers, or strings (and I guess base-8 octal numbers too, but who would do that?). This means you could have the data stored as numbers:

100 DATA 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
100 DATA &H0,&H2,&H3,&H4,&H5,&H6,&H7,&H8,&H9,&HA,&HB,&HC,&HD,&HE,&HF

…or as strings like “FE” or “1F” that you could READ and convert to hex numbers in the loader:

100 DATA 59,4F,55,20,4D,55,53,54,20,42,45,20,42,4F,52,45,44

When it comes to a size, hexadecimal numbers without the “&H” in front are always smaller than their base-10 equivalent. Single-digit decimal values 0-9 are single digit 0-9 in hex. Double-digit decimal values 10-15 are represented by single digit hexadecimal values A-F. Every time a value from 10-15 appears, representing it in decimal takes up twice as much space. And for three digit decimal values 100-255, those are two digit hex values 64-FF.

If you store the data as strings, like this:

100 DATA 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
101 DATA 10,11,12,13,14,15,16,17,18,19,1A,1B,1C,1D,1E,1F

…you can read each string in, and convert it to a number by adding “&H” to the start and using the VAL() function:

READ B$:B=VAL("&H"+B$)

For the decimal and hexadecimal versions, you just read it as a number:

READ B

The smallest version would be the string approach, since three digit numbers can be represented with two digits. But, doing the string conversion with VAL() makes it slower.

The fastest version would be using hexadecimal numbers since BASIC can parse hex values faster than base-10 numbers. But, this is the largest version since 255 in decimal (3 characters) or FF as a hex string (2 characters) would be represented as &HFF as a hex number (4 characters). Those numbers would take up twice as much space as the string version!

In the middle is base-10 numbers. It’s not the largest, or the smallest, or the fastest or the slowest. It makes an ideal compromise.

Let’s do a test. I have DATA statements representing values from 0 to 255. I have three versions: the first will use base-10 numbers, the second will use hexadecimal numbers, and the third will use strings that are just the hex part of the “&H” number.

Base 10 Numbers

0 REM DATADEC.BAS
10 TIMER=0:TM=TIMER
20 FOR A=0 TO 255
30 READ B
40 NEXT
50 PRINT TIMER-TM
60 END
100 DATA 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
101 DATA 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
102 DATA 32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47
103 DATA 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63
104 DATA 64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79
105 DATA 80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95
106 DATA 96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111
107 DATA 112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127
108 DATA 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143
109 DATA 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159
110 DATA 160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175
111 DATA 176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191
112 DATA 192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207
113 DATA 208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223
114 DATA 224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239
115 DATA 240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255

Hexadecimal Base-16 Numbers

0 REM DATAHEX.BAS
10 TIMER=0:TM=TIMER
20 FOR A=0 TO 255
30 READ B
40 NEXT
50 PRINT TIMER-TM
60 END
100 DATA &H0,&H1,&H2,&H3,&H4,&H5,&H6,&H7,&H8,&H9,&HA,&HB,&HC,&HD,&HE,&HF
101 DATA &H10,&H11,&H12,&H13,&H14,&H15,&H16,&H17,&H18,&H19,&H1A,&H1B,&H1C,&H1D,&H1E,&H1F
102 DATA &H20,&H21,&H22,&H23,&H24,&H25,&H26,&H27,&H28,&H29,&H2A,&H2B,&H2C,&H2D,&H2E,&H2F
103 DATA &H30,&H31,&H32,&H33,&H34,&H35,&H36,&H37,&H38,&H39,&H3A,&H3B,&H3C,&H3D,&H3E,&H3F
104 DATA &H40,&H41,&H42,&H43,&H44,&H45,&H46,&H47,&H48,&H49,&H4A,&H4B,&H4C,&H4D,&H4E,&H4F
105 DATA &H50,&H51,&H52,&H53,&H54,&H55,&H56,&H57,&H58,&H59,&H5A,&H5B,&H5C,&H5D,&H5E,&H5F
106 DATA &H60,&H61,&H62,&H63,&H64,&H65,&H66,&H67,&H68,&H69,&H6A,&H6B,&H6C,&H6D,&H6E,&H6F
107 DATA &H70,&H71,&H72,&H73,&H74,&H75,&H76,&H77,&H78,&H79,&H7A,&H7B,&H7C,&H7D,&H7E,&H7F
108 DATA &H80,&H81,&H82,&H83,&H84,&H85,&H86,&H87,&H88,&H89,&H8A,&H8B,&H8C,&H8D,&H8E,&H8F
109 DATA &H90,&H91,&H92,&H93,&H94,&H95,&H96,&H97,&H98,&H99,&H9A,&H9B,&H9C,&H9D,&H9E,&H9F
110 DATA &HA0,&HA1,&HA2,&HA3,&HA4,&HA5,&HA6,&HA7,&HA8,&HA9,&HAA,&HAB,&HAC,&HAD,&HAE,&HAF
111 DATA &HB0,&HB1,&HB2,&HB3,&HB4,&HB5,&HB6,&HB7,&HB8,&HB9,&HBA,&HBB,&HBC,&HBD,&HBE,&HBF
112 DATA &HC0,&HC1,&HC2,&HC3,&HC4,&HC5,&HC6,&HC7,&HC8,&HC9,&HCA,&HCB,&HCC,&HCD,&HCE,&HCF
113 DATA &HD0,&HD1,&HD2,&HD3,&HD4,&HD5,&HD6,&HD7,&HD8,&HD9,&HDA,&HDB,&HDC,&HDD,&HDE,&HDF
114 DATA &HE0,&HE1,&HE2,&HE3,&HE4,&HE5,&HE6,&HE7,&HE8,&HE9,&HEA,&HEB,&HEC,&HED,&HEE,&HEF
115 DATA &HF0,&HF1,&HF2,&HF3,&HF4,&HF5,&HF6,&HF7,&HF8,&HF9,&HFA,&HFB,&HFC,&HFD,&HFE,&HFF

String HEX Numbers

0 REM DATASTR.BAS
10 TIMER=0:TM=TIMER
20 FOR A=0 TO 255
30 READ B$:B=VAL("&H"+A$)
40 NEXT
50 PRINT TIMER-TM
60 END
100 DATA 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
101 DATA 10,11,12,13,14,15,16,17,18,19,1A,1B,1C,1D,1E,1F
102 DATA 20,21,22,23,24,25,26,27,28,29,2A,2B,2C,2D,2E,2F
103 DATA 30,31,32,33,34,35,36,37,38,39,3A,3B,3C,3D,3E,3F
104 DATA 40,41,42,43,44,45,46,47,48,49,4A,4B,4C,4D,4E,4F
105 DATA 50,51,52,53,54,55,56,57,58,59,5A,5B,5C,5D,5E,5F
106 DATA 60,61,62,63,64,65,66,67,68,69,6A,6B,6C,6D,6E,6F
107 DATA 70,71,72,73,74,75,76,77,78,79,7A,7B,7C,7D,7E,7F
108 DATA 80,81,82,83,84,85,86,87,88,89,8A,8B,8C,8D,8E,8F
109 DATA 90,91,92,93,94,95,96,97,98,99,9A,9B,9C,9D,9E,9F
110 DATA A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,AA,AB,AC,AD,AE,AF
111 DATA B0,B1,B2,B3,B4,B5,B6,B7,B8,B9,BA,BB,BC,BD,BE,BF
112 DATA C0,C1,C2,C3,C4,C5,C6,C7,C8,C9,CA,CB,CC,CD,CE,CF
113 DATA D0,D1,D2,D3,D4,D5,D6,D7,D8,D9,DA,DB,DC,DD,DE,DF
114 DATA E0,E1,E2,E3,E4,E5,E6,E7,E8,E9,EA,EB,EC,ED,EE,EF
115 DATA F0,F1,F2,F3,F4,F5,F6,F7,F8,F9,FA,FB,FC,FD,FE,FF

If we look at the size JUST the DATA statement lines take up (lines 100-115), here is the size breakdown:

  • DATADEC.BAS – speed 78, size 1010
  • DATAHEX.BAS – speed 49, size 1360
  • DATASTR.BAS – speed 109, size 848

As you can see, using hex values is over twice as fast as using string versions and converting them to hex.

For size, using strings is about 15% smaller in my test program than using decimal values.

If load time is important, use hex. If program space is important, use strings. Otherwise, normal decimal values are a good compromise between speed and size.

Bonus Data

One more thing… If we are going to use strings anyway, we could save more space by making the hex strings long, and parsing through them to pull out the individual hex values. Every number has to be two characters (00, 01, 02 … 0E, 0F) and this additional string parsing makes it even slower, but if code size is most important, try this:

0 REM DATASTR2.BAS
10 TIMER=0:TM=TIMER
20 FOR A=0 TO 15
30 READ B$:FOR I=1 TO 32 STEP 2:B=VAL("&H"+MID$(B$,I,2)):NEXT
40 NEXT
50 PRINT TIMER-TM
60 END
100 DATA 000102030405060708090A0B0C0D0E0F
101 DATA 101112131415161718191A1B1C1D1E1F
102 DATA 202122232425262728292A2B2C2D2E2F
103 DATA 303132333435363738393A3B3C3D3E3F
104 DATA 404142434445464748494A4B4C4D4E4F
105 DATA 505152535455565758595A5B5C5D5E5F
106 DATA 606162636465666768696A6B6C6D6E6F
107 DATA 707172737475767778797A7B7C7D7E7F
108 DATA 808182838485868788898A8B8C8D8E8F
109 DATA 909192939495969798999A9B9C9D9E9F
110 DATA A0A1A2A3A4A5A6A7A8A9AAABACADAEAF
111 DATA B0B1B2B3B4B5B6B7B8B9BABBBCBDBEBF
112 DATA C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF
113 DATA D0D1D2D3D4D5D6D7D8D9DADBDCDDDEDF
114 DATA E0E1E2E3E4E5E6E7E8E9EAEBECEDEEEF
115 DATA F0F1F2F3F4F5F6F7F8F9FAFBFCFDFEFF
  • DATASTR2.BAS – speed 172, size 624

By removing all those commas, it’s the smallest data size yet. And, since the longest line you can type* in BASIC is 249 characters…

BASIC allows for typing up to 249 characters on a line.

…you could really back some data in to it.

Side Note: *The BASIC editor allows for 249 characters, but when you press ENTER, the line is tokenized. Keywords like PRINT get reduced to smaller tokens. You may have typed a five character keyword (taking up part of that 249 byte buffer), but when you press ENTER, that five characters may be converted to a one byte token. This means it’s possible for a BASIC line to contain more valid code than you could actually type. There have been utilities for BASIC (such as Carl England‘s CRUNCH) that do this, packing program lines as big as they can be, and making them un-editable since the moment you try, they get detokenized and you lose anything past 249 characters. We’ll have to discuss this in a later installment.

With that in mind, we could pack any type of DATA in to fewer lines and save a bit. Each line number takes up 6 bytes, so every line we can eliminate makes our program smaller.

Through some trail-and-error experimentation, I got this:

0 REM DATASTR3.BAS
10 TIMER=0:TM=TIMER
20 FOR A=0 TO 15
30 READ B$:IF B$="*" THEN 50
35 FOR I=1 TO LEN(B$) STEP 2:B=VAL("&H"+MID$(B$,I,2)):NEXT
40 NEXT
50 PRINT TIMER-TM
60 END
100 DATA000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F202122232425262728292A2B2C2D2E2F303132333435363738393A3B3C3D3E3F404142434445464748494A4B4C4D4E4F505152535455565758595A5B5C5D5E5F606162636465666768696A6B6C6D6E6F7071727374757677
107 DATA78797A7B7C7D7E7F808182838485868788898A8B8C8D8E8F909192939495969798999A9B9C9D9E9FA0A1A2A3A4A5A6A7A8A9AAABACADAEAFB0B1B2B3B4B5B6B7B8B9BABBBCBDBEBFC0C1C2C3C4C5C6C7C8C9CACBCCCDCECFD0D1D2D3D4D5D6D7D8D9DADBDCDDDEDFE0E1E2E3E4E5E6E7E8E9EAEBECEDEEEF
108 DATAF0F1F2F3F4F5F6F7F8F9FAFBFCFDFEFF,*
  • DATASTR2.BAS – speed 167, size 532

As you can see, this is slightly faster than the previous combined hex string version because it does less READs. It is also slightly smaller because it has less line numbers. And, I think, it could even be packed a bit more, but because I am loading these test programs as ASCII files in to XRoar, the lines cannot exceed 249 characters (the same as typing them in) so this was as much as I could fit on them (even though using EDIT on these lines shows I could still type about 6 more characters, but it only seemed to show me 5 more after I re-listed it).

Fun with DATA, eh?

Until next time, I leave you with this:

A virtual cookie goes to the first person that finds them.

Interfacing assembly with BASIC via DEFUSR, part 5

See also: part 1, part 2, part 3, part 4, part 5 and part 6.

Now that I’ve gotten my digressions with BASIC variable access speeds and input speeds and INKEY/INSTR and GOTO/GOSUB speeds and HEX versus DECimal speeds out of the way, I can finally get back to digressing on using assembly language to speed up BASIC.

Where were we?

Oh, right…

In part 4 of this article I presented an example of using BASIC to scroll a PAC-MAN style maze that was too tall to fit on 16 the line screen.

I also presented some assembly code that would scroll the screen much faster than BASIC could ever hope to.

Today, let’s combine these two items and try to create a fast-scrolling maze playfield.

Let’s get started!

START SHOUTING AT ME! (revisited)

But before we get started, let’s revisit the uppercase routine I presented in Part 3.

Simon Jonassen is well-known in the CoCo Community for doing some amazing things on the original CoCo 1 and 2 hardware (and, lately, the CoCo 3 as well). He is quite the master of optimization, and has created some stunning sound players that allow the original CoCo to have cool background music while doing other things (if only the game programmers of 1980 knew about this!). He also has a cool web-based CoCo semigraphics editor. He provided a few enhancements:

* UCASE.ASM v1.01
* by Allen C. Huffman of Sub-Etha Software
* www.subethasoftware.com / alsplace@pobox.com
*
* 1.01 a bit smaller per Simon Jonassen
*
* DEFUSRx() uppercase output function
*
* INPUT:   VARPTR of a string
* RETURNS: # chars processed
*
* EXAMPLE:
*   CLEAR 200,&H3F00
*   DEFUSR0=&H3F00
*   A$="Print this in uppercase."
*   PRINT A$
*   A=USR0(VARPTR(A$))
*
ORGADDR     EQU     $3f00

GIVABF      EQU     $B4F4   * 46324
INTCNV      EQU     $B3ED   * 46061
CHROUT      EQU     $A002

            opt	    6809    * 6809 instructions only
            opt	    cd      * cycle counting

            org     ORGADDR

start       jsr     INTCNV  * get passed in value in D
            tfr     d,x     * move value (varptr) to X
            ldy     2,x     * load string addr to Y
;           ldb     ,x      * load string len to B
            beq     null    * exit if strlen is 0
            ldb     ,x      * load string len to B
            ldx     #0      * clear X (count of chars conv)

loop        lda     ,y+	    * get next char, inc Y
;           lda     ,y      * load char in A
            cmpa    #'a     * compare to lowercase A
            blt     nextch  * if less, no conv needed
            cmpa    #'z     * compare to lowercase Z
            bgt     nextch  * if greater, no conv needed
lcase       suba    #32     * subtract 32 to make uppercase
            leax    1,x     * inc count of chars converted
nextch      jsr     [CHROUT] * call ROM output character routine
;           leay    1,y     * increment Y pointer
cont        decb            * decrement counter
            bne	    loop    * not done yet
;           beq     exit    * if 0, go to exit
;           bra     loop    * go to loop

exit        tfr     x,d     * move chars conv count to D
;           bra     return
            jmp     GIVABF  * return to caller

null        ldd     #-1     * load -2 as error
return      jmp     GIVABF  * return to caller

* lwasm --decb -o ucase2.bin ucase2.asm -l
* lwasm --decb -f basic -o ucase2.bas ucase2.asm -l
* lwasm --decb -f ihex -o ucase2.hex ucase2.asm -l
* decb copy -2 -r ucase2.bin ../Xroar/dsk/DRIVE0.DSK,UCASE2.BIN

This code is 46 bytes long, compared to my original which was 49 bytes. The changes are:

  1. Move the initial LDB with string length to after the string length check, since it’s only needed if we get past that check and have a string.
  2. Change my LDA ,Y to LDA ,Y+ to increment Y there and not need the LEAY 1,Y later.
  3. Changed my “characters left” check from BEQ EXIT and BRA LOOP to BNE LOOP since it can just fall through and continue otherwise.
  4. Change a BRA RETURN to JMP GIVABF, since the branch would just end up at a JMP, and doing a JMP is faster than branching to a JMP.

Minor changes, but every little bit helps.

Simon also pointed out an embarrassing oversight in my very first example shown in part 1:

ORGADDR EQU $3f00

GIVABF EQU $B4F4   * 46324
INTCNV EQU $B3ED   * 46061

       org  ORGADDR
start  jsr  INTCNV * get passed in value in D
       tfr  d,x    * transfer D to X so we can manipulate it
       leax 1,x    * add 1 to X
       tfr  x,d    * transfer X back to D
return jmp  GIVABF * return to caller

He reminded me about the “addd” instruction which can add to D. For some reason, I was thinking I needed to use LEA to add to a 16-bit register, and since “LEAD 1,D” wasn’t a thing, I did the whole transfer to X, add one to X, transfer back to D thing.

He said I should just do this:

* ADDONE.ASM v1.01
* by Allen C. Huffman of Sub-Etha Software
* www.subethasoftware.com / alsplace@pobox.com
*
* 1.01 made less stupid per Simon Jonassen
*
* DEFUSRx() add one routine
*
* INPUT:   integer to add one to
* RETURNS: value +1
*
* EXAMPLE:
*   CLEAR 200,&H3F00
*   DEFUSR0=&H3F00
*   A=USR0(42)
*   PRINT A
*
ORGADDR EQU     $3f00

INTCNV  EQU     $B3ED   * 46061
GIVABF  EQU     $B4F4   * 46324

        org     ORGADDR

start   jsr     INTCNV  * get passed in value in D
;       tfr     d,x     * transfer D to X so we can manipulate it
;       leax    1,x     * add 1 to X
;       tfr     x,d     * transfer X back to D
        addd    #1      * add 1 to D
return  jmp     GIVABF  * return to caller

* lwasm --decb -o -9 addone2.bin addone2.asm
* lwasm --decb -f basic -o addone2.bas
* decb copy -2 -r addone2.bin ../Xroar/dsk/DRIVE0.DSK,ADDONE2.BIN

See what happens when people who actually know 6809 assembly language look at my code? Thanks, Simon!

Moving Day

My simple examples have been building up to slight less-simple ones that do something more useful, like moving data that would take days to move in BASIC. Previously, I presented a PAC-MAN maze that could “scroll” up and down the screen by PRINTing the whole screen each time with just the lines of the maze that should be visible. I also presented some assembly code that could be used to move the screen up, down, left or right.

Today, the first thing I want to do is integrate that assembly routine in to the PAC-MAN maze code. Instead of redrawing the entire screen each time, BASIC will only need to redraw the top or bottom line depending on which was the screen just scrolled. If my math is correct, printing one line instead of sixteen lines should be at least twice faster.

First, let’s revisit the screen moving assembly code, which, thanks to comments from L. Curtis Boyle, now has a smarter routine for checking which direction the user passed in to scroll (though it could still be thrown off by values larger than 255):

* SCRNMOVE.ASM v1.01
* by Allen C. Huffman of Sub-Etha Software
* www.subethasoftware.com / alsplace@pobox.com
*
* DEFUSRx() screen moving function
*
* INPUT:   direction (1=up, 2=down, 3=left, 4=right)
* RETURNS: 0 on success
*         -1 if invalid direction
*
* 1.01 better param parsing per L. Curtis Boyle
*
* EXAMPLE:
*   CLEAR 200,&H3F00
*   DEFUSR0=&H3F00
*   A=USR0(1)
*
ORGADDR EQU     $3f00

INTCNV  EQU     $B3ED   * 46061
GIVABF  EQU     $B4F4   * 46324

UP      EQU     1
DOWN    EQU     2
LEFT    EQU     3
RIGHT   EQU     4
SCREEN  EQU     1024    * top left of screen
END     EQU     1535    * bottom right of screen

        org     ORGADDR

start   jsr     INTCNV  * get incoming param in D
;       cmpb    #UP
        decb            * decrement B
        beq     up      * if one DEC got us to zero
;       cmpb    #DOWN
        decb            * decrement B
        beq     down    * if two DECs...
;       cmpb    #LEFT
        decb            * decrement B
        beq     left    * if three DECs...
;       cmpb    #RIGHT
        decb            * decrement B
        beq     right   * if four DECs...
error   ldd     #-1     * load D with -1 for error code
        bra     exit

up      ldx     #SCREEN+32
loopup  lda     ,x
        sta     -32,x
        leax    1,x
        cmpx    #END
        ble     loopup
        bra     return

down    ldx     #END-32
loopdown lda    ,x
        sta     32,x
        leax    -1,x
        cmpx    #SCREEN
        bge     loopdown
        bra     return

left    ldx     #SCREEN+1
loopleft lda    ,x
        sta     -1,x
        leax    1,x
        cmpx    #END
        ble     loopleft
        bra     return

right   ldx     #END-1
loopright lda   ,x
        sta     1,x
        leax    -1,x
        cmpx    #SCREEN
        bge     loopright
    
return  ldd     #0      * return code (0=success)
exit    jmp     GIVABF  * return to BASIC

* lwasm --decb -9 -o scrnmove2.bin scrnmove2.asm
* lwasm --decb -f basic -o scrnmove2.bas scrnmove2.asm
* decb copy -2 -r scrnmove2.bin ../Xroar/dsk/DRIVE0.DSK,SCRNMOVE2.BIN

The generated BASIC program looks like:

10 READ A,B
20 IF A=-1 THEN 70
30 FOR C = A TO B
40 READ D:POKE C,D
50 NEXT C
60 GOTO 10
70 END
80 DATA 16128,16217,189,179,237,90,39,14,90,39,28,90,39,42,90,39,55,204,255,255,32,67,142,4,32,166,132,167,136,224,48,1,140,5,255,47,244,32,47,142,5,223,166,132,167,136,32,48,31,140,4,0,44,244,32,30,142,4,1,166,132,167,31,48,1,140,5,255,47,245,32,14
90 DATA 142,5,254,166,132,167,1,48,31,140,4,0,44,245,204,0,0,126,180,244,-1,-1

Let’s take the original maze program and modify it to use the assembly routines instead:

0 REM MAZETEST.BAS
10 DIM MZ$(31)
20 FOR A=0 TO 30:READ MZ$(A):NEXT
30 CLS
40 REM SCROLL MAZE DOWN
50 FOR ST=0 TO 15
60 FOR LN=0 TO 15
70 PRINT @LN*32,MZ$(LN+ST);
80 NEXT:NEXT
90 REM SCROLL MAZE UP
100 FOR ST=15 TO 0 STEP-1
110 FOR LN=0 TO 15
120 PRINT @LN*32,MZ$(LN+ST);
130 NEXT:NEXT
140 GOTO 40
999 GOTO 999
1000 DATA "XXXXXXXXXXXXXXXXXXXXXXXXXXXX"    
1010 DATA "X            XX            X"    
1020 DATA "X XXXX XXXXX XX XXXXX XXXX X"    
1030 DATA "X XXXX XXXXX XX XXXXX XXXX X"    
1040 DATA "X XXXX XXXXX XX XXXXX XXXX X"    
1050 DATA "X                          X"
1060 DATA "X XXXX XX XXXXXXXX XX XXXX X"   
1070 DATA "X XXXX XX XXXXXXXX XX XXXX X"    
1080 DATA "X      XX    XX    XX      X"   
1090 DATA "XXXXXX XXXXX XX XXXXX XXXXXX"    
2100 DATA "     X XXXXX XX XXXXX X     "    
2110 DATA "     X XX          XX X     "    
2120 DATA "     X XX XXXXXXXX XX X     "   
2130 DATA "XXXXXX XX X      X XX XXXXXX"   
2140 DATA "          X      X          "   
2150 DATA "XXXXXX XX X      X XX XXXXXX"   
2160 DATA "     X XX XXXXXXXX XX X     "   
2170 DATA "     X XX          XX X     "   
2180 DATA "     X XX XXXXXXXX XX X     "   
2190 DATA "XXXXXX XX XXXXXXXX XX XXXXXX"   
3200 DATA "X            XX            X"   
3210 DATA "X XXXX XXXXX XX XXXXX XXXX X"   
3220 DATA "X XXXX XXXXX XX XXXXX XXXX X"   
3230 DATA "X   XX                XX   X"   
3240 DATA "XXX XX XX XXXXXXXX XX XX XXX"   
3250 DATA "XXX XX XX XXXXXXXX XX XX XXX"   
3260 DATA "X      XX    XX    XX      X"   
3270 DATA "X XXXXXXXXXX XX XXXXXXXXXX X"   
3280 DATA "X XXXXXXXXXX XX XXXXXXXXXX X"   
3290 DATA "X                          X"   
4200 DATA "XXXXXXXXXXXXXXXXXXXXXXXXXXXX"

The maze is 31 lines tall. The fake scrolling is done by redrawing the entire screen line-by-line. The screen is 16 lines tall, so initially we draw maze lines 0-15. Then we redraw maze lines 1-16, giving the appearance that the screen is scrolling up and a line has scrolled off the top of the screen. This repeats for lines 2-17, 3-18 and so on until we’ve drawn the last 16 lines of 15-30.

After “scrolling” all the way to the bottom of the maze, a second block of FOR/NEXT loops reverses the process, starting with maze lines 15-30, then 15-30 and so on until it is back to displaying the top lines 0-15.

The scrolling is done by the FOR/NEXT loops using the LN variables in lines 60-80 and 110-130.

Rather than redrawing all sixteen lines each time, we could use the assembly routine to move the screen, and then we’d just draw one line – top or bottom, depending on which was the screen scrolled.

In effect, we’d replace this:

40 REM SCROLL MAZE DOWN
50 FOR ST=0 TO 15
60 FOR LN=0 TO 15
70 PRINT @LN*32,MZ$(LN+ST);
80 NEXT:NEXT
90 REM SCROLL MAZE UP
100 FOR ST=15 TO 0 STEP-1
110 FOR LN=0 TO 15
120 PRINT @LN*32,MZ$(LN+ST);
130 NEXT:NEXT

…with this:

35 FOR LN=0 TO 15:PRINT @LN*32,MZ$(LN+ST);:NEXT
40 REM SCROLL MAZE DOWN
50 FOR ST=0 TO 15
60 Z=USR0(1)
70 PRINT @480,MZ$(ST+15);
80 NEXT
90 REM SCROLL MAZE UP
100 FOR ST=15 TO 0 STEP-1
110 Z=USR0(2)
120 PRINT @0,MZ$(ST);
130 NEXT

Line 35 was added to initially draw the screen. After that, the assembly routine can move it up or down, and let BASIC redraw just the one line that needs to be drawn.

This, of course, requires the assembly routine to be loaded. We can take the BASIC loader of that and renumber it so we can call it from our test program. Here is the scrnmove2.asm updated code from the top of this article, renumbered and changed in to a subroutine:

5000 REM ASSEMBLY ROUTINE
5010 READ A,B
5020 IF A=-1 THEN 5070
5030 FOR C = A TO B
5040 READ D:POKE C,D
5050 NEXT C
5060 GOTO 5010
5070 RETURN
5080 DATA 16128,16217,189,179,237,90,39,14,90,39,28,90,39,42,90,39,55,204,255,255,32,67,142,4,32,166,132,167,136,224,48,1,140,5,255,47,244,32,47,142,5,223,166,132,167,136,32,48,31,140,4,0,44,244,32,30,142,4,1,166,132,167,31,48,1,140,5,255,47,245,32,14
5090 DATA 142,5,254,166,132,167,1,48,31,140,4,0,44,245,204,0,0,126,180,244,-1,-1

Now, I can add this to the end of the mazetest.bas program and set it up so the USR0() calls will work:

10 CLEAR 200,&H3F00:DIM MZ$(31)
25 GOSUB5000:DEFUSR0=&H3F00

Now the program will use the CLEAR command to protect memory starting at &H3F00 (where the assembly will load), then after it reads all the maze strings in to memory (those DATA statements appear first), it will GOSUB 5000 and that READs the assembly code statements and POKEs them in to memory starting at &H3F00. The DEFUSR call is then done to make USR0(x) work.

With just a few lines changed, and getting our assembly routine in memory, now the maze scrolling is very fast! And, if we optimized the BASIC code around it, it could be even faster since most of the time is spent processing the BASIC program.

Here is the full listing:

0 REM MAZETST2.BAS - W/ASM!
10 CLEAR 200,&H3F00:DIM MZ$(31)
20 FOR A=0 TO 30:READ MZ$(A):NEXT
25 GOSUB5000:DEFUSR0=&H3F00
30 CLS

40 REM SCROLL MAZE DOWN
50 FOR ST=0 TO 15
60 FOR LN=0 TO 15
70 PRINT @LN*32,MZ$(LN+ST);
80 NEXT:NEXT
90 REM SCROLL MAZE UP
100 FOR ST=15 TO 0 STEP-1
110 FOR LN=0 TO 15
120 PRINT @LN*32,MZ$(LN+ST);
130 NEXT:NEXT

35 FOR LN=0 TO 15:PRINT @LN*32,MZ$(LN+ST);:NEXT
40 REM SCROLL MAZE DOWN
50 FOR ST=0 TO 15
60 Z=USR0(1)
70 PRINT @480,MZ$(ST+15);
80 NEXT
90 REM SCROLL MAZE UP
100 FOR ST=15 TO 0 STEP-1
110 Z=USR0(2)
120 PRINT @0,MZ$(ST);
130 NEXT
140 GOTO 40
999 GOTO 999
1000 DATA "XXXXXXXXXXXXXXXXXXXXXXXXXXXX"    
1010 DATA "X            XX            X"    
1020 DATA "X XXXX XXXXX XX XXXXX XXXX X"    
1030 DATA "X XXXX XXXXX XX XXXXX XXXX X"    
1040 DATA "X XXXX XXXXX XX XXXXX XXXX X"    
1050 DATA "X                          X"
1060 DATA "X XXXX XX XXXXXXXX XX XXXX X"   
1070 DATA "X XXXX XX XXXXXXXX XX XXXX X"    
1080 DATA "X      XX    XX    XX      X"   
1090 DATA "XXXXXX XXXXX XX XXXXX XXXXXX"    
2100 DATA "     X XXXXX XX XXXXX X     "    
2110 DATA "     X XX          XX X     "    
2120 DATA "     X XX XXXXXXXX XX X     "   
2130 DATA "XXXXXX XX X      X XX XXXXXX"   
2140 DATA "          X      X          "   
2150 DATA "XXXXXX XX X      X XX XXXXXX"   
2160 DATA "     X XX XXXXXXXX XX X     "   
2170 DATA "     X XX          XX X     "   
2180 DATA "     X XX XXXXXXXX XX X     "   
2190 DATA "XXXXXX XX XXXXXXXX XX XXXXXX"   
3200 DATA "X            XX            X"   
3210 DATA "X XXXX XXXXX XX XXXXX XXXX X"   
3220 DATA "X XXXX XXXXX XX XXXXX XXXX X"   
3230 DATA "X   XX                XX   X"   
3240 DATA "XXX XX XX XXXXXXXX XX XX XXX"   
3250 DATA "XXX XX XX XXXXXXXX XX XX XXX"   
3260 DATA "X      XX    XX    XX      X"   
3270 DATA "X XXXXXXXXXX XX XXXXXXXXXX X"   
3280 DATA "X XXXXXXXXXX XX XXXXXXXXXX X"   
3290 DATA "X                          X"   
4200 DATA "XXXXXXXXXXXXXXXXXXXXXXXXXXXX"

5000 REM ASSEMBLY ROUTINE
5010 READ A,B
5020 IF A=-1 THEN 5070
5030 FOR C = A TO B
5040 READ D:POKE C,D
5050 NEXT C
5060 GOTO 5010
5070 RETURN
5080 DATA 16128,16217,189,179,237,90,39,14,90,39,28,90,39,42,90,39,55,204,255,255,32,67,142,4,32,166,132,167,136,224,48,1,140,5,255,47,244,32,47,142,5,223,166,132,167,136,32,48,31,140,4,0,44,244,32,30,142,4,1,166,132,167,31,48,1,140,5,255,47,245,32,14
5090 DATA 142,5,254,166,132,167,1,48,31,140,4,0,44,245,204,0,0,126,180,244,-1,-1

Try the original BASIC-only version and then this new assembly-enhanced version and see what you think.

Next time, I will share a version of this scrolling maze that has a character you can control and move through the maze.

Until then…

Optimizing Color BASIC, part 5

See also: part 1, part 2, part 3, part 4, part 5, part 6, part 7, part 8 and part 9.

Updates:

  • 2/14/2017 – Fixed numeric typo (thanks, Geroge P!).

HEX versus DECimal Numbers

As Barbie once said*…

Math is hard! – Barbie

While Mattel’s Math-Is-Hard Barbie never quite made the splash the marketing team had hoped for, her sentiment lives on.

Side Note: *This is in reference to a the Teen Talk Barbie doll released in 1992, and out of the 270 phrases the doll could say, that was not one of them. The real quote was “Math class is tough!”

Earlier in this series, I touched on the fact that dealing with numbers is time consuming for BASIC. Something as simple as B=65535 takes time to process as the interpreter translates that base-10 decimal number in to an internal floating point value. The more digits, the more work. For instance:

0 REM NUMBERS.BAS
10 TIMER=0:TM=TIMER
20 FOR A=1 TO 1000
30 B=1
40 NEXT
50 PRINT TIMER-TM

That prints a value of 183. If you change line 3 to read “B=12345” the number jumps to 485. You can see the increase:

  • B=1 – 183
  • B=12 – 262
  • B=123 – 337
  • B=1234 – 408
  • B=12345 = 485

Obviously, the more numbers to parse and convert, the more time it will take. It also seems to matter if the value has a decimal point in it:

  • B=1.0 – 403
  • B=1.1 – 476

Even though that is only three characters to process, it takes longer than B=123. Clearly, more work is being done on floating point values. Even though all Color BASIC numbers are represented internally as floating point, it still makes sense to avoid using them unless you really need them.

You can also represent a base-16 number in hexadecimal. For the value of 1, it feels like parsing “&H1” should take longer than parsing “1”. Let’s try:

  • B=&H1 – 180
  • B=&H12 – 175
  • B=&H123 – 200
  • B=&H1234 – 203

It seems that parsing a hexadecimal value is much faster than dealing with base-10 values. Using this, you could speed up a program just by switching to hex, provided that your numbers are between 0 and 65535 (the values that can be represented in hex). I was surprised to see that negative values also work:

  • B=&HFFFF – 201
  • B=-&HFFFF – 230

It seems dealing with the negative takes a bit of more time, though, so it makes sense to avoid using them unless you really need them. ;-)

With this in mind, let’s test a FOR/NEXT loop:

10 TIMER=0:TM=TIMER
20 FOR A=&H1 TO &H3E8
30 B=&H1
40 NEXT
50 PRINT TIMER-TM

This prints 182, which is basically the same speed as the original that used 0 TO 1000. I guess hexadecimals don’t really help out FOR/NEXT.

Why? Because the FOR/NEXT statement is only parsed once, then the loop counters are set up and done. It is probably a tad faster to use hex, but that savings only happens once in the “do it 1000 times” test.

But, as you see, USING the variables gets faster. Any place we use a number, it seems using a hex version of that number may speed it up:

10 TIMER=0:TM=TIMER
20 FOR A=1 TO 1000
30 IF A>&HFF THEN REM
40 NEXT
50 PRINT TIMER-TM

This prints 278. Doing it with A>255 prints 427! Imagine if you could speed up every time you used a number in your code:

10 TIMER=0:TM=TIMER
20 FOR A=1 TO 1000
30 PRINT@&H20,"HELLO"
40 NEXT
50 PRINT TIMER-TM

That prints 391, but changing it to PRINT@32 prints 469! If you use a bunch of PRINT@s in your code, you can speed them up just by switching to hex!

Math could be accelerated, too, simply due to the number conversion being faster. The more digits, the better advantage hex has:

  • B=A+&H270F – 285
  • B=A+9999 – 483

And the more numbers, the more time you can save by using hex. A common PRINT thing is to use the length of a string to figure out how to center is on the screen:

0 REM NUMBERS.BAS
10 TIMER=0:TM=TIMER
15 CLS:A$="HELLO, WORLD!":LN=LEN(A$)
20 FOR A=1 TO 1000
25 PRINT@32*8+16-LN/2,A$
40 NEXT
50 PRINT TIMER-TM

That prints 1284. Converting line 24 to HEX:

25 PRINT@&H20*&H8+&H1-LN/&H2,A$

And now it prints 1097.

In a game where you might be PRINTing things on the screen constantly, those savings could really add up.

Pity that math is hard, else we could just use hex in our programs and get a free speed boost.

Until next time…

An effect of PAL versus NTSC…

Just a quick note about my Optimizing Color BASIC series…

In later installments, I started doing some benchmarking using BASIC’s TIMER command. TIMER returns an incrementing count value that is based on the 60hz TV sync. At 60hz, the timer counts to 60 approximately every second.

I have been doing my tests in the XRoar emulator, which was created to emulate the Dragon, a CoCo clone manufactured in England. Over there, their TV systems are 50hz, so the Dragon and UK versions of the CoCo operate using a different TV sync rate.

Thus, in Dragon/UK mode, TIMER counts up to 50 every second.

And by default, XRoar starts up in PAL mode.

So it’s likely that some of the TIMER values I have given have been off, because I may have been running in PAL/50hz mode sometime.

So if you catch any, let me know and I will go back and retest and correct. I already did that in a recent part, but I may have missed others.

Mea culpa.