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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Примечания

[править | править код]
  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.