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.

Fig-Forth At PC=Forty (Part 4)

In part 1, I talked about how to get FIG-Forth for the IBM PC running on PCjs. 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. Then part 2 covered how to implement a very rudimentary disk-based line editor as a precursor to an interactive full-screen editor; while part 3 dives into machine code routines and a PC BIOS interface, because there was no real screen cursor control via the existing commands.

Let's Edit!

Now, at least we can implement a screen editor. One of the constraints I'll impose will be to keep the editor to within 1kB of source code. At first that'll be easy, because all I want to support is normal characters, cursor control, return and escape to update. However, I know that I'll probably want to add the ability to copy text from a marker point using <ctrl-c>. But even a simple decision like this raises possible issues. Consider this, if I type VLIST I find I can press <ctrl-c> to stop the listing:

However, if I type this definition:

: T1 BEGIN KEY DUP . 27 = UNTIL ;

I find that <ctrl-c> doesn't break out of T1, instead it simply displays 3 and I really do have to press <esc> to quit the routine. But it could be that Forth still checks it automatically, just not with the above sequence of commands in T1. No, from the FIG-Forth source we can see, the breakout of VLIST is simply due to it executing ?TERMINAL and exiting if any key has been pressed. So, that potential problem is sorted!

VLIST Source Code:

DB 85H DB 'VLIS' DB 'T'+80H DW UDOT-5 VLIST DW DOCOL DW LIT,80H DW OUTT DW STORE DW CONT DW AT DW AT VLIS1 DW OUTT ;BEGIN

DW AT DW CSLL DW GREAT DW ZBRAN ;IF DW OFFSET VLIS2-$ DW CR DW ZERO DW OUTT DW STORE ;ENDIF VLIS2 DW DUPE DW IDDOT DW SPACE DW SPACE

DW PFA DW LFA DW AT DW DUPE DW ZEQU DW QTERM DW ORR DW ZBRAN ;UNTIL DW OFFSET VLIS1-$ DW DROP DW SEMIS

The Editor Itself

The first goal in the editor is to convert y x coordinates in the current screen to a memory location in a buffer. This is a minor change from the initial part of the code in EDL:

: EDYX& ( Y X -- ADDR)

  >R 15 AND 8 /MOD SCR @ B/SCR * +

  BLOCK SWAP C/L * + R> +

;

We want to be able to constrain Y and X coordinates to within the bounds of the screen (in this case with wrap around):

: 1- 1 - ; ( oddly enough missing from FIG-Forth, but I use it quite a bit in the editor)

: EDLIM ( Y X -- Y' X')

  DUP 0< IF

    DROP 1- 0

  THEN

  DUP C/L 1- > IF

    DROP 1+ 0

  THEN

  SWAP 15 AND SWAP

  OVER 2+ OVER 4 + AT

;

The key part of a screen editor is to be able to process characters, I've picked the vi cursor keys:

: DOKEY ( R C K  )

  >R

  R 8 = IF ( CTRL-H, Left)

    1-

  THEN

  R 12 = IF ( CTRL-L, Right)

    1+

  THEN

  SWAP R 11 = IF ( CTRL-K, Up )

    1-

  THEN

  R 10 = IF ( CTRL-J, Down)

   1+

  THEN

  SWAP R 13 = IF ( CR or CTRL-M)

    64 +

  THEN

  EDLIM

  R 31 > R 128 < AND IF ( PRINTABLE)

    2DUP EDYX& R SWAP C!

    R EMIT 1+ UPDATE EDLIM

  THEN

  R>

;

Finally we want to put it all together in a top-level function:

: ED ( scr -- )

  CLS LIST 0 0 EDLIM

  BEGIN

   KEY DOKEY

  27 = UNTIL

  DROP DROP

;

Interestingly, once I'd cleared up an initial bug where the cursor wasn't advanced when I typed a character, and another where I'd missed an AND when checking for printable characters, I was able to use the editor itself to edit improvements ( namely, putting the initial cursor at the right location instead of (0,0)).

Finally, although Forth isn't always as compact as its proponents like me often claim, in fact this editor in itself uses a mere 306 bytes, probably the most compact interactive editor I've seen and there's still over half the screen left for improvements. For example, there's no support for delete ( left, space, left); for inserting a line; copying text, nor blocks. But for the moment, it's easily far more enjoyable than the line editor it replaces.

Exercise For The Reader

The biggest user-interface problem I've found with extensions to the editor has been to decide which control character to use to mark the text location for copying. To explain: many archaic screen editors, including some early word processors used a mark, edit sequence for text manipulation. The user would move the cursor to where they wanted to perform an 'advanced' edit operation; mark the initial location; then move the cursor to either where they wanted the edit operation to finish; mark the end of that edit text; then finally, possibly move the cursor to some other location and complete the edit. For example, on the Quill word processor for the Sinclair QL, you'd Type F3, 'E' (for Erase), move the cursor to where you wanted to erase a block; press enter; move to where the erase should finish (and it would highlight the text as you went along); press enter; confirm you wanted to erase it and then it would. Or in the Turbo C editor you'd Mark an initial starting location; then Mark again an ending location and then perform an operation like 'Copy' to duplicate the text, or 'Delete' or 'Move' to move the text.

