Rosetta Code

Sort stability: Difference between revisions

Page Discussion

Sort stability (view source)

Revision as of 17:08, 1 October 2020

1,252 bytes removed ,  3 years ago
change sort insertion to merge sort to aarch64 assembly raspberry pi
(add task to aarch64 assembly raspberry pi)
(change sort insertion to merge sort to aarch64 assembly raspberry pi)
Line 33:
<lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program stableSort642stableSort641.s */
/* use merge sort and pointer table */
/* but use a extra table of pointer for the merge */
/*******************************************/
/* Constantes file */
Line 72 ⟶ 74:
.align 4
TableCities:
e1: .quad szLondon // address name string
.quad szUK // address conntrycountry 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
.equ NBELEMENTS, (. - TableCities) / city_end
.skip city_end // temp area for element inquad insertionSorte2
.quad e3
 
.quad e4
.quad e5
.quad e6
.equ NBELEMENTS, (. - ptrTableCities) / 8
/*********************************/
/* UnInitialized data */
Line 93 ⟶ 100:
.bss
sZoneConv: .skip 24
TableExtraSortptrTableExtraSort: .skip city_end8 * NBELEMENTS
/*********************************/
/* code section */
Line 100 ⟶ 107:
.global main
main: // entry of program
ldr x0,qAdrTableCities qAdrptrTableCities // address pointers table
bl displayTable
 
ldr x0,qAdrszMessSortName
bl affichageMess
 
ldr x0,qAdrTableCities qAdrptrTableCities // address pointers table
mov x1,0 // not use in routine
mov x2,NBELEMENTS - 1 // number of élements
mov x3,#city_name // sort by city name
mov x4,#'A' // alphanumeric
ldr x5,qAdrTableExtraSortqAdrptrTableExtraSort
bl insertionSortmergeSort
ldr x0,qAdrTableCities qAdrptrTableCities // address table
bl displayTable
Line 119 ⟶ 126:
bl affichageMess
 
ldr x0,qAdrTableCities qAdrptrTableCities // address table
mov x1,0 // not use in routine
mov x2,NBELEMENTS - 1 // number of élements
mov x3,#city_country // sort by city country
mov x4,#'A' // alphanumeric
ldr x5,qAdrTableExtraSortqAdrptrTableExtraSort
bl insertionSortmergeSort
ldr x0,qAdrTableCities qAdrptrTableCities // address table
bl displayTable
Line 139 ⟶ 146:
qAdrTableCities: .quad TableCities
qAdrszMessSortName: .quad szMessSortName
qAdrptrTableExtraSort: .quad ptrTableExtraSort
qAdrszMessSortCountry: .quad szMessSortCountry
qAdrTableExtraSortqAdrptrTableCities: .quad TableExtraSortptrTableCities
 
/******************************************************************/
/* merge sort insertion sort */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the index of 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 */
/* x5 contains address extra area */
insertionSort:
mergeSort:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,lr,[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 x10x6,x0 x1 // save addressindex first tableelement
mov x8x7,x1 x2 // save firstnumber of element
mov x6x11,x2 x0 // save numberaddress oftable element
movcmp x9x2,city_endx1 // elementend size?
ble 100f
add x5,x1,1 // index i
add x9,x2,x1
1: // start loop 1
lsr x9,x9,1 // number of element of each subset
mul x1,x5,x9
mov x2,x9
mul x2,x6,x9 // offset of extra element in table
bl mergeSort
bl copyElement // save element i in extra element
submov x2x1,x5,1 x9 // indexrestaur number of element of each jsubset
add x1,x1,1
2: // start loop 2
mov x1x2,x6x7 // restaur number // extraof element
bl mergeSort // x2 =sort elementfirst jsubset
add x10,x9,1
// x3 = offset area sort and x4 type A or N
1:
sub x1,x10,1
sub x8,x10,1
ldr x2,[x0,x1,lsl 3]
str x2,[x5,x8,lsl 3]
sub x10,x10,1
cmp x10,x6
bgt 1b
mov x10,x9
2:
add x1,x10,1
add x8,x7,x9
sub x8,x8,x10
ldr x2,[x0,x1,lsl 3]
str x2,[x5,x8,lsl 3]
add x10,x10,1
cmp x10,x7
blt 2b
 
mov x10,x6 //k
mov x1,x6 // i
mov x2,x7 // j
3:
mov x0,x5 // table address x1 = i x2 = j x3 = area sort offeset
bl comparArea
cmp x0,0
bge 3fbgt 5f
blt 4f
mov x0,x10 // restaur table address
mul x1,x2,x9 // offsetif equal and i < elementpivot j
cmp x1,x9
mov x7,x2 // save indice j
addble x2,x2,14f // incrementinverse indexto jstable
b 5f
mul x2,x2,x9 // offset element j + 1
4: bl copyElement // copy element j in element j// store element +subset 1
mov x0,x5
sub x2,x7,1 // j = j - 1
ldr x6,[x5,x1, lsl 3]
cmp x2,x8 // compare first element
str x6,[x11,x10, lsl 3]
bge 2b // loop 2
add x1,x1,1
3:
b 6f
mov x0,x10 // restaur table address
5: add x2,x2,1 // incrementstore element indexsubset j2
mov x0,x5
mul x1,x6,x9 // offset extra element
ldr x6,[x5,x2, lsl 3]
mul x2,x2,x9 // offset element j
str x6,[x11,x10, lsl 3]
bl copyElement
sub x2,x2,1
add x5,x5,1 // increment index i
6:
cmp x5,x6 // end ?
add x10,x10,1
blt 1b // loop 1
cmp x10,x7
ble 3b
mov x0,x11
 
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,lr,[sp],16 // restaur 2 registers
ldpret x1,lr,[sp],16 // restaurreturn to 2address lr registersx30
ret // return to address lr x30
 
 
/******************************************************************/
/* comparison sort area */
Line 217 ⟶ 248:
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
stp x10,x11,[sp,-16]! // save registers
movldr x5x1,city_end [x0,x1,lsl 3] // load pointer element size1
mulldr x1,x5x6,[x1 ,x3] // load area sort element offset1
addldr x1x2,x1[x0,x3 x2,lsl 3] // areaload pointer sortelement offset2
ldr x6x7,[x0x2,x1x3] // load area sort 1element 2
mulcmp x2x4,x5,x2'A' // elementnumeric or offsetalpha 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 // comparisoncompare numeric value
blt 10f
bgt 11f
b 12f
1: // else comparisoncompar alpha area string
mov x8,#0 // counter
2:
ldrb w9,[x6,x8] // byte string 1
ldrb w10w5,[x7,x8] // byte string 2
cmp w9,w10w5
bgt 11f
blt 10f
Line 242 ⟶ 270:
cmp w9,#0 // end string 1
beq 12f // end comparaison
add x8,x8,#1 // else add 1 toin counter
b 2b // and loop
Line 254 ⟶ 282:
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
Line 297 ⟶ 300:
mov x2,x0 // table address
mov x3,0
mov x6,city_end
1: // loop display table
mullsl x4,x3,x6#3 // offset element
ldr x6,[x2,x4] // load pointer
add x4,x4,city_name
ldr x1,[x2x6,x4city_name]
ldr x0,qAdrsMessResult
bl strInsertAtCharInc // put name in message
ldr x1,[x6,city_country] // and put country in the 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
bleblt 1b
ldr x0,qAdrszCarriageReturn
bl affichageMess
Line 325:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</lang>
<pre>
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/114408"