Ejercicios 1

Ejercicio: Simulacro de examen 1

Tiempo: 2h
Objetivo:
- Practicar para el examen final de prácticas

Contenido

Enunciado
Solución comentada
Solución
Autores
Licencia
Enlaces

Enunciado

Aquí está disponible el Enunciado en PDF

Solución comentada

Antes de empezar a escribir código, hay que pensar sobre el problema, y entender y procesar toda la información que se nos da. En total se nos pide que codifiquemos 4 partes: un programa principal y 3 subrutinas

Análisis general

Haciendo un primer análisis, vemos que hay dos niveles de llamadas a subrutina. El programa principal llama a la función procesar(), y ésta a su vez a las funciones copiar() y upper(), en ese orden. En este diagrama lo vemos representado

Las funciones copiar() y upper() son funciones hoja. Por tanto, NO es necesario almacenar la dirección de retorno al nivel superior, ya que se encuentra guardada en el registro ra. En principio no necesitamos crear la pila en ellas, salvo que en su implementación la necesitásemos para algo

Sin embargo la función procesar() es una función intermedia: realiza llamadas a subrutinas de niveles inferiores. Es obligatorio el uso de la pila en este caso, para guardar la dirección de retorno. A lo mejor necesitamos la pila para algo más, pero al menos hay que crearla para guardar la dirección de retorno. Por ello, usamos la pila mínima, de 16 bytes

Programa principal. Primera iteración

Lo siguiente es hacernos una idea del programa principal. Todavía no lo podemos implementar completamente, porque no tenemos implementada la función procesar(), pero sí podemos entenderlo y dejar establecida una plantilla. Además, nos servirá para probar temporalmente las funciones upper() y copiar(), antes de llamarlas desde procesar()

Leyendo el enunciado, lo primero que hace el programa principal es pedir una cadena al usuario. Será nuestra cadena origen. Esta es una cadena definida en tiempo de ejecución. Tendremos que reservar memoria para almacenarla. ¿Cuánto reservamos?. En la especificación (enunciado) no nos lo han dado, por tanto lo tendremos que dimensionar nosotros. Usaremos la constante MAX. Damos por ejemplo el valor 100 (pero también valdría 50, 1024...)

   .eqv MAX  100

En el segmento de datos reservamos el espacio para esta cadena origen:

src_cad:    .space MAX

Además necesitaremos espacio para almacenar la cadena procesada. La cadena original se copiará a otra zona de la memoria y se pasará a mayúsculas. La cadena procesada tiene la misma longitud que la original, por lo que reservamos el mismo espacio: MAX

dst_cad:    .space MAX

Tenemos que pedir la cadena al usuario, imprimir la cadena procesasa, luego la original y finalmente terminar. Es decier, que tendremos que invocar a los servicios READ_STRING, PRINT_STRING y EXIT del sistema operativo. En el examen tenemos que hacer el programa desde cero, por lo que no disponemos del fichero sercicios.asm. Bueno, no es problema. Sí que tenemos acceso a la documentación del RARs, donde están los códigos de los servicios. Los miramos y nos creamos las constantes para acceder a ellos:

#-- Servicios del S.O
	.eqv PRINT_STRING 4
	.eqv READ_STRING  8
	.eqv EXIT         10

Con toda esta información ya tenemos una primera plantilla de nuestro programa principal, que luego que habrá que modificar para adaptar a los detalles de la llamada a la función de procesar

#--- Programa principal

	#-- Servicios del S.O
	.eqv PRINT_STRING 4
	.eqv READ_STRING  8
	.eqv EXIT         10
	.eqv MAX  100

	.data
	
msg1:	.string "\nIntroduce una cadena: "
msg2:   .string "\nCadena procesada: "
msg3:   .string "\nCadena original : "

	#-- Espacio para cadena original
src_cad:    .space MAX

	#-- Espacio para cadena destino
dst_cad:    .space MAX

	.text
	
	#-- Imprimir mensaje 1
	la a0, msg1
	li a7, PRINT_STRING
	ecall
	
	#-- Pedir cadena al usuario
	la a0, src_cad
	li a1, MAX
	li a7, READ_STRING
	ecall
	
	#-- Llamar a procesar
        #-- POR IMPLEMENTAR

	#-- Imprimir mensaje 2
	la a0, msg2
	li a7, PRINT_STRING
	ecall
		
	#-- Imprimir cadena procesada
	la a0, dst_cad
	li a7, PRINT_STRING
	ecall
	
	#-- Imprimir mensaje 3
	la a0, msg3
	li a7, PRINT_STRING
	ecall
	
	#-- Imprimir cadena original
	la a0, src_cad
	li a7, PRINT_STRING
	ecall
	
	#-- Terminar
	li a7, EXIT
	ecall

Función upper()

Antes de implementar la función *upper()**, hay que entender muy bien sus parámetros de entrada y salida. Un error en ellos significaría que estamos violando las especificaciones, que es lo peor que nos puede ocurrir. En ingeniería, las especificaciones son sagradas. No se pueden violar

El enunciado nos dice que la función upper() tiene un único parámetro, que es el puntero a la dirección de la cadena a convertir a mayúsculas. Siguiendo el convenio de la ABI del RISC-v, este parámetro habrá que pasárselo por el registro a0 (¡¡y sólo por ese!!!. Si se pasa por otro registro, se viola el convenio, y esto es algo también MUY GRAVE)

Ahora que lo entendemos, nos hacemos una plantilla de upper(). Su punto de entrada será el nombre de la función: upper, por lo que lo usaremos como etiqueta (y la haremos global porque está en un fichero separado del principal)

#--------------------------------------
#--- SUBRUTINA upper
#---
#--- ENTRADA:
#---   a0:  Puntero a la cadena
#---
#--- SALIDA:
#--    No devuelve nada
#--------------------------------------

	.globl upper
	
	.text
	
       #--- Punto de entrada
upper:
       #-- No es necesario crear pila, porque es una funcion hoja
       #-- y por tanto no hay que guardar la direccion de retorno 

       #-- Implementacion de la funcion
       #-- Por hacer....

       #-- Punto de salida
       ret

Ahora ya podemos implementar la funcion upper(). En el enunciado no nos dan ningún algoritmo para su implementación, por lo que lo elegimos nosotros. Implementamos el que queramos. Los más fáciles son los aloritmos iterativos: recorreremos la cadena leyendo los caracteres. Si están en el intervalo 'a'-'z' les restamos 32 para convertirlos a mayúsculas y en caso contrario los dejamos como están. Una función muy parecida ya la hicimos en los ejercicios. Su implementación completa es:

#--------------------------------------
#--- SUBRUTINA upper
#---
#--- ENTRADA:
#---   a0:  Puntero a la cadena
#---
#--- SALIDA:
#--    No devuelve nada
#--------------------------------------

	.globl upper
	
	.text
	
upper:
	#-- Es una funcion hoja: No llama a otras
	#-- no necesitamos crear pila

bucle:

	#-- a0 apunta a la cadena
	
	#-- Leer caracter actual
	lb t0, 0(a0)
	
	#-- Si es cero se termina
	beq t0, zero, fin
	
	#-- Si el caracter es mennor que 'a': no se toca
	li t1, 'a'
	blt t0, t1, next
	
	#-- Si el caracter es mayor que 'z': no se toca
	li t1, 'z'
	bgt t0, t1, next
	
	#-- Es un caracter entre 'a' y 'z': pasarlo a mayusculas
	addi t0, t0, -32
	
	#-- Almacenarlo
	sb t0, 0(a0)
	
next:
	#-- Apuntar al siguiente caracter
	addi a0, a0, 1
	
	b bucle
	
fin:
	#-- PUnto de salida
	ret

Mientras la implementamos, hay que probarla. Para ello modificamos el programa principal temporalmente. Por ejemplo, al principio creamos el código para pasarle una cadena (definida en tiempo de compilación, por ejemplo) e imprimir el resultado, para asegurarnos que funciona correctamente

Función copiar()

Para implementar la función copiar() seguimos los mismos primeros pasos. Primero nos aseguramos de entender perfectamente los argumentos de esta función, para no violar la especificación. Hay dos argumentos, el primero es un puntero a la cadena original, y el segundo el puntero a la zona de memoria donde copiar la cadena. No hay ningún parámetro de retorno

Por tanto, según nos dice el convenio del ABI del risc-v, usaremos el registro a0 para el primer parámetro: el puntero a la cadena origen, y el registro a1 para el puntero a la cadena destino. ¡¡EN ESE ORDEN!!. Cualquier otro uso de los registos violaría la especificación

La pantilla de nuestra función quedaría así:

#--------------------------------------
#-- SUBRUTINA copiar()
#--
#-- ENTRADAS:
#--    a0: Puntero cadena origen
#--    a1: Puntero cadena destino
#--
#-- DEVUELVE: Nada
#--------------------------------------

	.globl copiar
	
	.text
	
copiar:	

       #--- Es una funcion Hoja: No realiza ninguna llamada a otra subrutina
       #-- No hace falta crear la pila

       #-- Implementacion de la funcion
       #-- Por hacer....

       #-- Punto de salida
       ret

Ya sólo nos queda implementar la función de copiar. Como tampoco nos especifican el algoritmo, podemos usar el que nosotros queramos. Por ejemplo uno iterativo. Esto ya lo hemos hecho en los ejercicios, por lo que no daré más explicaciones. Sólo un recordatorio: ¡al copiar la cadena también hay que copiar el '\0' final!

#--------------------------------------
#-- SUBRUTINA copiar()
#--
#-- ENTRADAS:
#--    a0: Puntero cadena origen
#--    a1: Puntero cadena destino
#--
#-- DEVUELVE: Nada
#--------------------------------------

	.globl copiar
	
	.text
	
copiar:	

	#--- Es una funcion Hoja: No realiza ninguna llamada a otra subrutina
	#-- No hace falta crear la pila

bucle:

	#--- Leer caracter actual
	lb t0, 0(a0)
	
	#-- Si es \0, terminar
	beq t0, zero, fin
	
	#-- Copiar el caracter a la cadena destino
	sb t0, 0(a1)
	
	#-- Incrementar los punteros
	addi a0, a0, 1
	addi a1, a1, 1
	
	#-- Repetir
	b bucle
	
	
fin:
	#-- Copiar el \0 al final de la cadena destino
	sb zero, 0(a1)
	
	ret

Para probarlo usamos temporalmente el programa principal. Eliminamos lo que habíamos hecho para probar la función upper() y colocamos un nuevo código para probar la función de copia. Por ejemplo que pida a al usuario una cadena, que la copie, y que se impriman tanto la copia como la original

La llamada a copiar debe ser así:

la a0, src_cad  #-- direccion de la cadena fuente
la a1, dst_cad  #-- direccion de la cadena destina
jal copiar

Función procesar()

Hacemos un análisis similar como en el caso de las funciones anteriores. La función procesar() tiene dos argumentos, el puntero a la cadena fuente y el puntero a la cadena destino, que se tienen que pasar por los registros a0 y a1

Además, como es una función intermedia, debemos usar la pila para almacenar la dirección de retorno. Usamos la pila mínima, que es de 16 bytes. Por tanto, la plantilla de esta función sería:

#---------------------------------------------------------------------------
#-- Subrutina procesar
#--
#-- ENTRADAS:
#--  a0: Puntero a cadena origen
#--  a1: Puntero a cadena destino
#--
#-- SALIDAS:
#---  Ninguna
#----------------------------------------------------------------------------

	.globl procesar
	
	.text
	
procesar:

        #-- Es una subrutina intermedia. Necesitamos crear
        #-- la pila para guardar la direccion de retorno
        addi sp, sp, -16
        
        #-- Guardar la direccion de retorno
        sw ra, 12(sp)
        
        #-- Implementacion de la funcion
        #-- Por hacer...
        
        #-- Recuperar la direccion de retorno
        lw ra, 12(sp)
        
        #-- Liberar la pila
        addi sp, sp, 16

        #-- Punto de salida
	ret

La función procesar() copia la cadena fuente en la dirección destino y la pasa a mayúsculas. Para ello tenemos que invocar a las funciones copiar() y upper(). El pseudocódigo sería el siguiente:

def procesar(src, dst):
  copiar(src, dst)
  upper(dst)

La única precaución que hay que tener al implementarla es que encesitamos preservar el valor de la cadena destino. Al tenerlo en el registro a1 y llamar a la función de copiar, perdemos su valor. Por ello, es preciso guardarlo en la pila y recuperarlo tras la llamada a copiar

Esta sería la implementación final:

#---------------------------------------------------------------------------
#-- Subrutina procesar
#--
#-- ENTRADAS:
#--  a0: Puntero a cadena origen
#--  a1: Puntero a cadena destino
#--
#-- SALIDAS:
#---  Ninguna
#----------------------------------------------------------------------------

	.globl procesar
	
	.text
	
procesar:

        #-- Es una subrutina intermedia. Necesitamos crear
        #-- la pila para guardar la direccion de retorno
        addi sp, sp, -16
        
        #-- Guardar la direccion de retorno
        sw ra, 12(sp)
        
        #-- Guardar en la pila a1,  
        #-- con la direccion destino, porque la necesitaremos despues
        sw a1, 0(sp)  #-- Direccion destino
        
        #-- llamar a copiar
        jal copiar

        #-- Recuperar la direccion destino en a0
        lw a0, 0(sp)
        
        #-- Llamar a upper
        jal upper
        
        #-- Recuperar la direccion de retorno
        lw ra, 12(sp)
        
        #-- Liberaer la pila
        addi sp, sp, 16

	ret

Programa principal final

Para terminar, completamos el programa principal. Sólo hay que llamar a la función procesar() con los valores correctos de sus parámetros:

#--- Programa principal

	#-- Servicios del S.O
	.eqv PRINT_STRING 4
	.eqv READ_STRING  8
	.eqv EXIT         10
	.eqv MAX  100

	.data
	
msg1:	.string "\nIntroduce una cadena: "
msg2:   .string "\nCadena procesada: "
msg3:   .string "\nCadena original : "

	#-- Espacio para cadena original
src_cad:    .space MAX

	#-- Espacio para cadena destino
dst_cad:    .space MAX

	.text
	
	#-- Imprimir mensaje 1
	la a0, msg1
	li a7, PRINT_STRING
	ecall
	
	#-- Pedir cadena al usuario
	la a0, src_cad
	li a1, MAX
	li a7, READ_STRING
	ecall
	
	#-- Llamar a procesar
	la a0, src_cad
	la a1, dst_cad
	jal procesar

	#-- Imprimir mensaje 2
	la a0, msg2
	li a7, PRINT_STRING
	ecall
		
	#-- Imprimir cadena procesada
	la a0, dst_cad
	li a7, PRINT_STRING
	ecall
	
	#-- Imprimir mensaje 3
	la a0, msg3
	li a7, PRINT_STRING
	ecall
	
	#-- Imprimir cadena original
	la a0, src_cad
	li a7, PRINT_STRING
	ecall
	
	#-- Terminar
	li a7, EXIT
	ecall

Solución

Los cuatro ficheros pedidos son los siguientes:

Fichero main.s

#--- Programa principal

	#-- Servicios del S.O
	.eqv PRINT_STRING 4
	.eqv READ_STRING  8
	.eqv EXIT         10
	.eqv MAX  100

	.data
	
msg1:	.string "\nIntroduce una cadena: "
msg2:   .string "\nCadena procesada: "
msg3:   .string "\nCadena original : "

	#-- Espacio para cadena original
src_cad:    .space MAX

	#-- Espacio para cadena destino
dst_cad:    .space MAX

	.text
	
	#-- Imprimir mensaje 1
	la a0, msg1
	li a7, PRINT_STRING
	ecall
	
	#-- Pedir cadena al usuario
	la a0, src_cad
	li a1, MAX
	li a7, READ_STRING
	ecall
	
	#-- Llamar a procesar
	la a0, src_cad
	la a1, dst_cad
	jal procesar

	#-- Imprimir mensaje 2
	la a0, msg2
	li a7, PRINT_STRING
	ecall
		
	#-- Imprimir cadena procesada
	la a0, dst_cad
	li a7, PRINT_STRING
	ecall
	
	#-- Imprimir mensaje 3
	la a0, msg3
	li a7, PRINT_STRING
	ecall
	
	#-- Imprimir cadena original
	la a0, src_cad
	li a7, PRINT_STRING
	ecall
	
	#-- Terminar
	li a7, EXIT
	ecall

Fichero procesar.s

#---------------------------------------------------------------------------
#-- Subrutina procesar
#--
#-- ENTRADAS:
#--  a0: Puntero a cadena origen
#--  a1: Puntero a cadena destino
#--
#-- SALIDAS:
#---  Ninguna
#----------------------------------------------------------------------------

	.globl procesar
	
	.text
	
procesar:

        #-- Es una subrutina intermedia. Necesitamos crear
        #-- la pila para guardar la direccion de retorno
        addi sp, sp, -16
        
        #-- Guardar la direccion de retorno
        sw ra, 12(sp)
        
        #-- Guardar en la pila a1,  
        #-- con la direccion destinno, porque la necesitaremos despues
        sw a1, 0(sp)  #-- Direccion destino
        
        #-- llamar a copiar
        jal copiar

        #-- Recuperar la direccion destino en a0
        lw a0, 0(sp)
        
        #-- Llamar a upper
        jal upper
        
        #-- Recuperar la direccion de retorno
        lw ra, 12(sp)
        
        #-- Liberaer la pila
        addi sp, sp, 16

	ret

Fichero upper.s

#--------------------------------------
#--- SUBRUTINA upper
#---
#--- ENTRADA:
#---   a0:  Puntero a la cadena
#---
#--- SALIDA:
#--    No devuelve nada
#--------------------------------------

	.globl upper
	
	.text
	
upper:
	#-- Es una funcion hoja: No llama a otras
	#-- no necesitamos crear pila

bucle:

	#-- a0 apunta a la cadena
	
	#-- Leer caracter actual
	lb t0, 0(a0)
	
	#-- Si es cero se termina
	beq t0, zero, fin
	
	#-- Si el caracter es mennor que 'a': no se toca
	li t1, 'a'
	blt t0, t1, next
	
	#-- Si el caracter es mayor que 'z': no se toca
	li t1, 'z'
	bgt t0, t1, next
	
	#-- Es un caracter entre 'a' y 'z': pasarlo a mayusculas
	addi t0, t0, -32
	
	#-- Almacenarlo
	sb t0, 0(a0)
	
next:
	#-- Apuntar al siguiente caracter
	addi a0, a0, 1
	
	b bucle
	
fin:
	#-- PUnto de salida
	ret

Fichero copiar.s

#--------------------------------------
#-- SUBRUTINA copiar()
#--
#-- ENTRADAS:
#--    a0: Puntero cadena origen
#--    a1: Puntero cadena destino
#--
#-- DEVUELVE: Nada
#--------------------------------------

	.globl copiar
	
	.text
	
copiar:	

	#--- Es una funcion Hoja: No realiza ninguna llamada a otra subrutina
	#-- No hace falta crear la pila

bucle:

	#--- Leer caracter actual
	lb t0, 0(a0)
	
	#-- Si es \0, terminar
	beq t0, zero, fin
	
	#-- Copiar el caracter a la cadena destino
	sb t0, 0(a1)
	
	#-- Incrementar los punteros
	addi a0, a0, 1
	addi a1, a1, 1
	
	#-- Repetir
	b bucle
	
	
fin:
	#-- Copiar el \0 al final de la cadena destino
	sb zero, 0(a1)
	
	ret