Оригинальный DVD-ROM: eXeL@B DVD !
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
выпущен 2 сентября!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

ПРОГРАММИРОВАНИЕ НА C и С++



Программисты долго мучаются с кодом прогаммы, изучают С++, WinAPI функции, MSDN. Потом пишут банальную систему защиты или навешивают банальный протектор, а крэкеры и реверсеры справляются с такой защитой за 5 минут. В итоге, продажи программы почти нулевые. Чтобы такого не допустить, тут самому надо немного поднабрать опыта отладки, реверсинга, тот же отладчик Ollydbg изучить или дизассемблер IDA Pro. Но где искать по крохам эти знания? Нет, конечно можно годами "методом тыка" разбираться, но куда быстрее видеокурс специальный посмотреть. Вот тут он есть: ссылка. Автор курса с большим опытом и объясняет понятно, я из этого курса много узнал про то как работает компьютер, процессор, про инструменты специальные и как с ними работать. Мои коллеги программисты на работе ничего такого и не знают, теперь я им нос утру.

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

Автор: Белоусов Аркадий, 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. Но, тем не менее, эти примеры закончены и готовы к применению в реальных программах.



<< ВЕРНУТЬСЯ В ПОДРАЗДЕЛ

<< ВЕРНУТЬСЯ В ОГЛАВЛЕНИЕ




Материалы находятся на сайте https://exelab.ru/pro/



Оригинальный DVD-ROM: eXeL@B DVD !


Вы находитесь на EXELAB.rU
Проект ReactOS