Skip to content

Instantly share code, notes, and snippets.

@baines baines/asmsort.s
Created Jan 17, 2017

Embed
What would you like to do?
x86_64 linux sort program, 640 bytes
#!/bin/bash
# example: ./asmsort 3 2 1 -> prints 1 2 3
// 2>/dev/null; as -g $0 -o $0.o && ld -s $0.o -o asmsort; exit
.text
.global _start
quicksort:
dec %rsi # base case
jle qs_end
push %rbx
mov %rsi, %rax # swap index -> rax
lea (%rdi, %rsi, 8), %rbx # pivot addr -> rbx
mov %rsi, %rcx # loop counter -> rcx
mov (%rbx), %r8 # pivot value -> r8
qs_compare:
mov -8(%rdi, %rcx, 8), %rdx
cmp %r8, %rdx # compare array[rcx-1] against pivot
jl qs_noswap
xchg %rdx, -8(%rdi, %rax, 8)
mov %rdx, -8(%rdi, %rcx, 8) # swap array[rcx-1] and index if pivot smaller
dec %rax # and decrease the index
qs_noswap:
loop qs_compare # keep comparing until %rcx == 0
xchg %r8, (%rdi, %rax, 8) # done comparing, swap pivot into position
mov %r8, (%rbx)
sub %rax, %rsi # calc size for 2nd/upper recurdion
push %rsi # and store in stack
mov %rax, %rsi # set new size argument for 1st recurdion
lea 8(%rdi, %rax, 8), %rax # calc array for 2nd recurdion
push %rax # and store in stack
call quicksort # do 1st/lower recurdion
pop %rdi # get stuff back off the stack
pop %rsi
pop %rbx
jmp quicksort # tail recurdion for 2nd/upper section
# quicksort(array + index + 1, size - index - 1)
qs_end:
ret
cvtargs: # rdi=output buffer, rsi=argc, rdx=argv
mov (%rdx), %r10
test %r10, %r10 # check for null pointer & end
je cvt_end
xor %rax, %rax
xor %r8, %r8
cvt:
movzxb (%r10, %r8), %rcx # get next char from string
test %rcx, %rcx # end on null-terminator
je cvt_next
sub $48, %rcx # rax = (rax * 10) + (c - '0')
imul $10, %rax, %rax
add %rcx, %rax
inc %r8
jmp cvt # loop until we reach argv[argc] which will be
cvt_next: # a null pointer
mov %rax, (%rdi)
lea 8(%rdi), %rdi
lea 8(%rdx), %rdx
jmp cvtargs
cvt_end:
ret
outc: # rsp+8 = ptr to character to print
mov $1, %rax
mov %rax, %rdi
lea 8(%rsp), %rsi
mov %rax, %rdx
syscall # write(STDOUT, rsp+8, 1);
ret
outnum: # rdi = number to print
test %rdi, %rdi
je outnum_end # FIXME: won't print 0
xor %rdx, %rdx
mov $10, %rcx
mov %rdi, %rax
div %rcx # rcx = num / 10, rdx = num % 10
push %rdx
mov %rax, %rdi
call outnum # recurse, so MSD is output first
add $48, (%rsp) # add '0' to convert to ascii
call outc
pop %rdx
outnum_end:
ret
outnums: # rdi = ptr, rsi = count
push %rbx
push %rbp
push $' '
mov %rdi, %rbp # save ptr to rbp
mov %rsi, %rbx # save count to rbx
morenums:
mov (%rbp), %rdi
call outnum # output the number
call outc # output space separator
lea 8(%rbp), %rbp
dec %rbx
jnz morenums
outnums_end:
pop %rax
pop %rbp
pop %rbx
ret
_start:
mov %rsp, %rbp
lea 16(%rsp), %rdx # argv -> rdx
mov (%rsp), %rsi # argc-1 -> rsi
dec %rsi
jle theend
mov %rsi, %rax
mov %rsi, %rbp
shl $3, %rax # buffer size = (argc-1) * 8
sub %rax, %rsp
mov %rsp, %rdi # stack space buffer -> rdi
mov %rdi, %rbx
call cvtargs
mov %rbx, %rdi
call quicksort # do sorting
mov %rbx, %rdi
mov %rbp, %rsi
call outnums
push $10 # newline
call outc
theend:
mov $60, %rax # exit(0);
xor %rdi, %rdi
syscall
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.