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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:52, 9 августа 2015.

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

;----------------------------------------------------------------------
;prg09_05.asm - программа вычисления CRC-таблицы для полинома 04c11db7.
;----------------------------------------------------------------------
.data
;CRC32-таблица для прямого табличного алгоритма вычисления 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	04c11db7h
.code
	;...
	les	di,adr_tabl_32_direct
	add	di,len_tabl_32_direct-4
	std	;идем назад по таблице
	mov	cx,255
	mov	ebx,polinom
m1:
	xor	eax,eax
	shrd	eax,ecx,8
	push	cx	;вложенные циклы
	mov	cx,8
m2:	shl	eax,1
	jnc	m3	;старшие разряды не равны - выполняем сдвиг (частное нас не интересует)
;старшие разряды равны - выполняем XOR:
	xor	eax,ebx	;ax XOR polinom
m3:	loop	m2
	pop	cx
	stosd
	loop	m1
	;...

Прямой табличный алгоритм CRC32 удобно рассматривать со стороны участников процесса, как это мы делали выше. Источник выполняет следующие действия.

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

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

;-------------------------------------------------------------------------
;prg09_06.asm - программа вычисления CRC32 по прямому табличному алгоритму.
;-------------------------------------------------------------------------

;исходная битовая последовательность в символах
bit_string	db	"123456789"
	len_bit_string=$-bit_string
crc_32	dd	0	;сюда мы поместим рассчитанное значение CRC32
adr_bit_string	dd	bit_string
;CRC32-таблица для прямого табличного алгоритма вычисления 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	04c11db7h
.code
	;...
;-------------расчитываем CRC-32 таблицу
	les	di,adr_tabl_32_direct
	add	di,len_tabl_32_direct-4
	std	;идем назад по таблице
	mov	cx,255
	mov	ebx,polinom
m1:
	xor	eax,eax
	shrd	eax,ecx,8
	push	cx	;вложенные циклы
	mov	cx,8
m2:	shl	eax,1
	jnc	m3	;старшие разряды не равны - выполняем сдвиг (частное нас не интересует)
;старшие разряды равны - выполняем XOR:
	xor	eax,ebx	;ax XOR polinom
m3:	loop	m2
	pop	cx
	stosd
	loop	m1
;-------------закончили расчет CRC-32 таблицы----------------------------
	mov	eax, 0FFFFFFFFh
	lds	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
	loop	m4
;запишем crc-32 в конец (или начало, см. обсуждение ниже) последовательности:
	xor	eax, 0FFFFFFFFh
	mov	crc_32,eax	;добавляем в конец исходной последовательности
	;...

Значение CRC32 для строки "123456789" равно 9c970409h.

Если для источника стандарт определяет практически однозначную последовательность действий, то для приемника возможны несколько вариантов поведения. Отметим два из них.

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

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

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

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

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

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

;------------------------------------------------------------------------------------------
;prg09_07.asm - программа демонстрирующая действия приемника табличного алгоритма CRC32 при
;анализе поступившего сообщения.
;------------------------------------------------------------------------------------------
.data
;полученная битовая последовательность в символах
bit_string	db	"123456789"
	len_bit_string=$-bit_string
crc_32	dd	9c970409h	;значение CRC32, рассчитанное источником для данной исходной последовательности
adr_bit_string	dd	bit_string
;CRC32-таблица для прямого табличного алгоритма вычисления 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	04c11db7h
.code
              ;...
;-------------расчитываем CRC32-таблицу---------------------------------
	les	di,adr_tabl_32_direct
	add	di,len_tabl_32_direct-4
	std	;идем назад по таблице
	mov	cx,255
	mov	ebx,polinom
m1:
	xor	eax,eax
	shrd	eax,ecx,8
	push	cx	;вложенные циклы
	mov	cx,8
m2:	shl	eax,1
	jnc	m3	;старшие разряды не равны - выполняем сдвиг (частное нас не интересует)
;старшие разряды равны - выполняем XOR:
	xor	eax,ebx	;ax XOR polinom
m3:	loop	m2
	pop	cx
	stosd
	loop	m1
;-------------закончили расчет CRC32-таблицы----------------------------
	mov	eax, 0FFFFFFFFh
	lds	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
	loop	m4
	xor	eax, 0FFFFFFFFh
;если исходная последовательность цела, то должно получиться значение crc32=9c970409h
;его можно сравнить исходным и на этом закончить работу или продолжить до победного, то есть до 0:
	mov	cx,4	; 4 (длина crc_32)
 si адрес crc_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
	;...		;должен быть 0

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

Рис. 1. Схема вычислений CRC с использованием прямого табличного алгоритма