A Crash Course in C Programming
This example assumes that you know at least the fundamentals of the C programming language.If you are a computer engineer, you will use C regularly, and you should thoroughly understand a few features of C that you will use again and again and again and again. They are probably not the typical features that you were taught in your C programming class, since they are not needed to solve the Tower of Hanoi or do a quicksort.
They include the following:
Storage Allocation & Data Representation
You need to understand that there is this thing called memory that holds all of your variables. C allows you to declare data types, such as the following:
int a, b, c;
int *ip;
char str[] = "strlen 18, size 19";
char *cp;
int A[2] = { 5551212, 5551313 };
double f;
These data items are not simply floating around somewhere; they are stored in the machine's memory.
You refer to them with nice names such as str and cp, but the
machine does not know these names; they are constructions of the compiler and
are translated into numeric addresses for the sake of the machine.
For instance, if we are talking about a 32-bit machine and the data are placed in the same area of memory (sometimes strings go somewhere other than integer and floating-point data), the memory area would look a little like the following (the string str and the array A are the only data items initialized, so they are the only items containing any information):
<-- 32-bit quantity -->
-------------------------
| |
-------------------------
f: | |
-------------------------
| 5551313 |
-------------------------
A: | 5551212 |
-------------------------
cp: | |
-------------------------
| 1 | 9 | \0 | ? |
-------------------------
| i | z | e | |
-------------------------
| 8 | , | | s |
-------------------------
| e | n | | 1 |
-------------------------
str: | s | t | r | l |
-------------------------
ip: | |
-------------------------
c: | |
-------------------------
b: | |
-------------------------
a: | |
-------------------------
This example assumes that we will give locations in memory the following addresses:
<-- 32-bit quantity -->
-------------------------
| etc | etc | ... | ... |
-------------------------
| 8 | 9 | 10 | 11 |
-------------------------
| 4 | 5 | 6 | 7 |
-------------------------
| 0 | 1 | 2 | 3 |
-------------------------
So, the first three data items in memory (starting with item a)
are four-byte quantities interpreted as integers.
The compiler makes sure that the machine interprets the data correctly.
Therefore when we say:
a = b;this translates to:
copy four bytes, starting at memory location b, to memory location aWhen we say:
str[0] = str[7];this translates to:
copy one byte, starting at memory location str+7, to memory location str+0And when we say:
f = 3.14159this translates to:
place into memory location f an 8-byte quantity having the value 3.14159Note that the MACHINE does no such interpreting; if you told it to jump to address 0 (or whatever address at which we have loaded item a), it would interpret the data as an instruction. If you told it to load the data there and print it out as a string, it would treat the data as a bunch of characters. If you told it to perform floating-point operations on it, the machine would treat that data as a floating-point number. Nonetheless, our C compiler will keep all usage straight and will make sure that we only use the 4-byte data item at location a as an integer.
At memory location ip we have something slightly different. This piece of data is declared as a pointer to an integer. This means that the data item will be used to reference integers. It will not hold integer values itself; it will merely point to storage locations that hold integers.
The distinction is critical; we will get to it in detail in a moment. Let us suppose that both a and ip contain the value 8. Then the following lines of code do two different things:
a = 8; a = 4; ip = 8; *ip = 4;The first line places the value 8 into the location a, overwriting whatever was previously there. The second line places the value 4 into the location a, overwriting the value 8. The third line places the value 8 into the location ip, overwriting whatever was previously there. The fourth line de-references the pointer ip and says to the computer: place the value 4 into the integer referenced by ip. Since ip currently has the value 8, the computer places the value 4 at the location 8, which happens to be item c.
Since we have previously declared ip to be a pointer to an integer, the statement
*ip = 4;is legal. The statement
*a = 4;is not, because a is declared to be an integer, not a pointer.
The compiler is also smart enough to detect the problem with this:
*ip = 4.5;Ip is a pointer to an integer, not a pointer to a floating point number. Therefore, the assignment mixes types, and many compilers will refuse to interpret it -- they issue an error statement and quit.
The next item in the list is the character array str, which has been initialized to the value "strlen 18, size 19". The string-length of the character array is 18 bytes, but the amount of space that it occupies is 19 bytes; strings are null-terminated, so for every string there is an extra zero-byte at the end. The amount of space the compiler allocates to hold the string is actually 20 bytes -- a multiple of 4 (the word size). I will get to this in a moment.
Note that the first character in a string starts at the lowest memory address, and the string works its way upward in memory, not downward. We could use the character pointer cp to point at the data elements in this character array. Say we do the following:
cp = str; cp++; cp = cp + 1; *cp = '\0';The first line assigns location of str to the variable cp, therefore the value 16 gets put into the location marked cp. The next line increments cp, so the pointer gets the new value 17, and so points at the second element in str (the 't' character). The third line does the same, and cp points to the 'r' character. The fourth line does not change the value of cp; it changes the value of the thing that cp points to -- the 'r' character. At this point, we have changed the data in the string. We have placed a NULL character where the 'r' used to be. Memory now looks like the following:
starting addr <-- 32-bit quantity --> ------------------------- 52 | | ------------------------- 48 f: | | ------------------------- 44 | 5551313 | ------------------------- 40 A: | 5551212 | ------------------------- 36 cp: | 18 | ------------------------- 32 | 1 | 9 | \0 | ? | ------------------------- 28 | i | z | e | | ------------------------- 24 | 8 | , | | s | ------------------------- 20 | e | n | | 1 | ------------------------- 16 str: | s | t | \0 | l | ------------------------- 12 ip: | | ------------------------- 8 c: | | ------------------------- 4 b: | | ------------------------- 0 a: | | -------------------------If we were to do a strlen(str), we would get the value 2, because there are now only two bytes in the string before we hit a null-terminator. However, the rest of the string did not go away; it is still there, occupying space.
Speaking of the rest of the data sitting there, occupying space, what is the '?' character at memory location 35?
It is an unknown. The compiler typically allocates space in units of 4 bytes (the fundamental unit in the 32-bit machine: 32 bits). Since our string only required 19 bytes, we had a little space left over, and the compiler DID NOT want to start the next item (the character pointer) at an odd address. So the compiler wastes the space in between the end of the string and the beginning of the character pointer, hoping that you will never go looking for it, or accidentally use it. It might contain the value '\0' but it could just as well contain the value 'Z' or (more likely) something outside the ASCII range, like 129 or 231 or 17. You cannot count on this value, but you can generally count on the space being there.
char str1[] = "strlen 18, size 19"; char *str2 = "strlen 17, size 4";This appears in memory as the following:
-------------------------
str2: | | --------------> "strlen 17, size 4"
-------------------------
| 1 | 9 | \0 | ? |
-------------------------
| i | z | e | |
-------------------------
| 8 | , | | s |
-------------------------
| e | n | | 1 |
-------------------------
str1: | s | t | r | l |
-------------------------
The first string, str1, is a character array, and space is allocated for it.
When you declare an array you must explicitly state how large it is, or implicitly
state how large it is by giving it an initial value.
Note that the size will never change.
The second string, str2 is a pointer to a character and space is allocated for it, but the space allocated is enough to hold a pointer, not the entire array. The actual array contents (the string "strlen 17, size 4") is placed in an entirely different area of memory and the pointer str2 merely references the string. Note that if you ever do something like this:
str2 = str1;you will effectively lose the original contents of str2:
-------------------------
str2: | | ---| "strlen 17, size 4"
------------------------- |
| 1 | 9 | \0 | ? | |
------------------------- |
| i | z | e | | |
------------------------- |
| 8 | , | | s | |
------------------------- |
| e | n | | 1 | |
------------------------- |
str1: | s | t | r | l | |
------------------------- |
^ |
|-------------------------|
Str2 now points to the beginning of str1 and nothing
points to the string "strlen 17, size 4" anymore -- it is lost.
So -- try the following program. What does it do and why?
#include <stdio.h>
main()
{
int a;
char s1[] = "this is a very large string that should take up much space";
int b;
char *s2 = "another very large string that should take up much space";
int c;
printf("loc a: %d \n", &a);
printf("loc s1: %d \n", &s1);
printf("loc b: %d \n", &b);
printf("loc s2: %d \n", &s2);
printf("loc c: %d \n", &c);
}
End of diversion. After the character pointer comes an integer array A. It has two elements, 5551212 and 5551313. Let us look at a variant of earlier code:
ip = A; ip++; ip = ip + 1; *ip = 0;The first line points ip to the array A; at this point, the variable ip contains the value 40. The second line increments the pointer to the next integer, not the next byte. At this point, ip does not point to storage location 41; it points to storage location 44. Why? Because the compiler is smart enough to translate the following lines of C code differently:
char *cp=0; int *ip=0; cp++ => cp = cp + 1 ip++ => ip = ip + 4Similarly, double-precision floating point numbers (data type double) occupy 8 bytes of storage each, therefore we have the following:
double *dp=0; dp++ => dp = dp + 8Another thing: why does the following statement not assign a zero to the character that cp points to?
char *cp=0;The answer is that it is an initialization statement and as such initializes the variable (cp), not the value that the variable points to. So at initialization, the pointer points to memory location 0 (also referred to as NULL).
Back to the story-line. We have just incremented integer-pointer ip. At this point, ip does not point to storage location 41; it points to storage location 44. Let's say we increment it again. It now points to storage location 48 (which, by the way, is OUTSIDE of array A). We now assign 0 to the storage location referenced by pointer ip:
*ip = 0;This puts a zero into the first half of the double-precision floating-point number f (and would cause quite a bug).
starting addr <-- 32-bit quantity --> ------------------------- 52 | | ------------------------- 48 f: | 0 | ------------------------- 44 | 5551313 | ------------------------- 40 A: | 5551212 | ------------------------- 36 cp: | 18 | ------------------------- 32 | 1 | 9 | \0 | ? | ------------------------- 28 | i | z | e | | ------------------------- 24 | 8 | , | | s | ------------------------- 20 | e | n | | 1 | ------------------------- 16 str: | s | t | \0 | l | ------------------------- 12 ip: | 48 | ------------------------- 8 c: | | ------------------------- 4 b: | | ------------------------- 0 a: | | -------------------------This has gotten into the area of pointers, so we will move on and talk about pointers in more depth in a bit.
Registers vs. Memory
Now you know what your C variables look like as they are stored in memory. One question to ask is "how does the machine operate on my variables?" In a load-store machine (one in which you must explicitly bring a value from memory into a register before you may operate on it), you cannot directly do things like this:a = b + cwhere a, b, and c are memory locations.
You must instead move the values into registers, operate on them, and then WRITE THEM BACK to memory (if their value has changed). The above code would translate to the following RiSC assembly code:
lw 1, 0, b lw 2, 0, c add 1, 1, 2 sw 1, 0, aThe first two instructions load the values of variables b and c into registers 1 and 2. The third instruction adds the two values together. Note that since memory has not changed, none of the variables have changed. The fourth instruction changes memory (by writing a value out to memory location a) and therefore changes the variable.
How Functions Work
Functions in C work on the property of call-by-value, which means that if you send variables into a function, the values of those variables are copied into the local working-space of the function (its stack frame). The function does not have direct access to those variables. Suppose we have the following, where the function function manipulates its input in some way:
int a, b, c;
a = 1;
b = 2;
c = 3;
function(a, b, c);
/*
* function does the following:
* a++;
* b++;
* c++;
* return;
*/
printf("a=%d, b=%d, c=%d \n", a, b, c);
What happens in this program?
Even though the values of a, b, and c are overwritten inside the function, they
are only overwritten there; the function has its own work-area that is not visible
to the rest of the program, and similarly the rest of the program is not visible
to the function.
Therefore, any changes that the function makes are local only; the changes disappear
when the function returns.
When the printf runs, the values of a, b, and c are still 1, 2, and 3.
Now, there might be times when we want a function to be able to influence variables outside of its scope. For instance, say we want a function such as increment, which takes a set of integer values and increments all of them. The following program would not work:
int a, b, c; a = 1; b = 2; c = 3; increment(a, b, c);It would not work because the function increment only sees the values of the arguments; it does not have direct access to the variables themselves.
We can get around this by understanding how storage is allocated in C, and by using pointers. The C operator & means "address-of" ... when you attach it to a variable, the whole expression is interpreted by the compiler to be the address of the variable, NOT the value of the variable. This way, rather than sending values of variables into the increment function, we can send addresses, effectively telling the function where the real variables reside:
int a, b, c; a = 1; b = 2; c = 3; increment(&a, &b, &c);The increment function would NOT look like this:
void
increment(int a, int b, int c)
{
a = a + 1;
b = b + 1;
c = c + 1;
return;
}
This would not work because the function as written expects a, b, and c
to be integers, not pointers to integers.
The following would also NOT work:
void
increment(int *a, int *b, int *c)
{
a = a + 1;
b = b + 1;
c = c + 1;
return;
}
This fails because the increment statements effectively say "increment the value of a,
which is a pointer to an integer".
This merely re-directs each of the local pointers to point somewhere other than the variables
a, b, and c.
It would not affect anything outside the function.
However, this WOULD work:
void
increment(int *a, int *b, int *c)
{
*a = *a + 1;
*b = *b + 1;
*c = *c + 1;
return;
}
Why does this work?
Because the statements each effectively say "increment the thing that a is pointing to, which
is an integer".
The difference (a is declared as int *a):
int * | a => a is an int-pointer int | *a => *a is an int ... the one referenced by pointer aNote that whereas the following two do the same thing:
a = a + 1; a++;the following two DO NOT do the same thing:
*a = *a + 1; *a++;The problem arises because in the second group of C statements, we mix two operations in one expression. When we combine the de-reference operator (the * operator) with the increment operator (the ++ operator) we get unusual behavior. The first line:
*a = *a + 1;says to get the contents of the data item that a points to, add 1 to it, and write the value back to data item that a points to. The second line:
*a++;says to get the contents of the data item that a points to, and then increment the pointer a. The value that a points to is not changed: the pointer a is changed. If you want something with the semantics of the first C statement, I think the following would work:
(*a)++;The parentheses override the precedence-ordering of the operators.
Again, we have strayed a bit far into pointers. Moving on ...
Stack vs. Heap, or Automatic vs. Static Variables
When functions run, they are allocated temporary storage on the stack. This storage is effectively destroyed/consumed/garbage-collected as soon as the function stops running. Therefore the following is an error:
char *
readline()
{
char line[128];
gets(line)
return line;
}
It is an error because all of the variables belonging to a function
(except those declared "static" -- I will get to that in a moment) are
destroyed as soon as the function exits.
The big problem is that they are not destroyed immediately, so your
program may run just fine for a little while before it goes haywire.
This makes debugging a pain.
Anyway -- the variables declared inside a function (i.e. all those that are not global) are allocated on the stack, as part of the function's stack frame. This stack frame is wiped out once the function exits. All of the variables go away when the stack frame is wiped out. They are called "automatic" variables because they are automatically created and destroyed by simply calling and returning from the function. Therefore, line gets destroyed, and you will get strange behavior if your program is pointing to where line used to be -- for example, if you had said something like the following:
char *cp = readline();At this point, cp is not valid because the program readline has exited, taking with it all of its automatic variables, including line, which is what the variable cp is now pointing at. It is pointing at some random location on the stack, which might get overwritten at any moment (for example, as soon as another function executes).
How to get around this?
There are two ways around this: GLOBAL variables and STATIC variables. GLOBALS are simply variables that are (for example) declared at the top of the program file, outside of any surrounding block (set of curly-braces). These are variables that are visible to every single function in the program; remember last section when I said that there is no way to change variables that are outside a function from within the function? If the variable is a global (and if the function does not locally declare one of the same name), then the function CAN change it.
For example, the following is a program where the function setA can see outside its own scope.
int A = 0;
void setA(value)
int value;
{
A = value;
}
main()
{
setA( 0xbabacafe );
}
The variable A is global, and the function setA can access it.
However, the following example shadows the global variable A:
int A = 0;
void setA(value)
int value;
{
int A = value;
}
main()
{
setA( 0xbabacafe );
}
Here, there is a locally-defined variable called A.
This local variable takes precedence over the global variable;
the net result is that setA cannot reference the global variable.
And the value that it saves in the integer A is lost as soon as
the function exits.
The other way to avoid having your variables destroyed is to explicitly allocate space for them. If you precede a variable declaration by the word "static" then the variable will NOT be placed on the stack but will instead be placed on the heap with all of the global variables. The advantage is that only the function in which the variable was declared has access to it.
int A = 0;
void setA(value)
int value;
{
static int A = value;
}
main()
{
setA( 0xbabacafe );
A = 0xbabacafe;
A++;
}
There are two variables named "A" ... one is global, one is local
to the function setA, but the one local to setA is not destroyed
when the function stops executing.
The A = 0xbabacafe assignment statement in the main() function does
NOT reproduce work done by the function setA.
At the point it executes, the global A still has the value 0, and the
variable A that is local to setA has the value 0xbabacafe.
Note that this change is permanent and the storage location is not
destroyed at the end of function setA, because A is declared as static.
The next time setA is called, the local variable A will still have the
value 0xbabacafe, and the global variable A will have the value 0xbabacaff.
This feature is good for things like keeping a count of how many times a function is called; in particular, you will often want to do something different the first time a function is called, as opposed to the second, third, or tenth time the function is called. You can do this by the following:
void
function()
{
static int count=0;
count++;
if (count == 1) {
/* do initialization steps */
}
/* on with the code */
}
The initialization of the variable count is only done once,
not on every execution of the function (as would be the case if the word
static were not there).
Therefore on the first execution, the value is zero, incremented to one.
On the second execution of the function, the value of count is one
and is incremented to two, etc.
Arrays, Structures, and Pointers
C has these things called arrays, which we have been discussing for a bit now; they are groups of similar data items, and the first item is item-0, the second is item-1, etc. The C compiler is smart enough to address the items in the array correctly, therefore the following is actually a bit more complex than it first appears.char C[10]; int I[10]; double F[10]; char c = C[3]; int i = I[3]; double f = F[3];We are simply grabbing data out of the arrays, and we are grabbing the same element-number from each array (item-3, the fourth item). A character is 1 byte wide, an int (let us suppose) is 4 bytes, and a double-precision floating-point number is 8 bytes wide. Therefore these three assignment statements result in the following low-level operations:
c <- MEM[ C + 3 ] i <- MEM[ I + 3 * 4 ] f <- MEM[ F + 3 * 8 ]One nice thing about arrays in C is that it is relatively simple to create multi-dimensional arrays, which is very important if you want arrays of strings (each of which is a character array). So, if you want to create an array of strings, you can do the following:
#define MAX_STRLEN 15 char labelarray[128][MAX_STRLEN+1];This creates an array containing 128 strings, each of which has 16 bytes in it. You can easily use this as follows:
int i;
for (i=0; i<MAX_LABELS; i++) {
char *label = get_string();
strncpy(labelarray[i], label, MAX_STRLEN);
}
This is obviously a contrived example, but it illustrates the point; you can
get strings, even from automatic storage, and copy them into global storage
locations to keep the data for the duration of the program.
If you do not copy the data somewhere, it is likely to disappear on you.
For instance, the function get_string likely has an internal buffer that it reads
data into (the array should be declated as static to avoid it being wiped out at function exit).
Every time the function is called, presumably the function gets a new string from
the input data source, and the previous string is wiped out.
The above code segment would "save" all interesting lines into labelarray,
so that when you are done reading from the input-source, the lines are still around.
Similar to arrays are structures, designated by the keyword struct. These are declared like this:
struct student {
char fname[32];
char lname[32];
int height;
int weight;
float gpa;
};
A structure is like an array in that it is a complex aggregate of data
types; the primary difference is that it is a set of (potentially)
different data types, whereas an array is a set of identical data types.
Here is how you refer to the elements of an array:
int array[] = { 5551212, 5551313 };
int a = array[0]; /* refers to the first item in the array: 5551212 */
int b = array[1]; /* refers to the second item in the array: 5551313 */
int c = array[2]; /* indexes beyond the end of the array: a bug */
Since each item in the array has the same size (they are required to be
identical data types), it is simple to find different elements.
A structure, however, is composed of (potentially) different data types
with (potentially) different sizes, so it is much more difficult to determine
how to find things in it.
Also, if one were to use the same sort of indexing method as in arrays, it
would lead to things like the following (note this is NOT correct C syntax):
struct student {
char fname[32];
char lname[32];
int height;
int weight;
float gpa;
} s;
strcpy(s[0], "Bob");
strcpy(s[1], "Jones");
s[3] = 70;
s[4] = 160;
s[5] = 3.675;
This is not very useful; it is difficult to know exactly what is going on.
Instead of this, C uses a much better method for locating fields
within structures:
struct student {
char fname[32];
char lname[32];
int height;
int weight;
float gpa;
} s;
strcpy(s.fname, "Bob");
strcpy(s.lname, "Jones");
s.height = 70;
s.weight = 160;
s.gpa = 3.675;
This is a much better method, as it is simple to tell what data is going where.
Here comes the point of pointers. When you wish to pass an aggregate data type into a function (i.e. pass an array or a structure into a function), you typically do not want to copy the ENTIRE array or structure into the work-area of the function. Remember a few sections back when we saw that functions had their own work-areas, and arguments are passed to functions via call-by-value? This means that when you pass an argument to a function, the compiler sets it up so that the data item is copied into the work-area (the stack frame) of the function.
What if one of the arguments is a 1,000,000-entry integer array? What if one of the arguments is a struct with 10,000 different data fields within it, totalling many dozens of kilobytes?
In the cases of aggregate data types, we typically DO NOT want to use call-by-value when invoking functions, because doing so would entail copying many kilobytes or perhaps even megabytes of data, much of which might not be needed or even used. Instead of copying all of that data, we typically leave the data where it is and tell the function where to find the data structure.
We use pointers.
Remember the & (address-of) operator? This is where it comes in very handy. If you have a function print_gpa that takes as an argument a structure, you have two choices. First, you can elect to copy the entire struct into print_gpa:
struct student {
char fname[32];
char lname[32];
int height;
int weight;
float gpa;
} s;
int print_gpa(s)
struct student s;
{
printf("%s, %s: GPA %f\n", s.lname, s.fname, s.gpa);
}
main()
{
struct student stdnt;
strcpy(stdnt.fname, "Bob");
strcpy(stdnt.lname, "Jones");
stdnt.height = 70;
stdnt.weight = 160;
stdnt.gpa = 3.675;
print_gpa(stdnt);
}
This would copy everything from the variable stdnt into the stack frame
of the function print_gpa before executing the function.
Of course, some compilers do not allow this, or they change it to something
else under your nose.
At any rate, here is the alternative, which is used MUCH more frequently:
int initialize(s, first, last, ht, wt, gpa)
struct student *s;
char *first, *last;
int ht, wt;
float gpa;
{
strcpy(s->fname, first);
strcpy(s->lname, last);
s->height = ht;
s->weight = wt;
s->gpa = gpa;
return;
}
int print_gpa(s)
struct student *s;
{
printf("%s, %s: GPA %f\n", s->lname, s->fname, s->gpa);
}
main()
{
struct student stdnt;
initialize(&stdnt, "Bob", "Jones", 70, 160, 3.675);
print_gpa(&stdnt);
}
Okay, what is going on here?
Rather than send copies of the actual student record around, we sent a pointer
to the student record (the struct student stdnt).
This allows the two functions initialize and print_gpa to access
the true data, not just a copy of it.
While this is not so important for the print_gpa function (it is only reading the data),
this is very important for the initialize function, since its changes would otherwise
not be seen.
So what are all the "->" things? When you de-reference a pointer (when you place an asterisk in front of a variable that is declared to be a pointer to a certain data type), the resulting term becomes equivalent to the thing pointed to. Therefore the terms stdnt and (*s) are equivalent:
struct student stdnt; /* allocates space for a structure */ struct student s = &stdnt; /* allocates space for a 4-byte pointer and initializes it to point at stdnt */ strcpy(stdnt.fname, "Brockton"); strcpy((*s).lname, "Veendorp");When you de-reference pointer s, the resulting term is equivalent to the thing pointed to: stdnt. Therefore the last two lines initialize values in the same structure. Note that the parentheses surrounding the *s combination are necessary, due to precedence of operators in C. So a short-hand notation was developed, because typing so many parentheses and asterisks is painful to do and painful to look at:
(*s).fname is equivalent to s->fname (*s).lname is equivalent to s->lname (*s).height is equivalent to s->height etc ...Much nicer, huh?
There are many really good uses for pointers to structures, especially in the area of linked lists, but I will not talk about them here because the area is pretty huge and you will probably not require dynamic data structures to build the types of things you will build in this class. Ask me about it at office hours if you want.
However, I WILL talk about the use of pointers when you have arrays of structures. This is very very useful. Say you have an array of structures, each of which represents a particular label-address mapping:
struct label {
char label[ MAX_LABEL_LEN + 1 ];
int address;
} labelarray[ MAX_LABELS ];
This is pretty simple; what we have is a structure that pairs a string
to hold the label with an integer to hold the address.
Suppose that this declaration is global; i.e. it is found near the top of
the file, before the functions get defined.
Then the following is a perfectly good label_lookup function:
int
label_lookup(label, max)
char *label;
int max;
{
struct label *lp = labelarray;
/* with some compilers you may need to say:
struct label *lp = &labelarray[0]; */
while (max-- > 0) {
if (strcmp(label, lp->label) == 0) {
return lp->address;
}
lp++;
}
return -1;
}
The function has a label pointer lp that it uses to sweep through the
labelarray.
For each element in the array, we compare the desired label (label, the input
argument to the function) to the value found in the structure (lp->label).
If the two are equal (if strcmp returns zero), we return the corresponding
address value.
If we get to the end (by exceeding max) without finding the desired label,
we return negative one--a value that no valid label should have; this indicates to
the function's callee that the label has not been found.
Pointers to Pointers
Sometimes you will see things like char **arg1, in which there are pointers to pointers. Remember the earlier example of passing pointers to variables into functions so that the functions could modify the variables directly? For instance, the initialize function:
int initialize(s, first, last, ht, wt, gpa)
struct student *s;
char *first, *last;
int ht, wt;
float gpa;
{
strcpy(s->fname, first);
strcpy(s->lname, last);
s->height = ht;
s->weight = wt;
s->gpa = gpa;
return;
}
This function takes as input a pointer to a structure and a whole bunch
of values with which we are to initialize the structure.
Since the function is given a pointer to the structure (rather than a
copy of the structure), it can make changes directly to the structure.
This extends beyond structures. For example, it is very useful for initializing pointers. Say, for example, that we have the following pointers: label, opcode, arg1, arg2, and arg3. We also have a buffer full of data that contains the following assembly-code line:
loop: lw 1, 2, FooWe want to give the pointer label a pointer to the string "loop:". We want to give the pointer opcode a pointer to the string "lw". We want to give the pointer arg1 a pointer to the string "1". Et cetera. One obvious way to do this is to create an equivalent function to the previous initialize--we'll call it parse_and_assign_values:
void
parse_and_assign_values(input, lab_ptr, op_ptr, a1_ptr, a2_ptr, a3_ptr)
char *input;
char **lab_ptr, **op_ptr, **a1_ptr, **a2_ptr, **a3_ptr;
{
char *cp;
cp = get_first_field_of_input(input);
if (cp == NULL) {
*lab_ptr = NULL;
} else {
*lab_ptr = cp;
}
cp = get_next_field_of_input(input);
if (cp == NULL) {
*op_ptr = NULL;
} else {
*op_ptr = cp;
}
cp = get_next_field_of_input(input);
if (cp == NULL) {
*a1_ptr = NULL;
} else {
*a1_ptr = cp;
}
etc ...
}
main()
{
char *label;
char *opcode;
char *arg1;
char *arg2;
char *arg3;
char line[128];
gets(line);
parse_and_assign_values(line, &label, &opcode, &arg1, &arg2, &arg3);
/* now, each of the char pointers points to NULL or to a valid string */
}
This example uses these pointer-pointer data types.
In our main function, we have character pointers that we use to manipulate strings.
At times, we will want to call a function that initializes these pointers.
To allow the function direct access to the pointers, we have to give the function
the address of the pointers, not a copy of the pointers.
Therefore, the function sees arguments that are addresses of pointers, or
pointers to pointers.
The notation in C is **.
One obvious question: what does the function get_next_field_of_input look like? We will get to that in the next section on string manipulation.
String Manipulation
In the previous example, we have a buffer called line that contained a line from an assembly-code program that looks like this:loop: lw 1, 2, FooThis happens to be a string containing the following data (underneath the data, I have shown the index of each byte within the string):
------------------------------------------------------------------------------- | l | o | o | p | : | \t | l | w | | 1 | , | | 2 | , | | F | o | o | \0 | ------------------------------------------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18The first character in the buffer (another word for data array, in this example a character array) is the character 'l', the second character is 'o', etc. The very last character is the NULL character, '\0'. And spaced between each of the components of the line of assembly code are separating tabs [\t], commas [,], and/or spaces [ ].
Here is what we could do to pull the data out of the buffer (note it is a little simplified for the sake of readability):
1. if the first character is '\t' then LABEL is NULL, advance to next character
otherwise, LABEL = this-address, move to next space (' '), replace it with '\0',
and replace every following space with '\0' until we hit a non-space character
2. OPCODE = this-address, move to next space (' '), replace with '\0',
and replace every following space with '\0' until we hit a non-space character
3. ARG1 = this-address, move to next comma (',') or space (' '), replace with '\0',
and replace every following space with '\0' until we hit a non-space character
4. ARG2 = this-address, move to next comma (',') or space (' '), replace with '\0',
and replace every following space with '\0' until we hit a non-space character
4. ARG3 = this-address, move to next comma (',') or space (' '), replace with '\0',
and replace every following space with '\0' until we hit a non-space character
Here is a graphical depiction of what happens.
This is how we start out:
------------------------------------------------------------------------------- | l | o | o | p | : | \t | l | w | | 1 | , | | 2 | , | | F | o | o | \0 | ------------------------------------------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 current-char: line[0] LABEL = NULL OPCODE = NULL ARG1 = NULL ARG2 = NULL ARG3 = NULLStep 1 looks to see if there is a valid LABEL field. If the first character is a TAB, then there is no LABEL field. In this case, there is a valid character (the 'l' character), therefore there is a valid LABEL field (loop). So we point LABEL at location 0 and terminate the string "loop:" with a NULL character:
------------------------------------------------------------------------------- | l | o | o | p | : | \0 | l | w | | 1 | , | | 2 | , | | F | o | o | \0 | ------------------------------------------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 current-char: line[6] LABEL = 0 OPCODE = NULL ARG1 = NULL ARG2 = NULL ARG3 = NULLNow we are looking at location 6, LABEL has been assigned, and since the character in position 5 has been replaced with a NULL terminator (the '\0' character), LABEL points to a string that has 5 characters. In Step 2, we do the same kind of thing: we test the first character to see if it is the end of the line, and we set OPCODE to NULL if it is. Assuming it is not, we set OPCODE to current-char and find the next SPACE in line, setting it to '\0'. This gives us the following:
-------------------------------------------------------------------------------- | l | o | o | p | : | \0 | l | w | \0 | 1 | , | | 2 | , | | F | o | o | \0 | -------------------------------------------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 current-char: line[9] LABEL = 0 OPCODE = 6 ARG1 = NULL ARG2 = NULL ARG3 = NULLNow, OPCODE points to location 6, which is the start of the string "lw". It is a string with only two characters, since we just replaced the SPACE character in position 8 with a NULL-terminator.
And the process continues until we have the following:
------------------------------------------------------------------------------------ | l | o | o | p | : | \0 | l | w | \0 | 1 | \0 | \0 | 2 | \0 | \0 | F | o | o | \0 | ------------------------------------------------------------------------------------ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 current-char: line[19] LABEL = 0 OPCODE = 6 ARG1 = 9 ARG2 = 12 ARG3 = 15Now, this would make pretty ugly code. Luckily, you don't have to do this kind of thing; it has already been done for you. Check out the library function strtok--it was written to do exactly this type of string parsing. I will not explain how it is used (you can get that from any C manual), but the way it works is VERY SIMILAR to what I have described here.
Arguments to Programs
Okay, this section will be very short, since I have been typing all day and my hands are tired. How do you get things into programs? When you type the following at the UNIX command line:wam.umd.edu: assembler mult.s mult.exehow do the strings mult.s and mult.exe get into the program? Very simple. The function main in your program is really a function and it really has arguments. They are called argc and argv (there is one more, but I won't discuss that right now). Here is how they are declared:
main(argc, argv)
int argc;
char *argv[];
{
}
Argc is the number of arguments on the command-line (including the name of
the program itself).
Therefore, in this example, argc would be 3.
Argv is an array of character pointers.
It always has at least one item (argv[0]), because the first item (argv[0]) is always
the name of the program (therefore argc is always at least 1).
In this example,
argv[0] refers to the string "assembler" argv[1] refers to the string "mult.s" argv[2] refers to the string "mult.exe" argv[3] does not exist; if you try to reference it, you get garbageVoila.
Bitfields and Bitmasks
In building your assembler and your simulator for Project 1 (and later projects as well), you will often need to look at only a portion of an integer -- to pull out a selected group of bits, ignoring all the rest. For instance, if you want a 3-bit field in an instruction that identifies a register number, you will not want the surrounding bits.This is done using bitmasks, or just masks. A mask is a field of bits that corresponds to the number of bits that you want to pull out of the integer. You shift either the instruction or the mask over to the appropriate place and perform an and to extract the desired bits; I will demonstrate this in a moment.
First, here is a table that you can use; it shows a bit pattern and the corresponding hexadecimal number that you would use to create the mask.
#Bits Bit Pattern Hexadecimal Number 1 1 0x1 2 11 0x3 3 111 0x7 4 1111 0xf 5 11111 0x1f 6 111111 0x3f 7 1111111 0x7f 8 11111111 0xff 9 111111111 0x1ff 10 1111111111 0x3ff 11 11111111111 0x7ff 12 111111111111 0xfff... and so on.
How do you use this? Very simple. If you want to extract a field from an integer called, for instance, "instruction", and place it into the variable "field", you would do the following. Say that you want a three-bit field from bit 12 to bit 14, assuming that the first bit is bit 0.
field = (instruction >> 12) & 0x7;This shifts the bits in "instruction" down by 12 bits, then uses a mask to zero out everything but the bits in the lowest three places (bits 0-2). After the shift, bits 12-14 are in locations 0-2, so this is exactly what we want.
Bits 8-11:
field = (instruction >> 8) & 0xf;
Bits 2-7:
field = (instruction >> 2) & 0x3f;
Bits 13-15:
field = (instruction >> 13) & 0x7;Now, suppose that you want to insert a field into the integer called "instruction". Let's say that you have an opcode value or a register value or something like that held in the variable "field" and you want to put it into the variable "instruction". Say that it is a 3-bit quantity and you want it in bits 10-12.
instruction = (field & 0x7) << 10;The and ensures that "field" contains a 3-bit number (by zeroing out any other bits), and the shift puts the three-bit field into place. The problem is that the variable "instruction" now contains only the three-bit field now in bits 10-12. In the general case, we would like to construct instructions out of many fields. Here is how.
Suppose we have a 3-bit opcode stored in the variable op, we have a 3-bit register stored in the variable r1, and we have another 3-bit register stored in the variable r2. Say we want them (respectively) in bits 15-13, 12-10, and 9-7. We would build up the instruction as follows:
instruction = ((op & 0x7) << 13) | ((r1 & 0x7) << 10) | ((r2 & 0x7) << 7);The ands ensure that each variable is only three bits wide, by masking out all other bits. The left-shifts put the values into place, according to the desired location. Since there is no overlap between the fields (we have ensured this by masking out any possible extra bits), the ors simply concatenate the fields together.
Hope this helps,
Prof. Jacob