In this article, I share some programming techniques with the C programming language on FreeBSD. As of FreeBSD 11.0, the basic installation comes with clang(1) tools for programming in C, C++, and Obj-C languages.

When I was a teaching assistant, I used to give my students a crash course in C programming. They already know C++ from their year 1. Once they understand the differences, they picked up C real quick.

C is one of my favourite programming languages. It’s features are minimal yet comprehensive. Because of its simplicity, it is also very popular in system implementation. Once somebody understands it, he is able to read and understand a lot of system implementation work. (Warning: he will also start to dislike some particular kernel implementations, because they are really badly written.)

Why is programming related to this blog? Indeed, one of the long-term goals here is to build a distributed software transactional memory system and deploy it on the cloud. Time will tell if I am capable of this accomplishment.

As a side note, in Cantonese, “C” has similar pronunciation as “詩” (poem), which is a popular character for feminine names, such as “李慧詩“. It is quite romantic to say “寫詩” (write poems) in place of “programming in that low-level language”… unless one broke up with one of those girls. Ah. The weather today is no good; and life is really harsh! Let’s carry (not Carrie) on.

## The Euclidean Algorithm

Today, we take the Euclidean Algorithm as an example. It is useful for finding the greatest common divisor (GCD) of two integers. I am not a mathematician, so please let me jump to my conclusion, as copied from the Wikipedia:

functiongcd(a, b)whileb ≠ 0 t := b; b := amodb; a := t;returna;

In short: There are two numbers. The larger number is replaced with the modulus between the two number. The logic repeats until a number turns into nothing. The remaining number is the answer.

## The First Attempt

Open up your favourite text editor and write to a file “gcd.c”. I use vi(1), but you can always use the easier ee(1). There are two functions in this program. The “gcd” function is responsible computing the greatest common divisor. The “main” function is the entry point. It uses scanf(3) to input two integers, “a” and “b”, and then uses printf(3) to output the result. In order to use these two functions, a header file “stdio.h” has to be included, as hinted by the manual pages.

There are “&” signs near the “a” and “b” and they mean pass-by-pointer. Normally, variables are only pass-by-value. The pass-by-pointer strategy allows the scanf(3) function to take the pointers and update the variables directly. The arguments “argc” and “argv” are the argument counts (a number) and argument vectors (array of strings, or array of array of characters). We do not use the arguments so we can leave them untouched.

#include <stdio.h> int gcd(int a, int b) { int c; while (b != 0) { c = a % b; a = b; } } int main(int argc, char** argv) { int a, int b; scanf("%d %d", &a, &b); printf("%d\n", gcd(a, b)); return 0; }

## Compilation Errors

Compile with the cc(1) command. Like the way I demonstrated to my students, the first attempt is usually a failed one…

# cc gcd.c -o gcd gcd.c:9:1: warning: control reaches end of non-void function } ^ gcd.c:12:9: error: expected identifier or '(' int a, int b; ^ gcd.c:12:8: error: expected ';' at end of declaration int a, int b; ^ ; 1 warning and 2 errors generated.

## The Second Attempt

It seems that semicolon should be used to separate declaration of the two variables. (I know, comma works another way, but I am not going to tell…)

#include <stdio.h> int gcd(int a, int b) { int c; while (b != 0) { c = a % b; a = b; } } int main(int argc, char** argv) { int a; // <-- this line int b; // <-- this line scanf("%d %d", &a, &b); printf("%d\n", gcd(a, b)); return 0; }

## Runtime Error

Let’s compile and try again. The program does compile despite the warning. For dramatic sake, ignore the warning and try. In the smoke test, we are supposed to enter the two numbers into the standard input. After inputting the two numbers, press enter a few times and …

# cc gcd.c -o gcd gcd.c:9:1: warning: control reaches end of non-void function } ^ 1 warning generated. # ./gcd 4 24

the program loops forever, press Ctrl-C to break out.

## First Time Debugging

To debug, let us use the LLVM debugger. (This is a new standard feature in FreeBSD 11.0. We used to have another debugger in the past.) Issue the lldb command, run with command “run”, input some text, then break it with Ctrl-C. Unlike last time we break to the shell, this time we end up seeing some assembly code dump.

# lldb gcd (lldb) target create "gcd" Current executable set to 'gcd' (x86_64). (lldb) run Process 93041 launching Process 93041 launched: '/root/gcd' (x86_64) 4 24 ^C Process 93041 stopped * thread #1: tid = 100067, 0x00000000004007ab gcd`gcd + 27, stop reason = signal SIGSTOP frame #0: 0x00000000004007ab gcd`gcd + 27 gcd`gcd: -> 0x4007ab <+27>: movl %edx, -0x10(%rbp) 0x4007ae <+30>: movl -0xc(%rbp), %edx 0x4007b1 <+33>: movl %edx, -0x8(%rbp) 0x4007b4 <+36>: jmp 0x40079a ; <+10> (lldb) quit Quitting LLDB will kill one or more processes. Do you really want to proceed: [Y/n] y

