### Author Topic: QuickSort algorithm  (Read 3002 times)

#### i Z !

• Member
• Posts: 125
##### QuickSort algorithm
« on: October 04, 2020, 07:56:34 PM »
I converted an old non-recursive QuickSort program written in BASIC into ml64 asm.
It doesn't sort the original array, but it writes indices of the array into another array in an ascending order.

Entry points: SortLng, SortULng, SortDbl and SortAny

The first three expect 3 arguments to be passed:
RCX - Pointer to the beginning of array of 64-bit integers or REAL8 to sort
RDX - Pointer to the beginning of array of 32-bit integers which will hold indices of the array in first argument. Its size must be at least the number given in R8
R8 - Number of items to examine in the array

The call destroys RAX, RCX, RDX, R8, R9, R10 and R11 registers.

EDIT: Example demonstrating sorting of Int64 and REAL8 arrays:

Code: [Select]
`includelib ArrayMan.libSortULng proto ;  Unsigned Int64 array ptr, indicesPtr, lenOfArraySortLng proto ;  QWORD array ptr, indicesPtr, lenOfArraySortDbl proto ;  REAL8 array ptr, indicesPtr, lenOfArray.dataarray1 dq 20, 19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9array2 real8 20.0, 19.0, 18.0, 17.0, 16.0, 15.0, 14.0, 13.0, 12.0, 11.0, 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0, -1.0, -2.0, -3.0, -4.0, -5.0, -6.0, -7.0, -8.0, -9.0indx dd 30 dup(0).codemainP procmov rcx,offset array1mov rdx,offset indxmov r8,30 ; array of 30 elementscall SortLng ;sort int64 array, result in 'indx'mov rcx,offset array2mov rdx,offset indxmov r8,30 ; array of 30 elementscall SortDbl ;sort REAL8 array, result in 'indx'retmainP endp`
For sorting any kind of array, see the example is in my next post.

-------------------------

I've also posted this on GitHub.
« Last Edit: October 11, 2020, 06:51:26 PM by i Z ! »
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!

#### Vortex

• Member
• Posts: 2583
##### Re: QuickSort algorithm
« Reply #1 on: October 04, 2020, 09:18:41 PM »
Hello,

Could you post an example demonstrating the usage of the library?

#### i Z !

• Member
• Posts: 125
##### Examples
« Reply #2 on: October 05, 2020, 02:44:23 AM »
Here's the deal: write your own delegate functions to compare array items. This gives you the ability to sort any kind of array.
All three delegate functions are called with index in EAX. The procedures have to find the array element based on this index.

1st procedure: stores the value of array element with index passed in EAX
2nd procedure: Compares that value with array element with index in EAX, returns True if less
3rd procedure: Compares the stored value with array element with index in EAX, returns True if bigger

Code: [Select]
`includelib ArrayMan.libSortAny proto ; lenOfArray, indicesPtr, ldValueMethod, cmpMethodLT, cmpMethodGToption casemap:none.dataarray1 dq 20, 19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9indx dd 30 dup(0).code.dataarray1 dq 20, 19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9indx dd 30 dup(0).codemainP procpush rsipush rdipush rbxmov rsi,offset array1 ; In this example, we'll usemov rdi,offset indx   ; RSI and RDI to point to bases of arrays;call the QuickSort proceduremov rcx,30 ; array of 30 elementsmov rdx,offset indxmov r8,loadValueToCmp ; load pointer to proceduremov r9,isItLess ; load pointer to proceduremov r10,isItMore ; load pointer to procedurecall SortAny;result in 'indx' at [RDI]pop rbxpop rdipop rsiretmainP endploadValueToCmp proc; To-do: Store array item with index given in EAX. This value will be compared with other array items in the next two procedures.;You can use RAX, RDI, RSI, R8 or FPU registers to store the pivot value.;These registers will retain their values during any subsequent calls to LTmethod and GTmethod procedures.;All other registers need to be preserved on return from all the procedures.;If you don't know what pivot is and you don't want to dive into QuickSort algorithm to find out,;just imagine it as a variable which holds one of the array items you will need to compare to other array elements in the two mentioned procedures.;Example here demonstrates loading an 8-byte integer from an array into R8SHL RAX, 3 ; multiply by 8 to get the offset in memory, since we are dealing with 8-byte integersmov r8,qword ptr [rsi+rax] ;rsi points to base of array1retloadValueToCmp endpisItMore proc;  To-Do: Compare item with index in EAX with pivot value; and return True if pivot is greater than array item    SHL RAX, 3     cmp r8,[rsi+rax]    jg isGreater    xor ax,ax    retisGreater:      mov ax,-1    retisItMore endpisItLess proc;  To-Do: Compare item with index in EAX with pivot value; and return True(in AX) if pivot is less than array item  SHL RAX, 3   cmp r8,[rsi+rax]  jl isLess  xor rax,rax  ret  isLess:        mov ax,-1    retisItLess endp`
Example of sorting an array of REAL8 numbers:

Code: [Select]
`includelib ArrayMan.liboption casemap:noneSortAny proto ; lenOfArray, indicesPtr, ldValueMethod, cmpMethodLT, cmpMethodGT.dataarray1 real8 20.0, 19.0, 18.0, 17.0, 16.0, 15.0, 14.0, 13.0, 12.0, 11.0, 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0, -1.0, -2.0, -3.0, -4.0, -5.0, -6.0, -7.0, -8.0, -9.0indx dd 30 dup(0).codeSortReal8Example procmov rsi,offset array1 ; In this example, we'll usemov rdi,offset indx   ; RSI and RDI to point to base of arrays;call the QuickSort proceduremov rcx,30 ; array of 30 elementsmov rdx,offset indxmov r8,loadReal8ToCmp ; load pointer to proceduremov r9,isItLessR8 ; load pointer to proceduremov r10,isItMoreR8 ; load pointer to procedurecall SortAny;result in 'indx' at [RDI]retSortReal8Example endploadReal8ToCmp proc  fstp st(0)  SHL RAX, 3 ; multiply by 8, since we are dealing with 8-byte real numbers  fld real8 ptr[rsi+rax] retloadReal8ToCmp endpisItMoreR8 proc   SHL RAX, 3     fcom real8 ptr [rsi+rax]    fnstsw ax   and    ax, 0100011100000000B     jz     isGreaterR    xor ax,ax    ret isGreaterR:      not ax    ret isItMoreR8 endpisItLessR8 proc  SHL RAX, 3    fcom real8 ptr [rsi+rax]   fnstsw ax    and    ax, 0100011100000000B     cmp    ax, 100h ; I'm cheating here by assuming there's no invalid FP values in the array    retisItLessR8 endp`
For a VB.NET example that sorts 1000 randomly generated numbers(using ArrayMan.dll), please refer to this GitHub post. You can also change the number of integers to generate and sort by editing a single line.
« Last Edit: October 11, 2020, 06:54:02 PM by i Z ! »
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!

#### i Z !

• Member
• Posts: 125
##### Re: QuickSort algorithm
« Reply #3 on: October 05, 2020, 02:46:49 AM »
Here's the library(.lib) which doesn't refer the .dll.
« Last Edit: October 08, 2020, 10:00:11 PM by i Z ! »
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!

#### guga

• Member
• Posts: 1357
• Assembly is a state of art.
##### Re: QuickSort algorithm
« Reply #4 on: October 05, 2020, 07:21:34 AM »
Here's the library(.lib) which doesn't refer the .dll.

Can you convert it to 32 bits so we can also test for non64 version ? This looks much similar to one JJ did. I wonder how fast it is to be compared with the others in the forum. Doing a benchmark could be good :)
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

#### i Z !

• Member
• Posts: 125
##### Re: QuickSort algorithm
« Reply #5 on: October 05, 2020, 07:48:27 AM »
Can you convert it to 32 bits so we can also test for non64 version ?

I don't think I will. I like x64 because I can store frequently accessed variables into registers.
This project fitted x64 perfectly, since there were many of such variables. There's no .DATA block in my code :)
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!

#### i Z !

• Member
• Posts: 125
« Reply #6 on: October 06, 2020, 03:27:47 AM »
I've updated the file in my initial post and the example. It supports real8 arrays now.

Update: Oops, I forgot to write a RET statement in my code, therefore SortDbl proc didn't work.

Update2: Still doesn't work.. Will update soon.
« Last Edit: October 06, 2020, 11:05:44 PM by i Z ! »
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!

#### i Z !

• Member
• Posts: 125
##### Sort arrays of any type
« Reply #7 on: October 08, 2020, 09:34:10 PM »
Please download v3.zip from the first post and see the updated example. By writing three short procedures, you can now sort any array.
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!

#### jj2007

• Member
• Posts: 11550
• Assembler is fun ;-)
##### Re: QuickSort algorithm
« Reply #8 on: October 08, 2020, 09:55:12 PM »
Code: [Select]
`POLINK: error: Symbol 'lup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'doLup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut2' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'lup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'doLup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut2' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'lup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'doLup1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut2' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'aut0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'lup01' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'lup0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'ni0' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'ni1' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.POLINK: error: Symbol 'ni2' is multiply defined: 'ArrayMan.lib(main.obj)' and 'ArrayMan.lib(main.obj)'.`

#### Mikl__

• Member
• Posts: 1133
##### Re: QuickSort algorithm
« Reply #9 on: October 08, 2020, 10:26:50 PM »

#### i Z !

• Member
• Posts: 125
##### Re: QuickSort algorithm
« Reply #10 on: October 08, 2020, 10:33:17 PM »
jj2007: Thanks for sharing that, strangely I didn't get those errors. Try if this is any better. This lib exports only SortAny procedure.
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!

#### jj2007

• Member
• Posts: 11550
• Assembler is fun ;-)
##### Re: QuickSort algorithm
« Reply #11 on: October 08, 2020, 11:44:27 PM »
This one assembles fine. It throws a runtime error then, but that's probably because of my setup.

#### i Z !

• Member
• Posts: 125
##### Re: QuickSort algorithm
« Reply #12 on: October 08, 2020, 11:57:08 PM »
This one assembles fine. It throws a runtime error then, but that's probably because of my setup.
Thanks for testing, does the error occur during the call to SortAny procedure?
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!

#### jj2007

• Member
• Posts: 11550
• Assembler is fun ;-)
##### Re: QuickSort algorithm
« Reply #13 on: October 09, 2020, 12:17:20 AM »
Thanks for testing, does the error occur during the call to SortAny procedure?

Yes.

Code: [Select]
`0000000140001849   | 48 8B C2                 | mov rax,rdx                       |000000014000184C   | E8 DF FF FF FF           | call 140001830                    |0000000140001851   | FF 15 59 1B 00 00        | call qword ptr ds:[1400033B0]     | <<<<<<<<<<<<<<<<<<<0000000140001857   | 44 8B D9                 | mov r11d,ecx                      |000000014000185A   | 41 FF CB                 | dec r11d                          |000000014000185D   | 44 8B E2                 | mov r12d,edx                      |`

#### i Z !

• Member
• Posts: 125
##### Re: QuickSort algorithm
« Reply #14 on: October 09, 2020, 01:42:09 AM »
This is a call to loadValueToCmp proc. Seems like your code is blocking its access from outside procedures. Only a guess...
I bit a bit,
got bites from bytes.
I'll ram'em back in their RAM
and machine-gun the shit out of their f*in machine...

Try out my Automatized ASM Editor for Windows 10 for 30 days. Also visit silverfox.systems/ace!