GNU libc имеет эту реализацию strcspn(), которая, кавычка,
Возвращает длину максимального начального сегмента S, который не содержит символов из REJECT.
Это разумно в своей реализации, поскольку он создает таблицу поиска с 256 записями, чтобы сделать операцию нахождения того, находится ли символ в reject, простой просмотр массива O (1), в отличие отнапример, реализация OpenBSD , которая использует вложенные циклы.
Однако мне любопытно, как приведенный ниже цикл c0 / c1 / c2 / c3 может получить доступ к памяти после видимого конца strбез ошибки страницы или подобного.
Гарантирует ли, например, стандарт C, что все строки, будь то в стеке, куче или статически распределенных, имеют свои распределения, выровненные до 4 байтов, так что доступ к ним безопасендо 3 последних последних NUL?
Я добавил несколько комментариев в коде ниже;оригинал (как указано выше) не имеет ничего.
/* Align a pointer by rounding down to closest size. */
#define PTR_ALIGN_DOWN(base, size) ...
size_t strcspn (const char *str, const char *reject)
{
if ((reject[0] == '\0') || (reject[1] == '\0'))
return __strchrnul (str, reject [0]) - str;
// Build a lookup table containing all characters from `reject`;
// due to the way the `do/while` loop below is constructed, `table`
// will end up having `table[0] = 1` always, which works as an
// exit condition.
unsigned char p[256] = {0};
unsigned char *s = (unsigned char*) reject;
unsigned char tmp;
do
p[tmp = *s++] = 1;
while (tmp);
// Check the first 4 bytes "by hand".
s = (unsigned char*) str;
if (p[s[0]]) return 0;
if (p[s[1]]) return 1;
if (p[s[2]]) return 2;
if (p[s[3]]) return 3;
// Align the pointer (for whichever reason?)
s = (unsigned char *) PTR_ALIGN_DOWN (s, 4);
unsigned int c0, c1, c2, c3;
do
{
s += 4; // Loop over 4 characters at a time (the first 4 bytes were checked before)
c0 = p[s[0]];
c1 = p[s[1]];
c2 = p[s[2]];
c3 = p[s[3]];
}
// break if any of c0, c1, c2, or c3 is nonzero,
// i.e. if we've either found one of the characters in `reject`, or a zero
while ((c0 | c1 | c2 | c3) == 0);
size_t count = s - (unsigned char *) str;
// figure out the actual offset based on which of c0..3 is set
return (c0 | c1) != 0 ? count - c0 + 1 : count - c2 + 3;
}