As part of my plan, you see nothing useful unless you understand assembly code. Quit and say yes to confirm. Then, we try compiling again with debug symbols.

# cc gcd.c -o gcd gcd.c:9:1: warning: control reaches end of non-void function } ^ 1 warning generated. # lldb gcd (lldb) target create "gcd" Current executable set to 'gcd' (x86_64). (lldb) run Process 93075 launching Process 93075 launched: '/root/gcd' (x86_64) 4 24 ^C Process 93075 stopped * thread #1: tid = 100096, 0x00000000004007ab gcd`gcd(a=24, b=24) + 27 at gcd.c:6, stop reason = signal SIGSTOP frame #0: 0x00000000004007ab gcd`gcd(a=24, b=24) + 27 at gcd.c:6 3 int gcd(int a, int b) { 4 int c; 5 while (b != 0) { -> 6 c = a % b; 7 a = b; 8 } 9 } (lldb)

To step through the program, use the command “print” to print a variable content, and “next” to step to the next statement. Repeat this a few times, we see the variable content does not change. The condition to break out of the loop will not be satisfiable.

(lldb) print b (int) $0 = 24 (lldb) next Process 93075 stopped * thread #1: tid = 100096, 0x00000000004007ae gcd`gcd(a=24, b=24) + 30 at gcd.c:7, stop reason = step over frame #0: 0x00000000004007ae gcd`gcd(a=24, b=24) + 30 at gcd.c:7 4 int c; 5 while (b != 0) { 6 c = a % b; -> 7 a = b; 8 } 9 } 10 (lldb) print b (int) $1 = 24 (lldb) next Process 93075 stopped * thread #1: tid = 100096, 0x00000000004007b4 gcd`gcd(a=24, b=24) + 36 at gcd.c:5, stop reason = step over frame #0: 0x00000000004007b4 gcd`gcd(a=24, b=24) + 36 at gcd.c:5 2 3 int gcd(int a, int b) { 4 int c; -> 5 while (b != 0) { 6 c = a % b; 7 a = b; 8 } (lldb) print b (int) $2 = 24 (lldb) next Process 93075 stopped * thread #1: tid = 100096, 0x00000000004007a4 gcd`gcd(a=24, b=24) + 20 at gcd.c:6, stop reason = step over frame #0: 0x00000000004007a4 gcd`gcd(a=24, b=24) + 20 at gcd.c:6 3 int gcd(int a, int b) { 4 int c; 5 while (b != 0) { -> 6 c = a % b; 7 a = b; 8 } 9 } (lldb) print b (int) $3 = 24

## The Third Attempt

In order to make the loop terminate, the variable “b” must change. We take revision on the source code and noticed a line is missing. Here is another iteration:

#include <stdio.h> int gcd(int a, int b) { int c; while (b != 0) { c = a % b; a = b; b = c; // <-- this line } } int main(int argc, char** argv) { int a; int b; scanf("%d %d", &a, &b); printf("%d\n", gcd(a, b)); return 0; }

## Second Time Debugging

I am going to save time and tell you the code does not work. It consistently returns “0” in my case. Let us jump into the debugger again. Because the program does not loop indefinitely this time, we need another way to stop the program before it finishes. In this example, I used a “breakpoint set” command with “–file” and “–line” option. Then I used “step” command to step inside the “gcd” function call.

