Computer Science 220
Assembly Language & Computer Architecture

Fall 2011, Siena College

Home     Syllabus     Schedule

For this lab assignment, you will learn how to write and run a simple C program, and then write a few more programs to try out some of its bitwise operators.

You may work alone or with a partner on this lab.

The first few sections of this lab handout contains some examples that you should work through during lab. Once you have completed those, you can move on to the C programming assignments. You may wish to solve them using your favorite programming language and convert them to C later to separate the problem solving from the learning curve of a new programming language.

A Very Simple C Program

We will begin by seeing how to compile and run a very simple C program (hello.c) in a Unix environment.

See Example:
~jteresco/shared/cs220/examples/hello

We will assume that we are working at the Unix command line. If you have not already done so, you will need to boot into Linux and open a Terminal window.

For you to run this, you will want to copy the example to your own directory. But first, we'll create a directory for it:

mkdir ~/hello

This creates a new directory (folder) in your home directory (indicated by the ~) called hello.

To copy the example from the shared area to your new directory:

cp ~jteresco/shared/cs220/examples/hello/hello.c ~/hello

We now change directory to the copy in your own directory:

cd ~/hello

And compile and run it:

gcc hello.c
./a.out

Things to note from this simple example:

• We run a program named gcc, which is the C compiler in the free GNU Compiler Collection.
• gcc, in its simplest form, can be used to compile a C program in a single file:

  gcc hello.c
  

  In this case, we're asking gcc to compile a C program found in the file hello.c.

  Since we didn't specify what to call the executable program produced, gcc produces a file a.out. The name is a.out for historical reasons.

• When we want to run a program located in our current directory in a Unix shell, we type its name.
  • For example, when we wanted to run gcc, we typed its name, and the Unix shell found a program on the system in a file named gcc.
  • How does it know where to find it? The shell searches for programs in a sequence of directories known as the search path. Try: env.
  • So if we want to run a.out, we should be able to type its name. But our current directory, always referred to in a Unix shell by ".", is not in the search path. We need to specify the "." as part of the command to run:

    ./a.out
    

• Of course, we probably don't want to compile up a bunch of programs all named a.out, so we usually ask gcc to put its output in a file named as one of the parameters to gcc:

  gcc -o hello hello.c
  

  Here, the executable file produced is called hello.

• And in the program itself, let's make sure we understand everything:
  • At the top of the file, we have a big comment describing what the program does, who wrote it, and when. Your programs should have something similar in each C file.
  • We are going to use a C library function called printf to print a message to the screen. Before we can use this function, we need to tell the C compiler about it. For C library functions, the needed information is provided in header files, which usually end in .h. In this case, we need to include stdio.h. Why? See man 3 printf. (More on the Unix manual later.)
  • A C program starts its execution by calling the function main. Any command-line parameters are provided to main through the first two arguments to main, traditionally declared as argc, the number of command-line parameters (including the name of the program itself), and argv, an array of pointers to character strings, each of which represents one of the command-line parameters. In this case, we don't use them, but there they are.
  • Our call to printf results in the string passed as a parameter to be printed to the screen. The \n results in a new line.
  • Our main function returns an int value. A value of 0 returned from main generally indicates a successful execution, while a non-zero return indicates an error condition. So we return a 0.
• Notes for Java programmers:
  • Good news: much of the syntax of Java was borrowed from C, so a lot of things will look familiar.
  • There are no classes and methods, just functions, which can be called at any time. Any information a function needs to do its job must be provided by its parameters or exist in global variables - variable declared outside of every function and which are accessible from all functions.

A Bit More Complex Example

We next consider an unnecessarily complicated C program that computes the greatest common denominator of two integer values.

See Example:
~jteresco/shared/cs220/examples/gcd-c

Lots of things to notice here:

• We have four files:
  • gcd.c: the implementation of the gcd function
  • gcd.h: a header file with a prototype for the gcd function
  • gcdmain.c: a main program that determines the input numbers, computes the GCD, and prints the answer, and
  • Makefile: a "make file" that gives a set of rules for compiling these files into the executable program gcdmain.

  When executing, functions from both gcdmain.c (main) and gcd.c (gcd) will be used. Both of these are included in our executable file gcdmain.

