Recursion And Stack Overflow

 
Few days ago, the Twitter account of StackOverflow (the famous site of technical questions and answers) has published the following tweet:

int main() { return main(); } pic.twitter.com/SfQv6E8wht

— Stack Overflow (@StackOverflow) 22 Luglio 2015

The intention was to recall the name of the site by presenting a situation that every developer has been warned about.

Of course I got the pun but a light bulb has turned on in my mind: tail calls. Some years ago I've read something about it on the blog of Gustavo Duarte: Tail Calls, Optimization, and ES6.

Do It Yourself

It's not that I don't trust Gustavo, but I've tried to do my own test (on x86-64bits with gcc 4.8):

#include <stdio.h>

int main()
{
        fprintf(stderr, "Go!\n");
        return main();
}

Compiled with the optimization enabled:

gcc -O2 -o so so.c

Launching the executable so (that stands for stack overflow), it prints a never ending series of "Go!", without crashing. The explanation is exactly the same Gustavo presented in his old post: the compiler optimizes this call with a jump. So basically it transforms a recursion in a loop. This is clear looking at the disassembled code, with the following command:

objdump -d so

This is the result (leaving only the interesting part):

0000000000400480 <main>:
  400480:   48 83 ec 08            sub    $0x8,%rsp
  400484:   0f 1f 40 00            nopl   0x0(%rax)
  400488:   48 8b 0d b1 0b 20 00   mov    0x200bb1(%rip),%rcx   # 601040 <__TMC_END__>
  40048f:   ba 04 00 00 00         mov    $0x4,%edx
  400494:   be 01 00 00 00         mov    $0x1,%esi
  400499:   bf 14 06 40 00         mov    $0x400614,%edi
  40049e:   e8 cd ff ff ff         callq  400470 <fwrite@plt>
  4004a3:   eb e3                  jmp    400488 <main+0x8>

As you can see, fprintf is mapped with a callq to fwrite, while the recursion is made by the instruction jmp

Conclusions

Basically there are three considerations that can be done:

1. Gustavo was right;
2. compilers are smarter than you think;
3. the same thing I've wrote about goto and do-while loops apply also for recursion.

Image taken from Wikimedia Commons (public domain).

C, compilers, development, stackoverflow Sunday, July 26, 2015 No comments

How C Compilers Work Part 4: Linker

Now we are at the point where we have produced one or more object files and we want to create an executable. Under GNU/Linux systems, this job is done by ld, the GNU linker.

As seen in the previous part, the compiler always works on one file at once, so, every time there is the need to access a symbol (function or variable) defined somewhere else, a reference is used. The first work of the linker is to check the correctness of all these references.

ELF layout

Once this operation has ended successfully, it's time to produce the executable. To do this, all the object files are split into their basic components which are reassembled according to the ELF format. For example, all the fixed strings go in the string table, the names of the used symbols in the symbol table, etc.

This also happens to static libraries (that are just a set of object files packed in an archive) and shared objects if the flag -static has been specified.

In case of dynamic linking (that happens 99% of the times), the linker appends:

• a section called dynamic symbol table (.dynsym) containing the names of the external symbols, and
• a section called simply .dynamic that, among other things, contains also the name of the shared objects needed at runtime.

When the process will be executed, the dynamic linker will append to the process image the images of the shared objects listed in the .dynamic section (but this is a different story).

Troubleshooting

"Undefined reference" is the most common error that you can get. It means that a function or a variable defined as extern has not been found. The most common case is a typo or a missing shared object.

When working with multiple toolchains or different versions of a shared object, it may happen that the linker signals errors for undefined references even if everything seems correct. This happens because the reference to the symbol (usually added by a .h file) does not match what's inside the shared object being linked. Or, to say it in other words, the shared object the linker is referring to, is not consistent with the header file that has been included. A solution is to check the path of the header and the library (flags -I and -L in gcc).