# cc gcd.c -o gcd gcd.c:9:1: warning: control reaches end of non-void function } ^ 1 warning generated. # lldb gcd (lldb) target create "gcd" Current executable set to 'gcd' (x86_64). (lldb) breakpoint set --file gcd.c --line 15 Breakpoint 1: where = gcd`main + 53 at gcd.c:15, address = 0x0000000000400805 (lldb) run Process 93155 launching Process 93155 launched: '/root/gcd' (x86_64) 4 24 ^C Process 93155 stopped * thread #1: tid = 100085, 0x0000000000400805 gcd`main(argc=1, argv=0x00007fffffffeb60) + 53 at gcd.c:15, stop reason = breakpoint 1.1 frame #0: 0x0000000000400805 gcd`main(argc=1, argv=0x00007fffffffeb60) + 53 at gcd.c:15 12 int main(int argc, char** argv) { 13 int a; int b; 14 scanf("%d %d", &a, &b); -> 15 printf("%d\n", gcd(a, b)); 16 return 0; 17 } (lldb) print a (int) $0 = 4 (lldb) print b (int) $1 = 24 (lldb) step Process 93155 stopped * thread #1: tid = 100085, 0x000000000040079a gcd`gcd(a=4, b=24) + 10 at gcd.c:5, stop reason = step in frame #0: 0x000000000040079a gcd`gcd(a=4, b=24) + 10 at gcd.c:5 2 3 int gcd(int a, int b) { 4 int c; -> 5 while (b != 0) { 6 c = a % b; 7 a = b; 8 b = c; (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007a4 gcd`gcd(a=4, b=24) + 20 at gcd.c:6, stop reason = step in frame #0: 0x00000000004007a4 gcd`gcd(a=4, b=24) + 20 at gcd.c:6 3 int gcd(int a, int b) { 4 int c; 5 while (b != 0) { -> 6 c = a % b; 7 a = b; 8 b = c; 9 } (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007ae gcd`gcd(a=4, b=24) + 30 at gcd.c:7, stop reason = step in frame #0: 0x00000000004007ae gcd`gcd(a=4, b=24) + 30 at gcd.c:7 4 int c; 5 while (b != 0) { 6 c = a % b; -> 7 a = b; 8 b = c; 9 } 10 } (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007b4 gcd`gcd(a=24, b=24) + 36 at gcd.c:8, stop reason = step over frame #0: 0x00000000004007b4 gcd`gcd(a=24, b=24) + 36 at gcd.c:8 5 while (b != 0) { 6 c = a % b; 7 a = b; -> 8 b = c; 9 } 10 } 11 (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007ba gcd`gcd(a=24, b=4) + 42 at gcd.c:5, stop reason = step over frame #0: 0x00000000004007ba gcd`gcd(a=24, b=4) + 42 at gcd.c:5 2 3 int gcd(int a, int b) { 4 int c; -> 5 while (b != 0) { 6 c = a % b; 7 a = b; 8 b = c; (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007a4 gcd`gcd(a=24, b=4) + 20 at gcd.c:6, stop reason = step over frame #0: 0x00000000004007a4 gcd`gcd(a=24, b=4) + 20 at gcd.c:6 3 int gcd(int a, int b) { 4 int c; 5 while (b != 0) { -> 6 c = a % b; 7 a = b; 8 b = c; 9 } (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007ae gcd`gcd(a=24, b=4) + 30 at gcd.c:7, stop reason = step over frame #0: 0x00000000004007ae gcd`gcd(a=24, b=4) + 30 at gcd.c:7 4 int c; 5 while (b != 0) { 6 c = a % b; -> 7 a = b; 8 b = c; 9 } 10 } (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007b4 gcd`gcd(a=4, b=4) + 36 at gcd.c:8, stop reason = step over frame #0: 0x00000000004007b4 gcd`gcd(a=4, b=4) + 36 at gcd.c:8 5 while (b != 0) { 6 c = a % b; 7 a = b; -> 8 b = c; 9 } 10 } 11 (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007ba gcd`gcd(a=4, b=0) + 42 at gcd.c:5, stop reason = step over frame #0: 0x00000000004007ba gcd`gcd(a=4, b=0) + 42 at gcd.c:5 2 3 int gcd(int a, int b) { 4 int c; -> 5 while (b != 0) { 6 c = a % b; 7 a = b; 8 b = c; (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x00000000004007bf gcd`gcd(a=4, b=0) + 47 at gcd.c:10, stop reason = step over frame #0: 0x00000000004007bf gcd`gcd(a=4, b=0) + 47 at gcd.c:10 7 a = b; 8 b = c; 9 } -> 10 } 11 12 int main(int argc, char** argv) { 13 int a; int b; (lldb) next Process 93155 stopped * thread #1: tid = 100085, 0x0000000000400813 gcd`main(argc=1, argv=0x00007fffffffeb60) + 67 at gcd.c:15, stop reason = step over frame #0: 0x0000000000400813 gcd`main(argc=1, argv=0x00007fffffffeb60) + 67 at gcd.c:15 12 int main(int argc, char** argv) { 13 int a; int b; 14 scanf("%d %d", &a, &b); -> 15 printf("%d\n", gcd(a, b)); 16 return 0; 17 }

We see the values of variables “a” and “b” decreases alone the time line. Pay attention to the transition between the “gcd” function to the “main” function. There is not a return value. This is why we kept having the warning. Compiler warnings are often more useful than what programmers think. Sometimes, I am amazed why the open source software packages contain some many warnings in compilations and they still work.

## The Final Version

We get to return the answer in the “gcd” function. Here is how it the code being corrected.

#include <stdio.h> int gcd(int a, int b) { int c; while (b != 0) { c = a % b; a = b; b = c; } return a; // <-- this line } int main(int argc, char** argv) { int a; int b; scanf("%d %d", &a, &b); printf("%d\n", gcd(a, b)); return 0; }

## The Final Testing

# cc gcd.c -o gcd # ./gcd 0 5 5 # ./gcd 5 0 5 # ./gcd 1 9 1 # ./gcd 9 1 1 # ./gcd 4 36 4 # ./gcd 36 4 4 # ./gcd 24 36 12 # ./gcd 36 24 12