Recitation R3: CS 270 Computer Organization

Recitation R3 - Bit Fields in C

No submission.

This recitation has five objectives:

to use a Makefile for compiling C programs
to write a C program that manipulates the bits of integer values,
to learn the C language operators for binary numbers,
to build a more complex C program with multiple files,
to see if you can follow directions!

About The Recitation

This recitation will be helpful for assignment P2. You will learn how to use the C language operators for binary and (&), binary or (|), and binary not (~). You will use the C language bit shift operators (<< and >>). We will also introduce Makefiles.

The goal of the recitation is to implement a small C library (4 functions) that enables some useful operations on an integer number. This is especially useful for playing around with numerical representations. For example, you could build a new floating point number from scratch by setting the sign bit, exponent, and mantissa, or you could analyze an existing floating point number by extracting the same fields. We will use it later in this class for understanding number representations and for converting LC3 assembly code into machine code. To get started, read the Getting Started section below and then study the documentation for field.h in the Files tab to understand the details of the assignment.

Getting Started

Perform the following steps

Create a folder for this recitation named R3. Copy the four files below into this directory. It is easiest to right click on the link, and use Save Link As ... to save the file in your directory. While you may use copy/paste to save the file, it may convert the required tabs of Makefile into spaces.
1. field.h (do not modify)
2. field.c (complete this file)
3. Makefile (do not modify)
4. testField.c (do not modify)
Open a terminal and make sure you are in the directory you created. The cd command can be used for this.

In the terminal, do an 'ls' command. You may need to rename Makefile.txt as Makefile, if the browser renamed it during download. Next run 'make', and you should see the following output:

    Compiling each C source file separately ...
    gcc -g -Wall -c field.c

    Compiling each C source file separately ...
    gcc -g -Wall -c testField.c

    Linking all object modules ...
    gcc -g -Wall field.o testField.o  -o testField

In the terminal type ./testField and read how to run the test program supplied with the recitation.
For example, type ./testField bin 11259375 and you should see the output:
```
    dec: 11259375  hex: 0xABCDEF  bin: 0000-0000-1010-1011-1100-1101-1110-1111
```
This shows you the representation of decimal number 11259375 in hexadecimal and 32-bit binary.

You now have a functioning program. All the commands run. However, only bin will produce correct results at this point.

Computing Bit Masks

In this recitation you will make extensive use of bit masks in order to get, set, or clear individual bits in an integer. Building a bit mask can be challenging, but here are some guidelines:

If you analyze the truth table for the AND (&) operator, you will notice that X & 1 = X and X & 0 = 0 (where X is any bit). This makes the AND operator perfect for isolating bits or for clearing bits. Below is an example for isolating bit 3 in a value:
```
    value            = 0000 0000 0000 0000 0001 0010 0011 1100
    mask             = 0000 0000 0000 0000 0000 0000 0000 1000
                       ---------------------------------------
    value & mask     = 0000 0000 0000 0000 0000 0000 0000 1000
```
Notice that the mask was built by placing a 1 in the position of interest. How would you compute such mask? If you know that the position you want is always bit 3, then you can hard code this mask:
```
    int mask = 0x00000008;
```
Think about how you could build a mask where the position you are interested in is stored in a variable (hint: use a shift operator).

How about clearing a bit? The example below shows how to clear bit 4 in a value:
```
    value            = 0000 0000 0000 0000 0001 0010 0011 1100
    mask             = 1111 1111 1111 1111 1111 1111 1110 1111
                       ---------------------------------------
    value & mask     = 0000 0000 0000 0000 0001 0010 0010 1100
```
Notice that the mask was built by placing a 0 in the position of interest and 0 elsewhere. Again, how would you compute such mask if the position of interest is stored in a variable? (hint: look at how this mask is related to the mask used for extracting a bit)
If you analyze the truth table for the OR (|) operator, you will notice that X | 1 = 1 and X | 0 = X (where X is any bit). This makes the OR operator perfect for setting bits. Below is an example for setting bit 7 in a value:
```
    value            = 0000 0000 0000 0000 0001 0010 0011 1100
    mask             = 0000 0000 0000 0000 0000 0000 1000 0000
                       ---------------------------------------
    value | mask     = 0000 0000 0000 0000 0001 0010 1011 1100
```
Notice that the mask was built by placing a 1 in the position of interest. How would you compute such mask if the position of interest is stored in a variable? (hint: refer to the mask computation for extracting a bit)

The previous examples dealt with one bit at a time. Sometimes, however, you may need to deal with multiple bits at once (as in the getField function). The most common obstacle when doing this is getting a group of contiguous 1's. For example, suppose you want to create the following mask without hard coding it:

  mask = 0000 0000 0000 0000 0000 0000 0111 0000

How would you go about doing this without using loops? (hint: start from 1 and manipulate it using the shift and subtraction operators).

Note: in GCC, when you shift a signed value to the right, the compiler will do an arithmetic shift. This means that it will preserve the sign. For example, if you shift a negative number to the right, it will bring 1's on the right instead of 0's. If you shift a positive number to the right, it will bring 0's on the right. This will not happen if you shift an unsigned number (for example, unsigned int). In this case, it will always bring 0's on the right (this is called a logical shift). Try the following program (compile with gcc -o test test.c):

#include <stdio.h>

int main() {
  int a = 0xABCD0123;           // Negative number
  a = a >> 4;                   // Arithmetic shift
  printf("%08X\n", a);          // Print in hexadecimal

  int b = 0x7BCD0123;           // Positive number
  b = b >> 4;                   // Arithmetic shift
  printf("%08X\n", b);          // Print in hexadecimal

  unsigned int c = 0xFBCD0123;  // Unsigned number
  c = c >> 4;                   // Logical shift
  printf("%08X\n", c);          // Print in hexadecimal

  return 0;
}

Examples for getField

COMMAND:
./testField getField 0x000012B4 7 4 0

ARGUMENTS:
old      = 0x000012B4 = 0000 0000 0000 0000 0001 0010 1011 0100
hi       = 7
lo       = 4
isSigned     = false

RETURN:
         = 0x0000000B = 0000 0000 0000 0000 0000 0000 0000 1011

Notice how the field is all the way to the right and no further modifications were made. Here is another example:

COMMAND:
./testField getField 0x000012B4 7 4 1

ARGUMENTS:
old      = 0x000012B4 = 0000 0000 0000 0000 0001 0010 1011 0100
hi       = 7
lo       = 4
isSigned     = true

RETURN:
         = 0xFFFFFFFB = 1111 1111 1111 1111 1111 1111 1111 1011

The field in question is the same as in the previous example. However, we had to sign extend it based on the left most bit (LSB) of the field, which in 1 in this case, meaning that the number is negative.

Completing the Code

Before attempting to write any of the functions of field.c, study the documentation found in the files tab. Plan what you need to do before writing code. The best way to be successful is to write, compile, and test a single function at a time.

Here are the line counts for my implementation:

getBit()   - 1 line
setBit()   - 1 lines
clearBit() - 1 lines
getField() - 4 lines