home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
magazine
/
drdobbs
/
1986
/
09
/
letters.sep
< prev
next >
Wrap
Text File
|
1986-09-30
|
11KB
|
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