The Circle Game

Of all the problems with machine code programming, there is one that really stands out: it is too simple!

Oh, sometimes it can be pretty hard to figure out how to make your program do what you want. But that is because the Z80 microprocessor—the “brain” inside your ZX/TS computer—is really rather simple-minded. It can add and subtract well enough —and even multiply and divide by two—as long as the numbers are between 0 and 65,535.

But for anything more complicated, the Z80 just cannot handle it alone. You—the programmer—have to do most of the work. You are the one who has to write a routine that will multiply or divide, or print something on the screen. If you want the Z80 to do something really fancy like square roots or trigonometric functions or floating-point math, you have to figure out some way to simplify it all down to very simpleminded jobs like adding and subtracting.

Either that, or you have to get someone else to do it for you.

In this and the next installment of this series of articles on Z80 machine code, we will try it both ways as we tackle a relatively complicated challenge: getting the ZX81 or TS1000 to draw a circle on the screen. This time we will do it the hard way, translating a circle drawing routine into machine code ourselves. Next time, we will let someone else do most of the work—using a special section of the Basic ROM called the “calculator.”

Why do it yourself if you can use ROM routines to do it more easily? Because the ROM “calculator” is only about twice as fast as Basic would be. “Pure” machine code is much faster than that. There is another reason, too: sometimes you may want to do something that the “calculator” in ROM just cannot handle. With regular machine code, you can do almost anything — if you can only figure out how…

Round and Round

Figure 1 shows one of the most common ways of drawing a circle using Basic. Type in the program and RUN it. You will see it slowly draw a circle, PLOTting one point at a time, on your screen.

10 LET R=20
20 LET S=32
30 LET T=22
40 FOR N=0 TO 2*PI STEP PI/60
50 LET X=R*COS N
60 LET Y=R*SIN N
70 PLOT X+S,Y+T
80 NEXT N

This circle drawing routine is pretty simple. It is based on a couple facts from trigonometry that show up in lines 50 and 60:

X=R*COS N
Y=R*SIN N

Or, as your trigonometry teacher might put it, “For any angle, the x-coordinate of a point on the circle equals the radius times the cosine of the angle, and the y-coordinate equals the radius times the sine of the angle.” If you have never had a trigonometry teacher, do not panic. SIN and COS are too complicated to explain here in detail, but, even if you do not understand exactly how they work, the program will run anyway.

In this routine, the radius of the circle is variable R. The LET command in line 10 sets it to 20. The center is at point (S,T); lines 20 and 30 make that (32,22), the center of the screen. You can change lines 10, 20, and 30 to make larger or smaller circles, with centers in different places on the screen. Watch out, though; if your routine tries to plot a point that is off the screen, you will get an error, and the program will stop.

There are really only two problems with this routine: SIN and COS. If the sine and cosine functions are complicated to explain, they are even more complicated for the computer to work out. The routine draws a circle so slowly because it spends most of its time figuring the sines and cosines.

Fortunately, we are not stuck with using these functions for drawing a circle. There are other ways to do it. Probably the easiest is the one worked out by Marvin Minsky, a computer scientist at the Massachusetts Institute of Technology. (You may have heard of Minsky; he is most famous for his work on an “artificial intelligence” computer language called LISP.)

A few years back, Minsky was looking for a better way to draw a circle with a computer—a way that would be simpler for the computer to do. He came up with a routine that, in Basic, looks something like Figure 2.

10 LET R=20
20 LET S=32
30 LET T=22
40 LET X=R
50 LET Y=0
60 FOR N=1 TO 202
70 LET X=X-Y/32
80 LET Y=Y+X/32
90 PLOT X+S,Y+T
100 NEXT N

It certainly seems like a much simpler routine, that’s for sure. There is no more SIN or COS-just adding and subtracting. multiplying and dividing. Since simpler means faster on a computer, it can draw a circle in much less time than the SIN and COS version. Type it in and run it, and you will see just how much faster it is.

You may wonder how it can do the work of SIN and COS when it is so simple. Actually, it just looks simple. The ideas behind it are quite complex-even more complicated than the ones behind using the sine and cosine functions. But this is not a course in college-level math; if it were, this issue of SYNC would be 500 pages long. Just remember that, like SIN and COS, it does work-even if you do not understand exactly how.

A Circle in Any Language

Translating this circle program into Z80 machine code really is not too difficult. It is long, that is true – but, if you translate the Basic program one line at a time, it is not hard. The translation is in Figure 3.

10 LET R=20              (you can load these
20 LET S=32              three variables with
30 LET T=32              their values before
                         the routine begins)
40 LET X=R               LD A,(R)
                         LD H,A
                         LD L,0
                         LD (X),HL
50 LET Y=0               LD H,0
                         LD (Y),HL
60 FOR N=1 TO 202        LD A,1
                         LD (N),A
