PKZIP CRC32, how to calculate

[Frank Westlake]

I'm having difficulty finding the right CRC32 algorithms which are used
by the various ZIP programs to calculate a CRC that they will each agree
is correct. There are two aspects of this difficulty: one is that there
are several algorithms which claim to be used by PKZIP, the second is
that one of those I've tried might be right but that I've coded it
incorrectly, and the third (huh?) is that there are two routines which
must be correctly coded to get the correct result.

If any of you wish the challenge please search for the algorithms on the
Internet and try it in the test script below.

It seems to me that the most promising algorithms are those in the files
"crc32.c" and "crc32.h" from:

64-bit <ftp://ftp.info-zip.org/pub/infozip/win32/zip300xn-x64.zip>
32-bit <ftp://ftp.info-zip.org/pub/infozip/win32/zip300xn.zip>

Those are the two I have below (in :setTable and :getCRC32) and they
obviously fail, which might be because of my coding.

The test script writes a short file and uses CERTUTIL to get a hex dump,
which is used to calculate the value of each byte. I have stored this
file (not the hex dump) with ZIP and UNZIP reports a CRC of 0xa8a9215b,
which is -1465310885. So the goal is to get this script to calculate
"-1465310885" from the test file.

Thank you,

Frank


:: BEGIN SCRIPT :::::::::::::::::::::::::::::::::::::::::::::::::::::
:: REQUIRES CERTUTIL.exe

@Echo OFF
SetLocal EnableExtensions EnableDelayedExpansion
Set "fileText=%TEMP%\crc32.txt"
Set "fileHex=%TEMP%\crc32.hex"

Echo;How now brown cow? >"%fileText%"
:: When the above file is calculated by unzip the CRC is
:: 0xa8a9215b, which is -1465310885.

:: Create a hex dump of the file so that each byte value can
:: be calculated from the hex-pair:
CertUtil -f -encodeHex "%fileText%" "%fileHex%" 4 >NUL: 2>&1

:: You can speed up the testing by calling ':setTable' once without
:: SETLOCAL to get it in your console's environment, then REM this line.
Call :setTable

:: Calculate the CRC:
Call :getCRC32 crc "%fileHex%"

:: Examine the result:
Echo; Expected crc32=-1465310885
Echo;Calculated crc32=%crc%

ERASE "%fileText%" "%fileHex%"
Goto :EOF

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:setTable
:: /* generate a crc for every 8-bit value */
:: for (n = 0; n < 256; n++) {
:: c = (ulg)n;
:: for (k = 8; k; k--)
:: c = c & 1 ? xor ^ (c >> 1) : c >> 1;
:: crctab_p[n] = REV_BE(c);
:: }
Set /A "xor=0xEDB88320"
For /L %%n in (0, 1, 255) Do (
Set /A "c=%%n"
For /L %%k in (8, -1, 1) Do (
Set /A "t=c&1, c>>=1"
If !t! NEQ 0 Set /A "c=xor^c"
Set /A "TABLE%%n=c"
)
)
Goto :EOF

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:getCRC32 <var name> <name of hex file>
::# define CRC32(c, b, crctab) (crctab[((int)(c) ^ (b)) & 0xff] ^ ((c) >> 8))
Set "crc=0xFFFFFFFF"
For /F "usebackq delims=" %%L in ("%~2") Do (
For %%B in (%%L) Do (
Set /A "n=(crc^0x%%B)&0xFF"
For %%i in (!n!) Do Set "n=!TABLE%%i!"
Set /A "crc=n^(crc>>8)"
)
)
Set /A "crc^=0xFFFFFFFF"
EndLocal & Set "%~1=%crc%"
Goto :EOF
:: END SCRIPT ::::::::::::::::::::::::::::::::::::::::::::::::::::

[Liviu]

"Frank Westlake" wrote...

> I'm having difficulty finding the right CRC32 algorithms which
> are used by the various ZIP programs to calculate a CRC

The CRC32 described at http://tools.ietf.org/html/rfc1952#section-8
for GZIP is the same as the one used by PKZip/ZMODEM/etc and
essentially matches the info-zip sources you quoted.

> Those are the two I have below (in :setTable and :getCRC32)
> and they obviously fail

First issue is that the C code does unsigned right shifts (0-filled)
while the batch >> does signed ones (sign-extended). Following
couple of changes fix this.

rem Set /A "t=c&1, c>>=1"
Set /A "t=c&1, c=(c>>1)&0x7FFFFFFF"

rem Set /A "crc=n^(crc>>8)"
Set /A "crc=n^((crc>>8)&0xFFFFFF)"

