CRC32

[CityAceE]

Из документации по формату UDI:



ПРИЛОЖЕНИЕ 2

Алгоритм вычисления CRC32 для файла UDI


Начальное значение CRC = 0xFFFFFFFF (-1l).

Функция обновления CRC32 для одного байта Symbol:

long CalcCRC32(long CRC, unsigned char Symbol)
{
long temp;
CRC ^= -1l ^ Symbol;
for(int k = 8; k--;)
{ temp = -(CRC & 1), CRC >>= 1, CRC ^= 0xEDB88320ul & temp; }
CRC ^= -1l;
return CRC;
}

Эту функцию нужно вызвать для каждого байта из файла UDI (исключая последние
4 байта CRC).

Первый аргумент функции - текущая CRC, второй аргумент - байт данных,
результат - новая CRC.


Так вот вопрос, это стандартный алгоритм CRC32? Если стандартный, то есть ли его реализация для Z80? Если не стандатный, то всё равно требуется его реализация под Z80 :)

[valker]

Так вот вопрос, это стандартный алгоритм CRC32? Если стандартный, то есть ли его реализация для Z80? Если не стандатный, то всё равно требуется его реализация под Z80 :)

Могу IAR'ом скомпилить и выложить листинг. Устроит?

[caro]

Могу IAR'ом скомпилить и выложить листинг. Устроит?Давай, меня тоже интересует результат.
А потом попробуем оптимизировать на ASMе.

[valker]

Давай, меня тоже интересует результат.
А потом попробуем оптимизировать на ASMе.

К сожалению, IAR использовал встроенные библиотеки для работы с long-ами...



################################################## ############################
# #
# IAR Z80/64180 C-Compiler V4.06A/WIN #
# #
# Compile time = 23/Jan/2008 16:05:18 #
# Target option = Z80 #
# Memory model = large #
# Source file = d:\java\javaonzx\nextgen\crc.c #
# List file = d:\java\javaonzx\nextgen\debug\list\crc.lst #
# Object file = d:\java\javaonzx\nextgen\debug\obj\crc.r01 #
# ASM file = d:\java\javaonzx\nextgen\debug\list\crc.s01 #
# Command line = -v0 -ml -uua -OD:\java\javaonzx\NextGen\Debug\Obj\ #
# -e -K -w -g -s9 -RCODE -r0i #
# -LD:\java\javaonzx\NextGen\Debug\List\ -q -t8 -x #
# -AD:\java\javaonzx\NextGen\Debug\List\ -X #
# -IC:\zx\IAR\EW23\z80\inc\ #
# D:\java\javaonzx\NextGen\crc.c #
# #
# Copyright 2001 IAR Systems. All rights reserved. #
################################################## ############################

\ 0000 NAME crc(16)
\ 0000 RSEG CODE(0)
\ 0000 PUBLIC CalcCRC32
\ 0000 EXTERN ?CLZ80L_4_06_L00
\ 0000 EXTERN ?L_AND_L03
\ 0000 EXTERN ?L_NOT_L03
\ 0000 EXTERN ?L_NEG_L03
\ 0000 EXTERN ?L_XORASG_L03
\ 0000 EXTERN ?SL_RSHASG_L03
\ 0000 RSEG CODE
\ 0000 CalcCRC32:
1 //crc.c
2 //Алгоритм вычисления CRC32 для файла UDI
3 //Начальное значение CRC = 0xFFFFFFFF (-1l).
4 //Функция обновления CRC32 для одного байта Symbol:
5
6 long CalcCRC32(long CRC, unsigned char Symbol)
7 {
\ 0000 DDE5 PUSH IX
\ 0002 C5 PUSH BC
\ 0003 D5 PUSH DE
\ 0004 F5 PUSH AF
\ 0005 F5 PUSH AF
8 long temp;
9 int k;
10 CRC ^= -1l ^ Symbol;
\ 0006 210400 LD HL,4
\ 0009 39 ADD HL,SP
\ 000A E5 PUSH HL
\ 000B 210E00 LD HL,14
\ 000E 39 ADD HL,SP
\ 000F 6E LD L,(HL)
\ 0010 010000 LD BC,0
\ 0013 61 LD H,C
\ 0014 CD0000 CALL ?L_NOT_L03
\ 0017 EB EX DE,HL
\ 0018 E1 POP HL
\ 0019 CD0000 CALL ?L_XORASG_L03
11 for(k = 8; k--;)
\ 001C DD210800 LD IX,8
\ 0020 ?0001:
\ 0020 DDE5 PUSH IX
\ 0022 E1 POP HL
\ 0023 7D LD A,L
\ 0024 B4 OR H
\ 0025 210400 LD HL,4
\ 0028 39 ADD HL,SP
\ 0029 DD2B DEC IX
\ 002B 283F JR Z,?0000
\ 002D ?0002:
12 { temp = -(CRC & 1), CRC >>= 1, CRC ^= 0xEDB88320ul & temp; }
\ 002D 5E LD E,(HL)
\ 002E EB EX DE,HL
\ 002F 7D LD A,L
\ 0030 E601 AND 1
\ 0032 6F LD L,A
\ 0033 2600 LD H,0
\ 0035 4C LD C,H
\ 0036 41 LD B,C
\ 0037 CD0000 CALL ?L_NEG_L03
\ 003A E5 PUSH HL
\ 003B 210200 LD HL,2
\ 003E 39 ADD HL,SP
\ 003F D1 POP DE
\ 0040 73 LD (HL),E
\ 0041 23 INC HL
\ 0042 72 LD (HL),D
\ 0043 23 INC HL
\ 0044 71 LD (HL),C
\ 0045 23 INC HL
\ 0046 70 LD (HL),B
\ 0047 23 INC HL
\ 0048 3E01 LD A,1
\ 004A CD0000 CALL ?SL_RSHASG_L03
\ 004D E5 PUSH HL
\ 004E 01B8ED LD BC,60856
\ 0051 C5 PUSH BC
\ 0052 012083 LD BC,33568
\ 0055 C5 PUSH BC
\ 0056 210600 LD HL,6
\ 0059 39 ADD HL,SP
\ 005A 5E LD E,(HL)
\ 005B 23 INC HL
\ 005C 56 LD D,(HL)
\ 005D 23 INC HL
\ 005E 4E LD C,(HL)
\ 005F 23 INC HL
\ 0060 46 LD B,(HL)
\ 0061 EB EX DE,HL
\ 0062 CD0000 CALL ?L_AND_L03
\ 0065 EB EX DE,HL
\ 0066 E1 POP HL
\ 0067 CD0000 CALL ?L_XORASG_L03
\ 006A 18B4 JR ?0001
\ 006C ?0000:
13 CRC ^= -1l;
\ 006C 01FFFF LD BC,65535
\ 006F 59 LD E,C
\ 0070 50 LD D,B
\ 0071 CD0000 CALL ?L_XORASG_L03
14 return CRC;
\ 0074 5E LD E,(HL)
\ 0075 23 INC HL
\ 0076 56 LD D,(HL)
\ 0077 23 INC HL
\ 0078 4E LD C,(HL)
\ 0079 23 INC HL
\ 007A 46 LD B,(HL)
\ 007B EB EX DE,HL
15 }
\ 007C F1 POP AF
\ 007D F1 POP AF
\ 007E F1 POP AF
\ 007F F1 POP AF
\ 0080 DDE1 POP IX
\ 0082 C9 RET
\ 0083 END


S Y M B O L - T A B L E
=======================


#include file(s):

[ 1] d:\java\javaonzx\nextgen\debug\obj\crc.r01


Symbol Type Class Defline Refline(s)
------ ---- ----- ------- ----------

CalcCRC32 function public 7 7


Errors: none
Warnings: none
Code size: 131
Constant size: 0
Static variable size: Data(0) Iram(0)




Добавлено через 4 минуты



{ temp = -(CRC & 1), CRC >>= 1, CRC ^= 0xEDB88320ul & temp; }


Cмущает строка "-(CRC&1)", ведь из-за запятой её результат выражения никуда не сохраняется....

[CityAceE]

Cмущает строка "-(CRC&1)", ведь из-за запятой её результат выражения никуда не сохраняется....
Не знаю... Я процитировал документацию буква в букву..

