Контрольная сумма Флетчера
— Контрольная сумма Флетчера это алгоритм вычисления контрольной суммы, зависящей от позиции, разработанный Джоном Г. Флетчером (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) были созданы на основе исходного случая и изучены в последующих спецификациях или статьях.
Флетчер-16
[ редактировать ]Когда слово данных делится на 8-битные блоки, как в примере выше, получаются две 8-битные суммы, которые объединяются в 16-битную контрольную сумму Флетчера. Обычно вторая сумма умножается на 256 и добавляется к простой контрольной сумме, эффективно складывая суммы рядом в 16-битное слово с простой контрольной суммой в наименее значимом конце. Этот алгоритм затем называется контрольной суммой Флетчера-16. Использование модуля 2 8 − 1 = 255 также обычно подразумевается.
Флетчер-32
[ редактировать ]Когда слово данных делится на 16-битные блоки, в результате получаются две 16-битные суммы, которые объединяются в 32-битную контрольную сумму Флетчера. Обычно вторую сумму умножают на 2. 16 и добавляется к простой контрольной сумме, эффективно складывая суммы рядом в 32-битное слово с простой контрольной суммой в наименее значимом конце. Этот алгоритм тогда называется контрольной суммой Флетчера-32. Использование модуля 2 16 − 1 = 65 535 также обычно подразумевается. Обоснование этого выбора такое же, как и для Флетчера-16.
Флетчер-64
[ редактировать ]Когда слово данных делится на 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] Какой модуль используется, зависит от реализации.
Пример расчета контрольной суммы Флетчера-16
[ редактировать ]Например, контрольная сумма Fletcher-16 должна быть рассчитана и проверена для потока байтов 0x01 0x02.
- C0_initial = 0
- C1_initial = 0
| Обмен (Б) | C0 = (C0 предыдущая + B) mod 255 | C1 = (C1 предыдущая + C0) по модулю 255 | Описание |
|---|---|---|---|
| 0x01 | 0x01 | 0x01 | Введен первый байт |
| 0x02 | 0x03 | 0x04 | Введен второй байт |
Таким образом, контрольная сумма равна 0x0403. Он может быть передан вместе с потоком байтов и проверен как таковой на принимающей стороне. Другой вариант — вычислить на втором этапе пару контрольных байтов, которые можно добавить к потоку байтов, чтобы результирующий поток имел глобальное значение контрольной суммы Fletcher-16, равное 0.
Значения контрольных байтов вычисляются следующим образом:
- CB0 = 255 − ((C0 + C1) mod 255),
- CB1 = 255 − ((C0 + CB0) mod 255),
где C0 и C1 — результат последнего шага вычисления Fletcher-16.
В нашем случае байты контрольной суммы: CB0 = 0xF8 и CB1 = 0x04. Передаваемый поток байтов: 0x01 0x02 0xF8 0x04. Получатель проверяет контрольную сумму по всем четырем байтам и вычисляет проходную контрольную сумму 0x00 0x00, как показано ниже:
| Обмен (Б) | C0 = (C0 предыдущая + B) mod 255 | C1 = (C1 предыдущая + C0) по модулю 255 | Описание |
|---|---|---|---|
| 0x01 | 0x01 | 0x01 | Введен первый байт |
| 0x02 | 0x03 | 0x04 | Введен второй байт |
| СВ0 = 0xF8 | (0x03 + 0xF8) % 0xFF = 0xFB | (0x04 + 0xFB) % 0xFF = 0x00 | Расчет контрольной суммы – байт 1 |
| СВ1 = 0x04 | (0xFB + 0x04) % 0xFF = 0x00 | (0x00 + 0x00) % 0xFF = 0x00 | Расчет контрольной суммы – байт 2 |
Слабые стороны
[ редактировать ]Контрольная сумма Флетчера не может различать блоки со всеми 0 битами и блоки со всеми 1 битами. Например, если 16-битный блок в слове данных изменится с 0x0000 на 0xFFFF, контрольная сумма Fletcher-32 останется прежней. Это также означает, что последовательность всех байтов 00 имеет ту же контрольную сумму, что и последовательность (того же размера) всех байтов FF.
Выполнение
[ редактировать ]В этих примерах предполагается арифметика с дополнением до двух , поскольку алгоритм Флетчера будет неверным на с дополнением до одного машинах .
Простой
[ редактировать ]Ниже описано, как вычислить контрольную сумму, включая контрольные байты; т. е. окончательный результат должен быть равен 0, если проверочные байты рассчитаны правильно. Однако сам код не будет вычислять проверочные байты.
Ниже представлена неэффективная, но простая реализация языка C функции для вычисления контрольной суммы Fletcher-16 массива 8 -битных элементов данных:
uint16_t Fletcher16( uint8_t *data, int count )
{
uint16_t sum1 = 0;
uint16_t sum2 = 0;
int index;
for ( index = 0; index < count; ++index )
{
sum1 = (sum1 + data[index]) % 255;
sum2 = (sum2 + sum1) % 255;
}
return (sum2 << 8) | sum1;
}
В строках 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(data, length);
f0 = csum & 0xff;
f1 = (csum >> 8) & 0xff;
c0 = 0xff - ((f0 + f1) % 0xff);
c1 = 0xff - ((f0 + c0) % 0xff);
Оптимизации
[ редактировать ]В статье 1988 года Анастасий Накассис обсудил и сравнил различные способы оптимизации алгоритма. Самая важная оптимизация заключается в использовании аккумуляторов большего размера и отсрочке относительно дорогостоящей операции по модулю до тех пор, пока не будет доказано, что переполнения не произойдет. Дополнительную выгоду можно получить, заменив оператор по модулю эквивалентной функцией, адаптированной для этого конкретного случая, например, простым сравнением и вычитанием, поскольку частное никогда не превышает 1. [5]
Вот реализация C , которая применяет первую, но не вторую оптимизацию:
#include <stdlib.h> /* for size_t */
#include <stdint.h> /* for uint8_t, uint16_t & uint32_t */
uint16_t fletcher16(const uint8_t *data, size_t len) {
uint32_t c0, c1;
/* Found by solving for c1 overflow: */
/* n > 0 and 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; /* Round up len to words */
/* We similarly solve for n > 0 and n * (n+1) / 2 * (2^16-1) < (2^32-1) here. */
/* On modern computers, using a 64-bit c0/c1 could allow a group size of 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);
}
// A similar routine could be written for fletcher64. The group size would be 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-битные блоки, на нее не влияет порядок байтов .
Ссылки
[ редактировать ]- ^ Флетчер, Дж. Г. (январь 1982 г.). «Арифметическая контрольная сумма для последовательных передач». Транзакции IEEE по коммуникациям . КОМ-30 (1): 247–252. дои : 10.1109/tcom.1982.1095369 .
- ^ Тереза К. Максино, Филип Дж. Купман (январь 2009 г.). «Эффективность контрольных сумм для встроенных сетей управления» (PDF) . Транзакции IEEE для надежных и безопасных вычислений.
- ^ Дж. Цвейг, UIUC, К. Партридж, BBN (февраль 1990 г.). «Параметры альтернативной контрольной суммы TCP» . Сетевая рабочая группа.
{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Сартек, Разное (июнь 2018 г.). «Правильный расчет контрольной суммы UBX в Python» . Портал поддержки uBlox.
- ^ Анастасий Накассис (октябрь 1988 г.). «Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок». Информационный бюллетень ACM SIGCOMM Обзор компьютерных коммуникаций Архив домашней страницы . 18 (5): 63–88. дои : 10.1145/53644.53648 . S2CID 17356816 .
- ^ Джонс, Дуглас В. «Модуль без деления, учебное пособие» . УНИВЕРСИТЕТ АЙОВЫ Факультет компьютерных наук . Проверено 9 сентября 2019 г.
Внешние ссылки
[ редактировать ]- RFC 905 - Спецификация транспортного протокола ISO описывает алгоритм суммирования контрольной суммы Флетчера до нуля (в Приложении B).
- RFC 1146 — Альтернативные параметры контрольной суммы TCP описывает алгоритм контрольной суммы Флетчера для использования с TCP.
- Стоун, Джонатан; Гринвальд, Майкл; Партридж, Крейг; Хьюз, Джим (1998). «Производительность контрольных сумм и CRC над реальными данными». Транзакции IEEE/ACM в сети . 6 (5): 529–543. CiteSeerX 10.1.1.55.8520 . дои : 10.1109/90.731187 . S2CID 1750358 .
- Кодис, Джон (1 мая 1992 г.). «Когда дело доходит до высокоскоростной проверки данных, алгоритм контрольной суммы Флетчера может справиться с этой задачей» . Доктор Добб .
- Сомертитл, Алан (12 апреля 2013 г.). «Контрольные суммы Флетчера в ZFS» (PDF) . Спектральная логика.