BUAA-CO-p2-课下
发表更新13 分钟读完 (大约1997个字)

BUAA-CO-p2-课下

T1 矩阵乘法

T3 卷积计算

这俩题都是矩阵计算，纯粹的for循环加上一点累加。写的时候最重要的是搞清楚每个for要循环几次，用哪个变量控制总次数，尤其这个卷积，要不然怎么死的都不知道

为了避免直接直接抄代码，我把宏定义和.data去掉了（

T1
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
.text
		getInt($s0)					# s0 = n
	
		li		$t0, 0				# t0 = i
	A_i:
		beq 		$t0, $s0, end_A_i
		li		$t1, 0			# t1 = j
	A_j:
		beq 		$t1, $s0, end_A_j	# j != n
		getInt($t3)
		getindex($t4, $s0, $t0, $t1)
		sw		$t3, A($t4)
		addi		$t1, $t1, 1	# j++
		j		A_j
	end_A_j:
		addi		$t0, $t0, 1	# i++
		j		A_i
	end_A_i:
		
		li		$t0, 0		# i = 0
	B_i:
		beq		$t0, $s0, end_B_i
		li		$t1, 0
	B_j:
		beq		$t1, $s0, end_B_j
		getInt($t3)
		getindex($t4, $s0, $t0, $t1)
		sw		$t3, B($t4)
		addi		$t1, $t1, 1
		j		B_j
	end_B_j:
		addi 	$t0, $t0, 1
		j		B_i
	end_B_i:
		
		
		li		$t0, 0			# t0 = i
	switch_row:
		beq		$t0, $s0, end_row
			
		li		$t2, 0			# t2 = col
	switch_col:
		beq		$t2, $s0, end_col			# col over
		li		$s1, 0			# s1 is sum
		li		$t1, 0
	switch_row_num:
		beq		$t1, $s0, end_num
		getindex($t3, $s0, $t0, $t1)		# A[i][j]
		getindex($t4, $s0, $t1, $t2)		# B[j][col]
		lw		$t5, A($t3)					# t5 = A[i][j]
		lw		$t6, B($t4)					# t6 = B[j][col]
		mul		$t7, $t5, $t6
		add		$s1, $s1, $t7
		addi		$t1, $t1, 1		# j++
		j switch_row_num
	end_num:
		getindex($t8, $s0, $t0, $t2)
		sw		$s1, C($t8)
		addi		$t2, $t2, 1		# col++
		j 		switch_col
	end_col:
		addi		$t0, $t0, 1		# i++
		j		switch_row
	end_row:
	
		li		$t0, 0			# t0 = i
	out_i:
		beq		$t0, $s0, end_out_i
		li		$t1, 0			# t1 = j
	out_j:
		beq		$t1, $s0, end_out_j
		getindex($t2, $s0, $t0, $t1)
		lw		$t3, C($t2)
		printInt($t3)
		printSpace
		addi		$t1, $t1, 1
		j		out_j
	end_out_j:
		printEnter
		addi		$t0, $t0, 1
		j		out_i
	end_out_i:
		end
T3
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
.text
	getInt($s0)			# s0 = m1
	getInt($s1)			# s1 = n1
	getInt($s2)			# s2 = m2
	getInt($s3)			# s3 = n2
	
	li		$t0, 0		# t0 = i
A_i:
	beq		$t0, $s0, end_A_i
	li		$t1, 0		# t1 = j
A_j:
	beq		$t1, $s1, end_A_j
	getIndex($t2, $s1, $t0, $t1)
	getInt($t3)
	sw		$t3, A($t2)
	addi		$t1, $t1, 1
	j		A_j
end_A_j:
	addi		$t0, $t0, 1
	j		A_i
end_A_i:

	li		$t0, 0
B_i:
	beq		$t0, $s2, end_B_i
	li		$t1, 0					# t1 = j
B_j:
	beq		$t1, $s3, end_B_j
	getIndex($t2, $s3, $t0, $t1)
	getInt($t3)
	sw		$t3, B($t2)
	addi		$t1, $t1, 1
	j		B_j
end_B_j:
	addi	$t0, $t0, 1
	j		B_i
end_B_i:

	sub		$s4, $s0, $s2
	addi		$s4, $s4, 1				#s4 = m1-m2+1
	sub		$s7, $s1, $s3			# s7 = n1-n2
	addi		$s5, $s7, 1				#s5 = n1-n2+1
	
	li		$t0, 0				# t0 = i
i:
	beq		$t0, $s4, end_i
	li		$t1, 0				# t1 = j
j:	
	beq		$t1, $s5, end_j
	li		$t2, 0				# t2 = k
	li		$s6, 0				#s6 = sum
k:	
	beq		$t2, $s2, end_k
	li		$t3, 0				# t3 = l
l:
	beq		$t3, $s3, end_l
	add		$t4, $t0, $t2		# t4 = i+k
	add		$t5, $t1, $t3		# t5 = j+l
	getIndex($t6, $s1, $t4, $t5)
	getIndex($t7, $s3, $t2, $t3)
	lw		$t6, A($t6)			# t6 = A[i+k][j+l]
	lw		$t7, B($t7)			# t7 = B[k][l]
	mul		$t6, $t6, $t7
	add 	$s6, $s6, $t6
	
	addi		$t3, $t3, 1
	j		l