The other issue, at least under xp.sp3, is that a value of 0xFFFFFFFF
set in a variable is internally capped at 0x7FFFFFFF when later used
in a set/a calculation (*). Following changes fix that, too.

rem Set "crc=0xFFFFFFFF"
Set /A "crc=~0"

rem Set /A "crc^=0xFFFFFFFF"
rem EndLocal & Set "%~1=%crc%"
EndLocal & Set /A "%~1=~crc"

With the changes above, your CRC32 appears to calculate correctly.

Liviu

(*) More at http://www.dostips.com/forum/viewtopic.php?p=24799

[Bob]

On 3/13/2013 10:21 PM, Liviu wrote:
> First issue is that the C code does unsigned right shifts (0-filled)
> while the batch >> does signed ones (sign-extended). Following
> couple of changes fix this.

<snip>

> The other issue, at least under xp.sp3, is that a value of 0xFFFFFFFF
> set in a variable is internally capped at 0x7FFFFFFF when later used
> in a set/a calculation (*). Following changes fix that, too.

<snip>

Nice work Liviu!

Using WIN 7 I made the changes to Frank's script that you posted and
fed the output to results.txt.

C:\>type results.txt
Expected crc32=-1465310885
Calculated crc32=-1465310885
C:\>

Below is Frank's work that was edited to include your code lines.

:: BEGIN SCRIPT :::::::::::::::::::::::::::::::::::::::::::::::::::::
:: REQUIRES CERTUTIL.exe
@Echo OFF
SetLocal EnableExtensions EnableDelayedExpansion

Set "fileText=crc32.txt"
Set "fileHex=crc32.hex"

Echo;How now brown cow? >"%fileText%"

:: When the above file is calculated by unzip the CRC is
:: 0xa8a9215b, which is -1465310885.

:: Create a hex dump of the file so that each byte value can
:: be calculated from the hex-pair:
CertUtil -f -encodeHex "%fileText%" "%fileHex%" 4 >NUL: 2>&1

:: You can speed up the testing by calling ':setTable' once without
:: SETLOCAL to get it in your console's environment, then REM this line.
Call :setTable

:: Calculate the CRC:
Call :getCRC32 crc "%fileHex%"

:: Examine the result:

Echo; Expected crc32=-1465310885>>results.txt
Echo;Calculated crc32=%crc%>>results.txt

ERASE "%fileText%" "%fileHex%"
Goto :EOF

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:setTable
:: /* generate a crc for every 8-bit value */
:: for (n = 0; n < 256; n++) {
:: c = (ulg)n;
:: for (k = 8; k; k--)
:: c = c & 1 ? xor ^ (c >> 1) : c >> 1;
:: crctab_p[n] = REV_BE(c);
:: }
Set /A "xor=0xEDB88320"
For /L %%n in (0, 1, 255) Do (
Set /A "c=%%n"
For /L %%k in (8, -1, 1) Do (

REM Set /A "t=c&1, c>>=1"

Set /A "t=c&1, c=(c>>1)&0x7FFFFFFF"

If !t! NEQ 0 Set /A "c=xor^c"
Set /A "TABLE%%n=c"
)
)
Goto :EOF

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:getCRC32 <var name> <name of hex file>
::# define CRC32(c, b, crctab) (crctab[((int)(c) ^ (b)) & 0xff] ^ ((c)
>> 8))

REM Set "crc=0xFFFFFFFF"
Set /A "crc=~0"

For /F "usebackq delims=" %%L in ("%~2") Do (
For %%B in (%%L) Do (
Set /A "n=(crc^0x%%B)&0xFF"
For %%i in (!n!) Do Set "n=!TABLE%%i!"

REM Set /A "crc=n^(crc>>8)"
Set /A "crc=n^((crc>>8)&0xFFFFFF)"
)
)
REM Set /A "crc^=0xFFFFFFFF"
REM EndLocal & Set "%~1=%crc%"

EndLocal & Set /A "%~1=~crc"

Goto :EOF
:: END SCRIPT ::::::::::::::::::::::::::::::::::::::::::::::::::::

::Later

[Frank Westlake]

2013-03-13 19:21, Liviu:

> First issue is that the C code does unsigned right shifts (0-filled)
> while the batch >> does signed ones (sign-extended).

> The other issue, at least under xp.sp3, is that a value of 0xFFFFFFFF
> set in a variable is internally capped at 0x7FFFFFFF when later used
> in a set/a calculation (*).

Thank you very much. I thought the problem might be related to the
sign-bit but I didn't know how to apply the fix.

Thanks for your test Bob.

Frank

[jgharston]

Non-table-driven PKZIP CRC32, tested, working, embedded in working
programs, reference code here:

http://mdfs.net/Info/Comp/Comms/CRC32.htm

JGH