Solved

Help converting a C quicksort to assembly

Posted on 2008-10-31
7
2,399 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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

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

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
matchUp  challenge 9 72
bunnyEars challenge 6 68
wordmultiple challenge 12 93
What language/protocol is the Angular Chat? 2 16
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…
Windows Script Host (WSH) has been part of Windows since Windows NT4. Windows Script Host provides architecture for building dynamic scripts that consist of a core object model, scripting hosts, and scripting engines. The key components of Window…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

743 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

10 Experts available now in Live!

Get 1:1 Help Now