mirror of
https://github.com/elliotnunn/boot3.git
synced 2024-05-28 15:41:27 +00:00
5b0f0cc134
Resource forks are included only for .rsrc files. These are DeRezzed into their data fork. 'ckid' resources, from the Projector VCS, are not included. The Tools directory, containing mostly junk, is also excluded.
197 lines
5.1 KiB
Plaintext
197 lines
5.1 KiB
Plaintext
;EASE$$$ READ ONLY COPY of file ÒSORTPOINTS.aÓ
|
|
;¥1.4 BAL 05/29/1989 Blasting in 32-Bit QuickDraw version 1.0 Final
|
|
;¥1.3 BAL 04/12/1989 Blasting in 32-Bit QuickDraw 1.0B1
|
|
; File SortPoints.a
|
|
;
|
|
; Copyright Apple Computer, Inc. 1981-1986
|
|
; All Rights Reserved
|
|
|
|
|
|
BLANKS ON
|
|
STRING ASIS
|
|
|
|
;------------------------------------------------------------------
|
|
;
|
|
; --> SORTPOINTS.TEXT
|
|
;
|
|
; Routines to sort inversion points and cull duplicates.
|
|
;
|
|
|
|
; MODIFICATION HISTORY
|
|
;
|
|
; 12May86 EHB Minor speed enhancement
|
|
|
|
SortPoints PROC EXPORT
|
|
;-------------------------------------------------------------
|
|
;
|
|
; 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
|
|
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'
|
|
|
|
|
|
|
|
|
|
|
|
CullPoints PROC EXPORT
|
|
;-------------------------------------------------------------
|
|
;
|
|
; 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.S 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'
|
|
|
|
|
|
|
|
|
|
|
|
ENDPROC
|
|
|
|
|
|
|