АЛГОРИТМЫ
Новости
Рассылка новостей
Форум
AlgoPascal
Редактор блок-схем
Статьи
О сайте
Контакты
Контрольные суммы: сумма Флетчера
Автор: Белоусов Аркадий, 2001 г.
Введение
Циклические избыточные коды (CRC) - популярный метод построения контрольных сумм, служащих для обнаружения и исправления ошибок при передаче и хранении данных. Широкое распространение получили алгоритмы вычисления CRC16 и CRC32. Однако для получения контрольных сумм можно использовать и другие алгоритмы. Например, очень простой, короткий и быстрый алгоритм - сумму Флетчера.
Обоснование
Сумма Флетчера - это остаток от деления интерпретируемого как длинное число потока данных на 255. Остаток от деления на 2n получить просто (достаточно взять n младших бит в двоичной системе счисления), остаток же от деления на (2n)-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=28-1=255 и B=28=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*Bm-k. Здесь k - значение старшего слагаемого, m - количество байт в младшем слагаемом. В псевдокоде выше при сокращении старший байт равен единице, т.е. k=m=1.
Сокращать промежуточную сумму следует при её переполнении, когда сумма S после добавления очередного аргумента R превысит максимальное значение M. При суммировании байт M должно быть больше или равно 28-1=255, для слов планка равна 216-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)=216-28.
В-третьих, в языках с модульной арифметикой (при которой переполнение в целочисленных операциях не вызывает ошибку, а возвращает значение числа по некоторому модулю - т.е. при добавлении единицы к максимальному числу получится ноль) можно сравнивать 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. Но, тем не менее, эти примеры закончены и готовы к применению в реальных программах.
Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU