201 lines
4.4 KiB
NASM
201 lines
4.4 KiB
NASM
.data
|
|
|
|
# Eingaben:
|
|
#Array_: .long 12,18,19,21, 25,27,31,40, 42,45,56,57, 59,60,61,63, 63,65,70,79, 81,81,85,86, 92,93,94
|
|
#Array: .long 86,19,59,63, 79,65,45,27, 61,31,94,85, 42,92,21,81, 63,18,56,25, 12,70,57,81, 40,60,93
|
|
#n: .long 27
|
|
Array: .long 4,3,2,1
|
|
n: .long 4
|
|
|
|
textout: .string "Ergebnis: "
|
|
intout: .string "%d "
|
|
endout: .string "\n"
|
|
|
|
.text
|
|
######################################################################
|
|
.globl _main
|
|
.global _mainCRTStartup # debugging 4 msvs/windows
|
|
######################################################################
|
|
_mainCRTStartup: # do nothing
|
|
jmp _main # jump to _main
|
|
######################################################################
|
|
_main:
|
|
|
|
leal Array, %eax # Lade ArrayAdresse in %ebx
|
|
movl n, %ebx # Lade n nach %ecx
|
|
decl %ebx # n-1
|
|
|
|
call .quicksort # call subrutine quicksort
|
|
|
|
jmp .end # finish
|
|
|
|
######################################################################
|
|
;# %eax = Array-Start-Adresse = A
|
|
;# %ebx = ArrayLänge = n
|
|
.quicksort:
|
|
|
|
cmp $1, %ebx # n = 1?
|
|
jle .quicksort_ancor # get outa here
|
|
|
|
pushl %ebx # save array-length
|
|
pushl %eax # save array-adress
|
|
pushl %eax # save array-adress (save twice)
|
|
|
|
# %eax = array-adress (saved
|
|
# %ebx = arry-length (saved)
|
|
|
|
call .partition # call .partition
|
|
|
|
# %eax = p
|
|
popl %ecx # %ecx = array-adress
|
|
|
|
pushl %eax # save p
|
|
movl %eax, %ebx # %ebx = p (new array length)
|
|
subl $1, %ebx # p -1
|
|
|
|
movl %ecx, %eax # %eax = Array-Address
|
|
|
|
# %eax = Array-Adress
|
|
# %ebx = p-1
|
|
|
|
call .quicksort # with A and p-1
|
|
|
|
popl %ecx # restore p
|
|
popl %eax # restore Array-Adress
|
|
popl %ebx # restore n
|
|
|
|
subl %ecx, %ebx # Correct Array-Length n - p
|
|
|
|
imull $4, %ecx # p * 4
|
|
addl %ecx, %eax # Move Array-Adress (p*4)
|
|
|
|
# Array-Adress + (p*4)
|
|
# Array-Length n-p
|
|
|
|
call .quicksort
|
|
ret
|
|
|
|
.quicksort_ancor:
|
|
ret # get outa here
|
|
|
|
######################################################################
|
|
;# %eax = Array-Start-Adresse = A
|
|
;# %ebx = ArrayLänge = n
|
|
.partition:
|
|
|
|
push %eax #Save Array-Address
|
|
push %ebx #Save Array-Length
|
|
|
|
imull $4, %ebx # %ebx * 4
|
|
addl %ebx, %eax # Adresse auf letzten Eintrag verschieben
|
|
movl (%eax), %eax # %eax = x = A[n]
|
|
pushl %eax # save x
|
|
movl $0, %ebx # %ebx = i = 0
|
|
movl $0, %ecx # %ecx = j = 0
|
|
|
|
.partition_for:
|
|
cmp %ecx, 4(%esp) # j < n
|
|
jle .partition_for_anchor
|
|
|
|
movl 8(%esp), %edx # %edx = Array-Adress
|
|
movl %ecx, %eax # %eax = j
|
|
imull $4, %eax # %eax = j*4
|
|
addl %eax, %edx # %edx = A[j]-Adresse
|
|
movl (%esp), %eax # %eax = x
|
|
cmp (%edx), %eax # compare A[j] with x
|
|
jl .partition_for_if_achnor
|
|
#if
|
|
pushl %eax
|
|
pushl %ebx
|
|
pushl %ecx
|
|
|
|
movl 20(%esp), %eax # %eax = Array-Adress
|
|
# %ebx = i
|
|
# %ecx = j
|
|
call .array_exchange
|
|
|
|
popl %ecx
|
|
popl %ebx
|
|
popl %eax
|
|
|
|
incl %ebx # i++
|
|
#endif (else)
|
|
.partition_for_if_achnor:
|
|
#nothing to do here, we are done with if
|
|
|
|
incl %ecx # j ++
|
|
jmp .partition_for # jump back to for-loop
|
|
#endfor
|
|
.partition_for_anchor:
|
|
#nothing to do here, we are done with for-loop
|
|
|
|
movl 8(%esp), %eax # %eax = Array-Adress
|
|
# %ebx = i
|
|
movl 4(%esp), %ecx # %ecx = n
|
|
pushl %ebx
|
|
|
|
|
|
call .array_exchange # call array_exchange
|
|
|
|
popl %eax # %eax = i
|
|
|
|
addl $12, %esp # clean stack (array-addr, n, x)
|
|
|
|
ret
|
|
|
|
######################################################################
|
|
;# %eax = Array-Start-Adresse = A
|
|
;# %ebx = pos A
|
|
;# %ecx = pos B
|
|
.array_exchange:
|
|
movl %eax, %edx # %edx = Array-Adress
|
|
|
|
imull $4, %ebx
|
|
imull $4, %ecx
|
|
addl %ebx, %eax # %eax = A[PosA]
|
|
addl %ecx, %edx # %edx = A[PosB]
|
|
|
|
movl (%eax), %ebx # %ebx = A[PosA]-Value
|
|
movl (%edx), %ecx # %ecx = A[PosB]-Value
|
|
movl %ecx, (%eax) #xchange
|
|
movl %ebx, (%edx)
|
|
|
|
ret
|
|
|
|
######################################################################
|
|
.end:
|
|
# Wert im %eax ausgeben
|
|
|
|
pushl $textout
|
|
call _printf
|
|
|
|
leal Array, %eax
|
|
|
|
mov n, %ebx;
|
|
imull $4, %ebx
|
|
|
|
addl %ebx, %eax
|
|
subl $4, %eax
|
|
|
|
output_loop:
|
|
cmp $0, %ebx
|
|
je output_ancor
|
|
|
|
pushl (%eax)
|
|
pushl $intout
|
|
call _printf
|
|
|
|
subl $4, %ebx
|
|
subl $4, %eax
|
|
|
|
jmp output_loop
|
|
|
|
output_ancor:
|
|
|
|
|
|
pushl $endout
|
|
call _printf
|
|
|
|
# Exit
|
|
movl $1, %eax
|
|
#int $0x80 |