1

I'm trying to implement a selection sort algorithm in C++ Assembly Blocks. The code below shows the sorter function with the assembly block within. I am trying to emulate the selection sort algorithm shown below my code. When I compile my cpp file and try to run the given code (separate from this) I get the exact same numbers back in the same order. (the first data set has 10 numbers [10, -20, 5, 12, 30, -5, -22, 55, 52, 0]). What should I change to get my desired results?

void sorter (long* list, long count, long opcode)
{
/* Move the array pointer to rax, opcode to rbx, count to rcx */
/* The following sample code swap the array elements in reverse order */
/* You would need to replace it with the logic from the bubble sort algorithm */
    long temp;
    long y;
asm
(
    "movq %0, %%rax;"                       //Sets array pointer (base address of array) to rax register
    "movq %1, %%rbx;"                       //Sets opcode (1 for Asc. | 2 for Desc) to rbx register
    "movq %2, %%rcx;"                       //Sets count (total amount of #'s) to rcx register
    "xorq %%rdx, %%rdx;"                    //Sets rdx (x counter) to 0 
    "movq %3, %%r9;"                        //Sets temp (used for swapping) to r9 register
"loop_start:"
    "dec %%rcx;"                            //Decrements rcx (count)
    "cmpq %%rdx, %%rcx;"                    //Compares rdx (x counter) to rcx (count)
    "jle done;"                             //If rcx (total amount of #'s) is zero, then finish
    "cmpq $1,%%rbx;"                        //Compares rbx (opcode) to 1
    "jne desc;"                             //Jump to descending if opcode != 1 (2 or more)

    "mov %%rdx, %%rdi;"                     //Sets rdi (y counter) = x

"inner_loop:"
    "inc %%rdi;"                            //Increments rdi (y counter) (y++)
    "movq (%%rax, %%rdx, 8), %%rsi;"        //Sets rsi to array pointer + 8*rdx (array[x])
    "movq (%%rax, %%rdi, 8), %%r8;"         //Sets r8 to array pointer + 8*rdi (array[y])
    "cmpq %%r8, %%rsi;"
    "jle swap;"

    "cmpq %%rdi, %%rcx;"                    //Compares rdi (y) and rcx (count)
    "jb inner_loop;"                       //Jump to inner_loop if y < count
    "inc %%rdx;"                            //Increment rdx (x counter) (x++)
    "jmp loop_start;"                       //Closing for outer loop (loop_start)

"swap:"
    "xchgq %%rsi,%%r9;"
    "xchgq %%r8, %%rsi;"
    "xchgq %%r9, %%r8;"
    "jmp inner_loop;"

"desc:"                                     //if opcode is 2 then reverse the list
    "movq (%%rax, %%rcx, 8), %%r10;"        //Moves array pointer + 8*rcx(count) to r10 (starts at last index of the array)
    "movq (%%rax, %%rdx, 8), %%r11;"        //Moves array pointer + 8*rdx to r11 (starts at first index of the array)
    "xchgq %%r10, (%%rax, %%rdx, 8);"
    "xchgq %%r11, (%%rax, %%rcx, 8);"
    "inc %%rdx;"
    "jmp loop_start;"

"done:"
     : 
     : "m" (list), "m" (opcode), "m" (count), "m" (temp)
     : 
     ); 
}

Selection sort algorithm to implement:

void sorter (long* list, long count, long opcode)
{
    long x, y, temp;
    for (x = 0; x < count - 1; x++)
        for (y = x; y < count; y++)
            if (list[x] > list[y])
            {
                temp = list[x];
                list[x] = list[y];
                list[y] = temp;
            }
}
Richard Tumaneng
  • 11
  • 1
  • I see where you read the values from memory, then I see where you compare and (potentially) swap. But I'm not seeing `swap` or `inner_loop` writing the changed values back? – David Wohlferd Oct 25 '21 at 18:47
  • How do I write the changed values back? I assumed that the xchgq in swap would have done that, but I am not very good at assembly code, so I definitely could be wrong – Richard Tumaneng Oct 25 '21 at 20:10
  • **This is an unsafe use of `asm()`**. You use a bunch of registers without telling the compiler about them. https://stackoverflow.com/tags/inline-assembly/info / https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html. This will likely break surrounding code if it inlines. Or even if not, because you picked some call-preserved regs like RBX. Also missing a `"memory"` clobber, [How can I indicate that the memory \*pointed\* to by an inline ASM argument may be used?](https://stackoverflow.com/q/56432259) – Peter Cordes Oct 25 '21 at 20:48
  • And you also strangely ask the compiler for your function args to be in memory, forcing it to spill/reload them. Generally best to use `[list] "+r" (list)` register operands and `"=r"` temporaries to let the compiler allocate registers use `%[list]` everywhere in the asm template, instead of hard-coding a register number. If you want to hard-code registers, just write a separate `.S` file, instead of defeating the purpose of inline asm. – Peter Cordes Oct 25 '21 at 20:51
  • Also note that `xchg` with memory has an implicit `lock` prefix, so it's *very* slow compare to normal loads/stores. (Has to drain the store buffer and atomically swap.) SelectionSort only needs one load in the inner loop that finds the min or max (and position). You only need to reload the min or max when it changes. – Peter Cordes Oct 25 '21 at 20:54
  • This is how it was assigned and we have to use C++ Inline Assembly. It's a mandatory requirement to 'xchg' aswell. – Richard Tumaneng Oct 26 '21 at 02:55
  • Then fix your clobber list to at least include `"memory"` and all the hard-coded registers you use. (Which might be none if you let the compiler pick registers for everything, only ever using `%[name]`). Have you used a debugger to single-step through your code? – Peter Cordes Oct 26 '21 at 03:42
  • (Out of curiosity, are you required to use `xchg` *with memory*, or could you just `xchg` a register? That would make it pretty silly, just exchanging for the sake of it since you normally only need `mov` to update an index and value, or a pair of `mov` stores from opposite registers than you loaded from to swap memory locations.) – Peter Cordes Oct 26 '21 at 03:42

0 Answers0