How the magic bits are improving the strlen function in glibc

Question

I was going through the source of strlen for glibc. They have used magic bits to find the length of string. Can someone please explain how it is working. Thank you

Answer 1

Let's say this function is looking through a string -- 4 bytes at a time, as explained by the comments (we assume long ints are 4 bytes) -- and the current "chunk" look like this:

'\3'     '\3'     '\0'     '\3'
00000011 00000011 00000000 00000011  (as a string: "\x03\x03\x00\x03")

The strlen function is just looking for the first zero byte in this string. It first determines, for each 4-byte chunk, whether there's any zero byte in there, by checking this magic_bits shortcut first: it adds the 4 bytes to this value:

01111110 11111110 11111110 11111111

Adding any non-zero bytes to this value will cause the 1's to overflow into the holes marked by zeroes, by propagating the carries. For our chunk, it'd look like this:

  11111111 111111          1 1111111   Carries
  00000011 00000011 00000000 00000011  Chunk
  01111110 11111110 11111110 11111111  Magic bits
+ -----------------------------------
  10000010 00000001 11111111 00000010
  ^      ^        ^        ^         

(The hole bits are marked by ^'s.)

And, from the comments:

       /* Look at only the hole bits.  If any of the hole bits
          are unchanged, most likely one of the bytes was a
          zero.  */

If there's no zeroes in the chunk, all of the hole bits will get set to 1's. However, because of the zero byte, one hole bit didn't get filled by a propagating carry, and we can then go check which byte it was.

Essentially, it speeds up the strlen calculation by applying some bit addition magic to 4-byte chunks to scan for zeroes, before narrowing down the search to single byte comparisons.

Answer 2

The idea is instead to compare one byte at a time against zero, rather to check one unsigned long object at a time if one of its byte is zero. This means checking 8 bytes at a time when sizeof (unsigned long) is 8.

With bit hacks, there is a fast known expression that can determine if one of the bytes compares equal to zero. Then if one of the bytes is equal to zero, the bytes of the object are individually tested to find the first one which is zero. The advantage of using bitwise operations is it reduces the number of branching instructions.

The bit hack expression to check if one of the byte of a multi-byte object is equal to zero is explained in the famous Stanford Bit Twiddling Hacks page, in

Determine if a word has a zero byte http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord