; This file updates SRDSRT.MAC;1 from SRD V6.5 to SRDSRT.MAC;2 for SRD V6.6. SRDSRT.MAC;2/AU=SRDSRT.MAC;1 \ -/.IDENT/,. .IDENT -6.6- ; Jun-85 -/;=/,. ; ; Version 6.6 - 12-Jun-85 (;WG6.6) ; ; SRD Working Group ; ; Modify the sort algorithm for improved performance. ; (Thanks to Jim DeMange and Tony Gandy of Systeme ; Corporation, Orlando, FL.) ; ;= % -,,/;WG6.6/ -/SRDSRT::/ -/15$:/ -/MOV...R2,R3/,/BHIS...40$/ ; ; All sort information is now set up - ready to sort ; ; First we do a modified shell sort: ; An intial offset is calculated as m=(N+1)/2, that is, as ; 1/2 the total number of entries in the table (rounded up). ; A: Then loop with i=1 to N-m, comparing entry i with entry i+m, ; swapping any entries found to be out of order. ; Calculate a new value for the offset m as 1/2 the previous ; value (rounded up). When this value reaches 1, go on to the ; shuttle sort. Otherwise, go to A: above. ; A shell sort tends to get the entries into the correct area of ; the table with minimal swapping of entries. ; ; Complete the sort with a shuttle sort: ; Loop through the whole table, starting with i=1. ; B: Compare entry i with entry i+1. ; If the entries are in order, increment i and goto B: above. ; If they are out of order, we know that the previous entries are ; all sorted, so we need to find where to insert entry i+1. ; Store entry i+1 on the stack. ; Search backward (watching for the start of the table) starting at ; entry i-1 to find an entry j where entry j and entry i+1 are in ; order. When found, that means that entry i+1 should go where entry ; j+1 is, after entries j+1 through i are each moved one entry towards ; the end of the table. Accomplish this by moving entry i to i+1, ; i-1 to i, ..., until j+1 is moved to j+2. ; Move the entry on the stack to j+1 to complete the insert. ; Increment i to the next entry and continue with the loop. ; ; First do a modified shell sort MOV R0,-(SP) ; Save R0 MOV R1,R5 ; Get address of end of table SUB R2,R5 ; Compute table size in bytes CLR R4 ; Prepare for double register shift ASHC #-4,R4 ; Divide by 16. to get number of entries ; (Here we are assuming D.SIZ is 16.) MOV R5,R0 ; Save total number of entries 511$: INC R0 ; Inc current entry offset number (to round up) ASR R0 ; Divide by 2 to calculate new offset number CMP R0,#1 ; Test for Shell sort completion BLE 518$ ; LE - Shell sort completed MOV R2,R3 ; Get start of table address (1st entry to cmp) MOV R0,R4 ; Get entry offset number ASH #4,R4 ; Multiply by 16. to convert to byte offset ADD R2,R4 ; Compute address of entry at offset 512$: CALL COMPAR ; Compare entries pointed to by R3 and R4 BNE 515$ ; NE - swap required ADD #D.SIZ,R3 ; Step to next entry ADD #D.SIZ,R4 513$: CMP R4,R1 ; Have we reached the end of the table? BLO 512$ ; LO - no BR 511$ ; Go start next loop 515$: MOV #D.SIZ/2,R5 ; Set up loop count to swap entries 516$: MOV (R3),-(SP) ; Swap entries MOV (R4),(R3)+ MOV (SP)+,(R4)+ SOB R5,516$ BR 513$ ; Continue, pointing at next entries ; Now do shuttle sort 518$: MOV R2,R3 ; Get address of beginning of table 520$: MOV R3,R4 ; Copy address of current entry ADD #D.SIZ,R4 ; Point at next entry CMP R4,R1 ; Have we reached the end of the table? BHIS 563$ ; HIS - yes, sort completed CALL COMPAR ; Compare entries pointed to by R3 and R4 BEQ 540$ ; EQ - entries are in order MOV R4,R0 ; Save pointer to current position 525$: SUB #D.SIZ,R3 ; Back up through table CMP R3,R2 ; Have we gone beyond the start of the table? BLO 527$ ; LO - at start of table - entry should go here CALL COMPAR ; Compare entries BNE 525$ ; NE - have not yet found where entry should go 527$: MOV R0,-(SP) ; Save entry address ; Here the (R4) entry should go AFTER the (R3) entry .REPT D.SIZ/2 MOV (R4)+,-(SP) ; Save swap entry .ENDR ADD #D.SIZ*2,R3 ; Go back past entry to swap 530$: MOV -(R0),-(R4) ; Move all entries up in table CMP R4,R3 ; Test for all entries moved BHI 530$ ; HI - all entries have not yet been moved .REPT D.SIZ/2 MOV (SP)+,-(R3) ; Insert swap entry in its proper location .ENDR MOV (SP)+,R3 ; Point back to position to restart BR 520$ ; Continue comparisons from this point 540$: ADD #D.SIZ,R3 ; Point to next entry BR 520$ ; Continue comparisons ; All data sorted 563$: MOV (SP)+,R0 ; Restore R0 BR WBACK ; Continue ; ; COMPARE SUBROUTINE ; COMPAR: -/EXCHNG:/,/CONTINUE:/ EXCHNG: CLZ ; Clear Z-bit to indicate NE RETURN ; Return CONTINUE: SEZ ; Set Z-bit to indicate EQ RETURN ; Return ; ; Field compare modules ; -/SDD:/ -/COME HERE/,/BLO...15$/ /