linked-list mips singly-linked-list

linked list - Lista vinculada de MIPS



linked-list singly-linked-list (1)

Estoy confundido exactamente sobre cómo crear estructuras en MIPS. Quiero crear una implementación de lista vinculada que calcule la longitud de las cadenas almacenadas y las clasifique en orden almacenado. Aquí está mi código hasta ahora:

# 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

¿A dónde debería ir desde aquí? Mi código se ensambla pero no hace nada después de leer en dos entradas.

Hiciste un gran trabajo con tu nivel de comentarios, estilo y diseño del programa. Algunos de los mejores que he visto en SO. En general, un buen esfuerzo.

Sin embargo, hubo errores.

He producido una versión anotada de su código y una refactorizada. Vea abajo.

Hubo una serie de errores en todo el código, no relacionados con la estructura o el código de inserción [hubo al menos 26 de esos errores].

Una frecuente a menudo repetía una sola instrucción incorrecta. Esto a menudo quería establecer un registro con una constante. Su código utilizó (por ejemplo) addi $t3,$t3,7 lugar del addi $t3,$t3,7 addi $t3,$zero,7 correcto addi $t3,$zero,7 . Los reemplacé con li $t3,7 . En algunos lugares, usaste la versión correcta, así que llamaría a esto un error tipográfico, pero había muchos de ellos.

Su strcmp solo comparó el primer carácter y no toda la cadena.

El código de inserción real era un poco complicado y mucho más complicado de lo necesario (por ejemplo, insert_here no se usó). También tenía algunos graves errores de lógica / implementación. Estaba en el camino correcto, pero, después de corregir tantos otros errores no relacionados, decidí reescribirlo en lugar de tratar de corregirlo.

Aquí está la versión anotada [reducida para los límites de espacio SO] donde reparé la mayoría de los errores de una línea [anotados con "BUG"], pero el código aún no es ejecutable y no hay correcciones a la lógica de estructura / inserción. Traté de permanecer fiel a su código original [perdone la limpieza de estilo gratuita]:

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_ (e.g. 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 (e.g. 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 (e.g. 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

Aquí está el código limpio, refactorizado, corregido y ejecutable.

Algunas cosas que recomiendo:

(1) Para las etiquetas dentro de una función, para evitar conflictos con otras funciones, las etiquetas deben tener como prefijo el nombre de la función (por ejemplo, para su función de trim [que nltrim a nltrim ], tenía un strloop etiqueta [que nltrim_loop a nltrim_loop ])

(2) Los comentarios deben describir la intención en términos del mundo real y no solo describir la instrucción asm real.

Me doy cuenta de que recién estás comenzando, pero (por ejemplo) esto:

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

Debería ser reemplazado por algo más descriptivo:

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

(3) La regla general es poner un comentario en la barra lateral en cada línea [lo que hiciste]. Es lo que hago, principalmente. Pero, para algunos repetitivos, eso se entiende bien, los comentarios pueden ser excesivos [y en realidad pueden interferir con la legibilidad].

Por ejemplo, el código que establece un marco de pila para una función y el código que se restaura a partir de ese marco en la salida de la función se entiende bien. Entonces, tal vez un solo comentario de bloque en la parte superior como # set up stack frame de la # set up stack frame para las pocas líneas y # restore from stack frame en la parte inferior en lugar de comentarios sobre cada inst

(4) Mantenga los comentarios de la barra lateral cortos para que quepan en 80 columnas. Si necesita más, eleve el comentario a un comentario de bloque de línea completo sobre la instrucción [y use tantas líneas como desee]

(5) Para cosas difíciles / complejas, está bien realizar un prototipo con pseudocódigo o C real [o un lenguaje de su elección]. Es razonable suponer que cualquiera que escriba [o lea] código asm esté familiarizado con al menos un lenguaje de alto nivel [C es el más probable].

Para el código de estructura, agregué una definición de estructura de C en un comentario de bloque superior. En la rutina de insert , agregué el pseudocódigo C en el bloque de comentarios superior. Los comentarios de la barra lateral para el ASM a menudo se refieren a los símbolos y acciones en el pseudocódigo

En realidad, hacer este prototipo incluso para funciones más simples tiene beneficios [incluso si no agrega el código como comentarios]. (por ejemplo) Puede haber ayudado al escribir su strcmp

(6) Mantenga el código lo más simple posible. Cuando el código es innecesariamente complicado, es muy fácil introducir errores en la lógica de su programa o usar instrucciones incorrectas para implementar esa lógica. También hace que sea difícil detectar estos errores más tarde.

(por ejemplo) En ciertos casos, su código estaba cargando un registro, solo para tener que moverlo más tarde. Por lo tanto, usando 2-3 insts donde solo era necesario uno. Intente minimizar el movimiento innecesario del registro [no solo por la velocidad, sino por un código más simple].

Por ejemplo, su strcmp tenía 24 líneas, y solo comparó el primer carácter [es decir, un error], y tenía varias ramas. Mi versión tenía solo 12 líneas, comparaba la cadena completa y era un bucle simple.

Del mismo modo, en su código de inserción, insert_here [no utilizado] tenía 17 líneas e insert tenía 47 líneas para un total de 64. Mi versión de trabajo tenía 31 líneas.

Nota: Utilicé el pseudo-op .eqv para "definir" las compensaciones de estructura. Uso mars y esto funciona, pero no sé si spim admite .eqv . Siempre puede codificar las compensaciones, pero hace que el código sea menos legible y propenso a errores. Con estructuras que tienen [digamos] 10 elementos, alguna forma de esto es bastante útil. La mayoría de los otros ensambladores tienen alguna forma de equivalente .eqv .

De todos modos, aquí está el código:

# 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

ACTUALIZAR:

Estoy de acuerdo con los comentarios línea por línea, ya que me ayuda a entender exactamente a qué registros pretendía acceder (o desordenar en el caso anterior).

La razón es simple. Imagine lo contrario: un archivo asm grande [5000 líneas] sin comentarios que se sabe que tiene un error. No puede confiar en la lógica / algoritmo [puede tener el error]. No puede confiar en la implementación [puede tener el error]. Cada vez que recibo un caso como ese, agrego los comentarios como he descrito antes, incluso buscando el error (es decir, estoy aprendiendo el algoritmo y el código mientras hago esto).

Esto está haciendo una revisión de código. Lo haré incluso si el archivo ya tiene comentarios [como el suyo]. A menudo hago esta revisión para el código que acabo de escribir que creo que está "completo" [es decir, todo el código que debe escribirse ha sido].

Si termino tarde en el día, haré la revisión como lo primero al día siguiente. A menudo, "dormir en él" hace que sea fácil detectar errores que no habría encontrado en una revisión el día anterior [porque todavía estaba "demasiado cerca" del problema]. Si lo que estoy escribiendo tomará varios días, siempre reviso el trabajo del día anterior como lo primero.

Incluso con sus comentarios originales que fueron como (2), me ayudó a encontrar sus errores tipográficos. Cuando vi add $t1,$t1,$zero #get zero la falta de coincidencia de comentarios facilitó la búsqueda / reparación. Sería 10 veces más difícil recorrer el código con un depurador.

Los comentarios siempre ayudan. Cuando originalmente codificaba el insert , tenía:

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

Obtuve una salida alta a baja.

Al principio, sospeché que strcmp era un código [igualmente] nuevo. Normalmente reviso la función de nivel inferior antes de revisar las llamadas a ella. Hice una revisión de código de strcmp y me pareció bien. Pero, todavía no estaba convencido. Escribí un código de diagnóstico [pruebas unitarias] para strcmp , pero pasó.

Luego, noté los comentarios frente al código en el insert anterior. La solución fue fácil: cambie bgtz a bltz .

Otra buena regla es: no rompa [introduzca un error en] el código [de trabajo] existente .

Cuando revisé por primera vez print_list , pensé: "está usando [y trashing] s0". Esto estaba bien porque después de llamarlo, el programa estaba terminando. Pero no, si se llamara varias veces. Me había perdido el hecho de que estabas guardando / restaurando s0 en la pila [que me di cuenta en la segunda lectura].

Es refrescante ver a un experimentado ser tan alentador para un novato como yo

Todos hemos sido novatos en algún momento. Sin daño, sin falta.

Incluso los programadores veteranos crean errores [a veces, varios / día]. Los errores no son una acusación del alma / carácter de uno. Los errores son simplemente un subproducto normal de ser un programador [al igual que encontrarlos / corregirlos].

OMI, las claves son:

(1) Voluntad de aprender

(2) Admitir errores (p. Ej.) Presidente Kennedy [después de la "Bahía de Cochinos"]: "Los errores no son errores, si los admitimos"

(3) Lo más importante, deja al ego fuera de él.

Los programadores más débiles , cuando se informa un error [o sospecha de error] son ​​los que:

(1) Digamos que su código está funcionando [sin siquiera verificar si el informe de error tiene mérito].

(2) Negar el error como realmente no es un error [cuando lo es]

(3) Negarse a generar [o aceptar] casos de prueba que puedan / prueben / refuten un error

(4) Sea [deliberadamente] "lento" para producir la corrección de errores [no es tan divertido como el nuevo código]

(5) Durante el tiempo de inactividad, rechace "limpiar" el código que funciona, pero que también está mal estructurado [y debe ser refactorizado]

(6) Tratar a los clientes con desdén [es decir, "todos son idiotas"]

OMI, los buenos programadores, por otro lado, son proactivos cuando se trata de errores [o errores potenciales ].

En una compañía en la que estaba, teníamos un producto de envío [una plataforma de procesamiento de video en tiempo real] que no tenía errores aparentes . Estábamos en el tiempo flojo. Pero mi jefe [que también era un buen programador] y yo sospechaba de algún código. Sin informe de errores, sin evidencia contundente, solo una corazonada. Entonces, hicimos una revisión.

Efectivamente, hubo un error. Pero, solo se desencadenaría para un caso de borde oscuro . Creíamos que era demasiado oscuro para que un cliente lo viera, ya que nunca lo habíamos visto en nuestro laboratorio a pesar de todos nuestros videos de prueba. Solo lo encontramos por la revisión del código. Pero, "los errores son errores" , así que comencé la corrección.

Aproximadamente dos semanas después, el representante de atención al cliente de nuestro principal cliente llega con un informe de cierta distorsión intermitente en el video que estaban viendo [aproximadamente una vez cada 2-3 días].

¿Podría esta distorsión provenir del error en el que estaba trabajando? Todavía no tenía mi solución completa, pero, para ese momento, tenía una prueba unitaria que podía generar el error. En el laboratorio, lo activé para el representante. Él dijo: "Sí, eso es, la distorsión que el cliente está viendo"

El error se había introducido unos 3 meses antes. El cliente solo tenía un video diferente al nuestro, lo que hacía que la aparición de errores fuera mucho más probable.

Al ser proactivos, pudimos [honestamente] decirle al cliente que "ya estábamos al tanto" y acortamos el tiempo de respuesta para el arreglo en dos semanas. Los dos nos hicieron dedicarnos a ellos [es decir, nos compraron más equipo].