Контрольная сумма Флетчера

Контрольная сумма Флетчера — это алгоритм вычисления контрольной суммы, разработанной Джоном Флетчером (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.

[1] Fletcher, J. G. An Arithmetic Checksum for Serial Transmissions (англ.) // IEEE Transactions on Communications. — 1982 1 (vol. COM-30, no. 1). — P. 247–252.

[2] 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 года.

[3] 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.

[1]

[2]

[3]