Anonymous user
Sort stability: Difference between revisions
add task to aarch64 assembly raspberry pi
m (→{{header|REXX}}: added whitespace, split a compound statement.) |
(add task to aarch64 assembly raspberry pi) |
||
Line 29:
(This [[wp:Stable_sort#Comparison_of_algorithms|Wikipedia table]] shows the stability of some common sort routines).
<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 stableSort642.s */
/*******************************************/
/* 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 "Sort table for name of city :\n"
szMessSortCountry: .asciz "Sort table for country : \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:
.quad szLondon // address name string
.quad szUK // address conntry string
.quad szParis
.quad szFR
.quad szNewyork
.quad szUS
.quad szBirmin
.quad szUK
.quad szParis
.quad szUS
.quad szBirmin
.quad szUS
.equ NBELEMENTS, (. - TableCities) / city_end
.skip city_end // temp area for element in insertionSort
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
TableExtraSort: .skip city_end * NBELEMENTS
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrTableCities // address table
bl displayTable
ldr x0,qAdrszMessSortName
bl affichageMess
ldr x0,qAdrTableCities // address table
mov x1,0 // not use in routine
mov x2,NBELEMENTS // number of élements
mov x3,#city_name // sort by city name
mov x4,#'A' // alphanumeric
ldr x5,qAdrTableExtraSort
bl insertionSort
ldr x0,qAdrTableCities // address table
bl displayTable
ldr x0,qAdrszMessSortCountry
bl affichageMess
ldr x0,qAdrTableCities // address table
mov x1,0 // not use in routine
mov x2,NBELEMENTS // number of élements
mov x3,#city_country // sort by city country
mov x4,#'A' // alphanumeric
ldr x5,qAdrTableExtraSort
bl insertionSort
ldr x0,qAdrTableCities // 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
qAdrszMessSortCountry: .quad szMessSortCountry
qAdrTableExtraSort: .quad TableExtraSort
/******************************************************************/
/* insertion sort */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element */
/* x2 contains the number of element */
/* x3 contains the offset of area sort */
/* x4 contains the type of area sort N numeric A alpha */
insertionSort:
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
stp x10,x11,[sp,-16]! // save registers
mov x10,x0 // save address table
mov x8,x1 // save first element
mov x6,x2 // save number of element
mov x9,city_end // element size
add x5,x1,1 // index i
1: // start loop 1
mul x1,x5,x9
mul x2,x6,x9 // offset of extra element in table
bl copyElement // save element i in extra element
sub x2,x5,1 // index j
2: // start loop 2
mov x1,x6 // extra element
// x2 = element j
// x3 = offset area sort and x4 type A or N
bl comparArea
cmp x0,0
bge 3f
mov x0,x10 // restaur table address
mul x1,x2,x9 // offset element j
mov x7,x2 // save indice j
add x2,x2,1 // increment index j
mul x2,x2,x9 // offset element j + 1
bl copyElement // copy element j in element j + 1
sub x2,x7,1 // j = j - 1
cmp x2,x8 // compare first element
bge 2b // loop 2
3:
mov x0,x10 // restaur table address
add x2,x2,1 // increment index j
mul x1,x6,x9 // offset extra element
mul x2,x2,x9 // offset element j
bl copyElement
add x5,x5,1 // increment index i
cmp x5,x6 // end ?
blt 1b // loop 1
100:
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 x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* comparison sort area */
/******************************************************************/
/* x0 contains the address of table */
/* x1 indice area sort 1 */
/* x2 indice area sort 2 */
/* x3 contains the offset of area sort */
/* x4 contains the type of area sort N numeric A alpha */
comparArea:
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
stp x10,x11,[sp,-16]! // save registers
mov x5,city_end // element size
mul x1,x5,x1 // element offset
add x1,x1,x3 // area sort offset
ldr x6,[x0,x1] // load area sort 1
mul x2,x5,x2 // element offset 2
add x2,x2,x3 // area sort offset 2
ldr x7,[x0,x2] // load area sort 2
cmp x4,'A' // alphanumeric
beq 1f
cmp x6,x7 // comparison numeric value
blt 10f
bgt 11f
b 12f
1: // else comparison alpha area
mov x8,#0 // counter
2:
ldrb w9,[x6,x8] // byte string 1
ldrb w10,[x7,x8] // byte string 2
cmp w9,w10
bgt 11f
blt 10f
cmp w9,#0 // end string 1
beq 12f // end comparaison
add x8,x8,#1 // else add 1 to counter
b 2b // and loop
10: // lower
mov x0,-1
b 100f
11: // highter
mov x0,1
b 100f
12: // equal
mov x0,0
100:
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 x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* copy table element */
/******************************************************************/
/* x0 contains the address of table */
/* x1 offset origin element */
/* x2 offset destination element */
copyElement:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
mov x3,0 // counter
add x1,x1,x0 // address element 1
add x2,x2,x0 // address element 2
1:
ldrb w4,[x1,x3] // load one byte
strb w4,[x2,x3] // store one byte
add x3,x3,1 // increment counter
cmp x3,city_end
blt 1b
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
/******************************************************************/
/* 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
mov x6,city_end
1: // loop display table
mul x4,x3,x6
add x4,x4,city_name
ldr x1,[x2,x4]
ldr x0,qAdrsMessResult
bl strInsertAtCharInc // put name in message
mul x4,x3,x6
add x4,x4,city_country // and put contry in message
ldr x1,[x2,x4]
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
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
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
Sort table for country :
Name : Paris country : FR
Name : Birmingham country : UK
Name : London country : UK
Name : Birmingham country : US
Name : New York country : US
Name : Paris country : US
</pre>
=={{header|Ada}}==
[[Ada 83]] and [[Ada 95]] do not provide a standard sort utility.
| |||