arm_quick_sort.s

.global main
.func main

main:
  LDR R0, =random_seed
  LDR R0, [R0]
  MOV R1, #num_elements
  BL _rng_loop
  LDR R0, =unordered_msg
  BL printf
  BL _print_arr

  LDR R0, =data_arr
  LDR R1, =data_arr
  ADD R1, #36

  BL _quicksort

  LDR R0, =ordered_msg
  BL printf
  BL _print_arr
  BAL _exit


@R0 contains low address
@R1 contains high address
_quicksort:

  @ remember where to return
  PUSH {LR}
  @ remember the bottom of the stack
  @ to check when we're done
  MOV R9, SP

  @ Note: if this doesn't work, first push R0, then R1

  PUSH {R0}
  PUSH {R1}

  _while_stack_not_empty:

    CMP R9, SP
    BEQ _stack_empty

    POP {R3}
    POP {R2}

    SUB R4, R3, R2
    CMP R4, #4
    BLT _while_stack_not_empty

    PUSH {R1-R4, R9}

    MOV R0, R2
    MOV R1, R3    

    BL _partition

    POP {R1-R4, R9}

    MOV R4, R0
    SUB R4, R4, #4
    CMP R4, R2 
    BLT _next1

    PUSH { R2 }
    PUSH { R4 } 

    _next1:

    MOV R4, R0
    ADD R4, R4, #4
    CMP R4, R3
    BGT _next2

    PUSH { R4 }
    PUSH { R3 }

    _next2:

      BAL _while_stack_not_empty

  _stack_empty:

    POP {PC}

_exit2:
  MOV R7, #1
  SWI 0

@R0 contains the low address
@R1 contains the high address
@We assume partition based on last element
@A better implementation would do a median-of-3 partition 
@to prevent quicksort degenerating from O(n*log(n)) to O(n^2)
@Return position of pivot in R0
_partition:

  MOV R5, R0
  MOV R6, R1

  MOV R2, R0
  LDR R2, [R2]

  _past_sel:  
    ADD R1, R1, #4
    @ loop forever
    _partition_loop_forever:
      @ do {i = i + 1 } while A[i] < pivot
      _first_partition_loop:
        @ if (i == right) break
        CMP R0, R6
        BEQ _second_partition_loop
        ADD R0, R0, #4
        LDR R3, [R0]
        CMP R3, R2
        BLT _first_partition_loop         
      @ do {j = j - 1} while A[j] > pivot
      _second_partition_loop:
        @ if (j == left) break
        CMP R1, R5
        BEQ _end_partition
        SUB R1, R1, #4
        LDR R4, [R1]
        CMP R4, R2
        BGT _second_partition_loop
      @ if i >= j  then return j
      CMP R0, R1
      BGE _end_partition
      @ swap A[i] with A[j] 
      STR R3, [R1]
      STR R4, [R0]

      BGE _end_partition
      BAL _partition_loop_forever

    _end_partition:

      LDR R7, [R5]
      LDR R8, [R1]
      STR R7, [R1]
      STR R8, [R5]

      MOV R0, R1
      MOV PC, LR


@ XORShift random number generator.
@ It takes state in R0 and generates a new state.
@ The first state in R0 is the seed of the RNG
 _rng:
  MOV R1, R0, LSL #13
  EOR R0, R0, R1
  MOV R1, R0, LSR #17
  EOR R0, R0, R1
  MOV R1, R0, LSL #5
  EOR R0, R0, R1
  MOV PC, LR

_rng_loop:
  PUSH {LR}
  LDR R2, =data_arr

  _rng_loop_inner:
    PUSH {R1}
    BL _rng
    POP {R1}
    STR R0, [R2], #4
    SUBS R1, R1, #1
    BNE _rng_loop_inner
    POP {LR}

  MOV PC, LR

_print_arr:

  PUSH {LR}
  LDR R2, =data_arr
  MOV R3, #num_elements

  _print_arr_inner:
    LDR R0, =num_str
    LDR R1, [R2], #4
    PUSH {R2, R3}
    BL printf
    POP {R2, R3}
    SUBS R3, R3, #1
    BNE _print_arr_inner

  POP {LR}
  MOV PC, LR

_exit:
  MOV R7, #1
  SWI 0

.data

.equ num_elements, 10
.equ num_bytes, 40

random_seed: .word 123

num_str: .asciz "%d\n"
unordered_msg: .asciz "\nUnordered numbers:\n"
ordered_msg: .asciz "\nOrdered numbers:\n"
data_arr: .skip num_bytes

Executed on Raspberry Pi v3 (Broadcom BCM2837, i.e. ARM Cortex A53)

Assembled via gcc rather than as + ld (note "main" rather than "_start" symbol)

To build and run:
gcc arm_quick_sort.s -o arm_quick_sort && ./arm_quick_sort

 

Output with random_seed = 123

Unordered numbers:
31682556
-276305998
2101636938
-452479844
1628673942
1875546790
-1906851511
-1180330826
1834579151
1003884751

Ordered numbers:
-1906851511
-1180330826
-452479844
-276305998
31682556
1003884751
1628673942
1834579151
1875546790
2101636938

Executed on Raspberry Pi v3 (Broadcom BCM2837, i.e. ARM Cortex A53)

Assembled via gcc rather than as + ld (note "main" rather than "_start" symbol)

To build and run:
gcc arm_quick_sort.s -o arm_quick_sort && ./arm_quick_sort

 

Output with random_seed = 42

Unordered numbers:
11355432
-1458948948
476557059
-646921280
-534983740
1441438134
-581500456
-1863322962
-1174750317
1067267639

Ordered numbers:
-1863322962
-1458948948
-1174750317
-646921280
-581500456
-534983740
11355432
476557059
1067267639
1441438134