Category Archives: Color BASIC

Bit shifting in BASIC

Recently, I had the urge to be lazy and have the computer do my work for me. I was designing some 8×8 graphics characters for the Commodore VIC-20 and wanted one for each offset position in a 2-character block (see image to the right).

Using modern tools like the Windows-based CBM prg Studio I could have easily edited each one by hand to get the desired result (which is what I did to create that image), but I thought it might be more fun to just design one character and write a program to create the other shifted frames.

I have bit shifted in C programming many times (because it has a bit shift operator) but I don’t recall ever knowingly doing it in BASIC.

Bit shifting basics

Bit shifting is where you take all the bits in a byte (or word, or long, whatever) and move them left or right. Here is an example of shifting the byte value 00111100 to the right:

Before: [ 0 0 1 1 1 1 0 0 ]
After : [ 0 0 0 1 1 1 1 0 ]

If you just want to shift and don’t care about the bit that “falls off the edge,” it is as simple as multiplying or dividing the value by 2.

To demonstrate this, we first need a program that will display a byte as bits.

0 REM bitsslow.bas
10 Z=&H00:GOSUB 500
20 Z=&HF0:GOSUB 500
30 Z=&H0F:GOSUB 500
40 Z=&HFF:GOSUB 500
50 END

500 REM PRINT BITS
510 FOR ZB=7 TO 0 STEP -1
520 IF Z AND 2^ZB THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 PRINT:RETURN

The routine at line 500 will print the value in variable Z as bits. It is hard coded to only work with a byte (0-255). When I run that, this is what it displays:

Those lines correspond to &H00, &HF0, &H0F and &FF. I show them in hex so the bit pattern is easier to see (0=0000, F=1111).

A bit faster…

My bit printing routine is so slow that you can see it print the digits one at a time. This is due to the math that goes on in line 520 for each bit check. To speed things up, we could pre-calculate an array of those powers of two (1, 2, 4, 8, 16, 32, 64, 128) and use that instead:

0 REM bitsfast.bas

5 GOSUB 1000

10 Z=&H00:GOSUB 500
20 Z=&HF0:GOSUB 500
30 Z=&H0F:GOSUB 500
40 Z=&HFF:GOSUB 500
50 END

500 REM PRINT BITS
510 FOR ZB=7 TO 0 STEP -1
520 IF Z AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 PRINT:RETURN

1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

Line 5 will GOSUB to our initialization routine which sets up the power-of-two array ZB(). After that, the routine at 500 can be called as it previously was, except now it will print so fast you can’t really see it printing.

Now let’s use this routine to demonstrate bit shifting by multiplying or dividing by 2.

Bit shifting left

0 REM bitshftl.bas
5 GOSUB 1000
10 Z=1 '00000001
20 FOR A=1 TO 8
30 GOSUB 500
35 REM *2 TO SHIFT LEFT
40 Z=Z*2:NEXT
50 END
500 REM PRINT BITS
510 FOR ZB=7 TO 0 STEP -1
520 IF Z AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 PRINT:RETURN
1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

In line 10, Z starts out with 1, which is the bit pattern of 00000001. It is then multiplied by 2 in a loop eight times, each time shifting the bit one place to the left. The output looks like this:

Bit shifting right

And if we start out with Z being 128 (bit pattern 10000000) and divide by 2, it will shift right:

0 REM bitshftr.bas
5 GOSUB 1000
10 Z=128 '10000000
20 FOR A=1 TO 8
30 GOSUB 500
35 REM /2 TO SHIFT RIGHT
40 Z=Z/2:NEXT
50 END
500 REM PRINT BITS
510 FOR ZB=7 TO 0 STEP -1
520 IF Z AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 PRINT:RETURN
1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

This will display:

Pretty simple. And if that were all I wanted to do, I’d be done.

But that was not all I wanted to do, so I am not done.

I wanted to shift bits right in one byte and have the bits that shift out end up shifting in to a second byte, like this:

    1st Byte  2nd Byte
1) [00001111][00000000]
2) [00000111][10000000]
3) [00000011][11000000]
4) [00000011][11100000]
5) [00000001][11110000]
6) [00000000][11111000]
...etc...

I spent far too much time coming up with an approach that would get me which bits were going to be shifted off to the right (using AND), and then placing those in a new variable and then shifting those bits to the left to line up where they would have ended up if I had just shifted a 16-bit value…

…then I realized that was silly, because I could just use a 16-bit value in BASIC!

16-bits in BASIC

You may have seen things like this which print out memory locations BASIC is using:

PRINT PEEK(25)*256+PEEK(26)

In Color BASIC, memory locations 25 and 26 contain the 16-bit address for where BASIC memory starts. Since PEEK only works on a single byte, it takes two PEEKs to get the two bytes that make up the 16-byte address, and some math to turn the two 8-bit values into one 16-bit value.

On my virtual CoCo in the Xroar emulator, memory location 25 contains 38 (&H26) and memory location 26 contains 1 (&h01). To turn those two 8-bit values into a 16-bit address, I need to somehow shift the 38/&H28 left eight times into a new 16-bit value, and then add (or OR) in the 1/&H01 value.

In C, one of the ways we’d do this is by using the bit shift operator:

uint16_t Result;
uint8_2  Byte1;
uint8_2  Byte2;
Byte1 = Peek(25); // Made up function to get a memory value.
Byte2 = Peek(26);
Result = (Byte1 << 8) | Byte2; // Shift Byte1 left 8 bits,
                               // OR in Byte2.
// Or...
Result = (Byte1 << 8) + Byte2; // Since the right 8 bits are empty,
                               // adding would have the same result.

…but there are many other ways to do the same thing, some much faster than these two approaches.

Back to BASIC

Shifting left can be done by multiplying the value by 2. To shift once, you might have:

V = V * 2

To shift twice, you could do:

V = V * 2 * 2

…but that looks silly. You’d just multiply by 4. And to bit shift three places (2 * 2 * 2) you could multiply by 8. See the pattern? They are all powers of 2 (2, 4, 8, 16, 32, 64, 128, 256, etc.)

So to shift 8 places left, you multiply by 256. Thus, the C example I gave earlier is represented in BASIC by:

10 B1=PEEK(25)
20 B2=PEEK(26)
30 R=(B1*256)+B2

Tada! When I first saw things like “X=PEEK(Y)*PEEK(Z)” back then, I did not understand why it worked, I just knew it did. And I was also confused at why the CoCo was like that, since on the VIC-20 it would have been “X=PEEK(Y)+256*PEEK(Z)”. See the differences? On the CoCo’s 6809 processor, a 16-bit value is YYZZ, but on the VIC-20’s 6502 processor it is stored the opposite as ZZYY. Thus, on my VIC, you would take the second location and multiply it by 256 then add the first location.

But I digress.

A bit more…

The previous example shows how you are effectively shifting a byte (B1) left 8 places so it ends up at the top 8-bits of a new 16-bit value. Something like that would work very well for shifting an 8-bit value into different positions of two characters (two bytes).

My approach would be this:

R will be the result, a value representing 16-bits (two bytes, 0-65535 in range).
Since I am shifting right (in this example), my first step is to get the 8-bit source value into the top 8-bits (left most bits) of the R result variable.
Next I will shift that entire R variable to the right, and then extract the left and right 8-bits as separate variables which is my output values.

Extract? Well, that will be the reverse of what we just did. In C, you can turn a 16-bit value into two 8-bit values like this:

uint16_t Source;
uint8_2  Byte1;
uint8_2  Byte2;
Source = 0x1234;           // Some 16-bit value.
Byte1 = (Source >> 8);     // Shift left 8-bits to the right.
Byte2 = (Source & 0x00ff); // Mask off top 8-bits.

…though there are many other (faster/better ways to do this). But, we could do this in BASIC the same way.

If shifting left is multiplying by 256, then shifting right must be dividing by 256.

10 R=&H1234
20 B1=(R/256)
30 B2=(R AND &HFF)

IMPORTANT NOTE: As I got to a later point in this article, I discovered a huge problem with this approach. If you didn’t already know it (I didn’t), I’ll explain it in just a bit… When I write, I’m usually learning as I type, and I decided to keep this stream of consciousness intact.

That is the first time I’ve ever done it that way in BASIC (duplicating the way C does it). The way I’ve commonly seen it done in BASIC is this:

10 R=&H1234
20 B1=INT(R/256)
30 B2=R-(B1*256)

Here is a simple test program:

0 REM split1.bas
10 S1=&H12
20 S2=&H34
30 R=S1*256+S2
40 PRINT HEX$(S1)" "HEX$(S2)" -> "HEX$(R)
50 D1=INT(R/256)
60 D2=R-(D1*256)
70 PRINT HEX$(R)" -> "HEX$(D1)" "HEX$(D2)

Using BASIC to split 16-bit values, or combine two 8-bit values.

Benchmark digression

Have I been doing it wrong since the 1980s? Is the C-style way (using AND) any faster than the BASIC way (using INT)? Let’s try the C-style way using my trusty benchmark program:

0 REM split2.bas
5 DIM TE,TM,B,A,TT
6 R=&H1234
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=42 THEN 100
40 B1=R/256
50 B2=R AND &HFF
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

This shows 1143. (Of course it could be made faster using hex and removing spaces and such, but this is just for comparison with the second version.)

And now let’s try it the traditional BASIC:

0 REM split3.bas
5 DIM TE,TM,B,A,TT
6 R=&H1234
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=42 THEN 100
40 B1=INT(R/256)
50 B2=R-B1*256
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

This version reports 1498! Well I’ll be darned… INT and a divide and a subtract and a multiply is slow than a divide and an AND. Well, once I write it out like that, I guess it makes sense.

I suppose applying some things I learned in C to BASIC is paying off.

But I digress…

Are we there yet?

So getting back to the original task, I should be able to combine 8-bit values and split 16-bit values and shift them any way I want.

First let me modify the bit printing routine to handle 16-bit values.

IMPORTANT NOTE: Here’s the bit I was talking about earlier…

I thought I could just change the 0 to 7 into 0 to 15 to cover all 16 bits, but that resulted in an ?FC ERROR (function call). A bit of testing revealed that AND only works on values from 0 to 32767 (&H7FFF). That is the maximum value of a 16-bit SIGNED integer, which uses 15-bits for the number and 1-bit for the sign (+ or -).

Yipes! So I could only easily show 15-bits, and I really want that extra bit.

Note to Self: Look into the Color BASIC Unravelled book and see why this is.

So, it looks like I’ll just have to modify my 8-bit print routine to print each byte of a 16-bit value separately. Good thing we learned how to do that earlier in this article!

16-bit bit printing

Here is how I had to modify the routine:

0 REM bits16.bas

5 GOSUB 1000

10 Z=&H0000:GOSUB 500
20 Z=&HFF00:GOSUB 500
30 Z=&H00FF:GOSUB 500
40 Z=&HFFFF:GOSUB 500
50 END

500 REM PRINT BITS
501 ZZ=INT(Z/256):GOSUB 510
502 ZZ=Z-ZZ*256:GOSUB 510
503 PRINT:RETURN
510 FOR ZB=7 TO 0 STEP -1
520 IF ZZ AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 RETURN

1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

Whew! That works, and prints the following:

0000000000000000
1111111100000000
0000000011111111
1111111111111111

Okay, so I did not discover any amazing speedup (at least if we want to use values larger than 32767), but I did get it to work.

I saved the best bit for last…

Now we can try a little test to see if we can start with an 8-bit value, shift it to the left side of a 16-bit value, the start shifting one bit at a time right, then splitting up the resulting two bytes at each step. I will use a test byte of &HFF (11111111).

0 REM shift16.bas

5 GOSUB 1000

10 Z=&HFF  '11111111
15 Z=Z*256 '1111111100000000
20 FOR A=1 TO 8
25 REM SPLIT INTO TWO BYTES
26 B1=INT(Z/256)
27 B2=Z-(B1*256)
28 PRINT HEX$(B1)TAB(3)HEX$(B2)TAB(5)" = ";
30 GOSUB 500
35 REM /2 TO SHIFT RIGHT
40 Z=Z/2:NEXT
50 END

500 REM PRINT BITS
501 ZZ=INT(Z/256):GOSUB 510
502 ZZ=Z-ZZ*256:GOSUB 510
503 PRINT:RETURN
510 FOR ZB=7 TO 0 STEP -1
520 IF ZZ AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 RETURN

1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

And it displays:

Color BASIC shifting a 16-bit value and splitting it up into two 8-bit values.

Success!

I could now incorporate that routine into my code, and take the data for one 8×8 character (like the solid circle I started this article with) and end up with 16 8×8 characters representing each position it could be within a 2×1 block of characters.

2010 DATA 60,126,255,255,255,255,126,60

In conclusion…

Wow. That was a really long way to go to show multiplying by 256 and dividing by 2, wasn’t it? But maybe there are some useful routines in these examples.

And now it’s my turn to ask you:

Do you know a better/faster way to print 16-bit values in binary?
Do you know a faster way to combine two 8-bit values into a 16-bit value, or split a 16-bit value into two 8-bit values?
Is there a better/faster way to to bit shifting than multiplying or dividing by powers of 2?

Let me know in the comments, and maybe there will be a part 2 on this topic.

Until next time…

Random Easter Egg

Leave a reply

There is an interesting hidden message embedded in the Color BASIC ROM, and here is the code that reveals it:

0 REM COLOR BASIC EASTER EGG
10 A=26493:B=66:C=13:GOSUB40
20 A=291227:B=B+2:C=C+3:GOSUB40
30 END
40 I=RND(-A):FOR I=1 TO 4:PRINT CHR$(B+RND(C));:NEXT:RETURN

If you run this code, it will display this:

“COCOFEST” easter egg in the Color BASIC ROM!

Amazing, eh? How did they possibly know back in 1980 that COCOFEST would become a thing?

But actually, it’s just a random message, and not a hidden message at all. I learned of this trick from this video by 8-Bit Show and Tell that claims to share a hidden anti-Microsoft Easter egg in Commodore 64 BASIC… and then reveals how the prank works.

A hidden anti-Microsoft Easter egg in Commodore 64 BASIC! Or not…

If you tried to run that program on other flavors of BASIC, it probably would not work. It certainly does not produce the expected results on a CoCo.

10 A=125708:GOSUB 20:A=33435700:GOSUB 20:A=17059266:GOSUB 20
20 A=RND(-A)
30 A=INT(RND(A)*22):IF A THEN PRINT CHR$(A+64);:GOTO 30
40 PRINT:RETURN

This was the first video from 8-Bit Show and Tell I ever saw, and it’s lead me down quick a rabbit hole trying things he demonstrates on the Commodore computers on our beloved CoCo. And it all started with this random video that YouTube randomly showed me.

Monkeys and Shakespeare

The infinite monkey theerem states that…

“…a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, such as the complete works of William Shakespeare.”
Wikipedia

We are just using BASIC’s RND() random number generator to simulate a monkey at a typewriter, and using short words instead of the complete works of Shakespeare.

It’s much quicker this way.

As previously discussed, the RND function generates a series of numbers that are not random. Each time you power up a CoCo, for instance, this code will produce the same “random” numbers the first time you run it:

FOR A=1 TO 8:PRINT RND(50);:NEXT

You get these same random numbers every time you power up the CoCo.

Try it for yourself using the web-based JS Mocha CoCo emulator.

In order to change the series of numbers, you pass a negative value into the RND() function, and that series will be used. If you do X=RND(-1), you will then get the same series of random values every time. If you do X=RND(-42), you get a different set of random numbers every time.

