CSE/EEE 230 Computer Organization and Assembly Language.

check the attachment for compete descriptions and the ZIP file as well ;  

This assignment includes exercises covering assembly language procedures, discussed in Ch. 2, and the IEEE 754 floating
point standard, which is discussed in the Ch. 3 lecture notes. First, read §2 which discusses how to define and use oneand
two-dimensional arrays (1D and 2D arrays) as parameters and local variables in function. Then complete Ch. 2 Exercises
1 and 2, which are assembly language functions involving arrays, if statements, and loops. Next, read §6 and §7 on
IEEE 754 rounding

CSE/EEE 230 Computer Organization and Assembly Language Homework 4 :: 50 pts 1 Instructions
This assignment includes exercises covering assembly language procedures, discussed in Ch. 2, and the IEEE 754 floating
point standard, which is discussed in the Ch. 3 lecture notes. First, read §2 which discusses how to define and use oneand two-dimensional arrays (1D and 2D arrays) as parameters and local variables in function. Then complete Ch. 2 Exer cises 1 and 2, which are assembly language functions involving arrays, if statements, and loops. Next, read §6 and §7 on
IEEE 754 rounding modes and converting numbers among different bases using Wolfram Alpha. Finally, complete Ch. 3
Exercises 3–5 in §5.
You may work in pairs with a partner on this assignment if you wish or you may work alone. If you work with a partner,
only submit one PDF file with both of your names in the document; you will each earn the same number of points. Your
PDF file must be uploaded to Blackboard by the assignment deadline. Section 8 describes what to submit and by when. 2 1D Arrays as Parameters and Local Variables
We discussed earlier how to define and allocate a global 1D array variable in the data section. What about defining array
variables as local variables and passing them as function arguments?
First, to define an array local variable in a function, the array must be allocated in the stack frame of the function. For
example,
void main()
{
char name[255];
...
print_string(name);
} To allocate name requires main() to allocate 255 bytes in its stack frame for name. However, to maintain word-alignment,
the size of data allocated in the stack frame should be a power of 4 (or divisible by 4) and 255 is not a power of 4, but
256 is. Consequently, main() will allocate name using 256 bytes, with the address of name being 0($sp),
main:
addi
...
move
jal
...
addi
addi
syscall $sp, $sp, -256 # Allocate 256 bytes for 255-char array name $a0, $sp
print_string # Place the address of name ($sp) into $a0 prior to the funct call
# Call print_string() with $a0 containing the address of name $sp, $sp, 256
$v0, $zero, SYS_EXIT # Deallocate stack frame
# $v0 = SysExit service code
# SysExit() Note that in C, the name of an array variable, i.e., name, is equivalent to the address of the variable in memory. Notice
the move instruction in main(): to pass name as the argument to print_string requires us to load the address of name
into the $a0 register, and 0($sp) is the address of name. In C, when an array variable is passed as a function argument,
we do not pass a copy of the entire array; rather, to save both time and memory, we simply pass the address of the array.
Since addresses are 4-bytes in our MIPS32 system, we only need to send 4 bytes to the callee when passing an array that
consists of one million elements!
See print_string() below. Notice in main() that the array of characters is called name while in print_string(), the array is
called string. In high-level programming languages like C and Java, the names of the arguments in the function call do
not need to be the same as the names of the parameters in the function header. Note, also that name and string both
refer to the same 1D array of characters allocated in main's stack frame. That is, if we were to modify the contents of
string in print_string() we would really be modifying the block of characters of name in main's stack frame, which means
upon returning to main(), the contents of name will have been changed. This may or may not be desirable. (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 1 CSE/EEE 230 Computer Organization and Assembly Language Homework 4 :: 50 pts void print_string(char string)
{
for (int i = 0; string[i] != '\0'; ++i) { -- Loop over the chars of string at indices 0, 1, 2, ...
SysPrintChar(string[i]);
-- stop looping and printing when the null char is reached
}
} Note that on entry to print_string(), string will contain in $a0 the address of name allocated in main's stack frame.
What we have in string is what C programmers call a pointer, making string a pointer variable. A pointer variable is
just like an integer variable, except the integer stored in a pointer variable is always the memory address of where
some data are located. Since string contains the address of the character array name found in main's stack frame, we can
mentally picture string pointing to name. Let us complete the code for print_string() so you will see how to use string.
First, rewrite print_string() changing the for loop into a while loop,
void print_string(char string)
{
int i = 0;
while (string[i] != '\0') {
SysPrintChar(string[i])
++i;
}
} Next, translate the code using a while loop into code using an if statement and goto,
void print_string(char string)
{
int i = 0;
begin_loop:
if (string[i] == '\0') goto end_loop;
SysPrintChar(string[i]);
++i;
goto begin_loop;
end_loop:
} // i is the index in string of the char to be printed
//
//
//
//
// Drop out of the loop when the null char is reached
Print the char at string[i]
Update i to be the index of the next char in string
Continue looping...
We come here when the null char is reached Finally, this code maps directly onto the assembly language code. print_string() is a leaf procedure so we do not need to
save $ra (syscalls are not function calls, they do not change $ra). Note that we do need to save $a0 in the stack frame
because it contains parameter string and when performing the syscall, we need to place the ASCII value of the character to be printed into $a0. I am also intentionally not optimizing this code so you can better see how local variables are
allocated and accessed.
print_string:
# int i = 0;
addi
$sp, $sp, -8
sw
$a0, 4($sp)
sw
$zero, 0($sp) # Allocate 2 words in stack frame: i at 0($sp), $a0 at 4($sp)
# Save $a0 (param string) in stack frame
# Initialize i in stack frame to 0 # if (string[i] == '\0') goto end_loop
lw
$t0, 0($s0)
lw
$t1, 4($sp)
add
$t0, $t1, $t0
lbu
$a0, 0($t0)
beq
$a0, $zero, end_loop #
#
#
#
# $t0 = i
$t1 = string
$t0 = string + i = &string[i]
$a0[7:0] = string[i] (note: lbu loads a byte/char)
if (string[i] == '\0') goto end_loop (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 2 CSE/EEE 230 Computer Organization and Assembly Language # SysPrintChar(string[i])
addi
$v0, $zero, SYS_PRINT_CHAR
syscall # $v0 = SysPrintChar service code
# SysPrintChar(string[i]) # ++i;
lw
addi
sw # $t0 = i
# $t0 = i + 1
# ++i $t0, 0($sp)
$t0, $t0, 1
$t0, 0($sp) # goto begin_loop
j
begin_loop # Continue looping end_loop:
addi
jr # Deallocate stack frame
# Return $sp, $sp, 8
$ra Homework 4 :: 50 pts It is important that you study this code, especially the instructions in print_string() that involve the local variable i and
parameter string. Note in particular how the address of string[index] is computed in the add $t0, $t1, $t0 instruction.
Since string is the address of name in main's stack frame, string + i is the address of string[i] which is really the address
of name[i].
One final note on 1D array addressing. The example used an array of characters, where the size of each array element was
1, since a character in our MIPS system consumes 1 byte of memory. If we are working with an array of integers, where
each int occupies 4 bytes of memory, then the general formula for calculating the address of a 1D array element is: &a[i]
= a + i · sizeof(type), where type is the data type of each element of the array and the C sizeof operator evaluates to
the number of bytes allocated for type. For a character array, sizeof(char) is 1, but for an integer array, sizeof(int) is 4.
Hence, if a is an array of ints, to find the address of the element at index 5, the formula is: &a[5] = a + 5 · 4 = a + 20,
and in general, it would be &a[i] = a + 4i. 3 2D Arrays as Parameters and Local Variables
In programming, we mentally picture a two-dimensional array as a table consisting of rows and columns of elements.
However, in a computer system, the memory address space is one-dimensional (or linear), i.e., memory can be pictured as
just a very big 1D array. So how do we store a 2D data structure in 1D space? There are two common methods. The one
described here is the most common method, as most popular programming languages do it this way.
The idea is to recognize that each row of a 2D array (table) is simply a 1D array of elements, e.g., consider this 2D array:
int a[2, 3], consisting of two rows and three columns. The method stores the elements for row 0 in contiguous memory
locations, then it stores the elements for row 1 in memory following the elements of row 0, for example,
+---------+
| a[1][2] |
+---------+
| a[1][1] |
+---------+
| a[1][0] |
+---------+
| a[0][2] |
+---------+
| a[0][1] |
+---------+
| a[0][0] |
+---------+ 0x7FFF_EA14
0x7FFF_EA10
0x7FFF_EA0C
0x7FFF_EA08
0x7FFF_EA04
0x7FFF_EA00 ---+
|
|
|
|
|
---+
|
|
|
|
= a |
---+ Row 1 Row 0 Storing the array elements by rows in this manner is referred to as row-major order. The other method is to store all of
the elements for column 0 first, then the elements for column 1, then the elements for column 2, and so on. That method
is called column-major order. The majority of programming languages I know of use row-major order. The only language I know that uses column-major order is FORTRAN.
(c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 3 CSE/EEE 230 Computer Organization and Assembly Language Homework 4 :: 50 pts Note that the name of the array is a and the arbitrarily-chosen address of a is 0x7FFF_EA00 (remember, the name of an
array variable is equivalent to the address of the array). In a manner similar to calculating the address of a 1D array ele ment, to calculate the address of a 2D array element, we need to know three things: the address of the array, the size in
bytes of each element of the array, and additionally, we must know the number of columns in the 2D array (call this value
num_cols). Then, the general formula is: &a[r][c] = a + r · num_cols · sizeof(type) + c · sizeof(type) which can be
simplified to &a[r][c] = a + (r · num_cols + c) · sizeof(type).
For example, try this out: what is the address of a[1][1]? a is 0x7FFF_EA00, r = 1, c = 1, sizeof(int) = 4, and num_
cols = 3, so we have &a[1][1] = a + (1 · 3 + 1) · 4 = 0x7FFF_EA00 + (4) · 4 = 0x7FFF_EA00 + 0x10 = 0x7FFF_EA10. 4 Chapter 2 Exercises
1. (8 pts) MIPS32 Assembly Language Programming - strlen() Function (modify h4-1.s). In §2.8 of the Ch.
2 lecture notes, we discussed how to write and use assembly language functions. We have also previously discussed
how C-strings are stored in memory as a one-dimensional array of characters with a null character '\0' (with ASCII
value 0) following the last character of the string. For this exercise, you will write the assembly language instructions
to implement the function int strlen(char string) which computes and returns the length of the C-string
string. Note, the length of a C-string is the number of characters in the string, excluding the null character, e.g., if
string is "Wilma" then what is stored in six consecutive bytes of memory for string is 87, 105, 108, 110, 103, 0, which
are the decimal ASCII values for 'W', 'i', 'l', 'm', 'a', and '\0', respectively. Therefore, strlen() must return 5. Here is
the pseudocode for strlen(),
function strlen(char string)
local int index ← 0
while string[index] =≠ '\0' do -- walk thru string starting at the beginning looking for the null char
++index
end while
return index -- when we drop out of the while loop, index is the index of the null char within string
end function strlen -- index also happens to be a count of the number of non-null chars that were encountered
Complete the following exercises:
a. First, rewrite this function replacing the while loop with equivalent code using an if statement and a goto. Insert the neatly-typed revised function into your solution document.
b. Translate the code using the if statement and goto into MIPS assembly language. Insert the assembly language
code into h4-1.s following the definition of main(). Test your function by running main() with several test cases.
Miscellaneous notes, hints, and requirements:
1. 2. 3. Study the assembly language source code files listed in the course notes and posted on the course website. Format
your code in a similar manner, i.e., an assembly language line containing an instruction consists of four columns
of mostly-optional stuff: column 1 is aligned with the left margin and is reserved for an optional label; column 2
is indented from column 1 by around 4-8 spaces and is reserved for instruction mnemonics; column 3 is indented
from column 2 and reserved for optional operands; column four is indented from column 3 and is reserved for
optional comments. How many spaces or tabs you indent is up to you, the important thing is to line things up in
columns and be consistent.
See how I commented main() in h4-1.s. In strlen(), write a meaningful comment in column 4 of each line of code
containing an instruction. This may seem like busy work, but it can be very helpful when your code does not
work and you are trying to figure out why. Trust me on this one.
Note that strlen() is a leaf procedure (because it does not call other functions) and as long as there are enough
registers to store all of the local variables, a leaf procedure does not really need to create a stack frame because it
does not need save $ra or any of the $ax argument registers. However, the primary objective of this exercise is for (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 4 CSE/EEE 230 Computer Organization and Assembly Language 4. 5. Homework 4 :: 50 pts you to demonstrate that you know how to write a function that creates a stack frame, allocates local variables
within the stack frame, accesses local variables in the stack frame, and destroys the stack frame before returning.
Consequently, your solution shall create a stack frame for strlen() and shall allocate local variable index in the
stack frame at 0($sp). Whenever the code must read or write index, write the lw and sw instructions to read and
write index from/to memory, i.e., do not optimize the code by simply storing index in a register and always
accessing it from there. Study how I wrote the code for main() which is also unoptimized, e.g., on line 103 I
wrote the return value from strlen()—which is in $v0—into the stack frame word allocated for len. Then, on line
107, I wrote an instruction which loads the value of len from the stack frame into $a0. If I were optimizing the
code, I could have just written move $a0, $v0 on line 107, rather than accessing memory, but again, the primary
objective of this exercise is for you to prove to the grader that you know how to create and use a stack frame.
Because SysReadStr always writes a newline character into the string buffer following the last typed character
(well, it always does this when the size of the buffer is large enough to store the newline character), then the
smallest string we can enter would be to simply hit the Enter key when the prompt is displayed. This will cause
string to be set to "\n", for which strlen() will return 1. Using SysReadStr the way we are using it, it is impossible to type the empty string "" for testing. However, testing the empty string can be done this way: set a breakpoint in the debugger on the line containing the jal strlen instruction, (as long as you have not modified
main(), this will be line 125; in the debugger, the instruction will be at 0x0040_0028). Run the program and
when prompted for the string, just hit the Enter key. In the Data Segment view of the MARS debugger window,
click on the button (next to the green arrows) that allows us to display different regions of memory; select
current $sp from the drop-down list box. Select Hexadecimal Addresses and Hexadecimal Values. If the ASCII
check box is selected, unselect it. Look at the stack diagram for main()—found in the header comment block for
main() starting on line 84—and note that the address of string is 0x7fff_efa8. In the Data Segment view, locate
the word stored in memory at that address, and you should see 0x0000000a as the value of this word. Place the
cursor inside the GUI box for the word and double-click. Edit the value of this word to be 0x00000000 and press
Enter to save the changes. We have now changed the string stored in memory from "\n" to "". Now click the
Run button to allow strlen() to be called and you should see 0 for the output. The empty string "" has length 0.
Update the header comment block of h4-1.s with your name and email address, if you have a partner, his/her
name and email address, and your lecture time: 10:45am or 2:00pm. 2. (27 pts) MIPS32 Assembly Language Programming - write_grid() Function (modify h4-2.s). Encryption is the process of converting information from one form to another form so as to make the original informa tion
unintelligible. For example, we may wish to encrypt a plaintext message "Gunther is loose again. Release the
hounds." into the encrypted ciphertext message "Giedulnsno.t.tohhsReeeerlhaeoigausasn".
A multitude of encryption algorithms have been devised over the last couple of millennia. Some are better than
others; the strength of an encryption algorithm E is a measure of how difficult it is to decrypt a message encrypted
using E without knowing how E works or what encryption key(s) E uses. That is, if Bob uses secret encryption
algorithm E with secret key K to encrypt a plaintext message plain forming an encrypted ciphertext message cipher,
and if Alice does not know how E works or she does not know K, then if E is a strong encryption method, it will be
extremely difficult—if not impossible—for Alice to decrypt cipher so she can read plain.
Strong encryption algorithms are very complex and very difficult to design. One of the best and well-known strong
encryption algorithms is the Advanced Encryption Standard (AES) endorsed by the U.S. National Institute of
Standards and Technology (NIST) and the National Security Agency (NSA). Weak or lousy encryption algorithms,
on the other hand, are quite easy to devise. For example, I will describe a method that we will implement in MIPS
assembly language.
When the program starts, it will display a prompt requesting the user to enter the plaintext message plain, with 1 ≤
strlen(plain) ≤ 80. Next, it writes the individual characters of plain into a 2D array of characters named grid, containing NUM_ROWS = 8 rows and NUM_COLS = 10 columns.
(c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 5 CSE/EEE 230 Computer Organization and Assembly Language Homework 4 :: 50 pts For example,
Plaintext (80 or fewer chars)? Gunther is loose again. Release the hounds. When the plaintext message is entered and read using the SysReadStr system call, the trailing newline character that
is generated when the user presses the Enter key is placed in the string buffer following the final period (and follow ing that byte in memory will be the null character '\0'). Excluding the newline character, in this example, the length
of plain is 43. We write the individual characters of plain into grid in row-major order (row-major order means we
fill up an entire row r before moving to row r+1).
G
␣
i
e
d
␣
␣
␣ u
l
n
␣
s
␣
␣
␣ n
o
.
t
.
␣
␣
␣ t
o
␣
h
␣
␣
␣
␣ h
s
R
e
␣
␣
␣
␣ e
e
e
␣
␣
␣
␣
␣ r
␣
l
h
␣
␣
␣
␣ ␣
a
e
o
␣
␣
␣
␣ i
g
a
u
␣
␣
␣
␣ s
a
s
n
␣
␣
␣
␣ where ␣ represents the space character. Note that unused elements of grid are written with spaces. Next, to create the
ciphertext message cipher we traverse the elements of grid in column-major order, appending each non-space character to cipher (column-major order means we append all of the characters in an entire column c before moving to column c+1). In this example, cipher will become "Giedulnsno.t.tohhsReeeerlhaeoigausasn". Finally, the program
shall output cipher,
Plaintext (80 or fewer chars)? Gunther is loose again. Release the hounds.
Ciphertext: Giedulnsno.t.tohhsReeeerlhaeoigausasn The equivalent C-like pseudocode for the program is shown below.
-- Note: Define these constants using the .eqv directive and use the constants in the assembly language code, e.g.,
-- in at least one instruction, you will need to load the value of NUM_COLS into a register. To do this, write:
-- addi $t0, $zero, NUM_COLS rather than addi $v0, $zero, 10. Remember, the entire reason we define constants
-- is to enhance the readability of the code, and using well-named constants does that.
global constant BUF_LEN
← 84 -- Size of the array string allocated in main().
global constant SYS_RS_MAX
← 82 -- Maximum number of chars to read when calling SysReadStr.
global constant NUM_COLS
← 10 -- Number of columns in the 2D grid.
global constant NUM_ROWS
← 8 -- Number of rows in the 2D grid.
function main()
local char string[BUF_LEN], grid[NUM_ROWS][NUM_COLS] -- local vars are allocated in stack frame
SysPrintStr("Plaintext (80 or fewer chars)? "
-- Display the prompt for the plaintext message.
SysReadStr(string, SYS_RS_MAX)
-- Read the plaintext message into string.
write_grid(grid, string)
-- Write plain into grid in row-major order.
read_grid(grid, string)
-- Read ciphertext msg by traversing grid in column-major order
SysPrintStr("Ciphertext: ")
SysPrintStr(string)
-- Display the ciphertext message.
SysExit()
-- Terminate the program.
end function main (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 6 CSE/EEE 230 Computer Organization and Assembly Language Homework 4 :: 50 pts function read_grid(char grid, char cipher) -- grid is a 2D array of chars; cipher is a 1D array of chars
local int col, index ← 0, row
for col ← 0 to NUM_COLS - 1 do
-- Because the for column loop is the outer loop and the for row loop
for row ← 0 to NUM_ROWS - 1 do -- is the inner loop, we traverse grid in column-major order.
if grid[row][col] =≠ ' ' then
-- We do not append space chars to cipher.
cipher[index] ← grid[row][col] -- Append the char at grid[row][col] to cipher.
++index
-- Update index to point to the next free element in cipher.
end if
end for
end for
cipher[index] ← '\0' -- We must append the required null char following the last char of cipher
end function read_grid
function strlen(char string) -- Copy-and-paste your strlen() function of Exercise 1 into h4-2.s here.
...
end function strlen
function write_grid(grid, plain)
local int col, index ← 0, len ← strlen(plain) - 1, row -- subtract 1 from strlen() to skip newline char at the end
for row ← 0 to NUM_ROWS do
-- Because the for row loop is the outer loop and the for column loop
for col ← 0 to NUM_COLS do
-- is the inner loop, we traverse grid in row-major order.
if index < len then
-- Does index still refer to a valid char in plain?
grid[row][col] ← plain[index] -- Yes, write the char to grid.
++index
-- Update index to refer to the next char in plain.
else
grid[row][col] ← ' '
-- Else, no, we have copied all of the chars from plain into grid
end if
-- so fill remaining unused grid elements with spaces
end for
end for
end function write_grid
You do not need to write the entire program as I have provided a template in h4-2.s containing the completed code
for main() and read_grid(). You will insert the code for the strlen() function you wrote in Exercise 1 into h4-2.s so it
may be called from write_grid(), leaving write_grid() as the only function remaining to be implemented by you.
Complete the following exercises.
a. First, rewrite the pseudocode for write_grid(), replacing the for loops with equivalent code using while loops.
Insert the neatly-typed revised function into your solution document and identify it as Version 2 of write_grid().
b. Next, rewrite Version 2, replacing the while loops with equivalent code using if statements and goto's. Insert
the neatly-typed revised function into your solution document and identify it as Version 3.
c. Next, rewrite Version 3, replacing the structured if-else statement with unstructured code that uses an if
statement (not an if-else statement) and goto's. Insert the neatly-typed revised function into your solution
document and identify it as Version 4.
d. Version 4 is now in a format that maps directly onto the assembly language implementation. Translate Version 4
to MIPS assembly language by writing the instructions for write_grid() in h4-2.s. (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 7 CSE/EEE 230 Computer Organization and Assembly Language Homework 4 :: 50 pts e. Testing. To ensure your program works correctly, you must test it using several test cases. I will give you two,
but you shoul...

Attachments:

• 1494491965-cse230-f16-h04.zip