Low Level Operators and Bit Fields

  We have seen how pointers give us control over low level memory operations. Many programs (e.g. systems type applications) must actually operate at a low level where individual bytes must be operated on.
NOTE: The combination of pointers and bit-level operators makes C useful for many low level applications and can almost replace assembly code. (Only about 10 % of UNIX is assembly code the rest is C!!.)

Bitwise Operators

The bitwise operators of C a summarised in the following table:

 

Table: Bitwise operators

&	AND
	OR
	XOR
	One's Compliment
<<	Left shift
>>	Right Shift

DO NOT confuse & with &&: & is bitwise AND, && logical AND. Similarly for and .

is a unary operator -- it only operates on one argument to right of the operator.

The shift operators perform appropriate shift by operator on the right to the operator on the left. The right operator must be positive. The vacated bits are filled with zero (i.e. There is NO wrap around).
For example: x << 2 shifts the bits in x by 2 places to the left.

So:

if x = 00000010 (binary) or 2 (decimal)

then:

or 0 (decimal)

Also: if x = 00000010 (binary) or 2 (decimal)

or 8 (decimal)

Therefore a shift left is equivalent to a multiplication by 2.

Similarly a shift right is equal to division by 2

NOTE: Shifting is much faster than actual multiplication (*) or division (/) by 2. So if you want fast multiplications or division by 2 use shifts.

To illustrate many points of bitwise operators let us write a function, Bitcount, that counts bits set to 1 in an 8 bit number (unsigned char) passed as an argument to the function.

int bitcount(unsigned char x) 
 
   { int count;
 
     for (count=0; x != 0; x>>=1);
       if ( x & 01)
         count++;
     return count;
   }

This function illustrates many C program points:

• for loop not used for simple counting operation
• x x = x >> 1
• for loop will repeatedly shift right x until x becomes 0
• use expression evaluation of x & 01 to control if
• x & 01 masks of 1st bit of x if this is 1 then count++

Bit Fields

Bit Fields allow the packing of data in a structure. This is especially useful when memory or data storage is at a premium. Typical examples:

• Packing several objects into a machine word. e.g. 1 bit flags can be compacted -- Symbol tables in compilers.
• Reading external file formats -- non-standard file formats could be read in. E.g. 9 bit integers.

C lets us do this in a structure definition by putting :bit length after the variable. i.e.

struct packed_struct {
   unsigned int f1:1;
   unsigned int f2:1;
   unsigned int f3:1;
   unsigned int f4:1;
   unsigned int type:4;
   unsigned int funny_int:9;
} pack;

Here the packed_struct contains 6 members: Four 1 bit flags f1..f3, a 4 bit type and a 9 bit funny_int.

C automatically packs the above bit fields as compactly as possible, provided that the maximum length of the field is less than or equal to the integer word length of the computer. If this is not the case then some compilers may allow memory overlap for the fields whilst other would store the next field in the next word (see comments on bit fiels portability below).

Access members as usual via:

   pack.type = 7;

NOTE:

• Only n lower bits will be assigned to an n bit number. So type cannot take values larger than 15 (4 bits long).
• Bit fields are always converted to integer type for computation.
• You are allowed to mix ``normal'' types with bit fields.
• The unsigned definition is important - ensures that no bits are used as a flag.

Bit Fields: Practical Example

Frequently device controllers (e.g. disk drives) and the operating system need to communicate at a low level. Device controllers contain several registers which may be packed together in one integer (Figure 12.1).
 
Fig. 12.1 Example Disk Controller Register We could define this register easily with bit fields:

struct DISK_REGISTER  {
     unsigned ready:1;
     unsigned error_occured:1;
     unsigned disk_spinning:1;
     unsigned write_protect:1;
     unsigned head_loaded:1;
     unsigned error_code:8;
     unsigned track:9;
     unsigned sector:5;
     unsigned command:5;
};

To access values stored at a particular memory address, DISK_REGISTER_MEMORY we can assign a pointer of the above structure to access the memory via:

struct DISK_REGISTER *disk_reg = (struct DISK_REGISTER *) DISK_REGISTER_MEMORY;

The disk driver code to access this is now relatively straightforward:

/* Define sector and track to start read */

disk_reg->sector = new_sector;
disk_reg->track = new_track;
disk_reg->command = READ;

/* wait until operation done, ready will be true */

while ( ! disk_reg->ready ) ;

/* check for errors */

if (disk_reg->error_occured)
  { /* interrogate disk_reg->error_code for error type */
    switch (disk_reg->error_code)
    ......
  }

A note of caution: Portability

Bit fields are a convenient way to express many difficult operations. However, bit fields do suffer from a lack of portability between platforms:

• integers may be signed or unsigned
• Many compilers limit the maximum number of bits in the bit field to the size of an integer which may be either 16-bit or 32-bit varieties.
• Some bit field members are stored left to right others are stored right to left in memory.
• If bit fields too large, next bit field may be stored consecutively in memory (overlapping the boundary between memory locations) or in the next word of memory.

If portability of code is a premium you can use bit shifting and masking to achieve the same results but not as easy to express or read. For example:

unsigned int  *disk_reg = (unsigned int *) DISK_REGISTER_MEMORY;

/* see if disk error occured */

disk_error_occured = (disk_reg & 0x40000000) >> 31;

Exercises

Exercise 12507
 Write a function that prints out an 8-bit (unsigned char) number in binary format.

Exercise 12514
Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of an unsigned char variable y (leaving other bits unchanged).
E.g. if x = 10101010 (170 decimal) and y = 10100111 (167 decimal) and n = 3 and p = 6 say then you need to strip off 3 bits of y (111) and put them in x at position 10xxx010 to get answer 10111010.
Your answer should print out the result in binary form (see Exercise 12.1 although input can be in decimal form.
Your output should be like this:

x = 10101010 (binary)
   y = 10100111 (binary)
   setbits n = 3, p = 6 gives x = 10111010 (binary)

Exercise 12515
Write a function that inverts the bits of an unsigned char x and stores answer in y.
Your answer should print out the result in binary form (see Exercise 12.1 although input can be in decimal form.
Your output should be like this:

x = 10101010 (binary)
   x inverted = 01010101 (binary)

Exercise 12516
Write a function that rotates (NOT shifts) to the right by n bit positions the bits of an unsigned char x.ie no bits are lost in this process.
Your answer should print out the result in binary form (see Exercise 12.1 although input can be in decimal form.
Your output should be like this:

x = 10100111 (binary)
   x rotated by 3 = 11110100 (binary)

Note: All the functions developed should be as concise as possible

Advanced Pointer Topics

We have introduced many applications and techniques that use pointers. We have introduced some advanced pointer issues already. This chapter brings together some topics we have briefly mentioned and others to complete our study C pointers.
In this chapter we will:

• Examine pointers to pointers in more detail.
• See how pointers are used in command line input in C.
• Study pointers to functions

Pointers to Pointers

We introduced the concept of a pointer to a pointer previously. You can have a pointer to a pointer of any type.
Consider the following:

char ch;  /* a character */
char *pch; /* a pointer to a character */
char **ppch; /* a pointer to a pointer to a character */

We can visualise this in Figure 11.1. Here we can see that **ppch refers to memory address of *pch which refers to the memory address of the variable ch. But what does this mean in practice?
 
Fig. 11.1 Pointers to pointers Recall that char * refers to a (NULL terminated string. So one common and convenient notion is to declare a pointer to a pointer to a string (Figure 11.2)
 
Fig. 11.2 Pointer to String Taking this one stage further we can have several strings being pointed to by the pointer (Figure 11.3)
 
Fig. 11.3 Pointer to Several Strings We can refer to individual strings by ppch[0], ppch[1], ..... Thus this is identical to declaring char *ppch[].
One common occurrence of this type is in C command line argument input which we now consider.

Command line input

C lets read arguments from the command line which can then be used in our programs.

We can type arguments after the program name when we run the program.

We have seen this with the compiler for example

   c89 -o prog prog.c

c89 is the program, -o prog prog.c the arguments.

In order to be able to use such arguments in our code we must define them as follows:

   main(int argc, char **argv)

So our main function now has its own arguments. These are the only arguments main accepts.

• argc is the number of arguments typed -- including the program name.
• argv is an array of strings holding each command line argument -- including the program name in the first array element.

A simple program example:

#include
 
main (int argc, char **argv)
    { /* program to print arguments
     from command line */
 
     int i;
 
     printf(``argc = %dnn'',argc);
     for (i=0;i
       printf(``argv[%d]: %sn'',
         i, argv[i]);
   }

Assume it is compiled to run it as args.

So if we type:

   args f1 ``f2'' f3 4 stop!

The output would be:

   argc = 6
 
   argv[0] = args
   argv[1] = f1
   argv[2] = f2
   argv[3] = f3
   argv[4] = 4
   argv[5] = stop!

NOTE:  argv[0] is program name.
    argc counts program name
    Embedded `` '' are ignored.
   Blank spaces delimit end of arguments.
   Put blanks in `` '' if needed.

Pointers to a Function

  Pointer to a function are perhaps on of the more confusing uses of pointers in C. Pointers to functions are not as common as other pointer uses. However, one common use is in a passing pointers to a function as a parameter in a function call. (Yes this is getting confusing, hold on to your hats for a moment).
This is especially useful when alternative functions maybe used to perform similar tasks on data. You can pass the data and the function to be used to some control function for instance. As we will see shortly the C standard library provided some basic sorting ( qsort) and searching (bsearch) functions for free. You can easily embed your own functions.
To declare a pointer to a function do:

int (*pf) ();

This simply declares a pointer *pf to function that returns and int. No actual function is pointed to yet.
If we have a function int f() then we may simply (!!) write:

pf = &f;

For compiler prototyping to fully work it is better to have full function prototypes for the function and the pointer to a function:

int f(int);
int (*pf) (int) = &f;

Now f() returns an int and takes one int as a parameter.
You can do things like:

ans = f(5);
ans = pf(5);

which are equivalent.
The qsort standard library function is very useful function that is designed to sort an array by a key value of any type into ascending order, as long as the elements of the array are of fixed type.
qsort is prototyped in (stdlib.h):

void qsort(void *base, size_t num_elements, size_t element_size,
   int (*compare)(void const *, void  const *));

The argument base points to the array to be sorted, num_elements indicates how long the array is, element_size is the size in bytes of each array element and the final argument compare is a pointer to a function.
qsort calls the compare function which is user defined to compare the data when sorting. Note that qsort maintains it's data type independence by giving the comparison responsibility to the user. The compare function must return certain (integer) values according to the comparison result:

less than zero

: if first value is less than the second value

zero

: if first value is equal to the second value

greater than zero

: if first value is greater than the second value

Some quite complicated data structures can be sorted in this manner. For example, to sort the following structure by integer key:

typedef struct {
        int   key;
        struct other_data;
} Record;

We can write a compare function, record_compare:

int record\_compare(void const *a, void  const *a)
  {  return ( ((Record *)a)->key - ((Record *)b)->key );
  }

Assuming that we have an array of array_length Records suitably filled with date we can call qsort like this:

qsort( array, arraylength, sizeof(Record), record_compare);

Further examples of standard library and system calls that use pointers to functions may be found in Chapters 15.4 and 19.1.

Exercises

Exercise 12476
Write a program last that prints the last n lines of its text input. By default n should be 5, but your program should allow an optional argument so that

last -n

prints out the last n lines, where n is any integer. Your program should make the best use of available storage. (Input of text could be by reading a file specified from the command or reading a file from standard input)

Exercise 12477
Write a program that sorts a list of integers in ascending order. However if a -r flag is present on the command line your program should sort the list in descending order. (You may use any sorting routine you wish)
Exercise 12478
Write a program that reads the following structure and sorts the data by keyword using qsort

typedef struct {
        char   keyword[10];
        int    other_data;
} Record;

Exercise 12479
An insertion sort is performed by adding values to an array one by one. The first value is simply stored at the beginning of the array. Each subsequent value is added by finding its ordered position in the array, moving data as needed to accommodate the value and inserting the value in this position.
Write a function called insort that performs this task and behaves in the same manner as qsort, i.e it can sort an array by a key value of any type and it has similar prototyping.

Pointers

  Pointer are a fundamental part of C. If you cannot use pointers properly then you have basically lost all the power and flexibility that C allows. The secret to C is in its use of pointers. C uses pointers a lot. Why?:

• It is the only way to express some computations.
• It produces compact and efficient code.
• It provides a very powerful tool.

C uses pointers explicitly with:

• Arrays,
• Structures,
• Functions.

NOTE: Pointers are perhaps the most difficult part of C to understand. C's implementation is slightly different DIFFERENT from other languages.

What is a Pointer?

A pointer is a variable which contains the address in memory of another variable. We can have a pointer to any variable type.
The unary or monadic operator & gives the ``address of a variable''.
The indirection or dereference operator * gives the ``contents of an object pointed to by a pointer''.
To declare a pointer to a variable do:
   int *pointer;
NOTE: We must associate a pointer to a particular type: You can't assign the address of a short int to a long int, for instance.
Consider the effect of the following code:

   int x = 1, y = 2;
   int *ip;
 
   ip = &x;
 

y = *ip;
 

x = ip;
 

   *ip = 3;

It is worth considering what is going on at the machine level in memory to fully understand how pointer work. Consider Fig. 9.1. Assume for the sake of this discussion that variable x resides at memory location 100, y at 200 and ip at 1000. Note A pointer is a variable and thus its values need to be stored somewhere. It is the nature of the pointers value that is new.
 
Fig. 9.1 Pointer, Variables and Memory Now the assignments x = 1 and y = 2 obviously load these values into the variables. ip is declared to be a pointer to an integer and is assigned to the address of x (&x). So ip gets loaded with the value 100.
Next y gets assigned to the contents of ip. In this example ip currently points to memory location 100 -- the location of x. So y gets assigned to the values of x -- which is 1.
We have already seen that C is not too fussy about assigning values of different type. Thus it is perfectly legal (although not all that common) to assign the current value of ip to x. The value of ip at this instant is 100.
Finally we can assign a value to the contents of a pointer (*ip).
IMPORTANT: When a pointer is declared it does not point anywhere. You must set it to point somewhere before you use it.
So ...

   int *ip;
 
   *ip = 100;

will generate an error (program crash!!).
The correct use is:

   int *ip;
   int x;
 
   ip = &x;
   *ip = 100;

We can do integer arithmetic on a pointer:

   float *flp, *flq;
 
   *flp = *flp + 10;
 
   ++*flp;
 
   (*flp)++;
 
   flq = flp;

NOTE: A pointer to any variable type is an address in memory -- which is an integer address. A pointer is definitely NOT an integer.
The reason we associate a pointer to a data type is so that it knows how many bytes the data is stored in. When we increment a pointer we increase the pointer by one ``block'' memory.
So for a character pointer ++ch_ptr adds 1 byte to the address.
For an integer or float ++ip or ++flp adds 4 bytes to the address.
Consider a float variable (fl) and a pointer to a float (flp) as shown in Fig. 9.2.
 
Fig. 9.2 Pointer Arithmetic Assume that flp points to fl then if we increment the pointer ( ++flp) it moves to the position shown 4 bytes on. If on the other hand we added 2 to the pointer then it moves 2 float positions i.e 8 bytes as shown in the Figure.

Pointer and Functions

Let us now examine the close relationship between pointers and C's other major parts. We will start with functions.
When C passes arguments to functions it passes them by value.
There are many cases when we may want to alter a passed argument in the function and receive the new value back once to function has finished. Other languages do this (e.g. var parameters in PASCAL). C uses pointers explicitly to do this. Other languages mask the fact that pointers also underpin the implementation of this.
The best way to study this is to look at an example where we must be able to receive changed parameters.
Let us try and write a function to swap variables around?
The usual function call:

    swap(a, b)   WON'T WORK.

Pointers provide the solution: Pass the address of the variables to the functions and access address of function.

Thus our function call in our program would look like this:

    swap(&a, &b)

The Code to swap is fairly straightforward:

    void swap(int *px, int *py)
 
      { int temp;
 
     temp = *px;
     /* contents of pointer */ 
 
     *px = *py;
     *py = temp;
   }

We can return pointer from functions. A common example is when passing back structures. e.g.:

typedef struct {float x,y,z;} COORD;
 
   main()
 
    {  COORD p1, *coord_fn();
      /* declare fn to return ptr of
       COORD type */ 
 
       ....
       p1 = *coord_fn(...);
     /* assign contents of address returned */
       ....
     }

   COORD *coord_fn(...)
 
    {  COORD p;
 
       .....
       p = ....;
       /* assign structure values */ 
 
       return &p;
       /* return address of p */
     }

Here we return a pointer whose contents are immediately unwrapped into a variable. We must do this straight away as the variable we pointed to was local to a function that has now finished. This means that the address space is free and can be overwritten. It will not have been overwritten straight after the function ha squit though so this is perfectly safe.

Pointers and Arrays

Pointers and arrays are very closely linked in C.

Hint: think of array elements arranged in consecutive memory locations.

Consider the following:

   int a[10], x;
   int *pa;
 
   pa = &a[0];  /* pa pointer to address of a[0] */
 
   x = *pa;
   /* x = contents of pa (a[0] in this case) */

 
Fig. 9.3 Arrays and Pointers
To get somewhere in the array (Fig. 9.3) using a pointer we could do:

   pa + i a[i]

WARNING: There is no bound checking of arrays and pointers so you can easily go beyond array memory and overwrite other things.

C however is much more subtle in its link between arrays and pointers.

For example we can just type

   pa = a;

instead of

   pa = &a[0]

and

   a[i] can be written as *(a + i).
i.e. &a[i] a + i.

We also express pointer addressing like this:

   pa[i] *(pa + i).

However pointers and arrays are different:

• A pointer is a variable. We can do
  pa = a and pa++.
• An Array is not a variable. a = pa and a++ ARE ILLEGAL.

This stuff is very important. Make sure you understand it. We will see a lot more of this.

We can now understand how arrays are passed to functions.

When an array is passed to a function what is actually passed is its initial elements location in memory.

So:

   strlen(s) strlen(&s[0])

This is why we declare the function:

     int strlen(char s[]);

An equivalent declaration is : int strlen(char *s);
since char s[] char *s.

strlen() is a standard library function (Chapter 18) that returns the length of a string. Let's look at how we may write a function:

   int strlen(char *s)
     { char *p = s;
 
     while (*p != `);
       p++;
     return p-s;
     }

Now lets write a function to copy a string to another string. strcpy() is a standard library function that does this.

   void strcpy(char *s, char *t)
     {  while ( (*s++ = *t++) != `);}

This uses pointers and assignment by value.

Very Neat!!

NOTE: Uses of Null statements with while.

Arrays of Pointers

We can have arrays of pointers since pointers are variables.

Example use:

Sort lines of text of different length.

NOTE: Text can't be moved or compared in a single operation.

Arrays of Pointers are a data representation that will cope efficiently and conveniently with variable length text lines.

How can we do this?:

• Store lines end-to-end in one big char array (Fig. 9.4). n will delimit lines.
• Store pointers in a different array where each pointer points to 1st char of each new line.
• Compare two lines using strcmp() standard library function.
• If 2 lines are out of order -- swap pointer in pointer array (not text).

 
Fig. 9.4 Arrays of Pointers (String Sorting Example)
This eliminates:

• complicated storage management.
• high overheads of moving lines.

Multidimensional arrays and pointers

We should think of multidimensional arrays in a different way in C:

A 2D array is really a 1D array, each of whose elements is itself an array

Hence

  a[n][m] notation.

Array elements are stored row by row.

When we pass a 2D array to a function we must specify the number of columns -- the number of rows is irrelevant.

The reason for this is pointers again. C needs to know how many columns in order that it can jump from row to row in memory.

Considerint a[5][35] to be passed in a function:

We can do:

   f(int a[][35]) {.....}

or even:

   f(int (*a)[35]) {.....}

We need parenthesis (*a) since [] have a higher precedence than *

So:

   int (*a)[35]; declares a pointer to an array of 35 ints.

   int *a[35]; declares an array of 35 pointers to ints.

Now lets look at the (subtle) difference between pointers and arrays. Strings are a common application of this.

Consider:
   char *name[10];
   char Aname[10][20];

We can legally do name[3][4] and Aname[3][4] in C.
However

• Aname is a true 200 element 2D char array.
• access elements via
     20*row + col + base_address
  in memory.
• name has 10 pointer elements.

NOTE: If each pointer in name is set to point to a 20 element array then and only then will 200 chars be set aside (+ 10 elements).

The advantage of the latter is that each pointer can point to arrays be of different length.

Consider:

   char *name[] = { ``no month'', ``jan'',
    ``feb'', ... };
   char Aname[][15] = { ``no month'', ``jan'',
    ``feb'', ... };

 
Fig.  2D Arrays and Arrays of Pointers

Static Initialisation of Pointer Arrays

Initialisation of arrays of pointers is an ideal application for an internal static array.

some_fn()
    { static char *months = { ``no month'',
       ``jan'', ``feb'',
       ...};
 
     }

static reserves a private permanent bit of memory.

Pointers and Structures

These are fairly straight forward and are easily defined. Consider the following:

   struct COORD {float x,y,z;} pt;
   struct COORD *pt_ptr;
 

pt_ptr = &pt; /* assigns pointer to pt */

the operator lets us access a member of the structure pointed to by a pointer.i.e.:
   pt_ptrx = 1.0;
   pt_ptry = pt_ptry - 3.0;


Example: Linked Lists

  typedef struct {  int value;
       ELEMENT *next;
     } ELEMENT; 
 

ELEMENT n1, n2;
 

n1.next = &n2;

 
Fig.  Linking Two Nodes NOTE: We can only declare next as a pointer to ELEMENT. We cannot have a element of the variable type as this would set up a recursive definition which is NOT ALLOWED. We are allowed to set a pointer reference since 4 bytes are set aside for any pointer.
The above code links a node n1 to n2 (Fig. 9.6) we will look at this matter further in the next Chapter.

Common Pointer Pitfalls

Here we will highlight two common mistakes made with pointers.

Not assigning a pointer to memory address before using it

  int *x;
 
   *x = 100;
 
we need a physical location say: int y;
 
   x = &y;
   *x = 100;

This may be hard to spot. NO COMPILER ERROR. Also x could some random address at initialisation.

Illegal indirection

Suppose we have a function malloc() which tries to allocate memory dynamically (at run time) and returns a pointer to block of memory requested if successful or a NULL pointer
otherwise.

  char *malloc() -- a standard library function (see later).

Let us have a pointer: char *p;

Consider:

  *p = (char *) malloc(100);    /* request 100 bytes of memory */

  *p = `y';

There is mistake above. What is it?


No * in
   *p = (char *) malloc(100);

Malloc returns a pointer. Also p does not point to any address.

The correct code should be:

   p = (char *) malloc(100);

If code rectified one problem is if no memory is available and p is NULL. Therefore we can't do:
   *p = `y';.

A good C program would check for this:

  p = (char *) malloc(100);
   if ( p == NULL)
     { printf(``Error: Out of Memory n'');
       exit(1);
     }
   *p = `y';

Exercise

Exercise 12453
Write a C program to read through an array of any type using pointers. Write a C program to scan through this array to find a particular value.
Exercise 12454
Write a program to find the number of times that a given word(i.e. a short string) occurs in a sentence (i.e. a long string!).
Read data from standard input. The first line is a single word, which is followed by general text on the second line. Read both up to a newline character, and insert a terminating null before processing.
Typical output should be:

The word is "the".
        The sentence is "the cat sat on the mat".
       The word occurs 2 times.

Exercise 12455
Write a program that takes three variable (a, b, b) in as separate parameters and rotates the values stored so that value a goes to be, b, to c and c to a.