Jump to content
IGNORED

Assembly on the 99/4A


Recommended Posts

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?

 

 

Link to comment
Share on other sites

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. 

Link to comment
Share on other sites

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 by apersson850
  • Thanks 1
Link to comment
Share on other sites

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)

 

Link to comment
Share on other sites

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

  • Like 3
Link to comment
Share on other sites

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 by Tursi
  • Haha 3
Link to comment
Share on other sites

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!:party:

 

     P.S. Did I mention that I borrowed some of this code... not sure where from... maybe a driver?:ahoy:

Link to comment
Share on other sites

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

 

  • Thanks 1
Link to comment
Share on other sites

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.  

 

 

 

  • Like 1
  • Haha 2
Link to comment
Share on other sites

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) :) 

 

  • Like 1
  • Haha 1
Link to comment
Share on other sites

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!🚙

;-)

  • Like 1
Link to comment
Share on other sites

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. ;)

 

  • Like 2
Link to comment
Share on other sites

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.

  • Like 1
Link to comment
Share on other sites

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.

 

Link to comment
Share on other sites

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. ;)

 

  • Like 1
Link to comment
Share on other sites

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?".   ;)

  • Like 1
Link to comment
Share on other sites

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?" ... 

  • Like 2
Link to comment
Share on other sites

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

 

 

Link to comment
Share on other sites

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

  • Like 1
  • Thanks 1
  • Haha 4
Link to comment
Share on other sites

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?

 

 

  • Like 1
Link to comment
Share on other sites

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. :)

 

Link to comment
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...