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

Контрольна сума Флетчера — алгоритм обчислення контрольної суми, який наприкінці 1970-х років розробив Джон Флетчер (1934—2012) із Лабораторії Лоуренса Лівермора.^[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-32

Контрольна сума Adler-32 є видозміною контрольної суми Fletcher-32, яку розробив Марк Адлер. Вибраний модуль (для обох сум) дорівнює простому числу 65521 (65535 ділиться на 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 біт. Після опрацювання всіх даних, у рядку 13 дві суми об'єднуються в 16-бітове значення контрольної суми Флетчера, яке й повертає функція.

Кожна сума обчислюється за модулем 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)