See also: part 1, part 2, part 3, part 4, part 5, part 6, part 7 and more (coming “soon”).

NOTE: I have a really great comment to share with you from a recent installment, but it deserves an article of it’s very own. Thank you, Jim, for the assembly sample. I’ll be getting to that soon…

Meanwhile, William Astle once again comments with some explanations to move this topic forward:

The KEYBUF thing is actually a lot more straight forward than it looks. It basically holds the result of reading FF00 for each keyboard column as of the last time KEYIN ran. More specifically, the last time it got to actually reading that column since it stops as soon as it finds a new key press and, so, it won’t necessarily update all eight entries in KEYBUF every time. It will when no new keys are pressed, though.

Basically, what it does is this:

Read the data from FF00
EOR it with the relevant byte in KEYBUF; this sets any bit where the value has changed since the last read; that is, a key was pressed or released. Exclusive OR yields a 1 if its two inputs are different and a 0 if the two inputs are the same.
AND the result of (2) with the KEYBUF value. This will keep only bits where the previous result was a “1” (not pressed). That ignores any keys that were released or are held down (previous state being a “0” in both of those cases).
Store the value read from FF00 into the KEYBUF byte using a copy of the original read from FF00.
If The result of (3) is nonzero, it stops reading the PIA and decodes the new keypress, does the debounce thing, etc.

KEYIN also masks off the joystick comparator input so you won’t see that in KEYBUF. Further, when reading the column with SHIFT in it, it masks that as well. So you can’t test for shift by looking in KEYBUF.

Basically, what the POKEs do is trick KEYIN into thinking that no keys in those particular columns were previously pressed by setting the bits to “1”.

As a side note, you can detect keys that are currently pressed by PEEKing KEYBUF. As long as Basic is doing its BREAK check, KEYIN is getting called at least once before every statement so KEYBUF gets updated.

William Astle

I’m glad there’s someone around here who understands this stuff. But it was his last paragraph that caught my attention. If we can just PEEK those values, INKEY$ isn’t even necessary (offering a slight speedup, perhaps).

Let’s look at what’s inside those eight KEYBUF locations. To make them fit on a 32 column screen, I will print them out as HEX values:

0 REM keyboard.bas
10 FOR A=338 TO 345:POKE A,&HFF
20 PRINT HEX$(PEEK(A))" ";
30 NEXT:PRINT:GOTO 10

Run this and you will see eight columns of hex values that represent the KEYBUF status of most of the keys. And by POKEing each value to 255 (&HFF for speed) before they are read, it allows detecting the key as long as it is being held down. You can now see the status of the arrow keys, including if you pressed two at the same time (Up+Left).

Let’s display this in bits so we can visualize which bits we care about:

0 REM keyboard2.bas
5 POKE 65495,0:CLS:FOR BT=0 TO 7:BT(BT)=INT(2^BT):NEXT
10 PRINT@0,;:FOR A=338 TO 345:POKE A,&HFF:PRINT A;:V=PEEK(A)
20 FOR BT=7 TO 0 STEP-1:IF V AND BT(BT) THEN PRINT "1"; ELSE PRINT "0";
30 NEXT:PRINT:NEXT:GOTO 10

Running this will display eight lines representing the bits in each of those memory locations. Here is what it looks like when all four arrow keys are held down at the same time:

I see that SPACE is also in its own column, likely by design for this very purpose – games. One would want to be able to detect ARROWS and SPACE independently which would not be possible if any of them used the same column.

With this in mind, we can try to just read those keys (Up, Down, Left, Right and Space) as fast as possible.

Read those keys as fast as possible

To be nice and flexible, we should take the PEEK of one of those values and AND off the bit(s) we care about and act upon that. This allows detecting just the key we want even if something else in that column is also being held down. Since we are going for speed, we’ll just say the user isn’t allowed to do that. Press Up and that’s okay. Press Up and S (another key in the same column) and the player won’t move. Maybe we can improve that later.

Using the first keyboard.bas listing as reference, it looks like it will be easy to detect these five keys by checking the PEEK value against &HF7. As long as only the Up, Down, Left, Right or Space is held down in that column, the value will be &HF7. This gives us something like this:

