Fig-Forth At PC=Forty (Part 5)

FIG-Forth was a popular and very compact, public-domain version of the medium speed Forth systems programming language and environment during the early 1980s. In part 1, I talked about how to get FIG-Forth for the IBM PC running on PCjs and in part 2 I implemented a very rudimentary interim disk-based line editor. Part 3 dives into machine code routines and a PC BIOS interface, so that I could implement the screen functions I needed for my full-screen editor and in Part 4 I used them to implement that full-screen editor.

Here I'd like to explore a bit more graphics, since the PC BIOS interface can plot pixels (in any of 4 colours).

So, let's start with Plot. I get most of my BIOS programming information from wikipedia, though I've used an independent web page too. Implementing plot is just an INT10H function (where AH=24), so let's try it:

: PLOT ( CLR X Y )
  >R >R 3072 + 0 R> R>
  INT10H
;

4 VMODE takes us into 320x 200 graphics. You can still type in text, but you can't see the cursor. CLS fills the screen with a stripe - the bios call doesn't work the same way. We can create a graphics cls with:

: CLG 1536 SWAP 21760 * 0 6183 INT10H 0 0 AT ;

We can fill the screen with a colour:

: FCOL 200 0 DO I 320 0 DO OVER OVER I SWAP PLOT LOOP DROP LOOP DROP ;

So, 0 CLS 1 FCOL will then fill the screen in cyan in 37.6s. This makes the plot rate 37.6/(320*200=64000) = 1702 pixels per second, or if we exclude the non-plot functions (43µs+32µs*4)*320*200 = 10.9s for the FORTH code itself, so 26.456s or 2419 pixels per second. Writing a simple random number generator:

0 VARIABLE SEED

: RND SEED @ 1+ 75 * DUP SEED ! U* SWAP DROP ;

Means we can fill the screen with random pixels with:

: RNDPIX 200 0 DO I 320 0 DO 4 RND OVER I SWAP PLOT LOOP DROP LOOP ;

Is what we get part of the way running this after CLS. It randomly plots successive pixels with the colours black, cyan, magenta or grey.

Lines

More usefully we can draw lines. The Jupiter Ace manual gives a nice routine for drawing lines (page 79), however it uses the definition PICK which isn't available on FIG-Forth. It will also turn out that the Bresenham routine, which although it's faster in pure assembler, is slower when the instruction execution rate is much slower than division or multiplication. And that's true for the 8088 where each Forth instruction is about 30µs, but a multiplication also takes about 60µs. Thus, if the Bresenham algorithm is at least 2 instructions longer, multiplies (or divides) are faster. And the Bresenham algorithm on the Jupiter Ace takes: 14 basic loop instructions + DIAG (some of the time) = 4 instructions + SQUARE the rest of the time = 8 or 7 instructions. And Step = 12 instructions. So, that's about 14+6+12 = 32 instructions per loop. By comparison, the main loop in FIGnition is 22 instructions. On this basis we'd be able to achieve about 1500 points per second, a diagonal line across the screen would take about 0.2 seconds.

It's possible to consider the fastest potential line drawing code and base the full line drawing algorithm around that. The quickest way is to consider that again, for the longest axis, its coordinate will increment by 1 on each pass and on the other axis, some fraction of 1. So we can consider a 16-bit fraction, in the range 0..1 on that axis, which we can multiply by the longer axis. In each case we need to add an offset for each coordinate to get the final location.

: DAxis ( col grad offsetg offseth limh )

  0 DO ( col grad offg offh)

    OVER >R >R >R 2DUP ( c g c g : f h f)

    I U* SWAP DROP R> + ( c g c g*i+f : h f)

    R I + PLOT R> R> SWAP

  LOOP
;

So, in this version we need about 20 instructions and we need a second version where the x coordinates map to the do loop. The problem with this version is handling negative gradients, because using U* to generate gradients won't generate negative results in the high word. However, this can be fixed by sorting the coordinates. Consider (with a normal x-y coordinate system) a vector in the second quadrant at about 153º (a gradient of about -1/2). If we sort the coordinates so that we draw from right to left, then the y coordinates will draw upwards. Similarly a line in the 4th quadrant drawn at 288º (a gradient of 2/3), if we sort the coordinates so that we draw from top to bottom, then the x coordinates are ordered left to right. And we can achieve this by XOR'ing the DO loop coordinate by 0xffff (and adding 1 to the DO LOOP coordinate offset). Furthermore we can 'improve' the line drawing by modifying the plot routine to add an origin ( ox, oy) and set the colour ( fgCol). This gives us:

0 VARIABLE oxy 0 ,

: Oplot ( col dx dy )
  >R >R 3072 + 0 oxy 2@ R> + SWAP R> +
  INT10H
;

So, OPLOT is 4 words longer than PLOT. Also we want x in the first word of oxy and y in the second word. Then DAxis is:

0 VARIABLE XDIR

: DAXISY ( col grad limh sgn&dx sgn&dy)

  OXY >R R 2+ +! R> +!

  0 DO ( col grad)

    2DUP ( c g c g)

    I U* SWAP DROP ( c g c g*i)

    XDIR @ I XOR OPLOT ( c g )

  LOOP DROP DROP
;

: SGN 0< MINUS ;

