Что не так с этой программой сортировки пузырьков сборки x86? - PullRequest
Новая
       14

Что не так с этой программой сортировки пузырьков сборки x86?

1 голос
/ 30 мая 2019

Мне нужно выяснить, почему ничего не происходит в этой программе.Программа получает целочисленный массив, содержащий 4,5,1,3,2, из отдельной программы на Си и возвращает ее отсортированной.

Я попытался изменить некоторые команды перехода, но ничего не помогло. 

.global myarray

.data
myarray:
    lea (%rdi),%r8      #load array to register
    mov %rsi,%r12       #load array size to register
    mov $0,%r10             #initialize index
sort:
    mov (%r8, %r10, 8), %rax    #store array[i] in rax
    inc %r10            #i++
    mov (%r8, %r10, 8), %rdx    #store array[i+1] in rdx
    cmp %rax, %rdx      #see if rdx is less than rax
    jle swap            #if rdx < rax, swap them
swap:
    cmp %r12, %r10      #check if still in array bounds
    je  check           #if we are at the end, check if sorted
    dec %r10            #i--
    mov %rdx, (%r8, %r10, 8)    #move array[i+1] into array[i]
    inc %r10            #i++
    mov %rax, (%r8, %r10, 8)    #move array[i] into array[i+1]
    jmp     check
check:
    mov $0, %r14        #temporary index in r14
    mov (%r8, %r10, 8), %eax    #temporarily store array[i] in eax
    inc %r14            #i++            
    mov (%r8, %r10, 8), %ebx    #temporarily store array[i+1] in ebx
    cmp %eax, %ebx      #check if ebx is less than eax
    jle sort            #if ebx < eax, swap
    cmp %r12, %r14      #check if still in array bounds
    ret

Ожидаемые результаты - отсортированный массив;1,2,3,4,5

1 Ответ

0 голосов
/ 30 мая 2019 
mov %rsi,%r12           #load array size to register
mov $0,%r10             #initialize index

В массиве из 5 элементов вы можете сравнить только 4 пары. Было бы удобно уменьшить %r12. В то же время у вас будет выход, когда в массиве есть только 1 элемент: 

mov %rsi,%r12             #load array size to register
dec %r12
jz  NothingToDo
mov $0,%r10               #initialize index

cmp %rax, %rdx          #see if rdx is less than rax
jle swap                #if rdx < rax, swap them
swap:

Если LessOrEqual, переход переходит к swap , но в противном случае код проваливается в swap . Это не имеет смысла!

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

sort:
    mov (%r8, %r10, 8), %rax    #store array[i] in rax
    inc %r10                    #i++
    mov (%r8, %r10, 8), %rdx    #store array[i+1] in rdx
    cmp %rdx, %rax
    jle NoSwap
    dec %r10                    #i--
    mov %rdx, (%r8, %r10, 8)    #move array[i+1] into array[i]
    inc %r10                    #i++
    mov %rax, (%r8, %r10, 8)    #move array[i] into array[i+1]
NoSwap:
    cmp %r12, %r10              #check if still in array bounds
    jb  sort

Этот код внутреннего цикла должен повторяться несколько раз, но каждый раз, когда вы понижаете предел в %r12. (*) 

jmp     check
check:

Это тоже бесполезно jmp! 

check:
mov $0, %r14        #temporary index in r14
mov (%r8, %r10, 8), %eax    #temporarily store array[i] in eax
inc %r14            #i++            
mov (%r8, %r10, 8), %ebx    #temporarily store array[i+1] in ebx
cmp %eax, %ebx      #check if ebx is less than eax
jle sort            #if ebx < eax, swap
cmp %r12, %r14      #check if still in array bounds

И эту часть кода нельзя спасти. То, что происходит здесь, за пределами понимания.

(*) 

    mov     %rdi,%r8
    mov     %rsi,%r12
    dec     %r12
    jz      NothingToDo
OuterLoop:
    mov     $0,%r10
    ...
    dec     %r12
    jnz     OuterLoop
NothingToDo:
    ret
...