string - 字符串处理子例程中的字符串缓冲区

Question

我目前正在使用 mips 汇编语言创建一些字符串处理子例程，但遇到了问题。每个子例程都将输出地址作为参数，该地址用作将写入新处理的字符串的内存位置。起初我让子程序直接将字节写入输出地址，但很快意识到我应该写入临时字符串缓冲区，处理它，然后将缓冲区内容复制到输出地址。问题是，我该怎么做呢？在 main.asm 中用 .space 声明一个全局静态字符串缓冲区是一种解决方案，但是当一个字符串处理子例程被另一个调用并开始覆盖调用者的字符串数据时可能会出现问题。使用运行时堆栈存储字符串数据是另一种解决方案，但也有其自身的问题。

这是个常见的问题吗？处理这种情况的最佳做法是什么？

任何建议将不胜感激。谢谢你。

标签： stringassemblymips

Answer 1

复制速度很慢，尽可能避免。

您有 2 个不错的选择：

• 复制和计算：例如，从输出缓冲区的末尾开始的字符串反转函数，在向前读取的同时向后写入。反之亦然，因为输入的结尾可能已经在缓存中很热。并且您希望将输出的开头热保留在缓存中，因此最后写入它对于中大型字符串很有用。如果您有字节交换指令，并且输入和输出都具有必要的对齐方式，则您可以轻松地一次完成整个单词（或 SIMD 向量）。
• 就地：例如字符串反转，从指向开始和结束的指针开始，然后将它们彼此靠近，直到它们在中间交叉。一次超过 1 个字节需要检查以避免它们交叉时重叠。（尽管如果您将自己限制为字对齐的加载/存储，那么您已经必须处理这个问题，并且根据对齐方式 + 长度，快速进行可能并不容易。）

如果您使用的是隐式长度字符串并且必须strlen输入，那么输入的末尾已经在缓存中很热，您应该从那里开始阅读。有些算法你可以在知道输出多长时间之前就开始编写输出，所以如果你需要先 strlen 来找出你需要多大的临时数组，情况会更糟。

您甚至可以在不同的函数中实现某些操作的复制和就地版本，以便为调用者提供选项，具体取决于他们是否需要保留原始版本。如果关心性能足以在 asm 中手写，请设计您的 API 以避免不必要的复制。

（对于某些算法，复制和就地可以使用相同的代码。）

通常你可以只处理到输出缓冲区。

您可以指定（在注释/文档/带有char *restrict outbufarg 的 C 函数签名中）您的函数在读取其所有输入之前写入其输出，因此重叠输入和输出不一定有效。

如果完全支持就地（例如，对于将每个字母输入字符大写的函数，其中out[i]仅取决于in[i]），那么您也可以记录它，即使部分重叠不会。（例如，如果写作out[i]破坏了in[i+something]）

像这样的函数可以完全在原地工作，也可以作为非重叠的复制和大写。

---

如果出于某种原因确实需要 tmp 缓冲区：

• 如果您的 tmp 缓冲区大小很小且大小固定（不随输入字符串长度缩放），请在调用堆栈上分配它。

• 把问题交给你的调用者：让你的调用者提供一个大小合适的 tmp 缓冲区作为额外的参数。然后你的调用者可以在多个调用中重用这个空间，只要它足够大以容纳最大的被调用者。

您的调用者可能知道它不需要是可重入的或线程安全的，并且可以使用静态缓冲区。或者它可能知道最大大小足够低，可以安全地使用堆栈而没有堆栈溢出的风险。

当然，动态分配 + 空闲作为大字符串的最坏情况后备是可能的。在像 MARS 或 SPIM 这样的玩具操作系统上，我认为有一个syscall。在真正的 MIPS 上，通常会有某种malloc库函数，您可以将其与维护空闲列表的优化分配器一起使用。您希望避免进行实际的系统调用来获取和释放一个小缓冲区。

您甚至可以在运行时检查大小是否很小并决定使用堆栈空间（并在函数结束时进行分支，以决定是free调整堆栈指针还是只调整堆栈指针。）