Author Topic: Sorting numbers in an array in ascending order  (Read 36957 times)

Offline edge363

  • Jr. Member
  • *
  • Posts: 9
Sorting numbers in an array in ascending order
« on: November 04, 2014, 05:23:26 AM »
Hello! this is my first post and I was wondering if I could receive some help on an assembly project for one of my college courses. The goal of the assignment is to  take in N double word integers and then print them out in ascending order. It should also do some other stuff, but I am confident I can do that myself.  When I run this code I get a segmentation fault, and after tracing through the program twice, I do not see why! After each method I explain what they do, so I would really appreciate it if someone could tell me what is wrong! I don't see why it does it incorrectly.

%include "Along32.inc"
section .data ;data section
;               Start Main Method

section .bss             
array resd 100;

section .code                   ;code section
global _start

  _start:   ; main program
mov ecx,0;
call readInts ;
; methods

//this one works, it reads in the ints and places them into a array.

readInts:
call ReadInt ; puts an int into eax along libraries
push ecx ;
mov ecx, eax ;
jecxz sortSetUp ;
pop ecx ;
mov [array+ecx*4],eax ;
inc ecx ;
call readInts ;

//this saves values, subtracts one from ecx( ecx ends up being one over because arrays start at the index of 0) it then grabs the last value, and places it in ebx

sortSetUp:
pop ecx ;
dec ecx ;
mov eax,ecx ;
mov edx,ecx ;
mov ebx,[array+ecx*4];
call sort ;

//this is the method that will sort the array. It does so by comparing ebx(containing last value) to every other value. If the value ebx is being compared to is //larger it exchanges places with the two different numbers.

sort:
cmp [array+ecx*4],ebx ;
jg greaterThan ;
jecxz sortNext ;
loop sort ;

//This number will first exchange the larger number with ebx(ebx now holds the larger number) It then copies the larger value to the last slot in the array as to put them in descending order. This will find the largest number and place it in the last slot after comparing all values. Subsequent loops will then not compare values to the last value. Which will allow the program to run slightly faster, but more importantly it will not copy the largest value over and over again.

greaterThan:
xchg [array+ecx*4],ebx ;
mov  [array+edx*4],ebx ;
ret ;

//as stated int the previous explenation, this method decrements edx so we wont grab the last value on the next go through, and it will continue until we reach the last value, and since it is the only value left we know it is in the right place so it then jumps to the end of the program(the method that prints out all of the values)

sortNext:
dec edx ;
mov ecx,edx ;
jecxz printAllSetUp ;
mov ebx,[array+edx*4];
call sort ;

//we have this method so we can restore ecx to its original glory.

printAllSetUp:
mov ecx, eax ;
call printAll ;

//this method basically just uses edx(which equals 0) and moves it up by one each go around to simply write out the ints

printAll:
mov eax,[array+edx*4] ;
inc edx ;
call WriteInt ; along method, prints out a vaue from eax.
jecxz exit ; leaves the program once all the values have been printed
loop printAll ;

exit:                                   ;exit function
       mov     eax,1                    ;mov 1 eax
       int     0x80                     ; ask kernal to exit
« Last Edit: November 04, 2014, 05:30:18 AM by edge363 »

Offline gammac

  • Jr. Member
  • *
  • Posts: 71
  • Country: 00
Re: Sorting numbers in an array in ascending order
« Reply #1 on: November 04, 2014, 07:36:23 AM »
Hello edge363,

I haven't analyzed your code at all, but it seems to me that you have too many recursive function calls.

good luck
gammac
Please comment your code! It helps to help you.

Offline edge363

  • Jr. Member
  • *
  • Posts: 9
Re: Sorting numbers in an array in ascending order
« Reply #2 on: November 04, 2014, 06:21:26 PM »
Is that bad? Does it cause errors? Like stack overflow or something to do with the stack pointer?

Offline edge363

  • Jr. Member
  • *
  • Posts: 9
Re: Sorting numbers in an array in ascending order
« Reply #3 on: November 04, 2014, 06:26:46 PM »
I will redesign it with less recursive calls. Give me 1 or 2 hours, also! If anybody can correct my original code I would be more than happy.

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Sorting numbers in an array in ascending order
« Reply #4 on: November 04, 2014, 10:34:15 PM »
Hi edge363,

Sorry, I'm having a little trouble getting "focused" on this... but I'm on it. I think gammac's right - too many "call"s, but I don't think they're really intended to be "recursive". The segfault appears to be in:
Code: [Select]
    mov ebx, [array + ecx * 4]
I think (not certain) that this is in your "sortSetUp" routine. Having ecx be negative at this point would segfault, and having ecx be a return address inadvertantly popped off the stack might, too. I haven't had any luck fixing the problem yet. I have only just begun to fight! :)

The research continues...

Best,
Frank


Offline edge363

  • Jr. Member
  • *
  • Posts: 9
Re: Sorting numbers in an array in ascending order
« Reply #5 on: November 05, 2014, 02:00:06 AM »
Thank you so much frank! I'm working on it to, and will have a few less calls shortly.

Offline edge363

  • Jr. Member
  • *
  • Posts: 9
Re: Sorting numbers in an array in ascending order
« Reply #6 on: November 05, 2014, 02:45:24 AM »
I changed the loop completely so its more understandable, and more easily debugged.

So this version works....some of the time. I do not get why it only works some of the time. But when it works it does it perfectly! example
give it -1,-34,45,67 then 0

will give you
-34,-1,45,67

give it -1,-23,-34,-45,-56,-67,-87,56,67,789,34545,0
it gives me a segmentation fault. Damnit. Its acceptable, but I really want it to work all the time.

Code: [Select]
%include "Along32.inc"
section .data ;data section
;               Start Main Method

section .bss
array resd 100;

section .code          ;code section
global _start

  _start:   ; main program
mov ecx,0;
call readInts ;
; methods

;this one works, it reads in the ints and places them into a array.

greaterThan:
xchg [esi+ecx*4],ebx ;
mov  [esi+edx*4],ebx ;
ret ;

readInts:
call ReadInt ;
push ecx ;
mov ecx, eax ;
jecxz sortSetUp ;
pop ecx ;
call WriteInt ;
call Crlf ;
mov [array+ecx*4],eax ;
inc ecx ;
call readInts ;

;this saves values, subtracts one from ecx( ecx ends up being one over because arrays start at the index of 0) it then grabs the last value, and
;places it in ebx

sortSetUp:
mov esi, array ;
pop ecx ;
mov eax,ecx ;
mov edx,ecx ;
dec ecx ;
call sortNext ;

;this is the method that will sort the array. It does so by comparing ebx(containing last value) to every other value. If the value ebx is being
;compared to is //larger it exchanges places with the two different numbers.

sortNext:
push ecx ;
dec edx ;
jecxz printAllSetUp ;
mov ebx,[esi+edx*4] ;
mov ecx,edx ;
call sort ;
pop ecx ;
loop sortNext;
sort:
cmp [esi+ecx*4],ebx ;
JG greaterThan ;
loop sort ;
ret ;

;This number will first exchange the larger number with ebx(ebx now holds the larger number) It then copies the larger value to the last slot in the
;array as to put them in descending order. This will find the largest number and place it in the last slot after comparing all values.
;Subsequent loops will then not compare values to the last value. Which will allow the program to run slightly faster, but more importantly
;it will not copy the largest value over and over again.
;as stated int the previous explanation, this method decrements edx so we wont grab the last value on the next go through, and it will continue
;until we reach the last value, and since it is the only value left we know it is in the right place so it then jumps to the end of the
;program(the method that prints out all of the values)

;we have this method so we can restore ecx to its original glory.

printAllSetUp:
mov edx,0 ;
mov ecx,eax ;
call printAll ;

;this method basically just uses edx(which equals 0) and moves it up by one each go around to simply write out the ints

printAll:
mov eax,[esi+edx*4] ;
inc edx ;
call WriteInt ;
jecxz exit ;
loop printAll ;

exit:                                   ;exit function
call Crlf ;
       mov     eax,1                    ;mov 1 eax
       int     0x80                     ; ask kernal to exit
« Last Edit: November 05, 2014, 03:17:40 PM by Frank Kotler »

Offline gammac

  • Jr. Member
  • *
  • Posts: 71
  • Country: 00
Re: Sorting numbers in an array in ascending order
« Reply #7 on: November 05, 2014, 01:25:39 PM »
Are you sure that you have a balanced stack? I mean, has esp at _start: and exit: the same value? I doubt it.

Why don't you use a clean structure (input -> sort -> output -> exit) without so many unnecessary and confusing calls?

I bet, in a few months without working on this code, you wont understand your own code. I wouldn't understand it.

Your code does not work for input: 0

Is it intended to run sortNext: twice? Why?
« Last Edit: November 05, 2014, 01:28:25 PM by gammac »
Please comment your code! It helps to help you.

Offline Rob Neff

  • Forum Moderator
  • Full Member
  • *****
  • Posts: 429
  • Country: us
Re: Sorting numbers in an array in ascending order
« Reply #8 on: November 05, 2014, 03:21:20 PM »
readInts:
   call ReadInt ;
   push ecx ;
   mov ecx, eax ;
   jecxz sortSetUp ;
   pop ecx ;
   call WriteInt ;
   call Crlf ;
   mov [array+ecx*4],eax ;
   inc ecx ;
   call readInts ;

Are you 100% certain that your call to ReadInt, WriteInt, and Crlf doesn't destroy ECX and EAX?

;this method basically just uses edx(which equals 0) and moves it up by one each go around to simply write out the ints

printAll:
   mov eax,[esi+edx*4] ;
   inc edx ;
   call WriteInt ;
   jecxz exit ;
   loop printAll ;

Are you 100% certain that your call to WriteInt doesn't destroy ECX and EDX?
« Last Edit: November 05, 2014, 03:23:46 PM by Rob Neff »

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Sorting numbers in an array in ascending order
« Reply #9 on: November 05, 2014, 04:40:29 PM »
For some reason, I continue to have trouble getting "in the mood" to test this. Being 32-bit Linux, I "can" test it which usually pleases me (not true of 64-bit nor Windows). I even have the Along32 macros/libraries in place (although I usually don't use 'em). Pretty sure they do preserve ecx/edx - which is not true of "normal" libraries! Good point, Rob! It's a Linux/Nasm port of Kip Irvine's "irvine32.lib" (for Windows/Masm). It would probably make a good "general rule" to tell us where to find any include files your code uses... http://along32.sourceforge.net/ in this case.

Another good "general rule" would be to use "code tags" - just the word "code" in square brackets (like a Nasm memory reference) at the top of your code, and "/code" at the end. I edited your code to use 'em. It may or may not make the code easier to read - definitely makes it easier to cut-and-paste. We should probably say that someplace prominent. Maybe it would make a good alternative to the "guess the puzzle" we put ya through (that'll go away after a few posts). I dunno...

Anyway... we definitely don't have a balanced stack.
Code: [Select]
%include "Along32.inc"
section .data ;data section
;               Start Main Method

section .bss
array resd 100;

section .code          ;code section
global _start

  _start:   ; main program
mov ecx,0;
call readInts ;
; methods
If, in fact, we ever returned from this call, we would "fall through" and do it all again. Not what we want! A general form like...
Code: [Select]
main_or_start:
call fill_array
; return to here
call sort_array
; return to here
call print_array
; return to here
exit:
; sys_exit or other clean exit

fill_array:
; do it
ret

sort_array:
;do it
ret

print array:
; do it
ret
might be better.

I deduce that when the prompts are added it will say "enter zero when finished". It is clearly intentional that an input of 0 "doesn't work".

I'll try to get into this and have more specific suggestions soon (I hope)...

Later,
Frank


Offline gammac

  • Jr. Member
  • *
  • Posts: 71
  • Country: 00
Re: Sorting numbers in an array in ascending order
« Reply #10 on: November 05, 2014, 04:58:03 PM »
Frank, 0 is a possible input and should be handled! Or not? If I say "it doesn't work" I didn't mean "it's not supported" I mean it's not handled and it's a fault.



Please comment your code! It helps to help you.

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Sorting numbers in an array in ascending order
« Reply #11 on: November 05, 2014, 06:24:47 PM »
Well, I dunno...
Code: [Select]
; ...
readInts:
call ReadInt ;
push ecx ;
mov ecx, eax ;
jecxz sortSetUp ;

That looks to me like an input of 0 is "supposed" to indicate "end of input". I'm not sure how else we let the user indicate they're done. Maybe make 'em say "how many items in array?" first? The "customer specification" (assignment) may say how this is supposed to be handled? Always understand the "specification" first! :)

I've only just assembled edge363's latest version - haven't really started to debug. I can confirm that sometimes it segfaults and sometimes exits cleanly. Sometimes the "sort" seems to work, and sometimes not. I wouldn't consider this "acceptable", but definitely "improved". Still "too many calls and not enough rets", IMO...

Sorry to be so slow-moving on this - even worse than usual. The research continues...

Best,
Frank


Offline gammac

  • Jr. Member
  • *
  • Posts: 71
  • Country: 00
Re: Sorting numbers in an array in ascending order
« Reply #12 on: November 05, 2014, 06:39:12 PM »
Code: [Select]
sortSetUp:
pop ecx ;
dec ecx ;


 ecx will be -1 if the input is only zero and imho this results in an unpredictable program state.
Please comment your code! It helps to help you.

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Sorting numbers in an array in ascending order
« Reply #13 on: November 05, 2014, 07:02:54 PM »
Right! Entering 0 as the first and only item results in a segfault.

Best,
Frank


Offline edge363

  • Jr. Member
  • *
  • Posts: 9
Re: Sorting numbers in an array in ascending order
« Reply #14 on: November 06, 2014, 01:13:55 AM »
0 is the call that is supposed to tell the program to stop taking in input and instead end. I am sorry for my messy, sloppy, code. I would loveeeeee to have a  better way, but with our teacher I am basically teaching myself completely. This is the way that makes the most sense to me right now.