Idear un programa y codificarlo en ARM y x86. Identificar pros y contras.
Esta cuestión ha sido, quizá, una de las más complejas.
Necesitábamos tener una idea que pudiera ser viable en ambas arquitecturas y que sirviera de comparativa básica, por lo que lo más factible sería una tarea de cómputo. Tras pensar bastante, nos decantamos por la generación de números amigos y perfectos.
Dos números enteros A y B son amigos (o amigables) si y solo sí la suma de los divisores de A (sin incluir a él mismo) es igual a B y viceversa. Un número C es perfecto si es amigo de sí mismo.
Esta primera idea nos pareció bastante adecuada, ya que se haría uso de bucles, comparaciones, funciones o subrutinas (y por tanto la pila), además de precisarse acceso a memoria y salida de datos (impresiones por pantalla).
El algoritmo que hemos ideado ha sido el siguiente:
Pasamos ahora a describir la implementación.
x86
En x86 hemos hecho uso de funciones de la API de C para escribir por pantalla (en Windows, importando msvcrt.dll). Partiendo de esto, el programa se reduce a generar los números amigos e ir imprimiéndolos.
Para generarlos, hemos seguido el diagrama de flujo tal cual. Para la generación de los divisores hemos usado una función (suma_divisores), que recibe el número cuyos divisores queremos sumar y una dirección de memoria donde almacenará la suma. Vamos a explicar paso por paso cómo hemos implementado la función.
Antes que nada, tenemos que aplicar cierto estándar en nuestras funciones. Si cada función tomase unos parámetros de entrada y utilizaran registros para llevar a cabo su tarea sin tener nada en cuenta, tendríamos cierta indeterminación en los datos de los que disponemos tras una llamada a una subrutina (a no ser que conociésemos perfectamente la implementación, lo cual sería, a pesar de todo, bastante tedioso). Para liberar al programador de dicha incertidumbre, se suelen cumplir unos procedimientos en la forma de entrar y salir de una función. Lo más común en x86 es usar la convención de llamadas de C. Para ello, en la entrada a la subrutina, tenemos que guardar Ebp en la pila y copiar el contenido de Esp a Ebp. Esto nos permite actuar sobre la pila con la seguridad de que luego podremos restaurar Ebp a la salida de la función. Así, a la salida, tendremos que restaurar Ebp y, por supuesto, saltar a la posición donde se realizó la llamada (RET).
suma_divisores:
Push Ebp
Mov Ebp, Esp
[...]
return_divisores:
Pop Ebp
Ret
Una vez dicho esto, entramos en el contenido de la función en sí. Antes que nada, vamos a aclarar la forma en la que generamos los divisores.
Por lo que la función nos queda así:
suma_divisores:
Push Ebp
Mov Ebp, Esp
Mov Ecx, 0
; Cargo en Edi la direccion donde guardaremos el sumatorio
Mov Edi, D[Ebp + 12]
; Calculo la mitad del numero
Mov Eax, D[Ebp + 8]
Mov Edx, 0
Mov Ebx, 2
Div Ebx
; Guardo la mitad en Ebx
Mov Ebx, Eax
inicio_divisores:
; Compruebo si se ha pasado ya de la mitad
Cmp Ecx, Ebx
Jg > return_divisores
; Siguiente numero
Inc Ecx
; Cargo en Eax el numero para saber si es divisor
Mov Eax, D[Ebp + 8]
Mov Edx, 0
Div Ecx
; Si en Edx esta el 0, es porque era divisor
Cmp Edx, 0
; Si no, salto al siguiente divisor
Jne inicio_divisores
; Añado el divisor al sumatorio
Add [Edi], Ecx
Jmp inicio_divisores
return_divisores:
Pop Ebp
Ret
Como podemos comprobar, primero hemos dividido el número entre dos para conocer los límites del bucle (los divisores de un número, sin incluirse él mismo, se encuentran desde 1 hasta su mitad, ambos inclusive). Esto lo guardamos en Ebx, inicializamos Ecx a 0 (divisor) y entramos en el bucle. El bucle es un 'while', por lo que comprueba las condiciones de parada al comienzo. Posteriormente se incrementa el divisor y se divide. Si el resto es 0, este divisor es sumado al dato al que apunta Edi, que será una dirección de memoria donde guardaremos el sumatorio. Cuando el bucle acabe, restauramos Ebp y volvemos al programa principal (desde donde se realizó la llamada).
Una vez hemos explicado la función que genera y suma los divisores, vamos a mostrar el código del programa principal:
inicio_bucle:
; Inicializar la memoria
Mov D[sumA], 0
Mov D[sumB], 0
; Guardar el numero 1
Mov [a], Ecx
; Sumo los divisores del primer numero
PushA
Invoke suma_divisores, Ecx, Addr sumA
Add Esp, 8
PopA
; Ahora tengo que comprobar si la suma es amiga con el primero
Mov Eax, D[sumA]
Mov [b], Eax
; Calculo los divisores de la suma
PushA
Invoke suma_divisores, Eax, Addr sumB
Add Esp, 8
PopA
; Comparo el resultado
Mov Eax, D[a]
Cmp Eax, D[sumB]
Jne > no_amigos ; No son amigos
Cmp Eax, D[b] ; Son perfectos
Je > perfectos
; Otro caso
PushAd
Invoke printf, "%d y %d son amigos%c", [a], [b], 10
Add Esp, 16
PopAd
Jmp > no_amigos
perfectos:
PushAd
Invoke printf, "%d es perfecto%c", [a], 10
Add Esp, 12
PopAd
no_amigos:
Inc Ecx
Cmp Ecx, [LIMITE]
Jbe inicio_bucle
Invoke system, "pause"
Xor Eax, Eax
Invoke ExitProcess, Eax
El procedimiento es el siguiente. Inicializamos los datos en memoria, ponemos el contador a 2 (ya que, por definición, el 1 no es perfecto) y empezamos a generar los números. ¿Cómo?
Al contador lo llamaremos A. Generamos la suma de los divisores de A, a la cual llamaremos B. Generamos ahora el sumatorio de los divisores de B. Si este último coincide con A, hay dos posibilidades:
- A y B son iguales, con lo cual estamos ante un número perfecto.
- A y B son distintos, con lo cual estamos ante dos números amigos.
Si A y el sumatorio de los divisores de B no coinciden, los números no son amigos, por lo que incrementaremos Ecx (A) y volveremos al comienzo del bucle. ¿Cuándo paramos?
Cuando A sea igual al límite impuesto, definido en la variable LIMITE.
ARM
En ARM hemos tenido muchos más problemas. Para empezar, vamos a indicar que debido a ciertos problemas que hemos tenido con el simulador (necesidad de ejecutarlo en sistema operativo de 32 bits, numerosos errores, etcétera) y a la falta de documentación del mismo (sobre todo en lo que respecta a llamadas al sistema) hemos decidido implementar el programa para que fuera ejecutado en una arquitectura ARM sobre un núcleo Linux. En concreto, lo hemos probado con un ARM11 de 32 bits bajo Raspbian (distribución basada en Debian, compilada para ARM), en una Raspberry Pi.
Nuestro programa está limitado a este entorno por el uso de llamadas al sistema específicas de Linux para realizar la salida de datos por pantalla. El ensamblador es completamente compatible con cualquier otro ARM.
Una vez dicho esto, pasamos a nuestro código. Antes que nada, empezaremos por analizar nuestra función que realiza la suma de divisores.
Comencemos primero por explicar el estándar que propone la documentación de ARM para la llamada a procedimientos. En ella se especifica que los registros r0 a r3 son usados para el paso de argumentos y la devolución de los resultados en la función, por lo que NO se garantiza que se preserven los datos de estos registros tras una llamada. Los registros r4 a r11 son usados como variables locales, es decir, tienen que conservarse tras llamar a una función. Para ello, el programador debe salvar dichos registros en la pila al entrar en la función (lo primero que se hace). Además de estos, el r14 también debe ser preservado, puesto que contiene la dirección de retorno. Si en nuestra función realizamos llamadas a otra función o subrutina, dicho valor será modificado, por lo que se recomienda salvarlo en la pila al igual que r0-r3. Una vez hayamos acabado la función, antes de volver a la ejecución del programa que realizó la llamada, tenemos que restaurar los valores de los registros r4-r11, teniendo en cuenta que también hemos salvado r14. Lo que se recomienda en estos casos es restaurar la dirección de retorno directamente sobre PC, para realizar el salto de forma inmediata. La llamada a estándar a una función quedaría así:
suma_divisores
PUSH {r4-r11, lr} ; Llamada a procedimiento estandar: guardar los registros de usuario r4-r11 y el registro que guarda la direccion de retorno r14
[...]
POP {r4-r11, pc} ; Restauro r4-r11 y copio la direccion de retorno al pc
Una vez que tenemos el preprotocolo y el postprotocolo de la función, vamos a pasar a implementarla. El procedimiento en rasgos generales es exactamente el mismo que en x86, por lo que el diagrama de flujo antes expuesto sería totalmente válido.
suma_divisores ; r0 <- numero, r1 <- hasta donde
PUSH {r4-r11, lr}
MOV r4, r0 ; r4 contiene el numero
MOV r5, r1 ; r5 contiene hasta donde buscaremos divisores
MOV r6, #1 ; r6 sera el divisor en potencia que iteramos
MOV r7, #0 ; r7 sera el sumatorio de los divisores que encontremos
sd_1 CMP r6, r5
BGT fin_divisores
MOV r0, r4
MOV r1, r6
BL div
CMP r1, #0
ADDEQ r7, r7, r6
ADD r6, r6, #1
B sd_1
fin_divisores
La función hace uso de los registros r0 y r1 para obtener los argumentos. r0 contendrá el número cuyos divisores buscamos y r1 contendrá el valor hasta donde queremos realizar dicha búsqueda. Designamos también 4 registros que serán usados como variables locales, del r4 al r7, conteniendo, respectivamente, el número (lo que hemos obtenido de r0), el límite superior (r1), el divisor que iteramos y el sumatorio hasta el momento.
Inicializamos los datos y entramos en un bucle. Dicho bucle va incrementando r6 hasta llegar al límite. En cada iteración, dividimos el número (r4) entre el divisor en potencia (r6). Si el resto es 0, sumamos dicho divisor a r7 (que contiene el sumatorio).
Cuando finaliza el bucle, copiamos el resultado a r0, que será usado para recibir el dato desde el programa principal.
Pasamos ahora a comentar, grosso modo, el programa principal. El funcionamiento de éste es muy similar al de x86.
Almacenamos el numero que estamos iterando en r4 (para que se preserve entre llamadas), calculamos su mitad (r7) y le paso ambos datos a suma_divisores (r0 y r1 respectivamente). Tras la llamada, tenemos en r0 la suma de los divisores de A, que la salvamos en r5. Calculamos ahora la mitad de r5 y la guardamos en r8. Volvemos a realizar la llamada a suma_divisores, pasando ambos parámetros por los registros r0 y r1 y obtenemos la suma de los divisores de B. Comprobamos si esa suma es igual que A. Si lo es, comprobamos si A es igual a B para determinar si son amigos o se trata de un perfecto, imprimimos lo que proceda y pasamos a la siguiente iteración. En el caso de que la suma de los divisores de B no sea A, pasamos a la siguiente iteración sin imprimir nada.
El principal problema que hemos experimentado en esta implementación ha sido realizar las impresiones. Para imprimir cadenas, realizamos una llamada al sistema, con la estructura siguiente:
MOV r2, r0 ; Guardo la longitud
MOV r0, #1 ; Flujo en el que se va a imprimir (1 = stdout, 2 = stderr).
MOV r1, r11 ; Direccion base del vector
MOV r7, #4
SVC #0
Realizamos una interrupción por software con el código 0 para que el sistema atienda nuestra petición. Lo que recibe el sistema es el flujo en el que se va a imprimir (r0), la dirección base del vector (r1), la longitud del mismo (r2) y un código indicado en la documentación que corresponde a imprimir cadena (el entero 4, en r7). Es decir, el sistema operativo imprimiría en stdout (representado por el entero 1) una cadena que empieza en la dirección indicada por r1 con longitud r2.
Obviamente, para hacer esto, necesitamos conocer primero la longitud. ¿Cómo lo hacemos?
Con otra función a la que hemos llamado strlen (igual que en C). En dicha función iteramos la dirección base hasta que encontramos el byte 0 (carácter terminador). Durante esas iteraciones, vamos incrementando un contador que, al final, será nuestra longitud.
strlen
PUSH {r4-r11, lr} ; Llamada a procedimiento estandar: guardar los registros de usuario r4-r11 y el registro que guarda la direccion de retorno r14
MOV r1, #0
while_longitud
LDRB r2, [r0], #1 ; Cargo el caracter y realizo un postincremento de r0
CMP r2, #0 ; Compruebo si es el caracter terminador
ADDNE r1, r1, #1 ; Si no hemos llegado al final, incrementamos el contador
BNE while_longitud ; Mientras no estemos en el \0, volver a ejecutar
MOV r0, r1 ; Copiamos el numero de caracteres a r0
POP {r4-r11, pc} ; Restauro r4-r11 y copio la direccion de retorno al pc
El siguiente problema que hemos tenido ha sido imprimir los números. Linux tiene una llamada para imprimir caracteres, pero no tiene llamada para imprimir enteros. Por ello, es necesario pasar los enteros a cadenas. Hemos hecho uso para ello de una implementación de la función 'iota' de C.
itoa
PUSH {r4-r11, lr}
MOV r4, r0
MOV r5, r1
MOV r0, r1
MOV r1, #10
BL div
SUB r5, r5, r0, LSL #3
SUB r5, r5, r0, LSL #1
CMP r0, #0
MOVNE r1, r0
MOV r0, r4
BLNE itoa
ADD r5, r5, #'0'
STRB r5, [r0], #1
POP {r4-r11, pc}
Tanto esta función como nuestra función que suma divisores precisan de la operación de división. Dicha función, al contrario de x86, no la proporciona el ensamblador de ARM, por lo que nos hemos visto obligados a programar una subrutina de división.
div
MOV r2, r0
MOV r3, r1
MOV r0, #0
MOV r1, #0
div_1 CMP r2, r3
BLT div_2
SUB r2, r2, r3
ADD r1, r1, #1
B div_1
div_2 MOV r0, r1
MOV r1, r2
MOV pc, lr
Y aquí nos vemos obligados a comentar algo. Nuestra función de división es simple. Resta el divisor tantas veces como pueda al dividendo. Pero, ¿por qué no salva los registros r4-r11 y r14? El procedimiento estándar indica que el programador de una función/subrutina tiene que garantizar que se preservan los registros r4 a r11 y que se vuelve al punto donde ha sido llamado (r14). Ahora bien, ¿realiza esta función alguna modificación sobre alguno de estos registros? No. El estándar de llamada a procedimientos de ARM también contempla esta posibilidad. No se indica cómo ha de hacerse (aunque si se aconseja), pero sí qué se tiene que garantizar. Y nosotros lo cumplimos, ya que únicamente hacemos uso de r0, r1, r2 y r3.
Veamos ahora rápidamente el programa principal.
MOV r4, #0
MOV r5, #0
MOV r6, #2
inicio_bucle
; Almaceno el numero que estamos iterando en r4 ('a')
MOV r4, r6
; Calculo la mitad de 'a'
MOV r0, r4
MOV r1, #2
BL div
; Ahora tengo en r0 el cociente de la division entera
; Guardo en r7 la mitad de 'a'
MOV r7, r0
; Sumo sus divisores sin incluir el mismo (desde 1 hasta r7)
MOV r0, r4
MOV r1, r7
BL suma_divisores
; Ahora tengo en r0 el sumatorio de los divisores
; Compruebo si esa suma es amiga con 'a'. Llamemosla 'b' (r5).
MOV r5, r0
; Calculo la mitad de 'b'
MOV r1, #2
BL div
; Ahora tengo en r0 el cociente de la division entera
; Guardo en r8 la mitad de 'b'
MOV r8, r0
; Sumo sus divisores sin incluir el mismo (desde 1 hasta r8)
MOV r0, r5
MOV r1, r8
BL suma_divisores
; Ahora tengo en r0 el sumatorio de los divisores
; Compruebo si esa suma es 'a'
CMP r0, r4
BNE fin_bucle
; Si estamos en este punto, es porque son amigos
; Necesitaremos imprimir al menos el primer numero
LDR r0,=buffer1
MOV r1, r4
BL itoa
; Ahora tengo en buffer1 a 'a' como char*
; Compruebo si a!=b. Si son distintos son amigos, si no, perfectos.
CMP r4, r5
BEQ perfectos
; Caso en el que son amigos --
; Paso el segundo numero a char*
LDR r0,=buffer2
MOV r1, r5
BL itoa
; Ahora tengo en buffer1 y buffer2 los numeros como char*
; Imprimo el primer numero
; 1.- Averiguo su longitud
LDR r11,=buffer1
MOV r0, r11
BL strlen
; 2.- Llamo al sistema para que lo imprima
MOV r2, r0 ; Guardo la longitud
MOV r0, #1 ; Flujo en el que se va a imprimir (1 = stdout).
MOV r1, r11 ; Direccion base del vector
MOV r7, #4
SVC #0
; Imprimo la cadena de amigos
; 1.- Llamo al sistema puesto que la longitud es conocida
LDR r1,=nAmigos
MOV r2, #13
MOV r0, #1
MOV r7, #4
SVC #0
; Imprimo el segundo numero
; 1.- Averiguo su longitud
LDR r11,=buffer2
MOV r0, r11
BL strlen
; 2.- Llamo al sistema para que lo imprima
MOV r2, r0 ; Guardo la longitud
MOV r0, #1 ; Flujo en el que se va a imprimir (1 = stdout).
MOV r1, r11 ; Direccion base del vector
MOV r7, #4
SVC #0
; Imprimo un salto de linea
; Llamo al sistema puesto que la longitud es conocida
MOV r0, #1
LDR r1,=endl
MOV r2, #2
MOV r7, #4
SVC #0
B fin_bucle
perfectos
; Caso en el que es perfecto --
; Imprimo el numero
; 1.- Averiguo su longitud
LDR r11,=buffer1
MOV r0, r11
BL strlen
; 2.- Llamo al sistema para que lo imprima
MOV r2, r0 ; Guardo la longitud
MOV r0, #1 ; Flujo en el que se va a imprimir (1 = stdout).
MOV r1, r11 ; Direccion base del vector
MOV r7, #4
SVC #0
; Imprimo la cadena perfectos
; 1.- Llamo al sistema puesto que la longitud es conocida
LDR r1,=nPerfec
MOV r2, #14
MOV r0, #1
MOV r7, #4
SVC #0
fin_bucle
ADD r6, r6, #1
LDR r0, nMAX
CMP r6, r0
BLE inicio_bucle
; Si ha acabado el bucle, finalizamos el programa
MOV r0, #0
MOV r7, #1
SVC #0
Hemos comentado el código de tal forma que sea más fácil entenderlo.
Ahora que lo tenemos todo, procedamos a realizar la comparativa entre ambas.
x86
|
ARM
|
|
Acceso a memoria
|
Inmediato desde (casi) cualquier instrucción, usando los corchetes y
una etiqueta.
|
Necesidad de guardar el dato en un registro y luego ejecutar la
instrucción que necesitaba el dato con dicho registro intermedio.
|
Bifurcaciones
|
Instrucción CMP para establecer los flags e instrucciones con códigos
condicionales.
|
Instrucción CMP para establecer los flags e instrucciones con códigos
condicionales.
|
Bucles
|
Instrucciones básicas para bucles (como loop). Necesidad de
implementar otros más complejos.
|
Necesidad de implementar todos los bucles.
|
Aritmética
|
Provee instrucciones para operaciones básicas, tales como suma,
resta, multiplicación y división.
|
Provee instrucciones para operaciones básicas, sin incluir la
división (necesidad de implementación).
|
Almacenamiento
|
Memoria y registros.
|
Memoria y registros (más que en x86).
|
Pila
|
Instrucciones básicas para el manejo de la pila (push-pop).
Instrucciones para salvar los registros de propósito general en la pila
(pusha-popa).
|
Instrucciones básicas para el manejo de la pila (push-pop).
|
Estándar de llamada a procedimientos.
|
El programador de la función únicamente preserva EBP. Acceso a los
argumentos a través de la pila. Devolución de los datos usando registros
(preferiblemente Eax y Edx).
|
El programador de la función debe preservar desde r4 hasta r11 y
garantizar el retorno a la dirección indicada por r14. Acceso a los
argumentos y devolución de datos usando desde r0 hasta r3.
|
Pros
|
Facilidad para acceder a memoria sin necesidad de pasar por
registros.
Función de división.
Instrucciones para bucles.
Instrucciones para salvar todos los registros de propósito general.
|
Mayor número de registros.
Estándar de llamada a procedimientos más simple.
Manejo de la pila simplificado.
Sin instrucciones para bucles.
|
Contras
|
Pocos registros.
Estándar de llamada a procedimientos más tedioso (necesidad de salvar
todos los registros, eliminar los argumentos introducidos y restaurar los
registros) fuera de la función.
|
Necesidad de guardar un dato de memoria en un registro intermedio.
Necesidad de implementación de la división.
|
No hay comentarios:
Publicar un comentario