Anonymous user
Sorting algorithms/Counting sort: Difference between revisions
add task to arm assembly raspberry pi
m (added Category:Sorting) |
(add task to arm assembly raspberry pi) |
||
Line 197:
0 1 2 3 3 4 4 5 6 7 8 9 9 10 11 12 15 18 18 19 21 21 22 27 33 35 36 38 38 38 38 39 40 40 41 43 44 53 54 55 57 57 58 59 59 60 60 60 60 61 62 64 65 66 67 68 70 71 78 79 82 83 84 84 87 87 88 88 88 89 89 92 93 93 97 98 99 99 100 107 109 114 115 115 118 122 126 127 127 129 129 130 131 133 134 136 136 137 139 139
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<lang ARM Assembly>
/* ARM assembly Raspberry PI */
/* program countSort.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"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
#Caution : number stritcly positive and not too big
#TableNumber: .int 1,3,6,2,5,9,10,8,5,7 @ for test 2 sames values
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,#NBELEMENTS @ number of élements
bl searchMinMax @ r1=min r2=max
mov r3,#NBELEMENTS @ number of élements
bl countSort
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 2f
ldr r0,iAdrszMessSortNok @ no !! error sort
bl affichageMess
b 100f
2: @ 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 éléments number */
/* r0 return address r1 return min r2 return max */
searchMinMax:
push {r3-r5,lr} @ save registers
mov r3,r1 @ save size
mov r1,#1<<30 @ min
mov r2,#0 @ max
mov r4,#0 @ index
1:
ldr r5,[r0,r4, lsl #2] @ load value
cmp r5,r1 @ if < min
movlt r1,r5
cmp r5,r2 @ if > max
movgt r2,r5
add r4,r4,#1 @ increment index
cmp r4,r3 @ end ?
blt 1b @ no -> loop
100:
pop {r3-r5,lr}
bx lr @ return
/******************************************************************/
/* 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
/******************************************************************/
/* count Sort */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the minimum */
/* r2 contains the maximun */
/* r3 contains elements number */
/* caution : the count area is in the stack. if max is very large, risk of error */
countSort:
push {r1-r9,lr} @ save registers
sub r3,r3,#1 @ compute end index
sub r5,r2,r1 @ compute max - min
add r5,r5,#1 @ + 1
lsl r9,r5,#2 @ 4 bytes by number
sub sp,sp,r9 @ reserve area on stack
mov fp,sp @ frame pointer = stack address
mov r6,#0
mov r4,#0
1: @ loop init stack area
str r6,[fp,r4, lsl #2]
add r4,r4,#1
cmp r4,r5
blt 1b
mov r4,#0 @ indice
2: @ start loop 2
ldr r5,[r0,r4,lsl #2] @ load value A[j]
sub r5,r5,r1 @ - min
ldr r6,[fp,r5,lsl #2] @ load count of value
add r6,r6,#1 @ increment counter
str r6,[fp,r5,lsl #2] @ and store
add r4,#1 @ increment indice
cmp r4,r3 @ end ?
ble 2b @ no -> loop 2
mov r7,#0 @ z
mov r4,r1 @ indice = min
//bl displayTable
3: @ loop 3
sub r6,r4,r1 @ compute index - min
ldr r5,[fp,r6,lsl #2] @ load count
4: @ loop 4
cmp r5,#0 @ cont <> zero
beq 5f
str r4,[r0,r7,lsl #2] @ store value
add r7,r7,#1 @ increment z
sub r5,r5,#1 @ decrement count
b 4b
5:
add r4,r4,#1 @ decrement indice
cmp r4,r2 @ max ?
ble 3b @ no -> loop 3
add sp,sp,r9 @ 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
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
</lang>
=={{header|AutoHotkey}}==
contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276465.html#276465 forum]
| |||