Or on a BBC Micro, the BASIC editor was essentially a line editor which supported two cursor positions (!!) If you needed to manipulate a line instead of just retyping it, you'd list the line (if it wasn't on the screen), then move the cursor keys and a second cursor would appear, moving to where you wanted on the screen; while the cursor at your editing position would remain. You'd then hit COPY and it would copy from the second cursor to your editing position, advancing both cursors.

So, in my system, which is similar to how editing works on FIGnition, I'd want to Mark the position where I wanted to copy / erase from; move to where I wanted to paste or finish a delete to and then COPY / MOVE a character at a time from the source to the destination (or Erase the text).

However, the most obvious control character to use, <ctrl-m> is already used for Return, and everything else seems rather contrived. Then I thought, what happens if I use <ctrl-symbol> instead? Do they produce interesting control codes? I found out quite a number produce 0s, but some actually generate the control codes in the range 0..31 that you can't generate from <ctrl-a> to <ctrl-z>.

This is what I found out:

Ctrl+	Code	Ctrl+	Code
\	28	]	29
6	30	-	31

So, what I'd like to know is whether this is just an artefact of the simulator being used on a Mac or whether it's common to other emulators and an actual IBM PC?

Conclusion

Once I'd implemented some earlier, critical definitions it turned out to be quite easy and satisfying to write a full-screen editor. The biggest challenges were in making sure certain key presses wouldn't collide with any system behaviour and finally thinking about some user-interface decisions for some future enhancements.

The editor also nicely illustrates some key Forth aspirations: the editor turns out to be very compact (though of course it's very rudimentary too); and I was able to use it to debug and improve itself once I'd reached some critical level of functionality. It was so easy and tiny, I wonder why it wasn't a standard part of FIG-FORTH, given that it was designed in an era when cursor addressable VDUs were already the norm.

Raspberry Pi Plum Pulling

I'm disappointed that Eben Upton, Technical Director of Broadcom, that make the patent-protected, closed-source BCM2835 chipset inside the Raspberry PI has chosen to use his product to promote free-trade ideology in developing countries.

"..A less positive experience has been the impact of state-monopoly postal services and punitive tariffs - often as high as 100% - on availability in markets such as Brazil.
There, a $35 (£23) Pi will currently cost you the best part of $100 (£66).
I believe that these measures, aimed at fostering local manufacturing, risk holding back the emergence of a modern knowledge economy in these countries."

 I've just been reading 23 things they don't tell you about Capitalism, by Ha-Joon Chang (a Korean economist based in Cambridge, like Eben... perhaps they should meet up in a pub sometime?). One of his key points is how rich countries got rich by creating tariffs, which they then expect poorer countries to forgo under the pretense that it'll improve poor economies.

The problem is that it's one rule for us, and another rule for them. Broadcom, the BCM2835 and to an extent, the Raspberry PI is a product of this; it creates low-barriers to entry for wealthier entities like Broadcom and high-barriers to entry for less wealthy entities, like Brazil or ... me.

For example, the Raspberry PI (which I believe is a great idea) is roughly the same price as a FIGnition, in effect, about £25 compared with £20 for my product. Yet Raspberry PI is about 10,000 times more powerful (and complex) than FIGnition. That's because firstly, the Raspberry PI (Model B) is built in China (which reduces costs). 

Secondly, it's massively mass-produced (which reduces costs).

Thirdly, they have the sophisticated tools to both design the chipset and the PCBs - a hobbyist can't build one at all even if given the components, a perfectly steady hand and a microscope (an infinite barrier for a hobbyist).

Fourthly, they have access to all the design documents - Broadcom don't even publish them for the general public (another infinite barrier for hobbyists).

Fifthly, they have volume access to suppliers, at a much reduced (secret) cost, which the general public (like me) don't have access to.

So you can see, there are barriers I face that others don't. But this is OK for me - I wouldn't produce a Raspberry PI instead of a FIGnition anyway, because I want people to build computers that can be understood - and that means building rudimentary computers that can be reproduced by the general public. That's because I believe that in the same way we teach kids to read using phonics rather than War And Peace and we don't believe that books have superseded the alphabet; if we want kids to master technology, they really need to start at the basics.

Similar barriers though apply to developing countries. There are inbuilt barriers to them, starting with for example, the fact that the brightest people in developing countries end up in places like Cambridge. Developing countries therefore often want to protect their own markets, for example, Ghana likes to grow and eat their own chickens, but instead Europe dumps our excess chickens on them, so they can't develop their own market.

It's unfair. But it's doubly unfair for a protectionist company Broadcom that makes use of cheap Chinese labour to force open markets in developing countries for their own benefit. Surely, surely, if Broadcom really did want Brazil to have lots of cheap Raspberry PIs, they'd simply give the information to Brazil to procure their own production runs - ship the raw chips to factories in Brazil and let them make their own PIs. There would still be the chip trade barrier, but not the for the added value of board production and assembly.

Problem solved - and the PI would be used for its intended purpose, not for sticking in thumbs and pulling out plums. Please Eben, you're a nice guy (as I recall from the BBC@30 event); don't use the PI as a free-market political tool :-)