Вычисление контрольных сумм

Что такое контрольная сумма (CRC) и для чего она нужна, я думаю знают многие. Ну а если кто не знает, то напомню, что контрольная сумма это некоторое число которое получается в результате обработки по определённому алгоритму некоторого объёма данных. Главное свойство контрольной суммы заключается в том, что она будет разной для двух массивов данных если они различаются хотя бы на один бит. Применяются контрольные суммы зачастую при передаче данных, для проверки целостности информации. Для расчета контрольных сумм применяются самые разнообразные алгоритмы, количество матана в которых превышает все разумные пределы. Именно поэтому применять мы их не будем, а пойдем другим путём. В контроллерах STM32 есть много полезной периферии, но ничего особо нового и необычного (например по сравнению с AVR) я не увидел. Лишь только одна штука меня немного приятно удивила и порадовала — аппаратная считалка контрольной суммы, и ей то мы сейчас и займемся.

Аппаратная это значит, что нам не нужно знать как оно там считается и тратить на это процессорное время. Мы просто записываем последовательно весь массив данных (контрольную сумму которого нам нужно посчитать) в определенный регистр, а потом из него же считываем результат, т.е.  работа с входными и выходными данными организована через один регистр (как в  UARTe).  Называется этот регистр CRC_DR, он 32-х битный. Более он ни чем не примечателен. Кроме него существует еще один регистр под названием CRC_IDR. Он восьмибитный, может хранить в себе любые данные, которые ни как не влияют на рассчет контрольной суммы. Его предназначение так и осталось для меня загадкой. И наконец третий регистр CRC_CR. Он существует ради одного бита который называется RESET. Установка этого бита в единицу сбрасывает считалку в исходное состояние. Нужно всегда устанавливать этот бит перед новым подсчётом CRC, ведь как я писал выше, для подсчёта контрольной суммы нужно последовательно писать в регистр CRC_DR данные. Именно поэтому есть вероятность что контрольная сумма посчитается не правильно, так как при подачи новой порции данных считалка не поймет что ей предлагают посчитать CRC для нового массива данных, а не продолжить расчет для предыдущего с добавлением новых данных. Ну да ладно, пора уже посчитать в качестве эксперимента контрольную сумму для каких-нибудь произвольных данных. 

В результате после выполнения этого кода, в переменной data_crc значение стало 0x4b6b373e. Контрольная сумма посчиталась. При изменение любого байта контрольная сумма меняется тоже. На основании этого я сделал вывод что все работает как надо. Чисто с практической точки зрения применения этой штуковине я пока не нашел, но возможно оно понадобится мне в будущем.

Скачать HashTab!

HashTab представляет из себя расширение проводника Windows и плагин для Mac Finder для проверки целостности и подлинности файлов посредством вычисления контрольной суммы. HashTab поддерживает множество алгоритмов хеширования, таких как CRC, MD5, SHA1, SHA2, SHA3/Keccak, RipeMD и Whirlpool, а так же BitTorrent Info Hash и генерацию Magnet-ссылок.

После установки HashTab, кликните правой кнопкой мыши по любому файлу. В Windows, выберите «Свойства», и вы увидите новую вкладку «Хеш-суммы файлов». В Mac, выберите «File Hashes». В Mac OS X 10.8 меню «File Hashes» расположено в подменю «More». Окно «Хеш-суммы файлов» отображает все хеши для выбранного файла. Вы можете настроить, какие хеши будут вычисляться и выводиться на экран. Вы можете хешировать другие файлы для сравнения.

Контрольная сумма файла. Что это?

Вы также можете вставить текст хеша, таким образом вам не придётся глазами сравнивать MD5 хеши, индикатор HashTab покажет, есть ли совпадения.

On-line CRC calculation and free library

Loading…

Introduction on CRC calculations

Whenever digital data is stored or interfaced, data corruption might occur. Since the beginning of computer science, people have been thinking of ways to deal with this type of problem. For serial data they came up with the solution to attach a parity bit to each sent byte. This simple detection mechanism works if an odd number of bits in a byte changes, but an even number of false bits in one byte will not be detected by the parity check. To overcome this problem people have searched for mathematical sound mechanisms to detect multiple false bits. The CRC calculation or cyclic redundancy check was the result of this. Nowadays CRC calculations are used in all types of communications. All packets sent over a network connection are checked with a CRC. Also each data block on your harddisk has a CRC value attached to it. Modern computer world cannot do without these CRC calculation. So let’s see why they are so widely used. The answer is simple, they are powerful, detect many types of errors and are extremly fast to calculate especially when dedicated hardware chips are used.

