I need to compare it to the Bresenham algorithm. Although recursion is pretty cheap in Forth it ain't free.
Take a look at my fbForth 2.0 primitive for LINE in bitmap graphics mode, which uses an integer, no-divide version of the Bresenham line algorithm:
;[*** LINE *** ( x1 y1 x2 y2 --- ) ( alternative LINE---one or the other) *++ This is an integer, no-divide version of the Bresenham line algorithm * LINE does the following: * 1) Computes dy = y2-y1 and dx = x2-x1 * 2) Determines which direction, x or y, has slope <= 1 * x) Flips dx and dy * y) Leaves dx and dy alone * 3) sets DOTCNT = dx in R4 * 4) Computes D = 2*dy-dx * 5) Forces plotting direction to be positive for independent variable * 6) Sets starting y|x accumulator as acc = (y|x) * 7) Finds accumulator increment as inc = +1|-1 * 8) Plots first dot * 9) Each time through dot plotting loop: * a) Loop counter check * b) x|y = x|y + 1 * c) D > 0? * yes) * y1) acc = acc + inc * y2) D = D+2*(dy-dx) * no) D = D+2*dy * d) y|x = acc * e) Plot dot * f) Decrement point counter * DATA DTBM_N * LINE_N DATA 4+TERMBT*LSHFT8+'L','IN','E '+TERMBT * LINE DATA $+2 * BL @BLF2A * DATA _LINE->6000+BANK1 * Register usage--- * R0: varies * R1: varies * R2: y2 * R3: x2 * R4: y1, then, point (dot) count for line (DOTCNT) * R5: x1, then, increment for dependent coordinate (INC) (+1|-1) * R6: accumulator for dependent coordinate (ACC) * R7: current independent coordinate (COORD) * R8: dx, then, 2*dx * R9: dy, then, 2*dy * R10: sign of dy/dx or dx/dy, then, D * R12: contains flag for principal axis (1 = x axis, 0 = y axis) _LINE LIMI 0 ; disable interrupts because __DTBM doesn't STPTR EQU MAINWS+18 ; stack pointer (fbForth's R9) LWPI FAC ; let's use our ws MOV @STPTR,R0 ; get stack pointer to R0 MOV *R0+,R2 ; pop coordinates (won't actually change Forth SP) MOV *R0+,R3 MOV *R0+,R4 MOV *R0+,R5 SETO R10 ; initially, store -1 as sign of slope MOV R2,R0 ; calculate dy S R4,R0 MOV R0,R1 ; prepare for sign calculation ABS R0 MOV R0,R9 MOV R3,R0 ; calculate dx S R5,R0 XOR R0,R1 ; calculate sign of slope (dy/dx|dx/dy) JLT LINE01 ; negative slope? NEG R10 ; change sign to +1 LINE01 ABS R0 MOV R0,R8 MOV R9,R1 C R1,R0 ; compare|dy| to |dx| JLT LINE04 ; dy < dx? MOV R0,R9 ; no, flip dy MOV R1,R8 ; and dx MOV R4,R7 ; assume starting with y1 MOV R5,R6 ; and x1 (to ACC) C R4,R2 ; should we switch? JGT LINE02 ; yes JMP LINE03 ; no LINE02 MOV R2,R7 ; we're starting with y2 MOV R3,R6 ; and x2 (to ACC) LINE03 CLR CRU ; 0 to CRU (R12) to indicate y-axis processing JMP LINE07 LINE04 MOV R5,R7 ; assume starting with x1 MOV R4,R6 ; and y1 (to ACC) C R5,R3 ; should we switch? JGT LINE05 ; yes JMP LINE06 ; no LINE05 MOV R3,R7 ; we're starting with x2 MOV R2,R6 ; and y2 (to ACC) LINE06 LI CRU,1 ; 1 to CRU (R12) to indicate x-axis processing LINE07 MOV R10,R5 ; get sign to INC register before we destroy it! SLA R9,1 ; dy = 2*dy (we don't need dy by itself any more) MOV R9,R0 ; calculate D S R8,R0 ; D = 2*dy-dx MOV R0,R10 ; store D in DYXSN MOV R8,R4 ; load point counter SLA R8,1 ; 2*dx (we don't need dx by itself any more) MOV CRU,CRU ; x or y axis? JNE LINE08 ; x-axis MOV R7,R0 ; y-axis, COORD to y for DOT MOV R6,R1 ; ACC to x for DOT JMP LNLOOP ; to first plot LINE08 MOV R7,R1 ; x-axis, COORD to x for DOT MOV R6,R0 ; ACC to y for DOT LNLOOP BL @__DTBM ; plot first dot (R0 = y, R1 = x) MOV R4,R4 ; are we done? JEQ LINEX ; yup! DEC R4 ; decrement counter INC R7 ; increment principal coordinate *++ Calculate D MOV R9,R1 ; get 2*dy MOV R10,R0 ; D > 0? JGT LINE09 ; yup JMP LINE10 ; nope LINE09 A R5,R6 ; inc/dec dependent variable S R8,R1 ; 2*dy-2*dx LINE10 A R1,R10 ; D = D+[2*dy or 2*dy-2*dx)] MOV CRU,CRU ; x-axis or y-axis? JEQ LNYAX ; y-axis MOV R7,R1 ; x-axis, get next x for DOT MOV R6,R0 ; get accumulator contents to y for DOT JMP LNLOOP ; go to plot LNYAX MOV R7,R0 ; y-axis, get next y for DOT MOV R6,R1 ; get accumulator contents to x for DOT JMP LNLOOP ; plot the dot (R0 = y, R1 = x) & on to next point LINEX LWPI MAINWS ; RESTORE MAIN WS AI SP,8 ; REDUCE STACK BY 4 CELLS B @RTNEXT ; back to bank 0 and the inner interpreter ;]
As I recall, I had a fair amount of help from Tursi on this. There is a fair discussion somewhere in the fbForth thread (see below in my signature) at the time I was converting all of the graphics primitives from TI Forth to ALC for fbForth 2.0 before I first released the cartridge a few years ago. You should have all of the source code. The graphics primitives are in Bank 1 file, fbForth104_GraphicsPrimitives.a99.