Two sort algos.

[hutch--]

I have started to convert some of the simpler sorts from the 32 bit versions to 64 bit MASM, the first is a bubble sort which is about as useful as a hip pocket in a singlet in all but a few specialised instances and an insertion sort which is suitable for small counts, both have their uses in hybrid sort algos that use more than one design, these two are basically "trimmer" algos that address a problem with more complex sorts that handle large data but are a bit clunky on small counts, something common with quick sorts.

I have yet to convert any of the quick sort designs as stack recursion with the Win64 ABI is not immediately a simple task where you can keep dumping stack parameters with each ascending iteration as you could in Win32.

[jj2007]

stack recursion with the Win64 ABI is not immediately a simple task where you can keep dumping stack parameters with each ascending iteration as you could in Win32.

As long as you don't call a Windows API inside the sort proc, you can do whatever you want, no?

[hutch--]

I have to think about that one, there has to be a way to do it as the shadow space for the registers will persist after each iteration but its likely that there will need to be a lot more stack space.

[jj2007]

as the shadow space for the registers will persist

You write an entry proc that handles shadow space according to the ABI but then calls the "real" recursive sort proc with no restrictions.

[nidud]

Here's a 64-bit version of qsort using the stack maintaining the shadow space within a loop.

Code: [Select]

qsort proc uses rsi rdi rbx p:ptr, n:qword, w:qword, compare:LPQSORTCMD

local stack_level

    mov rax,n
    .if rax > 1

        dec rax
        mul w
        mov rsi,p
        lea rdi,[rsi+rax]
        mov stack_level,0

        .while  1

            mov rcx,w
            lea rax,[rdi+rcx]   ; middle from (hi - lo) / 2
            sub rax,rsi
            .ifnz
                xor rdx,rdx
                div rcx
                shr rax,1
                mul rcx
            .endif

            sub rsp,0x20

            lea rbx,[rsi+rax]
            .ifsd compare(rsi, rbx) > 0
                memxchg(rsi, rbx, w)
            .endif
            .ifsd compare(rsi, rdi) > 0
                memxchg(rsi, rdi, w)
            .endif
            .ifsd compare(rbx, rdi) > 0
                memxchg(rbx, rdi, w)
            .endif
            mov p,rsi
            mov n,rdi

            .while  1

                mov rax,w
                add p,rax
                .if p < rdi

                    .continue .ifsd compare(p, rbx) <= 0
                .endif

                .while  1

                    mov rax,w
                    sub n,rax

                    .break .if n <= rbx
                    .break .ifsd compare(n, rbx) <= 0
                .endw

                mov rdx,n
                mov rax,p
                .break .if rdx < rax
                memxchg(rdx, rax, w)

                .if rbx == n

                    mov rbx,p
                .endif
            .endw

            mov rax,w
            add n,rax

            .while  1

                mov rax,w
                sub n,rax

                .break .if n <= rsi
                .break .ifd compare(n, rbx)
            .endw

            add rsp,0x20

            mov rdx,p
            mov rax,n
            sub rax,rsi
            mov rcx,rdi
            sub rcx,rdx

            .ifs rax < rcx

                mov rcx,n

                .if rdx < rdi

                    push rdx
                    push rdi
                    inc stack_level
                .endif

                .if rsi < rcx

                    mov rdi,rcx
                    .continue
                .endif
            .else
                mov rcx,n

                .if rsi < rcx

                    push rsi
                    push rcx
                    inc stack_level
                .endif

                .if rdx < rdi

                    mov rsi,rdx
                    .continue
                .endif
            .endif

            .break .if !stack_level

            dec stack_level
            pop rdi
            pop rsi
        .endw
    .endif
    ret

qsort endp