string - 如何在 MIPS 中反转多行字符串的行序？

Question

我有一个形式的多行消息：

.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

到目前为止，我的一般想法是将第一个 char 的地址推送到堆栈上，然后遍历消息（msg 的基地址 + 偏移计数器）并在 '\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

标签： stringassemblymipsstring-concatenationlow-level

Answer 1

我认为您在一行之前使用换行符将其与您之前打印的行分开。这是一个聪明的想法，比只打印一行（没有前面的换行符）更有效。否则，您必须进行单独的 print-single-char 系统调用，例如syscall使用$v0 = 11/ $a0 = '\n'（MARS 系统调用）

这意味着您的输出类似于"\nline3"then"\nline2"等，将光标留在每行的末尾。

但是您需要对最后一行（输入字符串的第一行）进行特殊处理，因为\n它之前没有。您已经对它进行了特殊封装，因此只需\n在它之前手动打印一个，作为上一行的结尾，使用 print-char 系统调用。

---

另一种方法可能是在换行符之后0存储一个字符1($s1)， at ，因此当您稍后到达该行的开头时，您可以将其打印为"line2\n"在末尾包含换行符。（我的这个版本包括在下面。）

特殊情况成为输入的最后一行（输出的第一行），但0如果你有一个以 0 结尾的 C 风格的隐式长度字符串，那么在换行符之后存储一个字节实际上是可以的。那里已经有一个，所以你可以在进入外循环时跳过它，或者如果不这样做更方便的话，可以不跳过。

---

不修改数据：write(1, line, length)

MARS 有一个write()系统调用( $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寄存器是调用保留（“保存”）的，也就是非易失性的。但是您的函数将它们用作临时对象而不保存/恢复它们。使用$t寄存器（以及 $a0..3 和 $v0..1）是正常的。

您的循环效率低下：您可以将条件分支放在底部，如do{}while(). 您编写循环的方式非常笨拙，每次循环迭代涉及 2 个分支（包括无条件循环分支）。或 3 用于您需要检查 for\n和 for的搜索循环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:

另外：在某处写一段注释，说明每个寄存器的用途。对于某些人来说，它可以在初始化寄存器的指令上。

一般来说，您的评论非常好，主要是在更高级别上描述正在发生的事情，而不是您已经从实际指令中看到的“将 1 添加到 $s0”之类的内容。

---

我是这样做的

我使用了在打印后覆盖一行的第一个字符的想法。这是换行符之后的字节。因此，当我们打印行时，它们就像line2\nnot \nline2。

我还在末尾添加了一个标签，msg而不是使用 strlen 循环。如果您要在字符串上向前迭代，是的，您应该在稍后保存工作时将指针保存在某处（例如，在堆栈上），就像您最初的想法一样。但是对于汇编时间常数字符串，我们可以让汇编器告诉我们它的结束位置。我还将这些行打包成一个.ascii字符串，以使源代码更紧凑。我添加了一个显式.byte 0终止符（而不是.asciiz），因此我可以在终止符上而不是之后添加标签。

我当然使用指针，而不是索引，所以我不需要add循环内的 for 索引。我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 '\0' 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是一个伪指令。如果我要优化更多，我会用 in 或其他东西将其从循环中提升出来10，而不是让汇编程序在每次迭代时在寄存器中设置该常量。相同的- 系统调用没有返回值，因此它甚至不会 destroy 。li$t3li $v0, 4$v0

在寻址模式中使用偏移量-1($a0)是“免费的”——指令有 16 位立即位移，所以我们不妨使用它而不是单独的指针数学。

我使用$t2而不是$t0没有真正的原因，只是为了让我使用的每个 reg 都有一个唯一的编号，以提高 MARS 小字体的人类可读性。