Sort using a custom comparator: Difference between revisions
Content added Content deleted
(Added Wren) |
(add task to aarch64 assembly raspberry pi) |
||
Line 12: | Line 12: | ||
'''Note:''' Lexicographic order is case-insensitive. |
'''Note:''' Lexicographic order is case-insensitive. |
||
<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 customSort64.s */ |
|||
/* use merge sort iteratif and pointer table */ |
|||
/* but use a extra table on stack for the merge */ |
|||
/*******************************************/ |
|||
/* Constantes file */ |
|||
/*******************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly*/ |
|||
.include "../includeConstantesARM64.inc" |
|||
/*******************************************/ |
|||
/* Structures */ |
|||
/********************************************/ |
|||
/* city structure */ |
|||
.struct 0 |
|||
city_name: // |
|||
.struct city_name + 8 // string pointer |
|||
city_country: // |
|||
.struct city_country + 8 // string pointer |
|||
city_end: |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
sMessResult: .asciz "Name : @ country : @ \n" |
|||
szMessSortName: .asciz "Ascending sort table for name of city :\n" |
|||
szMessSortCitiesDesc: .asciz "Descending sort table for name of city : \n" |
|||
szCarriageReturn: .asciz "\n" |
|||
// cities name |
|||
szLondon: .asciz "London" |
|||
szNewyork: .asciz "New York" |
|||
szBirmin: .asciz "Birmingham" |
|||
szParis: .asciz "Paris" |
|||
// country name |
|||
szUK: .asciz "UK" |
|||
szUS: .asciz "US" |
|||
szFR: .asciz "FR" |
|||
.align 4 |
|||
TableCities: |
|||
e1: .quad szLondon // address name string |
|||
.quad szUK // address country string |
|||
e2: .quad szParis |
|||
.quad szFR |
|||
e3: .quad szNewyork |
|||
.quad szUS |
|||
e4: .quad szBirmin |
|||
.quad szUK |
|||
e5: .quad szParis |
|||
.quad szUS |
|||
e6: .quad szBirmin |
|||
.quad szUS |
|||
/* pointers table */ |
|||
ptrTableCities: .quad e1 |
|||
.quad e2 |
|||
.quad e3 |
|||
.quad e4 |
|||
.quad e5 |
|||
.quad e6 |
|||
.equ NBELEMENTS, (. - ptrTableCities) / 8 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
sZoneConv: .skip 24 |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: // entry of program |
|||
ldr x0,qAdrptrTableCities // address pointers table |
|||
bl displayTable |
|||
ldr x0,qAdrszMessSortName |
|||
bl affichageMess |
|||
ldr x0,qAdrptrTableCities // address pointers table |
|||
mov x1,0 // first element |
|||
mov x2,NBELEMENTS // number of élements |
|||
adr x3,comparAreaAlphaCrois // address custom comparator ascending |
|||
bl mergeSortIter |
|||
ldr x0,qAdrptrTableCities // address table |
|||
bl displayTable |
|||
ldr x0,qAdrszMessSortCitiesDesc |
|||
bl affichageMess |
|||
ldr x0,qAdrptrTableCities // address table |
|||
mov x1,0 // first element |
|||
mov x2,NBELEMENTS // number of élements |
|||
adr x3,comparAreaAlphaDecrois // address custom comparator descending |
|||
bl mergeSortIter |
|||
ldr x0,qAdrptrTableCities // address table |
|||
bl displayTable |
|||
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 |
|||
qAdrTableCities: .quad TableCities |
|||
qAdrszMessSortName: .quad szMessSortName |
|||
qAdrszMessSortCitiesDesc: .quad szMessSortCitiesDesc |
|||
qAdrptrTableCities: .quad ptrTableCities |
|||
/******************************************************************/ |
|||
/* merge sort iteratif */ |
|||
/* use an extra table on stack */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 contains the index of first element */ |
|||
/* x2 contains the number of element */ |
|||
/* x3 contains the address of custom comparator */ |
|||
mergeSortIter: |
|||
stp fp,lr,[sp,-16]! // save registers |
|||
stp x1,x2,[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 |
|||
stp x10,x11,[sp,-16]! // save registers |
|||
stp x12,x13,[sp,-16]! // save registers |
|||
stp x14,x15,[sp,-16]! // save registers |
|||
mov x15,x0 // save address |
|||
mov x4,x1 // save N0 first element |
|||
sub x5,x2,1 // save N° last element |
|||
tst x2,1 // number of element odd ? |
|||
add x13,x2,1 // yes then add 1 |
|||
csel x13,x13,x2,ne // to have a multiple to 16 bytes |
|||
lsl x13,x13,3 // for reserve the extra table to the stack |
|||
sub sp,sp,x13 |
|||
mov fp,sp // frame register = address extra table on stack |
|||
mov x10,1 // subset size |
|||
1: |
|||
mov x6,x4 // first element |
|||
2: |
|||
lsl x8,x10,1 // compute end subset |
|||
add x8,x8,x6 |
|||
sub x8,x8,1 |
|||
add x7,x6,x8 // compute median |
|||
lsr x7,x7,1 |
|||
cmp x8,x5 // maxi ? |
|||
ble 21f // no |
|||
mov x8,x5 // yes -> end subset = maxi |
|||
cmp x6,0 // subset final ? |
|||
beq 21f // no |
|||
cmp x7,x8 // compare median end subset |
|||
blt 21f |
|||
mov x7,x8 // maxi -> median |
|||
21: |
|||
add x9,x7,1 |
|||
mov x0,x15 |
|||
3: // copy first subset on extra table |
|||
sub x1,x9,1 |
|||
ldr x2,[x0,x1,lsl 3] |
|||
str x2,[fp,x1,lsl 3] |
|||
sub x9,x9,1 |
|||
cmp x9,x6 |
|||
bgt 3b |
|||
mov x9,x7 |
|||
cmp x7,x8 |
|||
beq 41f |
|||
4: // and copy inverse second subset on extra table |
|||
add x1,x9,1 |
|||
add x12,x7,x8 |
|||
sub x12,x12,x9 |
|||
ldr x2,[x0,x1,lsl 3] |
|||
str x2,[fp,x12,lsl 3] |
|||
add x9,x9,1 |
|||
cmp x9,x8 |
|||
blt 4b |
|||
41: |
|||
mov x11,x6 //k |
|||
mov x1,x6 // i |
|||
mov x2,x8 // j |
|||
5: // and now merge the two subset on final table |
|||
mov x0,fp |
|||
blr x3 |
|||
cmp x0,0 |
|||
bgt 7f |
|||
blt 6f |
|||
// si egalité et si i < pivot |
|||
cmp x1,x7 |
|||
ble 6f |
|||
b 7f |
|||
6: |
|||
ldr x12,[fp,x1, lsl 3] |
|||
str x12,[x15,x11, lsl 3] |
|||
add x1,x1,1 |
|||
b 8f |
|||
7: |
|||
ldr x12,[fp,x2, lsl 3] |
|||
str x12,[x15,x11, lsl 3] |
|||
sub x2,x2,1 |
|||
8: |
|||
add x11,x11,1 |
|||
cmp x11,x8 |
|||
ble 5b |
|||
9: |
|||
mov x0,x15 |
|||
lsl x2,x10,1 |
|||
add x6,x6,x2 // compute new subset |
|||
cmp x6,x5 // end ? |
|||
ble 2b |
|||
lsl x10,x10,1 // size of subset * 2 |
|||
cmp x10,x5 // end ? |
|||
ble 1b |
|||
100: |
|||
add sp,sp,x13 // stack alignement |
|||
ldp x14,x15,[sp],16 // restaur 2 registers |
|||
ldp x12,x13,[sp],16 // restaur 2 registers |
|||
ldp x10,x11,[sp],16 // restaur 2 registers |
|||
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 x1,x2,[sp],16 // restaur 2 registers |
|||
ldp fp,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* ascending comparison sort area */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 indice area sort 1 */ |
|||
/* x2 indice area sort 2 */ |
|||
comparAreaAlphaCrois: |
|||
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 |
|||
ldr x1,[x0,x1,lsl 3] // load pointer element 1 |
|||
ldr x6,[x1,city_name] // load area sort element 1 |
|||
ldr x2,[x0,x2,lsl 3] // load pointer element 2 |
|||
ldr x7,[x2,city_name] // load area sort element 2 |
|||
mov x8,#0 // compar alpha string |
|||
1: |
|||
ldrb w9,[x6,x8] // byte string 1 |
|||
ldrb w5,[x7,x8] // byte string 2 |
|||
cmp w9,w5 |
|||
bgt 11f // croissant |
|||
blt 10f |
|||
cmp w9,#0 // end string 1 |
|||
beq 12f // end comparaison |
|||
add x8,x8,#1 // else add 1 in counter |
|||
b 1b // and loop |
|||
10: // lower |
|||
mov x0,-1 |
|||
b 100f |
|||
11: // highter |
|||
mov x0,1 |
|||
b 100f |
|||
12: // equal |
|||
mov x0,0 |
|||
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 |
|||
/******************************************************************/ |
|||
/* descending comparison sort area */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 indice area sort 1 */ |
|||
/* x2 indice area sort 2 */ |
|||
comparAreaAlphaDecrois: |
|||
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 |
|||
ldr x1,[x0,x1,lsl 3] // load pointer element 1 |
|||
ldr x6,[x1,city_name] // load area sort element 1 |
|||
ldr x2,[x0,x2,lsl 3] // load pointer element 2 |
|||
ldr x7,[x2,city_name] // load area sort element 2 |
|||
mov x8,#0 // compar alpha string |
|||
1: |
|||
ldrb w9,[x6,x8] // byte string 1 |
|||
ldrb w5,[x7,x8] // byte string 2 |
|||
cmp w9,w5 |
|||
blt 11f // descending |
|||
bgt 10f |
|||
cmp w9,#0 // end string 1 |
|||
beq 12f // end comparaison |
|||
add x8,x8,#1 // else add 1 in counter |
|||
b 1b // and loop |
|||
10: // lower |
|||
mov x0,-1 |
|||
b 100f |
|||
11: // highter |
|||
mov x0,1 |
|||
b 100f |
|||
12: // equal |
|||
mov x0,0 |
|||
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 |
|||
stp x4,x5,[sp,-16]! // save registers |
|||
stp x6,x7,[sp,-16]! // save registers |
|||
mov x2,x0 // table address |
|||
mov x3,0 |
|||
1: // loop display table |
|||
lsl x4,x3,#3 // offset element |
|||
ldr x6,[x2,x4] // load pointer |
|||
ldr x1,[x6,city_name] |
|||
ldr x0,qAdrsMessResult |
|||
bl strInsertAtCharInc // put name in message |
|||
ldr x1,[x6,city_country] // and put country in the message |
|||
bl strInsertAtCharInc // insert result at @ character |
|||
bl affichageMess // display message |
|||
add x3,x3,1 |
|||
cmp x3,#NBELEMENTS |
|||
blt 1b |
|||
ldr x0,qAdrszCarriageReturn |
|||
bl affichageMess |
|||
100: |
|||
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 |
|||
/********************************************************/ |
|||
/* File Include fonctions */ |
|||
/********************************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly */ |
|||
.include "../includeARM64.inc" |
|||
</lang> |
|||
<pre> |
|||
Name : London country : UK |
|||
Name : Paris country : FR |
|||
Name : New York country : US |
|||
Name : Birmingham country : UK |
|||
Name : Paris country : US |
|||
Name : Birmingham country : US |
|||
Ascending sort table for name of city : |
|||
Name : Birmingham country : UK |
|||
Name : Birmingham country : US |
|||
Name : London country : UK |
|||
Name : New York country : US |
|||
Name : Paris country : FR |
|||
Name : Paris country : US |
|||
Descending sort table for name of city : |
|||
Name : Paris country : FR |
|||
Name : Paris country : US |
|||
Name : New York country : US |
|||
Name : London country : UK |
|||
Name : Birmingham country : UK |
|||
Name : Birmingham country : US |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
{{incorrect}} |
{{incorrect}} |