One might think, that using a checksum can replace proper CRC calculations. It is certainly easier to calculate a checksum, but checksums do not find all errors. Lets take an example string and calculate a one byte checksum. The example string is «Lammert» which converts to the ASCII values [ 76, 97, 109, 109, 101, 114, 116 ]. The one byte checksum of this array can be calculated by adding all values, than dividing it by 256 and keeping the remainder. The resulting checksum is 210. You can use the calculator above to check this result.

In this example we have used a one byte long checksum which gives us 256 different values. Using a two byte checksum will result in 65,536 possible different checksum values and when a four byte value is used there are more than four billion possible values. We might conclude that with a four byte checksum the chance that we accidentily do not detect an error is less than 1 to 4 billion. Seems rather good, but this is only theory. In practice, bits do not change purely random during communications. They often fail in bursts, or due to electrical spikes. Let us assume that in our example array the lowest significant bit of the character ‘L‘ is set, and the lowest significant bit of charcter ‘a‘ is lost during communication. The receiver will than see the array [ 77, 96, 109, 109, 101, 114, 116 ] representing the string «M`mmert«. The checksum for this new string is still 210, but the result is obviously wrong, only after two bits changed. Even if we had used a four byte long checksum we would not have detected this transmission error. So calculating a checksum may be a simple method for detecting errors, but doesn’t give much more protection than the parity bit, independent of the length of the checksum.

The idea behind a check value calculation is simple. Use a function F(bval,cval) that inputs one data byte and a check value and outputs a recalculated check value. In fact checksum calculations as described above can be defined in this way. Our one byte checksum example could have been calculated with the following function (in C language) that we call repeatedly for each byte in the input string.

The initial value for cval is 0.

int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256; }

The idea behind CRC calculation is to look at the data as one large binary number. This number is divided by a certain value and the remainder of the calculation is called the CRC. Dividing in the CRC calculation at first looks to cost a lot of computing power, but it can be performed very quickly if we use a method similar to the one learned at school. We will as an example calculate the remainder for the character ‘m‘—which is 1101101 in binary notation—by dividing it by 19 or 10011. Please note that 19 is an odd number. This is necessary as we will see further on. Please refer to your schoolbooks as the binary calculation method here is not very different from the decimal method you learned when you were young. It might only look a little bit strange. Also notations differ between countries, but the method is similar.

1 0 1 = 5 ————- 1 0 0 1 1 / 1 1 0 1 1 0 1 1 0 0 1 1 | | ——— | | 1 0 0 0 0 | 0 0 0 0 0 | ——— | 1 0 0 0 0 1 1 0 0 1 1 ——— 1 1 1 0 = 14 = remainder

With decimal calculations you can quickly check that 109 divided by 19 gives a quotient of 5 with 14 as the remainder. But what we also see in the scheme is that every bit extra to check only costs one binary comparison and in 50% of the cases one binary substraction. You can easily increase the number of bits of the test data string—for example to 56 bits if we use our example value «Lammert«—and the result can be calculated with 56 binary comparisons and an average of 28 binary substractions. This can be implemented in hardware directly with only very few transistors involved. Also software algorithms can be very efficient.

For CRC calculations, no normal substraction is used, but all calculations are done modulo 2. In that situation you ignore carry bits and in effect the substraction will be equal to an exclusive or operation. This looks strange, the resulting remainder has a different value, but from an algebraic point of view the functionality is equal. A discussion of this would need university level knowledge of algebraic field theory and I guess most of the readers are not interested in this. Please look at the end of this document for books that discuss this in detail.

Now we have a CRC calculation method which is implementable in both hardware and software and also has a more random feeling than calculating an ordinary checksum. But how will it perform in practice when one ore more bits are wrong? If we choose the divisor—19 in our example—to be an odd number, you don’t need high level mathematics to see that every single bit error will be detected. This is because every single bit error will let the dividend change with a power of 2. If for example bit n changes from 0 to 1, the value of the dividend will increase with 2ⁿ. If on the other hand bit n changes from 1 to 0, the value of the dividend will decrease with 2ⁿ. Because you can’t divide any power of two by an odd number, the remainder of the CRC calculation will change and the error will not go unnoticed.

The second situation we want to detect is when two single bits change in the data. This requires some mathematics which can be read in Tanenbaum’s book mentioned below. You need to select your divisor very carefully to be sure that independent of the distance between the two wrong bits you will always detect them. It is known, that the commonly used values 0x8005 and 0x1021 of the CRC16 and CRC-CCITT calculations perform very good at this issue. Please note that other values might or might not, and you cannot easily calculate which divisor value is appropriate for detecting two bit errors and which isn’t. Rely on extensive mathematical research on this issue done some decades ago by highly skilled mathematicians and use the values these people obtained.

Furthermore, with our CRC calculation we want to detect all errors where an odd number of bit changes. This can be achieved by using a divisor with an even number of bits set. Using modulo 2 mathematics you can show that all errors with an odd number of bits are detected. As I have said before, in modulo 2 mathematics the substraction function is replaced by the exclusive or. There are four possible XOR operations.

0 XOR 0 => 0 even => even 0 XOR 1 => 1 odd => odd 1 XOR 0 => 1 odd => odd 1 XOR 1 => 0 even => even

We see that for all combinations of bit values, the oddness of the expression remains the same. When chosing a divisor with an even number of bits set, the oddness of the remainder is equal to the oddness of the divident. Therefore, if the oddness of the dividend changes because an odd number of bits changes, the remainder will also change. So all errors which change an odd number of bits will be detected by a CRC calculation which is performed with such a divisor. You might have seen that the commonly used divisor values 0x8005 and 0x1021 actually have an odd number of bits, and not even as stated here. This is because inside the algorithm there is a «hidden» extra bit 2¹⁶ which makes the actual used divisor value 0x18005 and 0x11021 inside the algorithm.

Last but not least we want to detect all burst errors with our CRC calculation with a maximum length to be detected, and all longer burst errors to be detected with a high probability. A burst error is quite common in communications. It is the type of error that occurs because of lightning, relay switching, etc. where during a small period all bits are set to one. To really understand this you also need to have some knowledge of modulo 2 algebra, so please accept that with a 16 bit divisor you will be able to detect all bursts with a maximum length of 16 bits, and all longer bursts with at least 99.997% certainty.

In a pure mathematical approach, CRC calculation is written down as polynomial calculations. The divisor value is most often not described as a binary number, but a polynomial of certain order. In normal life some polynomials are used more often than others. The three used in the on-line CRC calculation on this page are the 16 bit wide CRC16 and CRCCCITT and the 32 bits wide CRC32. The latter is probably most used now, because amongst others it is the CRC generator for all network traffic verification and validation.

For all three types of CRC calculations I have a free software library available. The test program can be used directly to test files or strings. You can also look at the source codes and integrate these CRC routines in your own program. Please be aware of the initialisation values of the CRC calculation and possible necessary postprocessing like flipping bits. If you don’t do this you might get different results than other CRC implementations. All this pre and post processing is done in the example program so it should be not to difficult to make your own implementation working. A common used test is to calculate the CRC value for the ASCII string «123456789». If the outcome of your routine matches the outcome of the test program or the outcome on this website, your implementation is working and compatible with most other implementations.

Just as a reference the polynomial functions for the most common CRC calculations.

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

Please remember that the highest order term of the polynomal (x¹⁶ or x³²) is not present in the binary number representation, but implied by the algorithm itself.

Скачать «CRC16 — Описание алгоритма и пример расчёта на языке Си» в формате PDF

Статья © PIClist-RUS (piclist.ru)

CRC (Cyclic Redundancy Code — циклический избыточный код) — алгоритм расчёта контрольной суммы для передаваемого сообщения, основанный на полиномиальной арифметике.

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

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

Кроме того, нужно отметить, что в CRC алгоритме используется полиномиальная арифметика по модулю 2. Это означает, что действия, выполняемые во время вычисления CRC, являются арифметическими операциями без учёта переноса. То есть сложение и вычитание выполняются побитово без учёта переноса, благодаря чему эти две операции дают эквивалентный результат. Операции сложения и вычитания в этом случае идентичны операции XOR (исключающее ИЛИ).

Деление выполняется по аналогии с обычным арифметическим делением столбиком с тем отличием, что вместо вычитания делителя из делимого используется операция XOR. В программной реализации этого алгоритма вместо делителя сдвигается делимое. Сдвиг осуществляется влево по одному биту. При этом выполняется проверка выдвигаемого бита: если он равен единице, выполняется операция XOR делителя (полинома) со старшими разрядами делимого (сообщения).

Чтобы выполнить вычисление CRC, необходимо выбрать делитель — полином. Важной характеристикой, определяющей дальнейшие расчёты, является степень полинома или его ширина W (от английского Width — ширина). Обычно выбирается степень 16 или 32, так как они являются кратными разрядности регистров современных процессоров, что значительно упрощает реализацию алгоритмов CRC.

Степень полинома — действительная позиция старшего бита. Позиции битов отсчитываются, начиная с нулевой.

Выбрав полином, нужно в конец сообщения добавить W нулевых битов.

В данной статье для расчета CRC будет достаточно использовать полином степени W = 16, который обеспечивает вероятность не обнаружения ошибки 1/2¹⁶~=15.3·10^-6. При том, что ошибки возникают тоже с достаточно малой вероятностью, доля искажённых данных среди всех принятых на хранение компьютером, будет очень мала и не окажет значительного влияния на дальнейшую работу с сохранёнными в компьютере данными.

Существует набор стандартных полиномов степени W = 16. В данном проекте будем использовать стандартный полином CRC-16, имеющий значение «8005» в шестнадцатеричном представлении или 1 1000 0000 0000 0101 в двоичном представлении (как правило, самая старшая единица не учитывается при расчётах).

При расчётах CRC используется абстрактный регистр CRC с разрядностью, равной степени полинома W, который хранит текущее значение вычисляемой контрольной суммы. Кроме степени полинома нужно выбрать начальное значение регистра CRC и значение, которое комбинируется по XOR с окончательным содержимым регистра. Лучшим выбором для инициализации регистра является значение FFFFh (или 1111 1111 1111 1111 в двоичном формате), которое обеспечить возможность обнаружить нулевые байты. Соответственно, окончательное значение регистра будет комбинироваться по XOR также с FFFFh.

Простой алгоритм расчёта CRC выполняется следующим образом:

1. В регистр CRC заносится начальное значение FFFFh.

2. В конец сообщения добавляется W нулевых битов

3. Содержимое регистра сдвигается влево на 1 бит, и в последнюю (нулевую) позицию заносится очередной, ещё не обработанный бит данных.

4. Если из регистра был выдвинут бит со значением «1», то содержимое регистра комбинируется по XOR с полиномом. Если значение бита равно «0», XOR не выполняется.

5. Шаги 3 и 4 выполняются, пока не будут обработаны все данные.

HashTab — определяем контрольные суммы файла

6. Окончательное содержимое регистра комбинируется по XOR со значением FFFFh.

Примечание: в программной реализации сначала выполняется проверка старшего бита, и только потом — сдвиг содержимого регистра.

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

Всего значений в таблице 256. Поэтому при ее расчёте выполняется цикл по 256 значениям (от 0 до 255):

1.Очередной индекс помещается в регистр. Так как индекс представляет собой один байт, а величина полинома и регистра — два байта, индекс помещается в старший байт регистра, а младший байт заполнен нулями.

2. Содержимое регистра восемь раз сдвигается влево по одному биту. Каждый раз проверяется выдвинутый бит. Если из регистра был выдвинут бит со значением «1», то содержимое регистра комбинируется по XOR с полиномом. Если значение бита равно «0», XOR не выполняется.

3. Полученная двухбайтовая величина заносится в таблицу по индексу.

После того как таблица рассчитана, можно использовать табличный алгоритм CRC:

1. Сдвиг регистра на 1 байт влево с чтением нового байта сообщения.

2. XOR старшего байта, только что выдвинутого из регистра с новым байтом сообщения, что даёт индекс в таблице [0..255].

3. XOR табличного значения с содержимым регистра.

4. Если ещё есть байты данных, перейти к шагу 1.

В данной статье используется описанный выше табличный алгоритм.

Код для расчёта таблицы:

Код для расчёта CRC:

© PIClist-RUS (piclist.ru), 2007 г.