Отслеживание двух разных индексов массива в сортировке вставки с приращением указателя по сравнению с индексированными режимами адресации? - PullRequest
Новая
       11

Отслеживание двух разных индексов массива в сортировке вставки с приращением указателя по сравнению с индексированными режимами адресации?

0 голосов
/ 06 июля 2018

Итак, чтобы научить себя циклам и условным выражениям, я пытался реализовать алгоритм сортировки вставок из Википедии : 

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

Я думаю, что переведен код для сборки, но он не работает. Я думаю, что причина проблемы, вероятно, заключается в индексации (в частности, в части A[j or j - something]), и все же я не могу ее исправить. Вот мой код: 

.386 
.model flat,stdcall
.stack 4096

ExitProcess proto,dwExitCode:dword

.data
arr DWORD 4,5,1,7


.code
main proc
mov esi, OFFSET arr
mov eax, 1 ; eax is i, i <- 1

L2:

    mov ebx, eax ; ebx is j, j <- i

    ; while j > 0
    INNERWHILE:
    cmp ebx, 0
    jle L3  

    ; and A[j-1] > A[j]
    mov ecx, [esi + 4*ebx] ; A[j]
    sub esi, 4
    cmp [esi + 4*ebx], ecx ;A[j-1] > A[j]
    jle L3

    ; swap A[j] and A[j-1]
    mov edx, [esi + 4*ebx] ; edx = A[j-1]
    add esi, 4
    mov ecx, [esi + 4*ebx] ; ecx = A[j]

    ; Begin Swap
    mov [esi + 4*ebx], edx ; A[j-1] <- A[j]
    sub esi, 4
    mov [esi + 4*ebx], ecx  ; A[j] <-  A[j-1]
    dec ebx
    jmp INNERWHILE
L3:
inc eax
cmp eax, LENGTHOF arr
jl L2
invoke ExitProcess,0
main ENDP
END main

Любая помощь приветствуется, мой уровень - новичок в x86, поэтому любые советы приветствуются.

Это точка, в которой я запутался: язык высокого уровня предполагает, что массив начинается с 0 и продолжается дальше. Однако A[j] != [esi], поскольку j не может быть = 0, поэтому я полностью застрял в части адресации на основе индекса.

1 Ответ

0 голосов
/ 06 июля 2018

Похоже, вы усложняете себе задачу, пытаясь использовать esi как A+i и ebx как j.

Легче всего использовать три разных регистра для A, i и j вместо попытки оптимизировать A+i в один регистр.

То есть A[i] это [esi + edi*4] и A[j] это [esi + ebx*4].

Это был бы прямой перевод этого псевдокода в asm.

Существуют оптимизации, которые вы можете выполнить позже, как только вы это заработаете, например, оптимизировать A+i и A+j в регистры, чтобы вы могли использовать [reg] режимы адресации вместо [reg+idx*4] режимы адресации.

И вы можете вообще не хранить A в регистре, а использовать его только в качестве операнда источника памяти для j>0, вместо этого делая cmp edx, OFFSET arr или cmp edx, [esp+0], если вы притворяетесь, что базовый адрес не ' t постоянную времени компиляции и поместите ее в стек.

А потом j = i становится mov edx, esi.

Возможно, вы захотите перевести псевдокод в C и посмотреть, что делают оптимизирующие компиляторы. (Напишите функцию сортировки, которая принимает указатель в качестве аргумента функции, чтобы компилятор не мог выполнять постоянное распространение константного массива и просто выдавать код, в котором хранится результат сортировки по константе: P) http://gcc.godbolt.org/ удобно для этого и см. также Как удалить «шум» из вывода сборки GCC / clang? .

...