; -----------------------------------------------
;        Library: QuickSort
;    Description: Generic recursive sorting
; -----------------------------------------------
; Authors: BitRAKE (fix by esiodur)
; -----------------------------------------------
;--- REVISIONS ---
; ver. 0.0.1 - 27.11.2002 - pelaillo:
;   Written in fasm syntax
;.
;--- INSTRUCTIONS ---
; Use:
;   include 'qsort.inc'
;    ...
;       call qsort,array,LowBound,UpBound
;--- TECHNICAL INFO ---
; Divide the array defined by index range [esi,edi] into
; two ranges: one with items less-than-equal item (ecx) and
; one with items greater-than-equal item (ecx).  Recursively process
; sub-partitions.  If there are zero/one items greater then it is
; possible to skip the upper partition.  Don't move items
; equal to pivot item.
; ----------------------------------------------------------------
; OnEntry:
;     ebx = Array pointer (doesn't change)
;     esi = Lower index [0,edi-1]
;     edi = Upper index [1,+]
; During Main Section of Code:
;     ebx = (see above)
;     esi = top index of lower partition
;     ebp = bottom index of upper partition
;     edi = (ebp-esi) gap between partition, approaches zero
;     ecx = pivot index
; eax/edx = (disposable)
;. ---------------------------------------------------------------

; unsigned
macro compareu item1,item2
 {
	push edi
	push ecx
	xor eax,eax ; remove if movzx is used
	xor edx,edx
	mov edi,[ebx + item1*4]
	; item1/item2 could be ECX, so store last into ECX
	mov ecx,[ebx + item2*4]
	.next:
	mov al,[edi] ; movzx eax, BYTE PTR [edi] is better
	inc edi
	mov dl,[ecx] ;  ; movzx edx, BYTE PTR [ecx] is better
	inc ecx
	cmp eax,edx
	jne .done
	cmp eax,0
	jne .next
	.done:
	pop ecx
	pop edi
 }

;signed
macro compare item1,item2
 {
	local .next
	local .done
	push ecx
	mov edx,[ebx + item1*4]
	mov ecx,[ebx + item2*4]
	.next:
	mov al,[edx]
	inc edx
	cmp al,[ecx]
	jne .done
	inc ecx
	cmp al,0
	jne .next
	.done:
	pop ecx
 }

macro exchange item1,item2
 {
	mov edx,[ebx + item1*4]
	mov eax,[ebx + item2*4]
	mov [ebx + item2*4],edx
	mov [ebx + item1*4],eax
 }

proc qsort,array,lb,ub
	begin
	push	esi edi ebx ebp
	mov	ebx,[array]
	mov	esi,[lb]
	mov	edi,[ub]
	call	partition
	pop	ebp ebx edi esi
	return
  partition:
	push	esi
	push	edi
	mov	ebp,edi
	sub	edi,esi
	jle	.exit
;       cmp     edi,10 ; Limit for insertsort
;       ja      .continue
;       mov     eax,edi
;       push    esi
;       shl     esi,2
;       add     esi,ebx
;       stdcall isort,esi,0,eax
;       pop     esi
;       jmp     .exit
;  .continue
	mov	ecx,esi
	inc	ebp
  .low:
	inc	esi
	dec	edi
	js	.donel
	compare ecx,esi
	jge	.low
  .high:
	dec	ebp
	dec	edi
	js	.donel
	compare ecx,ebp
	jle	.high
	exchange esi,ebp
	jmp	.low
  .donel:
	dec	esi
	exchange ecx,esi
	dec	esi
	mov	edi,[esp]
	mov	[esp],esi
	mov	esi,ebp
	call	partition
	pop	edi
	pop	esi
	jmp	partition
  .exit:
	add	esp,8
	ret
endp