# Lab2: Bubble Sort in RISC-V RV32I[MA] emulator with ELF support
## C code
I think there is so bug in compiler. Initial steak pointer fo array is in 0, but 0 can't be substracted. Program can't run in correctly. To slove this bug, I spend a lot of time.

Finally,I set global pointer(0x15000) to replace declaration of array.

void _start()
{   
    int tmp;
    int c=0;
    //int arr[5];
    int* arr = (int*) 0x15000;
    arr[0] = 3;
    arr[1] = 5;
    arr[2] = 1;
    arr[3] = 2;
    arr[4] = 4;

    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4 - i; j++){
            if(arr[j] > arr[j + 1]){
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }

    volatile  int* tx = (volatile int*) 0x40002000;
   
    while (c < 5) {
        *tx = *arr;
        arr++;
        c++;
    }

}

## Compile into assembly code
Use -Os in command here.

00010054 <_start>:
   10054:	000157b7          	lui	a5,0x15
   10058:	00300713          	li	a4,3
   1005c:	00e7a023          	sw	a4,0(a5) # 15000 <__global_pointer$+0x3708>
   10060:	00500713          	li	a4,5
   10064:	00e7a223          	sw	a4,4(a5)
   10068:	00100713          	li	a4,1
   1006c:	00e7a423          	sw	a4,8(a5)
   10070:	00200713          	li	a4,2
   10074:	00e7a623          	sw	a4,12(a5)
   10078:	00015637          	lui	a2,0x15
   1007c:	00400713          	li	a4,4
   10080:	00e7a823          	sw	a4,16(a5)
   10084:	00400693          	li	a3,4
   10088:	00460893          	addi	a7,a2,4 # 15004 <__global_pointer$+0x370c>
   1008c:	00000713          	li	a4,0
   10090:	0280006f          	j	100b8 <_start+0x64>
   10094:	00271793          	slli	a5,a4,0x2
   10098:	00c78533          	add	a0,a5,a2
   1009c:	011787b3          	add	a5,a5,a7
   100a0:	00052583          	lw	a1,0(a0)
   100a4:	0007a803          	lw	a6,0(a5)
   100a8:	00b85663          	bge	a6,a1,100b4 <_start+0x60>
   100ac:	01052023          	sw	a6,0(a0)
   100b0:	00b7a023          	sw	a1,0(a5)
   100b4:	00170713          	addi	a4,a4,1
   100b8:	fcd74ee3          	blt	a4,a3,10094 <_start+0x40>
   100bc:	fff68693          	addi	a3,a3,-1
   100c0:	fc0696e3          	bnez	a3,1008c <_start+0x38>
   100c4:	00015737          	lui	a4,0x15
   100c8:	00072683          	lw	a3,0(a4) # 15000 <__global_pointer$+0x3708>
   100cc:	400027b7          	lui	a5,0x40002
   100d0:	00d7a023          	sw	a3,0(a5) # 40002000 <__global_pointer$+0x3fff0708>
   100d4:	00472683          	lw	a3,4(a4)
   100d8:	00d7a023          	sw	a3,0(a5)
   100dc:	00872683          	lw	a3,8(a4)
   100e0:	00d7a023          	sw	a3,0(a5)
   100e4:	00c72683          	lw	a3,12(a4)
   100e8:	00d7a023          	sw	a3,0(a5)
   100ec:	01072703          	lw	a4,16(a4)
   100f0:	00e7a023          	sw	a4,0(a5)
   100f4:	00008067          	ret

## Handwritten assembly code
Optimized one has less 75 rows than handwritten one.

.file	"bubble.c"
	.option nopic
	.text
	.align	1
	.globl	main
	.type	main, @function
main:
	#create stack
	addi	sp,sp,-48
	#save s0
	sw	s0,44(sp)
	#update s0
	addi	s0,sp,48

	#init arr[] to memory
	li	a5,3
	sw	a5,-48(s0)
	li	a5,5
	sw	a5,-44(s0)
	li	a5,1
	sw	a5,-40(s0)
	li	a5,2
	sw	a5,-36(s0)
	li	a5,4
	sw	a5,-32(s0)

	#init i to memory
	sw	zero,-20(s0)
	j	.L2
.L6:
	#init j to memory
	sw	zero,-24(s0)
	j	.L3
.L5:
	#load arr[ j ] to a4
	lw	a5,-24(s0)
	slli	a5,a5,2
	addi	a4,s0,-16
	add	a5,a4,a5
	lw	a4,-32(a5)

	#load arr[j+1] a5
	lw	a5,-24(s0)
	addi	a5,a5,1
	slli	a5,a5,2
	addi	a3,s0,-16
	add	a5,a3,a5
	lw	a5,-32(a5)
	
	#if arr[j + 1] > arr[j] 
	bge	a5,a4,.L4

	#load arr[j] a5
	lw	a5,-24(s0)
	slli	a5,a5,2
	addi	a4,s0,-16
	add	a5,a4,a5
	lw	a5,-32(a5)

	#store arr[j] to tmp
	sw	a5,-28(s0)

	#load arr[j+1] to a4
	lw	a5,-24(s0)
	addi	a5,a5,1
	slli	a5,a5,2
	addi	a4,s0,-16
	add	a5,a4,a5
	lw	a4,-32(a5)

	#arr[j] = arr[j+1]
	lw	a5,-24(s0)
	slli	a5,a5,2
	addi	a3,s0,-16
	add	a5,a3,a5
	sw	a4,-32(a5)

	#store tmp to arr[j+1]
	lw	a5,-24(s0)
	addi	a5,a5,1
	slli	a5,a5,2
	addi	a4,s0,-16
	add	a5,a4,a5
	lw	a4,-28(s0)
	sw	a4,-32(a5)
.L4:
	#j++
	lw	a5,-24(s0)
	addi	a5,a5,1
	sw	a5,-24(s0)
.L3:
	#check (j - i) < 4
	li	a4,4
	lw	a5,-20(s0)
	sub	a5,a4,a5
	lw	a4,-24(s0)
	blt	a4,a5,.L5

	#i++
	lw	a5,-20(s0)
	addi	a5,a5,1
	sw	a5,-20(s0)
.L2:
	#check i < 4
	lw	a4,-20(s0)
	li	a5,3
	bge	a5,a4,.L6

	#return
	li	a5,0
	mv	a0,a5
	lw	s0,44(sp)
	addi	sp,sp,48
	jr	ra

	.size	main, .-main
	.ident	"GCC: (GNU) 9.2.0"
	.section	.note.GNU-stack,"",@progbits

## Emulate Result
To print the result of bubblesort , I revise emu-rv32i.c.
The result of bubblesort in first row is correct.

Total:
23 jump
Branch Prediction has only 64.29% accuracy.

Because bubblesort use the way which compare with next element.
It's more hard to predict next element if smaller than current one.


## ELF file header