1

Capítulo 7.

Direccionamiento y Estructuras de Datos. Una vez conocidos los mecanismos de direccionamiento de un procesador es útil visualizar cómo se pueden emplear para manipular arreglos y estructuras.

7.1 Arreglos. Se requiere una variable entera sin signo, denominada el índice del arreglo, generalmente se emplea un registro. Y una zona de datos, palabras normalmente consecutivas en la memoria para almacenar las componentes. Todas las componentes tienen igual tamaño, y si se asume que están almacenadas en forma contigua, se tendrá que si se conoce la dirección del primero, la dirección de la componente i, queda dada por: Dirección del primero + i * (tamaño de la componente) Si el tamaño de la componente, que es una constante, es un múltiplo de dos, la multiplicación puede efectuarse como corrimientos a la izquierda. Esto también asume que el primer índice es cero. Este modelo de representación de los arreglos en assembler, es el que usa el lenguaje C, que emplea el nombre del arreglo como un puntero a la primera componente. Y que permite accesar a una componente vía indirección, con la expresión a+i, que es la dirección de la componente i del arreglo a. Notar que en C, la aritmética de punteros calcula de acuerdo al tamaño, la correcta dirección de la componente; sea ésta de una, media o varias palabras. Debido a la fórmula anterior, ubicar una componente cualquiera del arreglo, toma el mismo tiempo (el que demora en efectuarse una multiplicación o corrimiento más la suma), por esta razón a esta estructura se la denomina ram (Modela la memoria externa del computador. Esto asumiendo que el número de las componentes es elevado, y que no pueden emplearse registros, para representar el arreglo). 7.1.1. Ejemplo de manipulación de arreglos. En lenguaje C. El siguiente segmento, en C, describe la manipulación mediante acceso vía índice: int a[ ] = {0,1,2,3,4,5,6}; int i = 0; Profesor Leopoldo Silva Bijit

18-07-2007

2

Estructuras de Computadores Digitales

int k = 0; void main(void) { i = 5; ........ k = a[i]; /* lectura de componente de arreglo */ ....... a[i] = k; /* escritura en componente de arreglo */ } Notar que la definición del arreglo, se efectúa con una inicialización vía conjunto de componentes. En este caso no es preciso establecer el tamaño del arreglo. Si se hubiera definido: int arreglo[3]; se crea espacio para tres componentes de tipo entero: arreglo[0], arreglo[1], arreglo[2]. El mismo segmento anterior puede describirse empleando manipulación mediante acceso vía puntero: int a[ ] = {0,1,2,3,4,5,6}; int i = 0; int k = 0; void main(void) { i = 5; ........ k = *(a+i); /* lectura de componente de arreglo */ ....... *(a+i) = k; /* escritura en componente de arreglo */ } En assembler. Se traslada a: .data a: i: k: .text .globl

.word 0,1,2,3,4,5,6 .word 0 .word 0 main

main: #inicia variable i, en zona estática, con constante 5. li $t3, 5 # t3=5 Macro que puede escribirse: ori $t3,$zero,5 la $t0, i # t0=&i t0 es un puntero. Apunta a variable i. sw $t3, 0($t0) # *t0=t3 Escribe en lo que apunta t0. #las dos instrucciones anteriores pueden escribirse con la macro: sw $t3, i($zero) #para direccionar a[i]. Profesor Leopoldo Silva Bijit

18-07-2007

Direccionamiento y estructuras de datos

3

#Primero se obtiene, en t2, el offset en bytes respecto al inicio. la $t0, i # t0 = &i lw $t0, 0($t0) # t0 = *t0 o también t0 = i sll $t2, $t0, 2 # t2 = i*4 # Luego se forma, en t2, la dirección de a[i] la $t1, a # t1 = &a addu $t2, $t2, $t1 # t2 = &(a[i] ) # Finalmente se deposita en t3 el contenido de a[i] lw $t3, 0($t2) # t3 = a[i] #Las tres instrucciones anteriores pueden escribirse con la macro: lw $t3, a($t2) # La asignación k=a[i] la $t4, k # t4 = &k sw $t3, 0($t4) # *t4 = t3 # Pueden ejecutarse otras instrucciones, ...... # En lo que sigue, se asume que se han modificado $t0 y $t2, o que se ha escrito en i # Para escribir componente (desde variable k) # Primero se deja el valor de la variable k en $t3. la $t4, k # t4 = &k lw $t3, 0($t4) # t3 = *t4 #Para direccionar a[i]: Primero se forma, en t2, offset en bytes. la $t0, i # t0 = &i sll $t2, $t0, 2 # t2 = i*4 # Luego se forma, en t2, la dirección de a[i] la $t1, a # t1 = &a addu $t2, $t2, $t1 # t2 = &(a[i] ) #Finalmente la asignación sw $t3, 0($t2) # *t2 = t3 jr

ra

Puede notarse en los comentarios el uso de los operadores * y &. Que básicamente permiten representar en forma abstracta el direccionamiento en base a registros. En operaciones intensivas con las componentes de un arreglo, conviene mantener el índice y la dirección de la componente a[i] en registros. Nótese que si las componentes fueran medias palabras, el corrimiento es sólo en una posición, para multiplicar por dos. En caso de bytes, no es necesario el paso de multiplicación, basta sumar el índice a la dirección inicial del arreglo. 7.1.2. Arreglos de caracteres. Strings. Un caso particular lo constituyen los arreglos de caracteres o strings. El cual es modelado, tanto en assembler como en C, mediante un puntero al primer carácter del string, y finalizando éste Profesor Leopoldo Silva Bijit

18-07-2007

4

Estructuras de Computadores Digitales

mediante un carácter nulo ( 0x00), que se coloca automáticamente. Por ejemplo: = "Este es un string"; define e inicia el string, terminado con el carácter nulo.

char *string

Veamos un ejemplo de diseño de función para la manipulación de strings: En lenguaje C. char *recortastring(register char *s, register int *inicial, register int *largo) { s = s + *inicial; *(s + *largo) = '\0'; return s; } Recorta “largo” carácteres de un string, desde la posición “inicial”; y devuelve un puntero al string resultante. Se le pasa como argumentos la dirección del string y punteros a variables enteras que contienen la posición inicial y el largo. Entonces, un ejemplo de invocación es: pchar = recortastring(arr,&i,&l); Donde pchar es un puntero a char, arr es un string, i y l enteros, todas las variables deben ser visibles, en el momento de invocar a la función. En assembler. Pasando los argumentos en registros tipo a, y retornando resultado en registro v0: ################################################################## # v0 = recortastring($a0, $a1, $a2) # # char *recortastring(register char *s, register int *inicial, register int *largo) # ####################################################################### recortastring: subu $sp,$sp,4 # push ra sw $ra,0($sp) move lw addu

$t0, $a0# t0 = s $t2, 0($a1) # t2 = *inicial $t0, $t0, $t2 # t0 = s + *inicial

lw addu sb

$t1, 0($a2) $t1, $t0, $t1 $zero, 0($t1)

# t1 = *largo # t1 = s + *largo # *t1 = '\0' Coloca el carácter nulo de fin de string.

move

$v0, $t0

# vo = nuevo inicio del string recortado. return(s)

lw addu jr

$ra, 0($sp) $sp, $sp, 4 $ra

# pop ra

Profesor Leopoldo Silva Bijit

# retorna

18-07-2007

Direccionamiento y estructuras de datos

5

7.1.3. Diferencia entre manipulación de arreglos vía índice y vía puntero. 7.1.3.1. Vía índices. Se tiene la siguiente función en C, que coloca en cero los elementos de un arreglo. void cleararray(int a[], int celdas) { int i; for( i = 0; i < celdas ; i++) a[i] = 0; } Se diseña la subrutina en assembler, con el siguiente empleo de registros: #argumentos $a0 = a, $a1 = celdas #local $t0 = i #temporales $t1 = &a[i], $t2, $t3 cleararray: add $t0, $zero, $zero #i=0 lazo: slt $t2, $t0, $a1 # t2 = 1 si i