Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #13963 > unrolled thread
| Started by | Branimir Maksimovic <branimir.maksimovic@icloud.com> |
|---|---|
| First post | 2021-10-03 19:20 +0000 |
| Last post | 2022-01-05 00:24 -0800 |
| Articles | 2 — 2 participants |
Back to article view | Back to comp.programming
merge sort vs radix sort aarch64 (done without debugger) Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-03 19:20 +0000
Re: merge sort vs radix sort aarch64 (done without debugger) Härra Ramob <hrramob@gmail.com> - 2022-01-05 00:24 -0800
| From | Branimir Maksimovic <branimir.maksimovic@icloud.com> |
|---|---|
| Date | 2021-10-03 19:20 +0000 |
| Subject | merge sort vs radix sort aarch64 (done without debugger) |
| Message-ID | <0on6J.9344$fZ.7470@fx06.iad> |
.set Node.next, 0
.set Node.data, 8
NodeSize = 16
.text
.globl _main
.align 4
; radix_sort_avx2
;extern _atoi
;extern _printf
;extern _puts
;extern _exit
;extern _rand_r
;extern _time
;extern _malloc
.macro stosq label,dest,val,len
mov x0,\dest
mov x1,\val
mov x2,\len
\label:
str x1,[x0],8
subs x2,x2,1
bne \label
.endm
_main:
sub sp,sp,#64
stp x29,x30,[sp,#48]
stp x19,x20,[sp,#32]
stp x21,x22,[sp,#16]
add x29,sp,#48
adrp x8, N@PAGE
mov w9,#4096*4096
str w9,[x8,N@PAGEOFF]
cmp x0, #1
beq .skip
ldr x0,[x1,#8]
bl _atoi
cmp w0,#1
blt .exit
adrp x8, N@PAGE
str w0,[x8,N@PAGEOFF]
.align 8
.skip:
mov x0,xzr
bl _time
adrp x8,seed@PAGE
str w0,[x8,seed@PAGEOFF] ; seed on time
str x0,[sp]
adrp x9,fmt1@PAGE
add x0,x9,fmt1@PAGEOFF
bl _printf ; print seed
adrp x9,fmt4@PAGE
add x0,x9,fmt4@PAGEOFF
adrp x8,N@PAGE
ldr w8,[x8,N@PAGEOFF]
str x8,[sp]
bl _printf
adrp x20,list1@PAGE
add x20,x20,list1@PAGEOFF
bl init_list
adrp x20,list2@PAGE
add x20,x20,list2@PAGEOFF
bl init_list
adrp x0,fmti@PAGE
add x0,x0,fmti@PAGEOFF
bl _puts
adrp x0,N@PAGE
ldr x0,[x0,N@PAGEOFF]
mov x1,#4
mov x2,xzr
mul x0,x0,x1
bl _malloc
adrp x8,array@PAGE
str x0, [x8,array@PAGEOFF]
adrp x0,list2@PAGE
ldr x0,[x0,list2@PAGEOFF]
adrp x1,list1@PAGE
ldr x1,[x1,list1@PAGEOFF]
bl assign_list
adrp x0,array@PAGE
ldr x0,[x0,array@PAGEOFF]
adrp x1,list1@PAGE
ldr x1,[x1,list1@PAGEOFF]
bl assign_array
adrp x0,fmtu@PAGE
add x0,x0,fmtu@PAGEOFF
adrp x20,list1@PAGE
add x20,x20,list1@PAGEOFF
bl print_list
;radix_avx2 equ 1
.ifdef radix_avx2
call init_time
mov rdi,[array]
mov esi,[N]
call [radix_sort_avx2]
mov rdi,fmtar
call time_me
.endif
.if 1
bl init_time
adrp x20,list1@PAGE
add x20,x20,list1@PAGEOFF
bl radix_sort
adrp x0,fmtr@PAGE
add x0,x0,fmtr@PAGEOFF
bl time_me
.endif
.if 1
bl init_time
adrp x0,list2@PAGE
ldr x0,[x0,list2@PAGEOFF]
sub sp,sp,32
str x0,[sp]
bl sort
adrp x0,list2@PAGE
ldr x1,[sp]
str x1,[x0,list2@PAGEOFF]
add sp,sp,32
adrp x0,fmtm@PAGE
add x0,x0,fmtm@PAGEOFF
bl time_me
.endif
adrp x0,list1@PAGE
ldr x0,[x0,list1@PAGEOFF]
adrp x1,list2@PAGE
ldr x1,[x1,list2@PAGEOFF]
bl equal_list
adrp x8,fmte@PAGE
add x8,x8,fmte@PAGEOFF
adrp x9,fmtne@PAGE
add x9,x9,fmtne@PAGEOFF
cmp x2,#1
csel x0,x8,x9,eq
bl _puts
/*
mov rdi,[array]
mov rsi,[list2]
call equal_array
mov rdi,fmte
test eax,eax
mov rbx,fmtne
cmovz rdi,rbx
call _puts
*/
adrp x0,fmts@PAGE
add x0,x0,fmts@PAGEOFF
adrp x20,list1@PAGE
add x20,x20,list1@PAGEOFF
bl print_list
adrp x0,fmts@PAGE
add x0,x0,fmts@PAGEOFF
adrp x20,list2@PAGE
add x20,x20,list2@PAGEOFF
bl print_list
adrp x20,list1@PAGE
ldr x20,[x20,list1@PAGEOFF]
bl length
mov x8,x0
adrp x0,fmt3@PAGE
add x0,x0,fmt3@PAGEOFF
mov x9,NodeSize
str x9,[sp]
str x8,[sp,8]
bl _printf
.exit:
ldp x29,x30,[sp,#48]
ldp x19,x20,[sp,#32]
ldp x21,x22,[sp,#16]
add sp,sp,#64
ret
.align 8
init_list:
str x30,[sp]
adrp x19,N@PAGE
ldr w19,[x19,N@PAGEOFF]
;address of list in x20
.L0:
mov x0,NodeSize
bl _malloc
ldr x8,[x20]
str x8,[x0,Node.next]
str x0,[x20]
adrp x0,seed@PAGE
add x0,x0,seed@PAGEOFF
bl _rand_r
; x0 -> random value
; divide by N, x8 -> N
adrp x8,N@PAGE
ldr w8,[x8,N@PAGEOFF]
udiv w2, w0, w8
msub w0, w2, w8, w0
ldr x8,[x20]
str w0, [x8,Node.data]
sub w19,w19,#1
cmp w19,wzr
bne .L0
ldr x30,[sp]
ret
print_list:
str x30,[sp]
sub sp,sp,16
bl _puts
ldr x20,[x20]
;x20 -> list address
mov x19,#16
.L01:
cmp x20,xzr
beq .exit1
adrp x0,fmt2@PAGE
add x0,x0,fmt2@PAGEOFF
mov x8,x20
ldr x8,[x8,Node.next]
str x8,[sp]
mov x9,x20
ldr w9,[x9,Node.data]
str x9,[sp,8]
bl _printf
ldr x20,[x20,Node.next]
sub x19,x19,1
cmp x19,xzr
beq .exit1
b .L01
.exit1:
add sp,sp,16
ldr x30,[sp]
ret
assign_list:
.L02:
cmp x1,xzr
beq .exit2
cmp x0,xzr
beq .exit2
ldr w8,[x1,Node.data]
str w8, [x0,Node.data]
ldr x1,[x1,Node.next]
ldr x0,[x0,Node.next]
b .L02
.exit2:
ret
assign_array:
.L03:
cmp x1,xzr
beq .exit3
ldr w8,[x1,Node.data]
str w8, [x0]
ldr x1,[x1,Node.next]
add x0,x0,#4
b .L03
.exit3:
ret
equal_list:
str x30,[sp,-16]!
mov x2,#1 ; return value if true
mov x20,x0
mov x3,x0
bl length
mov x4,x0
mov x20,x1
bl length
mov x5,x0
ldr x30,[sp],16
cmp x4,x5
bne .false
mov x0,x3
.L04:
cmp x1,xzr
beq .exit4
cmp x0,xzr
beq .exit4
ldr w8,[x1,Node.data]
ldr w9,[x0,Node.data]
cmp w8,w9
bne .false
ldr x1,[x1,Node.next]
ldr x0,[x0,Node.next]
b .L04
.exit4:
ret
.false:
mov x2,xzr
ret
equal_array:
mov x2,#1 ; return value if true
.L05:
cmp x1,xzr
beq .exit5
ldr w8,[x1,Node.data]
ldr w9,[x0]
cmp w8,w9
bne .false1
ldr x1,[x1,Node.next]
add x0,x0,#4
b .L05
.exit5:
ret
.false1:
mov x2,xzr
ret
; [sp] list to sort
sort:
sub sp,sp,32
str x30,[sp,16]
ldr x20,[sp,32]
bl length
mov x11,x0
cmp x11,#1
ble .exitsort
lsr x11,x11,#1
str xzr,[sp]
str xzr,[sp,8]
ldr x1,[sp,#32]
.L0sort: ; append to left
ldr x19,[sp]
ldr x10,[x1,Node.next]
str x19,[x1,Node.next]
str x1,[sp]
mov x1,x10
subs x11,x11,#1
bgt .L0sort
.L1sort: ; append to right
ldr x19,[sp,8]
ldr x10,[x1,Node.next]
str x19,[x1,Node.next]
str x1,[sp,8]
ldr x1,[x1,Node.next]
mov x1,x10
cmp x1,xzr
bne .L1sort
sub sp,sp,16
ldr x1,[sp,16]
str x1,[sp]
bl sort
ldr x1,[sp]
str x1,[sp,16]
ldr x1,[sp,24]
str x1,[sp]
bl sort
ldr x1,[sp]
str x1,[sp,24]
bl merge
ldr x1,[sp]
add sp,sp,#16
str x1,[sp,32]
.exitsort:
ldr x30,[sp,16]
add sp,sp,32
ret
; [rsp] output , [rsp+16] left, [rsp+24] right
merge:
sub sp,sp,16
str xzr,[sp,16]
str xzr,[sp]
.L0merge:
ldr x0,[sp,32]
cmp x0,xzr
beq .right
ldr x0,[sp,40]
cmp x0,xzr
beq .left
ldr x19,[sp,32]
ldr w1,[x19,Node.data]
ldr x11,[sp,40]
ldr w0,[x11,Node.data]
cmp w1,w0
blt .add_left
.add_right:
ldr x0,[sp]
cmp x0,xzr
beq .just_set_right
ldr x10,[sp]
str x11,[x10,Node.next]
ldr x10,[x11,Node.next]
str x10,[sp,40]
str xzr,[x11,Node.next]
str x11,[sp]
b .L0merge
.add_left:
ldr x0,[sp]
cmp x0,xzr
beq .just_set_left
ldr x10,[sp]
str x19,[x10,Node.next]
ldr x10,[x19,Node.next]
str x10,[sp,32]
str xzr,[x19,Node.next]
str x19,[sp]
b .L0merge
.just_set_left:
ldr x10,[x19,Node.next]
str xzr,[x19,Node.next]
str x19,[sp]
str x19,[sp,16]
str x10,[sp,32]
b .L0merge
.just_set_right:
ldr x10,[x11,Node.next]
str xzr,[x11,Node.next]
str x11,[sp]
str x11,[sp,16]
str x10,[sp,40]
b .L0merge
.right:
ldr x0,[sp,40]
cmp x0,xzr
beq .exitmerge
ldr x11,[sp,40]
ldr x0,[sp]
cmp x0,xzr
beq .just_set_right_only
ldr x10,[sp]
str x11,[x10,Node.next]
str x11,[sp]
ldr x10,[x11,Node.next]
str xzr,[x11,Node.next]
str x10,[sp,40]
b .right
.just_set_right_only:
ldr x10,[x11,Node.next]
str xzr,[x11,Node.next]
str x11,[sp]
str x11,[sp,16]
str x10,[sp,40]
b .right
.left:
ldr x0,[sp,32]
cmp x0,xzr
beq .exitmerge
ldr x19,[sp,32]
ldr x0,[sp]
cmp x0,xzr
beq .just_set_left_only
ldr x10,[sp]
str x19,[x10,Node.next]
str x19,[sp]
ldr x10,[x19,Node.next]
str xzr,[x19,Node.next]
str x10,[sp,32]
b .left
.just_set_left_only:
ldr x10,[x19,Node.next]
str xzr,[x19,Node.next]
str x19,[sp]
str x19,[sp,32]
str x10,[sp,40]
b .left
.exitmerge:
add sp,sp,16
ret
; x20 input list, x0 count
length:
mov x0,xzr
.L0L:
cmp x20,xzr
beq .exitL
ldr x20,[x20,Node.next]
add x0,x0,#1
b .L0L
.exitL:
ret
; [x20] list to sort
radix_sort:
sub sp,sp,#32*8
mov w9,wzr
.L0rad:
stosq .L0S,sp,#0,#32
ldr x8,[x20]
.L1rad:
cmp x8,xzr
beq .nextrad
mov w10,w9
lsl w10,w10,#2
ldr w11,[x8,Node.data]
lsr w11,w11,w10
and w11,w11,#0x0f
ldr x12,[sp,x11, lsl 3]
cmp x12,xzr
beq .just_set
ldr x13,[x8,Node.next]
add x11,x11,#16
ldr x0,[sp,x11,lsl 3]
str x8,[x0,Node.next]
str x8,[sp,x11,lsl 3]
sub x11,x11,#16
str xzr,[x8,Node.next]
mov x8,x13
b .L1rad
.just_set:
ldr x13,[x8,Node.next]
str x8,[sp,x11,lsl 3]
add x11,x11,16
str x8,[sp,x11,lsl 3]
sub x11,x11,16
str xzr,[x8,Node.next]
mov x8,x13
b .L1rad
.nextrad:
str xzr,[x20]
mov x8,xzr
mov x10,xzr
.L2rad:
ldr x11,[sp,x10, lsl 3]
.L3rad:
cmp x11,xzr
beq .next1rad
cmp x8,xzr
beq .just_set1
str x11,[x8,Node.next]
mov x8,x11
ldr x13,[x11,Node.next]
str xzr,[x11,Node.next]
mov x11,x13
b .L3rad
.just_set1:
mov x8,x11
str x11,[x20]
ldr x13,[x11,Node.next]
str xzr,[x11,Node.next]
mov x11,x13
b .L3rad
.next1rad:
add x10,x10,#1
cmp x10,#16
blt .L2rad
add x9,x9,#1
cmp x9,#8
blt .L0rad
.exitrad:
add sp,sp,#32*8
ret
init_time:
mrs x0,CNTPCT_EL0 ; counter
adrp x8,elapsed@PAGE
str x0, [x8,elapsed@PAGEOFF]
ret
time_me:
mrs x8,cntfrq_el0 ; clock
ucvtf d1,x8
mrs x8,CNTPCT_EL0 ; counter
adrp x9,elapsed@PAGE
ldr x9,[x9,elapsed@PAGEOFF]
sub x8,x8,x9
ucvtf d0,x8
fdiv d0,d0,d1
str d0,[sp]
b _printf
.data
.align 8
fmtpi: .asciz "pointer %p\n"
.align 8
fmti: .asciz "initialized\n"
.align 8
fmtu: .asciz "unsorted\n"
.align 8
fmts: .asciz "sorted\n"
.align 8
fmte: .asciz "equal\n"
.align 8
fmtne: .asciz "not equal\n"
.align 8
fmtm: .asciz "list merge elapsed %f seconds\n"
.align 8
fmtr: .asciz "list radix elapsed %f seconds\n"
.align 8
fmtari: .asciz "array radix elapsed %f seconds"
.align 8
fmt1: .asciz "seed: %d\n"
.align 8
fmt2: .asciz "%16p %d\n"
.align 8
fmt3: .asciz "size of node %d, length %d\n"
.align 8
fmt4: .asciz "N: %d\n"
.bss
.align 8
list1: .space 8
list2: .space 8
array: .space 8
elapsed: .space 8
.align 8
N: .space 4; number of nodes
.align 8
seed: .space 4
--
7-77-777
Evil Sinner!
to weak you should be meek, and you should brainfuck stronger
https://github.com/rofl0r/chaos-pp
[toc] | [next] | [standalone]
| From | Härra Ramob <hrramob@gmail.com> |
|---|---|
| Date | 2022-01-05 00:24 -0800 |
| Message-ID | <60ee7581-28b9-4043-8ab7-664c712e5dfbn@googlegroups.com> |
| In reply to | #13963 |
Branimir Maksimovic kirjutas Pühapäev, 3. oktoober 2021 kl 22:20:34 UTC+3: > .set Node.next, 0 > .set Node.data, 8 > NodeSize = 16 > .text > .globl _main > .align 4 > ; radix_sort_avx2 > ;extern _atoi > ;extern _printf > ;extern _puts > ;extern _exit > ;extern _rand_r > ;extern _time > ;extern _malloc > .macro stosq label,dest,val,len > mov x0,\dest > mov x1,\val > mov x2,\len > \label: > str x1,[x0],8 > subs x2,x2,1 > bne \label > .endm > _main: > sub sp,sp,#64 > stp x29,x30,[sp,#48] > stp x19,x20,[sp,#32] > stp x21,x22,[sp,#16] > add x29,sp,#48 > adrp x8, N@PAGE > mov w9,#4096*4096 > str w9,[x8,N@PAGEOFF] > cmp x0, #1 > beq .skip > ldr x0,[x1,#8] > bl _atoi > cmp w0,#1 > blt .exit > adrp x8, N@PAGE > str w0,[x8,N@PAGEOFF] > .align 8 > .skip: > mov x0,xzr > bl _time > adrp x8,seed@PAGE > str w0,[x8,seed@PAGEOFF] ; seed on time > str x0,[sp] > adrp x9,fmt1@PAGE > add x0,x9,fmt1@PAGEOFF > bl _printf ; print seed > > adrp x9,fmt4@PAGE > add x0,x9,fmt4@PAGEOFF > adrp x8,N@PAGE > ldr w8,[x8,N@PAGEOFF] > str x8,[sp] > bl _printf > adrp x20,list1@PAGE > add x20,x20,list1@PAGEOFF > bl init_list > adrp x20,list2@PAGE > add x20,x20,list2@PAGEOFF > bl init_list > adrp x0,fmti@PAGE > add x0,x0,fmti@PAGEOFF > bl _puts > > adrp x0,N@PAGE > ldr x0,[x0,N@PAGEOFF] > mov x1,#4 > mov x2,xzr > mul x0,x0,x1 > bl _malloc > adrp x8,array@PAGE > str x0, [x8,array@PAGEOFF] > > adrp x0,list2@PAGE > ldr x0,[x0,list2@PAGEOFF] > adrp x1,list1@PAGE > ldr x1,[x1,list1@PAGEOFF] > bl assign_list > > adrp x0,array@PAGE > ldr x0,[x0,array@PAGEOFF] > adrp x1,list1@PAGE > ldr x1,[x1,list1@PAGEOFF] > bl assign_array > > adrp x0,fmtu@PAGE > add x0,x0,fmtu@PAGEOFF > adrp x20,list1@PAGE > add x20,x20,list1@PAGEOFF > bl print_list > ;radix_avx2 equ 1 > .ifdef radix_avx2 > call init_time > mov rdi,[array] > mov esi,[N] > call [radix_sort_avx2] > mov rdi,fmtar > call time_me > .endif > > .if 1 > bl init_time > adrp x20,list1@PAGE > add x20,x20,list1@PAGEOFF > bl radix_sort > > adrp x0,fmtr@PAGE > add x0,x0,fmtr@PAGEOFF > bl time_me > .endif > .if 1 > bl init_time > adrp x0,list2@PAGE > ldr x0,[x0,list2@PAGEOFF] > sub sp,sp,32 > str x0,[sp] > bl sort > adrp x0,list2@PAGE > ldr x1,[sp] > str x1,[x0,list2@PAGEOFF] > add sp,sp,32 > adrp x0,fmtm@PAGE > add x0,x0,fmtm@PAGEOFF > bl time_me > .endif > adrp x0,list1@PAGE > ldr x0,[x0,list1@PAGEOFF] > adrp x1,list2@PAGE > ldr x1,[x1,list2@PAGEOFF] > bl equal_list > adrp x8,fmte@PAGE > add x8,x8,fmte@PAGEOFF > adrp x9,fmtne@PAGE > add x9,x9,fmtne@PAGEOFF > cmp x2,#1 > csel x0,x8,x9,eq > bl _puts > /* > mov rdi,[array] > mov rsi,[list2] > call equal_array > mov rdi,fmte > test eax,eax > mov rbx,fmtne > cmovz rdi,rbx > call _puts > */ > adrp x0,fmts@PAGE > add x0,x0,fmts@PAGEOFF > adrp x20,list1@PAGE > add x20,x20,list1@PAGEOFF > bl print_list > adrp x0,fmts@PAGE > add x0,x0,fmts@PAGEOFF > adrp x20,list2@PAGE > add x20,x20,list2@PAGEOFF > bl print_list > adrp x20,list1@PAGE > ldr x20,[x20,list1@PAGEOFF] > bl length > mov x8,x0 > adrp x0,fmt3@PAGE > add x0,x0,fmt3@PAGEOFF > mov x9,NodeSize > str x9,[sp] > str x8,[sp,8] > bl _printf > .exit: > ldp x29,x30,[sp,#48] > ldp x19,x20,[sp,#32] > ldp x21,x22,[sp,#16] > add sp,sp,#64 > ret > .align 8 > init_list: > str x30,[sp] > adrp x19,N@PAGE > ldr w19,[x19,N@PAGEOFF] > ;address of list in x20 > .L0: > mov x0,NodeSize > bl _malloc > ldr x8,[x20] > str x8,[x0,Node.next] > str x0,[x20] > adrp x0,seed@PAGE > add x0,x0,seed@PAGEOFF > bl _rand_r > ; x0 -> random value > ; divide by N, x8 -> N > adrp x8,N@PAGE > ldr w8,[x8,N@PAGEOFF] > > udiv w2, w0, w8 > msub w0, w2, w8, w0 > > ldr x8,[x20] > str w0, [x8,Node.data] > > sub w19,w19,#1 > cmp w19,wzr > bne .L0 > ldr x30,[sp] > ret > print_list: > str x30,[sp] > sub sp,sp,16 > bl _puts > ldr x20,[x20] > ;x20 -> list address > mov x19,#16 > .L01: > cmp x20,xzr > beq .exit1 > adrp x0,fmt2@PAGE > add x0,x0,fmt2@PAGEOFF > mov x8,x20 > ldr x8,[x8,Node.next] > str x8,[sp] > mov x9,x20 > ldr w9,[x9,Node.data] > str x9,[sp,8] > bl _printf > ldr x20,[x20,Node.next] > sub x19,x19,1 > cmp x19,xzr > beq .exit1 > b .L01 > .exit1: > add sp,sp,16 > ldr x30,[sp] > ret > assign_list: > .L02: > cmp x1,xzr > beq .exit2 > cmp x0,xzr > beq .exit2 > ldr w8,[x1,Node.data] > str w8, [x0,Node.data] > ldr x1,[x1,Node.next] > ldr x0,[x0,Node.next] > b .L02 > .exit2: > ret > assign_array: > .L03: > cmp x1,xzr > beq .exit3 > ldr w8,[x1,Node.data] > str w8, [x0] > ldr x1,[x1,Node.next] > add x0,x0,#4 > b .L03 > .exit3: > ret > equal_list: > str x30,[sp,-16]! > mov x2,#1 ; return value if true > mov x20,x0 > mov x3,x0 > bl length > mov x4,x0 > mov x20,x1 > bl length > mov x5,x0 > ldr x30,[sp],16 > cmp x4,x5 > bne .false > mov x0,x3 > .L04: > cmp x1,xzr > beq .exit4 > cmp x0,xzr > beq .exit4 > ldr w8,[x1,Node.data] > ldr w9,[x0,Node.data] > cmp w8,w9 > bne .false > ldr x1,[x1,Node.next] > ldr x0,[x0,Node.next] > b .L04 > .exit4: > ret > .false: > mov x2,xzr > ret > equal_array: > mov x2,#1 ; return value if true > .L05: > cmp x1,xzr > beq .exit5 > ldr w8,[x1,Node.data] > ldr w9,[x0] > cmp w8,w9 > bne .false1 > ldr x1,[x1,Node.next] > add x0,x0,#4 > b .L05 > .exit5: > ret > .false1: > mov x2,xzr > ret > ; [sp] list to sort > sort: > sub sp,sp,32 > str x30,[sp,16] > ldr x20,[sp,32] > bl length > mov x11,x0 > cmp x11,#1 > ble .exitsort > lsr x11,x11,#1 > str xzr,[sp] > str xzr,[sp,8] > ldr x1,[sp,#32] > .L0sort: ; append to left > ldr x19,[sp] > ldr x10,[x1,Node.next] > str x19,[x1,Node.next] > str x1,[sp] > mov x1,x10 > subs x11,x11,#1 > bgt .L0sort > .L1sort: ; append to right > ldr x19,[sp,8] > ldr x10,[x1,Node.next] > str x19,[x1,Node.next] > str x1,[sp,8] > ldr x1,[x1,Node.next] > mov x1,x10 > cmp x1,xzr > bne .L1sort > sub sp,sp,16 > ldr x1,[sp,16] > str x1,[sp] > bl sort > ldr x1,[sp] > str x1,[sp,16] > ldr x1,[sp,24] > str x1,[sp] > bl sort > ldr x1,[sp] > str x1,[sp,24] > bl merge > ldr x1,[sp] > add sp,sp,#16 > str x1,[sp,32] > .exitsort: > ldr x30,[sp,16] > add sp,sp,32 > ret > ; [rsp] output , [rsp+16] left, [rsp+24] right > merge: > sub sp,sp,16 > str xzr,[sp,16] > str xzr,[sp] > .L0merge: > ldr x0,[sp,32] > cmp x0,xzr > beq .right > ldr x0,[sp,40] > cmp x0,xzr > beq .left > ldr x19,[sp,32] > ldr w1,[x19,Node.data] > ldr x11,[sp,40] > ldr w0,[x11,Node.data] > cmp w1,w0 > blt .add_left > .add_right: > ldr x0,[sp] > cmp x0,xzr > beq .just_set_right > ldr x10,[sp] > str x11,[x10,Node.next] > ldr x10,[x11,Node.next] > str x10,[sp,40] > str xzr,[x11,Node.next] > str x11,[sp] > b .L0merge > .add_left: > ldr x0,[sp] > cmp x0,xzr > beq .just_set_left > ldr x10,[sp] > str x19,[x10,Node.next] > ldr x10,[x19,Node.next] > str x10,[sp,32] > str xzr,[x19,Node.next] > str x19,[sp] > b .L0merge > .just_set_left: > ldr x10,[x19,Node.next] > str xzr,[x19,Node.next] > str x19,[sp] > str x19,[sp,16] > str x10,[sp,32] > b .L0merge > .just_set_right: > ldr x10,[x11,Node.next] > str xzr,[x11,Node.next] > str x11,[sp] > str x11,[sp,16] > str x10,[sp,40] > b .L0merge > .right: > ldr x0,[sp,40] > cmp x0,xzr > beq .exitmerge > ldr x11,[sp,40] > ldr x0,[sp] > cmp x0,xzr > beq .just_set_right_only > ldr x10,[sp] > str x11,[x10,Node.next] > str x11,[sp] > ldr x10,[x11,Node.next] > str xzr,[x11,Node.next] > str x10,[sp,40] > b .right > .just_set_right_only: > ldr x10,[x11,Node.next] > str xzr,[x11,Node.next] > str x11,[sp] > str x11,[sp,16] > str x10,[sp,40] > b .right > .left: > ldr x0,[sp,32] > cmp x0,xzr > beq .exitmerge > ldr x19,[sp,32] > ldr x0,[sp] > cmp x0,xzr > beq .just_set_left_only > ldr x10,[sp] > str x19,[x10,Node.next] > str x19,[sp] > ldr x10,[x19,Node.next] > str xzr,[x19,Node.next] > str x10,[sp,32] > b .left > .just_set_left_only: > ldr x10,[x19,Node.next] > str xzr,[x19,Node.next] > str x19,[sp] > str x19,[sp,32] > str x10,[sp,40] > b .left > .exitmerge: > add sp,sp,16 > ret > ; x20 input list, x0 count > length: > mov x0,xzr > .L0L: > cmp x20,xzr > beq .exitL > ldr x20,[x20,Node.next] > add x0,x0,#1 > b .L0L > .exitL: > ret > ; [x20] list to sort > radix_sort: > sub sp,sp,#32*8 > mov w9,wzr > .L0rad: > stosq .L0S,sp,#0,#32 > ldr x8,[x20] > .L1rad: > cmp x8,xzr > beq .nextrad > mov w10,w9 > lsl w10,w10,#2 > ldr w11,[x8,Node.data] > lsr w11,w11,w10 > and w11,w11,#0x0f > ldr x12,[sp,x11, lsl 3] > cmp x12,xzr > beq .just_set > ldr x13,[x8,Node.next] > add x11,x11,#16 > ldr x0,[sp,x11,lsl 3] > str x8,[x0,Node.next] > str x8,[sp,x11,lsl 3] > sub x11,x11,#16 > str xzr,[x8,Node.next] > mov x8,x13 > b .L1rad > .just_set: > ldr x13,[x8,Node.next] > str x8,[sp,x11,lsl 3] > add x11,x11,16 > str x8,[sp,x11,lsl 3] > sub x11,x11,16 > str xzr,[x8,Node.next] > mov x8,x13 > b .L1rad > .nextrad: > str xzr,[x20] > mov x8,xzr > mov x10,xzr > .L2rad: > ldr x11,[sp,x10, lsl 3] > .L3rad: > cmp x11,xzr > beq .next1rad > cmp x8,xzr > beq .just_set1 > str x11,[x8,Node.next] > mov x8,x11 > ldr x13,[x11,Node.next] > str xzr,[x11,Node.next] > mov x11,x13 > b .L3rad > .just_set1: > mov x8,x11 > str x11,[x20] > ldr x13,[x11,Node.next] > str xzr,[x11,Node.next] > mov x11,x13 > b .L3rad > .next1rad: > add x10,x10,#1 > cmp x10,#16 > blt .L2rad > add x9,x9,#1 > cmp x9,#8 > blt .L0rad > .exitrad: > add sp,sp,#32*8 > ret > init_time: > mrs x0,CNTPCT_EL0 ; counter > adrp x8,elapsed@PAGE > str x0, [x8,elapsed@PAGEOFF] > ret > time_me: > mrs x8,cntfrq_el0 ; clock > ucvtf d1,x8 > mrs x8,CNTPCT_EL0 ; counter > adrp x9,elapsed@PAGE > ldr x9,[x9,elapsed@PAGEOFF] > sub x8,x8,x9 > ucvtf d0,x8 > fdiv d0,d0,d1 > str d0,[sp] > b _printf > .data > .align 8 > fmtpi: .asciz "pointer %p\n" > .align 8 > fmti: .asciz "initialized\n" > .align 8 > fmtu: .asciz "unsorted\n" > .align 8 > fmts: .asciz "sorted\n" > .align 8 > fmte: .asciz "equal\n" > .align 8 > fmtne: .asciz "not equal\n" > .align 8 > fmtm: .asciz "list merge elapsed %f seconds\n" > .align 8 > fmtr: .asciz "list radix elapsed %f seconds\n" > .align 8 > fmtari: .asciz "array radix elapsed %f seconds" > .align 8 > fmt1: .asciz "seed: %d\n" > .align 8 > fmt2: .asciz "%16p %d\n" > .align 8 > fmt3: .asciz "size of node %d, length %d\n" > .align 8 > fmt4: .asciz "N: %d\n" > .bss > .align 8 > list1: .space 8 > list2: .space 8 > array: .space 8 > elapsed: .space 8 > .align 8 > N: .space 4; number of nodes > .align 8 > seed: .space 4 > > > > -- > > 7-77-777 > Evil Sinner! > to weak you should be meek, and you should brainfuck stronger > https://github.com/rofl0r/chaos-pp 🙂 🙂 🙂 🙂 🙂 🙂
[toc] | [prev] | [standalone]
Back to top | Article view | comp.programming
csiph-web