Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: Elis 29. 04. 2015, 17:49:33
-
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.
-
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.
-
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.
-
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...
-
mam neblahe tuseni, ze se jedna o domaci ulohu ze skoly, nemam pravdu?
-
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.
-
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.
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:
}
}
-
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 :)
-
Díky moc za pomoc!
-
Díky moc za pomoc!
A kde je vypracovaný domácí úkol ? ;)
-
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.
-
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čí.
-
... 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?
-
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.
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..
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
-
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 ;)
-
Bonusový úkol do KMI/OS1, že Elis?
-
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 ;)
Zlepší to snad složitost? To je jeho, ne moje, úloha..
-
Jak jste prosím zjistil, že rekurze má být jenn jedna?
napoveda: http://en.wikipedia.org/wiki/Tail_call
-
Čísla bych raději řadil než třídil. Třídit čísla je samozřejmě možné, ale obvykle se třídí leda odpad.
-
Čísla bych raději řadil než třídil. Třídit čísla je samozřejmě možné, ale obvykle se třídí leda odpad.
not true
http://en.wikipedia.org/wiki/Radix_sort
-
Radix sort (česky Číslicové třídění) je řadicí algoritmus, který řadí celá čísla postupným procházením všech číslic.
-
Radix sort (česky Číslicové třídění) je řadicí algoritmus, který řadí celá čísla postupným procházením všech číslic.
radix sort je algoritmus kteri radi cisla tim ze je tridi podle cislic ;-)
-
Radix sort (česky Číslicové třídění) je řadicí algoritmus, který řadí celá čísla postupným procházením všech číslic.
radix sort je algoritmus kteri radi cisla tim ze je tridi podle cislic ;-)
Všechny řadicí metody se označují jako "xyz sort" z historických důvodů. Pochází to z dob děrných štítků, kdy se řadilo právě tříděním. Štos štítků se opakovaně prohnal přes řadu propadel a vždycky se roztřídil podle jedné číslice a získané štosy poskládaly za sebe. Je to mechanický radix-sort.