x86-64 Assembly — quicksort.asm
HW3 — x86-64 Assembly (NASM)
Toolchain
- Assembler: NASM version 2.16.03 (compiled Aug 31 2026), confirmed with
nasm -v. - Linker driver:
gcc (Ubuntu 15.2.0-16ubuntu1) 15.2.0, used only to driveldand link the C runtime startup (crt1.o/crti.o/crtn.o) plus libc, so a plainmain:label in the assembly file serves as the Cmainentry point. - Environment: WSL2 Ubuntu, run from Windows via
wsl.exe -d Ubuntu.
Build
nasm -f elf64 quicksort.asm -o quicksort.o
gcc quicksort.o -o quicksort -no-pie
-no-pie is used so the assembly can address .data/.bss globals with
simple absolute addressing (mov reg, label, [label]) instead of needing
default rel / RIP-relative addressing everywhere — the pragmatic choice
for a hand-written asm program per the assignment's toolchain notes.
Run
./quicksort
Full invocation used during development/testing (from the Windows side):
wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/asm' && nasm -f elf64 quicksort.asm -o quicksort.o && gcc quicksort.o -o quicksort -no-pie && ./quicksort"
The program writes HW3/results/asm.csv (path ../results/asm.csv relative
to this directory) and also prints each (n, time) row to stdout as it runs.
It reads no arguments and needs no input files.
Files
quicksort.asm— the entire program (randomized quicksort + timing harness- CSV/stdout output), single file, NASM syntax, linked against libc.
Notes
- Libc functions used via
extern:printf,fprintf,fopen,fclose,malloc,free,rand,srand,time,clock_gettime,exit. - Quicksort is implemented iteratively with an explicit (lo,hi) work stack
held in a small fixed-size local stack buffer, using the standard
"recurse into the smaller partition, push the larger one" trick, which
bounds the explicit stack depth to O(log n) — see comments at the top of
quicksort.asmfor the full design rationale and SysV ABI register map.
; ============================================================================
; HW3 - CSC 482 Language Comparison - x86-64 Assembly (NASM syntax)
;
; Randomized Quicksort per CLRS (Cormen, Leiserson, Rivest & Stein,
; "Introduction to Algorithms", Ch. 5) RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION
; pseudocode. In-place Lomuto partition; pivot chosen uniformly at random from
; the current subarray range at every partition step and swapped into the
; last slot before partitioning.
;
; No other external code used - this is an original implementation written
; directly from the CLRS pseudocode. The only external dependency is the C
; standard library (libc), linked via gcc, for I/O, timing, memory allocation
; and the RNG - exactly as the assignment's toolchain notes for this language
; call for ("extern-declaring libc functions ... rather than raw syscalls").
;
; Recursion strategy: RANDOMIZED-QUICKSORT is naturally recursive, but here it
; is implemented iteratively with an explicit work stack of (lo,hi) index
; pairs, using the standard "recurse on the smaller partition, push the larger
; one" trick. This bounds the explicit stack depth to O(log n) in the worst
; case (rather than O(n) for a naive push-both-sides approach), which is a
; well known and simple way to avoid deep native call-frame recursion in
; assembly while still implementing the exact same algorithm as CLRS's
; recursive pseudocode.
;
; SysV AMD64 ABI conventions followed throughout:
; - args: rdi, rsi, rdx, rcx, r8, r9 ; return: rax
; - callee-saved: rbx, rbp, r12-r15 (saved/restored by push/pop in any
; function that uses them)
; - caller-saved: rax, rcx, rdx, rsi, rdi, r8-r11 (assumed clobbered by
; any `call`)
; - rsp must be 16-byte aligned immediately before every `call` instruction
; - variadic calls (printf/fprintf) require AL = number of vector
; registers (xmm) used for the call
;
; Assemble/link (see README.md for details):
; nasm -f elf64 quicksort.asm -o quicksort.o
; gcc quicksort.o -o quicksort -no-pie
; ./quicksort
; ============================================================================
extern printf
extern fprintf
extern fopen
extern fclose
extern malloc
extern free
extern rand
extern srand
extern time
extern clock_gettime
extern exit
section .data
fmt_stdout: db "n=%d time=%.6f sec", 10, 0
fmt_csv_header: db "n,time_seconds", 10, 0
fmt_csv_row: db "%d,%.6f", 10, 0
mode_w: db "w", 0
csv_path: db "../results/asm.csv", 0
err_malloc: db "malloc failed", 10, 0
err_fopen: db "fopen failed for ../results/asm.csv", 10, 0
sanity_fmt: db "[sanity check] n=%d sorted=%d (1=yes,0=no)", 10, 0
four_const: dq 4.0
million_const: dq 1000000000.0
section .bss
ts_start: resb 16 ; struct timespec { long tv_sec; long tv_nsec; }
ts_end: resb 16
elapsed_val: resq 1 ; double, stashed across libc calls
section .text
global main
; ----------------------------------------------------------------------------
; int check_sorted(int32_t *arr /*rdi*/, int64_t n /*rsi*/)
; Leaf function (no calls, no stack frame needed). Returns 1 in eax if arr is
; sorted ascending, else 0. Used only as a debug/sanity check on the first
; couple of small iterations.
; ----------------------------------------------------------------------------
check_sorted:
cmp rsi, 2
jl .cs_true
mov rcx, 1
.cs_loop:
cmp rcx, rsi
jge .cs_true
mov eax, [rdi + rcx*4 - 4]
mov edx, [rdi + rcx*4]
cmp eax, edx
jg .cs_false
inc rcx
jmp .cs_loop
.cs_true:
mov eax, 1
ret
.cs_false:
xor eax, eax
ret
; ----------------------------------------------------------------------------
; void quicksort(int32_t *arr /*rdi*/, int64_t n /*rsi*/)
;
; Iterative randomized quicksort with an explicit (lo,hi) work stack held in
; a fixed local stack buffer (128 slots * 16 bytes = 2048 bytes -- far more
; than the O(log2(200,000,000)) ~= 28 max simultaneous frames the
; smaller-side-recurses-in-place / larger-side-pushed strategy can produce).
;
; Register map for the whole function body (fixed for the function's
; lifetime -- no push/pop after the prologue, so rsp/alignment never moves):
; r12 = arr pointer (callee-saved, set once)
; r14 = work-stack frame count (callee-saved)
; r15 = current lo (callee-saved; live across `call rand`)
; rbp = current hi (callee-saved; live across `call rand`)
; rbx = scratch, incl. partition range held live across `call rand`
; rax/rcx/rdx/rsi/rdi/r8/r9 = free scratch elsewhere (no calls pending)
; ----------------------------------------------------------------------------
quicksort:
push rbx
push rbp
push r12
push r14
push r15
sub rsp, 2048 ; work-stack buffer; rsp stays 16-aligned and
; fixed for the rest of the function
mov r12, rdi ; arr
cmp rsi, 2
jl .qs_done ; 0 or 1 elements: already sorted
mov r14, 0 ; work stack empty
xor r15, r15 ; lo = 0
lea rbp, [rsi - 1] ; hi = n - 1
jmp .qs_check
.qs_check:
cmp r15, rbp
jge .qs_pop ; lo >= hi: this branch's base case, pop next
; ---- RANDOMIZED-PARTITION(arr, lo=r15, hi=rbp) ----
; range = hi - lo + 1 ; kept in rbx (callee-saved) across `call rand`
mov rbx, rbp
sub rbx, r15
inc rbx
call rand ; eax = rand() in [0, RAND_MAX]
xor edx, edx
div ebx ; edx = rand() % range (32-bit unsigned div;
; range fits in 32 bits for all n used here)
add rdx, r15 ; rdx = r = random index in [lo, hi]
; swap arr[r] <-> arr[hi]
mov eax, [r12 + rdx*4]
mov ecx, [r12 + rbp*4]
mov [r12 + rbp*4], eax
mov [r12 + rdx*4], ecx
mov edi, [r12 + rbp*4] ; pivot value = arr[hi] (rdi free: no calls pending)
mov r8, r15
dec r8 ; i = lo - 1
mov r9, r15 ; j = lo
.qs_part_loop:
cmp r9, rbp
jge .qs_part_end ; j reached hi: stop (Lomuto loop is j = lo..hi-1)
mov eax, [r12 + r9*4]
cmp eax, edi
jg .qs_part_skip
inc r8
mov ecx, [r12 + r8*4]
mov [r12 + r8*4], eax
mov [r12 + r9*4], ecx
.qs_part_skip:
inc r9
jmp .qs_part_loop
.qs_part_end:
inc r8 ; r8 = i+1 = final pivot index p
mov eax, [r12 + r8*4]
mov ecx, [r12 + rbp*4]
mov [r12 + rbp*4], eax
mov [r12 + r8*4], ecx
; ---- end partition; r8 = p ----
mov rax, r8
sub rax, r15 ; leftSize = p - lo
mov rcx, rbp
sub rcx, r8 ; rightSize = hi - p
cmp rax, rcx
jl .qs_left_smaller
; leftSize >= rightSize: push the larger left half (lo, p-1),
; continue in place with the smaller right half (p+1, hi)
mov rax, r14
shl rax, 4 ; byte offset = frame_count * 16
mov [rsp + rax], r15 ; push lo
mov rdx, r8
dec rdx
mov [rsp + rax + 8], rdx ; push p-1
inc r14
mov r15, r8
inc r15 ; lo = p + 1 (hi unchanged)
jmp .qs_check
.qs_left_smaller:
; rightSize > leftSize: push the larger right half (p+1, hi),
; continue in place with the smaller left half (lo, p-1)
mov rax, r14
shl rax, 4
mov rdx, r8
inc rdx
mov [rsp + rax], rdx ; push p+1
mov [rsp + rax + 8], rbp ; push hi
inc r14
mov rbp, r8
dec rbp ; hi = p - 1 (lo unchanged)
jmp .qs_check
.qs_pop:
cmp r14, 0
je .qs_done
dec r14
mov rax, r14
shl rax, 4
mov r15, [rsp + rax]
mov rbp, [rsp + rax + 8]
jmp .qs_check
.qs_done:
add rsp, 2048
pop r15
pop r14
pop r12
pop rbp
pop rbx
ret
; ----------------------------------------------------------------------------
; main() - timing harness. Follows DESIGN.md's protocol exactly:
; n starts at 1000, doubles each iteration; fresh random array each
; iteration (generation not timed); time only the quicksort call via
; clock_gettime(CLOCK_MONOTONIC); stop when elapsed > 4.0s, or 25
; iterations have run, or the next n would exceed 200,000,000.
;
; Register map (fixed across the whole function; callee-saved so they
; survive every libc `call`):
; rbx = n (current) r12 = FILE* csv
; r13 = iteration count r14 = malloc'd array pointer (this iteration)
; ----------------------------------------------------------------------------
main:
push rbx
push r12
push r13
push r14
push r15 ; 5 pushes -> rsp 16-aligned from here on,
; no further push/pop until the epilogue
; srand(time(NULL))
xor edi, edi
call time
mov rdi, rax
call srand
; FILE *csv = fopen("../results/asm.csv", "w")
mov rdi, csv_path
mov rsi, mode_w
call fopen
test rax, rax
jnz .fopen_ok
mov rdi, err_fopen
xor eax, eax
call printf
mov edi, 1
call exit
.fopen_ok:
mov r12, rax
; header row
mov rdi, r12
mov rsi, fmt_csv_header
xor eax, eax
call fprintf
mov rbx, 1000 ; n = 1000
xor r13, r13 ; iteration count = 0
.main_loop:
cmp r13, 25
jge .main_loop_end
; arr = malloc(n * 4)
mov rax, rbx
imul rax, rax, 4
mov rdi, rax
call malloc
test rax, rax
jnz .malloc_ok
mov rdi, err_malloc
xor eax, eax
call printf
mov edi, 1
call exit
.malloc_ok:
mov r14, rax
; fill arr with n random ints in [0, 1000000) -- NOT timed
xor r15, r15
.fill_loop:
cmp r15, rbx
jge .fill_done
call rand
xor edx, edx
mov ecx, 1000000
div ecx
mov [r14 + r15*4], edx
inc r15
jmp .fill_loop
.fill_done:
; start timer
mov rdi, 1 ; CLOCK_MONOTONIC
mov rsi, ts_start
call clock_gettime
; time only this call
mov rdi, r14
mov rsi, rbx
call quicksort
; stop timer
mov rdi, 1
mov rsi, ts_end
call clock_gettime
; elapsed = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec)/1e9
mov rax, [ts_end]
sub rax, [ts_start]
mov rcx, [ts_end + 8]
sub rcx, [ts_start + 8]
test rcx, rcx
jns .no_borrow
dec rax
add rcx, 1000000000
.no_borrow:
cvtsi2sd xmm0, rax
cvtsi2sd xmm1, rcx
movsd xmm2, [million_const]
divsd xmm1, xmm2
addsd xmm0, xmm1
movsd [elapsed_val], xmm0
; sanity check on the first two (small-n) iterations only: verify sorted
cmp r13, 2
jge .skip_sanity
mov rdi, r14
mov rsi, rbx
call check_sorted
mov rdx, rax ; sorted flag
mov rsi, rbx ; n
mov rdi, sanity_fmt
xor eax, eax
call printf
.skip_sanity:
; print to stdout: printf(fmt_stdout, n, elapsed)
movsd xmm0, [elapsed_val]
mov rdi, fmt_stdout
mov rsi, rbx
mov al, 1
call printf
; write CSV row: fprintf(csv, fmt_csv_row, n, elapsed)
movsd xmm0, [elapsed_val]
mov rdi, r12
mov rsi, fmt_csv_row
mov rdx, rbx
mov al, 1
call fprintf
; free(arr)
mov rdi, r14
call free
; stop if elapsed > 4.0
movsd xmm0, [elapsed_val]
movsd xmm1, [four_const]
comisd xmm0, xmm1
ja .main_loop_end
; stop if next n would exceed 200,000,000
mov rax, rbx
imul rax, rax, 2
cmp rax, 200000000
jg .main_loop_end
mov rbx, rax ; n *= 2
inc r13
jmp .main_loop
.main_loop_end:
mov rdi, r12
call fclose
xor eax, eax
pop r15
pop r14
pop r13
pop r12
pop rbx
ret