4

Раскопал в интернете следующий код для вычисления длинны строки (оптимизированный под большие строки)

    #define STDCALL __stdcall
const size_t STDCALL strlen4( const char * str )
{
    const char* p = str;
    while ((DWORD_PTR)p & 3)
    {
        if (!*p)
        {
            return p - str;
        }
        ++p;
    }
    DWORD v = *(DWORD*)p;
    while(!(((~v) ^ (v + 0x7efefeff)) & 0x81010100))
    {
        p += 4;
        v = *(DWORD*)p;
    }
    const size_t l = p - str;
    if (v & 0xff)
    {
        if (v & 0xff00)
        {
            if (v & 0xff0000)
            {
                return l + 3;
            }
            return l + 2;
        }
        return l + 1;
    }
    return l;
}

И я никак не могу понять, что происходит вот в этом цикле этой функции и для чего он нужен:

while ((DWORD_PTR)p & 3)
    {
        if (!*p)
        {
            return p - str;
        }
        ++p;
    }

Помогите, пожалуйста, разобраться.... Пробовал эксперементировать с разными значениями строки, и пока что мне удавалось зайти в этот цикл только в тех случаях, когда входная строка была пустой, т.е. состояла только из '0', но если это только для пустых строк, то зачем тогда цикл делать... Вообщем, помогите, пожалуйста, разобраться...

2 ответа 2

2

Указатель p указывает на текущий символ строки. Как известно, строка должна оканчиваться символом 0 (нуль-терминатор). В условии указатель разадресуется, и если он указывает на нуль-терминатор, то условие становится истинным (!0 == true), значит, мы дошли до конца строки и длина строки будет равна разности текущего адреса и адреса начала строки. В противном случае мы увеличиваем на 1 p (переходим на следующий символ) и повторяем всё сначала.

7
  • в условие выход в цикл написано (DWORD_PTR)p & 3 , я так понял что там указатель на сhar приводится к типу указатель на беззнаковый длинный int, а потом производится опперация & 3 . Я только не понимаю для чего это делается и в каких случаях этот цикл будет выполнятся...
    – shc345
    11 фев 2012 в 8:14
  • 3
    Строка (DWORD_PTR)p & 3 - это хитро замаскированное определение остатка от деления p на 4. & - побитовое И, при применении p & 3 происходит взятие последних двух битов числа p, что даёт остаток от деления p на 4. Такое взятие остатка быстрее обычного %, поэтому и используется в быстром алгоритме.
    – fori1ton
    11 фев 2012 в 8:22
  • Понятно, спасибо. Но я до сих пор не понимаю зачем нужно считать остаток от деленеия на 4 от адреса содержачегося в (DWORD_PTR)p ? Какой в этом смысл? Почему нельзя при определении длянны строки только вторым циклом while(!(((~v) ^ (v + 0x7efefeff)) & 0x81010100)){ и т.д.} Зачем нужен цикл while ((DWORD_PTR)p & 3) ?
    – shc345
    11 фев 2012 в 8:42
  • 5
    Эта хохма для процессоров, где 32-битные целые должны быть выравнены на границы 4х байт. И если строка начинается не с этой границы, то первые байты (до границы) надо проверить как-нибудь иначе (здесь -- в лоб, напрямую), поскольку попытка выбрать по этому адресу целое вызовет ошибку выравнивания. А далее операции идут уже над четырёхбайтными целыми, и с захватом байт в последней четвёрке вне строки. Но переносимость у функции ограничена: порядок байт фиксирован -- мл.байт впереди, т.е. имеет меньший адрес, а это не везде так.
    – alexlz
    11 фев 2012 в 9:32
  • Понятно, спасибо. А в каких случаях может так получится, что строка начинётся не с этой границы ?
    – shc345
    12 фев 2012 в 10:04
0

В перовом цикле происходит выравнивание адреса p на 4 байта. В нем автор проверяет не равен ли один из не выравненных байтов \0, то есть не кончается ли на нем строка. Выравнивание на 4 байта здесь делается потому, что далее выполняется чтение и итерация сразу по 4 байта, а вот это сложное условие while(!(((~v) ^ (v + 0x7efefeff)) & 0x81010100)) проверяет не содержится ли в одном из 4 байтов значение \0 то есть конец строки. Эта проверка требует чтобы прочитанные 4 байта заносились в переменную типа DWORD - целое безнаковое число. На многих процессорных архитектурах для такого чтения требуется чтобы адрес был выравнен на размер целочисленного типа то есть на те самые 4 байта. Семейство x86 (условный "интел"), при невыравненном чтении автоматически выполняет два выравненых чтения и потом склеивание нужных байтиков в одно целое, происходит это минимум в три раза медленнее чем выравненное чтение. А есть архитектуры которые молча выравнивают в какую-либо строну указатель и читают хлам по не правильному адресу, бывает и так.

Таким образом, суть оптимизации состоит в том, что обход массива символов выполняется сразу по 4 байта. Выравнивание же нужно чтобы сделать такой обход правильно и быстро.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.