evan_tech

Previous Entry Share Next Entry
11:34 pm, 3 Jun 03

Judy trick

Via brad via avva, from the source of Judy:

// Test if Word has any of the 4 bytes == ‘\0’:
//
// This arcane code takes advantage of the CPU having a fast barrel shifter and
// a carry bit. Doug stole this code from elsewhere, and we know it works, but
// we really can’t explain why.

#define NOZEROBYTE(Word) \
((((((Word) - 0x01010101) | (Word)) ^ (Word)) & 0x80808080) ? 0 : 1)

It took me a while to follow, but it’s not that bad after I understood it. Consider it a series of steps:

  1. Subtracting 0x01010101 subtracts 1 from each byte, which forces a carry into any byte that is 0 already.
  2. (A | B) ^ B, as you can prove to yourself, zeros all bits in A that are set in B.
  3. A & 0x80808080 tests the high bit in each byte.
So basically, you force there to be a carry into any zeroed bytes, then clear the high bits in any bytes that had the high bit set in the first place, and then finally you test if there are any high bits left over. If there are, there was a zeroed byte.