Lab 1a: Pointers in C

Lab Format

pointer.c contains a skeleton for some programming puzzles, along with a comment block that describes exactly what the functions must do and what restrictions there are on their implementation. Your assignment is to complete each function skeleton according to the following rules:

• Only straightline code (i.e., no loops or conditionals) unless otherwise stated. Look for "Control Constructs" under ALLOWED in pointer.c comments.
• A limited number of C arithmetic and logical operators (described in pointer.c comments).
• The C bit shift operators (<< and >>) may be needed for some problems but will not be covered in lecture until Friday. You may want to do the reading for Friday early.
• No constants larger than 8 bits (i.e., 0 - 255 inclusive) are allowed.
• Feel free to use "(", ")", and "=" as much as you want.
• You are permitted to use casts for these functions.
• We will not grade comments, but commenting your code is good practice and helpful for debugging.

You will start working with basic pointers and use them to compute the size of different data items in memory, modify the contents of an array, and complete a couple of pointer "puzzles" that deal with alignment and array addresses.

Using Pointers

This section describes the functions you will be completing in pointer.c found in the lab1a folder you downloaded. Refer to the file pointer.c itself for more complete details.

Pointer Arithmetic

1. The first three functions ask you to compute the size (how much memory a single one takes up, in bytes) of various data elements (ints, doubles, and pointers). You will accomplish this by noting that arrays of these data elements allocate contiguous space in memory so that one element follows the next.

Manipulating Data Using Pointers

The next two functions challenge you to manipulate data in new ways with your new knowledge of pointers:

4. The swap_ints function asks you to swap the values that two given pointers point to, without changing the pointers themselves (i.e., they should still point to the same memory addresses).
5. The change_value function asks you to change the value of an element of an array using only the starting address of the array. You will add the appropriate value to the pointer to create a new pointer to the data element to be modified. You are not permitted to use [] syntax to access or change elements in the array anywhere in the pointer.c file.

Pointers and Address Ranges

6. The within_same_block function asks you to determine if the addresses stored by two pointers lie within the same block of 64-byte aligned memory. The following are some examples of parameters and returns for calls to this function:
   • ptr1: 0x0
ptr2: 0x3F
return: 1
   • ptr1: 0x0
ptr2: 0x40
return: 0
   • ptr1: 0x3F
ptr2: 0x40
return: 0
   • ptr1: 0x3CE
ptr2: 0x3EF
return: 1
   • ptr1: 0x3CE
ptr2: 0x404
return: 0
7. The within_array function ask you to determine if the address stored in ptr is pointing to a byte that makes up some part of an array element for the passed array. The byte does not need to be the first byte of the array element that it is pointing to. That description is a bit wordy, so here are some examples.
   • int_array: 0x0
size: 4
ptr: 0x0
return: 1
   • int_array: 0x0
size: 4
ptr: 0xF
return: 1
   • int_array: 0x0
size: 4
ptr: 0x10
return: 0
   • int_array: 0x100
size: 30
ptr: 0x12A
return: 1
   • int_array: 0x100
size: 30
ptr: 0x50
return: 0
   • int_array: 0x100
size: 30
ptr: 0x18C
return: 0

Byte Traversal

8. The string_length function has you return the length of a string, given a pointer to its beginning. Recall that C-strings do not know how long they are, so we must calculate it for ourselves. Note that you are allowed to use loops and that the null character does NOT count as part of the string length.
9. The endian_experiment function has you set the value a pointer points to to the number 351351. Remember that we work with little endian data storage, and what that means.

Selection Sort

10. The final part of the lab has you implement selection_sort. Selection sort works by effectively partitioning an array into a sorted section, followed by an unsorted section. It repeatedly finds (and selects) the minimum element in the unsorted section, and moves it to the end of the sorted section (swap_ints might be useful for this). The pseudo code might look something like this:

    // "arr" is an array
    // "n" is the length of arr
    for i = 0 to n - 1
      minIndex = i
      for  j = i + 1 to n
        if arr[minIndex] > arr[j]
          minIndex = j
        end if
      end for
      Swap(arr[i], arr[minIndex])
    end for

    Note that you are allowed to use loops and if statements in this one.

Checking Your Work

We have included the following tools to help you check the correctness of your work:

• ptest.c is a test harness for pointer.c. You can test your solutions like this:

  $ make
  $ ./ptest

  This only checks if your solutions return the expected result. We may test your solution on inputs that ptest does not check by default and we will review your solutions to ensure they meet the restrictions of the assignment.

• dlc.py is a Python script that will check for compliance with the coding rules. The usage is:

  $ ./dlc.py

  When no issues are found, the output will be [], otherwise, the output inside the brackets will tell you (using shorthand notation) what issues were found function-by-function.

• The dlc program enforces a stricter form of C declarations than is the case for C++ or that is enforced by gcc. In particular, in a block (what you enclose in curly braces) all your variable declarations must appear before any statement that is not a declaration. For example, dlc will complain about the following code:

  int foo(int x) {
    int a = x;
    a *= 3;     /* Statement that is not a declaration */
    int b = a;  /* ERROR: Declaration not allowed here */
  }

  Instead, you must declare all your variables first, like this:

  int foo(int x) {
    int a = x;
    int b;
    a *= 3;
    b = a;
  }

• The dlc program will also complain about binary constants such as 0b10001000, so avoid using them.