RISC-V
题目描述
汇编语言 (Assembly Language) 是用于电子计算机, 微处理器, 微控制器或其他可编程器件的低级语言, 可通过汇编器翻译成 CPU 能够直接识别的机器语言. 在不同的设备中, 汇编语言对应着不同的机器语言指令集, 因此不同平台之间的程序不可直接移植.
CPU 在运行时需要额外空间存储运算中产生的中间数据, 这个存储空间就是寄存器 (Register). 寄存器堆 (Register File, RF) 则是由一组寄存器组成的二维阵列, 在本题中, 可以将寄存器堆看作 32 个 unsigned 型变量, 用 unsigned rf[32] 表示. 初始状态下寄存器堆中所有寄存器的值均为 0.
CPU 在运行时还需要与外设进行通讯, 如内存, 硬盘, 键盘, 鼠标等. 本题中我们只考虑一个大小为 128 字节的内存 (Memory) 作为外设, 也将它看作 32 个 unsigned 型变量, 用 unsigned mem[32] 示. 初始状态下的内存数据由输入给出.
CPU 是通过一系列指令完成运算, 输入和输出. 常用的指令集包括 x86 指令集, RISC-V 指令集等. 本题中我们采用简化版的RISC-V指令集, 指令列表与指令格式如下, 其中 imm 为输入的整数, rs1, rs2, rd 为表示寄存器编号的整数, 取值范围为 0 ~ 31. 需要特别注意:
0号寄存器的值始终为0, 所有对0号寄存器的操作都不改变它的值. 如经过指令addi 0 0 114514后, 仍有rf[0] == 0, 而不是rf[0] == 114514.bltu为无符号比较运算符, 故在编程时请务必使用unsigned型变量来存储寄存器的值.
| 指令名称 | 指令格式 | 实现内容 |
|---|---|---|
| add | add rd rs1 rs2 |
rf[rd] = rf[rs1] + rf[rs2]; pc = pc + 1; |
| addi | addi rd rs1 imm |
rf[rd] = rf[rs1] + imm; pc = pc + 1; |
| sub | sub rd rs1 rs2 |
rf[rd] = rf[rs1] - rf[rs2]; pc = pc + 1; |
| subi | subi rd rs1 imm |
rf[rd] = rf[rs1] - imm; pc = pc + 1; |
| bne | bne rs1 rs2 imm |
if (rf[rs1] != rf[rs2]) pc = pc + imm; else pc = pc + 1; |
| beq | beq rs1 rs2 imm |
if (rf[rs1] == rf[rs2]) pc = pc + imm; else pc = pc + 1; |
| bltu | bltu rs1 rs2 imm |
if (rf[rs1] < rf[rs2]) pc = pc + imm; else pc = pc + 1; |
| jal | jal rd imm |
rf[rd] = pc + 1; pc = pc + imm; |
| jalr | jalr rd rs1 imm |
rf[rd] = pc + 1; pc = rf[rs1] + imm; |
| lw | lw rd rs1 imm |
rf[rd] = mem[ rf[rs1] + imm ]; pc = pc + 1; |
| sw | sw rs2 rs1 imm |
mem[ rf[rs1] + imm ] = rf[rs2]; pc = pc + 1; |
CPU 在运行时需要知道自己在执行哪条指令, 我们用程序计数器 (Program Counter, PC) 来表示. 本题中, 可以将 PC 设为代码行号, 当 PC 大于等于代码的总行数 n 时, 程序运行结束.
输入
输入共有 n + 2 行.
第 1 行为一个整数 n, 为指令总条数.
接下来的 n 行为 n 条指令, 对应的行号为 0 ~ n - 1.
第 n + 2 行为 32 个 10 进制整数, 对应初始状态下的内存数据.
保证所有输入均合法.
测试点 1 输入:
9
lw 1 0 0
lw 2 0 1
bltu 2 1 4
addi 3 1 0
addi 1 2 0
addi 2 3 0
sub 1 1 2
bne 1 2 -5
sw 1 0 2
114514 1919810 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0输出
输出共有 32 行.
使用大写 16 进制, 输出程序运行结束后所有的内存数据（即 32 个整数）, 不够 8 位则补 0.
测试点 1 输出:
0001BF52
001D4B42
00000002
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000提示
- 数据范围: $n\leq 10^{4}$, 不需要考虑运算中的溢出问题.
- 前 50% 测例为功能测试, 测试程序是否能够实现以上指令；后 50% 测例为性能测试, 测试程序是否能够在规定时间内给出正确的运行结果.
注意
上面的样例为第一个测试点. 对于非纯数字输入的题目, 有时会把样例作为第一个测试点以方便调试.
可以使用如下代码得到满足题意的输出.
int i;
for(i = 0; i < 32; i++)
printf("%08X\n", mem[i]);附加题
不计分, 感兴趣的同学可以尝试. 请利用以上指令设计一个排序器, 使其能对内存中的所有（32 个）元素进行排序, 并将排好序的数据写入内存中.