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+1) which is not necessary, of course, but then the inner loop doesn't overflow, however,
len extra operations are performed.
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
I have tested the algorithm on four different arrays : random, one-element, two-element, and sorted (the labels
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?