# strlen in IOS
contributed by < [Eric Lin](https://github.com/ericlinsechs) >

## Overview
The technique used to detect `\0` character by [strlen](https://opensource.apple.com/source/Libc/Libc-583/arm/string/strlen.s) 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](https://github.com/eblot/newlib/blob/master/newlib/libc/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](https://en.wikipedia.org/wiki/De_Morgan%27s_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#%E7%AE%97%E8%A1%93%E5%AE%8C%E5%85%A8%E5%8F%AF%E7%94%A8%E6%95%B8%E4%BD%8D%E9%82%8F%E8%BC%AF%E5%AF%A6%E4%BD%9C