This repository has been archived by the owner on Nov 29, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
SortPoints.a
180 lines (148 loc) · 7.12 KB
/
SortPoints.a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
.INCLUDE GRAFTYPES.TEXT
;------------------------------------------------------------------
;
; --> SORTPOINTS.TEXT
;
; Routines to sort inversion points and cull duplicates.
;
.PROC SortPoints
;-------------------------------------------------------------
;
; PROCEDURE SortPoints(ptBuf: PointsPtr; ptCount: INTEGER);
;
; PERFORMS A NON-RECURSIVE QUICKSORT ON AN ARRAY OF POINTS
; TO PUT THEM IN INCREASING VERT.HORIZ ORDER.
;
; RE-WROTE 5 SEPT 83 TO CUT DOWN WORST CASE STACK USAGE
;
; See Algorithms + Data Structures = Programs, p.80
;
; A6 OFFSETS OF PARAMETERS AFTER LINK:
;
PARAMSIZE .EQU 6
PTBUF .EQU PARAMSIZE+8-4 ;LONG
PTCOUNT .EQU PTBUF-2 ;WORD
LINK A6,#0 ;NO LOCAL VARIABLES
MOVEM.L D3-D4/A2-A4,-(SP) ;SAVE REGS
MOVE.L PTBUF(A6),A3 ;LEFTPTR:=START OF PT ARRAY
MOVE A3,D3
AND #3,D3 ;SET UP LOBITS FOR SORT
CLR.L D0
MOVE PTCOUNT(A6),D0 ;GET PTCOUNT
BLE.S GOHOME ;DO NOTHING IF NO POINTS
LSL.L #2,D0 ;QUAD PTCOUNT FOR BYTES
MOVE.L A3,A4
ADD.L D0,A4 ;ADD TO DSTSTART
SUB #4,A4 ;RIGHTPTR:=DSTEND-4
MOVE.L SP,D4 ;REMEMBER STACK MARKER
MOVEM.L A3/A4,-(SP) ;PUSH LEFTPTR AND RIGHTPTR
POPNXT MOVEM.L (SP)+,A3/A4 ;POP LEFTPTR AND RIGHTPTR
SPLIT MOVE.L A3,A1 ;IPTR := LEFTPTR
MOVE.L A4,A2 ;JPTR := RIGHTPTR
;
; CALC MIDPTR AND MIDPT
;
MOVE.L A3,D0 ;ADD LEFTPTR
ADD.L A4,D0 ;AND RIGHTPTR
ROXR.L #1,D0 ;THEN DIVIDE BY 2 FOR MIDPTR
AND #$FFFC,D0 ;TRUNC TO MULTIPLE OF 4 BYTES
OR D3,D0 ;OR IN LOBITS FOR POINT BOUNDARY
MOVE.L D0,A0 ;GET MIDPTR INTO A-REG
MOVE H(A0),D1 ;GET MIDPT.H
MOVE V(A0),D2 ;AND MIDPT.V
SCAN
;
; WHILE IPTR^ < MIDPT DO BUMP IPTR TO RIGHT
;
BRA.S TWO ;GO TO LOOP START
ONE ADD #4,A1 ;BUMP IPTR TO RIGHT
TWO CMP V(A1),D2 ;IS MIDPT.V > IPTR^.V ?
BGT ONE ;YES, BUMP SOME MORE
BLT.S THREE ;BR IF DONE WITH IPTR.
CMP H(A1),D1 ;IF SAME VERT, LOOK AT HORIZ
BGT ONE ;KEEP BUMPING IF MIDPT.H > IPTR^.H
THREE
;
; WHILE JPTR^ > MIDPT DO BUMP JPTR TO LEFT
;
BRA.S FIVE ;GO TO LOOP START
FOUR SUB #4,A2 ;BUMP JPTR TO LEFT
FIVE CMP V(A2),D2 ;IS MIDPT.V < JPTR^.V ?
BLT FOUR ;YES, BUMP SOME MORE
BGT.S SIX ;BR IF DONE BUMPING JPTR
CMP H(A2),D1 ;IF SAME VERT, LOOK AT HORIZ
BLT FOUR ;KEEP BUMPING IF MIDPT.H < JPTR^.H
SIX
;
; if IPtr <= JPtr then swap IPtr^ and JPtr^, and bump both pointers
;
CMP.L A2,A1 ;IS IPTR > JPTR ?
BGT.S NOSWAP ;YES, ALL DONE
MOVE.L (A1),D0
MOVE.L (A2),(A1)
MOVE.L D0,(A2) ;SWAP POINTS
ADD #4,A1 ;BUMP IPTR TO RIGHT
SUB #4,A2 ;BUMP JPTR TO LEFT
;
; repeat until this partitioning is complete, IPtr > JPtr
;
NOSWAP CMPA.L A2,A1 ;IS IPTR > JPTR ?
BLS SCAN ;NO, LOOP AGAIN
;
; IF i < right then stack request to sort right partition
;
CMPA.L A4,A1 ;IS IPTR < RIGHTPTR ?
BHS.S RIGHTOK ;YES, CONTINUE
MOVEM.L A1/A4,-(SP) ;NO, PUSH IPTR,RIGHTPTR
RIGHTOK MOVE.L A2,A4 ;RIGHTPTR := JPTR
CMPA.L A4,A3 ;IS LEFTPTR >= RIGHTPTR ?
BLO SPLIT ;NO, PARTITION AGAIN
CMPA.L D4,SP ;IS STACK EMPTY YET ?
BNE POPNXT ;NO, LOOP FOR MORE
GOHOME MOVEM.L (SP)+,D3-D4/A2-A4 ;RESTORE REGS
UNLINK PARAMSIZE,'SORTPOIN'
.PROC CullPoints,2
;-------------------------------------------------------------
;
; PROCEDURE CullPoints(ptBuf: PointsPtr; VAR ptCount: INTEGER);
;
; CANCEL ANY DUPLICATE PAIRS OF POINTS IN AN ARRAY OF POINTS.
;
;
; A6 OFFSETS OF PARAMETERS AFTER LINK:
;
PARAMSIZE .EQU 8
PTBUF .EQU PARAMSIZE+8-4 ;LONG
PTCOUNT .EQU PTBUF-4 ;LONG, VAR
LINK A6,#0 ;NO LOCAL VARIABLES
MOVEM.L D0-D7/A1-A5,-(SP) ;SAVE REGS
MOVE.L PTCOUNT(A6),A0 ;GET VAR ADDR OF PTCOUNT
MOVE (A0),D0 ;GET PTCOUNT
BLE GOHOME ;DO NOTHING IF NO POINTS
MOVE.L PTBUF(A6),A1 ;SRCPTR:=START PTR
MOVE.L A1,A3 ;COPY START
EXT.L D0 ;CLEAR HI WORD
LSL.L #2,D0 ;QUAD PTCOUNT FOR BYTES
ADD.L D0,A3 ;ADD TO START
SUB #4,A3 ;LAST POINT IS AT END-4
MOVE.L A1,D5 ;SAVE START FOR LATER
MOVE.L A1,A2 ;DSTPTR:=START
BRA.S WHILE1 ;GO TO LOOP START
DELETE ADD #4,A1 ;SKIP OVER BOTH SRC POINTS
BRA.S WHILE1 ;GO TO LOOP START
MORE1 MOVE.L (A1)+,D0 ;GET CURRENT SRC POINT
CMP.L (A1),D0 ;IS IT SAME AS NEXT ?
BEQ DELETE ;YES, DELETE BOTH
MOVE.L D0,(A2)+ ;NO, COPY TO DST
WHILE1 CMP.L A3,A1 ;IS SRCPTR < LASTPTR ?
BLT.S MORE1 ;YES, GO FOR MORE
BGT.S DONE
MOVE.L (A1)+,(A2)+ ;FINISH UP LAST POINT
DONE MOVE.L A2,D0 ;GET DST PTR
SUB.L D5,D0 ;SUBTRACT START PTR
LSR #2,D0 ;DIV BY 4 FOR PTCOUNT
MOVE.L PTCOUNT(A6),A0 ;GET VAR ADDR
MOVE D0,(A0) ;UPDATE PTCOUNT TO REFLECT DELETIONS
GOHOME MOVEM.L (SP)+,D0-D7/A1-A5 ;RESTORE REGS
UNLINK PARAMSIZE,'CULLPOIN'
.END