Index: trunk/Assembly_Library/Src/Util/Sort.asm
===================================================================
--- trunk/Assembly_Library/Src/Util/Sort.asm	(revision 45)
+++ trunk/Assembly_Library/Src/Util/Sort.asm	(revision 45)
@@ -0,0 +1,287 @@
+; File name		:	Sort.asm
+; Project name	:	Assembly Library
+; Created date	:	28.9.2010
+; Last update	:	29.9.2010
+; Author		:	Tomi Tilli
+; Description	:	Sorting algorithms
+
+; Algorith is from http://www.algolist.net/Algorithms/Sorting/Quicksort
+
+struc QSORT_PARAMS
+	.lpItems		resb	4
+	.tempStruct:
+endstruc
+
+;--------------------------------------------------------------------
+; Prototype for comparator callback function
+;	Parameters:
+;		DS:SI:	Offset to first item to compare
+;		ES:DI:	Offset to second item to compare
+;	Returns:
+;		FLAGS:	Signed comparition between first and second item
+;	Corrupts registers:
+;		Nothing
+;--------------------------------------------------------------------
+
+
+; Section containing code
+SECTION .text
+
+;--------------------------------------------------------------------
+; DialogFile_GetFileNameWithIoInDSSI
+;	Parameters:
+;		DS:SI:	Ptr to FILE_DIALOG_IO
+;		SS:BP:	Ptr to parent MENU
+;	Returns:
+;		Nothing
+;	Corrupts registers:
+;		AX, CX, DX
+;--------------------------------------------------------------------
+ALIGN JUMP_ALIGN
+Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX:
+	push	es
+	push	di
+	add		cx, BYTE QSORT_PARAMS_size
+	eENTER_STRUCT cx
+
+	cld
+	sub		cx, BYTE QSORT_PARAMS_size	; Restore CX to item size
+	xor		ax, ax						; Zero for starting index
+	dec		dx							; Count to index of last item
+	mov		[bp+QSORT_PARAMS.lpItems], si
+	mov		[bp+QSORT_PARAMS.lpItems+2], ds
+	call	QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
+
+	lds		si, [bp+QSORT_PARAMS.lpItems]
+	add		cx, BYTE QSORT_PARAMS_size
+	eLEAVE_STRUCT cx
+	pop		di
+	pop		es
+	ret
+
+
+;--------------------------------------------------------------------
+; QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
+;	Parameters:
+;		AX:		Index of first item in range
+;		BX:		Comparator function
+;		CX:		Size of struct in bytes
+;		DX:		Index of last (included) item in range
+;		SS:BP:	Ptr to QSORT_PARAMS
+;	Returns:
+;		Nothing
+;	Corrupts registers:
+;		DS, ES
+;		AX, DX (not for recursion)
+;--------------------------------------------------------------------
+ALIGN JUMP_ALIGN
+QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
+	push	di
+	push	si
+
+	mov		si, ax			; First index to SI
+	mov		di, dx			; Last index to DI
+	call	ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
+
+	; Does left partition need more sorting
+	cmp		si, dx			; if (first index < Index of rightmost unsorted item)
+	jae		SHORT .CheckIfRightPartitionNeedsMoreSorting
+	xchg	ax, si			; AX = first index, SI = Index of leftmost unsorted item
+	call	QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
+	xchg	ax, si			; AX = Index of leftmost unsorted item
+
+.CheckIfRightPartitionNeedsMoreSorting:
+	cmp		ax, di			; if (Index of leftmost unsorted item < last index)
+	jae		SHORT .SortCompleted
+	mov		dx, di			; DI = Index of leftmost unsorted item
+	call	QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
+
+ALIGN JUMP_ALIGN
+.SortCompleted:
+	pop		si
+	pop		di
+	ret
+
+
+;--------------------------------------------------------------------
+; ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
+;	Parameters:
+;		AX:		Index of first item in range
+;		BX:		Comparator function
+;		CX:		Size of struct in bytes
+;		DX:		Index of last (included) item in range
+;		SS:BP:	Ptr to QSORT_PARAMS
+;	Returns:
+;		AX:		Index of first unsorted item
+;		DX:		Index of last unsorted item
+;	Corrupts registers:
+;		DS, ES
+;--------------------------------------------------------------------
+ALIGN JUMP_ALIGN
+ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
+	push	di
+	push	si
+
+	call	.GetPivotPointerToESDI
+	call	ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
+
+	pop		si
+	pop		di
+	ret
+
+ALIGN JUMP_ALIGN
+.GetPivotPointerToESDI:
+	push	ax
+	add		ax, dx
+	shr		ax, 1
+	call	GetItemPointerToDSSIfromIndexInAX
+	pop		ax
+	jmp		Memory_ExchangeDSSIwithESDI
+
+
+;--------------------------------------------------------------------
+; ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
+;	Parameters:
+;		AX:		Index of first item in range
+;		BX:		Comparator function
+;		CX:		Size of struct in bytes
+;		DX:		Index of last (included) item in range
+;		ES:DI:	Ptr to Pivot item
+;		SS:BP:	Ptr to QSORT_PARAMS
+;	Returns:
+;		AX:		Index of first unsorted item
+;		DX:		Index of last unsorted item
+;	Corrupts registers:
+;		SI, DS
+;--------------------------------------------------------------------
+ALIGN JUMP_ALIGN
+ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
+	cmp		ax, dx	; while (left <= right)
+	ja		SHORT .BreakLoopSinceAllItemsExamined
+
+	call	GetItemPointerToDSSIfromIndexInAX
+	call	.GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
+
+	call	GetItemPointerToDSSIfromIndexInDX
+	call	.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
+
+	cmp		ax, dx	; If (left <= right)
+	ja		SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
+	call	SwapItemsFromIndexesAXandDX
+	inc		ax
+	dec		dx
+	jmp		SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
+
+ALIGN JUMP_ALIGN
+.GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI:
+	call	bx
+	jge		SHORT .NoNeedToIncrementOrDecrementAnyMore
+	inc		ax				; Increment item index
+	add		si, cx			; Point to next struct
+	jmp		SHORT .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
+
+ALIGN JUMP_ALIGN
+.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
+	call	bx
+	jle		SHORT .NoNeedToIncrementOrDecrementAnyMore
+	dec		dx
+	sub		si, cx
+	jmp		SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
+
+ALIGN JUMP_ALIGN
+.NoNeedToIncrementOrDecrementAnyMore:
+.BreakLoopSinceAllItemsExamined:
+	ret
+
+
+;--------------------------------------------------------------------
+; SwapItemsFromIndexesAXandDX
+;	Parameters:
+;		AX:		Index of item 1
+;		CX:		Size of struct in bytes
+;		DX:		Index of item 2
+;		SS:BP:	Ptr to QSORT_PARAMS
+;	Returns:
+;		Nothing
+;	Corrupts registers:
+;		SI, DS
+;--------------------------------------------------------------------
+ALIGN JUMP_ALIGN
+SwapItemsFromIndexesAXandDX:
+	push	es
+	push	di
+
+	; Item AX to stack
+	call	.GetPtrToTemporaryStructToESDI
+	call	GetItemPointerToDSSIfromIndexInAX
+	call	.CopyItemFromDSSItoESDI
+
+	; Item DX to Item AX
+	call	Memory_ExchangeDSSIwithESDI
+	call	GetItemPointerToDSSIfromIndexInDX
+	call	.CopyItemFromDSSItoESDI
+
+	; Stack to Item DX
+	call	.GetPtrToTemporaryStructToESDI
+	call	Memory_ExchangeDSSIwithESDI
+	call	.CopyItemFromDSSItoESDI
+
+	pop		di
+	pop		es
+	ret
+
+ALIGN JUMP_ALIGN
+.GetPtrToTemporaryStructToESDI:
+	lea		di, [bp+QSORT_PARAMS.tempStruct]
+	push	ss
+	pop		es
+	ret
+
+ALIGN JUMP_ALIGN
+.CopyItemFromDSSItoESDI:
+	push	si
+	push	cx
+
+	shr		cx, 1			; We want to copy WORDs for performance
+	jcxz	.CopyLastByte
+	rep		movsw
+.CopyLastByte:
+	jnc		SHORT .CopyComplete
+	movsb
+.CopyComplete:
+	pop		cx
+	pop		si
+	ret
+
+
+;--------------------------------------------------------------------
+; GetItemPointerToDSSIfromIndexInDX
+; GetItemPointerToDSSIfromIndexInAX
+;	Parameters:
+;		AX or DX:	Item index
+;		CX:			Size of struct in bytes
+;		SS:BP:		Ptr to QSORT_PARAMS
+;	Returns:
+;		DS:SI:		Ptr to item
+;	Corrupts registers:
+;		Nothing
+;--------------------------------------------------------------------
+ALIGN JUMP_ALIGN
+GetItemPointerToDSSIfromIndexInDX:
+	xchg	ax, dx
+	call	GetItemPointerToDSSIfromIndexInAX
+	xchg	dx, ax
+	ret
+
+ALIGN JUMP_ALIGN
+GetItemPointerToDSSIfromIndexInAX:
+	push	dx
+	push	ax
+
+	mul		cx		; DX:AX = index (AX) * size of struct (CX)
+	lds		si, [bp+QSORT_PARAMS.lpItems]
+	add		si, ax
+
+	pop		ax
+	pop		dx
+	ret