Magic!

Or math. But math is hard, and magic is just frustrating.

The monkey simulator

But how do you find which random seed value will give you the random numbers you want in the order you want them? The original prankster used brute-force trial and error.

A program can be designed that first seeds the RND function with -1, then generates a series of random numbers and tests to see if they are what it is looking for. In the case of the C64 version, it needed to see the numbers that represented the characters of the word followed by a ZERO to terminate the string.

If it did not work, it tries a seed of -2, and so on. This could take hours or days, and there is no guarantee the exact series of numbers will be found.

I decided to write a CoCo version of this monkey typewriter simulator, but I made some changes.

First, I figured looking for “W”+”O”+”R”+”D” was more work than just looking for “W”+”O”+”R”+”D” without a 0 byte at the end. That should speed up the search, but require an extra bit of data in the display program since it now needs to know how many random values to use (the length of the word).
The C64 version looked from A to the highest letter used (“BILL GATES SUCKS” scans A to U, though it doesn’t really need to try to find A since the earliest letter is B.) I figured that looking for A to Z (worst case, 26 choices) would be more work than just looking at the range of letters actually used in the word. For instance, finding “ABC” in a repeating random series of 26 numbers seems less likely than finding “ABC” if you were only using 3 random numbers. I made my generator look for a range covering only the letters being used. “CAT” would need numbers from “C” to “T”. “DOG” would need “D” to “O”. “ALACAZAM” would need “A” to “Z”. This meant my display program also needed to know the starting letter value and range value, in addition to the word length.

My version is not as clean and tidy as the C64 original

Here is the program I came up with. You can type in a word and it will present the range of letters it will look for, and then start searching until it finds it (or, weeks later, it has not and you give up):

10 REM rndwords.bas
20 POKE 65495,0
30 INPUT "TARGET STRING";T$
40 TL=LEN(T$)
50 IF TL=0 THEN 30
60 REM FIND LOWEST AND HIGHEST LETTER
70 LL=255:HL=0
80 FOR P=1 TO LEN(T$)
90 V=ASC(MID$(T$,P,1))
100 IF VHL THEN HL=V
120 ?V,LL;HL
130 NEXT
140 REM CALCULATE LETTER RANGE
150 R=HL-LL+1
160 PRINT "SEARCHING FOR: ";T$
170 PRINT "LETTER RANGE :";R;"(";CHR$(LL);" - ";CHR$(HL);")"
180 REM SEARCH...
190 FL=LL-1
200 FOR SD=1 TO 9999999
210 V=RND(-SD):A$=""
220 A$=A$+CHR$(FL+RND(R))
230 IF LEN(A$)

Some words are found almost instantly. “HI” shows up immediately:

Finding random words in the Color BASIC RND function.

The output shows the random seed to start with (-5), the word it was looking for (“HI”), the ASCII character to add to the random numbers it finds, and the range to use in the RND functions.

To display the string back, you would modify my original COCOFEST program with the proper values, or do it manually:

V=RND(-5):FOR I=1 TO 2:PRINT CHR$(71+RND(2));:NEXT:PRINT

Here are some words I have found:

REM "COCO"
V=RND(-26493):FOR I=1 TO 4:PRINT CHR$(66+RND(13));:NEXT

REM "FEST"
1001 V=RND(-291227):FOR I=1 TO 4:PRINT CHR$(68+RND(16));:NEXT

REM "SUB"
1002 V=RND(-56403):FOR I=1 TO 3:PRINT CHR$(65+RND(20));:NEXT

REM "ETHA"
1003 V=RND(-1049135):FOR I=1 TO 4:PRINT CHR$(64+RND(20));:NEXT

I tried to find “COCOFEST” together, but after days and days of running, it still hadn’t. Perhaps it would have found it if I was searching the entire A-Z range versus just C-T. It’s random-ish, after all.

Perhaps one of you will take this concept and recreate the C64 version, looking for A-Z and a zero. Maybe that works better. I did not try.

Perhaps one of you will start compiling a dictionary of random words and we can use this as a secret decoder ring for passing cryptic messages to each other on Facebook.

Perhaps this will just be a passing random thought and we will never speak of it again.

But knowing me and this site, I expect we will speak of it again. Especially if I get any good comments to this post.

Until next time…

BASIC and ELSE and GOTO and Work – part 2

Leave a reply

See also: part 1

There is a time and ELSE for everything

After I dove into ELSE efficiency, and then dove into it a bit deeper, I realized one of the major things that slows down BASIC is having to scan to the end of the line in order to find the next line.

In part 7 of my Optimizing Color BASIC series, I noticed that a GOTO or GOSUB was much slower if there were things on the line after it:

10 GOTO 100:REM THIS GOES TO THE INPUT ROUTINE

When BASIC is searching for a line number, each line entry has a size which lets it skip ahead to the next line if the line number did not match. But, once BASIC is processing a line, it does not track that. If the parser gets one token in to a line and it has to GOTO somewhere else, it has to scan forward until it finds the end of the line, then it can start scanning line numbers and skipping lines again.

Thus, one should not put comments on the ends of lines. They have to be parsed through. It is much faster to put comments on their own lines, though that takes up a more memory since each new line number takes 5 bytes.

This is one of the reasons this…

30 IF Z=1 THEN 100 ELSE IF Z=2 THEN 200 ELSE IF Z=3 THEN 300 ELSE IF Z=4 THEN 400

…can be slower than…

30 IF Z=1 THEN 100
31 IF Z=2 THEN 200
32 IF Z=3 THEN 300
33 IF Z=4 THEN 400

In the first example, if Z=1, BASIC still has to scan through all the remaining bytes of the line until it finds the end. In the second example, BASIC gets the line number then is already at the end and can immediately start scanning.

Thus, to add to my previous ELSE discussion, we should stop doing this:

30 IF X=1 THEN X=X+1:GOTO 70

If X is NOT 1, BASIC still has to scan through the rest of the line before it can check whatever happens next. Instead, it ican be much faster to do this:

30 IF X=1 THEN 100
...
100 X=X+1:GOTO xxx

There is a caveat to this. Things in BASIC are quite predictable. This change makes it faster to get to line 100 to do the actual work (X=X+1). BUT, from line 100 it could be much slower to get back to the top if there were a bunch of lines before the target line. If it’s a GOTO near the top of the program, it’s fast. If it’s a loop around 500, and you try to GOTO 500, that could be much slower if it had to scan through all the lines from 10 to 499 to get there.

This is when organizing code locations comes in very important, but that is a discussion for another time.

But other than situations like that, this is faster way:

10 REM MAIN LOOP

20 REM GET Z OR WHATEVER
30 IF Z=1 THEN 100
31 IF Z=2 THEN 200
32 IF Z=3 THEN 300
33 IF Z=4 THEN 400

40 REM NO KEY, DO IDLE LOOP STUFF
50 GOTO 10
100 X=X+1:GOTO 10
200 X=X-1:GOTO 10
300 Y=Y+1:GOTO 10
400 Y=Y-1:GOTO 10

If Z=4, the code will get there much faster since there is less for it to scan through after each Z check.

The location of where the work is done (later in the program or back at the top) is the only thing that can make this slower (or faster). Once a program gets large enough, moving things around may help speed up certain things but will slow down other things. I guess, much like real estate, location matters.

I guess we can stop using ELSE, and stop doing work on IF lines. And that goes for things like this:

IF SC=1000 THEN LV=LV+1

At 1000 points, we get a new life! However, every time through that loop when SC is not 1000, BASIC has to skip over “THEN LV=LV+1”, wasting cycles. The savings would be huge over the life of that loop to just do:

IF SC=1000 THEN 1000

…and let 1000 handle LV=LV+1 and returning back with a GOTO. GOSUB might be better, but that might be slower for something like this since:

IF SC=1000 THEN GOSUB 1000

