MergeSort em Assembly Faiska

Fiz um trabalho interessante aqui na universidade para a matéria de Assembly e acho interessante publicar. Foi pedido que fizessemos um MergeSort em Assembly do processador Faiska. Acredito que esse meu código possa servir de base para que se faça outros MergeSort para outras arquiteturas.

 

; Programa lab02
; Autor : Alexandre Tolstenko Nogueira
; Lab 07: MergeSort

;// Funçao em java
;void merge(int a[], int low, int high){
;  if (low == high)
;    return;
;  int length = high-low+1;
;  int pivot = (low+high)/2;
;  merge(a, low, pivot);
;  merge(a, pivot+1, high);
;  int working[] = new int[lenght];
;  for(int i = 0; i< lenght; i++)
;    working[i] = a[low+1];
;  int m1 = 0;
;  int m2 = pivot-low+1;
;  for(int i = 0; i< length; i++){
;    if(m2 <= high-low)
;      if(m1 <= pivot-low)
;	if(working[m1] > working[m2])
;	  a[i+low] = working[m2++];
;	else
;	  a[i+low] = working[m1++];
;      else
;        a[i+low] = working[m2++];
;  }
;  return;
;}

; algumas constantes
tamanho:    ds      4h                              ; posição 0000h tamanho do vetor
vetor:	ds	4h                              ; posicao 0004h vetor a ser ordenado

org 100h

Comeco:

set 	r0, 	vetor
ld 	r1,	tamanho
add	r1, 	r0
sub	r1,	1

; =================================================================== ;
; r0 -> ponteiro p inicio do vetor                                    ;
; r1 -> ponteiro p final do vetor (aponta para um elemento invalido)  ;
; r2 -> é a média do inicio e fim do (sub)vetor                       ;
; =================================================================== ;

push 	r0 		; r0 -> ponteiro p inicio do vetor
push 	r1 		; r1 -> ponteiro p final do vetor
call 	MERGE
add 	sp,	8 	; arruma a pilha

jmp FIM

MERGE:
ld 	r0,	(sp+8) 	; r0 -> ponteiro p inicio do vetor
ld 	r1,	(sp+4) 	; r1 -> ponteiro p final do vetor

cmp 	r0, 	r1 	; compara o inicio e fim do vetor
jnz	ali		; se forem iguais, retorna
ret

ali:
;media
ld 	r1,	(sp+4) 	; r1 -> recarrega o ponteiro p final do vetor
ld 	r0,	(sp+8) 	; r0 -> ponteiro p inicio do vetor
mov 	r2, 	r0	; carrega o apontador do inicio do subvetor
add 	r2,	r1	; soma no temporario o fim do subvetor
shr 	r2, 	01h	; faz a media

; merge(pos_inicial, pos_metade)
; passa os parametros para a pilha
push 	r0		; r0 -> ponteiro p inicio do vetor
push 	r2		; r2 -> indice medio do vetor maior(final do primeiro subvetor)
call 	MERGE
add 	sp, 	8 	; arruma a pilha

; merge(pos_metade + 1, pos_final)
; passa os parametros para a pilha

;media
ld 	r1,	(sp+4) 	; r1 -> recarrega o ponteiro p final do vetor
ld 	r0,	(sp+8) 	; r0 -> ponteiro p inicio do vetor
mov 	r2, 	r0	; carrega o apontador do inicio do subvetor
add 	r2,	r1	; soma no temporario o fim do subvetor
shr 	r2, 	01h	; faz a media
add	r2,	01h

push	r2        ; inicio
push	r1        ; fim
call	MERGE
add	sp, 	8 	; arruma a pilha

; Funcao intercala

;  int m1 = 0;
;  int m2 = pivot-low+1;
;  for(int i = 0; i< length; i++){
;    if(m2 <= high-low)
;      if(m1 <= pivot-low)
;	if(working[m1] > working[m2])
;	  a[i+low] = working[m2++];
;	else
;	  a[i+low] = working[m1++];
;      else
;        a[i+low] = working[m2++];
;  }

; copio o dois subvetores para a memoria auxiliar e arrumo eles

; =============================================================== ;
; r0 -> ponteiro p o inicio do primeiro subvetor                  ;
; r1 -> ponteiro p o fim do primeiro subvetor                     ;
; r2 -> ponteiro p o inicio do segundo subvetor                   ;
; r3 ->	ponteiro p o final do segundo subvetor                    ;
; r4 -> Ponteiro para o aux                                       ;
; r5 -> Conteudo de r0                                            ;
; r6 -> Conteudo de r2                                            ;
; r7 -> Contador (Tamanho)                                        ;
; =============================================================== ;

; inicializo os ponteiros
ld	r0,	(sp+8)	; r0 -> ponteiro p inicio do primeiro subvetor
ld	r3,	(sp+4)	; r3 -> ponteiro p final do segundo subvetor
mov	r1,	r0	; carrega o apontador do inicio do vetor
add	r1,	r3	; soma no temporario o fim do vetor
shr	r1,	01h	; faz a media que vai ser o fim do primeiro subvetor
mov	r2,	r1	; carrega a media anterior
add	r2,	01h	; soma um e agora o r2 é inicio do segundo subvetor
set	r4,	aux	; inicializa o r4
mov	r7, r3	; pega o ponteiro final para calcular o tamanho do vetor
sub	r7,	r0	; descobre o tamanho
add	r7,	01h	; arruma o tamnho pois eh o indice maior - indice menor + 1

; =========== Lengenda ========== ;
; F -> Fim do...                  ;
; C -> Continua o... (nao eh fim) ;
; 1 -> Primeiro subvetor          ;
; 2 -> Segundo subvetor           ;
; =============================== ;

; Desculpe o tanto de jmps, mas foi pq nao encontrei outra maneira de testar o fim. Sao dois if um dentro do outro

CopiaOrdendando:
; testa os casos de termino
cmp	r0, 	r1	; compara para saber se terminou o primeiro subvetor
ja F1

C1:
cmp	r2,	r3	; compara para saber se terminou o ultimo subvetor
ja	C1F2
jmp	C1C2

F1:
cmp	r2,	r3	; compara para saber se terminou o ultimo subvetor
ja	F1F2
jmp	F1C2

; Caso onde ambos nao chegaram ao fim
C1C2:
ldb 	r5, 	(r0)	; capturo o valor do ponteiro do primeiro subvetor
ldb	r6,	(r2)	; capturo o valor do ponteiro do segundo subvetor
cmp	r5,	r6	; comparo
jl	CopiaDaEsq
jmp	CopiaDaDir

; caso onde copia o resto do primeiro vetor para o aux
C1F2:
ldb   r5,   (r0)  ; capturo o conteudo do ponteiro para o primeiro subvetor
jmp CopiaDaEsq

; caso onde acabou o loop
F1F2:
jmp FimOrdena

; caso onde copia o resto do segundo vetor para o aux
F1C2:
ldb r6, (r2)  ; capturo o conteudo do ponteiro para o segundo subvetor
jmp CopiaDaDir

CopiaDaEsq:
stb	(r4),	r5	; gravo no aux
add	r0,	01h	; atualizo o ponteiro para o primeiro subvetor
add	r4,	01h	; atualizo o ponteiro para o segundo subvetor
jmp CopiaOrdendando

CopiaDaDir:
stb	(r4),	r6	; gravo no aux
add	r2,	01h	; atualizo o ponteiro para o primeiro subvetor
add	r4,	01h	; atualizo o ponteiro para o segundo subvetor
jmp CopiaOrdendando

FimOrdena:
ldb	r0,	(sp+8)	; r0 -> ponteiro p inicio do primeiro subvetor
set	r4,	aux	; restauro meu r4 para o inicio do vetor auxiliar

Devolve:
ldb	r5,	(r4)	; jogo num temporario o conteudo do ponteiro do aux
stb	(r0),	r5	; gravo de volta o conteudo no vetor original
add	r4,	01h	; anda no vetor aux
add	r0,	01h	; anda no vetor original
sub	r7,	01h	; atualiza o contador
jnz 	Devolve

ret

FIM:
hlt

aux: ds 	100h 	; vetor auxiliar
%d blogueiros gostam disto: