0

I'm trying to do a bubble sort in x86 assembly (yes it has to be bubble, as I'm not concerned about speed optimization regarding different types of sorts) and for some reason, my code will not swap the necessary values. Here is my code

mov eax, list                   ;store list in eax
mov edx,[eax+4*edi-4]           ;temp = var1
cmp edx,[eax+edi*4]             ;compare
JLE SECOND_LOOP                 ;jump if var1 < var2
mov [eax+4*edi-4],[eax+edi*4]   ;var1 = var2
mov [eax+edi*4], edx            ;var2 = temp
jmp SECOND_LOOP

At the last mov instruction where it's supposed to load the temp back into the address, it..doesn't. The EAX register has the starting address of the array which contains my list of values

0x*starting address* 0a 00 00 00 ec ff ff ff 05 00 00 00 0c 00 00 00 1e 00 00 00 fb ff ff ff ea
0x*address after   * ff ff ff 37 00 00 00 34 00 00 00 00 00 00 00

and the next address contains a few more numbers. In decimal, the numbers are 10 -20 5 12 30 -5 -22 55 52 0. Essentially right now I'm trying to move FFFFFFEC to 0000000A and then move 0000000A to FFFFFFEC. I can store it into my temp register EDX, but cannot store the value of EDX into the specific address. Any help?

HaskellElephant
  • 9,819
  • 4
  • 38
  • 67
gooberdope
  • 75
  • 1
  • 3
  • 13
  • Umm yeah it doesn't. But I just put my data into another register and used the mov instruction. – gooberdope Jul 17 '12 at 00:32
  • Related: https://stackoverflow.com/questions/17802947/bubble-sort-in-x86-masm32-the-sort-i-wrote-doesnt-work has a fairly clean MASM 32-bit implementation of the swap, in a working Bubble Sort for 32-bit integers. – Peter Cordes Nov 28 '17 at 08:05

2 Answers2

3

I think I'd use pointers into the current position into the list, instead of an index that needs to be scaled every time you use it:

    mov esi, offset list
top:
    mov edi, esi
inner:
    mov eax, [edi]
    mov edx, [edi+4]
    cmp eax, edx
    jle no_swap
    mov [edi+4], eax
    mov [edi], edx
no_swap:
    add edi, 4
    cmp edi, list_end - 4
    jb inner
    add esi, 4
    cmp esi, list_end - 4
    jb top
Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • Note that `xchg` with memory is very slow because it's atomic (implicit `lock`). Only use this if optimizing for code-size at the expense of performance (like a factor of 10 probably). See my comments about it in https://codegolf.stackexchange.com/questions/77836/sort-an-integer-list/149038#149038. Bubble-sort swaps a lot, it would make more sense to just load into `edx` before the cmp, so the "swap" is just two `mov` stores. Or better, avoid reloading the value you just stored when incrementing edi makes `[edi+4]` this iteration into `[edi]` next iteration. – Peter Cordes Nov 28 '17 at 07:43
  • @PeterCordes: I figure using a bubble sort is a pretty solid indication that you don't care about performance, but even so I suppose the `xchg` *is* a little steep of a penalty. There's a lot you could do to optimize it further, but not much point until/unless you switch to at least an insertion sort. – Jerry Coffin Jan 03 '18 at 18:09
  • In some situations, you want to optimize for code-size (and bubblesort or jumpdown sort is actually good for that in asm), but with *some* consideration for performance. That would be more likely on a microcontroller, where you don't find much x86, though. Yes, selection or insertion sort can be nearly as compact, and faster. – Peter Cordes Jan 03 '18 at 21:39
  • @PeterCordes: I'd have to write some code for it to be absolutely certain, but it's not immediately obvious (at least to me) that an insertion sort has to be any larger than a bubble sort. – Jerry Coffin Jan 03 '18 at 22:23
  • I tried InsertionSort for that code-golf question. I didn't finish the implementation, but it certainly looked like it was going to be a bit bigger than a `word` rotate bubblesort (with store-forwarding stalls), or an `xchg` jumpdown sort. But those are both horrible for performance, so not a useful comparison. I forget; it's been a while since looking at that code. I think a golfed InsertionSort was only going to be slightly bigger. – Peter Cordes Jan 03 '18 at 22:30
  • @PeterCordes: I suppose it might be, especially if you're code golfing--but even in the worst case, the difference should be pretty small. – Jerry Coffin Jan 03 '18 at 23:04
  • Yeah, I'd guess InsertionSort could be golfed for x86 to 30 bytes at most, instead of ~20 bytes, or a couple extra instructions on other architectures. Pretty trivial in an absolute sense, and worth it if the function is at all hot. – Peter Cordes Jan 03 '18 at 23:36
  • 1
    @PeterCordes: This [insertion sort](http://coliru.stacked-crooked.com/a/e6139e141073656f) is the same length (to the byte) as the bubble sort above (and written in essentially the same style--no real attempt at golfing either one). – Jerry Coffin Jan 04 '18 at 04:18
  • What is list_end? – John Guzman May 10 '20 at 13:42
  • @JohnGuzman: It's just a label for the end of the data being sorted, much like `list_i_end` in the example of insertion sort linked in the comment above yours. – Jerry Coffin May 18 '20 at 19:18
1

This part of your code:

mov edx,[eax+edi*4]
mov [eax+edi*4], edx

effectively does not change anything in the memory, it reads a value from the memory and writes it back where it's just got it from.

Btw, you may be interested in the xchg instruction.

HaskellElephant
  • 9,819
  • 4
  • 38
  • 67
Alexey Frunze
  • 61,140
  • 12
  • 83
  • 180
  • O wow I can't believe I made such an elementary mistake and missed it. And while I looked up xchg and realize it's purpose, my assignment, (it is a homework) requires me to use EDX as a temp register. I changed my code, but I'm getting an error: improper operand type. I didn't debug yet as I just posted when I found out but if you have advise, I'd love to hear. – gooberdope Jul 16 '12 at 04:48
  • Also not only can I not use xchg, but my EAX register has the starting address of the list, where as my edx has a value of some number, so xchg-ing it will just switch the address and the number value, not switch internally the numbers – gooberdope Jul 16 '12 at 05:10
  • You can't move from memory to memory using `mov`. Valid operand combinations can be summarized like this: `reg/mem` + `reg/imm`. No `mem` + `mem`. – Alexey Frunze Jul 16 '12 at 05:52