…has an extra token (and potentially spaces, if you use them for readability) versus:

IF SC=1000 THEN 1000

WHEN this code runs (SC=1000), it may be faster to GOSUB and RETURN than it would be to GOTO/GOTO. BUT, most of the time the main loop is running that code will not be called and parsing past the GOSUB will just be wasting time.

Until next time…

BASIC and ELSE and GOTO and Work – part 1

3 Replies

My recent return to exploring my old Commodore VIC-20 code has reminded me about the main reason I jumped ship to a Radio Shack TRS-80 Color Computer: Extended Color BASIC. The older CBM BASIC V2 used by the VIC was missing keywords like ELSE, and had no functions for graphics or sounds. While I am having a blast re-learning how to program VIC-20 games, I sure do miss things like ELSE.

But should I?

IF/THEN/ELSE versus IF/THEN versus ON/GOTO

Pop quiz time! Suppose you were trying to determine if you needed to move a game character up, down, left or right. Which is the faster way to handle four choices?

30 IF Z=1 THEN 100 ELSE IF Z=2 THEN 200 ELSE IF Z=3 THEN 400 ELSE IF Z=4 THEN 500

…or…

30 IF Z=1 THEN 100
31 IF Z=2 THEN 200
32 IF Z=3 THEN 400
33 IF Z=4 THEN 500

Of course, if the values were only 1, 2, 3 and 4, you wouldn’t do either. Instead, you might just do:

ON Z GOTO 100,200,300,400

…but for the sake of this question, assume the values are not in any kind of order that allows you to do that.

IF/THEN/Work/ELSE versus IF/THEN/WORK

Suppose you were a junior high kid learning to program and you wanted to update some player X/Y positions based on keyboard input. Which one of these would be faster?

30 IF Z=1 THEN X=X+1 ELSE IF Z=2 THEN X=X-1 IF Z=3 THEN Y=Y+1 IF Z=4 THEN Y=Y-1

…versus…

30 IF Z=1 THEN X=X+1
31 IF Z=2 THEN X=X-1
32 IF Z=3 THEN Y=Y+1
33 IF Z=4 THEN Y=Y-1

All is not fair

I should point out that the speed it takes to run these snippets depends on the value of Z. For the sake of this article, let’s assume no key is pressed, so Z is set to something that is not 1, 2, 3 or 4.

Obviously, when there are four IFs in a row (either in a single line with ELSE, or on separate lines), the order of the checks determines how fast you get to each one. If Z is 1, and that is the first IF check, that happens faster than if Z is 4 and the code has to check against 1, 2 and 3 before finally checking against 4.

The same thing applies in languages that use switch/case type logic, so the things that need to be the fastest or happen most often should be at the top of the list and checked before things that happen less often.

Because of this, to be fair, we should also check best case (Z=1) and worst case (Z=4) and see what that does.

Benchmarking going to a line

In my benchmark program, this one counted to 954:

0 REM elsetst1.bas '954
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN 100 ELSE IF Z=2 THEN 200 ELSE IF Z=3 THEN 400 ELSE IF Z=4 THEN 500
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

And this one was a tiny bit faster. It counted to 942:

0 REM elsetst1.bas '942
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN 100
31 IF Z=2 THEN 200
32 IF Z=3 THEN 300
33 IF Z=4 THEN 400
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

Thus, using ELSE was a bit worse if none of the conditions were true.

IF we could have used ON/GOTO, that would be blazing at 253!

0 REM elsetst3.bas '253
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 ON Z GOTO 100,200,300,400
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

But I said we couldn’t, because I changed the rules to “do work” rather than “go to a line.”

Benchmarking doing work

Doing work with ELSE clocked in at 601:

0 REM elsetst4.bas '601
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN X=X+1 ELSE IF Z=2 THEN X=X-1 IF Z=3 THEN Y=Y+1 IF Z=4 THEN Y=Y-1
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

Since ELSE was slower to go to a line, I thought maybe it would be here, too, but instead, splitting the statements was slower. This one reports 963:

0 REM elsetst5.bas '963
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN X=X+1
31 IF Z=2 THEN X=X-1
32 IF Z=3 THEN Y=Y+1
33 IF Z=4 THEN Y=Y-1
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

It seems like ELSE has its place, but not for just going to a line.

Best versus Worst: FIGHT!

Let’s try some best and worst cases now. For this test, I’ll resolve the jumps to lines 100, 200, 300 and 400 by adding this:

100 GOTO 70
200 GOTO 70
300 GOTO 70
400 GOTO 70

That will greatly slow things down since we have to search forward to the new line, then it has to start back at the top of the program and search forward to find line 70. BUT, it will be consistent from test to test. I’ll add a “6 Z=1” or “6 Z=4” line.

elsetst1.bas (else): Z=1 produces 507. Z=4 produces 1058.
elsetst2.bas (separate): Z=1 produces 390. Z=4 produces 1053.
elsetst3.bas (on/goto): Z=1 produces 317. Z=4 produces 357.

Wow. ON/GOTO is really good at going places, best or worst case.

And what about the “doing work” stuff?

elsetst4.bas (else): Z=1 produces 632. Z=4 produces 633.
elsetst5.bas (separate): Z=1 produces 1171. Z=4 produces 1172.

In conclusion…

If you are using IF to go to some code, ON/GOTO is the fastest, following by separate lines. Even in the worst case, separate lines are still a tiny bit faster, which surprised me. I suspect it’s the time it takes to parse the ELSE versus a new line number. Retesting with all the spaces removed might change the results and make them closer.

But it does look like we need to stop doing “IF X=Y THEN ZZZ ELSE IF X=Y THEN ZZZ ELSE” unless we really need the extra bytes ELSE saves over a new line number.

And if you are trying to do work, ELSE seems substantially faster than separate line numbers. But, in both cases, best and worst case are very close. I believe this is a benchmark issue, since the time to scan a few lines is tiny compared to the time it takes to do something like “X=X+1”, and both best and worst case do the same amount of work. A better test would need to be performed.

Bonus

There is a way to speed up the separate line statements when doing work, especially for better case. Consider this:

0 REM elsetst6.bas '1034
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN X=X+1:GOTO 70
31 IF Z=2 THEN X=X-1:GOTO 70
32 IF Z=3 THEN Y=Y+1:GOTO 70
33 IF Z=4 THEN Y=Y-1
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

By adding the GOTO, if line 30 is satisfied (Z=1), the parser can start searching for line 70 without having to do the check against Z three more times. But, when a case is not satisfied, it now has to parse through the GOTO token and a line number to find the end of the line, meaning that for worst case (Z=4) it should be a bit slower.

Let’s see if this works.

elsetst6.bas (separate/goto): Z=1 produces 544. Z=4 produces 1241.

Compare that to the previous version without the end line GOTOs:

elsetst5.bas (separate): Z=1 produces 1171. Z=4 produces 1172.

It looks like there’s a significant improvement for best case, and a slight decrease in performance for worst case (the overhead of skipping more characters to find the end of the line for the false conditions).

The more you know…

I guess I am learning quite a bit by revisiting the VIC-20 and having to do things without ELSE.

What do you think? Did I miss anything?

Until next time…

More Crazy ON/GOTO/GOSUB and IF/THENs

3 Replies

More comments from the first ELSE article… First, MiaM chimes in:

MiaM:

You could also split that to two separate statements. One handling K=17 case, and then do ON K-38 GOTO 50,x,30 where x is just the line following the ON GOTO line.
don’t know about speed but you could also try ON K-16 GOTO 40,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,50,x,x,30 (also where x is the following line)
MiaM

In my example, I was getting keypress values back that represented left (17), right (39) and jump (41). By filling the ON/GOTO/GOSUB with bogus line values where the gaps are, you can now use ON/GOTO for non-sequential values. But, if the first number expected was a 17, that would be 17 dummy values at the start. Mia’s approach is to subtract that starting value, eliminating the need for 16 dummy values. Clever!

Clever, sure. But can it be benchmarked?

So how bad is this with speed? Let’s find out.

First, for the dummy lines we will just put nothing between the commas. That will be parsed as a zero, which is bad if any of those values are hit since going to 0 would restart the program, but since we are just testing and can control the value, it will give us the fastest way to parse a long ON/GOTO/GOSUB. Using real lines numbers will only be slower.

0 REM ONMIAM.BAS
5 DIM TE,TM,B,A,TT
6 K=17 'BEST CASE
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 ON K-16 GOTO 100,,,,,,,,,,,,,,,,,,,,,,200,,300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 REM LEFT
110 GOTO70
200 REM RIGHT
210 GOTO70
300 REM JUMP
310 GOTO70

Best case for the first target gives me 590. Not bad!

Trying again with “K=41” for worst case gives us 664. Still not terrible.

How does this rank against manual IF/THENs like this?

0 REM ONMIAM2.BAS
5 DIM TE,TM,B,A,TT
6 K=17 'BEST CASE
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF K=17 THEN 100:GOTO 70
40 IF K=39 THEN 200:GOTO 70
50 IF K=41 THEN 300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 REM LEFT
110 GOTO70
200 REM RIGHT
210 GOTO70
300 REM JUMP
310 GOTO70

Best case (17) reports 504 and worst case (41) reports 1128. Can there really be that much more overhead to skip two extra IF/THENs? It seems so. In this example, the long ON/GOTO is faster in worst case. Interesting. If worst case is a button not used that often (“smart bomb”), IF/THEN may be the best option, but if all buttons are used equally, there’s probably a point where a long ON/GOTO makes more sense.

But wait … there’s more!

Rob provided a suggestion about using an array:

Yep, could also do something like
Dim C(256)
C(17)=1:C(39)=2:C(41)=3
…
ON C(K) GOSUB 20,30,40
etc.
But that’s probably a bit memory hungry.
Rob

Rob’s idea of using an array to translate the non-sequential values into sequential numbers is a fun one. It uses more memory, and trades the time it takes to do an array lookup for the time it takes to parse a long ON/GOTO/GOSUB line.

Let’s try:

0 REM ONMIAM2.BAS
5 DIM TE,TM,B,A,TT
6 K=17 'BEST CASE
7 DIMK(41):K(17)=1:K(39)=2:K(41)=41
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 ON K(K) GOTO 100,200,300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 REM LEFT
110 GOTO70
200 REM RIGHT
210 GOTO70
300 REM JUMP
310 GOTO70

Since the largest value we need to check for is 41, I did a DIM K(41). That will allow for values from 0 to 41.

Best case (17) gives us 432! Faster than the manual IF/THEN check!

Worse case (41) gives us 432 … Really? ON/GOTO is really fast with just a few choices. It would be slower if there were dozens and you wanted the one at the end.

The downside of this approach is the memory it took for an array of 42 (0-41) variables. Doing something like this:

NEW:CLEAR
PRINT MEM
DIM K(41)
PRINT MEM

…shows me 22823 and 22606. That’s 217 bytes being taken by the 42 K array entries. (There is an entry reserved for the array itself, then each array element takes 5 bytes, I believe. It’s been awhile since I wrote my String Theory articles which I think looked into how variables are stored.)

This may be the fastest approach if you have a few hundred bytes available to use for this. On a VIC-20 with 3583 bytes free on startup, if I had memory left when I was done with my normal IF/THEN version, I could retrofit it with this approach and use that extra available RAM to speed up my program a tad.

Very cool.

Thanks to MiaM and Rob for these interesting ideas.

Until next time…

ON/GOTO/GOSUB with arbitrary values!?!

Leave a reply

Someone named Rob posted a comment to my recent ELSE article that simply contained one line of weird BASIC code:

It looked like Rob was presenting a way to do an ON/GOTO with arbitrary values. Will that actually work?

ON GOTO/GOSUB

ON/GOTO (and ON/GOSUB) normally expects values from 1 to X, and a corresponding line number for each consecutive value:

10 INPUT "ENTER 1-5";A
20 ON A GOTO 100,200,300,400,500
30 GOTO 10
100 PRINT "YOU CHOSE 1":GOTO 10
200 PRINT "YOU CHOSE 2":GOTO 10
300 PRINT "YOU CHOSE 3":GOTO 10
400 PRINT "YOU CHOSE 4":GOTO 10
500 PRINT "YOU CHOSE 5":GOTO 10

If A is 1, it will go to 100. If A is 2, it will go to 200. And so on.

Mind the gaps

If you had wanted gaps in the choices, like 1, 3 and 5, you’d have to fill out the ON/GOTO with numbers for the missing choices:

10 INPUT "ENTER 1, 3 OR 5";A
20 ON A GOTO 100,10,300,10,500
30 GOTO 10
100 PRINT "YOU CHOSE 1":GOTO 10
300 PRINT "YOU CHOSE 3":GOTO 10
500 PRINT "YOU CHOSE 5":GOTO 10

That might be a nice approach if the numbers were relatively close to each other, but at some point, adding a bunch of dummy numbers to the ON/GOTO line would take more time to parse than just using separate IF/THEN statements.

Arbitrary GOTO

My example was based on some VIC-20 code I wrote back in 1983. I was reading which key was currently being held down, and would get back three different values for the keys I was reading:

17 – ‘A’ key is pressed (LEFT)
42 – ‘S’ key is pressed (RIGHT)
39 – ‘F1’ key is pressed (JUMP)

I couldn’t use ON/GOTO for values 17, 42 and 39.

But Rob’s code does just that!

20 ON -(K=41)-2*(K=17)-3*(K=39) GOTO 30,40,50

In BASIC, any comparison returns a -1 if it is TRUE, or a 0 if it is FALSE:

PRINTing the result of a comparison in Color BASIC.

…so in Rob’s example, the checks in parenthesis will be turned in to either a -1 or a 0 based on the value of K.

If K is 41, then (K=42) will be (-1) and (K=17) and (K=39) will both be (0).
If K is 17, then (K=17) will be (-1) and (K=41) and (K=3) will both be (0).
If K is 39, then (K-39) will be (-1) and (K=42) and (K=17) will both be (0).

Let’s see what that does:

20 ON -(K=41)-2*(K=17)-3*(K=39) GOTO 30,40,50

K = 41 produces:
ON -(-1) - 2*(0) - 3*(0) GOTO 30,40,50
ON    1  -    0  -    0  GOTO 30,40,50
ON    1                  GOTO 30,40,50

K-17 produces:
ON -(0) - 2*(-1) - 3*(0) GOTO 30,40,50
ON   0  -    -2  -    0  GOTO 30,40,50
ON            2          GOTO 30,40,50

K-39 produces:
ON -(0) - 2*(0) - 3*(-1) GOTO 30,40,50
ON   0  -    0  -    -3  GOTO 30,40,50
ON                    3  GOTO 30,40,50

Fantastic! Subtracting a negative makes it a positive, and multiplying by zero makes zero.

Math rules! And it actually works:

0 REM robgoto.bas
10 INPUT "41, 17 OR 39";K
20 ON -(K=41)-2*(K=17)-3*(K=39) GOSUB 30,40,50
25 GOTO 10
30 PRINT "30":RETURN
40 PRINT "40":RETURN
50 PRINT "50":RETURN

Fantastic! What a great tip. Thanks, Rob!

Arbitrary benchmark

So of course, I now have to see how this compares to separate IF/THEN’s speed-wise. Let’s pull out the trusty benchmark test code and do a version for best case (first choice) and worst case (last choice) for each approach (Rob’s, and IF/THENs).

Arbitrary ON/GOSUB, best case:

0 REM robgoto1.bas
5 DIM TE,TM,B,A,TT
6 K=41
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 ON -(K=41)-2*(K=17)-3*(K=39) GOSUB 100,200,300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 RETURN
200 RETURN
300 RETURN

This produces 1368.

Arbitrary ON/GOSUB, worse case:

0 REM robgoto2.bas
5 DIM TE,TM,B,A,TT
6 K=39
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 ON -(K=41)-2*(K=17)-3*(K=39) GOSUB 100,200,300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 RETURN
200 RETURN
300 RETURN

This produces 1434

Separate IF/THEN/GOSUB, best case:

0 REM ongoto1.bas
5 DIM TE,TM,B,A,TT
6 K=41
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF K=41 THEN GOSUB 100:GOTO 70
40 IF K=17 THEN GOSUB 200:GOTO 70
50 IF K=39 THEN GOSUB 300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 RETURN
200 RETURN
300 RETURN

This produces 518 – almost three times faster!

Separate IF/THEN/GOSUB, worse case:

0 REM ongoto2.bas
5 DIM TE,TM,B,A,TT
6 K=39
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF K=41 THEN GOSUB 100:GOTO 70
40 IF K=17 THEN GOSUB 200:GOTO 70
50 IF K=39 THEN GOSUB 300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 RETURN
200 RETURN
300 RETURN

This produces 1098, meaning even worst case is still faster.

BUT, we are doing a bunch of number parsing and math here. We can’t do anything about the math, but on Color BASIC, we can change those decimal values to HEX and speed up that part. Let’s try that:

0 REM robgoto3.bas
5 DIM TE,TM,B,A,TT
6 K=41
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 ON -(K=&H29)-&H2*(K=&H11)-&H3*(K=&H27) GOSUB 100,200,300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 RETURN
200 RETURN
300 RETURN

By switching the five integer values in line 30 one to HEX, the speed of best case goes from 1368 to 1150! That’s faster, but it still doesn’t beat 518 using separate IF/THEN/GOSUB.

We might be able to make this a bit faster by using variables, so lets try that:

0 REM robgoto4.bas
5 DIM TE,TM,B,A,TT
6 K=41
7 L=&H29:M=&H2:N=&H11:O=&H3:P=&H27
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 ON -(K=L)-M*(K=N)-O*(K=P) GOSUB 100,200,300
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
100 RETURN
200 RETURN
300 RETURN

This brings the time down slightly to 1092. Still not enough to beat the separate IF/THEN/GOSUB (and that could also be sped up slightly using HEX or variables).

Conclusion

This trick is very cool. From my calculations, it looks like it save code space, which could be very important on a low-memory system like a 4K CoCo or the 5K VIC-20. That alone might make this trick worth doing.

But for speed, such as a BASIC game, it looks like brute force IF/THEN may be a better approach.

It’s really nice to have options. I can’t wait for an opportunity to use this technique in something.

Thanks, Rob, for leaving such a cool comment!

Until next time…

Faster and smaller Color BASIC with Carl England’s CRUNCH

Leave a reply

Making BASIC run faster is hard to automate, but there have been some attempts to do this over the years.

Carl England CRUNCH

No, it’s not that cereal you remember from Saturday morning TV ads. It’s one of the coolest utilities ever created for the CoCo. Carl England wrote quite a few of those, actually.

Carl England was the creator of my all-time favorite Disk Extended BASIC program – Super Boot. It was a superb “type DOS and auto run your program” utility that added many neat features. I have it on many of my RS-DOS disks.

Carl also created THE DEFEATER, a copy utility that could duplicate any copy protected disk. It did not crack the software – it just cloned it, making a duplicate copy protected disk.

Carl also showed off a scanner attachment at the 1990 Atlanta CoCoFest that turned a Tandy DMP printer into scanner! But that’s a story for another time…

Make BASIC small again

Today I want do discuss one of Carl’s programs called CRUNCH. It is a machine language program that will pack a BASIC program to be as small as possible. It does this by removing REMs and unnecessary spaces. It also removes other unnecessary things like “IF X THEN GOTO 100” which could be written just as “IF X THEN 100”. It will even remove trailing quotes at the end of a line (which looked weird, but saved a byte).

But the most important thing it does is pack (er, crunch?) a BASIC program into as few lines as possible. It will take a program like this:

0 REM
1 REM GUESS.BAS
2 REM
3 REM BY ALLEN HUFFMAN
4 REM
5 REM GENERATE RANDOM NUMBER
10 N=RND(100)
15 REM DISPLAY INSTRUCTIONS
20 PRINT "I AM THINKING OF A NUMBER"
30 PRINT "BETWEEN 1 AND 100."
35 REM ASK FOR A GUESS
40 PRINT "WHAT IS YOUR GUESS";
50 INPUT G
55 REM IS GUESS TOO HIGH?
60 IF G > N THEN 100
65 REM IS GUESS TOO LOW?
70 IF G < N THEN 200
75 REM IS GUESS CORRECT?
80 IF G = N THEN 300
85 REM REPEAT
90 GOTO 35
100 REM TOO HIGH
110 PRINT "TOO HIGH!"
120 GOTO 35
200 REM TOO LOW
210 PRINT "TOO LOW!"
220 GOTO 35
300 REM CORRECT
310 PRINT "CORRECT!"
320 END

…and turn it into something like this:

10 N=RND(100):PRINT"I AM THINKING OF A NUMBER":PRINT "BETWEEN 1 AND 100.
40 PRINT"WHAT IS YOUR GUESS";:INPUTG:IFG>N THEN100
70 IFG<NTHEN200
80 IFG=NTHEN300:GOTO 40
110 PRINT"TOO HIGH!":GOTO35
210 PRINT"TOO LOW!":GOTO35
310 PRINT"CORRECT!":END

…except you generally can not list the program afterwards because CRUNCH will combine lines up to the maximum allowed (250 bytes or so?) and create lines too long to be EDITed or LISTed manually.

And, look at line 70 and 80. If you type them, you have to have a space after the variable in “IFG<N THEN…” because the tokenizer needs to know where the variable ends and the next keyword starts. CRUNCH can remove that space, which is impossible to do when typing that in by hand.

Here is what it looks like in operation on the GUESS.BAS program above:

You can select a specific operation to do, or choose 7 and do them all:

In this example, it changed a 519 byte BASIC program into 214. And, if you renumber the results by 1s starting at line zero (RENUM 0,0,1), that will save an addition 9 bytes because “GOTO30” (two digit line numbers) takes up more bytes than “GOTO9” (single digit line numbers).

CRUNCH is pretty amazing. And, you can download it today for free! It is one of the extra utilities in Carl’s DEFEATER disk copy utility package:

https://colorcomputerarchive.com/repo/Disks/Utilities/Defeater%2C%20The%20%28Carl%20England%29%20%28Coco%203%29.zip

While that archive says CoCo 3, CRUNCH itself will work on a CoCo 1/2. At least, it seems to in my testing using the Xroar emulator.

Try CRUNCH out on some of your programs and share the results in the comments. Just keep in mind that it will destroy your ability to edit the program! Save your crunched program under a different name! You can then distribute that crunched copy, or be nice and give folks both the original (hopefully easier to read) and crunched (smaller and faster to run).

Let me know what you think!

Until next time…

Color BASIC challenge: ball bouncing WITHOUT any IFs?

Leave a reply

It seems like all I’m doing lately is regurgitating things that Robin of 8-Bit Show and Tell has already done.

So let’s do that again.

Don’t blame me. Blame YouTube!

YouTube did what YouTube does and it showed me another of Robin’s well-done videos. This one caught my attention because it dealt with the Commodore VIC-20 and its Super Expander cartridge.

The main thing that pulled me away from Commodore was seeing the TRS-80 Color Computer’s Extended Color BASIC. The CoCo had simple commands to play music and draw lines, boxes and circles. It also had this wondrous ELSE command I’d only heard rumors about.

On the VIC-20, it seemed you needed to use POKE and PEEK for just about anything graphics or sound related. Thus I gave up a computer with programmable characters and a hardware sound chip for a machine that had neither. On my new CoCo, at least I could draw a circle and play music without needing pages of DATA statements and cryptic PEEKS and POKEs.

Commodore was aware of this shortcoming, and they sold the Super Expander as a way to make up for it. Not only did it provide an extra 3K of memory (giving a whopping 6.5K for BASIC), it also added new commands to do “high resolution” graphics including drawing lines and circles, as well as ways to PRINT music using simple notation.

I used the Super Expander to do TV titles for fishing videos my father shot and edited. It was a thrill to see my VIC-20 graphics on TV screens at the Houston Boat Show.

But no one else could run my programs unless they had purchased the Super Expander as well.

But I digress.

(And besides, the Commodore 64 was $600 when it came out, and I was able to get a 64K CoCo 1 for $300 at the time.)

Don’t blame YouTube. Blame Twitter.

Robin’s video was making use of the Super Expander to let the VIC-20 solve a challenge initiated by Twitter user Dataram_57. On June 8th, 2019, they wrote:

I challenge every mathematician and programmer to solve this problem. Write the equation that you will use to change the position of the red point according to time and the animation. (You can use every function without if statement)? #programming #math #mathgames #programmer pic.twitter.com/UDgGv1pajB
— D̨̯̞̜͇a̶͙̤t̵̪̤̺̪ͅḁ̱̳̱͠r̡a̦͞m͍̩̗͉͢ (@Dataram_57) June 8, 2019

This was, more or less, a classic bouncing ball program very much like the ones I have been writing about lately. But, all mine certainly made use of IF. Here’s how mine started:

0 REM bounce.bas
10 CLS:X=0:Y=0:XM=1:YM=1
20 PRINT@Y*32+X,"O";
30 X=X+XM:IF X<1 OR X>30 THEN XM=-XM
40 Y=Y+YM:IF Y<1 OR Y>13 THEN YM=-YM
50 GOTO 20

That’s not a very good example. It doesn’t erase itself, nor does it use the bottom line to avoid screen scrolling when the ball hits the bottom right position. It does show how I would use X and Y coordinates then an XM (X movement) and YM (Y movement) variable to increment or decrement them based on if they hit an edge.

The parameters of Dataram_57’s challenge were as follows:

Width: 90
Height: 80
Starting Position: 0,0
Time: ???

I wrote a quick graphical program do do this using my X/Y/XM/YM method:

0 REM dataram_57 twitter challenge
1 POKE 65495,0
10 W=89:H=79:X=0:Y=0:T=0:XM=1:YM=1
20 PMODE0,1:PCLS0:SCREEN1,1
30 LINE(0,0)-(89,79),PSET,BF
40 PSET(X,Y,0)
50 X=X+XM:IF X<0 THEN XM=1:GOTO 50 ELSE IF X>=W THEN XM=-1:GOTO 50
60 Y=Y+YM:IF Y<0 THEN YM=1:GOTO 60 ELSE IF Y>=H THEN YM=-1:GOTO 60
70 T=T+1:IF T=7031 THEN END
80 GOTO 40

The first thing to notice is that I draw a filled box from 0,0 to 89,79 and then set black pixels in it. This lets me visually verify my line is going all the way to the edge of the 90×80 target area. Also, I am using the CoCo 1/2 double speed poke since this is time consuming. If you do this on a CoCo 3, feel free to use POKE 65497,0 instead.

Twitter user Dataram_57’s challenge running on a CoCo.

Eventually the area should be entirely black when every dot has been erased.

How long has this been going on?

I did some tests and figured out that it takes 7032 iterations (0-7031) for the dot to cycle through the entire 90×80 area before it has erased all the other dots.

With that in mind, I propose we turn this into both a logic and optimization challenge. On the CoCo, let’s see if we can use the PMODE 0 screen (128×96 resolution with 1 color). We can put this in a modified version of benchmark framework for 7032 cycles and see how fast we can do it. (By modified, I am removing the outer “try this three times and average the results” loop.)

My example, using IFs, looks like this:

0 REM dataram_57 twitter challenge 2
1 POKE 65495,0
5 DIM TM,A
10 TIMER=0:TM=TIMER

15 W=89:H=79:X=0:Y=0:XM=1:YM=1
16 PMODE0,1:PCLS0:SCREEN1,1
17 LINE(0,0)-(89,79),PSET,BF

20 FORA=0TO7030

30 PSET(X,Y,0)
40 X=X+XM:IF X<0 THEN XM=1:GOTO 40 ELSE IF X>=W THEN XM=-1:GOTO 40
50 Y=Y+YM:IF Y<0 THEN YM=1:GOTO 50 ELSE IF Y>=H THEN YM=-1:GOTO 50

80 NEXT
90 PRINTTIMER:END

Mine, running in Xroar, displays 9808 at the end. And it’s not the correct way to meet the requirements of the challenge, so … the real versions may be faster, or slower.

Your challenge, should you decide to accept it…

Our challenge is to:

Rewrite this to work WITHOUT using any “IFs”.
Try to make it as fast as possible while keeping the benchmark code (lines 5, 10, 20, 80 and 90) intact. You can add variables to the DIM, but otherwise leave those lines alone.

What says you?

Credit where credit is due…

And lastly, for those who want to cheat, here is the solution that Robin came up with using the VIC-20 Super Expander cartridge…

Is his the only way? The best way? The fastest way?

Let the regurgitated challenge begin!

Until next time…

What ELSE can you do when you don’t have ELSE?

16 Replies

NOTE: I have a follow-up to this ELSE thing already written which “changes everything” for me. There’s stuff about ELSE I never knew, which makes me want to never use it. More on that in the next installment. And now back to your regularly scheduled blog post…

First, a quick BASIC memory saving tidbit.

Shaun Bebbington left a comment about my VIC-20 dissection article asking if I knew you could omit zeros from DATA statements like this:

100 DATA 128,0,0,50,239,0,123,42,0,4

If you leave them out (comma comma), READ will still get a zero! It saves a byte each time you do that, which could be important on a machine with 3584 bytes free on startup like my VIC-20.

100 DATA 128,,,50,239,,123,42,,4

Good tip, Shaun! Thanks!

Is there anything ELSE I can help you with?

And while I had his attention, I asked him a few Commodore BASIC questions. I was wondering how you did IF/THEN/ELSE without ELSE! One of the many things I liked about the BASIC in the CoCo was it had ELSE and commands like PLAY, DRAW, CIRICLE, etc. My VIC-20 had no ELSE. In my Sky-Ape-Er game, I’d see my young self doing things like this:

125 IF K=17 THEN L=L-1:M=14
130 IF K=41 THEN L=L+1:M=13
135 IF K=39 THEN 180

In that code snippet, K represented the key value that was pressed. If it was 17 (left), I’d move the player left one and change its graphic character. If it was 41 (right), I’d move the player right one and change its graphics character. If it was 39 (F1, jump), I’d go to a routine that would handle the jump.

Without ELSE, if K was 17, it would do that, then check K two more times, even though it didn’t need to. Maybe I did not “see” it back then, but If I had the bytes to spare, I probably should have done something like this:

125 IF K=17 THEN L=L-1:M=14:GOTO 140
130 IF K=41 THEN L=L+1:M=13:GOTO 140
135 IF K=39 THEN 180

That way, if K=17 was true, it would do it’s thing, then GOTO would skip over the next two lines. This could be a huge time saver if there were a bunch of conditions (up, down, left, right, diagonals, jump, fire, punch, windshield wipers, etc.)

Someone has already suggested that I may have done it my original way to get consistent timing in the game loop. Somehow I doubt my junior high self was that clever. But I digress…

With ELSE, it could have been written like this:

125 IF K=17 THEN L=L-1:M=14 ELSE IF K=41 THEN L=L+1:M=13 ELSE IF K=39 THEN 180