[caro]

К сожалению, IAR использовал встроенные библиотеки для работы с long-ами...А как бы их развернуть.


Cмущает строка "-(CRC&1)", ведь из-за запятой её результат выражения никуда не сохраняется....Если компилятор ёё правильно интерпретировал, это не беда.

[736b]

http://www.cpcwiki.com/index.php/Programming:CRC32

[CityAceE]

http://www.cpcwiki.com/index.php/Programming:CRC32
Вот цитаты оттуда:

CRC32Init


CRC32Init:
;Inputs:
; A=0 -> Use 'default' Polynomial (the one used in the ZIP Format)
; A=1 -> Use custom Polynomial
; -> DEHL=Polynomial
;Outputs:
; ($8292)=Polynomial
; ($8296)=Current CRC (~($8296)=CRC32)
;Destroys:
; AF,DE,HL
or a
jr nz,$+08
ld de,$EDB8
ld hl,$8320
ld a,d
ld d,e
ld e,a
ld a,h
ld h,l
ld l,a
ld ($8292),de
ld ($8294),hl
ld hl,$FFFF
ld ($8296),hl
ld ($8298),hl
ret


CRC32Update


CRC32Update:
;Inputs:
; HL -> Points to data
; BC -> Number of bytes
;Outputs:
; ($8296) = Updated
;Destroys:
; AF,BC,DE,HL
ld a,b
or c
ret z
push hl
push bc
ld b,(hl)
call CRC32Update_Routine
pop bc
pop hl
inc hl
dec bc
jr CRC32Update
CRC32Update_OneByte:
;Inputs:
; A = Byte to add to CRC
;Destroys:
; AF,BC,DE,HL
ld b,a
CRC32Update_Routine:
ld a,($8296)
xor b
call CRC32TableLookup
ld a,($8297)
xor l
ld ($8296),a
ld a,($8298)
xor h
ld ($8297),a
ld a,($8299)
xor e
ld ($8298),a
ld a,d
ld ($8299),a
ret
CRC32TableLookup:
ld de,$0000
ld h,d
ld l,a
ld b,8
CRC32TableLookupLoop:
push bc
or a
rr d
rr e
rr h
rr l
jr nc,CRC32TableLookupLoopEnd
push hl
pop bc
ld hl,$8292
ld a,d
xor (hl)
inc hl
ld d,a
ld a,e
xor (hl)
inc hl
ld e,a
ld a,b
xor (hl)
inc hl
ld b,a
ld a,c
xor (hl)
ld c,a
push bc
pop hl
CRC32TableLookupLoopEnd:
pop bc
djnz CRC32TableLookupLoop
ret

CRC32Finalize


CRC32Finalize:
;Inputs:
; None
;Outputs:
; DEHL = CRC32
;Destroys:
; AF,BC,DE,HL
ld de,($8298)
ld bc,($8296)
ld hl,$FFFF
push hl
or a
sbc hl,bc
ex (sp),hl
sbc hl,de
ex de,hl
pop hl
ret


Получается, что эта процедура имеет три части: вначале её надо инициализировать, потом подсчитать, а потом финализировать. Но судя по всему, это не то, что описано в UDI, так как там всего одна процедура без всякой финализации...

[boo_boo]

Cмущает строка "-(CRC&1)", ведь из-за запятой её результат выражения никуда не сохраняется....
опечатка, видимо. в исходниках UnrealSpeccy там точка с запятой:
{ int temp = -(crc & 1); crc >>= 1, crc ^= 0xEDB88320 & temp; }

[Alexandr Medvedev]

Вот вам код из FAR плагинов:

void *buf = MapViewOfFile(handle, FILE_MAP_ALL_ACCESS, 0, 0, 0);

long CRC = 0xFFFFFFFF;
for(DWORD i = 0; i < fileSize; i++)
{
DWORD temp;
CRC ^= -1 ^ *(((unsigned char*)buf)+i);
for(BYTE k = 8; k--;)
{ temp = -(CRC & 1); CRC >>= 1; CRC ^= 0xEDB88320 & temp; }
CRC ^= -1;
}