How to resolve the algorithm Sort stability step by step in the AArch64 Assembly programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Sort stability step by step in the AArch64 Assembly programming language
Table of Contents
Problem Statement
When sorting records in a table by a particular column or field, a stable sort will always retain the relative order of records that have the same key.
In this table of countries and cities, a stable sort on the second column, the cities, would keep the US Birmingham above the UK Birmingham. (Although an unstable sort might, in this case, place the US Birmingham above the UK Birmingham, a stable sort routine would guarantee it). Similarly, stable sorting on just the first column would generate UK London as the first item and US Birmingham as the last item (since the order of the elements having the same first word – UK or US – would be maintained).
(This Wikipedia table shows the stability of some common sort routines).
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sort stability step by step in the AArch64 Assembly programming language
Source code in the aarch64 programming language
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program stableSort641.s */
/* use merge sort and pointer table */
/* but use a extra table of pointer 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 "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:
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
ptrTableExtraSort: .skip 8 * NBELEMENTS
/*********************************/
/* 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 // 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,qAdrptrTableExtraSort
bl mergeSort
ldr x0,qAdrptrTableCities // address table
bl displayTable
ldr x0,qAdrszMessSortCountry
bl affichageMess
ldr x0,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,qAdrptrTableExtraSort
bl mergeSort
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
qAdrptrTableExtraSort: .quad ptrTableExtraSort
qAdrszMessSortCountry: .quad szMessSortCountry
qAdrptrTableCities: .quad ptrTableCities
/******************************************************************/
/* merge 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 */
mergeSort:
stp 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 x6,x1 // save index first element
mov x7,x2 // save number of element
mov x11,x0 // save address table
cmp x2,x1 // end ?
ble 100f
add x9,x2,x1
lsr x9,x9,1 // number of element of each subset
mov x2,x9
bl mergeSort
mov x1,x9 // restaur number of element of each subset
add x1,x1,1
mov x2,x7 // restaur number of element
bl mergeSort // sort first subset
add x10,x9,1
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
bgt 5f
blt 4f
// if equal and i < pivot
cmp x1,x9
ble 4f // inverse to stable
b 5f
4: // store element subset 1
mov x0,x5
ldr x6,[x5,x1, lsl 3]
str x6,[x11,x10, lsl 3]
add x1,x1,1
b 6f
5: // store element subset 2
mov x0,x5
ldr x6,[x5,x2, lsl 3]
str x6,[x11,x10, lsl 3]
sub x2,x2,1
6:
add x10,x10,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 x3,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
ldr x1,[x0,x1,lsl 3] // load pointer element 1
ldr x6,[x1,x3] // load area sort element 1
ldr x2,[x0,x2,lsl 3] // load pointer element 2
ldr x7,[x2,x3] // load area sort element 2
cmp x4,'A' // numeric or alpha ?
beq 1f
cmp x6,x7 // compare numeric value
blt 10f
bgt 11f
b 12f
1: // else compar alpha string
mov x8,#0
2:
ldrb w9,[x6,x8] // byte string 1
ldrb w5,[x7,x8] // byte string 2
cmp w9,w5
bgt 11f
blt 10f
cmp w9,#0 // end string 1
beq 12f // end comparaison
add x8,x8,#1 // else add 1 in 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 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"
You may also check:How to resolve the algorithm Dot product step by step in the Smalltalk programming language
You may also check:How to resolve the algorithm Abstract type step by step in the PHP programming language
You may also check:How to resolve the algorithm Unbias a random generator step by step in the Sidef programming language
You may also check:How to resolve the algorithm Count in octal step by step in the Scheme programming language
You may also check:How to resolve the algorithm Universal Turing machine step by step in the PicoLisp programming language