Revising the syntax of Duff's device - Is this legal C/C++?

Question

Only last night I encountered the curious Duff's device for the first time. I've been doing some reading on it, and I don't think it's that daunting to understand. What I am curious about is the strange syntax (from Wikipedia):

register short *to, *from;
register int count;
{
  register int n = (count + 7) / 8;
  switch(count % 8) {
  case 0: do {    *to = *from++;
  case 7:         *to = *from++;
  case 6:         *to = *from++;
  case 5:         *to = *from++;
  case 4:         *to = *from++;
  case 3:         *to = *from++;
  case 2:         *to = *from++;
  case 1:         *to = *from++;
    } while(--n > 0);
  }
}

I was reading the C++ standard definition of a switch statement (please let me know if that's outdated, I'm not familiar with Open-Std.org). So far as I can understand case statements are just simplified jump statements for use by the switch statement.

The switch itself completely ignores the nested do-while, and the loop ignores the case statements. Since the switch jumps inside of the loop, the loop is executed. The switch is there to cover the remainder (from the division by 8), and the loop handles the portion that is evenly divisible. This all makes sense.

My question then is why the awkward syntax? It occurs to me that the loop could be written such that all of the case statements are contained within, yes? I see nothing in the standard that prohibits this behavior, and it compiles correctly under GCC 4.7, so is the following considered legal?

register short *to, *from;
register int count;
{
  register int n = (count + 7) / 8;
  switch (count <= 0 ? 8 : count % 8)
  {
    do
    {
      case 0:         *to = *from++;
      case 7:         *to = *from++;
      case 6:         *to = *from++;
      case 5:         *to = *from++;
      case 4:         *to = *from++;
      case 3:         *to = *from++;
      case 2:         *to = *from++;
      case 1:         *to = *from++;
      default:        ; // invalid count, suppress warning, etc.
    } while(--n > 0);
  }
}

To me this makes the intent of the code much clearer. Thanks for any feedback. ;)

Edit: As noted below, the original code was written for C and had implicit int for the count and n variables. Since I tagged it C++ I've modified that.

Edit 2: Modified the revised example code to account for invalid count values.

Ben Voigt · Accepted Answer · 2013-01-15T05:25:03.077

8

Looking at the C++11 Standard, the part of the code I think you're asking about would be allowed. Have you tried it?

The rule I see that's most applicable is:

Note: Usually, the substatement that is the subject of a switch is compound and case and default labels appear on the top-level statements contained within the (compound) substatement, but this is not required.

In fact, this means you could get rid of the braces around the do-while, and write

  int n = (count + 7) / 8;
  switch (count % 8) do
  {
      case 0:         *to = *from++;
      case 7:         *to = *from++;
      case 6:         *to = *from++;
      case 5:         *to = *from++;
      case 4:         *to = *from++;
      case 3:         *to = *from++;
      case 2:         *to = *from++;
      case 1:         *to = *from++;
  } while(--n > 0);

However, this line is NOT valid C++:

register n = (count + 7) / 8;

C++ does not allow default-int, the type of a variable must be specified or inferred.

Oh here, fix the number of iterations without breaking formatting:

  int n = 1 + count / 8;
  switch (count % 8) do
  {
                      *to = *from++;
      case 7:         *to = *from++;
      case 6:         *to = *from++;
      case 5:         *to = *from++;
      case 4:         *to = *from++;
      case 3:         *to = *from++;
      case 2:         *to = *from++;
      case 1:         *to = *from++;
      case 0:                      ;
  } while(--n > 0);

edited Jan 15 '13 at 05:25

answered Jan 14 '13 at 22:11

Ben Voigt

277,958
43
419
720

You're right. I was wondering about that, as I said I snagged the example code from Wikipedia, and is given in C not C++. Omitting the "extra" braces seems even better. – monkey0506 Jan 14 '13 at 22:18
1

C doesn't allow default `int` either, as of the 1999 ISO standard. (Duff devised his Device long before C99.) – Keith Thompson Jan 14 '13 at 22:21
@Keith: Yes, back when compilers were too stupid to enregister local variables unless you asked them to. – Ben Voigt Jan 14 '13 at 22:24
2

I wonder if the `switch`-`do` statement will now be added to the list of little-known C/C++ features, just like the approaches operator `<--` and goes-to operator `-->`. – Ben Voigt Jan 14 '13 at 22:27
1

@BenVoigt: Don't forget the [`&&&` operator](http://stackoverflow.com/q/13946938/827263). – Keith Thompson Jan 14 '13 at 22:29
Just some added feedback, I've been reading about how terribly inefficient division (apparently) is, so it occurred to me that as long as the number of unrolled loops is a power of two (such as in this case, it's eight) then the division can be replaced with a binary shift to the right three, and the modulo can be replaced with binary and seven. It's not an issue for me right now, but could maybe help with performance critical code...? – monkey0506 Jan 18 '13 at 20:14
@monkey_05_06: That's true, and the compiler programmers already know about it. So when you right `count / 8` in the source code, the program might actually use a shift. Just enable optimizations. – Ben Voigt Jan 19 '13 at 02:48

Lindydancer · Answer 2 · 2013-01-14T22:53:12.397

1

Yes, it is legal. The labels of a switch statement is typically written at the same level as the switch statement. However, it is legal to write them inside compound statements, e.g. in the middle of a loop.

EDIT: There is no requirement that the body of the switch statement must start with a label, any code is legal. However, there is no way into it from the switch statement itself, so unless it is a loop, or a plain label, the code will be unreachable.

Another interesting thing with the swtich statement is that the braces are optional. However, in that case only one label is allowed:

  switch (i)
      case 5: printf("High five\n");

edited Jan 14 '13 at 22:53

answered Jan 14 '13 at 22:12

Lindydancer

25,428
4
49
68

1

The question is whether the controlled block has to have a `case` or `default` label on the first statement. And the answer appears to be "no". (Your summary is correct) – Ben Voigt Jan 14 '13 at 22:13
So instead of writing `if (i == 42) single_stmt;` you can write `switch (i) case 42: single_stmt;`. – md2perpe Mar 24 '17 at 08:35

score 1 · Answer 3 · answered Jan 14 '13 at 22:30

The code is certainly legal: There are no requirements at all about for blocks and/or loops. It is worth noting, though, that count == 0 isn't properly handled by the above loop. It is, however, properly handled by this one:

int count = atoi(ac == 1? "1": av[1]);
switch (count % 4)
{
case 0: while (0 < count) { std::cout << "0\n";
case 3: std::cout << "3\n";
case 2: std::cout << "2\n";
case 1: std::cout << "1\n";
    count -= 4;
    }
}

Putting the case 0 label inside the loop would also incorrectly execute the nested statements. Although I have seen Duff's device always using a do-while loop, it seems the above code is more natural to deal with the boundary condition.

I can appreciate that this case isn't properly handled by the above, but your code suffers from ugly. The standards don't require it, but even in a situation like this I still feel that it's good style for a switch statement to have a default case. I could then specifically delegate to the default for invalid values of count: switch (count <= 0 ? 8 : count % 8) do { /* ...case 0, 7, 6, 5... (switched to block comment due to SO comment formatting) */ default: ; } while (--n > 0); This avoids the ugly and handles every case correctly. — monkey0506, Jan 14 '13 at 23:51

Revising the syntax of Duff's device - Is this legal C/C++?

3 Answers3