• Start with gcd.c:
  • This is a very simple recursive function to compute the greatest common denominator using the Euclidean Algorithm.
  • There is no main function here, so if we try to compile this by itself as we did with hello.c, we will get an error.
  • Instead, we have gcc use "compile only" mode to generate an object file gcd.o from gcd.c:

    gcc -c gcd.c
    

    gcd.o is a compiled version of gcd.c, but it cannot be executed.

    C (and many other languages) require a two steps for source code to be converted into an executable. The first step compiles source code into object code, the second takes a collection of object code files and links together the references in those files into an executable file. (There's much more to discuss here, but this should suffice for now.)

• Next up, gcd.h:
  • Much like stdio.h tells the compiler what it needs to know about printf (among other things), we have gcd.h to tell other C functions what they need to know about the function gcd. Namely, that it's a function that takes two ints as parameters and returns an int.
  • Any C file that contains a function that calls gcd should #include "gcd.h".
• The driver program, gcdmain.c:
  • We include several header files to tell the compiler what it needs to know about C library functions (and our gcd function) that are called by functions defined here.
  • This is where our main function is defined.
  • We can define local variables to functions, just like local variables in a Java method.
  • In this case, we look at the arguments to main that provide the command-line parameters of our program: argc and argv.
  • If we have fewer than three command-line parameters, including the program name itself (which is always there), we prompt the user for two numbers (with printf), then read in two numbers from the terminal with scanf.
  • This is a good time to mention C strings. There is no "string" data type in C. Strings are just null-terminated arrays of char. Unlike Java, arrays do not come equipped with any way to tell how large they are (like Java's .length) so the only way we can tell the length of a C string is to follow it along until we get to the null terminator, which is character '\0'.
  • scanf is a very strange thing. It will make a bit more sense when you are more familiar with printf, but for now we can summarize what we see there as "read in two integer values (represented by the %d's in the format string), and put them into the place pointed at by the address of a and the address of b, then return the number of values that matched the input with the correct format." Right. And you thought I/O was a pain in Java.
  • The scanf call forces us to think a bit about pointers, which are the key to understanding so much of how C works. scanf's parameters after the format string are always a list of pointers to a place in memory where there is room to put the values being read in. In this case, we want the two int values to end up in the local variables a and b, so we have to take the address of those variables with the & operator. Don't worry, it will make better sense when you see more examples.
  • Next, we check to make sure that the input to scanf did, in fact, represent two int values. If not, we print an error message and exit. Otherwise, we continue.
  • Some things to notice in the error condition:
    • We use fprintf instead of printf. This is because we want to give this output special significance. Rather than sending it to the standard output, which is what printf would do, we send it to standard error, by using fprintf and specifying stderr as the first parameter. Java supports the same idea: use System.err instead of System.out.
    • Other than that, it works just like printf. We give it a format string. In this case, it includes one specifier, a %s, which means to expect an additional parameter which is a character string (well, really a pointer to a null-terminated array of char). Here, the string is argv[0], the first command-line parameter, which is always the name of the program. This labels the error message with the program name.
    • Once we have detected the error, we don't want to continue, so we call the exit function with an error code of 1 to terminate execution. We could also use the call return 1;.
  • In the case where at least two command-line parameters were provided, we try to convert them (argv[1] and argv[2]) to integer values. This is done with the overly complicated strtol function, which we use, then check error conditions.
    • The man page for strtol tells us we need to include two additional header files, stdlib.h and limits.h.
    • It also tells us about the parameters to strtol, which are the string which we would like to convert to a number, a pointer into the string at the point beyond which we matched a number (which we don't care about, so we pass in NULL), and the base to use for the conversion. We also see that the number is the return value.
    • Error checking for strtol is messy - we need to check the variable errno, defined in errno.h, to see if an error condition was encountered. If so, errno will be a non-zero value and we print an error message and exit.
    • Note that the error check here has two %s's, so we have two additional parameters to fprintf, both pointers to strings.
  • Finally, we're ready to check that the numbers entered are non-negative, and if so, we print out the answer (obtained by the gcd function call inside of a printf parameter).
  • This file includes a main function, so we might think we could compile it to an executable as we did with hello.c, but if we try, we'll find that it doesn't know how to find the gcd function. Again, we'll have to compile but not link:

    gcc -c gcdmain.c
    

    This produces the object file gcdmain.o. We need to link together our two object files, which, together, have the function definitions we need:

    gcc -o gcdmain gcdmain.o gcd.o
    

    This gives us gcdmain, which we can run.

• The Makefile contains rules to generate a sequence of calls to gcc that will correctly compile and link the gcdmain executable.

The bad news: that was a lot of trouble just to write a simple program.

The good news: you will have examples to look at and you can ask a lot of questions.

C Programming Assignments

The main part of the lab is to write two C programs. The first should be fairly straightforward, but the second will require some more careful thought. For both, you should try to come up with an elegant and simple solution. Avoid expensive operations like multiplication, division, and nested loops. The pow function, which can be used to compute powers, is not permitted. Keep in mind that bitwise operations are the focus of this assignment.

If you're having trouble, ask questions! Make sure that your code is well written and documented. I encourage, but will not require, that you develop them using Unix. You are, however, required to make sure your programs run properly on the Linux systems in Roger Bacon 306 before you submit them.

1. Write a C program counttheones.c that takes a signed int value and prints out the number of bits in the number's internal representation that have the value 1. Your program may prompt for the input value of accept it on the command line. You may assume the value on the input is an integer.
2. As a college student, you probably find yourself dining at restaurants that feature some sort of "value menu". Also as a college student, you want to get as much food from those value menus as your budget will allow. But even a poor college student needs some variety, so your goal might be to try as many combinations of items from the value menu as your budget will allow, but without repeating any one item on a given visit.

   For example, suppose the menu features burgers for $2, chicken strips for $3, fries for $1, and soft drinks for $1, and your budget allows you $5 per meal. Of the 16 possible combinations of 0 or 1 of each item that form the possible meals with this menu, on your budget you can afford 13 (all but burger/chicken/fries, burger/chicken/drink, and all 4).

   Write a C program valuemenu.c that takes as command-line parameters one int specifying your budget followed by anywhere from 1 to 26 additional ints specifying the price of each menu item. Your program should print its inputs, labelling the items A, B, C, etc. It should then print the number of possible combinations. Next, it should print each possible combination, listing the selected items and their costs, followed by the total cost of that meal and whether or not it is under budget. At the end, print the number of affordable combinations.

Submission and Evaluation

This lab is graded out of 25 points.

By the start of your next lab meeting, submit documented source code for your two programs. All necessary files should be submitted by email to jteresco AT siena.edu.