quick_sort_asm.cpp

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void quicksort(int * mas, int first, int last){
    asm(
                "leave;" //"pop %ebp;" // вернуть стек к его первоначальному состоянию (которое было перед вызовом внешней функции)
        "quick_sort:"
                // входим в функцию, сохраняя регистр ebp в стек
                "push   %ebp;"
                "mov    %esp,           %ebp;"

                // Смещаем стек влево на 10*sizeof(int) = 40 = 0x28
                "sub    $0x28,          %esp;"

                // f = first;
                "mov    0xc(%ebp),      %eax;"
                "mov    %eax,           -0xc(%ebp);"

                // l = last;
                "mov    0x10(%ebp),     %eax;"
                "mov    %eax,           -0x10(%ebp);"

                // l + f;
                "mov    -0xc(%ebp),     %edx;"
                "mov    -0x10(%ebp),    %eax;"
                "add    %edx,           %eax;"
                "mov    %eax,           %edx;"

                // (l + f)/2;
                "shr    $0x1f,          %edx;"
                "add    %edx,           %eax;"
                "sar    %eax;"

                // mid = mas[(l + f)/2];
                "lea    (,%eax,4),      %edx;"
                "mov    0x8(%ebp),      %eax;"
                "add    %edx,           %eax;"
                "mov    (%eax),         %eax;"
                "mov    %eax,           -0x14(%ebp);"

            // Цикл do {...} while (f < l);
            "_do:"
                "jmp    _condition_while_left;"

                // Цикл while ( mas[f] < mid ) f++;
                "_step_while_left:"
                    "addl   $0x1,       -0xc(%ebp);" // f++;
                "_condition_while_left:"
                    "mov    -0xc(%ebp), %eax;"
                    "lea    (,%eax,4),  %edx;"
                    "mov    0x8(%ebp),  %eax;"
                    "add    %edx,       %eax;"
                    "mov    (%eax),     %eax;"
                    "cmp    -0x14(%ebp),%eax;"
                    "jl     _step_while_left;"
                    "jmp    _condition_while_right;"

                // Цикл while ( mas[l] > mid ) l--;
                "_step_while_right:"
                    "subl   $0x1,       -0x10(%ebp);" // l--;
                "_condition_while_right:"
                    "mov    -0x10(%ebp),%eax;"
                    "lea    (,%eax,4),  %edx;"
                    "mov    0x8(%ebp),  %eax;"
                    "add    %edx,       %eax;"
                    "mov    (%eax),     %eax;"
                    "cmp    -0x14(%ebp),%eax;"
                    "jg     _step_while_right;"
                // if ( f <= l )
                "mov    -0xc(%ebp),     %eax;"  // Копирование f в регистр eax
                "cmp    -0x10(%ebp),    %eax;"  // Сравнение f и l

                // Если f > f то пропускаем тело условия
                "jg     _after_if_in_do_while;"

                // Иначе меняем местами mas[f] и mas[l]
                // count = mas[f];
                "mov    -0xc(%ebp),     %eax;"
                "lea    (,%eax,4),      %edx;"
                "mov    0x8(%ebp),      %eax;"
                "add    %edx,           %eax;"
                "mov    (%eax),         %eax;"
                "mov    %eax,           -0x18(%ebp);"

                // mas[f] = mas[l];
                "mov    -0xc(%ebp),     %eax;"
                "lea    (,%eax,4),      %edx;"
                "mov    0x8(%ebp),      %eax;"
                "add    %eax,           %edx;"
                "mov    -0x10(%ebp),    %eax;"
                "lea    (,%eax,4),      %ecx;"
                "mov    0x8(%ebp),      %eax;"
                "add    %ecx,           %eax;"
                "mov    (%eax),         %eax;"
                "mov    %eax,           (%edx);"
                // mas[l] = count;
                "mov    -0x10(%ebp),    %eax;"
                "lea    0x0(,%eax,4),   %edx;"
                "mov    0x8(%ebp),      %eax;"
                "add    %eax,           %edx;"
                "mov    -0x18(%ebp),    %eax;"
                "mov    %eax,           (%edx);"

                // Увеличиваем f на единицу
                "addl   $0x1,           -0xc(%ebp);"    // f++

                // Уменьшаем l на единицу
                "subl   $0x1,           -0x10(%ebp);"   // l--
            "_after_if_in_do_while:"
                // Сравниваем f и l
                "mov    -0xc(%ebp),     %eax;"
                "cmp    -0x10(%ebp),    %eax;"

                // Если f < l, то возвращаемся к телу цикла do {...} while
                "jl     _do;"

                // Сравниваем first и l
                "mov    0xc(%ebp),      %eax;"
                "cmp    -0x10(%ebp),    %eax;"

                // Если first >= last, то левая рекурсия не нужна, переходим к правой рекурсии
                "jge    _after_left_recursion;"

                // Иначе мы должны рекурсивно вызвать функцию сортировки на левом отрезке
                // Кладем l во второй элемент за указателем на стек
                "mov    -0x10(%ebp),    %eax;"
                "mov    %eax,           0x8(%esp);"

                // Кладем first в первый элемент за указателем на стек
                "mov    0xc(%ebp),      %eax;"
                "mov    %eax,           0x4(%esp);"

                // Кладем mas в элемент, на который непосредственно указывает указатель на стек
                "mov    0x8(%ebp),      %eax;"
                "mov    %eax,           (%esp);"

                // Вызываем quicksort(mas, first, l);
                "call   quick_sort;"
            "_after_left_recursion:"
                // Сравниваем f и last
                "mov    -0xc(%ebp),     %eax;"
                "cmp    0x10(%ebp),     %eax;"

                // Если f >= last, то правая рекурсия не нужна, переходим в конец функции
                "jge    _end;"

                // Иначе мы должны рекурсивно вызвать функцию сортировки на правом отрезке
                // Кладем last во второй элемент за указателем на стек
                "mov    0x10(%ebp),     %eax;"
                "mov    %eax,           0x8(%esp);"

                // Кладем f в первый элемент за указателем на стек
                "mov    -0xc(%ebp),     %eax;"
                "mov    %eax,           0x4(%esp);"

                // Кладем mas в элемент, на который непосредственно указывает указатель на стек
                "mov    0x8(%ebp),      %eax;"
                "mov    %eax,           (%esp);"

                // Вызываем quicksort(mas, f, last);
                "call   quick_sort;"
            "_end:  leave;"
        "ret;"
    );
}

int main() {
//  Создаем массив:
    const int n = 500000; int a[n];
    for (int i = 0; i < n; i++)
        a[i] = rand() % n;

//  Сортируем в порядке неубывания и засекаем время:
    int t = clock();
    quicksort(a, 0, n-1);
    double time_sec = (clock() - t ) * 1.0 / CLOCKS_PER_SEC;
//  Проверяем на правильность:
    for (int i = 1; i < n; i++)
        if ( a[i-1] > a[i] )
            printf("ERROR: a[%d] > a[%d]\n", i-1, i);
    printf("ok! time: %0.3fs\n", time_sec);
    return 0;
}