你好！本文章为该博客的第2篇文章！

本文章并不是对作业的题解，虽然可能会涉及若干题目的具体思路，但是文章重心是提供作者对课下作业所需技能知识的个人理解，希望读者能借此补足作业题目里缺失的思路。

以及，本文中的许多“规范”实际上是符合作者习惯并且在课程内行之有效的个人规范，可能存在不足之处，若读者发现问题，请批评指正。

P2课下作业内容介绍

本次课下作业的要求是，使用基于MIPS指令集的汇编语言，在Mars环境下完成一些程序。

具体来说，各题要求大致如下：

计算两个 $n\times n$ 的矩阵乘法。
判断一个长度为 $n$ 的字符串是否为回文串。
计算 $m_1\times n_1$ 矩阵与 $m_2\times m_2$ 卷积核的卷积结果。
按字典序输出 $1\sim n$ 的全排列。
（选做）输出一个 $n\times m$ 大小的迷宫从起点到终点不走回头路的方案数。
（选做）输出 $n$ 的阶乘，保证结果不超过 $1000$ 位。

拆出结构基础

总述

大概扫一眼各个题目的内容，我们可以归纳出来一些结构上的共性：

大量使用数组和二维数组；
需要进行大量的数组遍历；
部分题目涉及递归等复杂的函数调用，从而需要维护寄存器内的数据。

因此，接下来我们会针对这些结构进行一些讲述。

数组的实现

从数组到地址

首先，我们需要建立一个认识：只要我们有一片可以存数组的空间，再找到一个从数组下标到内存地址的一一对应关系，实际上就可以实现一个数组。

根据这样的想法，我们可以很容易的给出一个实现一维数组的方式：记 $size$ 为元素大小， $arr$ 为数组所在空间的首地址， $index$ 为待访问元素， $addr$ 为元素所在地址，则可以有 $addr=arr+index\times size$ 。也就是说，当我们想访问 arr[index] 的时候，我们就可以根据这个计算方式，得出这个元素所在的位置，从而对这个位置上的内存进行读写操作。

而对于高维数组来说，不论是怎样的数组，在内存中都是可以被拍扁处理的。

比如：一个很好想的做法就是，对于一个元素大小为 $4$ 字节的 $k$ 维数组 arr[d_1][d_2]...[d_k]，我们可以将其访问某个元素的下标 $id_1,id_2,\dots,id_k$ 映射到一个整数 $index = ((id_1+\dots)\times d_{k-1}+id_{k-1})\times d_k+id_k$ ，这样我们就把一个高维数组的问题转化成了一个一维数组的问题了。

从理论到打包使用

对于一维数组来说，我们可以打包一个宏来计算出元素地址：

.macro calc_addr(%addr, %arr, %index, %size)
    multu %index, %size
    mflo %addr
    addu %addr, %addr, %arr
.end_macro

如果可以确定要访问的是哪个数组的元素，那么也可以直接用内存读写指令里的立即数代替掉 addu 那一步。

当然，对于元素大小恰好是 $2^n$ 的情况，我们可以用一个 sll %addr, %index, n 来代替 multu mflo。

而对于高维数组，作者只在这里给出由课程组代码改的计算元素大小为 $4$ 字节二维数组的 $index$ 的宏：

.macro get_index(%dst, %row, %column, %rank)
    multu %row, %rank
    mflo %dst
    addu %dst, %dst, %column
.end_macro

循环过程描述的规范化

这一段主要是叙述一下如何用相对“规范”的方法描述一个循环，以for循环为例。

大致来说，我们会把一个循环分为如下几部分：初始化，终止条件，循环增量，循环体。如果用三个标签来切割的话，效果如下：

  # initialize
for_loop_begin:
  # set $t0 = end condition
  bne $t0, $0, for_loop_end 
  # loop body
  
  for_loop_next:
  # loop increment
  j for_loop_begin
for_loop_end:

举例来说，如果我们希望给一个元素大小为4字节的，数组大小为 $s0 的一维数组 arr 中的每个元素加1，则我们可以这样做：

li $t0, 0 #initialize, $t0 = i
for_loop_begin:
  bge $t0, $s0, for_loop_end # end_condition
  
  # loop body
  sll $t1, $t0, 2
  lw $t2, arr($t1)
  addu $t2, $t2, 1
  sw $t2, arr($t1)
  
  for_loop_next:
  add $t0, $t0, 1 # loop increment
  j for_loop_begin
for_loop_end:

函数调用时的数据维护

这一部分比较重要，如果没有把这一块规划好，调用函数的时候就很容易写乱。

具体来说，乱起来有以下几种情况：

调用函数前后，某些寄存器的值可能会发生改变，而程序员未注意到这一点，从而仍然使用原先的值。
入栈出栈次数不匹配，或者顺序错误。
函数内分配临时变量后，由于 $sp 的移动，导致临时变量寻址错误。

实际上，我们只想遵循这样几条原则：

调用函数后，需要某些寄存器的值被还原到调用前的状态。（如 $ra，以及调用函数时候的被覆盖的参数）
不使用额外申请的空间，仅用 $sp 和栈空间完成维护，并且调用函数前后 $sp 的值必然不变（即，函数调用前后栈内存储的元素个数不变）。
无论 $sp 如何变化，临时变量都能通过一个相对固定的寄存器进行访问。
需要维护的寄存器尽可能少。

基于这样一些原则，作者在此尝试给出一个规范：

我们认为调用函数前后，$0,$gp,$sp,$fp,$ra,$s0,$s1,...,$s7 的值不会发生改变，其余寄存器的值一定会改变。
除 $0,$gp,$sp 外，对于认为不会发生改变的寄存器，如果我们在函数内中需要对其进行修改，则应在函数开始处进行一次入栈，函数结尾处进行一次出栈，遵循先入后出的规则。同时，$ra 一定是第一个入栈的，$fp 入栈前一定仅有 $ra 入栈。
对于认为会发生改变的寄存器，如果在调用函数后仍然需要使用该寄存器内的值，则无论函数内部是否对其进行修改，都应该在调用函数前进行一次入栈，调用函数后进行一次出栈，遵循先入后出的规则。
如果需要用到临时变量，则在 $ra 入栈后，将当前 $fp 的值保存到栈中，再将 $sp 的值赋给 $fp，再将 $fp 入栈，再通过对 $sp 调整申请好所有临时变量的空间，此后再进行其他寄存器的入栈。访问临时变量时，通过 $fp 进行寻址。

实际上，第四条使用了一下栈帧的概念。

题目思路提示

01迷宫

可以意识到，这是一个需要递归的过程，递归内容为：从当前位置出发，试图搜索各个方向走到终点，若走到终点则给路径数加 $1$ 。

一种可行的想法是，我们先判断当前位置是否为终点（是的话直接修改路径数并退出函数），不是的话则先判断当前位置是否合法（在地图内，且当前格子未被走过且无遮挡），不合法则直接退出函数，合法则向四个方向均探查一遍，把周围四个点分别作为一组新的参数传入函数进行递归。

如果遵循“函数调用时的数据维护”一段里的规范的话，应该会写起来很顺利。

如果你采用的是在向四个方向均探查一遍时分别检查合法性的处理，则应该考虑把合法性判断作为一个单独的函数，而非写四遍。

高精度阶乘

首先，由题目可知，我们需要存储一个十分巨大的数，但每次与之相乘的数都很小（不超过 $1000$ ）。

因此，我们可以选择开一个数组 $digit$ ，从低位到高位依次存储单个十进制位。最低位设置为 $1$ ，同时，使用一个寄存器记录该大数的位数 $m$ （初始为 $1$ ）。

之后，我们依次用这个大数乘以从 $1$ 到 $n$ 的各个整数 $i$ 。具体来说，我们可以在每次计算开始记录一个进位 $carry = 0$ ，从第 $0$ 位到第 $m-1$ 位依次处理。处理到第 $j$ 位时，先令 $carry \leftarrow carry + i\times digit_j$ ，再将 $carry$ 除以 $10$ 的余数作为新的 $digit_j$ ，商作为新的 $carry$ 。同时我们注意到，这个过程中可能会因为进位而延长数位，所以当第 $m-1$ 位处理完后，如果 $carry>0$ ，则说明还需要进位，并且需要产生新的位，所以 $digit_m \leftarrow 0,m\leftarrow m+1$ 。

北航CO 2024 P2课下部分思路引导