Description
CS 0447 Project 1 – Calculator
The purpose of this project is for you to practice writing assembly language to interact with
output/input hardware. The hardware for this project is a dollar store calculator as shown below
(on left):
The Calculator (Mars Tool) that we are going to use for this project is shown above (on right).
This tool can be found in SimpleCalculatorRegister.zip located in the CourseWeb under this
project. Extract all files to your [..]/mars4 5/mars/tools directory. If you extract all files to the
right directory, when you run the MARS program, you should see ”Simple Calculator (Register)
V0.1” under the ”Tools” menu.
Introduction to the Simple Calculator (Mars Tool)
The Simple Calculator (Mars Tool) consists of two parts, LCD display and a key pad. The LCD
display is connected directly to the register $t8. It simply display the value of the register $t8 on
the LCD screen. Thus, whatever number your program wants to show on the calculator’s LCD
screen, simply put it in the register $t8. This display supports both positive and negative number.
If the value stored in the register $t8 is a negative value, a minus symbol will be displayed before
the value (e.g., -123). Note that there is no dot symbol (.) on the key pad. This Simple Calculator
can only display integer numbers. For this project, we will focus only on integer operations. Thus,
the division must be the integer division (e.g., 5 / 2 = 2).
1
There are 16 buttons on the key pad, 0 to 9, +, −, ∗, /, =, and C (clear). This key pad is
connected directly to the register $t9. If the value of the register $t9 is currently equal to 0 and
a button is pressed, the Most Significant Bit (MSB) of the register $t9 (bit 31) will be 1 and the
last four bit of the register $t9 (bit 0 to bit 3) will be changed according to the pressed button
as shown in Table 1. Note that these buttons are disabled if the content of the register $t9 is
Button b3b2b1b0
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
+ 1010
− 1011
∗ 1100
/ 1101
= 1110
C 1111
Table 1: Associated Values of Buttons
not equal to 0. Thus, it is your responsibility to change the content of the register $t9 to 0 when
your program is ready to get a new key pad input. Note that the Simple Calculator does not use
syscall. Thus, there is no special instruction for your program to wait for an input from the key
pad. Your program has to loop checking the value of the register $t9 until it is not zero. The
non zero value will be the input. Again, do not forget that when an input exists, the MSB of the
register $t9 will be 1 and the last four digits are used to represent a pressed button.
What to Do?
For this project, write a MIPS assembly program such that when the program is running, the
Simple Calculator will behave just like a dollar store calculator. Note that there are various kind
of dollar store calculators. They may behave differently. So, let’s follow the behavior as shown in
Table 2. According to the Table 2, we assume that to calculate a result, we need three variables,
two for operands and one for an operator. Let’s call these operand1, operand2, and operator,
respectively. According to the Table 2, if a user press operator key more than one time consecutively,
this calculator will use the last pressed operator key as the operator. For example, if user press the
following key 5, *, -, 9, and =, (in that order) your calculator should show the result -4 because 5 –
9 = -4. As you may notice, because of this type of behavior, we cannot have a negative number as
the second operand. For example, we a user wants to calculate 49 * (-52), the user has to calculate
(-52) * 49 instead which can be achieve by the following series of key presses, C, -, 5, 2, *, 4, 9, and
=. Note that when user press C, -, 5, and 2, the screen should show 52 because user is actually
2
calculating 0 – 52.
Requirements
The following are requirements that you must follow:
• Your program should be named calculator.asm
• Since the Simple Calculator (Mars Tool) uses registers $t8 and $t9, do not use these registers
for any other purpose.
• You can only use registers $s0 to $s7 and $t0 to $t9 in your program.
• Do not use any system calls (syscall). Do not worry that your calculator will run indefinitely.
• No functions in your program. In other words, do not use instructions jal and jr or stack
pointer ($sp). You may already learn how to create a function in assembly language and feel
tempted to do so. DON’T.
• No memory reference instructions are allowed (no load and store instructions).
• Your program should have only the text segment (.text) and no data segment (.data).
• You are not allowed to use multiplication and division instructions. Simply use loop to achieve
those type of calculations.
• Try not to use pseudo instructions. This project can be done by using only add, addi, sll,
srl, slt, beq, bne, and j instructions and a lot of labels. Note that this requirement is not
a definite requirement. If you need to use other instructions, you are allowed to do so. The
main reason why we should not use pseudo instruction is because we may use this program
for your last project. If you use a lot of pseudo instructions or a complex instructions, you
may have to rewrite your program for your last project.
Hints
• Focus on a small task at a time. For example:
1. Write the program to receive a numeric keypad and show the correct number of the LCD
screen
2. Extend from 1 to support a series of numeric keypad (e.g., 5, 2, and 9 should result in
529 on the LCD screen). Note that multiply by 10 can be easily achieved by shift left
three follows by adding with the original number twice.
3. Extend from 2 to support C (clear) button.
4. Practice writing multiplication and division.
Submission
The due date of this project is stated on the CourseWeb. Late submissions will not be accepted.
You should submit the file calculator.asm via CourseWeb.
3
State Input Actions
0 N/A Set operand1 and operand2 to 0
(Start) Set operator to nothing
Display operand1
Go to state 1
1 0 – 9 operand1 = (operand1 * 10) + Input
Display operand1
Go back to State 1
+,−,∗,/ operator = Input
Display operand1
Go to State 2
= result = operand1
Display result
Go to State 4
C Go to State 0
2 0 – 9 operand2 = (operand2 * 10) + Input
Display operand2
Go to State 3
+,−,∗,/ operator = Input
Display operand1
Go back to State 2
= result = operand1
Display result
Go to State 4
C Go to State 0
3 0 – 9 operand2 = (operand2 * 10) + Input
Display operand2
Go back to State 3
+,−,∗,/ result = operand1 operator operand2
Display result
operand1 = result
operand2 = 0
operator = Input
Go to State 2
= result = operand1 operator operand2
Display result
operand2 = 0
Go to State 4
C Go to State 0
4 0 – 9 operand1 = Input
Display operand1
Go to State 1
+,−,∗,/ operand1 = result
operator = Input
Go to State 2
= Display result
Go back to State 4
C Go to State 0
Table 2: Behavior of a Dollar Store Calculator 4
CS 0447 Project – Simon
The purpose of this project is for you to practice writing assembly language to interact with
output/input hardware. The hardware for this project is a game called Simon (on left):
The Simon (Mars Tool) that we are going to use for this project is shown above (on right). This
tool can be found in simon.zip located in the CourseWeb under this project. Extract all files to
your [..]/mars4 5/mars/tools directory. If you extract all files to the right directory, when you
run the MARS program, you should see ”Simon (Register) V0.1” under the ”Tools” menu.
Introduction to the Simon Game
Simon is a classic game from the 70’. See https://en.wikipedia.org/wiki/Simon (game) for
more detail. During the game play, the computer will play a sequence of tone and lit a button
associated to each tone. Each round, a player has to play the sequence back by pressing a series of
buttons. The length of the sequence starts at 1 at round 1 and increases by 1 for every round. At
n
th round where n ≥ 2, The computer will play a sequence of length n where the first n − 1 tones
are exactly the same as the sequence at round n − 1 and the n
th tone is a new one (randomly pick
a new one). The game is over when a player plays a wrong sequence.
Introduction to the Simon (Mars Tool)
The Simple Calculator (Mars Tool) consists of four colored buttons and one start game button.
These buttons are connected directly to the register $t9. If the value stored in the register $t9 is
1
currently 0, when a button is pressed, the value of the register $t9 will be changed according to
the pressed button as shown below:
Button Value of $t9
Blue 1
Yellow 2
Green 4
Red 8
Start Game 16
Note that if the content of the register $t9 is not equal to 0, these buttons are disabled. Thus, it
is the programmer responsible to change the content of the register $t9 to 0 when the program is
ready to accept the next input.
For this Simon (Mars Tool), the hardware is simply an input device. It is the program responsibility to tell the hardware to light a button and play sound, play starting sound, and play game
over sound. A command can be sent to the Simon game by simply change the value of the register
$t8 from 0 to a specific value as shown below:
Value of $t8 Command
1 light the blue button and play its associated tone
2 light the yellow button and play its associated tone
4 light the green button and play its associated tone
8 light the red button and play its associated tone
15 play the game over tone, light all colored button three times,
and enable the Start Game button
16 disable the Start Game button and play starting sound
Note that after the Simon game receives a command, it may take some time to process. After
a received command has been processed, the Simon game will change the content of the register
$t8 to 0. Thus, it is the programmer responsibility to wait until the content of the register $t8 is
changed to 0 before sending the next command.
What to Do?
For this project, write a MIPS assembly program named simon.asm such that when the program
is running, the Simon game will behave just like an actual Simon game hardware. Note that when
a player plays a wrong sequence, the Simon game should play the game over tone, light all colored
button three times, and enable the ”Start Game” button for the next player without restarting the
program.
Requirements
1. Since registers $t8 and $t9 are used for sending command and receiving button input, do
not use these registers for any other purpose.
2. Your program must consist of at least two functions as follows:
• playSequence: This function, when called, it will play a sequence of tones.
2
• userPlay: This function lets user play back the sequence. Note that this function should
return a value to notify the caller whether user successfully play back the sequence or
not.
3. You are allowed to have more functions.
4. Everything that a function needs should be passed as arguments.
5. Everything that a caller needs from a function must be passed as return values.
6. Every functions must follow the calling convention discussed in class.
Submission
The due date of this project is on the CourseWeb. Late submissions will not be accepted. You
should submit the file simon.asm via CourseWeb.
CS 0447 Project – Sudoku
The purpose of this project is for you to practice writing backtracking with recursion in assembly
language. The main goal of your program is to solve a Sudoku puzzle. The Sudoku (Mars Tool)
that we are going to use for this project is shown below. This tool can be found in sudoku.zip
located in the CourseWeb under this project. Extract all files to your [..]/mars4 5/mars/tools
directory. If you extract all files to the right directory, when you run the MARS program, you
should see ”Sudoku (Memory) V0.1” under the ”Tools” menu.
Introduction to the Sudoku Puzzle (from Wikipedia)
Sudoku (originally called Number Place), is a logic-based, combinatorial number-placement
puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the
nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, “regions”, or “subsquares”)
contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which
for a whell-posed puzzle has a unique solution.
Completed games are always a type of Latin square with an additional constraint on the contents
of individual regions. For example, the same single integer may not appear twice in the same row,
column, or any of the nine 3×3 subregions of the 9×9 playing board.
Visit https://en.wikipedia.org/wiki/Sudoku for more information about Sudoku.
1
Introduction to the Sudoku (Mars Tool)
Sudoku (Mars Tool) will fill the main memory byte-by-byte starting at the address 0xFFFF8000
with puzzle. If a square is blank, the associated memory location will be filled with 0. For example,
the content of the main memory starting at the address 0xFFFF8000 associated with the puzzle
shown above is as follows:
Address Content row column
0xFFFF8000 0 0 0
0xFFFF8001 0 0 1
0xFFFF8002 0 0 2
0xFFFF8003 0 0 3
0xFFFF8004 0 0 4
0xFFFF8005 0 0 5
0xFFFF8006 0 0 6
0xFFFF8007 0 0 7
0xFFFF8008 0 0 8
0xFFFF8009 0 1 0
0xFFFF800A 5 1 1
0xFFFF800B 8 1 2
0xFFFF800C 0 1 3
.
.
.
.
.
.
.
.
.
.
.
.
IMPORTANT: Since the Sudoku (Mars Tool) needs to update memory contents, after you successfully assemble your program, you must press either the “Reset” or “New Puzzle” button before
your run your program. This will allow the Sudoku (Mars Tool) to write data into your memory.
The “Reset” button will clear the puzzle without changing the puzzle and update contents of the
main memory. Similar to the “Reset” button, the “New Puzzle” button will create a new puzzle
and update contents of the main memory.
Note that each puzzle generated by the Sudoku (Mars Tool) will have exactly one solution. Your
program MAY NOT modify contents of the memory that contain the original digits. In the above
example, you are not allowed to modify contents at memory locations 0xFFFF8009, 0xFFFF800A,
0xFFFF800C, and so on. The “Check” button can be used to verify your solution. If a square
contains an invalid digit, the digit will turn red. Otherwise, it will turn green. If a square of the
original puzzle that contain a digit has been modified, it will turn red as well. The figure below
shows the result of pressing the “Check” button when the puzzle is being solved correctly.
2
What to Do?
For this project, write a MIPS assembly program named sudokuSolver.asm to solve a Sudoku
puzzle. Your program must perform the following:
1. Your program must display the puzzle on the console screen of MARS. For example, for the
puzzle shown on the first page, your console screen should display the following:
000000000
058020039
304008020
000907003
002010400
600302000
040200906
780090340
000000000
This step simply check that your program can read a given puzzle correctly. This part will
be your partial credit in case your program cannot solve a puzzle.
2. Your program must solve the Sudoku puzzle by changing contents of main memory starting
at the address 0xFFFF8000. If a data stored in a memory location is not zero, do not modify
the content of that memory location since it is a part of the puzzle. If a data stored in a
memory location is zero, you must change it to a non-zero value (1 – 9). Again, make sure
you follow all rules of Sudoku.
Once the puzzle is solved, your program should simply terminate. After your program is terminated,
you should click the “Check” button to verify that the puzzle is solved correctly.
3
Recursion and Backtracking for Sudoku
An idea of using recursion and backtracking to solve a Sudoku puzzle is to associate a recursive call
with a cell in Sudoku. For example, suppose your solveSudoku function looks like the following:
boolean _solveSudoku(int row, int column)
{
:
}
When solveSudoku(r, c) is called, this call is responsible for filling the cell at row r column c.
Once it finds a number that has no conflict, it should make a recursive call to solveSudoku(r, c
+ 1) so that the next call will take care of row r, column c + 1.
Now, consider a recursive call solveSudoku(r, c). At this call, if the cell at row r column
c is available, this call has 9 possible numbers (1 – 9) to put into this row r column c. This call
will pick the first number that does not have any conflict (row, column, and 3 by 3) and put it
into the cell. Note that this number (choice) may or may not lead to the correct solution. If the
select (no conflict) number does not lead to the solution, this call have to pick the next no conflict
number. However, if this call runs out of a choice of numbers. This mean that the choice picked
by the previous call does not work. So, this call have to send a signal to previous call (a return
value) to tell the previous call to pick a new number. But importantly, this call should set the row
r column c back to its original value (0) before returning back to the previous call.
Note that some cells may already have numbers. If that is the case, the recursive calls responsible
to those cells do not have to do anything. Simply call the next one.
Suppose the first row is the row number 0 and the first column is the column number 0, the
next page shows a pseudo code that solve a Sudoku puzzle using backtracking and recursion.
Requirements
1. Your program MUST use backtracking and recursion to solve puzzles.
2. Your program must contain the function named solveSodoku. This will be your recursive
function.
3. You can create as many helper function as you wish. For simplicity, at least you should have
the following three helper functions:
• checkRow: This function checks whether a given number is already in a give row.
• checkColumn: This function checks whether a given number is already in a given column.
• checkSubgrid: This function checks whether a given number is already in a subgrid
where a given row and a given column is located.
4. All functions in your program must follow all calling conventions discussed in class.
Submission
The due date of this project is on the CourseWeb. Late submissions will not be accepted. You
should submit the file sudokuSolver.asm via CourseWeb.
4
boolean _solveSudoku(r, c)
{
boolean p;
if(r == 8 and c == 9)
return true;
if(c == 9)
{
r = r + 1;
c = 0;
}
if(data at row r column c is not 0)
return _solveSudoku(r, c + 1);
else
{
for i = 1 to 9
{
if(i has no conflict)
{
put i into the cell at row r column c;
p = _solveSudoku(r, c + 1);
if(p)
return true;
}
}
put 0 back to the cell at row r column c
return false;
}
}
Pseudo Code
CS 0447 Project 4 – Multiplication and Division Hardware
The purpose of this project is for you to build 16-bit multiplication and 16-bit division hardwares
as we discussed in class in logisim.
Introduction to the Multiplication Hardware
The 16-bit multiplication hardware that we discussed in class is shown below:
M_Ready
Product
32
Multiplier 1
Multiplicant
Mul
16
16
1
Clock
Multiplication
Hardware
You can consider the above circuit as a sub-circuit named multiplication which contains the
following input/output:
• Multiplicand: a 16-bit input
• Multiplier: a 16-bit input
• Mul (1-bit input): This input will be one if the instruction is the multiplication instruction
• Clock (1-bit input)
• Product (32-bit output)
• M Ready (1-bit output): This output will be 1 if the product is ready
Note that we require to have the output M Ready because the multiplication instruction will take
multiple clock cycles to produce a result. Ideally, if a CPU see the instruction mul, it will set the
appropriate Multiplicant and Multiplier. Then, it will set Mul to 1 and wait until the signal
M Ready to turn to 1 before it continues to the next instruction. The circuit inside will be the same
as the multiplication hardware discussed in class as shown below:
Multiplicand
Shift left
Product
Write
Control test
Shift right
Multiplier
32 bits
16 bits
32−bit Adder
32 bits
1
Inside the multiplication hardware, you need three registers, Multiplicand (32-bit), Multiplier
(16-bit), and Product (32-bit). For these registers, you do not have build them from scratch.
Simply use the register component under “Memory”. Similarly, for the 32-bit adder, simply use
the one supplied by the logisim. Note that the above hardware is for multiplying two 16-bit
numbers and produce a 32-bit result. The flowchart of this hardware is shown below:
Start
Multiplier0
1. Test
1a. Add multiplicand to product and
place the result in Product register
2. Shift the Multiplicand register left 1 bit
3. Shift the Multiplier register right 1 bit
Done
Multiplier0 = 1 Multiplier0 = 0
No: < 16 repetitions
Yes: 16 recetitions
16nd rep?
Recall that in the first step, this hardware have to load the top 16-bit of the multiplicand register
with 0s and the bottom 16-bit with Multiplicand, load the product register with 0s, and load the
multiplier register with the Multiplier. After all three registers are loaded with proper values,
then the algorithm can start as follows.
1. product = product + (multiplicand ∗ multiplier0
): In this step, if multiplier0
is 0, we
actually perform product = product + 0. But if multiplier0
is 1, we perform product =
product + multiplicand. This can be done by adding a 32-bit (2-input) multiplexer. This
multiplexer has two inputs, one from the multiplicand and another one is imply a 32-bit constant 0. Simply use the Least Significant Bit (LSB) of the multiplier register (multiplier0
)
to choose which one to go to the output as shown below:
Multiplicand Product
u
x
m
0
multiplier0
Note that before the algorithm starts, you must clear the product register which can be
done in two ways:
2
(a) by writing 0. So, you also need another multiplexer to choose whether you want to write
0 or output from 32-bit adder to the product register as shown below:
Multiplicand
u
x
m
u
x
m
Product 0
multiplier0
0
Clear
Product
(b) use the Clear input pin of the register. Simply set it to 1 and the content will be cleared.
2. Shift multiplicand register left one bit: This step is simply update the multiplicand register by its data that has been shifted left by 1. Simply use a Shifter provided by logisim
under Arithmetic. Note at the first step before the algorithm starts, you need to update
multiplicand register by the input Multiplicand. So, you need a multiplexer to select which
data should go to the multiplicand register (Multiplicand input or multiplicand << 1.
The block diagram of the circuit is shown below:
u
m
x
Multiplicand
Multiplicand
0
16
16
32
1
3. Shift multiplier register right one bit: This step is pretty much the same as in previous step.
You need to be able to load the content of the multiplier or update it with multiplier >> 1
Note that we need an ability to control what to do at each clock cycle. For example, in the
first clock cycle, we need to load contents of all registers. The next clock cycle, we need to
perform product = product + (multiplicand ∗ multiplier0
). The third clock cycle, we need
to perform multiplicand = multiplicand << 1. The fourth clock cycle, we need to perform
multiplier = multiplier >> 2, and so on. To be able to control each clock cycle, we will use a
combination of counter and Read Only Memory (ROM) as shown below:
Clock
Mul
Counter ROM
M Ready
When Mul is 1, it will clear the Counter to 0. At the same time, it will allow the clock signal to
go to the Counter. So, the Counter will start counting up until its desired maximum value which
can be set. When it reaches its maximum value, its Carry signal will be 1 which can be used for
3
the signal M Ready. The output of the Counter will be use as the address of a ROM. The content
of the ROM will be control signal for each clock cycle. In other words, you can program what do
you want to do at each clock cycle by content of the ROM.
Note that you MUST set the maximum value of the counter to stay at a specific value based
on the number of clock cycles that your hardware uses. MAKE SURE that the last output value
of the ROM should maintain the output of your product register. When we grade your circuit, we
will simply put value of multiplicand and multiplier, and let the clock tick until M Ready turn green
without stopping the clock and check the result.
Introduction to the Division Hardware
The 16-bit division hardware that we discussed in class is shown below:
16
16
1
Clock
Hardware
Divisor
Dividend Quotient
1
16
16
Remainder
D Ready
Division
Div
You can consider the above circuit as a sub-circuit named division which contains the following
input/output:
• Dividend: a 16-bit input
• Divisor: a 16-bit input
• Div (1-bit input): This input will be one if the instruction is the division instruction
• Clock (1-bit input)
• Quotient (16-bit output)
• Remainder (16-bit output)
• D Ready (1-bit output): This output will be 1 if the product is ready
The division hardware that we discussed in class is shown below:
Control test
32 bits
32 bits
16 bits
Quotient
Divisor
Write
Remainder
Shift right
Shift left
32−bit Adder
Again, the above hardware is for dividing two 16-bit numbers and produce a 16-bit quotient and
16-bit remainder. The flowchart of this hardware is shown below:
4
Start
1. Subtract the Divisor register from the
Remainder register and place the
result in the Remainder register
Remainder
Test
2b. Restore the original value by adding
the Divisor register to the Remainder
register and placing the sum in the
Remainder register. Also shift the
Quotient register to the left, setting the
new least significant bit to 0
3. Shift the Divisor register right 1 bit
Done
2a. Shift the Quotient register to the left,
setting the new least significant bit 1
Remainder >= 0 Remainder < 0
No: < 17 repetitions
Yes: 17 repetitions
17rd
repetition?
The design concept of this division circuit will be pretty much the same as in multiplication circuit
but it requires more steps. For example, when the subtraction result is less than 0, you have to
restore to its original value by adding it back. Another different is the quotient, sometime we shift
it left and insert a 0 but sometime we insert a 1.
What to Do?
For this project, start with the given starter file named muldiv.circ. This starter file contains
two sub-circuits, 16-bit multiplication and 16-bit division. In both sub-circuit, the counter
and ROM are provided. Simply build your multiplication and division circuits there. Once you are
finish, put your circuits in the main and connect them with appropriate input/output. We will test
your circuit from the main circuit.
Again, you MUST set the maximum value of the counter to stay at a specific value based on
the number of clock cycles that each of your hardwares use. We will not stop the clock when we
check your results.
Submission
The due date of this project is stated in the CourseWeb under this project. Late submissions will
not be accepted. You should submit the file muldiv.circ via CourseWeb.