( Here Y is the major axis. There are 4 cases,

  maj>0, min>0 = first quadrant, normal.

  maj >0, min <0 = second quadrant [ \ ]. Set ox+=dx.

               Since the gradient is always unsigned,

               a left to right draw will cover the correct x direction.

               However, y will draw from bottom to top, giving [ / ]

               So, y needs to be drawn from top to bottom too,

               XDIR=-1, oy+=dy.

  maj <0, min <0. = third quadrant, set ox+=dx and oy+=dy. That's because

                dy<0, dx<0 is / kind of line so simply moving oxy fixes

                the problem.

  maj <0, min >0 = fourth quadrant.

               XDIR=-1.

  So, if dy^dx <0, then XDIR=-1 else 0.

)

: QUADFIX ( c min maj )

  2DUP >R >R ( c min maj : min maj)

  ABS SWAP ABS SWAP ( c |min| |maj| : min maj )

  >R 0 SWAP R U/ SWAP DROP R> ( c  g |maj| : min maj)

  R> R> 2DUP XOR SGN XDIR ! ( c g |maj| min maj sgn(min^maj)!XDIR [Quadrants 2 and 4])

  OVER SGN SWAP OVER AND >R ( c g |maj| min sgn.min : maj&sgn.min)

  AND R> ( c g |maj| min&sgn.min maj&sgn.min)

;

: DAXISX ( col grad limh sgn&dy sgn&dx)

  OXY >R R +! R> 2+ +!

  0 DO ( col grad)

    2DUP ( c g c g)

    I U* SWAP DROP ( c g c g*i)

    XDIR @ I XOR SWAP OPLOT ( c g )

  LOOP DROP DROP
;

So, this is 13 words + 4 for OPLOT, Saving 3 words. Now drawing the longest line ought to take about (43µs+4*32µs+32µs*16)*320 = 0.22s. In practice, timed basic plotting rate is 27.8s=32000 pixels, or 0.278s for the 320 pixels so that's a maximum of 1151 pixels per second, which is slowish, but tolerable.

: DRAW ( col dx dy)

  2DUP OR 0= IF

    DROP DROP DROP

  ELSE

  OVER OXY SWAP OVER @ + >R ( col dx dy &OXY : X')

  2+ @ OVER + >R ( col dx dy : Y' X')

  OVER ABS OVER ABS > IF

    SWAP QUADFIX DAXISX

  ELSE

    QUADFIX DAXISY

  THEN

THEN

  R> R> OXY 2!

;

: RLINE

  3 RND 1+ ( COLOR)

  200 RND 320 RND 2DUP OXY 2!

  320 RND SWAP - SWAP 200 RND SWAP - DRAW

;

: RLINES BEGIN RLINE ?TERMINAL UNTIL ;

Circles

Our circle algorithm, on the other hand will be copied straight from the equivalent FIGnition version.

Method: we know x^2+y^2 = const. So, we start at [0,r], which gives r^2 We can go straight up, which gives:

   [x^2+[y+1]^2] - x^2-y^2 => a difference of +2y+1.

Or we can do [x-1]^2 => a diff of 1-2x.

So, the rule is that when the accumulation of 2y+1>1-2x, then we do 1-2x. By only calculating the error, we don't need to calculate r*r and therefore there is no danger of 16-bit arithmetic overflow even for radius's larger than the width of the highest screen resolution.

: NEXTP ( X Y DIFF )

 OVER DUP + 1+ + >R  ( CALC WITH INC Y )

 OVER DUP + 1 - R> 2DUP > IF

   SWAP DROP

 ELSE

   SWAP - >R SWAP 1 - SWAP R>

 THEN SWAP 1+ SWAP

;

0 VARIABLE FG

: DXYPLOT ( COL DX DY)

  >R 2DUP R OPLOT R> ;

: OCTPLOT ( CX CY DX DY)

  4 0 DO

    DXYPLOT SWAP

    DXYPLOT NEG

  LOOP

; ( -- CX CY )

: CIRC ( COL X Y R )

  >R SWAP OXY 2! ( COL : R)

  R> 0 0 >R ( COL DX=R, DY=0 : DIFF=0)

  BEGIN

   OCTPLOT R> NEXTP >R

  2DUP < UNTIL R>

  DROP DROP DROP

;

: CIRCS ( CIRCLES)

  0 DO 3 RND 1+ 160 100 I CIRC 2 +LOOP DROP DROP ;

: CIRCBM 0 DO I 3 AND 160 100 98 CIRC LOOP ;

And with a ticks routine of the form: HEX : TICKS 40 6C L@ ; DECIMAL we can time it fairly well. 20 CIRCBM draws 98*2*pi pixels per circle and takes 174 ticks. So that's 12315 pixels in 9.56s or 1288 pixels per second. Amazingly, a bit faster than line drawing!

Conclusion

Once we can choose a graphics mode and implement a plot function we can build on that with simple line-drawing and circle-drawing algorithms. An original IBM PC running FIG-Forth draws lines like a lazy 8-bit computer, but for graphics of moderate complexity, that's tolerable. The real challenge is that a classic line drawing algorithm involves quite a lot of stack variables with extensive stack shuffling, making an efficient program far more involved than the equivalent even in 8-bit assembler and that the overhead of the Forth interpreter means the Bresenham line drawing algorithm is slower than one that uses division.