Many may have heard tell of Duff's device, a rather neat loop optimisation technique in C.
This page provides details of Pigeon's device - a related but independently-originated technique. The original instantiation of Pigeon's device was in a piece of C code written for MS-DOS before the days of the internet, so I had not heard of Duff's device. When I did, the similarity between the techniques was immediately apparent.
The original Pigeon's device was in a function for comparing two date/time records in various different manners according to the desired sort order - FORWARD, forward chronological order; REVERSE, reverse chrononological order; and REVDFWDT, dates in reverse but times within each day sorted forwards. It's kind of a mess to read in its original form because of the various typedefs which are unique to the original program and other such cack, but the basic structure is quite simple. Here it is expressed as a function:
int pigeons_device(int a, int b, int mode) { int result; /* Isn't C a wonderful language? */ switch (mode) { case 0: if (gloop(a, b)) { case 1: result = arfle(a, b); break; } else { case 2: result = barfle(a, b); break; } } return (result); }
Or in other words... If mode == 1, return some function of a and b. If mode == 2, return a different function of a and b. But if mode == 0, decide which function of a and b to return based on some other relation between a and b.
Here it is with the possible flows of control marked out with pretty coloured arrows:
Why might one want to do that? The simple answer is "because one is a pigeon". The more complicated answer is... well, here is the original implementation, from which you may work it out for yourself.
int lfdcmp(const void *a, const void *b) { static int mode; struct date d1, d2; struct time t; if (b==NULL) return(mode); if (a==NULL) { mode=*(int *)b; return(0); } /* Isn't C a wonderful language? */ switch (mode) { case REVDFWDT: unixtodos(((lfdy *)a)->stamplog, &d1, &t); unixtodos(((lfdy *)b)->stamplog, &d2, &t); if ((d1.da_day==d2.da_day) && (d1.da_mon==d2.da_mon) \ && (d1.da_year==d2.da_year)) { case FORWARD : return(longsub(((lfdy *)a)->stamplog,((lfdy *)b)->stamplog)); break; } else { case REVERSE : return(longsub(((lfdy *)b)->stamplog,((lfdy *)a)->stamplog)); break; } default : pigeonerror(FATAL,"Bad lfdcmp mode: %d\n\r",mode); break; } return(0); }
The function starts with a Gruesome Hack to set and read the comparison mode. I did this because the function is called from a library sort routine and there is no way to get that routine to pass a third "mode" parameter. There are various other ways to get the mode into the function but since it was intended in any case to specify that one should not set the mode directly but should instead use the functions setsortmode() and getsortmode(), I made the hidden workings inside those functions do it this way because it was more fun.
Then we move on to the Pigeon's Device proper. In the case of FORWARD sorting the function simply returns a value whose sign depends on the forward order of two date records - longsub() is a function which subtracts one value of type long from another and returns the result as a value of type int, but limited to the maximum and minimum values allowed for an int instead of overflowing; such a value will satisfy the requirements of the library sort function without further processing. In the case of REVERSE sorting the two records are simply compared the other way round.
In the case of REVDFWDT sorting - Reverse Date Forward Time - the first operation is to extract the date information from the records, which are in UNIX timestamp format which obfuscates midnight. So the dates are converted to a DOS format with separate values for date and time. Then we reach the if statement intertwined with the switch statement. If the two records relate to the same date, they are compared in forward order; if they relate to different dates, they are compared in reverse order. The result of this is that the overall list comes out sorted with the dates backwards but the times within each day still forwards.
The default case is a "bug catcher"; if the function is used as intended with the mode set by calling setsortmode() invalid values shouldn't get in there in the first place.
And that is Pigeon's device, in context.
Back to Pigeon's Nest
Be kind to pigeons
