Migueeeeeel Posted May 4, 2009 at 09:22 PM Report #261400 Posted May 4, 2009 at 09:22 PM Boas, eu tenho andado a tentar aprender MIPS, e para começar fiz um quicksort simples em C e estou a tentar converter-lo para MIPS. Mas estou a ter problemas, possivelmente variaveis trocadas no ciclo while do codigo em MIPS. Se alguém me poder ajudar a descobrir onde o programa (e eu 🙂 ) está a falhar fico agradecido. em C #include<stdio.h> void qsort(int[], int, int); int partition(int[], int, int); void swap(int[], int, int); main() { int a[] = {7,12,1,2,0,15,4,11,9}; int size = 8; printf("Array por Ordenar: "); int i; for(i=0;i<size+1;i++) printf("%d ",a[i]); qsort(a,0,size); printf("\n\nArray Ordenada: "); for(i=0;i<size+1;i++) printf("%d ",a[i]); printf("\n"); } void qsort(int a[], int z, int l){ if(z >= l) return; int index = partition(a,z,l); qsort(a,z,index-1); qsort(a,index+1,l); } int partition(int a[], int z, int l){ int pivot = a[z], i=z, index=z; swap(a, z, l); for(i = z; i < l; i++){ if(a[i] < pivot){ swap(a,i,index); index += 1; } } swap(a,l,index); return index; } void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } e em MIPS .data numbers: .word 3,5,7,8,9,0,11,2,5,7,8 size: .word 11 str: .asciiz " " str1: .asciiz "3 5 7 8 9 0 11 2 5 7 8\n" str2: .asciiz "\n" .text .globl main main: la $a0, numbers # $a0 = array move $a1, $zero # $a1 = 0 lw $a2, size # $a2 = size sub $a2,$a2,1 # size - 1 jal qsort # (array,0,n-1) # print the array la $a0,str1 # Print of str1, starting array, for comparison li $v0,4 syscall # print new sorted array la $t2,numbers lw $t4,size li $t3,0 for_print: bge $t3, $t4, exit_print # if test >= size go to exit_print sll $t1, $t3, 2 # $t1 = test*4 add $t1, $t1, $t2 # $t2 = numbers + test*4 lw $a0,0($t1) li $v0,1 # print of the element numbers[test] syscall la $a0,str # print newline li $v0,4 syscall addi $t3,$t3,1 # test = test + 1 j for_print exit_print: li $v0,10 # syscall to exit syscall qsort: # create stack frame and save vals addi $sp, $sp, -16 sw $ra, 0($sp) sw $s0, 12($sp) sw $s1, 8($sp) sw $s2, 4($sp) ### bge $a1,$a2,end_qsort_if # if(z >= l) return; #save contents in s registers #s0 = array, s1 = z, s2 = l # int index = partition(a,z,l); move $s0,$a0 move $s1,$a1 move $s2,$a2 jal partition move $s3,$v0 # store pivotPosition in $s3 sub $t0,$s3,1 # pivotPosition-1 = $t0 # qsort(a,z,index-1); move $a0,$s0 move $a1,$s1 move $a2,$t0 jal qsort # qsort(a,index+1,l); move $a0,$s0 addi $a1,$s3,1 move $a2,$s2 jal qsort end_qsort_if: # restore values lw $ra, 0($sp) lw $s0, 12($sp) lw $s1, 8($sp) lw $s2, 4($sp) addi $sp, $sp, 16 ### jr $ra #return # do some swapping, return "right" in $v0 # a0 = array, a1 = z, a2 = l partition: # create stack frame and save vals addi $sp, $sp, -24 sw $ra, 4($sp) sw $s0, 8($sp) sw $s1, 12($sp) sw $s2, 16($sp) sw $s3, 20($sp) sw $s4, 0($sp) ### move $s1, $a1 #s1 = z # pivot = a[z] move $s3,$s1 #s3 = pivot = a[z] sll $s3,$s1,2 add $s3,$s0,$s3 lw $s3, 0($s3) # i = z move $s4, $s1 # index = z move $s2,$s1 jal swap while: bge $t1,$a2,end_while # if i >= l, end while sll $t1, $a1, 2 # $t1 = i add $t1, $t1, $a0 # $t1=a+i*4 lw $t3, 0($t1) # $t0=a[i] #bge $t3, $t2,end_if # if i[i]] >= pivot slt $t0,$t3,$t2 # if a[i] < pivot beq $t0,$0,$end_if #move $a0,$s0 move $a1,$s1 move $a3,$a2 move $a2,$s2 jal swap add $s2, $s2, 1 # index ++ add $s4, $s4,1 j while end_if: add $s4, $s4,1 j while end_while: move $a0,$s0 move $a1,$a3 move $a2,$s2 jal swap move $v0,$s2 # return index # restore values lw $ra, 4($sp) lw $s0, 8($sp) lw $s1, 12($sp) lw $s2, 16($sp) lw $s3, 20($sp) lw $s4, 0($sp) addi $sp, $sp, 24 ### jr $ra swap: sll $t1, $a1, 2 # $t1 = i add $t1, $t1, $a0 # $t1=a+i*4 lw $t0, 0($t1) # $t0=a[i] sll $t2, $a2, 2 # $t2=j add $t2, $t2, $a0 # $t2=a+j*4 lw $t3, 0($t2) # $t3=a[j] sw $t3, 0($t1) # a[i]=$t3 sw $t0, 0($t2) # a[j]=$t0 jr $ra Obrigado desde já a quem poder ajudar.
Triton Posted May 4, 2009 at 09:26 PM Report #261404 Posted May 4, 2009 at 09:26 PM É muito código para estar a entender isso tudo... Uma sugestão: uma um debugger/simulador para ir seguindo o código e assim vês mais facilmente onde está o problema. <3 life
Migueeeeeel Posted May 5, 2009 at 11:11 AM Author Report #261517 Posted May 5, 2009 at 11:11 AM Antes de mais, obrigado pela resposta. Eu tenho andado a utilizar o SPIM, mas o programa não é muito intuitivo. Mas vou continuar a tentar, e se conseguir descobrir o problema posto aqui.
ozorio Posted July 10, 2009 at 03:09 AM Report #278469 Posted July 10, 2009 at 03:09 AM .data array: .word 6,5,-2,3,2,1 .text main: li $a0, 0 # carrega begin em $a0 para passar como parametro li $a1, 20 # carrega end em $a1 para passar como parametro li $a2, -1 li $a3, -1 jal quickSort # chama quickSort li $v0, 10 # system call for exit syscall # Exit! quickSort: .data end: .word 0 begin: .word 0 pivot: .word 0 left: .word 0 right: .word 0 .text #salva na pilha de execucao addiu $sp,$sp,-20 # Aloca espaço na pilha para 1 palavra (8 bytes) sw $a0, 0($sp) # salva begin sw $a1, 4($sp) # salva left sw $a2, 8($sp) # salva right sw $a3, 12($sp) # salva end sw $ra, 16($sp) # salva endereco da chamada #fim salvamento na pilha sw $a0, begin # guarda begin na memoria sw $a1, end # guarda end na memoria lw $s0, begin # $s0 = begin lw $s1, end # $s1 = end sub $t9, $s1, $s0 # $s9 = end - begin bgtz $t9, e # if(end - begin > 0) e j fim # else -> fim e: lw $s2, array($s0) # $s2 = array[begin] sw $s2, pivot # pivot = array[begin] addi $s3, $s0, 4 # left = begin + 1 sw $s3, left lw $s4, end # right = end sw $s4, right while: bge $s3, $s4, a # if(left >= right) a lw $s5, array($s3) # $s5 = array[left] ble $s5, $s2, incLeft # if(array[left] <= pivot) incLeft # else lw $s6, array($s4) # $s6 = array[right] lw $s5, array($s3) # $s5 = array[left] sw $s5, array($s4) # array[right] = array[left] sw $s6, array($s3) # array[left] = array[right] addi $s4, $s4, -4 # right-- sw $s4, right lw $s5, array($s3) # $s5 = array[left] lw $s6, array($s4) # $s6 = array[right] j while a: lw $s5, array($s3) # $s5 = array[left] lw $s6, array($s4) # $s6 = array[right] bgt $s5, $s2, decLeft # if(array[left] > pivot) decLeft c: lw $s7, array($s0) # $s7 = array[begin] lw $s5, array($s3) # $s5 = array[left] sw $s7, array($s3) # array[left] = array[begin] sw $s5, array($s0) # array[begin] = array[left] lw $s7, array($s0) # $s7 = array[begin] lw $s5, array($s3) # $s5 = array[left] #chama quickSort primeira parte lw $a0, begin # $a0 = begin primeira lw $a1, left # $a1 = left lw $a2, right # $a2 = right lw $a3, end # $a3 = end addi $a1, $a1, -4 # $a1 = left-1 addi $t0, $a1, 4 # $t0 = left jal quickSort # chama quickSort #fim recursao primeira parte sw $a0, begin # guarda begin na memoria sw $a1, left # guarda left na memoria sw $a2, right # guarda right na memoria sw $a3, end # guarda end na memoria #chama quickSort segunda parte lw $a0, right # $a0 = right segunda lw $a1, end # $a1 = end lw $a2, begin # $a2 = begin lw $a3, left # $a3 = left jal quickSort # chama quickSort #fim recursao segunda parte fim: lw $ra, 16($sp) # endereco lw $a3, 12($sp) # end lw $a2, 8($sp) # right lw $a1, 4($sp) # left lw $a0, 0($sp) # begin sw $zero, 16($sp) # endereco sw $zero, 12($sp) # end sw $zero, 8($sp) # right sw $zero, 4($sp) # left sw $zero, 0($sp) # begin addiu $sp, $sp, 20 # desaloca espaço na pilha para (20 bytes) jr $ra incLeft: addi $s3, $s3, 4 sw $s3, left j while decLeft: addi $s3, $s3, -4 sw $s3, left j c esse quicksort funciona fiz no Mars não se se vai adiantar pq já faz muito tempo
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now