asm_Q4

INCLUDE Irvine32.inc
INCLUDE asm3_Q4_data.inc

;Submit by: Omer Idel, ID: 203347794
;This program make QuickSort
;and make Collatz QuickSort (CollQuickSort)
;Arr array sorted by CollQuickSort function
;DiffArr shows the differnce beetween the regualr QuickSort
;and the Collatz QuickSort
;if there is 0 at the i'th place - it's the same value
;if there is 1 at the i'th place - it's not the same value

.data
FirstLeft=0
MyName BYTE		"Omer Idel, ID: 203347794", 10, 13, 0
DupliArr		word NN dup(?)
count			word 0 ; for Collatz
newpivotindex	dword ?
space			byte "	",13,10,0

.code
my_main PROC

    call	randomize

	mov		edx, offset MyName
	call	WriteString

	push	offset Arr
	push	offset DupliArr
	push	lengthof NN
	call	dupArr

	push	offset DupliArr
	push	FirstLeft
	push	dword ptr (NN-1)
	call	QuickSort

	push	offset Arr
	push	FirstLeft
	push	dword ptr (NN-1)
	call	CollQuickSortSecond

	push	offset DupliArr
	push	offset Arr
	push	offset DiffArr
	push	dword ptr NN
	call	FindTheDiff

	mov		edx, offset DiffArr
    call	exitProcess

my_main ENDP

;------------------------------------------------------------
;This function find the differnce between the regular quick sort
;and the coll quick sort
;input: 3 Arrays - DupliArr, Arr, DiffArr and the Size (16 Bytes)
;output: Nothing
;------------------------------------------------------------
FindTheDiff PROC

	push	ebp
	mov		ebp, esp

	push	eax
	push	ebx
	push	ecx
	push	edx

	mov		eax, [ebp+20] ; offset of DupliArr
	mov		ebx, [ebp+16] ; offset of Arr
	mov		edx, [ebp+12] ;	offset of DiffArr
	mov		ecx, [ebp+8] ; Size of Arrays
	
FindDiffLoop:
	shl		ecx, 1
	mov		di, word ptr[eax+ecx-2]
	cmp		di, word ptr[ebx+ecx-2]
	je		FillDiffArray
	mov		word ptr[edx+ecx-2], 1
	shr		ecx, 1
	loop	FindDiffLoop

FillDiffArray:
	mov		word ptr[edx+ecx-2], 0
	shr		ecx, 1
	loop	FindDiffLoop

    pop		ecx
    pop		edx
	pop		ebx
	pop		eax
    mov		esp, ebp
    pop		ebp
    ret		16
	
FindTheDiff ENDP

;------------------------------------------------------------
;This function make copy of arr
;input: 2 Arrays - DupliArr, Arr and Size (12 Bytes)
;output: Nothing
;------------------------------------------------------------
dupArr PROC
	push	ebp
	mov		ebp, esp

	push	eax
	push	ebx
	push	ecx
	push	edx ; helper 

	mov		eax, [ebp+16] ; offset of Arr
	mov		ebx, [ebp+12] ; offset of DupliArr
	mov		ecx, [ebp+8] ; Size of Arrays

duplicateArr:
	shl		ecx, 1
	mov		dx, word ptr [eax+ecx-2]
	mov		word ptr [ebx+ecx-2], dx
	shr		ecx, 1
	loop	duplicateArr

	pop		edx
	pop		ecx
    pop		ebx
	pop		eax
    mov		esp, ebp
    pop		ebp
    ret		12

dupArr ENDP

;------------------------------------------------------------
;This is the collatz function
;input: number (2 Bytes)
;output: ax - the collatz value
;------------------------------------------------------------
Collatz PROC
	push	ebp
	mov		ebp, esp
	push	ecx ; helper for mul 
	push	edx ; helper for div
	
	xor		eax, eax

    mov     ax, word ptr [ebp + 8] ; the input
    shr     ax, 1 ;check if even or not
    jnc     EvenNum ;if even
	jmp		OddNum ;else
	jmp     EndCollatz

OddNum:
    cmp     word ptr [ebp + 8], 1 ;checking the stop conditions
    je      EndCollatz  
    mov     ax, word ptr [ebp + 8]    
    mov     ecx, 3
    mul     ecx
    inc     ax
    inc     Count
    push    ax
    call    Collatz
    jmp     EndCollatz
	
EvenNum:
    cmp     word ptr [ebp + 8], 1 ; checking the stop conditions
    je      EndCollatz
    mov     ax, word ptr [ebp + 8]
    mov     ecx, 2      
    xor     edx, edx
    div     ecx
    inc     Count
    push    ax
    call    Collatz
    

EndCollatz:
	mov		ax, count
    pop		edx
    pop		ecx
    mov		esp, ebp
    pop		ebp
    ret		2

Collatz ENDP

;------------------------------------------------------------
;This function get left and right and retrun a random index beetwen those numbers
;input: left, right (8 Bytes)
;output: ax - the random index
;------------------------------------------------------------
ChooseIndex Proc 
    push	ebp
    mov		ebp, esp

    push	edx
    mov		eax, [ebp+12] ; para right
    mov		edx, [ebp+8] ; para left

    sub		eax, edx
    sub		eax, 1
    cmp		eax, 0
    je		donechooswindex
    call	RandomRange

donechooswindex:

	pop		edx 
    mov		esp, ebp
    pop		ebp
    ret		8
ChooseIndex ENDP

;------------------------------------------------------------
;This is the regular partion
;This partion return the index of the new location of pivot 
;input: Array, Left, Right, Pivot (16 Bytes)
;output: ax - the new index of pivot
;------------------------------------------------------------
Partition PROC
    push	ebp
    mov		ebp, esp
	sub		esp, 8 ; ebp-4 for index_i, ebp-8 for index_j

    push	ecx
    push	edx
    push	ebx
    
    mov		edx, [ebp+20] ;address of Arr
    mov		ebx, [ebp+16] ;index Left
    mov		ecx, [ebp+12] ;index Right
    mov		eax, [ebp+8] ;pivot

	;for relative location in arr
	shl		ebx, 1
	add		edx, ebx
	shr		ebx, 1

    ;for looping 
    sub		ecx, ebx
    inc		ecx

	mov     dword ptr [ebp-4], 0 ; index_i
	mov     dword ptr [ebp-8], 0 ; index_j
	sub		dword ptr [ebp-4], 2

	;moving to the right place in the arr and taking the arr[i]
    shl		eax, 1 ; shifing left becuase the arr is word arr

	mov		ax, word ptr [edx+eax]

Ploop: 
    mov		esi, edx
	add		esi, dword ptr [ebp-8]

    mov		edi, 0 ; reset the var 
    mov		di, word ptr [esi]
    cmp		di, ax
    jae		continueL
	add		dword ptr [ebp-4], 2

    ;push	eax and ecx for saving them before the swap
    push	eax
    push	ecx
    xor		eax, eax
    xor		ecx, ecx

    ;beacuse lea dosent work with vars - save ebx and use him to reach the right index
    
    push	ebx
    xor		ebx, ebx
    mov		ebx, dword ptr [ebp-4]
    lea		eax, [edx + [ebx]]
    push	eax

    xor		ebx, ebx
    mov		ebx, dword ptr [ebp-8]
    lea		ecx, [edx + [ebx]]
    push	ecx
    call	Swap

    pop		ebx
    pop		ecx
    pop		eax
	add		dword ptr [ebp-8], 2
    loop	Ploop
    Jmp		DonePartition

continueL:
	add		dword ptr [ebp-8], 2
    loop	Ploop

DonePartition:

    add		dword ptr [ebp-4], 2
    xor		ecx, ecx
    xor		ebx, ebx

    mov		ebx, dword ptr [ebp-4]
    lea		ecx, [edx + [ebx]]
    push	ecx

	xor		ecx, ecx
    xor		ebx, ebx

	mov		ebx, [ebp+16] ;index Left
    mov		ecx, [ebp+12] ;index Right
	sub		ecx, ebx
	inc		ecx 

findPivotIndex:
	
	shl		ecx, 1
	cmp		ax, [edx+ecx]
	je		contine
	shr		ecx, 1
	loop	findPivotIndex


contine:

    lea		ecx, [edx + [ecx]]
    push	ecx
    call	Swap
    
	mov		edx, [ebp+20] 
    mov		ecx, lengthof arr

findPivotIndexLast:
	
	shl		ecx, 1
	cmp		ax, [edx+ecx]
	je		DoneDone
	shr		ecx, 1
	loop	findPivotIndexLast

DoneDone:
    shr		ecx, 1
    mov		eax, ecx ; return the pivot index

    pop		ebx
    pop		edx
    pop		ecx
    mov		esp, ebp
    pop		ebp
    ret		16
Partition ENDP

;------------------------------------------------------------
;This is the QuickSort
;input: Array, Left, Right (12 Bytes)
;output: Nothing
;------------------------------------------------------------
QuickSort PROC
    push	ebp
    mov		ebp ,esp
    sub		esp ,8 ; first 4 bytes for choose index, second 4 bytes for newpivotindex
    push	ecx
    push	edx
    push	ebx
    mov		ebx, [ebp + 16] ; Arr offset
    mov		edx, [ebp + 12] ; Left
    mov		ecx, [ebp +8] ;Right

    cmp		dx, cx
    jge		DoneQsort

    push	ecx ; push right
    push	edx ; push Left
    call	ChooseIndex ; the return call is in ax
    mov		[ebp-4], eax 

    push	ebx ; the address of the arr
    push	edx ; push left
    push	ecx ; push right
    push	[ebp-4] ; push pivot index that returned from Chooseindex
    call	partition 
    mov		[ebp-8], eax 

    push	ebx ; the address of the arr
    push	edx ; push left

    push	ecx
    mov		ecx, [ebp-8]
    mov		newpivotindex, ecx
    sub		newpivotindex ,1
    pop		ecx

    push	newpivotindex ; push new pivot index
    call	QuickSort

    push	ebx ; the address of the arr

    push	ecx
    mov		ecx,[ebp-8]
    mov		newpivotindex, ecx
    add		newpivotindex ,1
    pop		ecx
    push	newpivotindex ; push new pivot index
    push	ecx ; push right
    call	QuickSort

DoneQsort:
    pop		ebx
    pop		edx
    pop		ecx
    mov		esp, ebp
    pop		ebp
    ret		12
QuickSort ENDP

;------------------------------------------------------------
;This is the partion for collQuickSort
;This partion return the index of the new location of pivot 
;input: Array, Left, Right, Pivot (16 Bytes)
;output: ax - the new index of pivot
;------------------------------------------------------------
PartitionColl PROC
    push	ebp
    mov		ebp, esp
	sub		esp, 8 ; ebp-4 for index_i, ebp-8 for index_j
    push	ecx
    push	edx
    push	ebx
    
    mov		edx, [ebp+20] ;address of Arr
    mov		ebx, [ebp+16] ;index Left
    mov		ecx, [ebp+12] ;index Right
    mov		eax, [ebp+8] ;pivot

	;for relative location in arr
	shl		ebx, 1
	add		edx, ebx
	shr		ebx, 1

    ;for looping 
    sub		ecx, ebx
    inc		ecx

	mov     dword ptr [ebp-4], 0 ; index_i
	mov     dword ptr [ebp-8], 0 ; index_j
	sub		dword ptr [ebp-4], 2


	;moving to the right place in the arr and taking the arr[i]
    shl		eax, 1 ; shifing left becuase the arr is word arr
	
	mov		ax, word ptr [edx+eax]
	push	ax
	push	ax
	mov		count, 0
	call	Collatz
	xor		ebx, ebx
	mov		bx, ax

PloopColl: 

    mov		esi, edx
    add		esi, dword ptr [ebp-8]
    mov		edi, 0 ; reset the var 
    mov		di, word ptr [esi]
	push	di
	mov		count, 0
	call	Collatz
    cmp		ax, bx
    jae		continueLColl
    add		dword ptr [ebp-4], 2

    ;push	eax and ecx for saving them before the swap
    push	ecx

    ;beacuse lea dosent work with vars - save ebx and use him to reach the right index
	push	ebx
    mov		ebx, dword ptr [ebp-4]
    lea		eax, [edx + [ebx]]
    push	eax
    mov		ebx, dword ptr [ebp-8]
    lea		ecx, [edx + [ebx]]
    push	ecx
    call	Swap

	pop		ebx
    pop		ecx
	add		dword ptr [ebp-8], 2
    loop	PloopColl
    Jmp		DonePartitionColl

continueLColl:
    add		dword ptr [ebp-8], 2
    loop	PloopColl

DonePartitionColl:

	pop		ax
    add		dword ptr [ebp-4], 2
    xor		ecx, ecx
    xor		ebx, ebx

    mov		ebx, dword ptr [ebp-4]
    lea		ecx, [edx + [ebx]]
    push	ecx

	xor		ecx, ecx
    xor		ebx, ebx

	mov		ebx, [ebp+16] ;index Left
    mov		ecx, [ebp+12] ;index Right
	sub		ecx, ebx
	inc		ecx 

findPivotIndexColl:
	
	shl		ecx, 1
	cmp		ax, [edx+ecx]
	je		contineColl
	shr		ecx, 1
	loop	findPivotIndexColl


contineColl:

    lea		ecx, [edx + [ecx]]
    push	ecx
    call	Swap
    
	mov		edx, [ebp+20] 
    mov		ecx, lengthof arr

findPivotIndexLastColl:
	
	shl		ecx, 1
	cmp		ax, [edx+ecx]
	je		DoneDoneColl
	shr		ecx, 1
	loop	findPivotIndexLastColl

DoneDoneColl:
    shr		ecx, 1
    mov		eax, ecx ; return the pivot index

    pop		ebx
    pop		edx
    pop		ecx
    mov		esp, ebp
    pop		ebp
    ret		16

PartitionColl ENDP

;------------------------------------------------------------
;This is the coolQuickSort
;input: Array, Left, Right (12 Bytes)
;output: Nothing
;------------------------------------------------------------
CollQuickSortSecond PROC

	push	ebp
    mov		ebp ,esp
    sub		esp ,8 ; first 4 bytes for choose index, second 4 bytes for newpivotindex
    push	ecx
    push	edx
    push	ebx
    mov		ebx, [ebp + 16] ; Arr offset
    mov		edx, [ebp + 12] ; Left
    mov		ecx, [ebp +8] ;Right

    cmp		dx, cx
    jge		DoneCollQuickSortSecond

    push	ecx ; push right
    push	edx ; push Left
    call	ChooseIndex ; the return call is in ax
    mov		[ebp-4], eax 

    push	ebx ; the address of the arr
    push	edx ; push left
    push	ecx ; push right
    push	[ebp-4] ; push pivot index that returned from Chooseindex
    call	partitionColl 
    mov		[ebp-8], eax 

    push	ebx ; the address of the arr
    push	edx ; push left

    push	ecx
    mov		ecx, [ebp-8]
    mov		newpivotindex, ecx
    sub		newpivotindex ,1
    pop		ecx

    push	newpivotindex ; push new pivot index
    call	collQuickSortSecond

    push	ebx ; the address of the arr

    push	ecx
    mov		ecx,[ebp-8]
    mov		newpivotindex, ecx
    add		newpivotindex ,1
    pop		ecx
 
    push	newpivotindex ; push new pivot index
    push	ecx ; push right
    call	collQuickSortSecond

DoneCollQuickSortSecond:
    pop		ebx
    pop		edx
    pop		ecx
    mov		esp, ebp
    pop		ebp
    ret		12

CollQuickSortSecond ENDP

;------------------------------------------------------------
;This Swap function
;input: 2 places in array that we need to swap (8 Bytes)
;output: Nothing
;------------------------------------------------------------
SWAP PROC
    push	ebp
    mov		ebp, esp
 
    sub		esp, 4 

    push	eax
    push	ebx
    push	edx

    xor		eax, eax
    xor		ebx, ebx
    xor		edx, edx

    mov		ebx, [ebp+12]		
    mov		ax, WORD ptr [ebx]    
    mov		word ptr [ebp-4], ax   
    mov		edx, [ebp+8]         

    mov		ax, WORD ptr [edx]     
    mov		word ptr [ebx], ax   
    mov		ax, word ptr [ebp-4]
    mov		word ptr [edx], ax    
    
    pop		edx
    pop		ebx
    pop		eax
    mov		esp, ebp
    pop		ebp
    ret		8
    
SWAP ENDP

END my_main