Информация


Programm.ws - это сайт, на котором вы можете почитать литературу по языкам программирования, а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..

Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.

Глава 9. Вычисление CRC

Прямой табличный алгоритм CRC32

Как и любой табличный алгоритм, табличный алгоритм вычисления CRC32 требует задания CRC-таблицы. Ее можно задать в програм'ме статически, явно прописав значения элементов таблицы в сегменте кода, или динамически, вычислив значения элементов таблицы перед началом расчета CRC. Ниже приведена программа вычисления CRC-таблицы для полинома 04clldb7.
Прямой табличный алгоритм CRC32 удобно рассматривать со стороны участников процесса, как это мы делали выше. Источник выполняет следующие действия.

:prgO9_O5.asm - программа вычисления CRC-таблицы для полинома 04clldb7.
.data
;С1<С32-таблица для прямого табличного алгоритма вычисления CRC32
tabl_32_direct dd 256 dup (0)
len_tabl_32_direct =$-tabl_32_direct
adr_tabl_32_direct dd tabl_32_direct
polinom dd 04clldb7h
.code
les di.adr_tabl_32_direct
add di,len_tabl_32_direct-4
std :идем назад по таблице
mov ex,255
mov ebx.polinom /
ml: xor eax.eax
shrd eax.ecx,8
push ex сложенные циклы
mov ex.8 m2: shl eax.l
jnc m3 :старшие разряды неравны - выполняем сдвиг (частное нас не интересует)
;старшйе разряды равны - выполняем XOR:
xor eax.ebx :ax XOR polinom
шЗ:loop m2
pop ex

  1. 1. Делает начальную установку регистра, в котором будет производиться формирование CRC, значением OFFFFFFFFh.
    2. Вычисляет значение CRC для каждого байта исходной последовательности, принцип которой показан на схеме (см. рис. 9.9). Читатель понимает, что хотя эта схема иллюстрирует принцип вычисления CRC16, но для 32-разрядного алгоритма нужно только увеличить размер элементов таблицы до 32 бит и задействовать весь регистр ЕАХ.
    3. Объединяет по XOR итоговое значение в ЕАХ со значением OFFFFFFFFh.
    4. Добавляет вычисленное значение в конец двоичной исходной последовательности. После этого его можно передать по назначению.

Ниже приведена программа вычисления CRC32 по прямому табличному алгоритму.

;prg09_06.asm - программа вычисления CRC32 по прямому табличному алгоритму.
исходная битовая последовательность в символах
bit_string db "123456789"
len_bit_string=$-bit_string
сгс_32 dd 0 ;сюда мы поместим рассчитанное значение CRC32
adr_bit_string dd bit_string
;СЯС32-таблица для прямого табличного алгоритма вычисления CRC32
tabl_32_direct dd 256 dup (0)
len_tabl_32_direct =$-tabl_32_direct
adr_tabl_32_direct dd tabl_32_direct
polinom dd 04clldb7h
.code
:----.........расчитываем CRC32 таблицу
les di.adr_tabl_32_direct
add di.len_tabl_32_direct-4 * std ;идем назад по таблице
mov ex.255
mov ebx, polinom
ml: xor eax.eax
shrd eax.ecx.8
push ex сложенные циклы
mov ex.8
m2: shl eax.l
jnc m3 :старшие разряды неравны - выполняем сдвиг (частное нас не интересует)
:старшие разряды равны - выполняем XOR:
xor eax.ebx :ax XOR polinom
m3: loop m2
pop ex
stosd
loop ml
:.....--......закончили расчет CRC32 таблицы
mov eax, OFFFFFFFFh
Ids si.adr_bit_string
mov cx.len_bit_string
m4: xor ebx.ebx
shld ebx.eax.8
shl eax.8
xor bl.[si]
xor eax. tabl_32_direct[bx]
inc si
1 oop m4 :запишем crc-32 в конец (или начало, см. обсуждение ниже) последовательности:
xor eax. OFFFFFFFFh
mov crc_32.eax ;добавляем в конец исходной последовательности

Значение CRC32 для строки "123456789" равно 9c970409h.
Если для источника стандарт определяет практически однозначную последовательность действий, то для приемника возможны несколько вариантов поведения. Отметим два из них.
В первом варианте критерием для вывода о целостности полученного приемником сообщения является результат сравнения или нулевой результат.

  1. 1. Выполнить начальную установку регистра, в котором будет производиться формирование значения CRC.
    2. Вычислить значение CRC для каждого байта полученной последовательности, принцип которой показан на схеме (см. рис. 9.9 и замечания выше о различиях CRC16 и CRC32).
    3. Объединить по XOR итоговое значение в ЕАХ со значением OFFFFFFFFh.
    4. Далее можно сделать одно из двух действий:
    1. сравнить значение в ЕАХ со значением CRC, полученным вместе с сообщением, — если они равны, то полученное сообщение идентично исходному;
    2. пропустить байты со значением CRC через процесс получения CRC наравне с другими байтами — об успехе будет свидетельствовать нулевое значение (этот вариант предпочтительнее, так как не предполагает получение предварительных сведений о длине начальной последовательности без учета исходного значения CRC).

Во втором варианте критерием для вывода о целостности полученного приемником сообщения является фиксированная двоичная константа 6b202ca2h.

  1. 1. Выполнить начальную установку регистра, в котором будет производиться формирование CRC, в значение OFFFFFFFFh;
    2. Вычислить значение CRC32 для каждого байта полученной последовательности (вместе со значением CRC32 в конце), принцип которой показан на схеме (см. рис. 9.9 и замечания выше о различиях CRC16 и CRC32). Должно получиться фиксированное двоичное значение — 6b202ca2h. Необ ходимо заметить, что в литературе можно встретить другое значение — 0debb20e3h, но у автора получалось первое.

Основное отличие этих двух вариантов в том, что нужно каким-то образом отделять контролируемую строку и ее значение CRC32. Избежать прямого отслеживания длины принимаемой строки на стороне приемника можно путем формирования источником значения CRC32 в начале исходной строки либо вообще вне строки. Последний случай, например, характерен для программы, которая отслеживает целостность файлов в некотором каталоге. Тогда результаты подсчета CRC для каждого файла хранятся в некотором служебном файле. Если такой вариант вас не устраивает, тогда следует написать код приемника для прямого табличного алгоритма так, как это сделано для приемника в зеркальном табличном алгоритме. Попробуйте самостоятельно определить константу, соответствующую успешному принятию приемником исходной строки.
Учитывая практическую важность обоих вариантов и для демонстрации разнообразия подходов к проблеме вычисления CRC32, работу приемника для прямого табличного алгоритма продемонстрируем на примере первого варианта, приемник «зеркального» табличного алгоритма CRC32 разработаем исходя из положений второго варианта. Но вы должны понимать, что правильное понимание принципов расчета CRC позволяет вам при соответствующей доработке кода поменять варианты работы приемников. В поле сгс_32 должно быть значение CRC32, рассчитанное предыдущей программой. Автор специально не стал объединять эти программы. Пусть это сделает читатель в нужном для его текущей работы контексте.

;prg09_06.asm - программа вычисления CRC32 по прямому табличному алгоритму.
исходная битовая последовательность в символах
bit_string db "123456789"
len_bit_string=$-bit_string
сгс_32 dd 0 ;сюда мы поместим рассчитанное значение CRC32
adr_bit_string dd bit_string
;СЯС32-таблица для прямого табличного алгоритма вычисления CRC32
tabl_32_direct dd 256 dup (0)
len_tabl_32_direct =$-tabl_32_direct
adr_tabl_32_direct dd tabl_32_direct
polinom dd 04clldb7h
.code
:----.........расчитываем CRC32 таблицу
les di.adr_tabl_32_direct
add di.len_tabl_32_direct-4 * std ;идем назад по таблице
mov ex.255
mov ebx, polinom
ml: xor eax.eax
shrd eax.ecx.8
push ex сложенные циклы
mov ex.8
m2: shl eax.l
jnc m3 :старшие разряды неравны - выполняем сдвиг (частное нас не интересует)
:старшие разряды равны - выполняем XOR:
xor eax.ebx :ax XOR polinom
m3: loop m2
pop ex
push ex сложенные циклы
mov ex,8 m2: shl eax.l
jnc m3 ;старшие разряды не равны - выполняем сдвиг (частное нас не интересует) :старшие разряды равны - выполняем XOR:
хог eax.ebx:ax XOR polinom m3: loop m2
pop сх
stosd
loop ml : закончили расчет СРО2-таблицы
mov eax. OFFFFFFFFh
Ids si,adr_bit_string
mov cx,len_bit_string m4: xor ebx.ebx
shld ebx.eax,8
shl eax.8
xor bl.[si]
xor eax. tabl_32_direct[bx]
inc si
1 oop m4
xor eax. OFFFFFFFFh
;если исходная последовательность цела, то должно получиться значение crc32=9c970409h ;его можно сравнить с исходным и на этом закончить работу или продолжить до победного. :то есть до 0:
mov ex.4 : 4 (длина сгс_32) :в si адрес сгс_32
mov ebx.crc_32
bswap ebx
mov crc_32.ebx m5: xor ebx.ebx
shld ebx.eax.8
shl eax.8
xor bl.[si]
xor eax. tabl_32_direct[bx]
inc si
loop m5 :должен быть О

Заметьте, что для получения нулевого результата нам пришлось использовать команду BSWAP, чтобы «перевернуть» "значение в поле сгс_32.