IC220 Spring 2014                     Project #1: Fabulous Factoring?             

 

This project must be completed independently (unlike regular assignments).

This means collaboration between students is not permitted. Online sources (aside from IC220’s website) are also prohibited.  You may consult your notes, textbook, and the instructor. See the instructor for help or clarification.

 

Background: You have already had experience with writing simple MIPS programs and testing them with SPIM.  In this project you will review and integrate your understanding of:

1.      General MIPS programming

2.      Function calls

3.      Recursion

 

Task:  Write a recursive MIPS program that outputs all the factors of a given integer.  Factors must be printed in decreasing order. To do this, translate the following C++ code into MIPS:

 

int getFirstFactor(int N);

void printFactors (int N);

 

int main() {

 

    // Get number from user   

    int N;

    cout << "Welcome to MIDN. Smith's (alpha XXXXXX) Factorizer!\nPlease enter number: ";

    cin  >> N;

 

    // Find the first factor and print it

    cout << "First factor is: " << getFirstFactor(N);

 

    // Print out *all* factors

    cout << "\nAll factors: ";

    printFactors(N);

    cout << "\nGoodbye!\n";

 

    return 0;

}

 

// Returns the smallest factor of N. 

int getFirstFactor(int N) {

        int ii=2;

        while (N % ii != 0)

        {

               ii++;

        }

                                                                             return ii;

}

 

// Prints out all the factors of N, from LARGEST to SMALLEST

void printFactors (int N) {

    // base case

    if (N <= 1) {

                                                                             return;

    }

   

    // recursive step -- find first (smallest) factor and remember it

    int aFactor = getFirstFactor(N);

 

    // print the remaining factors (possibly larger ones)

    printFactors(N / aFactor);

 

    cout << "(" << aFactor << ")";  

 

}

 

 

 

 

When finished, running your program should look like this (except with your name and alpha):

 

To solidify your understanding of recursion and the stack you are required to have a recursive solution.

 

Specifics: Starter code is provided (see calendar). You should do the following with this code:

1.      Run it and verify it works as-is.

2.      Study the code to understand

a.      how division works (including how to get the remainder, see the comments)

b.      how a function call, and a function definition, fit into a complete MIPS program

3.      Modify to print a welcome message that includes your name and alpha

4.      Write the getFirstFactor() function (translate from the provided C++)

5.      Modify main() to call this function and print the results (translate from code shown in C++ main() )

6.      Test (in SPIM) and verify it works so far.

7.      Write the printFactors() function (translate from provided C++)

8.      Modify main() to call this function (as shown in the C++). Note that calling this function will print the factors out; main doesn’t need to directly print them itself.

9.      Test in SPIM, and keep refining till it works!

10.   Verify that everything all works, including

a.      printFactors() is recursive?

b.      Factors print in decreasing order?

c.      Your code does exactly what the C++ does?

d.      ALL your functions should obey all the rules for register conventions that we discussed?  For instance, if I replaced your getFirstFactor() function with a version written by someone else, it should still work, because of the conventions.  If your function does not follow all the register conventions, it is not correct.

 

 (more on back)
Tips:

1.      Start early!  Recursion can be tricky.  Allow time to get help from the instructor if needed.

2.      But don’t make this harder than it needs to be! Your primary task is to simply translate the C code above to a few MIPS functions.  While one function is recursive, really this is just another example of a nested procedure – follow the rules for nested procedures and recursion will take care of itself.

3.      You will need to use the stack.  Before you begin, make sure you understand how to do this and what will need to be saved and restored with the stack.

4.      Warning: executing “syscall” may change the value of registers like “a0”, “a1”, etc. and “v0”, “v1” etc. So after a syscall, you must assume that all those registers have changed values.

5.      This assignment requires you to write less than 100 carefully chosen assembly instructions (and likely much fewer).  If you have many more than that, you probably are misunderstanding what should be done.

6.      The following material may be helpful to you:

·        Lecture notes on MIPS procedure calls, and SPIM

·        Homework, especially exercises 2-35 thru 2-37. Really spend time to understand these before you start!

·        Lab #1, where you first used SPIM

·        SPIM reference material: http://www.usna.edu/Users/cs/lmcdowel/courses/ic220/spim/

7.      Use Alt-PrintScreen to generate a screenshot. 

8.      An error message like “Can’t add 8 bytes to Lstack” means you are stuck in infinite recursion.

9.      Use the starter code!

10.   In SPIM, the value of the registers might be displayed by default in hex. You can change this to decimal via the menu option:   “Registers->Decimal"

 

Deliverables:

A. Hard-copy (print and staple in the following order):

1)          A cover sheet with your feedback.                                                                        (10 pts)

2)          Screenshot showing your program factoring 330                                                 (10 pts)

3)          Printout of your correct and recursive assembly code                                         (70 pts)
            (remember, factors must print in decreasing order!)

 

B. Electronic:

1)          On Blackboard->IC220->Assignments->Project 1, submit your .asm file.         (10 pts)

2)          If submitting any extra credit, also submit extra .asm files for those.

 

Extra credit (up to 5 pts each):

1. Re-write the C++ code to be non-recursive, then implement that in MIPS.  Turn it in as a separate .asm file, along with a screenshot showing it working. Change the prompt to indicate that this is now a different program.