CS2461-10 Computer Architecture I Spring 2021
Project 1 02/03/2021 Due 03/02/2021
This project is to practice the machine language and assembly language programming skills. Below are two lists of topics for machine problem (MP) and assembly problem (AP). Please choose one topic from each list and develop the programs.
This is a team-work project, and at most two students are allowed to work together. After the program development and test, please write your report to summarize your work, in which please include your flowchart with the details (see examples in the chapters 5 and 6 slides), the source code, and the screen shots of your results. You will submit both the source code and the report. Our TA will run your code for assessment.
Tools: You will need to use the LC-3 simulator (either on Unix or on Windows, whichever you prefer) in order to execute and test the program you write for this MP. If you are using a Windows machine, use the LC3Edit program to type in your programs. On Sun and Linux workstations, pico, emacs, and vi are several of the text editors you can use.
Machine Problems:
MP1: Bit Pattern Rotation
Introduction: In this problem you will develop a machine language program to rotate a bit pattern to the left
by a certain amount (a number between 0 and 16, including 0 and 16).
Specifics: Your task in this part is to write a program in LC-3 machine language to rotate a bit pattern some number of bits to the left and store the result in memory. The rotate amount (number of bits you rotate the bit pattern to the left) is a non-negative integer between 0 and 16, inclusive. Your program should assume that the initial bit pattern is in memory location x3100 and the rotate amount is stored in memory location x3101. Using those values, your program should perform the left rotation and store the result in memory location x3102. Your program should start at memory location x3000.
Example: If the memory location x3100 contains the bit pattern 1101000100001011 and memory location x3101 contains the value 0000000000000101 (decimal 5), then your program needs to rotate 1101000100001011 5 bits to the left and store the bit pattern 0010000101111010 in memory location x3102. Note that when you rotate a bit pattern n bits to the left, it is just like a left shift except that top n bits before the shift end up as the bottom n bits.
Testing: The first line of your programs must specify the memory address of the first instruction of your program. LC-3 simulator will place your program starting at that address. For this assignment, you should place your program starting at x3000 (the first line of your program should contain the bit pattern 0011000000000000).
MP2: Integer Division and Modulo
Introduction: In this problem you will develop a machine language program to compute the integer division
result and the remainder (modulo). For example, 11 IDIV 4 = 2; 11 % 4 = 3.
Specifics:
You will implement two functions, modulo and integer divide. Y=A/B Z=A%B
In high level statement above, Y and Z are destinations in memory, and A and B are sources in memory. Recall that the LC-3 is a Load/Store machine. Before operating on the values stored in A and B, we must first load them into registers.
After computing the integer quotient and the modulus, we must store these results into memory. The source operand A is stored in location 0x3100 in memory. The source operand B is stored in location 0x3101. The result Y should be stored in location 0x3102. The result Z should be stored in location 0x3103. Your program should start at location 0x3000. You should make the following assumptions: A>0 B>0
1. Initial values: you should write your program assuming that there are already values stored in memory at locations 0x3100 and 0x3101. When using the LC-3 simulator to test your program, you should manually load test values into these memory locations before running your program.
2. Format: your program must be a text file of binary characters. Each line contains a 16 character string of ones and zeros followed by a carriage return.
The first line will give the starting address of the sequence of memory locations containing the program.
Example: Suppose you were being asked to submit the program that was the subject of our multiply routine. The first two lines might be:
0011000000000000 ; The program will be stored, starting with location x3000. 0101011011100000 ; Clear R3, which will be used to keep the intermediate results.
MP3: Bit Pattern Reversing
Introduction: You are asked to write a program in LC-3 machine language that takes a word stored at
memory location x3100 and reverse all the bits. Specifics:
You will store your result in memory location x3300. For this assignment, you should place your program starting at x3000 (the first line of your program should contain the bit pattern 0011000000000000).
Before running your program, you should deposit a value into memory location x3100 using the “Set Register or Memory” or “Set Values” menu in the simulator. If your program functions correctly, the number at the location x3300 will be the reverse of the bit pattern stored at location x3100. You should verify that your program works correctly by testing it with several different values.
Example: If the bit pattern 1010100101001011 is stored at memory location x3100, your program should write the bit pattern 1101001010010101 into memory location x3300.
MP4: Summing Packed Array
Introduction: There are many different ways of interpreting bits in memory. We are already familiar with the idea of a single LC-3 memory location containing either an LC-3 instruction or a 16-bit 2’s complement value. Consider a program that deals with small values in the range -128 to +127. We would only need 8 bits to represent each number, so to conserve memory we could pack two such numbers in a single LC-3 location, hence the name “packed,” as it is often called.
Specifics:
Assignment Write a program to calculate the sum of all the 8-bit 2’s complement values in a packed array of N elements. With N elements in the packed array, we require N/2 memory locations. For this assignment, we will assume N is even. (You might on your own think of what modifications you would have to make if N were odd.) Your SUM will be stored in one word of memory as a 16-bit 2’s complement number.
For each element in the array, bits [15:8] contain the first 8-bit value, and bits [7:0] contain the second value.
Your program should begin at x3000. The size of the packed array, N, is stored in location x3101. We will restrict the value of N to be less than or equal to 600 (decimal). The packed array itself is stored beginning at location x3102. Your program should store the result SUM in location x3100.
Initial Values Your program should assume that there are already values stored in memory at locations x3101 and x3102 through x3102 + (N/2 -1). When using the LC-2 simulator to test your program, you should manually load test values into these memory locations before running your program.
Example: Consider the following array, where x3101 contains N, the number of elements in the array: x3101 |x0006
x3102 |x7F03
x3103 |xFE7A
x3104 |x1B40
Your program should result in x0155 stored in location x3100.
Assembly Problems:
AP1: Data Analysis
Introduction: You will be creating a program that will analyze a given piece of text to determine the unique words of a length given to you by the user. Additionally, you will need to count the occurrences of each unique word in the text.
Specifics:
-Your program must start at location x3000.
-The text block you will be analyzing starts at location x4000 and is at most 32KB in size, but may be smaller.
-The end of the file (EOF) is marked with the ASCII “NULL” character.
-A word is defined as any sequence of the characters [A-Z] or [a-z] with no special characters in between. -Capitalization counts. (e.g., “ECE”, “EcE”, and “ECe” are all unique words.)
-Your prompts and results should be formatted exactly as shown in the included example output. Points will be lost for formatting discrepancies.
-The unique words should be printed in the order in which the words first appear in the original text. No unique word should appear in the output more than once.
-No more than 99 unique words will be found in any text that we test your code with.
-It is suggested that you create an array of unique words in memory to keep track of the words which have already been seen.
-Your program is to be written in LC-3 assembly language.
Example: If the text that you were given in memory is “I had a dream last night that a man had me over for dinner. I said that I did not like what we had, but he did not mind.”
Underlined characters are user input. Use the ASCII LF character (x0A) to go to a new line.
AP2: Data Type Conversion
Introduction: In this program we explore how data types can be converted to one another. We ask you to implement a program in LC-3 assembly language that converts an integer from its 2’s complement representation into its corresponding floating-point representation and outputs the floating-point equivalent of the 2’s complement integer onto the screen. As the LC-3 does not have a defined floating-point standard, we will first define a 16-bit floating-point format.
16-Bit Floating-Point Format Definition
By now, you should be familiar with the 32-bit IEEE standard floating-point format. If you want to refresh your memory, take a look at section 2.7.1 of the textbook. The word-size of LC-3 is 16 bits. Therefore, to make things easier we will define a 16-bit floating-point format to be used in this program. This format consists of 1 sign bit, 6 bits reserved for the exponent, and 9 bits reserved for the fraction. The format of a floating-point number looks like the following:
The bias of the above definition is 31, and therefore any floating-point number in the above format evaluates to
Specifics:
– Take a 2’s complement number stored in memory location x3100, convert the number into the floating-point representation specified above, and store the converted result into memory location x3101. Note that you will have to set memory location x3100 with a 2’s complement value before you execute your program.
– Output the 16-bit floating-point representation in 0’s and 1’s onto the screen.
– You are not required to perform bounds checking. Note that the 2’s complement number in memory
location x3100 contains a number in the range -32768 to 32767.
– Store the result of the floating-point conversion in memory location x3101.
– Make sure you follow the output conventions (i.e. the output should be exactly the same as the sample
output shown below).
– We request you place your program at starting at memory location x3000.
– Note: When the fraction field is not enough to accurately represent the initial integer, truncate the
fraction field. The floating-point representation should be as close as possible in value to the initial integer. For example, if memory location x3100 contains the 2’s complement representation of the integer 4147, the floating-point representation of 4147 should be 0101011000000110. Note that if you calculate what floating-point 0101011000000110 corresponds to, you will get the value of 4144. This is due to the fact that, to be precisely represented in the above floating-point format, 4147 needs a fraction field of at least 12 bits. But our floating-point format has a fraction field of 9 bits. Therefore the least significant three bits in the fraction of 4147 should be discarded. This is called truncation.
Example:
For example, suppose memory location x3100 contains the value 0000000000011001 (decimal 25) before the program starts. After the program executes, memory location x3101 should contain the value 0100011100100000 (floating-point 25). The program should also output the following:
FP representation is 0100011100100000
Suppose memory location x3100 contains the value 1000000000000000 (decimal -32768) before the program starts. After the program executes, memory location x3101 should contain the value 1101110000000000 (floating-point -32768). The program should also output the following:
FP representation is 1101110000000000
AP3: Cryptography
Introduction: Encrypting a file requires an input message, called the “plain text,” and an encryption algorithm. An encryption algorithm transforms “plain text” into “cipher text.” Just like a door needs a key to lock and unlock it, an encryption algorithm often requires a key to encrypt and decrypt a message. Just like a homeowner can selectively give the key to the front door to only those he wants to allow unaccompanied access, the author of a message can selectively give the encryption key to only those he wants to be able to read the message. In order for someone to read the encrypted message, he has to decrypt the cipher text, which usually requires the key. For example, suppose the plain text message is HELLO WORLD. An encryption algorithm consisting of nothing more than replacing each letter with the next letter in the alphabet would produce the cipher text IFMMP XPSME. If someone saw IFMMP XPSME, he would have no idea what it meant (unless, of course, he could figure it out, or had the key to decrypt it.) The key to encrypt in this case is “pick the next letter in the alphabet,” and the decryption key is “pick the previous letter in the alphabet.” The decryption algorithm simply replaces each letter with the one before it, and presto: the plain text HELLO WORLD is produced.
Specifics:
Implement, in LC-3 assembly language, an encryption/decryption program that meets the following requirements:
Input
Your program should prompt the user for three separate inputs from the keyboard, as follows:
1. The prompt: IF YOU WANT TO ENCRYPT, TYPE E; IF YOU WANT TO DECRYPT, TYPE D:
– The user will type E or D. A real world program should also detect any other character typed and
respond with THAT IS AN ILLEGAL CHARACTER. PLEASE TRY AGAIN. We will assume in
this assignment that the user can type an E or D correctly.
– Your program will accept that character, store it in x3100, and use it, as we shall see momentarily.
2. The prompt: ENTER THE ENCRYPTION KEY (A SINGLE DIGIT FROM 1 TO 9):
– The user will type a single digit, from 1 to 9. Again, we will assume the user is not an Aggie, and can
successfully hit digit keys on the keyboard.
– Your program will accept this digit, store it in x3101, and use it to encrypt or decrypt the message.
3. The prompt: INPUT A MESSAGE OF NO MORE THAN 20 CHARACTERS. WHEN DONE, PRESS
– The user will input a character string from the keyboard, terminating the message with the
– Your program will store the message, starting in location x3102. Since the message is restricted to #20 characters, you must reserve locations x3102 to x3115 to store the message. (Note that #20 = x14.)
– One constraint: Messages must be less than or equal to #20 characters. (Recall: # means the number is decimal.)
Algorithm
The encryption algorithm is as follows. Each ASCII code in the message will be transformed as follows:
1. The low order bit of the code will be toggled. That is, if it is a 1, it will be replaced by a 0; if it is a 0, it will be replaced by a 1.
2. The key will be added to the result of step 1 above.
• For example, if the input (plain text) is A and the encryption key is 6, the program should take the ASCII value of A, 01000001, toggle bit [0:0], producing 01000000 and then add the encryption key, 6. The final output character would be 01000110, which is the ASCII value F.
The decryption algorithm is the reverse. That is,
1. Subtract the encryption key from the ASCII code. 2. Toggle the low order bit of the result of step 1.
• For example, if the input (cipher text) is F, and the encryption key is 6, we first subtract the encryption key (i.e., we add -6) from the ASCII value of F, 01000110 + 11111010, yielding 01000000. We then toggle bit [0:0], producing 01000001, which is the ASCII value for A.
• The result of the encryption/decryption algorithm should be stored in locations x3116 to x3129.
Output
Your program should output the encrypted or decrypted message to the screen. Note that the encryption/decryption algorithm stored the message to be output starting in location x3116.
Extra Information
-The starting location is to be x3000
-The buffers have been expanded to 21 memory locations each so that you may store
-The prompts have been shortened Prompt 1: (E)ncrypt/(D)ecrypt: Prompt 2: Encryption Key: Prompt 3: Input Message:
AP4: Day of the Week
Introduction: Your job is to write a program in LC-3 assembly language that provides the day of the week
for any date between January 1, 1901 and the present day.
Specifics:
• Input :
Your program will start at address x3000 and will work with other modules that will load x31F0, x31F1, x31F2 before your program computes the day of the week. You can assume that before your program executes, x31F0, x31F1, and x31F2 will contain data as follows:
x31F0: the day of the month (a number from 1 to 31).
x31F1: the month (a number from 1 to 12, corresponding to Jan to Dec). x31F2: the year (a four digit number)
For example October 2, 1989 will be stored as, x31F0 : #2
x31F1 : #10
x31F2 : #1989
You should test your program by supplying values in these three memory locations and then running your program.
• Output :
(A) Store the code for the day of the week in x31F3.
For example, in the case of April 10, 1901, you must store a 3 in x31F3. Use the following codes for the DAY of the WEEK:
Sunday = 0 Monday = 1 Tuesday = 2 Wednesday = 3 Thursday = 4 Friday = 5 Saturday = 6
(B) Display on the screen the message: The day is <
For example, in the case of 02 10 1989, the screen should display: The day is Monday.
Example:
• Suppose we want to find out the day of the week that July 4, 1999 fell on.
Your program must start with the three locations containing the values shown:
x31F0 : #4 x31F1 : #7 x31F2 : #1999.
Since 1999 -1901 = 98, and January 1, 1901 was a Tuesday, January 1, 1999 is a Friday. Since January 1, 1999 was a Friday, July 1 was a Thursday. Since July 1, 1999 was a Thursday, July 4 was a Sunday.
Thus, the program stores 0 in x31F3, and displays: The day is Sunday.