Classic Computer Magazine Archive COMPUTE! ISSUE 37 / JUNE 1983 / PAGE 188

An Interesting
Fragment Of Code
Chris Crawford

This fascinating byte-folding idea has several potential uses for machine language programmers. If you find it obscure, however, try out the applications note on an Atari to see one of the effects it makes possible.

Three years ago, a programmer showed me a fragment of code and challenged me to figure out what it did. After a great deal of head-scratching and paper-scribbling, I had to admit that I couldn't figure out what it did. The confusing code was:


    This is a very tricky and obscure piece of code. Loosely speaking, it takes the two bytes FIRST and SECOND and folds parts of them together into a single byte, RESULT. More precisely, it takes the individual bits from the two bytes and puts them together into a new byte. The bits in SELECT control this process. In general, bit DX of RESULT will be equal to bit DX of FIRST if bit DX of SELECT is equal to 1; if bit DX of SELECT is equal to 0, then bit DX of RESULT will be equal to bit DX of SECOND. For example, if SELECT is 0, RESULT will be the same as SECOND; if SELECT is $FF, RESULT will be the same as FIRST. If SELECT is $F0, then the high nybble (highest four bits) of RESULT will be the high nybble of FIRST, and the low nybble of RESULT will be the low nybble of SECOND. Let's work out an example:

FIRST:  01010111 ($57)
SECOND: 10101101 ($AD)
SELECT: 11110000 ($F0)


LDA FIRST     01010111    ($57)
EOR SECOND    11111010    ($FA)
AND SELECT    11110000    ($F0)
EOR SECOND    01011101    ($5D)
STA RESULT    01011101    ($5D)

The output of this code makes more sense when the bits are grouped suggestively:

FIRST:  0101 0111 ($57)
SECOND: 1010 1101 ($AD)
SELECT: 1111 0000 ($F0)
RESULT: 0101 1101 ($5D)

The pattern should be obvious. The upper four bits come from FIRST, the lower four bits come from SECOND.

Using A Byte Mixmaster
This may all seem rather confusing and pointless to you. Why would anybody want to mix together a bunch of bits? What good is a mixmaster for bytes? As it happens, this code fragment has a number of uses, and makes some very interesting graphics effects possible.
    The simplest application for this code is for nondestructive bit-packing. In most assembly. language programs, each byte represents a single quantity. This makes it easier for us to keep things straight. For example, consider the idea of giving orders to an army in a game like Eastern Front 1941. An army can move in only one of four directions: up, down, right, and left. It therefore takes only two bits to represent a single order. If we store one order in each byte, it will waste six bits. Now, if we are storing only one order, the waste of six bits is not significant. But Eastern Front 1941 allows eight orders per unit and up to 160 units. That amounts to 1280 possible orders. At one byte per order, it would cost 1280 bytes to store all that information, when only 2560 bits, or 320 bytes, are truly needed. Thus, 960 bytes would have been wasted in a 16K program. Tsk, tsk, we can't have that.
    The solution is bit-packing. We pack four independent orders into a single byte. The trick to bit-packing lies in changing some of the bits without disturbing the other bits. That's where our magic code comes in. It can fold a pair of bits into a byte without disturbing the rest of the byte.
    Here's an example: suppose that we have an order (only two bits) in the accumulator. The order is right-justified; that is, the two critical bits are in the lowest order position in the byte. Another way of saying this is that the accumulator contains a number between zero and three. Suppose also that the X register contains the order sequence number; that is, it tells whether this is the first order in the final byte, the second, the third, or the fourth. Thus, the X register contains a number between one and four. Finally, suppose that the bit-packed byte is labelled ORDER. The code to do the trick is:

MASK   DB 3,$C,$30,$C0
       LDY #0
       ASL A
       ASL A
       BNE LOOP
       AND MASK,Y
       EOR ORDER
       STA ORDER

