如何在 MIPS 中反转多行字符串的行顺序?
How do I reverse the line order of a multi-line string in MIPS?
我有一条多行消息,格式为:
.data
msg:
.ascii "aYZ B"
.byte 10
.ascii "234"
.byte 10
.ascii "b cd A"
.byte 10
而且我需要颠倒打印行的顺序,以便:
aYZ B -------------- b cd A
234 ----变成--- 234
b cd A -------------- aYZ B
到目前为止我的总体思路是将第一个字符的地址压入堆栈,然后遍历消息(消息的基地址+偏移量计数器)并立即压入每个字符的地址在 '\n' char (.byte 10) 之后进入堆栈('\n' char + 1 的索引)。
然后,我将能够以相反的顺序将每行中的第一个字母弹出堆栈。
我正在努力解决的问题是如何在循环遍历原始消息时对其进行修改。我应该以相反的顺序构建一个新的消息吗?如果是这样,如何?我猜我会为此使用字符串连接?
最后,如何打印该消息? (我可以使用系统调用 4,但我需要将整个消息存储在一个标签中)。
编辑:
所以我设法整合了一个解决方案并且 几乎 正常工作。 它有一个小错误:消息的最后一行没有单独打印,它只是在倒数第二行之后立即打印。
如果有人知道如何解决这个小问题,我很想知道如何解决。
.data
key: .byte 1
msg:
.ascii "ayZ B"
.byte 10
.ascii "234"
.byte 10
.ascii "b cD a"
.byte 10
.text
main:
jal reverseLinesAndPrint
# Exit Program
li $v0, 10
syscall
reverseLinesAndPrint: # $s3 contains address of last char, $s0 contains offsets for both front and back, but must be reset before using for back
li $s0, 0 # RESET value of msg position offset index to iterate from beginning again
lineLoop:
add $s1, $t0, $s0 # Set $s1 equal to the base address of msg ($t0) + the position offset index ($s0)
lb $s2, ($s1) # Deref. and move the current char into s2 for checking
bne $s2, $zero, notLastChar # If the current char is not the last char in the msg, keep looping
subi $s3, $s1, 1 # Subtract 1 from the ADDRESS of $s1 to get the last char ('\n') before the NULL Terminator and store it in $s3
j lastCharIndexFound # Exit the loop by jumping past it
notLastChar:
addi $s0, $s0, 1 # Increment the position offset index
j lineLoop
lastCharIndexFound: # We now have the address of the last valid char in message (always '\n') stored in $s3
li $s0, 0 # RESET value of msg position offset index to iterate from ending this time
reverseLineLoop:
sub $s1, $s3, $s0 # This time, we are going to subtract from the starting address so we can iterate backwards over msg
bne $t0, $s1, notFirstChar # If we iterate all the way to the very first char in msg, exit the loop
li $v0, 4 # Since the first char doesn't have a '\n' char, we have to manually print
move $a0, $s1
syscall
j exit
notFirstChar:
lb $s2, ($s1) # Deref. and move the current char into s2 for checking
bne $s2, 10, notNLChar # If we find a '\n' char, we need to do some logic
li $v0, 4 # First we need to call a syscall to print string (it will stop on the previous '\n' which is now NULL)
move $a0, $s1
syscall
sb $zero, ($s1) # Second, we need to replace that current '\n' char with NULL
notNLChar: # If the current char is not '\n', keep looping
addi $s0, $s0, 1 # Increment the offset
j reverseLineLoop # Jump to next iteration
exit:
jr $ra # Jump back to main
我认为您在前行中使用换行符将其与您之前打印的行分开。这是一个聪明的想法,比只打印行(没有前面的换行符)更有效。否则,您必须进行单独的打印单字符系统调用,例如 syscall
和 $v0 = 11
/ $a0 = '\n'
(MARS system calls)
这意味着您的输出类似于 "\nline3"
然后 "\nline2"
,等等。将光标留在每行的末尾。
但是您需要对最后一行(输入字符串的第一行)进行特殊处理,因为它之前没有 \n
。你已经 是 特殊外壳,所以只需在它之前手动打印一个 \n
,作为前一行的结尾,使用 print-char 系统调用。
另一种方法可能是在换行符之后的字符上存储一个0
,位于1($s1)
,所以当您稍后到达此行的开头时,您可以将其打印为 "line2\n"
,包括末尾的换行符。 (我的版本包括在下面。)
特殊情况成为输入的最后一行(输出的第一行),但如果你有一个以 0 结尾的 C 风格隐式长度,那么在换行符之后存储一个 0
字节实际上是可以的细绳。那里已经有一个,所以你可以在进入外循环时跳过它,或者如果不这样做更方便。
不修改数据:write(1, line, length)
MARS has a write()
system call ($v0=15
) 采用指针 + 长度,因此您不需要以 0 结尾的字符串。完全像 POSIX write(int fd, char *buf, size_t len)
。文件描述符 $a0 = 1
在 MARS4.3 及更高版本中是标准输出。
当你找到一个换行符时,你可以记录那个位置并继续循环。当你找到另一个时,你可以做 subu $a2, $t1, $t0
($a2 = end - start) 得到一个长度,并设置 $a1
指向换行符之后的字符。
因此您可以打印您选择的块,而不必破坏输入数据,使其可用于只读输入,或者无需制作副本以销毁您以后需要的东西。
其他东西/代码审查:
你的代码很奇怪;您调用 reverseLinesAndPrint
时没有在 main 的寄存器中放置指针和长度或结束指针,那么为什么要将它作为一个单独的函数呢?不可重复使用。
通常的做法是在 ASCII 数据块的末尾放置另一个标签,这样您就可以将该地址放入寄存器中,而无需扫描字符串来查找长度。 (特别是因为你没有明确地在字符串末尾有一个 0
字节来终止它。有一个是因为你没有在后面放置任何其他数据,而 MARS 在数据和代码之间留下了一个间隙当您使用将数据段的起始地址放在地址 0 的内存模型时。)
而你甚至从未使用过 la $reg, msg
。您似乎将其地址硬编码为 0
?你读了 $t0
而没有先初始化它。 MARS 开始时所有寄存器都清零。 (因此可能会错过这样的错误,因为这是您选择的内存布局的有效地址。)
在正常的 MIPS 调用约定中,$s
寄存器是调用保留的 ("saved"),也就是非易失性的。但是您的函数将它们用作没有 saving/restoring 的临时对象。使用 $t
寄存器(以及 $a0..3 和 $v0..1)是正常的。
您的循环效率低下:您可以将条件分支放在底部,如 do{}while()
。您编写循环的方式非常笨拙,每次循环迭代涉及 2 个分支(包括无条件循环分支)。或者 3 用于您需要检查 \n
和 p == end
.
的搜索循环
// your loops are over-complicated like this:
do {
loop body;
if (p == end) { // conditional branch over the loop epilogue
stuff; // put this after the loop instead of jumping over it inside the loop
goto out;
}
counter increment;
} while(1);
out:
另外:在某处写一段注释,说明每个寄存器的用途。对于某些人来说,它可以在初始化寄存器的指令上。
总的来说,您的评论非常好,主要是在更高层次上描述了正在发生的事情,而不是您已经可以从实际说明中看到的 "add 1 to $s0" 之类的东西。
这是我的做法
我使用了打印后覆盖一行的第一个字符的想法。这是 跟在 换行符之后的字节。所以当我们打印行时,它们就像 line2\n
而不是 \nline2
.
我还在 msg
的末尾放置了一个标签,而不是使用 strlen 循环。如果您要向前遍历字符串,是的,您应该在稍后保存工作时将指针保存在某个地方(例如在堆栈上),就像您最初想的那样。但是对于 assemble-time-constant 字符串,我们可以让 assembler 告诉我们它在哪里结束。我还将这些行打包到一个 .ascii
字符串中,以使源代码更加紧凑。我添加了一个明确的 .byte 0
终止符(而不是 .asciiz
),所以我可以在终止符上而不是之后添加标签。
我当然使用指针,而不是索引,所以我不需要 add
在循环内进行索引。我使用 lbu
以防零扩展比符号扩展到 32 位更有效。我宁愿将 char 值视为从 0..255 到 -128..127 的小整数。并不是说我对它们做任何带符号的比较,只是为了相等。
我使用了 addiu
因为我不想在指针数学上陷入有符号溢出。使用 add
而不是 addu
的唯一原因是陷入有符号溢出。
内部循环仍然需要 2 个条件分支来检查两个终止条件,但这是一个示例,说明您可以通过仔细规划来制作这样的循环是多么紧凑和高效。
.data
msg:
.ascii "ayZ B\n234\nb cD a\n"
endmsg: # 0 terminated *and* we have a label at the end for convenience.
.byte 0
.text
main:
la $a0, endmsg
la $a1, msg
jal reverseLinesAndPrint # revprint(end, start)
li $v0, 10
syscall # exit()
reverseLinesAndPrint:
# $a0 = end of string. We assume it's pointing at a '[=11=]' that follows a newline
# $a1 = start of string
# $t2 = tmp char
# we also assume the string isn't empty, i.e. that start - end >= 2 on function entry.
# the first char the inner loop looks at is -2(end)
#move $t0, $a0 # instead we can leave our args in a0, a1 because syscall/v0=4 doesn't modify them
lines:
findNL_loop: # do { // inner loop
addiu $a0, $a0, -1 # --p
beq $a1, $a0, foundStart # if(p==start) break
lbu $t2, -1($a0) # find a char that follows a newline
bne $t2, '\n', findNL_loop # }while(p[-1] != '\n');
# $a0 points to the start of a 0-terminated string that ends with a newline.
foundStart:
li $v0, 4
syscall # fputs(p /*$a0*/, stdout)
sb $zero, ($a0) # 0-terminate the previous line, after printing
bne $a0, $a1, lines # } while(!very start of the whole string)
jr $ra
已测试并使用您的数据。没有针对诸如第一行为空的极端情况进行测试,尽管它确实适用于最后一行为空。我想我在所有情况下都避免在第一个字符之前阅读(除了违反注释中的先决条件的太短输入。如果你想处理它们,你可以在进入循环之前检查它们。)
注意bne $t2, 10, target
是一个伪指令。如果我要进行更多优化,我会用 li
将 10
提升到 $t3
或其他东西的循环之外,而不是让 assembler 设置该常量在每次迭代的寄存器中。 li $v0, 4
相同 - 该系统调用没有 return 值,因此它甚至不会破坏 $v0
.
在寻址模式中使用像 -1($a0)
这样的偏移量是 "free" - 该指令有 16 位立即位移,所以我们不妨使用它而不是单独的指针数学。
我无缘无故地使用 $t2
而不是 $t0
,只是为了让我使用的每个 reg 都有一个唯一的编号,以便使用 MARS 小字体的人类可读性。
我有一条多行消息,格式为:
.data
msg:
.ascii "aYZ B"
.byte 10
.ascii "234"
.byte 10
.ascii "b cd A"
.byte 10
而且我需要颠倒打印行的顺序,以便:
aYZ B -------------- b cd A
234 ----变成--- 234
b cd A -------------- aYZ B
到目前为止我的总体思路是将第一个字符的地址压入堆栈,然后遍历消息(消息的基地址+偏移量计数器)并立即压入每个字符的地址在 '\n' char (.byte 10) 之后进入堆栈('\n' char + 1 的索引)。
然后,我将能够以相反的顺序将每行中的第一个字母弹出堆栈。
我正在努力解决的问题是如何在循环遍历原始消息时对其进行修改。我应该以相反的顺序构建一个新的消息吗?如果是这样,如何?我猜我会为此使用字符串连接?
最后,如何打印该消息? (我可以使用系统调用 4,但我需要将整个消息存储在一个标签中)。
编辑:
所以我设法整合了一个解决方案并且 几乎 正常工作。 它有一个小错误:消息的最后一行没有单独打印,它只是在倒数第二行之后立即打印。
如果有人知道如何解决这个小问题,我很想知道如何解决。
.data
key: .byte 1
msg:
.ascii "ayZ B"
.byte 10
.ascii "234"
.byte 10
.ascii "b cD a"
.byte 10
.text
main:
jal reverseLinesAndPrint
# Exit Program
li $v0, 10
syscall
reverseLinesAndPrint: # $s3 contains address of last char, $s0 contains offsets for both front and back, but must be reset before using for back
li $s0, 0 # RESET value of msg position offset index to iterate from beginning again
lineLoop:
add $s1, $t0, $s0 # Set $s1 equal to the base address of msg ($t0) + the position offset index ($s0)
lb $s2, ($s1) # Deref. and move the current char into s2 for checking
bne $s2, $zero, notLastChar # If the current char is not the last char in the msg, keep looping
subi $s3, $s1, 1 # Subtract 1 from the ADDRESS of $s1 to get the last char ('\n') before the NULL Terminator and store it in $s3
j lastCharIndexFound # Exit the loop by jumping past it
notLastChar:
addi $s0, $s0, 1 # Increment the position offset index
j lineLoop
lastCharIndexFound: # We now have the address of the last valid char in message (always '\n') stored in $s3
li $s0, 0 # RESET value of msg position offset index to iterate from ending this time
reverseLineLoop:
sub $s1, $s3, $s0 # This time, we are going to subtract from the starting address so we can iterate backwards over msg
bne $t0, $s1, notFirstChar # If we iterate all the way to the very first char in msg, exit the loop
li $v0, 4 # Since the first char doesn't have a '\n' char, we have to manually print
move $a0, $s1
syscall
j exit
notFirstChar:
lb $s2, ($s1) # Deref. and move the current char into s2 for checking
bne $s2, 10, notNLChar # If we find a '\n' char, we need to do some logic
li $v0, 4 # First we need to call a syscall to print string (it will stop on the previous '\n' which is now NULL)
move $a0, $s1
syscall
sb $zero, ($s1) # Second, we need to replace that current '\n' char with NULL
notNLChar: # If the current char is not '\n', keep looping
addi $s0, $s0, 1 # Increment the offset
j reverseLineLoop # Jump to next iteration
exit:
jr $ra # Jump back to main
我认为您在前行中使用换行符将其与您之前打印的行分开。这是一个聪明的想法,比只打印行(没有前面的换行符)更有效。否则,您必须进行单独的打印单字符系统调用,例如 syscall
和 $v0 = 11
/ $a0 = '\n'
(MARS system calls)
这意味着您的输出类似于 "\nline3"
然后 "\nline2"
,等等。将光标留在每行的末尾。
但是您需要对最后一行(输入字符串的第一行)进行特殊处理,因为它之前没有 \n
。你已经 是 特殊外壳,所以只需在它之前手动打印一个 \n
,作为前一行的结尾,使用 print-char 系统调用。
另一种方法可能是在换行符之后的字符上存储一个0
,位于1($s1)
,所以当您稍后到达此行的开头时,您可以将其打印为 "line2\n"
,包括末尾的换行符。 (我的版本包括在下面。)
特殊情况成为输入的最后一行(输出的第一行),但如果你有一个以 0 结尾的 C 风格隐式长度,那么在换行符之后存储一个 0
字节实际上是可以的细绳。那里已经有一个,所以你可以在进入外循环时跳过它,或者如果不这样做更方便。
不修改数据:write(1, line, length)
MARS has a write()
system call ($v0=15
) 采用指针 + 长度,因此您不需要以 0 结尾的字符串。完全像 POSIX write(int fd, char *buf, size_t len)
。文件描述符 $a0 = 1
在 MARS4.3 及更高版本中是标准输出。
当你找到一个换行符时,你可以记录那个位置并继续循环。当你找到另一个时,你可以做 subu $a2, $t1, $t0
($a2 = end - start) 得到一个长度,并设置 $a1
指向换行符之后的字符。
因此您可以打印您选择的块,而不必破坏输入数据,使其可用于只读输入,或者无需制作副本以销毁您以后需要的东西。
其他东西/代码审查:
你的代码很奇怪;您调用 reverseLinesAndPrint
时没有在 main 的寄存器中放置指针和长度或结束指针,那么为什么要将它作为一个单独的函数呢?不可重复使用。
通常的做法是在 ASCII 数据块的末尾放置另一个标签,这样您就可以将该地址放入寄存器中,而无需扫描字符串来查找长度。 (特别是因为你没有明确地在字符串末尾有一个 0
字节来终止它。有一个是因为你没有在后面放置任何其他数据,而 MARS 在数据和代码之间留下了一个间隙当您使用将数据段的起始地址放在地址 0 的内存模型时。)
而你甚至从未使用过 la $reg, msg
。您似乎将其地址硬编码为 0
?你读了 $t0
而没有先初始化它。 MARS 开始时所有寄存器都清零。 (因此可能会错过这样的错误,因为这是您选择的内存布局的有效地址。)
在正常的 MIPS 调用约定中,$s
寄存器是调用保留的 ("saved"),也就是非易失性的。但是您的函数将它们用作没有 saving/restoring 的临时对象。使用 $t
寄存器(以及 $a0..3 和 $v0..1)是正常的。
您的循环效率低下:您可以将条件分支放在底部,如 do{}while()
。您编写循环的方式非常笨拙,每次循环迭代涉及 2 个分支(包括无条件循环分支)。或者 3 用于您需要检查 \n
和 p == end
.
// your loops are over-complicated like this:
do {
loop body;
if (p == end) { // conditional branch over the loop epilogue
stuff; // put this after the loop instead of jumping over it inside the loop
goto out;
}
counter increment;
} while(1);
out:
另外:在某处写一段注释,说明每个寄存器的用途。对于某些人来说,它可以在初始化寄存器的指令上。
总的来说,您的评论非常好,主要是在更高层次上描述了正在发生的事情,而不是您已经可以从实际说明中看到的 "add 1 to $s0" 之类的东西。
这是我的做法
我使用了打印后覆盖一行的第一个字符的想法。这是 跟在 换行符之后的字节。所以当我们打印行时,它们就像 line2\n
而不是 \nline2
.
我还在 msg
的末尾放置了一个标签,而不是使用 strlen 循环。如果您要向前遍历字符串,是的,您应该在稍后保存工作时将指针保存在某个地方(例如在堆栈上),就像您最初想的那样。但是对于 assemble-time-constant 字符串,我们可以让 assembler 告诉我们它在哪里结束。我还将这些行打包到一个 .ascii
字符串中,以使源代码更加紧凑。我添加了一个明确的 .byte 0
终止符(而不是 .asciiz
),所以我可以在终止符上而不是之后添加标签。
我当然使用指针,而不是索引,所以我不需要 add
在循环内进行索引。我使用 lbu
以防零扩展比符号扩展到 32 位更有效。我宁愿将 char 值视为从 0..255 到 -128..127 的小整数。并不是说我对它们做任何带符号的比较,只是为了相等。
我使用了 addiu
因为我不想在指针数学上陷入有符号溢出。使用 add
而不是 addu
的唯一原因是陷入有符号溢出。
内部循环仍然需要 2 个条件分支来检查两个终止条件,但这是一个示例,说明您可以通过仔细规划来制作这样的循环是多么紧凑和高效。
.data
msg:
.ascii "ayZ B\n234\nb cD a\n"
endmsg: # 0 terminated *and* we have a label at the end for convenience.
.byte 0
.text
main:
la $a0, endmsg
la $a1, msg
jal reverseLinesAndPrint # revprint(end, start)
li $v0, 10
syscall # exit()
reverseLinesAndPrint:
# $a0 = end of string. We assume it's pointing at a '[=11=]' that follows a newline
# $a1 = start of string
# $t2 = tmp char
# we also assume the string isn't empty, i.e. that start - end >= 2 on function entry.
# the first char the inner loop looks at is -2(end)
#move $t0, $a0 # instead we can leave our args in a0, a1 because syscall/v0=4 doesn't modify them
lines:
findNL_loop: # do { // inner loop
addiu $a0, $a0, -1 # --p
beq $a1, $a0, foundStart # if(p==start) break
lbu $t2, -1($a0) # find a char that follows a newline
bne $t2, '\n', findNL_loop # }while(p[-1] != '\n');
# $a0 points to the start of a 0-terminated string that ends with a newline.
foundStart:
li $v0, 4
syscall # fputs(p /*$a0*/, stdout)
sb $zero, ($a0) # 0-terminate the previous line, after printing
bne $a0, $a1, lines # } while(!very start of the whole string)
jr $ra
已测试并使用您的数据。没有针对诸如第一行为空的极端情况进行测试,尽管它确实适用于最后一行为空。我想我在所有情况下都避免在第一个字符之前阅读(除了违反注释中的先决条件的太短输入。如果你想处理它们,你可以在进入循环之前检查它们。)
注意bne $t2, 10, target
是一个伪指令。如果我要进行更多优化,我会用 li
将 10
提升到 $t3
或其他东西的循环之外,而不是让 assembler 设置该常量在每次迭代的寄存器中。 li $v0, 4
相同 - 该系统调用没有 return 值,因此它甚至不会破坏 $v0
.
在寻址模式中使用像 -1($a0)
这样的偏移量是 "free" - 该指令有 16 位立即位移,所以我们不妨使用它而不是单独的指针数学。
我无缘无故地使用 $t2
而不是 $t0
,只是为了让我使用的每个 reg 都有一个唯一的编号,以便使用 MARS 小字体的人类可读性。