Контрольная сумма Флетчера — это алгоритм вычисления позиционно-зависимой контрольной суммы, разработанный Джоном Г. Флетчером (1934–2012) в Ливерморской лаборатории им. Лоуренса в конце 1970-х годов. [1] Целью контрольной суммы Флетчера было обеспечение свойств обнаружения ошибок, приближающихся к свойствам циклического избыточного кода , но с меньшими вычислительными затратами, связанными с методами суммирования.
Как и в случае с более простыми алгоритмами контрольной суммы, контрольная сумма Флетчера включает в себя разделение двоичного слова данных , которое должно быть защищено от ошибок, на короткие «блоки» битов и вычисление модульной суммы этих блоков. (Обратите внимание, что терминология, используемая в этой области, может быть запутанной. Данные, которые должны быть защищены, в целом называются «словом», а части, на которые они разделены, называются «блоками».)
Например, данные могут быть сообщением для передачи, состоящим из 136 символов, каждый из которых хранится как 8-битный байт , что составляет слово данных из 1088 бит в общей сложности. Удобный размер блока будет 8 бит, хотя это не обязательно. Аналогично, удобный модуль будет 255, хотя, опять же, можно выбрать и другие. Таким образом, простая контрольная сумма вычисляется путем сложения всех 8-битных байтов сообщения, деления на 255 и сохранения только остатка. (На практике операция по модулю выполняется во время суммирования для контроля размера результата.) Значение контрольной суммы передается вместе с сообщением, увеличивая его длину до 137 байт или 1096 бит. Получатель сообщения может повторно вычислить контрольную сумму и сравнить ее с полученным значением, чтобы определить, было ли сообщение изменено в процессе передачи.
Первая слабость простой контрольной суммы заключается в том, что она нечувствительна к порядку блоков (байтов) в слове данных (сообщении). Если порядок изменен, значение контрольной суммы будет тем же самым, и изменение не будет обнаружено. Вторая слабость заключается в том, что вселенная значений контрольной суммы мала, будучи равной выбранному модулю. В нашем примере существует только 255 возможных значений контрольной суммы, поэтому легко увидеть, что даже случайные данные имеют вероятность около 0,4% иметь ту же контрольную сумму, что и наше сообщение.
Fletcher устраняет оба этих недостатка, вычисляя второе значение вместе с простой контрольной суммой. Это модульная сумма значений, принимаемых простой контрольной суммой по мере добавления к ней каждого блока слова данных. Используемый модуль тот же самый. Таким образом, для каждого блока слова данных, взятого последовательно, значение блока добавляется к первой сумме, а новое значение первой суммы затем добавляется ко второй сумме. Обе суммы начинаются со значения ноль (или некоторого другого известного значения). В конце слова данных применяется оператор модуля, и два значения объединяются для формирования значения контрольной суммы Fletcher.
Чувствительность к порядку блоков вводится, поскольку после добавления блока к первой сумме он затем многократно добавляется ко второй сумме вместе с каждым блоком после него. Если, например, два соседних блока поменяются местами, тот, который изначально был первым, будет добавлен ко второй сумме на один раз меньше, а тот, который изначально был вторым, будет добавлен ко второй сумме еще один раз. Конечное значение первой суммы будет тем же самым, но вторая сумма будет другой, обнаруживая изменение в сообщении.
Вселенная возможных значений контрольной суммы теперь является квадратом значения простой контрольной суммы. В нашем примере две суммы, каждая из которых имеет 255 возможных значений, дают в результате 65025 возможных значений для объединенной контрольной суммы.
Хотя существует бесконечное множество параметров, в оригинальной статье изучается только случай K=8 (длина слова) с модулем 255 и 256.
Версии 16 и 32 бит (Fletcher-32 и -64) были созданы на основе исходного случая и изучены в последующих спецификациях или статьях.
Когда слово данных делится на 8-битные блоки, как в примере выше, получаются две 8-битные суммы, которые объединяются в 16-битную контрольную сумму Флетчера. Обычно вторая сумма умножается на 256 и добавляется к простой контрольной сумме, эффективно складывая суммы бок о бок в 16-битное слово с простой контрольной суммой в наименее значимом конце. Этот алгоритм затем называется контрольной суммой Флетчера-16. Использование модуля 2 8 − 1 = 255 также обычно подразумевается.
Когда слово данных делится на 16-битные блоки, получаются две 16-битные суммы, которые объединяются в 32-битную контрольную сумму Fletcher. Обычно вторая сумма умножается на 2 16 и добавляется к простой контрольной сумме, эффективно складывая суммы бок о бок в 32-битное слово с простой контрольной суммой в наименее значимом конце. Этот алгоритм затем называется контрольной суммой Fletcher-32. Использование модуля 2 16 − 1 = 65 535 также обычно подразумевается. Обоснование этого выбора такое же, как и для Fletcher-16.
Когда слово данных делится на 32-битные блоки, получаются две 32-битные суммы, которые объединяются в 64-битную контрольную сумму Fletcher. Обычно вторая сумма умножается на 2 32 и добавляется к простой контрольной сумме, эффективно складывая суммы бок о бок в 64-битное слово с простой контрольной суммой в наименее значимом конце. Этот алгоритм затем называется контрольной суммой Fletcher-64. Использование модуля 2 32 − 1 = 4 294 967 295 также обычно подразумевается. Обоснование этого выбора такое же, как для Fletcher-16 и Fletcher-32.
Контрольная сумма Adler -32 является специализацией контрольной суммы Fletcher-32, разработанной Марком Адлером . Выбранный модуль (для обеих сумм) является простым числом 65 521 (65 535 делится на 3, 5, 17 и 257). Первая сумма также начинается со значения 1. Выбор простого модуля приводит к улучшенному «смешиванию» (шаблоны ошибок обнаруживаются с более равномерной вероятностью, что повышает вероятность того, что будут обнаружены наименее обнаруживаемые шаблоны, что, как правило, доминирует над общей производительностью). Однако уменьшение размера вселенной возможных значений контрольной суммы действует против этого и немного снижает производительность. Одно исследование показало, что Fletcher-32 превосходит Adler-32 как по производительности, так и по способности обнаруживать ошибки. Поскольку сложение по модулю 65 535 значительно проще и быстрее в реализации, чем сложение по модулю 65 521, контрольная сумма Fletcher-32, как правило, является более быстрым алгоритмом. [2]
Выше и в примерах ниже для Fletcher-16 используется модуль 255, однако некоторые реальные реализации используют 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, как показано ниже:
Контрольная сумма Fletcher не может различать блоки из всех 0 битов и блоки из всех 1 битов. Например, если 16-битный блок в слове данных изменится с 0x0000 на 0xFFFF, контрольная сумма Fletcher-32 останется прежней. Это также означает, что последовательность из всех 00 байтов имеет ту же контрольную сумму, что и последовательность (того же размера) из всех FF байтов.
В этих примерах предполагается арифметика с дополнительным кодом , поскольку алгоритм Флетчера будет некорректным на машинах с дополнительным кодом .
Ниже приведено описание того, как вычислить контрольную сумму, включая контрольные байты; т. е. конечный результат должен быть равен 0, учитывая правильно вычисленные контрольные байты. Однако сам код не будет вычислять контрольные байты.
Ниже приведена неэффективная, но простая реализация функции языка C для вычисления контрольной суммы Fletcher-16 массива 8 -битных элементов данных:
uint16_t Fletcher16 ( uint8_t * данные , количество целых чисел ) { uint16_t сумма1 = 0 ; uint16_t сумма2 = 0 ; целочисленный индекс ; для ( индекс = 0 ; индекс < количество ; ++ индекс ) { сумма1 = ( сумма1 + данные [ индекс ]) % 255 ; сумма2 = ( сумма2 + сумма1 ) % 255 ; } возврат ( сумма2 << 8 ) | сумма1 ; }В строках 3 и 4 суммы являются 16-битными переменными , так что сложения в строках 9 и 10 не приведут к переполнению . Операция по модулю применяется к первой сумме в строке 9 и ко второй сумме в строке 10. Здесь это делается после каждого сложения, так что в конце цикла for суммы всегда сокращаются до 8 бит. В конце входных данных две суммы объединяются в 16-битное значение контрольной суммы Fletcher и возвращаются функцией в строке 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 ; if ( blocklen > 5802 ) { blocklen = 5802 ; } len -= blocklen ; do { c0 = c0 + * data ++ ; c1 = c1 + c0 ; } while ( -- blocklen ); c0 = c0 % 255 ; c1 = c1 % 255 ; } return ( c1 << 8 | c0 ); } uint32_t fletcher32 ( const uint16_t * data , size_t len ) { uint32_t c0 , c1 ; len = ( len + 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 ; if ( blocklen > 360 * 2 ) { blocklen = 360 * 2 ; } len -= blocklen ; do { c0 = c0 + * data ++ ; c1 = c1 + c0 ; } while (( blocklen -= 2 )); c0 = c0 % 65535 ; c1 = c1 % 65535 ; } return ( 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: несколько имен: список авторов ( ссылка )