Safe Graphics Animation
You may still wonder what makes this code so useful. After all, seldom do you need to work so hard to save bytes. There are still more uses of this code fragment. One of the most common uses of this code is for graphics. Suppose you have a bit-mapped display and desire to move a number of objects around the screen without disturbing the background. If you had player/missile graphics, you would simply use them directly. However, let us say that for some reason you cannot use player/missile graphics. Perhaps you are stuck with a primitive machine lacking such a facility. Perhaps you need to move so many objects that player/missile graphics are insufficient. In such a case, our magic code fragment is just the ticket for your problem. With it you can go into a bit map and modify only the bits you need to change without disturbing the other bits of the map. This is essential if you are to move objects around on the screen without disturbing the background.
    The basic idea behind this code can be extended to entire chunks of a bit map. Instead of merely mixing together the bits in single bytes, we can mix together the bits in two different bitmaps. Thus, if we have two source bit maps, suggestively labeled FIRST and SECOND, we can write a loop that will perform this fragment of code on every single pair of bytes in the two source bit maps to produce a final bit map that reflects both source maps. The degree to which one or the other source map appears in our final map depends on the value of SELECT. If SELECT is equal to zero, then only the second map will appear. If SELECT is $FF, then only the first map will appear. If SELECT is some other value, then we will see portions of both bit maps mixed together. If we use a random number for SELECT each time we process a byte, we will get a random mix of the two maps. If we then repeat the process of mixing the two many times in one second, the viewer will see a rather intriguing flickering display of the two bit maps enfolded together.
    We can extend the idea even further. If we now use a random number generating routine that allows us to specify the average number of bits that will be set in the random number used for SELECT, we can then control the degree to which we see either the first or the second bit map. For example, if we use random numbers with an average of six bits set, we shall see mostly the first bit map with only a faint image of the second superimposed. If we then create a routine that starts off using an average of zero bits set and then increases the average number of bits set in sequence until finally all eight bits are set, we will see on the screen a dissolve from the second image to the first.
    This technique can be extended further by chaining together enfolding fragments in sequence. Thus, if we enfold FIRST with SECOND to get RESULT, we can then enfold RESULT with THIRD to get a new result. This allows us to mix three images together, an impressive trick that has little utility. It is of some value in improving the overall visual impact of the dissolve algorithm. If the third image is a random bit map, the transition during the dissolve will look a little less mechanical. Unfortunately, it will run more slowly.
    There is a more important conclusion we can draw from this little adventure with five lines of assembly code. The moral of the story is that imagination is often more important in programming than technical prowess. I understood this code fragment at the technical level for a long time, but I did not realize its potential until recently. I wonder how many more programming jewels like this one are out there, waiting to be uncovered by imagination, wit, or, as in my own case, dumb luck?

Fragment For Atari 400/800
110 REM
130 OPEN #1,4,0,"K:"
140 P=PEEK(106)
150 FOR I=0 TO 2
160 POKE 106,P-I*8
170 GRAPHICS 4+16
180 SDLIST(I*2)=PEEk(560):SDLIST(I*2
200 CURR=0:X=0:Y=0:COLOUR=1
210 POKE 560,SDLIST(CURR*2):POKE 561
220 DL=PEEk(560)+256*PEEk(561)+4:POK
    E 88,PEEK(DL):POKE 89,PEEK(DL+1)
230 IF PEEK(53279)=5 THEN CURR=1-CUR
    R:GOTO 210
240 IF PEEK(53279)=3 THEN 310
250 IF PEEK(764)<255 THEN GET #1,A:C
270 NX=X+(S>4 AND S<8)*(X<79)-(S>8 A
    ND S<12)*(X>0)
280 NY=Y+(S=5 OR S=13 OR S=9)*(Y<23)
    -(S=6 OR S=10 OR S=14)*(Y>0)
300 X=NX:Y=NY:GOTO 230
340 POKE 560,SDLIST(4):POKE 561,SDLI
350 FOR I=0 TO 255
370 NEXT I
380 GET #1,A:GOTO 210
390 FOR I=0 TO 40:READ A:POKE 1536+1
400 DATA 104,104,133,204,104,133
410 DATA 203,104,133,206,104,133
420 DATA 205,104,133,208,104,133
430 DATA 207,104,104,133,209,160
440 DATA 0,177,203,81,205,37
450 DATA 209,81,205,145,207,200
460 DATA 192,240,208,241,96

Atari Applications Note

The program above illustrates the binary manipulation discussed in Chris Crawford's article. It lets you draw pictures on one of two screens with a joystick. Press FIRE to lay down points. To switch between the two screens, press SELECT (hold down SELECT for an interesting effect). You can change colors by pressing "0" (to erase) or "1" (to draw). For the purposes of the illustration, you are limited to one color and only half the normal height of GRAPHICS 4.

A Fascinating OPTION
The page flipping and joystick doodling are only a means to an end. The interesting effect happens when you press OPTION. A machine language routine in page six combines screens one and two in various ways, displaying them on a third page which you can see.
    This is not page flipping. The data (points, pixels) on one screen are combined with the data on the other by "enfolding" pairs of bytes as described by Crawford. You can pass the SELECT byte to the machine language routine. Our demonstration uses the numbers 0-255 as SELECT to roughly transform the second screen into the first.
    You could change the FOR/NEXT loop to "255 to 0 STEP-1" to reverse the process. Try changing the last parameter in the USR statement for different effects. You can use random numbers, for example. Trying different numbers may help you to better understand the powerful potential of Crawford's bit enfolding technique.