MIPS - Binary Search

[Dr.Fuzzy]

Παίδες λίγο βοήθεια στο παρακάτω πρόγραμμα assembly (MIPS) που υλοποιεί ένα αναδρομικό binary search σε sorted array. Μου επιστρέφει πάντα a στον $v0, ασχέτως τιμής που ψάχνω ($a0) και αδυνατώ να βρω τι πάει λάθος. Το τρέχω σε xspim.

 

>
.data
 first: # sorted array of 32 bit words.word 2, 3, 8, 10, 16, 21, 35, 42, 43, 50#, 64, 69#.word 70, 77, 82, 83, 84, 90, 96, 99, 100, 105, 111, 120last: # address just after sorted array .text.globl mainmain: # binary search in sorted array#   input:  search value in $a0#    base address of array in $a1#    last address of array in $a2#   output: address of needle in $v0 if found,#    0 in $v0 otherwiseli $a0, 35 # search valuela $a1, first # address of first array entryla $a2, last - 4 # address of last array entryjal binsearch # perform binary search li $v0, 10syscall binsearch:subu $sp, $sp, 4 # allocate 4 bytes on stacksw $ra, 4($sp) # save return address on stack subu $t0, $a2, $a1 # $t0 <- size of arraybnez $t0, search # if size > 0, continue search move $v0, $a1 # address of only entry in arraylw $t0, ($v0) # load the entrybeq $a0, $t0, return # equal to needle value? yes => returnli $v0, 0 # no => needle not in arrayb return # done, returnsearch:sra $t0, $t0, 3 # compute offset of middle entry m:sll $t0, $t0, 2 # $t0 <- ($t0 / 8) * 4addu $v0, $a1, $t0 # compute address of middle entry mlw $t0, ($v0) # $t0 <- middle entry mbeq $a0, $t0, return # m = needle? yes => returnblt $a0, $t0, go_left # needle less than m? yes =># search continues left of mgo_right:addu $a1, $v0, 4 # search continues right of mjal   binsearch # recursive callb return # done, returngo_left:move $a2, $v0 # search continues left of mjal binsearch # recursive callreturn:lw $ra, 4($sp) # recover return address from stackaddu $sp, $sp, 4 # release 4 bytes on stack j $ra # return to caller

[Dr.Fuzzy]

Ουδείς...;

[GCMH]

Εκείνο το li $v0, 10 πριν το syscall κάνει τη δουλειά... Δοκίμασε χωρίς αυτό...

[Dr.Fuzzy]

Εκείνο το li $v0, 10 πριν το syscall κάνει τη δουλειά... Δοκίμασε χωρίς αυτό...

 

 

 

Όχι δυστυχώς, αν το βγάλω επιστρέφει "unknown system call:  268501016" και το $v0= 10010018.  Καμιά ιδέα;

 

[GCMH]

Μα φίλε μου, έχεις την επιστροφή της συνάρτησης στον $v0. Ο ίδιος καταχωρητής χρησιμοποιείται και από την syscall. Άρα το αποτέλεσμά της συνάρτησης θα πρέπει να αντιγραφεί σε άλλο καταχωρητή της επιλογής σου. Μετά ο $v0 φορτώνεται με 10=0x0a για το syscall, ωστε να γίνει έξοδος από το πρόγραμμα. Γι' αυτό και σου επιστρέφει πάντα 0x0a...

[Dr.Fuzzy]

Μα φίλε μου, έχεις την επιστροφή της συνάρτησης στον $v0. Ο ίδιος καταχωρητής χρησιμοποιείται και από την syscall. Άρα το αποτέλεσμά της συνάρτησης θα πρέπει να αντιγραφεί σε άλλο καταχωρητή της επιλογής σου. Μετά ο $v0 φορτώνεται με 10=0x0a για το syscall, ωστε να γίνει έξοδος από το πρόγραμμα. Γι' αυτό και σου επιστρέφει πάντα 0x0a...

 

Κατανοητό, μπορείς αν δεν σου είναι κόπος να κάνεις την αλλαγή να το δοκιμάσω. (Διευκρινίζω ότι δεν πρόκειται για εργασία, ούτε είμαι φοιτητής, απλά το χρειάζομαι για να συγκρίνω με κάτι άλλο που με ενδιαφέρει)

[GCMH]

Δεν ξέρω από assembly σε MIPS αλλά φαντάζομαι ότι πριν από τα

li $v0, 10

syscall

 

θα μπορούσες να βάλεις

 

move	$t0, $v0

 

Και να τσεκάρεις τον $t0; Ειλικρινά δεν ξέρω αν διατηρείται ο $t0 μετά το syscall. Ενδεχομένως να σταματούσες την εκτέλεση με ένα Breakpoint, αν υποστηρίζεται, πριν το "li $v0, 10";

[Dr.Fuzzy]

Δεν ξέρω από assembly σε MIPS αλλά φαντάζομαι ότι πριν από τα

li $v0, 10

syscall

 

θα μπορούσες να βάλεις

 

move	$t0, $v0

 

Και να τσεκάρεις τον $t0; Ειλικρινά δεν ξέρω αν διατηρείται ο $t0 μετά το syscall. Ενδεχομένως να σταματούσες την εκτέλεση με ένα Breakpoint, αν υποστηρίζεται, πριν το "li $v0, 10";

όχι ούτε αυτό παίζει.

[ChRis6]

Για να τυπωσεις:

 

Στον $v0 βαζεις τιμη 1 , στον $a0 τη τιμη που θες να τυπωσεις και μετα system call.

 

 

Εσυ κάνεις μόνο system call για να σκοτωσεις το προγραμμα.Δεν τυπωνεις πουθενα κατι ή τουλάχιστον δεν βλεπω να τυπώνεις πουθενά κάτι.Είναι και περασμένη η ώρα...

[Dr.Fuzzy]

Για να τυπωσεις:

 

Στον $v0 βαζεις τιμη 1 , στον $a0 τη τιμη που θες να τυπωσεις και μετα system call.

 

 

Εσυ κάνεις μόνο system call για να σκοτωσεις το προγραμμα.Δεν τυπωνεις πουθενα κατι ή τουλάχιστον δεν βλεπω να τυπώνεις πουθενά κάτι.Είναι και περασμένη η ώρα...

Όπα, σε έχασα, μπορείς πάνω στο κώδικα να μου δείξεις τι εννοείς;

[ChRis6]

Κοιτα δεν εχω τσεκαρει την αναζητηση,για να δω αν εκει εχεις το προβλημα,δηλαδη αν οντως δουλευει οπως θα επρεπε.

 

Για να τερματισεις το προγραμμα πρεπει να βαλεις τη τιμη 10 στον καταχωρητη v0

li $v0,10
syscall

Για να δεις αν ολα πηγαν καλα στη συναρτηση,πρεπει να επιστρεφεις καποια τιμη,για να καταλαβεις αν βρεθηκε ή οχι η τιμη που ψαχνεις.Εστω οτι στον καταχωρητη $s2 βαζεις το αποτελεσμα και επιστρεφεις 0 αν δεν βρεθηκε η τιμή και 1 αν βρεθηκε.

 

Για να τυπωσεις αυτη τη τιμη,πρεπει να κανεις μια κληση συστηματος( syscall ).

 

Το αντιστοιχο printf("%d",result) της C σε mips assebly ειναι:

li $v0,1        # lew sto systhma oti thelw na kanw print
add $a0,$s2,$0  # bazw ston a0 th timh pou thelw na dw.Estw oti h sunarthsh epistrefei ston $s2
syscall

Και μετα κανεις exit με:

 

li $v0,10
syscall

Μπορει να κάνω και λαθος γιατι έχω πολύ καιρό να τα δω,αλλα γενικά σε τέτοια νερά κολυμπάς

 

edit: παντως μου φαινεται περιεργο να εχεις γραψει τοσο κωδικα και να σκαλωνεις σε κατι απλο.Μαλλον ετοιμο τον βρηκες ε ;

[Dr.Fuzzy]

 

Κοιτα δεν εχω τσεκαρει την αναζητηση,για να δω αν εκει εχεις το προβλημα,δηλαδη αν οντως δουλευει οπως θα επρεπε.

 

Για να τερματισεις το προγραμμα πρεπει να βαλεις τη τιμη 10 στον καταχωρητη v0

li $v0,10
syscall

Για να δεις αν ολα πηγαν καλα στη συναρτηση,πρεπει να επιστρεφεις καποια τιμη,για να καταλαβεις αν βρεθηκε ή οχι η τιμη που ψαχνεις.Εστω οτι στον καταχωρητη $s2 βαζεις το αποτελεσμα και επιστρεφεις 0 αν δεν βρεθηκε η τιμή και 1 αν βρεθηκε.

 

Για να τυπωσεις αυτη τη τιμη,πρεπει να κανεις μια κληση συστηματος( syscall ).

 

Το αντιστοιχο printf("%d",result) της C σε mips assebly ειναι:

li $v0,1        # lew sto systhma oti thelw na kanw print
add $a0,$s2,$0  # bazw ston a0 th timh pou thelw na dw.Estw oti h sunarthsh epistrefei ston $s2
syscall

Και μετα κανεις exit με:

 

li $v0,10
syscall

Μπορει να κάνω και λαθος γιατι έχω πολύ καιρό να τα δω,αλλα γενικά σε τέτοια νερά κολυμπάς

 

edit: παντως μου φαινεται περιεργο να εχεις γραψει τοσο κωδικα και να σκαλωνεις σε κατι απλο.Μαλλον ετοιμο τον βρηκες ε ;

Ναι, ετοιμότατο από εδώ University of Konstanz απο μια διάλεξη http://www.inf.uni-konstanz.de/dbis/teaching/ws0304/computing-systems/download/rs-05.pdf και η ειρωνεία είναι ότι είναι λάθος! Δεν το έκρυψα άλλωστε ούτε είπα ότι το έγραψα εγώ, δήλωσα εξαρχής ότι το θέλω για να συγκρίνω με κάτι άλλο που κάνω.

[Dr.Fuzzy]

Που χάθηκαν οι γκουρού σε MIPS...;