quicksort se assembly gia 8085. HELP!

kopunisher · 2 Σεπτεμβρίου 2005

Χαιρετε

Εχω μια εργασια για την σχολη να γραψω τον quicksort σε assembly για τον intel 8085. Εκανα μια απόπειρα να τον γραψω αλλά όπως μπορείτε να δείτε είναι μπαχαλο. Εγω παντως ξενερωσα τελείως. (Δεν μπορεσα να βρω τον τρόπο υλοποίησης του αναδρομικού μέρους του αλγορίθμου) Ξερω οτι το θέμα είναι τραγικά βαρετο και παρωχημένο, αλλα όποιος έχει όρεξη να δει τον κώδικα καλώς.

Επίσης δεν καταφερα να βρω κατι σχετικο στο ιντερνετ.

Μια ιδέα ήταν να περασω τον αλγόριθμο πχ σε C και να κανω disassemble, αλλα δεν μπορω να βρω compiler για 8085 (micro-C ???). Γίνεται να βρεθει κατι τετοιο?

Ο τρομερος κώδικας: :grin:

(χρησιμοποίησα 10 αριθμους με αρχική θέση την 3000Η ο κωδικας ειναι γραμμενος σε simulator)

; initialisation

LXI SP,FFF0H

LXI H,3009H

XCHG

MVI B,30H

MVI C,00H

QSORT:

MOV H,B

MOV L,C

MOV A,M

MOV L,E

SCANR:

CMP M

PUSH PSW

CNC SWAP

CPI 01H

JZ SCANL

DCX H

JMP SCANR

SCANL:

POP PSW

MOV C,L

LXI H,3000H

LOOP:

INX H

CMP M

PUSH PSW

PUSH B ;;;

CC SWAP

JZ RECURSIVE

CPI 01H

JNZ LOOP

POP H ;;;

POP PSW

JMP SCANR

SWAP:

PUSH B

PUSH D

PUSH H

MOV D,M

MOV L,C

MOV E,M

MOV M,D

POP H

MOV M,E

MVI A,01H

POP D

POP B

MOV C,L

RECURSIVE:

;BREAK

LXI B,3000H

DCX H

MOV E,L

JMP QSORT ; I<X

QS2:

LXI B,3009H

;BREAK

INX H

MOV E,L

JMP QSORT

HLT

GCMH · 3 Σεπτεμβρίου 2005

Επειδή δεν ξέρω.... Ποιός είναι ο αλγόριθμος quicksort και κάτι μπορεί να κάνω...............................

GCMH · 3 Σεπτεμβρίου 2005

Επειδή δεν ξέρω.... Ποιός είναι ο αλγόριθμος quicksort και κάτι μπορεί να κάνω...............................

kopunisher · 15 Σεπτεμβρίου 2005

den eixa parei xampari oti eixa kapoio reply.

O quicksort se c einai o parakato.

void quickSort(int numbers[], int array_size)

{

q_sort(numbers, 0, array_size - 1);

}

void q_sort(int numbers[], int left, int right)

{

int pivot, l_hold, r_hold;

l_hold = left;

r_hold = right;

pivot = numbers

;

while (left < right)

{

while ((numbers

>= pivot) && (left < right))

right--;

if (left != right)

{

numbers

= numbers

;

left++;

}

while ((numbers

<= pivot) && (left < right))

left++;

if (left != right)

{

numbers

= numbers

;

right--;

}

numbers

= pivot;

pivot = left;

left = l_hold;

right = r_hold;

if (left < pivot)

q_sort(numbers, left, pivot-1);

if (right > pivot)

q_sort(numbers, pivot+1, right);

}

epeidi den ksero c den katalavaino kai polla pragmata apo ton kodika. An exeis oreksi na tou rikseis kamia matia...

zazik · 24 Σεπτεμβρίου 2005

i pio apla kapos etsi

push(0) onto stack; push(n) onto stack

while stack not empty

hi = pop stack; lo = pop stack

if hi - lo not = 1

mid = part(lo, hi)

push lo onto stack; push mid onto stack

push mid onto stack; push hi onto stack

kopunisher · 24 Σεπτεμβρίου 2005

i pio apla kapos etsi

push(0) onto stack; push(n) onto stack

while stack not empty

hi = pop stack; lo = pop stack

if hi - lo not = 1

mid = part(lo' date=' hi)

push lo onto stack; push mid onto stack

push mid onto stack; push hi onto stack[/quote']

Basika den katalavaino ti theleis na peis...

(n) einai to stoixeio tou pinaka etsi?

Mporeis na mou grapseis se logia ti kanei to loop pou mou egrapses?

kai me tin assembly ti ginetai?

eyxaristo

zazik · 26 Σεπτεμβρίου 2005

χεχε

σόρρυ το ξέρω οτι οι ψευδοκώδικες μερικές φορές είναι πιο δύσκολοι απο τον κανονικό κώδικα.

για κοίτα αυτό θα σε βοηθήσει πολύ¨..

http://en.wikipedia.org/wiki/Quicksort

τώρα απο assembly δεν ξέρω εκτός των βασικών..μα και συ βρε άνθρωπε

ασσεμβλυ 8085?το παρατράβηξες. :grin: :grin:

GCMH · 26 Σεπτεμβρίου 2005

Ψάχνοντας στο google βρήκα έναν τύπο που έγραψε αυτό που θες σε γλώσσα μηχανής για τον Z80. Του έριξα μια ματιά και πιστεύω πως μπορείς να τον "μεταφράσεις" σε 8085 μιας και σχεδόν όλες οι εντολές του 8085 έχουν το αντίστοιχό τους στον Ζ80. Επιπλέον στο κομμάτι που παραθέτω σχεδόν όλες οι εντολές είναι κοινές και στους δύο επεξεργαστές.

Πρόβλημα θα έχεις με τις εντολές του Ζ80: τις SBC HL,BC και SBC HL,DE οι οποίες είναι αφαίρεση με τη χρήση κρατούμενου για 16 bit καταχωρητές...

Πιστεύω ότι θα τα καταφέρεις να τις αντικαταστήσεις με άλλες ισοδύναμες.....

Ακολουθεί ο κώδικας για Ζ80....

;

; >>> Quicksort routine v1.1 <<<

; by Frank Yaul 7/14/04

;

; Usage: bc->first, de->last,

; call qsort

; Destroys: abcdefhl

;

qsort ld hl,0

push hl

qsloop ld h,b

ld l,c

or a

sbc hl,de

jp c,next1 ;loop until lo<hi

pop bc

ld a,b

or c

ret z ;bottom of stack

pop de

jp qsloop

next1 push de ;save hi,lo

push bc

ld a,(bc) ;pivot

ld h,a

dec bc

inc de

fleft inc bc ;do i++ while cur<piv

ld a,(bc)

cp h

jp c,fleft

fright dec de ;do i-- while cur>piv

ld a,(de)

ld l,a

ld a,h

cp l

jp c,fright

push hl ;save pivot

ld h,d ;exit if lo>hi

ld l,e

or a

sbc hl,bc

jp c,next2

ld a,(bc) ;swap (bc),(de)

ld h,a

ld a,(de)

ld (bc),a

ld a,h

ld (de),a

pop hl ;restore pivot

jp fleft

next2 pop hl ;restore pivot

pop hl ;pop lo

push bc ;stack=left-hi

ld b,h

ld c,l ;bc=lo,de=right

jp qsloop

;

; >>> end Quicksort <<<

;

Αν κάτι δεν το καταλαβαίνεις εδώ είμαστε!!!

kopunisher · 27 Σεπτεμβρίου 2005

@ zazik: πιστεψε με δεν φταιω εγω!!! είναι τελείως παρωχημένο το θέμα...

πολυ καλο το λινκ για την wikipedia!

@GCMH

τον ειχα βρει κι εγω τον κωδικα για τον Ζ80, αλλά με μπέρδεψε τόσο που δεν εκανα τον κόπο να δω τις εντολές που δεν υποστηρίζει ο 8085. Ετσι εκανα την απόπειρα να γραψω τον κωδικα μόνος μου απο ότι καταλάβαινα.

Παντως ευχαριστω και θα κάτσω να το ψαξω κι αλλο, γιατι δεν προλάβαινα αυτο τον καιρό.

zazik · 27 Σεπτεμβρίου 2005

μιλάμε οτι γυρίσαμε στην εποχή του Homo Erectus :grin: :grin:

ποπο καντίλες έβγαλα... :? :? !!!

δεν μπορώ να καταλάβω πως μπορείτε να γράφετε κώδικα σε assembly.

εγώ ξέρω τα βασικά δηλαδή

push EAX και πάλι ζορίζομε..

You are heroes.... :wink: :wink: :razz: :grin:

GCMH · 27 Σεπτεμβρίου 2005

@kopunisher: Κοίτα το δεν είναι καθόλου δύσκολο, μόνο δύο εντολές από αυτό που σου έστειλα δεν έχει ο 8085, οι οποίες μάλιστα μπορούν να αντικατασταθούν (αν σκεφτείς πως η αφαίρεση είναι στην ουσία μια πρόσθεση του αντίθετου αριθμού)....

Όλες η άλλες εντολές υπάρχουν

@zazik: ναι, έχεις δίκιο. Αυτοί οι επεξεργαστές είναι από την εποχή του Erectus ή μήπως Habilis;;;;;!!!!!!!!! Τέλος πάντων, γλώσσα μηχανής για τον Ζ80 έμαθα λιγάκι τον καιρό που είχα έναν CPC 664.....

Εγώ προσωπικά δεν γράφω σε γλώσσα μηχανής... Την χρησιμοποιώ μόνο σε τμήματα προγραμμάτων που θέλω να βελτιστοποιήσω (γράφω σε Delphi)....

Sta · 27 Σεπτεμβρίου 2005

Φίλε, πες μου ποιον simulator χρησιμοποιείς αν θέλεις. Η αναδρομή δεν αποκλείεται αφού η κλήση των υπορουτινών γίνεται μέσω στοίβας.

kopunisher · 27 Σεπτεμβρίου 2005

@sta: Βασικά χρησιμοποιώ τον 8085 simulator της ABCreation (http://www.amanb.net/8085) ή εναλλακτικά τον microproccesor simulator 8085 apo Infotech Solution (http://www.insoluz.com) για να βλέπω το σετ των εντολών κυρίως.( ειναι μανουλες οι ινδοι !!!)

Φαντάζομαι ότι η αναδρομή είναι εφικτή, το ουσιαστικό μου πρόβλημα είναι με τον αλγόριθμο.

@GMCH: Οι εντολές όντως δεν είναι πρόβλημα, δεν μπορώ να πιάσω αυτά που κάνει...

Πάντως η assembly συνδιασμένη πχ με C βολεύει για διαχειριση hardware όπως μικροελεγκτες, γιατί ξέρεις τι κάνεις ακριβώς.

Ασχετο, πρέπει να μάθω C από το μηδεν για προγραμματισμό μικροελεγκτή 8051 like.

Μου εχουν πει για ένα βιβλίο programming in C κάποιου Dytel(????). Λέει αυτό ή υπάρχει κάποια καλύτερη πρόταση?

MrTryANalyzer · 27 Σεπτεμβρίου 2005

Kalispera ILIA . .

Des ta parakato LINKS:

http://www.programmersheaven.com/c/MsgBoard/read.asp?Board=17&MsgID=313211&Setting=A9999F0001

Ubiquitous Z80 QuickSort Implementation:

http://www.ticalc.org/pub/86/asm/source/routines/qsort.zip

From 8080/8085 to 8086:

http://alexfru.narod.ru/os/c16/c16.html#To8086

The 8085 Microprocessor Simulator:

http://www.geocities.com/ransandanks/

Wiki:

http://pt.wikipedia.org/wiki/Quicksort#Assembly

zazik · 28 Σεπτεμβρίου 2005

@GCMH

einai pantws poli diskoli glossa

pragmatika 2 fores tin sinantisa tin proti mou hronia kai vasika eftihos epesa se enan trelameno freak agglo pou mou lei ok asto panw mou tha kanw ego tin ergasia :grin: ..giati na tou halaso hatiri?

pantws ine sigoura hrisimi na ksereis pos leitourgoune ta registers klp idika an ehis na kaneis me leitourgika (kernel mode) kai me to pos litourgoune ta processes.

Alla mehri ekei!!!!!!!! :grin: :grin:

diladi pistevo oti o kodikas pou edoses sto palikari gia Z80 kanei oti tha ekane mia alli glossa se 5-10 grammes. :grin: :grin:

e pos na to kanoume imaste ligo kakomathimena emeis i nea genia.

Palia (sta 80's) mou legane palioi programatistes oti grafane assembly kai legane kai Doksa ton Theo. :razz: :razz: :grin:

Kalo kouragio :wink: :wink:

Σύνδεση

quicksort se assembly gia 8085. HELP!

Προτεινόμενες αναρτήσεις

kopunisher

GCMH

GCMH

kopunisher

zazik

kopunisher

zazik

GCMH

kopunisher

zazik

GCMH

Sta

kopunisher

MrTryANalyzer

zazik

Αρχειοθετημένο

Σύνδεση