не пойму реализацию strlen

здравствуйте, нарыл тут на просторах реализацию сишной функции strlen :
/* Magic numbers for the algorithm */ #if LONG_BIT == 32 static const unsigned long mask01 = 0x01010101; static const unsigned long mask80 = 0x80808080; #elif LONG_BIT == 64 static const unsigned long mask01 = 0x0101010101010101; static const unsigned long mask80 = 0x8080808080808080; #else #error Unsupported word size #endif
#define LONGPTR_MASK (sizeof(long) - 1)
/* * Helper macro to return string length if we caught the zero * byte. */ #define testbyte(x) \ do { \ if (p[x] == '\0') \ return (p - str + x); \ } while (0)
size_t strlen(const char *str) { const char *p; const unsigned long *lp;
/* Skip the first few bytes until we have an aligned p */ for (p = str; (uintptr_t)p & LONGPTR_MASK; p++) if (*p == '\0') return (p - str);
/* Scan the rest of the string using word sized operation */ for (lp = (const unsigned long *)p; ; lp++) if ((*lp - mask01) & mask80) { p = (const char *)(lp); testbyte(0); testbyte(1); testbyte(2); testbyte(3); #if (LONG_BIT >= 64) testbyte(4); testbyte(5); testbyte(6); testbyte(7); #endif }
/* NOTREACHED */ return (0); }
можете прокомментировать зачем такой треш?

Ответ

Это реализация strlen, которая работает не побайтно, а пословно. Для того она и сделана: чтобы ради пущей эффективности читать и анализировать данные из памяти не одиночными байтами, а сразу выровненными словами длиной 32 или 64 бита.
Для достижения выравнивания начальная часть строки (до требуемой границы выравнивания), обрабатывается побайтно, то есть обычным способом.
Далее строка читается пословно. Каждое прочитанное слово обрабатывается при помощи следующего бит-хака
if ((*lp - mask01) & mask80)
который анализирует все прочитанное слово (т.е. фактически "параллельно" анализирует все его байты) и приблизительно отвечает на вопрос о том, есть ли в слове *lp нулевой байт. Если данная проверка дает положительный ответ, то код под этим if при помощи макро testbyte выясняет уже, в какой точной позиции он находился.
"Приблизительность" проверки в данном случае заключается в том, что условие в if иногда может дать положительный ответ даже в случае слова без нулевого байта - если в слове присутствуют байты с единицей в старшем бите. Т.е. эта проверка допускает "ложные срабатывания" и, как следствие, вызывает ненужную побайтовую проверку через testbyte, но на корректность результата это не влияет. Строки, составленные из символов с кодами не выше 128 будут обрабатываться эффективно.
Слова же, в которых нулевой байт содержится, этой проверкой будут заведомо обнаружены.
Более сложная версия условия, основанная на тех же масках
if ((*lp - mask01) & ~*lp & mask80)
гарантировала бы точное определение наличия нулевого байта в слове, но авторы, очевидно, решили, что эффективнее будет работать именно их приближенный вариант (скорее всего потому, что код рассчитан на строки из символов латинского алфавита).
Теоретически, такая реализация обладает одной формальной проблемой: при пословном чтении содержимого строки может получиться так, что последнее читаемое слово будет "торчать" за пределы самой строки и выделенной для нее памяти. На практике это не приводит к проблемам, так как выделение и/или защита памяти обычно делаются по границам, выровненным как минимум до размера полного слова. Однако подобные "вылеты" могут вызвать жалобы от средств динамического анализа кода, типа valgrind.