Sorting algorithms/Patience sort: Difference between revisions

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

<lang ARM Assembly>

/* ARM assembly Raspberry PI */

/* program patienceSort.s */

/* REMARK 1 : this program use routines in a include file

see task Include a file language arm assembly

for the routine affichageMess conversion10

see at end of this program the instruction include */

/* for constantes see task include a file in arm assembly */

/************************************/

/* Constantes */

/************************************/

.include "../constantes.inc"

.include "../../ficmacros.s"

/*******************************************/

/* Structures */

/********************************************/

/* structure Doublylinkedlist*/

.struct 0

dllist_head: @ head node

.struct dllist_head + 4

dllist_tail: @ tail node

.struct dllist_tail + 4

dllist_fin:

/* structure Node Doublylinked List*/

.struct 0

NDlist_next: @ next element

.struct NDlist_next + 4

NDlist_prev: @ previous element

.struct NDlist_prev + 4

NDlist_value: @ element value or key

.struct NDlist_value + 4

NDlist_fin:

/*********************************/

/* Initialized data */

/*********************************/

.data

szMessSortOk: .asciz "Table sorted.\n"

szMessSortNok: .asciz "Table not sorted !!!!!.\n"

sMessResult: .asciz "Value : @ \n"

szCarriageReturn: .asciz "\n"

.align 4

TableNumber: .int 1,11,3,6,2,5,9,10,8,4,7

#TableNumber: .int 10,9,8,7,6,5,4,3,2,1

.equ NBELEMENTS, (. - TableNumber) / 4

/*********************************/

/* UnInitialized data */

/*********************************/

.bss

sZoneConv: .skip 24

/*********************************/

/* code section */

/*********************************/

.text

.global main

main: @ entry of program

ldr r0,iAdrTableNumber @ address number table

mov r1,#0 @ first element

mov r2,#NBELEMENTS @ number of élements

bl patienceSort

ldr r0,iAdrTableNumber @ address number table

bl displayTable

ldr r0,iAdrTableNumber @ address number table

mov r1,#NBELEMENTS @ number of élements

bl isSorted @ control sort

cmp r0,#1 @ sorted ?

beq 1f

ldr r0,iAdrszMessSortNok @ no !! error sort

bl affichageMess

b 100f

1: @ yes

ldr r0,iAdrszMessSortOk

bl affichageMess

100: @ standard end of the program

mov r0, #0 @ return code

mov r7, #EXIT @ request to exit program

svc #0 @ perform the system call

iAdrszCarriageReturn: .int szCarriageReturn

iAdrsMessResult: .int sMessResult

iAdrTableNumber: .int TableNumber

iAdrszMessSortOk: .int szMessSortOk

iAdrszMessSortNok: .int szMessSortNok

/******************************************************************/

/* control sorted table */

/******************************************************************/

/* r0 contains the address of table */

/* r1 contains the number of elements > 0 */

/* r0 return 0 if not sorted 1 if sorted */

isSorted:

push {r2-r4,lr} @ save registers

mov r2,#0

ldr r4,[r0,r2,lsl #2]

1:

add r2,#1

cmp r2,r1

movge r0,#1

bge 100f

ldr r3,[r0,r2, lsl #2]

cmp r3,r4

movlt r0,#0

blt 100f

mov r4,r3

b 1b

100:

pop {r2-r4,lr}

bx lr @ return

/******************************************************************/

/* patience sort */

/******************************************************************/

/* r0 contains the address of table */

/* r1 contains first start index

/* r2 contains the number of elements */

patienceSort:

push {r1-r9,lr} @ save registers

lsl r9,r2,#1 @ compute total size of piles (2 list pointer by pile )

lsl r10,r9,#2 @ 4 bytes by number

sub sp,sp,r10 @ reserve place to stack

mov fp,sp @ frame pointer = stack

mov r3,#0 @ index

mov r4,#0

1:

str r4,[fp,r3,lsl #2] @ init piles area

add r3,r3,#1 @ increment index

cmp r3,r9

blt 1b

mov r3,#0 @ index value

mov r4,#0 @ counter first pile

mov r8,r0 @ save table address

2:

ldr r1,[r8,r3,lsl #2] @ load value

add r0,fp,r4,lsl #3 @ pile address

bl isEmpty

cmp r0,#0 @ pile empty ?

bne 3f

add r0,fp,r4,lsl #3 @ pile address

bl insertHead @ insert value r1

b 5f

3:

add r0,fp,r4,lsl #3 @ pile address

ldr r5,[r0,#dllist_head]

ldr r5,[r5,#NDlist_value] @ load first list value

cmp r1,r5 @ compare value and last value on the pile

blt 4f

add r0,fp,r4,lsl #3 @ pile address

bl insertHead @ insert value r1

b 5f

4: @ value is smaller créate a new pile

add r4,r4,#1

add r0,fp,r4,lsl #3 @ pile address

bl insertHead @ insert value r1

5:

add r3,r3,#1 @ increment index value

cmp r3,r2 @ end

blt 2b @ and loop

/* step 2 */

mov r6,#0 @ index value table

6:

mov r3,#0 @ index pile

mov r5,# 1<<30 @ min

7: @ search minimum

add r0,fp,r3,lsl #3

bl isEmpty

cmp r0,#0

beq 8f

add r0,fp,r3,lsl #3

bl searchMinList

cmp r0,r5 @ compare min global

movlt r5,r0 @ smaller -> store new min

movlt r7,r1 @ and pointer to min

addlt r9,fp,r3,lsl #3 @ and head list

8:

add r3,r3,#1 @ next pile

cmp r3,r4 @ end ?

ble 7b

str r5,[r8,r6,lsl #2] @ store min to table value

mov r0,r9 @ and suppress the value in the pile

mov r1,r7

bl suppressNode

add r6,r6,#1 @ increment index value

cmp r6,r2 @ end ?

blt 6b

add sp,sp,r10 @ stack alignement

100:

pop {r1-r9,lr}

bx lr @ return

/******************************************************************/

/* Display table elements */

/******************************************************************/

/* r0 contains the address of table */

displayTable:

push {r0-r3,lr} @ save registers

mov r2,r0 @ table address

mov r3,#0

1: @ loop display table

ldr r0,[r2,r3,lsl #2]

ldr r1,iAdrsZoneConv @

bl conversion10S @ décimal conversion

ldr r0,iAdrsMessResult

ldr r1,iAdrsZoneConv @ insert conversion

bl strInsertAtCharInc

bl affichageMess @ display message

add r3,#1

cmp r3,#NBELEMENTS - 1

ble 1b

ldr r0,iAdrszCarriageReturn

bl affichageMess

mov r0,r2

100:

pop {r0-r3,lr}

bx lr

iAdrsZoneConv: .int sZoneConv

/******************************************************************/

/* list is empty ? */

/******************************************************************/

/* r0 contains the address of the list structure */

/* r0 return 0 if empty else return 1 */

isEmpty:

ldr r0,[r0,#dllist_head]

cmp r0,#0

movne r0,#1

bx lr @ return

/******************************************************************/

/* insert value at list head */

/******************************************************************/

/* r0 contains the address of the list structure */

/* r1 contains value */

insertHead:

push {r1-r4,lr} @ save registers

mov r4,r0 @ save address

mov r0,r1 @ value

bl createNode

cmp r0,#-1 @ allocation error ?

beq 100f

ldr r2,[r4,#dllist_head] @ load address first node

str r2,[r0,#NDlist_next] @ store in next pointer on new node

mov r1,#0

str r1,[r0,#NDlist_prev] @ store zero in previous pointer on new node

str r0,[r4,#dllist_head] @ store address new node in address head list

cmp r2,#0 @ address first node is null ?

strne r0,[r2,#NDlist_prev] @ no store adresse new node in previous pointer

streq r0,[r4,#dllist_tail] @ else store new node in tail address

100:

pop {r1-r4,lr} @ restaur registers

bx lr @ return

/******************************************************************/

/* search value minimum */

/******************************************************************/

/* r0 contains the address of the list structure */

/* r0 return min */

/* r1 return address of node */

searchMinList:

push {r2,r3,lr} @ save registers

ldr r0,[r0,#dllist_head] @ load first node

mov r3,#1<<30

mov r1,#0

1:

cmp r0,#0 @ null -> end

moveq r0,r3

beq 100f

ldr r2,[r0,#NDlist_value] @ load node value

cmp r2,r3 @ min ?

movlt r3,r2 @ value -> min

movlt r1,r0 @ store pointer

ldr r0,[r0,#NDlist_next] @ load addresse next node

b 1b @ and loop

100:

pop {r2,r3,lr} @ restaur registers

bx lr @ return

/******************************************************************/

/* suppress node */

/******************************************************************/

/* r0 contains the address of the list structure */

/* r1 contains the address to node to suppress */

/* r0 return address of node or -1 if not found */

suppressNode:

push {r2,r3,lr} @ save registers

ldr r2,[r1,#NDlist_next] @ load addresse next node

ldr r3,[r1,#NDlist_prev] @ load addresse prev node

cmp r3,#0

strne r2,[r3,#NDlist_next]

streq r3,[r0,#NDlist_next]

cmp r2,#0

strne r3,[r2,#NDlist_prev]

streq r2,[r0,#NDlist_prev]

100:

pop {r2,r3,lr} @ restaur registers

bx lr @ return

/******************************************************************/

/* Create new node */

/******************************************************************/

/* r0 contains the value */

/* r0 return node address or -1 if allocation error*/

createNode:

push {r1-r7,lr} @ save registers

mov r4,r0 @ save value

@ allocation place on the heap

mov r0,#0 @ allocation place heap

mov r7,#0x2D @ call system 'brk'

svc #0

mov r5,r0 @ save address heap for output string

add r0,#NDlist_fin @ reservation place one element

mov r7,#0x2D @ call system 'brk'

svc #0

cmp r0,#-1 @ allocation error

beq 100f

mov r0,r5

str r4,[r0,#NDlist_value] @ store value

mov r2,#0

str r2,[r0,#NDlist_next] @ store zero to pointer next

str r2,[r0,#NDlist_prev] @ store zero to pointer previous

100:

pop {r1-r7,lr} @ restaur registers

bx lr @ return

/***************************************************/

/* ROUTINES INCLUDE */

/***************************************************/

.include "../affichage.inc"

</lang>