70 LET X=X-Y/32          LD HL,(X)
                         LD DE,(Y)
                         LD B,5
                   DIV1: SRA D
                         RR E
                         DJNZ DIV1
                         OR A
                         SBC HL,DE
                         LD (X),HL
80 LET Y=Y+X/32          LD DE,(Y)
                         LD B,5
                   DIV2: SRA H
                         RR L
                         DJNZ DIV2
                         ADD HL,DE
                         LD (Y),HL
90 PLOT X+S,Y+T          LD DE,(X)
                         LD A,(S)
                         RL E
                         ADC A,D
                         LD C,A
                         LD A,(T)
                         RL L
                         ADC A,H
                         LD B,A
                         CALL PLOT
100 NEXT N               LD A,(N)
                         INC A
                         LD (N),A
                         CP 202
                         JR C,line 70

Let’s look at how some of the lines are translated; they are not all exactly what you might expect. Line 70, e.g., seems to be a pretty complicated piece of translation:

70 LET X=X-Y/32 

Subtracting is easy, but how do we divide by 32? We already know how to divide a number by 2. We can use the Z80 is “shift” and “rotate” instructions. A shift instruction, by itself, will divide the number in a register by 2. Using shift and rotate instructions together, we can do the same thing to the number in a register pair, such as DE or HL. For example, the instructions

SRA D 
RR E 

divide the number in register pair DE by 2.

Now try this: divide a number by 2, then divide the result by 2 again. The answer you get is the same as if you had divided the original number by 4. (Re- member, 4 = 2 * 2) If you divide that answer by 2 again, it is as if you had divided the original number by 8(2 * 2* 2).

What we want to do is divide by 32 (2 * 2 * 2 * 2 * 2). To do this, we put the shift and rotate instructions that will divide by 2 in the middle of a loop, like this:

      LD B,5 
DIV1: SRA D 
      RR E 
      DJNZ DIV1 

Do not be thrown off by the DJNZ instruction. It is a special instruction that only works with register B; it is exactly the two instructions

DEC B 
JR NZ,DIV1 

Every time the Z80 gets to the DJNZ instruction, it will subtract one from the number in register B. If the result is greater than zero, the program will jump; if it is zero, it just continues with the next instruction.

In other words, since register B starts out with the number 5 we will run through this loop 5 times. Each time the number in register pair DE will be divided by 2, and the number in register B will drop by 1, until finally B contains zero-and the program continues. In Basic, it might look something like this:

10 LET B=5 
20 LET DE=DE/2 
30 LET B=B-1 
40 IF B>0 THEN GOTO 20 

As you have probably noticed, the DJNZ instruction works a lot like the NEXT command in Basic. Here is another Basic version of the routine:

10 FOR B=5 TO 1 STEP-1 
20 LET DE=DE/2 
30 NEXT B 

If you add a couple more lines such as

5 INPUT DE 
50 PRINT DE

to either of these short programs, you can try running them in Basic. You will find that, as expected, each of them divides by 32.

The Fixer

There is something else that is a bit unusual in this translation. Though the variables R, S, and T are ordinary numbers, X and Y use a very special kind of arithmetic called fixed point arithmetic.

Here is why: when the plotting section of this routine starts its work, X equals 20 and Y equals 0. The first thing we do is divide Y by 32 and subtract the result from X:

X=X-Y/32 
X=20-0/32 
X=20 

So far, so good. Next we will divide X by 32 and add the result to Y:

Y=Y+X/32 
Y=0+20/32 

Here is where the problem shows up. The Z80 microprocessor only uses integers, i.e., whole numbers. There are not any fractions in this kind of arithmetic. When you divide a number, the result is always rounded off to the next whole number down. It is as if you have used the INT function in Basic.

This means that, for the Z80, 20/32 equals zero. And this means, after all that work, X still equals 20, and Y still equals 0. No matter how many times we run these numbers through the loop, they will never change. That is not going to draw much of a circle.

How can we solve this problem? We will cheat. We can trick the computer into keeping at least part of a fraction by putting each of these two variables into the top half of a register pair. In the translation of our Basic program, we do that in lines 40 and 50.

Now remember: putting a number in the top half of a register pair is like multiplying it by 256. So to the computer, X is not 20 any more; it is 20 times 256, or 5120. (Y, of course, is still zero since 0 times 256 is still O.)

When we run these two numbers through our routine now, the fractions do not completely disappear. They are still there in the lower half of each register pair:

X=X-Y/32 
X=5120-0/32 
X=5120 
Y=Y+X/32 
Y=0+5120/32 
Y=160

This time, we do not end up with exactly what we started with. The second time through, the numbers change even more

X=X-Y/32 
X=5120-160/32 
X=5115 
Y=160+5115/32 
Y=Y+X/32 
Y=319

To PLOT these points, of course, we have to use the actual values of X and Y. To find them, we must divide by 256, but that is easy to do. We just use the value that is in the top half of each register pair.

In Basic, what we are doing would look something like this: