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:
includelib ArrayMan.lib
SortULng proto ; Unsigned Int64 array ptr, indicesPtr, lenOfArray
SortLng proto ; QWORD array ptr, indicesPtr, lenOfArray
SortDbl proto ; REAL8 array ptr, indicesPtr, lenOfArray
.data
array1 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,-9
array2 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.0
indx dd 30 dup(0)
.code
mainP proc
mov rcx,offset array1
mov rdx,offset indx
mov r8,30 ; array of 30 elements
call SortLng ;sort int64 array, result in 'indx'
mov rcx,offset array2
mov rdx,offset indx
mov r8,30 ; array of 30 elements
call SortDbl ;sort REAL8 array, result in 'indx'
ret
mainP endp
For sorting any kind of array, see the example is in my next post.
-------------------------
I've also posted this on GitHub (https://github.com/SilverfoxSystems/ArrayMan).
Hello,
Could you post an example demonstrating the usage of the library?
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
includelib ArrayMan.lib
SortAny proto ; lenOfArray, indicesPtr, ldValueMethod, cmpMethodLT, cmpMethodGT
option casemap:none
.data
array1 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,-9
indx dd 30 dup(0)
.code
.data
array1 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,-9
indx dd 30 dup(0)
.code
mainP proc
push rsi
push rdi
push rbx
mov rsi,offset array1 ; In this example, we'll use
mov rdi,offset indx ; RSI and RDI to point to bases of arrays
;call the QuickSort procedure
mov rcx,30 ; array of 30 elements
mov rdx,offset indx
mov r8,loadValueToCmp ; load pointer to procedure
mov r9,isItLess ; load pointer to procedure
mov r10,isItMore ; load pointer to procedure
call SortAny
;result in 'indx' at [RDI]
pop rbx
pop rdi
pop rsi
ret
mainP endp
loadValueToCmp 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 R8
SHL RAX, 3 ; multiply by 8 to get the offset in memory, since we are dealing with 8-byte integers
mov r8,qword ptr [rsi+rax] ;rsi points to base of array1
ret
loadValueToCmp endp
isItMore 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
ret
isGreater:
mov ax,-1
ret
isItMore endp
isItLess 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
ret
isItLess endp
Example of sorting an array of REAL8 numbers:
includelib ArrayMan.lib
option casemap:none
SortAny proto ; lenOfArray, indicesPtr, ldValueMethod, cmpMethodLT, cmpMethodGT
.data
array1 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.0
indx dd 30 dup(0)
.code
SortReal8Example proc
mov rsi,offset array1 ; In this example, we'll use
mov rdi,offset indx ; RSI and RDI to point to base of arrays
;call the QuickSort procedure
mov rcx,30 ; array of 30 elements
mov rdx,offset indx
mov r8,loadReal8ToCmp ; load pointer to procedure
mov r9,isItLessR8 ; load pointer to procedure
mov r10,isItMoreR8 ; load pointer to procedure
call SortAny
;result in 'indx' at [RDI]
ret
SortReal8Example endp
loadReal8ToCmp proc
fstp st(0)
SHL RAX, 3 ; multiply by 8, since we are dealing with 8-byte real numbers
fld real8 ptr[rsi+rax]
ret
loadReal8ToCmp endp
isItMoreR8 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 endp
isItLessR8 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
ret
isItLessR8 endp
For a VB.NET example that sorts 1000 randomly generated numbers(using ArrayMan.dll), please refer to this GitHub post (https://github.com/SilverfoxSystems/ArrayMan). You can also change the number of integers to generate and sort by editing a single line.
Here's the library(.lib) which doesn't refer the .dll.
Quote from: i Z ! on October 05, 2020, 02:46:49 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 :)
Quote from: guga on October 05, 2020, 07:21:34 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'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.
Please download v3.zip from the first post and see the updated example. By writing three short procedures, you can now sort any array.
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)'.
Sort algorithms in Assembler:
- Bubble sort, Cocktail sort, Heapsort, Direct Power, Direct Pick, Shell sort, Hoare (Quick Sort) (MASM) (https://www.cyberforum.ru/post2210209.html)
- Insertion sort (FASM) (https://www.cyberforum.ru/post5145942.html)
jj2007: Thanks for sharing that, strangely I didn't get those errors. Try if this is any better. This lib exports only SortAny procedure.
This one assembles fine. It throws a runtime error then, but that's probably because of my setup.
Quote from: jj2007 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.
Thanks for testing, does the error occur during the call to SortAny procedure?
Quote from: i Z ! on October 08, 2020, 11:57:08 PMThanks for testing, does the error occur during the call to SortAny procedure?
Yes.
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 |
This is a call to loadValueToCmp proc. Seems like your code is blocking its access from outside procedures. Only a guess...
:thumbsup:
mov rsi,offset array1 ; In this example, we'll use
mov rdi,offset indx ; RSI and RDI to point to bases of arrays
;call the QuickSort procedure
mov rcx,30 ; array of 30 elements
mov rdx,offset indx
mov r8,loadValueToCmp ; load pointer to procedure
mov r9, offset isItLess ; load pointer to procedure
mov r10, offset isItMore ; load pointer to procedure
SortAny proto
call SortAny ; somewhere in here appears my stack misaligned at... message; the procs!
;result in 'indx' or at [RDI]
...
xor rbx, rbx
.Repeat
mov rax, offset indx
lea rax, [rax+4*rbx]
mov eax, [rax]
Print Str$(" \nRes=%i", eax)
inc rbx
.Until rbx>=30
Res=29
Res=28
Res=27
Res=26
Res=25
Res=24
Res=23
Res=22
Res=21
Res=20
Res=19
Res=18
Res=17
Res=16
Res=15
Res=14
Res=13
Res=12
Res=11
Res=10
Res=9
Res=8
Res=7
Res=6
Res=5
Res=4
Res=3
Res=2
Res=1
Res=0
Quote from: jj2007 on October 09, 2020, 02:37:48 AM
:thumbsup:
That's great, thanks. I might use your code for printing out in my next examples.
To anyone interested, I've added an example for sorting REAL8 values in my "example post" (the 3rd post in this topic)
Corrections and performance improvements in v4. Examples also added to my first post.
Found on Quora (https://www.quora.com/My-program-with-a-bubble-sort-in-C-doesnt-work-Why)
Quotestd::sort uses a hybrid sorting system that switches algorithms for shorter arrays versus longer ones.
A quicksort is attempted, which of course chooses an initial partition size and a pivot.
If the partition size exceeds 2log(𝑁)
then the potential recursion depth would be excessive and cause delays and a lot of memory, so std::sort switches to heapsort, which is done in-place and does not require recursion.
If the partition size is small (standard implementation is 16) insertion sort is used instead of quicksort for that partition, because it outperforms quicksort on most CPU architectures that have very fast cache memory.