Anonymous user
Sort using a custom comparator: Difference between revisions
add task to aarch64 assembly raspberry pi
(Added Wren) |
(add task to aarch64 assembly raspberry pi) |
||
Line 12:
'''Note:''' Lexicographic order is case-insensitive.
<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}}==
{{incorrect}}
| |||