end_l:
	addi		$t2, $t2, 1
	j		k
end_k:
	getIndex($t8, $s5, $t0, $t1)
	sw		$s6, C($t8)
	addi		$t1, $t1, 1
	j		j
end_j:
	addi		$t0, $t0, 1
	j		i
end_i:

	li 		$t0, 0
c_i:
	beq		$t0, $s4, c_end_i
	li		$t1, 0
c_j:
	beq		$t1, $s5, c_end_j
	getIndex($t2, $s5, $t0, $t1)
	lw		$t3, C($t2)
	printInt($t3)
	la		$a0, space
	li		$v0, 4
	syscall
	addi		$t1, $t1, 1
	j		c_j
c_end_j:
	la		$a0, enter
	li		$v0, 4
	syscall
	addi		$t0, $t0, 1
	j		c_i
	
c_end_i:
	li		$v0, 10
	syscall

T2 回文串判断

一维数组跟二维比起来真是小巫见大巫了…

从两头开始判断，如果碰到a[i] != a[n-1-i]就把output置0

T2
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
.text
 	getint($s0)			# s0 is n
 	
 	li		$t0, 0		# t0 = i
in_i:
	beq		$t0, $s0, end_i
	getindex($t1, $t0)	#str[i]
	getchar($t2)		# char
	sw		$t2, str($t1)
	addi 		$t0, $t0, 1
	j 		in_i
end_i:
 	
 	li		$t0, 0			#t0 = i
 	move		$t1, $s0
 	addi		$t1, $t1, -1	#t1 = j
 	li		$s2, 1			# s2 = !error
while:
	bgt 	$t0, $t1, end_while
	
	getindex($t2, $t0)
	getindex($t3, $t1)
	lw		$t4, str($t2)
	lw		$t5, str($t3)
	beq		$t4, $t5, true
false:
	li		$s2, 0
	j		end_if
true:
	
end_if:
	
	addi		$t0, $t0, 1
	addi 		$t1, $t1, -1
	j		while
end_while:
 	printint($s2)
 	end

T4 全排列

经典的递归，正好借此题复习一下汇编中递归的写法。

个人非常不喜欢类似以下的写法，感觉非常抽象

1
2
3
4
lw		$a3, 4($sp)
lw		$a2, 8($sp)
lw		$a1, 12($sp)
lw		$ra, 16($sp)

为避免此类写法，可以添加宏定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
.macro push(%src)
	addi		$sp, $sp, -4
	sw		%src, 0($sp)
.end_macro

.macro pop(%src)
	lw		%src, 0($sp)
	addi		$sp, $sp, 4
.end_macro

#实例：
			push($ra)
			push($t0)
			push($t1)
#do something
			pop($t1)
			pop($t0)
			pop($ra)

另外，如何判断哪些函数需要入栈，哪些不需要呢？如果在递归前与递归后，某一变量均需要被使用，那么需要将其入栈以免被破坏。

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
.text
	getInt($s0)					# s0 = n
	li			$t0, 0
for_init:
	beq				$t0, $s0, end_init
	getindex($t1, $t0)
	li			$t2, 0
	lw			$t2, array($t1)
	lw			$t2, symbol($t2)
	addi		$t0, $t0, 1
	j			for_init
end_init:
	li			$a0, 0
	jal				func
	li			$v0, 10
	syscall

func:
	push($ra)
	push($t0)
	push($t1)

	move			$t0, $a0		#t0 = index
	blt				$t0, $s0, end_if #index < n branch
if:								# index >= n
	li			$t1, 0			# t1 = i
for_i_1:
	beq				$t1, $s0, end_for_1
	getindex($t2, $t1)
	lw			$t3, array($t2)
	printInt($t3)
	printSpace
	addi			$t1, $t1, 1
	j			for_i_1
end_for_1:
	printEnter
	j 			end_func
	

end_if:


	li			$t1, 0			# t1 = i
for_i_2:
	beq				$t1, $s0, end_for_2
	getindex($t2,$t1)
	lw			$t2, symbol($t2)
	bnez			$t2, end_if_2
else:							# symbol[i] == 0
	addi			$t2, $t1, 1		# t2 = i + 1
	getindex($t3, $t0)			# t3 = [index]
	sw			$t2, array($t3)	# array[index] = i+1
	li			$t2, 1			# t2 = 1
	getindex($t3, $t1)			# t3 = [i]
	sw			$t2, symbol($t3)	#symbol[i] = 1
	addi			$a0, $t0, 1		# a0 = index + 1
	jal				func			# func(a0)
	li			$t2, 0			# t2 = 0
	getindex($t3, $t1)			# t3 = i
	sw			$t2, symbol($t3)	#symbol[i] = 0
end_if_2:
	addi			$t1, $t1, 1
	j			for_i_2
end_for_2:

#return
end_func:
	pop($t1)
	pop($t0)
	pop($ra)
	jr			$ra

Others

多说几句：

  • 就个人的debug经验来说，循环末尾的j和函数末尾的jr比较容易忘；

    如果是改c语言代码，在所有return和函数末尾，都需要jr和pop

  • 如果输出了异常大的数（类似地址），检查move $a0, $xx是否写对了；

  • 注释一定要写，要不然明天就看不懂自己写了什么

  • 对于for或者while循环，建议先把循环体写了，避免后面写晕了

for_loop
1
2
3
4
5
6
7
8
9
10
11
	getInt($s0)						# s0 = n
	li		$t0, 0					# t0 = i
for_loop:
	beq		$t0, $s0, end_for		# i < n

	# 循环体内

	addi		$t0, $t0, 1
	j		for_loop
end_for:
	# over
double_for
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	getInt($s0)						# s0 = n
	getInt($s1)						# s1 = m
	
	li	$t0, 0					# t0 = i
i:
	beq	$t0, $s0, end_i
	li	$t1, 0					# t1 = j
j:	
	beq	$t1, $s1, end_j

	# do something

	addi	$t1, $t1, 1				# j++
	j	j
end_j:
	addi	$t0, $t0, 1				# i++
	j	i
end_i:
	# over
  • 如果要打印存储内存中的字符，可以按如下操作
1
2
3
4
5
6
7
8
.data
	arr:		.space 40
.text
	# 假设arr中存储了要输出字符的ascii码值
	getIndex($t1, $t0)		# t1 = [i]
	lw		$a0, arr($t1)
	li		$v0, 11
	syscall

Hanoi

C语言样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
void move(int id, char from, char to) {
  printf("move disk %d from %c to %c\n", id, from, to);
}
void hanoi(int base, char from, char via, char to) {
  if (base == 0) {
      move(base, from, via);
      move(base, via, to);
      return;
  }
  hanoi(base - 1, from, via, to);
  move(base, from, via);
  hanoi(base - 1, to, via, from);
  move(base, via, to);
  hanoi(base - 1, from, via, to);
}
int main() {
  int n;
  scanf("%d", &n);
  hanoi(n, 'A', 'B', 'C');
  return 0;
}

改编时可以将字符串打印和函数传参的过程写成宏，让你的主函数看起来规整一些

另外，传参传参，$a0-$a3寄存器中的数值在函数体里还是放到$t0等寄存器中，并且入栈出栈只需要操作临时寄存器即可

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
.macro init
	move	$a0, $s0		# base
	la	$a1, A
	la	$a2, B
	la	$a3, C
.end_macro

.macro getInt(%des)
	li	$v0, 5
	syscall
	move	%des, $v0
.end_macro

.macro push(%src)
	addi	$sp, $sp, -4
	sw	%src, 0($sp)
.end_macro

.macro pop(%des)
	lw	%des, 0($sp)
	addi	$sp, $sp, 4
.end_macro

.macro hanoi(%base, %from, %via, %to)
	move	$a0, %base
	move	$a1, %from
	move 	$a2, %via
	move	$a3, %to
	jal		hanoi
.end_macro

.macro printf(%id, %from, %to)
	la	$a0, str1
	li	$v0, 4
	syscall
	move	$a0, %id
	li	$v0, 1
	syscall
	la	$a0, str2
	li	$v0, 4
	syscall
	move	$a0, %from
	li	$v0, 4
	syscall
	la	$a0, str3
	li	$v0, 4
	syscall
	move	$a0, %to
	li	$v0, 4
	syscall
	la	$a0, enter
	li	$v0, 4
	syscall
.end_macro

.data
	A:	.asciiz "A"
	B:	.asciiz "B"
	C:	.asciiz "C"
	str1:	.asciiz "move disk "
	str2:	.asciiz " from "
	str3:	.asciiz " to "
	enter:  .asciiz "\n"
.text
	
	getInt($s0)
	
	init
	jal		hanoi
	li		$v0, 10
	syscall
hanoi:
	push($ra)
	push($t0)
	push($t1)
	push($t2)
	push($t3)
	push($t4)
	move	$t0, $a0
	move	$t1, $a1
	move	$t2, $a2
	move	$t3, $a3
	bnez	$t0, not_zero
	# base == 0
	printf($t0, $t1, $t2)
	printf($t0, $t2, $t3)
	# return
	pop($t4)
	pop($t3)
	pop($t2)
	pop($t1)
	pop($t0)
	pop($ra)
	jr		$ra
	
not_zero:
	addi	$t4, $t0, -1		# t4 = base-1
	hanoi($t4, $t1, $t2, $t3)
	printf($t0, $t1, $t2)
	hanoi($t4, $t3, $t2, $t1)
	printf($t0, $t2, $t3)
	hanoi($t4, $t1, $t2, $t3)
	
	pop($t4)
	pop($t3)
	pop($t2)
	pop($t1)
	pop($t0)
	pop($ra)
	
	jr		$ra

BUAA-CO-p2-课下

http://wtxyz.com/2024/10/15/CO-p2-afterclass/

作者

OWPETER

发布于

2024-10-15

更新于

2024-12-02

许可协议

#

评论

关注我

目录

标签

CO14
Math1

链接

最新文章

归档

订阅更新

follow.it

×