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.

I’ve never made a request of this sort before — I don’t intend to make it a regular thing — but I’d like to ask you to not shop at Budds clothing stores, and to share this message if you’re willing to show your support.

The owner of the Kitchener Budds store wrongfully accused my 57 year old mother of shoplifting, by yelling it to everyone in the store. He then proceeded to physically stop her from leaving the store by pushing on her shoulders.

She was forced to remove her coat, undo her sweater, and lift up her shirt to prove that she didn’t have any items, and finally he let her leave.

Later, after cooling down, she decided to return to explain that she’d initially headed for the door after a bad customer service experience. She wanted to give them an opportunity to apologize, but instead, they told her the experience was fine and that she was wrong. Then the owner said that they’d never found the items he’d seen her holding earlier.

So she walked with him to where she’d put down the $15 worth of clothing on a shelf. My mom told him that if the store weren’t such a mess, it would have been easier to find. She didn’t know he was the owner, so she asked to speak to a manager — that’s when he yelled at her again, that he owned the place, and that she was unwelcome there. He went so far as to shove her on her way out.

The website for Budds[1] has written things like “YOU ARE FAMILY TO US”, “Remember that your customers are the ONLY reason you and I are in business, without them, you are nothing!”, and “At Budds our customers are the real reason for our existence and they will always be like family to us.” They have placed a great deal of focus on providing good customer service, and utterly failed to deliver on that promise.

Mom has filed complaints with the Better Business Bureau and the KW Chamber of Commerce. I just want to make sure that people hear about this, because it’s unbelievable and angering. If this is how Stan Budd of Budds treats people like my mom during the holidays, then he and his store simply don’t deserve to be in business. They say so themselves.

Thanks for reading.

[1] – http://www.buddsonline.com/aboutus.htm

don’t try to keep it all in your head.

I’m reading about the tortoise and hare algorithm for finding cycle detection. Just moments ago, I read the following in the (awful) comment on wikipedia:

# now the position of tortoise which is the distance between
# hare and tortoise is divisible by the length of the cycle.

So, the position of the tortoise is x, and the position of the hare is 2x, and x is divisible by L, the length of the cycle. I’m surprised that x is necessarily divisible by L, so I figured it’s time to do a thought experiment. So I sat here and thought “okay so let’s imagine a graph with a cycle in it — maybe 2 nodes going in, and 3 nodes cycling back and forth”. Next, I thought “Now let’s consider the tortoise at the point of entry into the cycle — he’s moved 2 steps, so the hare would have moved 4… so the hare would be” and I started trying to picture the point the hare would be at. Meanwhile, I’m thinking “maybe I should try fewer vertices? Or more…”, and “Maybe I should go step by step and keep track of each of their progress through the sequence.”

If that sounds confusing, good. Because it is. Keeping a ton of stuff in your head like that is silly, and error-prone, and vulnerable to distraction. Just by thinking “I should write a short blog post about this”, I lost some of the state I’d built up. Actually writing the blog has obliterated any progress I’d made.

Instead of trying to keep things in your head — whether you do it out of laziness, or because you want to prove you can do it*, or because it just doesn’t occur to you to do otherwise — just write things down. Open a text editor and plop things in there, or my personal recommendation: grab a pencil and some paper and write/draw it out. The physical world can do the job of remembering where and what everything is, and you just have to figure out the transformations. Much easier. Much smarter.

* I fall into this trap whenever I use Khan Academy’s tests. I start off on something easy enough that it makes sense to keep in my head. Then it gets a little harder, for a long time, and eventually I’m struggling to multiply 5 digit numbers in my head for no reason other than a misguided sense of pride. I’ll usually give up around then, too, which shows that it’s not a smart path.

I just read this blog post, linked from this HN thread, and it contained this quote:

In the information age, the barriers just aren’t there. The barriers are self-imposed. If you want to set off and go develop some grand new thing, you don’t need millions of dollars and capitalization. You need enough pizza and Diet Coke to stick in your refrigerator, a cheap PC to work on, and the dedication to go through with it. We slept on floors. We waded across rivers.
– John Carmack

Time to go read Masters of Doom.