WikiSort.ru - Не сортированное

Обзор простых контрольных сумм

Как и в случае с более простыми алгоритмами контрольных сумм, контрольная сумма Флетчера включает в себя разделение двоичного слова, которое должно быть проверено на ошибки, на короткие «блоки» бит и вычисление суммы по модулю для этих блоков. (Данные, которые должны быть проверены в целом, называются «словом», а части, на которые оно делится, называются «блоки»).

Например, пусть передаваемое сообщение состоит из 136 символов, каждый из которых составляет 8 бит, тогда слово данных составляет 1088 бит. Удобным размером блока будет 8 бит, хотя это необязательно. А удобный модуль будет 255, хотя, опять же, может быть выбран другой. Таким образом, простая контрольная сумма вычисляется путём суммирования всех 8-битных блоков сообщения и вычисления результата по модулю 255 (то есть, деление на 255 и взятие только остатка). На практике вычисление по модулю выполняется во время суммирования для управления размером результата. Значение контрольной суммы передаётся вместе с сообщением, увеличивая его длину до 137 байтов или 1096 бит. Получатель сообщения может повторно вычислить контрольную сумму и сравнить её с полученным значением контрольной суммы, чтобы определить, было ли сообщение изменено в процессе передачи.

Слабые стороны простых контрольных сумм

Первая слабая сторона простой контрольной суммы состоит в том, что она нечувствительна к порядку блоков (байтов) в слове данных (сообщении). Если их порядок был изменён, значение контрольной суммы будет одинаковым, и изменение не будет обнаружено. Вторая слабая сторона заключается в том, что множество возможных значений контрольной суммы мало и равно выбранному модулю. В нашем примере имеется только 255 возможных значений контрольной суммы, поэтому легко видеть, что даже случайные данные имеют вероятность примерно 0,4% получения той же контрольной суммы, что и наше сообщение (см. Коллизия хеш-функции).

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

Флетчер исправил оба эти недостатка, вычисляя второе значение вместе с простой контрольной суммой. Это модульная сумма значений, полученных простой контрольной суммой, так как каждый блок слова данных добавляется к ней. Используемый модуль одинаковый. Таким образом, для каждого блока слова данных, взятого последовательно, значение блока добавляется к первой сумме, а новое значение первой суммы затем добавляется ко второй сумме. Обе суммы начинаются с ноля (или какого-либо другого заранее определённого значения). В конце слова данных применяется сложение по модулю, и два значения объединяются, формируя контрольную сумму Флетчера.

Чувствительность к порядку блоков вводится, потому что, как только блок добавляется к первой сумме, он затем повторно добавляется ко второй сумме вместе с каждым блоком до неё. Если, например, обменяться двумя соседними блоками, тот, который первоначально был первым, будет добавлен ко второй сумме один раз, а второй, который был первоначально вторым, будет добавлен ко второй сумме ещё раз. Окончательное значение первой суммы будет одинаковым, но вторая сумма будет отличаться, обнаружив изменение в сообщении.

Множество всех возможных значений контрольной суммы теперь является квадратом того же значения для простой контрольной суммы. В нашем примере две суммы, каждая из которых имеет 255 возможных значений, приводят к 65025 возможным значениям для комбинированной контрольной суммы.

Прямая реализация

Неэффективная, но простая реализация функции на языке C для вычисления контрольной суммы Fletcher-16 из массива 8-битных элементов данных:

 1 uint16_t Fletcher16( uint8_t *data, int count )
 2 {
 3    uint16_t sum1 = 0;
 4    uint16_t sum2 = 0;
 5    int index;
 6 
 7    for( index = 0; index < count; ++index )
 8    {
 9       sum1 = (sum1 + data[index]) % 255;
10       sum2 = (sum2 + sum1) % 255;
11    }
12 
13    return (sum2 << 8) | sum1;
14 }

В строках 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)