Simtel MSDOS 1992 June/SIMTEL_0692.cdr/msdos/ddjmag/ddj8609.arc/LETTERS.SEP

Text File | 1986-09-30 | 10.5 KB | 458 lines

Listing One

Program Squareroot;
{
  Squareroot algorithm & testprogram; DDJ March 1986, p.122

  Features:  - sqrt routine in 68000 machine language;
         - long integer loopcount;
}

const    { Iteration count for test loop }
    NNR = 6E4;    { real, for printing of statistics }
    NNS = '60000';    { string, for assignment to long integer }

type    long = record
          low,high : integer;
        end;

var    finished    : boolean;    { flag for loop }
    number, limit   : long;        { loop count, loop limit }
    sqrrt,                { square root result }
    sqrrto,                { last displayed square root }
    t1,t2        : integer;    { parameters for system time }
    time1, time2    : real;     { start, end time }

{ --- ROUTINES FOR LONG (32-BIT) INTEGER SUPPORT --- }

procedure lg_clr(var l:long);   external;
{ Clears long integer l }

procedure lg_asn_DU(s:string; var l:long);   external;
{ Assigns the unsigned decimal string s to the long integer l }

procedure lg_inc1(var l:long);   external;
{ Increments long integer l by 1 }

procedure lg_grt(a,b:long; var flag:boolean);   external;
{ Compares long integers a and b and assign result to flag }

{ --- SQUAREROOT ROUTINE --- }

procedure sqrt(number:long; var result:integer);  external;
{ Calculates square root of 'number' and returns it in 'result' }

begin { main }

  sqrrto := 100;

  lg_clr(number);    { number := 0 }
  lg_asn_DU(NNS,limit); {limit := NNS }
  finished := false;

  write('Start...');
  time(t1,t2);  time1 := t2;  { get start time }

  while not finished do { calculate sqrt(number) }
    begin
      sqrt(number,sqrrt);
    {
      if sqrrt <> sqrrto
     then begin
       write ('Number = ',number.high:6,' | ',number.low:6);
       writeln('  ---  Sqrt = ',sqrrt:4);
       sqrrto := sqrrt;
     end;
    }
      lg_inc1(number);            { number := number + 1 }
      lg_grt(number,limit,finished);    { finished := (number > limit) }
    end;

    time(t1,t2);   time2 := t2;  { get end time }

    writeln('finished !'); writeln;
    writeln('Time: ',(time2-time1)/60,' seconds');

end.

Listing Two

1 *
2 * Squareroot algorithm;  DDJ March 1986, p.122
3 *
4 * 68000 assembly language version
5 *
6 * Features: - equivalent to compiler-generated code;
7 *
8 *
9 * procedure sqrt(number:long; var result:integer);
10 *
11 * Calculates integer square root of 'number' and returns it in 'result';
12 *
13 *
14 * Register usage:
15 * --------------
16 *
17 * D0 : word register        A0 : parameter stack pointer
18 * D1 : number                A1 : scratch register
19 * D2 : guess1
20 * D3 : guess2
21 * D4 : error
22 *
23     proc    sqrt,2        ;2 words of parameters
24 *
25 * Get parameters from stack
26 *
27    move.l     (sp)+,a0    ;get return address
28    move.w    2(sp),a1    ;get ^number
29    move.l    (a1),d1        ;get number
30 *
31 * bra Q15 ;--- for timing only
32 *
33    beq    Q8        ;if number=0, skip
34 *
35 * Set initial values
36 *
37 Q7    moveq    #1,d2        ;guess1 := 1
38        move.1    d1,d3        ;guess2 := number
39 *
40 * Do shifts until guess1 ~  guess2
41 *
42 Q9    move.l    d2,d0        ;guess1 to work register
43    asl.l    #1,d0        ;guess1 * 2
44    cmp.l    d3,d0        ;compare with guess2
45    bge    Q11        ;branch if guess1 * 2 >= guess2
46    asl.l     #1,d2        ;guess1 := guess1 * 2
47    asr.l    #1,d3        ;guess2 := guess2 / 2
48    bra    Q9
49 *
50 * Now do divisions
51 *
52 Q11
53 Q13    add.l    d3,d2        ;guess := guess1 + guess2
54    asr.l    #1,d2        ;guess1 := (guess1+guess2)/2
55    move.l    d1,d0        ;number to work register
56    divs    d2,d0        ;number / guess1
57    move.w    d0,d3        ;guess2 := number/guess1
58    ext.l    d3        ;extend to 32 bits
59    move.l    d2,d0        ;guess1 to work register
60    sub.l    d3,d0        ;guess1-guess2
61    move.l    d0,d4        ;error := guess1-guess2
62    ble    Q14        ;if error <= 0
63    bra    Q13        ;loop back if error > 0
64 Q14    move.l    d2,d0        ;result := guess1
65    bra    Q15
66 Q8    moveq     #0,d0        ;result := 0
67 *
68 * Set result & return to caller
69 *
70 Q15    movea.w (sp)+,a1    ;get ^result
71    move.w    d0,(a1)        ;store result
72 *
73    addq.l    #2,sp        ;drop ^number
74    jmp    (a0)        ;return to caller
75 *
76    .nolist

Listing Three

1 *
2 * Squareroot algorithm; DDJ March 1986, p.122
3 *
4 * 68000 assembly language version
5 *
6 * Features:  - hand-optimized machine code;
7 *
8 *
9 * procedure sqrt(number:integer; var result:integer);
10 *
11 * Calculates square root of 'number' and returns it in 'result';
12 *
13 *
14 * Register usage:
15 * --------------
16 *
17 * D0 : work register, error        A0 : ^result
18 * D1 : number            A1 : ^number
19 * D2 : guess1,result
20 * D3 : guess2
21 * D4 : temporary storage for return address
22 *
23 *
24     .proc    sqrt,2        ;2 words of parameters
25 *
26 * Get parameters from stack
27 *
28    moveq #0,d2        ;result := 0 --- remove for timing
29 *
30     move.l     (sp)+,d4    ;get return address
31     move.w    (sp)+,a0    ;get ^result
32    move.w (sp)+,a1        ;get ^number
33    move.l    (a1),d1        ;get number
34 *
35 * bra Q15 ;--- for timing only
36 *
37    beq     Q15        ;if number=0, then result=0
38 *
39 * Set initial values
40 *
41 Q7    moveq    #1,d2        ;guess1 := 1
42        move.l    d1,d3        ;guess2 := number
43 *
44 * Do shifts until guess1 ~  guess2
45 *
46 Q9    asl.l    #1,d2        ;guess1 := guess1 * 2
47    cmp.l    d3,d2        ;compare with guess2
48    bge    Q11        ;branch if guess1 * 2 >= guess2
49    asr.l    #1,d3        ;guess2 := guess2 / 2
50    bra    Q9
51 *
52 Q11    asr.l    #1,d2        ;adjust guess1
53 *
54 * Now do divisions
55 *
56 Q13    add.l    d3,d2        ;guess1 := guess1 + guess2
57     asr.l    #1,d2        ;guess1 := (guess1+guess2)/2
58    move.l    d1,d3        ;guess2 := number
59    divs    d2,d3        ;guess2 := number / guess1
60    ext.l    d3        ;extend guess2 to 32 bits
61    move.l    d2,d0        ;guess1 to work register
62    sub.l    d3,d0        ;error := guess1 - guess2
63    bgt    Q13        ;loop back if error > 0
64 *
65 * Store result and return to caller
66 *
67 Q15    move.w     d2,(a0)        ;store result
68 *
69     movea.l    d4,a0        ;move return address to adr-reg
70    jmp    (a0)        ;return to caller
71 *
72    .nolist

Listing Four

1 *
2 * Squareroot algorithm; DDJ November 1985, p.88
3 *
4 * 68000 assembly language
5 *
6 * procedure sqrt(number:long; var result:integer);
7 *
8 * Calculates the integer squareroot of 'number' and returns it in 'result'
9 *
10 *
11 * Register usage
12 * --------------
13 *
14 * D0 : number        A0 : scratch, for pointers
15 * D1 : error term        A1 : scratch, for pointers
16 * D2 : estimate
17 * D3 : corrector term
18 * D4 : loop counter
19 *
20 *
21    .proc    sqrt,2        ;2 words of parameters
22 *
23     move.w     6(sp),a0    ;get ^number
24    move.l    (a0),d0        ;get number into d0
25 *
26 * bra exit ;--- for timing only
27 *
28    moveq    #16-1,d4    ;set loopcount,16*2 = 32 bits
29    moveq    #0,d1        ;clear error term
30     moveq    #0,d2        ;clear estimate
31 *
32 * Calculate squareroot
33 *
34 sqrtl asl.l #1,d0        ;get 2 leading bits,
35    roxl.l    #1,d1        ;one at a time, into
36    asl.l    #1,d0        ;the error term
37    roxl.l    #1,d1
38    asl.l     #1,d2        ;estimate * 2
39    move.l  d2,d3
40    asl.l    #1,d3        ;corrector = 2 * new estimate
41    cmp.l    d3,d1
42    bls    sqrt2        ;branch if error term <= corrector
43    addq.l    #1,d2        ;otherwise, add low bit to estimate
44    addq.l    #1,d3
45    sub.l    d3,d1        ;and calculate new error term
46 *
47 sqrt2 dbra    d4,sqrtl    ;do all 16 bit-pairs
48 *
49 * Set result & return to caller
50 *
51 exit    move.l     (sp)+,a0    ;get return address
52    move.w    (sp)+,a1    ;get ^result
53    move.w    d2,(a1)        ;store integer result
54    addq.l    #2,sp        ;drop ^number
55    jmp    (a0)        ;return to caller
56 *
57     .nolist


Listing Five

djnz:                    * 10   djnz e
    move.b    (pseudopc)+,d0        * d0 <-- distance
    subq.b    #1,regb(regs)        * dec b
    beq    djnz2            * loop count expired
    ext.w    d0            * to word
    ext.l    d0            * to long
    add.l    d0,pseudopc        * add distance
djnz2:
    NEXT
jr:                    * 18   jr e
    move.b    (pseudopc)+,d0        * d0 <-- distance
    ext.w    d0            * to word
    ext.l    d0            * to long
    add.l    d0,pseudopc        * add distance
    NEXT
jrnz:                    * 20   jr nz,e
    move.b    (pseudopc)+,d0        * d0 <-- distance
    btst    #6,regf            * if Z bit set
    bne    jrnz2            * then no branch
    ext.w    d0            * to word
    ext.l    d0            * to long
    add.l    d0,pseudopc        * add distance
jrnz2:
    NEXT
jrz:                    * 28   jr z,e
    move.b    (pseudopc)+,d0        * d0 <-- distance
    btst    #6,regf            * if Z bit reset
    beq    jrz2            * then no branch
    ext.w    d0            * to word
    ext.l     d0            * to long
    add.l    d0,pseudopc        * add distance
jrz2:
    NEXT
jrnc:                    * 30   jr nc,e
    move.b     (pseudopc)+,d0        * d0 <-- distance
    btst    #0,regf            * if C bit set
    bne    jrnc2            * then no branch
    ext.w    d0            * to word
    ext.l    d0            * to long
    add.l    d0,pseudopc        * add distance
jrnc2:
    NEXT
jrc:                    * 38 jr c,e
    move.b     (pseudopc)+,d0        * d0 <-- distance
    btst    #0,regf            * if C bit reset
    beq    jrc2            * then no branch
    ext.w    d0            * to word
    ext.l    d0            * to long
    add.l    d0,pseudopc        * add distance
jrc2:
    NEXT


Listing Six

1  /* c_draw.c */             /*   jnm  5-27-86  rev.1     */
2
3  /* corrected line drawing routine using Bresenham's algorithm...   */
4
5
6  c_draw (x1, y1, x2, y2, color)
7  int x1, y1, x2, y2, color;
8
9  {
10 int inc1, inc2, inc3, xend, yend;
11 int d, x, y, dx, dy;
12
13 dx = abs (x2 - x1);
14 dy = abs (y2 - y1);
15 if (dy <= dx)
16    {
17    if (x1 > x2)
18     {
19     x = x2;
20     y = y2;
21     xend = x1;
22     dy = y1 - y2;
23     }
24    else
25     {
26     x = x1;
27     y = y1;
28      xend = x2;
29     dy = y2 - y1;
30     }
31    inc1 = dy << 1;
32    inc2 = (dy - dx) << 1;
33    inc3 = (dy + dx) << 1;
34    d = (dy >= 0) ? inc1 - dx:inc1 + dx;
35    while (x < xend)
36     {
37     pcvwd (y, x, color);        /* or whatever point plotting */
38      x++;                /* function you have handy... */
39     if (d >= 0)
40        {
41        if (dy <= 0)
42           d += inc1;
43        else
44           {
45           y++;
46             d += inc2;
47           }
48        }
49     else
50        {
51        if (dy >= 0)
52           d += inc1;
53         else
54           {
55           y--;
56           d += inc3;
57           }
58        }
59     }
60    }
61 else
62    {
63    if (y1 > y2)
64     {
65     y = y2;
66     x = x2;
67     yend = y1;
68     dx = x1 - x2;
69     }
70    else
71     {
72     y = y1;
73      x = x1;
74     yend = y2
75     dx = x2 - x1;
76     }
77    inc1 = dx << 1;
78    inc2 = (dx - dy) << 1;
79    inc3 = (dx + dy) << 1;
80    d = (dx >= 0) ? inc1 - dy:inc1 + dy;
81    while (y < yend)
82     {
83     pcvwd (y, x, color);
84     y++;
85     if (d >= 0)
86        {
87        if (dx <= 0)
88           d += inc1;
89        else
90           {
91           x++;
92           d += inc2;
93             }
94        }
95     else
96        {
97        if (dx >= 0)
98             d += inc1;
99        else
100           {
101           x--;
102           d += inc3;
103           }
104         }
105     }
106   }
107 pcvwd (y, x, color);
108 }
109