Быстрая сортировка на ассемблере для x86 (MASM о)


Моя задача была в реализации быстрой сортировки в сборе с псевдокода.

;*******************************************************************************
; This program implements the Quick Sort algorithm and sorts an array
;
; Author: William 
; Date: 4/6/18

                TITLE   Quick Sort      
                .386 
                .model  flat, stdcall
                .stack  4096

; prototype from Kernel32 lib
ExitProcess     PROTO, dwExitCode:DWORD 

.data

; An array of 25 random integers to be sorted
array           DWORD   43, 91, 97, 63, 52,
                        58, 99, 19, 33, 26,
                        77, 11, 41, 89, 27,
                        99, 98, 68, 26,  5,
                        73, 47, 46, 59, 21 

.code

;-------------------------------------------------------------------------------
; _partition@12 (A , p, r)
;
; Quicksort subroutine
;
; Entry: A @ ebp + 8            ; pointer to array being sorted
;        p @ ebp + 12           ; integer index to start of sub-array
;        r @ ebp + 16           ; integer index to end of sub-array 
; 
; Local: x                      ; The pivot 
;        i                      ; index of smaller element
;
; Exit: the index of the pivot stored in eax
;-------------------------------------------------------------------------------
_partition@12:
                ; set up stack, save regs
                push    ebp
                mov     ebp, esp
                push    ebx
                push    ecx
                push    edx
                push    esi
                push    edi

; Load function parameters into registers and initialize local variables
                mov     ebx, [ebp + 8]          ; A stored in ebx
                mov     ecx, [ebp + 12]         ; p stored in ecx
                mov     edx, [ebp + 16]         ; r stored in edx
                mov     esi, [ebx + edx * 4]    ; x initialized to A[r] 
                lea     edi, [ecx - 1]          ; i initialized to p - 1

                ; Loop from index p to r - 1
                mov     eax, ecx                ; j (loop count) initialized to p
L2:             cmp     eax, edx
                jnl     endL2

                ; If A[j] <= x
                cmp     [ebx + eax * 4], esi
                jnle    endIf1
                inc     edi                     ; i = i + 1

                ; swap A[i] with A[j]
                mov     ecx, [ebx + edi * 4]
                xchg    ecx, [ebx + eax * 4]
                mov     [ebx + edi * 4], ecx
endIf1:
                inc     eax
                jmp     L2
endL2:
                ; swap A[i + 1] with A[r]
                inc     edi                     ; i = i + 1
                mov     ecx, [ebx + edi * 4]
                xchg    ecx, [ebx + edx * 4]
                mov     [ebx + edi * 4], ecx

                mov     eax, edi                ; return i + 1

                ; clean up stack, restore regs
                pop     edi
                pop     esi
                pop     edx
                pop     ecx
                pop     ebx
                pop     ebp
                ret     12

;-------------------------------------------------------------------------------
; _quickSort@12 (A , p, r)
;
; Sorts array of DWORD integers
;
; Entry: A @ ebp + 8            ; pointer to array to being sorted
;        p @ ebp + 12           ; integer index to start of sub-array
;        r @ ebp + 16           ; integer index to end of sub-array 
; 
;-------------------------------------------------------------------------------
_quickSort@12:
                ; set up stack, save regs
                push    ebp
                mov     ebp, esp
                push    ebx
                push    ecx
                push    edx

                ; Load function parameters into registers
                mov     ebx, [ebp + 8]          ; A stored in ebx
                mov     ecx, [ebp + 12]         ; p stored in ecx
                mov     edx, [ebp + 16]         ; r stored in edx

                ; if (p < r)
                cmp     ecx, edx
                jnl     endIf2

                ;q = Partition(A, p, r) 
                push    edx
                push    ecx
                push    ebx
                call    _partition@12           ; q stored in eax

                ;Quicksort(A, p, q - 1)
                dec     eax
                push    eax
                push    ecx
                push    ebx
                call    _quickSort@12

                ;Quicksort(A, q + 1, r)
                add     eax, 2
                push    edx
                push    eax
                push    ebx     
                call    _quickSort@12
endIf2:
                ; clean up stack, restore regs
                pop     edx
                pop     ecx
                pop     ebx
                pop     ebp
                ret     12

main:
                push    24
                push    0
                push    OFFSET array
                call    _quickSort@12

                ; array is sorted, but code does not
                ; print it to the console

                INVOKE  ExitProcess, 0
                END     main

Это был псевдокод я использовал:

Partition(A, p, r)
x = A[r]
i = p - 1 
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

Quicksort(A, p, r)
if p < r
    q = Partition(A, p, r)
    Quicksort(A, p, q - 1)
    Quicksort(A, q + 1, r)

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



767
6
задан 7 апреля 2018 в 09:04 Источник Поделиться
Комментарии
1 ответ

Это всего лишь проверка кода; я не проверил, что код сборки правильно реализует алгоритм в псевдокоде.

Использование некоторых регистров немного нетипичная. EAX обычно используется как временный регистр и сумматор (настолько, что некоторые операции на нем имеют более короткие кодировки, чем если бы те же операции проделать и с другими регистрами). В вашем "своп" код, это было бы нормально использовать EAX вместо ECX. Вы используете EAX как граф, но вы начинаете ее, скопировав значение из ECX. Так что просто использовать ECX как граф, и EAX в цикле временного значения через.

Что приводит к следующей мысли: когда вы сделаете свой рекурсивный _quickSort звонки, вы предполагаете, что значение в EAX не будет меняться в течение первого звонка, но он может с вас не сохранение и восстановление стоимости во время вызова. Это позволит сделать второй вызов, работу на чужие границы, в результате либо длительного выполнения (сортировка по большей площади, чем необходимо) или неверные результаты (если вся площадь не отсортированный).

Так _partition используется только локально, оно может быть дано не исковеркали имя и параметров, передаваемых непосредственно в регистры а не через стек. (То же самое относится к _quickSortно если вы собираетесь использовать этот код в более позднем проекте, или вызвать его из другого языка, вы, возможно, захотите, чтобы сохранить передачу параметров в стеке.)

В конце цикла while (между endIf1 и endL2 этикетки), а не безоговорочно прыгает к верхней части петли и проверка состояния, проверка состояния и условно-вернуться к началу цикла. Это дублирует условие проверки, но позволяет избежать дополнительной прыгать, когда цикл завершается. Он также общей оптимизации в некоторых компилируемых языков программирования (в частности C и C++).

Использование негативных условий условного перехода (для меня) труднее читать, чем аналогичные положительные. JNL (прыгать не меньше) такая же, как JGE (прыжок больше или равно) и JNLE (прыгать не меньше или равно) равна JG (прыгать выше). Ничего плохого в том, что у вас есть, но я привык к положительной версии. Просто оставайтесь в соответствии с вашей использования.

2
ответ дан 7 апреля 2018 в 09:04 Источник Поделиться