Diskuze: Quicksort

švrčajs

Člen

švrčajs:1.5.2015 23:03

Zdarec, píšu si quicksort v inline assembleru, vloženého do cčka, podle pseudokodu:

void quick_sort (int *a, int n)
{
        int i, j, p, t;
        if (n <= 1)
        {
                return;
        }
        p = a[n / 2];
        for (i = 0, j = n - 1;; i++, j--)
        {
                while (a[i] < p)
                {
                        i++;
                }
                while (p < a[j])
                {
                        j--;
                }
                if (i >= j)
                {
                        break;
                }
                t = a[i];
                a[i] = a[j];
                a[j] = t;
        }
        quick_sort(a, i);
        quick_sort(a, n - i);
}

zatím jsem napsal tohle, ani nevím, zda to bude funkční , ale jde mi o to, jak prohodit prvky v poli pomocí assembleru ? když zkusím mov [prvek], [prvek].. tak to hodí error..

zatím mám napsané, dle mého názoru snad funkční, toto:

void Quick(int *A, unsigned short n)
{
        _asm
        {
                mov ebx, n;
                cmp ebx, 1;//ukončovací podmínka
                jbe konec;
                mov eax, A;
                mov ebx, [eax + ebx * 2]; //pivot (n/2) * 4 = n * 2
                mov ecx, 0; // index i
                movsx edx, n;
                sub edx, 1; //index j
                for:
                while1:
                        //dokud je pivot větší..
                        cmp ebx, [eax + ecx * 4];
                        jb while2;
                        inc ecx;
                        jmp while1;

                while2:
                        cmp ebx, [eax, edx * 4];
                        ja forbody;
                        dec edx;
                        jmp while2;

                forbody:
                        cmp ecx, edx;
                        jae rekurze;
                        //swap, zjistit..

                        jmp for;

                rekurze:
                        //quick(a, i)
                        push ecx;
                        push eax;
                        call Quick;
                        add esi, 8;
                        //quick(a, n - i)
                        movsx ebx, n;
                        sub ebx, ecx;
                        push ebx;
                        push eax;
                        call Quick;
                        add esi 16;



                konec:

        }



}

Odpovědět

1.5.2015 23:03

Martin Dráb

Tvůrce

Martin Dráb:1.5.2015 23:26

Instrukce

mov [adresa], [adresa]

v x86/x64 Assembleru neexistuje. Alespoň jeden argument u instrukce MOV musí být registr. Možná tě ale bude spíše zajímat instrukce XCHG.

Nahoru Odpovědět

1.5.2015 23:26

2 + 2 = 5 for extremely large values of 2

švrčajs

Člen

švrčajs:1.5.2015 23:56

na xchg jsem zapomenul no Ale stejně dneska jsem po dlouhé době otevřel scripta a zjistil jsem, že to mám tak z 98% špatně v zadání je, že to má fungovat i na dynamicky alokované pole, tak tak budu muset požívat LEA na výpočet adresy.. a celé to "překopat"

Nahoru Odpovědět

1.5.2015 23:56

coells

Tvůrce

coells:2.5.2015 0:30

Nebude to fungovat:

quick_sort(a, i);
quick_sort(a, n - i);

>>>

quick_sort(a, j);
quick_sort(a + i, n - i);

Nahoru Odpovědět

2.5.2015 0:30

Martin Dráb

Tvůrce

Martin Dráb:2.5.2015 1:00

v zadání je, že to má fungovat i na dynamicky alokované pole,

Ono by ti to i na dynamicky alokované pole fungovat i mohlo. Do funkce Quick předáváš pointer na první prvek toho pole. Ta funkce nemusí vědět, zda to pole je alokováno na zásobníku či na haldě.

Nahoru Odpovědět

2.5.2015 1:00

2 + 2 = 5 for extremely large values of 2

švrčajs

Člen

švrčajs:2.5.2015 10:47

no, zkusil jsem tam použít instrukci xchg, ale hází mi to error s tím, že používám špatné operandy..

xchg [eax + ecx * 4], [eax + edx * 4];

.....

