homework2 quick sort

create_data.s

  .text
	.global	_start
	.code	16
	.syntax	unified
	.type	_start, function

_start:
	@ clear registers
	mov	r0, #0
	mov	r1, #0
	mov	r2, #0
	mov	r3, #0
	mov	r4, #0
	mov	r5, #0
	mov	r6, #0
	mov	r7, #0
	mov	r8, #0
	
	@ set args
	ldr	r0, =Data1
	ldr	r1, =Dest
	add r2, #16 @結局使わなかったけど、配列の要素数を表すためのオフセット		
	bl	main	@ jump to main function
_deadloop:
	b	_deadloop

	.section .rodata @ rodata section
Data1: @配列に格納する値 = { 4,8,5,2,6 }	
  .word	4
	.word	8
	.word	5
	.word	2
	.word	6
	.word	0
	.align

	.data	@ data section
Dest:
	.space	0x100		@ preserve 0x100 bytes
	.end

homework2.s

@  homework2.s
@	r0 : 所与の配列領域
@	r1 : 結果を格納するための配列領域
@	r3 : ピボット値
@	r4 : l pointer	
@	r5 : r pointer	
@	r6 : left most　配列の最も左のポインタ
@ r7 : right most 配列の最も右のポインタ
@	r8 : general purpose　汎用レジスタ
@	r10: freezing point　再帰処理脱出用のスタックポインタ値
@
	
	.text
	.global	main
	.code	16
	.syntax	unified
	.type	main, function

main:
	push {r0, r1, lr}
	mov r10,sp    @この時点でのSP値をr10に格納しておく
  push {r0, r1}

copy: @r0上では書き換えが出来ないので、配列をr1へいったん全部コピー。r3はダミー
  ldr r3, [r0]
	cbz r3, init
	str r3, [r1]
	add r0, #4
	add r1, #4
	b copy

init:	@始めて関数を呼び出す時の条件を整備

  pop {r0, r1}
	mov r6, r1		  @r6:left most = r1の0番目
	add r7, r1, #16	@r7:right most＝r1の4番目
　b recursion     @再帰処理の呼び出し（なくてもいいけど明示しとく。）

recursion:
	ldr r3,[r6]	@pivot <- [left] :pivot値の決定
	mov r4,r6	@l <- left        ：l を配列の最も左の値に
  mov r5,r7	@r <- right        :r を配列の最も右の値に
  b search_left               

search_left: @配列の左から、ピボット以上の値を探し出す
  cmp r4,r7	@ l <=> right
	bge search_right @next
	ldr r8,[r4]	@ r8 <- [l]
	cmp r8,r3	@ [l] <=> [p]
	bge search_right  @ exitloop if [l] > [p]
	add r4, #4		@ loop l++
	b search_left

search_right: @配列の右から、ピボット以上の値を探し出す
	cmp r6,r5	@left <=> r
	bge mainloop @exit
	ldr r8,[r5]	@ r8 <- [r]
	cmp r8,r3	@ [r] <=> [r3]
	ble mainloop	@exit loop if [r] < [p]
	sub r5, #4		@loop r--
	b search_right	@

mainloop:　@上記で見つかった点swap、パーティショニング完了したら再帰呼び出し。
  cmp r4, r5		@ cmp l,r
	bge l_rec_call	@ if[l]>=[r] exit loop
	ldr	r8,[r4]		
	ldr	r9,[r5]		@swap [r4] <-> [r5]
	str r8,[r5]		
	str	r9,[r4]
	add r4, #4		@l++
	sub r5, #4		@r--
	b search_left		@loop

l_rec_call: @左側の部分配列に対して再帰呼び出し
	@	r6(leftmost:need) : left  
	@	r7(rightmost:need): l-1
	mov r8,#0	
	sub r8, r4, #4	@ r8 = l-1
	cmp r6, r8		@ left <=> l-1
	bge r_rec_call	@if left >= l-1 : cond unfulfill. go next
	push {r5,r7,lr}
	mov r7, r8
	@else: call recursively and come back
	bl recursion
	pop {r5,r7,lr}

r_rec_call:  @右側の部分配列に対して再帰呼び出し
	@	r6(leftmost:need) : r+1  
	@	r7(rightmost:need): right
	mov r8, #0
	add r8, r5, #4	@r8 : r+1
	cmp r6, r7		@r+1 <=> right
	bge finish		@else finish
	mov r6,r8
	push {lr}
	bl recursion
	pop {lr}

finish: @終わり処理
	cmp sp,r10
	beq exit
	mov pc,lr

exit:
	pop	{r0, r1, pc}
	.end