0 REM arrows.bas
10 CLS:L=16+32*8
20 POKE&H155,&HFF:POKE&H156,&HFF:POKE&H157,&HFF:POKE&H158,&HFF:D=.
30 IF PEEK(&H155)=&HF7 THEN D=-&H20
40 IF PEEK(&H156)=&HF7 THEN D=&H20
50 IF PEEK(&H157)=&HF7 THEN D=D-&H1
60 IF PEEK(&H158)=&HF7 THEN D=D+&H1
70 IF L+D<&H1FF THEN IF L+D>=. THEN L=L+D
80 IF PEEK(&H159)=&HF7 THEN PRINT@L,"O"; ELSE PRINT@L,"X";
90 GOTO 20

For speed, decimal values have been replaced with hex, and zeros have been replaced with “.” (yeah, it’s weird, but it’s faster). We could further optimize by removing spaces and combining some of the lines (and cheating by replacing the GOTO loop with a FOR/NEXT/STEP 0 hack), but for now, we’ll start with this.

When you run this program, it prints an “X” in the center of the screen. Using the arrow keys you can move the X around, leaving a trail. Hold down space, and you leave a trail of Os. There is limited checking to make sure you don’t try to print off the top or bottom of the screen.

We are now directly PEEKing the KEYBUF keyboard rollover table looking for those specific keys. We have key repeat, and the ability to detect multiple keys at the same time (such as UP+LEFT+SPACE).

Here’s what the code is doing:

• Line 10 clears the screen and sets the PRINT@ location variable to the center of the screen.
• Line 20 resets the four KEYBUF column values of the arrow keys. We don’t do this with the SPACE since it doesn’t seem to be needed (why not???). The movement delta value is set to 0 (this will be added to the PRINT@ location later).
• Line 30-40 checks for UP and DOWN, and set the delta (movement) value to either -32 (moving up) or +32 (moving down).
• Line 50-60 checks for LEFT and RIGHT, and ADD them to any existing delta value. This means UP could have set it to -32 and RIGHT could have added +1 to that, resulting in a delta of -31 (up and to the right).
• Line 70 checks to see if the result of current location plus new delta is within the screen by being less than PRINT@511 or greater or equal to PRINT@0. If valid, it adds the delta to the location variable. Note we are using the “IF THEN IF” optimization trick that I learned about in this video from Robin @ 8-bit Show and Tell.
• Line 80 checks for SPACE and then PRINTs an “X” or an “O” depending on if space is pressed or not.
• Line 90 goes back and does it all again.

Here we have a very simple routine for moving something around the screen using PRINT@ coordinates (0-511). For a game, we would probably want to change this to using POKE screen locations (1024-1535) so we could PEEK to detect walls or enemies and such.

Since the title of this article series has the word “benchmark” in it, I suppose the next thing we should do it look at different ways to do this and find the ones that are faster.

To be continued…

See also: part 1, part 2, part 3, part 4, part 5, part 6, part 7 and more (coming “soon”).

Updates:

• 2020-12-13 – Fixed a typo in the last BASIC example. Thanks, Johann K.
• 2020-12-14 – Fixed a typo in a PEEK command. My bad.

Over in the Facebook CoCo group, Jim McClellan posted a tidbit about reading the CoCo keyboard in BASIC:

I self answered a question I had and figured maybe this might be helpful info for other BASIC peeps. The location for whether a key is beng pressed is 65282. It’s either 255 (yes) or 0 (no) By peeking location 135 (135 retains the ASCII value of the key pressed even after releasing the key) and ANDing 65282, you can get a smooth, repeating key.

10 KBD=PEEK(135) AND PEEK(65282)
20 PRINT KBD
30 GOTO 10

Jim McClellan

Using standard BASIC commands, we have INKEY$ available to detect a keypress:

10 A$=INKEY$:IF A$="" THEN 10
20 PRINT "YOU PRESSED ";A$

This works great, and I have mentioned it in earlier articles on this site including one showing a way to use it without the variable by using it as a parameter of INSTR inside an ON GOTO.

But I digress.

INKEY$ only gets you the first press. It will not detect if the key is being held down. This limits its usefulness to one-key selections (without needing to press ENTER) and perhaps turn-by-turn games where you have to press a directional arrow over and over to move from position to position.

Most games want to move as long as you are holding down the arrow key, and Jim was sharing a way to do that easily by using PEEK.

What the PEEK is going on?

I wanted to understand what these PEEKs are doing, so I consulted the Color BASIC Unravelled book:

0146   0087   IKEYIM   RMB   1   *TV INKEY$ RAM IMAGE

Memory location 135 (&H87 hex) contains the last key handled by INKEY$. Except, that must not be technically correct because it works without calling INKEY$. Looking further into the disassembly, I see that it is actually where the BREAK CHECK stores the key it found:

It checks for BREAK and also the PAUSE key (SHIFT+@ on the CoCo keyboard, which now I see returns as &H13 from the “GET A KEYSTROKE ENTRY” routine). Thus, while INKEY$ uses this location…

…it is not involved with setting that location. (Note to self: Explore what KEYIN does.)

Doing a PEEK(135) will return whatever the last pressed key was, as detected by the looping BREAK check code. By itself, you could use this for a game where the player never stops moving, or only stops when you press a “stop moving” key.

GAME: Never Stop Moving using PEEK

0 REM nsm.bas
10 CLS0
20 PRINT STRING$(32,153);
30 FOR A=0 TO 12
40 PRINT CHR$(153);STRING$(30,32);CHR$(153);
50 SOUND 200-A*2,1:NEXT
60 PRINT STRING$(32,153);
70 L=1024+8*32+16:SC=0
80 POKE L,255:SOUND1,1
90 K=PEEK(135)
100 IF K=94 THEN M=-32
110 IF K=10 THEN M=32
120 IF K=8 THEN M=-1
130 IF K=9 THEN M=1
140 POKE L,96:IF PEEK(L+M)=96 THEN L=L+M ELSE 200
150 PRINT @480,SC;:IF K<>0 THEN SC=SC+1
160 GOTO 80
200 SOUND 1,5
210 PRINT @32*7+11,"GAME OVER!";
999 GOTO 999

In this pointless game (though I’ve seen worse for smartphones), you begin moving a red block around the screen using the arrow keys. Once you start moving, it will never stop unless you crash into a wall, ending the game. How high of a score can you make?

GAME: Never Stop Moving using INKEY$

It would have been easier (and more portable) to do this without PEEK and use INKEY$. All we would have needed was a check for no key being pressed, and then continue using the last direction used. Something like this would work:

0 REM nsm2.bas
10 CLS0
20 PRINT STRING$(32,153);
30 FOR A=0 TO 12
40 PRINT CHR$(153);STRING$(30,32);CHR$(153);
50 SOUND 200-A*2,1:NEXT
60 PRINT STRING$(32,153);
70 L=1024+8*32+16:SC=0
80 POKE L,255:SOUND1,1
90 K$=INKEY$:IF K$<>"" THEN K=ASC(K$)
100 IF K=94 THEN M=-32
110 IF K=10 THEN M=32
120 IF K=8 THEN M=-1
130 IF K=9 THEN M=1
140 POKE L,96:IF PEEK(L+M)=96 THEN L=L+M ELSE 200
150 PRINT @480,SC;:IF K<>0 THEN SC=SC+1
160 GOTO 80
200 SOUND 1,5
210 PRINT @32*7+11,"GAME OVER!";
999 GOTO 999

By avoiding CoCo-specific PEEKs, this version may run on an MC-10 or Dragon.

But, using PEEK may be faster since it has less BASIC to churn through than an INKEY$, IF and ASC() conversion. (Note to self: Benchmark PEEK versus INKEY$, assuming I haven’t already done that in an earlier article.)

But what if you wanted the player to move ONLY when the key is being pressed down? INKEY$ cannot do that, and neither can PEEK(135). That’s where the second memory location come in to play:

Decoding the (keyboard) Matrix

The Unraveled book shows that memory location 65282 (&HFF02) is part of a PIA that is hooked to the keyboard column matrix. BASIC uses this to determine which key is being held down:

Two bytes earlier is a similar value for the keyboard rows:

These bits are set or clear based on what key in the keyboard matrix is being held down.

                Color Computer Keyboard Array 
    Pin 1 --- @ --- A --- B --- C --- D --- E --- F --- G 
              |     |     |     |     |     |     |     | 
    Pin 2 --- H --- I --- J --- K --- L --- M --- N --- O 
              |     |     |     |     |     |     |     | 
    Pin 3 nc  |     |     |     |     |     |     |     | 
              |     |     |     |     |     |     |     | 
    Pin 4 --- P --- Q --- R --- S --- T --- U --- V --- W 
              |     |     |     |     |     |     |     | 
    Pin 5 --- X --- Y --- Z -- UP -- DWN - LFT - RGT - SPACE 
              |     |     |     |     |     |     |     | 
    Pin 6 --- 0 -- 1! -- 2" -- 3# -- 4$ -- 5% -- 6& -- 7' 
              |     |     |     |     |     |     |     | 
    Pin 7 -- 8( -- 9) -- :* -- ;+ -- ,< -- -= -- .> -- /? 
              |     |     |     |     |     |     |     | 
    Pin 8 -- ENT - CLR - BRK - ALT - CTL - F1 -- F2 - SHIFT 
              |     |     |     |     |     |     |     | 
    Pin 9 -----     |     |     |     |     |     |     | 
                    |     |     |     |     |     |     | 
    Pin 10 ----------     |     |     |     |     |     | 
                          |     |     |     |     |     | 
    Pin 11 ----------------     |     |     |     |     | 
                                |     |     |     |     | 
    Pin 12 ----------------------     |     |     |     | 
                                      |     |     |     | 
    Pin 13 ----------------------------     |     |     | 
                                            |     |     | 
    Pin 14 ----------------------------------     |     | 
                                                  |     | 
    Pin 15 ----------------------------------------     | 
                                                        | 
    Pin 16 ---------------------------------------------- 

But, from my testing, just PEEKing these I/O values does not work, at least not on Color BASIC 1.1. (Keyboard scanning changed a bit in later version of the Color BASIC ROMs.) I am unfamiliar with using the PIA so there may be some other things that have to be done to set it up before you can read it. Still, just PEEKing doesn’t do it for me.

10 PRINT PEEK(65282):GOTO 10

I get 255s over and over, though sometimes it looks like it might be blipping to a different value. To catch the changes, I tried this:

10 P=PEEK(65282)
20 IF P<>LP THEN PRINT P:LP=P
30 GOTO 10

Jim says it is 0 if nothing is pressed, or 255 if any key is being held down. From looking at the matrix, even if this did work, it seems like it would only be 0 if nothing was held down in any column, and 255 if a key was held down in each column. Can this be correct?

So I ask the audience: Why does this work for Jim, but not in the Xroar emulator I am using?

Comments are apprecaited!

To be continued…

See also: part 1 and part 2.

A Faster Base-64

I had planned to end this series with this third part, giving a simple way to turn 8-bit value DATA statements into Base-64 DATA statements. But smarter folks than I have looked at my previous work, so now my plans have changed. We will need an extra part or two… or three.

Today, let’s highlight some comments made to previous installments.

The always thought-provoking MiaM wrote:

I would had written out the 2 exponent values directly as 4, 16 and 64 rather than using INT(2^2).

The decdode-4-“chars”-to-3-bytes parts could use a modified base 64 thingy where you have the first 6 bits of three bytes in a row, and the fourth “char” contains the upper two bits for the previous three “chars”/bytes. Or the other way around, start with the “char” that contains the upper two bits for the following three chars and put that in a numerical variable. Then have a loop that runs three times. Each time first shift the “upper two bits” variable two steps left, i.e. multiply by 4, and then read a “char” and to that char OR the result of the “upper two bit” variable ANDed with 192 (=%110000).

That format would be incompatible with the standardized representation used by BASE 64, but it would indeed be a format with the same density and using the same characters.

Btw you could use the “BASE 90” as a way to slightly compress some data, by just having the values >63 represent two instances of the actual value minus 64. That might not save much, but perhaps worth investigating.

MiaM

Very good point! Eliminating “power of two” calculations and changing them to hard coded values should offer a noticeable speed increase. Pre-calculating values (i.e. writing 4 instead of 2^2) is a good way to save some time, and possibly space too (since “2^2” takes up more memory than “4”).

Normally I would go on a Benchmarking BASIC tangent, but I will save that for later.

I was more intrigued by the concept of making an easier to parse Base-64 format. Since the original goal of this article was to cram as much type-able DATA numbers as possible in to a BASIC program, there is nothing that says it needs to follow the standard Base-64 encoding format. Any format that gets more bits of data in to type-able DATA values would suffice.

This opens up an opportunity to tweak the encode/decode method to be easier to do in BASIC. Mia suggests something like this:

Instead of the standard Base-64 encoding of three 8-bit values into four 6-bit values:

+- Byte 1 --+- Byte 2 --+- Byte 3 --+
| 000000|00 | 0000|0000 | 00|000000 |
| \__A__/\___B___/ \___C___/ \_D__/

We could alter the encoding into a different version:

+- Byte 1 --+- Byte 2 --+- Byte 3 --+
| 00|000000 | 00|000000 | 00|000000 |
| \| \_A__/   \| \_B__/ | |/ \_C__/ |
|  \___________D__________/

The benefit here is that decoding this in BASIC could be done much easier and faster. Rather than all the multiplication/division needed to shift bits and then combine them into bytes, it could be as simple as this a few ANDs and divides. Here’s a rough example of converting three 8-bit (0-255) input values (A, B and C) into four 6-bit (0-63) output values (O1, O2, O3 and O4).

0 REM 6BIT.BAS
1 REM As proposed by MiaM

10 READ A,B,C
15 REM --XXXXXX of A
20 O1=(A AND &H3F)

25 REM --XXXXXX of B
30 O2=(B AND &H3F)

35 REM --XXXXXX of C
40 O3=(C AND &H3F)

45 REM XX------ of A
50 O4=(A AND &HC0)/4

55 REM XX------ of B
60 O4=O4+(B AND &HC0)/16

65 REM XX------ of C
70 O4=O4+(C AND &HC0)/64

75 PRINT "ENCODED:"
80 PRINT A;B;C,O1;O2;O3;O4

85 A=0:B=0:C=0
90 A=O1+INT(O4 AND &H30)*4
100 B=O2+INT(O4 AND &HC)*16
110 C=O3+INT(O4 AND &H3)*64

120 PRINT "DECODED:"
125 PRINT O1;O2;O3;O4,A;B;C

1000 DATA 111,222,123

Running this program displays:

The three 8-bit input values (111, 222 and 123) are converted into four 6-bit output values, then those four are turned back into three 8-bit values to verify it worked.

The conversion is very simple, since the output values O1, O2 and O3 are just the right 6-bits of the input values A, B, and C, which can be obtained by using AND to mask off the top two bits:

20 O1=(A AND &H3F)
30 O2=(B AND &H3F)
40 O3=(C AND &H3F)

Optimization Note: We could save a few bytes by omitting the parenthesis and the space before the &H3F. Due to how the Color BASIC’s parser works, we need the space between the variables (A, B and C) and the keyword “AND”. That space is what tells the tokenizer we want a variable followed by the keyword AND, versus a variable that starts with “AA”:

A=255

PRINT A AND 4
4

PRINT A AND4
4

PRINT AAND4
0

Above, Color BASIC thinks the third example is a variable called “AAND4” which is truncated to just be “AA” since Color BASIC only cares about the first two characters of a variable name:

A=255
AAND4=42

PRINT AAND4
42

PRINT A AND4
4

Oh the fun bugs that must have caused me back in the day!

But I digress…

The fourth byte is built by doing the opposite AND to get only the top two bits of A, then a divided that by 4 to shift them to the right 2 bits (AA—— to —AA—-), then do the same mask to B and divide by 16 to shift them 4 bits to the right (BB—— to ——BB–) and again for C divided by 64 to shift 6 bits to the right (CC—— to ——CC) and then add them together to make the result (–AABBCC).

50 O4=(A AND &HC0)/4
60 O4=O4+(B AND &HC0)/16
70 O4=O4+(C AND &HC0)/64

I think I did a poor job explaining that. But here it is visually:

INPUT (three 8-bit values):

A: aaAAAAAA
B: bbBBBBBB
C: ccCCCCCC

OUTPUT (four 6-bit values):

O1: --AAAAAA
O2: --BBBBBB
O3: --CCCCCC
O4: --aabbcc

Maybe that helps.

Doing it this was can be done faster and with less code, I think. Some benchmarking needs to be done to see if AND is faster than addition for combining the values, and the O4 line can just be made as one thing without the intermediate line numbers and steps:

50 O4=(A AND &HC0)/4+(B AND &HC0)/16+(C AND &HC0)/64

We will want to make the decoder as small as possible, since if we save 100 bytes doing BASE-64 over HEX and the decoder takes more than 100 bytes it defeats the purpose.

Maybe we can figure out this “base 90” concept in a future article, as well.

To be continued…

See also: part 1

Today we will explore writing a standard base-64 converter in BASIC, and then see if we can make a smaller and faster (and nonstandard) Color-BASIC-specific one.

When we last left off, we were looking at ways to get as much encoded data on to a DATA statement as possible. Instead of using integer numbers (base-10) or hex values (base-16), we began exploring if we could increase the base and use more typeable character to encode the data.

Although it seems we could create a weird base-90 format using every typeable character except for quote (which we’d need to start a DATA line else we couldn’t use comma), the decoder would be much larger and have to do much more work, and we actually wouldn’t benefit since we really need numbers that round to specific numbers of bits:

• Base-8 (octal) values can be represented by 3-bits (111). (Extended BASIC supports octal when you use &Oxx or just &xx.)
• Base-16 (hexadecimal) values can be represented as 4-bits (1111). (Extended BASIC supports hexadecimal when you use &Hxx.)
• Base-32 values would be represented as 5-bits (11111).
• Base-64 values would be represented as 6-bits (111111).
• Base-128 values would be represented as 7-bits (111111).

As you can see, a base-90 value isn’t a large enough range to give us an extra bit over base-64. We need to use bases that are nice multiples of the power of 2. Because of this, we’ll ignore a made-up base-90 and look at something a bit more standard, such as base-64 encoding.

Pump up the base

As previously discussed, natively, you can represent a number in a DATA statement as a base-10 value, or a hexadecimal value. Both of these are the value 32:

100 DATA 32,&H20

BASIC will READ them the same way, though hex values are much faster for BASIC to read and parse. Using native hex values like “&H20” is the fastest way to load DATA, but it is also the largest since every value has two extra characters (“&H”) in front.

A recent tip was given by Shaun Bebbington about how you can represent zero just by leaving it out between commas. It saves space, and the parse gets zero from this faster than if you put a zero there:

100 DATA 8,6,7,5,3,,9

But since we are trying to get as much DATA in there as possible, we don’t want to separate numbers by commas. We can pack all the 2-digit hex values together in a string then read that entire string and parse out the individual 2-digit hex values. That is more work, and slower, but gets more data per DATA line. Here are the values 0 to 15 in hex (00 to 0f):

100 DATA 000102030405060708090A0B0C0D0E0F

As previously demonstrated, this is the most efficient way to store HEX values. Even when we pad a low 0-15 value to make it two digits (1 represented by 01), it stills saves space over comma delimited values since no commas are used.

But each hex value is wasting 50% of the bits it takes to represent it. HEX values of 0-15 could be represented by four bits (0000 to 1111). We are storing them as one 8-bit character and thus achieving 50% storage efficiency.

We can do better by using a higher base-x value that can use those wasted bits. We want the highest value we can represent with typeable characters, which is 64 (since the next higher would be 128 and we don’t have a way to type 128 different characters on the CoCo).

Base-64

The standard Base-64 encoding uses the following 64 characters to represent values of 0 to 63:

ABCDEFGHIJKLMNOPQRSTUVWZYZabcdefghijklmnopqrstuvwxyz01234567890+/

Each base-64 character needs 6-bits to be represented (000000-111111).

Representing values that way only wastes 2 bits per character, rather than 4-bits like hex base-16 does:

ASCII HEX Chars.:    ASCII Base-64 Chars.:
      0    15              0    63
     "0"   "F"            "A"   "/"
     /       \            /       \
xxxx0000  xxxx1111   xx000000   xx111111

But, converting to and from base-64 is much trickier. Hex base-16 is as simple as this:

• Hex “F0” -> F is 15 which is 1111 in binary. 0 is 0000 in binary. Thus the first character becomes the left four bits, and the second character becomes the right four bits. Super easy. Barely an inconvenience. Two ASCII bytes represent one byte of data.

But for base-64, we are dealing with 6-bits, and two of those won’t fit into an 8-bit byte. Instead, four base-64 6-bit values are merged together to make a 3-byte 24-bit value.

• Base-64 “ABCD” (xx000000 xx000001 xx000010 xx000011) -> A is 0 which is 000000 in binary. B is 1 which is 000001 in binary. C is 2 which is 000010 in binary. D is 3 which is 000011 in binary. These values are merged together (removing the unused 2-bits in each one) and stored in 3 bytes as:

+- Byte 1 --+- Byte 2 --+- Byte 3 --+
| 000000|00 | 0001|0000 | 10|000011 |
| \__A__/\___B___/ \___C___/ \_D__/

• Byte 1 contains 6 bits of base-64 value A and 2 bits of base-64 value B.
• Byte 2 contains 4 bits of base-64 value B and 4-bits of base-64 value C.
• Byte 3 contains 2 bits of base-64 value C and 6 bits of base-64 value D.

Well that’s a mess. Moving bits around like that is super easy under languages like C, but a bit more work in BASIC.

Encode this!

We will start with encoding a simple ASCII string into base-64 using a web tool:

https://www.base64encode.org

If you go to that link, you can type something in and then encode it into base-64. I typed:

Greetings from Sub-Etha Software! Do you know where your towel is?

And that gets encoded into this:

R3JlZXRpbmdzIGZyb20gU3ViLUV0aGEgU29mdHdhcmUhIERvIHlvdSBrbm93IHdoZXJlIHlvdXIgdG93ZWwgaXM/

Each character represents a 6-bit (0-63) value which we will have to combine into 8-bit values and decode.

An easy way to decode the characters used by base-64 encoding is with a string:

10 Z$="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

We can use Extended BASIC’s INSTR() function to match a character from the encoded string with a character in that string, and the position it is found in will the the value it represents (well, minus 1, since INSTR returns a base-1 value).

Here is an example that will display the bytes of the encoded string:

0 REM base64-1.bas
10 Z$="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
20 READ A$:PRINT A$
30 FOR A=1 TO LEN(A$)
40 PRINT INSTR(Z$,MID$(A$,A,1))-1;
50 NEXT
1000 REM BASE-64 DATA
1010 DATA R3JlZXRpbmdzIGZyb20gU3ViLUV0aGEgU29mdHdhcmUhIERvIHlvdSBrbm93IHdoZXJlIHlvdXIgdG93ZWwgaXM/

Running that shows me this:

If A is 0, then R should be 17, and that is what it prints first. Now we know we can get the values for each character in a base-64 encoded string.

Next we have to turn four 6-bit base-64 values into three bytes (24-bits). I am not sure what a good way to do this is, so I’ll just brute-force it and see how that works out.

First, I know that I need four base-64 values to make my 3 8-bit values, so I’ll modify my loop to skip every four values, and then add an inner loop to process the individual four base-64 values.

Inside that inner loop it will process the next four base-64 6-bit values and convert them into 3 8-bit values.

Here is what I came up with:

0 REM base64.bas
5 POKE65395,0
10 Z$="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
20 READ A$
30 FOR A=1 TO LEN(A$) STEP 4
35 REM GET 4 6-BIT VALUES
40 FOR B=0 TO 3:B(B)=INSTR(Z$,MID$(A$,A+B,1))-1
50 IFB(B)<0 THEN B(B)=0
60 NEXT
65 REM CONVERT TO 3 8-BIT
70 C1=INT(B(0)*INT(2^2)) OR INT(B(1)/INT(2^4))
80 C2=(B(1) AND &HF)*INT(2^4) OR B(2)/INT(2^2)
90 C3=(B(2) AND &H3)*INT(2^6) OR B(3)
100 PRINT CHR$(C1);CHR$(C2);CHR$(C3);
110 NEXT
120 END
1000 REM BASE-64 DATA
1010 DATA R3JlZXRpbmdzIGZyb20gU3ViLUV0aGEgU29mdHdhcmUhIERvIHlvdSBrbm93IHdoZXJlIHlvdXIgdG93ZWwgaXM/

I figured out all the 6-bit to 8-bit stuff (lines 70-90) with alot of trial and error, so I expect there is a faster and easier way to do this. But, then end results is a program that will print out the expected message, albeit really slowly.

One unexpected problem was with the powers of two — (2^2) and such. They produce rounding errors which caused some bits to be lost. I had to use INT() round them. That took me hours to figure out, but it’s just part of the inaccuracies of floating point values, especially limited ones like a 1970s BASIC used.

PROBLEM: Since the goal here is to put more data in DATA statements, the base-64 decode routine needs to be small. If it is 100 bytes larger than just using HEX, you have to save 100 bytes in DATA before you break even. The routine I give is not small and not fast. It would probably not be useful in the 10 LINE contest I mentioned. Maybe one of you can help improve it.

Now that we have a simple base-64 decoder, the next step will be making an encoder to turn DATA statement values into a base-64 string.

Until next time…