Less code (the ELSE token takes up less memory than an addition line number and/or the extra GOTO to skip lines), and faster execution, maybe.

Side Note: Maybe? There is still the issue of, when completing a successful IF, BASIC’s parser still having to run through the rest of the line characters to find the end and the next line. Adding a “GOTO” wouldn’t help, either, since it would have to parse that and then STILL have to scan to the end of the line. (At least on Color BASIC, which does not remember line pointers once it is parsing a line.) It may actually be faster to break up a long set of IF/ELSE into small lines with a GOTO.

But Shuan mentioned a way of using ON to simulate an ELSE. A quick search led me to a forum post discussing this very thing.

It supposedly works like this… since a compare (K=42, A$=”RED”, G>100) will return either -1 (false) or 0 (true), you can do an ON GOTO based on the result of that compare. Since it’s a -1 or 0, you can just make the result negative (thus, -1 becomes 1, and 0 becomes -0 which is still 0):

10 ON -(A=42) GOTO 20:PRINT "NOT 42":END
20 PRINT "42!"

Er… what? I thought BASIC did not execute anything after a GOTO. It doesn’t, does it?

Nothing on a line after GOTO will be executed. WIll it?

But… but… How can ON/GOTO with something after it work, then? It turns out, ON/GOTO is special since the conditions of the “ON” may not be met, and thus the GOTO part may not get executed and BASIC will continue.

ON A GOTO 100,200,300:PRINT "A WAS NOT 1, 2 or 3"

Looking at it like that makes perfect sense to me. If A is not 1, 2 or 3, it won’t GOTO anywhere and the line continues to be processed.

Thus, this odd code serves as a simple “ELSE” when you don’t have ELSE:

10 INPUT "VALUE";A
20 ON -(A=42) GOTO 30:GOTO 10
30 PRINT "YOU KNOW THE ANSWER!"

…would be like…

10 INPUT "VALUE";A
20 IF A=42 THEN 30 ELSE 10
30 PRINT "YOU KNOW THE ANSWER!"

Interesting! I have not benchmarked this to see if it’s faster than using GOTO to skip lines, but it might be smaller due to not needing another few bytes for each line number.

Would this have helped my “left, right, jump” code? Maybe not. You can string these together like this:

124 ON -(K=17) GOTO 125:ON -(K=42) GOTO 130:ON -(K=39) GOTO 180
125 L=L-1:M=14:GOTO 140
130 L=L+1:M=13:GOTO 140

Since I was doing code in response to the IF, the ON/GOTO approach would just let me GOTO a line that does that code, which then still needs a GOTO to skip the lines after it that shouldn’t be executed. Not great for that use.

But, if I were dispatching to routines based on direction (like I do with the “jump” check to line 180), it would have worked just fine. Instead of this:

125 IF K=17 THEN 200
130 IF K=41 THEN 300
135 IF K=39 THEN 400
...
200 REM Handle LEFT
...
300 REM Handle RIGHT
...
400 REM Handle JUMP
...

Those three lines could be combined into one like this:

124 ON -(K=17) GOTO 200:ON -(K=42) GOTO 300:ON -(K=39) GOTO 400

But, doing a quick test typing in JUST those lines on a VIC-20 emulator, I got 3530 bytes free after each approach. No penalty, but no savings, and all the parsing with parens and the negatives is probably slower.

Interesting, for sure. Useful? I guess I’ll find out if I get around to updating my VIC-20 code.

Bonus offer

I also saw this example in the Commodore forum:

10 rem if then else demo
20 input a
30 if a = 1 then goto 60
40 print "this is the else part"
50 goto 70
60 print "this is the if (true) part"
70 end

This is how I’d write that with ELSE:

20 INPUT A
30 IF A=1 THEN PRINT "THIS IS THE IF (TRUE) PART" ELSE PRINT "THIS IS THE ELSE PART"

So we could change the Commodore example to match this a bit closer:

20 input a
30 if a = 1 then print "this is the if (true) part":goto 70
40 print "this is the else part"
70 end

…which leads us back to just adding a GOTO at the end of each separate IF:

10 GET A$:IF A$="" THEN 10
20 IF K$="U" THEN Y=Y-1:GOTO 70
30 IF K$="D" THEN Y=Y+1:GOTO 70
40 IF K$="L" THEN X=X-1:GOTO 70
50 IF K$="R" THEN X=X+1:GOTO 70
60 GOTO 10
70 REM DRAW X,Y...
80 GOTO 10

…which on the CoCo’s Extended Color BASIC might look like:

10 GET A$:IF A$="" THEN 10
20 IF K$="U" THEN Y=Y-1 ELSE IF K$="D" THEN Y=Y+1 ELSE IF K$="L" THEN X=X-1 ELSE IF K$="R" THEN X=X+1 ELSE 10
70 REM DRAW X,Y...
80 GOTO 10

Ultimately, we are just trading “ELSE” with “GOTO xx” and a new line, with ELSE being smaller due it it just being a token, verses the overhead of a GOTO token and the line number characters after it, AND a new line for each additional “else” condition.

Until next time, ELSE maybe sooner…

VIC-20: Sky-Ape-Er code dissection – part 2

Leave a reply

See also: part 1, part 2, part 3, part 4 or part 5 (with more coming).

Welcome to my second VIC-20 Tuesday!

Previously, I began to dissect my old VIC-20 game Sky-Ape-Er. It was made up of two BASIC programs:

INSTRUCTIONS – Display instructions, set up custom character set, then load and run the main game.
SKY-APE-ER – The main game.

VIC-20 custom fonts

The VIC-20 did not have a true graphics screen. Instead, it used font characters that could be dynamically changed. Each character on the 22×20 screen was 8×8. You could create custom 8×8 characters to represent anything you wanted.

I believe I used a program called Eight by Eight Create by Robert Spahitz from the January 1983 issue of Creative Computing (Vol 9, Number 1). See page 270 (or 272 of this PDF scan):

https://archive.org/details/creativecomputing-1983-01/page/n271/mode/2up

Or this text version of just the article.

This also helps me confirm that I got my VIC-20 in 1982 since I initially did not have a Commodore Datasette tape deck for it and had no way to save programs until later. By the time this issue came out, I had the tape deck.

But I digress…

VIC-20 custom fonts on the CoCo

I have screen shots of what the custom characters looked like in the VIC-20 game, but thought it would be fun to take those DATA statements and display them on my CoCo. Using lines 100 to 125 from the INSTRUCTIONS program, I created this Color BASIC program:

0 REM skychars.bas
5 POKE 65495,0
10 CLS:XO=4:YO=2
15 DIM BM(7):FOR A=0 TO 7:BM(7-A)=(2^A):NEXT
20 FOR R=0 TO 7
25   READ V:IF V=-1 THEN 99
30   FOR C=0 TO 7
35     IF V AND BM(C) THEN SET(XO+C,YO+R,8) ELSE RESET(XO+C,YO+R)
40   NEXT
45 NEXT
50 XO=XO+10:IF XO>60 THEN XO=4:YO=YO+10
55 GOTO 20
99 GOTO 99
100 DATA223,223,223,0,253,253,253,0,0,0,0,0,1,3,3,7,0,60,126,219,129,165,165,129
105 DATA0,0,0,0,128,192,192,224,31,63,127,255,252,254,127,63,0,126,126,0,255,0,231,231
110 DATA248,252,254,255,63,127,254,252,15,7,8,30,31,31,31,31,231,219,60,255,126,126
115 DATA189,195,240,224,16,120,248,248,248,248,31,31,31,15,15,63,127,0,231,129,0,0,129
120 DATA129,129,0,248,248,248,240,240,252,254,0,12,12,24,47,8,15,82,36,48,48,24,244,16
125 DATA240,74,36,28,8,28,42,8,20,20,54,12,76,40,47,40,159,82,36
130 DATA -1

It now displays what those font characters look like: