2

I'm trying to write a bubble sort in x86 (masm32). The sort doesn't work. I've tested some of the code and it appears to be messed up in the compare and swap sections. For some reason, the compare function always assigns 2 to EAX. If I can figure out why I can get the program working.

Thanks for your help in advance.

    .data
          aa DWORD 10 DUP(5, 7, 6, 1, 4, 3, 9, 2, 10, 8)
        count DWORD 0
; DB 8-bits, DW 16-bit, DWORD 32, WORD 16 BYTE 8



    .code                       ; Tell MASM where the code starts

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

start:                          ; The CODE entry point to the program

    mov esi, count ;loop count

    outer:
        inc esi
        mov edi, count        
        cmp esi, 9       
        je end_loop

    inner: ;this loop represents a full pass on the entire array
        inc edi        
        cmp edi, 9 ;after 9 passes goes to outer loop
        je outer

    compare:
        mov eax, [aa + edi * 4h] ;higher indexed one
        mov ebx, [aa + edi * 4h - 4h] 

;testing        print chr$(13,10)
;testing        print str$(eax)
;testing        print chr$(13, 10)
;testing        print str$(ebx)
;testing        print chr$(13, 10)

        cmp ebx, eax
        jg swap

    swap:
        mov [aa + edi * 4h], eax
        mov [aa + edi * 4h + 4], ebx
        jmp inner

end_loop:

    ;print out array elements
    sub esi, esi
    mov esi, [aa]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 2]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 3]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 4]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 5]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 6]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 7]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 8]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 9]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

exit


; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

end start                       ; Tell MASM where the program ends
Joachim Isaksson
  • 176,943
  • 25
  • 281
  • 294
grey
  • 31
  • 3

2 Answers2

1

Figured out what was wrong - the print statements in the middle of the program were hosing my memory. Here is the working sort. Thanks for the help everyone!

    .data
          aa DWORD 10 DUP(5, 7, 6, 1, 4, 3, 9, 2, 10, 8)
        count DWORD -1
; DB 8-bits, DW 16-bit, DWORD 32, WORD 16 BYTE 8



    .code                       ; Tell MASM where the code starts

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

start:                          ; The CODE entry point to the program

    mov esi, count ;loop count

    outer:
        inc esi
        mov edi, count        
        cmp esi, 10       
        je end_loop

    inner: ;this loop represents a full pass on the entire array
        inc edi        
        cmp edi, 9 ;after 9 passes goes to outer loop
        je outer

    compare:
        mov eax, [aa + edi * 4h]
        mov ebx, [aa + edi * 4h + 4] ;want to make this one the higher indexed-one

        ;print chr$(13,10) These print calls were hosing the memory before.
        ;print str$(eax)
        ;print chr$(13, 10)
        ;print str$(ebx)
        ;print chr$(13, 10)

        cmp eax, ebx
        jle inner

    swap:
        mov [aa + edi * 4h], ebx
        mov [aa + edi * 4h + 4], eax
        jmp inner

end_loop:

    ;print out array elements
    sub esi, esi
    mov esi, [aa]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 2]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 3]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 4]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 5]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 6]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 7]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 8]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

    mov esi, [aa + 4h * 9]
    print str$(esi)
    print chr$(" ")
    sub esi, esi

exit


; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

end start                       ; Tell MASM where the program ends
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
grey
  • 31
  • 3
  • This is why you use a debugger instead of debug-print function calls or macros! – Peter Cordes Nov 28 '17 at 07:54
  • This is actually a pretty clean / sane Bubble Sort, without any silly stuff like a slow `xchg` with memory (implicit `lock` prefix), or the [slow `loop` instruction](https://stackoverflow.com/questions/35742570/why-is-the-loop-instruction-slow-couldnt-intel-have-implemented-it-efficiently), or other wasted instructions. Also the branch/loop structure is pretty clean. Fall-through into `swap:` vs. a taken branch to skip the `swap` stores and putting a `cmp / jne inner` at the bottom is probably more or less break-even. – Peter Cordes Nov 28 '17 at 08:00
  • The loading `-1` from `count` is super-ugly, though, and so is hard-coding the number of elements. Loading the initial `count` from memory but hard-coding `10` makes zero sense. :/ Structuring the outer loop as a `do {} while()` with the loop condition at the bottom would be cleaner. Also, the print stuff at the end should *definitely* be a loop, but at least it comes after the sort so the answer is readable. – Peter Cordes Nov 28 '17 at 08:03
0

One obvious problem is right here:

    cmp ebx, eax
    jg swap

swap:
    mov [aa + edi * 4h], eax
    mov [aa + edi * 4h + 4], ebx
    jmp inner

With this, it jumps to swap if the g flag is set -- but it falls through to swap if the g flag is not set, so it executes exactly the same code either way. At a guess, what you want is probably something like jle inner to skip the swap if the two items are already in order.

Edit: Looking at things again, it looks like you have another fairly obvious problem. Let's think in terms of something like C, and use base as the address from whcih you load eax (at compare). You (conceptually) do:

eax = *base;
ebx = *(base + 4);

Then at swap you do:

*base = eax;
*(base - 4) = ebx;

This is clearly wrong as well. To swap the two variables, you want something like:

*base = ebx;
*(base + 4) = eax;
Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • Thanks! I'll change that right away. However, I still don't know why when I print out EAX it is always 2.. (in the compare function, comment in the ;testing notes) – grey Jul 23 '13 at 06:41
  • @grey: Offhand, I'm not sure about that. I'd guess it's a scaling problem, but about the only way I could be sure would be to run it under a debugger. – Jerry Coffin Jul 23 '13 at 06:57