В чем проблема с этой быстрой сортировкой в ​​MIPS? - PullRequest
Новая
       16

В чем проблема с этой быстрой сортировкой в ​​MIPS?

0 голосов
/ 14 ноября 2018

Это код C, который я использую для быстрой сортировки в MIPS, в редакторе Mars у меня возникают проблемы при запуске этого кода 

#include <stdio.h>

void QuickSort(int *array, int first, int last){
    int q;
    if (first<last){
        int value = array[last];
        int i = first-1;
        int tmp;
        int j = first;
        while(j<=last){
            if (array[j] <= value) {
              i++;
              tmp = array[i];
              array[i] = array[j];
              array[j] = tmp;
            }
          j++;
       }
       q = i;
       QuickSort(array,first,q-1);
       QuickSort(array,q+1,last);
    }
}

И это мой перевод MIPS,я получаю бесконечный цикл 

.data
numArray: 30, 15, 11, 40, 75, 80, 70, 60
first: 0
last: 7
    .text
main:
        la $a0, numArray
        lw $a1, first
        lw $a2, last
        jal quick_sort
        li $v0, 10
        syscall

quick_sort:
        subi $sp, $sp, 4        #reserving memory in the stack
        sw $ra, 4($sp)          #storing the return adress in the stack
        xor $t0, $t0, $t0       #int q
        bge $a1, $a2, label1    #if (first<last)
        sll $t1, $a2, 2         #int value = array[last];
        add $t1, $t1, $a0       #callculating array[last] in $t1
        lw $t1, 0($t1)          #array[last] = array direction + 4 * last
        or $t2, $t1, $zero      #$t2 will be value
        subi $t3, $a1, 1        #int i = first-1;
        xor $t4, $t4, $t4       #int tmp
        or $t5, $a1, $zero      #int j=first
        j label2                #while(j<=last)
    label3: sll $t6, $a2, 2     #calculating array[j] adress
        add $t6, $t6, $a0
        lw $t7, 0($t6)          #calculating array[j] value
        bgt $t7, $t1, label4    #if (array[j] <= value)
        addi $t3, $t3, 1        #i++
        sll $s0, $t3, 2         #calculating array[i] adress
        add $s0, $s0, $a0   
        lw $s1, 0($s0)          #calculating array[i] value
        or $t4, $s1, $zero      #tmp = array[i]
        sw $t7, 0($s0)          #array[i] = array[j];
        sw $t4, 0($t6)          #array[j] = tmp;
    label4: addi $t5, $t5, 1    #end if; j++
    label2: ble $t5, $a2, label3    #while condition
        or $t0, $t3, $zero      #q = i
        lw $a1, first           #first value on the second parameter
        subi $a2, $t0, 1        #q-1
        jal quick_sort          #QuickSort(array,first,q-1)
        addi $a1, $t0, 1        #q+1
        lw $a2, last            #last value on the third parameter
        jal quick_sort          #QuickSort(array,q+1,last);
    label1: lw $ra, 4($sp)      #Recovering the return address from the stack 
        addi $sp, $sp, 4        #releasing memory
        jr $ra                  #going to the return address

Может быть, мне нужно сохранить что-то еще в стеке или что-то, что мне не хватает, спасибо за вашу помощь, все, что вы видите там странным, пожалуйста, дайте мне знать, чтобы проверить это.

1 Ответ

0 голосов
/ 17 ноября 2018

РЕДАКТИРОВАТЬ:
Как указал Минн в комментарии, я пропустил две следующие строки: 

sll $t1, $a2, 2         #int value = array[last];

Таким образом, пока эта строка не соответствует комментарию вэто, загрузка значения кажется правильной.

END EDIT

Я не знаком с этой конкретной сборкой, но проблема, кажется, в том, что известно как «регистрация дубликатов» :

Согласно документации 1018 * jal хранит только обратный адрес, но не сохраняет ни один из регистров. 

    lw $a1, first           #first value on the second parameter
    subi $a2, $t0, 1        #q-1
    jal quick_sort          #QuickSort(array,first,q-1)
    addi $a1, $t0, 1        #q+1
    lw $a2, last            #last value on the third parameter
    jal quick_sort

Вы используете $t0 в качестве q локальной переменной, но никогда не сохраняете ее в стеке.

После первого вызова jal quick_sort #QuickSort(array,first,q-1) значение $ t0 будет другим, но вы его используетесразу в строке addi $a1, $t0, 1 #q+1, как если бы она никогда не менялась, а затем передать результат во второй вызов QuickSort.

Эквивалентом этой ошибки в C было бы сделать q глобальным и добавить q = 0; в начале функции.

Вы должны помнить, что при работепри сборке и использовании регистров для локальных переменных вы должны сохранить их состояние в стеке перед вызовом любой другой функции из вашей текущей функции, иначе вы потеряете состояние и ваш код не будет работать должным образом!

Если честноЯ впервые вижу именно этот язык ассемблера, поэтому могут быть и другие ошибки, которые я пропустил, но они наиболее очевидны, поэтому их было легко обнаружить.

...