10. Building Software and Bit Manipulation

SoftSys Lecture Notes, Monday 3/8 #

Building Software #

Warmup Question #

What’s the difference between

#include <string.h> (system folders, gcc searches through them)

and

#include "string.h (local file, looks in current directory)

string.h is small (18 KB)… why not just have it built in? (ie. why not just make a “string.h” instead of always using <string.h>)

Answer: Portability! Some values, like page size, differ among machines. System header files let you use settings relevant ot your OS and hardware to compile programs.

Header Files #

At a minimum, your header files need to specify the function signature, but you can also include a complete function in a header file.

With a headaer file, you can reuse common functions in multiple files.

The preprocessor replaces #include statements with the code of that file.

With multiple dependencies, you may end up calling #include on the same file multiple times - this can cause problems.

To avoid this, you can use include guards.

‘#’ <- preprocessor directive

#ifndef ADD_H_
#define ADD_H_

/* Code */

#endif

This makes the preprocessor ignore all future includes of this file. This goes in the header files (.h files).

You can also separate header files from source files. This is usefule when writing a Makefile to speed up your compile time.

Makefiles #

Makefiles help automate compilation. A makefile is a series of rules with dependencies.

foo: foo.c
    gcc -Wall -Wextra -pedantic -o foo foo.c
    
clean:
    rm foo

Makefiles will always frun the first rule by default.

Exercise #

The following C program reads three integers from the user and calculates a * (b + c) using the distributive property.

#include <stdio.h>

int add(int a, int b) {
  return a + b;
}

int mult(int a, int b) {
  if (b == 0) {
    return 0;
  }
  if (b < 0) {
    return -mult(a, -b);
  }
  return add(a, mult(a, b - 1));
}

int main() {
  int a, b, c;
  puts("Calculating a * (b + c)");
  puts("Enter value for a:");
  scanf("%d", &a);
  puts("Enter value for b:");
  scanf("%d", &b);
  puts("Enter value for c:");
  scanf("%d", &c);
  int ab = mult(a, b);
  int ac = mult(a, c);
  int total = add(ab, ac);
  printf("Using the distributive property, a * (b + c) is %d\n", total);
  return 0;
}
  1. Copy the add and mult functions into their own .h files. Don’t modify these files otherwise for now.
  2. Include these files in the file containing main and try to compile. What happens?
  3. If your program has successfully compiled, try running the function.
  4. Add the appropriate include statements and include guards to the .h files and try the above steps again. Now what happens?
  5. Now split the header files into function declarations in the .h files and the implementations in the .c files. What happens if you try to compile your main file now?
  6. Fix the compilation command to make your program build again (Head First C Chapter 4 talks about how to do this).
  7. Create a Makefile that automates this process. You should add one rule to this for now that depends on all of the files. Use make to compile your program.
  8. Now create rules to compile add and mult into .o files, and link these into your main program file. (Again, Head First C Chapter 4 talks about how to do this.)
all: dist

add.o: add.c add.h
    gcc -c -o add.o add.c
    
mult.o: mult.c mult.h add.o
    gcc -c -o mult.o mult.c add.o

dist: dist.c add.o mult.o
    gcc -o dist dist.c add.o mult.o
    
clean:
    rm dist

Here is dist.c:

#include <stdio.h>
#include "add.h"
#include "mult.h"

int main() {
  int a, b, c;
  puts("Calculating a * (b + c)");
  puts("Enter value for a:");
  scanf("%d", &a);
  puts("Enter value for b:");
  scanf("%d", &b);
  puts("Enter value for c:");
  scanf("%d", &c);
  int ab = mult(a, b);
  int ac = mult(a, c);
  int total = add(ab, ac);
  printf("Using the distributive property, a * (b + c) is %d\n", total);
  return 0;
}

This is add.h:

int add(int, int);

This is add.c:

int add(int a, int b) {
  return a + b;
}

This is mult.h:

#include "add.h"

int mult(int a, int b) {
  if (b == 0) {
    return 0;
  }
  if (b < 0) {
    return -mult(a, -b);
  }
  return add(a, mult(a, b - 1));
}

Unit Tests #

Unit tests can help you check whether your function is correct, helps you design your API (set of function signatures and behaviors), and check that refactored code is still correct.

Test-driven development: write the tests before you write the implementation.

Writing tests can help you specify what behavior your functions should have and provide documentation. Without the bias of your implementation, you may also catch bugs more easily.

Exercise #

Copy the source code for MinUnit into a file called minunit.h.

Now write a file called test_add.c or test_mult.c (or both if you have time). Write a few unit tests following the examples on the website above to test add or mult.

Bit Manipulation #

CPUs have optimized common operations, and there are theoretical algorithmic limits on some operations. Learning how to manipulate bits is an important skill for squeezing performance out of your implementations.

Swapping values of two variables x and y # 

x = x ^ y;
y = y ^ x;
x = x ^ y;

This does not work if x == y, because x ^ y = 0.

Bitwise operators are fast. Addition and subtraction are slightly slower but still relatively fast. Multiplication is a bit slower but well optimized. Division is slower than all of the above. FLoating-point arithmetic is slower than integer arithmetic, BUT floating-point multiplication is faster than floating-point addition.

Exercise #

For each problem, you need to implement a function in C that follows the given signature. In each problem, there are a few restrictions: you are limited to using certain operators, and you can only use a certain number of operators total.

You cannot use other operators, function calls, conditionals (if/else), or loops (for/while). You can define and use integers, but they can only be a single byte (between 0 and 255, inclusive).

Bitwise XOR #

Write a bitwise XOR function with this signature:

int bit_xor(int x, int y);

This function computes x ^ y, that is, the XOR of each of the respective bits of x and y.

You can use up to 14 of these operators:

& ~

Bitwise Inequality #

Write a bitwise inequality function with this signature:

int bit_neq(int x, int y);

This function returns 1 if x is not equal to y and 0 if they are equal.

You can use up to 6 of these operators:

! ~ & ^ | + << >>

Bitwise Byte #

Write a function with the following signature that takes an int x and a value n between 0 and 3 (inclusive), and returns the nth byte of x, where the 0th byte is the least significant and the 3rd is the most significant. Thus if x is 0xdeadbeef and n is 2, the function would return 0xad.

int bit_get_byte(int x, int n);

You can use up to 6 of these operators:

! ~ & ^ | + << >>

Lowest Significant Mask #

Write a function in C with the following signature:

int bit_least_set_mask(int x);

This function returns a mask of the least significant 1 bit in an integer x. Thus if x is 01100010, then the result is 00000010, and if x is 01111100, then the result is 00000100. (You’ll extend this to the full size of integers, which on this imaginary machine is 32 bits.)

You can use up to 6 of these operators:

! ~ & ^ | + << >>