Monday, February 25, 2013

goto: The Forbidden Fruit



Nowdays, it's not hard to find tons of arguments against the use of goto in C (and C-like languages).  Post anything to StackOverflow, about/including goto and you're almost guaranteed to get flamed.


Just like many good and useful things in our lives (pocketknives, guns, kegs, etc.) it only takes a few people to abuse something before everyone else categorizes it as "bad".  But the truth is, goto is a simple tool that, when used correctly, can make a program much easier to write (and even understand!)

First, let's take a look at how *not* to use goto (this is just a little example, nothing meaningful):

int foo(int a)
{

   int bar;
   while (bar < spam())
   {
loop:
      bar = a * scale;
      if (bar > 100) goto toobig;
      bla(bar);
   }
   return bar;
toobig:
   if (bar-tar > 0)
      return bar;
   bar -= 5; goto loop;


   return bar * 2;
}


Wow, that was even hard to come up with, and cetrainly isn't the way to do things. Jumping in and out of control structures is bound to confuse the next guy, and possibly the compiler when it is trying to optimize.

But in the right places, goto can be extremely useful. Luckily, my opinion here is not alone. In fact, the Linux Kernel (3.8) uses goto over 100,000 times!
$ find linux-3.8 -iname '*.c' -exec grep 'goto' {} \; | wc -l
104299
Here is a good example of this programming style in use, from the ext4 driver.


First, let's look at some bad code. The author does two things that I really dislike: 1) They return all over the place. This is okay, unless (like in this example) you have to deal with resource de-allocation. Here, this leads to a fragile situation with lots of calls to free. 2) They check first for success, which leads to ridiculous amounts of nesting.
bool baz() {
   bool result = false;
   uint8_t *buf1 = NULL;
   uint8_t *buf2 = NULL;
   uint8_t *buf3 = NULL;

   // Allocate buffers.
   buf1 = malloc(BUF1_SIZE);
   if (buf1) {

      buf2 = malloc(BUF2_SIZE);
      if (buf2) {

         buf3 = malloc(BUF3_SIZE);
         if (buf3) {

            result = use_buffers(buf1, buf2, buf3);
            if (result)
               printf("Success!\n");
            else
               fprintf(stderr, "Operation failed.\n");
            free(buf3);
            free(buf2);
            free(buf1);
            return result;

         }
         else {
            fprintf(stderr, "Error allocating %d bytes.\n", BUF3_SIZE);
            free(buf2);
            free(buf1);
            return false;
         }
      }
      else {
         fprintf(stderr, "Error allocating %d bytes.\n", BUF2_SIZE);
         free(buf1);
         return false;
      }
   }
   else {
      fprintf(stderr, "Error allocating %d bytes.\n", BUF1_SIZE);
      return false;
   }
}


Using goto and a single exit point clean this mess up very nicely:
bool baz() {
   bool result = false;    // Assume failure until proven successful
   uint8_t *buf1 = NULL;
   uint8_t *buf2 = NULL;
   uint8_t *buf3 = NULL;

   // Allocate buffers.
   buf1 = malloc(BUF1_SIZE);
   if (!buf1) {
      fprintf(stderr, "Error allocating %d bytes.\n", BUF1_SIZE);
      goto exit;
   }

   buf2 = malloc(BUF2_SIZE);
   if (!buf2) {
      fprintf(stderr, "Error allocating %d bytes.\n", BUF2_SIZE);
      goto exit;
   }

   buf3 = malloc(BUF3_SIZE);
   if (!buf3) {
      fprintf(stderr, "Error allocating %d bytes.\n", BUF3_SIZE);
      goto exit;
   }

   // Do something useful
   if (!use_buffers(buf1, buf2, buf3)) {
      fprintf(stderr, "Operation failed.\n");
      goto exit;
   }

   result = true;
   printf("Success!\n");

exit:
   if (buf1) free(buf1);
   if (buf2) free(buf2);
   if (buf3) free(buf3);

   return result;
}

This allows for a very straight-forward approach to handling resource allocation/freeing and a clean exit path. It's much easier to maintain as well (imagine having to remove buf2 in the first example!)

An alternative to goto I often see is the dummy do-while loop:
bool baz() {
   bool result = false;
   uint8_t *buf1 = NULL;
   uint8_t *buf2 = NULL;
   uint8_t *buf3 = NULL;

   do {
      // Allocate buffers.
      buf1 = malloc(BUF1_SIZE);
      if (!buf1) {
         fprintf(stderr, "Error allocating %d bytes.\n", BUF1_SIZE);
         break;
      }
   
      buf2 = malloc(BUF2_SIZE);
      if (!buf2) {
         fprintf(stderr, "Error allocating %d bytes.\n", BUF2_SIZE);
         break;
      }
   
      buf3 = malloc(BUF3_SIZE);
      if (!buf3) {
         fprintf(stderr, "Error allocating %d bytes.\n", BUF3_SIZE);
         break;
      }
   
      // Do something useful
      if (!use_buffers(buf1, buf2, buf3)) {
         fprintf(stderr, "Operation failed.\n");
         break;
      }
   
      result = true;
      printf("Success!\n");
   } while(0);

   if (buf1) free(buf1);
   if (buf2) free(buf2);
   if (buf3) free(buf3);

   return result;
}

This isn't terrible, but what about when you want to use an actual loop inside that dummy do-while, and break out of it? PHP includes a nice disgusting feature to break out of multiple levels. In other languages you're screwed, unless you follow the loop with some additional code to check for completion of the loop:

bool baz() {
   bool result = false;
   uint8_t *buf1 = NULL;
   uint8_t *buf2 = NULL;
   int i;

   do {
      // Allocate buffers.
      buf1 = malloc(BUF1_SIZE);
      if (!buf1) {
         fprintf(stderr, "Error allocating %d bytes.\n", BUF1_SIZE);
         break;
      }
   
      buf2 = malloc(BUF2_SIZE);
      if (!buf2) {
         fprintf(stderr, "Error allocating %d bytes.\n", BUF2_SIZE);
         break;
      }
   
      // Do something in a loop
      for (i=0; i<CONSTANT; ++i) {
         if (!use_buffers(buf1, buf2)) {
            fprintf(stderr, "Operation #%d failed.\n", i);
            break;            // Can't get out of the do-while from here!
         }
      }

      // Have to add this ridiculous check, because we could have exited
      // the loop early...
      if (i==CONSTANT) {
         result = true;
         printf("Success!\n");
      }
   } while(0);

   if (buf1) free(buf1);
   if (buf2) free(buf2);

   return result;
}
In this case, a goto exit; would have worked just fine.

Sunday, February 24, 2013

Deftones - You've Seen the Butcher - Timing


Maybe the name of this blog should include something about ADD or OCD. Either way, enough time was spent perfecting this, I figure I might as well share it with the Interwebs.

I'm a big fan of Deftones and their 2010 album Diamond Eyes was unsurprisingly awesome.  You've Seen the Butcher is an awesome track.  The timing is subtly complicated, so I decided to chart it out.  Hope this helps someone.

All time signatures are x/4, and the number of beats in each measure are shown.  For many parts of the song, the final measure's number of beats is the same as the part that follows. These are noted.

Intro
     lead-in                      1

Guitar-only               Alt. 3 and 4
     last measure                 5

Heavy riff (no vox)    Alt. 3 and 5
     last measure                 4


Verse 1
Verse                  Alt. 3 and 4
     last measure                 5

Pre-Chorus             Alt. 3 and 5

Chorus                 4
     last measure                 3


Verse 2
Verse                  Alt. 3 and 4
     last measure                 5

Pre-Chorus             Alt. 3 and 5

Chorus                 4


Bridge  note the two 6/4 measures

Heavy riff (no vox)    3  5  3  6  3  5  3  5
                     
Pre-Chorus             3  5  3  6  3  5  3  5


Outro
Chrous                 4
     last measure                 5

Ending                 3  (free)