strlen in IOS

contributed by < Eric Lin >

Overview

The technique used to detect \0 character by strlen in IOS:

Laligned_loop:
	/* ((x - 0x01010101) & ~x & 0x80808080) == hasnull(word) */
	sub		r3, r2, r1		/* x - 0x01010101 */
	bic		r3, r3, r2		/* above & ~x */
	tst		r3, r1, lsl #7	/* above & 0x80808080 */
	ldreq	r2, [r0], #4	/* load next word */
	beq		Laligned_loop

The same techique can be found in string/strlen.c:

#if LONG_MAX == 2147483647L
#define DETECTNULL(X) (((X) - 0x01010101) & ~(X) & 0x80808080)
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECTNULL(X) (((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif

I am curious about why this code can detect NULL byte.

Break down

First, simplify the code to detecting whether one byte data is NULL or not:

 (X - 0x01) & ~X & 0x80

Convert it according to De Morgan's laws:

 ~(~(X - 0x01) | X) & 0x80

Switch the first two parameters' position:

 ~(X | ~(X - 0x01)) & 0x80

Now, if X = 0:

 X = ~(X | ~(0b10000001)) & 0x80

 X = ~(0b00000000 | 0b01111110)) & 0x80

 X = 0b10000001 & 0b10000000

 X = 0x80

Other X != 0 conditions:

• X = 1:

  • ​​​​​​​​​​~(0x01 | 0xFFFFFFFFF) => 0x0 & 0x80 => 0
    

• X = 2 => 0000 0000 => 0
  …
• X = 255 => 0000 0000 => 0

Conclusion

• If X = 0, the outcome from DETECTNULL(X) will be 0x80.
• If X != 0, the outcome will be 0.

This detecting NULL implementation is more efficent than compares one byte at the time like this:

unsigned int strlen(const char *s) {
    char *p = s;
    while (*p != ’\0’) p++;
    return (p - s);
}

source: [你所不知道的 C 語言：數值系統](https://hackmd.io/@sysprog/c-numerics#算術完全可用數位邏輯實作