CSE 378 Homework 2 - Part 2

Cebollita Exercises

What To Hand In For This Part

Nothing.

Introduction

We begin with some assembler programming, using the following program that computes the factorial of 9. The line numbers you see are for reference only, and are not part of the actual assembly program. 
 1  # compute the factorial of 9 using the following algorithm
 2  #   N = 9
 3  #   result = 1
 4  #   while (N != 0) {
 5  #     result = result * N
 6  #     N = N - 1
 7  #   }
 8  
 9  .data                                   # begin data section
10  N:      .word    9                      # reserve and initialize a word
11  result: .space   4                      # reserve but don't initalize a word
12  msg:    .asciiz  "The factorial is: "   # message string
13  newline: .asciiz "\n"
14          
15  .text                                   # begin program text
16      .global main
17  main:
18          addi    $t0, $0, 1              # $t0 will hold result, initially 1
19          lw      $t1, N($gp)             # $t1 will hold N, initially 9
20      
21  top:    beq    $t1, $0, bottom
22          mult    $t0, $t0, $t1           # result = result * N
23          addi    $t1, $t1, -1            # decrement N
24          j       top                     # goto top
25      
26  bottom:
27          sw      $t0, result($gp)        # we'd better save result
28  	
29          addi    $v0, $0, 4              # finished w/ loop, now print out
30          addi    $a0, $gp, msg           # message, by invoking syscall 4
31          syscall                         # (print_string)
32  
33          addi    $v0, $0, 1              # now print out result, by 
34          lw      $a0, result($gp)        # invoking syscall 1 (print_int)
35          syscall
36  
37          addi    $v0, $0, 4              # print a newline
38          addi    $a0, $gp, newline
39          syscall
40  
41          halt                            # all done
Thankfully, you don't have to type the program in yourself, as you can download it (as well as a C-- program needed a bit later) here. Put it in some directory, e.g., Z:\cse378\hw2\. Make sure it's called fact.s (not fact.s.txt, as IE will happily try to name it).

Assembling/Linking Your Program

  1. As well as the file fact.s, you're going to need some "prologue" code. We've written fact.s to run "stand alone" -- without requiring any additional libraries (or even any real operating system). The prologue we need is Z:\cebollita\apps\prologues\prologue-standalone.o. Copy that file to the directory that has fact.s in it.

  2. Now you need to assemble fact.s to produce the "object code" file fact.o. You can do that with:
    $ java asm.parser fact.s
    or, if you've set up the standard aliases (#7 here):
    $ cebasm fact.s
    The .o file contains a translation of the assembler instructions into machine code, plus some information needed to link the object code into an executable.

  3. To create an executable file, fact:
    $ java asm.Linker --output fact prologue-standalone.o fact.o
      or  
    $ ceblink --output fact prologue-standalone.o fact.o
    Note: it's important to specify the two .o files in the order shown.

Each time you change fact.s you'll need to re-assemble and re-link (steps 2-3 above).

Look at the .o and Files

Cebollita provides tools that will "dump" .o and files -- print them on the screen for you. They're binary files, not characters, so you can't just print them in the normal way.

Try them out:

$ java asm.Module fact.o
$ java util fact 		  or   $ cebdumpm fact.o
$ cebdumpe fact
(For added excitement, try cebdumpe fact | less.)

Running Your Program on the Cebollita Simulator

  1. You'll first want to read over the document The Cebollita ISA Simulator/Debugger. (Note that that document doesn't know about the aliases you established (like cebsim) and so writes things out the hard way.)

  2. Start the simulator:
    $ java dbg.UI fact   or   $ cebsim fact
  3. Complete the following table by examining various registers and memory location contents after the appropriate instructions are executed. Setting breakpoints (right-click on an instruction...) may help in certain situations.

    Location Line 18 Line 22
    3rd iteration    		 Line 22
    5th iteration    		 Line 22
    8th iteration    		 Line 26
    $t0




    $t1




    result($gp)




  4. In total, how many instructions (in the simulator) are executed to calculate the factorial of 9? The right way to answer this question is not to step the program through 9 loops and count instructions, but rather determine how many instructions are exectuted before the loop, during one iteration of the loop, and after the loop. Then you can give us an answer in terms of N, where N is the value we're calculating the factorial of (as well as the number of times the loop iterates).

  5. Did you answer 4 already? Turns out the simulator prints out some useful information in the console window when you're done simulating...

Assembly Programming: Modifications

Modify fact.s so that it reads a value for N from the user, and then computes its factorial. Do this by reading the simulator user's manual, as well as Appendix A in the text, to figure out how to make the appropriate syscall. Next, modify the program to continue prompting the user for values of N and computing their factorials. Exit the program when the user enters a negative number.

Compilers: C-- Programming

The Cebollita toolkit provides a compiler for a language we call C--, which is roughly a subset of C. The compiler translates C-- programs into semantically equivalent assembler programs. The .s files can then be manipulated to produce executables in the same way that you worked with fact.s above.

Below is the C-- version of the factorial program. (It can be downloaded from here.) (Technically, this C-- program is a little different from fact.s because it doesn't do a Halt - it does something similar, though.) 

main() {
  int N = 9;
  int result = 1;
  while (N != 0) {
    result = result * N;
    N = N - 1;
  }
  printString("The factorial is: ");
  printInt(result);
}
  1. Copy hw2.c to your directory.

  2. You'll need a different prologue for this program. Copy C:\cebollita\apps\prologues\prologue-os.o to your directory. (The Cebollita simulator provides "the OS" this prologue is intended to work with.)

  3. You'll also need a version of the "C-- standard runtime library," which provides functions like printString(). The one you want is C:\cebollita\apps\iolibs\iolib-os.o. Copy it to your directory.

  4. Compile hw2.c to get an assembler program, hw2.s:
    $ java comp.parser hw2.c   or   $ cebcc hw2.c

  5. Assemble hw2.s to produce hw2.o.

  6. Link the files prologue-os.o, hw2.o, and iolib-os.o to produce hw2.

  7. Run hw2. Hopefully, you'll get the same result as you did for fact.s.
Answer the following questions. How many cycles does it take? Why is it different than the number required by fact.s? How many load instructions are executed by the program? How many arithmetic instructions are executed?
Finally, modify the above C-- program in the same manner as you modified the assembly program (above). It should call the function readInt() to get an integer from the user. Here is some sample C-- program that shows how to use readInt(): 
main() {
  printString("Please enter a number: ");
  int x = readInt();
  if (x < 0) {
    printString("Your number is negative.\n");
  }
  else {
    printString("Your number is non-negative.\n");
  }
}
Contrast the tradeoffs between programming in C-- and assembly code. How long did it take you to make the respective modifications?