CRC
Очень вольный пересказ классического текста Ross N. Williams A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, с лакунами, добавлениями, изменениями, попытками изложить лучше сложные места и пропустить простые. Вообще текст рекомендую, он очень милый и прекрасно написан, но некоторые места мне всё же было сложно понять, поэтому я подошел к ним иначе.
CRC это семейство алгоритмов для вычисления контрольной суммы, объединенных общей идеей, но отличающихся набором параметров.
Подробности того, как оно внутри устроены -- абсолютно бесполезное знание почти для всех почти всегда.
А мне просто было интересно.
0. Intro. Арифметика полиномов по модулю 2
Ужасно лень расписывать, простите.
Но на всякий случай главное кратко, в режиме тезисов, и не вполне математически-грамотно.
Полиномы, они же многочлены, это такие штуки типа 3x^4 + 2x^3 + x + 7. Их можно друг с другом складывать, вычитать, умножать друг на друга и делить в столбик с остатком.
Степень полинома это наибольшая входящая в него степень x. Числа при степенях x называются коэффициентами (последний считается коэффициентом при x^0), коэффициент при старшей степени x -- старший. Они могут быть равны нулю, в принципе хоть все, кроме старшего. Количество коэффициентов полинома всегда на 1 больше, чем его степень (нулевые коэффициенты тоже считаются).
В арифметике по модулю 2 всего два числа, 0 и 1. И от обычной она отличается тем, что 1 + 1 = 0, а 0 - 1 = 1. Поскольку, как и в обычной, 1 - 1 тоже равно 0, и 0 + 1 = 1, операции + и - неотличимы друг от друга, и обе сводятся к операции xor.
Наконец, арифметика полиномов по модулю 2, это арифметика полиномов, у которых коэффициенты только 0 и 1, и они складываются-вычитаются по модулю 2. И между сложением и вычитанием разницы тоже нет.
x^7 + x^6 + x^4 + x
+/- x^6 + x^3 + x^2 + x + 1
-------------------------------------
= x^7 + x^4 + x^3 + x^2 + 1
деление как-то так:
x^7 + x^6 + x^4 + x | x^2 + x + 1
---------------
x^7 + x^6 + x^5 | x^5 + x^3 + x + 1
---------------
x^5 + x^4
x^5 + x^4 + x^3
---------------
x^3 + x
x^3 + x^2 + x
-----------------
x^2
x^2 + x + 1
-----------
x + 1
Получилось частное x^5 + x^3 + x + 1 (оно нам будет не нужно) и остаток x + 1. "Остаток" -- первый получившийся полином, степени меньше делителя.
Полином степени n естественным образом представляется в виде вектора из n+1 коэффициента, а в нашем случае -- строки из 0 и 1. В общем, любое двоичное число можно считать соответствующим полиномом, главное договориться, с какой стороны старший коэффициент.
Та же самая операция деления для двоичных чисел:
11010010 | 111
-----
111 | 101011
---
110
111
---
101
111
---
100
111
---
11
От обычного деления в столбик отличается тем, что вместо вычитания выполняется xor, и мы регулярно "вычитаем" из "меньшего" "большее". Все слова в кавычках потому, что хотя для нормальной арифметики там меньшее и большее (101 и 111), но когда сложение и вычитание слились в одно, сравнение становится довольно условным. Сравниваются степени полиномов, и если они равны, то ни один не больше другого и можно вычитать, главное что при этом уменьшается старшая степень.
1. Базовый алгоритм абстрактного CRC
Математическая идея: у нас есть полином G степени n. Берем сообщение, дополняем его сзади n битами нулей, интерпретируем его как длинный-длинный полином и делим с остатком на G в арифметике "по модулю 2". Остаток -- значение CRC.
При реализации сообщение считается потоком байт, первые байты соответствуют старшим степеням, старшие биты в байтах соответствуют старшим степеням.
Идея реализации -- деление в столбик.
Давайте ещё раз посмотрим на пример, добавив туда "пустые" стадии, на которых нет вычитания, а в частное добавляется 0.
11010010 | 111
-----
111 | 101011
---
011 <---- нет вычитания, т.к. 011 < 111
---
110
111
---
010 <---- нет вычитания, т.к. 010 < 111
---
101
111
---
100
111
---
11
Что тут можно увидеть (если знать правильный ответ)?
Степень полинома (делителя) 2, он состоит из трех битов. На каждом шаге мы сносим из делимого по одному биту, каждый раз получая тройку. Если старший из этих трех битов равен 1, то происходит вычитание делителя, в результате к следующему шагу старший бит тройки всегда обнуляется. Если старший бит 0, ничего не происходит, переходим к следующему шагу.
То есть при реализации совсем "в лоб" нам нужен регистр длиной с полином, и на каждом шаге мы будем задвигать в него справа очередной бит делимого, и, если старший бит регистра равен 1, вычитать полином (ксорить, так как по модулю 2). И в конце в этом регистре останется остаток от деления.
Но можно сэкономить один бит. У полинома старший бит всегда 1, информативны только младшие. Получающийся в конце остаток тоже на один бит короче полинома. А в процессе старший бит регистра нам нужен только как флаг "можно вычитать", так как он сам при вычитании всегда обращается в 0. И чтобы вычитать из такого укороченного на бит регистра нам достаточно укороченного на бит полинома.
регистр = 0 // регистр шириной n бит
сообщение' = сообщение + n битов нулей
пока в сообщении' есть ещё биты
в регистр справа задвигаем очередной старший бит сообщения'
если выдвинувшийся_из_регистра_старший_бит == 1 // старшие степени сравнялись, можно вычитать
регистр ^= G // G -- младшие n бит полинома
Профит! В регистре остаток от деления.
Эту штуку назовем базовый алгоритм.
2. Базовый табличный алгоритм абстрактного CRC
Так очень медленно. Давайте делать это не по битам, а по байтам.
То есть из регистра на каждом шаге будет выдвигаться целый байт, а нам надо как-то понять, что делать с регистром, чтобы за одну операцию получить то же самое, что в базовом алгоритме получалось за 8 операций.
Поймем, что это возможно. То есть, что старший байт полностью определяет, какие операции будут совершаться с регистром.
Для начала, цикл можно записать без "если":
пока в сообщении' есть ещё биты
в регистр справа задвигаем очередной старший бит сообщения'
регистр ^= G * выдвинутый_из_регистра_старший_бит
если старший бит был 0, то это xor с 0, который ничего не меняет, а если 1, то это xor с G. То есть всё как раньше, алгоритм корректный.
Теперь проследим несколько шагов:
- какая операция совершаются с регистром на текущем шаге определяет старший бит r7.
- операция на следующем шаге -- следующий старший бит, который получен из r6 и возможно старшего бита полинома, r7' = r6 ^ (p7 * r7)
- следующий старший бит, получается как r7'' = r5 ^ (p6 * r7) ^ (p7 * r7') = r5 ^ (p6 * r7) ^ (p7 * (r6 ^ (p7 * r7)))
- и так далее
Что тут важно: что очередной старший бит зависит от предыдущих старших битов и не зависит от младших битов. Если мы все младшие биты заменим на 0, набор производимых с регистром операций не изменится.
А что при этом происходит с остальными битами? Это проще всего понять, развернув модель наоборот: пусть у нас не сообщение по одному биту пропихивается в регистр, а полином скользит вдоль сообщения.
r7r6r5r4r3r2r1r0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
r7 * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7'' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7'''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7''''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7'''''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7''''''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p
На каждом шаге полином сдвигается на бит вправо.
Область слева от красного это бывший первый байт регистра, за восемь шагов он оказался полностью снаружи.
А красная область это часть сообщения, оказавшаяся в регистре на последнем шаге. И видно, как она меняется в результате этого процесса: операция xor ассоциативна, так что мы можем сначала сложить все эти хвосты многочленов (помноженные на 0 или 1, смотря какой старший бит), получить одно число, и потом уже выполнить xor с сообщением. И исходная задача сводится к вычислению этого числа.
Алгоритм для этого очевиден:
- прогоняем через базовый алгоритм сообщение состоящее из байта r7r6..r0.
- по алгоритму он дополнится с конца нулями и алгоритм остановится как раз в тот момент, когда из регистра будет вытолкнут r0.
- в регистре при этом останутся следы xor-а полинома по алгоритму.
- поскольку xxxx..xxx в данном случае равно 000...000, это в чистом виде сумма хвостов многочленов с нужными множителями, то есть как раз то, что мы хотели.
Таким образом можно для всех 256 возможных старших байт сформировать табличку. После чего получить базовый табличный алгоритм
регистр = 0
сообщение' = сообщение + n битов нулей
пока в сообщении' есть ещё байты
в регистр справа задвигаем очередной старший байт сообщения'
регистр ^= таблица[старший_выдвинутый_байт]
Он уже гораздо быстрее.
3. Прямой алгоритм абстрактного CRC
Оба предыдущие алгоритма напрямую повторяют деление в столбик. Идеологически это верно, но разработчики CRC были хитры и коварны, и, как будет понятно ниже, на практике это влияет...
Пока посмотрим на такое соображение.
На последних тактах работы базового алгоритма в регистр проталкиваются завершающие нули, которыми было расширено исходное сообщение. До того в регистре находится результат xor-а последних байтов сообщения с какими-то значениями из таблицы. А в ходе этих последних тактов в регистре не остается ни одного бита, значение которого получено через xor с данными сообщения. То есть в регистре оказывается сколько-то раз поксоренный сам с собою полином со сдвигами.
А от содержимого сообщения зависит только сколько именно раз и с какими именно сдвигами.
Это позволяет подойти к вопросу так: чтобы получить такое же состояние регистра, как в конце базового алгоритма, нам не нужно использовать в самом регистре биты сообщения, нам достаточно знать, когда нужно выполнять xor полинома с текущим значением регистра, а когда нет.
Предлагается такой алгоритм (объяснение ниже):
регистр = 0
пока в сообщении есть ещё биты
в регистр справа задвигаем 0
если выдвинувшийся_из_регистра_старший_бит ^ старший_бит_сообщения == 1
регистр ^= G
Что изменилось:
- xor с данными сообщения выполняется в самый последний момент, когда нужно получить признак "ксорим полином с регистром или нет"
- не расширяем сообщение нулями, так как не надо проталкивать данные через весь регистр, они сразу используются на его краю
- выпала стадия начального проталкивания данных через регистр. Это ничего не меняет, если в регистре исходно 0. А вот если не 0, то результаты будут разные.
Чтобы осознать, как это работает, нужно развить мысль про скользящий вдоль сообщения регистр.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
| | '
| | '
............. '
| |
| |
Утверждение: на каждом шаге xor текущего значения регистра (по этому новому алгоритму), с областью сообщения, под которой он находится, равен значению регистра в базовом алгоритме на соответствующем шаге.
Доказывается по индукции: если это было так на прошлом шаге, то на текущем шаге мы верно определили признак "ксорим полином или нет", а значит и на следующем шаге тоже будет верно, чтд.
Аналогично можно поменять табличный алгоритм
регистр = 0
пока в сообщении есть ещё байты
в регистр справа задвигаем нулевой байт
регистр ^= таблица[старший_выдвинутый_байт ^ старший_байт_сообщения]
Сама таблица при этом та же самая.
4. Отраженные алгоритмы
По историческим причинам, некоторые версии CRC читают биты в байтах задом наперед. То есть самый младший бит байта считается старшей степенью полинома, а старший бит -- младшей.
Есть очевидный способ реализации -- просто переворачивать каждый байт. Для эффективности это можно делать по таблице, более того, для табличного алгоритма можно просто сразу составить подходящую "отраженную" таблицу.
Но есть и неочевидный.
Возвращаясь мыслями к базовому алгоритму, представим его наглядно. Вот регистр, вот полином G, вот сообщение как огромная строка бит заходит в регистр справа и биты выталкиваются из него слева по одному.
Теперь, если все это отразить зеркально. Отразить полином (так что его старший бит торчит за пределы регистра не слева, а справа), отразить всю строку бит, пропускать её в регистр слева, а биты будут выталкиваться справа. То в итоге, из соображений симметрии, мы получим точно такой же результат в регистре, но только тоже отраженный.
Это и есть наш неочевидный способ, за исключением того, что биты в байтах мы отражать не будем. И тогда биты будут поступать в регистр в том же порядке, что в "очевидном способе реализации" выше, младшими битами вперед. И поэтому тоже получим отраженный результат, но не исходного алгоритма, а отраженного.
Конечно в таком духе можно сделать и табличный алгоритм тоже. И прямые алгоритмы ни чем не хуже базовых.
5. Параметры конкретных алгоритмов CRC
Эта классификация была предложена Ross N. Williams в этом самом тексте и стала общепринятой.
- Степень полинома (width) -- просто число. Обычно 32, 16 или 8, но могут быть варианты.
- Сам полином (poly) -- все биты кроме старшего, то есть как раз тот вид, который нужен для алгоритма. Например 0x07 -- полином CRC-8, 0x04C11DB7 -- популярный полином для нескольких вариантов CRC-32.
- Начальное значение регистра (init) -- что лежит в регистре до начала работы алгоритма. И вот тут оказывается важно, базовый алгоритм использовать, или прямой. AFAIK, обычно подразумевается прямой.
- Отражен ли вход (refin) -- нужно ли зеркально отражать байты
- Отражен ли выход (refout) -- нужно ли в конце зеркально отражать полученный результат. Если оба эти параметры true, использование отраженного алгоритма позволяет добиться сразу и того и другого.
- Значение, с которым результат дополнительно xor-ится в самом конце (xorout).
- Пример вычисления на строке "123456789" (check)
Вот тут есть много примеров разных алгоритмов с возможностью посчитать https://crccalc.com/
Ещё больше примеров в вики, но там только параметры, посчитать не даёт.
CRC это семейство алгоритмов для вычисления контрольной суммы, объединенных общей идеей, но отличающихся набором параметров.
Подробности того, как оно внутри устроены -- абсолютно бесполезное знание почти для всех почти всегда.
А мне просто было интересно.
0. Intro. Арифметика полиномов по модулю 2
Ужасно лень расписывать, простите.
Но на всякий случай главное кратко, в режиме тезисов, и не вполне математически-грамотно.
Полиномы, они же многочлены, это такие штуки типа 3x^4 + 2x^3 + x + 7. Их можно друг с другом складывать, вычитать, умножать друг на друга и делить в столбик с остатком.
Степень полинома это наибольшая входящая в него степень x. Числа при степенях x называются коэффициентами (последний считается коэффициентом при x^0), коэффициент при старшей степени x -- старший. Они могут быть равны нулю, в принципе хоть все, кроме старшего. Количество коэффициентов полинома всегда на 1 больше, чем его степень (нулевые коэффициенты тоже считаются).
В арифметике по модулю 2 всего два числа, 0 и 1. И от обычной она отличается тем, что 1 + 1 = 0, а 0 - 1 = 1. Поскольку, как и в обычной, 1 - 1 тоже равно 0, и 0 + 1 = 1, операции + и - неотличимы друг от друга, и обе сводятся к операции xor.
Наконец, арифметика полиномов по модулю 2, это арифметика полиномов, у которых коэффициенты только 0 и 1, и они складываются-вычитаются по модулю 2. И между сложением и вычитанием разницы тоже нет.
x^7 + x^6 + x^4 + x
+/- x^6 + x^3 + x^2 + x + 1
-------------------------------------
= x^7 + x^4 + x^3 + x^2 + 1
деление как-то так:
x^7 + x^6 + x^4 + x | x^2 + x + 1
---------------
x^7 + x^6 + x^5 | x^5 + x^3 + x + 1
---------------
x^5 + x^4
x^5 + x^4 + x^3
---------------
x^3 + x
x^3 + x^2 + x
-----------------
x^2
x^2 + x + 1
-----------
x + 1
Получилось частное x^5 + x^3 + x + 1 (оно нам будет не нужно) и остаток x + 1. "Остаток" -- первый получившийся полином, степени меньше делителя.
Полином степени n естественным образом представляется в виде вектора из n+1 коэффициента, а в нашем случае -- строки из 0 и 1. В общем, любое двоичное число можно считать соответствующим полиномом, главное договориться, с какой стороны старший коэффициент.
Та же самая операция деления для двоичных чисел:
11010010 | 111
-----
111 | 101011
---
110
111
---
101
111
---
100
111
---
11
От обычного деления в столбик отличается тем, что вместо вычитания выполняется xor, и мы регулярно "вычитаем" из "меньшего" "большее". Все слова в кавычках потому, что хотя для нормальной арифметики там меньшее и большее (101 и 111), но когда сложение и вычитание слились в одно, сравнение становится довольно условным. Сравниваются степени полиномов, и если они равны, то ни один не больше другого и можно вычитать, главное что при этом уменьшается старшая степень.
1. Базовый алгоритм абстрактного CRC
Математическая идея: у нас есть полином G степени n. Берем сообщение, дополняем его сзади n битами нулей, интерпретируем его как длинный-длинный полином и делим с остатком на G в арифметике "по модулю 2". Остаток -- значение CRC.
При реализации сообщение считается потоком байт, первые байты соответствуют старшим степеням, старшие биты в байтах соответствуют старшим степеням.
Идея реализации -- деление в столбик.
Давайте ещё раз посмотрим на пример, добавив туда "пустые" стадии, на которых нет вычитания, а в частное добавляется 0.
11010010 | 111
-----
111 | 101011
---
011 <---- нет вычитания, т.к. 011 < 111
---
110
111
---
010 <---- нет вычитания, т.к. 010 < 111
---
101
111
---
100
111
---
11
Что тут можно увидеть (если знать правильный ответ)?
Степень полинома (делителя) 2, он состоит из трех битов. На каждом шаге мы сносим из делимого по одному биту, каждый раз получая тройку. Если старший из этих трех битов равен 1, то происходит вычитание делителя, в результате к следующему шагу старший бит тройки всегда обнуляется. Если старший бит 0, ничего не происходит, переходим к следующему шагу.
То есть при реализации совсем "в лоб" нам нужен регистр длиной с полином, и на каждом шаге мы будем задвигать в него справа очередной бит делимого, и, если старший бит регистра равен 1, вычитать полином (ксорить, так как по модулю 2). И в конце в этом регистре останется остаток от деления.
Но можно сэкономить один бит. У полинома старший бит всегда 1, информативны только младшие. Получающийся в конце остаток тоже на один бит короче полинома. А в процессе старший бит регистра нам нужен только как флаг "можно вычитать", так как он сам при вычитании всегда обращается в 0. И чтобы вычитать из такого укороченного на бит регистра нам достаточно укороченного на бит полинома.
регистр = 0 // регистр шириной n бит
сообщение' = сообщение + n битов нулей
пока в сообщении' есть ещё биты
в регистр справа задвигаем очередной старший бит сообщения'
если выдвинувшийся_из_регистра_старший_бит == 1 // старшие степени сравнялись, можно вычитать
регистр ^= G // G -- младшие n бит полинома
Профит! В регистре остаток от деления.
Эту штуку назовем базовый алгоритм.
2. Базовый табличный алгоритм абстрактного CRC
Так очень медленно. Давайте делать это не по битам, а по байтам.
То есть из регистра на каждом шаге будет выдвигаться целый байт, а нам надо как-то понять, что делать с регистром, чтобы за одну операцию получить то же самое, что в базовом алгоритме получалось за 8 операций.
Поймем, что это возможно. То есть, что старший байт полностью определяет, какие операции будут совершаться с регистром.
Для начала, цикл можно записать без "если":
пока в сообщении' есть ещё биты
в регистр справа задвигаем очередной старший бит сообщения'
регистр ^= G * выдвинутый_из_регистра_старший_бит
если старший бит был 0, то это xor с 0, который ничего не меняет, а если 1, то это xor с G. То есть всё как раньше, алгоритм корректный.
Теперь проследим несколько шагов:
- какая операция совершаются с регистром на текущем шаге определяет старший бит r7.
- операция на следующем шаге -- следующий старший бит, который получен из r6 и возможно старшего бита полинома, r7' = r6 ^ (p7 * r7)
- следующий старший бит, получается как r7'' = r5 ^ (p6 * r7) ^ (p7 * r7') = r5 ^ (p6 * r7) ^ (p7 * (r6 ^ (p7 * r7)))
- и так далее
Что тут важно: что очередной старший бит зависит от предыдущих старших битов и не зависит от младших битов. Если мы все младшие биты заменим на 0, набор производимых с регистром операций не изменится.
А что при этом происходит с остальными битами? Это проще всего понять, развернув модель наоборот: пусть у нас не сообщение по одному биту пропихивается в регистр, а полином скользит вдоль сообщения.
r7r6r5r4r3r2r1r0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
r7 * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7'' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7'''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7''''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7'''''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p '
r7''''''' * p7p6p5p4p3p2p1p0 ...... .......... ........................ p
На каждом шаге полином сдвигается на бит вправо.
Область слева от красного это бывший первый байт регистра, за восемь шагов он оказался полностью снаружи.
А красная область это часть сообщения, оказавшаяся в регистре на последнем шаге. И видно, как она меняется в результате этого процесса: операция xor ассоциативна, так что мы можем сначала сложить все эти хвосты многочленов (помноженные на 0 или 1, смотря какой старший бит), получить одно число, и потом уже выполнить xor с сообщением. И исходная задача сводится к вычислению этого числа.
Алгоритм для этого очевиден:
- прогоняем через базовый алгоритм сообщение состоящее из байта r7r6..r0.
- по алгоритму он дополнится с конца нулями и алгоритм остановится как раз в тот момент, когда из регистра будет вытолкнут r0.
- в регистре при этом останутся следы xor-а полинома по алгоритму.
- поскольку xxxx..xxx в данном случае равно 000...000, это в чистом виде сумма хвостов многочленов с нужными множителями, то есть как раз то, что мы хотели.
Таким образом можно для всех 256 возможных старших байт сформировать табличку. После чего получить базовый табличный алгоритм
регистр = 0
сообщение' = сообщение + n битов нулей
пока в сообщении' есть ещё байты
в регистр справа задвигаем очередной старший байт сообщения'
регистр ^= таблица[старший_выдвинутый_байт]
Он уже гораздо быстрее.
3. Прямой алгоритм абстрактного CRC
Оба предыдущие алгоритма напрямую повторяют деление в столбик. Идеологически это верно, но разработчики CRC были хитры и коварны, и, как будет понятно ниже, на практике это влияет...
Пока посмотрим на такое соображение.
На последних тактах работы базового алгоритма в регистр проталкиваются завершающие нули, которыми было расширено исходное сообщение. До того в регистре находится результат xor-а последних байтов сообщения с какими-то значениями из таблицы. А в ходе этих последних тактов в регистре не остается ни одного бита, значение которого получено через xor с данными сообщения. То есть в регистре оказывается сколько-то раз поксоренный сам с собою полином со сдвигами.
А от содержимого сообщения зависит только сколько именно раз и с какими именно сдвигами.
Это позволяет подойти к вопросу так: чтобы получить такое же состояние регистра, как в конце базового алгоритма, нам не нужно использовать в самом регистре биты сообщения, нам достаточно знать, когда нужно выполнять xor полинома с текущим значением регистра, а когда нет.
Предлагается такой алгоритм (объяснение ниже):
регистр = 0
пока в сообщении есть ещё биты
в регистр справа задвигаем 0
если выдвинувшийся_из_регистра_старший_бит ^ старший_бит_сообщения == 1
регистр ^= G
Что изменилось:
- xor с данными сообщения выполняется в самый последний момент, когда нужно получить признак "ксорим полином с регистром или нет"
- не расширяем сообщение нулями, так как не надо проталкивать данные через весь регистр, они сразу используются на его краю
- выпала стадия начального проталкивания данных через регистр. Это ничего не меняет, если в регистре исходно 0. А вот если не 0, то результаты будут разные.
Чтобы осознать, как это работает, нужно развить мысль про скользящий вдоль сообщения регистр.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
| | '
| | '
............. '
| |
| |
Утверждение: на каждом шаге xor текущего значения регистра (по этому новому алгоритму), с областью сообщения, под которой он находится, равен значению регистра в базовом алгоритме на соответствующем шаге.
Доказывается по индукции: если это было так на прошлом шаге, то на текущем шаге мы верно определили признак "ксорим полином или нет", а значит и на следующем шаге тоже будет верно, чтд.
Аналогично можно поменять табличный алгоритм
регистр = 0
пока в сообщении есть ещё байты
в регистр справа задвигаем нулевой байт
регистр ^= таблица[старший_выдвинутый_байт ^ старший_байт_сообщения]
Сама таблица при этом та же самая.
4. Отраженные алгоритмы
По историческим причинам, некоторые версии CRC читают биты в байтах задом наперед. То есть самый младший бит байта считается старшей степенью полинома, а старший бит -- младшей.
Есть очевидный способ реализации -- просто переворачивать каждый байт. Для эффективности это можно делать по таблице, более того, для табличного алгоритма можно просто сразу составить подходящую "отраженную" таблицу.
Но есть и неочевидный.
Возвращаясь мыслями к базовому алгоритму, представим его наглядно. Вот регистр, вот полином G, вот сообщение как огромная строка бит заходит в регистр справа и биты выталкиваются из него слева по одному.
Теперь, если все это отразить зеркально. Отразить полином (так что его старший бит торчит за пределы регистра не слева, а справа), отразить всю строку бит, пропускать её в регистр слева, а биты будут выталкиваться справа. То в итоге, из соображений симметрии, мы получим точно такой же результат в регистре, но только тоже отраженный.
Это и есть наш неочевидный способ, за исключением того, что биты в байтах мы отражать не будем. И тогда биты будут поступать в регистр в том же порядке, что в "очевидном способе реализации" выше, младшими битами вперед. И поэтому тоже получим отраженный результат, но не исходного алгоритма, а отраженного.
Конечно в таком духе можно сделать и табличный алгоритм тоже. И прямые алгоритмы ни чем не хуже базовых.
5. Параметры конкретных алгоритмов CRC
Эта классификация была предложена Ross N. Williams в этом самом тексте и стала общепринятой.
- Степень полинома (width) -- просто число. Обычно 32, 16 или 8, но могут быть варианты.
- Сам полином (poly) -- все биты кроме старшего, то есть как раз тот вид, который нужен для алгоритма. Например 0x07 -- полином CRC-8, 0x04C11DB7 -- популярный полином для нескольких вариантов CRC-32.
- Начальное значение регистра (init) -- что лежит в регистре до начала работы алгоритма. И вот тут оказывается важно, базовый алгоритм использовать, или прямой. AFAIK, обычно подразумевается прямой.
- Отражен ли вход (refin) -- нужно ли зеркально отражать байты
- Отражен ли выход (refout) -- нужно ли в конце зеркально отражать полученный результат. Если оба эти параметры true, использование отраженного алгоритма позволяет добиться сразу и того и другого.
- Значение, с которым результат дополнительно xor-ится в самом конце (xorout).
- Пример вычисления на строке "123456789" (check)
Вот тут есть много примеров разных алгоритмов с возможностью посчитать https://crccalc.com/
Ещё больше примеров в вики, но там только параметры, посчитать не даёт.