Computer-Architecture/merge.asm at main · rithiksachdeva/Computer-Architecture · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
# merge.asm — Iterative bottom-up merge sort for 1024 words (RV32I, RARS).
# In: a0 = output buffer, a1 = input buffer. Lab spec also names a2 as scratch;
# this implementation merges into a0 without using a separate scratch base.

.globl merge

merge:
	addi sp, sp, -4
	sw ra, 0(sp)

	mv s9, a0
	mv s8, a1

	li t2, 0
	li t3, 1024
	li t4, 0
	li s1, 0
	li s2, 0
	li s3, 0
	li s4, 0

startingforloop:

	addi t4 t4 1 #size+1
	j sizelessthanN
topforlooppart2:
	li s1 0
	li t2 0
	j islowerlimitplussizelessthanN
whileloop1:
	add s5 s1 t4
	addi s5 s5 -1
	mv s2 s5
	addi s5 s2 1
	mv s3 s5
	add s5 s3 t4
	addi s5 s5 -1
	mv s4 s5
	blt s4 t3 whileloop2
	addi s4 t3 -1
	j whileloop2
ifinsidewhileloop2:
	slli s5 s3 2
	add a1 s8 s5
	lw s6 0(a1) #arr[j]
	sub a1 a1 s5

	slli s5 s1 2
	add a1 s8 s5
	lw s7 0(a1) #arr[i]
	sub a1 a1 s5

	bgt s7 s6 outputkplus1equalsinputjplus1x

	slli s5 s1 2
	add a1 s8 s5
	lw s6 0(a1) #arr[i++]
	sub a1 a1 s5
	addi s1 s1 1

	slli s5 t2 2
	add a0 s9 s5
	sw s6 0(a0) #temp[k++]
	sub a0 a0 s5
	addi t2 t2 1
	j whileloop2

outputkplus1equalsinputjplus1x:

	slli s5 s3 2
	add a1 s8 s5
	lw s6 0(a1) #arr[j++]
	sub a1 a1 s5
	addi s3 s3 1

	slli s5 t2 2
	add a0 s9 s5
	sw s6 0(a0) #temp[k++]
	sub a0 a0 s5
	addi t2 t2 1
whileloop2:
	bgt s1 s2 isIlehigherlimit1
	ble s3 s4 ifinsidewhileloop2
	j isIlehigherlimit1
outputkplus1equalsinputiplus1:

	slli s5 s1 2
	add a1 s8 s5
	lw s6 0(a1) #arr[i++]
	sub a1 a1 s5
	addi s1 s1 1


	slli s5 t2 2
	add a0 s9 s5
	sw s6 0(a0) #temp[k++]
	sub a0 a0 s5
	addi t2 t2 1

isIlehigherlimit1:
	ble s1 s2 outputkplus1equalsinputiplus1
jump1:
	j while3
outputkplus1equalsinputjplus1:

	slli s5 s3 2
	add a1 s8 s5
	lw s6 0(a1) #arr[j++]
	sub a1 a1 s5
	addi s3 s3 1


	slli s5 t2 2
	add a0 s9 s5
	sw s6 0(a0) #temp[k++]
	sub a0 a0 s5
	addi t2 t2 1

while3:
	ble s3 s4 outputkplus1equalsinputjplus1
lowerlimit1isequalto1plushigherlimit2:
	mv s1 s4
	addi s1 s1 1

islowerlimitplussizelessthanN:
	add s5 s1 t4
	blt s5 t3 whileloop1
anotherforloop:
	j klessthann
outputkplus1equalsinputi:
	slli s5 s1 2
	add a1 s8 s5
	lw s6 0(a1) #arr[i]
	sub a1 a1 s5


	slli s5 t2 2
	add a0 s9 s5
	sw s6 0(a0) #temp[k++]
	sub a0 a0 s5
	addi t2 t2 1

	addi s1 s1 1
klessthann:
	blt t2 t3 outputkplus1equalsinputi
	li s1 0
	j ilessthann
inputiequalsoutputi:
	slli s5 s1 2
	add a0 s9 s5
	lw s6 0(a0) #temp[i]
	sub a0 a0 s5

	slli s5 s1 2
	add a1 s8 s5
	sw s6 0(a1) #arr[i]
	sub a1 a1 s5

	addi s1 s1 1
ilessthann:
	blt s1 t3 inputiequalsoutputi
	add t4 t4 t4

sizelessthanN:
	blt t4 t3 topforlooppart2

end:
	lw ra, 0(sp)
	addi sp, sp, 4
	ret