装配MIPS:检查字符串是否回文 [英] Assembly MIPS: Checking if a string is palindromic or not
问题描述
回文是可以双向读取的字符串.例如雷达",哇"等.
Palindromic is a string that can be read both ways. like "radar", "wow" etc.
从C中我们知道我们可以使用"for"循环和"if"表达式检查给定的字符串:
From C we know that we can check a given string with a "for" loop and an "if" expression:
for(i=0; i<length; i++)
if(str[i] == str[length-i-1])
printf("Palindromic");
else
print("Non Palindromic");
这样,我们就可以从两侧到达琴弦的中心.
so that way we can reach to the center of the string by both sides.
此代码要求我们已经对字符进行计数以了解字符串的长度.
This code requires that we have counted the characters to know the length of the string.
在MIPS上,此"for"循环似乎非常复杂.
On MIPS, this "for" loop seems quite complex.
在这里我得到了自己:
.data
str: .space 20
isntpal: .asciiz "it is not palindromic!"
ispal: .asciiz "it is palindromic!"
.text
.globl main
main:
add $t0, $zero, $zero #t0 = i counter for the loops
add $t1, $zero, $zero #t1 = j counter for length of the string
li $v0, 8 #gets(str)
la $a0, str
la $a1, 20
syscall
length:
lb $s0, str($t0) #load each character to s0
beq $s0, '\0', NEXTCHECK
add $t0, $t0, 1 #i++ to scan all the characters of the string
add $t1, $t1, 1 #j++ for the total length of the string
j length
NEXTCHECK:
add $t0, $zero, $zero #clean the t0 register from the length loop
pal:
sub $t4, $t1, $t0 #length - i - 1
sub $t4, $t4, 1
lb $s0, str($t0) #str[i]
lb $s1, str($t4) #str[length-i-1]
slt $t3, $t0, $t1 #for(i=0; i<length; i++)
beq $t3, $zero, EXIT
add $t0, $t0, 1 #i++
beq $s0, $s1, ELSE #if (str[i] == str[length-i-1])
li $v0, 4 #printf("It is palindromic");
la $a0, ispal
syscall
j EXIT
ELSE:
li $v0, 4 #else printf("It is not palindromic");
la $a0, isntpal
syscall
j EXIT
j pal
EXIT:
li $v0, 10
syscall
我在理解应该在哪里贴上EXIT和ELSE标签时遇到了一个问题,我认为这就是为什么它总是返回字符串是回文的,即使不是这样的原因.
I have a problem understanding where i should have the EXIT and ELSE labels, and I think this is why it always returns that the string is palindromic, even if it isn't.
正确放置标签的方法是什么?
What is the correct way to put the labels?
它需要多个标签吗?
推荐答案
正确高效的C版本:
bool is_palindrome(const char * str, const size_t length) {
const char * frontptr = str; // front pointer: points at the very first character of string
const char * backptr = str + length-1; // back pointer: points at the very last character of string
while (frontptr < backptr) { // while front pointer points ahead of back pointer
if (*frontptr != *backptr) return false; // characters differ => not a palindrome
++frontptr; // move front pointer at next character in string
--backptr; // move back pointer at "next" character toward start of string
}
// front pointer points at/beyond back pointer
// all chars were compared (except middle one for odd length string, which is "palindromic" always)
// and all were equal, thus the input string is a palindrome, if this point is reached
return true;
}
此C代码是有意编写的,这应使其非常容易转换为ASM(例如,每C行1-2条指令).
This C code is written intentionally in a way, which should make it very straightforward for conversion to ASM (like 1-2 instructions per C line).
如果您知道值的地址(在C中的指针),如何从内存中加载值:
How to load a value from memory, if you know it's address (pointer in C):
la $a0,some_address # a0 = address (pointer)
lb $t0,($a0) # t0 = byte loaded from memory at a0
如何在ASM中增加/减少指针:将指针所指向的元素的大小添加到指针的当前值.
How to increment/decrement pointers in ASM: you add to the current value of pointer the size of the element pointed at.
对于ASCII字符串,元素为单个字节,因此要向前/向后移动一个字符,必须向指针添加+ 1/-1,例如:
With ASCII string the elements are single bytes, so to move one character forth/back you have to add +1/-1 to the pointer, like:
addi $a0,$a0,1 # ++byte_ptr
addi $a1,$a1,-1 # --byte_ptr
如果要使用单词数组,则需要执行+ -4将指针向前/向后移动一个元素.
If you would work with word array, you would want to do +-4 to move the pointer one element forth/back.
并学习如何在MIPS ASM中使用过程" ,因此您可以创建一些通用的通用获取字符串长度" "代码,然后通过简单的复制/粘贴重复使用(除非最终创建自己的某个库).
And learn how to use "procedures" in MIPS ASM, so you can create some generic universal "get string length" code, and then re-use it later by simple copy/paste (unless you create eventually some library of your own).
如果您遵循C ++示例,则回文检验也可以作为单独的过程进行.
Also the palindrome test can be done as separate procedure, if you follow the C++ example.
基本上,您将需要一些简单的代码来维护+调试+原因:
The in the main you would have a bit simpler code to maintain + debug + reason about:
# input string
# prepare arguments for get_length
# call get_length
# process result and prepare arguments for is_palindrome
# call is_palindrome
# set a0 to one of the two result strings based on return value
# display string
# exit
在指令总数上可能会更长一些,因为您将有更多的jal
和jr $ra
行,但是它将使您在编写/调试时专注于更短,更简单的代码部分.
May be a bit longer on total number of instructions, as you will have additional jal
and jr $ra
lines, but it will allow you to focus on shorter and simpler parts of code while writing/debugging.
这篇关于装配MIPS:检查字符串是否回文的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!