I decided to take a glance at the linux release of the doom source code, from back in 1997, and just above the main loop, there’s some functions to deal with events. This is the line that got my brain stuck and jammed:

eventhead = (++eventhead)&(MAXEVENTS-1);

There is an events array, and a tail and a head. Naturally, I assumed that events would be written at the head and read off the tail, and that the head and tail would just cycle around the array. So, with that in mind (and seeing the same pattern at this other point in the code, as the increment-step in a for-loop), I figured that this must somehow be incrementing the head’s position and wrapping it back to 0 when appropriate.

Except that isn’t what that code is likely to do. Let’s break it down: pre-increment eventhead. Then subtract one from MAXEVENTS. Bitwise-and those two, and put the result in eventhead. Still a little complex! Let’s break it apart more.

Add one to whatever eventhead is. Then subtract one from MAXEVENTS. Then bitwise-and the two, which is: convert them to binary, and every column that has two 1s in it stays a 1 in the resulting number. The output of that is stored in eventhead. Sounds like something we can try out manually.

Imagine that MAXEVENTS is ten. Let’s assume that eventhead starts at zero.

Adding one to eventhead, we get 1. Subtracting one from MAXEVENTS is 9. Converting these to binary and padding them to equal width, eventhead is 0001, and MAXEVENTS-1 is 1001. Going column-wise through that from the left, we get 0&1=0, 0&0=0, 0&0=0, 1&1=1. We got 0001, which is just one. So eventhead incremented the first time the code ran — great! That’s what we want. What happens next?

Adding one to eventhead at 1, we get 2. Subtracting one from MAXEVENTS is still 9. Converting these to binary and padding them to equal width, eventhead is 0010, and MAXEVENTS-1 is 1001. Going column-wise through that from the left, we get 0&1=0, 0&0=0, 1&0=0, 0&1=0. That’s 0000. Zero. So eventhead decremented the second time the code ran. Huh… did we miss something?

Starting to wonder if I’d misunderstood the code, I wrote a simple program to check it, and the output was what we just got: a stream of alternating 0s and 1s. So what’s this code supposed to do? Next I asked a friend to look and give his opinions (he ended up at the same spot), and I went googling around. I found one port where the code has been replaced with something more readable that does what I expected. So we came to the conclusion that one of the following scenarios must be true:

1. The person who wrote this might be an idiot or a showoff. The code either doesn’t work as it seems it should, or relies on clever behaviour for no good reason to accomplish its task.
2. There may be a valid reason for it to be clever, and despite our best attempts to grok it, we’re missing something.
3. Maybe there have been semantic changes to bitwise-and or preincrement since this code was written.

We wrote 3 off right away. And we’re pretty sure (given the community’s adulation for John Carmack and the code he’s released) that 1 isn’t the case either. So probably, we are missing something and there’s a good reason for it to be so weird.

Near the end of my rope, I decided to search for ways to do what I think this code ought to. There, on the cplusplus forums, I found a pretty great answer that fills in the missing detail: MAXEVENTS must always be a power of two.

It didn’t even occur to me to look and see what MAXEVENTS was beyond a cursory glance — it’s not defined in d_main.c or d_main.h, so I stopped looking. Just now I’ve found it in d_event.h, defined to 64. 2**6.

So… what? Why?

Let’s try a power-of-two example MAXEVENTS: 16. MAXEVENTS minus one is then 15, in binary, 1111. Bitwise-and of 0001 (that’s eventhead starting at 0, and then preincremented before being and-ed) and 1111 is 0001. So eventhead is incremented the first time the code runs, just like before.

Next time it runs, pre-increment 1 to 2, which is 0010, and bitwise-and that with 1111, what do we get? 0010. It incremented again this time! Next time after that, it goes to 3. And then 4. Until eventhead hits 16, which is 10000. 10000 & 1111 = 00000. so this wraps back around to 0 and begins again. It finally makes sense.

Why do this? The modulus operator, using division, is the most common way to achieve this behaviour. But it’s expensive compared to bitwise operators. Carmack wanted speed and in one of the most commonly hit lines of code in the entire game, it makes sense to optimize.

Pretty sensible in the end. Two things I noted to look out for next time:

1. Look for the actual initialization (or equivalent — find the value) when doing mental or test-runs through of the code. If none is present, consider: powers of 2, negative numbers, very large number, 0, and 1. Not just something convenient like 10.
2. “What I think it does” is actually a good clue for where to start looking for answers.