Что такое кольцевой¹ хеш?

Основная особенность кольцевого хеша в том, что вычисление следующего значения хеш-суммы для блока данных, сдвинутого на один или более байт, производится на основании предыдущего значения хеш-суммы, вместо того, чтобы вычислять его заново. Это способствует значительному ускорению вычислений для задач, которым необходимо вычислять хеш-суммы для каждого байтового (или более) смещения. Такой хеш используется в rsync, системах блочной дедупликации данных, алгоритме Рабина — Карпа (поиск подстроки в строке).

Алгоритм Adler32

Одна из самых простых хеш-функций, которую можно придумать — сумма всех байт (или слов) по какому-то модулю (например, значению, ограниченному разрядной сеткой). Несмотря на высокую производительность, такая хеш-сумма дает много коллизий. И объяснение тому просто: «От перемены мест слагаемых сумма не меняется». Алгоритм Adler'а почти настолько же прост, только учитывает расположение слагаемых. Хеш-сумма Adler32 состоит из двух 16-разрядных слов. Первое слово — это сумма всех байт по модулю. Второе — сумма значений первого слова на каждой итерации по этому же модулю.

Если длина входной последовательности — N, то второе слово можно представить как сумму произведений i-го байта на (N - i + 1). Например, для последовательности 1, 2, 3, второе слово будет равным 1 + (1 + 2) + (1 + 2 + 3), или же 1•3 + 2•2 + 3•1. Таким образом, если переставить два байта во входной последовательности, то сумма поменяется из-за изменения коэффициентов при слагаемых.

Модуль для Adler32 выбран как наибольшее простое число, которое меньше 2¹⁶. Пока я тут это пишу, читатель, должно быть, уже успел прикинуть, что это число — 65521. Такой выбор должен улучшить вероятностные характеристики хеш-функции. Начальное значение суммы (первого слова) — 1.

Следует заметить, что данный хеш не является достаточно надежным. Вероятность коллизий у него даже выше, чем у CRC32. При этом Adler32 быстрее CRC32 в несколько раз. Это может дать преимущество в задачах, в которых после сравнения хеша на равенство в случае успеха производится более надежное сравнение (например, по криптографическому хешу или побайтовое сравнение).

Прямая реализация алгоритма выглядит следующим образом:

uint32_t adler32(unsigned char *data, int len){

    uint32_t sum1 = 1;
    uint32_t sum2 = 0;

    for (i = 0; i < len; i++){
        sum1 = (sum1 + buf[i]) % BASE;
        sum2 = (sum2 + sum1) % BASE;
    }

    return (sum2 << 16) | sum1;
}

Более эффективная реализация алгоритма Adler32 из библиотеки zlib:

uint32_t adler32(uint32_t adler, const unsigned char* buf,
                 unsigned len){

    uint32_t sum2;
    unsigned n;

    /* Обработка частных случаев...*/

    /* do length NMAX blocks -- requires just one modulo operation */
    while (len >= NMAX) {
        len -= NMAX;
        n = NMAX / 16;          /* NMAX is divisible by 16 */
        do {
            DO16(buf);          /* 16 sums unrolled */
            buf += 16;
        } while (--n);
        adler %= BASE;
        sum2 %= BASE;
    }

    /* Обработка оставшихся элементов массива...*/

    /* return recombined sums */
    return adler | (sum2 << 16);
}

Основная оптимизация здесь — это выполнения операции остатка от деления каждые NMAX байт вместо одного. NMAX — это максимальное число, при котором не происходит переполнение sum2. Вычислить его можно, исходя из того, что sum2 является суммой арифметической прогрессии с разностью d=255 (берем наихудший случай). Так, при 32-разрядном представлении чисел, получаем

(1 • 2 + 255 • (NMAX - 1)) • NMAX/2 = 2³² - 1

Открыв исходный файл решая квадратное уравнение, получаем NMAX = 5552 с учетом того, что оно должно быть кратно 16.

Макрос DO16(buf) разворачивается в следующее выражение

adler += buf[0]; sum2 += adler; adler += buf[1]; sum2 += adler; ...
adler += buf[15]; sum2 += adler;

Данная реализация алгоритма работает в 5-6 раз быстрее, чем реализация «в лоб».

Превращаем Adler32 в кольцевой хеш

Как изменится хеш-сумма, если из последовательности байт убрать первый, а в конец добавить новый? Очевидно, что первое слово «увеличится» на разность нового байта и старого. Что касается второго слова, то значение первого байта учтено в хеше то количество раз, каким является размер блока. Отняв от предыдущего значения слова произведение длины последовательности и значения первого байта, мы получим хеш, соответствующий последовательности без первого байта. Теперь добавим новое значение первого слова, отнимем единицу (иначе она будет учтена дважды) и получим новый хеш блока, смещенного на 1 байт вправо. При этом берем полученные значения по модулю.

inline uint32_t roll(int32_t adler, unsigned char oldbyte,
                     unsigned char newbyte, unsigned len){

    int32_t sum2 = (adler >> 16) & 0xffff;
    adler &= 0xffff;

    adler += newbyte - oldbyte;
    if(adler >= (int32_t) BASE)
        adler -= BASE;
    else if(adler < 0)
        adler += BASE;

    sum2 = (int32_t) (sum2 - len * oldbyte + adler - 1) %
           (int32_t) BASE;
    if(sum2 < 0){
        sum2 += BASE;

    return adler | (sum2 << 16);
}

Тут возможны отрицательные промежуточные значения, поэтому при операциях сравнения и модуля приходится приводить переменные и константы к числам со знаком. Для избежания переполнения на 32-разрядной архитектуре при перемножении длины блока на старый байт длина блока не должна превышать 8МБ. Функцию желательно объявить как inline, чтобы не расходовать дополнительное время на вызов функции и передачу аргументов.

Очевидно, у процесса оптимизации нет предела. И данная реализация тому не исключение. Например, можно изменить тип результата, возвращаемый функцией adler32 на структуру, содержащую два 32-разрядных слова, что может уменьшить количество ненужных операций по упаковке и распаковке хеш-суммы.