NASM - The Netwide Assembler
NASM Forum => Programming with NASM => Topic started by: Nicholas Westerhausen on March 28, 2013, 11:15:41 PM
-
Hello again, NASM Forums. It's been a while.
So I am trying to use bubble sort to sort an array (table). I have it go along and it does a decent job doing the for loop structures ( I think ). I'm not sure the correct values are reaching the registers ( and when I get home, I will be able to test that. I don't have enough time right now ).
I copied the relevant bits of code into a separate source file to test just the sort function. Here it is:
section .data
table dw 23,100,3,22,4,6
tLen dw 6
section .bss
index_k resd 1
index_i resd 1
isSorted resd 1
section .text
;;; These are macros I use to simplify subroutine creation.
;;; They are required to be definied before their use.
%macro prologue 0
push ebp
mov ebp, esp
%endmacro
%macro epilogue 0
mov esp, ebp
pop ebp
%endmacro
%macro pushregs 0
push eax
push ebx
push ecx
push edx
%endmacro
%macro popregs 0
pop edx
pop ecx
pop ebx
pop eax
%endmacro
global _start
_start:
main:
;; prints unsorted table first
call printtbl
;; sorts table here
call sorttbl
call write_newline
;; prints newly sorted table here
call printtbl
;; sys_exit(0)
xor ebx, ebx
mov eax, ebx
inc eax
int 0x80
;;;;;;;;;;;;;;;;;
;;; sorttbl ;;;
;;;;;;;;;;;;;;;;;
;;; Function for sorting the table
sorttbl:
prologue
pushregs
.logic:
;; public static void bubbleSort(int[] data)
;;{
;;for (int k = 0; k < data.length - 1; k++)
;; {
;; boolean isSorted = true;
;;
;; for (int i = 1; i < data.length - k; i++)
;; {
;; if (data[i] < data[i - 1])
;; {
;; int tempVariable = data[i];
;; data[i] = data[i - 1];
;; data[i - 1] = tempVariable;
;;
;; isSorted = false;
;;
;; }
;; }
;;
;; if (isSorted)
;; break;
;; }
;; }
.for1_init:
xor ecx, ecx
mov [index_k], ecx
.for1_logic:
; isSorted = true
xor ecx, ecx
inc ecx
mov [isSorted], ecx
; is k < len?
mov eax, [index_k]
mov ebx, [tLen]
cmp eax, ebx
jge .done
.for2_init:
xor ecx, ecx
inc ecx
mov [index_i], ecx
.for2_logic:
; if table[i] < table[i+1]
mov ecx, [index_i]
lea eax, [table + 4 * ecx]
lea ebx, [table + 4 * (ecx - 1)]
mov eax, [eax]
mov ebx, [ebx]
cmp eax, ebx
jge .for2_exit
.for2_swap:
lea eax, [table + 4 * ecx]
lea ebx, [table + 4 * (ecx - 1)]
mov ecx, [eax]
xchg [ebx], ecx
mov [eax], ecx
; isSorted = false
mov [isSorted], ecx
.for2_exit:
mov ecx, [index_i]
inc ecx
mov [index_i], ecx
mov ebx, [tLen]
sub ebx, [index_k]
cmp ecx, ebx
jl .for2_logic
.for1_swapcheck:
mov eax, [isSorted]
xor ebx, ebx
cmp eax, ebx
jne .done
.for1_exit:
mov ecx, [index_k]
inc ecx
mov [index_k], ecx
jmp .for1_logic
.done:
; finished
popregs
epilogue
ret
;;; END SORTTBL FUNCTION
;;;;;;;;;;;;;;;;;;
;;; printtbl ;;;
;;;;;;;;;;;;;;;;;;
;;; The printtbl subroutine prints out the contents of the array
;;; i.e., steps 6 and 9
;;; ARG1: address of array, ARG2: length of array
printtbl:
prologue
pushregs
.setup:
xor ecx, ecx
.prnt_loop:
;; Put the appropriate number from the table into ebx.
;; Then, call the writei function to output it to the
;; terminal. Then, call the write_newline function to
;; write a newline to the screen.
lea ebx, [table+ecx*2]
movzx ebx, word [ebx]
push ebx
call writei
add esp, 4
call write_newline
inc ecx
;; Now compare ecx to the length of the table to see
;; if we still have more numbers to print
mov ebx, [tLen]
cmp ecx, ebx
jb .prnt_loop
.done:
popregs
epilogue
ret
;;; END PRNTTBL FUNCTION
;;;;;;;;;;;;;;;;
;;; writei ;;;
;;;;;;;;;;;;;;;;
;;; Function for writing an integer value to the screen
;;; ARG1: actual integer to print
writei:
prologue
pushregs
.setup:
;; We load the value to convert into eax. Then we put
;; 10 into ebx for the decimal conversion and clear
;; ecx to use for counting
mov eax, [ebp+8]
mov ebx, 10
xor ecx, ecx
.divide:
;; Divide by ten until there is nothing left in eax
xor edx, edx
div ebx
push edx
inc ecx
cmp eax, 0
jne .divide
.writedigits:
;; Now we take off each digit one
;; at a time, add '0' to each digit,
;; push the new integer to the stack,
;; point the write call to the top
;; of the stack.
pop eax
add eax, 0x30
;; Save register for count
push ecx
;; push eax to write
push eax
;; Write
mov edx, 1
mov ecx, esp
mov ebx, 1
mov eax, 4
int 0x80
;; throwaway esp value
add esp, 4
;; retrieve count
pop ecx
;; Decrement the counter and if
;; it isn't zero, write another
;; digit.
dec ecx
cmp ecx, 0
jg .writedigits
.done:
popregs
epilogue
ret
;;; END WRITEi FUNCTION
;;;;;;;;;;;;;;;;;;;;;;;
;;; write_newline ;;;
;;;;;;;;;;;;;;;;;;;;;;;
;;; subroutine for printing a newline to screen
write_newline:
pushregs
.printing:
;; We have to push the newline char to the stack for
;; printing it.
mov edx, 1
push 0x0a
mov ecx, esp
mov ebx, 1
mov eax, 4
int 0x80
add esp, 4
.done:
popregs
ret
;;; END WRITE_NEWLINE FUNCTION
I'm just wondering if there are any glaring mistakes in there that I cannot see.
Compile code:
nasm -g -f elf32 sort-sample.asm
ld -melf_i386 sort-sample.o -o out
Thanks for your time!
Regards,
Nick
-
Yes, I am aware of the other recent bubble sort post (http://forum.nasm.us/index.php?topic=1594.0 (http://forum.nasm.us/index.php?topic=1594.0)), but reading through his post didn't really help me get anywhere. Just got home, so I'm going to run my code through gdb to (hopefully) find the issue.
-
Hi Nick,
Yeah, I see a "problem" with your code. You're mixing words and dwords. I get the feeling this is "intentional". I've seen a few examples lately using word-sized arrays or matrices. You seem to do this correctly in the "print" routine, but in the "sort" routine you're multiplying the index by 4 and using 32-bit registers.
I made a half-baked attempt to fix this up by changing the scale to 2 and using "movzx". I think it works a little better, but not quite right. It moves the 100 to the end, but then apparently exits the routine before sorting the rest of it. I haven't tracked down why. (may be something I screwed up myself)
I'll try to get back to this, but I've gotta get back to Raenir and Maplesirop an a couple things, too. Being "not in the mood" for a couple of days has put me way behind! I'll try to get caught up, but I wanted to mention the issue I saw right off...
Best,
Frank
-
Thanks for your input Frank! Had I not solved my issue before I checked back here, I would have found it after your hint. ;)
I did find that issue too after trying find my problem and watching what went into the registers during runtime. I ended up using dwords for everything so I didn't have to do anything "weird" with the mov instruction. (The extended registers hold 4 bytes, iirc.)
My fixed sorttbl function:
sorttbl:
prologue
pushregs
.logic:
;;public static void bubbleSort(int[] data)
;;{
;;for (int k = 0; k < data.length - 1; k++)
;; {
;; boolean isSorted = true;
;;
;; for (int i = 1; i < data.length - k; i++)
;; {
;; if (data[i] < data[i - 1])
;; {
;; int tempVariable = data[i];
;; data[i] = data[i - 1];
;; data[i - 1] = tempVariable;
;;
;; isSorted = false;
;;
;; }
;; }
;;
;; if (isSorted)
;; break;
;; }
;; }
.for1_init:
;; k = 0;
xor ecx, ecx
mov [index_k], ecx
.for1_logic:
; isSorted = true (1)
xor cl, cl
inc cl
mov [isSorted], cl
; is k > len? if it is, end!
mov eax, [index_k]
mov ebx, [tLen]
cmp eax, ebx
jg .done
.for2_init:
; i = 0;
xor ecx, ecx
inc ecx
mov [index_i], ecx
.for2_logic:
; if table[i] < table[i-1]
; ecx = i; eax = table[i]; ebx = table[i-1]
xor ecx, ecx
mov ecx, [index_i]
lea eax, [table + 4 * ecx] ;leahere
lea ebx, [table + 4 * (ecx - 1)]
mov eax, [eax]
mov ebx, [ebx]
cmp eax, ebx
jge .for2_exit
.for2_swap:
; Do the swap if table[i] < table[i-1]
lea eax, [table + 4 * ecx] ;leahere
lea ebx, [table + 4 * (ecx - 1)]
; Store table[i] in ecx, swap ecx and [ebx]
; Store table[i+1] in [eax]
mov ecx, [eax]
xchg [ebx], ecx
mov [eax], ecx
; isSorted = false
xor cl, cl
mov [isSorted], cl
.for2_exit:
; i++
mov ecx, [index_i]
inc ecx
mov [index_i], ecx
; if i < n - k - 1
mov ebx, [tLen]
sub ebx, [index_k]
dec ebx
cmp ecx, ebx
jle .for2_logic
.for1_swapcheck:
; if isSorted == 1
mov cl, [isSorted]
xor ch, ch
cmp cl, ch
jne .done
.for1_exit:
; k++;
mov ecx, [index_k]
inc ecx
mov [index_k], ecx
jmp .for1_logic
.done:
; finished
popregs
epilogue
ret
;;; END SORTTBL FUNCTION
I changed the size of the table to dwords and then all of sudden I saw it sort most of the table, all but the first index actually. So I had to correct my incorrect translation from the java function to assembly and then it worked! :D
Taking some time off can turn out to be really good for the mind! Hopefully you won't be too hard on yourself.
Regards,
Nick