Objectives

  • Learn to perform bit manipulations.

  • Learn to identify potential problems related to dynamic memory management.

Exercise 1: (BitOps)

Begin by downloading the starter file for this lab (from the top of this document) and unzip its content to a directory of your choice. Then implement in the bit_ops.c file, the functions get_bit(), set_bit() and flip_bit() (see description below). You can ONLY use bit operations like AND (&), OR (|), XOR (^), NOT (~), left shift (<<) and right shift (>>). You cannot use for/while/do loops or if/else and switch/case branch statements. You also cannot use arithmetic operations (modulo (%), division, subtraction, addition or multiplication) for this exercise.

// Return the n-th bit of x.
// You may assume 0 <= n <= 31
bool get_bit(uint32_t x, uint8_t n);

// Set the n-th bit of the value of x to v.
// You may assume 0 <= n <= 31, and v is either 0 or 1
void set_bit(uint32_t *x, uint8_t n, bool v);

// Invert the n-th bit of the value of x.
// You may assume 0 <= n <= 31
void flip_bit(uint32_t *x, uint8_t n);

Tasks to carry out:

After completing the implementation of the get_bit(), set_bit() and flip_bit() functions, compile and run the program using the commands below (under UN*X environment ).

$ make bit_ops
$ ./bit_ops

Correct execution of the program will display on your screen the results of some validation tests (tests which allow you to check whether you have correctly implemented the above-mentioned functions).

Testing get_bit()

get_bit(0x0000004e,0): 0x00000000, correct
get_bit(0x0000004e,1): 0x00000001, correct
get_bit(0x0000004e,5): 0x00000000, correct
get_bit(0x0000001b,3): 0x00000001, correct
get_bit(0x0000001b,2): 0x00000000, correct
get_bit(0x0000001b,9): 0x00000000, correct

Testing set_bit()

set_bit(0x0000004e,2,0): 0x0000004a, correct
set_bit(0x0000006d,0,0): 0x0000006c, correct
set_bit(0x0000004e,2,1): 0x0000004e, correct
set_bit(0x0000006d,0,1): 0x0000006d, correct
set_bit(0x0000004e,9,0): 0x0000004e, correct
set_bit(0x0000006d,4,0): 0x0000006d, correct
set_bit(0x0000004e,9,1): 0x0000024e, correct
set_bit(0x0000006d,7,1): 0x000000ed, correct

Testing flip_bit()

flip_bit(0x0000004e,0): 0x0000004f, correct
flip_bit(0x0000004e,1): 0x0000004c, correct
flip_bit(0x0000004e,2): 0x0000004a, correct
flip_bit(0x0000004e,5): 0x0000006e, correct
flip_bit(0x0000004e,9): 0x0000024e, correct

Exercise 2: (binary2int)

Given a binary input string (e.g. ‘1110010’), your program should return its integer equivalent (e.g. 114). The program should stop conversion at the first invalid input (if any) and return the converted value.

Tasks to carry out:

Implement the bin2int_conversion() function in the bin2int.c file then compile and run the program (using the make command under UN*X - see below). Correct execution of the program will display on your screen the results of some validation tests.

$ make bin2int
$ ./bin2int

bin2int_conversion('10011001') = 153    ... correct
bin2int_conversion('10011101') = 157    ... correct
bin2int_conversion('01011001') = 89     ... correct
bin2int_conversion('00110001') = 49     ... correct
bin2int_conversion('10010.01') = 18     ... correct
bin2int_conversion('100+1111') = 4      ... correct
bin2int_conversion('101011001') = 345   ... correct
bin2int_conversion('0110000') = 48      ... correct

Exercise 3: (Memory access)

This exercise is designed to help you become familiar with data structures and the manipulation of pointers (i.e. memory addresses) in the C language. The vector.h, vector-test.c and vector.c files implement functionality for handling variable-length arrays.

Tasks to carry out:

  • Explain why bad_vector_new() and also_bad_vector_new() are bad implementations. Then, complete the vector_new(), vector_get(), vector_delete() and vector_set() functions in vector.c .

  • Also insert the prototypes of these functions in the vector.h header file so that the test code vector-test.c can run without any errors.

  • Finally, implement a rule for the vector-test target in the “Makefile” file.

Hints:

  • Check the already implemented functions and the comments provided to see how the data structures should be manipulated.

  • For consistency, it is assumed that all entries in the vector are equal to 0 unless explicitly set or modified by the user. Recall that the malloc() function does not zero the memory it allocates.

  • To explain why the two bad functions are incorrect, keep in mind that one of these functions will run correctly but there may be other (unseen) problems.

  • Make sure that your implementation of vector_new(), vector_get(), vector_delete() and vector_set() return the right results and manage memory correctly (details below).

# 1) to check the accuracy of the results
$ make vector-test
$ ./vector-test

# 2) to check memory management with Valgrind
$ make vector-memcheck

The rule vector-memcheck in the ‘Makefile’ file runs the following valgrind command on an executable file.

$ valgrind --tool=memcheck --leak-check=full --track-origins=yes [OS SPECIFIC ARGS]./<executable>

What does each of the parameters in the previous command mean (Hint: How to get help on an instruction under UN*X)? The last line displayed by valgrind will tell you at a glance if there were any errors while your program was running. Here is an example output from a buggy program:

==47132== ERROR SUMMARY: 1200039 errors from 24 contexts (deleted: 18 from 18)

If your program has errors, you can scroll through the command line output to view the details of each error. For this exercise, you can ignore any output that refers to “suppressed errors”. In a program without memory issues, your output will look like this:

==44144== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 18 from 18)

In the end, feel free to also use CGDB or add printf statements to vector.c and vector-test.c to debug your code.