Правильность алгоритма контрольной суммы Fletcher32

Question

Мне сложно определить, какая реализация 32-битного изменения Fletcher checksum algorithm верна. Википедия предоставляет следующую оптимизированную реализацию:

uint32_t fletcher32(uint16_t const *data, size_t words) { 
     uint32_t sum1 = 0xffff, sum2 = 0xffff; 
     size_t tlen; 

     while (words) { 
       tlen = words >= 359 ? 359 : words; 
       words -= tlen; 
       do { 
         sum2 += sum1 += *data++; 
       } while (--tlen); 
       sum1 = (sum1 & 0xffff) + (sum1 >> 16); 
       sum2 = (sum2 & 0xffff) + (sum2 >> 16); 
     } 
     /* Second reduction step to reduce sums to 16 bits */ 
     sum1 = (sum1 & 0xffff) + (sum1 >> 16); 
     sum2 = (sum2 & 0xffff) + (sum2 >> 16); 
     return sum2 << 16 | sum1; 
} 

Кроме того, я адаптированный неоптимизированный 16-битный пример из статьи Википедии, чтобы вычислить 32-битную контрольные:

uint32_t naive_fletcher32(uint16_t *data, int words) { 
    uint32_t sum1 = 0; 
    uint32_t sum2 = 0; 

    int index; 
    for(index = 0; index < words; ++index) { 
     sum1 = (sum1 + data[index]) % 0xffff; 
     sum2 = (sum2 + sum1) % 0xffff; 
    } 
    return (sum2 << 16) | sum1; 
} 

Оба эти реализации дают одинаковые результаты, например 0x56502d2a для строки abcdef. Для того, чтобы убедиться, что это действительно правильно, я попытался найти другие реализации алгоритма:

• An online checksum/hash generator
• C++ implementation in the srecord project
• There's also a JavaScript implementation

Все они, похоже, согласны, что контрольная сумма для abcdef0x8180255 вместо значения, данного реализацией в Википедии. Я сузил это до того, как работает буфер данных, на котором выполняется реализация. Во всех вышеупомянутых реализациях, отличных от wikipedia, действует один байт за раз, тогда как реализация Wikipedia вычисляет контрольную сумму с использованием 16-битных слов. Если бы я изменить выше «наивную» реализацию Википедии для работы в байтах вместо этого, он читает так:

uint32_t naive_fletcher32_per_byte(uint8_t *data, int words) { 
    uint32_t sum1 = 0; 
    uint32_t sum2 = 0; 

    int index; 
    for(index = 0; index < words; ++index) { 
     sum1 = (sum1 + data[index]) % 0xffff; 
     sum2 = (sum2 + sum1) % 0xffff; 
    } 
    return (sum2 << 16) | sum1; 
} 

Единственное, что меняется, так это подпись, на самом деле. Таким образом, эта измененная наивная реализация и вышеупомянутые реализации (кроме Википедии) согласны с тем, что контрольная сумма abcdef действительно равна 0x8180255.

Моя проблема сейчас: какой из них правильный?

Answer 1

Согласно standard, правильный метод является один, что Википедия предоставляет - кроме названия:

Обратите внимание, что 8-битный Fletcher алгоритм дает 16-битовую контрольную сумму и алгоритм 16-бит дает 32-битная контрольная сумма.

Answer 2

В standard процитированном в ответе HideFromKGB, алгоритм тривиально: 8-разрядная версия использует только 8 бит аккумуляторов («INTS»), производя 8 бит результаты А и В, а также 16-битный версия использует 16-битные «ints», производя 16-битные результаты A и B.

Следует отметить, что то, что Wikipedia вызывает «32-битный Fletcher», на самом деле является «16-битным Fletcher». Количество бит в имени относится к стандарту к числу бит в каждом D [i] и в каждом из A и B, но в Википедии оно относится к числу бит в «суммированном результате», то есть в A<<16 | B для 32-битного результата.

Я не реализовал это, но, возможно, это может объяснить разницу. Я склонен сказать, что ваша интерпретация (реализация) верна.

N.b .: Также обратите внимание, что необходимо надеть data с нулями на соответствующее количество байтов.

Answer 3

Эти test vectors, которые являются кросс проверяются с двумя различными реализациями для 16-битных и для 32-битных контрольных сумм:

8-bit implementation (16-bit checksum) 
"abcde" -> 51440 (0xC8F0) 
"abcdef" -> 8279 (0x2057) 
"abcdefgh" -> 1575 (0x0627) 

16-bit implementation (32-bit checksum) 
"abcde" -> 4031760169 (0xF04FC729) 
"abcdef" -> 1448095018 (0x56502D2A) 
"abcdefgh" -> 3957429649 (0xEBE19591) 

Answer 4

Опции

TCP Альтернативные контрольной суммы описывает алгоритм контрольной суммы Fletcher для использования с TCP: RFC 1146 от марта 1990 года.

Обсуждается 8-битный алгоритм Флетчера, который дает 16-разрядную контрольную сумму и 16-разрядный алгоритм, который дает 32-разрядную контрольную сумму.

8-разрядный Флетчер Контрольная сумма Алгоритм вычисляется по последовательности октетов данных (назовем их D [1] через D [N]), поддерживая 2 беззнаковых 1's-дополнение 8-битовое аккумуляторы А и В, содержание которого являются изначально равна нулю, и выполнение следующий цикл, где я колеблется от 1 до N:

 A := A + D[i] 
     B := B + A 

16-битного Флетчер Checksum алгоритм переходит в точно такой же образом, как алгоритм контрольной суммы в 8-битном, за исключением того, что A, B и D [i]: 16-разрядные величины. Необходимо (как и для стандартного алгоритма контрольной суммы TCP для) для размещения дейтаграммы, содержащей нечетное число октетов 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Это согласуется с алгоритмами Wikipedia. Простая программа тестирования подтверждает цитировал результаты:

#include <stdio.h> 
    #include <string.h> 
    #include <stdint.h> // for uint32_t 

    uint32_t fletcher32_1(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); 
    } 

    uint32_t fletcher32_2(const uint16_t *data, size_t l) 
    { 
     uint32_t sum1 = 0xffff, sum2 = 0xffff; 

     while (l) { 
      unsigned tlen = l > 359 ? 359 : l; 
      l -= tlen; 
      do { 
       sum2 += sum1 += *data++; 
      } while (--tlen); 
      sum1 = (sum1 & 0xffff) + (sum1 >> 16); 
      sum2 = (sum2 & 0xffff) + (sum2 >> 16); 
     } 
     /* Second reduction step to reduce sums to 16 bits */ 
     sum1 = (sum1 & 0xffff) + (sum1 >> 16); 
     sum2 = (sum2 & 0xffff) + (sum2 >> 16); 
     return (sum2 << 16) | sum1; 
    } 

    int main() 
    { 
     char *str1 = "abcde"; 
     char *str2 = "abcdef"; 

     size_t len1 = (strlen(str1)+1)/2; // '\0' will be used for padding 
     size_t len2 = (strlen(str2)+1)/2; // 

     uint32_t f1 = fletcher32_1(str1, len1); 
     uint32_t f2 = fletcher32_2(str1, len1); 

     printf("%u %X \n", f1,f1); 
     printf("%u %X \n\n", f2,f2); 

     f1 = fletcher32_1(str2, len2); 
     f2 = fletcher32_2(str2, len2); 

     printf("%u %X \n",f1,f1); 
     printf("%u %X \n",f2,f2); 

     return 0; 
    } 

Выход:

4031760169 F04FC729                                                        
4031760169 F04FC729                                                        

1448095018 56502D2A                                                        
1448095018 56502D2A