Контрольная сумма Флетчера — это алгоритм вычисления контрольной суммы, зависящей от позиции , разработанный Джоном Г. Флетчером (1934–2012) в Ливерморской лаборатории Лоуренса в конце 1970-х годов. [1] Целью контрольной суммы Флетчера было обеспечение свойств обнаружения ошибок, приближающихся к свойствам проверки циклическим избыточным кодом , но с меньшими вычислительными затратами, связанными с методами суммирования.
Как и в случае с более простыми алгоритмами контрольной суммы, контрольная сумма Флетчера включает деление слова двоичных данных , которое необходимо защитить от ошибок, на короткие «блоки» битов и вычисление модульной суммы этих блоков. (Обратите внимание, что терминология, используемая в этой области, может сбивать с толку. Защищаемые данные целиком называются «словом», а части, на которые они разделены, называются «блоками».)
Например, данные могут представлять собой передаваемое сообщение, состоящее из 136 символов, каждый из которых хранится в виде 8-битного байта , что в сумме составляет слово данных из 1088 бит. Удобный размер блока — 8 бит, хотя это и не обязательно. Аналогично, удобным модулем будет 255, хотя, опять же, можно выбрать и другие. Итак, простая контрольная сумма вычисляется путем сложения всех 8-битных байтов сообщения, деления на 255 и сохранения только остатка. (На практике во время суммирования выполняется операция по модулю для контроля размера результата.) Значение контрольной суммы передается вместе с сообщением, увеличивая его длину до 137 байтов или 1096 бит. Получатель сообщения может повторно вычислить контрольную сумму и сравнить ее с полученным значением, чтобы определить, было ли сообщение изменено в процессе передачи.
Первый недостаток простой контрольной суммы заключается в том, что она нечувствительна к порядку блоков (байтов) в слове данных (сообщении). Если порядок изменен, значение контрольной суммы останется тем же, и изменение не будет обнаружено. Второй недостаток заключается в том, что набор значений контрольных сумм невелик и равен выбранному модулю. В нашем примере существует только 255 возможных значений контрольной суммы, поэтому легко увидеть, что даже случайные данные имеют вероятность иметь ту же контрольную сумму, что и наше сообщение, примерно в 0,4%.
Флетчер устраняет оба этих недостатка, вычисляя второе значение вместе с простой контрольной суммой. Это модульная сумма значений, принимаемых простой контрольной суммой при добавлении к ней каждого блока слова данных. Используемый модуль тот же. Таким образом, для каждого блока слова данных, взятого последовательно, значение блока добавляется к первой сумме, а новое значение первой суммы затем добавляется ко второй сумме. Обе суммы начинаются со значения ноль (или другого известного значения). В конце слова данных применяется оператор модуля, и два значения объединяются для формирования значения контрольной суммы Флетчера.
Вводится чувствительность к порядку блоков, поскольку, как только блок добавляется к первой сумме, он затем повторно добавляется ко второй сумме вместе с каждым блоком после него. Если, например, поменяются местами два соседних блока, то тот, который изначально был первым, будет добавлен ко второй сумме на один раз меньше, а тот, который изначально был вторым, будет добавлен ко второй сумме еще один раз. Окончательное значение первой суммы будет таким же, но вторая сумма будет другой, что указывает на изменение сообщения.
Всевозможные значения контрольной суммы теперь представляют собой квадрат значения простой контрольной суммы. В нашем примере две суммы, каждая из которых имеет 255 возможных значений, дают 65025 возможных значений объединенной контрольной суммы.
Несмотря на бесконечность параметров, в оригинальной статье изучается только случай K = 8 (длина слова) с модулем 255 и 256.
16- и 32-битные версии (Fletcher-32 и -64) были созданы на основе исходного случая и изучены в последующих спецификациях или статьях.
Когда слово данных делится на 8-битные блоки, как в примере выше, получаются две 8-битные суммы, которые объединяются в 16-битную контрольную сумму Флетчера. Обычно вторая сумма умножается на 256 и добавляется к простой контрольной сумме, эффективно складывая суммы рядом в 16-битное слово с простой контрольной суммой в наименее значимом конце. Этот алгоритм тогда называется контрольной суммой Флетчера-16. Также обычно подразумевается использование модуля 2 8 − 1 = 255.
Когда слово данных делится на 16-битные блоки, в результате получаются две 16-битные суммы, которые объединяются в 32-битную контрольную сумму Флетчера. Обычно вторая сумма умножается на 2 16 и добавляется к простой контрольной сумме, эффективно складывая суммы рядом в 32-битное слово с простой контрольной суммой в наименее значимом конце. Этот алгоритм тогда называется контрольной суммой Флетчера-32. Также обычно подразумевается использование модуля 2 16 − 1 = 65,535. Обоснование этого выбора такое же, как и для Флетчера-16.
Когда слово данных делится на 32-битные блоки, в результате получаются две 32-битные суммы, которые объединяются в 64-битную контрольную сумму Флетчера. Обычно вторая сумма умножается на 2 32 и добавляется к простой контрольной сумме, эффективно складывая суммы рядом в 64-битное слово с простой контрольной суммой в наименее значимом конце. Этот алгоритм тогда называется контрольной суммой Флетчера-64. Также обычно подразумевается использование модуля 2 32 − 1 = 4 294 967 295. Обоснование этого выбора такое же, как и для Флетчер-16 и Флетчер-32.
Контрольная сумма Адлера -32 — это специализация контрольной суммы Флетчера-32, разработанная Марком Адлером . Выбранный модуль (для обеих сумм) представляет собой простое число 65 521 (65 535 делится на 3, 5, 17 и 257). Первая сумма также начинается со значения 1. Выбор простого модуля приводит к улучшению «смешивания» (паттерны ошибок обнаруживаются с более равномерной вероятностью, повышая вероятность того, что будут обнаружены наименее обнаруживаемые закономерности, что имеет тенденцию доминировать над общей производительностью). ). Однако уменьшение размера совокупности возможных значений контрольной суммы действует против этого и немного снижает производительность. Одно исследование показало, что Fletcher-32 превосходит Adler-32 как по производительности, так и по способности обнаруживать ошибки. Поскольку сложение по модулю 65 535 значительно проще и быстрее реализовать, чем сложение по модулю 65 521, контрольная сумма Флетчера-32 обычно является более быстрым алгоритмом. [2]
Модуль 255 используется выше и в примерах ниже для Fletcher-16, однако в некоторых реальных реализациях используется 256. Альтернативная контрольная сумма протокола TCP имеет Fletcher-16 с модулем 256, [3], как и контрольные суммы UBX-*. сообщения от U-blox GPS. [4] Какой модуль используется, зависит от реализации.
Например, контрольная сумма Fletcher-16 должна быть рассчитана и проверена для потока байтов 0x01 0x02.
Таким образом, контрольная сумма равна 0x0403. Он может быть передан вместе с потоком байтов и проверен как таковой на принимающей стороне. Другой вариант — вычислить на втором этапе пару контрольных байтов, которые можно добавить к потоку байтов, чтобы результирующий поток имел глобальное значение контрольной суммы Fletcher-16, равное 0.
Значения контрольных байтов вычисляются следующим образом:
где C0 и C1 — результат последнего шага вычисления Fletcher-16.
В нашем случае байты контрольной суммы: CB0 = 0xF8 и CB1 = 0x04. Передаваемый поток байтов: 0x01 0x02 0xF8 0x04. Получатель проверяет контрольную сумму по всем четырем байтам и вычисляет проходную контрольную сумму 0x00 0x00, как показано ниже:
Контрольная сумма Флетчера не может отличить блоки со всеми 0 битами и блоки со всеми 1 битами. Например, если 16-битный блок в слове данных изменится с 0x0000 на 0xFFFF, контрольная сумма Fletcher-32 останется прежней. Это также означает, что последовательность всех байтов 00 имеет ту же контрольную сумму, что и последовательность (того же размера) всех байтов FF.
В этих примерах предполагается арифметика с дополнением до двух , поскольку алгоритм Флетчера будет неверным на машинах с дополнением до единицы .
Ниже описано, как вычислить контрольную сумму, включая контрольные байты; т. е. окончательный результат должен быть равен 0, если проверочные байты рассчитаны правильно. Однако сам код не будет вычислять проверочные байты.
Ниже представлена неэффективная, но простая реализация функции языка C для вычисления контрольной суммы Fletcher-16 массива 8 -битных элементов данных:
uint16_t Fletcher16 ( uint8_t * данные , число int ) { uint16_t sum1 = 0 ; uint16_t sum2 = 0 ; индекс интервала ; for ( индекс = 0 ; индекс < счет ; ++ индекс ) { сумма1 = ( сумма1 + данные [ индекс ]) % 255 ; сумма2 = ( сумма2 + сумма1 ) % 255 ; } возврат ( сумма2 << 8 ) | сумма1 ; }В строках 3 и 4 суммы представляют собой 16-битные переменные , поэтому сложения в строках 9 и 10 не переполняются . Операция по модулю применяется к первой сумме в строке 9 и ко второй сумме в строке 10. Здесь это делается после каждого сложения, так что в конце цикла for суммы всегда уменьшаются до 8 бит. В конце входных данных две суммы объединяются в 16-битное значение контрольной суммы Флетчера и возвращается функцией в строке 13.
Каждая сумма вычисляется по модулю 255 и, таким образом, всегда остается меньше 0xFF. Таким образом, эта реализация никогда не будет выдавать результаты контрольной суммы 0x??FF, 0xFF?? или 0xFFFF (т. е. 511 из 65536 возможных 16-битных значений никогда не используются). Он может выдать результат контрольной суммы 0x0000, что может быть нежелательно в некоторых обстоятельствах (например, когда это значение зарезервировано для обозначения «контрольная сумма не была вычислена»).
Пример исходного кода для расчета проверочных байтов с использованием вышеуказанной функции выглядит следующим образом. Проверочные байты могут быть добавлены в конец потока данных, причем c0 предшествует c1.
uint16_t csum ; uint16_t c0 , c1 , f0 , f1 ; csum = Fletcher16 ( данные , длина ); f0 = csum & 0xff ; f1 = ( csum >> 8 ) & 0xff ; c0 = 0xff - (( f0 + f1 ) % 0xff ); c1 = 0xff - (( f0 + c0 ) % 0xff ); В статье 1988 года Анастасий Накассис обсудил и сравнил различные способы оптимизации алгоритма. Самая важная оптимизация заключается в использовании аккумуляторов большего размера и отсрочке относительно дорогостоящей операции по модулю до тех пор, пока не будет доказано, что переполнения не произойдет. Дополнительную выгоду можно получить, заменив оператор по модулю эквивалентной функцией, адаптированной к этому конкретному случаю, например, простым сравнением и вычитанием, поскольку частное никогда не превышает 1. [5]
Вот реализация C , которая применяет первую, но не вторую оптимизацию:
#include <stdlib.h> /* для size_t */ #include <stdint.h> /* для uint8_t, uint16_t и uint32_t */ uint16_t fletcher16 ( const uint8_t * data , size_t len ) { uint32_t c0 , c1 ; /* Найдено путем решения проблемы переполнения c1: */ /* n > 0 и n * (n+1)/2 * (2^8-1) < (2^32-1). */ for ( c0 = c1 = 0 ; len > 0 ; ) { size_t blocklen = len ; если ( blocklen > 5802 ) { blocklen = 5802 ; } Лен -= блоклен ; do { c0 = c0 + * данные ++ ; с1 = с1 + с0 ; } Пока ( -блоклен ) ; с0 = с0 % 255 ; с1 = с1 % 255 ; } Возврат ( c1 << 8 | c0 ); } uint32_t fletcher32 ( const uint16_t * data , size_t len ) { uint32_t c0 , c1 ; длина = ( длина + 1 ) & ~ 1 ; /* Округляем len до слов */ /* Аналогичным образом мы решаем здесь n > 0 и n * (n+1)/2 * (2^16-1) < (2^32-1). */ /* На современных компьютерах использование 64-битного c0/c1 может позволить получить размер группы 23726746. */ for ( c0 = c1 = 0 ; len > 0 ; ) { size_t blocklen = len ; если ( blocklen > 360 * 2 ) { blocklen = 360 * 2 ; } Лен -= блоклен ; do { c0 = c0 + * данные ++ ; с1 = с1 + с0 ; } while (( blocklen -= 2 )); с0 = с0 % 65535 ; с1 = с1 % 65535 ; } Возврат ( c1 << 16 | c0 ); } // Аналогичную процедуру можно написать и для fletcher64. Размер группы будет 92681.Вторая оптимизация не используется, поскольку предположение «никогда не превышает 1» применяется только тогда, когда модуль вычисляется наивно; применение первой оптимизации сломало бы ее. С другой стороны, числа Мерсенна по модулю , такие как 255 и 65535, в любом случае являются быстрой операцией на компьютерах, поскольку доступны приемы, позволяющие выполнить их без дорогостоящей операции деления. [6]
8-битная реализация (16-битная контрольная сумма)
«abcde» -> 51440 (0xC8F0)«abcdef» -> 8279 (0x2057)«abcdefgh» -> 1575 (0x0627)
16-битная реализация (32-битная контрольная сумма), с 8-битными значениями ASCII входного слова, собранными в 16-битные блоки в порядке с прямым порядком байтов , слово дополняется нулями по мере необходимости до следующего целого блока, используя модуль 65535 и результат представлен как сумма сумм, сдвинутая влево на 16 бит (умноженная на 65536) плюс простая сумма
«abcde» -> 4031760169 (0xF04FC729)«abcdef» -> 1448095018 (0x56502D2A)«abcdefgh» -> 3957429649 (0xEBE19591)
32-битная реализация (64-битная контрольная сумма)
"abcde" -> 14467467625952928454 (0xC8C6C527646362C6)«abcdef» -> 14467579776138987718 (0xC8C72B276463C8C6)«abcdefgh» -> 3543817411021686982 (0x312E2B28CCCAC8C6)
Как и в любом вычислении, которое делит двоичное слово данных на короткие блоки и рассматривает блоки как числа, любые две системы, рассчитывающие получить одинаковый результат, должны сохранять порядок битов в слове данных. В этом отношении контрольная сумма Флетчера не отличается от других алгоритмов контрольной суммы и CRC и не нуждается в особых пояснениях.
Проблема упорядочивания, которую легко представить, возникает, когда слово данных передается побайтно между системой с прямым порядком байтов и системой с прямым порядком байтов и вычисляется контрольная сумма Fletcher-32. Если блоки извлекаются из слова данных в памяти путем простого чтения 16-битного целого числа без знака, то значения блоков будут разными в двух системах из-за изменения порядка байтов 16-битных элементов данных. в памяти, и, как следствие, результат контрольной суммы будет другим. В примерах реализации, приведенных выше, не рассматриваются проблемы упорядочения, чтобы не усложнять алгоритм контрольной суммы. Поскольку контрольная сумма Fletcher-16 использует 8-битные блоки, на нее не влияет порядок байтов .
{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )