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?
