Author Topic: Having an issue with sorting an array [SOLVED]  (Read 7321 times)

Offline Nicholas Westerhausen

  • Jr. Member
  • *
  • Posts: 9
Having an issue with sorting an array [SOLVED]
« 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:
Code: [Select]
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:
Code: [Select]
nasm -g -f elf32 sort-sample.asm
ld -melf_i386 sort-sample.o -o out

Thanks for your time!

Regards,
Nick
« Last Edit: March 29, 2013, 03:11:06 AM by Nicholas Westerhausen »

Offline Nicholas Westerhausen

  • Jr. Member
  • *
  • Posts: 9
Re: Having an issue with sorting an array
« Reply #1 on: March 29, 2013, 12:58:54 AM »
Yes, I am aware of the other recent bubble sort post (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.

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Having an issue with sorting an array
« Reply #2 on: March 29, 2013, 02:53:49 AM »
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


Offline Nicholas Westerhausen

  • Jr. Member
  • *
  • Posts: 9
Re: Having an issue with sorting an array
« Reply #3 on: March 29, 2013, 03:10:23 AM »
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:
Code: [Select]
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