/* ARM assembly Raspberry PI  */
/*  program quickSelection.s   */
/* look pseudo code in wikipedia  quickselect */

/************************************/
/* Constantes                       */
/************************************/
/* for constantes see task include a file in arm assembly */
.include "../constantes.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessResultIndex:        .asciz "index  : "
szMessResultValue:        .asciz " value  : "
szCarriageReturn:  .asciz "\n"

.align 4
TableNumber:	     .int   9, 8, 7, 6, 5, 0, 1, 2, 3, 4
.equ NBELEMENTS,      (. - TableNumber) / 4
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:             .skip 24
sZoneConv1:             .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main
main:                                    @ entry of program
    mov r5,#0
1:
    ldr r0,iAdrTableNumber               @ address number table
    mov r1,#0                            @ index first item
    mov r2,#NBELEMENTS -1                @ index last item
    mov r3,r5                            @ search index
    bl select                            @ call selection
    ldr r1,iAdrsZoneConv
    bl conversion10                      @ convert result to decimal
    mov r0,r5
    ldr r1,iAdrsZoneConv1
    bl conversion10                      @ convert index to decimal
    mov r0,#5                            @ and display result
    ldr r1,iAdrszMessResultIndex
    ldr r2,iAdrsZoneConv1
    ldr r3,iAdrszMessResultValue
    ldr r4,iAdrsZoneConv
    push {r4}
    ldr r4,iAdrszCarriageReturn
    push {r4}
    bl displayStrings
    add sp,sp,#8                         @ stack alignement (2 push)
    add r5,r5,#1
    cmp r5,#NBELEMENTS
    blt 1b

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
iAdrTableNumber:          .int TableNumber
iAdrsZoneConv:            .int sZoneConv
iAdrsZoneConv1:           .int sZoneConv1
iAdrszMessResultIndex:    .int szMessResultIndex
iAdrszMessResultValue:    .int szMessResultValue

/***************************************************/
/*   Appel récursif selection           */
/***************************************************/
/* r0 contains the address of table */
/* r1 contains index of first item  */
/* r2 contains index of last item   */
/* r3 contains search index */
select:
    push {r1-r6,lr}                @ save registers
    mov r6,r3                      @ save search index
    cmp r1,r2                      @ first = last ?
    ldreq r0,[r0,r1,lsl #2]        @ return value of first index
    beq 100f                       @ yes -> end
    add r3,r1,r2
    lsr r3,r3,#1                   @ compute median pivot
    mov r4,r0                      @ save r0
    mov r5,r2                      @ save r2
    bl partition                   @ cutting into 2 parts
    cmp r6,r0                      @ pivot is ok ?
    ldreq r0,[r4,r0,lsl #2]        @ return value
    beq 100f
    bgt 1f
    sub r2,r0,#1                   @ index partition  - 1
    mov r0,r4                      @ array address
    mov r3,r6                      @ search index
    bl select                      @ select lower part
    b 100f
1:
    add r1,r0,#1                   @ index begin = index partition + 1
    mov r0,r4                      @ array address
    mov r2,r5                      @ last item
    mov r3,r6                      @ search index
    bl select                      @ select higter part
 100:                              @ end function
    pop {r1-r6,pc}                 @ restaur  register
/******************************************************************/
/*      Partition table elements                                */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains index of first item  */
/* r2 contains index of last item   */
/* r3 contains index of pivot */
partition:
    push {r1-r6,lr}                                    @ save registers
    ldr r4,[r0,r3,lsl #2]                              @ load value of pivot
    ldr r5,[r0,r2,lsl #2]                              @ load value last index
    str r5,[r0,r3,lsl #2]                              @ swap value of pivot
    str r4,[r0,r2,lsl #2]                              @ and value last index
    mov r3,r1                                          @ init with first index
1:                                                     @ begin loop
    ldr r6,[r0,r3,lsl #2]                              @ load value
    cmp r6,r4                                          @ compare loop value and pivot value
    ldrlt r5,[r0,r1,lsl #2]                            @ if < swap value table
    strlt r6,[r0,r1,lsl #2]
    strlt r5,[r0,r3,lsl #2]
    addlt r1,#1                                        @ and increment index 1
    add r3,#1                                          @ increment index 2
    cmp r3,r2                                          @ end ?
    blt 1b                                             @ no loop
    ldr r5,[r0,r1,lsl #2]                              @ swap value
    str r4,[r0,r1,lsl #2]
    str r5,[r0,r2,lsl #2]
    mov r0,r1                                          @ return index partition
100:
    pop {r1-r6,pc}

/***************************************************/
/*   display multi strings                    */
/***************************************************/
/* r0  contains number strings address */
/* r1 address string1 */
/* r2 address string2 */
/* r3 address string3 */
/* other address on the stack */
/* thinck to add  number other address * 4 to add to the stack */
displayStrings:            @ INFO:  displayStrings
    push {r1-r4,fp,lr}     @ save des registres
    add fp,sp,#24          @ save paraméters address (6 registers saved * 4 bytes)
    mov r4,r0              @ save strings number
    cmp r4,#0              @ 0 string -> end
    ble 100f
    mov r0,r1              @ string 1
    bl affichageMess
    cmp r4,#1              @ number > 1
    ble 100f
    mov r0,r2
    bl affichageMess
    cmp r4,#2
    ble 100f
    mov r0,r3
    bl affichageMess
    cmp r4,#3
    ble 100f
    mov r3,#3
    sub r2,r4,#4
1:                         @ loop extract address string on stack
    ldr r0,[fp,r2,lsl #2]
    bl affichageMess
    subs r2,#1
    bge 1b
100:
    pop {r1-r4,fp,pc}
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../affichage.inc"