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

Offline edge363

  • Jr. Member
  • *
  • Posts: 9
Re: Sorting numbers in an array in ascending order
« Reply #15 on: November 06, 2014, 01:23:45 AM »
0 is not added to the array. It is not viable input.
« Last Edit: November 06, 2014, 04:45:28 AM by edge363 »

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Sorting numbers in an array in ascending order
« Reply #16 on: November 06, 2014, 02:50:57 AM »
Okay. Sorry you feel that all you're getting is criticism. It's intended to be "constructive criticism". We don't want to "do your homework for you". By all means try to work it out yourself! The fact that it "works sometimes" suggests that it's not a simple error that we can find and tell you. I'll keep looking and let you know if I spot anything. "too many calls and not enough rets" looks like a problem to me, and maybe "trying to use ecx for too many things". I'd introduce a variable for "item_count" once the user has entered 0, rather than saving it in eax and restoring it from there - might not help. Sorry I haven't gotten farther with it. Come back if you need "more" help - not that you've gotten much. You might catch me on a better day. :)

Best,
Frank

Edit: Hmmm... the post that this was in reply to has vanished. Never mind...
« Last Edit: November 06, 2014, 09:59:00 AM by Frank Kotler »

Offline gammac

  • Jr. Member
  • *
  • Posts: 71
  • Country: 00
Re: Sorting numbers in an array in ascending order
« Reply #17 on: November 06, 2014, 04:31:01 PM »
Hello edge363,

Frank's right, all criticism it's intended to be constructive and we don't want to do your homework it's right too. You got a lot of hints and keywords (e.g. stack balancing) to feed your search engine with it. You should try to rewrite your code, look at reply #9, Frank gave you a good skeleton for your program structure, try to use it. Post your new program here and maybe there is nothing to criticise any more. :) And do not use 'call' like a branch.

And 0 it's a possible input and no possible input should cause a segfault. Every possible input should be handled.

Good luck
gammac

PS: excuse my bad english, I hope you get me right.
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 #18 on: November 06, 2014, 10:10:41 PM »
Working version. For anybody who needs it.
Thank you Frank.(note, I over reacted and took part of the post down.) Thank you Gammac.
I did not want you to do my homework. I just wanted help when thinking about the logic of the program. The reason it wasn't working is because it was essentially quick sort without a pivot element. So it just clustered lower elements at the lower end and clustered higher elements at the top. Misleading with low numbers of input or high numbers of input.

Code: [Select]
%include "Along32.inc"
section .data
max dd 0
maxIndex dd 0
prompt1    : db "Overflow error, must use less than 100 numbers.",0ah, 0   
prompt2    : db "You must submit at least 1 number.",0ah, 0   
size dd 0
section .bss
array resd 100;
section .code
global _start
  _start:   ; main program
push esp ;
mov ecx,0;
call readInts ;

;explenation-reads in an array of ints, sorts them by finding largest and puting it in last place over and over, and then printing out the array.

overFlow:
mov edx, prompt1 ;
call WriteString ;
jmp exit ;
zeroError:
mov edx, prompt2 ;
call WriteString ;
jmp exit ;
readInts:
cmp ecx, 100 ;
je overFlow ;
call ReadInt ;
push ecx ;
mov ecx, eax ;
jecxz sortSetUp ;
pop ecx ;
mov [array+ecx*4],eax ;
inc ecx ;
call readInts ;
sortSetUp:
pop ecx ;
cmp ecx, 0 ;
je zeroError ;
dec ecx ;
mov esi, array ;
mov [size], ecx ;
mov edx, ecx ;
sortNext:
cmp edx,0 ;
je printAllSetUp;
mov ebx,[esi+edx*4] ;
mov [max],ebx ;
mov [maxIndex],edx ;
mov ecx,edx ;
sort:
cmp ebx,[esi+ecx*4] ;
Jge skip ;
mov ebx,[array+ecx*4];
mov [max], ebx ;
mov [maxIndex], ecx ;
mov eax,[max] ;
skip:
cmp ecx, 0;
je zeroLoopEnd ;
dec ecx ;
jmp sort ;
zeroLoopEnd:
mov eax, [max] ;
xchg [esi+edx*4], eax ;
mov ebx,[maxIndex] ;
mov [esi+ebx*4],eax ;
dec edx ;
call sortNext;
printAllSetUp:
mov edx,0 ;
mov ecx, [size] ;
inc ecx ;
call printAll ;
printAll:
mov eax,[esi+edx*4] ;
inc edx ;
call WriteInt ;
jecxz exit ;
loop printAll ;
exit:                                   ;exit function
       pop esp ;
       call Crlf ;
       mov     eax,1                    ;mov 1 eax
       int     0x80                     ; ask kernal to exit
« Last Edit: November 07, 2014, 01:13:55 AM by Frank Kotler »

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Sorting numbers in an array in ascending order
« Reply #19 on: November 06, 2014, 11:09:54 PM »
Good! I'm still not making much progress with this. I think my brain's on vacation this week... or this month... maybe forever...

Maybe I shouldn't mention this, but the same (apparently) question has appeared on Stack Overflow. http://stackoverflow.com/questions/26771581/how-do-i-sort-an-array-in-nasm
Answered by the same poster (a pretty young woman, if the picture is to be believed - who knows?) Supposed to work - I haven't tried it. Look at it only if you're desperate for help...

Anyway, I'll look at the new version... with the usual disclaimer "if I can get my asm in gear"... Still looks like "too many calls" to me...

Best,
Frank


Offline gammac

  • Jr. Member
  • *
  • Posts: 71
  • Country: 00
Re: Sorting numbers in an array in ascending order
« Reply #20 on: November 07, 2014, 12:17:10 AM »
Working version. For anybody who needs it.

Congratulation, but sorry, do you really think your code is bug free and reusable? :(

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 #21 on: November 07, 2014, 07:03:04 AM »
Well... I've only just assembled this and tried it with a couple of input sequences - 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 and 9, 8, 7, 6, 5, 4, 3, 2, 1, 0. The good news is that the sort worked perfectly both times. The bad news is that it segfaulted both times. (apparently on "call Crlf", which seems strange!)

So... "the research continues", but let me point out a couple of things that "don't look right to me" before I get back (I hope) to trying to find the actual problem...

Code: [Select]
%include "Along32.inc"
section .data
max dd 0
maxIndex dd 0
prompt1    : db "Overflow error, must use less than 100 numbers.",0ah, 0   
prompt2    : db "You must submit at least 1 number.",0ah, 0   
size dd 0
section .bss
array resd 100;
section .code
global _start
  _start:   ; main program
push esp ;

This is apparently an attempt to assure that esp is going to be the same at the end of the program as at the beginning - but it isn't going to work. If the stack gets messed up, the value you pop into esp at the end isn't going to be the same value you pushed here! (that's probably why "call Crlf" appears to fail for me - but perhaps not for you)

Code: [Select]
mov ecx,0;
call readInts ;
This call never returns. Already the stack is messed up! It may not be obvious to a beginner that "call" (and "ret") use the stack at all, but they sure do!

"call" does something like this:
Code: [Select]
; call somefunc
; next_instruction:
push next_instruction
jmp somefunc
and when the CPU gets to "ret" in "somefunc" (we hope it does) it does:
Code: [Select]
; ret
pop return_address
jmp return_address
If all goes well, "return_address" is "next_instruction" and we continue right after the "call" ("somefunc" can be called from different places, and should return to where it was called from). But the CPU doesn't know if the stack is "balanced" and will "pop" and "jmp" whatever it finds next on the stack. If it's total garbage, the crash is immediate. If it is some valid address, but not the right one, execution may continue for quite a while before the problem becomes obvious - if it does. This can make for a very hard to find bug!

Anyway, back to your code:
Code: [Select]
;explenation-reads in an array of ints, sorts them by finding largest and puting it in last place over and over, and then printing out the array.

overFlow:
mov edx, prompt1 ;
call WriteString ;
jmp exit ;
zeroError:
mov edx, prompt2 ;
call WriteString ;
jmp exit ;
readInts:
cmp ecx, 100 ;
je overFlow ;
call ReadInt ;
push ecx ;
mov ecx, eax ;
jecxz sortSetUp ;
pop ecx ;
mov [array+ecx*4],eax ;
inc ecx ;
call readInts ;
Another "call" with no "ret". Return-addresses pile up on the stack. One for every input (which may explain the different behavior on different runs). Just "jmp readInts" should work here, and would be "better", I think.

While we're here...
Code: [Select]
call ReadInt ;
push ecx ;
mov ecx, eax ;
jecxz sortSetUp ;
This is a legitimate "call" - Curtis Wong's code has a "ret" in it and the stack should have the proper return address on it, so we return here with the users input clutched firmly in eax. Gammac's right that 0 is a valid input, but we need to use it to pretend they said "quit". I don't understand why you did it the way you did ("because it came to me to do it that way" is a good reason). Why not:
Code: [Select]
        call ReadInt
        cmp eax, 0
        jz sortSetUp
        ...
This would save pushing and popping ecx - it could remain the "item count". I think the way you do it should work, but I get nervous when I see anything like:
Code: [Select]
push something
set some condition code ("flags")
any conditional jump
pop something
As long as the pushes and pops match on both branches of the conditional jump, it's no problem, but it's a place where bugs can sneak in. Since "pop" doesn't alter the flags, we can often do:
Code: [Select]
push something
set some condition codes
pop something
some conditional jump
but when we're popping ecx and the condition is "jecxz", this isn't going to work!

Code: [Select]
sortSetUp:
pop ecx ;
cmp ecx, 0 ;
je zeroError ;
dec ecx ;
mov esi, array ;
mov [size], ecx ;
mov edx, ecx ;
sortNext:
cmp edx,0 ;
je printAllSetUp;
mov ebx,[esi+edx*4] ;
mov [max],ebx ;
mov [maxIndex],edx ;
mov ecx,edx ;
sort:
cmp ebx,[esi+ecx*4] ;
Jge skip ;
mov ebx,[array+ecx*4];
mov [max], ebx ;
mov [maxIndex], ecx ;
mov eax,[max] ;
skip:
cmp ecx, 0;
je zeroLoopEnd ;
dec ecx ;
jmp sort ;
zeroLoopEnd:
mov eax, [max] ;
xchg [esi+edx*4], eax ;
mov ebx,[maxIndex] ;
mov [esi+ebx*4],eax ;
dec edx ;
call sortNext;
Yet another "call" with no "ret". Well, your sort routine seems to be working. Could probably do "jmp sortNext" with no ill effects. The way I learned to do a bubble sort, as I remember it, went something like:
Code: [Select]
top:
set some "swap flag" to zero (some register)
iterate through the array doing comparisons
jge noswap ; or some condition
do the swap
set the "swap flag" to non-zero
noswap:
continue through the array, until done
check the "swap flag"
if it's still zero, we're done
if not, go back to top and make another pass
If you call a "print_array" after each pass, you can watch the larger numbers "bubble" up to the top of the array. Since your method seems to work, better leave it alone - maybe get rid of that excess "call".

Code: [Select]
printAllSetUp:
mov edx,0 ;
mov ecx, [size] ;
inc ecx ;
call printAll ;
printAll:
mov eax,[esi+edx*4] ;
inc edx ;
call WriteInt ;
jecxz exit ;
loop printAll ;
This looks good and seems to work right.
Code: [Select]
exit:                                   ;exit function
       pop esp ;
       call Crlf ;
This is where it crashes for me. I said it was unusual for a "call" to crash (usually it's the "ret"s that get ya). If the value we popped into esp were any legitimate memory, it would have worked. It might not have been the "right" place on the stack, but "call" would have had someplace to put its return address, and the "ret" in Crlf would have found it. But if we'd popped something else - an array index or a value for number of items or anything - when "call" tried to save its return address, it would have been trying to write to invalid memory, and would segfault. I haven't tracked down why, but I think that must be what's happening. If you'd put the "pop esp" after the "call", we might never have noticed that the stack was messed up - but it still would have been.
Code: [Select]
       mov     eax,1                    ;mov 1 eax
Useless comment. One ring to rule them all? Oh, I see, it's sys_exit! :) sys_exit doesn't care what shape the stack is in. All of the memory for our process - including the stack - just vanishes and we return to the shell (bash, which is buggy as it turns out) not to here.

Code: [Select]
       int     0x80                     ; ask kernal to exit
Old-fashioned way to spell "kernel". Not wrong, just "old school". Okay, I'm just being picky now. I hear a bell ringing. I think it's recess! TTYL

Best,
Frank


Offline gammac

  • Jr. Member
  • *
  • Posts: 71
  • Country: 00
Re: Sorting numbers in an array in ascending order
« Reply #22 on: November 07, 2014, 11:37:25 AM »

Code: [Select]
printAllSetUp:
...
call printAll ;
printAll:
...
jecxz exit ;
loop printAll ;
This looks good and seems to work right.

Sorry Frank, but this messed up the stack too.
Please comment your code! It helps to help you.

Offline gammac

  • Jr. Member
  • *
  • Posts: 71
  • Country: 00
Re: Sorting numbers in an array in ascending order
« Reply #23 on: November 07, 2014, 12:02:11 PM »
Hello edge363,

I've found something for you!

http://williams.comp.ncat.edu/COMP375/AsmCall.pdf
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 #24 on: November 07, 2014, 10:58:21 PM »
That's a gem, gammac! A much better find than that wayward "call" I missed. :)

Best,
Frank



Offline edge363

  • Jr. Member
  • *
  • Posts: 9
Re: Sorting numbers in an array in ascending order
« Reply #25 on: November 11, 2014, 11:38:11 PM »
I am pretty sure the way I am doing this with the exiting the state of the stack will not matter. I do not plan to make this work in any c library or as a macro. I have not had any problems running it, but I will test it again tonight. I will change some of the calls to jumps. I really like using call because sometimes whenever I change it to jump it breaks the program with segfaults. I do not know why at all.

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Sorting numbers in an array in ascending order
« Reply #26 on: November 12, 2014, 09:35:54 AM »
Hi edge363,

I don't know why either. Your latest code, posted Nov 6 at 10:10, definitely segfaults for me. Even if I enter just 0 to test your error message (which works fine - that's a plus). I confess I did not enter 100 numbers to test that one (but it looks like it should work). If it works for you.... well, if it works it works... You are correct that it shouldn't bother sys_exit.

I have modified your code, removing the "push esp" at the start and the "pop esp" at the end. That "sounds like a good idea if you say it quick" but actually makes things worse (causes the following "call Crlf" to segfault - leaves esp pointed into read-only memory). I have replaced all the non-returning "call"s with "jmp"s. I don't know why that's giving you trouble. I have added code to print esp at the beginning and end (just for debugging purposes - you probably want to remove it). Proves that you've got the "push"s and "pop"s balanced - another plus. Other than that, it's all your code:

Code: [Select]
%include "Along32.inc"
section .data
max dd 0
maxIndex dd 0
prompt1    : db "Overflow error, must use less than 100 numbers.",0ah, 0   
prompt2    : db "You must submit at least 1 number.",0ah, 0   
size dd 0
section .bss
array resd 100;
section .code
global _start
  _start:   ; main program
; push esp ; bad idea

; display current esp
mov eax, esp
call WriteHex
call Crlf

mov ecx,0;
jmp readInts ;

;explenation-reads in an array of ints, sorts them by finding largest and puting it in last place over and over, and then printing out the array.

overFlow:
mov edx, prompt1 ;
call WriteString ;
jmp exit ;

zeroError:
mov edx, prompt2 ;
call WriteString ;
jmp exit ;

readInts:
cmp ecx, 100 ;
je overFlow ;
call ReadInt ;
push ecx ;
mov ecx, eax ;
jecxz sortSetUp ;
pop ecx ;
mov [array+ecx*4],eax ;
inc ecx ;
jmp readInts ;

sortSetUp:
pop ecx ;
cmp ecx, 0 ;
je zeroError ;
dec ecx ;
mov esi, array ;
mov [size], ecx ;
mov edx, ecx ;

sortNext:
cmp edx,0 ;
je printAllSetUp;
mov ebx,[esi+edx*4] ;
mov [max],ebx ;
mov [maxIndex],edx ;
mov ecx,edx ;

sort:
cmp ebx,[esi+ecx*4] ;
Jge skip ;
mov ebx,[array+ecx*4];
mov [max], ebx ;
mov [maxIndex], ecx ;
mov eax,[max] ;
skip:
cmp ecx, 0;
je zeroLoopEnd ;
dec ecx ;
jmp sort ;
zeroLoopEnd:
mov eax, [max] ;
xchg [esi+edx*4], eax ;
mov ebx,[maxIndex] ;
mov [esi+ebx*4],eax ;
dec edx ;
jmp sortNext;

printAllSetUp:
mov edx,0 ;
mov ecx, [size] ;
inc ecx ;
jmp printAll ;
printAll:
mov eax,[esi+edx*4] ;
inc edx ;
call WriteInt ;
jecxz exit ;
loop printAll ;

exit:                                   ;exit function
;       pop esp ; really bad idea
       call Crlf ;

; display ending esp
mov eax, esp
call WriteHex
call Crlf

       mov     eax,1                    ;mov 1 eax
       int     0x80                     ; ask kernal to exit

Try it - you don't have to use it. Good luck!

Best,
Frank