32-bit CRC Algorithm
Author Message
32-bit CRC Algorithm

: Does anyone know where I could find efficient source code for a 32-bit CRC
: subprogram? [...] about \$250,000 in CPU time each year [...} COBOL program
: that simply computes a 32-bit CRC from : a 500-byte buffer.
: I already converted it to assembly language [...] cost to \$10,000 per year,
: but I'd like to shoot for something less than \$5,000...

Please give us a solid interface spec for this subroutine.  Then we
can run it this weekend as a homework problem.

On the PDP-8 binary paper
tape, I think the CRC was simply the twos complement of the sum of
the other words on the tape.  I never saw it on IBM 360.
If your CRC is that simple, you are looking at one add instruction
inside a one BXLE instruction loop.
--                                  __  __

:-)    Search Service Development  \_\/_/\/  Office:  B5/F4/MA/54S05
The opinions I assert are opinion.  \_\_\/\  (513) 865-6800 x-4733
Home:  682 Deerfield Dr.            /_/_/\/  Lexis-Nexis, POB 933
Harrison, OH 45030  (513) 367-5653  \_\_\/   Dayton, OH  45401

Tue, 14 Dec 1999 03:00:00 GMT
32-bit CRC Algorithm

Quote:
> On the PDP-8 binary paper
> tape, I think the CRC was simply the twos complement of the sum of
> the other words on the tape.  I never saw it on IBM 360.
> If your CRC is that simple, you are looking at one add instruction
> inside a one BXLE instruction loop.

Hmmm.... I think it's a little more complex than that, but nevertheless
simple.  It involves multiplication by [odd?] powers of a polynomial.  I
don't have the spec, and I agree that it would be a fun thing to program.
I could even try out my S/390 emulator on it ;->

Yes, we need the specs.

Tue, 14 Dec 1999 03:00:00 GMT
32-bit CRC Algorithm

| Does anyone know where I could find efficient source code for a 32-bit CRC
| subprogram?
|
| My company spends about \$250,000 in CPU time each year on a very
| inefficient 150-line COBOL program that simply computes a 32-bit CRC from
| a 500-byte buffer.
|
| I already converted it to assembly language, but I'm not sure it's as
| efficient as it should be (of course, I've probably already reduced the
| cost to \$10,000 per year, but I'd like to shoot for something less than
| help!

I found this short one in C in my archive:

_FILE VERIFICATION USING CRC_
by Mark R. Nelson

[LISTING ONE]

*/

/* Instead of performing a straightforward calculation of the 32-bit CRC usin
* a series of logical operations, program uses faster table lookup method. */

#include <stdio.h>

unsigned long CalculateBufferCRC(unsigned int count,unsigned long crc,void
*buffer);

unsigned long CRCTable[256];

#define CRC32_POLYNOMIAL     0xEDB88320L

void BuildCRCTable()
{
int i;
int j;
unsigned long crc;

for ( i = 0; i <= 255 ; i++ ) {
crc = i;
for ( j = 8 ; j > 0; j-- ) {
if ( crc & 1 )
crc = ( crc >> 1 ) ^ CRC32_POLYNOMIAL;
else
crc >>= 1;
}
CRCTable[ i ] = crc;
}

Quote:
}

/* This routine is responsible for actually performing the calculation of the
* 32-bit CRC for the entire file. We precondition the CRC value with all 1's
* then invert every bit after the entire file has been done. This gives us a
* CRC value that corresponds with the values calculated by PKZIP and ARJ. */
void main()
{
unsigned long crc;

BuildCRCTable();

crc = 0xFFFFFFFFL;
crc = CalculateBufferCRC( 15, crc, "Dit is een test" );
crc ^= 0xFFFFFFFFL;

printf("CRC-32=%-8.8X\n",crc);

Quote:
}

/* Routine calculates the CRC for a block of data using table lookup method.
* It accepts an original value for the crc, and returns the updated value. */
unsigned long CalculateBufferCRC( count, crc, buffer )
unsigned int count;
unsigned long crc;
void *buffer;
{
unsigned char *p;
unsigned long temp1;
unsigned long temp2;

p = (unsigned char*) buffer;
while ( count-- != 0 ) {
temp1 = ( crc >> 8 ) & 0x00FFFFFFL;
temp2 = CRCTable[ ( (int) crc ^ *p++ ) & 0xff ];
crc = temp1 ^ temp2;
}
return( crc );

Quote:
}

Ron van Wier

--
------------------------------------------------------------------------

Tue, 14 Dec 1999 03:00:00 GMT
32-bit CRC Algorithm

Quote:

>I converted the 32-bit CRC algorithm from a COBOL program, so forgive me
>if what I say here does not reflect reality!  Nevertheless, this seems to
>be what the program is doing:

>INPUT:      DATALEN (full-word),  DATABUF (up to 8,000-bytes, generally less
>than 500).

>OUTPUT:  CRC (full-word).

>Set CRC to zero.
>Loop for each byte (1 through DATALEN) in DATABUF:
>  Set BYTE to next byte in DATABUF.
>  Loop for each of the 8-bits in a byte:
>    Shift BYTE left 1-bit, putting carry into BIT1
>    Shift CRC left 1-bit, putting carry into BIT2
>    If (BIT1 not equal to BIT2)
>      Invert all bits in CRC  (e.g., B'10010111' would become B'01101000')
>    Endif
>  Endloop
>Endloop
>Return(CRC)

>As I mentioned, this might not be the most efficient way to code a 32-bit
>CRC, but I think it is the algorithm my company's COBOL program tried to
>emulate.  When I converted the routine, I moved everything to a register
>and coded the inner loop as a macro that I included 8-times (since a
>CSECT consumes 4K, the trade-off of storage for CPU seemed good).  I
>wondered if there was a way to eliminate or optimize the inner loop,
>since that's where most of the CPU time would be consumed, but I couldn't
>think of a way to do that.  I also tried to cheat by searching the
>Internet for a good 32-bit CRC algorithm, but I was surprised at how
>difficult it was to find.  Any help would be appreciated.

Do you need to produce the *same* checksum as your current program
does, or will any good checksum algorithm do ?

If the latter, you might look at the CHECKSUM instruction in the new
POO (online at
http://ppdbooks.pok.ibm.com:80/cgi-bin/bookmgr/bookmgr.cmd/BOOKS/DZ9A...
).  There is certainly enough information to implement it, and if/when
you find that you are running on a machine that has it in microcode
you will presumably get even better performance.

If I understand the description correctly, what you need is (with
arbitrary registers for the example):

R1: checksum (zero it to start)
R3: length of databuf

LR    R4,R2          R4 -> area
AR    R4,R3          R4 -> end of area + 1
LA    R5,4           R5 := increment amount
LOOP AL    R1,0(,R2)      Add portion of data
BC    12,*+8         Skip NSI if no carry
AL    R1,=F'1'       Add 1 if carry
BXLE  R2,R4,LOOP     Continue...

This code fragment doesn't deal with databuf not a multiple of 4, and
may well be wrong in other respects, but I trust it gets the idea
across.

Tony Harminc
Usual disclaimers, my opinions only, etc.
In particular, if running this code causes your CPU to catch fire I
take no responsibility, results may be incorrect or incomplete, may
not suit your purposes, no patent rights are granted or implied, your
mileage may vary, etc.

Fri, 17 Dec 1999 03:00:00 GMT
32-bit CRC Algorithm

Quote:

>| Does anyone know where I could find efficient source code for a 32-bit CRC
>| subprogram?

[snip]

For lots of info on CRC calculation, look at:

ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt

Regards,
Dave

Sat, 08 Jan 2000 03:00:00 GMT
32-bit CRC Algorithm

>Does anyone know where I could find efficient source code for a 32-bit
CRC
>subprogram?
>
>My company spends about \$250,000 in CPU time each year on a very
>inefficient 150-line COBOL program that simply computes a 32-bit CRC from
>a 500-byte buffer.
>
>I already converted it to assembly language, but I'm not sure it's as
>efficient as it should be (of course, I've probably already reduced the
>cost to \$10,000 per year, but I'd like to shoot for something less than
>help!

If you're still interested, let me know.

I believe I have a ZModem-style CRC-32 routine in S/370 assembler, C, and
Think C compatible 68000 assembler.

Wed, 19 Jan 2000 03:00:00 GMT

 Page 1 of 1 [ 10 post ]

Relevant Pages