Home
Syllabus
Readings
Assignments
Tests
Due: 5:00pm, Friday, October 28. Value: 30 pts. Submit both programs to Sauron.
The hailstone sequence starts with an arbitrary integer k. If n represents a number in the sequence, we can compute the next number by testing whether n is even: If it is, the next number is n ÷ 2; and if n is odd, the next number is 3n + 1. For example, the sequence starting from 3 is as follows:
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → 4 → 2 → 1 …
As you see, this sequence eventually starts to loop between 1, 2, and 4. In 1937, mathematician Lothar Collatz conjectured that no matter what integer starts the sequence, its hailstone sequence will eventually reach this loop between 1, 2, and 4. The conjecture remains unproven.
Your assignment is to write two ARM assembly language
programs dealing with hailstone sequences, as described below.
You should use aas to test
your programs; the section Using aas
provides some examples of using this program.
Both programs you write should include and use the io.s library of subroutines,
described in The io.s library.
Commenting programs is particularly important when you're dealing with assembly language. The io.s library illustrates good commenting style.
The program, named seq.s, reads an integer from the user, displays the hailstone sequence starting from that integer until it reaches 1, and then halts in a tight loop. For example, if the user enters 13, the output would be as follows.
13 40 20 10 5 16 8 4 2 1
There's one feature of ARM's assembly language that we didn't
really discuss much in class but which is useful for doing this:
The final argument to any of the basic arithmetic instruction may
include a register plus an amount by which to shift its value before
incorporating it into the computation. Thus, the instruction
MOV R0, R1, ASR #4 takes the current value of R1, performs
an arithmetic right-shift by four spots, and places the result into
R0; register R1 remains unchanged. Permitted shift
operations include ASR (arithmetic shift right), LSL
(logical shift left), LSR (logical shift right), and ROR (rotate right).
The program, named records.s, takes no input. It goes through each starting integer and sees how many steps it takes to reach the number 1. Each time your program reaches a larger number of steps than it has seen before, it should display the starting number and the step count. Below are the first 10 lines of output of this program.
1 0 2 1 3 7 6 8 7 16 9 19 18 20 25 23 27 111 54 112
This output indicates that 1 takes 0 steps, 2 takes longer with 1 step, 3 takes longer with 7 steps. The first number with more than 7 steps is 6, which takes 8 steps. The first number with more than 8 steps is 7, which takes 16 steps. The first number with more than 16 steps is 9, which takes 19 steps. The first number with more than 19 steps is 18, which takes 20 steps. And so on.
Below is a list of the subroutines found in io.s.
| ttyStart | Initializes the terminal. All other io.s subroutines will not work unless this is called first. | (Changes R0, R3.) |
| getInt | Reads digits from the user until finding a non-digit character, interprets the digits as a base-10 number, which it places into R0. The first non-digit character read is consumed. | (Changes R0, R1, R2, R3.) |
| getChar | Reads a single character from the user and places it into R0. | (Changes R0, R3.) |
| printStr | Displays all characters in a NUL-terminated array whose first address is found in R0. | (Changes R0, R1, R2, R3, R12.) |
| printInt | Displays base-10 representation of integer found in R0. | (Changes R0, R1, R2, R3, R12.) |
| printChar | Displays character whose ASCII code is in the lower byte of R0. | (Changes R0, R1, R3.) |
Below are two program illustrating how to use io.s. The first just echoes everything the user types; the second repeatedly reads integers from the user and displays their squares.
BL ttyStart
again BL getChar ; load one character into R0
BL printChar ; and echo it
B again
INCLUDE "io.s"BL ttyStart
again BL getInt ; read an integer into R0,
MUL R0, R0, R0 ; square it
BL printInt ; and show integer's square
MOV R0, #'\n' ; followed by a newline
BL printChar
B again
INCLUDE "io.s"
The program aas includes an ARM assembler and simulator. It is already installed on the laboratory computers, so you have only to execute the aas command in the terminal window to start it. If you want to use it on other computers, you can download it from the aas home page.
The below transcript illustrates using aas. It uses the squares.s file, which we're imagining contains the second program given above, for displaying the square of each number the user types. For this to work, you would need to execute aas from within a directory that contains io.s and squares.s.
In the transcript, after starting aas, we first tell it to assemble the code found in squares.s and load the resulting machine code into the simulated computer's memory. Then we tell it that when the program executes, it should send a line containing the digit 5 to the program, and then it should send a line containing the digits 1,4,5 to the program. We then start the simulated computer running using the step command, where we tell the computer to execute one million instructions, which is enough for the simulated computer to read and process each of the two numbers. The program would spend most of the last one million instructions simply waiting for further input. But we then exit aas.
linux$ aas Welcome to aas 0.0.5 (http://www.toves.org/aas/). Type 'help' to list commands. (c) 2008, Carl Burch. For copyright information, enter 'print license'. (aas) load squares.s (aas) input input: 5 (aas) input input: 145 (aas) step 1m 25 21025 (aas) quit
Several additional commands are available within
aas that are helpful for debugging a program. In the following
transcript, we set a breakpoint so that the computer stops just
before executing line 3 of squares.s, which contains the
MUL instruction.
After executing the program so that it reaches this point, we
display the value of R0, then execute just a single
instruction (MUL), and then we display R0
again.
linux$ aas Welcome to aas 0.0.5 (http://www.toves.org/aas/). Type 'help' to list commands. (c) 2008, Carl Burch. For copyright information, enter 'print license'. (aas) load squares.s (aas) list 0 10 0x0000 0xeb000005 line 1: BL ttyStart 0x0004 0xeb000009 line 2: BL getInt 0x0008 0xe0000090 line 3: MUL R0, R0, R0 0x000c 0xeb000020 line 4: BL printInt (aas) break 3 breakpoint added at 0x8 (aas) input input: 25 (aas) step 1m execution reached breakpoint 0x8 after 49 steps; stopped (aas) print r0 R0 0x00000019 [25] (aas) step (aas) print r0 R0 0x00000271 [625] (aas) step 1m 625 (aas) quit