Bubble Sort in NASM

[saugata bose]

I wrote a program of bubble sort in NASM. But it shows segmentation fault. I tried to generate assembly version of the following c code:

Code: [Select]

    for(k=0;k<n;k++){
       ptr=0;
       while(ptr<=n-k){

          if(data[ptr]>data[ptr+1])
             do swap
          ptr++; 
       }
     }
The following NASM code is:

Code: [Select]

    section .data
      msg db "%d"
      four dd 4
      msga db "%d ",0

    section .bss
      arr resd 8

    section .text
      global main
      extern printf,scanf

    main:
      xor ecx,ecx

    lp:
      mov ebx,arr     ;; from this line to jnz lp is using for taking 8 inputs
      mov eax,ecx
      mul dword[four]
      add ebx,eax
      pusha

      push ebx
      push msg
      call scanf
      add esp,8
      popa

      inc ecx
      cmp ecx,8
      jnz lp

      mov ecx,0   ;; sorting replication of the above c program is starting
      mov ebx,7   ;; outerloop will execute from 0 to 7

    outerLoop: 
      mov eax,0   ;; it sets ptr=0

    .innerLoop:
      mov edx,8
      sub edx,ecx
      cmp eax,edx  ;; its using for cheking ptr<=n-k

      push ebx
      push ecx
      push edx
      add esp,12

      jle .task
      pop edx
      pop ecx
      pop ebx
      inc ecx

      cmp ecx, ebx ;; its using for cheking whether k is in between 0 to 7
      jl outerLoop

      xor ecx,ecx
      jmp lp1

  .task:
      mov ebx,dword[arr+eax*4]   ;; its using to get data[ptr]
      mov ecx,eax
      push eax
      add esp,4

      add ecx,1
      mov edx,dword[arr+ecx*4]   ;; its using to get data[ptr+1]

      cmp ebx,edx
      jl .activity
      xchg ebx,edx
      mov dword[arr+eax*4],ebx
      mov dword[arr+ecx*4],edx

 .activity:
     pop eax
     pop edx
     pop ecx
     pop ebx

     inc eax
     jmp .innerLoop

 lp1:                 ;; its using for print the output
   mov ebx,arr
   mov eax,ecx

   mul dword[four]
   add ebx,eax
   pusha

   push dword[ebx]
   push msga
   call printf
   add esp,8
   popa
   inc ecx
   cmp ecx,8
   jne lp1
Will u pls help me to find out my mistake? thanx in advance

[Frank Kotler]

Hi Saugata - good to see you over here! "Code Tags" are a little different here than at StackOverflow - "code" and "/code" in square brackets rather than angle brackets... and none of that nonsense about having to skip a line and indent 4 spaces! I edited your code to use 'em.

As we were discussing at SO, you've got some "stack problems" that are causing the crash:

Code: [Select]

...
      cmp eax,edx  ;; its using for cheking ptr<=n-k

      push ebx
      push ecx
      push edx
      add esp,12

And later...

Code: [Select]

      mov ecx,eax
      push eax
      add esp,4

We use "add esp, 4 * number_of_parameters" to "clean up" or "balance" the stack after pushing parameters prior to a "call" by "removing" values from the stack without actually "pop"ping them. That is not what you want to do here! You just pushed those values, you want to leave 'em there!

I think you'll find that if you remove those two "add esp, ?" lines (not the ones after your calls!), your program will run to completion without the segfault. The results aren't quite right. I think I entered 8 7 6 5 4 3 2 1, and got back "1 0 0 2 3 4 5 6" - something like that. I didn't delve into it any deeper than that. I  might, if I'm in the mood...

Gunner suggested that you walk before you try to run, and in that spirit if I were going to try to debug your code, I'd start by commenting out all the "sort" code and verifying that I could fill and print back my array correctly first. Then I might temporarily throw in an extra printf or two, to display the numbers I intend to swap. If you display the array after each "swap", you can watch the values "bubble" up and down to their final positions. Then throw all that crap away and just print the final array.

The very first thing that bothered me about your code...

Code: [Select]

    section .data
      msg db "%d"
I really think that format string ought to be zero-terminated! It "seems to work" without it, but I don't think it's "right".

While I'm at it... In some places you do your addressing like this:

Code: [Select]

      mov eax,ecx
      mul dword[four]
      add ebx,eax

and in other places, you use the more "32-bit like":

Code: [Select]

      mov ebx,dword[arr+eax*4]   ;; its using to get data[ptr]

Now, scanf wants the address of an integer (K&R calls this "the most common error") so you'll have to use "lea" instead of "mov", but otherwise the code could look similar. I don't think it's any part of your problem, but it might make it easier to keep track of which number you're addressing if the code were of a similar form. Just a thought...

You do a lot of pushing and popping - well, you have to 'cause printf and scanf trash 'em on you! But they won't trash ebx, esi, and edi. You use ebx... it might be a win to make more use of esi and edi and less pushin' and poppin'. Again, just a thought...

We're not going to do your homework for you, but we're willing to help with it. I thnk that if you can see your results and not just "segfault", you can probably make more progress on your own. If you have more trouble with it, come back.

Best,
Frank

[hhh3h]

I just wanted to thank you, Frank, for such a detailed and well-explained analysis. It is helpful for other people like me who run into similar pitfalls.