How to resolve the algorithm 100 doors step by step in the ARM Assembly programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm 100 doors step by step in the ARM Assembly programming language
Table of Contents
Problem Statement
There are 100 doors in a row that are all initially closed.
You make 100 passes by the doors.
The first time through, visit every door and toggle the door (if the door is closed, open it; if it is open, close it).
The second time, only visit every 2nd door (door #2, #4, #6, ...), and toggle it.
The third time, visit every 3rd door (door #3, #6, #9, ...), etc, until you only visit the 100th door.
Answer the question: what state are the doors in after the last pass? Which are open, which are closed?
Alternate:
As noted in this page's discussion page, the only doors that remain open are those whose numbers are perfect squares.
Opening only those doors is an optimization that may also be expressed;
however, as should be obvious, this defeats the intent of comparing implementations across programming languages.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm 100 doors step by step in the ARM Assembly programming language
Source code in the arm programming language
/* ARM assembly Raspberry PI */
/* program 100doors.s */
/************************************/
/* Constantes */
/************************************/
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
.equ NBDOORS, 100
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessResult: .ascii "The door "
sMessValeur: .fill 11, 1, ' ' @ size => 11
.asciz "is open.\n"
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
stTableDoors: .skip 4 * NBDOORS
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
push {fp,lr} @ saves 2 registers
@ display first line
ldr r3,iAdrstTableDoors @ table address
mov r5,#1
1:
mov r4,r5
2: @ begin loop
ldr r2,[r3,r4,lsl #2] @ read doors index r4
cmp r2,#0
moveq r2,#1 @ if r2 = 0 1 -> r2
movne r2,#0 @ if r2 = 1 0 -> r2
str r2,[r3,r4,lsl #2] @ store value of doors
add r4,r5 @ increment r4 with r5 value
cmp r4,#NBDOORS @ number of doors ?
ble 2b @ no -> loop
add r5,#1 @ increment the increment !!
cmp r5,#NBDOORS @ number of doors ?
ble 1b @ no -> loop
@ loop display state doors
mov r4,#0
3:
ldr r2,[r3,r4,lsl #2] @ read state doors r4 index
cmp r2,#0
beq 4f
mov r0,r4 @ open -> display message
ldr r1,iAdrsMessValeur @ display value index
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
4:
add r4,#1
cmp r4,#NBDOORS
ble 3b @ loop
100: @ standard end of the program
mov r0, #0 @ return code
pop {fp,lr} @restaur 2 registers
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrsMessValeur: .int sMessValeur
iAdrstTableDoors: .int stTableDoors
iAdrsMessResult: .int sMessResult
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal unsigned */
/******************************************************************/
/* r0 contains value and r1 address area */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
// and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
// and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area
add r4,#1 @ next position
cmp r4,#LGZONECAL
ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower @ for Raspberry pi 3
//movt r3,#0xCCCC @ r3 <- magic_number upper @ for Raspberry pi 3
ldr r3,iMagicNumber @ for Raspberry pi 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
/*********************************************/
/* optimized version */
/*********************************************/
/* ARM assembly Raspberry PI */
/* program 100doors.s */
/************************************/
/* Constantes */
/************************************/
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
.equ NBDOORS, 100
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessResult: .ascii "The door "
sMessValeur: .fill 11, 1, ' ' @ size => 11
.asciz "is open.\n"
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
push {fp,lr} @ saves 2 registers
@ display first line
mov r5,#3 @ start value of increment
mov r4,#1 @ start doors
@ loop display state doors
1:
mov r0,r4 @ open -> display message
ldr r1,iAdrsMessValeur @ display value index
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
add r4,r5 @ add increment
add r5,#2 @ new increment
cmp r4,#NBDOORS
ble 1b @ loop
100: @ standard end of the program
mov r0, #0 @ return code
pop {fp,lr} @ restaur 2 registers
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrsMessValeur: .int sMessValeur
iAdrsMessResult: .int sMessResult
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal unsigned */
/******************************************************************/
/* r0 contains value and r1 address area */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @ unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
@ and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
@ and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area
add r4,#1 @ next position
cmp r4,#LGZONECAL
ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower @ for raspberry 3
//movt r3,#0xCCCC @ r3 <- magic_number upper @ for raspberry 3
ldr r3,iMagicNumber @ for raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
You may also check:How to resolve the algorithm Dragon curve step by step in the EasyLang programming language
You may also check:How to resolve the algorithm P-Adic numbers, basic step by step in the Go programming language
You may also check:How to resolve the algorithm The Name Game step by step in the REXX programming language
You may also check:How to resolve the algorithm Find limit of recursion step by step in the Scheme programming language
You may also check:How to resolve the algorithm Combinations and permutations step by step in the ALGOL 68 programming language