checksums что это в играх
Checksum
Checksum — небольшое Qt графическое приложение для вычисления (хеширования / hashing) и проверки контрольной суммы файлов (checksums).
Хеширование (hashing) — преобразование входного массива данных произвольной длинны, в выходную битовую строку фиксированной длинны. Такие преобразования так же называют хеш-функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения.
Контрольная сумма — рассчитанное путём применения заданным алгоритмом значение, используемое для проверки целостности данных при их передаче и хранении. Так же может быть использована для сравнения двух наборов данных на неэквивалентность (с большой вероятностью различные наборы данных будут иметь неравные контрольные суммы).
Checksum прост в использовании, имеет удобный и интуитивно понятный пользовательский интерфейс, позволяет с высокой скоростью хешировать файлы, получать и проверять контрольные суммы.
Checksum поддерживает как одиночное, так и «массовое» хеширование (всех файлов из заданного каталога, включая подкаталоги, опционально) используя алгоритмы MD5 (128-битный алгоритм хеширования), MD4 (предшественник MD5) и SHA1 (алгоритм генерирует 160-битное хеш-значение).
Checksum вычисляет контрольные суммы в фоновом режиме (для одного или для всех добавленных файлов), поддерживает функцию «Перетащи и брось» (drap-and-drop) из файлового менеджера на окно приложения, интегрируется с буфером обмена (контрольная сумма автоматически вставляется в диалог сравнения), управление приложением с помощью мыши и/или клавиатурными сочетаниями.
Контрольная сумма файла или Checksum.
В статье описывается понятие что такое контрольная сумма файла, приёмы, с помощью которых она рассчитывается и зачем вообще она нам, пользователям, нужна? Вот лишь главные пункты, где без сверки контрольной суммы файла не обойтись.
Итак, вы качаете файл большого размера? Фильм это или игра — не суть: вы должны быть уверены, что игра установится без ошибок, а видео будет проигрываться гладко.
Вы купили SD-диск или флешку на АлиЭкспресс? Вам нужно удостовериться, не побита ли она и соответствует ли реальный объём указанному продавцом… Вот самый быстрый и простой способ подделать объём флешки.
Вы скачали файл, но есть сомнения в его подлинности? Перед установкой можно проверить, не «добавил» ли к его содержимому некий злоумышленник что-то зловредное, которое после инсталляции или даже простого открытия файла начнёт работать против вас…
Что такое контрольная сумма?
Название появилось от summation check (саммэйшен чек) — число, вычисляемое по особым правилам по содержимому блока данных с целью проверки получателем целостности данных при хранении или передаче. Если контрольная сумма, вычисленная получающим устройством, не совпадает с принятой суммой, то вывод один — целостность данных нарушена. Причиной тому может быть «кривое» интернет-соединение, подделка на этапе составления/копирования файла на стороне сервера, или неисправность принимающего устройства (а иногда и просто подлог со стороны его продавца).
Откуда её взять-то?
Составьте сами (если файл создаётся вами или готовится к пересылке/копированию) и сверьте с имеющимся/поставляемым. Если не стесняетесь, а для вас обладание файлом/программой очень важно, запросите контрольную сумму у поставщика. Для этого у нас есть все возможности: у самой Windows или несколько очень хороших, бесплатных и легковесных программ. О всех способах по порядку.
Что может Windows?
Уже в версии Windows 7 есть замечательная утилита certutil.exe, и с её помощью мы научимся вычислять и сверять контрольную сумму. В примере будет использоваться самый ходовой на данный момент алгоритм MD5 — именно он подходит для описанных в начале статьи задач (с командами, нижеописываемыми, прокатят также SHA256 и другие). Согласно Microsoft, утилита certutil.exe призвана снимать и выводить на экран информацию о конфигурации CA (авторизованной сертификации), работать со службами сертификатов, резервировать и восстанавливать компоненты CA, а также сверять сами сертификаты, парные ключи и цепочки хранящихся сертификатов. А мы сейчас с вами вычислим контрольную сумму любого файла.
К слову сказать, с появлением более современных версий Windows и обновлённых версий PowerShell возможности для вычисления и сверки контрольных сумм многократно усилились. Так, для работы можно попробовать апплет в виде:
Но подробности я пока опущу и остановлюсь на вседоступных вариантах расчётов.
К примеру, мне нужна контрольная сумма файла pdf:
Команда примет вид:
Если вы желаете у видеть чек-сумму в текстовом файле, можно просто воспользоваться заданием к cmd на вывод результатов команды в указанный файл:
Ищите файл с именем checksum.txt корне диска С:.
Если вам нужна исключительно контрольная сумма, можно воспользоваться дополнительными флагами к команде:
Контрольная сумма файла есть — сверяем
Если вы пытаетесь проверить контрольную сумму, её можно узнать у «поставщика» файла. Обнаружить их нетрудно, ибо добросовестный хозяин особо на это укажет на сайте или вложит файл с информацией для сверки в архив.
Что такое контрольная сумма (Checksum) и что с ней делать?
Вы собираетесь нажать кнопку загрузки и замечаете рядом с ней странный код. Кажется, не имеет никакого отношения к тому, насколько велик файл или на что вы должны обратить внимание. Так что вперед, получите файл и беда! Это не похоже на то, что вы ожидали.
Если бы только был быстрый способ узнать, совпадает ли только что загруженный вами элемент с файлом, который был на веб-сайте. Что ж, есть. Добро пожаловать в мир контрольных сумм!
Что за контрольная сумма (Checksum)?
Rонтрольная сумма (Checksum) — это число в форме двоичного или шестнадцатеричного значения, полученное из источника данных. Важные моменты, которые следует знать: контрольная сумма обычно намного меньше, чем источник данных, а также почти полностью уникальна. Это означает, что вероятность того, что некоторые другие данные дадут точно такую же контрольную сумму, крайне маловероятна.
Давайте рассмотрим несколько примеров, первый из которых — это простой текстовый файл (ниже), содержащий важную информацию! Все файлы содержат данные, которые охватывают не только, скажем, текст, который мы видим — будут выделены биты, чтобы сообщить нам, какой это тип файла, как данные расположены и так далее…
Все это обрабатывается в процессе создания контрольной суммы, и мы покажем вам, как это работает и как вы можете сделать это самостоятельно, позже в этой статье.
Но пока давайте посмотрим на значение, которое мы получаем:
Сам по себе этот код нам ничего не говорит. Мы не можем полностью «взломать» его, чтобы выяснить, из какого набора нулей и единиц состоит текстовый файл. Однако предполагается, что он специфичен для этого конкретного файла, поэтому теперь давайте изменим исходный текстовый файл, переставив некоторые слова.
Изображение выше ясно показывает, что это все тот же текст и, следовательно, те же данные технически, но последовательность битов теперь другая. Контрольная сумма на этот раз такова:
Обратите внимание, что это одинаковая длина — это ключевой аспект процесса получения кода, но это совершенно другая контрольная сумма. Те же данные, другой порядок, совершенно новая контрольная сумма.
Но, возможно, этого следовало ожидать; в конце концов, изменения в файле были не совсем тривиальными. Итак, давайте посмотрим, что произойдет, когда мы изменим только одну букву во всем: посмотрим, сможете ли вы определить, какую из них!
Наблюдайте за барабанной дробью на заднем плане, пока мы смотрим на контрольную сумму этого почти не измененного файла.
Это изменение всего одной буквы снова дало нам еще один уникальный код. Когда дело доходит до контрольных сумм, в этом вся суть системы: любые изменения в исходном источнике данных, какими бы маленькими они ни были, должны приводить к полностью новой контрольной сумме, что позволяет очень легко увидеть, было ли что-то изменено.
Разобравшись с этим, давайте посмотрим, как все это работает!
Технология
В основе контрольной суммы лежит программный алгоритм, который используется для создания кодов, которые мы видели. В случае наших примеров мы использовали очень распространенный алгоритм, известный как SHA-256 ( алгоритм безопасного хеширования — 256 бит ). Этот алгоритм представляет собой тип криптографической хэш — функции (CHF), с исходными данными, меченных в качестве сообщения, а выход которого называют значение хеш — функции или просто хэш (контрольная сумма, в данном случае).
SHA-256, разработанный АНБ и выпущенный почти 20 лет назад, относится к классу CHF, широко используемых во всем мире. Их популярность сводится к тому, что они работают быстро и устойчивы к попыткам «взломать» код, хотя в наши дни доступны гораздо лучшие варианты.
У каждого алгоритма свой способ работы, но мы сосредоточимся только на том, что делает SHA-256. Процесс всегда дает хэш фиксированной длины (в данном случае 256 бит), независимо от размера сообщения, хотя технически это фактически 8 значений, каждое размером 32 бита.
Таким образом, контрольная сумма для нашего файла test1 на самом деле 798B3808 4999FA50 E7D1861E 07E45F4E 3AA39668 DC6A12A8 4A058CAA A32DE0EB. Это было записано в шестнадцатеричном формате — записать его как строку из 256 единиц и нулей было бы очень утомительно!
Первым шагом в последовательности алгоритма является обработка сообщения, так что это набор блоков, каждый размером 512 бит. Для файлов, которые не являются целым числом, кратные 512, или если файл меньше этого размера, трюк называется обивка используется. Здесь после завершения битов сообщения добавляется целый стек нулей, чтобы сделать его раунд 512.
Например, предположим, что мы пытаемся найти контрольную сумму файла, общий размер которого составляет 10145 бит. Это будет разделено на 19 целых блоков, оставив 417 бит для заполнения. Чтобы указать, где заканчиваются данные и начинается заполнение, к концу строки битов, составляющей источник, добавляется 1. Итак, здесь заполнение добавит 352 нуля.
Погодите, а почему это не 416? Самая последняя часть последнего блока — это особое 64-битное число: длина исходного файла. Это означает, что в нашем примере 20-й блок должен заканчиваться двоичным значением 10145, в результате чего сообщение требует для заполнения только 402 бита пустого пространства.
Как только это будет сделано, алгоритм берет самый первый 512-битный блок и разбивает его на 16 частей, каждая из которых имеет длину 32 бита; каждое из этих значений будет использоваться в процессе вычисления хэша.
До этого момента это самая простая часть: остальная часть процесса включает в себя много математики.
Производители микросхем, такие как Intel, предлагают архитектурные решения для устройств FPGA для расчета хэш-значений SHA-256.
Все это выходит далеко за рамки этой статьи, но если вам интересно вникнуть в это более подробно, вы можете прочитать об этом здесь. Но чтобы дать вам краткий обзор, сначала нужно создать начальный хеш с использованием первых 8 простых чисел. Они проходят через уравнение, чтобы получить значение длиной 256 бит, которое затем изменяется снова и снова, поскольку остальная часть алгоритма проходит через все части в каждом блоке из обработанных исходных данных.
Звучит ужасно сложно, да? Однако для современного процессора это совсем несложно.
Для генерации хэша требуется не более дюжины или около того циклов процессора для каждого байта исходных данных.
Так что же делать с контрольной суммой (Checksum)?
Контрольная сумма позволяет легко проверить целостность данных, составляющих файл.
Представьте себе такой сценарий: вам нужно загрузить важный файл, который имеет решающее значение для работы компьютера. Действительно критично, настолько, что вы не хотите, чтобы в нем были какие-либо ошибки или сбои. У вас также медленное и нестабильное интернет-соединение, и вы беспокоитесь, что это может повлиять на скачивание файла.
Хост файла знает все это, поэтому он запускает алгоритм контрольной суммы для файла и помещает ответ на веб-страницу загрузки. Получив его, вы можете запустить тот же процесс и сравнить значения — если они совпадают, вы будете знать, что с файлом, который вы скачали, все в порядке.
И это основное использование контрольной суммы: проверка целостности данных, составляющих файл. Это можно сделать вручную, как мы вскоре увидим, или это может быть часть автоматизированной операции. Valve использует контрольные суммы на платформе Steam как часть процесса проверки файлов.
Выполните свою контрольную сумму
Все основные операционные системы также имеют встроенный инструмент контрольной суммы.
Windows
Чтобы запустить контрольную сумму в Windows, проще всего использовать PowerShell: щелкните правой кнопкой мыши кнопку меню «Пуск» или нажмите Win + X. Если вы используете более старую версию Windows, вы можете скачать PowerShell отсюда.
Введите команду get-filehash, а затем укажите местоположение файла. Либо введите команду, а затем перетащите файл в окно PowerShell. Вот как был создан наш первый тестовый файл.
Для контрольных сумм использование другой хеш-функции не приносит каких-либо значительных преимуществ, хотя было показано, что некоторые из более старых (например, MD5, SHA-1) создают одинаковый хеш для разных файлов — проблема, известная как коллизия.. Новые алгоритмы более устойчивы к конфликтам, поэтому PowerShell по умолчанию использует SHA-256.
Основная причина необходимости переключения на другую функцию заключается в том, что хост файла решил использовать что-то другое, кроме SHA-256, поэтому вам нужно переключиться на это, чтобы сравнить файлы.
Сравнивать две длинные строки цифр и букв может быть немного сложно, но с небольшим программированием вы можете заставить PowerShell вычислять контрольные суммы за вас. Давайте возьмем приведенный выше код MD5 в качестве примера и представим, что хеш исходного файла на самом деле заканчивается цифрой 8.
На изображении ниже показаны строки кода, которые необходимо ввести, используя Shift + Enter после каждой.
Видите, как написано «Ложь»? Это говорит вам, что файл не тот. Если вы уверены, что у вас есть правильный хеш для нужного файла, то все подозрения ложатся на данные.
Обратите внимание, что контрольная сумма не может сказать вам, как файлы различны — это очень двоичный тест, если вы простите за каламбур. Но это полезный инструмент, и в нем есть некоторые очень специфические функции контрольной суммы (например, контрольная цифра и контрольный бит ), которые используются все время для поиска ошибок в данных.
Microsoft сделала PowerShell доступным для macOS 10.13 или новее, а также для Linux, но если мысль об использовании чего-то, созданного с помощью Windows, вызывает у вас неприятные ощущения, знайте, что вы можете сделать то же самое в любой ОС.
macOS
Инструкция shasum эквивалентна Get-FileHash в PowerShell, а часть «-a 256» указывает, какой алгоритм использовать: 1 для SHA-1, 256 для SHA-256 и 512 для SHA-512.
Обратите внимание, как мы получили ту же контрольную сумму для тестового файла, что и при использовании PowerShell в Windows? В этом его реальная сила: независимо от того, какой компьютер или файловую систему вы используете, при одинаковом алгоритме вы всегда будете получать хеш-значения, которые можно напрямую сравнивать.
Linux
Если вам нравятся прелести Linux, вам будет приятно узнать, что это тот же процесс, что и выше — запустите Терминал и введите sha1sum, sha256sum или sha512sum, а затем адрес файла, чтобы сгенерировать требуемый хэш.
И снова вы можете видеть, что у нас такая же контрольная сумма для нашего текстового файла. Все прогоны производят одну и ту же математику для создания хэша, так что ничто из этого не должно было стать сюрпризом, но приятно знать, что контрольные суммы могут быть выполнены на любом вычислительном устройстве.
Заключение
Хотя подобные Steam обрабатывают этот процесс автоматически, мы полагаемся на файловые хосты, обеспечивающие точные контрольные суммы для данных, которые они предоставляют. В случае загрузок TechSpot, например, мы явно не предоставляем контрольную сумму, но инструменты, которые мы используем для подтверждения того, что загрузки являются чистыми, такие как VirusTotal, используют контрольную сумму для проверки целостности файлов и агрегирования данных, когда несколько сторон сканируют файлы. тот же файл с течением времени.
Некоторые веб-сайты предоставляют контрольные суммы для каждого файла, тогда как другие делают это только для важных или очень больших элементов (например, Microsoft в своих разделах безопасной загрузки), но это становится все более редким явлением. Для этого есть различные возможные причины, например, люди, просто не подозревающие о них.
Но если хосты предлагают это, то, по крайней мере, теперь вы знаете, как использовать хеш — любая дополнительная вещь, которая дает вам немного больше уверенности, всегда хорошо.
Простой расчет контрольной суммы
При передачи данных по линиям связи, используется контрольная сумма, рассчитанная по некоторому алгоритму. Алгоритм часто сложный, конечно, он обоснован математически, но очень уж неудобен при дефиците ресурсов, например при программировании микроконтроллеров.
Чтобы упростить алгоритм, без потери качества, нужно немного «битовой магии», что интересная тема сама по себе.
Без контрольной суммы, передавать данные опасно, так как помехи присутствуют везде и всегда, весь вопрос только в их вероятности возникновения и вызываемых ими побочных эффектах. В зависимости от условий и выбирается алгоритм выявления ошибок и количество данных в контрольной сумме. Сложнее алгоритм, и больше контрольная сумма, меньше не распознанных ошибок.
Причина помех на физическом уровне, при передаче данных.
Вот пример самого типичного алгоритма для микроконтроллера, ставшего, фактически, промышленным стандартом с 1979 года.
Не слабый такой код, есть вариант без таблицы, но более медленный (необходима побитовая обработка данных), в любом случае способный вынести мозг как программисту, так и микроконтроллеру. Не во всякий микроконтроллер алгоритм с таблицей влезет вообще.
Давайте разберем алгоритмы, которые вообще могут подтвердить целостность данных невысокой ценой.
Бит четности (1-битная контрольная сумма)
На первом месте простой бит четности. При необходимости формируется аппаратно, принцип простейший, и подробно расписан в википедии. Недостаток только один, пропускает двойные ошибки (и вообще четное число ошибок), когда четность всех бит не меняется. Можно использовать для сбора статистики о наличии ошибок в потоке передаваемых данных, но целостность данных не гарантирует, хотя и снижает вероятность пропущенной ошибки на 50% (зависит, конечно, от типа помех на линии, в данном случае подразумевается что число четных и нечетных сбоев равновероятно).
Для включения бита четности, часто и код никакой не нужен, просто указываем что UART должен задействовать бит четности. Типично, просто указываем:
Часто разработчики забывают даже, что UART имеет на борту возможность проверки бита четности. Кроме целостности передаваемых данных, это позволяет избежать устойчивого срыва синхронизации (например при передаче данных по радиоканалу), когда полезные данные могу случайно имитировать старт и стоп биты, а вместо данных на выходе буфера старт и стоп биты в случайном порядке.
8-битная контрольная сумма
Если контроля четности мало (а этого обычно мало), добавляется дополнительная контрольная сумма. Рассчитать контрольную сумму, можно как сумму ранее переданных байт, просто и логично
Естественно биты переполнения не учитываем, результат укладываем в выделенные под контрольную сумму 8 бит. Можно пропустить ошибку, если при случайном сбое один байт увеличится на некоторое значение, а другой байт уменьшится на то же значение. Контрольная сумма не изменится. Проведем эксперимент по передаче данных. Исходные данные такие:
.
,
на 256 отправленных телеграмм с ошибкой, одна пройдет проверку контрольной суммы. Смотрим статистику от виртуальной передачи данных, с помощью простой тестовой программы:
Или условный КПД=55%, от возможностей «идеальной» контрольной суммы. Такова плата за простоту алгоритма и скорость обработки данных. В целом, для многих применений, алгоритм работоспособен. Используется одна операция сложения и одна переменная 8-битовая. Нет возможности не корректной реализации. Поэтому алгоритм и применяется в контроллерах ADAMS, ICP, в составе протокола DCON (там дополнительно может быть включен бит четности, символы только ASCI, что так же способствует повышению надежности передачи данных и итоговая надежность несколько выше, так как часть ошибок выявляется по другим, дополнительным признакам, не связанных с контрольной суммой).
Не смотря на вероятность прохождения ошибки 1:143, вероятность обнаружения ошибки лучше, чем 1:256 невозможна теоретически. Потери в качестве работы есть, но не всегда это существенно. Если нужна надежность выше, нужно использовать контрольную сумму с большим числом бит. Или, иначе говоря, простая контрольная сумма, недостаточно эффективно использует примерно 0.75 бита из 8 имеющихся бит информации в контрольной сумме.
Для сравнения применим, вместо суммы, побитовое сложение XOR. Стало существенно хуже, вероятность обнаружения ошибки 1:67 или 26% от теоретического предела. Упрощенно, это можно объяснить тем, что XOR меняет при возникновении ошибке еще меньше бит в контрольной сумме, ниже отклик на единичный битовый сбой, и повторной ошибке более вероятно вернуть контрольную сумму в исходное состояние.
Так же можно утверждать, что контрольная сумма по XOR представляет из себя 8 независимых контрольных сумм из 1 бита. Вероятность того, что ошибка придется на один из 8 бит равна 1:8, вероятность двойного сбоя 1:64, что мы и наблюдаем, теоретическая величина совпала с экспериментальными данными.
Нам же нужен такой алгоритм, чтобы заменял при единичной ошибке максимальное количество бит в контрольной сумме. Но мы, в общей сложности, ограниченны сложностью алгоритма, и ресурсами в нашем распоряжении. Не во всех микроконтроллерах есть аппаратный блок расчета CRC. Но, практически везде, есть блок умножения. Рассчитаем контрольную сумму как произведение последовательности байт, на некоторую «магическую» константу:
Константа должна быть простой, и быть достаточно большой, для изменения большего числа бит после каждой операции, 211 вполне подходит, проверяем:
Всего 72% от теоретического предела, небольшое улучшение перед простой суммой. Алгоритм в таком виде не имеет смысла. В данном случае теряется важная информация из отбрасываемых старших 8..16 бит, а их необходимо учитывать. Проще всего, смешать функцией XOR с младшими битами 1..8. Приходим к еще более интенсивной модификации контрольной суммы, желательно с минимальным затратами ресурсов. Добавляем фокус из криптографических алгоритмов
Результат 91% от теоретического предела. Вполне годится для применения.
Если в микроконтроллере нет блока умножения, можно имитировать умножение операций сложения, смещения и XOR. Суть процесса такая же, модифицированный ошибкой бит, равномерно «распределяется» по остальным битам контрольной суммы.
На удивление хороший результат. Среднее значение 254,5 или 99% от теоретического предела, операций немного больше, но все они простые и не используется умножение.
Если для внутреннего хранения промежуточных значений контрольной суммы отдать 16 бит переменную (но передавать по линии связи будем только младшие 8 бит), что не проблема даже для самого слабого микроконтроллера, получим некоторое улучшение работы алгоритма. В целом экономить 8 бит нет особого смысла, и 8-битовая промежуточная переменная использовалась ранее просто для упрощения понимания работы алгоритма.
Что соответствует 100.6% от теоретического предела, вполне хороший результат для такого простого алгоритма из одной строчки:
Используется полноценное 16-битное умножение. Опять же не обошлось без магического числа 44111 (выбрано из общих соображений без перебора всего подмножества чисел). Более точно, константу имеет смысл подбирать, только определившись с предполагаемым типом ошибок в линии передачи данных.
Столь высокий результат объясняется тем, что 2 цикла умножения подряд, полностью перемешивают биты, что нам и требовалось. Исключением, похоже, является последний байт телеграммы, особенно его старшие биты, они не полностью замешиваются в контрольную сумму, но и вероятность того, что ошибка придется на них невелика, примерно 4%. Эта особенность практически ни как не проявляется статистически, по крайней мере на моем наборе тестовых данных и ошибке ограниченной 10 сбойными битами. Для исключения этой особенности можно делать N+1 итераций, добавив виртуальный байт в дополнение к имеющимся в тестовом блоке данных (но это усложнение алгоритма).
Вариант без умножения с аналогичным результатом. Переменная CRC 16-битная, данные 8-битные, результат работы алгоритма — младшие 8 бит найденной контрольной суммы:
Результат 100.6% от теоретического предела.
Вариант без умножения более простой, оставлен самый минимум функций, всего 3 математических операции:
Результат 86% от теоретического предела.
В этом случае потери старших бит нет, они возвращаются в младшую часть переменной через функцию XOR (битовый миксер).
Небольшое улучшение в некоторых случаях дает так же:
16-битная контрольная сумма
Далее, предположим что нам мало 8 бит для формирования контрольной суммы.
Следующий вариант 16 бит, и теоретическая вероятность ошибки переданных данных 1:65536, что намного лучше. Надежность растет по экспоненте. Но, как побочный эффект, растет количество вспомогательных данных, на примере нашей телеграммы, к 8 байтам полезной информации добавляется 2 байта контрольной суммы.
Простые алгоритмы суммы и XOR, применительно к 16-битной и последующим CRC не рассматриваем вообще, они практически не улучают качество работы, по сравнению с 8-битным вариантов.
Модифицируем алгоритм для обработки контрольной суммы разрядностью 16 бит, надо отметить, что тут так же есть магическое число 8 и 44111, значительное и необоснованное их изменение ухудшает работу алгоритма в разы.
Что соответствует 109% от теоретического предела. Присутствует ошибка измерений, но это простительно для 10 млн. итераций. Так же сказывается алгоритм создания, и вообще тип ошибок. Для более точного анализа, в любом случае нужно подстраивать условия под ошибки в конкретной линии передачи данных.
Дополнительно отмечу, что можно использовать 32-битные промежуточные переменные для накопления результата, а итоговую контрольную сумму использовать как младшие 16 бит. Во многих случаях, при любой разрядности контрольной суммы, так несколько улучшается качество работы алгоритма.
32-битная контрольная сумма
Перейдем к варианту 32-битной контрольной суммы. Появляется проблема со временем отводимым для анализа статистических данных, так как число переданных телеграмм уже сравнимо с 2^32. Алгоритм такой же, магические числа меняются в сторону увеличения
За 10 млн. итераций ошибка не обнаружена. Чтобы ускорить сбор статистики обрезал CRC до 24 бит:
Результат, из 10 млн. итераций ошибка обнаружена 3 раза
Вполне хороший результат и в целом близок к теоретическому пределу для 24 бит контрольной суммы (1:16777216). Тут надо отметить что функция контроля целостности данных равномерно распределена по всем битам CRC, и вполне возможно их отбрасывание с любой стороны, если есть ограничение на размер передаваемой CRC.
Для полноценных 32 бит, достаточно долго ждать результата, ошибок просто нет, за приемлемое время ожидания.
Вариант без умножения:
Сбоя для полноценной контрольной суммы дождаться не получилось. Контрольная сумма урезанная до 24 бит показывает примерно такие же результаты, 8 ошибок на 100 млн. итераций. Промежуточная переменная CRC 64-битная.
64-битная контрольная сумма
Ну и напоследок 64-битная контрольная сумма, максимальная контрольная сумма, которая имеет смысл при передачи данных на нижнем уровне:
Дождаться ошибки передачи данных, до конца существования вселенной, наверное не получится 🙂
Метод аналогичный тому, какой применили для CRC32 показал аналогичные результаты. Больше бит оставляем, выше надежность в полном соответствии с теоретическим пределом. Проверял на младших 20 и 24 битах, этого кажется вполне достаточным, для оценки качества работы алгоритма.
Так же можно применить для 128-битных чисел (и еще больших), главное подобрать корректно 128-битные магические константы. Но это уже явно не для микроконтроллеров, такие числа и компилятор не поддерживает.
Комментарии
В целом метод умножения похож на генерацию псевдослучайной последовательности, только с учетом полезных данных участвующих в процессе.
Рекомендую к использованию в микроконтроллерах, или для проверки целостности любых переданных данных. Вполне рабочий метод, уже как есть, не смотря на простоту алгоритма.
Мой проект по исследованию CRC на гитхаб.
Далее интересно было бы оптимизировать алгоритм на более реальных данных (не псевдослучайные числа по стандартному алгоритму), подобрать более подходящие магические числа под ряд задач и начальных условий, думаю можно еще выиграть доли процента по качеству работы алгоритма. Оптимизировать алгоритм по скорости, читаемости кода (простоте алгоритма), качеству работы. В идеале получить и протестировать образцы кода для всех типов микроконтроллеров, для этого как-раз и нужны примеры с использованием умножения 8, 16, 32 битных данных, и без умножения вообще.