Práctica Strings (Organización del Computador II)

De Cuba-Wiki
Revisión del 01:55 16 nov 2006 de 24.232.28.173 (discusión) (Restaure TOC)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

Ejercicio 1

Dado un string, armar una rutina que calcule la longitud.

  1. Comparar dos Strings, no hay observaciones sobre los dos strings, es decir no se detalla si son de igual longitud, ni si son vacíos, es decir chequear todos los casos.
  2. Generar una rutina que permita comprobar si en un string determinado, se encuentra incluida
    1. un carácter
    2. una palabra
    3. una frase

Item b

Puede utilizarse el codigo a continuacion correspondiente al subitem 3 para los dos anteriores.

Primero calcula la longitud de los dos strings, y despues recorre el contenedor para ver si encuentra la primera ocurrencia del buscado. Una vez encontrada, salva ese estado y empieza a compararlos. Devuelve 1 si lo encuentra, 0 si no.

global buscar

section .text

%define strA [ebp + 8]
%define strB [ebp + 12]

%define ptrA esi
%define ptrB edi

%define longA ebx
%define longB [ebp - 16]

;Busca el string A en el string B

buscar:
	;Inicio stack frame
	push ebp
	mov ebp, esp
	push esi
	push edi
	push ebx
	sub esp, 4
	
	;Calculo longitud de A
	cld
	mov edi, strA
	xor eax, eax
       xor ebx, ebx
	long1:
		inc ebx
		scasb
		jne long1
	dec ebx			;Guardo en ebx la longitud de A
 
 
	;Calculo longitud de B
	mov edi, strB
	xor ecx, ecx
	long2:
		inc ecx
		scasb
		jne long2
	dec ecx			;Guardo en ecx la longitud de B
	mov longB, ecx		;Y en la stack
 	
 
	;Busco primer caracter de A en B
 
	mov ptrB, strB	;edi apunta a B
	mov ptrA, strA	;esi apunta a A
	mov eax, [ptrA]	;Cargo en eax el 1er caracter de strA
 
iter:	repne scasb	;Busca en B hasta encontrar el 1er caracter de A o terminar B
 
	cmp ecx, 0x0	;Si termino de buscar en el string, salgo
	je false
 	
	cmp ecx, longA	;Comparo long de B y de A
	jl false	;Si longB<longA, no puede estar A contenido en B
  	
	mov edx, ptrB	;Guardo el estado del puntero a B
	mov longB, ecx	;Guardo la longitud restante de B
	mov ecx, longA	;Cargo en el contador la long de A
 	
	repe cmpsb	;Compara A y B mientras sean iguales
 	
	je true		;Si resultaron iguales, devuelvo true
 	
	mov ecx, longB	;Restauro registros con valores anteriores 
       dec ecx	        ;para seguir buscando
	mov ptrB, edx
	inc ptrB
	mov ptrA, strA
  	
	jmp iter
  	
 
false:	mov eax, 0
	jmp fin
 
true:	mov eax, 1
 	
fin:	;Retorno
	add esp, 4
	pop ebx
	pop edi
	pop esi
	pop ebp
	ret

Codigo C para testear el ASM

#include <stdio.h>
extern int buscar(char*, char*); //Devuelve 1 si encontro la cadena del primer  parametro en el segundo

int main() {

	char a[6] = {'a','a','a','b','c','\0'}; //Tira abc

	char b[14] = {'a','a','d','a','b','a','a','a','a','b','c','d','a','\0'};  //Contiene aaabc
	char c[14] = {'a','a','d','a','b','a','c','b','a','d','c','d','a','\0'};  //No contiene aaabc

	int resT= buscar(a,b);
	int resF= buscar(a,c);

	if (resT == 1) printf("\nOK: Encontro a en b");
	else printf("\nERR: No encontro a en b");

	if (resF == 0) printf("\nOK: No encontro a en c");
	else printf("\nERR: Encontro a en c");

	printf("\n\n");

	return 0;
}

Ejercicio 2

Generar una rutina que busque en un string la meseta mas corta y devuelva la posición donde comienza y su longitud. Se define como meseta a la repetición sucesiva de un mismo carácter: Ej: string:1111222222222444467777777 Mesetas: 1111, 222222222, 4444, 6, 7777777, siendo la meseta mas corta 6

global mese

section .text

%define ptrParam [ebp+8]  ;Puntero a string...
%define ptrDupla [ebp+12]

%define contAct ebx
%define cont	edx
%define ptr	edi
%define ptrMin	esi
%define charAct	al
 
mese:
	;InitFunction
	push ebp     		;Salvo la base de la pila anterior
	mov dword ebp, esp	;Pongo la nueva base en el tope de la pila	
	push esi	
	push edi
	push ebx

	cld			;Clear DF. Direccion de iteracion ->	
init:
	xor contAct, contAct
	xor cont, cont
	mov ptr, ptrParam
	mov byte al, [edi] 			;Me guardo en AL el primer caracter
	cmp charAct, 0		;Si el caracter actual es cero, salgo
	je fin	
	mov ptrMin, ptr		;Me guardo el inicio de la meseta actual (por ahora es la respuesta)
	xor ecx, ecx
cicloInit:
	inc contAct
	inc ptr	
	cmp byte charAct, [ptr]	
	je cicloInit		;Tambien saldre si esi es cero, dado que en AL	
;fin cicloInit	
	
	mov cont, contAct	;Esta es la longitud minima por el momento

cicloGroso:
	;Cuando llego aca, estoy en el inicio de la segunda meseta. 
	mov byte al, [edi]	;Cargo en AL el nuevo caracter
	cmp charAct, 0
	je fin			;Si el nuevo caracter es cero, termino la cadena, por ende, el analisis
	xor contAct, contAct	;Inicializo conAct en cero
	xor ecx, ecx		;Lo voy a usar para indexar

cicloMeseta:
	inc contAct		;Incremento el contador(dado que ya tengo 1 elemento de la meseta)	
	;if (contAct >= cont) pasarMesetaYCiclar
	cmp contAct, cont	;Comparo el contador actual con el general
	jge salirMeseta
	inc ecx
	cmp byte charAct, [ptr+ecx]
	je cicloMeseta	
;fin cicloMeseta

	;Si llego aca, termine una meseta y es mejor que la que tenia hasta ahora
	mov cont, contAct	;Reemplazo el mejor valor hasta el momento
	mov ptrMin, ptr		;Reemplazo la posicion de la meseta mas chica hasta el momento
	lea ptr, [ptr+ecx]	;Para el puntero en la proxima meseta
	jmp cicloGroso		;Itero
	
salirMeseta:
	;Quiero mover el puntero hasta la siguiente meseta, para eso tengo que comparar con el charAct hasta que sean
	;distintos e iterar.
	lea ptr, [ptr+ecx]	;Me paro hasta donde llegue...
	mov ecx, -1	;Inicializo ecx en -1 asi no llega a cero...
	repe scasb	;Repito hasta que el puntero apunte a un byte distinto
	dec ptr		;Esto es porque el repe se pasa uno...
	jmp cicloGroso
;fin cicloGroso	

fin:
	mov edi, ptrParam	
	sub esi, edi		;Queda en esi la posicion relativa al string de la meseta mas corta
	mov eax, ptrDupla	;Obtengo el puntero que apunta a la respuesta
	mov [eax], esi		;En dupla[0] queda la posicion
	mov [eax+4], cont	;En dupla[1] queda la longitud

	;EndFunction
	pop ebx
	pop edi
	pop esi
	pop ebp
 	ret

A continuación el archivo C para testearlo:

#include <stdio.h>

typedef int* dupla; //dupla[0]=posicion, dupla[1]=longitud

extern void mese(char*, dupla); //Devuelve 1 si encontro la cadena del primer parametro en el segundo

int main() {

	char a[6] = {'a','a','a','b','c','\0'}; //Tira abc

	char b[14] = {'a','a','d','a','b','a','a','a','a','b','c','d','a','\0'};  //Contiene aaabc
	char c[14] = {'a','a','d','a','b','a','c','b','a','d','c','d','a','\0'};  //No contiene aaabc

	char e[8] = {'a','a', 'a','d','d','a', 'a','\0'};

	dupla d;	

	mese(a, d);
	
	int pos= d[0];
	int length= d[1];

	printf("Posicion A: %d", pos); printf("\n");
	printf("Longitud A: %d", length); printf("\n");

	mese(b, d);
	
	pos= d[0];
	length= d[1];

	printf("Posicion B: %d", pos); printf("\n");
	printf("Longitud B: %d", length); printf("\n");

	mese(c, d);
	
	pos= d[0];
	length= d[1];

	printf("Posicion C: %d", pos); printf("\n");
	printf("Longitud C: %d", length); printf("\n");

	mese(e, d);
	
	pos= d[0];
	length= d[1];

	printf("Posicion E: %d", pos); printf("\n");
	printf("Longitud E: %d", length); printf("\n");

	printf("\n\n");

	return 0;
} 

Ejercicio 4

Dados dos strings, generar un tercero que tenga como resultado la intercalación de los dos strings, solo se puede realizar si los strings originales son de la misma long, se debe realizar dicha validación.

Este codigo devuelve como resultado un puntero a char que pide con malloc con el string intercalado por los dos recibidos como parametro, terminando con \0.

Calcula la longitud usando repne scasb contra 0 sobre un ecx negativo que luego convierte a la longitud real.

Usa movsb cambiando constantemente el esi para hacer la intercalacion, en lugar de hacer lodsb de dos registros distintos y stosb al destino.

global intercalar
extern malloc

section .text

%define strA		[ebp+8]
%define strB		[ebp+12]

intercalar:
	;Armo stack frame 
	push ebp
	mov ebp, esp
	push esi
	push edi
	push ebx

	;Calculo long de A y la guardo en ebx
	cld
	xor eax, eax
	mov edi, strA
	mov ecx, -1
	repne scasb
	neg ecx
	sub ecx, 2
	mov ebx, ecx

	;Calculo long de B y la guardo en ecx
	mov edi, strB
	mov ecx, -1
	repne scasb
	neg ecx
	sub ecx, 2

 	;Comparo longitudes
	cmp ebx, ecx
	jne false

	;Si son iguales, calculo cuanto espacio voy a necesitar para el resultado y lo pido
	mov esi, ecx
	shl ebx, 1
 	inc ebx
 	push ebx
 	call malloc
 	add esp, 4
 	
	;Preparo registros
	mov ecx, esi	;ecx= longA = longB
	dec ebx		;ebx= 2*long
	mov edi, eax	;edi apunta al destino
	mov eax, strA	;eax apunta al string A
	mov edx, strB	;edx apunta al string B

	;Intercalo
iter:	mov esi, eax
 	movsb
 	inc eax
	mov esi, edx
	movsb
	inc edx
	loop iter

	;Cierro el string
	xor eax, eax
	stosb
	
	;Calculo q dir tengo q devolver
 	mov eax, edi
	sub eax, ebx
	dec eax
	jmp fin
 
false:	mov eax, 0

fin:	;Retorno
	pop ebx
	pop edi
	pop esi
	pop ebp
	ret 

Este main.c permite testear el codigo asm anterior (libera la memoria que pidio y todo).

#include <stdio.h>
//Retorna el puntero al array de chars que resulta de intercalar los anteriores
//Si no coincidieron las longitudes, devuelve null
extern char* intercalar(char*, char*); 

int main() { 

	char e[5] = {'s','h','r','t','\0'}; 

	char a[7] = {'H','l',' ','u','d','!','\0'}; 
       char b[7] = {'o','a','M','n','o','!','\0'}; 

	char res[13] = {'H','o','l','a',' ','M','u','n','d','o','!','!','\0'};

	char* res1= intercalar(a,b);
	char* res2= intercalar(a,e);

	int i= 0;
	short c= 1;

	if (res1 != 0) {
		printf("OK: Las longitudes de A y B coinciden\n");
		while (i<13) {
			if (i<12) printf("%c", res1[i]);
			c= c && (res1[i] == res[i]);
			i++;
		}
		printf("\n");
		if (c != 0) printf("OK: Intercalo bien\n");
		else printf("ERR: Intercalo mal\n");
	}
	else {
		printf("ERR: Las longitudes de A y B no coinciden\n");
	} 

	if (res2 == 0) printf("OK: Las longitudes de A y E no coinciden\n");
	else printf("ERR: Las longitudes de A y E coinciden\n"); 

	if (res1 !=0) free(res1);

	return 0;
}

Todos los ejercicios

No están comentados, pero quizás a alguien le ayude.

section .text

global _length
global _compare
global _inString
global _mesetaMasCorta
global _reemplazar
global _intercalar

extern _malloc

; int length(char *str)
_length:
     push ebp
     mov ebp, esp
     push edi

     xor al, al
     mov edi, [ebp + 8]
     mov ecx, -1
     cld
     repne scasb
     add ecx, 2
     neg ecx
     mov eax, ecx

     pop edi
     pop ebp
     ret

; int compare(char *a, char *b)
_compare:
     push ebp
     mov ebp, esp
     push esi
     push edi
     push ebx

     push dword [ebp + 8]
     call _length
     pop esi
     mov ebx, eax

     push dword [ebp + 12]
     call _length
     pop edi
     mov ecx, eax

     cmp ebx, ecx
     jne notEqual
     cld
ciclo2:
     cmp ecx, 0
     je equal
     cmpsb
     jne notEqual
     dec ecx
     jnz ciclo2
equal:
     mov eax, 1
     jmp fin2

notEqual:
     xor eax, eax

fin2:
     pop ebx
     pop edi
     pop esi
     pop ebp
     ret

; int inString(char *str1, char *str2)
_inString:
   push ebp
   mov ebp, esp
   push esi
   push edi
   push ebx
   push edx

   push dword [ebp + 8]
   call _length
   pop edi
   mov ecx, eax
   cld

ciclo3:
   mov esi, [ebp + 12]
   mov al, [esi]

   repne scasb

   cmp ecx, 0
   je noEsta

   inc esi
   push esi
   call _length
   add esp, 4
   mov ebx, eax

   cmp ecx, ebx
   jl noEsta

   mov edx, edi
   xchg ecx, ebx
   repe cmpsb

   jz esta

   mov ecx, ebx
   mov edi, edx
   jmp ciclo3

esta:
   mov eax, 1
   jmp fin3

noEsta:
   xor eax, eax

fin3:
   pop edx
   pop ebx
   pop edi
   pop esi
   pop ebp
   ret

; char *mesetaMasCorta(char *str, int *len)
_mesetaMasCorta:
   push ebp
   mov ebp, esp
   push edi
   push ebx
   push edx
   push esi

   mov edi, [ebp + 8]
   push edi
   call _length
   add esp, 4
   mov ecx, eax

   mov edx, [ebp + 12]
   mov [edx], eax
   cld

ciclo4:
   mov al, [edi]
   cmp al, 0
   je noHay

   mov ebx, edi
   inc edi
   repe scasb

   mov eax, edi
   sub eax, ebx
   dec eax
   cmp eax, [edx]
   jge seguir1
   mov [edx], eax
   mov esi, ebx
seguir1:
   dec edi
   cmp ecx, 0
   jne ciclo4
   mov eax, esi
   jmp fin4

noHay:
   xor eax, eax
   mov [edx], eax

fin4:
   pop esi
   pop edx
   pop ebx
   pop edi
   pop ebp
   ret

; void reemplazar(char *str)
_reemplazar:
   push ebp
   mov ebp, esp
   push esi

   mov esi, [ebp + 8]
   push esi
   call _length
   add esp, 4
   mov ecx, eax
   cld

ciclo5:
   lodsb
   cmp al, 'A'
   je caso1
   cmp al, '/'
   je caso2
   cmp al, '*'
   je caso3
   cmp al, ';'
   je caso4
   cmp al, '{'
   je caso5
   cmp al, '}'
   je caso6

seguir2:
   loop ciclo5
   jmp fin5

caso1:
   mov byte [esi - 1], 'a'
   jmp seguir2

caso2:
   mov byte [esi - 1], '-'
   jmp seguir2

caso3:
   mov byte [esi - 1], ':'
   jmp seguir2

caso4:
   mov byte [esi - 1], ','
   jmp seguir2

caso5:
   mov byte [esi - 1], '('
   jmp seguir2

caso6:
   mov byte [esi - 1], ')'
   jmp seguir2

fin5:
   pop esi
   pop ebp
   ret

; char *intercalar(char *str1, char *str2)
_intercalar:
   push ebp
   mov ebp, esp
   push esi
   push edi
   push ebx

   mov esi, [ebp + 8]
   push esi
   call _length
   add esp, 4
   mov ebx, eax

   mov edi, [ebp + 12]
   push edi
   call _length
   add esp, 4

   cmp eax, ebx
   jne salir

   shl eax, 1
   inc eax
   push eax
   call _malloc
   add esp, 4
   mov ecx, ebx
   mov ebx, eax
   xchg edi, ebx

   cld
   cmp ecx, 0
   je fin6

ciclo6:
   movsb
   xchg esi, ebx
   movsb
   xchg esi, ebx
   loop ciclo6

   mov byte [edi], 0
   jmp fin6

salir:
   xor eax, eax

fin6:
   pop ebx
   pop edi
   pop esi
   pop ebp
   ret

Código C para probar las funciones:

#include <stdio.h>
#include <stdlib.h>

extern int length(char *str);
extern int compare(char *a, char *b);
extern int inString(char *str1, char *str2);
extern char *mesetaMasCorta(char *str, int *len);
extern void reemplazar(char *str);
extern char *intercalar(char *str1, char *str2);

int main()
{
   char str1[] = "2hholas giles3";
   char str2[] = "holas giles";
   char str3[] = "111122222222244446777777788";
   int len = 0;
   char *meseta = mesetaMasCorta(str3, &len);
   char str4[] = "A/*;{}chau";
   char str5[] = "holaquetal";
   char *str6 = intercalar(str4, str5);

   printf("Longitud: %d\n", length(str1));
   printf("Comparacion: %d\n", compare(str1, str2));
   printf("En string: %d\n", inString(str1, str2));
   printf("Longitud meseta mas corta: %d, %s\n", len, meseta);
   reemplazar(str4);
   printf("Reemplazar: %s\n", str4);
   printf("Intercalar: %s\n", str6);
   free(str6);

   system("pause");
   return 0;
}