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

Обоснование

Сумма Флетчера - это остаток от деления интерпретируемого как длинное число потока данных на 255. Остаток от деления на 2ⁿ получить просто (достаточно взять n младших бит в двоичной системе счисления), остаток же от деления на (2ⁿ)-1 получить сложнее. Ниже дано обоснование этого процесса:

G % D = (xn*Bn + ... + x1*B + x0) % D
= (xn*(...)*D + xn + ... + x1*D + x1 + x0) % D
= ((...)*D % D + (xn + ... + x1 + x0) % D) % D
= (xn + ... + x1 + x0) % D

Здесь D - это делитель, а G - поток данных, интерпретируемый как полином или как число в позиционной системе счисления с постоянным основанием B=D+1. Для суммы Флетчера D=2⁸-1=255 и B=2⁸=256. "%" - операция получения остатка от деления. Использованы следующие соотношения:

1. (D+1)n = Dn + ... + D + 1 = (...)*D + 1
2. (a + b) % d = (a % d + b % d) % d

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

Как факт: вычисление суммы Флетчера аналогично проверке делимости числа на 9, для чего суммируются все десятичные цифры числа и промежуточных сумм до тех пор, пока итог не станет меньше 10. Соответственно, число делится на 9 тогда и только тогда, когда итог равен 0 или 9.

Как оптимизацию отметим: сумму можно сокращать до окончания суммирования всех байт - например, байты суммы можно сложить сразу, как только сумма станет больше B:

(xn + ... + x1 + x0) % D
= (S + xk + ...) % D
= (S % D + (xk + ...) % D) % D
= ((sm*Bn + ... + s0) % D + (xk + ...) % D) % D
...
= ((sm + ... + s0) % D + (xk + ...) % D) % D
= (sm + ... + s0 + xk + ...) % D

Отсюда следует, что промежуточные суммы можно сокращать просто складывая их байты, а в силу коммутативности операции сложения байты промежуточных сумм и исходные байты можно перемешивать. Более того, для сокращения достаточно отделять от промежуточных сумм некоторые байты, не разбивая суммы на байты целиком.

Всё вышеизложенное упрощённо можно выразить на псевдокоде следующим образом:

сумма :два_байта := 0;
цикл знак :байт := следующий_знак_потока;
если знак не получен то прервать_цикл;
сумма += знак;
если сумма ≥ B то сумма -= B - 1;
конец_цикла;
если сумма = D то сумма := 0;

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

Данный пример не оптимален в двух аспектах. Во-первых, из-за минимального максимума для суммы её сокращение может происходить на каждой итерации, хотя здесь сумма может вместить больше значений. Заметьте: вместо "≥B" (или, что то же самое, ">D") данный метод сокращения (вместо сложения байт вычитание B с добавлением переноса) допускает условием сокращения более сильное условие "≥D", при этом надобность в итоговом сокращении отпадёт автоматически. Но это даст уже другой алгоритм, в котором остаток от деления на D суммы байт вычисляется последовательным взятием остатка от промежуточных сумм, а не сложением байт (коэффициентов) сумм.

Во-вторых, можно уменьшить среднее количество операций на байт, отрабатывая более крупные объекты. Легко доказать, что остаток от деления на D полинома, в котором коэффициенты сгруппированы парами, тройками или более, равен остатку от деления на D суммы этих групп:

G % D = (... + x3*B3 + x2*B2 + x1*B + x0) % D
= (... + (x3*B + x2)*B2 + (x1*B + x0)) % D
= (... + (x3*B + x2) + (x1*B + x0)) % D

Это означает, что поток можно разбить не только на байты, но и более крупные объекты (например, слова) - для получения остатка достаточно будет сократить сумму этих объектов. Причём, как и ранее, сумму можно сокращать до окончания суммирования объектов. Если же длина потока в байтах будет не кратна длине объектов, то поток можно явно или неявно дополнять с любой стороны нулевыми байтами или отработать остаток потока побайтно.

Как факт: описанные методы годятся не только для вычисления суммы Флетчера. Аналогично можно вычислять, например, остаток от деления на 3. Для этого достаточно просуммировать все пары бит и кратные парам группы (например, 8-битные байты), пока итог не станет меньше 4.