C Module 1: Pointers, arrays, malloc

Create your repository: https://classroom.github.com/a/onrkDI8h
Then clone the repository into your CodeAnywhere container using git clone YOUR_URL
(Click the green "Clone or Download" button to find your repository's URL).
Create all the exercise files inside your repository directory and then add, commit, and push them to GitHub when you are finished.

Due: Tuesday 9/11 at 11:59PM, see submission instructions.

In-class worksheet - Bring this to class in week 3

Updated 9/25: Added section on our heap model.

Objectives

The goal of this module is:

To practice building C programs using the Linux command line.
To introduce pointers and memory in C.
To work with arrays and strings, with an understanding of how they work in memory.

Important: to reduce clutter in the modules, our code examples will not show the "include's". Be sure to include the four in every program you write (you can copy/paste this):

// Put these at the top of every C file:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main ()
{
  printf("hello world!\n");
}

Compiling in Linux/Unix

We will use CodeAnywhere to provide a Linux environment. Be sure you have logged in with your GitHub account and created a container as detailed in Lab 1 (at least up to the Command Line Basics section).

Compiling and executing on Unix:

The program above is a plain text file, as in any programming language.
Use CodeAnywhere to create a file named helloworld.c in your repository directory (you may need to "Refresh" to file hiearchy to see the folder).
The file extension for any program you write should be .c.

To compile, open a terminal and navigate to your repository directory

  cd c-1    # then hit TAB to autocomplete the folder name
  gcc -o helloworld -ansi helloworld.c

This produces an executable called helloworld which can be executed as:
```
  ./helloworld
```

Some compiling options:

With the same contents, we could re-name the file to whatever.c and compile as:
```
gcc -o helloworld whatever.c
```
(Note the case-sensitivity).
We could also create an executable with any name:
```
gcc -o strangeThing helloworld.c
```
(The -o option lets you specify the name of the executable.)
The simplest form on invoking the gcc C compiler is:
```
gcc helloworld.c
```
This produces an executable called a.out (by tradition).

Versions of C, and running in a debugger

C has changed (slowly) over the years since the original:

The original is called K&R C (for Kernighan & Ritchie, the creators of C). There is code lying around that, if you want to use, you must set compiler options accordingly.
Later, as C evolved, other versions came along: ANSI C, C-99 and now the latest: C11 (for 2011).

You can set a compiler option (called a switch) to ask the compiler to check your code against a specific version:

The -ansi option asks the compiler to enforce the current ANSI standard.
```
    gcc -o helloworld -ansi helloworld.c
```
You can choose to compile with a specific (e.g., ANSI 1989) standard as follows:
```
  gcc -o helloworld -std=c99 helloworld.c
```

Before we can proceed we need to install the C debugger onto our CodeAnywhere container. To do that, run these commands:

# Update installation packages and install C debugger 
sudo apt-get update
sudo apt-get install gdb

When prompted, press y to install the debugger software.

Running the program inside a debugger:

First, compile with with the debug option:
```
    gcc -g -o helloworld helloworld.c
```

Then bring up the debugger:

    gdb helloworld

and run the program:

    (gdb) run
    Hello World
    (gdb) quit

Why run inside a debugger?

When a C program "crashes", the runtime system typically identifies one unhelpful error: a segmentation fault.
Inside a debugger, you can examine memory addresses and trap such runtime errors.
Debuggers also let you step through execution, examining variables as you go along.

Important: Here is a common mistake to avoid:

First, recall: the -o option names the executable file
```
  gcc -o helloworld -std=c89 helloworld.c
```
Here, the executable file is what we're asking the compiler to name as helloworld
This is the file that we execute:
```
  ./helloworld
```
Now, if one makes the mistake of typing
```
  gcc -o helloworld.c -std=c89 helloworld.c
```
Then, the executable gets written over the file helloworld.c because that's what we're asking the compiler to do (that is, we're telling it to write the executable code into the file helloworld.c)
This has the unfortunate effect of destroying the original file helloworld.c.

Pointers

What is a pointer?

A pointer stores a memory address.
A pointer usually has an associated type, e.g., an int pointer vs. a char pointer.
Pointers (memory addresses) are themselves numbers and can be added (if it makes sense to do so).

Let's start with an example:

int main ()
{
  int i = 5;
  int *intPtr;

  // Extract the address of variable i into the pointer:
  intPtr = & i;

  // Print this address:
  printf ("Variable i is located at address %p\n", intPtr);

  // Use the address:
  *intPtr = *intPtr + 1;

  // See what happens:
  printf ("i = %d\n", i);          // What is in i now?
}

Exercise 1.1: Type up (in the pointer.c file), compile and execute the above program. Add a second pointer variable that points to i and modifies i using only the second pointer variable. Can two pointers point to the same thing? (Put your answer in README.md)

Note:

The ampersand operator (&) extracts a memory address:
```
  intPtr = & i;
```
This address (a number) goes into the variable intPtr
The contents of this variable intPtr can be printed using the %p format specifier:
```
  printf ("Variable i is located at address %p\n", intPtr);
```
What good is a memory address if we can't use it?
To use a memory address, one uses the star operator:
```
  *intPtr = *intPtr + 1;
```
What this is saying:
- Look at the right side first.
- Add 1 to whatever intPtr is pointing to.
- For additional clarity, we could write this as
```
  (*intPtr) = (*intPtr) + 1;
```
- Left side of assignment: put the result in whatever intPtr is pointing to.
After the increment, the picture in memory is:
- Notice what's unusual here: in C, unlike Java, a pointer can point to anywhere in memory, including the stack.
- There is nothing in this program that's on the heap or in the global area.
- Note: we've just conjured up the number 4562 for the sake of the diagram; when you ran the program, you saw actual an address printed out, something like:
```
Variable i is located at address 0x7fff59c5359c
```

A more complex example:

// Declare some global integers:
int i = 5;
int j = 6;
int sum;

int main ()
{
  // Int pointer declarations:
  int *intPtr;
  int *intPtr2;
  int *intPtr3;

  // First, let's print the address of variable i:
  printf ("Variable i is located at address %p\n", &i);

  // Now extract the address of variable i into the pointer:
  intPtr = & i;

  // Print.
  printf ("The int at memory location %p is %d\n", intPtr, *intPtr);

  // Let's do some arithmetic.
  intPtr2 = & j;
  sum = (*intPtr) + (*intPtr2);
  printf ("The sum of %d and %d is %d\n", *intPtr, *intPtr2, sum);

  // Now for something stranger:
  printf ("The integer at location %p is %d\n", (intPtr+1), *(intPtr+1));
  printf ("The integer j=%d is at location %p\n", j, &j);

  // Let's see what the default initial value of intPtr3 is:
  if (intPtr3 == NULL) {
    printf ("intPtr3 has been initialized to NULL\n");
  }
  else {
    printf ("intPtr3 has been initialized to %p\n", intPtr3);
  }

}

Exercise 1.2: Copy (in pointer2.c), compile and execute the above program. Draw a memory diagram just after the line
  sum = (*intPtr) + (*intPtr2);
In your memory diagram, use the actual addresses printed to the screen. What is the actual memory address of the variable sum?

Note:

The (asterisk) operator * is used in pointer declarations and in dereferencing pointers.

The (ampersand) operator & is used for extracting memory addresses:

  // Now extract the address of variable i into the pointer:
  intPtr = & i;

Pointers (memory addresses) can be printed using the %p format specifier.
```
  printf ("Variable i is located at address %p\n", &i);
```
Dereferenced pointers can be used in expressions:
```
  sum = (*intPtr) + (*intPtr2);
```
What the right side is saying:
- Similarly *intPtr2 means "Go to the location pointed to by intPtr2 and get the value in there"
- The two values are added into sum.
Pointers themselves can be used in expressions:
```
  printf ("The integer at location %p is %d\n", (intPtr+1), *(intPtr+1));
```
In this case:
- The pointer intPtr is now pointing to i.
- The pointer-arithmetic expression (intPtr+1) means "the address further down (by 1 spot) in memory from where i is"
- Hence *(intPtr+1) fetches whatever is at that spot in memory.
- In our example, this happens to be where j is stored in memory.
Pointers can be compared (equality comparison) to NULL.
Curiously, NULL is not a reserved word but a constant.
ANSI C99 initializes pointers to NULL, but prior versions of C do not.
Important: it's best to assume pointers and variables are not initialized.

Consider an example with char pointers:

int main ()
{
  int i = 5;
  char *charPtr;  // Pointer declaration
  int j;

  // Make the char pointer point to the start of the integer:
  charPtr = (char*) (& i);

  // Extract the byte, store it in the integer j and print j.
  j = (int) *charPtr;
  printf ("First byte: %d\n", j);

  // Get the next byte and print:
  j = (int) *(charPtr+1);
  printf ("Second byte: %d\n", j);

  // Get the third byte and print:
  j = (int) *(charPtr+2);
  printf ("Third byte: %d\n", j);

  // Get the fourth byte and print:
  j = (int) *(charPtr+3);
  printf ("Fourth byte: %d\n", j);
}

HW Exercise 1.3: In addition to the value in j also print the address in charPtr in the first printf statement. Write your program in charpointer.c

Note:

The integer i occupies four bytes, only one of which contains "5".
(Because "5" is small enough to fit into a single byte among the four bytes set aside for an integer).
To extract the first byte, make the char pointer charPtr point to the start of the integer and extract the byte.
Every increment of the charpointer will point it to the next byte.
A char pointer is declared with the asterisk symbol to the left the variable:
```
  char *charPtr;  // Pointer declaration
```

Similarly, a pointer is dereferenced using the asterisk symbol:

  j = *charPtr;   // Retrieve whatever charPtr points to.

The byte so referenced is cast into an int type for printing (since C has no byte type).
The term (charPtr+1) points to the next memory address one byte down. To dereference (fetch something), we apply the asterisk.

Examining pointers in a debugger:

Let's compile the second example with the debug option
```
  gcc -g -o pointer2 pointer2.c
```
and run inside the debugger:
```
  gdb pointer2
```

Inside the debugger, we will set a breakpoint, step through and print the pointer intPtr and what it points to:

The l (list) command lists the program.

  (gdb) l
  7
  8       int main ()
  9       {
  10        // Int pointer declarations:
  11        int *intPtr;
  12        int *intPtr2;
  13        int *intPtr3;
  14
  15        // First, let's print the address of variable i:
  16        printf ("Variable i is located at address %p\n", &i);

The break command creates a breakpoint so you can stop midway through execution. You can set a breakpoint by line number or with a function name.

The run command tells the debugger to start running your program. It will run to completion unless it reaches a line with a breakpoint. Here it stops right before line 16 and prints the statement it is about to execute.

  (gdb) break 16
  Breakpoint 1 at 0x10720: file pointer.c, line 16.
  (gdb) run
  Starting program: pointer2
  Breakpoint 1, main () at pointer2.c:16
  16        printf ("Variable i is located at address %p\n", &i);

The p (print) command prints variables.

The next command executes the next statement.

  (gdb) p intPtr
  $1 = (int *) 0x0
  (gdb) next
  Variable i is located at address 134000
  19        intPtr = & i;
  (gdb) next
  22        printf ("The int at memory location %p is %d\n", intPtr, *intPtr);
  (gdb) p intPtr
  $2 = (int *) 0x20b70
  (gdb) p *intPtr
  $3 = 5
  (gdb)

The continue command tells the debugger to resume execution until it terminates or hits another breakpoint.

Double Pointers

C allows you to create a pointer to a pointer (also known as a double pointer). The syntax can look confusing, but it works in the same way.

Exercise 1.4: Write a program in pointertopointer.c to use a pointer to a pointer to an int. Fill in the needed assignments below to make the program print "5".
int main ()
{
  int i = 0;
  int *p = NULL;
  int **p2 = NULL;

  // Fill in the assignments here to make the program work:


  // Should print "5";
  printf ("i = %d\n", **p2);
}
Draw a memory diagram just after the printf. Use the actual addresses from your program.
Hint: make p point to i, then make p2 point to p. To get actual addresses, you'll need additional printf's to print pointer values (addresses), or better yet, use the debugger!

Strings

Strings in C:

There is limited support for strings in C.
There is no separate string type.
Strings are simply a sequence of char's where the last character is the special character \0.
String variables are declared as pointers to type char.

Example:

int main ()
{
  char *hStr = "hello";     // String initialization.
  char *wStr = "world";
  char ch;

  // Note the use of "%s"
  printf ("%s %s\n", hStr, wStr);

  printf ("3rd char in wStr is %c\n", *(wStr+2));     // Prints 'r'

  // Let's get the 6-th char: should be '\0'
  ch = *(wStr+5);
  if (ch == '\0') {
    printf ("char is string terminator\n");
  }
  else {
    printf ("char is not string terminator\n");
  }
}

Note:

Although not visible, the character immediately after the last real character in a string is the "null" character \0.
Strings are enclosed in double-quotes.
String variables are declared as char * variables.
Strings can be printed using the %s print-format specifier.

Exercise 1.5: Write the above program in string.c. Then, add a loop to determine the length of a string so that the line
  printf ("Length of %s is %d\n", hStr, count);
prints 5. Write all your code in main().

Now let's try to modify a string and see what happens...

Exercise 1.6: Copy over your string.c. code into string2.c and add these lines right after the first print statement
  *(hStr+1) = 'y';
  printf ("%s\n", hStr);
Explain what these lines are trying to achieve. Then compile and execute. Paste the output of your program into your answer file.

As we'll explain, memory in C is a bit more complicated:

It turns out, there are four places in memory where one could store a string:
- On the stack, using char arrays.
- On the heap, using malloc.
- In the global area, using char arrays and global variables.
- In read-only memory, as in the example above.
Thus, in the above case, the memory picture at the end of main() is:
- Strings declared as
```
  char *hStr = "hello";
  char *wStr = "world";
```
  where the actual string like "hello" is part of of the program, are intended as constants not to be modified.
- Where possible, the compiler asks the hardware to store these in read-only memory.
- This type of memory is not available on all hardware, and when it is available, the error in trying to modify differs.
- As a result, you may get different output depending on the computer you are using (like "Bus error 10" or "Segmentation fault").
Next, we will see that, to modify a string, we'll need store it as a char array.

Arrays

Most of this section you will do for homework, but let's look at the key ideas quickly!

There are two ways of creating an array in C:

Declare an array with a static size.
Declare an array variable without a size, and allocate memory dynamically.

Let's look at an example:

int main ()
{
  int A[5];           // Statically-sized unidimensional array.
  int *A2 = NULL;     // Declaration of 1D array variable.

  int i;              // For-loop variable.
  int sum;            // For use in examples.


  // Static example. The space is already allocated, so the
  // array can be used immediately.
  for (i=0; i<5; i++) {
    A[i] = i * 10;                 // Fill the array with some numbers.
  }

  sum = 0;
  for (i=0; i<5; i++) {
    sum += A[i];                   // Compute the sum of array's numbers.
  }
  printf ("sum = %d\n", sum);      // Print sum.


  // Dynamic version of example using "malloc" to allocate space.
  // Note the use of the "sizeof" keyword.
  A2 = (int*) malloc (sizeof(int) * 5);

  for (i=0; i<5; i++) {
    A2[i] = i * 10;                // Fill the array with some numbers.
  }

  sum = 0;
  for (i=0; i<5; i++) {
    sum += A2[i];                  // Compute the sum of array's numbers.
  }
  printf ("sum = %d\n", sum);      // Print sum.

  free (A2);                       // Must free malloc'd memory
}

HW Exercise 1.7: Type and execute the above in array.c. Then, in array2.c write a similar program to compute the sum of the numbers 0.1, 0.2, ..., 0.9. And do it both ways (static sizing, and via malloc).
What is the output for each program?

Note:

When you know the size of an array, and it's small, the array size can be written as a constant:
```
  int A[5];
```
In this case, space for the array is created on the stack.
When the size is unknown, declare the appropriate type of pointer (int, in this case):
```
  int *A2 = NULL;
```
The pointer is not pointing to anything, so space for the array must be requested at run time using malloc:
```
  A2 = (int*) malloc (sizeof(int) * 5);
```
Let's examine this in some detail:
- The argument to malloc is the total amount of space (in bytes) needed.
- We need space for 5 integers.
- Since we don't know how much space an int takes up, we get the current system's size-of-an-int by using the sizeof operator.
- Thus, an alternative way of writing the same code is:
```
       spaceNeededInBytes = sizeof(int) * 5;
       A2 = (int*) malloc (spaceNeededInBytes);
```
- Finally, note that malloc's return value is declared as void* (i.e., pointer to anything). It must be cast as the desired pointer:
```
  A2 = (int*) malloc (sizeof(int) * 5);
```
malloc is pronounced like you would "shalluck" (a combination of "shallow" and "luck").
malloc is the equivalent of new in Java, so space is allocated on the heap.
Thus, the memory picture for the above example is:
Let's highlight:
- The memory that's malloc'd is on the heap.
- This is large enough to hold 5 integers.
- The typical size for an integer is 4 bytes, so that's 20 bytes of memory.
  (On some small processors, the kind inside sensors, it may be 2 bytes).
- The pre-sized array, on the other hand, is created on the stack itself.
- Both array variables A and A2 are actually pointers.
  (And in fact, can be used as pointers, as we'll see.)
- We've shown the stack as growing "upwards", which is why the array contents are shown going up. This is just for our illustration, since we've always been showing the stack as growing upwards.
- Actual memory is just a long sequence of locations, with no real "direction" other than two adjacent locations differ in the address by 1.
C does not have garbage collection:
- This means, when you use malloc and a heap block is allocated, the programmer must "return" this to the heap.
- This is achieved by calling
```
  free (A2);
```

Let's now look at an example with 2D arrays:

int main ()
{
  double B[3][4];     // 2D array.
  double **B2 = NULL; // Declaration of 2D array pointer variable.

  int i, j;
  double dSum;


  for (i=0; i<3; i++) {              // B is pre-sized, ready to use.
    for (j=0; j<4; j++) {
      B[i][j] = (i+j)/10.0;          // Fill the array with some numbers.
    }
  }

  dSum = 0;
  for (i=0; i<3; i++) {              // Compute the sum of array's numbers.
    for (j=0; j<4; j++) {
      dSum += B[i][j];
    }
  }
  printf ("dSum = %4.2lf\n", dSum);


  // Dynamically allocated version of 2D example.
  // Note the two-step allocation.

  // Allocate space for 3 pointers-to-double
  B2 = (double **) malloc (sizeof(double*) * 3);

  for (i=0; i<3; i++) {
    // For each such pointer, allocate a size-4 double array.
    B2[i] = (double*) malloc (sizeof(double) * 4);
  }

  // Compute the sum of array's numbers.
  for (i=0; i<3; i++) {
    for (j=0; j<4; j++) {
      B2[i][j] = (i+j) / 10.0;
    }
  }

  dSum = 0;
  for (i=0; i<3; i++) {
    for (j=0; j<4; j++) {
      dSum += B2[i][j];
    }
  }
  printf ("dSum = %4.2lf\n", dSum);


  // Must free allocated memory when not needed anymore:
  free (B2);
}

HW Exercise 1.8: Type up and execute the above in array3.c.

Let's examine the pointer version:

Observe the first step, where we allocate space for 3 pointers:
```
  B2 = (double **) malloc (sizeof(double*) * 3);
```
Let's tease this apart:
- First, consider the argument to malloc:
```
  B2 = (double **) malloc (sizeof(double*) * 3);
```
- This says that we are requesting 3 contiguous spots where each spot is large enough to hold a pointer-to-a-double.
```
  B2 = (double **) malloc (sizeof(double*) * 3);
```
- The return value from malloc is the address (pointer) to that 3-sized array of double-pointers.
- Hence, it is a pointer to a pointer:
```
  B2 = (double **) malloc (sizeof(double*) * 3);
```
Next, we need each row of the 2D array:
```
  for (i=0; i<3; i++) {
    B2[i] = (double*) malloc (sizeof(double) * 4);
  }
```
Again, the details:
- Since B2 is a pointer to a group of contiguous slots (each a pointer) in memory, B2[i] refers to the i-th element of that array.
- Since these are pointers, B2[i] is a pointer.
- Before the loop, we only had the space for the group of pointers, but each spot is not yet pointing to anything.
- It's our job to make it point.
- So we make each of the three point to a row of 4 double's:
```
  for (i=0; i<3; i++) {
    B2[i] = (double*) malloc (sizeof(double) * 4);
  }
```
- Then, finally, an assignment like
```
  for (i=0; i<3; i++) {
    B2[i][j] = 100;
  }
```
  goes to the j-th element in the i-th row pointed to by B2.
Confusing? Perhaps a memory diagram will help:
- Let's start with the heap block that gets allocated in the first call to malloc:
```
  B2 = (double **) malloc (sizeof(double*) * 3);
```
- After the first iteration of the for-loop
```
  for (i=0; i<3; i++) {
    B2[i] = (double*) malloc (sizeof(double) * 4);
  }
```
- After the next two iterations:
- Thus, a particular element like B2[1][3] is accessed as shown above.
Thus, when using malloc, a 2D array is really an array of 1D arrays.
Finally, notice that we did not draw the memory for array B.
A statically sized (or pre-size) array like B is not stored as an array of arrays.
- The array
```
  double B[3][4];
```
  clearly requires enough space for 12 double's.
- These 12 double's are stored contiguously in one long sequence.
- The first four of these double's belong to the row B[0].
- The next four of these double's belong to the row B[1].
- And so on.
- When accessing, say, B[i][j], the compiler inserts a calculation along the lines of
```
    location = B + (i*4) + j;
```
  and uses the result to find the actual location offset from the start address.

HW Exercise 1.9: Enhance the last of the drawings above to include the pre-sized array B. Show on your diagram the location of B[1][3]. Explain how the above calculation works. You do not need to submit your diagram, but you should still make it and be sure you understand it!

The Heap

As seen above, the Heap is the memory region where dynamically sized data structures can be stored.

The malloc function is used to reserve memory from the heap, and its return value is always saved into a pointer. The pointer can then be used to access the heap data.
Once the program is finished using the heap data, it should call free on each address that has been allocated with malloc.
If you forget to free pointers that are no longer being used, this is known as a memory leak.
When your program exits, it will automatically free any memory allocated on the heap.

In our model of the Heap:

The malloc function will always allocate space at the next available address in the heap with sufficient space.
The amount of space reserved will be the size parameter passed to malloc. (This is a simplification, in reality malloc must reserve some extra space for meta data)
After a heap object is freed, that space can be reused for subsequent calls to malloc.
Calling free(p) allows the space that p pointed to to be reused, but it does not affect the pointer itself. The pointer p will still point to the same memory address, but this is called a dangling pointer, and it cannot safely be used by any subsequent code.

sizeof (HW)

Let's take a closer look at the sizeof operator:

Although it looks like a method, it's actually part of the language (because the arguments are not variables but types).
sizeof is used to determine the amount of space allocated to a certain type.
Unlike in Java, the actual space allocated to an int or double can vary across systems.
For example, a tiny microprocessor in a child's toy might use a 2-byte integer, whereas a laptop is likely to use a 4-byte integer.

Another example:

int main ()
{
  double *doublePtr;
  char *charPtr;

  printf ("The number of bytes needed by a double: %d\n", sizeof(double));
  printf ("The number of bytes needed by a char: %d\n", sizeof(char));

  // Get the space from malloc:
  doublePtr = (double*) malloc (sizeof(double));
  charPtr = (char*) malloc (sizeof(char));

  // Print the address of the memory block returned by malloc:
  printf ("double pointer is at location: %p\n", doublePtr);
  printf ("char pointer is at location: %p\n", charPtr);

  // Assign values and print:
  *doublePtr = 3.141;
  *charPtr = 'A';

  printf ("double value = %lf   char value = %c\n", *doublePtr, *charPtr);

  // Free the memory when done:
  free (doublePtr);
  free (charPtr);
}

HW Exercise 1.10: What is printed out in the above program? Write your code in sizeof.c. Draw a memory diagram.

Pointer arithmetic (HW)

In both Java and C, a pointer is a number because that's what a memory address is: a number.

While Java does not permit you to perform regular arithmetic on this number, C does.

In C, you can treat a memory address like any other number and add/sub etc.

Why would we want to do this?

An example using arrays:

int main ()
{
  int A[10];
  int *B;

  printf ("BEFORE malloc: Address A=%p  Address B=%p\n", A, B);
  // Prints an address for A, but zero for B

  // Assign space to B:
  B = (int*) malloc (sizeof(int) * 10);

  printf ("AFTER malloc: Address A=%p  Address B=%p\n", A, B);
  // Prints an address for A and newly allocated address for B.

  // Two ways of assigning values:
  A[3] = 5;
  *(A + 4) = 6;
  printf ("A[3]=%d  A[4]=%d\n", A[3], A[4]);    // Prints 5 and 6.

  // Two ways of assigning values:
  B[3] = 7;
  *(B + 4) = 8;
  printf ("B[3]=%d  B[4]=%d\n", B[3], B[4]);    // Prints 7 and 8.

  // Done.
  free (B);
}

HW Exercise 1.11: Implement the above program in pointerArith.c. Record its output.

Note:

Array variables are really pointers and can be used as pointers:

  A[3] = 5;
  *(A + 4) = 6;    // Fifth position in array A.

You should use regular array indexing (A[3]=5) where possible, instead of the pointer manipulation (*(A+4) = 5).
The pointer version explains how arrays work:
- A is the address of the start of the array.
- A+4 is the address 4 positions into the array, i.e., the address of A[4].
- The expression *(A+4) follows the address. Thus, the assignment
```
  *(A + 4) = 6;
```
  assigns the value 6 into this location.
The other example in the code shows that a pointer variable can be used with array brackets:
```
  // Two ways of assigning values:
  B[3] = 7;
  *(B + 4) = 8;
```
Again, where possible, you should use array notation.
Actual pointer arithmetic is useful when working with devices like sensors where the hardware provides a stream of bytes, and where you need only, say, a particular byte (like the 7th byte).

Here's an example of pointer arithmetic with 2D arrays:

int main ()
{
  double A[5][6]  ;     // Static allocation of space to array A.
  double **B;           // We'll use malloc to assign space to B.
  int i;

  printf ("BEFORE malloc: Address A=%p  Address B=%p\n", A, B);
  // Prints an address for A, but zero for B

  // Assign space for first dimension of B (an array of pointers-to-double)
  B = (double**) malloc (5 * sizeof(double*));
  for (i=0; i<5; i++) {
    B[i] = (double*) malloc (6 * sizeof(double));
  }

  printf ("AFTER malloc: Address A=%p  Address B=%p\n", A, B);
  // Prints an address for A and newly allocated address for B.

  // Two ways of assigning values:
  A[1][2] = 5.55;
  *((double*)A + 3*6 + 4) = 6.66;
  printf ("A[1][2]=%lf  A[3][4]=%lf\n", A[1][2], A[3][4]);    // Prints 5.55 and 6.66.

  // Two ways of assigning values:
  B[1][2] = 7.77;
  *((*(B + 3)) + 4) = 8.88;
  printf ("B[1][2]=%lf  B[3][4]=%lf\n", B[1][2], B[3][4]);    // Prints 7.77 and 8.88

  // Free the individual small arrays:
  for (i=0; i<5; i++) {
    free (B[i]);
  }
  // Free the array of double-pointers:
  free (B);
}

HW Exercise 1.12: Implement the above program in pointerArith2.c and draw a memory picture before the first free() is called. You can make your memory diagram with markdown tables, or draw in on paper and upload a picture to your repository (be sure to include a link to the picture in your README).

Note:

Both arrays are accessed using standard array indexing:
```
  A[1][2] = 5.55;
  B[1][2] = 7.77;
```
However, it is also possible (not recommended) to use the actual addresses and perform address arithmetic:
```
  *((double*)A + 3*6 + 4) = 6.66;

  *((*(B + 3)) + 4) = 8.88;
```
Let's explain the first one:
```
  *((double*)A + 3*6 + 4) = 6.66;
```
- A double occupies 8 bytes.
- Thus, a 5 x 6 array requires 30*8 = 240 bytes.
- To get to location A[3][4], we compute the address of the first byte in the 8 bytes allocated to A[3][4].
- Note that A[3] is the 4th row and so, we need to skip past 3 rows: 3*6.
- Then we skip past 4 positions to get to the 5th element.
- The total number of positions to skip past: 3*6 + 4.
- Adding this to the start address gives the start address of position A[3][4].
- Finally, because A is declared as a 2D array, we need to cast A into a pointer type to perform arithmetic.
The second one is a little more complicated:
```
  *((*(B + 3)) + 4) = 8.88;
```
- Recall that B is a pointer that points to a block of double-pointers.
- Thus, B+3 is the fourth such pointer in the block.
- The expression *(B+3) follows that address, which is the address of the block of 6 elements assigned to the 4th row.
- We now add 4 to this address to get the exact address of element B[3][4].
- Lastly, we follow the address (pointer) with the (outermost) * operation.
Note that the individual array blocks need to be free'd before the double-pointer block pointed to by B is free'd.

HW Exercise 1.13: In pascal.c, create a 2D array to store and print Pascal's triangle (Each element is the sum of the two elements immediately above, slightly to the left and to the right).

Sample triangle:
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1
Ensure that only as much space as needed is used for the array, so that the first row is of size 1, the second of size 2, and so on. You can hard code the first entry in the array, but the rest should be calculated by your program depending on the value of the size variable. Use malloc to create the space, but use array brackets to access the elements. Place the output for size=10 in your response file.

Hint: The output above has added white space to show the adjacency relationship. Your program does not need extra spaces before each line, so your program would produce the output below for size=5.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

HW Exercise 1.14 : In pascal2.c, repeat the exercise except that this time use pointer arithmetic instead of array brackets.

Hex (HW)

By now, you've noticed that pointers (which we've claimed are numbers) have letters in them, as in:

   address 0x7fff5eb8859c

Let's now explain the hexadecimal notation:

Recall: a decimal number uses ten digit symbols 0,1,2,...,9.
A binary number uses two symbols: 0 and 1.
A hexadecimal number uses 16 symbols.
- The first ten of these are the same ten used for decimal: 0 through 9.
- What symbols could we use for the remaining six?
- In an ideal world, one would invent new characters.
- But our keyboard is limited.
- So, the convention is to use the letters a,b,c,d,e,f.
  (Either lowercase or uppercase).
How do we understand the value of a hexadecimal number?
Recall the meaning of the placement of digits in our own decimal system:
```
          2      4      3
        2×100  +  4×10   +   3×1
     
```
- The first digit (going right to left), 3, is the number of units or 3×10⁰
- The second digit, 4, is the number of tens or 4×10¹
- The third digit, 2, is the number of hundreds or 2×10²

Similarly, the binary number 101 decodes as:

       1      0      1
      1×2²  +   0×2¹  +  1×2⁰    =   5 (in decimal)

So, the hexadecimal number 2AF decodes as:
```
       2      A      F
      2×16² +  A×16¹ + F×16⁰ 
      512   +  160  +   15   =   687 (in decimal)
     
```
- How does A×16 become 160?
- The symbol A has the value 10, the symbol B has the value 11, and so on ... and F has the value 15.
  ⇒ Thus A×16 is really 10×16.
Why is hexadecimal important?
- Actual hardware is binary, but binary numbers are very long when written out.
- For example:
```
     0 1 0 0 1 1 0 0 0 1 1 0 1 0 1 1
     
```
- In working with addresses and such we are rarely interested in the numeric value.
- Let's rewrite the above with a little spacing:
```
     0 1 0 0   1 1 0 0   0 1 1 0   1 0 1 1
     
```
- Each group of 4 bits can represent 16 values - a single hex digit!
- So, for the above:
```
     0 1 0 0   1 1 0 0   0 1 1 0   1 0 1 1
        4         C         7         B
     
```
- Thus the hex number 4C7B is equivalent, and much more compact.
Other than understanding addresses, binary numbers are useful when working with hardware directly. In this case, the hex versions are easier to read.

HW Exercise 1.15:

What is the decimal value of the number 1ABE?
Convert the decimal number 8384 into hexadecimal.
Use the hex version of 8384 to write that as a binary number, leaving spacing between every four bits.

Consider the following program:

int main ()
{
  int i;

  for (i=0; i<=16; i++) {
    printf ("%X\n", i);
  }
  printf ("\n");

  i = 256;
  printf ("i=%d hex=%X\n", i,i);
}

HW Exercise 1.16: Without writing the program, can you predict what it will print? Then, write the program and confirm.

Big vs. little endian (Bonus!)

Complete all exercises in this section to receive one bonus point towards the first exam.

Let's go back to an earlier example for a moment:

int main ()
{
  int i = 5;
  char *charPtr;  // Pointer declaration
  int j;

  // Make the char pointer point to the start of the integer:
  charPtr = (char*) (& i);

  j = (int) *charPtr;
  printf ("First byte:  %d at address %p\n", j, (charPtr));

  j = (int) *(charPtr+1);
  printf ("Second byte: %d at address %p\n", j, (charPtr+1));

  j = (int) *(charPtr+2);
  printf ("Third byte:  %d at address %p\n", j, (charPtr+2));

  j = (int) *(charPtr+3);
  printf ("Fourth byte: %d at address %p\n", j, (charPtr+3));

}

Exercise 1.17 (Bonus): Implement the above program in endian.c.

Let's explain:

First, a char pointer is a byte-level pointer:
- This means that
```
  charPtr = (char*) (& i);
```
  will make charPtr point to the start address of the integer i
- It also means that charPtr+1 points to the next byte.
Thus, a memory diagram for this looks like:
Before explaining the address-level detail, let's point out something about the diagram:
- We've drawn the stack and de-emphasized the other areas of memory because they are not relevant to this program.
- We've drawn the stack growing downwards to make illustration more convenient so that we can read increasing addresses going downwards.
Now we'll point out something about what the compiler does:
- Compilers have a choice in what order they place variables on the stack.
- In using the clang compiler on Mac-OS, we notice that the variables were placed in reverse order: first j (bottom of stack), then charPtr, then i (top of stack).
Now take a closer look at the 4-byte integer i:
- The 4 bytes could be stored in the order
```
         0
         0
         0
         1
```
- But it could just as easily be stored as
```
         1
         0
         0
         0
```
The term little endian is used for the latter approach:
- If the start address of the four bytes has the lowest-order digits (the 1's, 2's etc), it's called little-endian order.
The opposite order is called big endian.
There is no reason to prefer one or the other, and we as programmers can't choose: the hardware architecture comes fixed with one or the other approach.

Exercise 1.18 (Bonus): Modify endian.c. to print the addresses of all the variables. Then draw a detailed memory diagram like the one we've shown above, but using the actual memory addresses from the execution of your program. Look up the terms little- and big-endian and explain their origin.

Submission Instructions

Do your work in a repository created using this link.

Answer all of the exercise questions above in your README.md file.
Add all of your source code files (e.g., helloworld.c, pointer.c, etc) to your git repository. You can do this by running git add FILENAME when in the same directory as the file you want to add. You will then need to use git commit -m "some message" and git push origin master to commit and push your files. Be sure to run git status to verify that all modified files have been committed and pushed.
You should check the contents of the README.md file and your other C files through the GitHub website to ensure that it has all of your correct content!

Your work will be graded out of 20 points. 1 point will be for the style/formatting of your Markdown (e.g., use appropriate markdown code blocks and headings), and the remaining 19 points will be for completing the exercises fully.

Previous - Next