Что такое код crc32


Что такое код crc32

Передаю файл с серверной части по кускам на PDA.
При передаче куска также передаю его контрольную сумму CRC32.
После передачи смотрю, что получил визуально.
Отправляемый и принимаемый куски совершенно одинаковые.
Но если я вычисляю контрольную сумму принятого куска на PDA, то она
не равна контрольной сумме, посчитаной для отправляемого куска на сервере.
Может быть дело в кодировке? Я использую Encoding.UTF8
Кодировка на PDA отличается от кодировки на нормальном компе.
Тогда вопрос, как же вачислять контрольные суммы там и сям, чтобы они были равны.

Алгоритм вычисления CRC32 следующий

public static uint CalculateCRC(System.IO.Stream stream)
<
stream.Position = 0;

const int buffer_size = 1024;
const uint POLYNOMIAL = 0xEDB88320;

uint result = 0xFFFFFFFF;
uint Crc32;

byte] buffer = new byte[buffer_size];
uint] table_CRC32 = new uint[256];

//
// Чтение из буфера
//
int count = stream.Read(buffer, 0, buffer_size);

//
// Вычисление CRC
//
while (count > 0)
<
for (int i = 0; i > 8)
^ table_CRC32[(buffer[i])
^ ((result) & 0x000000FF)];
>

Расчет коллизий при CRC32

Возник вопрос — если существует значение функции CRC32 , например — a50985e0 которое было получено из массива байт — Hello (т.е. из строки ТОЛЬКО символов.) то какова вероятность что точно такое же значение ( a50985e0 ) появится при обработке функцией массива байт полученных из 12345 т.е. из числа ?

Исходя из ответов уважаемых @Alex и @Harry делаю вывод что коллизий не избежать в принципе. И при постаточно большем диапазоне числового массива (от 0 до 1 000 000 000) всегда найдется хеш, который совпадет с хешем полученным из строки символов. В связи с этим переформулирую вопрос — существует ли закономерность (возможно ли ее вообще обнаружить) в колличестве этих самых коллизий ? Например хеш X из числа Y (например 12345) проверен в обшем массиве хешей (0 — 2 000 000 000) и найдено 10 коллизий, и так же для любого числа — врезультируещем массиве существует хотябы 10 коллизий. В то время как хеш из символьной строки Hello даст всего 1 коллизию и так же любая другая строка из символов даст не более 1 коллизии. Существует ли подобная законормерность ?

4 ответа 4

Вначале хочу заметить, если вы задаетесь таким вопросом, то скорее всего вы используйте функцию чек-суммы не по прямому назначению. А значит, вы делаете что-то неправильно.

Насколько я понял, вам интересно, одинаков ли шанс получить коллизию, если на входе строка из букв, или строка из цифр. Хочу заметить, что если у вас откуда-то приходят случайные строки длиной 5 символов (для примера), то шанс что у вас появятся одинаковые строки из цифр на много-много порядков выше, чем когда приходят строки из букв.

Что бы показать, что шансы получить коллизию одинаковы, я сгенерировал 100 млн чек-сумм для строк длиной 20 (я взял 20, что бы не создавались одинаковые строки из чисел), и посчитал коллизии внутри строк из чисел, внутри строк из букв, и взаимные коллизии между строками из чисел и букв. Вот мой код на C#:

Как видно, вероятность получить коллизию одинаковая.

В другом тесте я брал длину входных данных 10 байт, и вместо случайных чисел просто брал строковое представление числа i . Результат получился другой:

Как видно, коллизий на числах в 2 раза больше, хотя чек-сумма считалась на уникальных входных данных. Это происходит потому, что в случайной строке из букв длиной 10 байт больше энтропии, чем в строке чисел. CRC-32 не является полноценной криптографической хеш-фукнцией, и в ней нет лавинного эффекта. С хорошей хеш-функцией мы бы получили одинаковый результат.

Crc-32

11.02.2012, 22:06

Расчет CRC
С Наступающим форумчане. ) подскажите пожалуйста можно ли как-то расcчитать CRC для многобайтового.

CRC-16 для файла
Есть код для подсчета crc16 (Modbus) для бинарного файла, если файл превышает заданный размер.

Подсчет CRC заданной структуры
Добрый день, есть стандартная функция подсчета контрольной суммы (взято с вики): unsigned short.

Контрольная Сумма (CRC, MD5)
Здраствуйте дорогие программисты. Вот в чём проблема!! Есть такая програмка.

CRC-контрольная сумма отправляемого сообщения
Здравствуйте. У меня такая проблема: я не очень разбираюсь в программирование, а начальство дало.

12.02.2012, 11:52 2 12.02.2012, 21:35 [ТС] 3 12.02.2012, 21:35

CRC
Помогите, пожалуйста, с CRC. А то я уже для CRC16 давно сделал, а для CRC32 уже неделю бьюсь(((.


CRC 16
Собсна есть алгоритм на C,но проблема в том что C я не знаю :D может есть у кого на C# или скилл.

STM32F030 CRC
Добрый день! У меня не сходится аппаратный расчет CRC. Полином фиксированный 0x4C11DB7 Начальное.

Как просто посчитать контрольную сумму CRC (CRC32 — CRC16 — CRC8)

Для начала давайте немного разберёмся в теории. Итак, что же такое CRC? Если кратко, это одна из разновидностей подсчёта контрольной суммы. Контрольная сумма — это метод проверки целостности принятой информации на стороне приёмника при передаче по каналам связи. Например, одна из простейших проверок — использование бита чётности. Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной — то 1. При приёме также подсчитывается сумма битов сообщения, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче возникли ошибки, и передаваемая информация была искажена.

Но такой способ определения наличия ошибок — очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более «продвинутых» проверок, в том числе CRC.

По сути, CRC — это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее — остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют «контрольная сумма». В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.

Прежде чем приступать к вычислению CRC, понадобится ещё немного теории.
Что такое исходное сообщение должно быть понятно. Это непрерывная последовательность битов произвольной длины.

Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту — 8, 16 и 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.

Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x^8 + x^2 + x^1 + x^0. Здесь степень числа «x» означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число — это не что иное как (1)00000111 в двоичной системе счисления, или 7 в десятичной. В скобках я указал подразумеваемый старший разряд числа.
Вот ещё пример: x^16 + x^15 + x^2 + x^0 = (1)1000000000000101″ = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC.

Илон Маск рекомендует:  Ferror проверка признака ошибки в файле

Так как же считать контрольную сумму? Существует базовый метод — деление сообщения на полином «в лоб» — и его модификации в целях уменьшения количества вычислений и, соответственно, ускорения расчёта CRC. Мы рассмотрим именно базовый метод.

В общем виде, деление числа на многочлен выполняется по такому алгоритму:
1) создаётся массив (регистр), заполненный нулями, равный по длине разрядности полинома;
2) исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома;
3) в младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит;
4) если выдвинутый бит равен «1», то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме;
5) если в сообщении ещё есть биты, переходим к шагу 3);
6) когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.

Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x^8 + x^2 + x^1 + x^0.

Осталась ещё пара дополнительных штрихов. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.
Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число.

Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC могут делить на какое-то другое число.

И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом «вперёд», так и наоборот, младшим.

На основании всего вышеизложенного, давайте напишем функцию на языке Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.

Public Shared Function GetCrc(ByVal bytes As Byte(), ByVal poly As UInteger, Optional ByVal w >
Dim w >
‘Дополняем сообщение width нулями (расчёт в байтах):
ReDim Preserve bytes(bytes.Length — 1 + widthInBytes)

‘Создаём очередь битов из сообщения:
Dim msgFifo As New Queue(Of Boolean)(bytes.Count * 8 — 1)
For Each b As Byte In bytes
Dim ba As New BitArray()
If reverseBytes Then
For i As Integer = 0 To 7
msgFifo.Enqueue(ba(i))
Next
Else
For i As Integer = 7 To 0 Step -1
msgFifo.Enqueue(ba(i))
Next
End If
Next

‘Создаём очередь из битов начального заполнения регистра:
Dim initBytes As Byte() = BitConverter.GetBytes(initReg)
Dim initBytesReversed As IEnumerable(Of Byte) = (From b As Byte In initBytes Take widthInBytes).Reverse
Dim initFifo As New Queue(Of Boolean)(width — 1)
For Each b As Byte In initBytesReversed
Dim ba As New BitArray()
If Not reverseBytes Then
For i As Integer = 0 To 7
initFifo.Enqueue(ba(i))
Next
Else
For i As Integer = 7 To 0 Step -1
initFifo.Enqueue(ba(i))
Next
End If
Next

‘Сдвиг и XOR:
Dim register As UInteger = 0 ‘заполняем width-разрядный регистр нулями.
Do While msgFifo.Count > 0

Dim poppedBit As Integer = CInt(register >> (width — 1)) And 1 ‘определить перед сдвигом регистра.

Dim shiftedBit As Byte = Convert.ToByte(msgFifo.Dequeue)
If initFifo.Count > 0 Then
Dim b As Byte = Convert.ToByte(initFifo.Dequeue)
shiftedBit = shiftedBit Xor b
End If

register = register > (32 — width)) ‘маскируем младшие разряды.

CRC FAQ. Что, зачем и как

Глава 1. Что такое CRC и зачем он нужен

CRC (cyclic redundancy code) — циклический избыточный код, иногда называемый также контрольным кодом. По своей сути — это просто вычисленное на основе исходного передаваемого сообщения число (или можно сказать код), которое передаётся вместе с самим сообщением (дописывается в конец информационной части) и служит для контроля его безошибочной передачи.

Число это вычисляется по определённым правилам и всегда имеет строго определённое заранее количество разрядов. Очень удобно заранее знать, сколько разрядов занимает контрольное число, потому что иначе станет заранее неизвестной длина сообщения целиком, вместе с CRC, даже при условии, что мы точно знаем длину информационной части. Кроме того, это позволяет заранее выделить для вычисления CRC регистр нужного размера.

Никакой дополнительной информационной нагрузки это число не несёт, поэтому с точки зрения передачи полезной информации оно избыточно. Однако, как я уже сказал, его наличие позволяет диагностировать некоторое количество ошибок, если такие возникают при передаче.

Глава 2. Базовая теория, необходимая для вычисления CRC


По большому счёту, вся теория нахождения CRC базируется на двух вещах.

Первое. Любое сообщение можно представить в виде одного большого двоичного числа и считать что значения разрядов этого числа кодируют коэффициенты некоторого полинома.

Например, возьмём сообщение «15». В шестнадцатиричном виде оно кодируется так: 0x31,0x35. Если перевести эту запись в двоичную форму и записать всё в одну строку, то получим: 00110001 00110101. Если считать, что каждый разряд полученного числа — это коэффициент полинома, то этот полином будет иметь вид:
0*x 15 +0*x 14 +1*x 13 +1*x 12 +0*x 11 +0*x 10 +0*x 9 + 1*x 8 +0*x 7 +0*x 6 +1*x 5 +1*x 4 +0*x 3 +1*x 2 + 0*x 1 +1*x 0
Кратко его можно записать так: x 13 +x 12 +x 8 +x 5 +x 4 +x 2 +1

По большому счёту, мы можем оставить и двоичную запись (чаще всего так и делают, иксы писать неудобно), но будем помнить, что теперь это не просто число, а вектор, составленный из коэффициентов полинома (можно даже продолжать называть такие вектора полиномами). Причём нулевые коэффициенты при старших степенях можно опустить (в дальнейшем вы увидите, что нулевые коэффициенты при старших степенях ни на что не влияют) и написать его в виде 11000100110101.

Второе. Количество разрядов любого двоичного сообщения — это вполне конкретные, конечные числа. Соответственно, множества всех возможных N-разрядных сообщений (где N-любое целое положительное число), составленных по описанному выше способу, — это конечные множества. При использовании особой алгебры такие конечные множества можно считать конечными полями, являющимися расширением простого конечного поля GF(2). Соответственно, любые полиномы, коэффициенты которых составлены из значений разрядов двоичных чисел, можно рассматривать как многочлены над конечным полем.

Подробно многочлены над конечными полями изучаются в отдельном разделе математики, в который мы не будем сильно углубляться в рамках этой статьи. Если кто-то хочет узнать больше — вектор поисков для самостоятельного изучения, я считаю, вполне определён. Нам же интересно, что это за особая алгебра и как это связано с вычислением CRC.

Так вот, отличия этой алгебры от обычной заключаются в следующем:
— операции сложения и вычитания в ней тождественны и выполняются как сложение по модулю 2 (XOR),
— вместо понятий «меньше»/»больше» используются понятия «старше»/»младше». Старшим считается многочлен с большей степенью (наибольшая степень, у которой коэффициент при x равен единице). Например x 3 +1 старше, чем x 2 +x, потому что 3>2.

Нахождение CRC заключается в делении с остатком информационного полинома (тот который составлен из информационного сообщения) на некоторый специальный полином. Делим мы как обычно — столбиком, но вместо операции «вычитания» используем «сложение по модулю 2» и продолжаем деление до тех пор, пока оставшийся в делимом полином не окажется младше полинома делителя. Полученный остаток — это и есть CRC.

Илон Маск рекомендует:  TimePMString - Переменная Delphi

Для примера разделим рассмотренный выше полином, составленный из сообщения «15», на полином x 4 +x+1, для чего сначала запишем последний полином со всеми коэффициентами в явном виде (1*x 4 +0*x 3 +0*x 2 +1*x 1 +1*x 0 ), а потом запишем эти коэффициенты в виде вектора (10011). Деление будет выглядеть так, как на рисунке справа.

Нули в самом начале делимого, как я и обещал, нам не пригодились, точно также, как они не пригодились бы нам и при обычном делении.

Идём далее. Что это за специальный полином, на который мы делим наше представленное в виде полинома сообщение?

А это как раз один из основных параметров CRC-алгоритма, называемый также порождающим многочленом или порождающим полиномом. В качестве порождающего многочлена обычно берут какой-либо неприводимый многочлен.

Деление с остатком на полином степени N позволяет получить 2 N различных остатков от деления, причем все эти остатки можно описать N-1 разрядными векторами.

Описанные выше действия — это то, что мы по сути всегда делаем при нахождении CRC. Такое описание алгоритма удобно теоретикам и неудобно инженерам. Поэтому теперь перейдём к частностям, которые приближают нас к практической действительности.

Глава 3. Модификация алгоритма для практического применения.

Посмотрим ещё раз внимательно на наш пример деления столбиком и обратим внимание вот на что — при вычислениях мы фактически всегда оперируем только пятью битами, а могли бы оперировать и четырьмя, поскольку во всех операциях XOR у нас самый старший бит равен единице и он всегда сокращается. То есть, если считать, что вычисления происходят в каком-то выделенном четырёхбитном регистре, то всё деление будет выглядеть так, как будто мы просто на каждом шаге сдвигаем биты в регистре влево, загружая новое значение младшего бита, а старший бит просто выкидываем, если он равен нулю, или, если он равен единице, выполняем XOR регистра и младших четырёх битов порождающего полинома.

То есть теперь можно описать наш алгоритм так: побитно загружаем наше информационное сообщение в регистр нужного размера (на единицу меньше степени порождающего полинома), каждый раз сдвигая регистр влево и помещая новый бит в младший разряд. При этом, если вытесняемый из регистра старший бит равен единице, то выполняем XOR регистра со всеми битами порождающего полинома, кроме старшего. Значение регистра после обработки всего сообщения — это и есть CRC.

На картинке слева тот же самый пример, который мы рассматривали выше, но оформленный в соответствии с новым (инженерным) описанием алгоритма вычисления CRC (хотя по сути, это то же самое деление, что и выше).

Одно отличие в нашем инженерном алгоритме от рассматриваемого выше деления столбиком всё же есть. Отличие это заключается в начальном значении регистра. Мы инициализировали регистр нулями. В итоге наше сообщение стало несколько длиннее первоначального. Как мы знаем, нули в начале сообщения не влияют на результат вычислений, их там можно хоть сколько написать. Но ведь можно инициализировать регистр и не нулями.

Что изменится? Да особенно ничего, просто мы тогда будем искать CRC для несколько модифицированного исходного сообщения (с приписанными в начале битами). Если тот, кто будет определять правильность передачи сообщения, знает об этом и знает какое значение для инициализации регистра нужно выбирать, то он сможет правильно посчитать CRC. Надо сказать, что на практике чаще всего используется инициализация всего регистра нулями или инициализация всего регистра единицами.

