Sorting algorithms/Patience sort: Difference between revisions
Content deleted Content added
m →{{header|REXX}}: changed whitespace. |
add task to aarch64 assembly raspberry pi |
||
Line 9: | Line 9: | ||
:* [[Longest increasing subsequence]] |
:* [[Longest increasing subsequence]] |
||
<br><br> |
<br><br> |
||
=={{header|AArch64 Assembly}}== |
|||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
|||
<lang AArch64 Assembly> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
|||
/* program patienceSort64.s */ |
|||
/*******************************************/ |
|||
/* Constantes file */ |
|||
/*******************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly */ |
|||
.include "../includeConstantesARM64.inc" |
|||
/*******************************************/ |
|||
/* Structures */ |
|||
/********************************************/ |
|||
/* structure Doublylinkedlist*/ |
|||
.struct 0 |
|||
dllist_head: // head node |
|||
.struct dllist_head + 8 |
|||
dllist_tail: // tail node |
|||
.struct dllist_tail + 8 |
|||
dllist_fin: |
|||
/* structure Node Doublylinked List*/ |
|||
.struct 0 |
|||
NDlist_next: // next element |
|||
.struct NDlist_next + 8 |
|||
NDlist_prev: // previous element |
|||
.struct NDlist_prev + 8 |
|||
NDlist_value: // element value or key |
|||
.struct NDlist_value + 8 |
|||
NDlist_fin: |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
szMessSortOk: .asciz "Table sorted.\n" |
|||
szMessSortNok: .asciz "Table not sorted !!!!!.\n" |
|||
sMessResult: .asciz "Value : @ \n" |
|||
szCarriageReturn: .asciz "\n" |
|||
.align 4 |
|||
TableNumber: .quad 1,3,11,6,2,-5,9,10,8,4,7 |
|||
#TableNumber: .quad 10,9,8,7,6,-5,4,3,2,1 |
|||
.equ NBELEMENTS, (. - TableNumber) / 8 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
sZoneConv: .skip 24 |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: // entry of program |
|||
ldr x0,qAdrTableNumber // address number table |
|||
mov x1,0 // first element |
|||
mov x2,NBELEMENTS // number of élements |
|||
bl patienceSort |
|||
ldr x0,qAdrTableNumber // address number table |
|||
bl displayTable |
|||
ldr x0,qAdrTableNumber // address number table |
|||
mov x1,NBELEMENTS // number of élements |
|||
bl isSorted // control sort |
|||
cmp x0,1 // sorted ? |
|||
beq 1f |
|||
ldr x0,qAdrszMessSortNok // no !! error sort |
|||
bl affichageMess |
|||
b 100f |
|||
1: // yes |
|||
ldr x0,qAdrszMessSortOk |
|||
bl affichageMess |
|||
100: // standard end of the program |
|||
mov x0,0 // return code |
|||
mov x8,EXIT // request to exit program |
|||
svc 0 // perform the system call |
|||
qAdrsZoneConv: .quad sZoneConv |
|||
qAdrszCarriageReturn: .quad szCarriageReturn |
|||
qAdrsMessResult: .quad sMessResult |
|||
qAdrTableNumber: .quad TableNumber |
|||
qAdrszMessSortOk: .quad szMessSortOk |
|||
qAdrszMessSortNok: .quad szMessSortNok |
|||
/******************************************************************/ |
|||
/* control sorted table */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 contains the number of elements > 0 */ |
|||
/* x0 return 0 if not sorted 1 if sorted */ |
|||
isSorted: |
|||
stp x2,lr,[sp,-16]! // save registers |
|||
stp x3,x4,[sp,-16]! // save registers |
|||
mov x2,0 |
|||
ldr x4,[x0,x2,lsl 3] |
|||
1: |
|||
add x2,x2,1 |
|||
cmp x2,x1 |
|||
bge 99f |
|||
ldr x3,[x0,x2, lsl 3] |
|||
cmp x3,x4 |
|||
blt 98f |
|||
mov x4,x3 |
|||
b 1b |
|||
98: |
|||
mov x0,0 // not sorted |
|||
b 100f |
|||
99: |
|||
mov x0,1 // sorted |
|||
100: |
|||
ldp x3,x4,[sp],16 // restaur 2 registers |
|||
ldp x2,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* patience sort */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 contains first start index |
|||
/* x2 contains the number of elements */ |
|||
patienceSort: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
stp x4,x5,[sp,-16]! // save registers |
|||
stp x6,x7,[sp,-16]! // save registers |
|||
stp x8,x9,[sp,-16]! // save registers |
|||
lsl x9,x2,1 // compute total size of piles (2 list pointer by pile ) |
|||
lsl x10,x9,3 // 8 bytes by number |
|||
sub sp,sp,x10 // reserve place to stack |
|||
mov fp,sp // frame pointer = stack |
|||
mov x3,0 // index |
|||
mov x4,0 |
|||
1: |
|||
str x4,[fp,x3,lsl 3] // init piles area |
|||
add x3,x3,1 // increment index |
|||
cmp x3,x9 |
|||
blt 1b |
|||
mov x3,0 // index value |
|||
mov x4,0 // counter first pile |
|||
mov x8,x0 // save table address |
|||
2: |
|||
ldr x1,[x8,x3,lsl 3] // load value |
|||
add x0,fp,x4,lsl 4 // pile address |
|||
bl isEmpty |
|||
cmp x0,0 // pile empty ? |
|||
bne 3f |
|||
add x0,fp,x4,lsl 4 // pile address |
|||
bl insertHead // insert value x1 |
|||
b 5f |
|||
3: |
|||
add x0,fp,x4,lsl 4 // pile address |
|||
ldr x5,[x0,dllist_head] |
|||
ldr x5,[x5,NDlist_value] // load first list value |
|||
cmp x1,x5 // compare value and last value on the pile |
|||
blt 4f |
|||
add x0,fp,x4,lsl 4 // pile address |
|||
bl insertHead // insert value x1 |
|||
b 5f |
|||
4: // value is smaller créate a new pile |
|||
add x4,x4,1 |
|||
add x0,fp,x4,lsl 4 // pile address |
|||
bl insertHead // insert value x1 |
|||
5: |
|||
add x3,x3,1 // increment index value |
|||
cmp x3,x2 // end |
|||
blt 2b // and loop |
|||
/* step 2 */ |
|||
mov x6,0 // index value table |
|||
6: |
|||
mov x3,0 // index pile |
|||
mov x5, 1<<62 // min |
|||
7: // search minimum |
|||
add x0,fp,x3,lsl 4 |
|||
bl isEmpty |
|||
cmp x0,0 |
|||
beq 8f |
|||
add x0,fp,x3,lsl 4 |
|||
bl searchMinList |
|||
cmp x0,x5 // compare min global |
|||
bge 8f |
|||
mov x5,x0 // smaller -> store new min |
|||
mov x7,x1 // and pointer to min |
|||
add x9,fp,x3,lsl 4 // and head list |
|||
8: |
|||
add x3,x3,1 // next pile |
|||
cmp x3,x4 // end ? |
|||
ble 7b |
|||
str x5,[x8,x6,lsl 3] // store min to table value |
|||
mov x0,x9 // and suppress the value in the pile |
|||
mov x1,x7 |
|||
bl suppressNode |
|||
add x6,x6,1 // increment index value |
|||
cmp x6,x2 // end ? |
|||
blt 6b |
|||
add sp,sp,x10 // stack alignement |
|||
100: |
|||
ldp x8,x9,[sp],16 // restaur 2 registers |
|||
ldp x6,x7,[sp],16 // restaur 2 registers |
|||
ldp x4,x5,[sp],16 // restaur 2 registers |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* Display table elements */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
displayTable: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
mov x2,x0 // table address |
|||
mov x3,0 |
|||
1: // loop display table |
|||
ldr x0,[x2,x3,lsl 3] |
|||
ldr x1,qAdrsZoneConv |
|||
bl conversion10S // décimal conversion |
|||
ldr x0,qAdrsMessResult |
|||
ldr x1,qAdrsZoneConv |
|||
bl strInsertAtCharInc // insert result at // character |
|||
bl affichageMess // display message |
|||
add x3,x3,1 |
|||
cmp x3,NBELEMENTS - 1 |
|||
ble 1b |
|||
ldr x0,qAdrszCarriageReturn |
|||
bl affichageMess |
|||
mov x0,x2 |
|||
100: |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* list is empty ? */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of the list structure */ |
|||
/* x0 return 0 if empty else return 1 */ |
|||
isEmpty: |
|||
ldr x0,[x0,#dllist_head] |
|||
cmp x0,0 |
|||
cset x0,ne |
|||
ret // return |
|||
/******************************************************************/ |
|||
/* insert value at list head */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of the list structure */ |
|||
/* x1 contains value */ |
|||
insertHead: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
stp x4,x5,[sp,-16]! // save registers |
|||
mov x4,x0 // save address |
|||
mov x0,x1 // value |
|||
bl createNode |
|||
cmp x0,#-1 // allocation error ? |
|||
beq 100f |
|||
ldr x2,[x4,#dllist_head] // load address first node |
|||
str x2,[x0,#NDlist_next] // store in next pointer on new node |
|||
mov x1,#0 |
|||
str x1,[x0,#NDlist_prev] // store zero in previous pointer on new node |
|||
str x0,[x4,#dllist_head] // store address new node in address head list |
|||
cmp x2,#0 // address first node is null ? |
|||
beq 1f |
|||
str x0,[x2,#NDlist_prev] // no store adresse new node in previous pointer |
|||
b 100f |
|||
1: |
|||
str x0,[x4,#dllist_tail] // else store new node in tail address |
|||
100: |
|||
ldp x4,x5,[sp],16 // restaur 2 registers |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* search value minimum */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of the list structure */ |
|||
/* x0 return min */ |
|||
/* x1 return address of node */ |
|||
searchMinList: |
|||
stp x2,lr,[sp,-16]! // save registers |
|||
stp x3,x4,[sp,-16]! // save registers |
|||
ldr x0,[x0,#dllist_head] // load first node |
|||
mov x3,1<<62 |
|||
mov x1,0 |
|||
1: |
|||
cmp x0,0 // null -> end |
|||
beq 99f |
|||
ldr x2,[x0,#NDlist_value] // load node value |
|||
cmp x2,x3 // min ? |
|||
bge 2f |
|||
mov x3,x2 // value -> min |
|||
mov x1,x0 // store pointer |
|||
2: |
|||
ldr x0,[x0,#NDlist_next] // load addresse next node |
|||
b 1b // and loop |
|||
99: |
|||
mov x0,x3 // return minimum |
|||
100: |
|||
ldp x3,x4,[sp],16 // restaur 2 registers |
|||
ldp x2,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* suppress node */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of the list structure */ |
|||
/* x1 contains the address to node to suppress */ |
|||
suppressNode: |
|||
stp x2,lr,[sp,-16]! // save registers |
|||
stp x3,x4,[sp,-16]! // save registers |
|||
ldr x2,[x1,#NDlist_next] // load addresse next node |
|||
ldr x3,[x1,#NDlist_prev] // load addresse prev node |
|||
cmp x3,#0 |
|||
beq 1f |
|||
str x2,[x3,#NDlist_next] |
|||
b 2f |
|||
1: |
|||
str x3,[x0,#NDlist_next] |
|||
2: |
|||
cmp x2,#0 |
|||
beq 3f |
|||
str x3,[x2,#NDlist_prev] |
|||
b 100f |
|||
3: |
|||
str x2,[x0,#NDlist_prev] |
|||
100: |
|||
ldp x3,x4,[sp],16 // restaur 2 registers |
|||
ldp x2,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* Create new node */ |
|||
/******************************************************************/ |
|||
/* x0 contains the value */ |
|||
/* x0 return node address or -1 if allocation error*/ |
|||
createNode: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
stp x4,x8,[sp,-16]! // save registers |
|||
mov x4,x0 // save value |
|||
// allocation place on the heap |
|||
mov x0,0 // allocation place heap |
|||
mov x8,BRK // call system 'brk' |
|||
svc 0 |
|||
mov x3,x0 // save address heap for output string |
|||
add x0,x0,NDlist_fin // reservation place one element |
|||
mov x8,BRK // call system 'brk' |
|||
svc #0 |
|||
cmp x0,-1 // allocation error |
|||
beq 100f |
|||
mov x0,x3 |
|||
str x4,[x0,#NDlist_value] // store value |
|||
mov x2,0 |
|||
str x2,[x0,#NDlist_next] // store zero to pointer next |
|||
str x2,[x0,#NDlist_prev] // store zero to pointer previous |
|||
100: |
|||
ldp x4,x8,[sp],16 // restaur 2 registers |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/********************************************************/ |
|||
/* File Include fonctions */ |
|||
/********************************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly */ |
|||
.include "../includeARM64.inc" |
|||
</lang> |
|||
=={{header|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi}} |
{{works with|as|Raspberry Pi}} |