Tarea para Raspberry Pi4
Tarea para Raspberry Pi4
Asignación:
Desde la página
[Link]
Realizar ya sea de manera física o virtual los tutoriales dispuestos en los capí[Link] 1 al 4
Esto se puede realizar usando una aplicación gráfica o la terminal del RPI.
Presentando ARM
Verás que mis explicaciones no pretenden ser muy minuciosas a la hora de describir la
arquitectura. Intentaré ser pragmático.
ARM es una arquitectura de 32 bits que tiene un objetivo simple en mente: flexibilidad. Si
bien esto es excelente para los integradores (ya que tienen mucha libertad al diseñar su
hardware), no es tan bueno para los desarrolladores de sistemas que tienen que lidiar con
las diferencias en el hardware ARM. Entonces, en este texto, asumiré que todo se hace en
una Raspberry Pi Modelo B que ejecuta Raspbian (la que tiene 2 puertos USB y 512
MB de RAM).
Algunas partes serán ARM-genéricas, pero otras serán específicas de Raspberry Pi. No haré
una distinción. El sitio web de ARM tiene mucha documentación. ¡Úsalo!
Ensamblador de escritura
El lenguaje ensamblador es solo una fina capa de sintaxis sobre el código binario.
Esta es una directiva para GNU Assembler. Una directiva le dice a GNU Assembler que
haga algo especial. Comienzan con un punto ( .) seguido del nombre de la directiva y
algunos argumentos. En este caso estamos diciendo que maines un nombre global. Esto es
necesario porque el tiempo de ejecución de C llamará main. Si no es global, el tiempo de
ejecución de C no lo podrá llamar y la fase de vinculación fallará.
5main: /* This is main */
Cada línea en GNU Assembler que no sea una directiva siempre será como label:
instruction. Podemos omitir label:y instruction(las líneas vacías y en blanco se ignoran). Una
línea con solo label:, aplica esa etiqueta a la siguiente línea (puede tener más de una etiqueta
que se refiera a lo mismo de esta manera). La instructionparte es el propio lenguaje
ensamblador ARM. En este caso solo estamos definiendo mainya que no hay instrucción.
6 mov r0, #2 /* Put a 2 inside the register r0 */
Registros
En esencia, un procesador en una computadora no es más que una poderosa
calculadora. Los cálculos solo se pueden realizar utilizando valores almacenados en
memorias muy pequeñas llamadas registros . El procesador ARM en una Raspberry Pi
tiene 16 registros enteros y 32 registros de punto flotante. Un procesador utiliza estos
registros para realizar cálculos de números enteros y cálculos de coma flotante,
respectivamente. Dejaremos los registros flotantes a un lado por ahora y eventualmente los
volveremos a encontrar en una entrega futura. Centrémonos en los registros de números
enteros.
No todos los registros desde r0hasta r15se utilizan por igual, pero esto no nos preocupará
por ahora. Simplemente asuma que lo que hacemos está "bien".
Aritmética básica
Casi todos los procesadores pueden realizar algunos cálculos aritméticos básicos utilizando
los registros de números enteros. También lo hacen los procesadores ARM. Puedes ADDdos
registros. Retomemos nuestro ejemplo del primer capítulo.
1/* -- sum01.s */
[Link] main
3
4main:
5 mov r1, #3 /* r1 ← 3 */
6 mov r2, #4 /* r2 ← 4 */
7 add r0, r1, r2 /* r0 ← r1 + r2 */
8 bx lr
Memoria
Una computadora tiene una memoria donde se almacenan el código ( .texten el
ensamblador) y los datos, por lo que debe haber alguna forma de acceder a ellos desde el
procesador. Un poco de digresión aquí, en arquitecturas 386 y x86-64, las instrucciones
pueden acceder a registros o memoria, por lo que podríamos sumar dos números, uno de los
cuales está en la memoria. No puede hacer esto en ARM donde todos los operandos deben
ser registros. Podemos solucionar este problema (no es realmente un problema, sino un
diseño de decisión deliberado que va más allá del alcance de este texto) cargando datos en
un registro desde la memoria y almacenando datos desde un registro en una memoria.
Estas dos operaciones especiales, cargar y almacenar, son instrucciones por sí mismas
llamadas normalmente cargar y almacenar . Hay varias formas de cargar y almacenar datos
desde / hacia la memoria, pero hoy nos centraremos en las más simples: cargar para
registrar ldry almacenar desde el registro str.
Cargar datos desde la memoria es un poco complicado porque necesitamos hablar
de direcciones .
Direcciones
Para acceder a los datos necesitamos darle un nombre. De lo contrario, no podríamos
referirnos a qué datos queremos. Pero, por supuesto, una computadora no tiene un nombre
diferente para cada dato que puede guardar en la memoria. Bueno, de hecho, tiene un
nombre para cada dato. Es la direccion . La dirección es un número, en ARM un número de
32 bits que identifica cada byte (esto es 8 bits) de la memoria.
La memoria es como una matriz de bytes donde cada byte tiene su
propia dirección.
Datos
Vimos en el capítulo 1 que el ensamblador contiene tanto código (llamado texto ) como
datos. Estuve deliberadamente suelto al describir las etiquetas del ensamblador. Ahora
podemos revelar su significado profundo: las etiquetas en el ensamblador son solo nombres
simbólicos para direcciones en su programa. Estas direcciones pueden referirse tanto a
datos como a códigos. Hasta ahora hemos utilizado solo una etiqueta mainpara designar la
dirección de nuestra mainfunción. Una etiqueta solo denota una dirección, nunca su
contenido. Tener esto en cuenta.
Dije que el ensamblador es una capa delgada sobre el código binario. Bueno, esa capa
delgada ahora puede parecerle un poco más gruesa ya que la herramienta ensambladora
( as) es responsable de asignar valores a las direcciones de las etiquetas. De esta manera
podemos usar estas etiquetas y el ensamblador hará algo de magia para que funcione.
.wordLa directiva establece que la herramienta ensambladora debe emitir el valor del
argumento de la directiva como un entero de 4 bytes. En este caso emitirá 4 bytes que
contienen el valor 3. Tenga en cuenta que nos basamos en el hecho de que .wordemite 4
bytes para definir el tamaño de nuestros datos.
Secciones
Los datos viven en la memoria como el código, pero debido a algunos tecnicismos
prácticos, que ahora no nos importan mucho, generalmente se mantienen juntos en lo que se
llama una sección de datos . .dataLa directiva le dice al ensamblador que emita las entidades
en la sección de datos . Esa .textdirectiva que vimos en el primer capítulo, hace algo similar
para el código. Así que colocaremos los datos después de una .datadirectiva y el código
después de un .text.
Carga
Ok, recuperaremos nuestro ejemplo del Capítulo 2 y lo mejoraremos con algunos accesos a
la memoria. Definiremos dos variables de 4 bytes myvar1y myvar2, inicializadas a 3 y 4
respectivamente. Cargaremos sus valores usando ldr, y realizaremos una suma. El código de
error resultante debería ser 7, como el del capítulo 2.
1/* -- load01.s */
2
3/* -- Data section */
[Link]
5
6/* Ensure variable is 4-byte aligned */
[Link] 4
8/* Define storage for myvar1 */
9myvar1:
10 /* Contents of myvar1 is just 4 bytes containing value '3' */
11 .word 3
12
13/* Ensure variable is 4-byte aligned */
[Link] 4
15/* Define storage for myvar2 */
16myvar2:
17 /* Contents of myvar2 is just 4 bytes containing value '4' */
18 .word 4
19
20/* -- Code section */
[Link]
22
23/* Ensure code is 4 byte aligned */
[Link] 4
[Link] main
26main:
27 ldr r1, addr_of_myvar1 /* r1 ← &myvar1 */
28 ldr r1, [r1] /* r1 ← *r1 */
29 ldr r2, addr_of_myvar2 /* r2 ← &myvar2 */
30 ldr r2, [r2] /* r2 ← *r2 */
31 add r0, r1, r2 /* r0 ← r1 + r2 */
32 bx lr
33
34/* Labels needed to access data */
35addr_of_myvar1 : .word myvar1
36addr_of_myvar2 : .word myvar2
He hecho un poco de trampa en el ejemplo anterior debido a limitaciones en el
ensamblador. Como puede ver, hay cuatro ldrinstrucciones. Intentaré explicar su
significado. Primero, sin embargo, tenemos que discutir las siguientes dos etiquetas.
Ok, entonces dos cargas. El primero de la línea 27 carga realmente el valor de reubicación
de la dirección de myvar1. Es decir, hay algunos datos en la memoria, cuya dirección
es addr_of_myvar1, con un tamaño de 4 bytes que contiene la dirección real
de myvar1. Entonces, después del primero ldr, r1tenemos la dirección real de myvar1. Pero no
queremos la dirección en absoluto, sino el contenido de la memoria en esa dirección, así
que hacemos un segundo ldr.
Suponiendo el contenido de memoria dado,
esto es lo que sucede con los registros después de que se ejecuta una instrucción de carga.
Probablemente se esté preguntando por qué las dos cargas tienen una sintaxis diferente. El
primero ldrusa la dirección simbólica de addr_of_myvar1etiqueta. El segundo ldrutiliza el
valor del registro como modo de direccionamiento . Entonces, en el segundo caso, estamos
usando el valor dentro r1como la dirección. En el primer caso, no sabemos realmente qué
usa el ensamblador como modo de direccionamiento, por lo que lo ignoraremos por ahora.
El programa carga dos valores de 32 bits desde myvar1y myvar2, que tenían los valores
iniciales 3 y 4, los suma y establece el resultado de la suma como el código de error del
programa en el r0registro justo antes de salir main.
$ ./load01 ; echo $?
7
Tienda
Ahora tome el ejemplo anterior, pero en lugar de establecer los valores iniciales
de myvar1y myvar2en 3 y 4 respectivamente, establezca ambos en 0. Reutilizaremos el
código existente pero antepondremos algún ensamblador para almacenar un 3 y un 4 en las
variables.
1/* -- store01.s */
2
3/* -- Data section */
[Link]
5
6/* Ensure variable is 4-byte aligned */
[Link] 4
8/* Define storage for myvar1 */
9myvar1:
10 /* Contents of myvar1 is just '3' */
11 .word 0
12
13/* Ensure variable is 4-byte aligned */
[Link] 4
15/* Define storage for myvar2 */
16myvar2:
17 /* Contents of myvar2 is just '3' */
18 .word 0
19
20/* -- Code section */
[Link]
22
23/* Ensure function section starts 4 byte aligned */
[Link] 4
[Link] main
26main:
27 ldr r1, addr_of_myvar1 /* r1 ← &myvar1 */
28 mov r3, #3 /* r3 ← 3 */
29 str r3, [r1] /* *r1 ← r3 */
30 ldr r2, addr_of_myvar2 /* r2 ← &myvar2 */
31 mov r3, #4 /* r3 ← 4 */
32 str r3, [r2] /* *r2 ← r3 */
33
34 /* Same instructions as above */
35 ldr r1, addr_of_myvar1 /* r1 ← &myvar1 */
36 ldr r1, [r1] /* r1 ← *r1 */
37 ldr r2, addr_of_myvar2 /* r2 ← &myvar2 */
38 ldr r2, [r2] /* r2 ← *r2 */
39 add r0, r1, r2
40 bx lr
41
42/* Labels needed to access data */
43addr_of_myvar1 : .word myvar1
44addr_of_myvar2 : .word myvar2
gdb
Usaremos el ejemplo store01del capítulo 3. Comience gdbespecificando el programa que va a
depurar.
$ gdb --args ./store01
GNU gdb (GDB) 7.4.1-debian
Copyright (C) 2012 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "arm-linux-gnueabihf".
For bug reporting instructions, please see:
...
Reading symbols from /home/roger/asm/chapter03/store01...(no debugging symbols found)...done.
(gdb)
Ok, estamos en el modo interactivo de gdb. En este modo te comunicas gdbusando
comandos. Hay un comando de ayuda incorporado llamado help. O puede consultar
la documentación del depurador GNU . Un primer comando para aprender es
(gdb) quit
Ok, ahora empieza de gdbnuevo. El programa aún no se está ejecutando. De hecho gdbno
podrá contarte muchas cosas al respecto ya que no tiene información de depuración. Pero
esto está bien, estamos depurando ensamblador, por lo que no necesitamos mucha
información de depuración. Entonces, como primer paso, comencemos el programa.
(gdb) start
Temporary breakpoint 1 at 0x8390
Starting program: /home/roger/asm/chapter03/store01
Derivación
Hasta ahora, nuestros pequeños programas ensambladores ejecutan una instrucción tras
otra. Si nuestro procesador ARM solo pudiera funcionar de esta manera, sería de uso
limitado. No pudo reaccionar a las condiciones existentes que pueden requerir diferentes
secuencias de instrucciones. Este es el propósito de las instrucciones de bifurcación .
Un registro especial
En el capítulo 2 aprendimos que nuestro procesador ARM Raspberry Pi tiene 16 registros
enteros de propósito general y también dijimos que algunos de ellos juegan roles especiales
en nuestro programa. Ignoré deliberadamente qué registros eran especiales, ya que no eran
relevantes en ese momento.
Pero ahora es relevante, al menos para el registro r15. Este registro es muy especial, tan
especial que también tiene otro nombre: pc. Es poco probable que lo veas usado r15ya que
es confuso (aunque correcto desde el punto de vista de la arquitectura ARM). A partir de
ahora solo usaremos pcpara nombrarlo.
¿Qué significa pc? pcsignifica contador de programa . Este nombre, cuyos orígenes se
encuentran en los albores de la informática, significa poco o nada hoy en día. En general,
el pcregistro (también llamado ip, puntero de instrucción , en otras arquitecturas como 386 o
x86_64) contiene la dirección de la siguiente instrucción que va a ser ejecutado.
Cuando el procesador ARM ejecuta una instrucción, pueden suceder dos cosas al final de
su ejecución. Si la instrucción no se modifica pc(y la mayoría de las instrucciones no lo
hacen), pcsimplemente se incrementa en 4 (como si lo hiciéramos add pc, pc, #4). ¿Por qué
4? Porque en ARM, las instrucciones tienen un ancho de 32 bits, por lo que hay 4 bytes
entre cada instrucción. Si la instrucción modifica pc, pcse utiliza el nuevo valor de .
Una vez que el procesador ha ejecutado completamente una instrucción, entonces usa el
valor en pccomo la dirección para que se ejecute la siguiente instrucción. De esta forma,
una instrucción que no modifique el pcserá seguida por la siguiente instrucción contigua en
memoria (ya que se ha incrementado automáticamente en 4). Esto se
denomina secuenciación implícita de instrucciones: después de que una se ha ejecutado,
normalmente se ejecuta la siguiente en la memoria. Pero si una instrucción modifica pc, por
ejemplo, a un valor distinto de pc + 4, entonces podemos estar ejecutando otra instrucción
del programa. Este proceso de cambiar el valor de pcse llama ramificación . En ARM, esto
se hace usando instrucciones de bifurcación .
Ramas incondicionales
Puede decirle al procesador que se bifurque incondicionalmente utilizando la
instrucción b(para la bifurcación ) y una etiqueta. Considere el siguiente programa.
1/* -- branch01.s */
[Link]
[Link] main
4main:
5 mov r0, #2 /* r0 ← 2 */
6 b end /* branch to 'end' */
7 mov r0, #3 /* r0 ← 3 */
8end:
9 bx lr
Ramas condicionales
Si nuestro procesador solo pudiera bifurcarse porque sí, no sería muy útil. Es mucho más
útil bifurcar cuando se cumple alguna condición . Entonces, un procesador debería poder
evaluar algún tipo de condiciones.
Así que tenemos todas las piezas necesarias para realizar ramificaciones de forma
condicional. Pero primero, comencemos a comparar dos valores. Usamos la
instrucción cmppara este propósito.
cmp r1, r2 /* updates cpsr doing "r1 - r2", but r1 and r2 are not modified */
Esta instrucción resta al valor del primer registro el valor del segundo registro. ¿Ejemplos
de lo que podría suceder en el fragmento anterior?
¿Cómo podemos usar estas banderas para representar condiciones útiles para nuestros
programas?
1/* -- compare01.s */
[Link]
[Link] main
4main:
5 mov r1, #2 /* r1 ← 2 */
6 mov r2, #2 /* r2 ← 2 */
7 cmp r1, r2 /* update cpsr condition codes with the value of r1-r2 */
8 beq case_equal /* branch to case_equal only if Z = 1 */
9case_different :
10 mov r0, #2 /* r0 ← 2 */
11 b end /* branch to end */
12case_equal:
13 mov r0, #1 /* r0 ← 1 */
14end:
15 bx lr
Estructuras de Control
En el capítulo anterior aprendimos instrucciones de bifurcación. Son herramientas
realmente poderosas porque nos permiten expresar estructuras de control. La programación
estructurada es un hito importante en la mejora de la ingeniería informática (fundamental,
pero no obstante importante). Por lo tanto, ser capaz de mapear construcciones de
programación estructuradas habituales en ensamblador, en nuestro procesador, es algo
bueno ™.
Si, entonces, si no
Bueno, este es básico, y de hecho ya usamos esta estructura en el capítulo
anterior. Considere la siguiente estructura, donde Ees una expresión S1y S2son
declaraciones (pueden ser declaraciones compuestas como { SA; SB; SC; })
if (E) then
S1
else
S2
Una posible forma de expresar esto en el ensamblador ARM podría ser la siguiente
if_eval:
/* Assembler that evaluates E and updates the cpsr accordingly */
bXX else /* Here XX is the appropiate condition */
then_part:
/* assembler for S1, the "then" part */
b end_of_if
else:
/* assembler for S2, the "else" part */
end_of_if:
Si no hay otra parte, podemos reemplazarla bXX elsecon bXX end_of_if.
Bucles
Este es otro habitual en la programación estructurada. Si bien hay varios tipos de bucles, en
realidad todos se reducen a la siguiente estructura.
while (E)
S
Supuestamente Shace que algo Efinalmente se vuelva falso y se deje el bucle. De lo
contrario, nos mantendríamos informados para siempre (a veces esto es lo que quieres, pero
no en nuestros ejemplos). Una forma de implementar estos bucles es la siguiente.
while_condition : /* assembler to evaluate E and update cpsr */
bXX end_of_loop /* If E is false, then leave the loop right now */
/* assembler of S */
b while_condition /* Unconditional branch to the beginning */
end_of_loop:
Un ciclo común implica iterar desde un solo rango de enteros, como en
for (i = L; i < N; i += K)
S
Pero esto no es más que
i = L;
while (i < N)
{
S;
i += K;
}
Por lo tanto, no tenemos que aprender una nueva forma de implementar el bucle en sí.
1 + 2 + 3 + 4 + ... + 22
Como primer ejemplo, sumemos todos los números del 1 al 22 (te diré más adelante por
qué elegí 22). El resultado de la suma es 253(compruébalo con una calculadora ). Sé que
tiene poco sentido calcular algo cuyo resultado ya conocemos, pero esto es solo un ejemplo.
1/* -- loop01.s */
[Link]
[Link] main
4main:
5 mov r1, #0 /* r1 ← 0 */
6 mov r2, #1 /* r2 ← 1 */
7loop:
8 cmp r2, #22 /* compare r2 and 22 */
9 bgt end /* branch if r2 > 22 to end */
10 add r1, r1, r2 /* r1 ← r1 + r2 */
11 add r2, r2, #1 /* r2 ← r2 + 1 */
12 b loop
13end:
14 mov r0, r1 /* r0 ← r1 */
15 bx lr
Aquí estamos contando del 1 al 22. Usaremos el registro r2como contador. Como puede ver
en la línea 6 lo inicializamos a 1. La suma se acumulará en el registro r1, al final del
programa movemos el contenido de r1en r0para devolver el resultado de la suma como el
código de error del programa (nosotros Podría haber usado r0en todo el código y evitar este
final movpero creo que es más claro así).
Tal vez haya notado que sucede algo extraño con nuestras etiquetas identificadas como
funciones. Abordaremos este problema en un capítulo futuro, aunque en su mayoría es
inofensivo.
3n + 1
Hagamos otro ejemplo un poco más complicado. Este es el famoso problema 3n +
1 también conocido como la conjetura de Collatz . Dado un número nlo dividiremos por 2 si
es par y lo multiplicaremos por 3 y sumaremos uno si es impar.
if (n % 2 == 0)
n = n / 2;
else
n = 3*n + 1;
Antes de continuar, nuestro procesador ARM es capaz de multiplicar dos números pero
deberíamos aprender una nueva instrucción mulque nos desviaría un poco. En su lugar,
usaremos la siguiente identidad 3 * n = 2*n + n. Realmente no sabemos cómo multiplicar o
dividir por dos todavía, estudiaremos esto en un capítulo futuro, así que por ahora solo
asuma que funciona como se muestra en el ensamblador a continuación.
1/* -- collatz.s */
[Link]
[Link] main
4main:
5 mov r1, #123 /* r1 ← 123 */
6 mov r2, #0 /* r2 ← 0 */
7loop:
8 cmp r1, #1 /* compare r1 and 1 */
9 beq end /* branch to end if r1 == 1 */
10
11 and r3, r1, #1 /* r3 ← r1 & 1 */
12 cmp r3, #0 /* compare r3 and 0 */
13 bne odd /* branch to odd if r3 != 0 */
14even:
15 mov r1, r1, ASR #1 /* r1 ← (r1 >> 1) */
16 b end_loop
17odd:
18 add r1, r1, r1, LSL #1 /* r1 ← r1 + (r1 << 1) */
19 add r1, r1, #1 /* r1 ← r1 + 1 */
20
21end_loop:
22 add r2, r2, #1 /* r2 ← r2 + 1 */
23 b loop /* branch to loop */
24
25end:
26 mov r0, r2
27 bx lr
Ahora ocurre algo de magia en la línea 15. Esta es una operación combinada que ARM nos
permite hacer. Esto es un, movpero no movemos el valor de r1directamente a r1(lo que no
haría nada), pero primero hacemos un desplazamiento aritmético a la derecha (ASR) al
valor de r1(al valor, no al registro en sí). Luego, este valor desplazado se traslada al
registro r1. Un desplazamiento aritmético a la derecha desplaza todos los bits de un registro
a la derecha: el bit más a la derecha se descarta efectivamente y el más a la izquierda se
establece en el mismo valor que el bit más a la izquierda antes del desplazamiento. Cambiar
un bit a la derecha a un número es lo mismo que dividir ese número por 2. Así que esto mov
r1, r1, ASR #1es lo que realmente sucede r1 ← r1 / 2.
Algo similar ocurre con el caso par en la línea 18. En este caso estamos haciendo un add. El
primer y segundo operandos deben ser registros (operando de destino y el primer operando
de origen). El tercero se combina con un desplazamiento lógico a la izquierda (LSL). El
valor del operando se desplaza 1 bit hacia la izquierda: el bit más a la izquierda se descarta
y el bit más a la derecha se establece en 0. Esto es efectivamente multiplicar el valor por 2.
Entonces estamos sumando r1(que mantiene el valor de n) a 2*r1. Esto
es 3*r1así 3*n. Mantenemos este valor r1nuevamente. En la línea 19 sumamos 1 a ese valor,
por lo que r1termina teniendo el valor 3*n+1que queríamos.
No te preocupes mucho ahora por estos LSL y ASR. Solo déjalos por sentado ahora. En un
capítulo futuro los veremos con más detalle.
Posdata
Kevin Millikin señaló correctamente (en un comentario a continuación) que, por lo general,
un bucle no se implementa de la forma que se muestra arriba. De hecho, Kevin dice que
una mejor manera de hacer el bucle [Link] la siguiente.
1/* -- loop02.s */
[Link]
[Link] main
4main:
5 mov r1, #0 /* r1 ← 0 */
6 mov r2, #1 /* r2 ← 1 */
7 b check_loop /* unconditionally jump at the end of the loop */
8loop:
9 add r1, r1, r2 /* r1 ← r1 + r2 */
10 add r2, r2, #1 /* r2 ← r2 + 1 */
11check_loop:
12 cmp r2, #22 /* compare r2 and 22 */
13 ble loop /* branch if r2 <= 22 to the beginning of the loop */
14end:
15 mov r0, r1 /* r0 ← r1 */
16 bx lr
Sin embargo, hay otra ventaja en esta segunda versión: solo hay una rama en el bucle
mismo, ya que recurrimos a la secuenciación implícita para alcanzar nuevamente las dos
instrucciones que realizan la verificación. Por razones más allá del alcance de esta
publicación, la ejecución de una instrucción de rama puede afectar negativamente el
desempeño de nuestros programas. Los procesadores tienen mecanismos para mitigar la
pérdida de rendimiento debido a las ramas (y de hecho, el procesador en la Raspberry Pi los
tiene). Pero evitar una instrucción de bifurcación evita por completo la posible penalización
del rendimiento de ejecutar una instrucción de bifurcación.
Modos de indexación
Hemos visto que, a excepción de load ( ldr), store ( str) y branch ( by bXX), las instrucciones
ARM toman como operandos registros o valores inmediatos. También hemos visto que el
primer operando suele ser el registro de destino (siendo struna excepción notable ya que allí
desempeña el papel de origen porque el destino ahora es la memoria). La
instrucción movtiene otro operando, un registro o un valor inmediato. Las instrucciones
aritméticas como addy and(y muchas otras) tienen dos registros fuente más, el primero de los
cuales es siempre un registro y el segundo puede ser un registro o un valor inmediato.
Operando desplazado
¿Qué es este misterioso source2en los patrones de instrucción anteriores? Si recuerda los
capítulos anteriores, hemos utilizado registros o valores inmediatos. Así que al menos
eso source2es esto: registro o valor inmediato. Puede utilizar un registro inmediato o
donde source2se espera un. A continuación se muestran algunos ejemplos, pero ya los hemos
utilizado en los ejemplos de los capítulos anteriores.
mov r0, #1
mov r1, r0
add r2, r1, r0
add r2, r3, #4
Pero source2puede ser mucho más que un simple registro o un inmediato. De hecho, cuando
es un registro podemos combinarlo con una operación de desplazamiento . Ya vimos una
de estas operaciones de cambio en el capítulo 6. No es el momento de desvelarlas todas.
Las rotaciones son menos útiles que los turnos en el uso diario. Suelen utilizarse en
criptografía, para reordenar bits y "codificarlos". ARM no proporciona una forma de rotar a
la izquierda, pero podemos nrotar a la izquierda haciendo un 32-nrotar a la derecha.
/* Assume r1 is 0x12345678 */
mov r1, r1, ROR #1 /* r1 ← r1 ror 1. This is r1 ← 0x91a2b3c */
mov r1, r1, ROR #31 /* r1 ← r1 ror 31. This is r1 ← 0x12345678 */
Matrices y estructuras
Hasta ahora hemos podido mover 32 bits de la memoria a los registros (cargar) y volver a la
memoria (almacenar). Pero trabajar con elementos individuales de 32 bits (generalmente
llamados escalares) es un poco limitante. Pronto nos encontraríamos trabajando en matrices
y estructuras, incluso si no lo sabíamos.
Una matriz es una secuencia de elementos del mismo tipo en la memoria. Las matrices son
una estructura de datos fundamental en casi todos los lenguajes de bajo nivel. Cada matriz
tiene una dirección base, generalmente indicada por el nombre de la matriz, y contiene N
elementos. Cada uno de estos elementos tiene asociado un índice creciente, que va de 0 a
N-1 o de 1 a N. Usando la dirección base y el índice podemos acceder a un elemento del
arreglo. En el capítulo 3 mencionamos que la memoria podría verse como una matriz de
bytes. Una matriz en la memoria es la misma, pero un elemento puede ocupar más de un
byte.
¿Qué tienen que ver las matrices y la estructura con los modos de indexación de carga y
almacenamiento? Bueno, estos modos de indexación están diseñados para facilitar el acceso
a matrices y estructuras.
1/* -- array01.s */
[Link]
3
[Link] 4
5a: .skip 400
En la línea 5 definimos el símbolo ay luego dejamos espacio para 400 bytes. La directiva
.skip le dice al ensamblador que avance un número dado de bytes antes de emitir el
siguiente dato. Aquí estamos saltando 400 bytes porque nuestra matriz de enteros toma 400
bytes (4 bytes por cada uno de los 100 enteros). Declarar una estructura no es muy
diferente.
[Link] 4
8b: .skip 8
En este momento, debería preguntarse por qué omitimos 8 bytes cuando la estructura en sí
solo ocupa 5 bytes. Bueno, necesita 5 bytes para almacenar información útil. El primer
campo f0es a char. A charocupa 1 byte de almacenamiento. El siguiente campo f1es un
número entero. Un número entero toma 4 bytes y también debe estar alineado en 4 bytes,
por lo que tenemos que dejar 3 bytes sin usar entre el campo f0y el campo f1. Este
almacenamiento no utilizado puesto solo para cumplir con la alineación se
llama relleno . Su programa nunca debe utilizar el relleno.
¡Uf! Estamos usando muchas cosas que hemos aprendido de los capítulos anteriores. En la
línea 14 cargamos la dirección base de la matriz en r1. La dirección de la matriz no
cambiará, así que la cargamos una vez. En registro r2mantendremos el índice que estará en
el rango de 0 a 99. En la línea 17 lo comparamos con 100 para ver si hemos llegado al final
del ciclo.
Como puede ver, acceder a una matriz implica calcular la dirección del elemento
accedido. ¿El conjunto de instrucciones ARM proporciona una forma más compacta de
hacer esto? La respuesta es sí. De hecho, proporciona varios modos de indexación .
Modos de indexación
En el capítulo anterior, el modo de indexación de conceptos estaba un poco apagado porque
no estábamos indexando nada. Ahora tiene mucho más sentido ya que estamos indexando
un elemento de matriz. ARM proporciona nueve de estos modos de indexación. Distinguiré
dos tipos de modos de indexación: no actualizar y actualizar dependiendo de si presentan
un efecto secundario que discutiremos más adelante, cuando se trata de actualizar los
modos de indexación.
Esta es similar a la operación de turno habitual que podemos hacer con otras
instrucciones. Una operación de desplazamiento
(recuerda: LSL, LSR, ASRo ROR) se aplica a Rsource2, Rsource1se añade a
continuación (o se resta) al resultado de la operación de desplazamiento
aplicada a Rsource2. Esto es útil cuando necesitamos multiplicar la dirección por
una cantidad fija. Al acceder a los elementos de la matriz de enteros a, tuvimos
que multiplicar el resultado por 4 para obtener una dirección significativa.
Podemos expresar esto de una manera mucho más compacta (sin la necesidad
del registro r3).
str r2, [r1, +r2, LSL #2] /* *(r1 + r2*4) ← r2 */
Modos de post-indexación
4. [Rsource1], #+immediateo
[Rsource1], #-immediate
16loop:
17 cmp r2, #100 /* Have we reached 100 yet? */
18 beq end /* If so, leave the loop, otherwise continue */
19 str r2, [r1], #4 /* *r1 ← r2 then r1 ← r1 + 4 */
20 add r2, r2, #1 /* r2 ← r2 + 1 */
21 b loop /* Go to the beginning of the loop */
22end:
5. [Rsource1], +Rsource2o
[Rsource1], -Rsource2
Modos de preindexación
Los modos de preindexación pueden parecer un poco extraños al principio, pero son útiles
cuando la dirección calculada se reutilizará pronto. En lugar de volver a calcularlo,
podemos reutilizar el archivo actualizado Rsource1. Tenga !en cuenta el símbolo en estos
modos de indexación que los distingue de los modos de indexación que no se actualizan.
7. [Rsource1, #+immediate]!o
[Rsource1, #-immediate]!
8. [Rsource1, +Rsource2]!o
[Rsource1, +Rsource2]!
Tenga en cuenta que usamos un modo de preindexación para mantener r1la dirección del
campo f1. De esta forma, la segunda tienda no necesita volver a calcular esa dirección.
Pasando parámetros
Las funciones pueden recibir parámetros. Los primeros 4 parámetros deben ser
almacenados, de forma secuencial, en los registros r0, r1, r2y r3. Quizás se esté preguntando
cómo pasar más de 4 parámetros. Podemos, por supuesto, pero necesitamos usar la pila,
pero lo discutiremos en el próximo capítulo. Hasta entonces, solo pasaremos hasta 4
parámetros.
Esto significa que, después de llamar a una función, tenemos que asumir que (sólo)
registros r0, r1, r2, r3y lrhan sido sobrescritos. </ Li>
Llamar a una función
Hay dos formas de llamar a una función. Si la función se conoce estáticamente (lo que
significa que sabemos exactamente a qué función se debe llamar) la usaremos bl label. Esa
etiqueta debe ser una etiqueta definida en la .textsección. A esto se le llama llamada directa
(o inmediata). Podemos hacer llamadas indirectas almacenando primero la dirección de la
función en un registro y luego usando blx Rsource1.
En los ejemplos de los capítulos anteriores, devolvimos el código de error del programa en
formato r0. Esto ahora tiene sentido. C's maindevuelve an int, que se usa como el valor del
código de error de nuestro programa.
Hola Mundo
Por lo general, este es el primer programa que escribe en cualquier lenguaje de
programación de alto nivel. En nuestro caso, primero tuvimos que aprender muchas
cosas. De todos modos, aquí está. Un "Hola mundo" en ensamblador ARM.
(Nota para los expertos: dado que no discutiremos la pila hasta el próximo capítulo, este
código puede parecerle muy tonto)
1/* -- hello01.s */
[Link]
3
4greeting:
5 .asciz "Hello world"
6
[Link] 4
8return: .word 0
9
[Link]
11
[Link] main
13main:
14 ldr r1, address_of_return /* r1 ← &address_of_return */
15 str lr, [r1] /* *r1 ← lr */
16
17 ldr r0, address_of_greeting /* r0 ← &address_of_greeting */
18 /* First parameter of puts */
19
20 bl puts /* Call to puts */
21 /* lr ← address of next instruction */
22
23 ldr r1, address_of_return /* r1 ← &address_of_return */
24 ldr lr, [r1] /* lr ← *r1 */
25 bx lr /* return from main */
26address_of_greeting: .word greeting
27address_of_return: .word return
28
29/* External */
[Link] puts
Después de los bytes del mensaje de saludo, nos aseguramos de que la siguiente etiqueta
tenga 4 bytes alineados y definimos una returnetiqueta en la línea 8. En esa etiqueta
mantendremos el valor de la lrque tenemos main. Como se indicó anteriormente, este es un
requisito para una función de buen comportamiento: poder obtener el valor original de lral
ingresar. Así que le hacemos espacio.
Las dos primeras instrucciones, líneas 14 y 15, de nuestra función principal mantienen el
valor de lren esa returnvariable definida anteriormente. Luego, en la línea 17 preparamos los
argumentos para la llamada a puts. Cargamos la dirección del mensaje de saludo en
el r0registro. Este registro contendrá el primer parámetro (el único en realidad)
de puts. Luego, en la línea 20 llamamos a la función. Recuerde que blse establecerá en lrla
dirección de la instrucción que le sigue (esta es la instrucción en la línea 23). Esta es la
razón por la que copiamos el valor de lren una variable al comienzo de la mainfunción,
porque iba a ser sobrescrito por bl.
Interacción real!
Ahora que tenemos el poder de llamar a funciones, podemos unirlas. Llamemos a printf y
scanf para leer un número y luego imprimirlo en la salida estándar.
1/* -- printf01.s */
[Link]
3
4/* First message */
[Link] 4
6message1: .asciz "Hey, type a number: "
7
8/* Second message */
[Link] 4
10message2: .asciz "I read the number %d\n"
11
12/* Format pattern for scanf */
[Link] 4
14scan_pattern : .asciz "%d"
15
16/* Where scanf will store the number read */
[Link] 4
18number_read: .word 0
19
[Link] 4
21return: .word 0
22
[Link]
24
[Link] main
26main:
27 ldr r1, address_of_return /* r1 ← &address_of_return */
28 str lr, [r1] /* *r1 ← lr */
29
30 ldr r0, address_of_message1 /* r0 ← &message1 */
31 bl printf /* call to printf */
32
33 ldr r0, address_of_scan_pattern /* r0 ← &scan_pattern */
34 ldr r1, address_of_number_read /* r1 ← &number_read */
35 bl scanf /* call to scanf */
36
37 ldr r0, address_of_message2 /* r0 ← &message2 */
38 ldr r1, address_of_number_read /* r1 ← &number_read */
39 ldr r1, [r1] /* r1 ← *r1 */
40 bl printf /* call to printf */
41
42 ldr r0, address_of_number_read /* r0 ← &number_read */
43 ldr r0, [r0] /* r0 ← *r0 */
44
45 ldr lr, address_of_return /* lr ← &address_of_return */
46 ldr lr, [lr] /* lr ← *lr */
47 bx lr /* return from main using lr */
48address_of_message1 : .word message1
49address_of_message2 : .word message2
50address_of_scan_pattern : .word scan_pattern
51address_of_number_read : .word number_read
52address_of_return : .word return
53
54/* External */
[Link] printf
[Link] scanf
[Link] 4
24return2: .word 0
25
[Link]
27
28/*
29mult_by_5 function
30*/
31mult_by_5:
32 ldr r1, address_of_return2 /* r1 ← &address_of_return */
33 str lr, [r1] /* *r1 ← lr */
34
35 add r0, r0, r0, LSL #2 /* r0 ← r0 + 4*r0 */
36
37 ldr lr, address_of_return2 /* lr ← &address_of_return */
38 ldr lr, [lr] /* lr ← *lr */
39 bx lr /* return from main using lr */
40address_of_return2 : .word return2
Esta función necesitará otra " return" variable como la que mainusa. Pero esto es por el bien
del ejemplo. En realidad, esta función no llama a otra función. Cuando esto sucede, no es
necesario que se mantenga, lrya que no blo la blxinstrucción lo va a modificar. Si la función
quisiera usar lrcomo r14registro de propósito general, el proceso de mantener el valor aún
sería obligatorio.
Como puede ver, una vez que la función ha calculado el valor, es suficiente
mantenerlo r0. En este caso fue bastante fácil y una sola instrucción fue suficiente.
1/* -- printf02.s */
[Link]
3
4/* First message */
[Link] 4
6message1: .asciz "Hey, type a number: "
7
8/* Second message */
[Link] 4
10message2: .asciz "%d times 5 is %d\n"
11
12/* Format pattern for scanf */
[Link] 4
14scan_pattern : .asciz "%d"
15
16/* Where scanf will store the number read */
[Link] 4
18number_read: .word 0
19
[Link] 4
21return: .word 0
22
[Link] 4
24return2: .word 0
25
[Link]
27
28/*
29mult_by_5 function
30*/
31mult_by_5:
32 ldr r1, address_of_return2 /* r1 ← &address_of_return */
33 str lr, [r1] /* *r1 ← lr */
34
35 add r0, r0, r0, LSL #2 /* r0 ← r0 + 4*r0 */
36
37 ldr lr, address_of_return2 /* lr ← &address_of_return */
38 ldr lr, [lr] /* lr ← *lr */
39 bx lr /* return from main using lr */
40address_of_return2 : .word return2
41
[Link] main
43main:
44 ldr r1, address_of_return /* r1 ← &address_of_return */
45 str lr, [r1] /* *r1 ← lr */
46
47 ldr r0, address_of_message1 /* r0 ← &message1 */
48 bl printf /* call to printf */
49
50 ldr r0, address_of_scan_pattern /* r0 ← &scan_pattern */
51 ldr r1, address_of_number_read /* r1 ← &number_read */
52 bl scanf /* call to scanf */
53
54 ldr r0, address_of_number_read /* r0 ← &number_read */
55 ldr r0, [r0] /* r0 ← *r0 */
56 bl mult_by_5
57
58 mov r2, r0 /* r2 ← r0 */
59 ldr r1, address_of_number_read /* r1 ← &number_read */
60 ldr r1, [r1] /* r1 ← *r1 */
61 ldr r0, address_of_message2 /* r0 ← &message2 */
62 bl printf /* call to printf */
63
64 ldr lr, address_of_return /* lr ← &address_of_return */
65 ldr lr, [lr] /* lr ← *lr */
66 bx lr /* return from main using lr */
67address_of_message1 : .word message1
68address_of_message2 : .word message2
69address_of_scan_pattern : .word scan_pattern
70address_of_number_read : .word number_read
71address_of_return : .word return
72
73/* External */
[Link] printf
[Link] scanf
Quiero que se fijen en las líneas 58 a 62. Allí preparamos la llamada a la printfque recibe
tres parámetros: el formato y los dos enteros referenciados en el formato. Queremos que el
primer entero sea el número ingresado por el usuario. El segundo será ese mismo número
multiplicado por 5. Luego de la llamada a mult_by_5, r0contiene el número ingresado por el
usuario multiplicado por 5. Queremos que sea el tercer parámetro así que lo movemos
a r2. Luego cargamos el valor del número ingresado por el usuario en r1. Finalmente
cargamos en r0la dirección al formato de mensaje de printf. Tenga en cuenta que aquí el
orden de preparación de los argumentos de una llamada no es relevante siempre que los
valores sean correctos en el momento de la llamada. Usamos el hecho de que tendremos
que sobrescribirr0, por lo que, para mayor comodidad, primero copiamos r0en r2.
$ ./printf02
Hey, type a number: 1234↴
1234 times 5 is 6170
En el capítulo 9 nos presentaron las funciones y vimos que tienen que seguir una serie de
convenciones para funcionar bien con otras funciones. También mencionamos brevemente
la pila, como un área de memoria que pertenece únicamente a la función. En este capítulo
profundizaremos en la pila y por qué es importante para las funciones.
Activación dinámica
Uno de los beneficios de las funciones es poder llamarlas más de una vez. Pero eso más de
una vez esconde una pequeña trampa. No estamos restringiendo quién podrá llamar a la
función, por lo que puede suceder que sea la misma función la que se llame a sí
misma. Esto sucede cuando usamos la recursividad.
Está bien. Tenemos una función que se llama a sí misma. No es gran cosa, ¿verdad? Bueno,
esto no sería un problema si no fuera por las reglas que debe cumplir una función. Vamos a
recordarlos rápidamente.
En el capítulo 9 usamos una variable global para mantener lr. Pero si intentáramos usar una
variable global en nuestro ejemplo factorial (3) , se sobrescribirá en la siguiente activación
dinámica de factorial. Solo podríamos volver de factorial (0) a factorial (1) . Después de
eso nos quedaríamos atrapados en factorial (1) , ya lrque siempre tendríamos el mismo
valor.
Entonces, parece que necesitamos alguna forma de mantener al menos el valor de lr por
cada activación dinámica . Y no solo lr, si quisiéramos usar registros de r4a r11también
necesitamos mantener de alguna manera por cada activación dinámica, una variable global
tampoco sería suficiente. Aquí es donde entra en juego la pila.
La pila
En informática, una pila es una estructura de datos (una forma de organizar los datos que
proporciona algunas propiedades interesantes). Una pila normalmente tiene tres
operaciones: acceder a la parte superior de la pila, empujar hacia la parte superior, saltar
desde la parte superior. Dependiendo del contexto, solo puede acceder a la parte superior de
la pila, en nuestro caso podremos acceder a más elementos que solo la parte superior.
Pero, ¿qué es la pila? Ya dije en el capítulo 9 que la pila es una región de memoria que
pertenece únicamente a la función. Ahora podemos reformular esto un poco mejor: la pila
es una región de memoria que pertenece únicamente a la activación dinámica actual. ¿Y
cómo controlamos la pila? Bueno, en el capítulo 9 dijimos que el
registro spsignifica s tack p ointer . Este registro contendrá la parte superior de la pila. La
región de memoria propiedad de la activación dinámica es la extensión de bytes contenidos
entre el valor actual de spy el valor inicial que sptenía al comienzo de la
función. Llamaremos a esa región la memoria [Link] una función (más precisamente, de
una activación dinámica de la misma). Pondremos allí todo lo que haya que guardar al
comienzo de una función y restaurarlo antes de salir. También guardaremos allí
las variables locales de una función (activación dinámica).
Nuestra función también tiene que adherirse a algunas reglas al manejar la pila.
El puntero de la pila ( sp) siempre está alineado con 4 bytes. Esto es
absolutamente obligatorio. Sin embargo, debido al estándar de llamada a
procedimiento para la arquitectura ARM (AAPCS), el puntero de la pila tendrá
que estar alineado en 8 bytes; de lo contrario, pueden suceder cosas divertidas
cuando llamamos a lo que AAPCS llama interfaces públicas (es decir, código
escrito por otros gente).
El valor de spal salir de la función debe ser el mismo valor que tenía al ingresar
a la función.
Es una convención cómo la pila, y por lo tanto la memoria local, tiene definido su
tamaño. La pila puede crecer hacia arriba o hacia abajo. Si crece hacia arriba significa que
tenemos que incrementar el valor del spregistro para poder ampliar la memoria local. Si
crece hacia abajo tenemos que hacer lo contrario, el valor del spregistro debe restarse tantos
bytes como el tamaño del almacenamiento local. En Linux ARM, la pila crece hacia abajo,
hacia cero (aunque nunca debería llegar a cero). Las direcciones de las variables locales
tienen valores muy grandes en el rango de 32 bits. Suelen estar cerca de 2 32 .
Bien, sabemos que la pila crece hacia abajo y la parte superior de la pila siempre debe estar
adentro sp. Entonces, para ampliar la memoria local debería ser suficiente
disminuyendo sp. La memoria local se define entonces por el rango de memoria desde
el spvalor actual hasta el valor original que sptenía al comienzo de la función. Un registro
que casi siempre debemos mantener es lr. Veamos cómo podemos mantenernos en la pila.
sub sp, sp, #8 /* sp ← sp - 8. This enlarges the stack by 8 bytes */
str lr, [sp] /* *sp ← lr */
... // Code of the function
ldr lr, [sp] /* lr ← *sp */
add sp, sp, #8 /* sp ← sp + 8. /* This reduces the stack by 8 bytes
effectively restoring the stack
pointer to its original value */
bx lr
Una función con buen comportamiento puede modificar sp pero debe asegurarse de que al
final tenga el mismo valor que tenía cuando ingresamos a la función. Esto es lo que
hacemos aquí. Primero restamos 8 bytes a sp y al final volvemos a agregar 8 bytes.
Esta secuencia de instrucciones sería suficiente. Pero tal vez recuerde el capítulo 8 y los
modos de indexación que podría usar para cargar y almacenar. Tenga en cuenta que las dos
primeras instrucciones se comportan exactamente como una preindexación. Primero
actualizamos spy luego usamos spcomo dirección donde almacenamos lr. ¡Esto es
exactamente un preíndice! Lo mismo ocurre con las dos últimas instrucciones. Primero
cargamos lrusando la dirección actual de spy luego disminuimos sp. ¡Esto es exactamente un
posíndice!
str lr, [sp, #-8]! /* preindex: sp ← sp - 8; *sp ← lr */
... // Code of the function
ldr lr, [sp], #+8 /* postindex; lr ← *sp; sp ← sp + 8 */
bx lr
Sí, estos modos de direccionamiento se inventaron para admitir este tipo de cosas. Usar una
sola instrucción es mejor en términos de tamaño de código. Esto puede no parecer
relevante, ¡pero es cuando nos damos cuenta de que la contabilidad de la pila es necesaria
en casi todas las funciones que escribimos!
Primer enfoque
Implementemos la función factorial anterior.
En primer lugar tenemos que aprender una nueva instrucción para multiplicar dos
números: mul Rdest, Rsource1, Rsource2. Tenga en cuenta que la multiplicación de dos valores
de 32 bits puede requerir hasta 64 bits para el resultado. Esta instrucción solo calcula los 32
bits inferiores. Debido a que no vamos a utilizar valores de 64 bits en este ejemplo, ¡el
factorial máximo que podremos calcular es 12! (13! Es mayor que 2 32 ). No verificaremos
que el número ingresado sea menor que 13 para simplificar el ejemplo (aunque le animo a
agregar esta verificación al ejemplo). En versiones de la arquitectura ARM anteriores a
ARMv6, esta instrucción no podía tener Rdestlo mismo que Rsource1. El ensamblador GNU
puede imprimir una advertencia si no aprueba -march=armv6.
1/* -- factorial01.s */
[Link]
3
4message1: .asciz "Type a number: "
5format: .asciz "%d"
6message2: .asciz "The factorial of %d is %d\n"
7
[Link]
9
10factorial:
11 str lr, [sp,#-4]! /* Push lr onto the top of the stack */
12 str r0, [sp,#-4]! /* Push r0 onto the top of the stack */
13 /* Note that after that, sp is 8 byte aligned */
14 cmp r0, #0 /* compare r0 and 0 */
15 bne is_nonzero /* if r0 != 0 then branch */
16 mov r0, #1 /* r0 ← 1. This is the return */
17 b end
18is_nonzero:
19 /* Prepare the call to factorial(n-1) */
20 sub r0, r0, #1 /* r0 ← r0 - 1 */
21 bl factorial
22 /* After the call r0 contains factorial(n-1) */
23 /* Load r0 (that we kept in th stack) into r1 */
24 ldr r1, [sp] /* r1 ← *sp */
25 mul r0, r0, r1 /* r0 ← r0 * r1 */
26
27end:
28 add sp, sp, #+4 /* Discard the r0 we kept in the stack */
29 ldr lr, [sp], #+4 /* Pop the top of the stack and put it in lr */
30 bx lr /* Leave factorial */
31
[Link] main
33main:
34 str lr, [sp,#-4]! /* Push lr onto the top of the stack */
35 sub sp, sp, #4 /* Make room for one 4 byte integer in the stack */
36 /* In these 4 bytes we will keep the number */
37 /* entered by the user */
38 /* Note that after that the stack is 8-byte aligned */
39 ldr r0, address_of_message1 /* Set &message1 as the first parameter of printf */
40 bl printf /* Call printf */
41
42 ldr r0, address_of_format /* Set &format as the first parameter of scanf */
43 mov r1, sp /* Set the top of the stack as the second parameter */
44 /* of scanf */
45 bl scanf /* Call scanf */
46
47 ldr r0, [sp] /* Load the integer read by scanf into r0 */
48 /* So we set it as the first parameter of factorial */
49 bl factorial /* Call factorial */
50
51 mov r2, r0 /* Get the result of factorial and move it to r2 */
52 /* So we set it as the third parameter of printf */
53 ldr r1, [sp] /* Load the integer read by scanf into r1 */
54 /* So we set it as the second parameter of printf */
55 ldr r0, address_of_message2 /* Set &message2 as the first parameter of printf */
56 bl printf /* Call printf */
57
58
59 add sp, sp, #+4 /* Discard the integer read by scanf */
60 ldr lr, [sp], #+4 /* Pop the top of the stack and put it in lr */
61 bx lr /* Leave main */
62
63address_of_message1: .word message1
64address_of_message2: .word message2
65address_of_format: .word format
Es importante tener en cuenta que la pila, como una pila real, el último elemento apilado
(empujado hacia arriba) será el primero en ser sacado de la pila (salido desde
arriba). Almacenamos lry dejamos espacio para un número entero de 4 bytes. Dado que se
trata de una pila, se debe utilizar el orden opuesto para devolver la pila a su estado
original. Primero descartamos el entero y luego restauramos el lr. Tenga en cuenta que esto
también sucede cuando reservamos el almacenamiento de la pila para el entero usando
a suby luego descartamos dicho almacenamiento haciendo la operación opuesta add.
Estas dos instrucciones son bastante poderosas y permiten en una sola instrucción realizar
muchas cosas. Su sintaxis se muestra a continuación. Elementos encerrados entre
llaves {y }pueden omitirse de la sintaxis (aunque el efecto de la instrucción variará).
ldm addressing-mode Rbase{!}, register-set
stm addressing-mode Rbase{!}, register-set
Lo consideraremos addressing-modemás adelante. Rbasees la dirección base utilizada para
cargar o almacenar desde el register-set. Los 16 registros ARM se pueden especificar
en register-set(excepto pcen stm). Se genera un conjunto de direcciones al ejecutar estas
instrucciones. Una dirección por registro en el conjunto de registros. Luego, cada registro,
en orden ascendente, se empareja con cada una de estas direcciones, también en orden
ascendente. De esta manera, el registro con el número más bajo obtiene la dirección de
memoria más baja y el registro con el número más alto obtiene la dirección de memoria
más alta. Cada par de direcciones de registro se utiliza para realizar la operación de
memoria: cargar o almacenar. Especificar los !medios que Rbasese actualizarán. El valor
actualizado depende de addressing-mode.
Tenga en cuenta que, si los registros están emparejados con direcciones en función de su
número de registro, parece que siempre se cargarán y almacenarán de la misma manera. Por
ejemplo, un register-setcontenedor r4, r5y r6siempre se almacenará r4en la dirección más baja
generada por la instrucción y r6en la más alta. Sin embargo, podemos especificar cuál se
considera la dirección más baja o la más alta. Entonces, ¿es Rbaserealmente la dirección más
alta o la más baja de la carga / tienda múltiple? Este es uno de los dos aspectos que
controla addressing-mode. El segundo aspecto se refiere a cuándo cambia la dirección de la
operación de memoria entre cada operación de memoria.
Si el valor en Rbasese considera la dirección más alta, significa que primero debemos
disminuir Rbasetantos bytes como requiera el número de registros en register-set(esto es 4
veces el número de registros) para formar la dirección más baja. Luego podemos cargar o
almacenar cada registro de forma consecutiva comenzando desde esa dirección más baja,
siempre en orden ascendente del número de registro. Este modo de direccionamiento se
denomina decreciente y se especifica mediante a d. Por el contrario, si Rbasese considera la
dirección más baja, entonces esto es un poco más fácil, ya que podemos usar su valor como
la dirección más baja. Procedemos como de costumbre, cargando o almacenando cada
registro en orden ascendente de su número de registro. Este modo de direccionamiento se
llama aumentoy se especifica mediante un i.
Factorial de nuevo
Antes de ilustrar estas dos instrucciones, primero reescribiremos ligeramente nuestro
factorial.
En nuestra segunda versión de factorial, guardaremos una copia del valor inicial
de r0into r4. Pero r4es un registro cuyo valor debe restaurarse al salir de una función. Así
que mantendremos el valor de r4en la entrada de la función en la pila. Al final, lo
restauraremos de la pila. De esta forma podemos usar r4sin romper las reglas de las
funciones que se comportan bien .
10factorial:
11 str lr, [sp,#-4]! /* Push lr onto the top of the stack */
12 str r4, [sp,#-4]! /* Push r4 onto the top of the stack */
13 /* The stack is now 8 byte aligned */
14 mov r4, r0 /* Keep a copy of the initial value of r0 in r4 */
15
16
17 cmp r0, #0 /* compare r0 and 0 */
18 bne is_nonzero /* if r0 != 0 then branch */
19 mov r0, #1 /* r0 ← 1. This is the return */
20 b end
21is_nonzero:
22 /* Prepare the call to factorial(n-1) */
23 sub r0, r0, #1 /* r0 ← r0 - 1 */
24 bl factorial
25 /* After the call r0 contains factorial(n-1) */
26 /* Load initial value of r0 (that we kept in r4) into r1 */
27 mov r1, r4 /* r1 ← r4 */
28 mul r0, r0, r1 /* r0 ← r0 * r1 */
29
30end:
31 ldr r4, [sp], #+4 /* Pop the top of the stack and put it in r4 */
32 ldr lr, [sp], #+4 /* Pop the top of the stack and put it in lr */
33 bx lr /* Leave factorial */
Tenga en cuenta que el resto del programa no tiene que cambiar. Esto es lo genial de las
funciones :)
Bien, ahora preste atención a estas dos secuencias en nuestra nueva versión factorial
anterior.
11 str lr, [sp,#-4]! /* Push lr onto the top of the stack */
12 str r4, [sp,#-4]! /* Push r4 onto the top of the stack */
30 ldr r4, [sp], #+4 /* Pop the top of the stack and put it in r4 */
31 ldr lr, [sp], #+4 /* Pop the top of the stack and put it in lr */
Recordar stmdb sp!y ldmia sp!puede ser un poco difícil. Además, dado que estas dos
instrucciones serán relativamente comunes al ingresar y salir de funciones, el ensamblador
GNU proporciona dos mnemónicos push y poppara stmdb sp!y ldmia sp!,
respectivamente. Tenga en cuenta que estas no son instrucciones ARM en realidad, solo
nombres de conveniencia que son más fáciles de recordar.
11 push {r4, lr}
30
pop {r4, lr}
Varias veces, en capítulos anteriores, dije que la arquitectura ARM se diseñó teniendo en
cuenta el mundo integrado. Aunque el costo de la memoria es cada día más bajo, aún puede
representar una parte importante del presupuesto de un sistema integrado. El conjunto de
instrucciones ARM tiene varias características destinadas a reducir el impacto del tamaño
del código. Una de las características que ayuda en tal enfoque es la predicación .
Predicación
Vimos en los capítulos 6 y 7 cómo usar ramas en nuestro programa para modificar el flujo
de ejecución de instrucciones e implementar estructuras de control útiles. Las ramas pueden
ser incondicionales, por ejemplo, cuando llamamos a una función como hicimos en los
capítulos 9 y 10, o condicionales cuando queremos saltar a alguna parte del código solo
cuando se cumple una condición previamente probada.
La predicación está relacionada con las ramas condicionales. ¿Qué pasaría si, en lugar de
ramificación a alguna parte del código destinado a ser ejecutado sólo cuando una
condición Cse mantiene, hemos sido capaces de convertir algunas
instrucciones apagado cuando esa Ccondición no se cumple ?. Considere un caso como
este.
if (C)
T();
else
E();
Usando la predicación (y con alguna sintaxis inventada para expresarla) podríamos escribir
lo anterior de la siguiente manera.
P = C;
[P] T();
[!P] E();
De esta forma evitamos las ramas. Pero, ¿por qué querría evitar las ramas? Bueno, ejecutar
una rama condicional implica un poco de incertidumbre. Pero esto merece un poco de
explicación.
En esta línea de montaje, el trabajador que comprueba el estado de una rama condicional no
es el primero sino el tercero. Ahora considere lo que sucede cuando el primer trabajador
obtiene una rama condicional y la coloca en la línea de ensamblaje. El segundo trabajador
lo procesará y lo pasará al tercero. El tercero lo procesará verificando la condición de la
rama condicional. Si no se mantiene, no pasa nada, la rama no tiene ningún efecto. Pero si
la condición se cumple, el tercer trabajador debe notificar al primero que la siguiente
instrucción obtenida debe ser la instrucción en la dirección de la sucursal.
Pero ahora hay dos instrucciones en la línea de ensamblaje que no deberían ejecutarse por
completo (las que estaban físicamente después de la rama condicional). Aquí hay varias
opciones. El tercer trabajador puede elegir dos pegatinas etiquetadas como NO HACER
NADA y pegarlas en las dos siguientes instrucciones. Otro enfoque sería que el tercer
trabajador le diga al primero y al segundo trabajador "Hola chicos, NO HAGAN NADA a su
instrucción actual". Trabajadores posteriores, cuando vean que estas pegatinas NO HACEN
NADA , no harán nada. De esta manera, cada instrucción de NO HACER NADA nunca se
ejecutará por completo.
Pero al hacer esto, esa bonita propiedad de nuestra línea de ensamblaje desaparece: ahora
no tenemos una instrucción completamente ejecutada cada 6 segundos. De hecho, después
de la rama condicional hay dos instrucciones de NO HACER NADA . Un programa que se
ramifica constantemente puede reducir el rendimiento de nuestra línea de montaje de una
instrucción (útil) cada 6 segundos a una instrucción cada 18 segundos. ¡Esto es tres veces
más lento!
Volviendo al ejemplo de la línea de montaje, sería el primer trabajador que intenta predecir
dónde se llevará o no la sucursal. Es el tercer trabajador quien verifica si el primer
trabajador hizo la predicción correcta. Si el primer trabajador predijo mal la sucursal,
entonces tenemos que volver a aplicar dos pegatinas y notificar al primer trabajador cuál es
la dirección correcta de la siguiente instrucción. Si el primer trabajador predijo
correctamente la rama, no se tiene que hacer nada especial, lo cual es genial.
Así que termina, como de costumbre, que ningún enfoque es perfecto por sí solo.
Predicación en ARM
En ARM, la predicación es muy simple de usar: casi todas las instrucciones se pueden
predicar. El predicado se especifica como sufijo del nombre de la instrucción. El sufijo es
exactamente el mismo que los utilizados en las ramas en el capítulo
5: eq, neq, le, lt, gey gt. Instrucciones que no se predican se supone que tienen un sufijo alde
pie para AL maneras . Ese predicado siempre es válido y no lo escribimos por economía
(aunque es válido). Puede entender las ramas condicionales como ramas predicadas si lo
desea.
1/* -- collatz02.s */
[Link]
3
4message: .asciz "Type a number: "
5scan_format : .asciz "%d"
6message2: .asciz "Length of the Hailstone sequence for %d is %d\n"
7
[Link]
9
10collatz:
11 /* r0 contains the first argument */
12 /* Only r0, r1 and r2 are modified,
13 so we do not need to keep anything
14 in the stack */
15 /* Since we do not do any call, we do
16 not have to keep lr either */
17 mov r1, r0 /* r1 ← r0 */
18 mov r0, #0 /* r0 ← 0 */
19 collatz_loop:
20 cmp r1, #1 /* compare r1 and 1 */
21 beq collatz_end /* if r1 == 1 branch to collatz_end */
22 and r2, r1, #1 /* r2 ← r1 & 1 */
23 cmp r2, #0 /* compare r2 and 0 */
24 bne collatz_odd /* if r2 != 0 (this is r1 % 2 != 0) branch to collatz_odd */
25 collatz_even:
26 mov r1, r1, ASR #1 /* r1 ← r1 >> 1. This is r1 ← r1/2 */
27 b collatz_end_loop /* branch to collatz_end_loop */
28 collatz_odd:
29 add r1, r1, r1, LSL #1 /* r1 ← r1 + (r1 << 1). This is r1 ← 3*r1 */
30 add r1, r1, #1 /* r1 ← r1 + 1. */
31 collatz_end_loop:
32 add r0, r0, #1 /* r0 ← r0 + 1 */
33 b collatz_loop /* branch back to collatz_loop */
34 collatz_end:
35 bx lr
36
[Link] main
38main:
39 push {lr} /* keep lr */
40 sub sp, sp, #4 /* make room for 4 bytes in the stack */
41 /* The stack is already 8 byte aligned */
42
43 ldr r0, address_of_message /* first parameter of printf: &message */
44 bl printf /* call printf */
45
46 ldr r0, address_of_scan_format /* first parameter of scanf: &scan_format */
47 mov r1, sp /* second parameter of scanf:
48 address of the top of the stack */
49 bl scanf /* call scanf */
50
51 ldr r0, [sp] /* first parameter of collatz:
52 the value stored (by scanf) in the top of the stack */
53 bl collatz /* call collatz */
54
55 mov r2, r0 /* third parameter of printf:
56 the result of collatz */
57 ldr r1, [sp] /* second parameter of printf:
58 the value stored (by scanf) in the top of the stack */
59 ldr r0, address_of_message2 /* first parameter of printf: &address_of_message2 */
60 bl printf
61
62 add sp, sp, #4
63 pop {lr}
64 bx lr
65
66
67address_of_message: .word message
68address_of_scan_format: .word scan_format
69address_of_message2: .word message2
Agregar predicación
Ok, agreguemos un poco de predicación. Hay una construcción if-then-else en las líneas 22
a 31. Allí verificamos si el número es par o impar. Si incluso lo dividimos por 2, si incluso
lo multiplicamos por 3 y sumamos 1.
A continuación se muestran las versiones que utilicé para esta comparación. Primero está la
versión de las ramas, segundo la versión de la predicación.
1collatz:
2 /* r0 contains the first argument */
3 push {r4}
4 sub sp, sp, #4 /* Make sure the stack is 8 byte aligned */
5 mov r4, r0
6 mov r3, #4194304
7 collatz_repeat:
8 mov r1, r4 /* r1 ← r0 */
9 mov r0, #0 /* r0 ← 0 */
10 collatz_loop:
11 cmp r1, #1 /* compare r1 and 1 */
12 beq collatz_end /* if r1 == 1 branch to collatz_end */
13 and r2, r1, #1 /* r2 ← r1 & 1 */
14 cmp r2, #0 /* compare r2 and 0 */
15 bne collatz_odd /* if r2 != 0 (this is r1 % 2 != 0) branch to collatz_odd */
16 collatz_even:
17 mov r1, r1, ASR #1 /* r1 ← r1 >> 1. This is r1 ← r1/2 */
18 b collatz_end_loop /* branch to collatz_end_loop */
19 collatz_odd:
20 add r1, r1, r1, LSL #1 /* r1 ← r1 + (r1 << 1). This is r1 ← 3*r1 */
21 add r1, r1, #1 /* r1 ← r1 + 1. */
22 collatz_end_loop:
23 add r0, r0, #1 /* r0 ← r0 + 1 */
24 b collatz_loop /* branch back to collatz_loop */
25 collatz_end:
26 sub r3, r3, #1
27 cmp r3, #0
28 bne collatz_repeat
29 add sp, sp, #4 /* Make sure the stack is 8 byte aligned */
30 pop {r4}
31 bx lr
1collatz2:
2 /* r0 contains the first argument */
3 push {r4}
4 sub sp, sp, #4 /* Make sure the stack is 8 byte aligned */
5 mov r4, r0
6 mov r3, #4194304
7 collatz_repeat:
8 mov r1, r4 /* r1 ← r0 */
9 mov r0, #0 /* r0 ← 0 */
10 collatz2_loop:
11 cmp r1, #1 /* compare r1 and 1 */
12 beq collatz2_end /* if r1 == 1 branch to collatz2_end */
13 and r2, r1, #1 /* r2 ← r1 & 1 */
14 cmp r2, #0 /* compare r2 and 0 */
15 moveq r1, r1, ASR #1 /* if r2 == 0, r1 ← r1 >> 1. This is r1 ← r1/2 */
16 addne r1, r1, r1, LSL #1 /* if r2 != 0, r1 ← r1 + (r1 << 1). This is r1 ← 3*r1 */
17 addne r1, r1, #1 /* if r2 != 0, r1 ← r1 + 1. */
18 collatz2_end_loop:
19 add r0, r0, #1 /* r0 ← r0 + 1 */
20 b collatz2_loop /* branch back to collatz2_loop */
21 collatz2_end:
22 sub r3, r3, #1
23 cmp r3, #0
24 bne collatz_repeat
25 add sp, sp, #4 /* Restore the stack */
26 pop {r4}
27 bx lr
Podemos manipular bucles para obtener una forma que sea más conveniente. Por ejemplo.
do
S
while (E);
/* Can be rewritten as */
S;
while (E)
S;
while (E)
S;
/* Can be rewritten as */
if (E)
{
do
S
while (E);
}
La última manipulación es interesante, porque podemos evitar la if-thensi vamos
directamente a la whilepieza.
/* This is not valid C */
goto check;
do
S
check: while (E);
En C válido, la transformación anterior se escribiría de la siguiente manera.
goto check;
loop:
S;
check:
if (E) goto loop;
Lo que parece mucho más feo que abusar de un poco de sintaxis C.
El sufijo -s
Hasta ahora, al verificar la condición de un ifo while, hemos evaluado la condición y luego
usamos la cmpinstrucción para actualizar cpsr. La actualización de cpsres obligatoria para
nuestros códigos condicionales, sin importar si usamos ramificación o
predicación. Pero cmpno es la única forma de actualizar cpsr. De hecho, muchas
instrucciones pueden actualizarlo.
¿Cómo podemos usar esto? Bueno, considere este simple ciclo contando hacia atrás.
/* for (int i = 100 ; i >= 0; i--) */
mov r1, #100
loop:
/* do something */
sub r1, r1, #1 /* r1 ← r1 - 1 */
cmp r1, #0 /* update cpsr with r1 - 0 */
bge loop /* branch if r1 >= 100 */
Si reemplazamos subpor subsentonces cpsrse actualizará con el resultado de la
sustracción. Esto significa que las banderas N, Z, C y V se actualizarán, por lo que
podemos usar una rama inmediatamente después subs. En nuestro caso, queremos volver al
bucle solo si i >= 0, aquí es cuando el resultado no es negativo. Podemos utilizar bplpara
lograr esto.
/* for (int i = 100 ; i >= 0; i--) */
mov r1, #100
loop:
/* do something */
subs r1, r1, #1 /* r1 ← r1 - 1 and update cpsr with the final r1 */
bpl loop /* branch if the previous sub computed a positive number (N flag in cpsr is 0) */
Es un poco complicado hacer estas cosas bien (es por eso que usamos compiladores). Por
ejemplo, este bucle similar, pero no idéntico, usaría en bnelugar de bpl. Aquí la condición
es ne(no igual). Sería bueno tener un alias como nz(no cero) pero, desafortunadamente, esto
no existe en ARM.
/* for (int i = 100 ; i > 0; i--). Note here i > 0, not i >= 0 as in the example above */
mov r1, #100
loop:
/* do something */
subs r1, r1, #1 /* r1 ← r1 - 1 and update cpsr with the final r1 */
bne loop /* branch if the previous sub computed a number that is not zero (Z flag in cpsr is 0) */
Una regla general en la que es posible que deseemos aplicar el uso del sufijo -s es en los
códigos de la siguiente forma.
s = ...
if (s @ 0)
donde @significa cualquier comparación con respecto a 0 (igual, diferente, menor, etc.).
Adición
Agregar dos números de 64 bits usando operandos de 32 bits significa agregar primero la
parte inferior y luego agregar las partes superiores, pero teniendo en cuenta un posible
arrastre desde la parte inferior. Con nuestro conocimiento actual, podríamos escribir algo
como esto (suponga que el primer número está adentro {r2,r3}, el segundo adentro {r4,r5}y el
resultado estará adentro {r0,r1}).
add r1, r3, r5 /* First we add the higher part */
/* r1 ← r3 + r5 */
adds r0, r2, r4 /* Now we add the lower part and we update cpsr */
/* r0 ← r2 + r4 */
addcs r1, r1, #1 /* If adding the lower part caused carry, add 1 to the higher part */
/* if C = 1 then r1 ← r1 + 1 */
/* Note that here the suffix -s is not applied, -cs means carry set */
Esto funcionaría. Afortunadamente, ARM proporciona instrucciones adcque suman dos
números y la bandera de acarreo. Entonces podríamos reescribir el código anterior con solo
dos instrucciones.
adds r0, r2, r4 /* First add the lower part and update cpsr */
/* r0 ← r2 + r4 */
adc r1, r3, r5 /* Now add the higher part plus the carry from the lower one */
/* r1 ← r3 + r5 + C */
Sustracción
Restar dos números es similar a sumarlos. En ARM, al restar dos números usando subs, si
necesitamos pedir prestado (porque el segundo operando es más grande que el primero), C
se desactivará (C será 0). Si no necesitamos pedir prestado, se habilitará C (C será 1). Esto
es un poco sorprendente pero coherente con el resto de la arquitectura (consulte las
condiciones CS / HS y CC / LO del capítulo 5). Similar a adchay a sbcque realiza una resta
normal si C es 1. De lo contrario, resta un elemento más. Nuevamente, esto es coherente
con el funcionamiento de C en la subsinstrucción.
subs r0, r2, r4 /* First subtract the lower part and update cpsr */
/* r0 ← r2 - r4 */
sbc r1, r3, r5 /* Now subtract the higher part plus the NOT of the carry from the lower one */
/* r1 ← r3 - r5 - ~C */
Multiplicación
Multiplicar dos números de 64 bits es complicado. Cuando multiplicamos dos números de
N bits, el resultado puede necesitar hasta 2 * N bits. Entonces, al multiplicar dos números
de 64 bits, es posible que necesitemos un número de 128 bits. En aras de la simplicidad,
asumiremos que esto no sucede y que 64 bits serán suficientes. Nuestros números de 64 bits
son dos enteros de 32 bits, por lo que una x de 64 bits es en realidad x = 2 32 × x 1 + x 0 ,
donde x 1 y x 0 son dos números de 32 bits. De manera similar, otro número y de 64 bits
sería y = 2 32 × y 1 + y 0 . Al multiplicar xey se obtiene z donde z = 2 64 × x 1 × y 1 + 2 32×
(x 0 × y 1 + x 1 × y 0 ) + x 0 × y 0 . Bueno, ahora nuestro problema es multiplicar cada x i por
y i , pero nuevamente es posible que necesitemos 64 bits para representar el valor.
En este ejemplo tenemos que usar, de lo umullcontrario, las partes inferiores de 32 bits
podrían terminar interpretándose como números negativos, dando valores intermedios
negativos. Dicho esto, ahora podemos multiplicar x 0 e y 0 . Recuerde que tenemos los dos
números de 64 bits r2,r3y r4,r5pares de registros. Así que primero multiplica r2y r4. Tenga en
cuenta el uso de r0ya que este será su valor final. Por el contrario, el registro r6se utilizará
más tarde.
umull r0, r6, r2, r4
Ahora multipliquemos x 0 por y 1 y x 1 por y 0 . Esto es r3por r4y r2por r5. Observe cómo
sobrescribimos r4y r5en la segunda multiplicación. Esto está bien, ya que ya no los
necesitaremos.
umull r7, r8, r3, r4
umull r4, r5, r2, r5
No es necesario multiplicar x 1 por y 1 porque si da un valor distinto de cero, siempre
desbordará un número de 64 bits. Esto significa que si ambos r3y r5fueran distintos de cero,
la multiplicación nunca se ajustará a 64 bits. Ésta es una condición suficiente, pero no
necesaria. El número puede desbordarse al agregar los valores intermedios que
resultarán r1.
adds r2, r7, r4
adc r1, r2, r6
Empaquetemos este código en una función agradable en un programa para ver si
funciona. Multiplicaremos los números 12345678901 (esto es 2 × 2 32 + 3755744309) y
12345678 e imprimiremos el resultado.
1/* -- mult64.s */
[Link]
3
[Link] 4
5message : .asciz "Multiplication of %lld by %lld is %lld\n"
6
[Link] 8
8number_a_low: .word 3755744309
9number_a_high: .word 2
10
[Link] 8
12number_b_low: .word 12345678
13number_b_high: .word 0
14
[Link]
16
17/* Note: This is not the most efficient way to doa 64-bit multiplication.
18 This is for illustration purposes */
19mult64:
20 /* The argument will be passed in r0, r1 and r2, r3 and returned in r0, r1 */
21 /* Keep the registers that we are going to write */
22 push {r4, r5, r6, r7, r8, lr}
23 /* For covenience, move {r0,r1} into {r4,r5} */
24 mov r4, r0 /* r0 ← r4 */
25 mov r5, r1 /* r5 ← r1 */
26
27 umull r0, r6, r2, r4 /* {r0,r6} ← r2 * r4 */
28 umull r7, r8, r3, r4 /* {r7,r8} ← r3 * r4 */
29 umull r4, r5, r2, r5 /* {r4,r5} ← r2 * r5 */
30 adds r2, r7, r4 /* r2 ← r7 + r4 and update cpsr */
31 adc r1, r2, r6 /* r1 ← r2 + r6 + C */
32
33 /* Restore registers */
34 pop {r4, r5, r6, r7, r8, lr}
35 bx lr /* Leave mult64 */
36
[Link] main
38main:
39 push {r4, r5, r6, r7, r8, lr} /* Keep the registers we are going to modify */
40 /* r8 is not actually used here, but this way
41 the stack is already 8-byte aligned */
42 /* Load the numbers from memory */
43 /* {r4,r5} ← a */
44 ldr r4, addr_number_a_low /* r4 ← &a_low */
45 ldr r4, [r4] /* r4 ← *r4 */
46 ldr r5, addr_number_a_high /* r5 ← &a_high */
47 ldr r5, [r5] /* r5 ← *r5 */
48
49 /* {r6,r7} ← b */
50 ldr r6, addr_number_b_low /* r6 ← &b_low */
51 ldr r6, [r6] /* r6 ← *r6 */
52 ldr r7, addr_number_b_high /* r7 ← &b_high */
53 ldr r7, [r7] /* r7 ← *r7 */
54
55 /* Now prepare the call to mult64
56 /*
57 The first number is passed in
58 registers {r0,r1} and the second one in {r2,r3}
59 */
60 mov r0, r4 /* r0 ← r4 */
61 mov r1, r5 /* r1 ← r5 */
62
63 mov r2, r6 /* r2 ← r6 */
64 mov r3, r7 /* r3 ← r7 */
65
66 bl mult64 /* call mult64 function */
67 /* The result of the multiplication is in r0,r1 */
68
69 /* Now prepare the call to printf */
70 /* We have to pass &message, {r4,r5}, {r6,r7} and {r0,r1} */
71 push {r1} /* Push r1 onto the stack. 4th (higher) parameter */
72 push {r0} /* Push r0 onto the stack. 4th (lower) parameter */
73 push {r7} /* Push r7 onto the stack. 3rd (higher) parameter */
74 push {r6} /* Push r6 onto the stack. 3rd (lower) parameter */
75 mov r3, r5 /* r3 ← r5. 2rd (higher) parameter */
76 mov r2, r4 /* r2 ← r4. 2nd (lower) parameter */
77 ldr r0, addr_of_message /* r0 ← &message 1st parameter */
78 bl printf /* Call printf */
79 add sp, sp, #16 /* sp ← sp + 16 */
80 /* Pop the two registers we pushed above */
81
82 mov r0, #0 /* r0 ← 0 */
83 pop {r4, r5, r6, r7, r8, lr} /* Restore the registers we kept */
84 bx lr /* Leave main */
85
86addr_of_message : .word message
87addr_number_a_low: .word number_a_low
88addr_number_a_high: .word number_a_high
89addr_number_b_low: .word number_b_low
90addr_number_b_high: .word number_b_high
Observe primero que tenemos las direcciones de la parte inferior y superior de cada
número. En lugar de esto, podríamos cargarlos simplemente usando un desplazamiento,
como vimos en el capítulo 8. Entonces, en las líneas 41 a 44 podríamos haber hecho lo
siguiente.
40 /* {r4,r5} ← a */
41 ldr r4, addr_number_a_low /* r4 ← &a_low */
42 ldr r5, [r4, +#4] /* r5 ← *(r4 + 4) */
43 ldr r4, [r4] /* r4 ← *r4 */
En la función mult64pasamos el primer valor (x) como r0,r1y el segundo valor (y)
como r2,r3. El resultado se almacena en formato r0,r1. Movemos los valores a los registros
apropiados para el paso de parámetros en las líneas 57 a 61.
1. Debe asegurarse de que la pila esté alineada para los datos que va a pasar (ajustando la
pila primero). Entonces, para números de 64 bits, la pila debe estar alineada con 8
bytes. Si pasa un número de 32 bits y luego un número de 64 bits, tendrá que omitir 4
bytes antes de pasar el número de 64 bits. No olvide mantener la pila siempre alineada
en 8 bytes según el requisito del estándar de llamada a procedimiento para arquitectura
ARM (AAPCS).
2. Un argumento con un número de posición más bajo en la llamada debe tener una
dirección más baja en la pila. Entonces tenemos que pasar los argumentos en orden
opuesto.
La segunda regla es la que explica por qué presionamos primero r1y luego r0, cuando son
los registros que contienen el último número de 64 bits (el resultado de la multiplicación) al
que queremos pasar printf.
Tenga en cuenta que en el ejemplo anterior, no podemos pasar los parámetros en la pila
usando push {r0,r1,r6,r7}, que es equivalente a push {r0}, push {r1}, push {r6}y push {r7}, pero no
es equivalente a la orden requerido al pasar los argumentos en la pila.
Hasta ahora, todos los ejemplos se han ocupado de valores enteros. Pero los procesadores
serían bastante limitados si solo pudieran trabajar con valores enteros. Afortunadamente,
pueden trabajar con números de coma flotante. En este capítulo veremos cómo podemos
utilizar las instalaciones de punto flotante de nuestra Raspberry Pi.
Números de punto flotante
A continuación se muestra un resumen rápido de lo que es un número de punto flotante.
Para que diferentes computadoras puedan compartir números de punto flotante, IEEE 754
estandariza el formato de un número de punto flotante. VFPv2 admite dos de los números
IEEE 754: Binary32 y Binary64, generalmente conocidos por sus tipos C floaty double, o por
precisión simple y doble, respectivamente. En un punto flotante de precisión simple, la
mantisa es de 23 bits (+1 del entero para números normalizados) y el exponente es de 8 bits
(por lo que el exponente varía de -126 a 127). En un punto flotante de doble precisiónla
mantisa es de 52 bits (+1) y el exponente es de 11 bits (por lo que el exponente varía de
-1022 a 1023). Un número de coma flotante de precisión simple ocupa 32 bits y un número
de coma flotante de precisión doble ocupa 64 bits. La operación de números de doble
precisión es, en promedio, una y media o dos veces más lenta que la de precisión simple.
El famoso artículo de Goldberg es una referencia clásica que cualquier persona seria
debería leer cuando utilice números de coma flotante.
Coprocesadores
Como dije varias veces en capítulos anteriores, ARM fue diseñado para ser muy
flexible. Podemos ver esto en el hecho de que la arquitectura ARM proporciona una
interfaz de coprocesador genérica. Los fabricantes de sistemas en chips pueden agrupar
coprocesadores adicionales. Cada coprocesador se identifica con un número y proporciona
instrucciones específicas. Por ejemplo, el Raspberry Pi SoC es un BCM2835 que
proporciona un coprocesador multimedia (que no discutiremos aquí).
Dicho esto, hay dos coprocesadores estándar en la arquitectura ARMv6: 10 y 11. Estos dos
coprocesadores brindan soporte de punto flotante para precisión simple y doble,
respectivamente. Aunque las instrucciones de punto flotante tienen sus propios nombres
específicos, en realidad se asignan a instrucciones de coprocesador genéricas dirigidas al
coprocesador 10 y 11.
Registros VFPv2
Ya sabemos que la arquitectura ARM proporciona 16 registros de propósito general, r0a r15,
donde algunos de ellos desempeñan papeles especiales: r13, r14y r15. A pesar de su nombre,
estos registros de propósito general no permiten operar números de punto flotante en ellos,
por lo que VFPv2 nos proporciona algunos registros específicos. Estos registros se
nombran s0para s31, para precisión simple y d0para d15para precisión doble. Estos no son 48
registros diferentes. En su lugar, cada se asigna a dos registros (consecutivos) y , donde 0
≤ ≤ 15. dns2ns2n+1n
Operaciones aritmeticas
La mayoría de las instrucciones de VFPv2 tienen el formato o . Tienen tres modos de
funcionamiento. vname Rdest, Rsource1, Rsource2fname Rdest, Rsource1
Ok, esto parece bastante complicado, así que veamos algunos ejemplos. La mayoría de las
instrucciones terminan en .f32si operan en precisión simple y en .f64si operan en precisión
doble. Podemos sumar dos números de precisión simple usando vadd.f32 Rdest, Rsource1,
Rsource2y doble precisión usando vadd.f64 Rdest, Rsource1, Rsource2. Tenga en cuenta también
que podemos usar la predicación en estas instrucciones (pero tenga en cuenta que, como de
costumbre, la predicación usa las banderas en cpsrno en fpscr). La predicación se
especificaría antes del sufijo como en vaddne.f32.
// For this example assume that len = 4, stride = 2
vadd.f32 s1, s2, s3 /* s1 ← s2 + s3. Scalar operation because Rdest = s1 in the bank 0 */
vadd.f32 s1, s8, s15 /* s1 ← s8 + s15. ditto */
vadd.f32 s8, s16, s24 /* s8 ← s16 + s24
s10 ← s18 + s26
s12 ← s20 + s28
s14 ← s22 + s30
or more compactly {s8,s10,s12,s14} ← {s16,s18,s20,s22} + {s24,s26,s28,s30}
Vectorial, since Rdest and Rsource2 are not in bank 0
*/
vadd.f32 s10, s16, s24 /* {s10,s12,s14,s8} ← {s16,s18,s20,s22} + {s24,s26,s28,s30}.
Vectorial, but note the wraparound inside the bank after s14.
*/
vadd.f32 s8, s16, s3 /* {s8,s10,s12,s14} ← {s16,s18,s20,s22} + {s3,s3,s3,s3}
Scalar expanded since Rsource2 is in the bank 0
*/
Cargar y almacenar
Una vez que tenemos una idea aproximada de cómo podemos operar puntos flotantes en
VFPv2, queda una pregunta: ¿cómo cargamos / almacenamos valores de punto flotante
desde / hacia la memoria? VFPv2 proporciona varias instrucciones específicas de carga /
almacenamiento.
Conversiones
A veces necesitamos convertir de un número entero a un punto flotante y lo
contrario. Tenga en cuenta que algunas conversiones pueden perder precisión, en particular,
cuando un punto flotante se convierte en un número entero. Hay una sola
instrucción vcvtcon un sufijo .[Link] T(objetivo) y S(fuente) se
puede u32, s32, f32y f64( Sdeben ser diferentes a T). Ambos registros deben ser registros de
coma flotante, por lo que para convertir enteros a coma flotante o coma flotante a un valor
entero, un extravmovSe requerirá instrucción desde o hacia un registro entero antes o
después de la conversión. Debido a esto, por un momento (entre las dos instrucciones) un
registro de punto flotante contendrá un valor que no es un valor IEEE 754, téngalo en
cuenta.
vcvt.f64.f32 d0, s0 /* Converts s0 single-precision value
to a double-precision value and stores it in d0 */
Modificar fpscr
El fpscr registro especial, donde leny stridese establecen, no se puede modificar
directamente. En su lugar, tenemos que cargar fpscr en un registro de propósito general
usando vmrsinstrucción. Luego operamos en el registro y lo volvemos a mover al fpscr,
usando la vmsrinstrucción.
Finalmente, una nota sobre funciones variadas como printf: no puede pasar un punto
flotante de precisión simple a una de estas funciones. Solo se pueden pasar dobles. Por lo
tanto, deberá convertir los valores de precisión simple en valores de precisión doble. Tenga
en cuenta también que se utilizan registros enteros habituales ( r0- r3), por lo que solo podrá
pasar hasta 2 valores de doble precisión, el resto debe pasarse a la pila. En particular
para printf, dado que r0contiene la dirección del formato de cadena, solo podrá pasar una
precisión doble en {r2,r3}.
Ensamblador
Asegúrese de pasar la bandera -mfpu=vfpv2a as, de lo contrario, no reconocerá las
instrucciones de VFPv2.
Colofón
Es posible que desee consultar esta tarjeta de referencia rápida oficial de VFP . Tenga en
cuenta que también incluye VFPv3 no disponible en el procesador Raspberry Pi. La mayor
parte de lo que hay allí ya se ha presentado aquí, aunque es posible que se hayan omitido
algunos detalles menores.
Matriz multiplicar
Dados dos vectores v y w de rango r donde v = <v 0 , v 1 , ... v r-1 > y w = <w 0 , w 1 , ..., w r-
1 >, definimos el producto escalar de v por w como el escalar v · w = v 0 × w 0 + v 1 ×
w 1 + ... + v r-1 × w r-1 .
Podemos multiplicar una matriz Ade nfilas y mcolumnas ( nx m) por una matriz Bde mfilas
y pcolumnas ( mx p). El resultado es una matriz de nfilas y pcolumnas. La multiplicación de
matrices puede parecer complicada, pero en realidad no lo es. Cada elemento en la matriz
de resultados es solo el producto escalar (definido en el párrafo anterior) de la fila
correspondiente de la matriz Apor la columna correspondiente de la matriz B(es por eso que
debe haber tantas columnas Acomo filas B) .
Para simplificar el ejemplo, asumiremos que ambas matrices A y B son matrices cuadradas
de tamaño n x n. Esto simplifica un poco el algoritmo.
1float A[N][N];
2float B[N][N];
3// Result
4float C[N][N];
5
6for (int i = 0; i < N; i++)
7{
8 for (int j = 0; j < N; j++)
9 {
10 C[i][j] = 0;
11 for (int k = 0; k < N; k++)
12 C[i][j] += A[i][k] * B[k][j];
13 }
14}
Una primera mejora que queremos hacer en este algoritmo es hacer que los bucles estén
perfectamente anidados. Hay algunas razones técnicas más allá del alcance de este código
para eso. Entonces nos desharemos de la inicialización de C[i][j]a 0, fuera del ciclo.
1float A[N][N];
2float B[M][N];
3// Result
4float C[N][N];
5
6for (int i = 0; i < N; i++)
7 for (int j = 0; j < N; j++)
8 C[i][j] = 0;
9
10for (int i = 0; i < N; i++)
11 for (int j = 0; j < N; j++)
12 for (int k = 0; k < N; k++)
13 C[i][j] += A[i][k] * B[k][j];
Después de este cambio, la parte interesante de nuestro algoritmo, la línea 13, está dentro
de un nido perfecto de bucles de profundidad 3.
Las cosas se complican un poco más cuando nuestra matriz tiene más de una dimensión,
como una matriz o un cubo. Dado un acceso como a[i][j][k]tenemos que calcular qué
elemento se denota por [i][j][k]. Esto depende de si el idioma es un orden de fila principal o
de columna principal. Asumimos aquí el orden de las filas principales (como en el lenguaje
C). Por [i][j][k]lo tanto, debe indicar k + j * NK + i * NK * NJdónde NKy NJson el número de
elementos en cada dimensión. Por ejemplo, una matriz tridimensional de 3 x 4 x 5
elementos, el elemento [1] [2] [3] es 3 + 2 * 5 + 1 * 5 * 4 = 23 (aquí NK= 5 y NJ= 4. Tenga
en cuenta queNI= 3 pero no lo necesitamos en absoluto). Suponemos que nuestro lenguaje
indexa matrices a partir de 0 (como C). Si el idioma permite un límite inferior distinto de 0,
primero tenemos que restar el límite inferior para obtener la posición.
1/* -- matmul.s */
[Link]
3mat_A: .float 0.1, 0.2, 0.0, 0.1
4 .float 0.2, 0.1, 0.3, 0.0
5 .float 0.0, 0.3, 0.1, 0.5
6 .float 0.0, 0.6, 0.4, 0.1
7mat_B: .float 4.92, 2.54, -0.63, -1.75
8 .float 3.02, -1.51, -0.87, 1.35
9 .float -4.29, 2.14, 0.71, 0.71
10 .float -0.95, 0.48, 2.38, -0.95
11mat_C: .float 0.0, 0.0, 0.0, 0.0
12 .float 0.0, 0.0, 0.0, 0.0
13 .float 0.0, 0.0, 0.0, 0.0
14 .float 0.0, 0.0, 0.0, 0.0
15 .float 0.0, 0.0, 0.0, 0.0
16
17format_result : .asciz "Matrix result is:\n%5.2f %5.2f %5.2f %5.2f\n%5.2f %5.2f %5.2f %5.2f\n%5.2f %5.2f %5.2f %5.2f\n%
18
[Link]
20
21naive_matmul_4x4:
22 /* r0 address of A
23 r1 address of B
24 r2 address of C
25 */
26 push {r4, r5, r6, r7, r8, lr} /* Keep integer registers */
27 /* First zero 16 single floating point */
28 /* In IEEE 754, all bits cleared means 0 */
29 mov r4, r2
30 mov r5, #16
31 mov r6, #0
32 b .Lloop_init_test
33 .Lloop_init :
34 str r6, [r4], +#4 /* *r4 ← r6 then r4 ← r4 + 4 */
35 .Lloop_init_test:
36 subs r5, r5, #1
37 bge .Lloop_init
38
39 /* We will use
40 r4 as i
41 r5 as j
42 r6 as k
43 */
44 mov r4, #0 /* r4 ← 0 */
45 .Lloop_i: /* loop header of i */
46 cmp r4, #4 /* if r4 == 4 goto end of the loop i */
47 beq .Lend_loop_i
48 mov r5, #0 /* r5 ← 0 */
49 .Lloop_j: /* loop header of j */
50 cmp r5, #4 /* if r5 == 4 goto end of the loop j */
51 beq .Lend_loop_j
52 /* Compute the address of C[i][j] and load it into s0 */
53 /* Address of C[i][j] is C + 4*(4 * i + j) */
54 mov r7, r5 /* r7 ← r5. This is r7 ← j */
55 adds r7, r7, r4, LSL #2 /* r7 ← r7 + (r4 << 2).
56 This is r7 ← j + i * 4.
57 We multiply i by the row size (4 elements) */
58 adds r7, r2, r7, LSL #2 /* r7 ← r2 + (r7 << 2).
59 This is r7 ← C + 4*(j + i * 4)
60 We multiply (j + i * 4) by the size of the element.
61 A single-precision floating point takes 4 bytes.
62 */
63 vldr s0, [r7] /* s0 ← *r7 */
64
65 mov r6, #0 /* r6 ← 0 */
66 .Lloop_k : /* loop header of k */
67 cmp r6, #4 /* if r6 == 4 goto end of the loop k */
68 beq .Lend_loop_k
69
70 /* Compute the address of a[i][k] and load it into s1 */
71 /* Address of a[i][k] is a + 4*(4 * i + k) */
72 mov r8, r6 /* r8 ← r6. This is r8 ← k */
73 adds r8, r8, r4, LSL #2 /* r8 ← r8 + (r4 << 2). This is r8 ← k + i * 4 */
74 adds r8, r0, r8, LSL #2 /* r8 ← r0 + (r8 << 2). This is r8 ← a + 4*(k + i * 4) */
75 vldr s1, [r8] /* s1 ← *r8 */
76
77 /* Compute the address of b[k][j] and load it into s2 */
78 /* Address of b[k][j] is b + 4*(4 * k + j) */
79 mov r8, r5 /* r8 ← r5. This is r8 ← j */
80 adds r8, r8, r6, LSL #2 /* r8 ← r8 + (r6 << 2). This is r8 ← j + k * 4 */
81 adds r8, r1, r8, LSL #2 /* r8 ← r1 + (r8 << 2). This is r8 ← b + 4*(j + k * 4) */
82 vldr s2, [r8] /* s1 ← *r8 */
83
84 vmul.f32 s3, s1, s2 /* s3 ← s1 * s2 */
85 vadd.f32 s0, s0, s3 /* s0 ← s0 + s3 */
86
87 add r6, r6, #1 /* r6 ← r6 + 1 */
88 b .Lloop_k /* next iteration of loop k */
89 .Lend_loop_k: /* Here ends loop k */
90 vstr s0, [r7] /* Store s0 back to C[i][j] */
91 add r5, r5, #1 /* r5 ← r5 + 1 */
92 b .Lloop_j /* next iteration of loop j */
93 .Lend_loop_j: /* Here ends loop j */
94 add r4, r4, #1 /* r4 ← r4 + 1 */
95 b .Lloop_i /* next iteration of loop i */
96 .Lend_loop_i: /* Here ends loop i */
97
98 pop {r4, r5, r6, r7, r8, lr} /* Restore integer registers */
99 bx lr /* Leave function */
100
101
[Link] main
103main:
104 push {r4, r5, r6, lr} /* Keep integer registers */
105 vpush {d0-d1} /* Keep floating point registers */
106
107 /* Prepare call to naive_matmul_4x4 */
108 ldr r0, addr_mat_A /* r0 ← a */
109 ldr r1, addr_mat_B /* r1 ← b */
110 ldr r2, addr_mat_C /* r2 ← c */
111 bl naive_matmul_4x4
112
113 /* Now print the result matrix */
114 ldr r4, addr_mat_C /* r4 ← c */
115
116 vldr s0, [r4] /* s0 ← *r4. This is s0 ← c[0][0] */
117 vcvt.f64.f32 d1, s0 /* Convert it into a double-precision
118 d1 ← s0
119 */
120 vmov r2, r3, d1 /* {r2,r3} ← d1 */
121
122 mov r6, sp /* Remember the stack pointer, we need it to restore it back later */
123 /* r6 ← sp */
124
125 mov r5, #1 /* We will iterate from 1 to 15 (because the 0th item has already been handled */
126 add r4, r4, #60 /* Go to the last item of the matrix c, this is c[3][3] */
127 .Lloop:
128 vldr s0, [r4] /* s0 ← *r4. Load the current item */
129 vcvt.f64.f32 d1, s0 /* Convert it into a double-precision
130 d1 ← s0
131 */
132 sub sp, sp, #8 /* Make room in the stack for the double-precision */
133 vstr d1, [sp] /* Store the double precision in the top of the stack */
134 sub r4, r4, #4 /* Move to the previous element in the matrix */
135 add r5, r5, #1 /* One more item has been handled */
136 cmp r5, #16 /* if r5 != 16 go to next iteration of the loop */
137 bne .Lloop
138
139 ldr r0, addr_format_result /* r0 ← &format_result */
140 bl printf /* call printf */
141 mov sp, r6 /* Restore the stack after the call */
142
143 mov r0, #0
144 vpop {d0-d1}
145 pop {r4, r5, r6, lr}
146 bx lr
147
148addr_mat_A : .word mat_A
149addr_mat_B : .word mat_B
150addr_mat_C : .word mat_C
151addr_format_result : .word format_result
Enfoque vectorial
El algoritmo que estamos intentando implementar está bien, pero no es el más
optimizable. El problema radica en la forma en que el bucle kaccede a los elementos. El
acceso A[i][k]es elegible para una carga múltiple ya que A[i][k]y A[i][k+1]son elementos
contiguos en la memoria. De esta manera podríamos evitar por completo todo el bucle ky
realizar una carga de 4 elementos de A[i][0]a A[i][3]. El acceso B[k][j]no permite eso, ya que
los elementos B[k][j]y B[k+1][j]tienen una fila completa entre ellos. Este es un acceso
escalonado (el stride aquí es una fila completa de 4 elementos, esto es 16 bytes), VFPv2 no
permite una carga múltiple escalonada, por lo que tendremos que cargar uno por uno .. Una
vez que tengamos todos los elementos de el ciclo kcargado, podemos hacer una
multiplicación de vectores y una suma.
1naive_vectorial_matmul_4x4:
2 /* r0 address of A
3 r1 address of B
4 r2 address of C
5 */
6 push {r4, r5, r6, r7, r8, lr} /* Keep integer registers */
7 vpush {s16-s19} /* Floating point registers starting from s16 must be preserved */
8 vpush {s24-s27}
9 /* First zero 16 single floating point */
10 /* In IEEE 754, all bits cleared means 0 */
11 mov r4, r2
12 mov r5, #16
13 mov r6, #0
14 b .L1_loop_init_test
15 .L1_loop_init :
16 str r6, [r4], +#4 /* *r4 ← r6 then r4 ← r4 + 4 */
17 .L1_loop_init_test:
18 subs r5, r5, #1
19 bge .L1_loop_init
20
21 /* Set the LEN field of FPSCR to be 4 (value 3) */
22 mov r5, #0b011 /* r5 ← 3 */
23 mov r5, r5, LSL #16 /* r5 ← r5 << 16 */
24 fmrx r4, fpscr /* r4 ← fpscr */
25 orr r4, r4, r5 /* r4 ← r4 | r5 */
26 fmxr fpscr, r4 /* fpscr ← r4 */
27
28 /* We will use
29 r4 as i
30 r5 as j
31 r6 as k
32 */
33 mov r4, #0 /* r4 ← 0 */
34 .L1_loop_i: /* loop header of i */
35 cmp r4, #4 /* if r4 == 4 goto end of the loop i */
36 beq .L1_end_loop_i
37 mov r5, #0 /* r5 ← 0 */
38 .L1_loop_j: /* loop header of j */
39 cmp r5, #4 /* if r5 == 4 goto end of the loop j */
40 beq .L1_end_loop_j
41 /* Compute the address of C[i][j] and load it into s0 */
42 /* Address of C[i][j] is C + 4*(4 * i + j) */
43 mov r7, r5 /* r7 ← r5. This is r7 ← j */
44 adds r7, r7, r4, LSL #2 /* r7 ← r7 + (r4 << 2).
45 This is r7 ← j + i * 4.
46 We multiply i by the row size (4 elements) */
47 adds r7, r2, r7, LSL #2 /* r7 ← r2 + (r7 << 2).
48 This is r7 ← C + 4*(j + i * 4)
49 We multiply (j + i * 4) by the size of the element.
50 A single-precision floating point takes 4 bytes.
51 */
52 /* Compute the address of a[i][0] */
53 mov r8, r4, LSL #2
54 adds r8, r0, r8, LSL #2
55 vldmia r8, {s8-s11} /* Load {s8,s9,s10,s11} ← {a[i][0], a[i][1], a[i][2], a[i][3]} */
56
57 /* Compute the address of b[0][j] */
58 mov r8, r5 /* r8 ← r5. This is r8 ← j */
59 adds r8, r1, r8, LSL #2 /* r8 ← r1 + (r8 << 2). This is r8 ← b + 4*(j) */
60 vldr s16, [r8] /* s16 ← *r8. This is s16 ← b[0][j] */
61 vldr s17, [r8, #16] /* s17 ← *(r8 + 16). This is s17 ← b[1][j] */
62 vldr s18, [r8, #32] /* s18 ← *(r8 + 32). This is s17 ← b[2][j] */
63 vldr s19, [r8, #48] /* s19 ← *(r8 + 48). This is s17 ← b[3][j] */
64
65 vmul.f32 s24, s8, s16 /* {s24,s25,s26,s27} ← {s8,s9,s10,s11} * {s16,s17,s18,s19} */
66 vmov.f32 s0, s24 /* s0 ← s24 */
67 vadd.f32 s0, s0, s25 /* s0 ← s0 + s25 */
68 vadd.f32 s0, s0, s26 /* s0 ← s0 + s26 */
69 vadd.f32 s0, s0, s27 /* s0 ← s0 + s27 */
70
71 vstr s0, [r7] /* Store s0 back to C[i][j] */
72 add r5, r5, #1 /* r5 ← r5 + 1 */
73 b .L1_loop_j /* next iteration of loop j */
74 .L1_end_loop_j: /* Here ends loop j */
75 add r4, r4, #1 /* r4 ← r4 + 1 */
76 b .L1_loop_i /* next iteration of loop i */
77 .L1_end_loop_i: /* Here ends loop i */
78
79 /* Set the LEN field of FPSCR back to 1 (value 0) */
80 mov r5, #0b011 /* r5 ← 3 */
81 mvn r5, r5, LSL #16 /* r5 ← ~(r5 << 16) */
82 fmrx r4, fpscr /* r4 ← fpscr */
83 and r4, r4, r5 /* r4 ← r4 & r5 */
84 fmxr fpscr, r4 /* fpscr ← r4 */
85
86 vpop {s24-s27} /* Restore preserved floating registers */
87 vpop {s16-s19}
88 pop {r4, r5, r6, r7, r8, lr} /* Restore integer registers */
89 bx lr /* Leave function */
Con este enfoque podemos eliminar por completo el bucle k, ya que hacemos 4 operaciones
a la vez. Tenga en cuenta que tenemos que modificar fpscrpara que el campo lense
establezca en 4 (y restaurarlo de nuevo a 1 al salir de la función).
1naive_vectorial_matmul_2_4x4:
2 /* r0 address of A
3 r1 address of B
4 r2 address of C
5 */
6 push {r4, r5, r6, r7, r8, lr} /* Keep integer registers */
7 vpush {s16-s31} /* Floating point registers starting from s16 must be preserved */
8 /* First zero 16 single floating point */
9 /* In IEEE 754, all bits cleared means 0 */
10 mov r4, r2
11 mov r5, #16
12 mov r6, #0
13 b .L2_loop_init_test
14 .L2_loop_init :
15 str r6, [r4], +#4 /* *r4 ← r6 then r4 ← r4 + 4 */
16 .L2_loop_init_test:
17 subs r5, r5, #1
18 bge .L2_loop_init
19
20 /* Set the LEN field of FPSCR to be 4 (value 3) */
21 mov r5, #0b011 /* r5 ← 3 */
22 mov r5, r5, LSL #16 /* r5 ← r5 << 16 */
23 fmrx r4, fpscr /* r4 ← fpscr */
24 orr r4, r4, r5 /* r4 ← r4 | r5 */
25 fmxr fpscr, r4 /* fpscr ← r4 */
26
27 /* We will use
28 r4 as i
29 r5 as j
30 */
31 mov r4, #0 /* r4 ← 0 */
32 .L2_loop_i: /* loop header of i */
33 cmp r4, #4 /* if r4 == 4 goto end of the loop i */
34 beq .L2_end_loop_i
35 mov r5, #0 /* r5 ← 0 */
36 .L2_loop_j: /* loop header of j */
37 cmp r5, #4 /* if r5 == 4 goto end of the loop j */
38 beq .L2_end_loop_j
39 /* Compute the address of C[i][j] and load it into s0 */
40 /* Address of C[i][j] is C + 4*(4 * i + j) */
41 mov r7, r5 /* r7 ← r5. This is r7 ← j */
42 adds r7, r7, r4, LSL #2 /* r7 ← r7 + (r4 << 2).
43 This is r7 ← j + i * 4.
44 We multiply i by the row size (4 elements) */
45 adds r7, r2, r7, LSL #2 /* r7 ← r2 + (r7 << 2).
46 This is r7 ← C + 4*(j + i * 4)
47 We multiply (j + i * 4) by the size of the element.
48 A single-precision floating point takes 4 bytes.
49 */
50 /* Compute the address of a[i][0] */
51 mov r8, r4, LSL #2
52 adds r8, r0, r8, LSL #2
53 vldmia r8, {s8-s11} /* Load {s8,s9,s10,s11} ← {a[i][0], a[i][1], a[i][2], a[i][3]} */
54
55 /* Compute the address of b[0][j] */
56 mov r8, r5 /* r8 ← r5. This is r8 ← j */
57 adds r8, r1, r8, LSL #2 /* r8 ← r1 + (r8 << 2). This is r8 ← b + 4*(j) */
58 vldr s16, [r8] /* s16 ← *r8. This is s16 ← b[0][j] */
59 vldr s17, [r8, #16] /* s17 ← *(r8 + 16). This is s17 ← b[1][j] */
60 vldr s18, [r8, #32] /* s18 ← *(r8 + 32). This is s17 ← b[2][j] */
61 vldr s19, [r8, #48] /* s19 ← *(r8 + 48). This is s17 ← b[3][j] */
62
63 /* Compute the address of b[0][j+1] */
64 add r8, r5, #1 /* r8 ← r5 + 1. This is r8 ← j + 1*/
65 adds r8, r1, r8, LSL #2 /* r8 ← r1 + (r8 << 2). This is r8 ← b + 4*(j + 1) */
66 vldr s20, [r8] /* s20 ← *r8. This is s20 ← b[0][j + 1] */
67 vldr s21, [r8, #16] /* s21 ← *(r8 + 16). This is s21 ← b[1][j + 1] */
68 vldr s22, [r8, #32] /* s22 ← *(r8 + 32). This is s22 ← b[2][j + 1] */
69 vldr s23, [r8, #48] /* s23 ← *(r8 + 48). This is s23 ← b[3][j + 1] */
70
71 vmul.f32 s24, s8, s16 /* {s24,s25,s26,s27} ← {s8,s9,s10,s11} * {s16,s17,s18,s19} */
72 vmov.f32 s0, s24 /* s0 ← s24 */
73 vadd.f32 s0, s0, s25 /* s0 ← s0 + s25 */
74 vadd.f32 s0, s0, s26 /* s0 ← s0 + s26 */
75 vadd.f32 s0, s0, s27 /* s0 ← s0 + s27 */
76
77 vmul.f32 s28, s8, s20 /* {s28,s29,s30,s31} ← {s8,s9,s10,s11} * {s20,s21,s22,s23} */
78
79 vmov.f32 s1, s28 /* s1 ← s28 */
80 vadd.f32 s1, s1, s29 /* s1 ← s1 + s29 */
81 vadd.f32 s1, s1, s30 /* s1 ← s1 + s30 */
82 vadd.f32 s1, s1, s31 /* s1 ← s1 + s31 */
83
84 vstmia r7, {s0-s1} /* {C[i][j], C[i][j+1]} ← {s0, s1} */
85
86 add r5, r5, #2 /* r5 ← r5 + 2 */
87 b .L2_loop_j /* next iteration of loop j */
88 .L2_end_loop_j: /* Here ends loop j */
89 add r4, r4, #1 /* r4 ← r4 + 1 */
90 b .L2_loop_i /* next iteration of loop i */
91 .L2_end_loop_i: /* Here ends loop i */
92
93 /* Set the LEN field of FPSCR back to 1 (value 0) */
94 mov r5, #0b011 /* r5 ← 3 */
95 mvn r5, r5, LSL #16 /* r5 ← ~(r5 << 16) */
96 fmrx r4, fpscr /* r4 ← fpscr */
97 and r4, r4, r5 /* r4 ← r4 & r5 */
98 fmxr fpscr, r4 /* fpscr ← r4 */
99
100 vpop {s16-s31} /* Restore preserved floating registers */
101 pop {r4, r5, r6, r7, r8, lr} /* Restore integer registers */
102 bx lr /* Leave function */
Tenga en cuenta que debido a que ahora procesamos jy j + 1, r5( j) ahora se incrementa en 2
al final del ciclo. Esto generalmente se conoce como desenrollado de bucle y siempre es
legal hacerlo. Hacemos más de una iteración del ciclo original en el ciclo desenrollado. La
cantidad de iteraciones del ciclo original que hacemos en el ciclo desenrollado es el factor
de desenrollado . En este caso, dado que el número de iteraciones (4) divide perfectamente
el factor de desenrollado (2), no necesitamos un bucle adicional para las iteraciones
restantes (el bucle restante tiene una iteración menos que el valor del factor de
desenrollado).
1float A[N][N];
2float B[M][N];
3// Result
4float C[N][N];
5
6for (int i = 0; i < N; i++)
7 for (int j = 0; j < N; j++)
8 C[i][j] = 0;
9
10for (int k = 0; k < N; k++)
11 for (int i = 0; i < N; i++)
12 for (int j = 0; j < N; j++)
13 C[i][j] += A[i][k] * B[k][j];
Esto puede parecer poco útil, pero tenga en cuenta que, dado que ahora k está en el bucle
más externo, ahora es más fácil usar instrucciones vectoriales.
for (int k = 0; k < N; k++)
for (int i = 0; i < N; i++)
{
C[i][0] += A[i][k] * B[k][0];
C[i][1] += A[i][k] * B[k][1];
C[i][2] += A[i][k] * B[k][2];
C[i][3] += A[i][k] * B[k][3];
}
Si recuerdas el capítulo 13, las instrucciones VFPv2 tienen un modo mixto cuando
el Rsource2registro está en el banco 0. Este caso hace una combinación perfecta: podemos
cargar C[i][0..3]y B[k][0..3]con un múltiplo de carga y luego cargar A[i][k]en un registro del
banco 0. Entonces podemos haz multiplicar A[i][k]*B[k][0..3]y suma el resultado a C[i]
[0..3]. Como beneficio adicional, el número de instrucciones es mucho menor.
1better_vectorial_matmul_4x4:
2 /* r0 address of A
3 r1 address of B
4 r2 address of C
5 */
6 push {r4, r5, r6, r7, r8, lr} /* Keep integer registers */
7 vpush {s16-s19} /* Floating point registers starting from s16 must be preserved */
8 vpush {s24-s27}
9 /* First zero 16 single floating point */
10 /* In IEEE 754, all bits cleared means 0 */
11 mov r4, r2
12 mov r5, #16
13 mov r6, #0
14 b .L3_loop_init_test
15 .L3_loop_init :
16 str r6, [r4], +#4 /* *r4 ← r6 then r4 ← r4 + 4 */
17 .L3_loop_init_test:
18 subs r5, r5, #1
19 bge .L3_loop_init
20
21 /* Set the LEN field of FPSCR to be 4 (value 3) */
22 mov r5, #0b011 /* r5 ← 3 */
23 mov r5, r5, LSL #16 /* r5 ← r5 << 16 */
24 fmrx r4, fpscr /* r4 ← fpscr */
25 orr r4, r4, r5 /* r4 ← r4 | r5 */
26 fmxr fpscr, r4 /* fpscr ← r4 */
27
28 /* We will use
29 r4 as k
30 r5 as i
31 */
32 mov r4, #0 /* r4 ← 0 */
33 .L3_loop_k: /* loop header of k */
34 cmp r4, #4 /* if r4 == 4 goto end of the loop k */
35 beq .L3_end_loop_k
36 mov r5, #0 /* r5 ← 0 */
37 .L3_loop_i: /* loop header of i */
38 cmp r5, #4 /* if r5 == 4 goto end of the loop i */
39 beq .L3_end_loop_i
40 /* Compute the address of C[i][0] */
41 /* Address of C[i][0] is C + 4*(4 * i) */
42 add r7, r2, r5, LSL #4 /* r7 ← r2 + (r5 << 4). This is r7 ← c + 4*4*i */
43 vldmia r7, {s8-s11} /* Load {s8,s9,s10,s11} ← {c[i][0], c[i][1], c[i][2], c[i][3]} */
44 /* Compute the address of A[i][k] */
45 /* Address of A[i][k] is A + 4*(4*i + k) */
46 add r8, r4, r5, LSL #2 /* r8 ← r4 + r5 << 2. This is r8 ← k + 4*i */
47 add r8, r0, r8, LSL #2 /* r8 ← r0 + r8 << 2. This is r8 ← a + 4*(k + 4*i) */
48 vldr s0, [r8] /* Load s0 ← a[i][k] */
49
50 /* Compute the address of B[k][0] */
51 /* Address of B[k][0] is B + 4*(4*k) */
52 add r8, r1, r4, LSL #4 /* r8 ← r1 + r4 << 4. This is r8 ← b + 4*(4*k) */
53 vldmia r8, {s16-s19} /* Load {s16,s17,s18,s19} ← {b[k][0], b[k][1], b[k][2], b[k][3]} */
54
55 vmul.f32 s24, s16, s0 /* {s24,s25,s26,s27} ← {s16,s17,s18,s19} * {s0,s0,s0,s0} */
56 vadd.f32 s8, s8, s24 /* {s8,s9,s10,s11} ← {s8,s9,s10,s11} + {s24,s25,s26,s7} */
57
58 vstmia r7, {s8-s11} /* Store {c[i][0], c[i][1], c[i][2], c[i][3]} ← {s8,s9,s10,s11} */
59
60 add r5, r5, #1 /* r5 ← r5 + 1. This is i = i + 1 */
61 b .L3_loop_i /* next iteration of loop i */
62 .L3_end_loop_i: /* Here ends loop i */
63 add r4, r4, #1 /* r4 ← r4 + 1. This is k = k + 1 */
64 b .L3_loop_k /* next iteration of loop k */
65 .L3_end_loop_k: /* Here ends loop k */
66
67 /* Set the LEN field of FPSCR back to 1 (value 0) */
68 mov r5, #0b011 /* r5 ← 3 */
69 mvn r5, r5, LSL #16 /* r5 ← ~(r5 << 16) */
70 fmrx r4, fpscr /* r4 ← fpscr */
71 and r4, r4, r5 /* r4 ← r4 & r5 */
72 fmxr fpscr, r4 /* fpscr ← r4 */
73
74 vpop {s24-s27} /* Restore preserved floating registers */
75 vpop {s16-s19}
76 pop {r4, r5, r6, r7, r8, lr} /* Restore integer registers */
77 bx lr /* Leave function */
1best_vectorial_matmul_4x4:
2 /* r0 address of A
3 r1 address of B
4 r2 address of C
5 */
6 push {r4, r5, r6, r7, r8, lr} /* Keep integer registers */
7 vpush {s16-s19} /* Floating point registers starting from s16 must be preserved */
8
9 /* First zero 16 single floating point */
10 /* In IEEE 754, all bits cleared means 0 */
11 mov r4, r2
12 mov r5, #16
13 mov r6, #0
14 b .L4_loop_init_test
15 .L4_loop_init :
16 str r6, [r4], +#4 /* *r4 ← r6 then r4 ← r4 + 4 */
17 .L4_loop_init_test:
18 subs r5, r5, #1
19 bge .L4_loop_init
20
21 /* Set the LEN field of FPSCR to be 4 (value 3) */
22 mov r5, #0b011 /* r5 ← 3 */
23 mov r5, r5, LSL #16 /* r5 ← r5 << 16 */
24 fmrx r4, fpscr /* r4 ← fpscr */
25 orr r4, r4, r5 /* r4 ← r4 | r5 */
26 fmxr fpscr, r4 /* fpscr ← r4 */
27
28 /* We will use
29 r4 as k
30 r5 as i
31 */
32 mov r4, #0 /* r4 ← 0 */
33 .L4_loop_k: /* loop header of k */
34 cmp r4, #4 /* if r4 == 4 goto end of the loop k */
35 beq .L4_end_loop_k
36 mov r5, #0 /* r5 ← 0 */
37 .L4_loop_i: /* loop header of i */
38 cmp r5, #4 /* if r5 == 4 goto end of the loop i */
39 beq .L4_end_loop_i
40 /* Compute the address of C[i][0] */
41 /* Address of C[i][0] is C + 4*(4 * i) */
42 add r7, r2, r5, LSL #4 /* r7 ← r2 + (r5 << 4). This is r7 ← c + 4*4*i */
43 vldmia r7, {s8-s15} /* Load {s8,s9,s10,s11,s12,s13,s14,s15}
44 ← {c[i][0], c[i][1], c[i][2], c[i][3]
45 c[i+1][0], c[i+1][1], c[i+1][2], c[i+1][3]} */
46 /* Compute the address of A[i][k] */
47 /* Address of A[i][k] is A + 4*(4*i + k) */
48 add r8, r4, r5, LSL #2 /* r8 ← r4 + r5 << 2. This is r8 ← k + 4*i */
49 add r8, r0, r8, LSL #2 /* r8 ← r0 + r8 << 2. This is r8 ← a + 4*(k + 4*i) */
50 vldr s0, [r8] /* Load s0 ← a[i][k] */
51 vldr s1, [r8, #16] /* Load s1 ← a[i+1][k] */
52
53 /* Compute the address of B[k][0] */
54 /* Address of B[k][0] is B + 4*(4*k) */
55 add r8, r1, r4, LSL #4 /* r8 ← r1 + r4 << 4. This is r8 ← b + 4*(4*k) */
56 vldmia r8, {s16-s19} /* Load {s16,s17,s18,s19} ← {b[k][0], b[k][1], b[k][2], b[k][3]} */
57
58 vmla.f32 s8, s16, s0 /* {s8,s9,s10,s11} ← {s8,s9,s10,s11} + ({s16,s17,s18,s19} * {s0,s0,s0,s0}) */
59 vmla.f32 s12, s16, s1 /* {s12,s13,s14,s15} ← {s12,s13,s14,s15} + ({s16,s17,s18,s19} * {s1,s1,s1,s1}) */
60
61 vstmia r7, {s8-s15} /* Store {c[i][0], c[i][1], c[i][2], c[i][3],
62 c[i+1][0], c[i+1][1], c[i+1][2]}, c[i+1][3] }
63 ← {s8,s9,s10,s11,s12,s13,s14,s15} */
64
65 add r5, r5, #2 /* r5 ← r5 + 2. This is i = i + 2 */
66 b .L4_loop_i /* next iteration of loop i */
67 .L4_end_loop_i: /* Here ends loop i */
68 add r4, r4, #1 /* r4 ← r4 + 1. This is k = k + 1 */
69 b .L4_loop_k /* next iteration of loop k */
70 .L4_end_loop_k: /* Here ends loop k */
71
72 /* Set the LEN field of FPSCR back to 1 (value 0) */
73 mov r5, #0b011 /* r5 ← 3 */
74 mvn r5, r5, LSL #16 /* r5 ← ~(r5 << 16) */
75 fmrx r4, fpscr /* r4 ← fpscr */
76 and r4, r4, r5 /* r4 ← r4 & r5 */
77 fmxr fpscr, r4 /* fpscr ← r4 */
78
79 vpop {s16-s19} /* Restore preserved floating registers */
80 pop {r4, r5, r6, r7, r8, lr} /* Restore integer registers */
81 bx lr /* Leave function */
Comparación de versiones
Por curiosidad probé las versiones, para ver cuál era más rápida.
mov r0, #0
pop {r4, lr}
bx lr
Aquí están los resultados. El que nombramos el mejor se convirtió en realidad para merecer
ese nombre.
naive_matmul_4x4 6,41
naive_vectorial_matmul_4x4 3,51
naive_vectorial_matmul_2_4x4 2,87
better_vectorial_matmul_4x4 2,59
best_vectorial_matmul_4x4 1,51
La igualdad implica que hay dos soluciones 0 < R < |D|y 0 < |-R| < |D|. Por
ejemplo, N=7y D=3tiene dos soluciones (Q=2, R=1)y (Q=3, R=-2). Si bien ambas soluciones
pueden ser útiles, la primera es la preferida, ya que está más cerca de nuestra noción natural
del resto. Pero, ¿y si Des negativo? Por ejemplo, N=7y también D=-3tiene dos
soluciones (Q=-2, R=1)y (Q=-3, R=-2). Cuando se trata de números negativos, la elección del
resto no es intuitiva sino convencional. Se pueden utilizar muchas convenciones para elegir
una solución. Siempre podemos elegir la solución con el resto positivo (esto se
llama división euclidiana ), o el negativo, o la solución donde el signo del resto coincide
con el numerador (o denominador).
La mayoría de las computadoras realizan una división entera donde el resto tiene el mismo
signo que el numerador. Entonces, para N=7y D=3la solución calculada es (Q=2, R=1)y
para N=7y D=-3la solución calculada es (Q=-2, R=1). Asumiremos tal convención de división
de enteros en el resto (sin juego de palabras) de esta publicación.
1unsigned_naive_div:
2 /* r0 contains N */
3 /* r1 contains D */
4 mov r2, r1 /* r2 ← r0. We keep D in r2 */
5 mov r1, r0 /* r1 ← r0. We keep N in r1 */
6
7 mov r0, #0 /* r0 ← 0. Set Q = 0 initially */
8
9 b .Lloop_check
10 .Lloop:
11 add r0, r0, #1 /* r0 ← r0 + 1. Q = Q + 1 */
12 sub r1, r1, r2 /* r1 ← r1 - r2 */
13 .Lloop_check:
14 cmp r1, r2 /* compute r1 - r2 */
15 bhs .Lloop /* branch if r1 >= r2 (C=0 or Z=1) */
16
17 /* r0 already contains Q */
18 /* r1 already contains R */
19 bx lr
Este algoritmo, aunque correcto y fácil de entender, no es muy eficiente (piense en dividir
una N grande con una D pequeña). ¿Hay alguna forma de calcular la división en un período
de tiempo fijo? La respuesta es sí, simplemente adapte la forma de dividir a mano, pero a
números binarios. Calcularemos un resto temporal seleccionando bits, de izquierda a
derecha, del dividendo. Cuando el resto es mayor que el divisor, restaremos el divisor de
ese resto y estableceremos el bit apropiado en el cociente.
1unsigned_longdiv:
2 /* r0 contains N */
3 /* r1 contains D */
4 /* r2 contains Q */
5 /* r3 contains R */
6 push {r4, lr}
7 mov r2, #0 /* r2 ← 0 */
8 mov r3, #0 /* r3 ← 0 */
9
10 mov r4, #32 /* r4 ← 32 */
11 b .Lloop_check1
12 .Lloop1:
13 movs r0, r0, LSL #1 /* r0 ← r0 << 1 updating cpsr (sets C if 31st bit of r0 was 1) */
14 adc r3, r3, r3 /* r3 ← r3 + r3 + C. This is equivalent to r3 ← (r3 << 1) + C */
15
16 cmp r3, r1 /* compute r3 - r1 and update cpsr */
17 subhs r3, r3, r1 /* if r3 >= r1 (C=1) then r3 ← r3 - r1 */
18 adc r2, r2, r2 /* r2 ← r2 + r2 + C. This is equivalent to r2 ← (r2 << 1) + C */
19 .Lloop_check1:
20 subs r4, r4, #1 /* r4 ← r4 - 1 */
21 bpl .Lloop1 /* if r4 >= 0 (N=0) then branch to .Lloop1 */
22
23 pop {r4, lr}
24 bx lr
Este enfoque es un poco más eficiente ya que repite el ciclo un número fijo de veces
(siempre 32). Para cada bit de N a partir del más significativo (línea 13), lo empujamos a la
derecha del valor actual de R (línea 14). Hacemos esto agregando R a sí mismo, esto es 2 *
R que en realidad se está desplazando al bit R 1 derecho. Luego agregamos el acarreo, que
será 1 si el bit más significativo de N antes del cambio (línea 13) fue 1. Luego verificamos
si la R actual ya es mayor que D (línea 16) Si es así, restamos N de R , R ← R - N (línea
17) y luego presionamos un 1 a la derecha de Q (línea 18), nuevamente agregando Q a sí
mismo más el acarreo establecido por la comparación (si R> = N entonces no hay préstamo
por lo que C se convirtió en 1 en la cmplínea 16).
El código que se muestra está bien, pero se puede mejorar de varias maneras. Primero, no
es necesario verificar todos los bits de un número (aunque esto da como límite superior del
costo en el peor de los casos). En segundo lugar, deberíamos esforzarnos por reducir el
número de registros utilizados. Aquí estamos usando 5 registros, ¿hay alguna manera de
que podamos usar menos registros? Para ello, tendremos que utilizar un enfoque
ligeramente diferente.
Dados N y D, primero desplazaremos D tantos bits a la izquierda como sea posible, pero
siempre teniendo N> D. Entonces, por ejemplo, si dividimos N = 1010 (2 por D = 10 (2 ,
ajustaríamos D hasta que fuera D 0 = 1000 (2 (esto se está desplazando dos veces hacia la
izquierda). Ahora comenzamos un proceso similar al anterior: si N i ≥ D i , establecemos 1
en el bit más bajo de Q y luego calculamos un nuevo N i + 1 ← N i - D i y un nuevo D i + 1 ←
D i / 2. Si N i <D i entonces simplemente calculamos un nuevo D i + 1 ← D i/ 2. Nos
detenemos cuando la D i actual es menor que la D inicial (no D 0 ). Tenga en cuenta que
esta condición es lo que hace que dividir N = 1010 (2 entre D = 10 (2) sea diferente de dividir
N = 1010 (2 entre D = 1 (2, aunque el D 0 de ambos casos es el mismo.
1better_unsigned_division :
2 /* r0 contains N and Ni */
3 /* r1 contains D */
4 /* r2 contains Q */
5 /* r3 will contain Di */
6
7 mov r3, r1 /* r3 ← r1 */
8 cmp r3, r0, LSR #1 /* update cpsr with r3 - r0/2 */
9 .Lloop2:
10 movls r3, r3, LSL #1 /* if r3 <= 2*r0 (C=0 or Z=1) then r3 ← r3*2 */
11 cmp r3, r0, LSR #1 /* update cpsr with r3 - (r0/2) */
12 bls .Lloop2 /* branch to .Lloop2 if r3 <= 2*r0 (C=0 or Z=1) */
13
14 mov r2, #0 /* r2 ← 0 */
15
16 .Lloop3:
17 cmp r0, r3 /* update cpsr with r0 - r3 */
18 subhs r0, r0, r3 /* if r0 >= r3 (C=1) then r0 ← r0 - r3 */
19 adc r2, r2, r2 /* r2 ← r2 + r2 + C.
20 Note that if r0 >= r3 then C=1, C=0 otherwise */
21
22 mov r3, r3, LSR #1 /* r3 ← r3/2 */
23 cmp r3, r1 /* update cpsr with r3 - r1 */
24 bhs .Lloop3 /* if r3 >= r1 branch to .Lloop3 */
25
26 bx lr
Podemos evitar el primer bucle en el que cambiamos hasta superar contando los ceros
iniciales . Contando los ceros iniciales del dividendo y el divisor, podemos calcular
directamente cuántos bits necesitamos para desplazar el divisor.
1clz_unsigned_division:
2 clz r3, r0 /* r3 ← CLZ(r0) Count leading zeroes of N */
3 clz r2, r1 /* r2 ← CLZ(r1) Count leading zeroes of D */
4 sub r3, r2, r3 /* r3 ← r2 - r3.
5 This is the difference of zeroes
6 between D and N.
7 Note that N >= D implies CLZ(N) <= CLZ(D)*/
8 add r3, r3, #1 /* Loop below needs an extra iteration count */
9
10 mov r2, #0 /* r2 ← 0 */
11 b .Lloop_check4
12 .Lloop4:
13 cmp r0, r1, lsl r3 /* Compute r0 - (r1 << r3) and update cpsr */
14 adc r2, r2, r2 /* r2 ← r2 + r2 + C.
15 Note that if r0 >= (r1 << r3) then C=1, C=0 otherwise */
16 subcs r0, r0, r1, lsl r3 /* r0 ← r0 - (r1 << r3) if C = 1 (this is, only if r0 >= (r1 << r3) ) */
17 .Lloop_check4:
18 subs r3, r3, #1 /* r3 ← r3 - 1 */
19 bpl .Lloop4 /* if r3 >= 0 (N=0) then branch to .Lloop1 */
20
21 mov r0, r2
22 bx lr
División firmada
La división con signo se puede calcular con una división sin signo pero cuidando los
signos. Primero podemos calcular | N | / | D | (esto es, ignorando los signos de Ny D), esto
producirá un cociente Q + y un resto R + . Si los signos de N y D son diferentes, Q =
-Q + . Si N <0, entonces R = -R + , como dijimos al comienzo del post.
Potencias de dos
Una división sin signo por una potencia de dos 2 N es tan simple como hacer un
desplazamiento lógico a la derecha de N bits. Por el contrario, una división con signo entre
una potencia de dos 2 N es tan simple como hacer un desplazamiento aritmético a la derecha
de N bits. Podemos usar movy los modos de direccionamiento LSRy ASRpara esto. Este caso
es ideal porque es extremadamente rápido.
División por un entero constante
Cuando dividimos un número por una constante, podemos usar una multiplicación por
un número mágico para calcular la división. Todos los detalles y la teoría de esta técnica
son demasiado largos para escribirlos aquí, pero puedes encontrarlos en el capítulo 10
de Hacker's Delight . Sin embargo, podemos resumirlo en tres valores: una constante
mágica M, un desplazamiento S y una bandera adicional. El autor creó una calculadora de
números mágicos que calcula estos números.
No es obvio cómo usar correctamente estos números mágicos, así que elaboré un pequeño
script de Python que emite código para el caso firmado y no firmado. Imagina que quieres
dividir un número sin firmar entre 14. Preguntemos a nuestro guión.
$ ./[Link] 14 code_for_unsigned
u_divide_by_14:
/* r0 contains the argument to be divided by 14 */
ldr r1, .Lu_magic_number_14 /* r1 ← magic_number */
umull r1, r2, r1, r0 /* r1 ← Lower32Bits(r1*r0). r2 ← Upper32Bits(r1*r0) */
adds r2, r2, r0 /* r2 ← r2 + r0 updating cpsr */
mov r2, r2, ROR #0 /* r2 ← (carry_flag << 31) | (r2 >> 1) */
mov r0, r2, LSR #4 /* r0 ← r2 >> 4 */
bx lr /* leave function */
.align 4
.Lu_magic_number_14: .word 0x24924925
De igual forma podemos solicitar la versión firmada:
$ ./[Link] 14 code_for_signed
s_divide_by_14:
/* r0 contains the argument to be divided by 14 */
ldr r1, .Ls_magic_number_14 /* r1 ← magic_number */
smull r1, r2, r1, r0 /* r1 ← Lower32Bits(r1*r0). r2 ← Upper32Bits(r1*r0) */
add r2, r2, r0 /* r2 ← r2 + r0 */
mov r2, r2, ASR #3 /* r2 ← r2 >> 3 */
mov r1, r0, LSR #31 /* r1 ← r0 >> 31 */
add r0, r2, r1 /* r0 ← r2 + r1 */
bx lr /* leave function */
.align 4
.Ls_magic_number_14: .word 0x92492493
Como ejemplo, lo he usado para implementar un pequeño programa que solo divide la
entrada del usuario entre 14.
1/* -- divideby14.s */
2
[Link]
4
[Link] 4
6read_number: .word 0
7
[Link] 4
9message1 : .asciz "Enter an integer to divide it by 14: "
10
[Link] 4
12message2 : .asciz "Number %d (signed-)divided by 14 is %d\n"
13
[Link] 4
15scan_format : .asciz "%d"
16
[Link]
18
19/* This function has been generated using "[Link] 14 code_for_signed" */
20s_divide_by_14:
21 /* r0 contains the argument to be divided by 14 */
22 ldr r1, .Ls_magic_number_14 /* r1 ← magic_number */
23 smull r1, r2, r1, r0 /* r1 ← Lower32Bits(r1*r0). r2 ← Upper32Bits(r1*r0) */
24 add r2, r2, r0 /* r2 ← r2 + r0 */
25 mov r2, r2, ASR #3 /* r2 ← r2 >> 3 */
26 mov r1, r0, LSR #31 /* r1 ← r0 >> 31 */
27 add r0, r2, r1 /* r0 ← r2 + r1 */
28 bx lr /* leave function */
29 .align 4
30 .Ls_magic_number_14: .word 0x92492493
31
[Link] main
33
34main:
35 /* Call printf */
36 push {r4, lr}
37 ldr r0, addr_of_message1 /* r0 ← &message */
38 bl printf
39
40 /* Call scanf */
41 ldr r0, addr_of_scan_format /* r0 ← &scan_format */
42 ldr r1, addr_of_read_number /* r1 ← &read_number */
43 bl scanf
44
45 ldr r0, addr_of_read_number /* r1 ← &read_number */
46 ldr r0, [r0] /* r1 ← *r1 */
47
48 bl s_divide_by_14
49 mov r2, r0
50
51 ldr r1, addr_of_read_number /* r1 ← &read_number */
52 ldr r1, [r1] /* r1 ← *r1 */
53
54 ldr r0, addr_of_message2 /* r0 ← &message2 */
55 bl printf /* Call printf, r1 and r2 already
56 contain the desired values */
57 pop {r4, lr}
58 mov r0, #0
59 bx lr
60
61addr_of_message1: .word message1
62addr_of_scan_format: .word scan_format
63addr_of_message2: .word message2
64addr_of_read_number: .word read_number
Usando VFPv2
No recomendaría usar esta técnica. Lo presento aquí en aras de la integridad. Simplemente
convertimos nuestros números enteros a números de punto flotante, los dividimos como
números de punto flotante y convertimos el resultado de nuevo a un número entero.
1vfpv2_division:
2 /* r0 contains N */
3 /* r1 contains D */
4 vmov s0, r0 /* s0 ← r0 (bit copy) */
5 vmov s1, r1 /* s1 ← r1 (bit copy) */
6 vcvt.f32.s32 s0, s0 /* s0 ← (float)s0 */
7 vcvt.f32.s32 s1, s1 /* s1 ← (float)s1 */
8 vdiv.f32 s0, s0, s1 /* s0 ← s0 / s1 */
9 vcvt.s32.f32 s0, s0 /* s0 ← (int)s0 */
10 vmov r0, s0 /* r0 ← s0 (bit copy). Now r0 is Q */
11 bx lr
Comparación de versiones
Después de un comentario a continuación, pensé que sería interesante comparar el
algoritmo de división general. El punto de referencia que utilicé es el siguiente:
.set MAX, 16384
main:
push {r4, r5, r6, lr}
mov r4, #1 /* r4 ← 1 */
b .Lcheck_loop_i /* branch to .Lcheck_loop_i */
.Lloop_i:
mov r5, r4 /* r5 ← r4 */
b .Lcheck_loop_j /* branch to .Lcheck_loop_j */
.Lloop_j:
mov r0, #0
unsigned_longdiv 45,43
vfpv2_division 9,70
clz_unsigned_longdiv 8,48
__aeabi_uidiv 7,37
better_unsigned_longdiv 6,67
Como puede ver, el desempeño de nuestra división larga sin firmar es pésimo. La razón es
que siempre verifica todos los bits. La versión libgcc es como nuestra versión clz pero el
bucle se ha desenrollado por completo y hay una rama calculada, similar al dispositivo de
Duff . Desafortunadamente, no tengo una explicación convincente de por qué
se better_unsigned_longdivejecuta más rápido que las otras versiones, porque el código, a
priori , me parece peor.
Vimos en los capítulos 6 y 12 varias estructuras de control pero dejamos fuera una habitual:
el interruptor también conocido como select / case . En este capítulo veremos cómo
podemos implementarlo en ensamblador ARM.
Tenga en cuenta que, una vez que el flujo salta a una declaración, la ejecución continúa
desde ese punto a menos breakque se encuentre una declaración. La construcción de
la breakdeclaración switch. La mayoría de las veces, el programador agrega un breakpara
finalizar cada caso. De lo contrario , ocurren casos fallidos. En el ejemplo anterior, si
se Eevalúa ay V1no hay interrupción S1, el programa continuará ejecutándose S2y,
a Sdefaultmenos que el programa encuentre una breakdeclaración dentro de S2o Sdefault. La
caída puede parecer un poco extraña y confusa, pero hay algunos casos en los que es útil.
Dicho esto, C es un ejemplo particularmente malo para mostrar esta estructura. La razón es
que la definición de lenguaje exacta de a switchen C es la siguiente.
switch (E)
S;
Spuede ser cualquier cosa, pero el flujo siempre saltará a un caseo un defaultinterior S, por lo
que si Sno contiene ninguna de estas declaraciones, no pasa nada.
switch (E)
printf("This will never be printed\n");
Entonces, para switchque sea útil,necesitaremos al menos una declaración caseo default. Si se
necesita más de uno, entonces podemos usar una declaración compuesta (una lista de
declaraciones incluidas al lado {y }como se muestra en el primer ejemplo anterior.
Implementación de interruptor
Probablemente ya se habrá dado cuenta de que un interruptor que no implica fallos en
ninguno de sus casos es equivalente a una secuencia de bloques if-else. Lo siguiente switch,
switch (x)
{
case 5: code_for_case5; break;
case 10: code_for_case10; break;
default: code_for_default; break;
// break would not be required here as this is the last case
}
se puede implementar como
if (x == 5)
code_for_case5;
else if (x == 10)
code_for_case10;
else /* default */
code_for_default;
code_after;
A diferencia de la instrucción if-else habitual, no es necesario que haya una rama que vaya
después de la instrucción if una vez que se haya ejecutado la rama if. Esto es, en el ejemplo
anterior, es opcional tener una rama después de la code_for_case5que va a code_after. Si se
omite dicha rama, entonces code_for_case10ocurre una caída de forma natural. Entonces,
la breakdeclaración dentro de a switches simplemente esa rama incondicional.
/* Here we evaluate x and keep it in r0 */
case_5: /* case 5 */
cmp r0, #5 /* Compute r0 - 5 and update cpsr */
bne case_10 /* if r0 != 5 branch to case_10 */
code_for_case5
b after_switch /* break */
case_10: /* case 10 */
cmp r0, #10 /* Compute r0 - 10 and update cpsr */
bne case_default /* If r0 != 10 branch to case_default */
code_for_case10
b after_switch /* break */
case_default:
code_for_default
/* Note that if default is not the last case
we need a branch to after_switch here */
after_switch:
Podemos poner todas las comprobaciones al principio, siempre que conservemos el orden
de los casos (por lo que el fallo funciona si breakse omite).
/* Here we evaluate x and keep it in r0 */
cmp r0, #5 /* Compute r0 - 5 and update cpsr */
beq case_5 /* if r0 == 5 branch to case_5 */
cmp r0, #10 /* Compute r0 - 10 and update cpsr */
beq case_10 /* if r0 == 10 branch to case_10 */
b case_default /* branch to default case
Note that there is no default case
we would branch to after_switch */
case_5: /* case 5 */
code_for_case5
b after_switch /* break */
case_10: /* case 10 */
code_for_case10
b after_switch /* break */
case_default:
code_for_default
/* Note that if default is not the last case
we need a branch to after_switch here */
after_switch:
Este enfoque es sensato si el número de casos es bajo. Aquí "bajo" no está muy bien
definido, digamos 10 o menos. ¿Y si tenemos muchos casos? Una secuencia de
comprobaciones if-else hará tantas comparaciones como casos. Si los valores de los N
casos se distribuyen uniformemente durante la ejecución del programa, esto significa que
en promedio tendremos que hacer N / 2 verificaciones. Si los valores no se distribuyen
uniformemente, entonces es obvio que debemos verificar los valores comunes primero y los
raros al final (lamentablemente, la mayoría de las veces no tenemos idea de su frecuencia).
Hay varias formas de reducir el costo de verificar los casos: tablas y búsqueda binaria.
Tablas de salto
Imagina que tenemos uno switchcomo este
switch (x)
{
case 1: do_something_1;
case 2: do_something_2;
...
case 100: do_something_100;
}
Si lo implementamos de la manera que se muestra arriba, haremos en promedio (para un
conjunto de valores distribuidos uniformemente x) 50 comparaciones. Podemos mejorar
esto si simplemente usamos el valor cpara indexar una tabla de direcciones a las
instrucciones de las instrucciones del caso.
Como puede ver en la línea 43 definimos una tabla de salto, cuyos elementos son las
direcciones de las etiquetas de cada caso (en orden). En las líneas 14 a 16 cargamos el valor
apropiado de esa tabla después de estar seguros de que el valor de argc está entre 1 y 3,
comprobado en las líneas 9 a 12. Finalmente, cargamos la dirección a pc. Esto
efectivamente hará una ramificación al caso adecuado.
Si ejecuta el programa verá diferentes códigos de salida devueltos (recuerde que ellos
vuelven a sintonizarse a través r0de main). El programa solo cuenta los argumentos, si en
lugar de "a b" usa "uno dos", también devolverá 3. Más de dos argumentos y devolverá 42.
$ ./jumptable ; echo $?
1
$ ./jumptable a ; echo $?
2
$ ./jumptable a b ; echo $?
3
$ ./jumptable a b c ; echo $?
42
Para usar la tabla de salto de forma segura, debemos asegurarnos de que el valor del caso se
encuentre dentro de los límites de la tabla. Si m es el valor de caso mínimo y M es el valor
de caso máximo, nuestra tabla tendrá M - m + 1 entradas. En el ejemplo anterior m = 1 y M
= 3, tenemos 3 entradas en la tabla. Tenemos que asegurarnos de que el valor utilizado para
indexar sea m ≤ x ≤ M, de lo contrario estaríamos accediendo a ubicaciones de memoria
incorrectas. Recuerde también que para indexar correctamente la tabla de salto tendremos
que restar m al valor del caso.
Las tablas de salto son geniales, una vez que hemos verificado que el valor del caso está en
el rango adecuado (estas son dos comparaciones), no tenemos que comparar nada
más. Entonces, básicamente, el costo de las comparaciones en este enfoque es constante (es
decir, no aumenta si aumenta el número de casos).
Hay dos grandes desventajas de este enfoque que nos impiden usarlo siempre. El primero
ocurre cuando la diferencia entre M y m es grande, nuestra tabla de salto será grande. Esto
aumenta el tamaño del código. Básicamente, hemos cambiado el tiempo por el
espacio. Ahora nuestro tamaño de código agregará 4 bytes por caso manejado en una tabla
de salto. Una tabla de 256 entradas ocupará hasta 1 Kbyte (1024 bytes) de memoria en
nuestro programa ejecutable. Para ser justos, esta es la cantidad de espacio que ocupan 256
instrucciones. Entonces, si el tamaño del código es una preocupación para usted (y
generalmente lo es en el mundo integrado), este enfoque puede no ser adecuado. La
segunda gran desventaja ocurre cuando hay "huecos" en los casos. Imagine que nuestros
casos son solo 1, 3 y 100. La tabla tendrá 100 elementos, pero solo 1, 3 y 100 tendrán
entradas útiles: todas las entradas restantes tendrán la dirección del caso predeterminado (o
la dirección después del cambio si se omite el caso predeterminado). En este caso, no solo
estamos tomando 400 bytes, estamos desperdiciando 388 bytes (¡el 97% de las entradas
serían inútiles!). Entonces, si el número de casos es bajo y los valores están dispersos en un
rango grande, las tablas de salto no son una buena opción.
En nuestro ejemplo de la tabla de salto, cada caso requiere solo dos instrucciones. Entonces
podemos obtener la dirección del primer caso y usarla como dirección base para calcular la
rama.
1/* calcjump.s */
[Link]
3
[Link]
5
[Link] main
7
8main:
9 cmp r0, #1 /* r0 - 1 and update cpsr */
10 blt case_default /* branch to case_default if r0 < 1 */
11 cmp r0, #3 /* r0 - 3 and update cpsr */
12 bgt case_default /* branch to case_default if r0 > 3 */
13
14 sub r0, r0, #1 /* r0 ← r0 - 1. Required to index the table */
15 ldr r1, addr_of_case_1 /* r1 ← &case_1 */
16 add r1, r1, r0, LSL #3 /* r1 ← r1 + r0 * 8
17 Each instruction is 4 bytes
18 Each case takes 2 instructions
19 Thus, each case is 8 bytes (4 * 2)
20 */
21
22 mov pc, r1 /* pc ← r1
23 This will cause a branch to the
24 computed address */
25
26 case_1:
27 mov r0, #1 /* r0 ← 1 */
28 b after_switch /* break */
29
30 case_2:
31 mov r0, #2 /* r0 ← 2 */
32 b after_switch /* break */
33
34 case_3:
35 mov r0, #3 /* r0 ← 3 */
36 b after_switch /* break */
37
38 case_default:
39 mov r0, #42 /* r0 ← 42 */
40 b after_switch /* break (unnecessary) */
41
42 after_switch:
43
44 bx lr /* Return from main */
45
[Link] 4
47addr_of_case_1: .word case_1
Búsqueda binaria
Considere nuevamente nuestro ejemplo con 100 casos. Una serie de if-else requerirá en
promedio 50 comparaciones. ¿Podemos reducir el número de comparaciones? Bueno, la
respuesta es sí. Realice una búsqueda binaria del caso.
Una búsqueda binaria descartará la mitad del conjunto de casos cada vez. Esto nos
permitirá reducir drásticamente la cantidad de comparaciones. El siguiente ejemplo
implementa el mismo código en la tabla de salto pero con los casos 1 a 10.
1/* binsearch.s */
[Link]
3
[Link]
5
[Link] main
7
8main:
9
10 cmp r0, #1 /* r0 - 1 and update cpsr */
11 blt case_default /* if r0 < 1 then branch to case_default */
12 cmp r0, #10 /* r0 - 10 and update cpsr */
13 bgt case_default /* if r0 > 10 then branch to case default */
14
15 case_1_to_10:
16 cmp r0, #5 /* r0 - 5 and update cpsr */
17 beq case_5 /* if r0 == 5 branch to case_5 */
18 blt case_1_to_4 /* if r0 < 5 branch to case_1_to_4 */
19 bgt case_6_to_10 /* if r0 > 5 branch to case_6_to_4 */
20
21 case_1_to_4:
22 cmp r0, #2 /* r0 - 2 and update cpsr */
23 beq case_2 /* if r0 == 2 branch to case_2 */
24 blt case_1 /* if r0 < 2 branch to case_1
25 (case_1_to_1 does not make sense) */
26 bgt case_3_to_4 /* if r0 > 2 branch to case_3_to_4 */
27
28 case_3_to_4:
29 cmp r0, #3 /* r0 - 3 and update cpsr */
30 beq case_3 /* if r0 == 3 branch to case_3 */
31 b case_4 /* otherwise it must be r0 == 4,
32 branch to case_4 */
33
34 case_6_to_10:
35 cmp r0, #8 /* r0 - 8 and update cpsr */
36 beq case_8 /* if r0 == 8 branch to case_8 */
37 blt case_6_to_7 /* if r0 < 8 then branch to case_6_to_7 */
38 bgt case_9_to_10 /* if r0 > 8 then branch to case_9_to_10 */
39
40 case_6_to_7:
41 cmp r0, #6 /* r0 - 6 and update cpsr */
42 beq case_6 /* if r0 == 6 branch to case_6 */
43 b case_7 /* otherwise it must be r0 == 7,
44 branch to case 7 */
45
46 case_9_to_10:
47 cmp r0, #9 /* r0 - 9 and update cpsr */
48 beq case_9 /* if r0 == 9 branch to case_9 */
49 b case_10 /* otherwise it must be r0 == 10,
50 branch to case 10 */
51
52 case_1:
53 mov r0, #1
54 b after_switch
55 case_2:
56 mov r0, #2
57 b after_switch
58 .
59 . /* Cases from 3 to 9 omitted */
60 .
61 case_10:
62 mov r0, #10
63 b after_switch
64
65 case_default:
66 mov r0, #42 /* r0 ← 42 */
67 b after_switch /* break (unnecessary) */
68
69 after_switch:
70
71 bx lr /* Return from main */
Esta estrategia es capaz de determinar el valor del caso en solo 3 comparaciones (si
ignoramos las dos comparaciones obligatorias para la verificación de rango). Lo que
hacemos es verificar y comparar el valor del caso con el del medio en el rango actual. De
esta forma podemos descartar la mitad de los conjuntos en cada paso de comparación.
Esta estrategia también funciona bien para conjuntos de casos dispersos como [1, 2, 3, 24,
25, 26, 97, 98, 99, 300]. En este caso las comparaciones serían
case_1_to_300:
cmp r0, #25
beq case_25
blt case_1_to_24
bgt case_26_to_300
case_1_to_24:
cmp r0, #2
beq case_2
blt case_1
bgt case_3_to_24
case_3_to_24:
cmp r0, #3
beq case_3
b case_24
case_26_to_300:
cmp r0, #98
beq case_98
blt case_26_to_97
bgt case_99_to_300
case_26_to_97:
cmp r0, #26
beq case_26
b case_97
case_99_to_300:
cmp r0, #99
beq case_99
b case_300
que son 3 comparaciones como máximo también.
Retomemos el problema de la hinchazón del código que surgió con las tablas de salto. Si
marca, cada comparación requiere 3 o 4 instrucciones, esto es aproximadamente de 12 a 16
bytes por comparación. Si tenemos un conjunto de casos de 256 elementos, el código
generado requerirá 128 bloques de comparación en total. Si bien el número de
comparaciones realizadas en tiempo de ejecución, 8 en el peor de los casos, todavía
necesitamos 128 case_x_to_ybloques de comparación para realizar la búsqueda binaria. Si
asumimos de manera pesimista que todos los bloques de comparación toman 4
instrucciones, esto será 4 * 128 * 4 = 2048 bytes en instrucciones. Compare eso con una
tabla de salto de 256 posiciones, cada posición ocupa 4 bytes: 256 * 4 = 1024
bytes. Entonces, la búsqueda binaria no es tan competitiva en términos de tamaño de
código.
La búsqueda binaria, por lo tanto, es útil para grandes conjuntos dispersos. Recuerde que
las cadenas if-else no son eficientes para grandes conjuntos de casos y las tablas de salto
desperdician espacio si el rango de casos carece de muchos casos.
Enfoque híbrido
¿Es posible combinar las dos estrategias? La respuesta es sí. Usaremos dos tablas: una tabla
de valores de casos (ordenada, generalmente en orden ascendente) y direcciones para cada
caso en otra tabla, en el mismo orden que la tabla de valores de casos.
Haremos una búsqueda binaria dentro del conjunto de valores del caso. Cuando se
encuentre el valor, usaremos el índice de la coincidencia para calcular un salto. Para el
siguiente ejemplo usaremos el conjunto de casos [1, 2, 3, 24, 25, 26, 97, 98, 99, 300].
1/* hybrid.s */
[Link]
3
[Link]
5
[Link] main
7
8main:
9 push {r4, r5, r6, lr}
10
11 cmp r0, #1 /* r0 - 1 and update cpsr */
12 blt case_default /* if r0 < 1 then branch to case_default */
13 cmp r0, #300 /* r0 - 300 and update cpsr */
14 bgt case_default /* if r0 > 300 then branch to case default */
15
16 /* prepare the binary search.
17 r1 will hold the lower index
18 r2 will hold the upper index
19 r3 the base address of the case_value_table
20 */
21 mov r1, #0
22 mov r2, #9
23 ldr r3, addr_case_value_table /* r3 ← &case_value_table */
24
25 b check_binary_search
26 binary_search:
27 add r4, r1, r2 /* r4 ← r1 + r2 */
28 mov r4, r4, ASR #1 /* r4 ← r4 / 2 */
29 ldr r5, [r3, +r4, LSL #2] /* r5 ← *(r3 + r4 * 4).
30 This is r5 ← case_value_table[r4] */
31 cmp r0, r5 /* r0 - r5 and update cpsr */
32 sublt r2, r4, #1 /* if r0 < r5 then r2 ← r4 - 1 */
33 addgt r1, r4, #1 /* if r0 > r5 then r1 ← r4 + 1 */
34 bne check_binary_search /* if r0 != r5 branch to binary_search */
35
36 /* if we reach here it means that r0 == r5 */
37 ldr r5, addr_case_addresses_table /* r5 ← &addr_case_value_table */
38 ldr r5, [r5, +r4, LSL #2] /* r5 ← *(r5 + r4*4)
39 This is r5 ← case_addresses_table[r4] */
40 mov pc, r5 /* branch to the proper case */
41
42 check_binary_search:
43 cmp r1, r2 /* r1 - r2 and update cpsr */
44 ble binary_search /* if r1 <= r2 branch to binary_search */
45
46 /* if we reach here it means the case value
47 was not found. branch to default case */
48 b case_default
49
50 case_1:
51 mov r0, #1
52 b after_switch
53 case_2:
54 mov r0, #2
55 b after_switch
56 case_3:
57 mov r0, #3
58 b after_switch
59 case_24:
60 mov r0, #24
61 b after_switch
62 case_25:
63 mov r0, #95
64 b after_switch
65 case_26:
66 mov r0, #96
67 b after_switch
68 case_97:
69 mov r0, #97
70 b after_switch
71 case_98:
72 mov r0, #98
73 b after_switch
74 case_99:
75 mov r0, #99
76 b after_switch
77 case_300:
78 mov r0, #300 /* The error code will be 44 */
79 b after_switch
80
81 case_default:
82 mov r0, #42 /* r0 ← 42 */
83 b after_switch /* break (unnecessary) */
84
85 after_switch:
86
87 pop {r4,r5,r6,lr}
88 bx lr /* Return from main */
89
90case_value_table: .word 1, 2, 3, 24, 25, 26, 97, 98, 99, 300
91addr_case_value_table: .word case_value_table
92
93case_addresses_table:
94 .word case_1
95 .word case_2
96 .word case_3
97 .word case_24
98 .word case_25
99 .word case_26
100 .word case_97
101 .word case_98
102 .word case_99
103 .word case_300
104addr_case_addresses_table: .word case_addresses_table
En el capítulo 10 vimos los conceptos básicos para llamar a una función. En este capítulo
cubriremos más temas relacionados con las funciones.
Hay varias formas de abordar este problema, pero la mayoría de ellas implican
sugerencias. Los punteros son temidos por muchas personas, que no los comprenden
completamente, pero son una parte crucial en la forma en que funcionan las
computadoras. Dicho esto, la mayoría de los problemas con los punteros en realidad están
relacionados con la memoria dinámica más que con los punteros en sí. No consideraremos
aquí la memoria dinámica.
Esta definición puede resultar confusa, pero ya hemos estado usando punteros en capítulos
anteriores. Es solo que no los nombramos de esta manera. Por lo general, hablamos
de direcciones y / o etiquetas en el ensamblador. Considere este programa muy simple:
/* first_pointer.s */
.data
.align 4
number_1 : .word 3
.text
.globl main
main:
ldr r0, pointer_to_number /* r0 ← &number */
ldr r0, [r0] /* r0 ← *r0. So r0 ← number_1 */
bx lr
.align 4
number_1 : .word 3
number_2 : .word 4
.text
.globl main
main:
ldr r1, address_of_number_2 /* r1 ← &number_2 */
str r1, pointer_to_number /* pointer_to_number ← r1, this is pointer_to_number ← &number_2 */
bx lr
De este último ejemplo deberían quedar claras varias cosas. Tenemos punteros estáticos
a number_1, number_2y pointer_to_number(respectivamente
llamados addr_of_number_1, addr_of_number_2y addr_of_pointer_to_number). ¡Tenga en cuenta que
en addr_of_pointer_to_numberrealidad es un puntero a un puntero! ¿Por qué estos punteros
están definidos estáticamente? Bueno, podemos nombrar ubicaciones de memoria (es decir,
direcciones) usando etiquetas (de esta manera no tenemos que saber realmente la dirección
exacta y al mismo tiempo podemos usar un nombre descriptivo). Estas ubicaciones de
memoria, nombradas mediante etiquetas, nunca cambiarán durante la ejecución del
programa, por lo que de alguna manera están predefinidas antes de que se inicie el
programa. Esta es la razón por la que las direcciones
de number_1, number_2y addr_of_pointer_to_numberse definen y almacenan estáticamente en una
parte del programa que no puede cambiar ([Link] no se puede modificar la sección cuando
se ejecuta el programa).
Hay varios casos en los que surge esta situación. En un lenguaje como C, todos los
parámetros se pasan por valor. Esto significa que la función recibe una copia del valor. De
esta manera, la función puede modificar libremente este valor y la persona que llama no
verá ningún cambio en él. Esto puede parecer ineficiente, pero desde el punto de vista de la
productividad, una función que no causa ningún efecto secundario a sus insumos puede
considerarse más fácil de entender que una que sí lo hace.
struct A
{
// big structure
};
void my_code(void)
{
struct A a;
thing_t something;
a = ...;
something = compute_something(a)
// a is unchanged here!
}
Tenga en cuenta que en C, los tipos de matriz no se pasan por valor, pero esto es por
diseño: no hay valores de matriz en C aunque hay tipos de matriz (es posible que deba
repetirse esta última oración varias veces antes de comprenderla por completo;)
Pero, ¿y si nuestra función no modifica realmente los datos? O, ¿qué pasa si estamos
interesados en los cambios que hizo la función? O mejor aún, ¿qué pasa si el parámetro que
se está modificando es en realidad otra salida de la función?
Para llamar a esta función tenemos que poner una matriz en la pila. Considere el siguiente
programa.
[Link]
2
[Link] 4
4
5big_array :
[Link] 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
[Link] 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41
[Link] 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61
[Link] 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81
[Link] 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100
[Link] 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116
[Link] 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132
[Link] 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148
[Link] 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164
[Link] 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180
[Link] 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196
[Link] 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212
[Link] 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228
[Link] 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244
[Link] 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
21
[Link] 4
23
24message: .asciz "The sum of 0 to 255 is %d\n"
25
[Link]
[Link] main
28
29sum_array_value :
30 /* code shown above */
31
32main:
33 push {r4, r5, r6, r7, r8, lr}
34 /* we will not use r8 but we need to keep the function 8-byte aligned */
35
36 ldr r4, address_of_big_array
37
38 /* Prepare call */
39
40 mov r0, #256 /* Load in the first parameter the number of items
41 r0 ← 256
42 */
43
44 ldr r1, [r4] /* load in the second parameter the first item of the array */
45 ldr r2, [r4, #4] /* load in the third parameter the second item of the array */
46 ldr r3, [r4, #8] /* load in the fourth parameter the third item of the array */
47
48 /* before pushing anything in the stack keep its position */
49 mov r7, sp
50
51 /* We cannot use more registers, now we have to push them onto the stack
52 (in reverse order) */
53 mov r5, #255 /* r5 ← 255
54 This is the last item position
55 (note that the first would be in position 0) */
56
57 b .Lcheck_pass_parameter_loop
58 .Lpass_parameter_loop:
59
60 ldr r6, [r4, r5, LSL #2] /* r6 ← *(r4 + r5 * 4).
61 loads the item in position r5 into r6. Note that
62 we have to multiply by 4 because this is the size
63 of each item in the array */
64 push {r6} /* push the loaded value to the stack */
65 sub r5, r5, #1 /* we are done with the current item,
66 go to the previous index of the array */
67 .Lcheck_pass_parameter_loop:
68 cmp r5, #2 /* compute r5 - #2 and update cpsr */
69 bne .Lpass_parameter_loop /* if r5 != #2 branch to pass_parameter_loop */
70
71 /* We are done, we have passed all the values of the array,
72 now call the function */
73 bl sum_array_value
74
75 /* restore the stack position */
76 mov sp, r7
77
78 /* prepare the call to printf */
79 mov r1, r0 /* second parameter, the sum itself */
80 ldr r0, address_of_message /* first parameter, the message */
81 bl printf
82
83 pop {r4, r5, r6, r7, r8, lr}
84 bx lr
85
86address_of_big_array : .word big_array
87address_of_message : .word message
Una advertencia importante al manipular la pila de esta manera es que es muy importante
restaurarla y dejarla en el mismo estado en que estaba antes de preparar la llamada. Esta es
la razón por la que nos mantenemos spen la r7línea 49 y la restauramos justo después de la
llamada en la línea 76. Olvidar hacer esto hará que las operaciones adicionales en la pila
empujen los datos al lugar equivocado o salgan de la pila datos incorrectos. Mantener la
pila sincronizada es esencial al llamar a funciones.
¿Podemos hacerlo mejor? Si. En lugar de pasar copias de los valores de la matriz, ¿sería
posible pasar la dirección a la matriz? La respuesta es, nuevamente, sí. Este es el concepto
de pasar por referencia . Cuando pasamos por valor, el valor de los datos pasados se copia
de alguna manera (ya sea en un registro o en una pila). Aquí pasaremos una referencia (es
decir, una dirección) a los datos. Así que ahora terminamos simplemente pasando el
número de elementos y luego la dirección de la matriz, y dejamos que la función use esta
dirección para realizar su cálculo.
Considere el siguiente programa, que también suma una matriz de enteros pero ahora pasa
la matriz por referencia.
[Link]
2
[Link] 4
4
5big_array :
6 /* Same as above */
7
[Link] 4
9
10message: .asciz "The sum of 0 to 255 is %d\n"
11
[Link]
[Link] main
14
15sum_array_ref :
16 /* Parameters:
17 r0 Number of items
18 r1 Address of the array
19 */
20 push {r4, r5, r6, lr}
21
22 /* We have passed all the data by reference */
23
24 /* r4 will hold the sum so far */
25 mov r4, #0 /* r4 ← 0 */
26 mov r5, #0 /* r5 ← 0 */
27
28 b .Lcheck_loop_array_sum
29 .Lloop_array_sum:
30 ldr r6, [r1, r5, LSL #2] /* r6 ← *(r1 + r5 * 4) */
31 add r4, r4, r6 /* r4 ← r4 + r6 */
32 add r5, r5, #1 /* r5 ← r5 + 1 */
33 .Lcheck_loop_array_sum:
34 cmp r5, r0 /* r5 - r0 and update cpsr */
35 bne .Lloop_array_sum /* if r5 != r0 go to .Lloop_array_sum */
36
37 mov r0, r4 /* r0 ← r4, to return the value of the sum */
38 pop {r4, r5, r6, lr}
39
40 bx lr
41
42
43main:
44 push {r4, lr}
45 /* we will not use r4 but we need to keep the function 8-byte aligned */
46
47 mov r0, #256
48 ldr r1, address_of_big_array
49
50 bl sum_array_ref
51
52 /* prepare the call to printf */
53 mov r1, r0 /* second parameter, the sum itself */
54 ldr r0, address_of_message /* first parameter, the message */
55 bl printf
56
57 pop {r4, lr}
58 bx lr
59
60address_of_big_array : .word big_array
61address_of_message : .word message
Ahora el código es mucho más simple ya que evitamos copiar los valores de la matriz en la
pila. Simplemente pasamos la dirección de la matriz como el segundo parámetro de la
función y luego la usamos para acceder a la matriz y calcular la suma. Mucho más simple,
¿no?
Un enfoque alternativo podría ser recibir un puntero a algunos datos y dejar que la función
incremente los datos en la posición definida por el puntero.
increment_ptr:
ldr r1, [r0] /* r1 ← *r0 */
add r1, r1, #1 /* r1 ← r1 + 1 */
str r1, [r0] /* *r0 ← r1 */
Para un ejemplo más elaborado, retomemos el código de la matriz, pero esta vez en lugar de
calcular la suma de todos los valores, multiplicaremos cada elemento por dos y lo
mantendremos en la misma matriz. Para demostrar que lo hemos modificado, también
imprimiremos cada elemento.
1/* double_array.s */
2
[Link]
4
[Link] 4
6big_array :
7 /* Same as above */
8
[Link] 4
10message: .asciz "Item at position %d has value %d\n"
11
[Link]
[Link] main
14
15double_array :
16 /* Parameters:
17 r0 Number of items
18 r1 Address of the array
19 */
20 push {r4, r5, r6, lr}
21
22 mov r4, #0 /* r4 ← 0 */
23
24 b .Lcheck_loop_array_double
25 .Lloop_array_double:
26 ldr r5, [r1, r4, LSL #2] /* r5 ← *(r1 + r4 * 4) */
27 mov r5, r5, LSL #1 /* r5 ← r5 * 2 */
28 str r5, [r1, r4, LSL #2] /* *(r1 + r4 * 4) ← r5 */
29 add r4, r4, #1 /* r4 ← r4 + 1 */
30 .Lcheck_loop_array_double:
31 cmp r4, r0 /* r4 - r0 and update cpsr */
32 bne .Lloop_array_double /* if r4 != r0 go to .Lloop_array_double */
33
34 pop {r4, r5, r6, lr}
35
36 bx lr
37
38print_each_item:
39 push {r4, r5, r6, r7, r8, lr} /* r8 is unused */
40
41 mov r4, #0 /* r4 ← 0 */
42 mov r6, r0 /* r6 ← r0. Keep r0 because we will overwrite it */
43 mov r7, r1 /* r7 ← r1. Keep r1 because we will overwrite it */
44
45
46 b .Lcheck_loop_print_items
47 .Lloop_print_items:
48 ldr r5, [r7, r4, LSL #2] /* r5 ← *(r7 + r4 * 4) */
49
50 /* Prepare the call to printf */
51 ldr r0, address_of_message /* first parameter of the call to printf below */
52 mov r1, r4 /* second parameter: item position */
53 mov r2, r5 /* third parameter: item value */
54 bl printf /* call printf */
55
56 add r4, r4, #1 /* r4 ← r4 + 1 */
57 .Lcheck_loop_print_items:
58 cmp r4, r6 /* r4 - r6 and update cpsr */
59 bne .Lloop_print_items /* if r4 != r6 goto .Lloop_print_items */
60
61 pop {r4, r5, r6, r7, r8, lr}
62 bx lr
63
64main:
65 push {r4, lr}
66 /* we will not use r4 but we need to keep the function 8-byte aligned */
67
68 /* first call print_each_item */
69 mov r0, #256 /* first_parameter: number of items */
70 ldr r1, address_of_big_array /* second parameter: address of the array */
71 bl print_each_item /* call to print_each_item */
72
73 /* call to double_array */
74 mov r0, #256 /* first_parameter: number of items */
75 ldr r1, address_of_big_array /* second parameter: address of the array */
76 bl double_array /* call to double_array */
77
78 /* second call print_each_item */
79 mov r0, #256 /* first_parameter: number of items */
80 ldr r1, address_of_big_array /* second parameter: address of the array */
81 bl print_each_item /* call to print_each_item */
82
83 pop {r4, lr}
84 bx lr
85
86address_of_big_array : .word big_array
87address_of_message : .word message
Si ejecuta este programa, verá que los elementos de la matriz se han duplicado de manera
efectiva.
...
Item at position 248 has value 248
Item at position 249 has value 249
Item at position 250 has value 250
Item at position 251 has value 251
Item at position 252 has value 252
Item at position 253 has value 253
Item at position 254 has value 254
Item at position 255 has value 255
Item at position 0 has value 0
Item at position 1 has value 2
Item at position 2 has value 4
Item at position 3 has value 6
Item at position 4 has value 8
Item at position 5 has value 10
Item at position 6 has value 12
Item at position 7 has value 14
Item at position 8 has value 16
Item at position 9 has value 18
...
Datos locales
La mayoría de nuestros ejemplos que involucran datos almacenados en la memoria (en
contraste con los datos almacenados en registros) han usado variables globales . Las
variables globales son nombres globales, es decir, direcciones de la memoria que usamos a
través de etiquetas. Estas direcciones, de alguna manera, preexisten antes de que se ejecute
el programa. Esto se debe a que los definimos al definir el programa en sí.
A veces, sin embargo, es posible que queramos datos almacenados en la memoria cuya
existencia no esté ligada a la existencia del programa sino a la activación dinámica de una
función. Tal vez recuerde de los capítulos anteriores que la pila nos permite almacenar
datos cuya vida útil es la misma que la activación dinámica de una función. Aquí es donde
almacenaremos las variables locales , que a diferencia de las variables globales, solo
existen porque la función a la que pertenecen ha sido activada dinámicamente (es decir,
llamada / invocada).
En el capítulo 17 pasamos una matriz muy grande a través de la pila para pasar la matriz
por valor. Esto nos llevará a la conclusión de que, de alguna manera, los parámetros actúan
como datos locales, en particular cuando se pasan a través de la pila.
Pero entonces surge un problema, ¿qué pasa si estamos pasando parámetros a través de la
pila y al mismo tiempo tenemos variables locales? Ambas entidades se almacenarán en la
pila. ¿Cómo podemos tratar con las dos fuentes de datos que se encuentran almacenadas en
la misma área de memoria?
1function:
2 /* Keep callee-saved registers */
3 push {r4, lr} /* Keep the callee saved registers */
4 ... /* code of the function */
5 pop {r4, lr} /* Restore the callee saved registers */
6 bx lr /* Return from the function */
Ahora modifiquemos la función para usar un puntero de marco (en el fragmento de código
a continuación, no importa el r5registro que solo aparece aquí para mantener alineada la pila
de 8 bytes).
1function:
2 /* Keep callee-saved registers */
3 push {r4, r5, fp, lr} /* Keep the callee saved registers.
4 We added r5 to keep the stack 8-byte aligned
5 but the important thing here is fp */
6 mov fp, sp /* fp ← sp. Keep dynamic link in fp */
7 ... /* code of the function */
8 mov sp, fp /* sp ← fp. Restore dynamic link in fp */
9 pop {r4, r5, fp, lr} /* Restore the callee saved registers.
10 This will restore fp as well */
11 bx lr /* Return from the function */
Supongamos por ahora que el puntero del marco será útil. Lo que hicimos en la línea de
instrucción 6 fue establecer el enlace dinámico . La pila y los registros se verán así después
de haberlos configurado.
Como puede ver, el fpregistro apuntará a la parte superior de la pila. Pero tenga en cuenta
que en la pila tenemos el valor de lo antiguo fp (el valor de fpen la función que nos
llamó). Si asumimos que nuestra persona que llama también usa un puntero de marco,
entonces el fpque mantuvimos en la pila de los destinatarios de la llamada apunta a la parte
superior de la pila cuando se llamó a nuestra persona que llama.
Pero aún así, esto parece inútil porque ambos registros fpy spen la función actual apuntan a
la misma posición en la pila.
1function:
2 /* Keep callee-saved registers */
3 push {r4, r5, fp, lr} /* Keep the callee saved registers.
4 We added r5 to keep the stack 8-byte aligned
5 but the important thing here is fp */
6 mov fp, sp /* fp ← sp. Keep dynamic link in fp */
7 sub sp, sp, #8 /* Enlarge the stack by 8 bytes */
8 ... /* code of the function */
9 mov sp, fp /* sp ← fp. Restore dynamic link in fp */
10 pop {r4, r5, fp, lr} /* Restore the callee saved registers.
11 This will restore fp as well */
12 bx lr /* Return from the function */
Ahora considere la instrucción mov sp, fpcerca del final de la función. Lo que hace es dejar
el estado de los registros como antes de ampliar la pila (antes de sub sp, sp, #8). Y voilà,
hemos liberado toda la pila que estaba usando nuestra función. Una ventaja de este enfoque
es que no requiere mantener en ningún lugar la cantidad de bytes que reservamos en la
pila. Limpio, ¿no es así?
En el siguiente ejemplo usaremos una función que recibe un número entero por referencia
(es decir, una dirección a un número entero) y luego eleva al cuadrado ese número entero.
void sq(int *c)
{
(*c) = (*c) * (*c);
}
Puede que se pregunte por qué la función sqtiene un parámetro por referencia (¿no debería
ser más fácil devolver un valor?), Pero tenga paciencia conmigo por ahora. Podemos
(¿deberíamos?) Implementar sqsin usar un puntero de marco debido a su simplicidad.
1sq:
2 ldr r1, [r0] /* r1 ← (*r0) */
3 mul r1, r1, r1 /* r1 ← r1 * r1 */
4 str r1, [r0] /* (*r0) ← r1 */
5 bx lr /* Return from the function */
Ahora considere la siguiente función que devuelve la suma de los cuadrados de sus cinco
parámetros. Utiliza la función sqdefinida anteriormente.
int sq_sum5(int a, int b, int c, int d, int e)
{
sq(&a);
sq(&b);
sq(&c);
sq(&d);
sq(&e);
return a + b + c + d + e;
}
Parámetros a, b, cy dse pasaron a través de registros r0, r1, r2, y r3respectivamente. El
parámetro se epasará a través de la pila. Sin sqembargo, la función espera una referencia,
es
decir, una dirección, a un número entero y los registros no tienen una dirección. Esto
significa que tendremos que asignar almacenamiento local temporal para estos
registros. Deberá asignarse al menos un número entero en la pila para poder llamar, sqpero
para simplificar, asignaremos cuatro de ellos.
Esta vez usaremos un puntero de marco para acceder tanto al almacenamiento local como al
parámetro e.
1sq_sum5:
2 push {fp, lr} /* Keep fp and all callee-saved registers. */
3 mov fp, sp /* Set the dynamic link */
4
5 sub sp, sp, #16 /* sp ← sp - 16. Allocate space for 4 integers in the stack */
6 /* Keep parameters in the stack */
7 str r0, [fp, #-16] /* *(fp - 16) ← r0 */
8 str r1, [fp, #-12] /* *(fp - 12) ← r1 */
9 str r2, [fp, #-8] /* *(fp - 8) ← r2 */
10 str r3, [fp, #-4] /* *(fp - 4) ← r3 */
11
12 /* At this point the stack looks like this
13 | Value | Address(es)
14 +--------+-----------------------
15 | r0 | [fp, #-16], [sp]
16 | r1 | [fp, #-12], [sp, #4]
17 | r2 | [fp, #-8], [sp, #8]
18 | r3 | [fp, #-4], [sp, #12]
19 | fp | [fp], [sp, #16]
20 | lr | [fp, #4], [sp, #20]
21 | e | [fp, #8], [sp, #24]
22 v
23 Higher
24 addresses
25 */
26
27 sub r0, fp, #16 /* r0 ← fp - 16 */
28 bl sq /* call sq(&a); */
29 sub r0, fp, #12 /* r0 ← fp - 12 */
30 bl sq /* call sq(&b); */
31 sub r0, fp, #8 /* r0 ← fp - 8 */
32 bl sq /* call sq(&c); */
33 sub r0, fp, #4 /* r0 ← fp - 4 */
34 bl sq /* call sq(&d) */
35 add r0, fp, #8 /* r0 ← fp + 8 */
36 bl sq /* call sq(&e) */
37
38 ldr r0, [fp, #-16] /* r0 ← *(fp - 16). Loads a into r0 */
39 ldr r1, [fp, #-12] /* r1 ← *(fp - 12). Loads b into r1 */
40 add r0, r0, r1 /* r0 ← r0 + r1 */
41 ldr r1, [fp, #-8] /* r1 ← *(fp - 8). Loads c into r1 */
42 add r0, r0, r1 /* r0 ← r0 + r1 */
43 ldr r1, [fp, #-4] /* r1 ← *(fp - 4). Loads d into r1 */
44 add r0, r0, r1 /* r0 ← r0 + r1 */
45 ldr r1, [fp, #8] /* r1 ← *(fp + 8). Loads e into r1 */
46 add r0, r0, r1 /* r0 ← r0 + r1 */
47
48 mov sp, fp /* Undo the dynamic link */
49 pop {fp, lr} /* Restore fp and callee-saved registers */
50 bx lr /* Return from the function */
Como puede ver, primero almacenamos todos los parámetros (pero e) en el almacenamiento
local. Esto significa que necesitamos ampliar la pila lo suficiente, como de costumbre,
restando sp(línea 5). Una vez que tengamos el almacenamiento, podemos hacer la tienda
real usando el fpregistro (líneas 7 a 10). Tenga en cuenta el uso de compensaciones
negativas, porque los datos locales siempre estarán en direcciones más bajas que la
dirección en fp. Como se mencionó anteriormente, el parámetro eno tiene que ser
almacenado porque ya está en la pila, en un desplazamiento positivo desde fp(es decir, en
una dirección más alta que la dirección en fp).
Tenga en cuenta que, en este ejemplo, el puntero del marco no es indispensable ya que
podríamos haberlo utilizado sppara acceder a todos los datos requeridos (ver la
representación de la pila en las líneas 12 a 21).
Para llamar sqtenemos que pasar las direcciones de varios enteros, entonces calculamos la
dirección restando fpel desplazamiento apropiado y almacenándolo en r0, que será usado
para pasar el primer (y único) parámetro de sq(líneas 27 a 36) . Vea cómo, para pasar la
dirección de e, simplemente calculamos una dirección con un desplazamiento positivo
(línea 35). Finalmente añadimos los valores mediante la carga de nuevo en r0y r1y el
uso r0de acumular las adiciones (líneas 38 a 46).
1/* squares.s */
[Link]
3
[Link] 4
5message: .asciz "Sum of 1^2 + 2^2 + 3^2 + 4^2 + 5^2 is %d\n"
6
[Link]
8
9sq:
10 <<defined above>>
11
12sq_sum5:
13 <<defined above>>
14
[Link] main
16
17main:
18 push {r4, lr} /* Keep callee-saved registers */
19
20 /* Prepare the call to sq_sum5 */
21 mov r0, #1 /* Parameter a ← 1 */
22 mov r1, #2 /* Parameter b ← 2 */
23 mov r2, #3 /* Parameter c ← 3 */
24 mov r3, #4 /* Parameter d ← 4 */
25
26 /* Parameter e goes through the stack,
27 so it requires enlarging the stack */
28 mov r4, #5 /* r4 ← 5 */
29 sub sp, sp, #8 /* Enlarge the stack 8 bytes,
30 we will use only the
31 topmost 4 bytes */
32 str r4, [sp] /* Parameter e ← 5 */
33 bl sq_sum5 /* call sq_sum5(1, 2, 3, 4, 5) */
34 add sp, sp, #8 /* Shrink back the stack */
35
36 /* Prepare the call to printf */
37 mov r1, r0 /* The result of sq_sum5 */
38 ldr r0, address_of_message
39 bl printf /* Call printf */
40
41 pop {r4, lr} /* Restore callee-saved registers */
42 bx lr
43
44
45address_of_message: .word message
$ ./square
Sum of 1^2 + 2^2 + 3^2 + 4^2 + 5^2 is 55
El sistema operativo
Nuestra Raspberry Pi ejecuta Raspbian . Raspbian es un sistema operativo basado
en Debian sobre el kernel de Linux . El sistema operativo es una pieza de software
(generalmente una colección de piezas que juntas forman un sistema útil) que habilita y
administra los recursos que requieren los programas para ejecutarse. ¿Qué tipo de recursos,
quizás se esté preguntando? Bueno, muchos tipos diferentes de ellos: procesos, archivos,
dispositivos de red, comunicaciones de red, pantallas, impresoras, terminales,
temporizadores, etc.
Desde el punto de vista del programa, el sistema operativo es solo un gran servidor que
brinda muchos servicios al programa. Pero el sistema operativo también es un cuidador,
tomando medidas cuando algo sale mal o los programas (a veces causados por los usuarios
del sistema operativo) intentan hacer algo para lo que no están autorizados. En nuestro
caso, Linux es el núcleo del sistema operativo Raspbian. El kernel proporciona la
funcionalidad más básica necesaria para proporcionar estos servicios (a veces los
proporciona directamente, a veces solo proporciona la funcionalidad esencial mínima para
que puedan implementarse). Puede verse como un programa fundamental que siempre está
en ejecución (o al menos, siempre listo) para que pueda atender las solicitudes de los
programas ejecutados por los usuarios. Linux es similar a UNIX® kernel y, como tal,
comparte muchas características con el largo linaje de sistemas operativos similares a
UNIX®.
Procesos
Para poder asignar recursos, el sistema operativo necesita una entidad a la que otorgue
dichos recursos. Esta entidad se llama proceso. Un proceso es un programa en ejecución. El
mismo programa se puede ejecutar varias veces, cada vez que se ejecuta es un proceso
diferente.
Llamadas al sistema
Un proceso interactúa con el sistema operativo al realizar llamadas al sistema . Una
llamada al sistema es conceptualmente como llamar a una función, pero más sofisticada. Es
más sofisticado porque ahora necesitamos satisfacer algunos requisitos de seguridad
adicionales. Un sistema operativo es una parte crítica de un sistema y no podemos permitir
que los procesos eludan el control del sistema operativo. Una llamada de función habitual
no ofrece protección de ningún tipo. Cualquier estrategia que pudiéramos diseñar sobre una
llamada de función simple sería fácilmente posible eludirla. Como consecuencia de esta
restricción, necesitamos el apoyo de la arquitectura (en nuestro caso ARM) para
implementar de forma segura un mecanismo de llamada al sistema.
La forma "ea-C"
Continuando con nuestro ejemplo, primero llamaremos a writetravés de la biblioteca C. La
biblioteca C sigue la convención AAPCS. El prototipo de la llamada al sistema de escritura
se puede encontrar en las páginas de manual de Linux y es el siguiente.
ssize_t write(int fd, const void *buf, size_t count);
Aquí ambos size_ty ssize_tson enteros de 32 bits,
donde el primero no está firmado y el
segundo está firmado. Equipados con nuestro conocimiento del ensamblador AAPCS y
ARM, no debería ser difícil para nosotros realizar una llamada como la siguiente
const char greeting[13] = "Hello world\n";
write(1, greeting, sizeof(greeting)); // Here sizeof(greeting) is 13
Aqui esta el codigo
/* write_c.s */
.data
/* This is an assembler constant: the assembler will compute it. Needless to say
that this must evaluate to a constant value. In this case we are computing the
difference of addresses between the address after_greeting and greeting. In this
case it will be 13 */
.set size_of_greeting, after_greeting - greeting
.text
.globl main
main:
push {r4, lr}
mov r0, #0
pop {r4, lr}
bx lr
.data
.text
.globl main
main:
push {r7, lr}
Etiquetas
Una de las características distintivas de los ensambladores es la escasez de información
simbólica. El único soporte simbólico disponible en este (bajo) nivel son las etiquetas . Ya
sabemos que las etiquetas son solo direcciones a la memoria del programa (tanto datos
como código).
Cuando definimos una función en ensamblador, definimos una etiqueta para ella.
fun: /* label 'fun' */
push {r4, r5}
...
pop {r4, r5}
bx lr
Posteriormente (o antes, a los montadores normalmente no les importa) usamos la
etiqueta. Entonces una llamada como
bl fun
Lefun está diciendo al ensamblador, estoy usando aquí, pero tienes que poner la dirección
apropiada allí al generar el código de máquina, ¿de acuerdo? .
En realidad, llamar a una función suele ser mucho más complicado pero al final hay una
etiqueta que nos lleva a la función.
Siente el poder
El último ejemplo no parece muy interesante, pero poder llamar a una función
indirectamente es algo muy poderoso. Nos permite mantener la dirección de una función en
algún lugar y llamarla. Nos permite pasar la dirección de una función a otra función. ¿Por
qué querríamos hacer eso? Bueno, es una forma rudimentaria, pero efectiva, de pasar
código a otra función.
.align 4
greeter:
push {r4, lr} /* keep lr because we call printf,
we keep r4 to keep the stack 8-byte
aligned, as per AAPCS requirements */
blx r0 /* indirect call to r0 */
pop {r4, lr} /* restore r4 and lr */
bx lr /* return to the caller */
Y ahora defina a algunas personas. Cada persona es en realidad un par formado por una
dirección a su nombre y una dirección a su etiqueta.
[Link] 4
29person_john: .word name_john, person_english
[Link] 4
31person_pierre: .word name_pierre, person_french
[Link] 4
33person_sally: .word name_sally, person_english
[Link] 4
35person_bernadette: .word name_bernadette, person_french
Finalmente, agrupemos a todas las personas en una matriz. La matriz contiene direcciones
para cada persona (no las personas en sí).
Ahora definamos el código. Estas son las dos funciones específicas para cada idioma
(inglés y francés). Tenga en cuenta que ya nombramos sus etiquetas en las etiquetas de
arriba.
Como puede ver, lo que hacemos aquí es cargar los elementos 0 a 3 del peoplearreglo y
llamar a la función greet_person. Cada elemento de la peoplematriz es un puntero, por lo que
podemos ponerlos en un registro, en este caso r0porque será el primer parámetro
de greet_person.
Espero que este último ejemplo, aunque sea un poco largo, realmente te muestre el poder de
las llamadas indirectas.
Ya sabemos que ARM es una arquitectura de 32 bits: los registros de propósito general
tienen un ancho de 32 bits y las direcciones en la memoria son números de 32 bits. El
tamaño de entero natural para una arquitectura generalmente se llama palabra y en ARM
obviamente son enteros de 32 bits. A veces, sin embargo, tenemos que tratar con datos
de subpalabras : números enteros de tamaño inferior a 32 bits.
Datos de la subpalabra
En este capítulo, los datos de las subpalabras se referirán a un byte oa media palabra . Un
byte es un número entero de 8 bits y una media palabra es un número entero de 16 bits. Por
tanto, una media palabra ocupa 2 bytes y una palabra 4 bytes.
.align 4
one_halfword: .hword 42445
/* This number in binary is 1010010111001101 */
Tenga en cuenta que, como de costumbre, estamos alineando datos a 4 bytes. Más adelante
veremos que para las subpalabras las restricciones de alineación de datos son un poco más
relajadas.
Cargar y almacenar
Antes de que comencemos a operar un entero de subpalabra, necesitamos llevarlo a alguna
parte. Si no vamos a cargarlo / almacenarlo desde / a la memoria, simplemente podemos
usar un registro. Puede que tengamos que comprobar que no sobrepasamos el rango de la
subpalabra, pero eso es todo.
.globl main
main:
push {r4, lr}
addr addr + 1
ARM en Raspberry Pi es una pequeña arquitectura endian , esto significa que los bytes en
la memoria se colocan en la memoria (de direcciones inferiores a superiores) comenzando
desde el byte menos significativo hasta el byte más significativo. Las instrucciones de carga
y almacenamiento conservan este pedido. Este hecho generalmente no es importante a
menos que se vea la memoria como una secuencia de bytes. Esta es la razón por la que en la
tabla anterior 11001101 siempre aparece en la primera columna incluso si el número 42445
es 10100101 11001101 en binario.
Ok, cargar usando ldrby ldrhestá bien siempre y cuando solo usemos números naturales. Los
números integrales incluyen números negativos y comúnmente se representan usando el
complemento a dos . Si ampliamos a cero un número negativo, el bit de signo (el bit más
significativo del complemento a dos) no se propagará y terminaremos con un número
positivo no relacionado. Al cargar enteros de subpalabras de complemento a dos,
necesitamos realizar la extensión de signo usando las instrucciones lsrby lsrh.
ldr r0, addr_of_one_byte /* r0 ← &one_byte */
ldrsb r0, [r0] /* r0 ← *{signed byte}r0 */
addr addr + 1
Interpretación de bits
Interpretación de bits
Tienda
Mientras que load requiere tener cuidado si la subpalabra cargada es un número codificado
en binario o en complemento a dos, una instrucción de almacenamiento no requiere nada de
esta consideración. La razón es que las instrucciones correspondientes strby strhsimplemente
tomarán los 8 o 16 bits menos significativos del registro y los almacenarán en la memoria.
ldr r1, addr_of_one_byte /* r0 ← &one_byte */
ldrsb r0, [r1] /* r0 ← *{signed byte}r1 */
strb r0, [r1] /* *{byte}r1 ← r0 */
Restricciones de alineación
Al cargar o almacenar un entero de 32 bits desde la memoria, la dirección debe estar
alineada con 4 bytes, esto significa que los dos bits menos significativos de la dirección
deben ser 0. Dicha restricción se relaja si la operación de memoria (cargar o almacenar) es
una subpalabra. uno. Para medias palabras, la dirección debe tener una alineación de 2
bytes. Para bytes, no se aplica ninguna restricción. De esta manera
podemos reinterpretar palabras y medias palabras como medias palabras y bytes si
queremos.
Considere el siguiente ejemplo, donde atravesamos una sola palabra reinterpretando sus
bytes y medias palabras (y finalmente la palabra en sí).
[Link]
2
[Link] 4
4a_word: .word 0x11223344
5
[Link] 4
7message_bytes : .asciz "byte #%d is 0x%x\n"
8message_halfwords : .asciz "halfword #%d is 0x%x\n"
9message_words : .asciz "word #%d is 0x%x\n"
10
[Link]
12
[Link] main
14main:
15 push {r4, r5, r6, lr} /* keep callee saved registers */
16
17 ldr r4, addr_a_word /* r4 ← &a_word */
18
19 mov r5, #0 /* r5 ← 0 */
20 b check_loop_bytes /* branch to check_loop_bytes */
21
22 loop_bytes:
23 /* prepare call to printf */
24 ldr r0, addr_message_bytes
25 /* r0 ← &message_bytes
26 first parameter of printf */
27 mov r1, r5 /* r1 ← r5
28 second parameter of printf */
29 ldrb r2, [r4, r5] /* r2 ← *{byte}(r4 + r5)
30 third parameter of printf */
31 bl printf /* call printf */
32 add r5, r5, #1 /* r5 ← r5 + 1 */
33 check_loop_bytes:
34 cmp r5, #4 /* compute r5 - 4 and update cpsr */
35 bne loop_bytes /* if r5 != 4 branch to loop_bytes */
36
37 mov r5, #0 /* r5 ← 0 */
38 b check_loop_halfwords /* branch to check_loop_halfwords */
39
40 loop_halfwords:
41 /* prepare call to printf */
42 ldr r0, addr_message_halfwords
43 /* r0 ← &message_halfwords
44 first parameter of printf */
45 mov r1, r5 /* r1 ← r5
46 second parameter of printf */
47 mov r6, r5, LSL #1 /* r6 ← r5 * 2 */
48 ldrh r2, [r4, r6] /* r2 ← *{half}(r4 + r6)
49 this is r2 ← *{half}(r4 + r5 * 2)
50 third parameter of printf */
51 bl printf /* call printf */
52 add r5, r5, #1 /* r5 ← r5 + 1 */
53 check_loop_halfwords:
54 cmp r5, #2 /* compute r5 - 2 and update cpsr */
55 bne loop_halfwords /* if r5 != 2 branch to loop_halfwords */
56
57 /* prepare call to printf */
58 ldr r0, addr_message_words /* r0 ← &message_words
59 first parameter of printf */
60 mov r1, #0 /* r1 ← 0
61 second parameter of printf */
62 ldr r2, [r4] /* r1 ← *r4
63 third parameter of printf */
64 bl printf /* call printf */
65
66 pop {r4, r5, r6, lr} /* restore callee saved registers */
67 mov r0, #0 /* set error code */
68 bx lr /* return to system */
69
70addr_a_word : .word a_word
71addr_message_bytes : .word message_bytes
72addr_message_halfwords : .word message_halfwords
73addr_message_words : .word message_words
Varias veces en capítulos anteriores hemos hablado de ARM como una arquitectura que
tiene varias características dirigidas a incrustar sistemas. En los sistemas integrados, la
memoria es escasa y costosa, por lo que los diseños que ayudan a reducir la huella de
memoria son muy bienvenidos. Hoy veremos otra de estas características: el conjunto de
instrucciones Thumb.
Instrucciones
Thumb proporciona alrededor de 45 instrucciones (de alrededor de 115 en ARMv6). La
codificación más estrecha de 16 bits significa que estaremos más limitados en lo que
podemos hacer en nuestro código. Los registros se dividen en dos conjuntos: registros
bajos , r0to r7, y registros altos , r8to r15. La mayoría de las instrucciones solo pueden
funcionar completamente con registros bajos y algunas otras tienen un comportamiento
limitado cuando se trabaja con registros altos.
Además, las instrucciones de Thumb no se pueden predicar. Recuerde que casi todas las
instrucciones ARM se pueden condicionar según los indicadores del cpsrregistro. Este no es
el caso en Thumb, donde solo la instrucción de bifurcación es condicional.
La combinación de ARM y Thumb solo es posible a nivel de función: una función debe ser
completamente ARM o Thumb, no puede ser una combinación de los dos conjuntos de
instrucciones. Recuerde que nuestro sistema Raspbian no es compatible con Thumb, por lo
que en algún momento tendremos que saltar del código ARM al código Thumb. Esto se
hace usando la instrucción (disponible en ambos conjuntos de instrucciones) blx. Esta
instrucción se comporta como la blinstrucción que usamos para las llamadas a funciones,
pero cambia el estado del procesador de ARM a Thumb (o Thumb a ARM).
También tenemos que decirle al ensamblador que una parte del ensamblador es en realidad
Thumb mientras que la otra es ARM. Dado que por defecto el ensamblador espera ARM,
tendremos que cambiar a Thumb en algún momento.
1/* thumb-first.s */
[Link]
3
[Link] 16 /* Here we say we will use Thumb */
[Link] 2 /* Make sure instructions are aligned at 2-byte boundary */
6
7thumb_function:
8 mov r0, #2 /* r0 ← 2 */
9 bx lr /* return */
10
[Link] 32 /* Here we say we will use ARM */
[Link] 4 /* Make sure instructions are aligned at 4-byte boundary */
13
[Link] main
15main:
16 push {r4, lr}
17
18 blx thumb_function /* From ARM to Thumb we use blx */
19
20 pop {r4, lr}
21 bx lr
00000000 <thumb_function>:
0: 2002 movs r0, #2
2: 4770 bx lr
4: e1a00000 nop ; (mov r0, r0)
8: e1a00000 nop ; (mov r0, r0)
c: e1a00000 nop ; (mov r0, r0)
00000010 <main>:
10: e92d4010 push {r4, lr}
14: fafffff9 blx 0 <thumb_function>
18: e8bd4010 pop {r4, lr}
1c: e12fff1e bx lr
Verifique thumb_function: sus dos instrucciones están codificadas en solo dos bytes (la
instrucción bx lrestá en el desplazamiento 2 de mov r0, #2. Compare esto con las
instrucciones en main: cada una está en el desplazamiento 4 de su instrucción predecesora.
Tenga en cuenta que el ensamblador agregó algo de relleno al final de el thumb_functionen
forma de nops (que no debería ejecutarse, de todos modos).
thumb_function_1:
push {r4, lr}
bl thumb_function_2
pop {r4, lr} /* ERROR: cannot use lr in pop in Thumb mode */
bx lr
Desafortunadamente, esto será rechazado por el ensamblador. Si recuerda el capítulo 10, en
ARM push y pop son nemotécnicos para stmdb sp!y ldmia sp!, respectivamente. Pero en el
modo Pulgar pushy popson instrucciones por sí mismas, por lo que son más
limitadas: pushsolo pueden usar registros bajos y lr, popsolo pueden usar registros bajos
y pc. El comportamiento de estas dos instrucciones es casi el mismo que el de la
mnemomics ARM. Entonces, probablemente ahora se esté preguntando por qué estos dos
casos especiales para lry pc. Este es el truco: en el modo Thumb pop {pc}es equivalente a
sacar el valor valde la pila y luego hacerlo bx val. Entonces, la secuencia de dos
instrucciones: pop {r4, lr}seguida de se bx lrconvierte en simple pop {r4, pc}.
thumb_function_2:
mov r0, #2
bx lr /* A leaf Thumb function (i.e. a function that does not call
any other function so it did not have to keep lr in the stack)
returns using "bx lr" */
thumb_function_1:
push {r4, lr}
bl thumb_function_2 /* From Thumb to Thumb we use bl */
pop {r4, pc} /* This is how we return from a non-leaf Thumb function */
.text
.data
message: .asciz "Hello world %d\n"
pop {r4, pc} /* restore registers and return from Thumb function */
.align 4
addr_of_message: .word message
.code 32 /* Here we say we will use ARM */
.align 4 /* Make sure instructions are aligned at 4-byte boundary */
.globl main
main:
push {r4, lr} /* keep r4 and lr in the stack */
blx thumb_function /* from ARM to Thumb we use blx */
pop {r4, lr} /* restore registers */
bx lr /* return */
Hoy veremos qué sucede cuando anidamos una función dentro de otra. Parece algo
inofensivo, pero viene con su propia dosis de detalles interesantes.
Funciones anidadas
A nivel de ensamblador, las funciones no se pueden anidar.
Por lo tanto, puede tener sentido anidar una función dentro de otra. ¿Qué significa anidar
una función dentro de otra? Bueno, significa que esta función solo tendrá significado
mientras su función adjunta esté dinámicamente activa (es decir, haya sido llamada).
A nivel de ensamblador, una función anidada se parecerá mucho a cualquier otra función,
pero tienen suficientes diferencias para ser interesantes.
Enlace dinámico
En el capítulo 18 hablamos sobre el enlace dinámico . El enlace dinámico se establece al
comienzo de la función y usamos el fpregistro (un alias para r11) para mantener una
dirección en la pila, generalmente llamada puntero de marco (de ahí el fpnombre). Es
dinámico porque se relaciona con la activación dinámica de la función. El puntero del
marco nos da una forma coherente de acceder a los datos locales de la función (que siempre
se almacenarán en la pila) y los parámetros que deben pasarse utilizando la pila.
Recuerde que los datos locales, debido a que la pila crece hacia abajo, se encuentran en
desplazamientos negativos de la dirección en fp. Por el contrario, los parámetros pasados
usando la pila estarán en compensaciones positivas. Tenga en cuenta que fp(también
conocido como r11) es un registro de llamadas guardadas según lo especificado por la
AAPCS. Esto significa que tendremos que pushcolocarlo en la pila al ingresar a la
función. Un hecho no obvio de este último paso es que el puntero del cuadro anterior
siempre es accesible desde el actual. De hecho, se encuentra entre los otros registros de
llamadas guardadas en un desplazamiento positivo defp(pero un desplazamiento más bajo
que los parámetros pasados usando la pila porque los registros guardados por el destinatario
se insertan en último lugar). Esta última propiedad puede parecer poco interesante, pero nos
permite encadenarnos a través del puntero del marco de nuestros llamadores. En general,
esto solo es de interés para los depuradores porque necesitan realizar un seguimiento de las
funciones que se están llamando hasta el momento.
El código anterior presenta este caso simple en el que una función puede llamar a una
anidada. Al final de la función f, xtendrá el valor 2porque la función anidada gmodifica la
variable x, también modificada por fsí misma.
1/* nested01.s */
2
[Link]
4
5f:
6 push {r4, r5, fp, lr} /* keep registers */
7 mov fp, sp /* keep dynamic link */
8
9 sub sp, sp, #8 /* make room for x (4 bytes)
10 plus 4 bytes to keep stack
11 aligned */
12 /* x is in address "fp - 4" */
13
14 mov r4, #1 /* r4 ← 0 */
15 str r4, [fp, #-4] /* x ← r4 */
16
17 bl g /* call (nested function) g
18 (the code of 'g' is given below, after 'f') */
19
20 ldr r4, [fp, #-4] /* r4 ← x */
21 add r4, r4, #1 /* r4 ← r4 + 1 */
22 str r4, [fp, #-4] /* x ← r4 */
23
24 mov sp, fp /* restore dynamic link */
25 pop {r4, r5, fp, lr} /* restore registers */
26 bx lr /* return */
27
28 /* nested function g */
29 g:
30 push {r4, r5, fp, lr} /* keep registers */
31 mov fp, sp /* keep dynamic link */
32
33 /* At this point our stack looks like this
34
35 Data | Address | Notes
36 ------+---------+--------------------------
37 r4 | fp |
38 r5 | fp + 4 |
39 fp | fp + 8 | This is the previous fp
40 lr | fp + 16 |
41 */
42
43 ldr r4, [fp, #+8] /* get the frame pointer
44 of my caller
45 (since only f can call me)
46 */
47
48 /* now r4 acts like the fp we had inside 'f' */
49 ldr r5, [r4, #-4] /* r5 ← x */
50 add r5, r5, #1 /* r5 ← r5 + 1 */
51 str r5, [r4, #-4] /* x ← r5 */
52
53 mov sp, fp /* restore dynamic link */
54 pop {r4, r5, fp, lr} /* restore registers */
55 bx lr /* return */
56
[Link] main
58
59main :
60 push {r4, lr} /* keep registers */
61
62 bl f /* call f */
63
64 mov r0, #0
65 pop {r4, lr}
66 bx lr
Ok, la idea esencial está establecida. Al acceder a una variable local, siempre necesitamos
obtener el puntero del marco de la función a la que pertenece la variable local. En la línea
43 obtenemos el puntero del marco de nuestro llamador y luego lo usamos para acceder a la
variable x, líneas 49 a 51. Por supuesto, si la variable local pertenece a la función actual, no
se tiene que hacer nada especial ya que fp es suficiente, vea líneas 20 a 22.
Dicho esto, aunque la idea es fundamentalmente correcta, usar el enlace dinámico nos
limita mucho: solo es posible una única llamada desde una función adjunta. ¿Qué pasa si
permitimos que las funciones anidadas llamen a otras funciones anidadas (funciones
hermanas) o, peor aún, qué hubiera pasado si lo ganterior se llamara a sí mismo de forma
recursiva? El enlace dinámico que encontraremos en la pila siempre hará referencia a la
función activada dinámicamente anterior, y en el ejemplo anterior lo era f, pero si se gllama
a sí mismo de forma recursiva, ¡ gserá la función activada dinámicamente anterior!
Está claro que algo anda mal. Usar el enlace dinámico no es correcto porque, al acceder a
una variable local de una función envolvente, necesitamos obtener la última activación de
esa función envolvente en el punto donde se llamó a la función anidada. La forma de
mantener la última activación de la función envolvente se llama enlace estático en contraste
con el enlace dinámico.
g(); // call g
m(); // call m
x = x + 3; // x ← x + 3
}
x = 1; // x ← 1
h(); // call h
// here x will be 8
}
Una función puede, obviamente, llamar a una función anidada inmediatamente. Entonces,
desde el cuerpo de la función fpodemos llamar go h. De manera similar, desde el cuerpo de
la función hpodemos llamar m. Una función puede ser llamada por otras funciones (no
anidadas inmediatamente) siempre que la profundidad de anidamiento de la persona que
llama sea mayor o igual que la llamada. Entonces, desde mpodemos
llamar m(recursivamente) h, gy f. No se permitiría eso fni se gllamaría m.
Configurar el enlace estático es un poco más complicado porque requiere prestar atención a
la función a la que llamamos. Hay dos casos:
31f:
32 push {r4, r10, fp, lr} /* keep registers */
33 mov fp, sp /* setup dynamic link */
34
35 sub sp, sp, #8 /* make room for x (4 + 4 bytes) */
36 /* x will be in address "fp - 4" */
37
38 /* At this point our stack looks like this
39
40 Data | Address | Notes
41 ------+---------+---------------------------
42 | fp - 8 | alignment (per AAPCS)
43 x | fp - 4 |
44 r4 | fp |
45 r10 | fp + 8 | previous value of r10
46 fp | fp + 12 | previous value of fp
47 lr | fp + 16 |
48 */
49
50 mov r4, #1 /* r4 ← 1 */
51 str r4, [fp, #-4] /* x ← r4 */
52
53 /* prepare the call to h */
54 mov r10, fp /* setup the static link,
55 since we are calling an immediately nested function
56 it is just the current frame */
57 bl h /* call h */
58
59 mov sp, fp /* restore stack */
60 pop {r4, r10, fp, lr} /* restore registers */
61 bx lr /* return */
Dado fque no está anidado en ninguna otra función, el valor anterior de r10no tiene ningún
significado especial para nosotros. Simplemente lo conservamos porque r10, a pesar del
significado especial que le daremos, sigue siendo un registro de llamadas guardadas según
lo exige la AAPCS. Al principio, asignamos espacio para la variable xampliando la pila
(línea 35). La variable xsiempre estará adentro fp - 4. Luego lo configuramos xen 1 (línea
51). Nada de lujos aquí, ya que esta es una función no anidada.
Ahora f llama a h (línea 57). Dado que es una función anidada inmediatamente, el enlace
estático es como en el caso I: el puntero del cuadro actual. Así que lo configuramos r10para
ser fp(línea 56).
Ahora la función llama g(línea 86) pero debe establecer correctamente el enlace estático
antes de la llamada. En este caso, el enlace estático es el mismo que hporque llamamos
al gque es hermano de h, por lo que comparten el mismo enlace estático. Lo obtenemos
de fp + 8(línea 85). Este es, de hecho, el caso II descrito anteriormente: gno es una función
anidada inmediatamente de h. Entonces, tenemos que obtener el enlace estático de la
persona que llama (el enlace estático de h, que se encuentra en fp + 8) y luego avanzar tantas
veces como la diferencia de sus profundidades de anidación. Ser hermanos significa que sus
profundidades de anidación son las mismas, por lo que en realidad no se requiere ningún
avance.
Después de la llamada a g, la función llama m(línea 92) que pasa a ser una función
inmediatamente anidada, por lo que su enlace estático es el puntero del marco actual (línea
91) porque este es nuevamente el caso I.
Lo primero que hace m es x ← x + 2. Entonces tenemos que obtener la dirección de x. La
dirección de xes relativa al puntero del marco de fporque xes una variable local de f. No
tenemos el puntero del marco de fsino el de h(este es el enlace estático de m). Dado que los
punteros del marco forman una cadena, podemos cargar el puntero del marco de hy luego
usarlo para obtener el enlace estático del hcual será el puntero del marco f. Es posible que
tenga que volver a leer esta última declaración dos veces :) Así que primero obtenemos el
puntero del marco de h(línea 122), recuerde que este es el enlace estático mque se configuró
cuando se hllamóm(línea 91). Ahora tenemos el puntero de cuadro de h, por lo que podemos
obtener su enlace estático (línea 123) que nuevamente está en el desplazamiento, +8pero
esto es por casualidad, ¡podría estar en un desplazamiento diferente! El enlace estático
de hes el puntero del marco de f, por lo que ahora tenemos el puntero del marco fcomo
queríamos y luego podemos proceder a obtener la dirección de x, que está en el
desplazamiento -4del puntero del marco de f. Con esta dirección ahora podemos realizar x ←
x + 2(líneas 124 a 126).
Veamos ahora el código de g, que es bastante similar al de h excepto que no llama a nadie.
A continuación se muestra una imagen de cómo se ve el diseño una vez que se mha
llamado g. Tenga en cuenta que el enlace estático de gy hes el mismo, el puntero del marco
de f, porque son hermanos.
A continuación se muestra la misma imagen, pero esta vez usando líneas de colores para
mostrar cómo cada función puede calcular la dirección de x.
Finalmente aquí está el main. Tenga en cuenta que cuando una función no anidada llama a
otra función no anidada, no es necesario hacer nada r10. Esta es la razón por la r10que no
tiene ningún valor significativo en la entrada a f.
[Link] main
153
154main :
155 push {r4, lr} /* keep registers */
156
157 bl f /* call f */
158
159 mov r0, #0
160 pop {r4, lr}
161 bx lr
Discusión
Si se detiene y piensa en todas estas cosas del enlace estático, pronto se dará cuenta de que
hay algo turbio con todo este asunto de funciones anidadas: estamos pasando algún tipo de
parámetro oculto (a través r10) a las funciones anidadas. De hecho, de alguna manera
estamos haciendo trampa, porque lo configuramos r10justo antes de la llamada y luego lo
presionamos en la entrada de las funciones anidadas, incluso si no lo modifican en la
función llamada. ¿Por qué estamos haciendo este paso aparentemente inútil?
Bueno, al presionar siempre r10la pila, solo estamos ocultando la verdad desnuda: las
funciones anidadas requieren un parámetro adicional, algo oculto. Este parámetro adicional
es este enlace estático. A veces también se le llama ámbito léxico . Se llama ámbito léxico
porque nos da el contexto de la función que lo encierra léxicamente (es decir, en el código)
(en contraste, el ámbito dinámico sería el de nuestro llamador, que no nos importa a menos
que seamos un depurador). Con ese contexto léxico podemos obtener las variables locales
de esa función adjunta. Debido a la naturaleza encadenada del enlace estático, podemos
subir los ámbitos léxicos. Esta es la razón por la que mpuede acceder a una variable de f,
simplemente sube a través de los enlaces estáticos como se muestra en la última imagen de
arriba.
¿Podemos pasar el alcance léxico a una función usando la pila, en lugar de un registro
guardado por el destinatario? Seguro. Por conveniencia, puede que tenga que ser el primer
parámetro pasado por la pila (por lo que su desplazamiento desde fpes fácil de calcular). En
lugar de configurar r10antes de la llamada, ampliaremos spsegún sea necesario (al menos 8
bytes, para mantener alineada la pila de 8 bytes) y luego almacenaremos allí el enlace
estático. En el diseño de pila, el enlace estático ahora se encontrará después (es decir,
compensaciones más grandes que) los registros insertados.
Como puede ver, cualquier enfoque requiere que mantengamos el enlace estático en la
pila. Si bien nuestro enfoque de consumo r10puede no ser completamente ortodoxo, termina
haciendo lo correcto.
Clasificación
Primero tomaremos un desvío. La función C qsortse puede utilizar para ordenar cualquier
tipo de matriz. Su firma C es la siguiente.
void qsort(void *base,
size_t nmemb,
size_t size,
int (*compar)(const void *, const void *));
qsortdevuelve void, es decir, no devuelvenada porque realiza la ordenación en el lugar . Esto
significa que pasaremos una matriz (potencialmente sin clasificar) llamada basede
longitud nmemba qsort. Cuando qsortregrese, los elementos de esta matriz se
ordenarán. Si qsortpudiera ordenar un tipo específico de matrices, sería bastante
limitado. Para poder ordenar cualquier matriz, se qsortrequiere el valor sizede cada elemento
de la matriz. Tenga en cuenta que la matriz se pasa por referencia (de lo contrario, la
clasificación en el lugar no sería posible): void*es la forma en C de decir «Acepto una
dirección para cualquier tipo de datos».
1/* print-array.s */
2
[Link]
4
5/* declare an array of 10 integers called my_array */
[Link] 4
7my_array: .word 82, 70, 93, 77, 91, 30, 42, 6, 92, 64
8
9/* format strings for printf */
10/* format string that prints an integer plus a space */
[Link] 4
12integer_printf: .asciz "%d "
13/* format string that simply prints a newline */
[Link] 4
15newline_printf: .asciz "\n"
16
[Link]
18
19print_array:
20 /* r0 will be the address of the integer array */
21 /* r1 will be the number of items in the array */
22 push {r4, r5, r6, lr} /* keep r4, r5, r6 and lr in the stack */
23
24 mov r4, r0 /* r4 ← r0. keep the address of the array */
25 mov r5, r1 /* r5 ← r1. keep the number of items */
26 mov r6, #0 /* r6 ← 0. current item to print */
27
28 b .Lprint_array_check_loop /* go to the condition check of the loop */
29
30 .Lprint_array_loop:
31 /* prepare the call to printf */
32 ldr r0, addr_of_integer_printf /* r0 ← &integer_printf */
33 /* load the item r6 in the array in address r4.
34 elements are of size 4 bytes so we need to multiply r6 by 4 */
35 ldr r1, [r4, +r6, LSL #2] /* r1 ← *(r4 + r6 << 2)
36 this is the same as
37 r1 ← *(r4 + r6 * 4) */
38 bl printf /* call printf */
39
40 add r6, r6, #1 /* r6 ← r6 + 1 */
41 .Lprint_array_check_loop:
42 cmp r6, r5 /* perform r6 - r5 and update cpsr */
43 bne .Lprint_array_loop /* if cpsr states that r6 is not equal to r5
44 branch to the body of the loop */
45
46 /* prepare call to printf */
47 ldr r0, addr_of_newline_printf /* r0 ← &newline_printf */
48 bl printf
49
50 pop {r4, r5, r6, lr} /* restore r4, r5, r6 and lr from the stack */
51 bx lr /* return */
52
53addr_of_integer_printf: .word integer_printf
54addr_of_newline_printf: .word newline_printf
55
[Link] main
57main:
58 push {r4, lr} /* keep r4 and lr in the stack */
59
60 /* prepare call to print_array */
61 ldr r0, addr_of_my_array /* r0 ← &my_array */
62 mov r1, #10 /* r1 ← 10
63 our array is of length 10 */
64 bl print_array /* call print_array */
65
66 mov r0, #0 /* r0 ← 0 set errorcode to 0 prior returning from main */
67 pop {r4, lr} /* restore r4 and lr in the stack */
68 bx lr /* return */
69
70addr_of_my_array: .word my_array
El código anterior es bastante sencillo y no incluye nada que no se haya visto en entregas
anteriores. Ejecutarlo simplemente imprime el contenido actual de la matriz.
$ ./print-array
82 70 93 77 91 30 42 6 92 64
Comparación
Arriba, cuando hablamos qsortnos saltamos el comparparámetro. ¿Qué es compar? Es una
dirección a una función. La sintaxis funky para C nos dice que a esta función, si alguna vez
se la llama, se le pasarán dos direcciones (de nuevo, no le importa cuáles son, entonces
son void*) y devuelve un número entero. El manual de qsort explica que esta función tiene
que devolver menor que cero, cero o mayor que cero. Si el objeto en la dirección del primer
parámetro de compares menor que el objeto en la dirección del segundo parámetro, entonces
tiene que devolver menor que cero. Si son iguales , debería devolver cero. Si el primer
objeto es mayor que el segundo, entonces debería devolver mayor que cero.
Si se pregunta por qué los parámetros de comparson en realidad en const void*lugar de void*,
es la forma en C de decirnos que los datos de los objetos referenciados no pueden cambiar
durante la comparación. Esto puede parecer obvio dado que cambiar las cosas no es el
trabajo de una función de comparación. Pasarlos por referencia nos permitiría
cambiarlos. Así que este es un recordatorio de que no deberíamos.
Dado que nuestra matriz es una matriz de números enteros, tendremos que comparar
enteros: escribamos una función que, dados dos punteros a números enteros (es decir,
direcciones) se comporte como se indicó anteriormente.
19integer_comparison:
20 /* r0 will be the address to the first integer */
21 /* r1 will be the address to the second integer */
22 ldr r0, [r0] /* r0 ← *r0
23 load the integer pointed by r0 in r0 */
24 ldr r1, [r1] /* r1 ← *r1
25 load the integer pointed by r1 in r1 */
26
27 cmp r0, r1 /* compute r0 - r1 and update cpsr */
28 moveq r0, #0 /* if cpsr means that r0 == r1 then r0 ← 0 */
29 movlt r0, #-1 /* if cpsr means that r0 < r1 then r0 ← -1 */
30 movgt r0, #1 /* if cpsr means that r0 > r1 then r0 ← 1 */
31 bx lr /* return */
Ahora tenemos el último bit que falta para poder llamar qsort. Aquí hay un programa que
imprime (solo mainse muestra) la matriz dos veces, antes de ordenarla y después de
ordenarla.
[Link] main
67main:
68 push {r4, lr} /* keep r4 and lr in the stack */
69
70 /* prepare call to print_array */
71 ldr r0, addr_of_my_array /* r0 ← &my_array */
72 mov r1, #10 /* r1 ← 10
73 our array is of length 10 */
74 bl print_array /* call print_array */
75
76 /* prepare call to qsort */
77 /*
78 void qsort(void *base,
79 size_t nmemb,
80 size_t size,
81 int (*compar)(const void *, const void *));
82 */
83 ldr r0, addr_of_my_array /* r0 ← &my_array
84 base */
85 mov r1, #10 /* r1 ← 10
86 nmemb = number of members
87 our array is 10 elements long */
88 mov r2, #4 /* r2 ← 4
89 size of each member is 4 bytes */
90 ldr r3, addr_of_integer_comparison
91 /* r3 ← &integer_comparison
92 compar */
93 bl qsort /* call qsort */
94
95 /* now print again to see if elements were sorted */
96 /* prepare call to print_array */
97 ldr r0, addr_of_my_array /* r0 ← &my_array */
98 mov r1, #10 /* r1 ← 10
99 our array is of length 10 */
100 bl print_array /* call print_array */
101
102 mov r0, #0 /* r0 ← 0 set errorcode to 0 prior returning from main */
103 pop {r4, lr} /* restore r4 and lr in the stack */
104 bx lr /* return */
105
106addr_of_my_array: .word my_array
107addr_of_integer_comparison : .word integer_comparison
Si juntamos todo, podemos verificar que nuestra matriz esté efectivamente ordenada
después de la llamada a la qsortfunción.
$ ./sort-array
82 70 93 77 91 30 42 6 92 64
6 30 42 64 70 77 82 91 92 93
.text
integer_comparison_count_global:
/* r0 will be the address to the first integer */
/* r1 will be the address to the second integer */
push {r4, r5} /* keep callee-saved registers */
ldr r0, [r0] /* r0 ← *r0
load the integer pointed by r0 in r0 */
ldr r1, [r1] /* r1 ← *r1
load the integer pointed by r1 in r1 */
En el último capítulo terminamos con una breve discusión sobre las funciones
anidadas. Una desventaja de las funciones anidadas es que un puntero a una función
anidada requiere dos cosas: la dirección de la función y el alcance léxico. Si vuelves a
revisar el ejemplo anterior donde llamamos qsort, verás que no mencionamos en ninguna
parte el alcance léxico. Y hay una razón para eso, no es posible pasárselo qsort. En C, las
funciones no se pueden anidar, por lo que un puntero a una función puede ser simplemente
la dirección de la función.
Trampolín
Continuaremos usando la convención del último capítulo: r10tendrá el alcance léxico al
ingresar la función. Pero qsort, cuando las llamadas integer_compare_countno nos lo
configuran: no podemos contar con r10tener un valor significativo cuando se nos llama
desde qsort. Esto significa que en qsortrealidad debería llamar a algo que primero se
establece r10con el valor correcto y luego salta a integer_compare_count. Llamaremos a este
código auxiliar (o pseudofunción) un trampolín . La técnica utilizada aquí es similar a la
utilizada por GCC descrita en Lexical Closures for C ++ (Thomas M. Breuel, USENIX C +
+ Conference Proceedings, 17-21 de octubre de 1988) .
Usé la plantilla de Word porque, si bien las instrucciones no van a cambiar, hay dos
elementos en el trampolín, etiquetados function_calledy lexical_scope, que deberán configurarse
adecuadamente antes de usar el trampolín.
Puede ser más fácil de entender si considera el código anterior como si fueran datos: véalo
como una matriz de números enteros. Los dos primeros enteros, function_calledy lexical_scope,
siguen siendo cero, pero se establecerán en algún momento. Los elementos restantes en la
matriz son otros enteros (no nos importa cuáles) que codifican instrucciones ARM. Lo
bueno es que estas instrucciones se refieren a los dos primeros números enteros, por lo que
al cambiarlos estamos cambiando indirectamente lo que hace el trampolín. Este trampolín
ocupa 8 palabras, es decir, 32 bytes.
[Link] main
55main:
56 push {r4, r5, r6, fp, lr} /* keep callee saved registers */
57 mov fp, sp /* setup dynamic link */
58
59 sub sp, sp, #4 /* counter will be in fp - 4 */
60 /* note that now the stack is 8-byte aligned */
61
62 /* set counter to zero */
63 mov r4, #0 /* r4 ← 0 */
64 str r4, [fp, #-4] /* counter ← r4 */
Nada especial aquí, configuramos el enlace dinámico, asignamos espacio en la pila para el
contador y lo configuramos en cero.
Ahora dejamos espacio para el trampolín en la pila. Recuerde que nuestro trampolín ocupa
32 bytes.
En el ciclo anterior, r4cuenta cuántos bytes quedan por copiar. r5y r6son punteros dentro del
trampolín (fuente) y la pila (destino), respectivamente. Dado que copiamos 4 bytes a la vez,
los tres registros se actualizan en 4.
Ahora tenemos el trampolín copiado en la pila. Recuerde, es solo una serie de palabras, las
dos primeras de las cuales deben actualizarse. Los primeros 4 bytes deben ser la dirección
de la función a llamar, es decir, integer_comparison_county los segundos 4 bytes deben ser el
enlace estático, es decir fp.
Recordemos que nuestro trampolín ocupa 32 bytes pero en la pila también tenemos el
contador. Esta es la razón por la que el trampolín comienza en fp - 36(esta es también la
dirección de la primera palabra del trampolín, por supuesto). La segunda palabra es
entonces fp - 32.
Arquitectura de Harvard
Si intenta ejecutar el programa como se muestra, probablemente funcionará. Pero lo hará
por casualidad. La razón es que estamos presentando una forma simple de código auto
modificable.
Un caché es una memoria más pequeña y rápida que se encuentra entre el procesador y la
memoria principal. Se utiliza para acelerar los accesos a la memoria, ya que la mayoría de
las veces dichos accesos ocurren cerca de otros accesos a la memoria (es decir, acceder a
elementos de una matriz, diferentes variables locales en la pila o una instrucción tras otra en
secuenciación implícita) o cerca en el tiempo ( es decir, acceder varias veces a la misma
variable local o ejecutar la misma instrucción cuando el código está en un bucle).
La mayoría de los procesadores modernos cuentan con cachés distinguidos para datos
(llamado caché de datos ) e instrucciones (llamado caché de instrucciones). La razón de tal
diferenciación es que el acceso a la memoria para ejecutar instrucciones tiene un patrón
diferente al acceso a la memoria para cargar / almacenar datos. Es beneficioso hacer tal
distinción pero tiene un precio: cuando un programa manipula datos que luego se
ejecutarán como instrucciones (como hicimos con el trampolín, pero también cuando el
sistema operativo carga un programa en la memoria) la vista del dos cachés con respecto al
estado del programa se vuelve incoherente: los cambios que hicimos en los datos tendrán
efecto en el caché de datos pero no en el caché de instrucciones. Por el contrario, dado que
la caché de instrucciones solo obtendrá datos de la memoria principal (y no de la caché de
datos), debemos volver a escribir todos los cambios que hicimos en la caché de datos en la
memoria principal (esto se llama vaciarel caché). También tenemos que asegurarnos de que
la caché de instrucciones obtenga de manera efectiva las instrucciones de la memoria, en
lugar de reutilizar instrucciones cargadas previamente (que ahora estarían obsoletas), por lo
que tenemos que invalidar (o borrar) la caché de instrucciones.
En ARM, las instrucciones que vacían e invalidan cachés son operaciones privilegiadas
(realizadas a través de instrucciones del coprocesador en el coprocesador 15 que administra
el sistema de memoria de la CPU). Esto significa que solo el sistema operativo puede
ejecutar tales instrucciones. Como puede ver, es posible que el código de usuario deba
solicitar un borrado de caché. Linux proporciona una cacheflushllamada al sistema para este
propósito. Recuerde que en el capítulo 19 vimos cómo realizar llamadas al sistema.
Discusión
Dado que las funciones anidadas requieren un ámbito léxico, no pueden pasarse
trivialmente como direcciones simples a otras funciones. Hoy hemos visto que al usar un
trampolín es posible pasarlos a funciones que no permiten pasar un ámbito léxico. El precio
es tener que copiar una plantilla, el trampolín, tener que configurarlo con los valores
adecuados. También tenemos que vaciar las cachés para evitar ejecutar código
incorrecto. Es complicado pero factible.
Tener que vaciar la caché no es deseable (aunque no es necesario en todas las arquitecturas)
y puede causar una degradación severa del rendimiento. Las piezas de código críticas para
el rendimiento normalmente no querrían hacer esto.
Sin embargo, una preocupación seria con el enfoque del trampolín se relaciona con el
hecho de que necesitamos una pila ejecutable. Un sistema operativo moderno, como Linux,
puede marcar regiones de memoria para que sean legibles, grabables o ejecutables. Una
región de la memoria que no es ejecutable puede contener instrucciones, pero si nos
ramificamos a esa región, el procesador indicará una falla y el sistema operativo
probablemente matará nuestro proceso. La posibilidad de deshabilitar la ejecución de
regiones de memoria específicas se realiza por motivos de seguridad. La mayoría de las
veces no es necesario ejecutar instrucciones que se encuentran en la pila o en
la .datasección. Solo .texttiene sentido en estos casos que sea ejecutable.
Como hemos visto en este capítulo y en el anterior, las funciones anidadas tienen varias
desventajas, por lo que no es sorprendente que varios lenguajes de programación no
brinden soporte para ellas.
SIMD
SIMD significa datos múltiples de una sola instrucción y significa que una instrucción se
puede utilizar para realizar la misma operación en varios operandos al mismo tiempo. En
los capítulos 13 y 14 vimos que al cambiar el lencampo en fpscry usar al menos un operando
en los bancos vectoriales, entonces una instrucción operaba en lenregistros en el banco (s)
vectorial (s), efectivamente haciendo por lentiempos una operación de coma flotante. De
esta manera, una sola instrucción como vadd.f32podría usarse para realizar hasta 8 adiciones
de punto flotante. Esta estrategia de acelerar el cálculo también se denomina paralelismo
de datos .
SIMD con enteros
El soporte SIMD para enteros también existe en ARMv6 pero es más limitado: los datos
múltiples son las subpalabras (ver capítulo 21) de un registro de propósito general. Esto
significa que podemos hacer 2 operaciones en las 2 medias palabras de un registro de
propósito general. De manera similar, podemos hacer hasta 4 operaciones en los 4 bytes de
un registro de propósito general.
Ejemplo motivador
En este punto, es posible que se pregunte cuál es el propósito de esta función y por qué
existe. Supongamos que tenemos dos señales de audio PCM de 16 bits muestreadas a
alguna frecuencia (es decir, 44,1 kHz como en un CD de audio). Esto significa que en el
momento de grabar el "sonido analógico" de cada canal se muestrea muchas veces por
segundo y la muestra, que representa la amplitud de la señal, se codifica usando un número
de 16 bits.
Una operación que podríamos querer hacer es mezclar las dos señales en una señal (por
ejemplo, antes de reproducir esa señal final a través de los altavoces). Una forma
(ligeramente incorrecta) de hacer esto es promediando las dos señales. El siguiente código
es un esquema de lo que queremos hacer.
short int channel1[num_samples]; // in our environment a 'short int' is a half-word
short int channel2[num_samples];
mov r4, #0 /* r4 ← 0 */
b .Lcheck_loop /* branch to check_loop */
.Lloop:
mov r5, r4, LSL #1 /* r5 ← r4 << 1 (this is r5 ← r4 * 2) */
/* a halfword takes two bytes, so multiply
the index by two. We do this here because
ldrsh does not allow an addressing mode
like [r0, r5, LSL #1] */
ldrsh r6, [r0, r5] /* r6 ← *{signed half}(r0 + r5) */
ldrsh r7, [r1, r5] /* r7 ← *{signed half}(r1 + r5) */
add r8, r6, r7 /* r8 ← r6 + r7 */
mov r8, r8, ASR #1 /* r8 ← r8 >> 1 (this is r8 ← r8 / 2)*/
strh r8, [r2, r5] /* *{half}(r2 + r5) ← r8 */
add r4, r4, #1 /* r4 ← r4 + 1 */
.Lcheck_loop:
cmp r4, r3 /* compute r4 - r3 and update cpsr */
blt .Lloop /* if r4 < r3 jump to the
beginning of the loop */
Probablemente podríamos estar contentos con este código, pero si estuviera en el negocio
de diseñar procesadores para dispositivos integrados, probablemente sería sensible a los
códigos de sus clientes. Y lo más probable es que su reproductor MP3 portátil (o cualquier
dispositivo capaz de reproducir música) esté "ARM adentro". Así que este es un código que
puede mejorarse desde el punto de vista de la arquitectura.
Medias palabras
o Firmado: sadd16,ssub16
o Sin firmar: uadd16,usub16
Bytes
o Firmado: sadd8,ssub8
o Sin firmar: uadd8,usub8
No debería ser difícil encontrar usos obvios para estas instrucciones. Por ejemplo, el
siguiente ciclo puede beneficiarse de la uadd8instrucción.
// unsigned char is an unsigned byte in our environment
// a, b and c are arrays of N unsigned chars
unsigned char a[N], b[N], c[N];
int i;
for (i = 0; i < N; i++)
{
c[i] = a[i] + b[i];
}
Primero escribamos un enfoque ingenuo para el ciclo anterior, que es similar al del
comienzo de la publicación.
1naive_byte_array_addition:
2 /* r0 contains the base address of a */
3 /* r1 contains the base address of b */
4 /* r2 contains the base address of c */
5 /* r3 is N */
6 /* r4 is the number of the current item
7 so it holds that 0 ≤ r4 < r3 */
8
9 mov r4, #0 /* r4 ← 0 */
10 b .Lcheck_loop0 /* branch to check_loop0 */
11
12 .Lloop0:
13 ldrb r5, [r0, r4] /* r5 ← *{unsigned byte}(r0 + r4) */
14 ldrb r6, [r1, r4] /* r6 ← *{unsigned byte}(r1 + r4) */
15 add r7, r5, r6 /* r7 ← r5 + r6 */
16 strb r7, [r2, r4] /* *{unsigned byte}(r2 + r4) ← r7 */
17 add r4, r4, #1 /* r4 ← r4 + 1 */
18 .Lcheck_loop0:
19 cmp r4, r3 /* perform r4 - r3 and update cpsr */
20 blt .Lloop0 /* if cpsr means that r4 < r3 jump to loop0 */
Este ciclo nuevamente está bien, pero podemos hacerlo mejor usando la
instrucción uadd8. Tenga en cuenta que ahora podremos agregar 4 bytes a la vez. Esto
significa que tendremos que incrementar r4en 4.
1simd_byte_array_addition_0:
2 /* r0 contains the base address of a */
3 /* r1 contains the base address of b */
4 /* r2 contains the base address of c */
5 /* r3 is N */
6 /* r4 is the number of the current item
7 so it holds that 0 ≤ r4 < r3 */
8
9 mov r4, #0 /* r4 ← 0 */
10 b .Lcheck_loop1 /* branch to check_loop1 */
11
12 .Lloop1:
13 ldr r5, [r0, r4] /* r5 ← *(r0 + r4) */
14 ldr r6, [r1, r4] /* r6 ← *(r1 + r4) */
15 sadd8 r7, r5, r6 /* r7[7:0] ← r5[7:0] + r6[7:0] */
16 /* r7[15:8] ← r5[15:8] + r6[15:8] */
17 /* r7[23:16] ← r5[23:16] + r6[23:16] */
18 /* r7[31:24] ← r5[31:24] + r6[31:24] */
19 /* rA[x:y] means bits x to y of the register rA */
20 str r7, [r2, r4] /* *(r2 + r4) ← r7 */
21 add r4, r4, #4 /* r4 ← r4 + 4 */
22 .Lcheck_loop1:
23 cmp r4, r3 /* perform r4 - r3 and update cpsr */
24 blt .Lloop1 /* if cpsr means that r4 < r3 jump to loop1 */
Una sutileza del código anterior es que solo funciona si N(se mantiene r3) es un múltiplo de
4. Si no es el caso (y esto incluye cuando 0 ≤ r3 <4), entonces el ciclo hará menos
iteraciones de las esperadas. Si sabemos que Nes un múltiplo de 4, no se debe hacer nada
más. Pero si no es un múltiplo de 4, necesitaremos lo que se llama bucle epílogo , para los
casos restantes. Tenga en cuenta que en nuestro caso, el ciclo del epílogo tendrá que hacer 0
(si N es un múltiplo de 4), 1, 2 o 3 iteraciones. Podemos implementarlo como un switch con
4 casos más fall-through (ver capítulo 16) o si nos preocupa el tamaño del código, con un
bucle. Usaremos un bucle.
Sin embargo, no podemos simplemente agregar un ciclo de epílogo al ciclo anterior, porque
en realidad está haciendo más trabajo del que queremos. Cuando N no es múltiplo de
cuatro, la última iteración agregará 1, 2 o 3 bytes más que no pertenecen a la matriz
original. Esta es una receta para un desastre, así que debemos evitarlo. Tenemos que
asegurarnos de que cuando estamos en el bucle, r4es tal que r4, r4 + 1, r4 + 2y r4 + 3son
elementos válidos de la matriz. Esto significa que debemos comprobar que r4 < N, r4 + 1 <
N, r4 + 2 < Ny r4 + 3 < N. Dado que el último de estos cuatro implica los tres primeros, basta
con comprobarlo r4 + 3 < N.
Tenga en cuenta que la comprobación r4 + 3 < Nnos obligaría a calcular r4 + 3en cada
iteración del ciclo, pero no es necesario. Verificar r4 + 3 < Nes equivalente a verificar r4 < N -
3. N - 3no depende de, por r4lo que se puede calcular antes del ciclo.
1simd_byte_array_addition_2:
2 /* r0 contains the base address of a */
3 /* r1 contains the base address of b */
4 /* r2 contains the base address of c */
5 /* r3 is N */
6 /* r4 is the number of the current item
7 so it holds that 0 ≤ r4 < r3 */
8
9 mov r4, #0 /* r4 ← 0 */
10 sub r8, r3, #3 /* r8 ← r3 - 3
11 this is r8 ← N - 3 */
12 b .Lcheck_loop2 /* branch to check_loop2 */
13
14 .Lloop2:
15 ldr r5, [r0, r4] /* r5 ← *(r0 + r4) */
16 ldr r6, [r1, r4] /* r6 ← *(r1 + r4) */
17 sadd8 r7, r5, r6 /* r7[7:0] ← r5[7:0] + r6[7:0] */
18 /* r7[15:8] ← r5[15:8] + r6[15:8] */
19 /* r7[23:16] ← r5[23:16] + r6[23:16] */
20 /* r7[31:24] ← r5[31:24] + r6[31:24] */
21 str r7, [r2, r4] /* *(r2 + r4) ← r7 */
22 add r4, r4, #4 /* r4 ← r4 + 4 */
23 .Lcheck_loop2:
24 cmp r4, r8 /* perform r4 - r8 and update cpsr */
25 blt .Lloop2 /* if cpsr means that r4 < r8 jump to loop2 */
26 /* i.e. if r4 < N - 3 jump to loop2 */
27 /* epilog loop */
28 b .Lcheck_loop3 /* branch to check_loop3 */
29
30 .Lloop3:
31 ldrb r5, [r0, r4] /* r5 ← *{unsigned byte}(r0 + r4) */
32 ldrb r6, [r1, r4] /* r6 ← *{unsigned byte}(r1 + r4) */
33 add r7, r5, r6 /* r7 ← r5 + r6 */
34 strb r7, [r2, r4] /* *{unsigned byte}(r2 + r4) ← r7 */
35
36 add r4, r4, #1 /* r4 ← r4 + 1 */
37 .Lcheck_loop3:
38 cmp r4, r3 /* perform r4 - r3 and update cpsr */
39 blt .Lloop3 /* if cpsr means that r4 < r3 jump to loop 3 */
Medias palabras
o Firmado: shadd16,shsub16
o Sin firmar: uhadd16,uhsub16
Bytes
o Firmado: shadd8,shsub8
o Sin firmar: uhadd8,uhsub8
Así, el ejemplo motivador del inicio del post se puede implementar utilizando
la shsub16instrucción. Para simplificar, supongamos que num_sampleses un múltiplo de 2
(ahora estamos tratando con medias palabras), por lo que no es necesario un epílogo.
better_channel_mixing:
/* r0 contains the base address of channel1 */
/* r1 contains the base address of channel2 */
/* r2 contains the base address of channel_out */
/* r3 is the number of samples */
/* r4 is the number of the current sample
so it holds that 0 ≤ r4 < r3 */
mov r4, #0 /* r4 ← 0 */
b .Lcheck_loop /* branch to check_loop */
.Lloop:
ldr r6, [r0, r4] /* r6 ← *(r0 + r4) */
ldr r7, [r1, r4] /* r7 ← *(r1 + r4) */
shadd16 r8, r6, r7 /* r8[15:0] ← (r6[15:0] + r7[15:0]) >> 1*/
/* r8[31:16] ← (r6[31:16] + r7[31:16]) >> 1*/
str r8, [r2, r4] /* *(r2 + r4) ← r8 */
add r4, r4, #2 /* r4 ← r4 + 2 */
.Lcheck_loop:
cmp r4, r3 /* compute r4 - r3 and update cpsr */
blt .Lloop /* if r4 < r3 jump to the
beginning of the loop */
Aritmética de saturación
Volvamos a nuestro ejemplo motivador. Hicimos un promedio de los dos canales de 16 bits
para mezclarlos pero, en realidad, la mezcla se logra simplemente agregando los dos
canales. En general, esto está bien porque las señales no están correlacionadas y la amplitud
de una muestra mixta generalmente se puede codificar en 16 bits. A veces, sin embargo, la
muestra mixta puede tener una amplitud que cae fuera del rango de 16 bits. En este caso,
queremos recortar la muestra dentro del rango representable. Una muestra con una amplitud
demasiado positiva se recortará a 2 15 -1, una muestra con una amplitud demasiado negativa
se recortará a -2 15 .
.text
clipped_add16bit:
/* first operand is in r0 */
/* second operand is in r0 */
/* result is left in r0 */
push {r4, lr} /* keep registers */
ldr r4, addr_of_max16bit /* r4 ← &max16bit */
ldr r4, [r4] /* r4 ← *r4 */
/* now r4 == 32767 (i.e. 2^15 - 1) */
end:
Medias palabras
o Firmado: qadd16,qsub16
o Sin firmar: uqadd16,uqsub16
Bytes
o Firmado: qadd8,qsub8
o Sin firmar: uqadd8,uqsub8
mov r4, #0 /* r4 ← 0 */
b .Lcheck_loop /* branch to check_loop */
.Lloop:
ldr r6, [r0, r4] /* r6 ← *(r0 + r4) */
ldr r7, [r1, r4] /* r7 ← *(r1 + r4) */
qadd16 r8, r6, r7 /* r8[15:0] ← saturated_sum_16(r6[15:0], r7[15:0]) */
/* r8[31:16] ← saturated_sum_16(r6[31:16], r7[31:16]) */
str r8, [r2, r4] /* *(r2 + r4) ← r8 */
add r4, r4, #2 /* r4 ← r4 + 2 */
.Lcheck_loop:
cmp r4, r3 /* compute r4 - r3 and update cpsr */
blt .Lloop /* if r4 < r3 jump to the
beginning of the loop */
En este capítulo hablaremos de un paso fascinante que se requiere para crear un programa,
incluso cuando se usa ensamblador. Hoy hablaremos de vincular.
DUENDE
Dado que varias herramientas manipulan archivos objeto (compiladores, ensambladores,
enlazadores), un formato común resulta útil. Hay algunos formatos disponibles para este
propósito como COFF, Mach-O o ELF. En el mundo UNIX (incluido Linux), el formato
más popular es ELF (formato ejecutable y de enlace) . Este formato se utiliza para archivos
de objetos (llamados objetos reubicables, veremos a continuación por qué), objetos
compartidos (bibliotecas dinámicas) y ejecutables (el programa en sí).
[Link]:
2var: .word 42
[Link]
4func:
5 /* ... */
6 ldr r0, addr_of_var /* r0 ← &var */
7 ldr r0, [r0] /* r0 ← *r0 */
8 /* ... */
9addr_of_var : .word var
Pero la pregunta que queda es, ¿qué pone el ensamblador en esa ubicación designada
por addr_of_var? Hemos escrito .word varpero ¿qué significa esto? El ensamblador debería
emitir la dirección de var, pero en este punto se desconoce su dirección. Entonces, el
ensamblador solo puede emitir información parcial en este punto. Esta información se
completará más tarde.
Un ejemplo
Consideremos un ejemplo más complejo para ver este proceso en acción. Considere el
siguiente código que toma dos variables globales y las agrega a una variable de
resultado. Luego llamamos a una función, que escribiremos en otro archivo. Esta función
incrementará la variable de resultado en uno. La variable de resultado tiene que ser
accesible desde el otro archivo, por lo que tendremos que marcarla como global (similar a
lo que hacemos con main).
/* main.s */
.data
one_var : .word 42
another_var : .word 66
.text
.globl main
main:
ldr r0, addr_one_var /* r0 ← &one_var */
ldr r0, [r0] /* r0 ← *r0 */
ldr r1, addr_another_var /* r1 ← &another_var */
ldr r1, [r1] /* r1 ← *r1 */
add r0, r0, r1 /* r0 ← r0 + r1 */
ldr r1, addr_result /* r1 ← &result */
str r0, [r1] /* *r1 ← r0 */
bl inc_result /* call to inc_result */
mov r0, #0 /* r0 ← 0 */
bx lr /* return */
Reubicaciones
Dijimos anteriormente que el ensamblador no conoce el valor final y en su lugar puede
poner alguna información parcial (por ejemplo, las compensaciones de .data). También
anota que se requiere alguna corrección aquí. Esta corrección se llama relocation. Podemos
leer las reubicaciones usando banderas -drde objdump.
$ objdump -dr main.o
main.o: file format elf32-littlearm
Disassembly of section .text:
00000000 <main>:
0: e59f0020 ldr r0, [pc, #32] ; 28 <addr_one_var>
4: e5900000 ldr r0, [r0]
8: e59f101c ldr r1, [pc, #28] ; 2c <addr_another_var>
c: e5911000 ldr r1, [r1]
10: e0800001 add r0, r0, r1
14: e59f1014 ldr r1, [pc, #20] ; 30 <addr_result>
18: e5810000 str r0, [r1]
1c: ebfffffe bl 0 <inc_result>
1c: R_ARM_CALL inc_result
20: e3a00000 mov r0, #0
24: e12fff1e bx lr
00000028 <addr_one_var>:
28: 00000000 .word 0x00000000
28: R_ARM_ABS32 .data
0000002c <addr_another_var>:
2c: 00000004 .word 0x00000004
2c: R_ARM_ABS32 .data
00000030 <addr_result>:
30: 00000000 .word 0x00000000
30: R_ARM_ABS32 result_var
Las reubicaciones se representan como la salida anterior como
OFFSET: TYPE VALUE
También se imprimen inmediatamente después del punto al que afectan.
OFFSETes el desplazamiento dentro de la sección para los bytes que necesitarán arreglarse
(en este caso todos ellos dentro .text). TYPEes el tipo de reubicación. El tipo de reubicación
determina qué bytes se arreglan y cómo. VALUEes una entidad simbólica para la que
tenemos que calcular la dirección física. Puede ser un símbolo real,
como inc_resulty result_var, o el nombre de una sección, como .data.
.globl inc_result
inc_result:
ldr r1, addr_result /* r1 ← &result */
ldr r0, [r1] /* r0 ← *r1 */
add r0, r0, #1 /* r0 ← r0 + 1 */
str r0, [r1] /* *r1 ← r0 */
bx lr /* return */
00000000 <inc_result>:
0: e59f100c ldr r1, [pc, #12] ; 14 <addr_result>
4: e5910000 ldr r0, [r1]
8: e2800001 add r0, r0, #1
c: e5810000 str r0, [r1]
10: e12fff1e bx lr
00000014 <addr_result>:
14: 00000000 .word 0x00000000
14: R_ARM_ABS32 result_var
Podemos ver que tiene una reubicación result_varcomo se esperaba.
Ahora podemos combinar los dos archivos de objeto para generar un binario ejecutable.
$ gcc -o [Link] print_float.o reloc.o
Y verifique el contenido del archivo. Nuestro programa incluirá algunas funciones de la
biblioteca C que podemos ignorar.
$ objdump -d [Link]
...
00008390 <main>:
8390: e59f0020 ldr r0, [pc, #32] ; 83b8 <addr_one_var>
8394: e5900000 ldr r0, [r0]
8398: e59f101c ldr r1, [pc, #28] ; 83bc <addr_another_var>
839c: e5911000 ldr r1, [r1]
83a0: e0800001 add r0, r0, r1
83a4: e59f1014 ldr r1, [pc, #20] ; 83c0 <addr_result>
83a8: e5810000 str r0, [r1]
83ac: eb000004 bl 83c4 <inc_result>
83b0: e3a00000 mov r0, #0
83b4: e12fff1e bx lr
000083b8 <addr_one_var>:
83b8: 00010578 .word 0x00010578
000083bc <addr_another_var>:
83bc: 0001057c .word 0x0001057c
000083c0 <addr_result>:
83c0: 00010580 .word 0x00010580
000083c4 <inc_result>:
83c4: e59f100c ldr r1, [pc, #12] ; 83d8 <addr_result>
83c8: e5910000 ldr r0, [r1]
83cc: e2800001 add r0, r0, #1
83d0: e5810000 str r0, [r1]
83d4: e12fff1e bx lr
000083d8 <addr_result>:
83d8: 00010580 .word 0x00010580
...
De la salida anterior podemos observar que addr_one_varestá en
dirección 0x00010578, addr_another_varestá en dirección 0x0001057cy addr_resultestá en
dirección 0x00010580. El último aparece repetido, pero esto se debe a que ambos
archivos [Link] se inc_result.srefieren a él, por lo que deben guardar la dirección en algún
lugar. Tenga en cuenta que en ambos casos contiene la misma dirección.
Sections:
Idx Name Size VMA LMA File off Algn Flags
...
13 .text 0000015c 000082e4 000082e4 000002e4 2**2 CONTENTS, ALLOC, LOAD,
READONLY, CODE
...
23 .data 00000014 00010570 00010570 00000570 2**2 CONTENTS, ALLOC, LOAD, DATA
...
La columna VMAdefine la dirección de la sección. En nuestro caso .datase encuentra
en 00010570. Y nuestras variables se encuentran en 0x00010578, 0x0001057c y 0x00010580. Se
trata de compensaciones 8, 12 y 16 respectivamente desde el principio de .data. El enlazador
ha colocado algunas otras variables en esta sección antes que la nuestra. Podemos ver esto
pidiendo al enlazador que imprima un mapa del ejecutable generado.
$ gcc -o [Link] main.o inc_result.o -Wl,--print-map > [Link]
$ cat [Link]
[Link] 0x00010570 0x14
315 0x00010570 PROVIDE (__data_start, .)
316 *(.data .data.* .[Link].d.*)
317 .data 0x00010570 0x4 /usr/lib/gcc/arm-linux-gnueabihf/4.6/../../../arm-linux-gnueabihf/crt1.o
318 0x00010570 data_start
319 0x00010570 __data_start
320 .data 0x00010574 0x0 /usr/lib/gcc/arm-linux-gnueabihf/4.6/../../../arm-linux-gnueabihf/crti.o
321 .data 0x00010574 0x4 /usr/lib/gcc/arm-linux-gnueabihf/4.6/crtbegin.o
322 0x00010574 __dso_handle
323 .data 0x00010578 0xc main.o
324 0x00010580 result_var
325 .data 0x00010584 0x0 inc_result.o
326 .data 0x00010584 0x0 /usr/lib/arm-linux-gnueabihf/libc_nonshared.a([Link])
327 .data 0x00010584 0x0 /usr/lib/gcc/arm-linux-gnueabihf/4.6/crtend.o
328 .data 0x00010584 0x0 /usr/lib/gcc/arm-linux-gnueabihf/4.6/../../../arm-linux-gnueabihf/cr
000083bc <addr_another_var>:
83bc: 0001057c .word 0x0001057c
000083c0 <addr_result>:
83c0: 00010580 .word 0x00010580
...
000083d8 <addr_result>:
83d8: 00010580 .word 0x00010580
¿Y la llamada a inc_result?
83ac: eb000004 bl 83c4
Este es un poco más complicado. Recuerde que la operación de reubicación es (S + A) -
P. Aquí Aestá 0y Pestá 0x000083ac, S es 0x000083c4. Por lo tanto, la reubicación tiene que
definir un desplazamiento de 24 bytes (83c4 - 83ac es 24 (10 ). La instrucción blcodifica el
desplazamiento desplazándolo 2 bits a la derecha. Por lo tanto, el desplazamiento actual
codificado eb000004es 16. Recuerde que la corriente pcapunta al instrucción actual más 8
bytes, por lo que esta instrucción nos dice exactamente que saltemos a un desplazamiento +
24 bytes, exactamente lo que queríamos.
...
83ac: eb000004 bl 83c4 <inc_result>
83b0: e3a00000 mov r0, #0
83b4: e12fff1e bx lr
000083b8 <addr_one_var>:
83b8: 00010578 .word 0x00010578
000083bc <addr_another_var>:
83bc: 0001057c .word 0x0001057c
000083c0 <addr_result>:
83c0: 00010580 .word 0x00010580
000083c4 <inc_result>:
83c4: e59f100c ldr r1, [pc, #12] ; 83d8 <addr_result>
...
Más información
Los enlazadores son un poco arcanos porque deben manejar las partes de código de nivel
más bajo. Por eso, a veces es difícil encontrar buenos recursos sobre ellos.
Vinculación dinámica
¿Qué pasa si en lugar de construir todo el programa en el momento del enlace, simplemente
ensamblamos las partes mínimas para poder completarlo al ejecutar el programa? ¿Y si en
lugar de bibliotecas estáticas utilizáramos bibliotecas dinámicas ? Por lo tanto, el programa
se vincularía dinámicamente a ellos al ejecutarse.
Al principio, esto parece un poco extravagante, pero tiene algunas ventajas. Al retrasar el
proceso de enlace, obtenemos algunas ventajas. Por ejemplo, un programa que
utilice printfno necesitaría tener el printfarchivo en el programa. Podría usar una biblioteca C
dinámica existente del sistema, que también tendrá su copia de printf. Además, si se
encuentra un error en el printfde esa biblioteca dinámica, solo reemplazar la biblioteca
dinámica sería suficiente y nuestro programa se beneficiaría automáticamente de un
archivo printf. Si lo hubiéramos vinculado estáticamente printf, nos veríamos obligados a
volver a vincularlo para obtener el correcto printf.
Por supuesto, muy pocas cosas son gratuitas en la naturaleza, y los enlaces dinámicos y las
bibliotecas dinámicas requieren más esfuerzo. Necesitamos hablar sobre la carga.
Cargando un programa
Antes de que podamos ejecutar un programa, debemos guardarlo en la memoria. Este
proceso se llama carga . Por lo general, el sistema operativo es responsable de cargar los
programas.
Los sistemas operativos modernos, como Linux, proporcionan a los procesos (es decir,
programas en ejecución) lo que se denomina memoria virtual gracias al soporte de
hardware específico para ello. La memoria virtual da la ilusión de que un proceso puede
usar el espacio de la memoria como quiera. Este mecanismo también proporciona
aislamiento: un proceso no puede escribir en la memoria de otro proceso. Ejecutar varios
programas que quieren cargarse en la misma dirección no es un problema porque
simplemente se cargan en la misma dirección virtual. El sistema operativo asigna estas
direcciones virtuales a diferentes direcciones físicas.
En sistemas sin memoria virtual, todas las direcciones son físicas. Esto hace imposible
cargar más de un proceso si alguno de ellos se superpone en la memoria con otro.
Para usar bibliotecas dinámicas, dado que el proceso de vinculación ocurre en tiempo de
ejecución, necesitamos un segundo programa, llamado vinculador dinámico . Esto contrasta
con el enlazador de programas o el enlazador estático . Este enlazador dinámico también
actuará como cargador dinámico porque será responsable de cargar las bibliotecas
dinámicas necesarias en la memoria.
A esta herramienta la llamamos enlazador dinámico porque una vez que haya cargado el
código y los datos de la biblioteca dinámica en la memoria tendrá que resolver algunas
reubicaciones. La cantidad de reubicaciones que debe realizar depende de si el código
es independiente de la posición o no.
Posición de código independiente
El código puede depender de la posición o ser independiente de la posición.
Una ventaja de esta técnica es que no hay que realizar reubicaciones en el código en el
momento de la carga. Solo el GOT debe reubicarse correctamente al cargar dinámicamente
el código. Esto puede reducir enormemente el tiempo de carga. Dado que el código en la
memoria no tiene que arreglarse, todos los procesos que usan las mismas bibliotecas
pueden compartirlo. Esto se hace en sistemas operativos que admiten memoria virtual: las
partes del código de las bibliotecas dinámicas se comparten entre procesos. Esto significa
que, aunque el código todavía ocupará espacio en el espacio de direcciones de la memoria
virtual del proceso, no utilizará la memoria física adicional del sistema. La desventaja es
que debido al GOT, el acceso a direcciones globales (variables y funciones globales) es
mucho más complejo.
.balign 4
.globl myvar
myvar : .word 42 /* 42 as initial value */
.size myvar, .-myvar
La .sizedirectiva será necesaria para el caso de la biblioteca dinámica. Indica el tamaño de
un símbolo, en este caso myvar. Podríamos haber codificado el valor (4) pero aquí estamos
haciendo que el ensamblador lo calcule por nosotros. La expresión resta la dirección actual
(indicada por un punto .) con la dirección de myvar. Debido a la .worddirectiva intermedia,
estas dos direcciones están separadas por 4 bytes.
.text
.globl main
.balign 4
main:
ldr r0, addr_myvar /* r0 ← &myvar */
ldr r1, [r0] /* r1 ← *r0 */
add r1, r1, #1 /* r1 ← r1 + 1 */
str r1, [r0] /* *r0 ← r1 */
Biblioteca dinámica
Para generar una biblioteca dinámica, necesitamos decirle al enlazador que no queremos un
programa sino una biblioteca dinámica. En ELF, las bibliotecas dinámicas se denominan
objetos compartidos y, por lo tanto, su extensión .so. Para este propósito usaremos gcc, que
proporciona un indicador útil -sharedque se encarga de todos los indicadores que ld
necesitará para crear una biblioteca dinámica.
# dynamic library
as -o mylib.o mylib.s
gcc -shared -o [Link] mylib.o
Ahora queremos acceder desde nuestro programa a la variable myvarutilizando un acceso
independiente de la posición.
Recuerde, no podemos usar un mecanismo que fuerce la reubicación del código (es decir,
que se arreglen sus direcciones). Solo se puede arreglar el GOT (después de todo, no es un
código). La dirección de myvarestará en alguna entrada en el GOT. No sabemos cuál,
exactamente, esto es una preocupación del enlazador. Sin embargo, todavía necesitamos
obtener la dirección base del GOT primero.
Una peculiaridad de ARM es que leer el pcen una instrucción, nos da el valor
del pcdesplazamiento de 8 bytes. Entonces, es posible que tengamos que restar 8 a
lo r0anterior o simplemente asegurarnos de que la reubicación ya lo esté haciendo por
nosotros. El segundo enfoque es realmente mejor porque evita una instrucción.
ldr r0, offset_of_GOT /* r0 ← "offset-to-GOT" */
got_address: add r0, pc, r0 /* r0 ← pc + r0 */
...
offset_of_GOT: .word _GLOBAL_OFFSET_TABLE_ - (got_address + 8)
Y ahora r0tenemos la dirección absoluta del GOT. Pero queremos acceder myvar. Podemos
pedirle al enlazador estático que indique el uso del desplazamiento (en bytes) en el GOT
para un símbolo usando la sintaxis siguiente.
.word myvar(GOT)
Ahora tenemos todos los ingredientes necesarios para acceder myvarde forma independiente
al puesto.
1/* main.s */
[Link]
3
[Link]
[Link] main
6
[Link] 4
8
9main:
10 ldr r0, offset_of_GOT /* r0 ← offset-to-GOT
11 (respect to got_address)*/
12 got_address: add r0, pc, r0 /* r0 ← pc + r0
13 this is
14 r0 ← &GOT */
15 ldr r1, myvar_in_GOT /* r1 ← offset-of-myvar-inside-GOT */
16 add r0, r0, r1 /* r0 ← r0 + r1
17 this is
18 r0 ← &GOT + offset-of-myvar-inside-GOT */
19 ldr r0, [r0] /* r0 ← *r0
20 this is
21 r0 ← &myvar
22 */
23 ldr r1, [r0] /* r0 ← *r1 */
24 add r1, r1, #1 /* r1 ← r1 + 1 */
25 str r1, [r0] /* *r0 ← r1 */
26
27 mov r0, #0 /* end as usual */
28 bx lr
29
30offset_of_GOT: .word _GLOBAL_OFFSET_TABLE_ - (got_address + 8)
31myvar_in_GOT : .word myvar(GOT)
Podemos reemplazar la add(línea 16) y la ldr(línea 19) con un acceso a la memoria más
elaborado.
Thus, under lazy loading, the first time that we call a function it has to be loaded. Further
calls will use the previously loaded function. This is efficient but requires a bit more of
machinery. In ELF this is achieved by using an extra table called the Procedure Linkage
Table (PLT). There is an entry for each, potentially, used function by the program. These
entries are also replicated in the GOT. In contrast to the GOT, the PLT is code and we do
not want to modify it. Entries in the PLT are small sequences of instructions that just
branch to the entry in the GOT. The GOT entries for functions are initialized by the
dynamic linker with the address to an internal function of the dynamic linker which
retrieves the address of the function, updates the GOT with that address and branches to it.
Because the dynamic linker updated the GOT table, the next call through the PLT (that
recall simply branches to the GOT) will directly go to the function.
Uno puede preguntarse por qué no llamar directamente a la dirección en el GOT o por qué
utilizar un PLT. La razón es que el enlazador dinámico debe saber qué función queremos
cargar la primera vez, si llamamos directamente a la dirección en el GOT necesitamos idear
un mecanismo para poder decir qué función se debe cargar. Una forma podría ser inicializar
las entradas GOT para funciones en una tabla que prepara todo para que el cargador
dinámico sepa la función exacta que debe cargarse. ¡Pero esto es en la práctica equivalente
al PLT!
Todo en este punto parece demasiado complicado, pero la buena noticia es que es el
enlazador quien crea estas entradas PLT y se pueden usar como llamadas de función
regulares. No es necesario obtener la dirección de la entrada GOT y todo lo que tuvimos
que hacer para una variable (¡todavía tenemos que hacer esto si usaremos la dirección de la
función!). Siempre podríamos hacer eso, pero esto inflaría el código ya que cada llamada de
función requeriría una indexación compleja en la tabla GOT. Este mecanismo funciona
tanto para PIC como para no PIC, y es la razón por la que hemos podido llamar a las
funciones de la biblioteca C printfsin tener que preocuparnos si provienen de una biblioteca
dinámica (y lo hacen a menos que usemos -staticpara generar un ejecutable completamente
estático ) o no. Dicho esto, podemos usar explícitamente el sufijo@PLTpara indicar que
queremos llamar a una función a través del PLT. Esto es obligatorio para las llamadas
realizadas dentro de una biblioteca.
Ejemplo completo
Extendamos ahora nuestra biblioteca con una función que imprima el valor de myvar. Dado
que es código en la biblioteca debe ser código PIC: accesos a variables a través del GOT y
llamadas a funciones vía PLT. Nuestra función se llama myfun. Es bastante similar a lo que
hicimos en el main, excepto por el incremento.
/* mylib.s */
.data
.balign 4
.globl myvar
myvar : .word 42 /* global variable "myvar" */
.size myvar, .-myvar
.text
.balign 4
.globl myfun
myfun:
push {r4, lr} /* we are going to do a
call so keep lr, and also r4
for a 8-byte aligned stack */
ldr r0, offset_of_GOT /* r0 ← offset-to-GOT
(respect to got_address)*/
got_address: add r0, pc, r0 /* r0 ← pc + r0
this is
r0 ← &GOT */
ldr r1, myvar_in_GOT /* r1 ← offset-of-myvar-inside-GOT */
ldr r0, [r0, r1] /* r0 ← *(r0 + r1)
this is
r0 ← *(&GOT + offset-of-myvar-inside-GOT) */
ldr r1, [r0] /* r0 ← *r1 */
.text
.globl main
.balign 4
main:
push {r4, lr} /* we are going to do a
call so keep lr, and also r4
for a 8-byte aligned stack */
bl myfun@PLT /* call function in library */