CS2461-10程序讲解、辅导Java，c/c++，Python编程设计

日期：2021-03-01 11:04

CS2461-10 Computer Architecture I

Spring 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 <ENTER>

- The user will input a character string from the keyboard, terminating the message with the <ENTER>

key.

- 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 <ENTER>

x3100 <-E/D

x3101 <-Encryption key

x3102 through x3116 <-input buffer

x3117 through x312A <-output buffer

-The <ENTER> key is mapped to the line feed character on the LC-3 (ASCII x0A)

-Acceptable inputs to be encrypted are any ASCII characters within the range x20 to x5A

-You may assume the user will only type an upper-case E or D

-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 <<followed by the correctly spelled day

that the date fell on>>.

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.