Recitation R3: CS 270 Computer Organization

Recitation R3 - Bit Fields in C

Due Fri, Sep. 9 at 5:00pm. No late submissions.

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 P3. 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 (5 functions) that enables getting and setting bits and fields in a binary 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 ...
    c11 -g -Wall -c field.c

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

    Linking all object modules ...
    c11 -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 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 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 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 manipulate multiple bits at once (as in the getField and setField functions). The most common need 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).

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 the rest of the number is padded with 0's (because isSigned = false, i.e., the field is considered to be unsigned). 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 is still all the way to the right. However, the rest of the number is padded with 1's (because isSigned = true, i.e., the field is considered to be signed and the leading bit in the field is 1, so the number is negative and the sign must be extended). Here is yet another example:

COMMAND:
./testField getField 0x00001234 7 4 0

ARGUMENTS:
old      = 0x00001234 = 0000 0000 0000 0000 0001 0010 0011 0100
hi       = 7
lo       = 4
isSigned = true

RETURN:
         = 0xFFFFFFF3 = 0000 0000 0000 0000 0000 0000 0000 0011

The field is still all the way to the right and the rest of the number is padded with 0's (because isSigned = true, i.e., the field is considered to be signed and the leading bit in the field is 0, so the number is positive and the sign must be extended).

Example for setField

The following is an example of replacing bits 4-7 in a 32-bit integer with a new value, i.e. setField:

COMMAND:
./testField setField 0x00001234 7 4 25

ARGUMENTS:
old         = 0x00001234  0000 0000 0000 0000 0001 0010 0011 0100 
new         = 0x00000019  0000 0000 0000 0000 0000 0000 0001 1001
hi          = 7
lo          = 4

Notice how we are only going to use the lower 4 bits of the new value: because
the size of the field is 4 (as determined by hi and lo).

STEP 1) Create a mask for bits 4-7:

mask        = 0x000000F0  0000 0000 0000 0000 0000 0000 1111 0000

STEP 2) Use inverted mask to clear bits 4-7 in old value:

mask        = 0x000000F0  0000 0000 0000 0000 0000 0000 1111 0000
~mask       = 0xFFFFFF0F  1111 1111 1111 1111 1111 1111 0000 1111
old         = 0x00001234  0000 0000 0000 0000 0001 0010 0011 0100 
old & ~mask = 0x00001204  0000 0000 0000 0000 0001 0010 0000 0100 

STEP 3) Shift the new value to be in the bits 4-7:

new         = 0x00000019  0000 0000 0000 0000 0000 0000 0001 1001
new << 4    = 0x00000190  0000 0000 0000 0000 0000 0001 1001 0000

STEP 4) Clear any other bits besides 4-7 in new value:

mask        = 0x000000F0  0000 0000 0000 0000 0000 0000 1111 0000
new         = 0x00000190  0000 0000 0000 0000 0000 0001 1001 0000
new & mask  = 0x00000090  0000 0000 0000 0000 0000 0000 1001 0000

STEP 5) Combine the old and new values, and return the result:

old         = 0x00001204  0000 0000 0000 0000 0001 0010 0000 0100 
new         = 0x00000090  0000 0000 0000 0000 0000 0000 1001 0000
old | new   = 0x00001294  0000 0000 0000 0000 0001 0010 1001 0100 

RESULT
setField: set bits 4:7 in 0x1234 to 0x19 = 0x1294

Completing the Code

Before attempting to write any of the functions of field.c, study the documentation in 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 including empty lines (you could make it more compact):

getBit()   - 7 lines
setBit()   - 2 lines
clearBit() - 2 lines
getField() - 12 lines
setBit()   - 6 lines

Grading Criteria

There will be no hidden testing for R3. Preliminary testing tests all functions.

100 points for perfect submission.
0 points for no submission, will not compile, submitted class file, etc.
Each test can make multiple calls to the function being tested, with different values.
Tests
- testCompile: checks that program compiles. (0 points)
- test1: calls testField with getBit to check the getBit function. (15 points)
- test2: calls testField with setBit to check the setBit function. (15 points)
- test3: calls testField with clearBit to check the clearBit function. (10 points)
- test4: calls testField with getField to check the getField function, with isSigned false. (20 points)
- test5: calls testField with getField to check the getField function, with isSigned true. (20 points)
- test6: calls testField with setField to check the setField function. (20 points)

Submit the single file field.c to the Checkin tab on the course website to get credit for this lab. The grade you will get for this recitation is the grade given by the autograder.