Evan Martin (evan) wrote in evan_tech,
Evan Martin
evan
evan_tech

  • Music:

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.

Subscribe

  • dremel

    They published a paper on Dremel, my favorite previously-unpublished tool from the Google toolchest. Greg Linden discusses it: "[...] it is capable…

  • more on synonyms

    Before Chrome, this is what I spent much of my Google career working on.

  • megaupload captcha

    Someone make a Javascript-based captcha cracker for megaupload. It's strange to see those captchas again because I idly myself wrote a…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments