Selection Sort

; ----------------------------------------------------------------------------
; SelectionSort.asm
;
; Selection sort is a sorting algorithm, specifically an in-place comparison sort.
;
; ----------------------------------------------------------------------------

;
;      10 000 =   0.040820039808750 sec
;      50 000 =   0.907835304737091 sec
;     100 000 =   4.108306407928467 sec
;     200 000 =  16.423355102539062 sec
;   1 000 000 = 421.7449951171875 sec (7min)
;
; -------- Constants -------
;
    MAX_NUMBERS equ 50000

    %define SORTDESC 0
    %if SORTDESC > 0
        CMPMASK equ 0xFFFF
    %else
        CMPMASK equ 0x0000
    %endif
    NULL equ 0
    STD_OUTPUT_HANDLE equ -11
    MB_OK equ 0x00000000
    INVALID_HANDLE_VALUE equ -1
    CRYPT_NEWKEYSET equ 0x8
    PROV_RSA_FULL equ 1
    CREATE_ALWAYS equ 2
    GENERIC_WRITE equ 0x40000000
;
; ---- End of Constants ----
;

    global _main

    extern  _GetStdHandle@4
    extern  _WriteFile@20
    extern _WriteConsoleA@20
    extern  _ExitProcess@4
    extern  _MessageBoxA@16
    extern _GetLastError@0
    extern _AllocConsole@0
    extern _AttachConsole@4
    extern _CryptGenRandom@12
    extern _CryptAcquireContextA@20
    extern _CryptReleaseContext@8
    extern _CreateFileA@28
    extern _CloseHandle@4
    extern _QueryPerformanceCounter@4
    extern _QueryPerformanceFrequency@4

%macro MessageBox 2
    ; int WINAPI MessageBox(HWND hWnd, LPCTSTR lpText, LPCTSTR lpCaption, UINT uType );
    push MB_OK
    push %2
    push %1
    push 0
    call _MessageBoxA@16
%endmacro

%macro WriteFile 3
;HANDLE WINAPI CreateFile( LPCTSTR lpFileName, DWORD dwDesiredAccess, DWORD dwShareMode, LPSECURITY_ATTRIBUTES lpSecurityAttributes, DWORD dwCreationDisposition, DWORD dwFlagsAndAttributes, HANDLE hTemplateFile);
push NULL
push NULL
push CREATE_ALWAYS
push NULL
push NULL
push GENERIC_WRITE
push %1
call _CreateFileA@28

push eax

; BOOL WINAPI WriteFile(HANDLE hFile, LPCVOID lpBuffer,DWORD nNumberOfBytesToWrite, LPDWORD lpNumberOfBytesWritten, LPOVERLAPPED lpOverlapped);
push NULL
push Temp
push %3
push %2
push eax
call _WriteFile@20

; BOOL WINAPI CloseHandle( HANDLE hObject );
call _CloseHandle@4
%endmacro

%macro Print 2
    ; BOOL WINAPI WriteConsole( HANDLE hConsoleOutput, const VOID *lpBuffer, DWORD nNumberOfCharsToWrite, LPDWORD lpNumberOfCharsWritten, LPVOID lpReserved );
    push    0
    push    NumberOfCharsWritten
    push    %2
    push    %1
    push    DWORD [Handle]
    call    _WriteConsoleA@20
%endmacro

%macro PrintLn 0
    Print NewLine, 2
%endmacro

%macro FillRandom 0
    mov byte [Numbers], 65
    push Numbers
    push MAX_NUMBERS
    push dword [CryptProv]
    call _CryptGenRandom@12
%endmacro

