Solved

Help converting a C quicksort to assembly

Posted on 2008-10-31
7
2,437 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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
XML::LibXML and Xpath syntax How do I get attribute of sibling 2 116
Choosing the right language for new project 8 61
Problem to event 3 76
Math Question 1 75
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…

919 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

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now