アセンブラでクイックソート

職業訓練の中でアセンブラのプログラミングをやった。課題で作ったプログラムをさらす。
プログラムの内容はアルゴリズムの定番、ソートのプログラム。
バブルソートと選択ソート、クイックソートの３パターンを作成し、今回のはクイックソート。

プロセッサはルネサステクノロジ社の SH-3 を使った。

クイックソートは自分自身を再帰呼出しをする。
そのときに、元の引数をメモリに退避し、帰ってきたときに復帰させる必要がある。
その退避と復帰のタイミングで結構悩んだ。

;******************************************************************
;	課題３：並び替えプログラム１      FILE NAME:Kadai3.src
;	H'8C00-1200番地に、39,62,55,24,76,17,43,97,6,83の数字がセットしてある。
;	この数字郡を小さい順に並び換えるプログラムを考えなさい。
;	
;******************************************************************
STACK_SIZE	.EQU	H'400

        .export _MAIN,_STACK_BOTTOM
;
       .section MAIN,CODE,ALIGN=4		
_MAIN: ;プログラムを考えなさい。

    MOVA   DATA, R0
    
    MOV    R0, R1
    MOV    R0, R2
    ADD    #(10 * 4), R2

    BSR    QSORT
    NOP

    BRA PEND
    NOP


;;**************************************************
;; quick sort
;;       R0 = pivot = mem[left + right / 2]; save PR
;;   arg.R1 = left
;;   arg.R2 = right
;;       R3 = i (init: left ), R13 = mem[i]
;;       R4 = j (init: right), R14 = mem[j]
;;       R5 = temporary
;; URL: http://www1.cts.ne.jp/~clab/hsample/Sort/Sort9.html
;;**************************************************
QSORT:
 
    MOV.L  R1 , @-R15
    MOV.L  R2 , @-R15
    STS    PR , R0
    MOV.L  R0 , @-R15
        
    MOV    R1, R3
    MOV    R2, R4

    MOV    R4, R0
    SUB    R3, R0
    SHLR   R0
    ADD    R3, R0
    MOV  #H'FC, R10
    AND   R10, R0
    MOV   @R0, R0

LOOP_A:
    LOOP_1:
        MOV   @R3, R13
        CMP/GT R13, R0
        BF LOOP_1_BREAK
        NOP

        ADD   #04, R3
        BRA LOOP_1
        NOP
    LOOP_1_BREAK:

    LOOP_2:
        MOV   @R4, R14
        CMP/GT R0, R14
        BF LOOP_2_BREAK
        NOP

        ADD   #-4, R4
        BRA LOOP_2
        NOP
    LOOP_2_BREAK:

        CMP/HS R4, R3
        BT LOOP_A_BREAK
        NOP

        MOV    R14, @R3
        MOV    R13, @R4

        ADD   #+4, R3
        ADD   #-4, R4

        BRA LOOP_A
        NOP
LOOP_A_BREAK:

    MOV    R3, R5
    ADD   #-4, R5

    ;; left(R1) < i-1(R5) = i-1(R5) > left(R1)
    CMP/HI R1, R5
    BF  SKIP_1
    NOP

    ;; BT
    MOV.L   R2  , @-R15
    MOV R5, R2
    BSR QSORT
    NOP
    MOV.L  @R15+,   R2        

SKIP_1:
    MOV R4, R5
    ADD #4, R5

    ;; j+1(R5) < right(R2) = right(R2) > j+1(R5)
    CMP/HI R5, R2
    BF SKIP_2
    NOP

    ;; BT
    MOV.L   R1  , @-R15
    MOV R5, R1
    BSR QSORT
    NOP
    MOV.L  @R15+,   R1

SKIP_2:

RETURN:
        
    MOV.L  @R15+, R0
    LDS    R0, PR
    MOV.L  @R15+, R2
    MOV.L  @R15+, R1
        
    RTS
    NOP

PEND:
	
;
LOOP:	BRA	LOOP
	NOP


	.ALIGN	4
STACK_BOTTOM_A:
	.DATA.L	_STACK_BOTTOM
	;
	.ORG	H'200
        
;並び替えられるデータ
DATA:	.DATA.L 39,62,55,24,76,17,43,97,6,83

;***********************************************************

;		STACK	AREA

;***********************************************************

	.SECTION STACK,STACK,ALIGN=4		
	.RES.B	STACK_SIZE
_STACK_BOTTOM:

 	.END