Как работает реализация glibc strlen()

strlen() от K & R занимает всего несколько строк.

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

Но glibc версия намного дольше. Для простоты я удалил все комментарии и 64-битную реализацию, извлеченная версия strlen() выглядит так:

size_t strlen(const char *str)
{
    const char *char_ptr;
    const unsigned long int *longword_ptr;
    unsigned long int longword, magic_bits, himagic, lomagic;

    for (char_ptr = str; ((unsigned long int) char_ptr 
             & (sizeof (longword) - 1)) != 0; ++char_ptr)
       if (*char_ptr == '\0')
           return char_ptr - str;

    longword_ptr = (unsigned long int *) char_ptr;

    himagic = 0x80808080L;
    lomagic = 0x01010101L;

    for (;;)
    { 
        longword = *longword_ptr++;

        if (((longword - lomagic) & himagic) != 0)
        {
            const char *cp = (const char *) (longword_ptr - 1);

            if (cp[0] == 0)
                return cp - str;
            if (cp[1] == 0)
                return cp - str + 1;
            if (cp[2] == 0)
                return cp - str + 2;
            if (cp[3] == 0)
                return cp - str + 3;
        }
    }
}

С помощью очень полезного комментария (нажмите здесь), я получил большую часть того, как это работает. Вместо проверки байта '\0' by by byte, glibc strlen() проверяет каждое слово (4 байта в 32-разрядной машине, 8 байт в 64-разрядной машине). Таким образом, когда строка относительно длинная, производительность может быть улучшена.

Он проверяет первые несколько символов, читая байты байтом, пока char_ptr не будет выровнен по границе longword. Затем он использует цикл, чтобы проверить, имеет ли longword все байты с именами всех нулей. Если есть, проверьте, какой байт, и верните результат.

Часть, которую я не получаю, как это проверить, если один байт в longword является all-zeros?

if (((longword - lomagic) & himagic) != 0)

Я могу построить значение longword 0x81818181, которое может сделать 0x81818181 - 0x01010101) & 0x80808080 не равным 0, но нет всех нулевых байтов.

Связано ли это с тем, что значения ASCII варьируются от 0 до 127, поэтому 0x81 недействителен ASCII? Но я не думаю, что стандарт C заставляет использовать ASCII.

Ответы

Ответ 1

Я понял это. Не могу поверить, что это просто, я провел последние полчаса на нем.

Хорошо, что проверка

if (((longword - lomagic) & himagic) != 0)

передает значения, такие как 0x81818181 pass, потому что, если он пройдет, следующий тест на каждый байт не будет возвращаться, так как нет байта с нулевым нулем. Таким образом, цикл может продолжить проверку следующего longword.

Алгоритм проверки основан на Определите, имеет ли слово нулевой байт

unsigned int v; 
bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);

В 2 дополнение - 0x01010101 имеет тот же эффект с + 0xFEFEFEFF. Разница заключается в том, что glibc не имеет v & 0x7F7F7F7F, что гарантирует, что байты в слове имеют самый старший бит 0. Это предотвращает такие примеры, как 0x81818181, но glibc опускает его, потому что ему не нужно пропускать его, как указано ранее. Проверка правильная, если она не пропустит ни одного слова, которое имеет все нулевые байты.