4
\$\begingroup\$

I returned to study assembly language. And this is actually my first function written in Yasm. Implementing this function is a suggested project from this book. I slightly modified the pseudo code presented in that book:

input:
    an array of integers 'array'
    length of 'array' 'len'

algorithm:
    for i := 0 to len-1
        min := array[i]
        i_min := i

        for j := i+1 to len-1
            if array[j] < min then
                min := array[j]
                i_min := j

        swap array[i_min] and array[i]

NOTE: The inner loop starts from i+1 so we need the outer loop only up to len-2. However, it is inconvenient because we can't just compare a counter with a decremented variable in a single instruction (as I understand). That is why I just left the outer loop up to len-1 and seemingly it overflows but actually it is not a problem, and as a result a dummy swap (the last element with itself) is made as a last step. In the original code the inner loop starts from i (not i+1) which is not necessary, of course, but then the inner loop doesn't overflow, however, len extra operations are performed.

Sorting function

I think the code is well commented (maybe even overcommented (: ) so I won't explain it. The only thing I want to highlight is the use of registers instead of stack for local variables.

section .text
    global ssort
        ; Selection sorting algorithm
        ; Arguments:
        ;   rdi : address of the array (the first element)
        ;   rsi : value of the length
        ; Local variables:
        ;   registers :
        ;       r10 : counter for the outer loop (i)
        ;       r11 : counter for the inner loop (j)
        ;       r12 : min (minimal element found in the inner loop)
        ;       rbx : i_min (position of min)
        ;       rcx : temporary variable for swapping
        ssort:
            prologue:
                ; save registers' values
                push    r12
                push    rbx
                push    rcx
            mov     r10, 0  ; i = 0
            outer_loop:
                ; for ( i = 0; i < length; i++ )
                cmp     r10, rsi    ; compare i and length
                jb      continue_outer_loop    ; if i < length (unsigned) then continue
                jmp     epilogue    ; else end
                continue_outer_loop:
                    mov     r12, qword [rdi + (r10 * 8)]   ; min = list[i]
                    mov     rbx, r10    ; i_min = i
                    mov     r11, r10    ; j = i 
                    inner_loop:
                        ; for( j = i+1; j < length; j++ )
                        inc     r11     ; j++
                        cmp     r11, rsi    ; compare j and length     
                        jb      continue_inner_loop     ; ( j < length (unsigned) ) conditional jump (distance limit)  
                        jmp     swap_elements  ; ( else ) unconditional jump (no distance limit)
                        continue_inner_loop:
                            cmp     r12, qword [rdi + (r11 * 8)]     ; compare min and list[j]
                            jg      update_min  ; if min > list[j] then update min
                            jmp     inner_loop  ; else check next element 
                            update_min:
                                mov     r12, qword [rdi + (r11 * 8)]    ; min = list[j]
                                mov     rbx, r11    ; i_min = j
                            jmp     inner_loop
                    swap_elements:
                        ; swap min and list[i]
                        mov     rcx, qword [rdi + (r10 * 8)]    ; rcx = list[i], use rcx as a temporary variable
                        mov     qword [rdi + (rbx * 8)], rcx    ; list[i_min] = list[i]
                        mov     qword [rdi + (r10 * 8)], r12    ; list[i] = min
                    inc     r10     ; i++
                    jmp     outer_loop
            epilogue:
                ; restore initial registers' values
                pop     rcx
                pop     rbx
                pop     r12
            ret

Test

I have tested the algorithm on four different arrays : random, one-element, two-element, and sorted (the labels one, two, three and four are for debugging purposes):

section .data

    list            dq      4, 24, 17, 135, -4, 450, 324, 0, 3
    len             dq      9

    list2           dq      1 
    len2            dq      1

    list3           dq      4, 3 
    len3            dq      2

    list4           dq      -1, 0, 1, 2 
    len4            dq      4


secion .text

    global _start
    _start:
        one:
            mov     rdi, list    
            mov     rsi, qword [len] 
            call    ssort

        two:
            mov     rdi, list2  
            mov     rsi, qword [len2] 
            call    ssort

        three:
            mov     rdi, list3    
            mov     rsi, qword [len3] 
            call    ssort

        four:
            mov     rdi, list4    
            mov     rsi, qword [len4] 
            call    ssort

    _end:
        mov     rax, sys_exit
        mov     rdi, EXIT_SUCCESS
        syscall

What do you think?

\$\endgroup\$
2
\$\begingroup\$

I understand that you've written this code staying close to the high level example, but assembly code is typically not written that way. To me at least this code is less readable than it could be.
The code that you have is of course a good starting point, but in my opinion it should not stay the final version.

A selection of improvements

To clear a register instead of using mov r10, 0, you should write xor r10d, r10d. This is both faster and shorter code.

In a snippet like:

cmp     r10, rsi
jb      continue_outer_loop
jmp     epilogue
continue_outer_loop:

you can save yourself from writing the extra label and remove one of the jumps, if you simply reverse the condition:

cmp     r10, rsi
jnb     epilogue

This is something that you can apply 3 times in your code.

The only thing I want to highlight is the use of registers instead of stack for local variables.

It's certainly a good idea to use registers whenever you can, but here it makes for less readable text. Perhaps you could use the EQU directive to makes things clearer.

i       equ     r10 ; counter for the outer loop
j       equ     r11 ; counter for the inner loop
min     equ     r12 ; minimal element found in the inner loop
i_min   equ     rbx ; position of min
temp    equ     rcx ; temporary variable for swapping

I agree that you've slightly over-commented the source. Some comments were redundant.

mov     r12, qword [rdi + (r10 * 8)]   ; min = list[i]

I don't know YASM, but I think you can drop the qword tag in many instructions where the size is clear from the other operands:

mov     r12, [rdi + (r10 * 8)]   ; min = list[i]

r12 is a qword so the mention of the tag is redundant.

My rewrite, more the assembly way

See what you do with the EQU idea!

ssort:
    push    r12
    push    rbx
    push    rcx
    xor     r10d, r10d              ; i = 0
  outer_loop:                       ; for ( i = 0; i < length; i++ )
    cmp     r10, rsi                ; compare i and length
    jnb     epilogue                ; if i >= length (unsigned) thenend
    mov     r12, [rdi + (r10 * 8)]  ; min = list[i]
    mov     rbx, r10                ; i_min = i
    mov     r11, r10                ; j = i 
  inner_loop:                       ; for( j = i+1; j < length; j++ )
    inc     r11                     ; j++
    cmp     r11, rsi                ; compare j and length     
    jnb     swap_elements           ; ( j >= length (unsigned) ) unconditional jump (no distance limit)
    cmp     r12, [rdi + (r11 * 8)]  ; compare min and list[j]
    jng     inner_loop              ; if min <= list[j] then check next element 
    mov     r12, [rdi + (r11 * 8)]  ; min = list[j]
    mov     rbx, r11                ; i_min = j
    jmp     inner_loop
  swap_elements:                    ; swap min and list[i]
    mov     rcx, [rdi + (r10 * 8)]  ; rcx = list[i], use rcx as a temporary variable
    mov     [rdi + (rbx * 8)], rcx  ; list[i_min] = list[i]
    mov     [rdi + (r10 * 8)], r12  ; list[i] = min
    inc     r10                     ; i++
    jmp     outer_loop
  epilogue:
    pop     rcx
    pop     rbx
    pop     r12
    ret
\$\endgroup\$
2
  • \$\begingroup\$ OK. Thank you for answer. One comment per a recommendation. About jump instructions. I do it in that way because of (from the book I referred to) "...the target label must be within +/- 128 bytes from the conditional jump instruction" (see comments in the code also). I think that way is safer. Though, probably the linker would throw an error if there was a problem. I mean I did it on purpose. \$\endgroup\$ – LRDPRDX Jun 14 '20 at 19:51
  • \$\begingroup\$ @LRDPRDX That's a very old recommendation dating back to the era of the 8086 pc. Since then we have the full range of conditional jumps that can jump all the distance you need. I don't think it's safer using that trick. A good compiler/assembler will choose the optimal form for you automatically, using the shortest encoding possible. \$\endgroup\$ – Sep Roland Jun 14 '20 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.