GNU libc имеет эта реализация strcspn()
, который, цитата,
Returns the length of the maximum initial segment of S which contains no characters from REJECT.
Он умен в своей реализации, поскольку создает таблицу поиска из 256 записей, чтобы сделать операцию определения того, находится ли символ в наборе reject
, простым поиском в массиве O (1), в отличие, например, от реализация OpenBSD, который использует вложенные циклы.
Однако мне любопытно, как приведенный ниже цикл c0/c1/c2/c3 может получить доступ к памяти после видимого конца str
без ошибки страницы или чего-то подобного.
Гарантирует ли стандарт C, например, что все строки, находящиеся в стеке, куче или статически выделенные, выровнены до 4 байтов, поэтому безопасно обращаться к трем после последнего 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;
}
Связано: stackoverflow.com/a/57651888/918959
почти дубликат: Безопасно ли читать дальше конца буфера на одной странице на x86 и x64?
Этому циклу предшествует строка:
s = (unsigned char *) PTR_ALIGN_DOWN (s, 4);
Это гарантирует, что s
выровнено по 4 байтам. Затем цикл считывает по 4 байта за раз. Это гарантирует, что даже если он будет считан за конец строки, дополнительные прочитанные байты все равно будут находиться в том же 4-байтовом слове.
Если вы строго придерживаетесь стандарта C, это приводит к неопределенному поведению. Но glibc предполагает, что на платформах, на которых он работает, размер страницы кратен 4 байтам, и что чтение после конца буфера не вызовет никаких проблем, если оно находится на той же странице.
Звучит правдоподобно! Интересно, документировано ли это предположение где-нибудь.
Обратите внимание, что это предположение практически является данностью: страницы памяти обычно большие (4 КБ), всегда выровнены по своему естественному размеру и всегда содержат степень 2 байта. Это следует непосредственно из того, как работает постраничная адресация. Таким образом, вы можете так же легко прочитать всю кэш-линию (64 байта = 512 битов = один регистр AVX-512) из выровненного адреса и быть в порядке: либо все 64 байта отображаются, либо нет, между ними ничего нет.
Единственный случай, когда это может привести к сбою, - это запуск очень агрессивной проверки доступа к памяти, такой как valgrind, о которой нужно сообщить, можно ли безопасно игнорировать эту функцию.
@GemTaylor Это правда. Я думаю, что valgrind предоставляет альтернативные реализации функций glibc, таких как strcspn
, чтобы избежать этой проблемы.
Возможно, они знают, что в архитектурах, для которых применяется этот код, сегменты памяти всегда продолжаются до следующего кратного четырем байтам?