Cuestión D

Idear un programa muy sencillo y codificarlo en ARM o x86 para que se ejecute directamente en una máquina que tenga esa arquitectura. Explicar el proceso seguido y las dificultades encontradas.

La idea de esta cuestión fue generar series de números sociables y calcular ciertos parámetros estadísticos de dicha serie usando operaciones con el coprocesador matemático.

Antes de nada, hay que aclarar qué características cumplen las series que generamos. Partimos de un número introducido por el usuario, al que le vamos a llamar A. La suma de los divisores de ese número (sin contar a él mismo, para garantizar que la serie sea convergente) da lugar a otro número B. Si repetimos el proceso hasta que converja, tenemos una sucesión en la que cada número es generado a partir de los divisores del término anterior.

La idea es bastante simple, dado que es lo que el programa requería. El algoritmo que hemos usado para realizar esto ha sido el siguiente:

El código ensamblador para esta parte es bastante sencillo y se explica casi por sí solo (junto a los comentarios).

Invoke printf, "Introduce el numero inicial%c", 10
Add Esp, 8
Invoke scanf, "%d", Addr NUM
Add Esp, 8
Invoke printf, "Introduce el limite de sociables que quieres generar%c", 10
Add Esp, 8
Invoke scanf, "%d", Addr LIMITE
Add Esp, 8

bucle_generador:
Cmp D[NUM], 0
Je > no_mas_sociables

;Calculo la mitad
Mov Edx, [NUM + 4]
Mov Eax, [NUM]
Mov Ebx, 2
Div Ebx
Mov [NUMm], Eax

;Inicializo el divisor
Mov D[DIVI], 1
bucle_divisor:
;Copio el divisor a Rbx
Mov Ebx, [DIVI]
;Compruebo que no hayamos llegado a la mitad del numero
Cmp Ebx, [NUMm]
Jg > fin_bucle
;Divido NUM/DIV
Mov Edx, [NUM + 4]
Mov Eax, [NUM]
Div Ebx

;Ahora tengo en Eax el cociente y en Edx el resto.
Cmp Edx, 0
Jne > no_divisor
; Si resto == 0
Add [suma], Ebx

; Si resto != 0
no_divisor:
Inc D[DIVI]
Jmp bucle_divisor

fin_bucle:
;Decremento el numero de elementos que nos quedan por generar
Dec D[LIMITE]

PushA
Invoke printf, "%d ", [suma]
Add Esp, 8
PopA

;Guardamos suma en NUM y comprobamos si hemos llegado al limite
Mov Eax, [suma]
Mov [NUM], Eax
Mov D[suma], 0

Cmp D[LIMITE], 0
Je > final
Jmp bucle_generador

no_mas_sociables:
;Imprimimos que hemos llegado al final
PushA
Invoke printf, "%cNo hay mas sociables%c", 10, 10
Add Esp, 12
PopA

Queda ahora calcular los parámetros estadísticos. Esto era simplemente para demostrar el funcionamiento del coprocesador y su juego de instrucciones, por lo que los parámetros que hemos decidido calcular fuero la media, la varianza y la desviación típica.

Media aritmética

Varianza. Hemos usado la tercera igualdad.

Las fórmulas anteriores describen cómo hemos calculado la media y la varianza. La desviación típica se obtiene realizando la raiz cuadrada a la varianza.

Pero claro, todos estos cálculos había que realizarlos sobre la serie computada, por lo que había que guardarla. ¿Cómo?

En primer lugar, pedimos al usuario un número máximo de términos a generar al usuario. Con dicho número, reservamos memoria usando las funciones disponibles en la API de Windows (conocida como winapi o win32api e integrada en kernel32.dll). Como íbamos a trabajar con enteros de 64 bits, tenemos que reservar 8 bytes por cada número que generemos, con un máximo introducido por el usuario, por lo que teníamos que reservar 8*Limite bytes. Lo hacemos de la siguiente forma:

;Reservo memoria para el vector donde almacenare los numeros
Mov Eax, [LIMITE]
Mov Edx, 0
Mov Ebx, 8
Mul Ebx
Invoke GlobalAlloc, GMEM_ZEROINIT, Eax
;Guardo la direccion base de la memoria reservada en BVECTOR
Mov [BVECTOR], Eax
Mov Edi, Eax

Básicamente, multiplicamos por 8 el límite y se lo pasamos a GlobalAlloc. El flag GMEM_ZEROINIT sirve para indicar al sistema que inicialice la memoria a 0. Obtenemos en Eax la dirección del primer elemento, que la guardamos en memoria como respaldo y la copiamos a Edi para trabajar con el vector. Lo único que queda es introducirlo en el vector cada vez que se genere uno, lo cual lo conseguimos copiando suma al vector e incrementado Edi antes de entrar en la siguiente iteración.

;Guardo suma en NUM para la siguiente iteracion
Mov Eax, [suma]
Mov [NUM], Eax
Mov D[suma], 0
;Incremento el contador de generados y copio el divisor
;al vector para luego procesarlo
Inc D[cont]
Mov [Edi], Eax
Add Edi, 8

Teniendo todo esto hecho, queda realizar las operaciones en coma flotante. Vamos a explicar para ello el funcionamiento del coprocesador (comunmente llamdo x87).
El coprocesador trabaja con una serie de registros apilados (funcionan como una pila), accesibles con st0 a st7, conocidos como la pila x87. Para insertar y extraer datos de esta pila hay que trabajar con las instrucciones que proporciona dicho coprocesador (conocidas como el juego de instrucciones x87). Cada registro es de 80 bits para minimizar redondeos, pero se trabaja con el estándar IEEE754 (representación en coma flotante de simple y doble precisión). Las instrucciones que hemos usado son muy simples:

Fild	Carga un entero desde memoria
Fist	Guarda un entero en memoria
Fistp	Guarda un entero en memoria y hace pop a la pila x87
Fld	Carga un flotante desde memoria
Fst	Guarda un flotante en memoria
Fstp	Guarda un flotante en memoria y hace pop a la pila x87
Fiadd	Suma st0 con un entero ubicado en memoria
Fidiv	Divide st0 entre un entero ubicado en memoria
Fimul	Multiplica st0 por un entero ubicado en memoria
Fsub	Resta dos registros x87
Fmul	Multiplica dos registros x87
Fsqrt	Realiza la raíz cuadrada de st0

Sabiendo lo que hace cada una, vamos a explicar cómo las hemos usado. Lo primero que necesitábamos era realizar un sumatorio del vector para calcular la media. Para ello, como el sumatorio lo tendríamos que realizar más veces, hemos creado una subrutina. Los requisitos para la llamada son colocar en Edi la dirección base del vector, en Esi la dirección donde guardaremos la suma y en Eax la longitud del vector.

sumar_vector: ; Eax <- Elementos, Esi <- Dirección base, Edi <- dirección suma

Push Ebp

Mov Ebp, Esp

;Pongo el contador en Ecx para Loop

Mov Ecx, Eax

;Cargo el primero y elimino su iteracion

Fild Q[Esi]

Dec Ecx

;Y voy sumando el siguiente a st0

sumatorio_f:

;Incremento el puntero

Add Esi, 8

;Sumo st0 (lo que teniamos) con la nueva posicion

Fiadd D[Esi]

Loop sumatorio_f

;Guardo el resultado en la direccion pasada en la llamada

Fstp Q[Edi]

Pop Ebp

Ret

El funcionamiento de esta función es trivial. Cargamos el primer dato, incrementamos el puntero y sumamos con el siguiente dato. Repitiendo estos dos últimos pasos hasta que el contador llegue a 0 obtenemos el sumatorio. Sólo queda guardarlo en la dirección a la que apunta Edi.

Una vez que tenemos la capacidad de sumar, necesitamos calcular la media. Queda de la siguiente forma:

; Hago el sumatorio del vector

Mov Eax, [cont]

Mov Esi, [BVECTOR]

Mov Edi, Addr suma_f

Call sumar_vector

; Calculo la media dividiendo entre contador

Fld Q[suma_f]

Fidiv D[cont]

Fstp Q[media]

Ya tenemos la media guardada en memoria. Ahora vamos a calcular la varianza. Necesitamos la suma de los cuadrados, dividir entre el numero de elementos y restarle el cuadrado de la media. Así, lo primero será calcular el cuadrado de todos los elementos del vector.

; Calculo los cuadrados de las posiciones del vector

; 1. Cargo contador en Ecx para Loop

; 2. Cargo en Esi la direccion base del vector

Mov Ecx, [cont]

Mov Esi, [BVECTOR]

cuadrados_f:

; 3. Multiplico cada entero por si mismo

Fild Q[Esi]

Fimul D[Esi]

; 4. Lo guardo de nuevo en el vector

Fistp Q[Esi]

; 5. Avanzo el puntero

Add Esi, 8

Loop cuadrados_f

Ya tenemos los datos al cuadrado. Tenemos que sumarlos, por lo que volvemos a llamar a nuestra función. Colocamos todos los datos y hacemos la llamada.

; Realizo el sumatorio de nuevo, que ahora contendra los cuadrados

Mov Eax, [cont]

Mov Esi, [BVECTOR]

Mov Edi, Addr suma_f2

Call sumar_vector

Hemos guardado la suma de los cuadrados en memoria, como respaldo. Tenemos que dividir esa suma entre el número de términos, al igual que ya hemos hecho con la media, pero antes, para ahorrarnos un paso (para evitar tener que intercambiar el tope de la pila para la resta), calcularemos el cuadrado de la media.

; Calculo el cuadrado de la media

Fld Q[media]

Fmul st0, st0

; Divido el sumatorio de los cuadrados entre el contador

Fld Q[suma_f2]

Fidiv D[cont]

Ahora estamos en la siguiente situación: tenemos en st1 el cuadrado de la media y en st0 el resultado de dividir el sumatorio de los cuadrados entre el número de datos. El último paso (si consultamos la fórmula) es restar st0-st1.

;Al sumatorio de los cuadrados entre el contador le resto la media al cuadrado y tenemos la varianza

Fsub st0, st1

;Guardo la varianza

Fst Q[varianza]

Por supuesto, guardamos la varianza en memoria. El cálculo de la desviación típica se reduce a realizar la raíz cuadrada de la varianza. La guardamos en memoria y todo listo.

;Realizo la raiz cuadrada

Fsqrt

;Y obtengo la desviacion tipica

Fstp Q[d_tipica]

Sólo nos queda imprimirlo todo (hemos usado la API de C, en concreto printf. Obviamos la llamada por ser extremadamente larga).

En cuanto a las dificultades encontradas, la realidad es que no han sido muchas pero sí nos han resultado difícil de solventar (aclarando un poco, nos ha costado averiguar el problema y buscar la solución más adecuada).

• El entorno usado no está preparado para trabajar directamente con x86-64, por lo que las operaciones con enteros de 8 bytes (que se podían haber realizado con el procesador) las hemos tenido que realizar con el coprocesador, incrementando la dificultad de la solución.
• En un principio creamos un vector de tamaño fijo, con un tamaño suficientemente grande como para almacenar todos los sociables que pudiésemos generar sin que desbordasen los enteros. Sin embargo, tener siempre esa memoria ocupada era un desperdicio. Así que posteriormente decidimos reservar memoria en tiempo de ejecución. Para ello intentamos usar malloc (porque nos es familiar). Con ella obtuvimos varias violaciones de segmento, que las achacamos a que las direcciones de memoria que devolvía esta función eran de 64 bits (pudimos comprobar esto desensamblado un programa hecho por nosotros para ver cómo trataba el compilador (gcc) con dicha función. Observamos que obtenía la dirección en Rax), mientras que nuestros registros estaban funcionando en 32 bits (como hemos dicho, nuestro entorno estaba preparado para 32b). Por todo ello, al final nos decidimos por usar la API de Windows.

Enlace de descarga.