Mips 中的回文检查器
Palindrome Checker in Mips
我正在参加一个计算机组织 class，该组织通过 MIPS 汇编教授计算机的低级功能。作业中的一个问题是回文检查器。这是：
Write a MIPS function (called “palindrome”) that returns 1 if the
input string is a palindrome and returns 0 otherwise. The address of
the string will be passed in $a0 and the value should be returned in
$v0. Here a string is a palindrome if it reads the same in forward or
backward direction (including white spaces, punctuation marks, and so
on, but is case insensitive (i.e., „A‟ and „a‟ are considered to be
the same)). Note the string is ended with „[=13=]‟ (C/C++ convention). You
need to test your program using “test_palindrome.s”
我写了一个简单的c++程序来解决这个问题，包括一个基本的tolower函数。然后我手动将它翻译成 mips。我已经达到 运行，但是用我的 c++ 程序和 mips 程序检查回文测试字符串，我没有得到相同的结果。
为了测试mips函数，我使用了教授提供的程序。它说 none 其中是回文。这是 MIPS 代码，有一个注释部分显示了我的原始 c++ 代码。
# Program to test if a palindrome function works properly or not
# Written by Xiuwen Liu for CDA 3100 - Homework #3, problem #2
# Register usage
# $s7 - save $ra
# $s2 - current address of the string to be tested
# $s3 - the next of the last string to be tested
# $a0 - for function parameter / syscall parameter
# $v0 - syscall number / function return value
.text
.globl main
main:
addu $s7, $ra, $zero, # Save the ra
la $s2, test_str # Load the starting address of the array
la $s3, is_pali_msg, # the next of last address
pali_test_loop:
lw $a0, 0($s2) # $a0 is the address of the string
li $v0, 4 # system call to print a string
syscall # print string
li $v0, 4 # print a new line
la $a0, newline
li $v0, 4
syscall
lw $a0, 0($s2) # $a0 is the address of the string
jal palindrome # call palindrome
beq $v0, $zero, pali_no #if $v0 is 0, it is not a palindrome
li $v0, 4 #it is a palindrome
la $a0, is_pali_msg
syscall
j pali_test_end
pali_no: #it is not a palindrome
li $v0, 4
la $a0, not_pali_msg
syscall
pali_test_end:
li $v0, 4
la $a0, newline
syscall
addiu $s2, $s2, 4
lw $a0, 0($s2)
beq $a0, $s3, pali_done
j pali_test_loop
pali_done:
li $v0, 10
syscall
addu $ra, $zero, $s7 #restore $ra since the function calles
#another function
jr $ra
add $zero, $zero, $zero
add $zero, $zero, $zero
########## End of main function #########
所以这是我的代码：
# My working c++ code
# int arrayLen ( char s[]) {
# int counter = 0;
# while(s[counter] != '[=11=]'){
# if (s[counter] > 64 && s[counter] < 91)
# s[counter] = s[counter] + 32;
# counter++;
# }
# return counter;
# }
#
# int palindrom(char s[]){
# int i;
# int l = arrayLen(s);
# for(i=0;i<=l/2;i++)
# if(s[i]!=s[l-i-1]) return 0;
# return 1;
# }
palindrome:
addu $s4, $ra, $zero # save $ra
jal arrayLen # get string length and set to lowercase
move $t0, $zero # i = 0
move $t1, $v1 # l = arrayLen(s)
srl $t2, $t1, 1 # divide l by 2
palinFor:
bgt $t0, $t2, palinForExit # end for loop when i > l/2
sub $t3, $t1, $t0 # l - i
addi $t3, $t3, -1 # l - i - 1
add $t4, $a0, $t0 # s[i]
add $t5, $a0, $t3 # s[l-i-1]
addi $t0, $t0, 1 # i++
lbu $t4, ($t4) # load s[i]
lbu $t5, ($t5) # load s[l-i-1]
sne $t6, $t4, $t5 # if not equal, set $t6 to 1
beq $t6, 1, palinForExit # leave loop if not equal
j palinFor # loop again
palinForExit:
sne $v0, $t6, $zero # set return value: 0 for not palindrome, 1 for palindrome
addu $ra, $zero, $s4 # restore $ra
jr $ra # return to function caller
arrayLen:
li $t0, 0 # counter = 0
sll $t1, $t0, 2 # counter * 4
add $t1, $t1, $a0 # address of s[counter] in $t1
lbu $t2, ($t1) # load s[counter]
while:
beq $t2, 0, whileEnd # skip to end of while loop if s[counter] == [=11=]
blt $t2, 64, breakIf # skip if not uppercase range
bgt $t2, 91, breakIf # skip if not uppercase range
addi $t2, $t2, 32 # add 32 to make character lowercase
sw $t2, ($t1) # save change to memory
breakIf:
addi $t0, $t0, 1 # counter++
whileEnd:
move $v1, $t0 # return value of arrayLen is counter
jr $ra # return to function caller
这是我的代码停止的地方，下面是测试代码的 .data 部分：
.data
#The following examples were copied from
# http://en.wikipedia.org/wiki/Palindrome
pali1:
.asciiz "Socorram me subi no on ibus em Marrocos" #Brazilian Portuguese
pali2:
.asciiz "Ein Neger mit Gazelle zagtim Regen nie" #German
pali3:
.asciiz "stressed desserts"
pali4:
.asciiz "palindromes"
pali5:
.asciiz "tattarrattat"
is_pali_msg:
.asciiz " The string is a palindrome."
not_pali_msg:
.asciiz " The string is not a palindrome."
newline:
.asciiz "\n"
test_str:
.word pali1, pali2, pali3, pali4, pali5, is_pali_msg
学这些东西我的脑袋疼。不胜感激，谢谢 :D
试试这个：
.text
strlen:
# ------------
# arguments:
# a0 = string
# ------------
li $v0, 0 #set return value to 0
strlen_loop:
lb $t0, 0($a0) #load byte from beginning of the string
beq $t0, [=10=], strlen_exit #when character value is 0 we have
#reached the end of the string
addi $a0, $a0, 1 #shift pointer to string one space right
addi $v0, $v0, 1 #increment return value by one
j strlen_loop
strlen_exit:
# ------------
# returns:
# INTEGER (string length)
# ------------
jr $ra #return
palindrom:
# ------------
# arguments:
# a0 = string
# ------------
sub $sp, $sp, 8 #allocate memory on stack
sw $ra 0($sp) #save return address
sw $a0 4($sp) #save argumrnt value
jal strlen #call strlen
move $t0, $v0 #save result
lw $a0 4($sp) #load argument
move $t1, $a0 #save its value to t1
li $t2, 1 #set counter to 1
li $v0, 1 #prepare return value
div $t3, $t0, 2 #calculate string length / 2
addi $t3, $t3, 1 #add one more in case of even number
palindrom_loop:
bge $t2, $t3 palindrom_exit #when counter reaches half of the string length - exit
lb $t4, 0($a0) #get character from beginning
sub $t5, $t0, $t2 #subtract counter from the string length
add $t6, $t5, $t1 #add index from the end of the string to start address
lb $t7, 0($t6) #get corresponding character from the end of the string
beq $t4, $t7, palindrom_continue #check to determine are the characters exact match
li $v0, 0 #if not return 0, immediately
j palindrom_exit
palindrom_continue:
addi $a0, $a0, 1 #shift pointer to string one space right
addi $t2, $t2, 1 #increment counter by one
j palindrom_loop
palindrom_exit:
# ------------
# returns:
# TRUE (1) or FALSE (0)
# ------------
lw $ra 0($sp) #load return address
addi $sp, $sp, 8 #free stack
jr $ra #return
main:
#entry point
la $a0, str #load string
jal palindrom #call palindrom
move $a0, $v0 #set a0 to palindrom return value
li $v0, 1 #set 1 to v0 - as this is system call for print int
syscall #make the call
li $v0, 10 #set 10 to v0 - as this is system call for exit program
syscall #make the call
.data
str: .asciiz "thiispalindrome_emordnilapsiiht"
方法是从字符串的开头获取字符，从字符串的末尾获取对应的字符。如果完全匹配，则继续执行直到计数器达到字符串长度的一半。如果发现任何一对字符不同，立即停止执行并且 return FALSE.
还有一点，我还没有实现大写字母与小写字母没有区别的部分。但这并不难。你可以自己添加。这个想法是测试每个加载的字符，如果它的 ascii 在 A (65) 和 Z (90) 之间。如果是这样，您将向 ascii 值添加 32，您将得到小写字母。
我正在参加一个计算机组织 class，该组织通过 MIPS 汇编教授计算机的低级功能。作业中的一个问题是回文检查器。这是：
Write a MIPS function (called “palindrome”) that returns 1 if the input string is a palindrome and returns 0 otherwise. The address of the string will be passed in $a0 and the value should be returned in $v0. Here a string is a palindrome if it reads the same in forward or backward direction (including white spaces, punctuation marks, and so on, but is case insensitive (i.e., „A‟ and „a‟ are considered to be the same)). Note the string is ended with „[=13=]‟ (C/C++ convention). You need to test your program using “test_palindrome.s”
我写了一个简单的c++程序来解决这个问题，包括一个基本的tolower函数。然后我手动将它翻译成 mips。我已经达到 运行，但是用我的 c++ 程序和 mips 程序检查回文测试字符串，我没有得到相同的结果。
为了测试mips函数，我使用了教授提供的程序。它说 none 其中是回文。这是 MIPS 代码，有一个注释部分显示了我的原始 c++ 代码。
# Program to test if a palindrome function works properly or not
# Written by Xiuwen Liu for CDA 3100 - Homework #3, problem #2
# Register usage
# $s7 - save $ra
# $s2 - current address of the string to be tested
# $s3 - the next of the last string to be tested
# $a0 - for function parameter / syscall parameter
# $v0 - syscall number / function return value
.text
.globl main
main:
addu $s7, $ra, $zero, # Save the ra
la $s2, test_str # Load the starting address of the array
la $s3, is_pali_msg, # the next of last address
pali_test_loop:
lw $a0, 0($s2) # $a0 is the address of the string
li $v0, 4 # system call to print a string
syscall # print string
li $v0, 4 # print a new line
la $a0, newline
li $v0, 4
syscall
lw $a0, 0($s2) # $a0 is the address of the string
jal palindrome # call palindrome
beq $v0, $zero, pali_no #if $v0 is 0, it is not a palindrome
li $v0, 4 #it is a palindrome
la $a0, is_pali_msg
syscall
j pali_test_end
pali_no: #it is not a palindrome
li $v0, 4
la $a0, not_pali_msg
syscall
pali_test_end:
li $v0, 4
la $a0, newline
syscall
addiu $s2, $s2, 4
lw $a0, 0($s2)
beq $a0, $s3, pali_done
j pali_test_loop
pali_done:
li $v0, 10
syscall
addu $ra, $zero, $s7 #restore $ra since the function calles
#another function
jr $ra
add $zero, $zero, $zero
add $zero, $zero, $zero
########## End of main function #########
所以这是我的代码：
# My working c++ code
# int arrayLen ( char s[]) {
# int counter = 0;
# while(s[counter] != '[=11=]'){
# if (s[counter] > 64 && s[counter] < 91)
# s[counter] = s[counter] + 32;
# counter++;
# }
# return counter;
# }
#
# int palindrom(char s[]){
# int i;
# int l = arrayLen(s);
# for(i=0;i<=l/2;i++)
# if(s[i]!=s[l-i-1]) return 0;
# return 1;
# }
palindrome:
addu $s4, $ra, $zero # save $ra
jal arrayLen # get string length and set to lowercase
move $t0, $zero # i = 0
move $t1, $v1 # l = arrayLen(s)
srl $t2, $t1, 1 # divide l by 2
palinFor:
bgt $t0, $t2, palinForExit # end for loop when i > l/2
sub $t3, $t1, $t0 # l - i
addi $t3, $t3, -1 # l - i - 1
add $t4, $a0, $t0 # s[i]
add $t5, $a0, $t3 # s[l-i-1]
addi $t0, $t0, 1 # i++
lbu $t4, ($t4) # load s[i]
lbu $t5, ($t5) # load s[l-i-1]
sne $t6, $t4, $t5 # if not equal, set $t6 to 1
beq $t6, 1, palinForExit # leave loop if not equal
j palinFor # loop again
palinForExit:
sne $v0, $t6, $zero # set return value: 0 for not palindrome, 1 for palindrome
addu $ra, $zero, $s4 # restore $ra
jr $ra # return to function caller
arrayLen:
li $t0, 0 # counter = 0
sll $t1, $t0, 2 # counter * 4
add $t1, $t1, $a0 # address of s[counter] in $t1
lbu $t2, ($t1) # load s[counter]
while:
beq $t2, 0, whileEnd # skip to end of while loop if s[counter] == [=11=]
blt $t2, 64, breakIf # skip if not uppercase range
bgt $t2, 91, breakIf # skip if not uppercase range
addi $t2, $t2, 32 # add 32 to make character lowercase
sw $t2, ($t1) # save change to memory
breakIf:
addi $t0, $t0, 1 # counter++
whileEnd:
move $v1, $t0 # return value of arrayLen is counter
jr $ra # return to function caller
这是我的代码停止的地方，下面是测试代码的 .data 部分：
.data
#The following examples were copied from
# http://en.wikipedia.org/wiki/Palindrome
pali1:
.asciiz "Socorram me subi no on ibus em Marrocos" #Brazilian Portuguese
pali2:
.asciiz "Ein Neger mit Gazelle zagtim Regen nie" #German
pali3:
.asciiz "stressed desserts"
pali4:
.asciiz "palindromes"
pali5:
.asciiz "tattarrattat"
is_pali_msg:
.asciiz " The string is a palindrome."
not_pali_msg:
.asciiz " The string is not a palindrome."
newline:
.asciiz "\n"
test_str:
.word pali1, pali2, pali3, pali4, pali5, is_pali_msg
学这些东西我的脑袋疼。不胜感激，谢谢 :D
试试这个：
.text
strlen:
# ------------
# arguments:
# a0 = string
# ------------
li $v0, 0 #set return value to 0
strlen_loop:
lb $t0, 0($a0) #load byte from beginning of the string
beq $t0, [=10=], strlen_exit #when character value is 0 we have
#reached the end of the string
addi $a0, $a0, 1 #shift pointer to string one space right
addi $v0, $v0, 1 #increment return value by one
j strlen_loop
strlen_exit:
# ------------
# returns:
# INTEGER (string length)
# ------------
jr $ra #return
palindrom:
# ------------
# arguments:
# a0 = string
# ------------
sub $sp, $sp, 8 #allocate memory on stack
sw $ra 0($sp) #save return address
sw $a0 4($sp) #save argumrnt value
jal strlen #call strlen
move $t0, $v0 #save result
lw $a0 4($sp) #load argument
move $t1, $a0 #save its value to t1
li $t2, 1 #set counter to 1
li $v0, 1 #prepare return value
div $t3, $t0, 2 #calculate string length / 2
addi $t3, $t3, 1 #add one more in case of even number
palindrom_loop:
bge $t2, $t3 palindrom_exit #when counter reaches half of the string length - exit
lb $t4, 0($a0) #get character from beginning
sub $t5, $t0, $t2 #subtract counter from the string length
add $t6, $t5, $t1 #add index from the end of the string to start address
lb $t7, 0($t6) #get corresponding character from the end of the string
beq $t4, $t7, palindrom_continue #check to determine are the characters exact match
li $v0, 0 #if not return 0, immediately
j palindrom_exit
palindrom_continue:
addi $a0, $a0, 1 #shift pointer to string one space right
addi $t2, $t2, 1 #increment counter by one
j palindrom_loop
palindrom_exit:
# ------------
# returns:
# TRUE (1) or FALSE (0)
# ------------
lw $ra 0($sp) #load return address
addi $sp, $sp, 8 #free stack
jr $ra #return
main:
#entry point
la $a0, str #load string
jal palindrom #call palindrom
move $a0, $v0 #set a0 to palindrom return value
li $v0, 1 #set 1 to v0 - as this is system call for print int
syscall #make the call
li $v0, 10 #set 10 to v0 - as this is system call for exit program
syscall #make the call
.data
str: .asciiz "thiispalindrome_emordnilapsiiht"
方法是从字符串的开头获取字符，从字符串的末尾获取对应的字符。如果完全匹配，则继续执行直到计数器达到字符串长度的一半。如果发现任何一对字符不同，立即停止执行并且 return FALSE.
还有一点，我还没有实现大写字母与小写字母没有区别的部分。但这并不难。你可以自己添加。这个想法是测试每个加载的字符，如果它的 ascii 在 A (65) 和 Z (90) 之间。如果是这样，您将向 ascii 值添加 32，您将得到小写字母。