Funkce v assembleru

[Elis]

Ahoj,

mám napsanou funkci v assembleru, která má za úkol setřídit pole čísel. Nenašel by se prosím někdo, kdo by byl ochotný se podívat můj kód a pomohl mi najít chybu?

Díky moc předem.

[Reklama]

[Michal Strnad]

Zkus sem dát svůj kód (nějak rozumně zformátovaný), napiš, o jaký assembler jde, popiš použitý algoritmus, jak se tvůj výtvor chová a jak by sis představoval, aby se choval. Teprve potom můžeš očekávat kvalifikovanou pomoc.

[Elis]

http://leteckaposta.cz/262910553 (můj kód). Jedná se o inline assembler (32bitový assembler procesorů Intel
(řady označované jako IA32 či x86)). Použitý byl algoritmus quicksort, který bere jako parametr pole a jeho délku.

[Michal Kovačič]

Ahoj,

mám napsanou funkci v assembleru, která má za úkol setřídit pole čísel. Nenašel by se prosím někdo, kdo by byl ochotný se podívat můj kód a pomohl mi najít chybu?

Díky moc předem.

Bez ohledu na vlastni algoritmus tam vidim nekolik nesmyslu spojenych s tim, ze nektere porovnani+skok jsou velice zvlastni:

   cmp edx, eax
   jl zmensi_edi

zmensi_edi:

na kod zmensi_edi to dorazi pokazde BEZ ohledu na porovnani... Podobna konstrukce je tam nekolikrat.

Az se mi jevi, ze tohle nemuze byt uplny kod...

[fish]

mam neblahe tuseni, ze se jedna o domaci ulohu ze skoly, nemam pravdu?

[Reklama]

[j]

mam neblahe tuseni, ze se jedna o domaci ulohu ze skoly, nemam pravdu?

To urcite je, a uz definice ty funkce neni koser... a to pisu jako neprogramator ... pokud vim Ccko rozhodne nijak negarantuje jak velky bude unsigned short. Pokud wiki nekeca, tak je to at least 16bit ... ale klidne to muze byt 32 nebo taky 64 ... . Mno a ladovat trebas tech 64bitu do 32bit registru .... navic tahle funkce se podle vseho podela i pri 32bitech, definovana je pro 8/16.

[Kolemjdoucí]

V tvém kódu se vrtat nebudu, dělá se to nějak takhle. Za domácí úkol máš zjistit, proč na QuickSort stačí jenom jedna rekurze a ne dvě jak máš ty.

Kód: [Vybrat]

int quicksort(int* pole, unsigned short delka_pole)
{
_asm
{
movzx eax,delka_pole
test eax,eax
jz Exit

mov esi,pole
lea edi,dword ptr [esi+eax*4-4]
mov ebx,edi

    Start:
lea eax,dword ptr [esi+edi]
shr eax,1
and eax,~0x03
                mov ecx,dword ptr [eax]

    Left:
cmp ecx,dword ptr [esi]
jng Right
lea esi,dword ptr [esi+4]
jmp Left

    Right:
cmp ecx,dword ptr [edi]
jnl Swap
lea edi,dword ptr [edi-4]
jmp Right

    Swap:
cmp esi,edi
ja NestingLeft

mov eax,dword ptr [esi]
mov edx,dword ptr [edi]
mov dword ptr [esi],edx
mov dword ptr [edi],eax
lea esi,dword ptr [esi+4]
lea edi,dword ptr [edi-4]
cmp esi,edi
jb Left 

    NestingLeft:
sub edi,pole
jbe NestingRight
shr edi,2
lea edi,dword ptr [edi+1]
push edi
mov eax,pole
push eax
call quicksort
add esp,8

NestingRight:
mov eax,ebx
sub eax,esi
jbe Exit

shr eax,2
lea eax,dword ptr [eax+1]

mov pole,esi
mov delka_pole,ax
mov edi,ebx
jmp Start

    Exit:
}
}


[Kolemjdoucí]

navic tahle funkce se podle vseho podela i pri 32bitech, definovana je pro 8/16.

_asm jde přeložit jenom v MSVC, takže jestli nevytáhne nějakou verzi pro Windows 3.1 a starší, tak to bude fungovat vždy dobře, protože int a short jsou definované exaktně. Problém s 64-bit je vyřešen tím, že MSVC 64-bit inline assembler nepodporuje

[Elis]

Díky moc za pomoc!

[Kolemjdoucí]

Díky moc za pomoc!

A kde je vypracovaný domácí úkol ?

[j]

navic tahle funkce se podle vseho podela i pri 32bitech, definovana je pro 8/16.

_asm jde přeložit jenom v MSVC, takže jestli nevytáhne nějakou verzi pro Windows 3.1 a starší, tak to bude fungovat vždy dobře, protože int a short jsou definované exaktně. Problém s 64-bit je vyřešen tím, že MSVC 64-bit inline assembler nepodporuje

To je jedno ze to bude fungovat. Kdybych tohle zadaval jako domaci ukol, tak tohle bude jedna z veci, kterou mu vytknu. Protoze nikdy nevis v cem ten tvuj kod bude prekladat za 20let nejaky pokracovatel nebo ty sam. Tohle je totiz napsany presne ve stylu "proc bych mel kotrolovat vstup, ono to nejak dopadne". A pak se dotycny strasne divi, kdyz se mu v poli kde on prece naprosto logicky ocekava cislo objevi string.

[Kolemjdoucí]

Protoze nikdy nevis v cem ten tvuj kod bude prekladat za 20let nejaky pokracovatel nebo ty sam.

To sis nějak spletl, školní úloha má fungovat 5 minut při kontrole učitelem a tím to končí.

[Michal Strnad]

... A pak se dotycny strasne divi, kdyz se mu v poli kde on prece naprosto logicky ocekava cislo objevi string.

To by mě fakt zajímalo, jak se pozná, že pole neobsahuje čísla, ale string?

[Giovanna]

V tvém kódu se vrtat nebudu, dělá se to nějak takhle. Za domácí úkol máš zjistit, proč na QuickSort stačí jenom jedna rekurze a ne dvě jak máš ty.

Kód: [Vybrat]

int quicksort(int* pole, unsigned short delka_pole)
{
_asm
{
movzx eax,delka_pole
test eax,eax
jz Exit

mov esi,pole
lea edi,dword ptr [esi+eax*4-4]
mov ebx,edi

    Start:
lea eax,dword ptr [esi+edi]
shr eax,1
and eax,~0x03
                mov ecx,dword ptr [eax]

    Left:
cmp ecx,dword ptr [esi]
jng Right
lea esi,dword ptr [esi+4]
jmp Left

    Right:
cmp ecx,dword ptr [edi]
jnl Swap
lea edi,dword ptr [edi-4]
jmp Right

    Swap:
cmp esi,edi
ja NestingLeft

mov eax,dword ptr [esi]
mov edx,dword ptr [edi]
mov dword ptr [esi],edx
mov dword ptr [edi],eax
lea esi,dword ptr [esi+4]
lea edi,dword ptr [edi-4]
cmp esi,edi
jb Left 

    NestingLeft:
sub edi,pole
jbe NestingRight
shr edi,2
lea edi,dword ptr [edi+1]
push edi
mov eax,pole
push eax
call quicksort
add esp,8

NestingRight:
mov eax,ebx
sub eax,esi
jbe Exit

shr eax,2
lea eax,dword ptr [eax+1]

mov pole,esi
mov delka_pole,ax
mov edi,ebx
jmp Start

    Exit:
}
}


Jak jste prosím zjistil, že rekurze má být jenn jedna? Já jsem k zápočtu odevzdával kód, regurzi mám pro pravou i levou, a nevidím na tom nic špatného. Je to tedy v NASM..

Kód: [Vybrat]

BITS 32

section .data

global a_quick_sort

section .text

a_quick_sort: ;int quick_sort (int *a, int ll, int rr)

    enter 10, 0
    push EBX
    push ECX
    push EDX
   
    ; pole hodnot
    mov EBX, [EBP+8]
   
    ; levy a pravy index
    mov ESI, [EBP+12] ; v ESI je l = ll
    mov EDI, [EBP+16] ; v EDI je r = rr
   
    ; medianem je prvni prvek
    mov EAX, ESI
    add EAX, EDI
    xor EDX, EDX
    mov ECX, 2
    div ECX
    mov EAX, [EBX+EAX*4]
   
do: ; hlavni cyklus do-while
   
w1: cmp [EBX+ESI*4], AX ; cyklus while pro levou polovinu
    jnl w2
    inc ESI
    jmp w1

w2: cmp AX, [EBX+EDI*4] ; cyklus while pro pravou polovinu
    jnl x
    dec EDI
    jmp w2

x:  cmp ESI, EDI ; if (l<=r) pak prehod prvky
    jg xx
    mov EDX, [EBX+ESI*4]
    mov ECX, [EBX+EDI*4]
    mov [EBX+ESI*4], ECX
    mov [EBX+EDI*4], EDX
    inc ESI
    dec EDI
xx: ; jinak neprehazuj
    cmp ESI, EDI ; while (l<=r)
    jle do

; setrideni leveho useku
r1: cmp [EBP+12], EDI
    jge r2
    push EDI
    push dword [EBP+12]
    push dword [EBP+8]
    call a_quick_sort
    pop EAX
    pop EAX
    pop EAX

; setrideni praveho useku
r2: cmp ESI, [EBP+16]
    jge nr
    push dword [EBP+16]
    push ESI
    push dword [EBP+8]
    call a_quick_sort
    pop EAX
    pop EAX
    pop EAX

nr:
    xor EAX, EAX ; navratova hodnota

    pop EDX
    pop ECX
    pop EBX
    leave
    ret
end


[Kolemjdoucí]

Jak jste prosím zjistil, že rekurze má být jenn jedna? Já jsem k zápočtu odevzdával kód, regurzi mám pro pravou i levou

Ano, obvykle bývají rekurze dvě. Avšak po chvilce přemýšlení to jde udělat i pouze s jednou a protože to máte evidentní školní úlohu, zkuste na to přijít sám