;  EDX - address to memory
;  ECX - byte count
PrintReversedHex:
    push edx
    push ecx
    Print HEXStart, 2
    pop ecx
    pop edx
    mov ebx, ecx
    .loop:
        push ecx
        ;mov eax, ecx
        ;sub eax, ecx
        mov al, byte [edx+ecx-1]
        and eax, 0xFF
        div byte [m16]
        xor ecx, ecx
        mov cl, al
        add ecx, HEX
        push edx
        push eax
        Print ecx, 1
        pop eax
        xor ecx, ecx
        mov cl, ah
        add ecx, HEX
        Print ecx, 1
        pop edx
        pop ecx
    loop .loop
ret

MakeHex:
    mov ecx, MAX_NUMBERS
    .loop:
        xor eax, eax
        mov al, byte [Numbers+ecx-1]
        xor ebx, ebx
        div byte [m16]
        mov bl, al
        mov al, byte [HEX+ebx]
        xor ebx, ebx
        mov bl, ah
        mov ah, byte [HEX+ebx]
        push eax
        mov eax, ecx
        sub eax, 1
        xor edx, edx
        mul dword [m6]
        mov ebx, eax
        pop eax
        mov byte [NumbersHEX+ebx], '0'
        mov byte [NumbersHEX+1+ebx], 'x'
        mov byte [NumbersHEX+2+ebx], al
        mov byte [NumbersHEX+3+ebx], ah
        mov byte [NumbersHEX+4+ebx], 13
        mov byte [NumbersHEX+5+ebx], 10
    loope .loop
ret

%macro Fill_xmm1_With_al 0
    PINSRB xmm0, al, 0
    PINSRB xmm0, al, 1
    PINSRB xmm0, al, 2
    PINSRB xmm0, al, 3
    PSHUFD xmm1, xmm0, 0
    PADDB xmm1, xmm4
    ;mov edi, esi
%endmacro

%macro CheckReg 1
        PEXTRB eax, xmm0, %1
        cmp eax, CMPMASK
        jne .not%1
            PEXTRB eax, xmm2, %1
            cmp esi, eax
            %if SORTDESC > 0
                jae .not%1
            %else
                jb .not%1
            %endif
            mov edx, ebx
            add edx, %1
            mov esi, eax
        .not%1:
%endmacro

%macro Swap 0
    mov al, byte [Numbers+ecx]
    xchg byte [Numbers+edx], al
    mov byte [Numbers+ecx], al
%endmacro

;
;  Sort - Selection sort
;
;  ecx - i, position in array
;  ebx - j, position in array
;  edx - min or max index
;
Sort:
    xor eax,eax
    xor ecx, ecx
    xor edx, edx
.loop:
    mov ebx, ecx
    add ebx, 1
    mov al, byte [Numbers+ecx]
    .loop2:
        cmp byte [Numbers+ebx], al
        %if SORTDESC > 0
          jb .not
        %else
          jae .not
        %endif
            mov edx, ebx
            mov al, byte [Numbers+edx]
        .not:
        add ebx, 1
        cmp ebx, MAX_NUMBERS
    jb .loop2
    cmp edx, ecx
    je .continue
        Swap
    .continue:
    add ecx, 1
    cmp ecx, MAX_NUMBERS
    jbe .loop
ret

TimeElapsed:
; BOOL WINAPI QueryPerformanceCounter( LARGE_INTEGER *lpPerformanceCount );
    MOVQ xmm2, qword [Frequency]
    PEXTRD eax, xmm2, 1
    PEXTRD ebx, xmm2, 0
    or  eax,ebx
    jz .skip
      push CurrentCounter
      call _QueryPerformanceCounter@4
      MOVQ xmm0, qword [CurrentCounter]
      MOVQ xmm1, qword [LastCounter]
      MOVQ qword [LastCounter], xmm0
      PSUBQ xmm0, xmm1
      MOVQ qword [Temp], xmm0
      FILD qword [Frequency]
      FST ST1
      FILD qword [Temp]
      FTST
      jbe .skip
      FDIV ST1
      FST dword [DeltaTime]
    .skip:
ret


%macro Header 0
    mov     ebp, esp
    sub     esp, 4

    ; BOOL WINAPI AttachConsole( DWORD dwProcessId );
    push -1
    call _AttachConsole@4
    cmp eax, 0
    jz .error
    jmp .no_error
    .error:
        ; BOOL WINAPI AllocConsole(void);
        call _AllocConsole@0
    .no_error:
    ; HANDLE WINAPI GetStdHandle( DWORD nStdHandle );
    push    STD_OUTPUT_HANDLE
    call    _GetStdHandle@4
    cmp eax, NULL
    je LabelError
    cmp eax, INVALID_HANDLE_VALUE
    je LabelError
    mov [Handle], eax

    push NULL
    push PROV_RSA_FULL
    push NULL
    push Key
    push CryptProv
    call _CryptAcquireContextA@20
    cmp eax,0
    jne success
    push CRYPT_NEWKEYSET
    push PROV_RSA_FULL
    push NULL
    push Key
    push CryptProv
    call _CryptAcquireContextA@20
    success:
    ; BOOL WINAPI QueryPerformanceFrequency( LARGE_INTEGER *lpFrequency );
    push Frequency
    call _QueryPerformanceFrequency@4
    push LastCounter
    call _QueryPerformanceCounter@4
%endmacro

%macro Footer 0
    push 0
    push dword [CryptProv]
    call _CryptReleaseContext@8
    jmp Exit
    LabelError:
        MessageBox TextExit, TextError
    Exit:
    call FunctionExit
%endmacro


section .text

FunctionExit:
    ; ExitProcess(0)
    push    0
    call    _ExitProcess@4

    ; never here
    hlt

NewLine: db 10,10
m6: dd 6
m16: db 16
align 16
n128: db 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h, 80h
HEXStart: db '0x'
HEX: db '0123456789ABCDEF'
Key: db 'ThisKey',0
FileName: db 'File.dat',0
FileNameSorted: db 'FileSorted.dat',0
FileNameHEX: db 'FileHex.txt',0
FileNameSortedHEX: db 'FileSortedHex.txt',0
Author:  db 'davispuh',10
AuthorLength equ $-Author
Tittle:  db 'Selection Sort',10
TittleLength equ $-Tittle
Done: db 'Done!',0
TextError: db      'Error!', NULL
TextExit:  db      'Error occurred program will exit.', NULL

_main:
    Header
    PrintLn
    Print Author, AuthorLength
    Print Tittle, TittleLength

    %if SORTDESC > 0
        mov eax, 0x00000000
    %else
        mov eax, 0xFFFFFFFF
    %endif

    mov dword [padding], eax
    mov dword [padding+4], eax
    mov dword [padding+8], eax
    mov dword [padding+12], eax

    FillRandom

    WriteFile FileName, Numbers, MAX_NUMBERS
    call MakeHex
    WriteFile FileNameHEX, NumbersHEX, MAX_NUMBERS*6
    call Sort

    WriteFile FileNameSorted, Numbers, MAX_NUMBERS
    call MakeHex
    WriteFile FileNameSortedHEX, NumbersHEX, MAX_NUMBERS*6
    mov ecx, 10
    .repeat:
        push ecx
        FINIT
        FillRandom
        call TimeElapsed
        call Sort
        call TimeElapsed
        mov ecx, 4
        mov edx, DeltaTime
        call PrintReversedHex
        Print NewLine, 1
        pop ecx
        sub ecx, 1
        cmp ecx, 0
        ja .repeat

    PrintLn
    MessageBox Done, Done
    Footer

section .bss

Handle: resd 1
NumberOfCharsWritten: resd 1
alignb 16
padding2: resb 16
Numbers: resb MAX_NUMBERS
padding: resb 16
NumbersHEX: resb MAX_NUMBERS*6
Frequency: resq 1
CurrentCounter: resq 1
LastCounter: resq 1
DeltaTime: resq 2
Temp: resb 100
CryptProv: resd 1
resb 1