Another sneaky error may appear when a program is executed in a system different from the one where it has been created. The message usually shown is the pretty misleading "No such file or directory". But the message is absolutely correct, a file is missing (or it's in an unexpected location). The missing file is a dynamically linked shared object. To check which one is, you have to use readelf.

$ readelf -d <process_name>

The first rows show the names of the needed shared objects. Now you only have to make sure they are present in your system. If you are able to find them but you get the same error, try to specify additional paths for them.

Other posts in this series

• Part 1 - Introduction
• Part 2 - Preprocessor
• Part 3 - Compiler

C, compilers, troubleshooting Wednesday, February 11, 2015 No comments

Bitwise Right Shift With Signed Int

It's never too late to learn something new. And sometimes the compiler is smarter than what you think. In this case, I've discovered this behavior a couple of weeks ago while I was working on a C function that manipulates the bits of an unsigned integer variable using the right-shift operator (>>).

The function worked pretty well, until someone wanted to use it with signed integers, too. The issue here is that the sign bit (the leftmost one) is replaced with zero when right-shifting. The solution has been absurdly easy: cast to signed int.

This is an example with 8 bits:

The right shift produces different results depending on the signedness of the variable

Too Good To Be True?

This is wonderful but there is a little thing to consider when you plan to use it. According to the C standard:

1196 If E1 has a signed type and a negative value, the resulting value is implementation-defined.

This means that every compiler can behave in its own way and, worst of all, for different architectures the same compiler can act differently. So, what's the solution?

There isn't just one, of course. The following function should work pretty fine in all cases, but I'm sure you can find at least another algorithm to do the same thing.

int right_shift_with_sign(int var, unsigned int amount)
{
        int mask = (var < 0) ? -1 >> amount : -1;
        int result = var >> amount;
        return (result | ~mask);
}

[Code not fully tested - use it at your own risk]

If you need way to detect how your compiler behave, you can use this short snippet:

if ((-1 >> 2) == -1) {
        /* right shift preserves the sign */
} else {
        /* right shift DOES NOT preserve the sign */
}

C, development, tips Thursday, December 18, 2014 No comments

How C Compilers Work Part 3: Compiler

The properly so called compiler is a really complicated piece of software. It performs many different tasks on single files. This means that no matter if your project is made of thousand source files: they will be compiled one by one.

Now let's see the common operations. First of all, it does a lexical and syntax analysis over the code. Many of the errors about missing semicolons and misspelled variables will be caught here. For functions there is a small caveat. According to C standard, if a function has not been declared, the compiler assumes that:

• it exists in some other file of your project, linked library or common library (such as libc), and
• it returns an integer value.

This will lead to warnings like this:

warning: implicit declaration of function ‘fprintf’ [-Wimplicit-function-declaration]
        fprintf(stderr, "Error! Expected %d param\n", ARGS);

or this:

warning: initialization makes pointer from integer without a cast
        char *token = strtok(my_string, "/");

To remove them, you just have to add the declaration of the functions you are using, by including the right header file.

Other things that the compiler checks:

• types of variables in assignments;
• type and number of parameters of called functions must match the corresponding prototypes (usually declared in header files included by the preprocessor);
• const variables and parameters have to remain untouched.

Another important task that is performed is the optimization. This task can improve your code mainly in two ways: increasing the speed or reducing the size of the final output. There are many things that can be done to achieve one of these goals. GCC, for example, has lots of options to let you do a fine tuning but, in the end, the more used are -O2 (to optimize for speed) and -Os (to optimize for size).

Eventually, the compiler produces a binary file (often called object file) full of references to unknown things. To make those things known is the job of the linker.

Other posts in this series

• Part 1 - Introduction
• Part 2 - Preprocessor
• Part 4 - Linker

C, compilers Saturday, December 13, 2014 No comments

Horror Code: Paid By The Number Of Rows

The first thing I've thought is: "I'm missing something". But after few seconds the doubt that the author of the following code is paid for the number of lines of code come to my mind. Judge yourself:

struct data_node *node = calloc(1, sizeof(*node));
if (node) {
        node->data = NULL;
        node->info = NULL;
        node->next = NULL;
}
comm->data_list = node;

Since node isn't used anywhere else, those six lines are exactly equivalent to the following:

comm->data_list = calloc(1, sizeof(*(comm->data_list)));

The function calloc returns a pointer to a memory area that is guarantee to be blank, so there is non need to assign NULL to the members of the structure.

Checking the value returned by calloc is a good thing. It may be that there is no more memory available so that error should be handled. But in this case the author didn't take any action in case of failure.

Use a temporary variable may be useful in some situations, but this is not one of those.

In conclusion, the code is formally correct: it doesn't have bugs or cause harms and maybe the compiler can optimize it. But the point is that redundant and useless code can lead to difficulties in reading and understanding besides subtle hard-to-find bugs.

Image by goopy mart licensed under CreativeCommons by-nc-sa 2.0

C, horror code Friday, November 28, 2014 No comments

How C Compilers Work Part 2 - Preprocessor

As said in the previous post, in modern compilers, preprocessing is not a separate phase but it's made together with compilation. Nevertheless, understanding the role of preprocessor is really helpful. The first thing to say is that it basically understands only rows that start with character hash (#).

In a standard program, those rows specifies header files to include and constants/macro to substitute in the rest of the file. Another frequent used feature is the conditional compilation (#if, #ifdef, etc.) to enable some part of code only if a condition is met at compile time. In this case the flag -D of GCC can be really useful.

A strange thing is the #pragma directive, used to issue commands directly to the compiler, in some cases to enable some vendor specific option. Other directives commonly used are #warning and #error; they force the compiler to present a warning or an error in special situations (usually depending on which other files are included or not included in the project).

An Example

Now let's see what a preprocessor does. Look at this simple program:

#include <stdio.h>
#include <string.h>

#define ARGS    1
#define TEST    "test_arg"

/* Main function */
int main (int argc, char **argv)
{
        if (argc != ARGS + 1) {
                fprintf(stderr, "Error! Expected %d param\n", ARGS);
                return 1;
        }

        if (strcmp(argv[1], TEST) != 0) {
                fprintf(stderr, "Error! Expected %s\n", TEST);
                return 2;
        }

        fputs("OK!\n", stdout);
        return 0;
}

Now if you compile it with:

gcc -Wall -E -o main_pp.c main.c

you'll get another C file named main_pp.c as a result (the flag -E tells GCC to only execute the preprocessor). If you don't have a compiler available, you can look at it here. Pretty big, isn't it?

What you should notice is that #include and #define directives have been processed and the comment has been removed. This obviously helps the programmer but basically almost all the work done by the preprocessor can be bypassed. In other words, the preprocessor is not indispensable. If you compile the following piece of code, you'll notice no differences in program execution compared to the original one.

typedef struct foo FILE;
FILE *stdout;
FILE *stderr;

int fprintf(FILE*, char*, ...);
int fputs(char*, FILE*);
int strcmp(const char*, const char *);

int main (int argc, char **argv)
{
        if (argc != 1 + 1) {
                fprintf(stderr, "Error! Expected %d param\n", 1);
                return 1;
        }

        if (strcmp(argv[1], "test_arg") != 0) {
                fprintf(stderr, "Error! Expected %s\n", "test_arg");
                return 2;
        }

        fputs("OK!\n", stdout);
        return 0;
}

How is this possible? How can it be that struct foo is a FILE? And what about other functions? For the answer, you'll have to wait the next two chapters of this series.

Troubleshooting

Usually preprocessor errors are easily understandable. For example:

failed.c:1:21: fatal error: missing.h

means that the header file missing.h does not exist or is not in the path. Another comprehensible error is the following:

failed.c:3:0: error: unterminated #ifdef

which remind us that an #endif is missing.

References

• If you want to play with the above examples, source files are here.
• A full explanation of the GCC preprocessor can be found at this page.
• The idea for the second example has been taken from this blog post.

Other posts in this series

• Part 1 - Introduction
• Part 3 - Compiler
• Part 4 - Linker

C, compilers, troubleshooting Sunday, November 23, 2014 No comments

How C Compilers Work Part 1 - Introduction

I'm writing this series of posts because it seems to me that many young programmers lack a clear idea about what's behind the "Build" button on their IDE. In my opinion, this happens because nowadays the interpreted languages (such as JavaScript, Python or Lua) are perceived to be more fancy and cool to learn.

The truth is that many companies still use compiled languages like C and C++. This ends in several developers (some of them absolutely remarkable) that keep losing time to understand how to fix an "undefined symbol" error.

An Overview

Operating diagram of a C compiler

The main purpose of a C compiler is to generate a binary file starting from one or more C source files. The generated file may be an executable or a library but in every case it contains low level machine-code instructions that a processor can execute.

A C compiler (such as GCC) is made of three logical blocks: the preprocessor, the compiler properly so called and the linker. Each block performs a set of specific tasks and produces an output for the next block but for performances reasons, usually the first two are implemented together.

Just as a side note, the first C++ compilers were implemented as preprocessors for C compilers.

Other posts in this series

• Part 2 - Preprocessor
• Part 3 - Compiler
• Part 4 - Linker

C, compilers Saturday, November 08, 2014 No comments

When Unit Tests Fail

This week, my colleague +Giancarlo B. showed me this short function.

char *unescape(char *in)
{
        char *tmp;
        int i, x;
        char b[5];
 
        tmp = calloc(strlen(in), sizeof(char));
        x = 0;
        for(i = 0; i < strlen(in); i++) {
                if(in[i] == '+')
                        tmp[x++] = 32;
                else if(in[i] == '%') {
                        memset(b, 0, 5);
                        strncpy(b, &in[i + 1], 2);
                        tmp[x++] = (char) strtol(b, NULL, 16);
                        i += 2;
                } else {
                        tmp[x++] = in[i];
                }
        }
        tmp[x] = 0;
        return tmp;
}

It's purpose is to convert a string such as "this+is+a%20space" into "this is a space". The function works pretty well provided that the input string contains at least a "%xx" sequence. If not, the output allocated string is one character too short. To fix this, it's sufficient to substitute

        tmp = calloc(strlen(in), sizeof(char));

with

        tmp = calloc(strlen(in) + 1, sizeof(char));

The thing that makes this bug special is that it can only be found by looking at the code. Let's see why.

The Speed Of calloc

The first thing to understand is how calloc works. I've learn this thing a couple of years ago when searching for the differences in speed with malloc + memset. Basically, calloc returns a pointer to a memory area that belongs to an already blank page, so there is no need to clear it, saving time. At this link there is an extended explanation.

This means that is (almost) guaranteed the next byte after the memory returned by calloc is blank. Or, in other words, that the string is NULL-terminated. But unfortunately this is true only until another calloc is called.

This second call is likely to return a pointer to the first unallocated byte that can be later changed into something different from NULL, generating unexpected behaviors.

False Negative

Now you should have understood why unit tests can fail here. Suppose you have this code:

int do_test()
{
        int err = 0;       /* 0 = no errors */
        char *s1 = "this+is+a%20space";
        char *s2 = "thisisnotaspace";
        char *t1 = "this is a space";
        char *t2 = "thisisnotaspace";

        char *r1 = unescape(s1);
        if (strcmp(t1, r1) != 0)
                err = 1;   /* error on the fist test */

        char *r2 = unescape(s2);
        if (strcmp(t2, r2) != 0)
                err = 2;   /* error on the second test */

        free(r1);
        free(r2);
        return err;
}

I expect that this function always returns 0, that means no errors. But obviously this is wrong. And, even if I know a couple of way to modify the test code to catch this particular error, it's not said that enabling or disabling some compiler flags we obtain the same behavior.

Conclusions

I really believe that unit tests are useful in order to find a wide range of bugs, but, in some situation, developer's experienced eyes are indispensable.

C, development, tests Friday, October 24, 2014 No comments

0 Errors - 0 Warnings

Are you one of those that don't care about warnings when compiling? Well, if you write conditions like the following,  probably you are:

if (2 == foo)

At first, it seems reasonable: if you forget one "=" by mistake, the compiler will stop the build with an error, making it obvious that you did something wrong. If the condition was written in the opposite way, it only would present you a warning message. But this approach has a big pitfall: the false sense of security.

If you think that whenever your code compiles without errors it is OK and the warnings are just annoying messages that can be easily ignored, you are probably missing the following problem:

if (bar = foo)

Every decent compiler will warn you by telling that, if an assignment is what you really want to do, it's better to surround it with double parenthesis. But if you ignore warnings, you'll get an unexpected (for you) behavior.

In my opinion, compiler warnings are even more important than errors: an error is something that is illegal in the format of a program while a warning is telling you that something looks strange in the logic of your code.

Many warnings are similar to a question: "are you sure you want to do that?" Or better: "doing that you'll get this result: is it what you want?" From my personal experience, many times the answer was "No!"

Bottom line: if you want to be sure that your code won't compile if there are warnings, the flag -Werror of gcc is what you need.

C, Cpp, development, style Wednesday, September 24, 2014 No comments

C++ And goto Don't Match Together

As you can see by reading this blog, I'm a fan of goto when used in an appropriate way. Unfortunately it works for C only - not C++.

The issue is all in this short paragraph (6.7/3) of the C++ standard:

It is possible to transfer into a block, but not in a way that bypasses declarations with initialization. A program that jumps from a point where a local variable with automatic storage duration is not in scope to a point where it is in scope is ill-formed unless the variable has POD type (3.9) and is declared without an initializer (8.5).

Jan 2012 Draft

This means that your C++ compiler will not build many C sources if you have used gotos to bypass initializations.

The solution to maintain the same functionality and the same structure of your code is to use exceptions. I'm sure you are thinking "why cannot I simply use some nested ifs?" My answer is "readability over all!"

An Example

Let's see a quick example, as I would write it in C.

int foo()
{
        int err = 0;
        X *x = NULL;
        Y *y = NULL;

        x = x_factory();
        if (x == NULL) {
                err = 1;
                goto clean_exit;
        }

        y = y_factory(x);
        if (y == NULL) {
                err = 2;
                goto clean_exit;
        }

        while ( /* condition */ ) {
                while ( /* other condition */ ) {
                        /* some code */

                        if ( /* critical error */ ) {
                                err = 3;
                                goto clean_exit;
                        }
                }
        }

        /* some other code */

clean_exit:
        if (x != NULL)
                x_free(x);
        if (y != NULL)
                y_free(y);

        return err;
}

The same code in C++ won't work, if in the code inside or after the loops there is some initialization. So, let's see how you would be tempted to rewrite it.

int foo()
{
        int err = 0;
        X *x = NULL;
        Y *y = NULL;

        x = x_factory();
        if (x != NULL) {
                y = y_factory(x);
                if (y != NULL){
                        while ( /* condition */ ) {
                                while ( /* other condition */ ) {
                                        /* some code */

                                        if ( /* critical error */ ) {
                                                err = 3;
                                                break;
                                        }
                                }

                                if (err != 0)
                                        break;
                        }

                        if (err != 0) {
                                /* some other code */
                        }
                } else {
                        err = 2;
                }
        } else {
                err = 1;
        }

        if (x != NULL)
                x_free(x);
        if (y != NULL)
                y_free(y);

        return err;
}

Too many elses and too indented, in my opinion. Below there is my version, using one of the most powerful constructs of C++: exceptions.

int foo()
{
        int err = 0;
        X *x = NULL;
        Y *y = NULL;

        try {
                x = x_factory();
                if (x == NULL)
                        throw(1);

                y = y_factory(x);
                if (y == NULL)
                        throw(2);

                while ( /* condition */ ) {
                        while ( /* other condition */ ) {
                                /* some code */

                                if ( /* critical error */ )
                                        throw (3);
                        }
                }

                /* some other code */
        } catch (int exception_code) {
                err = exception_code;
        }

        if (x != NULL)
                x_free(x);
        if (y != NULL)
                y_free(y);

        return err;
}

This is my opinion; what's your?

C, Cpp, development, style Friday, September 19, 2014 No comments

Power and Control

This video is a perfect representation of the Pirelli's slogan "power is nothing without control". You can have the fastest car in the world but if you are not able to manage it, you'll crash.

With the development languages it's the same. Some languages are (sensed to be) more powerful than others: some say that C++ is more powerful than C.

Please stop laughing and keep reading.

Small Digression on the Most Powerful Language

What is the meaning of "powerful" related to a programming language? Try to ask Google. Excluding Richard Stallman (that seems to love LISP), the majority of the results will say: "Every Turing-complete language is at the same level of the others."

Someone else points out that a language that needs less code to do the same thing is more powerful and probably I could agree, but... would you say that Assembly is less powerful than Pascal?

The answer that I like much is the following (from here):

C is powerful, because it is low level and gives you access to hardware. Python is powerful because you can prototype quickly. Lisp is powerful because its REPL gives you fantastic debugging opportunities. SQL is powerful because you say what you want and the DMBS will figure out the best way to do it for you. Haskell is powerful because each function can be tested in isolation. C++ is powerful because it has ten times the number of syntactic constructs that any one person ever needs or uses. APL is powerful since it can squeeze a ten-screen program into ten characters. Hell, COBOL is powerful because... why else would all the banks be using it? :)

Power and Control in C++

That having been said, we can go back to the control part. No matter the language you are using, you have to use it well. Are you still determined to use C++ because you think it's more powerful? Please go on. I'm not interested in a religion war. I love C++ too. But I know that mastering it is way more difficult than C.

And no, "mastering C++" doesn't mean using the iterators to scan a std::vector containing your fancy objects. Mastering C++ means understand OOP and understand template meta-programming.

Now you are able to start to design your class hierarchy. Design. Not code. The design part is the most important in a C++ project. If you fail it, your software will be a total failure. And when you have finished your design, take some time to simplify it.

The risk with C++ is to fall in love with your architecture and forget that the main purpose of every program is to run in a decent time without saturate the hardware resources.

Good Old Dirty C

So now you think that C is easier, right? Wrong! Probably the design part is faster and shorter but the risk to create something that is buggy, leaking memory and unmaintainable is just around the corner.

With C you can let all your perverse ideas to run free: cast madness, mixed usage of integers and pointers, long jumps like there is no tomorrow, etc.

The fact that you can do almost everything in C doesn't mean that you should. And remember, you don't have to demonstrate that you are a good programmer. Other developers don't care about you and your fancy hack; if it takes more than one minute to be understood, it's surely wrong.

Conclusions

You should have understood that the programmer is much more important than the used language. Poor developers will only write bad software. And programmers that don't think about the design before starting to code are doomed to write and rewrite and rewrite again.

C, Cpp, development Monday, June 16, 2014 No comments

Self-limited Development

I'm sure you have already heard of the following proverb:

If all you have is a hammer, everything looks like a nail.

It has come to my mind while reading this Linked in discussion (don't be mislead by the original question), especially those answers claiming "never used goto" or that there is no need to use do-while.

Well, you should know what I think about goto, and I don't want to repeat here the good reasons to use it. What I'm saying is that if a tool has been provided by the creators of the language (and never removed across several revisions) maybe it's not so bad.

Look at the above toolbox: there is also a cutter. It's pretty sharpened and can be dangerous if not used carefully. I bet you'd never use a cutter instead of a screwdriver. Maybe sometimes you can use the scissors instead of the cutter but in some situations it will not be practical and probably the result won't be the same.

Would you avoid using the cutter just because it is potentially dangerous or because someone told you that it's not good? Why the hell are supermarkets still selling cutters if you don't have to use them?!

So, why are you not using some instructions legally provided by the language?

C, development Thursday, May 22, 2014 No comments

Horror Code: the Impossible Function

This is one of the less readable functions that I've found in my life. I've removed any reference to structures and variable names, according to the Italian law about privacy ;-)

I don't want to add any other comment. Enjoy!

static int my_function( /* Parameters */ )
{
  /* Some code */
  int j;
  for(j = 0; j < 2; j++) {
    /* Some code */
    if (j == 0) {
      /* Some code */
    } else {
      /* Some code */
    }
    /* Some code */
    if ( /* Condition */ ) {
      if ( /* Condition */ ) {
        /* Some code */
        if ( /* Condition */ ) {
          /* Some code */
          if ( /* Condition */ ) {
            /* Some code */
            if ( /* Condition */ ) {
              int i;
              /* Some code */
              for(i = 0; i < length; i++) {
                /* Some code */
                if ( /* Condition */ ) {
                  /* Some code */
                  if ( /* Condition */ ) {
                    if ( /* Condition */ ) {
                      /* Some code */
                      if ( /* Condition */ ) {
                        /* Some code */
                        if ( /* Condition */ ) {
                          /* Some code */
                          if ( /* Condition */ ) {
                            /* Some code */
                          }
                          /* Some code */
                          if ( /* Condition */ ) {
                            /* Some code */
                          } else {
                            /* Some code */
                          }
                        } else {
                            /* Some code */
                        }
                        /* Some code */
                      } else {
                        /* Some code */
                      }
                      /* Some code */
                    } else {
                      /* Some code */
                    }
                  } else {
                    /* Some code */
                  }
                } else {
                  /* Some code */
                }
              }
            } else {
              /* Some code */
            }
          } else {
            /* Some code */
          }
        } else {
          /* Some code */
        }
        /* Some code */
      } else {
        /* Some code */
      }
      /* Some code */
    }
  }
  /* Some code */
  if ( /* Condition */ ) {
    /* Some code */
  } else {
    /* Some code */
  }
  /* Some code */
  return 0;
}

The real function has 113 rows and most of the code in the else's is made of debug prints. The innermost code, the only one that actually does something, is indented 13 (thirteen) times.

Wasn't there a clearer way to write that function?

C, development, horror code, personal Sunday, April 27, 2014 No comments

Indentation Matters

Last week my colleague +Daniele Veneroni told me: "You chose the wrong timing to write a post about the usefulness of goto. Have you heard what happened to Apple?" To make it short, there was a vulnerability into the validation of SSL/TLS connections in iOS devices. According to Sophos, this is the broken code:

. . .
hashOut.data = hashes + SSL_MD5_DIGEST_LEN;
hashOut.length = SSL_SHA1_DIGEST_LEN;
if ((err = SSLFreeBuffer(&hashCtx)) != 0)
    goto fail;
if ((err = ReadyHash(&SSLHashSHA1, &hashCtx)) != 0)
    goto fail;
if ((err = SSLHashSHA1.update(&hashCtx, &clientRandom)) != 0)
    goto fail;
if ((err = SSLHashSHA1.update(&hashCtx, &serverRandom)) != 0)
    goto fail;
if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
    goto fail;
    goto fail;  /* MISTAKE! THIS LINE SHOULD NOT BE HERE */
if ((err = SSLHashSHA1.final(&hashCtx, &hashOut)) != 0)
    goto fail;

err = sslRawVerify(...);
. . .

The error is probably a result of a bad copy 'n' paste, not the goto itself. Nonetheless if that line would have been correctly positioned (i.e. at the same level of the if statements), it would be immediately clear to everyone looking the code that something was wrong.

This event gives me the opportunity to talk about something that I consider very important when writing code: the coding style.

Matters of Style

Believe me, I've seen code less readable than this!

When there are at least two people working on the same code, the first thing that can cause problems is the coding style. Tabs versus white spaces, bracket placing, naming style, case, and, over all, indentation.

What is the purpose of the indentation? To make more readable the code. And why you should use descriptive names for variables and functions? For the same reason: readability. Your code should not only be executed by a processor, but also understood by other programmers.

And other programmers are full of laziness, impatience and hubris just like you. So they don't want to read every single row of your code just to add a trivial feature. This is true both in the open and the closed source worlds because if your code is not easy to maintain, it will be abandoned or someone will decide that is cheaper to rewrite it.

My Choices

I have to admit it. Often in the past I've used two-characters indentation and CamelCase names for functions and variables (you know, once I was also known as Mr Pascal).

But now those days are over. What I've decided to do some years ago is to use a different style for every programming language: so, for example, for Python I use PEP8. For C there are at least ten different styles, each one with his supporters (or should I call them ultras?). After a short research I decided for the Linux Kernel coding style.

If you read the document, you'll find that every choice is there for a good reason and the main guideline is always the readability. Because, as Guido Van Rossum said:

code is read much more often than it is written

Apple, bugs, C, Python, security, style Monday, March 03, 2014 No comments

Goto Is Your Friend

Yes Sir, that's what I'm gonna say!

I've started coding when I was 13. In Basic. And no, I'm not gonna say "good old times". Going back to those days, the only things I remember are the command AUTO to automatically create line numbers and the (ab)use of the GOTO statement.

Few years later, at the high school, my computer science teacher told me that goto is evil but luckily its use can be always avoided (see the Structured Program Theorem). One of the reasons for its bad reputation is that usually the code that uses goto is less readable and the program flow is difficult to follow. In two words: spaghetti code.

Only a couple of years ago I realized that this is not true. Goto is not evil by itself and in some (many) situations its use can produce a code that is more readable, optimized, and with small memory footprint.

Do you want some examples? How do you exit from multiple nested loops? Without using goto you should have at least a variable and an if for every loop that encloses loops and then you should have a bunch of breaks. And what is a break? A masked goto.

And what about multiple exit conditions that need to free allocated memory? Without using goto, you should duplicate the cleanup code with the risk to forget something every time you need to modify the code in the future.

These are only a couple of examples about the usefulness of the goto statement. If you are not fully convinced, have a look to this thread.

C, development Tuesday, February 11, 2014 No comments