quick_sort(a, j);
quick_sort(a + i, n - i);

a tady to a + i značí co ? přece k poli nemůžu přičíst číslo ne ?

Editováno 2.5.2015 10:48

Nahoru Odpovědět

2.5.2015 10:47

Martin Dráb

Tvůrce

Martin Dráb:2.5.2015 11:27

Stejně jako MOV, ani XCHG nemá variantu se dvěma adresovými operandy, pokud vím. Tzn. budeš muset provést něco jako:

mov edi, [eax + ecx * 4]
xchg edi, [eax + edx * 4];
mov [eax + ecx * 4], edi

Ale vsadil vych se, že to půjde napsat lépe.

Přičítání čísla k poli je v Cčku opravdu možné. Krom toho, ty do funkce nepředáváš pole, ale adresu jeho prvního prvku. A k adrese čísla přičítat, přičemž následující výrazy jsou ekvivalentní:

a + i
&a[i]

V Cčku je pole v podstatě jen adresa svého prvního prvku, tzn. ukazatel.

Nahoru Odpovědět

2.5.2015 11:27

2 + 2 = 5 for extremely large values of 2

švrčajs

Člen

švrčajs:2.5.2015 13:04

no, poupravoval jsem celý kód a teď to vypadá následovně...

void Quick(int *A, unsigned short n)
{
        _asm
        {
                movsx ebx, [n];
                cmp ebx, 1;//ukončovací podmínka
                jbe konec;
                mov eax, A;
                mov ebx, [eax + ebx * 2]; //pivot (n/2) * 4 = n * 2
                mov ecx, 0; // index i
                movsx edx, [n];
                sub edx, 1; //index j
                for:
        while1 :

                        //dokud je pivot větší.;.
                   cmp ebx, [eax + ecx * 4];
                        jb while2;
                        inc ecx;
                        jmp while1;

                while2:
                        cmp ebx, [eax + edx * 4];
                        jge forbody;
                        dec edx;
                        jmp while2;

                forbody:
                        cmp ecx, edx;
                        jae rekurze;
                        //swap, zjistit..
                        mov edi, [eax + ecx * 4];
                        xchg edi, [eax + edx * 4];
                        mov [eax + ecx * 4], edi;
                        inc ecx;
                        dec edx;
                        jmp for;

                rekurze:
                        //quick(a, i)
                        push ecx;
                        push eax;
                        call Quick;
                        add esi, 8;
                        //quick(a, n - i)
                        movsx ebx, n;
                        sub ebx, ecx;
                        push ebx;
                        //A + i
                        add eax, 1;

                        push eax;
                        call Quick;
                        add esi, 16;



                konec:
                        xor eax, eax;
        }
}

Mám ale problém v rekurzi, protože, jak mi jedna větev rekurze přepíše registry, tak ta druhá potom leze do nepřístupné paměti.. Co jsem se díval, tak ve skriptech je jenom jedna rekurzivní větev...

paramety
call funkce

ale není tam, jak udělat dvě větve

Nahoru Odpovědět

2.5.2015 13:04

Martin Dráb

Tvůrce

Martin Dráb:2.5.2015 21:12

Podle mě bys aktuálně měl problém i s tou jednou větví (kód jsem nekontroloval, jen se vyjadřuju k té rekurzi). Prostě proto, že si při volání funkce necháváš aktuální stav v registrech, které ve volané funkci následně přepíšeš.

Registry si můžeš ukládat na zásobník a v případě potřeby vybrat (instrukce PUSH a POP), případně je ukládat do místa na zásobníku rezervovaného pro parametry a lokální proměnné. Ale to by pak asi bylo skoro lepší mít plnou kontrolu nad funkcí, tzn. pro MSVS ji deklarovat jako __declspec(naked).

Také bys měl asi jasně deklarovat volací konvenci (ideálně asi stdcall), abys měl jistotu, že správně předáváš parametry při volání.

Nahoru Odpovědět

2.5.2015 21:12

2 + 2 = 5 for extremely large values of 2

Nejčastěji vyhledáváné

Diskuze: Quicksort