Каталог статей

Введение

Циклические избыточные коды (CRC) - популярный метод построения контрольных сумм, служащих для обнаружения и исправления ошибок при передаче и хранении данных. Широкое распространение получили алгоритмы вычисления CRC16 и CRC32. Однако для получения контрольных сумм можно использовать и другие алгоритмы. Например, очень простой, короткий и быстрый алгоритм - сумму Флетчера.

Обоснование

Сумма Флетчера - это остаток от деления интерпретируемого как длинное число потока данных на 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.

Сокращение суммы и работа с переполнением

Для сокращения сумма разбивается на байты и кратные байтам объекты, которые и суммируются. В случае если значение некоторых слагаемых известно заранее, то сокращение можно выразить упрощённой формулой вида S-=k*B^m-k. Здесь k - значение старшего слагаемого, m - количество байт в младшем слагаемом. В псевдокоде выше при сокращении старший байт равен единице, т.е. k=m=1.

Сокращать промежуточную сумму следует при её переполнении, когда сумма S после добавления очередного аргумента R превысит максимальное значение M. При суммировании байт M должно быть больше или равно 2⁸-1=255, для слов планка равна 2¹⁶-1. Имеется 4 способа выполнить проверку переполнения.

Во-первых, можно перед сложением проверить условие S>M-R. Этот способ самый неэффективный, хотя и реализуем в любом языке, поскольку переполнение здесь предотвращается до своего возникновения. Если M минимально и равно B-1, как в псевдокоде выше, то суммирование, с учётом упрощённой формулы сокращения, может выглядеть так:

 если S < B-R то
 S += R;
 иначе S -= B-1-R;

Заметьте: здесь не допускается не только переполнение, но и возникновение чисел со знаком. Невнимание к подобным аспектам приводит к программам, не работающим вообще или работающим неправильно (причём не всегда). Например, если разрядность S равна разрядности B, то в языке с проверкой диапазонов добавление R к S перед проверкой "S<B" может вызвать генерацию ошибки, а в языках с модульной арифметикой при условии одинаковой разрядности проверка "S+R<B" всегда истинна (даже если B-S меньше R). Аналогично, на некоторых платформах и языках попытка вычесть B-1 из S независимо от добавления R также может привести к неверному результату или даже генерации ошибки.

Во-вторых, если S может вместить сумму M и любого R, то сравнивать S с M можно уже после добавления R к S, как это сделано в псевдокоде выше. Этот способ также реализуем в любом языке, однако максимум для M здесь меньше, чем для других способов, поэтому сокращений может быть больше. Заметьте: в псевдокоде M равно B-1, что позволяет свести сокращение суммы (в цикле и после цикла) к вычитанию B-1 вместо сложения байт суммы, но сокращений можно не делать пока S≤max(S)-max(R)=2¹⁶-2⁸.

В-третьих, в языках с модульной арифметикой (при которой переполнение в целочисленных операциях не вызывает ошибку, а возвращает значение числа по некоторому модулю - т.е. при добавлении единицы к максимальному числу получится ноль) можно сравнивать S с R после добавления R. Легко доказать, что если S<W, R<W и W<(S+R), то (S+R)%W<R. Т.е., когда S станет меньше R, следует просто учесть единицу переноса. При этом подразумевается, что M равно максимальному значению S, разрядность которого должна быть кратна разрядности B. На языке C это может выглядеть следующим образом:

 S += R; if(S < R) S++;

Последний способ является переложением третьего способа на машинные языки (и ассемблеры). В этих языках инструкции обычно меняют значение флагов, описывающих результаты действия инструкций. Инструкции сложения, среди прочих, обычно меняют "флаг переноса", который позволяет отказаться от сравнений S с R. Для процессоров Intel x86 это может выглядеть так:

 add S,R ; S += R
 jnc skip ; перейти, если нет переноса...
 inc S ; ...иначе скорректировать сумму
 skip:

Реализация

Ниже даны функции вычисления суммы Флетчера на языке C и на ассемблере для процессоров Intel x86. Функция на C вычисляет сумму побайтно, функция на ассемблере вычисляет сумму блоками по два байта. Момент переполнения определяется по третьему и четвёртому способам соответственно.

 typedef unsigned char byte;
 byte FletchSum(byte *buf, size_t len){
 byte S = 0;
 for(; len > 0; len--){
 byte R = *buf++;
 S += R; if(S < R) S++;
 }
 /*if(S = 255) S = 0;*/
 return S;
 }

Функция на ассемблере работает только с буферами, длина которых не нулевая и кратна 2. На входе адрес буфера в DS:SI, длина буфера в CX. На выходе значение суммы в DL.

 shr cx,1 ; CX=CX/2 - преобразовать к счётчику слов
 xor dx,dx ; DX=0, также сбросить флаг переноса
 do: lodsw ; AX=[DS:SI], SI+=2
 adc dx,ax ; добавить с учётом предыдущего переноса
 loop do ; CX--; jnz do
 adc dl,dh ; сократить сумму: от модуля 0FFFFh...
 ; ...перейти к модулю 0FFh
 ;adc dl,1 ; если сумма==255 то сумма=0
 adc dl,0
 ;dec dl

Пример реализации суммирования на C не оптимизирован для сложения блоками более чем байты, а пример на ассемблере не отрабатывает буфера с нулевой длиной или длиной, не кратной 2. Но, тем не менее, эти примеры закончены и готовы к применению в реальных программах.