Practico 11 Ejercicio 2

Practico 11 Ejercicio 2

de Matias Alejandro De Horta Roldan -
Número de respuestas: 6
Esta bien resuelto en assambler de la siguiente manera?
buscar PROC
CMP AX ES:[BX]
JE igual
JL menor
JG mayor
else:
MOV  CL, 0
JMP fin
igual:
MOV CL, 1
JMP fin
menor:
CMP ptr  byte ES:[BX], 0
JE else
PUSH BX
MOV ptr byte BX ES:[BX + 2]
CALL buscar
POP BX
JMP fin 
mayor:
CMP ptr  byte ES:[BX], 0
JE else
PUSH BX
MOV ptr byte BX ES:[BX + 3]
CALL buscar
POP BX
JMP fin
fin:
RET
buscar ENDP

Siendo el codigo en alto nivel el siguiente
bool buscar(int N; byte i)
{
if(arbol[i].dato == N)
 return true
else if (arbol[i].dato < N) && (arbol[i].izq != 0)
 return buscar(N, arbol[i].izq)
else if (arbol[i].dato > N) && (arbol[i].der != 0)
 return buscar(N, arbol[i].der)
else
 return 0;
}

Tengo dudas con las directivas byte ptr, al hacer x ejemplo MOV ptr byte BX ES:[BX + 2] Carga en BH 0x00 y en BL el byte almacenado en memoria?, Tambien se puede hacer MOV incluyendo a BX como registro para almacenar y tambien para referenciar indirectamente a memoria a cargar en la misma instruccion?
Gracias!
En respuesta a Matias Alejandro De Horta Roldan

Re: Practico 11 Ejercicio 2

de Gonzalo Tejera -
Hola. No es un árbol binario de búsqueda por lo que tenes que buscar en ambas ramas el elemento.

Está mal el ptr cuando traes a un registro, como ya se discutió en otro hilo, cuando accedes a memoria y el otro operando es memoria el tipo del puntero queda determina por el tamaño del registro.

Sí, podés usar BX como destino y para formar la dirección de memoria en la misma instrucción.

Saludos, Gonzalo 
En respuesta a Gonzalo Tejera

Re: Practico 11 Ejercicio 2

de Maria Valentina Da Silva De Souza -
Hola yo tengo las siguientes dudas respecto a este ejercicio:
1) Dice que BX es el puntero al árbol o subárbol,esto significa que BX vendria a ser como el indice del array arbol que me permite acceder a cada nodo haciendo [BX]?
2) Es correcto hacer SHL BX,2? Vi en la cartilla que el segundo operando debia ser 1 o CL. Por eso me entro la duda.
Hice mi solución asumienddo que 1) y 2) eran correctos, aca la planteo:
Buscar proc

cmp bx,0
je NO_ENCONTRE
shl bx,2
cmp es:[bx],ax
je ENCONTRE

push bx
mov bx, byte ptr es:[bx+2] 
call Buscar ;{ llamo con el indice izquierdo}
pop bx
cmp cl,1
je ENCONTRE
push bx
mov bx,byte ptr es:[bx+3]
call Buscar;{ llamo con el indice derecho}
pop bx
cmp cl,1
je ENCONTRE

NO_ENCONTRE: 
mov cl,0
jmp FIN
ENCONTRE:
mov cl,1
FIN:
ret
Buscar endp

Ahora tengo duda con la parte b) que pedia calcular el tamaño minimo que debe tener el stack para que la función pueda ser ejecutada en todos los casos, cualquiera sea el árbol.
Entonces el peor caso se da cuando el árbol es una lista y el elemento no está en el árbol.
Si f(n) es el tamaño del stack necesario para un árbol con n nodos en las condiciones de peor caso
f(0) = 2 bytes (2 del IP)
f(n) = 4 + f(n-1) ( 2 del IP, 2 de bx más lo que consuma f(n-1))
Expandiendo la recurencia obtuve f(n) = 4*n +2, estaria bien asi?
Saludos.

En respuesta a Maria Valentina Da Silva De Souza

Re: Practico 11 Ejercicio 2

de Gonzalo Tejera -
Hola. 

1-No, si dice puntero es una dirección de memoria, puede ser segmentada o absoluta, y en el caso de segmentada puede asumir un segmento fijo y pasar solo el desplazamiento.

2-No, solo se le puede pasar el inmediato. O haces dos instrucciones de uno o cargas previamente CL.

Saludos, Gonzalo
En respuesta a Gonzalo Tejera

Re: Practico 11 Ejercicio 2

de Maria Valentina Da Silva De Souza -
1) En este caso supongo que es segmentado porque dice que el árbol esta cargado en memoria como un array de nodos a partir de la posición 0 del ES.
a)BX vendria hacer como el desplazamiento dentro de ES?
Entonces nose si esta bien el código que hice porque yo asumi que BX era como el indice.
b)Si yo hago [BX] estoy accediendo al primer dato del arreglo osea a arbol[0].dato no?
c)Si yo hago mov ax,[bx] me va a cargar en ax la parte baja y alta del dato no?

cmp bx,0 ; esto nose si esta bien?
je NO_ENCONTRE
shl bx,2
cmp es:[bx],ax
je ENCONTRE
Y despues invocaba con el indice izq o derecho segun fuera el caso.

2) Con  hacer dos intrucciones de uno te referis a en vez de hacer shl bx,2 haga shl bx,1 y luego shl bx,1.

Asi me queda el código con esto que hice:
cmp bx,0
je NO_ENCONTRE
shl bx,1
shl bx,1
cmp es:[bx],ax
je ENCONTRE

push bx
mov bx, byte ptr es:[bx+2] 
call Buscar ;{ llamo con el indice izquierdo}
pop bx
cmp cl,1
je ENCONTRE
push bx
mov bx,byte ptr es:[bx+3]
call Buscar;{ llamo con el indice derecho}
pop bx
cmp cl,1
je ENCONTRE

NO_ENCONTRE: 
mov cl,0
jmp FIN
ENCONTRE:
mov cl,1
FIN:
ret
Buscar endp
En respuesta a Maria Valentina Da Silva De Souza

Re: Practico 11 Ejercicio 2

de Gonzalo Tejera -
1a. Sí, es un desplazamiento, si asumiste que es un indice está mal el acceso a la estructura.
1b. Sí.
1c. Sí.
1d. está bien comparar BX con cero, por qué te surge esa duda?

2. Sí, a esas dos intrucciones me refiero.

Saludos, Gonzalo
En respuesta a Gonzalo Tejera

Re: Practico 11 Ejercicio 2

de Maria Valentina Da Silva De Souza -

En alto nivel yo hice asi la función:
void Buscar (int elem,int i)
{ if (i==0)
         return false;
  else
  {     if (elem==arbol[i].dato)
                         return 1;
        esle return (Buscar(elem,arbol[i].hijoIzq)||Buscar(elem,arbol[i].hijoDer));
   }
}
En la letra dice el árbol esta cargado en memoria en la posición 0 del ES.Esto que me esta queriendo decir que BX inicialmente es cero?

Me surgue la duda con comparar con cero, porque como tu me dijiste BX no contiene el indice sino una dirección, y yo lo que quise hacer fue como emular el comportamiento de la función en alto nivel a assembler. "El if (i==0)".
Osea me surge la duda en la primera invocación a la función, porque en las demás invocaciones dejo en BX el contenido de hijoIzq y hijoDer, que en alto nivel son indices en el arreglo. De ahi mi confusión con los indices.
Pero en bajo nivel hijoIzq y hijoDer contienen las direcciones de memoria donde esta el nodo hijo izquierdo del arbol y el nodo hijo derecho del arbol no?
Nose si se entiende mi confusión.
Saludos.