Ещё одна особенность практической реализации основана на таком свойстве деления с остатком: если C — это остаток от деления A на B, то остаток от деления (A-C) на B будет равен нулю, а остаток от деления (A-C+D) на B будет равен D (если D 4 +x+1

  • в виде двоичного (шестнадцатиричного) числа (коэффициенты полинома): 10011 ( 0x0B )
  • в виде двоичного (шестнадцатиричного) числа без старшего бита (самый распространённый вариант): 0011 ( 0x03 )
  • в виде двоичного (шестнадцатиричного) числа без младшего бита 1001 ( 0x09 )
  • Параметры, определяющие формирование битовой последовательности должны описывать:

    • начальное значение регистра, в котором вычисляется CRC.
    • битовую последовательность, которая дописывается в конце сообщения.
    • порядок записи бит в байтах и байтов в словах исходного сообщения.


    Наличие последнего параметра связано с тем, что сообщения как правило передаются побайтно и при этом возможны два варианта передачи: старшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в нормальном порядке) или младшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в обратном порядке). Причём, иногда переворачивают не только биты в байтах, но и, например, байты в словах. Кстати говоря, во всех примерах, которые приводятся в этой статье, рассматривался только нормальный порядок бит (старшим битом вперёд).

    Кроме того, иногда полученный в результате деления остаток дополнительно инвертируют и в качестве CRC используют не сам остаток, а это инвертированное значение.

    Помимо описанного в этой статье прямого способа вычисления, существует, так называемый, табличный или быстрый способ расчёта CRC, но об этом как-нибудь в другой раз. А на сегодня, пожалуй, всё.

    Циклический избыточный код

    Алгоритм вычисления контрольной суммы (CRC, англ. cyclic redundancy check , проверка избыточности циклической суммы) — способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения её циклического избыточного кода.

    С точки зрения математики КС является типом хэш-функции, используемой для вычисления контрольного кода — небольшого количества бит внутри большого блока данных, например сетевого пакета или блока компьютерного файла, применяемого для обнаружения ошибок при передаче или хранении информации. Результат вычисления КС добавляется в конец блока данных непосредственно перед началом передачи или сохранения данных на каком-либо носителе информации. Впоследствии он проверяется для подтверждения её целостности. Популярность КС обусловлена тем, что подобная проверка просто реализуема в двоичном цифровом оборудовании, легко анализируется, и хорошо подходит для обнаружения общих ошибок, вызванных наличием шума в каналах передачи данных.

    Алгоритм CRC Править

    Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, т.е. хэш-функция является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.

    Каждому конечному двоичному набору данных $ a_0, a_1, \dots, a_N $ взаимооднозначно сопоставляется двоичный многочлен $ \sum_ <0\le n\le N>a_n x^n $ , последовательность коэффициентов которого представляет из себя исходную последовательность. Например, десятичное число 90 (1011010 в двоичной записи) соответствует многочлену:

    $ P(x) = 1\cdot x^6 + 0\cdot x^5 + 1\cdot x^4 + 1\cdot x^3 + 0\cdot x^2 + 1\cdot x^1 + 0\cdot x^0 = x^6 + x^4 + x^3 + x^1 $

    Подобным же образом в виде двоичного многочлена может быть представлен любой из блоков обрабатываемых данных, и любой двоичный многочлен обращается в набор битов. Нетрудно видеть, что количество различных многочленов степени меньше N равно $ 2^N $ , что совпадает с числом всех двоичных последовательностей длины N.

    При делении с остатком степень многочлена остатка строго меньше степени многочлена делителя, т.е. если в качестве делителя выбрать многочлен степени N, то различных остатков от деления он будет давать как раз $ 2^N. $

    При «правильном» выборе порождающего многочлена (делителя), остатки от деления на него будут обладать нужными свойствами хэширования — хорошей перемешиваемостью и быстрым алгоритмом вычисления. Второе обеспечивается тем, что степень порождающего многочлена обычно пропорциональна длине байта или машинного слова (например 8, 16 или 32).

    Илон Маск рекомендует:  Gnu general public license

    Таким образом, контрольная сумма CRC с порождающим многочленом степени N есть битовая последовательность длины N, представляющая многочлен, получившийся в остатке при делении исходного многочлена (представляющего входной поток бит) на порождающий многочлен:

    $ R(x) = P(x)\cdot x^r\, \bmod\, G(x) $

    $ R(x) $ — контрольный код многочлена $ P(x) $ . $ P(x) $ — исходный многочлен. $ G(x) $ — порождающий многочлен. $ r = \deg\,G(x) $ — степень порождающего многочлена.

    Умножение $ x^r $ осуществляется приписыванием $ r $ нулей к входной последовательности, что улучшает качество хэширования для коротких входных последовательностей.

    Ниже представлены реализации получения некоторых CRC для многочленов степени 8 (CRC-8), 16 (CRC-16) и 32 (CRC-32).

    Формализованный алгоритм расчёта CRC16 Править

    Для получения контрольной суммы, необходимо сгенерировать полином. Основное требование к полиному: его степень должна быть равна длине контрольной суммы в битах. При этом старший бит полинома обязательно должен быть равен “1”.

    Из файла берется первое слово. В зависимости от того, равен ли старший бит этого слова “1” или нет, выполняем (или нет) операцию XOR на полином. Полученный результат, вне зависимости от того, выполнялась ли операция XOR, сдвигаем на один бит влево (т.е. умножаем на 2). После сдвига (умножения) теряется старый старший бит, а младший бит освобождается (обнуляется). На место младшего бита загружается очередной бит из файла. Операция повторяется до тех пор, пока не загрузится последний бит файла.

    После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

    _mm_crc32_u8 дает отличный результат, чем код ссылки

    Я боролся с внутренними проблемами. В частности, я не получаю одинаковых результатов, используя стандартный CRC-расчет и предположительно эквивалентные интеллектуальные возможности. Я хотел бы перейти к использованию _mm_crc32_u16 и _mm_crc32_u32 но если я не могу заставить 8-битную операцию работать там, нет смысла.

    Эта таблица предназначена для другого полинома CRC, отличного от того, который используется инструкцией Intel. Таблица предназначена для Ethernet/ZIP/и т.д. CRC, часто называемый CRC-32. В инструкции Intel используется многочлен iSCSI (Castagnoli), для CRC, часто называемый CRC-32C.

    Этот короткий примерный код может вычислять либо путем раскодирования нужного многочлена:

    Вы можете использовать этот код для создания таблицы замены для своего кода, просто вычисляя CRC-32C каждого из однобайтных сообщений 0, 1, 2. 255.

    Кстати, я получил SW-код, который явно соответствует инструкции Intel crc32c, но использует другой многочлен: 0x82f63b78 Функция определенно не соответствует ни одному из тестовых примеров iSCSI здесь: https://tools.ietf.org/html/rfc3720#appendix-B.4

    Что расстраивает во всем этом, так это то, что каждая реализация, которую я пробовал для CRC-32C, отличается от других. Есть ли реальный код ссылки там?


    CRC32 Online

    Текст, контрольную сумму которого нужно посчитать

    Введите или скопируйте текст в соответствующее поле. Кодировка или раскодировка будет выполнена автоматически.

    CRC32:

    Dec (десятичная система исчисления):

    Hex (шестандцатиричная система исчисления):

    CRC32 — Алгоритм вычисления контрольной суммы — способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения её циклического избыточного кода.

    crc32 — Вычисляет полином CRC32 для строки

    (PHP 4 >= 4.0.1, PHP 5, PHP 7)

    crc32 — Вычисляет полином CRC32 для строки

    Описание

    Функция вычисляет циклический избыточный код 32-битных полиномов (CRC32) для строки str . Это обычно используется для контроля целостности передаваемых данных.

    В PHP целые числа имеют знак, поэтому многие контрольные суммы могут оказаться отрицательными на 32-битных платформах. На 64-битных платформах все результаты crc32() будут положительными целыми.

    Поэтому вам нужно использовать формат «%u» в функциях sprintf() или printf() для получения строкового представления суммы crc32() без знака.

    Для шестнадцатеричного представления суммы вы можете использовать или формат «%x» в функциях sprintf() и printf() , или же функцию конвертации dechex() . Оба этих способа также позаботятся о конвертации результата crc32() в беззнаковое целое.

    При использовании 64-битных платформ также возвращаются также рассматривалась возможность возвращать отрицательные целые для больших значений, но это ломало шестнадцатеричное представление, добавляя дополнительные 0xFFFFFFFF######## смещения для них. Так как шестнадцатеричное представление является самым востребованным, было решено не ломать его, даже если это ломает прямое сравнение десятеричных значений в 50% случаев при переходе с 32-битных на 64-битные платформы.

    Оглядываясь назад, возможно возвращать целое число было не самой лучшей идеей и лучше было возвращать сразу шестнадцатеричное представление (как например делает md5() ).

    Можно воспользоваться также более общим решением с использованием функции hash() . hash(«crc32b», $str) вернет ту же строку, что и dechex(crc32($str)) .

    Функция CRC-32 кадров Ethernet

    В качестве примера одного из возможных вариантов классического кода CRC рассмотрим код CRC-32 стандарта IEEE 802.3. Этот код лежит в основе функции CRC кадра MAC Ethernet (Media Access Control Ethernet).

    В данном случае порождающий многочлен кода примитивен [1] :

    В качестве информационной последовательности / кода CRC-32 кадра MAC Ethernet выступает последовательность полей МАС-адреса приемника (Destination Address, DA), МАС-адреса источника кадра (Source Address, SA), длины/типа кадра (Length/Type), а также нагрузки (данных) кадра (DATA). Преамбула (Preamble) и индикатор начала кадра — Start Frame Delimiter (SFD) в информационную последовательность CRC-32 не входят (рисунок 4.7 а)).

    Нумерация битов кадра в данном случае соответствует принятой в ITU-T (см. параграф 2.6).

    При использовании виртуальных локальных сетей (Virtual Local Area Network, VLAN) к указанным полям добавляется префикс стандарта IEEE 802.1 Q длиной 4 байта (рисунок 4.7 б)). Длина остальных полей кадра остается неизменной.

    Информационная последовательность кода выделена на рисунке 4.7 серым цветом.

    Общая длина информационной последовательности кода CRC в этом случае может меняться за счет изменения длины нагрузки от 56 до 1514 байт или от 60 до 1518 байт (при наличии префикса 802.1Q). Таким образом, длина i информационной последовательности имеет переменный размер и может принимать значения из указанных диапазонов в зависимости от размера нагрузки, а также наличия или отсутствия префикса 802.1 Q.

    Старшему значащему биту информационной последовательности соответствует первый бит поля DA, а младшему — последний бит поля данных. Многочлен проверочной последовательности, в соответствии с правилами систематического кодирования, будет иметь вид:

    Биты проверочной последовательности (коэффициенты проверочного многочлена) передаются в поле Frame Check Sequence (FCS) проверочной последовательности кадра MAC Ethernet (рисунок 4.7). При этом коэффициент при степени 31 многочлена t соответствует первому биту поля FCS, а при степени 0 — последнему.

    Код CRC-32 стандарта IEEE 802.3 отвечает условию (4.2). При этом максимальная длина информационной последовательности кодового слова 12144 бит (1518 байт), что существенно меньше значения 2 32 — 32 — 1 = 4294967263, определяемого условием (4.4). Порождающий многочлен в данном случае не содержит множитель х + 1 (см. подпараграф 4.1.1). Таким образом, рассматриваемый код CRC-32 соответствует одной из рассмотренных ранее вариаций классических кодов CRC (см. подпараграф 4.3.3), причем укороченной (см. подпараграф 2.2.5).

    В этом случае последовательность кадра также соответствует кодовому слову кода CRC при систематическом кодировании, так как поле FCS следует сразу за полем информационной последовательности. Таким образом, процесс декодирования кодового слова сводится к определению остатка от деления всей последовательности кадра, за исключением полей Preamble и SFD, на порождающий многочлен кода. Ненулевой остаток отделения свидетельствует об ошибках в принятом кадре. Кадр с обнаруженными ошибками не обрабатывается приемником (сбрасывается).

    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL