retrodroid Posted January 25, 2023 Share Posted January 25, 2023 Folks, now that I have "pixels per second" speed regulation technology (tm), I'd like to make sure my game will render at the same speed on both NTSC and PAL systems, so PAL users don't have to suffer with the slow-motion version of things. Q: How does one detect in AL the output frequency in use? Quote Link to comment Share on other sites More sharing options...
+TheBF Posted January 25, 2023 Share Posted January 25, 2023 On 1/23/2023 at 6:25 PM, retrodroid said: I'm creating some more generic routines to do things like player sprite movement with different parameters depending on which mode they are in (walk, fall, climb, etc.) (to reduce code bloat). It's data-driven, using data lists I pass in in other registers. So I can configure the routine in the calling routine by setting up some registers to different lists of values, and even in this case other routines to be optionally called. " using data lists I pass in in other registers." Depending on the number of elements in these data lists, you might be able to make the data lists into workspaces and give your code access to the data via registers by using BLWP/RTWP. Just a thought. Quote Link to comment Share on other sites More sharing options...
apersson850 Posted January 25, 2023 Share Posted January 25, 2023 (edited) On 1/25/2023 at 3:07 PM, retrodroid said: Q: How does one detect in AL the output frequency in use? At game setup, run without interrupts, clear the VDP interrupt request bit, keep on testing that input until it interrupts, clear a counter and start counting in a loop while testing for the interrupt to occur again. Your count will be larger on a 50 Hz console, since you aren't interrupted that frequently. Regarding lists of programs; it's possible to make a table of addresses to programs. PROGTABLE DATA PROGRAM1 DATA PROGRAM2 DATA PROGRAM3 Then you can use an index in register one to jump to the program in question. SLA R1,1 MOV @PROGTABLE(R1),R2 BL *R2 or just B *R2 if you don't want to use it as a subroutine. Edited January 29, 2023 by apersson850 1 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted January 25, 2023 Share Posted January 25, 2023 1 hour ago, apersson850 said: At game setup, run without interrupts, clear the VDP interrupt request bit, keep on testing that input until it interruptts, clear a counter and start counting in a loop while testing for the interrupt to occur again. Your count will be larger on a 50 Hz console, since you aren't interrupted that frequently. Regarding lists of programs; it's possible to make a table of addresses to programs. PROGTABLE DATA PROGRAM1 DATA PROGRAM2 DATA PROGRAM3 Then you can use an index in register one to jump to the program in question. SLA R1,1 MOV @PROGTABLE(R1),R2 BL *R2 or just B *R2 if you don't want to use it as a subroutine. Do you need the MOV to R2 or can you just do: BL @PROGTABLE(R1) Quote Link to comment Share on other sites More sharing options...
apersson850 Posted January 25, 2023 Share Posted January 25, 2023 No, that's the tricky thing to understand. @PROGTABLE(R1) is the address to the item in the table. The data at that address is where you need to branch to. So you want to do BL *(@PROGTABLE(R1)), because you want to branch to the place which the data in the table points to, not to the table itself. But since the TMS 9900 can't do an indexed-deferred addressing in one fell swoop, you have to do it in two steps. But if you don't need the index any more, until you calculate it again, you can save a register by doing MOV @PROGTABLE(R1),R1 BL *R1 3 Quote Link to comment Share on other sites More sharing options...
Tursi Posted January 25, 2023 Share Posted January 25, 2023 (edited) 38 minutes ago, TheBF said: Do you need the MOV to R2 or can you just do: BL @PROGTABLE(R1) You need the MOV to R2. "PROGTABLE(R1)" resolves to an address inside the lookup table - the 9900 doesn't have any double-reference instructions. That said, you could struct it as a jump table instead, and use that: PROGTABLE B @PROG1 B @PROG2 B @PROG3 B @PROG4 CODE SLA 1,2 * each instruction is 4 bytes long BL @PROGTABLE(R1) It's a bit faster in 16 bit RAM (Base speed of 40 cycles vs 52 cycles in 16-bit RAM, 60 vs 68 in 8 bit) but eats twice as much memory for the table. (FWIW, I went through this twice because I fully expected this method to be slower. But the difference in cycles between a branch and a move is significant (8 cycles vs 14 - it's almost double), so the double jump doesn't hurt as much as I expected. That said, I need to double check whether the B@ is symbolic, I think it is.. that adds 8 more cycles which would make it barely faster in 16 bit RAM and equivalent in 8 bit RAM). I went through it a third time, on paper this time, and I was way off. In both 8 bit and 16 bit the register version is 4 cycles faster. So, there's not really any good reason to use the jump table, except maybe no free registers (assuming you can't reuse R1 as aperrson suggested). SLA 1,2 16+4 20 16 Bl @TABLE(R1) 12+4+4+8 28 20 B @TARGET 8+4+4+8 24 16 72 52 SLA 1,1 14+4 18 14 MOV @TABLE(1),2 14+4+4+8+4 34 22 BL *2 12+4+4 20 16 72 52 Equal, and I'm walking away now. Edited January 25, 2023 by Tursi 3 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted January 25, 2023 Share Posted January 25, 2023 "There are no free lunches with the 9900". 1 2 Quote Link to comment Share on other sites More sharing options...
HOME AUTOMATION Posted January 25, 2023 Share Posted January 25, 2023 Not sure this works the same. It progressively compares the WORDS in DTAB, to the WORD @>7272, then when a match is found, uses the count, to Branch-Link, to the associated address in JTAB. A R3,R2 *add count to JTAB MOV *R2,R2 *move the address found in the jump table into R2 BL *R2 *execute code there AORG >7380 DEF ONSCRN REF VSBW DTAB DATA >6897,>30CF,>18E7,>7A85,>10EF DATA >38C7,>5AA5,>42BD,>4AB5,>52AD ONSCRN MOV R11,R15 INPUT CLR R0 PRESS BL @>7330 BL @>7276 LI R1,DTAB LI R2,JTAB CLR R3 COMP INCT R3 CI R3,22 JEQ PRESS C @>7272,*R1+ JNE COMP DECT R3 A R3,R2 MOV *R2,R2 BL *R2 SWPB R1 BLWP @VSBW INC R0 JMP PRESS JTAB DATA D0,D1,D2,D3,D4,D5,D6 DATA D7,D8,D9 D0 LI R1,>30 RT D1 LI R1,>31 RT D2 LI R1,>32 RT D3 LI R1,>33 RT D4 LI R1,>34 RT D5 LI R1,>35 RT D6 LI R1,>36 RT D7 LI R1,>37 RT D8 LI R1,>38 RT D9 LI R1,>39 RT END Not sure how fast this compares to the other methods, or if it indeed compares at all. It runs fast enough to type on a remote control w/o missing any keystrokes. YAY! P.S. Did I mention that I borrowed some of this code... not sure where from... maybe a driver? Quote Link to comment Share on other sites More sharing options...
apersson850 Posted January 25, 2023 Share Posted January 25, 2023 I hope you got it from a cab driver or something. It would not have ranked high if I had seen this back when I was teaching programming part time at university. I've for sure not tested it, but in my mind, this code produces the same result. AORG >7380 DEF ONSCRN REF VSBW DTAB DATA >6897,>30CF,>18E7,>7A85,>10EF DATA >38C7,>5AA5,>42BD,>4AB5,>52AD ONSCRN MOV R11,R15 INPUT CLR R0 PRESS BL @>7330 BL @>7276 LI R1,DTAB CLR R3 COMP INC R3 CI R3,11 JEQ PRESS C @>7272,*R1+ JNE COMP LI R1,>30-1 A R3,R1 SWPB R1 BLWP @VSBW INC R0 JMP PRESS END 1 Quote Link to comment Share on other sites More sharing options...
retrodroid Posted January 25, 2023 Share Posted January 25, 2023 6 hours ago, TheBF said: " using data lists I pass in in other registers." Depending on the number of elements in these data lists, you might be able to make the data lists into workspaces and give your code access to the data via registers by using BLWP/RTWP. Just a thought. I did think of that, when I was dying a miserable death trying to remap a bunch of routines to spread register usage around. Changing the code to renumber the registers being used is a delicate art, to say the least. However, I'm not enabling interrupts in my code, isn't that a pre-requisite to using BLWP? 3 hours ago, Tursi said: You need the MOV to R2. "PROGTABLE(R1)" resolves to an address inside the lookup table - the 9900 doesn't have any double-reference instructions. That said, you could struct it as a jump table instead, and use that: PROGTABLE B @PROG1 B @PROG2 B @PROG3 B @PROG4 CODE SLA 1,2 * each instruction is 4 bytes long BL @PROGTABLE(R1) That's amazeballs! So much flexibility available takes some effort to get my mind to think "outside the box". Thanks. 45 minutes ago, apersson850 said: I hope you got it from a cab driver or something. It would not have ranked high if I had seen this back when I was teaching programming part time at university. Remind me to never post my code here... "the shame!". I'm kind of like a trial-and-error monkey at the keyboard at this point. The benefit of AL is that when do mess up, you tend to know it immediately. That and the blistering speed will forgive many sins. 1 2 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted January 25, 2023 Share Posted January 25, 2023 1 minute ago, retrodroid said: I did think of that, when I was dying a miserable death trying to remap a bunch of routines to spread register usage around. Changing the code to renumber the registers being used is a delicate art, to say the least. However, I'm not enabling interrupts in my code, isn't that a pre-requisite to using BLWP? Not at all. You can BLWP anytime you want to. (Well... maybe not in public places) 1 1 Quote Link to comment Share on other sites More sharing options...
HOME AUTOMATION Posted January 25, 2023 Share Posted January 25, 2023 56 minutes ago, apersson850 said: I've for sure not tested it, but in my mind, this code produces the same result. That looks interesting... I think I chose that way of doing it because there are many more buttons on a remote control, which do not associate with numbers or letters. Seems convenient to be able to stagger the subs' lengths. Also, with many keys, I suppose that simple JMPs, would eventually go out-of-range. I have met some rather accommodating cab/limo DRIVERS though. 'Scull's Angels'🚕 is long gone. But, Attitude New York, isn't too bad!🚙 1 Quote Link to comment Share on other sites More sharing options...
Tursi Posted January 26, 2023 Share Posted January 26, 2023 10 hours ago, TheBF said: "There are no free lunches with the 9900". It really does help reinforce that at least on the 4/A, the number of instructions has more to do with performance than any particular algorithm. 2 Quote Link to comment Share on other sites More sharing options...
apersson850 Posted January 26, 2023 Share Posted January 26, 2023 15 hours ago, HOME AUTOMATION said: That looks interesting... I think I chose that way of doing it because there are many more buttons on a remote control, which do not associate with numbers or letters The program I posted just tried to slim the execution of what you posted. I noticed for example that your conversion always ended with a code increasing by one. In such a case, you can just as well calculate it, instead of looking it up in a table. If there are more things to do, that you didn't show, then that may change things. @Tursi Very true, but a good algorithm may achieve just that. 1 Quote Link to comment Share on other sites More sharing options...
Tursi Posted January 26, 2023 Share Posted January 26, 2023 3 hours ago, apersson850 said: @Tursi Very true, but a good algorithm may achieve just that. @apersson850 ANY generalization has specific cases that don't match it. Probably even this one! It's not necessary to call it out. But I challenge you to show me one. Show me an algorithm that runs on the TI with standard 8-bit wait states that runs faster with more instructions executed than one that does the same work with fewer instructions. No cheating with do-nothing code like using 16 shifts to clear a register or such. I fully believe it exists. In fact I've probably written one. But it's pretty exceptional when it happens and I can't think of an example. Quote Link to comment Share on other sites More sharing options...
apersson850 Posted January 26, 2023 Share Posted January 26, 2023 Perhaps you misunderstood me there. What I tried to say was that a good algorithm may result in fewer instructions being executed. Quote Link to comment Share on other sites More sharing options...
Tursi Posted January 26, 2023 Share Posted January 26, 2023 4 hours ago, apersson850 said: Perhaps you misunderstood me there. What I tried to say was that a good algorithm may result in fewer instructions being executed. Good call. I still like the challenge. 1 Quote Link to comment Share on other sites More sharing options...
+InsaneMultitasker Posted January 26, 2023 Share Posted January 26, 2023 On 1/25/2023 at 3:31 PM, retrodroid said: Remind me to never post my code here... "the shame!". I'm kind of like a trial-and-error monkey at the keyboard at this point. The benefit of AL is that when do mess up, you tend to know it immediately. That and the blistering speed will forgive many sins Post away! Sometimes, the "best" or "fastest" code is not the right code for the situation... or for the programmer sitting behind the keyboard. If your code doesn't require peak performance and/or you have space to code things in a way you can understand, that's perfectly fine. Want to use BLWP utility routines instead of rolling your own, great! there might be some limitations or caveats, particularly for games, so understanding when to use an approach can be just as important as how to use it. All part of learning, IMHO. The only text I felt was missing from the recent examples was a comment or two or three. I dare say most of us have looked at a piece of their own code six months after writing it and asked themselves, "why didn't I write this a different way?". 1 Quote Link to comment Share on other sites More sharing options...
SteveB Posted January 26, 2023 Share Posted January 26, 2023 21 minutes ago, InsaneMultitasker said: I dare say most of us have looked at a piece of their own code six months after writing it and asked themselves, "why didn't I write this a different way?". or even "was this really me?" ... 2 Quote Link to comment Share on other sites More sharing options...
Tursi Posted January 26, 2023 Share Posted January 26, 2023 No doubt! And yeah, post away. Getting it working matters first. Optimization comes later if you need it. 1 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted January 26, 2023 Share Posted January 26, 2023 1 hour ago, Tursi said: Good call. I still like the challenge. I think @apersson850 's quick sort is a good candidate Lot's of instructions but the algorithm makes the difference. Sorts really fast. Spoiler .NARROWPAGE .PAGEHEIGHT 72 .TITLE "QUICKSORT FOR INTEGERS" ;Procedure sorting integers in ascending order ;Called from Pascal host by QSORT(A,N); ;Declared as PROCEDURE QSORT(VAR A:VECTOR; N:INTEGER); EXTERNAL; ;Vector should be an array [..] of integer; ;Author: @APERSON850 on Atariag.com ;-------------- ;Workspace registers for subroutine at START ; ;R0 Array base pointer ;R1 Array end pointer ;R2 L ;R3 R ;R4 I ;R5 J ;R6 KEY ;R7 Temporary ;R8 Temporary ;R9 Subfile stack pointer ;R10 Main stackpointer ;R11 Pascal return address (P-system WS) ;R12 Not used ;R13 Calling program's Workspace Pointer ;R14 Calling program's Program Counter ;R15 Calling program's Status Register ;----------------- ;The actual vector in the Pascal-program could be indexed [1..n] ;This routine assumes only that n indicates the number of elements, not the ;last array index. .RELPROC QSORT,2 LIMIT .EQU 16 ;Quick- or Insertionsort limit BLWP @SORTING AI R10,4 ;Simulate pop of two words B *R11 ;Back to Pascal host SORTING .WORD SORTWS ;Transfer vector for Quicksort .WORD START START MOV @14H(R13),R10 ;Get stackpointer from calling program's WP LI R9,ENDOFSTK ;SUBFILE STACKPOINTER MOV *R10+,R1 ;GET PARAMETER N MOV *R10+,R0 ;GET ARRAY POINTER DEC R1 SLA R1,1 A R0,R1 ;CALCULATE ARRAY ENDPOINT MOV R0,R2 ;L:=1 MOV R1,R3 ;R:=N MOV R1,R7 S R0,R7 CI R7,LIMIT JLE INSERT ;FIGURE OUT IF QUICKSORT IS NEEDED MAINLOOP MOV R2,R7 SRL R7,1 MOV R3,R8 SRL R8,1 A R8,R7 ANDI R7,0FFFEH ;R7:=INT((L+R)/2) MOV *R7,R8 MOV @2(R2),*R7 MOV R8,@2(R2) ;A[(L+R)/2]:=:A[L+1] C @2(R2),*R3 JLT NOSWAP1 MOV @2(R2),R8 MOV *R3,@2(R2) MOV R8,*R3 ;A[L+1]:=:A[R] NOSWAP1 C *R2,*R3 JLT NOSWAP2 MOV *R2,R8 MOV *R3,*R2 MOV R8,*R3 ;A[L]:=:A[R] NOSWAP2 C @2(R2),*R2 JLT NOSWAP3 MOV @2(R2),R8 MOV *R2,@2(R2) MOV R8,*R2 ;A[L+1]:=:A[L] NOSWAP3 MOV R2,R4 INCT R4 ;I:=L+1 MOV R3,R5 ;J:=R MOV *R2,R6 ;KEY:=A[L] JMP INCLOOP INNERLOP MOV *R4,R8 ;LOOP UNWRAPPING MOV *R5,*R4 MOV R8,*R5 ;A[I]:=:A[J] INCLOOP INCT R4 ;I:=I+1 C *R4,R6 JLT INCLOOP ;A[I]<KEY DECLOOP DECT R5 ;J:=J-1 C *R5,R6 JGT DECLOOP ;A[J]>KEY C R4,R5 JLE INNERLOP ;IF I<=J THEN CONTINUE OUT MOV *R2,R8 MOV *R5,*R2 MOV R8,*R5 ;A[L]:=:A[J] DEL1 MOV R5,R7 ;Quicksort subfiles? S R2,R7 ;R7:=J-L MOV R3,R8 S R4,R8 INCT R8 ;R8:=R-I+1 CI R7,LIMIT JH DEL2 CI R8,LIMIT JH DEL2 CI R9,ENDOFSTK ;LVL=0? JEQ INSERT ;No more Quicksorting at all? MOV *R9+,R2 ;POP L MOV *R9+,R3 ;POP R JMP MAINLOOP DEL2 C R7,R8 ;Determine what is small and large subfile JL ELSE2 MOV R2,@LSFL MOV R5,@LSFR DECT @LSFR MOV R4,@SSFL MOV R3,@SSFR JMP DEL3 ELSE2 MOV R4,@LSFL MOV R3,@LSFR MOV R2,@SSFL MOV R5,@SSFR DECT @SSFR DEL3 CI R7,LIMIT ;Is small subfile big enough to be sorted by JLE THEN3 ;Quicksort? CI R8,LIMIT JH ELSE3 THEN3 MOV @LSFL,R2 ;Don't Quicksort small subfile, only large MOV @LSFR,R3 JMP MAINLOOP ELSE3 DECT R9 ;Stack large subfile MOV @LSFR,*R9 ;PUSH R DECT R9 MOV @LSFL,*R9 ;PUSH L MOV @SSFL,R2 ;Sort small subfile MOV @SSFR,R3 JMP MAINLOOP ;Insertionsort finishing up INSERT MOV R1,R4 DECT R4 ;I:=N-1 C R4,R0 JL LEAVE ;Check if any looping at al FORI C @2(R4),*R4 JGT NEXTI ;If next is greater than this, it's OK MOV *R4,R6 ;KEY:=A[I] MOV R4,R5 INCT R5 ;J:=I+1 WHILE MOV *R5,@-2(R5) ;A[J-1]:=A[J] INCT R5 ;J:=J+1 C R5,R1 JH ENDWHILE ;J>N? C *R5,R6 ;A[J]<KEY? JLT WHILE ENDWHILE MOV R6,@-2(R5) ;A[J-1]:=KEY NEXTI DECT R4 C R4,R0 ;Check if passed array base point JHE FORI LEAVE RTWP ;Return to main assembly level ;-------------- ; DATA AREA SORTWS .BLOCK 20H,0 ;Workspace for sorting routine SUBFSTK .BLOCK 40H,0 ;Internal subfile stack ENDOFSTK .EQU SUBFSTK+40H ;End of that stack LSFL .WORD 0 ;Large SubFile Left pointer LSFR .WORD 0 ;Large SubFile Right pointer SSFL .WORD 0 ;Small SubFile Left pointer SSFR .WORD 0 ;Small SubFile Right pointer .END Quote Link to comment Share on other sites More sharing options...
+OLD CS1 Posted January 27, 2023 Share Posted January 27, 2023 1 hour ago, InsaneMultitasker said: The only text I felt was missing from the recent examples was a comment or two or three. I dare say most of us have looked at a piece of their own code six months after writing it and asked themselves, "why didn't I write this a different way?". Comments are a crutch. If the code was difficult to write, it should be difficult to understand. -- Unknown Always code as if the person who ends up maintaining your code will be a violent psychopath who knows where you live -- The guy hired after Unknown Always think of the poor schmuck who has to come in and work after you. It will often be you. -- AvE 1 1 4 Quote Link to comment Share on other sites More sharing options...
Jeff White Posted January 28, 2023 Share Posted January 28, 2023 Sometimes it may make sense to load your workspace registers with subroutine addresses. E.g., MYWS could be: MYWS DATA S0,S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,0,S12,S13,S14,S15 The S? addresses are your subs, which can be called with B *R? or BL *R?, where R? is a workspace register. R11 is reserved for return. If you can limit the subs, you gain registers you can make general purpose. Preload registers with subs? Is that stupid? How many subs does a program have? How many general registers are normally used? 1 Quote Link to comment Share on other sites More sharing options...
Tursi Posted January 28, 2023 Share Posted January 28, 2023 On 1/26/2023 at 4:59 PM, TheBF said: I think @apersson850 's quick sort is a good candidate Lot's of instructions but the algorithm makes the difference. Sorts really fast. Reveal hidden contents .NARROWPAGE .PAGEHEIGHT 72 .TITLE "QUICKSORT FOR INTEGERS" ;Procedure sorting integers in ascending order ;Called from Pascal host by QSORT(A,N); ;Declared as PROCEDURE QSORT(VAR A:VECTOR; N:INTEGER); EXTERNAL; ;Vector should be an array [..] of integer; ;Author: @APERSON850 on Atariag.com ;-------------- ;Workspace registers for subroutine at START ; ;R0 Array base pointer ;R1 Array end pointer ;R2 L ;R3 R ;R4 I ;R5 J ;R6 KEY ;R7 Temporary ;R8 Temporary ;R9 Subfile stack pointer ;R10 Main stackpointer ;R11 Pascal return address (P-system WS) ;R12 Not used ;R13 Calling program's Workspace Pointer ;R14 Calling program's Program Counter ;R15 Calling program's Status Register ;----------------- ;The actual vector in the Pascal-program could be indexed [1..n] ;This routine assumes only that n indicates the number of elements, not the ;last array index. .RELPROC QSORT,2 LIMIT .EQU 16 ;Quick- or Insertionsort limit BLWP @SORTING AI R10,4 ;Simulate pop of two words B *R11 ;Back to Pascal host SORTING .WORD SORTWS ;Transfer vector for Quicksort .WORD START START MOV @14H(R13),R10 ;Get stackpointer from calling program's WP LI R9,ENDOFSTK ;SUBFILE STACKPOINTER MOV *R10+,R1 ;GET PARAMETER N MOV *R10+,R0 ;GET ARRAY POINTER DEC R1 SLA R1,1 A R0,R1 ;CALCULATE ARRAY ENDPOINT MOV R0,R2 ;L:=1 MOV R1,R3 ;R:=N MOV R1,R7 S R0,R7 CI R7,LIMIT JLE INSERT ;FIGURE OUT IF QUICKSORT IS NEEDED MAINLOOP MOV R2,R7 SRL R7,1 MOV R3,R8 SRL R8,1 A R8,R7 ANDI R7,0FFFEH ;R7:=INT((L+R)/2) MOV *R7,R8 MOV @2(R2),*R7 MOV R8,@2(R2) ;A[(L+R)/2]:=:A[L+1] C @2(R2),*R3 JLT NOSWAP1 MOV @2(R2),R8 MOV *R3,@2(R2) MOV R8,*R3 ;A[L+1]:=:A[R] NOSWAP1 C *R2,*R3 JLT NOSWAP2 MOV *R2,R8 MOV *R3,*R2 MOV R8,*R3 ;A[L]:=:A[R] NOSWAP2 C @2(R2),*R2 JLT NOSWAP3 MOV @2(R2),R8 MOV *R2,@2(R2) MOV R8,*R2 ;A[L+1]:=:A[L] NOSWAP3 MOV R2,R4 INCT R4 ;I:=L+1 MOV R3,R5 ;J:=R MOV *R2,R6 ;KEY:=A[L] JMP INCLOOP INNERLOP MOV *R4,R8 ;LOOP UNWRAPPING MOV *R5,*R4 MOV R8,*R5 ;A[I]:=:A[J] INCLOOP INCT R4 ;I:=I+1 C *R4,R6 JLT INCLOOP ;A[I]<KEY DECLOOP DECT R5 ;J:=J-1 C *R5,R6 JGT DECLOOP ;A[J]>KEY C R4,R5 JLE INNERLOP ;IF I<=J THEN CONTINUE OUT MOV *R2,R8 MOV *R5,*R2 MOV R8,*R5 ;A[L]:=:A[J] DEL1 MOV R5,R7 ;Quicksort subfiles? S R2,R7 ;R7:=J-L MOV R3,R8 S R4,R8 INCT R8 ;R8:=R-I+1 CI R7,LIMIT JH DEL2 CI R8,LIMIT JH DEL2 CI R9,ENDOFSTK ;LVL=0? JEQ INSERT ;No more Quicksorting at all? MOV *R9+,R2 ;POP L MOV *R9+,R3 ;POP R JMP MAINLOOP DEL2 C R7,R8 ;Determine what is small and large subfile JL ELSE2 MOV R2,@LSFL MOV R5,@LSFR DECT @LSFR MOV R4,@SSFL MOV R3,@SSFR JMP DEL3 ELSE2 MOV R4,@LSFL MOV R3,@LSFR MOV R2,@SSFL MOV R5,@SSFR DECT @SSFR DEL3 CI R7,LIMIT ;Is small subfile big enough to be sorted by JLE THEN3 ;Quicksort? CI R8,LIMIT JH ELSE3 THEN3 MOV @LSFL,R2 ;Don't Quicksort small subfile, only large MOV @LSFR,R3 JMP MAINLOOP ELSE3 DECT R9 ;Stack large subfile MOV @LSFR,*R9 ;PUSH R DECT R9 MOV @LSFL,*R9 ;PUSH L MOV @SSFL,R2 ;Sort small subfile MOV @SSFR,R3 JMP MAINLOOP ;Insertionsort finishing up INSERT MOV R1,R4 DECT R4 ;I:=N-1 C R4,R0 JL LEAVE ;Check if any looping at al FORI C @2(R4),*R4 JGT NEXTI ;If next is greater than this, it's OK MOV *R4,R6 ;KEY:=A[I] MOV R4,R5 INCT R5 ;J:=I+1 WHILE MOV *R5,@-2(R5) ;A[J-1]:=A[J] INCT R5 ;J:=J+1 C R5,R1 JH ENDWHILE ;J>N? C *R5,R6 ;A[J]<KEY? JLT WHILE ENDWHILE MOV R6,@-2(R5) ;A[J-1]:=KEY NEXTI DECT R4 C R4,R0 ;Check if passed array base point JHE FORI LEAVE RTWP ;Return to main assembly level ;-------------- ; DATA AREA SORTWS .BLOCK 20H,0 ;Workspace for sorting routine SUBFSTK .BLOCK 40H,0 ;Internal subfile stack ENDOFSTK .EQU SUBFSTK+40H ;End of that stack LSFL .WORD 0 ;Large SubFile Left pointer LSFR .WORD 0 ;Large SubFile Right pointer SSFL .WORD 0 ;Small SubFile Left pointer SSFR .WORD 0 ;Small SubFile Right pointer .END I think you'll find that a bubble sort or such actually executes more instructions. The speed of quick sort is obtained by needing to go through the data fewer times. Quote Link to comment Share on other sites More sharing options...
GDMike Posted January 28, 2023 Share Posted January 28, 2023 I'll always think of it as Bull Whip and not Bull Whoops! 1 1 Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.