format elf executable

entry main

main:

   mov ecx, string_address                 ; address of string
   mov edx, [string_address.length]        ; length of string
   mov ebx, 1                              ; stdout
   mov eax, 4                              ; sys_write
   int $80

   push [lo] [hi]
   call quicksort

   jmp exit

;--------------------------------

quicksort:                  ; void quicksort (int[] a, int lo, int hi)
;;; begin debug 
    call prarr
    call prstack
    push eax
    mov eax, [esp+12]
    shr eax, 2
    call dot                ; lo
    mov eax, [esp+8]
    shr eax, 2
    call dot                ; hi
    pop eax
;;; end debug

; eax = i=lo
; ecx = x
; edx = j=hi

    mov eax,[esp+8]         ;{
    mov edx,[esp+4]         ;//  lo is the lower index, hi is the upper index
    lea ecx,[eax+edx]       ;//  of the region of array a that is to be sorted
    shr ecx,3               ;    int i=lo, j=hi, h;
    shl ecx,2

;;; begin debug 
    push eax   
    mov eax, ecx
    shr eax, 2
    call dot                ; x
    pop eax
;;; end debug

    mov ecx,[a+ecx]         ;    int x=a[(lo+hi)/2];

;;; begin debug 
    push eax   
    mov eax, ecx
    call dot                ; a[x]
    mov eax, 10
    call emit               ; cr
    pop eax
;;; end debug


  .qc1:                     ;
    cmp [a+eax],ecx         ;    //  partition
    jnc  .qc2               ;    do
    add eax,4
    jmp .qc1                ;    {
  .qc2:                     ;        while (a[i]<x) i++;      // .qc1
    cmp ecx,[a+edx]         ;        while (a[j]>x) j--;      // .qc2
    jnc .qc3                ;        if (i<=j)                // .qc3
    sub edx,4               ;        {
    jmp .qc2                ;            h=a[i]; a[i]=a[j]; a[j]=h;
  .qc3:                     ;            i++; j--;
    cmp edx,eax             ;        }
    jc  .qc4                ;    } while (i<=j);             
    push [a+eax] [a+edx]    ;
    pop  [a+eax] [a+edx]    ;    //  recursion
    add eax,4               ;    if (lo<j) quicksort(a, lo, j);  // .qc4
    sub edx,4               ;    if (i<hi) quicksort(a, i, hi);  // .qc5
    cmp edx,eax             ;}                                   // .qc6
    jnc .qc1
  .qc4:
    cmp  [esp+8],edx
    jnc  .qc5
    push dword [esp+8]
    push edx

;;; debug
    push eax
    mov eax, 'A'
    call emit
    mov eax, ' '
    call emit
    pop eax
;;; end debug
    
    call quicksort
    pop  edx
    pop  dword [esp+12]
  .qc5:
    cmp  eax,[esp+4]
    jnc  .qc6
    push eax
    push dword [esp+8]

;;; debug
    push eax
    mov eax, 'B'
    call emit
    mov eax, ' '
    call emit
    pop eax
;;; end debug

    call quicksort
    pop  dword [esp+12]
    pop  eax
  .qc6:
    ret

align 4
a  dd 3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3   ;16
lo dd 0
hi dd 15*4    

;--------------------------------

prstack:                      ; print the stack
   push    eax
   push    ebx
   push    ecx
   push    edx
   mov  ebx,$10              ; \
   mov  [base],ebx          ;   configure dot
   xor  edx,edx             ; /

   xor  edx,edx
.a: mov  eax,'0'
   call emit
   mov  eax,'x'
   call emit
   mov  eax,[esp+edx]
   call dot
   add  edx,4
   cmp  edx,40
   jna  .a

   mov eax, 10
   call emit
   pop edx
   pop ecx
   pop ebx
   pop eax
   ret

;--------------------------------


prarr:                      ; print the array           
   push    eax
   push    ebx
   push    ecx
   push    edx
   mov     eax,'a'
   call    emit
   mov     eax,'['
   call    emit
   mov     eax,']'
   call    emit
   mov     eax,'='
   call    emit
   mov     ebx,10           ; \
   mov  [base],ebx          ;   configure dot
   xor  edx,edx             

.a:mov  eax,[a+edx]
   call dot
   add  edx,4
   cmp  edx,[hi]
   jna  .a

   mov eax, 10
   call emit
   pop edx
   pop ecx
   pop ebx
   pop eax
   ret

;--------------------------------

dot:    ; print a number
   ; eax = number, ebx = base, edi = buffer
   push eax
   push ebx
   push ecx
   push edx
   mov     ebx, [base]
   cmp  ebx,10
   jne  udot
   mov     edi,buffer
   or      eax,eax         ; negative?
   jns     udot
   push eax
   mov     al,'-'          ; eax is altered
   stosb                   ; only al is stored
   mov  edx, 1
   mov     ecx, buffer
   mov     ebx, 1          ; stdout
   mov     eax, 4          ; sys_write
   int     80h             ; Linux syscall
   pop  eax
   neg  eax
udot:   ;  print a unsigned number
   ; eax = number, ebx = base, edi = buffer
   mov  ebx, [base]
   mov     edi,buffer
   xor     ecx,ecx
.new:
   xor  edx,edx
   div  ebx
   push    edx          ; push remainder
   inc     ecx          ; loop cnt, see below
   test    eax,eax
   jnz     .new
   mov  edx,ecx         ; for type above
.loop:
   pop     eax
   add     al,30h
   cmp     al,'9'
   jng     .ok
   add     al,27h       ; lowercases
.ok:
   stosb                ; mov edi,[al], and inc edi, inc edx
   loop    .loop        ; loop bails out on eci=0
   mov     al,32        ; terminate with space
   inc  edx
   stosb
type:
                        ; edx = count
   mov ecx, buffer
   mov ebx, 1           ; stdout
   mov eax, 4           ; sys_write
   int 80h              ; Linux syscall
   pop  edx
   pop  ecx
   pop  ebx
   pop  eax
   ret

buffer  rb 33           ; 32 + 1
base    rd 1    

;--------------------------------

emit:                   ; print one character
   push eax
   push ebx
   push ecx
   push edx
   mov [char], eax
   mov edx, 1           ; count
   mov ecx, char
   mov ebx, 1           ; stdout
   mov eax, 4           ; sys_write
   int 80h              ; Linux syscall
   pop  edx
   pop  ecx
   pop  ebx
   pop  eax
   ret

char    dd 0

;--------------------------------

exit:
   xor ebx,ebx  ; exit 0
   mov eax, 1
   int 80h

;--------------------------------

string_address db 'lo  hi  x  a[x]',10
.length dd $ - string_address