Контрольная сумма Флетчера
Контрольная сумма Флетчера — это алгоритм вычисления контрольной суммы, разработанной Джоном Флетчером (1934—2012) из Лаборатории Лоуренса Ливермора в конце 1970-х годов.[1] Цель контрольной суммы Флетчера заключалась в том, чтобы обеспечить обнаружение ошибок, близкое к свойствам циклического избыточного кода, но с более низкой вычислительной сложностью при реализации на процессорах общего назначения.
Алгоритм
[править | править код]Обзор простых контрольных сумм
[править | править код]Как и в случае с более простыми алгоритмами контрольных сумм, контрольная сумма Флетчера включает в себя разделение двоичного слова, которое должно быть проверено на ошибки, на короткие «блоки» бит и вычисление суммы по модулю для этих блоков. (Данные, которые должны быть проверены в целом, называются «словом», а части, на которые оно делится, называются «блоки»).
Например, пусть передаваемое сообщение состоит из 136 символов, каждый из которых составляет 8 бит, тогда слово данных составляет 1088 бит. Удобным размером блока будет 8 бит, хотя это необязательно. А удобный модуль будет 255, хотя, опять же, может быть выбран другой. Таким образом, простая контрольная сумма вычисляется путём суммирования всех 8-битных блоков сообщения и вычисления результата по модулю 255 (то есть, деление на 255 и взятие только остатка). На практике вычисление по модулю выполняется во время суммирования для управления размером результата. Значение контрольной суммы передаётся вместе с сообщением, увеличивая его длину до 137 байтов или 1096 бит. Получатель сообщения может повторно вычислить контрольную сумму и сравнить её с полученным значением контрольной суммы, чтобы определить, было ли сообщение изменено в процессе передачи.
Слабые стороны простых контрольных сумм
[править | править код]Первая слабая сторона простой контрольной суммы состоит в том, что она нечувствительна к порядку блоков (байтов) в слове данных (сообщении). Если их порядок был изменён, значение контрольной суммы будет одинаковым, и изменение не будет обнаружено. Вторая слабая сторона заключается в том, что множество возможных значений контрольной суммы мало и равно выбранному модулю. В нашем примере имеется только 255 возможных значений контрольной суммы, поэтому легко видеть, что даже случайные данные имеют вероятность примерно 0,4% получения той же контрольной суммы, что и наше сообщение (см. Коллизия хеш-функции).
Контрольная сумма Флетчера
[править | править код]Флетчер исправил оба эти недостатка, вычисляя второе значение вместе с простой контрольной суммой. Это модульная сумма значений, полученных простой контрольной суммой, так как каждый блок слова данных добавляется к ней. Используемый модуль одинаковый. Таким образом, для каждого блока слова данных, взятого последовательно, значение блока добавляется к первой сумме, а новое значение первой суммы затем добавляется ко второй сумме. Обе суммы начинаются с ноля (или какого-либо другого заранее определённого значения). В конце слова данных применяется сложение по модулю, и два значения объединяются, формируя контрольную сумму Флетчера.
Чувствительность к порядку блоков вводится, потому что, как только блок добавляется к первой сумме, он затем повторно добавляется ко второй сумме вместе с каждым блоком до неё. Если, например, обменяться двумя соседними блоками, тот, который первоначально был первым, будет добавлен ко второй сумме один раз, а второй, который был первоначально вторым, будет добавлен ко второй сумме ещё раз. Окончательное значение первой суммы будет одинаковым, но вторая сумма будет отличаться, обнаружив изменение в сообщении.
Множество всех возможных значений контрольной суммы теперь является квадратом того же значения для простой контрольной суммы. В нашем примере две суммы, каждая из которых имеет 255 возможных значений, приводят к 65025 возможным значениям для комбинированной контрольной суммы.
Обзор различных параметров алгоритма
[править | править код]Несмотря на бесконечное количество параметров, в оригинальной работе изучается случай с длиной блока 8 бит и модулем 255 и 256.
Варианты с 16 и 32-битными блоками были получены из исходного случая и изучены в последующих спецификациях или документах.
16-битная сумма Флетчера
[править | править код]Когда слово данных разделяется на 8-битные блоки, как в приведённом выше примере, две 8-битные суммы объединяются в 16-битную контрольную сумму Флетчера.
Очевидно, что выбор модуля должен быть таким, чтобы результаты соответствовали размеру блока. 256, следовательно, является самым большим возможным модулем для Fletcher-16. Однако это плохой выбор, поскольку биты, которые переполняют бит 7, просто теряются. Модуль, который принимает бит переполнения и смешивает их с нижними битами, обеспечивает лучшее обнаружение ошибок. Модуль должен, однако, быть большим, чтобы получить наибольшее количество возможных значений контрольной суммы. Значение 255 берётся в связи со вторым соображением, но, как было установлено, обладает отличной производительностью.
32-битная сумма Флетчера
[править | править код]Когда слово данных разделено на 16-битные блоки, две 16-битные суммы объединяются в 32-битную контрольную сумму. Обычно используется модуль 65535, по тем же соображениям, что и 16-битная сумма.
64-битная сумма Флетчера
[править | править код]Когда слово данных разделено на 32-битные блоки, две 32-битные суммы объединяются в 64-битную контрольную сумму. Обычно используется модуль 4294967295, по тем же соображениям, что и 16, и 32-битные суммы.
Сравнение с контрольной суммой Adler
[править | править код]Контрольная сумма Adler-32 является специализацией контрольной суммы Fletcher-32, разработанной Марком Адлером. Выбранный модуль (для обеих сумм) равен простому числу 65 521 (65 535 делится на 3, 5, 17 и 257). Первая сумма начинается со значения 1. Выбор простого модуля приводит к улучшенному «перемешиванию» (ошибки обнаруживаются с более равномерной вероятностью, улучшая вероятность обнаружения наименее обнаружимых ошибок). Тем не менее, уменьшение размера множества всех возможных значений контрольной суммы действует против этого и немного снижает производительность. Одно из исследований показало, что Fletcher-32 превосходит Adler-32 как в производительности, так и в способности обнаруживать ошибки. Поскольку остаток по модулю 65535 значительно проще и быстрее реализовать, чем остаток по модулю 65521, контрольная сумма Fletcher-32 обычно является более быстрым алгоритмом.[2]
Слабые стороны
[править | править код]Контрольная сумма Флетчера не может различать блоки состоящие только из нолей или только из единиц. Например, если 16-разрядный блок в слове данных изменяется с 0x0000 на 0xFFFF, контрольная сумма Fletcher-32 останется неизменной.
Реализация
[править | править код]Прямая реализация
[править | править код]Неэффективная, но простая реализация функции на языке 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 не будут переполняться. Операция modulo применяется к первой сумме в строке 9 и ко второй сумме в строке 10. Здесь это делается после каждого добавления, так что в конце цикла for суммы всегда сводятся к 8 битам. В конце входных данных две суммы объединяются в 16-битное значение контрольной суммы Флетчера и возвращаются функцией в строке 13.
Каждая сумма вычисляется по модулю 255 и, таким образом, всегда остаётся меньше 0xFF. Таким образом, эта реализация никогда не приведёт к результатам контрольной суммы 0x00FF, 0xFF00 или 0xFFFF. Он может выдавать результат контрольной суммы 0x0000, что может быть нежелательно в некоторых случаях (например, когда это значение зарезервировано для обозначения «никакая контрольная сумма не была вычислена»).
Проверка байтов
[править | править код]Пример исходного кода для вычисления байтов проверки, используя указанную выше функцию, выглядит следующим образом. Байты проверки могут быть добавлены в конец потока данных, а c0 - перед c1.
uint16_t csum;
uint8_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 года Анастас Накассис обсудил и сравнил различные способы оптимизации алгоритма. Самая важная оптимизация заключается в отсрочке вычисления по модулю до тех пор, пока известно, что переполнения точно не произойдёт.[3]
Вот реализация на C, которая применяет данную оптимизацию:
uint16_t
fletcher16(const uint8_t *data, size_t len)
{
uint32_t c0, c1;
unsigned int i;
for (c0 = c1 = 0; len >= 5802; len -= 5802) {
for (i = 0; i < 5802; ++i) {
c0 = c0 + *data++;
c1 = c1 + c0;
}
c0 = c0 % 255;
c1 = c1 % 255;
}
for (i = 0; i < len; ++i) {
c0 = c0 + *data++;
c1 = c1 + c0;
}
c0 = c0 % 255;
c1 = c1 % 255;
return (c1 << 8 | c0);
}
uint32_t
fletcher32(const uint16_t *data, size_t len)
{
uint32_t c0, c1;
unsigned int i;
for (c0 = c1 = 0; len >= 360; len -= 360) {
for (i = 0; i < 360; ++i) {
c0 = c0 + *data++;
c1 = c1 + c0;
}
c0 = c0 % 65535;
c1 = c1 % 65535;
}
for (i = 0; i < len; ++i) {
c0 = c0 + *data++;
c1 = c1 + c0;
}
c0 = c0 % 65535;
c1 = c1 % 65535;
return (c1 << 16 | c0);
}
Тестовые векторы
[править | править код]8-битная реализация (16-битная контрольная сумма).
"abcde" -> 51440 (0xC8F0) "abcdef" -> 8279 (0x2057) "abcdefgh" -> 1575 (0x0627)
16-битная реализация (32-битная контрольная сумма).
"abcde" -> 4031760169 (0xF04FC729) "abcdef" -> 1448095018 (0x56502D2A) "abcdefgh" -> 3957429649 (0xEBE19591)
32-битная реализация (64-битная контрольная сумма)
"abcde" -> 14467467625952928454 (0xC8C6C527646362C6) "abcdef" -> 14467579776138987718 (0xC8C72B276463C8C6)
Примечания
[править | править код]- ↑ Fletcher, J. G. An Arithmetic Checksum for Serial Transmissions (англ.) // IEEE Transactions on Communications. — 1982 1 (vol. COM-30, no. 1). — P. 247–252.
- ↑ Theresa C. Maxino, Philip J. Koopman. The Effectiveness of Checksums for Embedded Control Networks (англ.) // IEEE Transactions on Dependable and Secure Computing. — 2009. — December. Архивировано 21 октября 2013 года.
- ↑ Anastase Nakassis. Fletcher's error detection algorithm: how to implement it efficiently and how toavoid the most common pitfalls (англ.) // Newsletter ACM SIGCOMM Computer Communication Review Homepage archive. — 1988. — October (vol. 18, no. 5). — P. 63—88.