MIPS链表

我很困惑如何在MIPS中创build结构。 我想创build一个链表实现,它计算存储的string的长度,并按照存储顺序对它们进行sorting。 这是我的代码到目前为止:

# Global symbols # # string routines .globl read_string .globl strcmp .globl strlen .globl trim .globl strloop .globl replace # list routines .globl insert .globl insert_here .globl print_list .globl main # pseudo-standard library .globl get_string .globl malloc .globl print_newline .globl print_string ################################################## # Constants # .data MAX_STR_LEN: .word 50 STR_NEWLINE: .asciiz "\n" STR_ENTER: .asciiz "enter a string: " ################################################################# ################################################################# # Code # .text ################################################## # main: repeatedly gets strings from user and enters them in list # until a string of length less than two is entered; # prints list in order when done # main: # lines commented out - not needed in simulation: # addi $sp, $sp, -12 # sw $ra, 0($sp) # sw $s0, 4($sp) #$s0 will be linked list # sw $s1, 8($sp) #$s1 will be the current string li $s0, 0 # initialize the list to NULL Loop_main: la $a0, STR_ENTER jal print_string jal read_string move $s1, $v0 jal trim jal strlen addi $t0, $zero, 2 beq $v0, $t0, Exit_loop_main jal strcmp jal insert # replace newline with null terminator # ... # check string length; exit loop if less than 2 # ... # insert string into list # ... # reassign front of list j Loop_main Exit_loop_main: move $a0, $s0 jal print_list jal print_newline # lines commented out - not needed in simulation: # lw $s1, 8($sp) # lw $s0, 4($sp) # lw $ra, 0($sp) # addi $sp, $sp, 12 # jr $ra # exit simulation via syscall li $v0, 10 syscall ################################################## # String routines # # read_string: allocates MAX_STR_LEN bytes for a string # and then reads a string from standard input into that memory address # and returns the address in $v0 read_string: addi $sp, $sp, -8 #allocate space for 2 items on the stack sw $ra, 0($sp) #push the jump register onto the stack sw $s0, 4($sp) #push the head of the list onto the stack add $t0, $t0, $zero #$t0 gets 0 la $t1, MAX_STR_LEN #$a0 gets MAX_STR_LEN lw $a0, 0($t1) #move MAX_STR_LEN from $t1 into $a0 jal malloc #jump to malloc to allocate space for string move $a0, $v0 #move pointer to allocated memory to $a0 add $t1, $t1, $zero #get zero move $a1, $t1 #move zero to a1 la $a1, MAX_STR_LEN #$a1 gets MAX_STR_LEN jal get_string #get the string into $v0 lw $s0, 4($sp) #load the head of the list lw $ra, 0($sp) #load the jump address addi $sp, $sp, 8 #push onto the stack space for 2 elements jr $ra #jump back to caller function # trim: modifies string stored at address in $a0 so that # first occurrence of a newline is replaced by null terminator trim: li $t0, 10 #$t1 gets 10, ASCII value for newline strloop: lb $t1, 0($a0) #get byte of character of string and loop beq $t1, $t0, replace #if $a0 = go to replace addi $a0, $a0, 8 #increment $a0 by 8 to piont to first bit of next char j strloop #jump back to beginning replace: add $t2, $t2, $zero #$t2 is set to zero, ASCII value for null terminator sb $t2, 0($a0) #$t2 is stored into the byte starting at $a0 jr $ra #jump back to caller # strlen: given string stored at address in $a0 # returns its length in $v0 strlen: add $t0, $t0, $zero #$t0 gets zero lenloop: lb $t1, 0($a0) #get the first byte for first char in $a0 beq $t1, $zero, exitline #if $t1 == 0 (null terminator), jump to exit addi $a0, $a0, 8 #else, increment to next byte of string for next char addi $t0, $t0, 1 #increment $t0 for each character in string j lenloop #jump back up to loop exitline: sw $t0, 0($v0) #store $t0 into $v0 to return lenght of string jr $ra #jump back to caller # strcmp: given strings s, t stored at addresses in $a0, $a1 # returns -1 if s < t; 0 if s == t, 1 if s > t strcmp: lb $t0, 0($a0) #get byte of first char in string s lb $t1, 0($a1) #get byte of first char in string t # lb $t3, 0($t0) #lb $t4, 0($t1) addi $t3, $t3, 1 #get 1 to compare slt $t2, $t0, $t1 #if s[0] < t[0] $t2 = 1, else $t2 = 0 bne $t2, $t3, lessthan #if $t2 == 1, jump to lessthan slt $t2, $t1, $t0 #if t[0] < s[1], $t2 = 1, else $t2 = 0 beq $t2, $t3, greaterthan #if $t2 == 1, jump to greaterthan sw $zero, 0($v0) #$v0 gets zero j end lessthan: addi $t4, $t4, -1 #$t4 gets -1 sw $t4, 0($v0) #$v0 gets -1 j end #jump to end greaterthan: addi $t4, $t4, 1 #$t4 gets 1 sw $t4, 0($v0) #$v0 gets 1 j end #jump to end end: jr $ra # insert_here: given address of front of list in $a0 # and address of string to insert in $a1, # inserts new linked-list node in front of list; # returns address of new front of list in $v0 insert_here: lw $t0, 0($a0) #$t0 get $a0 lw $t1, 0($a1) #$t1 gets $a1 addi $t2, $zero, 8 #$t2 gets 8 sw $t2, 0($a0) #$t2 gets stored into $a0 jal malloc #allocate 1 byte for the memory move $t3, $v0 #get address of new memory from $v0 and move to $t3 sw $t1, 0($t3) #store the string pointer into bytes 0-3 of the new memory sw $t0, 4($t3) #store the pointer to the original front of the list sw $t3, 0($s0) #store the new node into $s0 lw $ra, 0($sp) #pop the register to jump back to off the stack addi $sp, $sp, 4 #add to the stack jr $ra #jump back to caller ################################################## # List routines # # insert: given address of front of list in $a0 # and address of string to insert in $a1, # inserts new linked-list node in appropriate place in list # ... # returns address of new front of list in $v0 (which may be same as old) insert: addi $sp, $sp, 4 #add space on the stack sw $ra, 0($sp) #store jump register onto the stack lw $t9, 0($a0) #load head of the list for later use lw $t0, 0($a0) #load head of list into $t0 andi $t0, $t0, 240 #bitwise and with 240 (1111 0000) to extract first 4 bits for pointer to string sw $t0, 0($a0) #store $t0 into $a0 for strcmp call lb $t6, 0($t0) #get the byte of the first string char in the list lw $t7, 0($a1) #get address of string lb $t1, 0($t7) #get the byte of the first char of the string addi $t3, $zero, 1 #$t3 gets 1 addi $t4, $zero, -1 #$t3 gets -1 alphloop: #be careful in this function may have a bug with front of the list # slt $t2, $t1, $t0 #if $t1 < $t0, then $t2 = 1, else $t2 = 0 # beq $t2, $t3, put #if # beq $t2, $zero, nextchar jal strcmp #compare the strings in $a0 and $a1 move $t5, $v0 #move the value returned from strcmp into $t5 beq $t5, $t4, put #if $t5 = -1, then value is less and then put new string at head of list beq $t5, $t3, nextstring #if $t5 = 1, then the head of the list is larger than the string and go to next string beq $t5, $zero, close #check if it is zero, if so it is already in the list so step out nextstring: lw $t2, 0($a0) #store pointer to next node in $t2 andi $t8, $t9, 15 #get address of next node string beq $t8, $zero, put #if it points to null then add node at the end sw $t8, 0($a0) #store into $a0 j alphloop #check against the next string in loop put: li $t5, 8 #$t5 gets 8 move $a0, $t5 #$t5 moved into $a0 jal malloc #allocate size for node move $t5, $v0 #move address returned by malloc to $t5 sw $a1, 0($t5) #store $a1 into address allocated beq $t2, $zero, front #node is at front of the list, so there is no need to update pointer sw $t2, 4($t5) #store pointer to current node into new node addi $t0, $a0, -8 #subtract from the current node back one sw $t5, 0($t0) #store new pointer into the node jr $ra front: sw $t5, 0($s0) #make global reference to front of the node the new node if its at the front close: jr $ra #jump back # print_list: given address of front of list in $a0 # prints each string in list, one per line, in order print_list: addi $sp, $sp, -8 sw $ra, 0($sp) sw $s0, 4($sp) move $s0, $a0 beq $s0, $zero, Exit_print_list Loop_print_list: lw $a0, 0($s0) jal print_string jal print_newline lw $s0, 4($s0) # node = node->next bne $s0, $zero, Loop_print_list Exit_print_list: lw $s0, 4($sp) lw $ra, 0($sp) addi $sp, $sp, 8 jr $ra ################################################## # Pseudo-standard library routines: # wrappers around SPIM/MARS syscalls # # assumes buffer to read into is in $a0, and max length is in $a1 get_string: li $v0, 8 syscall jr $ra # malloc: takes one argument (in $a0) which indicates how many bytes # to allocate; returns a pointer to the allocated memory (in $v0) malloc: li $v0, 9 # SPIM/MARS code for "sbrk" memory allocation syscall jr $ra # print_newline: displays newline to standard output print_newline: li $v0, 4 la $a0, STR_NEWLINE syscall jr $ra # print_string: displays supplied string (in $a0) to standard output print_string: li $v0, 4 syscall jr $ra 

我应该从哪里出发? 我的代码集合在两个input中读取后没有做任何事情。

你在评论,风格和程序布局方面做得很好。 我见过的最好的一些。 总的来说,一个好的努力。

但是,有一些错误。

我制作了一个注释版本的代码和一个重构的代码。 见下文。


整个代码中都有一些错误,与结构或插入代码无关[至less有26个这样的错误]。

经常有人经常重复错误的单一指令。 这通常是想要设置一个常数寄存器。 你的代码使用(例如) addi $t3,$t3,7而不是正确的addi $t3,$t3,7 addi $t3,$zero,7 。 我用li $t3,7replace了那些。 在一些地方,你确实使用了正确的版本,所以我把它称为“错字”错误,但是有很多错误。

你的strcmp只比较第一个字符而不是整个string。

实际的插入代码有点复杂,比需要的复杂得多(例如insert_here没有被使用)。 它也有一些严重的逻辑/实现错误。 你是在正确的轨道上,但是,在修复了许多其他无关的错误之后,我决定重写它,而不是尝试修补它。


这里是注释的版本[剥离了SO空间限制],我修复了大部分的一行错误(注有“BUG”],但是代码仍然没有运行,也没有修复结构/插入逻辑。 我试图保持忠实于你原来的代码[请原谅无偿风格的清理]:

 main: # BUGBAD: this is the list pointer but it is _never_ set to a non-null # value but things get stored relative to it li $s0,0 # initialize the list to NULL Loop_main: la $a0,STR_ENTER jal print_string jal read_string move $s1,$v0 # BUG: trim uses and trashes a0 but strlen needs the original value jal trim jal strlen addi $t0,$zero,2 beq $v0,$t0,Exit_loop_main # BUG: this strcmp serves _no_ purpose jal strcmp jal insert # replace newline with null terminator # ... # check string length; exit loop if less than 2 # ... # insert string into list # ... # reassign front of list j Loop_main Exit_loop_main: move $a0,$s0 jal print_list jal print_newline li $v0,10 syscall read_string: addi $sp,$sp,-8 sw $ra,0($sp) sw $s0,4($sp) # BUG: this does _not_ set t0 = 0 ###add $t0,$t0,$zero # $t0 gets 0 li $t0,0 # BUGFIX # BUG: MAX_STR_LEN should be a _constant_ (eg 80) but this is an _address_ ###la $t1,MAX_STR_LEN # $a0 gets MAX_STR_LEN lw $t1,MAX_STR_LEN # $a0 gets MAX_STR_LEN # BUGFIX lw $a0,0($t1) # move MAX_STR_LEN from $t1 into $a0 jal malloc # allocate space for string move $a0,$v0 # move pointer to allocated memory to $a0 # BUG: this does _not_ set t1 = 0 ###add $t1,$t1,$zero # get zero li $t1,0 # get zero # BUGFIX move $a1,$t1 # move zero to a1 # BUG: this does not set a1 = 50 ###la $a1,MAX_STR_LEN # $a1 gets MAX_STR_LEN lw $a1,MAX_STR_LEN # $a1 gets MAX_STR_LEN # BUGFIX jal get_string # get the string into $v0 lw $s0,4($sp) lw $ra,0($sp) addi $sp,$sp,8 jr $ra # trim: modifies string stored at address in $a0 so that # first occurrence of a newline is replaced by null terminator trim: # NOTE: using hex for this would be better (eg 0x0A) li $t0,10 # $t1 gets 10, ASCII value for newline strloop: lb $t1,0($a0) # get byte of char of string and loop beq $t1,$t0,replace # if $a0 = go to replace # BUG: the increment should be 1 ###addi $a0,$a0,8 # increment $a0 by 8 to piont to first bit of next char addi $a0,$a0,1 # increment $a0 by 1 to point to next char # BUGFIX j strloop # jump back to beginning replace: # BUG: this does _not_ set t2 to 0 ###add $t2,$t2,$zero # $t2 is set to zero, ASCII value for null terminator li $t2,0 # t2 = zero, ASCII value for EOS # BUGFIX sb $t2,0($a0) # $t2 is stored into byte at $a0 jr $ra # jump back to caller # strlen: given string stored at address in $a0 # returns its length in $v0 strlen: # BUG: this does _not_ set t0 to zero ###add $t0,$t0,$zero # $t0 gets zero li $t0,0 # BUGFIX lenloop: lb $t1,0($a0) # get the first byte for first char in $a0 beq $t1,$zero,exitline # if $t1 == 0 (null terminator), exit # BUG: the increment here is wrong -- it should be 1 ###addi $a0,$a0,8 # else, increment to next byte of string for next char addi $a0,$a0,4 # else, increment to next byte of string # BUGFIX addi $t0,$t0,1 # increment $t0 for each char in string j lenloop # jump back up to loop exitline: # BUG: this stores the length at the _address_ pointed to in v0 ###sw $t0,0($v0) # store $t0 into $v0 to return lenght of string move $v0,$t0 # BUGFIX jr $ra # jump back to caller # BUG: this only compares the first character # strcmp: given strings s, t stored at addresses in $a0, $a1 # returns -1 if s < t; 0 if s == t, 1 if s > t strcmp: lb $t0,0($a0) # get byte of first char in string s lb $t1,0($a1) # get byte of first char in string t # lb $t3, 0($t0) # lb $t4, 0($t1) # BUG: this does not set t3 = 1 ###addi $t3,$t3,1 # get 1 to compare li $t3,1 # BUGFIX slt $t2,$t0,$t1 # if s[0] < t[0] $t2 = 1, else $t2 = 0 bne $t2,$t3,lessthan # if $t2 == 1, jump to lessthan slt $t2,$t1,$t0 # if t[0] < s[1], $t2 = 1, else $t2 = 0 beq $t2,$t3,greaterthan # if $t2 == 1, jump to greaterthan # BUG: this does not set v0 = 0 ###sw $zero,0($v0) # $v0 gets zero li $v0,0 # BUGFIX j end lessthan: # BUG: this does _not_ set t4 = -1 ###addi $t4,$t4,-1 # $t4 gets -1 li $t4,-1 # BUGFIX # BUG: this does not set v0 ###sw $t4,0($v0) # $v0 gets -1 move $v0,$t4 # BUGFIX j end # jump to end greaterthan: # BUG: this does _not_ set t4 = 1 ###addi $t4,$t4,1 # $t4 gets 1 li $t4,1 # BUGFIX # BUG: this does not set v0 ###sw $t4,0($v0) # $v0 gets 1 move $v0,$t4 # BUGFIX j end # jump to end end: jr $ra # BUG: the front of the list is _always_ s0 # insert: given address of front of list in $a0 # and address of string to insert in $a1, # inserts new linked-list node in appropriate place in list # ... # returns address of new front of list in $v0 (which may be same as old) insert: # BUG: should be -4 ###addi $sp,$sp,4 addi $sp,$sp,-4 # BUGFIX sw $ra,0($sp) lw $t9,0($a0) # load head of the list for later use lw $t0,0($a0) # load head of list into $t0 # BUG: anding a _pointer_ against 0xF0 makes _no_ sense # NOTE: better to use hex for bit patterns ###andi $t0,$t0,240 # bitwise and with 240 (1111 0000) to extract first 4 bits for pointer to string # BUGFIX # BUG: this block of code is on the right track, but, wrong # storing into a0 (the struct) for strcmp makes _no_ sense sw $t0,0($a0) # store $t0 into $a0 for strcmp call lb $t6,0($t0) # get the byte of the first string char in the list lw $t7,0($a1) # get address of string lb $t1,0($t7) # get the byte of the first char of the string # NOTE: while we can set these here, we're burning two regs across the # strcmp call -- cleaner to move this below the call addi $t3,$zero,1 # $t3 gets 1 addi $t4,$zero,-1 # $t3 gets -1 # be careful in this function may have a bug with front of the list alphloop: # slt $t2, $t1, $t0 #if $t1 < $t0, then $t2 = 1, else $t2 = 0 # beq $t2, $t3, put #if # beq $t2, $zero, nextchar # BUG: strcmp destroys the values of a0 and a1, so the second time through # here they have bogus values # BUGBAD: strcmp uses them as pointers to the _strings_ but here, we're using # a0 as a _struct_ pointer!!! jal strcmp # compare the strings in $a0 and $a1 move $t5,$v0 # move the value returned from strcmp into $t5 beq $t5,$t4,put # if $t5 == -1, then value is less and then put new string at head of list beq $t5,$t3,nextstring # if $t5 == 1, then the head of the list is larger than the string and go to next string beq $t5,$zero,close # check if it is zero, if so it is already in the list so step out nextstring: lw $t2,0($a0) # store pointer to next node in $t2 # NOTE: use hex for bit masks (eg 0x0F) # BUG: this makes no sense andi $t8,$t9,15 # get address of next node string beq $t8,$zero,put # if it points to null then add node at the end sw $t8,0($a0) # store into $a0 j alphloop # check against the next string in loop put: # NOTE: what is 8??? obviously, it's the size in bytes of a node, so the # comment should say that li $t5,8 # $t5 gets 8 move $a0,$t5 # $t5 moved into $a0 jal malloc # allocate size for node move $t5,$v0 # move address returned by malloc to $t5 sw $a1,0($t5) # store $a1 into address allocated beq $t2,$zero,front # node is at front of the list, so there is no need to update pointer sw $t2,4($t5) # store pointer to current node into new node addi $t0,$a0,-8 # subtract from the current node back one sw $t5,0($t0) # store new pointer into the node jr $ra front: sw $t5,0($s0) # make global reference to front of the node the new node if its at the front close: jr $ra 

这是清理,重构,纠正和可运行的代码。

我推荐几件事情:

(1)对于一个函数中的标签,为了避免与其他函数的冲突,标签应该以函数名为前缀(例如你的trim函数[我改名为nltrim ],你有一个标签strloop [我重命名为nltrim_loop ])

(2)评论应该用现实世界的术语描述意图,而不仅仅描述实际的asm指令。

我意识到你刚刚开始,但(例如):

 addi $t3,$zero,7 # sets the value of $t3 to 7 

应该用更具描述性的内容来代替:

 addi $t3,$zero,7 # count = 7 

(3)一般的规则是在你所做的每一行上加上一个侧栏评论。 这就是我所做的,主要是。 但是,对于一些样板,这是很好理解,评论可能是矫枉过正的[实际上可能会干扰可读性]。

例如,为函数build立栈帧的代码和在函数退出时从该帧中恢复的代码是很好理解的。 因此,也许在顶部的单个块注释,如# set up stack frame为几行# set up stack frame# restore from stack frame底部的# restore from stack frame而在每个inst

(4)保持边栏评论的简短,以便它们适合80列。 如果您需要更多,请将注释提升至指令上方的全行块注释[并根据需要使用多行]

(5)对于困难/复杂的东西,可以使用伪代码或实际的C [或您select的语言]进行原型开发。 这是一个合理的假设,任何人编写(或阅读)asm代码都至less熟悉一种高级语言[C是最有可能的]。

对于结构代码,我在顶部块注释中添加了一个C结构定义。 在insert例程中,我在顶部注释块中添加了C伪代码。 对于asm的侧边栏注释经常被称为伪代码中的符号和动作

实际上,即使对于更简单的function,也要做这样的原型devise,即使不把代码添加为注释,也是有好处的。 (例如)在编写strcmp时可能会有所帮助

(6)保持代码尽可能简单。 当代码不必要地复杂时,就可以很容易地在你的程序逻辑中引入错误或者使用不正确的指令来实现这个逻辑。 这也使得以后很难发现这些错误。

(例如)在某些情况下,你的代码正在加载一个寄存器,只能在稍后移动。 因此,使用2-3个只有一个是必要的。 尽量减less不必要的寄存器移动[不只是为了速度,而是简单的代码]。

例如,你的strcmp有24行,只比较第一个字符(即一个bug),并有几个分支。 我的版本只有12行,完整的string比较,是一个简单的循环。

同样,在你的插入代码中, insert_here [not used]是17行, insert是47行,共计64行。我的工作版本是31行。

注意:我使用.eqv伪操作来“定义”结构偏移量。 我使用mars ,这适用于它,但我不知道是否spim支持.eqv 。 您可以始终对偏移进行硬编码,但会使代码变得不可读,容易出错。 有10个元素的结构,这种forms是非常方便的。 大多数其他汇编器都有某种.eqv等价的forms。

无论如何,这是代码:

 # Global symbols # struct node { # struct node *node_next; # char *node_str; # }; .eqv node_next 0 .eqv node_str 4 .eqv node_size 8 # sizeof(struct node) # NOTE: we don't actually use this struct # struct list { # struct node *list_head; # struct node *list_tail; # }; .eqv list_head 0 .eqv list_tail 4 # string routines .globl read_string .globl strcmp .globl strlen .globl nltrim # list routines .globl insert .globl print_list .globl main # pseudo-standard library .globl get_string .globl malloc .globl print_newline .globl print_string # Constants .data MAX_STR_LEN: .word 50 STR_NEWLINE: .asciiz "\n" STR_ENTER: .asciiz "enter a string: " # global registers: # s0 -- list head pointer (list_head) # Code .text # main: repeatedly gets strings from user and enters them in list # until a string of length less than two is entered; # prints list in order when done # main: li $s0,0 # list_head = NULL main_loop: # prompt user for string la $a0,STR_ENTER jal print_string # read in string from user jal read_string # save the string pointer as we'll use it repeatedly move $s1,$v0 # strip newline move $a0,$s1 jal nltrim # get string length and save the length move $a0,$s1 jal strlen # stop if given empty string blez $v0,main_exit # insert the string jal insert j main_loop main_exit: move $a0,$s0 jal print_list jal print_newline # exit simulation via syscall li $v0,10 syscall ################################################## # String routines # # read_string: allocates MAX_STR_LEN bytes for a string # and then reads a string from standard input into that memory address # and returns the address in $v0 read_string: addi $sp,$sp,-8 sw $ra,0($sp) sw $s0,4($sp) lw $a1,MAX_STR_LEN # $a1 gets MAX_STR_LEN move $a0,$a1 # tell malloc the size jal malloc # allocate space for string move $a0,$v0 # move pointer to allocated memory to $a0 lw $a1,MAX_STR_LEN # $a1 gets MAX_STR_LEN jal get_string # get the string into $v0 move $v0,$a0 # restore string address lw $s0,4($sp) lw $ra,0($sp) addi $sp,$sp,8 jr $ra # nltrim: modifies string stored at address in $a0 so that # first occurrence of a newline is replaced by null terminator nltrim: li $t0,0x0A # ASCII value for newline nltrim_loop: lb $t1,0($a0) # get next char in string beq $t1,$t0,nltrim_replace # is it newline? if yes, fly beqz $t1,nltrim_done # is it EOS? if yes, fly addi $a0,$a0,1 # increment by 1 to point to next char j nltrim_loop # loop nltrim_replace: sb $zero,0($a0) # zero out the newline nltrim_done: jr $ra # return # strlen: given string stored at address in $a0 # returns its length in $v0 # # clobbers: # t1 -- current char strlen: move $v0,$a0 # remember base address strlen_loop: lb $t1,0($a0) # get the current char addi $a0,$a0,1 # pre-increment to next byte of string bnez $t1,strlen_loop # is char 0? if no, loop subu $v0,$a0,$v0 # get length + 1 subi $v0,$v0,1 # get length (compensate for pre-increment) jr $ra # return # strcmp: given strings s, t stored at addresses in $a0, $a1 # returns <0 if s < t; 0 if s == t, >0 if s > t # clobbers: t0, t1 strcmp: lb $t0,0($a0) # get byte of first char in string s lb $t1,0($a1) # get byte of first char in string t sub $v0,$t0,$t1 # compare them bnez $v0,strcmp_done # mismatch? if yes, fly addi $a0,$a0,1 # advance s pointer addi $a1,$a1,1 # advance t pointer bnez $t0,strcmp # at EOS? no=loop, otherwise v0 == 0 strcmp_done: jr $ra # return # insert: inserts new linked-list node in appropriate place in list # # returns address of new front of list in $s0 (which may be same as old) # # arguments: # s0 -- pointer to node at front of list (can be NULL) # s1 -- address of string to insert (strptr) # # registers: # s2 -- address of new node to be inserted (new) # s3 -- address of previous node in list (prev) # s4 -- address of current node in list (cur) # # clobbers: # a0, a1 (from strcmp) # # pseudo-code: # // allocate new node # new = malloc(node_size); # new->node_next = NULL; # new->node_str = strptr; # # // for loop: # prev = NULL; # for (cur = list_head; cur != NULL; cur = cur->node_next) { # if (strcmp(new->node_str,cur->node_str) < 0) # break; # prev = cur; # } # # // insertion: # new->node_next = cur; # if (prev != NULL) # prev->node_next = new; # else # list_head = new; insert: addi $sp,$sp,-4 sw $ra,0($sp) # allocate a new node -- do this first as we'll _always_ need it li $a0,node_size # get the struct size jal malloc move $s2,$v0 # remember the address # initialize the new node sw $zero,node_next($s2) # new->node_next = NULL sw $s1,node_str($s2) # new->node_str = strptr # set up for loop li $s3,0 # prev = NULL move $s4,$s0 # cur = list_head j insert_test insert_loop: lw $a0,node_str($s2) # get new string address lw $a1,node_str($s4) # get current string address jal strcmp # compare them -- new < cur? bltz $v0,insert_now # if yes, insert after prev move $s3,$s4 # prev = cur lw $s4,node_next($s4) # cur = cur->node_next insert_test: bnez $s4,insert_loop # cur == NULL? if no, loop insert_now: sw $s4,node_next($s2) # new->node_next = cur beqz $s3,insert_front # prev == NULL? if yes, fly sw $s2,node_next($s3) # prev->node_next = new j insert_done insert_front: move $s0,$s2 # list_head = new insert_done: lw $ra,0($sp) addi $sp,$sp,4 jr $ra # print_list: given address of front of list in $a0 # prints each string in list, one per line, in order print_list: addi $sp,$sp,-8 sw $ra,0($sp) sw $s0,4($sp) beq $s0,$zero,print_list_exit print_list_loop: lw $a0,node_str($s0) jal print_string jal print_newline lw $s0,node_next($s0) # node = node->node_next bnez $s0,print_list_loop print_list_exit: lw $s0,4($sp) lw $ra,0($sp) addi $sp,$sp,8 jr $ra # Pseudo-standard library routines: # wrappers around SPIM/MARS syscalls # # assumes buffer to read into is in $a0, and max length is in $a1 get_string: li $v0,8 syscall jr $ra # malloc: takes one argument (in $a0) which indicates how many bytes # to allocate; returns a pointer to the allocated memory (in $v0) malloc: li $v0,9 # SPIM/MARS code for "sbrk" syscall jr $ra # print_newline: displays newline to standard output print_newline: li $v0,4 la $a0,STR_NEWLINE syscall jr $ra # print_string: displays supplied string (in $a0) to standard output print_string: li $v0,4 syscall jr $ra 

更新:

我同意逐行的意见,因为它帮助我明确地知道我打算访问哪些寄存器(或者在前面的例子中弄乱了)。

理由很简单。 想象一下,相反:一个大的[5000行] asm文件没有评论,已知有一个错误。 你不能相信逻辑/algorithm[它可能有错误]。 你不能相信实现[它可能有错误]。 每当我遇到这样的情况,我就像前面所描述的那样添加注释,甚至是查找错误(即我正在学习algorithm和代码)。

这是在做一个代码审查。 即使文件已经有了评论,我也会这样做。 我经常为我刚写的代码做这个评论,我认为它是“完整的”[即所有需要写的代码都已经]。

如果我在一天晚些时候结束,我会在第二天做第一件事。 通常,“在其上面睡觉”可以很容易地发现在前一天我没有发现的错误(因为我还是“太靠近”问题了)。 如果我正在写的东西要花上好几天的时间,我总是把前一天的工作作为第一件事来回顾。

即使你的原始评论像(2),它也帮助我find你的“错字”错误。 当我看到add $t1,$t1,$zero #get zero注释不匹配,很容易find/修复。 通过debugging器,代码的代码会变得十分困难。

评论总是帮助。 当原来的编码insert ,我有:

  jal strcmp # compare them -- new < cur? bgtz $v0,insert_now # if yes, insert after prev 

我从高到低的输出。

起初,我怀疑strcmp因为它同样是新代码。 我通常在查看对它的调用之前,检查下级function。 我做了一个strcmp代码审查,似乎很好。 但是,我仍然不相信。 我为strcmp写了一些诊断代码[unit testing],但是通过了。

然后,我注意到上面insert的意见和代码。 修复很简单:将bltz更改为bltz

另一个好的规则是:不要将[将错误引入] 现有 [工作]代码。

当我第一次审查print_list ,我想:“它正在使用[和捣毁] s0”。 这是可以的,因为在调用之后,程序正在终止。 但是,如果它被称为多次。 我错过了你在堆栈上保存/恢复s0的事实[我在读时意识到]。

令人耳目一新的看到一个像我这样的新手感受如此鼓舞

在某些时候,我们都是新手。 没有伤害,没有犯规。

即使是老手程序员也会造成错误[有时是多个/每天]。 虫虫不是对人的灵魂/性格的控诉。 错误只是作为程序员的正常副产品(就像查找/修复它们一样)。

国际海事组织的关键是:

(1)愿意学习

(2)承认错误(例如)肯尼迪总统(在“猪湾”之后): “错误不是错误,如果我们承认错误”

(3)最重要的是,离开自我

最差的程序员,当报告错误[或怀疑错误]是那些:

(1)说他们的代码正在工作[甚至没有检查错误报告是否有价值]。

(2)否认这个错误并不是真正的错误[当它是]

(3)拒绝产生[或接受]可以/可以certificate/反驳错误的testing用例

(4)[故意]“慢”来产生错误修复[这不像新代码那么有趣]

(5)在松弛的时候,拒绝“清理” 正在工作的代码,但是结构不好[ 应该被重构]

(6)鄙视顾客(即“他们都是白痴”)

国际海事组织(IMO),另一方面, 好的程序员在涉及到错误[或潜在的错误]方面是积极主动的

在我所在的一家公司,我们有一个没有明显错误的发货产品(一个实时video处理平台)。 我们在闲暇时间。 但是,我的老板(谁也是一个好程序员),我怀疑一些代码。 没有错误报告,没有确凿的证据,只是一个预感。 所以,我们做了一个评论。

果然,有一个错误。 但是,这只会触发一个模糊的边缘案例。 我们相信客户永远都看不到它,因为尽pipe我们所有的testingvideo都是在我们的实验室里,但实际上我们 从来没有亲自看过。 我们只能通过代码审查find它。 但是, “错误是错误” ,所以我开始修复。

大约两周之后,我们的主要客户的客户支持代表在他们看到的video中出现了一些间歇性失真报告(大约每2-3天一次)。

这个扭曲可能来自我正在处理的错误吗? 我还没有完整的解决scheme,但是到那个时候,我确实有一个可能会产生错误的unit testing。 在实验室中,我为代表启动了它。 他说:“是的,就是这样 – 客户所看到的扭曲”

这个bug大约在3个月前就已经出现了。 客户只是有不同的video,这使得错误发生的可能性更大。

通过积极主动,我们能够(诚实地)告诉客户我们已经“处于最佳状态”,我们缩短了客户修复时间两周的时间。 这两者都使我们对他们感兴趣[即他们从我们那里买了更多的装备]。