Solved

Help converting a C quicksort to assembly

Posted on 2008-10-31
7
2,476 Views
Last Modified: 2012-08-13
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.


;   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

Open in new window

0
Comment
Question by:BusyBeee
7 Comments
 

Author Comment

by:BusyBeee
ID: 22848066
Yea sorry first time trying to do this code/snippet.. apparently notepad++ does some werid tabstops or something... I redid the assembly part so you guys dont have to strain as hard trying to read it.

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
////////////////////////////////////////////////////////////////////////
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

Open in new window

0
 
LVL 3

Expert Comment

by:Blackninja2007
ID: 22848290
which c are you using C++ (VS2003/5/ or 8 ) or something else ?
0
 

Author Comment

by:BusyBeee
ID: 22853216
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
;---------------------------------------
; 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

Open in new window

0
Efficient way to get backups off site to Azure

This user guide provides instructions on how to deploy and configure both a StoneFly Scale Out NAS Enterprise Cloud Drive virtual machine and Veeam Cloud Connect in the Microsoft Azure Cloud.

 

Assisted Solution

by:rfqu
rfqu earned 166 total points
ID: 22856743
Usually C compilers have an option to generate assembly source. Use this generated source as a starting point and then optimize it step by step.
0
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 166 total points
ID: 22871088
My advice is don't convert it to assembly if you don't need to.  Any speed you gain will, in my opinion, be outweighed by unreliability because assembly is more difficult to verify than C.  Any speedup of the inner loop will be small compared to the cost of cache misses anyway.

If you could look at the bigger picture and find an algorithmic improvement for what you're tring to do, that would be more worthwhile.
0
 

Accepted Solution

by:
BusyBeee earned 0 total points
ID: 22871576
Its ok I got it worked out.  Mainly my problem was the push pop of registers when your preforming the recursion.  I understand whatcha mean nova, but this is more for learning assembly, not just becuase I am trying to make a sort more efficient.
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 22871896
To learn how to do it is definitely a good enough reason.
0

Featured Post

Ransomware-A Revenue Bonanza for Service Providers

Ransomware – malware that gets on your customers’ computers, encrypts their data, and extorts a hefty ransom for the decryption keys – is a surging new threat.  The purpose of this eBook is to educate the reader about ransomware attacks.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
no14 challenge 14 69
My project did see openJDK that I installed. What could be the problem 7 143
bunnyEars2 challenge 6 134
Problem to open Excel file 15 136
One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

803 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question