Контрольные суммы: сумма Флетчера
Страница 2. Сокращение суммы Флетчера

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

Для сокращения сумма разбивается на байты и кратные байтам объекты, которые и суммируются. В случае если значение некоторых слагаемых известно заранее, то сокращение можно выразить упрощённой формулой вида 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: