Week 02 Tutorial Questions

Objectives

understand how raw binary data is associated with a context to provide meaningful information to a computer
practise using the bitwise operators in C to manipulate binary representations of data
introduce how specific tasks and hardware may use custom formats of binary data

When should the types in stdint.h be used:

#include <stdint.h>

                 // range of values for type
                 //             minimum               maximum
    int8_t   i1; //                 -128                  127
    uint8_t  i2; //                    0                  255
    int16_t  i3; //               -32768                32767
    uint16_t i4; //                    0                65535
    int32_t  i5; //          -2147483648           2147483647
    uint32_t i6; //                    0           4294967295
    int64_t  i7; // -9223372036854775808  9223372036854775807
    uint64_t i8; //                    0 18446744073709551615

How can you tell if an integer constant in a C program is decimal (base 10), hexadecimal (base 16), octal (base 8) or binary (base 2)?
Sidenote: do you think this is good language design?
Language trivia: what base is the constant 0 in C?
Show what the following decimal values look like in 8-bit binary, 3-digit octal, and 2-digit hexadecimal:
1. 1
2. 8
3. 10
4. 15
5. 16
6. 100
7. 127
8. 200
How could I write a C program to answer this question?

Discuss the starting code for sixteen_out, one of this week's lab exercises. In particular, what does this code (from the provided main) do?

    long l = strtol(argv[arg], NULL, 0);
    assert(l >= INT16_MIN && l <= INT16_MAX);
    int16_t value = l;

    char *bits = sixteen_out(value);
    printf("%s\n", bits);

    free(bits);

Assume that we have the following 16-bit variables defined and initialised:
```
uint16_t a = 0x3535, b = 0x25fA, c = 0x4311;
```
What are the values of the following expressions:
1. a | b (bitwise OR)
2. a & b (bitwise AND)
3. a ^ b (bitwise XOR)
4. a & ~b (bitwise AND)
5. c << 6 (left shift)
6. a >> 4 (right shift)
7. a & (b << 1)
8. b | c
9. a & ~c
Give your answer in hexadecimal, but you might find it easier to convert to binary to work out the solution.
Write a function with the following prototype that returns the given value with the nth bit set to 1. Assume the LSB is the 0th bit. If the value of n is out of range, simply do nothing.
```
unsigned char value set_nth_bit(unsigned char value, unsigned char n);
```
Write a function with the following prototype that returns the given value with the nth bit set to 0. Assume the LSB is the 0th bit. If the value of n is out of range, simply do nothing.
```
unsigned char unset_nth_bit(unsigned char value, unsigned char n);
```
Write a C function, six_middle_bits, which, given a uint32_t, extracts and returns the middle six bits.
Given the following type definition
```
typedef unsigned int Word;
```
Write a function
```
Word reverseBits(Word w);
```
... which reverses the order of the bits in the variable w.
For example: If w == 0x01234567, the underlying bit string looks like:
```
0000 0001 0010 0011 0100 0101 0110 0111
```
which, when reversed, looks like:
```
1110 0110 1010 0010 1100 0100 1000 0000
```
which is 0xE6A2C480 in hexadecimal.

Use the following set definition to represent a set of small non-negative integers

typedef uint64_t set;

Use bitoperations to implement the following functions for your datatype

set set_add(int x, set a);
set set_union(set a, set b);
set set_intersection(set a, set b);
int set_member(int x, set a);
int set_cardinality(set a);

You can use the following code to run your functions

#include <stdio.h>
#include <stdint.h>
#include <assert.h>

typedef uint64_t set;
#define MAX_SET_MEMBER ((int)(8 * sizeof(set) - 1))
#define EMPTY_SET 0

set set_add(int x, set a);
set set_union(set a, set b);
set set_intersection(set a, set b);
int set_member(int x, set a);
int set_cardinality(set a);


//provided functions
set set_read(char *prompt);
void set_print(char *description, set a);
void print_bits_hex(char *description, set value);
int get_nth_bit(uint64_t value, int n);
void print_bits(uint64_t value, int how_many_bits);

int main(void) {
    printf("Set members can be 0-%d, negative number to finish\n",
           MAX_SET_MEMBER);
    set a = set_read("Enter set a: ");
    set b = set_read("Enter set b: ");

    print_bits_hex("a = ", a);
    print_bits_hex("b = ", b);
    set_print("a = ", a);
    set_print("b = ", b);
    set_print("a union b = ", set_union(a, b));
    set_print("a intersection b = ", set_intersection(a, b));
    printf("cardinality(a) = %d\n", set_cardinality(a));
    printf("is_member(42, a) = %d\n", (int)set_member(42, a));

    return 0;
}

set set_read(char *prompt) {
    printf("%s", prompt);
    set a = EMPTY_SET;
    int x;
    while (scanf("%d", &x) == 1 && x >= 0) {
        a = set_add(x, a);
    }
    return a;
}

// print out member of the set in increasing order
// for example {5,11,56}
void set_print(char *description, set a) {
    printf("%s", description);
    printf("{");
    int n_printed = 0;
    for (int i = 0; i < MAX_SET_MEMBER; i++) {
        if (set_member(i, a)) {
            if (n_printed > 0) {
                printf(",");
            }
            printf("%d", i);
            n_printed++;
        }
    }
    printf("}\n");
}


// print description then binary, hex and decimal representation of value
void print_bits_hex(char *description, set value) {
    printf("%s", description);
    print_bits(value, 8 * sizeof value);
    printf(" = 0x%08jx = %jd\n", (intmax_t)value, (intmax_t)value);
}

// extract the nth bit from a value
int get_nth_bit(uint64_t value, int n) {
    // shift the bit right n bits
    // this leaves the n-th bit as the least significant bit
    uint64_t shifted_value = value >> n;

    // zero all bits except the the least significant bit
    int bit = shifted_value & 1;

    return bit;
}

// print the bottom how_many_bits bits of value
void print_bits(uint64_t value, int how_many_bits) {
    // print bits from most significant to least significant

    for (int i = how_many_bits - 1; i >= 0; i--) {
        int bit = get_nth_bit(value, i);
        printf("%d", bit);
    }
}

Consider a scenario where we have the following flags controlling access to a device.
```
#define READING   0x01
#define WRITING   0x02
#define AS_BYTES  0x04
#define AS_BLOCKS 0x08
#define LOCKED    0x10
```
The flags are contained in an 8-bit register, defined as:
```
unsigned char device;
```
Write C expressions to implement each of the following:
1. mark the device as locked for reading bytes
2. mark the device as locked for writing blocks
3. set the device as locked, leaving other flags unchanged
4. remove the lock on a device, leaving other flags unchanged
5. switch a device from reading to writing, leaving other flags unchanged
6. swap a device between reading and writing, leaving other flags unchanged
You've been hired to write a driver to control a printer/scanner combo. The printer communicates through a series of flags that can be either 0 or 1:
- NO_INK (read/write): The printer sets this flag when it's out of ink. You must unset it when the ink is replaced.
- COLOUR (write): You set this flag to tell the printer to scan/print in colour.
- SELECT_PRINT (write): You set this flag to select printing mode.
- SELECT_SCAN (write): You set this flag to select scanning mode.
- START (read/write): You set this flag to do the selected task (print or scan). The printer will unset this when it's finished.
Don't worry about how the actual file you're printing/scanning gets to and from the printer. We're only interested in the control signals.

One way to implement this is to have a variable for each flag:
```
int NO_INK = 0;       // Ink levels OK
int COLOUR = 1;       // Printing/scanning in colour
int SELECT_PRINT = 1; // Print mode selected
int SELECT_SCAN = 0;  // Scan mode not selected
int START = 0;        // Printing/scanning hasn't started
```
However, this is a waste of space, and in hardware, every bit matters! Each integer takes up 32 bits, but we only need to store 1 bit of information for each flag. Instead, we can pack all the flags into a single 8 bit (1 byte) integer, and use the individual bits to represent the flags:
```
printerControl = 0 0 0 0 0 0 0 0
                       ^ ^ ^ ^ ^
                       | | | | |
                       | | | | L [NO_INK]
                       | | | L [COLOUR]
                       | | L [SELECT_PRINT]
                       | L [SELECT_SCAN]
                       L [START]
```
The most significant 3 bits are unused.
In C, that would look like:
```
#include <stdint.h>

uint8_t printerControl = 0; // 0b 0000 0000

// Whether the printer is out of ink
#define NO_INK (0x1)       // 0b 0000 0001
// Whether to print/scan in colour
#define COLOUR (0x2)       // 0b 0000 0010
// Select print mode
#define SELECT_PRINT (0x4) // 0b 0000 0100
// Select scan mode
#define SELECT_SCAN (0x8)  // 0b 0000 1000
// Start print/scan
#define START (0x10)       // 0b 0001 0000
```
For the following questions, assume the C code above is included globally. Don't change any other flags other than the ones specified.
Write a function:
1. that prints (to terminal) whether the printer is out of ink.
2. that tells the printer the ink has been replaced.
3. to use colour and select scan mode. Assume no mode has been selected yet.
4. that toggles between print and scan mode. Assume 1 mode is already selected.
5. (Extension question) to start printing/scanning. It should:
  1. check that one (and only one) mode is selected
  2. check there's ink if printing.
  3. print (to terminal) what it's doing and any error messages.
  4. wait until the printing/scanning is finished and print a 'finished' message. Since there isn't an actual printer on the other side, a correct implementation of this will infinite loop and never print 'finished'.
On a machine with 16-bit ints, the C expression (30000 + 30000) yields a negative result.
Why the negative result? How can you make it produce the correct result?
Assume that the following hexadecimal values are 16-bit twos-complement. Convert each to the corresponding decimal value.
1. 0x0013
2. 0x0444
3. 0x1234
4. 0xffff
5. 0x8000
Give a representation for each of the following decimal values in 16-bit twos-complement bit-strings. Show the value in binary, octal and hexadecimal.
1. 1
2. 100
3. 1000
4. 10000
5. 100000
6. -5
7. -100

Revision questions

The following questions are primarily intended for revision, either this week or later in session.
Your tutor may still choose to cover some of these questions, time permitting.

Consider the following struct definition defining a type for points in a three-dimensional space:

typedef struct Coord {
    int x;
    int y;
    int z;
} Coord;

and the program fragment using Coord variables and pointers to them:

{
    Coord coords[10];
    Coord a = { .x = 5, .y = 6, .z = 7 };
    Coord b = { .x = 3, .y = 3, .z = 3 };
    Coord *p = &a;

    /*** A ***/
    (*p).x = 6;
    p->y++;
    p->z++;
    b = *p;
    /*** B ***/

}

Draw diagrams to show the state of the variables a, b, and p, at points A and B.
Why would a statement like *p.x++; be incorrect?

How does the C library function

void *realloc(void *ptr, size_t size);

differ from

void *malloc(size_t size);

What is the effect of each of the static declarations in the following program fragment:

#include <stdio.h>

static int x1;
...

static int f(int n) {
    static int x2 = 0;
    ...
}