BusyBeee
asked on
Help converting a C quicksort to assembly
I need to translate a C quicksort into assembly to use in a quicksort subroutine and I wanted to make sure I did this part correctly. I think everything is ok until I get to figuring out how to keep doing the quick sort recursively... do I need to like set my registers before I reenter my quick method?
I attached my C and then under that my assembler version to compare.
I attached my C and then under that my assembler version to compare.
; quick (int list[], int l, int r)
;
; // inputs: 1. The address of the array with n elements (0...n-1)
; // 2. 'l' which is the left index
; // 3. 'r' which is the right index
; {
; int i,j,x,w; // i,j are indices x,w are values
;
; i=l; j=r; // i starts at left, j starts at right
; x=list[(l+r) / 2]; // x is the selected value
; while (i<=j) // do until i and j cross
; {
; while (x>list[i]) {i++;} // find value equal or greater than selected
; while (x<list[j]) {j--;} // find value equal or less than selected
; if (i<=j) // swap values and inc i and dec j
; {
; w=list[i];
; list[i]=list[j];
; list[j]=w;
; i++; j--;
; }
; }
; if (l<j) quick(list,l,j); // sort the left side
; if (i<r) quick(list,i,r); // sort the right side
; }
////////////////////////////////////////////////////////////////////////
my version in assembly, intel 8086, compiled in masam
////////////////////////////////////////////////////////////////////////
quick: ;!!!!!!!!!!!I NEED TO SET SI AND DI BEFORE THIS!
mov si,bx ;associating si as my left
mov di,dx ;!!!!!!!!!!!associating di with my right (I DONT THINK I CAN DO THIS!)
mov al,di ;getting my pivot value
add al,si ;preparing to get my pivot
mov cl, 2 ;preparing to divide (si + di )/2)) = pivot
div cl ;ax/cl, al should have my quotent (which is my pivot!)
mloop:
jmp test_m ;main initial check
mrep:
leftLoop: ;left inner while loop
jmp lcheck ; left initial check
lrep: ;left rep
inc si ; !!!!!!!!!!!increment the left further down my stack i++ (SHOULD I DO [] OR NOT!)
lcheck: ;left check
cmp al,[si] ; if (al > [si])
ja lrep ; jump up to my repeating step
rightLoop: ;right inner while loop
jmp rcheck ; right initial check
rrep: ;right rep
dec di ; !!!!!!!!!!!decrement my right further up my stack j-- (SHOULD I DO [] OR NOT!)
rcheck: ;
cmp al,[di] ;if (al < [di])
jl rrep ;jump up to my repeating step
cmp si,di ;if (si < di) hopefully comparable to if (i <=j)
jae mcheck ;else skip over this section
;!!!!!!!!!!!can I resue cl like this?
mov cl,[si] ;w = list[i]
mov ch,[di] ;!!!!!!!!!!!cant compare 2 memory... need to do this as well?
mov [si],ch ;moves list[j]'s value into list[i]'s value
mov [di],cl ;moves list[i]'s value into list[j]'s value
;!!!!!!!!!!!i think.. i donnt need one of the cl/ch moves and can use al ... but i was iffy
inc si ;increment the left further down my stack i++
dec di ;decrement my right further up my stack j--
mcheck:
cmp si,di ;if (left <= right)
jbe mrep ;jump up to my main repeating step!
;!!!!!!!!!!!fix my bp and dx for the next recursive loop.... ????
ret ;return
which c are you using C++ (VS2003/5/ or 8 ) or something else ?
ASKER
I was just using C(plain)... but I know the code is correct, I was provided with it. I just need to convert it to assembly
so I worked on it some more... I realized that 1 my al was justthe index... I needed it to be equal to the daat that was at al, and I cant just do [si] or [di] I need to do [bx+si] etc where bx is the start of my data... however right now I am getting an infite loop...after commenting / trying to print data I believe it has something to do with the recursion that I implemented... any help is appreciated
I think the problem is my if checks for the recursion is always true and its not stopping (causing me to loop indefinitely. Although I am having trouble seeing exactly where this is happening
so I worked on it some more... I realized that 1 my al was justthe index... I needed it to be equal to the daat that was at al, and I cant just do [si] or [di] I need to do [bx+si] etc where bx is the start of my data... however right now I am getting an infite loop...after commenting / trying to print data I believe it has something to do with the recursion that I implemented... any help is appreciated
I think the problem is my if checks for the recursion is always true and its not stopping (causing me to loop indefinitely. Although I am having trouble seeing exactly where this is happening
;---------------------------------------
; Quicksort registers:
; al = x = random value in the list
; bx = address of the list
; ch = used in swap
; cl = w = used in swap
; dx = r = right index
; si = i = index
; di = j = index
; bp = l = left index
; In the call to quicksort
; - bx contains the address of the list
; - bp contains the left most index
; - dx contains the right most index
;
; *** warning ***
; Be careful about the use of signed versus unsigned tests.
; The i and j index values are signed and j can go negative,
; so be sure to use signed tests on i and j.
; The data values for this assignment are unsigned,
; so be sure to use unsigned tests on the data values.
;
;---------------------------------------
quick: ;!!!!!!!!!!!I NEED TO SET SI AND DI BEFORE THIS!
mov si,bp ;associating si as my left
mov di,dx ;!!!!!!!!!!!associating di with my right (I DONT THINK I CAN DO THIS!)
mov ax,di ;getting my pivot value
add ax,si ;preparing to get my pivot
mov cl, 2 ;preparing to divide (si + di )/2)) = pivot
div cl ;ax/cl, al should have my quotent (which is my pivot!)
;only counted the index here I need to add this index into the offset
;now I have X in al after the push pop operation
;
push bx ;after you do the add bx is changed... we dont want to change the value of bx
mov ah,0 ;this is a copy of bx.. after we manupilate it we get it back from the stack
add bx,ax
mov al,[bx]
pop bx
mloop:
jmp mcheck ;main initial check
mrep:
leftLoop: ;left inner while loop
jmp lcheck ; left initial check
lrep: ;left rep
inc si ; !!!!!!!!!!!increment the left further down my stack i++ (SHOULD I DO [] OR NOT!)
lcheck: ;left check
cmp al,[bx+si] ; if (al > [si])
ja lrep ; jump up to my repeating step
rightLoop: ;right inner while loop
jmp rcheck ; right initial check
rrep: ;right rep
dec di ; !!!!!!!!!!!decrement my right further up my stack j-- (SHOULD I DO [] OR NOT!)
rcheck: ;
cmp al,[bx+di] ;if (al < [di])
jl rrep ;jump up to my repeating step
cmp si,di ;if (si < di) hopefully comparable to if (i <=j)
jae mcheck ;else skip over this section
;!!!!!!!!!!!can I resue cl like this?
mov cl,[bx+si] ;w = list[i]
mov ch,[bx+di] ;!!!!!!!!!!!cant compare 2 memory... need to do this as well?
mov [bx+si],ch ;moves list[j]'s value into list[i]'s value
mov [bx+di],cl ;moves list[i]'s value into list[j]'s value
;!!!!!!!!!!!i think.. i donnt need one of the cl/ch moves and can use al ... but i was iffy
inc si ;increment the left further down my stack i++
dec di ;decrement my right further up my stack j--
mcheck:
cmp si,di ;if (left <= right)
jbe mrep ;jump up to my main repeating step!
;!!!!!!!!!!!fix my bp and dx for the next recursive loop.... ????
cmp bp,di ;we arent getting out of here
jae else_if
push si
push bp
push di
push dx
mov dx,di ;changes the value of r in dx for the next recursive call
call quick
pop dx
pop di
pop bp
pop si
else_if:
cmp si,dx
jae else_
push si
push bp
push di
push dx
mov bp,si ;changes the value of l in bp for the next recursive call
call quick
pop dx
pop di
pop bp
pop si
else_:
ret ;return
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
To learn how to do it is definitely a good enough reason.
ASKER
Hope that helps
also wherever you see a !!!!!!!!!!!!! in the comments is where I was unsure if I did that line correctly (as explained in the comments directly after the !
If this doesnt work ill just upload as a file
Open in new window