http://pigeonsnest.co.uk/stuff/pigeons-device.html

Pigeon's Device

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:

Control flows in Pigeon's device

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




Valid HTML 4.01!